src/third-party/lzma/LzmaEnc.c (view raw)
1/* LzmaEnc.c -- LZMA Encoder
22015-11-08 : Igor Pavlov : Public domain */
3
4#include "Precomp.h"
5
6#include <string.h>
7
8/* #define SHOW_STAT */
9/* #define SHOW_STAT2 */
10
11#if defined(SHOW_STAT) || defined(SHOW_STAT2)
12#include <stdio.h>
13#endif
14
15#include "LzmaEnc.h"
16
17#include "LzFind.h"
18#ifndef _7ZIP_ST
19#include "LzFindMt.h"
20#endif
21
22#ifdef SHOW_STAT
23static unsigned g_STAT_OFFSET = 0;
24#endif
25
26#define kMaxHistorySize ((UInt32)3 << 29)
27/* #define kMaxHistorySize ((UInt32)7 << 29) */
28
29#define kBlockSizeMax ((1 << LZMA_NUM_BLOCK_SIZE_BITS) - 1)
30
31#define kBlockSize (9 << 10)
32#define kUnpackBlockSize (1 << 18)
33#define kMatchArraySize (1 << 21)
34#define kMatchRecordMaxSize ((LZMA_MATCH_LEN_MAX * 2 + 3) * LZMA_MATCH_LEN_MAX)
35
36#define kNumMaxDirectBits (31)
37
38#define kNumTopBits 24
39#define kTopValue ((UInt32)1 << kNumTopBits)
40
41#define kNumBitModelTotalBits 11
42#define kBitModelTotal (1 << kNumBitModelTotalBits)
43#define kNumMoveBits 5
44#define kProbInitValue (kBitModelTotal >> 1)
45
46#define kNumMoveReducingBits 4
47#define kNumBitPriceShiftBits 4
48#define kBitPrice (1 << kNumBitPriceShiftBits)
49
50void LzmaEncProps_Init(CLzmaEncProps *p)
51{
52 p->level = 5;
53 p->dictSize = p->mc = 0;
54 p->reduceSize = (UInt64)(Int64)-1;
55 p->lc = p->lp = p->pb = p->algo = p->fb = p->btMode = p->numHashBytes = p->numThreads = -1;
56 p->writeEndMark = 0;
57}
58
59void LzmaEncProps_Normalize(CLzmaEncProps *p)
60{
61 int level = p->level;
62 if (level < 0) level = 5;
63 p->level = level;
64
65 if (p->dictSize == 0) p->dictSize = (level <= 5 ? (1 << (level * 2 + 14)) : (level == 6 ? (1 << 25) : (1 << 26)));
66 if (p->dictSize > p->reduceSize)
67 {
68 unsigned i;
69 for (i = 11; i <= 30; i++)
70 {
71 if ((UInt32)p->reduceSize <= ((UInt32)2 << i)) { p->dictSize = ((UInt32)2 << i); break; }
72 if ((UInt32)p->reduceSize <= ((UInt32)3 << i)) { p->dictSize = ((UInt32)3 << i); break; }
73 }
74 }
75
76 if (p->lc < 0) p->lc = 3;
77 if (p->lp < 0) p->lp = 0;
78 if (p->pb < 0) p->pb = 2;
79
80 if (p->algo < 0) p->algo = (level < 5 ? 0 : 1);
81 if (p->fb < 0) p->fb = (level < 7 ? 32 : 64);
82 if (p->btMode < 0) p->btMode = (p->algo == 0 ? 0 : 1);
83 if (p->numHashBytes < 0) p->numHashBytes = 4;
84 if (p->mc == 0) p->mc = (16 + (p->fb >> 1)) >> (p->btMode ? 0 : 1);
85
86 if (p->numThreads < 0)
87 p->numThreads =
88 #ifndef _7ZIP_ST
89 ((p->btMode && p->algo) ? 2 : 1);
90 #else
91 1;
92 #endif
93}
94
95UInt32 LzmaEncProps_GetDictSize(const CLzmaEncProps *props2)
96{
97 CLzmaEncProps props = *props2;
98 LzmaEncProps_Normalize(&props);
99 return props.dictSize;
100}
101
102#if (_MSC_VER >= 1400)
103/* BSR code is fast for some new CPUs */
104/* #define LZMA_LOG_BSR */
105#endif
106
107#ifdef LZMA_LOG_BSR
108
109#define kDicLogSizeMaxCompress 32
110
111#define BSR2_RET(pos, res) { unsigned long i; _BitScanReverse(&i, (pos)); res = (i + i) + ((pos >> (i - 1)) & 1); }
112
113static UInt32 GetPosSlot1(UInt32 pos)
114{
115 UInt32 res;
116 BSR2_RET(pos, res);
117 return res;
118}
119#define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }
120#define GetPosSlot(pos, res) { if (pos < 2) res = pos; else BSR2_RET(pos, res); }
121
122#else
123
124#define kNumLogBits (9 + sizeof(size_t) / 2)
125/* #define kNumLogBits (11 + sizeof(size_t) / 8 * 3) */
126
127#define kDicLogSizeMaxCompress ((kNumLogBits - 1) * 2 + 7)
128
129static void LzmaEnc_FastPosInit(Byte *g_FastPos)
130{
131 unsigned slot;
132 g_FastPos[0] = 0;
133 g_FastPos[1] = 1;
134 g_FastPos += 2;
135
136 for (slot = 2; slot < kNumLogBits * 2; slot++)
137 {
138 size_t k = ((size_t)1 << ((slot >> 1) - 1));
139 size_t j;
140 for (j = 0; j < k; j++)
141 g_FastPos[j] = (Byte)slot;
142 g_FastPos += k;
143 }
144}
145
146/* we can use ((limit - pos) >> 31) only if (pos < ((UInt32)1 << 31)) */
147/*
148#define BSR2_RET(pos, res) { UInt32 i = 6 + ((kNumLogBits - 1) & \
149 (0 - (((((UInt32)1 << (kNumLogBits + 6)) - 1) - pos) >> 31))); \
150 res = p->g_FastPos[pos >> i] + (i * 2); }
151*/
152
153/*
154#define BSR2_RET(pos, res) { UInt32 i = 6 + ((kNumLogBits - 1) & \
155 (0 - (((((UInt32)1 << (kNumLogBits)) - 1) - (pos >> 6)) >> 31))); \
156 res = p->g_FastPos[pos >> i] + (i * 2); }
157*/
158
159#define BSR2_RET(pos, res) { UInt32 i = (pos < (1 << (kNumLogBits + 6))) ? 6 : 6 + kNumLogBits - 1; \
160 res = p->g_FastPos[pos >> i] + (i * 2); }
161
162/*
163#define BSR2_RET(pos, res) { res = (pos < (1 << (kNumLogBits + 6))) ? \
164 p->g_FastPos[pos >> 6] + 12 : \
165 p->g_FastPos[pos >> (6 + kNumLogBits - 1)] + (6 + (kNumLogBits - 1)) * 2; }
166*/
167
168#define GetPosSlot1(pos) p->g_FastPos[pos]
169#define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }
170#define GetPosSlot(pos, res) { if (pos < kNumFullDistances) res = p->g_FastPos[pos]; else BSR2_RET(pos, res); }
171
172#endif
173
174
175#define LZMA_NUM_REPS 4
176
177typedef unsigned CState;
178
179typedef struct
180{
181 UInt32 price;
182
183 CState state;
184 int prev1IsChar;
185 int prev2;
186
187 UInt32 posPrev2;
188 UInt32 backPrev2;
189
190 UInt32 posPrev;
191 UInt32 backPrev;
192 UInt32 backs[LZMA_NUM_REPS];
193} COptimal;
194
195#define kNumOpts (1 << 12)
196
197#define kNumLenToPosStates 4
198#define kNumPosSlotBits 6
199#define kDicLogSizeMin 0
200#define kDicLogSizeMax 32
201#define kDistTableSizeMax (kDicLogSizeMax * 2)
202
203
204#define kNumAlignBits 4
205#define kAlignTableSize (1 << kNumAlignBits)
206#define kAlignMask (kAlignTableSize - 1)
207
208#define kStartPosModelIndex 4
209#define kEndPosModelIndex 14
210#define kNumPosModels (kEndPosModelIndex - kStartPosModelIndex)
211
212#define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
213
214#ifdef _LZMA_PROB32
215#define CLzmaProb UInt32
216#else
217#define CLzmaProb UInt16
218#endif
219
220#define LZMA_PB_MAX 4
221#define LZMA_LC_MAX 8
222#define LZMA_LP_MAX 4
223
224#define LZMA_NUM_PB_STATES_MAX (1 << LZMA_PB_MAX)
225
226
227#define kLenNumLowBits 3
228#define kLenNumLowSymbols (1 << kLenNumLowBits)
229#define kLenNumMidBits 3
230#define kLenNumMidSymbols (1 << kLenNumMidBits)
231#define kLenNumHighBits 8
232#define kLenNumHighSymbols (1 << kLenNumHighBits)
233
234#define kLenNumSymbolsTotal (kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)
235
236#define LZMA_MATCH_LEN_MIN 2
237#define LZMA_MATCH_LEN_MAX (LZMA_MATCH_LEN_MIN + kLenNumSymbolsTotal - 1)
238
239#define kNumStates 12
240
241
242typedef struct
243{
244 CLzmaProb choice;
245 CLzmaProb choice2;
246 CLzmaProb low[LZMA_NUM_PB_STATES_MAX << kLenNumLowBits];
247 CLzmaProb mid[LZMA_NUM_PB_STATES_MAX << kLenNumMidBits];
248 CLzmaProb high[kLenNumHighSymbols];
249} CLenEnc;
250
251
252typedef struct
253{
254 CLenEnc p;
255 UInt32 tableSize;
256 UInt32 prices[LZMA_NUM_PB_STATES_MAX][kLenNumSymbolsTotal];
257 UInt32 counters[LZMA_NUM_PB_STATES_MAX];
258} CLenPriceEnc;
259
260
261typedef struct
262{
263 UInt32 range;
264 Byte cache;
265 UInt64 low;
266 UInt64 cacheSize;
267 Byte *buf;
268 Byte *bufLim;
269 Byte *bufBase;
270 ISeqOutStream *outStream;
271 UInt64 processed;
272 SRes res;
273} CRangeEnc;
274
275
276typedef struct
277{
278 CLzmaProb *litProbs;
279
280 UInt32 state;
281 UInt32 reps[LZMA_NUM_REPS];
282
283 CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];
284 CLzmaProb isRep[kNumStates];
285 CLzmaProb isRepG0[kNumStates];
286 CLzmaProb isRepG1[kNumStates];
287 CLzmaProb isRepG2[kNumStates];
288 CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];
289
290 CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];
291 CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex];
292 CLzmaProb posAlignEncoder[1 << kNumAlignBits];
293
294 CLenPriceEnc lenEnc;
295 CLenPriceEnc repLenEnc;
296} CSaveState;
297
298
299typedef struct
300{
301 void *matchFinderObj;
302 IMatchFinder matchFinder;
303
304 UInt32 optimumEndIndex;
305 UInt32 optimumCurrentIndex;
306
307 UInt32 longestMatchLength;
308 UInt32 numPairs;
309 UInt32 numAvail;
310
311 UInt32 numFastBytes;
312 UInt32 additionalOffset;
313 UInt32 reps[LZMA_NUM_REPS];
314 UInt32 state;
315
316 unsigned lc, lp, pb;
317 unsigned lpMask, pbMask;
318 unsigned lclp;
319
320 CLzmaProb *litProbs;
321
322 Bool fastMode;
323 Bool writeEndMark;
324 Bool finished;
325 Bool multiThread;
326 Bool needInit;
327
328 UInt64 nowPos64;
329
330 UInt32 matchPriceCount;
331 UInt32 alignPriceCount;
332
333 UInt32 distTableSize;
334
335 UInt32 dictSize;
336 SRes result;
337
338 CRangeEnc rc;
339
340 #ifndef _7ZIP_ST
341 Bool mtMode;
342 CMatchFinderMt matchFinderMt;
343 #endif
344
345 CMatchFinder matchFinderBase;
346
347 #ifndef _7ZIP_ST
348 Byte pad[128];
349 #endif
350
351 COptimal opt[kNumOpts];
352
353 #ifndef LZMA_LOG_BSR
354 Byte g_FastPos[1 << kNumLogBits];
355 #endif
356
357 UInt32 ProbPrices[kBitModelTotal >> kNumMoveReducingBits];
358 UInt32 matches[LZMA_MATCH_LEN_MAX * 2 + 2 + 1];
359
360 UInt32 posSlotPrices[kNumLenToPosStates][kDistTableSizeMax];
361 UInt32 distancesPrices[kNumLenToPosStates][kNumFullDistances];
362 UInt32 alignPrices[kAlignTableSize];
363
364 CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];
365 CLzmaProb isRep[kNumStates];
366 CLzmaProb isRepG0[kNumStates];
367 CLzmaProb isRepG1[kNumStates];
368 CLzmaProb isRepG2[kNumStates];
369 CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];
370
371 CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];
372 CLzmaProb posEncoders[kNumFullDistances - kEndPosModelIndex];
373 CLzmaProb posAlignEncoder[1 << kNumAlignBits];
374
375 CLenPriceEnc lenEnc;
376 CLenPriceEnc repLenEnc;
377
378 CSaveState saveState;
379
380 #ifndef _7ZIP_ST
381 Byte pad2[128];
382 #endif
383} CLzmaEnc;
384
385
386void LzmaEnc_SaveState(CLzmaEncHandle pp)
387{
388 CLzmaEnc *p = (CLzmaEnc *)pp;
389 CSaveState *dest = &p->saveState;
390 int i;
391 dest->lenEnc = p->lenEnc;
392 dest->repLenEnc = p->repLenEnc;
393 dest->state = p->state;
394
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, ((UInt32)0x300 << p->lclp) * sizeof(CLzmaProb));
410}
411
412void LzmaEnc_RestoreState(CLzmaEncHandle pp)
413{
414 CLzmaEnc *dest = (CLzmaEnc *)pp;
415 const CSaveState *p = &dest->saveState;
416 int i;
417 dest->lenEnc = p->lenEnc;
418 dest->repLenEnc = p->repLenEnc;
419 dest->state = p->state;
420
421 for (i = 0; i < kNumStates; i++)
422 {
423 memcpy(dest->isMatch[i], p->isMatch[i], sizeof(p->isMatch[i]));
424 memcpy(dest->isRep0Long[i], p->isRep0Long[i], sizeof(p->isRep0Long[i]));
425 }
426 for (i = 0; i < kNumLenToPosStates; i++)
427 memcpy(dest->posSlotEncoder[i], p->posSlotEncoder[i], sizeof(p->posSlotEncoder[i]));
428 memcpy(dest->isRep, p->isRep, sizeof(p->isRep));
429 memcpy(dest->isRepG0, p->isRepG0, sizeof(p->isRepG0));
430 memcpy(dest->isRepG1, p->isRepG1, sizeof(p->isRepG1));
431 memcpy(dest->isRepG2, p->isRepG2, sizeof(p->isRepG2));
432 memcpy(dest->posEncoders, p->posEncoders, sizeof(p->posEncoders));
433 memcpy(dest->posAlignEncoder, p->posAlignEncoder, sizeof(p->posAlignEncoder));
434 memcpy(dest->reps, p->reps, sizeof(p->reps));
435 memcpy(dest->litProbs, p->litProbs, ((UInt32)0x300 << dest->lclp) * sizeof(CLzmaProb));
436}
437
438SRes LzmaEnc_SetProps(CLzmaEncHandle pp, const CLzmaEncProps *props2)
439{
440 CLzmaEnc *p = (CLzmaEnc *)pp;
441 CLzmaEncProps props = *props2;
442 LzmaEncProps_Normalize(&props);
443
444 if (props.lc > LZMA_LC_MAX
445 || props.lp > LZMA_LP_MAX
446 || props.pb > LZMA_PB_MAX
447 || props.dictSize > ((UInt64)1 << kDicLogSizeMaxCompress)
448 || props.dictSize > kMaxHistorySize)
449 return SZ_ERROR_PARAM;
450
451 p->dictSize = props.dictSize;
452 {
453 unsigned fb = props.fb;
454 if (fb < 5)
455 fb = 5;
456 if (fb > LZMA_MATCH_LEN_MAX)
457 fb = LZMA_MATCH_LEN_MAX;
458 p->numFastBytes = fb;
459 }
460 p->lc = props.lc;
461 p->lp = props.lp;
462 p->pb = props.pb;
463 p->fastMode = (props.algo == 0);
464 p->matchFinderBase.btMode = (Byte)(props.btMode ? 1 : 0);
465 {
466 UInt32 numHashBytes = 4;
467 if (props.btMode)
468 {
469 if (props.numHashBytes < 2)
470 numHashBytes = 2;
471 else if (props.numHashBytes < 4)
472 numHashBytes = props.numHashBytes;
473 }
474 p->matchFinderBase.numHashBytes = numHashBytes;
475 }
476
477 p->matchFinderBase.cutValue = props.mc;
478
479 p->writeEndMark = props.writeEndMark;
480
481 #ifndef _7ZIP_ST
482 /*
483 if (newMultiThread != _multiThread)
484 {
485 ReleaseMatchFinder();
486 _multiThread = newMultiThread;
487 }
488 */
489 p->multiThread = (props.numThreads > 1);
490 #endif
491
492 return SZ_OK;
493}
494
495static const int kLiteralNextStates[kNumStates] = {0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5};
496static const int kMatchNextStates[kNumStates] = {7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10};
497static const int kRepNextStates[kNumStates] = {8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11};
498static const int kShortRepNextStates[kNumStates]= {9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11};
499
500#define IsCharState(s) ((s) < 7)
501
502#define GetLenToPosState(len) (((len) < kNumLenToPosStates + 1) ? (len) - 2 : kNumLenToPosStates - 1)
503
504#define kInfinityPrice (1 << 30)
505
506static void RangeEnc_Construct(CRangeEnc *p)
507{
508 p->outStream = NULL;
509 p->bufBase = NULL;
510}
511
512#define RangeEnc_GetProcessed(p) ((p)->processed + ((p)->buf - (p)->bufBase) + (p)->cacheSize)
513
514#define RC_BUF_SIZE (1 << 16)
515static int RangeEnc_Alloc(CRangeEnc *p, ISzAlloc *alloc)
516{
517 if (!p->bufBase)
518 {
519 p->bufBase = (Byte *)alloc->Alloc(alloc, RC_BUF_SIZE);
520 if (!p->bufBase)
521 return 0;
522 p->bufLim = p->bufBase + RC_BUF_SIZE;
523 }
524 return 1;
525}
526
527static void RangeEnc_Free(CRangeEnc *p, ISzAlloc *alloc)
528{
529 alloc->Free(alloc, p->bufBase);
530 p->bufBase = 0;
531}
532
533static void RangeEnc_Init(CRangeEnc *p)
534{
535 /* Stream.Init(); */
536 p->low = 0;
537 p->range = 0xFFFFFFFF;
538 p->cacheSize = 1;
539 p->cache = 0;
540
541 p->buf = p->bufBase;
542
543 p->processed = 0;
544 p->res = SZ_OK;
545}
546
547static void RangeEnc_FlushStream(CRangeEnc *p)
548{
549 size_t num;
550 if (p->res != SZ_OK)
551 return;
552 num = p->buf - p->bufBase;
553 if (num != p->outStream->Write(p->outStream, p->bufBase, num))
554 p->res = SZ_ERROR_WRITE;
555 p->processed += num;
556 p->buf = p->bufBase;
557}
558
559static void MY_FAST_CALL RangeEnc_ShiftLow(CRangeEnc *p)
560{
561 if ((UInt32)p->low < (UInt32)0xFF000000 || (unsigned)(p->low >> 32) != 0)
562 {
563 Byte temp = p->cache;
564 do
565 {
566 Byte *buf = p->buf;
567 *buf++ = (Byte)(temp + (Byte)(p->low >> 32));
568 p->buf = buf;
569 if (buf == p->bufLim)
570 RangeEnc_FlushStream(p);
571 temp = 0xFF;
572 }
573 while (--p->cacheSize != 0);
574 p->cache = (Byte)((UInt32)p->low >> 24);
575 }
576 p->cacheSize++;
577 p->low = (UInt32)p->low << 8;
578}
579
580static void RangeEnc_FlushData(CRangeEnc *p)
581{
582 int i;
583 for (i = 0; i < 5; i++)
584 RangeEnc_ShiftLow(p);
585}
586
587static void RangeEnc_EncodeDirectBits(CRangeEnc *p, UInt32 value, unsigned numBits)
588{
589 do
590 {
591 p->range >>= 1;
592 p->low += p->range & (0 - ((value >> --numBits) & 1));
593 if (p->range < kTopValue)
594 {
595 p->range <<= 8;
596 RangeEnc_ShiftLow(p);
597 }
598 }
599 while (numBits != 0);
600}
601
602static void RangeEnc_EncodeBit(CRangeEnc *p, CLzmaProb *prob, UInt32 symbol)
603{
604 UInt32 ttt = *prob;
605 UInt32 newBound = (p->range >> kNumBitModelTotalBits) * ttt;
606 if (symbol == 0)
607 {
608 p->range = newBound;
609 ttt += (kBitModelTotal - ttt) >> kNumMoveBits;
610 }
611 else
612 {
613 p->low += newBound;
614 p->range -= newBound;
615 ttt -= ttt >> kNumMoveBits;
616 }
617 *prob = (CLzmaProb)ttt;
618 if (p->range < kTopValue)
619 {
620 p->range <<= 8;
621 RangeEnc_ShiftLow(p);
622 }
623}
624
625static void LitEnc_Encode(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol)
626{
627 symbol |= 0x100;
628 do
629 {
630 RangeEnc_EncodeBit(p, probs + (symbol >> 8), (symbol >> 7) & 1);
631 symbol <<= 1;
632 }
633 while (symbol < 0x10000);
634}
635
636static void LitEnc_EncodeMatched(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol, UInt32 matchByte)
637{
638 UInt32 offs = 0x100;
639 symbol |= 0x100;
640 do
641 {
642 matchByte <<= 1;
643 RangeEnc_EncodeBit(p, probs + (offs + (matchByte & offs) + (symbol >> 8)), (symbol >> 7) & 1);
644 symbol <<= 1;
645 offs &= ~(matchByte ^ symbol);
646 }
647 while (symbol < 0x10000);
648}
649
650static void LzmaEnc_InitPriceTables(UInt32 *ProbPrices)
651{
652 UInt32 i;
653 for (i = (1 << kNumMoveReducingBits) / 2; i < kBitModelTotal; i += (1 << kNumMoveReducingBits))
654 {
655 const int kCyclesBits = kNumBitPriceShiftBits;
656 UInt32 w = i;
657 UInt32 bitCount = 0;
658 int j;
659 for (j = 0; j < kCyclesBits; j++)
660 {
661 w = w * w;
662 bitCount <<= 1;
663 while (w >= ((UInt32)1 << 16))
664 {
665 w >>= 1;
666 bitCount++;
667 }
668 }
669 ProbPrices[i >> kNumMoveReducingBits] = ((kNumBitModelTotalBits << kCyclesBits) - 15 - bitCount);
670 }
671}
672
673
674#define GET_PRICE(prob, symbol) \
675 p->ProbPrices[((prob) ^ (((-(int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];
676
677#define GET_PRICEa(prob, symbol) \
678 ProbPrices[((prob) ^ ((-((int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];
679
680#define GET_PRICE_0(prob) p->ProbPrices[(prob) >> kNumMoveReducingBits]
681#define GET_PRICE_1(prob) p->ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]
682
683#define GET_PRICE_0a(prob) ProbPrices[(prob) >> kNumMoveReducingBits]
684#define GET_PRICE_1a(prob) ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]
685
686static UInt32 LitEnc_GetPrice(const CLzmaProb *probs, UInt32 symbol, const UInt32 *ProbPrices)
687{
688 UInt32 price = 0;
689 symbol |= 0x100;
690 do
691 {
692 price += GET_PRICEa(probs[symbol >> 8], (symbol >> 7) & 1);
693 symbol <<= 1;
694 }
695 while (symbol < 0x10000);
696 return price;
697}
698
699static UInt32 LitEnc_GetPriceMatched(const CLzmaProb *probs, UInt32 symbol, UInt32 matchByte, const UInt32 *ProbPrices)
700{
701 UInt32 price = 0;
702 UInt32 offs = 0x100;
703 symbol |= 0x100;
704 do
705 {
706 matchByte <<= 1;
707 price += GET_PRICEa(probs[offs + (matchByte & offs) + (symbol >> 8)], (symbol >> 7) & 1);
708 symbol <<= 1;
709 offs &= ~(matchByte ^ symbol);
710 }
711 while (symbol < 0x10000);
712 return price;
713}
714
715
716static void RcTree_Encode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol)
717{
718 UInt32 m = 1;
719 int i;
720 for (i = numBitLevels; i != 0;)
721 {
722 UInt32 bit;
723 i--;
724 bit = (symbol >> i) & 1;
725 RangeEnc_EncodeBit(rc, probs + m, bit);
726 m = (m << 1) | bit;
727 }
728}
729
730static void RcTree_ReverseEncode(CRangeEnc *rc, CLzmaProb *probs, int numBitLevels, UInt32 symbol)
731{
732 UInt32 m = 1;
733 int i;
734 for (i = 0; i < numBitLevels; i++)
735 {
736 UInt32 bit = symbol & 1;
737 RangeEnc_EncodeBit(rc, probs + m, bit);
738 m = (m << 1) | bit;
739 symbol >>= 1;
740 }
741}
742
743static UInt32 RcTree_GetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, const UInt32 *ProbPrices)
744{
745 UInt32 price = 0;
746 symbol |= (1 << numBitLevels);
747 while (symbol != 1)
748 {
749 price += GET_PRICEa(probs[symbol >> 1], symbol & 1);
750 symbol >>= 1;
751 }
752 return price;
753}
754
755static UInt32 RcTree_ReverseGetPrice(const CLzmaProb *probs, int numBitLevels, UInt32 symbol, const UInt32 *ProbPrices)
756{
757 UInt32 price = 0;
758 UInt32 m = 1;
759 int i;
760 for (i = numBitLevels; i != 0; i--)
761 {
762 UInt32 bit = symbol & 1;
763 symbol >>= 1;
764 price += GET_PRICEa(probs[m], bit);
765 m = (m << 1) | bit;
766 }
767 return price;
768}
769
770
771static void LenEnc_Init(CLenEnc *p)
772{
773 unsigned i;
774 p->choice = p->choice2 = kProbInitValue;
775 for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumLowBits); i++)
776 p->low[i] = kProbInitValue;
777 for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << kLenNumMidBits); i++)
778 p->mid[i] = kProbInitValue;
779 for (i = 0; i < kLenNumHighSymbols; i++)
780 p->high[i] = kProbInitValue;
781}
782
783static void LenEnc_Encode(CLenEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState)
784{
785 if (symbol < kLenNumLowSymbols)
786 {
787 RangeEnc_EncodeBit(rc, &p->choice, 0);
788 RcTree_Encode(rc, p->low + (posState << kLenNumLowBits), kLenNumLowBits, symbol);
789 }
790 else
791 {
792 RangeEnc_EncodeBit(rc, &p->choice, 1);
793 if (symbol < kLenNumLowSymbols + kLenNumMidSymbols)
794 {
795 RangeEnc_EncodeBit(rc, &p->choice2, 0);
796 RcTree_Encode(rc, p->mid + (posState << kLenNumMidBits), kLenNumMidBits, symbol - kLenNumLowSymbols);
797 }
798 else
799 {
800 RangeEnc_EncodeBit(rc, &p->choice2, 1);
801 RcTree_Encode(rc, p->high, kLenNumHighBits, symbol - kLenNumLowSymbols - kLenNumMidSymbols);
802 }
803 }
804}
805
806static void LenEnc_SetPrices(CLenEnc *p, UInt32 posState, UInt32 numSymbols, UInt32 *prices, const UInt32 *ProbPrices)
807{
808 UInt32 a0 = GET_PRICE_0a(p->choice);
809 UInt32 a1 = GET_PRICE_1a(p->choice);
810 UInt32 b0 = a1 + GET_PRICE_0a(p->choice2);
811 UInt32 b1 = a1 + GET_PRICE_1a(p->choice2);
812 UInt32 i = 0;
813 for (i = 0; i < kLenNumLowSymbols; i++)
814 {
815 if (i >= numSymbols)
816 return;
817 prices[i] = a0 + RcTree_GetPrice(p->low + (posState << kLenNumLowBits), kLenNumLowBits, i, ProbPrices);
818 }
819 for (; i < kLenNumLowSymbols + kLenNumMidSymbols; i++)
820 {
821 if (i >= numSymbols)
822 return;
823 prices[i] = b0 + RcTree_GetPrice(p->mid + (posState << kLenNumMidBits), kLenNumMidBits, i - kLenNumLowSymbols, ProbPrices);
824 }
825 for (; i < numSymbols; i++)
826 prices[i] = b1 + RcTree_GetPrice(p->high, kLenNumHighBits, i - kLenNumLowSymbols - kLenNumMidSymbols, ProbPrices);
827}
828
829static void MY_FAST_CALL LenPriceEnc_UpdateTable(CLenPriceEnc *p, UInt32 posState, const UInt32 *ProbPrices)
830{
831 LenEnc_SetPrices(&p->p, posState, p->tableSize, p->prices[posState], ProbPrices);
832 p->counters[posState] = p->tableSize;
833}
834
835static void LenPriceEnc_UpdateTables(CLenPriceEnc *p, UInt32 numPosStates, const UInt32 *ProbPrices)
836{
837 UInt32 posState;
838 for (posState = 0; posState < numPosStates; posState++)
839 LenPriceEnc_UpdateTable(p, posState, ProbPrices);
840}
841
842static void LenEnc_Encode2(CLenPriceEnc *p, CRangeEnc *rc, UInt32 symbol, UInt32 posState, Bool updatePrice, const UInt32 *ProbPrices)
843{
844 LenEnc_Encode(&p->p, rc, symbol, posState);
845 if (updatePrice)
846 if (--p->counters[posState] == 0)
847 LenPriceEnc_UpdateTable(p, posState, ProbPrices);
848}
849
850
851
852
853static void MovePos(CLzmaEnc *p, UInt32 num)
854{
855 #ifdef SHOW_STAT
856 g_STAT_OFFSET += num;
857 printf("\n MovePos %u", num);
858 #endif
859
860 if (num != 0)
861 {
862 p->additionalOffset += num;
863 p->matchFinder.Skip(p->matchFinderObj, num);
864 }
865}
866
867static UInt32 ReadMatchDistances(CLzmaEnc *p, UInt32 *numDistancePairsRes)
868{
869 UInt32 lenRes = 0, numPairs;
870 p->numAvail = p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);
871 numPairs = p->matchFinder.GetMatches(p->matchFinderObj, p->matches);
872
873 #ifdef SHOW_STAT
874 printf("\n i = %u numPairs = %u ", g_STAT_OFFSET, numPairs / 2);
875 g_STAT_OFFSET++;
876 {
877 UInt32 i;
878 for (i = 0; i < numPairs; i += 2)
879 printf("%2u %6u | ", p->matches[i], p->matches[i + 1]);
880 }
881 #endif
882
883 if (numPairs > 0)
884 {
885 lenRes = p->matches[numPairs - 2];
886 if (lenRes == p->numFastBytes)
887 {
888 UInt32 numAvail = p->numAvail;
889 if (numAvail > LZMA_MATCH_LEN_MAX)
890 numAvail = LZMA_MATCH_LEN_MAX;
891 {
892 const Byte *pbyCur = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
893 const Byte *pby = pbyCur + lenRes;
894 ptrdiff_t dif = (ptrdiff_t)-1 - p->matches[numPairs - 1];
895 const Byte *pbyLim = pbyCur + numAvail;
896 for (; pby != pbyLim && *pby == pby[dif]; pby++);
897 lenRes = (UInt32)(pby - pbyCur);
898 }
899 }
900 }
901 p->additionalOffset++;
902 *numDistancePairsRes = numPairs;
903 return lenRes;
904}
905
906
907#define MakeAsChar(p) (p)->backPrev = (UInt32)(-1); (p)->prev1IsChar = False;
908#define MakeAsShortRep(p) (p)->backPrev = 0; (p)->prev1IsChar = False;
909#define IsShortRep(p) ((p)->backPrev == 0)
910
911static UInt32 GetRepLen1Price(CLzmaEnc *p, UInt32 state, UInt32 posState)
912{
913 return
914 GET_PRICE_0(p->isRepG0[state]) +
915 GET_PRICE_0(p->isRep0Long[state][posState]);
916}
917
918static UInt32 GetPureRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 state, UInt32 posState)
919{
920 UInt32 price;
921 if (repIndex == 0)
922 {
923 price = GET_PRICE_0(p->isRepG0[state]);
924 price += GET_PRICE_1(p->isRep0Long[state][posState]);
925 }
926 else
927 {
928 price = GET_PRICE_1(p->isRepG0[state]);
929 if (repIndex == 1)
930 price += GET_PRICE_0(p->isRepG1[state]);
931 else
932 {
933 price += GET_PRICE_1(p->isRepG1[state]);
934 price += GET_PRICE(p->isRepG2[state], repIndex - 2);
935 }
936 }
937 return price;
938}
939
940static UInt32 GetRepPrice(CLzmaEnc *p, UInt32 repIndex, UInt32 len, UInt32 state, UInt32 posState)
941{
942 return p->repLenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN] +
943 GetPureRepPrice(p, repIndex, state, posState);
944}
945
946static UInt32 Backward(CLzmaEnc *p, UInt32 *backRes, UInt32 cur)
947{
948 UInt32 posMem = p->opt[cur].posPrev;
949 UInt32 backMem = p->opt[cur].backPrev;
950 p->optimumEndIndex = cur;
951 do
952 {
953 if (p->opt[cur].prev1IsChar)
954 {
955 MakeAsChar(&p->opt[posMem])
956 p->opt[posMem].posPrev = posMem - 1;
957 if (p->opt[cur].prev2)
958 {
959 p->opt[posMem - 1].prev1IsChar = False;
960 p->opt[posMem - 1].posPrev = p->opt[cur].posPrev2;
961 p->opt[posMem - 1].backPrev = p->opt[cur].backPrev2;
962 }
963 }
964 {
965 UInt32 posPrev = posMem;
966 UInt32 backCur = backMem;
967
968 backMem = p->opt[posPrev].backPrev;
969 posMem = p->opt[posPrev].posPrev;
970
971 p->opt[posPrev].backPrev = backCur;
972 p->opt[posPrev].posPrev = cur;
973 cur = posPrev;
974 }
975 }
976 while (cur != 0);
977 *backRes = p->opt[0].backPrev;
978 p->optimumCurrentIndex = p->opt[0].posPrev;
979 return p->optimumCurrentIndex;
980}
981
982#define LIT_PROBS(pos, prevByte) (p->litProbs + ((((pos) & p->lpMask) << p->lc) + ((prevByte) >> (8 - p->lc))) * (UInt32)0x300)
983
984static UInt32 GetOptimum(CLzmaEnc *p, UInt32 position, UInt32 *backRes)
985{
986 UInt32 numAvail, mainLen, numPairs, repMaxIndex, i, posState, lenEnd, len, cur;
987 UInt32 matchPrice, repMatchPrice, normalMatchPrice;
988 UInt32 reps[LZMA_NUM_REPS], repLens[LZMA_NUM_REPS];
989 UInt32 *matches;
990 const Byte *data;
991 Byte curByte, matchByte;
992 if (p->optimumEndIndex != p->optimumCurrentIndex)
993 {
994 const COptimal *opt = &p->opt[p->optimumCurrentIndex];
995 UInt32 lenRes = opt->posPrev - p->optimumCurrentIndex;
996 *backRes = opt->backPrev;
997 p->optimumCurrentIndex = opt->posPrev;
998 return lenRes;
999 }
1000 p->optimumCurrentIndex = p->optimumEndIndex = 0;
1001
1002 if (p->additionalOffset == 0)
1003 mainLen = ReadMatchDistances(p, &numPairs);
1004 else
1005 {
1006 mainLen = p->longestMatchLength;
1007 numPairs = p->numPairs;
1008 }
1009
1010 numAvail = p->numAvail;
1011 if (numAvail < 2)
1012 {
1013 *backRes = (UInt32)(-1);
1014 return 1;
1015 }
1016 if (numAvail > LZMA_MATCH_LEN_MAX)
1017 numAvail = LZMA_MATCH_LEN_MAX;
1018
1019 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1020 repMaxIndex = 0;
1021 for (i = 0; i < LZMA_NUM_REPS; i++)
1022 {
1023 UInt32 lenTest;
1024 const Byte *data2;
1025 reps[i] = p->reps[i];
1026 data2 = data - reps[i] - 1;
1027 if (data[0] != data2[0] || data[1] != data2[1])
1028 {
1029 repLens[i] = 0;
1030 continue;
1031 }
1032 for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; lenTest++);
1033 repLens[i] = lenTest;
1034 if (lenTest > repLens[repMaxIndex])
1035 repMaxIndex = i;
1036 }
1037 if (repLens[repMaxIndex] >= p->numFastBytes)
1038 {
1039 UInt32 lenRes;
1040 *backRes = repMaxIndex;
1041 lenRes = repLens[repMaxIndex];
1042 MovePos(p, lenRes - 1);
1043 return lenRes;
1044 }
1045
1046 matches = p->matches;
1047 if (mainLen >= p->numFastBytes)
1048 {
1049 *backRes = matches[numPairs - 1] + LZMA_NUM_REPS;
1050 MovePos(p, mainLen - 1);
1051 return mainLen;
1052 }
1053 curByte = *data;
1054 matchByte = *(data - (reps[0] + 1));
1055
1056 if (mainLen < 2 && curByte != matchByte && repLens[repMaxIndex] < 2)
1057 {
1058 *backRes = (UInt32)-1;
1059 return 1;
1060 }
1061
1062 p->opt[0].state = (CState)p->state;
1063
1064 posState = (position & p->pbMask);
1065
1066 {
1067 const CLzmaProb *probs = LIT_PROBS(position, *(data - 1));
1068 p->opt[1].price = GET_PRICE_0(p->isMatch[p->state][posState]) +
1069 (!IsCharState(p->state) ?
1070 LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) :
1071 LitEnc_GetPrice(probs, curByte, p->ProbPrices));
1072 }
1073
1074 MakeAsChar(&p->opt[1]);
1075
1076 matchPrice = GET_PRICE_1(p->isMatch[p->state][posState]);
1077 repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[p->state]);
1078
1079 if (matchByte == curByte)
1080 {
1081 UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, p->state, posState);
1082 if (shortRepPrice < p->opt[1].price)
1083 {
1084 p->opt[1].price = shortRepPrice;
1085 MakeAsShortRep(&p->opt[1]);
1086 }
1087 }
1088 lenEnd = ((mainLen >= repLens[repMaxIndex]) ? mainLen : repLens[repMaxIndex]);
1089
1090 if (lenEnd < 2)
1091 {
1092 *backRes = p->opt[1].backPrev;
1093 return 1;
1094 }
1095
1096 p->opt[1].posPrev = 0;
1097 for (i = 0; i < LZMA_NUM_REPS; i++)
1098 p->opt[0].backs[i] = reps[i];
1099
1100 len = lenEnd;
1101 do
1102 p->opt[len--].price = kInfinityPrice;
1103 while (len >= 2);
1104
1105 for (i = 0; i < LZMA_NUM_REPS; i++)
1106 {
1107 UInt32 repLen = repLens[i];
1108 UInt32 price;
1109 if (repLen < 2)
1110 continue;
1111 price = repMatchPrice + GetPureRepPrice(p, i, p->state, posState);
1112 do
1113 {
1114 UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][repLen - 2];
1115 COptimal *opt = &p->opt[repLen];
1116 if (curAndLenPrice < opt->price)
1117 {
1118 opt->price = curAndLenPrice;
1119 opt->posPrev = 0;
1120 opt->backPrev = i;
1121 opt->prev1IsChar = False;
1122 }
1123 }
1124 while (--repLen >= 2);
1125 }
1126
1127 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[p->state]);
1128
1129 len = ((repLens[0] >= 2) ? repLens[0] + 1 : 2);
1130 if (len <= mainLen)
1131 {
1132 UInt32 offs = 0;
1133 while (len > matches[offs])
1134 offs += 2;
1135 for (; ; len++)
1136 {
1137 COptimal *opt;
1138 UInt32 distance = matches[offs + 1];
1139
1140 UInt32 curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][len - LZMA_MATCH_LEN_MIN];
1141 UInt32 lenToPosState = GetLenToPosState(len);
1142 if (distance < kNumFullDistances)
1143 curAndLenPrice += p->distancesPrices[lenToPosState][distance];
1144 else
1145 {
1146 UInt32 slot;
1147 GetPosSlot2(distance, slot);
1148 curAndLenPrice += p->alignPrices[distance & kAlignMask] + p->posSlotPrices[lenToPosState][slot];
1149 }
1150 opt = &p->opt[len];
1151 if (curAndLenPrice < opt->price)
1152 {
1153 opt->price = curAndLenPrice;
1154 opt->posPrev = 0;
1155 opt->backPrev = distance + LZMA_NUM_REPS;
1156 opt->prev1IsChar = False;
1157 }
1158 if (len == matches[offs])
1159 {
1160 offs += 2;
1161 if (offs == numPairs)
1162 break;
1163 }
1164 }
1165 }
1166
1167 cur = 0;
1168
1169 #ifdef SHOW_STAT2
1170 /* if (position >= 0) */
1171 {
1172 unsigned i;
1173 printf("\n pos = %4X", position);
1174 for (i = cur; i <= lenEnd; i++)
1175 printf("\nprice[%4X] = %u", position - cur + i, p->opt[i].price);
1176 }
1177 #endif
1178
1179 for (;;)
1180 {
1181 UInt32 numAvailFull, newLen, numPairs, posPrev, state, posState, startLen;
1182 UInt32 curPrice, curAnd1Price, matchPrice, repMatchPrice;
1183 Bool nextIsChar;
1184 Byte curByte, matchByte;
1185 const Byte *data;
1186 COptimal *curOpt;
1187 COptimal *nextOpt;
1188
1189 cur++;
1190 if (cur == lenEnd)
1191 return Backward(p, backRes, cur);
1192
1193 newLen = ReadMatchDistances(p, &numPairs);
1194 if (newLen >= p->numFastBytes)
1195 {
1196 p->numPairs = numPairs;
1197 p->longestMatchLength = newLen;
1198 return Backward(p, backRes, cur);
1199 }
1200 position++;
1201 curOpt = &p->opt[cur];
1202 posPrev = curOpt->posPrev;
1203 if (curOpt->prev1IsChar)
1204 {
1205 posPrev--;
1206 if (curOpt->prev2)
1207 {
1208 state = p->opt[curOpt->posPrev2].state;
1209 if (curOpt->backPrev2 < LZMA_NUM_REPS)
1210 state = kRepNextStates[state];
1211 else
1212 state = kMatchNextStates[state];
1213 }
1214 else
1215 state = p->opt[posPrev].state;
1216 state = kLiteralNextStates[state];
1217 }
1218 else
1219 state = p->opt[posPrev].state;
1220 if (posPrev == cur - 1)
1221 {
1222 if (IsShortRep(curOpt))
1223 state = kShortRepNextStates[state];
1224 else
1225 state = kLiteralNextStates[state];
1226 }
1227 else
1228 {
1229 UInt32 pos;
1230 const COptimal *prevOpt;
1231 if (curOpt->prev1IsChar && curOpt->prev2)
1232 {
1233 posPrev = curOpt->posPrev2;
1234 pos = curOpt->backPrev2;
1235 state = kRepNextStates[state];
1236 }
1237 else
1238 {
1239 pos = curOpt->backPrev;
1240 if (pos < LZMA_NUM_REPS)
1241 state = kRepNextStates[state];
1242 else
1243 state = kMatchNextStates[state];
1244 }
1245 prevOpt = &p->opt[posPrev];
1246 if (pos < LZMA_NUM_REPS)
1247 {
1248 UInt32 i;
1249 reps[0] = prevOpt->backs[pos];
1250 for (i = 1; i <= pos; i++)
1251 reps[i] = prevOpt->backs[i - 1];
1252 for (; i < LZMA_NUM_REPS; i++)
1253 reps[i] = prevOpt->backs[i];
1254 }
1255 else
1256 {
1257 UInt32 i;
1258 reps[0] = (pos - LZMA_NUM_REPS);
1259 for (i = 1; i < LZMA_NUM_REPS; i++)
1260 reps[i] = prevOpt->backs[i - 1];
1261 }
1262 }
1263 curOpt->state = (CState)state;
1264
1265 curOpt->backs[0] = reps[0];
1266 curOpt->backs[1] = reps[1];
1267 curOpt->backs[2] = reps[2];
1268 curOpt->backs[3] = reps[3];
1269
1270 curPrice = curOpt->price;
1271 nextIsChar = False;
1272 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1273 curByte = *data;
1274 matchByte = *(data - (reps[0] + 1));
1275
1276 posState = (position & p->pbMask);
1277
1278 curAnd1Price = curPrice + GET_PRICE_0(p->isMatch[state][posState]);
1279 {
1280 const CLzmaProb *probs = LIT_PROBS(position, *(data - 1));
1281 curAnd1Price +=
1282 (!IsCharState(state) ?
1283 LitEnc_GetPriceMatched(probs, curByte, matchByte, p->ProbPrices) :
1284 LitEnc_GetPrice(probs, curByte, p->ProbPrices));
1285 }
1286
1287 nextOpt = &p->opt[cur + 1];
1288
1289 if (curAnd1Price < nextOpt->price)
1290 {
1291 nextOpt->price = curAnd1Price;
1292 nextOpt->posPrev = cur;
1293 MakeAsChar(nextOpt);
1294 nextIsChar = True;
1295 }
1296
1297 matchPrice = curPrice + GET_PRICE_1(p->isMatch[state][posState]);
1298 repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[state]);
1299
1300 if (matchByte == curByte && !(nextOpt->posPrev < cur && nextOpt->backPrev == 0))
1301 {
1302 UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(p, state, posState);
1303 if (shortRepPrice <= nextOpt->price)
1304 {
1305 nextOpt->price = shortRepPrice;
1306 nextOpt->posPrev = cur;
1307 MakeAsShortRep(nextOpt);
1308 nextIsChar = True;
1309 }
1310 }
1311 numAvailFull = p->numAvail;
1312 {
1313 UInt32 temp = kNumOpts - 1 - cur;
1314 if (temp < numAvailFull)
1315 numAvailFull = temp;
1316 }
1317
1318 if (numAvailFull < 2)
1319 continue;
1320 numAvail = (numAvailFull <= p->numFastBytes ? numAvailFull : p->numFastBytes);
1321
1322 if (!nextIsChar && matchByte != curByte) /* speed optimization */
1323 {
1324 /* try Literal + rep0 */
1325 UInt32 temp;
1326 UInt32 lenTest2;
1327 const Byte *data2 = data - reps[0] - 1;
1328 UInt32 limit = p->numFastBytes + 1;
1329 if (limit > numAvailFull)
1330 limit = numAvailFull;
1331
1332 for (temp = 1; temp < limit && data[temp] == data2[temp]; temp++);
1333 lenTest2 = temp - 1;
1334 if (lenTest2 >= 2)
1335 {
1336 UInt32 state2 = kLiteralNextStates[state];
1337 UInt32 posStateNext = (position + 1) & p->pbMask;
1338 UInt32 nextRepMatchPrice = curAnd1Price +
1339 GET_PRICE_1(p->isMatch[state2][posStateNext]) +
1340 GET_PRICE_1(p->isRep[state2]);
1341 /* for (; lenTest2 >= 2; lenTest2--) */
1342 {
1343 UInt32 curAndLenPrice;
1344 COptimal *opt;
1345 UInt32 offset = cur + 1 + lenTest2;
1346 while (lenEnd < offset)
1347 p->opt[++lenEnd].price = kInfinityPrice;
1348 curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);
1349 opt = &p->opt[offset];
1350 if (curAndLenPrice < opt->price)
1351 {
1352 opt->price = curAndLenPrice;
1353 opt->posPrev = cur + 1;
1354 opt->backPrev = 0;
1355 opt->prev1IsChar = True;
1356 opt->prev2 = False;
1357 }
1358 }
1359 }
1360 }
1361
1362 startLen = 2; /* speed optimization */
1363 {
1364 UInt32 repIndex;
1365 for (repIndex = 0; repIndex < LZMA_NUM_REPS; repIndex++)
1366 {
1367 UInt32 lenTest;
1368 UInt32 lenTestTemp;
1369 UInt32 price;
1370 const Byte *data2 = data - reps[repIndex] - 1;
1371 if (data[0] != data2[0] || data[1] != data2[1])
1372 continue;
1373 for (lenTest = 2; lenTest < numAvail && data[lenTest] == data2[lenTest]; lenTest++);
1374 while (lenEnd < cur + lenTest)
1375 p->opt[++lenEnd].price = kInfinityPrice;
1376 lenTestTemp = lenTest;
1377 price = repMatchPrice + GetPureRepPrice(p, repIndex, state, posState);
1378 do
1379 {
1380 UInt32 curAndLenPrice = price + p->repLenEnc.prices[posState][lenTest - 2];
1381 COptimal *opt = &p->opt[cur + lenTest];
1382 if (curAndLenPrice < opt->price)
1383 {
1384 opt->price = curAndLenPrice;
1385 opt->posPrev = cur;
1386 opt->backPrev = repIndex;
1387 opt->prev1IsChar = False;
1388 }
1389 }
1390 while (--lenTest >= 2);
1391 lenTest = lenTestTemp;
1392
1393 if (repIndex == 0)
1394 startLen = lenTest + 1;
1395
1396 /* if (_maxMode) */
1397 {
1398 UInt32 lenTest2 = lenTest + 1;
1399 UInt32 limit = lenTest2 + p->numFastBytes;
1400 if (limit > numAvailFull)
1401 limit = numAvailFull;
1402 for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++);
1403 lenTest2 -= lenTest + 1;
1404 if (lenTest2 >= 2)
1405 {
1406 UInt32 nextRepMatchPrice;
1407 UInt32 state2 = kRepNextStates[state];
1408 UInt32 posStateNext = (position + lenTest) & p->pbMask;
1409 UInt32 curAndLenCharPrice =
1410 price + p->repLenEnc.prices[posState][lenTest - 2] +
1411 GET_PRICE_0(p->isMatch[state2][posStateNext]) +
1412 LitEnc_GetPriceMatched(LIT_PROBS(position + lenTest, data[lenTest - 1]),
1413 data[lenTest], data2[lenTest], p->ProbPrices);
1414 state2 = kLiteralNextStates[state2];
1415 posStateNext = (position + lenTest + 1) & p->pbMask;
1416 nextRepMatchPrice = curAndLenCharPrice +
1417 GET_PRICE_1(p->isMatch[state2][posStateNext]) +
1418 GET_PRICE_1(p->isRep[state2]);
1419
1420 /* for (; lenTest2 >= 2; lenTest2--) */
1421 {
1422 UInt32 curAndLenPrice;
1423 COptimal *opt;
1424 UInt32 offset = cur + lenTest + 1 + lenTest2;
1425 while (lenEnd < offset)
1426 p->opt[++lenEnd].price = kInfinityPrice;
1427 curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);
1428 opt = &p->opt[offset];
1429 if (curAndLenPrice < opt->price)
1430 {
1431 opt->price = curAndLenPrice;
1432 opt->posPrev = cur + lenTest + 1;
1433 opt->backPrev = 0;
1434 opt->prev1IsChar = True;
1435 opt->prev2 = True;
1436 opt->posPrev2 = cur;
1437 opt->backPrev2 = repIndex;
1438 }
1439 }
1440 }
1441 }
1442 }
1443 }
1444 /* for (UInt32 lenTest = 2; lenTest <= newLen; lenTest++) */
1445 if (newLen > numAvail)
1446 {
1447 newLen = numAvail;
1448 for (numPairs = 0; newLen > matches[numPairs]; numPairs += 2);
1449 matches[numPairs] = newLen;
1450 numPairs += 2;
1451 }
1452 if (newLen >= startLen)
1453 {
1454 UInt32 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[state]);
1455 UInt32 offs, curBack, posSlot;
1456 UInt32 lenTest;
1457 while (lenEnd < cur + newLen)
1458 p->opt[++lenEnd].price = kInfinityPrice;
1459
1460 offs = 0;
1461 while (startLen > matches[offs])
1462 offs += 2;
1463 curBack = matches[offs + 1];
1464 GetPosSlot2(curBack, posSlot);
1465 for (lenTest = /*2*/ startLen; ; lenTest++)
1466 {
1467 UInt32 curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][lenTest - LZMA_MATCH_LEN_MIN];
1468 UInt32 lenToPosState = GetLenToPosState(lenTest);
1469 COptimal *opt;
1470 if (curBack < kNumFullDistances)
1471 curAndLenPrice += p->distancesPrices[lenToPosState][curBack];
1472 else
1473 curAndLenPrice += p->posSlotPrices[lenToPosState][posSlot] + p->alignPrices[curBack & kAlignMask];
1474
1475 opt = &p->opt[cur + lenTest];
1476 if (curAndLenPrice < opt->price)
1477 {
1478 opt->price = curAndLenPrice;
1479 opt->posPrev = cur;
1480 opt->backPrev = curBack + LZMA_NUM_REPS;
1481 opt->prev1IsChar = False;
1482 }
1483
1484 if (/*_maxMode && */lenTest == matches[offs])
1485 {
1486 /* Try Match + Literal + Rep0 */
1487 const Byte *data2 = data - curBack - 1;
1488 UInt32 lenTest2 = lenTest + 1;
1489 UInt32 limit = lenTest2 + p->numFastBytes;
1490 if (limit > numAvailFull)
1491 limit = numAvailFull;
1492 for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++);
1493 lenTest2 -= lenTest + 1;
1494 if (lenTest2 >= 2)
1495 {
1496 UInt32 nextRepMatchPrice;
1497 UInt32 state2 = kMatchNextStates[state];
1498 UInt32 posStateNext = (position + lenTest) & p->pbMask;
1499 UInt32 curAndLenCharPrice = curAndLenPrice +
1500 GET_PRICE_0(p->isMatch[state2][posStateNext]) +
1501 LitEnc_GetPriceMatched(LIT_PROBS(position + lenTest, data[lenTest - 1]),
1502 data[lenTest], data2[lenTest], p->ProbPrices);
1503 state2 = kLiteralNextStates[state2];
1504 posStateNext = (posStateNext + 1) & p->pbMask;
1505 nextRepMatchPrice = curAndLenCharPrice +
1506 GET_PRICE_1(p->isMatch[state2][posStateNext]) +
1507 GET_PRICE_1(p->isRep[state2]);
1508
1509 /* for (; lenTest2 >= 2; lenTest2--) */
1510 {
1511 UInt32 offset = cur + lenTest + 1 + lenTest2;
1512 UInt32 curAndLenPrice;
1513 COptimal *opt;
1514 while (lenEnd < offset)
1515 p->opt[++lenEnd].price = kInfinityPrice;
1516 curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);
1517 opt = &p->opt[offset];
1518 if (curAndLenPrice < opt->price)
1519 {
1520 opt->price = curAndLenPrice;
1521 opt->posPrev = cur + lenTest + 1;
1522 opt->backPrev = 0;
1523 opt->prev1IsChar = True;
1524 opt->prev2 = True;
1525 opt->posPrev2 = cur;
1526 opt->backPrev2 = curBack + LZMA_NUM_REPS;
1527 }
1528 }
1529 }
1530 offs += 2;
1531 if (offs == numPairs)
1532 break;
1533 curBack = matches[offs + 1];
1534 if (curBack >= kNumFullDistances)
1535 GetPosSlot2(curBack, posSlot);
1536 }
1537 }
1538 }
1539 }
1540}
1541
1542#define ChangePair(smallDist, bigDist) (((bigDist) >> 7) > (smallDist))
1543
1544static UInt32 GetOptimumFast(CLzmaEnc *p, UInt32 *backRes)
1545{
1546 UInt32 numAvail, mainLen, mainDist, numPairs, repIndex, repLen, i;
1547 const Byte *data;
1548 const UInt32 *matches;
1549
1550 if (p->additionalOffset == 0)
1551 mainLen = ReadMatchDistances(p, &numPairs);
1552 else
1553 {
1554 mainLen = p->longestMatchLength;
1555 numPairs = p->numPairs;
1556 }
1557
1558 numAvail = p->numAvail;
1559 *backRes = (UInt32)-1;
1560 if (numAvail < 2)
1561 return 1;
1562 if (numAvail > LZMA_MATCH_LEN_MAX)
1563 numAvail = LZMA_MATCH_LEN_MAX;
1564 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1565
1566 repLen = repIndex = 0;
1567 for (i = 0; i < LZMA_NUM_REPS; i++)
1568 {
1569 UInt32 len;
1570 const Byte *data2 = data - p->reps[i] - 1;
1571 if (data[0] != data2[0] || data[1] != data2[1])
1572 continue;
1573 for (len = 2; len < numAvail && data[len] == data2[len]; len++);
1574 if (len >= p->numFastBytes)
1575 {
1576 *backRes = i;
1577 MovePos(p, len - 1);
1578 return len;
1579 }
1580 if (len > repLen)
1581 {
1582 repIndex = i;
1583 repLen = len;
1584 }
1585 }
1586
1587 matches = p->matches;
1588 if (mainLen >= p->numFastBytes)
1589 {
1590 *backRes = matches[numPairs - 1] + LZMA_NUM_REPS;
1591 MovePos(p, mainLen - 1);
1592 return mainLen;
1593 }
1594
1595 mainDist = 0; /* for GCC */
1596 if (mainLen >= 2)
1597 {
1598 mainDist = matches[numPairs - 1];
1599 while (numPairs > 2 && mainLen == matches[numPairs - 4] + 1)
1600 {
1601 if (!ChangePair(matches[numPairs - 3], mainDist))
1602 break;
1603 numPairs -= 2;
1604 mainLen = matches[numPairs - 2];
1605 mainDist = matches[numPairs - 1];
1606 }
1607 if (mainLen == 2 && mainDist >= 0x80)
1608 mainLen = 1;
1609 }
1610
1611 if (repLen >= 2 && (
1612 (repLen + 1 >= mainLen) ||
1613 (repLen + 2 >= mainLen && mainDist >= (1 << 9)) ||
1614 (repLen + 3 >= mainLen && mainDist >= (1 << 15))))
1615 {
1616 *backRes = repIndex;
1617 MovePos(p, repLen - 1);
1618 return repLen;
1619 }
1620
1621 if (mainLen < 2 || numAvail <= 2)
1622 return 1;
1623
1624 p->longestMatchLength = ReadMatchDistances(p, &p->numPairs);
1625 if (p->longestMatchLength >= 2)
1626 {
1627 UInt32 newDistance = matches[p->numPairs - 1];
1628 if ((p->longestMatchLength >= mainLen && newDistance < mainDist) ||
1629 (p->longestMatchLength == mainLen + 1 && !ChangePair(mainDist, newDistance)) ||
1630 (p->longestMatchLength > mainLen + 1) ||
1631 (p->longestMatchLength + 1 >= mainLen && mainLen >= 3 && ChangePair(newDistance, mainDist)))
1632 return 1;
1633 }
1634
1635 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1636 for (i = 0; i < LZMA_NUM_REPS; i++)
1637 {
1638 UInt32 len, limit;
1639 const Byte *data2 = data - p->reps[i] - 1;
1640 if (data[0] != data2[0] || data[1] != data2[1])
1641 continue;
1642 limit = mainLen - 1;
1643 for (len = 2; len < limit && data[len] == data2[len]; len++);
1644 if (len >= limit)
1645 return 1;
1646 }
1647 *backRes = mainDist + LZMA_NUM_REPS;
1648 MovePos(p, mainLen - 2);
1649 return mainLen;
1650}
1651
1652static void WriteEndMarker(CLzmaEnc *p, UInt32 posState)
1653{
1654 UInt32 len;
1655 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1);
1656 RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0);
1657 p->state = kMatchNextStates[p->state];
1658 len = LZMA_MATCH_LEN_MIN;
1659 LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);
1660 RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBits, (1 << kNumPosSlotBits) - 1);
1661 RangeEnc_EncodeDirectBits(&p->rc, (((UInt32)1 << 30) - 1) >> kNumAlignBits, 30 - kNumAlignBits);
1662 RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, kAlignMask);
1663}
1664
1665static SRes CheckErrors(CLzmaEnc *p)
1666{
1667 if (p->result != SZ_OK)
1668 return p->result;
1669 if (p->rc.res != SZ_OK)
1670 p->result = SZ_ERROR_WRITE;
1671 if (p->matchFinderBase.result != SZ_OK)
1672 p->result = SZ_ERROR_READ;
1673 if (p->result != SZ_OK)
1674 p->finished = True;
1675 return p->result;
1676}
1677
1678static SRes Flush(CLzmaEnc *p, UInt32 nowPos)
1679{
1680 /* ReleaseMFStream(); */
1681 p->finished = True;
1682 if (p->writeEndMark)
1683 WriteEndMarker(p, nowPos & p->pbMask);
1684 RangeEnc_FlushData(&p->rc);
1685 RangeEnc_FlushStream(&p->rc);
1686 return CheckErrors(p);
1687}
1688
1689static void FillAlignPrices(CLzmaEnc *p)
1690{
1691 UInt32 i;
1692 for (i = 0; i < kAlignTableSize; i++)
1693 p->alignPrices[i] = RcTree_ReverseGetPrice(p->posAlignEncoder, kNumAlignBits, i, p->ProbPrices);
1694 p->alignPriceCount = 0;
1695}
1696
1697static void FillDistancesPrices(CLzmaEnc *p)
1698{
1699 UInt32 tempPrices[kNumFullDistances];
1700 UInt32 i, lenToPosState;
1701 for (i = kStartPosModelIndex; i < kNumFullDistances; i++)
1702 {
1703 UInt32 posSlot = GetPosSlot1(i);
1704 UInt32 footerBits = ((posSlot >> 1) - 1);
1705 UInt32 base = ((2 | (posSlot & 1)) << footerBits);
1706 tempPrices[i] = RcTree_ReverseGetPrice(p->posEncoders + base - posSlot - 1, footerBits, i - base, p->ProbPrices);
1707 }
1708
1709 for (lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++)
1710 {
1711 UInt32 posSlot;
1712 const CLzmaProb *encoder = p->posSlotEncoder[lenToPosState];
1713 UInt32 *posSlotPrices = p->posSlotPrices[lenToPosState];
1714 for (posSlot = 0; posSlot < p->distTableSize; posSlot++)
1715 posSlotPrices[posSlot] = RcTree_GetPrice(encoder, kNumPosSlotBits, posSlot, p->ProbPrices);
1716 for (posSlot = kEndPosModelIndex; posSlot < p->distTableSize; posSlot++)
1717 posSlotPrices[posSlot] += ((((posSlot >> 1) - 1) - kNumAlignBits) << kNumBitPriceShiftBits);
1718
1719 {
1720 UInt32 *distancesPrices = p->distancesPrices[lenToPosState];
1721 UInt32 i;
1722 for (i = 0; i < kStartPosModelIndex; i++)
1723 distancesPrices[i] = posSlotPrices[i];
1724 for (; i < kNumFullDistances; i++)
1725 distancesPrices[i] = posSlotPrices[GetPosSlot1(i)] + tempPrices[i];
1726 }
1727 }
1728 p->matchPriceCount = 0;
1729}
1730
1731void LzmaEnc_Construct(CLzmaEnc *p)
1732{
1733 RangeEnc_Construct(&p->rc);
1734 MatchFinder_Construct(&p->matchFinderBase);
1735
1736 #ifndef _7ZIP_ST
1737 MatchFinderMt_Construct(&p->matchFinderMt);
1738 p->matchFinderMt.MatchFinder = &p->matchFinderBase;
1739 #endif
1740
1741 {
1742 CLzmaEncProps props;
1743 LzmaEncProps_Init(&props);
1744 LzmaEnc_SetProps(p, &props);
1745 }
1746
1747 #ifndef LZMA_LOG_BSR
1748 LzmaEnc_FastPosInit(p->g_FastPos);
1749 #endif
1750
1751 LzmaEnc_InitPriceTables(p->ProbPrices);
1752 p->litProbs = NULL;
1753 p->saveState.litProbs = NULL;
1754}
1755
1756CLzmaEncHandle LzmaEnc_Create(ISzAlloc *alloc)
1757{
1758 void *p;
1759 p = alloc->Alloc(alloc, sizeof(CLzmaEnc));
1760 if (p)
1761 LzmaEnc_Construct((CLzmaEnc *)p);
1762 return p;
1763}
1764
1765void LzmaEnc_FreeLits(CLzmaEnc *p, ISzAlloc *alloc)
1766{
1767 alloc->Free(alloc, p->litProbs);
1768 alloc->Free(alloc, p->saveState.litProbs);
1769 p->litProbs = NULL;
1770 p->saveState.litProbs = NULL;
1771}
1772
1773void LzmaEnc_Destruct(CLzmaEnc *p, ISzAlloc *alloc, ISzAlloc *allocBig)
1774{
1775 #ifndef _7ZIP_ST
1776 MatchFinderMt_Destruct(&p->matchFinderMt, allocBig);
1777 #endif
1778
1779 MatchFinder_Free(&p->matchFinderBase, allocBig);
1780 LzmaEnc_FreeLits(p, alloc);
1781 RangeEnc_Free(&p->rc, alloc);
1782}
1783
1784void LzmaEnc_Destroy(CLzmaEncHandle p, ISzAlloc *alloc, ISzAlloc *allocBig)
1785{
1786 LzmaEnc_Destruct((CLzmaEnc *)p, alloc, allocBig);
1787 alloc->Free(alloc, p);
1788}
1789
1790static SRes LzmaEnc_CodeOneBlock(CLzmaEnc *p, Bool useLimits, UInt32 maxPackSize, UInt32 maxUnpackSize)
1791{
1792 UInt32 nowPos32, startPos32;
1793 if (p->needInit)
1794 {
1795 p->matchFinder.Init(p->matchFinderObj);
1796 p->needInit = 0;
1797 }
1798
1799 if (p->finished)
1800 return p->result;
1801 RINOK(CheckErrors(p));
1802
1803 nowPos32 = (UInt32)p->nowPos64;
1804 startPos32 = nowPos32;
1805
1806 if (p->nowPos64 == 0)
1807 {
1808 UInt32 numPairs;
1809 Byte curByte;
1810 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)
1811 return Flush(p, nowPos32);
1812 ReadMatchDistances(p, &numPairs);
1813 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][0], 0);
1814 p->state = kLiteralNextStates[p->state];
1815 curByte = *(p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset);
1816 LitEnc_Encode(&p->rc, p->litProbs, curByte);
1817 p->additionalOffset--;
1818 nowPos32++;
1819 }
1820
1821 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) != 0)
1822 for (;;)
1823 {
1824 UInt32 pos, len, posState;
1825
1826 if (p->fastMode)
1827 len = GetOptimumFast(p, &pos);
1828 else
1829 len = GetOptimum(p, nowPos32, &pos);
1830
1831 #ifdef SHOW_STAT2
1832 printf("\n pos = %4X, len = %u pos = %u", nowPos32, len, pos);
1833 #endif
1834
1835 posState = nowPos32 & p->pbMask;
1836 if (len == 1 && pos == (UInt32)-1)
1837 {
1838 Byte curByte;
1839 CLzmaProb *probs;
1840 const Byte *data;
1841
1842 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 0);
1843 data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
1844 curByte = *data;
1845 probs = LIT_PROBS(nowPos32, *(data - 1));
1846 if (IsCharState(p->state))
1847 LitEnc_Encode(&p->rc, probs, curByte);
1848 else
1849 LitEnc_EncodeMatched(&p->rc, probs, curByte, *(data - p->reps[0] - 1));
1850 p->state = kLiteralNextStates[p->state];
1851 }
1852 else
1853 {
1854 RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1);
1855 if (pos < LZMA_NUM_REPS)
1856 {
1857 RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 1);
1858 if (pos == 0)
1859 {
1860 RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 0);
1861 RangeEnc_EncodeBit(&p->rc, &p->isRep0Long[p->state][posState], ((len == 1) ? 0 : 1));
1862 }
1863 else
1864 {
1865 UInt32 distance = p->reps[pos];
1866 RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 1);
1867 if (pos == 1)
1868 RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 0);
1869 else
1870 {
1871 RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 1);
1872 RangeEnc_EncodeBit(&p->rc, &p->isRepG2[p->state], pos - 2);
1873 if (pos == 3)
1874 p->reps[3] = p->reps[2];
1875 p->reps[2] = p->reps[1];
1876 }
1877 p->reps[1] = p->reps[0];
1878 p->reps[0] = distance;
1879 }
1880 if (len == 1)
1881 p->state = kShortRepNextStates[p->state];
1882 else
1883 {
1884 LenEnc_Encode2(&p->repLenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);
1885 p->state = kRepNextStates[p->state];
1886 }
1887 }
1888 else
1889 {
1890 UInt32 posSlot;
1891 RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0);
1892 p->state = kMatchNextStates[p->state];
1893 LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);
1894 pos -= LZMA_NUM_REPS;
1895 GetPosSlot(pos, posSlot);
1896 RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBits, posSlot);
1897
1898 if (posSlot >= kStartPosModelIndex)
1899 {
1900 UInt32 footerBits = ((posSlot >> 1) - 1);
1901 UInt32 base = ((2 | (posSlot & 1)) << footerBits);
1902 UInt32 posReduced = pos - base;
1903
1904 if (posSlot < kEndPosModelIndex)
1905 RcTree_ReverseEncode(&p->rc, p->posEncoders + base - posSlot - 1, footerBits, posReduced);
1906 else
1907 {
1908 RangeEnc_EncodeDirectBits(&p->rc, posReduced >> kNumAlignBits, footerBits - kNumAlignBits);
1909 RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, posReduced & kAlignMask);
1910 p->alignPriceCount++;
1911 }
1912 }
1913 p->reps[3] = p->reps[2];
1914 p->reps[2] = p->reps[1];
1915 p->reps[1] = p->reps[0];
1916 p->reps[0] = pos;
1917 p->matchPriceCount++;
1918 }
1919 }
1920 p->additionalOffset -= len;
1921 nowPos32 += len;
1922 if (p->additionalOffset == 0)
1923 {
1924 UInt32 processed;
1925 if (!p->fastMode)
1926 {
1927 if (p->matchPriceCount >= (1 << 7))
1928 FillDistancesPrices(p);
1929 if (p->alignPriceCount >= kAlignTableSize)
1930 FillAlignPrices(p);
1931 }
1932 if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)
1933 break;
1934 processed = nowPos32 - startPos32;
1935 if (useLimits)
1936 {
1937 if (processed + kNumOpts + 300 >= maxUnpackSize ||
1938 RangeEnc_GetProcessed(&p->rc) + kNumOpts * 2 >= maxPackSize)
1939 break;
1940 }
1941 else if (processed >= (1 << 17))
1942 {
1943 p->nowPos64 += nowPos32 - startPos32;
1944 return CheckErrors(p);
1945 }
1946 }
1947 }
1948 p->nowPos64 += nowPos32 - startPos32;
1949 return Flush(p, nowPos32);
1950}
1951
1952#define kBigHashDicLimit ((UInt32)1 << 24)
1953
1954static SRes LzmaEnc_Alloc(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)
1955{
1956 UInt32 beforeSize = kNumOpts;
1957 if (!RangeEnc_Alloc(&p->rc, alloc))
1958 return SZ_ERROR_MEM;
1959
1960 #ifndef _7ZIP_ST
1961 p->mtMode = (p->multiThread && !p->fastMode && (p->matchFinderBase.btMode != 0));
1962 #endif
1963
1964 {
1965 unsigned lclp = p->lc + p->lp;
1966 if (!p->litProbs || !p->saveState.litProbs || p->lclp != lclp)
1967 {
1968 LzmaEnc_FreeLits(p, alloc);
1969 p->litProbs = (CLzmaProb *)alloc->Alloc(alloc, ((UInt32)0x300 << lclp) * sizeof(CLzmaProb));
1970 p->saveState.litProbs = (CLzmaProb *)alloc->Alloc(alloc, ((UInt32)0x300 << lclp) * sizeof(CLzmaProb));
1971 if (!p->litProbs || !p->saveState.litProbs)
1972 {
1973 LzmaEnc_FreeLits(p, alloc);
1974 return SZ_ERROR_MEM;
1975 }
1976 p->lclp = lclp;
1977 }
1978 }
1979
1980 p->matchFinderBase.bigHash = (Byte)(p->dictSize > kBigHashDicLimit ? 1 : 0);
1981
1982 if (beforeSize + p->dictSize < keepWindowSize)
1983 beforeSize = keepWindowSize - p->dictSize;
1984
1985 #ifndef _7ZIP_ST
1986 if (p->mtMode)
1987 {
1988 RINOK(MatchFinderMt_Create(&p->matchFinderMt, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig));
1989 p->matchFinderObj = &p->matchFinderMt;
1990 MatchFinderMt_CreateVTable(&p->matchFinderMt, &p->matchFinder);
1991 }
1992 else
1993 #endif
1994 {
1995 if (!MatchFinder_Create(&p->matchFinderBase, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig))
1996 return SZ_ERROR_MEM;
1997 p->matchFinderObj = &p->matchFinderBase;
1998 MatchFinder_CreateVTable(&p->matchFinderBase, &p->matchFinder);
1999 }
2000
2001 return SZ_OK;
2002}
2003
2004void LzmaEnc_Init(CLzmaEnc *p)
2005{
2006 UInt32 i;
2007 p->state = 0;
2008 for (i = 0 ; i < LZMA_NUM_REPS; i++)
2009 p->reps[i] = 0;
2010
2011 RangeEnc_Init(&p->rc);
2012
2013
2014 for (i = 0; i < kNumStates; i++)
2015 {
2016 UInt32 j;
2017 for (j = 0; j < LZMA_NUM_PB_STATES_MAX; j++)
2018 {
2019 p->isMatch[i][j] = kProbInitValue;
2020 p->isRep0Long[i][j] = kProbInitValue;
2021 }
2022 p->isRep[i] = kProbInitValue;
2023 p->isRepG0[i] = kProbInitValue;
2024 p->isRepG1[i] = kProbInitValue;
2025 p->isRepG2[i] = kProbInitValue;
2026 }
2027
2028 {
2029 UInt32 num = (UInt32)0x300 << (p->lp + p->lc);
2030 CLzmaProb *probs = p->litProbs;
2031 for (i = 0; i < num; i++)
2032 probs[i] = kProbInitValue;
2033 }
2034
2035 {
2036 for (i = 0; i < kNumLenToPosStates; i++)
2037 {
2038 CLzmaProb *probs = p->posSlotEncoder[i];
2039 UInt32 j;
2040 for (j = 0; j < (1 << kNumPosSlotBits); j++)
2041 probs[j] = kProbInitValue;
2042 }
2043 }
2044 {
2045 for (i = 0; i < kNumFullDistances - kEndPosModelIndex; i++)
2046 p->posEncoders[i] = kProbInitValue;
2047 }
2048
2049 LenEnc_Init(&p->lenEnc.p);
2050 LenEnc_Init(&p->repLenEnc.p);
2051
2052 for (i = 0; i < (1 << kNumAlignBits); i++)
2053 p->posAlignEncoder[i] = kProbInitValue;
2054
2055 p->optimumEndIndex = 0;
2056 p->optimumCurrentIndex = 0;
2057 p->additionalOffset = 0;
2058
2059 p->pbMask = (1 << p->pb) - 1;
2060 p->lpMask = (1 << p->lp) - 1;
2061}
2062
2063void LzmaEnc_InitPrices(CLzmaEnc *p)
2064{
2065 if (!p->fastMode)
2066 {
2067 FillDistancesPrices(p);
2068 FillAlignPrices(p);
2069 }
2070
2071 p->lenEnc.tableSize =
2072 p->repLenEnc.tableSize =
2073 p->numFastBytes + 1 - LZMA_MATCH_LEN_MIN;
2074 LenPriceEnc_UpdateTables(&p->lenEnc, 1 << p->pb, p->ProbPrices);
2075 LenPriceEnc_UpdateTables(&p->repLenEnc, 1 << p->pb, p->ProbPrices);
2076}
2077
2078static SRes LzmaEnc_AllocAndInit(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)
2079{
2080 UInt32 i;
2081 for (i = 0; i < (UInt32)kDicLogSizeMaxCompress; i++)
2082 if (p->dictSize <= ((UInt32)1 << i))
2083 break;
2084 p->distTableSize = i * 2;
2085
2086 p->finished = False;
2087 p->result = SZ_OK;
2088 RINOK(LzmaEnc_Alloc(p, keepWindowSize, alloc, allocBig));
2089 LzmaEnc_Init(p);
2090 LzmaEnc_InitPrices(p);
2091 p->nowPos64 = 0;
2092 return SZ_OK;
2093}
2094
2095static SRes LzmaEnc_Prepare(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream,
2096 ISzAlloc *alloc, ISzAlloc *allocBig)
2097{
2098 CLzmaEnc *p = (CLzmaEnc *)pp;
2099 p->matchFinderBase.stream = inStream;
2100 p->needInit = 1;
2101 p->rc.outStream = outStream;
2102 return LzmaEnc_AllocAndInit(p, 0, alloc, allocBig);
2103}
2104
2105SRes LzmaEnc_PrepareForLzma2(CLzmaEncHandle pp,
2106 ISeqInStream *inStream, UInt32 keepWindowSize,
2107 ISzAlloc *alloc, ISzAlloc *allocBig)
2108{
2109 CLzmaEnc *p = (CLzmaEnc *)pp;
2110 p->matchFinderBase.stream = inStream;
2111 p->needInit = 1;
2112 return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);
2113}
2114
2115static void LzmaEnc_SetInputBuf(CLzmaEnc *p, const Byte *src, SizeT srcLen)
2116{
2117 p->matchFinderBase.directInput = 1;
2118 p->matchFinderBase.bufferBase = (Byte *)src;
2119 p->matchFinderBase.directInputRem = srcLen;
2120}
2121
2122SRes LzmaEnc_MemPrepare(CLzmaEncHandle pp, const Byte *src, SizeT srcLen,
2123 UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)
2124{
2125 CLzmaEnc *p = (CLzmaEnc *)pp;
2126 LzmaEnc_SetInputBuf(p, src, srcLen);
2127 p->needInit = 1;
2128
2129 return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);
2130}
2131
2132void LzmaEnc_Finish(CLzmaEncHandle pp)
2133{
2134 #ifndef _7ZIP_ST
2135 CLzmaEnc *p = (CLzmaEnc *)pp;
2136 if (p->mtMode)
2137 MatchFinderMt_ReleaseStream(&p->matchFinderMt);
2138 #else
2139 UNUSED_VAR(pp);
2140 #endif
2141}
2142
2143
2144typedef struct
2145{
2146 ISeqOutStream funcTable;
2147 Byte *data;
2148 SizeT rem;
2149 Bool overflow;
2150} CSeqOutStreamBuf;
2151
2152static size_t MyWrite(void *pp, const void *data, size_t size)
2153{
2154 CSeqOutStreamBuf *p = (CSeqOutStreamBuf *)pp;
2155 if (p->rem < size)
2156 {
2157 size = p->rem;
2158 p->overflow = True;
2159 }
2160 memcpy(p->data, data, size);
2161 p->rem -= size;
2162 p->data += size;
2163 return size;
2164}
2165
2166
2167UInt32 LzmaEnc_GetNumAvailableBytes(CLzmaEncHandle pp)
2168{
2169 const CLzmaEnc *p = (CLzmaEnc *)pp;
2170 return p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);
2171}
2172
2173
2174const Byte *LzmaEnc_GetCurBuf(CLzmaEncHandle pp)
2175{
2176 const CLzmaEnc *p = (CLzmaEnc *)pp;
2177 return p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
2178}
2179
2180
2181SRes LzmaEnc_CodeOneMemBlock(CLzmaEncHandle pp, Bool reInit,
2182 Byte *dest, size_t *destLen, UInt32 desiredPackSize, UInt32 *unpackSize)
2183{
2184 CLzmaEnc *p = (CLzmaEnc *)pp;
2185 UInt64 nowPos64;
2186 SRes res;
2187 CSeqOutStreamBuf outStream;
2188
2189 outStream.funcTable.Write = MyWrite;
2190 outStream.data = dest;
2191 outStream.rem = *destLen;
2192 outStream.overflow = False;
2193
2194 p->writeEndMark = False;
2195 p->finished = False;
2196 p->result = SZ_OK;
2197
2198 if (reInit)
2199 LzmaEnc_Init(p);
2200 LzmaEnc_InitPrices(p);
2201 nowPos64 = p->nowPos64;
2202 RangeEnc_Init(&p->rc);
2203 p->rc.outStream = &outStream.funcTable;
2204
2205 res = LzmaEnc_CodeOneBlock(p, True, desiredPackSize, *unpackSize);
2206
2207 *unpackSize = (UInt32)(p->nowPos64 - nowPos64);
2208 *destLen -= outStream.rem;
2209 if (outStream.overflow)
2210 return SZ_ERROR_OUTPUT_EOF;
2211
2212 return res;
2213}
2214
2215
2216static SRes LzmaEnc_Encode2(CLzmaEnc *p, ICompressProgress *progress)
2217{
2218 SRes res = SZ_OK;
2219
2220 #ifndef _7ZIP_ST
2221 Byte allocaDummy[0x300];
2222 allocaDummy[0] = 0;
2223 allocaDummy[1] = allocaDummy[0];
2224 #endif
2225
2226 for (;;)
2227 {
2228 res = LzmaEnc_CodeOneBlock(p, False, 0, 0);
2229 if (res != SZ_OK || p->finished)
2230 break;
2231 if (progress)
2232 {
2233 res = progress->Progress(progress, p->nowPos64, RangeEnc_GetProcessed(&p->rc));
2234 if (res != SZ_OK)
2235 {
2236 res = SZ_ERROR_PROGRESS;
2237 break;
2238 }
2239 }
2240 }
2241
2242 LzmaEnc_Finish(p);
2243
2244 /*
2245 if (res == S_OK && !Inline_MatchFinder_IsFinishedOK(&p->matchFinderBase))
2246 res = SZ_ERROR_FAIL;
2247 }
2248 */
2249
2250 return res;
2251}
2252
2253
2254SRes LzmaEnc_Encode(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream, ICompressProgress *progress,
2255 ISzAlloc *alloc, ISzAlloc *allocBig)
2256{
2257 RINOK(LzmaEnc_Prepare(pp, outStream, inStream, alloc, allocBig));
2258 return LzmaEnc_Encode2((CLzmaEnc *)pp, progress);
2259}
2260
2261
2262SRes LzmaEnc_WriteProperties(CLzmaEncHandle pp, Byte *props, SizeT *size)
2263{
2264 CLzmaEnc *p = (CLzmaEnc *)pp;
2265 unsigned i;
2266 UInt32 dictSize = p->dictSize;
2267 if (*size < LZMA_PROPS_SIZE)
2268 return SZ_ERROR_PARAM;
2269 *size = LZMA_PROPS_SIZE;
2270 props[0] = (Byte)((p->pb * 5 + p->lp) * 9 + p->lc);
2271
2272 if (dictSize >= ((UInt32)1 << 22))
2273 {
2274 UInt32 kDictMask = ((UInt32)1 << 20) - 1;
2275 if (dictSize < (UInt32)0xFFFFFFFF - kDictMask)
2276 dictSize = (dictSize + kDictMask) & ~kDictMask;
2277 }
2278 else for (i = 11; i <= 30; i++)
2279 {
2280 if (dictSize <= ((UInt32)2 << i)) { dictSize = (2 << i); break; }
2281 if (dictSize <= ((UInt32)3 << i)) { dictSize = (3 << i); break; }
2282 }
2283
2284 for (i = 0; i < 4; i++)
2285 props[1 + i] = (Byte)(dictSize >> (8 * i));
2286 return SZ_OK;
2287}
2288
2289
2290SRes LzmaEnc_MemEncode(CLzmaEncHandle pp, Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
2291 int writeEndMark, ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig)
2292{
2293 SRes res;
2294 CLzmaEnc *p = (CLzmaEnc *)pp;
2295
2296 CSeqOutStreamBuf outStream;
2297
2298 outStream.funcTable.Write = MyWrite;
2299 outStream.data = dest;
2300 outStream.rem = *destLen;
2301 outStream.overflow = False;
2302
2303 p->writeEndMark = writeEndMark;
2304 p->rc.outStream = &outStream.funcTable;
2305
2306 res = LzmaEnc_MemPrepare(pp, src, srcLen, 0, alloc, allocBig);
2307
2308 if (res == SZ_OK)
2309 {
2310 res = LzmaEnc_Encode2(p, progress);
2311 if (res == SZ_OK && p->nowPos64 != srcLen)
2312 res = SZ_ERROR_FAIL;
2313 }
2314
2315 *destLen -= outStream.rem;
2316 if (outStream.overflow)
2317 return SZ_ERROR_OUTPUT_EOF;
2318 return res;
2319}
2320
2321
2322SRes LzmaEncode(Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
2323 const CLzmaEncProps *props, Byte *propsEncoded, SizeT *propsSize, int writeEndMark,
2324 ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig)
2325{
2326 CLzmaEnc *p = (CLzmaEnc *)LzmaEnc_Create(alloc);
2327 SRes res;
2328 if (!p)
2329 return SZ_ERROR_MEM;
2330
2331 res = LzmaEnc_SetProps(p, props);
2332 if (res == SZ_OK)
2333 {
2334 res = LzmaEnc_WriteProperties(p, propsEncoded, propsSize);
2335 if (res == SZ_OK)
2336 res = LzmaEnc_MemEncode(p, dest, destLen, src, srcLen,
2337 writeEndMark, progress, alloc, allocBig);
2338 }
2339
2340 LzmaEnc_Destroy(p, alloc, allocBig);
2341 return res;
2342}