target/linux/generic-2.6/image/lzma-loader/src/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 #if 0
 125 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
 126 {
 127   unsigned char prop0;
 128   if (size < LZMA_PROPERTIES_SIZE)
 129     return LZMA_RESULT_DATA_ERROR;
 130   prop0 = propsData[0];
 131   if (prop0 >= (9 * 5 * 5))
 132     return LZMA_RESULT_DATA_ERROR;
 133   {
 134     for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
 135     for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
 136     propsRes->lc = prop0;
 137     /*
 138     unsigned char remainder = (unsigned char)(prop0 / 9);
 139     propsRes->lc = prop0 % 9;
 140     propsRes->pb = remainder / 5;
 141     propsRes->lp = remainder % 5;
 142     */
 143   }
 144
 145   #ifdef _LZMA_OUT_READ
 146   {
 147     int i;
 148     propsRes->DictionarySize = 0;
 149     for (i = 0; i < 4; i++)
 150       propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);
 151     if (propsRes->DictionarySize == 0)
 152       propsRes->DictionarySize = 1;
 153   }
 154   #endif
 155   return LZMA_RESULT_OK;
 156 }
 157 #endif
 158
 159 #define kLzmaStreamWasFinishedId (-1)
 160
 161 int LzmaDecode(CLzmaDecoderState *vs,
 162     #ifdef _LZMA_IN_CB
 163     ILzmaInCallback *InCallback,
 164     #else
 165     const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
 166     #endif
 167     unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
 168 {
 169   CProb *p = vs->Probs;
 170   SizeT nowPos = 0;
 171   Byte previousByte = 0;
 172   UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
 173   UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
 174   int lc = vs->Properties.lc;
 175
 176   #ifdef _LZMA_OUT_READ
 177
 178   UInt32 Range = vs->Range;
 179   UInt32 Code = vs->Code;
 180   #ifdef _LZMA_IN_CB
 181   const Byte *Buffer = vs->Buffer;
 182   const Byte *BufferLim = vs->BufferLim;
 183   #else
 184   const Byte *Buffer = inStream;
 185   const Byte *BufferLim = inStream + inSize;
 186   #endif
 187   int state = vs->State;
 188   UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
 189   int len = vs->RemainLen;
 190   UInt32 globalPos = vs->GlobalPos;
 191   UInt32 distanceLimit = vs->DistanceLimit;
 192
 193   Byte *dictionary = vs->Dictionary;
 194   UInt32 dictionarySize = vs->Properties.DictionarySize;
 195   UInt32 dictionaryPos = vs->DictionaryPos;
 196
 197   Byte tempDictionary[4];
 198
 199   #ifndef _LZMA_IN_CB
 200   *inSizeProcessed = 0;
 201   #endif
 202   *outSizeProcessed = 0;
 203   if (len == kLzmaStreamWasFinishedId)
 204     return LZMA_RESULT_OK;
 205
 206   if (dictionarySize == 0)
 207   {
 208     dictionary = tempDictionary;
 209     dictionarySize = 1;
 210     tempDictionary[0] = vs->TempDictionary[0];
 211   }
 212
 213   if (len == kLzmaNeedInitId)
 214   {
 215     {
 216       UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
 217       UInt32 i;
 218       for (i = 0; i < numProbs; i++)
 219         p[i] = kBitModelTotal >> 1;
 220       rep0 = rep1 = rep2 = rep3 = 1;
 221       state = 0;
 222       globalPos = 0;
 223       distanceLimit = 0;
 224       dictionaryPos = 0;
 225       dictionary[dictionarySize - 1] = 0;
 226       #ifdef _LZMA_IN_CB
 227       RC_INIT;
 228       #else
 229       RC_INIT(inStream, inSize);
 230       #endif
 231     }
 232     len = 0;
 233   }
 234   while(len != 0 && nowPos < outSize)
 235   {
 236     UInt32 pos = dictionaryPos - rep0;
 237     if (pos >= dictionarySize)
 238       pos += dictionarySize;
 239     outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
 240     if (++dictionaryPos == dictionarySize)
 241       dictionaryPos = 0;
 242     len--;
 243   }
 244   if (dictionaryPos == 0)
 245     previousByte = dictionary[dictionarySize - 1];
 246   else
 247     previousByte = dictionary[dictionaryPos - 1];
 248
 249   #else /* if !_LZMA_OUT_READ */
 250
 251   int state = 0;
 252   UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
 253   int len = 0;
 254   const Byte *Buffer;
 255   const Byte *BufferLim;
 256   UInt32 Range;
 257   UInt32 Code;
 258
 259   #ifndef _LZMA_IN_CB
 260   *inSizeProcessed = 0;
 261   #endif
 262   *outSizeProcessed = 0;
 263
 264   {
 265     UInt32 i;
 266     UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
 267     for (i = 0; i < numProbs; i++)
 268       p[i] = kBitModelTotal >> 1;
 269   }
 270
 271   #ifdef _LZMA_IN_CB
 272   RC_INIT;
 273   #else
 274   RC_INIT(inStream, inSize);
 275   #endif
 276
 277   #endif /* _LZMA_OUT_READ */
 278
 279   while(nowPos < outSize)
 280   {
 281     CProb *prob;
 282     UInt32 bound;
 283     int posState = (int)(
 284         (nowPos
 285         #ifdef _LZMA_OUT_READ
 286         + globalPos
 287         #endif
 288         )
 289         & posStateMask);
 290
 291     prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
 292     IfBit0(prob)
 293     {
 294       int symbol = 1;
 295       UpdateBit0(prob)
 296       prob = p + Literal + (LZMA_LIT_SIZE *
 297         (((
 298         (nowPos
 299         #ifdef _LZMA_OUT_READ
 300         + globalPos
 301         #endif
 302         )
 303         & literalPosMask) << lc) + (previousByte >> (8 - lc))));
 304
 305       if (state >= kNumLitStates)
 306       {
 307         int matchByte;
 308         #ifdef _LZMA_OUT_READ
 309         UInt32 pos = dictionaryPos - rep0;
 310         if (pos >= dictionarySize)
 311           pos += dictionarySize;
 312         matchByte = dictionary[pos];
 313         #else
 314         matchByte = outStream[nowPos - rep0];
 315         #endif
 316         do
 317         {
 318           int bit;
 319           CProb *probLit;
 320           matchByte <<= 1;
 321           bit = (matchByte & 0x100);
 322           probLit = prob + 0x100 + bit + symbol;
 323           RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
 324         }
 325         while (symbol < 0x100);
 326       }
 327       while (symbol < 0x100)
 328       {
 329         CProb *probLit = prob + symbol;
 330         RC_GET_BIT(probLit, symbol)
 331       }
 332       previousByte = (Byte)symbol;
 333
 334       outStream[nowPos++] = previousByte;
 335       #ifdef _LZMA_OUT_READ
 336       if (distanceLimit < dictionarySize)
 337         distanceLimit++;
 338
 339       dictionary[dictionaryPos] = previousByte;
 340       if (++dictionaryPos == dictionarySize)
 341         dictionaryPos = 0;
 342       #endif
 343       if (state < 4) state = 0;
 344       else if (state < 10) state -= 3;
 345       else state -= 6;
 346     }
 347     else
 348     {
 349       UpdateBit1(prob);
 350       prob = p + IsRep + state;
 351       IfBit0(prob)
 352       {
 353         UpdateBit0(prob);
 354         rep3 = rep2;
 355         rep2 = rep1;
 356         rep1 = rep0;
 357         state = state < kNumLitStates ? 0 : 3;
 358         prob = p + LenCoder;
 359       }
 360       else
 361       {
 362         UpdateBit1(prob);
 363         prob = p + IsRepG0 + state;
 364         IfBit0(prob)
 365         {
 366           UpdateBit0(prob);
 367           prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
 368           IfBit0(prob)
 369           {
 370             #ifdef _LZMA_OUT_READ
 371             UInt32 pos;
 372             #endif
 373             UpdateBit0(prob);
 374
 375             #ifdef _LZMA_OUT_READ
 376             if (distanceLimit == 0)
 377             #else
 378             if (nowPos == 0)
 379             #endif
 380               return LZMA_RESULT_DATA_ERROR;
 381
 382             state = state < kNumLitStates ? 9 : 11;
 383             #ifdef _LZMA_OUT_READ
 384             pos = dictionaryPos - rep0;
 385             if (pos >= dictionarySize)
 386               pos += dictionarySize;
 387             previousByte = dictionary[pos];
 388             dictionary[dictionaryPos] = previousByte;
 389             if (++dictionaryPos == dictionarySize)
 390               dictionaryPos = 0;
 391             #else
 392             previousByte = outStream[nowPos - rep0];
 393             #endif
 394             outStream[nowPos++] = previousByte;
 395             #ifdef _LZMA_OUT_READ
 396             if (distanceLimit < dictionarySize)
 397               distanceLimit++;
 398             #endif
 399
 400             continue;
 401           }
 402           else
 403           {
 404             UpdateBit1(prob);
 405           }
 406         }
 407         else
 408         {
 409           UInt32 distance;
 410           UpdateBit1(prob);
 411           prob = p + IsRepG1 + state;
 412           IfBit0(prob)
 413           {
 414             UpdateBit0(prob);
 415             distance = rep1;
 416           }
 417           else
 418           {
 419             UpdateBit1(prob);
 420             prob = p + IsRepG2 + state;
 421             IfBit0(prob)
 422             {
 423               UpdateBit0(prob);
 424               distance = rep2;
 425             }
 426             else
 427             {
 428               UpdateBit1(prob);
 429               distance = rep3;
 430               rep3 = rep2;
 431             }
 432             rep2 = rep1;
 433           }
 434           rep1 = rep0;
 435           rep0 = distance;
 436         }
 437         state = state < kNumLitStates ? 8 : 11;
 438         prob = p + RepLenCoder;
 439       }
 440       {
 441         int numBits, offset;
 442         CProb *probLen = prob + LenChoice;
 443         IfBit0(probLen)
 444         {
 445           UpdateBit0(probLen);
 446           probLen = prob + LenLow + (posState << kLenNumLowBits);
 447           offset = 0;
 448           numBits = kLenNumLowBits;
 449         }
 450         else
 451         {
 452           UpdateBit1(probLen);
 453           probLen = prob + LenChoice2;
 454           IfBit0(probLen)
 455           {
 456             UpdateBit0(probLen);
 457             probLen = prob + LenMid + (posState << kLenNumMidBits);
 458             offset = kLenNumLowSymbols;
 459             numBits = kLenNumMidBits;
 460           }
 461           else
 462           {
 463             UpdateBit1(probLen);
 464             probLen = prob + LenHigh;
 465             offset = kLenNumLowSymbols + kLenNumMidSymbols;
 466             numBits = kLenNumHighBits;
 467           }
 468         }
 469         RangeDecoderBitTreeDecode(probLen, numBits, len);
 470         len += offset;
 471       }
 472
 473       if (state < 4)
 474       {
 475         int posSlot;
 476         state += kNumLitStates;
 477         prob = p + PosSlot +
 478             ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
 479             kNumPosSlotBits);
 480         RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
 481         if (posSlot >= kStartPosModelIndex)
 482         {
 483           int numDirectBits = ((posSlot >> 1) - 1);
 484           rep0 = (2 | ((UInt32)posSlot & 1));
 485           if (posSlot < kEndPosModelIndex)
 486           {
 487             rep0 <<= numDirectBits;
 488             prob = p + SpecPos + rep0 - posSlot - 1;
 489           }
 490           else
 491           {
 492             numDirectBits -= kNumAlignBits;
 493             do
 494             {
 495               RC_NORMALIZE
 496               Range >>= 1;
 497               rep0 <<= 1;
 498               if (Code >= Range)
 499               {
 500                 Code -= Range;
 501                 rep0 |= 1;
 502               }
 503             }
 504             while (--numDirectBits != 0);
 505             prob = p + Align;
 506             rep0 <<= kNumAlignBits;
 507             numDirectBits = kNumAlignBits;
 508           }
 509           {
 510             int i = 1;
 511             int mi = 1;
 512             do
 513             {
 514               CProb *prob3 = prob + mi;
 515               RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
 516               i <<= 1;
 517             }
 518             while(--numDirectBits != 0);
 519           }
 520         }
 521         else
 522           rep0 = posSlot;
 523         if (++rep0 == (UInt32)(0))
 524         {
 525           /* it's for stream version */
 526           len = kLzmaStreamWasFinishedId;
 527           break;
 528         }
 529       }
 530
 531       len += kMatchMinLen;
 532       #ifdef _LZMA_OUT_READ
 533       if (rep0 > distanceLimit)
 534       #else
 535       if (rep0 > nowPos)
 536       #endif
 537         return LZMA_RESULT_DATA_ERROR;
 538
 539       #ifdef _LZMA_OUT_READ
 540       if (dictionarySize - distanceLimit > (UInt32)len)
 541         distanceLimit += len;
 542       else
 543         distanceLimit = dictionarySize;
 544       #endif
 545
 546       do
 547       {
 548         #ifdef _LZMA_OUT_READ
 549         UInt32 pos = dictionaryPos - rep0;
 550         if (pos >= dictionarySize)
 551           pos += dictionarySize;
 552         previousByte = dictionary[pos];
 553         dictionary[dictionaryPos] = previousByte;
 554         if (++dictionaryPos == dictionarySize)
 555           dictionaryPos = 0;
 556         #else
 557         previousByte = outStream[nowPos - rep0];
 558         #endif
 559         len--;
 560         outStream[nowPos++] = previousByte;
 561       }
 562       while(len != 0 && nowPos < outSize);
 563     }
 564   }
 565   RC_NORMALIZE;
 566
 567   #ifdef _LZMA_OUT_READ
 568   vs->Range = Range;
 569   vs->Code = Code;
 570   vs->DictionaryPos = dictionaryPos;
 571   vs->GlobalPos = globalPos + (UInt32)nowPos;
 572   vs->DistanceLimit = distanceLimit;
 573   vs->Reps[0] = rep0;
 574   vs->Reps[1] = rep1;
 575   vs->Reps[2] = rep2;
 576   vs->Reps[3] = rep3;
 577   vs->State = state;
 578   vs->RemainLen = len;
 579   vs->TempDictionary[0] = tempDictionary[0];
 580   #endif
 581
 582   #ifdef _LZMA_IN_CB
 583   vs->Buffer = Buffer;
 584   vs->BufferLim = BufferLim;
 585   #else
 586   *inSizeProcessed = (SizeT)(Buffer - inStream);
 587   #endif
 588   *outSizeProcessed = nowPos;
 589   return LZMA_RESULT_OK;
 590 }