git.maemo.org Git - physicsfs/blob - lzma/C/Compress/Lzma/LzmaDecodeSize.c

   1 /*
   2   LzmaDecodeSize.c
   3   LZMA Decoder (optimized for Size version)
   4
   5   LZMA SDK 4.40 Copyright (c) 1999-2006 Igor Pavlov (2006-05-01)
   6   http://www.7-zip.org/
   7
   8   LZMA SDK is licensed under two licenses:
   9   1) GNU Lesser General Public License (GNU LGPL)
  10   2) Common Public License (CPL)
  11   It means that you can select one of these two licenses and
  12   follow rules of that license.
  13
  14   SPECIAL EXCEPTION:
  15   Igor Pavlov, as the author of this code, expressly permits you to
  16   statically or dynamically link your code (or bind by name) to the
  17   interfaces of this file without subjecting your linked code to the
  18   terms of the CPL or GNU LGPL. Any modifications or additions
  19   to this file, however, are subject to the LGPL or CPL terms.
  20 */
  21
  22 #include "LzmaDecode.h"
  23
  24 #define kNumTopBits 24
  25 #define kTopValue ((UInt32)1 << kNumTopBits)
  26
  27 #define kNumBitModelTotalBits 11
  28 #define kBitModelTotal (1 << kNumBitModelTotalBits)
  29 #define kNumMoveBits 5
  30
  31 typedef struct _CRangeDecoder
  32 {
  33   const Byte *Buffer;
  34   const Byte *BufferLim;
  35   UInt32 Range;
  36   UInt32 Code;
  37   #ifdef _LZMA_IN_CB
  38   ILzmaInCallback *InCallback;
  39   int Result;
  40   #endif
  41   int ExtraBytes;
  42 } CRangeDecoder;
  43
  44 Byte RangeDecoderReadByte(CRangeDecoder *rd)
  45 {
  46   if (rd->Buffer == rd->BufferLim)
  47   {
  48     #ifdef _LZMA_IN_CB
  49     SizeT size;
  50     rd->Result = rd->InCallback->Read(rd->InCallback, &rd->Buffer, &size);
  51     rd->BufferLim = rd->Buffer + size;
  52     if (size == 0)
  53     #endif
  54     {
  55       rd->ExtraBytes = 1;
  56       return 0xFF;
  57     }
  58   }
  59   return (*rd->Buffer++);
  60 }
  61
  62 /* #define ReadByte (*rd->Buffer++) */
  63 #define ReadByte (RangeDecoderReadByte(rd))
  64
  65 void RangeDecoderInit(CRangeDecoder *rd
  66   #ifndef _LZMA_IN_CB
  67     , const Byte *stream, SizeT bufferSize
  68   #endif
  69     )
  70 {
  71   int i;
  72   #ifdef _LZMA_IN_CB
  73   rd->Buffer = rd->BufferLim = 0;
  74   #else
  75   rd->Buffer = stream;
  76   rd->BufferLim = stream + bufferSize;
  77   #endif
  78   rd->ExtraBytes = 0;
  79   rd->Code = 0;
  80   rd->Range = (0xFFFFFFFF);
  81   for(i = 0; i < 5; i++)
  82     rd->Code = (rd->Code << 8) | ReadByte;
  83 }
  84
  85 #define RC_INIT_VAR UInt32 range = rd->Range; UInt32 code = rd->Code;
  86 #define RC_FLUSH_VAR rd->Range = range; rd->Code = code;
  87 #define RC_NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | ReadByte; }
  88
  89 UInt32 RangeDecoderDecodeDirectBits(CRangeDecoder *rd, int numTotalBits)
  90 {
  91   RC_INIT_VAR
  92   UInt32 result = 0;
  93   int i;
  94   for (i = numTotalBits; i != 0; i--)
  95   {
  96     /* UInt32 t; */
  97     range >>= 1;
  98
  99     result <<= 1;
 100     if (code >= range)
 101     {
 102       code -= range;
 103       result |= 1;
 104     }
 105     /*
 106     t = (code - range) >> 31;
 107     t &= 1;
 108     code -= range & (t - 1);
 109     result = (result + result) | (1 - t);
 110     */
 111     RC_NORMALIZE
 112   }
 113   RC_FLUSH_VAR
 114   return result;
 115 }
 116
 117 int RangeDecoderBitDecode(CProb *prob, CRangeDecoder *rd)
 118 {
 119   UInt32 bound = (rd->Range >> kNumBitModelTotalBits) * *prob;
 120   if (rd->Code < bound)
 121   {
 122     rd->Range = bound;
 123     *prob += (kBitModelTotal - *prob) >> kNumMoveBits;
 124     if (rd->Range < kTopValue)
 125     {
 126       rd->Code = (rd->Code << 8) | ReadByte;
 127       rd->Range <<= 8;
 128     }
 129     return 0;
 130   }
 131   else
 132   {
 133     rd->Range -= bound;
 134     rd->Code -= bound;
 135     *prob -= (*prob) >> kNumMoveBits;
 136     if (rd->Range < kTopValue)
 137     {
 138       rd->Code = (rd->Code << 8) | ReadByte;
 139       rd->Range <<= 8;
 140     }
 141     return 1;
 142   }
 143 }
 144
 145 #define RC_GET_BIT2(prob, mi, A0, A1) \
 146   UInt32 bound = (range >> kNumBitModelTotalBits) * *prob; \
 147   if (code < bound) \
 148     { A0; range = bound; *prob += (kBitModelTotal - *prob) >> kNumMoveBits; mi <<= 1; } \
 149   else \
 150     { A1; range -= bound; code -= bound; *prob -= (*prob) >> kNumMoveBits; mi = (mi + mi) + 1; } \
 151   RC_NORMALIZE
 152
 153 #define RC_GET_BIT(prob, mi) RC_GET_BIT2(prob, mi, ; , ;)
 154
 155 int RangeDecoderBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd)
 156 {
 157   int mi = 1;
 158   int i;
 159   #ifdef _LZMA_LOC_OPT
 160   RC_INIT_VAR
 161   #endif
 162   for(i = numLevels; i != 0; i--)
 163   {
 164     #ifdef _LZMA_LOC_OPT
 165     CProb *prob = probs + mi;
 166     RC_GET_BIT(prob, mi)
 167     #else
 168     mi = (mi + mi) + RangeDecoderBitDecode(probs + mi, rd);
 169     #endif
 170   }
 171   #ifdef _LZMA_LOC_OPT
 172   RC_FLUSH_VAR
 173   #endif
 174   return mi - (1 << numLevels);
 175 }
 176
 177 int RangeDecoderReverseBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd)
 178 {
 179   int mi = 1;
 180   int i;
 181   int symbol = 0;
 182   #ifdef _LZMA_LOC_OPT
 183   RC_INIT_VAR
 184   #endif
 185   for(i = 0; i < numLevels; i++)
 186   {
 187     #ifdef _LZMA_LOC_OPT
 188     CProb *prob = probs + mi;
 189     RC_GET_BIT2(prob, mi, ; , symbol |= (1 << i))
 190     #else
 191     int bit = RangeDecoderBitDecode(probs + mi, rd);
 192     mi = mi + mi + bit;
 193     symbol |= (bit << i);
 194     #endif
 195   }
 196   #ifdef _LZMA_LOC_OPT
 197   RC_FLUSH_VAR
 198   #endif
 199   return symbol;
 200 }
 201
 202 Byte LzmaLiteralDecode(CProb *probs, CRangeDecoder *rd)
 203 {
 204   int symbol = 1;
 205   #ifdef _LZMA_LOC_OPT
 206   RC_INIT_VAR
 207   #endif
 208   do
 209   {
 210     #ifdef _LZMA_LOC_OPT
 211     CProb *prob = probs + symbol;
 212     RC_GET_BIT(prob, symbol)
 213     #else
 214     symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd);
 215     #endif
 216   }
 217   while (symbol < 0x100);
 218   #ifdef _LZMA_LOC_OPT
 219   RC_FLUSH_VAR
 220   #endif
 221   return symbol;
 222 }
 223
 224 Byte LzmaLiteralDecodeMatch(CProb *probs, CRangeDecoder *rd, Byte matchByte)
 225 {
 226   int symbol = 1;
 227   #ifdef _LZMA_LOC_OPT
 228   RC_INIT_VAR
 229   #endif
 230   do
 231   {
 232     int bit;
 233     int matchBit = (matchByte >> 7) & 1;
 234     matchByte <<= 1;
 235     #ifdef _LZMA_LOC_OPT
 236     {
 237       CProb *prob = probs + 0x100 + (matchBit << 8) + symbol;
 238       RC_GET_BIT2(prob, symbol, bit = 0, bit = 1)
 239     }
 240     #else
 241     bit = RangeDecoderBitDecode(probs + 0x100 + (matchBit << 8) + symbol, rd);
 242     symbol = (symbol << 1) | bit;
 243     #endif
 244     if (matchBit != bit)
 245     {
 246       while (symbol < 0x100)
 247       {
 248         #ifdef _LZMA_LOC_OPT
 249         CProb *prob = probs + symbol;
 250         RC_GET_BIT(prob, symbol)
 251         #else
 252         symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd);
 253         #endif
 254       }
 255       break;
 256     }
 257   }
 258   while (symbol < 0x100);
 259   #ifdef _LZMA_LOC_OPT
 260   RC_FLUSH_VAR
 261   #endif
 262   return symbol;
 263 }
 264
 265 #define kNumPosBitsMax 4
 266 #define kNumPosStatesMax (1 << kNumPosBitsMax)
 267
 268 #define kLenNumLowBits 3
 269 #define kLenNumLowSymbols (1 << kLenNumLowBits)
 270 #define kLenNumMidBits 3
 271 #define kLenNumMidSymbols (1 << kLenNumMidBits)
 272 #define kLenNumHighBits 8
 273 #define kLenNumHighSymbols (1 << kLenNumHighBits)
 274
 275 #define LenChoice 0
 276 #define LenChoice2 (LenChoice + 1)
 277 #define LenLow (LenChoice2 + 1)
 278 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
 279 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
 280 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
 281
 282 int LzmaLenDecode(CProb *p, CRangeDecoder *rd, int posState)
 283 {
 284   if(RangeDecoderBitDecode(p + LenChoice, rd) == 0)
 285     return RangeDecoderBitTreeDecode(p + LenLow +
 286         (posState << kLenNumLowBits), kLenNumLowBits, rd);
 287   if(RangeDecoderBitDecode(p + LenChoice2, rd) == 0)
 288     return kLenNumLowSymbols + RangeDecoderBitTreeDecode(p + LenMid +
 289         (posState << kLenNumMidBits), kLenNumMidBits, rd);
 290   return kLenNumLowSymbols + kLenNumMidSymbols +
 291       RangeDecoderBitTreeDecode(p + LenHigh, kLenNumHighBits, rd);
 292 }
 293
 294 #define kNumStates 12
 295 #define kNumLitStates 7
 296
 297 #define kStartPosModelIndex 4
 298 #define kEndPosModelIndex 14
 299 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
 300
 301 #define kNumPosSlotBits 6
 302 #define kNumLenToPosStates 4
 303
 304 #define kNumAlignBits 4
 305 #define kAlignTableSize (1 << kNumAlignBits)
 306
 307 #define kMatchMinLen 2
 308
 309 #define IsMatch 0
 310 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
 311 #define IsRepG0 (IsRep + kNumStates)
 312 #define IsRepG1 (IsRepG0 + kNumStates)
 313 #define IsRepG2 (IsRepG1 + kNumStates)
 314 #define IsRep0Long (IsRepG2 + kNumStates)
 315 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
 316 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
 317 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
 318 #define LenCoder (Align + kAlignTableSize)
 319 #define RepLenCoder (LenCoder + kNumLenProbs)
 320 #define Literal (RepLenCoder + kNumLenProbs)
 321
 322 #if Literal != LZMA_BASE_SIZE
 323 StopCompilingDueBUG
 324 #endif
 325
 326 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
 327 {
 328   unsigned char prop0;
 329   if (size < LZMA_PROPERTIES_SIZE)
 330     return LZMA_RESULT_DATA_ERROR;
 331   prop0 = propsData[0];
 332   if (prop0 >= (9 * 5 * 5))
 333     return LZMA_RESULT_DATA_ERROR;
 334   {
 335     for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
 336     for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
 337     propsRes->lc = prop0;
 338     /*
 339     unsigned char remainder = (unsigned char)(prop0 / 9);
 340     propsRes->lc = prop0 % 9;
 341     propsRes->pb = remainder / 5;
 342     propsRes->lp = remainder % 5;
 343     */
 344   }
 345
 346   #ifdef _LZMA_OUT_READ
 347   {
 348     int i;
 349     propsRes->DictionarySize = 0;
 350     for (i = 0; i < 4; i++)
 351       propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);
 352     if (propsRes->DictionarySize == 0)
 353       propsRes->DictionarySize = 1;
 354   }
 355   #endif
 356   return LZMA_RESULT_OK;
 357 }
 358
 359 #define kLzmaStreamWasFinishedId (-1)
 360
 361 int LzmaDecode(CLzmaDecoderState *vs,
 362     #ifdef _LZMA_IN_CB
 363     ILzmaInCallback *InCallback,
 364     #else
 365     const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
 366     #endif
 367     unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
 368 {
 369   CProb *p = vs->Probs;
 370   SizeT nowPos = 0;
 371   Byte previousByte = 0;
 372   UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
 373   UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
 374   int lc = vs->Properties.lc;
 375   CRangeDecoder rd;
 376
 377   #ifdef _LZMA_OUT_READ
 378
 379   int state = vs->State;
 380   UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
 381   int len = vs->RemainLen;
 382   UInt32 globalPos = vs->GlobalPos;
 383   UInt32 distanceLimit = vs->DistanceLimit;
 384
 385   Byte *dictionary = vs->Dictionary;
 386   UInt32 dictionarySize = vs->Properties.DictionarySize;
 387   UInt32 dictionaryPos = vs->DictionaryPos;
 388
 389   Byte tempDictionary[4];
 390
 391   rd.Range = vs->Range;
 392   rd.Code = vs->Code;
 393   #ifdef _LZMA_IN_CB
 394   rd.InCallback = InCallback;
 395   rd.Buffer = vs->Buffer;
 396   rd.BufferLim = vs->BufferLim;
 397   #else
 398   rd.Buffer = inStream;
 399   rd.BufferLim = inStream + inSize;
 400   #endif
 401
 402   #ifndef _LZMA_IN_CB
 403   *inSizeProcessed = 0;
 404   #endif
 405   *outSizeProcessed = 0;
 406   if (len == kLzmaStreamWasFinishedId)
 407     return LZMA_RESULT_OK;
 408
 409   if (dictionarySize == 0)
 410   {
 411     dictionary = tempDictionary;
 412     dictionarySize = 1;
 413     tempDictionary[0] = vs->TempDictionary[0];
 414   }
 415
 416   if (len == kLzmaNeedInitId)
 417   {
 418     {
 419       UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
 420       UInt32 i;
 421       for (i = 0; i < numProbs; i++)
 422         p[i] = kBitModelTotal >> 1;
 423       rep0 = rep1 = rep2 = rep3 = 1;
 424       state = 0;
 425       globalPos = 0;
 426       distanceLimit = 0;
 427       dictionaryPos = 0;
 428       dictionary[dictionarySize - 1] = 0;
 429       RangeDecoderInit(&rd
 430           #ifndef _LZMA_IN_CB
 431           , inStream, inSize
 432           #endif
 433           );
 434       #ifdef _LZMA_IN_CB
 435       if (rd.Result != LZMA_RESULT_OK)
 436         return rd.Result;
 437       #endif
 438       if (rd.ExtraBytes != 0)
 439         return LZMA_RESULT_DATA_ERROR;
 440     }
 441     len = 0;
 442   }
 443   while(len != 0 && nowPos < outSize)
 444   {
 445     UInt32 pos = dictionaryPos - rep0;
 446     if (pos >= dictionarySize)
 447       pos += dictionarySize;
 448     outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
 449     if (++dictionaryPos == dictionarySize)
 450       dictionaryPos = 0;
 451     len--;
 452   }
 453   if (dictionaryPos == 0)
 454     previousByte = dictionary[dictionarySize - 1];
 455   else
 456     previousByte = dictionary[dictionaryPos - 1];
 457
 458   #ifdef _LZMA_IN_CB
 459   rd.Result = LZMA_RESULT_OK;
 460   #endif
 461   rd.ExtraBytes = 0;
 462
 463   #else /* if !_LZMA_OUT_READ */
 464
 465   int state = 0;
 466   UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
 467   int len = 0;
 468
 469   #ifndef _LZMA_IN_CB
 470   *inSizeProcessed = 0;
 471   #endif
 472   *outSizeProcessed = 0;
 473
 474   {
 475     UInt32 i;
 476     UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
 477     for (i = 0; i < numProbs; i++)
 478       p[i] = kBitModelTotal >> 1;
 479   }
 480
 481   #ifdef _LZMA_IN_CB
 482   rd.InCallback = InCallback;
 483   #endif
 484   RangeDecoderInit(&rd
 485       #ifndef _LZMA_IN_CB
 486       , inStream, inSize
 487       #endif
 488       );
 489
 490   #ifdef _LZMA_IN_CB
 491   if (rd.Result != LZMA_RESULT_OK)
 492     return rd.Result;
 493   #endif
 494   if (rd.ExtraBytes != 0)
 495     return LZMA_RESULT_DATA_ERROR;
 496
 497   #endif /* _LZMA_OUT_READ */
 498
 499
 500   while(nowPos < outSize)
 501   {
 502     int posState = (int)(
 503         (nowPos
 504         #ifdef _LZMA_OUT_READ
 505         + globalPos
 506         #endif
 507         )
 508         & posStateMask);
 509     #ifdef _LZMA_IN_CB
 510     if (rd.Result != LZMA_RESULT_OK)
 511       return rd.Result;
 512     #endif
 513     if (rd.ExtraBytes != 0)
 514       return LZMA_RESULT_DATA_ERROR;
 515     if (RangeDecoderBitDecode(p + IsMatch + (state << kNumPosBitsMax) + posState, &rd) == 0)
 516     {
 517       CProb *probs = p + Literal + (LZMA_LIT_SIZE *
 518         (((
 519         (nowPos
 520         #ifdef _LZMA_OUT_READ
 521         + globalPos
 522         #endif
 523         )
 524         & literalPosMask) << lc) + (previousByte >> (8 - lc))));
 525
 526       if (state >= kNumLitStates)
 527       {
 528         Byte matchByte;
 529         #ifdef _LZMA_OUT_READ
 530         UInt32 pos = dictionaryPos - rep0;
 531         if (pos >= dictionarySize)
 532           pos += dictionarySize;
 533         matchByte = dictionary[pos];
 534         #else
 535         matchByte = outStream[nowPos - rep0];
 536         #endif
 537         previousByte = LzmaLiteralDecodeMatch(probs, &rd, matchByte);
 538       }
 539       else
 540         previousByte = LzmaLiteralDecode(probs, &rd);
 541       outStream[nowPos++] = previousByte;
 542       #ifdef _LZMA_OUT_READ
 543       if (distanceLimit < dictionarySize)
 544         distanceLimit++;
 545
 546       dictionary[dictionaryPos] = previousByte;
 547       if (++dictionaryPos == dictionarySize)
 548         dictionaryPos = 0;
 549       #endif
 550       if (state < 4) state = 0;
 551       else if (state < 10) state -= 3;
 552       else state -= 6;
 553     }
 554     else
 555     {
 556       if (RangeDecoderBitDecode(p + IsRep + state, &rd) == 1)
 557       {
 558         if (RangeDecoderBitDecode(p + IsRepG0 + state, &rd) == 0)
 559         {
 560           if (RangeDecoderBitDecode(p + IsRep0Long + (state << kNumPosBitsMax) + posState, &rd) == 0)
 561           {
 562             #ifdef _LZMA_OUT_READ
 563             UInt32 pos;
 564             #endif
 565
 566             #ifdef _LZMA_OUT_READ
 567             if (distanceLimit == 0)
 568             #else
 569             if (nowPos == 0)
 570             #endif
 571               return LZMA_RESULT_DATA_ERROR;
 572
 573             state = state < 7 ? 9 : 11;
 574             #ifdef _LZMA_OUT_READ
 575             pos = dictionaryPos - rep0;
 576             if (pos >= dictionarySize)
 577               pos += dictionarySize;
 578             previousByte = dictionary[pos];
 579             dictionary[dictionaryPos] = previousByte;
 580             if (++dictionaryPos == dictionarySize)
 581               dictionaryPos = 0;
 582             #else
 583             previousByte = outStream[nowPos - rep0];
 584             #endif
 585             outStream[nowPos++] = previousByte;
 586
 587             #ifdef _LZMA_OUT_READ
 588             if (distanceLimit < dictionarySize)
 589               distanceLimit++;
 590             #endif
 591             continue;
 592           }
 593         }
 594         else
 595         {
 596           UInt32 distance;
 597           if(RangeDecoderBitDecode(p + IsRepG1 + state, &rd) == 0)
 598             distance = rep1;
 599           else
 600           {
 601             if(RangeDecoderBitDecode(p + IsRepG2 + state, &rd) == 0)
 602               distance = rep2;
 603             else
 604             {
 605               distance = rep3;
 606               rep3 = rep2;
 607             }
 608             rep2 = rep1;
 609           }
 610           rep1 = rep0;
 611           rep0 = distance;
 612         }
 613         len = LzmaLenDecode(p + RepLenCoder, &rd, posState);
 614         state = state < 7 ? 8 : 11;
 615       }
 616       else
 617       {
 618         int posSlot;
 619         rep3 = rep2;
 620         rep2 = rep1;
 621         rep1 = rep0;
 622         state = state < 7 ? 7 : 10;
 623         len = LzmaLenDecode(p + LenCoder, &rd, posState);
 624         posSlot = RangeDecoderBitTreeDecode(p + PosSlot +
 625             ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
 626             kNumPosSlotBits), kNumPosSlotBits, &rd);
 627         if (posSlot >= kStartPosModelIndex)
 628         {
 629           int numDirectBits = ((posSlot >> 1) - 1);
 630           rep0 = ((2 | ((UInt32)posSlot & 1)) << numDirectBits);
 631           if (posSlot < kEndPosModelIndex)
 632           {
 633             rep0 += RangeDecoderReverseBitTreeDecode(
 634                 p + SpecPos + rep0 - posSlot - 1, numDirectBits, &rd);
 635           }
 636           else
 637           {
 638             rep0 += RangeDecoderDecodeDirectBits(&rd,
 639                 numDirectBits - kNumAlignBits) << kNumAlignBits;
 640             rep0 += RangeDecoderReverseBitTreeDecode(p + Align, kNumAlignBits, &rd);
 641           }
 642         }
 643         else
 644           rep0 = posSlot;
 645         if (++rep0 == (UInt32)(0))
 646         {
 647           /* it's for stream version */
 648           len = kLzmaStreamWasFinishedId;
 649           break;
 650         }
 651       }
 652
 653       len += kMatchMinLen;
 654       #ifdef _LZMA_OUT_READ
 655       if (rep0 > distanceLimit)
 656       #else
 657       if (rep0 > nowPos)
 658       #endif
 659         return LZMA_RESULT_DATA_ERROR;
 660
 661       #ifdef _LZMA_OUT_READ
 662       if (dictionarySize - distanceLimit > (UInt32)len)
 663         distanceLimit += len;
 664       else
 665         distanceLimit = dictionarySize;
 666       #endif
 667
 668       do
 669       {
 670         #ifdef _LZMA_OUT_READ
 671         UInt32 pos = dictionaryPos - rep0;
 672         if (pos >= dictionarySize)
 673           pos += dictionarySize;
 674         previousByte = dictionary[pos];
 675         dictionary[dictionaryPos] = previousByte;
 676         if (++dictionaryPos == dictionarySize)
 677           dictionaryPos = 0;
 678         #else
 679         previousByte = outStream[nowPos - rep0];
 680         #endif
 681         len--;
 682         outStream[nowPos++] = previousByte;
 683       }
 684       while(len != 0 && nowPos < outSize);
 685     }
 686   }
 687
 688
 689   #ifdef _LZMA_OUT_READ
 690   vs->Range = rd.Range;
 691   vs->Code = rd.Code;
 692   vs->DictionaryPos = dictionaryPos;
 693   vs->GlobalPos = globalPos + (UInt32)nowPos;
 694   vs->DistanceLimit = distanceLimit;
 695   vs->Reps[0] = rep0;
 696   vs->Reps[1] = rep1;
 697   vs->Reps[2] = rep2;
 698   vs->Reps[3] = rep3;
 699   vs->State = state;
 700   vs->RemainLen = len;
 701   vs->TempDictionary[0] = tempDictionary[0];
 702   #endif
 703
 704   #ifdef _LZMA_IN_CB
 705   vs->Buffer = rd.Buffer;
 706   vs->BufferLim = rd.BufferLim;
 707   #else
 708   *inSizeProcessed = (SizeT)(rd.Buffer - inStream);
 709   #endif
 710   *outSizeProcessed = nowPos;
 711   return LZMA_RESULT_OK;
 712 }