target/linux/adm5120-2.6/image/lzma-loader/src/LzmaDecode.c

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