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