morton.h (3042B)
1 /* Copyright (C) 2013-2023, 2025 Vincent Forest (vaplv@free.fr) 2 * 3 * The RSys library is free software: you can redistribute it and/or modify 4 * it under the terms of the GNU General Public License as published 5 * by the Free Software Foundation, either version 3 of the License, or 6 * (at your option) any later version. 7 * 8 * The RSys library is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * GNU General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public License 14 * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */ 15 16 #ifndef MORTON_H 17 #define MORTON_H 18 19 #include "rsys.h" 20 21 static FINLINE uint32_t 22 morton2D_encode_u16(const uint16_t u16) 23 { 24 uint32_t u32 = u16; 25 u32 = (u32 | (u32 << 8)) & 0x00FF00FF; 26 u32 = (u32 | (u32 << 4)) & 0X0F0F0F0F; 27 u32 = (u32 | (u32 << 2)) & 0x33333333; 28 u32 = (u32 | (u32 << 1)) & 0x55555555; 29 return u32; 30 } 31 32 static FINLINE uint16_t 33 morton2D_decode_u16(const uint32_t u32) 34 { 35 uint32_t x = u32 & 0x55555555; 36 x = (x | (x >> 1)) & 0x33333333; 37 x = (x | (x >> 2)) & 0x0F0F0F0F; 38 x = (x | (x >> 4)) & 0x00FF00FF; 39 x = (x | (x >> 8)) & 0x0000FFFF; 40 return (uint16_t)x; 41 } 42 43 static INLINE uint64_t 44 morton3D_encode_u21(const uint32_t u21) 45 { 46 uint64_t u64 = u21 & ((1<<21) - 1); 47 ASSERT(u21 <= ((1 << 21) - 1)); 48 u64 = (u64 | (u64 << 32)) & 0xFFFF00000000FFFF; 49 u64 = (u64 | (u64 << 16)) & 0x00FF0000FF0000FF; 50 u64 = (u64 | (u64 << 8)) & 0xF00F00F00F00F00F; 51 u64 = (u64 | (u64 << 4)) & 0x30C30C30C30C30C3; 52 u64 = (u64 | (u64 << 2)) & 0x9249249249249249; 53 return u64; 54 } 55 56 static INLINE uint32_t 57 morton3D_decode_u21(const uint64_t u64) 58 { 59 uint64_t tmp = (u64 & 0x9249249249249249); 60 tmp = (tmp | (tmp >> 2)) & 0x30C30C30C30C30C3; 61 tmp = (tmp | (tmp >> 4)) & 0xF00F00F00F00F00F; 62 tmp = (tmp | (tmp >> 8)) & 0x00FF0000FF0000FF; 63 tmp = (tmp | (tmp >> 16)) & 0xFFFF00000000FFFF; 64 tmp = (tmp | (tmp >> 32)) & 0x00000000FFFFFFFF; 65 ASSERT(tmp <= ((1<<21)-1)); 66 return (uint32_t)tmp; 67 } 68 69 static INLINE uint32_t 70 morton_xy_encode_u16(const uint16_t xy[2]) 71 { 72 ASSERT(xy); 73 return (morton2D_encode_u16(xy[0]) << 1) 74 | (morton2D_encode_u16(xy[1]) << 0); 75 } 76 77 static INLINE void 78 morton_xy_decode_u16(const uint32_t code, uint16_t xy[2]) 79 { 80 ASSERT(xy); 81 xy[0] = (uint16_t)morton2D_decode_u16(code >> 1); 82 xy[1] = (uint16_t)morton2D_decode_u16(code >> 0); 83 } 84 85 static INLINE uint64_t 86 morton_xyz_encode_u21(const uint32_t xyz[3]) 87 { 88 ASSERT(xyz); 89 return (morton3D_encode_u21(xyz[0]) << 2) 90 | (morton3D_encode_u21(xyz[1]) << 1) 91 | (morton3D_encode_u21(xyz[2]) << 0); 92 } 93 94 static INLINE void 95 morton_xyz_decode_u21(const uint64_t code, uint32_t xyz[3]) 96 { 97 ASSERT(xyz && code < (((uint64_t)1 << 63)-1)); 98 xyz[0] = (uint32_t)morton3D_decode_u21(code >> 2); 99 xyz[1] = (uint32_t)morton3D_decode_u21(code >> 1); 100 xyz[2] = (uint32_t)morton3D_decode_u21(code >> 0); 101 } 102 103 #endif /* MORTON_H */