arch/common/boot/grub2/lib/LzmaEnc.c

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