1 // LZMA/Encoder.h

     2 

     3 #ifndef __LZMA_ENCODER_H

     4 #define __LZMA_ENCODER_H

     5 

     6 #include "../../../Common/MyCom.h"

     7 #include "../../ICoder.h"

     8 

     9 extern "C"

    10 {

    11   #include "../../../../C/Alloc.h"

    12   #include "../../../../C/Compress/Lz/MatchFinder.h"

    13   #ifdef COMPRESS_MF_MT

    14   #include "../../../../C/Compress/Lz/MatchFinderMt.h"

    15   #endif

    16 }

    17 

    18 #include "../RangeCoder/RangeCoderBitTree.h"

    19 

    20 #include "LZMA.h"

    21 

    22 namespace NCompress {

    23 namespace NLZMA {

    24 

    25 typedef NRangeCoder::CBitEncoder<kNumMoveBits> CMyBitEncoder;

    26 

    27 class CBaseState

    28 {

    29 protected:

    30   CState _state;

    31   Byte _previousByte;

    32   UInt32 _repDistances[kNumRepDistances];

    33   void Init()

    34   {

    35     _state.Init();

    36     _previousByte = 0;

    37     for(UInt32 i = 0 ; i < kNumRepDistances; i++)

    38       _repDistances[i] = 0;

    39   }

    40 };

    41 

    42 struct COptimal

    43 {

    44   CState State;

    45 

    46   bool Prev1IsChar;

    47   bool Prev2;

    48 

    49   UInt32 PosPrev2;

    50   UInt32 BackPrev2;     

    51 

    52   UInt32 Price;    

    53   UInt32 PosPrev;         // posNext;

    54   UInt32 BackPrev;     

    55   UInt32 Backs[kNumRepDistances];

    56   void MakeAsChar() { BackPrev = UInt32(-1); Prev1IsChar = false; }

    57   void MakeAsShortRep() { BackPrev = 0; ; Prev1IsChar = false; }

    58   bool IsShortRep() { return (BackPrev == 0); }

    59 };

    60 

    61 

    62 // #define LZMA_LOG_BRANCH

    63 

    64 #if _MSC_VER >= 1400

    65 // Must give gain in core 2. but slower ~2% on k8.

    66 // #define LZMA_LOG_BSR

    67 #endif

    68 

    69 #ifndef LZMA_LOG_BSR

    70 static const int kNumLogBits = 13; // don't change it !

    71 extern Byte g_FastPos[];

    72 #endif

    73 inline UInt32 GetPosSlot(UInt32 pos)

    74 {

    75   #ifdef LZMA_LOG_BSR

    76   if (pos < 2)

    77     return pos;

    78   unsigned long index;

    79   _BitScanReverse(&index, pos);

    80   return (index + index) + ((pos >> (index - 1)) & 1);

    81   #else

    82   if (pos < (1 << kNumLogBits))

    83     return g_FastPos[pos];

    84   if (pos < (1 << (kNumLogBits * 2 - 1)))

    85     return g_FastPos[pos >> (kNumLogBits - 1)] + (kNumLogBits - 1) * 2;

    86   return g_FastPos[pos >> (kNumLogBits - 1) * 2] + (kNumLogBits - 1) * 4;

    87   #endif

    88 }

    89 

    90 inline UInt32 GetPosSlot2(UInt32 pos)

    91 {

    92   #ifdef LZMA_LOG_BSR

    93   unsigned long index;

    94   _BitScanReverse(&index, pos);

    95   return (index + index) + ((pos >> (index - 1)) & 1);

    96   #else

    97   #ifdef LZMA_LOG_BRANCH

    98   if (pos < (1 << (kNumLogBits + 6)))

    99     return g_FastPos[pos >> 6] + 12;

   100   if (pos < (1 << (kNumLogBits * 2 + 5)))

   101     return g_FastPos[pos >> (kNumLogBits + 5)] + (kNumLogBits + 5) * 2;

   102   return g_FastPos[pos >> (kNumLogBits * 2 + 4)] + (kNumLogBits * 2 + 4) * 2;

   103   #else

   104   // it's faster with VC6-32bit.

   105   UInt32 s = 6 + ((kNumLogBits - 1) & (UInt32)((Int32)(((1 << (kNumLogBits + 6)) - 1) -  pos) >> 31));

   106   return g_FastPos[pos >> s] + (s * 2);

   107   #endif

   108   #endif

   109 }

   110 

   111 const UInt32 kIfinityPrice = 0xFFFFFFF;

   112 

   113 const UInt32 kNumOpts = 1 << 12;

   114 

   115 

   116 class CLiteralEncoder2

   117 {

   118   CMyBitEncoder _encoders[0x300];

   119 public:

   120   void Init()

   121   {

   122     for (int i = 0; i < 0x300; i++)

   123       _encoders[i].Init();

   124   }

   125   void Encode(NRangeCoder::CEncoder *rangeEncoder, Byte symbol);

   126   void EncodeMatched(NRangeCoder::CEncoder *rangeEncoder, Byte matchByte, Byte symbol);

   127   UInt32 GetPrice(bool matchMode, Byte matchByte, Byte symbol) const;

   128 };

   129 

   130 class CLiteralEncoder

   131 {

   132   CLiteralEncoder2 *_coders;

   133   int _numPrevBits;

   134   int _numPosBits;

   135   UInt32 _posMask;

   136 public:

   137   CLiteralEncoder(): _coders(0) {}

   138   ~CLiteralEncoder()  { Free(); }

   139   void Free()

   140   { 

   141     MyFree(_coders);

   142     _coders = 0;

   143   }

   144   bool Create(int numPosBits, int numPrevBits)

   145   {

   146     if (_coders == 0 || (numPosBits + numPrevBits) != (_numPrevBits + _numPosBits))

   147     {

   148       Free();

   149       UInt32 numStates = 1 << (numPosBits + numPrevBits);

   150       _coders = (CLiteralEncoder2 *)MyAlloc(numStates * sizeof(CLiteralEncoder2));

   151     }

   152     _numPosBits = numPosBits;

   153     _posMask = (1 << numPosBits) - 1;

   154     _numPrevBits = numPrevBits;

   155     return (_coders != 0);

   156   }

   157   void Init()

   158   {

   159     UInt32 numStates = 1 << (_numPrevBits + _numPosBits);

   160     for (UInt32 i = 0; i < numStates; i++)

   161       _coders[i].Init();

   162   }

   163   CLiteralEncoder2 *GetSubCoder(UInt32 pos, Byte prevByte)

   164     { return &_coders[((pos & _posMask) << _numPrevBits) + (prevByte >> (8 - _numPrevBits))]; }

   165 };

   166 

   167 namespace NLength {

   168 

   169 class CEncoder

   170 {

   171   CMyBitEncoder _choice;

   172   CMyBitEncoder _choice2;

   173   NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumLowBits> _lowCoder[kNumPosStatesEncodingMax];

   174   NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumMidBits> _midCoder[kNumPosStatesEncodingMax];

   175   NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumHighBits> _highCoder;

   176 public:

   177   void Init(UInt32 numPosStates);

   178   void Encode(NRangeCoder::CEncoder *rangeEncoder, UInt32 symbol, UInt32 posState);

   179   void SetPrices(UInt32 posState, UInt32 numSymbols, UInt32 *prices) const;

   180 };

   181 

   182 const UInt32 kNumSpecSymbols = kNumLowSymbols + kNumMidSymbols;

   183 

   184 class CPriceTableEncoder: public CEncoder

   185 {

   186   UInt32 _prices[kNumPosStatesEncodingMax][kNumSymbolsTotal];

   187   UInt32 _tableSize;

   188   UInt32 _counters[kNumPosStatesEncodingMax];

   189 public:

   190   void SetTableSize(UInt32 tableSize) { _tableSize = tableSize;  }

   191   UInt32 GetPrice(UInt32 symbol, UInt32 posState) const { return _prices[posState][symbol]; }

   192   void UpdateTable(UInt32 posState)

   193   {

   194     SetPrices(posState, _tableSize, _prices[posState]);

   195     _counters[posState] = _tableSize;

   196   }

   197   void UpdateTables(UInt32 numPosStates)

   198   {

   199     for (UInt32 posState = 0; posState < numPosStates; posState++)

   200       UpdateTable(posState);

   201   }

   202   void Encode(NRangeCoder::CEncoder *rangeEncoder, UInt32 symbol, UInt32 posState, bool updatePrice)

   203   {

   204     CEncoder::Encode(rangeEncoder, symbol, posState);

   205     if (updatePrice)

   206       if (--_counters[posState] == 0)

   207         UpdateTable(posState);

   208   }

   209 };

   210 

   211 }

   212 

   213 typedef struct _CSeqInStream

   214 {

   215   ISeqInStream SeqInStream;

   216   CMyComPtr<ISequentialInStream> RealStream;

   217 } CSeqInStream;

   218 

   219 

   220 class CEncoder : 

   221   public ICompressCoder,

   222   public ICompressSetOutStream,

   223   public ICompressSetCoderProperties,

   224   public ICompressWriteCoderProperties,

   225   public CBaseState,

   226   public CMyUnknownImp

   227 {

   228   NRangeCoder::CEncoder _rangeEncoder;

   229 

   230   IMatchFinder _matchFinder;

   231   void *_matchFinderObj;

   232   

   233   #ifdef COMPRESS_MF_MT

   234   Bool _multiThread;

   235   Bool _mtMode;

   236   CMatchFinderMt _matchFinderMt;

   237   #endif

   238 

   239   CMatchFinder _matchFinderBase;

   240   #ifdef COMPRESS_MF_MT

   241   Byte _pad1[kMtCacheLineDummy];

   242   #endif

   243 

   244   COptimal _optimum[kNumOpts];

   245 

   246   CMyBitEncoder _isMatch[kNumStates][NLength::kNumPosStatesEncodingMax];

   247   CMyBitEncoder _isRep[kNumStates];

   248   CMyBitEncoder _isRepG0[kNumStates];

   249   CMyBitEncoder _isRepG1[kNumStates];

   250   CMyBitEncoder _isRepG2[kNumStates];

   251   CMyBitEncoder _isRep0Long[kNumStates][NLength::kNumPosStatesEncodingMax];

   252 

   253   NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumPosSlotBits> _posSlotEncoder[kNumLenToPosStates];

   254 

   255   CMyBitEncoder _posEncoders[kNumFullDistances - kEndPosModelIndex];

   256   NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumAlignBits> _posAlignEncoder;

   257   

   258   NLength::CPriceTableEncoder _lenEncoder;

   259   NLength::CPriceTableEncoder _repMatchLenEncoder;

   260 

   261   CLiteralEncoder _literalEncoder;

   262 

   263   UInt32 _matchDistances[kMatchMaxLen * 2 + 2 + 1];

   264 

   265   bool _fastMode;

   266   // bool _maxMode;

   267   UInt32 _numFastBytes;

   268   UInt32 _longestMatchLength;    

   269   UInt32 _numDistancePairs;

   270 

   271   UInt32 _additionalOffset;

   272 

   273   UInt32 _optimumEndIndex;

   274   UInt32 _optimumCurrentIndex;

   275 

   276   bool _longestMatchWasFound;

   277 

   278   UInt32 _posSlotPrices[kNumLenToPosStates][kDistTableSizeMax];

   279   

   280   UInt32 _distancesPrices[kNumLenToPosStates][kNumFullDistances];

   281 

   282   UInt32 _alignPrices[kAlignTableSize];

   283   UInt32 _alignPriceCount;

   284 

   285   UInt32 _distTableSize;

   286 

   287   UInt32 _posStateBits;

   288   UInt32 _posStateMask;

   289   UInt32 _numLiteralPosStateBits;

   290   UInt32 _numLiteralContextBits;

   291 

   292   UInt32 _dictionarySize;

   293 

   294   UInt32 _matchPriceCount;

   295   UInt64 nowPos64;

   296   bool _finished;

   297   ISequentialInStream *_inStream;

   298 

   299   CSeqInStream _seqInStream;

   300 

   301   UInt32 _matchFinderCycles;

   302   // int _numSkip

   303 

   304   bool _writeEndMark;

   305 

   306   bool _needReleaseMFStream;

   307 

   308   void ReleaseMatchFinder()

   309   {

   310     _matchFinder.Init = 0;

   311     _seqInStream.RealStream.Release();

   312   }

   313 

   314   void ReleaseMFStream()

   315   {

   316     if (_matchFinderObj && _needReleaseMFStream)

   317     {

   318       #ifdef COMPRESS_MF_MT

   319       if (_mtMode)

   320         MatchFinderMt_ReleaseStream(&_matchFinderMt);

   321       #endif

   322       _needReleaseMFStream = false;

   323     }

   324     _seqInStream.RealStream.Release();

   325   }

   326   

   327   UInt32 ReadMatchDistances(UInt32 &numDistancePairs);

   328 

   329   void MovePos(UInt32 num);

   330   UInt32 GetRepLen1Price(CState state, UInt32 posState) const

   331   {

   332     return _isRepG0[state.Index].GetPrice0() +

   333         _isRep0Long[state.Index][posState].GetPrice0();

   334   }

   335   

   336   UInt32 GetPureRepPrice(UInt32 repIndex, CState state, UInt32 posState) const

   337   {

   338     UInt32 price;

   339     if(repIndex == 0)

   340     {

   341       price = _isRepG0[state.Index].GetPrice0();

   342       price += _isRep0Long[state.Index][posState].GetPrice1();

   343     }

   344     else

   345     {

   346       price = _isRepG0[state.Index].GetPrice1();

   347       if (repIndex == 1)

   348         price += _isRepG1[state.Index].GetPrice0();

   349       else

   350       {

   351         price += _isRepG1[state.Index].GetPrice1();

   352         price += _isRepG2[state.Index].GetPrice(repIndex - 2);

   353       }

   354     }

   355     return price;

   356   }

   357   UInt32 GetRepPrice(UInt32 repIndex, UInt32 len, CState state, UInt32 posState) const

   358   {

   359     return _repMatchLenEncoder.GetPrice(len - kMatchMinLen, posState) +

   360         GetPureRepPrice(repIndex, state, posState);

   361   }

   362   /*

   363   UInt32 GetPosLen2Price(UInt32 pos, UInt32 posState) const

   364   {

   365     if (pos >= kNumFullDistances)

   366       return kIfinityPrice;

   367     return _distancesPrices[0][pos] + _lenEncoder.GetPrice(0, posState);

   368   }

   369   UInt32 GetPosLen3Price(UInt32 pos, UInt32 len, UInt32 posState) const

   370   {

   371     UInt32 price;

   372     UInt32 lenToPosState = GetLenToPosState(len);

   373     if (pos < kNumFullDistances)

   374       price = _distancesPrices[lenToPosState][pos];

   375     else

   376       price = _posSlotPrices[lenToPosState][GetPosSlot2(pos)] + 

   377           _alignPrices[pos & kAlignMask];

   378     return price + _lenEncoder.GetPrice(len - kMatchMinLen, posState);

   379   }

   380   */

   381   UInt32 GetPosLenPrice(UInt32 pos, UInt32 len, UInt32 posState) const

   382   {

   383     UInt32 price;

   384     UInt32 lenToPosState = GetLenToPosState(len);

   385     if (pos < kNumFullDistances)

   386       price = _distancesPrices[lenToPosState][pos];

   387     else

   388       price = _posSlotPrices[lenToPosState][GetPosSlot2(pos)] + 

   389           _alignPrices[pos & kAlignMask];

   390     return price + _lenEncoder.GetPrice(len - kMatchMinLen, posState);

   391   }

   392 

   393   UInt32 Backward(UInt32 &backRes, UInt32 cur);

   394   UInt32 GetOptimum(UInt32 position, UInt32 &backRes);

   395   UInt32 GetOptimumFast(UInt32 &backRes);

   396 

   397   void FillDistancesPrices();

   398   void FillAlignPrices();

   399     

   400   void ReleaseStreams()

   401   {

   402     ReleaseMFStream();

   403     ReleaseOutStream();

   404   }

   405 

   406   HRESULT Flush(UInt32 nowPos);

   407   class CCoderReleaser

   408   {

   409     CEncoder *_coder;

   410   public:

   411     CCoderReleaser(CEncoder *coder): _coder(coder) {}

   412     ~CCoderReleaser() { _coder->ReleaseStreams(); }

   413   };

   414   friend class CCoderReleaser;

   415 

   416   void WriteEndMarker(UInt32 posState);

   417 

   418 public:

   419   CEncoder();

   420   void SetWriteEndMarkerMode(bool writeEndMarker)

   421     { _writeEndMark= writeEndMarker; }

   422 

   423   HRESULT Create();

   424 

   425   MY_UNKNOWN_IMP3(

   426       ICompressSetOutStream,

   427       ICompressSetCoderProperties,

   428       ICompressWriteCoderProperties

   429       )

   430     

   431   HRESULT Init();

   432   

   433   // ICompressCoder interface

   434   HRESULT SetStreams(ISequentialInStream *inStream,

   435       ISequentialOutStream *outStream,

   436       const UInt64 *inSize, const UInt64 *outSize);

   437   HRESULT CodeOneBlock(UInt64 *inSize, UInt64 *outSize, Int32 *finished);

   438 

   439   HRESULT CodeReal(ISequentialInStream *inStream,

   440       ISequentialOutStream *outStream, 

   441       const UInt64 *inSize, const UInt64 *outSize,

   442       ICompressProgressInfo *progress);

   443 

   444   // ICompressCoder interface

   445   STDMETHOD(Code)(ISequentialInStream *inStream,

   446       ISequentialOutStream *outStream, 

   447       const UInt64 *inSize, const UInt64 *outSize,

   448       ICompressProgressInfo *progress);

   449 

   450   // ICompressSetCoderProperties2

   451   STDMETHOD(SetCoderProperties)(const PROPID *propIDs, 

   452       const PROPVARIANT *properties, UInt32 numProperties);

   453   

   454   // ICompressWriteCoderProperties

   455   STDMETHOD(WriteCoderProperties)(ISequentialOutStream *outStream);

   456 

   457   STDMETHOD(SetOutStream)(ISequentialOutStream *outStream);

   458   STDMETHOD(ReleaseOutStream)();

   459 

   460   virtual ~CEncoder();

   461 };

   462 

   463 }}

   464 

   465 #endif