#define logL (logLL-1-5)
#define L (1<<logL)
-int blog(int x) {
+int __blog(int x) {
int l;
l = 0;
while (x>0) {
}
-int setbit(uint *B, int i,int x) {
+int __setbit(uint *B, int i,int x) {
int j,l;
//printf("%u\n",D);
j = i / D;
if (x==0) B[j] &= (~(1<<(D-1-l)));
else if (x==1) B[j] |= (1<<(D-1-l));
else {
- printf("error setbit x=%d\n",x);
+ printf("error __setbit x=%d\n",x);
exit(1);
}
return x;
}
-int setbit2(uchar *B, int i,int x) {
+int __setbit2(uchar *B, int i,int x) {
int j,l;
j = i / 8;
if (x==0) B[j] &= (~(1<<(8-1-l)));
else if (x==1) B[j] |= (1<<(8-1-l));
else {
- printf("error setbit2 x=%d\n",x);
+ printf("error __setbit2 x=%d\n",x);
exit(1);
}
return x;
}
-int setbits(uint *B, int i, int d, int x) {
+int __setbits(uint *B, int i, int d, int x) {
int j;
for (j=0; j<d; j++) {
- setbit(B,i+j,(x>>(d-j-1))&1);
+ __setbit(B,i+j,(x>>(d-j-1))&1);
}
return x;
}
-int getbit(uint *B, int i) {
+int __getbit(uint *B, int i) {
int j,l;
//j = i / D;
}
-int getbit2(uchar *B, int i) {
+int __getbit2(uchar *B, int i) {
int j,l;
//j = i / D;
#if 1
-uint getbits(uint *B, int i, int d) {
+uint __getbits(uint *B, int i, int d) {
qword x,z;
B += (i >> logD);
#endif
#if 0
-uint getbits(uint *B, int i, int d) {
+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);
+ x += __getbit(B,i+j);
}
return x;
}
#endif
-static const unsigned int popCount[] = {
+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,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};
-static unsigned int selecttbl[8*256];
+static unsigned int __selecttbl[8*256];
-void make_selecttbl(void) {
+void make___selecttbl(void) {
int i,x,r;
uint buf[1];
for (x = 0; x < 256; x++) {
- setbits(buf,0,8,x);
- for (r=0; r<8; r++) selecttbl[(r<<8)+x] = -1;
+ __setbits(buf,0,8,x);
+ 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;
+ if (__getbit(buf,i)) {
+ __selecttbl[(r<<8)+x] = i;
r++;
}
}
}
}
-unsigned int popcount(uint x) {
+unsigned int __popCount(uint x) {
uint r;
#if 0
r = x;
//r = ((r & 0xffff0000)>>16) + (r & 0x0000ffff);
r = ((r>>16) + r) & 63;
#else
- r = popCount[x & 0xff];
+ r = _popCount[x & 0xff];
x >>= 8;
- r += popCount[x & 0xff];
+ r += _popCount[x & 0xff];
x >>= 8;
- r += popCount[x & 0xff];
+ r += _popCount[x & 0xff];
x >>= 8;
- r += popCount[x & 0xff];
+ r += _popCount[x & 0xff];
#endif
return r;
}
-unsigned int popcount8(uint x) {
+unsigned int __popCount8(uint x) {
uint r;
#if 1
r = x;
r = ((r & 0xcc)>>2) + (r & 0x33);
r = ((r>>4) + r) & 0x0f;
#else
- r = popCount[x & 0xff];
+ r = _popCount[x & 0xff];
#endif
return r;
}
int r;
uint *s;
- make_selecttbl();
+ make___selecttbl();
if (L/LLL == 0) {
printf("ERROR: L=%d LLL=%d\n",L,LLL);
}
m = 0;
- for (i=0; i<n; i++) m += getbit2(buf,i);
+ for (i=0; i<n; i++) m += __getbit2(buf,i);
select->n = n;
select->m = m;
//printf("n=%d m=%d\n",n,m);
s = new uint[m];
m = 0;
for (i=0; i<n; i++) {
- if (getbit2(buf,i)) {
+ if (__getbit2(buf,i)) {
m++;
s[m-1] = i;
}
if (f == 1) {
rr = p & (8-1);
- r -= popCount[*q >> (8-1-rr)];
+ r -= _popCount[*q >> (8-1-rr)];
//p = p - rr;
while (1) {
- rr = popCount[*q];
+ rr = _popCount[*q];
if (r + rr >= i) break;
r += rr;
//p += 8;
q++;
}
p = (q - select->buf) << 3;
- p += selecttbl[((i-r-1)<<8)+(*q)];
+ p += __selecttbl[((i-r-1)<<8)+(*q)];
}
else {
rr = p & (8-1);
- r -= popCount[(*q ^ 0xff) >> (8-1-rr)];
+ r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
//p = p - rr;
while (1) {
- rr = popCount[*q ^ 0xff];
+ rr = _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 ^ 0xff)];
}
}
return p;
if (f == 1) {
rr = p & (8-1);
- r -= popCount[*q >> (8-1-rr)];
+ r -= _popCount[*q >> (8-1-rr)];
//p = p - rr;
while (1) {
- rr = popCount[*q];
+ rr = _popCount[*q];
if (r + rr >= i) break;
r += rr;
//p += 8;
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++;
while (1) {
- rr = popCount[*q];
+ rr = _popCount[*q];
if (r + rr >= i) break;
r += rr;
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);
}
else {
rr = p & (8-1);
- r -= popCount[(*q ^ 0xff) >> (8-1-rr)];
+ r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
//p = p - rr;
while (1) {
- rr = popCount[*q ^ 0xff];
+ rr = _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 ^ 0xff)];
if ((i>>logL) == ((i+1)>>logL)) {
i++;
while (1) {
- rr = popCount[*q ^ 0xff];
+ rr = _popCount[*q ^ 0xff];
if (r + rr >= i) break;
r += rr;
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);
selectd2 *sd0,*sd1;
m = 0;
- for (i=0; i<n; i++) m += getbit(buf,i);
+ for (i=0; i<n; i++) m += __getbit(buf,i);
select->n = n;
select->m = m;
select->low = low;
select->size = sizeof(uchar)*((2*m+8-1)/8+1) + sizeof(uint)*((d*m+PBS-1)/PBS+1);
- for (i=0; i<m*2; i++) setbit2(buf2,i,0);
+ for (i=0; i<m*2; i++) __setbit2(buf2,i,0);
m = 0;
for (i=0; i<n; i++) {
- if (getbit(buf,i)) {
- setbit2(buf2,(i>>d)+m,1);
- setbits(low,m*d,d,i & ((1<<d)-1));
+ if (__getbit(buf,i)) {
+ __setbit2(buf2,(i>>d)+m,1);
+ __setbits(low,m*d,d,i & ((1<<d)-1));
m++;
}
}
selectd2_construct(sd1,m*2,buf2);
select->sd1 = sd1;
- for (i=0; i<m*2; i++) setbit2(buf2,i,1-getbit2(buf2,i));
+ for (i=0; i<m*2; i++) __setbit2(buf2,i,1-__getbit2(buf2,i));
selectd2_construct(sd0,m*2,buf2);
select->sd0 = sd0;
- for (i=0; i<m*2; i++) setbit2(buf2,i,1-getbit2(buf2,i));
+ for (i=0; i<m*2; i++) __setbit2(buf2,i,1-__getbit2(buf2,i));
return 0;
}
x = selectd2_select(select->sd1,i,1) - (i-1);
x <<= d;
- x += getbits(select->low,(i-1)*d,d);
+ x += __getbits(select->low,(i-1)*d,d);
return x;
}
z = select->hi[y];
while (1) {
if (((z << r) & 0x80) == 0) break;
- w = getbits(q,x*d,d);
+ w = __getbits(q,x*d,d);
if (w >= j) {
if (w == j) x++;
break;