arithCoder.hpp

Go to the documentation of this file.

// Copyright (c) 2013 Michael D. Adams
// All rights reserved.

// __START_OF_LICENSE__
// 
// Copyright (c) 2015 Michael D. Adams
// All rights reserved.
// 
// This file is part of the Signal Processing Library (SPL).
// 
// 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,
// 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; see the file LICENSE.  If not,
// see <http://www.gnu.org/licenses/>.
// 
// __END_OF_LICENSE__

#ifndef SPL_arithCoder_hpp
#define SPL_arithCoder_hpp

// Header files

#include <SPL/config.hpp>
#include <cassert>
#include <fstream>
#include <iostream>
#include <vector>
#include <SPL/bitStream.hpp>

//

// In the GIC code base, the following symbol was defined.
// The following symbol should probably not normally be defined.
#define SPL_ArithCoder_CodeSize32

#define SPL_ArithCoder_Entropy

#if defined(SPL_ArithCoder_CodeSize32)
#define SPL_ArithCoder_BigType unsigned long long
#define SPL_ArithCoder_NumBigBits 64
#define SPL_ArithCoder_CodeType unsigned long
#define SPL_ArithCoder_NumCodeBits 32
#define SPL_ArithCoder_FreqType unsigned long
#define SPL_ArithCoder_NumFreqBits 30
#else
#define SPL_ArithCoder_BigType unsigned long
#define SPL_ArithCoder_NumBigBits 32
#define SPL_ArithCoder_CodeType unsigned short
#define SPL_ArithCoder_NumCodeBits 16
#define SPL_ArithCoder_FreqType unsigned short
#define SPL_ArithCoder_NumFreqBits 14
#endif

// NOTE: This probably ought to be 255 (one less than a power of 2).
#define SPL_ArithCoder_DefaultMaxFreq 256

// These types need to be revisited.  Maybe they should be changed.
// For now, they have been flagged in the code by these special names.
#define SPL_ArithCoder_long long
#define SPL_ArithCoder_ulong unsigned long

namespace SPL {

// Arithmetic Coder Core: Common Encoder/Decoder Class


class ArithCoder
{
public:

        typedef SPL_ArithCoder_FreqType Freq;

        static const int FreqBits = SPL_ArithCoder_NumFreqBits;

        static const Freq MaxFreq = (1ULL << FreqBits) - 1;

protected:

        // The type for a code word.
        typedef SPL_ArithCoder_CodeType Code;

        // A type providing sufficient dynamic range for code word computations.
        typedef SPL_ArithCoder_BigType BigCode;

        static const int BigBits = SPL_ArithCoder_NumBigBits;
        static const int CodeBits = SPL_ArithCoder_NumCodeBits;
        static const Code MaxCode = (1ULL << CodeBits) - 1;
        static const Code FirstQuart = (MaxCode >> 2) + 1;
        static const Code Half = 2 * FirstQuart;
        static const Code ThirdQuart = 3 * FirstQuart;
};


// M-ary Arithmetic Coder Core: Encoder Class


class ArithEncoder : public ArithCoder
{
public:

        // Constructors and destructor

        ArithEncoder(OutputBitStream* out = nullptr);

        ~ArithEncoder();

        // Set and get various state

        void setOutput(OutputBitStream* out);

        OutputBitStream* getOutput() const;

        SPL_ArithCoder_ulong getSymCount() const;

        SPL_ArithCoder_ulong getBitCount() const;

        // Encoding

        int start();

        int terminate();

        int encode(Freq lowFreq, Freq highFreq, Freq totalFreq);

        // Debugging

        static void setDebugLevel(int debugLevel);

        static void setDebugStream(std::ostream& out);

        static std::ostream& getDebugStream();

        void dump(std::ostream& out) const;

private:

        // The copy constructor is declared but not defined in order to
        // prevent copying.
        ArithEncoder(const ArithEncoder&);

        // The copy constructor is declared but not defined in order to
        // prevent copying.
        ArithEncoder& operator=(const ArithEncoder&);

