incbwt/bits/bitbuffer.h

   1 #ifndef BITBUFFER_H
   2 #define BITBUFFER_H
   3
   4 #include <algorithm>
   5 #include <cstdlib>
   6 #include <cstring>
   7 #include <fstream>
   8 #include <iostream>
   9
  10 #include "../misc/definitions.h"
  11
  12
  13 namespace CSA
  14 {
  15
  16
  17 class ReadBuffer
  18 {
  19   public:
  20     ReadBuffer(std::ifstream& file, usint words) :
  21       size(words),
  22       item_bits(1),
  23       items(0),
  24       free_buffer(true)
  25     {
  26       usint* buffer = new usint[this->size];
  27       memset(buffer, 0, this->size * sizeof(usint));
  28       file.read((char*)buffer, this->size * sizeof(usint));
  29       this->data = buffer;
  30       this->reset();
  31     }
  32
  33     ReadBuffer(std::ifstream& file, usint _items, usint item_size) :
  34       item_bits(item_size),
  35       items(_items),
  36       free_buffer(true)
  37     {
  38       this->size = bitsToWords(this->items * this->item_bits);
  39       usint* buffer = new usint[this->size];
  40       memset(buffer, 0, this->size * sizeof(usint));
  41       file.read((char*)buffer, this->size * sizeof(usint));
  42       this->data = buffer;
  43       this->reset();
  44     }
  45
  46     ReadBuffer(std::FILE* file, usint _items, usint item_size) :
  47       item_bits(item_size),
  48       items(_items),
  49       free_buffer(true)
  50     {
  51       this->size = bitsToWords(this->items * this->item_bits);
  52       usint* buffer = new usint[this->size];
  53       memset(buffer, 0, this->size * sizeof(usint));
  54       if (fread(buffer, sizeof(usint), this->size, file) != this->size)
  55       {
  56           std::cerr << "ReadBuffer constructor: Unable to read file" << std::endl;
  57           std::exit(1);
  58       }
  59       this->data = buffer;
  60       this->reset();
  61     }
  62
  63     // This version does not delete the data when deleted.
  64     ReadBuffer(const usint* buffer, usint words) :
  65       size(words),
  66       item_bits(1),
  67       items(0),
  68       free_buffer(false)
  69     {
  70       this->data = buffer;
  71       this->reset();
  72     }
  73
  74     // This version does not delete the data when deleted.
  75     ReadBuffer(const usint* buffer, usint _items, usint item_size) :
  76       item_bits(item_size),
  77       items(_items),
  78       free_buffer(false)
  79     {
  80       this->size = bitsToWords(this->items * this->item_bits);
  81       this->data = buffer;
  82       this->reset();
  83     }
  84
  85     // This version does not delete the data when deleted.
  86     ReadBuffer(const ReadBuffer& original) :
  87       data(original.data),
  88       size(original.size),
  89       item_bits(original.item_bits),
  90       items(original.items),
  91       free_buffer(false)
  92     {
  93       this->reset();
  94     }
  95
  96     ~ReadBuffer()
  97     {
  98       if(this->free_buffer)
  99       {
 100         delete[] this->data;
 101       }
 102     }
 103
 104 //--------------------------------------------------------------------------
 105
 106     void claimData()
 107     {
 108       this->free_buffer = true;
 109     }
 110
 111     void writeBuffer(std::ofstream& file) const
 112     {
 113       file.write((const char*)this->data, this->size * sizeof(usint));
 114     }
 115     void writeBuffer(std::FILE* file) const
 116     {
 117         fwrite(this->data, sizeof(usint), this->size, file);
 118     }
 119
 120     // The buffer will no longer own the data.
 121     void moveBuffer(const usint* buffer)
 122     {
 123       if(this->free_buffer)
 124       {
 125         delete[] this->data;
 126       }
 127       this->free_buffer = false;
 128
 129       this->data = buffer;
 130       this->reset();
 131     }
 132
 133     usint reportSize() const
 134     {
 135       usint bytes = sizeof(*this);
 136       if(this->free_buffer) { bytes += this->size * sizeof(usint); }
 137       return bytes;
 138     }
 139
 140 //--------------------------------------------------------------------------
 141
 142     inline void reset()
 143     {
 144       this->pos = 0;
 145       this->bits = WORD_BITS;
 146       this->current = 0;
 147     }
 148
 149     inline void skipBits(usint count)
 150     {
 151       if(count < this->bits)
 152       {
 153         this->bits -= count;
 154         return;
 155       }
 156
 157       count -= this->bits;
 158       this->pos += 1 + count / WORD_BITS;
 159       this->bits = WORD_BITS - count % WORD_BITS;
 160     }
 161
 162 //--------------------------------------------------------------------------
 163
 164     inline usint bitsLeft() const
 165     {
 166       return this->bits + WORD_BITS * (this->size - this->pos - 1);
 167     }
 168
 169     // Returns nonzero if bit is 1
 170     inline usint readBit()
 171     {
 172       this->bits--;
 173       usint bit = this->data[this->pos] & ((usint)1 << this->bits);
 174
 175       if(this->bits == 0) { this->pos++; this->bits = WORD_BITS; }
 176
 177       return bit;
 178     }
 179
 180     inline usint readBits(usint count)
 181     {
 182       usint value = 0;
 183
 184       if(count >= this->bits)
 185       {
 186         count -= this->bits;
 187         value |= HIGHER(GET(this->data[this->pos], this->bits), count);
 188         this->pos++; this->bits = WORD_BITS;
 189       }
 190       if(count > 0)
 191       {
 192         this->bits -= count;
 193         value |= GET(LOWER(this->data[this->pos], this->bits), count);
 194       }
 195
 196       return value;
 197     }
 198
 199 //--------------------------------------------------------------------------
 200
 201     /*
 202       These operations work on 4-bit nibbles.
 203       Do not use these with the bit-level operations.
 204     */
 205
 206     inline usint readNibble()
 207     {
 208       this->bits -= 4;
 209       usint value = GET(LOWER(this->data[this->pos], this->bits), 4);
 210
 211       if(this->bits == 0) { this->pos++; this->bits = WORD_BITS; }
 212
 213       return value;
 214     }
 215
 216     // Nibble code for positive integers.
 217     inline usint readNibbleCode()
 218     {
 219       usint temp, value = 0, shift = 0;
 220       do
 221       {
 222         temp = this->readNibble();
 223         value |= (temp & 0x7) << shift;
 224         shift += 3;
 225       }
 226       while((temp & 0x8) == 0);
 227
 228       return value + 1;
 229     }
 230
 231 //--------------------------------------------------------------------------
 232
 233     /*
 234       These operations work on fixed-size items. No sanity checks are made
 235       for parameter values.
 236     */
 237
 238     inline usint getItemSize() const
 239     {
 240       return this->item_bits;
 241     }
 242
 243     inline void goToItem(usint item)
 244     {
 245       usint b = item * this->item_bits;
 246       this->pos = b / WORD_BITS;
 247       this->bits = WORD_BITS - b % WORD_BITS;
 248       this->current = item;
 249     }
 250
 251     inline usint readItem()
 252     {
 253       this->current++;
 254       return this->readBits(this->item_bits);
 255     }
 256
 257     inline usint readItem(usint item)
 258     {
 259       this->goToItem(item);
 260       return this->readItem();
 261     }
 262
 263     inline usint readFirstItem()
 264     {
 265       return this->readItem(0);
 266     }
 267
 268     inline usint readItemConst(usint item) const
 269     {
 270       usint b = item * this->item_bits;
 271       usint p = b / WORD_BITS;
 272       b = WORD_BITS - b % WORD_BITS;
 273
 274       usint c = this->item_bits;
 275       usint value = 0;
 276
 277       if(c >= b)
 278       {
 279         c -= b;
 280         value |= HIGHER(GET(this->data[p], b), c);
 281         p++; b = WORD_BITS;
 282       }
 283       if(c > 0)
 284       {
 285         b -= c;
 286         value |= GET(LOWER(this->data[p], b), c);
 287       }
 288
 289       return value;
 290     }
 291
 292     inline bool hasNextItem() const
 293     {
 294       return (this->current < this->items);
 295     }
 296
 297     inline void skipItem()
 298     {
 299       this->skipBits(this->item_bits);
 300       this->current++;
 301     }
 302
 303 //--------------------------------------------------------------------------
 304
 305     /*
 306       Delta coding for positive integers
 307     */
 308
 309     inline usint readDeltaCode()
 310     {
 311       usint len = 0;
 312       while(this->readBit() == 0) { len++; }
 313
 314       usint temp = (((usint)1 << len) | this->readBits(len)) - 1;
 315       temp = ((usint)1 << temp) | this->readBits(temp);
 316       return temp;
 317     }
 318
 319 //--------------------------------------------------------------------------
 320
 321   private:
 322     const usint* data;
 323     usint size, item_bits, items;
 324     bool  free_buffer;
 325
 326     // Iterator data
 327     usint pos, bits, current;
 328
 329     inline static usint bitsToWords(usint _bits) { return (_bits + WORD_BITS - 1) / WORD_BITS; }
 330
 331     // These are not allowed.
 332     ReadBuffer();
 333     ReadBuffer& operator = (const ReadBuffer&);
 334 };
 335
 336
 337 //--------------------------------------------------------------------------
 338
 339
 340 class WriteBuffer
 341 {
 342   public:
 343     WriteBuffer(usint words) :
 344       size(words),
 345       item_bits(1),
 346       items(0),
 347       free_buffer(true)
 348     {
 349       this->data = new usint[words];
 350       memset(this->data, 0, this->size * sizeof(usint));
 351       this->reset();
 352     }
 353
 354     WriteBuffer(usint _items, usint item_size) :
 355       item_bits(item_size),
 356       items(_items),
 357       free_buffer(true)
 358     {
 359       this->size = bitsToWords(this->items * this->item_bits);
 360       this->data = new usint[this->size];
 361       memset(this->data, 0, this->size * sizeof(usint));
 362       this->reset();
 363     }
 364
 365     // This version does not delete the data when deleted.
 366     WriteBuffer(usint* buffer, usint words) :
 367       size(words),
 368       item_bits(1),
 369       items(0),
 370       free_buffer(false)
 371     {
 372       this->data = buffer;
 373       this->reset();
 374     }
 375
 376     // This version does not delete the data when deleted.
 377     WriteBuffer(usint* buffer, usint _items, usint item_size) :
 378       item_bits(item_size),
 379       items(_items),
 380       free_buffer(false)
 381     {
 382       this->size = bitsToWords(this->items * this->item_bits);
 383       this->data = buffer;
 384       this->reset();
 385     }
 386
 387     ~WriteBuffer()
 388     {
 389       if(this->free_buffer)
 390       {
 391         delete[] this->data;
 392       }
 393     }
 394
 395 //--------------------------------------------------------------------------
 396
 397     // This transfers the ownership of the data to the read buffer.
 398     ReadBuffer* getReadBuffer()
 399     {
 400       ReadBuffer* buffer;
 401       if(this->items > 0)
 402       {
 403         buffer = new ReadBuffer(this->data, this->items, this->item_bits);
 404       }
 405       else
 406       {
 407         buffer = new ReadBuffer(this->data, this->size);
 408       }
 409
 410       if(this->free_buffer)
 411       {
 412         buffer->claimData();
 413         this->free_buffer = false;
 414       }
 415
 416       return buffer;
 417     }
 418
 419     void writeBuffer(std::ofstream& file) const
 420     {
 421       file.write((char*)this->data, this->size * sizeof(usint));
 422     }
 423     void writeBuffer(std::FILE *file) const
 424     {
 425         fwrite(this->data, sizeof(usint), this->size, file);
 426     }
 427
 428     // The buffer will no longer own the data.
 429     void moveBuffer(usint* buffer)
 430     {
 431       if(this->free_buffer)
 432       {
 433         delete[] this->data;
 434       }
 435       this->free_buffer = false;
 436
 437       this->data = buffer;
 438       this->reset();
 439     }
 440
 441     usint reportSize() const
 442     {
 443       usint bytes = sizeof(*this);
 444       if(this->free_buffer) { bytes += this->size * sizeof(usint); }
 445       return bytes;
 446     }
 447
 448 //--------------------------------------------------------------------------
 449
 450     inline void reset()
 451     {
 452       this->pos = 0;
 453       this->bits = WORD_BITS;
 454       this->current = 0;
 455     }
 456
 457     inline void skipBits(usint count)
 458     {
 459       if(count < this->bits)
 460       {
 461         this->bits -= count;
 462         return;
 463       }
 464
 465       count -= this->bits;
 466       this->pos += 1 + count / WORD_BITS;
 467       this->bits = WORD_BITS - count % WORD_BITS;
 468     }
 469
 470 //--------------------------------------------------------------------------
 471
 472     inline usint bitsLeft() const
 473     {
 474       return this->bits + WORD_BITS * (this->size - this->pos - 1);
 475     }
 476
 477     inline void writeBits(usint value, usint count)
 478     {
 479       if(count >= this->bits)
 480       {
 481         count -= this->bits;
 482         this->data[this->pos] |= GET(LOWER(value, count), this->bits);
 483         this->pos++; this->bits = WORD_BITS;
 484       }
 485       if(count > 0)
 486       {
 487         this->bits -= count;
 488         this->data[this->pos] |= HIGHER(GET(value, count), this->bits);
 489       }
 490     }
 491
 492 //--------------------------------------------------------------------------
 493
 494     /*
 495       These operations work on fixed-size items.
 496     */
 497
 498     inline usint getItemSize() const
 499     {
 500       return this->item_bits;
 501     }
 502
 503     inline void goToItem(usint item)
 504     {
 505       usint b = item * this->item_bits;
 506       this->pos = b / WORD_BITS;
 507       this->bits = WORD_BITS - b % WORD_BITS;
 508       this->current = item;
 509     }
 510
 511     inline bool hasNextItem() const
 512     {
 513       return (this->current < this->items);
 514     }
 515
 516     inline void writeItem(usint item)
 517     {
 518       this->writeBits(item, this->item_bits);
 519       this->current++;
 520     }
 521
 522     inline void skipItem()
 523     {
 524       this->skipBits(this->item_bits);
 525       this->current++;
 526     }
 527
 528 //--------------------------------------------------------------------------
 529
 530     /*
 531       Nibble coding for positive integers.
 532     */
 533
 534     inline usint nibbleCodeLength(usint value) const
 535     {
 536       usint b = 0;
 537       value--;
 538
 539       do
 540       {
 541         b += 4;
 542         value >>= 3;
 543       }
 544       while(value > 0);
 545
 546       return b;
 547     }
 548
 549     // Something breaks very badly if value > 15.
 550     inline void writeNibble(usint value)
 551     {
 552       this->bits -= 4;
 553       this->data[this->pos] |= HIGHER(value, this->bits);
 554       if(this->bits == 0) { this->pos++; this->bits = WORD_BITS; }
 555     }
 556
 557     // It is assumed that there is enough space for the code.
 558     inline void writeNibbleCode(usint value)
 559     {
 560       value--;
 561       while(value > 0x7)
 562       {
 563         this->writeNibble(value & 0x7);
 564         value >>= 3;
 565       }
 566       this->writeNibble(value | 0x8);
 567     }
 568
 569 //--------------------------------------------------------------------------
 570
 571     /*
 572       Delta coding for positive integers
 573     */
 574
 575     inline bool canDeltaCode(usint value) const
 576     {
 577       return this->deltaCodeLength(value) <= this->bitsLeft();
 578     }
 579
 580     inline usint deltaCodeLength(usint value) const
 581     {
 582       usint len = length(value);
 583       usint llen = length(len);
 584       return (len + llen + llen - 2);
 585     }
 586
 587     // This version returns false if there is no space left for the encoding.
 588     inline bool writeDeltaCode(usint value)
 589     {
 590       usint len = length(value);
 591       usint llen = length(len);
 592
 593       if(len + llen + llen - 2 > this->bitsLeft()) { return false; }
 594
 595       // this->writeBits(0, llen - 1); // Now included in the next writeBits()
 596       this->writeBits(len, llen + llen - 1);
 597       this->writeBits(value, len - 1);
 598       return true;
 599     }
 600
 601     // This version assumes the code fits into the buffer.
 602     inline void writeDeltaCodeDirect(usint value)
 603     {
 604       usint len = length(value);
 605       usint llen = length(len);
 606
 607       // this->writeBits(0, llen - 1); // Now included in the next writeBits()
 608       this->writeBits(len, llen + llen - 1);
 609       this->writeBits(value, len - 1);
 610     }
 611
 612     // We assume the code fits into usint:
 613     //  32-bit:  value < 2^24
 614     //  64-bit:  value < 2^54
 615     inline void writeDeltaCodeFast(usint value)
 616     {
 617       usint len = length(value);
 618
 619       value ^= ((usint)1 << (len - 1));
 620       this->writeBits((len << (len - 1)) | value, len + 2 * length(len) - 2);
 621     }
 622
 623 //--------------------------------------------------------------------------
 624
 625   private:
 626     usint* data;
 627     usint size, item_bits, items;
 628     bool free_buffer;
 629
 630     // Iterator data
 631     usint pos, bits, current;
 632
 633     inline static usint bitsToWords(usint _bits) { return (_bits + WORD_BITS - 1) / WORD_BITS; }
 634
 635     // These are not allowed.
 636     WriteBuffer();
 637     WriteBuffer(const WriteBuffer&);
 638     WriteBuffer& operator = (const WriteBuffer&);
 639 };
 640
 641
 642 //--------------------------------------------------------------------------
 643
 644
 645 } // namespace CSA
 646
 647
 648 #endif // BITBUFFER_H