]> git.proxmox.com Git - mirror_edk2.git/blob - BaseTools/Source/C/LzmaCompress/Sdk/C/LzmaEnc.c
projects / mirror_edk2.git / blob
? search:


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