- Implement popcount in ASM if available

[SXSI/XMLTree.git] / darray.c

diff --git a/darray.c b/darray.c
index 780b967..890de45 100644 (file)
--- a/darray.c
+++ b/darray.c
@@ -1,6 +1,7 @@
 #include <stdio.h>\r
 #include <stdlib.h>\r
 #include "darray.h"\r
+#include "utils.h"\r
 \r
 //typedef unsigned char byte;\r
 //typedef unsigned short word;\r
@@ -134,61 +135,6 @@ static const unsigned int popCount[] = {
 \r
 static int selecttbl[8*256];\r
 \r
-unsigned int popcount_old(pb x)\r
-{\r
-  pb r;\r
-#if 0\r
-  r = x;\r
-  r = r - ((r>>1) & 0x77777777) - ((r>>2) & 0x33333333) - ((r>>3) & 0x11111111);\r
-  r = ((r + (r>>4)) & 0x0f0f0f0f) % 0xff;\r
-#elif 1\r
-  r = x;\r
-  r = ((r & 0xaaaaaaaa)>>1) + (r & 0x55555555);\r
-  r = ((r & 0xcccccccc)>>2) + (r & 0x33333333);\r
-  //r = ((r & 0xf0f0f0f0)>>4) + (r & 0x0f0f0f0f);\r
-  r = ((r>>4) + r) & 0x0f0f0f0f;\r
-  //r = ((r & 0xff00ff00)>>8) + (r & 0x00ff00ff);\r
-  r = (r>>8) + r;\r
-  //r = ((r & 0xffff0000)>>16) + (r & 0x0000ffff);\r
-  r = ((r>>16) + r) & 63;\r
-#else\r
-  r = popCount[x & 0xff];\r
-  x >>= 8;\r
-  r += popCount[x & 0xff];\r
-  x >>= 8;\r
-  r += popCount[x & 0xff];\r
-  x >>= 8;\r
-  r += popCount[x & 0xff];\r
-#endif\r
-  return r;\r
-}\r
-\r
-inline unsigned int\r
-popcount(pb x) \r
-{\r
-  uint m1 = 0x55555555;\r
-  uint m2 = 0xc30c30c3;\r
-  x -= (x >> 1) & m1;\r
-  x = (x & m2) + ((x >> 2) & m2) + ((x >> 4) & m2);\r
-  x += x >> 6;\r
-  return  (x + (x >> 12) + (x >> 24)) & 0x3f;\r
-}\r
-\r
-\r
-unsigned int popcount8(pb x)\r
-{\r
-  dword r;\r
-#if 1\r
-  r = x;\r
-  r = ((r & 0xaa)>>1) + (r & 0x55);\r
-  r = ((r & 0xcc)>>2) + (r & 0x33);\r
-  r = ((r>>4) + r) & 0x0f;\r
-#else\r
-  r = popCount[x & 0xff];\r
-#endif\r
-  return r;\r
-}\r
-\r
 void make_selecttbl(void)\r
 {\r
   int i,x,r;\r
@@ -416,17 +362,19 @@ int darray_rank0(darray *da, int i)
 \r
 int darray_rank(darray *da, int i)\r
 {\r
-  int r,j;\r
+  int r,j,i_rr, i_rrr;\r
   pb *p;\r
+  i_rr = i >> logRR;\r
+  i_rrr = i >> logRRR;\r
+  r = da->rl[i>>logR] + da->rm[i_rr];\r
 \r
-  r = da->rl[i>>logR] + da->rm[i>>logRR];\r
-  j = (i>>logRRR) & (RR/RRR-1);\r
+  j = (i_rrr) & (RR/RRR-1);\r
   while (j > 0) {\r
-    r += da->rs[((i>>logRR)<<(logRR-logRRR))+j-1];\r
+    r += da->rs[((i_rr)<<(logRR-logRRR))+j-1];\r
     j--;\r
   }\r
 \r
-  p = da->buf + ((i>>logRRR)<<(logRRR-logD));\r
+  p = da->buf + ((i_rrr)<<(logRRR-logD));\r
   j = i & (RRR-1);\r
   while (j >= D) {\r
     r += popcount(*p++);\r
@@ -618,8 +566,8 @@ int darray_select(darray *da, int i,int f)
       x = *q;\r
       while (1) {\r
        //rr = popcount(x >> (D-8));\r
-       rr = popCount[x >> (D-8)];\r
-       //rr = popcount8(x >> (D-8));\r
+       //rr = popcount(x >> (D-8));\r
+       rr = popcount8(x >> (D-8));\r
        if (r + rr >= i) break;\r
        r += rr;\r
        p += 8;\r
@@ -643,8 +591,8 @@ int darray_select(darray *da, int i,int f)
 \r
       while (1) {\r
        //rr = popcount(x >> (D-8));\r
-       rr = popCount[x >> (D-8)];\r
-       //rr = popcount8(x >> (D-8));\r
+       //rr = popCount[x >> (D-8)];\r
+       rr = popcount8(x >> (D-8));\r
        if (r + rr >= i) break;\r
        r += rr;\r
        p += 8;\r
@@ -700,8 +648,8 @@ int darray_pat_select(darray *da, int i, pb (*getpat)(pb *))
     x = getpat(q);\r
     while (1) {\r
       //rr = popcount(x >> (D-8));\r
-      rr = popCount[x >> (D-8)];\r
-      //rr = popcount8(x >> (D-8));\r
+      //rr = popCount[x >> (D-8)];\r
+      rr = popcount8(x >> (D-8));\r
       if (r + rr >= i) break;\r
       r += rr;\r
       p += 8;\r