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