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

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