third_party/lzma_sdk/LzmaEnc.c

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