deps/libchdr/deps/lzma-24.05/src/LzmaEnc.c

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