BitRank.cpp

   1 #include "BitRank.h"
   2
   3 /*****************************************************************************
   4  * Copyright (C) 2005, Rodrigo Gonzalez, all rights reserved.                *
   5  *                                                                           *
   6  * New RANK, SELECT, SELECT-NEXT and SPARSE RANK implementations.            *
   7  *                                                                           *
   8  * This library is free software; you can redistribute it and/or             *
   9  * modify it under the terms of the GNU Lesser General Public                *
  10  * License as published by the Free Software Foundation; either              *
  11  * version 2.1 of the License, or (at your option) any later version.        *
  12  *                                                                           *
  13  * This library is distributed in the hope that it will be useful,           *
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of            *
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU         *
  16  * Lesser General Public License for more details.                           *
  17  *                                                                           *
  18  * You should have received a copy of the GNU Lesser General Public          *
  19  * License along with this library; if not, write to the Free Software       *
  20  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA *
  21  ****************************************************************************/
  22
  23 // Modified by Niko Välimäki
  24
  25 /////////////
  26 //Rank(B,i)//
  27 /////////////
  28 //This Class use a superblock size of 256-512 bits
  29 //and a block size of 32-64 bits also
  30
  31
  32 const unsigned char __popcount_tab[] =
  33 {
  34 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,
  35 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,
  36 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,
  37 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,
  38 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,
  39 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,
  40 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,
  41 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,
  42 };
  43
  44 const unsigned char select_tab[] =
  45 {
  46 0,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,
  47
  48 6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,
  49
  50 7,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,
  51
  52 6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,
  53
  54 8,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,
  55
  56 6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,
  57
  58 7,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,
  59
  60 6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,
  61 };
  62
  63
  64 // bits needed to represent a number between 0 and n
  65 inline ulong bits (ulong n){
  66         ulong b = 0;
  67         while (n) { b++; n >>= 1; }
  68         return b;
  69 }
  70
  71 #if W == 32
  72     // 32 bit version
  73     inline unsigned popcount (register ulong x){
  74         return __popcount_tab[(x >>  0) & 0xff]  + __popcount_tab[(x >>  8) & 0xff]  + __popcount_tab[(x >> 16) & 0xff] + __popcount_tab[(x >> 24) & 0xff];
  75     }
  76 #else
  77     // 64 bit version
  78     inline unsigned popcount (register ulong x){
  79         return __popcount_tab[(x >>  0) & 0xff]  + __popcount_tab[(x >>  8) & 0xff]  + __popcount_tab[(x >> 16) & 0xff] + __popcount_tab[(x >> 24) & 0xff] + __popcount_tab[(x >> 32) & 0xff] + __popcount_tab[(x >> 40) & 0xff] + __popcount_tab[(x >> 48) & 0xff] + __popcount_tab[(x >> 56) & 0xff];
  80     }
  81 #endif
  82
  83 inline unsigned popcount16 (register int x){
  84   return __popcount_tab[x & 0xff]  + __popcount_tab[(x >>  8) & 0xff];
  85 }
  86
  87 inline unsigned popcount8 (register int x){
  88   return __popcount_tab[x & 0xff];
  89 }
  90
  91 BitRank::BitRank(ulong *bitarray, ulong n, bool owner) {
  92     data=bitarray;
  93     this->owner = owner;
  94     this->n=n;  // length of bitarray in bits
  95     ulong aux=(n+1)%W;
  96     if (aux != 0)
  97         integers = (n+1)/W+1;
  98     else
  99         integers = (n+1)/W;
 100     BuildRank();
 101 }
 102
 103 BitRank::~BitRank() {
 104     delete Rs;
 105     delete [] Rb;
 106     if (owner) delete [] data;
 107 }
 108
 109 //Build the rank (blocks and superblocks)
 110 void BitRank::BuildRank()
 111 {
 112     ulong num_sblock = n/s;
 113     ulong num_block = n/W;
 114     Rs = new BlockArray(num_sblock+1, Tools::CeilLog2(n));//+1 we add the 0 pos
 115     Rb = new uchar[num_block+1];//+1 we add the 0 pos
 116
 117         ulong j;
 118     (*Rs)[0] = 0lu;
 119
 120     for (j=1;j<=num_sblock;j++)
 121         {
 122                         (*Rs)[j]=BuildRankSub((j-1)*superFactor,superFactor)+(*Rs)[j-1];
 123                 }
 124
 125     Rb[0]=0;
 126     for (ulong k=1;k<=num_block;k++) {
 127         j = k / superFactor;
 128         Rb[k]=BuildRankSub(j*superFactor, k%superFactor);
 129           }
 130 }
 131
 132 ulong BitRank::BuildRankSub(ulong ini, ulong bloques){
 133     ulong rank=0,aux;
 134
 135
 136         for(ulong i=ini;i<ini+bloques;i++) {
 137                 if (i < integers) {
 138                         aux=data[i];
 139                         rank+=popcount(aux);
 140                 }
 141         }
 142      return rank; //return the numbers of 1's in the interval
 143 }
 144
 145
 146 //this rank ask from 0 to n-1
 147 ulong BitRank::rank(ulong i) {
 148     ++i; // the following gives sum of 1s before i
 149     return (*Rs)[i>>8]+Rb[i>>wordShift]
 150         +popcount(data[i >> wordShift] & ((1lu << (i & Wminusone))-1));
 151 }
 152
 153 ulong BitRank::select(ulong x) {
 154     // returns i such that x=rank(i) && rank(i-1)<x or n if that i not exist
 155     // first binary search over first level rank structure
 156     // then sequential search using popcount over a int
 157     // then sequential search using popcount over a char
 158     // then sequential search bit a bit
 159
 160     //binary search over first level rank structure
 161     if (x == 0)
 162         return 0;
 163
 164     ulong l=0, r=n/s;
 165     ulong mid=(l+r)/2;
 166     ulong rankmid = (*Rs)[mid];
 167     while (l<=r) {
 168         if (rankmid<x)
 169             l = mid+1;
 170         else
 171             r = mid-1;
 172         mid = (l+r)/2;
 173         rankmid = (*Rs)[mid];
 174     }
 175     //sequential search using popcount over a int
 176     ulong left;
 177     left=mid*superFactor;
 178     x-=rankmid;
 179     ulong j = data[left];
 180
 181     unsigned ones = popcount(j);
 182     while (ones < x) {
 183         x-=ones;left++;
 184         if (left > integers)
 185             return n;
 186
 187         j = data[left];
 188
 189         ones = popcount(j);
 190     }
 191     //sequential search using popcount over a char
 192     left=left*W;
 193     rankmid = popcount8(j);
 194     if (rankmid < x) {
 195         j=j>>8;
 196         x-=rankmid;
 197         left+=8;
 198         rankmid = popcount8(j);
 199         if (rankmid < x) {
 200             j=j>>8;
 201             x-=rankmid;
 202             left+=8;
 203             rankmid = popcount8(j);
 204             if (rankmid < x) {
 205                 j=j>>8;
 206                 x-=rankmid;
 207                 left+=8;
 208             }
 209         }
 210     }
 211
 212     // then sequential search bit a bit
 213     while (x>0) {
 214         if  (j&1lu) x--;
 215         j=j>>1;
 216         left++;
 217     }
 218     return left-1;
 219 }
 220
 221 ulong BitRank::select0(ulong x) {
 222     // returns i such that x=rank0(i) && rank0(i-1)<x or n if that i not exist
 223     // first binary search over first level rank structure
 224     // then sequential search using popcount over a int
 225     // then sequential search using popcount over a char
 226     // then sequential search bit a bit
 227
 228     //binary search over first level rank structure
 229     if (x == 0)
 230         return 0;
 231
 232     ulong l=0, r=n/s;
 233     ulong mid=(l+r)/2;
 234     ulong rankmid = mid * s - (*Rs)[mid];
 235     while (l<=r) {
 236         if (rankmid<x)
 237             l = mid+1;
 238         else
 239             r = mid-1;
 240         mid = (l+r)/2;
 241         rankmid = mid * s - (*Rs)[mid];
 242     }
 243
 244     //sequential search using popcount over a int
 245     ulong left;
 246     left=mid*superFactor;
 247     x-=rankmid;
 248     ulong j = data[left];
 249
 250     unsigned zeros = W - popcount(j);
 251     while (zeros < x) {
 252         x-=zeros;
 253         left++;
 254         if (left > integers)
 255             return n;
 256
 257         j = data[left];
 258         zeros = W - popcount(j);
 259     }
 260
 261     //sequential search using popcount over a char
 262     left=left*W;
 263     rankmid = 8 - popcount8(j);
 264     if (rankmid < x) {
 265         j=j>>8;
 266         x-=rankmid;
 267         left+=8;
 268         rankmid = 8 - popcount8(j);
 269         if (rankmid < x) {
 270             j=j>>8;
 271             x-=rankmid;
 272             left+=8;
 273             rankmid = 8 - popcount8(j);
 274             if (rankmid < x) {
 275                 j=j>>8;
 276                 x-=rankmid;
 277                 left+=8;
 278             }
 279         }
 280     }
 281
 282     // then sequential search bit a bit
 283     while (x>0) {
 284         if  (!(j&1lu)) x--;
 285         j=j>>1;
 286         left++;
 287     }
 288     return left - 1;
 289 }
 290
 291
 292 bool BitRank::IsBitSet(ulong i) {
 293     return (1lu << (i % W)) & data[i/W];
 294 }
 295
 296 ulong BitRank::NumberOfBits() {
 297     return n;
 298 }
 299
 300 /**
 301  * Saving data fields:
 302
 303     ulong n;
 304     ulong *data; //here is the bit-arra
 305  */
 306 void BitRank::Save(FILE *file)
 307 {
 308     if (std::fwrite(&(this->n), sizeof(ulong), 1, file) != 1)
 309         throw std::runtime_error("BitRank::Save(): file write error (n).");
 310
 311     for (ulong offset = 0; offset < integers; ++offset)
 312         if (std::fwrite(this->data + offset, sizeof(ulong), 1, file) != 1)
 313             throw std::runtime_error("BitRank::Save(): file write error (data).");
 314 }
 315
 316 BitRank::BitRank(FILE *file)
 317 {
 318     owner = 1;
 319     if (std::fread(&(this->n), sizeof(ulong), 1, file) != 1)
 320         throw std::runtime_error("BitRank::Load(): file read error (n).");
 321
 322     ulong aux=(n+1)%W;
 323     if (aux != 0)
 324         integers = (n+1)/W+1;
 325     else
 326         integers = (n+1)/W;
 327
 328     data = new ulong[integers];
 329     for (ulong offset = 0; offset < integers; ++offset)
 330         if (std::fread(this->data + offset, sizeof(ulong), 1, file) != 1)
 331             throw std::runtime_error("BitRank::Load(): file read error (data).");
 332
 333     BuildRank();
 334 }