rsys

commit 70219079ed1cdc9305f219b46257014fb63374e7
parent b97e5bba8c71261b6cb85479a0224b5b15161715
Author: vaplv <vaplv@free.fr>
Date:   Mon, 15 Feb 2021 12:28:10 +0100

Add and test the 2D morton encoding/decoding

Diffstat:
M
src/morton.h
 | 
39
+++++++++++++++++++++++++++++++++++++++
M
src/test_morton.c
 | 
85
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------

2 files changed, 114 insertions(+), 10 deletions(-)
diff --git a/src/morton.h b/src/morton.h
@@ -18,6 +18,28 @@
 
 #include "rsys.h"
 
+static FINLINE uint32_t
+morton2D_encode_u16(const uint16_t u16)
+{
+  uint32_t u32 = u16;
+  u32 = (u32 | (u32 << 8)) & 0x00FF00FF;
+  u32 = (u32 | (u32 << 4)) & 0X0F0F0F0F;
+  u32 = (u32 | (u32 << 2)) & 0x33333333;
+  u32 = (u32 | (u32 << 1)) & 0x55555555;
+  return u32;
+}
+
+static FINLINE uint16_t
+morton2D_decode_u16(const uint32_t u32)
+{
+  uint32_t x = u32 & 0x55555555;
+  x = (x | (x >> 1)) & 0x33333333;
+  x = (x | (x >> 2)) & 0x0F0F0F0F;
+  x = (x | (x >> 4)) & 0x00FF00FF;
+  x = (x | (x >> 8)) & 0x0000FFFF;
+  return (uint16_t)x;
+}
+
 static INLINE uint64_t
 morton3D_encode_u21(const uint32_t u21)
 {
@@ -44,9 +66,26 @@ morton3D_decode_u21(const uint64_t u64)
   return (uint32_t)tmp;
 }
 
+static INLINE uint32_t
+morton_xy_encode_u16(const uint16_t xy[2])
+{
+  ASSERT(xy);
+  return (morton2D_encode_u16(xy[0]) << 1)
+       | (morton2D_encode_u16(xy[1]) << 0);
+}
+
+static INLINE void
+morton_xy_decode_u16(const uint32_t code, uint16_t xy[2])
+{
+  ASSERT(xy);
+  xy[0] = (uint16_t)morton2D_decode_u16(code >> 1);
+  xy[1] = (uint16_t)morton2D_decode_u16(code >> 0);
+}
+
 static INLINE uint64_t
 morton_xyz_encode_u21(const uint32_t xyz[3])
 {
+  ASSERT(xyz);
   return (morton3D_encode_u21(xyz[0]) << 2)
        | (morton3D_encode_u21(xyz[1]) << 1)
        | (morton3D_encode_u21(xyz[2]) << 0);
diff --git a/src/test_morton.c b/src/test_morton.c
@@ -18,6 +18,12 @@
 
 #include <stdlib.h>
 
+static INLINE uint16_t
+rand_u16()
+{
+  return (uint16_t)(rand() & (BIT(16)-1));
+}
+
 static INLINE uint32_t
 rand_u21()
 {
@@ -28,22 +34,74 @@ static INLINE uint64_t
 encode_u21(uint32_t u21)
 {
   uint64_t mcode = 0;
+  uint64_t i;
+  for(i = (uint64_t)round_up_pow2(u21); i != 0; i >>= 1) {
+    if(i <= (uint64_t)u21) {
+      mcode |= morton3D_encode_u21((uint32_t)i);
+      u21 -= (uint32_t)i;
+    }
+  }
+  return mcode;
+}
+
+static INLINE uint32_t
+encode_u16(uint32_t u16)
+{
+  uint32_t mcode = 0;
   uint32_t i;
-  for(i = (uint32_t)round_up_pow2(u21); i != 0; i >>= 1) {
-    if(i <= u21) {
-      mcode |= morton3D_encode_u21(i);
-      u21 -= i;
+  for(i = (uint32_t)round_up_pow2(u16); i != 0; i >>= 1) {
+    if(i <= (uint32_t)u16) {
+      mcode |= morton2D_encode_u16((uint16_t)i);
+      u16 -= (uint16_t)i;
     }
   }
   return mcode;
 }
 
-int
-main(int argc, char** argv)
+static void
+test_morton2D(void)
+{
+  int bit = 0;
+  int i = 0;
+
+  FOR_EACH(bit, 0, 16) {
+    CHK(morton2D_encode_u16(BIT_U16(bit)) == BIT_U32(2*bit));
+    CHK(morton2D_decode_u16(BIT_U32(2*bit)) == BIT_U16(bit));
+  }
+
+  FOR_EACH(i, 0, 10000) {
+    const uint16_t u16 = rand_u16();
+    const uint32_t u32 = morton2D_encode_u16(u16);
+    CHK(u32 == encode_u16(u16));
+    CHK(u16 == morton2D_decode_u16(u32));
+  }
+
+  FOR_EACH(i, 0, 10000) {
+    uint16_t xy[2];
+    uint16_t xy2[2];
+    uint32_t xy_mcode[2];
+    uint32_t mcode;
+
+    xy[0] = rand_u16();
+    xy[1] = rand_u16();
+    mcode = morton_xy_encode_u16(xy);
+
+    xy_mcode[0] = morton2D_encode_u16(xy[0]);
+    xy_mcode[1] = morton2D_encode_u16(xy[1]);
+    CHK(mcode == ((xy_mcode[0]<<1) | (xy_mcode[1]<<0)));
+
+    morton_xy_decode_u16(mcode, xy2);
+    CHK(xy[0] == xy2[0]);
+    CHK(xy[1] == xy2[1]);
+  }
+
+}
+
+static void
+test_morton3D(void)
 {
   int bit = 0;
   int i = 0;
-  (void)argc, (void)argv;
 
   FOR_EACH(bit, 0, 21) {
     CHK(morton3D_encode_u21(BIT_U32(bit)) == BIT_U64(3*bit));
@@ -74,10 +132,17 @@ main(int argc, char** argv)
     CHK(mcode == ((xyz_mcode[0]<<2) | (xyz_mcode[1]<<1) | (xyz_mcode[2]<<0)));
 
     morton_xyz_decode_u21(mcode, xyz2);
-    CHK(xyz[0] = xyz2[0]);
-    CHK(xyz[1] = xyz2[1]);
-    CHK(xyz[2] = xyz2[2]);
+    CHK(xyz[0] == xyz2[0]);
+    CHK(xyz[1] == xyz2[1]);
+    CHK(xyz[2] == xyz2[2]);
   }
+}
 
+int
+main(int argc, char** argv)
+{
+  (void)argc, (void)argv;
+  test_morton2D();
+  test_morton3D();
   return 0;
 }