-
#include <sdarray.h>
+#include <stdint.h>
using std::min;
using std::max;
#if 0
}
-int __getbit2(uchar *B, int i) {
+static int __getbit2(uchar *B, int i) {
int j,l;
//j = i / D;
#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;
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
-
+#endif
-#ifdef HAS_NATIVE_POPCOUNT
+#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 popcount(n & 0xff);
-}
+// static inline unsigned int popcount8(unsigned int n) {
+// return __builtin_popcount(n & 0xff);
+// }
-static inline unsigned int _fast_popcount(int x)
+static inline unsigned int _fast_popcount(uchar x)
{
- return popcount8(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,
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) {
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);
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);
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++) {
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++) {
select->sl[ml*L+is] = s[il*L+is];
}
}
+
select->p[il] = -((ml<<logL)+1);
ml++;
}
ms++;
}
}
+
if (r == 0) {
select->sl = new uint[ml*L+1];
for(int k=0;k<ml*L+1;k++) select->sl[k]=0;
}
-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];
}
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;
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++;
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);
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++;
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);
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;
}
projects / SXSI / libcds.git / blobdiff