1 /* LzmaEnc.c -- LZMA Encoder 2 2018-12-29: Igor Pavlov : Public domain */ 3 4 #include "Precomp.h" 5 6 #include <string.h> 7 8 /* #define SHOW_STAT */ 9 /* #define SHOW_STAT2 */ 10 11 #if defined(SHOW_STAT) || defined(SHOW_STAT2) 12 #include <stdio.h> 13 #endif 14 15 #include "LzmaEnc.h" 16 17 #include "LzFind.h" 18 #ifndef _7ZIP_ST 19 #include "LzFindMt.h" 20 #endif 21 22 #ifdef SHOW_STAT 23 static unsigned g_STAT_OFFSET = 0; 24 #endif 25 26 #define kLzmaMaxHistorySize ((UInt32)3 << 29) 27 /* #define kLzmaMaxHistorySize ((UInt32)7 << 29) */ 28 29 #define kNumTopBits 24 30 #define kTopValue ((UInt32)1 << kNumTopBits) 31 32 #define kNumBitModelTotalBits 11 33 #define kBitModelTotal (1 << kNumBitModelTotalBits) 34 #define kNumMoveBits 5 35 #define kProbInitValue (kBitModelTotal >> 1) 36 37 #define kNumMoveReducingBits 4 38 #define kNumBitPriceShiftBits 4 39 #define kBitPrice (1 << kNumBitPriceShiftBits) 40 41 #define REP_LEN_COUNT 64 42 43 void LzmaEncProps_Init(CLzmaEncProps *p) 44 { 45 p->level = 5; 46 p->dictSize = p->mc = 0; 47 p->reduceSize = (UInt64)(Int64)-1; 48 p->lc = p->lp = p->pb = p->algo = p->fb = p->btMode = p->numHashBytes = p->numThreads = -1; 49 p->writeEndMark = 0; 50 } 51 52 void LzmaEncProps_Normalize(CLzmaEncProps *p) 53 { 54 int level = p->level; 55 if (level < 0) level = 5; 56 p->level = level; 57 58 if (p->dictSize == 0) p->dictSize = (level <= 5 ? (1 << (level * 2 + 14)) : (level <= 7 ? (1 << 25) : (1 << 26))); 59 if (p->dictSize > p->reduceSize) 60 { 61 unsigned i; 62 UInt32 reduceSize = (UInt32)p->reduceSize; 63 for (i = 11; i <= 30; i++) 64 { 65 if (reduceSize <= ((UInt32)2 << i)) { p->dictSize = ((UInt32)2 << i); break; } 66 if (reduceSize <= ((UInt32)3 << i)) { p->dictSize = ((UInt32)3 << i); break; } 67 } 68 } 69 70 if (p->lc < 0) p->lc = 3; 71 if (p->lp < 0) p->lp = 0; 72 if (p->pb < 0) p->pb = 2; 73 74 if (p->algo < 0) p->algo = (level < 5 ? 0 : 1); 75 if (p->fb < 0) p->fb = (level < 7 ? 32 : 64); 76 if (p->btMode < 0) p->btMode = (p->algo == 0 ? 0 : 1); 77 if (p->numHashBytes < 0) p->numHashBytes = 4; 78 if (p->mc == 0) p->mc = (16 + (p->fb >> 1)) >> (p->btMode ? 0 : 1); 79 80 if (p->numThreads < 0) 81 p->numThreads = 82 #ifndef _7ZIP_ST 83 ((p->btMode && p->algo) ? 2 : 1); 84 #else 85 1; 86 #endif 87 } 88 89 UInt32 LzmaEncProps_GetDictSize(const CLzmaEncProps *props2) 90 { 91 CLzmaEncProps props = *props2; 92 LzmaEncProps_Normalize(&props); 93 return props.dictSize; 94 } 95 96 #if (_MSC_VER >= 1400) 97 /* BSR code is fast for some new CPUs */ 98 /* #define LZMA_LOG_BSR */ 99 #endif 100 101 #ifdef LZMA_LOG_BSR 102 103 #define kDicLogSizeMaxCompress 32 104 105 #define BSR2_RET(pos, res) { unsigned long zz; _BitScanReverse(&zz, (pos)); res = (zz + zz) + ((pos >> (zz - 1)) & 1); } 106 107 static unsigned GetPosSlot1(UInt32 pos) 108 { 109 unsigned res; 110 BSR2_RET(pos, res); 111 return res; 112 } 113 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); } 114 #define GetPosSlot(pos, res) { if (pos < 2) res = pos; else BSR2_RET(pos, res); } 115 116 #else 117 118 #define kNumLogBits (9 + sizeof(size_t) / 2) 119 /* #define kNumLogBits (11 + sizeof(size_t) / 8 * 3) */ 120 121 #define kDicLogSizeMaxCompress ((kNumLogBits - 1) * 2 + 7) 122 123 static void LzmaEnc_FastPosInit(Byte *g_FastPos) 124 { 125 unsigned slot; 126 g_FastPos[0] = 0; 127 g_FastPos[1] = 1; 128 g_FastPos += 2; 129 130 for (slot = 2; slot < kNumLogBits * 2; slot++) 131 { 132 size_t k = ((size_t)1 << ((slot >> 1) - 1)); 133 size_t j; 134 for (j = 0; j < k; j++) 135 g_FastPos[j] = (Byte)slot; 136 g_FastPos += k; 137 } 138 } 139 140 /* we can use ((limit - pos) >> 31) only if (pos < ((UInt32)1 << 31)) */ 141 /* 142 #define BSR2_RET(pos, res) { unsigned zz = 6 + ((kNumLogBits - 1) & \ 143 (0 - (((((UInt32)1 << (kNumLogBits + 6)) - 1) - pos) >> 31))); \ 144 res = p->g_FastPos[pos >> zz] + (zz * 2); } 145 */ 146 147 /* 148 #define BSR2_RET(pos, res) { unsigned zz = 6 + ((kNumLogBits - 1) & \ 149 (0 - (((((UInt32)1 << (kNumLogBits)) - 1) - (pos >> 6)) >> 31))); \ 150 res = p->g_FastPos[pos >> zz] + (zz * 2); } 151 */ 152 153 #define BSR2_RET(pos, res) { unsigned zz = (pos < (1 << (kNumLogBits + 6))) ? 6 : 6 + kNumLogBits - 1; \ 154 res = p->g_FastPos[pos >> zz] + (zz * 2); } 155 156 /* 157 #define BSR2_RET(pos, res) { res = (pos < (1 << (kNumLogBits + 6))) ? \ 158 p->g_FastPos[pos >> 6] + 12 : \ 159 p->g_FastPos[pos >> (6 + kNumLogBits - 1)] + (6 + (kNumLogBits - 1)) * 2; } 160 */ 161 162 #define GetPosSlot1(pos) p->g_FastPos[pos] 163 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); } 164 #define GetPosSlot(pos, res) { if (pos < kNumFullDistances) res = p->g_FastPos[pos & (kNumFullDistances - 1)]; else BSR2_RET(pos, res); } 165 166 #endif 167 168 169 #define LZMA_NUM_REPS 4 170 171 typedef UInt16 CState; 172 typedef UInt16 CExtra; 173 174 typedef struct 175 { 176 UInt32 price; 177 CState state; 178 CExtra extra; 179 // 0 : normal 180 // 1 : LIT : MATCH 181 // > 1 : MATCH (extra-1) : LIT : REP0 (len) 182 UInt32 len; 183 UInt32 dist; 184 UInt32 reps[LZMA_NUM_REPS]; 185 } COptimal; 186 187 188 // 18.06 189 #define kNumOpts (1 << 11) 190 #define kPackReserve (kNumOpts * 8) 191 // #define kNumOpts (1 << 12) 192 // #define kPackReserve (1 + kNumOpts * 2) 193 194 #define kNumLenToPosStates 4 195 #define kNumPosSlotBits 6 196 #define kDicLogSizeMin 0 197 #define kDicLogSizeMax 32 198 #define kDistTableSizeMax (kDicLogSizeMax * 2) 199 200 #define kNumAlignBits 4 201 #define kAlignTableSize (1 << kNumAlignBits) 202 #define kAlignMask (kAlignTableSize - 1) 203 204 #define kStartPosModelIndex 4 205 #define kEndPosModelIndex 14 206 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1)) 207 208 typedef 209 #ifdef _LZMA_PROB32 210 UInt32 211 #else 212 UInt16 213 #endif 214 CLzmaProb; 215 216 #define LZMA_PB_MAX 4 217 #define LZMA_LC_MAX 8 218 #define LZMA_LP_MAX 4 219 220 #define LZMA_NUM_PB_STATES_MAX (1 << LZMA_PB_MAX) 221 222 #define kLenNumLowBits 3 223 #define kLenNumLowSymbols (1 << kLenNumLowBits) 224 #define kLenNumHighBits 8 225 #define kLenNumHighSymbols (1 << kLenNumHighBits) 226 #define kLenNumSymbolsTotal (kLenNumLowSymbols * 2 + kLenNumHighSymbols) 227 228 #define LZMA_MATCH_LEN_MIN 2 229 #define LZMA_MATCH_LEN_MAX (LZMA_MATCH_LEN_MIN + kLenNumSymbolsTotal - 1) 230 231 #define kNumStates 12 232 233 234 typedef struct 235 { 236 CLzmaProb low[LZMA_NUM_PB_STATES_MAX << (kLenNumLowBits + 1)]; 237 CLzmaProb high[kLenNumHighSymbols]; 238 } CLenEnc; 239 240 241 typedef struct 242 { 243 unsigned tableSize; 244 UInt32 prices[LZMA_NUM_PB_STATES_MAX][kLenNumSymbolsTotal]; 245 // UInt32 prices1[LZMA_NUM_PB_STATES_MAX][kLenNumLowSymbols * 2]; 246 // UInt32 prices2[kLenNumSymbolsTotal]; 247 } CLenPriceEnc; 248 249 #define GET_PRICE_LEN(p, posState, len) \ 250 ((p)->prices[posState][(size_t)(len) - LZMA_MATCH_LEN_MIN]) 251 252 /* 253 #define GET_PRICE_LEN(p, posState, len) \ 254 ((p)->prices2[(size_t)(len) - 2] + ((p)->prices1[posState][((len) - 2) & (kLenNumLowSymbols * 2 - 1)] & (((len) - 2 - kLenNumLowSymbols * 2) >> 9))) 255 */ 256 257 typedef struct 258 { 259 UInt32 range; 260 unsigned cache; 261 UInt64 low; 262 UInt64 cacheSize; 263 Byte *buf; 264 Byte *bufLim; 265 Byte *bufBase; 266 ISeqOutStream *outStream; 267 UInt64 processed; 268 SRes res; 269 } CRangeEnc; 270 271 272 typedef struct 273 { 274 CLzmaProb *litProbs; 275 276 unsigned state; 277 UInt32 reps[LZMA_NUM_REPS]; 278 279 CLzmaProb posAlignEncoder[1 << kNumAlignBits]; 280 CLzmaProb isRep[kNumStates]; 281 CLzmaProb isRepG0[kNumStates]; 282 CLzmaProb isRepG1[kNumStates]; 283 CLzmaProb isRepG2[kNumStates]; 284 CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX]; 285 CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX]; 286 287 CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits]; 288 CLzmaProb posEncoders[kNumFullDistances]; 289 290 CLenEnc lenProbs; 291 CLenEnc repLenProbs; 292 293 } CSaveState; 294 295 296 typedef UInt32 CProbPrice; 297 298 299 typedef struct 300 { 301 void *matchFinderObj; 302 IMatchFinder matchFinder; 303 304 unsigned optCur; 305 unsigned optEnd; 306 307 unsigned longestMatchLen; 308 unsigned numPairs; 309 UInt32 numAvail; 310 311 unsigned state; 312 unsigned numFastBytes; 313 unsigned additionalOffset; 314 UInt32 reps[LZMA_NUM_REPS]; 315 unsigned lpMask, pbMask; 316 CLzmaProb *litProbs; 317 CRangeEnc rc; 318 319 UInt32 backRes; 320 321 unsigned lc, lp, pb; 322 unsigned lclp; 323 324 BoolInt fastMode; 325 BoolInt writeEndMark; 326 BoolInt finished; 327 BoolInt multiThread; 328 BoolInt needInit; 329 // BoolInt _maxMode; 330 331 UInt64 nowPos64; 332 333 unsigned matchPriceCount; 334 // unsigned alignPriceCount; 335 int repLenEncCounter; 336 337 unsigned distTableSize; 338 339 UInt32 dictSize; 340 SRes result; 341 342 #ifndef _7ZIP_ST 343 BoolInt mtMode; 344 // begin of CMatchFinderMt is used in LZ thread 345 CMatchFinderMt matchFinderMt; 346 // end of CMatchFinderMt is used in BT and HASH threads 347 #endif 348 349 CMatchFinder matchFinderBase; 350 351 #ifndef _7ZIP_ST 352 Byte pad[128]; 353 #endif 354 355 // LZ thread 356 CProbPrice ProbPrices[kBitModelTotal >> kNumMoveReducingBits]; 357 358 UInt32 matches[LZMA_MATCH_LEN_MAX * 2 + 2 + 1]; 359 360 UInt32 alignPrices[kAlignTableSize]; 361 UInt32 posSlotPrices[kNumLenToPosStates][kDistTableSizeMax]; 362 UInt32 distancesPrices[kNumLenToPosStates][kNumFullDistances]; 363 364 CLzmaProb posAlignEncoder[1 << kNumAlignBits]; 365 CLzmaProb isRep[kNumStates]; 366 CLzmaProb isRepG0[kNumStates]; 367 CLzmaProb isRepG1[kNumStates]; 368 CLzmaProb isRepG2[kNumStates]; 369 CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX]; 370 CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX]; 371 CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits]; 372 CLzmaProb posEncoders[kNumFullDistances]; 373 374 CLenEnc lenProbs; 375 CLenEnc repLenProbs; 376 377 #ifndef LZMA_LOG_BSR 378 Byte g_FastPos[1 << kNumLogBits]; 379 #endif 380 381 CLenPriceEnc lenEnc; 382 CLenPriceEnc repLenEnc; 383 384 COptimal opt[kNumOpts]; 385 386 CSaveState saveState; 387 388 #ifndef _7ZIP_ST 389 Byte pad2[128]; 390 #endif 391 } CLzmaEnc; 392 393 394 395 #define COPY_ARR(dest, src, arr) memcpy(dest->arr, src->arr, sizeof(src->arr)); 396 397 void LzmaEnc_SaveState(CLzmaEncHandle pp) 398 { 399 CLzmaEnc *p = (CLzmaEnc *)pp; 400 CSaveState *dest = &p->saveState; 401 402 dest->state = p->state; 403 404 dest->lenProbs = p->lenProbs; 405 dest->repLenProbs = p->repLenProbs; 406 407 COPY_ARR(dest, p, reps); 408 409 COPY_ARR(dest, p, posAlignEncoder); 410 COPY_ARR(dest, p, isRep); 411 COPY_ARR(dest, p, isRepG0); 412 COPY_ARR(dest, p, isRepG1); 413 COPY_ARR(dest, p, isRepG2); 414 COPY_ARR(dest, p, isMatch); 415 COPY_ARR(dest, p, isRep0Long); 416 COPY_ARR(dest, p, posSlotEncoder); 417 COPY_ARR(dest, p, posEncoders); 418 419 memcpy(dest->litProbs, p->litProbs, ((UInt32)0x300 << p->lclp) * sizeof(CLzmaProb)); 420 } 421 422 423 void LzmaEnc_RestoreState(CLzmaEncHandle pp) 424 { 425 CLzmaEnc *dest = (CLzmaEnc *)pp; 426 const CSaveState *p = &dest->saveState; 427 428 dest->state = p->state; 429 430 dest->lenProbs = p->lenProbs; 431 dest->repLenProbs = p->repLenProbs; 432 433 COPY_ARR(dest, p, reps); 434 435 COPY_ARR(dest, p, posAlignEncoder); 436 COPY_ARR(dest, p, isRep); 437 COPY_ARR(dest, p, isRepG0); 438 COPY_ARR(dest, p, isRepG1); 439 COPY_ARR(dest, p, isRepG2); 440 COPY_ARR(dest, p, isMatch); 441 COPY_ARR(dest, p, isRep0Long); 442 COPY_ARR(dest, p, posSlotEncoder); 443 COPY_ARR(dest, p, posEncoders); 444 445 memcpy(dest->litProbs, p->litProbs, ((UInt32)0x300 << dest->lclp) * sizeof(CLzmaProb)); 446 } 447 448 449 450 SRes LzmaEnc_SetProps(CLzmaEncHandle pp, const CLzmaEncProps *props2) 451 { 452 CLzmaEnc *p = (CLzmaEnc *)pp; 453 CLzmaEncProps props = *props2; 454 LzmaEncProps_Normalize(&props); 455 456 if (props.lc > LZMA_LC_MAX 457 || props.lp > LZMA_LP_MAX 458 || props.pb > LZMA_PB_MAX 459 || props.dictSize > ((UInt64)1 << kDicLogSizeMaxCompress) 460 || props.dictSize > kLzmaMaxHistorySize) 461 return SZ_ERROR_PARAM; 462 463 p->dictSize = props.dictSize; 464 { 465 unsigned fb = props.fb; 466 if (fb < 5) 467 fb = 5; 468 if (fb > LZMA_MATCH_LEN_MAX) 469 fb = LZMA_MATCH_LEN_MAX; 470 p->numFastBytes = fb; 471 } 472 p->lc = props.lc; 473 p->lp = props.lp; 474 p->pb = props.pb; 475 p->fastMode = (props.algo == 0); 476 // p->_maxMode = True; 477 p->matchFinderBase.btMode = (Byte)(props.btMode ? 1 : 0); 478 { 479 unsigned numHashBytes = 4; 480 if (props.btMode) 481 { 482 if (props.numHashBytes < 2) 483 numHashBytes = 2; 484 else if (props.numHashBytes < 4) 485 numHashBytes = props.numHashBytes; 486 } 487 p->matchFinderBase.numHashBytes = numHashBytes; 488 } 489 490 p->matchFinderBase.cutValue = props.mc; 491 492 p->writeEndMark = props.writeEndMark; 493 494 #ifndef _7ZIP_ST 495 /* 496 if (newMultiThread != _multiThread) 497 { 498 ReleaseMatchFinder(); 499 _multiThread = newMultiThread; 500 } 501 */ 502 p->multiThread = (props.numThreads > 1); 503 #endif 504 505 return SZ_OK; 506 } 507 508 509 void LzmaEnc_SetDataSize(CLzmaEncHandle pp, UInt64 expectedDataSiize) 510 { 511 CLzmaEnc *p = (CLzmaEnc *)pp; 512 p->matchFinderBase.expectedDataSize = expectedDataSiize; 513 } 514 515 516 #define kState_Start 0 517 #define kState_LitAfterMatch 4 518 #define kState_LitAfterRep 5 519 #define kState_MatchAfterLit 7 520 #define kState_RepAfterLit 8 521 522 static const Byte kLiteralNextStates[kNumStates] = {0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5}; 523 static const Byte kMatchNextStates[kNumStates] = {7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10}; 524 static const Byte kRepNextStates[kNumStates] = {8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11}; 525 static const Byte kShortRepNextStates[kNumStates]= {9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11}; 526 527 #define IsLitState(s) ((s) < 7) 528 #define GetLenToPosState2(len) (((len) < kNumLenToPosStates - 1) ? (len) : kNumLenToPosStates - 1) 529 #define GetLenToPosState(len) (((len) < kNumLenToPosStates + 1) ? (len) - 2 : kNumLenToPosStates - 1) 530 531 #define kInfinityPrice (1 << 30) 532 533 static void RangeEnc_Construct(CRangeEnc *p) 534 { 535 p->outStream = NULL; 536 p->bufBase = NULL; 537 } 538 539 #define RangeEnc_GetProcessed(p) ((p)->processed + ((p)->buf - (p)->bufBase) + (p)->cacheSize) 540 #define RangeEnc_GetProcessed_sizet(p) ((size_t)(p)->processed + ((p)->buf - (p)->bufBase) + (size_t)(p)->cacheSize) 541 542 #define RC_BUF_SIZE (1 << 16) 543 544 static int RangeEnc_Alloc(CRangeEnc *p, ISzAllocPtr alloc) 545 { 546 if (!p->bufBase) 547 { 548 p->bufBase = (Byte *)ISzAlloc_Alloc(alloc, RC_BUF_SIZE); 549 if (!p->bufBase) 550 return 0; 551 p->bufLim = p->bufBase + RC_BUF_SIZE; 552 } 553 return 1; 554 } 555 556 static void RangeEnc_Free(CRangeEnc *p, ISzAllocPtr alloc) 557 { 558 ISzAlloc_Free(alloc, p->bufBase); 559 p->bufBase = 0; 560 } 561 562 static void RangeEnc_Init(CRangeEnc *p) 563 { 564 /* Stream.Init(); */ 565 p->range = 0xFFFFFFFF; 566 p->cache = 0; 567 p->low = 0; 568 p->cacheSize = 0; 569 570 p->buf = p->bufBase; 571 572 p->processed = 0; 573 p->res = SZ_OK; 574 } 575 576 MY_NO_INLINE static void RangeEnc_FlushStream(CRangeEnc *p) 577 { 578 size_t num; 579 if (p->res != SZ_OK) 580 return; 581 num = p->buf - p->bufBase; 582 if (num != ISeqOutStream_Write(p->outStream, p->bufBase, num)) 583 p->res = SZ_ERROR_WRITE; 584 p->processed += num; 585 p->buf = p->bufBase; 586 } 587 588 MY_NO_INLINE static void MY_FAST_CALL RangeEnc_ShiftLow(CRangeEnc *p) 589 { 590 UInt32 low = (UInt32)p->low; 591 unsigned high = (unsigned)(p->low >> 32); 592 p->low = (UInt32)(low << 8); 593 if (low < (UInt32)0xFF000000 || high != 0) 594 { 595 { 596 Byte *buf = p->buf; 597 *buf++ = (Byte)(p->cache + high); 598 p->cache = (unsigned)(low >> 24); 599 p->buf = buf; 600 if (buf == p->bufLim) 601 RangeEnc_FlushStream(p); 602 if (p->cacheSize == 0) 603 return; 604 } 605 high += 0xFF; 606 for (;;) 607 { 608 Byte *buf = p->buf; 609 *buf++ = (Byte)(high); 610 p->buf = buf; 611 if (buf == p->bufLim) 612 RangeEnc_FlushStream(p); 613 if (--p->cacheSize == 0) 614 return; 615 } 616 } 617 p->cacheSize++; 618 } 619 620 static void RangeEnc_FlushData(CRangeEnc *p) 621 { 622 int i; 623 for (i = 0; i < 5; i++) 624 RangeEnc_ShiftLow(p); 625 } 626 627 #define RC_NORM(p) if (range < kTopValue) { range <<= 8; RangeEnc_ShiftLow(p); } 628 629 #define RC_BIT_PRE(p, prob) \ 630 ttt = *(prob); \ 631 newBound = (range >> kNumBitModelTotalBits) * ttt; 632 633 // #define _LZMA_ENC_USE_BRANCH 634 635 #ifdef _LZMA_ENC_USE_BRANCH 636 637 #define RC_BIT(p, prob, bit) { \ 638 RC_BIT_PRE(p, prob) \ 639 if (bit == 0) { range = newBound; ttt += (kBitModelTotal - ttt) >> kNumMoveBits; } \ 640 else { (p)->low += newBound; range -= newBound; ttt -= ttt >> kNumMoveBits; } \ 641 *(prob) = (CLzmaProb)ttt; \ 642 RC_NORM(p) \ 643 } 644 645 #else 646 647 #define RC_BIT(p, prob, bit) { \ 648 UInt32 mask; \ 649 RC_BIT_PRE(p, prob) \ 650 mask = 0 - (UInt32)bit; \ 651 range &= mask; \ 652 mask &= newBound; \ 653 range -= mask; \ 654 (p)->low += mask; \ 655 mask = (UInt32)bit - 1; \ 656 range += newBound & mask; \ 657 mask &= (kBitModelTotal - ((1 << kNumMoveBits) - 1)); \ 658 mask += ((1 << kNumMoveBits) - 1); \ 659 ttt += (Int32)(mask - ttt) >> kNumMoveBits; \ 660 *(prob) = (CLzmaProb)ttt; \ 661 RC_NORM(p) \ 662 } 663 664 #endif 665 666 667 668 669 #define RC_BIT_0_BASE(p, prob) \ 670 range = newBound; *(prob) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits)); 671 672 #define RC_BIT_1_BASE(p, prob) \ 673 range -= newBound; (p)->low += newBound; *(prob) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits)); \ 674 675 #define RC_BIT_0(p, prob) \ 676 RC_BIT_0_BASE(p, prob) \ 677 RC_NORM(p) 678 679 #define RC_BIT_1(p, prob) \ 680 RC_BIT_1_BASE(p, prob) \ 681 RC_NORM(p) 682 683 static void RangeEnc_EncodeBit_0(CRangeEnc *p, CLzmaProb *prob) 684 { 685 UInt32 range, ttt, newBound; 686 range = p->range; 687 RC_BIT_PRE(p, prob) 688 RC_BIT_0(p, prob) 689 p->range = range; 690 } 691 692 static void LitEnc_Encode(CRangeEnc *p, CLzmaProb *probs, UInt32 sym) 693 { 694 UInt32 range = p->range; 695 sym |= 0x100; 696 do 697 { 698 UInt32 ttt, newBound; 699 // RangeEnc_EncodeBit(p, probs + (sym >> 8), (sym >> 7) & 1); 700 CLzmaProb *prob = probs + (sym >> 8); 701 UInt32 bit = (sym >> 7) & 1; 702 sym <<= 1; 703 RC_BIT(p, prob, bit); 704 } 705 while (sym < 0x10000); 706 p->range = range; 707 } 708 709 static void LitEnc_EncodeMatched(CRangeEnc *p, CLzmaProb *probs, UInt32 sym, UInt32 matchByte) 710 { 711 UInt32 range = p->range; 712 UInt32 offs = 0x100; 713 sym |= 0x100; 714 do 715 { 716 UInt32 ttt, newBound; 717 CLzmaProb *prob; 718 UInt32 bit; 719 matchByte <<= 1; 720 // RangeEnc_EncodeBit(p, probs + (offs + (matchByte & offs) + (sym >> 8)), (sym >> 7) & 1); 721 prob = probs + (offs + (matchByte & offs) + (sym >> 8)); 722 bit = (sym >> 7) & 1; 723 sym <<= 1; 724 offs &= ~(matchByte ^ sym); 725 RC_BIT(p, prob, bit); 726 } 727 while (sym < 0x10000); 728 p->range = range; 729 } 730 731 732 733 static void LzmaEnc_InitPriceTables(CProbPrice *ProbPrices) 734 { 735 UInt32 i; 736 for (i = 0; i < (kBitModelTotal >> kNumMoveReducingBits); i++) 737 { 738 const unsigned kCyclesBits = kNumBitPriceShiftBits; 739 UInt32 w = (i << kNumMoveReducingBits) + (1 << (kNumMoveReducingBits - 1)); 740 unsigned bitCount = 0; 741 unsigned j; 742 for (j = 0; j < kCyclesBits; j++) 743 { 744 w = w * w; 745 bitCount <<= 1; 746 while (w >= ((UInt32)1 << 16)) 747 { 748 w >>= 1; 749 bitCount++; 750 } 751 } 752 ProbPrices[i] = (CProbPrice)((kNumBitModelTotalBits << kCyclesBits) - 15 - bitCount); 753 // printf("\n%3d: %5d", i, ProbPrices[i]); 754 } 755 } 756 757 758 #define GET_PRICE(prob, bit) \ 759 p->ProbPrices[((prob) ^ (unsigned)(((-(int)(bit))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits]; 760 761 #define GET_PRICEa(prob, bit) \ 762 ProbPrices[((prob) ^ (unsigned)((-((int)(bit))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits]; 763 764 #define GET_PRICE_0(prob) p->ProbPrices[(prob) >> kNumMoveReducingBits] 765 #define GET_PRICE_1(prob) p->ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits] 766 767 #define GET_PRICEa_0(prob) ProbPrices[(prob) >> kNumMoveReducingBits] 768 #define GET_PRICEa_1(prob) ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits] 769 770 771 static UInt32 LitEnc_GetPrice(const CLzmaProb *probs, UInt32 sym, const CProbPrice *ProbPrices) 772 { 773 UInt32 price = 0; 774 sym |= 0x100; 775 do 776 { 777 unsigned bit = sym & 1; 778 sym >>= 1; 779 price += GET_PRICEa(probs[sym], bit); 780 } 781 while (sym >= 2); 782 return price; 783 } 784 785 786 static UInt32 LitEnc_Matched_GetPrice(const CLzmaProb *probs, UInt32 sym, UInt32 matchByte, const CProbPrice *ProbPrices) 787 { 788 UInt32 price = 0; 789 UInt32 offs = 0x100; 790 sym |= 0x100; 791 do 792 { 793 matchByte <<= 1; 794 price += GET_PRICEa(probs[offs + (matchByte & offs) + (sym >> 8)], (sym >> 7) & 1); 795 sym <<= 1; 796 offs &= ~(matchByte ^ sym); 797 } 798 while (sym < 0x10000); 799 return price; 800 } 801 802 803 static void RcTree_ReverseEncode(CRangeEnc *rc, CLzmaProb *probs, unsigned numBits, unsigned sym) 804 { 805 UInt32 range = rc->range; 806 unsigned m = 1; 807 do 808 { 809 UInt32 ttt, newBound; 810 unsigned bit = sym & 1; 811 // RangeEnc_EncodeBit(rc, probs + m, bit); 812 sym >>= 1; 813 RC_BIT(rc, probs + m, bit); 814 m = (m << 1) | bit; 815 } 816 while (--numBits); 817 rc->range = range; 818 } 819 820 821 822 static void LenEnc_Init(CLenEnc *p) 823 { 824 unsigned i; 825 for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << (kLenNumLowBits + 1)); i++) 826 p->low[i] = kProbInitValue; 827 for (i = 0; i < kLenNumHighSymbols; i++) 828 p->high[i] = kProbInitValue; 829 } 830 831 static void LenEnc_Encode(CLenEnc *p, CRangeEnc *rc, unsigned sym, unsigned posState) 832 { 833 UInt32 range, ttt, newBound; 834 CLzmaProb *probs = p->low; 835 range = rc->range; 836 RC_BIT_PRE(rc, probs); 837 if (sym >= kLenNumLowSymbols) 838 { 839 RC_BIT_1(rc, probs); 840 probs += kLenNumLowSymbols; 841 RC_BIT_PRE(rc, probs); 842 if (sym >= kLenNumLowSymbols * 2) 843 { 844 RC_BIT_1(rc, probs); 845 rc->range = range; 846 // RcTree_Encode(rc, p->high, kLenNumHighBits, sym - kLenNumLowSymbols * 2); 847 LitEnc_Encode(rc, p->high, sym - kLenNumLowSymbols * 2); 848 return; 849 } 850 sym -= kLenNumLowSymbols; 851 } 852 853 // RcTree_Encode(rc, probs + (posState << kLenNumLowBits), kLenNumLowBits, sym); 854 { 855 unsigned m; 856 unsigned bit; 857 RC_BIT_0(rc, probs); 858 probs += (posState << (1 + kLenNumLowBits)); 859 bit = (sym >> 2) ; RC_BIT(rc, probs + 1, bit); m = (1 << 1) + bit; 860 bit = (sym >> 1) & 1; RC_BIT(rc, probs + m, bit); m = (m << 1) + bit; 861 bit = sym & 1; RC_BIT(rc, probs + m, bit); 862 rc->range = range; 863 } 864 } 865 866 static void SetPrices_3(const CLzmaProb *probs, UInt32 startPrice, UInt32 *prices, const CProbPrice *ProbPrices) 867 { 868 unsigned i; 869 for (i = 0; i < 8; i += 2) 870 { 871 UInt32 price = startPrice; 872 UInt32 prob; 873 price += GET_PRICEa(probs[1 ], (i >> 2)); 874 price += GET_PRICEa(probs[2 + (i >> 2)], (i >> 1) & 1); 875 prob = probs[4 + (i >> 1)]; 876 prices[i ] = price + GET_PRICEa_0(prob); 877 prices[i + 1] = price + GET_PRICEa_1(prob); 878 } 879 } 880 881 882 MY_NO_INLINE static void MY_FAST_CALL LenPriceEnc_UpdateTables( 883 CLenPriceEnc *p, 884 unsigned numPosStates, 885 const CLenEnc *enc, 886 const CProbPrice *ProbPrices) 887 { 888 UInt32 b; 889 890 { 891 unsigned prob = enc->low[0]; 892 UInt32 a, c; 893 unsigned posState; 894 b = GET_PRICEa_1(prob); 895 a = GET_PRICEa_0(prob); 896 c = b + GET_PRICEa_0(enc->low[kLenNumLowSymbols]); 897 for (posState = 0; posState < numPosStates; posState++) 898 { 899 UInt32 *prices = p->prices[posState]; 900 const CLzmaProb *probs = enc->low + (posState << (1 + kLenNumLowBits)); 901 SetPrices_3(probs, a, prices, ProbPrices); 902 SetPrices_3(probs + kLenNumLowSymbols, c, prices + kLenNumLowSymbols, ProbPrices); 903 } 904 } 905 906 /* 907 { 908 unsigned i; 909 UInt32 b; 910 a = GET_PRICEa_0(enc->low[0]); 911 for (i = 0; i < kLenNumLowSymbols; i++) 912 p->prices2[i] = a; 913 a = GET_PRICEa_1(enc->low[0]); 914 b = a + GET_PRICEa_0(enc->low[kLenNumLowSymbols]); 915 for (i = kLenNumLowSymbols; i < kLenNumLowSymbols * 2; i++) 916 p->prices2[i] = b; 917 a += GET_PRICEa_1(enc->low[kLenNumLowSymbols]); 918 } 919 */ 920 921 // p->counter = numSymbols; 922 // p->counter = 64; 923 924 { 925 unsigned i = p->tableSize; 926 927 if (i > kLenNumLowSymbols * 2) 928 { 929 const CLzmaProb *probs = enc->high; 930 UInt32 *prices = p->prices[0] + kLenNumLowSymbols * 2; 931 i -= kLenNumLowSymbols * 2 - 1; 932 i >>= 1; 933 b += GET_PRICEa_1(enc->low[kLenNumLowSymbols]); 934 do 935 { 936 /* 937 p->prices2[i] = a + 938 // RcTree_GetPrice(enc->high, kLenNumHighBits, i - kLenNumLowSymbols * 2, ProbPrices); 939 LitEnc_GetPrice(probs, i - kLenNumLowSymbols * 2, ProbPrices); 940 */ 941 // UInt32 price = a + RcTree_GetPrice(probs, kLenNumHighBits - 1, sym, ProbPrices); 942 unsigned sym = --i + (1 << (kLenNumHighBits - 1)); 943 UInt32 price = b; 944 do 945 { 946 unsigned bit = sym & 1; 947 sym >>= 1; 948 price += GET_PRICEa(probs[sym], bit); 949 } 950 while (sym >= 2); 951 952 { 953 unsigned prob = probs[(size_t)i + (1 << (kLenNumHighBits - 1))]; 954 prices[(size_t)i * 2 ] = price + GET_PRICEa_0(prob); 955 prices[(size_t)i * 2 + 1] = price + GET_PRICEa_1(prob); 956 } 957 } 958 while (i); 959 960 { 961 unsigned posState; 962 size_t num = (p->tableSize - kLenNumLowSymbols * 2) * sizeof(p->prices[0][0]); 963 for (posState = 1; posState < numPosStates; posState++) 964 memcpy(p->prices[posState] + kLenNumLowSymbols * 2, p->prices[0] + kLenNumLowSymbols * 2, num); 965 } 966 } 967 } 968 } 969 970 /* 971 #ifdef SHOW_STAT 972 g_STAT_OFFSET += num; 973 printf("\n MovePos %u", num); 974 #endif 975 */ 976 977 #define MOVE_POS(p, num) { \ 978 p->additionalOffset += (num); \ 979 p->matchFinder.Skip(p->matchFinderObj, (UInt32)(num)); } 980 981 982 static unsigned ReadMatchDistances(CLzmaEnc *p, unsigned *numPairsRes) 983 { 984 unsigned numPairs; 985 986 p->additionalOffset++; 987 p->numAvail = p->matchFinder.GetNumAvailableBytes(p->matchFinderObj); 988 numPairs = p->matchFinder.GetMatches(p->matchFinderObj, p->matches); 989 *numPairsRes = numPairs; 990 991 #ifdef SHOW_STAT 992 printf("\n i = %u numPairs = %u ", g_STAT_OFFSET, numPairs / 2); 993 g_STAT_OFFSET++; 994 { 995 unsigned i; 996 for (i = 0; i < numPairs; i += 2) 997 printf("%2u %6u | ", p->matches[i], p->matches[i + 1]); 998 } 999 #endif 1000 1001 if (numPairs == 0) 1002 return 0; 1003 { 1004 unsigned len = p->matches[(size_t)numPairs - 2]; 1005 if (len != p->numFastBytes) 1006 return len; 1007 { 1008 UInt32 numAvail = p->numAvail; 1009 if (numAvail > LZMA_MATCH_LEN_MAX) 1010 numAvail = LZMA_MATCH_LEN_MAX; 1011 { 1012 const Byte *p1 = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; 1013 const Byte *p2 = p1 + len; 1014 ptrdiff_t dif = (ptrdiff_t)-1 - p->matches[(size_t)numPairs - 1]; 1015 const Byte *lim = p1 + numAvail; 1016 for (; p2 != lim && *p2 == p2[dif]; p2++) 1017 {} 1018 return (unsigned)(p2 - p1); 1019 } 1020 } 1021 } 1022 } 1023 1024 #define MARK_LIT ((UInt32)(Int32)-1) 1025 1026 #define MakeAs_Lit(p) { (p)->dist = MARK_LIT; (p)->extra = 0; } 1027 #define MakeAs_ShortRep(p) { (p)->dist = 0; (p)->extra = 0; } 1028 #define IsShortRep(p) ((p)->dist == 0) 1029 1030 1031 #define GetPrice_ShortRep(p, state, posState) \ 1032 ( GET_PRICE_0(p->isRepG0[state]) + GET_PRICE_0(p->isRep0Long[state][posState])) 1033 1034 #define GetPrice_Rep_0(p, state, posState) ( \ 1035 GET_PRICE_1(p->isMatch[state][posState]) \ 1036 + GET_PRICE_1(p->isRep0Long[state][posState])) \ 1037 + GET_PRICE_1(p->isRep[state]) \ 1038 + GET_PRICE_0(p->isRepG0[state]) 1039 1040 MY_FORCE_INLINE 1041 static UInt32 GetPrice_PureRep(const CLzmaEnc *p, unsigned repIndex, size_t state, size_t posState) 1042 { 1043 UInt32 price; 1044 UInt32 prob = p->isRepG0[state]; 1045 if (repIndex == 0) 1046 { 1047 price = GET_PRICE_0(prob); 1048 price += GET_PRICE_1(p->isRep0Long[state][posState]); 1049 } 1050 else 1051 { 1052 price = GET_PRICE_1(prob); 1053 prob = p->isRepG1[state]; 1054 if (repIndex == 1) 1055 price += GET_PRICE_0(prob); 1056 else 1057 { 1058 price += GET_PRICE_1(prob); 1059 price += GET_PRICE(p->isRepG2[state], repIndex - 2); 1060 } 1061 } 1062 return price; 1063 } 1064 1065 1066 static unsigned Backward(CLzmaEnc *p, unsigned cur) 1067 { 1068 unsigned wr = cur + 1; 1069 p->optEnd = wr; 1070 1071 for (;;) 1072 { 1073 UInt32 dist = p->opt[cur].dist; 1074 unsigned len = (unsigned)p->opt[cur].len; 1075 unsigned extra = (unsigned)p->opt[cur].extra; 1076 cur -= len; 1077 1078 if (extra) 1079 { 1080 wr--; 1081 p->opt[wr].len = (UInt32)len; 1082 cur -= extra; 1083 len = extra; 1084 if (extra == 1) 1085 { 1086 p->opt[wr].dist = dist; 1087 dist = MARK_LIT; 1088 } 1089 else 1090 { 1091 p->opt[wr].dist = 0; 1092 len--; 1093 wr--; 1094 p->opt[wr].dist = MARK_LIT; 1095 p->opt[wr].len = 1; 1096 } 1097 } 1098 1099 if (cur == 0) 1100 { 1101 p->backRes = dist; 1102 p->optCur = wr; 1103 return len; 1104 } 1105 1106 wr--; 1107 p->opt[wr].dist = dist; 1108 p->opt[wr].len = (UInt32)len; 1109 } 1110 } 1111 1112 1113 1114 #define LIT_PROBS(pos, prevByte) \ 1115 (p->litProbs + (UInt32)3 * (((((pos) << 8) + (prevByte)) & p->lpMask) << p->lc)) 1116 1117 1118 static unsigned GetOptimum(CLzmaEnc *p, UInt32 position) 1119 { 1120 unsigned last, cur; 1121 UInt32 reps[LZMA_NUM_REPS]; 1122 unsigned repLens[LZMA_NUM_REPS]; 1123 UInt32 *matches; 1124 1125 { 1126 UInt32 numAvail; 1127 unsigned numPairs, mainLen, repMaxIndex, i, posState; 1128 UInt32 matchPrice, repMatchPrice; 1129 const Byte *data; 1130 Byte curByte, matchByte; 1131 1132 p->optCur = p->optEnd = 0; 1133 1134 if (p->additionalOffset == 0) 1135 mainLen = ReadMatchDistances(p, &numPairs); 1136 else 1137 { 1138 mainLen = p->longestMatchLen; 1139 numPairs = p->numPairs; 1140 } 1141 1142 numAvail = p->numAvail; 1143 if (numAvail < 2) 1144 { 1145 p->backRes = MARK_LIT; 1146 return 1; 1147 } 1148 if (numAvail > LZMA_MATCH_LEN_MAX) 1149 numAvail = LZMA_MATCH_LEN_MAX; 1150 1151 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; 1152 repMaxIndex = 0; 1153 1154 for (i = 0; i < LZMA_NUM_REPS; i++) 1155 { 1156 unsigned len; 1157 const Byte *data2; 1158 reps[i] = p->reps[i]; 1159 data2 = data - reps[i]; 1160 if (data[0] != data2[0] || data[1] != data2[1]) 1161 { 1162 repLens[i] = 0; 1163 continue; 1164 } 1165 for (len = 2; len < numAvail && data[len] == data2[len]; len++) 1166 {} 1167 repLens[i] = len; 1168 if (len > repLens[repMaxIndex]) 1169 repMaxIndex = i; 1170 } 1171 1172 if (repLens[repMaxIndex] >= p->numFastBytes) 1173 { 1174 unsigned len; 1175 p->backRes = (UInt32)repMaxIndex; 1176 len = repLens[repMaxIndex]; 1177 MOVE_POS(p, len - 1) 1178 return len; 1179 } 1180 1181 matches = p->matches; 1182 1183 if (mainLen >= p->numFastBytes) 1184 { 1185 p->backRes = matches[(size_t)numPairs - 1] + LZMA_NUM_REPS; 1186 MOVE_POS(p, mainLen - 1) 1187 return mainLen; 1188 } 1189 1190 curByte = *data; 1191 matchByte = *(data - reps[0]); 1192 1193 last = repLens[repMaxIndex]; 1194 if (last <= mainLen) 1195 last = mainLen; 1196 1197 if (last < 2 && curByte != matchByte) 1198 { 1199 p->backRes = MARK_LIT; 1200 return 1; 1201 } 1202 1203 p->opt[0].state = (CState)p->state; 1204 1205 posState = (position & p->pbMask); 1206 1207 { 1208 const CLzmaProb *probs = LIT_PROBS(position, *(data - 1)); 1209 p->opt[1].price = GET_PRICE_0(p->isMatch[p->state][posState]) + 1210 (!IsLitState(p->state) ? 1211 LitEnc_Matched_GetPrice(probs, curByte, matchByte, p->ProbPrices) : 1212 LitEnc_GetPrice(probs, curByte, p->ProbPrices)); 1213 } 1214 1215 MakeAs_Lit(&p->opt[1]); 1216 1217 matchPrice = GET_PRICE_1(p->isMatch[p->state][posState]); 1218 repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[p->state]); 1219 1220 // 18.06 1221 if (matchByte == curByte && repLens[0] == 0) 1222 { 1223 UInt32 shortRepPrice = repMatchPrice + GetPrice_ShortRep(p, p->state, posState); 1224 if (shortRepPrice < p->opt[1].price) 1225 { 1226 p->opt[1].price = shortRepPrice; 1227 MakeAs_ShortRep(&p->opt[1]); 1228 } 1229 if (last < 2) 1230 { 1231 p->backRes = p->opt[1].dist; 1232 return 1; 1233 } 1234 } 1235 1236 p->opt[1].len = 1; 1237 1238 p->opt[0].reps[0] = reps[0]; 1239 p->opt[0].reps[1] = reps[1]; 1240 p->opt[0].reps[2] = reps[2]; 1241 p->opt[0].reps[3] = reps[3]; 1242 1243 // ---------- REP ---------- 1244 1245 for (i = 0; i < LZMA_NUM_REPS; i++) 1246 { 1247 unsigned repLen = repLens[i]; 1248 UInt32 price; 1249 if (repLen < 2) 1250 continue; 1251 price = repMatchPrice + GetPrice_PureRep(p, i, p->state, posState); 1252 do 1253 { 1254 UInt32 price2 = price + GET_PRICE_LEN(&p->repLenEnc, posState, repLen); 1255 COptimal *opt = &p->opt[repLen]; 1256 if (price2 < opt->price) 1257 { 1258 opt->price = price2; 1259 opt->len = (UInt32)repLen; 1260 opt->dist = (UInt32)i; 1261 opt->extra = 0; 1262 } 1263 } 1264 while (--repLen >= 2); 1265 } 1266 1267 1268 // ---------- MATCH ---------- 1269 { 1270 unsigned len = repLens[0] + 1; 1271 if (len <= mainLen) 1272 { 1273 unsigned offs = 0; 1274 UInt32 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[p->state]); 1275 1276 if (len < 2) 1277 len = 2; 1278 else 1279 while (len > matches[offs]) 1280 offs += 2; 1281 1282 for (; ; len++) 1283 { 1284 COptimal *opt; 1285 UInt32 dist = matches[(size_t)offs + 1]; 1286 UInt32 price = normalMatchPrice + GET_PRICE_LEN(&p->lenEnc, posState, len); 1287 unsigned lenToPosState = GetLenToPosState(len); 1288 1289 if (dist < kNumFullDistances) 1290 price += p->distancesPrices[lenToPosState][dist & (kNumFullDistances - 1)]; 1291 else 1292 { 1293 unsigned slot; 1294 GetPosSlot2(dist, slot); 1295 price += p->alignPrices[dist & kAlignMask]; 1296 price += p->posSlotPrices[lenToPosState][slot]; 1297 } 1298 1299 opt = &p->opt[len]; 1300 1301 if (price < opt->price) 1302 { 1303 opt->price = price; 1304 opt->len = (UInt32)len; 1305 opt->dist = dist + LZMA_NUM_REPS; 1306 opt->extra = 0; 1307 } 1308 1309 if (len == matches[offs]) 1310 { 1311 offs += 2; 1312 if (offs == numPairs) 1313 break; 1314 } 1315 } 1316 } 1317 } 1318 1319 1320 cur = 0; 1321 1322 #ifdef SHOW_STAT2 1323 /* if (position >= 0) */ 1324 { 1325 unsigned i; 1326 printf("\n pos = %4X", position); 1327 for (i = cur; i <= last; i++) 1328 printf("\nprice[%4X] = %u", position - cur + i, p->opt[i].price); 1329 } 1330 #endif 1331 } 1332 1333 1334 1335 // ---------- Optimal Parsing ---------- 1336 1337 for (;;) 1338 { 1339 unsigned numAvail; 1340 UInt32 numAvailFull; 1341 unsigned newLen, numPairs, prev, state, posState, startLen; 1342 UInt32 litPrice, matchPrice, repMatchPrice; 1343 BoolInt nextIsLit; 1344 Byte curByte, matchByte; 1345 const Byte *data; 1346 COptimal *curOpt, *nextOpt; 1347 1348 if (++cur == last) 1349 break; 1350 1351 // 18.06 1352 if (cur >= kNumOpts - 64) 1353 { 1354 unsigned j, best; 1355 UInt32 price = p->opt[cur].price; 1356 best = cur; 1357 for (j = cur + 1; j <= last; j++) 1358 { 1359 UInt32 price2 = p->opt[j].price; 1360 if (price >= price2) 1361 { 1362 price = price2; 1363 best = j; 1364 } 1365 } 1366 { 1367 unsigned delta = best - cur; 1368 if (delta != 0) 1369 { 1370 MOVE_POS(p, delta); 1371 } 1372 } 1373 cur = best; 1374 break; 1375 } 1376 1377 newLen = ReadMatchDistances(p, &numPairs); 1378 1379 if (newLen >= p->numFastBytes) 1380 { 1381 p->numPairs = numPairs; 1382 p->longestMatchLen = newLen; 1383 break; 1384 } 1385 1386 curOpt = &p->opt[cur]; 1387 1388 position++; 1389 1390 // we need that check here, if skip_items in p->opt are possible 1391 /* 1392 if (curOpt->price >= kInfinityPrice) 1393 continue; 1394 */ 1395 1396 prev = cur - curOpt->len; 1397 1398 if (curOpt->len == 1) 1399 { 1400 state = (unsigned)p->opt[prev].state; 1401 if (IsShortRep(curOpt)) 1402 state = kShortRepNextStates[state]; 1403 else 1404 state = kLiteralNextStates[state]; 1405 } 1406 else 1407 { 1408 const COptimal *prevOpt; 1409 UInt32 b0; 1410 UInt32 dist = curOpt->dist; 1411 1412 if (curOpt->extra) 1413 { 1414 prev -= (unsigned)curOpt->extra; 1415 state = kState_RepAfterLit; 1416 if (curOpt->extra == 1) 1417 state = (dist < LZMA_NUM_REPS ? kState_RepAfterLit : kState_MatchAfterLit); 1418 } 1419 else 1420 { 1421 state = (unsigned)p->opt[prev].state; 1422 if (dist < LZMA_NUM_REPS) 1423 state = kRepNextStates[state]; 1424 else 1425 state = kMatchNextStates[state]; 1426 } 1427 1428 prevOpt = &p->opt[prev]; 1429 b0 = prevOpt->reps[0]; 1430 1431 if (dist < LZMA_NUM_REPS) 1432 { 1433 if (dist == 0) 1434 { 1435 reps[0] = b0; 1436 reps[1] = prevOpt->reps[1]; 1437 reps[2] = prevOpt->reps[2]; 1438 reps[3] = prevOpt->reps[3]; 1439 } 1440 else 1441 { 1442 reps[1] = b0; 1443 b0 = prevOpt->reps[1]; 1444 if (dist == 1) 1445 { 1446 reps[0] = b0; 1447 reps[2] = prevOpt->reps[2]; 1448 reps[3] = prevOpt->reps[3]; 1449 } 1450 else 1451 { 1452 reps[2] = b0; 1453 reps[0] = prevOpt->reps[dist]; 1454 reps[3] = prevOpt->reps[dist ^ 1]; 1455 } 1456 } 1457 } 1458 else 1459 { 1460 reps[0] = (dist - LZMA_NUM_REPS + 1); 1461 reps[1] = b0; 1462 reps[2] = prevOpt->reps[1]; 1463 reps[3] = prevOpt->reps[2]; 1464 } 1465 } 1466 1467 curOpt->state = (CState)state; 1468 curOpt->reps[0] = reps[0]; 1469 curOpt->reps[1] = reps[1]; 1470 curOpt->reps[2] = reps[2]; 1471 curOpt->reps[3] = reps[3]; 1472 1473 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; 1474 curByte = *data; 1475 matchByte = *(data - reps[0]); 1476 1477 posState = (position & p->pbMask); 1478 1479 /* 1480 The order of Price checks: 1481 < LIT 1482 <= SHORT_REP 1483 < LIT : REP_0 1484 < REP [ : LIT : REP_0 ] 1485 < MATCH [ : LIT : REP_0 ] 1486 */ 1487 1488 { 1489 UInt32 curPrice = curOpt->price; 1490 unsigned prob = p->isMatch[state][posState]; 1491 matchPrice = curPrice + GET_PRICE_1(prob); 1492 litPrice = curPrice + GET_PRICE_0(prob); 1493 } 1494 1495 nextOpt = &p->opt[(size_t)cur + 1]; 1496 nextIsLit = False; 1497 1498 // here we can allow skip_items in p->opt, if we don't check (nextOpt->price < kInfinityPrice) 1499 // 18.new.06 1500 if (nextOpt->price < kInfinityPrice 1501 // && !IsLitState(state) 1502 && matchByte == curByte 1503 || litPrice > nextOpt->price 1504 ) 1505 litPrice = 0; 1506 else 1507 { 1508 const CLzmaProb *probs = LIT_PROBS(position, *(data - 1)); 1509 litPrice += (!IsLitState(state) ? 1510 LitEnc_Matched_GetPrice(probs, curByte, matchByte, p->ProbPrices) : 1511 LitEnc_GetPrice(probs, curByte, p->ProbPrices)); 1512 1513 if (litPrice < nextOpt->price) 1514 { 1515 nextOpt->price = litPrice; 1516 nextOpt->len = 1; 1517 MakeAs_Lit(nextOpt); 1518 nextIsLit = True; 1519 } 1520 } 1521 1522 repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[state]); 1523 1524 numAvailFull = p->numAvail; 1525 { 1526 unsigned temp = kNumOpts - 1 - cur; 1527 if (numAvailFull > temp) 1528 numAvailFull = (UInt32)temp; 1529 } 1530 1531 // 18.06 1532 // ---------- SHORT_REP ---------- 1533 if (IsLitState(state)) // 18.new 1534 if (matchByte == curByte) 1535 if (repMatchPrice < nextOpt->price) // 18.new 1536 // if (numAvailFull < 2 || data[1] != *(data - reps[0] + 1)) 1537 if ( 1538 // nextOpt->price >= kInfinityPrice || 1539 nextOpt->len < 2 // we can check nextOpt->len, if skip items are not allowed in p->opt 1540 || (nextOpt->dist != 0 1541 // && nextOpt->extra <= 1 // 17.old 1542 ) 1543 ) 1544 { 1545 UInt32 shortRepPrice = repMatchPrice + GetPrice_ShortRep(p, state, posState); 1546 // if (shortRepPrice <= nextOpt->price) // 17.old 1547 if (shortRepPrice < nextOpt->price) // 18.new 1548 { 1549 nextOpt->price = shortRepPrice; 1550 nextOpt->len = 1; 1551 MakeAs_ShortRep(nextOpt); 1552 nextIsLit = False; 1553 } 1554 } 1555 1556 if (numAvailFull < 2) 1557 continue; 1558 numAvail = (numAvailFull <= p->numFastBytes ? numAvailFull : p->numFastBytes); 1559 1560 // numAvail <= p->numFastBytes 1561 1562 // ---------- LIT : REP_0 ---------- 1563 1564 if (!nextIsLit 1565 && litPrice != 0 // 18.new 1566 && matchByte != curByte 1567 && numAvailFull > 2) 1568 { 1569 const Byte *data2 = data - reps[0]; 1570 if (data[1] == data2[1] && data[2] == data2[2]) 1571 { 1572 unsigned len; 1573 unsigned limit = p->numFastBytes + 1; 1574 if (limit > numAvailFull) 1575 limit = numAvailFull; 1576 for (len = 3; len < limit && data[len] == data2[len]; len++) 1577 {} 1578 1579 { 1580 unsigned state2 = kLiteralNextStates[state]; 1581 unsigned posState2 = (position + 1) & p->pbMask; 1582 UInt32 price = litPrice + GetPrice_Rep_0(p, state2, posState2); 1583 { 1584 unsigned offset = cur + len; 1585 1586 if (last < offset) 1587 last = offset; 1588 1589 // do 1590 { 1591 UInt32 price2; 1592 COptimal *opt; 1593 len--; 1594 // price2 = price + GetPrice_Len_Rep_0(p, len, state2, posState2); 1595 price2 = price + GET_PRICE_LEN(&p->repLenEnc, posState2, len); 1596 1597 opt = &p->opt[offset]; 1598 // offset--; 1599 if (price2 < opt->price) 1600 { 1601 opt->price = price2; 1602 opt->len = (UInt32)len; 1603 opt->dist = 0; 1604 opt->extra = 1; 1605 } 1606 } 1607 // while (len >= 3); 1608 } 1609 } 1610 } 1611 } 1612 1613 startLen = 2; /* speed optimization */ 1614 1615 { 1616 // ---------- REP ---------- 1617 unsigned repIndex = 0; // 17.old 1618 // unsigned repIndex = IsLitState(state) ? 0 : 1; // 18.notused 1619 for (; repIndex < LZMA_NUM_REPS; repIndex++) 1620 { 1621 unsigned len; 1622 UInt32 price; 1623 const Byte *data2 = data - reps[repIndex]; 1624 if (data[0] != data2[0] || data[1] != data2[1]) 1625 continue; 1626 1627 for (len = 2; len < numAvail && data[len] == data2[len]; len++) 1628 {} 1629 1630 // if (len < startLen) continue; // 18.new: speed optimization 1631 1632 { 1633 unsigned offset = cur + len; 1634 if (last < offset) 1635 last = offset; 1636 } 1637 { 1638 unsigned len2 = len; 1639 price = repMatchPrice + GetPrice_PureRep(p, repIndex, state, posState); 1640 do 1641 { 1642 UInt32 price2 = price + GET_PRICE_LEN(&p->repLenEnc, posState, len2); 1643 COptimal *opt = &p->opt[cur + len2]; 1644 if (price2 < opt->price) 1645 { 1646 opt->price = price2; 1647 opt->len = (UInt32)len2; 1648 opt->dist = (UInt32)repIndex; 1649 opt->extra = 0; 1650 } 1651 } 1652 while (--len2 >= 2); 1653 } 1654 1655 if (repIndex == 0) startLen = len + 1; // 17.old 1656 // startLen = len + 1; // 18.new 1657 1658 /* if (_maxMode) */ 1659 { 1660 // ---------- REP : LIT : REP_0 ---------- 1661 // numFastBytes + 1 + numFastBytes 1662 1663 unsigned len2 = len + 1; 1664 unsigned limit = len2 + p->numFastBytes; 1665 if (limit > numAvailFull) 1666 limit = numAvailFull; 1667 1668 len2 += 2; 1669 if (len2 <= limit) 1670 if (data[len2 - 2] == data2[len2 - 2]) 1671 if (data[len2 - 1] == data2[len2 - 1]) 1672 { 1673 unsigned state2 = kRepNextStates[state]; 1674 unsigned posState2 = (position + len) & p->pbMask; 1675 price += GET_PRICE_LEN(&p->repLenEnc, posState, len) 1676 + GET_PRICE_0(p->isMatch[state2][posState2]) 1677 + LitEnc_Matched_GetPrice(LIT_PROBS(position + len, data[(size_t)len - 1]), 1678 data[len], data2[len], p->ProbPrices); 1679 1680 // state2 = kLiteralNextStates[state2]; 1681 state2 = kState_LitAfterRep; 1682 posState2 = (posState2 + 1) & p->pbMask; 1683 1684 1685 price += GetPrice_Rep_0(p, state2, posState2); 1686 1687 for (; len2 < limit && data[len2] == data2[len2]; len2++) 1688 {} 1689 1690 len2 -= len; 1691 // if (len2 >= 3) 1692 { 1693 { 1694 unsigned offset = cur + len + len2; 1695 1696 if (last < offset) 1697 last = offset; 1698 // do 1699 { 1700 UInt32 price2; 1701 COptimal *opt; 1702 len2--; 1703 // price2 = price + GetPrice_Len_Rep_0(p, len2, state2, posState2); 1704 price2 = price + GET_PRICE_LEN(&p->repLenEnc, posState2, len2); 1705 1706 opt = &p->opt[offset]; 1707 // offset--; 1708 if (price2 < opt->price) 1709 { 1710 opt->price = price2; 1711 opt->len = (UInt32)len2; 1712 opt->extra = (CExtra)(len + 1); 1713 opt->dist = (UInt32)repIndex; 1714 } 1715 } 1716 // while (len2 >= 3); 1717 } 1718 } 1719 } 1720 } 1721 } 1722 } 1723 1724 1725 // ---------- MATCH ---------- 1726 /* for (unsigned len = 2; len <= newLen; len++) */ 1727 if (newLen > numAvail) 1728 { 1729 newLen = numAvail; 1730 for (numPairs = 0; newLen > matches[numPairs]; numPairs += 2); 1731 matches[numPairs] = (UInt32)newLen; 1732 numPairs += 2; 1733 } 1734 1735 // startLen = 2; /* speed optimization */ 1736 1737 if (newLen >= startLen) 1738 { 1739 UInt32 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[state]); 1740 UInt32 dist; 1741 unsigned offs, posSlot, len; 1742 1743 { 1744 unsigned offset = cur + newLen; 1745 if (last < offset) 1746 last = offset; 1747 } 1748 1749 offs = 0; 1750 while (startLen > matches[offs]) 1751 offs += 2; 1752 dist = matches[(size_t)offs + 1]; 1753 1754 // if (dist >= kNumFullDistances) 1755 GetPosSlot2(dist, posSlot); 1756 1757 for (len = /*2*/ startLen; ; len++) 1758 { 1759 UInt32 price = normalMatchPrice + GET_PRICE_LEN(&p->lenEnc, posState, len); 1760 { 1761 COptimal *opt; 1762 unsigned lenNorm = len - 2; 1763 lenNorm = GetLenToPosState2(lenNorm); 1764 if (dist < kNumFullDistances) 1765 price += p->distancesPrices[lenNorm][dist & (kNumFullDistances - 1)]; 1766 else 1767 price += p->posSlotPrices[lenNorm][posSlot] + p->alignPrices[dist & kAlignMask]; 1768 1769 opt = &p->opt[cur + len]; 1770 if (price < opt->price) 1771 { 1772 opt->price = price; 1773 opt->len = (UInt32)len; 1774 opt->dist = dist + LZMA_NUM_REPS; 1775 opt->extra = 0; 1776 } 1777 } 1778 1779 if (len == matches[offs]) 1780 { 1781 // if (p->_maxMode) { 1782 // MATCH : LIT : REP_0 1783 1784 const Byte *data2 = data - dist - 1; 1785 unsigned len2 = len + 1; 1786 unsigned limit = len2 + p->numFastBytes; 1787 if (limit > numAvailFull) 1788 limit = numAvailFull; 1789 1790 len2 += 2; 1791 if (len2 <= limit) 1792 if (data[len2 - 2] == data2[len2 - 2]) 1793 if (data[len2 - 1] == data2[len2 - 1]) 1794 { 1795 for (; len2 < limit && data[len2] == data2[len2]; len2++) 1796 {} 1797 1798 len2 -= len; 1799 1800 // if (len2 >= 3) 1801 { 1802 unsigned state2 = kMatchNextStates[state]; 1803 unsigned posState2 = (position + len) & p->pbMask; 1804 unsigned offset; 1805 price += GET_PRICE_0(p->isMatch[state2][posState2]); 1806 price += LitEnc_Matched_GetPrice(LIT_PROBS(position + len, data[(size_t)len - 1]), 1807 data[len], data2[len], p->ProbPrices); 1808 1809 // state2 = kLiteralNextStates[state2]; 1810 state2 = kState_LitAfterMatch; 1811 1812 posState2 = (posState2 + 1) & p->pbMask; 1813 price += GetPrice_Rep_0(p, state2, posState2); 1814 1815 offset = cur + len + len2; 1816 1817 if (last < offset) 1818 last = offset; 1819 // do 1820 { 1821 UInt32 price2; 1822 COptimal *opt; 1823 len2--; 1824 // price2 = price + GetPrice_Len_Rep_0(p, len2, state2, posState2); 1825 price2 = price + GET_PRICE_LEN(&p->repLenEnc, posState2, len2); 1826 opt = &p->opt[offset]; 1827 // offset--; 1828 if (price2 < opt->price) 1829 { 1830 opt->price = price2; 1831 opt->len = (UInt32)len2; 1832 opt->extra = (CExtra)(len + 1); 1833 opt->dist = dist + LZMA_NUM_REPS; 1834 } 1835 } 1836 // while (len2 >= 3); 1837 } 1838 1839 } 1840 1841 offs += 2; 1842 if (offs == numPairs) 1843 break; 1844 dist = matches[(size_t)offs + 1]; 1845 // if (dist >= kNumFullDistances) 1846 GetPosSlot2(dist, posSlot); 1847 } 1848 } 1849 } 1850 } 1851 1852 do 1853 p->opt[last].price = kInfinityPrice; 1854 while (--last); 1855 1856 return Backward(p, cur); 1857 } 1858 1859 1860 1861 #define ChangePair(smallDist, bigDist) (((bigDist) >> 7) > (smallDist)) 1862 1863 1864 1865 static unsigned GetOptimumFast(CLzmaEnc *p) 1866 { 1867 UInt32 numAvail, mainDist; 1868 unsigned mainLen, numPairs, repIndex, repLen, i; 1869 const Byte *data; 1870 1871 if (p->additionalOffset == 0) 1872 mainLen = ReadMatchDistances(p, &numPairs); 1873 else 1874 { 1875 mainLen = p->longestMatchLen; 1876 numPairs = p->numPairs; 1877 } 1878 1879 numAvail = p->numAvail; 1880 p->backRes = MARK_LIT; 1881 if (numAvail < 2) 1882 return 1; 1883 // if (mainLen < 2 && p->state == 0) return 1; // 18.06.notused 1884 if (numAvail > LZMA_MATCH_LEN_MAX) 1885 numAvail = LZMA_MATCH_LEN_MAX; 1886 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; 1887 repLen = repIndex = 0; 1888 1889 for (i = 0; i < LZMA_NUM_REPS; i++) 1890 { 1891 unsigned len; 1892 const Byte *data2 = data - p->reps[i]; 1893 if (data[0] != data2[0] || data[1] != data2[1]) 1894 continue; 1895 for (len = 2; len < numAvail && data[len] == data2[len]; len++) 1896 {} 1897 if (len >= p->numFastBytes) 1898 { 1899 p->backRes = (UInt32)i; 1900 MOVE_POS(p, len - 1) 1901 return len; 1902 } 1903 if (len > repLen) 1904 { 1905 repIndex = i; 1906 repLen = len; 1907 } 1908 } 1909 1910 if (mainLen >= p->numFastBytes) 1911 { 1912 p->backRes = p->matches[(size_t)numPairs - 1] + LZMA_NUM_REPS; 1913 MOVE_POS(p, mainLen - 1) 1914 return mainLen; 1915 } 1916 1917 mainDist = 0; /* for GCC */ 1918 1919 if (mainLen >= 2) 1920 { 1921 mainDist = p->matches[(size_t)numPairs - 1]; 1922 while (numPairs > 2) 1923 { 1924 UInt32 dist2; 1925 if (mainLen != p->matches[(size_t)numPairs - 4] + 1) 1926 break; 1927 dist2 = p->matches[(size_t)numPairs - 3]; 1928 if (!ChangePair(dist2, mainDist)) 1929 break; 1930 numPairs -= 2; 1931 mainLen--; 1932 mainDist = dist2; 1933 } 1934 if (mainLen == 2 && mainDist >= 0x80) 1935 mainLen = 1; 1936 } 1937 1938 if (repLen >= 2) 1939 if ( repLen + 1 >= mainLen 1940 || (repLen + 2 >= mainLen && mainDist >= (1 << 9)) 1941 || (repLen + 3 >= mainLen && mainDist >= (1 << 15))) 1942 { 1943 p->backRes = (UInt32)repIndex; 1944 MOVE_POS(p, repLen - 1) 1945 return repLen; 1946 } 1947 1948 if (mainLen < 2 || numAvail <= 2) 1949 return 1; 1950 1951 { 1952 unsigned len1 = ReadMatchDistances(p, &p->numPairs); 1953 p->longestMatchLen = len1; 1954 1955 if (len1 >= 2) 1956 { 1957 UInt32 newDist = p->matches[(size_t)p->numPairs - 1]; 1958 if ( (len1 >= mainLen && newDist < mainDist) 1959 || (len1 == mainLen + 1 && !ChangePair(mainDist, newDist)) 1960 || (len1 > mainLen + 1) 1961 || (len1 + 1 >= mainLen && mainLen >= 3 && ChangePair(newDist, mainDist))) 1962 return 1; 1963 } 1964 } 1965 1966 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; 1967 1968 for (i = 0; i < LZMA_NUM_REPS; i++) 1969 { 1970 unsigned len, limit; 1971 const Byte *data2 = data - p->reps[i]; 1972 if (data[0] != data2[0] || data[1] != data2[1]) 1973 continue; 1974 limit = mainLen - 1; 1975 for (len = 2;; len++) 1976 { 1977 if (len >= limit) 1978 return 1; 1979 if (data[len] != data2[len]) 1980 break; 1981 } 1982 } 1983 1984 p->backRes = mainDist + LZMA_NUM_REPS; 1985 if (mainLen != 2) 1986 { 1987 MOVE_POS(p, mainLen - 2) 1988 } 1989 return mainLen; 1990 } 1991 1992 1993 1994 1995 static void WriteEndMarker(CLzmaEnc *p, unsigned posState) 1996 { 1997 UInt32 range; 1998 range = p->rc.range; 1999 { 2000 UInt32 ttt, newBound; 2001 CLzmaProb *prob = &p->isMatch[p->state][posState]; 2002 RC_BIT_PRE(&p->rc, prob) 2003 RC_BIT_1(&p->rc, prob) 2004 prob = &p->isRep[p->state]; 2005 RC_BIT_PRE(&p->rc, prob) 2006 RC_BIT_0(&p->rc, prob) 2007 } 2008 p->state = kMatchNextStates[p->state]; 2009 2010 p->rc.range = range; 2011 LenEnc_Encode(&p->lenProbs, &p->rc, 0, posState); 2012 range = p->rc.range; 2013 2014 { 2015 // RcTree_Encode_PosSlot(&p->rc, p->posSlotEncoder[0], (1 << kNumPosSlotBits) - 1); 2016 CLzmaProb *probs = p->posSlotEncoder[0]; 2017 unsigned m = 1; 2018 do 2019 { 2020 UInt32 ttt, newBound; 2021 RC_BIT_PRE(p, probs + m) 2022 RC_BIT_1(&p->rc, probs + m); 2023 m = (m << 1) + 1; 2024 } 2025 while (m < (1 << kNumPosSlotBits)); 2026 } 2027 { 2028 // RangeEnc_EncodeDirectBits(&p->rc, ((UInt32)1 << (30 - kNumAlignBits)) - 1, 30 - kNumAlignBits); UInt32 range = p->range; 2029 unsigned numBits = 30 - kNumAlignBits; 2030 do 2031 { 2032 range >>= 1; 2033 p->rc.low += range; 2034 RC_NORM(&p->rc) 2035 } 2036 while (--numBits); 2037 } 2038 2039 { 2040 // RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, kAlignMask); 2041 CLzmaProb *probs = p->posAlignEncoder; 2042 unsigned m = 1; 2043 do 2044 { 2045 UInt32 ttt, newBound; 2046 RC_BIT_PRE(p, probs + m) 2047 RC_BIT_1(&p->rc, probs + m); 2048 m = (m << 1) + 1; 2049 } 2050 while (m < kAlignTableSize); 2051 } 2052 p->rc.range = range; 2053 } 2054 2055 2056 static SRes CheckErrors(CLzmaEnc *p) 2057 { 2058 if (p->result != SZ_OK) 2059 return p->result; 2060 if (p->rc.res != SZ_OK) 2061 p->result = SZ_ERROR_WRITE; 2062 if (p->matchFinderBase.result != SZ_OK) 2063 p->result = SZ_ERROR_READ; 2064 if (p->result != SZ_OK) 2065 p->finished = True; 2066 return p->result; 2067 } 2068 2069 2070 MY_NO_INLINE static SRes Flush(CLzmaEnc *p, UInt32 nowPos) 2071 { 2072 /* ReleaseMFStream(); */ 2073 p->finished = True; 2074 if (p->writeEndMark) 2075 WriteEndMarker(p, nowPos & p->pbMask); 2076 RangeEnc_FlushData(&p->rc); 2077 RangeEnc_FlushStream(&p->rc); 2078 return CheckErrors(p); 2079 } 2080 2081 2082 MY_NO_INLINE static void FillAlignPrices(CLzmaEnc *p) 2083 { 2084 unsigned i; 2085 const CProbPrice *ProbPrices = p->ProbPrices; 2086 const CLzmaProb *probs = p->posAlignEncoder; 2087 // p->alignPriceCount = 0; 2088 for (i = 0; i < kAlignTableSize / 2; i++) 2089 { 2090 UInt32 price = 0; 2091 unsigned sym = i; 2092 unsigned m = 1; 2093 unsigned bit; 2094 UInt32 prob; 2095 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[m], bit); m = (m << 1) + bit; 2096 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[m], bit); m = (m << 1) + bit; 2097 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[m], bit); m = (m << 1) + bit; 2098 prob = probs[m]; 2099 p->alignPrices[i ] = price + GET_PRICEa_0(prob); 2100 p->alignPrices[i + 8] = price + GET_PRICEa_1(prob); 2101 // p->alignPrices[i] = RcTree_ReverseGetPrice(p->posAlignEncoder, kNumAlignBits, i, p->ProbPrices); 2102 } 2103 } 2104 2105 2106 MY_NO_INLINE static void FillDistancesPrices(CLzmaEnc *p) 2107 { 2108 // int y; for (y = 0; y < 100; y++) { 2109 2110 UInt32 tempPrices[kNumFullDistances]; 2111 unsigned i, lps; 2112 2113 const CProbPrice *ProbPrices = p->ProbPrices; 2114 p->matchPriceCount = 0; 2115 2116 for (i = kStartPosModelIndex / 2; i < kNumFullDistances / 2; i++) 2117 { 2118 unsigned posSlot = GetPosSlot1(i); 2119 unsigned footerBits = (posSlot >> 1) - 1; 2120 unsigned base = ((2 | (posSlot & 1)) << footerBits); 2121 const CLzmaProb *probs = p->posEncoders + (size_t)base * 2; 2122 // tempPrices[i] = RcTree_ReverseGetPrice(p->posEncoders + base, footerBits, i - base, p->ProbPrices); 2123 UInt32 price = 0; 2124 unsigned m = 1; 2125 unsigned sym = i; 2126 unsigned offset = (unsigned)1 << footerBits; 2127 base += i; 2128 2129 if (footerBits) 2130 do 2131 { 2132 unsigned bit = sym & 1; 2133 sym >>= 1; 2134 price += GET_PRICEa(probs[m], bit); 2135 m = (m << 1) + bit; 2136 } 2137 while (--footerBits); 2138 2139 { 2140 unsigned prob = probs[m]; 2141 tempPrices[base ] = price + GET_PRICEa_0(prob); 2142 tempPrices[base + offset] = price + GET_PRICEa_1(prob); 2143 } 2144 } 2145 2146 for (lps = 0; lps < kNumLenToPosStates; lps++) 2147 { 2148 unsigned slot; 2149 unsigned distTableSize2 = (p->distTableSize + 1) >> 1; 2150 UInt32 *posSlotPrices = p->posSlotPrices[lps]; 2151 const CLzmaProb *probs = p->posSlotEncoder[lps]; 2152 2153 for (slot = 0; slot < distTableSize2; slot++) 2154 { 2155 // posSlotPrices[slot] = RcTree_GetPrice(encoder, kNumPosSlotBits, slot, p->ProbPrices); 2156 UInt32 price; 2157 unsigned bit; 2158 unsigned sym = slot + (1 << (kNumPosSlotBits - 1)); 2159 unsigned prob; 2160 bit = sym & 1; sym >>= 1; price = GET_PRICEa(probs[sym], bit); 2161 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[sym], bit); 2162 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[sym], bit); 2163 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[sym], bit); 2164 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[sym], bit); 2165 prob = probs[(size_t)slot + (1 << (kNumPosSlotBits - 1))]; 2166 posSlotPrices[(size_t)slot * 2 ] = price + GET_PRICEa_0(prob); 2167 posSlotPrices[(size_t)slot * 2 + 1] = price + GET_PRICEa_1(prob); 2168 } 2169 2170 { 2171 UInt32 delta = ((UInt32)((kEndPosModelIndex / 2 - 1) - kNumAlignBits) << kNumBitPriceShiftBits); 2172 for (slot = kEndPosModelIndex / 2; slot < distTableSize2; slot++) 2173 { 2174 posSlotPrices[(size_t)slot * 2 ] += delta; 2175 posSlotPrices[(size_t)slot * 2 + 1] += delta; 2176 delta += ((UInt32)1 << kNumBitPriceShiftBits); 2177 } 2178 } 2179 2180 { 2181 UInt32 *dp = p->distancesPrices[lps]; 2182 2183 dp[0] = posSlotPrices[0]; 2184 dp[1] = posSlotPrices[1]; 2185 dp[2] = posSlotPrices[2]; 2186 dp[3] = posSlotPrices[3]; 2187 2188 for (i = 4; i < kNumFullDistances; i += 2) 2189 { 2190 UInt32 slotPrice = posSlotPrices[GetPosSlot1(i)]; 2191 dp[i ] = slotPrice + tempPrices[i]; 2192 dp[i + 1] = slotPrice + tempPrices[i + 1]; 2193 } 2194 } 2195 } 2196 // } 2197 } 2198 2199 2200 2201 void LzmaEnc_Construct(CLzmaEnc *p) 2202 { 2203 RangeEnc_Construct(&p->rc); 2204 MatchFinder_Construct(&p->matchFinderBase); 2205 2206 #ifndef _7ZIP_ST 2207 MatchFinderMt_Construct(&p->matchFinderMt); 2208 p->matchFinderMt.MatchFinder = &p->matchFinderBase; 2209 #endif 2210 2211 { 2212 CLzmaEncProps props; 2213 LzmaEncProps_Init(&props); 2214 LzmaEnc_SetProps(p, &props); 2215 } 2216 2217 #ifndef LZMA_LOG_BSR 2218 LzmaEnc_FastPosInit(p->g_FastPos); 2219 #endif 2220 2221 LzmaEnc_InitPriceTables(p->ProbPrices); 2222 p->litProbs = NULL; 2223 p->saveState.litProbs = NULL; 2224 2225 } 2226 2227 CLzmaEncHandle LzmaEnc_Create(ISzAllocPtr alloc) 2228 { 2229 void *p; 2230 p = ISzAlloc_Alloc(alloc, sizeof(CLzmaEnc)); 2231 if (p) 2232 LzmaEnc_Construct((CLzmaEnc *)p); 2233 return p; 2234 } 2235 2236 void LzmaEnc_FreeLits(CLzmaEnc *p, ISzAllocPtr alloc) 2237 { 2238 ISzAlloc_Free(alloc, p->litProbs); 2239 ISzAlloc_Free(alloc, p->saveState.litProbs); 2240 p->litProbs = NULL; 2241 p->saveState.litProbs = NULL; 2242 } 2243 2244 void LzmaEnc_Destruct(CLzmaEnc *p, ISzAllocPtr alloc, ISzAllocPtr allocBig) 2245 { 2246 #ifndef _7ZIP_ST 2247 MatchFinderMt_Destruct(&p->matchFinderMt, allocBig); 2248 #endif 2249 2250 MatchFinder_Free(&p->matchFinderBase, allocBig); 2251 LzmaEnc_FreeLits(p, alloc); 2252 RangeEnc_Free(&p->rc, alloc); 2253 } 2254 2255 void LzmaEnc_Destroy(CLzmaEncHandle p, ISzAllocPtr alloc, ISzAllocPtr allocBig) 2256 { 2257 LzmaEnc_Destruct((CLzmaEnc *)p, alloc, allocBig); 2258 ISzAlloc_Free(alloc, p); 2259 } 2260 2261 2262 static SRes LzmaEnc_CodeOneBlock(CLzmaEnc *p, UInt32 maxPackSize, UInt32 maxUnpackSize) 2263 { 2264 UInt32 nowPos32, startPos32; 2265 if (p->needInit) 2266 { 2267 p->matchFinder.Init(p->matchFinderObj); 2268 p->needInit = 0; 2269 } 2270 2271 if (p->finished) 2272 return p->result; 2273 RINOK(CheckErrors(p)); 2274 2275 nowPos32 = (UInt32)p->nowPos64; 2276 startPos32 = nowPos32; 2277 2278 if (p->nowPos64 == 0) 2279 { 2280 unsigned numPairs; 2281 Byte curByte; 2282 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0) 2283 return Flush(p, nowPos32); 2284 ReadMatchDistances(p, &numPairs); 2285 RangeEnc_EncodeBit_0(&p->rc, &p->isMatch[kState_Start][0]); 2286 // p->state = kLiteralNextStates[p->state]; 2287 curByte = *(p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset); 2288 LitEnc_Encode(&p->rc, p->litProbs, curByte); 2289 p->additionalOffset--; 2290 nowPos32++; 2291 } 2292 2293 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) != 0) 2294 2295 for (;;) 2296 { 2297 UInt32 dist; 2298 unsigned len, posState; 2299 UInt32 range, ttt, newBound; 2300 CLzmaProb *probs; 2301 2302 if (p->fastMode) 2303 len = GetOptimumFast(p); 2304 else 2305 { 2306 unsigned oci = p->optCur; 2307 if (p->optEnd == oci) 2308 len = GetOptimum(p, nowPos32); 2309 else 2310 { 2311 const COptimal *opt = &p->opt[oci]; 2312 len = opt->len; 2313 p->backRes = opt->dist; 2314 p->optCur = oci + 1; 2315 } 2316 } 2317 2318 posState = (unsigned)nowPos32 & p->pbMask; 2319 range = p->rc.range; 2320 probs = &p->isMatch[p->state][posState]; 2321 2322 RC_BIT_PRE(&p->rc, probs) 2323 2324 dist = p->backRes; 2325 2326 #ifdef SHOW_STAT2 2327 printf("\n pos = %6X, len = %3u pos = %6u", nowPos32, len, dist); 2328 #endif 2329 2330 if (dist == MARK_LIT) 2331 { 2332 Byte curByte; 2333 const Byte *data; 2334 unsigned state; 2335 2336 RC_BIT_0(&p->rc, probs); 2337 p->rc.range = range; 2338 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset; 2339 probs = LIT_PROBS(nowPos32, *(data - 1)); 2340 curByte = *data; 2341 state = p->state; 2342 p->state = kLiteralNextStates[state]; 2343 if (IsLitState(state)) 2344 LitEnc_Encode(&p->rc, probs, curByte); 2345 else 2346 LitEnc_EncodeMatched(&p->rc, probs, curByte, *(data - p->reps[0])); 2347 } 2348 else 2349 { 2350 RC_BIT_1(&p->rc, probs); 2351 probs = &p->isRep[p->state]; 2352 RC_BIT_PRE(&p->rc, probs) 2353 2354 if (dist < LZMA_NUM_REPS) 2355 { 2356 RC_BIT_1(&p->rc, probs); 2357 probs = &p->isRepG0[p->state]; 2358 RC_BIT_PRE(&p->rc, probs) 2359 if (dist == 0) 2360 { 2361 RC_BIT_0(&p->rc, probs); 2362 probs = &p->isRep0Long[p->state][posState]; 2363 RC_BIT_PRE(&p->rc, probs) 2364 if (len != 1) 2365 { 2366 RC_BIT_1_BASE(&p->rc, probs); 2367 } 2368 else 2369 { 2370 RC_BIT_0_BASE(&p->rc, probs); 2371 p->state = kShortRepNextStates[p->state]; 2372 } 2373 } 2374 else 2375 { 2376 RC_BIT_1(&p->rc, probs); 2377 probs = &p->isRepG1[p->state]; 2378 RC_BIT_PRE(&p->rc, probs) 2379 if (dist == 1) 2380 { 2381 RC_BIT_0_BASE(&p->rc, probs); 2382 dist = p->reps[1]; 2383 } 2384 else 2385 { 2386 RC_BIT_1(&p->rc, probs); 2387 probs = &p->isRepG2[p->state]; 2388 RC_BIT_PRE(&p->rc, probs) 2389 if (dist == 2) 2390 { 2391 RC_BIT_0_BASE(&p->rc, probs); 2392 dist = p->reps[2]; 2393 } 2394 else 2395 { 2396 RC_BIT_1_BASE(&p->rc, probs); 2397 dist = p->reps[3]; 2398 p->reps[3] = p->reps[2]; 2399 } 2400 p->reps[2] = p->reps[1]; 2401 } 2402 p->reps[1] = p->reps[0]; 2403 p->reps[0] = dist; 2404 } 2405 2406 RC_NORM(&p->rc) 2407 2408 p->rc.range = range; 2409 2410 if (len != 1) 2411 { 2412 LenEnc_Encode(&p->repLenProbs, &p->rc, len - LZMA_MATCH_LEN_MIN, posState); 2413 --p->repLenEncCounter; 2414 p->state = kRepNextStates[p->state]; 2415 } 2416 } 2417 else 2418 { 2419 unsigned posSlot; 2420 RC_BIT_0(&p->rc, probs); 2421 p->rc.range = range; 2422 p->state = kMatchNextStates[p->state]; 2423 2424 LenEnc_Encode(&p->lenProbs, &p->rc, len - LZMA_MATCH_LEN_MIN, posState); 2425 // --p->lenEnc.counter; 2426 2427 dist -= LZMA_NUM_REPS; 2428 p->reps[3] = p->reps[2]; 2429 p->reps[2] = p->reps[1]; 2430 p->reps[1] = p->reps[0]; 2431 p->reps[0] = dist + 1; 2432 2433 p->matchPriceCount++; 2434 GetPosSlot(dist, posSlot); 2435 // RcTree_Encode_PosSlot(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], posSlot); 2436 { 2437 UInt32 sym = (UInt32)posSlot + (1 << kNumPosSlotBits); 2438 range = p->rc.range; 2439 probs = p->posSlotEncoder[GetLenToPosState(len)]; 2440 do 2441 { 2442 CLzmaProb *prob = probs + (sym >> kNumPosSlotBits); 2443 UInt32 bit = (sym >> (kNumPosSlotBits - 1)) & 1; 2444 sym <<= 1; 2445 RC_BIT(&p->rc, prob, bit); 2446 } 2447 while (sym < (1 << kNumPosSlotBits * 2)); 2448 p->rc.range = range; 2449 } 2450 2451 if (dist >= kStartPosModelIndex) 2452 { 2453 unsigned footerBits = ((posSlot >> 1) - 1); 2454 2455 if (dist < kNumFullDistances) 2456 { 2457 unsigned base = ((2 | (posSlot & 1)) << footerBits); 2458 RcTree_ReverseEncode(&p->rc, p->posEncoders + base, footerBits, (unsigned)(dist /* - base */)); 2459 } 2460 else 2461 { 2462 UInt32 pos2 = (dist | 0xF) << (32 - footerBits); 2463 range = p->rc.range; 2464 // RangeEnc_EncodeDirectBits(&p->rc, posReduced >> kNumAlignBits, footerBits - kNumAlignBits); 2465 /* 2466 do 2467 { 2468 range >>= 1; 2469 p->rc.low += range & (0 - ((dist >> --footerBits) & 1)); 2470 RC_NORM(&p->rc) 2471 } 2472 while (footerBits > kNumAlignBits); 2473 */ 2474 do 2475 { 2476 range >>= 1; 2477 p->rc.low += range & (0 - (pos2 >> 31)); 2478 pos2 += pos2; 2479 RC_NORM(&p->rc) 2480 } 2481 while (pos2 != 0xF0000000); 2482 2483 2484 // RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, posReduced & kAlignMask); 2485 2486 { 2487 unsigned m = 1; 2488 unsigned bit; 2489 bit = dist & 1; dist >>= 1; RC_BIT(&p->rc, p->posAlignEncoder + m, bit); m = (m << 1) + bit; 2490 bit = dist & 1; dist >>= 1; RC_BIT(&p->rc, p->posAlignEncoder + m, bit); m = (m << 1) + bit; 2491 bit = dist & 1; dist >>= 1; RC_BIT(&p->rc, p->posAlignEncoder + m, bit); m = (m << 1) + bit; 2492 bit = dist & 1; RC_BIT(&p->rc, p->posAlignEncoder + m, bit); 2493 p->rc.range = range; 2494 // p->alignPriceCount++; 2495 } 2496 } 2497 } 2498 } 2499 } 2500 2501 nowPos32 += (UInt32)len; 2502 p->additionalOffset -= len; 2503 2504 if (p->additionalOffset == 0) 2505 { 2506 UInt32 processed; 2507 2508 if (!p->fastMode) 2509 { 2510 /* 2511 if (p->alignPriceCount >= 16) // kAlignTableSize 2512 FillAlignPrices(p); 2513 if (p->matchPriceCount >= 128) 2514 FillDistancesPrices(p); 2515 if (p->lenEnc.counter <= 0) 2516 LenPriceEnc_UpdateTables(&p->lenEnc, 1 << p->pb, &p->lenProbs, p->ProbPrices); 2517 */ 2518 if (p->matchPriceCount >= 64) 2519 { 2520 FillAlignPrices(p); 2521 // { int y; for (y = 0; y < 100; y++) { 2522 FillDistancesPrices(p); 2523 // }} 2524 LenPriceEnc_UpdateTables(&p->lenEnc, 1 << p->pb, &p->lenProbs, p->ProbPrices); 2525 } 2526 if (p->repLenEncCounter <= 0) 2527 { 2528 p->repLenEncCounter = REP_LEN_COUNT; 2529 LenPriceEnc_UpdateTables(&p->repLenEnc, 1 << p->pb, &p->repLenProbs, p->ProbPrices); 2530 } 2531 } 2532 2533 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0) 2534 break; 2535 processed = nowPos32 - startPos32; 2536 2537 if (maxPackSize) 2538 { 2539 if (processed + kNumOpts + 300 >= maxUnpackSize 2540 || RangeEnc_GetProcessed_sizet(&p->rc) + kPackReserve >= maxPackSize) 2541 break; 2542 } 2543 else if (processed >= (1 << 17)) 2544 { 2545 p->nowPos64 += nowPos32 - startPos32; 2546 return CheckErrors(p); 2547 } 2548 } 2549 } 2550 2551 p->nowPos64 += nowPos32 - startPos32; 2552 return Flush(p, nowPos32); 2553 } 2554 2555 2556 2557 #define kBigHashDicLimit ((UInt32)1 << 24) 2558 2559 static SRes LzmaEnc_Alloc(CLzmaEnc *p, UInt32 keepWindowSize, ISzAllocPtr alloc, ISzAllocPtr allocBig) 2560 { 2561 UInt32 beforeSize = kNumOpts; 2562 if (!RangeEnc_Alloc(&p->rc, alloc)) 2563 return SZ_ERROR_MEM; 2564 2565 #ifndef _7ZIP_ST 2566 p->mtMode = (p->multiThread && !p->fastMode && (p->matchFinderBase.btMode != 0)); 2567 #endif 2568 2569 { 2570 unsigned lclp = p->lc + p->lp; 2571 if (!p->litProbs || !p->saveState.litProbs || p->lclp != lclp) 2572 { 2573 LzmaEnc_FreeLits(p, alloc); 2574 p->litProbs = (CLzmaProb *)ISzAlloc_Alloc(alloc, ((UInt32)0x300 << lclp) * sizeof(CLzmaProb)); 2575 p->saveState.litProbs = (CLzmaProb *)ISzAlloc_Alloc(alloc, ((UInt32)0x300 << lclp) * sizeof(CLzmaProb)); 2576 if (!p->litProbs || !p->saveState.litProbs) 2577 { 2578 LzmaEnc_FreeLits(p, alloc); 2579 return SZ_ERROR_MEM; 2580 } 2581 p->lclp = lclp; 2582 } 2583 } 2584 2585 p->matchFinderBase.bigHash = (Byte)(p->dictSize > kBigHashDicLimit ? 1 : 0); 2586 2587 if (beforeSize + p->dictSize < keepWindowSize) 2588 beforeSize = keepWindowSize - p->dictSize; 2589 2590 #ifndef _7ZIP_ST 2591 if (p->mtMode) 2592 { 2593 RINOK(MatchFinderMt_Create(&p->matchFinderMt, p->dictSize, beforeSize, p->numFastBytes, 2594 LZMA_MATCH_LEN_MAX 2595 + 1 /* 18.04 */ 2596 , allocBig)); 2597 p->matchFinderObj = &p->matchFinderMt; 2598 p->matchFinderBase.bigHash = (Byte)( 2599 (p->dictSize > kBigHashDicLimit && p->matchFinderBase.hashMask >= 0xFFFFFF) ? 1 : 0); 2600 MatchFinderMt_CreateVTable(&p->matchFinderMt, &p->matchFinder); 2601 } 2602 else 2603 #endif 2604 { 2605 if (!MatchFinder_Create(&p->matchFinderBase, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig)) 2606 return SZ_ERROR_MEM; 2607 p->matchFinderObj = &p->matchFinderBase; 2608 MatchFinder_CreateVTable(&p->matchFinderBase, &p->matchFinder); 2609 } 2610 2611 return SZ_OK; 2612 } 2613 2614 void LzmaEnc_Init(CLzmaEnc *p) 2615 { 2616 unsigned i; 2617 p->state = 0; 2618 p->reps[0] = 2619 p->reps[1] = 2620 p->reps[2] = 2621 p->reps[3] = 1; 2622 2623 RangeEnc_Init(&p->rc); 2624 2625 for (i = 0; i < (1 << kNumAlignBits); i++) 2626 p->posAlignEncoder[i] = kProbInitValue; 2627 2628 for (i = 0; i < kNumStates; i++) 2629 { 2630 unsigned j; 2631 for (j = 0; j < LZMA_NUM_PB_STATES_MAX; j++) 2632 { 2633 p->isMatch[i][j] = kProbInitValue; 2634 p->isRep0Long[i][j] = kProbInitValue; 2635 } 2636 p->isRep[i] = kProbInitValue; 2637 p->isRepG0[i] = kProbInitValue; 2638 p->isRepG1[i] = kProbInitValue; 2639 p->isRepG2[i] = kProbInitValue; 2640 } 2641 2642 { 2643 for (i = 0; i < kNumLenToPosStates; i++) 2644 { 2645 CLzmaProb *probs = p->posSlotEncoder[i]; 2646 unsigned j; 2647 for (j = 0; j < (1 << kNumPosSlotBits); j++) 2648 probs[j] = kProbInitValue; 2649 } 2650 } 2651 { 2652 for (i = 0; i < kNumFullDistances; i++) 2653 p->posEncoders[i] = kProbInitValue; 2654 } 2655 2656 { 2657 UInt32 num = (UInt32)0x300 << (p->lp + p->lc); 2658 UInt32 k; 2659 CLzmaProb *probs = p->litProbs; 2660 for (k = 0; k < num; k++) 2661 probs[k] = kProbInitValue; 2662 } 2663 2664 2665 LenEnc_Init(&p->lenProbs); 2666 LenEnc_Init(&p->repLenProbs); 2667 2668 p->optEnd = 0; 2669 p->optCur = 0; 2670 2671 { 2672 for (i = 0; i < kNumOpts; i++) 2673 p->opt[i].price = kInfinityPrice; 2674 } 2675 2676 p->additionalOffset = 0; 2677 2678 p->pbMask = (1 << p->pb) - 1; 2679 p->lpMask = ((UInt32)0x100 << p->lp) - ((unsigned)0x100 >> p->lc); 2680 } 2681 2682 2683 void LzmaEnc_InitPrices(CLzmaEnc *p) 2684 { 2685 if (!p->fastMode) 2686 { 2687 FillDistancesPrices(p); 2688 FillAlignPrices(p); 2689 } 2690 2691 p->lenEnc.tableSize = 2692 p->repLenEnc.tableSize = 2693 p->numFastBytes + 1 - LZMA_MATCH_LEN_MIN; 2694 2695 p->repLenEncCounter = REP_LEN_COUNT; 2696 2697 LenPriceEnc_UpdateTables(&p->lenEnc, 1 << p->pb, &p->lenProbs, p->ProbPrices); 2698 LenPriceEnc_UpdateTables(&p->repLenEnc, 1 << p->pb, &p->repLenProbs, p->ProbPrices); 2699 } 2700 2701 static SRes LzmaEnc_AllocAndInit(CLzmaEnc *p, UInt32 keepWindowSize, ISzAllocPtr alloc, ISzAllocPtr allocBig) 2702 { 2703 unsigned i; 2704 for (i = kEndPosModelIndex / 2; i < kDicLogSizeMax; i++) 2705 if (p->dictSize <= ((UInt32)1 << i)) 2706 break; 2707 p->distTableSize = i * 2; 2708 2709 p->finished = False; 2710 p->result = SZ_OK; 2711 RINOK(LzmaEnc_Alloc(p, keepWindowSize, alloc, allocBig)); 2712 LzmaEnc_Init(p); 2713 LzmaEnc_InitPrices(p); 2714 p->nowPos64 = 0; 2715 return SZ_OK; 2716 } 2717 2718 static SRes LzmaEnc_Prepare(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream, 2719 ISzAllocPtr alloc, ISzAllocPtr allocBig) 2720 { 2721 CLzmaEnc *p = (CLzmaEnc *)pp; 2722 p->matchFinderBase.stream = inStream; 2723 p->needInit = 1; 2724 p->rc.outStream = outStream; 2725 return LzmaEnc_AllocAndInit(p, 0, alloc, allocBig); 2726 } 2727 2728 SRes LzmaEnc_PrepareForLzma2(CLzmaEncHandle pp, 2729 ISeqInStream *inStream, UInt32 keepWindowSize, 2730 ISzAllocPtr alloc, ISzAllocPtr allocBig) 2731 { 2732 CLzmaEnc *p = (CLzmaEnc *)pp; 2733 p->matchFinderBase.stream = inStream; 2734 p->needInit = 1; 2735 return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig); 2736 } 2737 2738 static void LzmaEnc_SetInputBuf(CLzmaEnc *p, const Byte *src, SizeT srcLen) 2739 { 2740 p->matchFinderBase.directInput = 1; 2741 p->matchFinderBase.bufferBase = (Byte *)src; 2742 p->matchFinderBase.directInputRem = srcLen; 2743 } 2744 2745 SRes LzmaEnc_MemPrepare(CLzmaEncHandle pp, const Byte *src, SizeT srcLen, 2746 UInt32 keepWindowSize, ISzAllocPtr alloc, ISzAllocPtr allocBig) 2747 { 2748 CLzmaEnc *p = (CLzmaEnc *)pp; 2749 LzmaEnc_SetInputBuf(p, src, srcLen); 2750 p->needInit = 1; 2751 2752 LzmaEnc_SetDataSize(pp, srcLen); 2753 return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig); 2754 } 2755 2756 void LzmaEnc_Finish(CLzmaEncHandle pp) 2757 { 2758 #ifndef _7ZIP_ST 2759 CLzmaEnc *p = (CLzmaEnc *)pp; 2760 if (p->mtMode) 2761 MatchFinderMt_ReleaseStream(&p->matchFinderMt); 2762 #else 2763 UNUSED_VAR(pp); 2764 #endif 2765 } 2766 2767 2768 typedef struct 2769 { 2770 ISeqOutStream vt; 2771 Byte *data; 2772 SizeT rem; 2773 BoolInt overflow; 2774 } CLzmaEnc_SeqOutStreamBuf; 2775 2776 static size_t SeqOutStreamBuf_Write(const ISeqOutStream *pp, const void *data, size_t size) 2777 { 2778 CLzmaEnc_SeqOutStreamBuf *p = CONTAINER_FROM_VTBL(pp, CLzmaEnc_SeqOutStreamBuf, vt); 2779 if (p->rem < size) 2780 { 2781 size = p->rem; 2782 p->overflow = True; 2783 } 2784 memcpy(p->data, data, size); 2785 p->rem -= size; 2786 p->data += size; 2787 return size; 2788 } 2789 2790 2791 UInt32 LzmaEnc_GetNumAvailableBytes(CLzmaEncHandle pp) 2792 { 2793 const CLzmaEnc *p = (CLzmaEnc *)pp; 2794 return p->matchFinder.GetNumAvailableBytes(p->matchFinderObj); 2795 } 2796 2797 2798 const Byte *LzmaEnc_GetCurBuf(CLzmaEncHandle pp) 2799 { 2800 const CLzmaEnc *p = (CLzmaEnc *)pp; 2801 return p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset; 2802 } 2803 2804 2805 SRes LzmaEnc_CodeOneMemBlock(CLzmaEncHandle pp, BoolInt reInit, 2806 Byte *dest, size_t *destLen, UInt32 desiredPackSize, UInt32 *unpackSize) 2807 { 2808 CLzmaEnc *p = (CLzmaEnc *)pp; 2809 UInt64 nowPos64; 2810 SRes res; 2811 CLzmaEnc_SeqOutStreamBuf outStream; 2812 2813 outStream.vt.Write = SeqOutStreamBuf_Write; 2814 outStream.data = dest; 2815 outStream.rem = *destLen; 2816 outStream.overflow = False; 2817 2818 p->writeEndMark = False; 2819 p->finished = False; 2820 p->result = SZ_OK; 2821 2822 if (reInit) 2823 LzmaEnc_Init(p); 2824 LzmaEnc_InitPrices(p); 2825 2826 nowPos64 = p->nowPos64; 2827 RangeEnc_Init(&p->rc); 2828 p->rc.outStream = &outStream.vt; 2829 2830 if (desiredPackSize == 0) 2831 return SZ_ERROR_OUTPUT_EOF; 2832 2833 res = LzmaEnc_CodeOneBlock(p, desiredPackSize, *unpackSize); 2834 2835 *unpackSize = (UInt32)(p->nowPos64 - nowPos64); 2836 *destLen -= outStream.rem; 2837 if (outStream.overflow) 2838 return SZ_ERROR_OUTPUT_EOF; 2839 2840 return res; 2841 } 2842 2843 2844 static SRes LzmaEnc_Encode2(CLzmaEnc *p, ICompressProgress *progress) 2845 { 2846 SRes res = SZ_OK; 2847 2848 #ifndef _7ZIP_ST 2849 Byte allocaDummy[0x300]; 2850 allocaDummy[0] = 0; 2851 allocaDummy[1] = allocaDummy[0]; 2852 #endif 2853 2854 for (;;) 2855 { 2856 res = LzmaEnc_CodeOneBlock(p, 0, 0); 2857 if (res != SZ_OK || p->finished) 2858 break; 2859 if (progress) 2860 { 2861 res = ICompressProgress_Progress(progress, p->nowPos64, RangeEnc_GetProcessed(&p->rc)); 2862 if (res != SZ_OK) 2863 { 2864 res = SZ_ERROR_PROGRESS; 2865 break; 2866 } 2867 } 2868 } 2869 2870 LzmaEnc_Finish(p); 2871 2872 /* 2873 if (res == SZ_OK && !Inline_MatchFinder_IsFinishedOK(&p->matchFinderBase)) 2874 res = SZ_ERROR_FAIL; 2875 } 2876 */ 2877 2878 return res; 2879 } 2880 2881 2882 SRes LzmaEnc_Encode(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream, ICompressProgress *progress, 2883 ISzAllocPtr alloc, ISzAllocPtr allocBig) 2884 { 2885 RINOK(LzmaEnc_Prepare(pp, outStream, inStream, alloc, allocBig)); 2886 return LzmaEnc_Encode2((CLzmaEnc *)pp, progress); 2887 } 2888 2889 2890 SRes LzmaEnc_WriteProperties(CLzmaEncHandle pp, Byte *props, SizeT *size) 2891 { 2892 CLzmaEnc *p = (CLzmaEnc *)pp; 2893 unsigned i; 2894 UInt32 dictSize = p->dictSize; 2895 if (*size < LZMA_PROPS_SIZE) 2896 return SZ_ERROR_PARAM; 2897 *size = LZMA_PROPS_SIZE; 2898 props[0] = (Byte)((p->pb * 5 + p->lp) * 9 + p->lc); 2899 2900 if (dictSize >= ((UInt32)1 << 22)) 2901 { 2902 UInt32 kDictMask = ((UInt32)1 << 20) - 1; 2903 if (dictSize < (UInt32)0xFFFFFFFF - kDictMask) 2904 dictSize = (dictSize + kDictMask) & ~kDictMask; 2905 } 2906 else for (i = 11; i <= 30; i++) 2907 { 2908 if (dictSize <= ((UInt32)2 << i)) { dictSize = (2 << i); break; } 2909 if (dictSize <= ((UInt32)3 << i)) { dictSize = (3 << i); break; } 2910 } 2911 2912 for (i = 0; i < 4; i++) 2913 props[1 + i] = (Byte)(dictSize >> (8 * i)); 2914 return SZ_OK; 2915 } 2916 2917 2918 unsigned LzmaEnc_IsWriteEndMark(CLzmaEncHandle pp) 2919 { 2920 return ((CLzmaEnc *)pp)->writeEndMark; 2921 } 2922 2923 2924 SRes LzmaEnc_MemEncode(CLzmaEncHandle pp, Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen, 2925 int writeEndMark, ICompressProgress *progress, ISzAllocPtr alloc, ISzAllocPtr allocBig) 2926 { 2927 SRes res; 2928 CLzmaEnc *p = (CLzmaEnc *)pp; 2929 2930 CLzmaEnc_SeqOutStreamBuf outStream; 2931 2932 outStream.vt.Write = SeqOutStreamBuf_Write; 2933 outStream.data = dest; 2934 outStream.rem = *destLen; 2935 outStream.overflow = False; 2936 2937 p->writeEndMark = writeEndMark; 2938 p->rc.outStream = &outStream.vt; 2939 2940 res = LzmaEnc_MemPrepare(pp, src, srcLen, 0, alloc, allocBig); 2941 2942 if (res == SZ_OK) 2943 { 2944 res = LzmaEnc_Encode2(p, progress); 2945 if (res == SZ_OK && p->nowPos64 != srcLen) 2946 res = SZ_ERROR_FAIL; 2947 } 2948 2949 *destLen -= outStream.rem; 2950 if (outStream.overflow) 2951 return SZ_ERROR_OUTPUT_EOF; 2952 return res; 2953 } 2954 2955 2956 SRes LzmaEncode(Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen, 2957 const CLzmaEncProps *props, Byte *propsEncoded, SizeT *propsSize, int writeEndMark, 2958 ICompressProgress *progress, ISzAllocPtr alloc, ISzAllocPtr allocBig) 2959 { 2960 CLzmaEnc *p = (CLzmaEnc *)LzmaEnc_Create(alloc); 2961 SRes res; 2962 if (!p) 2963 return SZ_ERROR_MEM; 2964 2965 res = LzmaEnc_SetProps(p, props); 2966 if (res == SZ_OK) 2967 { 2968 res = LzmaEnc_WriteProperties(p, propsEncoded, propsSize); 2969 if (res == SZ_OK) 2970 res = LzmaEnc_MemEncode(p, dest, destLen, src, srcLen, 2971 writeEndMark, progress, alloc, allocBig); 2972 } 2973 2974 LzmaEnc_Destroy(p, alloc, allocBig); 2975 return res; 2976 } 2977