8 #include <cstring> // defines std::memset, added by Kim
10 #include "../misc/definitions.h"
18 class GenericBitBuffer
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);
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);
35 // We assume we are already using a buffer not owned by this.
36 inline void moveBuffer(Data* buffer)
40 this->bits = DATA_BITS;
44 //--------------------------------------------------------------------------
46 inline void reset(bool erase)
49 this->bits = DATA_BITS;
53 memset(this->data, 0, this->size * sizeof(Data));
57 inline void skipBits(usint count)
59 if(count < this->bits)
66 this->pos += 1 + count / DATA_BITS;
67 this->bits = DATA_BITS - count % DATA_BITS;
70 inline void rewind(usint count)
73 if(this->bits > DATA_BITS)
75 usint back = (this->bits - 1) / DATA_BITS;
77 this->bits -= back * DATA_BITS;
81 //--------------------------------------------------------------------------
83 inline usint bitsLeft()
85 return this->bits + DATA_BITS * (this->size - this->pos - 1);
88 inline void writeBits(usint value, usint count)
90 while(count >= this->bits)
93 this->data[this->pos] |= GET(LOWER(value, count), this->bits);
94 this->pos++; this->bits = DATA_BITS;
99 this->data[this->pos] |= HIGHER(GET(value, count), this->bits);
103 // Returns nonzero if bit is 1
104 inline usint readBit()
107 usint bit = this->data[this->pos] & ((usint)1 << this->bits);
109 if(this->bits == 0) { this->pos++; this->bits = DATA_BITS; }
114 inline usint readBits(usint count)
118 while(count >= this->bits)
121 value |= HIGHER(GET(this->data[this->pos], this->bits), count);
122 this->pos++; this->bits = DATA_BITS;
127 value |= GET(LOWER(this->data[this->pos], this->bits), count);
133 //--------------------------------------------------------------------------
136 These operations work on fixed-size items.
139 inline usint getItemSize()
141 return this->item_bits;
145 inline void setItemSize(usint new_size)
147 if(new_size == 0) { return; }
148 this->item_bits = new_size;
152 inline void goToItem(usint item)
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;
160 inline usint readItem()
163 return this->readBits(this->item_bits);
166 inline usint readItem(usint item)
168 this->goToItem(item);
169 return this->readItem();
172 inline usint readFirstItem()
174 return this->readItem(0);
177 inline bool hasNextItem()
179 return (this->current < this->items);
182 inline void writeItem(usint item)
184 this->writeBits(item, this->item_bits);
188 inline void skipItem()
190 this->skipBits(this->item_bits);
194 //--------------------------------------------------------------------------
197 Delta coding for positive integers
200 inline bool canDeltaCode(usint value)
202 return this->deltaCodeLength(value) <= this->bitsLeft();
205 inline usint deltaCodeLength(usint value)
207 usint len = length(value);
208 usint llen = length(len);
209 return (len + llen + llen - 2);
212 // This version returns false if there is no space left for the encoding.
213 inline bool writeDeltaCode(usint value)
215 usint len = length(value);
216 usint llen = length(len);
218 if(len + llen + llen - 2 > this->bitsLeft()) { return false; }
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);
226 // This version assumes the code fits into the buffer.
227 inline void writeDeltaCodeDirect(usint value)
229 usint len = length(value);
230 usint llen = length(len);
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);
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)
242 usint len = length(value);
244 value ^= ((usint)1 << (len - 1));
245 this->writeBits((len << (len - 1)) | value, len + 2 * length(len) - 2);
248 inline usint readDeltaCode()
251 while(this->readBit() == 0) { len++; }
253 usint temp = (((usint)1 << len) | this->readBits(len)) - 1;
254 temp = ((usint)1 << temp) | this->readBits(temp);
258 //--------------------------------------------------------------------------
261 Gamma coding for positive integers
264 inline bool canGammaCode(usint value)
266 return this->gammaCodeLength(value) <= this->bitsLeft();
269 inline usint gammaCodeLength(usint value)
271 return 2 * length(value) - 1;
274 // This version returns false if there is no space left for the encoding.
275 inline bool writeGammaCode(usint value)
277 usint len = length(value);
279 if(len > this->bitsLeft()) { return false; }
281 this->writeBits(0, len - 1);
282 this->writeBits(value, len);
286 // This version assumes the code fits into the buffer.
287 inline void writeGammaCodeDirect(usint value)
289 usint len = length(value);
291 this->writeBits(0, len - 1);
292 this->writeBits(value, len);
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)
300 this->writeBits(value, this->gammaCodeLength(value));
303 inline usint readGammaCode()
306 while(this->readBit() == 0) { len++; }
307 return ((usint)1 << len) | this->readBits(len);
310 //--------------------------------------------------------------------------
314 //--------------------------------------------------------------------------
318 usint size, pos, bits;
319 usint item_bits, items, current;
322 const static usint DATA_BITS = sizeof(Data) * CHAR_BIT;
324 inline static usint bitsToData(usint _bits) { return (_bits + DATA_BITS - 1) / DATA_BITS; }
328 typedef GenericBitBuffer<uchar> BitBuffer;
329 typedef GenericBitBuffer<usint> FastBitBuffer;
332 //--------------------------------------------------------------------------
336 GenericBitBuffer<Data>::GenericBitBuffer(usint words) :
345 this->data = new Data[words];
346 memset(this->data, 0, words * sizeof(Data));
350 GenericBitBuffer<Data>::GenericBitBuffer(usint _items, usint item_size) :
353 item_bits(item_size),
358 this->size = bitsToData(items * item_size);
359 this->data = new Data[this->size];
360 memset(this->data, 0, this->size * sizeof(Data));
364 GenericBitBuffer<Data>::GenericBitBuffer(std::ifstream& file, usint words) :
373 this->data = new Data[words];
374 memset(this->data, 0, words * sizeof(Data));
375 file.read((char*)this->data, words * sizeof(Data));
379 GenericBitBuffer<Data>::GenericBitBuffer(std::ifstream& file, usint _items, usint item_size) :
380 size(BITS_TO_WORDS(_items * item_size)),
383 item_bits(item_size),
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));
394 GenericBitBuffer<Data>::GenericBitBuffer(std::FILE* file, usint _items, usint item_size) :
395 size(BITS_TO_WORDS(_items * item_size)),
398 item_bits(item_size),
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);
409 GenericBitBuffer<Data>::GenericBitBuffer(Data* buffer, usint words) :
422 GenericBitBuffer<Data>::GenericBitBuffer(Data* buffer, usint _items, usint item_size) :
423 size(BITS_TO_WORDS(_items * item_size)),
426 item_bits(item_size),
435 GenericBitBuffer<Data>::~GenericBitBuffer()
437 if(this->free_buffer)
443 //--------------------------------------------------------------------------
447 GenericBitBuffer<Data>::writeBuffer(std::ofstream& file, bool erase)
449 file.write((char*)this->data, this->size * sizeof(Data));
455 GenericBitBuffer<Data>::writeBuffer(std::FILE* file, bool erase)
457 std::fwrite(this->data, sizeof(Data), this->size, file);
463 GenericBitBuffer<Data>::readBuffer(std::ifstream& file, usint words, bool erase)
465 if(words > this->size || !(this->free_buffer))
467 if(this->free_buffer)
472 this->data = new Data[words];
473 this->free_buffer = true;
477 file.read((char*)this->data, words * sizeof(Data));
482 GenericBitBuffer<Data>::setBuffer(Data* buffer, usint words)
484 if(this->free_buffer)
487 this->free_buffer = false;
495 //--------------------------------------------------------------------------
499 GenericBitBuffer<Data>::reportSize()
501 usint bytes = sizeof(*this);
502 if(this->free_buffer) { bytes += this->size * sizeof(Data); }
506 //--------------------------------------------------------------------------
512 #endif // BITBUFFER_H