Debian Codegraph @

utils/lzma/SRC/7zip/Compress/LZMA/LZMAEncoder.cpp

raw
1 // LZMA/Encoder.cpp
2
3 #include "StdAfx.h"
4
5 #include "../../../Common/Defs.h"
6
7 #include "LZMAEncoder.h"
8
9 // for minimal compressing code size define these:
10 #define COMPRESS_MF_BT
11 #define COMPRESS_MF_BT4
12
13 #if !defined(COMPRESS_MF_BT) && !defined(COMPRESS_MF_PAT) && !defined(COMPRESS_MF_HC)
14 #define COMPRESS_MF_BT
15 #define COMPRESS_MF_PAT
16 #define COMPRESS_MF_HC
17 #endif
18
19 #ifdef COMPRESS_MF_BT
20 #if !defined(COMPRESS_MF_BT2) && !defined(COMPRESS_MF_BT3) && !defined(COMPRESS_MF_BT4) && !defined(COMPRESS_MF_BT4B)
21 #define COMPRESS_MF_BT2
22 #define COMPRESS_MF_BT3
23 #define COMPRESS_MF_BT4
24 #define COMPRESS_MF_BT4B
25 #endif
26 #ifdef COMPRESS_MF_BT2
27 #include "../LZ/BinTree/BinTree2.h"
28 #endif
29 #ifdef COMPRESS_MF_BT3
30 #include "../LZ/BinTree/BinTree3.h"
31 #endif
32 #ifdef COMPRESS_MF_BT4
33 #include "../LZ/BinTree/BinTree4.h"
34 #endif
35 #ifdef COMPRESS_MF_BT4B
36 #include "../LZ/BinTree/BinTree4b.h"
37 #endif
38 #endif
39
40 #ifdef COMPRESS_MF_PAT
41 #include "../LZ/Patricia/Pat2.h"
42 #include "../LZ/Patricia/Pat2H.h"
43 #include "../LZ/Patricia/Pat3H.h"
44 #include "../LZ/Patricia/Pat4H.h"
45 #include "../LZ/Patricia/Pat2R.h"
46 #endif
47
48 #ifdef COMPRESS_MF_HC
49 #include "../LZ/HashChain/HC3.h"
50 #include "../LZ/HashChain/HC4.h"
51 #endif
52
53 #ifdef COMPRESS_MF_MT
54 #include "../LZ/MT/MT.h"
55 #endif
56
57 namespace NCompress {
58 namespace NLZMA {
59
60 const int kDefaultDictionaryLogSize = 20;
61 const UInt32 kNumFastBytesDefault = 0x20;
62
63 enum
64 {
65 kBT2,
66 kBT3,
67 kBT4,
68 kBT4B,
69 kPat2,
70 kPat2H,
71 kPat3H,
72 kPat4H,
73 kPat2R,
74 kHC3,
75 kHC4
76 };
77
78 static const wchar_t *kMatchFinderIDs[] =
79 {
80 L"BT2",
81 L"BT3",
82 L"BT4",
83 L"BT4B",
84 L"PAT2",
85 L"PAT2H",
86 L"PAT3H",
87 L"PAT4H",
88 L"PAT2R",
89 L"HC3",
90 L"HC4"
91 };
92
93 Byte g_FastPos[1024];
94
95 class CFastPosInit
96 {
97 public:
98 CFastPosInit() { Init(); }
99 void Init()
100 {
101 const Byte kFastSlots = 20;
102 int c = 2;
103 g_FastPos[0] = 0;
104 g_FastPos[1] = 1;
105
106 for (Byte slotFast = 2; slotFast < kFastSlots; slotFast++)
107 {
108 UInt32 k = (1 << ((slotFast >> 1) - 1));
109 for (UInt32 j = 0; j < k; j++, c++)
110 g_FastPos[c] = slotFast;
111 }
112 }
113 } g_FastPosInit;
114
115
116 void CLiteralEncoder2::Encode(NRangeCoder::CEncoder *rangeEncoder, Byte symbol)
117 {
118 UInt32 context = 1;
119 int i = 8;
120 do
121 {
122 i--;
123 UInt32 bit = (symbol >> i) & 1;
124 _encoders[context].Encode(rangeEncoder, bit);
125 context = (context << 1) | bit;
126 }
127 while(i != 0);
128 }
129
130 void CLiteralEncoder2::EncodeMatched(NRangeCoder::CEncoder *rangeEncoder,
131 Byte matchByte, Byte symbol)
132 {
133 UInt32 context = 1;
134 int i = 8;
135 do
136 {
137 i--;
138 UInt32 bit = (symbol >> i) & 1;
139 UInt32 matchBit = (matchByte >> i) & 1;
140 _encoders[0x100 + (matchBit << 8) + context].Encode(rangeEncoder, bit);
141 context = (context << 1) | bit;
142 if (matchBit != bit)
143 {
144 while(i != 0)
145 {
146 i--;
147 UInt32 bit = (symbol >> i) & 1;
148 _encoders[context].Encode(rangeEncoder, bit);
149 context = (context << 1) | bit;
150 }
151 break;
152 }
153 }
154 while(i != 0);
155 }
156
157 UInt32 CLiteralEncoder2::GetPrice(bool matchMode, Byte matchByte, Byte symbol) const
158 {
159 UInt32 price = 0;
160 UInt32 context = 1;
161 int i = 8;
162 if (matchMode)
163 {
164 do
165 {
166 i--;
167 UInt32 matchBit = (matchByte >> i) & 1;
168 UInt32 bit = (symbol >> i) & 1;
169 price += _encoders[0x100 + (matchBit << 8) + context].GetPrice(bit);
170 context = (context << 1) | bit;
171 if (matchBit != bit)
172 break;
173 }
174 while (i != 0);
175 }
176 while(i != 0)
177 {
178 i--;
179 UInt32 bit = (symbol >> i) & 1;
180 price += _encoders[context].GetPrice(bit);
181 context = (context << 1) | bit;
182 }
183 return price;
184 };
185
186
187 namespace NLength {
188
189 void CEncoder::Init(UInt32 numPosStates)
190 {
191 _choice.Init();
192 _choice2.Init();
193 for (UInt32 posState = 0; posState < numPosStates; posState++)
194 {
195 _lowCoder[posState].Init();
196 _midCoder[posState].Init();
197 }
198 _highCoder.Init();
199 }
200
201 void CEncoder::Encode(NRangeCoder::CEncoder *rangeEncoder, UInt32 symbol, UInt32 posState)
202 {
203 if(symbol < kNumLowSymbols)
204 {
205 _choice.Encode(rangeEncoder, 0);
206 _lowCoder[posState].Encode(rangeEncoder, symbol);
207 }
208 else
209 {
210 _choice.Encode(rangeEncoder, 1);
211 if(symbol < kNumLowSymbols + kNumMidSymbols)
212 {
213 _choice2.Encode(rangeEncoder, 0);
214 _midCoder[posState].Encode(rangeEncoder, symbol - kNumLowSymbols);
215 }
216 else
217 {
218 _choice2.Encode(rangeEncoder, 1);
219 _highCoder.Encode(rangeEncoder, symbol - kNumLowSymbols - kNumMidSymbols);
220 }
221 }
222 }
223
224 UInt32 CEncoder::GetPrice(UInt32 symbol, UInt32 posState) const
225 {
226 if(symbol < kNumLowSymbols)
227 return _choice.GetPrice0() + _lowCoder[posState].GetPrice(symbol);
228 UInt32 price = _choice.GetPrice1();
229 if(symbol < kNumLowSymbols + kNumMidSymbols)
230 {
231 price += _choice2.GetPrice0();
232 price += _midCoder[posState].GetPrice(symbol - kNumLowSymbols);
233 }
234 else
235 {
236 price += _choice2.GetPrice1();
237 price += _highCoder.GetPrice(symbol - kNumLowSymbols - kNumMidSymbols);
238 }
239 return price;
240 }
241
242 }
243 CEncoder::CEncoder():
244 _numFastBytes(kNumFastBytesDefault),
245 _distTableSize(kDefaultDictionaryLogSize * 2),
246 _posStateBits(2),
247 _posStateMask(4 - 1),
248 _numLiteralPosStateBits(0),
249 _numLiteralContextBits(3),
250 _dictionarySize(1 << kDefaultDictionaryLogSize),
251 _dictionarySizePrev(UInt32(-1)),
252 _numFastBytesPrev(UInt32(-1)),
253 _matchFinderIndex(kBT4),
254 #ifdef COMPRESS_MF_MT
255 _multiThread(false),
256 #endif
257 _writeEndMark(false)
258 {
259 _maxMode = false;
260 _fastMode = false;
261 }
262
263 HRESULT CEncoder::Create()
264 {
265 if (!_rangeEncoder.Create(1 << 20))
266 return E_OUTOFMEMORY;
267 if (!_matchFinder)
268 {
269 switch(_matchFinderIndex)
270 {
271 #ifdef COMPRESS_MF_BT
272 #ifdef COMPRESS_MF_BT2
273 case kBT2:
274 _matchFinder = new NBT2::CMatchFinderBinTree;
275 break;
276 #endif
277 #ifdef COMPRESS_MF_BT3
278 case kBT3:
279 _matchFinder = new NBT3::CMatchFinderBinTree;
280 break;
281 #endif
282 #ifdef COMPRESS_MF_BT4
283 case kBT4:
284 _matchFinder = new NBT4::CMatchFinderBinTree;
285 break;
286 #endif
287 #ifdef COMPRESS_MF_BT4B
288 case kBT4B:
289 _matchFinder = new NBT4B::CMatchFinderBinTree;
290 break;
291 #endif
292 #endif
293
294 #ifdef COMPRESS_MF_PAT
295 case kPat2:
296 _matchFinder = new NPat2::CPatricia;
297 break;
298 case kPat2H:
299 _matchFinder = new NPat2H::CPatricia;
300 break;
301 case kPat3H:
302 _matchFinder = new NPat3H::CPatricia;
303 break;
304 case kPat4H:
305 _matchFinder = new NPat4H::CPatricia;
306 break;
307 case kPat2R:
308 _matchFinder = new NPat2R::CPatricia;
309 break;
310 #endif
311
312 #ifdef COMPRESS_MF_HC
313 case kHC3:
314 _matchFinder = new NHC3::CMatchFinderHC;
315 break;
316 case kHC4:
317 _matchFinder = new NHC4::CMatchFinderHC;
318 break;
319 #endif
320 }
321 if (_matchFinder == 0)
322 return E_OUTOFMEMORY;
323
324 #ifdef COMPRESS_MF_MT
325 if (_multiThread && !(_fastMode && (_matchFinderIndex == kHC3 || _matchFinderIndex == kHC4)))
326 {
327 CMatchFinderMT *mfSpec = new CMatchFinderMT;
328 if (mfSpec == 0)
329 return E_OUTOFMEMORY;
330 CMyComPtr<IMatchFinder> mf = mfSpec;
331 RINOK(mfSpec->SetMatchFinder(_matchFinder));
332 _matchFinder.Release();
333 _matchFinder = mf;
334 }
335 #endif
336 }
337
338 if (!_literalEncoder.Create(_numLiteralPosStateBits, _numLiteralContextBits))
339 return E_OUTOFMEMORY;
340
341 if (_dictionarySize == _dictionarySizePrev && _numFastBytesPrev == _numFastBytes)
342 return S_OK;
343 RINOK(_matchFinder->Create(_dictionarySize, kNumOpts, _numFastBytes,
344 kMatchMaxLen - _numFastBytes));
345 _dictionarySizePrev = _dictionarySize;
346 _numFastBytesPrev = _numFastBytes;
347 return S_OK;
348 }
349
350 static bool AreStringsEqual(const wchar_t *base, const wchar_t *testString)
351 {
352 while (true)
353 {
354 wchar_t c = *testString;
355 if (c >= 'a' && c <= 'z')
356 c -= 0x20;
357 if (*base != c)
358 return false;
359 if (c == 0)
360 return true;
361 base++;
362 testString++;
363 }
364 }
365
366 static int FindMatchFinder(const wchar_t *s)
367 {
368 for (int m = 0; m < (int)(sizeof(kMatchFinderIDs) / sizeof(kMatchFinderIDs[0])); m++)
369 if (AreStringsEqual(kMatchFinderIDs[m], s))
370 return m;
371 return -1;
372 }
373
374 STDMETHODIMP CEncoder::SetCoderProperties(const PROPID *propIDs,
375 const PROPVARIANT *properties, UInt32 numProperties)
376 {
377 for (UInt32 i = 0; i < numProperties; i++)
378 {
379 const PROPVARIANT &prop = properties[i];
380 switch(propIDs[i])
381 {
382 case NCoderPropID::kNumFastBytes:
383 {
384 if (prop.vt != VT_UI4)
385 return E_INVALIDARG;
386 UInt32 numFastBytes = prop.ulVal;
387 if(numFastBytes < 5 || numFastBytes > kMatchMaxLen)
388 return E_INVALIDARG;
389 _numFastBytes = numFastBytes;
390 break;
391 }
392 case NCoderPropID::kAlgorithm:
393 {
394 if (prop.vt != VT_UI4)
395 return E_INVALIDARG;
396 UInt32 maximize = prop.ulVal;
397 _fastMode = (maximize == 0);
398 _maxMode = (maximize >= 2);
399 break;
400 }
401 case NCoderPropID::kMatchFinder:
402 {
403 if (prop.vt != VT_BSTR)
404 return E_INVALIDARG;
405 int matchFinderIndexPrev = _matchFinderIndex;
406 int m = FindMatchFinder(prop.bstrVal);
407 if (m < 0)
408 return E_INVALIDARG;
409 _matchFinderIndex = m;
410 if (_matchFinder && matchFinderIndexPrev != _matchFinderIndex)
411 {
412 _dictionarySizePrev = UInt32(-1);
413 _matchFinder.Release();
414 }
415 break;
416 }
417 #ifdef COMPRESS_MF_MT
418 case NCoderPropID::kMultiThread:
419 {
420 if (prop.vt != VT_BOOL)
421 return E_INVALIDARG;
422 bool newMultiThread = (prop.boolVal == VARIANT_TRUE);
423 if (newMultiThread != _multiThread)
424 {
425 _dictionarySizePrev = UInt32(-1);
426 _matchFinder.Release();
427 }
428 _multiThread = newMultiThread;
429 break;
430 }
431 #endif
432 case NCoderPropID::kDictionarySize:
433 {
434 const int kDicLogSizeMaxCompress = 28;
435 if (prop.vt != VT_UI4)
436 return E_INVALIDARG;
437 UInt32 dictionarySize = prop.ulVal;
438 if (dictionarySize < UInt32(1 << kDicLogSizeMin) ||
439 dictionarySize > UInt32(1 << kDicLogSizeMaxCompress))
440 return E_INVALIDARG;
441 _dictionarySize = dictionarySize;
442 UInt32 dicLogSize;
443 for(dicLogSize = 0; dicLogSize < (UInt32)kDicLogSizeMaxCompress; dicLogSize++)
444 if (dictionarySize <= (UInt32(1) << dicLogSize))
445 break;
446 _distTableSize = dicLogSize * 2;
447 break;
448 }
449 case NCoderPropID::kPosStateBits:
450 {
451 if (prop.vt != VT_UI4)
452 return E_INVALIDARG;
453 UInt32 value = prop.ulVal;
454 if (value > (UInt32)NLength::kNumPosStatesBitsEncodingMax)
455 return E_INVALIDARG;
456 _posStateBits = value;
457 _posStateMask = (1 << _posStateBits) - 1;
458 break;
459 }
460 case NCoderPropID::kLitPosBits:
461 {
462 if (prop.vt != VT_UI4)
463 return E_INVALIDARG;
464 UInt32 value = prop.ulVal;
465 if (value > (UInt32)kNumLitPosStatesBitsEncodingMax)
466 return E_INVALIDARG;
467 _numLiteralPosStateBits = value;
468 break;
469 }
470 case NCoderPropID::kLitContextBits:
471 {
472 if (prop.vt != VT_UI4)
473 return E_INVALIDARG;
474 UInt32 value = prop.ulVal;
475 if (value > (UInt32)kNumLitContextBitsMax)
476 return E_INVALIDARG;
477 _numLiteralContextBits = value;
478 break;
479 }
480 case NCoderPropID::kEndMarker:
481 {
482 if (prop.vt != VT_BOOL)
483 return E_INVALIDARG;
484 SetWriteEndMarkerMode(prop.boolVal == VARIANT_TRUE);
485 break;
486 }
487 default:
488 return E_INVALIDARG;
489 }
490 }
491 return S_OK;
492 }
493
494 STDMETHODIMP CEncoder::WriteCoderProperties(ISequentialOutStream *outStream)
495 {
496 const UInt32 kPropSize = 5;
497 Byte properties[kPropSize];
498 properties[0] = (_posStateBits * 5 + _numLiteralPosStateBits) * 9 + _numLiteralContextBits;
499 for (int i = 0; i < 4; i++)
500 properties[1 + i] = Byte(_dictionarySize >> (8 * i));
501 return outStream->Write(properties, kPropSize, NULL);
502 }
503
504 STDMETHODIMP CEncoder::SetOutStream(ISequentialOutStream *outStream)
505 {
506 _rangeEncoder.SetStream(outStream);
507 return S_OK;
508 }
509
510 STDMETHODIMP CEncoder::ReleaseOutStream()
511 {
512 _rangeEncoder.ReleaseStream();
513 return S_OK;
514 }
515
516 HRESULT CEncoder::Init()
517 {
518 CBaseState::Init();
519
520 // RINOK(_matchFinder->Init(inStream));
521 _rangeEncoder.Init();
522
523 for(int i = 0; i < kNumStates; i++)
524 {
525 for (UInt32 j = 0; j <= _posStateMask; j++)
526 {
527 _isMatch[i][j].Init();
528 _isRep0Long[i][j].Init();
529 }
530 _isRep[i].Init();
531 _isRepG0[i].Init();
532 _isRepG1[i].Init();
533 _isRepG2[i].Init();
534 }
535
536 _literalEncoder.Init();
537
538 // _repMatchLenEncoder.Init();
539
540 {
541 for(UInt32 i = 0; i < kNumLenToPosStates; i++)
542 _posSlotEncoder[i].Init();
543 }
544 {
545 for(UInt32 i = 0; i < kNumFullDistances - kEndPosModelIndex; i++)
546 _posEncoders[i].Init();
547 }
548
549 _lenEncoder.Init(1 << _posStateBits);
550 _repMatchLenEncoder.Init(1 << _posStateBits);
551
552 _posAlignEncoder.Init();
553
554 _longestMatchWasFound = false;
555 _optimumEndIndex = 0;
556 _optimumCurrentIndex = 0;
557 _additionalOffset = 0;
558
559 return S_OK;
560 }
561
562 HRESULT CEncoder::MovePos(UInt32 num)
563 {
564 for (;num != 0; num--)
565 {
566 _matchFinder->DummyLongestMatch();
567 RINOK(_matchFinder->MovePos());
568 _additionalOffset++;
569 }
570 return S_OK;
571 }
572
573 UInt32 CEncoder::Backward(UInt32 &backRes, UInt32 cur)
574 {
575 _optimumEndIndex = cur;
576 UInt32 posMem = _optimum[cur].PosPrev;
577 UInt32 backMem = _optimum[cur].BackPrev;
578 do
579 {
580 if (_optimum[cur].Prev1IsChar)
581 {
582 _optimum[posMem].MakeAsChar();
583 _optimum[posMem].PosPrev = posMem - 1;
584 if (_optimum[cur].Prev2)
585 {
586 _optimum[posMem - 1].Prev1IsChar = false;
587 _optimum[posMem - 1].PosPrev = _optimum[cur].PosPrev2;
588 _optimum[posMem - 1].BackPrev = _optimum[cur].BackPrev2;
589 }
590 }
591 UInt32 posPrev = posMem;
592 UInt32 backCur = backMem;
593
594 backMem = _optimum[posPrev].BackPrev;
595 posMem = _optimum[posPrev].PosPrev;
596
597 _optimum[posPrev].BackPrev = backCur;
598 _optimum[posPrev].PosPrev = cur;
599 cur = posPrev;
600 }
601 while(cur != 0);
602 backRes = _optimum[0].BackPrev;
603 _optimumCurrentIndex = _optimum[0].PosPrev;
604 return _optimumCurrentIndex;
605 }
606
607 /*
608 inline UInt32 GetMatchLen(const Byte *data, UInt32 back, UInt32 limit)
609 {
610 back++;
611 for(UInt32 i = 0; i < limit && data[i] == data[i - back]; i++);
612 return i;
613 }
614 */
615
616 HRESULT CEncoder::GetOptimum(UInt32 position, UInt32 &backRes, UInt32 &lenRes)
617 {
618 if(_optimumEndIndex != _optimumCurrentIndex)
619 {
620 lenRes = _optimum[_optimumCurrentIndex].PosPrev - _optimumCurrentIndex;
621 backRes = _optimum[_optimumCurrentIndex].BackPrev;
622 _optimumCurrentIndex = _optimum[_optimumCurrentIndex].PosPrev;
623 return S_OK;
624 }
625 _optimumCurrentIndex = 0;
626 _optimumEndIndex = 0; // test it;
627
628 UInt32 lenMain;
629 if (!_longestMatchWasFound)
630 {
631 RINOK(ReadMatchDistances(lenMain));
632 }
633 else
634 {
635 lenMain = _longestMatchLength;
636 _longestMatchWasFound = false;
637 }
638
639
640 UInt32 reps[kNumRepDistances];
641 UInt32 repLens[kNumRepDistances];
642 UInt32 repMaxIndex = 0;
643 UInt32 i;
644 for(i = 0; i < kNumRepDistances; i++)
645 {
646 reps[i] = _repDistances[i];
647 repLens[i] = _matchFinder->GetMatchLen(0 - 1, reps[i], kMatchMaxLen);
648 if (i == 0 || repLens[i] > repLens[repMaxIndex])
649 repMaxIndex = i;
650 }
651 if(repLens[repMaxIndex] > _numFastBytes)
652 {
653 backRes = repMaxIndex;
654 lenRes = repLens[repMaxIndex];
655 return MovePos(lenRes - 1);
656 }
657
658 if(lenMain > _numFastBytes)
659 {
660 backRes = _matchDistances[_numFastBytes] + kNumRepDistances;
661 lenRes = lenMain;
662 return MovePos(lenMain - 1);
663 }
664 Byte currentByte = _matchFinder->GetIndexByte(0 - 1);
665
666 _optimum[0].State = _state;
667
668 Byte matchByte;
669
670 matchByte = _matchFinder->GetIndexByte(0 - _repDistances[0] - 1 - 1);
671
672 UInt32 posState = (position & _posStateMask);
673
674 _optimum[1].Price = _isMatch[_state.Index][posState].GetPrice0() +
675 _literalEncoder.GetPrice(position, _previousByte, !_state.IsCharState(), matchByte, currentByte);
676 _optimum[1].MakeAsChar();
677
678 _optimum[1].PosPrev = 0;
679
680 for (i = 0; i < kNumRepDistances; i++)
681 _optimum[0].Backs[i] = reps[i];
682
683 UInt32 matchPrice = _isMatch[_state.Index][posState].GetPrice1();
684 UInt32 repMatchPrice = matchPrice + _isRep[_state.Index].GetPrice1();
685
686 if(matchByte == currentByte)
687 {
688 UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(_state, posState);
689 if(shortRepPrice < _optimum[1].Price)
690 {
691 _optimum[1].Price = shortRepPrice;
692 _optimum[1].MakeAsShortRep();
693 }
694 }
695 if(lenMain < 2)
696 {
697 backRes = _optimum[1].BackPrev;
698 lenRes = 1;
699 return S_OK;
700 }
701
702
703 UInt32 normalMatchPrice = matchPrice +
704 _isRep[_state.Index].GetPrice0();
705
706 if (lenMain <= repLens[repMaxIndex])
707 lenMain = 0;
708
709 UInt32 len;
710 for(len = 2; len <= lenMain; len++)
711 {
712 _optimum[len].PosPrev = 0;
713 _optimum[len].BackPrev = _matchDistances[len] + kNumRepDistances;
714 _optimum[len].Price = normalMatchPrice +
715 GetPosLenPrice(_matchDistances[len], len, posState);
716 _optimum[len].Prev1IsChar = false;
717 }
718
719 if (lenMain < repLens[repMaxIndex])
720 lenMain = repLens[repMaxIndex];
721
722 for (; len <= lenMain; len++)
723 _optimum[len].Price = kIfinityPrice;
724
725 for(i = 0; i < kNumRepDistances; i++)
726 {
727 UInt32 repLen = repLens[i];
728 for(UInt32 lenTest = 2; lenTest <= repLen; lenTest++)
729 {
730 UInt32 curAndLenPrice = repMatchPrice + GetRepPrice(i, lenTest, _state, posState);
731 COptimal &optimum = _optimum[lenTest];
732 if (curAndLenPrice < optimum.Price)
733 {
734 optimum.Price = curAndLenPrice;
735 optimum.PosPrev = 0;
736 optimum.BackPrev = i;
737 optimum.Prev1IsChar = false;
738 }
739 }
740 }
741
742 UInt32 cur = 0;
743 UInt32 lenEnd = lenMain;
744
745 while(true)
746 {
747 cur++;
748 if(cur == lenEnd)
749 {
750 lenRes = Backward(backRes, cur);
751 return S_OK;
752 }
753 position++;
754 UInt32 posPrev = _optimum[cur].PosPrev;
755 CState state;
756 if (_optimum[cur].Prev1IsChar)
757 {
758 posPrev--;
759 if (_optimum[cur].Prev2)
760 {
761 state = _optimum[_optimum[cur].PosPrev2].State;
762 if (_optimum[cur].BackPrev2 < kNumRepDistances)
763 state.UpdateRep();
764 else
765 state.UpdateMatch();
766 }
767 else
768 state = _optimum[posPrev].State;
769 state.UpdateChar();
770 }
771 else
772 state = _optimum[posPrev].State;
773 if (posPrev == cur - 1)
774 {
775 if (_optimum[cur].IsShortRep())
776 state.UpdateShortRep();
777 else
778 state.UpdateChar();
779 /*
780 if (_optimum[cur].Prev1IsChar)
781 for(int i = 0; i < kNumRepDistances; i++)
782 reps[i] = _optimum[posPrev].Backs[i];
783 */
784 }
785 else
786 {
787 UInt32 pos;
788 if (_optimum[cur].Prev1IsChar && _optimum[cur].Prev2)
789 {
790 posPrev = _optimum[cur].PosPrev2;
791 pos = _optimum[cur].BackPrev2;
792 state.UpdateRep();
793 }
794 else
795 {
796 pos = _optimum[cur].BackPrev;
797 if (pos < kNumRepDistances)
798 state.UpdateRep();
799 else
800 state.UpdateMatch();
801 }
802 if (pos < kNumRepDistances)
803 {
804 reps[0] = _optimum[posPrev].Backs[pos];
805 UInt32 i;
806 for(i = 1; i <= pos; i++)
807 reps[i] = _optimum[posPrev].Backs[i - 1];
808 for(; i < kNumRepDistances; i++)
809 reps[i] = _optimum[posPrev].Backs[i];
810 }
811 else
812 {
813 reps[0] = (pos - kNumRepDistances);
814 for(UInt32 i = 1; i < kNumRepDistances; i++)
815 reps[i] = _optimum[posPrev].Backs[i - 1];
816 }
817 }
818 _optimum[cur].State = state;
819 for(UInt32 i = 0; i < kNumRepDistances; i++)
820 _optimum[cur].Backs[i] = reps[i];
821 UInt32 newLen;
822 RINOK(ReadMatchDistances(newLen));
823 if(newLen > _numFastBytes)
824 {
825 _longestMatchLength = newLen;
826 _longestMatchWasFound = true;
827 lenRes = Backward(backRes, cur);
828 return S_OK;
829 }
830 UInt32 curPrice = _optimum[cur].Price;
831 // Byte currentByte = _matchFinder->GetIndexByte(0 - 1);
832 // Byte matchByte = _matchFinder->GetIndexByte(0 - reps[0] - 1 - 1);
833 const Byte *data = _matchFinder->GetPointerToCurrentPos() - 1;
834 Byte currentByte = *data;
835 Byte matchByte = data[(size_t)0 - reps[0] - 1];
836
837 UInt32 posState = (position & _posStateMask);
838
839 UInt32 curAnd1Price = curPrice +
840 _isMatch[state.Index][posState].GetPrice0() +
841 _literalEncoder.GetPrice(position, data[(size_t)0 - 1], !state.IsCharState(), matchByte, currentByte);
842
843 COptimal &nextOptimum = _optimum[cur + 1];
844
845 bool nextIsChar = false;
846 if (curAnd1Price < nextOptimum.Price)
847 {
848 nextOptimum.Price = curAnd1Price;
849 nextOptimum.PosPrev = cur;
850 nextOptimum.MakeAsChar();
851 nextIsChar = true;
852 }
853
854 UInt32 matchPrice = curPrice + _isMatch[state.Index][posState].GetPrice1();
855 UInt32 repMatchPrice = matchPrice + _isRep[state.Index].GetPrice1();
856
857 if(matchByte == currentByte &&
858 !(nextOptimum.PosPrev < cur && nextOptimum.BackPrev == 0))
859 {
860 UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(state, posState);
861 if(shortRepPrice <= nextOptimum.Price)
862 {
863 nextOptimum.Price = shortRepPrice;
864 nextOptimum.PosPrev = cur;
865 nextOptimum.MakeAsShortRep();
866 // nextIsChar = false;
867 }
868 }
869 /*
870 if(newLen == 2 && _matchDistances[2] >= kDistLimit2) // test it maybe set 2000 ?
871 continue;
872 */
873
874 UInt32 numAvailableBytes = _matchFinder->GetNumAvailableBytes() + 1;
875 numAvailableBytes = MyMin(kNumOpts - 1 - cur, numAvailableBytes);
876
877 if (numAvailableBytes < 2)
878 continue;
879 if (numAvailableBytes > _numFastBytes)
880 numAvailableBytes = _numFastBytes;
881 if (numAvailableBytes >= 3 && !nextIsChar)
882 {
883 UInt32 backOffset = reps[0] + 1;
884 UInt32 temp;
885 for (temp = 1; temp < numAvailableBytes; temp++)
886 if (data[temp] != data[(size_t)temp - backOffset])
887 break;
888 UInt32 lenTest2 = temp - 1;
889 if (lenTest2 >= 2)
890 {
891 CState state2 = state;
892 state2.UpdateChar();
893 UInt32 posStateNext = (position + 1) & _posStateMask;
894 UInt32 nextRepMatchPrice = curAnd1Price +
895 _isMatch[state2.Index][posStateNext].GetPrice1() +
896 _isRep[state2.Index].GetPrice1();
897 // for (; lenTest2 >= 2; lenTest2--)
898 {
899 while(lenEnd < cur + 1 + lenTest2)
900 _optimum[++lenEnd].Price = kIfinityPrice;
901 UInt32 curAndLenPrice = nextRepMatchPrice + GetRepPrice(
902 0, lenTest2, state2, posStateNext);
903 COptimal &optimum = _optimum[cur + 1 + lenTest2];
904 if (curAndLenPrice < optimum.Price)
905 {
906 optimum.Price = curAndLenPrice;
907 optimum.PosPrev = cur + 1;
908 optimum.BackPrev = 0;
909 optimum.Prev1IsChar = true;
910 optimum.Prev2 = false;
911 }
912 }
913 }
914 }
915 for(UInt32 repIndex = 0; repIndex < kNumRepDistances; repIndex++)
916 {
917 // UInt32 repLen = _matchFinder->GetMatchLen(0 - 1, reps[repIndex], newLen); // test it;
918 UInt32 backOffset = reps[repIndex] + 1;
919 UInt32 lenTest;
920 for (lenTest = 0; lenTest < numAvailableBytes; lenTest++)
921 if (data[lenTest] != data[(size_t)lenTest - backOffset])
922 break;
923 for(; lenTest >= 2; lenTest--)
924 {
925 while(lenEnd < cur + lenTest)
926 _optimum[++lenEnd].Price = kIfinityPrice;
927 UInt32 curAndLenPrice = repMatchPrice + GetRepPrice(repIndex, lenTest, state, posState);
928 COptimal &optimum = _optimum[cur + lenTest];
929 if (curAndLenPrice < optimum.Price)
930 {
931 optimum.Price = curAndLenPrice;
932 optimum.PosPrev = cur;
933 optimum.BackPrev = repIndex;
934 optimum.Prev1IsChar = false;
935 }
936
937 /*
938 if (_maxMode)
939 {
940 UInt32 temp;
941 for (temp = lenTest + 1; temp < numAvailableBytes; temp++)
942 if (data[temp] != data[(size_t)temp - backOffset])
943 break;
944 UInt32 lenTest2 = temp - (lenTest + 1);
945 if (lenTest2 >= 2)
946 {
947 CState state2 = state;
948 state2.UpdateRep();
949 UInt32 posStateNext = (position + lenTest) & _posStateMask;
950 UInt32 curAndLenCharPrice = curAndLenPrice +
951 _isMatch[state2.Index][posStateNext].GetPrice0() +
952 _literalEncoder.GetPrice(position + lenTest, data[(size_t)lenTest - 1],
953 true, data[(size_t)lenTest - backOffset], data[lenTest]);
954 state2.UpdateChar();
955 posStateNext = (position + lenTest + 1) & _posStateMask;
956 UInt32 nextMatchPrice = curAndLenCharPrice + _isMatch[state2.Index][posStateNext].GetPrice1();
957 UInt32 nextRepMatchPrice = nextMatchPrice + _isRep[state2.Index].GetPrice1();
958
959 // for(; lenTest2 >= 2; lenTest2--)
960 {
961 UInt32 offset = lenTest + 1 + lenTest2;
962 while(lenEnd < cur + offset)
963 _optimum[++lenEnd].Price = kIfinityPrice;
964 UInt32 curAndLenPrice = nextRepMatchPrice + GetRepPrice(
965 0, lenTest2, state2, posStateNext);
966 COptimal &optimum = _optimum[cur + offset];
967 if (curAndLenPrice < optimum.Price)
968 {
969 optimum.Price = curAndLenPrice;
970 optimum.PosPrev = cur + lenTest + 1;
971 optimum.BackPrev = 0;
972 optimum.Prev1IsChar = true;
973 optimum.Prev2 = true;
974 optimum.PosPrev2 = cur;
975 optimum.BackPrev2 = repIndex;
976 }
977 }
978 }
979 }
980 */
981 }
982 }
983
984 // for(UInt32 lenTest = 2; lenTest <= newLen; lenTest++)
985 if (newLen > numAvailableBytes)
986 newLen = numAvailableBytes;
987 if (newLen >= 2)
988 {
989 if (newLen == 2 && _matchDistances[2] >= 0x80)
990 continue;
991 UInt32 normalMatchPrice = matchPrice +
992 _isRep[state.Index].GetPrice0();
993 while(lenEnd < cur + newLen)
994 _optimum[++lenEnd].Price = kIfinityPrice;
995
996 for(UInt32 lenTest = newLen; lenTest >= 2; lenTest--)
997 {
998 UInt32 curBack = _matchDistances[lenTest];
999 UInt32 curAndLenPrice = normalMatchPrice + GetPosLenPrice(curBack, lenTest, posState);
1000 COptimal &optimum = _optimum[cur + lenTest];
1001 if (curAndLenPrice < optimum.Price)
1002 {
1003 optimum.Price = curAndLenPrice;
1004 optimum.PosPrev = cur;
1005 optimum.BackPrev = curBack + kNumRepDistances;
1006 optimum.Prev1IsChar = false;
1007 }
1008
1009 if (_maxMode)
1010 {
1011 UInt32 backOffset = curBack + 1;
1012 UInt32 temp;
1013 for (temp = lenTest + 1; temp < numAvailableBytes; temp++)
1014 if (data[temp] != data[(size_t)temp - backOffset])
1015 break;
1016 UInt32 lenTest2 = temp - (lenTest + 1);
1017 if (lenTest2 >= 2)
1018 {
1019 CState state2 = state;
1020 state2.UpdateMatch();
1021 UInt32 posStateNext = (position + lenTest) & _posStateMask;
1022 UInt32 curAndLenCharPrice = curAndLenPrice +
1023 _isMatch[state2.Index][posStateNext].GetPrice0() +
1024 _literalEncoder.GetPrice(position + lenTest, data[(size_t)lenTest - 1],
1025 true, data[(size_t)lenTest - backOffset], data[lenTest]);
1026 state2.UpdateChar();
1027 posStateNext = (position + lenTest + 1) & _posStateMask;
1028 UInt32 nextMatchPrice = curAndLenCharPrice + _isMatch[state2.Index][posStateNext].GetPrice1();
1029 UInt32 nextRepMatchPrice = nextMatchPrice + _isRep[state2.Index].GetPrice1();
1030
1031 // for(; lenTest2 >= 2; lenTest2--)
1032 {
1033 UInt32 offset = lenTest + 1 + lenTest2;
1034 while(lenEnd < cur + offset)
1035 _optimum[++lenEnd].Price = kIfinityPrice;
1036 UInt32 curAndLenPrice = nextRepMatchPrice + GetRepPrice(
1037 0, lenTest2, state2, posStateNext);
1038 COptimal &optimum = _optimum[cur + offset];
1039 if (curAndLenPrice < optimum.Price)
1040 {
1041 optimum.Price = curAndLenPrice;
1042 optimum.PosPrev = cur + lenTest + 1;
1043 optimum.BackPrev = 0;
1044 optimum.Prev1IsChar = true;
1045 optimum.Prev2 = true;
1046 optimum.PosPrev2 = cur;
1047 optimum.BackPrev2 = curBack + kNumRepDistances;
1048 }
1049 }
1050 }
1051 }
1052 }
1053 }
1054 }
1055 }
1056
1057 static inline bool ChangePair(UInt32 smallDist, UInt32 bigDist)
1058 {
1059 const int kDif = 7;
1060 return (smallDist < (UInt32(1) << (32-kDif)) && bigDist >= (smallDist << kDif));
1061 }
1062
1063
1064 HRESULT CEncoder::ReadMatchDistances(UInt32 &lenRes)
1065 {
1066 lenRes = _matchFinder->GetLongestMatch(_matchDistances);
1067 if (lenRes == _numFastBytes)
1068 lenRes += _matchFinder->GetMatchLen(lenRes, _matchDistances[lenRes],
1069 kMatchMaxLen - lenRes);
1070 _additionalOffset++;
1071 return _matchFinder->MovePos();
1072 }
1073
1074 HRESULT CEncoder::GetOptimumFast(UInt32 position, UInt32 &backRes, UInt32 &lenRes)
1075 {
1076 UInt32 lenMain;
1077 if (!_longestMatchWasFound)
1078 {
1079 RINOK(ReadMatchDistances(lenMain));
1080 }
1081 else
1082 {
1083 lenMain = _longestMatchLength;
1084 _longestMatchWasFound = false;
1085 }
1086 UInt32 repLens[kNumRepDistances];
1087 UInt32 repMaxIndex = 0;
1088 for(UInt32 i = 0; i < kNumRepDistances; i++)
1089 {
1090 repLens[i] = _matchFinder->GetMatchLen(0 - 1, _repDistances[i], kMatchMaxLen);
1091 if (i == 0 || repLens[i] > repLens[repMaxIndex])
1092 repMaxIndex = i;
1093 }
1094 if(repLens[repMaxIndex] >= _numFastBytes)
1095 {
1096 backRes = repMaxIndex;
1097 lenRes = repLens[repMaxIndex];
1098 return MovePos(lenRes - 1);
1099 }
1100 if(lenMain >= _numFastBytes)
1101 {
1102 backRes = _matchDistances[_numFastBytes] + kNumRepDistances;
1103 lenRes = lenMain;
1104 return MovePos(lenMain - 1);
1105 }
1106 while (lenMain > 2)
1107 {
1108 if (!ChangePair(_matchDistances[lenMain - 1], _matchDistances[lenMain]))
1109 break;
1110 lenMain--;
1111 }
1112 if (lenMain == 2 && _matchDistances[2] >= 0x80)
1113 lenMain = 1;
1114
1115 UInt32 backMain = _matchDistances[lenMain];
1116 if (repLens[repMaxIndex] >= 2)
1117 {
1118 if (repLens[repMaxIndex] + 1 >= lenMain ||
1119 repLens[repMaxIndex] + 2 >= lenMain && (backMain > (1<<12)))
1120 {
1121 backRes = repMaxIndex;
1122 lenRes = repLens[repMaxIndex];
1123 return MovePos(lenRes - 1);
1124 }
1125 }
1126
1127
1128 if (lenMain >= 2)
1129 {
1130 RINOK(ReadMatchDistances(_longestMatchLength));
1131 if (_longestMatchLength >= 2 &&
1132 (
1133 (_longestMatchLength >= lenMain && _matchDistances[lenMain] < backMain) ||
1134 _longestMatchLength == lenMain + 1 &&
1135 !ChangePair(backMain, _matchDistances[_longestMatchLength]) ||
1136 _longestMatchLength > lenMain + 1 ||
1137 _longestMatchLength + 1 >= lenMain && lenMain >= 3 &&
1138 ChangePair(_matchDistances[lenMain - 1], backMain)
1139 )
1140 )
1141 {
1142 _longestMatchWasFound = true;
1143 backRes = UInt32(-1);
1144 lenRes = 1;
1145 return S_OK;
1146 }
1147 for(UInt32 i = 0; i < kNumRepDistances; i++)
1148 {
1149 UInt32 repLen = _matchFinder->GetMatchLen(0 - 1, _repDistances[i], kMatchMaxLen);
1150 if (repLen >= 2 && repLen + 1 >= lenMain)
1151 {
1152 _longestMatchWasFound = true;
1153 backRes = UInt32(-1);
1154 lenRes = 1;
1155 return S_OK;
1156 }
1157 }
1158 backRes = backMain + kNumRepDistances;
1159 lenRes = lenMain;
1160 return MovePos(lenMain - 2);
1161 }
1162 backRes = UInt32(-1);
1163 lenRes = 1;
1164 return S_OK;
1165 }
1166
1167 STDMETHODIMP CEncoder::InitMatchFinder(IMatchFinder *matchFinder)
1168 {
1169 _matchFinder = matchFinder;
1170 return S_OK;
1171 }
1172
1173 HRESULT CEncoder::Flush(UInt32 nowPos)
1174 {
1175 ReleaseMFStream();
1176 WriteEndMarker(nowPos & _posStateMask);
1177 _rangeEncoder.FlushData();
1178 return _rangeEncoder.FlushStream();
1179 }
1180
1181 void CEncoder::WriteEndMarker(UInt32 posState)
1182 {
1183 // This function for writing End Mark for stream version of LZMA.
1184 // In current version this feature is not used.
1185 if (!_writeEndMark)
1186 return;
1187
1188 _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 1);
1189 _isRep[_state.Index].Encode(&_rangeEncoder, 0);
1190 _state.UpdateMatch();
1191 UInt32 len = kMatchMinLen; // kMatchMaxLen;
1192 _lenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState);
1193 UInt32 posSlot = (1 << kNumPosSlotBits) - 1;
1194 UInt32 lenToPosState = GetLenToPosState(len);
1195 _posSlotEncoder[lenToPosState].Encode(&_rangeEncoder, posSlot);
1196 UInt32 footerBits = 30;
1197 UInt32 posReduced = (UInt32(1) << footerBits) - 1;
1198 _rangeEncoder.EncodeDirectBits(posReduced >> kNumAlignBits, footerBits - kNumAlignBits);
1199 _posAlignEncoder.ReverseEncode(&_rangeEncoder, posReduced & kAlignMask);
1200 }
1201
1202 HRESULT CEncoder::CodeReal(ISequentialInStream *inStream,
1203 ISequentialOutStream *outStream,
1204 const UInt64 *inSize, const UInt64 *outSize,
1205 ICompressProgressInfo *progress)
1206 {
1207 _needReleaseMFStream = false;
1208 CCoderReleaser coderReleaser(this);
1209 RINOK(SetStreams(inStream, outStream, inSize, outSize));
1210 while(true)
1211 {
1212 UInt64 processedInSize;
1213 UInt64 processedOutSize;
1214 Int32 finished;
1215 RINOK(CodeOneBlock(&processedInSize, &processedOutSize, &finished));
1216 if (finished != 0)
1217 return S_OK;
1218 if (progress != 0)
1219 {
1220 RINOK(progress->SetRatioInfo(&processedInSize, &processedOutSize));
1221 }
1222 }
1223 }
1224
1225 HRESULT CEncoder::SetStreams(ISequentialInStream *inStream,
1226 ISequentialOutStream *outStream,
1227 const UInt64 *inSize, const UInt64 *outSize)
1228 {
1229 _inStream = inStream;
1230 _finished = false;
1231 RINOK(Create());
1232 RINOK(SetOutStream(outStream));
1233 RINOK(Init());
1234
1235 // CCoderReleaser releaser(this);
1236
1237 /*
1238 if (_matchFinder->GetNumAvailableBytes() == 0)
1239 return Flush();
1240 */
1241
1242 if (!_fastMode)
1243 {
1244 FillPosSlotPrices();
1245 FillDistancesPrices();
1246 FillAlignPrices();
1247 }
1248
1249 _lenEncoder.SetTableSize(_numFastBytes);
1250 _lenEncoder.UpdateTables(1 << _posStateBits);
1251 _repMatchLenEncoder.SetTableSize(_numFastBytes);
1252 _repMatchLenEncoder.UpdateTables(1 << _posStateBits);
1253
1254 lastPosSlotFillingPos = 0;
1255 nowPos64 = 0;
1256 return S_OK;
1257 }
1258
1259 HRESULT CEncoder::CodeOneBlock(UInt64 *inSize, UInt64 *outSize, Int32 *finished)
1260 {
1261 if (_inStream != 0)
1262 {
1263 RINOK(_matchFinder->Init(_inStream));
1264 _needReleaseMFStream = true;
1265 _inStream = 0;
1266 }
1267
1268
1269 *finished = 1;
1270 if (_finished)
1271 return S_OK;
1272 _finished = true;
1273
1274
1275 UInt64 progressPosValuePrev = nowPos64;
1276 if (nowPos64 == 0)
1277 {
1278 if (_matchFinder->GetNumAvailableBytes() == 0)
1279 return Flush(UInt32(nowPos64));
1280 UInt32 len; // it's not used
1281 RINOK(ReadMatchDistances(len));
1282 UInt32 posState = UInt32(nowPos64) & _posStateMask;
1283 _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 0);
1284 _state.UpdateChar();
1285 Byte curByte = _matchFinder->GetIndexByte(0 - _additionalOffset);
1286 _literalEncoder.GetSubCoder(UInt32(nowPos64), _previousByte)->Encode(&_rangeEncoder, curByte);
1287 _previousByte = curByte;
1288 _additionalOffset--;
1289 nowPos64++;
1290 }
1291 if (_matchFinder->GetNumAvailableBytes() == 0)
1292 return Flush(UInt32(nowPos64));
1293 while(true)
1294 {
1295 #ifdef _NO_EXCEPTIONS
1296 if (_rangeEncoder.Stream.ErrorCode != S_OK)
1297 return _rangeEncoder.Stream.ErrorCode;
1298 #endif
1299 UInt32 pos;
1300 UInt32 posState = UInt32(nowPos64) & _posStateMask;
1301
1302 UInt32 len;
1303 HRESULT result;
1304 if (_fastMode)
1305 result = GetOptimumFast(UInt32(nowPos64), pos, len);
1306 else
1307 result = GetOptimum(UInt32(nowPos64), pos, len);
1308 RINOK(result);
1309
1310 if(len == 1 && pos == 0xFFFFFFFF)
1311 {
1312 _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 0);
1313 Byte curByte = _matchFinder->GetIndexByte(0 - _additionalOffset);
1314 CLiteralEncoder2 *subCoder = _literalEncoder.GetSubCoder(UInt32(nowPos64), _previousByte);
1315 if(!_state.IsCharState())
1316 {
1317 Byte matchByte = _matchFinder->GetIndexByte(0 - _repDistances[0] - 1 - _additionalOffset);
1318 subCoder->EncodeMatched(&_rangeEncoder, matchByte, curByte);
1319 }
1320 else
1321 subCoder->Encode(&_rangeEncoder, curByte);
1322 _state.UpdateChar();
1323 _previousByte = curByte;
1324 }
1325 else
1326 {
1327 _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 1);
1328 if(pos < kNumRepDistances)
1329 {
1330 _isRep[_state.Index].Encode(&_rangeEncoder, 1);
1331 if(pos == 0)
1332 {
1333 _isRepG0[_state.Index].Encode(&_rangeEncoder, 0);
1334 if(len == 1)
1335 _isRep0Long[_state.Index][posState].Encode(&_rangeEncoder, 0);
1336 else
1337 _isRep0Long[_state.Index][posState].Encode(&_rangeEncoder, 1);
1338 }
1339 else
1340 {
1341 _isRepG0[_state.Index].Encode(&_rangeEncoder, 1);
1342 if (pos == 1)
1343 _isRepG1[_state.Index].Encode(&_rangeEncoder, 0);
1344 else
1345 {
1346 _isRepG1[_state.Index].Encode(&_rangeEncoder, 1);
1347 _isRepG2[_state.Index].Encode(&_rangeEncoder, pos - 2);
1348 }
1349 }
1350 if (len == 1)
1351 _state.UpdateShortRep();
1352 else
1353 {
1354 _repMatchLenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState);
1355 _state.UpdateRep();
1356 }
1357
1358
1359 UInt32 distance = _repDistances[pos];
1360 if (pos != 0)
1361 {
1362 for(UInt32 i = pos; i >= 1; i--)
1363 _repDistances[i] = _repDistances[i - 1];
1364 _repDistances[0] = distance;
1365 }
1366 }
1367 else
1368 {
1369 _isRep[_state.Index].Encode(&_rangeEncoder, 0);
1370 _state.UpdateMatch();
1371 _lenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState);
1372 pos -= kNumRepDistances;
1373 UInt32 posSlot = GetPosSlot(pos);
1374 UInt32 lenToPosState = GetLenToPosState(len);
1375 _posSlotEncoder[lenToPosState].Encode(&_rangeEncoder, posSlot);
1376
1377 if (posSlot >= kStartPosModelIndex)
1378 {
1379 UInt32 footerBits = ((posSlot >> 1) - 1);
1380 UInt32 base = ((2 | (posSlot & 1)) << footerBits);
1381 UInt32 posReduced = pos - base;
1382
1383 if (posSlot < kEndPosModelIndex)
1384 NRangeCoder::ReverseBitTreeEncode(_posEncoders + base - posSlot - 1,
1385 &_rangeEncoder, footerBits, posReduced);
1386 else
1387 {
1388 _rangeEncoder.EncodeDirectBits(posReduced >> kNumAlignBits, footerBits - kNumAlignBits);
1389 _posAlignEncoder.ReverseEncode(&_rangeEncoder, posReduced & kAlignMask);
1390 if (!_fastMode)
1391 if (--_alignPriceCount == 0)
1392 FillAlignPrices();
1393 }
1394 }
1395 UInt32 distance = pos;
1396 for(UInt32 i = kNumRepDistances - 1; i >= 1; i--)
1397 _repDistances[i] = _repDistances[i - 1];
1398 _repDistances[0] = distance;
1399 }
1400 _previousByte = _matchFinder->GetIndexByte(len - 1 - _additionalOffset);
1401 }
1402 _additionalOffset -= len;
1403 nowPos64 += len;
1404 if (!_fastMode)
1405 if (nowPos64 - lastPosSlotFillingPos >= (1 << 9))
1406 {
1407 FillPosSlotPrices();
1408 FillDistancesPrices();
1409 lastPosSlotFillingPos = nowPos64;
1410 }
1411 if (_additionalOffset == 0)
1412 {
1413 *inSize = nowPos64;
1414 *outSize = _rangeEncoder.GetProcessedSize();
1415 if (_matchFinder->GetNumAvailableBytes() == 0)
1416 return Flush(UInt32(nowPos64));
1417 if (nowPos64 - progressPosValuePrev >= (1 << 12))
1418 {
1419 _finished = false;
1420 *finished = 0;
1421 return S_OK;
1422 }
1423 }
1424 }
1425 }
1426
1427 STDMETHODIMP CEncoder::Code(ISequentialInStream *inStream,
1428 ISequentialOutStream *outStream, const UInt64 *inSize, const UInt64 *outSize,
1429 ICompressProgressInfo *progress)
1430 {
1431 #ifndef _NO_EXCEPTIONS
1432 try
1433 {
1434 #endif
1435 return CodeReal(inStream, outStream, inSize, outSize, progress);
1436 #ifndef _NO_EXCEPTIONS
1437 }
1438 catch(const COutBufferException &e) { return e.ErrorCode; }
1439 catch(...) { return E_FAIL; }
1440 #endif
1441 }
1442
1443 void CEncoder::FillPosSlotPrices()
1444 {
1445 for (UInt32 lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++)
1446 {
1447 UInt32 posSlot;
1448 for (posSlot = 0; posSlot < kEndPosModelIndex && posSlot < _distTableSize; posSlot++)
1449 _posSlotPrices[lenToPosState][posSlot] = _posSlotEncoder[lenToPosState].GetPrice(posSlot);
1450 for (; posSlot < _distTableSize; posSlot++)
1451 _posSlotPrices[lenToPosState][posSlot] = _posSlotEncoder[lenToPosState].GetPrice(posSlot) +
1452 ((((posSlot >> 1) - 1) - kNumAlignBits) << NRangeCoder::kNumBitPriceShiftBits);
1453 }
1454 }
1455
1456 void CEncoder::FillDistancesPrices()
1457 {
1458 for (UInt32 lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++)
1459 {
1460 UInt32 i;
1461 for (i = 0; i < kStartPosModelIndex; i++)
1462 _distancesPrices[lenToPosState][i] = _posSlotPrices[lenToPosState][i];
1463 for (; i < kNumFullDistances; i++)
1464 {
1465 UInt32 posSlot = GetPosSlot(i);
1466 UInt32 footerBits = ((posSlot >> 1) - 1);
1467 UInt32 base = ((2 | (posSlot & 1)) << footerBits);
1468
1469 _distancesPrices[lenToPosState][i] = _posSlotPrices[lenToPosState][posSlot] +
1470 NRangeCoder::ReverseBitTreeGetPrice(_posEncoders +
1471 base - posSlot - 1, footerBits, i - base);
1472
1473 }
1474 }
1475 }
1476
1477 void CEncoder::FillAlignPrices()
1478 {
1479 for (UInt32 i = 0; i < kAlignTableSize; i++)
1480 _alignPrices[i] = _posAlignEncoder.ReverseGetPrice(i);
1481 _alignPriceCount = kAlignTableSize;
1482 }
1483
1484 }}