1 /* LzmaEnc.c -- LZMA Encoder 2 2014-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 kBlockSizeMax ((1 << LZMA_NUM_BLOCK_SIZE_BITS) - 1) 27 28 #define kBlockSize (9 << 10) 29 #define kUnpackBlockSize (1 << 18) 30 #define kMatchArraySize (1 << 21) 31 #define kMatchRecordMaxSize ((LZMA_MATCH_LEN_MAX * 2 + 3) * LZMA_MATCH_LEN_MAX) 32 33 #define kNumMaxDirectBits (31) 34 35 #define kNumTopBits 24 36 #define kTopValue ((UInt32)1 << kNumTopBits) 37 38 #define kNumBitModelTotalBits 11 39 #define kBitModelTotal (1 << kNumBitModelTotalBits) 40 #define kNumMoveBits 5 41 #define kProbInitValue (kBitModelTotal >> 1) 42 43 #define kNumMoveReducingBits 4 44 #define kNumBitPriceShiftBits 4 45 #define kBitPrice (1 << kNumBitPriceShiftBits) 46 47 void LzmaEncProps_Init(CLzmaEncProps *p) 48 { 49 p->level = 5; 50 p->dictSize = p->mc = 0; 51 p->reduceSize = (UInt64)(Int64)-1; 52 p->lc = p->lp = p->pb = p->algo = p->fb = p->btMode = p->numHashBytes = p->numThreads = -1; 53 p->writeEndMark = 0; 54 } 55 56 void LzmaEncProps_Normalize(CLzmaEncProps *p) 57 { 58 int level = p->level; 59 if (level < 0) level = 5; 60 p->level = level; 61 if (p->dictSize == 0) p->dictSize = (level <= 5 ? (1 << (level * 2 + 14)) : (level == 6 ? (1 << 25) : (1 << 26))); 62 if (p->dictSize > p->reduceSize) 63 { 64 unsigned i; 65 for (i = 11; i <= 30; i++) 66 { 67 if ((UInt32)p->reduceSize <= ((UInt32)2 << i)) { p->dictSize = ((UInt32)2 << i); break; } 68 if ((UInt32)p->reduceSize <= ((UInt32)3 << i)) { p->dictSize = ((UInt32)3 << i); break; } 69 } 70 } 71 if (p->lc < 0) p->lc = 3; 72 if (p->lp < 0) p->lp = 0; 73 if (p->pb < 0) p->pb = 2; 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 if (p->numThreads < 0) 80 p->numThreads = 81 #ifndef _7ZIP_ST 82 ((p->btMode && p->algo) ? 2 : 1); 83 #else 84 1; 85 #endif 86 } 87 88 UInt32 LzmaEncProps_GetDictSize(const CLzmaEncProps *props2) 89 { 90 CLzmaEncProps props = *props2; 91 LzmaEncProps_Normalize(&props); 92 return props.dictSize; 93 } 94 95 /* #define LZMA_LOG_BSR */ 96 /* Define it for Intel's CPU */ 97 98 99 #ifdef LZMA_LOG_BSR 100 101 #define kDicLogSizeMaxCompress 30 102 103 #define BSR2_RET(pos, res) { unsigned long i; _BitScanReverse(&i, (pos)); res = (i + i) + ((pos >> (i - 1)) & 1); } 104 105 UInt32 GetPosSlot1(UInt32 pos) 106 { 107 UInt32 res; 108 BSR2_RET(pos, res); 109 return res; 110 } 111 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); } 112 #define GetPosSlot(pos, res) { if (pos < 2) res = pos; else BSR2_RET(pos, res); } 113 114 #else 115 116 #define kNumLogBits (9 + (int)sizeof(size_t) / 2) 117 #define kDicLogSizeMaxCompress ((kNumLogBits - 1) * 2 + 7) 118 119 void LzmaEnc_FastPosInit(Byte *g_FastPos) 120 { 121 int c = 2, slotFast; 122 g_FastPos[0] = 0; 123 g_FastPos[1] = 1; 124 125 for (slotFast = 2; slotFast < kNumLogBits * 2; slotFast++) 126 { 127 UInt32 k = (1 << ((slotFast >> 1) - 1)); 128 UInt32 j; 129 for (j = 0; j < k; j++, c++) 130 g_FastPos[c] = (Byte)slotFast; 131 } 132 } 133 134 #define BSR2_RET(pos, res) { UInt32 i = 6 + ((kNumLogBits - 1) & \ 135 (0 - (((((UInt32)1 << (kNumLogBits + 6)) - 1) - pos) >> 31))); \ 136 res = p->g_FastPos[pos >> i] + (i * 2); } 137 /* 138 #define BSR2_RET(pos, res) { res = (pos < (1 << (kNumLogBits + 6))) ? \ 139 p->g_FastPos[pos >> 6] + 12 : \ 140 p->g_FastPos[pos >> (6 + kNumLogBits - 1)] + (6 + (kNumLogBits - 1)) * 2; } 141 */ 142 143 #define GetPosSlot1(pos) p->g_FastPos[pos] 144 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); } 145 #define GetPosSlot(pos, res) { if (pos < kNumFullDistances) res = p->g_FastPos[pos]; else BSR2_RET(pos, res); } 146 147 #endif 148 149 150 #define LZMA_NUM_REPS 4 151 152 typedef unsigned CState; 153 154 typedef struct 155 { 156 UInt32 price; 157 158 CState state; 159 int prev1IsChar; 160 int prev2; 161 162 UInt32 posPrev2; 163 UInt32 backPrev2; 164 165 UInt32 posPrev; 166 UInt32 backPrev; 167 UInt32 backs[LZMA_NUM_REPS]; 168 } COptimal; 169 170 #define kNumOpts (1 << 12) 171 172 #define kNumLenToPosStates 4 173 #define kNumPosSlotBits 6 174 #define kDicLogSizeMin 0 175 #define kDicLogSizeMax 32 176 #define kDistTableSizeMax (kDicLogSizeMax * 2) 177 178 179 #define kNumAlignBits 4 180 #define kAlignTableSize (1 << kNumAlignBits) 181 #define kAlignMask (kAlignTableSize - 1) 182 183 #define kStartPosModelIndex 4 184 #define kEndPosModelIndex 14 185 #define kNumPosModels (kEndPosModelIndex - kStartPosModelIndex) 186 187 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1)) 188 189 #ifdef _LZMA_PROB32 190 #define CLzmaProb UInt32 191 #else 192 #define CLzmaProb UInt16 193 #endif 194 195 #define LZMA_PB_MAX 4 196 #define LZMA_LC_MAX 8 197 #define LZMA_LP_MAX 4 198 199 #define LZMA_NUM_PB_STATES_MAX (1 << LZMA_PB_MAX) 200 201 202 #define kLenNumLowBits 3 203 #define kLenNumLowSymbols (1 << kLenNumLowBits) 204 #define kLenNumMidBits 3 205 #define kLenNumMidSymbols (1 << kLenNumMidBits) 206 #define kLenNumHighBits 8 207 #define kLenNumHighSymbols (1 << kLenNumHighBits) 208 209 #define kLenNumSymbolsTotal (kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols) 210 211 #define LZMA_MATCH_LEN_MIN 2 212 #define LZMA_MATCH_LEN_MAX (LZMA_MATCH_LEN_MIN + kLenNumSymbolsTotal - 1) 213 214 #define kNumStates 12 215 216 typedef struct 217 { 218 CLzmaProb choice; 219 CLzmaProb choice2; 220 CLzmaProb low[LZMA_NUM_PB_STATES_MAX << kLenNumLowBits]; 221 CLzmaProb mid[LZMA_NUM_PB_STATES_MAX << kLenNumMidBits]; 222 CLzmaProb high[kLenNumHighSymbols]; 223 } CLenEnc; 224 225 typedef struct 226 { 227 CLenEnc p; 228 UInt32 prices[LZMA_NUM_PB_STATES_MAX][kLenNumSymbolsTotal]; 229 UInt32 tableSize; 230 UInt32 counters[LZMA_NUM_PB_STATES_MAX]; 231 } CLenPriceEnc; 232 233 typedef struct 234 { 235 UInt32 range; 236 Byte cache; 237 UInt64 low; 238 UInt64 cacheSize; 239 Byte *buf; 240 Byte *bufLim; 241 Byte *bufBase; 242 ISeqOutStream *outStream; 243 UInt64 processed; 244 SRes res; 245 } CRangeEnc; 246 247 typedef struct 248 { 249 CLzmaProb *litProbs; 250 251 CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX]; 252 CLzmaProb isRep[kNumStates]; 253 CLzmaProb isRepG0[kNumStates]; 254 CLzmaProb isRepG1[kNumStates]; 255 CLzmaProb isRepG2[kNumStates]; 256 CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX]; 257 258 CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits]; 259 CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex]; 260 CLzmaProb posAlignEncoder[1 << kNumAlignBits]; 261 262 CLenPriceEnc lenEnc; 263 CLenPriceEnc repLenEnc; 264 265 UInt32 reps[LZMA_NUM_REPS]; 266 UInt32 state; 267 } CSaveState; 268 269 typedef struct 270 { 271 IMatchFinder matchFinder; 272 void *matchFinderObj; 273 274 #ifndef _7ZIP_ST 275 Bool mtMode; 276 CMatchFinderMt matchFinderMt; 277 #endif 278 279 CMatchFinder matchFinderBase; 280 281 #ifndef _7ZIP_ST 282 Byte pad[128]; 283 #endif 284 285 UInt32 optimumEndIndex; 286 UInt32 optimumCurrentIndex; 287 288 UInt32 longestMatchLength; 289 UInt32 numPairs; 290 UInt32 numAvail; 291 COptimal opt[kNumOpts]; 292 293 #ifndef LZMA_LOG_BSR 294 Byte g_FastPos[1 << kNumLogBits]; 295 #endif 296 297 UInt32 ProbPrices[kBitModelTotal >> kNumMoveReducingBits]; 298 UInt32 matches[LZMA_MATCH_LEN_MAX * 2 + 2 + 1]; 299 UInt32 numFastBytes; 300 UInt32 additionalOffset; 301 UInt32 reps[LZMA_NUM_REPS]; 302 UInt32 state; 303 304 UInt32 posSlotPrices[kNumLenToPosStates][kDistTableSizeMax]; 305 UInt32 distancesPrices[kNumLenToPosStates][kNumFullDistances]; 306 UInt32 alignPrices[kAlignTableSize]; 307 UInt32 alignPriceCount; 308 309 UInt32 distTableSize; 310 311 unsigned lc, lp, pb; 312 unsigned lpMask, pbMask; 313 314 CLzmaProb *litProbs; 315 316 CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX]; 317 CLzmaProb isRep[kNumStates]; 318 CLzmaProb isRepG0[kNumStates]; 319 CLzmaProb isRepG1[kNumStates]; 320 CLzmaProb isRepG2[kNumStates]; 321 CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX]; 322 323 CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits]; 324 CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex]; 325 CLzmaProb posAlignEncoder[1 << kNumAlignBits]; 326 327 CLenPriceEnc lenEnc; 328 CLenPriceEnc repLenEnc; 329 330 unsigned lclp; 331 332 Bool fastMode; 333 334 CRangeEnc rc; 335 336 Bool writeEndMark; 337 UInt64 nowPos64; 338 UInt32 matchPriceCount; 339 Bool finished; 340 Bool multiThread; 341 342 SRes result; 343 UInt32 dictSize; 344 345 int needInit; 346 347 CSaveState saveState; 348 } CLzmaEnc; 349 350 void LzmaEnc_SaveState(CLzmaEncHandle pp) 351 { 352 CLzmaEnc *p = (CLzmaEnc *)pp; 353 CSaveState *dest = &p->saveState; 354 int i; 355 dest->lenEnc = p->lenEnc; 356 dest->repLenEnc = p->repLenEnc; 357 dest->state = p->state; 358 359 for (i = 0; i < kNumStates; i++) 360 { 361 memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i])); 362 memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i])); 363 } 364 for (i = 0; i < kNumLenToPosStates; i++) 365 memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i])); 366 memcpy(dest->isRep, p->isRep, sizeof(p->isRep)); 367 memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0)); 368 memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1)); 369 memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2)); 370 memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders)); 371 memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder)); 372 memcpy(dest->reps, p->reps, sizeof(p->reps)); 373 memcpy(dest->litProbs, p->litProbs, (0x300 << p->lclp) * sizeof(CLzmaProb)); 374 } 375 376 void LzmaEnc_RestoreState(CLzmaEncHandle pp) 377 { 378 CLzmaEnc *dest = (CLzmaEnc *)pp; 379 const CSaveState *p = &dest->saveState; 380 int i; 381 dest->lenEnc = p->lenEnc; 382 dest->repLenEnc = p->repLenEnc; 383 dest->state = p->state; 384 385 for (i = 0; i < kNumStates; i++) 386 { 387 memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i])); 388 memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i])); 389 } 390 for (i = 0; i < kNumLenToPosStates; i++) 391 memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i])); 392 memcpy(dest->isRep, p->isRep, sizeof(p->isRep)); 393 memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0)); 394 memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1)); 395 memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2)); 396 memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders)); 397 memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder)); 398 memcpy(dest->reps, p->reps, sizeof(p->reps)); 399 memcpy(dest->litProbs, p->litProbs, (0x300 << dest->lclp) * sizeof(CLzmaProb)); 400 } 401 402 SRes LzmaEnc_SetProps(CLzmaEncHandle pp, const CLzmaEncProps *props2) 403 { 404 CLzmaEnc *p = (CLzmaEnc *)pp; 405 CLzmaEncProps props = *props2; 406 LzmaEncProps_Normalize(&props); 407 408 if (props.lc > LZMA_LC_MAX || props.lp > LZMA_LP_MAX || props.pb > LZMA_PB_MAX || 409 props.dictSize > ((UInt32)1 << kDicLogSizeMaxCompress) || props.dictSize > ((UInt32)1 << 30)) 410 return SZ_ERROR_PARAM; 411 p->dictSize = props.dictSize; 412 { 413 unsigned fb = props.fb; 414 if (fb < 5) 415 fb = 5; 416 if (fb > LZMA_MATCH_LEN_MAX) 417 fb = LZMA_MATCH_LEN_MAX; 418 p->numFastBytes = fb; 419 } 420 p->lc = props.lc; 421 p->lp = props.lp; 422 p->pb = props.pb; 423 p->fastMode = (props.algo == 0); 424 p->matchFinderBase.btMode = props.btMode; 425 { 426 UInt32 numHashBytes = 4; 427 if (props.btMode) 428 { 429 if (props.numHashBytes < 2) 430 numHashBytes = 2; 431 else if (props.numHashBytes < 4) 432 numHashBytes = props.numHashBytes; 433 } 434 p->matchFinderBase.numHashBytes = numHashBytes; 435 } 436 437 p->matchFinderBase.cutValue = props.mc; 438 439 p->writeEndMark = props.writeEndMark; 440 441 #ifndef _7ZIP_ST 442 /* 443 if (newMultiThread != _multiThread) 444 { 445 ReleaseMatchFinder(); 446 _multiThread = newMultiThread; 447 } 448 */ 449 p->multiThread = (props.numThreads > 1); 450 #endif 451 452 return SZ_OK; 453 } 454 455 static const int kLiteralNextStates[kNumStates] = {0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5}; 456 static const int kMatchNextStates[kNumStates] = {7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10}; 457 static const int kRepNextStates[kNumStates] = {8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11}; 458 static const int kShortRepNextStates[kNumStates]= {9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11}; 459 460 #define IsCharState(s) ((s) < 7) 461 462 #define GetLenToPosState(len) (((len) < kNumLenToPosStates + 1) ? (len) - 2 : kNumLenToPosStates - 1) 463 464 #define kInfinityPrice (1 << 30) 465 466 static void RangeEnc_Construct(CRangeEnc *p) 467 { 468 p->outStream = 0; 469 p->bufBase = 0; 470 } 471 472 #define RangeEnc_GetProcessed(p) ((p)->processed + ((p)->buf - (p)->bufBase) + (p)->cacheSize) 473 474 #define RC_BUF_SIZE (1 << 16) 475 static int RangeEnc_Alloc(CRangeEnc *p, ISzAlloc *alloc) 476 { 477 if (p->bufBase == 0) 478 { 479 p->bufBase = (Byte *)alloc->Alloc(alloc, RC_BUF_SIZE); 480 if (p->bufBase == 0) 481 return 0; 482 p->bufLim = p->bufBase + RC_BUF_SIZE; 483 } 484 return 1; 485 } 486 487 static void RangeEnc_Free(CRangeEnc *p, ISzAlloc *alloc) 488 { 489 alloc->Free(alloc, p->bufBase); 490 p->bufBase = 0; 491 } 492 493 static void RangeEnc_Init(CRangeEnc *p) 494 { 495 /* Stream.Init(); */ 496 p->low = 0; 497 p->range = 0xFFFFFFFF; 498 p->cacheSize = 1; 499 p->cache = 0; 500 501 p->buf = p->bufBase; 502 503 p->processed = 0; 504 p->res = SZ_OK; 505 } 506 507 static void RangeEnc_FlushStream(CRangeEnc *p) 508 { 509 size_t num; 510 if (p->res != SZ_OK) 511 return; 512 num = p->buf - p->bufBase; 513 if (num != p->outStream->Write(p->outStream, p->bufBase, num)) 514 p->res = SZ_ERROR_WRITE; 515 p->processed += num; 516 p->buf = p->bufBase; 517 } 518 519 static void MY_FAST_CALL RangeEnc_ShiftLow(CRangeEnc *p) 520 { 521 if ((UInt32)p->low < (UInt32)0xFF000000 || (unsigned)(p->low >> 32) != 0) 522 { 523 Byte temp = p->cache; 524 do 525 { 526 Byte *buf = p->buf; 527 *buf++ = (Byte)(temp + (Byte)(p->low >> 32)); 528 p->buf = buf; 529 if (buf == p->bufLim) 530 RangeEnc_FlushStream(p); 531 temp = 0xFF; 532 } 533 while (--p->cacheSize != 0); 534 p->cache = (Byte)((UInt32)p->low >> 24); 535 } 536 p->cacheSize++; 537 p->low = (UInt32)p->low << 8; 538 } 539 540 static void RangeEnc_FlushData(CRangeEnc *p) 541 { 542 int i; 543 for (i = 0; i < 5; i++) 544 RangeEnc_ShiftLow(p); 545 } 546 547 static void RangeEnc_EncodeDirectBits(CRangeEnc *p, UInt32 value, unsigned numBits) 548 { 549 do 550 { 551 p->range >>= 1; 552 p->low += p->range & (0 - ((value >> --numBits) & 1)); 553 if (p->range < kTopValue) 554 { 555 p->range <<= 8; 556 RangeEnc_ShiftLow(p); 557 } 558 } 559 while (numBits != 0); 560 } 561 562 static void RangeEnc_EncodeBit(CRangeEnc *p, CLzmaProb *prob, UInt32 symbol) 563 { 564 UInt32 ttt = *prob; 565 UInt32 newBound = (p->range >> kNumBitModelTotalBits) * ttt; 566 if (symbol == 0) 567 { 568 p->range = newBound; 569 ttt += (kBitModelTotal - ttt) >> kNumMoveBits; 570 } 571 else 572 { 573 p->low += newBound; 574 p->range -= newBound; 575 ttt -= ttt >> kNumMoveBits; 576 } 577 *prob = (CLzmaProb)ttt; 578 if (p->range < kTopValue) 579 { 580 p->range <<= 8; 581 RangeEnc_ShiftLow(p); 582 } 583 } 584 585 static void LitEnc_Encode(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol) 586 { 587 symbol |= 0x100; 588 do 589 { 590 RangeEnc_EncodeBit(p, probs + (symbol >> 8), (symbol >> 7) & 1); 591 symbol <<= 1; 592 } 593 while (symbol < 0x10000); 594 } 595 596 static void LitEnc_EncodeMatched(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol, UInt32 matchByte) 597 { 598 UInt32 offs = 0x100; 599 symbol |= 0x100; 600 do 601 { 602 matchByte <<= 1; 603 RangeEnc_EncodeBit(p, probs + (offs + (matchByte & offs) + (symbol >> 8)), (symbol >> 7) & 1); 604 symbol <<= 1; 605 offs &= ~(matchByte ^ symbol); 606 } 607 while (symbol < 0x10000); 608 } 609 610 void LzmaEnc_InitPriceTables(UInt32 *ProbPrices) 611 { 612 UInt32 i; 613 for (i = (1 << kNumMoveReducingBits) / 2; i < kBitModelTotal; i += (1 << kNumMoveReducingBits)) 614 { 615 const int kCyclesBits = kNumBitPriceShiftBits; 616 UInt32 w = i; 617 UInt32 bitCount = 0; 618 int j; 619 for (j = 0; j < kCyclesBits; j++) 620 { 621 w = w * w; 622 bitCount <<= 1; 623 while (w >= ((UInt32)1 << 16)) 624 { 625 w >>= 1; 626 bitCount++; 627 } 628 } 629 ProbPrices[i >> kNumMoveReducingBits] = ((kNumBitModelTotalBits << kCyclesBits) - 15 - bitCount); 630 } 631 } 632 633 634 #define GET_PRICE(prob, symbol) \ 635 p->ProbPrices[((prob) ^ (((-(int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits]; 636 637 #define GET_PRICEa(prob, symbol) \ 638 ProbPrices[((prob) ^ ((-((int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits]; 639 640 #define GET_PRICE_0(prob) p->ProbPrices[(prob) >> kNumMoveReducingBits] 641 #define GET_PRICE_1(prob) p->ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits] 642 643 #define GET_PRICE_0a(prob) ProbPrices[(prob) >> kNumMoveReducingBits] 644 #define GET_PRICE_1a(prob) ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits] 645 646 static UInt32 LitEnc_GetPrice(const CLzmaProb *probs, UInt32 symbol, UInt32 *ProbPrices) 647 { 648 UInt32 price = 0; 649 symbol |= 0x100; 650 do 651 { 652 price += GET_PRICEa(probs[symbol >> 8], (symbol >> 7) & 1); 653 symbol <<= 1; 654 } 655 while (symbol < 0x10000); 656 return price; 657 } 658 659 static UInt32 LitEnc_GetPriceMatched(const CLzmaProb *probs, UInt32 symbol, UInt32 matchByte, UInt32 *ProbPrices) 660 { 661 UInt32 price = 0; 662 UInt32 offs = 0x100; 663 symbol |= 0x100; 664 do 665 { 666 matchByte <<= 1; 667 price += GET_PRICEa(probs[offs + (matchByte & offs) + (symbol >> 8)], (symbol >> 7) & 1); 668 symbol <<= 1; 669 offs &= ~(matchByte ^ symbol); 670 } 671 while (symbol < 0x10000); 672 return price; 673 } 674 675 676 static void RcTree_Encode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol) 677 { 678 UInt32 m = 1; 679 int i; 680 for (i = numBitLevels; i != 0;) 681 { 682 UInt32 bit; 683 i--; 684 bit = (symbol >> i) & 1; 685 RangeEnc_EncodeBit(rc, probs + m, bit); 686 m = (m << 1) | bit; 687 } 688 } 689 690 static void RcTree_ReverseEncode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol) 691 { 692 UInt32 m = 1; 693 int i; 694 for (i = 0; i < numBitLevels; i++) 695 { 696 UInt32 bit = symbol & 1; 697 RangeEnc_EncodeBit(rc, probs + m, bit); 698 m = (m << 1) | bit; 699 symbol >>= 1; 700 } 701 } 702 703 static UInt32 RcTree_GetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, UInt32 *ProbPrices) 704 { 705 UInt32 price = 0; 706 symbol |= (1 << numBitLevels); 707 while (symbol != 1) 708 { 709 price += GET_PRICEa(probs[symbol >> 1], symbol & 1); 710 symbol >>= 1; 711 } 712 return price; 713 } 714 715 static UInt32 RcTree_ReverseGetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, UInt32 *ProbPrices) 716 { 717 UInt32 price = 0; 718 UInt32 m = 1; 719 int i; 720 for (i = numBitLevels; i != 0; i--) 721 { 722 UInt32 bit = symbol & 1; 723 symbol >>= 1; 724 price += GET_PRICEa(probs[m], bit); 725 m = (m << 1) | bit; 726 } 727 return price; 728 } 729 730 731 static void LenEnc_Init(CLenEnc *p) 732 { 733 unsigned i; 734 p->choice = p->choice2 = kProbInitValue; 735 for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumLowBits); i++) 736 p->low[i] = kProbInitValue; 737 for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumMidBits); i++) 738 p->mid[i] = kProbInitValue; 739 for (i = 0; i < kLenNumHighSymbols; i++) 740 p->high[i] = kProbInitValue; 741 } 742 743 static void LenEnc_Encode(CLenEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState) 744 { 745 if (symbol < kLenNumLowSymbols) 746 { 747 RangeEnc_EncodeBit(rc, &p->choice, 0); 748 RcTree_Encode(rc, p->low + (posState << kLenNumLowBits), kLenNumLowBits, symbol); 749 } 750 else 751 { 752 RangeEnc_EncodeBit(rc, &p->choice, 1); 753 if (symbol < kLenNumLowSymbols + kLenNumMidSymbols) 754 { 755 RangeEnc_EncodeBit(rc, &p->choice2, 0); 756 RcTree_Encode(rc, p->mid + (posState << kLenNumMidBits), kLenNumMidBits, symbol - kLenNumLowSymbols); 757 } 758 else 759 { 760 RangeEnc_EncodeBit(rc, &p->choice2, 1); 761 RcTree_Encode(rc, p->high, kLenNumHighBits, symbol - kLenNumLowSymbols - kLenNumMidSymbols); 762 } 763 } 764 } 765 766 static void LenEnc_SetPrices(CLenEnc *p, UInt32 posState, UInt32 numSymbols, UInt32 *prices, UInt32 *ProbPrices) 767 { 768 UInt32 a0 = GET_PRICE_0a(p->choice); 769 UInt32 a1 = GET_PRICE_1a(p->choice); 770 UInt32 b0 = a1 + GET_PRICE_0a(p->choice2); 771 UInt32 b1 = a1 + GET_PRICE_1a(p->choice2); 772 UInt32 i = 0; 773 for (i = 0; i < kLenNumLowSymbols; i++) 774 { 775 if (i >= numSymbols) 776 return; 777 prices[i] = a0 + RcTree_GetPrice(p->low + (posState << kLenNumLowBits), kLenNumLowBits, i, ProbPrices); 778 } 779 for (; i < kLenNumLowSymbols + kLenNumMidSymbols; i++) 780 { 781 if (i >= numSymbols) 782 return; 783 prices[i] = b0 + RcTree_GetPrice(p->mid + (posState << kLenNumMidBits), kLenNumMidBits, i - kLenNumLowSymbols, ProbPrices); 784 } 785 for (; i < numSymbols; i++) 786 prices[i] = b1 + RcTree_GetPrice(p->high, kLenNumHighBits, i - kLenNumLowSymbols - kLenNumMidSymbols, ProbPrices); 787 } 788 789 static void MY_FAST_CALL LenPriceEnc_UpdateTable(CLenPriceEnc *p, UInt32 posState, UInt32 *ProbPrices) 790 { 791 LenEnc_SetPrices(&p->p, posState, p->tableSize, p->prices[posState], ProbPrices); 792 p->counters[posState] = p->tableSize; 793 } 794 795 static void LenPriceEnc_UpdateTables(CLenPriceEnc *p, UInt32 numPosStates, UInt32 *ProbPrices) 796 { 797 UInt32 posState; 798 for (posState = 0; posState < numPosStates; posState++) 799 LenPriceEnc_UpdateTable(p, posState, ProbPrices); 800 } 801 802 static void LenEnc_Encode2(CLenPriceEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState, Bool updatePrice, UInt32 *ProbPrices) 803 { 804 LenEnc_Encode(&p->p, rc, symbol, posState); 805 if (updatePrice) 806 if (--p->counters[posState] == 0) 807 LenPriceEnc_UpdateTable(p, posState, ProbPrices); 808 } 809 810 811 812 813 static void MovePos(CLzmaEnc *p, UInt32 num) 814 { 815 #ifdef SHOW_STAT 816 g_STAT_OFFSET += num; 817 printf("\n MovePos %d", num); 818 #endif 819 820 if (num != 0) 821 { 822 p->additionalOffset += num; 823 p->matchFinder.Skip(p->matchFinderObj, num); 824 } 825 } 826 827 static UInt32 ReadMatchDistances(CLzmaEnc *p, UInt32 *numDistancePairsRes) 828 { 829 UInt32 lenRes = 0, numPairs; 830 p->numAvail = p->matchFinder.GetNumAvailableBytes(p->matchFinderObj); 831 numPairs = p->matchFinder.GetMatches(p->matchFinderObj, p->matches); 832 833 #ifdef SHOW_STAT 834 printf("\n i = %d numPairs = %d ", g_STAT_OFFSET, numPairs / 2); 835 g_STAT_OFFSET++; 836 { 837 UInt32 i; 838 for (i = 0; i < numPairs; i += 2) 839 printf("%2d %6d | ", p->matches[i], p->matches[i + 1]); 840 } 841 #endif 842 843 if (numPairs > 0) 844 { 845 lenRes = p->matches[numPairs - 2]; 846 if (lenRes == p->numFastBytes) 847 { 848 const Byte *pby = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; 849 UInt32 distance = p->matches[numPairs - 1] + 1; 850 UInt32 numAvail = p->numAvail; 851 if (numAvail > LZMA_MATCH_LEN_MAX) 852 numAvail = LZMA_MATCH_LEN_MAX; 853 { 854 const Byte *pby2 = pby - distance; 855 for (; lenRes < numAvail && pby[lenRes] == pby2[lenRes]; lenRes++); 856 } 857 } 858 } 859 p->additionalOffset++; 860 *numDistancePairsRes = numPairs; 861 return lenRes; 862 } 863 864 865 #define MakeAsChar(p) (p)->backPrev = (UInt32)(-1); (p)->prev1IsChar = False; 866 #define MakeAsShortRep(p) (p)->backPrev = 0; (p)->prev1IsChar = False; 867 #define IsShortRep(p) ((p)->backPrev == 0) 868 869 static UInt32 GetRepLen1Price(CLzmaEnc *p, UInt32 state, UInt32 posState) 870 { 871 return 872 GET_PRICE_0(p->isRepG0[state]) + 873 GET_PRICE_0(p->isRep0Long[state][posState]); 874 } 875 876 static UInt32 GetPureRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 state, UInt32 posState) 877 { 878 UInt32 price; 879 if (repIndex == 0) 880 { 881 price = GET_PRICE_0(p->isRepG0[state]); 882 price += GET_PRICE_1(p->isRep0Long[state][posState]); 883 } 884 else 885 { 886 price = GET_PRICE_1(p->isRepG0[state]); 887 if (repIndex == 1) 888 price += GET_PRICE_0(p->isRepG1[state]); 889 else 890 { 891 price += GET_PRICE_1(p->isRepG1[state]); 892 price += GET_PRICE(p->isRepG2[state], repIndex - 2); 893 } 894 } 895 return price; 896 } 897 898 static UInt32 GetRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 len, UInt32 state, UInt32 posState) 899 { 900 return p->repLenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN] + 901 GetPureRepPrice(p, repIndex, state, posState); 902 } 903 904 static UInt32 Backward(CLzmaEnc *p, UInt32 *backRes, UInt32 cur) 905 { 906 UInt32 posMem = p->opt[cur].posPrev; 907 UInt32 backMem = p->opt[cur].backPrev; 908 p->optimumEndIndex = cur; 909 do 910 { 911 if (p->opt[cur].prev1IsChar) 912 { 913 MakeAsChar(&p->opt[posMem]) 914 p->opt[posMem].posPrev = posMem - 1; 915 if (p->opt[cur].prev2) 916 { 917 p->opt[posMem - 1].prev1IsChar = False; 918 p->opt[posMem - 1].posPrev = p->opt[cur].posPrev2; 919 p->opt[posMem - 1].backPrev = p->opt[cur].backPrev2; 920 } 921 } 922 { 923 UInt32 posPrev = posMem; 924 UInt32 backCur = backMem; 925 926 backMem = p->opt[posPrev].backPrev; 927 posMem = p->opt[posPrev].posPrev; 928 929 p->opt[posPrev].backPrev = backCur; 930 p->opt[posPrev].posPrev = cur; 931 cur = posPrev; 932 } 933 } 934 while (cur != 0); 935 *backRes = p->opt[0].backPrev; 936 p->optimumCurrentIndex = p->opt[0].posPrev; 937 return p->optimumCurrentIndex; 938 } 939 940 #define LIT_PROBS(pos, prevByte) (p->litProbs + ((((pos) & p->lpMask) << p->lc) + ((prevByte) >> (8 - p->lc))) * 0x300) 941 942 static UInt32 GetOptimum(CLzmaEnc *p, UInt32 position, UInt32 *backRes) 943 { 944 UInt32 numAvail, mainLen, numPairs, repMaxIndex, i, posState, lenEnd, len, cur; 945 UInt32 matchPrice, repMatchPrice, normalMatchPrice; 946 UInt32 reps[LZMA_NUM_REPS], repLens[LZMA_NUM_REPS]; 947 UInt32 *matches; 948 const Byte *data; 949 Byte curByte, matchByte; 950 if (p->optimumEndIndex != p->optimumCurrentIndex) 951 { 952 const COptimal *opt = &p->opt[p->optimumCurrentIndex]; 953 UInt32 lenRes = opt->posPrev - p->optimumCurrentIndex; 954 *backRes = opt->backPrev; 955 p->optimumCurrentIndex = opt->posPrev; 956 return lenRes; 957 } 958 p->optimumCurrentIndex = p->optimumEndIndex = 0; 959 960 if (p->additionalOffset == 0) 961 mainLen = ReadMatchDistances(p, &numPairs); 962 else 963 { 964 mainLen = p->longestMatchLength; 965 numPairs = p->numPairs; 966 } 967 968 numAvail = p->numAvail; 969 if (numAvail < 2) 970 { 971 *backRes = (UInt32)(-1); 972 return 1; 973 } 974 if (numAvail > LZMA_MATCH_LEN_MAX) 975 numAvail = LZMA_MATCH_LEN_MAX; 976 977 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; 978 repMaxIndex = 0; 979 for (i = 0; i < LZMA_NUM_REPS; i++) 980 { 981 UInt32 lenTest; 982 const Byte *data2; 983 reps[i] = p->reps[i]; 984 data2 = data - (reps[i] + 1); 985 if (data[0] != data2[0] || data[1] != data2[1]) 986 { 987 repLens[i] = 0; 988 continue; 989 } 990 for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; lenTest++); 991 repLens[i] = lenTest; 992 if (lenTest > repLens[repMaxIndex]) 993 repMaxIndex = i; 994 } 995 if (repLens[repMaxIndex] >= p->numFastBytes) 996 { 997 UInt32 lenRes; 998 *backRes = repMaxIndex; 999 lenRes = repLens[repMaxIndex]; 1000 MovePos(p, lenRes - 1); 1001 return lenRes; 1002 } 1003 1004 matches = p->matches; 1005 if (mainLen >= p->numFastBytes) 1006 { 1007 *backRes = matches[numPairs - 1] + LZMA_NUM_REPS; 1008 MovePos(p, mainLen - 1); 1009 return mainLen; 1010 } 1011 curByte = *data; 1012 matchByte = *(data - (reps[0] + 1)); 1013 1014 if (mainLen < 2 && curByte != matchByte && repLens[repMaxIndex] < 2) 1015 { 1016 *backRes = (UInt32)-1; 1017 return 1; 1018 } 1019 1020 p->opt[0].state = (CState)p->state; 1021 1022 posState = (position & p->pbMask); 1023 1024 { 1025 const CLzmaProb *probs = LIT_PROBS(position, *(data - 1)); 1026 p->opt[1].price = GET_PRICE_0(p->isMatch[p->state][posState]) + 1027 (!IsCharState(p->state) ? 1028 LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) : 1029 LitEnc_GetPrice(probs, curByte, p->ProbPrices)); 1030 } 1031 1032 MakeAsChar(&p->opt[1]); 1033 1034 matchPrice = GET_PRICE_1(p->isMatch[p->state][posState]); 1035 repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[p->state]); 1036 1037 if (matchByte == curByte) 1038 { 1039 UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, p->state, posState); 1040 if (shortRepPrice < p->opt[1].price) 1041 { 1042 p->opt[1].price = shortRepPrice; 1043 MakeAsShortRep(&p->opt[1]); 1044 } 1045 } 1046 lenEnd = ((mainLen >= repLens[repMaxIndex]) ? mainLen : repLens[repMaxIndex]); 1047 1048 if (lenEnd < 2) 1049 { 1050 *backRes = p->opt[1].backPrev; 1051 return 1; 1052 } 1053 1054 p->opt[1].posPrev = 0; 1055 for (i = 0; i < LZMA_NUM_REPS; i++) 1056 p->opt[0].backs[i] = reps[i]; 1057 1058 len = lenEnd; 1059 do 1060 p->opt[len--].price = kInfinityPrice; 1061 while (len >= 2); 1062 1063 for (i = 0; i < LZMA_NUM_REPS; i++) 1064 { 1065 UInt32 repLen = repLens[i]; 1066 UInt32 price; 1067 if (repLen < 2) 1068 continue; 1069 price = repMatchPrice + GetPureRepPrice(p, i, p->state, posState); 1070 do 1071 { 1072 UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][repLen - 2]; 1073 COptimal *opt = &p->opt[repLen]; 1074 if (curAndLenPrice < opt->price) 1075 { 1076 opt->price = curAndLenPrice; 1077 opt->posPrev = 0; 1078 opt->backPrev = i; 1079 opt->prev1IsChar = False; 1080 } 1081 } 1082 while (--repLen >= 2); 1083 } 1084 1085 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[p->state]); 1086 1087 len = ((repLens[0] >= 2) ? repLens[0] + 1 : 2); 1088 if (len <= mainLen) 1089 { 1090 UInt32 offs = 0; 1091 while (len > matches[offs]) 1092 offs += 2; 1093 for (; ; len++) 1094 { 1095 COptimal *opt; 1096 UInt32 distance = matches[offs + 1]; 1097 1098 UInt32 curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN]; 1099 UInt32 lenToPosState = GetLenToPosState(len); 1100 if (distance < kNumFullDistances) 1101 curAndLenPrice += p->distancesPrices[lenToPosState][distance]; 1102 else 1103 { 1104 UInt32 slot; 1105 GetPosSlot2(distance, slot); 1106 curAndLenPrice += p->alignPrices[distance & kAlignMask] + p->posSlotPrices[lenToPosState][slot]; 1107 } 1108 opt = &p->opt[len]; 1109 if (curAndLenPrice < opt->price) 1110 { 1111 opt->price = curAndLenPrice; 1112 opt->posPrev = 0; 1113 opt->backPrev = distance + LZMA_NUM_REPS; 1114 opt->prev1IsChar = False; 1115 } 1116 if (len == matches[offs]) 1117 { 1118 offs += 2; 1119 if (offs == numPairs) 1120 break; 1121 } 1122 } 1123 } 1124 1125 cur = 0; 1126 1127 #ifdef SHOW_STAT2 1128 if (position >= 0) 1129 { 1130 unsigned i; 1131 printf("\n pos = %4X", position); 1132 for (i = cur; i <= lenEnd; i++) 1133 printf("\nprice[%4X] = %d", position - cur + i, p->opt[i].price); 1134 } 1135 #endif 1136 1137 for (;;) 1138 { 1139 UInt32 numAvailFull, newLen, numPairs, posPrev, state, posState, startLen; 1140 UInt32 curPrice, curAnd1Price, matchPrice, repMatchPrice; 1141 Bool nextIsChar; 1142 Byte curByte, matchByte; 1143 const Byte *data; 1144 COptimal *curOpt; 1145 COptimal *nextOpt; 1146 1147 cur++; 1148 if (cur == lenEnd) 1149 return Backward(p, backRes, cur); 1150 1151 newLen = ReadMatchDistances(p, &numPairs); 1152 if (newLen >= p->numFastBytes) 1153 { 1154 p->numPairs = numPairs; 1155 p->longestMatchLength = newLen; 1156 return Backward(p, backRes, cur); 1157 } 1158 position++; 1159 curOpt = &p->opt[cur]; 1160 posPrev = curOpt->posPrev; 1161 if (curOpt->prev1IsChar) 1162 { 1163 posPrev--; 1164 if (curOpt->prev2) 1165 { 1166 state = p->opt[curOpt->posPrev2].state; 1167 if (curOpt->backPrev2 < LZMA_NUM_REPS) 1168 state = kRepNextStates[state]; 1169 else 1170 state = kMatchNextStates[state]; 1171 } 1172 else 1173 state = p->opt[posPrev].state; 1174 state = kLiteralNextStates[state]; 1175 } 1176 else 1177 state = p->opt[posPrev].state; 1178 if (posPrev == cur - 1) 1179 { 1180 if (IsShortRep(curOpt)) 1181 state = kShortRepNextStates[state]; 1182 else 1183 state = kLiteralNextStates[state]; 1184 } 1185 else 1186 { 1187 UInt32 pos; 1188 const COptimal *prevOpt; 1189 if (curOpt->prev1IsChar && curOpt->prev2) 1190 { 1191 posPrev = curOpt->posPrev2; 1192 pos = curOpt->backPrev2; 1193 state = kRepNextStates[state]; 1194 } 1195 else 1196 { 1197 pos = curOpt->backPrev; 1198 if (pos < LZMA_NUM_REPS) 1199 state = kRepNextStates[state]; 1200 else 1201 state = kMatchNextStates[state]; 1202 } 1203 prevOpt = &p->opt[posPrev]; 1204 if (pos < LZMA_NUM_REPS) 1205 { 1206 UInt32 i; 1207 reps[0] = prevOpt->backs[pos]; 1208 for (i = 1; i <= pos; i++) 1209 reps[i] = prevOpt->backs[i - 1]; 1210 for (; i < LZMA_NUM_REPS; i++) 1211 reps[i] = prevOpt->backs[i]; 1212 } 1213 else 1214 { 1215 UInt32 i; 1216 reps[0] = (pos - LZMA_NUM_REPS); 1217 for (i = 1; i < LZMA_NUM_REPS; i++) 1218 reps[i] = prevOpt->backs[i - 1]; 1219 } 1220 } 1221 curOpt->state = (CState)state; 1222 1223 curOpt->backs[0] = reps[0]; 1224 curOpt->backs[1] = reps[1]; 1225 curOpt->backs[2] = reps[2]; 1226 curOpt->backs[3] = reps[3]; 1227 1228 curPrice = curOpt->price; 1229 nextIsChar = False; 1230 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; 1231 curByte = *data; 1232 matchByte = *(data - (reps[0] + 1)); 1233 1234 posState = (position & p->pbMask); 1235 1236 curAnd1Price = curPrice + GET_PRICE_0(p->isMatch[state][posState]); 1237 { 1238 const CLzmaProb *probs = LIT_PROBS(position, *(data - 1)); 1239 curAnd1Price += 1240 (!IsCharState(state) ? 1241 LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) : 1242 LitEnc_GetPrice(probs, curByte, p->ProbPrices)); 1243 } 1244 1245 nextOpt = &p->opt[cur + 1]; 1246 1247 if (curAnd1Price < nextOpt->price) 1248 { 1249 nextOpt->price = curAnd1Price; 1250 nextOpt->posPrev = cur; 1251 MakeAsChar(nextOpt); 1252 nextIsChar = True; 1253 } 1254 1255 matchPrice = curPrice + GET_PRICE_1(p->isMatch[state][posState]); 1256 repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[state]); 1257 1258 if (matchByte == curByte && !(nextOpt->posPrev < cur && nextOpt->backPrev == 0)) 1259 { 1260 UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, state, posState); 1261 if (shortRepPrice <= nextOpt->price) 1262 { 1263 nextOpt->price = shortRepPrice; 1264 nextOpt->posPrev = cur; 1265 MakeAsShortRep(nextOpt); 1266 nextIsChar = True; 1267 } 1268 } 1269 numAvailFull = p->numAvail; 1270 { 1271 UInt32 temp = kNumOpts - 1 - cur; 1272 if (temp < numAvailFull) 1273 numAvailFull = temp; 1274 } 1275 1276 if (numAvailFull < 2) 1277 continue; 1278 numAvail = (numAvailFull <= p->numFastBytes ? numAvailFull : p->numFastBytes); 1279 1280 if (!nextIsChar && matchByte != curByte) /* speed optimization */ 1281 { 1282 /* try Literal + rep0 */ 1283 UInt32 temp; 1284 UInt32 lenTest2; 1285 const Byte *data2 = data - (reps[0] + 1); 1286 UInt32 limit = p->numFastBytes + 1; 1287 if (limit > numAvailFull) 1288 limit = numAvailFull; 1289 1290 for (temp = 1; temp < limit && data[temp] == data2[temp]; temp++); 1291 lenTest2 = temp - 1; 1292 if (lenTest2 >= 2) 1293 { 1294 UInt32 state2 = kLiteralNextStates[state]; 1295 UInt32 posStateNext = (position + 1) & p->pbMask; 1296 UInt32 nextRepMatchPrice = curAnd1Price + 1297 GET_PRICE_1(p->isMatch[state2][posStateNext]) + 1298 GET_PRICE_1(p->isRep[state2]); 1299 /* for (; lenTest2 >= 2; lenTest2--) */ 1300 { 1301 UInt32 curAndLenPrice; 1302 COptimal *opt; 1303 UInt32 offset = cur + 1 + lenTest2; 1304 while (lenEnd < offset) 1305 p->opt[++lenEnd].price = kInfinityPrice; 1306 curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext); 1307 opt = &p->opt[offset]; 1308 if (curAndLenPrice < opt->price) 1309 { 1310 opt->price = curAndLenPrice; 1311 opt->posPrev = cur + 1; 1312 opt->backPrev = 0; 1313 opt->prev1IsChar = True; 1314 opt->prev2 = False; 1315 } 1316 } 1317 } 1318 } 1319 1320 startLen = 2; /* speed optimization */ 1321 { 1322 UInt32 repIndex; 1323 for (repIndex = 0; repIndex < LZMA_NUM_REPS; repIndex++) 1324 { 1325 UInt32 lenTest; 1326 UInt32 lenTestTemp; 1327 UInt32 price; 1328 const Byte *data2 = data - (reps[repIndex] + 1); 1329 if (data[0] != data2[0] || data[1] != data2[1]) 1330 continue; 1331 for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; lenTest++); 1332 while (lenEnd < cur + lenTest) 1333 p->opt[++lenEnd].price = kInfinityPrice; 1334 lenTestTemp = lenTest; 1335 price = repMatchPrice + GetPureRepPrice(p, repIndex, state, posState); 1336 do 1337 { 1338 UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][lenTest - 2]; 1339 COptimal *opt = &p->opt[cur + lenTest]; 1340 if (curAndLenPrice < opt->price) 1341 { 1342 opt->price = curAndLenPrice; 1343 opt->posPrev = cur; 1344 opt->backPrev = repIndex; 1345 opt->prev1IsChar = False; 1346 } 1347 } 1348 while (--lenTest >= 2); 1349 lenTest = lenTestTemp; 1350 1351 if (repIndex == 0) 1352 startLen = lenTest + 1; 1353 1354 /* if (_maxMode) */ 1355 { 1356 UInt32 lenTest2 = lenTest + 1; 1357 UInt32 limit = lenTest2 + p->numFastBytes; 1358 UInt32 nextRepMatchPrice; 1359 if (limit > numAvailFull) 1360 limit = numAvailFull; 1361 for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++); 1362 lenTest2 -= lenTest + 1; 1363 if (lenTest2 >= 2) 1364 { 1365 UInt32 state2 = kRepNextStates[state]; 1366 UInt32 posStateNext = (position + lenTest) & p->pbMask; 1367 UInt32 curAndLenCharPrice = 1368 price + p->repLenEnc.prices[posState][lenTest - 2] + 1369 GET_PRICE_0(p->isMatch[state2][posStateNext]) + 1370 LitEnc_GetPriceMatched(LIT_PROBS(position + lenTest, data[lenTest - 1]), 1371 data[lenTest], data2[lenTest], p->ProbPrices); 1372 state2 = kLiteralNextStates[state2]; 1373 posStateNext = (position + lenTest + 1) & p->pbMask; 1374 nextRepMatchPrice = curAndLenCharPrice + 1375 GET_PRICE_1(p->isMatch[state2][posStateNext]) + 1376 GET_PRICE_1(p->isRep[state2]); 1377 1378 /* for (; lenTest2 >= 2; lenTest2--) */ 1379 { 1380 UInt32 curAndLenPrice; 1381 COptimal *opt; 1382 UInt32 offset = cur + lenTest + 1 + lenTest2; 1383 while (lenEnd < offset) 1384 p->opt[++lenEnd].price = kInfinityPrice; 1385 curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext); 1386 opt = &p->opt[offset]; 1387 if (curAndLenPrice < opt->price) 1388 { 1389 opt->price = curAndLenPrice; 1390 opt->posPrev = cur + lenTest + 1; 1391 opt->backPrev = 0; 1392 opt->prev1IsChar = True; 1393 opt->prev2 = True; 1394 opt->posPrev2 = cur; 1395 opt->backPrev2 = repIndex; 1396 } 1397 } 1398 } 1399 } 1400 } 1401 } 1402 /* for (UInt32 lenTest = 2; lenTest <= newLen; lenTest++) */ 1403 if (newLen > numAvail) 1404 { 1405 newLen = numAvail; 1406 for (numPairs = 0; newLen > matches[numPairs]; numPairs += 2); 1407 matches[numPairs] = newLen; 1408 numPairs += 2; 1409 } 1410 if (newLen >= startLen) 1411 { 1412 UInt32 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[state]); 1413 UInt32 offs, curBack, posSlot; 1414 UInt32 lenTest; 1415 while (lenEnd < cur + newLen) 1416 p->opt[++lenEnd].price = kInfinityPrice; 1417 1418 offs = 0; 1419 while (startLen > matches[offs]) 1420 offs += 2; 1421 curBack = matches[offs + 1]; 1422 GetPosSlot2(curBack, posSlot); 1423 for (lenTest = /*2*/ startLen; ; lenTest++) 1424 { 1425 UInt32 curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][lenTest - LZMA_MATCH_LEN_MIN]; 1426 UInt32 lenToPosState = GetLenToPosState(lenTest); 1427 COptimal *opt; 1428 if (curBack < kNumFullDistances) 1429 curAndLenPrice += p->distancesPrices[lenToPosState][curBack]; 1430 else 1431 curAndLenPrice += p->posSlotPrices[lenToPosState][posSlot] + p->alignPrices[curBack & kAlignMask]; 1432 1433 opt = &p->opt[cur + lenTest]; 1434 if (curAndLenPrice < opt->price) 1435 { 1436 opt->price = curAndLenPrice; 1437 opt->posPrev = cur; 1438 opt->backPrev = curBack + LZMA_NUM_REPS; 1439 opt->prev1IsChar = False; 1440 } 1441 1442 if (/*_maxMode && */lenTest == matches[offs]) 1443 { 1444 /* Try Match + Literal + Rep0 */ 1445 const Byte *data2 = data - (curBack + 1); 1446 UInt32 lenTest2 = lenTest + 1; 1447 UInt32 limit = lenTest2 + p->numFastBytes; 1448 UInt32 nextRepMatchPrice; 1449 if (limit > numAvailFull) 1450 limit = numAvailFull; 1451 for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++); 1452 lenTest2 -= lenTest + 1; 1453 if (lenTest2 >= 2) 1454 { 1455 UInt32 state2 = kMatchNextStates[state]; 1456 UInt32 posStateNext = (position + lenTest) & p->pbMask; 1457 UInt32 curAndLenCharPrice = curAndLenPrice + 1458 GET_PRICE_0(p->isMatch[state2][posStateNext]) + 1459 LitEnc_GetPriceMatched(LIT_PROBS(position + lenTest, data[lenTest - 1]), 1460 data[lenTest], data2[lenTest], p->ProbPrices); 1461 state2 = kLiteralNextStates[state2]; 1462 posStateNext = (posStateNext + 1) & p->pbMask; 1463 nextRepMatchPrice = curAndLenCharPrice + 1464 GET_PRICE_1(p->isMatch[state2][posStateNext]) + 1465 GET_PRICE_1(p->isRep[state2]); 1466 1467 /* for (; lenTest2 >= 2; lenTest2--) */ 1468 { 1469 UInt32 offset = cur + lenTest + 1 + lenTest2; 1470 UInt32 curAndLenPrice; 1471 COptimal *opt; 1472 while (lenEnd < offset) 1473 p->opt[++lenEnd].price = kInfinityPrice; 1474 curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext); 1475 opt = &p->opt[offset]; 1476 if (curAndLenPrice < opt->price) 1477 { 1478 opt->price = curAndLenPrice; 1479 opt->posPrev = cur + lenTest + 1; 1480 opt->backPrev = 0; 1481 opt->prev1IsChar = True; 1482 opt->prev2 = True; 1483 opt->posPrev2 = cur; 1484 opt->backPrev2 = curBack + LZMA_NUM_REPS; 1485 } 1486 } 1487 } 1488 offs += 2; 1489 if (offs == numPairs) 1490 break; 1491 curBack = matches[offs + 1]; 1492 if (curBack >= kNumFullDistances) 1493 GetPosSlot2(curBack, posSlot); 1494 } 1495 } 1496 } 1497 } 1498 } 1499 1500 #define ChangePair(smallDist, bigDist) (((bigDist) >> 7) > (smallDist)) 1501 1502 static UInt32 GetOptimumFast(CLzmaEnc *p, UInt32 *backRes) 1503 { 1504 UInt32 numAvail, mainLen, mainDist, numPairs, repIndex, repLen, i; 1505 const Byte *data; 1506 const UInt32 *matches; 1507 1508 if (p->additionalOffset == 0) 1509 mainLen = ReadMatchDistances(p, &numPairs); 1510 else 1511 { 1512 mainLen = p->longestMatchLength; 1513 numPairs = p->numPairs; 1514 } 1515 1516 numAvail = p->numAvail; 1517 *backRes = (UInt32)-1; 1518 if (numAvail < 2) 1519 return 1; 1520 if (numAvail > LZMA_MATCH_LEN_MAX) 1521 numAvail = LZMA_MATCH_LEN_MAX; 1522 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; 1523 1524 repLen = repIndex = 0; 1525 for (i = 0; i < LZMA_NUM_REPS; i++) 1526 { 1527 UInt32 len; 1528 const Byte *data2 = data - (p->reps[i] + 1); 1529 if (data[0] != data2[0] || data[1] != data2[1]) 1530 continue; 1531 for (len = 2; len < numAvail && data[len] == data2[len]; len++); 1532 if (len >= p->numFastBytes) 1533 { 1534 *backRes = i; 1535 MovePos(p, len - 1); 1536 return len; 1537 } 1538 if (len > repLen) 1539 { 1540 repIndex = i; 1541 repLen = len; 1542 } 1543 } 1544 1545 matches = p->matches; 1546 if (mainLen >= p->numFastBytes) 1547 { 1548 *backRes = matches[numPairs - 1] + LZMA_NUM_REPS; 1549 MovePos(p, mainLen - 1); 1550 return mainLen; 1551 } 1552 1553 mainDist = 0; /* for GCC */ 1554 if (mainLen >= 2) 1555 { 1556 mainDist = matches[numPairs - 1]; 1557 while (numPairs > 2 && mainLen == matches[numPairs - 4] + 1) 1558 { 1559 if (!ChangePair(matches[numPairs - 3], mainDist)) 1560 break; 1561 numPairs -= 2; 1562 mainLen = matches[numPairs - 2]; 1563 mainDist = matches[numPairs - 1]; 1564 } 1565 if (mainLen == 2 && mainDist >= 0x80) 1566 mainLen = 1; 1567 } 1568 1569 if (repLen >= 2 && ( 1570 (repLen + 1 >= mainLen) || 1571 (repLen + 2 >= mainLen && mainDist >= (1 << 9)) || 1572 (repLen + 3 >= mainLen && mainDist >= (1 << 15)))) 1573 { 1574 *backRes = repIndex; 1575 MovePos(p, repLen - 1); 1576 return repLen; 1577 } 1578 1579 if (mainLen < 2 || numAvail <= 2) 1580 return 1; 1581 1582 p->longestMatchLength = ReadMatchDistances(p, &p->numPairs); 1583 if (p->longestMatchLength >= 2) 1584 { 1585 UInt32 newDistance = matches[p->numPairs - 1]; 1586 if ((p->longestMatchLength >= mainLen && newDistance < mainDist) || 1587 (p->longestMatchLength == mainLen + 1 && !ChangePair(mainDist, newDistance)) || 1588 (p->longestMatchLength > mainLen + 1) || 1589 (p->longestMatchLength + 1 >= mainLen && mainLen >= 3 && ChangePair(newDistance, mainDist))) 1590 return 1; 1591 } 1592 1593 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1; 1594 for (i = 0; i < LZMA_NUM_REPS; i++) 1595 { 1596 UInt32 len, limit; 1597 const Byte *data2 = data - (p->reps[i] + 1); 1598 if (data[0] != data2[0] || data[1] != data2[1]) 1599 continue; 1600 limit = mainLen - 1; 1601 for (len = 2; len < limit && data[len] == data2[len]; len++); 1602 if (len >= limit) 1603 return 1; 1604 } 1605 *backRes = mainDist + LZMA_NUM_REPS; 1606 MovePos(p, mainLen - 2); 1607 return mainLen; 1608 } 1609 1610 static void WriteEndMarker(CLzmaEnc *p, UInt32 posState) 1611 { 1612 UInt32 len; 1613 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1); 1614 RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0); 1615 p->state = kMatchNextStates[p->state]; 1616 len = LZMA_MATCH_LEN_MIN; 1617 LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices); 1618 RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBits, (1 << kNumPosSlotBits) - 1); 1619 RangeEnc_EncodeDirectBits(&p->rc, (((UInt32)1 << 30) - 1) >> kNumAlignBits, 30 - kNumAlignBits); 1620 RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, kAlignMask); 1621 } 1622 1623 static SRes CheckErrors(CLzmaEnc *p) 1624 { 1625 if (p->result != SZ_OK) 1626 return p->result; 1627 if (p->rc.res != SZ_OK) 1628 p->result = SZ_ERROR_WRITE; 1629 if (p->matchFinderBase.result != SZ_OK) 1630 p->result = SZ_ERROR_READ; 1631 if (p->result != SZ_OK) 1632 p->finished = True; 1633 return p->result; 1634 } 1635 1636 static SRes Flush(CLzmaEnc *p, UInt32 nowPos) 1637 { 1638 /* ReleaseMFStream(); */ 1639 p->finished = True; 1640 if (p->writeEndMark) 1641 WriteEndMarker(p, nowPos & p->pbMask); 1642 RangeEnc_FlushData(&p->rc); 1643 RangeEnc_FlushStream(&p->rc); 1644 return CheckErrors(p); 1645 } 1646 1647 static void FillAlignPrices(CLzmaEnc *p) 1648 { 1649 UInt32 i; 1650 for (i = 0; i < kAlignTableSize; i++) 1651 p->alignPrices[i] = RcTree_ReverseGetPrice(p->posAlignEncoder, kNumAlignBits, i, p->ProbPrices); 1652 p->alignPriceCount = 0; 1653 } 1654 1655 static void FillDistancesPrices(CLzmaEnc *p) 1656 { 1657 UInt32 tempPrices[kNumFullDistances]; 1658 UInt32 i, lenToPosState; 1659 for (i = kStartPosModelIndex; i < kNumFullDistances; i++) 1660 { 1661 UInt32 posSlot = GetPosSlot1(i); 1662 UInt32 footerBits = ((posSlot >> 1) - 1); 1663 UInt32 base = ((2 | (posSlot & 1)) << footerBits); 1664 tempPrices[i] = RcTree_ReverseGetPrice(p->posEncoders + base - posSlot - 1, footerBits, i - base, p->ProbPrices); 1665 } 1666 1667 for (lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++) 1668 { 1669 UInt32 posSlot; 1670 const CLzmaProb *encoder = p->posSlotEncoder[lenToPosState]; 1671 UInt32 *posSlotPrices = p->posSlotPrices[lenToPosState]; 1672 for (posSlot = 0; posSlot < p->distTableSize; posSlot++) 1673 posSlotPrices[posSlot] = RcTree_GetPrice(encoder, kNumPosSlotBits, posSlot, p->ProbPrices); 1674 for (posSlot = kEndPosModelIndex; posSlot < p->distTableSize; posSlot++) 1675 posSlotPrices[posSlot] += ((((posSlot >> 1) - 1) - kNumAlignBits) << kNumBitPriceShiftBits); 1676 1677 { 1678 UInt32 *distancesPrices = p->distancesPrices[lenToPosState]; 1679 UInt32 i; 1680 for (i = 0; i < kStartPosModelIndex; i++) 1681 distancesPrices[i] = posSlotPrices[i]; 1682 for (; i < kNumFullDistances; i++) 1683 distancesPrices[i] = posSlotPrices[GetPosSlot1(i)] + tempPrices[i]; 1684 } 1685 } 1686 p->matchPriceCount = 0; 1687 } 1688 1689 void LzmaEnc_Construct(CLzmaEnc *p) 1690 { 1691 RangeEnc_Construct(&p->rc); 1692 MatchFinder_Construct(&p->matchFinderBase); 1693 #ifndef _7ZIP_ST 1694 MatchFinderMt_Construct(&p->matchFinderMt); 1695 p->matchFinderMt.MatchFinder = &p->matchFinderBase; 1696 #endif 1697 1698 { 1699 CLzmaEncProps props; 1700 LzmaEncProps_Init(&props); 1701 LzmaEnc_SetProps(p, &props); 1702 } 1703 1704 #ifndef LZMA_LOG_BSR 1705 LzmaEnc_FastPosInit(p->g_FastPos); 1706 #endif 1707 1708 LzmaEnc_InitPriceTables(p->ProbPrices); 1709 p->litProbs = 0; 1710 p->saveState.litProbs = 0; 1711 } 1712 1713 CLzmaEncHandle LzmaEnc_Create(ISzAlloc *alloc) 1714 { 1715 void *p; 1716 p = alloc->Alloc(alloc, sizeof(CLzmaEnc)); 1717 if (p != 0) 1718 LzmaEnc_Construct((CLzmaEnc *)p); 1719 return p; 1720 } 1721 1722 void LzmaEnc_FreeLits(CLzmaEnc *p, ISzAlloc *alloc) 1723 { 1724 alloc->Free(alloc, p->litProbs); 1725 alloc->Free(alloc, p->saveState.litProbs); 1726 p->litProbs = 0; 1727 p->saveState.litProbs = 0; 1728 } 1729 1730 void LzmaEnc_Destruct(CLzmaEnc *p, ISzAlloc *alloc, ISzAlloc *allocBig) 1731 { 1732 #ifndef _7ZIP_ST 1733 MatchFinderMt_Destruct(&p->matchFinderMt, allocBig); 1734 #endif 1735 MatchFinder_Free(&p->matchFinderBase, allocBig); 1736 LzmaEnc_FreeLits(p, alloc); 1737 RangeEnc_Free(&p->rc, alloc); 1738 } 1739 1740 void LzmaEnc_Destroy(CLzmaEncHandle p, ISzAlloc *alloc, ISzAlloc *allocBig) 1741 { 1742 LzmaEnc_Destruct((CLzmaEnc *)p, alloc, allocBig); 1743 alloc->Free(alloc, p); 1744 } 1745 1746 static SRes LzmaEnc_CodeOneBlock(CLzmaEnc *p, Bool useLimits, UInt32 maxPackSize, UInt32 maxUnpackSize) 1747 { 1748 UInt32 nowPos32, startPos32; 1749 if (p->needInit) 1750 { 1751 p->matchFinder.Init(p->matchFinderObj); 1752 p->needInit = 0; 1753 } 1754 1755 if (p->finished) 1756 return p->result; 1757 RINOK(CheckErrors(p)); 1758 1759 nowPos32 = (UInt32)p->nowPos64; 1760 startPos32 = nowPos32; 1761 1762 if (p->nowPos64 == 0) 1763 { 1764 UInt32 numPairs; 1765 Byte curByte; 1766 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0) 1767 return Flush(p, nowPos32); 1768 ReadMatchDistances(p, &numPairs); 1769 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][0], 0); 1770 p->state = kLiteralNextStates[p->state]; 1771 curByte = p->matchFinder.GetIndexByte(p->matchFinderObj, 0 - p->additionalOffset); 1772 LitEnc_Encode(&p->rc, p->litProbs, curByte); 1773 p->additionalOffset--; 1774 nowPos32++; 1775 } 1776 1777 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) != 0) 1778 for (;;) 1779 { 1780 UInt32 pos, len, posState; 1781 1782 if (p->fastMode) 1783 len = GetOptimumFast(p, &pos); 1784 else 1785 len = GetOptimum(p, nowPos32, &pos); 1786 1787 #ifdef SHOW_STAT2 1788 printf("\n pos = %4X, len = %d pos = %d", nowPos32, len, pos); 1789 #endif 1790 1791 posState = nowPos32 & p->pbMask; 1792 if (len == 1 && pos == (UInt32)-1) 1793 { 1794 Byte curByte; 1795 CLzmaProb *probs; 1796 const Byte *data; 1797 1798 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 0); 1799 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset; 1800 curByte = *data; 1801 probs = LIT_PROBS(nowPos32, *(data - 1)); 1802 if (IsCharState(p->state)) 1803 LitEnc_Encode(&p->rc, probs, curByte); 1804 else 1805 LitEnc_EncodeMatched(&p->rc, probs, curByte, *(data - p->reps[0] - 1)); 1806 p->state = kLiteralNextStates[p->state]; 1807 } 1808 else 1809 { 1810 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1); 1811 if (pos < LZMA_NUM_REPS) 1812 { 1813 RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 1); 1814 if (pos == 0) 1815 { 1816 RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 0); 1817 RangeEnc_EncodeBit(&p->rc, &p->isRep0Long[p->state][posState], ((len == 1) ? 0 : 1)); 1818 } 1819 else 1820 { 1821 UInt32 distance = p->reps[pos]; 1822 RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 1); 1823 if (pos == 1) 1824 RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 0); 1825 else 1826 { 1827 RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 1); 1828 RangeEnc_EncodeBit(&p->rc, &p->isRepG2[p->state], pos - 2); 1829 if (pos == 3) 1830 p->reps[3] = p->reps[2]; 1831 p->reps[2] = p->reps[1]; 1832 } 1833 p->reps[1] = p->reps[0]; 1834 p->reps[0] = distance; 1835 } 1836 if (len == 1) 1837 p->state = kShortRepNextStates[p->state]; 1838 else 1839 { 1840 LenEnc_Encode2(&p->repLenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices); 1841 p->state = kRepNextStates[p->state]; 1842 } 1843 } 1844 else 1845 { 1846 UInt32 posSlot; 1847 RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0); 1848 p->state = kMatchNextStates[p->state]; 1849 LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices); 1850 pos -= LZMA_NUM_REPS; 1851 GetPosSlot(pos, posSlot); 1852 RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBits, posSlot); 1853 1854 if (posSlot >= kStartPosModelIndex) 1855 { 1856 UInt32 footerBits = ((posSlot >> 1) - 1); 1857 UInt32 base = ((2 | (posSlot & 1)) << footerBits); 1858 UInt32 posReduced = pos - base; 1859 1860 if (posSlot < kEndPosModelIndex) 1861 RcTree_ReverseEncode(&p->rc, p->posEncoders + base - posSlot - 1, footerBits, posReduced); 1862 else 1863 { 1864 RangeEnc_EncodeDirectBits(&p->rc, posReduced >> kNumAlignBits, footerBits - kNumAlignBits); 1865 RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, posReduced & kAlignMask); 1866 p->alignPriceCount++; 1867 } 1868 } 1869 p->reps[3] = p->reps[2]; 1870 p->reps[2] = p->reps[1]; 1871 p->reps[1] = p->reps[0]; 1872 p->reps[0] = pos; 1873 p->matchPriceCount++; 1874 } 1875 } 1876 p->additionalOffset -= len; 1877 nowPos32 += len; 1878 if (p->additionalOffset == 0) 1879 { 1880 UInt32 processed; 1881 if (!p->fastMode) 1882 { 1883 if (p->matchPriceCount >= (1 << 7)) 1884 FillDistancesPrices(p); 1885 if (p->alignPriceCount >= kAlignTableSize) 1886 FillAlignPrices(p); 1887 } 1888 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0) 1889 break; 1890 processed = nowPos32 - startPos32; 1891 if (useLimits) 1892 { 1893 if (processed + kNumOpts + 300 >= maxUnpackSize || 1894 RangeEnc_GetProcessed(&p->rc) + kNumOpts * 2 >= maxPackSize) 1895 break; 1896 } 1897 else if (processed >= (1 << 15)) 1898 { 1899 p->nowPos64 += nowPos32 - startPos32; 1900 return CheckErrors(p); 1901 } 1902 } 1903 } 1904 p->nowPos64 += nowPos32 - startPos32; 1905 return Flush(p, nowPos32); 1906 } 1907 1908 #define kBigHashDicLimit ((UInt32)1 << 24) 1909 1910 static SRes LzmaEnc_Alloc(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig) 1911 { 1912 UInt32 beforeSize = kNumOpts; 1913 if (!RangeEnc_Alloc(&p->rc, alloc)) 1914 return SZ_ERROR_MEM; 1915 #ifndef _7ZIP_ST 1916 p->mtMode = (p->multiThread && !p->fastMode && (p->matchFinderBase.btMode != 0)); 1917 #endif 1918 1919 { 1920 unsigned lclp = p->lc + p->lp; 1921 if (p->litProbs == 0 || p->saveState.litProbs == 0 || p->lclp != lclp) 1922 { 1923 LzmaEnc_FreeLits(p, alloc); 1924 p->litProbs = (CLzmaProb *)alloc->Alloc(alloc, (0x300 << lclp) * sizeof(CLzmaProb)); 1925 p->saveState.litProbs = (CLzmaProb *)alloc->Alloc(alloc, (0x300 << lclp) * sizeof(CLzmaProb)); 1926 if (p->litProbs == 0 || p->saveState.litProbs == 0) 1927 { 1928 LzmaEnc_FreeLits(p, alloc); 1929 return SZ_ERROR_MEM; 1930 } 1931 p->lclp = lclp; 1932 } 1933 } 1934 1935 p->matchFinderBase.bigHash = (p->dictSize > kBigHashDicLimit); 1936 1937 if (beforeSize + p->dictSize < keepWindowSize) 1938 beforeSize = keepWindowSize - p->dictSize; 1939 1940 #ifndef _7ZIP_ST 1941 if (p->mtMode) 1942 { 1943 RINOK(MatchFinderMt_Create(&p->matchFinderMt, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig)); 1944 p->matchFinderObj = &p->matchFinderMt; 1945 MatchFinderMt_CreateVTable(&p->matchFinderMt, &p->matchFinder); 1946 } 1947 else 1948 #endif 1949 { 1950 if (!MatchFinder_Create(&p->matchFinderBase, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig)) 1951 return SZ_ERROR_MEM; 1952 p->matchFinderObj = &p->matchFinderBase; 1953 MatchFinder_CreateVTable(&p->matchFinderBase, &p->matchFinder); 1954 } 1955 return SZ_OK; 1956 } 1957 1958 void LzmaEnc_Init(CLzmaEnc *p) 1959 { 1960 UInt32 i; 1961 p->state = 0; 1962 for (i = 0 ; i < LZMA_NUM_REPS; i++) 1963 p->reps[i] = 0; 1964 1965 RangeEnc_Init(&p->rc); 1966 1967 1968 for (i = 0; i < kNumStates; i++) 1969 { 1970 UInt32 j; 1971 for (j = 0; j < LZMA_NUM_PB_STATES_MAX; j++) 1972 { 1973 p->isMatch[i][j] = kProbInitValue; 1974 p->isRep0Long[i][j] = kProbInitValue; 1975 } 1976 p->isRep[i] = kProbInitValue; 1977 p->isRepG0[i] = kProbInitValue; 1978 p->isRepG1[i] = kProbInitValue; 1979 p->isRepG2[i] = kProbInitValue; 1980 } 1981 1982 { 1983 UInt32 num = 0x300 << (p->lp + p->lc); 1984 for (i = 0; i < num; i++) 1985 p->litProbs[i] = kProbInitValue; 1986 } 1987 1988 { 1989 for (i = 0; i < kNumLenToPosStates; i++) 1990 { 1991 CLzmaProb *probs = p->posSlotEncoder[i]; 1992 UInt32 j; 1993 for (j = 0; j < (1 << kNumPosSlotBits); j++) 1994 probs[j] = kProbInitValue; 1995 } 1996 } 1997 { 1998 for (i = 0; i < kNumFullDistances - kEndPosModelIndex; i++) 1999 p->posEncoders[i] = kProbInitValue; 2000 } 2001 2002 LenEnc_Init(&p->lenEnc.p); 2003 LenEnc_Init(&p->repLenEnc.p); 2004 2005 for (i = 0; i < (1 << kNumAlignBits); i++) 2006 p->posAlignEncoder[i] = kProbInitValue; 2007 2008 p->optimumEndIndex = 0; 2009 p->optimumCurrentIndex = 0; 2010 p->additionalOffset = 0; 2011 2012 p->pbMask = (1 << p->pb) - 1; 2013 p->lpMask = (1 << p->lp) - 1; 2014 } 2015 2016 void LzmaEnc_InitPrices(CLzmaEnc *p) 2017 { 2018 if (!p->fastMode) 2019 { 2020 FillDistancesPrices(p); 2021 FillAlignPrices(p); 2022 } 2023 2024 p->lenEnc.tableSize = 2025 p->repLenEnc.tableSize = 2026 p->numFastBytes + 1 - LZMA_MATCH_LEN_MIN; 2027 LenPriceEnc_UpdateTables(&p->lenEnc, 1 << p->pb, p->ProbPrices); 2028 LenPriceEnc_UpdateTables(&p->repLenEnc, 1 << p->pb, p->ProbPrices); 2029 } 2030 2031 static SRes LzmaEnc_AllocAndInit(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig) 2032 { 2033 UInt32 i; 2034 for (i = 0; i < (UInt32)kDicLogSizeMaxCompress; i++) 2035 if (p->dictSize <= ((UInt32)1 << i)) 2036 break; 2037 p->distTableSize = i * 2; 2038 2039 p->finished = False; 2040 p->result = SZ_OK; 2041 RINOK(LzmaEnc_Alloc(p, keepWindowSize, alloc, allocBig)); 2042 LzmaEnc_Init(p); 2043 LzmaEnc_InitPrices(p); 2044 p->nowPos64 = 0; 2045 return SZ_OK; 2046 } 2047 2048 static SRes LzmaEnc_Prepare(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream, 2049 ISzAlloc *alloc, ISzAlloc *allocBig) 2050 { 2051 CLzmaEnc *p = (CLzmaEnc *)pp; 2052 p->matchFinderBase.stream = inStream; 2053 p->needInit = 1; 2054 p->rc.outStream = outStream; 2055 return LzmaEnc_AllocAndInit(p, 0, alloc, allocBig); 2056 } 2057 2058 SRes LzmaEnc_PrepareForLzma2(CLzmaEncHandle pp, 2059 ISeqInStream *inStream, UInt32 keepWindowSize, 2060 ISzAlloc *alloc, ISzAlloc *allocBig) 2061 { 2062 CLzmaEnc *p = (CLzmaEnc *)pp; 2063 p->matchFinderBase.stream = inStream; 2064 p->needInit = 1; 2065 return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig); 2066 } 2067 2068 static void LzmaEnc_SetInputBuf(CLzmaEnc *p, const Byte *src, SizeT srcLen) 2069 { 2070 p->matchFinderBase.directInput = 1; 2071 p->matchFinderBase.bufferBase = (Byte *)src; 2072 p->matchFinderBase.directInputRem = srcLen; 2073 } 2074 2075 SRes LzmaEnc_MemPrepare(CLzmaEncHandle pp, const Byte *src, SizeT srcLen, 2076 UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig) 2077 { 2078 CLzmaEnc *p = (CLzmaEnc *)pp; 2079 LzmaEnc_SetInputBuf(p, src, srcLen); 2080 p->needInit = 1; 2081 2082 return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig); 2083 } 2084 2085 void LzmaEnc_Finish(CLzmaEncHandle pp) 2086 { 2087 #ifndef _7ZIP_ST 2088 CLzmaEnc *p = (CLzmaEnc *)pp; 2089 if (p->mtMode) 2090 MatchFinderMt_ReleaseStream(&p->matchFinderMt); 2091 #else 2092 pp = pp; 2093 #endif 2094 } 2095 2096 typedef struct 2097 { 2098 ISeqOutStream funcTable; 2099 Byte *data; 2100 SizeT rem; 2101 Bool overflow; 2102 } CSeqOutStreamBuf; 2103 2104 static size_t MyWrite(void *pp, const void *data, size_t size) 2105 { 2106 CSeqOutStreamBuf *p = (CSeqOutStreamBuf *)pp; 2107 if (p->rem < size) 2108 { 2109 size = p->rem; 2110 p->overflow = True; 2111 } 2112 memcpy(p->data, data, size); 2113 p->rem -= size; 2114 p->data += size; 2115 return size; 2116 } 2117 2118 2119 UInt32 LzmaEnc_GetNumAvailableBytes(CLzmaEncHandle pp) 2120 { 2121 const CLzmaEnc *p = (CLzmaEnc *)pp; 2122 return p->matchFinder.GetNumAvailableBytes(p->matchFinderObj); 2123 } 2124 2125 const Byte *LzmaEnc_GetCurBuf(CLzmaEncHandle pp) 2126 { 2127 const CLzmaEnc *p = (CLzmaEnc *)pp; 2128 return p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset; 2129 } 2130 2131 SRes LzmaEnc_CodeOneMemBlock(CLzmaEncHandle pp, Bool reInit, 2132 Byte *dest, size_t *destLen, UInt32 desiredPackSize, UInt32 *unpackSize) 2133 { 2134 CLzmaEnc *p = (CLzmaEnc *)pp; 2135 UInt64 nowPos64; 2136 SRes res; 2137 CSeqOutStreamBuf outStream; 2138 2139 outStream.funcTable.Write = MyWrite; 2140 outStream.data = dest; 2141 outStream.rem = *destLen; 2142 outStream.overflow = False; 2143 2144 p->writeEndMark = False; 2145 p->finished = False; 2146 p->result = SZ_OK; 2147 2148 if (reInit) 2149 LzmaEnc_Init(p); 2150 LzmaEnc_InitPrices(p); 2151 nowPos64 = p->nowPos64; 2152 RangeEnc_Init(&p->rc); 2153 p->rc.outStream = &outStream.funcTable; 2154 2155 res = LzmaEnc_CodeOneBlock(p, True, desiredPackSize, *unpackSize); 2156 2157 *unpackSize = (UInt32)(p->nowPos64 - nowPos64); 2158 *destLen -= outStream.rem; 2159 if (outStream.overflow) 2160 return SZ_ERROR_OUTPUT_EOF; 2161 2162 return res; 2163 } 2164 2165 static SRes LzmaEnc_Encode2(CLzmaEnc *p, ICompressProgress *progress) 2166 { 2167 SRes res = SZ_OK; 2168 2169 #ifndef _7ZIP_ST 2170 Byte allocaDummy[0x300]; 2171 allocaDummy[0] = 0; 2172 allocaDummy[1] = allocaDummy[0]; 2173 #endif 2174 2175 for (;;) 2176 { 2177 res = LzmaEnc_CodeOneBlock(p, False, 0, 0); 2178 if (res != SZ_OK || p->finished != 0) 2179 break; 2180 if (progress != 0) 2181 { 2182 res = progress->Progress(progress, p->nowPos64, RangeEnc_GetProcessed(&p->rc)); 2183 if (res != SZ_OK) 2184 { 2185 res = SZ_ERROR_PROGRESS; 2186 break; 2187 } 2188 } 2189 } 2190 LzmaEnc_Finish(p); 2191 return res; 2192 } 2193 2194 SRes LzmaEnc_Encode(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream, ICompressProgress *progress, 2195 ISzAlloc *alloc, ISzAlloc *allocBig) 2196 { 2197 RINOK(LzmaEnc_Prepare(pp, outStream, inStream, alloc, allocBig)); 2198 return LzmaEnc_Encode2((CLzmaEnc *)pp, progress); 2199 } 2200 2201 SRes LzmaEnc_WriteProperties(CLzmaEncHandle pp, Byte *props, SizeT *size) 2202 { 2203 CLzmaEnc *p = (CLzmaEnc *)pp; 2204 int i; 2205 UInt32 dictSize = p->dictSize; 2206 if (*size < LZMA_PROPS_SIZE) 2207 return SZ_ERROR_PARAM; 2208 *size = LZMA_PROPS_SIZE; 2209 props[0] = (Byte)((p->pb * 5 + p->lp) * 9 + p->lc); 2210 2211 for (i = 11; i <= 30; i++) 2212 { 2213 if (dictSize <= ((UInt32)2 << i)) 2214 { 2215 dictSize = (2 << i); 2216 break; 2217 } 2218 if (dictSize <= ((UInt32)3 << i)) 2219 { 2220 dictSize = (3 << i); 2221 break; 2222 } 2223 } 2224 2225 for (i = 0; i < 4; i++) 2226 props[1 + i] = (Byte)(dictSize >> (8 * i)); 2227 return SZ_OK; 2228 } 2229 2230 SRes LzmaEnc_MemEncode(CLzmaEncHandle pp, Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen, 2231 int writeEndMark, ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig) 2232 { 2233 SRes res; 2234 CLzmaEnc *p = (CLzmaEnc *)pp; 2235 2236 CSeqOutStreamBuf outStream; 2237 2238 LzmaEnc_SetInputBuf(p, src, srcLen); 2239 2240 outStream.funcTable.Write = MyWrite; 2241 outStream.data = dest; 2242 outStream.rem = *destLen; 2243 outStream.overflow = False; 2244 2245 p->writeEndMark = writeEndMark; 2246 2247 p->rc.outStream = &outStream.funcTable; 2248 res = LzmaEnc_MemPrepare(pp, src, srcLen, 0, alloc, allocBig); 2249 if (res == SZ_OK) 2250 res = LzmaEnc_Encode2(p, progress); 2251 2252 *destLen -= outStream.rem; 2253 if (outStream.overflow) 2254 return SZ_ERROR_OUTPUT_EOF; 2255 return res; 2256 } 2257 2258 SRes LzmaEncode(Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen, 2259 const CLzmaEncProps *props, Byte *propsEncoded, SizeT *propsSize, int writeEndMark, 2260 ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig) 2261 { 2262 CLzmaEnc *p = (CLzmaEnc *)LzmaEnc_Create(alloc); 2263 SRes res; 2264 if (p == 0) 2265 return SZ_ERROR_MEM; 2266 2267 res = LzmaEnc_SetProps(p, props); 2268 if (res == SZ_OK) 2269 { 2270 res = LzmaEnc_WriteProperties(p, propsEncoded, propsSize); 2271 if (res == SZ_OK) 2272 res = LzmaEnc_MemEncode(p, dest, destLen, src, srcLen, 2273 writeEndMark, progress, alloc, allocBig); 2274 } 2275 2276 LzmaEnc_Destroy(p, alloc, allocBig); 2277 return res; 2278 } 2279
