vm/bitwise_hacks.hpp

   1 namespace factor
   2 {
   3
   4 /* These algorithms were snarfed from various places. I did not come up with them myself */
   5
   6 inline cell popcount(u64 x)
   7 {
   8         u64 k1 = 0x5555555555555555ll;
   9         u64 k2 = 0x3333333333333333ll;
  10         u64 k4 = 0x0f0f0f0f0f0f0f0fll;
  11         u64 kf = 0x0101010101010101ll;
  12         x =  x       - ((x >> 1)  & k1); // put count of each 2 bits into those 2 bits
  13         x = (x & k2) + ((x >> 2)  & k2); // put count of each 4 bits into those 4 bits
  14         x = (x       +  (x >> 4)) & k4 ; // put count of each 8 bits into those 8 bits
  15         x = (x * kf) >> 56; // returns 8 most significant bits of x + (x<<8) + (x<<16) + (x<<24) + ...
  16
  17         return (cell)x;
  18 }
  19
  20 inline cell log2(u64 x)
  21 {
  22 #ifdef FACTOR_AMD64
  23         cell n;
  24         asm ("bsr %1, %0;":"=r"(n):"r"((cell)x));
  25 #else
  26         cell n = 0;
  27         if (x >= (u64)1 << 32) { x >>= 32; n += 32; }
  28         if (x >= (u64)1 << 16) { x >>= 16; n += 16; }
  29         if (x >= (u64)1 <<  8) { x >>=  8; n +=  8; }
  30         if (x >= (u64)1 <<  4) { x >>=  4; n +=  4; }
  31         if (x >= (u64)1 <<  2) { x >>=  2; n +=  2; }
  32         if (x >= (u64)1 <<  1) {           n +=  1; }
  33 #endif
  34         return n;
  35 }
  36
  37 inline cell log2(u16 x)
  38 {
  39 #if defined(FACTOR_X86) || defined(FACTOR_AMD64)
  40         cell n;
  41         asm ("bsr %1, %0;":"=r"(n):"r"((cell)x));
  42 #else
  43         cell n = 0;
  44         if (x >= 1 << 8) { x >>=  8; n += 8; }
  45         if (x >= 1 << 4) { x >>=  4; n += 4; }
  46         if (x >= 1 << 2) { x >>=  2; n += 2; }
  47         if (x >= 1 << 1) {           n += 1; }
  48 #endif
  49         return n;
  50 }
  51
  52 inline cell rightmost_clear_bit(u64 x)
  53 {
  54         return log2(~x & (x + 1));
  55 }
  56
  57 inline cell rightmost_set_bit(u64 x)
  58 {
  59         return log2(x & -x);
  60 }
  61
  62 inline cell rightmost_set_bit(u16 x)
  63 {
  64         return log2((u16)(x & -x));
  65 }
  66
  67 }