3 #include "bp-darray.h"
\r
4 #include "bp-utils.h"
\r
6 #define PBS (sizeof(pb)*8)
\r
12 #define logLL 16 // size of word
\r
13 #define LL (1<<logLL)
\r
16 #define LLL (1<<logLLL)
\r
18 //#define logL (logLL-3)
\r
19 #define logL (logLL-1-5)
\r
23 ({ __typeof__ (a) _a = (a); \
\r
24 __typeof__ (b) _b = (b); \
\r
25 _a > _b ? _a : _b; })
\r
29 ({ __typeof__ (a) _a = (a); \
\r
30 __typeof__ (b) _b = (b); \
\r
31 _a <= _b ? _a : _b; })
\r
36 static dword getbits(pb *B, int i, int d)
\r
41 for (j=0; j<d; j++) {
\r
43 x += bp_getbit(B,i+j);
\r
48 static int getpattern(pb *B, int i, int k, pb pat)
\r
53 for (j=0; j<k; j++) {
\r
54 x &= bp_getbit(B,i+j) ^ (~(pat>>(k-1-j)));
\r
56 //printf("getpattern(%d) = %d\n",i,x);
\r
60 static int selecttbl[8*256];
\r
61 static int selecttbl_init = 0;
\r
63 static void make_selecttbl(void)
\r
67 if (selecttbl_init) return;
\r
71 for (x = 0; x < 256; x++) {
\r
72 bp_setbits(buf,0,8,x);
\r
73 for (r=0; r<8; r++) selecttbl[(r<<8)+x] = -1;
\r
75 for (i=0; i<8; i++) {
\r
76 if (bp_getbit(buf,i)) {
\r
77 selecttbl[(r<<8)+x] = i;
\r
85 darray * bp_darray_construct(int n, pb *buf, int opt)
\r
92 int p1,p2,p3,p4,s1,s2,s3,s4;
\r
103 printf("ERROR: L=%d LLL=%d\n",L,LLL);
\r
108 for (i=0; i<n; i++) m += bp_getbit(buf,i);
\r
111 //printf("n=%d m=%d\n",n,m);
\r
115 if (opt & (~OPT_NO_RANK)) { // construct select table
\r
117 nl = (m-1) / L + 1;
\r
118 bp_xmalloc(da->lp, nl+1);
\r
119 da->idx_size += (nl+1) * sizeof(*da->lp);
\r
120 bp_xmalloc(da->p, nl+1);
\r
121 da->idx_size += (nl+1) * sizeof(*da->p);
\r
123 for (r = 0; r < 2; r++) {
\r
124 s1 = s2 = s3 = s4 = 0;
\r
125 p1 = p2 = p3 = p4 = -1;
\r
128 for (il = 0; il < nl; il++) {
\r
130 while (s1 <= il*L) {
\r
131 if (bp_getbit(buf,p1+1)) s1++;
\r
136 i = min((il+1)*L-1,m-1);
\r
139 if (bp_getbit(buf,p2+1)) s2++;
\r
144 if (p - pp >= LL) {
\r
146 for (is = 0; is < L; is++) {
\r
147 if (il*L+is >= m) break;
\r
149 while (s3 <= il*L+is) {
\r
150 if (bp_getbit(buf,p3+1)) s3++;
\r
153 da->sl[ml*L+is] = p3;
\r
156 da->p[il] = -(ml+1);
\r
160 for (is = 0; is < L/LLL; is++) {
\r
161 if (il*L+is*LLL >= m) break;
\r
162 while (s4 <= il*L+is*LLL) {
\r
163 if (bp_getbit(buf,p4+1)) s4++;
\r
167 da->ss[ms*(L/LLL)+is] = p4 - pp;
\r
175 bp_xmalloc(da->sl,ml*L+1);
\r
176 da->idx_size += (ml*L+1) * sizeof(*da->sl);
\r
177 bp_xmalloc(da->ss, ms*(L/LLL)+1);
\r
178 da->idx_size += (ms*(L/LLL)+1) * sizeof(*da->ss);
\r
182 } else { // no select table
\r
184 da->p = da->sl = NULL;
\r
188 // construct rank table
\r
190 if ((opt & OPT_NO_RANK) == 0) {
\r
191 bp_xmalloc(da->rl,n/R1+2);
\r
192 da->idx_size += (n/R1+2) * sizeof(*da->rl);
\r
193 bp_xmalloc(da->rm,n/RR+2);
\r
195 da->idx_size += (n/RR+2) * sizeof(*da->rm);
\r
197 bp_xmalloc(da->rs,n/RRR+2);
\r
198 da->idx_size += (n/RRR+2) * sizeof(*da->rs);
\r
201 for (k=0; k<=n; k+=R1) {
\r
204 for (i=0; i<R1; i+=RR) {
\r
205 if (k+i <= n) da->rm[(k+i)/RR] = m2;
\r
207 for (j=0; j<RR; j++) {
\r
208 if (k+i+j < n && bp_getbit(buf,k+i+j)==1) m++;
\r
209 if (j % RRR == RRR-1) {
\r
210 if (k+i+j <= n) da->rs[(k+i+j)/RRR] = m;
\r
227 void bp_darray_free(darray *da) {
\r
230 if (da->buf) bp_free(da->buf);
\r
231 if (da->lp) bp_free(da->lp);
\r
232 if (da->sl) bp_free(da->sl);
\r
233 if (da->ss) bp_free(da->ss);
\r
234 if (da->p) bp_free(da->p);
\r
235 if (da->rl) bp_free(da->rl);
\r
236 if (da->rm) bp_free(da->rm);
\r
237 if (da->rs) bp_free(da->rs);
\r
242 static int darray_rank0(darray *da, int i)
\r
248 r = da->rl[i>>logR] + da->rm[i>>logRR] + da->rs[i>>logRRR];
\r
249 p = da->buf + ((i>>logRRR)<<(logRRR-logD));
\r
251 if (j < D) r += popcount(*p >> (D-1-j));
\r
252 else r += popcount(*p) + popcount(p[1] >> (D-1-(j-D)));
\r
257 r = da->rl[i>>logR] + da->rm[i>>logRR] + da->rs[i>>logRRR];
\r
258 p = da->buf + ((i>>logRRR)<<(logRRR-logD));
\r
260 r += popcount(*p++);
\r
263 r += popcount(*p >> (D-1-j));
\r
265 j = RRR-1 - (i & (RRR-1));
\r
267 r = da->rl[i>>logR] + da->rm[i>>logRR] + da->rs[i>>logRRR];
\r
268 p = da->buf + ((i>>logRRR)<<(logRRR-logD));
\r
270 r -= popcount(*--p);
\r
273 if (j > 0) r -= popcount(*--p << (D-j));
\r
281 int bp_darray_rank(darray *da, int i)
\r
283 int r,j,i_rr, i_rrr;
\r
286 i_rrr = i >> logRRR;
\r
287 r = da->rl[i>>logR] + da->rm[i_rr];
\r
289 j = (i_rrr) & (RR/RRR-1);
\r
291 r += da->rs[((i_rr)<<(logRR-logRRR))+j-1];
\r
295 p = da->buf + ((i_rrr)<<(logRRR-logD));
\r
298 r += popcount(*p++);
\r
301 r += popcount(*p >> (D-1-j));
\r
306 int bp_darray_select_bsearch(darray *da, int i, pb (*getpat)(pb *))
\r
315 if (i == 0) return -1;
\r
329 l = 0; r = (n-1)>>logR;
\r
330 // find the smallest index x s.t. rl[x] >= t
\r
333 //printf("m=%d rl[m+1]=%d t=%d\n",m,da->rl[m+1],t);
\r
334 if (da->rl[m+1] > t) { // m+1 is out of range
\r
335 r = m; // new r = m >= l
\r
337 l = m+1; // new l = m+1 <= r
\r
345 l = x >> logRR; r = (min(x+R1-1,n))>>logRR;
\r
348 //printf("m=%d rm[m+1]=%d t=%d\n",m,da->rm[m+1],t);
\r
349 if (da->rm[m+1] > t) { // m+1 is out of range
\r
352 l = m+1; // new l = m+1 <= r
\r
361 l = x >> logRRR; r = (min(x+RR-1,n))>>logRRR;
\r
364 //printf("m=%d rs[m+1]=%d t=%d\n",m,da->rs[m+1],t);
\r
365 if (da->rs[m+1] > t) { // m+1 is out of range
\r
368 l = m+1; // new l = m+1 <= r
\r
375 while (t > da->rs[l]) {
\r
384 p = &da->buf[x >> logD];
\r
386 m = popcount(getpat(p));
\r
395 rr = popcount8(w >> (D-8));
\r
401 x += selecttbl[((t-0)<<8)+(w>>(D-8))];
\r
405 printf("error x=%d s=%d\n",x,s);
\r
411 int bp_darray_pat_rank(darray *da, int i, pb (*getpat)(pb *))
\r
416 r = da->rl[i>>logR] + da->rm[i>>logRR];
\r
417 j = (i>>logRRR) & (RR/RRR-1);
\r
419 r += da->rs[((i>>logRR)<<(logRR-logRRR))+j-1];
\r
423 p = da->buf + ((i>>logRRR)<<(logRRR-logD));
\r
426 r += popcount(getpat(p));
\r
430 r += popcount(getpat(p) >> (D-1-j));
\r
436 int bp_darray_select(darray *da, int i,int f)
\r
444 if (i <= 0 || i > da->m) return -1;
\r
448 il = da->p[ i >> logL ];
\r
451 p = da->sl[(il<<logL)+(i & (L-1))];
\r
453 p = da->lp[i>>logL];
\r
454 p += da->ss[(il<<(logL-logLLL))+(i & (L-1))/LLL];
\r
455 r = i - (i & (LLL-1));
\r
457 q = &(da->buf[p>>logD]);
\r
461 r -= popcount(*q >> (D-1-rr));
\r
466 if (r + rr >= i) break;
\r
474 //rr = popcount(x >> (D-8));
\r
475 //rr = popcount(x >> (D-8));
\r
476 rr = popcount8(x >> (D-8));
\r
477 if (r + rr >= i) break;
\r
482 p += selecttbl[((i-r-1)<<8)+(x>>(D-8))];
\r
485 r -= popcount((~(*q)) >> (D-1-rr));
\r
489 rr = popcount(~(*q));
\r
490 if (r + rr >= i) break;
\r
499 rr = popcount8(x >> (D-8));
\r
500 if (r + rr >= i) break;
\r
505 p += selecttbl[((i-r-1)<<8)+(x>>(D-8))];
\r
511 int bp_darray_pat_select(darray *da, int i, pb (*getpat)(pb *))
\r
519 if (i == 0) return -1;
\r
523 //printf("ERROR: m=%d i=%d\n",da->m,i);
\r
529 il = da->p[i>>logL];
\r
532 p = da->sl[(il<<logL)+(i & (L-1))];
\r
534 p = da->lp[i>>logL];
\r
535 p += da->ss[(il<<(logL-logLLL))+(i & (L-1))/LLL];
\r
536 r = i - (i & (LLL-1));
\r
538 q = &(da->buf[p>>logD]);
\r
541 r -= popcount(getpat(q) >> (D-1-rr));
\r
545 rr = popcount(getpat(q));
\r
546 if (r + rr >= i) break;
\r
554 rr = popcount8(x >> (D-8));
\r
555 if (r + rr >= i) break;
\r
560 p += selecttbl[((i-r-1)<<8)+(x>>(D-8))];
\r
566 darray * bp_darray_pat_construct(int n, pb *buf, int k, pb pat, int opt)
\r
572 bp_xmalloc(b, (n+D-1)/D);
\r
574 for (i=0; i<n-k+1; i++) {
\r
575 bp_setbit(b, i, getpattern(buf,i,k,pat));
\r
577 for (i=n-k+1; i<n; i++) {
\r
578 bp_setbit(b, i, 0);
\r
581 da = bp_darray_construct(n, b, opt);
\r