BaseTools/Source/C/LzmaCompress/Sdk/C/LzmaEnc.c

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