# HG changeset patch
# User Claus Gittinger <cg@exept.de>
# Date 1503926090 -7200
# Node ID afff1eb8cb7109d089d8d5f0d7928cb958a50c0f
# Parent  3dadc5038ad86a7a7e42f375517ce337b84aa7e8
#FEATURE by cg
class: SmallInteger
added: #bitInterleaveWith:

diff -r 3dadc5038ad8 -r afff1eb8cb71 SmallInteger.st
--- a/SmallInteger.st	Mon Aug 28 15:14:38 2017 +0200
+++ b/SmallInteger.st	Mon Aug 28 15:14:50 2017 +0200
@@ -1219,6 +1219,63 @@
     "Modified: / 09-01-2012 / 19:12:41 / cg"
 !
 
+bitInterleaveWith:anInteger
+    "generate a Morton number (-> https://en.wikipedia.org/wiki/Morton_number_(number_theory)) 
+     by interleaving bits of the receiver 
+     (at even positions if counting from 1) with bits of the argument (at odd bit positions).
+     Thus, if the bits of the receiver are
+        aN ... a2 a1 a0
+     and those of the argument are:
+        bN ... b2 b1 b0
+     the result is
+        bN aN ... b2 a2 b1 a1 b0 a0.
+
+     Morton numbers are great to linearize 2D coordinates
+     eg. to sort 2D points by distances"    
+
+%{
+#if __POINTER_SIZE__ == 8
+# ifndef __SLOW_MULTIPLY__
+
+    // the following is only faster, if multiplication is faster than a memory fetch
+    if (__isSmallInteger(anInteger)) {
+        INT _a = __intVal(self);
+        INT _b = __intVal(anInteger); 
+
+        if ( (((unsigned)_a)<=0xFFFFFFFF) && (((unsigned)_b)<=0xFFFFFFFF) )  {
+            int shift = 0;
+            unsigned INT val = 0;
+
+            // Interleave bits of (8-bit) a and b, so that all of the
+            // bits of a are in the even positions and b in the odd;
+            // resulting in a 16-bit Morton Number.
+#           define interleaveBytes(a,b) \
+                ((((a * 0x0101010101010101ULL & 0x8040201008040201ULL) * 0x0102040810204081ULL >> 49) & 0x5555) \ 
+                | (((b * 0x0101010101010101ULL & 0x8040201008040201ULL) * 0x0102040810204081ULL >> 48) & 0xAAAA)) 
+
+            while (_a | _b) {
+                val |= (interleaveBytes((_a & 0xFF), (_b & 0xFF)) << shift); 
+                _a = _a >> 8;    
+                _b = _b >> 8;
+                shift += 16;
+            } 
+            RETURN (__MKUINT(val) );
+        }
+    }
+    
+# endif
+#endif
+%}.
+    ^ super bitInterleaveWith:anInteger
+
+    "
+     (2r1100 bitInterleaveWith:2r1001) printStringRadix:2 -> '11 01 00 10'
+     (2r11000101 bitInterleaveWith:2r10010000) printStringRadix:2 -> '11 01 00 10 00 01 00 01'
+    "
+
+    "Created: / 28-08-2017 / 14:33:52 / cg"
+!
+
 bitInvert
     "return the value of the receiver with all bits inverted.
      The method's name may be misleading: the receiver is not changed,