C语言 2D移动码编码/解码64bit

Question

如何编码/解码给定[x, y]为32位无符号整数的莫顿码(z顺序)，产生64位莫顿码，反之亦然?我确实有xy2d和d2xy，但仅适用于16位宽的坐标，产生32位摩尔数。在网上搜索了很多，但是没有找到。请帮助。

Answer 1

如果您可以使用特定于体系结构的指令，那么您可能能够加速操作，而不是使用比特操纵的hack:

例如，如果你为Intel Haswell和以后的cpu编写代码，你可以使用包含pext和pdep指令的BMI2指令集。这些都可以用来构建你的函数。

下面是一个完整的示例(使用GCC测试):

#include <immintrin.h>
#include <stdint.h>
// 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平台，并不是所有的都丢失了。对于xy_to_morton函数，您至少可以从特定于密码学的指令中获得帮助。

现在很多cpu都支持无进位乘法。在ARM上，这将是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 <wmmintrin.h>
#include <stdint.h>
// 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函数，我真的努力尝试了几个月。

Answer 2

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
uint32_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)) & 0x00000000FFFFFFFF;
    return (uint32_t)x;
}
void d2xy_morton(uint64_t d, uint64_t &x, uint64_t &y)
{
    x = morton_1(d);
    y = morton_1(d >> 1);
}

Answer 3

naïve代码与位计数无关。如果你不需要超快的比特旋转版本，这将做

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);