Annotation of elwix/tools/oldlzma/SRC/7zip/Compress/LZMA_C/LzmaDecodeSize.c, revision 1.1.1.1
1.1 misho 1: /*
2: LzmaDecodeSize.c
3: LZMA Decoder (optimized for Size version)
4:
5: LZMA SDK 4.16 Copyright (c) 1999-2005 Igor Pavlov (2005-03-18)
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: typedef struct _CRangeDecoder
36: {
37: Byte *Buffer;
38: Byte *BufferLim;
39: UInt32 Range;
40: UInt32 Code;
41: #ifdef _LZMA_IN_CB
42: ILzmaInCallback *InCallback;
43: int Result;
44: #endif
45: int ExtraBytes;
46: } CRangeDecoder;
47:
48: Byte RangeDecoderReadByte(CRangeDecoder *rd)
49: {
50: if (rd->Buffer == rd->BufferLim)
51: {
52: #ifdef _LZMA_IN_CB
53: UInt32 size;
54: rd->Result = rd->InCallback->Read(rd->InCallback, &rd->Buffer, &size);
55: rd->BufferLim = rd->Buffer + size;
56: if (size == 0)
57: #endif
58: {
59: rd->ExtraBytes = 1;
60: return 0xFF;
61: }
62: }
63: return (*rd->Buffer++);
64: }
65:
66: /* #define ReadByte (*rd->Buffer++) */
67: #define ReadByte (RangeDecoderReadByte(rd))
68:
69: void RangeDecoderInit(CRangeDecoder *rd,
70: #ifdef _LZMA_IN_CB
71: ILzmaInCallback *inCallback
72: #else
73: Byte *stream, UInt32 bufferSize
74: #endif
75: )
76: {
77: int i;
78: #ifdef _LZMA_IN_CB
79: rd->InCallback = inCallback;
80: rd->Buffer = rd->BufferLim = 0;
81: #else
82: rd->Buffer = stream;
83: rd->BufferLim = stream + bufferSize;
84: #endif
85: rd->ExtraBytes = 0;
86: rd->Code = 0;
87: rd->Range = (0xFFFFFFFF);
88: for(i = 0; i < 5; i++)
89: rd->Code = (rd->Code << 8) | ReadByte;
90: }
91:
92: #define RC_INIT_VAR UInt32 range = rd->Range; UInt32 code = rd->Code;
93: #define RC_FLUSH_VAR rd->Range = range; rd->Code = code;
94: #define RC_NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | ReadByte; }
95:
96: UInt32 RangeDecoderDecodeDirectBits(CRangeDecoder *rd, int numTotalBits)
97: {
98: RC_INIT_VAR
99: UInt32 result = 0;
100: int i;
101: for (i = numTotalBits; i != 0; i--)
102: {
103: /* UInt32 t; */
104: range >>= 1;
105:
106: result <<= 1;
107: if (code >= range)
108: {
109: code -= range;
110: result |= 1;
111: }
112: /*
113: t = (code - range) >> 31;
114: t &= 1;
115: code -= range & (t - 1);
116: result = (result + result) | (1 - t);
117: */
118: RC_NORMALIZE
119: }
120: RC_FLUSH_VAR
121: return result;
122: }
123:
124: int RangeDecoderBitDecode(CProb *prob, CRangeDecoder *rd)
125: {
126: UInt32 bound = (rd->Range >> kNumBitModelTotalBits) * *prob;
127: if (rd->Code < bound)
128: {
129: rd->Range = bound;
130: *prob += (kBitModelTotal - *prob) >> kNumMoveBits;
131: if (rd->Range < kTopValue)
132: {
133: rd->Code = (rd->Code << 8) | ReadByte;
134: rd->Range <<= 8;
135: }
136: return 0;
137: }
138: else
139: {
140: rd->Range -= bound;
141: rd->Code -= bound;
142: *prob -= (*prob) >> kNumMoveBits;
143: if (rd->Range < kTopValue)
144: {
145: rd->Code = (rd->Code << 8) | ReadByte;
146: rd->Range <<= 8;
147: }
148: return 1;
149: }
150: }
151:
152: #define RC_GET_BIT2(prob, mi, A0, A1) \
153: UInt32 bound = (range >> kNumBitModelTotalBits) * *prob; \
154: if (code < bound) \
155: { A0; range = bound; *prob += (kBitModelTotal - *prob) >> kNumMoveBits; mi <<= 1; } \
156: else \
157: { A1; range -= bound; code -= bound; *prob -= (*prob) >> kNumMoveBits; mi = (mi + mi) + 1; } \
158: RC_NORMALIZE
159:
160: #define RC_GET_BIT(prob, mi) RC_GET_BIT2(prob, mi, ; , ;)
161:
162: int RangeDecoderBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd)
163: {
164: int mi = 1;
165: int i;
166: #ifdef _LZMA_LOC_OPT
167: RC_INIT_VAR
168: #endif
169: for(i = numLevels; i != 0; i--)
170: {
171: #ifdef _LZMA_LOC_OPT
172: CProb *prob = probs + mi;
173: RC_GET_BIT(prob, mi)
174: #else
175: mi = (mi + mi) + RangeDecoderBitDecode(probs + mi, rd);
176: #endif
177: }
178: #ifdef _LZMA_LOC_OPT
179: RC_FLUSH_VAR
180: #endif
181: return mi - (1 << numLevels);
182: }
183:
184: int RangeDecoderReverseBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd)
185: {
186: int mi = 1;
187: int i;
188: int symbol = 0;
189: #ifdef _LZMA_LOC_OPT
190: RC_INIT_VAR
191: #endif
192: for(i = 0; i < numLevels; i++)
193: {
194: #ifdef _LZMA_LOC_OPT
195: CProb *prob = probs + mi;
196: RC_GET_BIT2(prob, mi, ; , symbol |= (1 << i))
197: #else
198: int bit = RangeDecoderBitDecode(probs + mi, rd);
199: mi = mi + mi + bit;
200: symbol |= (bit << i);
201: #endif
202: }
203: #ifdef _LZMA_LOC_OPT
204: RC_FLUSH_VAR
205: #endif
206: return symbol;
207: }
208:
209: Byte LzmaLiteralDecode(CProb *probs, CRangeDecoder *rd)
210: {
211: int symbol = 1;
212: #ifdef _LZMA_LOC_OPT
213: RC_INIT_VAR
214: #endif
215: do
216: {
217: #ifdef _LZMA_LOC_OPT
218: CProb *prob = probs + symbol;
219: RC_GET_BIT(prob, symbol)
220: #else
221: symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd);
222: #endif
223: }
224: while (symbol < 0x100);
225: #ifdef _LZMA_LOC_OPT
226: RC_FLUSH_VAR
227: #endif
228: return symbol;
229: }
230:
231: Byte LzmaLiteralDecodeMatch(CProb *probs, CRangeDecoder *rd, Byte matchByte)
232: {
233: int symbol = 1;
234: #ifdef _LZMA_LOC_OPT
235: RC_INIT_VAR
236: #endif
237: do
238: {
239: int bit;
240: int matchBit = (matchByte >> 7) & 1;
241: matchByte <<= 1;
242: #ifdef _LZMA_LOC_OPT
243: {
244: CProb *prob = probs + 0x100 + (matchBit << 8) + symbol;
245: RC_GET_BIT2(prob, symbol, bit = 0, bit = 1)
246: }
247: #else
248: bit = RangeDecoderBitDecode(probs + 0x100 + (matchBit << 8) + symbol, rd);
249: symbol = (symbol << 1) | bit;
250: #endif
251: if (matchBit != bit)
252: {
253: while (symbol < 0x100)
254: {
255: #ifdef _LZMA_LOC_OPT
256: CProb *prob = probs + symbol;
257: RC_GET_BIT(prob, symbol)
258: #else
259: symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd);
260: #endif
261: }
262: break;
263: }
264: }
265: while (symbol < 0x100);
266: #ifdef _LZMA_LOC_OPT
267: RC_FLUSH_VAR
268: #endif
269: return symbol;
270: }
271:
272: #define kNumPosBitsMax 4
273: #define kNumPosStatesMax (1 << kNumPosBitsMax)
274:
275: #define kLenNumLowBits 3
276: #define kLenNumLowSymbols (1 << kLenNumLowBits)
277: #define kLenNumMidBits 3
278: #define kLenNumMidSymbols (1 << kLenNumMidBits)
279: #define kLenNumHighBits 8
280: #define kLenNumHighSymbols (1 << kLenNumHighBits)
281:
282: #define LenChoice 0
283: #define LenChoice2 (LenChoice + 1)
284: #define LenLow (LenChoice2 + 1)
285: #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
286: #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
287: #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
288:
289: int LzmaLenDecode(CProb *p, CRangeDecoder *rd, int posState)
290: {
291: if(RangeDecoderBitDecode(p + LenChoice, rd) == 0)
292: return RangeDecoderBitTreeDecode(p + LenLow +
293: (posState << kLenNumLowBits), kLenNumLowBits, rd);
294: if(RangeDecoderBitDecode(p + LenChoice2, rd) == 0)
295: return kLenNumLowSymbols + RangeDecoderBitTreeDecode(p + LenMid +
296: (posState << kLenNumMidBits), kLenNumMidBits, rd);
297: return kLenNumLowSymbols + kLenNumMidSymbols +
298: RangeDecoderBitTreeDecode(p + LenHigh, kLenNumHighBits, rd);
299: }
300:
301: #define kNumStates 12
302: #define kNumLitStates 7
303:
304: #define kStartPosModelIndex 4
305: #define kEndPosModelIndex 14
306: #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
307:
308: #define kNumPosSlotBits 6
309: #define kNumLenToPosStates 4
310:
311: #define kNumAlignBits 4
312: #define kAlignTableSize (1 << kNumAlignBits)
313:
314: #define kMatchMinLen 2
315:
316: #define IsMatch 0
317: #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
318: #define IsRepG0 (IsRep + kNumStates)
319: #define IsRepG1 (IsRepG0 + kNumStates)
320: #define IsRepG2 (IsRepG1 + kNumStates)
321: #define IsRep0Long (IsRepG2 + kNumStates)
322: #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
323: #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
324: #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
325: #define LenCoder (Align + kAlignTableSize)
326: #define RepLenCoder (LenCoder + kNumLenProbs)
327: #define Literal (RepLenCoder + kNumLenProbs)
328:
329: #if Literal != LZMA_BASE_SIZE
330: StopCompilingDueBUG
331: #endif
332:
333: #ifdef _LZMA_OUT_READ
334:
335: typedef struct _LzmaVarState
336: {
337: CRangeDecoder RangeDecoder;
338: Byte *Dictionary;
339: UInt32 DictionarySize;
340: UInt32 DictionaryPos;
341: UInt32 GlobalPos;
342: UInt32 Reps[4];
343: int lc;
344: int lp;
345: int pb;
346: int State;
347: int RemainLen;
348: Byte TempDictionary[4];
349: } LzmaVarState;
350:
351: int LzmaDecoderInit(
352: unsigned char *buffer, UInt32 bufferSize,
353: int lc, int lp, int pb,
354: unsigned char *dictionary, UInt32 dictionarySize,
355: #ifdef _LZMA_IN_CB
356: ILzmaInCallback *inCallback
357: #else
358: unsigned char *inStream, UInt32 inSize
359: #endif
360: )
361: {
362: LzmaVarState *vs = (LzmaVarState *)buffer;
363: CProb *p = (CProb *)(buffer + sizeof(LzmaVarState));
364: UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + lp));
365: UInt32 i;
366: if (bufferSize < numProbs * sizeof(CProb) + sizeof(LzmaVarState))
367: return LZMA_RESULT_NOT_ENOUGH_MEM;
368: vs->Dictionary = dictionary;
369: vs->DictionarySize = dictionarySize;
370: vs->DictionaryPos = 0;
371: vs->GlobalPos = 0;
372: vs->Reps[0] = vs->Reps[1] = vs->Reps[2] = vs->Reps[3] = 1;
373: vs->lc = lc;
374: vs->lp = lp;
375: vs->pb = pb;
376: vs->State = 0;
377: vs->RemainLen = 0;
378: dictionary[dictionarySize - 1] = 0;
379: for (i = 0; i < numProbs; i++)
380: p[i] = kBitModelTotal >> 1;
381: RangeDecoderInit(&vs->RangeDecoder,
382: #ifdef _LZMA_IN_CB
383: inCallback
384: #else
385: inStream, inSize
386: #endif
387: );
388: return LZMA_RESULT_OK;
389: }
390:
391: int LzmaDecode(unsigned char *buffer,
392: unsigned char *outStream, UInt32 outSize,
393: UInt32 *outSizeProcessed)
394: {
395: LzmaVarState *vs = (LzmaVarState *)buffer;
396: CProb *p = (CProb *)(buffer + sizeof(LzmaVarState));
397: CRangeDecoder rd = vs->RangeDecoder;
398: int state = vs->State;
399: Byte previousByte;
400: UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
401: UInt32 nowPos = 0;
402: UInt32 posStateMask = (1 << (vs->pb)) - 1;
403: UInt32 literalPosMask = (1 << (vs->lp)) - 1;
404: int lc = vs->lc;
405: int len = vs->RemainLen;
406: UInt32 globalPos = vs->GlobalPos;
407:
408: Byte *dictionary = vs->Dictionary;
409: UInt32 dictionarySize = vs->DictionarySize;
410: UInt32 dictionaryPos = vs->DictionaryPos;
411:
412: Byte tempDictionary[4];
413: if (dictionarySize == 0)
414: {
415: dictionary = tempDictionary;
416: dictionarySize = 1;
417: tempDictionary[0] = vs->TempDictionary[0];
418: }
419:
420: if (len == -1)
421: {
422: *outSizeProcessed = 0;
423: return LZMA_RESULT_OK;
424: }
425:
426: while(len != 0 && nowPos < outSize)
427: {
428: UInt32 pos = dictionaryPos - rep0;
429: if (pos >= dictionarySize)
430: pos += dictionarySize;
431: outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
432: if (++dictionaryPos == dictionarySize)
433: dictionaryPos = 0;
434: len--;
435: }
436: if (dictionaryPos == 0)
437: previousByte = dictionary[dictionarySize - 1];
438: else
439: previousByte = dictionary[dictionaryPos - 1];
440: #else
441:
442: int LzmaDecode(
443: Byte *buffer, UInt32 bufferSize,
444: int lc, int lp, int pb,
445: #ifdef _LZMA_IN_CB
446: ILzmaInCallback *inCallback,
447: #else
448: unsigned char *inStream, UInt32 inSize,
449: #endif
450: unsigned char *outStream, UInt32 outSize,
451: UInt32 *outSizeProcessed)
452: {
453: UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + lp));
454: CProb *p = (CProb *)buffer;
455: CRangeDecoder rd;
456: UInt32 i;
457: int state = 0;
458: Byte previousByte = 0;
459: UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
460: UInt32 nowPos = 0;
461: UInt32 posStateMask = (1 << pb) - 1;
462: UInt32 literalPosMask = (1 << lp) - 1;
463: int len = 0;
464: if (bufferSize < numProbs * sizeof(CProb))
465: return LZMA_RESULT_NOT_ENOUGH_MEM;
466: for (i = 0; i < numProbs; i++)
467: p[i] = kBitModelTotal >> 1;
468: RangeDecoderInit(&rd,
469: #ifdef _LZMA_IN_CB
470: inCallback
471: #else
472: inStream, inSize
473: #endif
474: );
475: #endif
476:
477: *outSizeProcessed = 0;
478: while(nowPos < outSize)
479: {
480: int posState = (int)(
481: (nowPos
482: #ifdef _LZMA_OUT_READ
483: + globalPos
484: #endif
485: )
486: & posStateMask);
487: #ifdef _LZMA_IN_CB
488: if (rd.Result != LZMA_RESULT_OK)
489: return rd.Result;
490: #endif
491: if (rd.ExtraBytes != 0)
492: return LZMA_RESULT_DATA_ERROR;
493: if (RangeDecoderBitDecode(p + IsMatch + (state << kNumPosBitsMax) + posState, &rd) == 0)
494: {
495: CProb *probs = p + Literal + (LZMA_LIT_SIZE *
496: (((
497: (nowPos
498: #ifdef _LZMA_OUT_READ
499: + globalPos
500: #endif
501: )
502: & literalPosMask) << lc) + (previousByte >> (8 - lc))));
503:
504: if (state >= kNumLitStates)
505: {
506: Byte matchByte;
507: #ifdef _LZMA_OUT_READ
508: UInt32 pos = dictionaryPos - rep0;
509: if (pos >= dictionarySize)
510: pos += dictionarySize;
511: matchByte = dictionary[pos];
512: #else
513: matchByte = outStream[nowPos - rep0];
514: #endif
515: previousByte = LzmaLiteralDecodeMatch(probs, &rd, matchByte);
516: }
517: else
518: previousByte = LzmaLiteralDecode(probs, &rd);
519: outStream[nowPos++] = previousByte;
520: #ifdef _LZMA_OUT_READ
521: dictionary[dictionaryPos] = previousByte;
522: if (++dictionaryPos == dictionarySize)
523: dictionaryPos = 0;
524: #endif
525: if (state < 4) state = 0;
526: else if (state < 10) state -= 3;
527: else state -= 6;
528: }
529: else
530: {
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 || rep0 > dictionarySize
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->RemainLen = len;
662: vs->TempDictionary[0] = tempDictionary[0];
663: #endif
664:
665: *outSizeProcessed = nowPos;
666: return LZMA_RESULT_OK;
667: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to LzmaDecodeSize.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