vm/bitwise_hacks.hpp

   1 namespace factor
   2 {
   3
   4 inline cell log2(cell x)
   5 {
   6         cell n;
   7 #if defined(FACTOR_X86) || defined(FACTOR_AMD64)
   8         asm ("bsr %1, %0;":"=r"(n):"r"(x));
   9 #elif defined(FACTOR_PPC)
  10         asm ("cntlzw %1, %0;":"=r"(n):"r"(x));
  11         n = (31 - n);
  12 #else
  13         #error Unsupported CPU
  14 #endif
  15         return n;
  16 }
  17
  18 inline cell rightmost_clear_bit(cell x)
  19 {
  20         return log2(~x & (x + 1));
  21 }
  22
  23 inline cell rightmost_set_bit(cell x)
  24 {
  25         return log2(x & -x);
  26 }
  27
  28 inline cell popcount(cell x)
  29 {
  30 #ifdef FACTOR_64
  31         u64 k1 = 0x5555555555555555ll;
  32         u64 k2 = 0x3333333333333333ll;
  33         u64 k4 = 0x0f0f0f0f0f0f0f0fll;
  34         u64 kf = 0x0101010101010101ll;
  35         cell ks = 56;
  36 #else
  37         u32 k1 = 0x55555555;
  38         u32 k2 = 0x33333333;
  39         u32 k4 = 0xf0f0f0f;
  40         u32 kf = 0x1010101;
  41         cell ks = 24;
  42 #endif
  43
  44         x =  x       - ((x >> 1)  & k1); // put count of each 2 bits into those 2 bits
  45         x = (x & k2) + ((x >> 2)  & k2); // put count of each 4 bits into those 4 bits
  46         x = (x       +  (x >> 4)) & k4 ; // put count of each 8 bits into those 8 bits
  47         x = (x * kf) >> ks; // returns 8 most significant bits of x + (x<<8) + (x<<16) + (x<<24) + ...
  48
  49         return x;
  50 }
  51
  52 }