openwrt/target/linux/generic-2.6/patches/002-squashfs_lzma.patch

   1 diff -Nur linux-2.6.12.5-brcm-squashfs/fs/squashfs/LzmaDecode.c linux-2.6.12.5-brcm-squashfs-lzma/fs/squashfs/LzmaDecode.c
   2 --- linux-2.6.12.5-brcm-squashfs/fs/squashfs/LzmaDecode.c       1970-01-01 01:00:00.000000000 +0100
   3 +++ linux-2.6.12.5-brcm-squashfs-lzma/fs/squashfs/LzmaDecode.c  2005-08-29 00:02:44.099124176 +0200
   4 @@ -0,0 +1,663 @@
   5 +/*
   6 +  LzmaDecode.c
   7 +  LZMA Decoder
   8 +
   9 +  LZMA SDK 4.05 Copyright (c) 1999-2004 Igor Pavlov (2004-08-25)
  10 +  http://www.7-zip.org/
  11 +
  12 +  LZMA SDK is licensed under two licenses:
  13 +  1) GNU Lesser General Public License (GNU LGPL)
  14 +  2) Common Public License (CPL)
  15 +  It means that you can select one of these two licenses and
  16 +  follow rules of that license.
  17 +
  18 +  SPECIAL EXCEPTION:
  19 +  Igor Pavlov, as the author of this code, expressly permits you to
  20 +  statically or dynamically link your code (or bind by name) to the
  21 +  interfaces of this file without subjecting your linked code to the
  22 +  terms of the CPL or GNU LGPL. Any modifications or additions
  23 +  to this file, however, are subject to the LGPL or CPL terms.
  24 +*/
  25 +
  26 +#include "LzmaDecode.h"
  27 +
  28 +#ifndef Byte
  29 +#define Byte unsigned char
  30 +#endif
  31 +
  32 +#define kNumTopBits 24
  33 +#define kTopValue ((UInt32)1 << kNumTopBits)
  34 +
  35 +#define kNumBitModelTotalBits 11
  36 +#define kBitModelTotal (1 << kNumBitModelTotalBits)
  37 +#define kNumMoveBits 5
  38 +
  39 +typedef struct _CRangeDecoder
  40 +{
  41 +  Byte *Buffer;
  42 +  Byte *BufferLim;
  43 +  UInt32 Range;
  44 +  UInt32 Code;
  45 +  #ifdef _LZMA_IN_CB
  46 +  ILzmaInCallback *InCallback;
  47 +  int Result;
  48 +  #endif
  49 +  int ExtraBytes;
  50 +} CRangeDecoder;
  51 +
  52 +Byte RangeDecoderReadByte(CRangeDecoder *rd)
  53 +{
  54 +  if (rd->Buffer == rd->BufferLim)
  55 +  {
  56 +    #ifdef _LZMA_IN_CB
  57 +    UInt32 size;
  58 +    rd->Result = rd->InCallback->Read(rd->InCallback, &rd->Buffer, &size);
  59 +    rd->BufferLim = rd->Buffer + size;
  60 +    if (size == 0)
  61 +    #endif
  62 +    {
  63 +      rd->ExtraBytes = 1;
  64 +      return 0xFF;
  65 +    }
  66 +  }
  67 +  return (*rd->Buffer++);
  68 +}
  69 +
  70 +/* #define ReadByte (*rd->Buffer++) */
  71 +#define ReadByte (RangeDecoderReadByte(rd))
  72 +
  73 +void RangeDecoderInit(CRangeDecoder *rd,
  74 +  #ifdef _LZMA_IN_CB
  75 +    ILzmaInCallback *inCallback
  76 +  #else
  77 +    Byte *stream, UInt32 bufferSize
  78 +  #endif
  79 +    )
  80 +{
  81 +  int i;
  82 +  #ifdef _LZMA_IN_CB
  83 +  rd->InCallback = inCallback;
  84 +  rd->Buffer = rd->BufferLim = 0;
  85 +  #else
  86 +  rd->Buffer = stream;
  87 +  rd->BufferLim = stream + bufferSize;
  88 +  #endif
  89 +  rd->ExtraBytes = 0;
  90 +  rd->Code = 0;
  91 +  rd->Range = (0xFFFFFFFF);
  92 +  for(i = 0; i < 5; i++)
  93 +    rd->Code = (rd->Code << 8) | ReadByte;
  94 +}
  95 +
  96 +#define RC_INIT_VAR UInt32 range = rd->Range; UInt32 code = rd->Code;
  97 +#define RC_FLUSH_VAR rd->Range = range; rd->Code = code;
  98 +#define RC_NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | ReadByte; }
  99 +
 100 +UInt32 RangeDecoderDecodeDirectBits(CRangeDecoder *rd, int numTotalBits)
 101 +{
 102 +  RC_INIT_VAR
 103 +  UInt32 result = 0;
 104 +  int i;
 105 +  for (i = numTotalBits; i > 0; i--)
 106 +  {
 107 +    /* UInt32 t; */
 108 +    range >>= 1;
 109 +
 110 +    result <<= 1;
 111 +    if (code >= range)
 112 +    {
 113 +      code -= range;
 114 +      result |= 1;
 115 +    }
 116 +    /*
 117 +    t = (code - range) >> 31;
 118 +    t &= 1;
 119 +    code -= range & (t - 1);
 120 +    result = (result + result) | (1 - t);
 121 +    */
 122 +    RC_NORMALIZE
 123 +  }
 124 +  RC_FLUSH_VAR
 125 +  return result;
 126 +}
 127 +
 128 +int RangeDecoderBitDecode(CProb *prob, CRangeDecoder *rd)
 129 +{
 130 +  UInt32 bound = (rd->Range >> kNumBitModelTotalBits) * *prob;
 131 +  if (rd->Code < bound)
 132 +  {
 133 +    rd->Range = bound;
 134 +    *prob += (kBitModelTotal - *prob) >> kNumMoveBits;
 135 +    if (rd->Range < kTopValue)
 136 +    {
 137 +      rd->Code = (rd->Code << 8) | ReadByte;
 138 +      rd->Range <<= 8;
 139 +    }
 140 +    return 0;
 141 +  }
 142 +  else
 143 +  {
 144 +    rd->Range -= bound;
 145 +    rd->Code -= bound;
 146 +    *prob -= (*prob) >> kNumMoveBits;
 147 +    if (rd->Range < kTopValue)
 148 +    {
 149 +      rd->Code = (rd->Code << 8) | ReadByte;
 150 +      rd->Range <<= 8;
 151 +    }
 152 +    return 1;
 153 +  }
 154 +}
 155 +
 156 +#define RC_GET_BIT2(prob, mi, A0, A1) \
 157 +  UInt32 bound = (range >> kNumBitModelTotalBits) * *prob; \
 158 +  if (code < bound) \
 159 +    { A0; range = bound; *prob += (kBitModelTotal - *prob) >> kNumMoveBits; mi <<= 1; } \
 160 +  else \
 161 +    { A1; range -= bound; code -= bound; *prob -= (*prob) >> kNumMoveBits; mi = (mi + mi) + 1; } \
 162 +  RC_NORMALIZE
 163 +
 164 +#define RC_GET_BIT(prob, mi) RC_GET_BIT2(prob, mi, ; , ;)
 165 +
 166 +int RangeDecoderBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd)
 167 +{
 168 +  int mi = 1;
 169 +  int i;
 170 +  #ifdef _LZMA_LOC_OPT
 171 +  RC_INIT_VAR
 172 +  #endif
 173 +  for(i = numLevels; i > 0; i--)
 174 +  {
 175 +    #ifdef _LZMA_LOC_OPT
 176 +    CProb *prob = probs + mi;
 177 +    RC_GET_BIT(prob, mi)
 178 +    #else
 179 +    mi = (mi + mi) + RangeDecoderBitDecode(probs + mi, rd);
 180 +    #endif
 181 +  }
 182 +  #ifdef _LZMA_LOC_OPT
 183 +  RC_FLUSH_VAR
 184 +  #endif
 185 +  return mi - (1 << numLevels);
 186 +}
 187 +
 188 +int RangeDecoderReverseBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd)
 189 +{
 190 +  int mi = 1;
 191 +  int i;
 192 +  int symbol = 0;
 193 +  #ifdef _LZMA_LOC_OPT
 194 +  RC_INIT_VAR
 195 +  #endif
 196 +  for(i = 0; i < numLevels; i++)
 197 +  {
 198 +    #ifdef _LZMA_LOC_OPT
 199 +    CProb *prob = probs + mi;
 200 +    RC_GET_BIT2(prob, mi, ; , symbol |= (1 << i))
 201 +    #else
 202 +    int bit = RangeDecoderBitDecode(probs + mi, rd);
 203 +    mi = mi + mi + bit;
 204 +    symbol |= (bit << i);
 205 +    #endif
 206 +  }
 207 +  #ifdef _LZMA_LOC_OPT
 208 +  RC_FLUSH_VAR
 209 +  #endif
 210 +  return symbol;
 211 +}
 212 +
 213 +Byte LzmaLiteralDecode(CProb *probs, CRangeDecoder *rd)
 214 +{
 215 +  int symbol = 1;
 216 +  #ifdef _LZMA_LOC_OPT
 217 +  RC_INIT_VAR
 218 +  #endif
 219 +  do
 220 +  {
 221 +    #ifdef _LZMA_LOC_OPT
 222 +    CProb *prob = probs + symbol;
 223 +    RC_GET_BIT(prob, symbol)
 224 +    #else
 225 +    symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd);
 226 +    #endif
 227 +  }
 228 +  while (symbol < 0x100);
 229 +  #ifdef _LZMA_LOC_OPT
 230 +  RC_FLUSH_VAR
 231 +  #endif
 232 +  return symbol;
 233 +}
 234 +
 235 +Byte LzmaLiteralDecodeMatch(CProb *probs, CRangeDecoder *rd, Byte matchByte)
 236 +{
 237 +  int symbol = 1;
 238 +  #ifdef _LZMA_LOC_OPT
 239 +  RC_INIT_VAR
 240 +  #endif
 241 +  do
 242 +  {
 243 +    int bit;
 244 +    int matchBit = (matchByte >> 7) & 1;
 245 +    matchByte <<= 1;
 246 +    #ifdef _LZMA_LOC_OPT
 247 +    {
 248 +      CProb *prob = probs + ((1 + matchBit) << 8) + symbol;
 249 +      RC_GET_BIT2(prob, symbol, bit = 0, bit = 1)
 250 +    }
 251 +    #else
 252 +    bit = RangeDecoderBitDecode(probs + ((1 + matchBit) << 8) + symbol, rd);
 253 +    symbol = (symbol << 1) | bit;
 254 +    #endif
 255 +    if (matchBit != bit)
 256 +    {
 257 +      while (symbol < 0x100)
 258 +      {
 259 +        #ifdef _LZMA_LOC_OPT
 260 +        CProb *prob = probs + symbol;
 261 +        RC_GET_BIT(prob, symbol)
 262 +        #else
 263 +        symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd);
 264 +        #endif
 265 +      }
 266 +      break;
 267 +    }
 268 +  }
 269 +  while (symbol < 0x100);
 270 +  #ifdef _LZMA_LOC_OPT
 271 +  RC_FLUSH_VAR
 272 +  #endif
 273 +  return symbol;
 274 +}
 275 +
 276 +#define kNumPosBitsMax 4
 277 +#define kNumPosStatesMax (1 << kNumPosBitsMax)
 278 +
 279 +#define kLenNumLowBits 3
 280 +#define kLenNumLowSymbols (1 << kLenNumLowBits)
 281 +#define kLenNumMidBits 3
 282 +#define kLenNumMidSymbols (1 << kLenNumMidBits)
 283 +#define kLenNumHighBits 8
 284 +#define kLenNumHighSymbols (1 << kLenNumHighBits)
 285 +
 286 +#define LenChoice 0
 287 +#define LenChoice2 (LenChoice + 1)
 288 +#define LenLow (LenChoice2 + 1)
 289 +#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
 290 +#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
 291 +#define kNumLenProbs (LenHigh + kLenNumHighSymbols)
 292 +
 293 +int LzmaLenDecode(CProb *p, CRangeDecoder *rd, int posState)
 294 +{
 295 +  if(RangeDecoderBitDecode(p + LenChoice, rd) == 0)
 296 +    return RangeDecoderBitTreeDecode(p + LenLow +
 297 +        (posState << kLenNumLowBits), kLenNumLowBits, rd);
 298 +  if(RangeDecoderBitDecode(p + LenChoice2, rd) == 0)
 299 +    return kLenNumLowSymbols + RangeDecoderBitTreeDecode(p + LenMid +
 300 +        (posState << kLenNumMidBits), kLenNumMidBits, rd);
 301 +  return kLenNumLowSymbols + kLenNumMidSymbols +
 302 +      RangeDecoderBitTreeDecode(p + LenHigh, kLenNumHighBits, rd);
 303 +}
 304 +
 305 +#define kNumStates 12
 306 +
 307 +#define kStartPosModelIndex 4
 308 +#define kEndPosModelIndex 14
 309 +#define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
 310 +
 311 +#define kNumPosSlotBits 6
 312 +#define kNumLenToPosStates 4
 313 +
 314 +#define kNumAlignBits 4
 315 +#define kAlignTableSize (1 << kNumAlignBits)
 316 +
 317 +#define kMatchMinLen 2
 318 +
 319 +#define IsMatch 0
 320 +#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
 321 +#define IsRepG0 (IsRep + kNumStates)
 322 +#define IsRepG1 (IsRepG0 + kNumStates)
 323 +#define IsRepG2 (IsRepG1 + kNumStates)
 324 +#define IsRep0Long (IsRepG2 + kNumStates)
 325 +#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
 326 +#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
 327 +#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
 328 +#define LenCoder (Align + kAlignTableSize)
 329 +#define RepLenCoder (LenCoder + kNumLenProbs)
 330 +#define Literal (RepLenCoder + kNumLenProbs)
 331 +
 332 +#if Literal != LZMA_BASE_SIZE
 333 +StopCompilingDueBUG
 334 +#endif
 335 +
 336 +#ifdef _LZMA_OUT_READ
 337 +
 338 +typedef struct _LzmaVarState
 339 +{
 340 +  CRangeDecoder RangeDecoder;
 341 +  Byte *Dictionary;
 342 +  UInt32 DictionarySize;
 343 +  UInt32 DictionaryPos;
 344 +  UInt32 GlobalPos;
 345 +  UInt32 Reps[4];
 346 +  int lc;
 347 +  int lp;
 348 +  int pb;
 349 +  int State;
 350 +  int PreviousIsMatch;
 351 +  int RemainLen;
 352 +} LzmaVarState;
 353 +
 354 +int LzmaDecoderInit(
 355 +    unsigned char *buffer, UInt32 bufferSize,
 356 +    int lc, int lp, int pb,
 357 +    unsigned char *dictionary, UInt32 dictionarySize,
 358 +    #ifdef _LZMA_IN_CB
 359 +    ILzmaInCallback *inCallback
 360 +    #else
 361 +    unsigned char *inStream, UInt32 inSize
 362 +    #endif
 363 +    )
 364 +{
 365 +  LzmaVarState *vs = (LzmaVarState *)buffer;
 366 +  CProb *p = (CProb *)(buffer + sizeof(LzmaVarState));
 367 +  UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + lp));
 368 +  UInt32 i;
 369 +  if (bufferSize < numProbs * sizeof(CProb) + sizeof(LzmaVarState))
 370 +    return LZMA_RESULT_NOT_ENOUGH_MEM;
 371 +  vs->Dictionary = dictionary;
 372 +  vs->DictionarySize = dictionarySize;
 373 +  vs->DictionaryPos = 0;
 374 +  vs->GlobalPos = 0;
 375 +  vs->Reps[0] = vs->Reps[1] = vs->Reps[2] = vs->Reps[3] = 1;
 376 +  vs->lc = lc;
 377 +  vs->lp = lp;
 378 +  vs->pb = pb;
 379 +  vs->State = 0;
 380 +  vs->PreviousIsMatch = 0;
 381 +  vs->RemainLen = 0;
 382 +  dictionary[dictionarySize - 1] = 0;
 383 +  for (i = 0; i < numProbs; i++)
 384 +    p[i] = kBitModelTotal >> 1;
 385 +  RangeDecoderInit(&vs->RangeDecoder,
 386 +      #ifdef _LZMA_IN_CB
 387 +      inCallback
 388 +      #else
 389 +      inStream, inSize
 390 +      #endif
 391 +  );
 392 +  return LZMA_RESULT_OK;
 393 +}
 394 +
 395 +int LzmaDecode(unsigned char *buffer,
 396 +    unsigned char *outStream, UInt32 outSize,
 397 +    UInt32 *outSizeProcessed)
 398 +{
 399 +  LzmaVarState *vs = (LzmaVarState *)buffer;
 400 +  CProb *p = (CProb *)(buffer + sizeof(LzmaVarState));
 401 +  CRangeDecoder rd = vs->RangeDecoder;
 402 +  int state = vs->State;
 403 +  int previousIsMatch = vs->PreviousIsMatch;
 404 +  Byte previousByte;
 405 +  UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
 406 +  UInt32 nowPos = 0;
 407 +  UInt32 posStateMask = (1 << (vs->pb)) - 1;
 408 +  UInt32 literalPosMask = (1 << (vs->lp)) - 1;
 409 +  int lc = vs->lc;
 410 +  int len = vs->RemainLen;
 411 +  UInt32 globalPos = vs->GlobalPos;
 412 +
 413 +  Byte *dictionary = vs->Dictionary;
 414 +  UInt32 dictionarySize = vs->DictionarySize;
 415 +  UInt32 dictionaryPos = vs->DictionaryPos;
 416 +
 417 +  if (len == -1)
 418 +  {
 419 +    *outSizeProcessed = 0;
 420 +    return LZMA_RESULT_OK;
 421 +  }
 422 +
 423 +  while(len > 0 && nowPos < outSize)
 424 +  {
 425 +    UInt32 pos = dictionaryPos - rep0;
 426 +    if (pos >= dictionarySize)
 427 +      pos += dictionarySize;
 428 +    outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
 429 +    if (++dictionaryPos == dictionarySize)
 430 +      dictionaryPos = 0;
 431 +    len--;
 432 +  }
 433 +  if (dictionaryPos == 0)
 434 +    previousByte = dictionary[dictionarySize - 1];
 435 +  else
 436 +    previousByte = dictionary[dictionaryPos - 1];
 437 +#else
 438 +
 439 +int LzmaDecode(
 440 +    Byte *buffer, UInt32 bufferSize,
 441 +    int lc, int lp, int pb,
 442 +    #ifdef _LZMA_IN_CB
 443 +    ILzmaInCallback *inCallback,
 444 +    #else
 445 +    unsigned char *inStream, UInt32 inSize,
 446 +    #endif
 447 +    unsigned char *outStream, UInt32 outSize,
 448 +    UInt32 *outSizeProcessed)
 449 +{
 450 +  UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + lp));
 451 +  CProb *p = (CProb *)buffer;
 452 +  CRangeDecoder rd;
 453 +  UInt32 i;
 454 +  int state = 0;
 455 +  int previousIsMatch = 0;
 456 +  Byte previousByte = 0;
 457 +  UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
 458 +  UInt32 nowPos = 0;
 459 +  UInt32 posStateMask = (1 << pb) - 1;
 460 +  UInt32 literalPosMask = (1 << lp) - 1;
 461 +  int len = 0;
 462 +  if (bufferSize < numProbs * sizeof(CProb))
 463 +    return LZMA_RESULT_NOT_ENOUGH_MEM;
 464 +  for (i = 0; i < numProbs; i++)
 465 +    p[i] = kBitModelTotal >> 1;
 466 +  RangeDecoderInit(&rd,
 467 +      #ifdef _LZMA_IN_CB
 468 +      inCallback
 469 +      #else
 470 +      inStream, inSize
 471 +      #endif
 472 +      );
 473 +#endif
 474 +
 475 +  *outSizeProcessed = 0;
 476 +  while(nowPos < outSize)
 477 +  {
 478 +    int posState = (int)(
 479 +        (nowPos
 480 +        #ifdef _LZMA_OUT_READ
 481 +        + globalPos
 482 +        #endif
 483 +        )
 484 +        & posStateMask);
 485 +    #ifdef _LZMA_IN_CB
 486 +    if (rd.Result != LZMA_RESULT_OK)
 487 +      return rd.Result;
 488 +    #endif
 489 +    if (rd.ExtraBytes != 0)
 490 +      return LZMA_RESULT_DATA_ERROR;
 491 +    if (RangeDecoderBitDecode(p + IsMatch + (state << kNumPosBitsMax) + posState, &rd) == 0)
 492 +    {
 493 +      CProb *probs = p + Literal + (LZMA_LIT_SIZE *
 494 +        (((
 495 +        (nowPos
 496 +        #ifdef _LZMA_OUT_READ
 497 +        + globalPos
 498 +        #endif
 499 +        )
 500 +        & literalPosMask) << lc) + (previousByte >> (8 - lc))));
 501 +
 502 +      if (state < 4) state = 0;
 503 +      else if (state < 10) state -= 3;
 504 +      else state -= 6;
 505 +      if (previousIsMatch)
 506 +      {
 507 +        Byte matchByte;
 508 +        #ifdef _LZMA_OUT_READ
 509 +        UInt32 pos = dictionaryPos - rep0;
 510 +        if (pos >= dictionarySize)
 511 +          pos += dictionarySize;
 512 +        matchByte = dictionary[pos];
 513 +        #else
 514 +        matchByte = outStream[nowPos - rep0];
 515 +        #endif
 516 +        previousByte = LzmaLiteralDecodeMatch(probs, &rd, matchByte);
 517 +        previousIsMatch = 0;
 518 +      }
 519 +      else
 520 +        previousByte = LzmaLiteralDecode(probs, &rd);
 521 +      outStream[nowPos++] = previousByte;
 522 +      #ifdef _LZMA_OUT_READ
 523 +      dictionary[dictionaryPos] = previousByte;
 524 +      if (++dictionaryPos == dictionarySize)
 525 +        dictionaryPos = 0;
 526 +      #endif
 527 +    }
 528 +    else
 529 +    {
 530 +      previousIsMatch = 1;
 531 +      if (RangeDecoderBitDecode(p + IsRep + state, &rd) == 1)
 532 +      {
 533 +        if (RangeDecoderBitDecode(p + IsRepG0 + state, &rd) == 0)
 534 +        {
 535 +          if (RangeDecoderBitDecode(p + IsRep0Long + (state << kNumPosBitsMax) + posState, &rd) == 0)
 536 +          {
 537 +            #ifdef _LZMA_OUT_READ
 538 +            UInt32 pos;
 539 +            #endif
 540 +            if (
 541 +               (nowPos
 542 +                #ifdef _LZMA_OUT_READ
 543 +                + globalPos
 544 +                #endif
 545 +               )
 546 +               == 0)
 547 +              return LZMA_RESULT_DATA_ERROR;
 548 +            state = state < 7 ? 9 : 11;
 549 +            #ifdef _LZMA_OUT_READ
 550 +            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 +            outStream[nowPos++] = previousByte;
 561 +            continue;
 562 +          }
 563 +        }
 564 +        else
 565 +        {
 566 +          UInt32 distance;
 567 +          if(RangeDecoderBitDecode(p + IsRepG1 + state, &rd) == 0)
 568 +            distance = rep1;
 569 +          else
 570 +          {
 571 +            if(RangeDecoderBitDecode(p + IsRepG2 + state, &rd) == 0)
 572 +              distance = rep2;
 573 +            else
 574 +            {
 575 +              distance = rep3;
 576 +              rep3 = rep2;
 577 +            }
 578 +            rep2 = rep1;
 579 +          }
 580 +          rep1 = rep0;
 581 +          rep0 = distance;
 582 +        }
 583 +        len = LzmaLenDecode(p + RepLenCoder, &rd, posState);
 584 +        state = state < 7 ? 8 : 11;
 585 +      }
 586 +      else
 587 +      {
 588 +        int posSlot;
 589 +        rep3 = rep2;
 590 +        rep2 = rep1;
 591 +        rep1 = rep0;
 592 +        state = state < 7 ? 7 : 10;
 593 +        len = LzmaLenDecode(p + LenCoder, &rd, posState);
 594 +        posSlot = RangeDecoderBitTreeDecode(p + PosSlot +
 595 +            ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
 596 +            kNumPosSlotBits), kNumPosSlotBits, &rd);
 597 +        if (posSlot >= kStartPosModelIndex)
 598 +        {
 599 +          int numDirectBits = ((posSlot >> 1) - 1);
 600 +          rep0 = ((2 | ((UInt32)posSlot & 1)) << numDirectBits);
 601 +          if (posSlot < kEndPosModelIndex)
 602 +          {
 603 +            rep0 += RangeDecoderReverseBitTreeDecode(
 604 +                p + SpecPos + rep0 - posSlot - 1, numDirectBits, &rd);
 605 +          }
 606 +          else
 607 +          {
 608 +            rep0 += RangeDecoderDecodeDirectBits(&rd,
 609 +                numDirectBits - kNumAlignBits) << kNumAlignBits;
 610 +            rep0 += RangeDecoderReverseBitTreeDecode(p + Align, kNumAlignBits, &rd);
 611 +          }
 612 +        }
 613 +        else
 614 +          rep0 = posSlot;
 615 +        rep0++;
 616 +      }
 617 +      if (rep0 == (UInt32)(0))
 618 +      {
 619 +        /* it's for stream version */
 620 +        len = -1;
 621 +        break;
 622 +      }
 623 +      if (rep0 > nowPos
 624 +        #ifdef _LZMA_OUT_READ
 625 +        + globalPos
 626 +        #endif
 627 +        )
 628 +      {
 629 +        return LZMA_RESULT_DATA_ERROR;
 630 +      }
 631 +      len += kMatchMinLen;
 632 +      do
 633 +      {
 634 +        #ifdef _LZMA_OUT_READ
 635 +        UInt32 pos = dictionaryPos - rep0;
 636 +        if (pos >= dictionarySize)
 637 +          pos += dictionarySize;
 638 +        previousByte = dictionary[pos];
 639 +        dictionary[dictionaryPos] = previousByte;
 640 +        if (++dictionaryPos == dictionarySize)
 641 +          dictionaryPos = 0;
 642 +        #else
 643 +        previousByte = outStream[nowPos - rep0];
 644 +        #endif
 645 +        outStream[nowPos++] = previousByte;
 646 +        len--;
 647 +      }
 648 +      while(len > 0 && nowPos < outSize);
 649 +    }
 650 +  }
 651 +
 652 +  #ifdef _LZMA_OUT_READ
 653 +  vs->RangeDecoder = rd;
 654 +  vs->DictionaryPos = dictionaryPos;
 655 +  vs->GlobalPos = globalPos + nowPos;
 656 +  vs->Reps[0] = rep0;
 657 +  vs->Reps[1] = rep1;
 658 +  vs->Reps[2] = rep2;
 659 +  vs->Reps[3] = rep3;
 660 +  vs->State = state;
 661 +  vs->PreviousIsMatch = previousIsMatch;
 662 +  vs->RemainLen = len;
 663 +  #endif
 664 +
 665 +  *outSizeProcessed = nowPos;
 666 +  return LZMA_RESULT_OK;
 667 +}
 668 diff -Nur linux-2.6.12.5-brcm-squashfs/fs/squashfs/LzmaDecode.h linux-2.6.12.5-brcm-squashfs-lzma/fs/squashfs/LzmaDecode.h
 669 --- linux-2.6.12.5-brcm-squashfs/fs/squashfs/LzmaDecode.h       1970-01-01 01:00:00.000000000 +0100
 670 +++ linux-2.6.12.5-brcm-squashfs-lzma/fs/squashfs/LzmaDecode.h  2005-08-29 00:02:44.099124176 +0200
 671 @@ -0,0 +1,100 @@
 672 +/*
 673 +  LzmaDecode.h
 674 +  LZMA Decoder interface
 675 +
 676 +  LZMA SDK 4.05 Copyright (c) 1999-2004 Igor Pavlov (2004-08-25)
 677 +  http://www.7-zip.org/
 678 +
 679 +  LZMA SDK is licensed under two licenses:
 680 +  1) GNU Lesser General Public License (GNU LGPL)
 681 +  2) Common Public License (CPL)
 682 +  It means that you can select one of these two licenses and
 683 +  follow rules of that license.
 684 +
 685 +  SPECIAL EXCEPTION:
 686 +  Igor Pavlov, as the author of this code, expressly permits you to
 687 +  statically or dynamically link your code (or bind by name) to the
 688 +  interfaces of this file without subjecting your linked code to the
 689 +  terms of the CPL or GNU LGPL. Any modifications or additions
 690 +  to this file, however, are subject to the LGPL or CPL terms.
 691 +*/
 692 +
 693 +#ifndef __LZMADECODE_H
 694 +#define __LZMADECODE_H
 695 +
 696 +/* #define _LZMA_IN_CB */
 697 +/* Use callback for input data */
 698 +
 699 +/* #define _LZMA_OUT_READ */
 700 +/* Use read function for output data */
 701 +
 702 +/* #define _LZMA_PROB32 */
 703 +/* It can increase speed on some 32-bit CPUs,
 704 +   but memory usage will be doubled in that case */
 705 +
 706 +/* #define _LZMA_LOC_OPT */
 707 +/* Enable local speed optimizations inside code */
 708 +
 709 +#ifndef UInt32
 710 +#ifdef _LZMA_UINT32_IS_ULONG
 711 +#define UInt32 unsigned long
 712 +#else
 713 +#define UInt32 unsigned int
 714 +#endif
 715 +#endif
 716 +
 717 +#ifdef _LZMA_PROB32
 718 +#define CProb UInt32
 719 +#else
 720 +#define CProb unsigned short
 721 +#endif
 722 +
 723 +#define LZMA_RESULT_OK 0
 724 +#define LZMA_RESULT_DATA_ERROR 1
 725 +#define LZMA_RESULT_NOT_ENOUGH_MEM 2
 726 +
 727 +#ifdef _LZMA_IN_CB
 728 +typedef struct _ILzmaInCallback
 729 +{
 730 +  int (*Read)(void *object, unsigned char **buffer, UInt32 *bufferSize);
 731 +} ILzmaInCallback;
 732 +#endif
 733 +
 734 +#define LZMA_BASE_SIZE 1846
 735 +#define LZMA_LIT_SIZE 768
 736 +
 737 +/*
 738 +bufferSize = (LZMA_BASE_SIZE + (LZMA_LIT_SIZE << (lc + lp)))* sizeof(CProb)
 739 +bufferSize += 100 in case of _LZMA_OUT_READ
 740 +by default CProb is unsigned short,
 741 +but if specify _LZMA_PROB_32, CProb will be UInt32(unsigned int)
 742 +*/
 743 +
 744 +#ifdef _LZMA_OUT_READ
 745 +int LzmaDecoderInit(
 746 +    unsigned char *buffer, UInt32 bufferSize,
 747 +    int lc, int lp, int pb,
 748 +    unsigned char *dictionary, UInt32 dictionarySize,
 749 +  #ifdef _LZMA_IN_CB
 750 +    ILzmaInCallback *inCallback
 751 +  #else
 752 +    unsigned char *inStream, UInt32 inSize
 753 +  #endif
 754 +);
 755 +#endif
 756 +
 757 +int LzmaDecode(
 758 +    unsigned char *buffer,
 759 +  #ifndef _LZMA_OUT_READ
 760 +    UInt32 bufferSize,
 761 +    int lc, int lp, int pb,
 762 +  #ifdef _LZMA_IN_CB
 763 +    ILzmaInCallback *inCallback,
 764 +  #else
 765 +    unsigned char *inStream, UInt32 inSize,
 766 +  #endif
 767 +  #endif
 768 +    unsigned char *outStream, UInt32 outSize,
 769 +    UInt32 *outSizeProcessed);
 770 +
 771 +#endif
 772 diff -Nur linux-2.6.12.5-brcm-squashfs/fs/squashfs/Makefile linux-2.6.12.5-brcm-squashfs-lzma/fs/squashfs/Makefile
 773 --- linux-2.6.12.5-brcm-squashfs/fs/squashfs/Makefile   2005-08-28 23:44:05.046246000 +0200
 774 +++ linux-2.6.12.5-brcm-squashfs-lzma/fs/squashfs/Makefile      2005-08-29 00:06:21.872017664 +0200
 775 @@ -4,4 +4,4 @@
 776
 777  obj-$(CONFIG_SQUASHFS) += squashfs.o
 778
 779 -squashfs-objs := inode.o
 780 +squashfs-objs := inode.o LzmaDecode.o
 781 diff -Nur linux-2.6.12.5-brcm-squashfs/fs/squashfs/inode.c linux-2.6.12.5-brcm-squashfs-lzma/fs/squashfs/inode.c
 782 --- linux-2.6.12.5-brcm-squashfs/fs/squashfs/inode.c    2005-08-28 23:44:05.045246000 +0200
 783 +++ linux-2.6.12.5-brcm-squashfs-lzma/fs/squashfs/inode.c       2005-08-29 00:19:48.473476904 +0200
 784 @@ -3,6 +3,9 @@
 785   *
 786   * Copyright (c) 2002, 2003, 2004, 2005 Phillip Lougher <phillip@lougher.demon.co.uk>
 787   *
 788 + * LZMA decompressor support added by Oleg I. Vdovikin
 789 + * Copyright (c) 2005 Oleg I.Vdovikin <oleg@cs.msu.su>
 790 + *
 791   * This program is free software; you can redistribute it and/or
 792   * modify it under the terms of the GNU General Public License
 793   * as published by the Free Software Foundation; either version 2,
 794 @@ -20,7 +23,11 @@
 795   * inode.c
 796   */
 797
 798 +#define SQUASHFS_LZMA
 799 +
 800 +#ifndef SQUASHFS_LZMA
 801  #define SQUASHFS_1_0_COMPATIBILITY
 802 +#endif
 803
 804  #include <linux/types.h>
 805  #include <linux/squashfs_fs.h>
 806 @@ -43,6 +50,19 @@
 807  #include <linux/blkdev.h>
 808  #include <linux/vmalloc.h>
 809
 810 +#ifdef SQUASHFS_LZMA
 811 +#include "LzmaDecode.h"
 812 +
 813 +/* default LZMA settings, should be in sync with mksquashfs */
 814 +#define LZMA_LC 3
 815 +#define LZMA_LP 0
 816 +#define LZMA_PB 2
 817 +
 818 +#define LZMA_WORKSPACE_SIZE ((LZMA_BASE_SIZE + \
 819 +       (LZMA_LIT_SIZE << (LZMA_LC + LZMA_LP))) * sizeof(CProb))
 820 +
 821 +#endif
 822 +
 823  #ifdef SQUASHFS_TRACE
 824  #define TRACE(s, args...)                              printk(KERN_NOTICE "SQUASHFS: "s, ## args)
 825  #else
 826 @@ -85,7 +105,11 @@
 827
 828  DECLARE_MUTEX(read_data_mutex);
 829
 830 +#ifdef SQUASHFS_LZMA
 831 +static unsigned char lzma_workspace[LZMA_WORKSPACE_SIZE];
 832 +#else
 833  static z_stream stream;
 834 +#endif
 835
 836  static struct file_system_type squashfs_fs_type = {
 837         .owner = THIS_MODULE,
 838 @@ -274,6 +298,15 @@
 839         if(compressed) {
 840                 int zlib_err;
 841
 842 +#ifdef SQUASHFS_LZMA
 843 +               if ((zlib_err = LzmaDecode(lzma_workspace,
 844 +                       LZMA_WORKSPACE_SIZE, LZMA_LC, LZMA_LP, LZMA_PB,
 845 +                       c_buffer, c_byte, buffer, msBlk->read_size, &bytes)) != LZMA_RESULT_OK)
 846 +               {
 847 +                       ERROR("lzma returned unexpected result 0x%x\n", zlib_err);
 848 +                       bytes = 0;
 849 +               }
 850 +#else
 851                 stream.next_in = c_buffer;
 852                 stream.avail_in = c_byte;
 853                 stream.next_out = buffer;
 854 @@ -285,6 +318,7 @@
 855                         bytes = 0;
 856                 } else
 857                         bytes = stream.total_out;
 858 +#endif
 859                 up(&read_data_mutex);
 860         }
 861
 862 @@ -1725,14 +1759,17 @@
 863
 864         printk(KERN_INFO "Squashfs 2.2 (released 2005/07/03) (C) 2002-2005 Phillip Lougher\n");
 865
 866 +#ifndef SQUASHFS_LZMA
 867         if(!(stream.workspace = (char *) vmalloc(zlib_inflate_workspacesize()))) {
 868                 ERROR("Failed to allocate zlib workspace\n");
 869                 destroy_inodecache();
 870                 return -ENOMEM;
 871         }
 872 -
 873 +#endif
 874         if((err = register_filesystem(&squashfs_fs_type))) {
 875 +#ifndef SQUASHFS_LZMA
 876                 vfree(stream.workspace);
 877 +#endif
 878                 destroy_inodecache();
 879         }
 880
 881 @@ -1742,7 +1779,9 @@
 882
 883  static void __exit exit_squashfs_fs(void)
 884  {
 885 +#ifndef SQUASHFS_LZMA
 886         vfree(stream.workspace);
 887 +#endif
 888         unregister_filesystem(&squashfs_fs_type);
 889         destroy_inodecache();
 890  }