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(Data* buffer, usint words);
26 GenericBitBuffer(Data* buffer, usint _items, usint item_size);
29 void writeBuffer(std::ofstream& file, bool erase = true);
30 void readBuffer(std::ifstream& file, usint words, bool erase = true);
31 void setBuffer(Data* buffer, usint words);
33 // We assume we are already using a buffer not owned by this.
34 inline void moveBuffer(Data* buffer)
38 this->bits = DATA_BITS;
42 //--------------------------------------------------------------------------
44 inline void reset(bool erase)
47 this->bits = DATA_BITS;
51 memset(this->data, 0, this->size * sizeof(Data));
55 inline void skipBits(usint count)
57 if(count < this->bits)
64 this->pos += 1 + count / DATA_BITS;
65 this->bits = DATA_BITS - count % DATA_BITS;
68 inline void rewind(usint count)
71 if(this->bits > DATA_BITS)
73 usint back = (this->bits - 1) / DATA_BITS;
75 this->bits -= back * DATA_BITS;
79 //--------------------------------------------------------------------------
81 inline usint bitsLeft()
83 return this->bits + DATA_BITS * (this->size - this->pos - 1);
86 inline void writeBits(usint value, usint count)
88 while(count >= this->bits)
91 this->data[this->pos] |= GET(LOWER(value, count), this->bits);
92 this->pos++; this->bits = DATA_BITS;
97 this->data[this->pos] |= HIGHER(GET(value, count), this->bits);
101 // Returns nonzero if bit is 1
102 inline usint readBit()
105 usint bit = this->data[this->pos] & ((usint)1 << this->bits);
107 if(this->bits == 0) { this->pos++; this->bits = DATA_BITS; }
112 inline usint readBits(usint count)
116 while(count >= this->bits)
119 value |= HIGHER(GET(this->data[this->pos], this->bits), count);
120 this->pos++; this->bits = DATA_BITS;
125 value |= GET(LOWER(this->data[this->pos], this->bits), count);
131 //--------------------------------------------------------------------------
134 These operations work on fixed-size items.
137 inline usint getItemSize()
139 return this->item_bits;
143 inline void setItemSize(usint new_size)
145 if(new_size == 0) { return; }
146 this->item_bits = new_size;
150 inline void goToItem(usint item)
152 usint b = item * this->item_bits;
153 this->pos = b / DATA_BITS;
154 this->bits = DATA_BITS - b % DATA_BITS;
155 this->current = item;
158 inline usint readItem()
161 return this->readBits(this->item_bits);
164 inline usint readItem(usint item)
166 this->goToItem(item);
167 return this->readItem();
170 inline usint readFirstItem()
172 return this->readItem(0);
175 inline bool hasNextItem()
177 return (this->current < this->items);
180 inline void writeItem(usint item)
182 this->writeBits(item, this->item_bits);
186 inline void skipItem()
188 this->skipBits(this->item_bits);
192 //--------------------------------------------------------------------------
195 Delta coding for positive integers
198 inline bool canDeltaCode(usint value)
200 return this->deltaCodeLength(value) <= this->bitsLeft();
203 inline usint deltaCodeLength(usint value)
205 usint len = length(value);
206 usint llen = length(len);
207 return (len + llen + llen - 2);
210 // This version returns false if there is no space left for the encoding.
211 inline bool writeDeltaCode(usint value)
213 usint len = length(value);
214 usint llen = length(len);
216 if(len + llen + llen - 2 > this->bitsLeft()) { return false; }
218 // this->writeBits(0, llen - 1); // Now included in the next writeBits()
219 this->writeBits(len, llen + llen - 1);
220 this->writeBits(value, len - 1);
224 // This version assumes the code fits into the buffer.
225 inline void writeDeltaCodeDirect(usint value)
227 usint len = length(value);
228 usint llen = length(len);
230 // this->writeBits(0, llen - 1); // Now included in the next writeBits()
231 this->writeBits(len, llen + llen - 1);
232 this->writeBits(value, len - 1);
235 // We assume the code fits into usint:
236 // 32-bit: value < 2^24
237 // 64-bit: value < 2^54
238 inline void writeDeltaCodeFast(usint value)
240 usint len = length(value);
242 value ^= ((usint)1 << (len - 1));
243 this->writeBits((len << (len - 1)) | value, len + 2 * length(len) - 2);
246 inline usint readDeltaCode()
249 while(this->readBit() == 0) { len++; }
251 usint temp = (((usint)1 << len) | this->readBits(len)) - 1;
252 temp = ((usint)1 << temp) | this->readBits(temp);
256 //--------------------------------------------------------------------------
259 Gamma coding for positive integers
262 inline bool canGammaCode(usint value)
264 return this->gammaCodeLength(value) <= this->bitsLeft();
267 inline usint gammaCodeLength(usint value)
269 return 2 * length(value) - 1;
272 // This version returns false if there is no space left for the encoding.
273 inline bool writeGammaCode(usint value)
275 usint len = length(value);
277 if(len > this->bitsLeft()) { return false; }
279 this->writeBits(0, len - 1);
280 this->writeBits(value, len);
284 // This version assumes the code fits into the buffer.
285 inline void writeGammaCodeDirect(usint value)
287 usint len = length(value);
289 this->writeBits(0, len - 1);
290 this->writeBits(value, len);
293 // We assume the code fits into usint:
294 // 32-bit: value < 2^16
295 // 64-bit: value < 2^32
296 inline void writeGammaCodeFast(usint value)
298 this->writeBits(value, this->gammaCodeLength(value));
301 inline usint readGammaCode()
304 while(this->readBit() == 0) { len++; }
305 return ((usint)1 << len) | this->readBits(len);
308 //--------------------------------------------------------------------------
312 //--------------------------------------------------------------------------
316 usint size, pos, bits;
317 usint item_bits, items, current;
320 const static usint DATA_BITS = sizeof(Data) * CHAR_BIT;
322 inline static usint bitsToData(usint _bits) { return (_bits + DATA_BITS - 1) / DATA_BITS; }
326 typedef GenericBitBuffer<uchar> BitBuffer;
327 typedef GenericBitBuffer<usint> FastBitBuffer;
330 //--------------------------------------------------------------------------
334 GenericBitBuffer<Data>::GenericBitBuffer(usint words) :
343 this->data = new Data[words];
344 memset(this->data, 0, words * sizeof(Data));
348 GenericBitBuffer<Data>::GenericBitBuffer(usint _items, usint item_size) :
351 item_bits(item_size),
356 this->size = bitsToData(items * item_size);
357 this->data = new Data[this->size];
358 memset(this->data, 0, this->size * sizeof(Data));
362 GenericBitBuffer<Data>::GenericBitBuffer(std::ifstream& file, usint words) :
371 this->data = new Data[words];
372 memset(this->data, 0, words * sizeof(Data));
373 file.read((char*)this->data, words * sizeof(Data));
377 GenericBitBuffer<Data>::GenericBitBuffer(std::ifstream& file, usint _items, usint item_size) :
378 size(BITS_TO_WORDS(_items * item_size)),
381 item_bits(item_size),
386 this->data = new Data[this->size];
387 memset(this->data, 0, this->size * sizeof(Data));
388 file.read((char*)this->data, this->size * sizeof(Data));
392 GenericBitBuffer<Data>::GenericBitBuffer(Data* buffer, usint words) :
405 GenericBitBuffer<Data>::GenericBitBuffer(Data* buffer, usint _items, usint item_size) :
406 size(BITS_TO_WORDS(_items * item_size)),
409 item_bits(item_size),
418 GenericBitBuffer<Data>::~GenericBitBuffer()
420 if(this->free_buffer)
426 //--------------------------------------------------------------------------
430 GenericBitBuffer<Data>::writeBuffer(std::ofstream& file, bool erase)
432 file.write((char*)this->data, this->size * sizeof(Data));
438 GenericBitBuffer<Data>::readBuffer(std::ifstream& file, usint words, bool erase)
440 if(words > this->size || !(this->free_buffer))
442 if(this->free_buffer)
447 this->data = new Data[words];
448 this->free_buffer = true;
452 file.read((char*)this->data, words * sizeof(Data));
457 GenericBitBuffer<Data>::setBuffer(Data* buffer, usint words)
459 if(this->free_buffer)
462 this->free_buffer = false;
470 //--------------------------------------------------------------------------
474 GenericBitBuffer<Data>::reportSize()
476 usint bytes = sizeof(*this);
477 if(this->free_buffer) { bytes += this->size * sizeof(Data); }
481 //--------------------------------------------------------------------------
487 #endif // BITBUFFER_H