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 #ifndef _MSC_VER
1371       if (1 /* _maxMode */)
1372 #endif
1373         {
1374           UInt32 lenTest2 = lenTest + 1;
1375           UInt32 limit = lenTest2 + p->numFastBytes;
1376           UInt32 nextRepMatchPrice;
1377           if (limit > numAvailFull)
1378             limit = numAvailFull;
1379           for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++);
1380           lenTest2 -= lenTest + 1;
1381           if (lenTest2 >= 2)
1382           {
1383             UInt32 state2 = kRepNextStates[state];
1384             UInt32 posStateNext = (position + lenTest) & p->pbMask;
1385             UInt32 curAndLenCharPrice =
1386                 price + p->repLenEnc.prices[posState][lenTest - 2] +
1387                 GET_PRICE_0(p->isMatch[state2][posStateNext]) +
1388                 LitEnc_GetPriceMatched(LIT_PROBS(position + lenTest, data[lenTest - 1]),
1389                     data[lenTest], data2[lenTest], p->ProbPrices);
1390             state2 = kLiteralNextStates[state2];
1391             posStateNext = (position + lenTest + 1) & p->pbMask;
1392             nextRepMatchPrice = curAndLenCharPrice +
1393                 GET_PRICE_1(p->isMatch[state2][posStateNext]) +
1394                 GET_PRICE_1(p->isRep[state2]);
1395
1396             /* for (; lenTest2 >= 2; lenTest2--) */
1397             {
1398               UInt32 curAndLenPrice;
1399               COptimal *opt;
1400               UInt32 offset = cur + lenTest + 1 + lenTest2;
1401               while (lenEnd < offset)
1402                 p->opt[++lenEnd].price = kInfinityPrice;
1403               curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);
1404               opt = &p->opt[offset];
1405               if (curAndLenPrice < opt->price)
1406               {
1407                 opt->price = curAndLenPrice;
1408                 opt->posPrev = cur + lenTest + 1;
1409                 opt->backPrev = 0;
1410                 opt->prev1IsChar = True;
1411                 opt->prev2 = True;
1412                 opt->posPrev2 = cur;
1413                 opt->backPrev2 = repIndex;
1414               }
1415             }
1416           }
1417         }
1418     }
1419     }
1420     /* for (UInt32 lenTest = 2; lenTest <= newLen; lenTest++) */
1421     if (newLen > numAvail)
1422     {
1423       newLen = numAvail;
1424       for (numPairs = 0; newLen > matches[numPairs]; numPairs += 2);
1425       matches[numPairs] = newLen;
1426       numPairs += 2;
1427     }
1428     if (newLen >= startLen)
1429     {
1430       normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[state]);
1431       UInt32 offs, curBack, posSlot;
1432       UInt32 lenTest;
1433       while (lenEnd < cur + newLen)
1434         p->opt[++lenEnd].price = kInfinityPrice;
1435
1436       offs = 0;
1437       while (startLen > matches[offs])
1438         offs += 2;
1439       curBack = matches[offs + 1];
1440       GetPosSlot2(curBack, posSlot);
1441       for (lenTest = /*2*/ startLen; ; lenTest++)
1442       {
1443         UInt32 curAndLenPrice;
1444         curAndLenPrice = normalMatchPrice + p->lenEnc.prices[posState][lenTest - LZMA_MATCH_LEN_MIN];
1445         UInt32 lenToPosState = GetLenToPosState(lenTest);
1446         COptimal *opt;
1447         if (curBack < kNumFullDistances)
1448           curAndLenPrice += p->distancesPrices[lenToPosState][curBack];
1449         else
1450           curAndLenPrice += p->posSlotPrices[lenToPosState][posSlot] + p->alignPrices[curBack & kAlignMask];
1451
1452         opt = &p->opt[cur + lenTest];
1453         if (curAndLenPrice < opt->price)
1454         {
1455           opt->price = curAndLenPrice;
1456           opt->posPrev = cur;
1457           opt->backPrev = curBack + LZMA_NUM_REPS;
1458           opt->prev1IsChar = False;
1459         }
1460
1461         if (/*_maxMode && */lenTest == matches[offs])
1462         {
1463           /* Try Match + Literal + Rep0 */
1464           const Byte *data2 = data - (curBack + 1);
1465           UInt32 lenTest2 = lenTest + 1;
1466           UInt32 limit = lenTest2 + p->numFastBytes;
1467           UInt32 nextRepMatchPrice;
1468           if (limit > numAvailFull)
1469             limit = numAvailFull;
1470           for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++);
1471           lenTest2 -= lenTest + 1;
1472           if (lenTest2 >= 2)
1473           {
1474             UInt32 state2 = kMatchNextStates[state];
1475             UInt32 posStateNext = (position + lenTest) & p->pbMask;
1476             UInt32 curAndLenCharPrice = curAndLenPrice +
1477                 GET_PRICE_0(p->isMatch[state2][posStateNext]) +
1478                 LitEnc_GetPriceMatched(LIT_PROBS(position + lenTest, data[lenTest - 1]),
1479                     data[lenTest], data2[lenTest], p->ProbPrices);
1480             state2 = kLiteralNextStates[state2];
1481             posStateNext = (posStateNext + 1) & p->pbMask;
1482             nextRepMatchPrice = curAndLenCharPrice +
1483                 GET_PRICE_1(p->isMatch[state2][posStateNext]) +
1484                 GET_PRICE_1(p->isRep[state2]);
1485
1486             /* for (; lenTest2 >= 2; lenTest2--) */
1487             {
1488               UInt32 offset = cur + lenTest + 1 + lenTest2;
1489
1490               while (lenEnd < offset)
1491                 p->opt[++lenEnd].price = kInfinityPrice;
1492               curAndLenPrice = nextRepMatchPrice + GetRepPrice(p, 0, lenTest2, state2, posStateNext);
1493               opt = &p->opt[offset];
1494               if (curAndLenPrice < opt->price)
1495               {
1496                 opt->price = curAndLenPrice;
1497                 opt->posPrev = cur + lenTest + 1;
1498                 opt->backPrev = 0;
1499                 opt->prev1IsChar = True;
1500                 opt->prev2 = True;
1501                 opt->posPrev2 = cur;
1502                 opt->backPrev2 = curBack + LZMA_NUM_REPS;
1503               }
1504             }
1505           }
1506           offs += 2;
1507           if (offs == numPairs)
1508             break;
1509           curBack = matches[offs + 1];
1510           if (curBack >= kNumFullDistances)
1511             GetPosSlot2(curBack, posSlot);
1512         }
1513       }
1514     }
1515   }
1516 }
1517
1518 #define ChangePair(smallDist, bigDist) (((bigDist) >> 7) > (smallDist))
1519
1520 static UInt32 GetOptimumFast(CLzmaEnc *p, UInt32 *backRes)
1521 {
1522   UInt32 numAvail, mainLen, mainDist, numPairs, repIndex, repLen, i;
1523   const Byte *data;
1524   const UInt32 *matches;
1525
1526   if (p->additionalOffset == 0)
1527     mainLen = ReadMatchDistances(p, &numPairs);
1528   else
1529   {
1530     mainLen = p->longestMatchLength;
1531     numPairs = p->numPairs;
1532   }
1533
1534   numAvail = p->numAvail;
1535   *backRes = (UInt32)-1;
1536   if (numAvail < 2)
1537     return 1;
1538   if (numAvail > LZMA_MATCH_LEN_MAX)
1539     numAvail = LZMA_MATCH_LEN_MAX;
1540   data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1541
1542   repLen = repIndex = 0;
1543   for (i = 0; i < LZMA_NUM_REPS; i++)
1544   {
1545     UInt32 len;
1546     const Byte *data2 = data - (p->reps[i] + 1);
1547     if (data[0] != data2[0] || data[1] != data2[1])
1548       continue;
1549     for (len = 2; len < numAvail && data[len] == data2[len]; len++);
1550     if (len >= p->numFastBytes)
1551     {
1552       *backRes = i;
1553       MovePos(p, len - 1);
1554       return len;
1555     }
1556     if (len > repLen)
1557     {
1558       repIndex = i;
1559       repLen = len;
1560     }
1561   }
1562
1563   matches = p->matches;
1564   if (mainLen >= p->numFastBytes)
1565   {
1566     *backRes = matches[numPairs - 1] + LZMA_NUM_REPS;
1567     MovePos(p, mainLen - 1);
1568     return mainLen;
1569   }
1570
1571   mainDist = 0; /* for GCC */
1572   if (mainLen >= 2)
1573   {
1574     mainDist = matches[numPairs - 1];
1575     while (numPairs > 2 && mainLen == matches[numPairs - 4] + 1)
1576     {
1577       if (!ChangePair(matches[numPairs - 3], mainDist))
1578         break;
1579       numPairs -= 2;
1580       mainLen = matches[numPairs - 2];
1581       mainDist = matches[numPairs - 1];
1582     }
1583     if (mainLen == 2 && mainDist >= 0x80)
1584       mainLen = 1;
1585   }
1586
1587   if (repLen >= 2 && (
1588         (repLen + 1 >= mainLen) ||
1589         (repLen + 2 >= mainLen && mainDist >= (1 << 9)) ||
1590         (repLen + 3 >= mainLen && mainDist >= (1 << 15))))
1591   {
1592     *backRes = repIndex;
1593     MovePos(p, repLen - 1);
1594     return repLen;
1595   }
1596
1597   if (mainLen < 2 || numAvail <= 2)
1598     return 1;
1599
1600   p->longestMatchLength = ReadMatchDistances(p, &p->numPairs);
1601   if (p->longestMatchLength >= 2)
1602   {
1603     UInt32 newDistance = matches[p->numPairs - 1];
1604     if ((p->longestMatchLength >= mainLen && newDistance < mainDist) ||
1605         (p->longestMatchLength == mainLen + 1 && !ChangePair(mainDist, newDistance)) ||
1606         (p->longestMatchLength > mainLen + 1) ||
1607         (p->longestMatchLength + 1 >= mainLen && mainLen >= 3 && ChangePair(newDistance, mainDist)))
1608       return 1;
1609   }
1610
1611   data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1612   for (i = 0; i < LZMA_NUM_REPS; i++)
1613   {
1614     UInt32 len, limit;
1615     const Byte *data2 = data - (p->reps[i] + 1);
1616     if (data[0] != data2[0] || data[1] != data2[1])
1617       continue;
1618     limit = mainLen - 1;
1619     for (len = 2; len < limit && data[len] == data2[len]; len++);
1620     if (len >= limit)
1621       return 1;
1622   }
1623   *backRes = mainDist + LZMA_NUM_REPS;
1624   MovePos(p, mainLen - 2);
1625   return mainLen;
1626 }
1627
1628 static void WriteEndMarker(CLzmaEnc *p, UInt32 posState)
1629 {
1630   UInt32 len;
1631   RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1);
1632   RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0);
1633   p->state = kMatchNextStates[p->state];
1634   len = LZMA_MATCH_LEN_MIN;
1635   LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);
1636   RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBits, (1 << kNumPosSlotBits) - 1);
1637   RangeEnc_EncodeDirectBits(&p->rc, (((UInt32)1 << 30) - 1) >> kNumAlignBits, 30 - kNumAlignBits);
1638   RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, kAlignMask);
1639 }
1640
1641 static SRes CheckErrors(CLzmaEnc *p)
1642 {
1643   if (p->result != SZ_OK)
1644     return p->result;
1645   if (p->rc.res != SZ_OK)
1646     p->result = SZ_ERROR_WRITE;
1647   if (p->matchFinderBase.result != SZ_OK)
1648     p->result = SZ_ERROR_READ;
1649   if (p->result != SZ_OK)
1650     p->finished = True;
1651   return p->result;
1652 }
1653
1654 static SRes Flush(CLzmaEnc *p, UInt32 nowPos)
1655 {
1656   /* ReleaseMFStream(); */
1657   p->finished = True;
1658   if (p->writeEndMark)
1659     WriteEndMarker(p, nowPos & p->pbMask);
1660   RangeEnc_FlushData(&p->rc);
1661   RangeEnc_FlushStream(&p->rc);
1662   return CheckErrors(p);
1663 }
1664
1665 static void FillAlignPrices(CLzmaEnc *p)
1666 {
1667   UInt32 i;
1668   for (i = 0; i < kAlignTableSize; i++)
1669     p->alignPrices[i] = RcTree_ReverseGetPrice(p->posAlignEncoder, kNumAlignBits, i, p->ProbPrices);
1670   p->alignPriceCount = 0;
1671 }
1672
1673 static void FillDistancesPrices(CLzmaEnc *p)
1674 {
1675   UInt32 tempPrices[kNumFullDistances];
1676   UInt32 i, lenToPosState;
1677   for (i = kStartPosModelIndex; i < kNumFullDistances; i++)
1678   {
1679     UInt32 posSlot = GetPosSlot1(i);
1680     UInt32 footerBits = ((posSlot >> 1) - 1);
1681     UInt32 base = ((2 | (posSlot & 1)) << footerBits);
1682     tempPrices[i] = RcTree_ReverseGetPrice(p->posEncoders + base - posSlot - 1, footerBits, i - base, p->ProbPrices);
1683   }
1684
1685   for (lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++)
1686   {
1687     UInt32 posSlot;
1688     const CLzmaProb *encoder = p->posSlotEncoder[lenToPosState];
1689     UInt32 *posSlotPrices = p->posSlotPrices[lenToPosState];
1690     for (posSlot = 0; posSlot < p->distTableSize; posSlot++)
1691       posSlotPrices[posSlot] = RcTree_GetPrice(encoder, kNumPosSlotBits, posSlot, p->ProbPrices);
1692     for (posSlot = kEndPosModelIndex; posSlot < p->distTableSize; posSlot++)
1693       posSlotPrices[posSlot] += ((((posSlot >> 1) - 1) - kNumAlignBits) << kNumBitPriceShiftBits);
1694
1695     {
1696       UInt32 *distancesPrices = p->distancesPrices[lenToPosState];
1697
1698       for (i = 0; i < kStartPosModelIndex; i++)
1699         distancesPrices[i] = posSlotPrices[i];
1700       for (; i < kNumFullDistances; i++)
1701         distancesPrices[i] = posSlotPrices[GetPosSlot1(i)] + tempPrices[i];
1702     }
1703   }
1704   p->matchPriceCount = 0;
1705 }
1706
1707 void LzmaEnc_Construct(CLzmaEnc *p)
1708 {
1709   RangeEnc_Construct(&p->rc);
1710   MatchFinder_Construct(&p->matchFinderBase);
1711   #ifdef COMPRESS_MF_MT
1712   MatchFinderMt_Construct(&p->matchFinderMt);
1713   p->matchFinderMt.MatchFinder = &p->matchFinderBase;
1714   #endif
1715
1716   {
1717     CLzmaEncProps props;
1718     LzmaEncProps_Init(&props);
1719     LzmaEnc_SetProps(p, &props);
1720   }
1721
1722   #ifndef LZMA_LOG_BSR
1723   LzmaEnc_FastPosInit(p->g_FastPos);
1724   #endif
1725
1726   LzmaEnc_InitPriceTables(p->ProbPrices);
1727   p->litProbs = 0;
1728   p->saveState.litProbs = 0;
1729 }
1730
1731 CLzmaEncHandle LzmaEnc_Create(ISzAlloc *alloc)
1732 {
1733   void *p;
1734   p = alloc->Alloc(alloc, sizeof(CLzmaEnc));
1735   if (p != 0)
1736     LzmaEnc_Construct((CLzmaEnc *)p);
1737   return p;
1738 }
1739
1740 void LzmaEnc_FreeLits(CLzmaEnc *p, ISzAlloc *alloc)
1741 {
1742   alloc->Free(alloc, p->litProbs);
1743   alloc->Free(alloc, p->saveState.litProbs);
1744   p->litProbs = 0;
1745   p->saveState.litProbs = 0;
1746 }
1747
1748 void LzmaEnc_Destruct(CLzmaEnc *p, ISzAlloc *alloc, ISzAlloc *allocBig)
1749 {
1750   #ifdef COMPRESS_MF_MT
1751   MatchFinderMt_Destruct(&p->matchFinderMt, allocBig);
1752   #endif
1753   MatchFinder_Free(&p->matchFinderBase, allocBig);
1754   LzmaEnc_FreeLits(p, alloc);
1755   RangeEnc_Free(&p->rc, alloc);
1756 }
1757
1758 void LzmaEnc_Destroy(CLzmaEncHandle p, ISzAlloc *alloc, ISzAlloc *allocBig)
1759 {
1760   LzmaEnc_Destruct((CLzmaEnc *)p, alloc, allocBig);
1761   alloc->Free(alloc, p);
1762 }
1763
1764 static SRes LzmaEnc_CodeOneBlock(CLzmaEnc *p, Bool useLimits, UInt32 maxPackSize, UInt32 maxUnpackSize)
1765 {
1766   UInt32 nowPos32, startPos32;
1767   if (p->inStream != 0)
1768   {
1769     p->matchFinderBase.stream = p->inStream;
1770     p->matchFinder.Init(p->matchFinderObj);
1771     p->inStream = 0;
1772   }
1773
1774   if (p->finished)
1775     return p->result;
1776   RINOK(CheckErrors(p));
1777
1778   nowPos32 = (UInt32)p->nowPos64;
1779   startPos32 = nowPos32;
1780
1781   if (p->nowPos64 == 0)
1782   {
1783     UInt32 numPairs;
1784     Byte curByte;
1785     if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)
1786       return Flush(p, nowPos32);
1787     ReadMatchDistances(p, &numPairs);
1788     RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][0], 0);
1789     p->state = kLiteralNextStates[p->state];
1790     curByte = p->matchFinder.GetIndexByte(p->matchFinderObj, 0 - p->additionalOffset);
1791     LitEnc_Encode(&p->rc, p->litProbs, curByte);
1792     p->additionalOffset--;
1793     nowPos32++;
1794   }
1795
1796   if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) != 0)
1797   for (;;)
1798   {
1799     UInt32 pos, len, posState;
1800
1801     if (p->fastMode)
1802       len = GetOptimumFast(p, &pos);
1803     else
1804       len = GetOptimum(p, nowPos32, &pos);
1805
1806     #ifdef SHOW_STAT2
1807     printf("\n pos = %4X,   len = %d   pos = %d", nowPos32, len, pos);
1808     #endif
1809
1810     posState = nowPos32 & p->pbMask;
1811     if (len == 1 && pos == (UInt32)-1)
1812     {
1813       Byte curByte;
1814       CLzmaProb *probs;
1815       const Byte *data;
1816
1817       RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 0);
1818       data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
1819       curByte = *data;
1820       probs = LIT_PROBS(nowPos32, *(data - 1));
1821       if (IsCharState(p->state))
1822         LitEnc_Encode(&p->rc, probs, curByte);
1823       else
1824         LitEnc_EncodeMatched(&p->rc, probs, curByte, *(data - p->reps[0] - 1));
1825       p->state = kLiteralNextStates[p->state];
1826     }
1827     else
1828     {
1829       RangeEnc_EncodeBit(&p->rc, &p->isMatch[p->state][posState], 1);
1830       if (pos < LZMA_NUM_REPS)
1831       {
1832         RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 1);
1833         if (pos == 0)
1834         {
1835           RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 0);
1836           RangeEnc_EncodeBit(&p->rc, &p->isRep0Long[p->state][posState], ((len == 1) ? 0 : 1));
1837         }
1838         else
1839         {
1840           UInt32 distance = p->reps[pos];
1841           RangeEnc_EncodeBit(&p->rc, &p->isRepG0[p->state], 1);
1842           if (pos == 1)
1843             RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 0);
1844           else
1845           {
1846             RangeEnc_EncodeBit(&p->rc, &p->isRepG1[p->state], 1);
1847             RangeEnc_EncodeBit(&p->rc, &p->isRepG2[p->state], pos - 2);
1848             if (pos == 3)
1849               p->reps[3] = p->reps[2];
1850             p->reps[2] = p->reps[1];
1851           }
1852           p->reps[1] = p->reps[0];
1853           p->reps[0] = distance;
1854         }
1855         if (len == 1)
1856           p->state = kShortRepNextStates[p->state];
1857         else
1858         {
1859           LenEnc_Encode2(&p->repLenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);
1860           p->state = kRepNextStates[p->state];
1861         }
1862       }
1863       else
1864       {
1865         UInt32 posSlot;
1866         RangeEnc_EncodeBit(&p->rc, &p->isRep[p->state], 0);
1867         p->state = kMatchNextStates[p->state];
1868         LenEnc_Encode2(&p->lenEnc, &p->rc, len - LZMA_MATCH_LEN_MIN, posState, !p->fastMode, p->ProbPrices);
1869         pos -= LZMA_NUM_REPS;
1870         GetPosSlot(pos, posSlot);
1871         RcTree_Encode(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], kNumPosSlotBits, posSlot);
1872
1873         if (posSlot >= kStartPosModelIndex)
1874         {
1875           UInt32 footerBits = ((posSlot >> 1) - 1);
1876           UInt32 base = ((2 | (posSlot & 1)) << footerBits);
1877           UInt32 posReduced = pos - base;
1878
1879           if (posSlot < kEndPosModelIndex)
1880             RcTree_ReverseEncode(&p->rc, p->posEncoders + base - posSlot - 1, footerBits, posReduced);
1881           else
1882           {
1883             RangeEnc_EncodeDirectBits(&p->rc, posReduced >> kNumAlignBits, footerBits - kNumAlignBits);
1884             RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, posReduced & kAlignMask);
1885             p->alignPriceCount++;
1886           }
1887         }
1888         p->reps[3] = p->reps[2];
1889         p->reps[2] = p->reps[1];
1890         p->reps[1] = p->reps[0];
1891         p->reps[0] = pos;
1892         p->matchPriceCount++;
1893       }
1894     }
1895     p->additionalOffset -= len;
1896     nowPos32 += len;
1897     if (p->additionalOffset == 0)
1898     {
1899       UInt32 processed;
1900       if (!p->fastMode)
1901       {
1902         if (p->matchPriceCount >= (1 << 7))
1903           FillDistancesPrices(p);
1904         if (p->alignPriceCount >= kAlignTableSize)
1905           FillAlignPrices(p);
1906       }
1907       if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)
1908         break;
1909       processed = nowPos32 - startPos32;
1910       if (useLimits)
1911       {
1912         if (processed + kNumOpts + 300 >= maxUnpackSize ||
1913             RangeEnc_GetProcessed(&p->rc) + kNumOpts * 2 >= maxPackSize)
1914           break;
1915       }
1916       else if (processed >= (1 << 15))
1917       {
1918         p->nowPos64 += nowPos32 - startPos32;
1919         return CheckErrors(p);
1920       }
1921     }
1922   }
1923   p->nowPos64 += nowPos32 - startPos32;
1924   return Flush(p, nowPos32);
1925 }
1926
1927 #define kBigHashDicLimit ((UInt32)1 << 24)
1928
1929 static SRes LzmaEnc_Alloc(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)
1930 {
1931   UInt32 beforeSize = kNumOpts;
1932   #ifdef COMPRESS_MF_MT
1933   Bool btMode;
1934   #endif
1935   if (!RangeEnc_Alloc(&p->rc, alloc))
1936     return SZ_ERROR_MEM;
1937   #ifdef COMPRESS_MF_MT
1938   btMode = (p->matchFinderBase.btMode != 0);
1939   p->mtMode = (p->multiThread && !p->fastMode && btMode);
1940   #endif
1941
1942   {
1943     unsigned lclp = p->lc + p->lp;
1944     if (p->litProbs == 0 || p->saveState.litProbs == 0 || p->lclp != lclp)
1945     {
1946       LzmaEnc_FreeLits(p, alloc);
1947       p->litProbs = (CLzmaProb *)alloc->Alloc(alloc, (0x300 << lclp) * sizeof(CLzmaProb));
1948       p->saveState.litProbs = (CLzmaProb *)alloc->Alloc(alloc, (0x300 << lclp) * sizeof(CLzmaProb));
1949       if (p->litProbs == 0 || p->saveState.litProbs == 0)
1950       {
1951         LzmaEnc_FreeLits(p, alloc);
1952         return SZ_ERROR_MEM;
1953       }
1954       p->lclp = lclp;
1955     }
1956   }
1957
1958   p->matchFinderBase.bigHash = (p->dictSize > kBigHashDicLimit);
1959
1960   if (beforeSize + p->dictSize < keepWindowSize)
1961     beforeSize = keepWindowSize - p->dictSize;
1962
1963   #ifdef COMPRESS_MF_MT
1964   if (p->mtMode)
1965   {
1966     RINOK(MatchFinderMt_Create(&p->matchFinderMt, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig));
1967     p->matchFinderObj = &p->matchFinderMt;
1968     MatchFinderMt_CreateVTable(&p->matchFinderMt, &p->matchFinder);
1969   }
1970   else
1971   #endif
1972   {
1973     if (!MatchFinder_Create(&p->matchFinderBase, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig))
1974       return SZ_ERROR_MEM;
1975     p->matchFinderObj = &p->matchFinderBase;
1976     MatchFinder_CreateVTable(&p->matchFinderBase, &p->matchFinder);
1977   }
1978   return SZ_OK;
1979 }
1980
1981 void LzmaEnc_Init(CLzmaEnc *p)
1982 {
1983   UInt32 i;
1984   p->state = 0;
1985   for (i = 0 ; i < LZMA_NUM_REPS; i++)
1986     p->reps[i] = 0;
1987
1988   RangeEnc_Init(&p->rc);
1989
1990
1991   for (i = 0; i < kNumStates; i++)
1992   {
1993     UInt32 j;
1994     for (j = 0; j < LZMA_NUM_PB_STATES_MAX; j++)
1995     {
1996       p->isMatch[i][j] = kProbInitValue;
1997       p->isRep0Long[i][j] = kProbInitValue;
1998     }
1999     p->isRep[i] = kProbInitValue;
2000     p->isRepG0[i] = kProbInitValue;
2001     p->isRepG1[i] = kProbInitValue;
2002     p->isRepG2[i] = kProbInitValue;
2003   }
2004
2005   {
2006     UInt32 num = 0x300 << (p->lp + p->lc);
2007     for (i = 0; i < num; i++)
2008       p->litProbs[i] = kProbInitValue;
2009   }
2010
2011   {
2012     for (i = 0; i < kNumLenToPosStates; i++)
2013     {
2014       CLzmaProb *probs = p->posSlotEncoder[i];
2015       UInt32 j;
2016       for (j = 0; j < (1 << kNumPosSlotBits); j++)
2017         probs[j] = kProbInitValue;
2018     }
2019   }
2020   {
2021     for (i = 0; i < kNumFullDistances - kEndPosModelIndex; i++)
2022       p->posEncoders[i] = kProbInitValue;
2023   }
2024
2025   LenEnc_Init(&p->lenEnc.p);
2026   LenEnc_Init(&p->repLenEnc.p);
2027
2028   for (i = 0; i < (1 << kNumAlignBits); i++)
2029     p->posAlignEncoder[i] = kProbInitValue;
2030
2031   p->optimumEndIndex = 0;
2032   p->optimumCurrentIndex = 0;
2033   p->additionalOffset = 0;
2034
2035   p->pbMask = (1 << p->pb) - 1;
2036   p->lpMask = (1 << p->lp) - 1;
2037 }
2038
2039 void LzmaEnc_InitPrices(CLzmaEnc *p)
2040 {
2041   if (!p->fastMode)
2042   {
2043     FillDistancesPrices(p);
2044     FillAlignPrices(p);
2045   }
2046
2047   p->lenEnc.tableSize =
2048   p->repLenEnc.tableSize =
2049       p->numFastBytes + 1 - LZMA_MATCH_LEN_MIN;
2050   LenPriceEnc_UpdateTables(&p->lenEnc, 1 << p->pb, p->ProbPrices);
2051   LenPriceEnc_UpdateTables(&p->repLenEnc, 1 << p->pb, p->ProbPrices);
2052 }
2053
2054 static SRes LzmaEnc_AllocAndInit(CLzmaEnc *p, UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)
2055 {
2056   UInt32 i;
2057   for (i = 0; i < (UInt32)kDicLogSizeMaxCompress; i++)
2058     if (p->dictSize <= ((UInt32)1 << i))
2059       break;
2060   p->distTableSize = i * 2;
2061
2062   p->finished = False;
2063   p->result = SZ_OK;
2064   RINOK(LzmaEnc_Alloc(p, keepWindowSize, alloc, allocBig));
2065   LzmaEnc_Init(p);
2066   LzmaEnc_InitPrices(p);
2067   p->nowPos64 = 0;
2068   return SZ_OK;
2069 }
2070
2071 static SRes LzmaEnc_Prepare(CLzmaEncHandle pp, ISeqInStream *inStream, ISeqOutStream *outStream,
2072     ISzAlloc *alloc, ISzAlloc *allocBig)
2073 {
2074   CLzmaEnc *p = (CLzmaEnc *)pp;
2075   p->inStream = inStream;
2076   p->rc.outStream = outStream;
2077   return LzmaEnc_AllocAndInit(p, 0, alloc, allocBig);
2078 }
2079
2080 SRes LzmaEnc_PrepareForLzma2(CLzmaEncHandle pp,
2081     ISeqInStream *inStream, UInt32 keepWindowSize,
2082     ISzAlloc *alloc, ISzAlloc *allocBig)
2083 {
2084   CLzmaEnc *p = (CLzmaEnc *)pp;
2085   p->inStream = inStream;
2086   return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);
2087 }
2088
2089 static void LzmaEnc_SetInputBuf(CLzmaEnc *p, const Byte *src, SizeT srcLen)
2090 {
2091   p->seqBufInStream.funcTable.Read = MyRead;
2092   p->seqBufInStream.data = src;
2093   p->seqBufInStream.rem = srcLen;
2094 }
2095
2096 SRes LzmaEnc_MemPrepare(CLzmaEncHandle pp, const Byte *src, SizeT srcLen,
2097     UInt32 keepWindowSize, ISzAlloc *alloc, ISzAlloc *allocBig)
2098 {
2099   CLzmaEnc *p = (CLzmaEnc *)pp;
2100   LzmaEnc_SetInputBuf(p, src, srcLen);
2101   p->inStream = &p->seqBufInStream.funcTable;
2102   return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);
2103 }
2104
2105 void LzmaEnc_Finish(CLzmaEncHandle pp)
2106 {
2107   #ifdef COMPRESS_MF_MT
2108   CLzmaEnc *p = (CLzmaEnc *)pp;
2109   if (p->mtMode)
2110     MatchFinderMt_ReleaseStream(&p->matchFinderMt);
2111   #else
2112   (void)pp;
2113   #endif
2114 }
2115
2116 typedef struct _CSeqOutStreamBuf
2117 {
2118   ISeqOutStream funcTable;
2119   Byte *data;
2120   SizeT rem;
2121   Bool overflow;
2122 } CSeqOutStreamBuf;
2123
2124 static size_t MyWrite(void *pp, const void *data, size_t size)
2125 {
2126   CSeqOutStreamBuf *p = (CSeqOutStreamBuf *)pp;
2127   if (p->rem < size)
2128   {
2129     size = p->rem;
2130     p->overflow = True;
2131   }
2132   memcpy(p->data, data, size);
2133   p->rem -= size;
2134   p->data += size;
2135   return size;
2136 }
2137
2138
2139 UInt32 LzmaEnc_GetNumAvailableBytes(CLzmaEncHandle pp)
2140 {
2141   const CLzmaEnc *p = (CLzmaEnc *)pp;
2142   return p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);
2143 }
2144
2145 const Byte *LzmaEnc_GetCurBuf(CLzmaEncHandle pp)
2146 {
2147   const CLzmaEnc *p = (CLzmaEnc *)pp;
2148   return p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
2149 }
2150
2151 SRes LzmaEnc_CodeOneMemBlock(CLzmaEncHandle pp, Bool reInit,
2152     Byte *dest, size_t *destLen, UInt32 desiredPackSize, UInt32 *unpackSize)
2153 {
2154   CLzmaEnc *p = (CLzmaEnc *)pp;
2155   UInt64 nowPos64;
2156   SRes res;
2157   CSeqOutStreamBuf outStream;
2158
2159   outStream.funcTable.Write = MyWrite;
2160   outStream.data = dest;
2161   outStream.rem = *destLen;
2162   outStream.overflow = False;
2163
2164   p->writeEndMark = False;
2165   p->finished = False;
2166   p->result = SZ_OK;
2167
2168   if (reInit)
2169     LzmaEnc_Init(p);
2170   LzmaEnc_InitPrices(p);
2171   nowPos64 = p->nowPos64;
2172   RangeEnc_Init(&p->rc);
2173   p->rc.outStream = &outStream.funcTable;
2174
2175   res = LzmaEnc_CodeOneBlock(p, True, desiredPackSize, *unpackSize);
2176
2177   *unpackSize = (UInt32)(p->nowPos64 - nowPos64);
2178   *destLen -= outStream.rem;
2179   if (outStream.overflow)
2180     return SZ_ERROR_OUTPUT_EOF;
2181
2182   return res;
2183 }
2184
2185 SRes LzmaEnc_Encode(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream, ICompressProgress *progress,
2186     ISzAlloc *alloc, ISzAlloc *allocBig)
2187 {
2188   CLzmaEnc *p = (CLzmaEnc *)pp;
2189   SRes res = SZ_OK;
2190
2191   #ifdef COMPRESS_MF_MT
2192   Byte allocaDummy[0x300];
2193   int i = 0;
2194   for (i = 0; i < 16; i++)
2195     allocaDummy[i] = (Byte)i;
2196   #endif
2197
2198   RINOK(LzmaEnc_Prepare(pp, inStream, outStream, alloc, allocBig));
2199
2200   for (;;)
2201   {
2202     res = LzmaEnc_CodeOneBlock(p, False, 0, 0);
2203     if (res != SZ_OK || p->finished != 0)
2204       break;
2205     if (progress != 0)
2206     {
2207       res = progress->Progress(progress, p->nowPos64, RangeEnc_GetProcessed(&p->rc));
2208       if (res != SZ_OK)
2209       {
2210         res = SZ_ERROR_PROGRESS;
2211         break;
2212       }
2213     }
2214   }
2215   LzmaEnc_Finish(pp);
2216   return res;
2217 }
2218
2219 SRes LzmaEnc_WriteProperties(CLzmaEncHandle pp, Byte *props, SizeT *size)
2220 {
2221   CLzmaEnc *p = (CLzmaEnc *)pp;
2222   int i;
2223   UInt32 dictSize = p->dictSize;
2224   if (*size < LZMA_PROPS_SIZE)
2225     return SZ_ERROR_PARAM;
2226   *size = LZMA_PROPS_SIZE;
2227   props[0] = (Byte)((p->pb * 5 + p->lp) * 9 + p->lc);
2228
2229   for (i = 11; i <= 30; i++)
2230   {
2231     if (dictSize <= ((UInt32)2 << i))
2232     {
2233       dictSize = (2 << i);
2234       break;
2235     }
2236     if (dictSize <= ((UInt32)3 << i))
2237     {
2238       dictSize = (3 << i);
2239       break;
2240     }
2241   }
2242
2243   for (i = 0; i < 4; i++)
2244     props[1 + i] = (Byte)(dictSize >> (8 * i));
2245   return SZ_OK;
2246 }
2247
2248 SRes LzmaEnc_MemEncode(CLzmaEncHandle pp, Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
2249     int writeEndMark, ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig)
2250 {
2251   SRes res;
2252   CLzmaEnc *p = (CLzmaEnc *)pp;
2253
2254   CSeqOutStreamBuf outStream;
2255
2256   LzmaEnc_SetInputBuf(p, src, srcLen);
2257
2258   outStream.funcTable.Write = MyWrite;
2259   outStream.data = dest;
2260   outStream.rem = *destLen;
2261   outStream.overflow = False;
2262
2263   p->writeEndMark = writeEndMark;
2264   res = LzmaEnc_Encode(pp, &outStream.funcTable, &p->seqBufInStream.funcTable,
2265       progress, alloc, allocBig);
2266
2267   *destLen -= outStream.rem;
2268   if (outStream.overflow)
2269     return SZ_ERROR_OUTPUT_EOF;
2270   return res;
2271 }
2272
2273 SRes LzmaEncode(Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
2274     const CLzmaEncProps *props, Byte *propsEncoded, SizeT *propsSize, int writeEndMark,
2275     ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig)
2276 {
2277   CLzmaEnc *p = (CLzmaEnc *)LzmaEnc_Create(alloc);
2278   SRes res;
2279   if (p == 0)
2280     return SZ_ERROR_MEM;
2281
2282   res = LzmaEnc_SetProps(p, props);
2283   if (res == SZ_OK)
2284   {
2285     res = LzmaEnc_WriteProperties(p, propsEncoded, propsSize);
2286     if (res == SZ_OK)
2287       res = LzmaEnc_MemEncode(p, dest, destLen, src, srcLen,
2288           writeEndMark, progress, alloc, allocBig);
2289   }
2290
2291   LzmaEnc_Destroy(p, alloc, allocBig);
2292   return res;
2293 }