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