X-Git-Url: http://git.nguyen.vg/gitweb/?p=SXSI%2Flibbp.git;a=blobdiff_plain;f=bp-darray.c;h=eecaccbe7a9ab8431c266090150f2240c3356e99;hp=c3c06a613239ca119cbb8816e4e42e2a1a7277a8;hb=HEAD;hpb=45ff7a2260f890f6ef6a7b56f654ffa1a057a7e7

diff --git a/bp-darray.c b/bp-darray.c
index c3c06a6..eecaccb 100644
--- a/bp-darray.c
+++ b/bp-darray.c
@@ -1,7 +1,6 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include "bp-darray.h"
-#include "bp-utils.h"
 
 #define PBS (sizeof(pb)*8)
 #define D (1<<logD)
@@ -57,13 +56,32 @@ static int getpattern(pb *B, int i, int k, pb pat)
   return x;
 }
 
-static int selecttbl[8*256];
+int selecttbl[8*256];
 static int selecttbl_init = 0;
+static void prbin(unsigned int x)
+{
+  int i;
+  //  for(i = 31; i >= 0; i--){
+  for (i = 0 ; i < 32; i ++) {
+    fprintf(stderr,"%.1u", (x >> i)&1);
+    if (i % 4 == 3)
+      fprintf(stderr, " ");
+  }
+
+}
+int clz(unsigned int x)
+{
+  if (x == 0)
+    return -1;
+  else
+    __builtin_clz(x);
+}
 
 static void make_selecttbl(void)
 {
   int i,x,r;
   pb buf[1];
+  unsigned int mask;
   if (selecttbl_init) return;
 
   selecttbl_init = 1;
@@ -74,11 +92,21 @@ static void make_selecttbl(void)
     r = 0;
     for (i=0; i<8; i++) {
       if (bp_getbit(buf,i)) {
+	//	fprintf(stderr, "Init: setting %i to %i (r= %i, x = %i)\n", (r<<8)+x, i, r, x);
 	selecttbl[(r<<8)+x] = i;
 	r++;
       }
     }
   }
+  /*
+  fprintf(stderr, "Select table:\n");
+  for (i = 0; i < 8 * 256; i++){
+    mask = i / 256 + 1;
+    x = __builtin_clz((i + (i << 8)));
+    prbin(i);
+    fprintf(stderr, " (%.4i): %08i, %08i\n", i, selecttbl[i], x);
+  };
+  */
 }
 
 
@@ -278,31 +306,6 @@ static int darray_rank0(darray *da, int i)
   return r;
 }
 
-int bp_darray_rank(darray *da, int i)
-{
-  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];
-
-  j = (i_rrr) & (RR/RRR-1);
-  while (j > 0) {
-    r += da->rs[((i_rr)<<(logRR-logRRR))+j-1];
-    j--;
-  }
-
-  p = da->buf + ((i_rrr)<<(logRRR-logD));
-  j = i & (RRR-1);
-  while (j >= D) {
-    r += popcount(*p++);
-    j -= D;
-  }
-  r += popcount(*p >> (D-1-j));
-
-  return r;
-}
-
 int bp_darray_select_bsearch(darray *da, int i, pb (*getpat)(pb *))
 {
   int j;
@@ -441,17 +444,11 @@ int bp_darray_select(darray *da, int i,int f)
   pb x;
   pb *q;
 
-  if (i == 0) return -1;
-
-  if (i > da->m) {
-    return -1;
-    //printf("ERROR: m=%d i=%d\n",da->m,i);
-    //exit(1);
-  }
+  if (i <= 0 || i > da->m) return -1;
 
   i--;
 
-  il = da->p[i>>logL];
+  il = da->p[ i >> logL ];
   if (il < 0) {
     il = -il-1;
     p = da->sl[(il<<logL)+(i & (L-1))];