/* * This code is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This code is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this code; if not, write to the Free Software * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ /* * Utilities for conversion between integer coordinates, Morton indices, * and Peano-Hilbert indices * * Copyright (C) 2015-2023 Max-Planck-Society * Author: Martin Reinecke */ #include "ducc0/math/space_filling.h" #include "ducc0/infra/error_handling.h" namespace ducc0 { #ifndef DUCC0_USE_PDEP_PEXT #if 0 // this variant is sometimes faster than the functions in the else-branch, but // its tables need valuable L1 space. namespace { static constexpr const uint16_t utab[] = { #define Z(a) 0x##a##0, 0x##a##1, 0x##a##4, 0x##a##5 #define Y(a) Z(a##0), Z(a##1), Z(a##4), Z(a##5) #define X(a) Y(a##0), Y(a##1), Y(a##4), Y(a##5) X(0),X(1),X(4),X(5) #undef X #undef Y #undef Z }; static constexpr const uint16_t ctab[] = { #define Z(a) a,a+1,a+256,a+257 #define Y(a) Z(a),Z(a+2),Z(a+512),Z(a+514) #define X(a) Y(a),Y(a+4),Y(a+1024),Y(a+1028) X(0),X(8),X(2048),X(2056) #undef X #undef Y #undef Z }; } // unnamed namespace uint32_t spread_bits_2D_32 (uint32_t v) { using I=uint32_t; return I(utab[ v &0xff]) | (I(utab[(v>> 8)&0xff])<<16); } uint64_t spread_bits_2D_64 (uint64_t v) { using I=uint64_t; return I(utab[ v &0xff]) | (I(utab[(v>> 8)&0xff])<<16) | (I(utab[(v>>16)&0xff])<<32) | (I(utab[(v>>24)&0xff])<<48); } uint32_t block2morton2D_32 (uint32_t v) { using I=uint32_t; return I(utab[ v &0xff]) | (I(utab[(v>> 8)&0xff])<<16) | (I(utab[(v>>16)&0xff])<<1) | (I(utab[(v>>24)&0xff])<<17); } uint32_t coord2morton2D_32 (std::array xy) { using I=uint32_t; return I(utab[xy[0]&0xff]) | (I(utab[(xy[0]>>8)&0xff])<<16) | (I(utab[xy[1]&0xff])<<1) | (I(utab[(xy[1]>>8)&0xff])<<17); } uint32_t morton2block2D_32 (uint32_t v) { using I=uint32_t; I raw1 = v&0x55555555, raw2 = (v>>1)&0x55555555; raw1|=raw1>>15; raw2|=raw2>>15; return I(ctab[raw1&0xff] ) | I(ctab[(raw1>>8)&0xff]<< 4) | I(ctab[raw2&0xff]<<16) | I(ctab[(raw2>>8)&0xff]<<20); } std::array morton2coord2D_32 (uint32_t v) { using I=uint32_t; I raw1 = v&0x55555555u, raw2 = (v>>1)&0x55555555u; raw1|=raw1>>15; raw2|=raw2>>15; return {I(ctab[raw1&0xff]) | I(ctab[(raw1>>8)&0xff]<<4), I(ctab[raw2&0xff]) | I(ctab[(raw2>>8)&0xff]<<4)}; } uint64_t block2morton2D_64 (uint64_t v) { using I=uint64_t; return I(utab[ v &0xff]) | (I(utab[(v>> 8)&0xff])<<16) | (I(utab[(v>>16)&0xff])<<32) | (I(utab[(v>>24)&0xff])<<48) | (I(utab[(v>>32)&0xff])<< 1) | (I(utab[(v>>40)&0xff])<<17) | (I(utab[(v>>48)&0xff])<<33) | (I(utab[(v>>56)&0xff])<<49); } uint64_t coord2morton2D_64 (std::array xy) { using I=uint64_t; return I(utab[ xy[0] &0xff]) | (I(utab[(xy[0]>> 8)&0xff])<<16) | (I(utab[(xy[0]>>16)&0xff])<<32) | (I(utab[(xy[0]>>24)&0xff])<<48) | (I(utab[ xy[1] &0xff])<< 1) | (I(utab[(xy[1]>> 8)&0xff])<<17) | (I(utab[(xy[1]>>16)&0xff])<<33) | (I(utab[(xy[1]>>24)&0xff])<<49); } uint64_t morton2block2D_64 (uint64_t v) { using I=uint64_t; I raw1 = v&0x5555555555555555, raw2 = (v>>1)&0x5555555555555555; raw1|=raw1>>15; raw2|=raw2>>15; return I(ctab[ raw1 &0xff]) | (I(ctab[(raw1>> 8)&0xff])<< 4) | (I(ctab[(raw1>>32)&0xff])<<16) | (I(ctab[(raw1>>40)&0xff])<<20) | (I(ctab[ raw2 &0xff])<<32) | (I(ctab[(raw2>> 8)&0xff])<<36) | (I(ctab[(raw2>>32)&0xff])<<48) | (I(ctab[(raw2>>40)&0xff])<<52); } std::array morton2coord2D_64 (uint64_t v) { using I=uint64_t; I raw1 = v&0x5555555555555555, raw2 = (v>>1)&0x5555555555555555; raw1|=raw1>>15; raw2|=raw2>>15; return { I(ctab[ raw1 &0xff]) | (I(ctab[(raw1>> 8)&0xff])<< 4) | (I(ctab[(raw1>>32)&0xff])<<16) | (I(ctab[(raw1>>40)&0xff])<<20), I(ctab[ raw2 &0xff]) | (I(ctab[(raw2>> 8)&0xff])<< 4) | (I(ctab[(raw2>>32)&0xff])<<16) | (I(ctab[(raw2>>40)&0xff])<<20)}; } #else inline uint64_t spread_bits_2D_64 (uint64_t v) { v&=0xffffffffu; v = (v|(v<<16)) & 0x0000ffff0000ffffu; v = (v|(v<< 8)) & 0x00ff00ff00ff00ffu; v = (v|(v<< 4)) & 0x0f0f0f0f0f0f0f0fu; v = (v|(v<< 2)) & 0x3333333333333333u; v = (v|(v<< 1)) & 0x5555555555555555u; return v; } inline uint32_t spread_bits_2D_32 (uint32_t v) { v&=0xffffu; v = (v|(v<< 8)) & 0x00ff00ff00ff00ffu; v = (v|(v<< 4)) & 0x0f0f0f0f0f0f0f0fu; v = (v|(v<< 2)) & 0x3333333333333333u; v = (v|(v<< 1)) & 0x5555555555555555u; return v; } namespace { inline uint64_t compress_bits_2D_64 (uint64_t v) { v&=0x5555555555555555u; v = (v|(v>> 1)) & 0x3333333333333333u; v = (v|(v>> 2)) & 0x0f0f0f0f0f0f0f0fu; v = (v|(v>> 4)) & 0x00ff00ff00ff00ffu; v = (v|(v>> 8)) & 0x0000ffff0000ffffu; v = (v|(v>>16)) & 0x00000000ffffffffu; return v; } #if 0 // currently not needed inline uint32_t compress_bits_2D_32 (uint32_t v) { v&=0x55555555u; v = (v|(v>> 1)) & 0x33333333u; v = (v|(v>> 2)) & 0x0f0f0f0fu; v = (v|(v>> 4)) & 0x00ff00ffu; v = (v|(v>> 8)) & 0x0000ffffu; return v; } #endif } // unnamed namespace uint32_t block2morton2D_32 (uint32_t v) { uint64_t t=spread_bits_2D_64(v); return (t | (t>>31)) & 0xffffffffu; } uint32_t coord2morton2D_32 (std::array xy) { uint64_t t=spread_bits_2D_64((xy[0]&0xffff)|(xy[1]<<16)); return (t | (t>>31)) & 0xffffffffu; } uint32_t morton2block2D_32 (uint32_t v) { uint64_t t=v; t|=t<<31; t=compress_bits_2D_64(t); return t; } std::array morton2coord2D_32 (uint32_t v) { uint64_t t=v; t|=t<<31; t=compress_bits_2D_64(t); return {uint32_t(t&0xffff), uint32_t(t>>16)}; } uint64_t block2morton2D_64 (uint64_t v) { return spread_bits_2D_64(v) | (spread_bits_2D_64(v>>32)<<1); } uint64_t coord2morton2D_64 (std::array xy) { return spread_bits_2D_64(xy[0]) | (spread_bits_2D_64(xy[1])<<1); } uint64_t morton2block2D_64 (uint64_t v) { return compress_bits_2D_64(v) | (compress_bits_2D_64(v>>1)<<32); } std::array morton2coord2D_64 (uint64_t v) { return {compress_bits_2D_64(v), compress_bits_2D_64(v>>1)}; } #endif namespace { inline uint32_t spread_bits_3D_32 (uint32_t v) { v&=0x3ff; v = (v|(v<< 8)|(v<<16)) & 0x0f00f00fu; v = (v|(v<< 4)) & 0xc30c30c3u; v = (v|(v<< 2)) & 0x49249249u; return v; } inline uint32_t compress_bits_3D_32 (uint32_t v) { v&=0x9249249u; v = (v|(v>> 2)) & 0xc30c30c3u; v = (v|(v>> 4)) & 0x0f00f00fu; v = (v|(v>> 8)|(v>>16)) & 0x3ffu; return v; } inline uint64_t spread_bits_3D_64 (uint64_t v) { v&=0x1fffff; v = (v|(v<<16)|(v<<32)) & 0x00ff0000ff0000ffu; v = (v|(v<< 8)) & 0xf00f00f00f00f00fu; v = (v|(v<< 4)) & 0x30c30c30c30c30c3u; v = (v|(v<< 2)) & 0x9249249249249249u; return v; } inline uint64_t compress_bits_3D_64 (uint64_t v) { v&=0x1249249249249249u; v=(v|(v>> 2)) & 0x30c30c30c30c30c3u; v=(v|(v>> 4)) & 0xf00f00f00f00f00fu; v=(v|(v>> 8)) & 0x00ff0000ff0000ffu; v=(v|(v>>16)|(v>>32)) & 0x1fffffu; return v; } } // unnamed namespace uint32_t block2morton3D_32 (uint32_t v) { uint32_t v2=v&0xfffff; uint64_t v3=spread_bits_3D_64(v2); v3=(v3|(v3>>29))&0x1fffffff; return uint32_t(v3)|(spread_bits_3D_32(v>>20)<<2); } uint32_t coord2morton3D_32 (std::array xyz) { uint32_t v2=(xyz[0]&0x3ff)|((xyz[1]&0x3ff)<<10); uint64_t v3=spread_bits_3D_64(v2); v3=(v3|(v3>>29))&0x1fffffff; return uint32_t(v3)|(spread_bits_3D_32(xyz[2]&0x3ff)<<2); } uint32_t morton2block3D_32 (uint32_t v) { return compress_bits_3D_32(v) | (compress_bits_3D_32(v>>1)<<10) | (compress_bits_3D_32(v>>2)<<20); } std::array morton2coord3D_32 (uint32_t v) { return {compress_bits_3D_32(v), compress_bits_3D_32(v>>1), compress_bits_3D_32(v>>2)}; } uint64_t block2morton3D_64 (uint64_t v) { return spread_bits_3D_64(v) | (spread_bits_3D_64(v>>21)<<1) | (spread_bits_3D_64(v>>42)<<2); } uint64_t coord2morton3D_64 (std::array xyz) { return spread_bits_3D_64(xyz[0]) | (spread_bits_3D_64(xyz[1])<<1) | (spread_bits_3D_64(xyz[2])<<2); } uint64_t morton2block3D_64 (uint64_t v) { return compress_bits_3D_64(v) | (compress_bits_3D_64(v>>1)<<21) | (compress_bits_3D_64(v>>2)<<42); } std::array morton2coord3D_64 (uint64_t v) { return { compress_bits_3D_64(v), compress_bits_3D_64(v>>1), compress_bits_3D_64(v>>2)}; } #endif namespace { static constexpr const uint8_t m2p2D_1[4][4] = { { 4, 1,11, 2},{ 0,15, 5, 6},{10, 9, 3,12},{14, 7,13, 8}}; static constexpr const uint8_t p2m2D_1[4][4] = { { 4, 1, 3,10},{ 0, 6, 7,13},{15, 9, 8, 2},{11,14,12, 5}}; static constexpr const uint8_t m2p2D_3[4][64] = { { 64, 1,131, 2,206, 79,205,140, 4,199, 69, 70, 8,203, 73, 74, 16,211, 81, 82, 84, 21,151, 22, 158,157, 31,220, 88, 25,155, 26, 186,185, 59,248,182,181, 55,244, 124, 61,191, 62,242,115,241,176, 32,227, 97, 98,100, 37,167, 38, 174,173, 47,236,104, 41,171, 42}, { 0,195, 65, 66, 68, 5,135, 6, 142,141, 15,204, 72, 9,139, 10, 250,123,249,184, 60,255,125,126, 246,119,245,180,178,177, 51,240, 80, 17,147, 18,222, 95,221,156, 20,215, 85, 86, 24,219, 89, 90, 96, 33,163, 34,238,111,237,172, 36,231,101,102, 40,235,105,106}, {170,169, 43,232,166,165, 39,228, 108, 45,175, 46,226, 99,225,160, 154,153, 27,216,150,149, 23,212, 92, 29,159, 30,210, 83,209,144, 48,243,113,114,116, 53,183, 54, 190,189, 63,252,120, 57,187, 58, 202, 75,201,136, 12,207, 77, 78, 198, 71,197,132,130,129, 3,192}, {234,107,233,168, 44,239,109,110, 230,103,229,164,162,161, 35,224, 112, 49,179, 50,254,127,253,188, 52,247,117,118, 56,251,121,122, 218, 91,217,152, 28,223, 93, 94, 214, 87,213,148,146,145, 19,208, 138,137, 11,200,134,133, 7,196, 76, 13,143, 14,194, 67,193,128} }; static constexpr const uint8_t p2m2D_3[4][64] = { { 64, 1, 3,130, 8, 74, 75,201, 12, 78, 79,205,135,198,196, 69, 16, 82, 83,209, 84, 21, 23,150, 92, 29, 31,158,219,153,152, 26, 48,114,115,241,116, 53, 55,182, 124, 61, 63,190,251,185,184, 58, 175,238,236,109,231,165,164, 38, 227,161,160, 34,104, 41, 43,170}, { 0, 66, 67,193, 68, 5, 7,134, 76, 13, 15,142,203,137,136, 10, 96, 33, 35,162, 40,106,107,233, 44,110,111,237,167,230,228,101, 112, 49, 51,178, 56,122,123,249, 60,126,127,253,183,246,244,117, 223,157,156, 30,155,218,216, 89, 147,210,208, 81, 20, 86, 87,213}, {255,189,188, 62,187,250,248,121, 179,242,240,113, 52,118,119,245, 159,222,220, 93,215,149,148, 22, 211,145,144, 18, 88, 25, 27,154, 143,206,204, 77,199,133,132, 6, 195,129,128, 2, 72, 9, 11,138, 32, 98, 99,225,100, 37, 39,166, 108, 45, 47,174,235,169,168, 42}, {191,254,252,125,247,181,180, 54, 243,177,176, 50,120, 57, 59,186, 239,173,172, 46,171,234,232,105, 163,226,224, 97, 36,102,103,229, 207,141,140, 14,139,202,200, 73, 131,194,192, 65, 4, 70, 71,197, 80, 17, 19,146, 24, 90, 91,217, 28, 94, 95,221,151,214,212, 85} }; static constexpr const uint8_t m2p3D_1[24][8]={ {144,119, 97,110, 43, 44, 98,109}, { 36, 35,101,106,127,152,102,105}, { 96, 27,135, 28,161,162,182,181}, {170,169,189,190, 19,104, 20,143}, {134,137,151,112,133,138, 12, 11}, {130,141, 3, 4,129,142,120,159}, {174,173,185,186,103, 60,128, 59}, { 52,111, 51,136,165,166,178,177}, {118,167,117, 92,153,168,154, 91}, {160,145, 83,146,175,126, 84,125}, {114, 75,113,176,157, 76,158,191}, { 68,149,183,150, 67,122,184,121}, { 16,139, 1, 2, 55,140, 14, 13}, {132, 63, 5, 6,131, 24, 10, 9}, { 70, 7, 81, 32, 69,124, 82,123}, {116, 77,115, 90, 15, 78, 40, 89}, { 38, 37, 23,108, 41, 42, 48,107}, { 34, 33, 99, 56, 45, 46,100, 31}, { 0, 73, 39, 94,155, 74,156, 93}, { 66,147, 85,148, 65, 8, 86, 47}, { 72, 71,187,188, 17, 62, 18, 61}, { 54, 25, 53, 26, 79, 64,180,179}, {172,171, 95, 80, 21, 58, 22, 57}, { 50, 29, 49, 30,163,164, 88, 87}}; static constexpr const uint8_t p2m3D_1[24][8]={ {144, 98,102, 44, 45,111,107,113}, {157,111,107, 33, 32, 98,102,124}, { 96,164,165, 25, 27,183,182,130}, {109,169,168, 20, 22,186,187,143}, {115,137,141, 15, 14,132,128,146}, {126,132,128, 2, 3,137,141,159}, {134,186,187, 63, 61,169,168,100}, {139,183,182, 50, 48,164,165,105}, {173,156,158, 95, 91,114,112,161}, {160,145,147, 82, 86,127,125,172}, {179,114,112, 73, 77,156,158,191}, {190,127,125, 68, 64,145,147,178}, { 16, 2, 3,137,141, 15, 14, 52}, { 29, 15, 14,132,128, 2, 3, 57}, { 35, 82, 86,127,125, 68, 64, 1}, { 46, 95, 91,114,112, 73, 77, 12}, { 54, 44, 45,111,107, 33, 32, 18}, { 59, 33, 32, 98,102, 44, 45, 31}, { 0, 73, 77,156,158, 95, 91, 34}, { 13, 68, 64,145,147, 82, 86, 47}, { 72, 20, 22,186,187, 63, 61, 65}, { 69, 25, 27,183,182, 50, 48, 76}, { 83, 63, 61,169,168, 20, 22, 90}, { 94, 50, 48,164,165, 25, 27, 87}}; static constexpr const uint16_t m2p3D_2[24][64]={ { 0, 577, 263, 710,1219, 578,1220, 709, 574, 63, 697, 312, 573,1020, 698,1019, 136,1099, 9, 10, 399,1100, 78, 77, 1076, 503, 53, 54,1075, 240, 114, 113, 1050,1117, 27, 28,1049,1118, 984,1247, 1058,1125, 35, 36,1057,1126, 992,1255, 144,1107, 17, 18, 407,1108, 86, 85, 1068, 495, 45, 46,1067, 232, 106, 105}, {1062,1121,1191, 928,1061,1122, 100, 99, 1054,1113,1183, 920,1053,1114, 92, 91, 168,1131, 41, 42, 431,1132, 110, 109, 1044, 471, 21, 22,1043, 208, 82, 81, 956, 637, 955, 762, 127, 638, 376, 761, 514,1155, 645,1156, 513, 64, 646, 327, 176,1139, 49, 50, 439,1140, 118, 117, 1036, 463, 13, 14,1035, 200, 74, 73}, { 128,1091, 1, 2, 391,1092, 70, 69, 1370,1369,1501,1502, 155, 856, 156,1119, 318, 317, 191, 892, 377, 378, 440, 891, 1378,1377,1509,1510, 163, 864, 164,1127, 584, 527,1483,1484, 137, 462, 138, 461, 592, 535,1491,1492, 145, 470, 146, 469, 1396,1395, 759, 688, 181, 498, 182, 497, 1388,1387, 751, 680, 173, 490, 174, 489}, { 406, 209, 405, 210, 599, 528,1428,1427, 398, 201, 397, 202, 591, 520,1420,1419, 426, 237, 425, 238,1323,1324, 744, 687, 434, 245, 433, 246,1331,1332, 752, 695, 792, 219,1055, 220,1305,1306,1438,1437, 1028, 455, 5, 6,1027, 192, 66, 65, 800, 227,1063, 228,1313,1314,1446,1445, 314, 313, 827, 504, 381, 382, 828, 255}, { 310, 309, 183, 884, 369, 370, 432, 883, 266, 265, 779, 456, 333, 334, 780, 207, 56, 633, 319, 766,1275, 634,1276, 765, 518, 7, 641, 256, 517, 964, 642, 963, 302, 301, 175, 876, 361, 362, 424, 875, 274, 273, 787, 464, 341, 342, 788, 215, 292, 291, 805, 866, 999,1248, 806, 865, 284, 283, 797, 858, 991,1240, 798, 857}, { 278, 277, 151, 852, 337, 338, 400, 851, 298, 297, 811, 488, 365, 366, 812, 239, 1176, 927, 793, 862, 347, 348, 794, 861, 1184, 935, 801, 870, 355, 356, 802, 869, 270, 269, 143, 844, 329, 330, 392, 843, 306, 305, 819, 496, 373, 374, 820, 247, 900, 581, 899, 706, 71, 582, 320, 705, 570,1211, 701,1212, 569, 120, 702, 383}, { 438, 241, 437, 242, 631, 560,1460,1459, 430, 233, 429, 234, 623, 552,1452,1451, 394, 205, 393, 206,1291,1292, 712, 655, 402, 213, 401, 214,1299,1300, 720, 663, 184,1147, 57, 58, 447,1148, 126, 125, 420, 871, 419,1120,1317,1318,1442,1441, 262, 261, 135, 836, 321, 322, 384, 835, 412, 863, 411,1112,1309,1310,1434,1433}, {1382,1381,1505,1506, 807, 484,1056, 483, 1084, 511, 61, 62,1083, 248, 122, 121, 1374,1373,1497,1498, 799, 476,1048, 475, 258, 257, 771, 448, 325, 326, 772, 199, 616, 559,1515,1516, 169, 494, 170, 493, 624, 567,1523,1524, 177, 502, 178, 501, 1364,1363, 727, 656, 149, 466, 150, 465, 1356,1355, 719, 648, 141, 458, 142, 457}, { 566, 55, 689, 304, 565,1012, 690,1011, 632, 575,1531,1532, 185, 510, 186, 509, 558, 47, 681, 296, 557,1004, 682,1003, 548,1189,1447,1190, 547, 994,1504, 993, 522,1163, 653,1164, 521, 72, 654, 335, 390, 193, 389, 194, 583, 512,1412,1411, 530,1171, 661,1172, 529, 80, 662, 343, 540,1181,1439,1182, 539, 986,1496, 985}, { 576, 519,1475,1476, 129, 454, 130, 453, 8, 585, 271, 718,1227, 586,1228, 717, 922, 603, 921,1432,1245, 604,1246,1503, 16, 593, 279, 726,1235, 594,1236, 725, 446, 249, 445, 250, 639, 568,1468,1467, 948, 629, 947, 754, 119, 630, 368, 753, 930, 611, 929,1440,1253, 612,1254,1511, 940, 621, 939, 746, 111, 622, 360, 745}, { 534, 23, 657, 272, 533, 980, 658, 979, 1304,1177, 667,1178,1375, 990, 668, 989, 526, 15, 649, 264, 525, 972, 650, 971, 1348,1347, 711, 640, 133, 450, 134, 449, 554,1195, 685,1196, 553, 104, 686, 367, 1312,1185, 675,1186,1383, 998, 676, 997, 562,1203, 693,1204, 561, 112, 694, 375, 442, 253, 441, 254,1339,1340, 760, 703}, { 934,1319, 933, 740,1249,1376,1250, 739, 40, 617, 303, 750,1259, 618,1260, 749, 1404,1403, 767, 696, 189, 506, 190, 505, 48, 625, 311, 758,1267, 626,1268, 757, 926,1311, 925, 732,1241,1368,1242, 731, 916, 597, 915, 722, 87, 598, 336, 721, 386, 197, 385, 198,1283,1284, 704, 647, 908, 589, 907, 714, 79, 590, 328, 713}, { 768, 195,1031, 196,1281,1282,1414,1413, 282, 281, 795, 472, 349, 350, 796, 223, 1160, 911, 777, 846, 331, 332, 778, 845, 1168, 919, 785, 854, 339, 340, 786, 853, 1406,1405,1529,1530, 831, 508,1080, 507, 290, 289, 803, 480, 357, 358, 804, 231, 308, 307, 821, 882,1015,1264, 822, 881, 300, 299, 813, 874,1007,1256, 814, 873}, { 294, 293, 167, 868, 353, 354, 416, 867, 444, 895, 443,1144,1341,1342,1466,1465, 1192, 943, 809, 878, 363, 364, 810, 877, 1200, 951, 817, 886, 371, 372, 818, 885, 286, 285, 159, 860, 345, 346, 408, 859, 1346,1345,1477,1478, 131, 832, 132,1095, 276, 275, 789, 850, 983,1232, 790, 849, 268, 267, 781, 842, 975,1224, 782, 841}, { 950,1335, 949, 756,1265,1392,1266, 755, 1208, 959, 825, 894, 379, 380, 826, 893, 906, 587, 905,1416,1229, 588,1230,1487, 1030,1089,1159, 896,1029,1090, 68, 67, 942,1327, 941, 748,1257,1384,1258, 747, 932, 613, 931, 738, 103, 614, 352, 737, 914, 595, 913,1424,1237, 596,1238,1495, 924, 605, 923, 730, 95, 606, 344, 729}, { 550, 39, 673, 288, 549, 996, 674, 995, 1320,1193, 683,1194,1391,1006, 684,1005, 542, 31, 665, 280, 541, 988, 666, 987, 532,1173,1431,1174, 531, 978,1488, 977, 316, 315, 829, 890,1023,1272, 830, 889, 1328,1201, 691,1202,1399,1014, 692,1013, 1026,1093, 3, 4,1025,1094, 960,1223, 524,1165,1423,1166, 523, 970,1480, 969}, {1078,1137,1207, 944,1077,1138, 116, 115, 1070,1129,1199, 936,1069,1130, 108, 107, 824, 251,1087, 252,1337,1338,1470,1469, 1060, 487, 37, 38,1059, 224, 98, 97, 1034,1101, 11, 12,1033,1102, 968,1231, 1042,1109, 19, 20,1041,1110, 976,1239, 1350,1349,1473,1474, 775, 452,1024, 451, 1052, 479, 29, 30,1051, 216, 90, 89}, {1046,1105,1175, 912,1045,1106, 84, 83, 1038,1097,1167, 904,1037,1098, 76, 75, 152,1115, 25, 26, 415,1116, 94, 93, 388, 839, 387,1088,1285,1286,1410,1409, 1066,1133, 43, 44,1065,1134,1000,1263, 1074,1141, 51, 52,1073,1142,1008,1271, 160,1123, 33, 34, 423,1124, 102, 101, 1402,1401,1533,1534, 187, 888, 188,1151}, {1152, 903, 769, 838, 323, 324, 770, 837, 1288,1161, 651,1162,1359, 974, 652, 973, 1086,1145,1215, 952,1085,1146, 124, 123, 564,1205,1463,1206, 563,1010,1520,1009, 538,1179, 669,1180, 537, 88, 670, 351, 1296,1169, 659,1170,1367, 982, 660, 981, 546,1187, 677,1188, 545, 96, 678, 359, 556,1197,1455,1198, 555,1002,1512,1001}, { 918,1303, 917, 724,1233,1360,1234, 723, 24, 601, 287, 734,1243, 602,1244, 733, 938, 619, 937,1448,1261, 620,1262,1519, 32, 609, 295, 742,1251, 610,1252, 741, 910,1295, 909, 716,1225,1352,1226, 715, 260, 259, 773, 834, 967,1216, 774, 833, 946, 627, 945,1456,1269, 628,1270,1527, 1082,1149, 59, 60,1081,1150,1016,1279}, {1280,1153, 643,1154,1351, 966, 644, 965, 958,1343, 957, 764,1273,1400,1274, 763, 410, 221, 409, 222,1307,1308, 728, 671, 418, 229, 417, 230,1315,1316, 736, 679, 776, 203,1039, 204,1289,1290,1422,1421, 436, 887, 435,1136,1333,1334,1458,1457, 784, 211,1047, 212,1297,1298,1430,1429, 428, 879, 427,1128,1325,1326,1450,1449}, {1398,1397,1521,1522, 823, 500,1072, 499, 1354,1353,1485,1486, 139, 840, 140,1103, 1390,1389,1513,1514, 815, 492,1064, 491, 1362,1361,1493,1494, 147, 848, 148,1111, 1336,1209, 699,1210,1407,1022, 700,1021, 902,1287, 901, 708,1217,1344,1218, 707, 1380,1379, 743, 672, 165, 482, 166, 481, 1372,1371, 735, 664, 157, 474, 158, 473}, { 422, 225, 421, 226, 615, 544,1444,1443, 414, 217, 413, 218, 607, 536,1436,1435, 572,1213,1471,1214, 571,1018,1528,1017, 898, 579, 897,1408,1221, 580,1222,1479, 808, 235,1071, 236,1321,1322,1454,1453, 404, 855, 403,1104,1301,1302,1426,1425, 816, 243,1079, 244,1329,1330,1462,1461, 396, 847, 395,1096,1293,1294,1418,1417}, {1366,1365,1489,1490, 791, 468,1040, 467, 1386,1385,1517,1518, 171, 872, 172,1135, 1358,1357,1481,1482, 783, 460,1032, 459, 1394,1393,1525,1526, 179, 880, 180,1143, 600, 543,1499,1500, 153, 478, 154, 477, 608, 551,1507,1508, 161, 486, 162, 485, 516,1157,1415,1158, 515, 962,1472, 961, 954, 635, 953,1464,1277, 636,1278,1535} }; static constexpr const uint16_t p2m3D_2[24][64]={ { 0, 577, 581,1220,1222, 711, 707, 258, 144, 18, 19,1105,1109, 87, 86, 404, 176, 50, 51,1137,1141, 119, 118, 436, 998,1060,1056, 34, 35,1121,1125,1255, 1006,1068,1064, 42, 43,1129,1133,1263, 253, 127, 126,1084,1080, 58, 59, 505, 221, 95, 94,1052,1048, 26, 27, 473, 267, 650, 654, 975, 973, 524, 520, 9}, { 109, 556, 552,1193,1195, 682, 686, 367, 253, 127, 126,1084,1080, 58, 59, 505, 221, 95, 94,1052,1048, 26, 27, 473, 907,1097,1101, 79, 78,1036,1032,1162, 899,1089,1093, 71, 70,1028,1024,1154, 144, 18, 19,1105,1109, 87, 86, 404, 176, 50, 51,1137,1141, 119, 118, 436, 358, 743, 739, 930, 928, 609, 613, 100}, { 128, 2, 3,1089,1093, 71, 70, 388, 608, 164, 166,1506,1507, 487, 485, 545, 616, 172, 174,1514,1515, 495, 493, 553, 845,1353,1352, 140, 142,1482,1483,1103, 861,1369,1368, 156, 158,1498,1499,1119, 699, 511, 509,1401,1400, 188, 190, 762, 691, 503, 501,1393,1392, 180, 182, 754, 406, 340, 341, 855, 851, 273, 272, 146}, { 237, 111, 110,1068,1064, 42, 43, 489, 525, 201, 203,1423,1422, 394, 392, 588, 517, 193, 195,1415,1414, 386, 384, 580, 800,1316,1317, 225, 227,1447,1446,1058, 816,1332,1333, 241, 243,1463,1462,1074, 726, 402, 400,1300,1301, 209, 211, 663, 734, 410, 408,1308,1309, 217, 219, 671, 507, 313, 312, 826, 830, 380, 381, 255}, { 283, 666, 670, 991, 989, 540, 536, 25, 459, 265, 264, 778, 782, 332, 333, 207, 491, 297, 296, 810, 814, 364, 365, 239, 1277, 895, 891, 313, 312, 826, 830,1020, 1269, 887, 883, 305, 304, 818, 822,1012, 422, 356, 357, 871, 867, 289, 288, 162, 390, 324, 325, 839, 835, 257, 256, 130, 16, 593, 597,1236,1238, 727, 723, 274}, { 374, 759, 755, 946, 944, 625, 629, 116, 422, 356, 357, 871, 867, 289, 288, 162, 390, 324, 325, 839, 835, 257, 256, 130, 1168, 786, 790, 340, 341, 855, 851, 913, 1176, 794, 798, 348, 349, 863, 859, 921, 459, 265, 264, 778, 782, 332, 333, 207, 491, 297, 296, 810, 814, 364, 365, 239, 125, 572, 568,1209,1211, 698, 702, 383}, { 438, 372, 373, 887, 883, 305, 304, 178, 726, 402, 400,1300,1301, 209, 211, 663, 734, 410, 408,1308,1309, 217, 219, 671, 1147,1471,1470, 442, 440,1340,1341, 889, 1131,1455,1454, 426, 424,1324,1325, 873, 525, 201, 203,1423,1422, 394, 392, 588, 517, 193, 195,1415,1414, 386, 384, 580, 160, 34, 35,1121,1125, 103, 102, 420}, { 475, 281, 280, 794, 798, 348, 349, 223, 699, 511, 509,1401,1400, 188, 190, 762, 691, 503, 501,1393,1392, 180, 182, 754, 1046,1490,1491, 471, 469,1361,1360, 788, 1030,1474,1475, 455, 453,1345,1344, 772, 608, 164, 166,1506,1507, 487, 485, 545, 616, 172, 174,1514,1515, 495, 493, 553, 205, 79, 78,1036,1032, 10, 11, 457}, { 557, 233, 235,1455,1454, 426, 424, 620, 101, 548, 544,1185,1187, 674, 678, 359, 117, 564, 560,1201,1203, 690, 694, 375, 1534,1023,1021, 572, 568,1209,1211,1466, 1502, 991, 989, 540, 536,1177,1179,1434, 275, 658, 662, 983, 981, 532, 528, 17, 259, 642, 646, 967, 965, 516, 512, 1, 584, 140, 142,1482,1483, 463, 461, 521}, { 576, 132, 134,1474,1475, 455, 453, 513, 8, 585, 589,1228,1230, 719, 715, 266, 24, 601, 605,1244,1246, 735, 731, 282, 1427, 914, 912, 593, 597,1236,1238,1495, 1459, 946, 944, 625, 629,1268,1270,1527, 382, 767, 763, 954, 952, 633, 637, 124, 366, 751, 747, 938, 936, 617, 621, 108, 549, 225, 227,1447,1446, 418, 416, 612}, { 667, 479, 477,1369,1368, 156, 158, 730, 275, 658, 662, 983, 981, 532, 528, 17, 259, 642, 646, 967, 965, 516, 512, 1, 1288,1161,1163, 650, 654, 975, 973,1356, 1320,1193,1195, 682, 686,1007,1005,1388, 101, 548, 544,1185,1187, 674, 678, 359, 117, 564, 560,1201,1203, 690, 694, 375, 766, 442, 440,1340,1341, 249, 251, 703}, { 758, 434, 432,1332,1333, 241, 243, 695, 382, 767, 763, 954, 952, 633, 637, 124, 366, 751, 747, 938, 936, 617, 621, 108, 1381,1252,1254, 743, 739, 930, 928,1313, 1349,1220,1222, 711, 707, 898, 896,1281, 8, 585, 589,1228,1230, 719, 715, 266, 24, 601, 605,1244,1246, 735, 731, 282, 659, 471, 469,1361,1360, 148, 150, 722}, { 768,1284,1285, 193, 195,1415,1414,1026, 1168, 786, 790, 340, 341, 855, 851, 913, 1176, 794, 798, 348, 349, 863, 859, 921, 459, 265, 264, 778, 782, 332, 333, 207, 491, 297, 296, 810, 814, 364, 365, 239, 1277, 895, 891, 313, 312, 826, 830,1020, 1269, 887, 883, 305, 304, 818, 822,1012, 1062,1506,1507, 487, 485,1377,1376, 804}, { 877,1385,1384, 172, 174,1514,1515,1135, 1277, 895, 891, 313, 312, 826, 830,1020, 1269, 887, 883, 305, 304, 818, 822,1012, 422, 356, 357, 871, 867, 289, 288, 162, 390, 324, 325, 839, 835, 257, 256, 130, 1168, 786, 790, 340, 341, 855, 851, 913, 1176, 794, 798, 348, 349, 863, 859, 921, 1099,1423,1422, 394, 392,1292,1293, 841}, { 923,1113,1117, 95, 94,1052,1048,1178, 1427, 914, 912, 593, 597,1236,1238,1495, 1459, 946, 944, 625, 629,1268,1270,1527, 382, 767, 763, 954, 952, 633, 637, 124, 366, 751, 747, 938, 936, 617, 621, 108, 1381,1252,1254, 743, 739, 930, 928,1313, 1349,1220,1222, 711, 707, 898, 896,1281, 1160, 778, 782, 332, 333, 847, 843, 905}, {1014,1076,1072, 50, 51,1137,1141,1271, 1534,1023,1021, 572, 568,1209,1211,1466, 1502, 991, 989, 540, 536,1177,1179,1434, 275, 658, 662, 983, 981, 532, 528, 17, 259, 642, 646, 967, 965, 516, 512, 1, 1288,1161,1163, 650, 654, 975, 973,1356, 1320,1193,1195, 682, 686,1007,1005,1388, 1253, 871, 867, 289, 288, 802, 806, 996}, {1078,1522,1523, 503, 501,1393,1392, 820, 998,1060,1056, 34, 35,1121,1125,1255, 1006,1068,1064, 42, 43,1129,1133,1263, 253, 127, 126,1084,1080, 58, 59, 505, 221, 95, 94,1052,1048, 26, 27, 473, 907,1097,1101, 79, 78,1036,1032,1162, 899,1089,1093, 71, 70,1028,1024,1154, 784,1300,1301, 209, 211,1431,1430,1042}, {1115,1439,1438, 410, 408,1308,1309, 857, 907,1097,1101, 79, 78,1036,1032,1162, 899,1089,1093, 71, 70,1028,1024,1154, 144, 18, 19,1105,1109, 87, 86, 404, 176, 50, 51,1137,1141, 119, 118, 436, 998,1060,1056, 34, 35,1121,1125,1255, 1006,1068,1064, 42, 43,1129,1133,1263, 893,1401,1400, 188, 190,1530,1531,1151}, {1152, 770, 774, 324, 325, 839, 835, 897, 1288,1161,1163, 650, 654, 975, 973,1356, 1320,1193,1195, 682, 686,1007,1005,1388, 101, 548, 544,1185,1187, 674, 678, 359, 117, 564, 560,1201,1203, 690, 694, 375, 1534,1023,1021, 572, 568,1209,1211,1466, 1502, 991, 989, 540, 536,1177,1179,1434, 915,1105,1109, 87, 86,1044,1040,1170}, {1261, 879, 875, 297, 296, 810, 814,1004, 1381,1252,1254, 743, 739, 930, 928,1313, 1349,1220,1222, 711, 707, 898, 896,1281, 8, 585, 589,1228,1230, 719, 715, 266, 24, 601, 605,1244,1246, 735, 731, 282, 1427, 914, 912, 593, 597,1236,1238,1495, 1459, 946, 944, 625, 629,1268,1270,1527, 1022,1084,1080, 58, 59,1145,1149,1279}, {1280,1153,1155, 642, 646, 967, 965,1348, 800,1316,1317, 225, 227,1447,1446,1058, 816,1332,1333, 241, 243,1463,1462,1074, 726, 402, 400,1300,1301, 209, 211, 663, 734, 410, 408,1308,1309, 217, 219, 671, 1147,1471,1470, 442, 440,1340,1341, 889, 1131,1455,1454, 426, 424,1324,1325, 873, 1357,1228,1230, 719, 715, 906, 904,1289}, {1389,1260,1262, 751, 747, 938, 936,1321, 845,1353,1352, 140, 142,1482,1483,1103, 861,1369,1368, 156, 158,1498,1499,1119, 699, 511, 509,1401,1400, 188, 190, 762, 691, 503, 501,1393,1392, 180, 182, 754, 1046,1490,1491, 471, 469,1361,1360, 788, 1030,1474,1475, 455, 453,1345,1344, 772, 1312,1185,1187, 674, 678, 999, 997,1380}, {1435, 922, 920, 601, 605,1244,1246,1503, 1147,1471,1470, 442, 440,1340,1341, 889, 1131,1455,1454, 426, 424,1324,1325, 873, 525, 201, 203,1423,1422, 394, 392, 588, 517, 193, 195,1415,1414, 386, 384, 580, 800,1316,1317, 225, 227,1447,1446,1058, 816,1332,1333, 241, 243,1463,1462,1074, 1494, 983, 981, 532, 528,1169,1171,1426}, {1526,1015,1013, 564, 560,1201,1203,1458, 1046,1490,1491, 471, 469,1361,1360, 788, 1030,1474,1475, 455, 453,1345,1344, 772, 608, 164, 166,1506,1507, 487, 485, 545, 616, 172, 174,1514,1515, 495, 493, 553, 845,1353,1352, 140, 142,1482,1483,1103, 861,1369,1368, 156, 158,1498,1499,1119, 1467, 954, 952, 633, 637,1276,1278,1535} }; template inline T morton2peano2D_sub(unsigned rot, T res, T v) { constexpr unsigned nbits = 8*sizeof(T); static_assert(2*rbits<=nbits, "too many significant bits"); // if constexpr (rbits==0) return res; if constexpr (rbits==1) return (res<<2)|(m2p2D_1[rot][v>>(nbits-2)]&0x3); if constexpr (rbits==2) { unsigned tab=m2p2D_1[rot][v>>(nbits-2)]; return morton2peano2D_sub(tab>>2, (res<<2)|(tab&0x3), v<<2); } if constexpr (rbits==3) return (res<<6)|(m2p2D_3[rot][v>>(nbits-6)]&0x3fu); if constexpr (rbits>3) { unsigned tab=m2p2D_3[rot][v>>(nbits-6)]; return morton2peano2D_sub(tab>>6, (res<<6)|(tab&0x3fu), v<<6); } } template inline T peano2morton2D_sub(unsigned rot, T res, T v) { constexpr unsigned nbits = 8*sizeof(T); static_assert(2*rbits<=nbits, "too many significant bits"); // if constexpr (rbits==0) return res; if constexpr (rbits==1) return (res<<2)|(p2m2D_1[rot][v>>(nbits-2)]&0x3); if constexpr (rbits==2) { unsigned tab=p2m2D_1[rot][v>>(nbits-2)]; return peano2morton2D_sub(tab>>2, (res<<2)|(tab&0x3), v<<2); } if constexpr (rbits==3) return (res<<6)|(p2m2D_3[rot][v>>(nbits-6)]&0x3fu); if constexpr (rbits>3) { unsigned tab=p2m2D_3[rot][v>>(nbits-6)]; return peano2morton2D_sub(tab>>6, (res<<6)|(tab&0x3fu), v<<6); } } template inline T morton2peano3D_sub(unsigned rot, T res, T v) { constexpr unsigned nbits = 8*sizeof(T); static_assert(3*rbits<=nbits, "too many significant bits"); // if constexpr (rbits==0) return res; if constexpr (rbits==1) return (res<<3)|(m2p3D_1[rot][v>>(nbits-3)]&0x7); if constexpr (rbits==2) return (res<<6)|(m2p3D_2[rot][v>>(nbits-6)]&0x3fu); if constexpr (rbits>2) { unsigned tab=m2p3D_2[rot][v>>(nbits-6)]; return morton2peano3D_sub(tab>>6, (res<<6)|(tab&0x3fu), v<<6); } } template inline T peano2morton3D_sub(unsigned rot, T res, T v) { constexpr unsigned nbits = 8*sizeof(T); static_assert(3*rbits<=nbits, "too many significant bits"); // if constexpr (rbits==0) return res; if constexpr (rbits==1) return (res<<3)|(p2m3D_1[rot][v>>(nbits-3)]&0x7); if constexpr (rbits==2) return (res<<6)|(p2m3D_2[rot][v>>(nbits-6)]&0x3fu); if constexpr (rbits>2) { unsigned tab=p2m3D_2[rot][v>>(nbits-6)]; return peano2morton3D_sub(tab>>6, (res<<6)|(tab&0x3fu), v<<6); } } template uint64_t tmorton2peano2D_64(uint64_t v) { return morton2peano2D_sub(0, 0, v<<(64-(bits<<1))); } template uint64_t tpeano2morton2D_64(uint64_t v) { return peano2morton2D_sub(0, 0, v<<(64-(bits<<1))); } template uint32_t tmorton2peano2D_32(uint32_t v) { return morton2peano2D_sub(0, 0, v<<(32-(bits<<1))); } template uint32_t tpeano2morton2D_32(uint32_t v) { return peano2morton2D_sub(0, 0, v<<(32-(bits<<1))); } template uint64_t tmorton2peano3D_64(uint64_t v) { return morton2peano3D_sub(0, 0, v<<(3*(21-bits)+1)); } template uint64_t tpeano2morton3D_64(uint64_t v) { return peano2morton3D_sub(0, 0, v<<(3*(21-bits)+1)); } template uint32_t tmorton2peano3D_32(uint32_t v) { return morton2peano3D_sub(0, 0, v<<(3*(10-bits)+2)); } template uint32_t tpeano2morton3D_32(uint32_t v) { return peano2morton3D_sub(0, 0, v<<(3*(10-bits)+2)); } } // unnamed namespace uint32_t morton2peano3D_32(uint32_t v, unsigned bits) { switch(bits) { case 1: return tmorton2peano3D_32< 1>(v); case 2: return tmorton2peano3D_32< 2>(v); case 3: return tmorton2peano3D_32< 3>(v); case 4: return tmorton2peano3D_32< 4>(v); case 5: return tmorton2peano3D_32< 5>(v); case 6: return tmorton2peano3D_32< 6>(v); case 7: return tmorton2peano3D_32< 7>(v); case 8: return tmorton2peano3D_32< 8>(v); case 9: return tmorton2peano3D_32< 9>(v); case 10: return tmorton2peano3D_32<10>(v); default: MR_fail("bad number of requested bits"); } } uint32_t peano2morton3D_32(uint32_t v, unsigned bits) { switch(bits) { case 1: return tpeano2morton3D_32< 1>(v); case 2: return tpeano2morton3D_32< 2>(v); case 3: return tpeano2morton3D_32< 3>(v); case 4: return tpeano2morton3D_32< 4>(v); case 5: return tpeano2morton3D_32< 5>(v); case 6: return tpeano2morton3D_32< 6>(v); case 7: return tpeano2morton3D_32< 7>(v); case 8: return tpeano2morton3D_32< 8>(v); case 9: return tpeano2morton3D_32< 9>(v); case 10: return tpeano2morton3D_32<10>(v); default: MR_fail("bad number of requested bits"); } } uint64_t morton2peano3D_64(uint64_t v, unsigned bits) { switch(bits) { case 1: return tmorton2peano3D_64< 1>(v); case 2: return tmorton2peano3D_64< 2>(v); case 3: return tmorton2peano3D_64< 3>(v); case 4: return tmorton2peano3D_64< 4>(v); case 5: return tmorton2peano3D_64< 5>(v); case 6: return tmorton2peano3D_64< 6>(v); case 7: return tmorton2peano3D_64< 7>(v); case 8: return tmorton2peano3D_64< 8>(v); case 9: return tmorton2peano3D_64< 9>(v); case 10: return tmorton2peano3D_64<10>(v); case 11: return tmorton2peano3D_64<11>(v); case 12: return tmorton2peano3D_64<12>(v); case 13: return tmorton2peano3D_64<13>(v); case 14: return tmorton2peano3D_64<14>(v); case 15: return tmorton2peano3D_64<15>(v); case 16: return tmorton2peano3D_64<16>(v); case 17: return tmorton2peano3D_64<17>(v); case 18: return tmorton2peano3D_64<18>(v); case 19: return tmorton2peano3D_64<19>(v); case 20: return tmorton2peano3D_64<20>(v); case 21: return tmorton2peano3D_64<21>(v); default: MR_fail("bad number of requested bits"); } } uint64_t peano2morton3D_64(uint64_t v, unsigned bits) { switch(bits) { case 1: return tpeano2morton3D_64< 1>(v); case 2: return tpeano2morton3D_64< 2>(v); case 3: return tpeano2morton3D_64< 3>(v); case 4: return tpeano2morton3D_64< 4>(v); case 5: return tpeano2morton3D_64< 5>(v); case 6: return tpeano2morton3D_64< 6>(v); case 7: return tpeano2morton3D_64< 7>(v); case 8: return tpeano2morton3D_64< 8>(v); case 9: return tpeano2morton3D_64< 9>(v); case 10: return tpeano2morton3D_64<10>(v); case 11: return tpeano2morton3D_64<11>(v); case 12: return tpeano2morton3D_64<12>(v); case 13: return tpeano2morton3D_64<13>(v); case 14: return tpeano2morton3D_64<14>(v); case 15: return tpeano2morton3D_64<15>(v); case 16: return tpeano2morton3D_64<16>(v); case 17: return tpeano2morton3D_64<17>(v); case 18: return tpeano2morton3D_64<18>(v); case 19: return tpeano2morton3D_64<19>(v); case 20: return tpeano2morton3D_64<20>(v); case 21: return tpeano2morton3D_64<21>(v); default: MR_fail("bad number of requested bits"); } } uint32_t morton2peano2D_32(uint32_t v, unsigned bits) { switch(bits) { case 1: return tmorton2peano2D_32< 1>(v); case 2: return tmorton2peano2D_32< 2>(v); case 3: return tmorton2peano2D_32< 3>(v); case 4: return tmorton2peano2D_32< 4>(v); case 5: return tmorton2peano2D_32< 5>(v); case 6: return tmorton2peano2D_32< 6>(v); case 7: return tmorton2peano2D_32< 7>(v); case 8: return tmorton2peano2D_32< 8>(v); case 9: return tmorton2peano2D_32< 9>(v); case 10: return tmorton2peano2D_32<10>(v); case 11: return tmorton2peano2D_32<11>(v); case 12: return tmorton2peano2D_32<12>(v); case 13: return tmorton2peano2D_32<13>(v); case 14: return tmorton2peano2D_32<14>(v); case 15: return tmorton2peano2D_32<15>(v); case 16: return tmorton2peano2D_32<16>(v); default: MR_fail("bad number of requested bits"); } } uint32_t peano2morton2D_32(uint32_t v, unsigned bits) { switch(bits) { case 1: return tpeano2morton2D_32< 1>(v); case 2: return tpeano2morton2D_32< 2>(v); case 3: return tpeano2morton2D_32< 3>(v); case 4: return tpeano2morton2D_32< 4>(v); case 5: return tpeano2morton2D_32< 5>(v); case 6: return tpeano2morton2D_32< 6>(v); case 7: return tpeano2morton2D_32< 7>(v); case 8: return tpeano2morton2D_32< 8>(v); case 9: return tpeano2morton2D_32< 9>(v); case 10: return tpeano2morton2D_32<10>(v); case 11: return tpeano2morton2D_32<11>(v); case 12: return tpeano2morton2D_32<12>(v); case 13: return tpeano2morton2D_32<13>(v); case 14: return tpeano2morton2D_32<14>(v); case 15: return tpeano2morton2D_32<15>(v); case 16: return tpeano2morton2D_32<16>(v); default: MR_fail("bad number of requested bits"); } } uint64_t morton2peano2D_64(uint64_t v, unsigned bits) { switch(bits) { case 1: return tmorton2peano2D_64< 1>(v); case 2: return tmorton2peano2D_64< 2>(v); case 3: return tmorton2peano2D_64< 3>(v); case 4: return tmorton2peano2D_64< 4>(v); case 5: return tmorton2peano2D_64< 5>(v); case 6: return tmorton2peano2D_64< 6>(v); case 7: return tmorton2peano2D_64< 7>(v); case 8: return tmorton2peano2D_64< 8>(v); case 9: return tmorton2peano2D_64< 9>(v); case 10: return tmorton2peano2D_64<10>(v); case 11: return tmorton2peano2D_64<11>(v); case 12: return tmorton2peano2D_64<12>(v); case 13: return tmorton2peano2D_64<13>(v); case 14: return tmorton2peano2D_64<14>(v); case 15: return tmorton2peano2D_64<15>(v); case 16: return tmorton2peano2D_64<16>(v); case 17: return tmorton2peano2D_64<17>(v); case 18: return tmorton2peano2D_64<18>(v); case 19: return tmorton2peano2D_64<19>(v); case 20: return tmorton2peano2D_64<20>(v); case 21: return tmorton2peano2D_64<21>(v); case 22: return tmorton2peano2D_64<22>(v); case 23: return tmorton2peano2D_64<23>(v); case 24: return tmorton2peano2D_64<24>(v); case 25: return tmorton2peano2D_64<25>(v); case 26: return tmorton2peano2D_64<26>(v); case 27: return tmorton2peano2D_64<27>(v); case 28: return tmorton2peano2D_64<28>(v); case 29: return tmorton2peano2D_64<29>(v); case 30: return tmorton2peano2D_64<30>(v); case 31: return tmorton2peano2D_64<31>(v); case 32: return tmorton2peano2D_64<32>(v); default: MR_fail("bad number of requested bits"); } } uint64_t peano2morton2D_64(uint64_t v, unsigned bits) { switch(bits) { case 1: return tpeano2morton2D_64< 1>(v); case 2: return tpeano2morton2D_64< 2>(v); case 3: return tpeano2morton2D_64< 3>(v); case 4: return tpeano2morton2D_64< 4>(v); case 5: return tpeano2morton2D_64< 5>(v); case 6: return tpeano2morton2D_64< 6>(v); case 7: return tpeano2morton2D_64< 7>(v); case 8: return tpeano2morton2D_64< 8>(v); case 9: return tpeano2morton2D_64< 9>(v); case 10: return tpeano2morton2D_64<10>(v); case 11: return tpeano2morton2D_64<11>(v); case 12: return tpeano2morton2D_64<12>(v); case 13: return tpeano2morton2D_64<13>(v); case 14: return tpeano2morton2D_64<14>(v); case 15: return tpeano2morton2D_64<15>(v); case 16: return tpeano2morton2D_64<16>(v); case 17: return tpeano2morton2D_64<17>(v); case 18: return tpeano2morton2D_64<18>(v); case 19: return tpeano2morton2D_64<19>(v); case 20: return tpeano2morton2D_64<20>(v); case 21: return tpeano2morton2D_64<21>(v); case 22: return tpeano2morton2D_64<22>(v); case 23: return tpeano2morton2D_64<23>(v); case 24: return tpeano2morton2D_64<24>(v); case 25: return tpeano2morton2D_64<25>(v); case 26: return tpeano2morton2D_64<26>(v); case 27: return tpeano2morton2D_64<27>(v); case 28: return tpeano2morton2D_64<28>(v); case 29: return tpeano2morton2D_64<29>(v); case 30: return tpeano2morton2D_64<30>(v); case 31: return tpeano2morton2D_64<31>(v); case 32: return tpeano2morton2D_64<32>(v); default: MR_fail("bad number of requested bits"); } } }