package/uboot-ifxmips/files/lib_generic/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 <config.h>
  23 #include <common.h>
  24
  25 #ifdef CONFIG_LZMA
  26
  27 #include "LzmaDecode.h"
  28
  29 #define kNumTopBits 24
  30 #define kTopValue ((UInt32)1 << kNumTopBits)
  31
  32 #define kNumBitModelTotalBits 11
  33 #define kBitModelTotal (1 << kNumBitModelTotalBits)
  34 #define kNumMoveBits 5
  35
  36 #define RC_READ_BYTE (*Buffer++)
  37
  38 #define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \
  39   { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }}
  40
  41 #ifdef _LZMA_IN_CB
  42
  43 #ifndef CFG_BOOTSTRAP_CODE
  44 #define RC_TEST { if (Buffer == BufferLim) \
  45   { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) { printf("ERROR, %s, %d\n", __FILE__, __LINE__); return result; } \
  46   BufferLim = Buffer + size; if (size == 0) { printf("ERROR, %s, %d\n", __FILE__, __LINE__); return LZMA_RESULT_DATA_ERROR; } }}
  47 #else //CFG_BOOTSTRAP_CODE
  48 #define RC_TEST { if (Buffer == BufferLim) \
  49   { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) { return result; } \
  50   BufferLim = Buffer + size; if (size == 0) { return LZMA_RESULT_DATA_ERROR; } }}
  51 #endif //CFG_BOOTSTRAP_CODE
  52
  53 #define RC_INIT Buffer = BufferLim = 0; RC_INIT2
  54
  55 #else //_LZMA_IN_CB
  56
  57 #ifndef CFG_BOOTSTRAP_CODE
  58 #define RC_TEST { if (Buffer == BufferLim) { printf("ERROR, %s, %d\n", __FILE__, __LINE__); return LZMA_RESULT_DATA_ERROR; } }
  59 #else //CFG_BOOTSTRAP_CODE
  60 #define RC_TEST { if (Buffer == BufferLim) { return LZMA_RESULT_DATA_ERROR; } }
  61 #endif //CFG_BOOTSTRAP_CODE
  62
  63 #define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
  64
  65 #endif //_LZMA_IN_CB
  66
  67 #define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
  68 #define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)
  69 #define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;
  70 #define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;
  71
  72 #define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \
  73   { UpdateBit0(p); mi <<= 1; A0; } else \
  74   { UpdateBit1(p); mi = (mi + mi) + 1; A1; }
  75
  76 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
  77
  78 #define RangeDecoderBitTreeDecode(probs, numLevels, res) \
  79   { int i = numLevels; res = 1; \
  80   do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \
  81   res -= (1 << numLevels); }
  82
  83
  84 #define kNumPosBitsMax 4
  85 #define kNumPosStatesMax (1 << kNumPosBitsMax)
  86
  87 #define kLenNumLowBits 3
  88 #define kLenNumLowSymbols (1 << kLenNumLowBits)
  89 #define kLenNumMidBits 3
  90 #define kLenNumMidSymbols (1 << kLenNumMidBits)
  91 #define kLenNumHighBits 8
  92 #define kLenNumHighSymbols (1 << kLenNumHighBits)
  93
  94 #define LenChoice 0
  95 #define LenChoice2 (LenChoice + 1)
  96 #define LenLow (LenChoice2 + 1)
  97 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
  98 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
  99 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
 100
 101
 102 #define kNumStates 12
 103 #define kNumLitStates 7
 104
 105 #define kStartPosModelIndex 4
 106 #define kEndPosModelIndex 14
 107 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
 108
 109 #define kNumPosSlotBits 6
 110 #define kNumLenToPosStates 4
 111
 112 #define kNumAlignBits 4
 113 #define kAlignTableSize (1 << kNumAlignBits)
 114
 115 #define kMatchMinLen 2
 116
 117 #define IsMatch 0
 118 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
 119 #define IsRepG0 (IsRep + kNumStates)
 120 #define IsRepG1 (IsRepG0 + kNumStates)
 121 #define IsRepG2 (IsRepG1 + kNumStates)
 122 #define IsRep0Long (IsRepG2 + kNumStates)
 123 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
 124 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
 125 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
 126 #define LenCoder (Align + kAlignTableSize)
 127 #define RepLenCoder (LenCoder + kNumLenProbs)
 128 #define Literal (RepLenCoder + kNumLenProbs)
 129
 130 #if Literal != LZMA_BASE_SIZE
 131 StopCompilingDueBUG
 132 #endif
 133
 134 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
 135 {
 136   unsigned char prop0;
 137   if (size < LZMA_PROPERTIES_SIZE)
 138   {
 139 #if defined(DEBUG_ENABLE_BOOTSTRAP_PRINTF) || !defined(CFG_BOOTSTRAP_CODE)
 140     printf("ERROR: %s, %d\n", __FILE__, __LINE__);
 141 #endif
 142     return LZMA_RESULT_DATA_ERROR;
 143   }
 144   prop0 = propsData[0];
 145   if (prop0 >= (9 * 5 * 5))
 146   {
 147 #if defined(DEBUG_ENABLE_BOOTSTRAP_PRINTF) || !defined(CFG_BOOTSTRAP_CODE)
 148     printf("ERROR: %s, %d\n", __FILE__, __LINE__);
 149 #endif
 150     return LZMA_RESULT_DATA_ERROR;
 151   }
 152   {
 153     for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
 154     for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
 155     propsRes->lc = prop0;
 156     /*
 157     unsigned char remainder = (unsigned char)(prop0 / 9);
 158     propsRes->lc = prop0 % 9;
 159     propsRes->pb = remainder / 5;
 160     propsRes->lp = remainder % 5;
 161     */
 162   }
 163
 164   #ifdef _LZMA_OUT_READ
 165   {
 166     int i;
 167     propsRes->DictionarySize = 0;
 168     for (i = 0; i < 4; i++)
 169       propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);
 170     if (propsRes->DictionarySize == 0)
 171       propsRes->DictionarySize = 1;
 172   }
 173   #endif
 174   return LZMA_RESULT_OK;
 175 }
 176
 177 #define kLzmaStreamWasFinishedId (-1)
 178
 179 int LzmaDecode(CLzmaDecoderState *vs,
 180     #ifdef _LZMA_IN_CB
 181     ILzmaInCallback *InCallback,
 182     #else
 183     const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
 184     #endif
 185     unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
 186 {
 187   CProb *p = vs->Probs;
 188   SizeT nowPos = 0;
 189   Byte previousByte = 0;
 190   UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
 191   UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
 192   int lc = vs->Properties.lc;
 193
 194   #ifdef _LZMA_OUT_READ
 195
 196   UInt32 Range = vs->Range;
 197   UInt32 Code = vs->Code;
 198   #ifdef _LZMA_IN_CB
 199   const Byte *Buffer = vs->Buffer;
 200   const Byte *BufferLim = vs->BufferLim;
 201   #else
 202   const Byte *Buffer = inStream;
 203   const Byte *BufferLim = inStream + inSize;
 204   #endif
 205   int state = vs->State;
 206   UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
 207   int len = vs->RemainLen;
 208   UInt32 globalPos = vs->GlobalPos;
 209   UInt32 distanceLimit = vs->DistanceLimit;
 210
 211   Byte *dictionary = vs->Dictionary;
 212   UInt32 dictionarySize = vs->Properties.DictionarySize;
 213   UInt32 dictionaryPos = vs->DictionaryPos;
 214
 215   Byte tempDictionary[4];
 216
 217   #ifndef _LZMA_IN_CB
 218   *inSizeProcessed = 0;
 219   #endif
 220   *outSizeProcessed = 0;
 221   if (len == kLzmaStreamWasFinishedId)
 222     return LZMA_RESULT_OK;
 223
 224   if (dictionarySize == 0)
 225   {
 226     dictionary = tempDictionary;
 227     dictionarySize = 1;
 228     tempDictionary[0] = vs->TempDictionary[0];
 229   }
 230
 231   if (len == kLzmaNeedInitId)
 232   {
 233     {
 234       UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
 235       UInt32 i;
 236       for (i = 0; i < numProbs; i++)
 237         p[i] = kBitModelTotal >> 1;
 238       rep0 = rep1 = rep2 = rep3 = 1;
 239       state = 0;
 240       globalPos = 0;
 241       distanceLimit = 0;
 242       dictionaryPos = 0;
 243       dictionary[dictionarySize - 1] = 0;
 244       #ifdef _LZMA_IN_CB
 245       RC_INIT;
 246       #else
 247       RC_INIT(inStream, inSize);
 248       #endif
 249     }
 250     len = 0;
 251   }
 252   while(len != 0 && nowPos < outSize)
 253   {
 254     UInt32 pos = dictionaryPos - rep0;
 255     if (pos >= dictionarySize)
 256       pos += dictionarySize;
 257     outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
 258     if (++dictionaryPos == dictionarySize)
 259       dictionaryPos = 0;
 260     len--;
 261   }
 262   if (dictionaryPos == 0)
 263     previousByte = dictionary[dictionarySize - 1];
 264   else
 265     previousByte = dictionary[dictionaryPos - 1];
 266
 267   #else /* if !_LZMA_OUT_READ */
 268
 269   int state = 0;
 270   UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
 271   int len = 0;
 272   const Byte *Buffer;
 273   const Byte *BufferLim;
 274   UInt32 Range;
 275   UInt32 Code;
 276
 277   #ifndef _LZMA_IN_CB
 278   *inSizeProcessed = 0;
 279   #endif
 280   *outSizeProcessed = 0;
 281
 282   {
 283     UInt32 i;
 284     UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
 285     for (i = 0; i < numProbs; i++)
 286       p[i] = kBitModelTotal >> 1;
 287   }
 288
 289   #ifdef _LZMA_IN_CB
 290   RC_INIT;
 291   #else
 292   RC_INIT(inStream, inSize);
 293   #endif
 294
 295   #endif /* _LZMA_OUT_READ */
 296
 297   while(nowPos < outSize)
 298   {
 299     CProb *prob;
 300     UInt32 bound;
 301     int posState = (int)(
 302         (nowPos
 303         #ifdef _LZMA_OUT_READ
 304         + globalPos
 305         #endif
 306         )
 307         & posStateMask);
 308
 309     prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
 310     IfBit0(prob)
 311     {
 312       int symbol = 1;
 313       UpdateBit0(prob)
 314       prob = p + Literal + (LZMA_LIT_SIZE *
 315         (((
 316         (nowPos
 317         #ifdef _LZMA_OUT_READ
 318         + globalPos
 319         #endif
 320         )
 321         & literalPosMask) << lc) + (previousByte >> (8 - lc))));
 322
 323       if (state >= kNumLitStates)
 324       {
 325         int matchByte;
 326         #ifdef _LZMA_OUT_READ
 327         UInt32 pos = dictionaryPos - rep0;
 328         if (pos >= dictionarySize)
 329           pos += dictionarySize;
 330         matchByte = dictionary[pos];
 331         #else
 332         matchByte = outStream[nowPos - rep0];
 333         #endif
 334         do
 335         {
 336           int bit;
 337           CProb *probLit;
 338           matchByte <<= 1;
 339           bit = (matchByte & 0x100);
 340           probLit = prob + 0x100 + bit + symbol;
 341           RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
 342         }
 343         while (symbol < 0x100);
 344       }
 345       while (symbol < 0x100)
 346       {
 347         CProb *probLit = prob + symbol;
 348         RC_GET_BIT(probLit, symbol)
 349       }
 350       previousByte = (Byte)symbol;
 351
 352       outStream[nowPos++] = previousByte;
 353       #ifdef _LZMA_OUT_READ
 354       if (distanceLimit < dictionarySize)
 355         distanceLimit++;
 356
 357       dictionary[dictionaryPos] = previousByte;
 358       if (++dictionaryPos == dictionarySize)
 359         dictionaryPos = 0;
 360       #endif
 361       if (state < 4) state = 0;
 362       else if (state < 10) state -= 3;
 363       else state -= 6;
 364     }
 365     else
 366     {
 367       UpdateBit1(prob);
 368       prob = p + IsRep + state;
 369       IfBit0(prob)
 370       {
 371         UpdateBit0(prob);
 372         rep3 = rep2;
 373         rep2 = rep1;
 374         rep1 = rep0;
 375         state = state < kNumLitStates ? 0 : 3;
 376         prob = p + LenCoder;
 377       }
 378       else
 379       {
 380         UpdateBit1(prob);
 381         prob = p + IsRepG0 + state;
 382         IfBit0(prob)
 383         {
 384           UpdateBit0(prob);
 385           prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
 386           IfBit0(prob)
 387           {
 388             #ifdef _LZMA_OUT_READ
 389             UInt32 pos;
 390             #endif
 391             UpdateBit0(prob);
 392
 393             #ifdef _LZMA_OUT_READ
 394             if (distanceLimit == 0)
 395             #else
 396             if (nowPos == 0)
 397             #endif
 398             {
 399 #if defined(DEBUG_ENABLE_BOOTSTRAP_PRINTF) || !defined(CFG_BOOTSTRAP_CODE)
 400               printf("ERROR: %s, %d\n", __FILE__, __LINE__);
 401 #endif
 402               return LZMA_RESULT_DATA_ERROR;
 403             }
 404
 405             state = state < kNumLitStates ? 9 : 11;
 406             #ifdef _LZMA_OUT_READ
 407             pos = dictionaryPos - rep0;
 408             if (pos >= dictionarySize)
 409               pos += dictionarySize;
 410             previousByte = dictionary[pos];
 411             dictionary[dictionaryPos] = previousByte;
 412             if (++dictionaryPos == dictionarySize)
 413               dictionaryPos = 0;
 414             #else
 415             previousByte = outStream[nowPos - rep0];
 416             #endif
 417             outStream[nowPos++] = previousByte;
 418             #ifdef _LZMA_OUT_READ
 419             if (distanceLimit < dictionarySize)
 420               distanceLimit++;
 421             #endif
 422
 423             continue;
 424           }
 425           else
 426           {
 427             UpdateBit1(prob);
 428           }
 429         }
 430         else
 431         {
 432           UInt32 distance;
 433           UpdateBit1(prob);
 434           prob = p + IsRepG1 + state;
 435           IfBit0(prob)
 436           {
 437             UpdateBit0(prob);
 438             distance = rep1;
 439           }
 440           else
 441           {
 442             UpdateBit1(prob);
 443             prob = p + IsRepG2 + state;
 444             IfBit0(prob)
 445             {
 446               UpdateBit0(prob);
 447               distance = rep2;
 448             }
 449             else
 450             {
 451               UpdateBit1(prob);
 452               distance = rep3;
 453               rep3 = rep2;
 454             }
 455             rep2 = rep1;
 456           }
 457           rep1 = rep0;
 458           rep0 = distance;
 459         }
 460         state = state < kNumLitStates ? 8 : 11;
 461         prob = p + RepLenCoder;
 462       }
 463       {
 464         int numBits, offset;
 465         CProb *probLen = prob + LenChoice;
 466         IfBit0(probLen)
 467         {
 468           UpdateBit0(probLen);
 469           probLen = prob + LenLow + (posState << kLenNumLowBits);
 470           offset = 0;
 471           numBits = kLenNumLowBits;
 472         }
 473         else
 474         {
 475           UpdateBit1(probLen);
 476           probLen = prob + LenChoice2;
 477           IfBit0(probLen)
 478           {
 479             UpdateBit0(probLen);
 480             probLen = prob + LenMid + (posState << kLenNumMidBits);
 481             offset = kLenNumLowSymbols;
 482             numBits = kLenNumMidBits;
 483           }
 484           else
 485           {
 486             UpdateBit1(probLen);
 487             probLen = prob + LenHigh;
 488             offset = kLenNumLowSymbols + kLenNumMidSymbols;
 489             numBits = kLenNumHighBits;
 490           }
 491         }
 492         RangeDecoderBitTreeDecode(probLen, numBits, len);
 493         len += offset;
 494       }
 495
 496       if (state < 4)
 497       {
 498         int posSlot;
 499         state += kNumLitStates;
 500         prob = p + PosSlot +
 501             ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
 502             kNumPosSlotBits);
 503         RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
 504         if (posSlot >= kStartPosModelIndex)
 505         {
 506           int numDirectBits = ((posSlot >> 1) - 1);
 507           rep0 = (2 | ((UInt32)posSlot & 1));
 508           if (posSlot < kEndPosModelIndex)
 509           {
 510             rep0 <<= numDirectBits;
 511             prob = p + SpecPos + rep0 - posSlot - 1;
 512           }
 513           else
 514           {
 515             numDirectBits -= kNumAlignBits;
 516             do
 517             {
 518               RC_NORMALIZE
 519               Range >>= 1;
 520               rep0 <<= 1;
 521               if (Code >= Range)
 522               {
 523                 Code -= Range;
 524                 rep0 |= 1;
 525               }
 526             }
 527             while (--numDirectBits != 0);
 528             prob = p + Align;
 529             rep0 <<= kNumAlignBits;
 530             numDirectBits = kNumAlignBits;
 531           }
 532           {
 533             int i = 1;
 534             int mi = 1;
 535             do
 536             {
 537               CProb *prob3 = prob + mi;
 538               RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
 539               i <<= 1;
 540             }
 541             while(--numDirectBits != 0);
 542           }
 543         }
 544         else
 545           rep0 = posSlot;
 546         if (++rep0 == (UInt32)(0))
 547         {
 548           /* it's for stream version */
 549           len = kLzmaStreamWasFinishedId;
 550           break;
 551         }
 552       }
 553
 554       len += kMatchMinLen;
 555       #ifdef _LZMA_OUT_READ
 556       if (rep0 > distanceLimit)
 557       #else
 558       if (rep0 > nowPos)
 559       #endif
 560       {
 561 #if defined(DEBUG_ENABLE_BOOTSTRAP_PRINTF) || !defined(CFG_BOOTSTRAP_CODE)
 562         printf("ERROR: %s, %d\n", __FILE__, __LINE__);
 563 #endif
 564         return LZMA_RESULT_DATA_ERROR;
 565       }
 566
 567       #ifdef _LZMA_OUT_READ
 568       if (dictionarySize - distanceLimit > (UInt32)len)
 569         distanceLimit += len;
 570       else
 571         distanceLimit = dictionarySize;
 572       #endif
 573
 574       do
 575       {
 576         #ifdef _LZMA_OUT_READ
 577         UInt32 pos = dictionaryPos - rep0;
 578         if (pos >= dictionarySize)
 579           pos += dictionarySize;
 580         previousByte = dictionary[pos];
 581         dictionary[dictionaryPos] = previousByte;
 582         if (++dictionaryPos == dictionarySize)
 583           dictionaryPos = 0;
 584         #else
 585         previousByte = outStream[nowPos - rep0];
 586         #endif
 587         len--;
 588         outStream[nowPos++] = previousByte;
 589       }
 590       while(len != 0 && nowPos < outSize);
 591     }
 592   }
 593   RC_NORMALIZE;
 594
 595   #ifdef _LZMA_OUT_READ
 596   vs->Range = Range;
 597   vs->Code = Code;
 598   vs->DictionaryPos = dictionaryPos;
 599   vs->GlobalPos = globalPos + (UInt32)nowPos;
 600   vs->DistanceLimit = distanceLimit;
 601   vs->Reps[0] = rep0;
 602   vs->Reps[1] = rep1;
 603   vs->Reps[2] = rep2;
 604   vs->Reps[3] = rep3;
 605   vs->State = state;
 606   vs->RemainLen = len;
 607   vs->TempDictionary[0] = tempDictionary[0];
 608   #endif
 609
 610   #ifdef _LZMA_IN_CB
 611   vs->Buffer = Buffer;
 612   vs->BufferLim = BufferLim;
 613   #else
 614   *inSizeProcessed = (SizeT)(Buffer - inStream);
 615   #endif
 616   *outSizeProcessed = nowPos;
 617   return LZMA_RESULT_OK;
 618 }
 619
 620 #endif /* CONFIG_LZMA */