BaseTools/Source/C/LzmaCompress/Sdk/C/LzmaEnc.c

   1 /* LzmaEnc.c -- LZMA Encoder
   2 2018-04-29 : Igor Pavlov : Public domain */
   3
   4 #include "Precomp.h"
   5
   6 #include <string.h>
   7
   8 /* #define SHOW_STAT */
   9 /* #define SHOW_STAT2 */
  10
  11 #if defined(SHOW_STAT) || defined(SHOW_STAT2)
  12 #include <stdio.h>
  13 #endif
  14
  15 #include "LzmaEnc.h"
  16
  17 #include "LzFind.h"
  18 #ifndef _7ZIP_ST
  19 #include "LzFindMt.h"
  20 #endif
  21
  22 #ifdef SHOW_STAT
  23 static unsigned g_STAT_OFFSET = 0;
  24 #endif
  25
  26 #define kLzmaMaxHistorySize ((UInt32)3 << 29)
  27 /* #define kLzmaMaxHistorySize ((UInt32)7 << 29) */
  28
  29 #define kNumTopBits 24
  30 #define kTopValue ((UInt32)1 << kNumTopBits)
  31
  32 #define kNumBitModelTotalBits 11
  33 #define kBitModelTotal (1 << kNumBitModelTotalBits)
  34 #define kNumMoveBits 5
  35 #define kProbInitValue (kBitModelTotal >> 1)
  36
  37 #define kNumMoveReducingBits 4
  38 #define kNumBitPriceShiftBits 4
  39 #define kBitPrice (1 << kNumBitPriceShiftBits)
  40
  41 void LzmaEncProps_Init(CLzmaEncProps *p)
  42 {
  43   p->level = 5;
  44   p->dictSize = p->mc = 0;
  45   p->reduceSize = (UInt64)(Int64)-1;
  46   p->lc = p->lp = p->pb = p->algo = p->fb = p->btMode = p->numHashBytes = p->numThreads = -1;
  47   p->writeEndMark = 0;
  48 }
  49
  50 void LzmaEncProps_Normalize(CLzmaEncProps *p)
  51 {
  52   int level = p->level;
  53   if (level < 0) level = 5;
  54   p->level = level;
  55
  56   if (p->dictSize == 0) p->dictSize = (level <= 5 ? (1 << (level * 2 + 14)) : (level <= 7 ? (1 << 25) : (1 << 26)));
  57   if (p->dictSize > p->reduceSize)
  58   {
  59     unsigned i;
  60     UInt32 reduceSize = (UInt32)p->reduceSize;
  61     for (i = 11; i <= 30; i++)
  62     {
  63       if (reduceSize <= ((UInt32)2 << i)) { p->dictSize = ((UInt32)2 << i); break; }
  64       if (reduceSize <= ((UInt32)3 << i)) { p->dictSize = ((UInt32)3 << i); break; }
  65     }
  66   }
  67
  68   if (p->lc < 0) p->lc = 3;
  69   if (p->lp < 0) p->lp = 0;
  70   if (p->pb < 0) p->pb = 2;
  71
  72   if (p->algo < 0) p->algo = (level < 5 ? 0 : 1);
  73   if (p->fb < 0) p->fb = (level < 7 ? 32 : 64);
  74   if (p->btMode < 0) p->btMode = (p->algo == 0 ? 0 : 1);
  75   if (p->numHashBytes < 0) p->numHashBytes = 4;
  76   if (p->mc == 0) p->mc = (16 + (p->fb >> 1)) >> (p->btMode ? 0 : 1);
  77
  78   if (p->numThreads < 0)
  79     p->numThreads =
  80       #ifndef _7ZIP_ST
  81       ((p->btMode && p->algo) ? 2 : 1);
  82       #else
  83       1;
  84       #endif
  85 }
  86
  87 UInt32 LzmaEncProps_GetDictSize(const CLzmaEncProps *props2)
  88 {
  89   CLzmaEncProps props = *props2;
  90   LzmaEncProps_Normalize(&props);
  91   return props.dictSize;
  92 }
  93
  94 #if (_MSC_VER >= 1400)
  95 /* BSR code is fast for some new CPUs */
  96 /* #define LZMA_LOG_BSR */
  97 #endif
  98
  99 #ifdef LZMA_LOG_BSR
 100
 101 #define kDicLogSizeMaxCompress 32
 102
 103 #define BSR2_RET(pos, res) { unsigned long zz; _BitScanReverse(&zz, (pos)); res = (zz + zz) + ((pos >> (zz - 1)) & 1); }
 104
 105 static unsigned GetPosSlot1(UInt32 pos)
 106 {
 107   unsigned res;
 108   BSR2_RET(pos, res);
 109   return res;
 110 }
 111 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }
 112 #define GetPosSlot(pos, res) { if (pos < 2) res = pos; else BSR2_RET(pos, res); }
 113
 114 #else
 115
 116 #define kNumLogBits (9 + sizeof(size_t) / 2)
 117 /* #define kNumLogBits (11 + sizeof(size_t) / 8 * 3) */
 118
 119 #define kDicLogSizeMaxCompress ((kNumLogBits - 1) * 2 + 7)
 120
 121 static void LzmaEnc_FastPosInit(Byte *g_FastPos)
 122 {
 123   unsigned slot;
 124   g_FastPos[0] = 0;
 125   g_FastPos[1] = 1;
 126   g_FastPos += 2;
 127
 128   for (slot = 2; slot < kNumLogBits * 2; slot++)
 129   {
 130     size_t k = ((size_t)1 << ((slot >> 1) - 1));
 131     size_t j;
 132     for (j = 0; j < k; j++)
 133       g_FastPos[j] = (Byte)slot;
 134     g_FastPos += k;
 135   }
 136 }
 137
 138 /* we can use ((limit - pos) >> 31) only if (pos < ((UInt32)1 << 31)) */
 139 /*
 140 #define BSR2_RET(pos, res) { unsigned zz = 6 + ((kNumLogBits - 1) & \
 141   (0 - (((((UInt32)1 << (kNumLogBits + 6)) - 1) - pos) >> 31))); \
 142   res = p->g_FastPos[pos >> zz] + (zz * 2); }
 143 */
 144
 145 /*
 146 #define BSR2_RET(pos, res) { unsigned zz = 6 + ((kNumLogBits - 1) & \
 147   (0 - (((((UInt32)1 << (kNumLogBits)) - 1) - (pos >> 6)) >> 31))); \
 148   res = p->g_FastPos[pos >> zz] + (zz * 2); }
 149 */
 150
 151 #define BSR2_RET(pos, res) { unsigned zz = (pos < (1 << (kNumLogBits + 6))) ? 6 : 6 + kNumLogBits - 1; \
 152   res = p->g_FastPos[pos >> zz] + (zz * 2); }
 153
 154 /*
 155 #define BSR2_RET(pos, res) { res = (pos < (1 << (kNumLogBits + 6))) ? \
 156   p->g_FastPos[pos >> 6] + 12 : \
 157   p->g_FastPos[pos >> (6 + kNumLogBits - 1)] + (6 + (kNumLogBits - 1)) * 2; }
 158 */
 159
 160 #define GetPosSlot1(pos) p->g_FastPos[pos]
 161 #define GetPosSlot2(pos, res) { BSR2_RET(pos, res); }
 162 #define GetPosSlot(pos, res) { if (pos < kNumFullDistances) res = p->g_FastPos[pos & (kNumFullDistances - 1)]; else BSR2_RET(pos, res); }
 163
 164 #endif
 165
 166
 167 #define LZMA_NUM_REPS 4
 168
 169 typedef UInt16 CState;
 170 typedef UInt16 CExtra;
 171
 172 typedef struct
 173 {
 174   UInt32 price;
 175   CState state;
 176   CExtra extra;
 177       // 0   : normal
 178       // 1   : LIT : MATCH
 179       // > 1 : MATCH (extra-1) : LIT : REP0 (len)
 180   UInt32 len;
 181   UInt32 dist;
 182   UInt32 reps[LZMA_NUM_REPS];
 183 } COptimal;
 184
 185
 186 #define kNumOpts (1 << 12)
 187 #define kPackReserve (1 + kNumOpts * 2)
 188
 189 #define kNumLenToPosStates 4
 190 #define kNumPosSlotBits 6
 191 #define kDicLogSizeMin 0
 192 #define kDicLogSizeMax 32
 193 #define kDistTableSizeMax (kDicLogSizeMax * 2)
 194
 195 #define kNumAlignBits 4
 196 #define kAlignTableSize (1 << kNumAlignBits)
 197 #define kAlignMask (kAlignTableSize - 1)
 198
 199 #define kStartPosModelIndex 4
 200 #define kEndPosModelIndex 14
 201 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
 202
 203 typedef
 204 #ifdef _LZMA_PROB32
 205   UInt32
 206 #else
 207   UInt16
 208 #endif
 209   CLzmaProb;
 210
 211 #define LZMA_PB_MAX 4
 212 #define LZMA_LC_MAX 8
 213 #define LZMA_LP_MAX 4
 214
 215 #define LZMA_NUM_PB_STATES_MAX (1 << LZMA_PB_MAX)
 216
 217 #define kLenNumLowBits 3
 218 #define kLenNumLowSymbols (1 << kLenNumLowBits)
 219 #define kLenNumHighBits 8
 220 #define kLenNumHighSymbols (1 << kLenNumHighBits)
 221 #define kLenNumSymbolsTotal (kLenNumLowSymbols * 2 + kLenNumHighSymbols)
 222
 223 #define LZMA_MATCH_LEN_MIN 2
 224 #define LZMA_MATCH_LEN_MAX (LZMA_MATCH_LEN_MIN + kLenNumSymbolsTotal - 1)
 225
 226 #define kNumStates 12
 227
 228
 229 typedef struct
 230 {
 231   CLzmaProb low[LZMA_NUM_PB_STATES_MAX << (kLenNumLowBits + 1)];
 232   CLzmaProb high[kLenNumHighSymbols];
 233 } CLenEnc;
 234
 235
 236 typedef struct
 237 {
 238   unsigned tableSize;
 239   unsigned counters[LZMA_NUM_PB_STATES_MAX];
 240   UInt32 prices[LZMA_NUM_PB_STATES_MAX][kLenNumSymbolsTotal];
 241 } CLenPriceEnc;
 242
 243
 244 typedef struct
 245 {
 246   UInt32 range;
 247   unsigned cache;
 248   UInt64 low;
 249   UInt64 cacheSize;
 250   Byte *buf;
 251   Byte *bufLim;
 252   Byte *bufBase;
 253   ISeqOutStream *outStream;
 254   UInt64 processed;
 255   SRes res;
 256 } CRangeEnc;
 257
 258
 259 typedef struct
 260 {
 261   CLzmaProb *litProbs;
 262
 263   unsigned state;
 264   UInt32 reps[LZMA_NUM_REPS];
 265
 266   CLzmaProb posAlignEncoder[1 << kNumAlignBits];
 267   CLzmaProb isRep[kNumStates];
 268   CLzmaProb isRepG0[kNumStates];
 269   CLzmaProb isRepG1[kNumStates];
 270   CLzmaProb isRepG2[kNumStates];
 271   CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];
 272   CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];
 273
 274   CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];
 275   CLzmaProb posEncoders[kNumFullDistances];
 276
 277   CLenEnc lenProbs;
 278   CLenEnc repLenProbs;
 279
 280 } CSaveState;
 281
 282
 283 typedef UInt32 CProbPrice;
 284
 285
 286 typedef struct
 287 {
 288   void *matchFinderObj;
 289   IMatchFinder matchFinder;
 290
 291   unsigned optCur;
 292   unsigned optEnd;
 293
 294   unsigned longestMatchLen;
 295   unsigned numPairs;
 296   UInt32 numAvail;
 297
 298   unsigned state;
 299   unsigned numFastBytes;
 300   unsigned additionalOffset;
 301   UInt32 reps[LZMA_NUM_REPS];
 302   unsigned lpMask, pbMask;
 303   CLzmaProb *litProbs;
 304   CRangeEnc rc;
 305
 306   UInt32 backRes;
 307
 308   unsigned lc, lp, pb;
 309   unsigned lclp;
 310
 311   Bool fastMode;
 312   Bool writeEndMark;
 313   Bool finished;
 314   Bool multiThread;
 315   Bool needInit;
 316
 317   UInt64 nowPos64;
 318
 319   unsigned matchPriceCount;
 320   unsigned alignPriceCount;
 321
 322   unsigned distTableSize;
 323
 324   UInt32 dictSize;
 325   SRes result;
 326
 327   #ifndef _7ZIP_ST
 328   Bool mtMode;
 329   // begin of CMatchFinderMt is used in LZ thread
 330   CMatchFinderMt matchFinderMt;
 331   // end of CMatchFinderMt is used in BT and HASH threads
 332   #endif
 333
 334   CMatchFinder matchFinderBase;
 335
 336   #ifndef _7ZIP_ST
 337   Byte pad[128];
 338   #endif
 339
 340   // LZ thread
 341   CProbPrice ProbPrices[kBitModelTotal >> kNumMoveReducingBits];
 342
 343   UInt32 matches[LZMA_MATCH_LEN_MAX * 2 + 2 + 1];
 344
 345   UInt32 alignPrices[kAlignTableSize];
 346   UInt32 posSlotPrices[kNumLenToPosStates][kDistTableSizeMax];
 347   UInt32 distancesPrices[kNumLenToPosStates][kNumFullDistances];
 348
 349   CLzmaProb posAlignEncoder[1 << kNumAlignBits];
 350   CLzmaProb isRep[kNumStates];
 351   CLzmaProb isRepG0[kNumStates];
 352   CLzmaProb isRepG1[kNumStates];
 353   CLzmaProb isRepG2[kNumStates];
 354   CLzmaProb isMatch[kNumStates][LZMA_NUM_PB_STATES_MAX];
 355   CLzmaProb isRep0Long[kNumStates][LZMA_NUM_PB_STATES_MAX];
 356   CLzmaProb posSlotEncoder[kNumLenToPosStates][1 << kNumPosSlotBits];
 357   CLzmaProb posEncoders[kNumFullDistances];
 358
 359   CLenEnc lenProbs;
 360   CLenEnc repLenProbs;
 361
 362   #ifndef LZMA_LOG_BSR
 363   Byte g_FastPos[1 << kNumLogBits];
 364   #endif
 365
 366   CLenPriceEnc lenEnc;
 367   CLenPriceEnc repLenEnc;
 368
 369   COptimal opt[kNumOpts];
 370
 371   CSaveState saveState;
 372
 373   #ifndef _7ZIP_ST
 374   Byte pad2[128];
 375   #endif
 376 } CLzmaEnc;
 377
 378
 379
 380 #define COPY_ARR(dest, src, arr) memcpy(dest->arr, src->arr, sizeof(src->arr));
 381
 382 void LzmaEnc_SaveState(CLzmaEncHandle pp)
 383 {
 384   CLzmaEnc *p = (CLzmaEnc *)pp;
 385   CSaveState *dest = &p->saveState;
 386
 387   dest->state = p->state;
 388
 389   dest->lenProbs = p->lenProbs;
 390   dest->repLenProbs = p->repLenProbs;
 391
 392   COPY_ARR(dest, p, reps);
 393
 394   COPY_ARR(dest, p, posAlignEncoder);
 395   COPY_ARR(dest, p, isRep);
 396   COPY_ARR(dest, p, isRepG0);
 397   COPY_ARR(dest, p, isRepG1);
 398   COPY_ARR(dest, p, isRepG2);
 399   COPY_ARR(dest, p, isMatch);
 400   COPY_ARR(dest, p, isRep0Long);
 401   COPY_ARR(dest, p, posSlotEncoder);
 402   COPY_ARR(dest, p, posEncoders);
 403
 404   memcpy(dest->litProbs, p->litProbs, ((UInt32)0x300 << p->lclp) * sizeof(CLzmaProb));
 405 }
 406
 407
 408 void LzmaEnc_RestoreState(CLzmaEncHandle pp)
 409 {
 410   CLzmaEnc *dest = (CLzmaEnc *)pp;
 411   const CSaveState *p = &dest->saveState;
 412
 413   dest->state = p->state;
 414
 415   dest->lenProbs = p->lenProbs;
 416   dest->repLenProbs = p->repLenProbs;
 417
 418   COPY_ARR(dest, p, reps);
 419
 420   COPY_ARR(dest, p, posAlignEncoder);
 421   COPY_ARR(dest, p, isRep);
 422   COPY_ARR(dest, p, isRepG0);
 423   COPY_ARR(dest, p, isRepG1);
 424   COPY_ARR(dest, p, isRepG2);
 425   COPY_ARR(dest, p, isMatch);
 426   COPY_ARR(dest, p, isRep0Long);
 427   COPY_ARR(dest, p, posSlotEncoder);
 428   COPY_ARR(dest, p, posEncoders);
 429
 430   memcpy(dest->litProbs, p->litProbs, ((UInt32)0x300 << dest->lclp) * sizeof(CLzmaProb));
 431 }
 432
 433
 434
 435 SRes LzmaEnc_SetProps(CLzmaEncHandle pp, const CLzmaEncProps *props2)
 436 {
 437   CLzmaEnc *p = (CLzmaEnc *)pp;
 438   CLzmaEncProps props = *props2;
 439   LzmaEncProps_Normalize(&props);
 440
 441   if (props.lc > LZMA_LC_MAX
 442       || props.lp > LZMA_LP_MAX
 443       || props.pb > LZMA_PB_MAX
 444       || props.dictSize > ((UInt64)1 << kDicLogSizeMaxCompress)
 445       || props.dictSize > kLzmaMaxHistorySize)
 446     return SZ_ERROR_PARAM;
 447
 448   p->dictSize = props.dictSize;
 449   {
 450     unsigned fb = props.fb;
 451     if (fb < 5)
 452       fb = 5;
 453     if (fb > LZMA_MATCH_LEN_MAX)
 454       fb = LZMA_MATCH_LEN_MAX;
 455     p->numFastBytes = fb;
 456   }
 457   p->lc = props.lc;
 458   p->lp = props.lp;
 459   p->pb = props.pb;
 460   p->fastMode = (props.algo == 0);
 461   p->matchFinderBase.btMode = (Byte)(props.btMode ? 1 : 0);
 462   {
 463     unsigned numHashBytes = 4;
 464     if (props.btMode)
 465     {
 466       if (props.numHashBytes < 2)
 467         numHashBytes = 2;
 468       else if (props.numHashBytes < 4)
 469         numHashBytes = props.numHashBytes;
 470     }
 471     p->matchFinderBase.numHashBytes = numHashBytes;
 472   }
 473
 474   p->matchFinderBase.cutValue = props.mc;
 475
 476   p->writeEndMark = props.writeEndMark;
 477
 478   #ifndef _7ZIP_ST
 479   /*
 480   if (newMultiThread != _multiThread)
 481   {
 482     ReleaseMatchFinder();
 483     _multiThread = newMultiThread;
 484   }
 485   */
 486   p->multiThread = (props.numThreads > 1);
 487   #endif
 488
 489   return SZ_OK;
 490 }
 491
 492
 493 void LzmaEnc_SetDataSize(CLzmaEncHandle pp, UInt64 expectedDataSiize)
 494 {
 495   CLzmaEnc *p = (CLzmaEnc *)pp;
 496   p->matchFinderBase.expectedDataSize = expectedDataSiize;
 497 }
 498
 499
 500 #define kState_Start 0
 501 #define kState_LitAfterMatch 4
 502 #define kState_LitAfterRep   5
 503 #define kState_MatchAfterLit 7
 504 #define kState_RepAfterLit   8
 505
 506 static const Byte kLiteralNextStates[kNumStates] = {0, 0, 0, 0, 1, 2, 3, 4,  5,  6,   4, 5};
 507 static const Byte kMatchNextStates[kNumStates]   = {7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10};
 508 static const Byte kRepNextStates[kNumStates]     = {8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11};
 509 static const Byte kShortRepNextStates[kNumStates]= {9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11};
 510
 511 #define IsLitState(s) ((s) < 7)
 512 #define GetLenToPosState2(len) (((len) < kNumLenToPosStates - 1) ? (len) : kNumLenToPosStates - 1)
 513 #define GetLenToPosState(len) (((len) < kNumLenToPosStates + 1) ? (len) - 2 : kNumLenToPosStates - 1)
 514
 515 #define kInfinityPrice (1 << 30)
 516
 517 static void RangeEnc_Construct(CRangeEnc *p)
 518 {
 519   p->outStream = NULL;
 520   p->bufBase = NULL;
 521 }
 522
 523 #define RangeEnc_GetProcessed(p)       ((p)->processed + ((p)->buf - (p)->bufBase) + (p)->cacheSize)
 524 #define RangeEnc_GetProcessed_sizet(p) ((size_t)(p)->processed + ((p)->buf - (p)->bufBase) + (size_t)(p)->cacheSize)
 525
 526 #define RC_BUF_SIZE (1 << 16)
 527
 528 static int RangeEnc_Alloc(CRangeEnc *p, ISzAllocPtr alloc)
 529 {
 530   if (!p->bufBase)
 531   {
 532     p->bufBase = (Byte *)ISzAlloc_Alloc(alloc, RC_BUF_SIZE);
 533     if (!p->bufBase)
 534       return 0;
 535     p->bufLim = p->bufBase + RC_BUF_SIZE;
 536   }
 537   return 1;
 538 }
 539
 540 static void RangeEnc_Free(CRangeEnc *p, ISzAllocPtr alloc)
 541 {
 542   ISzAlloc_Free(alloc, p->bufBase);
 543   p->bufBase = 0;
 544 }
 545
 546 static void RangeEnc_Init(CRangeEnc *p)
 547 {
 548   /* Stream.Init(); */
 549   p->range = 0xFFFFFFFF;
 550   p->cache = 0;
 551   p->low = 0;
 552   p->cacheSize = 0;
 553
 554   p->buf = p->bufBase;
 555
 556   p->processed = 0;
 557   p->res = SZ_OK;
 558 }
 559
 560 MY_NO_INLINE static void RangeEnc_FlushStream(CRangeEnc *p)
 561 {
 562   size_t num;
 563   if (p->res != SZ_OK)
 564     return;
 565   num = p->buf - p->bufBase;
 566   if (num != ISeqOutStream_Write(p->outStream, p->bufBase, num))
 567     p->res = SZ_ERROR_WRITE;
 568   p->processed += num;
 569   p->buf = p->bufBase;
 570 }
 571
 572 MY_NO_INLINE static void MY_FAST_CALL RangeEnc_ShiftLow(CRangeEnc *p)
 573 {
 574   UInt32 low = (UInt32)p->low;
 575   unsigned high = (unsigned)(p->low >> 32);
 576   p->low = (UInt32)(low << 8);
 577   if (low < (UInt32)0xFF000000 || high != 0)
 578   {
 579     {
 580       Byte *buf = p->buf;
 581       *buf++ = (Byte)(p->cache + high);
 582       p->cache = (unsigned)(low >> 24);
 583       p->buf = buf;
 584       if (buf == p->bufLim)
 585         RangeEnc_FlushStream(p);
 586       if (p->cacheSize == 0)
 587         return;
 588     }
 589     high += 0xFF;
 590     for (;;)
 591     {
 592       Byte *buf = p->buf;
 593       *buf++ = (Byte)(high);
 594       p->buf = buf;
 595       if (buf == p->bufLim)
 596         RangeEnc_FlushStream(p);
 597       if (--p->cacheSize == 0)
 598         return;
 599     }
 600   }
 601   p->cacheSize++;
 602 }
 603
 604 static void RangeEnc_FlushData(CRangeEnc *p)
 605 {
 606   int i;
 607   for (i = 0; i < 5; i++)
 608     RangeEnc_ShiftLow(p);
 609 }
 610
 611 #define RC_NORM(p) if (range < kTopValue) { range <<= 8; RangeEnc_ShiftLow(p); }
 612
 613 #define RC_BIT_PRE(p, prob) \
 614   ttt = *(prob); \
 615   newBound = (range >> kNumBitModelTotalBits) * ttt;
 616
 617 // #define _LZMA_ENC_USE_BRANCH
 618
 619 #ifdef _LZMA_ENC_USE_BRANCH
 620
 621 #define RC_BIT(p, prob, symbol) { \
 622   RC_BIT_PRE(p, prob) \
 623   if (symbol == 0) { range = newBound; ttt += (kBitModelTotal - ttt) >> kNumMoveBits; } \
 624   else { (p)->low += newBound; range -= newBound; ttt -= ttt >> kNumMoveBits; } \
 625   *(prob) = (CLzmaProb)ttt; \
 626   RC_NORM(p) \
 627   }
 628
 629 #else
 630
 631 #define RC_BIT(p, prob, symbol) { \
 632   UInt32 mask; \
 633   RC_BIT_PRE(p, prob) \
 634   mask = 0 - (UInt32)symbol; \
 635   range &= mask; \
 636   mask &= newBound; \
 637   range -= mask; \
 638   (p)->low += mask; \
 639   mask = (UInt32)symbol - 1; \
 640   range += newBound & mask; \
 641   mask &= (kBitModelTotal - ((1 << kNumMoveBits) - 1)); \
 642   mask += ((1 << kNumMoveBits) - 1); \
 643   ttt += (Int32)(mask - ttt) >> kNumMoveBits; \
 644   *(prob) = (CLzmaProb)ttt; \
 645   RC_NORM(p) \
 646   }
 647
 648 #endif
 649
 650
 651
 652
 653 #define RC_BIT_0_BASE(p, prob) \
 654   range = newBound; *(prob) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits));
 655
 656 #define RC_BIT_1_BASE(p, prob) \
 657   range -= newBound; (p)->low += newBound; *(prob) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits)); \
 658
 659 #define RC_BIT_0(p, prob) \
 660   RC_BIT_0_BASE(p, prob) \
 661   RC_NORM(p)
 662
 663 #define RC_BIT_1(p, prob) \
 664   RC_BIT_1_BASE(p, prob) \
 665   RC_NORM(p)
 666
 667 static void RangeEnc_EncodeBit_0(CRangeEnc *p, CLzmaProb *prob)
 668 {
 669   UInt32 range, ttt, newBound;
 670   range = p->range;
 671   RC_BIT_PRE(p, prob)
 672   RC_BIT_0(p, prob)
 673   p->range = range;
 674 }
 675
 676 static void LitEnc_Encode(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol)
 677 {
 678   UInt32 range = p->range;
 679   symbol |= 0x100;
 680   do
 681   {
 682     UInt32 ttt, newBound;
 683     // RangeEnc_EncodeBit(p, probs + (symbol >> 8), (symbol >> 7) & 1);
 684     CLzmaProb *prob = probs + (symbol >> 8);
 685     UInt32 bit = (symbol >> 7) & 1;
 686     symbol <<= 1;
 687     RC_BIT(p, prob, bit);
 688   }
 689   while (symbol < 0x10000);
 690   p->range = range;
 691 }
 692
 693 static void LitEnc_EncodeMatched(CRangeEnc *p, CLzmaProb *probs, UInt32 symbol, UInt32 matchByte)
 694 {
 695   UInt32 range = p->range;
 696   UInt32 offs = 0x100;
 697   symbol |= 0x100;
 698   do
 699   {
 700     UInt32 ttt, newBound;
 701     CLzmaProb *prob;
 702     UInt32 bit;
 703     matchByte <<= 1;
 704     // RangeEnc_EncodeBit(p, probs + (offs + (matchByte & offs) + (symbol >> 8)), (symbol >> 7) & 1);
 705     prob = probs + (offs + (matchByte & offs) + (symbol >> 8));
 706     bit = (symbol >> 7) & 1;
 707     symbol <<= 1;
 708     offs &= ~(matchByte ^ symbol);
 709     RC_BIT(p, prob, bit);
 710   }
 711   while (symbol < 0x10000);
 712   p->range = range;
 713 }
 714
 715
 716
 717 static void LzmaEnc_InitPriceTables(CProbPrice *ProbPrices)
 718 {
 719   UInt32 i;
 720   for (i = 0; i < (kBitModelTotal >> kNumMoveReducingBits); i++)
 721   {
 722     const unsigned kCyclesBits = kNumBitPriceShiftBits;
 723     UInt32 w = (i << kNumMoveReducingBits) + (1 << (kNumMoveReducingBits - 1));
 724     unsigned bitCount = 0;
 725     unsigned j;
 726     for (j = 0; j < kCyclesBits; j++)
 727     {
 728       w = w * w;
 729       bitCount <<= 1;
 730       while (w >= ((UInt32)1 << 16))
 731       {
 732         w >>= 1;
 733         bitCount++;
 734       }
 735     }
 736     ProbPrices[i] = (CProbPrice)((kNumBitModelTotalBits << kCyclesBits) - 15 - bitCount);
 737     // printf("\n%3d: %5d", i, ProbPrices[i]);
 738   }
 739 }
 740
 741
 742 #define GET_PRICE(prob, symbol) \
 743   p->ProbPrices[((prob) ^ (unsigned)(((-(int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];
 744
 745 #define GET_PRICEa(prob, symbol) \
 746      ProbPrices[((prob) ^ (unsigned)((-((int)(symbol))) & (kBitModelTotal - 1))) >> kNumMoveReducingBits];
 747
 748 #define GET_PRICE_0(prob) p->ProbPrices[(prob) >> kNumMoveReducingBits]
 749 #define GET_PRICE_1(prob) p->ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]
 750
 751 #define GET_PRICEa_0(prob) ProbPrices[(prob) >> kNumMoveReducingBits]
 752 #define GET_PRICEa_1(prob) ProbPrices[((prob) ^ (kBitModelTotal - 1)) >> kNumMoveReducingBits]
 753
 754
 755 static UInt32 LitEnc_GetPrice(const CLzmaProb *probs, UInt32 symbol, const CProbPrice *ProbPrices)
 756 {
 757   UInt32 price = 0;
 758   symbol |= 0x100;
 759   do
 760   {
 761     unsigned bit = symbol & 1;
 762     symbol >>= 1;
 763     price += GET_PRICEa(probs[symbol], bit);
 764   }
 765   while (symbol >= 2);
 766   return price;
 767 }
 768
 769
 770 static UInt32 LitEnc_Matched_GetPrice(const CLzmaProb *probs, UInt32 symbol, UInt32 matchByte, const CProbPrice *ProbPrices)
 771 {
 772   UInt32 price = 0;
 773   UInt32 offs = 0x100;
 774   symbol |= 0x100;
 775   do
 776   {
 777     matchByte <<= 1;
 778     price += GET_PRICEa(probs[offs + (matchByte & offs) + (symbol >> 8)], (symbol >> 7) & 1);
 779     symbol <<= 1;
 780     offs &= ~(matchByte ^ symbol);
 781   }
 782   while (symbol < 0x10000);
 783   return price;
 784 }
 785
 786
 787 static void RcTree_ReverseEncode(CRangeEnc *rc, CLzmaProb *probs, unsigned numBits, UInt32 symbol)
 788 {
 789   UInt32 range = rc->range;
 790   unsigned m = 1;
 791   do
 792   {
 793     UInt32 ttt, newBound;
 794     unsigned bit = symbol & 1;
 795     // RangeEnc_EncodeBit(rc, probs + m, bit);
 796     symbol >>= 1;
 797     RC_BIT(rc, probs + m, bit);
 798     m = (m << 1) | bit;
 799   }
 800   while (--numBits);
 801   rc->range = range;
 802 }
 803
 804
 805
 806 static void LenEnc_Init(CLenEnc *p)
 807 {
 808   unsigned i;
 809   for (i = 0; i < (LZMA_NUM_PB_STATES_MAX << (kLenNumLowBits + 1)); i++)
 810     p->low[i] = kProbInitValue;
 811   for (i = 0; i < kLenNumHighSymbols; i++)
 812     p->high[i] = kProbInitValue;
 813 }
 814
 815 static void LenEnc_Encode(CLenEnc *p, CRangeEnc *rc, unsigned symbol, unsigned posState)
 816 {
 817   UInt32 range, ttt, newBound;
 818   CLzmaProb *probs = p->low;
 819   range = rc->range;
 820   RC_BIT_PRE(rc, probs);
 821   if (symbol >= kLenNumLowSymbols)
 822   {
 823     RC_BIT_1(rc, probs);
 824     probs += kLenNumLowSymbols;
 825     RC_BIT_PRE(rc, probs);
 826     if (symbol >= kLenNumLowSymbols * 2)
 827     {
 828       RC_BIT_1(rc, probs);
 829       rc->range = range;
 830       // RcTree_Encode(rc, p->high, kLenNumHighBits, symbol - kLenNumLowSymbols * 2);
 831       LitEnc_Encode(rc, p->high, symbol - kLenNumLowSymbols * 2);
 832       return;
 833     }
 834     symbol -= kLenNumLowSymbols;
 835   }
 836
 837   // RcTree_Encode(rc, probs + (posState << kLenNumLowBits), kLenNumLowBits, symbol);
 838   {
 839     unsigned m;
 840     unsigned bit;
 841     RC_BIT_0(rc, probs);
 842     probs += (posState << (1 + kLenNumLowBits));
 843     bit = (symbol >> 2)    ; RC_BIT(rc, probs + 1, bit); m = (1 << 1) + bit;
 844     bit = (symbol >> 1) & 1; RC_BIT(rc, probs + m, bit); m = (m << 1) + bit;
 845     bit =  symbol       & 1; RC_BIT(rc, probs + m, bit);
 846     rc->range = range;
 847   }
 848 }
 849
 850 static void SetPrices_3(const CLzmaProb *probs, UInt32 startPrice, UInt32 *prices, const CProbPrice *ProbPrices)
 851 {
 852   unsigned i;
 853   for (i = 0; i < 8; i += 2)
 854   {
 855     UInt32 price = startPrice;
 856     UInt32 prob;
 857     price += GET_PRICEa(probs[1           ], (i >> 2));
 858     price += GET_PRICEa(probs[2 + (i >> 2)], (i >> 1) & 1);
 859     prob = probs[4 + (i >> 1)];
 860     prices[i    ] = price + GET_PRICEa_0(prob);
 861     prices[i + 1] = price + GET_PRICEa_1(prob);
 862   }
 863 }
 864
 865
 866 MY_NO_INLINE static void MY_FAST_CALL LenPriceEnc_UpdateTable(
 867     CLenPriceEnc *p, unsigned posState,
 868     const CLenEnc *enc,
 869     const CProbPrice *ProbPrices)
 870 {
 871   // int y; for (y = 0; y < 100; y++) {
 872   UInt32 a;
 873   unsigned i, numSymbols;
 874
 875   UInt32 *prices = p->prices[posState];
 876   {
 877     const CLzmaProb *probs = enc->low + (posState << (1 + kLenNumLowBits));
 878     SetPrices_3(probs, GET_PRICEa_0(enc->low[0]), prices, ProbPrices);
 879     a = GET_PRICEa_1(enc->low[0]);
 880     SetPrices_3(probs + kLenNumLowSymbols, a + GET_PRICEa_0(enc->low[kLenNumLowSymbols]), prices + kLenNumLowSymbols, ProbPrices);
 881     a += GET_PRICEa_1(enc->low[kLenNumLowSymbols]);
 882   }
 883   numSymbols = p->tableSize;
 884   p->counters[posState] = numSymbols;
 885   for (i = kLenNumLowSymbols * 2; i < numSymbols; i += 1)
 886   {
 887     prices[i] = a +
 888        // RcTree_GetPrice(enc->high, kLenNumHighBits, i - kLenNumLowSymbols * 2, ProbPrices);
 889        LitEnc_GetPrice(enc->high, i - kLenNumLowSymbols * 2, ProbPrices);
 890     /*
 891     unsigned sym = (i - kLenNumLowSymbols * 2) >> 1;
 892     UInt32 price = a + RcTree_GetPrice(enc->high, kLenNumHighBits - 1, sym, ProbPrices);
 893     UInt32 prob = enc->high[(1 << 7) + sym];
 894     prices[i    ] = price + GET_PRICEa_0(prob);
 895     prices[i + 1] = price + GET_PRICEa_1(prob);
 896     */
 897   }
 898   // }
 899 }
 900
 901 static void LenPriceEnc_UpdateTables(CLenPriceEnc *p, unsigned numPosStates,
 902     const CLenEnc *enc,
 903     const CProbPrice *ProbPrices)
 904 {
 905   unsigned posState;
 906   for (posState = 0; posState < numPosStates; posState++)
 907     LenPriceEnc_UpdateTable(p, posState, enc, ProbPrices);
 908 }
 909
 910
 911 /*
 912   #ifdef SHOW_STAT
 913   g_STAT_OFFSET += num;
 914   printf("\n MovePos %u", num);
 915   #endif
 916 */
 917
 918 #define MOVE_POS(p, num) { \
 919     p->additionalOffset += (num); \
 920     p->matchFinder.Skip(p->matchFinderObj, (num)); }
 921
 922
 923 static unsigned ReadMatchDistances(CLzmaEnc *p, unsigned *numPairsRes)
 924 {
 925   unsigned numPairs;
 926
 927   p->additionalOffset++;
 928   p->numAvail = p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);
 929   numPairs = p->matchFinder.GetMatches(p->matchFinderObj, p->matches);
 930   *numPairsRes = numPairs;
 931
 932   #ifdef SHOW_STAT
 933   printf("\n i = %u numPairs = %u    ", g_STAT_OFFSET, numPairs / 2);
 934   g_STAT_OFFSET++;
 935   {
 936     unsigned i;
 937     for (i = 0; i < numPairs; i += 2)
 938       printf("%2u %6u   | ", p->matches[i], p->matches[i + 1]);
 939   }
 940   #endif
 941
 942   if (numPairs == 0)
 943     return 0;
 944   {
 945     unsigned len = p->matches[(size_t)numPairs - 2];
 946     if (len != p->numFastBytes)
 947       return len;
 948     {
 949       UInt32 numAvail = p->numAvail;
 950       if (numAvail > LZMA_MATCH_LEN_MAX)
 951         numAvail = LZMA_MATCH_LEN_MAX;
 952       {
 953         const Byte *p1 = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
 954         const Byte *p2 = p1 + len;
 955         ptrdiff_t dif = (ptrdiff_t)-1 - p->matches[(size_t)numPairs - 1];
 956         const Byte *lim = p1 + numAvail;
 957         for (; p2 != lim && *p2 == p2[dif]; p2++);
 958         return (unsigned)(p2 - p1);
 959       }
 960     }
 961   }
 962 }
 963
 964 #define MARK_LIT ((UInt32)(Int32)-1)
 965
 966 #define MakeAs_Lit(p)       { (p)->dist = MARK_LIT; (p)->extra = 0; }
 967 #define MakeAs_ShortRep(p)  { (p)->dist = 0; (p)->extra = 0; }
 968 #define IsShortRep(p)       ((p)->dist == 0)
 969
 970
 971 #define GetPrice_ShortRep(p, state, posState) \
 972   ( GET_PRICE_0(p->isRepG0[state]) + GET_PRICE_0(p->isRep0Long[state][posState]))
 973
 974 #define GetPrice_Rep_0(p, state, posState) ( \
 975     GET_PRICE_1(p->isMatch[state][posState]) \
 976   + GET_PRICE_1(p->isRep0Long[state][posState])) \
 977   + GET_PRICE_1(p->isRep[state]) \
 978   + GET_PRICE_0(p->isRepG0[state])
 979
 980
 981 static UInt32 GetPrice_PureRep(const CLzmaEnc *p, unsigned repIndex, size_t state, size_t posState)
 982 {
 983   UInt32 price;
 984   UInt32 prob = p->isRepG0[state];
 985   if (repIndex == 0)
 986   {
 987     price = GET_PRICE_0(prob);
 988     price += GET_PRICE_1(p->isRep0Long[state][posState]);
 989   }
 990   else
 991   {
 992     price = GET_PRICE_1(prob);
 993     prob = p->isRepG1[state];
 994     if (repIndex == 1)
 995       price += GET_PRICE_0(prob);
 996     else
 997     {
 998       price += GET_PRICE_1(prob);
 999       price += GET_PRICE(p->isRepG2[state], repIndex - 2);
1000     }
1001   }
1002   return price;
1003 }
1004
1005
1006 static unsigned Backward(CLzmaEnc *p, unsigned cur)
1007 {
1008   unsigned wr = cur + 1;
1009   p->optEnd = wr;
1010
1011   for (;;)
1012   {
1013     UInt32 dist = p->opt[cur].dist;
1014     UInt32 len = p->opt[cur].len;
1015     UInt32 extra = p->opt[cur].extra;
1016     cur -= len;
1017
1018     if (extra)
1019     {
1020       wr--;
1021       p->opt[wr].len = len;
1022       cur -= extra;
1023       len = extra;
1024       if (extra == 1)
1025       {
1026         p->opt[wr].dist = dist;
1027         dist = MARK_LIT;
1028       }
1029       else
1030       {
1031         p->opt[wr].dist = 0;
1032         len--;
1033         wr--;
1034         p->opt[wr].dist = MARK_LIT;
1035         p->opt[wr].len = 1;
1036       }
1037     }
1038
1039     if (cur == 0)
1040     {
1041       p->backRes = dist;
1042       p->optCur = wr;
1043       return len;
1044     }
1045
1046     wr--;
1047     p->opt[wr].dist = dist;
1048     p->opt[wr].len = len;
1049   }
1050 }
1051
1052
1053
1054 #define LIT_PROBS(pos, prevByte) \
1055   (p->litProbs + (UInt32)3 * (((((pos) << 8) + (prevByte)) & p->lpMask) << p->lc))
1056
1057
1058 static unsigned GetOptimum(CLzmaEnc *p, UInt32 position)
1059 {
1060   unsigned last, cur;
1061   UInt32 reps[LZMA_NUM_REPS];
1062   unsigned repLens[LZMA_NUM_REPS];
1063   UInt32 *matches;
1064
1065   {
1066     UInt32 numAvail;
1067     unsigned numPairs, mainLen, repMaxIndex, i, posState;
1068     UInt32 matchPrice, repMatchPrice;
1069     const Byte *data;
1070     Byte curByte, matchByte;
1071
1072     p->optCur = p->optEnd = 0;
1073
1074     if (p->additionalOffset == 0)
1075       mainLen = ReadMatchDistances(p, &numPairs);
1076     else
1077     {
1078       mainLen = p->longestMatchLen;
1079       numPairs = p->numPairs;
1080     }
1081
1082     numAvail = p->numAvail;
1083     if (numAvail < 2)
1084     {
1085       p->backRes = MARK_LIT;
1086       return 1;
1087     }
1088     if (numAvail > LZMA_MATCH_LEN_MAX)
1089       numAvail = LZMA_MATCH_LEN_MAX;
1090
1091     data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1092     repMaxIndex = 0;
1093
1094     for (i = 0; i < LZMA_NUM_REPS; i++)
1095     {
1096       unsigned len;
1097       const Byte *data2;
1098       reps[i] = p->reps[i];
1099       data2 = data - reps[i];
1100       if (data[0] != data2[0] || data[1] != data2[1])
1101       {
1102         repLens[i] = 0;
1103         continue;
1104       }
1105       for (len = 2; len < numAvail && data[len] == data2[len]; len++);
1106       repLens[i] = len;
1107       if (len > repLens[repMaxIndex])
1108         repMaxIndex = i;
1109     }
1110
1111     if (repLens[repMaxIndex] >= p->numFastBytes)
1112     {
1113       unsigned len;
1114       p->backRes = repMaxIndex;
1115       len = repLens[repMaxIndex];
1116       MOVE_POS(p, len - 1)
1117       return len;
1118     }
1119
1120     matches = p->matches;
1121
1122     if (mainLen >= p->numFastBytes)
1123     {
1124       p->backRes = matches[(size_t)numPairs - 1] + LZMA_NUM_REPS;
1125       MOVE_POS(p, mainLen - 1)
1126       return mainLen;
1127     }
1128
1129     curByte = *data;
1130     matchByte = *(data - reps[0]);
1131
1132     if (mainLen < 2 && curByte != matchByte && repLens[repMaxIndex] < 2)
1133     {
1134       p->backRes = MARK_LIT;
1135       return 1;
1136     }
1137
1138     p->opt[0].state = (CState)p->state;
1139
1140     posState = (position & p->pbMask);
1141
1142     {
1143       const CLzmaProb *probs = LIT_PROBS(position, *(data - 1));
1144       p->opt[1].price = GET_PRICE_0(p->isMatch[p->state][posState]) +
1145         (!IsLitState(p->state) ?
1146           LitEnc_Matched_GetPrice(probs, curByte, matchByte, p->ProbPrices) :
1147           LitEnc_GetPrice(probs, curByte, p->ProbPrices));
1148     }
1149
1150     MakeAs_Lit(&p->opt[1]);
1151
1152     matchPrice = GET_PRICE_1(p->isMatch[p->state][posState]);
1153     repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[p->state]);
1154
1155     if (matchByte == curByte)
1156     {
1157       UInt32 shortRepPrice = repMatchPrice + GetPrice_ShortRep(p, p->state, posState);
1158       if (shortRepPrice < p->opt[1].price)
1159       {
1160         p->opt[1].price = shortRepPrice;
1161         MakeAs_ShortRep(&p->opt[1]);
1162       }
1163     }
1164
1165     last = (mainLen >= repLens[repMaxIndex] ? mainLen : repLens[repMaxIndex]);
1166
1167     if (last < 2)
1168     {
1169       p->backRes = p->opt[1].dist;
1170       return 1;
1171     }
1172
1173     p->opt[1].len = 1;
1174
1175     p->opt[0].reps[0] = reps[0];
1176     p->opt[0].reps[1] = reps[1];
1177     p->opt[0].reps[2] = reps[2];
1178     p->opt[0].reps[3] = reps[3];
1179
1180     {
1181       unsigned len = last;
1182       do
1183         p->opt[len--].price = kInfinityPrice;
1184       while (len >= 2);
1185     }
1186
1187     // ---------- REP ----------
1188
1189     for (i = 0; i < LZMA_NUM_REPS; i++)
1190     {
1191       unsigned repLen = repLens[i];
1192       UInt32 price;
1193       if (repLen < 2)
1194         continue;
1195       price = repMatchPrice + GetPrice_PureRep(p, i, p->state, posState);
1196       do
1197       {
1198         UInt32 price2 = price + p->repLenEnc.prices[posState][(size_t)repLen - 2];
1199         COptimal *opt = &p->opt[repLen];
1200         if (price2 < opt->price)
1201         {
1202           opt->price = price2;
1203           opt->len = repLen;
1204           opt->dist = i;
1205           opt->extra = 0;
1206         }
1207       }
1208       while (--repLen >= 2);
1209     }
1210
1211
1212     // ---------- MATCH ----------
1213     {
1214       unsigned len  = ((repLens[0] >= 2) ? repLens[0] + 1 : 2);
1215       if (len <= mainLen)
1216       {
1217         unsigned offs = 0;
1218         UInt32 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[p->state]);
1219
1220         while (len > matches[offs])
1221           offs += 2;
1222
1223         for (; ; len++)
1224         {
1225           COptimal *opt;
1226           UInt32 dist = matches[(size_t)offs + 1];
1227           UInt32 price2 = normalMatchPrice + p->lenEnc.prices[posState][(size_t)len - LZMA_MATCH_LEN_MIN];
1228           unsigned lenToPosState = GetLenToPosState(len);
1229
1230           if (dist < kNumFullDistances)
1231             price2 += p->distancesPrices[lenToPosState][dist & (kNumFullDistances - 1)];
1232           else
1233           {
1234             unsigned slot;
1235             GetPosSlot2(dist, slot);
1236             price2 += p->alignPrices[dist & kAlignMask];
1237             price2 += p->posSlotPrices[lenToPosState][slot];
1238           }
1239
1240           opt = &p->opt[len];
1241
1242           if (price2 < opt->price)
1243           {
1244             opt->price = price2;
1245             opt->len = len;
1246             opt->dist = dist + LZMA_NUM_REPS;
1247             opt->extra = 0;
1248           }
1249
1250           if (len == matches[offs])
1251           {
1252             offs += 2;
1253             if (offs == numPairs)
1254               break;
1255           }
1256         }
1257       }
1258     }
1259
1260
1261     cur = 0;
1262
1263     #ifdef SHOW_STAT2
1264     /* if (position >= 0) */
1265     {
1266       unsigned i;
1267       printf("\n pos = %4X", position);
1268       for (i = cur; i <= last; i++)
1269       printf("\nprice[%4X] = %u", position - cur + i, p->opt[i].price);
1270     }
1271     #endif
1272   }
1273
1274
1275
1276   // ---------- Optimal Parsing ----------
1277
1278   for (;;)
1279   {
1280     UInt32 numAvail, numAvailFull;
1281     unsigned newLen, numPairs, prev, state, posState, startLen;
1282     UInt32 curPrice, litPrice, matchPrice, repMatchPrice;
1283     Bool nextIsLit;
1284     Byte curByte, matchByte;
1285     const Byte *data;
1286     COptimal *curOpt, *nextOpt;
1287
1288     if (++cur == last)
1289       return Backward(p, cur);
1290
1291     newLen = ReadMatchDistances(p, &numPairs);
1292
1293     if (newLen >= p->numFastBytes)
1294     {
1295       p->numPairs = numPairs;
1296       p->longestMatchLen = newLen;
1297       return Backward(p, cur);
1298     }
1299
1300     curOpt = &p->opt[cur];
1301     prev = cur - curOpt->len;
1302
1303     if (curOpt->len == 1)
1304     {
1305       state = p->opt[prev].state;
1306       if (IsShortRep(curOpt))
1307         state = kShortRepNextStates[state];
1308       else
1309         state = kLiteralNextStates[state];
1310     }
1311     else
1312     {
1313       const COptimal *prevOpt;
1314       UInt32 b0;
1315       UInt32 dist = curOpt->dist;
1316
1317       if (curOpt->extra)
1318       {
1319         prev -= curOpt->extra;
1320         state = kState_RepAfterLit;
1321         if (curOpt->extra == 1)
1322           state = (dist < LZMA_NUM_REPS) ? kState_RepAfterLit : kState_MatchAfterLit;
1323       }
1324       else
1325       {
1326         state = p->opt[prev].state;
1327         if (dist < LZMA_NUM_REPS)
1328           state = kRepNextStates[state];
1329         else
1330           state = kMatchNextStates[state];
1331       }
1332
1333       prevOpt = &p->opt[prev];
1334       b0 = prevOpt->reps[0];
1335
1336       if (dist < LZMA_NUM_REPS)
1337       {
1338         if (dist == 0)
1339         {
1340           reps[0] = b0;
1341           reps[1] = prevOpt->reps[1];
1342           reps[2] = prevOpt->reps[2];
1343           reps[3] = prevOpt->reps[3];
1344         }
1345         else
1346         {
1347           reps[1] = b0;
1348           b0 = prevOpt->reps[1];
1349           if (dist == 1)
1350           {
1351             reps[0] = b0;
1352             reps[2] = prevOpt->reps[2];
1353             reps[3] = prevOpt->reps[3];
1354           }
1355           else
1356           {
1357             reps[2] = b0;
1358             reps[0] = prevOpt->reps[dist];
1359             reps[3] = prevOpt->reps[dist ^ 1];
1360           }
1361         }
1362       }
1363       else
1364       {
1365         reps[0] = (dist - LZMA_NUM_REPS + 1);
1366         reps[1] = b0;
1367         reps[2] = prevOpt->reps[1];
1368         reps[3] = prevOpt->reps[2];
1369       }
1370     }
1371
1372     curOpt->state = (CState)state;
1373     curOpt->reps[0] = reps[0];
1374     curOpt->reps[1] = reps[1];
1375     curOpt->reps[2] = reps[2];
1376     curOpt->reps[3] = reps[3];
1377
1378     data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1379     curByte = *data;
1380     matchByte = *(data - reps[0]);
1381
1382     position++;
1383     posState = (position & p->pbMask);
1384
1385     /*
1386     The order of Price checks:
1387        <  LIT
1388        <= SHORT_REP
1389        <  LIT : REP_0
1390        <  REP    [ : LIT : REP_0 ]
1391        <  MATCH  [ : LIT : REP_0 ]
1392     */
1393
1394     curPrice = curOpt->price;
1395     litPrice = curPrice + GET_PRICE_0(p->isMatch[state][posState]);
1396
1397     nextOpt = &p->opt[(size_t)cur + 1];
1398     nextIsLit = False;
1399
1400     // if (litPrice >= nextOpt->price) litPrice = 0; else // 18.new
1401     {
1402       const CLzmaProb *probs = LIT_PROBS(position, *(data - 1));
1403       litPrice += (!IsLitState(state) ?
1404           LitEnc_Matched_GetPrice(probs, curByte, matchByte, p->ProbPrices) :
1405           LitEnc_GetPrice(probs, curByte, p->ProbPrices));
1406
1407       if (litPrice < nextOpt->price)
1408       {
1409         nextOpt->price = litPrice;
1410         nextOpt->len = 1;
1411         MakeAs_Lit(nextOpt);
1412         nextIsLit = True;
1413       }
1414     }
1415
1416     matchPrice = curPrice + GET_PRICE_1(p->isMatch[state][posState]);
1417     repMatchPrice = matchPrice + GET_PRICE_1(p->isRep[state]);
1418
1419     // ---------- SHORT_REP ----------
1420     // if (IsLitState(state)) // 18.new
1421     if (matchByte == curByte)
1422     // if (repMatchPrice < nextOpt->price) // 18.new
1423     if (nextOpt->len < 2
1424         || (nextOpt->dist != 0
1425             && nextOpt->extra <= 1 // 17.old
1426         ))
1427     {
1428       UInt32 shortRepPrice = repMatchPrice + GetPrice_ShortRep(p, state, posState);
1429       if (shortRepPrice <= nextOpt->price) // 17.old
1430       // if (shortRepPrice < nextOpt->price)  // 18.new
1431       {
1432         nextOpt->price = shortRepPrice;
1433         nextOpt->len = 1;
1434         MakeAs_ShortRep(nextOpt);
1435         nextIsLit = False;
1436       }
1437     }
1438
1439     numAvailFull = p->numAvail;
1440     {
1441       UInt32 temp = kNumOpts - 1 - cur;
1442       if (numAvailFull > temp)
1443         numAvailFull = temp;
1444     }
1445
1446     if (numAvailFull < 2)
1447       continue;
1448     numAvail = (numAvailFull <= p->numFastBytes ? numAvailFull : p->numFastBytes);
1449
1450     // numAvail <= p->numFastBytes
1451
1452     // ---------- LIT : REP_0 ----------
1453
1454     if (
1455         // litPrice != 0 && // 18.new
1456         !nextIsLit
1457         && matchByte != curByte
1458         && numAvailFull > 2)
1459     {
1460       const Byte *data2 = data - reps[0];
1461       if (data[1] == data2[1] && data[2] == data2[2])
1462       {
1463         unsigned len;
1464         unsigned limit = p->numFastBytes + 1;
1465         if (limit > numAvailFull)
1466           limit = numAvailFull;
1467         for (len = 3; len < limit && data[len] == data2[len]; len++);
1468
1469         {
1470           unsigned state2 = kLiteralNextStates[state];
1471           unsigned posState2 = (position + 1) & p->pbMask;
1472           UInt32 price = litPrice + GetPrice_Rep_0(p, state2, posState2);
1473           {
1474             unsigned offset = cur + len;
1475             while (last < offset)
1476               p->opt[++last].price = kInfinityPrice;
1477
1478             // do
1479             {
1480               UInt32 price2;
1481               COptimal *opt;
1482               len--;
1483               // price2 = price + GetPrice_Len_Rep_0(p, len, state2, posState2);
1484               price2 = price + p->repLenEnc.prices[posState2][len - LZMA_MATCH_LEN_MIN];
1485
1486               opt = &p->opt[offset];
1487               // offset--;
1488               if (price2 < opt->price)
1489               {
1490                 opt->price = price2;
1491                 opt->len = len;
1492                 opt->dist = 0;
1493                 opt->extra = 1;
1494               }
1495             }
1496             // while (len >= 3);
1497           }
1498         }
1499       }
1500     }
1501
1502     startLen = 2; /* speed optimization */
1503     {
1504       // ---------- REP ----------
1505       unsigned repIndex = 0; // 17.old
1506       // unsigned repIndex = IsLitState(state) ? 0 : 1; // 18.notused
1507       for (; repIndex < LZMA_NUM_REPS; repIndex++)
1508       {
1509         unsigned len;
1510         UInt32 price;
1511         const Byte *data2 = data - reps[repIndex];
1512         if (data[0] != data2[0] || data[1] != data2[1])
1513           continue;
1514
1515         for (len = 2; len < numAvail && data[len] == data2[len]; len++);
1516
1517         // if (len < startLen) continue; // 18.new: speed optimization
1518
1519         while (last < cur + len)
1520           p->opt[++last].price = kInfinityPrice;
1521         {
1522           unsigned len2 = len;
1523           price = repMatchPrice + GetPrice_PureRep(p, repIndex, state, posState);
1524           do
1525           {
1526             UInt32 price2 = price + p->repLenEnc.prices[posState][(size_t)len2 - 2];
1527             COptimal *opt = &p->opt[cur + len2];
1528             if (price2 < opt->price)
1529             {
1530               opt->price = price2;
1531               opt->len = len2;
1532               opt->dist = repIndex;
1533               opt->extra = 0;
1534             }
1535           }
1536           while (--len2 >= 2);
1537         }
1538
1539         if (repIndex == 0) startLen = len + 1;  // 17.old
1540         // startLen = len + 1; // 18.new
1541
1542         /* if (_maxMode) */
1543         {
1544           // ---------- REP : LIT : REP_0 ----------
1545           // numFastBytes + 1 + numFastBytes
1546
1547           unsigned len2 = len + 1;
1548           unsigned limit = len2 + p->numFastBytes;
1549           if (limit > numAvailFull)
1550             limit = numAvailFull;
1551
1552           for (; len2 < limit && data[len2] == data2[len2]; len2++);
1553
1554           len2 -= len;
1555           if (len2 >= 3)
1556           {
1557             unsigned state2 = kRepNextStates[state];
1558             unsigned posState2 = (position + len) & p->pbMask;
1559             price +=
1560                   p->repLenEnc.prices[posState][(size_t)len - 2]
1561                 + GET_PRICE_0(p->isMatch[state2][posState2])
1562                 + LitEnc_Matched_GetPrice(LIT_PROBS(position + len, data[(size_t)len - 1]),
1563                     data[len], data2[len], p->ProbPrices);
1564
1565             // state2 = kLiteralNextStates[state2];
1566             state2 = kState_LitAfterRep;
1567             posState2 = (posState2 + 1) & p->pbMask;
1568
1569
1570             price += GetPrice_Rep_0(p, state2, posState2);
1571             {
1572               unsigned offset = cur + len + len2;
1573               while (last < offset)
1574                 p->opt[++last].price = kInfinityPrice;
1575               // do
1576               {
1577                 unsigned price2;
1578                 COptimal *opt;
1579                 len2--;
1580                 // price2 = price + GetPrice_Len_Rep_0(p, len2, state2, posState2);
1581                 price2 = price + p->repLenEnc.prices[posState2][len2 - LZMA_MATCH_LEN_MIN];
1582
1583                 opt = &p->opt[offset];
1584                 // offset--;
1585                 if (price2 < opt->price)
1586                 {
1587                   opt->price = price2;
1588                   opt->len = len2;
1589                   opt->extra = (CExtra)(len + 1);
1590                   opt->dist = repIndex;
1591                 }
1592               }
1593               // while (len2 >= 3);
1594             }
1595           }
1596         }
1597       }
1598     }
1599
1600
1601     // ---------- MATCH ----------
1602     /* for (unsigned len = 2; len <= newLen; len++) */
1603     if (newLen > numAvail)
1604     {
1605       newLen = numAvail;
1606       for (numPairs = 0; newLen > matches[numPairs]; numPairs += 2);
1607       matches[numPairs] = newLen;
1608       numPairs += 2;
1609     }
1610
1611     if (newLen >= startLen)
1612     {
1613       UInt32 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[state]);
1614       UInt32 dist;
1615       unsigned offs, posSlot, len;
1616       while (last < cur + newLen)
1617         p->opt[++last].price = kInfinityPrice;
1618
1619       offs = 0;
1620       while (startLen > matches[offs])
1621         offs += 2;
1622       dist = matches[(size_t)offs + 1];
1623
1624       // if (dist >= kNumFullDistances)
1625       GetPosSlot2(dist, posSlot);
1626
1627       for (len = /*2*/ startLen; ; len++)
1628       {
1629         UInt32 price = normalMatchPrice + p->lenEnc.prices[posState][(size_t)len - LZMA_MATCH_LEN_MIN];
1630         {
1631           COptimal *opt;
1632           unsigned lenToPosState = len - 2; lenToPosState = GetLenToPosState2(lenToPosState);
1633           if (dist < kNumFullDistances)
1634             price += p->distancesPrices[lenToPosState][dist & (kNumFullDistances - 1)];
1635           else
1636             price += p->posSlotPrices[lenToPosState][posSlot] + p->alignPrices[dist & kAlignMask];
1637
1638           opt = &p->opt[cur + len];
1639           if (price < opt->price)
1640           {
1641             opt->price = price;
1642             opt->len = len;
1643             opt->dist = dist + LZMA_NUM_REPS;
1644             opt->extra = 0;
1645           }
1646         }
1647
1648         if (/*_maxMode && */ len == matches[offs])
1649         {
1650           // MATCH : LIT : REP_0
1651
1652           const Byte *data2 = data - dist - 1;
1653           unsigned len2 = len + 1;
1654           unsigned limit = len2 + p->numFastBytes;
1655           if (limit > numAvailFull)
1656             limit = numAvailFull;
1657
1658           for (; len2 < limit && data[len2] == data2[len2]; len2++);
1659
1660           len2 -= len;
1661
1662           if (len2 >= 3)
1663           {
1664             unsigned state2 = kMatchNextStates[state];
1665             unsigned posState2 = (position + len) & p->pbMask;
1666             unsigned offset;
1667             price += GET_PRICE_0(p->isMatch[state2][posState2]);
1668             price += LitEnc_Matched_GetPrice(LIT_PROBS(position + len, data[(size_t)len - 1]),
1669                     data[len], data2[len], p->ProbPrices);
1670
1671             // state2 = kLiteralNextStates[state2];
1672             state2 = kState_LitAfterMatch;
1673
1674             posState2 = (posState2 + 1) & p->pbMask;
1675             price += GetPrice_Rep_0(p, state2, posState2);
1676
1677             offset = cur + len + len2;
1678             while (last < offset)
1679               p->opt[++last].price = kInfinityPrice;
1680             // do
1681             {
1682               UInt32 price2;
1683               COptimal *opt;
1684               len2--;
1685               // price2 = price + GetPrice_Len_Rep_0(p, len2, state2, posState2);
1686               price2 = price + p->repLenEnc.prices[posState2][len2 - LZMA_MATCH_LEN_MIN];
1687               opt = &p->opt[offset];
1688               // offset--;
1689               if (price2 < opt->price)
1690               {
1691                 opt->price = price2;
1692                 opt->len = len2;
1693                 opt->extra = (CExtra)(len + 1);
1694                 opt->dist = dist + LZMA_NUM_REPS;
1695               }
1696             }
1697             // while (len2 >= 3);
1698           }
1699
1700           offs += 2;
1701           if (offs == numPairs)
1702             break;
1703           dist = matches[(size_t)offs + 1];
1704           // if (dist >= kNumFullDistances)
1705             GetPosSlot2(dist, posSlot);
1706         }
1707       }
1708     }
1709   }
1710 }
1711
1712
1713
1714 #define ChangePair(smallDist, bigDist) (((bigDist) >> 7) > (smallDist))
1715
1716
1717
1718 static unsigned GetOptimumFast(CLzmaEnc *p)
1719 {
1720   UInt32 numAvail, mainDist;
1721   unsigned mainLen, numPairs, repIndex, repLen, i;
1722   const Byte *data;
1723
1724   if (p->additionalOffset == 0)
1725     mainLen = ReadMatchDistances(p, &numPairs);
1726   else
1727   {
1728     mainLen = p->longestMatchLen;
1729     numPairs = p->numPairs;
1730   }
1731
1732   numAvail = p->numAvail;
1733   p->backRes = MARK_LIT;
1734   if (numAvail < 2)
1735     return 1;
1736   if (numAvail > LZMA_MATCH_LEN_MAX)
1737     numAvail = LZMA_MATCH_LEN_MAX;
1738   data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1739   repLen = repIndex = 0;
1740
1741   for (i = 0; i < LZMA_NUM_REPS; i++)
1742   {
1743     unsigned len;
1744     const Byte *data2 = data - p->reps[i];
1745     if (data[0] != data2[0] || data[1] != data2[1])
1746       continue;
1747     for (len = 2; len < numAvail && data[len] == data2[len]; len++);
1748     if (len >= p->numFastBytes)
1749     {
1750       p->backRes = i;
1751       MOVE_POS(p, len - 1)
1752       return len;
1753     }
1754     if (len > repLen)
1755     {
1756       repIndex = i;
1757       repLen = len;
1758     }
1759   }
1760
1761   if (mainLen >= p->numFastBytes)
1762   {
1763     p->backRes = p->matches[(size_t)numPairs - 1] + LZMA_NUM_REPS;
1764     MOVE_POS(p, mainLen - 1)
1765     return mainLen;
1766   }
1767
1768   mainDist = 0; /* for GCC */
1769
1770   if (mainLen >= 2)
1771   {
1772     mainDist = p->matches[(size_t)numPairs - 1];
1773     while (numPairs > 2)
1774     {
1775       UInt32 dist2;
1776       if (mainLen != p->matches[(size_t)numPairs - 4] + 1)
1777         break;
1778       dist2 = p->matches[(size_t)numPairs - 3];
1779       if (!ChangePair(dist2, mainDist))
1780         break;
1781       numPairs -= 2;
1782       mainLen--;
1783       mainDist = dist2;
1784     }
1785     if (mainLen == 2 && mainDist >= 0x80)
1786       mainLen = 1;
1787   }
1788
1789   if (repLen >= 2)
1790     if (    repLen + 1 >= mainLen
1791         || (repLen + 2 >= mainLen && mainDist >= (1 << 9))
1792         || (repLen + 3 >= mainLen && mainDist >= (1 << 15)))
1793   {
1794     p->backRes = repIndex;
1795     MOVE_POS(p, repLen - 1)
1796     return repLen;
1797   }
1798
1799   if (mainLen < 2 || numAvail <= 2)
1800     return 1;
1801
1802   {
1803     unsigned len1 = ReadMatchDistances(p, &p->numPairs);
1804     p->longestMatchLen = len1;
1805
1806     if (len1 >= 2)
1807     {
1808       UInt32 newDist = p->matches[(size_t)p->numPairs - 1];
1809       if (   (len1 >= mainLen && newDist < mainDist)
1810           || (len1 == mainLen + 1 && !ChangePair(mainDist, newDist))
1811           || (len1 >  mainLen + 1)
1812           || (len1 + 1 >= mainLen && mainLen >= 3 && ChangePair(newDist, mainDist)))
1813         return 1;
1814     }
1815   }
1816
1817   data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1818
1819   for (i = 0; i < LZMA_NUM_REPS; i++)
1820   {
1821     unsigned len, limit;
1822     const Byte *data2 = data - p->reps[i];
1823     if (data[0] != data2[0] || data[1] != data2[1])
1824       continue;
1825     limit = mainLen - 1;
1826     for (len = 2;; len++)
1827     {
1828       if (len >= limit)
1829         return 1;
1830       if (data[len] != data2[len])
1831         break;
1832     }
1833   }
1834
1835   p->backRes = mainDist + LZMA_NUM_REPS;
1836   if (mainLen != 2)
1837   {
1838     MOVE_POS(p, mainLen - 2)
1839   }
1840   return mainLen;
1841 }
1842
1843
1844
1845
1846 static void WriteEndMarker(CLzmaEnc *p, unsigned posState)
1847 {
1848   UInt32 range;
1849   range = p->rc.range;
1850   {
1851     UInt32 ttt, newBound;
1852     CLzmaProb *prob = &p->isMatch[p->state][posState];
1853     RC_BIT_PRE(&p->rc, prob)
1854     RC_BIT_1(&p->rc, prob)
1855     prob = &p->isRep[p->state];
1856     RC_BIT_PRE(&p->rc, prob)
1857     RC_BIT_0(&p->rc, prob)
1858   }
1859   p->state = kMatchNextStates[p->state];
1860
1861   p->rc.range = range;
1862   LenEnc_Encode(&p->lenProbs, &p->rc, 0, posState);
1863   range = p->rc.range;
1864
1865   {
1866     // RcTree_Encode_PosSlot(&p->rc, p->posSlotEncoder[0], (1 << kNumPosSlotBits) - 1);
1867     CLzmaProb *probs = p->posSlotEncoder[0];
1868     unsigned m = 1;
1869     do
1870     {
1871       UInt32 ttt, newBound;
1872       RC_BIT_PRE(p, probs + m)
1873       RC_BIT_1(&p->rc, probs + m);
1874       m = (m << 1) + 1;
1875     }
1876     while (m < (1 << kNumPosSlotBits));
1877   }
1878   {
1879     // RangeEnc_EncodeDirectBits(&p->rc, ((UInt32)1 << (30 - kNumAlignBits)) - 1, 30 - kNumAlignBits);    UInt32 range = p->range;
1880     unsigned numBits = 30 - kNumAlignBits;
1881     do
1882     {
1883       range >>= 1;
1884       p->rc.low += range;
1885       RC_NORM(&p->rc)
1886     }
1887     while (--numBits);
1888   }
1889
1890   {
1891     // RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, kAlignMask);
1892     CLzmaProb *probs = p->posAlignEncoder;
1893     unsigned m = 1;
1894     do
1895     {
1896       UInt32 ttt, newBound;
1897       RC_BIT_PRE(p, probs + m)
1898       RC_BIT_1(&p->rc, probs + m);
1899       m = (m << 1) + 1;
1900     }
1901     while (m < kAlignTableSize);
1902   }
1903   p->rc.range = range;
1904 }
1905
1906
1907 static SRes CheckErrors(CLzmaEnc *p)
1908 {
1909   if (p->result != SZ_OK)
1910     return p->result;
1911   if (p->rc.res != SZ_OK)
1912     p->result = SZ_ERROR_WRITE;
1913   if (p->matchFinderBase.result != SZ_OK)
1914     p->result = SZ_ERROR_READ;
1915   if (p->result != SZ_OK)
1916     p->finished = True;
1917   return p->result;
1918 }
1919
1920
1921 MY_NO_INLINE static SRes Flush(CLzmaEnc *p, UInt32 nowPos)
1922 {
1923   /* ReleaseMFStream(); */
1924   p->finished = True;
1925   if (p->writeEndMark)
1926     WriteEndMarker(p, nowPos & p->pbMask);
1927   RangeEnc_FlushData(&p->rc);
1928   RangeEnc_FlushStream(&p->rc);
1929   return CheckErrors(p);
1930 }
1931
1932
1933
1934 static void FillAlignPrices(CLzmaEnc *p)
1935 {
1936   unsigned i;
1937   const CProbPrice *ProbPrices = p->ProbPrices;
1938   const CLzmaProb *probs = p->posAlignEncoder;
1939   p->alignPriceCount = 0;
1940   for (i = 0; i < kAlignTableSize / 2; i++)
1941   {
1942     UInt32 price = 0;
1943     unsigned symbol = i;
1944     unsigned m = 1;
1945     unsigned bit;
1946     UInt32 prob;
1947     bit = symbol & 1; symbol >>= 1; price += GET_PRICEa(probs[m], bit); m = (m << 1) + bit;
1948     bit = symbol & 1; symbol >>= 1; price += GET_PRICEa(probs[m], bit); m = (m << 1) + bit;
1949     bit = symbol & 1; symbol >>= 1; price += GET_PRICEa(probs[m], bit); m = (m << 1) + bit;
1950     prob = probs[m];
1951     p->alignPrices[i    ] = price + GET_PRICEa_0(prob);
1952     p->alignPrices[i + 8] = price + GET_PRICEa_1(prob);
1953     // p->alignPrices[i] = RcTree_ReverseGetPrice(p->posAlignEncoder, kNumAlignBits, i, p->ProbPrices);
1954   }
1955 }
1956
1957
1958 static void FillDistancesPrices(CLzmaEnc *p)
1959 {
1960   UInt32 tempPrices[kNumFullDistances];
1961   unsigned i, lenToPosState;
1962
1963   const CProbPrice *ProbPrices = p->ProbPrices;
1964   p->matchPriceCount = 0;
1965
1966   for (i = kStartPosModelIndex; i < kNumFullDistances; i++)
1967   {
1968     unsigned posSlot = GetPosSlot1(i);
1969     unsigned footerBits = ((posSlot >> 1) - 1);
1970     unsigned base = ((2 | (posSlot & 1)) << footerBits);
1971     // tempPrices[i] = RcTree_ReverseGetPrice(p->posEncoders + base, footerBits, i - base, p->ProbPrices);
1972
1973     const CLzmaProb *probs = p->posEncoders + base;
1974     UInt32 price = 0;
1975     unsigned m = 1;
1976     unsigned symbol = i - base;
1977     do
1978     {
1979       unsigned bit = symbol & 1;
1980       symbol >>= 1;
1981       price += GET_PRICEa(probs[m], bit);
1982       m = (m << 1) + bit;
1983     }
1984     while (--footerBits);
1985     tempPrices[i] = price;
1986   }
1987
1988   for (lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++)
1989   {
1990     unsigned posSlot;
1991     const CLzmaProb *encoder = p->posSlotEncoder[lenToPosState];
1992     UInt32 *posSlotPrices = p->posSlotPrices[lenToPosState];
1993     unsigned distTableSize = p->distTableSize;
1994     const CLzmaProb *probs = encoder;
1995     for (posSlot = 0; posSlot < distTableSize; posSlot += 2)
1996     {
1997       // posSlotPrices[posSlot] = RcTree_GetPrice(encoder, kNumPosSlotBits, posSlot, p->ProbPrices);
1998       UInt32 price = 0;
1999       unsigned bit;
2000       unsigned symbol = (posSlot >> 1) + (1 << (kNumPosSlotBits - 1));
2001       UInt32 prob;
2002       bit = symbol & 1; symbol >>= 1; price += GET_PRICEa(probs[symbol], bit);
2003       bit = symbol & 1; symbol >>= 1; price += GET_PRICEa(probs[symbol], bit);
2004       bit = symbol & 1; symbol >>= 1; price += GET_PRICEa(probs[symbol], bit);
2005       bit = symbol & 1; symbol >>= 1; price += GET_PRICEa(probs[symbol], bit);
2006       bit = symbol & 1; symbol >>= 1; price += GET_PRICEa(probs[symbol], bit);
2007       prob = probs[(posSlot >> 1) + (1 << (kNumPosSlotBits - 1))];
2008       posSlotPrices[posSlot    ] = price + GET_PRICEa_0(prob);
2009       posSlotPrices[posSlot + 1] = price + GET_PRICEa_1(prob);
2010     }
2011     for (posSlot = kEndPosModelIndex; posSlot < distTableSize; posSlot++)
2012       posSlotPrices[posSlot] += ((UInt32)(((posSlot >> 1) - 1) - kNumAlignBits) << kNumBitPriceShiftBits);
2013
2014     {
2015       UInt32 *distancesPrices = p->distancesPrices[lenToPosState];
2016       {
2017         distancesPrices[0] = posSlotPrices[0];
2018         distancesPrices[1] = posSlotPrices[1];
2019         distancesPrices[2] = posSlotPrices[2];
2020         distancesPrices[3] = posSlotPrices[3];
2021       }
2022       for (i = 4; i < kNumFullDistances; i += 2)
2023       {
2024         UInt32 slotPrice = posSlotPrices[GetPosSlot1(i)];
2025         distancesPrices[i    ] = slotPrice + tempPrices[i];
2026         distancesPrices[i + 1] = slotPrice + tempPrices[i + 1];
2027       }
2028     }
2029   }
2030 }
2031
2032
2033
2034 void LzmaEnc_Construct(CLzmaEnc *p)
2035 {
2036   RangeEnc_Construct(&p->rc);
2037   MatchFinder_Construct(&p->matchFinderBase);
2038
2039   #ifndef _7ZIP_ST
2040   MatchFinderMt_Construct(&p->matchFinderMt);
2041   p->matchFinderMt.MatchFinder = &p->matchFinderBase;
2042   #endif
2043
2044   {
2045     CLzmaEncProps props;
2046     LzmaEncProps_Init(&props);
2047     LzmaEnc_SetProps(p, &props);
2048   }
2049
2050   #ifndef LZMA_LOG_BSR
2051   LzmaEnc_FastPosInit(p->g_FastPos);
2052   #endif
2053
2054   LzmaEnc_InitPriceTables(p->ProbPrices);
2055   p->litProbs = NULL;
2056   p->saveState.litProbs = NULL;
2057
2058 }
2059
2060 CLzmaEncHandle LzmaEnc_Create(ISzAllocPtr alloc)
2061 {
2062   void *p;
2063   p = ISzAlloc_Alloc(alloc, sizeof(CLzmaEnc));
2064   if (p)
2065     LzmaEnc_Construct((CLzmaEnc *)p);
2066   return p;
2067 }
2068
2069 void LzmaEnc_FreeLits(CLzmaEnc *p, ISzAllocPtr alloc)
2070 {
2071   ISzAlloc_Free(alloc, p->litProbs);
2072   ISzAlloc_Free(alloc, p->saveState.litProbs);
2073   p->litProbs = NULL;
2074   p->saveState.litProbs = NULL;
2075 }
2076
2077 void LzmaEnc_Destruct(CLzmaEnc *p, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2078 {
2079   #ifndef _7ZIP_ST
2080   MatchFinderMt_Destruct(&p->matchFinderMt, allocBig);
2081   #endif
2082
2083   MatchFinder_Free(&p->matchFinderBase, allocBig);
2084   LzmaEnc_FreeLits(p, alloc);
2085   RangeEnc_Free(&p->rc, alloc);
2086 }
2087
2088 void LzmaEnc_Destroy(CLzmaEncHandle p, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2089 {
2090   LzmaEnc_Destruct((CLzmaEnc *)p, alloc, allocBig);
2091   ISzAlloc_Free(alloc, p);
2092 }
2093
2094
2095 static SRes LzmaEnc_CodeOneBlock(CLzmaEnc *p, UInt32 maxPackSize, UInt32 maxUnpackSize)
2096 {
2097   UInt32 nowPos32, startPos32;
2098   if (p->needInit)
2099   {
2100     p->matchFinder.Init(p->matchFinderObj);
2101     p->needInit = 0;
2102   }
2103
2104   if (p->finished)
2105     return p->result;
2106   RINOK(CheckErrors(p));
2107
2108   nowPos32 = (UInt32)p->nowPos64;
2109   startPos32 = nowPos32;
2110
2111   if (p->nowPos64 == 0)
2112   {
2113     unsigned numPairs;
2114     Byte curByte;
2115     if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)
2116       return Flush(p, nowPos32);
2117     ReadMatchDistances(p, &numPairs);
2118     RangeEnc_EncodeBit_0(&p->rc, &p->isMatch[kState_Start][0]);
2119     // p->state = kLiteralNextStates[p->state];
2120     curByte = *(p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset);
2121     LitEnc_Encode(&p->rc, p->litProbs, curByte);
2122     p->additionalOffset--;
2123     nowPos32++;
2124   }
2125
2126   if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) != 0)
2127
2128   for (;;)
2129   {
2130     UInt32 dist;
2131     unsigned len, posState;
2132     UInt32 range, ttt, newBound;
2133     CLzmaProb *probs;
2134
2135     if (p->fastMode)
2136       len = GetOptimumFast(p);
2137     else
2138     {
2139       unsigned oci = p->optCur;
2140       if (p->optEnd == oci)
2141         len = GetOptimum(p, nowPos32);
2142       else
2143       {
2144         const COptimal *opt = &p->opt[oci];
2145         len = opt->len;
2146         p->backRes = opt->dist;
2147         p->optCur = oci + 1;
2148       }
2149     }
2150
2151     posState = (unsigned)nowPos32 & p->pbMask;
2152     range = p->rc.range;
2153     probs = &p->isMatch[p->state][posState];
2154
2155     RC_BIT_PRE(&p->rc, probs)
2156
2157     dist = p->backRes;
2158
2159     #ifdef SHOW_STAT2
2160     printf("\n pos = %6X, len = %3u  pos = %6u", nowPos32, len, dist);
2161     #endif
2162
2163     if (dist == MARK_LIT)
2164     {
2165       Byte curByte;
2166       const Byte *data;
2167       unsigned state;
2168
2169       RC_BIT_0(&p->rc, probs);
2170       p->rc.range = range;
2171       data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
2172       probs = LIT_PROBS(nowPos32, *(data - 1));
2173       curByte = *data;
2174       state = p->state;
2175       p->state = kLiteralNextStates[state];
2176       if (IsLitState(state))
2177         LitEnc_Encode(&p->rc, probs, curByte);
2178       else
2179         LitEnc_EncodeMatched(&p->rc, probs, curByte, *(data - p->reps[0]));
2180     }
2181     else
2182     {
2183       RC_BIT_1(&p->rc, probs);
2184       probs = &p->isRep[p->state];
2185       RC_BIT_PRE(&p->rc, probs)
2186
2187       if (dist < LZMA_NUM_REPS)
2188       {
2189         RC_BIT_1(&p->rc, probs);
2190         probs = &p->isRepG0[p->state];
2191         RC_BIT_PRE(&p->rc, probs)
2192         if (dist == 0)
2193         {
2194           RC_BIT_0(&p->rc, probs);
2195           probs = &p->isRep0Long[p->state][posState];
2196           RC_BIT_PRE(&p->rc, probs)
2197           if (len != 1)
2198           {
2199             RC_BIT_1_BASE(&p->rc, probs);
2200           }
2201           else
2202           {
2203             RC_BIT_0_BASE(&p->rc, probs);
2204             p->state = kShortRepNextStates[p->state];
2205           }
2206         }
2207         else
2208         {
2209           RC_BIT_1(&p->rc, probs);
2210           probs = &p->isRepG1[p->state];
2211           RC_BIT_PRE(&p->rc, probs)
2212           if (dist == 1)
2213           {
2214             RC_BIT_0_BASE(&p->rc, probs);
2215             dist = p->reps[1];
2216           }
2217           else
2218           {
2219             RC_BIT_1(&p->rc, probs);
2220             probs = &p->isRepG2[p->state];
2221             RC_BIT_PRE(&p->rc, probs)
2222             if (dist == 2)
2223             {
2224               RC_BIT_0_BASE(&p->rc, probs);
2225               dist = p->reps[2];
2226             }
2227             else
2228             {
2229               RC_BIT_1_BASE(&p->rc, probs);
2230               dist = p->reps[3];
2231               p->reps[3] = p->reps[2];
2232             }
2233             p->reps[2] = p->reps[1];
2234           }
2235           p->reps[1] = p->reps[0];
2236           p->reps[0] = dist;
2237         }
2238
2239         RC_NORM(&p->rc)
2240
2241         p->rc.range = range;
2242
2243         if (len != 1)
2244         {
2245           LenEnc_Encode(&p->repLenProbs, &p->rc, len - LZMA_MATCH_LEN_MIN, posState);
2246           if (!p->fastMode)
2247             if (--p->repLenEnc.counters[posState] == 0)
2248               LenPriceEnc_UpdateTable(&p->repLenEnc, posState, &p->repLenProbs, p->ProbPrices);
2249
2250           p->state = kRepNextStates[p->state];
2251         }
2252       }
2253       else
2254       {
2255         unsigned posSlot;
2256         RC_BIT_0(&p->rc, probs);
2257         p->rc.range = range;
2258         p->state = kMatchNextStates[p->state];
2259
2260         LenEnc_Encode(&p->lenProbs, &p->rc, len - LZMA_MATCH_LEN_MIN, posState);
2261         if (!p->fastMode)
2262           if (--p->lenEnc.counters[posState] == 0)
2263             LenPriceEnc_UpdateTable(&p->lenEnc, posState, &p->lenProbs, p->ProbPrices);
2264
2265         dist -= LZMA_NUM_REPS;
2266         p->reps[3] = p->reps[2];
2267         p->reps[2] = p->reps[1];
2268         p->reps[1] = p->reps[0];
2269         p->reps[0] = dist + 1;
2270
2271         p->matchPriceCount++;
2272         GetPosSlot(dist, posSlot);
2273         // RcTree_Encode_PosSlot(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], posSlot);
2274         {
2275           UInt32 symbol = posSlot + (1 << kNumPosSlotBits);
2276           range = p->rc.range;
2277           probs = p->posSlotEncoder[GetLenToPosState(len)];
2278           do
2279           {
2280             CLzmaProb *prob = probs + (symbol >> kNumPosSlotBits);
2281             UInt32 bit = (symbol >> (kNumPosSlotBits - 1)) & 1;
2282             symbol <<= 1;
2283             RC_BIT(&p->rc, prob, bit);
2284           }
2285           while (symbol < (1 << kNumPosSlotBits * 2));
2286           p->rc.range = range;
2287         }
2288
2289         if (dist >= kStartPosModelIndex)
2290         {
2291           unsigned footerBits = ((posSlot >> 1) - 1);
2292
2293           if (dist < kNumFullDistances)
2294           {
2295             unsigned base = ((2 | (posSlot & 1)) << footerBits);
2296             RcTree_ReverseEncode(&p->rc, p->posEncoders + base, footerBits, dist - base);
2297           }
2298           else
2299           {
2300             UInt32 pos2 = (dist | 0xF) << (32 - footerBits);
2301             range = p->rc.range;
2302             // RangeEnc_EncodeDirectBits(&p->rc, posReduced >> kNumAlignBits, footerBits - kNumAlignBits);
2303             /*
2304             do
2305             {
2306               range >>= 1;
2307               p->rc.low += range & (0 - ((dist >> --footerBits) & 1));
2308               RC_NORM(&p->rc)
2309             }
2310             while (footerBits > kNumAlignBits);
2311             */
2312             do
2313             {
2314               range >>= 1;
2315               p->rc.low += range & (0 - (pos2 >> 31));
2316               pos2 += pos2;
2317               RC_NORM(&p->rc)
2318             }
2319             while (pos2 != 0xF0000000);
2320
2321
2322             // RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, posReduced & kAlignMask);
2323
2324             {
2325               unsigned m = 1;
2326               unsigned bit;
2327               bit = dist & 1; dist >>= 1; RC_BIT(&p->rc, p->posAlignEncoder + m, bit); m = (m << 1) + bit;
2328               bit = dist & 1; dist >>= 1; RC_BIT(&p->rc, p->posAlignEncoder + m, bit); m = (m << 1) + bit;
2329               bit = dist & 1; dist >>= 1; RC_BIT(&p->rc, p->posAlignEncoder + m, bit); m = (m << 1) + bit;
2330               bit = dist & 1;             RC_BIT(&p->rc, p->posAlignEncoder + m, bit);
2331               p->rc.range = range;
2332               p->alignPriceCount++;
2333             }
2334           }
2335         }
2336       }
2337     }
2338
2339     nowPos32 += len;
2340     p->additionalOffset -= len;
2341
2342     if (p->additionalOffset == 0)
2343     {
2344       UInt32 processed;
2345
2346       if (!p->fastMode)
2347       {
2348         if (p->matchPriceCount >= (1 << 7))
2349           FillDistancesPrices(p);
2350         if (p->alignPriceCount >= kAlignTableSize)
2351           FillAlignPrices(p);
2352       }
2353
2354       if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)
2355         break;
2356       processed = nowPos32 - startPos32;
2357
2358       if (maxPackSize)
2359       {
2360         if (processed + kNumOpts + 300 >= maxUnpackSize
2361             || RangeEnc_GetProcessed_sizet(&p->rc) + kPackReserve >= maxPackSize)
2362           break;
2363       }
2364       else if (processed >= (1 << 17))
2365       {
2366         p->nowPos64 += nowPos32 - startPos32;
2367         return CheckErrors(p);
2368       }
2369     }
2370   }
2371
2372   p->nowPos64 += nowPos32 - startPos32;
2373   return Flush(p, nowPos32);
2374 }
2375
2376
2377
2378 #define kBigHashDicLimit ((UInt32)1 << 24)
2379
2380 static SRes LzmaEnc_Alloc(CLzmaEnc *p, UInt32 keepWindowSize, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2381 {
2382   UInt32 beforeSize = kNumOpts;
2383   if (!RangeEnc_Alloc(&p->rc, alloc))
2384     return SZ_ERROR_MEM;
2385
2386   #ifndef _7ZIP_ST
2387   p->mtMode = (p->multiThread && !p->fastMode && (p->matchFinderBase.btMode != 0));
2388   #endif
2389
2390   {
2391     unsigned lclp = p->lc + p->lp;
2392     if (!p->litProbs || !p->saveState.litProbs || p->lclp != lclp)
2393     {
2394       LzmaEnc_FreeLits(p, alloc);
2395       p->litProbs = (CLzmaProb *)ISzAlloc_Alloc(alloc, ((UInt32)0x300 << lclp) * sizeof(CLzmaProb));
2396       p->saveState.litProbs = (CLzmaProb *)ISzAlloc_Alloc(alloc, ((UInt32)0x300 << lclp) * sizeof(CLzmaProb));
2397       if (!p->litProbs || !p->saveState.litProbs)
2398       {
2399         LzmaEnc_FreeLits(p, alloc);
2400         return SZ_ERROR_MEM;
2401       }
2402       p->lclp = lclp;
2403     }
2404   }
2405
2406   p->matchFinderBase.bigHash = (Byte)(p->dictSize > kBigHashDicLimit ? 1 : 0);
2407
2408   if (beforeSize + p->dictSize < keepWindowSize)
2409     beforeSize = keepWindowSize - p->dictSize;
2410
2411   #ifndef _7ZIP_ST
2412   if (p->mtMode)
2413   {
2414     RINOK(MatchFinderMt_Create(&p->matchFinderMt, p->dictSize, beforeSize, p->numFastBytes,
2415         LZMA_MATCH_LEN_MAX
2416         + 1  /* 18.04 */
2417         , allocBig));
2418     p->matchFinderObj = &p->matchFinderMt;
2419     p->matchFinderBase.bigHash = (Byte)(
2420         (p->dictSize > kBigHashDicLimit && p->matchFinderBase.hashMask >= 0xFFFFFF) ? 1 : 0);
2421     MatchFinderMt_CreateVTable(&p->matchFinderMt, &p->matchFinder);
2422   }
2423   else
2424   #endif
2425   {
2426     if (!MatchFinder_Create(&p->matchFinderBase, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig))
2427       return SZ_ERROR_MEM;
2428     p->matchFinderObj = &p->matchFinderBase;
2429     MatchFinder_CreateVTable(&p->matchFinderBase, &p->matchFinder);
2430   }
2431
2432   return SZ_OK;
2433 }
2434
2435 void LzmaEnc_Init(CLzmaEnc *p)
2436 {
2437   unsigned i;
2438   p->state = 0;
2439   p->reps[0] =
2440   p->reps[1] =
2441   p->reps[2] =
2442   p->reps[3] = 1;
2443
2444   RangeEnc_Init(&p->rc);
2445
2446   for (i = 0; i < (1 << kNumAlignBits); i++)
2447     p->posAlignEncoder[i] = kProbInitValue;
2448
2449   for (i = 0; i < kNumStates; i++)
2450   {
2451     unsigned j;
2452     for (j = 0; j < LZMA_NUM_PB_STATES_MAX; j++)
2453     {
2454       p->isMatch[i][j] = kProbInitValue;
2455       p->isRep0Long[i][j] = kProbInitValue;
2456     }
2457     p->isRep[i] = kProbInitValue;
2458     p->isRepG0[i] = kProbInitValue;
2459     p->isRepG1[i] = kProbInitValue;
2460     p->isRepG2[i] = kProbInitValue;
2461   }
2462
2463   {
2464     for (i = 0; i < kNumLenToPosStates; i++)
2465     {
2466       CLzmaProb *probs = p->posSlotEncoder[i];
2467       unsigned j;
2468       for (j = 0; j < (1 << kNumPosSlotBits); j++)
2469         probs[j] = kProbInitValue;
2470     }
2471   }
2472   {
2473     for (i = 0; i < kNumFullDistances; i++)
2474       p->posEncoders[i] = kProbInitValue;
2475   }
2476
2477   {
2478     UInt32 num = (UInt32)0x300 << (p->lp + p->lc);
2479     UInt32 k;
2480     CLzmaProb *probs = p->litProbs;
2481     for (k = 0; k < num; k++)
2482       probs[k] = kProbInitValue;
2483   }
2484
2485
2486   LenEnc_Init(&p->lenProbs);
2487   LenEnc_Init(&p->repLenProbs);
2488
2489   p->optEnd = 0;
2490   p->optCur = 0;
2491   p->additionalOffset = 0;
2492
2493   p->pbMask = (1 << p->pb) - 1;
2494   p->lpMask = ((UInt32)0x100 << p->lp) - ((unsigned)0x100 >> p->lc);
2495 }
2496
2497 void LzmaEnc_InitPrices(CLzmaEnc *p)
2498 {
2499   if (!p->fastMode)
2500   {
2501     FillDistancesPrices(p);
2502     FillAlignPrices(p);
2503   }
2504
2505   p->lenEnc.tableSize =
2506   p->repLenEnc.tableSize =
2507       p->numFastBytes + 1 - LZMA_MATCH_LEN_MIN;
2508   LenPriceEnc_UpdateTables(&p->lenEnc, 1 << p->pb, &p->lenProbs, p->ProbPrices);
2509   LenPriceEnc_UpdateTables(&p->repLenEnc, 1 << p->pb, &p->repLenProbs, p->ProbPrices);
2510 }
2511
2512 static SRes LzmaEnc_AllocAndInit(CLzmaEnc *p, UInt32 keepWindowSize, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2513 {
2514   unsigned i;
2515   for (i = kEndPosModelIndex / 2; i < kDicLogSizeMax; i++)
2516     if (p->dictSize <= ((UInt32)1 << i))
2517       break;
2518   p->distTableSize = i * 2;
2519
2520   p->finished = False;
2521   p->result = SZ_OK;
2522   RINOK(LzmaEnc_Alloc(p, keepWindowSize, alloc, allocBig));
2523   LzmaEnc_Init(p);
2524   LzmaEnc_InitPrices(p);
2525   p->nowPos64 = 0;
2526   return SZ_OK;
2527 }
2528
2529 static SRes LzmaEnc_Prepare(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream,
2530     ISzAllocPtr alloc, ISzAllocPtr allocBig)
2531 {
2532   CLzmaEnc *p = (CLzmaEnc *)pp;
2533   p->matchFinderBase.stream = inStream;
2534   p->needInit = 1;
2535   p->rc.outStream = outStream;
2536   return LzmaEnc_AllocAndInit(p, 0, alloc, allocBig);
2537 }
2538
2539 SRes LzmaEnc_PrepareForLzma2(CLzmaEncHandle pp,
2540     ISeqInStream *inStream, UInt32 keepWindowSize,
2541     ISzAllocPtr alloc, ISzAllocPtr allocBig)
2542 {
2543   CLzmaEnc *p = (CLzmaEnc *)pp;
2544   p->matchFinderBase.stream = inStream;
2545   p->needInit = 1;
2546   return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);
2547 }
2548
2549 static void LzmaEnc_SetInputBuf(CLzmaEnc *p, const Byte *src, SizeT srcLen)
2550 {
2551   p->matchFinderBase.directInput = 1;
2552   p->matchFinderBase.bufferBase = (Byte *)src;
2553   p->matchFinderBase.directInputRem = srcLen;
2554 }
2555
2556 SRes LzmaEnc_MemPrepare(CLzmaEncHandle pp, const Byte *src, SizeT srcLen,
2557     UInt32 keepWindowSize, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2558 {
2559   CLzmaEnc *p = (CLzmaEnc *)pp;
2560   LzmaEnc_SetInputBuf(p, src, srcLen);
2561   p->needInit = 1;
2562
2563   LzmaEnc_SetDataSize(pp, srcLen);
2564   return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);
2565 }
2566
2567 void LzmaEnc_Finish(CLzmaEncHandle pp)
2568 {
2569   #ifndef _7ZIP_ST
2570   CLzmaEnc *p = (CLzmaEnc *)pp;
2571   if (p->mtMode)
2572     MatchFinderMt_ReleaseStream(&p->matchFinderMt);
2573   #else
2574   UNUSED_VAR(pp);
2575   #endif
2576 }
2577
2578
2579 typedef struct
2580 {
2581   ISeqOutStream vt;
2582   Byte *data;
2583   SizeT rem;
2584   Bool overflow;
2585 } CLzmaEnc_SeqOutStreamBuf;
2586
2587 static size_t SeqOutStreamBuf_Write(const ISeqOutStream *pp, const void *data, size_t size)
2588 {
2589   CLzmaEnc_SeqOutStreamBuf *p = CONTAINER_FROM_VTBL(pp, CLzmaEnc_SeqOutStreamBuf, vt);
2590   if (p->rem < size)
2591   {
2592     size = p->rem;
2593     p->overflow = True;
2594   }
2595   memcpy(p->data, data, size);
2596   p->rem -= size;
2597   p->data += size;
2598   return size;
2599 }
2600
2601
2602 UInt32 LzmaEnc_GetNumAvailableBytes(CLzmaEncHandle pp)
2603 {
2604   const CLzmaEnc *p = (CLzmaEnc *)pp;
2605   return p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);
2606 }
2607
2608
2609 const Byte *LzmaEnc_GetCurBuf(CLzmaEncHandle pp)
2610 {
2611   const CLzmaEnc *p = (CLzmaEnc *)pp;
2612   return p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
2613 }
2614
2615
2616 SRes LzmaEnc_CodeOneMemBlock(CLzmaEncHandle pp, Bool reInit,
2617     Byte *dest, size_t *destLen, UInt32 desiredPackSize, UInt32 *unpackSize)
2618 {
2619   CLzmaEnc *p = (CLzmaEnc *)pp;
2620   UInt64 nowPos64;
2621   SRes res;
2622   CLzmaEnc_SeqOutStreamBuf outStream;
2623
2624   outStream.vt.Write = SeqOutStreamBuf_Write;
2625   outStream.data = dest;
2626   outStream.rem = *destLen;
2627   outStream.overflow = False;
2628
2629   p->writeEndMark = False;
2630   p->finished = False;
2631   p->result = SZ_OK;
2632
2633   if (reInit)
2634     LzmaEnc_Init(p);
2635   LzmaEnc_InitPrices(p);
2636
2637   nowPos64 = p->nowPos64;
2638   RangeEnc_Init(&p->rc);
2639   p->rc.outStream = &outStream.vt;
2640
2641   if (desiredPackSize == 0)
2642     return SZ_ERROR_OUTPUT_EOF;
2643
2644   res = LzmaEnc_CodeOneBlock(p, desiredPackSize, *unpackSize);
2645
2646   *unpackSize = (UInt32)(p->nowPos64 - nowPos64);
2647   *destLen -= outStream.rem;
2648   if (outStream.overflow)
2649     return SZ_ERROR_OUTPUT_EOF;
2650
2651   return res;
2652 }
2653
2654
2655 static SRes LzmaEnc_Encode2(CLzmaEnc *p, ICompressProgress *progress)
2656 {
2657   SRes res = SZ_OK;
2658
2659   #ifndef _7ZIP_ST
2660   Byte allocaDummy[0x300];
2661   allocaDummy[0] = 0;
2662   allocaDummy[1] = allocaDummy[0];
2663   #endif
2664
2665   for (;;)
2666   {
2667     res = LzmaEnc_CodeOneBlock(p, 0, 0);
2668     if (res != SZ_OK || p->finished)
2669       break;
2670     if (progress)
2671     {
2672       res = ICompressProgress_Progress(progress, p->nowPos64, RangeEnc_GetProcessed(&p->rc));
2673       if (res != SZ_OK)
2674       {
2675         res = SZ_ERROR_PROGRESS;
2676         break;
2677       }
2678     }
2679   }
2680
2681   LzmaEnc_Finish(p);
2682
2683   /*
2684   if (res == SZ_OK && !Inline_MatchFinder_IsFinishedOK(&p->matchFinderBase))
2685     res = SZ_ERROR_FAIL;
2686   }
2687   */
2688
2689   return res;
2690 }
2691
2692
2693 SRes LzmaEnc_Encode(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream, ICompressProgress *progress,
2694     ISzAllocPtr alloc, ISzAllocPtr allocBig)
2695 {
2696   RINOK(LzmaEnc_Prepare(pp, outStream, inStream, alloc, allocBig));
2697   return LzmaEnc_Encode2((CLzmaEnc *)pp, progress);
2698 }
2699
2700
2701 SRes LzmaEnc_WriteProperties(CLzmaEncHandle pp, Byte *props, SizeT *size)
2702 {
2703   CLzmaEnc *p = (CLzmaEnc *)pp;
2704   unsigned i;
2705   UInt32 dictSize = p->dictSize;
2706   if (*size < LZMA_PROPS_SIZE)
2707     return SZ_ERROR_PARAM;
2708   *size = LZMA_PROPS_SIZE;
2709   props[0] = (Byte)((p->pb * 5 + p->lp) * 9 + p->lc);
2710
2711   if (dictSize >= ((UInt32)1 << 22))
2712   {
2713     UInt32 kDictMask = ((UInt32)1 << 20) - 1;
2714     if (dictSize < (UInt32)0xFFFFFFFF - kDictMask)
2715       dictSize = (dictSize + kDictMask) & ~kDictMask;
2716   }
2717   else for (i = 11; i <= 30; i++)
2718   {
2719     if (dictSize <= ((UInt32)2 << i)) { dictSize = (2 << i); break; }
2720     if (dictSize <= ((UInt32)3 << i)) { dictSize = (3 << i); break; }
2721   }
2722
2723   for (i = 0; i < 4; i++)
2724     props[1 + i] = (Byte)(dictSize >> (8 * i));
2725   return SZ_OK;
2726 }
2727
2728
2729 unsigned LzmaEnc_IsWriteEndMark(CLzmaEncHandle pp)
2730 {
2731   return ((CLzmaEnc *)pp)->writeEndMark;
2732 }
2733
2734
2735 SRes LzmaEnc_MemEncode(CLzmaEncHandle pp, Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
2736     int writeEndMark, ICompressProgress *progress, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2737 {
2738   SRes res;
2739   CLzmaEnc *p = (CLzmaEnc *)pp;
2740
2741   CLzmaEnc_SeqOutStreamBuf outStream;
2742
2743   outStream.vt.Write = SeqOutStreamBuf_Write;
2744   outStream.data = dest;
2745   outStream.rem = *destLen;
2746   outStream.overflow = False;
2747
2748   p->writeEndMark = writeEndMark;
2749   p->rc.outStream = &outStream.vt;
2750
2751   res = LzmaEnc_MemPrepare(pp, src, srcLen, 0, alloc, allocBig);
2752
2753   if (res == SZ_OK)
2754   {
2755     res = LzmaEnc_Encode2(p, progress);
2756     if (res == SZ_OK && p->nowPos64 != srcLen)
2757       res = SZ_ERROR_FAIL;
2758   }
2759
2760   *destLen -= outStream.rem;
2761   if (outStream.overflow)
2762     return SZ_ERROR_OUTPUT_EOF;
2763   return res;
2764 }
2765
2766
2767 SRes LzmaEncode(Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
2768     const CLzmaEncProps *props, Byte *propsEncoded, SizeT *propsSize, int writeEndMark,
2769     ICompressProgress *progress, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2770 {
2771   CLzmaEnc *p = (CLzmaEnc *)LzmaEnc_Create(alloc);
2772   SRes res;
2773   if (!p)
2774     return SZ_ERROR_MEM;
2775
2776   res = LzmaEnc_SetProps(p, props);
2777   if (res == SZ_OK)
2778   {
2779     res = LzmaEnc_WriteProperties(p, propsEncoded, propsSize);
2780     if (res == SZ_OK)
2781       res = LzmaEnc_MemEncode(p, dest, destLen, src, srcLen,
2782           writeEndMark, progress, alloc, allocBig);
2783   }
2784
2785   LzmaEnc_Destroy(p, alloc, allocBig);
2786   return res;
2787 }