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