#include <stdio.h>\r
#include <stdlib.h>\r
#include "bp-darray.h"\r
-#include "bp-utils.h"\r
\r
#define PBS (sizeof(pb)*8)\r
#define D (1<<logD)\r
return x;\r
}\r
\r
-static int selecttbl[8*256];\r
+int selecttbl[8*256];\r
static int selecttbl_init = 0;\r
+static void prbin(unsigned int x)\r
+{\r
+ int i;\r
+ // for(i = 31; i >= 0; i--){\r
+ for (i = 0 ; i < 32; i ++) {\r
+ fprintf(stderr,"%.1u", (x >> i)&1);\r
+ if (i % 4 == 3)\r
+ fprintf(stderr, " ");\r
+ }\r
+\r
+}\r
+int clz(unsigned int x)\r
+{\r
+ if (x == 0)\r
+ return -1;\r
+ else\r
+ __builtin_clz(x);\r
+}\r
\r
static void make_selecttbl(void)\r
{\r
int i,x,r;\r
pb buf[1];\r
+ unsigned int mask;\r
if (selecttbl_init) return;\r
\r
selecttbl_init = 1;\r
r = 0;\r
for (i=0; i<8; i++) {\r
if (bp_getbit(buf,i)) {\r
+ // fprintf(stderr, "Init: setting %i to %i (r= %i, x = %i)\n", (r<<8)+x, i, r, x);\r
selecttbl[(r<<8)+x] = i;\r
r++;\r
}\r
}\r
}\r
+ /*\r
+ fprintf(stderr, "Select table:\n");\r
+ for (i = 0; i < 8 * 256; i++){\r
+ mask = i / 256 + 1;\r
+ x = __builtin_clz((i + (i << 8)));\r
+ prbin(i);\r
+ fprintf(stderr, " (%.4i): %08i, %08i\n", i, selecttbl[i], x);\r
+ };\r
+ */\r
}\r
\r
\r
return r;\r
}\r
\r
-int bp_darray_rank(darray *da, int i)\r
-{\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
- j = (i_rrr) & (RR/RRR-1);\r
- while (j > 0) {\r
- r += da->rs[((i_rr)<<(logRR-logRRR))+j-1];\r
- j--;\r
- }\r
-\r
- p = da->buf + ((i_rrr)<<(logRRR-logD));\r
- j = i & (RRR-1);\r
- while (j >= D) {\r
- r += popcount(*p++);\r
- j -= D;\r
- }\r
- r += popcount(*p >> (D-1-j));\r
-\r
- return r;\r
-}\r
-\r
int bp_darray_select_bsearch(darray *da, int i, pb (*getpat)(pb *))\r
{\r
int j;\r
pb x;\r
pb *q;\r
\r
- if (i == 0) return -1;\r
-\r
- if (i > da->m) {\r
- return -1;\r
- //printf("ERROR: m=%d i=%d\n",da->m,i);\r
- //exit(1);\r
- }\r
+ if (i <= 0 || i > da->m) return -1;\r
\r
i--;\r
\r
- il = da->p[i>>logL];\r
+ il = da->p[ i >> logL ];\r
if (il < 0) {\r
il = -il-1;\r
p = da->sl[(il<<logL)+(i & (L-1))];\r