c - 2D莫顿码编码/解码64位

如何将给定[x，y]的莫顿码（z阶）编码/解码为产生64位莫顿码的32位无符号整数，反之亦然？
我有xy2d和d2xy，但只适用于16位宽的坐标，产生32位莫顿数。在网上搜了很多，但找不到。请帮忙。

最佳答案

如果您可以使用特定于体系结构的指令，那么您将能够加速操作，而不必使用比特抖动黑客：
例如，如果您为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位。因此，您甚至可以改进以上版本，并使用一个单一的clmulepi64_si128来完成这项工作。
这是在主流平台上所能得到的最好结果（例如，配备Neon和x86的现代ARM）。不幸的是，我不知道用密码指令加速morton-to-xy函数的任何技巧，我花了好几个月的努力。

关于c - 2D莫顿码编码/解码64位，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30539347/