X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=src%2Fstatic_bitsequence%2Fsdarray.cpp;h=d0a4066905d0d150f6b5972fff73362af7bd0168;hb=8357cb440cfd7678784a186f04ca7375b1fe669c;hp=4fe52b24b2e1b9f6129b8e9ac3f2f4f3c210f40c;hpb=3fd4bcef236556c7f3bff1d2be8d3f4206245501;p=SXSI%2Flibcds.git

diff --git a/src/static_bitsequence/sdarray.cpp b/src/static_bitsequence/sdarray.cpp
index 4fe52b2..d0a4066 100644
--- a/src/static_bitsequence/sdarray.cpp
+++ b/src/static_bitsequence/sdarray.cpp
@@ -1,5 +1,5 @@
-
 #include <sdarray.h>
+#include <stdint.h>
 using std::min;
 using std::max;
 #if 0
@@ -89,7 +89,7 @@ int __getbit(uint *B, int i) {
 }
 
 
-int __getbit2(uchar *B, int i) {
+static int __getbit2(uchar *B, int i) {
   int j,l;
 
   //j = i / D;
@@ -101,18 +101,22 @@ int __getbit2(uchar *B, int i) {
 
 
 #if 1
-uint __getbits(uint *B, int i, int d) {
+uint __getbits_aux(uint *B, int i, int d) {
   qword x,z;
-
+  int j = i;
   B += (i >> logD);
   i &= (D-1);
-  if (i+d <= 2*D) {
+  if (d==8 && (j & 7) == 0) {
+    i = (24 - i) >> 3;
+    x = (uint) (((unsigned char*) B)[i]);
+  } else if (i+d <= 2*D) {
     x = (((qword)B[0]) << D) + B[1];
     x <<= i;
     x >>= (D*2-1-d);
     x >>= 1;
   }
   else {
+    fprintf(stderr, "Warning: %d, %d\n", D, d);
     x = (((qword)B[0])<<D)+B[1];
     z = (x<<D)+B[2];
     x <<= i;
@@ -125,21 +129,37 @@ uint __getbits(uint *B, int i, int d) {
 
   return x;
 }
-#endif
-
-#if 0
-uint __getbits(uint *B, int i, int d) {
-  uint j,x;
 
-  x = 0;
-  for (j=0; j<d; j++) {
-    x <<= 1;
-    x += __getbit(B,i+j);
-  }
+static uint __getbits(uint *B, int i, int d)
+{
+  uint64_t x;
+  B += (i >> logD);
+  i &= (D-1);
+  x = ((uint64_t *) B)[0];
+  x = (x << 32)|(x >> 32);
+  x = (x << i) >> (2*D - d);
   return x;
 }
+
 #endif
 
+#if HAS_NATIVE_POPCOUNT
+static inline unsigned int popcount(unsigned int n){
+  asm ("popcnt %1, %0" : "=r" (n) : "0" (n));
+  return n;
+}
+
+// static inline unsigned int popcount8(unsigned int n) {
+//   return __builtin_popcount(n & 0xff);
+// }
+
+static inline unsigned int _fast_popcount(uchar x)
+{
+  return __builtin_popcount(x);
+}
+
+
+#else
 static const unsigned int _popCount[] = {
   0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
   1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
@@ -158,101 +178,37 @@ 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];
+  return _popCount[x & 0xff];
 }
+#endif
 
-static unsigned int __selecttbl[8*256];
+
+
+//static unsigned int __selecttbl[8*256];
 static int built = 0;
 
 void make___selecttbl(void) {
   if(built) return;
   built = 1;
   int i,x,r;
-  uint buf[1];
+  uint buf[1] = { 0 };
 
   for (x = 0; x < 256; x++) {
     __setbits(buf,0,8,x);
-    for (r=0; r<8; r++) __selecttbl[(r<<8)+x] = -1;
+//    for (r=0; r<8; r++) __selecttbl[(r<<8)+x] = -1;
     r = 0;
     for (i=0; i<8; i++) {
       if (__getbit(buf,i)) {
-        __selecttbl[(r<<8)+x] = i;
+	//      __selecttbl[(r<<8)+x] = i;
         r++;
       }
     }
   }
 }
 
-
-unsigned int __popCount(uint x) {
-  uint 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(uint x) {
-  uint 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;
-}
-
-
 int selectd2_save(selectd2 * s, FILE * fp) {
   uint wr = 0;
   wr += fwrite(&s->n,sizeof(uint),1,fp);
@@ -309,11 +265,11 @@ int selectd2_construct(selectd2 *select, int n, uchar *buf) {
   int i,m;
   int nl;
   int p,pp;
-  int il,is,ml,ms;
+  int il,is,ms,ml;
   int r;
   uint *s;
 
-  make___selecttbl();
+  //make___selecttbl();
 
   if (L/LLL == 0) {
     printf("ERROR: L=%d LLL=%d\n",L,LLL);
@@ -346,6 +302,7 @@ int selectd2_construct(selectd2 *select, int n, uchar *buf) {
   for(int k=0;k<nl+1;k++) select->p[k]=0;
   select->size += (nl+1)*sizeof(uint);
 
+  
   for (r = 0; r < 2; r++) {
     ml = ms = 0;
     for (il = 0; il < nl; il++) {
@@ -353,7 +310,8 @@ int selectd2_construct(selectd2 *select, int n, uchar *buf) {
       select->lp[il] = pp;
       i = min((il+1)*L-1,m-1);
       p = s[i];
-      //printf("%d ",p-pp);
+      // printf("p-pp=%d, LL=%d\n",p-pp, LL);
+
       if (p - pp >= LL) {
         if (r == 1) {
           for (is = 0; is < L; is++) {
@@ -361,6 +319,7 @@ int selectd2_construct(selectd2 *select, int n, uchar *buf) {
             select->sl[ml*L+is] = s[il*L+is];
           }
         }
+
         select->p[il] = -((ml<<logL)+1);
         ml++;
       }
@@ -375,6 +334,7 @@ int selectd2_construct(selectd2 *select, int n, uchar *buf) {
         ms++;
       }
     }
+
     if (r == 0) {
       select->sl = new uint[ml*L+1];
       for(int k=0;k<ml*L+1;k++) select->sl[k]=0;
@@ -391,21 +351,12 @@ int selectd2_construct(selectd2 *select, int n, uchar *buf) {
 }
 
 
-int selectd2_select(selectd2 *select, int i,int f) {
+int selectd2_select1(selectd2 *select, int i) {
   int p,r;
   int il;
   int rr;
   uchar *q;
-
-  if (i == 0) return -1;
-
-  #if 0
-  if (i > select->m) {
-    printf("ERROR: m=%d i=%d\n",select->m,i);
-    exit(1);
-  }
-  #endif
-
+  if (i <= 0) return -1;
   i--;
 
   il = select->p[i>>logL];
@@ -416,50 +367,75 @@ int selectd2_select(selectd2 *select, int i,int f) {
   }
   else {
     p = select->lp[i>>logL];
-    //p += select->ss[(il<<(logL-logLLL))+(i & (L-1))/LLL];
     p += select->ss[il+((i & (L-1))>>logLLL)];
     r = i - (i & (LLL-1));
 
     q = &(select->buf[p>>3]);
 
-    if (f == 1) {
-      rr = p & (8-1);
-      //r -= _popCount[*q >> (8-1-rr)];
-      r -= _fast_popcount(*q >> (8-1-rr));
-      //p = p - rr;
-
-      while (1) {
+    rr = p & (8-1);
+    r -= _fast_popcount(*q >> (8-1-rr));
+    
+    while (1) {
         //rr = _popCount[*q];
-	rr = _fast_popcount(*q);
-        if (r + rr >= i) break;
-        r += rr;
-        //p += 8;
-        q++;
-      }
-      p = (q - select->buf) << 3;
-      p += __selecttbl[((i-r-1)<<8)+(*q)];
+      rr = _fast_popcount(*q);
+      if (r + rr >= i) break;
+      r += rr;
+      //p += 8;
+      q++;
     }
-    else {
-      rr = p & (8-1);
-      //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 = _fast_popcount(*q ^ 0xff);
-        if (r + rr >= i) break;
-        r += rr;
-        //p += 8;
-        q++;
-      }
       p = (q - select->buf) << 3;
-      p += __selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
-    }
+      p += selecttbl[((i-r-1)<<8)+(*q)];
   }
   return p;
 }
 
+int selectd2_select0(selectd2 *select, int i) {
+  int p,r;
+  int il;
+  int rr;
+  uchar *q;
+
+  if (i <= 0) return -1;
+  i--;
+
+  il = select->p[i>>logL];
+  if (il < 0) {
+    il = -il-1;
+    return select->sl[il+(i & (L-1))];
+
+  } else {
+    p = select->lp[i>>logL];
+
+    p += select->ss[il+((i & (L-1))>>logLLL)];
+    r = i - (i & (LLL-1));
+
+    q = &(select->buf[p>>3]);
+
+    rr = p & 7;
+
+    uint masked_q = *q ^ 0xff;
+
+    r -= _fast_popcount(masked_q >> (7-rr));
+
+    for(;;) {
+      rr = _fast_popcount(masked_q);
+      if (rr >= i-r) {
+	p = (q - select->buf) << 3;
+	p += selecttbl[((i-r-1)<<8)+masked_q];
+	return p;
+      };
+      r += rr;
+      q++;
+      masked_q = *q ^ 0xff;
+    };
+  }
+}
+
+int selectd2_select(selectd2 *select, int i,int f) {
+  return f ? selectd2_select1(select, i) :
+    selectd2_select0(select, i);
+}
+
 
 int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
   int p,r,p2;
@@ -517,7 +493,7 @@ int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
         q++;
       }
       p = (q - select->buf) << 3;
-      p += __selecttbl[((i-r-1)<<8)+(*q)];
+      p += selecttbl[((i-r-1)<<8)+(*q)];
 
       if ((i>>logL) == ((i+1)>>logL)) {
         i++;
@@ -529,7 +505,7 @@ int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
           q++;
         }
         p2 = (q - select->buf) << 3;
-        p2 += __selecttbl[((i-r-1)<<8)+(*q)];
+        p2 += selecttbl[((i-r-1)<<8)+(*q)];
       }
       else {
         p2 = selectd2_select(select,i+2,f);
@@ -551,7 +527,7 @@ int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
         q++;
       }
       p = (q - select->buf) << 3;
-      p += __selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
+      p += selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
 
       if ((i>>logL) == ((i+1)>>logL)) {
         i++;
@@ -563,7 +539,7 @@ int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
           q++;
         }
         p2 = (q - select->buf) << 3;
-        p2 += __selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
+        p2 += selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
       }
       else {
         p2 = selectd2_select(select,i+2,f);
@@ -710,122 +686,139 @@ int selects3_select(selects3 *select, int i) {
   d = select->d;
 	/*if(select->lasti==(uint)i-1) {
 		while(!__getbit2(select->sd1->buf,++select->lasts));
-	} 
+	}
 	else {
 	  select->lasts = selectd2_select(select->sd1,i,1);
 	}
 	select->lasti = i;
 	//lasts3 = select; */
-	x = selectd2_select(select->sd1,i,1) - (i-1);
+	x = selectd2_select1(select->sd1,i) - (i-1);
   //x = (select->lasts-(i-1)) << d;
   x <<= d;
   x += __getbits(select->low,(i-1)*d,d);
   return x;
 }
 
+void pr_byte(FILE* fp, uchar b)
+{
+  uchar * buff = &b;
+  for(int i = 0; i < 8; i++){
+    fprintf(stderr, "%i", __getbit2(buff, i));
+  };
+}
 
 int selects3_selectnext(selects3 *select, int i) {
-	//return selects3_select(select,selects3_rank(select,i)+1);
+  //return selects3_select(select,selects3_rank(select,i)+1);
   int d,x,w,y;
   int r,j;
   int z,ii;
+  int xoffset;
   uint *q;
   d = select->d;
   q = select->low;
   ii = i>>d;
-  y = selectd2_select(select->sd0,ii,0)+1;
-	int k2=y-ii;
+  y = selectd2_select0(select->sd0,ii)+1;
+  int k2=y-ii;
   x = y - ii;
-	int x_orig = x;
+  int x_orig = x;
   j = i - (ii<<d);
   r = y & 7;
   y >>= 3;
   z = select->hi[y];
+  xoffset = x * d;
   while (1) {
     if (((z << r) & 0x80) == 0) {
-			if(x!=x_orig) k2++;
-			break;
-		}
-    w = __getbits(q,x*d,d);
+      k2 += (x!=x_orig);
+      break;
+    };
+
+    w = __getbits(q,xoffset,d);
     if (w >= j) {
       if (w == j) {
-				if(__getbit2(select->hi,(8*y+r))) k2++;
-				x++;
-				r++;
-			}
+	if (__getbit2(select->hi,((y << 3)+r)))  k2 ++;
+	x++;
+	r++;
+	xoffset += d;
+      };
       break;
-    }
+    };
+
     x++;
     r++;
-		if(__getbit2(select->hi,(8*y+r))) k2++;
+    xoffset += d;
+    if(__getbit2(select->hi,( (y << 3)+r))) k2++;
     if (r == 8) {
       r = 0;
       y++;
       z = select->hi[y];
     }
-  }
-	if(x==select->m)
-		return (uint)-1;
-	int c=8*y+r;
-	int fin=0;
-	for(int kk=0;kk<8-r;kk++) {
-		if(__getbit2(select->hi,c)) {
-			fin=1;
-			break;
-		}
-		c++;
-	}
-	if(!fin) {
-		int pp = c/8;
-		while(select->hi[pp]==0) {
-			pp++;
-			c+=8;
-		}
-		while(!__getbit2(select->hi,c)) c++;
-	}
-	c -= (k2);
-  return __getbits(q,x*d,d)+((c)<<d);
+  };
+
+  if(x==select->m) return (uint)-1;
+
+
+  int c = (y << 3)+r;
+
+  uint mask = ~(0xffu << (8*sizeof(uint) - 8));
+  uint tmp = (select->hi[y] << ((8*sizeof(uint) - 8)+r)) | mask;
+  uint c_incr = __builtin_clz(tmp);
+  c += (c_incr & 7);
+  if (c_incr == 8) {
+    c += (8-r);
+
+    uchar * pp = &(select->hi[c >> 3]);
+
+    while(*pp == 0) {
+      pp++;
+      c += 8;
+    };
+
+    c += __builtin_clz(*pp) - 24;
+
+  };
+  c -= k2;
+
+  return __getbits(q,xoffset,d)+((c)<<d);
 }
 
 int selects3_rank(selects3 *select, int i) {
   int d,x,w,y;
   int r,j;
   int z,ii;
+  int xoffset;
   uint *q;
 
   d = select->d;
   q = select->low;
 
-  ii = i>>d;
+  ii = i >> d;
 
-  y = selectd2_select(select->sd0,ii,0)+1;
-  //  selectd2_select2(select->sd0,ii,0,&y1,&y2);
-  //y1++;  y2++;
-  //printf("y %d y1 %d  %d\n",y,y1,y2-y1);
+  y = selectd2_select0(select->sd0, ii)+1;
 
   x = y - ii;
 
-  j = i - (ii<<d);
+  j = i - (ii << d);
 
   r = y & 7;
   y >>= 3;
   z = select->hi[y];
+  xoffset = x * d;
+
   while (1) {
-    if (((z << r) & 0x80) == 0) break;
-    w = __getbits(q,x*d,d);
-    if (w >= j) {
-      if (w == j) x++;
-      break;
-    }
+    if (((z << r) & 0x80) == 0) return x;
+
+    w = __getbits(q, xoffset, d);
+
+    if (w >= j) return x + (w == j);
+
     x++;
     r++;
+    xoffset += d;
     if (r == 8) {
       r = 0;
       y++;
       z = select->hi[y];
     }
   }
-
-	return x;
 }