incbwt/bits/bitbuffer.h

   1 #ifndef BITBUFFER_H
   2 #define BITBUFFER_H
   3
   4 #include <algorithm>
   5 #include <cstdlib>
   6 #include <fstream>
   7 #include <iostream>
   8 #include <cstring>  // defines std::memset, added by Kim
   9
  10 #include "../misc/definitions.h"
  11
  12
  13 namespace CSA
  14 {
  15
  16
  17 template<class Data>
  18 class GenericBitBuffer
  19 {
  20   public:
  21     GenericBitBuffer(usint words);
  22     GenericBitBuffer(usint _items, usint item_size);
  23     GenericBitBuffer(std::ifstream& file, usint words);
  24     GenericBitBuffer(std::ifstream& file, usint _items, usint item_size);
  25     GenericBitBuffer(Data* buffer, usint words);
  26     GenericBitBuffer(Data* buffer, usint _items, usint item_size);
  27     ~GenericBitBuffer();
  28
  29     void writeBuffer(std::ofstream& file, bool erase = true);
  30     void readBuffer(std::ifstream& file, usint words, bool erase = true);
  31     void setBuffer(Data* buffer, usint words);
  32
  33     // We assume we are already using a buffer not owned by this.
  34     inline void moveBuffer(Data* buffer)
  35     {
  36       this->data = buffer;
  37       this->pos = 0;
  38       this->bits = DATA_BITS;
  39       this->current = 0;
  40     }
  41
  42 //--------------------------------------------------------------------------
  43
  44     inline void reset(bool erase)
  45     {
  46       this->pos = 0;
  47       this->bits = DATA_BITS;
  48       this->current = 0;
  49       if(erase)
  50       {
  51         memset(this->data, 0, this->size * sizeof(Data));
  52       }
  53     }
  54
  55     inline void skipBits(usint count)
  56     {
  57       if(count < this->bits)
  58       {
  59         this->bits -= count;
  60         return;
  61       }
  62
  63       count -= this->bits;
  64       this->pos += 1 + count / DATA_BITS;
  65       this->bits = DATA_BITS - count % DATA_BITS;
  66     }
  67
  68     inline void rewind(usint count)
  69     {
  70       this->bits += count;
  71       if(this->bits > DATA_BITS)
  72       {
  73         usint back = (this->bits - 1) / DATA_BITS;
  74         this->pos -= back;
  75         this->bits -= back * DATA_BITS;
  76       }
  77     }
  78
  79 //--------------------------------------------------------------------------
  80
  81     inline usint bitsLeft()
  82     {
  83       return this->bits + DATA_BITS * (this->size - this->pos - 1);
  84     }
  85
  86     inline void writeBits(usint value, usint count)
  87     {
  88       while(count >= this->bits)
  89       {
  90         count -= this->bits;
  91         this->data[this->pos] |= GET(LOWER(value, count), this->bits);
  92         this->pos++; this->bits = DATA_BITS;
  93       }
  94       if(count > 0)
  95       {
  96         this->bits -= count;
  97         this->data[this->pos] |= HIGHER(GET(value, count), this->bits);
  98       }
  99     }
 100
 101     // Returns nonzero if bit is 1
 102     inline usint readBit()
 103     {
 104       this->bits--;
 105       usint bit = this->data[this->pos] & ((usint)1 << this->bits);
 106
 107       if(this->bits == 0) { this->pos++; this->bits = DATA_BITS; }
 108
 109       return bit;
 110     }
 111
 112     inline usint readBits(usint count)
 113     {
 114       usint value = 0;
 115
 116       while(count >= this->bits)
 117       {
 118         count -= this->bits;
 119         value |= HIGHER(GET(this->data[this->pos], this->bits), count);
 120         this->pos++; this->bits = DATA_BITS;
 121       }
 122       if(count > 0)
 123       {
 124         this->bits -= count;
 125         value |= GET(LOWER(this->data[this->pos], this->bits), count);
 126       }
 127
 128       return value;
 129     }
 130
 131 //--------------------------------------------------------------------------
 132
 133     /*
 134       These operations work on fixed-size items.
 135     */
 136
 137     inline usint getItemSize()
 138     {
 139       return this->item_bits;
 140     }
 141
 142 /*
 143     inline void setItemSize(usint new_size)
 144     {
 145       if(new_size == 0) { return; }
 146       this->item_bits = new_size;
 147     }
 148 */
 149
 150     inline void goToItem(usint item)
 151     {
 152       usint b = item * this->item_bits;
 153       this->pos = b / DATA_BITS;
 154       this->bits = DATA_BITS - b % DATA_BITS;
 155       this->current = item;
 156     }
 157
 158     inline usint readItem()
 159     {
 160       this->current++;
 161       return this->readBits(this->item_bits);
 162     }
 163
 164     inline usint readItem(usint item)
 165     {
 166       this->goToItem(item);
 167       return this->readItem();
 168     }
 169
 170     inline usint readFirstItem()
 171     {
 172       return this->readItem(0);
 173     }
 174
 175     inline bool hasNextItem()
 176     {
 177       return (this->current < this->items);
 178     }
 179
 180     inline void writeItem(usint item)
 181     {
 182       this->writeBits(item, this->item_bits);
 183       this->current++;
 184     }
 185
 186     inline void skipItem()
 187     {
 188       this->skipBits(this->item_bits);
 189       this->current++;
 190     }
 191
 192 //--------------------------------------------------------------------------
 193
 194     /*
 195       Delta coding for positive integers
 196     */
 197
 198     inline bool canDeltaCode(usint value)
 199     {
 200       return this->deltaCodeLength(value) <= this->bitsLeft();
 201     }
 202
 203     inline usint deltaCodeLength(usint value)
 204     {
 205       usint len = length(value);
 206       usint llen = length(len);
 207       return (len + llen + llen - 2);
 208     }
 209
 210     // This version returns false if there is no space left for the encoding.
 211     inline bool writeDeltaCode(usint value)
 212     {
 213       usint len = length(value);
 214       usint llen = length(len);
 215
 216       if(len + llen + llen - 2 > this->bitsLeft()) { return false; }
 217
 218       // this->writeBits(0, llen - 1); // Now included in the next writeBits()
 219       this->writeBits(len, llen + llen - 1);
 220       this->writeBits(value, len - 1);
 221       return true;
 222     }
 223
 224     // This version assumes the code fits into the buffer.
 225     inline void writeDeltaCodeDirect(usint value)
 226     {
 227       usint len = length(value);
 228       usint llen = length(len);
 229
 230       // this->writeBits(0, llen - 1); // Now included in the next writeBits()
 231       this->writeBits(len, llen + llen - 1);
 232       this->writeBits(value, len - 1);
 233     }
 234
 235     // We assume the code fits into usint:
 236     //  32-bit:  value < 2^24
 237     //  64-bit:  value < 2^54
 238     inline void writeDeltaCodeFast(usint value)
 239     {
 240       usint len = length(value);
 241
 242       value ^= ((usint)1 << (len - 1));
 243       this->writeBits((len << (len - 1)) | value, len + 2 * length(len) - 2);
 244     }
 245
 246     inline usint readDeltaCode()
 247     {
 248       usint len = 0;
 249       while(this->readBit() == 0) { len++; }
 250
 251       usint temp = (((usint)1 << len) | this->readBits(len)) - 1;
 252       temp = ((usint)1 << temp) | this->readBits(temp);
 253       return temp;
 254     }
 255
 256 //--------------------------------------------------------------------------
 257
 258     /*
 259       Gamma coding for positive integers
 260     */
 261
 262     inline bool canGammaCode(usint value)
 263     {
 264       return this->gammaCodeLength(value) <= this->bitsLeft();
 265     }
 266
 267     inline usint gammaCodeLength(usint value)
 268     {
 269       return 2 * length(value) - 1;
 270     }
 271
 272     // This version returns false if there is no space left for the encoding.
 273     inline bool writeGammaCode(usint value)
 274     {
 275       usint len = length(value);
 276
 277       if(len > this->bitsLeft()) { return false; }
 278
 279       this->writeBits(0, len - 1);
 280       this->writeBits(value, len);
 281       return true;
 282     }
 283
 284     // This version assumes the code fits into the buffer.
 285     inline void writeGammaCodeDirect(usint value)
 286     {
 287       usint len = length(value);
 288
 289       this->writeBits(0, len - 1);
 290       this->writeBits(value, len);
 291     }
 292
 293     // We assume the code fits into usint:
 294     //  32-bit:  value < 2^16
 295     //  64-bit:  value < 2^32
 296     inline void writeGammaCodeFast(usint value)
 297     {
 298       this->writeBits(value, this->gammaCodeLength(value));
 299     }
 300
 301     inline usint readGammaCode()
 302     {
 303       usint len = 1;
 304       while(this->readBit() == 0) { len++; }
 305       return ((usint)1 << len) | this->readBits(len);
 306     }
 307
 308 //--------------------------------------------------------------------------
 309
 310     usint reportSize();
 311
 312 //--------------------------------------------------------------------------
 313
 314   private:
 315     Data* data;
 316     usint size, pos, bits;
 317     usint item_bits, items, current;
 318     bool  free_buffer;
 319
 320     const static usint DATA_BITS = sizeof(Data) * CHAR_BIT;
 321
 322     inline static usint bitsToData(usint _bits) { return (_bits + DATA_BITS - 1) / DATA_BITS; }
 323 };
 324
 325
 326 typedef GenericBitBuffer<uchar> BitBuffer;
 327 typedef GenericBitBuffer<usint> FastBitBuffer;
 328
 329
 330 //--------------------------------------------------------------------------
 331
 332
 333 template<class Data>
 334 GenericBitBuffer<Data>::GenericBitBuffer(usint words) :
 335   size(words),
 336   pos(0),
 337   bits(DATA_BITS),
 338   item_bits(1),
 339   items(0),
 340   current(0),
 341   free_buffer(true)
 342 {
 343   this->data = new Data[words];
 344   memset(this->data, 0, words * sizeof(Data));
 345 }
 346
 347 template<class Data>
 348 GenericBitBuffer<Data>::GenericBitBuffer(usint _items, usint item_size) :
 349   pos(0),
 350   bits(DATA_BITS),
 351   item_bits(item_size),
 352   items(_items),
 353   current(0),
 354   free_buffer(true)
 355 {
 356   this->size = bitsToData(items * item_size);
 357   this->data = new Data[this->size];
 358   memset(this->data, 0, this->size * sizeof(Data));
 359 }
 360
 361 template<class Data>
 362 GenericBitBuffer<Data>::GenericBitBuffer(std::ifstream& file, usint words) :
 363   size(words),
 364   pos(0),
 365   bits(DATA_BITS),
 366   item_bits(1),
 367   items(0),
 368   current(0),
 369   free_buffer(true)
 370 {
 371   this->data = new Data[words];
 372   memset(this->data, 0, words * sizeof(Data));
 373   file.read((char*)this->data, words * sizeof(Data));
 374 }
 375
 376 template<class Data>
 377 GenericBitBuffer<Data>::GenericBitBuffer(std::ifstream& file, usint _items, usint item_size) :
 378   size(BITS_TO_WORDS(_items * item_size)),
 379   pos(0),
 380   bits(DATA_BITS),
 381   item_bits(item_size),
 382   items(_items),
 383   current(0),
 384   free_buffer(true)
 385 {
 386   this->data = new Data[this->size];
 387   memset(this->data, 0, this->size * sizeof(Data));
 388   file.read((char*)this->data, this->size * sizeof(Data));
 389 }
 390
 391 template<class Data>
 392 GenericBitBuffer<Data>::GenericBitBuffer(Data* buffer, usint words) :
 393   size(words),
 394   pos(0),
 395   bits(DATA_BITS),
 396   item_bits(1),
 397   items(0),
 398   current(0),
 399   free_buffer(false)
 400 {
 401   this->data = buffer;
 402 }
 403
 404 template<class Data>
 405 GenericBitBuffer<Data>::GenericBitBuffer(Data* buffer, usint _items, usint item_size) :
 406   size(BITS_TO_WORDS(_items * item_size)),
 407   pos(0),
 408   bits(DATA_BITS),
 409   item_bits(item_size),
 410   items(_items),
 411   current(0),
 412   free_buffer(false)
 413 {
 414   this->data = buffer;
 415 }
 416
 417 template<class Data>
 418 GenericBitBuffer<Data>::~GenericBitBuffer()
 419 {
 420   if(this->free_buffer)
 421   {
 422     delete[] this->data;
 423   }
 424 }
 425
 426 //--------------------------------------------------------------------------
 427
 428 template<class Data>
 429 void
 430 GenericBitBuffer<Data>::writeBuffer(std::ofstream& file, bool erase)
 431 {
 432   file.write((char*)this->data, this->size * sizeof(Data));
 433   this->reset(erase);
 434 }
 435
 436 template<class Data>
 437 void
 438 GenericBitBuffer<Data>::readBuffer(std::ifstream& file, usint words, bool erase)
 439 {
 440   if(words > this->size || !(this->free_buffer))
 441   {
 442     if(this->free_buffer)
 443     {
 444       delete[] this->data;
 445     }
 446     this->size = words;
 447     this->data = new Data[words];
 448     this->free_buffer = true;
 449   }
 450
 451   this->reset(erase);
 452   file.read((char*)this->data, words * sizeof(Data));
 453 }
 454
 455 template<class Data>
 456 void
 457 GenericBitBuffer<Data>::setBuffer(Data* buffer, usint words)
 458 {
 459   if(this->free_buffer)
 460   {
 461     delete[] this->data;
 462     this->free_buffer = false;
 463   }
 464
 465   this->data = buffer;
 466   this->size = words;
 467   this->reset(false);
 468 }
 469
 470 //--------------------------------------------------------------------------
 471
 472 template<class Data>
 473 usint
 474 GenericBitBuffer<Data>::reportSize()
 475 {
 476   usint bytes = sizeof(*this);
 477   if(this->free_buffer) { bytes += this->size * sizeof(Data); }
 478   return bytes;
 479 }
 480
 481 //--------------------------------------------------------------------------
 482
 483
 484 } // namespace CSA
 485
 486
 487 #endif // BITBUFFER_H