        // The debug level.
        static int debugLevel_;

        // The stream to use for debugging output.
        static std::ostream* debugStream_;

        inline int renorm();

        int bitPlusFollow(int bit);

        // The bit stream to which the encoder output is to be written.
        OutputBitStream* out_;

        // The low end of the current interval.
        Code low_;

        // The high end of the current interval.
        Code high_;

        // The number of bits yet to be output.
        unsigned long bitsOutstanding_;

        // The number of bits output so far.
        SPL_ArithCoder_ulong bitCount_;

        // The number of symbols encoded so far.
        SPL_ArithCoder_ulong symCount_;
};

inline void ArithEncoder::setOutput(OutputBitStream* out)
{
        out_ = out;
}

inline OutputBitStream* ArithEncoder::getOutput() const
{
        return out_;
}

inline SPL_ArithCoder_ulong ArithEncoder::getSymCount() const
{
        return symCount_;
}

inline SPL_ArithCoder_ulong ArithEncoder::getBitCount() const
{
        return bitCount_ + bitsOutstanding_;
}

inline void ArithEncoder::setDebugLevel(int debugLevel)
{
        debugLevel_ = debugLevel;
}

inline void ArithEncoder::setDebugStream(std::ostream& out)
{
        debugStream_ = &out;
}

inline std::ostream& ArithEncoder::getDebugStream()
{
        return debugStream_ ? (*debugStream_) : std::cerr;
}


// M-ary Arithmetic Coder Core: Decoder Class


class ArithDecoder : public ArithCoder
{
public:

        // Constructors and destructor

        ArithDecoder(InputBitStream* in = nullptr);

        ~ArithDecoder();

        // Set and get various state

        InputBitStream* getInput() const;

        void setInput(InputBitStream* in);

        SPL_ArithCoder_ulong getBitCount() const;

        SPL_ArithCoder_ulong getSymCount() const;

        // Decoding

        int start();

        int terminate();

        int decode(Freq totalFreq, Freq& target);

        int adjust(Freq lowFreq, Freq highFreq, Freq totalFreq);

        // Debugging

        static void setDebugLevel(int debugLevel);

        static void setDebugStream(std::ostream& out);

        std::ostream& getDebugStream();

        void dump(std::ostream& out) const;

private:

        // The debug level.
        static int debugLevel_;

        // The stream to be used for debugging output.
        static std::ostream* debugStream_;

        // The copy constructor is declared but not defined in order to
        // prevent copying.
        ArithDecoder(const ArithDecoder&);

        // The copy constructor is declared but not defined in order to
        // prevent copying.
        ArithDecoder& operator=(const ArithDecoder&);

        inline int renorm();

        // The bit stream from which to read data to decode.
        InputBitStream* in_;

        // The code value.
        Code value_;

        // The low end of the current interval.
        Code low_;

        // The high end of the current interval.
        Code high_;

        // The number of symbols that have been decoded so far.
        SPL_ArithCoder_ulong symCount_;

        // The number of bits that have been read so far.
        SPL_ArithCoder_ulong bitCount_;
};

inline InputBitStream* ArithDecoder::getInput() const
{
        return in_;
}

inline SPL_ArithCoder_ulong ArithDecoder::getSymCount() const
{
        return symCount_;
}

inline SPL_ArithCoder_ulong ArithDecoder::getBitCount() const
{
        return bitCount_;
}

inline void ArithDecoder::setDebugLevel(int debugLevel)
{
        debugLevel_ = debugLevel;
}

inline void ArithDecoder::setDebugStream(std::ostream& out)
{
        debugStream_ = &out;
}

inline std::ostream& ArithDecoder::getDebugStream()
{
        return debugStream_ ? (*debugStream_) : std::cerr;
}

inline void ArithDecoder::setInput(InputBitStream* in)
{
        in_ = in;
}


// Simple Probability Model


class ArithCoderModel
{
public:

        // Constructors and destructor

