2D morton代码编码/解码64位
如何将[x，y]的morton代码（z-order）编码/解码为32位无符号整数，产生64位morton代码，反之亦然？ 我确实有xy2d和d2xy，但仅适用于16位宽的坐标，产生32位莫顿数。 在网上搜索了很多，但找不到。 请帮忙。
如果你可以使用体系结构特定的指令，你可能会加速操作超出使用bit-twiddeling hacks的可能性：
例如，如果您为Intel Haswell和更高版本的CPU编写代码，则可以使用包含pext和pdep指令的BMI2指令集。 这些可以（以及其他伟大的事情）用于构建您的function。
这是一个完整的例子（用GCC测试）：
#include #include // on GCC, compile with option -mbmi2, requires Haswell or better. uint64_t xy_to_morton(uint32_t x, uint32_t y) { return _pdep_u32(x, 0x55555555) | _pdep_u32(y,0xaaaaaaaa); } void morton_to_xy(uint64_t m, uint32_t *x, uint32_t *y) { *x = _pext_u64(m, 0x5555555555555555); *y = _pext_u64(m, 0xaaaaaaaaaaaaaaaa); }
如果必须支持早期的CPU或ARM平台，则不会丢失所有CPU或ARM平台。 您仍然可以从特定于加密的指令获得xy_to_morton函数的至少帮助。
如今，很多CPU都支持无负载乘法。 在ARM上， vmul_p8来自NEON指令集的vmul_p8 。 在X86上，您将从CLMUL指令集（自2010年起可用）中将其发现为PCLMULQDQ 。
这里的技巧是，数字与自身的无进位乘法将返回一个位模式，该位模式包含零比特交错的参数的原始位。 所以它与上面显示的_pdep_u32（x，0x55555555）相同。 例如，它会转换以下字节：
+----+----+----+----+----+----+----+----+ | b7 | b6 | b5 | b4 | b3 | b2 | b1 | b0 | +----+----+----+----+----+----+----+----+
成：
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ | 0 | b7 | 0 | b6 | 0 | b5 | 0 | b4 | 0 | b3 | 0 | b2 | 0 | b1 | 0 | b0 | +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
现在您可以构建xy_to_morton函数（此处显示为CLMUL指令集）：
#include #include // on GCC, compile with option -mpclmul uint64_t carryless_square (uint32_t x) { uint64_t val[2] = {x, 0}; __m128i *a = (__m128i * )val; *a = _mm_clmulepi64_si128 (*a,*a,0); return val[0]; } uint64_t xy_to_morton (uint32_t x, uint32_t y) { return carryless_square(x)|(carryless_square(y) <<1); }
_mm_clmulepi64_si128生成128位结果，我们只使用低64位。 所以你甚至可以改进上面的版本并使用单个_mm_clmulepi64_si128来完成这项工作。
这与主流平台（例如具有NEON和x86的现代ARM）一样好。 不幸的是，我不知道使用密码学指令加速morton_to_xy函数的任何技巧，我在几个月内努力了。
void xy2d_morton(uint64_t x, uint64_t y, uint64_t *d) { x = (x | (x << 16)) & 0x0000FFFF0000FFFF; x = (x | (x << 8)) & 0x00FF00FF00FF00FF; x = (x | (x << 4)) & 0x0F0F0F0F0F0F0F0F; x = (x | (x << 2)) & 0x3333333333333333; x = (x | (x << 1)) & 0x5555555555555555; y = (y | (y << 16)) & 0x0000FFFF0000FFFF; y = (y | (y << 8)) & 0x00FF00FF00FF00FF; y = (y | (y << 4)) & 0x0F0F0F0F0F0F0F0F; y = (y | (y << 2)) & 0x3333333333333333; y = (y | (y << 1)) & 0x5555555555555555; *d = x | (y << 1); } // morton_1 - extract even bits uint64_t morton_1(uint64_t x) { x = x & 0x5555555555555555; x = (x | (x >> 1)) & 0x3333333333333333; x = (x | (x >> 2)) & 0x0F0F0F0F0F0F0F0F; x = (x | (x >> 4)) & 0x00FF00FF00FF00FF; x = (x | (x >> 8)) & 0x0000FFFF0000FFFF; x = (x | (x >> 16)) & 0xFFFFFFFFFFFFFFFF; return x; } void d2xy_morton(uint64_t d, uint64_t *x, uint64_t *y) { *x = morton_1(d); *y = morton_1(d >> 1); }
无论位数如何，天真的代码都是相同的。 如果你不需要超快速位的twiddling版本，这样做
uint32_t x; uint32_t y; uint64_t z = 0; for (int i = 0; i < sizeof(x) * 8; i++) { z |= (x & (uint64_t)1 << i) << i | (y & (uint64_t)1 << i) << (i + 1); }
如果你需要更快的比特，那么这个应该工作。 请注意，x和y必须是64位变量。
uint64_t x; uint64_t y; uint64_t z = 0; x = (x | (x << 16)) & 0x0000FFFF0000FFFF; x = (x | (x << 8)) & 0x00FF00FF00FF00FF; x = (x | (x << 4)) & 0x0F0F0F0F0F0F0F0F; x = (x | (x << 2)) & 0x3333333333333333; x = (x | (x << 1)) & 0x5555555555555555; y = (y | (y << 16)) & 0x0000FFFF0000FFFF; y = (y | (y << 8)) & 0x00FF00FF00FF00FF; y = (y | (y << 4)) & 0x0F0F0F0F0F0F0F0F; y = (y | (y << 2)) & 0x3333333333333333; y = (y | (y << 1)) & 0x5555555555555555; z = x | (y << 1);