payloads/bayou/util/pbuilder/lzma/C/7zip/Compress/RangeCoder/RangeCoder.h

   1 // Compress/RangeCoder/RangeCoder.h
   2
   3 #ifndef __COMPRESS_RANGECODER_H
   4 #define __COMPRESS_RANGECODER_H
   5
   6 #include "../../Common/InBuffer.h"
   7 #include "../../Common/OutBuffer.h"
   8
   9 namespace NCompress {
  10 namespace NRangeCoder {
  11
  12 const int kNumTopBits = 24;
  13 const UInt32 kTopValue = (1 << kNumTopBits);
  14
  15 class CEncoder
  16 {
  17   UInt32 _cacheSize;
  18   Byte _cache;
  19 public:
  20   UInt64 Low;
  21   UInt32 Range;
  22   COutBuffer Stream;
  23   bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); }
  24
  25   void SetStream(ISequentialOutStream *stream) { Stream.SetStream(stream); }
  26   void Init()
  27   {
  28     Stream.Init();
  29     Low = 0;
  30     Range = 0xFFFFFFFF;
  31     _cacheSize = 1;
  32     _cache = 0;
  33   }
  34
  35   void FlushData()
  36   {
  37     // Low += 1;
  38     for(int i = 0; i < 5; i++)
  39       ShiftLow();
  40   }
  41
  42   HRESULT FlushStream() { return Stream.Flush();  }
  43
  44   void ReleaseStream() { Stream.ReleaseStream(); }
  45
  46   void Encode(UInt32 start, UInt32 size, UInt32 total)
  47   {
  48     Low += start * (Range /= total);
  49     Range *= size;
  50     while (Range < kTopValue)
  51     {
  52       Range <<= 8;
  53       ShiftLow();
  54     }
  55   }
  56
  57   void ShiftLow()
  58   {
  59     if ((UInt32)Low < (UInt32)0xFF000000 || (int)(Low >> 32) != 0)
  60     {
  61       Byte temp = _cache;
  62       do
  63       {
  64         Stream.WriteByte((Byte)(temp + (Byte)(Low >> 32)));
  65         temp = 0xFF;
  66       }
  67       while(--_cacheSize != 0);
  68       _cache = (Byte)((UInt32)Low >> 24);
  69     }
  70     _cacheSize++;
  71     Low = (UInt32)Low << 8;
  72   }
  73
  74   void EncodeDirectBits(UInt32 value, int numTotalBits)
  75   {
  76     for (int i = numTotalBits - 1; i >= 0; i--)
  77     {
  78       Range >>= 1;
  79       if (((value >> i) & 1) == 1)
  80         Low += Range;
  81       if (Range < kTopValue)
  82       {
  83         Range <<= 8;
  84         ShiftLow();
  85       }
  86     }
  87   }
  88
  89   void EncodeBit(UInt32 size0, UInt32 numTotalBits, UInt32 symbol)
  90   {
  91     UInt32 newBound = (Range >> numTotalBits) * size0;
  92     if (symbol == 0)
  93       Range = newBound;
  94     else
  95     {
  96       Low += newBound;
  97       Range -= newBound;
  98     }
  99     while (Range < kTopValue)
 100     {
 101       Range <<= 8;
 102       ShiftLow();
 103     }
 104   }
 105
 106   UInt64 GetProcessedSize() {  return Stream.GetProcessedSize() + _cacheSize + 4; }
 107 };
 108
 109 class CDecoder
 110 {
 111 public:
 112   CInBuffer Stream;
 113   UInt32 Range;
 114   UInt32 Code;
 115   bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); }
 116
 117   void Normalize()
 118   {
 119     while (Range < kTopValue)
 120     {
 121       Code = (Code << 8) | Stream.ReadByte();
 122       Range <<= 8;
 123     }
 124   }
 125
 126   void SetStream(ISequentialInStream *stream) { Stream.SetStream(stream); }
 127   void Init()
 128   {
 129     Stream.Init();
 130     Code = 0;
 131     Range = 0xFFFFFFFF;
 132     for(int i = 0; i < 5; i++)
 133       Code = (Code << 8) | Stream.ReadByte();
 134   }
 135
 136   void ReleaseStream() { Stream.ReleaseStream(); }
 137
 138   UInt32 GetThreshold(UInt32 total)
 139   {
 140     return (Code) / ( Range /= total);
 141   }
 142
 143   void Decode(UInt32 start, UInt32 size)
 144   {
 145     Code -= start * Range;
 146     Range *= size;
 147     Normalize();
 148   }
 149
 150   UInt32 DecodeDirectBits(int numTotalBits)
 151   {
 152     UInt32 range = Range;
 153     UInt32 code = Code;
 154     UInt32 result = 0;
 155     for (int i = numTotalBits; i != 0; i--)
 156     {
 157       range >>= 1;
 158       /*
 159       result <<= 1;
 160       if (code >= range)
 161       {
 162         code -= range;
 163         result |= 1;
 164       }
 165       */
 166       UInt32 t = (code - range) >> 31;
 167       code -= range & (t - 1);
 168       result = (result << 1) | (1 - t);
 169
 170       if (range < kTopValue)
 171       {
 172         code = (code << 8) | Stream.ReadByte();
 173         range <<= 8;
 174       }
 175     }
 176     Range = range;
 177     Code = code;
 178     return result;
 179   }
 180
 181   UInt32 DecodeBit(UInt32 size0, UInt32 numTotalBits)
 182   {
 183     UInt32 newBound = (Range >> numTotalBits) * size0;
 184     UInt32 symbol;
 185     if (Code < newBound)
 186     {
 187       symbol = 0;
 188       Range = newBound;
 189     }
 190     else
 191     {
 192       symbol = 1;
 193       Code -= newBound;
 194       Range -= newBound;
 195     }
 196     Normalize();
 197     return symbol;
 198   }
 199
 200   UInt64 GetProcessedSize() {return Stream.GetProcessedSize(); }
 201 };
 202
 203 }}
 204
 205 #endif