ScummVM API documentation
bitstream.h
1 /* ScummVM - Graphic Adventure Engine
2  *
3  * ScummVM is the legal property of its developers, whose names
4  * are too numerous to list here. Please refer to the COPYRIGHT
5  * file distributed with this source distribution.
6  *
7  * This program is free software: you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation, either version 3 of the License, or
10  * (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program. If not, see <http://www.gnu.org/licenses/>.
19  *
20  */
21 
22 // Based on xoreos' BitStream implementation
23 
24 #ifndef COMMON_BITSTREAM_H
25 #define COMMON_BITSTREAM_H
26 
27 #include "common/scummsys.h"
28 #include "common/textconsole.h"
29 #include "common/stream.h"
30 #include "common/types.h"
31 #include "common/util.h"
32 
33 namespace Common {
34 
54 template<class STREAM, typename CONTAINER, int valueBits, bool isLE, bool MSB2LSB>
56 private:
57  STREAM *_stream;
58  DisposeAfterUse::Flag _disposeAfterUse;
59 
60  CONTAINER _bitContainer;
61  uint8 _bitsLeft;
62  uint32 _size;
63  uint32 _pos;
64 
66  FORCEINLINE uint32 readData() {
67  if (isLE) {
68  if (valueBits == 8)
69  return _stream->readByte();
70  if (valueBits == 16)
71  return _stream->readUint16LE();
72  if (valueBits == 32)
73  return _stream->readUint32LE();
74  } else {
75  if (valueBits == 8)
76  return _stream->readByte();
77  if (valueBits == 16)
78  return _stream->readUint16BE();
79  if (valueBits == 32)
80  return _stream->readUint32BE();
81  }
82 
83  assert(false);
84  return 0;
85  }
86 
88  FORCEINLINE void fillContainer(size_t min) {
89  while (_bitsLeft < min) {
90 
91  CONTAINER data;
92  if (_pos + _bitsLeft + valueBits <= _size) {
93  data = readData();
94  } else {
95  // Peeking data out of bounds is well-defined and returns 0 bits.
96  // This is for convenience when using speed-up techniques reading
97  // more bits than actually available. Call eos() to check if data
98  // was actually read out of bounds. Peeking out of bounds does not
99  // set the eos flag.
100  data = 0;
101  }
102 
103  // Move the data value to the right position in the bit container
104  if (MSB2LSB)
105  _bitContainer |= data << ((sizeof(_bitContainer) * 8) - valueBits - _bitsLeft);
106  else
107  _bitContainer |= data << _bitsLeft;
108 
109  _bitsLeft += valueBits;
110  }
111 }
112 
114  FORCEINLINE static uint32 getNBits(CONTAINER value, size_t n) {
115  if (n == 0)
116  return 0;
117 
118  const size_t toShift = (sizeof(value) * 8) - n;
119 
120  if (MSB2LSB)
121  return value >> toShift;
122  else
123  return (value << toShift) >> toShift;
124  }
125 
127  FORCEINLINE void skipBits(size_t n) {
128  assert(n <= _bitsLeft);
129 
130  // Shift to the next bit
131  if (MSB2LSB)
132  _bitContainer <<= n;
133  else
134  _bitContainer >>= n;
135 
136  _bitsLeft -= n;
137  _pos += n;
138  }
139 
140 public:
142  BitStreamImpl(STREAM *stream, DisposeAfterUse::Flag disposeAfterUse = DisposeAfterUse::NO) :
143  _stream(stream), _disposeAfterUse(disposeAfterUse), _bitContainer(0), _bitsLeft(0), _pos(0) {
144 
145  if ((valueBits != 8) && (valueBits != 16) && (valueBits != 32))
146  error("BitStreamImpl: Invalid memory layout %d, %d, %d", valueBits, int(isLE), int(MSB2LSB));
147 
148  _size = (_stream->size() & ~((uint32) ((valueBits >> 3) - 1))) * 8;
149  }
150 
152  BitStreamImpl(STREAM &stream) :
153  _stream(&stream), _disposeAfterUse(DisposeAfterUse::NO), _bitContainer(0), _bitsLeft(0), _pos(0) {
154 
155  if ((valueBits != 8) && (valueBits != 16) && (valueBits != 32))
156  error("BitStreamImpl: Invalid memory layout %d, %d, %d", valueBits, int(isLE), int(MSB2LSB));
157 
158  _size = (_stream->size() & ~((uint32) ((valueBits >> 3) - 1))) * 8;
159  }
160 
161  ~BitStreamImpl() {
162  if (_disposeAfterUse == DisposeAfterUse::YES)
163  delete _stream;
164  }
165 
167  uint peekBit() {
168  fillContainer(1);
169 
170  return getNBits(_bitContainer, 1);
171  }
172 
174  uint getBit() {
175  const uint b = peekBit();
176 
177  skipBits(1);
178 
179  return b;
180  }
181 
187  template<int n>
188  uint32 peekBits() {
189  if (n > 32)
190  error("BitStreamImpl::peekBits(): Too many bits requested to be peeked");
191 
192  fillContainer(n);
193  return getNBits(_bitContainer, n);
194  }
195 
206  template<int n>
207  uint32 getBits() {
208  if (n > 32)
209  error("BitStreamImpl::getBits(): Too many bits requested to be read");
210 
211  const uint32 b = peekBits<n>();
212 
213  skipBits(n);
214 
215  return b;
216  }
217 
223  uint32 peekBits(size_t n) {
224  if (n > 32)
225  error("BitStreamImpl::peekBits(): Too many bits requested to be peeked");
226 
227  fillContainer(n);
228  return getNBits(_bitContainer, n);
229  }
230 
241  uint32 getBits(size_t n) {
242  if (n > 32)
243  error("BitStreamImpl::getBits(): Too many bits requested to be read");
244 
245  const uint32 b = peekBits(n);
246 
247  skipBits(n);
248 
249  return b;
250  }
251 
263  void addBit(uint32 &x, uint32 n) {
264  if (n >= 32)
265  error("BitStreamImpl::addBit(): Too many bits requested to be read");
266 
267  if (MSB2LSB)
268  x = (x << 1) | getBit();
269  else
270  x = (x & ~(1 << n)) | (getBit() << n);
271  }
272 
274  void rewind() {
275  _stream->seek(0);
276 
277  _bitContainer = 0;
278  _bitsLeft = 0;
279  _pos = 0;
280  }
281 
283  void skip(uint32 n) {
284  if (n >= _bitsLeft) {
285  n -= _bitsLeft;
286  skipBits(_bitsLeft);
287  }
288 
289  while (n > 32) {
290  fillContainer(32);
291  skipBits(32);
292  n -= 32;
293  }
294 
295  fillContainer(n);
296  skipBits(n);
297  }
298 
300  void align() {
301  uint32 bitsAfterBoundary = _pos % valueBits;
302  if (bitsAfterBoundary) {
303  skip(valueBits - bitsAfterBoundary);
304  }
305  }
306 
308  uint32 pos() const {
309  return _pos;
310  }
311 
313  uint32 size() const {
314  return _size;
315  }
316 
317  bool eos() const {
318  return _stream->eos() || (_pos >= _size);
319  }
320 
321  static bool isMSB2LSB() {
322  return MSB2LSB;
323  }
324 };
325 
326 
327 
338 private:
339  const byte * const _ptrOrig;
340  const byte *_ptr;
341  const uint32 _size;
342  uint32 _pos;
343  DisposeAfterUse::Flag _disposeMemory;
344  bool _eos;
346 public:
347  BitStreamMemoryStream(const byte *dataPtr, uint32 dataSize, DisposeAfterUse::Flag disposeMemory = DisposeAfterUse::NO) :
348  _ptrOrig(dataPtr),
349  _ptr(dataPtr),
350  _size(dataSize),
351  _pos(0),
352  _disposeMemory(disposeMemory),
353  _eos(false) {}
354 
356  if (_disposeMemory)
357  free(const_cast<byte *>(_ptrOrig));
358  }
359 
360  bool eos() const {
361  return _eos;
362  }
363 
364  bool err() const {
365  return false;
366  }
367 
368  uint32 pos() const {
369  return _pos;
370  }
371 
372  uint32 size() const {
373  return _size;
374  }
375 
376  bool seek(uint32 offset) {
377  assert(offset <= _size);
378 
379  _eos = false;
380  _pos = offset;
381  _ptr = _ptrOrig + _pos;
382  return true;
383  }
384 
385  byte readByte() {
386  if (_pos >= _size) {
387  _eos = true;
388  return 0;
389  }
390 
391  _pos++;
392  return *_ptr++;
393  }
394 
395  uint16 readUint16LE() {
396  if (_pos + 2 > _size) {
397  _eos = true;
398  if (_pos < _size) {
399  _pos++;
400  return *_ptr++;
401  } else {
402  return 0;
403  }
404  }
405 
406  uint16 val = READ_LE_UINT16(_ptr);
407 
408  _pos += 2;
409  _ptr += 2;
410 
411  return val;
412  }
413 
414  uint16 readUint16BE() {
415  if (_pos + 2 > _size) {
416  _eos = true;
417  if (_pos < _size) {
418  _pos++;
419  return (*_ptr++) << 8;
420  } else {
421  return 0;
422  }
423  }
424 
425  uint16 val = READ_LE_UINT16(_ptr);
426 
427  _pos += 2;
428  _ptr += 2;
429 
430  return val;
431  }
432 
433  uint32 readUint32LE() {
434  if (_pos + 4 > _size) {
435  uint32 val = readByte();
436  val |= (uint32)readByte() << 8;
437  val |= (uint32)readByte() << 16;
438  val |= (uint32)readByte() << 24;
439 
440  return val;
441  }
442 
443  uint32 val = READ_LE_UINT32(_ptr);
444 
445  _pos += 4;
446  _ptr += 4;
447 
448  return val;
449  }
450 
451  uint32 readUint32BE() {
452  if (_pos + 4 > _size) {
453  uint32 val = (uint32)readByte() << 24;
454  val |= (uint32)readByte() << 16;
455  val |= (uint32)readByte() << 8;
456  val |= (uint32)readByte();
457 
458  return val;
459  }
460 
461  uint32 val = READ_BE_UINT32(_ptr);
462 
463  _pos += 4;
464  _ptr += 4;
465 
466  return val;
467  }
468 
469 };
470 
480 
489 
498 
499 
500 
505 
514 
523 
528 } // End of namespace Common
529 
530 #endif // COMMON_BITSTREAM_H
BitStreamImpl< SeekableReadStream, uint64, 32, true, false > BitStream32LELSB
Definition: bitstream.h:493
BitStreamImpl< BitStreamMemoryStream, uint64, 32, false, true > BitStreamMemory32BEMSB
Definition: bitstream.h:520
void align()
Definition: bitstream.h:300
Definition: types.h:27
void skip(uint32 n)
Definition: bitstream.h:283
uint peekBit()
Definition: bitstream.h:167
uint32 getBits()
Definition: bitstream.h:207
BitStreamImpl< BitStreamMemoryStream, uint64, 32, false, false > BitStreamMemory32BELSB
Definition: bitstream.h:522
BitStreamImpl< SeekableReadStream, uint64, 32, false, false > BitStream32BELSB
Definition: bitstream.h:497
BitStreamImpl< BitStreamMemoryStream, uint64, 16, true, false > BitStreamMemory16LELSB
Definition: bitstream.h:509
uint32 getBits(size_t n)
Definition: bitstream.h:241
BitStreamImpl(STREAM &stream)
Definition: bitstream.h:152
BitStreamImpl< SeekableReadStream, uint64, 16, true, false > BitStream16LELSB
Definition: bitstream.h:484
BitStreamImpl< BitStreamMemoryStream, uint64, 8, false, true > BitStreamMemory8MSB
Definition: bitstream.h:502
BitStreamImpl< SeekableReadStream, uint64, 32, true, true > BitStream32LEMSB
Definition: bitstream.h:491
BitStreamImpl< SeekableReadStream, uint64, 32, false, true > BitStream32BEMSB
Definition: bitstream.h:495
Definition: bitstream.h:55
Definition: algorithm.h:29
BitStreamImpl< SeekableReadStream, uint64, 8, false, false > BitStream8LSB
Definition: bitstream.h:479
uint32 size() const
Definition: bitstream.h:313
void NORETURN_PRE error(MSVC_PRINTF const char *s,...) GCC_PRINTF(1
BitStreamImpl(STREAM *stream, DisposeAfterUse::Flag disposeAfterUse=DisposeAfterUse::NO)
Definition: bitstream.h:142
BitStreamImpl< BitStreamMemoryStream, uint64, 16, false, true > BitStreamMemory16BEMSB
Definition: bitstream.h:511
BitStreamImpl< SeekableReadStream, uint64, 8, false, true > BitStream8MSB
Definition: bitstream.h:477
uint32 pos() const
Definition: bitstream.h:308
BitStreamImpl< SeekableReadStream, uint64, 16, true, true > BitStream16LEMSB
Definition: bitstream.h:482
BitStreamImpl< BitStreamMemoryStream, uint64, 32, true, true > BitStreamMemory32LEMSB
Definition: bitstream.h:516
uint getBit()
Definition: bitstream.h:174
void rewind()
Definition: bitstream.h:274
void addBit(uint32 &x, uint32 n)
Definition: bitstream.h:263
BitStreamImpl< BitStreamMemoryStream, uint64, 16, false, false > BitStreamMemory16BELSB
Definition: bitstream.h:513
Definition: bitstream.h:337
uint32 peekBits()
Definition: bitstream.h:188
BitStreamImpl< SeekableReadStream, uint64, 16, false, true > BitStream16BEMSB
Definition: bitstream.h:486
BitStreamImpl< BitStreamMemoryStream, uint64, 8, false, false > BitStreamMemory8LSB
Definition: bitstream.h:504
BitStreamImpl< SeekableReadStream, uint64, 16, false, false > BitStream16BELSB
Definition: bitstream.h:488
BitStreamMemoryStream(const byte *dataPtr, uint32 dataSize, DisposeAfterUse::Flag disposeMemory=DisposeAfterUse::NO)
Definition: bitstream.h:347
uint32 peekBits(size_t n)
Definition: bitstream.h:223
BitStreamImpl< BitStreamMemoryStream, uint64, 16, true, true > BitStreamMemory16LEMSB
Definition: bitstream.h:507
BitStreamImpl< BitStreamMemoryStream, uint64, 32, true, false > BitStreamMemory32LELSB
Definition: bitstream.h:518