bitstream.h

/* ScummVM - Graphic Adventure Engine
 *
 * ScummVM is the legal property of its developers, whose names
 * are too numerous to list here. Please refer to the COPYRIGHT
 * file distributed with this source distribution.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

// Based on xoreos' BitStream implementation

#ifndef COMMON_BITSTREAM_H
#define COMMON_BITSTREAM_H

#include "common/scummsys.h"
#include "common/textconsole.h"
#include "common/stream.h"
#include "common/types.h"
#include "common/util.h"

namespace Common {

template<class STREAM, typename CONTAINER, int valueBits, bool isLE, bool MSB2LSB>
class BitStreamImpl {
private:
    STREAM *_stream;                        
    DisposeAfterUse::Flag _disposeAfterUse; 

    CONTAINER _bitContainer;                
    uint8  _bitsLeft;                       
    uint32 _size;                           
    uint32 _pos;                            

    FORCEINLINE uint32 readData() {
        if (isLE) {
            if (valueBits ==  8)
                return _stream->readByte();
            if (valueBits == 16)
                return _stream->readUint16LE();
            if (valueBits == 32)
                return _stream->readUint32LE();
        } else {
            if (valueBits ==  8)
                return _stream->readByte();
            if (valueBits == 16)
                return _stream->readUint16BE();
            if (valueBits == 32)
                return _stream->readUint32BE();
        }

        assert(false);
        return 0;
    }

    FORCEINLINE void fillContainer(size_t min) {
        while (_bitsLeft < min) {

            CONTAINER 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. 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 << ((sizeof(_bitContainer) * 8) - valueBits - _bitsLeft);
            else
                _bitContainer |= data << _bitsLeft;

            _bitsLeft += valueBits;
        }
}

    FORCEINLINE static uint32 getNBits(CONTAINER value, size_t n) {
        if (n == 0)
            return 0;

        const size_t toShift = (sizeof(value) * 8) - n;

        if (MSB2LSB)
            return value >> toShift;
        else
            return (value << toShift) >> toShift;
    }

    FORCEINLINE 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:
    BitStreamImpl(STREAM *stream, DisposeAfterUse::Flag disposeAfterUse = DisposeAfterUse::NO) :
        _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, int(isLE), int(MSB2LSB));

        _size = (_stream->size() & ~((uint32) ((valueBits >> 3) - 1))) * 8;
    }

    BitStreamImpl(STREAM &stream) :
        _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, int(isLE), int(MSB2LSB));

        _size = (_stream->size() & ~((uint32) ((valueBits >> 3) - 1))) * 8;
    }

    ~BitStreamImpl() {
        if (_disposeAfterUse == DisposeAfterUse::YES)
            delete _stream;
    }

    uint peekBit() {
        fillContainer(1);

        return getNBits(_bitContainer, 1);
    }

    uint getBit() {
        const uint b = peekBit();

        skipBits(1);

        return b;
    }

    template<int n>
    uint32 peekBits() {
        if (n > 32)
            error("BitStreamImpl::peekBits(): Too many bits requested to be peeked");

        fillContainer(n);
        return getNBits(_bitContainer, n);
    }

    template<int n>
    uint32 getBits() {
        if (n > 32)
            error("BitStreamImpl::getBits(): Too many bits requested to be read");

        const uint32 b = peekBits<n>();

        skipBits(n);

        return b;
    }

    uint32 peekBits(size_t n) {
        if (n > 32)
            error("BitStreamImpl::peekBits(): Too many bits requested to be peeked");

        fillContainer(n);
        return getNBits(_bitContainer, n);
    }

    uint32 getBits(size_t n) {
        if (n > 32)
            error("BitStreamImpl::getBits(): Too many bits requested to be read");

        const uint32 b = peekBits(n);

        skipBits(n);

        return b;
    }

    void addBit(uint32 &x, uint32 n) {
        if (n >= 32)
            error("BitStreamImpl::addBit(): Too many bits requested to be read");

        if (MSB2LSB)
            x = (x << 1) | getBit();
        else
            x = (x & ~(1 << n)) | (getBit() << n);
    }

    void rewind() {
        _stream->seek(0);

        _bitContainer = 0;
        _bitsLeft     = 0;
        _pos          = 0;
    }

    void skip(uint32 n) {
        if (n >= _bitsLeft) {
            n -= _bitsLeft;
            skipBits(_bitsLeft);
        }

        while (n > 32) {
            fillContainer(32);
            skipBits(32);
            n -= 32;
        }

        fillContainer(n);
        skipBits(n);
    }

    void align() {
        uint32 bitsAfterBoundary = _pos % valueBits;
        if (bitsAfterBoundary) {
            skip(valueBits - bitsAfterBoundary);
        }
    }

    uint32 pos() const {
        return _pos;
    }

    uint32 size() const {
        return _size;
    }

    bool eos() const {
        return _stream->eos() || (_pos >= _size);
    }

    static bool isMSB2LSB() {
        return MSB2LSB;
    }
};



class BitStreamMemoryStream {
private:
    const byte * const _ptrOrig;
    const byte *_ptr;
    const uint32 _size;
    uint32 _pos;
    DisposeAfterUse::Flag _disposeMemory;
    bool _eos;
public:
    BitStreamMemoryStream(const byte *dataPtr, uint32 dataSize, DisposeAfterUse::Flag disposeMemory = DisposeAfterUse::NO) :
        _ptrOrig(dataPtr),
        _ptr(dataPtr),
        _size(dataSize),
        _pos(0),
        _disposeMemory(disposeMemory),
        _eos(false) {}

    ~BitStreamMemoryStream() {
        if (_disposeMemory)
            free(const_cast<byte *>(_ptrOrig));
    }

    bool eos() const {
        return _eos;
    }

    bool err() const {
        return false;
    }

    uint32 pos() const {
        return _pos;
    }

    uint32 size() const {
        return _size;
    }

    bool seek(uint32 offset) {
        assert(offset <= _size);

        _eos = false;
        _pos = offset;
        _ptr = _ptrOrig + _pos;
        return true;
    }

    byte readByte() {
        if (_pos >= _size) {
            _eos = true;
            return 0;
        }

        _pos++;
        return *_ptr++;
    }

    uint16 readUint16LE() {
        if (_pos + 2 > _size) {
            _eos = true;
            if (_pos < _size) {
                _pos++;
                return *_ptr++;
            } else {
                return 0;
            }
        }

        uint16 val = READ_LE_UINT16(_ptr);

        _pos += 2;
        _ptr += 2;

        return val;
    }

    uint16 readUint16BE() {
        if (_pos + 2 > _size) {
            _eos = true;
            if (_pos < _size) {
                _pos++;
                return (*_ptr++) << 8;
            } else {
                return 0;
            }
        }

        uint16 val = READ_LE_UINT16(_ptr);

        _pos += 2;
        _ptr += 2;

        return val;
    }

    uint32 readUint32LE() {
        if (_pos + 4 > _size) {
            uint32 val = readByte();
            val |= (uint32)readByte() << 8;
            val |= (uint32)readByte() << 16;
            val |= (uint32)readByte() << 24;

            return val;
        }

        uint32 val = READ_LE_UINT32(_ptr);

        _pos += 4;
        _ptr += 4;

        return val;
    }

    uint32 readUint32BE() {
        if (_pos + 4 > _size) {
            uint32 val = (uint32)readByte() << 24;
            val |= (uint32)readByte() << 16;
            val |= (uint32)readByte() << 8;
            val |= (uint32)readByte();

            return val;
        }

        uint32 val = READ_BE_UINT32(_ptr);

        _pos += 4;
        _ptr += 4;

        return val;
    }

};

typedef BitStreamImpl<SeekableReadStream, uint64, 8, false, true > BitStream8MSB;
typedef BitStreamImpl<SeekableReadStream, uint64, 8, false, false> BitStream8LSB;

typedef BitStreamImpl<SeekableReadStream, uint64, 16, true , true > BitStream16LEMSB;
typedef BitStreamImpl<SeekableReadStream, uint64, 16, true , false> BitStream16LELSB;
typedef BitStreamImpl<SeekableReadStream, uint64, 16, false, true > BitStream16BEMSB;
typedef BitStreamImpl<SeekableReadStream, uint64, 16, false, false> BitStream16BELSB;

typedef BitStreamImpl<SeekableReadStream, uint64, 32, true , true > BitStream32LEMSB;
typedef BitStreamImpl<SeekableReadStream, uint64, 32, true , false> BitStream32LELSB;
typedef BitStreamImpl<SeekableReadStream, uint64, 32, false, true > BitStream32BEMSB;
typedef BitStreamImpl<SeekableReadStream, uint64, 32, false, false> BitStream32BELSB;



typedef BitStreamImpl<BitStreamMemoryStream, uint64, 8, false, true > BitStreamMemory8MSB;
typedef BitStreamImpl<BitStreamMemoryStream, uint64, 8, false, false> BitStreamMemory8LSB;

typedef BitStreamImpl<BitStreamMemoryStream, uint64, 16, true , true > BitStreamMemory16LEMSB;
typedef BitStreamImpl<BitStreamMemoryStream, uint64, 16, true , false> BitStreamMemory16LELSB;
typedef BitStreamImpl<BitStreamMemoryStream, uint64, 16, false, true > BitStreamMemory16BEMSB;
typedef BitStreamImpl<BitStreamMemoryStream, uint64, 16, false, false> BitStreamMemory16BELSB;

typedef BitStreamImpl<BitStreamMemoryStream, uint64, 32, true , true > BitStreamMemory32LEMSB;
typedef BitStreamImpl<BitStreamMemoryStream, uint64, 32, true , false> BitStreamMemory32LELSB;
typedef BitStreamImpl<BitStreamMemoryStream, uint64, 32, false, true > BitStreamMemory32BEMSB;
typedef BitStreamImpl<BitStreamMemoryStream, uint64, 32, false, false> BitStreamMemory32BELSB;

} // End of namespace Common

#endif // COMMON_BITSTREAM_H