deps/lzma-16.04/C/LzmaEnc.c

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