rsys

Basic data structures and low-level features
git clone git://git.meso-star.fr/rsys.git
Log | Files | Refs | README | LICENSE

test_morton.c (3478B)

      1 /* Copyright (C) 2013-2023, 2025 Vincent Forest (vaplv@free.fr)
      2  *
      3  * The RSys library is free software: you can redistribute it and/or modify
      4  * it under the terms of the GNU General Public License as published
      5  * by the Free Software Foundation, either version 3 of the License, or
      6  * (at your option) any later version.
      7  *
      8  * The RSys library is distributed in the hope that it will be useful,
      9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
     10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
     11  * GNU General Public License for more details.
     12  *
     13  * You should have received a copy of the GNU General Public License
     14  * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */
     15 
     16 #include "math.h"
     17 #include "morton.h"
     18 
     19 #include <stdlib.h>
     20 
     21 static INLINE uint16_t
     22 rand_u16()
     23 {
     24   return (uint16_t)(rand() & (BIT(16)-1));
     25 }
     26 
     27 static INLINE uint32_t
     28 rand_u21()
     29 {
     30   return (uint32_t)(rand() & (BIT(21)-1));
     31 }
     32 
     33 static INLINE uint64_t
     34 encode_u21(uint32_t u21)
     35 {
     36   uint64_t mcode = 0;
     37   uint64_t i;
     38   for(i = (uint64_t)round_up_pow2(u21); i != 0; i >>= 1) {
     39     if(i <= (uint64_t)u21) {
     40       mcode |= morton3D_encode_u21((uint32_t)i);
     41       u21 -= (uint32_t)i;
     42     }
     43   }
     44   return mcode;
     45 }
     46 
     47 static INLINE uint32_t
     48 encode_u16(uint32_t u16)
     49 {
     50   uint32_t mcode = 0;
     51   uint32_t i;
     52   for(i = (uint32_t)round_up_pow2(u16); i != 0; i >>= 1) {
     53     if(i <= (uint32_t)u16) {
     54       mcode |= morton2D_encode_u16((uint16_t)i);
     55       u16 -= (uint16_t)i;
     56     }
     57   }
     58   return mcode;
     59 }
     60 
     61 static void
     62 test_morton2D(void)
     63 {
     64   int bit = 0;
     65   int i = 0;
     66 
     67   FOR_EACH(bit, 0, 16) {
     68     CHK(morton2D_encode_u16(BIT_U16(bit)) == BIT_U32(2*bit));
     69     CHK(morton2D_decode_u16(BIT_U32(2*bit)) == BIT_U16(bit));
     70   }
     71 
     72   FOR_EACH(i, 0, 10000) {
     73     const uint16_t u16 = rand_u16();
     74     const uint32_t u32 = morton2D_encode_u16(u16);
     75     CHK(u32 == encode_u16(u16));
     76     CHK(u16 == morton2D_decode_u16(u32));
     77   }
     78 
     79   FOR_EACH(i, 0, 10000) {
     80     uint16_t xy[2];
     81     uint16_t xy2[2];
     82     uint32_t xy_mcode[2];
     83     uint32_t mcode;
     84 
     85     xy[0] = rand_u16();
     86     xy[1] = rand_u16();
     87     mcode = morton_xy_encode_u16(xy);
     88 
     89     xy_mcode[0] = morton2D_encode_u16(xy[0]);
     90     xy_mcode[1] = morton2D_encode_u16(xy[1]);
     91     CHK(mcode == ((xy_mcode[0]<<1) | (xy_mcode[1]<<0)));
     92 
     93     morton_xy_decode_u16(mcode, xy2);
     94     CHK(xy[0] == xy2[0]);
     95     CHK(xy[1] == xy2[1]);
     96   }
     97 
     98 }
     99 
    100 static void
    101 test_morton3D(void)
    102 {
    103   int bit = 0;
    104   int i = 0;
    105 
    106   FOR_EACH(bit, 0, 21) {
    107     CHK(morton3D_encode_u21(BIT_U32(bit)) == BIT_U64(3*bit));
    108     CHK(morton3D_decode_u21(BIT_U64(3*bit)) == BIT_U32(bit));
    109   }
    110 
    111   FOR_EACH(i, 0, 10000) {
    112     const uint32_t u21 = rand_u21();
    113     const uint64_t u64 = morton3D_encode_u21(u21);
    114     CHK(u64 == encode_u21(u21));
    115     CHK(u21 == morton3D_decode_u21(u64));
    116   }
    117 
    118   FOR_EACH(i, 0, 10000) {
    119     uint32_t xyz[3];
    120     uint32_t xyz2[3];
    121     uint64_t xyz_mcode[3];
    122     uint64_t mcode;
    123 
    124     xyz[0] = rand_u21();
    125     xyz[1] = rand_u21();
    126     xyz[2] = rand_u21();
    127     mcode = morton_xyz_encode_u21(xyz);
    128 
    129     xyz_mcode[0] = morton3D_encode_u21(xyz[0]);
    130     xyz_mcode[1] = morton3D_encode_u21(xyz[1]);
    131     xyz_mcode[2] = morton3D_encode_u21(xyz[2]);
    132     CHK(mcode == ((xyz_mcode[0]<<2) | (xyz_mcode[1]<<1) | (xyz_mcode[2]<<0)));
    133 
    134     morton_xyz_decode_u21(mcode, xyz2);
    135     CHK(xyz[0] == xyz2[0]);
    136     CHK(xyz[1] == xyz2[1]);
    137     CHK(xyz[2] == xyz2[2]);
    138   }
    139 }
    140 
    141 int
    142 main(int argc, char** argv)
    143 {
    144   (void)argc, (void)argv;
    145   test_morton2D();
    146   test_morton3D();
    147   return 0;
    148 }