Changeset 16939


Ignore:
Timestamp:
2009-07-21T04:31:37+02:00 (7 years ago)
Author:
nbd
Message:

add a new arm lzma kernel decompressor based on rewritten (and much more readable) unlzma code. backport to 2.6.28 as well. tested on ixp4xx and orion

Location:
trunk/target/linux/generic-2.6
Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/target/linux/generic-2.6/patches-2.6.30/960-arm_lzma_loader.patch

    r16284 r16939  
    1 --- /dev/null 
    2 +++ b/arch/arm/boot/compressed/LzmaDecode.c 
    3 @@ -0,0 +1,590 @@ 
    4 +/* 
    5 +  LzmaDecode.c 
    6 +  LZMA Decoder (optimized for Speed version) 
    7  
    8 +  LZMA SDK 4.22 Copyright (c) 1999-2005 Igor Pavlov (2005-06-10) 
    9 +  http://www.7-zip.org/ 
    10 + 
    11 +  LZMA SDK is licensed under two licenses: 
    12 +  1) GNU Lesser General Public License (GNU LGPL) 
    13 +  2) Common Public License (CPL) 
    14 +  It means that you can select one of these two licenses and  
    15 +  follow rules of that license. 
    16 + 
    17 +  SPECIAL EXCEPTION: 
    18 +  Igor Pavlov, as the author of this Code, expressly permits you to  
    19 +  statically or dynamically link your Code (or bind by name) to the  
    20 +  interfaces of this file without subjecting your linked Code to the  
    21 +  terms of the CPL or GNU LGPL. Any modifications or additions  
    22 +  to this file, however, are subject to the LGPL or CPL terms. 
    23 +*/ 
    24 + 
    25 +#include "LzmaDecode.h" 
    26 + 
    27 +#ifndef Byte 
    28 +#define Byte unsigned char 
    29 +#endif 
    30 + 
    31 +#define kNumTopBits 24 
    32 +#define kTopValue ((UInt32)1 << kNumTopBits) 
    33 + 
    34 +#define kNumBitModelTotalBits 11 
    35 +#define kBitModelTotal (1 << kNumBitModelTotalBits) 
    36 +#define kNumMoveBits 5 
    37 + 
    38 +#define RC_READ_BYTE (*Buffer++) 
    39 + 
    40 +#define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \ 
    41 +  { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }} 
    42 + 
    43 +#ifdef _LZMA_IN_CB 
    44 + 
    45 +#define RC_TEST { if (Buffer == BufferLim) \ 
    46 +  { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) return result; \ 
    47 +  BufferLim = Buffer + size; if (size == 0) return LZMA_RESULT_DATA_ERROR; }} 
    48 + 
    49 +#define RC_INIT Buffer = BufferLim = 0; RC_INIT2 
    50 + 
    51 +#else 
    52 + 
    53 +#define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; } 
    54 + 
    55 +#define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2 
    56 +  
    57 +#endif 
    58 + 
    59 +#define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; } 
    60 + 
    61 +#define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound) 
    62 +#define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits; 
    63 +#define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits; 
    64 + 
    65 +#define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \ 
    66 +  { UpdateBit0(p); mi <<= 1; A0; } else \ 
    67 +  { UpdateBit1(p); mi = (mi + mi) + 1; A1; }  
    68  
    69 +#define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)                
    70 + 
    71 +#define RangeDecoderBitTreeDecode(probs, numLevels, res) \ 
    72 +  { int i = numLevels; res = 1; \ 
    73 +  do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \ 
    74 +  res -= (1 << numLevels); } 
    75 + 
    76 + 
    77 +#define kNumPosBitsMax 4 
    78 +#define kNumPosStatesMax (1 << kNumPosBitsMax) 
    79 + 
    80 +#define kLenNumLowBits 3 
    81 +#define kLenNumLowSymbols (1 << kLenNumLowBits) 
    82 +#define kLenNumMidBits 3 
    83 +#define kLenNumMidSymbols (1 << kLenNumMidBits) 
    84 +#define kLenNumHighBits 8 
    85 +#define kLenNumHighSymbols (1 << kLenNumHighBits) 
    86 + 
    87 +#define LenChoice 0 
    88 +#define LenChoice2 (LenChoice + 1) 
    89 +#define LenLow (LenChoice2 + 1) 
    90 +#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits)) 
    91 +#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits)) 
    92 +#define kNumLenProbs (LenHigh + kLenNumHighSymbols)  
    93 + 
    94 + 
    95 +#define kNumStates 12 
    96 +#define kNumLitStates 7 
    97 + 
    98 +#define kStartPosModelIndex 4 
    99 +#define kEndPosModelIndex 14 
    100 +#define kNumFullDistances (1 << (kEndPosModelIndex >> 1)) 
    101 + 
    102 +#define kNumPosSlotBits 6 
    103 +#define kNumLenToPosStates 4 
    104 + 
    105 +#define kNumAlignBits 4 
    106 +#define kAlignTableSize (1 << kNumAlignBits) 
    107 + 
    108 +#define kMatchMinLen 2 
    109 + 
    110 +#define IsMatch 0 
    111 +#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax)) 
    112 +#define IsRepG0 (IsRep + kNumStates) 
    113 +#define IsRepG1 (IsRepG0 + kNumStates) 
    114 +#define IsRepG2 (IsRepG1 + kNumStates) 
    115 +#define IsRep0Long (IsRepG2 + kNumStates) 
    116 +#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax)) 
    117 +#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits)) 
    118 +#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex) 
    119 +#define LenCoder (Align + kAlignTableSize) 
    120 +#define RepLenCoder (LenCoder + kNumLenProbs) 
    121 +#define Literal (RepLenCoder + kNumLenProbs) 
    122 + 
    123 +#if Literal != LZMA_BASE_SIZE 
    124 +StopCompilingDueBUG 
    125 +#endif 
    126 + 
    127 +#if 0 
    128 +int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size) 
    129 +{ 
    130 +  unsigned char prop0; 
    131 +  if (size < LZMA_PROPERTIES_SIZE) 
    132 +    return LZMA_RESULT_DATA_ERROR; 
    133 +  prop0 = propsData[0]; 
    134 +  if (prop0 >= (9 * 5 * 5)) 
    135 +    return LZMA_RESULT_DATA_ERROR; 
    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 +#endif 
    161 + 
    162 +#define kLzmaStreamWasFinishedId (-1) 
    163 + 
    164 +int LzmaDecode(CLzmaDecoderState *vs, 
    165 +    #ifdef _LZMA_IN_CB 
    166 +    ILzmaInCallback *InCallback, 
    167 +    #else 
    168 +    const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed, 
    169 +    #endif 
    170 +    unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed) 
    171 +{ 
    172 +  CProb *p = vs->Probs; 
    173 +  SizeT nowPos = 0; 
    174 +  Byte previousByte = 0; 
    175 +  UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1; 
    176 +  UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1; 
    177 +  int lc = vs->Properties.lc; 
    178 + 
    179 +  #ifdef _LZMA_OUT_READ 
    180  
    181 +  UInt32 Range = vs->Range; 
    182 +  UInt32 Code = vs->Code; 
    183 +  #ifdef _LZMA_IN_CB 
    184 +  const Byte *Buffer = vs->Buffer; 
    185 +  const Byte *BufferLim = vs->BufferLim; 
    186 +  #else 
    187 +  const Byte *Buffer = inStream; 
    188 +  const Byte *BufferLim = inStream + inSize; 
    189 +  #endif 
    190 +  int state = vs->State; 
    191 +  UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3]; 
    192 +  int len = vs->RemainLen; 
    193 +  UInt32 globalPos = vs->GlobalPos; 
    194 +  UInt32 distanceLimit = vs->DistanceLimit; 
    195 + 
    196 +  Byte *dictionary = vs->Dictionary; 
    197 +  UInt32 dictionarySize = vs->Properties.DictionarySize; 
    198 +  UInt32 dictionaryPos = vs->DictionaryPos; 
    199 + 
    200 +  Byte tempDictionary[4]; 
    201 + 
    202 +  #ifndef _LZMA_IN_CB 
    203 +  *inSizeProcessed = 0; 
    204 +  #endif 
    205 +  *outSizeProcessed = 0; 
    206 +  if (len == kLzmaStreamWasFinishedId) 
    207 +    return LZMA_RESULT_OK; 
    208 + 
    209 +  if (dictionarySize == 0) 
    210 +  { 
    211 +    dictionary = tempDictionary; 
    212 +    dictionarySize = 1; 
    213 +    tempDictionary[0] = vs->TempDictionary[0]; 
    214 +  } 
    215 + 
    216 +  if (len == kLzmaNeedInitId) 
    217 +  { 
    218 +    { 
    219 +      UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp)); 
    220 +      UInt32 i; 
    221 +      for (i = 0; i < numProbs; i++) 
    222 +        p[i] = kBitModelTotal >> 1;  
    223 +      rep0 = rep1 = rep2 = rep3 = 1; 
    224 +      state = 0; 
    225 +      globalPos = 0; 
    226 +      distanceLimit = 0; 
    227 +      dictionaryPos = 0; 
    228 +      dictionary[dictionarySize - 1] = 0; 
    229 +      #ifdef _LZMA_IN_CB 
    230 +      RC_INIT; 
    231 +      #else 
    232 +      RC_INIT(inStream, inSize); 
    233 +      #endif 
    234 +    } 
    235 +    len = 0; 
    236 +  } 
    237 +  while(len != 0 && nowPos < outSize) 
    238 +  { 
    239 +    UInt32 pos = dictionaryPos - rep0; 
    240 +    if (pos >= dictionarySize) 
    241 +      pos += dictionarySize; 
    242 +    outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos]; 
    243 +    if (++dictionaryPos == dictionarySize) 
    244 +      dictionaryPos = 0; 
    245 +    len--; 
    246 +  } 
    247 +  if (dictionaryPos == 0) 
    248 +    previousByte = dictionary[dictionarySize - 1]; 
    249 +  else 
    250 +    previousByte = dictionary[dictionaryPos - 1]; 
    251 + 
    252 +  #else /* if !_LZMA_OUT_READ */ 
    253 + 
    254 +  int state = 0; 
    255 +  UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1; 
    256 +  int len = 0; 
    257 +  const Byte *Buffer; 
    258 +  const Byte *BufferLim; 
    259 +  UInt32 Range; 
    260 +  UInt32 Code; 
    261 + 
    262 +  #ifndef _LZMA_IN_CB 
    263 +  *inSizeProcessed = 0; 
    264 +  #endif 
    265 +  *outSizeProcessed = 0; 
    266 + 
    267 +  { 
    268 +    UInt32 i; 
    269 +    UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp)); 
    270 +    for (i = 0; i < numProbs; i++) 
    271 +      p[i] = kBitModelTotal >> 1; 
    272 +  } 
    273  
    274 +  #ifdef _LZMA_IN_CB 
    275 +  RC_INIT; 
    276 +  #else 
    277 +  RC_INIT(inStream, inSize); 
    278 +  #endif 
    279 + 
    280 +  #endif /* _LZMA_OUT_READ */ 
    281 + 
    282 +  while(nowPos < outSize) 
    283 +  { 
    284 +    CProb *prob; 
    285 +    UInt32 bound; 
    286 +    int posState = (int)( 
    287 +        (nowPos  
    288 +        #ifdef _LZMA_OUT_READ 
    289 +        + globalPos 
    290 +        #endif 
    291 +        ) 
    292 +        & posStateMask); 
    293 + 
    294 +    prob = p + IsMatch + (state << kNumPosBitsMax) + posState; 
    295 +    IfBit0(prob) 
    296 +    { 
    297 +      int symbol = 1; 
    298 +      UpdateBit0(prob) 
    299 +      prob = p + Literal + (LZMA_LIT_SIZE *  
    300 +        ((( 
    301 +        (nowPos  
    302 +        #ifdef _LZMA_OUT_READ 
    303 +        + globalPos 
    304 +        #endif 
    305 +        ) 
    306 +        & literalPosMask) << lc) + (previousByte >> (8 - lc)))); 
    307 + 
    308 +      if (state >= kNumLitStates) 
    309 +      { 
    310 +        int matchByte; 
    311 +        #ifdef _LZMA_OUT_READ 
    312 +        UInt32 pos = dictionaryPos - rep0; 
    313 +        if (pos >= dictionarySize) 
    314 +          pos += dictionarySize; 
    315 +        matchByte = dictionary[pos]; 
    316 +        #else 
    317 +        matchByte = outStream[nowPos - rep0]; 
    318 +        #endif 
    319 +        do 
    320 +        { 
    321 +          int bit; 
    322 +          CProb *probLit; 
    323 +          matchByte <<= 1; 
    324 +          bit = (matchByte & 0x100); 
    325 +          probLit = prob + 0x100 + bit + symbol; 
    326 +          RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break) 
    327 +        } 
    328 +        while (symbol < 0x100); 
    329 +      } 
    330 +      while (symbol < 0x100) 
    331 +      { 
    332 +        CProb *probLit = prob + symbol; 
    333 +        RC_GET_BIT(probLit, symbol) 
    334 +      } 
    335 +      previousByte = (Byte)symbol; 
    336 + 
    337 +      outStream[nowPos++] = previousByte; 
    338 +      #ifdef _LZMA_OUT_READ 
    339 +      if (distanceLimit < dictionarySize) 
    340 +        distanceLimit++; 
    341 + 
    342 +      dictionary[dictionaryPos] = previousByte; 
    343 +      if (++dictionaryPos == dictionarySize) 
    344 +        dictionaryPos = 0; 
    345 +      #endif 
    346 +      if (state < 4) state = 0; 
    347 +      else if (state < 10) state -= 3; 
    348 +      else state -= 6; 
    349 +    } 
    350 +    else              
    351 +    { 
    352 +      UpdateBit1(prob); 
    353 +      prob = p + IsRep + state; 
    354 +      IfBit0(prob) 
    355 +      { 
    356 +        UpdateBit0(prob); 
    357 +        rep3 = rep2; 
    358 +        rep2 = rep1; 
    359 +        rep1 = rep0; 
    360 +        state = state < kNumLitStates ? 0 : 3; 
    361 +        prob = p + LenCoder; 
    362 +      } 
    363 +      else 
    364 +      { 
    365 +        UpdateBit1(prob); 
    366 +        prob = p + IsRepG0 + state; 
    367 +        IfBit0(prob) 
    368 +        { 
    369 +          UpdateBit0(prob); 
    370 +          prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState; 
    371 +          IfBit0(prob) 
    372 +          { 
    373 +            #ifdef _LZMA_OUT_READ 
    374 +            UInt32 pos; 
    375 +            #endif 
    376 +            UpdateBit0(prob); 
    377 +             
    378 +            #ifdef _LZMA_OUT_READ 
    379 +            if (distanceLimit == 0) 
    380 +            #else 
    381 +            if (nowPos == 0) 
    382 +            #endif 
    383 +              return LZMA_RESULT_DATA_ERROR; 
    384 +             
    385 +            state = state < kNumLitStates ? 9 : 11; 
    386 +            #ifdef _LZMA_OUT_READ 
    387 +            pos = dictionaryPos - rep0; 
    388 +            if (pos >= dictionarySize) 
    389 +              pos += dictionarySize; 
    390 +            previousByte = dictionary[pos]; 
    391 +            dictionary[dictionaryPos] = previousByte; 
    392 +            if (++dictionaryPos == dictionarySize) 
    393 +              dictionaryPos = 0; 
    394 +            #else 
    395 +            previousByte = outStream[nowPos - rep0]; 
    396 +            #endif 
    397 +            outStream[nowPos++] = previousByte; 
    398 +            #ifdef _LZMA_OUT_READ 
    399 +            if (distanceLimit < dictionarySize) 
    400 +              distanceLimit++; 
    401 +            #endif 
    402 + 
    403 +            continue; 
    404 +          } 
    405 +          else 
    406 +          { 
    407 +            UpdateBit1(prob); 
    408 +          } 
    409 +        } 
    410 +        else 
    411 +        { 
    412 +          UInt32 distance; 
    413 +          UpdateBit1(prob); 
    414 +          prob = p + IsRepG1 + state; 
    415 +          IfBit0(prob) 
    416 +          { 
    417 +            UpdateBit0(prob); 
    418 +            distance = rep1; 
    419 +          } 
    420 +          else  
    421 +          { 
    422 +            UpdateBit1(prob); 
    423 +            prob = p + IsRepG2 + state; 
    424 +            IfBit0(prob) 
    425 +            { 
    426 +              UpdateBit0(prob); 
    427 +              distance = rep2; 
    428 +            } 
    429 +            else 
    430 +            { 
    431 +              UpdateBit1(prob); 
    432 +              distance = rep3; 
    433 +              rep3 = rep2; 
    434 +            } 
    435 +            rep2 = rep1; 
    436 +          } 
    437 +          rep1 = rep0; 
    438 +          rep0 = distance; 
    439 +        } 
    440 +        state = state < kNumLitStates ? 8 : 11; 
    441 +        prob = p + RepLenCoder; 
    442 +      } 
    443 +      { 
    444 +        int numBits, offset; 
    445 +        CProb *probLen = prob + LenChoice; 
    446 +        IfBit0(probLen) 
    447 +        { 
    448 +          UpdateBit0(probLen); 
    449 +          probLen = prob + LenLow + (posState << kLenNumLowBits); 
    450 +          offset = 0; 
    451 +          numBits = kLenNumLowBits; 
    452 +        } 
    453 +        else 
    454 +        { 
    455 +          UpdateBit1(probLen); 
    456 +          probLen = prob + LenChoice2; 
    457 +          IfBit0(probLen) 
    458 +          { 
    459 +            UpdateBit0(probLen); 
    460 +            probLen = prob + LenMid + (posState << kLenNumMidBits); 
    461 +            offset = kLenNumLowSymbols; 
    462 +            numBits = kLenNumMidBits; 
    463 +          } 
    464 +          else 
    465 +          { 
    466 +            UpdateBit1(probLen); 
    467 +            probLen = prob + LenHigh; 
    468 +            offset = kLenNumLowSymbols + kLenNumMidSymbols; 
    469 +            numBits = kLenNumHighBits; 
    470 +          } 
    471 +        } 
    472 +        RangeDecoderBitTreeDecode(probLen, numBits, len); 
    473 +        len += offset; 
    474 +      } 
    475 + 
    476 +      if (state < 4) 
    477 +      { 
    478 +        int posSlot; 
    479 +        state += kNumLitStates; 
    480 +        prob = p + PosSlot + 
    481 +            ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<  
    482 +            kNumPosSlotBits); 
    483 +        RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot); 
    484 +        if (posSlot >= kStartPosModelIndex) 
    485 +        { 
    486 +          int numDirectBits = ((posSlot >> 1) - 1); 
    487 +          rep0 = (2 | ((UInt32)posSlot & 1)); 
    488 +          if (posSlot < kEndPosModelIndex) 
    489 +          { 
    490 +            rep0 <<= numDirectBits; 
    491 +            prob = p + SpecPos + rep0 - posSlot - 1; 
    492 +          } 
    493 +          else 
    494 +          { 
    495 +            numDirectBits -= kNumAlignBits; 
    496 +            do 
    497 +            { 
    498 +              RC_NORMALIZE 
    499 +              Range >>= 1; 
    500 +              rep0 <<= 1; 
    501 +              if (Code >= Range) 
    502 +              { 
    503 +                Code -= Range; 
    504 +                rep0 |= 1; 
    505 +              } 
    506 +            } 
    507 +            while (--numDirectBits != 0); 
    508 +            prob = p + Align; 
    509 +            rep0 <<= kNumAlignBits; 
    510 +            numDirectBits = kNumAlignBits; 
    511 +          } 
    512 +          { 
    513 +            int i = 1; 
    514 +            int mi = 1; 
    515 +            do 
    516 +            { 
    517 +              CProb *prob3 = prob + mi; 
    518 +              RC_GET_BIT2(prob3, mi, ; , rep0 |= i); 
    519 +              i <<= 1; 
    520 +            } 
    521 +            while(--numDirectBits != 0); 
    522 +          } 
    523 +        } 
    524 +        else 
    525 +          rep0 = posSlot; 
    526 +        if (++rep0 == (UInt32)(0)) 
    527 +        { 
    528 +          /* it's for stream version */ 
    529 +          len = kLzmaStreamWasFinishedId; 
    530 +          break; 
    531 +        } 
    532 +      } 
    533 + 
    534 +      len += kMatchMinLen; 
    535 +      #ifdef _LZMA_OUT_READ 
    536 +      if (rep0 > distanceLimit)  
    537 +      #else 
    538 +      if (rep0 > nowPos) 
    539 +      #endif 
    540 +        return LZMA_RESULT_DATA_ERROR; 
    541 + 
    542 +      #ifdef _LZMA_OUT_READ 
    543 +      if (dictionarySize - distanceLimit > (UInt32)len) 
    544 +        distanceLimit += len; 
    545 +      else 
    546 +        distanceLimit = dictionarySize; 
    547 +      #endif 
    548 + 
    549 +      do 
    550 +      { 
    551 +        #ifdef _LZMA_OUT_READ 
    552 +        UInt32 pos = dictionaryPos - rep0; 
    553 +        if (pos >= dictionarySize) 
    554 +          pos += dictionarySize; 
    555 +        previousByte = dictionary[pos]; 
    556 +        dictionary[dictionaryPos] = previousByte; 
    557 +        if (++dictionaryPos == dictionarySize) 
    558 +          dictionaryPos = 0; 
    559 +        #else 
    560 +        previousByte = outStream[nowPos - rep0]; 
    561 +        #endif 
    562 +        len--; 
    563 +        outStream[nowPos++] = previousByte; 
    564 +      } 
    565 +      while(len != 0 && nowPos < outSize); 
    566 +    } 
    567 +  } 
    568 +  RC_NORMALIZE; 
    569 + 
    570 +  #ifdef _LZMA_OUT_READ 
    571 +  vs->Range = Range; 
    572 +  vs->Code = Code; 
    573 +  vs->DictionaryPos = dictionaryPos; 
    574 +  vs->GlobalPos = globalPos + (UInt32)nowPos; 
    575 +  vs->DistanceLimit = distanceLimit; 
    576 +  vs->Reps[0] = rep0; 
    577 +  vs->Reps[1] = rep1; 
    578 +  vs->Reps[2] = rep2; 
    579 +  vs->Reps[3] = rep3; 
    580 +  vs->State = state; 
    581 +  vs->RemainLen = len; 
    582 +  vs->TempDictionary[0] = tempDictionary[0]; 
    583 +  #endif 
    584 + 
    585 +  #ifdef _LZMA_IN_CB 
    586 +  vs->Buffer = Buffer; 
    587 +  vs->BufferLim = BufferLim; 
    588 +  #else 
    589 +  *inSizeProcessed = (SizeT)(Buffer - inStream); 
    590 +  #endif 
    591 +  *outSizeProcessed = nowPos; 
    592 +  return LZMA_RESULT_OK; 
    593 +} 
    594 --- /dev/null 
    595 +++ b/arch/arm/boot/compressed/LzmaDecode.h 
    596 @@ -0,0 +1,131 @@ 
    597 +/*  
    598 +  LzmaDecode.h 
    599 +  LZMA Decoder interface 
    600 + 
    601 +  LZMA SDK 4.21 Copyright (c) 1999-2005 Igor Pavlov (2005-06-08) 
    602 +  http://www.7-zip.org/ 
    603 + 
    604 +  LZMA SDK is licensed under two licenses: 
    605 +  1) GNU Lesser General Public License (GNU LGPL) 
    606 +  2) Common Public License (CPL) 
    607 +  It means that you can select one of these two licenses and  
    608 +  follow rules of that license. 
    609 + 
    610 +  SPECIAL EXCEPTION: 
    611 +  Igor Pavlov, as the author of this code, expressly permits you to  
    612 +  statically or dynamically link your code (or bind by name) to the  
    613 +  interfaces of this file without subjecting your linked code to the  
    614 +  terms of the CPL or GNU LGPL. Any modifications or additions  
    615 +  to this file, however, are subject to the LGPL or CPL terms. 
    616 +*/ 
    617 + 
    618 +#ifndef __LZMADECODE_H 
    619 +#define __LZMADECODE_H 
    620 + 
    621 +/* #define _LZMA_IN_CB */ 
    622 +/* Use callback for input data */ 
    623 + 
    624 +/* #define _LZMA_OUT_READ */ 
    625 +/* Use read function for output data */ 
    626 + 
    627 +/* #define _LZMA_PROB32 */ 
    628 +/* It can increase speed on some 32-bit CPUs,  
    629 +   but memory usage will be doubled in that case */ 
    630 + 
    631 +/* #define _LZMA_LOC_OPT */ 
    632 +/* Enable local speed optimizations inside code */ 
    633 + 
    634 +/* #define _LZMA_SYSTEM_SIZE_T */ 
    635 +/* Use system's size_t. You can use it to enable 64-bit sizes supporting*/ 
    636 + 
    637 +#ifndef UInt32 
    638 +#ifdef _LZMA_UINT32_IS_ULONG 
    639 +#define UInt32 unsigned long 
    640 +#else 
    641 +#define UInt32 unsigned int 
    642 +#endif 
    643 +#endif 
    644 + 
    645 +#ifndef SizeT 
    646 +#ifdef _LZMA_SYSTEM_SIZE_T 
    647 +#include <stddef.h> 
    648 +#define SizeT size_t 
    649 +#else 
    650 +#define SizeT UInt32 
    651 +#endif 
    652 +#endif 
    653 + 
    654 +#ifdef _LZMA_PROB32 
    655 +#define CProb UInt32 
    656 +#else 
    657 +#define CProb unsigned short 
    658 +#endif 
    659 + 
    660 +#define LZMA_RESULT_OK 0 
    661 +#define LZMA_RESULT_DATA_ERROR 1 
    662 + 
    663 +#ifdef _LZMA_IN_CB 
    664 +typedef struct _ILzmaInCallback 
    665 +{ 
    666 +  int (*Read)(void *object, const unsigned char **buffer, SizeT *bufferSize); 
    667 +} ILzmaInCallback; 
    668 +#endif 
    669 + 
    670 +#define LZMA_BASE_SIZE 1846 
    671 +#define LZMA_LIT_SIZE 768 
    672 + 
    673 +#define LZMA_PROPERTIES_SIZE 5 
    674 + 
    675 +typedef struct _CLzmaProperties 
    676 +{ 
    677 +  int lc; 
    678 +  int lp; 
    679 +  int pb; 
    680 +  #ifdef _LZMA_OUT_READ 
    681 +  UInt32 DictionarySize; 
    682 +  #endif 
    683 +}CLzmaProperties; 
    684 + 
    685 +int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size); 
    686 + 
    687 +#define LzmaGetNumProbs(Properties) (LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((Properties)->lc + (Properties)->lp))) 
    688 + 
    689 +#define kLzmaNeedInitId (-2) 
    690 + 
    691 +typedef struct _CLzmaDecoderState 
    692 +{ 
    693 +  CLzmaProperties Properties; 
    694 +  CProb *Probs; 
    695 + 
    696 +  #ifdef _LZMA_IN_CB 
    697 +  const unsigned char *Buffer; 
    698 +  const unsigned char *BufferLim; 
    699 +  #endif 
    700 + 
    701 +  #ifdef _LZMA_OUT_READ 
    702 +  unsigned char *Dictionary; 
    703 +  UInt32 Range; 
    704 +  UInt32 Code; 
    705 +  UInt32 DictionaryPos; 
    706 +  UInt32 GlobalPos; 
    707 +  UInt32 DistanceLimit; 
    708 +  UInt32 Reps[4]; 
    709 +  int State; 
    710 +  int RemainLen; 
    711 +  unsigned char TempDictionary[4]; 
    712 +  #endif 
    713 +} CLzmaDecoderState; 
    714 + 
    715 +#ifdef _LZMA_OUT_READ 
    716 +#define LzmaDecoderInit(vs) { (vs)->RemainLen = kLzmaNeedInitId; } 
    717 +#endif 
    718 + 
    719 +int LzmaDecode(CLzmaDecoderState *vs, 
    720 +    #ifdef _LZMA_IN_CB 
    721 +    ILzmaInCallback *inCallback, 
    722 +    #else 
    723 +    const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed, 
    724 +    #endif 
    725 +    unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed); 
    726 + 
    727 +#endif 
    7281--- a/arch/arm/boot/compressed/Makefile 
    7292+++ b/arch/arm/boot/compressed/Makefile 
    730 @@ -5,7 +5,7 @@ 
    731  # 
    732   
    733  HEAD   = head.o 
    734 -OBJS   = misc.o 
    735 +OBJS   = misc.o ../../lib/lib1funcs.o 
    736  FONTC  = $(srctree)/drivers/video/console/font_acorn_8x8.c 
    737   
    738  # 
    7393@@ -63,7 +63,7 @@ endif 
    7404  
     
    76226--- a/arch/arm/boot/compressed/misc.c 
    76327+++ b/arch/arm/boot/compressed/misc.c 
    764 @@ -202,8 +202,8 @@ typedef unsigned long  ulg; 
    765  static uch *inbuf;             /* input buffer */ 
    766  static uch window[WSIZE];      /* Sliding window buffer */ 
    767   
     28@@ -186,36 +186,10 @@ static inline __ptr_t memcpy(__ptr_t __d 
     29        return __dest; 
     30 } 
     31  
     32-/* 
     33- * gzip delarations 
     34- */ 
     35-#define OF(args)  args 
     36-#define STATIC static 
     37- 
     38-typedef unsigned char  uch; 
     39-typedef unsigned short ush; 
     40-typedef unsigned long  ulg; 
     41- 
     42-#define WSIZE 0x8000           /* Window size must be at least 32k, */ 
     43+#define WSIZE 0x20000          /* Window size must be at least 128k, */ 
     44                                /* and a power of two */ 
     45  
     46-static uch *inbuf;             /* input buffer */ 
     47-static uch window[WSIZE];      /* Sliding window buffer */ 
     48- 
    76849-static unsigned insize;                /* valid bytes in inbuf */ 
    76950-static unsigned inptr;         /* index of next byte to be processed in inbuf */ 
    770 +static unsigned insize = 0;            /* valid bytes in inbuf */ 
    771 +static unsigned inptr = 0;             /* index of next byte to be processed in inbuf */ 
    772  static unsigned outcnt;                /* bytes in output buffer */ 
    773   
    774  /* gzip flag byte */ 
    775 @@ -242,7 +242,7 @@ extern char input_data[]; 
     51-static unsigned outcnt;                /* bytes in output buffer */ 
     52- 
     53-/* gzip flag byte */ 
     54-#define ASCII_FLAG   0x01 /* bit 0 set: file probably ascii text */ 
     55-#define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */ 
     56-#define EXTRA_FIELD  0x04 /* bit 2 set: extra field present */ 
     57-#define ORIG_NAME    0x08 /* bit 3 set: original file name present */ 
     58-#define COMMENT      0x10 /* bit 4 set: file comment present */ 
     59-#define ENCRYPTED    0x20 /* bit 5 set: file is encrypted */ 
     60-#define RESERVED     0xC0 /* bit 6,7:   reserved */ 
     61- 
     62-#define get_byte()  (inptr < insize ? inbuf[inptr++] : fill_inbuf()) 
     63+static u8 window[WSIZE];       /* Sliding window buffer */ 
     64  
     65 /* Diagnostic functions */ 
     66 #ifdef DEBUG 
     67@@ -234,24 +208,21 @@ static unsigned outcnt;           /* bytes in out 
     68 #  define Tracecv(c,x) 
     69 #endif 
     70  
     71-static int  fill_inbuf(void); 
     72-static void flush_window(void); 
     73 static void error(char *m); 
     74  
     75 extern char input_data[]; 
    77676 extern char input_data_end[]; 
    77777  
    778  static uch *output_data; 
     78-static uch *output_data; 
    77979-static ulg output_ptr; 
    780 +static ulg output_ptr = 0; 
    781  static ulg bytes_out; 
     80-static ulg bytes_out; 
     81+static unsigned long output_ptr; 
     82+static unsigned long bytes_out; 
    78283  
    78384 static void error(char *m); 
    784 @@ -259,7 +259,7 @@ static ulg free_mem_end_ptr; 
     85  
     86 static void putstr(const char *); 
     87  
     88 extern int end; 
     89-static ulg free_mem_ptr; 
     90-static ulg free_mem_end_ptr; 
     91+static unsigned long free_mem_ptr; 
     92+static unsigned long free_mem_end_ptr; 
     93  
     94 #ifdef STANDALONE_DEBUG 
     95 #define NO_INFLATE_MALLOC 
     96@@ -259,50 +230,10 @@ static ulg free_mem_end_ptr; 
    78597  
    78698 #define ARCH_HAS_DECOMP_WDOG 
    78799  
    788100-#include "../../../../lib/inflate.c" 
    789 +/* #include "../../../../lib/inflate.c" */ 
    790   
    791  /* =========================================================================== 
    792   * Fill the input buffer. This is called only when the buffer is empty 
    793 @@ -277,6 +277,76 @@ int fill_inbuf(void) 
    794         return inbuf[0]; 
    795  } 
    796   
    797 +#define _LZMA_IN_CB 
    798 +#include "LzmaDecode.h" 
    799 +#include "LzmaDecode.c" 
    800 + 
    801 +void __div0(void) 
    802 +{ 
    803 +} 
    804 + 
    805 +static int read_byte(void *object, const unsigned char **buffer, SizeT *bufferSize); 
    806 + 
    807 +/* 
    808 + * Do the lzma decompression 
    809 + */ 
    810 +static int unlzma(void) 
    811 +{ 
    812 + 
    813 +       unsigned int i; 
    814 +       CLzmaDecoderState state; 
    815 +       unsigned int uncompressedSize = 0; 
    816 + 
    817 +       ILzmaInCallback callback; 
    818 +       callback.Read = read_byte; 
    819 + 
    820 +       /* lzma args */ 
    821 +       i = get_byte(); 
    822 +       state.Properties.lc = i % 9, i = i / 9; 
    823 +       state.Properties.lp = i % 5, state.Properties.pb = i / 5; 
    824 + 
    825 +       /* skip dictionary size */ 
    826 +       for (i = 0; i < 4; i++) 
    827 +               get_byte(); 
    828 +       /* get uncompressed size */ 
    829 +       uncompressedSize = (get_byte()) + 
    830 +               (get_byte() << 8) + 
    831 +               (get_byte() << 16) + 
    832 +               (get_byte() << 24); 
    833 + 
    834 +       /* skip high order bytes */ 
    835 +       for (i = 0; i < 4; i++) 
    836 +               get_byte(); 
    837 +       /* point it beyond uncompresedSize */ 
    838 +       state.Probs = (CProb *) (output_data + uncompressedSize); 
    839 + 
    840 +       /* decompress kernel */ 
    841 +       if (LzmaDecode(&state, &callback, 
    842 +               (unsigned char *)output_data, uncompressedSize, &i) == LZMA_RESULT_OK) { 
    843 +               if (i != uncompressedSize) 
    844 +                       error("kernel corrupted!\n"); 
    845 +               /* copy it back to low_buffer */ 
    846 +               bytes_out = i; 
    847 +               output_ptr = i; 
    848 +               return 0; 
    849 +       } 
    850 +       return 1; 
    851 +} 
    852 + 
    853 +static unsigned int icnt = 0; 
    854 + 
    855 +static int read_byte(void *object, const unsigned char **buffer, SizeT *bufferSize) 
    856 +{ 
    857 +       static unsigned char val; 
    858 +       *bufferSize = 1; 
    859 +       val = get_byte(); 
    860 +       *buffer = &val; 
    861 +       if (icnt++ % (1024 * 10) == 0) 
    862 +               putstr("."); 
    863 +       return LZMA_RESULT_OK; 
    864 +} 
    865 + 
    866 +#if 0 
    867  /* =========================================================================== 
    868   * Write the output window window[0..outcnt-1] and update crc and bytes_out. 
    869   * (Used for the decompressed data only.) 
    870 @@ -299,6 +369,7 @@ void flush_window(void) 
    871         outcnt = 0; 
    872         putstr("."); 
    873  } 
    874 +#endif 
    875   
     101- 
     102-/* =========================================================================== 
     103- * Fill the input buffer. This is called only when the buffer is empty 
     104- * and at least one byte is really needed. 
     105- */ 
     106-int fill_inbuf(void) 
     107-{ 
     108-       if (insize != 0) 
     109-               error("ran out of input data"); 
     110- 
     111-       inbuf = input_data; 
     112-       insize = &input_data_end[0] - &input_data[0]; 
     113- 
     114-       inptr = 1; 
     115-       return inbuf[0]; 
     116-} 
     117- 
     118-/* =========================================================================== 
     119- * Write the output window window[0..outcnt-1] and update crc and bytes_out. 
     120- * (Used for the decompressed data only.) 
     121- */ 
     122-void flush_window(void) 
     123-{ 
     124-       ulg c = crc; 
     125-       unsigned n; 
     126-       uch *in, *out, ch; 
     127- 
     128-       in = window; 
     129-       out = &output_data[output_ptr]; 
     130-       for (n = 0; n < outcnt; n++) { 
     131-               ch = *out++ = *in++; 
     132-               c = crc_32_tab[((int)c ^ ch) & 0xff] ^ (c >> 8); 
     133-       } 
     134-       crc = c; 
     135-       bytes_out += (ulg)outcnt; 
     136-       output_ptr += (ulg)outcnt; 
     137-       outcnt = 0; 
     138-       putstr("."); 
     139-} 
     140- 
    876141 #ifndef arch_error 
    877142 #define arch_error(x) 
    878 @@ -328,9 +399,9 @@ decompress_kernel(ulg output_start, ulg  
     143 #endif 
     144+#include "unlzma.c" 
     145  
     146 static void error(char *x) 
     147 { 
     148@@ -317,20 +248,16 @@ static void error(char *x) 
     149  
     150 #ifndef STANDALONE_DEBUG 
     151  
     152-ulg 
     153-decompress_kernel(ulg output_start, ulg free_mem_ptr_p, ulg free_mem_ptr_end_p, 
     154+unsigned long 
     155+decompress_kernel(unsigned long output_start, unsigned long free_mem_ptr_p, unsigned long free_mem_ptr_end_p, 
     156                  int arch_id) 
     157 { 
     158-       output_data             = (uch *)output_start;  /* Points to kernel start */ 
     159-       free_mem_ptr            = free_mem_ptr_p; 
     160-       free_mem_end_ptr        = free_mem_ptr_end_p; 
     161        __machine_arch_type     = arch_id; 
    879162  
    880163        arch_decomp_setup(); 
    881164  
    882165-       makecrc(); 
    883 +       /* makecrc(); */ 
    884166        putstr("Uncompressing Linux..."); 
    885167-       gunzip(); 
    886 +       unlzma(); 
     168+       output_ptr += unlzma((u8 *) output_start, input_data, window); 
    887169        putstr(" done, booting the kernel.\n"); 
    888170        return output_ptr; 
    889171 } 
    890 @@ -342,9 +413,9 @@ int main() 
     172@@ -340,11 +267,8 @@ char output_buffer[1500*1024]; 
     173  
     174 int main() 
    891175 { 
    892         output_data = output_buffer; 
    893   
     176-       output_data = output_buffer; 
     177- 
    894178-       makecrc(); 
    895 +       /* makecrc(); */ 
    896179        putstr("Uncompressing Linux..."); 
    897180-       gunzip(); 
    898 +       unlzma(); 
     181+       unlzma((u8 *) output_buffer, input_data, window); 
    899182        putstr("done.\n"); 
    900183        return 0; 
     
    910193        .globl  input_data_end 
    911194 input_data_end: 
     195--- /dev/null 
     196+++ b/arch/arm/boot/compressed/unlzma.c 
     197@@ -0,0 +1,429 @@ 
     198+/* 
     199+ * Copyright (c) 2009  Felix Fietkau <nbd@openwrt.org> 
     200+ * 
     201+ * This program is free software; you can redistribute it and/or 
     202+ * modify it under the terms of the GNU General Public License 
     203+ * as published by the Free Software Foundation; either version 2, 
     204+ * or (at your option) any later version. 
     205+ * 
     206+ * This program is distributed in the hope that it will be useful, 
     207+ * but WITHOUT ANY WARRANTY; without even the implied warranty of 
     208+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
     209+ * GNU General Public License for more details. 
     210+ * 
     211+ * You should have received a copy of the GNU General Public License 
     212+ * along with this program; if not, write to the Free Software 
     213+ * Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 
     214+ * 
     215+ * uncompress.c 
     216+ */ 
     217+ 
     218+#include <linux/types.h> 
     219+#include <asm/byteorder.h> 
     220+#include "unlzma.h" 
     221+ 
     222+struct unlzma_ctx { 
     223+       const u8 *next_in; 
     224+       u8 *next_out; 
     225+       u8 *outbuf; 
     226+ 
     227+       /* reader state */ 
     228+       u32 code; 
     229+       u32 range; 
     230+       u32 bound; 
     231+ 
     232+       /* writer state */ 
     233+       u8 previous_byte; 
     234+       ssize_t pos; 
     235+ 
     236+       /* cstate */ 
     237+       int state; 
     238+       u32 rep0, rep1, rep2, rep3; 
     239+ 
     240+       void *workspace; 
     241+} ctx; 
     242+ 
     243+static int inbs = 0; 
     244+static inline u8 
     245+rc_read(void) 
     246+{ 
     247+#if 0 
     248+       if (unlikely(++inbs > 16 * 1024)) { 
     249+               putstr("."); 
     250+               inbs = 0; 
     251+       } 
     252+#endif 
     253+       return *(ctx.next_in++); 
     254+} 
     255+ 
     256+ 
     257+static inline void 
     258+rc_get_code(void) 
     259+{ 
     260+       ctx.code = (ctx.code << 8) | rc_read(); 
     261+} 
     262+ 
     263+static inline void 
     264+rc_normalize(void) 
     265+{ 
     266+       if (ctx.range < (1 << RC_TOP_BITS)) { 
     267+               ctx.range <<= 8; 
     268+               rc_get_code(); 
     269+       } 
     270+} 
     271+ 
     272+static inline int 
     273+rc_is_bit_0(u16 *p) 
     274+{ 
     275+       rc_normalize(); 
     276+       ctx.bound = *p * (ctx.range >> RC_MODEL_TOTAL_BITS); 
     277+       return ctx.code < ctx.bound; 
     278+} 
     279+ 
     280+static inline void 
     281+rc_update_bit_0(u16 *p) 
     282+{ 
     283+       ctx.range = ctx.bound; 
     284+       *p += ((1 << RC_MODEL_TOTAL_BITS) - *p) >> RC_MOVE_BITS; 
     285+} 
     286+ 
     287+static inline void 
     288+rc_update_bit_1(u16 *p) 
     289+{ 
     290+       ctx.range -= ctx.bound; 
     291+       ctx.code -= ctx.bound; 
     292+       *p -= *p >> RC_MOVE_BITS; 
     293+} 
     294+ 
     295+static inline bool 
     296+rc_get_bit(u16 *p, int *symbol) 
     297+{ 
     298+       if (rc_is_bit_0(p)) { 
     299+               rc_update_bit_0(p); 
     300+               *symbol *= 2; 
     301+               return 0; 
     302+       } else { 
     303+               rc_update_bit_1(p); 
     304+               *symbol = *symbol * 2 + 1; 
     305+               return 1; 
     306+       } 
     307+} 
     308+ 
     309+static inline int 
     310+rc_direct_bit(void) 
     311+{ 
     312+       rc_normalize(); 
     313+       ctx.range >>= 1; 
     314+       if (ctx.code >= ctx.range) { 
     315+               ctx.code -= ctx.range; 
     316+               return 1; 
     317+       } 
     318+       return 0; 
     319+} 
     320+ 
     321+static inline void 
     322+rc_bit_tree_decode(u16 *p, int num_levels, int *symbol) 
     323+{ 
     324+       int i = num_levels; 
     325+ 
     326+       *symbol = 1; 
     327+       while (i--) 
     328+               rc_get_bit(p + *symbol, symbol); 
     329+       *symbol -= 1 << num_levels; 
     330+} 
     331+ 
     332+static inline u8 
     333+peek_old_byte(u32 offs) 
     334+{ 
     335+       u32 pos = ctx.pos - offs; 
     336+       return ctx.outbuf[pos]; 
     337+} 
     338+ 
     339+static inline void 
     340+write_byte(u8 byte) 
     341+{ 
     342+       ctx.previous_byte = byte; 
     343+       *(ctx.next_out++) = byte; 
     344+       ctx.pos++; 
     345+} 
     346+ 
     347+ 
     348+static inline void 
     349+copy_byte(u32 offs) 
     350+{ 
     351+       write_byte(peek_old_byte(offs)); 
     352+} 
     353+ 
     354+static inline void 
     355+copy_bytes(u32 rep0, int len) 
     356+{ 
     357+       do { 
     358+               copy_byte(rep0); 
     359+               len--; 
     360+       } while (len != 0); 
     361+} 
     362+ 
     363+static inline void 
     364+process_bit0(u16 *p, int pos_state, u16 *prob, 
     365+             int lc, u32 literal_pos_mask) 
     366+{ 
     367+       int mi = 1; 
     368+       rc_update_bit_0(prob); 
     369+       prob = (p + LZMA_LITERAL + 
     370+               (LZMA_LIT_SIZE 
     371+                * (((ctx.pos & literal_pos_mask) << lc) 
     372+                   + (ctx.previous_byte >> (8 - lc)))) 
     373+               ); 
     374+ 
     375+       if (ctx.state >= LZMA_NUM_LIT_STATES) { 
     376+               int match_byte = peek_old_byte(ctx.rep0); 
     377+               do { 
     378+                       u16 bit; 
     379+                       u16 *prob_lit; 
     380+ 
     381+                       match_byte <<= 1; 
     382+                       bit = match_byte & 0x100; 
     383+                       prob_lit = prob + 0x100 + bit + mi; 
     384+                       if (rc_get_bit(prob_lit, &mi) != !!bit) 
     385+                               break; 
     386+               } while (mi < 0x100); 
     387+       } 
     388+       while (mi < 0x100) { 
     389+               u16 *prob_lit = prob + mi; 
     390+               rc_get_bit(prob_lit, &mi); 
     391+       } 
     392+       write_byte(mi); 
     393+       if (ctx.state < 4) 
     394+               ctx.state = 0; 
     395+       else if (ctx.state < 10) 
     396+               ctx.state -= 3; 
     397+       else 
     398+               ctx.state -= 6; 
     399+} 
     400+ 
     401+static inline void 
     402+process_bit1(u16 *p, int pos_state, u16 *prob) 
     403+{ 
     404+       int offset; 
     405+       u16 *prob_len; 
     406+       int num_bits; 
     407+       int len; 
     408+ 
     409+       rc_update_bit_1(prob); 
     410+       prob = p + LZMA_IS_REP + ctx.state; 
     411+       if (rc_is_bit_0(prob)) { 
     412+               rc_update_bit_0(prob); 
     413+               ctx.rep3 = ctx.rep2; 
     414+               ctx.rep2 = ctx.rep1; 
     415+               ctx.rep1 = ctx.rep0; 
     416+               ctx.state = ctx.state < LZMA_NUM_LIT_STATES ? 0 : 3; 
     417+               prob = p + LZMA_LEN_CODER; 
     418+       } else { 
     419+               rc_update_bit_1(prob); 
     420+               prob = p + LZMA_IS_REP_G0 + ctx.state; 
     421+               if (rc_is_bit_0(prob)) { 
     422+                       rc_update_bit_0(prob); 
     423+                       prob = (p + LZMA_IS_REP_0_LONG 
     424+                               + (ctx.state << 
     425+                                  LZMA_NUM_POS_BITS_MAX) + 
     426+                               pos_state); 
     427+                       if (rc_is_bit_0(prob)) { 
     428+                               rc_update_bit_0(prob); 
     429+ 
     430+                               ctx.state = ctx.state < LZMA_NUM_LIT_STATES ? 
     431+                                       9 : 11; 
     432+                               copy_byte(ctx.rep0); 
     433+                               return; 
     434+                       } else { 
     435+                               rc_update_bit_1(prob); 
     436+                       } 
     437+               } else { 
     438+                       u32 distance; 
     439+ 
     440+                       rc_update_bit_1(prob); 
     441+                       prob = p + LZMA_IS_REP_G1 + ctx.state; 
     442+                       if (rc_is_bit_0(prob)) { 
     443+                               rc_update_bit_0(prob); 
     444+                               distance = ctx.rep1; 
     445+                       } else { 
     446+                               rc_update_bit_1(prob); 
     447+                               prob = p + LZMA_IS_REP_G2 + ctx.state; 
     448+                               if (rc_is_bit_0(prob)) { 
     449+                                       rc_update_bit_0(prob); 
     450+                                       distance = ctx.rep2; 
     451+                               } else { 
     452+                                       rc_update_bit_1(prob); 
     453+                                       distance = ctx.rep3; 
     454+                                       ctx.rep3 = ctx.rep2; 
     455+                               } 
     456+                               ctx.rep2 = ctx.rep1; 
     457+                       } 
     458+                       ctx.rep1 = ctx.rep0; 
     459+                       ctx.rep0 = distance; 
     460+               } 
     461+               ctx.state = ctx.state < LZMA_NUM_LIT_STATES ? 8 : 11; 
     462+               prob = p + LZMA_REP_LEN_CODER; 
     463+       } 
     464+ 
     465+       prob_len = prob + LZMA_LEN_CHOICE; 
     466+       if (rc_is_bit_0(prob_len)) { 
     467+               rc_update_bit_0(prob_len); 
     468+               prob_len = (prob + LZMA_LEN_LOW 
     469+                           + (pos_state << 
     470+                              LZMA_LEN_NUM_LOW_BITS)); 
     471+               offset = 0; 
     472+               num_bits = LZMA_LEN_NUM_LOW_BITS; 
     473+       } else { 
     474+               rc_update_bit_1(prob_len); 
     475+               prob_len = prob + LZMA_LEN_CHOICE_2; 
     476+               if (rc_is_bit_0(prob_len)) { 
     477+                       rc_update_bit_0(prob_len); 
     478+                       prob_len = (prob + LZMA_LEN_MID 
     479+                                   + (pos_state << 
     480+                                      LZMA_LEN_NUM_MID_BITS)); 
     481+                       offset = 1 << LZMA_LEN_NUM_LOW_BITS; 
     482+                       num_bits = LZMA_LEN_NUM_MID_BITS; 
     483+               } else { 
     484+                       rc_update_bit_1(prob_len); 
     485+                       prob_len = prob + LZMA_LEN_HIGH; 
     486+                       offset = ((1 << LZMA_LEN_NUM_LOW_BITS) 
     487+                                 + (1 << LZMA_LEN_NUM_MID_BITS)); 
     488+                       num_bits = LZMA_LEN_NUM_HIGH_BITS; 
     489+               } 
     490+       } 
     491+ 
     492+       rc_bit_tree_decode(prob_len, num_bits, &len); 
     493+       len += offset; 
     494+ 
     495+       if (ctx.state < 4) { 
     496+               int pos_slot; 
     497+ 
     498+               ctx.state += LZMA_NUM_LIT_STATES; 
     499+               prob = 
     500+                       p + LZMA_POS_SLOT + 
     501+                       ((len < 
     502+                         LZMA_NUM_LEN_TO_POS_STATES ? len : 
     503+                         LZMA_NUM_LEN_TO_POS_STATES - 1) 
     504+                        << LZMA_NUM_POS_SLOT_BITS); 
     505+               rc_bit_tree_decode(prob, 
     506+                                  LZMA_NUM_POS_SLOT_BITS, 
     507+                                  &pos_slot); 
     508+               if (pos_slot >= LZMA_START_POS_MODEL_INDEX) { 
     509+                       int i, mi; 
     510+                       num_bits = (pos_slot >> 1) - 1; 
     511+                       ctx.rep0 = 2 | (pos_slot & 1); 
     512+                       if (pos_slot < LZMA_END_POS_MODEL_INDEX) { 
     513+                               ctx.rep0 <<= num_bits; 
     514+                               prob = p + LZMA_SPEC_POS + 
     515+                                       ctx.rep0 - pos_slot - 1; 
     516+                       } else { 
     517+                               num_bits -= LZMA_NUM_ALIGN_BITS; 
     518+                               while (num_bits--) 
     519+                                       ctx.rep0 = (ctx.rep0 << 1) | 
     520+                                               rc_direct_bit(); 
     521+                               prob = p + LZMA_ALIGN; 
     522+                               ctx.rep0 <<= LZMA_NUM_ALIGN_BITS; 
     523+                               num_bits = LZMA_NUM_ALIGN_BITS; 
     524+                       } 
     525+                       i = 1; 
     526+                       mi = 1; 
     527+                       while (num_bits--) { 
     528+                               if (rc_get_bit(prob + mi, &mi)) 
     529+                                       ctx.rep0 |= i; 
     530+                               i <<= 1; 
     531+                       } 
     532+               } else 
     533+                       ctx.rep0 = pos_slot; 
     534+               if (++(ctx.rep0) == 0) 
     535+                       return; 
     536+       } 
     537+ 
     538+       len += LZMA_MATCH_MIN_LEN; 
     539+ 
     540+       copy_bytes(ctx.rep0, len); 
     541+} 
     542+ 
     543+ 
     544+static int 
     545+do_unlzma(void) 
     546+{ 
     547+       u8 hdr_buf[sizeof(struct lzma_header)]; 
     548+       struct lzma_header *header = (struct lzma_header *)hdr_buf; 
     549+       u32 pos_state_mask; 
     550+       u32 literal_pos_mask; 
     551+       int lc, pb, lp; 
     552+       int num_probs; 
     553+       int i, mi; 
     554+       u16 *p; 
     555+ 
     556+       for (i = 0; i < sizeof(struct lzma_header); i++) { 
     557+               hdr_buf[i] = rc_read(); 
     558+       } 
     559+ 
     560+       ctx.pos = 0; 
     561+       ctx.state = 0; 
     562+       ctx.rep0 = ctx.rep1 = ctx.rep2 = ctx.rep3 = 1; 
     563+ 
     564+       ctx.previous_byte = 0; 
     565+       ctx.code = 0; 
     566+       ctx.range = 0xFFFFFFFF; 
     567+ 
     568+       if (header->pos >= (9 * 5 * 5)) 
     569+               return -1; 
     570+ 
     571+       mi = 0; 
     572+       lc = header->pos; 
     573+       while (lc >= 9) { 
     574+               mi++; 
     575+               lc -= 9; 
     576+       } 
     577+       pb = 0; 
     578+       lp = mi; 
     579+       while (lp >= 5) { 
     580+               pb++; 
     581+               lp -= 5; 
     582+       } 
     583+       pos_state_mask = (1 << pb) - 1; 
     584+       literal_pos_mask = (1 << lp) - 1; 
     585+ 
     586+       p = (u16 *) ctx.workspace; 
     587+       if (!p) 
     588+               return -1; 
     589+ 
     590+       num_probs = LZMA_LITERAL + (LZMA_LIT_SIZE << (lc + lp)); 
     591+       for (i = 0; i < num_probs; i++) 
     592+               p[i] = (1 << RC_MODEL_TOTAL_BITS) >> 1; 
     593+ 
     594+       for (i = 0; i < 5; i++) 
     595+               rc_get_code(); 
     596+ 
     597+       while (1) { 
     598+               int pos_state = ctx.pos & pos_state_mask; 
     599+               u16 *prob = p + LZMA_IS_MATCH + 
     600+                       (ctx.state << LZMA_NUM_POS_BITS_MAX) + pos_state; 
     601+               if (rc_is_bit_0(prob)) 
     602+                       process_bit0(p, pos_state, prob, 
     603+                                    lc, literal_pos_mask); 
     604+               else { 
     605+                       process_bit1(p, pos_state, prob); 
     606+                       if (ctx.rep0 == 0) 
     607+                               break; 
     608+               } 
     609+       } 
     610+ 
     611+       return ctx.pos; 
     612+} 
     613+ 
     614+ 
     615+static int unlzma(unsigned char *dest, const unsigned char *src, unsigned char *workspace) 
     616+{ 
     617+       memset(&ctx, 0, sizeof(ctx)); 
     618+       ctx.outbuf = dest; 
     619+       ctx.next_in = src; 
     620+       ctx.next_out = dest; 
     621+       ctx.workspace = workspace; 
     622+ 
     623+       return do_unlzma(); 
     624+} 
     625+ 
     626+ 
     627--- /dev/null 
     628+++ b/arch/arm/boot/compressed/unlzma.h 
     629@@ -0,0 +1,81 @@ 
     630+/* LZMA uncompresion module for pcomp 
     631+ * Copyright (C) 2009  Felix Fietkau <nbd@openwrt.org> 
     632+ * 
     633+ * Based on: 
     634+ *  Initial Linux kernel adaptation 
     635+ *  Copyright (C) 2006  Alain < alain@knaff.lu > 
     636+ * 
     637+ *  Based on small lzma deflate implementation/Small range coder 
     638+ *  implementation for lzma. 
     639+ *  Copyright (C) 2006  Aurelien Jacobs < aurel@gnuage.org > 
     640+ * 
     641+ *  Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/) 
     642+ *  Copyright (C) 1999-2005  Igor Pavlov 
     643+ * 
     644+ * This program is free software; you can redistribute it and/or modify it 
     645+ * under the terms of the GNU General Public License version 2 as published 
     646+ * by the Free Software Foundation. 
     647+ */ 
     648+#ifndef __UNLZMA_H 
     649+#define __UNLZMA_H 
     650+ 
     651+struct lzma_header { 
     652+       __u8 pos; 
     653+       __le32 dict_size; 
     654+       __le64 uncompr_size; 
     655+} __attribute__ ((packed)); 
     656+ 
     657+ 
     658+#define RC_TOP_BITS 24 
     659+#define RC_MOVE_BITS 5 
     660+#define RC_MODEL_TOTAL_BITS 11 
     661+ 
     662+#define LZMA_BASE_SIZE 1846 
     663+#define LZMA_LIT_SIZE 768 
     664+ 
     665+#define LZMA_NUM_POS_BITS_MAX 4 
     666+ 
     667+#define LZMA_LEN_NUM_LOW_BITS 3 
     668+#define LZMA_LEN_NUM_MID_BITS 3 
     669+#define LZMA_LEN_NUM_HIGH_BITS 8 
     670+ 
     671+#define LZMA_LEN_CHOICE 0 
     672+#define LZMA_LEN_CHOICE_2 (LZMA_LEN_CHOICE + 1) 
     673+#define LZMA_LEN_LOW (LZMA_LEN_CHOICE_2 + 1) 
     674+#define LZMA_LEN_MID (LZMA_LEN_LOW \ 
     675+                     + (1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_LOW_BITS))) 
     676+#define LZMA_LEN_HIGH (LZMA_LEN_MID \ 
     677+                      +(1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_MID_BITS))) 
     678+#define LZMA_NUM_LEN_PROBS (LZMA_LEN_HIGH + (1 << LZMA_LEN_NUM_HIGH_BITS)) 
     679+ 
     680+#define LZMA_NUM_STATES 12 
     681+#define LZMA_NUM_LIT_STATES 7 
     682+ 
     683+#define LZMA_START_POS_MODEL_INDEX 4 
     684+#define LZMA_END_POS_MODEL_INDEX 14 
     685+#define LZMA_NUM_FULL_DISTANCES (1 << (LZMA_END_POS_MODEL_INDEX >> 1)) 
     686+ 
     687+#define LZMA_NUM_POS_SLOT_BITS 6 
     688+#define LZMA_NUM_LEN_TO_POS_STATES 4 
     689+ 
     690+#define LZMA_NUM_ALIGN_BITS 4 
     691+ 
     692+#define LZMA_MATCH_MIN_LEN 2 
     693+ 
     694+#define LZMA_IS_MATCH 0 
     695+#define LZMA_IS_REP (LZMA_IS_MATCH + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS_MAX)) 
     696+#define LZMA_IS_REP_G0 (LZMA_IS_REP + LZMA_NUM_STATES) 
     697+#define LZMA_IS_REP_G1 (LZMA_IS_REP_G0 + LZMA_NUM_STATES) 
     698+#define LZMA_IS_REP_G2 (LZMA_IS_REP_G1 + LZMA_NUM_STATES) 
     699+#define LZMA_IS_REP_0_LONG (LZMA_IS_REP_G2 + LZMA_NUM_STATES) 
     700+#define LZMA_POS_SLOT (LZMA_IS_REP_0_LONG \ 
     701+                      + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS_MAX)) 
     702+#define LZMA_SPEC_POS (LZMA_POS_SLOT \ 
     703+                      +(LZMA_NUM_LEN_TO_POS_STATES << LZMA_NUM_POS_SLOT_BITS)) 
     704+#define LZMA_ALIGN (LZMA_SPEC_POS \ 
     705+                   + LZMA_NUM_FULL_DISTANCES - LZMA_END_POS_MODEL_INDEX) 
     706+#define LZMA_LEN_CODER (LZMA_ALIGN + (1 << LZMA_NUM_ALIGN_BITS)) 
     707+#define LZMA_REP_LEN_CODER (LZMA_LEN_CODER + LZMA_NUM_LEN_PROBS) 
     708+#define LZMA_LITERAL (LZMA_REP_LEN_CODER + LZMA_NUM_LEN_PROBS) 
     709+ 
     710+#endif 
  • trunk/target/linux/generic-2.6/patches-2.6.30/998-openwrt_lzma_options.patch

    r16281 r16939  
    66 quiet_cmd_lzma = LZMA    $@ 
    77-cmd_lzma = (lzma -9 -c $< && $(size_append) $<) >$@ || (rm -f $@ ; false) 
    8 +cmd_lzma = lzma e $< $@ -lc1 -lp2 -pb2 
     8+cmd_lzma = lzma e $< $@ -lc1 -lp2 -pb2 -eos 
Note: See TracChangeset for help on using the changeset viewer.