1217 " |
1217 " |
1218 |
1218 |
1219 "Modified: / 09-01-2012 / 19:12:41 / cg" |
1219 "Modified: / 09-01-2012 / 19:12:41 / cg" |
1220 ! |
1220 ! |
1221 |
1221 |
|
1222 bitDeinterleave:n |
|
1223 "extract count integers from an n-way Morton number as a vector; |
|
1224 This is the inverse operation from bitInterleave: - see comment there. |
|
1225 i.e. if count is 3, |
|
1226 and the receiver's bits are |
|
1227 cN bN aN ... c2 b2 a2 c1 b1 a1 c0 b0 a0 |
|
1228 then the result will be a vector containing the numbers a,b,c with bits: |
|
1229 aN ... a2 a1 a0 |
|
1230 bN ... b2 b1 b0 |
|
1231 cN ... c2 c1 c0." |
|
1232 |
|
1233 %{ |
|
1234 #if __POINTER_SIZE__ == 8 |
|
1235 |
|
1236 # define M5555555555555555 0x5555555555555555 |
|
1237 # define M3333333333333333 0x3333333333333333 |
|
1238 # define M0f0f0f0f0f0f0f0f 0x0f0f0f0f0f0f0f0f |
|
1239 # define M00ff00ff00ff00ff 0x00ff00ff00ff00ff |
|
1240 # define M0000ffff0000ffff 0x0000ffff0000ffff |
|
1241 # define M00000000ffffffff 0x00000000ffffffff |
|
1242 |
|
1243 # define M9249249249249249 0x9249249249249249 |
|
1244 # define M30c30c30c30c30c3 0x30c30c30c30c30c3 |
|
1245 # define Mf00f00f00f00f00f 0xf00f00f00f00f00f |
|
1246 # define M00ff0000ff0000ff 0x00ff0000ff0000ff |
|
1247 # define Mffff00000000ffff 0xffff00000000ffff |
|
1248 |
|
1249 #else |
|
1250 |
|
1251 # define M5555555555555555 0x55555555 |
|
1252 # define M3333333333333333 0x33333333 |
|
1253 # define M0f0f0f0f0f0f0f0f 0x0f0f0f0f |
|
1254 # define M00ff00ff00ff00ff 0x00ff00ff |
|
1255 # define M0000ffff0000ffff 0x0000ffff |
|
1256 # define M00000000ffffffff 0 |
|
1257 |
|
1258 # define M9249249249249249 0x49249249 |
|
1259 # define M30c30c30c30c30c3 0xc30c30c3 |
|
1260 # define Mf00f00f00f00f00f 0x0f00f00f |
|
1261 # define M00ff0000ff0000ff 0xff0000ff |
|
1262 # define Mffff00000000ffff 0x0000ffff |
|
1263 |
|
1264 #endif |
|
1265 |
|
1266 unsigned INT bits = __intVal(self); |
|
1267 unsigned INT a, b; |
|
1268 |
|
1269 if (n == __MKSMALLINT(2)) { |
|
1270 # define morton2(x,dst) \ |
|
1271 { \ |
|
1272 unsigned INT t; \ |
|
1273 t = (x) & M5555555555555555; \ |
|
1274 t = (t | (t >> 1)) & M3333333333333333; \ |
|
1275 t = (t | (t >> 2)) & M0f0f0f0f0f0f0f0f; \ |
|
1276 t = (t | (t >> 4)) & M00ff00ff00ff00ff; \ |
|
1277 t = (t | (t >> 8)) & M0000ffff0000ffff; \ |
|
1278 t = (t | (t >> 16)) & M00000000ffffffff; \ |
|
1279 dst = t; \ |
|
1280 } |
|
1281 |
|
1282 morton2(bits, a); |
|
1283 morton2(bits>>1, b); |
|
1284 RETURN (__ARRAY_WITH2(__MKSMALLINT(a), __MKSMALLINT(b))); |
|
1285 } |
|
1286 |
|
1287 if (n == __MKSMALLINT(3)) { |
|
1288 unsigned INT c; |
|
1289 |
|
1290 # define morton3(x,dst) \ |
|
1291 { \ |
|
1292 unsigned INT t; \ |
|
1293 t = (x) & M9249249249249249; \ |
|
1294 t = (t | (t >> 2)) & M30c30c30c30c30c3; \ |
|
1295 t = (t | (t >> 4)) & Mf00f00f00f00f00f; \ |
|
1296 t = (t | (t >> 8)) & M00ff0000ff0000ff; \ |
|
1297 t = (t | (t >> 16)) & Mffff00000000ffff; \ |
|
1298 t = (t | (t >> 32)) & M00000000ffffffff; \ |
|
1299 dst = t; \ |
|
1300 } |
|
1301 |
|
1302 morton3(bits, a); |
|
1303 morton3(bits>>1, b); |
|
1304 morton3(bits>>2, c); |
|
1305 RETURN (__ARRAY_WITH3(__MKSMALLINT(a), __MKSMALLINT(b), __MKSMALLINT(c))); |
|
1306 } |
|
1307 done: ; |
|
1308 %}. |
|
1309 ^ super bitDeinterleave:n |
|
1310 |
|
1311 " |
|
1312 (2r1100 bitInterleaveWith:2r1001) bitDeinterleave:2 -> #(12 9) |
|
1313 (197 bitInterleaveWith:144) bitDeinterleave:2 -> #(197 144) |
|
1314 |
|
1315 (197 bitInterleaveWith:144 and:62) bitDeinterleave:3 -> #(197 144 62) |
|
1316 |
|
1317 |a b| |
|
1318 (0 to:31) do:[:bitA | |
|
1319 a := 1 << bitA. |
|
1320 (0 to:31) do:[:bitB | |
|
1321 b := 1 << bitB. |
|
1322 self assert:( (a bitInterleaveWith:b) bitDeinterleave:2 ) = {a . b } |
|
1323 ]. |
|
1324 ]. |
|
1325 |
|
1326 |a b c| |
|
1327 (0 to:31) do:[:bitA | |
|
1328 a := 1 << bitA. |
|
1329 (0 to:31) do:[:bitB | |
|
1330 b := 1 << bitB. |
|
1331 (0 to:31) do:[:bitC | |
|
1332 c := 1 << bitC. |
|
1333 self assert:( (a bitInterleaveWith:b and:c) bitDeinterleave:3 ) = {a . b . c} |
|
1334 ]. |
|
1335 ]. |
|
1336 ]. |
|
1337 " |
|
1338 |
|
1339 "Created: / 28-08-2017 / 18:32:48 / cg" |
|
1340 ! |
|
1341 |
1222 bitInterleaveWith:anInteger |
1342 bitInterleaveWith:anInteger |
1223 "generate a Morton number (-> https://en.wikipedia.org/wiki/Morton_number_(number_theory)) |
1343 "generate a Morton number (-> https://en.wikipedia.org/wiki/Morton_number_(number_theory)) |
1224 by interleaving bits of the receiver |
1344 by interleaving bits of the receiver |
1225 (at even positions if counting from 1) with bits of the argument (at odd bit positions). |
1345 (at even positions if counting from 1) with bits of the argument (at odd bit positions). |
1226 Thus, if the bits of the receiver are |
1346 Thus, if the bits of the receiver are |
1233 Morton numbers are great to linearize 2D coordinates |
1353 Morton numbers are great to linearize 2D coordinates |
1234 eg. to sort 2D points by distances" |
1354 eg. to sort 2D points by distances" |
1235 |
1355 |
1236 %{ |
1356 %{ |
1237 #if __POINTER_SIZE__ == 8 |
1357 #if __POINTER_SIZE__ == 8 |
|
1358 # define __SLOW_MULTIPLY__ |
1238 # ifndef __SLOW_MULTIPLY__ |
1359 # ifndef __SLOW_MULTIPLY__ |
1239 |
1360 |
1240 // the following is only faster, if multiplication is faster than a memory fetch |
1361 // the following is only faster, if multiplication is faster than a memory fetch |
1241 if (__isSmallInteger(anInteger)) { |
1362 if (__isSmallInteger(anInteger)) { |
1242 INT _a = __intVal(self); |
1363 INT _a = __intVal(self); |
1260 shift += 16; |
1381 shift += 16; |
1261 } |
1382 } |
1262 RETURN (__MKUINT(val) ); |
1383 RETURN (__MKUINT(val) ); |
1263 } |
1384 } |
1264 } |
1385 } |
|
1386 # else |
|
1387 # if __POINTER_SIZE__ == 8 |
|
1388 # define HALF_INT_MAX 0xFFFFFFFFFFFFFFFF |
|
1389 # define M55555555 0x5555555555555555 |
|
1390 # define M33333333 0x3333333333333333 |
|
1391 # define M0F0F0F0F 0x0F0F0F0F0F0F0F0F |
|
1392 # define M00FF00FF 0x00FF00FF00FF00FF |
|
1393 # define M0000FFFF 0x0000FFFF0000FFFF |
|
1394 # else |
|
1395 # define HALF_INT_MAX 0xFFFFFFFF |
|
1396 # define M55555555 0x55555555 |
|
1397 # define M33333333 0x33333333 |
|
1398 # define M0F0F0F0F 0x0F0F0F0F |
|
1399 # define M00FF00FF 0x00FF00FF |
|
1400 # define M0000FFFF 0 |
|
1401 # endif |
|
1402 |
|
1403 if (__isSmallInteger(anInteger)) { |
|
1404 INT _a = __intVal(self); |
|
1405 INT _b = __intVal(anInteger); |
|
1406 |
|
1407 if ( (((unsigned)_a)<=HALF_INT_MAX) && (((unsigned)_b)<=HALF_INT_MAX) ) { |
|
1408 unsigned INT val; |
|
1409 |
|
1410 _a = (_a | (_a << 16)) & M0000FFFF; |
|
1411 _a = (_a | (_a << 8)) & M00FF00FF; |
|
1412 _a = (_a | (_a << 4)) & M0F0F0F0F; |
|
1413 _a = (_a | (_a << 2)) & M33333333; |
|
1414 _a = (_a | (_a << 1)) & M55555555; |
|
1415 |
|
1416 _b = (_b | (_b << 16)) & M0000FFFF; |
|
1417 _b = (_b | (_b << 8)) & M00FF00FF; |
|
1418 _b = (_b | (_b << 4)) & M0F0F0F0F; |
|
1419 _b = (_b | (_b << 2)) & M33333333; |
|
1420 _b = (_b | (_b << 1)) & M55555555; |
|
1421 |
|
1422 val = _a | (_b << 1); |
|
1423 RETURN (__MKUINT(val) ); |
|
1424 } |
|
1425 } |
1265 |
1426 |
1266 # endif |
1427 # endif |
1267 #endif |
1428 #endif |
1268 %}. |
1429 %}. |
1269 ^ super bitInterleaveWith:anInteger |
1430 ^ super bitInterleaveWith:anInteger |
1270 |
1431 |
1271 " |
1432 " |
1272 (2r1100 bitInterleaveWith:2r1001) printStringRadix:2 -> '11 01 00 10' |
1433 (2r1100 bitInterleaveWith:2r1001) printStringRadix:2 -> '11 01 00 10' |
1273 (2r11000101 bitInterleaveWith:2r10010000) printStringRadix:2 -> '11 01 00 10 00 01 00 01' |
1434 (2r11000101 bitInterleaveWith:2r10010000) printStringRadix:2'1101001000010001 -> '11 01 00 10 00 01 00 01' |
|
1435 |
|
1436 |a b| |
|
1437 (0 to:31) do:[:bitA | |
|
1438 a := 1 << bitA. |
|
1439 (0 to:31) do:[:bitB | |
|
1440 b := 1 << bitB. |
|
1441 self assert:( (a bitInterleaveWith:b) bitDeinterleave:2 ) = {a . b } |
|
1442 ]. |
|
1443 ]. |
|
1444 |
1274 " |
1445 " |
1275 |
1446 |
1276 "Created: / 28-08-2017 / 14:33:52 / cg" |
1447 "Created: / 28-08-2017 / 14:33:52 / cg" |
|
1448 "Modified (comment): / 28-08-2017 / 19:30:14 / cg" |
1277 ! |
1449 ! |
1278 |
1450 |
1279 bitInvert |
1451 bitInvert |
1280 "return the value of the receiver with all bits inverted. |
1452 "return the value of the receiver with all bits inverted. |
1281 The method's name may be misleading: the receiver is not changed, |
1453 The method's name may be misleading: the receiver is not changed, |