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