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