target/linux/rdc/files-2.6.24/arch/x86/boot/compressed/LzmaDecode.c

   1 /*
   2   LzmaDecode.c
   3   LZMA Decoder (optimized for Speed version)
   4
   5   LZMA SDK 4.17 Copyright (c) 1999-2005 Igor Pavlov (2005-04-05)
   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         do
 336         {
 337           int bit;
 338           CProb *probLit;
 339           matchByte <<= 1;
 340           bit = (matchByte & 0x100);
 341           probLit = prob + 0x100 + bit + symbol;
 342           RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
 343         }
 344         while (symbol < 0x100);
 345       }
 346       while (symbol < 0x100)
 347       {
 348         CProb *probLit = prob + symbol;
 349         RC_GET_BIT(probLit, symbol)
 350       }
 351       previousByte = (Byte)symbol;
 352
 353       outStream[nowPos++] = previousByte;
 354       #ifdef _LZMA_OUT_READ
 355       dictionary[dictionaryPos] = previousByte;
 356       if (++dictionaryPos == dictionarySize)
 357         dictionaryPos = 0;
 358       #endif
 359       if (state < 4) state = 0;
 360       else if (state < 10) state -= 3;
 361       else state -= 6;
 362     }
 363     else
 364     {
 365       UpdateBit1(prob);
 366       prob = p + IsRep + state;
 367       IfBit0(prob)
 368       {
 369         UpdateBit0(prob);
 370         rep3 = rep2;
 371         rep2 = rep1;
 372         rep1 = rep0;
 373         state = state < kNumLitStates ? 0 : 3;
 374         prob = p + LenCoder;
 375       }
 376       else
 377       {
 378         UpdateBit1(prob);
 379         prob = p + IsRepG0 + state;
 380         IfBit0(prob)
 381         {
 382           UpdateBit0(prob);
 383           prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
 384           IfBit0(prob)
 385           {
 386             #ifdef _LZMA_OUT_READ
 387             UInt32 pos;
 388             #endif
 389             UpdateBit0(prob);
 390             if (nowPos
 391                 #ifdef _LZMA_OUT_READ
 392                 + globalPos
 393                 #endif
 394                 == 0)
 395               return LZMA_RESULT_DATA_ERROR;
 396             state = state < kNumLitStates ? 9 : 11;
 397             #ifdef _LZMA_OUT_READ
 398             pos = dictionaryPos - rep0;
 399             if (pos >= dictionarySize)
 400               pos += dictionarySize;
 401             previousByte = dictionary[pos];
 402             dictionary[dictionaryPos] = previousByte;
 403             if (++dictionaryPos == dictionarySize)
 404               dictionaryPos = 0;
 405             #else
 406             previousByte = outStream[nowPos - rep0];
 407             #endif
 408             outStream[nowPos++] = previousByte;
 409             continue;
 410           }
 411           else
 412           {
 413             UpdateBit1(prob);
 414           }
 415         }
 416         else
 417         {
 418           UInt32 distance;
 419           UpdateBit1(prob);
 420           prob = p + IsRepG1 + state;
 421           IfBit0(prob)
 422           {
 423             UpdateBit0(prob);
 424             distance = rep1;
 425           }
 426           else
 427           {
 428             UpdateBit1(prob);
 429             prob = p + IsRepG2 + state;
 430             IfBit0(prob)
 431             {
 432               UpdateBit0(prob);
 433               distance = rep2;
 434             }
 435             else
 436             {
 437               UpdateBit1(prob);
 438               distance = rep3;
 439               rep3 = rep2;
 440             }
 441             rep2 = rep1;
 442           }
 443           rep1 = rep0;
 444           rep0 = distance;
 445         }
 446         state = state < kNumLitStates ? 8 : 11;
 447         prob = p + RepLenCoder;
 448       }
 449       {
 450         int numBits, offset;
 451         CProb *probLen = prob + LenChoice;
 452         IfBit0(probLen)
 453         {
 454           UpdateBit0(probLen);
 455           probLen = prob + LenLow + (posState << kLenNumLowBits);
 456           offset = 0;
 457           numBits = kLenNumLowBits;
 458         }
 459         else
 460         {
 461           UpdateBit1(probLen);
 462           probLen = prob + LenChoice2;
 463           IfBit0(probLen)
 464           {
 465             UpdateBit0(probLen);
 466             probLen = prob + LenMid + (posState << kLenNumMidBits);
 467             offset = kLenNumLowSymbols;
 468             numBits = kLenNumMidBits;
 469           }
 470           else
 471           {
 472             UpdateBit1(probLen);
 473             probLen = prob + LenHigh;
 474             offset = kLenNumLowSymbols + kLenNumMidSymbols;
 475             numBits = kLenNumHighBits;
 476           }
 477         }
 478         RangeDecoderBitTreeDecode(probLen, numBits, len);
 479         len += offset;
 480       }
 481
 482       if (state < 4)
 483       {
 484         int posSlot;
 485         state += kNumLitStates;
 486         prob = p + PosSlot +
 487             ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
 488             kNumPosSlotBits);
 489         RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
 490         if (posSlot >= kStartPosModelIndex)
 491         {
 492           int numDirectBits = ((posSlot >> 1) - 1);
 493           rep0 = (2 | ((UInt32)posSlot & 1));
 494           if (posSlot < kEndPosModelIndex)
 495           {
 496             rep0 <<= numDirectBits;
 497             prob = p + SpecPos + rep0 - posSlot - 1;
 498           }
 499           else
 500           {
 501             numDirectBits -= kNumAlignBits;
 502             do
 503             {
 504               RC_NORMALIZE
 505               Range >>= 1;
 506               rep0 <<= 1;
 507               if (Code >= Range)
 508               {
 509                 Code -= Range;
 510                 rep0 |= 1;
 511               }
 512             }
 513             while (--numDirectBits != 0);
 514             prob = p + Align;
 515             rep0 <<= kNumAlignBits;
 516             numDirectBits = kNumAlignBits;
 517           }
 518           {
 519             int i = 1;
 520             int mi = 1;
 521             do
 522             {
 523               CProb *prob3 = prob + mi;
 524               RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
 525               i <<= 1;
 526             }
 527             while(--numDirectBits != 0);
 528           }
 529         }
 530         else
 531           rep0 = posSlot;
 532         if (++rep0 == (UInt32)(0))
 533         {
 534           /* it's for stream version */
 535           len = -1;
 536           break;
 537         }
 538       }
 539
 540       len += kMatchMinLen;
 541       if (rep0 > nowPos
 542         #ifdef _LZMA_OUT_READ
 543         + globalPos || rep0 > dictionarySize
 544         #endif
 545         )
 546         return LZMA_RESULT_DATA_ERROR;
 547       do
 548       {
 549         #ifdef _LZMA_OUT_READ
 550         UInt32 pos = dictionaryPos - rep0;
 551         if (pos >= dictionarySize)
 552           pos += dictionarySize;
 553         previousByte = dictionary[pos];
 554         dictionary[dictionaryPos] = previousByte;
 555         if (++dictionaryPos == dictionarySize)
 556           dictionaryPos = 0;
 557         #else
 558         previousByte = outStream[nowPos - rep0];
 559         #endif
 560         len--;
 561         outStream[nowPos++] = previousByte;
 562       }
 563       while(len != 0 && nowPos < outSize);
 564     }
 565   }
 566   RC_NORMALIZE;
 567
 568   #ifdef _LZMA_OUT_READ
 569   vs->Buffer = Buffer;
 570   vs->BufferLim = BufferLim;
 571   vs->Range = Range;
 572   vs->Code = Code;
 573   vs->DictionaryPos = dictionaryPos;
 574   vs->GlobalPos = globalPos + nowPos;
 575   vs->Reps[0] = rep0;
 576   vs->Reps[1] = rep1;
 577   vs->Reps[2] = rep2;
 578   vs->Reps[3] = rep3;
 579   vs->State = state;
 580   vs->RemainLen = len;
 581   vs->TempDictionary[0] = tempDictionary[0];
 582   #endif
 583
 584   *outSizeProcessed = nowPos;
 585   return LZMA_RESULT_OK;
 586 }