libcds/src/static_bitsequence/static_bitsequence_brw32.cpp

   1 /* static_bitsequence_brw32.cpp
   2    Copyright (C) 2005, Rodrigo Gonzalez, all rights reserved.
   3
   4    New RANK, SELECT, SELECT-NEXT and SPARSE RANK implementations.
   5
   6    This library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    This library is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with this library; if not, write to the Free Software
  18    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19
  20 */
  21
  22 #include "static_bitsequence_brw32.h"
  23 #include <cassert>
  24 #include <cmath>
  25 // #include <sys/types.h>
  26 using std::cout;
  27 using std::endl;
  28
  29 /////////////
  30 //Rank(B,i)//
  31 /////////////
  32 //_factor = 0  => s=W*lgn
  33 //_factor = P  => s=W*P
  34 //Is interesting to notice
  35 //factor=2 => overhead 50%
  36 //factor=3 => overhead 33%
  37 //factor=4 => overhead 25%
  38 //factor=20=> overhead 5%
  39
  40 static_bitsequence_brw32::static_bitsequence_brw32(){
  41   data=NULL;
  42 //  this->owner = true;
  43   this->n=0;
  44   this->factor=0;
  45 }
  46
  47 static_bitsequence_brw32::static_bitsequence_brw32( uint *bitarray, uint _n, uint _factor){
  48   /*cout << "*****" << endl;
  49   cout << bitarray << endl;
  50   cout << _n << endl;
  51   cout << _factor << endl; */
  52   if(_factor==0) exit(-1);
  53   data=new uint[_n/W+1];
  54   for(uint i=0;i<uint_len(_n,1);i++)
  55     data[i] = bitarray[i];
  56   for(uint i=uint_len(_n,1);i<_n/W+1;i++)
  57     data[i] = 0;
  58   //this->owner = true;
  59   this->n=_n;
  60   uint lgn=bits(n-1);
  61   this->factor=_factor;
  62   if (_factor==0) this->factor=lgn;
  63   else this->factor=_factor;
  64   b=32;
  65   s=b*this->factor;
  66   integers = n/W+1;
  67   BuildRank();
  68   this->len = n;
  69   this->ones = rank1(n-1);
  70 }
  71
  72 static_bitsequence_brw32::~static_bitsequence_brw32() {
  73   delete [] Rs;
  74   delete [] data;
  75 }
  76
  77 //Metodo que realiza la busqueda d
  78 void static_bitsequence_brw32::BuildRank(){
  79   uint num_sblock = n/s;
  80   Rs = new uint[num_sblock+5];// +1 pues sumo la pos cero
  81   for(uint i=0;i<num_sblock+5;i++)
  82     Rs[i]=0;
  83   uint j;
  84   Rs[0]=0;
  85   for (j=1;j<=num_sblock;j++) {
  86     Rs[j]=Rs[j-1];
  87     Rs[j]+=BuildRankSub((j-1)*factor,factor);
  88   }
  89 }
  90
  91 uint static_bitsequence_brw32::BuildRankSub(uint ini,uint bloques){
  92   uint rank=0,aux;
  93   for(uint i=ini;i<ini+bloques;i++) {
  94     if (i < integers) {
  95       aux=data[i];
  96       rank+=popcount(aux);
  97     }
  98   }
  99   return rank; //retorna el numero de 1's del intervalo
 100
 101 }
 102
 103 uint static_bitsequence_brw32::rank1(uint i) {
 104   ++i;
 105   uint resp=Rs[i/s];
 106   uint aux=(i/s)*factor;
 107   for (uint a=aux;a<i/W;a++)
 108     resp+=popcount(data[a]);
 109   resp+=popcount(data[i/W]  & ((1<<(i & mask31))-1));
 110   return resp;
 111 }
 112
 113 bool static_bitsequence_brw32::access(uint i) {
 114   return (1u << (i % W)) & data[i/W];
 115 }
 116
 117 int static_bitsequence_brw32::save(FILE *f) {
 118   uint wr = BRW32_HDR;
 119   if (f == NULL) return 20;
 120   if( fwrite(&wr,sizeof(uint),1,f) != 1 ) return -1;
 121   if (fwrite (&n,sizeof(uint),1,f) != 1) return 21;
 122   if (fwrite (&factor,sizeof(uint),1,f) != 1) return 21;
 123   if (fwrite (data,sizeof(uint),n/W+1,f) != n/W+1) return 21;
 124   if (fwrite (Rs,sizeof(uint),n/s+1,f) != n/s+1) return 21;
 125   return 0;
 126 }
 127
 128 static_bitsequence_brw32 * static_bitsequence_brw32::load(FILE *f) {
 129   if (f == NULL) return NULL;
 130   uint type;
 131   if(fread(&type,sizeof(uint),1,f)!=1) return NULL;
 132   if(type!=BRW32_HDR) { cout << "type:"<<type<<endl; return NULL; }
 133   static_bitsequence_brw32 * ret = new static_bitsequence_brw32();
 134   if (fread (&ret->n,sizeof(uint),1,f) != 1) return NULL;
 135   ret->b=32; // b is a word
 136   if (fread (&ret->factor,sizeof(uint),1,f) != 1) return NULL;
 137   ret->s=ret->b*ret->factor;
 138   uint aux=(ret->n+1)%W;
 139   if (aux != 0)
 140     ret->integers = (ret->n+1)/W+1;
 141   else
 142     ret->integers = (ret->n+1)/W;
 143   ret->data = new uint[ret->n/W+1];
 144   if (!ret->data) return NULL;
 145   if (fread (ret->data,sizeof(uint),ret->n/W+1,f) != ret->n/W+1) return NULL;
 146   ret->Rs= new uint[ret->n/ret->s+1];
 147   if (!ret->Rs) return NULL;
 148   if (fread (ret->Rs,sizeof(uint),ret->n/ret->s+1,f) != ret->n/ret->s+1) return NULL;
 149   ret->len = ret->n;
 150   ret->ones = ret->rank1(ret->n-1);
 151   return ret;
 152 }
 153
 154 uint static_bitsequence_brw32::SpaceRequirementInBits() {
 155   return uint_len(n,1)*sizeof(uint)*8+(n/s)*sizeof(uint)*8 +sizeof(static_bitsequence_brw32)*8;
 156 }
 157
 158 uint static_bitsequence_brw32::size() {
 159   return sizeof(static_bitsequence_brw32)+SpaceRequirementInBits()/8;
 160 }
 161
 162 uint static_bitsequence_brw32::SpaceRequirement() {
 163   return n/8+(n/s)*sizeof(uint)+sizeof(static_bitsequence_brw32);
 164 }
 165
 166 uint static_bitsequence_brw32::prev2(uint start) {
 167       // returns the position of the previous 1 bit before and including start.
 168       // tuned to 32 bit machine
 169
 170       uint i = start >> 5;
 171       int offset = (start % W);
 172       uint answer = start;
 173       uint val = data[i] << (Wminusone-offset);
 174
 175       if (!val) { val = data[--i]; answer -= 1+offset; }
 176
 177       while (!val) { val = data[--i]; answer -= W; }
 178
 179       if (!(val & 0xFFFF0000)) { val <<= 16; answer -= 16; }
 180       if (!(val & 0xFF000000)) { val <<= 8; answer -= 8; }
 181
 182       while (!(val & 0x80000000)) { val <<= 1; answer--; }
 183       return answer;
 184 }
 185
 186 uint static_bitsequence_brw32::prev(uint start) {
 187       // returns the position of the previous 1 bit before and including start.
 188       // tuned to 32 bit machine
 189
 190       uint i = start >> 5;
 191       int offset = (start % W);
 192       uint aux2 = data[i] & (-1u >> (31-offset));
 193
 194       if (aux2 > 0) {
 195                 if ((aux2&0xFF000000) > 0) return i*W+23+prev_tab[(aux2>>24)&0xFF];
 196                 else if ((aux2&0xFF0000) > 0) return i*W+15+prev_tab[(aux2>>16)&0xFF];
 197                 else if ((aux2&0xFF00) > 0) return i*W+7+prev_tab[(aux2>>8)&0xFF];
 198                 else  return i*W+prev_tab[aux2&0xFF]-1;
 199       }
 200       for (uint k=i-1;;k--) {
 201          aux2=data[k];
 202          if (aux2 > 0) {
 203                 if ((aux2&0xFF000000) > 0) return k*W+23+prev_tab[(aux2>>24)&0xFF];
 204                 else if ((aux2&0xFF0000) > 0) return k*W+15+prev_tab[(aux2>>16)&0xFF];
 205                 else if ((aux2&0xFF00) > 0) return k*W+7+prev_tab[(aux2>>8)&0xFF];
 206                 else  return k*W+prev_tab[aux2&0xFF]-1;
 207          }
 208       }
 209       return 0;
 210 }
 211
 212 uint static_bitsequence_brw32::next(uint k) {
 213         uint count = k;
 214         uint des,aux2;
 215         des=count%W;
 216         aux2= data[count/W] >> des;
 217         if (aux2 > 0) {
 218                 if ((aux2&0xff) > 0) return count+select_tab[aux2&0xff]-1;
 219                 else if ((aux2&0xff00) > 0) return count+8+select_tab[(aux2>>8)&0xff]-1;
 220                 else if ((aux2&0xff0000) > 0) return count+16+select_tab[(aux2>>16)&0xff]-1;
 221                 else {return count+24+select_tab[(aux2>>24)&0xff]-1;}
 222         }
 223
 224         for (uint i=count/W+1;i<integers;i++) {
 225                 aux2=data[i];
 226                 if (aux2 > 0) {
 227                         if ((aux2&0xff) > 0) return i*W+select_tab[aux2&0xff]-1;
 228                         else if ((aux2&0xff00) > 0) return i*W+8+select_tab[(aux2>>8)&0xff]-1;
 229                         else if ((aux2&0xff0000) > 0) return i*W+16+select_tab[(aux2>>16)&0xff]-1;
 230                         else {return i*W+24+select_tab[(aux2>>24)&0xff]-1;}
 231                 }
 232         }
 233         return n;
 234 }
 235
 236 uint static_bitsequence_brw32::select1(uint x) {
 237   // returns i such that x=rank(i) && rank(i-1)<x or n if that i not exist
 238   // first binary search over first level rank structure
 239   // then sequential search using popcount over a int
 240   // then sequential search using popcount over a char
 241   // then sequential search bit a bit
 242   if(x>ones) return (uint)(-1);
 243
 244   //binary search over first level rank structure
 245   uint l=0, r=n/s;
 246   uint mid=(l+r)/2;
 247   uint rankmid = Rs[mid];
 248   while (l<=r) {
 249     if (rankmid<x)
 250       l = mid+1;
 251     else
 252       r = mid-1;
 253     mid = (l+r)/2;
 254     rankmid = Rs[mid];
 255   }
 256   //sequential search using popcount over a int
 257   uint left;
 258   left=mid*factor;
 259   x-=rankmid;
 260         uint j=data[left];
 261         uint ones = popcount(j);
 262         while (ones < x) {
 263     x-=ones;left++;
 264     if (left > integers) return n;
 265           j = data[left];
 266       ones = popcount(j);
 267         }
 268   //sequential search using popcount over a char
 269   left=left*b;
 270   rankmid = popcount8(j);
 271   if (rankmid < x) {
 272     j=j>>8;
 273     x-=rankmid;
 274     left+=8;
 275     rankmid = popcount8(j);
 276     if (rankmid < x) {
 277       j=j>>8;
 278       x-=rankmid;
 279       left+=8;
 280       rankmid = popcount8(j);
 281       if (rankmid < x) {
 282         j=j>>8;
 283         x-=rankmid;
 284         left+=8;
 285       }
 286     }
 287   }
 288
 289   // then sequential search bit a bit
 290         while (x>0) {
 291     if  (j&1) x--;
 292     j=j>>1;
 293     left++;
 294   }
 295   return left-1;
 296 }
 297
 298 uint static_bitsequence_brw32::select0(uint x) {
 299   // returns i such that x=rank_0(i) && rank_0(i-1)<x or n if that i not exist
 300   // first binary search over first level rank structure
 301   // then sequential search using popcount over a int
 302   // then sequential search using popcount over a char
 303   // then sequential search bit a bit
 304   if(x>n-ones) return (uint)(-1);
 305
 306   //binary search over first level rank structure
 307   if(x==0) return 0;
 308   uint l=0, r=n/s;
 309   uint mid=(l+r)/2;
 310   uint rankmid = mid*factor*W-Rs[mid];
 311   while (l<=r) {
 312     if (rankmid<x)
 313       l = mid+1;
 314     else
 315       r = mid-1;
 316     mid = (l+r)/2;
 317     rankmid = mid*factor*W-Rs[mid];
 318   }
 319   //sequential search using popcount over a int
 320   uint left;
 321   left=mid*factor;
 322   x-=rankmid;
 323   uint j=data[left];
 324   uint zeros = W-popcount(j);
 325   while (zeros < x) {
 326     x-=zeros;left++;
 327     if (left > integers) return n;
 328     j = data[left];
 329     zeros = W-popcount(j);
 330   }
 331   //sequential search using popcount over a char
 332   left=left*b;
 333   rankmid = 8-popcount8(j);
 334   if (rankmid < x) {
 335     j=j>>8;
 336     x-=rankmid;
 337     left+=8;
 338     rankmid = 8-popcount8(j);
 339     if (rankmid < x) {
 340       j=j>>8;
 341       x-=rankmid;
 342       left+=8;
 343       rankmid = 8-popcount8(j);
 344       if (rankmid < x) {
 345         j=j>>8;
 346         x-=rankmid;
 347         left+=8;
 348       }
 349     }
 350   }
 351
 352   // then sequential search bit a bit
 353   while (x>0) {
 354     if  (j%2 == 0 ) x--;
 355     j=j>>1;
 356     left++;
 357   }
 358   left--;
 359   if (left > n)  return n;
 360   else return left;
 361 }