util/cbfstool/lzma/C/LzmaEnc.c

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