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
9extern "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
22namespace NCompress {
23namespace NLZMA {
24
25typedef NRangeCoder::CBitEncoder<kNumMoveBits> CMyBitEncoder;
26
27class CBaseState
28{
29protected:
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
42struct 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
70static const int kNumLogBits = 13; // don't change it !
71extern Byte g_FastPos[];
72#endif
73inline 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
90inline 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
111const UInt32 kIfinityPrice = 0xFFFFFFF;
112
113const UInt32 kNumOpts = 1 << 12;
114
115
116class CLiteralEncoder2
117{
118  CMyBitEncoder _encoders[0x300];
119public:
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
130class CLiteralEncoder
131{
132  CLiteralEncoder2 *_coders;
133  int _numPrevBits;
134  int _numPosBits;
135  UInt32 _posMask;
136public:
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
167namespace NLength {
168
169class 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;
176public:
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
182const UInt32 kNumSpecSymbols = kNumLowSymbols + kNumMidSymbols;
183
184class CPriceTableEncoder: public CEncoder
185{
186  UInt32 _prices[kNumPosStatesEncodingMax][kNumSymbolsTotal];
187  UInt32 _tableSize;
188  UInt32 _counters[kNumPosStatesEncodingMax];
189public:
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
213typedef struct _CSeqInStream
214{
215  ISeqInStream SeqInStream;
216  CMyComPtr<ISequentialInStream> RealStream;
217} CSeqInStream;
218
219
220class 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
418public:
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
466