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
1471         {
1472           unsigned state2 = kLiteralNextStates[state];
1473           unsigned posState2 = (position + 1) & p->pbMask;
1474           UInt32 price = litPrice + GetPrice_Rep_0(p, state2, posState2);
1475           {
1476             unsigned offset = cur + len;
1477             while (last < offset)
1478               p->opt[++last].price = kInfinityPrice;
1479
1480             // do
1481             {
1482               UInt32 price2;
1483               COptimal *opt;
1484               len--;
1485               // price2 = price + GetPrice_Len_Rep_0(p, len, state2, posState2);
1486               price2 = price + p->repLenEnc.prices[posState2][len - LZMA_MATCH_LEN_MIN];
1487
1488               opt = &p->opt[offset];
1489               // offset--;
1490               if (price2 < opt->price)
1491               {
1492                 opt->price = price2;
1493                 opt->len = len;
1494                 opt->dist = 0;
1495                 opt->extra = 1;
1496               }
1497             }
1498             // while (len >= 3);
1499           }
1500         }
1501       }
1502     }
1503
1504     startLen = 2; /* speed optimization */
1505     {
1506       // ---------- REP ----------
1507       unsigned repIndex = 0; // 17.old
1508       // unsigned repIndex = IsLitState(state) ? 0 : 1; // 18.notused
1509       for (; repIndex < LZMA_NUM_REPS; repIndex++)
1510       {
1511         unsigned len;
1512         UInt32 price;
1513         const Byte *data2 = data - reps[repIndex];
1514         if (data[0] != data2[0] || data[1] != data2[1])
1515           continue;
1516
1517         for (len = 2; len < numAvail && data[len] == data2[len]; len++);
1518
1519         // if (len < startLen) continue; // 18.new: speed optimization
1520
1521         while (last < cur + len)
1522           p->opt[++last].price = kInfinityPrice;
1523         {
1524           unsigned len2 = len;
1525           price = repMatchPrice + GetPrice_PureRep(p, repIndex, state, posState);
1526           do
1527           {
1528             UInt32 price2 = price + p->repLenEnc.prices[posState][(size_t)len2 - 2];
1529             COptimal *opt = &p->opt[cur + len2];
1530             if (price2 < opt->price)
1531             {
1532               opt->price = price2;
1533               opt->len = len2;
1534               opt->dist = repIndex;
1535               opt->extra = 0;
1536             }
1537           }
1538           while (--len2 >= 2);
1539         }
1540
1541         if (repIndex == 0) startLen = len + 1;  // 17.old
1542         // startLen = len + 1; // 18.new
1543
1544         /* if (_maxMode) */
1545         {
1546           // ---------- REP : LIT : REP_0 ----------
1547           // numFastBytes + 1 + numFastBytes
1548
1549           unsigned len2 = len + 1;
1550           unsigned limit = len2 + p->numFastBytes;
1551           if (limit > numAvailFull)
1552             limit = numAvailFull;
1553
1554           for (; len2 < limit && data[len2] == data2[len2]; len2++);
1555
1556           len2 -= len;
1557           if (len2 >= 3)
1558           {
1559             unsigned state2 = kRepNextStates[state];
1560             unsigned posState2 = (position + len) & p->pbMask;
1561             price +=
1562                   p->repLenEnc.prices[posState][(size_t)len - 2]
1563                 + GET_PRICE_0(p->isMatch[state2][posState2])
1564                 + LitEnc_Matched_GetPrice(LIT_PROBS(position + len, data[(size_t)len - 1]),
1565                     data[len], data2[len], p->ProbPrices);
1566
1567             // state2 = kLiteralNextStates[state2];
1568             state2 = kState_LitAfterRep;
1569             posState2 = (posState2 + 1) & p->pbMask;
1570
1571
1572             price += GetPrice_Rep_0(p, state2, posState2);
1573             {
1574               unsigned offset = cur + len + len2;
1575               while (last < offset)
1576                 p->opt[++last].price = kInfinityPrice;
1577               // do
1578               {
1579                 unsigned price2;
1580                 COptimal *opt;
1581                 len2--;
1582                 // price2 = price + GetPrice_Len_Rep_0(p, len2, state2, posState2);
1583                 price2 = price + p->repLenEnc.prices[posState2][len2 - LZMA_MATCH_LEN_MIN];
1584
1585                 opt = &p->opt[offset];
1586                 // offset--;
1587                 if (price2 < opt->price)
1588                 {
1589                   opt->price = price2;
1590                   opt->len = len2;
1591                   opt->extra = (CExtra)(len + 1);
1592                   opt->dist = repIndex;
1593                 }
1594               }
1595               // while (len2 >= 3);
1596             }
1597           }
1598         }
1599       }
1600     }
1601
1602
1603     // ---------- MATCH ----------
1604     /* for (unsigned len = 2; len <= newLen; len++) */
1605     if (newLen > numAvail)
1606     {
1607       newLen = numAvail;
1608       for (numPairs = 0; newLen > matches[numPairs]; numPairs += 2);
1609       matches[numPairs] = newLen;
1610       numPairs += 2;
1611     }
1612
1613     if (newLen >= startLen)
1614     {
1615       UInt32 normalMatchPrice = matchPrice + GET_PRICE_0(p->isRep[state]);
1616       UInt32 dist;
1617       unsigned offs, posSlot, len;
1618       while (last < cur + newLen)
1619         p->opt[++last].price = kInfinityPrice;
1620
1621       offs = 0;
1622       while (startLen > matches[offs])
1623         offs += 2;
1624       dist = matches[(size_t)offs + 1];
1625
1626       // if (dist >= kNumFullDistances)
1627       GetPosSlot2(dist, posSlot);
1628
1629       for (len = /*2*/ startLen; ; len++)
1630       {
1631         UInt32 price = normalMatchPrice + p->lenEnc.prices[posState][(size_t)len - LZMA_MATCH_LEN_MIN];
1632         {
1633           COptimal *opt;
1634           unsigned lenToPosState = len - 2; lenToPosState = GetLenToPosState2(lenToPosState);
1635           if (dist < kNumFullDistances)
1636             price += p->distancesPrices[lenToPosState][dist & (kNumFullDistances - 1)];
1637           else
1638             price += p->posSlotPrices[lenToPosState][posSlot] + p->alignPrices[dist & kAlignMask];
1639
1640           opt = &p->opt[cur + len];
1641           if (price < opt->price)
1642           {
1643             opt->price = price;
1644             opt->len = len;
1645             opt->dist = dist + LZMA_NUM_REPS;
1646             opt->extra = 0;
1647           }
1648         }
1649
1650         if (/*_maxMode && */ len == matches[offs])
1651         {
1652           // MATCH : LIT : REP_0
1653
1654           const Byte *data2 = data - dist - 1;
1655           unsigned len2 = len + 1;
1656           unsigned limit = len2 + p->numFastBytes;
1657           if (limit > numAvailFull)
1658             limit = numAvailFull;
1659
1660           for (; len2 < limit && data[len2] == data2[len2]; len2++);
1661
1662           len2 -= len;
1663
1664           if (len2 >= 3)
1665           {
1666             unsigned state2 = kMatchNextStates[state];
1667             unsigned posState2 = (position + len) & p->pbMask;
1668             unsigned offset;
1669             price += GET_PRICE_0(p->isMatch[state2][posState2]);
1670             price += LitEnc_Matched_GetPrice(LIT_PROBS(position + len, data[(size_t)len - 1]),
1671                     data[len], data2[len], p->ProbPrices);
1672
1673             // state2 = kLiteralNextStates[state2];
1674             state2 = kState_LitAfterMatch;
1675
1676             posState2 = (posState2 + 1) & p->pbMask;
1677             price += GetPrice_Rep_0(p, state2, posState2);
1678
1679             offset = cur + len + len2;
1680             while (last < offset)
1681               p->opt[++last].price = kInfinityPrice;
1682             // do
1683             {
1684               UInt32 price2;
1685               COptimal *opt;
1686               len2--;
1687               // price2 = price + GetPrice_Len_Rep_0(p, len2, state2, posState2);
1688               price2 = price + p->repLenEnc.prices[posState2][len2 - LZMA_MATCH_LEN_MIN];
1689               opt = &p->opt[offset];
1690               // offset--;
1691               if (price2 < opt->price)
1692               {
1693                 opt->price = price2;
1694                 opt->len = len2;
1695                 opt->extra = (CExtra)(len + 1);
1696                 opt->dist = dist + LZMA_NUM_REPS;
1697               }
1698             }
1699             // while (len2 >= 3);
1700           }
1701
1702           offs += 2;
1703           if (offs == numPairs)
1704             break;
1705           dist = matches[(size_t)offs + 1];
1706           // if (dist >= kNumFullDistances)
1707             GetPosSlot2(dist, posSlot);
1708         }
1709       }
1710     }
1711   }
1712 }
1713
1714
1715
1716 #define ChangePair(smallDist, bigDist) (((bigDist) >> 7) > (smallDist))
1717
1718
1719
1720 static unsigned GetOptimumFast(CLzmaEnc *p)
1721 {
1722   UInt32 numAvail, mainDist;
1723   unsigned mainLen, numPairs, repIndex, repLen, i;
1724   const Byte *data;
1725
1726   if (p->additionalOffset == 0)
1727     mainLen = ReadMatchDistances(p, &numPairs);
1728   else
1729   {
1730     mainLen = p->longestMatchLen;
1731     numPairs = p->numPairs;
1732   }
1733
1734   numAvail = p->numAvail;
1735   p->backRes = MARK_LIT;
1736   if (numAvail < 2)
1737     return 1;
1738   if (numAvail > LZMA_MATCH_LEN_MAX)
1739     numAvail = LZMA_MATCH_LEN_MAX;
1740   data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1741   repLen = repIndex = 0;
1742
1743   for (i = 0; i < LZMA_NUM_REPS; i++)
1744   {
1745     unsigned len;
1746     const Byte *data2 = data - p->reps[i];
1747     if (data[0] != data2[0] || data[1] != data2[1])
1748       continue;
1749     for (len = 2; len < numAvail && data[len] == data2[len]; len++);
1750     if (len >= p->numFastBytes)
1751     {
1752       p->backRes = i;
1753       MOVE_POS(p, len - 1)
1754       return len;
1755     }
1756     if (len > repLen)
1757     {
1758       repIndex = i;
1759       repLen = len;
1760     }
1761   }
1762
1763   if (mainLen >= p->numFastBytes)
1764   {
1765     p->backRes = p->matches[(size_t)numPairs - 1] + LZMA_NUM_REPS;
1766     MOVE_POS(p, mainLen - 1)
1767     return mainLen;
1768   }
1769
1770   mainDist = 0; /* for GCC */
1771
1772   if (mainLen >= 2)
1773   {
1774     mainDist = p->matches[(size_t)numPairs - 1];
1775     while (numPairs > 2)
1776     {
1777       UInt32 dist2;
1778       if (mainLen != p->matches[(size_t)numPairs - 4] + 1)
1779         break;
1780       dist2 = p->matches[(size_t)numPairs - 3];
1781       if (!ChangePair(dist2, mainDist))
1782         break;
1783       numPairs -= 2;
1784       mainLen--;
1785       mainDist = dist2;
1786     }
1787     if (mainLen == 2 && mainDist >= 0x80)
1788       mainLen = 1;
1789   }
1790
1791   if (repLen >= 2)
1792     if (    repLen + 1 >= mainLen
1793         || (repLen + 2 >= mainLen && mainDist >= (1 << 9))
1794         || (repLen + 3 >= mainLen && mainDist >= (1 << 15)))
1795   {
1796     p->backRes = repIndex;
1797     MOVE_POS(p, repLen - 1)
1798     return repLen;
1799   }
1800
1801   if (mainLen < 2 || numAvail <= 2)
1802     return 1;
1803
1804   {
1805     unsigned len1 = ReadMatchDistances(p, &p->numPairs);
1806     p->longestMatchLen = len1;
1807
1808     if (len1 >= 2)
1809     {
1810       UInt32 newDist = p->matches[(size_t)p->numPairs - 1];
1811       if (   (len1 >= mainLen && newDist < mainDist)
1812           || (len1 == mainLen + 1 && !ChangePair(mainDist, newDist))
1813           || (len1 >  mainLen + 1)
1814           || (len1 + 1 >= mainLen && mainLen >= 3 && ChangePair(newDist, mainDist)))
1815         return 1;
1816     }
1817   }
1818
1819   data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - 1;
1820
1821   for (i = 0; i < LZMA_NUM_REPS; i++)
1822   {
1823     unsigned len, limit;
1824     const Byte *data2 = data - p->reps[i];
1825     if (data[0] != data2[0] || data[1] != data2[1])
1826       continue;
1827     limit = mainLen - 1;
1828     for (len = 2;; len++)
1829     {
1830       if (len >= limit)
1831         return 1;
1832       if (data[len] != data2[len])
1833         break;
1834     }
1835   }
1836
1837   p->backRes = mainDist + LZMA_NUM_REPS;
1838   if (mainLen != 2)
1839   {
1840     MOVE_POS(p, mainLen - 2)
1841   }
1842   return mainLen;
1843 }
1844
1845
1846
1847
1848 static void WriteEndMarker(CLzmaEnc *p, unsigned posState)
1849 {
1850   UInt32 range;
1851   range = p->rc.range;
1852   {
1853     UInt32 ttt, newBound;
1854     CLzmaProb *prob = &p->isMatch[p->state][posState];
1855     RC_BIT_PRE(&p->rc, prob)
1856     RC_BIT_1(&p->rc, prob)
1857     prob = &p->isRep[p->state];
1858     RC_BIT_PRE(&p->rc, prob)
1859     RC_BIT_0(&p->rc, prob)
1860   }
1861   p->state = kMatchNextStates[p->state];
1862
1863   p->rc.range = range;
1864   LenEnc_Encode(&p->lenProbs, &p->rc, 0, posState);
1865   range = p->rc.range;
1866
1867   {
1868     // RcTree_Encode_PosSlot(&p->rc, p->posSlotEncoder[0], (1 << kNumPosSlotBits) - 1);
1869     CLzmaProb *probs = p->posSlotEncoder[0];
1870     unsigned m = 1;
1871     do
1872     {
1873       UInt32 ttt, newBound;
1874       RC_BIT_PRE(p, probs + m)
1875       RC_BIT_1(&p->rc, probs + m);
1876       m = (m << 1) + 1;
1877     }
1878     while (m < (1 << kNumPosSlotBits));
1879   }
1880   {
1881     // RangeEnc_EncodeDirectBits(&p->rc, ((UInt32)1 << (30 - kNumAlignBits)) - 1, 30 - kNumAlignBits);    UInt32 range = p->range;
1882     unsigned numBits = 30 - kNumAlignBits;
1883     do
1884     {
1885       range >>= 1;
1886       p->rc.low += range;
1887       RC_NORM(&p->rc)
1888     }
1889     while (--numBits);
1890   }
1891
1892   {
1893     // RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, kAlignMask);
1894     CLzmaProb *probs = p->posAlignEncoder;
1895     unsigned m = 1;
1896     do
1897     {
1898       UInt32 ttt, newBound;
1899       RC_BIT_PRE(p, probs + m)
1900       RC_BIT_1(&p->rc, probs + m);
1901       m = (m << 1) + 1;
1902     }
1903     while (m < kAlignTableSize);
1904   }
1905   p->rc.range = range;
1906 }
1907
1908
1909 static SRes CheckErrors(CLzmaEnc *p)
1910 {
1911   if (p->result != SZ_OK)
1912     return p->result;
1913   if (p->rc.res != SZ_OK)
1914     p->result = SZ_ERROR_WRITE;
1915   if (p->matchFinderBase.result != SZ_OK)
1916     p->result = SZ_ERROR_READ;
1917   if (p->result != SZ_OK)
1918     p->finished = True;
1919   return p->result;
1920 }
1921
1922
1923 MY_NO_INLINE static SRes Flush(CLzmaEnc *p, UInt32 nowPos)
1924 {
1925   /* ReleaseMFStream(); */
1926   p->finished = True;
1927   if (p->writeEndMark)
1928     WriteEndMarker(p, nowPos & p->pbMask);
1929   RangeEnc_FlushData(&p->rc);
1930   RangeEnc_FlushStream(&p->rc);
1931   return CheckErrors(p);
1932 }
1933
1934
1935
1936 static void FillAlignPrices(CLzmaEnc *p)
1937 {
1938   unsigned i;
1939   const CProbPrice *ProbPrices = p->ProbPrices;
1940   const CLzmaProb *probs = p->posAlignEncoder;
1941   p->alignPriceCount = 0;
1942   for (i = 0; i < kAlignTableSize / 2; i++)
1943   {
1944     UInt32 price = 0;
1945     unsigned symbol = i;
1946     unsigned m = 1;
1947     unsigned bit;
1948     UInt32 prob;
1949     bit = symbol & 1; symbol >>= 1; price += GET_PRICEa(probs[m], bit); m = (m << 1) + bit;
1950     bit = symbol & 1; symbol >>= 1; price += GET_PRICEa(probs[m], bit); m = (m << 1) + bit;
1951     bit = symbol & 1; symbol >>= 1; price += GET_PRICEa(probs[m], bit); m = (m << 1) + bit;
1952     prob = probs[m];
1953     p->alignPrices[i    ] = price + GET_PRICEa_0(prob);
1954     p->alignPrices[i + 8] = price + GET_PRICEa_1(prob);
1955     // p->alignPrices[i] = RcTree_ReverseGetPrice(p->posAlignEncoder, kNumAlignBits, i, p->ProbPrices);
1956   }
1957 }
1958
1959
1960 static void FillDistancesPrices(CLzmaEnc *p)
1961 {
1962   UInt32 tempPrices[kNumFullDistances];
1963   unsigned i, lenToPosState;
1964
1965   const CProbPrice *ProbPrices = p->ProbPrices;
1966   p->matchPriceCount = 0;
1967
1968   for (i = kStartPosModelIndex; i < kNumFullDistances; i++)
1969   {
1970     unsigned posSlot = GetPosSlot1(i);
1971     unsigned footerBits = ((posSlot >> 1) - 1);
1972     unsigned base = ((2 | (posSlot & 1)) << footerBits);
1973     // tempPrices[i] = RcTree_ReverseGetPrice(p->posEncoders + base, footerBits, i - base, p->ProbPrices);
1974
1975     const CLzmaProb *probs = p->posEncoders + base;
1976     UInt32 price = 0;
1977     unsigned m = 1;
1978     unsigned symbol = i - base;
1979     do
1980     {
1981       unsigned bit = symbol & 1;
1982       symbol >>= 1;
1983       price += GET_PRICEa(probs[m], bit);
1984       m = (m << 1) + bit;
1985     }
1986     while (--footerBits);
1987     tempPrices[i] = price;
1988   }
1989
1990   for (lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++)
1991   {
1992     unsigned posSlot;
1993     const CLzmaProb *encoder = p->posSlotEncoder[lenToPosState];
1994     UInt32 *posSlotPrices = p->posSlotPrices[lenToPosState];
1995     unsigned distTableSize = p->distTableSize;
1996     const CLzmaProb *probs = encoder;
1997     for (posSlot = 0; posSlot < distTableSize; posSlot += 2)
1998     {
1999       // posSlotPrices[posSlot] = RcTree_GetPrice(encoder, kNumPosSlotBits, posSlot, p->ProbPrices);
2000       UInt32 price = 0;
2001       unsigned bit;
2002       unsigned symbol = (posSlot >> 1) + (1 << (kNumPosSlotBits - 1));
2003       UInt32 prob;
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       bit = symbol & 1; symbol >>= 1; price += GET_PRICEa(probs[symbol], bit);
2008       bit = symbol & 1; symbol >>= 1; price += GET_PRICEa(probs[symbol], bit);
2009       prob = probs[(posSlot >> 1) + (1 << (kNumPosSlotBits - 1))];
2010       posSlotPrices[posSlot    ] = price + GET_PRICEa_0(prob);
2011       posSlotPrices[posSlot + 1] = price + GET_PRICEa_1(prob);
2012     }
2013     for (posSlot = kEndPosModelIndex; posSlot < distTableSize; posSlot++)
2014       posSlotPrices[posSlot] += ((UInt32)(((posSlot >> 1) - 1) - kNumAlignBits) << kNumBitPriceShiftBits);
2015
2016     {
2017       UInt32 *distancesPrices = p->distancesPrices[lenToPosState];
2018       {
2019         distancesPrices[0] = posSlotPrices[0];
2020         distancesPrices[1] = posSlotPrices[1];
2021         distancesPrices[2] = posSlotPrices[2];
2022         distancesPrices[3] = posSlotPrices[3];
2023       }
2024       for (i = 4; i < kNumFullDistances; i += 2)
2025       {
2026         UInt32 slotPrice = posSlotPrices[GetPosSlot1(i)];
2027         distancesPrices[i    ] = slotPrice + tempPrices[i];
2028         distancesPrices[i + 1] = slotPrice + tempPrices[i + 1];
2029       }
2030     }
2031   }
2032 }
2033
2034
2035
2036 void LzmaEnc_Construct(CLzmaEnc *p)
2037 {
2038   RangeEnc_Construct(&p->rc);
2039   MatchFinder_Construct(&p->matchFinderBase);
2040
2041   #ifndef _7ZIP_ST
2042   MatchFinderMt_Construct(&p->matchFinderMt);
2043   p->matchFinderMt.MatchFinder = &p->matchFinderBase;
2044   #endif
2045
2046   {
2047     CLzmaEncProps props;
2048     LzmaEncProps_Init(&props);
2049     LzmaEnc_SetProps(p, &props);
2050   }
2051
2052   #ifndef LZMA_LOG_BSR
2053   LzmaEnc_FastPosInit(p->g_FastPos);
2054   #endif
2055
2056   LzmaEnc_InitPriceTables(p->ProbPrices);
2057   p->litProbs = NULL;
2058   p->saveState.litProbs = NULL;
2059
2060 }
2061
2062 CLzmaEncHandle LzmaEnc_Create(ISzAllocPtr alloc)
2063 {
2064   void *p;
2065   p = ISzAlloc_Alloc(alloc, sizeof(CLzmaEnc));
2066   if (p)
2067     LzmaEnc_Construct((CLzmaEnc *)p);
2068   return p;
2069 }
2070
2071 void LzmaEnc_FreeLits(CLzmaEnc *p, ISzAllocPtr alloc)
2072 {
2073   ISzAlloc_Free(alloc, p->litProbs);
2074   ISzAlloc_Free(alloc, p->saveState.litProbs);
2075   p->litProbs = NULL;
2076   p->saveState.litProbs = NULL;
2077 }
2078
2079 void LzmaEnc_Destruct(CLzmaEnc *p, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2080 {
2081   #ifndef _7ZIP_ST
2082   MatchFinderMt_Destruct(&p->matchFinderMt, allocBig);
2083   #endif
2084
2085   MatchFinder_Free(&p->matchFinderBase, allocBig);
2086   LzmaEnc_FreeLits(p, alloc);
2087   RangeEnc_Free(&p->rc, alloc);
2088 }
2089
2090 void LzmaEnc_Destroy(CLzmaEncHandle p, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2091 {
2092   LzmaEnc_Destruct((CLzmaEnc *)p, alloc, allocBig);
2093   ISzAlloc_Free(alloc, p);
2094 }
2095
2096
2097 static SRes LzmaEnc_CodeOneBlock(CLzmaEnc *p, UInt32 maxPackSize, UInt32 maxUnpackSize)
2098 {
2099   UInt32 nowPos32, startPos32;
2100   if (p->needInit)
2101   {
2102     p->matchFinder.Init(p->matchFinderObj);
2103     p->needInit = 0;
2104   }
2105
2106   if (p->finished)
2107     return p->result;
2108   RINOK(CheckErrors(p));
2109
2110   nowPos32 = (UInt32)p->nowPos64;
2111   startPos32 = nowPos32;
2112
2113   if (p->nowPos64 == 0)
2114   {
2115     unsigned numPairs;
2116     Byte curByte;
2117     if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)
2118       return Flush(p, nowPos32);
2119     ReadMatchDistances(p, &numPairs);
2120     RangeEnc_EncodeBit_0(&p->rc, &p->isMatch[kState_Start][0]);
2121     // p->state = kLiteralNextStates[p->state];
2122     curByte = *(p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset);
2123     LitEnc_Encode(&p->rc, p->litProbs, curByte);
2124     p->additionalOffset--;
2125     nowPos32++;
2126   }
2127
2128   if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) != 0)
2129
2130   for (;;)
2131   {
2132     UInt32 dist;
2133     unsigned len, posState;
2134     UInt32 range, ttt, newBound;
2135     CLzmaProb *probs;
2136
2137     if (p->fastMode)
2138       len = GetOptimumFast(p);
2139     else
2140     {
2141       unsigned oci = p->optCur;
2142       if (p->optEnd == oci)
2143         len = GetOptimum(p, nowPos32);
2144       else
2145       {
2146         const COptimal *opt = &p->opt[oci];
2147         len = opt->len;
2148         p->backRes = opt->dist;
2149         p->optCur = oci + 1;
2150       }
2151     }
2152
2153     posState = (unsigned)nowPos32 & p->pbMask;
2154     range = p->rc.range;
2155     probs = &p->isMatch[p->state][posState];
2156
2157     RC_BIT_PRE(&p->rc, probs)
2158
2159     dist = p->backRes;
2160
2161     #ifdef SHOW_STAT2
2162     printf("\n pos = %6X, len = %3u  pos = %6u", nowPos32, len, dist);
2163     #endif
2164
2165     if (dist == MARK_LIT)
2166     {
2167       Byte curByte;
2168       const Byte *data;
2169       unsigned state;
2170
2171       RC_BIT_0(&p->rc, probs);
2172       p->rc.range = range;
2173       data = p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
2174       probs = LIT_PROBS(nowPos32, *(data - 1));
2175       curByte = *data;
2176       state = p->state;
2177       p->state = kLiteralNextStates[state];
2178       if (IsLitState(state))
2179         LitEnc_Encode(&p->rc, probs, curByte);
2180       else
2181         LitEnc_EncodeMatched(&p->rc, probs, curByte, *(data - p->reps[0]));
2182     }
2183     else
2184     {
2185       RC_BIT_1(&p->rc, probs);
2186       probs = &p->isRep[p->state];
2187       RC_BIT_PRE(&p->rc, probs)
2188
2189       if (dist < LZMA_NUM_REPS)
2190       {
2191         RC_BIT_1(&p->rc, probs);
2192         probs = &p->isRepG0[p->state];
2193         RC_BIT_PRE(&p->rc, probs)
2194         if (dist == 0)
2195         {
2196           RC_BIT_0(&p->rc, probs);
2197           probs = &p->isRep0Long[p->state][posState];
2198           RC_BIT_PRE(&p->rc, probs)
2199           if (len != 1)
2200           {
2201             RC_BIT_1_BASE(&p->rc, probs);
2202           }
2203           else
2204           {
2205             RC_BIT_0_BASE(&p->rc, probs);
2206             p->state = kShortRepNextStates[p->state];
2207           }
2208         }
2209         else
2210         {
2211           RC_BIT_1(&p->rc, probs);
2212           probs = &p->isRepG1[p->state];
2213           RC_BIT_PRE(&p->rc, probs)
2214           if (dist == 1)
2215           {
2216             RC_BIT_0_BASE(&p->rc, probs);
2217             dist = p->reps[1];
2218           }
2219           else
2220           {
2221             RC_BIT_1(&p->rc, probs);
2222             probs = &p->isRepG2[p->state];
2223             RC_BIT_PRE(&p->rc, probs)
2224             if (dist == 2)
2225             {
2226               RC_BIT_0_BASE(&p->rc, probs);
2227               dist = p->reps[2];
2228             }
2229             else
2230             {
2231               RC_BIT_1_BASE(&p->rc, probs);
2232               dist = p->reps[3];
2233               p->reps[3] = p->reps[2];
2234             }
2235             p->reps[2] = p->reps[1];
2236           }
2237           p->reps[1] = p->reps[0];
2238           p->reps[0] = dist;
2239         }
2240
2241         RC_NORM(&p->rc)
2242
2243         p->rc.range = range;
2244
2245         if (len != 1)
2246         {
2247           LenEnc_Encode(&p->repLenProbs, &p->rc, len - LZMA_MATCH_LEN_MIN, posState);
2248           if (!p->fastMode)
2249             if (--p->repLenEnc.counters[posState] == 0)
2250               LenPriceEnc_UpdateTable(&p->repLenEnc, posState, &p->repLenProbs, p->ProbPrices);
2251
2252           p->state = kRepNextStates[p->state];
2253         }
2254       }
2255       else
2256       {
2257         unsigned posSlot;
2258         RC_BIT_0(&p->rc, probs);
2259         p->rc.range = range;
2260         p->state = kMatchNextStates[p->state];
2261
2262         LenEnc_Encode(&p->lenProbs, &p->rc, len - LZMA_MATCH_LEN_MIN, posState);
2263         if (!p->fastMode)
2264           if (--p->lenEnc.counters[posState] == 0)
2265             LenPriceEnc_UpdateTable(&p->lenEnc, posState, &p->lenProbs, p->ProbPrices);
2266
2267         dist -= LZMA_NUM_REPS;
2268         p->reps[3] = p->reps[2];
2269         p->reps[2] = p->reps[1];
2270         p->reps[1] = p->reps[0];
2271         p->reps[0] = dist + 1;
2272
2273         p->matchPriceCount++;
2274         GetPosSlot(dist, posSlot);
2275         // RcTree_Encode_PosSlot(&p->rc, p->posSlotEncoder[GetLenToPosState(len)], posSlot);
2276         {
2277           UInt32 symbol = posSlot + (1 << kNumPosSlotBits);
2278           range = p->rc.range;
2279           probs = p->posSlotEncoder[GetLenToPosState(len)];
2280           do
2281           {
2282             CLzmaProb *prob = probs + (symbol >> kNumPosSlotBits);
2283             UInt32 bit = (symbol >> (kNumPosSlotBits - 1)) & 1;
2284             symbol <<= 1;
2285             RC_BIT(&p->rc, prob, bit);
2286           }
2287           while (symbol < (1 << kNumPosSlotBits * 2));
2288           p->rc.range = range;
2289         }
2290
2291         if (dist >= kStartPosModelIndex)
2292         {
2293           unsigned footerBits = ((posSlot >> 1) - 1);
2294
2295           if (dist < kNumFullDistances)
2296           {
2297             unsigned base = ((2 | (posSlot & 1)) << footerBits);
2298             RcTree_ReverseEncode(&p->rc, p->posEncoders + base, footerBits, dist - base);
2299           }
2300           else
2301           {
2302             UInt32 pos2 = (dist | 0xF) << (32 - footerBits);
2303             range = p->rc.range;
2304             // RangeEnc_EncodeDirectBits(&p->rc, posReduced >> kNumAlignBits, footerBits - kNumAlignBits);
2305             /*
2306             do
2307             {
2308               range >>= 1;
2309               p->rc.low += range & (0 - ((dist >> --footerBits) & 1));
2310               RC_NORM(&p->rc)
2311             }
2312             while (footerBits > kNumAlignBits);
2313             */
2314             do
2315             {
2316               range >>= 1;
2317               p->rc.low += range & (0 - (pos2 >> 31));
2318               pos2 += pos2;
2319               RC_NORM(&p->rc)
2320             }
2321             while (pos2 != 0xF0000000);
2322
2323
2324             // RcTree_ReverseEncode(&p->rc, p->posAlignEncoder, kNumAlignBits, posReduced & kAlignMask);
2325
2326             {
2327               unsigned m = 1;
2328               unsigned bit;
2329               bit = dist & 1; dist >>= 1; RC_BIT(&p->rc, p->posAlignEncoder + m, bit); m = (m << 1) + bit;
2330               bit = dist & 1; dist >>= 1; RC_BIT(&p->rc, p->posAlignEncoder + m, bit); m = (m << 1) + bit;
2331               bit = dist & 1; dist >>= 1; RC_BIT(&p->rc, p->posAlignEncoder + m, bit); m = (m << 1) + bit;
2332               bit = dist & 1;             RC_BIT(&p->rc, p->posAlignEncoder + m, bit);
2333               p->rc.range = range;
2334               p->alignPriceCount++;
2335             }
2336           }
2337         }
2338       }
2339     }
2340
2341     nowPos32 += len;
2342     p->additionalOffset -= len;
2343
2344     if (p->additionalOffset == 0)
2345     {
2346       UInt32 processed;
2347
2348       if (!p->fastMode)
2349       {
2350         if (p->matchPriceCount >= (1 << 7))
2351           FillDistancesPrices(p);
2352         if (p->alignPriceCount >= kAlignTableSize)
2353           FillAlignPrices(p);
2354       }
2355
2356       if (p->matchFinder.GetNumAvailableBytes(p->matchFinderObj) == 0)
2357         break;
2358       processed = nowPos32 - startPos32;
2359
2360       if (maxPackSize)
2361       {
2362         if (processed + kNumOpts + 300 >= maxUnpackSize
2363             || RangeEnc_GetProcessed_sizet(&p->rc) + kPackReserve >= maxPackSize)
2364           break;
2365       }
2366       else if (processed >= (1 << 17))
2367       {
2368         p->nowPos64 += nowPos32 - startPos32;
2369         return CheckErrors(p);
2370       }
2371     }
2372   }
2373
2374   p->nowPos64 += nowPos32 - startPos32;
2375   return Flush(p, nowPos32);
2376 }
2377
2378
2379
2380 #define kBigHashDicLimit ((UInt32)1 << 24)
2381
2382 static SRes LzmaEnc_Alloc(CLzmaEnc *p, UInt32 keepWindowSize, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2383 {
2384   UInt32 beforeSize = kNumOpts;
2385   if (!RangeEnc_Alloc(&p->rc, alloc))
2386     return SZ_ERROR_MEM;
2387
2388   #ifndef _7ZIP_ST
2389   p->mtMode = (p->multiThread && !p->fastMode && (p->matchFinderBase.btMode != 0));
2390   #endif
2391
2392   {
2393     unsigned lclp = p->lc + p->lp;
2394     if (!p->litProbs || !p->saveState.litProbs || p->lclp != lclp)
2395     {
2396       LzmaEnc_FreeLits(p, alloc);
2397       p->litProbs = (CLzmaProb *)ISzAlloc_Alloc(alloc, ((UInt32)0x300 << lclp) * sizeof(CLzmaProb));
2398       p->saveState.litProbs = (CLzmaProb *)ISzAlloc_Alloc(alloc, ((UInt32)0x300 << lclp) * sizeof(CLzmaProb));
2399       if (!p->litProbs || !p->saveState.litProbs)
2400       {
2401         LzmaEnc_FreeLits(p, alloc);
2402         return SZ_ERROR_MEM;
2403       }
2404       p->lclp = lclp;
2405     }
2406   }
2407
2408   p->matchFinderBase.bigHash = (Byte)(p->dictSize > kBigHashDicLimit ? 1 : 0);
2409
2410   if (beforeSize + p->dictSize < keepWindowSize)
2411     beforeSize = keepWindowSize - p->dictSize;
2412
2413   #ifndef _7ZIP_ST
2414   if (p->mtMode)
2415   {
2416     RINOK(MatchFinderMt_Create(&p->matchFinderMt, p->dictSize, beforeSize, p->numFastBytes,
2417         LZMA_MATCH_LEN_MAX
2418         + 1  /* 18.04 */
2419         , allocBig));
2420     p->matchFinderObj = &p->matchFinderMt;
2421     p->matchFinderBase.bigHash = (Byte)(
2422         (p->dictSize > kBigHashDicLimit && p->matchFinderBase.hashMask >= 0xFFFFFF) ? 1 : 0);
2423     MatchFinderMt_CreateVTable(&p->matchFinderMt, &p->matchFinder);
2424   }
2425   else
2426   #endif
2427   {
2428     if (!MatchFinder_Create(&p->matchFinderBase, p->dictSize, beforeSize, p->numFastBytes, LZMA_MATCH_LEN_MAX, allocBig))
2429       return SZ_ERROR_MEM;
2430     p->matchFinderObj = &p->matchFinderBase;
2431     MatchFinder_CreateVTable(&p->matchFinderBase, &p->matchFinder);
2432   }
2433
2434   return SZ_OK;
2435 }
2436
2437 void LzmaEnc_Init(CLzmaEnc *p)
2438 {
2439   unsigned i;
2440   p->state = 0;
2441   p->reps[0] =
2442   p->reps[1] =
2443   p->reps[2] =
2444   p->reps[3] = 1;
2445
2446   RangeEnc_Init(&p->rc);
2447
2448   for (i = 0; i < (1 << kNumAlignBits); i++)
2449     p->posAlignEncoder[i] = kProbInitValue;
2450
2451   for (i = 0; i < kNumStates; i++)
2452   {
2453     unsigned j;
2454     for (j = 0; j < LZMA_NUM_PB_STATES_MAX; j++)
2455     {
2456       p->isMatch[i][j] = kProbInitValue;
2457       p->isRep0Long[i][j] = kProbInitValue;
2458     }
2459     p->isRep[i] = kProbInitValue;
2460     p->isRepG0[i] = kProbInitValue;
2461     p->isRepG1[i] = kProbInitValue;
2462     p->isRepG2[i] = kProbInitValue;
2463   }
2464
2465   {
2466     for (i = 0; i < kNumLenToPosStates; i++)
2467     {
2468       CLzmaProb *probs = p->posSlotEncoder[i];
2469       unsigned j;
2470       for (j = 0; j < (1 << kNumPosSlotBits); j++)
2471         probs[j] = kProbInitValue;
2472     }
2473   }
2474   {
2475     for (i = 0; i < kNumFullDistances; i++)
2476       p->posEncoders[i] = kProbInitValue;
2477   }
2478
2479   {
2480     UInt32 num = (UInt32)0x300 << (p->lp + p->lc);
2481     UInt32 k;
2482     CLzmaProb *probs = p->litProbs;
2483     for (k = 0; k < num; k++)
2484       probs[k] = kProbInitValue;
2485   }
2486
2487
2488   LenEnc_Init(&p->lenProbs);
2489   LenEnc_Init(&p->repLenProbs);
2490
2491   p->optEnd = 0;
2492   p->optCur = 0;
2493   p->additionalOffset = 0;
2494
2495   p->pbMask = (1 << p->pb) - 1;
2496   p->lpMask = ((UInt32)0x100 << p->lp) - ((unsigned)0x100 >> p->lc);
2497 }
2498
2499 void LzmaEnc_InitPrices(CLzmaEnc *p)
2500 {
2501   if (!p->fastMode)
2502   {
2503     FillDistancesPrices(p);
2504     FillAlignPrices(p);
2505   }
2506
2507   p->lenEnc.tableSize =
2508   p->repLenEnc.tableSize =
2509       p->numFastBytes + 1 - LZMA_MATCH_LEN_MIN;
2510   LenPriceEnc_UpdateTables(&p->lenEnc, 1 << p->pb, &p->lenProbs, p->ProbPrices);
2511   LenPriceEnc_UpdateTables(&p->repLenEnc, 1 << p->pb, &p->repLenProbs, p->ProbPrices);
2512 }
2513
2514 static SRes LzmaEnc_AllocAndInit(CLzmaEnc *p, UInt32 keepWindowSize, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2515 {
2516   unsigned i;
2517   for (i = kEndPosModelIndex / 2; i < kDicLogSizeMax; i++)
2518     if (p->dictSize <= ((UInt32)1 << i))
2519       break;
2520   p->distTableSize = i * 2;
2521
2522   p->finished = False;
2523   p->result = SZ_OK;
2524   RINOK(LzmaEnc_Alloc(p, keepWindowSize, alloc, allocBig));
2525   LzmaEnc_Init(p);
2526   LzmaEnc_InitPrices(p);
2527   p->nowPos64 = 0;
2528   return SZ_OK;
2529 }
2530
2531 static SRes LzmaEnc_Prepare(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream,
2532     ISzAllocPtr alloc, ISzAllocPtr allocBig)
2533 {
2534   CLzmaEnc *p = (CLzmaEnc *)pp;
2535   p->matchFinderBase.stream = inStream;
2536   p->needInit = 1;
2537   p->rc.outStream = outStream;
2538   return LzmaEnc_AllocAndInit(p, 0, alloc, allocBig);
2539 }
2540
2541 SRes LzmaEnc_PrepareForLzma2(CLzmaEncHandle pp,
2542     ISeqInStream *inStream, UInt32 keepWindowSize,
2543     ISzAllocPtr alloc, ISzAllocPtr allocBig)
2544 {
2545   CLzmaEnc *p = (CLzmaEnc *)pp;
2546   p->matchFinderBase.stream = inStream;
2547   p->needInit = 1;
2548   return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);
2549 }
2550
2551 static void LzmaEnc_SetInputBuf(CLzmaEnc *p, const Byte *src, SizeT srcLen)
2552 {
2553   p->matchFinderBase.directInput = 1;
2554   p->matchFinderBase.bufferBase = (Byte *)src;
2555   p->matchFinderBase.directInputRem = srcLen;
2556 }
2557
2558 SRes LzmaEnc_MemPrepare(CLzmaEncHandle pp, const Byte *src, SizeT srcLen,
2559     UInt32 keepWindowSize, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2560 {
2561   CLzmaEnc *p = (CLzmaEnc *)pp;
2562   LzmaEnc_SetInputBuf(p, src, srcLen);
2563   p->needInit = 1;
2564
2565   LzmaEnc_SetDataSize(pp, srcLen);
2566   return LzmaEnc_AllocAndInit(p, keepWindowSize, alloc, allocBig);
2567 }
2568
2569 void LzmaEnc_Finish(CLzmaEncHandle pp)
2570 {
2571   #ifndef _7ZIP_ST
2572   CLzmaEnc *p = (CLzmaEnc *)pp;
2573   if (p->mtMode)
2574     MatchFinderMt_ReleaseStream(&p->matchFinderMt);
2575   #else
2576   UNUSED_VAR(pp);
2577   #endif
2578 }
2579
2580
2581 typedef struct
2582 {
2583   ISeqOutStream vt;
2584   Byte *data;
2585   SizeT rem;
2586   Bool overflow;
2587 } CLzmaEnc_SeqOutStreamBuf;
2588
2589 static size_t SeqOutStreamBuf_Write(const ISeqOutStream *pp, const void *data, size_t size)
2590 {
2591   CLzmaEnc_SeqOutStreamBuf *p = CONTAINER_FROM_VTBL(pp, CLzmaEnc_SeqOutStreamBuf, vt);
2592   if (p->rem < size)
2593   {
2594     size = p->rem;
2595     p->overflow = True;
2596   }
2597   memcpy(p->data, data, size);
2598   p->rem -= size;
2599   p->data += size;
2600   return size;
2601 }
2602
2603
2604 UInt32 LzmaEnc_GetNumAvailableBytes(CLzmaEncHandle pp)
2605 {
2606   const CLzmaEnc *p = (CLzmaEnc *)pp;
2607   return p->matchFinder.GetNumAvailableBytes(p->matchFinderObj);
2608 }
2609
2610
2611 const Byte *LzmaEnc_GetCurBuf(CLzmaEncHandle pp)
2612 {
2613   const CLzmaEnc *p = (CLzmaEnc *)pp;
2614   return p->matchFinder.GetPointerToCurrentPos(p->matchFinderObj) - p->additionalOffset;
2615 }
2616
2617
2618 SRes LzmaEnc_CodeOneMemBlock(CLzmaEncHandle pp, Bool reInit,
2619     Byte *dest, size_t *destLen, UInt32 desiredPackSize, UInt32 *unpackSize)
2620 {
2621   CLzmaEnc *p = (CLzmaEnc *)pp;
2622   UInt64 nowPos64;
2623   SRes res;
2624   CLzmaEnc_SeqOutStreamBuf outStream;
2625
2626   outStream.vt.Write = SeqOutStreamBuf_Write;
2627   outStream.data = dest;
2628   outStream.rem = *destLen;
2629   outStream.overflow = False;
2630
2631   p->writeEndMark = False;
2632   p->finished = False;
2633   p->result = SZ_OK;
2634
2635   if (reInit)
2636     LzmaEnc_Init(p);
2637   LzmaEnc_InitPrices(p);
2638
2639   nowPos64 = p->nowPos64;
2640   RangeEnc_Init(&p->rc);
2641   p->rc.outStream = &outStream.vt;
2642
2643   if (desiredPackSize == 0)
2644     return SZ_ERROR_OUTPUT_EOF;
2645
2646   res = LzmaEnc_CodeOneBlock(p, desiredPackSize, *unpackSize);
2647
2648   *unpackSize = (UInt32)(p->nowPos64 - nowPos64);
2649   *destLen -= outStream.rem;
2650   if (outStream.overflow)
2651     return SZ_ERROR_OUTPUT_EOF;
2652
2653   return res;
2654 }
2655
2656
2657 static SRes LzmaEnc_Encode2(CLzmaEnc *p, ICompressProgress *progress)
2658 {
2659   SRes res = SZ_OK;
2660
2661   #ifndef _7ZIP_ST
2662   Byte allocaDummy[0x300];
2663   allocaDummy[0] = 0;
2664   allocaDummy[1] = allocaDummy[0];
2665   #endif
2666
2667   for (;;)
2668   {
2669     res = LzmaEnc_CodeOneBlock(p, 0, 0);
2670     if (res != SZ_OK || p->finished)
2671       break;
2672     if (progress)
2673     {
2674       res = ICompressProgress_Progress(progress, p->nowPos64, RangeEnc_GetProcessed(&p->rc));
2675       if (res != SZ_OK)
2676       {
2677         res = SZ_ERROR_PROGRESS;
2678         break;
2679       }
2680     }
2681   }
2682
2683   LzmaEnc_Finish(p);
2684
2685   /*
2686   if (res == SZ_OK && !Inline_MatchFinder_IsFinishedOK(&p->matchFinderBase))
2687     res = SZ_ERROR_FAIL;
2688   }
2689   */
2690
2691   return res;
2692 }
2693
2694
2695 SRes LzmaEnc_Encode(CLzmaEncHandle pp, ISeqOutStream *outStream, ISeqInStream *inStream, ICompressProgress *progress,
2696     ISzAllocPtr alloc, ISzAllocPtr allocBig)
2697 {
2698   RINOK(LzmaEnc_Prepare(pp, outStream, inStream, alloc, allocBig));
2699   return LzmaEnc_Encode2((CLzmaEnc *)pp, progress);
2700 }
2701
2702
2703 SRes LzmaEnc_WriteProperties(CLzmaEncHandle pp, Byte *props, SizeT *size)
2704 {
2705   CLzmaEnc *p = (CLzmaEnc *)pp;
2706   unsigned i;
2707   UInt32 dictSize = p->dictSize;
2708   if (*size < LZMA_PROPS_SIZE)
2709     return SZ_ERROR_PARAM;
2710   *size = LZMA_PROPS_SIZE;
2711   props[0] = (Byte)((p->pb * 5 + p->lp) * 9 + p->lc);
2712
2713   if (dictSize >= ((UInt32)1 << 22))
2714   {
2715     UInt32 kDictMask = ((UInt32)1 << 20) - 1;
2716     if (dictSize < (UInt32)0xFFFFFFFF - kDictMask)
2717       dictSize = (dictSize + kDictMask) & ~kDictMask;
2718   }
2719   else for (i = 11; i <= 30; i++)
2720   {
2721     if (dictSize <= ((UInt32)2 << i)) { dictSize = (2 << i); break; }
2722     if (dictSize <= ((UInt32)3 << i)) { dictSize = (3 << i); break; }
2723   }
2724
2725   for (i = 0; i < 4; i++)
2726     props[1 + i] = (Byte)(dictSize >> (8 * i));
2727   return SZ_OK;
2728 }
2729
2730
2731 unsigned LzmaEnc_IsWriteEndMark(CLzmaEncHandle pp)
2732 {
2733   return ((CLzmaEnc *)pp)->writeEndMark;
2734 }
2735
2736
2737 SRes LzmaEnc_MemEncode(CLzmaEncHandle pp, Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
2738     int writeEndMark, ICompressProgress *progress, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2739 {
2740   SRes res;
2741   CLzmaEnc *p = (CLzmaEnc *)pp;
2742
2743   CLzmaEnc_SeqOutStreamBuf outStream;
2744
2745   outStream.vt.Write = SeqOutStreamBuf_Write;
2746   outStream.data = dest;
2747   outStream.rem = *destLen;
2748   outStream.overflow = False;
2749
2750   p->writeEndMark = writeEndMark;
2751   p->rc.outStream = &outStream.vt;
2752
2753   res = LzmaEnc_MemPrepare(pp, src, srcLen, 0, alloc, allocBig);
2754
2755   if (res == SZ_OK)
2756   {
2757     res = LzmaEnc_Encode2(p, progress);
2758     if (res == SZ_OK && p->nowPos64 != srcLen)
2759       res = SZ_ERROR_FAIL;
2760   }
2761
2762   *destLen -= outStream.rem;
2763   if (outStream.overflow)
2764     return SZ_ERROR_OUTPUT_EOF;
2765   return res;
2766 }
2767
2768
2769 SRes LzmaEncode(Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
2770     const CLzmaEncProps *props, Byte *propsEncoded, SizeT *propsSize, int writeEndMark,
2771     ICompressProgress *progress, ISzAllocPtr alloc, ISzAllocPtr allocBig)
2772 {
2773   CLzmaEnc *p = (CLzmaEnc *)LzmaEnc_Create(alloc);
2774   SRes res;
2775   if (!p)
2776     return SZ_ERROR_MEM;
2777
2778   res = LzmaEnc_SetProps(p, props);
2779   if (res == SZ_OK)
2780   {
2781     res = LzmaEnc_WriteProperties(p, propsEncoded, propsSize);
2782     if (res == SZ_OK)
2783       res = LzmaEnc_MemEncode(p, dest, destLen, src, srcLen,
2784           writeEndMark, progress, alloc, allocBig);
2785   }
2786
2787   LzmaEnc_Destroy(p, alloc, allocBig);
2788   return res;
2789 }