        ArithCoderModel(int numSyms, ArithCoder::Freq maxFreq);

        ~ArithCoderModel();

        // Lookup and update

        void lookup(int sym, ArithCoder::Freq& lowFreq,
          ArithCoder::Freq& highFreq, ArithCoder::Freq& totalFreq) const;

        void invLookup(ArithCoder::Freq targetFreq, int& sym,
          ArithCoder::Freq& lowFreq, ArithCoder::Freq& highFreq,
          ArithCoder::Freq& totalFreq) const;

        void update(int sym);

        // Set and get various state

        int getNumSyms() const;

        void setAdaptive(bool adaptive);

        bool getAdaptive() const;

        SPL_ArithCoder_ulong getSymCount(int sym) const;

        SPL_ArithCoder_ulong getTotalSymCount() const;

        // Set and get probabilities

        ArithCoder::Freq getTotalFreq() const;

        // NEW: 2015-10-23
        ArithCoder::Freq getMaxFreq() const;

        void setProbs(const std::vector<ArithCoder::Freq>& freqs);

        void getProbs(std::vector<ArithCoder::Freq>& freqs);

        // Debugging

        static void setDebugLevel(int debugLevel);

        static void setDebugStream(std::ostream& out);

        static std::ostream& getDebugStream();

        void dump(std::ostream& out) const;

private:

        // The copy constructor is declared but not defined in order to
        // prevent copying.
        ArithCoderModel(const ArithCoderModel&);

        // The copy constructor is declared but not defined in order to
        // prevent copying.
        ArithCoderModel& operator=(const ArithCoderModel&);

        // The debug level.
        static int debugLevel_;

        // The stream to use for debugging output.
        static std::ostream* debugStream_;

        // Lookup table that maps from symbols to indices.
        // The size of the vector is the number of symbols.
        std::vector<int> symToIdx_;

        // Lookup table that maps from indices to symbols.
        // The size of the vector is one greater than the number of symbols.
        std::vector<int> idxToSym_;

        // The symbol frequencies (ordered by symbol index).
        // The size of the vector is one greater than the number of symbols.
        // The element with index zero is always zero?
        std::vector<ArithCoder::Freq> freqs_;

        // The cumulative frequencies.
        // The size of the vector is one greater than the number of symbols.
        std::vector<ArithCoder::Freq> cumFreqs_;

        // The number of times each symbol has been seen so far.
        std::vector<SPL_ArithCoder_ulong> symCnts_;

        // The total number of symbols that have been seen so far.
        SPL_ArithCoder_ulong totalSymCnt_;

        // The normalizing denominator for frequencies.
        ArithCoder::Freq maxFreq_;

        // The adaptivity mode.
        bool adaptive_;
};

inline SPL_ArithCoder_ulong ArithCoderModel::getSymCount(int sym) const
{
        return symCnts_[sym];
}

inline SPL_ArithCoder_ulong ArithCoderModel::getTotalSymCount() const
{
        return totalSymCnt_;
}

inline void ArithCoderModel::setAdaptive(bool adaptive)
{
        adaptive_ = adaptive;
}

inline bool ArithCoderModel::getAdaptive() const
{
        return adaptive_;
}

// NEW: 2015-10-23
inline ArithCoder::Freq ArithCoderModel::getMaxFreq() const
{
        return maxFreq_;
}

inline ArithCoder::Freq ArithCoderModel::getTotalFreq() const
{
        return cumFreqs_[0];
}

inline int ArithCoderModel::getNumSyms() const
{
        return symToIdx_.size();
}

inline void ArithCoderModel::setDebugLevel(int debugLevel)
{
        debugLevel_ = debugLevel;
}

inline void ArithCoderModel::setDebugStream(std::ostream& out)
{
        debugStream_ = &out;
}

inline std::ostream& ArithCoderModel::getDebugStream()
{
        return debugStream_ ? (*debugStream_) : std::cerr;
}


// M-ary Arithmetic Coder: Encoder Class

class MultiArithEncoder
{
public:

