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