Annotation of elwix/tools/oldlzma/SRC/7zip/Compress/LZMA_C/LzmaDecode.c, revision 1.1
1.1 ! misho 1: /*
! 2: LzmaDecode.c
! 3: LZMA Decoder (optimized for Speed version)
! 4:
! 5: LZMA SDK 4.17 Copyright (c) 1999-2005 Igor Pavlov (2005-04-05)
! 6: http://www.7-zip.org/
! 7:
! 8: LZMA SDK is licensed under two licenses:
! 9: 1) GNU Lesser General Public License (GNU LGPL)
! 10: 2) Common Public License (CPL)
! 11: It means that you can select one of these two licenses and
! 12: follow rules of that license.
! 13:
! 14: SPECIAL EXCEPTION:
! 15: Igor Pavlov, as the author of this Code, expressly permits you to
! 16: statically or dynamically link your Code (or bind by name) to the
! 17: interfaces of this file without subjecting your linked Code to the
! 18: terms of the CPL or GNU LGPL. Any modifications or additions
! 19: to this file, however, are subject to the LGPL or CPL terms.
! 20: */
! 21:
! 22: #include "LzmaDecode.h"
! 23:
! 24: #ifndef Byte
! 25: #define Byte unsigned char
! 26: #endif
! 27:
! 28: #define kNumTopBits 24
! 29: #define kTopValue ((UInt32)1 << kNumTopBits)
! 30:
! 31: #define kNumBitModelTotalBits 11
! 32: #define kBitModelTotal (1 << kNumBitModelTotalBits)
! 33: #define kNumMoveBits 5
! 34:
! 35: #define RC_READ_BYTE (*Buffer++)
! 36:
! 37: #define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \
! 38: { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }}
! 39:
! 40: #ifdef _LZMA_IN_CB
! 41:
! 42: #define RC_TEST { if (Buffer == BufferLim) \
! 43: { UInt32 size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) return result; \
! 44: BufferLim = Buffer + size; if (size == 0) return LZMA_RESULT_DATA_ERROR; }}
! 45:
! 46: #define RC_INIT Buffer = BufferLim = 0; RC_INIT2
! 47:
! 48: #else
! 49:
! 50: #define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
! 51:
! 52: #define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
! 53:
! 54: #endif
! 55:
! 56: #define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
! 57:
! 58: #define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)
! 59: #define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;
! 60: #define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;
! 61:
! 62: #define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \
! 63: { UpdateBit0(p); mi <<= 1; A0; } else \
! 64: { UpdateBit1(p); mi = (mi + mi) + 1; A1; }
! 65:
! 66: #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
! 67:
! 68: #define RangeDecoderBitTreeDecode(probs, numLevels, res) \
! 69: { int i = numLevels; res = 1; \
! 70: do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \
! 71: res -= (1 << numLevels); }
! 72:
! 73:
! 74: #define kNumPosBitsMax 4
! 75: #define kNumPosStatesMax (1 << kNumPosBitsMax)
! 76:
! 77: #define kLenNumLowBits 3
! 78: #define kLenNumLowSymbols (1 << kLenNumLowBits)
! 79: #define kLenNumMidBits 3
! 80: #define kLenNumMidSymbols (1 << kLenNumMidBits)
! 81: #define kLenNumHighBits 8
! 82: #define kLenNumHighSymbols (1 << kLenNumHighBits)
! 83:
! 84: #define LenChoice 0
! 85: #define LenChoice2 (LenChoice + 1)
! 86: #define LenLow (LenChoice2 + 1)
! 87: #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
! 88: #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
! 89: #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
! 90:
! 91:
! 92: #define kNumStates 12
! 93: #define kNumLitStates 7
! 94:
! 95: #define kStartPosModelIndex 4
! 96: #define kEndPosModelIndex 14
! 97: #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
! 98:
! 99: #define kNumPosSlotBits 6
! 100: #define kNumLenToPosStates 4
! 101:
! 102: #define kNumAlignBits 4
! 103: #define kAlignTableSize (1 << kNumAlignBits)
! 104:
! 105: #define kMatchMinLen 2
! 106:
! 107: #define IsMatch 0
! 108: #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
! 109: #define IsRepG0 (IsRep + kNumStates)
! 110: #define IsRepG1 (IsRepG0 + kNumStates)
! 111: #define IsRepG2 (IsRepG1 + kNumStates)
! 112: #define IsRep0Long (IsRepG2 + kNumStates)
! 113: #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
! 114: #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
! 115: #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
! 116: #define LenCoder (Align + kAlignTableSize)
! 117: #define RepLenCoder (LenCoder + kNumLenProbs)
! 118: #define Literal (RepLenCoder + kNumLenProbs)
! 119:
! 120: #if Literal != LZMA_BASE_SIZE
! 121: StopCompilingDueBUG
! 122: #endif
! 123:
! 124: #ifdef _LZMA_OUT_READ
! 125:
! 126: typedef struct _LzmaVarState
! 127: {
! 128: Byte *Buffer;
! 129: Byte *BufferLim;
! 130: UInt32 Range;
! 131: UInt32 Code;
! 132: #ifdef _LZMA_IN_CB
! 133: ILzmaInCallback *InCallback;
! 134: #endif
! 135: Byte *Dictionary;
! 136: UInt32 DictionarySize;
! 137: UInt32 DictionaryPos;
! 138: UInt32 GlobalPos;
! 139: UInt32 Reps[4];
! 140: int lc;
! 141: int lp;
! 142: int pb;
! 143: int State;
! 144: int RemainLen;
! 145: Byte TempDictionary[4];
! 146: } LzmaVarState;
! 147:
! 148: int LzmaDecoderInit(
! 149: unsigned char *buffer, UInt32 bufferSize,
! 150: int lc, int lp, int pb,
! 151: unsigned char *dictionary, UInt32 dictionarySize,
! 152: #ifdef _LZMA_IN_CB
! 153: ILzmaInCallback *InCallback
! 154: #else
! 155: unsigned char *inStream, UInt32 inSize
! 156: #endif
! 157: )
! 158: {
! 159: Byte *Buffer;
! 160: Byte *BufferLim;
! 161: UInt32 Range;
! 162: UInt32 Code;
! 163: LzmaVarState *vs = (LzmaVarState *)buffer;
! 164: CProb *p = (CProb *)(buffer + sizeof(LzmaVarState));
! 165: UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + lp));
! 166: UInt32 i;
! 167: if (bufferSize < numProbs * sizeof(CProb) + sizeof(LzmaVarState))
! 168: return LZMA_RESULT_NOT_ENOUGH_MEM;
! 169: vs->Dictionary = dictionary;
! 170: vs->DictionarySize = dictionarySize;
! 171: vs->DictionaryPos = 0;
! 172: vs->GlobalPos = 0;
! 173: vs->Reps[0] = vs->Reps[1] = vs->Reps[2] = vs->Reps[3] = 1;
! 174: vs->lc = lc;
! 175: vs->lp = lp;
! 176: vs->pb = pb;
! 177: vs->State = 0;
! 178: vs->RemainLen = 0;
! 179: dictionary[dictionarySize - 1] = 0;
! 180: for (i = 0; i < numProbs; i++)
! 181: p[i] = kBitModelTotal >> 1;
! 182:
! 183: #ifdef _LZMA_IN_CB
! 184: RC_INIT;
! 185: #else
! 186: RC_INIT(inStream, inSize);
! 187: #endif
! 188: vs->Buffer = Buffer;
! 189: vs->BufferLim = BufferLim;
! 190: vs->Range = Range;
! 191: vs->Code = Code;
! 192: #ifdef _LZMA_IN_CB
! 193: vs->InCallback = InCallback;
! 194: #endif
! 195:
! 196: return LZMA_RESULT_OK;
! 197: }
! 198:
! 199: int LzmaDecode(unsigned char *buffer,
! 200: unsigned char *outStream, UInt32 outSize,
! 201: UInt32 *outSizeProcessed)
! 202: {
! 203: LzmaVarState *vs = (LzmaVarState *)buffer;
! 204: Byte *Buffer = vs->Buffer;
! 205: Byte *BufferLim = vs->BufferLim;
! 206: UInt32 Range = vs->Range;
! 207: UInt32 Code = vs->Code;
! 208: #ifdef _LZMA_IN_CB
! 209: ILzmaInCallback *InCallback = vs->InCallback;
! 210: #endif
! 211: CProb *p = (CProb *)(buffer + sizeof(LzmaVarState));
! 212: int state = vs->State;
! 213: Byte previousByte;
! 214: UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
! 215: UInt32 nowPos = 0;
! 216: UInt32 posStateMask = (1 << (vs->pb)) - 1;
! 217: UInt32 literalPosMask = (1 << (vs->lp)) - 1;
! 218: int lc = vs->lc;
! 219: int len = vs->RemainLen;
! 220: UInt32 globalPos = vs->GlobalPos;
! 221:
! 222: Byte *dictionary = vs->Dictionary;
! 223: UInt32 dictionarySize = vs->DictionarySize;
! 224: UInt32 dictionaryPos = vs->DictionaryPos;
! 225:
! 226: Byte tempDictionary[4];
! 227: if (dictionarySize == 0)
! 228: {
! 229: dictionary = tempDictionary;
! 230: dictionarySize = 1;
! 231: tempDictionary[0] = vs->TempDictionary[0];
! 232: }
! 233:
! 234: if (len == -1)
! 235: {
! 236: *outSizeProcessed = 0;
! 237: return LZMA_RESULT_OK;
! 238: }
! 239:
! 240: while(len != 0 && nowPos < outSize)
! 241: {
! 242: UInt32 pos = dictionaryPos - rep0;
! 243: if (pos >= dictionarySize)
! 244: pos += dictionarySize;
! 245: outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
! 246: if (++dictionaryPos == dictionarySize)
! 247: dictionaryPos = 0;
! 248: len--;
! 249: }
! 250: if (dictionaryPos == 0)
! 251: previousByte = dictionary[dictionarySize - 1];
! 252: else
! 253: previousByte = dictionary[dictionaryPos - 1];
! 254: #else
! 255:
! 256: int LzmaDecode(
! 257: Byte *buffer, UInt32 bufferSize,
! 258: int lc, int lp, int pb,
! 259: #ifdef _LZMA_IN_CB
! 260: ILzmaInCallback *InCallback,
! 261: #else
! 262: unsigned char *inStream, UInt32 inSize,
! 263: #endif
! 264: unsigned char *outStream, UInt32 outSize,
! 265: UInt32 *outSizeProcessed)
! 266: {
! 267: UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + lp));
! 268: CProb *p = (CProb *)buffer;
! 269:
! 270: UInt32 i;
! 271: int state = 0;
! 272: Byte previousByte = 0;
! 273: UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
! 274: UInt32 nowPos = 0;
! 275: UInt32 posStateMask = (1 << pb) - 1;
! 276: UInt32 literalPosMask = (1 << lp) - 1;
! 277: int len = 0;
! 278:
! 279: Byte *Buffer;
! 280: Byte *BufferLim;
! 281: UInt32 Range;
! 282: UInt32 Code;
! 283:
! 284: if (bufferSize < numProbs * sizeof(CProb))
! 285: return LZMA_RESULT_NOT_ENOUGH_MEM;
! 286: for (i = 0; i < numProbs; i++)
! 287: p[i] = kBitModelTotal >> 1;
! 288:
! 289:
! 290: #ifdef _LZMA_IN_CB
! 291: RC_INIT;
! 292: #else
! 293: RC_INIT(inStream, inSize);
! 294: #endif
! 295: #endif
! 296:
! 297: *outSizeProcessed = 0;
! 298: while(nowPos < outSize)
! 299: {
! 300: CProb *prob;
! 301: UInt32 bound;
! 302: int posState = (int)(
! 303: (nowPos
! 304: #ifdef _LZMA_OUT_READ
! 305: + globalPos
! 306: #endif
! 307: )
! 308: & posStateMask);
! 309:
! 310: prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
! 311: IfBit0(prob)
! 312: {
! 313: int symbol = 1;
! 314: UpdateBit0(prob)
! 315: prob = p + Literal + (LZMA_LIT_SIZE *
! 316: (((
! 317: (nowPos
! 318: #ifdef _LZMA_OUT_READ
! 319: + globalPos
! 320: #endif
! 321: )
! 322: & literalPosMask) << lc) + (previousByte >> (8 - lc))));
! 323:
! 324: if (state >= kNumLitStates)
! 325: {
! 326: int matchByte;
! 327: #ifdef _LZMA_OUT_READ
! 328: UInt32 pos = dictionaryPos - rep0;
! 329: if (pos >= dictionarySize)
! 330: pos += dictionarySize;
! 331: matchByte = dictionary[pos];
! 332: #else
! 333: matchByte = outStream[nowPos - rep0];
! 334: #endif
! 335: do
! 336: {
! 337: int bit;
! 338: CProb *probLit;
! 339: matchByte <<= 1;
! 340: bit = (matchByte & 0x100);
! 341: probLit = prob + 0x100 + bit + symbol;
! 342: RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
! 343: }
! 344: while (symbol < 0x100);
! 345: }
! 346: while (symbol < 0x100)
! 347: {
! 348: CProb *probLit = prob + symbol;
! 349: RC_GET_BIT(probLit, symbol)
! 350: }
! 351: previousByte = (Byte)symbol;
! 352:
! 353: outStream[nowPos++] = previousByte;
! 354: #ifdef _LZMA_OUT_READ
! 355: dictionary[dictionaryPos] = previousByte;
! 356: if (++dictionaryPos == dictionarySize)
! 357: dictionaryPos = 0;
! 358: #endif
! 359: if (state < 4) state = 0;
! 360: else if (state < 10) state -= 3;
! 361: else state -= 6;
! 362: }
! 363: else
! 364: {
! 365: UpdateBit1(prob);
! 366: prob = p + IsRep + state;
! 367: IfBit0(prob)
! 368: {
! 369: UpdateBit0(prob);
! 370: rep3 = rep2;
! 371: rep2 = rep1;
! 372: rep1 = rep0;
! 373: state = state < kNumLitStates ? 0 : 3;
! 374: prob = p + LenCoder;
! 375: }
! 376: else
! 377: {
! 378: UpdateBit1(prob);
! 379: prob = p + IsRepG0 + state;
! 380: IfBit0(prob)
! 381: {
! 382: UpdateBit0(prob);
! 383: prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
! 384: IfBit0(prob)
! 385: {
! 386: #ifdef _LZMA_OUT_READ
! 387: UInt32 pos;
! 388: #endif
! 389: UpdateBit0(prob);
! 390: if (nowPos
! 391: #ifdef _LZMA_OUT_READ
! 392: + globalPos
! 393: #endif
! 394: == 0)
! 395: return LZMA_RESULT_DATA_ERROR;
! 396: state = state < kNumLitStates ? 9 : 11;
! 397: #ifdef _LZMA_OUT_READ
! 398: pos = dictionaryPos - rep0;
! 399: if (pos >= dictionarySize)
! 400: pos += dictionarySize;
! 401: previousByte = dictionary[pos];
! 402: dictionary[dictionaryPos] = previousByte;
! 403: if (++dictionaryPos == dictionarySize)
! 404: dictionaryPos = 0;
! 405: #else
! 406: previousByte = outStream[nowPos - rep0];
! 407: #endif
! 408: outStream[nowPos++] = previousByte;
! 409: continue;
! 410: }
! 411: else
! 412: {
! 413: UpdateBit1(prob);
! 414: }
! 415: }
! 416: else
! 417: {
! 418: UInt32 distance;
! 419: UpdateBit1(prob);
! 420: prob = p + IsRepG1 + state;
! 421: IfBit0(prob)
! 422: {
! 423: UpdateBit0(prob);
! 424: distance = rep1;
! 425: }
! 426: else
! 427: {
! 428: UpdateBit1(prob);
! 429: prob = p + IsRepG2 + state;
! 430: IfBit0(prob)
! 431: {
! 432: UpdateBit0(prob);
! 433: distance = rep2;
! 434: }
! 435: else
! 436: {
! 437: UpdateBit1(prob);
! 438: distance = rep3;
! 439: rep3 = rep2;
! 440: }
! 441: rep2 = rep1;
! 442: }
! 443: rep1 = rep0;
! 444: rep0 = distance;
! 445: }
! 446: state = state < kNumLitStates ? 8 : 11;
! 447: prob = p + RepLenCoder;
! 448: }
! 449: {
! 450: int numBits, offset;
! 451: CProb *probLen = prob + LenChoice;
! 452: IfBit0(probLen)
! 453: {
! 454: UpdateBit0(probLen);
! 455: probLen = prob + LenLow + (posState << kLenNumLowBits);
! 456: offset = 0;
! 457: numBits = kLenNumLowBits;
! 458: }
! 459: else
! 460: {
! 461: UpdateBit1(probLen);
! 462: probLen = prob + LenChoice2;
! 463: IfBit0(probLen)
! 464: {
! 465: UpdateBit0(probLen);
! 466: probLen = prob + LenMid + (posState << kLenNumMidBits);
! 467: offset = kLenNumLowSymbols;
! 468: numBits = kLenNumMidBits;
! 469: }
! 470: else
! 471: {
! 472: UpdateBit1(probLen);
! 473: probLen = prob + LenHigh;
! 474: offset = kLenNumLowSymbols + kLenNumMidSymbols;
! 475: numBits = kLenNumHighBits;
! 476: }
! 477: }
! 478: RangeDecoderBitTreeDecode(probLen, numBits, len);
! 479: len += offset;
! 480: }
! 481:
! 482: if (state < 4)
! 483: {
! 484: int posSlot;
! 485: state += kNumLitStates;
! 486: prob = p + PosSlot +
! 487: ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
! 488: kNumPosSlotBits);
! 489: RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
! 490: if (posSlot >= kStartPosModelIndex)
! 491: {
! 492: int numDirectBits = ((posSlot >> 1) - 1);
! 493: rep0 = (2 | ((UInt32)posSlot & 1));
! 494: if (posSlot < kEndPosModelIndex)
! 495: {
! 496: rep0 <<= numDirectBits;
! 497: prob = p + SpecPos + rep0 - posSlot - 1;
! 498: }
! 499: else
! 500: {
! 501: numDirectBits -= kNumAlignBits;
! 502: do
! 503: {
! 504: RC_NORMALIZE
! 505: Range >>= 1;
! 506: rep0 <<= 1;
! 507: if (Code >= Range)
! 508: {
! 509: Code -= Range;
! 510: rep0 |= 1;
! 511: }
! 512: }
! 513: while (--numDirectBits != 0);
! 514: prob = p + Align;
! 515: rep0 <<= kNumAlignBits;
! 516: numDirectBits = kNumAlignBits;
! 517: }
! 518: {
! 519: int i = 1;
! 520: int mi = 1;
! 521: do
! 522: {
! 523: CProb *prob3 = prob + mi;
! 524: RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
! 525: i <<= 1;
! 526: }
! 527: while(--numDirectBits != 0);
! 528: }
! 529: }
! 530: else
! 531: rep0 = posSlot;
! 532: if (++rep0 == (UInt32)(0))
! 533: {
! 534: /* it's for stream version */
! 535: len = -1;
! 536: break;
! 537: }
! 538: }
! 539:
! 540: len += kMatchMinLen;
! 541: if (rep0 > nowPos
! 542: #ifdef _LZMA_OUT_READ
! 543: + globalPos || rep0 > dictionarySize
! 544: #endif
! 545: )
! 546: return LZMA_RESULT_DATA_ERROR;
! 547: do
! 548: {
! 549: #ifdef _LZMA_OUT_READ
! 550: UInt32 pos = dictionaryPos - rep0;
! 551: if (pos >= dictionarySize)
! 552: pos += dictionarySize;
! 553: previousByte = dictionary[pos];
! 554: dictionary[dictionaryPos] = previousByte;
! 555: if (++dictionaryPos == dictionarySize)
! 556: dictionaryPos = 0;
! 557: #else
! 558: previousByte = outStream[nowPos - rep0];
! 559: #endif
! 560: len--;
! 561: outStream[nowPos++] = previousByte;
! 562: }
! 563: while(len != 0 && nowPos < outSize);
! 564: }
! 565: }
! 566: RC_NORMALIZE;
! 567:
! 568: #ifdef _LZMA_OUT_READ
! 569: vs->Buffer = Buffer;
! 570: vs->BufferLim = BufferLim;
! 571: vs->Range = Range;
! 572: vs->Code = Code;
! 573: vs->DictionaryPos = dictionaryPos;
! 574: vs->GlobalPos = globalPos + nowPos;
! 575: vs->Reps[0] = rep0;
! 576: vs->Reps[1] = rep1;
! 577: vs->Reps[2] = rep2;
! 578: vs->Reps[3] = rep3;
! 579: vs->State = state;
! 580: vs->RemainLen = len;
! 581: vs->TempDictionary[0] = tempDictionary[0];
! 582: #endif
! 583:
! 584: *outSizeProcessed = nowPos;
! 585: return LZMA_RESULT_OK;
! 586: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to LzmaDecode.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / elwix / tools / oldlzma / SRC / 7zip / Compress / LZMA_C