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