bp-utils.h

   1 #ifndef BP_UTILS_H_
   2 #define BP_UTILS_H_
   3
   4 #ifdef __cplusplus
   5
   6 extern "C" {
   7 #endif
   8
   9 #define logD 5
  10 #define D (1<<logD)
  11
  12 #define logR 16
  13 #define R1 (1<<logR)
  14 #define logRR 10
  15 //#define logRR 8
  16 #define RR (1<<logRR)
  17 #define logRRR 7
  18 #define RRR (1<<logRRR)
  19
  20
  21 #include <stdlib.h>
  22
  23 #ifdef __GNUC__
  24 #define UNUSED __attribute__((unused))
  25 #else
  26 #define UNUSED
  27 #endif
  28
  29 #ifdef HAS_NATIVE_POPCOUNT
  30 static inline UNUSED unsigned int popcount(unsigned int n){
  31   asm ("popcnt %1, %0" : "=r" (n) : "0" (n));
  32   return n;
  33 }
  34
  35 static inline UNUSED unsigned int popcount8(unsigned int n) {
  36   return popcount(n & 0xff);
  37 }
  38
  39 #else
  40 #ifdef HAS_POPCOUNT_TABLE
  41
  42 extern unsigned char popCount[256];
  43
  44 static UNUSED unsigned int popcount8(unsigned int x)
  45 {
  46   return (unsigned int) popCount[x & 0xff];
  47 }
  48
  49 static UNUSED unsigned int popcount(unsigned int x)
  50 {
  51   return popcount8(x) +
  52     popcount8((x >> 8)) +
  53     popcount8((x >> 16)) +
  54     popcount8((x >> 24));
  55 }
  56
  57
  58 #else
  59 static UNUSED unsigned int popcount8(unsigned int x)
  60 {
  61   unsigned int r;
  62   r = x;
  63   r = ((r & 0xaa)>>1) + (r & 0x55);
  64   r = ((r & 0xcc)>>2) + (r & 0x33);
  65   r = ((r>>4) + r) & 0x0f;
  66   return r;
  67 }
  68
  69 static inline UNUSED unsigned int popcount(unsigned int x)
  70 {
  71   unsigned int m1 = 0x55555555;
  72   unsigned int m2 = 0xc30c30c3;
  73   x -= (x >> 1) & m1;
  74   x = (x & m2) + ((x >> 2) & m2) + ((x >> 4) & m2);
  75   x += x >> 6;
  76   return  (x + (x >> 12) + (x >> 24)) & 0x3f;
  77 }
  78
  79 #endif
  80 #endif
  81
  82
  83 void * bp_malloc(size_t);
  84
  85 #define bp_xmalloc(p, n) p = (__typeof__(p)) bp_malloc((n)*sizeof(*p))
  86
  87
  88
  89 void bp_free(void *);
  90
  91 size_t bp_get_alloc_stats(void);
  92
  93 void bp_reset_alloc_states(void);
  94
  95 int bp_setbit(unsigned int *B, int i,int x);
  96
  97 int bp_setbits(unsigned int *B, int i, int d, int x);
  98
  99 static inline int bp_getbit(unsigned int *B, int i)
 100 {
 101   int j = i >> logD;
 102   int l = i & (D-1);
 103   return (B[j] >> (D-1-l)) & 1;
 104 }
 105
 106 #ifdef __cplusplus
 107  }
 108 #endif
 109
 110 #endif