Code morton 2D encoder / décoder 64bits

Comment encoder / décoder les codes morton (ordre z) à partir de [x, y] sous forme d’entiers non signés 32 bits produisant un code morton 64 bits, et vice-versa? J’ai effectivement xy2d et d2xy, mais uniquement pour les coordonnées d’une largeur de 16 bits produisant un nombre morton de 32 bits. J’ai beaucoup cherché dans le réseau, mais je n’ai pas trouvé. S’il vous plaît aider.

S’il vous est possible d’utiliser des instructions spécifiques à l’architecture, vous serez probablement en mesure d’accélérer l’opération au-delà de ce qui est possible avec des bidouilles bidirectionnelles:

Par exemple, si vous écrivez du code pour les processeurs Intel Haswell et ultérieurs, vous pouvez utiliser le jeu d’instructions BMI2 contenant les instructions pext et pdep . Ceux-ci peuvent (entre autres choses) être utilisés pour créer vos fonctions.

Voici un exemple complet (testé avec GCC):

 #include  #include  // on GCC, comstack 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 vous devez prendre en charge des processeurs antérieurs ou la plate-forme ARM, tout n’est pas perdu. Vous pouvez toujours obtenir au moins de l’aide pour la fonction xy_to_morton à partir d’instructions spécifiques à la cryptographie.

De nos jours, de nombreux processeurs prennent en charge la multiplication sans report. Sur ARM, ce sera vmul_p8 partir du jeu d’instructions NEON. Sous X86, vous le trouverez sous le nom PCLMULQDQ dans le jeu d’instructions CLMUL (disponible depuis 2010).

Le truc, c’est qu’une multiplication sans retenue d’un nombre avec lui-même renvoie un modèle de bits contenant les bits d’origine de l’argument avec des bits nuls entrelacés. Donc, il est identique au _pdep_u32 (x, 0x55555555) montré ci-dessus. Par exemple, il tourne l’octet suivant:

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

Dans:

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

Vous pouvez maintenant construire la fonction xy_to_morton sous la forme (illustrée ici pour le jeu d’instructions CLMUL):

 #include  #include  // on GCC, comstack 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 génère un résultat de 128 bits dont nous utilisons uniquement les 64 bits inférieurs. Ainsi, vous pouvez même améliorer la version ci-dessus et utiliser un seul _mm_clmulepi64_si128 faire le travail.

C’est tout ce que vous pouvez obtenir sur les plates-formes classiques (par exemple, ARM moderne avec NEON et x86). Malheureusement, je ne connais aucune astuce pour accélérer la fonction morton_to_xy en utilisant les instructions de cryptographie et j'ai vraiment essayé pendant plusieurs mois.

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

Le code naïf serait le même, indépendamment du nombre de bits. Si vous n’avez pas besoin de la version très rapide du twiddling, cela suffira

 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 vous avez besoin d'un peu plus rapidement, alors celui-ci devrait fonctionner. Notez que x et y doivent être des variables 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);