        // Constructors and destructor

        MultiArithEncoder(int maxContexts, OutputBitStream* out = nullptr);

        ~MultiArithEncoder();

        //

        OutputBitStream* getOutput();

        void setOutput(OutputBitStream* out);

        SPL_ArithCoder_ulong getSymCount() const;

        SPL_ArithCoder_ulong getBitCount() const;

        int getMaxContexts() const;

        void setContext(int contextId, int numSyms);

        void setContext(int contextId, const std::vector<ArithCoder::Freq>&
          symFreqs, bool adaptive);

        // Encoding

        int start();

        int terminate();

        int encodeRegular(int contextId, int sym);

        int encodeBypass(int numSyms, int sym);

        // Debugging

        static void setDebugLevel(int debugLevel);

        static void setDebugStream(std::ostream& out);

        static std::ostream& getDebugStream();

        void dump(std::ostream& out) const;

private:

        // The debug level.
        static int debugLevel_;

        // The stream to use for debugging output.
        static std::ostream* debugStream_;

        // The copy constructor is declared but not defined in order to
        // prevent copying.
        MultiArithEncoder(const MultiArithEncoder&);

        // The copy constructor is declared but not defined in order to
        // prevent copying.
        MultiArithEncoder& operator=(const MultiArithEncoder&);

        // The arithmetic coding engine.
        ArithEncoder enc_;

        // The context information.
        std::vector<ArithCoderModel*> contexts_;
};

inline std::ostream& MultiArithEncoder::getDebugStream()
{
        return (debugStream_) ? (*debugStream_) : std::cerr;
}

inline OutputBitStream* MultiArithEncoder::getOutput()
{
        return enc_.getOutput();
}

inline void MultiArithEncoder::setOutput(OutputBitStream* out)
{
        enc_.setOutput(out);
}

inline SPL_ArithCoder_ulong MultiArithEncoder::getSymCount() const
{
        return enc_.getSymCount();
}

inline SPL_ArithCoder_ulong MultiArithEncoder::getBitCount() const
{
        return enc_.getBitCount();
}

inline void MultiArithEncoder::setDebugLevel(int debugLevel)
{
        debugLevel_ = debugLevel;
}

inline void MultiArithEncoder::setDebugStream(std::ostream& debugStream)
{
        debugStream_ = &debugStream;
}

inline int MultiArithEncoder::getMaxContexts() const
{
        return contexts_.size();
}

// M-ary Arithmetic Coder: Decoder Class

class MultiArithDecoder
{
public:

        // Constructors and destructor

        MultiArithDecoder(int maxContexts, InputBitStream* in = nullptr);

        ~MultiArithDecoder();

        // Set and get various state

        InputBitStream* getInput() const;

        void setInput(InputBitStream* in);

        SPL_ArithCoder_ulong getBitCount() const;

        SPL_ArithCoder_ulong getSymCount() const;

        // Context management

        int getMaxContexts() const;

        void setContext(int contextId, int numSyms);

        void setContext(int contextId, const std::vector<ArithCoder::Freq>&
          symFreqs, bool adaptive);

        // Decoding

        int start();

        int terminate();

        int decodeRegular(int contextId);

        int decodeBypass(int numSyms);

        // Debugging

        static void setDebugLevel(int debugLevel);

        static void setDebugStream(std::ostream& out);

        static std::ostream& getDebugStream();

        void dump(std::ostream& out) const;

private:

        // The debug level.
        static int debugLevel_;

        // The stream to use for debugging output.
        static std::ostream* debugStream_;

        // The copy constructor is declared but not defined in order to
        // prevent copying.
        MultiArithDecoder(const MultiArithDecoder&);

        // The copy constructor is declared but not defined in order to
        // prevent copying.
        MultiArithDecoder& operator=(const MultiArithDecoder&);

        // The arithmetic decoding engine.
        ArithDecoder dec_;

