util/cbfstool/lzma/C/7zip/Decompress/LzmaDecode.c

   1 /*
   2   LzmaDecode.c
   3   LZMA Decoder (optimized for Speed version)
   4
   5   LZMA SDK 4.22 Copyright (c) 1999-2005 Igor Pavlov (2005-06-10)
   6   http://www.7-zip.org/
   7
   8   LZMA SDK is licensed under two licenses:
   9   1) GNU Lesser General Public License (GNU LGPL)
  10   2) Common Public License (CPL)
  11   It means that you can select one of these two licenses and
  12   follow rules of that license.
  13
  14   SPECIAL EXCEPTION:
  15   Igor Pavlov, as the author of this Code, expressly permits you to
  16   statically or dynamically link your Code (or bind by name) to the
  17   interfaces of this file without subjecting your linked Code to the
  18   terms of the CPL or GNU LGPL. Any modifications or additions
  19   to this file, however, are subject to the LGPL or CPL terms.
  20 */
  21
  22 #include "LzmaDecode.h"
  23
  24 #ifndef Byte
  25 #define Byte unsigned char
  26 #endif
  27
  28 #define kNumTopBits 24
  29 #define kTopValue ((UInt32)1 << kNumTopBits)
  30
  31 #define kNumBitModelTotalBits 11
  32 #define kBitModelTotal (1 << kNumBitModelTotalBits)
  33 #define kNumMoveBits 5
  34
  35 #define RC_READ_BYTE (*Buffer++)
  36
  37 #define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \
  38   { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }}
  39
  40 #ifdef _LZMA_IN_CB
  41
  42 #define RC_TEST { if (Buffer == BufferLim) \
  43   { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) return result; \
  44   BufferLim = Buffer + size; if (size == 0) return LZMA_RESULT_DATA_ERROR; }}
  45
  46 #define RC_INIT Buffer = BufferLim = 0; RC_INIT2
  47
  48 #else
  49
  50 #define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
  51
  52 #define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
  53
  54 #endif
  55
  56 #define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
  57
  58 #define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)
  59 #define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;
  60 #define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;
  61
  62 #define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \
  63   { UpdateBit0(p); mi <<= 1; A0; } else \
  64   { UpdateBit1(p); mi = (mi + mi) + 1; A1; }
  65
  66 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
  67
  68 #define RangeDecoderBitTreeDecode(probs, numLevels, res) \
  69   { int i = numLevels; res = 1; \
  70   do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \
  71   res -= (1 << numLevels); }
  72
  73
  74 #define kNumPosBitsMax 4
  75 #define kNumPosStatesMax (1 << kNumPosBitsMax)
  76
  77 #define kLenNumLowBits 3
  78 #define kLenNumLowSymbols (1 << kLenNumLowBits)
  79 #define kLenNumMidBits 3
  80 #define kLenNumMidSymbols (1 << kLenNumMidBits)
  81 #define kLenNumHighBits 8
  82 #define kLenNumHighSymbols (1 << kLenNumHighBits)
  83
  84 #define LenChoice 0
  85 #define LenChoice2 (LenChoice + 1)
  86 #define LenLow (LenChoice2 + 1)
  87 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
  88 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
  89 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
  90
  91
  92 #define kNumStates 12
  93 #define kNumLitStates 7
  94
  95 #define kStartPosModelIndex 4
  96 #define kEndPosModelIndex 14
  97 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
  98
  99 #define kNumPosSlotBits 6
 100 #define kNumLenToPosStates 4
 101
 102 #define kNumAlignBits 4
 103 #define kAlignTableSize (1 << kNumAlignBits)
 104
 105 #define kMatchMinLen 2
 106
 107 #define IsMatch 0
 108 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
 109 #define IsRepG0 (IsRep + kNumStates)
 110 #define IsRepG1 (IsRepG0 + kNumStates)
 111 #define IsRepG2 (IsRepG1 + kNumStates)
 112 #define IsRep0Long (IsRepG2 + kNumStates)
 113 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
 114 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
 115 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
 116 #define LenCoder (Align + kAlignTableSize)
 117 #define RepLenCoder (LenCoder + kNumLenProbs)
 118 #define Literal (RepLenCoder + kNumLenProbs)
 119
 120 #if Literal != LZMA_BASE_SIZE
 121 StopCompilingDueBUG
 122 #endif
 123
 124 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
 125 {
 126   unsigned char prop0;
 127   if (size < LZMA_PROPERTIES_SIZE)
 128     return LZMA_RESULT_DATA_ERROR;
 129   prop0 = propsData[0];
 130   if (prop0 >= (9 * 5 * 5))
 131     return LZMA_RESULT_DATA_ERROR;
 132   {
 133     for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
 134     for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
 135     propsRes->lc = prop0;
 136     /*
 137     unsigned char remainder = (unsigned char)(prop0 / 9);
 138     propsRes->lc = prop0 % 9;
 139     propsRes->pb = remainder / 5;
 140     propsRes->lp = remainder % 5;
 141     */
 142   }
 143
 144   #ifdef _LZMA_OUT_READ
 145   {
 146     int i;
 147     propsRes->DictionarySize = 0;
 148     for (i = 0; i < 4; i++)
 149       propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);
 150     if (propsRes->DictionarySize == 0)
 151       propsRes->DictionarySize = 1;
 152   }
 153   #endif
 154   return LZMA_RESULT_OK;
 155 }
 156
 157 #define kLzmaStreamWasFinishedId (-1)
 158
 159 int LzmaDecode(CLzmaDecoderState *vs,
 160     #ifdef _LZMA_IN_CB
 161     ILzmaInCallback *InCallback,
 162     #else
 163     const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
 164     #endif
 165     unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
 166 {
 167   CProb *p = vs->Probs;
 168   SizeT nowPos = 0;
 169   Byte previousByte = 0;
 170   UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
 171   UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
 172   int lc = vs->Properties.lc;
 173
 174   #ifdef _LZMA_OUT_READ
 175
 176   UInt32 Range = vs->Range;
 177   UInt32 Code = vs->Code;
 178   #ifdef _LZMA_IN_CB
 179   const Byte *Buffer = vs->Buffer;
 180   const Byte *BufferLim = vs->BufferLim;
 181   #else
 182   const Byte *Buffer = inStream;
 183   const Byte *BufferLim = inStream + inSize;
 184   #endif
 185   int state = vs->State;
 186   UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
 187   int len = vs->RemainLen;
 188   UInt32 globalPos = vs->GlobalPos;
 189   UInt32 distanceLimit = vs->DistanceLimit;
 190
 191   Byte *dictionary = vs->Dictionary;
 192   UInt32 dictionarySize = vs->Properties.DictionarySize;
 193   UInt32 dictionaryPos = vs->DictionaryPos;
 194
 195   Byte tempDictionary[4];
 196
 197   #ifndef _LZMA_IN_CB
 198   *inSizeProcessed = 0;
 199   #endif
 200   *outSizeProcessed = 0;
 201   if (len == kLzmaStreamWasFinishedId)
 202     return LZMA_RESULT_OK;
 203
 204   if (dictionarySize == 0)
 205   {
 206     dictionary = tempDictionary;
 207     dictionarySize = 1;
 208     tempDictionary[0] = vs->TempDictionary[0];
 209   }
 210
 211   if (len == kLzmaNeedInitId)
 212   {
 213     {
 214       UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
 215       UInt32 i;
 216       for (i = 0; i < numProbs; i++)
 217         p[i] = kBitModelTotal >> 1;
 218       rep0 = rep1 = rep2 = rep3 = 1;
 219       state = 0;
 220       globalPos = 0;
 221       distanceLimit = 0;
 222       dictionaryPos = 0;
 223       dictionary[dictionarySize - 1] = 0;
 224       #ifdef _LZMA_IN_CB
 225       RC_INIT;
 226       #else
 227       RC_INIT(inStream, inSize);
 228       #endif
 229     }
 230     len = 0;
 231   }
 232   while(len != 0 && nowPos < outSize)
 233   {
 234     UInt32 pos = dictionaryPos - rep0;
 235     if (pos >= dictionarySize)
 236       pos += dictionarySize;
 237     outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
 238     if (++dictionaryPos == dictionarySize)
 239       dictionaryPos = 0;
 240     len--;
 241   }
 242   if (dictionaryPos == 0)
 243     previousByte = dictionary[dictionarySize - 1];
 244   else
 245     previousByte = dictionary[dictionaryPos - 1];
 246
 247   #else /* if !_LZMA_OUT_READ */
 248
 249   int state = 0;
 250   UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
 251   int len = 0;
 252   const Byte *Buffer;
 253   const Byte *BufferLim;
 254   UInt32 Range;
 255   UInt32 Code;
 256
 257   #ifndef _LZMA_IN_CB
 258   *inSizeProcessed = 0;
 259   #endif
 260   *outSizeProcessed = 0;
 261
 262   {
 263     UInt32 i;
 264     UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
 265     for (i = 0; i < numProbs; i++)
 266       p[i] = kBitModelTotal >> 1;
 267   }
 268
 269   #ifdef _LZMA_IN_CB
 270   RC_INIT;
 271   #else
 272   RC_INIT(inStream, inSize);
 273   #endif
 274
 275   #endif /* _LZMA_OUT_READ */
 276
 277   while(nowPos < outSize)
 278   {
 279     CProb *prob;
 280     UInt32 bound;
 281     int posState = (int)(
 282         (nowPos
 283         #ifdef _LZMA_OUT_READ
 284         + globalPos
 285         #endif
 286         )
 287         & posStateMask);
 288
 289     prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
 290     IfBit0(prob)
 291     {
 292       int symbol = 1;
 293       UpdateBit0(prob)
 294       prob = p + Literal + (LZMA_LIT_SIZE *
 295         (((
 296         (nowPos
 297         #ifdef _LZMA_OUT_READ
 298         + globalPos
 299         #endif
 300         )
 301         & literalPosMask) << lc) + (previousByte >> (8 - lc))));
 302
 303       if (state >= kNumLitStates)
 304       {
 305         int matchByte;
 306         #ifdef _LZMA_OUT_READ
 307         UInt32 pos = dictionaryPos - rep0;
 308         if (pos >= dictionarySize)
 309           pos += dictionarySize;
 310         matchByte = dictionary[pos];
 311         #else
 312         matchByte = outStream[nowPos - rep0];
 313         #endif
 314         do
 315         {
 316           int bit;
 317           CProb *probLit;
 318           matchByte <<= 1;
 319           bit = (matchByte & 0x100);
 320           probLit = prob + 0x100 + bit + symbol;
 321           RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
 322         }
 323         while (symbol < 0x100);
 324       }
 325       while (symbol < 0x100)
 326       {
 327         CProb *probLit = prob + symbol;
 328         RC_GET_BIT(probLit, symbol)
 329       }
 330       previousByte = (Byte)symbol;
 331
 332       outStream[nowPos++] = previousByte;
 333       #ifdef _LZMA_OUT_READ
 334       if (distanceLimit < dictionarySize)
 335         distanceLimit++;
 336
 337       dictionary[dictionaryPos] = previousByte;
 338       if (++dictionaryPos == dictionarySize)
 339         dictionaryPos = 0;
 340       #endif
 341       if (state < 4) state = 0;
 342       else if (state < 10) state -= 3;
 343       else state -= 6;
 344     }
 345     else
 346     {
 347       UpdateBit1(prob);
 348       prob = p + IsRep + state;
 349       IfBit0(prob)
 350       {
 351         UpdateBit0(prob);
 352         rep3 = rep2;
 353         rep2 = rep1;
 354         rep1 = rep0;
 355         state = state < kNumLitStates ? 0 : 3;
 356         prob = p + LenCoder;
 357       }
 358       else
 359       {
 360         UpdateBit1(prob);
 361         prob = p + IsRepG0 + state;
 362         IfBit0(prob)
 363         {
 364           UpdateBit0(prob);
 365           prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
 366           IfBit0(prob)
 367           {
 368             #ifdef _LZMA_OUT_READ
 369             UInt32 pos;
 370             #endif
 371             UpdateBit0(prob);
 372
 373             #ifdef _LZMA_OUT_READ
 374             if (distanceLimit == 0)
 375             #else
 376             if (nowPos == 0)
 377             #endif
 378               return LZMA_RESULT_DATA_ERROR;
 379
 380             state = state < kNumLitStates ? 9 : 11;
 381             #ifdef _LZMA_OUT_READ
 382             pos = dictionaryPos - rep0;
 383             if (pos >= dictionarySize)
 384               pos += dictionarySize;
 385             previousByte = dictionary[pos];
 386             dictionary[dictionaryPos] = previousByte;
 387             if (++dictionaryPos == dictionarySize)
 388               dictionaryPos = 0;
 389             #else
 390             previousByte = outStream[nowPos - rep0];
 391             #endif
 392             outStream[nowPos++] = previousByte;
 393             #ifdef _LZMA_OUT_READ
 394             if (distanceLimit < dictionarySize)
 395               distanceLimit++;
 396             #endif
 397
 398             continue;
 399           }
 400           else
 401           {
 402             UpdateBit1(prob);
 403           }
 404         }
 405         else
 406         {
 407           UInt32 distance;
 408           UpdateBit1(prob);
 409           prob = p + IsRepG1 + state;
 410           IfBit0(prob)
 411           {
 412             UpdateBit0(prob);
 413             distance = rep1;
 414           }
 415           else
 416           {
 417             UpdateBit1(prob);
 418             prob = p + IsRepG2 + state;
 419             IfBit0(prob)
 420             {
 421               UpdateBit0(prob);
 422               distance = rep2;
 423             }
 424             else
 425             {
 426               UpdateBit1(prob);
 427               distance = rep3;
 428               rep3 = rep2;
 429             }
 430             rep2 = rep1;
 431           }
 432           rep1 = rep0;
 433           rep0 = distance;
 434         }
 435         state = state < kNumLitStates ? 8 : 11;
 436         prob = p + RepLenCoder;
 437       }
 438       {
 439         int numBits, offset;
 440         CProb *probLen = prob + LenChoice;
 441         IfBit0(probLen)
 442         {
 443           UpdateBit0(probLen);
 444           probLen = prob + LenLow + (posState << kLenNumLowBits);
 445           offset = 0;
 446           numBits = kLenNumLowBits;
 447         }
 448         else
 449         {
 450           UpdateBit1(probLen);
 451           probLen = prob + LenChoice2;
 452           IfBit0(probLen)
 453           {
 454             UpdateBit0(probLen);
 455             probLen = prob + LenMid + (posState << kLenNumMidBits);
 456             offset = kLenNumLowSymbols;
 457             numBits = kLenNumMidBits;
 458           }
 459           else
 460           {
 461             UpdateBit1(probLen);
 462             probLen = prob + LenHigh;
 463             offset = kLenNumLowSymbols + kLenNumMidSymbols;
 464             numBits = kLenNumHighBits;
 465           }
 466         }
 467         RangeDecoderBitTreeDecode(probLen, numBits, len);
 468         len += offset;
 469       }
 470
 471       if (state < 4)
 472       {
 473         int posSlot;
 474         state += kNumLitStates;
 475         prob = p + PosSlot +
 476             ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
 477             kNumPosSlotBits);
 478         RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
 479         if (posSlot >= kStartPosModelIndex)
 480         {
 481           int numDirectBits = ((posSlot >> 1) - 1);
 482           rep0 = (2 | ((UInt32)posSlot & 1));
 483           if (posSlot < kEndPosModelIndex)
 484           {
 485             rep0 <<= numDirectBits;
 486             prob = p + SpecPos + rep0 - posSlot - 1;
 487           }
 488           else
 489           {
 490             numDirectBits -= kNumAlignBits;
 491             do
 492             {
 493               RC_NORMALIZE
 494               Range >>= 1;
 495               rep0 <<= 1;
 496               if (Code >= Range)
 497               {
 498                 Code -= Range;
 499                 rep0 |= 1;
 500               }
 501             }
 502             while (--numDirectBits != 0);
 503             prob = p + Align;
 504             rep0 <<= kNumAlignBits;
 505             numDirectBits = kNumAlignBits;
 506           }
 507           {
 508             int i = 1;
 509             int mi = 1;
 510             do
 511             {
 512               CProb *prob3 = prob + mi;
 513               RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
 514               i <<= 1;
 515             }
 516             while(--numDirectBits != 0);
 517           }
 518         }
 519         else
 520           rep0 = posSlot;
 521         if (++rep0 == (UInt32)(0))
 522         {
 523           /* it's for stream version */
 524           len = kLzmaStreamWasFinishedId;
 525           break;
 526         }
 527       }
 528
 529       len += kMatchMinLen;
 530       #ifdef _LZMA_OUT_READ
 531       if (rep0 > distanceLimit)
 532       #else
 533       if (rep0 > nowPos)
 534       #endif
 535         return LZMA_RESULT_DATA_ERROR;
 536
 537       #ifdef _LZMA_OUT_READ
 538       if (dictionarySize - distanceLimit > (UInt32)len)
 539         distanceLimit += len;
 540       else
 541         distanceLimit = dictionarySize;
 542       #endif
 543
 544       do
 545       {
 546         #ifdef _LZMA_OUT_READ
 547         UInt32 pos = dictionaryPos - rep0;
 548         if (pos >= dictionarySize)
 549           pos += dictionarySize;
 550         previousByte = dictionary[pos];
 551         dictionary[dictionaryPos] = previousByte;
 552         if (++dictionaryPos == dictionarySize)
 553           dictionaryPos = 0;
 554         #else
 555         previousByte = outStream[nowPos - rep0];
 556         #endif
 557         len--;
 558         outStream[nowPos++] = previousByte;
 559       }
 560       while(len != 0 && nowPos < outSize);
 561     }
 562   }
 563   RC_NORMALIZE;
 564
 565   #ifdef _LZMA_OUT_READ
 566   vs->Range = Range;
 567   vs->Code = Code;
 568   vs->DictionaryPos = dictionaryPos;
 569   vs->GlobalPos = globalPos + (UInt32)nowPos;
 570   vs->DistanceLimit = distanceLimit;
 571   vs->Reps[0] = rep0;
 572   vs->Reps[1] = rep1;
 573   vs->Reps[2] = rep2;
 574   vs->Reps[3] = rep3;
 575   vs->State = state;
 576   vs->RemainLen = len;
 577   vs->TempDictionary[0] = tempDictionary[0];
 578   #endif
 579
 580   #ifdef _LZMA_IN_CB
 581   vs->Buffer = Buffer;
 582   vs->BufferLim = BufferLim;
 583   #else
 584   *inSizeProcessed = (SizeT)(Buffer - inStream);
 585   #endif
 586   *outSizeProcessed = nowPos;
 587   return LZMA_RESULT_OK;
 588 }