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