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