        // The context information.
        std::vector<ArithCoderModel*> contexts_;
};

inline std::ostream& MultiArithDecoder::getDebugStream()
{
        return debugStream_ ? (*debugStream_) : std::cerr;
}

inline InputBitStream* MultiArithDecoder::getInput() const
{
        return dec_.getInput();
}

inline void MultiArithDecoder::setInput(InputBitStream* in)
{
        dec_.setInput(in);
}

inline SPL_ArithCoder_ulong MultiArithDecoder::getBitCount() const
{
        return dec_.getBitCount();
}

inline SPL_ArithCoder_ulong MultiArithDecoder::getSymCount() const
{
        return dec_.getSymCount();
}

inline void MultiArithDecoder::setDebugLevel(int debugLevel)
{
        debugLevel_ = debugLevel;
}

inline void MultiArithDecoder::setDebugStream(std::ostream& debugStream)
{
        debugStream_ = &debugStream;
}

inline int MultiArithDecoder::getMaxContexts() const
{
        return contexts_.size();
}

// Binary Arithmetic Coder

struct BinArithCoderContextStat
{
        SPL_ArithCoder_ulong numOnes;
        SPL_ArithCoder_ulong numSyms;
};

// Binary Arithmetic Encoder

class BinArithEncoder
{
public:

        using Freq = ArithCoder::Freq;

        // Constructors and destructor

        BinArithEncoder(int numContexts, OutputBitStream* out = nullptr);

        ~BinArithEncoder();

        // Set and get various state

        int getNumContexts() const;

        SPL_ArithCoder_ulong getSymCount() const;

        SPL_ArithCoder_ulong getBitCount() const;

        void setOutput(OutputBitStream* out);

        OutputBitStream* getOutput() const;

        // Context management

        void getContextStats(std::vector<BinArithCoderContextStat>& stats) const;

        void setContextState(int contextId, ArithCoder::Freq oneFreq,
          ArithCoder::Freq totalFreq, ArithCoder::Freq maxFreq, bool adaptive);

        void getContextState(int contextId, ArithCoder::Freq& oneFreq,
          ArithCoder::Freq& totalFreq, ArithCoder::Freq& maxFreq, bool& adaptive);

        // Encoding

        int start();

        int encodeRegular(int contextId, int binVal);

        int encodeBypass(int binVal);

        int terminate();

        // Debugging

        void dump(std::ostream& out) const;

        void dumpModels(std::ostream& out) const;

        static void setDebugLevel(int debugLevel);

        static void setDebugStream(std::ostream& out);

        static std::ostream& getDebugStream();

#if defined(SPL_ArithCoder_Entropy)
        long double getEntropy() const;
        void clearEntropy();
#endif

private:

        // The debug level.
        static int debugLevel_;

        // The stream to use for debugging output.
        static std::ostream* debugStream_;

        // The copy constructor is declared but not defined in order to
        // prevent copying.
        BinArithEncoder(const BinArithEncoder&);

        // The copy constructor is declared but not defined in order to
        // prevent copying.
        BinArithEncoder& operator=(const BinArithEncoder&);

        // The arithmetic coding engine.
        ArithEncoder enc_;

        // The context information.
        std::vector<ArithCoderModel*> models_;

        // The number of one symbols encoded in bypass mode.
        SPL_ArithCoder_ulong bypassOneCnt_;

