1 --- /dev/null 2005-12-16 15:50:59.000000000 +0100
2 +++ rpm-4.4.5/rpmio/LzmaDecode.c 2006-04-23 13:07:24.000000000 +0200
6 + LZMA Decoder (optimized for Speed version)
8 + LZMA SDK 4.22 Copyright (c) 1999-2005 Igor Pavlov (2005-06-10)
9 + http://www.7-zip.org/
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.
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.
25 +#include "LzmaDecode.h"
28 +#define Byte unsigned char
31 +#define kNumTopBits 24
32 +#define kTopValue ((UInt32)1 << kNumTopBits)
34 +#define kNumBitModelTotalBits 11
35 +#define kBitModelTotal (1 << kNumBitModelTotalBits)
36 +#define kNumMoveBits 5
38 +#define RC_READ_BYTE (*Buffer++)
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; }}
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; }}
49 +#define RC_INIT Buffer = BufferLim = 0; RC_INIT2
53 +#define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
55 +#define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
59 +#define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
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;
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; }
69 +#define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
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); }
77 +#define kNumPosBitsMax 4
78 +#define kNumPosStatesMax (1 << kNumPosBitsMax)
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)
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)
95 +#define kNumStates 12
96 +#define kNumLitStates 7
98 +#define kStartPosModelIndex 4
99 +#define kEndPosModelIndex 14
100 +#define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
102 +#define kNumPosSlotBits 6
103 +#define kNumLenToPosStates 4
105 +#define kNumAlignBits 4
106 +#define kAlignTableSize (1 << kNumAlignBits)
108 +#define kMatchMinLen 2
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)
123 +#if Literal != LZMA_BASE_SIZE
127 +int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
129 + unsigned char prop0;
130 + if (size < LZMA_PROPERTIES_SIZE)
131 + return LZMA_RESULT_DATA_ERROR;
132 + prop0 = propsData[0];
133 + if (prop0 >= (9 * 5 * 5))
134 + return LZMA_RESULT_DATA_ERROR;
136 + for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
137 + for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
138 + propsRes->lc = prop0;
140 + unsigned char remainder = (unsigned char)(prop0 / 9);
141 + propsRes->lc = prop0 % 9;
142 + propsRes->pb = remainder / 5;
143 + propsRes->lp = remainder % 5;
147 + #ifdef _LZMA_OUT_READ
150 + propsRes->DictionarySize = 0;
151 + for (i = 0; i < 4; i++)
152 + propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);
153 + if (propsRes->DictionarySize == 0)
154 + propsRes->DictionarySize = 1;
157 + return LZMA_RESULT_OK;
160 +#define kLzmaStreamWasFinishedId (-1)
162 +int LzmaDecode(CLzmaDecoderState *vs,
164 + ILzmaInCallback *InCallback,
166 + const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
168 + unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
170 + CProb *p = vs->Probs;
172 + Byte previousByte = 0;
173 + UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
174 + UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
175 + int lc = vs->Properties.lc;
177 + #ifdef _LZMA_OUT_READ
179 + UInt32 Range = vs->Range;
180 + UInt32 Code = vs->Code;
182 + const Byte *Buffer = vs->Buffer;
183 + const Byte *BufferLim = vs->BufferLim;
185 + const Byte *Buffer = inStream;
186 + const Byte *BufferLim = inStream + inSize;
188 + int state = vs->State;
189 + UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
190 + int len = vs->RemainLen;
191 + UInt32 globalPos = vs->GlobalPos;
192 + UInt32 distanceLimit = vs->DistanceLimit;
194 + Byte *dictionary = vs->Dictionary;
195 + UInt32 dictionarySize = vs->Properties.DictionarySize;
196 + UInt32 dictionaryPos = vs->DictionaryPos;
198 + Byte tempDictionary[4];
200 + #ifndef _LZMA_IN_CB
201 + *inSizeProcessed = 0;
203 + *outSizeProcessed = 0;
204 + if (len == kLzmaStreamWasFinishedId)
205 + return LZMA_RESULT_OK;
207 + if (dictionarySize == 0)
209 + dictionary = tempDictionary;
210 + dictionarySize = 1;
211 + tempDictionary[0] = vs->TempDictionary[0];
214 + if (len == kLzmaNeedInitId)
217 + UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
219 + for (i = 0; i < numProbs; i++)
220 + p[i] = kBitModelTotal >> 1;
221 + rep0 = rep1 = rep2 = rep3 = 1;
226 + dictionary[dictionarySize - 1] = 0;
230 + RC_INIT(inStream, inSize);
235 + while(len != 0 && nowPos < outSize)
237 + UInt32 pos = dictionaryPos - rep0;
238 + if (pos >= dictionarySize)
239 + pos += dictionarySize;
240 + outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
241 + if (++dictionaryPos == dictionarySize)
245 + if (dictionaryPos == 0)
246 + previousByte = dictionary[dictionarySize - 1];
248 + previousByte = dictionary[dictionaryPos - 1];
250 + #else /* if !_LZMA_OUT_READ */
253 + UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
255 + const Byte *Buffer;
256 + const Byte *BufferLim;
260 + #ifndef _LZMA_IN_CB
261 + *inSizeProcessed = 0;
263 + *outSizeProcessed = 0;
267 + UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
268 + for (i = 0; i < numProbs; i++)
269 + p[i] = kBitModelTotal >> 1;
275 + RC_INIT(inStream, inSize);
278 + #endif /* _LZMA_OUT_READ */
280 + while(nowPos < outSize)
284 + int posState = (int)(
286 + #ifdef _LZMA_OUT_READ
292 + prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
297 + prob = p + Literal + (LZMA_LIT_SIZE *
300 + #ifdef _LZMA_OUT_READ
304 + & literalPosMask) << lc) + (previousByte >> (8 - lc))));
306 + if (state >= kNumLitStates)
309 + #ifdef _LZMA_OUT_READ
310 + UInt32 pos = dictionaryPos - rep0;
311 + if (pos >= dictionarySize)
312 + pos += dictionarySize;
313 + matchByte = dictionary[pos];
315 + matchByte = outStream[nowPos - rep0];
322 + bit = (matchByte & 0x100);
323 + probLit = prob + 0x100 + bit + symbol;
324 + RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
326 + while (symbol < 0x100);
328 + while (symbol < 0x100)
330 + CProb *probLit = prob + symbol;
331 + RC_GET_BIT(probLit, symbol)
333 + previousByte = (Byte)symbol;
335 + outStream[nowPos++] = previousByte;
336 + #ifdef _LZMA_OUT_READ
337 + if (distanceLimit < dictionarySize)
340 + dictionary[dictionaryPos] = previousByte;
341 + if (++dictionaryPos == dictionarySize)
344 + if (state < 4) state = 0;
345 + else if (state < 10) state -= 3;
351 + prob = p + IsRep + state;
358 + state = state < kNumLitStates ? 0 : 3;
359 + prob = p + LenCoder;
364 + prob = p + IsRepG0 + state;
368 + prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
371 + #ifdef _LZMA_OUT_READ
376 + #ifdef _LZMA_OUT_READ
377 + if (distanceLimit == 0)
381 + return LZMA_RESULT_DATA_ERROR;
383 + state = state < kNumLitStates ? 9 : 11;
384 + #ifdef _LZMA_OUT_READ
385 + pos = dictionaryPos - rep0;
386 + if (pos >= dictionarySize)
387 + pos += dictionarySize;
388 + previousByte = dictionary[pos];
389 + dictionary[dictionaryPos] = previousByte;
390 + if (++dictionaryPos == dictionarySize)
393 + previousByte = outStream[nowPos - rep0];
395 + outStream[nowPos++] = previousByte;
396 + #ifdef _LZMA_OUT_READ
397 + if (distanceLimit < dictionarySize)
412 + prob = p + IsRepG1 + state;
421 + prob = p + IsRepG2 + state;
438 + state = state < kNumLitStates ? 8 : 11;
439 + prob = p + RepLenCoder;
442 + int numBits, offset;
443 + CProb *probLen = prob + LenChoice;
446 + UpdateBit0(probLen);
447 + probLen = prob + LenLow + (posState << kLenNumLowBits);
449 + numBits = kLenNumLowBits;
453 + UpdateBit1(probLen);
454 + probLen = prob + LenChoice2;
457 + UpdateBit0(probLen);
458 + probLen = prob + LenMid + (posState << kLenNumMidBits);
459 + offset = kLenNumLowSymbols;
460 + numBits = kLenNumMidBits;
464 + UpdateBit1(probLen);
465 + probLen = prob + LenHigh;
466 + offset = kLenNumLowSymbols + kLenNumMidSymbols;
467 + numBits = kLenNumHighBits;
470 + RangeDecoderBitTreeDecode(probLen, numBits, len);
477 + state += kNumLitStates;
478 + prob = p + PosSlot +
479 + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
481 + RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
482 + if (posSlot >= kStartPosModelIndex)
484 + int numDirectBits = ((posSlot >> 1) - 1);
485 + rep0 = (2 | ((UInt32)posSlot & 1));
486 + if (posSlot < kEndPosModelIndex)
488 + rep0 <<= numDirectBits;
489 + prob = p + SpecPos + rep0 - posSlot - 1;
493 + numDirectBits -= kNumAlignBits;
505 + while (--numDirectBits != 0);
507 + rep0 <<= kNumAlignBits;
508 + numDirectBits = kNumAlignBits;
515 + CProb *prob3 = prob + mi;
516 + RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
519 + while(--numDirectBits != 0);
524 + if (++rep0 == (UInt32)(0))
526 + /* it's for stream version */
527 + len = kLzmaStreamWasFinishedId;
532 + len += kMatchMinLen;
533 + #ifdef _LZMA_OUT_READ
534 + if (rep0 > distanceLimit)
538 + return LZMA_RESULT_DATA_ERROR;
540 + #ifdef _LZMA_OUT_READ
541 + if (dictionarySize - distanceLimit > (UInt32)len)
542 + distanceLimit += len;
544 + distanceLimit = dictionarySize;
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)
558 + previousByte = outStream[nowPos - rep0];
561 + outStream[nowPos++] = previousByte;
563 + while(len != 0 && nowPos < outSize);
568 + #ifdef _LZMA_OUT_READ
571 + vs->DictionaryPos = dictionaryPos;
572 + vs->GlobalPos = globalPos + (UInt32)nowPos;
573 + vs->DistanceLimit = distanceLimit;
574 + vs->Reps[0] = rep0;
575 + vs->Reps[1] = rep1;
576 + vs->Reps[2] = rep2;
577 + vs->Reps[3] = rep3;
579 + vs->RemainLen = len;
580 + vs->TempDictionary[0] = tempDictionary[0];
584 + vs->Buffer = Buffer;
585 + vs->BufferLim = BufferLim;
587 + *inSizeProcessed = (SizeT)(Buffer - inStream);
589 + *outSizeProcessed = nowPos;
590 + return LZMA_RESULT_OK;
592 --- /dev/null 2005-12-16 15:50:59.000000000 +0100
593 +++ rpm-4.4.5/rpmio/LzmaDecode.h 2006-04-23 13:25:41.000000000 +0200
597 + LZMA Decoder interface
599 + LZMA SDK 4.21 Copyright (c) 1999-2005 Igor Pavlov (2005-06-08)
600 + http://www.7-zip.org/
602 + LZMA SDK is licensed under two licenses:
603 + 1) GNU Lesser General Public License (GNU LGPL)
604 + 2) Common Public License (CPL)
605 + It means that you can select one of these two licenses and
606 + follow rules of that license.
609 + Igor Pavlov, as the author of this code, expressly permits you to
610 + statically or dynamically link your code (or bind by name) to the
611 + interfaces of this file without subjecting your linked code to the
612 + terms of the CPL or GNU LGPL. Any modifications or additions
613 + to this file, however, are subject to the LGPL or CPL terms.
616 +#ifndef __LZMADECODE_H
617 +#define __LZMADECODE_H
620 +/* Use callback for input data */
622 +#define _LZMA_OUT_READ
623 +/* Use read function for output data */
625 +/* #define _LZMA_PROB32 */
626 +/* It can increase speed on some 32-bit CPUs,
627 + but memory usage will be doubled in that case */
629 +/* #define _LZMA_LOC_OPT */
630 +/* Enable local speed optimizations inside code */
632 +/* #define _LZMA_SYSTEM_SIZE_T */
633 +/* Use system's size_t. You can use it to enable 64-bit sizes supporting*/
636 +#ifdef _LZMA_UINT32_IS_ULONG
637 +#define UInt32 unsigned long
639 +#define UInt32 unsigned int
644 +#ifdef _LZMA_SYSTEM_SIZE_T
646 +#define SizeT size_t
648 +#define SizeT UInt32
653 +#define CProb UInt32
655 +#define CProb unsigned short
658 +#define LZMA_RESULT_OK 0
659 +#define LZMA_RESULT_DATA_ERROR 1
662 +typedef struct _ILzmaInCallback
664 + int (*Read)(void *object, const unsigned char **buffer, SizeT *bufferSize);
668 +#define LZMA_BASE_SIZE 1846
669 +#define LZMA_LIT_SIZE 768
671 +#define LZMA_PROPERTIES_SIZE 5
673 +typedef struct _CLzmaProperties
678 + #ifdef _LZMA_OUT_READ
679 + UInt32 DictionarySize;
683 +int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size);
685 +#define LzmaGetNumProbs(Properties) (LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((Properties)->lc + (Properties)->lp)))
687 +#define kLzmaNeedInitId (-2)
689 +typedef struct _CLzmaDecoderState
691 + CLzmaProperties Properties;
695 + const unsigned char *Buffer;
696 + const unsigned char *BufferLim;
699 + #ifdef _LZMA_OUT_READ
700 + unsigned char *Dictionary;
703 + UInt32 DictionaryPos;
705 + UInt32 DistanceLimit;
709 + unsigned char TempDictionary[4];
711 +} CLzmaDecoderState;
713 +#ifdef _LZMA_OUT_READ
714 +#define LzmaDecoderInit(vs) { (vs)->RemainLen = kLzmaNeedInitId; }
717 +int LzmaDecode(CLzmaDecoderState *vs,
719 + ILzmaInCallback *inCallback,
721 + const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
723 + unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed);