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