CPP/7zip/Compress/QuantumDecoder.h

   1 // QuantumDecoder.h\r
   2 \r
   3 #ifndef __COMPRESS_QUANTUM_DECODER_H\r
   4 #define __COMPRESS_QUANTUM_DECODER_H\r
   5 \r
   6 #include "../../Common/MyCom.h"\r
   7 \r
   8 #include "../ICoder.h"\r
   9 \r
  10 #include "../Common/InBuffer.h"\r
  11 \r
  12 #include "LzOutWindow.h"\r
  13 \r
  14 namespace NCompress {\r
  15 namespace NQuantum {\r
  16 \r
  17 class CStreamBitDecoder\r
  18 {\r
  19   UInt32 Value;\r
  20   CInBuffer Stream;\r
  21 public:\r
  22   bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); }\r
  23   void SetStream(ISequentialInStream *stream) { Stream.SetStream(stream); }\r
  24   void ReleaseStream() { Stream.ReleaseStream(); }\r
  25 \r
  26   void Finish() { Value = 0x10000; }\r
  27 \r
  28   void Init()\r
  29   {\r
  30     Stream.Init();\r
  31     Value = 0x10000;\r
  32   }\r
  33 \r
  34   UInt64 GetProcessedSize() const { return Stream.GetProcessedSize(); }\r
  35   bool WasFinished() const { return Stream.WasFinished(); }\r
  36   \r
  37   UInt32 ReadBit()\r
  38   {\r
  39     if (Value >= 0x10000)\r
  40       Value = 0x100 | Stream.ReadByte();\r
  41     UInt32 res = (Value >> 7) & 1;\r
  42     Value <<= 1;\r
  43     return res;\r
  44   }\r
  45 \r
  46   UInt32 ReadBits(int numBits) // numBits > 0\r
  47   {\r
  48     UInt32 res = 0;\r
  49     do\r
  50       res = (res << 1) | ReadBit();\r
  51     while (--numBits != 0);\r
  52     return res;\r
  53   }\r
  54 };\r
  55 \r
  56 const unsigned kNumLitSelectorBits = 2;\r
  57 const unsigned kNumLitSelectors = (1 << kNumLitSelectorBits);\r
  58 const unsigned kNumLitSymbols = 1 << (8 - kNumLitSelectorBits);\r
  59 const unsigned kNumMatchSelectors = 3;\r
  60 const unsigned kNumSelectors = kNumLitSelectors + kNumMatchSelectors;\r
  61 const unsigned kNumSymbolsMax = kNumLitSymbols; // 64\r
  62 \r
  63 namespace NRangeCoder {\r
  64 \r
  65 class CDecoder\r
  66 {\r
  67   UInt32 Low;\r
  68   UInt32 Range;\r
  69   UInt32 Code;\r
  70 public:\r
  71   CStreamBitDecoder Stream;\r
  72   bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); }\r
  73   void SetStream(ISequentialInStream *stream) { Stream.SetStream(stream); }\r
  74   void ReleaseStream() { Stream.ReleaseStream(); }\r
  75 \r
  76   void Init()\r
  77   {\r
  78     Stream.Init();\r
  79     Low = 0;\r
  80     Range = 0x10000;\r
  81     Code = Stream.ReadBits(16);\r
  82   }\r
  83 \r
  84   void Finish()\r
  85   {\r
  86     // we need these extra two Bit_reads\r
  87     Stream.ReadBit();\r
  88     Stream.ReadBit();\r
  89     Stream.Finish();\r
  90   }\r
  91 \r
  92   UInt64 GetProcessedSize() const { return Stream.GetProcessedSize(); }\r
  93 \r
  94   UInt32 GetThreshold(UInt32 total) const\r
  95   {\r
  96     return ((Code + 1) * total - 1) / Range; // & 0xFFFF is not required;\r
  97   }\r
  98 \r
  99   void Decode(UInt32 start, UInt32 end, UInt32 total)\r
 100   {\r
 101     UInt32 high = Low + end * Range / total - 1;\r
 102     UInt32 offset = start * Range / total;\r
 103     Code -= offset;\r
 104     Low += offset;\r
 105     for (;;)\r
 106     {\r
 107       if ((Low & 0x8000) != (high & 0x8000))\r
 108       {\r
 109         if ((Low & 0x4000) == 0 || (high & 0x4000) != 0)\r
 110           break;\r
 111         Low &= 0x3FFF;\r
 112         high |= 0x4000;\r
 113       }\r
 114       Low = (Low << 1) & 0xFFFF;\r
 115       high = ((high << 1) | 1) & 0xFFFF;\r
 116       Code = ((Code << 1) | Stream.ReadBit());\r
 117     }\r
 118     Range = high - Low + 1;\r
 119   }\r
 120 };\r
 121 \r
 122 const UInt16 kUpdateStep = 8;\r
 123 const UInt16 kFreqSumMax = 3800;\r
 124 const UInt16 kReorderCountStart = 4;\r
 125 const UInt16 kReorderCount = 50;\r
 126 \r
 127 class CModelDecoder\r
 128 {\r
 129   unsigned NumItems;\r
 130   unsigned ReorderCount;\r
 131   UInt16 Freqs[kNumSymbolsMax + 1];\r
 132   Byte Values[kNumSymbolsMax];\r
 133 public:\r
 134   void Init(unsigned numItems)\r
 135   {\r
 136     NumItems = numItems;\r
 137     ReorderCount = kReorderCountStart;\r
 138     for (unsigned i = 0; i < numItems; i++)\r
 139     {\r
 140       Freqs[i] = (UInt16)(numItems - i);\r
 141       Values[i] = (Byte)i;\r
 142     }\r
 143     Freqs[numItems] = 0;\r
 144   }\r
 145   \r
 146   unsigned Decode(CDecoder *rangeDecoder)\r
 147   {\r
 148     UInt32 threshold = rangeDecoder->GetThreshold(Freqs[0]);\r
 149     unsigned i;\r
 150     for (i = 1; Freqs[i] > threshold; i++);\r
 151     rangeDecoder->Decode(Freqs[i], Freqs[i - 1], Freqs[0]);\r
 152     unsigned res = Values[--i];\r
 153     do\r
 154       Freqs[i] += kUpdateStep;\r
 155     while (i-- != 0);\r
 156 \r
 157     if (Freqs[0] > kFreqSumMax)\r
 158     {\r
 159       if (--ReorderCount == 0)\r
 160       {\r
 161         ReorderCount = kReorderCount;\r
 162         for (i = 0; i < NumItems; i++)\r
 163           Freqs[i] = (UInt16)(((Freqs[i] - Freqs[i + 1]) + 1) >> 1);\r
 164         for (i = 0; i < NumItems - 1; i++)\r
 165           for (unsigned j = i + 1; j < NumItems; j++)\r
 166             if (Freqs[i] < Freqs[j])\r
 167             {\r
 168               UInt16 tmpFreq = Freqs[i];\r
 169               Byte tmpVal = Values[i];\r
 170               Freqs[i] = Freqs[j];\r
 171               Values[i] = Values[j];\r
 172               Freqs[j] = tmpFreq;\r
 173               Values[j] = tmpVal;\r
 174             }\r
 175         do\r
 176           Freqs[i] = (UInt16)(Freqs[i] + Freqs[i + 1]);\r
 177         while (i-- != 0);\r
 178       }\r
 179       else\r
 180       {\r
 181         i = NumItems - 1;\r
 182         do\r
 183         {\r
 184           Freqs[i] >>= 1;\r
 185           if (Freqs[i] <= Freqs[i + 1])\r
 186             Freqs[i] = (UInt16)(Freqs[i + 1] + 1);\r
 187         }\r
 188         while (i-- != 0);\r
 189       }\r
 190     }\r
 191     return res;\r
 192   }\r
 193 };\r
 194 \r
 195 }\r
 196 \r
 197 class CDecoder:\r
 198   public ICompressCoder,\r
 199   public ICompressSetInStream,\r
 200   public ICompressSetOutStreamSize,\r
 201   public CMyUnknownImp\r
 202 {\r
 203   CLzOutWindow _outWindowStream;\r
 204   NRangeCoder::CDecoder _rangeDecoder;\r
 205 \r
 206   UInt64 _outSize;\r
 207   int _remainLen; // -1 means end of stream. // -2 means need Init\r
 208   UInt32 _rep0;\r
 209 \r
 210   int _numDictBits;\r
 211   bool _keepHistory;\r
 212 \r
 213   NRangeCoder::CModelDecoder m_Selector;\r
 214   NRangeCoder::CModelDecoder m_Literals[kNumLitSelectors];\r
 215   NRangeCoder::CModelDecoder m_PosSlot[kNumMatchSelectors];\r
 216   NRangeCoder::CModelDecoder m_LenSlot;\r
 217   void Init();\r
 218   HRESULT CodeSpec(UInt32 size);\r
 219 public:\r
 220   MY_UNKNOWN_IMP2(\r
 221       ICompressSetInStream,\r
 222       ICompressSetOutStreamSize)\r
 223 \r
 224   void ReleaseStreams()\r
 225   {\r
 226     _outWindowStream.ReleaseStream();\r
 227     ReleaseInStream();\r
 228   }\r
 229 \r
 230   class CDecoderFlusher\r
 231   {\r
 232     CDecoder *_decoder;\r
 233   public:\r
 234     bool NeedFlush;\r
 235     CDecoderFlusher(CDecoder *decoder): _decoder(decoder), NeedFlush(true) {}\r
 236     ~CDecoderFlusher()\r
 237     {\r
 238       if (NeedFlush)\r
 239         _decoder->Flush();\r
 240       _decoder->ReleaseStreams();\r
 241     }\r
 242   };\r
 243 \r
 244   HRESULT Flush() {  return _outWindowStream.Flush(); }\r
 245 \r
 246   HRESULT CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream,\r
 247       const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress);\r
 248   \r
 249   STDMETHOD(Code)(ISequentialInStream *inStream, ISequentialOutStream *outStream,\r
 250       const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress);\r
 251 \r
 252   STDMETHOD(SetInStream)(ISequentialInStream *inStream);\r
 253   STDMETHOD(ReleaseInStream)();\r
 254   STDMETHOD(SetOutStreamSize)(const UInt64 *outSize);\r
 255 \r
 256   void SetParams(int numDictBits) { _numDictBits = numDictBits; }\r
 257   void SetKeepHistory(bool keepHistory) { _keepHistory = keepHistory; }\r
 258   CDecoder(): _keepHistory(false) {}\r
 259   virtual ~CDecoder() {}\r
 260 };\r
 261 \r
 262 }}\r
 263 \r
 264 #endif\r