release/src-rt-6.x/linux/linux-2.6/scripts/squashfs/lzma/C/7zip/Compress/LZMA/LZMAEncoder.h

   1 // LZMA/Encoder.h
   2
   3 #ifndef __LZMA_ENCODER_H
   4 #define __LZMA_ENCODER_H
   5
   6 #include "../../../Common/MyCom.h"
   7 #include "../../../Common/Alloc.h"
   8 #include "../../ICoder.h"
   9 #include "../LZ/IMatchFinder.h"
  10 #include "../RangeCoder/RangeCoderBitTree.h"
  11
  12 #include "LZMA.h"
  13
  14 namespace NCompress {
  15 namespace NLZMA {
  16
  17 typedef NRangeCoder::CBitEncoder<kNumMoveBits> CMyBitEncoder;
  18
  19 class CBaseState
  20 {
  21 protected:
  22   CState _state;
  23   Byte _previousByte;
  24   UInt32 _repDistances[kNumRepDistances];
  25   void Init()
  26   {
  27     _state.Init();
  28     _previousByte = 0;
  29     for(UInt32 i = 0 ; i < kNumRepDistances; i++)
  30       _repDistances[i] = 0;
  31   }
  32 };
  33
  34 struct COptimal
  35 {
  36   CState State;
  37
  38   bool Prev1IsChar;
  39   bool Prev2;
  40
  41   UInt32 PosPrev2;
  42   UInt32 BackPrev2;
  43
  44   UInt32 Price;
  45   UInt32 PosPrev;         // posNext;
  46   UInt32 BackPrev;
  47   UInt32 Backs[kNumRepDistances];
  48   void MakeAsChar() { BackPrev = UInt32(-1); Prev1IsChar = false; }
  49   void MakeAsShortRep() { BackPrev = 0; ; Prev1IsChar = false; }
  50   bool IsShortRep() { return (BackPrev == 0); }
  51 };
  52
  53
  54 extern Byte g_FastPos[1024];
  55 inline UInt32 GetPosSlot(UInt32 pos)
  56 {
  57   if (pos < (1 << 10))
  58     return g_FastPos[pos];
  59   if (pos < (1 << 19))
  60     return g_FastPos[pos >> 9] + 18;
  61   return g_FastPos[pos >> 18] + 36;
  62 }
  63
  64 inline UInt32 GetPosSlot2(UInt32 pos)
  65 {
  66   if (pos < (1 << 16))
  67     return g_FastPos[pos >> 6] + 12;
  68   if (pos < (1 << 25))
  69     return g_FastPos[pos >> 15] + 30;
  70   return g_FastPos[pos >> 24] + 48;
  71 }
  72
  73 const UInt32 kIfinityPrice = 0xFFFFFFF;
  74
  75 const UInt32 kNumOpts = 1 << 12;
  76
  77
  78 class CLiteralEncoder2
  79 {
  80   CMyBitEncoder _encoders[0x300];
  81 public:
  82   void Init()
  83   {
  84     for (int i = 0; i < 0x300; i++)
  85       _encoders[i].Init();
  86   }
  87   void Encode(NRangeCoder::CEncoder *rangeEncoder, Byte symbol);
  88   void EncodeMatched(NRangeCoder::CEncoder *rangeEncoder, Byte matchByte, Byte symbol);
  89   UInt32 GetPrice(bool matchMode, Byte matchByte, Byte symbol) const;
  90 };
  91
  92 class CLiteralEncoder
  93 {
  94   CLiteralEncoder2 *_coders;
  95   int _numPrevBits;
  96   int _numPosBits;
  97   UInt32 _posMask;
  98 public:
  99   CLiteralEncoder(): _coders(0) {}
 100   ~CLiteralEncoder()  { Free(); }
 101   void Free()
 102   {
 103     MyFree(_coders);
 104     _coders = 0;
 105   }
 106   bool Create(int numPosBits, int numPrevBits)
 107   {
 108     if (_coders == 0 || (numPosBits + numPrevBits) !=
 109         (_numPrevBits + _numPosBits) )
 110     {
 111       Free();
 112       UInt32 numStates = 1 << (numPosBits + numPrevBits);
 113       _coders = (CLiteralEncoder2 *)MyAlloc(numStates * sizeof(CLiteralEncoder2));
 114     }
 115     _numPosBits = numPosBits;
 116     _posMask = (1 << numPosBits) - 1;
 117     _numPrevBits = numPrevBits;
 118     return (_coders != 0);
 119   }
 120   void Init()
 121   {
 122     UInt32 numStates = 1 << (_numPrevBits + _numPosBits);
 123     for (UInt32 i = 0; i < numStates; i++)
 124       _coders[i].Init();
 125   }
 126   UInt32 GetState(UInt32 pos, Byte prevByte) const
 127     { return ((pos & _posMask) << _numPrevBits) + (prevByte >> (8 - _numPrevBits)); }
 128   CLiteralEncoder2 *GetSubCoder(UInt32 pos, Byte prevByte)
 129     { return &_coders[GetState(pos, prevByte)]; }
 130   /*
 131   void Encode(NRangeCoder::CEncoder *rangeEncoder, UInt32 pos, Byte prevByte,
 132       Byte symbol)
 133     { _coders[GetState(pos, prevByte)].Encode(rangeEncoder, symbol); }
 134   void EncodeMatched(NRangeCoder::CEncoder *rangeEncoder, UInt32 pos, Byte prevByte,
 135       Byte matchByte, Byte symbol)
 136     { _coders[GetState(pos, prevByte)].Encode(rangeEncoder,
 137       matchByte, symbol); }
 138   */
 139   UInt32 GetPrice(UInt32 pos, Byte prevByte, bool matchMode, Byte matchByte, Byte symbol) const
 140     { return _coders[GetState(pos, prevByte)].GetPrice(matchMode, matchByte, symbol); }
 141 };
 142
 143 namespace NLength {
 144
 145 class CEncoder
 146 {
 147   CMyBitEncoder _choice;
 148   CMyBitEncoder  _choice2;
 149   NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumLowBits>  _lowCoder[kNumPosStatesEncodingMax];
 150   NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumMidBits>  _midCoder[kNumPosStatesEncodingMax];
 151   NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumHighBits>  _highCoder;
 152 public:
 153   void Init(UInt32 numPosStates);
 154   void Encode(NRangeCoder::CEncoder *rangeEncoder, UInt32 symbol, UInt32 posState);
 155   UInt32 GetPrice(UInt32 symbol, UInt32 posState) const;
 156 };
 157
 158 const UInt32 kNumSpecSymbols = kNumLowSymbols + kNumMidSymbols;
 159
 160 class CPriceTableEncoder: public CEncoder
 161 {
 162   UInt32 _prices[kNumSymbolsTotal][kNumPosStatesEncodingMax];
 163   UInt32 _tableSize;
 164   UInt32 _counters[kNumPosStatesEncodingMax];
 165 public:
 166   void SetTableSize(UInt32 tableSize) { _tableSize = tableSize;  }
 167   UInt32 GetPrice(UInt32 symbol, UInt32 posState) const
 168     { return _prices[symbol][posState]; }
 169   void UpdateTable(UInt32 posState)
 170   {
 171     for (UInt32 len = 0; len < _tableSize; len++)
 172       _prices[len][posState] = CEncoder::GetPrice(len, posState);
 173     _counters[posState] = _tableSize;
 174   }
 175   void UpdateTables(UInt32 numPosStates)
 176   {
 177     for (UInt32 posState = 0; posState < numPosStates; posState++)
 178       UpdateTable(posState);
 179   }
 180   void Encode(NRangeCoder::CEncoder *rangeEncoder, UInt32 symbol, UInt32 posState)
 181   {
 182     CEncoder::Encode(rangeEncoder, symbol, posState);
 183     if (--_counters[posState] == 0)
 184       UpdateTable(posState);
 185   }
 186 };
 187
 188 }
 189
 190 class CEncoder :
 191   public ICompressCoder,
 192   public ICompressSetOutStream,
 193   public ICompressSetCoderProperties,
 194   public ICompressWriteCoderProperties,
 195   public CBaseState,
 196   public CMyUnknownImp
 197 {
 198   COptimal _optimum[kNumOpts];
 199   CMyComPtr<IMatchFinder> _matchFinder; // test it
 200   NRangeCoder::CEncoder _rangeEncoder;
 201
 202   CMyBitEncoder _isMatch[kNumStates][NLength::kNumPosStatesEncodingMax];
 203   CMyBitEncoder _isRep[kNumStates];
 204   CMyBitEncoder _isRepG0[kNumStates];
 205   CMyBitEncoder _isRepG1[kNumStates];
 206   CMyBitEncoder _isRepG2[kNumStates];
 207   CMyBitEncoder _isRep0Long[kNumStates][NLength::kNumPosStatesEncodingMax];
 208
 209   NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumPosSlotBits> _posSlotEncoder[kNumLenToPosStates];
 210
 211   CMyBitEncoder _posEncoders[kNumFullDistances - kEndPosModelIndex];
 212   NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumAlignBits> _posAlignEncoder;
 213
 214   NLength::CPriceTableEncoder _lenEncoder;
 215   NLength::CPriceTableEncoder _repMatchLenEncoder;
 216
 217   CLiteralEncoder _literalEncoder;
 218
 219   UInt32 _matchDistances[kMatchMaxLen + 1];
 220
 221   bool _fastMode;
 222   bool _maxMode;
 223   UInt32 _numFastBytes;
 224   UInt32 _longestMatchLength;
 225
 226   UInt32 _additionalOffset;
 227
 228   UInt32 _optimumEndIndex;
 229   UInt32 _optimumCurrentIndex;
 230
 231   bool _longestMatchWasFound;
 232
 233   UInt32 _posSlotPrices[kNumLenToPosStates][kDistTableSizeMax];
 234
 235   UInt32 _distancesPrices[kNumLenToPosStates][kNumFullDistances];
 236
 237   UInt32 _alignPrices[kAlignTableSize];
 238   UInt32 _alignPriceCount;
 239
 240   UInt32 _distTableSize;
 241
 242   UInt32 _posStateBits;
 243   UInt32 _posStateMask;
 244   UInt32 _numLiteralPosStateBits;
 245   UInt32 _numLiteralContextBits;
 246
 247   UInt32 _dictionarySize;
 248
 249   UInt32 _dictionarySizePrev;
 250   UInt32 _numFastBytesPrev;
 251
 252   UInt64 lastPosSlotFillingPos;
 253   UInt64 nowPos64;
 254   bool _finished;
 255   ISequentialInStream *_inStream;
 256
 257   int _matchFinderIndex;
 258   #ifdef COMPRESS_MF_MT
 259   bool _multiThread;
 260   #endif
 261
 262   bool _writeEndMark;
 263
 264   bool _needReleaseMFStream;
 265
 266   HRESULT ReadMatchDistances(UInt32 &len);
 267
 268   HRESULT MovePos(UInt32 num);
 269   UInt32 GetRepLen1Price(CState state, UInt32 posState) const
 270   {
 271     return _isRepG0[state.Index].GetPrice0() +
 272         _isRep0Long[state.Index][posState].GetPrice0();
 273   }
 274   UInt32 GetRepPrice(UInt32 repIndex, UInt32 len, CState state, UInt32 posState) const
 275   {
 276     UInt32 price = _repMatchLenEncoder.GetPrice(len - kMatchMinLen, posState);
 277     if(repIndex == 0)
 278     {
 279       price += _isRepG0[state.Index].GetPrice0();
 280       price += _isRep0Long[state.Index][posState].GetPrice1();
 281     }
 282     else
 283     {
 284       price += _isRepG0[state.Index].GetPrice1();
 285       if (repIndex == 1)
 286         price += _isRepG1[state.Index].GetPrice0();
 287       else
 288       {
 289         price += _isRepG1[state.Index].GetPrice1();
 290         price += _isRepG2[state.Index].GetPrice(repIndex - 2);
 291       }
 292     }
 293     return price;
 294   }
 295   /*
 296   UInt32 GetPosLen2Price(UInt32 pos, UInt32 posState) const
 297   {
 298     if (pos >= kNumFullDistances)
 299       return kIfinityPrice;
 300     return _distancesPrices[0][pos] + _lenEncoder.GetPrice(0, posState);
 301   }
 302   UInt32 GetPosLen3Price(UInt32 pos, UInt32 len, UInt32 posState) const
 303   {
 304     UInt32 price;
 305     UInt32 lenToPosState = GetLenToPosState(len);
 306     if (pos < kNumFullDistances)
 307       price = _distancesPrices[lenToPosState][pos];
 308     else
 309       price = _posSlotPrices[lenToPosState][GetPosSlot2(pos)] +
 310           _alignPrices[pos & kAlignMask];
 311     return price + _lenEncoder.GetPrice(len - kMatchMinLen, posState);
 312   }
 313   */
 314   UInt32 GetPosLenPrice(UInt32 pos, UInt32 len, UInt32 posState) const
 315   {
 316     if (len == 2 && pos >= 0x80)
 317       return kIfinityPrice;
 318     UInt32 price;
 319     UInt32 lenToPosState = GetLenToPosState(len);
 320     if (pos < kNumFullDistances)
 321       price = _distancesPrices[lenToPosState][pos];
 322     else
 323       price = _posSlotPrices[lenToPosState][GetPosSlot2(pos)] +
 324           _alignPrices[pos & kAlignMask];
 325     return price + _lenEncoder.GetPrice(len - kMatchMinLen, posState);
 326   }
 327
 328   UInt32 Backward(UInt32 &backRes, UInt32 cur);
 329   HRESULT GetOptimum(UInt32 position, UInt32 &backRes, UInt32 &lenRes);
 330   HRESULT GetOptimumFast(UInt32 position, UInt32 &backRes, UInt32 &lenRes);
 331
 332   void FillPosSlotPrices();
 333   void FillDistancesPrices();
 334   void FillAlignPrices();
 335
 336   void ReleaseMFStream()
 337   {
 338     if (_matchFinder && _needReleaseMFStream)
 339     {
 340       _matchFinder->ReleaseStream();
 341       _needReleaseMFStream = false;
 342     }
 343   }
 344
 345   void ReleaseStreams()
 346   {
 347     ReleaseMFStream();
 348     ReleaseOutStream();
 349   }
 350
 351   HRESULT Flush(UInt32 nowPos);
 352   class CCoderReleaser
 353   {
 354     CEncoder *_coder;
 355   public:
 356     CCoderReleaser(CEncoder *coder): _coder(coder) {}
 357     ~CCoderReleaser()
 358     {
 359       _coder->ReleaseStreams();
 360     }
 361   };
 362   friend class CCoderReleaser;
 363
 364   void WriteEndMarker(UInt32 posState);
 365
 366 public:
 367   CEncoder();
 368   void SetWriteEndMarkerMode(bool writeEndMarker)
 369     { _writeEndMark= writeEndMarker; }
 370
 371   HRESULT Create();
 372
 373   MY_UNKNOWN_IMP3(
 374       ICompressSetOutStream,
 375       ICompressSetCoderProperties,
 376       ICompressWriteCoderProperties
 377       )
 378
 379   HRESULT Init();
 380
 381   // ICompressCoder interface
 382   HRESULT SetStreams(ISequentialInStream *inStream,
 383       ISequentialOutStream *outStream,
 384       const UInt64 *inSize, const UInt64 *outSize);
 385   HRESULT CodeOneBlock(UInt64 *inSize, UInt64 *outSize, Int32 *finished);
 386
 387   HRESULT CodeReal(ISequentialInStream *inStream,
 388       ISequentialOutStream *outStream,
 389       const UInt64 *inSize, const UInt64 *outSize,
 390       ICompressProgressInfo *progress);
 391
 392   // ICompressCoder interface
 393   STDMETHOD(Code)(ISequentialInStream *inStream,
 394       ISequentialOutStream *outStream,
 395       const UInt64 *inSize, const UInt64 *outSize,
 396       ICompressProgressInfo *progress);
 397
 398   // IInitMatchFinder interface
 399   STDMETHOD(InitMatchFinder)(IMatchFinder *matchFinder);
 400
 401   // ICompressSetCoderProperties2
 402   STDMETHOD(SetCoderProperties)(const PROPID *propIDs,
 403       const PROPVARIANT *properties, UInt32 numProperties);
 404
 405   // ICompressWriteCoderProperties
 406   STDMETHOD(WriteCoderProperties)(ISequentialOutStream *outStream);
 407
 408   STDMETHOD(SetOutStream)(ISequentialOutStream *outStream);
 409   STDMETHOD(ReleaseOutStream)();
 410
 411   virtual ~CEncoder() {}
 412 };
 413
 414 }}
 415
 416 #endif