BitStream.H

Go to the documentation of this file.

/* Copyright 2000-2018 Matt Flax <flatmax@flatmax.org>
   This file is part of GTK+ IOStream class set

   GTK+ IOStream 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 2 of the License, or
   (at your option) any later version.

   GTK+ IOStream 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 have received a copy of the GNU General Public License
   along with GTK+ IOStream
 */

/*
Author: Matt Flax <flatmax@flatmax.org>
Date: 2013.08.23
*/

#ifndef BITSTREAM_H_
#define BITSTREAM_H_

#include <vector>
#include <math.h>
#include <algorithm>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>

#if __BYTE_ORDER != __LITTLE_ENDIAN
#error "iobitstream not tested on big endian systems"
#endif

#include <assert.h>

class BitStream {
protected:
    typedef unsigned int VTYPE; 

    void testMask(unsigned int mSize) const {
#ifndef NDEBUG
        testMask(mSize, genMask(mSize));
#endif
    }

    void testMask(unsigned int mSize, VTYPE compareAgainst) const {
#ifndef NDEBUG
        VTYPE maskCheck=0;
        for (int j=0; j<mSize; j++)
            maskCheck|=(maskCheck<<1|1);
        if (maskCheck!=compareAgainst) {
            fprintf(stderr,"BitStream::testMask(%d) failed\n",mSize);
            fprintf(stderr,"BitStream::compare against  0x%x\n",compareAgainst);
            fprintf(stderr,"BitStream::compare maskcheck 0x%x\n",maskCheck);
            assert("BitStream : testMask is failing");
            abort();
        }
#endif
    }

private:
    std::vector<VTYPE> data; 
    int freeBits; 

    static const unsigned char revChars[];

    BitStream &push_backVType(const VTYPE *tempBits, int N, const int sizeOfT);

    unsigned int VTYPEBits() const {
        return sizeof(VTYPE)*CHAR_BIT;
    }

    unsigned int takenBits() const {
        return (size()>0) ? VTYPEBits()-freeBits : 0;
    }

    VTYPE maskBitsToRight(const unsigned int M, const VTYPE &bits) const {
        if (M>sizeof(VTYPE)*CHAR_BIT)
            assert("BitStream::maskBitsToRight : you can't shift right more bits then the word size. M > sizeof(VTYPE)*8");
        return ((genMask(M)<<(VTYPEBits()-M))&bits)>>(VTYPEBits()-M);
    }

    VTYPE maskOffsetBitsToRight(const unsigned int M, const unsigned int offset, const VTYPE &bits) const {
        if (M+offset>sizeof(VTYPE)*CHAR_BIT)
            assert("BitStream::maskOffsetBitsToRight : you can't shift right more bits then the word size. M+offset > sizeof(VTYPE)*CHAR_BIT");
        return ((genMask(M)<<(VTYPEBits()-M-offset))&bits)>>(VTYPEBits()-M-offset);
    }

    VTYPE maskBitsToLeft(const unsigned int M, const VTYPE bits) const {
        if (M>sizeof(VTYPE)*CHAR_BIT)
            assert("BitStream::maskBitsToLeft : you can't shift left more bits then the word size. M > sizeof(VTYPE)*8");
        return (genMask(M)&bits)<<(VTYPEBits()-M);
    }

    void reverseBits(unsigned char *bits, const unsigned int N) const {
        // switch each char ...
        for (int i=0; i<N/2; i++) {
            char lastChar=revChars[bits[N-1-i]];
            bits[N-1-i]=revChars[bits[i]];
            bits[i]=lastChar;
        }
        if (N%2) // the case where the number of char is odd
            bits[N/2]=revChars[bits[N/2]];
    }

    VTYPE shiftLeftSubword(std::vector<VTYPE>::iterator firstWord, std::vector<VTYPE>::iterator lastWord, const unsigned int N);

    VTYPE shiftRightSubword(std::vector<VTYPE>::iterator firstWord, std::vector<VTYPE>::iterator lastWord, const unsigned int N);

protected:
#ifndef __MINGW32__
    VTYPE genMask(int M) const {
#ifndef NDEBUG // if debugging, test the mask by default
        testMask(M, (VTYPE)((unsigned long )pow(2.,(float)M)-1));
#endif
        return (VTYPE)((unsigned long )pow(2.,(float)M)-1);
    }
#else // mingw seems to have trouble with the unsigned long
    VTYPE genMask(int M) const {
#ifndef NDEBUG // if debugging, test the mask by default
        testMask(M, (VTYPE)((unsigned long long )pow(2.,(float)M)-1));
#endif
        return (VTYPE)((unsigned long long)pow(2.,(float)M)-1);
    }
#endif

public:

