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   if (owner) 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->owner = true;
 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 (owner?n:0)+(n/s)*sizeof(uint)*8 +sizeof(static_bitsequence_brw32)*8;
 156 }
 157
 158 uint static_bitsequence_brw32::size() {
 159   return SpaceRequirementInBits()/8;
 160 }
 161
 162 uint static_bitsequence_brw32::SpaceRequirement() {
 163   return (owner?n:0)/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
 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 }