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