aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--common/bitstream.h232
-rw-r--r--test/common/bitstream.h50
2 files changed, 148 insertions, 134 deletions
diff --git a/common/bitstream.h b/common/bitstream.h
index 1fbc0065ab..81976efdc8 100644
--- a/common/bitstream.h
+++ b/common/bitstream.h
@@ -20,7 +20,7 @@
*
*/
-// Based on eos' BitStream implementation
+// Based on xoreos' BitStream implementation
#ifndef COMMON_BITSTREAM_H
#define COMMON_BITSTREAM_H
@@ -43,14 +43,14 @@ namespace Common {
* for valueBits, isLE and isMSB2LSB, reads 32bit little-endian values
* from the data stream and hands out the bits in the order of LSB to MSB.
*/
-template<class STREAM, int valueBits, bool isLE, bool isMSB2LSB>
+template<class STREAM, int valueBits, bool isLE, bool MSB2LSB>
class BitStreamImpl {
private:
STREAM *_stream; ///< The input stream.
DisposeAfterUse::Flag _disposeAfterUse; ///< Should we delete the stream on destruction?
- uint32 _value; ///< Current value.
- uint8 _inValue; ///< Position within the current value.
+ uint64 _bitContainer; ///< The currently available bits.
+ uint8 _bitsLeft; ///< Number of bits currently left in the bit container.
uint32 _size; ///< Total bitstream size (in bits)
uint32 _pos; ///< Current bitstream position (in bits)
@@ -76,37 +76,76 @@ private:
return 0;
}
- /** Read the next data value. */
- inline void readValue() {
- if (_size - _pos < valueBits)
- error("BitStreamImpl::readValue(): End of bit stream reached");
+ /** Fill the container with at least min bits. */
+ inline void fillContainer(size_t min) {
+ while (_bitsLeft < min) {
- _value = readData();
- if (_stream->err() || _stream->eos())
- error("BitStreamImpl::readValue(): Read error");
+ uint64 data;
+ if (_pos + _bitsLeft + valueBits <= _size) {
+ data = readData();
+ } else {
+ // Peeking data out of bounds is well defined and returns 0 bits.
+ // This is for convenience when using speed-up techniques reading
+ // more bits than actually available. Users should call eos() to
+ // check if data was actually read out of bounds. Peeking out of
+ // bounds does not set the eos flag.
+ data = 0;
+ }
+
+ // Move the data value to the right position in the bit container
+ if (MSB2LSB)
+ _bitContainer |= data << (64 - valueBits - _bitsLeft);
+ else
+ _bitContainer |= data << _bitsLeft;
- // If we're reading the bits MSB first, we need to shift the value to that position
- if (isMSB2LSB)
- _value <<= 32 - valueBits;
+ _bitsLeft += valueBits;
}
+}
+
+ /** Get n bits from the bit container. */
+ inline static uint32 getNBits(uint64 value, size_t n) {
+ if (n == 0)
+ return 0;
+
+ const size_t toShift = 64 - n;
+
+ if (MSB2LSB)
+ return value >> toShift;
+ else
+ return (value << toShift) >> toShift;
+ }
+
+ /** Skip already read bits. */
+ inline void skipBits(size_t n) {
+ assert(n <= _bitsLeft);
+
+ // Shift to the next bit
+ if (MSB2LSB)
+ _bitContainer <<= n;
+ else
+ _bitContainer >>= n;
+
+ _bitsLeft -= n;
+ _pos += n;
+ }
public:
/** Create a bit stream using this input data stream and optionally delete it on destruction. */
BitStreamImpl(STREAM *stream, DisposeAfterUse::Flag disposeAfterUse = DisposeAfterUse::NO) :
- _stream(stream), _disposeAfterUse(disposeAfterUse), _value(0), _inValue(0), _pos(0) {
+ _stream(stream), _disposeAfterUse(disposeAfterUse), _bitContainer(0), _bitsLeft(0), _pos(0) {
if ((valueBits != 8) && (valueBits != 16) && (valueBits != 32))
- error("BitStreamImpl: Invalid memory layout %d, %d, %d", valueBits, isLE, isMSB2LSB);
+ error("BitStreamImpl: Invalid memory layout %d, %d, %d", valueBits, isLE, MSB2LSB);
_size = (_stream->size() & ~((uint32) ((valueBits >> 3) - 1))) * 8;
}
/** Create a bit stream using this input data stream. */
BitStreamImpl(STREAM &stream) :
- _stream(&stream), _disposeAfterUse(DisposeAfterUse::NO), _value(0), _inValue(0), _pos(0) {
+ _stream(&stream), _disposeAfterUse(DisposeAfterUse::NO), _bitContainer(0), _bitsLeft(0), _pos(0) {
if ((valueBits != 8) && (valueBits != 16) && (valueBits != 32))
- error("BitStreamImpl: Invalid memory layout %d, %d, %d", valueBits, isLE, isMSB2LSB);
+ error("BitStreamImpl: Invalid memory layout %d, %d, %d", valueBits, isLE, MSB2LSB);
_size = (_stream->size() & ~((uint32) ((valueBits >> 3) - 1))) * 8;
}
@@ -116,41 +155,36 @@ public:
delete _stream;
}
-private:
- uint32 getBit_internal() {
- // Get the current bit
- uint32 b = 0;
- if (isMSB2LSB)
- b = ((_value & 0x80000000) == 0) ? 0 : 1;
- else
- b = ((_value & 1) == 0) ? 0 : 1;
-
- // Shift to the next bit
- if (isMSB2LSB)
- _value <<= 1;
- else
- _value >>= 1;
+ /** Read a bit from the bit stream, without changing the stream's position. */
+ uint peekBit() {
+ fillContainer(1);
- return b;
+ return getNBits(_bitContainer, 1);
}
-public:
/** Read a bit from the bit stream. */
- uint32 getBit() {
- // Check if we need the next value
- if (_inValue == 0)
- readValue();
+ uint getBit() {
+ const uint b = peekBit();
- uint32 b = getBit_internal();
-
- // Increase the position within the current value
- _inValue = (_inValue + 1) % valueBits;
- _pos++;
+ skipBits(1);
return b;
}
/**
+ * Read a multi-bit value from the bit stream, without changing the stream's position.
+ *
+ * The bit order is the same as in getBits().
+ */
+ uint32 peekBits(size_t n) {
+ if (n > 32)
+ error("BitStreamImpl::peekBits(): Too many bits requested to be peeked");
+
+ fillContainer(n);
+ return getNBits(_bitContainer, n);
+ }
+
+ /**
* Read a multi-bit value from the bit stream.
*
* The value is read as if just taken as a whole from the bitstream.
@@ -160,91 +194,15 @@ public:
* If the bitstream is MSB2LSB, the 4-bit value would be 0101.
* If the bitstream is LSB2MSB, the 4-bit value would be 0011.
*/
- uint32 getBits(uint8 n) {
- if (n == 0)
- return 0;
-
+ uint32 getBits(size_t n) {
if (n > 32)
error("BitStreamImpl::getBits(): Too many bits requested to be read");
- // Read the number of bits
- uint32 v = 0;
-
- uint8 nOrig = n;
- if (_inValue) {
- int count = MIN((int)n, valueBits - _inValue);
- for (int i = 0; i < count; ++i) {
- if (isMSB2LSB) {
- v = (v << 1) | getBit_internal();
- } else {
- v = (v >> 1) | (getBit_internal() << 31);
- }
- }
-
- n -= count;
- }
-
- while (n > 0) {
- // NB: readValue doesn't care that _inValue is incorrect here
- readValue();
-
- int count = MIN((int)n, valueBits);
- for (int i = 0; i < count; ++i) {
- if (isMSB2LSB) {
- v = (v << 1) | getBit_internal();
- } else {
- v = (v >> 1) | (getBit_internal() << 31);
- }
- }
-
- n -= count;
- }
-
- _inValue = (_inValue + nOrig) % valueBits;
- _pos += nOrig;
-
- if (!isMSB2LSB)
- v >>= (32 - nOrig);
-
- return v;
- }
-
- /** Read a bit from the bit stream, without changing the stream's position. */
- uint32 peekBit() {
- uint32 value = _value;
- uint8 inValue = _inValue;
- uint32 curStreamPos = _stream->pos();
- uint32 curPos = _pos;
-
- uint32 v = getBit();
-
- _pos = curPos;
- _stream->seek(curStreamPos);
- _inValue = inValue;
- _value = value;
+ const uint32 b = peekBits(n);
- return v;
- }
-
- /**
- * Read a multi-bit value from the bit stream, without changing the stream's position.
- *
- * The bit order is the same as in getBits().
- */
- uint32 peekBits(uint8 n) {
- uint32 value = _value;
- uint8 inValue = _inValue;
- uint32 curStreamPos = _stream->pos();
- uint32 curPos = _pos;
+ skipBits(n);
- uint32 v = getBits(n);
-
- _pos = curPos;
- _stream->seek(curStreamPos);
- _inValue = inValue;
- _value = value;
-
- return v;
+ return b;
}
/**
@@ -262,7 +220,7 @@ public:
if (n >= 32)
error("BitStreamImpl::addBit(): Too many bits requested to be read");
- if (isMSB2LSB)
+ if (MSB2LSB)
x = (x << 1) | getBit();
else
x = (x & ~(1 << n)) | (getBit() << n);
@@ -272,21 +230,29 @@ public:
void rewind() {
_stream->seek(0);
- _value = 0;
- _inValue = 0;
- _pos = 0;
+ _bitContainer = 0;
+ _bitsLeft = 0;
+ _pos = 0;
}
/** Skip the specified amount of bits. */
void skip(uint32 n) {
- while (n-- > 0)
- getBit();
+ while (n > 32) {
+ fillContainer(32);
+ skipBits(32);
+ n -= 32;
+ }
+
+ fillContainer(n);
+ skipBits(n);
}
/** Skip the bits to closest data value border. */
void align() {
- while (_inValue)
- getBit();
+ uint32 bitsAfterBoundary = _pos % valueBits;
+ if (bitsAfterBoundary) {
+ skip(valueBits - bitsAfterBoundary);
+ }
}
/** Return the stream position in bits. */
@@ -302,6 +268,10 @@ public:
bool eos() const {
return _stream->eos() || (_pos >= _size);
}
+
+ static bool isMSB2LSB() {
+ return MSB2LSB;
+ }
};
diff --git a/test/common/bitstream.h b/test/common/bitstream.h
index 0488169183..742f0c18b1 100644
--- a/test/common/bitstream.h
+++ b/test/common/bitstream.h
@@ -50,7 +50,7 @@ public:
private:
template<class MS, class BS>
void tmpl_skip() {
- byte contents[] = { 'a', 'b' };
+ byte contents[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' };
MS ms(contents, sizeof(contents));
@@ -61,6 +61,8 @@ private:
bs.skip(4);
TS_ASSERT_EQUALS(bs.pos(), 9u);
TS_ASSERT_EQUALS(bs.getBits(3), 6u);
+ bs.skip(65);
+ TS_ASSERT_EQUALS(bs.pos(), 77u);
TS_ASSERT(!bs.eos());
}
public:
@@ -133,7 +135,7 @@ private:
TS_ASSERT_EQUALS(bs.pos(), 3u);
bs.skip(8);
TS_ASSERT_EQUALS(bs.pos(), 11u);
- TS_ASSERT_EQUALS(bs.peekBits(5), 2u);
+ TS_ASSERT_EQUALS(bs.peekBits(6), 4u);
TS_ASSERT(!bs.eos());
}
public:
@@ -203,7 +205,7 @@ private:
TS_ASSERT_EQUALS(bs.pos(), 3u);
bs.skip(8);
TS_ASSERT_EQUALS(bs.pos(), 11u);
- TS_ASSERT_EQUALS(bs.peekBits(5), 12u);
+ TS_ASSERT_EQUALS(bs.peekBits(20), 12u);
TS_ASSERT(!bs.eos());
}
public:
@@ -211,4 +213,46 @@ public:
tmpl_peek_bits_lsb<Common::MemoryReadStream, Common::BitStream8LSB>();
tmpl_peek_bits_lsb<Common::BitStreamMemoryStream, Common::BitStreamMemory8LSB>();
}
+
+private:
+ template<class MS, class BS>
+ void tmpl_align() {
+ byte contents[] = { 'a', 'b' };
+
+ MS ms(contents, sizeof(contents));
+
+ BS bs(ms);
+ TS_ASSERT_EQUALS(bs.pos(), 0u);
+ bs.align();
+ TS_ASSERT_EQUALS(bs.pos(), 0u);
+ bs.skip(3);
+ bs.align();
+ TS_ASSERT_EQUALS(bs.pos(), 8u);
+ }
+public:
+ void test_align() {
+ tmpl_align<Common::MemoryReadStream, Common::BitStream8LSB>();
+ tmpl_align<Common::BitStreamMemoryStream, Common::BitStreamMemory8LSB>();
+ }
+
+private:
+ template<class MS, class BS>
+ void tmpl_align_16() {
+ byte contents[] = { 'a', 'b' };
+
+ MS ms(contents, sizeof(contents));
+
+ BS bs(ms);
+ TS_ASSERT_EQUALS(bs.pos(), 0u);
+ bs.align();
+ TS_ASSERT_EQUALS(bs.pos(), 0u);
+ bs.skip(3);
+ bs.align();
+ TS_ASSERT_EQUALS(bs.pos(), 16u);
+ }
+public:
+ void test_align_16() {
+ tmpl_align_16<Common::MemoryReadStream, Common::BitStream16BELSB>();
+ tmpl_align_16<Common::BitStreamMemoryStream, Common::BitStreamMemory16BELSB>();
+ }
};
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 06:34:54 +0000