1 /* LzmaEnc.c -- LZMA Encoder
2 2009-02-02 : Igor Pavlov : Public domain */
6 /* #define SHOW_STAT */
7 /* #define SHOW_STAT2 */
9 #if defined(SHOW_STAT) || defined(SHOW_STAT2)
24 #define kBlockSizeMax ((1 << LZMA_NUM_BLOCK_SIZE_BITS) - 1)
26 #define kBlockSize (9 << 10)
27 #define kUnpackBlockSize (1 << 18)
28 #define kMatchArraySize (1 << 21)
29 #define kMatchRecordMaxSize ((LZMA_MATCH_LEN_MAX * 2 + 3) * LZMA_MATCH_LEN_MAX)
31 #define kNumMaxDirectBits (31)
33 #define kNumTopBits 24
34 #define kTopValue ((UInt32)1 << kNumTopBits)
36 #define kNumBitModelTotalBits 11
37 #define kBitModelTotal (1 << kNumBitModelTotalBits)
38 #define kNumMoveBits 5
39 #define kProbInitValue (kBitModelTotal >> 1)
41 #define kNumMoveReducingBits 4
42 #define kNumBitPriceShiftBits 4
43 #define kBitPrice (1 << kNumBitPriceShiftBits)
45 void LzmaEncProps_Init(CLzmaEncProps
*p
)
48 p
->dictSize
= p
->mc
= 0;
49 p
->lc
= p
->lp
= p
->pb
= p
->algo
= p
->fb
= p
->btMode
= p
->numHashBytes
= p
->numThreads
= -1;
53 void LzmaEncProps_Normalize(CLzmaEncProps
*p
)
56 if (level
< 0) level
= 5;
58 if (p
->dictSize
== 0) p
->dictSize
= (level
<= 5 ? (1 << (level
* 2 + 14)) : (level
== 6 ? (1 << 25) : (1 << 26)));
59 if (p
->lc
< 0) p
->lc
= 3;
60 if (p
->lp
< 0) p
->lp
= 0;
61 if (p
->pb
< 0) p
->pb
= 2;
62 if (p
->algo
< 0) p
->algo
= (level
< 5 ? 0 : 1);
63 if (p
->fb
< 0) p
->fb
= (level
< 7 ? 32 : 64);
64 if (p
->btMode
< 0) p
->btMode
= (p
->algo
== 0 ? 0 : 1);
65 if (p
->numHashBytes
< 0) p
->numHashBytes
= 4;
66 if (p
->mc
== 0) p
->mc
= (16 + (p
->fb
>> 1)) >> (p
->btMode
? 0 : 1);
67 if (p
->numThreads
< 0)
70 ((p
->btMode
&& p
->algo
) ? 2 : 1);
76 UInt32
LzmaEncProps_GetDictSize(const CLzmaEncProps
*props2
)
78 CLzmaEncProps props
= *props2
;
79 LzmaEncProps_Normalize(&props
);
80 return props
.dictSize
;
83 /* #define LZMA_LOG_BSR */
84 /* Define it for Intel's CPU */
89 #define kDicLogSizeMaxCompress 30
91 #define BSR2_RET(pos, res) { unsigned long i; _BitScanReverse(&i, (pos)); res = (i + i) + ((pos >> (i - 1)) & 1); }
93 UInt32
GetPosSlot1(UInt32 pos
)
99 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }
100 #define GetPosSlot(pos, res) { if (pos < 2) res = pos; else BSR2_RET(pos, res); }
104 #define kNumLogBits (9 + (int)sizeof(size_t) / 2)
105 #define kDicLogSizeMaxCompress ((kNumLogBits - 1) * 2 + 7)
107 void LzmaEnc_FastPosInit(Byte
*g_FastPos
)
113 for (slotFast
= 2; slotFast
< kNumLogBits
* 2; slotFast
++)
115 UInt32 k
= (1 << ((slotFast
>> 1) - 1));
117 for (j
= 0; j
< k
; j
++, c
++)
118 g_FastPos
[c
] = (Byte
)slotFast
;
122 #define BSR2_RET(pos, res) { UInt32 i = 6 + ((kNumLogBits - 1) & \
123 (0 - (((((UInt32)1 << (kNumLogBits + 6)) - 1) - pos) >> 31))); \
124 res = p->g_FastPos[pos >> i] + (i * 2); }
126 #define BSR2_RET(pos, res) { res = (pos < (1 << (kNumLogBits + 6))) ? \
127 p->g_FastPos[pos >> 6] + 12 : \
128 p->g_FastPos[pos >> (6 + kNumLogBits - 1)] + (6 + (kNumLogBits - 1)) * 2; }
131 #define GetPosSlot1(pos) p->g_FastPos[pos]
132 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }
133 #define GetPosSlot(pos, res) { if (pos < kNumFullDistances) res = p->g_FastPos[pos]; else BSR2_RET(pos, res); }
138 #define LZMA_NUM_REPS 4
140 typedef unsigned CState
;
142 typedef struct _COptimal
155 UInt32 backs
[LZMA_NUM_REPS
];
158 #define kNumOpts (1 << 12)
160 #define kNumLenToPosStates 4
161 #define kNumPosSlotBits 6
162 #define kDicLogSizeMin 0
163 #define kDicLogSizeMax 32
164 #define kDistTableSizeMax (kDicLogSizeMax * 2)
167 #define kNumAlignBits 4
168 #define kAlignTableSize (1 << kNumAlignBits)
169 #define kAlignMask (kAlignTableSize - 1)
171 #define kStartPosModelIndex 4
172 #define kEndPosModelIndex 14
173 #define kNumPosModels (kEndPosModelIndex - kStartPosModelIndex)
175 #define kNumFullDistances (1 << (kEndPosModelIndex / 2))
178 #define CLzmaProb UInt32
180 #define CLzmaProb UInt16
183 #define LZMA_PB_MAX 4
184 #define LZMA_LC_MAX 8
185 #define LZMA_LP_MAX 4
187 #define LZMA_NUM_PB_STATES_MAX (1 << LZMA_PB_MAX)
190 #define kLenNumLowBits 3
191 #define kLenNumLowSymbols (1 << kLenNumLowBits)
192 #define kLenNumMidBits 3
193 #define kLenNumMidSymbols (1 << kLenNumMidBits)
194 #define kLenNumHighBits 8
195 #define kLenNumHighSymbols (1 << kLenNumHighBits)
197 #define kLenNumSymbolsTotal (kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)
199 #define LZMA_MATCH_LEN_MIN 2
200 #define LZMA_MATCH_LEN_MAX (LZMA_MATCH_LEN_MIN + kLenNumSymbolsTotal - 1)
202 #define kNumStates 12
208 CLzmaProb low
[LZMA_NUM_PB_STATES_MAX
<< kLenNumLowBits
];
209 CLzmaProb mid
[LZMA_NUM_PB_STATES_MAX
<< kLenNumMidBits
];
210 CLzmaProb high
[kLenNumHighSymbols
];
216 UInt32 prices
[LZMA_NUM_PB_STATES_MAX
][kLenNumSymbolsTotal
];
218 UInt32 counters
[LZMA_NUM_PB_STATES_MAX
];
221 typedef struct _CRangeEnc
230 ISeqOutStream
*outStream
;
235 typedef struct _CSeqInStreamBuf
237 ISeqInStream funcTable
;
242 static SRes
MyRead(void *pp
, void *data
, size_t *size
)
244 size_t curSize
= *size
;
245 CSeqInStreamBuf
*p
= (CSeqInStreamBuf
*)pp
;
246 if (p
->rem
< curSize
)
248 memcpy(data
, p
->data
, curSize
);
259 CLzmaProb isMatch
[kNumStates
][LZMA_NUM_PB_STATES_MAX
];
260 CLzmaProb isRep
[kNumStates
];
261 CLzmaProb isRepG0
[kNumStates
];
262 CLzmaProb isRepG1
[kNumStates
];
263 CLzmaProb isRepG2
[kNumStates
];
264 CLzmaProb isRep0Long
[kNumStates
][LZMA_NUM_PB_STATES_MAX
];
266 CLzmaProb posSlotEncoder
[kNumLenToPosStates
][1 << kNumPosSlotBits
];
267 CLzmaProb posEncoders
[kNumFullDistances
- kEndPosModelIndex
];
268 CLzmaProb posAlignEncoder
[1 << kNumAlignBits
];
271 CLenPriceEnc repLenEnc
;
273 UInt32 reps
[LZMA_NUM_REPS
];
277 typedef struct _CLzmaEnc
279 IMatchFinder matchFinder
;
280 void *matchFinderObj
;
282 #ifdef COMPRESS_MF_MT
284 CMatchFinderMt matchFinderMt
;
287 CMatchFinder matchFinderBase
;
289 #ifdef COMPRESS_MF_MT
293 UInt32 optimumEndIndex
;
294 UInt32 optimumCurrentIndex
;
296 UInt32 longestMatchLength
;
299 COptimal opt
[kNumOpts
];
302 Byte g_FastPos
[1 << kNumLogBits
];
305 UInt32 ProbPrices
[kBitModelTotal
>> kNumMoveReducingBits
];
306 UInt32 matches
[LZMA_MATCH_LEN_MAX
* 2 + 2 + 1];
308 UInt32 additionalOffset
;
309 UInt32 reps
[LZMA_NUM_REPS
];
312 UInt32 posSlotPrices
[kNumLenToPosStates
][kDistTableSizeMax
];
313 UInt32 distancesPrices
[kNumLenToPosStates
][kNumFullDistances
];
314 UInt32 alignPrices
[kAlignTableSize
];
315 UInt32 alignPriceCount
;
317 UInt32 distTableSize
;
320 unsigned lpMask
, pbMask
;
324 CLzmaProb isMatch
[kNumStates
][LZMA_NUM_PB_STATES_MAX
];
325 CLzmaProb isRep
[kNumStates
];
326 CLzmaProb isRepG0
[kNumStates
];
327 CLzmaProb isRepG1
[kNumStates
];
328 CLzmaProb isRepG2
[kNumStates
];
329 CLzmaProb isRep0Long
[kNumStates
][LZMA_NUM_PB_STATES_MAX
];
331 CLzmaProb posSlotEncoder
[kNumLenToPosStates
][1 << kNumPosSlotBits
];
332 CLzmaProb posEncoders
[kNumFullDistances
- kEndPosModelIndex
];
333 CLzmaProb posAlignEncoder
[1 << kNumAlignBits
];
336 CLenPriceEnc repLenEnc
;
346 UInt32 matchPriceCount
;
352 UInt32 matchFinderCycles
;
354 ISeqInStream
*inStream
;
355 CSeqInStreamBuf seqBufInStream
;
357 CSaveState saveState
;
360 void LzmaEnc_SaveState(CLzmaEncHandle pp
)
362 CLzmaEnc
*p
= (CLzmaEnc
*)pp
;
363 CSaveState
*dest
= &p
->saveState
;
365 dest
->lenEnc
= p
->lenEnc
;
366 dest
->repLenEnc
= p
->repLenEnc
;
367 dest
->state
= p
->state
;
369 for (i
= 0; i
< kNumStates
; i
++)
371 memcpy(dest
->isMatch
[i
], p
->isMatch
[i
], sizeof(p
->isMatch
[i
]));
372 memcpy(dest
->isRep0Long
[i
], p
->isRep0Long
[i
], sizeof(p
->isRep0Long
[i
]));
374 for (i
= 0; i
< kNumLenToPosStates
; i
++)
375 memcpy(dest
->posSlotEncoder
[i
], p
->posSlotEncoder
[i
], sizeof(p
->posSlotEncoder
[i
]));
376 memcpy(dest
->isRep
, p
->isRep
, sizeof(p
->isRep
));
377 memcpy(dest
->isRepG0
, p
->isRepG0
, sizeof(p
->isRepG0
));
378 memcpy(dest
->isRepG1
, p
->isRepG1
, sizeof(p
->isRepG1
));
379 memcpy(dest
->isRepG2
, p
->isRepG2
, sizeof(p
->isRepG2
));
380 memcpy(dest
->posEncoders
, p
->posEncoders
, sizeof(p
->posEncoders
));
381 memcpy(dest
->posAlignEncoder
, p
->posAlignEncoder
, sizeof(p
->posAlignEncoder
));
382 memcpy(dest
->reps
, p
->reps
, sizeof(p
->reps
));
383 memcpy(dest
->litProbs
, p
->litProbs
, (0x300 << p
->lclp
) * sizeof(CLzmaProb
));
386 void LzmaEnc_RestoreState(CLzmaEncHandle pp
)
388 CLzmaEnc
*dest
= (CLzmaEnc
*)pp
;
389 const CSaveState
*p
= &dest
->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
, (0x300 << dest
->lclp
) * sizeof(CLzmaProb
));
412 SRes
LzmaEnc_SetProps(CLzmaEncHandle pp
, const CLzmaEncProps
*props2
)
414 CLzmaEnc
*p
= (CLzmaEnc
*)pp
;
415 CLzmaEncProps props
= *props2
;
416 LzmaEncProps_Normalize(&props
);
418 if (props
.lc
> LZMA_LC_MAX
|| props
.lp
> LZMA_LP_MAX
|| props
.pb
> LZMA_PB_MAX
||
419 props
.dictSize
> (1 << kDicLogSizeMaxCompress
) || props
.dictSize
> (1 << 30))
420 return SZ_ERROR_PARAM
;
421 p
->dictSize
= props
.dictSize
;
422 p
->matchFinderCycles
= props
.mc
;
424 unsigned fb
= props
.fb
;
427 if (fb
> LZMA_MATCH_LEN_MAX
)
428 fb
= LZMA_MATCH_LEN_MAX
;
429 p
->numFastBytes
= fb
;
434 p
->fastMode
= (props
.algo
== 0);
435 p
->matchFinderBase
.btMode
= props
.btMode
;
437 UInt32 numHashBytes
= 4;
440 if (props
.numHashBytes
< 2)
442 else if (props
.numHashBytes
< 4)
443 numHashBytes
= props
.numHashBytes
;
445 p
->matchFinderBase
.numHashBytes
= numHashBytes
;
448 p
->matchFinderBase
.cutValue
= props
.mc
;
450 p
->writeEndMark
= props
.writeEndMark
;
452 #ifdef COMPRESS_MF_MT
454 if (newMultiThread != _multiThread)
456 ReleaseMatchFinder();
457 _multiThread = newMultiThread;
460 p
->multiThread
= (props
.numThreads
> 1);
466 static const int kLiteralNextStates
[kNumStates
] = {0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5};
467 static const int kMatchNextStates
[kNumStates
] = {7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10};
468 static const int kRepNextStates
[kNumStates
] = {8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11};
469 static const int kShortRepNextStates
[kNumStates
]= {9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11};
471 #define IsCharState(s) ((s) < 7)
473 #define GetLenToPosState(len) (((len) < kNumLenToPosStates + 1) ? (len) - 2 : kNumLenToPosStates - 1)
475 #define kInfinityPrice (1 << 30)
477 static void RangeEnc_Construct(CRangeEnc
*p
)
483 #define RangeEnc_GetProcessed(p) ((p)->processed + ((p)->buf - (p)->bufBase) + (p)->cacheSize)
485 #define RC_BUF_SIZE (1 << 16)
486 static int RangeEnc_Alloc(CRangeEnc
*p
, ISzAlloc
*alloc
)
490 p
->bufBase
= (Byte
*)alloc
->Alloc(alloc
, RC_BUF_SIZE
);
493 p
->bufLim
= p
->bufBase
+ RC_BUF_SIZE
;
498 static void RangeEnc_Free(CRangeEnc
*p
, ISzAlloc
*alloc
)
500 alloc
->Free(alloc
, p
->bufBase
);
504 static void RangeEnc_Init(CRangeEnc
*p
)
508 p
->range
= 0xFFFFFFFF;
518 static void RangeEnc_FlushStream(CRangeEnc
*p
)
523 num
= p
->buf
- p
->bufBase
;
524 if (num
!= p
->outStream
->Write(p
->outStream
, p
->bufBase
, num
))
525 p
->res
= SZ_ERROR_WRITE
;
530 static void MY_FAST_CALL
RangeEnc_ShiftLow(CRangeEnc
*p
)
532 if ((UInt32
)p
->low
< (UInt32
)0xFF000000 || (int)(p
->low
>> 32) != 0)
534 Byte temp
= p
->cache
;
538 *buf
++ = (Byte
)(temp
+ (Byte
)(p
->low
>> 32));
540 if (buf
== p
->bufLim
)
541 RangeEnc_FlushStream(p
);
544 while (--p
->cacheSize
!= 0);
545 p
->cache
= (Byte
)((UInt32
)p
->low
>> 24);
548 p
->low
= (UInt32
)p
->low
<< 8;
551 static void RangeEnc_FlushData(CRangeEnc
*p
)
554 for (i
= 0; i
< 5; i
++)
555 RangeEnc_ShiftLow(p
);
558 static void RangeEnc_EncodeDirectBits(CRangeEnc
*p
, UInt32 value
, int numBits
)
563 p
->low
+= p
->range
& (0 - ((value
>> --numBits
) & 1));
564 if (p
->range
< kTopValue
)
567 RangeEnc_ShiftLow(p
);
570 while (numBits
!= 0);
573 static void RangeEnc_EncodeBit(CRangeEnc
*p
, CLzmaProb
*prob
, UInt32 symbol
)
576 UInt32 newBound
= (p
->range
>> kNumBitModelTotalBits
) * ttt
;
580 ttt
+= (kBitModelTotal
- ttt
) >> kNumMoveBits
;
585 p
->range
-= newBound
;
586 ttt
-= ttt
>> kNumMoveBits
;
588 *prob
= (CLzmaProb
)ttt
;
589 if (p
->range
< kTopValue
)
592 RangeEnc_ShiftLow(p
);
596 static void LitEnc_Encode(CRangeEnc
*p
, CLzmaProb
*probs
, UInt32 symbol
)
601 RangeEnc_EncodeBit(p
, probs
+ (symbol
>> 8), (symbol
>> 7) & 1);
604 while (symbol
< 0x10000);
607 static void LitEnc_EncodeMatched(CRangeEnc
*p
, CLzmaProb
*probs
, UInt32 symbol
, UInt32 matchByte
)
614 RangeEnc_EncodeBit(p
, probs
+ (offs
+ (matchByte
& offs
) + (symbol
>> 8)), (symbol
>> 7) & 1);
616 offs
&= ~(matchByte
^ symbol
);
618 while (symbol
< 0x10000);
621 void LzmaEnc_InitPriceTables(UInt32
*ProbPrices
)
624 for (i
= (1 << kNumMoveReducingBits
) / 2; i
< kBitModelTotal
; i
+= (1 << kNumMoveReducingBits
))
626 const int kCyclesBits
= kNumBitPriceShiftBits
;
630 for (j
= 0; j
< kCyclesBits
; j
++)
634 while (w
>= ((UInt32
)1 << 16))
640 ProbPrices
[i
>> kNumMoveReducingBits
] = ((kNumBitModelTotalBits
<< kCyclesBits
) - 15 - bitCount
);
645 #define GET_PRICE(prob, symbol) \
646 p->ProbPrices[((prob) ^ (((-(int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];
648 #define GET_PRICEa(prob, symbol) \
649 ProbPrices[((prob) ^ ((-((int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];
651 #define GET_PRICE_0(prob) p->ProbPrices[(prob) >> kNumMoveReducingBits]
652 #define GET_PRICE_1(prob) p->ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]
654 #define GET_PRICE_0a(prob) ProbPrices[(prob) >> kNumMoveReducingBits]
655 #define GET_PRICE_1a(prob) ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]
657 static UInt32
LitEnc_GetPrice(const CLzmaProb
*probs
, UInt32 symbol
, UInt32
*ProbPrices
)
663 price
+= GET_PRICEa(probs
[symbol
>> 8], (symbol
>> 7) & 1);
666 while (symbol
< 0x10000);
670 static UInt32
LitEnc_GetPriceMatched(const CLzmaProb
*probs
, UInt32 symbol
, UInt32 matchByte
, UInt32
*ProbPrices
)
678 price
+= GET_PRICEa(probs
[offs
+ (matchByte
& offs
) + (symbol
>> 8)], (symbol
>> 7) & 1);
680 offs
&= ~(matchByte
^ symbol
);
682 while (symbol
< 0x10000);
687 static void RcTree_Encode(CRangeEnc
*rc
, CLzmaProb
*probs
, int numBitLevels
, UInt32 symbol
)
691 for (i
= numBitLevels
; i
!= 0;)
695 bit
= (symbol
>> i
) & 1;
696 RangeEnc_EncodeBit(rc
, probs
+ m
, bit
);
701 static void RcTree_ReverseEncode(CRangeEnc
*rc
, CLzmaProb
*probs
, int numBitLevels
, UInt32 symbol
)
705 for (i
= 0; i
< numBitLevels
; i
++)
707 UInt32 bit
= symbol
& 1;
708 RangeEnc_EncodeBit(rc
, probs
+ m
, bit
);
714 static UInt32
RcTree_GetPrice(const CLzmaProb
*probs
, int numBitLevels
, UInt32 symbol
, UInt32
*ProbPrices
)
717 symbol
|= (1 << numBitLevels
);
720 price
+= GET_PRICEa(probs
[symbol
>> 1], symbol
& 1);
726 static UInt32
RcTree_ReverseGetPrice(const CLzmaProb
*probs
, int numBitLevels
, UInt32 symbol
, UInt32
*ProbPrices
)
731 for (i
= numBitLevels
; i
!= 0; i
--)
733 UInt32 bit
= symbol
& 1;
735 price
+= GET_PRICEa(probs
[m
], bit
);
742 static void LenEnc_Init(CLenEnc
*p
)
745 p
->choice
= p
->choice2
= kProbInitValue
;
746 for (i
= 0; i
< (LZMA_NUM_PB_STATES_MAX
<< kLenNumLowBits
); i
++)
747 p
->low
[i
] = kProbInitValue
;
748 for (i
= 0; i
< (LZMA_NUM_PB_STATES_MAX
<< kLenNumMidBits
); i
++)
749 p
->mid
[i
] = kProbInitValue
;
750 for (i
= 0; i
< kLenNumHighSymbols
; i
++)
751 p
->high
[i
] = kProbInitValue
;
754 static void LenEnc_Encode(CLenEnc
*p
, CRangeEnc
*rc
, UInt32 symbol
, UInt32 posState
)
756 if (symbol
< kLenNumLowSymbols
)
758 RangeEnc_EncodeBit(rc
, &p
->choice
, 0);
759 RcTree_Encode(rc
, p
->low
+ (posState
<< kLenNumLowBits
), kLenNumLowBits
, symbol
);
763 RangeEnc_EncodeBit(rc
, &p
->choice
, 1);
764 if (symbol
< kLenNumLowSymbols
+ kLenNumMidSymbols
)
766 RangeEnc_EncodeBit(rc
, &p
->choice2
, 0);
767 RcTree_Encode(rc
, p
->mid
+ (posState
<< kLenNumMidBits
), kLenNumMidBits
, symbol
- kLenNumLowSymbols
);
771 RangeEnc_EncodeBit(rc
, &p
->choice2
, 1);
772 RcTree_Encode(rc
, p
->high
, kLenNumHighBits
, symbol
- kLenNumLowSymbols
- kLenNumMidSymbols
);
777 static void LenEnc_SetPrices(CLenEnc
*p
, UInt32 posState
, UInt32 numSymbols
, UInt32
*prices
, UInt32
*ProbPrices
)
779 UInt32 a0
= GET_PRICE_0a(p
->choice
);
780 UInt32 a1
= GET_PRICE_1a(p
->choice
);
781 UInt32 b0
= a1
+ GET_PRICE_0a(p
->choice2
);
782 UInt32 b1
= a1
+ GET_PRICE_1a(p
->choice2
);
784 for (i
= 0; i
< kLenNumLowSymbols
; i
++)
788 prices
[i
] = a0
+ RcTree_GetPrice(p
->low
+ (posState
<< kLenNumLowBits
), kLenNumLowBits
, i
, ProbPrices
);
790 for (; i
< kLenNumLowSymbols
+ kLenNumMidSymbols
; i
++)
794 prices
[i
] = b0
+ RcTree_GetPrice(p
->mid
+ (posState
<< kLenNumMidBits
), kLenNumMidBits
, i
- kLenNumLowSymbols
, ProbPrices
);
796 for (; i
< numSymbols
; i
++)
797 prices
[i
] = b1
+ RcTree_GetPrice(p
->high
, kLenNumHighBits
, i
- kLenNumLowSymbols
- kLenNumMidSymbols
, ProbPrices
);
800 static void MY_FAST_CALL
LenPriceEnc_UpdateTable(CLenPriceEnc
*p
, UInt32 posState
, UInt32
*ProbPrices
)
802 LenEnc_SetPrices(&p
->p
, posState
, p
->tableSize
, p
->prices
[posState
], ProbPrices
);
803 p
->counters
[posState
] = p
->tableSize
;
806 static void LenPriceEnc_UpdateTables(CLenPriceEnc
*p
, UInt32 numPosStates
, UInt32
*ProbPrices
)
809 for (posState
= 0; posState
< numPosStates
; posState
++)
810 LenPriceEnc_UpdateTable(p
, posState
, ProbPrices
);
813 static void LenEnc_Encode2(CLenPriceEnc
*p
, CRangeEnc
*rc
, UInt32 symbol
, UInt32 posState
, Bool updatePrice
, UInt32
*ProbPrices
)
815 LenEnc_Encode(&p
->p
, rc
, symbol
, posState
);
817 if (--p
->counters
[posState
] == 0)
818 LenPriceEnc_UpdateTable(p
, posState
, ProbPrices
);
824 static void MovePos(CLzmaEnc
*p
, UInt32 num
)
828 printf("\n MovePos %d", num
);
832 p
->additionalOffset
+= num
;
833 p
->matchFinder
.Skip(p
->matchFinderObj
, num
);
837 static UInt32
ReadMatchDistances(CLzmaEnc
*p
, UInt32
*numDistancePairsRes
)
839 UInt32 lenRes
= 0, numPairs
;
840 p
->numAvail
= p
->matchFinder
.GetNumAvailableBytes(p
->matchFinderObj
);
841 numPairs
= p
->matchFinder
.GetMatches(p
->matchFinderObj
, p
->matches
);
843 printf("\n i = %d numPairs = %d ", ttt
, numPairs
/ 2);
847 for (i
= 0; i
< numPairs
; i
+= 2)
848 printf("%2d %6d | ", p
->matches
[i
], p
->matches
[i
+ 1]);
853 lenRes
= p
->matches
[numPairs
- 2];
854 if (lenRes
== p
->numFastBytes
)
856 const Byte
*pby
= p
->matchFinder
.GetPointerToCurrentPos(p
->matchFinderObj
) - 1;
857 UInt32 distance
= p
->matches
[numPairs
- 1] + 1;
858 UInt32 numAvail
= p
->numAvail
;
859 if (numAvail
> LZMA_MATCH_LEN_MAX
)
860 numAvail
= LZMA_MATCH_LEN_MAX
;
862 const Byte
*pby2
= pby
- distance
;
863 for (; lenRes
< numAvail
&& pby
[lenRes
] == pby2
[lenRes
]; lenRes
++);
867 p
->additionalOffset
++;
868 *numDistancePairsRes
= numPairs
;
873 #define MakeAsChar(p) (p)->backPrev = (UInt32)(-1); (p)->prev1IsChar = False;
874 #define MakeAsShortRep(p) (p)->backPrev = 0; (p)->prev1IsChar = False;
875 #define IsShortRep(p) ((p)->backPrev == 0)
877 static UInt32
GetRepLen1Price(CLzmaEnc
*p
, UInt32 state
, UInt32 posState
)
880 GET_PRICE_0(p
->isRepG0
[state
]) +
881 GET_PRICE_0(p
->isRep0Long
[state
][posState
]);
884 static UInt32
GetPureRepPrice(CLzmaEnc
*p
, UInt32 repIndex
, UInt32 state
, UInt32 posState
)
889 price
= GET_PRICE_0(p
->isRepG0
[state
]);
890 price
+= GET_PRICE_1(p
->isRep0Long
[state
][posState
]);
894 price
= GET_PRICE_1(p
->isRepG0
[state
]);
896 price
+= GET_PRICE_0(p
->isRepG1
[state
]);
899 price
+= GET_PRICE_1(p
->isRepG1
[state
]);
900 price
+= GET_PRICE(p
->isRepG2
[state
], repIndex
- 2);
906 static UInt32
GetRepPrice(CLzmaEnc
*p
, UInt32 repIndex
, UInt32 len
, UInt32 state
, UInt32 posState
)
908 return p
->repLenEnc
.prices
[posState
][len
- LZMA_MATCH_LEN_MIN
] +
909 GetPureRepPrice(p
, repIndex
, state
, posState
);
912 static UInt32
Backward(CLzmaEnc
*p
, UInt32
*backRes
, UInt32 cur
)
914 UInt32 posMem
= p
->opt
[cur
].posPrev
;
915 UInt32 backMem
= p
->opt
[cur
].backPrev
;
916 p
->optimumEndIndex
= cur
;
919 if (p
->opt
[cur
].prev1IsChar
)
921 MakeAsChar(&p
->opt
[posMem
])
922 p
->opt
[posMem
].posPrev
= posMem
- 1;
923 if (p
->opt
[cur
].prev2
)
925 p
->opt
[posMem
- 1].prev1IsChar
= False
;
926 p
->opt
[posMem
- 1].posPrev
= p
->opt
[cur
].posPrev2
;
927 p
->opt
[posMem
- 1].backPrev
= p
->opt
[cur
].backPrev2
;
931 UInt32 posPrev
= posMem
;
932 UInt32 backCur
= backMem
;
934 backMem
= p
->opt
[posPrev
].backPrev
;
935 posMem
= p
->opt
[posPrev
].posPrev
;
937 p
->opt
[posPrev
].backPrev
= backCur
;
938 p
->opt
[posPrev
].posPrev
= cur
;
943 *backRes
= p
->opt
[0].backPrev
;
944 p
->optimumCurrentIndex
= p
->opt
[0].posPrev
;
945 return p
->optimumCurrentIndex
;
948 #define LIT_PROBS(pos, prevByte) (p->litProbs + ((((pos) & p->lpMask) << p->lc) + ((prevByte) >> (8 - p->lc))) * 0x300)
950 static UInt32
GetOptimum(CLzmaEnc
*p
, UInt32 position
, UInt32
*backRes
)
952 UInt32 numAvail
, mainLen
, numPairs
, repMaxIndex
, i
, posState
, lenEnd
, len
, cur
;
953 UInt32 matchPrice
, repMatchPrice
, normalMatchPrice
;
954 UInt32 reps
[LZMA_NUM_REPS
], repLens
[LZMA_NUM_REPS
];
957 Byte curByte
, matchByte
;
958 if (p
->optimumEndIndex
!= p
->optimumCurrentIndex
)
960 const COptimal
*opt
= &p
->opt
[p
->optimumCurrentIndex
];
961 UInt32 lenRes
= opt
->posPrev
- p
->optimumCurrentIndex
;
962 *backRes
= opt
->backPrev
;
963 p
->optimumCurrentIndex
= opt
->posPrev
;
966 p
->optimumCurrentIndex
= p
->optimumEndIndex
= 0;
968 if (p
->additionalOffset
== 0)
969 mainLen
= ReadMatchDistances(p
, &numPairs
);
972 mainLen
= p
->longestMatchLength
;
973 numPairs
= p
->numPairs
;
976 numAvail
= p
->numAvail
;
979 *backRes
= (UInt32
)(-1);
982 if (numAvail
> LZMA_MATCH_LEN_MAX
)
983 numAvail
= LZMA_MATCH_LEN_MAX
;
985 data
= p
->matchFinder
.GetPointerToCurrentPos(p
->matchFinderObj
) - 1;
987 for (i
= 0; i
< LZMA_NUM_REPS
; i
++)
991 reps
[i
] = p
->reps
[i
];
992 data2
= data
- (reps
[i
] + 1);
993 if (data
[0] != data2
[0] || data
[1] != data2
[1])
998 for (lenTest
= 2; lenTest
< numAvail
&& data
[lenTest
] == data2
[lenTest
]; lenTest
++);
999 repLens
[i
] = lenTest
;
1000 if (lenTest
> repLens
[repMaxIndex
])
1003 if (repLens
[repMaxIndex
] >= p
->numFastBytes
)
1006 *backRes
= repMaxIndex
;
1007 lenRes
= repLens
[repMaxIndex
];
1008 MovePos(p
, lenRes
- 1);
1012 matches
= p
->matches
;
1013 if (mainLen
>= p
->numFastBytes
)
1015 *backRes
= matches
[numPairs
- 1] + LZMA_NUM_REPS
;
1016 MovePos(p
, mainLen
- 1);
1020 matchByte
= *(data
- (reps
[0] + 1));
1022 if (mainLen
< 2 && curByte
!= matchByte
&& repLens
[repMaxIndex
] < 2)
1024 *backRes
= (UInt32
)-1;
1028 p
->opt
[0].state
= (CState
)p
->state
;
1030 posState
= (position
& p
->pbMask
);
1033 const CLzmaProb
*probs
= LIT_PROBS(position
, *(data
- 1));
1034 p
->opt
[1].price
= GET_PRICE_0(p
->isMatch
[p
->state
][posState
]) +
1035 (!IsCharState(p
->state
) ?
1036 LitEnc_GetPriceMatched(probs
, curByte
, matchByte
, p
->ProbPrices
) :
1037 LitEnc_GetPrice(probs
, curByte
, p
->ProbPrices
));
1040 MakeAsChar(&p
->opt
[1]);
1042 matchPrice
= GET_PRICE_1(p
->isMatch
[p
->state
][posState
]);
1043 repMatchPrice
= matchPrice
+ GET_PRICE_1(p
->isRep
[p
->state
]);
1045 if (matchByte
== curByte
)
1047 UInt32 shortRepPrice
= repMatchPrice
+ GetRepLen1Price(p
, p
->state
, posState
);
1048 if (shortRepPrice
< p
->opt
[1].price
)
1050 p
->opt
[1].price
= shortRepPrice
;
1051 MakeAsShortRep(&p
->opt
[1]);
1054 lenEnd
= ((mainLen
>= repLens
[repMaxIndex
]) ? mainLen
: repLens
[repMaxIndex
]);
1058 *backRes
= p
->opt
[1].backPrev
;
1062 p
->opt
[1].posPrev
= 0;
1063 for (i
= 0; i
< LZMA_NUM_REPS
; i
++)
1064 p
->opt
[0].backs
[i
] = reps
[i
];
1068 p
->opt
[len
--].price
= kInfinityPrice
;
1071 for (i
= 0; i
< LZMA_NUM_REPS
; i
++)
1073 UInt32 repLen
= repLens
[i
];
1077 price
= repMatchPrice
+ GetPureRepPrice(p
, i
, p
->state
, posState
);
1080 UInt32 curAndLenPrice
= price
+ p
->repLenEnc
.prices
[posState
][repLen
- 2];
1081 COptimal
*opt
= &p
->opt
[repLen
];
1082 if (curAndLenPrice
< opt
->price
)
1084 opt
->price
= curAndLenPrice
;
1087 opt
->prev1IsChar
= False
;
1090 while (--repLen
>= 2);
1093 normalMatchPrice
= matchPrice
+ GET_PRICE_0(p
->isRep
[p
->state
]);
1095 len
= ((repLens
[0] >= 2) ? repLens
[0] + 1 : 2);
1099 while (len
> matches
[offs
])
1104 UInt32 distance
= matches
[offs
+ 1];
1106 UInt32 curAndLenPrice
= normalMatchPrice
+ p
->lenEnc
.prices
[posState
][len
- LZMA_MATCH_LEN_MIN
];
1107 UInt32 lenToPosState
= GetLenToPosState(len
);
1108 if (distance
< kNumFullDistances
)
1109 curAndLenPrice
+= p
->distancesPrices
[lenToPosState
][distance
];
1113 GetPosSlot2(distance
, slot
);
1114 curAndLenPrice
+= p
->alignPrices
[distance
& kAlignMask
] + p
->posSlotPrices
[lenToPosState
][slot
];
1117 if (curAndLenPrice
< opt
->price
)
1119 opt
->price
= curAndLenPrice
;
1121 opt
->backPrev
= distance
+ LZMA_NUM_REPS
;
1122 opt
->prev1IsChar
= False
;
1124 if (len
== matches
[offs
])
1127 if (offs
== numPairs
)
1139 printf("\n pos = %4X", position
);
1140 for (i
= cur
; i
<= lenEnd
; i
++)
1141 printf("\nprice[%4X] = %d", position
- cur
+ i
, p
->opt
[i
].price
);
1147 UInt32 numAvailFull
, newLen
, numPairs
, posPrev
, state
, posState
, startLen
;
1148 UInt32 curPrice
, curAnd1Price
, matchPrice
, repMatchPrice
;
1150 Byte curByte
, matchByte
;
1157 return Backward(p
, backRes
, cur
);
1159 newLen
= ReadMatchDistances(p
, &numPairs
);
1160 if (newLen
>= p
->numFastBytes
)
1162 p
->numPairs
= numPairs
;
1163 p
->longestMatchLength
= newLen
;
1164 return Backward(p
, backRes
, cur
);
1167 curOpt
= &p
->opt
[cur
];
1168 posPrev
= curOpt
->posPrev
;
1169 if (curOpt
->prev1IsChar
)
1174 state
= p
->opt
[curOpt
->posPrev2
].state
;
1175 if (curOpt
->backPrev2
< LZMA_NUM_REPS
)
1176 state
= kRepNextStates
[state
];
1178 state
= kMatchNextStates
[state
];
1181 state
= p
->opt
[posPrev
].state
;
1182 state
= kLiteralNextStates
[state
];
1185 state
= p
->opt
[posPrev
].state
;
1186 if (posPrev
== cur
- 1)
1188 if (IsShortRep(curOpt
))
1189 state
= kShortRepNextStates
[state
];
1191 state
= kLiteralNextStates
[state
];
1196 const COptimal
*prevOpt
;
1197 if (curOpt
->prev1IsChar
&& curOpt
->prev2
)
1199 posPrev
= curOpt
->posPrev2
;
1200 pos
= curOpt
->backPrev2
;
1201 state
= kRepNextStates
[state
];
1205 pos
= curOpt
->backPrev
;
1206 if (pos
< LZMA_NUM_REPS
)
1207 state
= kRepNextStates
[state
];
1209 state
= kMatchNextStates
[state
];
1211 prevOpt
= &p
->opt
[posPrev
];
1212 if (pos
< LZMA_NUM_REPS
)
1215 reps
[0] = prevOpt
->backs
[pos
];
1216 for (i
= 1; i
<= pos
; i
++)
1217 reps
[i
] = prevOpt
->backs
[i
- 1];
1218 for (; i
< LZMA_NUM_REPS
; i
++)
1219 reps
[i
] = prevOpt
->backs
[i
];
1224 reps
[0] = (pos
- LZMA_NUM_REPS
);
1225 for (i
= 1; i
< LZMA_NUM_REPS
; i
++)
1226 reps
[i
] = prevOpt
->backs
[i
- 1];
1229 curOpt
->state
= (CState
)state
;
1231 curOpt
->backs
[0] = reps
[0];
1232 curOpt
->backs
[1] = reps
[1];
1233 curOpt
->backs
[2] = reps
[2];
1234 curOpt
->backs
[3] = reps
[3];
1236 curPrice
= curOpt
->price
;
1238 data
= p
->matchFinder
.GetPointerToCurrentPos(p
->matchFinderObj
) - 1;
1240 matchByte
= *(data
- (reps
[0] + 1));
1242 posState
= (position
& p
->pbMask
);
1244 curAnd1Price
= curPrice
+ GET_PRICE_0(p
->isMatch
[state
][posState
]);
1246 const CLzmaProb
*probs
= LIT_PROBS(position
, *(data
- 1));
1248 (!IsCharState(state
) ?
1249 LitEnc_GetPriceMatched(probs
, curByte
, matchByte
, p
->ProbPrices
) :
1250 LitEnc_GetPrice(probs
, curByte
, p
->ProbPrices
));
1253 nextOpt
= &p
->opt
[cur
+ 1];
1255 if (curAnd1Price
< nextOpt
->price
)
1257 nextOpt
->price
= curAnd1Price
;
1258 nextOpt
->posPrev
= cur
;
1259 MakeAsChar(nextOpt
);
1263 matchPrice
= curPrice
+ GET_PRICE_1(p
->isMatch
[state
][posState
]);
1264 repMatchPrice
= matchPrice
+ GET_PRICE_1(p
->isRep
[state
]);
1266 if (matchByte
== curByte
&& !(nextOpt
->posPrev
< cur
&& nextOpt
->backPrev
== 0))
1268 UInt32 shortRepPrice
= repMatchPrice
+ GetRepLen1Price(p
, state
, posState
);
1269 if (shortRepPrice
<= nextOpt
->price
)
1271 nextOpt
->price
= shortRepPrice
;
1272 nextOpt
->posPrev
= cur
;
1273 MakeAsShortRep(nextOpt
);
1277 numAvailFull
= p
->numAvail
;
1279 UInt32 temp
= kNumOpts
- 1 - cur
;
1280 if (temp
< numAvailFull
)
1281 numAvailFull
= temp
;
1284 if (numAvailFull
< 2)
1286 numAvail
= (numAvailFull
<= p
->numFastBytes
? numAvailFull
: p
->numFastBytes
);
1288 if (!nextIsChar
&& matchByte
!= curByte
) /* speed optimization */
1290 /* try Literal + rep0 */
1293 const Byte
*data2
= data
- (reps
[0] + 1);
1294 UInt32 limit
= p
->numFastBytes
+ 1;
1295 if (limit
> numAvailFull
)
1296 limit
= numAvailFull
;
1298 for (temp
= 1; temp
< limit
&& data
[temp
] == data2
[temp
]; temp
++);
1299 lenTest2
= temp
- 1;
1302 UInt32 state2
= kLiteralNextStates
[state
];
1303 UInt32 posStateNext
= (position
+ 1) & p
->pbMask
;
1304 UInt32 nextRepMatchPrice
= curAnd1Price
+
1305 GET_PRICE_1(p
->isMatch
[state2
][posStateNext
]) +
1306 GET_PRICE_1(p
->isRep
[state2
]);
1307 /* for (; lenTest2 >= 2; lenTest2--) */
1309 UInt32 curAndLenPrice
;
1311 UInt32 offset
= cur
+ 1 + lenTest2
;
1312 while (lenEnd
< offset
)
1313 p
->opt
[++lenEnd
].price
= kInfinityPrice
;
1314 curAndLenPrice
= nextRepMatchPrice
+ GetRepPrice(p
, 0, lenTest2
, state2
, posStateNext
);
1315 opt
= &p
->opt
[offset
];
1316 if (curAndLenPrice
< opt
->price
)
1318 opt
->price
= curAndLenPrice
;
1319 opt
->posPrev
= cur
+ 1;
1321 opt
->prev1IsChar
= True
;
1328 startLen
= 2; /* speed optimization */
1331 for (repIndex
= 0; repIndex
< LZMA_NUM_REPS
; repIndex
++)
1336 const Byte
*data2
= data
- (reps
[repIndex
] + 1);
1337 if (data
[0] != data2
[0] || data
[1] != data2
[1])
1339 for (lenTest
= 2; lenTest
< numAvail
&& data
[lenTest
] == data2
[lenTest
]; lenTest
++);
1340 while (lenEnd
< cur
+ lenTest
)
1341 p
->opt
[++lenEnd
].price
= kInfinityPrice
;
1342 lenTestTemp
= lenTest
;
1343 price
= repMatchPrice
+ GetPureRepPrice(p
, repIndex
, state
, posState
);
1346 UInt32 curAndLenPrice
= price
+ p
->repLenEnc
.prices
[posState
][lenTest
- 2];
1347 COptimal
*opt
= &p
->opt
[cur
+ lenTest
];
1348 if (curAndLenPrice
< opt
->price
)
1350 opt
->price
= curAndLenPrice
;
1352 opt
->backPrev
= repIndex
;
1353 opt
->prev1IsChar
= False
;
1356 while (--lenTest
>= 2);
1357 lenTest
= lenTestTemp
;
1360 startLen
= lenTest
+ 1;
1364 UInt32 lenTest2
= lenTest
+ 1;
1365 UInt32 limit
= lenTest2
+ p
->numFastBytes
;
1366 UInt32 nextRepMatchPrice
;
1367 if (limit
> numAvailFull
)
1368 limit
= numAvailFull
;
1369 for (; lenTest2
< limit
&& data
[lenTest2
] == data2
[lenTest2
]; lenTest2
++);
1370 lenTest2
-= lenTest
+ 1;
1373 UInt32 state2
= kRepNextStates
[state
];
1374 UInt32 posStateNext
= (position
+ lenTest
) & p
->pbMask
;
1375 UInt32 curAndLenCharPrice
=
1376 price
+ p
->repLenEnc
.prices
[posState
][lenTest
- 2] +
1377 GET_PRICE_0(p
->isMatch
[state2
][posStateNext
]) +
1378 LitEnc_GetPriceMatched(LIT_PROBS(position
+ lenTest
, data
[lenTest
- 1]),
1379 data
[lenTest
], data2
[lenTest
], p
->ProbPrices
);
1380 state2
= kLiteralNextStates
[state2
];
1381 posStateNext
= (position
+ lenTest
+ 1) & p
->pbMask
;
1382 nextRepMatchPrice
= curAndLenCharPrice
+
1383 GET_PRICE_1(p
->isMatch
[state2
][posStateNext
]) +
1384 GET_PRICE_1(p
->isRep
[state2
]);
1386 /* for (; lenTest2 >= 2; lenTest2--) */
1388 UInt32 curAndLenPrice
;
1390 UInt32 offset
= cur
+ lenTest
+ 1 + lenTest2
;
1391 while (lenEnd
< offset
)
1392 p
->opt
[++lenEnd
].price
= kInfinityPrice
;
1393 curAndLenPrice
= nextRepMatchPrice
+ GetRepPrice(p
, 0, lenTest2
, state2
, posStateNext
);
1394 opt
= &p
->opt
[offset
];
1395 if (curAndLenPrice
< opt
->price
)
1397 opt
->price
= curAndLenPrice
;
1398 opt
->posPrev
= cur
+ lenTest
+ 1;
1400 opt
->prev1IsChar
= True
;
1402 opt
->posPrev2
= cur
;
1403 opt
->backPrev2
= repIndex
;
1410 /* for (UInt32 lenTest = 2; lenTest <= newLen; lenTest++) */
1411 if (newLen
> numAvail
)
1414 for (numPairs
= 0; newLen
> matches
[numPairs
]; numPairs
+= 2);
1415 matches
[numPairs
] = newLen
;
1418 if (newLen
>= startLen
)
1420 UInt32 normalMatchPrice
= matchPrice
+ GET_PRICE_0(p
->isRep
[state
]);
1421 UInt32 offs
, curBack
, posSlot
;
1423 while (lenEnd
< cur
+ newLen
)
1424 p
->opt
[++lenEnd
].price
= kInfinityPrice
;
1427 while (startLen
> matches
[offs
])
1429 curBack
= matches
[offs
+ 1];
1430 GetPosSlot2(curBack
, posSlot
);
1431 for (lenTest
= /*2*/ startLen
; ; lenTest
++)
1433 UInt32 curAndLenPrice
= normalMatchPrice
+ p
->lenEnc
.prices
[posState
][lenTest
- LZMA_MATCH_LEN_MIN
];
1434 UInt32 lenToPosState
= GetLenToPosState(lenTest
);
1436 if (curBack
< kNumFullDistances
)
1437 curAndLenPrice
+= p
->distancesPrices
[lenToPosState
][curBack
];
1439 curAndLenPrice
+= p
->posSlotPrices
[lenToPosState
][posSlot
] + p
->alignPrices
[curBack
& kAlignMask
];
1441 opt
= &p
->opt
[cur
+ lenTest
];
1442 if (curAndLenPrice
< opt
->price
)
1444 opt
->price
= curAndLenPrice
;
1446 opt
->backPrev
= curBack
+ LZMA_NUM_REPS
;
1447 opt
->prev1IsChar
= False
;
1450 if (/*_maxMode && */lenTest
== matches
[offs
])
1452 /* Try Match + Literal + Rep0 */
1453 const Byte
*data2
= data
- (curBack
+ 1);
1454 UInt32 lenTest2
= lenTest
+ 1;
1455 UInt32 limit
= lenTest2
+ p
->numFastBytes
;
1456 UInt32 nextRepMatchPrice
;
1457 if (limit
> numAvailFull
)
1458 limit
= numAvailFull
;
1459 for (; lenTest2
< limit
&& data
[lenTest2
] == data2
[lenTest2
]; lenTest2
++);
1460 lenTest2
-= lenTest
+ 1;
1463 UInt32 state2
= kMatchNextStates
[state
];
1464 UInt32 posStateNext
= (position
+ lenTest
) & p
->pbMask
;
1465 UInt32 curAndLenCharPrice
= curAndLenPrice
+
1466 GET_PRICE_0(p
->isMatch
[state2
][posStateNext
]) +
1467 LitEnc_GetPriceMatched(LIT_PROBS(position
+ lenTest
, data
[lenTest
- 1]),
1468 data
[lenTest
], data2
[lenTest
], p
->ProbPrices
);
1469 state2
= kLiteralNextStates
[state2
];
1470 posStateNext
= (posStateNext
+ 1) & p
->pbMask
;
1471 nextRepMatchPrice
= curAndLenCharPrice
+
1472 GET_PRICE_1(p
->isMatch
[state2
][posStateNext
]) +
1473 GET_PRICE_1(p
->isRep
[state2
]);
1475 /* for (; lenTest2 >= 2; lenTest2--) */
1477 UInt32 offset
= cur
+ lenTest
+ 1 + lenTest2
;
1478 UInt32 curAndLenPrice
;
1480 while (lenEnd
< offset
)
1481 p
->opt
[++lenEnd
].price
= kInfinityPrice
;
1482 curAndLenPrice
= nextRepMatchPrice
+ GetRepPrice(p
, 0, lenTest2
, state2
, posStateNext
);
1483 opt
= &p
->opt
[offset
];
1484 if (curAndLenPrice
< opt
->price
)
1486 opt
->price
= curAndLenPrice
;
1487 opt
->posPrev
= cur
+ lenTest
+ 1;
1489 opt
->prev1IsChar
= True
;
1491 opt
->posPrev2
= cur
;
1492 opt
->backPrev2
= curBack
+ LZMA_NUM_REPS
;
1497 if (offs
== numPairs
)
1499 curBack
= matches
[offs
+ 1];
1500 if (curBack
>= kNumFullDistances
)
1501 GetPosSlot2(curBack
, posSlot
);
1508 #define ChangePair(smallDist, bigDist) (((bigDist) >> 7) > (smallDist))
1510 static UInt32
GetOptimumFast(CLzmaEnc
*p
, UInt32
*backRes
)
1512 UInt32 numAvail
, mainLen
, mainDist
, numPairs
, repIndex
, repLen
, i
;
1514 const UInt32
*matches
;
1516 if (p
->additionalOffset
== 0)
1517 mainLen
= ReadMatchDistances(p
, &numPairs
);
1520 mainLen
= p
->longestMatchLength
;
1521 numPairs
= p
->numPairs
;
1524 numAvail
= p
->numAvail
;
1525 *backRes
= (UInt32
)-1;
1528 if (numAvail
> LZMA_MATCH_LEN_MAX
)
1529 numAvail
= LZMA_MATCH_LEN_MAX
;
1530 data
= p
->matchFinder
.GetPointerToCurrentPos(p
->matchFinderObj
) - 1;
1532 repLen
= repIndex
= 0;
1533 for (i
= 0; i
< LZMA_NUM_REPS
; i
++)
1536 const Byte
*data2
= data
- (p
->reps
[i
] + 1);
1537 if (data
[0] != data2
[0] || data
[1] != data2
[1])
1539 for (len
= 2; len
< numAvail
&& data
[len
] == data2
[len
]; len
++);
1540 if (len
>= p
->numFastBytes
)
1543 MovePos(p
, len
- 1);
1553 matches
= p
->matches
;
1554 if (mainLen
>= p
->numFastBytes
)
1556 *backRes
= matches
[numPairs
- 1] + LZMA_NUM_REPS
;
1557 MovePos(p
, mainLen
- 1);
1561 mainDist
= 0; /* for GCC */
1564 mainDist
= matches
[numPairs
- 1];
1565 while (numPairs
> 2 && mainLen
== matches
[numPairs
- 4] + 1)
1567 if (!ChangePair(matches
[numPairs
- 3], mainDist
))
1570 mainLen
= matches
[numPairs
- 2];
1571 mainDist
= matches
[numPairs
- 1];
1573 if (mainLen
== 2 && mainDist
>= 0x80)
1577 if (repLen
>= 2 && (
1578 (repLen
+ 1 >= mainLen
) ||
1579 (repLen
+ 2 >= mainLen
&& mainDist
>= (1 << 9)) ||
1580 (repLen
+ 3 >= mainLen
&& mainDist
>= (1 << 15))))
1582 *backRes
= repIndex
;
1583 MovePos(p
, repLen
- 1);
1587 if (mainLen
< 2 || numAvail
<= 2)
1590 p
->longestMatchLength
= ReadMatchDistances(p
, &p
->numPairs
);
1591 if (p
->longestMatchLength
>= 2)
1593 UInt32 newDistance
= matches
[p
->numPairs
- 1];
1594 if ((p
->longestMatchLength
>= mainLen
&& newDistance
< mainDist
) ||
1595 (p
->longestMatchLength
== mainLen
+ 1 && !ChangePair(mainDist
, newDistance
)) ||
1596 (p
->longestMatchLength
> mainLen
+ 1) ||
1597 (p
->longestMatchLength
+ 1 >= mainLen
&& mainLen
>= 3 && ChangePair(newDistance
, mainDist
)))
1601 data
= p
->matchFinder
.GetPointerToCurrentPos(p
->matchFinderObj
) - 1;
1602 for (i
= 0; i
< LZMA_NUM_REPS
; i
++)
1605 const Byte
*data2
= data
- (p
->reps
[i
] + 1);
1606 if (data
[0] != data2
[0] || data
[1] != data2
[1])
1608 limit
= mainLen
- 1;
1609 for (len
= 2; len
< limit
&& data
[len
] == data2
[len
]; len
++);
1613 *backRes
= mainDist
+ LZMA_NUM_REPS
;
1614 MovePos(p
, mainLen
- 2);
1618 static void WriteEndMarker(CLzmaEnc
*p
, UInt32 posState
)
1621 RangeEnc_EncodeBit(&p
->rc
, &p
->isMatch
[p
->state
][posState
], 1);
1622 RangeEnc_EncodeBit(&p
->rc
, &p
->isRep
[p
->state
], 0);
1623 p
->state
= kMatchNextStates
[p
->state
];
1624 len
= LZMA_MATCH_LEN_MIN
;
1625 LenEnc_Encode2(&p
->lenEnc
, &p
->rc
, len
- LZMA_MATCH_LEN_MIN
, posState
, !p
->fastMode
, p
->ProbPrices
);
1626 RcTree_Encode(&p
->rc
, p
->posSlotEncoder
[GetLenToPosState(len
)], kNumPosSlotBits
, (1 << kNumPosSlotBits
) - 1);
1627 RangeEnc_EncodeDirectBits(&p
->rc
, (((UInt32
)1 << 30) - 1) >> kNumAlignBits
, 30 - kNumAlignBits
);
1628 RcTree_ReverseEncode(&p
->rc
, p
->posAlignEncoder
, kNumAlignBits
, kAlignMask
);
1631 static SRes
CheckErrors(CLzmaEnc
*p
)
1633 if (p
->result
!= SZ_OK
)
1635 if (p
->rc
.res
!= SZ_OK
)
1636 p
->result
= SZ_ERROR_WRITE
;
1637 if (p
->matchFinderBase
.result
!= SZ_OK
)
1638 p
->result
= SZ_ERROR_READ
;
1639 if (p
->result
!= SZ_OK
)
1644 static SRes
Flush(CLzmaEnc
*p
, UInt32 nowPos
)
1646 /* ReleaseMFStream(); */
1648 if (p
->writeEndMark
)
1649 WriteEndMarker(p
, nowPos
& p
->pbMask
);
1650 RangeEnc_FlushData(&p
->rc
);
1651 RangeEnc_FlushStream(&p
->rc
);
1652 return CheckErrors(p
);
1655 static void FillAlignPrices(CLzmaEnc
*p
)
1658 for (i
= 0; i
< kAlignTableSize
; i
++)
1659 p
->alignPrices
[i
] = RcTree_ReverseGetPrice(p
->posAlignEncoder
, kNumAlignBits
, i
, p
->ProbPrices
);
1660 p
->alignPriceCount
= 0;
1663 static void FillDistancesPrices(CLzmaEnc
*p
)
1665 UInt32 tempPrices
[kNumFullDistances
];
1666 UInt32 i
, lenToPosState
;
1667 for (i
= kStartPosModelIndex
; i
< kNumFullDistances
; i
++)
1669 UInt32 posSlot
= GetPosSlot1(i
);
1670 UInt32 footerBits
= ((posSlot
>> 1) - 1);
1671 UInt32 base
= ((2 | (posSlot
& 1)) << footerBits
);
1672 tempPrices
[i
] = RcTree_ReverseGetPrice(p
->posEncoders
+ base
- posSlot
- 1, footerBits
, i
- base
, p
->ProbPrices
);
1675 for (lenToPosState
= 0; lenToPosState
< kNumLenToPosStates
; lenToPosState
++)
1678 const CLzmaProb
*encoder
= p
->posSlotEncoder
[lenToPosState
];
1679 UInt32
*posSlotPrices
= p
->posSlotPrices
[lenToPosState
];
1680 for (posSlot
= 0; posSlot
< p
->distTableSize
; posSlot
++)
1681 posSlotPrices
[posSlot
] = RcTree_GetPrice(encoder
, kNumPosSlotBits
, posSlot
, p
->ProbPrices
);
1682 for (posSlot
= kEndPosModelIndex
; posSlot
< p
->distTableSize
; posSlot
++)
1683 posSlotPrices
[posSlot
] += ((((posSlot
>> 1) - 1) - kNumAlignBits
) << kNumBitPriceShiftBits
);
1686 UInt32
*distancesPrices
= p
->distancesPrices
[lenToPosState
];
1688 for (i
= 0; i
< kStartPosModelIndex
; i
++)
1689 distancesPrices
[i
] = posSlotPrices
[i
];
1690 for (; i
< kNumFullDistances
; i
++)
1691 distancesPrices
[i
] = posSlotPrices
[GetPosSlot1(i
)] + tempPrices
[i
];
1694 p
->matchPriceCount
= 0;
1697 void LzmaEnc_Construct(CLzmaEnc
*p
)
1699 RangeEnc_Construct(&p
->rc
);
1700 MatchFinder_Construct(&p
->matchFinderBase
);
1701 #ifdef COMPRESS_MF_MT
1702 MatchFinderMt_Construct(&p
->matchFinderMt
);
1703 p
->matchFinderMt
.MatchFinder
= &p
->matchFinderBase
;
1707 CLzmaEncProps props
;
1708 LzmaEncProps_Init(&props
);
1709 LzmaEnc_SetProps(p
, &props
);
1712 #ifndef LZMA_LOG_BSR
1713 LzmaEnc_FastPosInit(p
->g_FastPos
);
1716 LzmaEnc_InitPriceTables(p
->ProbPrices
);
1718 p
->saveState
.litProbs
= 0;
1721 CLzmaEncHandle
LzmaEnc_Create(ISzAlloc
*alloc
)
1724 p
= alloc
->Alloc(alloc
, sizeof(CLzmaEnc
));
1726 LzmaEnc_Construct((CLzmaEnc
*)p
);
1730 void LzmaEnc_FreeLits(CLzmaEnc
*p
, ISzAlloc
*alloc
)
1732 alloc
->Free(alloc
, p
->litProbs
);
1733 alloc
->Free(alloc
, p
->saveState
.litProbs
);
1735 p
->saveState
.litProbs
= 0;
1738 void LzmaEnc_Destruct(CLzmaEnc
*p
, ISzAlloc
*alloc
, ISzAlloc
*allocBig
)
1740 #ifdef COMPRESS_MF_MT
1741 MatchFinderMt_Destruct(&p
->matchFinderMt
, allocBig
);
1743 MatchFinder_Free(&p
->matchFinderBase
, allocBig
);
1744 LzmaEnc_FreeLits(p
, alloc
);
1745 RangeEnc_Free(&p
->rc
, alloc
);
1748 void LzmaEnc_Destroy(CLzmaEncHandle p
, ISzAlloc
*alloc
, ISzAlloc
*allocBig
)
1750 LzmaEnc_Destruct((CLzmaEnc
*)p
, alloc
, allocBig
);
1751 alloc
->Free(alloc
, p
);
1754 static SRes
LzmaEnc_CodeOneBlock(CLzmaEnc
*p
, Bool useLimits
, UInt32 maxPackSize
, UInt32 maxUnpackSize
)
1756 UInt32 nowPos32
, startPos32
;
1757 if (p
->inStream
!= 0)
1759 p
->matchFinderBase
.stream
= p
->inStream
;
1760 p
->matchFinder
.Init(p
->matchFinderObj
);
1766 RINOK(CheckErrors(p
));
1768 nowPos32
= (UInt32
)p
->nowPos64
;
1769 startPos32
= nowPos32
;
1771 if (p
->nowPos64
== 0)
1775 if (p
->matchFinder
.GetNumAvailableBytes(p
->matchFinderObj
) == 0)
1776 return Flush(p
, nowPos32
);
1777 ReadMatchDistances(p
, &numPairs
);
1778 RangeEnc_EncodeBit(&p
->rc
, &p
->isMatch
[p
->state
][0], 0);
1779 p
->state
= kLiteralNextStates
[p
->state
];
1780 curByte
= p
->matchFinder
.GetIndexByte(p
->matchFinderObj
, 0 - p
->additionalOffset
);
1781 LitEnc_Encode(&p
->rc
, p
->litProbs
, curByte
);
1782 p
->additionalOffset
--;
1786 if (p
->matchFinder
.GetNumAvailableBytes(p
->matchFinderObj
) != 0)
1789 UInt32 pos
, len
, posState
;
1792 len
= GetOptimumFast(p
, &pos
);
1794 len
= GetOptimum(p
, nowPos32
, &pos
);
1797 printf("\n pos = %4X, len = %d pos = %d", nowPos32
, len
, pos
);
1800 posState
= nowPos32
& p
->pbMask
;
1801 if (len
== 1 && pos
== (UInt32
)-1)
1807 RangeEnc_EncodeBit(&p
->rc
, &p
->isMatch
[p
->state
][posState
], 0);
1808 data
= p
->matchFinder
.GetPointerToCurrentPos(p
->matchFinderObj
) - p
->additionalOffset
;
1810 probs
= LIT_PROBS(nowPos32
, *(data
- 1));
1811 if (IsCharState(p
->state
))
1812 LitEnc_Encode(&p
->rc
, probs
, curByte
);
1814 LitEnc_EncodeMatched(&p
->rc
, probs
, curByte
, *(data
- p
->reps
[0] - 1));
1815 p
->state
= kLiteralNextStates
[p
->state
];
1819 RangeEnc_EncodeBit(&p
->rc
, &p
->isMatch
[p
->state
][posState
], 1);
1820 if (pos
< LZMA_NUM_REPS
)
1822 RangeEnc_EncodeBit(&p
->rc
, &p
->isRep
[p
->state
], 1);
1825 RangeEnc_EncodeBit(&p
->rc
, &p
->isRepG0
[p
->state
], 0);
1826 RangeEnc_EncodeBit(&p
->rc
, &p
->isRep0Long
[p
->state
][posState
], ((len
== 1) ? 0 : 1));
1830 UInt32 distance
= p
->reps
[pos
];
1831 RangeEnc_EncodeBit(&p
->rc
, &p
->isRepG0
[p
->state
], 1);
1833 RangeEnc_EncodeBit(&p
->rc
, &p
->isRepG1
[p
->state
], 0);
1836 RangeEnc_EncodeBit(&p
->rc
, &p
->isRepG1
[p
->state
], 1);
1837 RangeEnc_EncodeBit(&p
->rc
, &p
->isRepG2
[p
->state
], pos
- 2);
1839 p
->reps
[3] = p
->reps
[2];
1840 p
->reps
[2] = p
->reps
[1];
1842 p
->reps
[1] = p
->reps
[0];
1843 p
->reps
[0] = distance
;
1846 p
->state
= kShortRepNextStates
[p
->state
];
1849 LenEnc_Encode2(&p
->repLenEnc
, &p
->rc
, len
- LZMA_MATCH_LEN_MIN
, posState
, !p
->fastMode
, p
->ProbPrices
);
1850 p
->state
= kRepNextStates
[p
->state
];
1856 RangeEnc_EncodeBit(&p
->rc
, &p
->isRep
[p
->state
], 0);
1857 p
->state
= kMatchNextStates
[p
->state
];
1858 LenEnc_Encode2(&p
->lenEnc
, &p
->rc
, len
- LZMA_MATCH_LEN_MIN
, posState
, !p
->fastMode
, p
->ProbPrices
);
1859 pos
-= LZMA_NUM_REPS
;
1860 GetPosSlot(pos
, posSlot
);
1861 RcTree_Encode(&p
->rc
, p
->posSlotEncoder
[GetLenToPosState(len
)], kNumPosSlotBits
, posSlot
);
1863 if (posSlot
>= kStartPosModelIndex
)
1865 UInt32 footerBits
= ((posSlot
>> 1) - 1);
1866 UInt32 base
= ((2 | (posSlot
& 1)) << footerBits
);
1867 UInt32 posReduced
= pos
- base
;
1869 if (posSlot
< kEndPosModelIndex
)
1870 RcTree_ReverseEncode(&p
->rc
, p
->posEncoders
+ base
- posSlot
- 1, footerBits
, posReduced
);
1873 RangeEnc_EncodeDirectBits(&p
->rc
, posReduced
>> kNumAlignBits
, footerBits
- kNumAlignBits
);
1874 RcTree_ReverseEncode(&p
->rc
, p
->posAlignEncoder
, kNumAlignBits
, posReduced
& kAlignMask
);
1875 p
->alignPriceCount
++;
1878 p
->reps
[3] = p
->reps
[2];
1879 p
->reps
[2] = p
->reps
[1];
1880 p
->reps
[1] = p
->reps
[0];
1882 p
->matchPriceCount
++;
1885 p
->additionalOffset
-= len
;
1887 if (p
->additionalOffset
== 0)
1892 if (p
->matchPriceCount
>= (1 << 7))
1893 FillDistancesPrices(p
);
1894 if (p
->alignPriceCount
>= kAlignTableSize
)
1897 if (p
->matchFinder
.GetNumAvailableBytes(p
->matchFinderObj
) == 0)
1899 processed
= nowPos32
- startPos32
;
1902 if (processed
+ kNumOpts
+ 300 >= maxUnpackSize
||
1903 RangeEnc_GetProcessed(&p
->rc
) + kNumOpts
* 2 >= maxPackSize
)
1906 else if (processed
>= (1 << 15))
1908 p
->nowPos64
+= nowPos32
- startPos32
;
1909 return CheckErrors(p
);
1913 p
->nowPos64
+= nowPos32
- startPos32
;
1914 return Flush(p
, nowPos32
);
1917 #define kBigHashDicLimit ((UInt32)1 << 24)
1919 static SRes
LzmaEnc_Alloc(CLzmaEnc
*p
, UInt32 keepWindowSize
, ISzAlloc
*alloc
, ISzAlloc
*allocBig
)
1921 UInt32 beforeSize
= kNumOpts
;
1923 if (!RangeEnc_Alloc(&p
->rc
, alloc
))
1924 return SZ_ERROR_MEM
;
1925 btMode
= (p
->matchFinderBase
.btMode
!= 0);
1926 #ifdef COMPRESS_MF_MT
1927 p
->mtMode
= (p
->multiThread
&& !p
->fastMode
&& btMode
);
1931 unsigned lclp
= p
->lc
+ p
->lp
;
1932 if (p
->litProbs
== 0 || p
->saveState
.litProbs
== 0 || p
->lclp
!= lclp
)
1934 LzmaEnc_FreeLits(p
, alloc
);
1935 p
->litProbs
= (CLzmaProb
*)alloc
->Alloc(alloc
, (0x300 << lclp
) * sizeof(CLzmaProb
));
1936 p
->saveState
.litProbs
= (CLzmaProb
*)alloc
->Alloc(alloc
, (0x300 << lclp
) * sizeof(CLzmaProb
));
1937 if (p
->litProbs
== 0 || p
->saveState
.litProbs
== 0)
1939 LzmaEnc_FreeLits(p
, alloc
);
1940 return SZ_ERROR_MEM
;
1946 p
->matchFinderBase
.bigHash
= (p
->dictSize
> kBigHashDicLimit
);
1948 if (beforeSize
+ p
->dictSize
< keepWindowSize
)
1949 beforeSize
= keepWindowSize
- p
->dictSize
;
1951 #ifdef COMPRESS_MF_MT
1954 RINOK(MatchFinderMt_Create(&p
->matchFinderMt
, p
->dictSize
, beforeSize
, p
->numFastBytes
, LZMA_MATCH_LEN_MAX
, allocBig
));
1955 p
->matchFinderObj
= &p
->matchFinderMt
;
1956 MatchFinderMt_CreateVTable(&p
->matchFinderMt
, &p
->matchFinder
);
1961 if (!MatchFinder_Create(&p
->matchFinderBase
, p
->dictSize
, beforeSize
, p
->numFastBytes
, LZMA_MATCH_LEN_MAX
, allocBig
))
1962 return SZ_ERROR_MEM
;
1963 p
->matchFinderObj
= &p
->matchFinderBase
;
1964 MatchFinder_CreateVTable(&p
->matchFinderBase
, &p
->matchFinder
);
1969 void LzmaEnc_Init(CLzmaEnc
*p
)
1973 for (i
= 0 ; i
< LZMA_NUM_REPS
; i
++)
1976 RangeEnc_Init(&p
->rc
);
1979 for (i
= 0; i
< kNumStates
; i
++)
1982 for (j
= 0; j
< LZMA_NUM_PB_STATES_MAX
; j
++)
1984 p
->isMatch
[i
][j
] = kProbInitValue
;
1985 p
->isRep0Long
[i
][j
] = kProbInitValue
;
1987 p
->isRep
[i
] = kProbInitValue
;
1988 p
->isRepG0
[i
] = kProbInitValue
;
1989 p
->isRepG1
[i
] = kProbInitValue
;
1990 p
->isRepG2
[i
] = kProbInitValue
;
1994 UInt32 num
= 0x300 << (p
->lp
+ p
->lc
);
1995 for (i
= 0; i
< num
; i
++)
1996 p
->litProbs
[i
] = kProbInitValue
;
2000 for (i
= 0; i
< kNumLenToPosStates
; i
++)
2002 CLzmaProb
*probs
= p
->posSlotEncoder
[i
];
2004 for (j
= 0; j
< (1 << kNumPosSlotBits
); j
++)
2005 probs
[j
] = kProbInitValue
;
2009 for (i
= 0; i
< kNumFullDistances
- kEndPosModelIndex
; i
++)
2010 p
->posEncoders
[i
] = kProbInitValue
;
2013 LenEnc_Init(&p
->lenEnc
.p
);
2014 LenEnc_Init(&p
->repLenEnc
.p
);
2016 for (i
= 0; i
< (1 << kNumAlignBits
); i
++)
2017 p
->posAlignEncoder
[i
] = kProbInitValue
;
2019 p
->optimumEndIndex
= 0;
2020 p
->optimumCurrentIndex
= 0;
2021 p
->additionalOffset
= 0;
2023 p
->pbMask
= (1 << p
->pb
) - 1;
2024 p
->lpMask
= (1 << p
->lp
) - 1;
2027 void LzmaEnc_InitPrices(CLzmaEnc
*p
)
2031 FillDistancesPrices(p
);
2035 p
->lenEnc
.tableSize
=
2036 p
->repLenEnc
.tableSize
=
2037 p
->numFastBytes
+ 1 - LZMA_MATCH_LEN_MIN
;
2038 LenPriceEnc_UpdateTables(&p
->lenEnc
, 1 << p
->pb
, p
->ProbPrices
);
2039 LenPriceEnc_UpdateTables(&p
->repLenEnc
, 1 << p
->pb
, p
->ProbPrices
);
2042 static SRes
LzmaEnc_AllocAndInit(CLzmaEnc
*p
, UInt32 keepWindowSize
, ISzAlloc
*alloc
, ISzAlloc
*allocBig
)
2045 for (i
= 0; i
< (UInt32
)kDicLogSizeMaxCompress
; i
++)
2046 if (p
->dictSize
<= ((UInt32
)1 << i
))
2048 p
->distTableSize
= i
* 2;
2050 p
->finished
= False
;
2052 RINOK(LzmaEnc_Alloc(p
, keepWindowSize
, alloc
, allocBig
));
2054 LzmaEnc_InitPrices(p
);
2059 static SRes
LzmaEnc_Prepare(CLzmaEncHandle pp
, ISeqInStream
*inStream
, ISeqOutStream
*outStream
,
2060 ISzAlloc
*alloc
, ISzAlloc
*allocBig
)
2062 CLzmaEnc
*p
= (CLzmaEnc
*)pp
;
2063 p
->inStream
= inStream
;
2064 p
->rc
.outStream
= outStream
;
2065 return LzmaEnc_AllocAndInit(p
, 0, alloc
, allocBig
);
2068 SRes
LzmaEnc_PrepareForLzma2(CLzmaEncHandle pp
,
2069 ISeqInStream
*inStream
, UInt32 keepWindowSize
,
2070 ISzAlloc
*alloc
, ISzAlloc
*allocBig
)
2072 CLzmaEnc
*p
= (CLzmaEnc
*)pp
;
2073 p
->inStream
= inStream
;
2074 return LzmaEnc_AllocAndInit(p
, keepWindowSize
, alloc
, allocBig
);
2077 static void LzmaEnc_SetInputBuf(CLzmaEnc
*p
, const Byte
*src
, SizeT srcLen
)
2079 p
->seqBufInStream
.funcTable
.Read
= MyRead
;
2080 p
->seqBufInStream
.data
= src
;
2081 p
->seqBufInStream
.rem
= srcLen
;
2084 SRes
LzmaEnc_MemPrepare(CLzmaEncHandle pp
, const Byte
*src
, SizeT srcLen
,
2085 UInt32 keepWindowSize
, ISzAlloc
*alloc
, ISzAlloc
*allocBig
)
2087 CLzmaEnc
*p
= (CLzmaEnc
*)pp
;
2088 LzmaEnc_SetInputBuf(p
, src
, srcLen
);
2089 p
->inStream
= &p
->seqBufInStream
.funcTable
;
2090 return LzmaEnc_AllocAndInit(p
, keepWindowSize
, alloc
, allocBig
);
2093 void LzmaEnc_Finish(CLzmaEncHandle pp
)
2095 #ifdef COMPRESS_MF_MT
2096 CLzmaEnc
*p
= (CLzmaEnc
*)pp
;
2098 MatchFinderMt_ReleaseStream(&p
->matchFinderMt
);
2104 typedef struct _CSeqOutStreamBuf
2106 ISeqOutStream funcTable
;
2112 static size_t MyWrite(void *pp
, const void *data
, size_t size
)
2114 CSeqOutStreamBuf
*p
= (CSeqOutStreamBuf
*)pp
;
2120 memcpy(p
->data
, data
, size
);
2127 UInt32
LzmaEnc_GetNumAvailableBytes(CLzmaEncHandle pp
)
2129 const CLzmaEnc
*p
= (CLzmaEnc
*)pp
;
2130 return p
->matchFinder
.GetNumAvailableBytes(p
->matchFinderObj
);
2133 const Byte
*LzmaEnc_GetCurBuf(CLzmaEncHandle pp
)
2135 const CLzmaEnc
*p
= (CLzmaEnc
*)pp
;
2136 return p
->matchFinder
.GetPointerToCurrentPos(p
->matchFinderObj
) - p
->additionalOffset
;
2139 SRes
LzmaEnc_CodeOneMemBlock(CLzmaEncHandle pp
, Bool reInit
,
2140 Byte
*dest
, size_t *destLen
, UInt32 desiredPackSize
, UInt32
*unpackSize
)
2142 CLzmaEnc
*p
= (CLzmaEnc
*)pp
;
2145 CSeqOutStreamBuf outStream
;
2147 outStream
.funcTable
.Write
= MyWrite
;
2148 outStream
.data
= dest
;
2149 outStream
.rem
= *destLen
;
2150 outStream
.overflow
= False
;
2152 p
->writeEndMark
= False
;
2153 p
->finished
= False
;
2158 LzmaEnc_InitPrices(p
);
2159 nowPos64
= p
->nowPos64
;
2160 RangeEnc_Init(&p
->rc
);
2161 p
->rc
.outStream
= &outStream
.funcTable
;
2163 res
= LzmaEnc_CodeOneBlock(p
, True
, desiredPackSize
, *unpackSize
);
2165 *unpackSize
= (UInt32
)(p
->nowPos64
- nowPos64
);
2166 *destLen
-= outStream
.rem
;
2167 if (outStream
.overflow
)
2168 return SZ_ERROR_OUTPUT_EOF
;
2173 SRes
LzmaEnc_Encode(CLzmaEncHandle pp
, ISeqOutStream
*outStream
, ISeqInStream
*inStream
, ICompressProgress
*progress
,
2174 ISzAlloc
*alloc
, ISzAlloc
*allocBig
)
2176 CLzmaEnc
*p
= (CLzmaEnc
*)pp
;
2179 #ifdef COMPRESS_MF_MT
2180 Byte allocaDummy
[0x300];
2182 for (i
= 0; i
< 16; i
++)
2183 allocaDummy
[i
] = (Byte
)i
;
2186 RINOK(LzmaEnc_Prepare(pp
, inStream
, outStream
, alloc
, allocBig
));
2190 res
= LzmaEnc_CodeOneBlock(p
, False
, 0, 0);
2191 if (res
!= SZ_OK
|| p
->finished
!= 0)
2195 res
= progress
->Progress(progress
, p
->nowPos64
, RangeEnc_GetProcessed(&p
->rc
));
2198 res
= SZ_ERROR_PROGRESS
;
2207 SRes
LzmaEnc_WriteProperties(CLzmaEncHandle pp
, Byte
*props
, SizeT
*size
)
2209 CLzmaEnc
*p
= (CLzmaEnc
*)pp
;
2211 UInt32 dictSize
= p
->dictSize
;
2212 if (*size
< LZMA_PROPS_SIZE
)
2213 return SZ_ERROR_PARAM
;
2214 *size
= LZMA_PROPS_SIZE
;
2215 props
[0] = (Byte
)((p
->pb
* 5 + p
->lp
) * 9 + p
->lc
);
2217 for (i
= 11; i
<= 30; i
++)
2219 if (dictSize
<= ((UInt32
)2 << i
))
2221 dictSize
= (2 << i
);
2224 if (dictSize
<= ((UInt32
)3 << i
))
2226 dictSize
= (3 << i
);
2231 for (i
= 0; i
< 4; i
++)
2232 props
[1 + i
] = (Byte
)(dictSize
>> (8 * i
));
2236 SRes
LzmaEnc_MemEncode(CLzmaEncHandle pp
, Byte
*dest
, SizeT
*destLen
, const Byte
*src
, SizeT srcLen
,
2237 int writeEndMark
, ICompressProgress
*progress
, ISzAlloc
*alloc
, ISzAlloc
*allocBig
)
2240 CLzmaEnc
*p
= (CLzmaEnc
*)pp
;
2242 CSeqOutStreamBuf outStream
;
2244 LzmaEnc_SetInputBuf(p
, src
, srcLen
);
2246 outStream
.funcTable
.Write
= MyWrite
;
2247 outStream
.data
= dest
;
2248 outStream
.rem
= *destLen
;
2249 outStream
.overflow
= False
;
2251 p
->writeEndMark
= writeEndMark
;
2252 res
= LzmaEnc_Encode(pp
, &outStream
.funcTable
, &p
->seqBufInStream
.funcTable
,
2253 progress
, alloc
, allocBig
);
2255 *destLen
-= outStream
.rem
;
2256 if (outStream
.overflow
)
2257 return SZ_ERROR_OUTPUT_EOF
;
2261 SRes
LzmaEncode(Byte
*dest
, SizeT
*destLen
, const Byte
*src
, SizeT srcLen
,
2262 const CLzmaEncProps
*props
, Byte
*propsEncoded
, SizeT
*propsSize
, int writeEndMark
,
2263 ICompressProgress
*progress
, ISzAlloc
*alloc
, ISzAlloc
*allocBig
)
2265 CLzmaEnc
*p
= (CLzmaEnc
*)LzmaEnc_Create(alloc
);
2268 return SZ_ERROR_MEM
;
2270 res
= LzmaEnc_SetProps(p
, props
);
2273 res
= LzmaEnc_WriteProperties(p
, propsEncoded
, propsSize
);
2275 res
= LzmaEnc_MemEncode(p
, dest
, destLen
, src
, srcLen
,
2276 writeEndMark
, progress
, alloc
, allocBig
);
2279 LzmaEnc_Destroy(p
, alloc
, allocBig
);