C/LzmaEnc.c

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