2D код Morton кодировать / декодировать 64 бит

Как кодировать / декодировать коды трибуны (z-порядок), заданные [x, y] как 32-битные целые числа без знака, производящие 64-битный код трибуны, и наоборот? У меня есть xy2d и d2xy, но только для координат шириной 16 бит, производящих 32-битное число Morton. Много искал в сети, но не смог найти. Пожалуйста помоги.

Источник

3 ответа

Решение

Если вы сможете использовать специфические для архитектуры инструкции, вы, вероятно, сможете ускорить работу за пределы того, что возможно с помощью хитов с бит-твиддлингом:

Например, если вы пишете код для процессоров Intel Haswell и более поздних, вы можете использовать набор инструкций BMI2, который содержит pext а также pdep инструкции. Они могут (помимо прочего) использоваться для создания ваших функций.

Вот полный пример (протестирован с 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);
}

Если вам нужно поддерживать более ранние процессоры или платформу ARM, не все потеряно. Вы по-прежнему можете получить, по крайней мере, помощь для функции xy_to_morton из инструкций, специфичных для криптографии.

В наши дни многие процессоры поддерживают умножение без переноса. На ARM это будет vmul_p8 из набора команд NEON. На X86 вы найдете его как PCLMULQDQ из набора инструкций CLMUL (доступно с 2010 года).

Хитрость в том, что умножение числа без переноса на самого себя вернет битовый шаблон, который содержит исходные биты аргумента с чередованием нулевых битов. Таким образом, он идентичен _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, который сделает эту работу.

Это так же хорошо, как вы можете получить на основных платформах (например, современные ARM с NEON и x86). К сожалению, я не знаю какой-либо хитрости для ускорения функции 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);
}
Источник

Наивный код будет одинаковым независимо от количества битов. Если вам не нужна супербыстрая версия с битами, это сделает

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);
Источник
Другие вопросы по тегам