    BitStream(); 
    virtual ~BitStream(); 

    std::vector<VTYPE>::size_type size() const;

    float byteSize() const;

    template<typename T>
    T reverseBits(T bits) const {
        unsigned int N=sizeof(T)*CHAR_BIT;
        return reverseBits(bits, N);
    }

    template<typename T>
    T reverseBits(T bits, unsigned int N) const {
        unsigned int charCnt=sizeof(T);
        if (N>charCnt*CHAR_BIT) N=charCnt*CHAR_BIT;
        reverseBits((unsigned char *)&bits, charCnt);
        bits>>=charCnt*CHAR_BIT-N; // roll the word so that there aren't any empty spaces in the LSB
        return bits;
    }

    template<typename T>
    BitStream &operator<<(T bits) {
        int N=sizeof(T)*CHAR_BIT;
        return push_back(bits, N);
    }

    template<typename T>
    BitStream &push_back(const T bits, const int N) {
        if (N>0) {
            VTYPE *tempBits=(VTYPE*)&bits;
            return push_backVType(tempBits, N, sizeof(T));
        }
        return *this;
    }

    template<typename T>
    T pop_back(const unsigned int N) {
        unsigned int NN=N;
        T bits=0;

        if (NN && (size()>0)) {
            //if (NN>sizeof(T)*CHAR_BIT) NN=sizeof(T)*CHAR_BIT;
            if (takenBits()>=NN) { // if we have enough bits loaded in the last word, the acquire from there
                bits=maskBitsToRight(takenBits(), data[data.size()-1])&genMask(NN);
                freeBits+=NN;
                if (freeBits==VTYPEBits()) { // if we have an completely empty last word, then remove it
                    data.resize(data.size()-1);
                    freeBits-=VTYPEBits();
                }
            } else { // handle the case where the takenBits are less then the number requested
                unsigned int tb=takenBits();
                NN-=tb; // start with the available bits
                bits=pop_back<T>(tb);
                T newBits=pop_back<T>(NN);
                bits|=(genMask(NN)&newBits)<<tb;
            }
        }
        return bits;
    }

    template<typename T>
    T pop_front(const unsigned int N) {
        rotateL(N); // rotate so that the required bits are at the end of the strea,
        return pop_back<T>(N); // pop the back of the stream returning those bits
    }

    BitStream &rotateL(const unsigned int N);

    BitStream &rotateR(const unsigned int N);

    std::ostream& hexDump(std::ostream& stream);

    friend std::ostream& operator<<(std::ostream& stream, const BitStream& bitStream);

    void clear();

    int reserve(std::vector<VTYPE>::size_type N);

    std::vector<VTYPE>::size_type capacity() const;

    void dump(void);

    void dumpHex(void);

    template<typename T>
    T getBits(std::vector<VTYPE>::size_type i, unsigned int N) const {
        if ((i+N)>size()) // if none of the requested bits are available, then assert
            assert("BitStream::operator[] : you requested an index which is out of range. The bitstream is smaller then your starting point and the size of your requested type.");
        unsigned int whichWord=i/VTYPEBits(); // the word to extract the data from.
        unsigned int wordLoc=i-whichWord*VTYPEBits(); // the MSB to get from the word
        unsigned int M=std::min<unsigned int>(N,VTYPEBits()-wordLoc);
        T ret=(T)0.;
        while (N>0) { // indicate that some bits were retrieved and keep going until complete
            ret|=maskOffsetBitsToRight(M, wordLoc, data[whichWord++]); // next word's data from the (possibly offset) MSB location shifted to the LSB location
            M=std::min<unsigned int>(N-=M,VTYPEBits()); // find how many to retrieve from the next word
            ret<<=M; // ensure there is enough room in T for the left over bits.
            wordLoc=0;
        }
        return ret;
    }


    template<typename T>
    T operator[](std::vector<VTYPE>::size_type i) const {
        return getBits<T>(i, sizeof(T)*CHAR_BIT);
    }

    template<typename T>
    std::vector<std::vector<VTYPE>::size_type> find(T toFind, const unsigned int N) const {
        BitStream toFindRef; // construct a vector to use for searching
        toFindRef.push_back(toFind, N);
        return find(toFindRef, N);
    }

    std::vector<std::vector<VTYPE>::size_type> find(BitStream toFind, const unsigned int N) const;
};

#endif // BITSTREAM_H_