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