vm/bitwise_hacks.hpp

   1 namespace factor {
   2
   3 inline cell log2(cell x) {
   4   cell n;
   5 #if defined(FACTOR_X86)
   6 #if defined(_MSC_VER)
   7   _BitScanReverse((unsigned long*)&n, x);
   8 #else
   9   asm("bsr %1, %0;" : "=r"(n) : "r"(x));
  10 #endif
  11
  12 #elif defined(FACTOR_AMD64)
  13 #if defined(_MSC_VER)
  14   n = 0;
  15   _BitScanReverse64((unsigned long*)&n, x);
  16 #else
  17   asm("bsr %1, %0;" : "=r"(n) : "r"(x));
  18 #endif
  19
  20 #elif defined(FACTOR_ARM)
  21 #if defined(_MSC_VER)
  22   _BitScanReverse((unsigned long*)&n, x);
  23 #else
  24   n = (31 - __builtin_clz(x));
  25 #endif
  26
  27 #elif defined(FACTOR_ARM64)
  28 #if defined(_MSC_VER)
  29   n = 0;
  30   _BitScanReverse64((unsigned long*)&n, x);
  31 #else
  32   n = (63 - __builtin_clzll(x));
  33 #endif
  34
  35 #elif defined(FACTOR_PPC32)
  36 #if defined(__GNUC__)
  37   n = (31 - __builtin_clz(x));
  38 #else
  39 #error Unsupported compiler
  40 #endif
  41
  42 #elif defined(FACTOR_PPC64)
  43 #if defined(__GNUC__)
  44   n = (63 - __builtin_clzll(x));
  45 #else
  46 #error Unsupported compiler
  47 #endif
  48
  49 #else
  50 #error Unsupported CPU
  51 #endif
  52   return n;
  53 }
  54
  55 inline cell rightmost_clear_bit(cell x) { return log2(~x & (x + 1)); }
  56
  57 inline cell rightmost_set_bit(cell x) { return log2(x & (~x + 1)); }
  58
  59 inline cell popcount(cell x) {
  60 #if defined(__GNUC__)
  61 #ifdef FACTOR_64
  62   return __builtin_popcountll(x);
  63 #else
  64   return __builtin_popcount(x);
  65 #endif
  66 #else
  67 #ifdef FACTOR_64
  68   uint64_t k1 = 0x5555555555555555ll;
  69   uint64_t k2 = 0x3333333333333333ll;
  70   uint64_t k4 = 0x0f0f0f0f0f0f0f0fll;
  71   uint64_t kf = 0x0101010101010101ll;
  72   cell ks = 56;
  73 #else
  74   uint32_t k1 = 0x55555555;
  75   uint32_t k2 = 0x33333333;
  76   uint32_t k4 = 0xf0f0f0f;
  77   uint32_t kf = 0x1010101;
  78   cell ks = 24;
  79 #endif
  80
  81   x = x - ((x >> 1) & k1);         // put count of each 2 bits into those 2 bits
  82   x = (x & k2) + ((x >> 2) & k2);  // put count of each 4 bits into those 4 bits
  83   x = (x + (x >> 4)) & k4;         // put count of each 8 bits into those 8 bits
  84   x = (x * kf) >> ks;  // returns 8 most significant bits of x + (x<<8) +
  85                        // (x<<16) + (x<<24) + ...
  86
  87   return x;
  88 #endif
  89 }
  90
  91 inline bool bitmap_p(uint8_t* bitmap, cell index) {
  92   cell byte = index >> 3;
  93   cell bit = index & 7;
  94   return (bitmap[byte] & (1 << bit)) != 0;
  95 }
  96
  97 }