--- 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,