src/lzmadecode.c

   1 /*
   2   LzmaDecode.c
   3   LZMA Decoder (optimized for Speed version)
   4
   5   LZMA SDK 4.40 Copyright (c) 1999-2006 Igor Pavlov (2006-05-01)
   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 #define kNumTopBits 24
  25 #define kTopValue ((UInt32)1 << kNumTopBits)
  26
  27 #define kNumBitModelTotalBits 11
  28 #define kBitModelTotal (1 << kNumBitModelTotalBits)
  29 #define kNumMoveBits 5
  30
  31 #define RC_READ_BYTE (*Buffer++)
  32
  33 #define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \
  34   { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }}
  35
  36
  37 #define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
  38
  39 #define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
  40
  41
  42 #define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
  43
  44 #define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)
  45 #define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;
  46 #define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;
  47
  48 #define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \
  49   { UpdateBit0(p); mi <<= 1; A0; } else \
  50   { UpdateBit1(p); mi = (mi + mi) + 1; A1; }
  51
  52 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
  53
  54 #define RangeDecoderBitTreeDecode(probs, numLevels, res) \
  55   { int i = numLevels; res = 1; \
  56   do { CProb *cp = probs + res; RC_GET_BIT(cp, res) } while(--i != 0); \
  57   res -= (1 << numLevels); }
  58
  59
  60 #define kNumPosBitsMax 4
  61 #define kNumPosStatesMax (1 << kNumPosBitsMax)
  62
  63 #define kLenNumLowBits 3
  64 #define kLenNumLowSymbols (1 << kLenNumLowBits)
  65 #define kLenNumMidBits 3
  66 #define kLenNumMidSymbols (1 << kLenNumMidBits)
  67 #define kLenNumHighBits 8
  68 #define kLenNumHighSymbols (1 << kLenNumHighBits)
  69
  70 #define LenChoice 0
  71 #define LenChoice2 (LenChoice + 1)
  72 #define LenLow (LenChoice2 + 1)
  73 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
  74 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
  75 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
  76
  77
  78 #define kNumStates 12
  79 #define kNumLitStates 7
  80
  81 #define kStartPosModelIndex 4
  82 #define kEndPosModelIndex 14
  83 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
  84
  85 #define kNumPosSlotBits 6
  86 #define kNumLenToPosStates 4
  87
  88 #define kNumAlignBits 4
  89 #define kAlignTableSize (1 << kNumAlignBits)
  90
  91 #define kMatchMinLen 2
  92
  93 #define IsMatch 0
  94 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
  95 #define IsRepG0 (IsRep + kNumStates)
  96 #define IsRepG1 (IsRepG0 + kNumStates)
  97 #define IsRepG2 (IsRepG1 + kNumStates)
  98 #define IsRep0Long (IsRepG2 + kNumStates)
  99 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
 100 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
 101 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
 102 #define LenCoder (Align + kAlignTableSize)
 103 #define RepLenCoder (LenCoder + kNumLenProbs)
 104 #define Literal (RepLenCoder + kNumLenProbs)
 105
 106 #if Literal != LZMA_BASE_SIZE
 107 StopCompilingDueBUG
 108 #endif
 109
 110 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
 111 {
 112   unsigned char prop0;
 113   if (size < LZMA_PROPERTIES_SIZE)
 114     return LZMA_RESULT_DATA_ERROR;
 115   prop0 = propsData[0];
 116   if (prop0 >= (9 * 5 * 5))
 117     return LZMA_RESULT_DATA_ERROR;
 118   {
 119     for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
 120     for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
 121     propsRes->lc = prop0;
 122     /*
 123     unsigned char remainder = (unsigned char)(prop0 / 9);
 124     propsRes->lc = prop0 % 9;
 125     propsRes->pb = remainder / 5;
 126     propsRes->lp = remainder % 5;
 127     */
 128   }
 129
 130   return LZMA_RESULT_OK;
 131 }
 132
 133 #define kLzmaStreamWasFinishedId (-1)
 134
 135 int LzmaDecode(CLzmaDecoderState *vs,
 136     const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
 137     unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
 138 {
 139   CProb *p = vs->Probs;
 140   SizeT nowPos = 0;
 141   Byte previousByte = 0;
 142   UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
 143   UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
 144   int lc = vs->Properties.lc;
 145
 146
 147   int state = 0;
 148   UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
 149   int len = 0;
 150   const Byte *Buffer;
 151   const Byte *BufferLim;
 152   UInt32 Range;
 153   UInt32 Code;
 154
 155   *inSizeProcessed = 0;
 156   *outSizeProcessed = 0;
 157
 158   {
 159     UInt32 i;
 160     UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
 161     for (i = 0; i < numProbs; i++)
 162       p[i] = kBitModelTotal >> 1;
 163   }
 164
 165   RC_INIT(inStream, inSize);
 166
 167
 168   while(nowPos < outSize)
 169   {
 170     CProb *prob;
 171     UInt32 bound;
 172     int posState = (int)(
 173         (nowPos
 174         )
 175         & posStateMask);
 176
 177     prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
 178     IfBit0(prob)
 179     {
 180       int symbol = 1;
 181       UpdateBit0(prob)
 182       prob = p + Literal + (LZMA_LIT_SIZE *
 183         (((
 184         (nowPos
 185         )
 186         & literalPosMask) << lc) + (previousByte >> (8 - lc))));
 187
 188       if (state >= kNumLitStates)
 189       {
 190         int matchByte;
 191         matchByte = outStream[nowPos - rep0];
 192         do
 193         {
 194           int bit;
 195           CProb *probLit;
 196           matchByte <<= 1;
 197           bit = (matchByte & 0x100);
 198           probLit = prob + 0x100 + bit + symbol;
 199           RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
 200         }
 201         while (symbol < 0x100);
 202       }
 203       while (symbol < 0x100)
 204       {
 205         CProb *probLit = prob + symbol;
 206         RC_GET_BIT(probLit, symbol)
 207       }
 208       previousByte = (Byte)symbol;
 209
 210       outStream[nowPos++] = previousByte;
 211       if (state < 4) state = 0;
 212       else if (state < 10) state -= 3;
 213       else state -= 6;
 214     }
 215     else
 216     {
 217       UpdateBit1(prob);
 218       prob = p + IsRep + state;
 219       IfBit0(prob)
 220       {
 221         UpdateBit0(prob);
 222         rep3 = rep2;
 223         rep2 = rep1;
 224         rep1 = rep0;
 225         state = state < kNumLitStates ? 0 : 3;
 226         prob = p + LenCoder;
 227       }
 228       else
 229       {
 230         UpdateBit1(prob);
 231         prob = p + IsRepG0 + state;
 232         IfBit0(prob)
 233         {
 234           UpdateBit0(prob);
 235           prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
 236           IfBit0(prob)
 237           {
 238             UpdateBit0(prob);
 239
 240             if (nowPos == 0)
 241               return LZMA_RESULT_DATA_ERROR;
 242
 243             state = state < kNumLitStates ? 9 : 11;
 244             previousByte = outStream[nowPos - rep0];
 245             outStream[nowPos++] = previousByte;
 246
 247             continue;
 248           }
 249           else
 250           {
 251             UpdateBit1(prob);
 252           }
 253         }
 254         else
 255         {
 256           UInt32 distance;
 257           UpdateBit1(prob);
 258           prob = p + IsRepG1 + state;
 259           IfBit0(prob)
 260           {
 261             UpdateBit0(prob);
 262             distance = rep1;
 263           }
 264           else
 265           {
 266             UpdateBit1(prob);
 267             prob = p + IsRepG2 + state;
 268             IfBit0(prob)
 269             {
 270               UpdateBit0(prob);
 271               distance = rep2;
 272             }
 273             else
 274             {
 275               UpdateBit1(prob);
 276               distance = rep3;
 277               rep3 = rep2;
 278             }
 279             rep2 = rep1;
 280           }
 281           rep1 = rep0;
 282           rep0 = distance;
 283         }
 284         state = state < kNumLitStates ? 8 : 11;
 285         prob = p + RepLenCoder;
 286       }
 287       {
 288         int numBits, offset;
 289         CProb *probLen = prob + LenChoice;
 290         IfBit0(probLen)
 291         {
 292           UpdateBit0(probLen);
 293           probLen = prob + LenLow + (posState << kLenNumLowBits);
 294           offset = 0;
 295           numBits = kLenNumLowBits;
 296         }
 297         else
 298         {
 299           UpdateBit1(probLen);
 300           probLen = prob + LenChoice2;
 301           IfBit0(probLen)
 302           {
 303             UpdateBit0(probLen);
 304             probLen = prob + LenMid + (posState << kLenNumMidBits);
 305             offset = kLenNumLowSymbols;
 306             numBits = kLenNumMidBits;
 307           }
 308           else
 309           {
 310             UpdateBit1(probLen);
 311             probLen = prob + LenHigh;
 312             offset = kLenNumLowSymbols + kLenNumMidSymbols;
 313             numBits = kLenNumHighBits;
 314           }
 315         }
 316         RangeDecoderBitTreeDecode(probLen, numBits, len);
 317         len += offset;
 318       }
 319
 320       if (state < 4)
 321       {
 322         int posSlot;
 323         state += kNumLitStates;
 324         prob = p + PosSlot +
 325             ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
 326             kNumPosSlotBits);
 327         RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
 328         if (posSlot >= kStartPosModelIndex)
 329         {
 330           int numDirectBits = ((posSlot >> 1) - 1);
 331           rep0 = (2 | ((UInt32)posSlot & 1));
 332           if (posSlot < kEndPosModelIndex)
 333           {
 334             rep0 <<= numDirectBits;
 335             prob = p + SpecPos + rep0 - posSlot - 1;
 336           }
 337           else
 338           {
 339             numDirectBits -= kNumAlignBits;
 340             do
 341             {
 342               RC_NORMALIZE
 343               Range >>= 1;
 344               rep0 <<= 1;
 345               if (Code >= Range)
 346               {
 347                 Code -= Range;
 348                 rep0 |= 1;
 349               }
 350             }
 351             while (--numDirectBits != 0);
 352             prob = p + Align;
 353             rep0 <<= kNumAlignBits;
 354             numDirectBits = kNumAlignBits;
 355           }
 356           {
 357             int i = 1;
 358             int mi = 1;
 359             do
 360             {
 361               CProb *prob3 = prob + mi;
 362               RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
 363               i <<= 1;
 364             }
 365             while(--numDirectBits != 0);
 366           }
 367         }
 368         else
 369           rep0 = posSlot;
 370         if (++rep0 == (UInt32)(0))
 371         {
 372           /* it's for stream version */
 373           len = kLzmaStreamWasFinishedId;
 374           break;
 375         }
 376       }
 377
 378       len += kMatchMinLen;
 379       if (rep0 > nowPos)
 380         return LZMA_RESULT_DATA_ERROR;
 381
 382
 383       do
 384       {
 385         previousByte = outStream[nowPos - rep0];
 386         len--;
 387         outStream[nowPos++] = previousByte;
 388       }
 389       while(len != 0 && nowPos < outSize);
 390     }
 391   }
 392   RC_NORMALIZE;
 393
 394
 395   *inSizeProcessed = (SizeT)(Buffer - inStream);
 396   *outSizeProcessed = nowPos;
 397   return LZMA_RESULT_OK;
 398 }