1222 bitDeinterleave:n |
1222 bitDeinterleave:n |
1223 "extract count integers from an n-way Morton number as a vector; |
1223 "extract count integers from an n-way Morton number as a vector; |
1224 This is the inverse operation from bitInterleave: - see comment there. |
1224 This is the inverse operation from bitInterleave: - see comment there. |
1225 i.e. if count is 3, |
1225 i.e. if count is 3, |
1226 and the receiver's bits are |
1226 and the receiver's bits are |
1227 cN bN aN ... c2 b2 a2 c1 b1 a1 c0 b0 a0 |
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: |
1228 then the result will be a vector containing the numbers a,b,c with bits: |
1229 aN ... a2 a1 a0 |
1229 aN ... a2 a1 a0 |
1230 bN ... b2 b1 b0 |
1230 bN ... b2 b1 b0 |
1231 cN ... c2 c1 c0." |
1231 cN ... c2 c1 c0." |
1232 |
1232 |
1233 %{ |
1233 %{ |
1234 #if __POINTER_SIZE__ == 8 |
1234 #if __POINTER_SIZE__ == 8 |
1235 |
1235 |
1236 # define M5555555555555555 0x5555555555555555 |
1236 # define M5555555555555555 0x5555555555555555 |
1261 # define M00ff0000ff0000ff 0xff0000ff |
1261 # define M00ff0000ff0000ff 0xff0000ff |
1262 # define Mffff00000000ffff 0x0000ffff |
1262 # define Mffff00000000ffff 0x0000ffff |
1263 |
1263 |
1264 #endif |
1264 #endif |
1265 |
1265 |
1266 unsigned INT bits = __intVal(self); |
1266 unsigned INT bits = __intVal(self); |
1267 unsigned INT a, b; |
1267 unsigned INT a, b; |
1268 |
1268 |
1269 if (n == __MKSMALLINT(2)) { |
1269 if (n == __MKSMALLINT(2)) { |
1270 # define morton2(x,dst) \ |
1270 # define morton2(x,dst) \ |
1271 { \ |
1271 { \ |
1272 unsigned INT t; \ |
1272 unsigned INT t; \ |
1273 t = (x) & M5555555555555555; \ |
1273 t = (x) & M5555555555555555; \ |
1274 t = (t | (t >> 1)) & M3333333333333333; \ |
1274 t = (t | (t >> 1)) & M3333333333333333; \ |
1275 t = (t | (t >> 2)) & M0f0f0f0f0f0f0f0f; \ |
1275 t = (t | (t >> 2)) & M0f0f0f0f0f0f0f0f; \ |
1276 t = (t | (t >> 4)) & M00ff00ff00ff00ff; \ |
1276 t = (t | (t >> 4)) & M00ff00ff00ff00ff; \ |
1277 t = (t | (t >> 8)) & M0000ffff0000ffff; \ |
1277 t = (t | (t >> 8)) & M0000ffff0000ffff; \ |
1278 t = (t | (t >> 16)) & M00000000ffffffff; \ |
1278 t = (t | (t >> 16)) & M00000000ffffffff; \ |
1279 dst = t; \ |
1279 dst = t; \ |
1280 } |
1280 } |
1281 |
1281 |
1282 morton2(bits, a); |
1282 morton2(bits, a); |
1283 morton2(bits>>1, b); |
1283 morton2(bits>>1, b); |
1284 RETURN (__ARRAY_WITH2(__MKSMALLINT(a), __MKSMALLINT(b))); |
1284 RETURN (__ARRAY_WITH2(__MKSMALLINT(a), __MKSMALLINT(b))); |
1285 } |
1285 } |
1286 |
1286 |
1287 if (n == __MKSMALLINT(3)) { |
1287 if (n == __MKSMALLINT(3)) { |
1288 unsigned INT c; |
1288 unsigned INT c; |
1289 |
1289 |
1290 # define morton3(x,dst) \ |
1290 # define morton3(x,dst) \ |
1291 { \ |
1291 { \ |
1292 unsigned INT t; \ |
1292 unsigned INT t; \ |
1293 t = (x) & M9249249249249249; \ |
1293 t = (x) & M9249249249249249; \ |
1294 t = (t | (t >> 2)) & M30c30c30c30c30c3; \ |
1294 t = (t | (t >> 2)) & M30c30c30c30c30c3; \ |
1295 t = (t | (t >> 4)) & Mf00f00f00f00f00f; \ |
1295 t = (t | (t >> 4)) & Mf00f00f00f00f00f; \ |
1296 t = (t | (t >> 8)) & M00ff0000ff0000ff; \ |
1296 t = (t | (t >> 8)) & M00ff0000ff0000ff; \ |
1297 t = (t | (t >> 16)) & Mffff00000000ffff; \ |
1297 t = (t | (t >> 16)) & Mffff00000000ffff; \ |
1298 t = (t | (t >> 32)) & M00000000ffffffff; \ |
1298 t = (t | (t >> 32)) & M00000000ffffffff; \ |
1299 dst = t; \ |
1299 dst = t; \ |
1300 } |
1300 } |
1301 |
1301 |
1302 morton3(bits, a); |
1302 morton3(bits, a); |
1303 morton3(bits>>1, b); |
1303 morton3(bits>>1, b); |
1304 morton3(bits>>2, c); |
1304 morton3(bits>>2, c); |
1305 RETURN (__ARRAY_WITH3(__MKSMALLINT(a), __MKSMALLINT(b), __MKSMALLINT(c))); |
1305 RETURN (__ARRAY_WITH3(__MKSMALLINT(a), __MKSMALLINT(b), __MKSMALLINT(c))); |
1306 } |
1306 } |
1307 done: ; |
1307 done: ; |
1308 %}. |
1308 %}. |
1309 ^ super bitDeinterleave:n |
1309 ^ super bitDeinterleave:n |
1310 |
1310 |
1314 |
1314 |
1315 (197 bitInterleaveWith:144 and:62) bitDeinterleave:3 -> #(197 144 62) |
1315 (197 bitInterleaveWith:144 and:62) bitDeinterleave:3 -> #(197 144 62) |
1316 |
1316 |
1317 |a b| |
1317 |a b| |
1318 (0 to:31) do:[:bitA | |
1318 (0 to:31) do:[:bitA | |
1319 a := 1 << bitA. |
1319 a := 1 << bitA. |
1320 (0 to:31) do:[:bitB | |
1320 (0 to:31) do:[:bitB | |
1321 b := 1 << bitB. |
1321 b := 1 << bitB. |
1322 self assert:( (a bitInterleaveWith:b) bitDeinterleave:2 ) = {a . b } |
1322 self assert:( (a bitInterleaveWith:b) bitDeinterleave:2 ) = {a . b } |
1323 ]. |
1323 ]. |
1324 ]. |
1324 ]. |
1325 |
1325 |
1326 |a b c| |
1326 |a b c| |
1327 (0 to:31) do:[:bitA | |
1327 (0 to:31) do:[:bitA | |
1328 a := 1 << bitA. |
1328 a := 1 << bitA. |
1329 (0 to:31) do:[:bitB | |
1329 (0 to:31) do:[:bitB | |
1330 b := 1 << bitB. |
1330 b := 1 << bitB. |
1331 (0 to:31) do:[:bitC | |
1331 (0 to:31) do:[:bitC | |
1332 c := 1 << bitC. |
1332 c := 1 << bitC. |
1333 self assert:( (a bitInterleaveWith:b and:c) bitDeinterleave:3 ) = {a . b . c} |
1333 self assert:( (a bitInterleaveWith:b and:c) bitDeinterleave:3 ) = {a . b . c} |
1334 ]. |
1334 ]. |
1335 ]. |
1335 ]. |
1336 ]. |
1336 ]. |
1337 " |
1337 " |
1338 |
1338 |
1339 "Created: / 28-08-2017 / 18:32:48 / cg" |
1339 "Created: / 28-08-2017 / 18:32:48 / cg" |
1340 ! |
1340 ! |
1341 |
1341 |
1342 bitInterleaveWith:anInteger |
1342 bitInterleaveWith:anInteger |
1343 "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)) |
1344 by interleaving bits of the receiver |
1344 by interleaving bits of the receiver |
1345 (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). |
1346 Thus, if the bits of the receiver are |
1346 Thus, if the bits of the receiver are |
1347 aN ... a2 a1 a0 |
1347 aN ... a2 a1 a0 |
1348 and those of the argument are: |
1348 and those of the argument are: |
1349 bN ... b2 b1 b0 |
1349 bN ... b2 b1 b0 |
1350 the result is |
1350 the result is |
1351 bN aN ... b2 a2 b1 a1 b0 a0. |
1351 bN aN ... b2 a2 b1 a1 b0 a0. |
1352 |
1352 |
1353 Morton numbers are great to linearize 2D coordinates |
1353 Morton numbers are great to linearize 2D coordinates |
1354 eg. to sort 2D points by distances" |
1354 eg. to sort 2D points by distances" |
1355 |
1355 |
1356 %{ |
1356 %{ |
1357 #if __POINTER_SIZE__ == 8 |
1357 #if __POINTER_SIZE__ == 8 |
1358 # define __SLOW_MULTIPLY__ |
1358 # define __SLOW_MULTIPLY__ |
1359 # ifndef __SLOW_MULTIPLY__ |
1359 # ifndef __SLOW_MULTIPLY__ |
1360 |
1360 |
1361 // 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 |
1362 if (__isSmallInteger(anInteger)) { |
1362 if (__isSmallInteger(anInteger)) { |
1363 INT _a = __intVal(self); |
1363 INT _a = __intVal(self); |
1364 INT _b = __intVal(anInteger); |
1364 INT _b = __intVal(anInteger); |
1365 |
1365 |
1366 if ( (((unsigned)_a)<=0xFFFFFFFF) && (((unsigned)_b)<=0xFFFFFFFF) ) { |
1366 if ( (((unsigned)_a)<=0xFFFFFFFF) && (((unsigned)_b)<=0xFFFFFFFF) ) { |
1367 int shift = 0; |
1367 int shift = 0; |
1368 unsigned INT val = 0; |
1368 unsigned INT val = 0; |
1369 |
1369 |
1370 // Interleave bits of (8-bit) a and b, so that all of the |
1370 // Interleave bits of (8-bit) a and b, so that all of the |
1371 // bits of a are in the even positions and b in the odd; |
1371 // bits of a are in the even positions and b in the odd; |
1372 // resulting in a 16-bit Morton Number. |
1372 // resulting in a 16-bit Morton Number. |
1373 # define interleaveBytes(a,b) \ |
1373 # define interleaveBytes(a,b) \ |
1374 ((((a * 0x0101010101010101ULL & 0x8040201008040201ULL) * 0x0102040810204081ULL >> 49) & 0x5555) \ |
1374 ((((a * 0x0101010101010101ULL & 0x8040201008040201ULL) * 0x0102040810204081ULL >> 49) & 0x5555) \ |
1375 | (((b * 0x0101010101010101ULL & 0x8040201008040201ULL) * 0x0102040810204081ULL >> 48) & 0xAAAA)) |
1375 | (((b * 0x0101010101010101ULL & 0x8040201008040201ULL) * 0x0102040810204081ULL >> 48) & 0xAAAA)) |
1376 |
1376 |
1377 while (_a | _b) { |
1377 while (_a | _b) { |
1378 val |= (interleaveBytes((_a & 0xFF), (_b & 0xFF)) << shift); |
1378 val |= (interleaveBytes((_a & 0xFF), (_b & 0xFF)) << shift); |
1379 _a = _a >> 8; |
1379 _a = _a >> 8; |
1380 _b = _b >> 8; |
1380 _b = _b >> 8; |
1381 shift += 16; |
1381 shift += 16; |
1382 } |
1382 } |
1383 RETURN (__MKUINT(val) ); |
1383 RETURN (__MKUINT(val) ); |
1384 } |
1384 } |
1385 } |
1385 } |
1386 # else |
1386 # else |
1387 # if __POINTER_SIZE__ == 8 |
1387 # if __POINTER_SIZE__ == 8 |
1388 # define HALF_INT_MAX 0xFFFFFFFFFFFFFFFF |
1388 # define HALF_INT_MAX 0xFFFFFFFFFFFFFFFF |
1389 # define M55555555 0x5555555555555555 |
1389 # define M55555555 0x5555555555555555 |
1399 # define M00FF00FF 0x00FF00FF |
1399 # define M00FF00FF 0x00FF00FF |
1400 # define M0000FFFF 0 |
1400 # define M0000FFFF 0 |
1401 # endif |
1401 # endif |
1402 |
1402 |
1403 if (__isSmallInteger(anInteger)) { |
1403 if (__isSmallInteger(anInteger)) { |
1404 INT _a = __intVal(self); |
1404 INT _a = __intVal(self); |
1405 INT _b = __intVal(anInteger); |
1405 INT _b = __intVal(anInteger); |
1406 |
1406 |
1407 if ( (((unsigned)_a)<=HALF_INT_MAX) && (((unsigned)_b)<=HALF_INT_MAX) ) { |
1407 if ( (((unsigned)_a)<=HALF_INT_MAX) && (((unsigned)_b)<=HALF_INT_MAX) ) { |
1408 unsigned INT val; |
1408 unsigned INT val; |
1409 |
1409 |
1410 _a = (_a | (_a << 16)) & M0000FFFF; |
1410 _a = (_a | (_a << 16)) & M0000FFFF; |
1411 _a = (_a | (_a << 8)) & M00FF00FF; |
1411 _a = (_a | (_a << 8)) & M00FF00FF; |
1412 _a = (_a | (_a << 4)) & M0F0F0F0F; |
1412 _a = (_a | (_a << 4)) & M0F0F0F0F; |
1413 _a = (_a | (_a << 2)) & M33333333; |
1413 _a = (_a | (_a << 2)) & M33333333; |
1414 _a = (_a | (_a << 1)) & M55555555; |
1414 _a = (_a | (_a << 1)) & M55555555; |
1415 |
1415 |
1416 _b = (_b | (_b << 16)) & M0000FFFF; |
1416 _b = (_b | (_b << 16)) & M0000FFFF; |
1417 _b = (_b | (_b << 8)) & M00FF00FF; |
1417 _b = (_b | (_b << 8)) & M00FF00FF; |
1418 _b = (_b | (_b << 4)) & M0F0F0F0F; |
1418 _b = (_b | (_b << 4)) & M0F0F0F0F; |
1419 _b = (_b | (_b << 2)) & M33333333; |
1419 _b = (_b | (_b << 2)) & M33333333; |
1420 _b = (_b | (_b << 1)) & M55555555; |
1420 _b = (_b | (_b << 1)) & M55555555; |
1421 |
1421 |
1422 val = _a | (_b << 1); |
1422 val = _a | (_b << 1); |
1423 RETURN (__MKUINT(val) ); |
1423 RETURN (__MKUINT(val) ); |
1424 } |
1424 } |
1425 } |
1425 } |
1426 |
1426 |
1427 # endif |
1427 # endif |
1428 #endif |
1428 #endif |
1429 %}. |
1429 %}. |
1430 ^ super bitInterleaveWith:anInteger |
1430 ^ super bitInterleaveWith:anInteger |
1431 |
1431 |
1814 Returns 0 if no bit is set." |
1814 Returns 0 if no bit is set." |
1815 |
1815 |
1816 %{ /* NOCONTEXT */ |
1816 %{ /* NOCONTEXT */ |
1817 #ifdef __SCHTEAM__ |
1817 #ifdef __SCHTEAM__ |
1818 { |
1818 { |
1819 long bits = self.longValue(); |
1819 long bits = self.longValue(); |
1820 int bitNr = 0; |
1820 int bitNr = 0; |
1821 |
1821 |
1822 if (bits != 0) { |
1822 if (bits != 0) { |
1823 if ((bits & 0xFFFFFFFF00000000L) != 0) { |
1823 if ((bits & 0xFFFFFFFF00000000L) != 0) { |
1824 bitNr += 32; bits >>= 32; |
1824 bitNr += 32; bits >>= 32; |
1825 } |
1825 } |
1826 if ((bits & 0xFFFF0000L) != 0) { |
1826 if ((bits & 0xFFFF0000L) != 0) { |
1827 bitNr += 16; bits >>= 16; |
1827 bitNr += 16; bits >>= 16; |
1828 } |
1828 } |
1829 if ((bits & 0xFF00) != 0) { |
1829 if ((bits & 0xFF00) != 0) { |
1830 bitNr += 8; bits >>= 8; |
1830 bitNr += 8; bits >>= 8; |
1831 } |
1831 } |
1832 if ((bits & 0xF0) != 0) { |
1832 if ((bits & 0xF0) != 0) { |
1833 bitNr += 4; bits >>= 4; |
1833 bitNr += 4; bits >>= 4; |
1834 } |
1834 } |
1835 if ((bits & 0xC) != 0) { |
1835 if ((bits & 0xC) != 0) { |
1836 bitNr += 2; bits >>= 2; |
1836 bitNr += 2; bits >>= 2; |
1837 } |
1837 } |
1838 if ((bits & 0x2) != 0) { |
1838 if ((bits & 0x2) != 0) { |
1839 bitNr += 1; bits >>= 1; |
1839 bitNr += 1; bits >>= 1; |
1840 } |
1840 } |
1841 bitNr += 1; |
1841 bitNr += 1; |
1842 } |
1842 } |
1843 return context._RETURN( STInteger._new(bitNr) ); |
1843 return context._RETURN( STInteger._new(bitNr) ); |
1844 } |
1844 } |
1845 /* NOTREACHED */ |
1845 /* NOTREACHED */ |
1846 #else |
1846 #else |
1847 unsigned INT bits; |
1847 unsigned INT bits; |
1848 int index; |
1848 int index; |
1878 # else |
1878 # else |
1879 /* |
1879 /* |
1880 * general fallback; not super-fast, |
1880 * general fallback; not super-fast, |
1881 * but fast enough on all machines (better than a bit-masking loop, definitely). |
1881 * but fast enough on all machines (better than a bit-masking loop, definitely). |
1882 */ |
1882 */ |
1883 |
1883 |
1884 index = 0; |
1884 index = 0; |
1885 |
1885 |
1886 bits = __intVal(self); |
1886 bits = __intVal(self); |
1887 if (bits == 0) { |
1887 if (bits == 0) { |
1888 RETURN ( __mkSmallInteger(0) ); |
1888 RETURN ( __mkSmallInteger(0) ); |
1889 } |
1889 } |
1890 # if __POINTER_SIZE__ == 8 |
1890 # if __POINTER_SIZE__ == 8 |
1891 if (bits & 0xFFFFFFFF00000000L) { |
1891 if (bits & 0xFFFFFFFF00000000L) { |
1892 index += 32; bits >>= 32; |
1892 index += 32; bits >>= 32; |
1893 } |
1893 } |
1894 # endif |
1894 # endif |
1895 if (bits & 0xFFFF0000L) { |
1895 if (bits & 0xFFFF0000L) { |
1896 index += 16; bits >>= 16; |
1896 index += 16; bits >>= 16; |
1897 } |
1897 } |
1898 if (bits & 0xFF00) { |
1898 if (bits & 0xFF00) { |
1899 index += 8; bits >>= 8; |
1899 index += 8; bits >>= 8; |
1900 } |
1900 } |
1901 if (bits & 0xF0) { |
1901 if (bits & 0xF0) { |
1902 index += 4; bits >>= 4; |
1902 index += 4; bits >>= 4; |
1903 } |
1903 } |
1904 if (bits & 0xC) { |
1904 if (bits & 0xC) { |
1905 index += 2; bits >>= 2; |
1905 index += 2; bits >>= 2; |
1906 } |
1906 } |
1907 if (bits & 0x2) { |
1907 if (bits & 0x2) { |
1908 index += 1; bits >>= 1; |
1908 index += 1; bits >>= 1; |
1909 } |
1909 } |
1910 # endif /* not IEE float */ |
1910 # endif /* not IEE float */ |
1911 # endif /* no BSR instruction */ |
1911 # endif /* no BSR instruction */ |
1912 |
1912 |
1913 RETURN ( __mkSmallInteger(index+1) ); |
1913 RETURN ( __mkSmallInteger(index+1) ); |
1922 2r100 highBit |
1922 2r100 highBit |
1923 2r1000 highBit |
1923 2r1000 highBit |
1924 2r100000000000 highBit |
1924 2r100000000000 highBit |
1925 |
1925 |
1926 ((0 to:64) collect:[:s | 1 bitShift:s]) |
1926 ((0 to:64) collect:[:s | 1 bitShift:s]) |
1927 collect:[:n | n highBit] |
1927 collect:[:n | n highBit] |
1928 |
1928 |
1929 (((0 to:64) collect:[:s | 1 bitShift:s]) |
1929 (((0 to:64) collect:[:s | 1 bitShift:s]) |
1930 collect:[:n | n highBit]) = (1 to:65) |
1930 collect:[:n | n highBit]) = (1 to:65) |
1931 " |
1931 " |
1932 |
1932 |
1933 " |
1933 " |
1934 Time millisecondsToRun:[ |
1934 Time millisecondsToRun:[ |
1935 1000000 timesRepeat:[ |
1935 1000000 timesRepeat:[ |
1936 2r1 highBit |
1936 2r1 highBit |
1937 ] |
1937 ] |
1938 ] |
1938 ] |
1939 " |
1939 " |
1940 " |
1940 " |
1941 Time millisecondsToRun:[ |
1941 Time millisecondsToRun:[ |
1942 1000000 timesRepeat:[ |
1942 1000000 timesRepeat:[ |
1943 2r1111 highBit |
1943 2r1111 highBit |
1944 ] |
1944 ] |
1945 ] |
1945 ] |
1946 " |
1946 " |
1947 " |
1947 " |
1948 Time millisecondsToRun:[ |
1948 Time millisecondsToRun:[ |
1949 1000000 timesRepeat:[ |
1949 1000000 timesRepeat:[ |
1950 2r11111111111111 highBit |
1950 2r11111111111111 highBit |
1951 ] |
1951 ] |
1952 ] |
1952 ] |
1953 " |
1953 " |
1954 " |
1954 " |
1955 Time millisecondsToRun:[ |
1955 Time millisecondsToRun:[ |
1956 1000000 timesRepeat:[ |
1956 1000000 timesRepeat:[ |
1957 2r11111111111111111111111111 highBit |
1957 2r11111111111111111111111111 highBit |
1958 ] |
1958 ] |
1959 ] |
1959 ] |
1960 " |
1960 " |
1961 |
1961 |
1962 " |
1962 " |
1963 2r000100 highBit |
1963 2r000100 highBit |
2093 |
2093 |
2094 rightShift:shiftCount |
2094 rightShift:shiftCount |
2095 "return the value of the receiver shifted by shiftCount bits; |
2095 "return the value of the receiver shifted by shiftCount bits; |
2096 right shift if shiftCount > 0; left shift otherwise. |
2096 right shift if shiftCount > 0; left shift otherwise. |
2097 Notice: the result of bitShift: on negative receivers is not |
2097 Notice: the result of bitShift: on negative receivers is not |
2098 defined in the language standard (since the implementation |
2098 defined in the language standard (since the implementation |
2099 is free to choose any internal representation for integers). |
2099 is free to choose any internal representation for integers). |
2100 However, ST/X preserves the sign." |
2100 However, ST/X preserves the sign." |
2101 |
2101 |
2102 %{ /* NOCONTEXT */ |
2102 %{ /* NOCONTEXT */ |
2103 #ifdef __SCHTEAM__ |
2103 #ifdef __SCHTEAM__ |
2104 #else |
2104 #else |
2105 INT bits, count; |
2105 INT bits, count; |
2106 |
2106 |
2107 if (__isSmallInteger(shiftCount)) { |
2107 if (__isSmallInteger(shiftCount)) { |
2108 bits = __intVal(self); |
2108 bits = __intVal(self); |
2109 if (bits == 0) { |
2109 if (bits == 0) { |
2110 RETURN (self); |
2110 RETURN (self); |
2111 } |
2111 } |
2112 |
2112 |
2113 count = __intVal(shiftCount); |
2113 count = __intVal(shiftCount); |
2114 |
2114 |
2115 if (count < 0) { |
2115 if (count < 0) { |
2116 /* |
2116 /* |
2117 * a left shift |
2117 * a left shift |
2118 */ |
2118 */ |
2119 count = -count; |
2119 count = -count; |
2120 # if defined(USE_LONGLONG_FOR_SHIFT) |
2120 # if defined(USE_LONGLONG_FOR_SHIFT) |
2121 if (count <= N_INT_BITS) { |
2121 if (count <= N_INT_BITS) { |
2122 unsigned LONGLONG result; |
2122 unsigned LONGLONG result; |
2123 |
2123 |
2124 result = (unsigned LONGLONG)bits; |
2124 result = (unsigned LONGLONG)bits; |
2125 result <<= count; |
2125 result <<= count; |
2126 if (result <= _MAX_INT) { |
2126 if (result <= _MAX_INT) { |
2127 RETURN ( __mkSmallInteger(result) ); |
2127 RETURN ( __mkSmallInteger(result) ); |
2128 } |
2128 } |
2129 { |
2129 { |
2130 RETURN (__MKLARGEINT64(1, (INT)(result >> 32), (INT)(result & 0xFFFFFFFF))); |
2130 RETURN (__MKLARGEINT64(1, (INT)(result >> 32), (INT)(result & 0xFFFFFFFF))); |
2131 } |
2131 } |
2132 } |
2132 } |
2133 # else |
2133 # else |
2134 /* |
2134 /* |
2135 * check for overflow |
2135 * check for overflow |
2136 */ |
2136 */ |
2137 if (count < (N_INT_BITS-1)) { |
2137 if (count < (N_INT_BITS-1)) { |
2138 if (! (bits >> (N_INT_BITS - 1 - count))) { |
2138 if (! (bits >> (N_INT_BITS - 1 - count))) { |
2139 RETURN ( __mkSmallInteger(bits << count) ); |
2139 RETURN ( __mkSmallInteger(bits << count) ); |
2140 } |
2140 } |
2141 /* |
2141 /* |
2142 * so, there is an overflow ... |
2142 * so, there is an overflow ... |
2143 * handle it as largeInteger |
2143 * handle it as largeInteger |
2144 */ |
2144 */ |
2145 /* FALL THROUGH */ |
2145 /* FALL THROUGH */ |
2146 } |
2146 } |
2147 # endif |
2147 # endif |
2148 } else { |
2148 } else { |
2149 if (count == 0) { |
2149 if (count == 0) { |
2150 RETURN (self); |
2150 RETURN (self); |
2151 } |
2151 } |
2152 |
2152 |
2153 /* |
2153 /* |
2154 * right shifts cannot overflow |
2154 * right shifts cannot overflow |
2155 * |
2155 * |
2156 * some machines ignore shifts bigger than |
2156 * some machines ignore shifts bigger than |
2157 * the number of bits in an int ... |
2157 * the number of bits in an int ... |
2158 */ |
2158 */ |
2159 if (count > (N_INT_BITS-1)) { |
2159 if (count > (N_INT_BITS-1)) { |
2160 RETURN (__mkSmallInteger(0)); |
2160 RETURN (__mkSmallInteger(0)); |
2161 } |
2161 } |
2162 |
2162 |
2163 RETURN ( __mkSmallInteger(bits >> count) ); |
2163 RETURN ( __mkSmallInteger(bits >> count) ); |
2164 } |
2164 } |
2165 } |
2165 } |
2166 #endif /* not __SCHTEAM__ */ |
2166 #endif /* not __SCHTEAM__ */ |
2167 %}. |
2167 %}. |
2168 (shiftCount isMemberOf:SmallInteger) ifTrue:[ |
2168 (shiftCount isMemberOf:SmallInteger) ifTrue:[ |
2169 ^ (LargeInteger value:self) rightShift:shiftCount |
2169 ^ (LargeInteger value:self) rightShift:shiftCount |
2170 ]. |
2170 ]. |
2171 ^ self rightShift:shiftCount asInteger "/ is this a good idea ? |
2171 ^ self rightShift:shiftCount asInteger "/ is this a good idea ? |
2172 |
2172 |
2173 |
2173 |
2174 " |
2174 " |
2175 16 rightShift:2 |
2175 16 rightShift:2 |
2176 -16 rightShift:2 |
2176 -16 rightShift:2 |
2177 |
2177 |
2178 4 rightShift:-2 |
2178 4 rightShift:-2 |
2179 -4 rightShift:-2 |
2179 -4 rightShift:-2 |
2180 " |
2180 " |
2181 |
2181 |
2182 "Modified: / 25-08-2017 / 12:30:42 / cg" |
2182 "Modified: / 25-08-2017 / 12:30:42 / cg" |
2183 ! ! |
2183 ! ! |
2184 |
2184 |
4251 !SmallInteger methodsFor:'misc math'! |
4251 !SmallInteger methodsFor:'misc math'! |
4252 |
4252 |
4253 bernoulli |
4253 bernoulli |
4254 "returns the nth Bernoulli number. |
4254 "returns the nth Bernoulli number. |
4255 The series runs this: |
4255 The series runs this: |
4256 1, 1/2, 1/6, 0, -1/30, 0, 1/42, 0, -1/30, 0, 5/66, 0, -691/2730, etc |
4256 1, 1/2, 1/6, 0, -1/30, 0, 1/42, 0, -1/30, 0, 5/66, 0, -691/2730, etc |
4257 |
4257 |
4258 Uses a table of the first 20 even bernoulli numbers. |
4258 Uses a table of the first 20 even bernoulli numbers. |
4259 So bernoulli(42) will fail for now. |
4259 So bernoulli(42) will fail for now. |
4260 Used with taylor series for tan" |
4260 Used with taylor series for tan" |
4261 |
4261 |
4262 |table p| |
4262 |table p| |
4263 |
4263 |
4264 table := #( |
4264 table := #( |
4265 (1 6) |
4265 (1 6) |
4266 (-1 30) |
4266 (-1 30) |
4267 (1 42) |
4267 (1 42) |
4268 (-1 30) |
4268 (-1 30) |
4269 (5 66) |
4269 (5 66) |
4270 (-691 2730) |
4270 (-691 2730) |
4271 (7 6) |
4271 (7 6) |
4272 (-3617 510) |
4272 (-3617 510) |
4273 (43867 798) |
4273 (43867 798) |
4274 (-174611 330) |
4274 (-174611 330) |
4275 (854513 138) |
4275 (854513 138) |
4276 (-236364091 2730) |
4276 (-236364091 2730) |
4277 (8553103 6) |
4277 (8553103 6) |
4278 (-23749461029 870) |
4278 (-23749461029 870) |
4279 (8615841276005 14322) |
4279 (8615841276005 14322) |
4280 (-7709321041217 510) |
4280 (-7709321041217 510) |
4281 (2577687858367 6) |
4281 (2577687858367 6) |
4282 (-26315271553053477373 1919190) |
4282 (-26315271553053477373 1919190) |
4283 (2929993913841559 6) |
4283 (2929993913841559 6) |
4284 (-261082718496449122051 13530) |
4284 (-261082718496449122051 13530) |
4285 ). |
4285 ). |
4286 |
4286 |
4287 self even ifTrue:[ |
4287 self even ifTrue:[ |
4288 self == 0 ifTrue:[^1]. |
4288 self == 0 ifTrue:[^1]. |
4289 p := table at:(self / 2). |
4289 p := table at:(self / 2). |
4290 ^ Fraction numerator:(p first) denominator:(p second). |
4290 ^ Fraction numerator:(p first) denominator:(p second). |
4291 ]. |
4291 ]. |
4292 self == 1 ifTrue:[ ^ (1 / 2) ]. |
4292 self == 1 ifTrue:[ ^ (1 / 2) ]. |
4293 ^ 0. |
4293 ^ 0. |
4294 |
4294 |
4295 " |
4295 " |
4425 to print a number/and for conversion to a LargeInteger. |
4425 to print a number/and for conversion to a LargeInteger. |
4426 Implemented that way, to allow for tiny systems (PDAs) without a Float class |
4426 Implemented that way, to allow for tiny systems (PDAs) without a Float class |
4427 (i.e. without log)." |
4427 (i.e. without log)." |
4428 |
4428 |
4429 self > 0 ifTrue:[ |
4429 self > 0 ifTrue:[ |
4430 self < 10000 ifTrue:[ |
4430 self < 10000 ifTrue:[ |
4431 self < 10 ifTrue:[^ 0]. |
4431 self < 10 ifTrue:[^ 0]. |
4432 self < 100 ifTrue:[^ 1]. |
4432 self < 100 ifTrue:[^ 1]. |
4433 self < 1000 ifTrue:[^ 2]. |
4433 self < 1000 ifTrue:[^ 2]. |
4434 ^ 3 |
4434 ^ 3 |
4435 ]. |
4435 ]. |
4436 self < 100000000 ifTrue:[ |
4436 self < 100000000 ifTrue:[ |
4437 self < 100000 ifTrue:[^ 4]. |
4437 self < 100000 ifTrue:[^ 4]. |
4438 self < 1000000 ifTrue:[^ 5]. |
4438 self < 1000000 ifTrue:[^ 5]. |
4439 self < 10000000 ifTrue:[^ 6]. |
4439 self < 10000000 ifTrue:[^ 6]. |
4440 ^ 7 |
4440 ^ 7 |
4441 ]. |
4441 ]. |
4442 self < 1000000000 ifTrue:[^ 8]. |
4442 self < 1000000000 ifTrue:[^ 8]. |
4443 |
4443 |
4444 SmallInteger maxBytes == 4 ifTrue:[ |
4444 SmallInteger maxBytes == 4 ifTrue:[ |
4445 "/ on a 32 bit machine, SmallInt cannot be larger |
4445 "/ on a 32 bit machine, SmallInt cannot be larger |
4446 ^ 9 |
4446 ^ 9 |
4447 ] ifFalse:[ |
4447 ] ifFalse:[ |
4448 "/ 64 bit machine |
4448 "/ 64 bit machine |
4449 self < 100000000000000 ifTrue:[ |
4449 self < 100000000000000 ifTrue:[ |
4450 self < 10000000000 ifTrue:[^ 9]. |
4450 self < 10000000000 ifTrue:[^ 9]. |
4451 self < 100000000000 ifTrue:[^ 10]. |
4451 self < 100000000000 ifTrue:[^ 10]. |
4452 self < 1000000000000 ifTrue:[^ 11]. |
4452 self < 1000000000000 ifTrue:[^ 11]. |
4453 self < 10000000000000 ifTrue:[^ 12]. |
4453 self < 10000000000000 ifTrue:[^ 12]. |
4454 ^ 13 |
4454 ^ 13 |
4455 ]. |
4455 ]. |
4456 self < 1000000000000000 ifTrue:[^ 14]. |
4456 self < 1000000000000000 ifTrue:[^ 14]. |
4457 self < 10000000000000000 ifTrue:[^ 15]. |
4457 self < 10000000000000000 ifTrue:[^ 15]. |
4458 self < 100000000000000000 ifTrue:[^ 16]. |
4458 self < 100000000000000000 ifTrue:[^ 16]. |
4459 self < 1000000000000000000 ifTrue:[^ 17]. |
4459 self < 1000000000000000000 ifTrue:[^ 17]. |
4460 ^ 18. |
4460 ^ 18. |
4461 ]. |
4461 ]. |
4462 ]. |
4462 ]. |
4463 |
4463 |
4464 ^ self class |
4464 ^ self class |
4465 raise:(self = 0 ifTrue:[#infiniteResultSignal] ifFalse:[#domainErrorSignal]) |
4465 raise:(self = 0 ifTrue:[#infiniteResultSignal] ifFalse:[#domainErrorSignal]) |
4466 receiver:self |
4466 receiver:self |
4467 selector:#integerLog10 |
4467 selector:#integerLog10 |
4468 arguments:#() |
4468 arguments:#() |
4469 errorString:'bad receiver in log10 (not strictly positive)' |
4469 errorString:'bad receiver in log10 (not strictly positive)' |
4470 |
4470 |
4471 " |
4471 " |
4472 99 integerLog10 |
4472 99 integerLog10 |
4473 100 integerLog10 |
4473 100 integerLog10 |
4474 101 integerLog10 |
4474 101 integerLog10 |
4869 char buffer[256]; |
4869 char buffer[256]; |
4870 OBJ s; |
4870 OBJ s; |
4871 int len; |
4871 int len; |
4872 |
4872 |
4873 if (__isStringLike(formatString)) { |
4873 if (__isStringLike(formatString)) { |
4874 /* |
4874 /* |
4875 * actually only needed on sparc: since thisContext is |
4875 * actually only needed on sparc: since thisContext is |
4876 * in a global register, which gets destroyed by printf, |
4876 * in a global register, which gets destroyed by printf, |
4877 * manually save it here - very stupid ... |
4877 * manually save it here - very stupid ... |
4878 */ |
4878 */ |
4879 __BEGIN_PROTECT_REGISTERS__ |
4879 __BEGIN_PROTECT_REGISTERS__ |
4880 |
4880 |
4881 len = snprintf(buffer, sizeof(buffer), __stringVal(formatString), __intVal(self)); |
4881 len = snprintf(buffer, sizeof(buffer), __stringVal(formatString), __intVal(self)); |
4882 |
4882 |
4883 __END_PROTECT_REGISTERS__ |
4883 __END_PROTECT_REGISTERS__ |
4884 |
4884 |
4885 if (len < 0) goto fail; |
4885 if (len < 0) goto fail; |
4886 if (len >= sizeof(buffer)) goto fail; |
4886 if (len >= sizeof(buffer)) goto fail; |
4887 |
4887 |
4888 s = __MKSTRING_L(buffer, len); |
4888 s = __MKSTRING_L(buffer, len); |
4889 if (s != nil) { |
4889 if (s != nil) { |
4890 RETURN (s); |
4890 RETURN (s); |
4891 } |
4891 } |
4892 } |
4892 } |
4893 fail: ; |
4893 fail: ; |
4894 #endif /* not __SCHTEAM__ */ |
4894 #endif /* not __SCHTEAM__ */ |
4895 %}. |
4895 %}. |
4896 ^ super printfPrintString:formatString |
4896 ^ super printfPrintString:formatString |
4897 |
4897 |
4898 " |
4898 " |
4899 123 printfPrintString:'%%d -> %d' |
4899 123 printfPrintString:'%%d -> %d' |
4900 123 printfPrintString:'%%6d -> %6d' |
4900 123 printfPrintString:'%%6d -> %6d' |
4901 123 printfPrintString:'%%x -> %x' |
4901 123 printfPrintString:'%%x -> %x' |
4902 123 printfPrintString:'%%4x -> %4x' |
4902 123 printfPrintString:'%%4x -> %4x' |
4903 123 printfPrintString:'%%04x -> %04x' |
4903 123 printfPrintString:'%%04x -> %04x' |
4904 " |
4904 " |
4905 |
4905 |
4906 "Modified: / 03-07-2017 / 15:07:37 / cg" |
4906 "Modified: / 03-07-2017 / 15:07:37 / cg" |
4907 ! ! |
4907 ! ! |
4908 |
4908 |