michael@0: // Compress/RangeCoder/RangeCoderBitTree.h
michael@0: 
michael@0: #ifndef __COMPRESS_RANGECODER_BIT_TREE_H
michael@0: #define __COMPRESS_RANGECODER_BIT_TREE_H
michael@0: 
michael@0: #include "RangeCoderBit.h"
michael@0: #include "RangeCoderOpt.h"
michael@0: 
michael@0: namespace NCompress {
michael@0: namespace NRangeCoder {
michael@0: 
michael@0: template <int numMoveBits, int NumBitLevels>
michael@0: class CBitTreeEncoder
michael@0: {
michael@0:   CBitEncoder<numMoveBits> Models[1 << NumBitLevels];
michael@0: public:
michael@0:   void Init()
michael@0:   {
michael@0:     for(UInt32 i = 1; i < (1 << NumBitLevels); i++)
michael@0:       Models[i].Init();
michael@0:   }
michael@0:   void Encode(CEncoder *rangeEncoder, UInt32 symbol)
michael@0:   {
michael@0:     UInt32 modelIndex = 1;
michael@0:     for (int bitIndex = NumBitLevels; bitIndex != 0 ;)
michael@0:     {
michael@0:       bitIndex--;
michael@0:       UInt32 bit = (symbol >> bitIndex) & 1;
michael@0:       Models[modelIndex].Encode(rangeEncoder, bit);
michael@0:       modelIndex = (modelIndex << 1) | bit;
michael@0:     }
michael@0:   };
michael@0:   void ReverseEncode(CEncoder *rangeEncoder, UInt32 symbol)
michael@0:   {
michael@0:     UInt32 modelIndex = 1;
michael@0:     for (int i = 0; i < NumBitLevels; i++)
michael@0:     {
michael@0:       UInt32 bit = symbol & 1;
michael@0:       Models[modelIndex].Encode(rangeEncoder, bit);
michael@0:       modelIndex = (modelIndex << 1) | bit;
michael@0:       symbol >>= 1;
michael@0:     }
michael@0:   }
michael@0:   UInt32 GetPrice(UInt32 symbol) const
michael@0:   {
michael@0:     symbol |= (1 << NumBitLevels);
michael@0:     UInt32 price = 0;
michael@0:     while (symbol != 1)
michael@0:     {
michael@0:       price += Models[symbol >> 1].GetPrice(symbol & 1);
michael@0:       symbol >>= 1;
michael@0:     }
michael@0:     return price;
michael@0:   }
michael@0:   UInt32 ReverseGetPrice(UInt32 symbol) const
michael@0:   {
michael@0:     UInt32 price = 0;
michael@0:     UInt32 modelIndex = 1;
michael@0:     for (int i = NumBitLevels; i != 0; i--)
michael@0:     {
michael@0:       UInt32 bit = symbol & 1;
michael@0:       symbol >>= 1;
michael@0:       price += Models[modelIndex].GetPrice(bit);
michael@0:       modelIndex = (modelIndex << 1) | bit;
michael@0:     }
michael@0:     return price;
michael@0:   }
michael@0: };
michael@0: 
michael@0: template <int numMoveBits, int NumBitLevels>
michael@0: class CBitTreeDecoder
michael@0: {
michael@0:   CBitDecoder<numMoveBits> Models[1 << NumBitLevels];
michael@0: public:
michael@0:   void Init()
michael@0:   {
michael@0:     for(UInt32 i = 1; i < (1 << NumBitLevels); i++)
michael@0:       Models[i].Init();
michael@0:   }
michael@0:   UInt32 Decode(CDecoder *rangeDecoder)
michael@0:   {
michael@0:     UInt32 modelIndex = 1;
michael@0:     RC_INIT_VAR
michael@0:     for(int bitIndex = NumBitLevels; bitIndex != 0; bitIndex--)
michael@0:     {
michael@0:       // modelIndex = (modelIndex << 1) + Models[modelIndex].Decode(rangeDecoder);
michael@0:       RC_GETBIT(numMoveBits, Models[modelIndex].Prob, modelIndex)
michael@0:     }
michael@0:     RC_FLUSH_VAR
michael@0:     return modelIndex - (1 << NumBitLevels);
michael@0:   };
michael@0:   UInt32 ReverseDecode(CDecoder *rangeDecoder)
michael@0:   {
michael@0:     UInt32 modelIndex = 1;
michael@0:     UInt32 symbol = 0;
michael@0:     RC_INIT_VAR
michael@0:     for(int bitIndex = 0; bitIndex < NumBitLevels; bitIndex++)
michael@0:     {
michael@0:       // UInt32 bit = Models[modelIndex].Decode(rangeDecoder);
michael@0:       // modelIndex <<= 1;
michael@0:       // modelIndex += bit;
michael@0:       // symbol |= (bit << bitIndex);
michael@0:       RC_GETBIT2(numMoveBits, Models[modelIndex].Prob, modelIndex, ; , symbol |= (1 << bitIndex))
michael@0:     }
michael@0:     RC_FLUSH_VAR
michael@0:     return symbol;
michael@0:   }
michael@0: };
michael@0: 
michael@0: template <int numMoveBits>
michael@0: void ReverseBitTreeEncode(CBitEncoder<numMoveBits> *Models, 
michael@0:     CEncoder *rangeEncoder, int NumBitLevels, UInt32 symbol)
michael@0: {
michael@0:   UInt32 modelIndex = 1;
michael@0:   for (int i = 0; i < NumBitLevels; i++)
michael@0:   {
michael@0:     UInt32 bit = symbol & 1;
michael@0:     Models[modelIndex].Encode(rangeEncoder, bit);
michael@0:     modelIndex = (modelIndex << 1) | bit;
michael@0:     symbol >>= 1;
michael@0:   }
michael@0: }
michael@0: 
michael@0: template <int numMoveBits>
michael@0: UInt32 ReverseBitTreeGetPrice(CBitEncoder<numMoveBits> *Models, 
michael@0:     UInt32 NumBitLevels, UInt32 symbol)
michael@0: {
michael@0:   UInt32 price = 0;
michael@0:   UInt32 modelIndex = 1;
michael@0:   for (int i = NumBitLevels; i != 0; i--)
michael@0:   {
michael@0:     UInt32 bit = symbol & 1;
michael@0:     symbol >>= 1;
michael@0:     price += Models[modelIndex].GetPrice(bit);
michael@0:     modelIndex = (modelIndex << 1) | bit;
michael@0:   }
michael@0:   return price;
michael@0: }
michael@0: 
michael@0: template <int numMoveBits>
michael@0: UInt32 ReverseBitTreeDecode(CBitDecoder<numMoveBits> *Models, 
michael@0:     CDecoder *rangeDecoder, int NumBitLevels)
michael@0: {
michael@0:   UInt32 modelIndex = 1;
michael@0:   UInt32 symbol = 0;
michael@0:   RC_INIT_VAR
michael@0:   for(int bitIndex = 0; bitIndex < NumBitLevels; bitIndex++)
michael@0:   {
michael@0:     // UInt32 bit = Models[modelIndex].Decode(rangeDecoder);
michael@0:     // modelIndex <<= 1;
michael@0:     // modelIndex += bit;
michael@0:     // symbol |= (bit << bitIndex);
michael@0:     RC_GETBIT2(numMoveBits, Models[modelIndex].Prob, modelIndex, ; , symbol |= (1 << bitIndex))
michael@0:   }
michael@0:   RC_FLUSH_VAR
michael@0:   return symbol;
michael@0: }
michael@0: 
michael@0: }}
michael@0: 
michael@0: #endif