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 8 * modify it under the terms of the GNU General Public License 9 * as published by the Free Software Foundation; either version 2 10 * of the License, or (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, write to the Free Software 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 20 * 21 */ 22 23 // Based on xoreos' BitStream implementation 24 25 #ifndef COMMON_BITSTREAM_H 26 #define COMMON_BITSTREAM_H 27 28 #include "common/scummsys.h" 29 #include "common/textconsole.h" 30 #include "common/stream.h" 31 #include "common/types.h" 32 #include "common/util.h" 33 34 namespace Common { 35 36 /** 37 * A template implementing a bit stream for different data memory layouts. 38 * 39 * Such a bit stream reads valueBits-wide values from the data stream and 40 * gives access to their bits, one at a time. 41 * 42 * For example, a bit stream with the layout parameters 32, true, false 43 * for valueBits, isLE and isMSB2LSB, reads 32bit little-endian values 44 * from the data stream and hands out the bits in the order of LSB to MSB. 45 */ 46 template<class STREAM, int valueBits, bool isLE, bool MSB2LSB> 47 class BitStreamImpl { 48 private: 49 STREAM *_stream; ///< The input stream. 50 DisposeAfterUse::Flag _disposeAfterUse; ///< Should we delete the stream on destruction? 51 52 uint64 _bitContainer; ///< The currently available bits. 53 uint8 _bitsLeft; ///< Number of bits currently left in the bit container. 54 uint32 _size; ///< Total bitstream size (in bits) 55 uint32 _pos; ///< Current bitstream position (in bits) 56 57 /** Read a data value. */ readData()58 inline uint32 readData() { 59 if (isLE) { 60 if (valueBits == 8) 61 return _stream->readByte(); 62 if (valueBits == 16) 63 return _stream->readUint16LE(); 64 if (valueBits == 32) 65 return _stream->readUint32LE(); 66 } else { 67 if (valueBits == 8) 68 return _stream->readByte(); 69 if (valueBits == 16) 70 return _stream->readUint16BE(); 71 if (valueBits == 32) 72 return _stream->readUint32BE(); 73 } 74 75 assert(false); 76 return 0; 77 } 78 79 /** Fill the container with at least min bits. */ fillContainer(size_t min)80 inline void fillContainer(size_t min) { 81 while (_bitsLeft < min) { 82 83 uint64 data; 84 if (_pos + _bitsLeft + valueBits <= _size) { 85 data = readData(); 86 } else { 87 // Peeking data out of bounds is well defined and returns 0 bits. 88 // This is for convenience when using speed-up techniques reading 89 // more bits than actually available. Users should call eos() to 90 // check if data was actually read out of bounds. Peeking out of 91 // bounds does not set the eos flag. 92 data = 0; 93 } 94 95 // Move the data value to the right position in the bit container 96 if (MSB2LSB) 97 _bitContainer |= data << (64 - valueBits - _bitsLeft); 98 else 99 _bitContainer |= data << _bitsLeft; 100 101 _bitsLeft += valueBits; 102 } 103 } 104 105 /** Get n bits from the bit container. */ getNBits(uint64 value,size_t n)106 inline static uint32 getNBits(uint64 value, size_t n) { 107 if (n == 0) 108 return 0; 109 110 const size_t toShift = 64 - n; 111 112 if (MSB2LSB) 113 return value >> toShift; 114 else 115 return (value << toShift) >> toShift; 116 } 117 118 /** Skip already read bits. */ skipBits(size_t n)119 inline void skipBits(size_t n) { 120 assert(n <= _bitsLeft); 121 122 // Shift to the next bit 123 if (MSB2LSB) 124 _bitContainer <<= n; 125 else 126 _bitContainer >>= n; 127 128 _bitsLeft -= n; 129 _pos += n; 130 } 131 132 public: 133 /** Create a bit stream using this input data stream and optionally delete it on destruction. */ 134 BitStreamImpl(STREAM *stream, DisposeAfterUse::Flag disposeAfterUse = DisposeAfterUse::NO) : _stream(stream)135 _stream(stream), _disposeAfterUse(disposeAfterUse), _bitContainer(0), _bitsLeft(0), _pos(0) { 136 137 if ((valueBits != 8) && (valueBits != 16) && (valueBits != 32)) 138 error("BitStreamImpl: Invalid memory layout %d, %d, %d", valueBits, isLE, MSB2LSB); 139 140 _size = (_stream->size() & ~((uint32) ((valueBits >> 3) - 1))) * 8; 141 } 142 143 /** Create a bit stream using this input data stream. */ BitStreamImpl(STREAM & stream)144 BitStreamImpl(STREAM &stream) : 145 _stream(&stream), _disposeAfterUse(DisposeAfterUse::NO), _bitContainer(0), _bitsLeft(0), _pos(0) { 146 147 if ((valueBits != 8) && (valueBits != 16) && (valueBits != 32)) 148 error("BitStreamImpl: Invalid memory layout %d, %d, %d", valueBits, isLE, MSB2LSB); 149 150 _size = (_stream->size() & ~((uint32) ((valueBits >> 3) - 1))) * 8; 151 } 152 ~BitStreamImpl()153 ~BitStreamImpl() { 154 if (_disposeAfterUse == DisposeAfterUse::YES) 155 delete _stream; 156 } 157 158 /** Read a bit from the bit stream, without changing the stream's position. */ peekBit()159 uint peekBit() { 160 fillContainer(1); 161 162 return getNBits(_bitContainer, 1); 163 } 164 165 /** Read a bit from the bit stream. */ getBit()166 uint getBit() { 167 const uint b = peekBit(); 168 169 skipBits(1); 170 171 return b; 172 } 173 174 /** 175 * Read a multi-bit value from the bit stream, without changing the stream's position. 176 * 177 * The bit order is the same as in getBits(). 178 */ peekBits(size_t n)179 uint32 peekBits(size_t n) { 180 if (n > 32) 181 error("BitStreamImpl::peekBits(): Too many bits requested to be peeked"); 182 183 fillContainer(n); 184 return getNBits(_bitContainer, n); 185 } 186 187 /** 188 * Read a multi-bit value from the bit stream. 189 * 190 * The value is read as if just taken as a whole from the bitstream. 191 * 192 * For example: 193 * Reading a 4-bit value from an 8-bit bitstream with the contents 01010011: 194 * If the bitstream is MSB2LSB, the 4-bit value would be 0101. 195 * If the bitstream is LSB2MSB, the 4-bit value would be 0011. 196 */ getBits(size_t n)197 uint32 getBits(size_t n) { 198 if (n > 32) 199 error("BitStreamImpl::getBits(): Too many bits requested to be read"); 200 201 const uint32 b = peekBits(n); 202 203 skipBits(n); 204 205 return b; 206 } 207 208 /** 209 * Add a bit to the value x, making it an n+1-bit value. 210 * 211 * The current value is shifted and the bit is added to the 212 * appropriate place, dependant on the stream's bitorder. 213 * 214 * For example: 215 * A bit y is added to the value 00001100 with size 4. 216 * If the stream's bitorder is MSB2LSB, the resulting value is 0001100y. 217 * If the stream's bitorder is LSB2MSB, the resulting value is 000y1100. 218 */ addBit(uint32 & x,uint32 n)219 void addBit(uint32 &x, uint32 n) { 220 if (n >= 32) 221 error("BitStreamImpl::addBit(): Too many bits requested to be read"); 222 223 if (MSB2LSB) 224 x = (x << 1) | getBit(); 225 else 226 x = (x & ~(1 << n)) | (getBit() << n); 227 } 228 229 /** Rewind the bit stream back to the start. */ rewind()230 void rewind() { 231 _stream->seek(0); 232 233 _bitContainer = 0; 234 _bitsLeft = 0; 235 _pos = 0; 236 } 237 238 /** Skip the specified amount of bits. */ skip(uint32 n)239 void skip(uint32 n) { 240 while (n > 32) { 241 fillContainer(32); 242 skipBits(32); 243 n -= 32; 244 } 245 246 fillContainer(n); 247 skipBits(n); 248 } 249 250 /** Skip the bits to closest data value border. */ align()251 void align() { 252 uint32 bitsAfterBoundary = _pos % valueBits; 253 if (bitsAfterBoundary) { 254 skip(valueBits - bitsAfterBoundary); 255 } 256 } 257 258 /** Return the stream position in bits. */ pos()259 uint32 pos() const { 260 return _pos; 261 } 262 263 /** Return the stream size in bits. */ size()264 uint32 size() const { 265 return _size; 266 } 267 eos()268 bool eos() const { 269 return _stream->eos() || (_pos >= _size); 270 } 271 isMSB2LSB()272 static bool isMSB2LSB() { 273 return MSB2LSB; 274 } 275 }; 276 277 278 279 /** 280 * A cut-down version of MemoryReadStream specifically for use with BitStream. 281 * It removes the virtual call overhead for reading bytes from a memory buffer, 282 * and allows directly inlining this access. 283 * 284 * The code duplication with MemoryReadStream is not ideal. 285 * It might be possible to avoid this by making this a final subclass of 286 * MemoryReadStream, but that is a C++11 feature. 287 */ 288 class BitStreamMemoryStream { 289 private: 290 const byte * const _ptrOrig; 291 const byte *_ptr; 292 const uint32 _size; 293 uint32 _pos; 294 DisposeAfterUse::Flag _disposeMemory; 295 bool _eos; 296 297 public: 298 BitStreamMemoryStream(const byte *dataPtr, uint32 dataSize, DisposeAfterUse::Flag disposeMemory = DisposeAfterUse::NO) : _ptrOrig(dataPtr)299 _ptrOrig(dataPtr), 300 _ptr(dataPtr), 301 _size(dataSize), 302 _pos(0), 303 _disposeMemory(disposeMemory), 304 _eos(false) {} 305 ~BitStreamMemoryStream()306 ~BitStreamMemoryStream() { 307 if (_disposeMemory) 308 free(const_cast<byte *>(_ptrOrig)); 309 } 310 eos()311 bool eos() const { 312 return _eos; 313 } 314 err()315 bool err() const { 316 return false; 317 } 318 pos()319 int32 pos() const { 320 return _pos; 321 } 322 size()323 int32 size() const { 324 return _size; 325 } 326 seek(uint32 offset)327 bool seek(uint32 offset) { 328 assert(offset <= _size); 329 330 _eos = false; 331 _pos = offset; 332 _ptr = _ptrOrig + _pos; 333 return true; 334 } 335 readByte()336 byte readByte() { 337 if (_pos >= _size) { 338 _eos = true; 339 return 0; 340 } 341 342 _pos++; 343 return *_ptr++; 344 } 345 readUint16LE()346 uint16 readUint16LE() { 347 if (_pos + 2 > _size) { 348 _eos = true; 349 if (_pos < _size) { 350 _pos++; 351 return *_ptr++; 352 } else { 353 return 0; 354 } 355 } 356 357 uint16 val = READ_LE_UINT16(_ptr); 358 359 _pos += 2; 360 _ptr += 2; 361 362 return val; 363 } 364 readUint16BE()365 uint16 readUint16BE() { 366 if (_pos + 2 > _size) { 367 _eos = true; 368 if (_pos < _size) { 369 _pos++; 370 return (*_ptr++) << 8; 371 } else { 372 return 0; 373 } 374 } 375 376 uint16 val = READ_LE_UINT16(_ptr); 377 378 _pos += 2; 379 _ptr += 2; 380 381 return val; 382 } 383 readUint32LE()384 uint32 readUint32LE() { 385 if (_pos + 4 > _size) { 386 uint32 val = readByte(); 387 val |= (uint32)readByte() << 8; 388 val |= (uint32)readByte() << 16; 389 val |= (uint32)readByte() << 24; 390 391 return val; 392 } 393 394 uint32 val = READ_LE_UINT32(_ptr); 395 396 _pos += 4; 397 _ptr += 4; 398 399 return val; 400 } 401 readUint32BE()402 uint32 readUint32BE() { 403 if (_pos + 4 > _size) { 404 uint32 val = (uint32)readByte() << 24; 405 val |= (uint32)readByte() << 16; 406 val |= (uint32)readByte() << 8; 407 val |= (uint32)readByte(); 408 409 return val; 410 } 411 412 uint32 val = READ_BE_UINT32(_ptr); 413 414 _pos += 4; 415 _ptr += 4; 416 417 return val; 418 } 419 420 }; 421 422 423 // typedefs for various memory layouts. 424 425 /** 8-bit data, MSB to LSB. */ 426 typedef BitStreamImpl<SeekableReadStream, 8, false, true > BitStream8MSB; 427 /** 8-bit data, LSB to MSB. */ 428 typedef BitStreamImpl<SeekableReadStream, 8, false, false> BitStream8LSB; 429 430 /** 16-bit little-endian data, MSB to LSB. */ 431 typedef BitStreamImpl<SeekableReadStream, 16, true , true > BitStream16LEMSB; 432 /** 16-bit little-endian data, LSB to MSB. */ 433 typedef BitStreamImpl<SeekableReadStream, 16, true , false> BitStream16LELSB; 434 /** 16-bit big-endian data, MSB to LSB. */ 435 typedef BitStreamImpl<SeekableReadStream, 16, false, true > BitStream16BEMSB; 436 /** 16-bit big-endian data, LSB to MSB. */ 437 typedef BitStreamImpl<SeekableReadStream, 16, false, false> BitStream16BELSB; 438 439 /** 32-bit little-endian data, MSB to LSB. */ 440 typedef BitStreamImpl<SeekableReadStream, 32, true , true > BitStream32LEMSB; 441 /** 32-bit little-endian data, LSB to MSB. */ 442 typedef BitStreamImpl<SeekableReadStream, 32, true , false> BitStream32LELSB; 443 /** 32-bit big-endian data, MSB to LSB. */ 444 typedef BitStreamImpl<SeekableReadStream, 32, false, true > BitStream32BEMSB; 445 /** 32-bit big-endian data, LSB to MSB. */ 446 typedef BitStreamImpl<SeekableReadStream, 32, false, false> BitStream32BELSB; 447 448 449 450 /** 8-bit data, MSB to LSB. */ 451 typedef BitStreamImpl<BitStreamMemoryStream, 8, false, true > BitStreamMemory8MSB; 452 /** 8-bit data, LSB to MSB. */ 453 typedef BitStreamImpl<BitStreamMemoryStream, 8, false, false> BitStreamMemory8LSB; 454 455 /** 16-bit little-endian data, MSB to LSB. */ 456 typedef BitStreamImpl<BitStreamMemoryStream, 16, true , true > BitStreamMemory16LEMSB; 457 /** 16-bit little-endian data, LSB to MSB. */ 458 typedef BitStreamImpl<BitStreamMemoryStream, 16, true , false> BitStreamMemory16LELSB; 459 /** 16-bit big-endian data, MSB to LSB. */ 460 typedef BitStreamImpl<BitStreamMemoryStream, 16, false, true > BitStreamMemory16BEMSB; 461 /** 16-bit big-endian data, LSB to MSB. */ 462 typedef BitStreamImpl<BitStreamMemoryStream, 16, false, false> BitStreamMemory16BELSB; 463 464 /** 32-bit little-endian data, MSB to LSB. */ 465 typedef BitStreamImpl<BitStreamMemoryStream, 32, true , true > BitStreamMemory32LEMSB; 466 /** 32-bit little-endian data, LSB to MSB. */ 467 typedef BitStreamImpl<BitStreamMemoryStream, 32, true , false> BitStreamMemory32LELSB; 468 /** 32-bit big-endian data, MSB to LSB. */ 469 typedef BitStreamImpl<BitStreamMemoryStream, 32, false, true > BitStreamMemory32BEMSB; 470 /** 32-bit big-endian data, LSB to MSB. */ 471 typedef BitStreamImpl<BitStreamMemoryStream, 32, false, false> BitStreamMemory32BELSB; 472 473 474 } // End of namespace Common 475 476 #endif // COMMON_BITSTREAM_H 477