        // The total number of symbols encoded in bypass mode.
        SPL_ArithCoder_ulong bypassSymCnt_;

#if defined(SPL_ArithCoder_Entropy)
        long double entropy_;
#endif
};

#if defined(SPL_ArithCoder_Entropy)
inline long double BinArithEncoder::getEntropy() const
{
        return entropy_;
}
inline void BinArithEncoder::clearEntropy()
{
        entropy_ = 0;
}
#endif

inline SPL_ArithCoder_ulong BinArithEncoder::getSymCount() const
{
        return enc_.getSymCount();
}

inline SPL_ArithCoder_ulong BinArithEncoder::getBitCount() const
{
        return enc_.getBitCount();
}

inline OutputBitStream* BinArithEncoder::getOutput() const
{
        return enc_.getOutput();
}

inline int BinArithEncoder::getNumContexts() const
{
        return models_.size();
}

inline void BinArithEncoder::setDebugStream(std::ostream& out)
{
        ArithEncoder::setDebugStream(out);
        debugStream_ = &out;
}

inline std::ostream& BinArithEncoder::getDebugStream()
{
        return debugStream_ ? (*debugStream_) : std::cerr;
}

inline void BinArithEncoder::setDebugLevel(int debugLevel)
{
        ArithEncoder::setDebugLevel(debugLevel >> 8);
        debugLevel_ = debugLevel;
}

inline void BinArithEncoder::setOutput(OutputBitStream* out)
{
        enc_.setOutput(out);
}

// Binary Arithmetic Coder: Decoder Class

class BinArithDecoder
{
public:

        using Freq = ArithCoder::Freq;

        // Constructors and destructor

        BinArithDecoder(int numContexts, InputBitStream* in = nullptr);

        ~BinArithDecoder();

        // Set and get various state

        SPL_ArithCoder_ulong getSymCount() const;

        SPL_ArithCoder_ulong getBitCount() const;

        void setInput(InputBitStream* in);

        InputBitStream* getInput() const;

        // Context management

        int getNumContexts() const;

        void setContextState(int contextId, ArithCoder::Freq oneFreq,
          ArithCoder::Freq totalFreq, ArithCoder::Freq maxFreq, bool adaptive);

        void getContextState(int contextId, ArithCoder::Freq& oneFreq,
          ArithCoder::Freq& totalFreq, ArithCoder::Freq& maxFreq, bool& adaptive);

        // Decoding

        int start();

        int terminate();

        int decodeRegular(int contextId);

        int decodeBypass();

        // Debugging

        void dump(std::ostream& out) const;

        static void setDebugLevel(int debugLevel);

        static void setDebugStream(std::ostream& out);

        static std::ostream& getDebugStream();

#if defined(SPL_ArithCoder_Entropy)
        long double getEntropy() const;
        void clearEntropy();
#endif

private:

        // The debug level.
        static int debugLevel_;

        // The stream used for debugging output.
        static std::ostream* debugStream_;

        // The copy constructor is declared but not defined in order to
        // prevent copying.
        BinArithDecoder(const BinArithDecoder&);

        // The copy constructor is declared but not defined in order to
        // prevent copying.
        BinArithDecoder& operator=(const BinArithDecoder&);

        // The arithmetic decoding engine.
        ArithDecoder dec_;

        // The context information.
        std::vector<ArithCoderModel*> models_;

#if defined(SPL_ArithCoder_Entropy)
        long double entropy_;
#endif

};

#if defined(SPL_ArithCoder_Entropy)
inline long double BinArithDecoder::getEntropy() const
{
        return entropy_;
}
inline void BinArithDecoder::clearEntropy()
{
        entropy_ = 0;
}
#endif

inline SPL_ArithCoder_ulong BinArithDecoder::getSymCount() const
{
        return dec_.getSymCount();
}

inline SPL_ArithCoder_ulong BinArithDecoder::getBitCount() const
{
        return dec_.getBitCount();
}

inline InputBitStream* BinArithDecoder::getInput() const
{
        return dec_.getInput();
}

inline int BinArithDecoder::getNumContexts() const
{
        return models_.size();
}

inline void BinArithDecoder::setDebugStream(std::ostream& out)
{
        ArithDecoder::setDebugStream(out);
        debugStream_ = &out;
}

inline std::ostream& BinArithDecoder::getDebugStream()
{
        return debugStream_ ? (*debugStream_) : std::cerr;
}

inline void BinArithDecoder::setDebugLevel(int debugLevel)
{
        ArithDecoder::setDebugLevel(debugLevel >> 8);
        debugLevel_ = debugLevel;
}

inline void BinArithDecoder::setInput(InputBitStream* in)
{
        dec_.setInput(in);
}

//

}

#endif