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