.

[SXSI/XMLTree.git] / libcds / src / static_bitsequence / sdarray.cpp

diff --git a/libcds/src/static_bitsequence/sdarray.cpp b/libcds/src/static_bitsequence/sdarray.cpp
index 2294a0c..258162a 100644 (file)
--- a/libcds/src/static_bitsequence/sdarray.cpp
+++ b/libcds/src/static_bitsequence/sdarray.cpp
@@ -157,6 +157,34 @@ static const unsigned int _popCount[] = {
   3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
   4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
 };
+static inline unsigned int
+_fast_popcount2(int x)
+{
+    uint m1 = 0x55555555;
+    uint m2 = 0x33333333;
+    uint m4 = 0x0f0f0f0f;
+    x -= (x >> 1) & m1;
+    x = (x & m2) + ((x >> 2) & m2);
+    x = (x + (x >> 4)) & m4;
+    x += x >>  8;
+    return (x + (x >> 16)) & 0x3f;
+}
+
+static inline unsigned int
+_fast_popcount3(int x) 
+{
+  uint m1 = 0x55555555;
+  uint m2 = 0xc30c30c3;
+  x -= (x >> 1) & m1;
+  x = (x & m2) + ((x >> 2) & m2) + ((x >> 4) & m2);
+  x += x >> 6;
+  return  (x + (x >> 12) + (x >> 24)) & 0x3f;
+}
+
+static inline unsigned int
+_fast_popcount(int x) {
+  return _popCount[x];
+}
 
 static unsigned int __selecttbl[8*256];
 static int built = 0;
@@ -395,11 +423,13 @@ int selectd2_select(selectd2 *select, int i,int f) {
 
     if (f == 1) {
       rr = p & (8-1);
-      r -= _popCount[*q >> (8-1-rr)];
+      //r -= _popCount[*q >> (8-1-rr)];
+      r -= _fast_popcount(*q >> (8-1-rr));
       //p = p - rr;
 
       while (1) {
-        rr = _popCount[*q];
+        //rr = _popCount[*q];
+       rr = _fast_popcount(*q);
         if (r + rr >= i) break;
         r += rr;
         //p += 8;
@@ -410,11 +440,13 @@ int selectd2_select(selectd2 *select, int i,int f) {
     }
     else {
       rr = p & (8-1);
-      r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
+      //r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
+      r -= _fast_popcount((*q ^ 0xff) >> (8-1-rr));
       //p = p - rr;
 
       while (1) {
-        rr = _popCount[*q ^ 0xff];
+        //rr = _popCount[*q ^ 0xff];
+       rr = _fast_popcount(*q ^ 0xff);
         if (r + rr >= i) break;
         r += rr;
         //p += 8;
@@ -471,11 +503,13 @@ int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
 
     if (f == 1) {
       rr = p & (8-1);
-      r -= _popCount[*q >> (8-1-rr)];
+      //r -= _popCount[*q >> (8-1-rr)];
+      r -= _fast_popcount(*q >> (8-1-rr));
       //p = p - rr;
 
       while (1) {
-        rr = _popCount[*q];
+        //rr = _popCount[*q];
+       rr = _fast_popcount(*q);
         if (r + rr >= i) break;
         r += rr;
         //p += 8;
@@ -487,7 +521,8 @@ int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
       if ((i>>logL) == ((i+1)>>logL)) {
         i++;
         while (1) {
-          rr = _popCount[*q];
+          //rr = _popCount[*q];
+         r = _fast_popcount(*q);
           if (r + rr >= i) break;
           r += rr;
           q++;
@@ -502,11 +537,13 @@ int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
     }
     else {
       rr = p & (8-1);
-      r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
+      //r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
+      r -= _fast_popcount((*q ^ 0xff) >> (8-1-rr));
       //p = p - rr;
 
       while (1) {
-        rr = _popCount[*q ^ 0xff];
+        //rr = _popCount[*q ^ 0xff];
+       rr = _fast_popcount(*q ^ 0xff);
         if (r + rr >= i) break;
         r += rr;
         //p += 8;
@@ -518,7 +555,8 @@ int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
       if ((i>>logL) == ((i+1)>>logL)) {
         i++;
         while (1) {
-          rr = _popCount[*q ^ 0xff];
+          //rr = _popCount[*q ^ 0xff];
+         rr = _fast_popcount(*q ^ 0xff);
           if (r + rr >= i) break;
           r += rr;
           q++;