1 /* LzmaEnc.c -- LZMA Encoder
2 2024-01-24: Igor Pavlov : Public domain */
8 /* #define SHOW_STAT */
9 /* #define SHOW_STAT2 */
11 #if defined(SHOW_STAT) || defined(SHOW_STAT2)
23 /* the following LzmaEnc_* declarations is internal LZMA interface for LZMA2 encoder */
25 SRes LzmaEnc_PrepareForLzma2(CLzmaEncHandle p, ISeqInStreamPtr inStream, UInt32 keepWindowSize,
26 ISzAllocPtr alloc, ISzAllocPtr allocBig);
27 SRes LzmaEnc_MemPrepare(CLzmaEncHandle p, const Byte *src, SizeT srcLen,
28 UInt32 keepWindowSize, ISzAllocPtr alloc, ISzAllocPtr allocBig);
29 SRes LzmaEnc_CodeOneMemBlock(CLzmaEncHandle p, BoolInt reInit,
30 Byte *dest, size_t *destLen, UInt32 desiredPackSize, UInt32 *unpackSize);
31 const Byte *LzmaEnc_GetCurBuf(CLzmaEncHandle p);
32 void LzmaEnc_Finish(CLzmaEncHandle p);
33 void LzmaEnc_SaveState(CLzmaEncHandle p);
34 void LzmaEnc_RestoreState(CLzmaEncHandle p);
37 static unsigned g_STAT_OFFSET = 0;
40 /* for good normalization speed we still reserve 256 MB before 4 GB range */
41 #define kLzmaMaxHistorySize ((UInt32)15 << 28)
43 // #define kNumTopBits 24
44 #define kTopValue ((UInt32)1 << 24)
46 #define kNumBitModelTotalBits 11
47 #define kBitModelTotal (1 << kNumBitModelTotalBits)
48 #define kNumMoveBits 5
49 #define kProbInitValue (kBitModelTotal >> 1)
51 #define kNumMoveReducingBits 4
52 #define kNumBitPriceShiftBits 4
53 // #define kBitPrice (1 << kNumBitPriceShiftBits)
55 #define REP_LEN_COUNT 64
57 void LzmaEncProps_Init(CLzmaEncProps *p)
60 p->dictSize = p->mc = 0;
61 p->reduceSize = (UInt64)(Int64)-1;
62 p->lc = p->lp = p->pb = p->algo = p->fb = p->btMode = p->numHashBytes = p->numThreads = -1;
63 p->numHashOutBits = 0;
68 void LzmaEncProps_Normalize(CLzmaEncProps *p)
71 if (level < 0) level = 5;
76 ( level <= 3 ? ((UInt32)1 << (level * 2 + 16)) :
77 ( level <= 6 ? ((UInt32)1 << (level + 19)) :
78 ( level <= 7 ? ((UInt32)1 << 25) : ((UInt32)1 << 26)
81 if (p->dictSize > p->reduceSize)
83 UInt32 v = (UInt32)p->reduceSize;
84 const UInt32 kReduceMin = ((UInt32)1 << 12);
91 if (p->lc < 0) p->lc = 3;
92 if (p->lp < 0) p->lp = 0;
93 if (p->pb < 0) p->pb = 2;
95 if (p->algo < 0) p->algo = (level < 5 ? 0 : 1);
96 if (p->fb < 0) p->fb = (level < 7 ? 32 : 64);
97 if (p->btMode < 0) p->btMode = (p->algo == 0 ? 0 : 1);
98 if (p->numHashBytes < 0) p->numHashBytes = (p->btMode ? 4 : 5);
99 if (p->mc == 0) p->mc = (16 + ((unsigned)p->fb >> 1)) >> (p->btMode ? 0 : 1);
101 if (p->numThreads < 0)
104 ((p->btMode && p->algo) ? 2 : 1);
110 UInt32 LzmaEncProps_GetDictSize(const CLzmaEncProps *props2)
112 CLzmaEncProps props = *props2;
113 LzmaEncProps_Normalize(&props);
114 return props.dictSize;
122 IF (SRC == 0) ZF = 1, DEST is undefined;
123 AMD : DEST is unchanged;
124 IF (SRC != 0) ZF = 0; DEST is index of top non-zero bit
125 BSR is slow in some processors
128 IF (SRC == 0) CF = 1, DEST is size_in_bits_of_register(src) (32 or 64)
129 IF (SRC != 0) CF = 0, DEST = num_lead_zero_bits
130 IF (DEST == 0) ZF = 1;
132 LZCNT works only in new processors starting from Haswell.
133 if LZCNT is not supported by processor, then it's executed as BSR.
134 LZCNT can be faster than BSR, if supported.
137 // #define LZMA_LOG_BSR
139 #if defined(MY_CPU_ARM_OR_ARM64) /* || defined(MY_CPU_X86_OR_AMD64) */
141 #if (defined(__clang__) && (__clang_major__ >= 6)) \
142 || (defined(__GNUC__) && (__GNUC__ >= 6))
144 #elif defined(_MSC_VER) && (_MSC_VER >= 1300)
145 // #if defined(MY_CPU_ARM_OR_ARM64)
151 // #include <intrin.h>
155 #if defined(__clang__) \
159 C code: : (30 - __builtin_clz(x))
160 gcc9/gcc10 for x64 /x86 : 30 - (bsr(x) xor 31)
161 clang10 for x64 : 31 + (bsr(x) xor -32)
164 #define MY_clz(x) ((unsigned)__builtin_clz(x))
166 // __builtin_ia32_lzcnt_u32
168 #else // #if defined(_MSC_VER)
170 #ifdef MY_CPU_ARM_OR_ARM64
172 #define MY_clz _CountLeadingZeros
174 #else // if defined(MY_CPU_X86_OR_AMD64)
176 // #define MY_clz __lzcnt // we can use lzcnt (unsupported by old CPU)
177 // _BitScanReverse code is not optimal for some MSVC compilers
178 #define BSR2_RET(pos, res) { unsigned long zz; _BitScanReverse(&zz, (pos)); zz--; \
179 res = (zz + zz) + (pos >> zz); }
181 #endif // MY_CPU_X86_OR_AMD64
188 #define BSR2_RET(pos, res) { unsigned zz = 30 - MY_clz(pos); \
189 res = (zz + zz) + (pos >> zz); }
194 unsigned GetPosSlot1(UInt32 pos);
195 unsigned GetPosSlot1(UInt32 pos)
201 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res) }
202 #define GetPosSlot(pos, res) { if (pos < 2) res = pos; else BSR2_RET(pos, res) }
205 #else // ! LZMA_LOG_BSR
207 #define kNumLogBits (11 + sizeof(size_t) / 8 * 3)
209 #define kDicLogSizeMaxCompress ((kNumLogBits - 1) * 2 + 7)
211 static void LzmaEnc_FastPosInit(Byte *g_FastPos)
218 for (slot = 2; slot < kNumLogBits * 2; slot++)
220 size_t k = ((size_t)1 << ((slot >> 1) - 1));
222 for (j = 0; j < k; j++)
223 g_FastPos[j] = (Byte)slot;
228 /* we can use ((limit - pos) >> 31) only if (pos < ((UInt32)1 << 31)) */
230 #define BSR2_RET(pos, res) { unsigned zz = 6 + ((kNumLogBits - 1) & \
231 (0 - (((((UInt32)1 << (kNumLogBits + 6)) - 1) - pos) >> 31))); \
232 res = p->g_FastPos[pos >> zz] + (zz * 2); }
236 #define BSR2_RET(pos, res) { unsigned zz = 6 + ((kNumLogBits - 1) & \
237 (0 - (((((UInt32)1 << (kNumLogBits)) - 1) - (pos >> 6)) >> 31))); \
238 res = p->g_FastPos[pos >> zz] + (zz * 2); }
241 #define BSR2_RET(pos, res) { unsigned zz = (pos < (1 << (kNumLogBits + 6))) ? 6 : 6 + kNumLogBits - 1; \
242 res = p->g_FastPos[pos >> zz] + (zz * 2); }
245 #define BSR2_RET(pos, res) { res = (pos < (1 << (kNumLogBits + 6))) ? \
246 p->g_FastPos[pos >> 6] + 12 : \
247 p->g_FastPos[pos >> (6 + kNumLogBits - 1)] + (6 + (kNumLogBits - 1)) * 2; }
250 #define GetPosSlot1(pos) p->g_FastPos[pos]
251 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }
252 #define GetPosSlot(pos, res) { if (pos < kNumFullDistances) res = p->g_FastPos[pos & (kNumFullDistances - 1)]; else BSR2_RET(pos, res); }
254 #endif // LZMA_LOG_BSR
257 #define LZMA_NUM_REPS 4
259 typedef UInt16 CState;
260 typedef UInt16 CExtra;
269 // > 1 : MATCH (extra-1) : LIT : REP0 (len)
272 UInt32 reps[LZMA_NUM_REPS];
277 #define kNumOpts (1 << 11)
278 #define kPackReserve (kNumOpts * 8)
279 // #define kNumOpts (1 << 12)
280 // #define kPackReserve (1 + kNumOpts * 2)
282 #define kNumLenToPosStates 4
283 #define kNumPosSlotBits 6
284 // #define kDicLogSizeMin 0
285 #define kDicLogSizeMax 32
286 #define kDistTableSizeMax (kDicLogSizeMax * 2)
288 #define kNumAlignBits 4
289 #define kAlignTableSize (1 << kNumAlignBits)
290 #define kAlignMask (kAlignTableSize - 1)
292 #define kStartPosModelIndex 4
293 #define kEndPosModelIndex 14
294 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
297 #ifdef Z7_LZMA_PROB32
304 #define LZMA_PB_MAX 4
305 #define LZMA_LC_MAX 8
306 #define LZMA_LP_MAX 4
308 #define LZMA_NUM_PB_STATES_MAX (1 << LZMA_PB_MAX)
310 #define kLenNumLowBits 3
311 #define kLenNumLowSymbols (1 << kLenNumLowBits)
312 #define kLenNumHighBits 8
313 #define kLenNumHighSymbols (1 << kLenNumHighBits)
314 #define kLenNumSymbolsTotal (kLenNumLowSymbols * 2 + kLenNumHighSymbols)
316 #define LZMA_MATCH_LEN_MIN 2
317 #define LZMA_MATCH_LEN_MAX (LZMA_MATCH_LEN_MIN + kLenNumSymbolsTotal - 1)
319 #define kNumStates 12
324 CLzmaProb low[LZMA_NUM_PB_STATES_MAX << (kLenNumLowBits + 1)];
325 CLzmaProb high[kLenNumHighSymbols];
332 UInt32 prices[LZMA_NUM_PB_STATES_MAX][kLenNumSymbolsTotal];
333 // UInt32 prices1[LZMA_NUM_PB_STATES_MAX][kLenNumLowSymbols * 2];
334 // UInt32 prices2[kLenNumSymbolsTotal];
337 #define GET_PRICE_LEN(p, posState, len) \
338 ((p)->prices[posState][(size_t)(len) - LZMA_MATCH_LEN_MIN])
341 #define GET_PRICE_LEN(p, posState, len) \
342 ((p)->prices2[(size_t)(len) - 2] + ((p)->prices1[posState][((len) - 2) & (kLenNumLowSymbols * 2 - 1)] & (((len) - 2 - kLenNumLowSymbols * 2) >> 9)))
354 ISeqOutStreamPtr outStream;
365 UInt32 reps[LZMA_NUM_REPS];
367 CLzmaProb posAlignEncoder[1 << kNumAlignBits];
368 CLzmaProb isRep[kNumStates];
369 CLzmaProb isRepG0[kNumStates];
370 CLzmaProb isRepG1[kNumStates];
371 CLzmaProb isRepG2[kNumStates];
372 CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];
373 CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];
375 CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];
376 CLzmaProb posEncoders[kNumFullDistances];
384 typedef UInt32 CProbPrice;
389 void *matchFinderObj;
390 IMatchFinder2 matchFinder;
395 unsigned longestMatchLen;
400 unsigned numFastBytes;
401 unsigned additionalOffset;
402 UInt32 reps[LZMA_NUM_REPS];
403 unsigned lpMask, pbMask;
413 BoolInt writeEndMark;
421 unsigned matchPriceCount;
422 // unsigned alignPriceCount;
423 int repLenEncCounter;
425 unsigned distTableSize;
432 // begin of CMatchFinderMt is used in LZ thread
433 CMatchFinderMt matchFinderMt;
434 // end of CMatchFinderMt is used in BT and HASH threads
436 // CMatchFinder matchFinderBase;
438 CMatchFinder matchFinderBase;
441 // we suppose that we have 8-bytes alignment after CMatchFinder
448 CProbPrice ProbPrices[kBitModelTotal >> kNumMoveReducingBits];
450 // we want {len , dist} pairs to be 8-bytes aligned in matches array
451 UInt32 matches[LZMA_MATCH_LEN_MAX * 2 + 2];
453 // we want 8-bytes alignment here
454 UInt32 alignPrices[kAlignTableSize];
455 UInt32 posSlotPrices[kNumLenToPosStates][kDistTableSizeMax];
456 UInt32 distancesPrices[kNumLenToPosStates][kNumFullDistances];
458 CLzmaProb posAlignEncoder[1 << kNumAlignBits];
459 CLzmaProb isRep[kNumStates];
460 CLzmaProb isRepG0[kNumStates];
461 CLzmaProb isRepG1[kNumStates];
462 CLzmaProb isRepG2[kNumStates];
463 CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];
464 CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];
465 CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];
466 CLzmaProb posEncoders[kNumFullDistances];
472 Byte g_FastPos[1 << kNumLogBits];
476 CLenPriceEnc repLenEnc;
478 COptimal opt[kNumOpts];
480 CSaveState saveState;
482 // BoolInt mf_Failure;
489 #define MFB (p->matchFinderBase)
492 #define MFB (p->matchFinderMt.MatchFinder)
496 // #define GET_CLzmaEnc_p CLzmaEnc *p = (CLzmaEnc*)(void *)p;
497 // #define GET_const_CLzmaEnc_p const CLzmaEnc *p = (const CLzmaEnc*)(const void *)p;
499 #define COPY_ARR(dest, src, arr) memcpy((dest)->arr, (src)->arr, sizeof((src)->arr));
501 #define COPY_LZMA_ENC_STATE(d, s, p) \
502 (d)->state = (s)->state; \
503 COPY_ARR(d, s, reps) \
504 COPY_ARR(d, s, posAlignEncoder) \
505 COPY_ARR(d, s, isRep) \
506 COPY_ARR(d, s, isRepG0) \
507 COPY_ARR(d, s, isRepG1) \
508 COPY_ARR(d, s, isRepG2) \
509 COPY_ARR(d, s, isMatch) \
510 COPY_ARR(d, s, isRep0Long) \
511 COPY_ARR(d, s, posSlotEncoder) \
512 COPY_ARR(d, s, posEncoders) \
513 (d)->lenProbs = (s)->lenProbs; \
514 (d)->repLenProbs = (s)->repLenProbs; \
515 memcpy((d)->litProbs, (s)->litProbs, ((size_t)0x300 * sizeof(CLzmaProb)) << (p)->lclp);
517 void LzmaEnc_SaveState(CLzmaEncHandle p)
520 CSaveState *v = &p->saveState;
521 COPY_LZMA_ENC_STATE(v, p, p)
524 void LzmaEnc_RestoreState(CLzmaEncHandle p)
527 const CSaveState *v = &p->saveState;
528 COPY_LZMA_ENC_STATE(p, v, p)
533 SRes LzmaEnc_SetProps(CLzmaEncHandle p, const CLzmaEncProps *props2)
536 CLzmaEncProps props = *props2;
537 LzmaEncProps_Normalize(&props);
539 if (props.lc > LZMA_LC_MAX
540 || props.lp > LZMA_LP_MAX
541 || props.pb > LZMA_PB_MAX)
542 return SZ_ERROR_PARAM;
545 if (props.dictSize > kLzmaMaxHistorySize)
546 props.dictSize = kLzmaMaxHistorySize;
550 const UInt64 dict64 = props.dictSize;
551 if (dict64 > ((UInt64)1 << kDicLogSizeMaxCompress))
552 return SZ_ERROR_PARAM;
556 p->dictSize = props.dictSize;
558 unsigned fb = (unsigned)props.fb;
561 if (fb > LZMA_MATCH_LEN_MAX)
562 fb = LZMA_MATCH_LEN_MAX;
563 p->numFastBytes = fb;
565 p->lc = (unsigned)props.lc;
566 p->lp = (unsigned)props.lp;
567 p->pb = (unsigned)props.pb;
568 p->fastMode = (props.algo == 0);
569 // p->_maxMode = True;
570 MFB.btMode = (Byte)(props.btMode ? 1 : 0);
571 // MFB.btMode = (Byte)(props.btMode);
573 unsigned numHashBytes = 4;
576 if (props.numHashBytes < 2) numHashBytes = 2;
577 else if (props.numHashBytes < 4) numHashBytes = (unsigned)props.numHashBytes;
579 if (props.numHashBytes >= 5) numHashBytes = 5;
581 MFB.numHashBytes = numHashBytes;
582 // MFB.numHashBytes_Min = 2;
583 MFB.numHashOutBits = (Byte)props.numHashOutBits;
586 MFB.cutValue = props.mc;
588 p->writeEndMark = (BoolInt)props.writeEndMark;
592 if (newMultiThread != _multiThread)
594 ReleaseMatchFinder();
595 _multiThread = newMultiThread;
598 p->multiThread = (props.numThreads > 1);
599 p->matchFinderMt.btSync.affinity =
600 p->matchFinderMt.hashSync.affinity = props.affinity;
607 void LzmaEnc_SetDataSize(CLzmaEncHandle p, UInt64 expectedDataSiize)
610 MFB.expectedDataSize = expectedDataSiize;
614 #define kState_Start 0
615 #define kState_LitAfterMatch 4
616 #define kState_LitAfterRep 5
617 #define kState_MatchAfterLit 7
618 #define kState_RepAfterLit 8
620 static const Byte kLiteralNextStates[kNumStates] = {0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5};
621 static const Byte kMatchNextStates[kNumStates] = {7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10};
622 static const Byte kRepNextStates[kNumStates] = {8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11};
623 static const Byte kShortRepNextStates[kNumStates]= {9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11};
625 #define IsLitState(s) ((s) < 7)
626 #define GetLenToPosState2(len) (((len) < kNumLenToPosStates - 1) ? (len) : kNumLenToPosStates - 1)
627 #define GetLenToPosState(len) (((len) < kNumLenToPosStates + 1) ? (len) - 2 : kNumLenToPosStates - 1)
629 #define kInfinityPrice (1 << 30)
631 static void RangeEnc_Construct(CRangeEnc *p)
637 #define RangeEnc_GetProcessed(p) ( (p)->processed + (size_t)((p)->buf - (p)->bufBase) + (p)->cacheSize)
638 #define RangeEnc_GetProcessed_sizet(p) ((size_t)(p)->processed + (size_t)((p)->buf - (p)->bufBase) + (size_t)(p)->cacheSize)
640 #define RC_BUF_SIZE (1 << 16)
642 static int RangeEnc_Alloc(CRangeEnc *p, ISzAllocPtr alloc)
646 p->bufBase = (Byte *)ISzAlloc_Alloc(alloc, RC_BUF_SIZE);
649 p->bufLim = p->bufBase + RC_BUF_SIZE;
654 static void RangeEnc_Free(CRangeEnc *p, ISzAllocPtr alloc)
656 ISzAlloc_Free(alloc, p->bufBase);
660 static void RangeEnc_Init(CRangeEnc *p)
662 p->range = 0xFFFFFFFF;
673 Z7_NO_INLINE static void RangeEnc_FlushStream(CRangeEnc *p)
675 const size_t num = (size_t)(p->buf - p->bufBase);
678 if (num != ISeqOutStream_Write(p->outStream, p->bufBase, num))
679 p->res = SZ_ERROR_WRITE;
685 Z7_NO_INLINE static void Z7_FASTCALL RangeEnc_ShiftLow(CRangeEnc *p)
687 UInt32 low = (UInt32)p->low;
688 unsigned high = (unsigned)(p->low >> 32);
689 p->low = (UInt32)(low << 8);
690 if (low < (UInt32)0xFF000000 || high != 0)
694 *buf++ = (Byte)(p->cache + high);
695 p->cache = (unsigned)(low >> 24);
697 if (buf == p->bufLim)
698 RangeEnc_FlushStream(p);
699 if (p->cacheSize == 0)
706 *buf++ = (Byte)(high);
708 if (buf == p->bufLim)
709 RangeEnc_FlushStream(p);
710 if (--p->cacheSize == 0)
717 static void RangeEnc_FlushData(CRangeEnc *p)
720 for (i = 0; i < 5; i++)
721 RangeEnc_ShiftLow(p);
724 #define RC_NORM(p) if (range < kTopValue) { range <<= 8; RangeEnc_ShiftLow(p); }
726 #define RC_BIT_PRE(p, prob) \
728 newBound = (range >> kNumBitModelTotalBits) * ttt;
730 // #define Z7_LZMA_ENC_USE_BRANCH
732 #ifdef Z7_LZMA_ENC_USE_BRANCH
734 #define RC_BIT(p, prob, bit) { \
735 RC_BIT_PRE(p, prob) \
736 if (bit == 0) { range = newBound; ttt += (kBitModelTotal - ttt) >> kNumMoveBits; } \
737 else { (p)->low += newBound; range -= newBound; ttt -= ttt >> kNumMoveBits; } \
738 *(prob) = (CLzmaProb)ttt; \
744 #define RC_BIT(p, prob, bit) { \
746 RC_BIT_PRE(p, prob) \
747 mask = 0 - (UInt32)bit; \
752 mask = (UInt32)bit - 1; \
753 range += newBound & mask; \
754 mask &= (kBitModelTotal - ((1 << kNumMoveBits) - 1)); \
755 mask += ((1 << kNumMoveBits) - 1); \
756 ttt += (UInt32)((Int32)(mask - ttt) >> kNumMoveBits); \
757 *(prob) = (CLzmaProb)ttt; \
766 #define RC_BIT_0_BASE(p, prob) \
767 range = newBound; *(prob) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits));
769 #define RC_BIT_1_BASE(p, prob) \
770 range -= newBound; (p)->low += newBound; *(prob) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits)); \
772 #define RC_BIT_0(p, prob) \
773 RC_BIT_0_BASE(p, prob) \
776 #define RC_BIT_1(p, prob) \
777 RC_BIT_1_BASE(p, prob) \
780 static void RangeEnc_EncodeBit_0(CRangeEnc *p, CLzmaProb *prob)
782 UInt32 range, ttt, newBound;
789 static void LitEnc_Encode(CRangeEnc *p, CLzmaProb *probs, UInt32 sym)
791 UInt32 range = p->range;
795 UInt32 ttt, newBound;
796 // RangeEnc_EncodeBit(p, probs + (sym >> 8), (sym >> 7) & 1);
797 CLzmaProb *prob = probs + (sym >> 8);
798 UInt32 bit = (sym >> 7) & 1;
802 while (sym < 0x10000);
806 static void LitEnc_EncodeMatched(CRangeEnc *p, CLzmaProb *probs, UInt32 sym, UInt32 matchByte)
808 UInt32 range = p->range;
813 UInt32 ttt, newBound;
817 // RangeEnc_EncodeBit(p, probs + (offs + (matchByte & offs) + (sym >> 8)), (sym >> 7) & 1);
818 prob = probs + (offs + (matchByte & offs) + (sym >> 8));
819 bit = (sym >> 7) & 1;
821 offs &= ~(matchByte ^ sym);
824 while (sym < 0x10000);
830 static void LzmaEnc_InitPriceTables(CProbPrice *ProbPrices)
833 for (i = 0; i < (kBitModelTotal >> kNumMoveReducingBits); i++)
835 const unsigned kCyclesBits = kNumBitPriceShiftBits;
836 UInt32 w = (i << kNumMoveReducingBits) + (1 << (kNumMoveReducingBits - 1));
837 unsigned bitCount = 0;
839 for (j = 0; j < kCyclesBits; j++)
843 while (w >= ((UInt32)1 << 16))
849 ProbPrices[i] = (CProbPrice)(((unsigned)kNumBitModelTotalBits << kCyclesBits) - 15 - bitCount);
850 // printf("\n%3d: %5d", i, ProbPrices[i]);
855 #define GET_PRICE(prob, bit) \
856 p->ProbPrices[((prob) ^ (unsigned)(((-(int)(bit))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits]
858 #define GET_PRICEa(prob, bit) \
859 ProbPrices[((prob) ^ (unsigned)((-((int)(bit))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits]
861 #define GET_PRICE_0(prob) p->ProbPrices[(prob) >> kNumMoveReducingBits]
862 #define GET_PRICE_1(prob) p->ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]
864 #define GET_PRICEa_0(prob) ProbPrices[(prob) >> kNumMoveReducingBits]
865 #define GET_PRICEa_1(prob) ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]
868 static UInt32 LitEnc_GetPrice(const CLzmaProb *probs, UInt32 sym, const CProbPrice *ProbPrices)
874 unsigned bit = sym & 1;
876 price += GET_PRICEa(probs[sym], bit);
883 static UInt32 LitEnc_Matched_GetPrice(const CLzmaProb *probs, UInt32 sym, UInt32 matchByte, const CProbPrice *ProbPrices)
891 price += GET_PRICEa(probs[offs + (matchByte & offs) + (sym >> 8)], (sym >> 7) & 1);
893 offs &= ~(matchByte ^ sym);
895 while (sym < 0x10000);
900 static void RcTree_ReverseEncode(CRangeEnc *rc, CLzmaProb *probs, unsigned numBits, unsigned sym)
902 UInt32 range = rc->range;
906 UInt32 ttt, newBound;
907 unsigned bit = sym & 1;
908 // RangeEnc_EncodeBit(rc, probs + m, bit);
910 RC_BIT(rc, probs + m, bit)
919 static void LenEnc_Init(CLenEnc *p)
922 for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << (kLenNumLowBits + 1)); i++)
923 p->low[i] = kProbInitValue;
924 for (i = 0; i < kLenNumHighSymbols; i++)
925 p->high[i] = kProbInitValue;
928 static void LenEnc_Encode(CLenEnc *p, CRangeEnc *rc, unsigned sym, unsigned posState)
930 UInt32 range, ttt, newBound;
931 CLzmaProb *probs = p->low;
933 RC_BIT_PRE(rc, probs)
934 if (sym >= kLenNumLowSymbols)
937 probs += kLenNumLowSymbols;
938 RC_BIT_PRE(rc, probs)
939 if (sym >= kLenNumLowSymbols * 2)
943 // RcTree_Encode(rc, p->high, kLenNumHighBits, sym - kLenNumLowSymbols * 2);
944 LitEnc_Encode(rc, p->high, sym - kLenNumLowSymbols * 2);
947 sym -= kLenNumLowSymbols;
950 // RcTree_Encode(rc, probs + (posState << kLenNumLowBits), kLenNumLowBits, sym);
955 probs += (posState << (1 + kLenNumLowBits));
956 bit = (sym >> 2) ; RC_BIT(rc, probs + 1, bit) m = (1 << 1) + bit;
957 bit = (sym >> 1) & 1; RC_BIT(rc, probs + m, bit) m = (m << 1) + bit;
958 bit = sym & 1; RC_BIT(rc, probs + m, bit)
963 static void SetPrices_3(const CLzmaProb *probs, UInt32 startPrice, UInt32 *prices, const CProbPrice *ProbPrices)
966 for (i = 0; i < 8; i += 2)
968 UInt32 price = startPrice;
970 price += GET_PRICEa(probs[1 ], (i >> 2));
971 price += GET_PRICEa(probs[2 + (i >> 2)], (i >> 1) & 1);
972 prob = probs[4 + (i >> 1)];
973 prices[i ] = price + GET_PRICEa_0(prob);
974 prices[i + 1] = price + GET_PRICEa_1(prob);
979 Z7_NO_INLINE static void Z7_FASTCALL LenPriceEnc_UpdateTables(
981 unsigned numPosStates,
983 const CProbPrice *ProbPrices)
988 unsigned prob = enc->low[0];
991 b = GET_PRICEa_1(prob);
992 a = GET_PRICEa_0(prob);
993 c = b + GET_PRICEa_0(enc->low[kLenNumLowSymbols]);
994 for (posState = 0; posState < numPosStates; posState++)
996 UInt32 *prices = p->prices[posState];
997 const CLzmaProb *probs = enc->low + (posState << (1 + kLenNumLowBits));
998 SetPrices_3(probs, a, prices, ProbPrices);
999 SetPrices_3(probs + kLenNumLowSymbols, c, prices + kLenNumLowSymbols, ProbPrices);
1007 a = GET_PRICEa_0(enc->low[0]);
1008 for (i = 0; i < kLenNumLowSymbols; i++)
1010 a = GET_PRICEa_1(enc->low[0]);
1011 b = a + GET_PRICEa_0(enc->low[kLenNumLowSymbols]);
1012 for (i = kLenNumLowSymbols; i < kLenNumLowSymbols * 2; i++)
1014 a += GET_PRICEa_1(enc->low[kLenNumLowSymbols]);
1018 // p->counter = numSymbols;
1022 unsigned i = p->tableSize;
1024 if (i > kLenNumLowSymbols * 2)
1026 const CLzmaProb *probs = enc->high;
1027 UInt32 *prices = p->prices[0] + kLenNumLowSymbols * 2;
1028 i -= kLenNumLowSymbols * 2 - 1;
1030 b += GET_PRICEa_1(enc->low[kLenNumLowSymbols]);
1035 // RcTree_GetPrice(enc->high, kLenNumHighBits, i - kLenNumLowSymbols * 2, ProbPrices);
1036 LitEnc_GetPrice(probs, i - kLenNumLowSymbols * 2, ProbPrices);
1038 // UInt32 price = a + RcTree_GetPrice(probs, kLenNumHighBits - 1, sym, ProbPrices);
1039 unsigned sym = --i + (1 << (kLenNumHighBits - 1));
1043 const unsigned bit = sym & 1;
1045 price += GET_PRICEa(probs[sym], bit);
1050 const unsigned prob = probs[(size_t)i + (1 << (kLenNumHighBits - 1))];
1051 prices[(size_t)i * 2 ] = price + GET_PRICEa_0(prob);
1052 prices[(size_t)i * 2 + 1] = price + GET_PRICEa_1(prob);
1059 const size_t num = (p->tableSize - kLenNumLowSymbols * 2) * sizeof(p->prices[0][0]);
1060 for (posState = 1; posState < numPosStates; posState++)
1061 memcpy(p->prices[posState] + kLenNumLowSymbols * 2, p->prices[0] + kLenNumLowSymbols * 2, num);
1069 g_STAT_OFFSET += num;
1070 printf("\n MovePos %u", num);
1074 #define MOVE_POS(p, num) { \
1075 p->additionalOffset += (num); \
1076 p->matchFinder.Skip(p->matchFinderObj, (UInt32)(num)); }
1079 static unsigned ReadMatchDistances(CLzmaEnc *p, unsigned *numPairsRes)
1083 p->additionalOffset++;
1084 p->numAvail = p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);
1086 const UInt32 *d = p->matchFinder.GetMatches(p->matchFinderObj, p->matches);
1087 // if (!d) { p->mf_Failure = True; *numPairsRes = 0; return 0; }
1088 numPairs = (unsigned)(d - p->matches);
1090 *numPairsRes = numPairs;
1093 printf("\n i = %u numPairs = %u ", g_STAT_OFFSET, numPairs / 2);
1097 for (i = 0; i < numPairs; i += 2)
1098 printf("%2u %6u | ", p->matches[i], p->matches[i + 1]);
1105 const unsigned len = p->matches[(size_t)numPairs - 2];
1106 if (len != p->numFastBytes)
1109 UInt32 numAvail = p->numAvail;
1110 if (numAvail > LZMA_MATCH_LEN_MAX)
1111 numAvail = LZMA_MATCH_LEN_MAX;
1113 const Byte *p1 = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1114 const Byte *p2 = p1 + len;
1115 const ptrdiff_t dif = (ptrdiff_t)-1 - (ptrdiff_t)p->matches[(size_t)numPairs - 1];
1116 const Byte *lim = p1 + numAvail;
1117 for (; p2 != lim && *p2 == p2[dif]; p2++)
1119 return (unsigned)(p2 - p1);
1125 #define MARK_LIT ((UInt32)(Int32)-1)
1127 #define MakeAs_Lit(p) { (p)->dist = MARK_LIT; (p)->extra = 0; }
1128 #define MakeAs_ShortRep(p) { (p)->dist = 0; (p)->extra = 0; }
1129 #define IsShortRep(p) ((p)->dist == 0)
1132 #define GetPrice_ShortRep(p, state, posState) \
1133 ( GET_PRICE_0(p->isRepG0[state]) + GET_PRICE_0(p->isRep0Long[state][posState]))
1135 #define GetPrice_Rep_0(p, state, posState) ( \
1136 GET_PRICE_1(p->isMatch[state][posState]) \
1137 + GET_PRICE_1(p->isRep0Long[state][posState])) \
1138 + GET_PRICE_1(p->isRep[state]) \
1139 + GET_PRICE_0(p->isRepG0[state])
1142 static UInt32 GetPrice_PureRep(const CLzmaEnc *p, unsigned repIndex, size_t state, size_t posState)
1145 UInt32 prob = p->isRepG0[state];
1148 price = GET_PRICE_0(prob);
1149 price += GET_PRICE_1(p->isRep0Long[state][posState]);
1153 price = GET_PRICE_1(prob);
1154 prob = p->isRepG1[state];
1156 price += GET_PRICE_0(prob);
1159 price += GET_PRICE_1(prob);
1160 price += GET_PRICE(p->isRepG2[state], repIndex - 2);
1167 static unsigned Backward(CLzmaEnc *p, unsigned cur)
1169 unsigned wr = cur + 1;
1174 UInt32 dist = p->opt[cur].dist;
1175 unsigned len = (unsigned)p->opt[cur].len;
1176 unsigned extra = (unsigned)p->opt[cur].extra;
1182 p->opt[wr].len = (UInt32)len;
1187 p->opt[wr].dist = dist;
1192 p->opt[wr].dist = 0;
1195 p->opt[wr].dist = MARK_LIT;
1208 p->opt[wr].dist = dist;
1209 p->opt[wr].len = (UInt32)len;
1215 #define LIT_PROBS(pos, prevByte) \
1216 (p->litProbs + (UInt32)3 * (((((pos) << 8) + (prevByte)) & p->lpMask) << p->lc))
1219 static unsigned GetOptimum(CLzmaEnc *p, UInt32 position)
1222 UInt32 reps[LZMA_NUM_REPS];
1223 unsigned repLens[LZMA_NUM_REPS];
1228 unsigned numPairs, mainLen, repMaxIndex, i, posState;
1229 UInt32 matchPrice, repMatchPrice;
1231 Byte curByte, matchByte;
1233 p->optCur = p->optEnd = 0;
1235 if (p->additionalOffset == 0)
1236 mainLen = ReadMatchDistances(p, &numPairs);
1239 mainLen = p->longestMatchLen;
1240 numPairs = p->numPairs;
1243 numAvail = p->numAvail;
1246 p->backRes = MARK_LIT;
1249 if (numAvail > LZMA_MATCH_LEN_MAX)
1250 numAvail = LZMA_MATCH_LEN_MAX;
1252 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1255 for (i = 0; i < LZMA_NUM_REPS; i++)
1259 reps[i] = p->reps[i];
1260 data2 = data - reps[i];
1261 if (data[0] != data2[0] || data[1] != data2[1])
1266 for (len = 2; len < numAvail && data[len] == data2[len]; len++)
1269 if (len > repLens[repMaxIndex])
1271 if (len == LZMA_MATCH_LEN_MAX) // 21.03 : optimization
1275 if (repLens[repMaxIndex] >= p->numFastBytes)
1278 p->backRes = (UInt32)repMaxIndex;
1279 len = repLens[repMaxIndex];
1280 MOVE_POS(p, len - 1)
1284 matches = p->matches;
1285 #define MATCHES matches
1286 // #define MATCHES p->matches
1288 if (mainLen >= p->numFastBytes)
1290 p->backRes = MATCHES[(size_t)numPairs - 1] + LZMA_NUM_REPS;
1291 MOVE_POS(p, mainLen - 1)
1296 matchByte = *(data - reps[0]);
1298 last = repLens[repMaxIndex];
1299 if (last <= mainLen)
1302 if (last < 2 && curByte != matchByte)
1304 p->backRes = MARK_LIT;
1308 p->opt[0].state = (CState)p->state;
1310 posState = (position & p->pbMask);
1313 const CLzmaProb *probs = LIT_PROBS(position, *(data - 1));
1314 p->opt[1].price = GET_PRICE_0(p->isMatch[p->state][posState]) +
1315 (!IsLitState(p->state) ?
1316 LitEnc_Matched_GetPrice(probs, curByte, matchByte, p->ProbPrices) :
1317 LitEnc_GetPrice(probs, curByte, p->ProbPrices));
1320 MakeAs_Lit(&p->opt[1])
1322 matchPrice = GET_PRICE_1(p->isMatch[p->state][posState]);
1323 repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[p->state]);
1326 if (matchByte == curByte && repLens[0] == 0)
1328 UInt32 shortRepPrice = repMatchPrice + GetPrice_ShortRep(p, p->state, posState);
1329 if (shortRepPrice < p->opt[1].price)
1331 p->opt[1].price = shortRepPrice;
1332 MakeAs_ShortRep(&p->opt[1])
1336 p->backRes = p->opt[1].dist;
1343 p->opt[0].reps[0] = reps[0];
1344 p->opt[0].reps[1] = reps[1];
1345 p->opt[0].reps[2] = reps[2];
1346 p->opt[0].reps[3] = reps[3];
1348 // ---------- REP ----------
1350 for (i = 0; i < LZMA_NUM_REPS; i++)
1352 unsigned repLen = repLens[i];
1356 price = repMatchPrice + GetPrice_PureRep(p, i, p->state, posState);
1359 UInt32 price2 = price + GET_PRICE_LEN(&p->repLenEnc, posState, repLen);
1360 COptimal *opt = &p->opt[repLen];
1361 if (price2 < opt->price)
1363 opt->price = price2;
1364 opt->len = (UInt32)repLen;
1365 opt->dist = (UInt32)i;
1369 while (--repLen >= 2);
1373 // ---------- MATCH ----------
1375 unsigned len = repLens[0] + 1;
1379 UInt32 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[p->state]);
1384 while (len > MATCHES[offs])
1390 UInt32 dist = MATCHES[(size_t)offs + 1];
1391 UInt32 price = normalMatchPrice + GET_PRICE_LEN(&p->lenEnc, posState, len);
1392 unsigned lenToPosState = GetLenToPosState(len);
1394 if (dist < kNumFullDistances)
1395 price += p->distancesPrices[lenToPosState][dist & (kNumFullDistances - 1)];
1399 GetPosSlot2(dist, slot)
1400 price += p->alignPrices[dist & kAlignMask];
1401 price += p->posSlotPrices[lenToPosState][slot];
1406 if (price < opt->price)
1409 opt->len = (UInt32)len;
1410 opt->dist = dist + LZMA_NUM_REPS;
1414 if (len == MATCHES[offs])
1417 if (offs == numPairs)
1428 /* if (position >= 0) */
1431 printf("\n pos = %4X", position);
1432 for (i = cur; i <= last; i++)
1433 printf("\nprice[%4X] = %u", position - cur + i, p->opt[i].price);
1440 // ---------- Optimal Parsing ----------
1445 UInt32 numAvailFull;
1446 unsigned newLen, numPairs, prev, state, posState, startLen;
1447 UInt32 litPrice, matchPrice, repMatchPrice;
1449 Byte curByte, matchByte;
1451 COptimal *curOpt, *nextOpt;
1457 if (cur >= kNumOpts - 64)
1460 UInt32 price = p->opt[cur].price;
1462 for (j = cur + 1; j <= last; j++)
1464 UInt32 price2 = p->opt[j].price;
1465 if (price >= price2)
1472 unsigned delta = best - cur;
1482 newLen = ReadMatchDistances(p, &numPairs);
1484 if (newLen >= p->numFastBytes)
1486 p->numPairs = numPairs;
1487 p->longestMatchLen = newLen;
1491 curOpt = &p->opt[cur];
1495 // we need that check here, if skip_items in p->opt are possible
1497 if (curOpt->price >= kInfinityPrice)
1501 prev = cur - curOpt->len;
1503 if (curOpt->len == 1)
1505 state = (unsigned)p->opt[prev].state;
1506 if (IsShortRep(curOpt))
1507 state = kShortRepNextStates[state];
1509 state = kLiteralNextStates[state];
1513 const COptimal *prevOpt;
1515 UInt32 dist = curOpt->dist;
1519 prev -= (unsigned)curOpt->extra;
1520 state = kState_RepAfterLit;
1521 if (curOpt->extra == 1)
1522 state = (dist < LZMA_NUM_REPS ? kState_RepAfterLit : kState_MatchAfterLit);
1526 state = (unsigned)p->opt[prev].state;
1527 if (dist < LZMA_NUM_REPS)
1528 state = kRepNextStates[state];
1530 state = kMatchNextStates[state];
1533 prevOpt = &p->opt[prev];
1534 b0 = prevOpt->reps[0];
1536 if (dist < LZMA_NUM_REPS)
1541 reps[1] = prevOpt->reps[1];
1542 reps[2] = prevOpt->reps[2];
1543 reps[3] = prevOpt->reps[3];
1548 b0 = prevOpt->reps[1];
1552 reps[2] = prevOpt->reps[2];
1553 reps[3] = prevOpt->reps[3];
1558 reps[0] = prevOpt->reps[dist];
1559 reps[3] = prevOpt->reps[dist ^ 1];
1565 reps[0] = (dist - LZMA_NUM_REPS + 1);
1567 reps[2] = prevOpt->reps[1];
1568 reps[3] = prevOpt->reps[2];
1572 curOpt->state = (CState)state;
1573 curOpt->reps[0] = reps[0];
1574 curOpt->reps[1] = reps[1];
1575 curOpt->reps[2] = reps[2];
1576 curOpt->reps[3] = reps[3];
1578 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1580 matchByte = *(data - reps[0]);
1582 posState = (position & p->pbMask);
1585 The order of Price checks:
1589 < REP [ : LIT : REP_0 ]
1590 < MATCH [ : LIT : REP_0 ]
1594 UInt32 curPrice = curOpt->price;
1595 unsigned prob = p->isMatch[state][posState];
1596 matchPrice = curPrice + GET_PRICE_1(prob);
1597 litPrice = curPrice + GET_PRICE_0(prob);
1600 nextOpt = &p->opt[(size_t)cur + 1];
1603 // here we can allow skip_items in p->opt, if we don't check (nextOpt->price < kInfinityPrice)
1605 if ((nextOpt->price < kInfinityPrice
1606 // && !IsLitState(state)
1607 && matchByte == curByte)
1608 || litPrice > nextOpt->price
1613 const CLzmaProb *probs = LIT_PROBS(position, *(data - 1));
1614 litPrice += (!IsLitState(state) ?
1615 LitEnc_Matched_GetPrice(probs, curByte, matchByte, p->ProbPrices) :
1616 LitEnc_GetPrice(probs, curByte, p->ProbPrices));
1618 if (litPrice < nextOpt->price)
1620 nextOpt->price = litPrice;
1627 repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[state]);
1629 numAvailFull = p->numAvail;
1631 unsigned temp = kNumOpts - 1 - cur;
1632 if (numAvailFull > temp)
1633 numAvailFull = (UInt32)temp;
1637 // ---------- SHORT_REP ----------
1638 if (IsLitState(state)) // 18.new
1639 if (matchByte == curByte)
1640 if (repMatchPrice < nextOpt->price) // 18.new
1641 // if (numAvailFull < 2 || data[1] != *(data - reps[0] + 1))
1643 // nextOpt->price >= kInfinityPrice ||
1644 nextOpt->len < 2 // we can check nextOpt->len, if skip items are not allowed in p->opt
1645 || (nextOpt->dist != 0
1646 // && nextOpt->extra <= 1 // 17.old
1650 UInt32 shortRepPrice = repMatchPrice + GetPrice_ShortRep(p, state, posState);
1651 // if (shortRepPrice <= nextOpt->price) // 17.old
1652 if (shortRepPrice < nextOpt->price) // 18.new
1654 nextOpt->price = shortRepPrice;
1656 MakeAs_ShortRep(nextOpt)
1661 if (numAvailFull < 2)
1663 numAvail = (numAvailFull <= p->numFastBytes ? numAvailFull : p->numFastBytes);
1665 // numAvail <= p->numFastBytes
1667 // ---------- LIT : REP_0 ----------
1670 && litPrice != 0 // 18.new
1671 && matchByte != curByte
1672 && numAvailFull > 2)
1674 const Byte *data2 = data - reps[0];
1675 if (data[1] == data2[1] && data[2] == data2[2])
1678 unsigned limit = p->numFastBytes + 1;
1679 if (limit > numAvailFull)
1680 limit = numAvailFull;
1681 for (len = 3; len < limit && data[len] == data2[len]; len++)
1685 unsigned state2 = kLiteralNextStates[state];
1686 unsigned posState2 = (position + 1) & p->pbMask;
1687 UInt32 price = litPrice + GetPrice_Rep_0(p, state2, posState2);
1689 unsigned offset = cur + len;
1699 // price2 = price + GetPrice_Len_Rep_0(p, len, state2, posState2);
1700 price2 = price + GET_PRICE_LEN(&p->repLenEnc, posState2, len);
1702 opt = &p->opt[offset];
1704 if (price2 < opt->price)
1706 opt->price = price2;
1707 opt->len = (UInt32)len;
1712 // while (len >= 3);
1718 startLen = 2; /* speed optimization */
1721 // ---------- REP ----------
1722 unsigned repIndex = 0; // 17.old
1723 // unsigned repIndex = IsLitState(state) ? 0 : 1; // 18.notused
1724 for (; repIndex < LZMA_NUM_REPS; repIndex++)
1728 const Byte *data2 = data - reps[repIndex];
1729 if (data[0] != data2[0] || data[1] != data2[1])
1732 for (len = 2; len < numAvail && data[len] == data2[len]; len++)
1735 // if (len < startLen) continue; // 18.new: speed optimization
1738 unsigned offset = cur + len;
1743 unsigned len2 = len;
1744 price = repMatchPrice + GetPrice_PureRep(p, repIndex, state, posState);
1747 UInt32 price2 = price + GET_PRICE_LEN(&p->repLenEnc, posState, len2);
1748 COptimal *opt = &p->opt[cur + len2];
1749 if (price2 < opt->price)
1751 opt->price = price2;
1752 opt->len = (UInt32)len2;
1753 opt->dist = (UInt32)repIndex;
1757 while (--len2 >= 2);
1760 if (repIndex == 0) startLen = len + 1; // 17.old
1761 // startLen = len + 1; // 18.new
1765 // ---------- REP : LIT : REP_0 ----------
1766 // numFastBytes + 1 + numFastBytes
1768 unsigned len2 = len + 1;
1769 unsigned limit = len2 + p->numFastBytes;
1770 if (limit > numAvailFull)
1771 limit = numAvailFull;
1775 if (data[len2 - 2] == data2[len2 - 2])
1776 if (data[len2 - 1] == data2[len2 - 1])
1778 unsigned state2 = kRepNextStates[state];
1779 unsigned posState2 = (position + len) & p->pbMask;
1780 price += GET_PRICE_LEN(&p->repLenEnc, posState, len)
1781 + GET_PRICE_0(p->isMatch[state2][posState2])
1782 + LitEnc_Matched_GetPrice(LIT_PROBS(position + len, data[(size_t)len - 1]),
1783 data[len], data2[len], p->ProbPrices);
1785 // state2 = kLiteralNextStates[state2];
1786 state2 = kState_LitAfterRep;
1787 posState2 = (posState2 + 1) & p->pbMask;
1790 price += GetPrice_Rep_0(p, state2, posState2);
1792 for (; len2 < limit && data[len2] == data2[len2]; len2++)
1799 unsigned offset = cur + len + len2;
1808 // price2 = price + GetPrice_Len_Rep_0(p, len2, state2, posState2);
1809 price2 = price + GET_PRICE_LEN(&p->repLenEnc, posState2, len2);
1811 opt = &p->opt[offset];
1813 if (price2 < opt->price)
1815 opt->price = price2;
1816 opt->len = (UInt32)len2;
1817 opt->extra = (CExtra)(len + 1);
1818 opt->dist = (UInt32)repIndex;
1821 // while (len2 >= 3);
1830 // ---------- MATCH ----------
1831 /* for (unsigned len = 2; len <= newLen; len++) */
1832 if (newLen > numAvail)
1835 for (numPairs = 0; newLen > MATCHES[numPairs]; numPairs += 2);
1836 MATCHES[numPairs] = (UInt32)newLen;
1840 // startLen = 2; /* speed optimization */
1842 if (newLen >= startLen)
1844 UInt32 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[state]);
1846 unsigned offs, posSlot, len;
1849 unsigned offset = cur + newLen;
1855 while (startLen > MATCHES[offs])
1857 dist = MATCHES[(size_t)offs + 1];
1859 // if (dist >= kNumFullDistances)
1860 GetPosSlot2(dist, posSlot)
1862 for (len = /*2*/ startLen; ; len++)
1864 UInt32 price = normalMatchPrice + GET_PRICE_LEN(&p->lenEnc, posState, len);
1867 unsigned lenNorm = len - 2;
1868 lenNorm = GetLenToPosState2(lenNorm);
1869 if (dist < kNumFullDistances)
1870 price += p->distancesPrices[lenNorm][dist & (kNumFullDistances - 1)];
1872 price += p->posSlotPrices[lenNorm][posSlot] + p->alignPrices[dist & kAlignMask];
1874 opt = &p->opt[cur + len];
1875 if (price < opt->price)
1878 opt->len = (UInt32)len;
1879 opt->dist = dist + LZMA_NUM_REPS;
1884 if (len == MATCHES[offs])
1886 // if (p->_maxMode) {
1887 // MATCH : LIT : REP_0
1889 const Byte *data2 = data - dist - 1;
1890 unsigned len2 = len + 1;
1891 unsigned limit = len2 + p->numFastBytes;
1892 if (limit > numAvailFull)
1893 limit = numAvailFull;
1897 if (data[len2 - 2] == data2[len2 - 2])
1898 if (data[len2 - 1] == data2[len2 - 1])
1900 for (; len2 < limit && data[len2] == data2[len2]; len2++)
1907 unsigned state2 = kMatchNextStates[state];
1908 unsigned posState2 = (position + len) & p->pbMask;
1910 price += GET_PRICE_0(p->isMatch[state2][posState2]);
1911 price += LitEnc_Matched_GetPrice(LIT_PROBS(position + len, data[(size_t)len - 1]),
1912 data[len], data2[len], p->ProbPrices);
1914 // state2 = kLiteralNextStates[state2];
1915 state2 = kState_LitAfterMatch;
1917 posState2 = (posState2 + 1) & p->pbMask;
1918 price += GetPrice_Rep_0(p, state2, posState2);
1920 offset = cur + len + len2;
1929 // price2 = price + GetPrice_Len_Rep_0(p, len2, state2, posState2);
1930 price2 = price + GET_PRICE_LEN(&p->repLenEnc, posState2, len2);
1931 opt = &p->opt[offset];
1933 if (price2 < opt->price)
1935 opt->price = price2;
1936 opt->len = (UInt32)len2;
1937 opt->extra = (CExtra)(len + 1);
1938 opt->dist = dist + LZMA_NUM_REPS;
1941 // while (len2 >= 3);
1947 if (offs == numPairs)
1949 dist = MATCHES[(size_t)offs + 1];
1950 // if (dist >= kNumFullDistances)
1951 GetPosSlot2(dist, posSlot)
1958 p->opt[last].price = kInfinityPrice;
1961 return Backward(p, cur);
1966 #define ChangePair(smallDist, bigDist) (((bigDist) >> 7) > (smallDist))
1970 static unsigned GetOptimumFast(CLzmaEnc *p)
1972 UInt32 numAvail, mainDist;
1973 unsigned mainLen, numPairs, repIndex, repLen, i;
1976 if (p->additionalOffset == 0)
1977 mainLen = ReadMatchDistances(p, &numPairs);
1980 mainLen = p->longestMatchLen;
1981 numPairs = p->numPairs;
1984 numAvail = p->numAvail;
1985 p->backRes = MARK_LIT;
1988 // if (mainLen < 2 && p->state == 0) return 1; // 18.06.notused
1989 if (numAvail > LZMA_MATCH_LEN_MAX)
1990 numAvail = LZMA_MATCH_LEN_MAX;
1991 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1992 repLen = repIndex = 0;
1994 for (i = 0; i < LZMA_NUM_REPS; i++)
1997 const Byte *data2 = data - p->reps[i];
1998 if (data[0] != data2[0] || data[1] != data2[1])
2000 for (len = 2; len < numAvail && data[len] == data2[len]; len++)
2002 if (len >= p->numFastBytes)
2004 p->backRes = (UInt32)i;
2005 MOVE_POS(p, len - 1)
2015 if (mainLen >= p->numFastBytes)
2017 p->backRes = p->matches[(size_t)numPairs - 1] + LZMA_NUM_REPS;
2018 MOVE_POS(p, mainLen - 1)
2022 mainDist = 0; /* for GCC */
2026 mainDist = p->matches[(size_t)numPairs - 1];
2027 while (numPairs > 2)
2030 if (mainLen != p->matches[(size_t)numPairs - 4] + 1)
2032 dist2 = p->matches[(size_t)numPairs - 3];
2033 if (!ChangePair(dist2, mainDist))
2039 if (mainLen == 2 && mainDist >= 0x80)
2044 if ( repLen + 1 >= mainLen
2045 || (repLen + 2 >= mainLen && mainDist >= (1 << 9))
2046 || (repLen + 3 >= mainLen && mainDist >= (1 << 15)))
2048 p->backRes = (UInt32)repIndex;
2049 MOVE_POS(p, repLen - 1)
2053 if (mainLen < 2 || numAvail <= 2)
2057 unsigned len1 = ReadMatchDistances(p, &p->numPairs);
2058 p->longestMatchLen = len1;
2062 UInt32 newDist = p->matches[(size_t)p->numPairs - 1];
2063 if ( (len1 >= mainLen && newDist < mainDist)
2064 || (len1 == mainLen + 1 && !ChangePair(mainDist, newDist))
2065 || (len1 > mainLen + 1)
2066 || (len1 + 1 >= mainLen && mainLen >= 3 && ChangePair(newDist, mainDist)))
2071 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
2073 for (i = 0; i < LZMA_NUM_REPS; i++)
2075 unsigned len, limit;
2076 const Byte *data2 = data - p->reps[i];
2077 if (data[0] != data2[0] || data[1] != data2[1])
2079 limit = mainLen - 1;
2080 for (len = 2;; len++)
2084 if (data[len] != data2[len])
2089 p->backRes = mainDist + LZMA_NUM_REPS;
2092 MOVE_POS(p, mainLen - 2)
2100 static void WriteEndMarker(CLzmaEnc *p, unsigned posState)
2103 range = p->rc.range;
2105 UInt32 ttt, newBound;
2106 CLzmaProb *prob = &p->isMatch[p->state][posState];
2107 RC_BIT_PRE(&p->rc, prob)
2108 RC_BIT_1(&p->rc, prob)
2109 prob = &p->isRep[p->state];
2110 RC_BIT_PRE(&p->rc, prob)
2111 RC_BIT_0(&p->rc, prob)
2113 p->state = kMatchNextStates[p->state];
2115 p->rc.range = range;
2116 LenEnc_Encode(&p->lenProbs, &p->rc, 0, posState);
2117 range = p->rc.range;
2120 // RcTree_Encode_PosSlot(&p->rc, p->posSlotEncoder[0], (1 << kNumPosSlotBits) - 1);
2121 CLzmaProb *probs = p->posSlotEncoder[0];
2125 UInt32 ttt, newBound;
2126 RC_BIT_PRE(p, probs + m)
2127 RC_BIT_1(&p->rc, probs + m)
2130 while (m < (1 << kNumPosSlotBits));
2133 // RangeEnc_EncodeDirectBits(&p->rc, ((UInt32)1 << (30 - kNumAlignBits)) - 1, 30 - kNumAlignBits); UInt32 range = p->range;
2134 unsigned numBits = 30 - kNumAlignBits;
2145 // RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, kAlignMask);
2146 CLzmaProb *probs = p->posAlignEncoder;
2150 UInt32 ttt, newBound;
2151 RC_BIT_PRE(p, probs + m)
2152 RC_BIT_1(&p->rc, probs + m)
2155 while (m < kAlignTableSize);
2157 p->rc.range = range;
2161 static SRes CheckErrors(CLzmaEnc *p)
2163 if (p->result != SZ_OK)
2165 if (p->rc.res != SZ_OK)
2166 p->result = SZ_ERROR_WRITE;
2172 ( // p->matchFinderMt.failure_LZ_LZ ||
2173 p->matchFinderMt.failure_LZ_BT))
2176 p->result = MY_HRES_ERROR_INTERNAL_ERROR;
2177 // printf("\nCheckErrors p->matchFinderMt.failureLZ\n");
2181 if (MFB.result != SZ_OK)
2182 p->result = SZ_ERROR_READ;
2184 if (p->result != SZ_OK)
2190 Z7_NO_INLINE static SRes Flush(CLzmaEnc *p, UInt32 nowPos)
2192 /* ReleaseMFStream(); */
2194 if (p->writeEndMark)
2195 WriteEndMarker(p, nowPos & p->pbMask);
2196 RangeEnc_FlushData(&p->rc);
2197 RangeEnc_FlushStream(&p->rc);
2198 return CheckErrors(p);
2202 Z7_NO_INLINE static void FillAlignPrices(CLzmaEnc *p)
2205 const CProbPrice *ProbPrices = p->ProbPrices;
2206 const CLzmaProb *probs = p->posAlignEncoder;
2207 // p->alignPriceCount = 0;
2208 for (i = 0; i < kAlignTableSize / 2; i++)
2215 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[m], bit); m = (m << 1) + bit;
2216 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[m], bit); m = (m << 1) + bit;
2217 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[m], bit); m = (m << 1) + bit;
2219 p->alignPrices[i ] = price + GET_PRICEa_0(prob);
2220 p->alignPrices[i + 8] = price + GET_PRICEa_1(prob);
2221 // p->alignPrices[i] = RcTree_ReverseGetPrice(p->posAlignEncoder, kNumAlignBits, i, p->ProbPrices);
2226 Z7_NO_INLINE static void FillDistancesPrices(CLzmaEnc *p)
2228 // int y; for (y = 0; y < 100; y++) {
2230 UInt32 tempPrices[kNumFullDistances];
2233 const CProbPrice *ProbPrices = p->ProbPrices;
2234 p->matchPriceCount = 0;
2236 for (i = kStartPosModelIndex / 2; i < kNumFullDistances / 2; i++)
2238 unsigned posSlot = GetPosSlot1(i);
2239 unsigned footerBits = (posSlot >> 1) - 1;
2240 unsigned base = ((2 | (posSlot & 1)) << footerBits);
2241 const CLzmaProb *probs = p->posEncoders + (size_t)base * 2;
2242 // tempPrices[i] = RcTree_ReverseGetPrice(p->posEncoders + base, footerBits, i - base, p->ProbPrices);
2246 unsigned offset = (unsigned)1 << footerBits;
2252 unsigned bit = sym & 1;
2254 price += GET_PRICEa(probs[m], bit);
2257 while (--footerBits);
2260 unsigned prob = probs[m];
2261 tempPrices[base ] = price + GET_PRICEa_0(prob);
2262 tempPrices[base + offset] = price + GET_PRICEa_1(prob);
2266 for (lps = 0; lps < kNumLenToPosStates; lps++)
2269 unsigned distTableSize2 = (p->distTableSize + 1) >> 1;
2270 UInt32 *posSlotPrices = p->posSlotPrices[lps];
2271 const CLzmaProb *probs = p->posSlotEncoder[lps];
2273 for (slot = 0; slot < distTableSize2; slot++)
2275 // posSlotPrices[slot] = RcTree_GetPrice(encoder, kNumPosSlotBits, slot, p->ProbPrices);
2278 unsigned sym = slot + (1 << (kNumPosSlotBits - 1));
2280 bit = sym & 1; sym >>= 1; price = GET_PRICEa(probs[sym], bit);
2281 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[sym], bit);
2282 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[sym], bit);
2283 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[sym], bit);
2284 bit = sym & 1; sym >>= 1; price += GET_PRICEa(probs[sym], bit);
2285 prob = probs[(size_t)slot + (1 << (kNumPosSlotBits - 1))];
2286 posSlotPrices[(size_t)slot * 2 ] = price + GET_PRICEa_0(prob);
2287 posSlotPrices[(size_t)slot * 2 + 1] = price + GET_PRICEa_1(prob);
2291 UInt32 delta = ((UInt32)((kEndPosModelIndex / 2 - 1) - kNumAlignBits) << kNumBitPriceShiftBits);
2292 for (slot = kEndPosModelIndex / 2; slot < distTableSize2; slot++)
2294 posSlotPrices[(size_t)slot * 2 ] += delta;
2295 posSlotPrices[(size_t)slot * 2 + 1] += delta;
2296 delta += ((UInt32)1 << kNumBitPriceShiftBits);
2301 UInt32 *dp = p->distancesPrices[lps];
2303 dp[0] = posSlotPrices[0];
2304 dp[1] = posSlotPrices[1];
2305 dp[2] = posSlotPrices[2];
2306 dp[3] = posSlotPrices[3];
2308 for (i = 4; i < kNumFullDistances; i += 2)
2310 UInt32 slotPrice = posSlotPrices[GetPosSlot1(i)];
2311 dp[i ] = slotPrice + tempPrices[i];
2312 dp[i + 1] = slotPrice + tempPrices[i + 1];
2321 static void LzmaEnc_Construct(CLzmaEnc *p)
2323 RangeEnc_Construct(&p->rc);
2324 MatchFinder_Construct(&MFB);
2327 p->matchFinderMt.MatchFinder = &MFB;
2328 MatchFinderMt_Construct(&p->matchFinderMt);
2332 CLzmaEncProps props;
2333 LzmaEncProps_Init(&props);
2334 LzmaEnc_SetProps((CLzmaEncHandle)(void *)p, &props);
2337 #ifndef LZMA_LOG_BSR
2338 LzmaEnc_FastPosInit(p->g_FastPos);
2341 LzmaEnc_InitPriceTables(p->ProbPrices);
2343 p->saveState.litProbs = NULL;
2346 CLzmaEncHandle LzmaEnc_Create(ISzAllocPtr alloc)
2349 p = ISzAlloc_Alloc(alloc, sizeof(CLzmaEnc));
2351 LzmaEnc_Construct((CLzmaEnc *)p);
2355 static void LzmaEnc_FreeLits(CLzmaEnc *p, ISzAllocPtr alloc)
2357 ISzAlloc_Free(alloc, p->litProbs);
2358 ISzAlloc_Free(alloc, p->saveState.litProbs);
2360 p->saveState.litProbs = NULL;
2363 static void LzmaEnc_Destruct(CLzmaEnc *p, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2366 MatchFinderMt_Destruct(&p->matchFinderMt, allocBig);
2369 MatchFinder_Free(&MFB, allocBig);
2370 LzmaEnc_FreeLits(p, alloc);
2371 RangeEnc_Free(&p->rc, alloc);
2374 void LzmaEnc_Destroy(CLzmaEncHandle p, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2377 LzmaEnc_Destruct(p, alloc, allocBig);
2378 ISzAlloc_Free(alloc, p);
2383 static SRes LzmaEnc_CodeOneBlock(CLzmaEnc *p, UInt32 maxPackSize, UInt32 maxUnpackSize)
2385 UInt32 nowPos32, startPos32;
2391 RINOK(MatchFinderMt_InitMt(&p->matchFinderMt))
2394 p->matchFinder.Init(p->matchFinderObj);
2400 RINOK(CheckErrors(p))
2402 nowPos32 = (UInt32)p->nowPos64;
2403 startPos32 = nowPos32;
2405 if (p->nowPos64 == 0)
2409 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)
2410 return Flush(p, nowPos32);
2411 ReadMatchDistances(p, &numPairs);
2412 RangeEnc_EncodeBit_0(&p->rc, &p->isMatch[kState_Start][0]);
2413 // p->state = kLiteralNextStates[p->state];
2414 curByte = *(p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset);
2415 LitEnc_Encode(&p->rc, p->litProbs, curByte);
2416 p->additionalOffset--;
2420 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) != 0)
2425 unsigned len, posState;
2426 UInt32 range, ttt, newBound;
2430 len = GetOptimumFast(p);
2433 unsigned oci = p->optCur;
2434 if (p->optEnd == oci)
2435 len = GetOptimum(p, nowPos32);
2438 const COptimal *opt = &p->opt[oci];
2440 p->backRes = opt->dist;
2441 p->optCur = oci + 1;
2445 posState = (unsigned)nowPos32 & p->pbMask;
2446 range = p->rc.range;
2447 probs = &p->isMatch[p->state][posState];
2449 RC_BIT_PRE(&p->rc, probs)
2454 printf("\n pos = %6X, len = %3u pos = %6u", nowPos32, len, dist);
2457 if (dist == MARK_LIT)
2463 RC_BIT_0(&p->rc, probs)
2464 p->rc.range = range;
2465 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
2466 probs = LIT_PROBS(nowPos32, *(data - 1));
2469 p->state = kLiteralNextStates[state];
2470 if (IsLitState(state))
2471 LitEnc_Encode(&p->rc, probs, curByte);
2473 LitEnc_EncodeMatched(&p->rc, probs, curByte, *(data - p->reps[0]));
2477 RC_BIT_1(&p->rc, probs)
2478 probs = &p->isRep[p->state];
2479 RC_BIT_PRE(&p->rc, probs)
2481 if (dist < LZMA_NUM_REPS)
2483 RC_BIT_1(&p->rc, probs)
2484 probs = &p->isRepG0[p->state];
2485 RC_BIT_PRE(&p->rc, probs)
2488 RC_BIT_0(&p->rc, probs)
2489 probs = &p->isRep0Long[p->state][posState];
2490 RC_BIT_PRE(&p->rc, probs)
2493 RC_BIT_1_BASE(&p->rc, probs)
2497 RC_BIT_0_BASE(&p->rc, probs)
2498 p->state = kShortRepNextStates[p->state];
2503 RC_BIT_1(&p->rc, probs)
2504 probs = &p->isRepG1[p->state];
2505 RC_BIT_PRE(&p->rc, probs)
2508 RC_BIT_0_BASE(&p->rc, probs)
2513 RC_BIT_1(&p->rc, probs)
2514 probs = &p->isRepG2[p->state];
2515 RC_BIT_PRE(&p->rc, probs)
2518 RC_BIT_0_BASE(&p->rc, probs)
2523 RC_BIT_1_BASE(&p->rc, probs)
2525 p->reps[3] = p->reps[2];
2527 p->reps[2] = p->reps[1];
2529 p->reps[1] = p->reps[0];
2535 p->rc.range = range;
2539 LenEnc_Encode(&p->repLenProbs, &p->rc, len - LZMA_MATCH_LEN_MIN, posState);
2540 --p->repLenEncCounter;
2541 p->state = kRepNextStates[p->state];
2547 RC_BIT_0(&p->rc, probs)
2548 p->rc.range = range;
2549 p->state = kMatchNextStates[p->state];
2551 LenEnc_Encode(&p->lenProbs, &p->rc, len - LZMA_MATCH_LEN_MIN, posState);
2552 // --p->lenEnc.counter;
2554 dist -= LZMA_NUM_REPS;
2555 p->reps[3] = p->reps[2];
2556 p->reps[2] = p->reps[1];
2557 p->reps[1] = p->reps[0];
2558 p->reps[0] = dist + 1;
2560 p->matchPriceCount++;
2561 GetPosSlot(dist, posSlot)
2562 // RcTree_Encode_PosSlot(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], posSlot);
2564 UInt32 sym = (UInt32)posSlot + (1 << kNumPosSlotBits);
2565 range = p->rc.range;
2566 probs = p->posSlotEncoder[GetLenToPosState(len)];
2569 CLzmaProb *prob = probs + (sym >> kNumPosSlotBits);
2570 UInt32 bit = (sym >> (kNumPosSlotBits - 1)) & 1;
2572 RC_BIT(&p->rc, prob, bit)
2574 while (sym < (1 << kNumPosSlotBits * 2));
2575 p->rc.range = range;
2578 if (dist >= kStartPosModelIndex)
2580 unsigned footerBits = ((posSlot >> 1) - 1);
2582 if (dist < kNumFullDistances)
2584 unsigned base = ((2 | (posSlot & 1)) << footerBits);
2585 RcTree_ReverseEncode(&p->rc, p->posEncoders + base, footerBits, (unsigned)(dist /* - base */));
2589 UInt32 pos2 = (dist | 0xF) << (32 - footerBits);
2590 range = p->rc.range;
2591 // RangeEnc_EncodeDirectBits(&p->rc, posReduced >> kNumAlignBits, footerBits - kNumAlignBits);
2596 p->rc.low += range & (0 - ((dist >> --footerBits) & 1));
2599 while (footerBits > kNumAlignBits);
2604 p->rc.low += range & (0 - (pos2 >> 31));
2608 while (pos2 != 0xF0000000);
2611 // RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, posReduced & kAlignMask);
2616 bit = dist & 1; dist >>= 1; RC_BIT(&p->rc, p->posAlignEncoder + m, bit) m = (m << 1) + bit;
2617 bit = dist & 1; dist >>= 1; RC_BIT(&p->rc, p->posAlignEncoder + m, bit) m = (m << 1) + bit;
2618 bit = dist & 1; dist >>= 1; RC_BIT(&p->rc, p->posAlignEncoder + m, bit) m = (m << 1) + bit;
2619 bit = dist & 1; RC_BIT(&p->rc, p->posAlignEncoder + m, bit)
2620 p->rc.range = range;
2621 // p->alignPriceCount++;
2628 nowPos32 += (UInt32)len;
2629 p->additionalOffset -= len;
2631 if (p->additionalOffset == 0)
2638 if (p->alignPriceCount >= 16) // kAlignTableSize
2640 if (p->matchPriceCount >= 128)
2641 FillDistancesPrices(p);
2642 if (p->lenEnc.counter <= 0)
2643 LenPriceEnc_UpdateTables(&p->lenEnc, 1 << p->pb, &p->lenProbs, p->ProbPrices);
2645 if (p->matchPriceCount >= 64)
2648 // { int y; for (y = 0; y < 100; y++) {
2649 FillDistancesPrices(p);
2651 LenPriceEnc_UpdateTables(&p->lenEnc, (unsigned)1 << p->pb, &p->lenProbs, p->ProbPrices);
2653 if (p->repLenEncCounter <= 0)
2655 p->repLenEncCounter = REP_LEN_COUNT;
2656 LenPriceEnc_UpdateTables(&p->repLenEnc, (unsigned)1 << p->pb, &p->repLenProbs, p->ProbPrices);
2660 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)
2662 processed = nowPos32 - startPos32;
2666 if (processed + kNumOpts + 300 >= maxUnpackSize
2667 || RangeEnc_GetProcessed_sizet(&p->rc) + kPackReserve >= maxPackSize)
2670 else if (processed >= (1 << 17))
2672 p->nowPos64 += nowPos32 - startPos32;
2673 return CheckErrors(p);
2678 p->nowPos64 += nowPos32 - startPos32;
2679 return Flush(p, nowPos32);
2684 #define kBigHashDicLimit ((UInt32)1 << 24)
2686 static SRes LzmaEnc_Alloc(CLzmaEnc *p, UInt32 keepWindowSize, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2688 UInt32 beforeSize = kNumOpts;
2691 if (!RangeEnc_Alloc(&p->rc, alloc))
2692 return SZ_ERROR_MEM;
2695 p->mtMode = (p->multiThread && !p->fastMode && (MFB.btMode != 0));
2699 const unsigned lclp = p->lc + p->lp;
2700 if (!p->litProbs || !p->saveState.litProbs || p->lclp != lclp)
2702 LzmaEnc_FreeLits(p, alloc);
2703 p->litProbs = (CLzmaProb *)ISzAlloc_Alloc(alloc, ((size_t)0x300 * sizeof(CLzmaProb)) << lclp);
2704 p->saveState.litProbs = (CLzmaProb *)ISzAlloc_Alloc(alloc, ((size_t)0x300 * sizeof(CLzmaProb)) << lclp);
2705 if (!p->litProbs || !p->saveState.litProbs)
2707 LzmaEnc_FreeLits(p, alloc);
2708 return SZ_ERROR_MEM;
2714 MFB.bigHash = (Byte)(p->dictSize > kBigHashDicLimit ? 1 : 0);
2717 dictSize = p->dictSize;
2718 if (dictSize == ((UInt32)2 << 30) ||
2719 dictSize == ((UInt32)3 << 30))
2721 /* 21.03 : here we reduce the dictionary for 2 reasons:
2722 1) we don't want 32-bit back_distance matches in decoder for 2 GB dictionary.
2723 2) we want to elimate useless last MatchFinder_Normalize3() for corner cases,
2724 where data size is aligned for 1 GB: 5/6/8 GB.
2725 That reducing must be >= 1 for such corner cases. */
2729 if (beforeSize + dictSize < keepWindowSize)
2730 beforeSize = keepWindowSize - dictSize;
2732 /* in worst case we can look ahead for
2733 max(LZMA_MATCH_LEN_MAX, numFastBytes + 1 + numFastBytes) bytes.
2734 we send larger value for (keepAfter) to MantchFinder_Create():
2735 (numFastBytes + LZMA_MATCH_LEN_MAX + 1)
2741 RINOK(MatchFinderMt_Create(&p->matchFinderMt, dictSize, beforeSize,
2742 p->numFastBytes, LZMA_MATCH_LEN_MAX + 1 /* 18.04 */
2744 p->matchFinderObj = &p->matchFinderMt;
2745 MFB.bigHash = (Byte)(MFB.hashMask >= 0xFFFFFF ? 1 : 0);
2746 MatchFinderMt_CreateVTable(&p->matchFinderMt, &p->matchFinder);
2751 if (!MatchFinder_Create(&MFB, dictSize, beforeSize,
2752 p->numFastBytes, LZMA_MATCH_LEN_MAX + 1 /* 21.03 */
2754 return SZ_ERROR_MEM;
2755 p->matchFinderObj = &MFB;
2756 MatchFinder_CreateVTable(&MFB, &p->matchFinder);
2762 static void LzmaEnc_Init(CLzmaEnc *p)
2771 RangeEnc_Init(&p->rc);
2773 for (i = 0; i < (1 << kNumAlignBits); i++)
2774 p->posAlignEncoder[i] = kProbInitValue;
2776 for (i = 0; i < kNumStates; i++)
2779 for (j = 0; j < LZMA_NUM_PB_STATES_MAX; j++)
2781 p->isMatch[i][j] = kProbInitValue;
2782 p->isRep0Long[i][j] = kProbInitValue;
2784 p->isRep[i] = kProbInitValue;
2785 p->isRepG0[i] = kProbInitValue;
2786 p->isRepG1[i] = kProbInitValue;
2787 p->isRepG2[i] = kProbInitValue;
2791 for (i = 0; i < kNumLenToPosStates; i++)
2793 CLzmaProb *probs = p->posSlotEncoder[i];
2795 for (j = 0; j < (1 << kNumPosSlotBits); j++)
2796 probs[j] = kProbInitValue;
2800 for (i = 0; i < kNumFullDistances; i++)
2801 p->posEncoders[i] = kProbInitValue;
2805 const size_t num = (size_t)0x300 << (p->lp + p->lc);
2807 CLzmaProb *probs = p->litProbs;
2808 for (k = 0; k < num; k++)
2809 probs[k] = kProbInitValue;
2813 LenEnc_Init(&p->lenProbs);
2814 LenEnc_Init(&p->repLenProbs);
2820 for (i = 0; i < kNumOpts; i++)
2821 p->opt[i].price = kInfinityPrice;
2824 p->additionalOffset = 0;
2826 p->pbMask = ((unsigned)1 << p->pb) - 1;
2827 p->lpMask = ((UInt32)0x100 << p->lp) - ((unsigned)0x100 >> p->lc);
2829 // p->mf_Failure = False;
2833 static void LzmaEnc_InitPrices(CLzmaEnc *p)
2837 FillDistancesPrices(p);
2841 p->lenEnc.tableSize =
2842 p->repLenEnc.tableSize =
2843 p->numFastBytes + 1 - LZMA_MATCH_LEN_MIN;
2845 p->repLenEncCounter = REP_LEN_COUNT;
2847 LenPriceEnc_UpdateTables(&p->lenEnc, (unsigned)1 << p->pb, &p->lenProbs, p->ProbPrices);
2848 LenPriceEnc_UpdateTables(&p->repLenEnc, (unsigned)1 << p->pb, &p->repLenProbs, p->ProbPrices);
2851 static SRes LzmaEnc_AllocAndInit(CLzmaEnc *p, UInt32 keepWindowSize, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2854 for (i = kEndPosModelIndex / 2; i < kDicLogSizeMax; i++)
2855 if (p->dictSize <= ((UInt32)1 << i))
2857 p->distTableSize = i * 2;
2859 p->finished = False;
2863 RINOK(LzmaEnc_Alloc(p, keepWindowSize, alloc, allocBig))
2865 LzmaEnc_InitPrices(p);
2869 static SRes LzmaEnc_Prepare(CLzmaEncHandle p,
2870 ISeqOutStreamPtr outStream,
2871 ISeqInStreamPtr inStream,
2872 ISzAllocPtr alloc, ISzAllocPtr allocBig)
2875 MatchFinder_SET_STREAM(&MFB, inStream)
2876 p->rc.outStream = outStream;
2877 return LzmaEnc_AllocAndInit(p, 0, alloc, allocBig);
2880 SRes LzmaEnc_PrepareForLzma2(CLzmaEncHandle p,
2881 ISeqInStreamPtr inStream, UInt32 keepWindowSize,
2882 ISzAllocPtr alloc, ISzAllocPtr allocBig)
2885 MatchFinder_SET_STREAM(&MFB, inStream)
2886 return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);
2889 SRes LzmaEnc_MemPrepare(CLzmaEncHandle p,
2890 const Byte *src, SizeT srcLen,
2891 UInt32 keepWindowSize,
2892 ISzAllocPtr alloc, ISzAllocPtr allocBig)
2895 MatchFinder_SET_DIRECT_INPUT_BUF(&MFB, src, srcLen)
2896 LzmaEnc_SetDataSize(p, srcLen);
2897 return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);
2900 void LzmaEnc_Finish(CLzmaEncHandle p)
2905 MatchFinderMt_ReleaseStream(&p->matchFinderMt);
2918 } CLzmaEnc_SeqOutStreamBuf;
2920 static size_t SeqOutStreamBuf_Write(ISeqOutStreamPtr pp, const void *data, size_t size)
2922 Z7_CONTAINER_FROM_VTBL_TO_DECL_VAR_pp_vt_p(CLzmaEnc_SeqOutStreamBuf)
2930 memcpy(p->data, data, size);
2939 UInt32 LzmaEnc_GetNumAvailableBytes(CLzmaEncHandle p)
2941 GET_const_CLzmaEnc_p
2942 return p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);
2946 const Byte *LzmaEnc_GetCurBuf(CLzmaEncHandle p)
2948 // GET_const_CLzmaEnc_p
2949 return p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
2953 // (desiredPackSize == 0) is not allowed
2954 SRes LzmaEnc_CodeOneMemBlock(CLzmaEncHandle p, BoolInt reInit,
2955 Byte *dest, size_t *destLen, UInt32 desiredPackSize, UInt32 *unpackSize)
2960 CLzmaEnc_SeqOutStreamBuf outStream;
2962 outStream.vt.Write = SeqOutStreamBuf_Write;
2963 outStream.data = dest;
2964 outStream.rem = *destLen;
2965 outStream.overflow = False;
2967 p->writeEndMark = False;
2968 p->finished = False;
2973 LzmaEnc_InitPrices(p);
2974 RangeEnc_Init(&p->rc);
2975 p->rc.outStream = &outStream.vt;
2976 nowPos64 = p->nowPos64;
2978 res = LzmaEnc_CodeOneBlock(p, desiredPackSize, *unpackSize);
2980 *unpackSize = (UInt32)(p->nowPos64 - nowPos64);
2981 *destLen -= outStream.rem;
2982 if (outStream.overflow)
2983 return SZ_ERROR_OUTPUT_EOF;
2990 static SRes LzmaEnc_Encode2(CLzmaEnc *p, ICompressProgressPtr progress)
2995 Byte allocaDummy[0x300];
2997 allocaDummy[1] = allocaDummy[0];
3002 res = LzmaEnc_CodeOneBlock(p, 0, 0);
3003 if (res != SZ_OK || p->finished)
3007 res = ICompressProgress_Progress(progress, p->nowPos64, RangeEnc_GetProcessed(&p->rc));
3010 res = SZ_ERROR_PROGRESS;
3016 LzmaEnc_Finish((CLzmaEncHandle)(void *)p);
3019 if (res == SZ_OK && !Inline_MatchFinder_IsFinishedOK(&MFB))
3020 res = SZ_ERROR_FAIL;
3028 SRes LzmaEnc_Encode(CLzmaEncHandle p, ISeqOutStreamPtr outStream, ISeqInStreamPtr inStream, ICompressProgressPtr progress,
3029 ISzAllocPtr alloc, ISzAllocPtr allocBig)
3032 RINOK(LzmaEnc_Prepare(p, outStream, inStream, alloc, allocBig))
3033 return LzmaEnc_Encode2(p, progress);
3037 SRes LzmaEnc_WriteProperties(CLzmaEncHandle p, Byte *props, SizeT *size)
3039 if (*size < LZMA_PROPS_SIZE)
3040 return SZ_ERROR_PARAM;
3041 *size = LZMA_PROPS_SIZE;
3044 const UInt32 dictSize = p->dictSize;
3046 props[0] = (Byte)((p->pb * 5 + p->lp) * 9 + p->lc);
3048 // we write aligned dictionary value to properties for lzma decoder
3049 if (dictSize >= ((UInt32)1 << 21))
3051 const UInt32 kDictMask = ((UInt32)1 << 20) - 1;
3052 v = (dictSize + kDictMask) & ~kDictMask;
3058 unsigned i = 11 * 2;
3061 v = (UInt32)(2 + (i & 1)) << (i >> 1);
3064 while (v < dictSize);
3067 SetUi32(props + 1, v)
3073 unsigned LzmaEnc_IsWriteEndMark(CLzmaEncHandle p)
3076 return (unsigned)p->writeEndMark;
3080 SRes LzmaEnc_MemEncode(CLzmaEncHandle p, Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
3081 int writeEndMark, ICompressProgressPtr progress, ISzAllocPtr alloc, ISzAllocPtr allocBig)
3086 CLzmaEnc_SeqOutStreamBuf outStream;
3088 outStream.vt.Write = SeqOutStreamBuf_Write;
3089 outStream.data = dest;
3090 outStream.rem = *destLen;
3091 outStream.overflow = False;
3093 p->writeEndMark = writeEndMark;
3094 p->rc.outStream = &outStream.vt;
3096 res = LzmaEnc_MemPrepare(p, src, srcLen, 0, alloc, allocBig);
3100 res = LzmaEnc_Encode2(p, progress);
3101 if (res == SZ_OK && p->nowPos64 != srcLen)
3102 res = SZ_ERROR_FAIL;
3105 *destLen -= (SizeT)outStream.rem;
3106 if (outStream.overflow)
3107 return SZ_ERROR_OUTPUT_EOF;
3112 SRes LzmaEncode(Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
3113 const CLzmaEncProps *props, Byte *propsEncoded, SizeT *propsSize, int writeEndMark,
3114 ICompressProgressPtr progress, ISzAllocPtr alloc, ISzAllocPtr allocBig)
3116 CLzmaEncHandle p = LzmaEnc_Create(alloc);
3119 return SZ_ERROR_MEM;
3121 res = LzmaEnc_SetProps(p, props);
3124 res = LzmaEnc_WriteProperties(p, propsEncoded, propsSize);
3126 res = LzmaEnc_MemEncode(p, dest, destLen, src, srcLen,
3127 writeEndMark, progress, alloc, allocBig);
3130 LzmaEnc_Destroy(p, alloc, allocBig);
3137 void LzmaEnc_GetLzThreads(CLzmaEncHandle p, HANDLE lz_threads[2])
3139 GET_const_CLzmaEnc_p
3140 lz_threads[0] = p->matchFinderMt.hashSync.thread;
3141 lz_threads[1] = p->matchFinderMt.btSync.thread;