2 // Implements operations over a bitmap
7 // In theory, we should have superblocks of size s=log^2 n divided into
8 // blocks of size b=(log n)/2. This takes
9 // O(n log n / log^2 n + n log log n / log n + log n sqrt n log log n) bits
10 // In practice, we can have any s and b, and the needed amount of bits is
11 // (n/s) log n + (n/b) log s + b 2^b log b bits
12 // Optimizing it turns out that s should be exactly s = b log n
13 // Optimizing b is more difficult but could be done numerically.
14 // However, the exponential table does no more than popcounting, so why not
15 // setting up a popcount algorithm tailored to the computer register size,
16 // defining that size as b, and proceeding.
18 //unsigned char OnesInByte[] =
19 const unsigned char popc[] = //number of ones in one byte value [0..255].
21 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,
22 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
23 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
24 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
25 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
26 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
27 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
28 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
31 uint popcount (register uint x)
33 { return popc[x&0xFF] + popc[(x>>8)&0xFF] + popc[(x>>16)&0xFF] + popc[x>>24];
37 /******************************************************************/
38 // FUNCIONS DE EDU ...
39 /******************************************************************/
41 Creates a bitmap and structures to rank and select
44 //bitmap createBitmapEdu (uint *string, uint n){ return createBitmap(string,n);}
46 bitmap createBitmap (uint *string, uint n){
51 unsigned int countB, countS, blockIndex, superblockIndex;
52 register unsigned int block;
54 B =(struct sbitmap *) malloc (sizeof(struct sbitmap));
62 B->bdata =(byte *)malloc(nb*sizeof(byte)); // Db = (unsigned char *)malloc(nb*sizeof(unsigned char));
63 B->sdata = (uint*)malloc(ns*sizeof(uint)); // Ds = (unsigned int *)malloc(ns*sizeof(unsigned int));
65 B->mem_usage = (ns*sizeof(uint)) + (nb*sizeof(byte)) + (sizeof(struct sbitmap));
66 /* Ahora construimos los bloques */
72 while(blockIndex < nb) {
76 B->sdata[superblockIndex++] = countS;
80 B->bdata[blockIndex] = countB;
81 block = string[blockIndex++];
83 countB += popcount(block);
86 B->pop = countS+countB;
88 // {int i; //fprintf(stderr,"\n");
89 // for (i=0;i<ns;i++) {//fprintf(stderr,"%d ",B->sdata[i]);
91 // //fprintf(stderr,"\n");
92 // for (i=0;i<8;i++) {//fprintf(stderr,"%d ",B->bdata[i]);
100 Number of 1s in range [0,posicion]
102 //uint rank1Edu(bitmap B, unsigned int position) {
103 //uint rank1Edu(bitmap B, unsigned int position) { return rank(B,position);}
104 uint rank(bitmap B, unsigned int position) {
105 register unsigned int block;
106 if (position > B->n) return B->pop;
109 block = B->data[position/32] << (31-position%32);
111 return B->sdata[position/256] + B->bdata[position/32] +
112 popc[block & 0xff] + popc[(block>>8) & 0xff] +
113 popc[(block>>16) & 0xff] + popc[block>>24];
117 /********************************************************************************************/
118 /**************************************************************************************/
120 static uint binsearch (uint *data, uint size, uint val)
126 if (data[m] >= val) j = m;
132 uint bselect (bitmap B, uint j)
134 { uint spos,bpos,pos,word,x;
136 if (j > B->pop) return B->n;
137 spos = binsearch(B->sdata,(B->n+256-1)/256,j);
139 //fprintf(stderr,"\n SPOS IS %d, and B->sdata[pos] = %d",spos,B->sdata[spos]);
142 blk = B->bdata + (pos>>5);
145 //while ((bpos < (1<<3)-1) && (blk[bpos+1] < j)) bpos++;
146 while ( ((spos*8+bpos) < ((B->n-1)/W)) && (bpos < (1<<3)-1) && (blk[bpos+1] < j)) bpos++;
149 //fprintf(stderr,"\n BPOS = %d",bpos);
151 word = B->data[pos>>5];
153 //fprintf(stderr,"\n pos>>5 = %d ... pasou XXX con word = %d, and j= %d",pos>>5,word,j);
155 { x = popc[word & ((1<<8)-1)];
156 //fprintf(stderr,"\n word = %u popc vale %u",word & ((1<<8)-1),x);
163 while (j) { if (word & 1) j--; word >>= 1; pos++; }
165 // fprintf(stderr,"\n\nBSELECT::: POSICIÓN FINAL = %u",pos-1);
171 // destroys the bitmap, freeing the original bitstream
172 void destroyBitmap (bitmap B)
181 // Prints the bit vector
182 void showBitVector(uint * V, int vectorSize) {
184 while(bitIndex<vectorSize) {
185 fprintf(stderr,"%d",bitget(V,bitIndex));
190 void saveBitmap (char *filename, bitmap b) {
193 if( (file = open(filename, O_WRONLY|O_CREAT,S_IRWXG | S_IRWXU)) < 0) {
194 printf("Cannot open file %s\n", filename);
197 write(file, &(b->sSize), sizeof(uint));
198 write(file, b->sdata, sizeof(int) * (b->sSize));
199 write(file, &(b->bSize), sizeof(uint));
200 write(file, b->bdata, sizeof(byte) * (b->bSize));
202 write(file, &(b->pop), sizeof(uint));
203 write(file, &(b->n), sizeof(uint));
207 /* loads the Rank structures from disk, and sets Bitmap->data ptr to "string"
209 bitmap loadBitmap (char *filename, uint *string, uint n) {
213 if( (file = open(filename, O_RDONLY)) < 0) {
214 printf("Cannot read file %s\n", filename);
218 B = (struct sbitmap *) malloc (sizeof(struct sbitmap));
221 read(file, &(B->sSize), sizeof(uint));
222 B->sdata = (uint *) malloc(sizeof(uint) * B->sSize);
223 read(file, B->sdata, sizeof(uint) * B->sSize);
225 read(file, &(B->bSize), sizeof(uint));
226 B->bdata = (byte *) malloc(sizeof(byte) * B->bSize);
227 read(file, B->bdata, sizeof(byte) * B->bSize);
229 read(file, &(B->pop), sizeof(uint));
230 read(file, &(B->n), sizeof(uint));
232 B->mem_usage = (sizeof(uint) * B->sSize) + (sizeof(byte) * B->bSize) + (sizeof(struct sbitmap));
234 if (n != B->n) {printf("\n LoadBitmap failed: %u distinto de %u",n,B->n); exit(0);}
240 /********************************************************************************************/
241 /********************************************************************************************/
246 // creates a bitmap structure from a bitstring, which is shared
248 bitmap createBitmapGONZA (uint *string, uint n)
249 //bitmap createBitmap (uint *string, uint n)
252 uint i,j,pop,bpop,pos;
254 B = (struct sbitmap *) malloc (sizeof(struct sbitmap));
258 B->n = n; words = (n+W-1)/W;
259 ns = (n+256-1)/256; nb = 256/W; // adjustments
262 B->bdata = (byte *) malloc (ns*nb*sizeof(byte));
264 B->sdata = (uint *)malloc (ns*sizeof(int));
266 B->mem_usage = (ns*sizeof(int)) + (ns*nb*sizeof(byte)) + (sizeof(struct sbitmap));
268 printf (" Bitmap over %i bits took %i bits\n", n,n+ns*nb*8+ns*32);
270 //fprintf (stderr," Bitmap over %i bits took %i bits\n", n,n+ns*nb*8+ns*32);
276 { if (pos == words) break;
277 B->bdata[pos++] = bpop;
278 bpop += popcount(*string++);
284 // //fprintf(stderr,"\n");
285 // for (i=0;i<ns;i++) {//fprintf(stderr,"%d ",B->sdata[i]);
287 // //fprintf(stderr,"\n");
288 // for (i=0;i<ns*nb;i++) {//fprintf(stderr,"%d ",B->bdata[i]);
294 // rank(i): how many 1's are there before position i, not included
296 //uint rank (bitmap B, uint i)
297 uint rankGONZA (bitmap B, uint i)
301 if (i > B->n) return B->pop;
302 return B->sdata[i>>8] + B->bdata[i>>5] +
303 popcount (B->data[i>>5] & ((1<<(i&0x1F))-1));