Codificación/decodificación de código Morton 2D de 64 bits

6 minutos de lectura

avatar de usuario
Dawid Szymański

Cómo codificar / decodificar códigos morton (orden z) dado [x, y] como enteros sin signo de 32 bits que producen código morton de 64 bits, y viceversa? Tengo xy2d y d2xy pero solo para coordenadas de 16 bits de ancho que producen un número morton de 32 bits. Busqué mucho en la red, pero no pude encontrar. Por favor ayuda.

  • Realmente no es difícil extender una versión de 32 bits a 64 bits. Duplica el ancho de todas las máscaras y agrega un paso adicional siguiendo el mismo patrón que los demás.

    – harold

    29 mayo 2015 a las 22:16


avatar de usuario
Nils Pipenbrinck

Si es posible que utilice instrucciones específicas de la arquitectura, es probable que pueda acelerar la operación más allá de lo que es posible utilizando trucos de modificación de bits:

Por ejemplo, si escribe código para Intel Haswell y CPU posteriores, puede usar el conjunto de instrucciones BMI2 que contiene el pext y pdep instrucciones. Estos pueden (entre otras cosas geniales) usarse para construir sus funciones.

Aquí hay un ejemplo completo (probado con 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);
}

Si tiene que admitir CPU anteriores o la plataforma ARM, no todo está perdido. Todavía puede obtener al menos ayuda para la función xy_to_morton de las instrucciones específicas para criptografía.

Muchas CPU tienen soporte para la multiplicación sin acarreo en estos días. En ARM eso será vmul_p8 del conjunto de instrucciones NEON. En X86 lo encontrarás como PCLMULQDQ del conjunto de instrucciones CLMUL (disponible desde 2010).

El truco aquí es que una multiplicación sin acarreo de un número consigo mismo devolverá un patrón de bits que contiene los bits originales del argumento con bits cero intercalados. Por lo tanto, es idéntico al _pdep_u32(x,0x55555555) que se muestra arriba. Por ejemplo, convierte el siguiente byte:

 +----+----+----+----+----+----+----+----+
 | b7 | b6 | b5 | b4 | b3 | b2 | b1 | b0 |
 +----+----+----+----+----+----+----+----+

Dentro:

 +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
 | 0  | b7 | 0  | b6 | 0  | b5 | 0  | b4 | 0  | b3 | 0  | b2 | 0  | b1 | 0  | b0 |
 +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+

Ahora puede construir la función xy_to_morton como (aquí se muestra para el conjunto de instrucciones 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 genera un resultado de 128 bits del cual solo usamos los 64 bits inferiores. Entonces, incluso puede mejorar la versión anterior y usar un solo _mm_clmulepi64_si128 para hacer el trabajo.

Eso es lo mejor que puede obtener en las principales plataformas (por ejemplo, ARM moderno con NEON y x86). Desafortunadamente, no conozco ningún truco para acelerar la función morton_to_xy usando las instrucciones de criptografía y lo intenté mucho durante varios meses.

  • Realmente grandioso. apreciar

    – Dawid Szymański

    30 de mayo de 2015 a las 0:45

  • @DawidSzymański Si quiere más, le sugiero que consulte este blog: bitmath.blogspot.de y lea sobre aritmética tesseral (eso es hacer aritmética con números almacenados en orden morton sin codificarlos/descifrarlos). Estoy bastante seguro de que puedes usarlo para tus cosas de curvas que llenan el espacio.

    – Nils Pipenbrinck

    30 de mayo de 2015 a las 0:52

  • @harold, el hecho divertido es: hemos disfrutado de la rareza matemática de los poderes de la operación x*x en GF(2’m). Sin embargo, a la gente de las criptomonedas también les gusta tener un sqrt(x) rápido en GF(2’m). Ya se enteraron de que se trata de separar incluso de los bits impares, pero aún no conocen los trucos de los bits… ¡Creo que todos pueden aprender de eso!

    – Nils Pipenbrinck

    31 mayo 2015 a las 20:20

  • @NilsPipenbrinck golpeando esta respuesta después de tanto tiempo, ¿inquisitivo por el hecho de si existen para un espacio 3D? digamos codificar x, y, z en orden Z y viceversa.

    – datapanda

    7 de mayo de 2018 a las 0:20

avatar de usuario
Dawid Szymański

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

  • En morton_1¿no debería ser ese último valor 0x00000000FFFFFFFF?

    –Todd Lehman

    31 de julio de 2015 a las 1:34

  • PD morton_1 podría devolver un uint32_t.

    –Todd Lehman

    31 de julio de 2015 a las 1:35

avatar de usuario
Sami Kuhmonen

El código ingenuo sería el mismo independientemente del número de bits. Si no necesita una versión de giro de bits súper rápida, esto servirá

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

Si necesita girar un poco más rápido, entonces este debería funcionar. Tenga en cuenta que x e y tienen que ser variables de 64 bits.

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

  • ¿Más interesado en la forma rápida e inversa?

    – Dawid Szymański

    29 mayo 2015 a las 22:38

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad