utils.h

   1 #ifndef UTILS_H_
   2 #define UTILS_H_
   3
   4 #ifdef HAS_NATIVE_POPCOUNT
   5 static inline unsigned int popcount(pb n){
   6   asm ("popcnt %1, %0" : "=r" (n) : "0" (n));
   7   return n;
   8 }
   9
  10 static inline unsigned int popcount8(pb n) {
  11   return popcount(n & 0xff);
  12 }
  13
  14 #else
  15
  16 static unsigned int popcount8(pb x)
  17 {
  18   dword r;
  19   r = x;
  20   r = ((r & 0xaa)>>1) + (r & 0x55);
  21   r = ((r & 0xcc)>>2) + (r & 0x33);
  22   r = ((r>>4) + r) & 0x0f;
  23   return r;
  24 }
  25
  26 static inline unsigned int
  27 popcount(pb x)
  28 {
  29   uint m1 = 0x55555555;
  30   uint m2 = 0xc30c30c3;
  31   x -= (x >> 1) & m1;
  32   x = (x & m2) + ((x >> 2) & m2) + ((x >> 4) & m2);
  33   x += x >> 6;
  34   return  (x + (x >> 12) + (x >> 24)) & 0x3f;
  35 }
  36
  37 #endif
  38
  39 #endif