X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=darray.c;h=890de4522a6224a7d299da93a69852e214315153;hb=e2c476850d5598f78c8584530563491a7effd632;hp=780b9673c0463f5a53a83dfdc3b835bfe6883400;hpb=44dc45dfa812b495fc4ef7dff7f69a6b89ee5128;p=SXSI%2FXMLTree.git

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