goat3d
view libs/openctm/liblzma/LzmaEnc.c @ 51:fa5c52ea9d59
foo
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Fri, 17 Jan 2014 18:16:09 +0200 |
| parents | |
| children |
line source
1 /* LzmaEnc.c -- LZMA Encoder
2 2009-02-02 : Igor Pavlov : Public domain */
4 #include <string.h>
6 /* #define SHOW_STAT */
7 /* #define SHOW_STAT2 */
9 #if defined(SHOW_STAT) || defined(SHOW_STAT2)
10 #include <stdio.h>
11 #endif
13 #include "LzmaEnc.h"
15 #include "LzFind.h"
16 #ifdef COMPRESS_MF_MT
17 #include "LzFindMt.h"
18 #endif
20 #ifdef SHOW_STAT
21 static int ttt = 0;
22 #endif
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)
46 {
47 p->level = 5;
48 p->dictSize = p->mc = 0;
49 p->lc = p->lp = p->pb = p->algo = p->fb = p->btMode = p->numHashBytes = p->numThreads = -1;
50 p->writeEndMark = 0;
51 }
53 void LzmaEncProps_Normalize(CLzmaEncProps *p)
54 {
55 int level = p->level;
56 if (level < 0) level = 5;
57 p->level = level;
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)
68 p->numThreads =
69 #ifdef COMPRESS_MF_MT
70 ((p->btMode && p->algo) ? 2 : 1);
71 #else
72 1;
73 #endif
74 }
76 UInt32 LzmaEncProps_GetDictSize(const CLzmaEncProps *props2)
77 {
78 CLzmaEncProps props = *props2;
79 LzmaEncProps_Normalize(&props);
80 return props.dictSize;
81 }
83 /* #define LZMA_LOG_BSR */
84 /* Define it for Intel's CPU */
87 #ifdef LZMA_LOG_BSR
89 #define kDicLogSizeMaxCompress 30
91 #define BSR2_RET(pos, res) { unsigned long i; _BitScanReverse(&i, (pos)); res = (i + i) + ((pos >> (i - 1)) & 1); }
93 static UInt32 GetPosSlot1(UInt32 pos)
94 {
95 UInt32 res;
96 BSR2_RET(pos, res);
97 return res;
98 }
99 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }
100 #define GetPosSlot(pos, res) { if (pos < 2) res = pos; else BSR2_RET(pos, res); }
102 #else
104 #define kNumLogBits (9 + (int)sizeof(size_t) / 2)
105 #define kDicLogSizeMaxCompress ((kNumLogBits - 1) * 2 + 7)
107 void LzmaEnc_FastPosInit(Byte *g_FastPos)
108 {
109 int c = 2, slotFast;
110 g_FastPos[0] = 0;
111 g_FastPos[1] = 1;
113 for (slotFast = 2; slotFast < kNumLogBits * 2; slotFast++)
114 {
115 UInt32 k = (1 << ((slotFast >> 1) - 1));
116 UInt32 j;
117 for (j = 0; j < k; j++, c++)
118 g_FastPos[c] = (Byte)slotFast;
119 }
120 }
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); }
125 /*
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; }
129 */
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); }
135 #endif
138 #define LZMA_NUM_REPS 4
140 typedef unsigned CState;
142 typedef struct _COptimal
143 {
144 UInt32 price;
146 CState state;
147 int prev1IsChar;
148 int prev2;
150 UInt32 posPrev2;
151 UInt32 backPrev2;
153 UInt32 posPrev;
154 UInt32 backPrev;
155 UInt32 backs[LZMA_NUM_REPS];
156 } COptimal;
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))
177 #ifdef _LZMA_PROB32
178 #define CLzmaProb UInt32
179 #else
180 #define CLzmaProb UInt16
181 #endif
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
204 typedef struct
205 {
206 CLzmaProb choice;
207 CLzmaProb choice2;
208 CLzmaProb low[LZMA_NUM_PB_STATES_MAX << kLenNumLowBits];
209 CLzmaProb mid[LZMA_NUM_PB_STATES_MAX << kLenNumMidBits];
210 CLzmaProb high[kLenNumHighSymbols];
211 } CLenEnc;
213 typedef struct
214 {
215 CLenEnc p;
216 UInt32 prices[LZMA_NUM_PB_STATES_MAX][kLenNumSymbolsTotal];
217 UInt32 tableSize;
218 UInt32 counters[LZMA_NUM_PB_STATES_MAX];
219 } CLenPriceEnc;
221 typedef struct _CRangeEnc
222 {
223 UInt32 range;
224 Byte cache;
225 UInt64 low;
226 UInt64 cacheSize;
227 Byte *buf;
228 Byte *bufLim;
229 Byte *bufBase;
230 ISeqOutStream *outStream;
231 UInt64 processed;
232 SRes res;
233 } CRangeEnc;
235 typedef struct _CSeqInStreamBuf
236 {
237 ISeqInStream funcTable;
238 const Byte *data;
239 SizeT rem;
240 } CSeqInStreamBuf;
242 static SRes MyRead(void *pp, void *data, size_t *size)
243 {
244 size_t curSize = *size;
245 CSeqInStreamBuf *p = (CSeqInStreamBuf *)pp;
246 if (p->rem < curSize)
247 curSize = p->rem;
248 memcpy(data, p->data, curSize);
249 p->rem -= curSize;
250 p->data += curSize;
251 *size = curSize;
252 return SZ_OK;
253 }
255 typedef struct
256 {
257 CLzmaProb *litProbs;
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];
270 CLenPriceEnc lenEnc;
271 CLenPriceEnc repLenEnc;
273 UInt32 reps[LZMA_NUM_REPS];
274 UInt32 state;
275 } CSaveState;
277 typedef struct _CLzmaEnc
278 {
279 IMatchFinder matchFinder;
280 void *matchFinderObj;
282 #ifdef COMPRESS_MF_MT
283 Bool mtMode;
284 CMatchFinderMt matchFinderMt;
285 #endif
287 CMatchFinder matchFinderBase;
289 #ifdef COMPRESS_MF_MT
290 Byte pad[128];
291 #endif
293 UInt32 optimumEndIndex;
294 UInt32 optimumCurrentIndex;
296 UInt32 longestMatchLength;
297 UInt32 numPairs;
298 UInt32 numAvail;
299 COptimal opt[kNumOpts];
301 #ifndef LZMA_LOG_BSR
302 Byte g_FastPos[1 << kNumLogBits];
303 #endif
305 UInt32 ProbPrices[kBitModelTotal >> kNumMoveReducingBits];
306 UInt32 matches[LZMA_MATCH_LEN_MAX * 2 + 2 + 1];
307 UInt32 numFastBytes;
308 UInt32 additionalOffset;
309 UInt32 reps[LZMA_NUM_REPS];
310 UInt32 state;
312 UInt32 posSlotPrices[kNumLenToPosStates][kDistTableSizeMax];
313 UInt32 distancesPrices[kNumLenToPosStates][kNumFullDistances];
314 UInt32 alignPrices[kAlignTableSize];
315 UInt32 alignPriceCount;
317 UInt32 distTableSize;
319 unsigned lc, lp, pb;
320 unsigned lpMask, pbMask;
322 CLzmaProb *litProbs;
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];
335 CLenPriceEnc lenEnc;
336 CLenPriceEnc repLenEnc;
338 unsigned lclp;
340 Bool fastMode;
342 CRangeEnc rc;
344 Bool writeEndMark;
345 UInt64 nowPos64;
346 UInt32 matchPriceCount;
347 Bool finished;
348 Bool multiThread;
350 SRes result;
351 UInt32 dictSize;
352 UInt32 matchFinderCycles;
354 ISeqInStream *inStream;
355 CSeqInStreamBuf seqBufInStream;
357 CSaveState saveState;
358 } CLzmaEnc;
360 void LzmaEnc_SaveState(CLzmaEncHandle pp)
361 {
362 CLzmaEnc *p = (CLzmaEnc *)pp;
363 CSaveState *dest = &p->saveState;
364 int i;
365 dest->lenEnc = p->lenEnc;
366 dest->repLenEnc = p->repLenEnc;
367 dest->state = p->state;
369 for (i = 0; i < kNumStates; i++)
370 {
371 memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i]));
372 memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i]));
373 }
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));
384 }
386 void LzmaEnc_RestoreState(CLzmaEncHandle pp)
387 {
388 CLzmaEnc *dest = (CLzmaEnc *)pp;
389 const CSaveState *p = &dest->saveState;
390 int i;
391 dest->lenEnc = p->lenEnc;
392 dest->repLenEnc = p->repLenEnc;
393 dest->state = p->state;
395 for (i = 0; i < kNumStates; i++)
396 {
397 memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i]));
398 memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i]));
399 }
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));
410 }
412 SRes LzmaEnc_SetProps(CLzmaEncHandle pp, const CLzmaEncProps *props2)
413 {
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 > (1U << kDicLogSizeMaxCompress) || props.dictSize > (1U << 30))
420 return SZ_ERROR_PARAM;
421 p->dictSize = props.dictSize;
422 p->matchFinderCycles = props.mc;
423 {
424 unsigned fb = props.fb;
425 if (fb < 5)
426 fb = 5;
427 if (fb > LZMA_MATCH_LEN_MAX)
428 fb = LZMA_MATCH_LEN_MAX;
429 p->numFastBytes = fb;
430 }
431 p->lc = props.lc;
432 p->lp = props.lp;
433 p->pb = props.pb;
434 p->fastMode = (props.algo == 0);
435 p->matchFinderBase.btMode = props.btMode;
436 {
437 UInt32 numHashBytes = 4;
438 if (props.btMode)
439 {
440 if (props.numHashBytes < 2)
441 numHashBytes = 2;
442 else if (props.numHashBytes < 4)
443 numHashBytes = props.numHashBytes;
444 }
445 p->matchFinderBase.numHashBytes = numHashBytes;
446 }
448 p->matchFinderBase.cutValue = props.mc;
450 p->writeEndMark = props.writeEndMark;
452 #ifdef COMPRESS_MF_MT
453 /*
454 if (newMultiThread != _multiThread)
455 {
456 ReleaseMatchFinder();
457 _multiThread = newMultiThread;
458 }
459 */
460 p->multiThread = (props.numThreads > 1);
461 #endif
463 return SZ_OK;
464 }
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)
478 {
479 p->outStream = 0;
480 p->bufBase = 0;
481 }
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)
487 {
488 if (p->bufBase == 0)
489 {
490 p->bufBase = (Byte *)alloc->Alloc(alloc, RC_BUF_SIZE);
491 if (p->bufBase == 0)
492 return 0;
493 p->bufLim = p->bufBase + RC_BUF_SIZE;
494 }
495 return 1;
496 }
498 static void RangeEnc_Free(CRangeEnc *p, ISzAlloc *alloc)
499 {
500 alloc->Free(alloc, p->bufBase);
501 p->bufBase = 0;
502 }
504 static void RangeEnc_Init(CRangeEnc *p)
505 {
506 /* Stream.Init(); */
507 p->low = 0;
508 p->range = 0xFFFFFFFF;
509 p->cacheSize = 1;
510 p->cache = 0;
512 p->buf = p->bufBase;
514 p->processed = 0;
515 p->res = SZ_OK;
516 }
518 static void RangeEnc_FlushStream(CRangeEnc *p)
519 {
520 size_t num;
521 if (p->res != SZ_OK)
522 return;
523 num = p->buf - p->bufBase;
524 if (num != p->outStream->Write(p->outStream, p->bufBase, num))
525 p->res = SZ_ERROR_WRITE;
526 p->processed += num;
527 p->buf = p->bufBase;
528 }
530 static void MY_FAST_CALL RangeEnc_ShiftLow(CRangeEnc *p)
531 {
532 if ((UInt32)p->low < (UInt32)0xFF000000 || (int)(p->low >> 32) != 0)
533 {
534 Byte temp = p->cache;
535 do
536 {
537 Byte *buf = p->buf;
538 *buf++ = (Byte)(temp + (Byte)(p->low >> 32));
539 p->buf = buf;
540 if (buf == p->bufLim)
541 RangeEnc_FlushStream(p);
542 temp = 0xFF;
543 }
544 while (--p->cacheSize != 0);
545 p->cache = (Byte)((UInt32)p->low >> 24);
546 }
547 p->cacheSize++;
548 p->low = (UInt32)p->low << 8;
549 }
551 static void RangeEnc_FlushData(CRangeEnc *p)
552 {
553 int i;
554 for (i = 0; i < 5; i++)
555 RangeEnc_ShiftLow(p);
556 }
558 static void RangeEnc_EncodeDirectBits(CRangeEnc *p, UInt32 value, int numBits)
559 {
560 do
561 {
562 p->range >>= 1;
563 p->low += p->range & (0 - ((value >> --numBits) & 1));
564 if (p->range < kTopValue)
565 {
566 p->range <<= 8;
567 RangeEnc_ShiftLow(p);
568 }
569 }
570 while (numBits != 0);
571 }
573 static void RangeEnc_EncodeBit(CRangeEnc *p, CLzmaProb *prob, UInt32 symbol)
574 {
575 UInt32 ttt = *prob;
576 UInt32 newBound = (p->range >> kNumBitModelTotalBits) * ttt;
577 if (symbol == 0)
578 {
579 p->range = newBound;
580 ttt += (kBitModelTotal - ttt) >> kNumMoveBits;
581 }
582 else
583 {
584 p->low += newBound;
585 p->range -= newBound;
586 ttt -= ttt >> kNumMoveBits;
587 }
588 *prob = (CLzmaProb)ttt;
589 if (p->range < kTopValue)
590 {
591 p->range <<= 8;
592 RangeEnc_ShiftLow(p);
593 }
594 }
596 static void LitEnc_Encode(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol)
597 {
598 symbol |= 0x100;
599 do
600 {
601 RangeEnc_EncodeBit(p, probs + (symbol >> 8), (symbol >> 7) & 1);
602 symbol <<= 1;
603 }
604 while (symbol < 0x10000);
605 }
607 static void LitEnc_EncodeMatched(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol, UInt32 matchByte)
608 {
609 UInt32 offs = 0x100;
610 symbol |= 0x100;
611 do
612 {
613 matchByte <<= 1;
614 RangeEnc_EncodeBit(p, probs + (offs + (matchByte & offs) + (symbol >> 8)), (symbol >> 7) & 1);
615 symbol <<= 1;
616 offs &= ~(matchByte ^ symbol);
617 }
618 while (symbol < 0x10000);
619 }
621 void LzmaEnc_InitPriceTables(UInt32 *ProbPrices)
622 {
623 UInt32 i;
624 for (i = (1 << kNumMoveReducingBits) / 2; i < kBitModelTotal; i += (1 << kNumMoveReducingBits))
625 {
626 const int kCyclesBits = kNumBitPriceShiftBits;
627 UInt32 w = i;
628 UInt32 bitCount = 0;
629 int j;
630 for (j = 0; j < kCyclesBits; j++)
631 {
632 w = w * w;
633 bitCount <<= 1;
634 while (w >= ((UInt32)1 << 16))
635 {
636 w >>= 1;
637 bitCount++;
638 }
639 }
640 ProbPrices[i >> kNumMoveReducingBits] = ((kNumBitModelTotalBits << kCyclesBits) - 15 - bitCount);
641 }
642 }
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)
658 {
659 UInt32 price = 0;
660 symbol |= 0x100;
661 do
662 {
663 price += GET_PRICEa(probs[symbol >> 8], (symbol >> 7) & 1);
664 symbol <<= 1;
665 }
666 while (symbol < 0x10000);
667 return price;
668 }
670 static UInt32 LitEnc_GetPriceMatched(const CLzmaProb *probs, UInt32 symbol, UInt32 matchByte, UInt32 *ProbPrices)
671 {
672 UInt32 price = 0;
673 UInt32 offs = 0x100;
674 symbol |= 0x100;
675 do
676 {
677 matchByte <<= 1;
678 price += GET_PRICEa(probs[offs + (matchByte & offs) + (symbol >> 8)], (symbol >> 7) & 1);
679 symbol <<= 1;
680 offs &= ~(matchByte ^ symbol);
681 }
682 while (symbol < 0x10000);
683 return price;
684 }
687 static void RcTree_Encode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol)
688 {
689 UInt32 m = 1;
690 int i;
691 for (i = numBitLevels; i != 0;)
692 {
693 UInt32 bit;
694 i--;
695 bit = (symbol >> i) & 1;
696 RangeEnc_EncodeBit(rc, probs + m, bit);
697 m = (m << 1) | bit;
698 }
699 }
701 static void RcTree_ReverseEncode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol)
702 {
703 UInt32 m = 1;
704 int i;
705 for (i = 0; i < numBitLevels; i++)
706 {
707 UInt32 bit = symbol & 1;
708 RangeEnc_EncodeBit(rc, probs + m, bit);
709 m = (m << 1) | bit;
710 symbol >>= 1;
711 }
712 }
714 static UInt32 RcTree_GetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, UInt32 *ProbPrices)
715 {
716 UInt32 price = 0;
717 symbol |= (1 << numBitLevels);
718 while (symbol != 1)
719 {
720 price += GET_PRICEa(probs[symbol >> 1], symbol & 1);
721 symbol >>= 1;
722 }
723 return price;
724 }
726 static UInt32 RcTree_ReverseGetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, UInt32 *ProbPrices)
727 {
728 UInt32 price = 0;
729 UInt32 m = 1;
730 int i;
731 for (i = numBitLevels; i != 0; i--)
732 {
733 UInt32 bit = symbol & 1;
734 symbol >>= 1;
735 price += GET_PRICEa(probs[m], bit);
736 m = (m << 1) | bit;
737 }
738 return price;
739 }
742 static void LenEnc_Init(CLenEnc *p)
743 {
744 unsigned i;
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;
752 }
754 static void LenEnc_Encode(CLenEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState)
755 {
756 if (symbol < kLenNumLowSymbols)
757 {
758 RangeEnc_EncodeBit(rc, &p->choice, 0);
759 RcTree_Encode(rc, p->low + (posState << kLenNumLowBits), kLenNumLowBits, symbol);
760 }
761 else
762 {
763 RangeEnc_EncodeBit(rc, &p->choice, 1);
764 if (symbol < kLenNumLowSymbols + kLenNumMidSymbols)
765 {
766 RangeEnc_EncodeBit(rc, &p->choice2, 0);
767 RcTree_Encode(rc, p->mid + (posState << kLenNumMidBits), kLenNumMidBits, symbol - kLenNumLowSymbols);
768 }
769 else
770 {
771 RangeEnc_EncodeBit(rc, &p->choice2, 1);
772 RcTree_Encode(rc, p->high, kLenNumHighBits, symbol - kLenNumLowSymbols - kLenNumMidSymbols);
773 }
774 }
775 }
777 static void LenEnc_SetPrices(CLenEnc *p, UInt32 posState, UInt32 numSymbols, UInt32 *prices, UInt32 *ProbPrices)
778 {
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);
783 UInt32 i = 0;
784 for (i = 0; i < kLenNumLowSymbols; i++)
785 {
786 if (i >= numSymbols)
787 return;
788 prices[i] = a0 + RcTree_GetPrice(p->low + (posState << kLenNumLowBits), kLenNumLowBits, i, ProbPrices);
789 }
790 for (; i < kLenNumLowSymbols + kLenNumMidSymbols; i++)
791 {
792 if (i >= numSymbols)
793 return;
794 prices[i] = b0 + RcTree_GetPrice(p->mid + (posState << kLenNumMidBits), kLenNumMidBits, i - kLenNumLowSymbols, ProbPrices);
795 }
796 for (; i < numSymbols; i++)
797 prices[i] = b1 + RcTree_GetPrice(p->high, kLenNumHighBits, i - kLenNumLowSymbols - kLenNumMidSymbols, ProbPrices);
798 }
800 static void MY_FAST_CALL LenPriceEnc_UpdateTable(CLenPriceEnc *p, UInt32 posState, UInt32 *ProbPrices)
801 {
802 LenEnc_SetPrices(&p->p, posState, p->tableSize, p->prices[posState], ProbPrices);
803 p->counters[posState] = p->tableSize;
804 }
806 static void LenPriceEnc_UpdateTables(CLenPriceEnc *p, UInt32 numPosStates, UInt32 *ProbPrices)
807 {
808 UInt32 posState;
809 for (posState = 0; posState < numPosStates; posState++)
810 LenPriceEnc_UpdateTable(p, posState, ProbPrices);
811 }
813 static void LenEnc_Encode2(CLenPriceEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState, Bool updatePrice, UInt32 *ProbPrices)
814 {
815 LenEnc_Encode(&p->p, rc, symbol, posState);
816 if (updatePrice)
817 if (--p->counters[posState] == 0)
818 LenPriceEnc_UpdateTable(p, posState, ProbPrices);
819 }
824 static void MovePos(CLzmaEnc *p, UInt32 num)
825 {
826 #ifdef SHOW_STAT
827 ttt += num;
828 printf("\n MovePos %d", num);
829 #endif
830 if (num != 0)
831 {
832 p->additionalOffset += num;
833 p->matchFinder.Skip(p->matchFinderObj, num);
834 }
835 }
837 static UInt32 ReadMatchDistances(CLzmaEnc *p, UInt32 *numDistancePairsRes)
838 {
839 UInt32 lenRes = 0, numPairs;
840 p->numAvail = p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);
841 numPairs = p->matchFinder.GetMatches(p->matchFinderObj, p->matches);
842 #ifdef SHOW_STAT
843 printf("\n i = %d numPairs = %d ", ttt, numPairs / 2);
844 ttt++;
845 {
846 UInt32 i;
847 for (i = 0; i < numPairs; i += 2)
848 printf("%2d %6d | ", p->matches[i], p->matches[i + 1]);
849 }
850 #endif
851 if (numPairs > 0)
852 {
853 lenRes = p->matches[numPairs - 2];
854 if (lenRes == p->numFastBytes)
855 {
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;
861 {
862 const Byte *pby2 = pby - distance;
863 for (; lenRes < numAvail && pby[lenRes] == pby2[lenRes]; lenRes++);
864 }
865 }
866 }
867 p->additionalOffset++;
868 *numDistancePairsRes = numPairs;
869 return lenRes;
870 }
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)
878 {
879 return
880 GET_PRICE_0(p->isRepG0[state]) +
881 GET_PRICE_0(p->isRep0Long[state][posState]);
882 }
884 static UInt32 GetPureRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 state, UInt32 posState)
885 {
886 UInt32 price;
887 if (repIndex == 0)
888 {
889 price = GET_PRICE_0(p->isRepG0[state]);
890 price += GET_PRICE_1(p->isRep0Long[state][posState]);
891 }
892 else
893 {
894 price = GET_PRICE_1(p->isRepG0[state]);
895 if (repIndex == 1)
896 price += GET_PRICE_0(p->isRepG1[state]);
897 else
898 {
899 price += GET_PRICE_1(p->isRepG1[state]);
900 price += GET_PRICE(p->isRepG2[state], repIndex - 2);
901 }
902 }
903 return price;
904 }
906 static UInt32 GetRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 len, UInt32 state, UInt32 posState)
907 {
908 return p->repLenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN] +
909 GetPureRepPrice(p, repIndex, state, posState);
910 }
912 static UInt32 Backward(CLzmaEnc *p, UInt32 *backRes, UInt32 cur)
913 {
914 UInt32 posMem = p->opt[cur].posPrev;
915 UInt32 backMem = p->opt[cur].backPrev;
916 p->optimumEndIndex = cur;
917 do
918 {
919 if (p->opt[cur].prev1IsChar)
920 {
921 MakeAsChar(&p->opt[posMem])
922 p->opt[posMem].posPrev = posMem - 1;
923 if (p->opt[cur].prev2)
924 {
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;
928 }
929 }
930 {
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;
939 cur = posPrev;
940 }
941 }
942 while (cur != 0);
943 *backRes = p->opt[0].backPrev;
944 p->optimumCurrentIndex = p->opt[0].posPrev;
945 return p->optimumCurrentIndex;
946 }
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)
951 {
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];
955 UInt32 *matches;
956 const Byte *data;
957 Byte curByte, matchByte;
958 if (p->optimumEndIndex != p->optimumCurrentIndex)
959 {
960 const COptimal *opt = &p->opt[p->optimumCurrentIndex];
961 UInt32 lenRes = opt->posPrev - p->optimumCurrentIndex;
962 *backRes = opt->backPrev;
963 p->optimumCurrentIndex = opt->posPrev;
964 return lenRes;
965 }
966 p->optimumCurrentIndex = p->optimumEndIndex = 0;
968 if (p->additionalOffset == 0)
969 mainLen = ReadMatchDistances(p, &numPairs);
970 else
971 {
972 mainLen = p->longestMatchLength;
973 numPairs = p->numPairs;
974 }
976 numAvail = p->numAvail;
977 if (numAvail < 2)
978 {
979 *backRes = (UInt32)(-1);
980 return 1;
981 }
982 if (numAvail > LZMA_MATCH_LEN_MAX)
983 numAvail = LZMA_MATCH_LEN_MAX;
985 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
986 repMaxIndex = 0;
987 for (i = 0; i < LZMA_NUM_REPS; i++)
988 {
989 UInt32 lenTest;
990 const Byte *data2;
991 reps[i] = p->reps[i];
992 data2 = data - (reps[i] + 1);
993 if (data[0] != data2[0] || data[1] != data2[1])
994 {
995 repLens[i] = 0;
996 continue;
997 }
998 for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; lenTest++);
999 repLens[i] = lenTest;
1000 if (lenTest > repLens[repMaxIndex])
1001 repMaxIndex = i;
1002 }
1003 if (repLens[repMaxIndex] >= p->numFastBytes)
1004 {
1005 UInt32 lenRes;
1006 *backRes = repMaxIndex;
1007 lenRes = repLens[repMaxIndex];
1008 MovePos(p, lenRes - 1);
1009 return lenRes;
1010 }
1012 matches = p->matches;
1013 if (mainLen >= p->numFastBytes)
1014 {
1015 *backRes = matches[numPairs - 1] + LZMA_NUM_REPS;
1016 MovePos(p, mainLen - 1);
1017 return mainLen;
1018 }
1019 curByte = *data;
1020 matchByte = *(data - (reps[0] + 1));
1022 if (mainLen < 2 && curByte != matchByte && repLens[repMaxIndex] < 2)
1023 {
1024 *backRes = (UInt32)-1;
1025 return 1;
1026 }
1028 p->opt[0].state = (CState)p->state;
1030 posState = (position & p->pbMask);
1032 {
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));
1038 }
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)
1046 {
1047 UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, p->state, posState);
1048 if (shortRepPrice < p->opt[1].price)
1049 {
1050 p->opt[1].price = shortRepPrice;
1051 MakeAsShortRep(&p->opt[1]);
1052 }
1053 }
1054 lenEnd = ((mainLen >= repLens[repMaxIndex]) ? mainLen : repLens[repMaxIndex]);
1056 if (lenEnd < 2)
1057 {
1058 *backRes = p->opt[1].backPrev;
1059 return 1;
1060 }
1062 p->opt[1].posPrev = 0;
1063 for (i = 0; i < LZMA_NUM_REPS; i++)
1064 p->opt[0].backs[i] = reps[i];
1066 len = lenEnd;
1067 do
1068 p->opt[len--].price = kInfinityPrice;
1069 while (len >= 2);
1071 for (i = 0; i < LZMA_NUM_REPS; i++)
1072 {
1073 UInt32 repLen = repLens[i];
1074 UInt32 price;
1075 if (repLen < 2)
1076 continue;
1077 price = repMatchPrice + GetPureRepPrice(p, i, p->state, posState);
1078 do
1079 {
1080 UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][repLen - 2];
1081 COptimal *opt = &p->opt[repLen];
1082 if (curAndLenPrice < opt->price)
1083 {
1084 opt->price = curAndLenPrice;
1085 opt->posPrev = 0;
1086 opt->backPrev = i;
1087 opt->prev1IsChar = False;
1088 }
1089 }
1090 while (--repLen >= 2);
1091 }
1093 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[p->state]);
1095 len = ((repLens[0] >= 2) ? repLens[0] + 1 : 2);
1096 if (len <= mainLen)
1097 {
1098 UInt32 offs = 0;
1099 while (len > matches[offs])
1100 offs += 2;
1101 for (; ; len++)
1102 {
1103 COptimal *opt;
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];
1110 else
1111 {
1112 UInt32 slot;
1113 GetPosSlot2(distance, slot);
1114 curAndLenPrice += p->alignPrices[distance & kAlignMask] + p->posSlotPrices[lenToPosState][slot];
1115 }
1116 opt = &p->opt[len];
1117 if (curAndLenPrice < opt->price)
1118 {
1119 opt->price = curAndLenPrice;
1120 opt->posPrev = 0;
1121 opt->backPrev = distance + LZMA_NUM_REPS;
1122 opt->prev1IsChar = False;
1123 }
1124 if (len == matches[offs])
1125 {
1126 offs += 2;
1127 if (offs == numPairs)
1128 break;
1129 }
1130 }
1131 }
1133 cur = 0;
1135 #ifdef SHOW_STAT2
1136 if (position >= 0)
1137 {
1138 unsigned i;
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);
1142 }
1143 #endif
1145 for (;;)
1146 {
1147 UInt32 numAvailFull, newLen, numPairs, posPrev, state, posState, startLen;
1148 UInt32 curPrice, curAnd1Price, matchPrice, repMatchPrice;
1149 Bool nextIsChar;
1150 Byte curByte, matchByte;
1151 const Byte *data;
1152 COptimal *curOpt;
1153 COptimal *nextOpt;
1155 cur++;
1156 if (cur == lenEnd)
1157 return Backward(p, backRes, cur);
1159 newLen = ReadMatchDistances(p, &numPairs);
1160 if (newLen >= p->numFastBytes)
1161 {
1162 p->numPairs = numPairs;
1163 p->longestMatchLength = newLen;
1164 return Backward(p, backRes, cur);
1165 }
1166 position++;
1167 curOpt = &p->opt[cur];
1168 posPrev = curOpt->posPrev;
1169 if (curOpt->prev1IsChar)
1170 {
1171 posPrev--;
1172 if (curOpt->prev2)
1173 {
1174 state = p->opt[curOpt->posPrev2].state;
1175 if (curOpt->backPrev2 < LZMA_NUM_REPS)
1176 state = kRepNextStates[state];
1177 else
1178 state = kMatchNextStates[state];
1179 }
1180 else
1181 state = p->opt[posPrev].state;
1182 state = kLiteralNextStates[state];
1183 }
1184 else
1185 state = p->opt[posPrev].state;
1186 if (posPrev == cur - 1)
1187 {
1188 if (IsShortRep(curOpt))
1189 state = kShortRepNextStates[state];
1190 else
1191 state = kLiteralNextStates[state];
1192 }
1193 else
1194 {
1195 UInt32 pos;
1196 const COptimal *prevOpt;
1197 if (curOpt->prev1IsChar && curOpt->prev2)
1198 {
1199 posPrev = curOpt->posPrev2;
1200 pos = curOpt->backPrev2;
1201 state = kRepNextStates[state];
1202 }
1203 else
1204 {
1205 pos = curOpt->backPrev;
1206 if (pos < LZMA_NUM_REPS)
1207 state = kRepNextStates[state];
1208 else
1209 state = kMatchNextStates[state];
1210 }
1211 prevOpt = &p->opt[posPrev];
1212 if (pos < LZMA_NUM_REPS)
1213 {
1214 UInt32 i;
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];
1220 }
1221 else
1222 {
1223 UInt32 i;
1224 reps[0] = (pos - LZMA_NUM_REPS);
1225 for (i = 1; i < LZMA_NUM_REPS; i++)
1226 reps[i] = prevOpt->backs[i - 1];
1227 }
1228 }
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;
1237 nextIsChar = False;
1238 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1239 curByte = *data;
1240 matchByte = *(data - (reps[0] + 1));
1242 posState = (position & p->pbMask);
1244 curAnd1Price = curPrice + GET_PRICE_0(p->isMatch[state][posState]);
1245 {
1246 const CLzmaProb *probs = LIT_PROBS(position, *(data - 1));
1247 curAnd1Price +=
1248 (!IsCharState(state) ?
1249 LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) :
1250 LitEnc_GetPrice(probs, curByte, p->ProbPrices));
1251 }
1253 nextOpt = &p->opt[cur + 1];
1255 if (curAnd1Price < nextOpt->price)
1256 {
1257 nextOpt->price = curAnd1Price;
1258 nextOpt->posPrev = cur;
1259 MakeAsChar(nextOpt);
1260 nextIsChar = True;
1261 }
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))
1267 {
1268 UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, state, posState);
1269 if (shortRepPrice <= nextOpt->price)
1270 {
1271 nextOpt->price = shortRepPrice;
1272 nextOpt->posPrev = cur;
1273 MakeAsShortRep(nextOpt);
1274 nextIsChar = True;
1275 }
1276 }
1277 numAvailFull = p->numAvail;
1278 {
1279 UInt32 temp = kNumOpts - 1 - cur;
1280 if (temp < numAvailFull)
1281 numAvailFull = temp;
1282 }
1284 if (numAvailFull < 2)
1285 continue;
1286 numAvail = (numAvailFull <= p->numFastBytes ? numAvailFull : p->numFastBytes);
1288 if (!nextIsChar && matchByte != curByte) /* speed optimization */
1289 {
1290 /* try Literal + rep0 */
1291 UInt32 temp;
1292 UInt32 lenTest2;
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;
1300 if (lenTest2 >= 2)
1301 {
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--) */
1308 {
1309 UInt32 curAndLenPrice;
1310 COptimal *opt;
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)
1317 {
1318 opt->price = curAndLenPrice;
1319 opt->posPrev = cur + 1;
1320 opt->backPrev = 0;
1321 opt->prev1IsChar = True;
1322 opt->prev2 = False;
1323 }
1324 }
1325 }
1326 }
1328 startLen = 2; /* speed optimization */
1329 {
1330 UInt32 repIndex;
1331 for (repIndex = 0; repIndex < LZMA_NUM_REPS; repIndex++)
1332 {
1333 UInt32 lenTest;
1334 UInt32 lenTestTemp;
1335 UInt32 price;
1336 const Byte *data2 = data - (reps[repIndex] + 1);
1337 if (data[0] != data2[0] || data[1] != data2[1])
1338 continue;
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);
1344 do
1345 {
1346 UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][lenTest - 2];
1347 COptimal *opt = &p->opt[cur + lenTest];
1348 if (curAndLenPrice < opt->price)
1349 {
1350 opt->price = curAndLenPrice;
1351 opt->posPrev = cur;
1352 opt->backPrev = repIndex;
1353 opt->prev1IsChar = False;
1354 }
1355 }
1356 while (--lenTest >= 2);
1357 lenTest = lenTestTemp;
1359 if (repIndex == 0)
1360 startLen = lenTest + 1;
1362 /* if (_maxMode) */
1363 {
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;
1371 if (lenTest2 >= 2)
1372 {
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--) */
1387 {
1388 UInt32 curAndLenPrice;
1389 COptimal *opt;
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)
1396 {
1397 opt->price = curAndLenPrice;
1398 opt->posPrev = cur + lenTest + 1;
1399 opt->backPrev = 0;
1400 opt->prev1IsChar = True;
1401 opt->prev2 = True;
1402 opt->posPrev2 = cur;
1403 opt->backPrev2 = repIndex;
1404 }
1405 }
1406 }
1407 }
1408 }
1409 }
1410 /* for (UInt32 lenTest = 2; lenTest <= newLen; lenTest++) */
1411 if (newLen > numAvail)
1412 {
1413 newLen = numAvail;
1414 for (numPairs = 0; newLen > matches[numPairs]; numPairs += 2);
1415 matches[numPairs] = newLen;
1416 numPairs += 2;
1417 }
1418 if (newLen >= startLen)
1419 {
1420 UInt32 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[state]);
1421 UInt32 offs, curBack, posSlot;
1422 UInt32 lenTest;
1423 while (lenEnd < cur + newLen)
1424 p->opt[++lenEnd].price = kInfinityPrice;
1426 offs = 0;
1427 while (startLen > matches[offs])
1428 offs += 2;
1429 curBack = matches[offs + 1];
1430 GetPosSlot2(curBack, posSlot);
1431 for (lenTest = /*2*/ startLen; ; lenTest++)
1432 {
1433 UInt32 curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][lenTest - LZMA_MATCH_LEN_MIN];
1434 UInt32 lenToPosState = GetLenToPosState(lenTest);
1435 COptimal *opt;
1436 if (curBack < kNumFullDistances)
1437 curAndLenPrice += p->distancesPrices[lenToPosState][curBack];
1438 else
1439 curAndLenPrice += p->posSlotPrices[lenToPosState][posSlot] + p->alignPrices[curBack & kAlignMask];
1441 opt = &p->opt[cur + lenTest];
1442 if (curAndLenPrice < opt->price)
1443 {
1444 opt->price = curAndLenPrice;
1445 opt->posPrev = cur;
1446 opt->backPrev = curBack + LZMA_NUM_REPS;
1447 opt->prev1IsChar = False;
1448 }
1450 if (/*_maxMode && */lenTest == matches[offs])
1451 {
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;
1461 if (lenTest2 >= 2)
1462 {
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--) */
1476 {
1477 UInt32 offset = cur + lenTest + 1 + lenTest2;
1478 UInt32 curAndLenPrice;
1479 COptimal *opt;
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)
1485 {
1486 opt->price = curAndLenPrice;
1487 opt->posPrev = cur + lenTest + 1;
1488 opt->backPrev = 0;
1489 opt->prev1IsChar = True;
1490 opt->prev2 = True;
1491 opt->posPrev2 = cur;
1492 opt->backPrev2 = curBack + LZMA_NUM_REPS;
1493 }
1494 }
1495 }
1496 offs += 2;
1497 if (offs == numPairs)
1498 break;
1499 curBack = matches[offs + 1];
1500 if (curBack >= kNumFullDistances)
1501 GetPosSlot2(curBack, posSlot);
1502 }
1503 }
1504 }
1505 }
1506 }
1508 #define ChangePair(smallDist, bigDist) (((bigDist) >> 7) > (smallDist))
1510 static UInt32 GetOptimumFast(CLzmaEnc *p, UInt32 *backRes)
1511 {
1512 UInt32 numAvail, mainLen, mainDist, numPairs, repIndex, repLen, i;
1513 const Byte *data;
1514 const UInt32 *matches;
1516 if (p->additionalOffset == 0)
1517 mainLen = ReadMatchDistances(p, &numPairs);
1518 else
1519 {
1520 mainLen = p->longestMatchLength;
1521 numPairs = p->numPairs;
1522 }
1524 numAvail = p->numAvail;
1525 *backRes = (UInt32)-1;
1526 if (numAvail < 2)
1527 return 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++)
1534 {
1535 UInt32 len;
1536 const Byte *data2 = data - (p->reps[i] + 1);
1537 if (data[0] != data2[0] || data[1] != data2[1])
1538 continue;
1539 for (len = 2; len < numAvail && data[len] == data2[len]; len++);
1540 if (len >= p->numFastBytes)
1541 {
1542 *backRes = i;
1543 MovePos(p, len - 1);
1544 return len;
1545 }
1546 if (len > repLen)
1547 {
1548 repIndex = i;
1549 repLen = len;
1550 }
1551 }
1553 matches = p->matches;
1554 if (mainLen >= p->numFastBytes)
1555 {
1556 *backRes = matches[numPairs - 1] + LZMA_NUM_REPS;
1557 MovePos(p, mainLen - 1);
1558 return mainLen;
1559 }
1561 mainDist = 0; /* for GCC */
1562 if (mainLen >= 2)
1563 {
1564 mainDist = matches[numPairs - 1];
1565 while (numPairs > 2 && mainLen == matches[numPairs - 4] + 1)
1566 {
1567 if (!ChangePair(matches[numPairs - 3], mainDist))
1568 break;
1569 numPairs -= 2;
1570 mainLen = matches[numPairs - 2];
1571 mainDist = matches[numPairs - 1];
1572 }
1573 if (mainLen == 2 && mainDist >= 0x80)
1574 mainLen = 1;
1575 }
1577 if (repLen >= 2 && (
1578 (repLen + 1 >= mainLen) ||
1579 (repLen + 2 >= mainLen && mainDist >= (1 << 9)) ||
1580 (repLen + 3 >= mainLen && mainDist >= (1 << 15))))
1581 {
1582 *backRes = repIndex;
1583 MovePos(p, repLen - 1);
1584 return repLen;
1585 }
1587 if (mainLen < 2 || numAvail <= 2)
1588 return 1;
1590 p->longestMatchLength = ReadMatchDistances(p, &p->numPairs);
1591 if (p->longestMatchLength >= 2)
1592 {
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)))
1598 return 1;
1599 }
1601 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1602 for (i = 0; i < LZMA_NUM_REPS; i++)
1603 {
1604 UInt32 len, limit;
1605 const Byte *data2 = data - (p->reps[i] + 1);
1606 if (data[0] != data2[0] || data[1] != data2[1])
1607 continue;
1608 limit = mainLen - 1;
1609 for (len = 2; len < limit && data[len] == data2[len]; len++);
1610 if (len >= limit)
1611 return 1;
1612 }
1613 *backRes = mainDist + LZMA_NUM_REPS;
1614 MovePos(p, mainLen - 2);
1615 return mainLen;
1616 }
1618 static void WriteEndMarker(CLzmaEnc *p, UInt32 posState)
1619 {
1620 UInt32 len;
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);
1629 }
1631 static SRes CheckErrors(CLzmaEnc *p)
1632 {
1633 if (p->result != SZ_OK)
1634 return p->result;
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)
1640 p->finished = True;
1641 return p->result;
1642 }
1644 static SRes Flush(CLzmaEnc *p, UInt32 nowPos)
1645 {
1646 /* ReleaseMFStream(); */
1647 p->finished = True;
1648 if (p->writeEndMark)
1649 WriteEndMarker(p, nowPos & p->pbMask);
1650 RangeEnc_FlushData(&p->rc);
1651 RangeEnc_FlushStream(&p->rc);
1652 return CheckErrors(p);
1653 }
1655 static void FillAlignPrices(CLzmaEnc *p)
1656 {
1657 UInt32 i;
1658 for (i = 0; i < kAlignTableSize; i++)
1659 p->alignPrices[i] = RcTree_ReverseGetPrice(p->posAlignEncoder, kNumAlignBits, i, p->ProbPrices);
1660 p->alignPriceCount = 0;
1661 }
1663 static void FillDistancesPrices(CLzmaEnc *p)
1664 {
1665 UInt32 tempPrices[kNumFullDistances];
1666 UInt32 i, lenToPosState;
1667 for (i = kStartPosModelIndex; i < kNumFullDistances; i++)
1668 {
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);
1673 }
1675 for (lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++)
1676 {
1677 UInt32 posSlot;
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);
1685 {
1686 UInt32 *distancesPrices = p->distancesPrices[lenToPosState];
1687 UInt32 i;
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];
1692 }
1693 }
1694 p->matchPriceCount = 0;
1695 }
1697 void LzmaEnc_Construct(CLzmaEnc *p)
1698 {
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;
1704 #endif
1706 {
1707 CLzmaEncProps props;
1708 LzmaEncProps_Init(&props);
1709 LzmaEnc_SetProps(p, &props);
1710 }
1712 #ifndef LZMA_LOG_BSR
1713 LzmaEnc_FastPosInit(p->g_FastPos);
1714 #endif
1716 LzmaEnc_InitPriceTables(p->ProbPrices);
1717 p->litProbs = 0;
1718 p->saveState.litProbs = 0;
1719 }
1721 CLzmaEncHandle LzmaEnc_Create(ISzAlloc *alloc)
1722 {
1723 void *p;
1724 p = alloc->Alloc(alloc, sizeof(CLzmaEnc));
1725 if (p != 0)
1726 LzmaEnc_Construct((CLzmaEnc *)p);
1727 return p;
1728 }
1730 void LzmaEnc_FreeLits(CLzmaEnc *p, ISzAlloc *alloc)
1731 {
1732 alloc->Free(alloc, p->litProbs);
1733 alloc->Free(alloc, p->saveState.litProbs);
1734 p->litProbs = 0;
1735 p->saveState.litProbs = 0;
1736 }
1738 void LzmaEnc_Destruct(CLzmaEnc *p, ISzAlloc *alloc, ISzAlloc *allocBig)
1739 {
1740 #ifdef COMPRESS_MF_MT
1741 MatchFinderMt_Destruct(&p->matchFinderMt, allocBig);
1742 #endif
1743 MatchFinder_Free(&p->matchFinderBase, allocBig);
1744 LzmaEnc_FreeLits(p, alloc);
1745 RangeEnc_Free(&p->rc, alloc);
1746 }
1748 void LzmaEnc_Destroy(CLzmaEncHandle p, ISzAlloc *alloc, ISzAlloc *allocBig)
1749 {
1750 LzmaEnc_Destruct((CLzmaEnc *)p, alloc, allocBig);
1751 alloc->Free(alloc, p);
1752 }
1754 static SRes LzmaEnc_CodeOneBlock(CLzmaEnc *p, Bool useLimits, UInt32 maxPackSize, UInt32 maxUnpackSize)
1755 {
1756 UInt32 nowPos32, startPos32;
1757 if (p->inStream != 0)
1758 {
1759 p->matchFinderBase.stream = p->inStream;
1760 p->matchFinder.Init(p->matchFinderObj);
1761 p->inStream = 0;
1762 }
1764 if (p->finished)
1765 return p->result;
1766 RINOK(CheckErrors(p));
1768 nowPos32 = (UInt32)p->nowPos64;
1769 startPos32 = nowPos32;
1771 if (p->nowPos64 == 0)
1772 {
1773 UInt32 numPairs;
1774 Byte curByte;
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--;
1783 nowPos32++;
1784 }
1786 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) != 0)
1787 for (;;)
1788 {
1789 UInt32 pos, len, posState;
1791 if (p->fastMode)
1792 len = GetOptimumFast(p, &pos);
1793 else
1794 len = GetOptimum(p, nowPos32, &pos);
1796 #ifdef SHOW_STAT2
1797 printf("\n pos = %4X, len = %d pos = %d", nowPos32, len, pos);
1798 #endif
1800 posState = nowPos32 & p->pbMask;
1801 if (len == 1 && pos == (UInt32)-1)
1802 {
1803 Byte curByte;
1804 CLzmaProb *probs;
1805 const Byte *data;
1807 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 0);
1808 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
1809 curByte = *data;
1810 probs = LIT_PROBS(nowPos32, *(data - 1));
1811 if (IsCharState(p->state))
1812 LitEnc_Encode(&p->rc, probs, curByte);
1813 else
1814 LitEnc_EncodeMatched(&p->rc, probs, curByte, *(data - p->reps[0] - 1));
1815 p->state = kLiteralNextStates[p->state];
1816 }
1817 else
1818 {
1819 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1);
1820 if (pos < LZMA_NUM_REPS)
1821 {
1822 RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 1);
1823 if (pos == 0)
1824 {
1825 RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 0);
1826 RangeEnc_EncodeBit(&p->rc, &p->isRep0Long[p->state][posState], ((len == 1) ? 0 : 1));
1827 }
1828 else
1829 {
1830 UInt32 distance = p->reps[pos];
1831 RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 1);
1832 if (pos == 1)
1833 RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 0);
1834 else
1835 {
1836 RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 1);
1837 RangeEnc_EncodeBit(&p->rc, &p->isRepG2[p->state], pos - 2);
1838 if (pos == 3)
1839 p->reps[3] = p->reps[2];
1840 p->reps[2] = p->reps[1];
1841 }
1842 p->reps[1] = p->reps[0];
1843 p->reps[0] = distance;
1844 }
1845 if (len == 1)
1846 p->state = kShortRepNextStates[p->state];
1847 else
1848 {
1849 LenEnc_Encode2(&p->repLenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);
1850 p->state = kRepNextStates[p->state];
1851 }
1852 }
1853 else
1854 {
1855 UInt32 posSlot;
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)
1864 {
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);
1871 else
1872 {
1873 RangeEnc_EncodeDirectBits(&p->rc, posReduced >> kNumAlignBits, footerBits - kNumAlignBits);
1874 RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, posReduced & kAlignMask);
1875 p->alignPriceCount++;
1876 }
1877 }
1878 p->reps[3] = p->reps[2];
1879 p->reps[2] = p->reps[1];
1880 p->reps[1] = p->reps[0];
1881 p->reps[0] = pos;
1882 p->matchPriceCount++;
1883 }
1884 }
1885 p->additionalOffset -= len;
1886 nowPos32 += len;
1887 if (p->additionalOffset == 0)
1888 {
1889 UInt32 processed;
1890 if (!p->fastMode)
1891 {
1892 if (p->matchPriceCount >= (1 << 7))
1893 FillDistancesPrices(p);
1894 if (p->alignPriceCount >= kAlignTableSize)
1895 FillAlignPrices(p);
1896 }
1897 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)
1898 break;
1899 processed = nowPos32 - startPos32;
1900 if (useLimits)
1901 {
1902 if (processed + kNumOpts + 300 >= maxUnpackSize ||
1903 RangeEnc_GetProcessed(&p->rc) + kNumOpts * 2 >= maxPackSize)
1904 break;
1905 }
1906 else if (processed >= (1 << 15))
1907 {
1908 p->nowPos64 += nowPos32 - startPos32;
1909 return CheckErrors(p);
1910 }
1911 }
1912 }
1913 p->nowPos64 += nowPos32 - startPos32;
1914 return Flush(p, nowPos32);
1915 }
1917 #define kBigHashDicLimit ((UInt32)1 << 24)
1919 static SRes LzmaEnc_Alloc(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)
1920 {
1921 UInt32 beforeSize = kNumOpts;
1922 Bool btMode;
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);
1928 #endif
1930 {
1931 unsigned lclp = p->lc + p->lp;
1932 if (p->litProbs == 0 || p->saveState.litProbs == 0 || p->lclp != lclp)
1933 {
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)
1938 {
1939 LzmaEnc_FreeLits(p, alloc);
1940 return SZ_ERROR_MEM;
1941 }
1942 p->lclp = lclp;
1943 }
1944 }
1946 p->matchFinderBase.bigHash = (p->dictSize > kBigHashDicLimit);
1948 if (beforeSize + p->dictSize < keepWindowSize)
1949 beforeSize = keepWindowSize - p->dictSize;
1951 #ifdef COMPRESS_MF_MT
1952 if (p->mtMode)
1953 {
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);
1957 }
1958 else
1959 #endif
1960 {
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);
1965 }
1966 return SZ_OK;
1967 }
1969 void LzmaEnc_Init(CLzmaEnc *p)
1970 {
1971 UInt32 i;
1972 p->state = 0;
1973 for (i = 0 ; i < LZMA_NUM_REPS; i++)
1974 p->reps[i] = 0;
1976 RangeEnc_Init(&p->rc);
1979 for (i = 0; i < kNumStates; i++)
1980 {
1981 UInt32 j;
1982 for (j = 0; j < LZMA_NUM_PB_STATES_MAX; j++)
1983 {
1984 p->isMatch[i][j] = kProbInitValue;
1985 p->isRep0Long[i][j] = kProbInitValue;
1986 }
1987 p->isRep[i] = kProbInitValue;
1988 p->isRepG0[i] = kProbInitValue;
1989 p->isRepG1[i] = kProbInitValue;
1990 p->isRepG2[i] = kProbInitValue;
1991 }
1993 {
1994 UInt32 num = 0x300 << (p->lp + p->lc);
1995 for (i = 0; i < num; i++)
1996 p->litProbs[i] = kProbInitValue;
1997 }
1999 {
2000 for (i = 0; i < kNumLenToPosStates; i++)
2001 {
2002 CLzmaProb *probs = p->posSlotEncoder[i];
2003 UInt32 j;
2004 for (j = 0; j < (1 << kNumPosSlotBits); j++)
2005 probs[j] = kProbInitValue;
2006 }
2007 }
2008 {
2009 for (i = 0; i < kNumFullDistances - kEndPosModelIndex; i++)
2010 p->posEncoders[i] = kProbInitValue;
2011 }
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;
2025 }
2027 void LzmaEnc_InitPrices(CLzmaEnc *p)
2028 {
2029 if (!p->fastMode)
2030 {
2031 FillDistancesPrices(p);
2032 FillAlignPrices(p);
2033 }
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);
2040 }
2042 static SRes LzmaEnc_AllocAndInit(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)
2043 {
2044 UInt32 i;
2045 for (i = 0; i < (UInt32)kDicLogSizeMaxCompress; i++)
2046 if (p->dictSize <= ((UInt32)1 << i))
2047 break;
2048 p->distTableSize = i * 2;
2050 p->finished = False;
2051 p->result = SZ_OK;
2052 RINOK(LzmaEnc_Alloc(p, keepWindowSize, alloc, allocBig));
2053 LzmaEnc_Init(p);
2054 LzmaEnc_InitPrices(p);
2055 p->nowPos64 = 0;
2056 return SZ_OK;
2057 }
2059 static SRes LzmaEnc_Prepare(CLzmaEncHandle pp, ISeqInStream *inStream, ISeqOutStream *outStream,
2060 ISzAlloc *alloc, ISzAlloc *allocBig)
2061 {
2062 CLzmaEnc *p = (CLzmaEnc *)pp;
2063 p->inStream = inStream;
2064 p->rc.outStream = outStream;
2065 return LzmaEnc_AllocAndInit(p, 0, alloc, allocBig);
2066 }
2068 SRes LzmaEnc_PrepareForLzma2(CLzmaEncHandle pp,
2069 ISeqInStream *inStream, UInt32 keepWindowSize,
2070 ISzAlloc *alloc, ISzAlloc *allocBig)
2071 {
2072 CLzmaEnc *p = (CLzmaEnc *)pp;
2073 p->inStream = inStream;
2074 return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);
2075 }
2077 static void LzmaEnc_SetInputBuf(CLzmaEnc *p, const Byte *src, SizeT srcLen)
2078 {
2079 p->seqBufInStream.funcTable.Read = MyRead;
2080 p->seqBufInStream.data = src;
2081 p->seqBufInStream.rem = srcLen;
2082 }
2084 SRes LzmaEnc_MemPrepare(CLzmaEncHandle pp, const Byte *src, SizeT srcLen,
2085 UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)
2086 {
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);
2091 }
2093 void LzmaEnc_Finish(CLzmaEncHandle pp)
2094 {
2095 #ifdef COMPRESS_MF_MT
2096 CLzmaEnc *p = (CLzmaEnc *)pp;
2097 if (p->mtMode)
2098 MatchFinderMt_ReleaseStream(&p->matchFinderMt);
2099 #else
2100 pp = pp;
2101 #endif
2102 }
2104 typedef struct _CSeqOutStreamBuf
2105 {
2106 ISeqOutStream funcTable;
2107 Byte *data;
2108 SizeT rem;
2109 Bool overflow;
2110 } CSeqOutStreamBuf;
2112 static size_t MyWrite(void *pp, const void *data, size_t size)
2113 {
2114 CSeqOutStreamBuf *p = (CSeqOutStreamBuf *)pp;
2115 if (p->rem < size)
2116 {
2117 size = p->rem;
2118 p->overflow = True;
2119 }
2120 memcpy(p->data, data, size);
2121 p->rem -= size;
2122 p->data += size;
2123 return size;
2124 }
2127 UInt32 LzmaEnc_GetNumAvailableBytes(CLzmaEncHandle pp)
2128 {
2129 const CLzmaEnc *p = (CLzmaEnc *)pp;
2130 return p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);
2131 }
2133 const Byte *LzmaEnc_GetCurBuf(CLzmaEncHandle pp)
2134 {
2135 const CLzmaEnc *p = (CLzmaEnc *)pp;
2136 return p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
2137 }
2139 SRes LzmaEnc_CodeOneMemBlock(CLzmaEncHandle pp, Bool reInit,
2140 Byte *dest, size_t *destLen, UInt32 desiredPackSize, UInt32 *unpackSize)
2141 {
2142 CLzmaEnc *p = (CLzmaEnc *)pp;
2143 UInt64 nowPos64;
2144 SRes res;
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;
2154 p->result = SZ_OK;
2156 if (reInit)
2157 LzmaEnc_Init(p);
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;
2170 return res;
2171 }
2173 SRes LzmaEnc_Encode(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream, ICompressProgress *progress,
2174 ISzAlloc *alloc, ISzAlloc *allocBig)
2175 {
2176 CLzmaEnc *p = (CLzmaEnc *)pp;
2177 SRes res = SZ_OK;
2179 #ifdef COMPRESS_MF_MT
2180 Byte allocaDummy[0x300];
2181 int i = 0;
2182 for (i = 0; i < 16; i++)
2183 allocaDummy[i] = (Byte)i;
2184 #endif
2186 RINOK(LzmaEnc_Prepare(pp, inStream, outStream, alloc, allocBig));
2188 for (;;)
2189 {
2190 res = LzmaEnc_CodeOneBlock(p, False, 0, 0);
2191 if (res != SZ_OK || p->finished != 0)
2192 break;
2193 if (progress != 0)
2194 {
2195 res = progress->Progress(progress, p->nowPos64, RangeEnc_GetProcessed(&p->rc));
2196 if (res != SZ_OK)
2197 {
2198 res = SZ_ERROR_PROGRESS;
2199 break;
2200 }
2201 }
2202 }
2203 LzmaEnc_Finish(pp);
2204 return res;
2205 }
2207 SRes LzmaEnc_WriteProperties(CLzmaEncHandle pp, Byte *props, SizeT *size)
2208 {
2209 CLzmaEnc *p = (CLzmaEnc *)pp;
2210 int i;
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++)
2218 {
2219 if (dictSize <= ((UInt32)2 << i))
2220 {
2221 dictSize = (2 << i);
2222 break;
2223 }
2224 if (dictSize <= ((UInt32)3 << i))
2225 {
2226 dictSize = (3 << i);
2227 break;
2228 }
2229 }
2231 for (i = 0; i < 4; i++)
2232 props[1 + i] = (Byte)(dictSize >> (8 * i));
2233 return SZ_OK;
2234 }
2236 SRes LzmaEnc_MemEncode(CLzmaEncHandle pp, Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
2237 int writeEndMark, ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig)
2238 {
2239 SRes res;
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;
2258 return res;
2259 }
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)
2264 {
2265 CLzmaEnc *p = (CLzmaEnc *)LzmaEnc_Create(alloc);
2266 SRes res;
2267 if (p == 0)
2268 return SZ_ERROR_MEM;
2270 res = LzmaEnc_SetProps(p, props);
2271 if (res == SZ_OK)
2272 {
2273 res = LzmaEnc_WriteProperties(p, propsEncoded, propsSize);
2274 if (res == SZ_OK)
2275 res = LzmaEnc_MemEncode(p, dest, destLen, src, srcLen,
2276 writeEndMark, progress, alloc, allocBig);
2277 }
2279 LzmaEnc_Destroy(p, alloc, allocBig);
2280 return res;
2281 }