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