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
 242   //binary search over first level rank structure
 243   uint l=0, r=n/s;
 244   uint mid=(l+r)/2;
 245   uint rankmid = Rs[mid];
 246   while (l<=r) {
 247     if (rankmid<x)
 248       l = mid+1;
 249     else
 250       r = mid-1;
 251     mid = (l+r)/2;
 252     rankmid = Rs[mid];
 253   }
 254   //sequential search using popcount over a int
 255   uint left;
 256   left=mid*factor;
 257   x-=rankmid;
 258         uint j=data[left];
 259         uint ones = popcount(j);
 260         while (ones < x) {
 261     x-=ones;left++;
 262     if (left > integers) return n;
 263           j = data[left];
 264       ones = popcount(j);
 265         }
 266   //sequential search using popcount over a char
 267   left=left*b;
 268   rankmid = popcount8(j);
 269   if (rankmid < x) {
 270     j=j>>8;
 271     x-=rankmid;
 272     left+=8;
 273     rankmid = popcount8(j);
 274     if (rankmid < x) {
 275       j=j>>8;
 276       x-=rankmid;
 277       left+=8;
 278       rankmid = popcount8(j);
 279       if (rankmid < x) {
 280         j=j>>8;
 281         x-=rankmid;
 282         left+=8;
 283       }
 284     }
 285   }
 286
 287   // then sequential search bit a bit
 288         while (x>0) {
 289     if  (j&1) x--;
 290     j=j>>1;
 291     left++;
 292   }
 293   return left-1;
 294 }
 295
 296 uint static_bitsequence_brw32::select0(uint x) {
 297   // returns i such that x=rank_0(i) && rank_0(i-1)<x or n if that i not exist
 298   // first binary search over first level rank structure
 299   // then sequential search using popcount over a int
 300   // then sequential search using popcount over a char
 301   // then sequential search bit a bit
 302
 303   //binary search over first level rank structure
 304   if(x==0) return 0;
 305   uint l=0, r=n/s;
 306   uint mid=(l+r)/2;
 307   uint rankmid = mid*factor*W-Rs[mid];
 308   while (l<=r) {
 309     if (rankmid<x)
 310       l = mid+1;
 311     else
 312       r = mid-1;
 313     mid = (l+r)/2;
 314     rankmid = mid*factor*W-Rs[mid];
 315   }
 316   //sequential search using popcount over a int
 317   uint left;
 318   left=mid*factor;
 319   x-=rankmid;
 320   uint j=data[left];
 321   uint zeros = W-popcount(j);
 322   while (zeros < x) {
 323     x-=zeros;left++;
 324     if (left > integers) return n;
 325     j = data[left];
 326     zeros = W-popcount(j);
 327   }
 328   //sequential search using popcount over a char
 329   left=left*b;
 330   rankmid = 8-popcount8(j);
 331   if (rankmid < x) {
 332     j=j>>8;
 333     x-=rankmid;
 334     left+=8;
 335     rankmid = 8-popcount8(j);
 336     if (rankmid < x) {
 337       j=j>>8;
 338       x-=rankmid;
 339       left+=8;
 340       rankmid = 8-popcount8(j);
 341       if (rankmid < x) {
 342         j=j>>8;
 343         x-=rankmid;
 344         left+=8;
 345       }
 346     }
 347   }
 348
 349   // then sequential search bit a bit
 350   while (x>0) {
 351     if  (j%2 == 0 ) x--;
 352     j=j>>1;
 353     left++;
 354   }
 355   left--;
 356   if (left > n)  return n;
 357   else return left;
 358 }