release/src-rt/tools/misc/lzma_src/C/LzmaEnc.c

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