deps/lzma-16.04/C/LzmaDec.c

   1 /* LzmaDec.c -- LZMA Decoder\r
   2 2016-05-16 : Igor Pavlov : Public domain */\r
   3 \r
   4 #include "Precomp.h"\r
   5 \r
   6 #include "LzmaDec.h"\r
   7 \r
   8 #include <string.h>\r
   9 \r
  10 #define kNumTopBits 24\r
  11 #define kTopValue ((UInt32)1 << kNumTopBits)\r
  12 \r
  13 #define kNumBitModelTotalBits 11\r
  14 #define kBitModelTotal (1 << kNumBitModelTotalBits)\r
  15 #define kNumMoveBits 5\r
  16 \r
  17 #define RC_INIT_SIZE 5\r
  18 \r
  19 #define NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | (*buf++); }\r
  20 \r
  21 #define IF_BIT_0(p) ttt = *(p); NORMALIZE; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound)\r
  22 #define UPDATE_0(p) range = bound; *(p) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits));\r
  23 #define UPDATE_1(p) range -= bound; code -= bound; *(p) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits));\r
  24 #define GET_BIT2(p, i, A0, A1) IF_BIT_0(p) \\r
  25   { UPDATE_0(p); i = (i + i); A0; } else \\r
  26   { UPDATE_1(p); i = (i + i) + 1; A1; }\r
  27 #define GET_BIT(p, i) GET_BIT2(p, i, ; , ;)\r
  28 \r
  29 #define TREE_GET_BIT(probs, i) { GET_BIT((probs + i), i); }\r
  30 #define TREE_DECODE(probs, limit, i) \\r
  31   { i = 1; do { TREE_GET_BIT(probs, i); } while (i < limit); i -= limit; }\r
  32 \r
  33 /* #define _LZMA_SIZE_OPT */\r
  34 \r
  35 #ifdef _LZMA_SIZE_OPT\r
  36 #define TREE_6_DECODE(probs, i) TREE_DECODE(probs, (1 << 6), i)\r
  37 #else\r
  38 #define TREE_6_DECODE(probs, i) \\r
  39   { i = 1; \\r
  40   TREE_GET_BIT(probs, i); \\r
  41   TREE_GET_BIT(probs, i); \\r
  42   TREE_GET_BIT(probs, i); \\r
  43   TREE_GET_BIT(probs, i); \\r
  44   TREE_GET_BIT(probs, i); \\r
  45   TREE_GET_BIT(probs, i); \\r
  46   i -= 0x40; }\r
  47 #endif\r
  48 \r
  49 #define NORMAL_LITER_DEC GET_BIT(prob + symbol, symbol)\r
  50 #define MATCHED_LITER_DEC \\r
  51   matchByte <<= 1; \\r
  52   bit = (matchByte & offs); \\r
  53   probLit = prob + offs + bit + symbol; \\r
  54   GET_BIT2(probLit, symbol, offs &= ~bit, offs &= bit)\r
  55 \r
  56 #define NORMALIZE_CHECK if (range < kTopValue) { if (buf >= bufLimit) return DUMMY_ERROR; range <<= 8; code = (code << 8) | (*buf++); }\r
  57 \r
  58 #define IF_BIT_0_CHECK(p) ttt = *(p); NORMALIZE_CHECK; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound)\r
  59 #define UPDATE_0_CHECK range = bound;\r
  60 #define UPDATE_1_CHECK range -= bound; code -= bound;\r
  61 #define GET_BIT2_CHECK(p, i, A0, A1) IF_BIT_0_CHECK(p) \\r
  62   { UPDATE_0_CHECK; i = (i + i); A0; } else \\r
  63   { UPDATE_1_CHECK; i = (i + i) + 1; A1; }\r
  64 #define GET_BIT_CHECK(p, i) GET_BIT2_CHECK(p, i, ; , ;)\r
  65 #define TREE_DECODE_CHECK(probs, limit, i) \\r
  66   { i = 1; do { GET_BIT_CHECK(probs + i, i) } while (i < limit); i -= limit; }\r
  67 \r
  68 \r
  69 #define kNumPosBitsMax 4\r
  70 #define kNumPosStatesMax (1 << kNumPosBitsMax)\r
  71 \r
  72 #define kLenNumLowBits 3\r
  73 #define kLenNumLowSymbols (1 << kLenNumLowBits)\r
  74 #define kLenNumMidBits 3\r
  75 #define kLenNumMidSymbols (1 << kLenNumMidBits)\r
  76 #define kLenNumHighBits 8\r
  77 #define kLenNumHighSymbols (1 << kLenNumHighBits)\r
  78 \r
  79 #define LenChoice 0\r
  80 #define LenChoice2 (LenChoice + 1)\r
  81 #define LenLow (LenChoice2 + 1)\r
  82 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))\r
  83 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))\r
  84 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)\r
  85 \r
  86 \r
  87 #define kNumStates 12\r
  88 #define kNumLitStates 7\r
  89 \r
  90 #define kStartPosModelIndex 4\r
  91 #define kEndPosModelIndex 14\r
  92 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))\r
  93 \r
  94 #define kNumPosSlotBits 6\r
  95 #define kNumLenToPosStates 4\r
  96 \r
  97 #define kNumAlignBits 4\r
  98 #define kAlignTableSize (1 << kNumAlignBits)\r
  99 \r
 100 #define kMatchMinLen 2\r
 101 #define kMatchSpecLenStart (kMatchMinLen + kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)\r
 102 \r
 103 #define IsMatch 0\r
 104 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))\r
 105 #define IsRepG0 (IsRep + kNumStates)\r
 106 #define IsRepG1 (IsRepG0 + kNumStates)\r
 107 #define IsRepG2 (IsRepG1 + kNumStates)\r
 108 #define IsRep0Long (IsRepG2 + kNumStates)\r
 109 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))\r
 110 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))\r
 111 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)\r
 112 #define LenCoder (Align + kAlignTableSize)\r
 113 #define RepLenCoder (LenCoder + kNumLenProbs)\r
 114 #define Literal (RepLenCoder + kNumLenProbs)\r
 115 \r
 116 #define LZMA_BASE_SIZE 1846\r
 117 #define LZMA_LIT_SIZE 0x300\r
 118 \r
 119 #if Literal != LZMA_BASE_SIZE\r
 120 StopCompilingDueBUG\r
 121 #endif\r
 122 \r
 123 #define LzmaProps_GetNumProbs(p) (Literal + ((UInt32)LZMA_LIT_SIZE << ((p)->lc + (p)->lp)))\r
 124 \r
 125 #define LZMA_DIC_MIN (1 << 12)\r
 126 \r
 127 /* First LZMA-symbol is always decoded.\r
 128 And it decodes new LZMA-symbols while (buf < bufLimit), but "buf" is without last normalization\r
 129 Out:\r
 130   Result:\r
 131     SZ_OK - OK\r
 132     SZ_ERROR_DATA - Error\r
 133   p->remainLen:\r
 134     < kMatchSpecLenStart : normal remain\r
 135     = kMatchSpecLenStart : finished\r
 136     = kMatchSpecLenStart + 1 : Flush marker (unused now)\r
 137     = kMatchSpecLenStart + 2 : State Init Marker (unused now)\r
 138 */\r
 139 \r
 140 static int MY_FAST_CALL LzmaDec_DecodeReal(CLzmaDec *p, SizeT limit, const Byte *bufLimit)\r
 141 {\r
 142   CLzmaProb *probs = p->probs;\r
 143 \r
 144   unsigned state = p->state;\r
 145   UInt32 rep0 = p->reps[0], rep1 = p->reps[1], rep2 = p->reps[2], rep3 = p->reps[3];\r
 146   unsigned pbMask = ((unsigned)1 << (p->prop.pb)) - 1;\r
 147   unsigned lpMask = ((unsigned)1 << (p->prop.lp)) - 1;\r
 148   unsigned lc = p->prop.lc;\r
 149 \r
 150   Byte *dic = p->dic;\r
 151   SizeT dicBufSize = p->dicBufSize;\r
 152   SizeT dicPos = p->dicPos;\r
 153   \r
 154   UInt32 processedPos = p->processedPos;\r
 155   UInt32 checkDicSize = p->checkDicSize;\r
 156   unsigned len = 0;\r
 157 \r
 158   const Byte *buf = p->buf;\r
 159   UInt32 range = p->range;\r
 160   UInt32 code = p->code;\r
 161 \r
 162   do\r
 163   {\r
 164     CLzmaProb *prob;\r
 165     UInt32 bound;\r
 166     unsigned ttt;\r
 167     unsigned posState = processedPos & pbMask;\r
 168 \r
 169     prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;\r
 170     IF_BIT_0(prob)\r
 171     {\r
 172       unsigned symbol;\r
 173       UPDATE_0(prob);\r
 174       prob = probs + Literal;\r
 175       if (processedPos != 0 || checkDicSize != 0)\r
 176         prob += ((UInt32)LZMA_LIT_SIZE * (((processedPos & lpMask) << lc) +\r
 177             (dic[(dicPos == 0 ? dicBufSize : dicPos) - 1] >> (8 - lc))));\r
 178       processedPos++;\r
 179 \r
 180       if (state < kNumLitStates)\r
 181       {\r
 182         state -= (state < 4) ? state : 3;\r
 183         symbol = 1;\r
 184         #ifdef _LZMA_SIZE_OPT\r
 185         do { NORMAL_LITER_DEC } while (symbol < 0x100);\r
 186         #else\r
 187         NORMAL_LITER_DEC\r
 188         NORMAL_LITER_DEC\r
 189         NORMAL_LITER_DEC\r
 190         NORMAL_LITER_DEC\r
 191         NORMAL_LITER_DEC\r
 192         NORMAL_LITER_DEC\r
 193         NORMAL_LITER_DEC\r
 194         NORMAL_LITER_DEC\r
 195         #endif\r
 196       }\r
 197       else\r
 198       {\r
 199         unsigned matchByte = dic[dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0)];\r
 200         unsigned offs = 0x100;\r
 201         state -= (state < 10) ? 3 : 6;\r
 202         symbol = 1;\r
 203         #ifdef _LZMA_SIZE_OPT\r
 204         do\r
 205         {\r
 206           unsigned bit;\r
 207           CLzmaProb *probLit;\r
 208           MATCHED_LITER_DEC\r
 209         }\r
 210         while (symbol < 0x100);\r
 211         #else\r
 212         {\r
 213           unsigned bit;\r
 214           CLzmaProb *probLit;\r
 215           MATCHED_LITER_DEC\r
 216           MATCHED_LITER_DEC\r
 217           MATCHED_LITER_DEC\r
 218           MATCHED_LITER_DEC\r
 219           MATCHED_LITER_DEC\r
 220           MATCHED_LITER_DEC\r
 221           MATCHED_LITER_DEC\r
 222           MATCHED_LITER_DEC\r
 223         }\r
 224         #endif\r
 225       }\r
 226 \r
 227       dic[dicPos++] = (Byte)symbol;\r
 228       continue;\r
 229     }\r
 230     \r
 231     {\r
 232       UPDATE_1(prob);\r
 233       prob = probs + IsRep + state;\r
 234       IF_BIT_0(prob)\r
 235       {\r
 236         UPDATE_0(prob);\r
 237         state += kNumStates;\r
 238         prob = probs + LenCoder;\r
 239       }\r
 240       else\r
 241       {\r
 242         UPDATE_1(prob);\r
 243         if (checkDicSize == 0 && processedPos == 0)\r
 244           return SZ_ERROR_DATA;\r
 245         prob = probs + IsRepG0 + state;\r
 246         IF_BIT_0(prob)\r
 247         {\r
 248           UPDATE_0(prob);\r
 249           prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;\r
 250           IF_BIT_0(prob)\r
 251           {\r
 252             UPDATE_0(prob);\r
 253             dic[dicPos] = dic[dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0)];\r
 254             dicPos++;\r
 255             processedPos++;\r
 256             state = state < kNumLitStates ? 9 : 11;\r
 257             continue;\r
 258           }\r
 259           UPDATE_1(prob);\r
 260         }\r
 261         else\r
 262         {\r
 263           UInt32 distance;\r
 264           UPDATE_1(prob);\r
 265           prob = probs + IsRepG1 + state;\r
 266           IF_BIT_0(prob)\r
 267           {\r
 268             UPDATE_0(prob);\r
 269             distance = rep1;\r
 270           }\r
 271           else\r
 272           {\r
 273             UPDATE_1(prob);\r
 274             prob = probs + IsRepG2 + state;\r
 275             IF_BIT_0(prob)\r
 276             {\r
 277               UPDATE_0(prob);\r
 278               distance = rep2;\r
 279             }\r
 280             else\r
 281             {\r
 282               UPDATE_1(prob);\r
 283               distance = rep3;\r
 284               rep3 = rep2;\r
 285             }\r
 286             rep2 = rep1;\r
 287           }\r
 288           rep1 = rep0;\r
 289           rep0 = distance;\r
 290         }\r
 291         state = state < kNumLitStates ? 8 : 11;\r
 292         prob = probs + RepLenCoder;\r
 293       }\r
 294       \r
 295       #ifdef _LZMA_SIZE_OPT\r
 296       {\r
 297         unsigned lim, offset;\r
 298         CLzmaProb *probLen = prob + LenChoice;\r
 299         IF_BIT_0(probLen)\r
 300         {\r
 301           UPDATE_0(probLen);\r
 302           probLen = prob + LenLow + (posState << kLenNumLowBits);\r
 303           offset = 0;\r
 304           lim = (1 << kLenNumLowBits);\r
 305         }\r
 306         else\r
 307         {\r
 308           UPDATE_1(probLen);\r
 309           probLen = prob + LenChoice2;\r
 310           IF_BIT_0(probLen)\r
 311           {\r
 312             UPDATE_0(probLen);\r
 313             probLen = prob + LenMid + (posState << kLenNumMidBits);\r
 314             offset = kLenNumLowSymbols;\r
 315             lim = (1 << kLenNumMidBits);\r
 316           }\r
 317           else\r
 318           {\r
 319             UPDATE_1(probLen);\r
 320             probLen = prob + LenHigh;\r
 321             offset = kLenNumLowSymbols + kLenNumMidSymbols;\r
 322             lim = (1 << kLenNumHighBits);\r
 323           }\r
 324         }\r
 325         TREE_DECODE(probLen, lim, len);\r
 326         len += offset;\r
 327       }\r
 328       #else\r
 329       {\r
 330         CLzmaProb *probLen = prob + LenChoice;\r
 331         IF_BIT_0(probLen)\r
 332         {\r
 333           UPDATE_0(probLen);\r
 334           probLen = prob + LenLow + (posState << kLenNumLowBits);\r
 335           len = 1;\r
 336           TREE_GET_BIT(probLen, len);\r
 337           TREE_GET_BIT(probLen, len);\r
 338           TREE_GET_BIT(probLen, len);\r
 339           len -= 8;\r
 340         }\r
 341         else\r
 342         {\r
 343           UPDATE_1(probLen);\r
 344           probLen = prob + LenChoice2;\r
 345           IF_BIT_0(probLen)\r
 346           {\r
 347             UPDATE_0(probLen);\r
 348             probLen = prob + LenMid + (posState << kLenNumMidBits);\r
 349             len = 1;\r
 350             TREE_GET_BIT(probLen, len);\r
 351             TREE_GET_BIT(probLen, len);\r
 352             TREE_GET_BIT(probLen, len);\r
 353           }\r
 354           else\r
 355           {\r
 356             UPDATE_1(probLen);\r
 357             probLen = prob + LenHigh;\r
 358             TREE_DECODE(probLen, (1 << kLenNumHighBits), len);\r
 359             len += kLenNumLowSymbols + kLenNumMidSymbols;\r
 360           }\r
 361         }\r
 362       }\r
 363       #endif\r
 364 \r
 365       if (state >= kNumStates)\r
 366       {\r
 367         UInt32 distance;\r
 368         prob = probs + PosSlot +\r
 369             ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits);\r
 370         TREE_6_DECODE(prob, distance);\r
 371         if (distance >= kStartPosModelIndex)\r
 372         {\r
 373           unsigned posSlot = (unsigned)distance;\r
 374           unsigned numDirectBits = (unsigned)(((distance >> 1) - 1));\r
 375           distance = (2 | (distance & 1));\r
 376           if (posSlot < kEndPosModelIndex)\r
 377           {\r
 378             distance <<= numDirectBits;\r
 379             prob = probs + SpecPos + distance - posSlot - 1;\r
 380             {\r
 381               UInt32 mask = 1;\r
 382               unsigned i = 1;\r
 383               do\r
 384               {\r
 385                 GET_BIT2(prob + i, i, ; , distance |= mask);\r
 386                 mask <<= 1;\r
 387               }\r
 388               while (--numDirectBits != 0);\r
 389             }\r
 390           }\r
 391           else\r
 392           {\r
 393             numDirectBits -= kNumAlignBits;\r
 394             do\r
 395             {\r
 396               NORMALIZE\r
 397               range >>= 1;\r
 398               \r
 399               {\r
 400                 UInt32 t;\r
 401                 code -= range;\r
 402                 t = (0 - ((UInt32)code >> 31)); /* (UInt32)((Int32)code >> 31) */\r
 403                 distance = (distance << 1) + (t + 1);\r
 404                 code += range & t;\r
 405               }\r
 406               /*\r
 407               distance <<= 1;\r
 408               if (code >= range)\r
 409               {\r
 410                 code -= range;\r
 411                 distance |= 1;\r
 412               }\r
 413               */\r
 414             }\r
 415             while (--numDirectBits != 0);\r
 416             prob = probs + Align;\r
 417             distance <<= kNumAlignBits;\r
 418             {\r
 419               unsigned i = 1;\r
 420               GET_BIT2(prob + i, i, ; , distance |= 1);\r
 421               GET_BIT2(prob + i, i, ; , distance |= 2);\r
 422               GET_BIT2(prob + i, i, ; , distance |= 4);\r
 423               GET_BIT2(prob + i, i, ; , distance |= 8);\r
 424             }\r
 425             if (distance == (UInt32)0xFFFFFFFF)\r
 426             {\r
 427               len += kMatchSpecLenStart;\r
 428               state -= kNumStates;\r
 429               break;\r
 430             }\r
 431           }\r
 432         }\r
 433         \r
 434         rep3 = rep2;\r
 435         rep2 = rep1;\r
 436         rep1 = rep0;\r
 437         rep0 = distance + 1;\r
 438         if (checkDicSize == 0)\r
 439         {\r
 440           if (distance >= processedPos)\r
 441           {\r
 442             p->dicPos = dicPos;\r
 443             return SZ_ERROR_DATA;\r
 444           }\r
 445         }\r
 446         else if (distance >= checkDicSize)\r
 447         {\r
 448           p->dicPos = dicPos;\r
 449           return SZ_ERROR_DATA;\r
 450         }\r
 451         state = (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3;\r
 452       }\r
 453 \r
 454       len += kMatchMinLen;\r
 455 \r
 456       {\r
 457         SizeT rem;\r
 458         unsigned curLen;\r
 459         SizeT pos;\r
 460         \r
 461         if ((rem = limit - dicPos) == 0)\r
 462         {\r
 463           p->dicPos = dicPos;\r
 464           return SZ_ERROR_DATA;\r
 465         }\r
 466         \r
 467         curLen = ((rem < len) ? (unsigned)rem : len);\r
 468         pos = dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0);\r
 469 \r
 470         processedPos += curLen;\r
 471 \r
 472         len -= curLen;\r
 473         if (curLen <= dicBufSize - pos)\r
 474         {\r
 475           Byte *dest = dic + dicPos;\r
 476           ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos;\r
 477           const Byte *lim = dest + curLen;\r
 478           dicPos += curLen;\r
 479           do\r
 480             *(dest) = (Byte)*(dest + src);\r
 481           while (++dest != lim);\r
 482         }\r
 483         else\r
 484         {\r
 485           do\r
 486           {\r
 487             dic[dicPos++] = dic[pos];\r
 488             if (++pos == dicBufSize)\r
 489               pos = 0;\r
 490           }\r
 491           while (--curLen != 0);\r
 492         }\r
 493       }\r
 494     }\r
 495   }\r
 496   while (dicPos < limit && buf < bufLimit);\r
 497 \r
 498   NORMALIZE;\r
 499   \r
 500   p->buf = buf;\r
 501   p->range = range;\r
 502   p->code = code;\r
 503   p->remainLen = len;\r
 504   p->dicPos = dicPos;\r
 505   p->processedPos = processedPos;\r
 506   p->reps[0] = rep0;\r
 507   p->reps[1] = rep1;\r
 508   p->reps[2] = rep2;\r
 509   p->reps[3] = rep3;\r
 510   p->state = state;\r
 511 \r
 512   return SZ_OK;\r
 513 }\r
 514 \r
 515 static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, SizeT limit)\r
 516 {\r
 517   if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart)\r
 518   {\r
 519     Byte *dic = p->dic;\r
 520     SizeT dicPos = p->dicPos;\r
 521     SizeT dicBufSize = p->dicBufSize;\r
 522     unsigned len = p->remainLen;\r
 523     SizeT rep0 = p->reps[0]; /* we use SizeT to avoid the BUG of VC14 for AMD64 */\r
 524     SizeT rem = limit - dicPos;\r
 525     if (rem < len)\r
 526       len = (unsigned)(rem);\r
 527 \r
 528     if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len)\r
 529       p->checkDicSize = p->prop.dicSize;\r
 530 \r
 531     p->processedPos += len;\r
 532     p->remainLen -= len;\r
 533     while (len != 0)\r
 534     {\r
 535       len--;\r
 536       dic[dicPos] = dic[dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0)];\r
 537       dicPos++;\r
 538     }\r
 539     p->dicPos = dicPos;\r
 540   }\r
 541 }\r
 542 \r
 543 static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, SizeT limit, const Byte *bufLimit)\r
 544 {\r
 545   do\r
 546   {\r
 547     SizeT limit2 = limit;\r
 548     if (p->checkDicSize == 0)\r
 549     {\r
 550       UInt32 rem = p->prop.dicSize - p->processedPos;\r
 551       if (limit - p->dicPos > rem)\r
 552         limit2 = p->dicPos + rem;\r
 553     }\r
 554     \r
 555     RINOK(LzmaDec_DecodeReal(p, limit2, bufLimit));\r
 556     \r
 557     if (p->checkDicSize == 0 && p->processedPos >= p->prop.dicSize)\r
 558       p->checkDicSize = p->prop.dicSize;\r
 559     \r
 560     LzmaDec_WriteRem(p, limit);\r
 561   }\r
 562   while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart);\r
 563 \r
 564   if (p->remainLen > kMatchSpecLenStart)\r
 565     p->remainLen = kMatchSpecLenStart;\r
 566 \r
 567   return 0;\r
 568 }\r
 569 \r
 570 typedef enum\r
 571 {\r
 572   DUMMY_ERROR, /* unexpected end of input stream */\r
 573   DUMMY_LIT,\r
 574   DUMMY_MATCH,\r
 575   DUMMY_REP\r
 576 } ELzmaDummy;\r
 577 \r
 578 static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const Byte *buf, SizeT inSize)\r
 579 {\r
 580   UInt32 range = p->range;\r
 581   UInt32 code = p->code;\r
 582   const Byte *bufLimit = buf + inSize;\r
 583   const CLzmaProb *probs = p->probs;\r
 584   unsigned state = p->state;\r
 585   ELzmaDummy res;\r
 586 \r
 587   {\r
 588     const CLzmaProb *prob;\r
 589     UInt32 bound;\r
 590     unsigned ttt;\r
 591     unsigned posState = (p->processedPos) & ((1 << p->prop.pb) - 1);\r
 592 \r
 593     prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;\r
 594     IF_BIT_0_CHECK(prob)\r
 595     {\r
 596       UPDATE_0_CHECK\r
 597 \r
 598       /* if (bufLimit - buf >= 7) return DUMMY_LIT; */\r
 599 \r
 600       prob = probs + Literal;\r
 601       if (p->checkDicSize != 0 || p->processedPos != 0)\r
 602         prob += ((UInt32)LZMA_LIT_SIZE *\r
 603             ((((p->processedPos) & ((1 << (p->prop.lp)) - 1)) << p->prop.lc) +\r
 604             (p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >> (8 - p->prop.lc))));\r
 605 \r
 606       if (state < kNumLitStates)\r
 607       {\r
 608         unsigned symbol = 1;\r
 609         do { GET_BIT_CHECK(prob + symbol, symbol) } while (symbol < 0x100);\r
 610       }\r
 611       else\r
 612       {\r
 613         unsigned matchByte = p->dic[p->dicPos - p->reps[0] +\r
 614             (p->dicPos < p->reps[0] ? p->dicBufSize : 0)];\r
 615         unsigned offs = 0x100;\r
 616         unsigned symbol = 1;\r
 617         do\r
 618         {\r
 619           unsigned bit;\r
 620           const CLzmaProb *probLit;\r
 621           matchByte <<= 1;\r
 622           bit = (matchByte & offs);\r
 623           probLit = prob + offs + bit + symbol;\r
 624           GET_BIT2_CHECK(probLit, symbol, offs &= ~bit, offs &= bit)\r
 625         }\r
 626         while (symbol < 0x100);\r
 627       }\r
 628       res = DUMMY_LIT;\r
 629     }\r
 630     else\r
 631     {\r
 632       unsigned len;\r
 633       UPDATE_1_CHECK;\r
 634 \r
 635       prob = probs + IsRep + state;\r
 636       IF_BIT_0_CHECK(prob)\r
 637       {\r
 638         UPDATE_0_CHECK;\r
 639         state = 0;\r
 640         prob = probs + LenCoder;\r
 641         res = DUMMY_MATCH;\r
 642       }\r
 643       else\r
 644       {\r
 645         UPDATE_1_CHECK;\r
 646         res = DUMMY_REP;\r
 647         prob = probs + IsRepG0 + state;\r
 648         IF_BIT_0_CHECK(prob)\r
 649         {\r
 650           UPDATE_0_CHECK;\r
 651           prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;\r
 652           IF_BIT_0_CHECK(prob)\r
 653           {\r
 654             UPDATE_0_CHECK;\r
 655             NORMALIZE_CHECK;\r
 656             return DUMMY_REP;\r
 657           }\r
 658           else\r
 659           {\r
 660             UPDATE_1_CHECK;\r
 661           }\r
 662         }\r
 663         else\r
 664         {\r
 665           UPDATE_1_CHECK;\r
 666           prob = probs + IsRepG1 + state;\r
 667           IF_BIT_0_CHECK(prob)\r
 668           {\r
 669             UPDATE_0_CHECK;\r
 670           }\r
 671           else\r
 672           {\r
 673             UPDATE_1_CHECK;\r
 674             prob = probs + IsRepG2 + state;\r
 675             IF_BIT_0_CHECK(prob)\r
 676             {\r
 677               UPDATE_0_CHECK;\r
 678             }\r
 679             else\r
 680             {\r
 681               UPDATE_1_CHECK;\r
 682             }\r
 683           }\r
 684         }\r
 685         state = kNumStates;\r
 686         prob = probs + RepLenCoder;\r
 687       }\r
 688       {\r
 689         unsigned limit, offset;\r
 690         const CLzmaProb *probLen = prob + LenChoice;\r
 691         IF_BIT_0_CHECK(probLen)\r
 692         {\r
 693           UPDATE_0_CHECK;\r
 694           probLen = prob + LenLow + (posState << kLenNumLowBits);\r
 695           offset = 0;\r
 696           limit = 1 << kLenNumLowBits;\r
 697         }\r
 698         else\r
 699         {\r
 700           UPDATE_1_CHECK;\r
 701           probLen = prob + LenChoice2;\r
 702           IF_BIT_0_CHECK(probLen)\r
 703           {\r
 704             UPDATE_0_CHECK;\r
 705             probLen = prob + LenMid + (posState << kLenNumMidBits);\r
 706             offset = kLenNumLowSymbols;\r
 707             limit = 1 << kLenNumMidBits;\r
 708           }\r
 709           else\r
 710           {\r
 711             UPDATE_1_CHECK;\r
 712             probLen = prob + LenHigh;\r
 713             offset = kLenNumLowSymbols + kLenNumMidSymbols;\r
 714             limit = 1 << kLenNumHighBits;\r
 715           }\r
 716         }\r
 717         TREE_DECODE_CHECK(probLen, limit, len);\r
 718         len += offset;\r
 719       }\r
 720 \r
 721       if (state < 4)\r
 722       {\r
 723         unsigned posSlot;\r
 724         prob = probs + PosSlot +\r
 725             ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<\r
 726             kNumPosSlotBits);\r
 727         TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot);\r
 728         if (posSlot >= kStartPosModelIndex)\r
 729         {\r
 730           unsigned numDirectBits = ((posSlot >> 1) - 1);\r
 731 \r
 732           /* if (bufLimit - buf >= 8) return DUMMY_MATCH; */\r
 733 \r
 734           if (posSlot < kEndPosModelIndex)\r
 735           {\r
 736             prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits) - posSlot - 1;\r
 737           }\r
 738           else\r
 739           {\r
 740             numDirectBits -= kNumAlignBits;\r
 741             do\r
 742             {\r
 743               NORMALIZE_CHECK\r
 744               range >>= 1;\r
 745               code -= range & (((code - range) >> 31) - 1);\r
 746               /* if (code >= range) code -= range; */\r
 747             }\r
 748             while (--numDirectBits != 0);\r
 749             prob = probs + Align;\r
 750             numDirectBits = kNumAlignBits;\r
 751           }\r
 752           {\r
 753             unsigned i = 1;\r
 754             do\r
 755             {\r
 756               GET_BIT_CHECK(prob + i, i);\r
 757             }\r
 758             while (--numDirectBits != 0);\r
 759           }\r
 760         }\r
 761       }\r
 762     }\r
 763   }\r
 764   NORMALIZE_CHECK;\r
 765   return res;\r
 766 }\r
 767 \r
 768 \r
 769 void LzmaDec_InitDicAndState(CLzmaDec *p, Bool initDic, Bool initState)\r
 770 {\r
 771   p->needFlush = 1;\r
 772   p->remainLen = 0;\r
 773   p->tempBufSize = 0;\r
 774 \r
 775   if (initDic)\r
 776   {\r
 777     p->processedPos = 0;\r
 778     p->checkDicSize = 0;\r
 779     p->needInitState = 1;\r
 780   }\r
 781   if (initState)\r
 782     p->needInitState = 1;\r
 783 }\r
 784 \r
 785 void LzmaDec_Init(CLzmaDec *p)\r
 786 {\r
 787   p->dicPos = 0;\r
 788   LzmaDec_InitDicAndState(p, True, True);\r
 789 }\r
 790 \r
 791 static void LzmaDec_InitStateReal(CLzmaDec *p)\r
 792 {\r
 793   SizeT numProbs = LzmaProps_GetNumProbs(&p->prop);\r
 794   SizeT i;\r
 795   CLzmaProb *probs = p->probs;\r
 796   for (i = 0; i < numProbs; i++)\r
 797     probs[i] = kBitModelTotal >> 1;\r
 798   p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1;\r
 799   p->state = 0;\r
 800   p->needInitState = 0;\r
 801 }\r
 802 \r
 803 SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit, const Byte *src, SizeT *srcLen,\r
 804     ELzmaFinishMode finishMode, ELzmaStatus *status)\r
 805 {\r
 806   SizeT inSize = *srcLen;\r
 807   (*srcLen) = 0;\r
 808   LzmaDec_WriteRem(p, dicLimit);\r
 809   \r
 810   *status = LZMA_STATUS_NOT_SPECIFIED;\r
 811 \r
 812   while (p->remainLen != kMatchSpecLenStart)\r
 813   {\r
 814       int checkEndMarkNow;\r
 815 \r
 816       if (p->needFlush)\r
 817       {\r
 818         for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--)\r
 819           p->tempBuf[p->tempBufSize++] = *src++;\r
 820         if (p->tempBufSize < RC_INIT_SIZE)\r
 821         {\r
 822           *status = LZMA_STATUS_NEEDS_MORE_INPUT;\r
 823           return SZ_OK;\r
 824         }\r
 825         if (p->tempBuf[0] != 0)\r
 826           return SZ_ERROR_DATA;\r
 827         p->code =\r
 828               ((UInt32)p->tempBuf[1] << 24)\r
 829             | ((UInt32)p->tempBuf[2] << 16)\r
 830             | ((UInt32)p->tempBuf[3] << 8)\r
 831             | ((UInt32)p->tempBuf[4]);\r
 832         p->range = 0xFFFFFFFF;\r
 833         p->needFlush = 0;\r
 834         p->tempBufSize = 0;\r
 835       }\r
 836 \r
 837       checkEndMarkNow = 0;\r
 838       if (p->dicPos >= dicLimit)\r
 839       {\r
 840         if (p->remainLen == 0 && p->code == 0)\r
 841         {\r
 842           *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK;\r
 843           return SZ_OK;\r
 844         }\r
 845         if (finishMode == LZMA_FINISH_ANY)\r
 846         {\r
 847           *status = LZMA_STATUS_NOT_FINISHED;\r
 848           return SZ_OK;\r
 849         }\r
 850         if (p->remainLen != 0)\r
 851         {\r
 852           *status = LZMA_STATUS_NOT_FINISHED;\r
 853           return SZ_ERROR_DATA;\r
 854         }\r
 855         checkEndMarkNow = 1;\r
 856       }\r
 857 \r
 858       if (p->needInitState)\r
 859         LzmaDec_InitStateReal(p);\r
 860   \r
 861       if (p->tempBufSize == 0)\r
 862       {\r
 863         SizeT processed;\r
 864         const Byte *bufLimit;\r
 865         if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)\r
 866         {\r
 867           int dummyRes = LzmaDec_TryDummy(p, src, inSize);\r
 868           if (dummyRes == DUMMY_ERROR)\r
 869           {\r
 870             memcpy(p->tempBuf, src, inSize);\r
 871             p->tempBufSize = (unsigned)inSize;\r
 872             (*srcLen) += inSize;\r
 873             *status = LZMA_STATUS_NEEDS_MORE_INPUT;\r
 874             return SZ_OK;\r
 875           }\r
 876           if (checkEndMarkNow && dummyRes != DUMMY_MATCH)\r
 877           {\r
 878             *status = LZMA_STATUS_NOT_FINISHED;\r
 879             return SZ_ERROR_DATA;\r
 880           }\r
 881           bufLimit = src;\r
 882         }\r
 883         else\r
 884           bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX;\r
 885         p->buf = src;\r
 886         if (LzmaDec_DecodeReal2(p, dicLimit, bufLimit) != 0)\r
 887           return SZ_ERROR_DATA;\r
 888         processed = (SizeT)(p->buf - src);\r
 889         (*srcLen) += processed;\r
 890         src += processed;\r
 891         inSize -= processed;\r
 892       }\r
 893       else\r
 894       {\r
 895         unsigned rem = p->tempBufSize, lookAhead = 0;\r
 896         while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize)\r
 897           p->tempBuf[rem++] = src[lookAhead++];\r
 898         p->tempBufSize = rem;\r
 899         if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)\r
 900         {\r
 901           int dummyRes = LzmaDec_TryDummy(p, p->tempBuf, rem);\r
 902           if (dummyRes == DUMMY_ERROR)\r
 903           {\r
 904             (*srcLen) += lookAhead;\r
 905             *status = LZMA_STATUS_NEEDS_MORE_INPUT;\r
 906             return SZ_OK;\r
 907           }\r
 908           if (checkEndMarkNow && dummyRes != DUMMY_MATCH)\r
 909           {\r
 910             *status = LZMA_STATUS_NOT_FINISHED;\r
 911             return SZ_ERROR_DATA;\r
 912           }\r
 913         }\r
 914         p->buf = p->tempBuf;\r
 915         if (LzmaDec_DecodeReal2(p, dicLimit, p->buf) != 0)\r
 916           return SZ_ERROR_DATA;\r
 917         \r
 918         {\r
 919           unsigned kkk = (unsigned)(p->buf - p->tempBuf);\r
 920           if (rem < kkk)\r
 921             return SZ_ERROR_FAIL; /* some internal error */\r
 922           rem -= kkk;\r
 923           if (lookAhead < rem)\r
 924             return SZ_ERROR_FAIL; /* some internal error */\r
 925           lookAhead -= rem;\r
 926         }\r
 927         (*srcLen) += lookAhead;\r
 928         src += lookAhead;\r
 929         inSize -= lookAhead;\r
 930         p->tempBufSize = 0;\r
 931       }\r
 932   }\r
 933   if (p->code == 0)\r
 934     *status = LZMA_STATUS_FINISHED_WITH_MARK;\r
 935   return (p->code == 0) ? SZ_OK : SZ_ERROR_DATA;\r
 936 }\r
 937 \r
 938 SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status)\r
 939 {\r
 940   SizeT outSize = *destLen;\r
 941   SizeT inSize = *srcLen;\r
 942   *srcLen = *destLen = 0;\r
 943   for (;;)\r
 944   {\r
 945     SizeT inSizeCur = inSize, outSizeCur, dicPos;\r
 946     ELzmaFinishMode curFinishMode;\r
 947     SRes res;\r
 948     if (p->dicPos == p->dicBufSize)\r
 949       p->dicPos = 0;\r
 950     dicPos = p->dicPos;\r
 951     if (outSize > p->dicBufSize - dicPos)\r
 952     {\r
 953       outSizeCur = p->dicBufSize;\r
 954       curFinishMode = LZMA_FINISH_ANY;\r
 955     }\r
 956     else\r
 957     {\r
 958       outSizeCur = dicPos + outSize;\r
 959       curFinishMode = finishMode;\r
 960     }\r
 961 \r
 962     res = LzmaDec_DecodeToDic(p, outSizeCur, src, &inSizeCur, curFinishMode, status);\r
 963     src += inSizeCur;\r
 964     inSize -= inSizeCur;\r
 965     *srcLen += inSizeCur;\r
 966     outSizeCur = p->dicPos - dicPos;\r
 967     memcpy(dest, p->dic + dicPos, outSizeCur);\r
 968     dest += outSizeCur;\r
 969     outSize -= outSizeCur;\r
 970     *destLen += outSizeCur;\r
 971     if (res != 0)\r
 972       return res;\r
 973     if (outSizeCur == 0 || outSize == 0)\r
 974       return SZ_OK;\r
 975   }\r
 976 }\r
 977 \r
 978 void LzmaDec_FreeProbs(CLzmaDec *p, ISzAlloc *alloc)\r
 979 {\r
 980   alloc->Free(alloc, p->probs);\r
 981   p->probs = NULL;\r
 982 }\r
 983 \r
 984 static void LzmaDec_FreeDict(CLzmaDec *p, ISzAlloc *alloc)\r
 985 {\r
 986   alloc->Free(alloc, p->dic);\r
 987   p->dic = NULL;\r
 988 }\r
 989 \r
 990 void LzmaDec_Free(CLzmaDec *p, ISzAlloc *alloc)\r
 991 {\r
 992   LzmaDec_FreeProbs(p, alloc);\r
 993   LzmaDec_FreeDict(p, alloc);\r
 994 }\r
 995 \r
 996 SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size)\r
 997 {\r
 998   UInt32 dicSize;\r
 999   Byte d;\r
1000   \r
1001   if (size < LZMA_PROPS_SIZE)\r
1002     return SZ_ERROR_UNSUPPORTED;\r
1003   else\r
1004     dicSize = data[1] | ((UInt32)data[2] << 8) | ((UInt32)data[3] << 16) | ((UInt32)data[4] << 24);\r
1005  \r
1006   if (dicSize < LZMA_DIC_MIN)\r
1007     dicSize = LZMA_DIC_MIN;\r
1008   p->dicSize = dicSize;\r
1009 \r
1010   d = data[0];\r
1011   if (d >= (9 * 5 * 5))\r
1012     return SZ_ERROR_UNSUPPORTED;\r
1013 \r
1014   p->lc = d % 9;\r
1015   d /= 9;\r
1016   p->pb = d / 5;\r
1017   p->lp = d % 5;\r
1018 \r
1019   return SZ_OK;\r
1020 }\r
1021 \r
1022 static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew, ISzAlloc *alloc)\r
1023 {\r
1024   UInt32 numProbs = LzmaProps_GetNumProbs(propNew);\r
1025   if (!p->probs || numProbs != p->numProbs)\r
1026   {\r
1027     LzmaDec_FreeProbs(p, alloc);\r
1028     p->probs = (CLzmaProb *)alloc->Alloc(alloc, numProbs * sizeof(CLzmaProb));\r
1029     p->numProbs = numProbs;\r
1030     if (!p->probs)\r
1031       return SZ_ERROR_MEM;\r
1032   }\r
1033   return SZ_OK;\r
1034 }\r
1035 \r
1036 SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)\r
1037 {\r
1038   CLzmaProps propNew;\r
1039   RINOK(LzmaProps_Decode(&propNew, props, propsSize));\r
1040   RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));\r
1041   p->prop = propNew;\r
1042   return SZ_OK;\r
1043 }\r
1044 \r
1045 SRes LzmaDec_Allocate(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)\r
1046 {\r
1047   CLzmaProps propNew;\r
1048   SizeT dicBufSize;\r
1049   RINOK(LzmaProps_Decode(&propNew, props, propsSize));\r
1050   RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));\r
1051 \r
1052   {\r
1053     UInt32 dictSize = propNew.dicSize;\r
1054     SizeT mask = ((UInt32)1 << 12) - 1;\r
1055          if (dictSize >= ((UInt32)1 << 30)) mask = ((UInt32)1 << 22) - 1;\r
1056     else if (dictSize >= ((UInt32)1 << 22)) mask = ((UInt32)1 << 20) - 1;;\r
1057     dicBufSize = ((SizeT)dictSize + mask) & ~mask;\r
1058     if (dicBufSize < dictSize)\r
1059       dicBufSize = dictSize;\r
1060   }\r
1061 \r
1062   if (!p->dic || dicBufSize != p->dicBufSize)\r
1063   {\r
1064     LzmaDec_FreeDict(p, alloc);\r
1065     p->dic = (Byte *)alloc->Alloc(alloc, dicBufSize);\r
1066     if (!p->dic)\r
1067     {\r
1068       LzmaDec_FreeProbs(p, alloc);\r
1069       return SZ_ERROR_MEM;\r
1070     }\r
1071   }\r
1072   p->dicBufSize = dicBufSize;\r
1073   p->prop = propNew;\r
1074   return SZ_OK;\r
1075 }\r
1076 \r
1077 SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,\r
1078     const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode,\r
1079     ELzmaStatus *status, ISzAlloc *alloc)\r
1080 {\r
1081   CLzmaDec p;\r
1082   SRes res;\r
1083   SizeT outSize = *destLen, inSize = *srcLen;\r
1084   *destLen = *srcLen = 0;\r
1085   *status = LZMA_STATUS_NOT_SPECIFIED;\r
1086   if (inSize < RC_INIT_SIZE)\r
1087     return SZ_ERROR_INPUT_EOF;\r
1088   LzmaDec_Construct(&p);\r
1089   RINOK(LzmaDec_AllocateProbs(&p, propData, propSize, alloc));\r
1090   p.dic = dest;\r
1091   p.dicBufSize = outSize;\r
1092   LzmaDec_Init(&p);\r
1093   *srcLen = inSize;\r
1094   res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status);\r
1095   *destLen = p.dicPos;\r
1096   if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT)\r
1097     res = SZ_ERROR_INPUT_EOF;\r
1098   LzmaDec_FreeProbs(&p, alloc);\r
1099   return res;\r
1100 }\r