release/src-rt/linux/linux-2.6/scripts/squashfs/lzma/C/7zip/Compress/RangeCoder/RangeCoderBitTree.h

   1 // Compress/RangeCoder/RangeCoderBitTree.h
   2
   3 #ifndef __COMPRESS_RANGECODER_BIT_TREE_H
   4 #define __COMPRESS_RANGECODER_BIT_TREE_H
   5
   6 #include "RangeCoderBit.h"
   7 #include "RangeCoderOpt.h"
   8
   9 namespace NCompress {
  10 namespace NRangeCoder {
  11
  12 template <int numMoveBits, int NumBitLevels>
  13 class CBitTreeEncoder
  14 {
  15   CBitEncoder<numMoveBits> Models[1 << NumBitLevels];
  16 public:
  17   void Init()
  18   {
  19     for(UInt32 i = 1; i < (1 << NumBitLevels); i++)
  20       Models[i].Init();
  21   }
  22   void Encode(CEncoder *rangeEncoder, UInt32 symbol)
  23   {
  24     UInt32 modelIndex = 1;
  25     for (int bitIndex = NumBitLevels; bitIndex != 0 ;)
  26     {
  27       bitIndex--;
  28       UInt32 bit = (symbol >> bitIndex) & 1;
  29       Models[modelIndex].Encode(rangeEncoder, bit);
  30       modelIndex = (modelIndex << 1) | bit;
  31     }
  32   };
  33   void ReverseEncode(CEncoder *rangeEncoder, UInt32 symbol)
  34   {
  35     UInt32 modelIndex = 1;
  36     for (int i = 0; i < NumBitLevels; i++)
  37     {
  38       UInt32 bit = symbol & 1;
  39       Models[modelIndex].Encode(rangeEncoder, bit);
  40       modelIndex = (modelIndex << 1) | bit;
  41       symbol >>= 1;
  42     }
  43   }
  44   UInt32 GetPrice(UInt32 symbol) const
  45   {
  46     symbol |= (1 << NumBitLevels);
  47     UInt32 price = 0;
  48     while (symbol != 1)
  49     {
  50       price += Models[symbol >> 1].GetPrice(symbol & 1);
  51       symbol >>= 1;
  52     }
  53     return price;
  54   }
  55   UInt32 ReverseGetPrice(UInt32 symbol) const
  56   {
  57     UInt32 price = 0;
  58     UInt32 modelIndex = 1;
  59     for (int i = NumBitLevels; i != 0; i--)
  60     {
  61       UInt32 bit = symbol & 1;
  62       symbol >>= 1;
  63       price += Models[modelIndex].GetPrice(bit);
  64       modelIndex = (modelIndex << 1) | bit;
  65     }
  66     return price;
  67   }
  68 };
  69
  70 template <int numMoveBits, int NumBitLevels>
  71 class CBitTreeDecoder
  72 {
  73   CBitDecoder<numMoveBits> Models[1 << NumBitLevels];
  74 public:
  75   void Init()
  76   {
  77     for(UInt32 i = 1; i < (1 << NumBitLevels); i++)
  78       Models[i].Init();
  79   }
  80   UInt32 Decode(CDecoder *rangeDecoder)
  81   {
  82     UInt32 modelIndex = 1;
  83     RC_INIT_VAR
  84     for(int bitIndex = NumBitLevels; bitIndex != 0; bitIndex--)
  85     {
  86       // modelIndex = (modelIndex << 1) + Models[modelIndex].Decode(rangeDecoder);
  87       RC_GETBIT(numMoveBits, Models[modelIndex].Prob, modelIndex)
  88     }
  89     RC_FLUSH_VAR
  90     return modelIndex - (1 << NumBitLevels);
  91   };
  92   UInt32 ReverseDecode(CDecoder *rangeDecoder)
  93   {
  94     UInt32 modelIndex = 1;
  95     UInt32 symbol = 0;
  96     RC_INIT_VAR
  97     for(int bitIndex = 0; bitIndex < NumBitLevels; bitIndex++)
  98     {
  99       // UInt32 bit = Models[modelIndex].Decode(rangeDecoder);
 100       // modelIndex <<= 1;
 101       // modelIndex += bit;
 102       // symbol |= (bit << bitIndex);
 103       RC_GETBIT2(numMoveBits, Models[modelIndex].Prob, modelIndex, ; , symbol |= (1 << bitIndex))
 104     }
 105     RC_FLUSH_VAR
 106     return symbol;
 107   }
 108 };
 109
 110 template <int numMoveBits>
 111 void ReverseBitTreeEncode(CBitEncoder<numMoveBits> *Models,
 112     CEncoder *rangeEncoder, int NumBitLevels, UInt32 symbol)
 113 {
 114   UInt32 modelIndex = 1;
 115   for (int i = 0; i < NumBitLevels; i++)
 116   {
 117     UInt32 bit = symbol & 1;
 118     Models[modelIndex].Encode(rangeEncoder, bit);
 119     modelIndex = (modelIndex << 1) | bit;
 120     symbol >>= 1;
 121   }
 122 }
 123
 124 template <int numMoveBits>
 125 UInt32 ReverseBitTreeGetPrice(CBitEncoder<numMoveBits> *Models,
 126     UInt32 NumBitLevels, UInt32 symbol)
 127 {
 128   UInt32 price = 0;
 129   UInt32 modelIndex = 1;
 130   for (int i = NumBitLevels; i != 0; i--)
 131   {
 132     UInt32 bit = symbol & 1;
 133     symbol >>= 1;
 134     price += Models[modelIndex].GetPrice(bit);
 135     modelIndex = (modelIndex << 1) | bit;
 136   }
 137   return price;
 138 }
 139
 140 template <int numMoveBits>
 141 UInt32 ReverseBitTreeDecode(CBitDecoder<numMoveBits> *Models,
 142     CDecoder *rangeDecoder, int NumBitLevels)
 143 {
 144   UInt32 modelIndex = 1;
 145   UInt32 symbol = 0;
 146   RC_INIT_VAR
 147   for(int bitIndex = 0; bitIndex < NumBitLevels; bitIndex++)
 148   {
 149     // UInt32 bit = Models[modelIndex].Decode(rangeDecoder);
 150     // modelIndex <<= 1;
 151     // modelIndex += bit;
 152     // symbol |= (bit << bitIndex);
 153     RC_GETBIT2(numMoveBits, Models[modelIndex].Prob, modelIndex, ; , symbol |= (1 << bitIndex))
 154   }
 155   RC_FLUSH_VAR
 156   return symbol;
 157 }
 158
 159 }}
 160
 161 #endif