vm/bitwise_hacks.hpp

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