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