X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=darray.c;h=890de4522a6224a7d299da93a69852e214315153;hb=a75155efc2ed07c1907ef017360bd719a47f9c06;hp=3359ed305466da861d6f3815097aeb30bcc2b267;hpb=1413ae2197d87e87571c9d8d6fc9f20f691fcea3;p=SXSI%2FXMLTree.git

diff --git a/darray.c b/darray.c
index 3359ed3..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;
@@ -46,6 +47,27 @@ int setbit(pb *B, int i,int x)
   return x;
 }
 
+int setbit_zero(pb *B, int i)
+{
+  int j,l;
+  j = i >> logD;
+  l = i & (D-1);
+  B[j] &= (~(1<<(D-1-l)));
+  return 0;
+}
+
+int setbit_one(pb *B, int i)
+{
+  int j,l;
+  j = i >> logD;
+  l = i & (D-1);
+  B[j] |= (1<<(D-1-l));
+  return 1;
+
+}
+
+
+
 int setbits(pb *B, int i, int d, int x)
 {
   int j;
@@ -113,49 +135,6 @@ static const unsigned int popCount[] = {
 
 static int selecttbl[8*256];
 
-unsigned int popcount(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;
-}
-
-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;
@@ -383,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++);
@@ -585,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;
@@ -610,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;
@@ -667,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;