target/linux/ifxmips/image/u-boot/files/lib_bootstrap/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 #ifdef CONFIG_LZMA
  23
  24 #include "LzmaDecode.h"
  25
  26 #define kNumTopBits 24
  27 #define kTopValue ((UInt32)1 << kNumTopBits)
  28
  29 #define kNumBitModelTotalBits 11
  30 #define kBitModelTotal (1 << kNumBitModelTotalBits)
  31 #define kNumMoveBits 5
  32
  33 #define RC_READ_BYTE (*Buffer++)
  34
  35 #define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \
  36   { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }}
  37
  38 #ifdef _LZMA_IN_CB
  39
  40
  41 #if 0
  42 #define RC_TEST { if (Buffer == BufferLim) \
  43   { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) { printf("ERROR, %s, %d\n", __FILE__, __LINE__); return result; } \
  44   BufferLim = Buffer + size; if (size == 0) { printf("ERROR, %s, %d\n", __FILE__, __LINE__); return LZMA_RESULT_DATA_ERROR; } }}
  45 #else
  46
  47 #define RC_TEST { if (Buffer == BufferLim) \
  48   { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) { return result; } \
  49   BufferLim = Buffer + size; if (size == 0) { return LZMA_RESULT_DATA_ERROR; } }}
  50 #endif
  51
  52 #define RC_INIT Buffer = BufferLim = 0; RC_INIT2
  53
  54 #else
  55
  56 #if 0
  57 #define RC_TEST { if (Buffer == BufferLim) { printf("ERROR, %s, %d\n", __FILE__, __LINE__); return LZMA_RESULT_DATA_ERROR; } }
  58 #else
  59 #define RC_TEST { if (Buffer == BufferLim) { return LZMA_RESULT_DATA_ERROR; } }
  60 #endif
  61
  62 #define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
  63
  64 #endif
  65
  66 #define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
  67
  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 #ifdef DEBUG_ENABLE_BOOTSTRAP_PRINTF
 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 #ifdef DEBUG_ENABLE_BOOTSTRAP_PRINTF
 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
 400 #ifdef DEBUG_ENABLE_BOOTSTRAP_PRINTF
 401               printf("ERROR: %s, %d\n", __FILE__, __LINE__);
 402 #endif
 403               return LZMA_RESULT_DATA_ERROR;
 404             }
 405
 406             state = state < kNumLitStates ? 9 : 11;
 407             #ifdef _LZMA_OUT_READ
 408             pos = dictionaryPos - rep0;
 409             if (pos >= dictionarySize)
 410               pos += dictionarySize;
 411             previousByte = dictionary[pos];
 412             dictionary[dictionaryPos] = previousByte;
 413             if (++dictionaryPos == dictionarySize)
 414               dictionaryPos = 0;
 415             #else
 416             previousByte = outStream[nowPos - rep0];
 417             #endif
 418             outStream[nowPos++] = previousByte;
 419             #ifdef _LZMA_OUT_READ
 420             if (distanceLimit < dictionarySize)
 421               distanceLimit++;
 422             #endif
 423
 424             continue;
 425           }
 426           else
 427           {
 428             UpdateBit1(prob);
 429           }
 430         }
 431         else
 432         {
 433           UInt32 distance;
 434           UpdateBit1(prob);
 435           prob = p + IsRepG1 + state;
 436           IfBit0(prob)
 437           {
 438             UpdateBit0(prob);
 439             distance = rep1;
 440           }
 441           else
 442           {
 443             UpdateBit1(prob);
 444             prob = p + IsRepG2 + state;
 445             IfBit0(prob)
 446             {
 447               UpdateBit0(prob);
 448               distance = rep2;
 449             }
 450             else
 451             {
 452               UpdateBit1(prob);
 453               distance = rep3;
 454               rep3 = rep2;
 455             }
 456             rep2 = rep1;
 457           }
 458           rep1 = rep0;
 459           rep0 = distance;
 460         }
 461         state = state < kNumLitStates ? 8 : 11;
 462         prob = p + RepLenCoder;
 463       }
 464       {
 465         int numBits, offset;
 466         CProb *probLen = prob + LenChoice;
 467         IfBit0(probLen)
 468         {
 469           UpdateBit0(probLen);
 470           probLen = prob + LenLow + (posState << kLenNumLowBits);
 471           offset = 0;
 472           numBits = kLenNumLowBits;
 473         }
 474         else
 475         {
 476           UpdateBit1(probLen);
 477           probLen = prob + LenChoice2;
 478           IfBit0(probLen)
 479           {
 480             UpdateBit0(probLen);
 481             probLen = prob + LenMid + (posState << kLenNumMidBits);
 482             offset = kLenNumLowSymbols;
 483             numBits = kLenNumMidBits;
 484           }
 485           else
 486           {
 487             UpdateBit1(probLen);
 488             probLen = prob + LenHigh;
 489             offset = kLenNumLowSymbols + kLenNumMidSymbols;
 490             numBits = kLenNumHighBits;
 491           }
 492         }
 493         RangeDecoderBitTreeDecode(probLen, numBits, len);
 494         len += offset;
 495       }
 496
 497       if (state < 4)
 498       {
 499         int posSlot;
 500         state += kNumLitStates;
 501         prob = p + PosSlot +
 502             ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
 503             kNumPosSlotBits);
 504         RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
 505         if (posSlot >= kStartPosModelIndex)
 506         {
 507           int numDirectBits = ((posSlot >> 1) - 1);
 508           rep0 = (2 | ((UInt32)posSlot & 1));
 509           if (posSlot < kEndPosModelIndex)
 510           {
 511             rep0 <<= numDirectBits;
 512             prob = p + SpecPos + rep0 - posSlot - 1;
 513           }
 514           else
 515           {
 516             numDirectBits -= kNumAlignBits;
 517             do
 518             {
 519               RC_NORMALIZE
 520               Range >>= 1;
 521               rep0 <<= 1;
 522               if (Code >= Range)
 523               {
 524                 Code -= Range;
 525                 rep0 |= 1;
 526               }
 527             }
 528             while (--numDirectBits != 0);
 529             prob = p + Align;
 530             rep0 <<= kNumAlignBits;
 531             numDirectBits = kNumAlignBits;
 532           }
 533           {
 534             int i = 1;
 535             int mi = 1;
 536             do
 537             {
 538               CProb *prob3 = prob + mi;
 539               RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
 540               i <<= 1;
 541             }
 542             while(--numDirectBits != 0);
 543           }
 544         }
 545         else
 546           rep0 = posSlot;
 547         if (++rep0 == (UInt32)(0))
 548         {
 549           /* it's for stream version */
 550           len = kLzmaStreamWasFinishedId;
 551           break;
 552         }
 553       }
 554
 555       len += kMatchMinLen;
 556       #ifdef _LZMA_OUT_READ
 557       if (rep0 > distanceLimit)
 558       #else
 559       if (rep0 > nowPos)
 560       #endif
 561       {
 562
 563 #ifdef DEBUG_ENABLE_BOOTSTRAP_PRINTF
 564         printf("ERROR: %s, %d\n", __FILE__, __LINE__);
 565 #endif
 566         return LZMA_RESULT_DATA_ERROR;
 567       }
 568
 569       #ifdef _LZMA_OUT_READ
 570       if (dictionarySize - distanceLimit > (UInt32)len)
 571         distanceLimit += len;
 572       else
 573         distanceLimit = dictionarySize;
 574       #endif
 575
 576       do
 577       {
 578         #ifdef _LZMA_OUT_READ
 579         UInt32 pos = dictionaryPos - rep0;
 580         if (pos >= dictionarySize)
 581           pos += dictionarySize;
 582         previousByte = dictionary[pos];
 583         dictionary[dictionaryPos] = previousByte;
 584         if (++dictionaryPos == dictionarySize)
 585           dictionaryPos = 0;
 586         #else
 587         previousByte = outStream[nowPos - rep0];
 588         #endif
 589         len--;
 590         outStream[nowPos++] = previousByte;
 591       }
 592       while(len != 0 && nowPos < outSize);
 593     }
 594   }
 595   RC_NORMALIZE;
 596
 597   #ifdef _LZMA_OUT_READ
 598   vs->Range = Range;
 599   vs->Code = Code;
 600   vs->DictionaryPos = dictionaryPos;
 601   vs->GlobalPos = globalPos + (UInt32)nowPos;
 602   vs->DistanceLimit = distanceLimit;
 603   vs->Reps[0] = rep0;
 604   vs->Reps[1] = rep1;
 605   vs->Reps[2] = rep2;
 606   vs->Reps[3] = rep3;
 607   vs->State = state;
 608   vs->RemainLen = len;
 609   vs->TempDictionary[0] = tempDictionary[0];
 610   #endif
 611
 612   #ifdef _LZMA_IN_CB
 613   vs->Buffer = Buffer;
 614   vs->BufferLim = BufferLim;
 615   #else
 616   *inSizeProcessed = (SizeT)(Buffer - inStream);
 617   #endif
 618   *outSizeProcessed = nowPos;
 619   return LZMA_RESULT_OK;
 620 }
 621
 622 #endif /* CONFIG_LZMA */