1 /* LzmaEnc.c -- LZMA Encoder
2 2019-01-10: Igor Pavlov : Public domain */
8 /* #define SHOW_STAT */
9 /* #define SHOW_STAT2 */
11 #if defined(SHOW_STAT) || defined(SHOW_STAT2)
23 static unsigned g_STAT_OFFSET = 0;
26 #define kLzmaMaxHistorySize ((UInt32)3 << 29)
27 /* #define kLzmaMaxHistorySize ((UInt32)7 << 29) */
29 #define kNumTopBits 24
30 #define kTopValue ((UInt32)1 << kNumTopBits)
32 #define kNumBitModelTotalBits 11
33 #define kBitModelTotal (1 << kNumBitModelTotalBits)
34 #define kNumMoveBits 5
35 #define kProbInitValue (kBitModelTotal >> 1)
37 #define kNumMoveReducingBits 4
38 #define kNumBitPriceShiftBits 4
39 #define kBitPrice (1 << kNumBitPriceShiftBits)
41 #define REP_LEN_COUNT 64
43 void LzmaEncProps_Init(CLzmaEncProps *p)
46 p->dictSize = p->mc = 0;
47 p->reduceSize = (UInt64)(Int64)-1;
48 p->lc = p->lp = p->pb = p->algo = p->fb = p->btMode = p->numHashBytes = p->numThreads = -1;
52 void LzmaEncProps_Normalize(CLzmaEncProps *p)
55 if (level < 0) level = 5;
58 if (p->dictSize == 0) p->dictSize = (level <= 5 ? (1 << (level * 2 + 14)) : (level <= 7 ? (1 << 25) : (1 << 26)));
59 if (p->dictSize > p->reduceSize)
62 UInt32 reduceSize = (UInt32)p->reduceSize;
63 for (i = 11; i <= 30; i++)
65 if (reduceSize <= ((UInt32)2 << i)) { p->dictSize = ((UInt32)2 << i); break; }
66 if (reduceSize <= ((UInt32)3 << i)) { p->dictSize = ((UInt32)3 << i); break; }
70 if (p->lc < 0) p->lc = 3;
71 if (p->lp < 0) p->lp = 0;
72 if (p->pb < 0) p->pb = 2;
74 if (p->algo < 0) p->algo = (level < 5 ? 0 : 1);
75 if (p->fb < 0) p->fb = (level < 7 ? 32 : 64);
76 if (p->btMode < 0) p->btMode = (p->algo == 0 ? 0 : 1);
77 if (p->numHashBytes < 0) p->numHashBytes = 4;
78 if (p->mc == 0) p->mc = (16 + (p->fb >> 1)) >> (p->btMode ? 0 : 1);
80 if (p->numThreads < 0)
83 ((p->btMode && p->algo) ? 2 : 1);
89 UInt32 LzmaEncProps_GetDictSize(const CLzmaEncProps *props2)
91 CLzmaEncProps props = *props2;
92 LzmaEncProps_Normalize(&props);
93 return props.dictSize;
96 #if (_MSC_VER >= 1400)
97 /* BSR code is fast for some new CPUs */
98 /* #define LZMA_LOG_BSR */
103 #define kDicLogSizeMaxCompress 32
105 #define BSR2_RET(pos, res) { unsigned long zz; _BitScanReverse(&zz, (pos)); res = (zz + zz) + ((pos >> (zz - 1)) & 1); }
107 static unsigned GetPosSlot1(UInt32 pos)
113 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }
114 #define GetPosSlot(pos, res) { if (pos < 2) res = pos; else BSR2_RET(pos, res); }
118 #define kNumLogBits (9 + sizeof(size_t) / 2)
119 /* #define kNumLogBits (11 + sizeof(size_t) / 8 * 3) */
121 #define kDicLogSizeMaxCompress ((kNumLogBits - 1) * 2 + 7)
123 static void LzmaEnc_FastPosInit(Byte *g_FastPos)
130 for (slot = 2; slot < kNumLogBits * 2; slot++)
132 size_t k = ((size_t)1 << ((slot >> 1) - 1));
134 for (j = 0; j < k; j++)
135 g_FastPos[j] = (Byte)slot;
140 /* we can use ((limit - pos) >> 31) only if (pos < ((UInt32)1 << 31)) */
142 #define BSR2_RET(pos, res) { unsigned zz = 6 + ((kNumLogBits - 1) & \
143 (0 - (((((UInt32)1 << (kNumLogBits + 6)) - 1) - pos) >> 31))); \
144 res = p->g_FastPos[pos >> zz] + (zz * 2); }
148 #define BSR2_RET(pos, res) { unsigned zz = 6 + ((kNumLogBits - 1) & \
149 (0 - (((((UInt32)1 << (kNumLogBits)) - 1) - (pos >> 6)) >> 31))); \
150 res = p->g_FastPos[pos >> zz] + (zz * 2); }
153 #define BSR2_RET(pos, res) { unsigned zz = (pos < (1 << (kNumLogBits + 6))) ? 6 : 6 + kNumLogBits - 1; \
154 res = p->g_FastPos[pos >> zz] + (zz * 2); }
157 #define BSR2_RET(pos, res) { res = (pos < (1 << (kNumLogBits + 6))) ? \
158 p->g_FastPos[pos >> 6] + 12 : \
159 p->g_FastPos[pos >> (6 + kNumLogBits - 1)] + (6 + (kNumLogBits - 1)) * 2; }
162 #define GetPosSlot1(pos) p->g_FastPos[pos]
163 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }
164 #define GetPosSlot(pos, res) { if (pos < kNumFullDistances) res = p->g_FastPos[pos & (kNumFullDistances - 1)]; else BSR2_RET(pos, res); }
169 #define LZMA_NUM_REPS 4
171 typedef UInt16 CState;
172 typedef UInt16 CExtra;
181 // > 1 : MATCH (extra-1) : LIT : REP0 (len)
184 UInt32 reps[LZMA_NUM_REPS];
189 #define kNumOpts (1 << 11)
190 #define kPackReserve (kNumOpts * 8)
191 // #define kNumOpts (1 << 12)
192 // #define kPackReserve (1 + kNumOpts * 2)
194 #define kNumLenToPosStates 4
195 #define kNumPosSlotBits 6
196 #define kDicLogSizeMin 0
197 #define kDicLogSizeMax 32
198 #define kDistTableSizeMax (kDicLogSizeMax * 2)
200 #define kNumAlignBits 4
201 #define kAlignTableSize (1 << kNumAlignBits)
202 #define kAlignMask (kAlignTableSize - 1)
204 #define kStartPosModelIndex 4
205 #define kEndPosModelIndex 14
206 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
216 #define LZMA_PB_MAX 4
217 #define LZMA_LC_MAX 8
218 #define LZMA_LP_MAX 4
220 #define LZMA_NUM_PB_STATES_MAX (1 << LZMA_PB_MAX)
222 #define kLenNumLowBits 3
223 #define kLenNumLowSymbols (1 << kLenNumLowBits)
224 #define kLenNumHighBits 8
225 #define kLenNumHighSymbols (1 << kLenNumHighBits)
226 #define kLenNumSymbolsTotal (kLenNumLowSymbols * 2 + kLenNumHighSymbols)
228 #define LZMA_MATCH_LEN_MIN 2
229 #define LZMA_MATCH_LEN_MAX (LZMA_MATCH_LEN_MIN + kLenNumSymbolsTotal - 1)
231 #define kNumStates 12
236 CLzmaProb low[LZMA_NUM_PB_STATES_MAX << (kLenNumLowBits + 1)];
237 CLzmaProb high[kLenNumHighSymbols];
244 UInt32 prices[LZMA_NUM_PB_STATES_MAX][kLenNumSymbolsTotal];
245 // UInt32 prices1[LZMA_NUM_PB_STATES_MAX][kLenNumLowSymbols * 2];
246 // UInt32 prices2[kLenNumSymbolsTotal];
249 #define GET_PRICE_LEN(p, posState, len) \
250 ((p)->prices[posState][(size_t)(len) - LZMA_MATCH_LEN_MIN])
253 #define GET_PRICE_LEN(p, posState, len) \
254 ((p)->prices2[(size_t)(len) - 2] + ((p)->prices1[posState][((len) - 2) & (kLenNumLowSymbols * 2 - 1)] & (((len) - 2 - kLenNumLowSymbols * 2) >> 9)))
266 ISeqOutStream *outStream;
277 UInt32 reps[LZMA_NUM_REPS];
279 CLzmaProb posAlignEncoder[1 << kNumAlignBits];
280 CLzmaProb isRep[kNumStates];
281 CLzmaProb isRepG0[kNumStates];
282 CLzmaProb isRepG1[kNumStates];
283 CLzmaProb isRepG2[kNumStates];
284 CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];
285 CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];
287 CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];
288 CLzmaProb posEncoders[kNumFullDistances];
296 typedef UInt32 CProbPrice;
301 void *matchFinderObj;
302 IMatchFinder matchFinder;
307 unsigned longestMatchLen;
312 unsigned numFastBytes;
313 unsigned additionalOffset;
314 UInt32 reps[LZMA_NUM_REPS];
315 unsigned lpMask, pbMask;
325 BoolInt writeEndMark;
333 unsigned matchPriceCount;
334 // unsigned alignPriceCount;
335 int repLenEncCounter;
337 unsigned distTableSize;
344 // begin of CMatchFinderMt is used in LZ thread
345 CMatchFinderMt matchFinderMt;
346 // end of CMatchFinderMt is used in BT and HASH threads
349 CMatchFinder matchFinderBase;
356 CProbPrice ProbPrices[kBitModelTotal >> kNumMoveReducingBits];
358 UInt32 matches[LZMA_MATCH_LEN_MAX * 2 + 2 + 1];
360 UInt32 alignPrices[kAlignTableSize];
361 UInt32 posSlotPrices[kNumLenToPosStates][kDistTableSizeMax];
362 UInt32 distancesPrices[kNumLenToPosStates][kNumFullDistances];
364 CLzmaProb posAlignEncoder[1 << kNumAlignBits];
365 CLzmaProb isRep[kNumStates];
366 CLzmaProb isRepG0[kNumStates];
367 CLzmaProb isRepG1[kNumStates];
368 CLzmaProb isRepG2[kNumStates];
369 CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];
370 CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];
371 CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];
372 CLzmaProb posEncoders[kNumFullDistances];
378 Byte g_FastPos[1 << kNumLogBits];
382 CLenPriceEnc repLenEnc;
384 COptimal opt[kNumOpts];
386 CSaveState saveState;
394 SRes LzmaEnc_SetProps(CLzmaEncHandle pp, const CLzmaEncProps *props2)
396 CLzmaEnc *p = (CLzmaEnc *)pp;
397 CLzmaEncProps props = *props2;
398 LzmaEncProps_Normalize(&props);
400 if (props.lc > LZMA_LC_MAX
401 || props.lp > LZMA_LP_MAX
402 || props.pb > LZMA_PB_MAX
403 || props.dictSize > ((UInt64)1 << kDicLogSizeMaxCompress)
404 || props.dictSize > kLzmaMaxHistorySize)
405 return SZ_ERROR_PARAM;
407 p->dictSize = props.dictSize;
409 unsigned fb = props.fb;
412 if (fb > LZMA_MATCH_LEN_MAX)
413 fb = LZMA_MATCH_LEN_MAX;
414 p->numFastBytes = fb;
419 p->fastMode = (props.algo == 0);
420 // p->_maxMode = True;
421 p->matchFinderBase.btMode = (Byte)(props.btMode ? 1 : 0);
423 unsigned numHashBytes = 4;
426 if (props.numHashBytes < 2)
428 else if (props.numHashBytes < 4)
429 numHashBytes = props.numHashBytes;
431 p->matchFinderBase.numHashBytes = numHashBytes;
434 p->matchFinderBase.cutValue = props.mc;
436 p->writeEndMark = props.writeEndMark;
440 if (newMultiThread != _multiThread)
442 ReleaseMatchFinder();
443 _multiThread = newMultiThread;
446 p->multiThread = (props.numThreads > 1);
453 void LzmaEnc_SetDataSize(CLzmaEncHandle pp, UInt64 expectedDataSiize)
455 CLzmaEnc *p = (CLzmaEnc *)pp;
456 p->matchFinderBase.expectedDataSize = expectedDataSiize;
460 #define kState_Start 0
461 #define kState_LitAfterMatch 4
462 #define kState_LitAfterRep 5
463 #define kState_MatchAfterLit 7
464 #define kState_RepAfterLit 8
466 static const Byte kLiteralNextStates[kNumStates] = {0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5};
467 static const Byte kMatchNextStates[kNumStates] = {7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10};
468 static const Byte kRepNextStates[kNumStates] = {8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11};
469 static const Byte kShortRepNextStates[kNumStates]= {9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11};
471 #define IsLitState(s) ((s) < 7)
472 #define GetLenToPosState2(len) (((len) < kNumLenToPosStates - 1) ? (len) : kNumLenToPosStates - 1)
473 #define GetLenToPosState(len) (((len) < kNumLenToPosStates + 1) ? (len) - 2 : kNumLenToPosStates - 1)
475 #define kInfinityPrice (1 << 30)
477 static void RangeEnc_Construct(CRangeEnc *p)
483 #define RangeEnc_GetProcessed(p) ((p)->processed + ((p)->buf - (p)->bufBase) + (p)->cacheSize)
484 #define RangeEnc_GetProcessed_sizet(p) ((size_t)(p)->processed + ((p)->buf - (p)->bufBase) + (size_t)(p)->cacheSize)
486 #define RC_BUF_SIZE (1 << 16)
488 static int RangeEnc_Alloc(CRangeEnc *p, ISzAllocPtr alloc)
492 p->bufBase = (Byte *)ISzAlloc_Alloc(alloc, RC_BUF_SIZE);
495 p->bufLim = p->bufBase + RC_BUF_SIZE;
500 static void RangeEnc_Free(CRangeEnc *p, ISzAllocPtr alloc)
502 ISzAlloc_Free(alloc, p->bufBase);
506 static void RangeEnc_Init(CRangeEnc *p)
509 p->range = 0xFFFFFFFF;
520 MY_NO_INLINE static void RangeEnc_FlushStream(CRangeEnc *p)
525 num = p->buf - p->bufBase;
526 if (num != ISeqOutStream_Write(p->outStream, p->bufBase, num))
527 p->res = SZ_ERROR_WRITE;
532 MY_NO_INLINE static void MY_FAST_CALL RangeEnc_ShiftLow(CRangeEnc *p)
534 UInt32 low = (UInt32)p->low;
535 unsigned high = (unsigned)(p->low >> 32);
536 p->low = (UInt32)(low << 8);
537 if (low < (UInt32)0xFF000000 || high != 0)
541 *buf++ = (Byte)(p->cache + high);
542 p->cache = (unsigned)(low >> 24);
544 if (buf == p->bufLim)
545 RangeEnc_FlushStream(p);
546 if (p->cacheSize == 0)
553 *buf++ = (Byte)(high);
555 if (buf == p->bufLim)
556 RangeEnc_FlushStream(p);
557 if (--p->cacheSize == 0)
564 static void RangeEnc_FlushData(CRangeEnc *p)
567 for (i = 0; i < 5; i++)
568 RangeEnc_ShiftLow(p);
571 #define RC_NORM(p) if (range < kTopValue) { range <<= 8; RangeEnc_ShiftLow(p); }
573 #define RC_BIT_PRE(p, prob) \
575 newBound = (range >> kNumBitModelTotalBits) * ttt;
577 // #define _LZMA_ENC_USE_BRANCH
579 #ifdef _LZMA_ENC_USE_BRANCH
581 #define RC_BIT(p, prob, bit) { \
582 RC_BIT_PRE(p, prob) \
583 if (bit == 0) { range = newBound; ttt += (kBitModelTotal - ttt) >> kNumMoveBits; } \
584 else { (p)->low += newBound; range -= newBound; ttt -= ttt >> kNumMoveBits; } \
585 *(prob) = (CLzmaProb)ttt; \
591 #define RC_BIT(p, prob, bit) { \
593 RC_BIT_PRE(p, prob) \
594 mask = 0 - (UInt32)bit; \
599 mask = (UInt32)bit - 1; \
600 range += newBound & mask; \
601 mask &= (kBitModelTotal - ((1 << kNumMoveBits) - 1)); \
602 mask += ((1 << kNumMoveBits) - 1); \
603 ttt += (Int32)(mask - ttt) >> kNumMoveBits; \
604 *(prob) = (CLzmaProb)ttt; \
613 #define RC_BIT_0_BASE(p, prob) \
614 range = newBound; *(prob) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits));
616 #define RC_BIT_1_BASE(p, prob) \
617 range -= newBound; (p)->low += newBound; *(prob) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits)); \
619 #define RC_BIT_0(p, prob) \
620 RC_BIT_0_BASE(p, prob) \
623 #define RC_BIT_1(p, prob) \
624 RC_BIT_1_BASE(p, prob) \
627 static void RangeEnc_EncodeBit_0(CRangeEnc *p, CLzmaProb *prob)
629 UInt32 range, ttt, newBound;
636 static void LitEnc_Encode(CRangeEnc *p, CLzmaProb *probs, UInt32 sym)
638 UInt32 range = p->range;
642 UInt32 ttt, newBound;
643 // RangeEnc_EncodeBit(p, probs + (sym >> 8), (sym >> 7) & 1);
644 CLzmaProb *prob = probs + (sym >> 8);
645 UInt32 bit = (sym >> 7) & 1;
647 RC_BIT(p, prob, bit);
649 while (sym < 0x10000);
653 static void LzmaEnc_InitPriceTables(CProbPrice *ProbPrices)
656 for (i = 0; i < (kBitModelTotal >> kNumMoveReducingBits); i++)
658 const unsigned kCyclesBits = kNumBitPriceShiftBits;
659 UInt32 w = (i << kNumMoveReducingBits) + (1 << (kNumMoveReducingBits - 1));
660 unsigned bitCount = 0;
662 for (j = 0; j < kCyclesBits; j++)
666 while (w >= ((UInt32)1 << 16))
672 ProbPrices[i] = (CProbPrice)((kNumBitModelTotalBits << kCyclesBits) - 15 - bitCount);
673 // printf("\n%3d: %5d", i, ProbPrices[i]);
678 #define GET_PRICE(prob, bit) \
679 p->ProbPrices[((prob) ^ (unsigned)(((-(int)(bit))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];
681 #define GET_PRICEa(prob, bit) \
682 ProbPrices[((prob) ^ (unsigned)((-((int)(bit))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];
684 #define GET_PRICE_0(prob) p->ProbPrices[(prob) >> kNumMoveReducingBits]
685 #define GET_PRICE_1(prob) p->ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]
687 #define GET_PRICEa_0(prob) ProbPrices[(prob) >> kNumMoveReducingBits]
688 #define GET_PRICEa_1(prob) ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]
691 static UInt32 LitEnc_GetPrice(const CLzmaProb *probs, UInt32 sym, const CProbPrice *ProbPrices)
697 unsigned bit = sym & 1;
699 price += GET_PRICEa(probs[sym], bit);
706 static UInt32 LitEnc_Matched_GetPrice(const CLzmaProb *probs, UInt32 sym, UInt32 matchByte, const CProbPrice *ProbPrices)
714 price += GET_PRICEa(probs[offs + (matchByte & offs) + (sym >> 8)], (sym >> 7) & 1);
716 offs &= ~(matchByte ^ sym);
718 while (sym < 0x10000);
724 static void LenEnc_Init(CLenEnc *p)
727 for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << (kLenNumLowBits + 1)); i++)
728 p->low[i] = kProbInitValue;
729 for (i = 0; i < kLenNumHighSymbols; i++)
730 p->high[i] = kProbInitValue;
733 static void LenEnc_Encode(CLenEnc *p, CRangeEnc *rc, unsigned sym, unsigned posState)
735 UInt32 range, ttt, newBound;
736 CLzmaProb *probs = p->low;
738 RC_BIT_PRE(rc, probs);
739 if (sym >= kLenNumLowSymbols)
742 probs += kLenNumLowSymbols;
743 RC_BIT_PRE(rc, probs);
744 if (sym >= kLenNumLowSymbols * 2)
748 // RcTree_Encode(rc, p->high, kLenNumHighBits, sym - kLenNumLowSymbols * 2);
749 LitEnc_Encode(rc, p->high, sym - kLenNumLowSymbols * 2);
752 sym -= kLenNumLowSymbols;
755 // RcTree_Encode(rc, probs + (posState << kLenNumLowBits), kLenNumLowBits, sym);
760 probs += (posState << (1 + kLenNumLowBits));
761 bit = (sym >> 2) ; RC_BIT(rc, probs + 1, bit); m = (1 << 1) + bit;
762 bit = (sym >> 1) & 1; RC_BIT(rc, probs + m, bit); m = (m << 1) + bit;
763 bit = sym & 1; RC_BIT(rc, probs + m, bit);
768 static void SetPrices_3(const CLzmaProb *probs, UInt32 startPrice, UInt32 *prices, const CProbPrice *ProbPrices)
771 for (i = 0; i < 8; i += 2)
773 UInt32 price = startPrice;
775 price += GET_PRICEa(probs[1 ], (i >> 2));
776 price += GET_PRICEa(probs[2 + (i >> 2)], (i >> 1) & 1);
777 prob = probs[4 + (i >> 1)];
778 prices[i ] = price + GET_PRICEa_0(prob);
779 prices[i + 1] = price + GET_PRICEa_1(prob);
784 MY_NO_INLINE static void MY_FAST_CALL LenPriceEnc_UpdateTables(
786 unsigned numPosStates,
788 const CProbPrice *ProbPrices)
793 unsigned prob = enc->low[0];
796 b = GET_PRICEa_1(prob);
797 a = GET_PRICEa_0(prob);
798 c = b + GET_PRICEa_0(enc->low[kLenNumLowSymbols]);
799 for (posState = 0; posState < numPosStates; posState++)
801 UInt32 *prices = p->prices[posState];
802 const CLzmaProb *probs = enc->low + (posState << (1 + kLenNumLowBits));
803 SetPrices_3(probs, a, prices, ProbPrices);
804 SetPrices_3(probs + kLenNumLowSymbols, c, prices + kLenNumLowSymbols, ProbPrices);
812 a = GET_PRICEa_0(enc->low[0]);
813 for (i = 0; i < kLenNumLowSymbols; i++)
815 a = GET_PRICEa_1(enc->low[0]);
816 b = a + GET_PRICEa_0(enc->low[kLenNumLowSymbols]);
817 for (i = kLenNumLowSymbols; i < kLenNumLowSymbols * 2; i++)
819 a += GET_PRICEa_1(enc->low[kLenNumLowSymbols]);
823 // p->counter = numSymbols;
827 unsigned i = p->tableSize;
829 if (i > kLenNumLowSymbols * 2)
831 const CLzmaProb *probs = enc->high;
832 UInt32 *prices = p->prices[0] + kLenNumLowSymbols * 2;
833 i -= kLenNumLowSymbols * 2 - 1;
835 b += GET_PRICEa_1(enc->low[kLenNumLowSymbols]);
840 // RcTree_GetPrice(enc->high, kLenNumHighBits, i - kLenNumLowSymbols * 2, ProbPrices);
841 LitEnc_GetPrice(probs, i - kLenNumLowSymbols * 2, ProbPrices);
843 // UInt32 price = a + RcTree_GetPrice(probs, kLenNumHighBits - 1, sym, ProbPrices);
844 unsigned sym = --i + (1 << (kLenNumHighBits - 1));
848 unsigned bit = sym & 1;
850 price += GET_PRICEa(probs[sym], bit);
855 unsigned prob = probs[(size_t)i + (1 << (kLenNumHighBits - 1))];
856 prices[(size_t)i * 2 ] = price + GET_PRICEa_0(prob);
857 prices[(size_t)i * 2 + 1] = price + GET_PRICEa_1(prob);
864 size_t num = (p->tableSize - kLenNumLowSymbols * 2) * sizeof(p->prices[0][0]);
865 for (posState = 1; posState < numPosStates; posState++)
866 memcpy(p->prices[posState] + kLenNumLowSymbols * 2, p->prices[0] + kLenNumLowSymbols * 2, num);
874 g_STAT_OFFSET += num;
875 printf("\n MovePos %u", num);
879 #define MOVE_POS(p, num) { \
880 p->additionalOffset += (num); \
881 p->matchFinder.Skip(p->matchFinderObj, (UInt32)(num)); }
884 #define MARK_LIT ((UInt32)(Int32)-1)
886 #define MakeAs_Lit(p) { (p)->dist = MARK_LIT; (p)->extra = 0; }
887 #define MakeAs_ShortRep(p) { (p)->dist = 0; (p)->extra = 0; }
888 #define IsShortRep(p) ((p)->dist == 0)
891 #define GetPrice_ShortRep(p, state, posState) \
892 ( GET_PRICE_0(p->isRepG0[state]) + GET_PRICE_0(p->isRep0Long[state][posState]))
894 #define GetPrice_Rep_0(p, state, posState) ( \
895 GET_PRICE_1(p->isMatch[state][posState]) \
896 + GET_PRICE_1(p->isRep0Long[state][posState])) \
897 + GET_PRICE_1(p->isRep[state]) \
898 + GET_PRICE_0(p->isRepG0[state])
901 static UInt32 GetPrice_PureRep(const CLzmaEnc *p, unsigned repIndex, size_t state, size_t posState)
904 UInt32 prob = p->isRepG0[state];
907 price = GET_PRICE_0(prob);
908 price += GET_PRICE_1(p->isRep0Long[state][posState]);
912 price = GET_PRICE_1(prob);
913 prob = p->isRepG1[state];
915 price += GET_PRICE_0(prob);
918 price += GET_PRICE_1(prob);
919 price += GET_PRICE(p->isRepG2[state], repIndex - 2);
926 static SRes CheckErrors(CLzmaEnc *p)
928 if (p->result != SZ_OK)
930 if (p->rc.res != SZ_OK)
931 p->result = SZ_ERROR_WRITE;
932 if (p->matchFinderBase.result != SZ_OK)
933 p->result = SZ_ERROR_READ;
934 if (p->result != SZ_OK)
940 MY_NO_INLINE static void FillAlignPrices(CLzmaEnc *p)
943 const CProbPrice *ProbPrices = p->ProbPrices;
944 const CLzmaProb *probs = p->posAlignEncoder;
945 // p->alignPriceCount = 0;
946 for (i = 0; i < kAlignTableSize / 2; i++)
953 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[m], bit); m = (m << 1) + bit;
954 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[m], bit); m = (m << 1) + bit;
955 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[m], bit); m = (m << 1) + bit;
957 p->alignPrices[i ] = price + GET_PRICEa_0(prob);
958 p->alignPrices[i + 8] = price + GET_PRICEa_1(prob);
959 // p->alignPrices[i] = RcTree_ReverseGetPrice(p->posAlignEncoder, kNumAlignBits, i, p->ProbPrices);
964 MY_NO_INLINE static void FillDistancesPrices(CLzmaEnc *p)
966 // int y; for (y = 0; y < 100; y++) {
968 UInt32 tempPrices[kNumFullDistances];
971 const CProbPrice *ProbPrices = p->ProbPrices;
972 p->matchPriceCount = 0;
974 for (i = kStartPosModelIndex / 2; i < kNumFullDistances / 2; i++)
976 unsigned posSlot = GetPosSlot1(i);
977 unsigned footerBits = (posSlot >> 1) - 1;
978 unsigned base = ((2 | (posSlot & 1)) << footerBits);
979 const CLzmaProb *probs = p->posEncoders + (size_t)base * 2;
980 // tempPrices[i] = RcTree_ReverseGetPrice(p->posEncoders + base, footerBits, i - base, p->ProbPrices);
984 unsigned offset = (unsigned)1 << footerBits;
990 unsigned bit = sym & 1;
992 price += GET_PRICEa(probs[m], bit);
995 while (--footerBits);
998 unsigned prob = probs[m];
999 tempPrices[base ] = price + GET_PRICEa_0(prob);
1000 tempPrices[base + offset] = price + GET_PRICEa_1(prob);
1004 for (lps = 0; lps < kNumLenToPosStates; lps++)
1007 unsigned distTableSize2 = (p->distTableSize + 1) >> 1;
1008 UInt32 *posSlotPrices = p->posSlotPrices[lps];
1009 const CLzmaProb *probs = p->posSlotEncoder[lps];
1011 for (slot = 0; slot < distTableSize2; slot++)
1013 // posSlotPrices[slot] = RcTree_GetPrice(encoder, kNumPosSlotBits, slot, p->ProbPrices);
1016 unsigned sym = slot + (1 << (kNumPosSlotBits - 1));
1018 bit = sym & 1; sym >>= 1; price = GET_PRICEa(probs[sym], bit);
1019 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[sym], bit);
1020 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[sym], bit);
1021 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[sym], bit);
1022 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[sym], bit);
1023 prob = probs[(size_t)slot + (1 << (kNumPosSlotBits - 1))];
1024 posSlotPrices[(size_t)slot * 2 ] = price + GET_PRICEa_0(prob);
1025 posSlotPrices[(size_t)slot * 2 + 1] = price + GET_PRICEa_1(prob);
1029 UInt32 delta = ((UInt32)((kEndPosModelIndex / 2 - 1) - kNumAlignBits) << kNumBitPriceShiftBits);
1030 for (slot = kEndPosModelIndex / 2; slot < distTableSize2; slot++)
1032 posSlotPrices[(size_t)slot * 2 ] += delta;
1033 posSlotPrices[(size_t)slot * 2 + 1] += delta;
1034 delta += ((UInt32)1 << kNumBitPriceShiftBits);
1039 UInt32 *dp = p->distancesPrices[lps];
1041 dp[0] = posSlotPrices[0];
1042 dp[1] = posSlotPrices[1];
1043 dp[2] = posSlotPrices[2];
1044 dp[3] = posSlotPrices[3];
1046 for (i = 4; i < kNumFullDistances; i += 2)
1048 UInt32 slotPrice = posSlotPrices[GetPosSlot1(i)];
1049 dp[i ] = slotPrice + tempPrices[i];
1050 dp[i + 1] = slotPrice + tempPrices[i + 1];
1059 void LzmaEnc_Construct(CLzmaEnc *p)
1061 RangeEnc_Construct(&p->rc);
1062 MatchFinder_Construct(&p->matchFinderBase);
1065 MatchFinderMt_Construct(&p->matchFinderMt);
1066 p->matchFinderMt.MatchFinder = &p->matchFinderBase;
1070 CLzmaEncProps props;
1071 LzmaEncProps_Init(&props);
1072 LzmaEnc_SetProps(p, &props);
1075 #ifndef LZMA_LOG_BSR
1076 LzmaEnc_FastPosInit(p->g_FastPos);
1079 LzmaEnc_InitPriceTables(p->ProbPrices);
1081 p->saveState.litProbs = NULL;
1085 CLzmaEncHandle LzmaEnc_Create(ISzAllocPtr alloc)
1088 p = ISzAlloc_Alloc(alloc, sizeof(CLzmaEnc));
1090 LzmaEnc_Construct((CLzmaEnc *)p);
1094 void LzmaEnc_FreeLits(CLzmaEnc *p, ISzAllocPtr alloc)
1096 ISzAlloc_Free(alloc, p->litProbs);
1097 ISzAlloc_Free(alloc, p->saveState.litProbs);
1099 p->saveState.litProbs = NULL;
1102 void LzmaEnc_Destruct(CLzmaEnc *p, ISzAllocPtr alloc, ISzAllocPtr allocBig)
1105 MatchFinderMt_Destruct(&p->matchFinderMt, allocBig);
1108 MatchFinder_Free(&p->matchFinderBase, allocBig);
1109 LzmaEnc_FreeLits(p, alloc);
1110 RangeEnc_Free(&p->rc, alloc);
1113 void LzmaEnc_Destroy(CLzmaEncHandle p, ISzAllocPtr alloc, ISzAllocPtr allocBig)
1115 LzmaEnc_Destruct((CLzmaEnc *)p, alloc, allocBig);
1116 ISzAlloc_Free(alloc, p);
1120 #define kBigHashDicLimit ((UInt32)1 << 24)
1122 static SRes LzmaEnc_Alloc(CLzmaEnc *p, UInt32 keepWindowSize, ISzAllocPtr alloc, ISzAllocPtr allocBig)
1124 UInt32 beforeSize = kNumOpts;
1125 if (!RangeEnc_Alloc(&p->rc, alloc))
1126 return SZ_ERROR_MEM;
1129 p->mtMode = (p->multiThread && !p->fastMode && (p->matchFinderBase.btMode != 0));
1133 unsigned lclp = p->lc + p->lp;
1134 if (!p->litProbs || !p->saveState.litProbs || p->lclp != lclp)
1136 LzmaEnc_FreeLits(p, alloc);
1137 p->litProbs = (CLzmaProb *)ISzAlloc_Alloc(alloc, ((UInt32)0x300 << lclp) * sizeof(CLzmaProb));
1138 p->saveState.litProbs = (CLzmaProb *)ISzAlloc_Alloc(alloc, ((UInt32)0x300 << lclp) * sizeof(CLzmaProb));
1139 if (!p->litProbs || !p->saveState.litProbs)
1141 LzmaEnc_FreeLits(p, alloc);
1142 return SZ_ERROR_MEM;
1148 p->matchFinderBase.bigHash = (Byte)(p->dictSize > kBigHashDicLimit ? 1 : 0);
1150 if (beforeSize + p->dictSize < keepWindowSize)
1151 beforeSize = keepWindowSize - p->dictSize;
1156 RINOK(MatchFinderMt_Create(&p->matchFinderMt, p->dictSize, beforeSize, p->numFastBytes,
1160 p->matchFinderObj = &p->matchFinderMt;
1161 p->matchFinderBase.bigHash = (Byte)(
1162 (p->dictSize > kBigHashDicLimit && p->matchFinderBase.hashMask >= 0xFFFFFF) ? 1 : 0);
1163 MatchFinderMt_CreateVTable(&p->matchFinderMt, &p->matchFinder);
1168 if (!MatchFinder_Create(&p->matchFinderBase, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig))
1169 return SZ_ERROR_MEM;
1170 p->matchFinderObj = &p->matchFinderBase;
1171 MatchFinder_CreateVTable(&p->matchFinderBase, &p->matchFinder);
1177 void LzmaEnc_Init(CLzmaEnc *p)
1186 RangeEnc_Init(&p->rc);
1188 for (i = 0; i < (1 << kNumAlignBits); i++)
1189 p->posAlignEncoder[i] = kProbInitValue;
1191 for (i = 0; i < kNumStates; i++)
1194 for (j = 0; j < LZMA_NUM_PB_STATES_MAX; j++)
1196 p->isMatch[i][j] = kProbInitValue;
1197 p->isRep0Long[i][j] = kProbInitValue;
1199 p->isRep[i] = kProbInitValue;
1200 p->isRepG0[i] = kProbInitValue;
1201 p->isRepG1[i] = kProbInitValue;
1202 p->isRepG2[i] = kProbInitValue;
1206 for (i = 0; i < kNumLenToPosStates; i++)
1208 CLzmaProb *probs = p->posSlotEncoder[i];
1210 for (j = 0; j < (1 << kNumPosSlotBits); j++)
1211 probs[j] = kProbInitValue;
1215 for (i = 0; i < kNumFullDistances; i++)
1216 p->posEncoders[i] = kProbInitValue;
1220 UInt32 num = (UInt32)0x300 << (p->lp + p->lc);
1222 CLzmaProb *probs = p->litProbs;
1223 for (k = 0; k < num; k++)
1224 probs[k] = kProbInitValue;
1228 LenEnc_Init(&p->lenProbs);
1229 LenEnc_Init(&p->repLenProbs);
1235 for (i = 0; i < kNumOpts; i++)
1236 p->opt[i].price = kInfinityPrice;
1239 p->additionalOffset = 0;
1241 p->pbMask = (1 << p->pb) - 1;
1242 p->lpMask = ((UInt32)0x100 << p->lp) - ((unsigned)0x100 >> p->lc);
1246 void LzmaEnc_InitPrices(CLzmaEnc *p)
1250 FillDistancesPrices(p);
1254 p->lenEnc.tableSize =
1255 p->repLenEnc.tableSize =
1256 p->numFastBytes + 1 - LZMA_MATCH_LEN_MIN;
1258 p->repLenEncCounter = REP_LEN_COUNT;
1260 LenPriceEnc_UpdateTables(&p->lenEnc, 1 << p->pb, &p->lenProbs, p->ProbPrices);
1261 LenPriceEnc_UpdateTables(&p->repLenEnc, 1 << p->pb, &p->repLenProbs, p->ProbPrices);
1270 } CLzmaEnc_SeqOutStreamBuf;
1272 static size_t SeqOutStreamBuf_Write(const ISeqOutStream *pp, const void *data, size_t size)
1274 CLzmaEnc_SeqOutStreamBuf *p = CONTAINER_FROM_VTBL(pp, CLzmaEnc_SeqOutStreamBuf, vt);
1280 memcpy(p->data, data, size);
1287 UInt32 LzmaEnc_GetNumAvailableBytes(CLzmaEncHandle pp)
1289 const CLzmaEnc *p = (CLzmaEnc *)pp;
1290 return p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);
1294 const Byte *LzmaEnc_GetCurBuf(CLzmaEncHandle pp)
1296 const CLzmaEnc *p = (CLzmaEnc *)pp;
1297 return p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
1301 SRes LzmaEnc_WriteProperties(CLzmaEncHandle pp, Byte *props, SizeT *size)
1303 CLzmaEnc *p = (CLzmaEnc *)pp;
1305 UInt32 dictSize = p->dictSize;
1306 if (*size < LZMA_PROPS_SIZE)
1307 return SZ_ERROR_PARAM;
1308 *size = LZMA_PROPS_SIZE;
1309 props[0] = (Byte)((p->pb * 5 + p->lp) * 9 + p->lc);
1311 if (dictSize >= ((UInt32)1 << 22))
1313 UInt32 kDictMask = ((UInt32)1 << 20) - 1;
1314 if (dictSize < (UInt32)0xFFFFFFFF - kDictMask)
1315 dictSize = (dictSize + kDictMask) & ~kDictMask;
1317 else for (i = 11; i <= 30; i++)
1319 if (dictSize <= ((UInt32)2 << i)) { dictSize = (2 << i); break; }
1320 if (dictSize <= ((UInt32)3 << i)) { dictSize = (3 << i); break; }
1323 for (i = 0; i < 4; i++)
1324 props[1 + i] = (Byte)(dictSize >> (8 * i));