audio.engine.test: cleanup using

[factor.git] / vm / bitwise_hacks.hpp

diff --git a/vm/bitwise_hacks.hpp b/vm/bitwise_hacks.hpp
index dc685bb28c1d6ac52808c187b48c6ec1fc96e70d..ed338dd3039794708a4a9b8ebb1f1f3c1759dbe0 100644 (file)
--- a/vm/bitwise_hacks.hpp
+++ b/vm/bitwise_hacks.hpp
@@ -1,67 +1,97 @@
-namespace factor
-{
+namespace factor {
 
-/* These algorithms were snarfed from various places. I did not come up with them myself */
+inline cell log2(cell x) {
+  cell n;
+#if defined(FACTOR_X86)
+#if defined(_MSC_VER)
+  _BitScanReverse((unsigned long*)&n, x);
+#else
+  asm("bsr %1, %0;" : "=r"(n) : "r"(x));
+#endif
 
-inline cell popcount(u64 x)
-{
-       u64 k1 = 0x5555555555555555ll;
-       u64 k2 = 0x3333333333333333ll;
-       u64 k4 = 0x0f0f0f0f0f0f0f0fll;
-       u64 kf = 0x0101010101010101ll;
-       x =  x       - ((x >> 1)  & k1); // put count of each 2 bits into those 2 bits
-       x = (x & k2) + ((x >> 2)  & k2); // put count of each 4 bits into those 4 bits
-       x = (x       +  (x >> 4)) & k4 ; // put count of each 8 bits into those 8 bits
-       x = (x * kf) >> 56; // returns 8 most significant bits of x + (x<<8) + (x<<16) + (x<<24) + ...
+#elif defined(FACTOR_AMD64)
+#if defined(_MSC_VER)
+  n = 0;
+  _BitScanReverse64((unsigned long*)&n, x);
+#else
+  asm("bsr %1, %0;" : "=r"(n) : "r"(x));
+#endif
 
-       return (cell)x;
-}
+#elif defined(FACTOR_ARM)
+#if defined(_MSC_VER)
+  _BitScanReverse((unsigned long*)&n, x);
+#else
+  n = (31 - __builtin_clz(x));
+#endif
 
-inline cell log2(u64 x)
-{
-#ifdef FACTOR_AMD64
-       cell n;
-       asm ("bsr %1, %0;":"=r"(n):"r"((cell)x));
+#elif defined(FACTOR_ARM64)
+#if defined(_MSC_VER)
+  n = 0;
+  _BitScanReverse64((unsigned long*)&n, x);
 #else
-       cell n = 0;
-       if (x >= (u64)1 << 32) { x >>= 32; n += 32; }
-       if (x >= (u64)1 << 16) { x >>= 16; n += 16; }
-       if (x >= (u64)1 <<  8) { x >>=  8; n +=  8; }
-       if (x >= (u64)1 <<  4) { x >>=  4; n +=  4; }
-       if (x >= (u64)1 <<  2) { x >>=  2; n +=  2; }
-       if (x >= (u64)1 <<  1) {           n +=  1; }
+  n = (63 - __builtin_clzll(x));
 #endif
-       return n;
-}
 
-inline cell log2(u16 x)
-{
-#if defined(FACTOR_X86) || defined(FACTOR_AMD64)
-       cell n;
-       asm ("bsr %1, %0;":"=r"(n):"r"((cell)x));
+#elif defined(FACTOR_PPC32)
+#if defined(__GNUC__)
+  n = (31 - __builtin_clz(x));
 #else
-       cell n = 0;
-       if (x >= 1 << 8) { x >>=  8; n += 8; }
-       if (x >= 1 << 4) { x >>=  4; n += 4; }
-       if (x >= 1 << 2) { x >>=  2; n += 2; }
-       if (x >= 1 << 1) {           n += 1; }
+#error Unsupported compiler
+#endif
+
+#elif defined(FACTOR_PPC64)
+#if defined(__GNUC__)
+  n = (63 - __builtin_clzll(x));
+#else
+#error Unsupported compiler
 #endif
-       return n;
-}
 
-inline cell rightmost_clear_bit(u64 x)
-{
-       return log2(~x & (x + 1));
+#else
+#error Unsupported CPU
+#endif
+  return n;
 }
 
-inline cell rightmost_set_bit(u64 x)
-{
-       return log2(x & -x);
+inline cell rightmost_clear_bit(cell x) { return log2(~x & (x + 1)); }
+
+inline cell rightmost_set_bit(cell x) { return log2(x & (~x + 1)); }
+
+inline cell popcount(cell x) {
+#if defined(__GNUC__)
+#ifdef FACTOR_64
+  return __builtin_popcountll(x);
+#else
+  return __builtin_popcount(x);
+#endif
+#else
+#ifdef FACTOR_64
+  uint64_t k1 = 0x5555555555555555ll;
+  uint64_t k2 = 0x3333333333333333ll;
+  uint64_t k4 = 0x0f0f0f0f0f0f0f0fll;
+  uint64_t kf = 0x0101010101010101ll;
+  cell ks = 56;
+#else
+  uint32_t k1 = 0x55555555;
+  uint32_t k2 = 0x33333333;
+  uint32_t k4 = 0xf0f0f0f;
+  uint32_t kf = 0x1010101;
+  cell ks = 24;
+#endif
+
+  x = x - ((x >> 1) & k1);         // put count of each 2 bits into those 2 bits
+  x = (x & k2) + ((x >> 2) & k2);  // put count of each 4 bits into those 4 bits
+  x = (x + (x >> 4)) & k4;         // put count of each 8 bits into those 8 bits
+  x = (x * kf) >> ks;  // returns 8 most significant bits of x + (x<<8) +
+                       // (x<<16) + (x<<24) + ...
+
+  return x;
+#endif
 }
 
-inline cell rightmost_set_bit(u16 x)
-{
-       return log2((u16)(x & -x));
+inline bool bitmap_p(uint8_t* bitmap, cell index) {
+  cell byte = index >> 3;
+  cell bit = index & 7;
+  return (bitmap[byte] & (1 << bit)) != 0;
 }
 
 }