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