1 /* LzmaEnc.c -- LZMA Encoder
\r
2 2016-05-16 : Igor Pavlov : Public domain */
\r
8 /* #define SHOW_STAT */
\r
9 /* #define SHOW_STAT2 */
\r
11 #if defined(SHOW_STAT) || defined(SHOW_STAT2)
\r
15 #include "LzmaEnc.h"
\r
19 #include "LzFindMt.h"
\r
23 static unsigned g_STAT_OFFSET = 0;
\r
26 #define kMaxHistorySize ((UInt32)3 << 29)
\r
27 /* #define kMaxHistorySize ((UInt32)7 << 29) */
\r
29 #define kBlockSizeMax ((1 << LZMA_NUM_BLOCK_SIZE_BITS) - 1)
\r
31 #define kBlockSize (9 << 10)
\r
32 #define kUnpackBlockSize (1 << 18)
\r
33 #define kMatchArraySize (1 << 21)
\r
34 #define kMatchRecordMaxSize ((LZMA_MATCH_LEN_MAX * 2 + 3) * LZMA_MATCH_LEN_MAX)
\r
36 #define kNumMaxDirectBits (31)
\r
38 #define kNumTopBits 24
\r
39 #define kTopValue ((UInt32)1 << kNumTopBits)
\r
41 #define kNumBitModelTotalBits 11
\r
42 #define kBitModelTotal (1 << kNumBitModelTotalBits)
\r
43 #define kNumMoveBits 5
\r
44 #define kProbInitValue (kBitModelTotal >> 1)
\r
46 #define kNumMoveReducingBits 4
\r
47 #define kNumBitPriceShiftBits 4
\r
48 #define kBitPrice (1 << kNumBitPriceShiftBits)
\r
50 void LzmaEncProps_Init(CLzmaEncProps *p)
\r
53 p->dictSize = p->mc = 0;
\r
54 p->reduceSize = (UInt64)(Int64)-1;
\r
55 p->lc = p->lp = p->pb = p->algo = p->fb = p->btMode = p->numHashBytes = p->numThreads = -1;
\r
56 p->writeEndMark = 0;
\r
59 void LzmaEncProps_Normalize(CLzmaEncProps *p)
\r
61 int level = p->level;
\r
62 if (level < 0) level = 5;
\r
65 if (p->dictSize == 0) p->dictSize = (level <= 5 ? (1 << (level * 2 + 14)) : (level == 6 ? (1 << 25) : (1 << 26)));
\r
66 if (p->dictSize > p->reduceSize)
\r
69 for (i = 11; i <= 30; i++)
\r
71 if ((UInt32)p->reduceSize <= ((UInt32)2 << i)) { p->dictSize = ((UInt32)2 << i); break; }
\r
72 if ((UInt32)p->reduceSize <= ((UInt32)3 << i)) { p->dictSize = ((UInt32)3 << i); break; }
\r
76 if (p->lc < 0) p->lc = 3;
\r
77 if (p->lp < 0) p->lp = 0;
\r
78 if (p->pb < 0) p->pb = 2;
\r
80 if (p->algo < 0) p->algo = (level < 5 ? 0 : 1);
\r
81 if (p->fb < 0) p->fb = (level < 7 ? 32 : 64);
\r
82 if (p->btMode < 0) p->btMode = (p->algo == 0 ? 0 : 1);
\r
83 if (p->numHashBytes < 0) p->numHashBytes = 4;
\r
84 if (p->mc == 0) p->mc = (16 + (p->fb >> 1)) >> (p->btMode ? 0 : 1);
\r
86 if (p->numThreads < 0)
\r
89 ((p->btMode && p->algo) ? 2 : 1);
\r
95 UInt32 LzmaEncProps_GetDictSize(const CLzmaEncProps *props2)
\r
97 CLzmaEncProps props = *props2;
\r
98 LzmaEncProps_Normalize(&props);
\r
99 return props.dictSize;
\r
102 #if (_MSC_VER >= 1400)
\r
103 /* BSR code is fast for some new CPUs */
\r
104 /* #define LZMA_LOG_BSR */
\r
107 #ifdef LZMA_LOG_BSR
\r
109 #define kDicLogSizeMaxCompress 32
\r
111 #define BSR2_RET(pos, res) { unsigned long zz; _BitScanReverse(&zz, (pos)); res = (zz + zz) + ((pos >> (zz - 1)) & 1); }
\r
113 static UInt32 GetPosSlot1(UInt32 pos)
\r
116 BSR2_RET(pos, res);
\r
119 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }
\r
120 #define GetPosSlot(pos, res) { if (pos < 2) res = pos; else BSR2_RET(pos, res); }
\r
124 #define kNumLogBits (9 + sizeof(size_t) / 2)
\r
125 /* #define kNumLogBits (11 + sizeof(size_t) / 8 * 3) */
\r
127 #define kDicLogSizeMaxCompress ((kNumLogBits - 1) * 2 + 7)
\r
129 static void LzmaEnc_FastPosInit(Byte *g_FastPos)
\r
136 for (slot = 2; slot < kNumLogBits * 2; slot++)
\r
138 size_t k = ((size_t)1 << ((slot >> 1) - 1));
\r
140 for (j = 0; j < k; j++)
\r
141 g_FastPos[j] = (Byte)slot;
\r
146 /* we can use ((limit - pos) >> 31) only if (pos < ((UInt32)1 << 31)) */
\r
148 #define BSR2_RET(pos, res) { UInt32 zz = 6 + ((kNumLogBits - 1) & \
\r
149 (0 - (((((UInt32)1 << (kNumLogBits + 6)) - 1) - pos) >> 31))); \
\r
150 res = p->g_FastPos[pos >> zz] + (zz * 2); }
\r
154 #define BSR2_RET(pos, res) { UInt32 zz = 6 + ((kNumLogBits - 1) & \
\r
155 (0 - (((((UInt32)1 << (kNumLogBits)) - 1) - (pos >> 6)) >> 31))); \
\r
156 res = p->g_FastPos[pos >> zz] + (zz * 2); }
\r
159 #define BSR2_RET(pos, res) { UInt32 zz = (pos < (1 << (kNumLogBits + 6))) ? 6 : 6 + kNumLogBits - 1; \
\r
160 res = p->g_FastPos[pos >> zz] + (zz * 2); }
\r
163 #define BSR2_RET(pos, res) { res = (pos < (1 << (kNumLogBits + 6))) ? \
\r
164 p->g_FastPos[pos >> 6] + 12 : \
\r
165 p->g_FastPos[pos >> (6 + kNumLogBits - 1)] + (6 + (kNumLogBits - 1)) * 2; }
\r
168 #define GetPosSlot1(pos) p->g_FastPos[pos]
\r
169 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }
\r
170 #define GetPosSlot(pos, res) { if (pos < kNumFullDistances) res = p->g_FastPos[pos]; else BSR2_RET(pos, res); }
\r
175 #define LZMA_NUM_REPS 4
\r
177 typedef unsigned CState;
\r
192 UInt32 backs[LZMA_NUM_REPS];
\r
195 #define kNumOpts (1 << 12)
\r
197 #define kNumLenToPosStates 4
\r
198 #define kNumPosSlotBits 6
\r
199 #define kDicLogSizeMin 0
\r
200 #define kDicLogSizeMax 32
\r
201 #define kDistTableSizeMax (kDicLogSizeMax * 2)
\r
204 #define kNumAlignBits 4
\r
205 #define kAlignTableSize (1 << kNumAlignBits)
\r
206 #define kAlignMask (kAlignTableSize - 1)
\r
208 #define kStartPosModelIndex 4
\r
209 #define kEndPosModelIndex 14
\r
210 #define kNumPosModels (kEndPosModelIndex - kStartPosModelIndex)
\r
212 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
\r
214 #ifdef _LZMA_PROB32
\r
215 #define CLzmaProb UInt32
\r
217 #define CLzmaProb UInt16
\r
220 #define LZMA_PB_MAX 4
\r
221 #define LZMA_LC_MAX 8
\r
222 #define LZMA_LP_MAX 4
\r
224 #define LZMA_NUM_PB_STATES_MAX (1 << LZMA_PB_MAX)
\r
227 #define kLenNumLowBits 3
\r
228 #define kLenNumLowSymbols (1 << kLenNumLowBits)
\r
229 #define kLenNumMidBits 3
\r
230 #define kLenNumMidSymbols (1 << kLenNumMidBits)
\r
231 #define kLenNumHighBits 8
\r
232 #define kLenNumHighSymbols (1 << kLenNumHighBits)
\r
234 #define kLenNumSymbolsTotal (kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)
\r
236 #define LZMA_MATCH_LEN_MIN 2
\r
237 #define LZMA_MATCH_LEN_MAX (LZMA_MATCH_LEN_MIN + kLenNumSymbolsTotal - 1)
\r
239 #define kNumStates 12
\r
246 CLzmaProb low[LZMA_NUM_PB_STATES_MAX << kLenNumLowBits];
\r
247 CLzmaProb mid[LZMA_NUM_PB_STATES_MAX << kLenNumMidBits];
\r
248 CLzmaProb high[kLenNumHighSymbols];
\r
256 UInt32 prices[LZMA_NUM_PB_STATES_MAX][kLenNumSymbolsTotal];
\r
257 UInt32 counters[LZMA_NUM_PB_STATES_MAX];
\r
270 ISeqOutStream *outStream;
\r
278 CLzmaProb *litProbs;
\r
281 UInt32 reps[LZMA_NUM_REPS];
\r
283 CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];
\r
284 CLzmaProb isRep[kNumStates];
\r
285 CLzmaProb isRepG0[kNumStates];
\r
286 CLzmaProb isRepG1[kNumStates];
\r
287 CLzmaProb isRepG2[kNumStates];
\r
288 CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];
\r
290 CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];
\r
291 CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex];
\r
292 CLzmaProb posAlignEncoder[1 << kNumAlignBits];
\r
294 CLenPriceEnc lenEnc;
\r
295 CLenPriceEnc repLenEnc;
\r
301 void *matchFinderObj;
\r
302 IMatchFinder matchFinder;
\r
304 UInt32 optimumEndIndex;
\r
305 UInt32 optimumCurrentIndex;
\r
307 UInt32 longestMatchLength;
\r
311 UInt32 numFastBytes;
\r
312 UInt32 additionalOffset;
\r
313 UInt32 reps[LZMA_NUM_REPS];
\r
316 unsigned lc, lp, pb;
\r
317 unsigned lpMask, pbMask;
\r
320 CLzmaProb *litProbs;
\r
330 UInt32 matchPriceCount;
\r
331 UInt32 alignPriceCount;
\r
333 UInt32 distTableSize;
\r
342 CMatchFinderMt matchFinderMt;
\r
345 CMatchFinder matchFinderBase;
\r
351 COptimal opt[kNumOpts];
\r
353 #ifndef LZMA_LOG_BSR
\r
354 Byte g_FastPos[1 << kNumLogBits];
\r
357 UInt32 ProbPrices[kBitModelTotal >> kNumMoveReducingBits];
\r
358 UInt32 matches[LZMA_MATCH_LEN_MAX * 2 + 2 + 1];
\r
360 UInt32 posSlotPrices[kNumLenToPosStates][kDistTableSizeMax];
\r
361 UInt32 distancesPrices[kNumLenToPosStates][kNumFullDistances];
\r
362 UInt32 alignPrices[kAlignTableSize];
\r
364 CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];
\r
365 CLzmaProb isRep[kNumStates];
\r
366 CLzmaProb isRepG0[kNumStates];
\r
367 CLzmaProb isRepG1[kNumStates];
\r
368 CLzmaProb isRepG2[kNumStates];
\r
369 CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];
\r
371 CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];
\r
372 CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex];
\r
373 CLzmaProb posAlignEncoder[1 << kNumAlignBits];
\r
375 CLenPriceEnc lenEnc;
\r
376 CLenPriceEnc repLenEnc;
\r
378 CSaveState saveState;
\r
386 void LzmaEnc_SaveState(CLzmaEncHandle pp)
\r
388 CLzmaEnc *p = (CLzmaEnc *)pp;
\r
389 CSaveState *dest = &p->saveState;
\r
391 dest->lenEnc = p->lenEnc;
\r
392 dest->repLenEnc = p->repLenEnc;
\r
393 dest->state = p->state;
\r
395 for (i = 0; i < kNumStates; i++)
\r
397 memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i]));
\r
398 memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i]));
\r
400 for (i = 0; i < kNumLenToPosStates; i++)
\r
401 memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i]));
\r
402 memcpy(dest->isRep, p->isRep, sizeof(p->isRep));
\r
403 memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0));
\r
404 memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1));
\r
405 memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2));
\r
406 memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders));
\r
407 memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder));
\r
408 memcpy(dest->reps, p->reps, sizeof(p->reps));
\r
409 memcpy(dest->litProbs, p->litProbs, ((UInt32)0x300 << p->lclp) * sizeof(CLzmaProb));
\r
412 void LzmaEnc_RestoreState(CLzmaEncHandle pp)
\r
414 CLzmaEnc *dest = (CLzmaEnc *)pp;
\r
415 const CSaveState *p = &dest->saveState;
\r
417 dest->lenEnc = p->lenEnc;
\r
418 dest->repLenEnc = p->repLenEnc;
\r
419 dest->state = p->state;
\r
421 for (i = 0; i < kNumStates; i++)
\r
423 memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i]));
\r
424 memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i]));
\r
426 for (i = 0; i < kNumLenToPosStates; i++)
\r
427 memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i]));
\r
428 memcpy(dest->isRep, p->isRep, sizeof(p->isRep));
\r
429 memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0));
\r
430 memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1));
\r
431 memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2));
\r
432 memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders));
\r
433 memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder));
\r
434 memcpy(dest->reps, p->reps, sizeof(p->reps));
\r
435 memcpy(dest->litProbs, p->litProbs, ((UInt32)0x300 << dest->lclp) * sizeof(CLzmaProb));
\r
438 SRes LzmaEnc_SetProps(CLzmaEncHandle pp, const CLzmaEncProps *props2)
\r
440 CLzmaEnc *p = (CLzmaEnc *)pp;
\r
441 CLzmaEncProps props = *props2;
\r
442 LzmaEncProps_Normalize(&props);
\r
444 if (props.lc > LZMA_LC_MAX
\r
445 || props.lp > LZMA_LP_MAX
\r
446 || props.pb > LZMA_PB_MAX
\r
447 || props.dictSize > ((UInt64)1 << kDicLogSizeMaxCompress)
\r
448 || props.dictSize > kMaxHistorySize)
\r
449 return SZ_ERROR_PARAM;
\r
451 p->dictSize = props.dictSize;
\r
453 unsigned fb = props.fb;
\r
456 if (fb > LZMA_MATCH_LEN_MAX)
\r
457 fb = LZMA_MATCH_LEN_MAX;
\r
458 p->numFastBytes = fb;
\r
463 p->fastMode = (props.algo == 0);
\r
464 p->matchFinderBase.btMode = (Byte)(props.btMode ? 1 : 0);
\r
466 UInt32 numHashBytes = 4;
\r
469 if (props.numHashBytes < 2)
\r
471 else if (props.numHashBytes < 4)
\r
472 numHashBytes = props.numHashBytes;
\r
474 p->matchFinderBase.numHashBytes = numHashBytes;
\r
477 p->matchFinderBase.cutValue = props.mc;
\r
479 p->writeEndMark = props.writeEndMark;
\r
483 if (newMultiThread != _multiThread)
\r
485 ReleaseMatchFinder();
\r
486 _multiThread = newMultiThread;
\r
489 p->multiThread = (props.numThreads > 1);
\r
495 static const int kLiteralNextStates[kNumStates] = {0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5};
\r
496 static const int kMatchNextStates[kNumStates] = {7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10};
\r
497 static const int kRepNextStates[kNumStates] = {8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11};
\r
498 static const int kShortRepNextStates[kNumStates]= {9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11};
\r
500 #define IsCharState(s) ((s) < 7)
\r
502 #define GetLenToPosState(len) (((len) < kNumLenToPosStates + 1) ? (len) - 2 : kNumLenToPosStates - 1)
\r
504 #define kInfinityPrice (1 << 30)
\r
506 static void RangeEnc_Construct(CRangeEnc *p)
\r
508 p->outStream = NULL;
\r
512 #define RangeEnc_GetProcessed(p) ((p)->processed + ((p)->buf - (p)->bufBase) + (p)->cacheSize)
\r
514 #define RC_BUF_SIZE (1 << 16)
\r
515 static int RangeEnc_Alloc(CRangeEnc *p, ISzAlloc *alloc)
\r
519 p->bufBase = (Byte *)alloc->Alloc(alloc, RC_BUF_SIZE);
\r
522 p->bufLim = p->bufBase + RC_BUF_SIZE;
\r
527 static void RangeEnc_Free(CRangeEnc *p, ISzAlloc *alloc)
\r
529 alloc->Free(alloc, p->bufBase);
\r
533 static void RangeEnc_Init(CRangeEnc *p)
\r
535 /* Stream.Init(); */
\r
537 p->range = 0xFFFFFFFF;
\r
541 p->buf = p->bufBase;
\r
547 static void RangeEnc_FlushStream(CRangeEnc *p)
\r
550 if (p->res != SZ_OK)
\r
552 num = p->buf - p->bufBase;
\r
553 if (num != p->outStream->Write(p->outStream, p->bufBase, num))
\r
554 p->res = SZ_ERROR_WRITE;
\r
555 p->processed += num;
\r
556 p->buf = p->bufBase;
\r
559 static void MY_FAST_CALL RangeEnc_ShiftLow(CRangeEnc *p)
\r
561 if ((UInt32)p->low < (UInt32)0xFF000000 || (unsigned)(p->low >> 32) != 0)
\r
563 Byte temp = p->cache;
\r
566 Byte *buf = p->buf;
\r
567 *buf++ = (Byte)(temp + (Byte)(p->low >> 32));
\r
569 if (buf == p->bufLim)
\r
570 RangeEnc_FlushStream(p);
\r
573 while (--p->cacheSize != 0);
\r
574 p->cache = (Byte)((UInt32)p->low >> 24);
\r
577 p->low = (UInt32)p->low << 8;
\r
580 static void RangeEnc_FlushData(CRangeEnc *p)
\r
583 for (i = 0; i < 5; i++)
\r
584 RangeEnc_ShiftLow(p);
\r
587 static void RangeEnc_EncodeDirectBits(CRangeEnc *p, UInt32 value, unsigned numBits)
\r
592 p->low += p->range & (0 - ((value >> --numBits) & 1));
\r
593 if (p->range < kTopValue)
\r
596 RangeEnc_ShiftLow(p);
\r
599 while (numBits != 0);
\r
602 static void RangeEnc_EncodeBit(CRangeEnc *p, CLzmaProb *prob, UInt32 symbol)
\r
604 UInt32 ttt = *prob;
\r
605 UInt32 newBound = (p->range >> kNumBitModelTotalBits) * ttt;
\r
608 p->range = newBound;
\r
609 ttt += (kBitModelTotal - ttt) >> kNumMoveBits;
\r
613 p->low += newBound;
\r
614 p->range -= newBound;
\r
615 ttt -= ttt >> kNumMoveBits;
\r
617 *prob = (CLzmaProb)ttt;
\r
618 if (p->range < kTopValue)
\r
621 RangeEnc_ShiftLow(p);
\r
625 static void LitEnc_Encode(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol)
\r
630 RangeEnc_EncodeBit(p, probs + (symbol >> 8), (symbol >> 7) & 1);
\r
633 while (symbol < 0x10000);
\r
636 static void LitEnc_EncodeMatched(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol, UInt32 matchByte)
\r
638 UInt32 offs = 0x100;
\r
643 RangeEnc_EncodeBit(p, probs + (offs + (matchByte & offs) + (symbol >> 8)), (symbol >> 7) & 1);
\r
645 offs &= ~(matchByte ^ symbol);
\r
647 while (symbol < 0x10000);
\r
650 static void LzmaEnc_InitPriceTables(UInt32 *ProbPrices)
\r
653 for (i = (1 << kNumMoveReducingBits) / 2; i < kBitModelTotal; i += (1 << kNumMoveReducingBits))
\r
655 const int kCyclesBits = kNumBitPriceShiftBits;
\r
657 UInt32 bitCount = 0;
\r
659 for (j = 0; j < kCyclesBits; j++)
\r
663 while (w >= ((UInt32)1 << 16))
\r
669 ProbPrices[i >> kNumMoveReducingBits] = ((kNumBitModelTotalBits << kCyclesBits) - 15 - bitCount);
\r
674 #define GET_PRICE(prob, symbol) \
\r
675 p->ProbPrices[((prob) ^ (((-(int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];
\r
677 #define GET_PRICEa(prob, symbol) \
\r
678 ProbPrices[((prob) ^ ((-((int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];
\r
680 #define GET_PRICE_0(prob) p->ProbPrices[(prob) >> kNumMoveReducingBits]
\r
681 #define GET_PRICE_1(prob) p->ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]
\r
683 #define GET_PRICE_0a(prob) ProbPrices[(prob) >> kNumMoveReducingBits]
\r
684 #define GET_PRICE_1a(prob) ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]
\r
686 static UInt32 LitEnc_GetPrice(const CLzmaProb *probs, UInt32 symbol, const UInt32 *ProbPrices)
\r
692 price += GET_PRICEa(probs[symbol >> 8], (symbol >> 7) & 1);
\r
695 while (symbol < 0x10000);
\r
699 static UInt32 LitEnc_GetPriceMatched(const CLzmaProb *probs, UInt32 symbol, UInt32 matchByte, const UInt32 *ProbPrices)
\r
702 UInt32 offs = 0x100;
\r
707 price += GET_PRICEa(probs[offs + (matchByte & offs) + (symbol >> 8)], (symbol >> 7) & 1);
\r
709 offs &= ~(matchByte ^ symbol);
\r
711 while (symbol < 0x10000);
\r
716 static void RcTree_Encode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol)
\r
720 for (i = numBitLevels; i != 0;)
\r
724 bit = (symbol >> i) & 1;
\r
725 RangeEnc_EncodeBit(rc, probs + m, bit);
\r
726 m = (m << 1) | bit;
\r
730 static void RcTree_ReverseEncode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol)
\r
734 for (i = 0; i < numBitLevels; i++)
\r
736 UInt32 bit = symbol & 1;
\r
737 RangeEnc_EncodeBit(rc, probs + m, bit);
\r
738 m = (m << 1) | bit;
\r
743 static UInt32 RcTree_GetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, const UInt32 *ProbPrices)
\r
746 symbol |= (1 << numBitLevels);
\r
747 while (symbol != 1)
\r
749 price += GET_PRICEa(probs[symbol >> 1], symbol & 1);
\r
755 static UInt32 RcTree_ReverseGetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, const UInt32 *ProbPrices)
\r
760 for (i = numBitLevels; i != 0; i--)
\r
762 UInt32 bit = symbol & 1;
\r
764 price += GET_PRICEa(probs[m], bit);
\r
765 m = (m << 1) | bit;
\r
771 static void LenEnc_Init(CLenEnc *p)
\r
774 p->choice = p->choice2 = kProbInitValue;
\r
775 for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumLowBits); i++)
\r
776 p->low[i] = kProbInitValue;
\r
777 for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumMidBits); i++)
\r
778 p->mid[i] = kProbInitValue;
\r
779 for (i = 0; i < kLenNumHighSymbols; i++)
\r
780 p->high[i] = kProbInitValue;
\r
783 static void LenEnc_Encode(CLenEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState)
\r
785 if (symbol < kLenNumLowSymbols)
\r
787 RangeEnc_EncodeBit(rc, &p->choice, 0);
\r
788 RcTree_Encode(rc, p->low + (posState << kLenNumLowBits), kLenNumLowBits, symbol);
\r
792 RangeEnc_EncodeBit(rc, &p->choice, 1);
\r
793 if (symbol < kLenNumLowSymbols + kLenNumMidSymbols)
\r
795 RangeEnc_EncodeBit(rc, &p->choice2, 0);
\r
796 RcTree_Encode(rc, p->mid + (posState << kLenNumMidBits), kLenNumMidBits, symbol - kLenNumLowSymbols);
\r
800 RangeEnc_EncodeBit(rc, &p->choice2, 1);
\r
801 RcTree_Encode(rc, p->high, kLenNumHighBits, symbol - kLenNumLowSymbols - kLenNumMidSymbols);
\r
806 static void LenEnc_SetPrices(CLenEnc *p, UInt32 posState, UInt32 numSymbols, UInt32 *prices, const UInt32 *ProbPrices)
\r
808 UInt32 a0 = GET_PRICE_0a(p->choice);
\r
809 UInt32 a1 = GET_PRICE_1a(p->choice);
\r
810 UInt32 b0 = a1 + GET_PRICE_0a(p->choice2);
\r
811 UInt32 b1 = a1 + GET_PRICE_1a(p->choice2);
\r
813 for (i = 0; i < kLenNumLowSymbols; i++)
\r
815 if (i >= numSymbols)
\r
817 prices[i] = a0 + RcTree_GetPrice(p->low + (posState << kLenNumLowBits), kLenNumLowBits, i, ProbPrices);
\r
819 for (; i < kLenNumLowSymbols + kLenNumMidSymbols; i++)
\r
821 if (i >= numSymbols)
\r
823 prices[i] = b0 + RcTree_GetPrice(p->mid + (posState << kLenNumMidBits), kLenNumMidBits, i - kLenNumLowSymbols, ProbPrices);
\r
825 for (; i < numSymbols; i++)
\r
826 prices[i] = b1 + RcTree_GetPrice(p->high, kLenNumHighBits, i - kLenNumLowSymbols - kLenNumMidSymbols, ProbPrices);
\r
829 static void MY_FAST_CALL LenPriceEnc_UpdateTable(CLenPriceEnc *p, UInt32 posState, const UInt32 *ProbPrices)
\r
831 LenEnc_SetPrices(&p->p, posState, p->tableSize, p->prices[posState], ProbPrices);
\r
832 p->counters[posState] = p->tableSize;
\r
835 static void LenPriceEnc_UpdateTables(CLenPriceEnc *p, UInt32 numPosStates, const UInt32 *ProbPrices)
\r
838 for (posState = 0; posState < numPosStates; posState++)
\r
839 LenPriceEnc_UpdateTable(p, posState, ProbPrices);
\r
842 static void LenEnc_Encode2(CLenPriceEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState, Bool updatePrice, const UInt32 *ProbPrices)
\r
844 LenEnc_Encode(&p->p, rc, symbol, posState);
\r
846 if (--p->counters[posState] == 0)
\r
847 LenPriceEnc_UpdateTable(p, posState, ProbPrices);
\r
853 static void MovePos(CLzmaEnc *p, UInt32 num)
\r
856 g_STAT_OFFSET += num;
\r
857 printf("\n MovePos %u", num);
\r
862 p->additionalOffset += num;
\r
863 p->matchFinder.Skip(p->matchFinderObj, num);
\r
867 static UInt32 ReadMatchDistances(CLzmaEnc *p, UInt32 *numDistancePairsRes)
\r
869 UInt32 lenRes = 0, numPairs;
\r
870 p->numAvail = p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);
\r
871 numPairs = p->matchFinder.GetMatches(p->matchFinderObj, p->matches);
\r
874 printf("\n i = %u numPairs = %u ", g_STAT_OFFSET, numPairs / 2);
\r
878 for (i = 0; i < numPairs; i += 2)
\r
879 printf("%2u %6u | ", p->matches[i], p->matches[i + 1]);
\r
885 lenRes = p->matches[numPairs - 2];
\r
886 if (lenRes == p->numFastBytes)
\r
888 UInt32 numAvail = p->numAvail;
\r
889 if (numAvail > LZMA_MATCH_LEN_MAX)
\r
890 numAvail = LZMA_MATCH_LEN_MAX;
\r
892 const Byte *pbyCur = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
\r
893 const Byte *pby = pbyCur + lenRes;
\r
894 ptrdiff_t dif = (ptrdiff_t)-1 - p->matches[numPairs - 1];
\r
895 const Byte *pbyLim = pbyCur + numAvail;
\r
896 for (; pby != pbyLim && *pby == pby[dif]; pby++);
\r
897 lenRes = (UInt32)(pby - pbyCur);
\r
901 p->additionalOffset++;
\r
902 *numDistancePairsRes = numPairs;
\r
907 #define MakeAsChar(p) (p)->backPrev = (UInt32)(-1); (p)->prev1IsChar = False;
\r
908 #define MakeAsShortRep(p) (p)->backPrev = 0; (p)->prev1IsChar = False;
\r
909 #define IsShortRep(p) ((p)->backPrev == 0)
\r
911 static UInt32 GetRepLen1Price(CLzmaEnc *p, UInt32 state, UInt32 posState)
\r
914 GET_PRICE_0(p->isRepG0[state]) +
\r
915 GET_PRICE_0(p->isRep0Long[state][posState]);
\r
918 static UInt32 GetPureRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 state, UInt32 posState)
\r
923 price = GET_PRICE_0(p->isRepG0[state]);
\r
924 price += GET_PRICE_1(p->isRep0Long[state][posState]);
\r
928 price = GET_PRICE_1(p->isRepG0[state]);
\r
930 price += GET_PRICE_0(p->isRepG1[state]);
\r
933 price += GET_PRICE_1(p->isRepG1[state]);
\r
934 price += GET_PRICE(p->isRepG2[state], repIndex - 2);
\r
940 static UInt32 GetRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 len, UInt32 state, UInt32 posState)
\r
942 return p->repLenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN] +
\r
943 GetPureRepPrice(p, repIndex, state, posState);
\r
946 static UInt32 Backward(CLzmaEnc *p, UInt32 *backRes, UInt32 cur)
\r
948 UInt32 posMem = p->opt[cur].posPrev;
\r
949 UInt32 backMem = p->opt[cur].backPrev;
\r
950 p->optimumEndIndex = cur;
\r
953 if (p->opt[cur].prev1IsChar)
\r
955 MakeAsChar(&p->opt[posMem])
\r
956 p->opt[posMem].posPrev = posMem - 1;
\r
957 if (p->opt[cur].prev2)
\r
959 p->opt[posMem - 1].prev1IsChar = False;
\r
960 p->opt[posMem - 1].posPrev = p->opt[cur].posPrev2;
\r
961 p->opt[posMem - 1].backPrev = p->opt[cur].backPrev2;
\r
965 UInt32 posPrev = posMem;
\r
966 UInt32 backCur = backMem;
\r
968 backMem = p->opt[posPrev].backPrev;
\r
969 posMem = p->opt[posPrev].posPrev;
\r
971 p->opt[posPrev].backPrev = backCur;
\r
972 p->opt[posPrev].posPrev = cur;
\r
977 *backRes = p->opt[0].backPrev;
\r
978 p->optimumCurrentIndex = p->opt[0].posPrev;
\r
979 return p->optimumCurrentIndex;
\r
982 #define LIT_PROBS(pos, prevByte) (p->litProbs + ((((pos) & p->lpMask) << p->lc) + ((prevByte) >> (8 - p->lc))) * (UInt32)0x300)
\r
984 static UInt32 GetOptimum(CLzmaEnc *p, UInt32 position, UInt32 *backRes)
\r
986 UInt32 lenEnd, cur;
\r
987 UInt32 reps[LZMA_NUM_REPS], repLens[LZMA_NUM_REPS];
\r
992 UInt32 numAvail, mainLen, numPairs, repMaxIndex, i, posState, len;
\r
993 UInt32 matchPrice, repMatchPrice, normalMatchPrice;
\r
995 Byte curByte, matchByte;
\r
997 if (p->optimumEndIndex != p->optimumCurrentIndex)
\r
999 const COptimal *opt = &p->opt[p->optimumCurrentIndex];
\r
1000 UInt32 lenRes = opt->posPrev - p->optimumCurrentIndex;
\r
1001 *backRes = opt->backPrev;
\r
1002 p->optimumCurrentIndex = opt->posPrev;
\r
1005 p->optimumCurrentIndex = p->optimumEndIndex = 0;
\r
1007 if (p->additionalOffset == 0)
\r
1008 mainLen = ReadMatchDistances(p, &numPairs);
\r
1011 mainLen = p->longestMatchLength;
\r
1012 numPairs = p->numPairs;
\r
1015 numAvail = p->numAvail;
\r
1018 *backRes = (UInt32)(-1);
\r
1021 if (numAvail > LZMA_MATCH_LEN_MAX)
\r
1022 numAvail = LZMA_MATCH_LEN_MAX;
\r
1024 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
\r
1026 for (i = 0; i < LZMA_NUM_REPS; i++)
\r
1029 const Byte *data2;
\r
1030 reps[i] = p->reps[i];
\r
1031 data2 = data - reps[i] - 1;
\r
1032 if (data[0] != data2[0] || data[1] != data2[1])
\r
1037 for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; lenTest++);
\r
1038 repLens[i] = lenTest;
\r
1039 if (lenTest > repLens[repMaxIndex])
\r
1042 if (repLens[repMaxIndex] >= p->numFastBytes)
\r
1045 *backRes = repMaxIndex;
\r
1046 lenRes = repLens[repMaxIndex];
\r
1047 MovePos(p, lenRes - 1);
\r
1051 matches = p->matches;
\r
1052 if (mainLen >= p->numFastBytes)
\r
1054 *backRes = matches[numPairs - 1] + LZMA_NUM_REPS;
\r
1055 MovePos(p, mainLen - 1);
\r
1059 matchByte = *(data - (reps[0] + 1));
\r
1061 if (mainLen < 2 && curByte != matchByte && repLens[repMaxIndex] < 2)
\r
1063 *backRes = (UInt32)-1;
\r
1067 p->opt[0].state = (CState)p->state;
\r
1069 posState = (position & p->pbMask);
\r
1072 const CLzmaProb *probs = LIT_PROBS(position, *(data - 1));
\r
1073 p->opt[1].price = GET_PRICE_0(p->isMatch[p->state][posState]) +
\r
1074 (!IsCharState(p->state) ?
\r
1075 LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) :
\r
1076 LitEnc_GetPrice(probs, curByte, p->ProbPrices));
\r
1079 MakeAsChar(&p->opt[1]);
\r
1081 matchPrice = GET_PRICE_1(p->isMatch[p->state][posState]);
\r
1082 repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[p->state]);
\r
1084 if (matchByte == curByte)
\r
1086 UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, p->state, posState);
\r
1087 if (shortRepPrice < p->opt[1].price)
\r
1089 p->opt[1].price = shortRepPrice;
\r
1090 MakeAsShortRep(&p->opt[1]);
\r
1093 lenEnd = ((mainLen >= repLens[repMaxIndex]) ? mainLen : repLens[repMaxIndex]);
\r
1097 *backRes = p->opt[1].backPrev;
\r
1101 p->opt[1].posPrev = 0;
\r
1102 for (i = 0; i < LZMA_NUM_REPS; i++)
\r
1103 p->opt[0].backs[i] = reps[i];
\r
1107 p->opt[len--].price = kInfinityPrice;
\r
1110 for (i = 0; i < LZMA_NUM_REPS; i++)
\r
1112 UInt32 repLen = repLens[i];
\r
1116 price = repMatchPrice + GetPureRepPrice(p, i, p->state, posState);
\r
1119 UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][repLen - 2];
\r
1120 COptimal *opt = &p->opt[repLen];
\r
1121 if (curAndLenPrice < opt->price)
\r
1123 opt->price = curAndLenPrice;
\r
1125 opt->backPrev = i;
\r
1126 opt->prev1IsChar = False;
\r
1129 while (--repLen >= 2);
\r
1132 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[p->state]);
\r
1134 len = ((repLens[0] >= 2) ? repLens[0] + 1 : 2);
\r
1135 if (len <= mainLen)
\r
1138 while (len > matches[offs])
\r
1143 UInt32 distance = matches[offs + 1];
\r
1145 UInt32 curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN];
\r
1146 UInt32 lenToPosState = GetLenToPosState(len);
\r
1147 if (distance < kNumFullDistances)
\r
1148 curAndLenPrice += p->distancesPrices[lenToPosState][distance];
\r
1152 GetPosSlot2(distance, slot);
\r
1153 curAndLenPrice += p->alignPrices[distance & kAlignMask] + p->posSlotPrices[lenToPosState][slot];
\r
1155 opt = &p->opt[len];
\r
1156 if (curAndLenPrice < opt->price)
\r
1158 opt->price = curAndLenPrice;
\r
1160 opt->backPrev = distance + LZMA_NUM_REPS;
\r
1161 opt->prev1IsChar = False;
\r
1163 if (len == matches[offs])
\r
1166 if (offs == numPairs)
\r
1175 /* if (position >= 0) */
\r
1178 printf("\n pos = %4X", position);
\r
1179 for (i = cur; i <= lenEnd; i++)
\r
1180 printf("\nprice[%4X] = %u", position - cur + i, p->opt[i].price);
\r
1189 UInt32 numAvailFull, newLen, numPairs, posPrev, state, posState, startLen;
\r
1190 UInt32 curPrice, curAnd1Price, matchPrice, repMatchPrice;
\r
1192 Byte curByte, matchByte;
\r
1195 COptimal *nextOpt;
\r
1198 if (cur == lenEnd)
\r
1199 return Backward(p, backRes, cur);
\r
1201 newLen = ReadMatchDistances(p, &numPairs);
\r
1202 if (newLen >= p->numFastBytes)
\r
1204 p->numPairs = numPairs;
\r
1205 p->longestMatchLength = newLen;
\r
1206 return Backward(p, backRes, cur);
\r
1209 curOpt = &p->opt[cur];
\r
1210 posPrev = curOpt->posPrev;
\r
1211 if (curOpt->prev1IsChar)
\r
1214 if (curOpt->prev2)
\r
1216 state = p->opt[curOpt->posPrev2].state;
\r
1217 if (curOpt->backPrev2 < LZMA_NUM_REPS)
\r
1218 state = kRepNextStates[state];
\r
1220 state = kMatchNextStates[state];
\r
1223 state = p->opt[posPrev].state;
\r
1224 state = kLiteralNextStates[state];
\r
1227 state = p->opt[posPrev].state;
\r
1228 if (posPrev == cur - 1)
\r
1230 if (IsShortRep(curOpt))
\r
1231 state = kShortRepNextStates[state];
\r
1233 state = kLiteralNextStates[state];
\r
1238 const COptimal *prevOpt;
\r
1239 if (curOpt->prev1IsChar && curOpt->prev2)
\r
1241 posPrev = curOpt->posPrev2;
\r
1242 pos = curOpt->backPrev2;
\r
1243 state = kRepNextStates[state];
\r
1247 pos = curOpt->backPrev;
\r
1248 if (pos < LZMA_NUM_REPS)
\r
1249 state = kRepNextStates[state];
\r
1251 state = kMatchNextStates[state];
\r
1253 prevOpt = &p->opt[posPrev];
\r
1254 if (pos < LZMA_NUM_REPS)
\r
1257 reps[0] = prevOpt->backs[pos];
\r
1258 for (i = 1; i <= pos; i++)
\r
1259 reps[i] = prevOpt->backs[i - 1];
\r
1260 for (; i < LZMA_NUM_REPS; i++)
\r
1261 reps[i] = prevOpt->backs[i];
\r
1266 reps[0] = (pos - LZMA_NUM_REPS);
\r
1267 for (i = 1; i < LZMA_NUM_REPS; i++)
\r
1268 reps[i] = prevOpt->backs[i - 1];
\r
1271 curOpt->state = (CState)state;
\r
1273 curOpt->backs[0] = reps[0];
\r
1274 curOpt->backs[1] = reps[1];
\r
1275 curOpt->backs[2] = reps[2];
\r
1276 curOpt->backs[3] = reps[3];
\r
1278 curPrice = curOpt->price;
\r
1279 nextIsChar = False;
\r
1280 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
\r
1282 matchByte = *(data - (reps[0] + 1));
\r
1284 posState = (position & p->pbMask);
\r
1286 curAnd1Price = curPrice + GET_PRICE_0(p->isMatch[state][posState]);
\r
1288 const CLzmaProb *probs = LIT_PROBS(position, *(data - 1));
\r
1290 (!IsCharState(state) ?
\r
1291 LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) :
\r
1292 LitEnc_GetPrice(probs, curByte, p->ProbPrices));
\r
1295 nextOpt = &p->opt[cur + 1];
\r
1297 if (curAnd1Price < nextOpt->price)
\r
1299 nextOpt->price = curAnd1Price;
\r
1300 nextOpt->posPrev = cur;
\r
1301 MakeAsChar(nextOpt);
\r
1302 nextIsChar = True;
\r
1305 matchPrice = curPrice + GET_PRICE_1(p->isMatch[state][posState]);
\r
1306 repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[state]);
\r
1308 if (matchByte == curByte && !(nextOpt->posPrev < cur && nextOpt->backPrev == 0))
\r
1310 UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, state, posState);
\r
1311 if (shortRepPrice <= nextOpt->price)
\r
1313 nextOpt->price = shortRepPrice;
\r
1314 nextOpt->posPrev = cur;
\r
1315 MakeAsShortRep(nextOpt);
\r
1316 nextIsChar = True;
\r
1319 numAvailFull = p->numAvail;
\r
1321 UInt32 temp = kNumOpts - 1 - cur;
\r
1322 if (temp < numAvailFull)
\r
1323 numAvailFull = temp;
\r
1326 if (numAvailFull < 2)
\r
1328 numAvail = (numAvailFull <= p->numFastBytes ? numAvailFull : p->numFastBytes);
\r
1330 if (!nextIsChar && matchByte != curByte) /* speed optimization */
\r
1332 /* try Literal + rep0 */
\r
1335 const Byte *data2 = data - reps[0] - 1;
\r
1336 UInt32 limit = p->numFastBytes + 1;
\r
1337 if (limit > numAvailFull)
\r
1338 limit = numAvailFull;
\r
1340 for (temp = 1; temp < limit && data[temp] == data2[temp]; temp++);
\r
1341 lenTest2 = temp - 1;
\r
1342 if (lenTest2 >= 2)
\r
1344 UInt32 state2 = kLiteralNextStates[state];
\r
1345 UInt32 posStateNext = (position + 1) & p->pbMask;
\r
1346 UInt32 nextRepMatchPrice = curAnd1Price +
\r
1347 GET_PRICE_1(p->isMatch[state2][posStateNext]) +
\r
1348 GET_PRICE_1(p->isRep[state2]);
\r
1349 /* for (; lenTest2 >= 2; lenTest2--) */
\r
1351 UInt32 curAndLenPrice;
\r
1353 UInt32 offset = cur + 1 + lenTest2;
\r
1354 while (lenEnd < offset)
\r
1355 p->opt[++lenEnd].price = kInfinityPrice;
\r
1356 curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);
\r
1357 opt = &p->opt[offset];
\r
1358 if (curAndLenPrice < opt->price)
\r
1360 opt->price = curAndLenPrice;
\r
1361 opt->posPrev = cur + 1;
\r
1362 opt->backPrev = 0;
\r
1363 opt->prev1IsChar = True;
\r
1364 opt->prev2 = False;
\r
1370 startLen = 2; /* speed optimization */
\r
1373 for (repIndex = 0; repIndex < LZMA_NUM_REPS; repIndex++)
\r
1376 UInt32 lenTestTemp;
\r
1378 const Byte *data2 = data - reps[repIndex] - 1;
\r
1379 if (data[0] != data2[0] || data[1] != data2[1])
\r
1381 for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; lenTest++);
\r
1382 while (lenEnd < cur + lenTest)
\r
1383 p->opt[++lenEnd].price = kInfinityPrice;
\r
1384 lenTestTemp = lenTest;
\r
1385 price = repMatchPrice + GetPureRepPrice(p, repIndex, state, posState);
\r
1388 UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][lenTest - 2];
\r
1389 COptimal *opt = &p->opt[cur + lenTest];
\r
1390 if (curAndLenPrice < opt->price)
\r
1392 opt->price = curAndLenPrice;
\r
1393 opt->posPrev = cur;
\r
1394 opt->backPrev = repIndex;
\r
1395 opt->prev1IsChar = False;
\r
1398 while (--lenTest >= 2);
\r
1399 lenTest = lenTestTemp;
\r
1401 if (repIndex == 0)
\r
1402 startLen = lenTest + 1;
\r
1404 /* if (_maxMode) */
\r
1406 UInt32 lenTest2 = lenTest + 1;
\r
1407 UInt32 limit = lenTest2 + p->numFastBytes;
\r
1408 if (limit > numAvailFull)
\r
1409 limit = numAvailFull;
\r
1410 for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++);
\r
1411 lenTest2 -= lenTest + 1;
\r
1412 if (lenTest2 >= 2)
\r
1414 UInt32 nextRepMatchPrice;
\r
1415 UInt32 state2 = kRepNextStates[state];
\r
1416 UInt32 posStateNext = (position + lenTest) & p->pbMask;
\r
1417 UInt32 curAndLenCharPrice =
\r
1418 price + p->repLenEnc.prices[posState][lenTest - 2] +
\r
1419 GET_PRICE_0(p->isMatch[state2][posStateNext]) +
\r
1420 LitEnc_GetPriceMatched(LIT_PROBS(position + lenTest, data[lenTest - 1]),
\r
1421 data[lenTest], data2[lenTest], p->ProbPrices);
\r
1422 state2 = kLiteralNextStates[state2];
\r
1423 posStateNext = (position + lenTest + 1) & p->pbMask;
\r
1424 nextRepMatchPrice = curAndLenCharPrice +
\r
1425 GET_PRICE_1(p->isMatch[state2][posStateNext]) +
\r
1426 GET_PRICE_1(p->isRep[state2]);
\r
1428 /* for (; lenTest2 >= 2; lenTest2--) */
\r
1430 UInt32 curAndLenPrice;
\r
1432 UInt32 offset = cur + lenTest + 1 + lenTest2;
\r
1433 while (lenEnd < offset)
\r
1434 p->opt[++lenEnd].price = kInfinityPrice;
\r
1435 curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);
\r
1436 opt = &p->opt[offset];
\r
1437 if (curAndLenPrice < opt->price)
\r
1439 opt->price = curAndLenPrice;
\r
1440 opt->posPrev = cur + lenTest + 1;
\r
1441 opt->backPrev = 0;
\r
1442 opt->prev1IsChar = True;
\r
1443 opt->prev2 = True;
\r
1444 opt->posPrev2 = cur;
\r
1445 opt->backPrev2 = repIndex;
\r
1452 /* for (UInt32 lenTest = 2; lenTest <= newLen; lenTest++) */
\r
1453 if (newLen > numAvail)
\r
1455 newLen = numAvail;
\r
1456 for (numPairs = 0; newLen > matches[numPairs]; numPairs += 2);
\r
1457 matches[numPairs] = newLen;
\r
1460 if (newLen >= startLen)
\r
1462 UInt32 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[state]);
\r
1463 UInt32 offs, curBack, posSlot;
\r
1465 while (lenEnd < cur + newLen)
\r
1466 p->opt[++lenEnd].price = kInfinityPrice;
\r
1469 while (startLen > matches[offs])
\r
1471 curBack = matches[offs + 1];
\r
1472 GetPosSlot2(curBack, posSlot);
\r
1473 for (lenTest = /*2*/ startLen; ; lenTest++)
\r
1475 UInt32 curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][lenTest - LZMA_MATCH_LEN_MIN];
\r
1477 UInt32 lenToPosState = GetLenToPosState(lenTest);
\r
1479 if (curBack < kNumFullDistances)
\r
1480 curAndLenPrice += p->distancesPrices[lenToPosState][curBack];
\r
1482 curAndLenPrice += p->posSlotPrices[lenToPosState][posSlot] + p->alignPrices[curBack & kAlignMask];
\r
1484 opt = &p->opt[cur + lenTest];
\r
1485 if (curAndLenPrice < opt->price)
\r
1487 opt->price = curAndLenPrice;
\r
1488 opt->posPrev = cur;
\r
1489 opt->backPrev = curBack + LZMA_NUM_REPS;
\r
1490 opt->prev1IsChar = False;
\r
1494 if (/*_maxMode && */lenTest == matches[offs])
\r
1496 /* Try Match + Literal + Rep0 */
\r
1497 const Byte *data2 = data - curBack - 1;
\r
1498 UInt32 lenTest2 = lenTest + 1;
\r
1499 UInt32 limit = lenTest2 + p->numFastBytes;
\r
1500 if (limit > numAvailFull)
\r
1501 limit = numAvailFull;
\r
1502 for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++);
\r
1503 lenTest2 -= lenTest + 1;
\r
1504 if (lenTest2 >= 2)
\r
1506 UInt32 nextRepMatchPrice;
\r
1507 UInt32 state2 = kMatchNextStates[state];
\r
1508 UInt32 posStateNext = (position + lenTest) & p->pbMask;
\r
1509 UInt32 curAndLenCharPrice = curAndLenPrice +
\r
1510 GET_PRICE_0(p->isMatch[state2][posStateNext]) +
\r
1511 LitEnc_GetPriceMatched(LIT_PROBS(position + lenTest, data[lenTest - 1]),
\r
1512 data[lenTest], data2[lenTest], p->ProbPrices);
\r
1513 state2 = kLiteralNextStates[state2];
\r
1514 posStateNext = (posStateNext + 1) & p->pbMask;
\r
1515 nextRepMatchPrice = curAndLenCharPrice +
\r
1516 GET_PRICE_1(p->isMatch[state2][posStateNext]) +
\r
1517 GET_PRICE_1(p->isRep[state2]);
\r
1519 /* for (; lenTest2 >= 2; lenTest2--) */
\r
1521 UInt32 offset = cur + lenTest + 1 + lenTest2;
\r
1522 UInt32 curAndLenPrice2;
\r
1524 while (lenEnd < offset)
\r
1525 p->opt[++lenEnd].price = kInfinityPrice;
\r
1526 curAndLenPrice2 = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);
\r
1527 opt = &p->opt[offset];
\r
1528 if (curAndLenPrice2 < opt->price)
\r
1530 opt->price = curAndLenPrice2;
\r
1531 opt->posPrev = cur + lenTest + 1;
\r
1532 opt->backPrev = 0;
\r
1533 opt->prev1IsChar = True;
\r
1534 opt->prev2 = True;
\r
1535 opt->posPrev2 = cur;
\r
1536 opt->backPrev2 = curBack + LZMA_NUM_REPS;
\r
1541 if (offs == numPairs)
\r
1543 curBack = matches[offs + 1];
\r
1544 if (curBack >= kNumFullDistances)
\r
1545 GetPosSlot2(curBack, posSlot);
\r
1552 #define ChangePair(smallDist, bigDist) (((bigDist) >> 7) > (smallDist))
\r
1554 static UInt32 GetOptimumFast(CLzmaEnc *p, UInt32 *backRes)
\r
1556 UInt32 numAvail, mainLen, mainDist, numPairs, repIndex, repLen, i;
\r
1558 const UInt32 *matches;
\r
1560 if (p->additionalOffset == 0)
\r
1561 mainLen = ReadMatchDistances(p, &numPairs);
\r
1564 mainLen = p->longestMatchLength;
\r
1565 numPairs = p->numPairs;
\r
1568 numAvail = p->numAvail;
\r
1569 *backRes = (UInt32)-1;
\r
1572 if (numAvail > LZMA_MATCH_LEN_MAX)
\r
1573 numAvail = LZMA_MATCH_LEN_MAX;
\r
1574 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
\r
1576 repLen = repIndex = 0;
\r
1577 for (i = 0; i < LZMA_NUM_REPS; i++)
\r
1580 const Byte *data2 = data - p->reps[i] - 1;
\r
1581 if (data[0] != data2[0] || data[1] != data2[1])
\r
1583 for (len = 2; len < numAvail && data[len] == data2[len]; len++);
\r
1584 if (len >= p->numFastBytes)
\r
1587 MovePos(p, len - 1);
\r
1597 matches = p->matches;
\r
1598 if (mainLen >= p->numFastBytes)
\r
1600 *backRes = matches[numPairs - 1] + LZMA_NUM_REPS;
\r
1601 MovePos(p, mainLen - 1);
\r
1605 mainDist = 0; /* for GCC */
\r
1608 mainDist = matches[numPairs - 1];
\r
1609 while (numPairs > 2 && mainLen == matches[numPairs - 4] + 1)
\r
1611 if (!ChangePair(matches[numPairs - 3], mainDist))
\r
1614 mainLen = matches[numPairs - 2];
\r
1615 mainDist = matches[numPairs - 1];
\r
1617 if (mainLen == 2 && mainDist >= 0x80)
\r
1621 if (repLen >= 2 && (
\r
1622 (repLen + 1 >= mainLen) ||
\r
1623 (repLen + 2 >= mainLen && mainDist >= (1 << 9)) ||
\r
1624 (repLen + 3 >= mainLen && mainDist >= (1 << 15))))
\r
1626 *backRes = repIndex;
\r
1627 MovePos(p, repLen - 1);
\r
1631 if (mainLen < 2 || numAvail <= 2)
\r
1634 p->longestMatchLength = ReadMatchDistances(p, &p->numPairs);
\r
1635 if (p->longestMatchLength >= 2)
\r
1637 UInt32 newDistance = matches[p->numPairs - 1];
\r
1638 if ((p->longestMatchLength >= mainLen && newDistance < mainDist) ||
\r
1639 (p->longestMatchLength == mainLen + 1 && !ChangePair(mainDist, newDistance)) ||
\r
1640 (p->longestMatchLength > mainLen + 1) ||
\r
1641 (p->longestMatchLength + 1 >= mainLen && mainLen >= 3 && ChangePair(newDistance, mainDist)))
\r
1645 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
\r
1646 for (i = 0; i < LZMA_NUM_REPS; i++)
\r
1648 UInt32 len, limit;
\r
1649 const Byte *data2 = data - p->reps[i] - 1;
\r
1650 if (data[0] != data2[0] || data[1] != data2[1])
\r
1652 limit = mainLen - 1;
\r
1653 for (len = 2; len < limit && data[len] == data2[len]; len++);
\r
1657 *backRes = mainDist + LZMA_NUM_REPS;
\r
1658 MovePos(p, mainLen - 2);
\r
1662 static void WriteEndMarker(CLzmaEnc *p, UInt32 posState)
\r
1665 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1);
\r
1666 RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0);
\r
1667 p->state = kMatchNextStates[p->state];
\r
1668 len = LZMA_MATCH_LEN_MIN;
\r
1669 LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);
\r
1670 RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBits, (1 << kNumPosSlotBits) - 1);
\r
1671 RangeEnc_EncodeDirectBits(&p->rc, (((UInt32)1 << 30) - 1) >> kNumAlignBits, 30 - kNumAlignBits);
\r
1672 RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, kAlignMask);
\r
1675 static SRes CheckErrors(CLzmaEnc *p)
\r
1677 if (p->result != SZ_OK)
\r
1679 if (p->rc.res != SZ_OK)
\r
1680 p->result = SZ_ERROR_WRITE;
\r
1681 if (p->matchFinderBase.result != SZ_OK)
\r
1682 p->result = SZ_ERROR_READ;
\r
1683 if (p->result != SZ_OK)
\r
1684 p->finished = True;
\r
1688 static SRes Flush(CLzmaEnc *p, UInt32 nowPos)
\r
1690 /* ReleaseMFStream(); */
\r
1691 p->finished = True;
\r
1692 if (p->writeEndMark)
\r
1693 WriteEndMarker(p, nowPos & p->pbMask);
\r
1694 RangeEnc_FlushData(&p->rc);
\r
1695 RangeEnc_FlushStream(&p->rc);
\r
1696 return CheckErrors(p);
\r
1699 static void FillAlignPrices(CLzmaEnc *p)
\r
1702 for (i = 0; i < kAlignTableSize; i++)
\r
1703 p->alignPrices[i] = RcTree_ReverseGetPrice(p->posAlignEncoder, kNumAlignBits, i, p->ProbPrices);
\r
1704 p->alignPriceCount = 0;
\r
1707 static void FillDistancesPrices(CLzmaEnc *p)
\r
1709 UInt32 tempPrices[kNumFullDistances];
\r
1710 UInt32 i, lenToPosState;
\r
1711 for (i = kStartPosModelIndex; i < kNumFullDistances; i++)
\r
1713 UInt32 posSlot = GetPosSlot1(i);
\r
1714 UInt32 footerBits = ((posSlot >> 1) - 1);
\r
1715 UInt32 base = ((2 | (posSlot & 1)) << footerBits);
\r
1716 tempPrices[i] = RcTree_ReverseGetPrice(p->posEncoders + base - posSlot - 1, footerBits, i - base, p->ProbPrices);
\r
1719 for (lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++)
\r
1722 const CLzmaProb *encoder = p->posSlotEncoder[lenToPosState];
\r
1723 UInt32 *posSlotPrices = p->posSlotPrices[lenToPosState];
\r
1724 for (posSlot = 0; posSlot < p->distTableSize; posSlot++)
\r
1725 posSlotPrices[posSlot] = RcTree_GetPrice(encoder, kNumPosSlotBits, posSlot, p->ProbPrices);
\r
1726 for (posSlot = kEndPosModelIndex; posSlot < p->distTableSize; posSlot++)
\r
1727 posSlotPrices[posSlot] += ((((posSlot >> 1) - 1) - kNumAlignBits) << kNumBitPriceShiftBits);
\r
1730 UInt32 *distancesPrices = p->distancesPrices[lenToPosState];
\r
1731 for (i = 0; i < kStartPosModelIndex; i++)
\r
1732 distancesPrices[i] = posSlotPrices[i];
\r
1733 for (; i < kNumFullDistances; i++)
\r
1734 distancesPrices[i] = posSlotPrices[GetPosSlot1(i)] + tempPrices[i];
\r
1737 p->matchPriceCount = 0;
\r
1740 void LzmaEnc_Construct(CLzmaEnc *p)
\r
1742 RangeEnc_Construct(&p->rc);
\r
1743 MatchFinder_Construct(&p->matchFinderBase);
\r
1746 MatchFinderMt_Construct(&p->matchFinderMt);
\r
1747 p->matchFinderMt.MatchFinder = &p->matchFinderBase;
\r
1751 CLzmaEncProps props;
\r
1752 LzmaEncProps_Init(&props);
\r
1753 LzmaEnc_SetProps(p, &props);
\r
1756 #ifndef LZMA_LOG_BSR
\r
1757 LzmaEnc_FastPosInit(p->g_FastPos);
\r
1760 LzmaEnc_InitPriceTables(p->ProbPrices);
\r
1761 p->litProbs = NULL;
\r
1762 p->saveState.litProbs = NULL;
\r
1765 CLzmaEncHandle LzmaEnc_Create(ISzAlloc *alloc)
\r
1768 p = alloc->Alloc(alloc, sizeof(CLzmaEnc));
\r
1770 LzmaEnc_Construct((CLzmaEnc *)p);
\r
1774 void LzmaEnc_FreeLits(CLzmaEnc *p, ISzAlloc *alloc)
\r
1776 alloc->Free(alloc, p->litProbs);
\r
1777 alloc->Free(alloc, p->saveState.litProbs);
\r
1778 p->litProbs = NULL;
\r
1779 p->saveState.litProbs = NULL;
\r
1782 void LzmaEnc_Destruct(CLzmaEnc *p, ISzAlloc *alloc, ISzAlloc *allocBig)
\r
1785 MatchFinderMt_Destruct(&p->matchFinderMt, allocBig);
\r
1788 MatchFinder_Free(&p->matchFinderBase, allocBig);
\r
1789 LzmaEnc_FreeLits(p, alloc);
\r
1790 RangeEnc_Free(&p->rc, alloc);
\r
1793 void LzmaEnc_Destroy(CLzmaEncHandle p, ISzAlloc *alloc, ISzAlloc *allocBig)
\r
1795 LzmaEnc_Destruct((CLzmaEnc *)p, alloc, allocBig);
\r
1796 alloc->Free(alloc, p);
\r
1799 static SRes LzmaEnc_CodeOneBlock(CLzmaEnc *p, Bool useLimits, UInt32 maxPackSize, UInt32 maxUnpackSize)
\r
1801 UInt32 nowPos32, startPos32;
\r
1804 p->matchFinder.Init(p->matchFinderObj);
\r
1810 RINOK(CheckErrors(p));
\r
1812 nowPos32 = (UInt32)p->nowPos64;
\r
1813 startPos32 = nowPos32;
\r
1815 if (p->nowPos64 == 0)
\r
1819 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)
\r
1820 return Flush(p, nowPos32);
\r
1821 ReadMatchDistances(p, &numPairs);
\r
1822 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][0], 0);
\r
1823 p->state = kLiteralNextStates[p->state];
\r
1824 curByte = *(p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset);
\r
1825 LitEnc_Encode(&p->rc, p->litProbs, curByte);
\r
1826 p->additionalOffset--;
\r
1830 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) != 0)
\r
1833 UInt32 pos, len, posState;
\r
1836 len = GetOptimumFast(p, &pos);
\r
1838 len = GetOptimum(p, nowPos32, &pos);
\r
1841 printf("\n pos = %4X, len = %u pos = %u", nowPos32, len, pos);
\r
1844 posState = nowPos32 & p->pbMask;
\r
1845 if (len == 1 && pos == (UInt32)-1)
\r
1851 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 0);
\r
1852 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
\r
1854 probs = LIT_PROBS(nowPos32, *(data - 1));
\r
1855 if (IsCharState(p->state))
\r
1856 LitEnc_Encode(&p->rc, probs, curByte);
\r
1858 LitEnc_EncodeMatched(&p->rc, probs, curByte, *(data - p->reps[0] - 1));
\r
1859 p->state = kLiteralNextStates[p->state];
\r
1863 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1);
\r
1864 if (pos < LZMA_NUM_REPS)
\r
1866 RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 1);
\r
1869 RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 0);
\r
1870 RangeEnc_EncodeBit(&p->rc, &p->isRep0Long[p->state][posState], ((len == 1) ? 0 : 1));
\r
1874 UInt32 distance = p->reps[pos];
\r
1875 RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 1);
\r
1877 RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 0);
\r
1880 RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 1);
\r
1881 RangeEnc_EncodeBit(&p->rc, &p->isRepG2[p->state], pos - 2);
\r
1883 p->reps[3] = p->reps[2];
\r
1884 p->reps[2] = p->reps[1];
\r
1886 p->reps[1] = p->reps[0];
\r
1887 p->reps[0] = distance;
\r
1890 p->state = kShortRepNextStates[p->state];
\r
1893 LenEnc_Encode2(&p->repLenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);
\r
1894 p->state = kRepNextStates[p->state];
\r
1900 RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0);
\r
1901 p->state = kMatchNextStates[p->state];
\r
1902 LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);
\r
1903 pos -= LZMA_NUM_REPS;
\r
1904 GetPosSlot(pos, posSlot);
\r
1905 RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBits, posSlot);
\r
1907 if (posSlot >= kStartPosModelIndex)
\r
1909 UInt32 footerBits = ((posSlot >> 1) - 1);
\r
1910 UInt32 base = ((2 | (posSlot & 1)) << footerBits);
\r
1911 UInt32 posReduced = pos - base;
\r
1913 if (posSlot < kEndPosModelIndex)
\r
1914 RcTree_ReverseEncode(&p->rc, p->posEncoders + base - posSlot - 1, footerBits, posReduced);
\r
1917 RangeEnc_EncodeDirectBits(&p->rc, posReduced >> kNumAlignBits, footerBits - kNumAlignBits);
\r
1918 RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, posReduced & kAlignMask);
\r
1919 p->alignPriceCount++;
\r
1922 p->reps[3] = p->reps[2];
\r
1923 p->reps[2] = p->reps[1];
\r
1924 p->reps[1] = p->reps[0];
\r
1926 p->matchPriceCount++;
\r
1929 p->additionalOffset -= len;
\r
1931 if (p->additionalOffset == 0)
\r
1936 if (p->matchPriceCount >= (1 << 7))
\r
1937 FillDistancesPrices(p);
\r
1938 if (p->alignPriceCount >= kAlignTableSize)
\r
1939 FillAlignPrices(p);
\r
1941 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)
\r
1943 processed = nowPos32 - startPos32;
\r
1946 if (processed + kNumOpts + 300 >= maxUnpackSize ||
\r
1947 RangeEnc_GetProcessed(&p->rc) + kNumOpts * 2 >= maxPackSize)
\r
1950 else if (processed >= (1 << 17))
\r
1952 p->nowPos64 += nowPos32 - startPos32;
\r
1953 return CheckErrors(p);
\r
1957 p->nowPos64 += nowPos32 - startPos32;
\r
1958 return Flush(p, nowPos32);
\r
1961 #define kBigHashDicLimit ((UInt32)1 << 24)
\r
1963 static SRes LzmaEnc_Alloc(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)
\r
1965 UInt32 beforeSize = kNumOpts;
\r
1966 if (!RangeEnc_Alloc(&p->rc, alloc))
\r
1967 return SZ_ERROR_MEM;
\r
1970 p->mtMode = (p->multiThread && !p->fastMode && (p->matchFinderBase.btMode != 0));
\r
1974 unsigned lclp = p->lc + p->lp;
\r
1975 if (!p->litProbs || !p->saveState.litProbs || p->lclp != lclp)
\r
1977 LzmaEnc_FreeLits(p, alloc);
\r
1978 p->litProbs = (CLzmaProb *)alloc->Alloc(alloc, ((UInt32)0x300 << lclp) * sizeof(CLzmaProb));
\r
1979 p->saveState.litProbs = (CLzmaProb *)alloc->Alloc(alloc, ((UInt32)0x300 << lclp) * sizeof(CLzmaProb));
\r
1980 if (!p->litProbs || !p->saveState.litProbs)
\r
1982 LzmaEnc_FreeLits(p, alloc);
\r
1983 return SZ_ERROR_MEM;
\r
1989 p->matchFinderBase.bigHash = (Byte)(p->dictSize > kBigHashDicLimit ? 1 : 0);
\r
1991 if (beforeSize + p->dictSize < keepWindowSize)
\r
1992 beforeSize = keepWindowSize - p->dictSize;
\r
1997 RINOK(MatchFinderMt_Create(&p->matchFinderMt, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig));
\r
1998 p->matchFinderObj = &p->matchFinderMt;
\r
1999 MatchFinderMt_CreateVTable(&p->matchFinderMt, &p->matchFinder);
\r
2004 if (!MatchFinder_Create(&p->matchFinderBase, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig))
\r
2005 return SZ_ERROR_MEM;
\r
2006 p->matchFinderObj = &p->matchFinderBase;
\r
2007 MatchFinder_CreateVTable(&p->matchFinderBase, &p->matchFinder);
\r
2013 void LzmaEnc_Init(CLzmaEnc *p)
\r
2017 for (i = 0 ; i < LZMA_NUM_REPS; i++)
\r
2020 RangeEnc_Init(&p->rc);
\r
2023 for (i = 0; i < kNumStates; i++)
\r
2026 for (j = 0; j < LZMA_NUM_PB_STATES_MAX; j++)
\r
2028 p->isMatch[i][j] = kProbInitValue;
\r
2029 p->isRep0Long[i][j] = kProbInitValue;
\r
2031 p->isRep[i] = kProbInitValue;
\r
2032 p->isRepG0[i] = kProbInitValue;
\r
2033 p->isRepG1[i] = kProbInitValue;
\r
2034 p->isRepG2[i] = kProbInitValue;
\r
2038 UInt32 num = (UInt32)0x300 << (p->lp + p->lc);
\r
2039 CLzmaProb *probs = p->litProbs;
\r
2040 for (i = 0; i < num; i++)
\r
2041 probs[i] = kProbInitValue;
\r
2045 for (i = 0; i < kNumLenToPosStates; i++)
\r
2047 CLzmaProb *probs = p->posSlotEncoder[i];
\r
2049 for (j = 0; j < (1 << kNumPosSlotBits); j++)
\r
2050 probs[j] = kProbInitValue;
\r
2054 for (i = 0; i < kNumFullDistances - kEndPosModelIndex; i++)
\r
2055 p->posEncoders[i] = kProbInitValue;
\r
2058 LenEnc_Init(&p->lenEnc.p);
\r
2059 LenEnc_Init(&p->repLenEnc.p);
\r
2061 for (i = 0; i < (1 << kNumAlignBits); i++)
\r
2062 p->posAlignEncoder[i] = kProbInitValue;
\r
2064 p->optimumEndIndex = 0;
\r
2065 p->optimumCurrentIndex = 0;
\r
2066 p->additionalOffset = 0;
\r
2068 p->pbMask = (1 << p->pb) - 1;
\r
2069 p->lpMask = (1 << p->lp) - 1;
\r
2072 void LzmaEnc_InitPrices(CLzmaEnc *p)
\r
2076 FillDistancesPrices(p);
\r
2077 FillAlignPrices(p);
\r
2080 p->lenEnc.tableSize =
\r
2081 p->repLenEnc.tableSize =
\r
2082 p->numFastBytes + 1 - LZMA_MATCH_LEN_MIN;
\r
2083 LenPriceEnc_UpdateTables(&p->lenEnc, 1 << p->pb, p->ProbPrices);
\r
2084 LenPriceEnc_UpdateTables(&p->repLenEnc, 1 << p->pb, p->ProbPrices);
\r
2087 static SRes LzmaEnc_AllocAndInit(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)
\r
2090 for (i = 0; i < (UInt32)kDicLogSizeMaxCompress; i++)
\r
2091 if (p->dictSize <= ((UInt32)1 << i))
\r
2093 p->distTableSize = i * 2;
\r
2095 p->finished = False;
\r
2096 p->result = SZ_OK;
\r
2097 RINOK(LzmaEnc_Alloc(p, keepWindowSize, alloc, allocBig));
\r
2099 LzmaEnc_InitPrices(p);
\r
2104 static SRes LzmaEnc_Prepare(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream,
\r
2105 ISzAlloc *alloc, ISzAlloc *allocBig)
\r
2107 CLzmaEnc *p = (CLzmaEnc *)pp;
\r
2108 p->matchFinderBase.stream = inStream;
\r
2110 p->rc.outStream = outStream;
\r
2111 return LzmaEnc_AllocAndInit(p, 0, alloc, allocBig);
\r
2114 SRes LzmaEnc_PrepareForLzma2(CLzmaEncHandle pp,
\r
2115 ISeqInStream *inStream, UInt32 keepWindowSize,
\r
2116 ISzAlloc *alloc, ISzAlloc *allocBig)
\r
2118 CLzmaEnc *p = (CLzmaEnc *)pp;
\r
2119 p->matchFinderBase.stream = inStream;
\r
2121 return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);
\r
2124 static void LzmaEnc_SetInputBuf(CLzmaEnc *p, const Byte *src, SizeT srcLen)
\r
2126 p->matchFinderBase.directInput = 1;
\r
2127 p->matchFinderBase.bufferBase = (Byte *)src;
\r
2128 p->matchFinderBase.directInputRem = srcLen;
\r
2131 SRes LzmaEnc_MemPrepare(CLzmaEncHandle pp, const Byte *src, SizeT srcLen,
\r
2132 UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)
\r
2134 CLzmaEnc *p = (CLzmaEnc *)pp;
\r
2135 LzmaEnc_SetInputBuf(p, src, srcLen);
\r
2138 return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);
\r
2141 void LzmaEnc_Finish(CLzmaEncHandle pp)
\r
2144 CLzmaEnc *p = (CLzmaEnc *)pp;
\r
2146 MatchFinderMt_ReleaseStream(&p->matchFinderMt);
\r
2155 ISeqOutStream funcTable;
\r
2159 } CSeqOutStreamBuf;
\r
2161 static size_t MyWrite(void *pp, const void *data, size_t size)
\r
2163 CSeqOutStreamBuf *p = (CSeqOutStreamBuf *)pp;
\r
2164 if (p->rem < size)
\r
2167 p->overflow = True;
\r
2169 memcpy(p->data, data, size);
\r
2176 UInt32 LzmaEnc_GetNumAvailableBytes(CLzmaEncHandle pp)
\r
2178 const CLzmaEnc *p = (CLzmaEnc *)pp;
\r
2179 return p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);
\r
2183 const Byte *LzmaEnc_GetCurBuf(CLzmaEncHandle pp)
\r
2185 const CLzmaEnc *p = (CLzmaEnc *)pp;
\r
2186 return p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
\r
2190 SRes LzmaEnc_CodeOneMemBlock(CLzmaEncHandle pp, Bool reInit,
\r
2191 Byte *dest, size_t *destLen, UInt32 desiredPackSize, UInt32 *unpackSize)
\r
2193 CLzmaEnc *p = (CLzmaEnc *)pp;
\r
2196 CSeqOutStreamBuf outStream;
\r
2198 outStream.funcTable.Write = MyWrite;
\r
2199 outStream.data = dest;
\r
2200 outStream.rem = *destLen;
\r
2201 outStream.overflow = False;
\r
2203 p->writeEndMark = False;
\r
2204 p->finished = False;
\r
2205 p->result = SZ_OK;
\r
2209 LzmaEnc_InitPrices(p);
\r
2210 nowPos64 = p->nowPos64;
\r
2211 RangeEnc_Init(&p->rc);
\r
2212 p->rc.outStream = &outStream.funcTable;
\r
2214 res = LzmaEnc_CodeOneBlock(p, True, desiredPackSize, *unpackSize);
\r
2216 *unpackSize = (UInt32)(p->nowPos64 - nowPos64);
\r
2217 *destLen -= outStream.rem;
\r
2218 if (outStream.overflow)
\r
2219 return SZ_ERROR_OUTPUT_EOF;
\r
2225 static SRes LzmaEnc_Encode2(CLzmaEnc *p, ICompressProgress *progress)
\r
2230 Byte allocaDummy[0x300];
\r
2231 allocaDummy[0] = 0;
\r
2232 allocaDummy[1] = allocaDummy[0];
\r
2237 res = LzmaEnc_CodeOneBlock(p, False, 0, 0);
\r
2238 if (res != SZ_OK || p->finished)
\r
2242 res = progress->Progress(progress, p->nowPos64, RangeEnc_GetProcessed(&p->rc));
\r
2245 res = SZ_ERROR_PROGRESS;
\r
2251 LzmaEnc_Finish(p);
\r
2254 if (res == S_OK && !Inline_MatchFinder_IsFinishedOK(&p->matchFinderBase))
\r
2255 res = SZ_ERROR_FAIL;
\r
2263 SRes LzmaEnc_Encode(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream, ICompressProgress *progress,
\r
2264 ISzAlloc *alloc, ISzAlloc *allocBig)
\r
2266 RINOK(LzmaEnc_Prepare(pp, outStream, inStream, alloc, allocBig));
\r
2267 return LzmaEnc_Encode2((CLzmaEnc *)pp, progress);
\r
2271 SRes LzmaEnc_WriteProperties(CLzmaEncHandle pp, Byte *props, SizeT *size)
\r
2273 CLzmaEnc *p = (CLzmaEnc *)pp;
\r
2275 UInt32 dictSize = p->dictSize;
\r
2276 if (*size < LZMA_PROPS_SIZE)
\r
2277 return SZ_ERROR_PARAM;
\r
2278 *size = LZMA_PROPS_SIZE;
\r
2279 props[0] = (Byte)((p->pb * 5 + p->lp) * 9 + p->lc);
\r
2281 if (dictSize >= ((UInt32)1 << 22))
\r
2283 UInt32 kDictMask = ((UInt32)1 << 20) - 1;
\r
2284 if (dictSize < (UInt32)0xFFFFFFFF - kDictMask)
\r
2285 dictSize = (dictSize + kDictMask) & ~kDictMask;
\r
2287 else for (i = 11; i <= 30; i++)
\r
2289 if (dictSize <= ((UInt32)2 << i)) { dictSize = (2 << i); break; }
\r
2290 if (dictSize <= ((UInt32)3 << i)) { dictSize = (3 << i); break; }
\r
2293 for (i = 0; i < 4; i++)
\r
2294 props[1 + i] = (Byte)(dictSize >> (8 * i));
\r
2299 SRes LzmaEnc_MemEncode(CLzmaEncHandle pp, Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
\r
2300 int writeEndMark, ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig)
\r
2303 CLzmaEnc *p = (CLzmaEnc *)pp;
\r
2305 CSeqOutStreamBuf outStream;
\r
2307 outStream.funcTable.Write = MyWrite;
\r
2308 outStream.data = dest;
\r
2309 outStream.rem = *destLen;
\r
2310 outStream.overflow = False;
\r
2312 p->writeEndMark = writeEndMark;
\r
2313 p->rc.outStream = &outStream.funcTable;
\r
2315 res = LzmaEnc_MemPrepare(pp, src, srcLen, 0, alloc, allocBig);
\r
2319 res = LzmaEnc_Encode2(p, progress);
\r
2320 if (res == SZ_OK && p->nowPos64 != srcLen)
\r
2321 res = SZ_ERROR_FAIL;
\r
2324 *destLen -= outStream.rem;
\r
2325 if (outStream.overflow)
\r
2326 return SZ_ERROR_OUTPUT_EOF;
\r
2331 SRes LzmaEncode(Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
\r
2332 const CLzmaEncProps *props, Byte *propsEncoded, SizeT *propsSize, int writeEndMark,
\r
2333 ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig)
\r
2335 CLzmaEnc *p = (CLzmaEnc *)LzmaEnc_Create(alloc);
\r
2338 return SZ_ERROR_MEM;
\r
2340 res = LzmaEnc_SetProps(p, props);
\r
2343 res = LzmaEnc_WriteProperties(p, propsEncoded, propsSize);
\r
2345 res = LzmaEnc_MemEncode(p, dest, destLen, src, srcLen,
\r
2346 writeEndMark, progress, alloc, allocBig);
\r
2349 LzmaEnc_Destroy(p, alloc, allocBig);
\r