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