#include <stdio.h>\r
#include <stdlib.h>\r
#include "darray.h"\r
+#include "utils.h"\r
\r
//typedef unsigned char byte;\r
//typedef unsigned short word;\r
//typedef unsigned int dword;\r
\r
//typedef dword pb;\r
-#define logD 5\r
+//#define logD 5\r
\r
#define PBS (sizeof(pb)*8)\r
#define D (1<<logD)\r
return x;\r
}\r
\r
+int setbit_zero(pb *B, int i)\r
+{\r
+ int j,l;\r
+ j = i >> logD;\r
+ l = i & (D-1);\r
+ B[j] &= (~(1<<(D-1-l)));\r
+ return 0;\r
+}\r
+\r
+int setbit_one(pb *B, int i)\r
+{\r
+ int j,l;\r
+ j = i >> logD;\r
+ l = i & (D-1);\r
+ B[j] |= (1<<(D-1-l));\r
+ return 1;\r
+\r
+}\r
+\r
+\r
+\r
int setbits(pb *B, int i, int d, int x)\r
{\r
int j;\r
\r
static int selecttbl[8*256];\r
\r
-unsigned int popcount(pb x)\r
-{\r
- pb r;\r
-#if 0\r
- r = x;\r
- r = r - ((r>>1) & 0x77777777) - ((r>>2) & 0x33333333) - ((r>>3) & 0x11111111);\r
- r = ((r + (r>>4)) & 0x0f0f0f0f) % 0xff;\r
-#elif 1\r
- r = x;\r
- r = ((r & 0xaaaaaaaa)>>1) + (r & 0x55555555);\r
- r = ((r & 0xcccccccc)>>2) + (r & 0x33333333);\r
- //r = ((r & 0xf0f0f0f0)>>4) + (r & 0x0f0f0f0f);\r
- r = ((r>>4) + r) & 0x0f0f0f0f;\r
- //r = ((r & 0xff00ff00)>>8) + (r & 0x00ff00ff);\r
- r = (r>>8) + r;\r
- //r = ((r & 0xffff0000)>>16) + (r & 0x0000ffff);\r
- r = ((r>>16) + r) & 63;\r
-#else\r
- r = popCount[x & 0xff];\r
- x >>= 8;\r
- r += popCount[x & 0xff];\r
- x >>= 8;\r
- r += popCount[x & 0xff];\r
- x >>= 8;\r
- r += popCount[x & 0xff];\r
-#endif\r
- return r;\r
-}\r
-\r
-unsigned int popcount8(pb x)\r
-{\r
- dword r;\r
-#if 1\r
- r = x;\r
- r = ((r & 0xaa)>>1) + (r & 0x55);\r
- r = ((r & 0xcc)>>2) + (r & 0x33);\r
- r = ((r>>4) + r) & 0x0f;\r
-#else\r
- r = popCount[x & 0xff];\r
-#endif\r
- return r;\r
-}\r
-\r
void make_selecttbl(void)\r
{\r
int i,x,r;\r
\r
int darray_rank(darray *da, int i)\r
{\r
- int r,j;\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
- r = da->rl[i>>logR] + da->rm[i>>logRR];\r
- j = (i>>logRRR) & (RR/RRR-1);\r
+ j = (i_rrr) & (RR/RRR-1);\r
while (j > 0) {\r
- r += da->rs[((i>>logRR)<<(logRR-logRRR))+j-1];\r
+ r += da->rs[((i_rr)<<(logRR-logRRR))+j-1];\r
j--;\r
}\r
\r
- p = da->buf + ((i>>logRRR)<<(logRRR-logD));\r
+ p = da->buf + ((i_rrr)<<(logRRR-logD));\r
j = i & (RRR-1);\r
while (j >= D) {\r
r += popcount(*p++);\r
x = *q;\r
while (1) {\r
//rr = popcount(x >> (D-8));\r
- rr = popCount[x >> (D-8)];\r
- //rr = popcount8(x >> (D-8));\r
+ //rr = popcount(x >> (D-8));\r
+ rr = popcount8(x >> (D-8));\r
if (r + rr >= i) break;\r
r += rr;\r
p += 8;\r
\r
while (1) {\r
//rr = popcount(x >> (D-8));\r
- rr = popCount[x >> (D-8)];\r
- //rr = popcount8(x >> (D-8));\r
+ //rr = popCount[x >> (D-8)];\r
+ rr = popcount8(x >> (D-8));\r
if (r + rr >= i) break;\r
r += rr;\r
p += 8;\r
x = getpat(q);\r
while (1) {\r
//rr = popcount(x >> (D-8));\r
- rr = popCount[x >> (D-8)];\r
- //rr = popcount8(x >> (D-8));\r
+ //rr = popCount[x >> (D-8)];\r
+ rr = popcount8(x >> (D-8));\r
if (r + rr >= i) break;\r
r += rr;\r
p += 8;\r