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