1 /*
2 LzmaDecode.c
3 LZMA Decoder (optimized for Speed 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 #if CONFIG(DECOMPRESS_OFAST)
23 #define __lzma_attribute_Ofast__ __attribute__((optimize("Ofast")))
24 #else
25 #define __lzma_attribute_Ofast__
26 #endif
27
28 #include "lzmadecode.h"
29 #include <types.h>
30
31 #define kNumTopBits 24
32 #define kTopValue ((UInt32)1 << kNumTopBits)
33
34 #define kNumBitModelTotalBits 11
35 #define kBitModelTotal (1 << kNumBitModelTotalBits)
36 #define kNumMoveBits 5
37
38 /* Use sizeof(SizeT) sized reads whenever possible to avoid bad flash performance. Fall back
39 * to byte reads for last sizeof(SizeT) bytes since RC_TEST returns an error when BufferLim
40 * is *reached* (not surpassed!), meaning we can't allow that to happen while
41 * there are still bytes to decode from the algorithm's point of view. */
42 #define RC_READ_BYTE \
43 (look_ahead_ptr < sizeof(SizeT) ? look_ahead.raw[look_ahead_ptr++] \
44 : ((((uintptr_t) Buffer & (sizeof(SizeT) - 1)) \
45 || ((SizeT) (BufferLim - Buffer) <= sizeof(SizeT))) ? (*Buffer++) \
46 : ((look_ahead.dw = *(SizeT *)Buffer), (Buffer += sizeof(SizeT)), \
47 (look_ahead_ptr = 1), look_ahead.raw[0])))
48
49 #define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \
50 { \
51 int i; \
52 \
53 for (i = 0; i < 5; i++) { \
54 RC_TEST; \
55 Code = (Code << 8) | RC_READ_BYTE; \
56 } \
57 }
58
59
60 #define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
61
62 #define RC_INIT(buffer, bufferSize) Buffer = buffer; \
63 BufferLim = buffer + bufferSize; RC_INIT2
64
65
66 #define RC_NORMALIZE \
67 if (Range < kTopValue) { \
68 RC_TEST; \
69 Range <<= 8; \
70 Code = (Code << 8) | RC_READ_BYTE; \
71 }
72
73 #define IfBit0(p) \
74 RC_NORMALIZE; \
75 bound = (Range >> kNumBitModelTotalBits) * *(p); \
76 if (Code < bound)
77
78 #define UpdateBit0(p) \
79 Range = bound; \
80 *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits
81
82 #define UpdateBit1(p) \
83 Range -= bound; \
84 Code -= bound; \
85 *(p) -= (*(p)) >> kNumMoveBits
86
87 #define RC_GET_BIT2(p, mi, A0, A1) \
88 IfBit0(p) { \
89 UpdateBit0(p); \
90 mi <<= 1; \
91 A0; \
92 } else { \
93 UpdateBit1(p); \
94 mi = (mi + mi) + 1; \
95 A1; \
96 }
97
98 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ;, ;)
99
100 #define RangeDecoderBitTreeDecode(probs, numLevels, res) \
101 { \
102 int i = numLevels; \
103 \
104 res = 1; \
105 do { \
106 CProb *cp = probs + res; \
107 RC_GET_BIT(cp, res) \
108 } while (--i != 0); \
109 res -= (1 << numLevels); \
110 }
111
112
113 #define kNumPosBitsMax 4
114 #define kNumPosStatesMax (1 << kNumPosBitsMax)
115
116 #define kLenNumLowBits 3
117 #define kLenNumLowSymbols (1 << kLenNumLowBits)
118 #define kLenNumMidBits 3
119 #define kLenNumMidSymbols (1 << kLenNumMidBits)
120 #define kLenNumHighBits 8
121 #define kLenNumHighSymbols (1 << kLenNumHighBits)
122
123 #define LenChoice 0
124 #define LenChoice2 (LenChoice + 1)
125 #define LenLow (LenChoice2 + 1)
126 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
127 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
128 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
129
130
131 #define kNumStates 12
132 #define kNumLitStates 7
133
134 #define kStartPosModelIndex 4
135 #define kEndPosModelIndex 14
136 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
137
138 #define kNumPosSlotBits 6
139 #define kNumLenToPosStates 4
140
141 #define kNumAlignBits 4
142 #define kAlignTableSize (1 << kNumAlignBits)
143
144 #define kMatchMinLen 2
145
146 #define IsMatch 0
147 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
148 #define IsRepG0 (IsRep + kNumStates)
149 #define IsRepG1 (IsRepG0 + kNumStates)
150 #define IsRepG2 (IsRepG1 + kNumStates)
151 #define IsRep0Long (IsRepG2 + kNumStates)
152 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
153 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
154 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
155 #define LenCoder (Align + kAlignTableSize)
156 #define RepLenCoder (LenCoder + kNumLenProbs)
157 #define Literal (RepLenCoder + kNumLenProbs)
158
159 #if Literal != LZMA_BASE_SIZE
160 StopCompilingDueBUG
161 #endif
162
LzmaDecodeProperties(CLzmaProperties * propsRes,const unsigned char * propsData,int size)163 int LzmaDecodeProperties(CLzmaProperties *propsRes,
164 const unsigned char *propsData, int size)
165 {
166 unsigned char prop0;
167 if (size < LZMA_PROPERTIES_SIZE)
168 return LZMA_RESULT_DATA_ERROR;
169 prop0 = propsData[0];
170 if (prop0 >= (9 * 5 * 5))
171 return LZMA_RESULT_DATA_ERROR;
172 {
173 for (propsRes->pb = 0; prop0 >= (9 * 5);
174 propsRes->pb++, prop0 -= (9 * 5))
175 ;
176 for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9)
177 ;
178 propsRes->lc = prop0;
179 /*
180 * unsigned char remainder = (unsigned char)(prop0 / 9);
181 * propsRes->lc = prop0 % 9;
182 * propsRes->pb = remainder / 5;
183 * propsRes->lp = remainder % 5;
184 */
185 }
186
187 return LZMA_RESULT_OK;
188 }
189
190 #define kLzmaStreamWasFinishedId (-1)
191
192 __lzma_attribute_Ofast__
LzmaDecode(CLzmaDecoderState * vs,const unsigned char * inStream,SizeT inSize,SizeT * inSizeProcessed,unsigned char * outStream,SizeT outSize,SizeT * outSizeProcessed)193 int LzmaDecode(CLzmaDecoderState *vs,
194 const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
195 unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
196 {
197 CProb *p = vs->Probs;
198 SizeT nowPos = 0;
199 Byte previousByte = 0;
200 UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
201 UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
202 int lc = vs->Properties.lc;
203
204
205 int state = 0;
206 UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
207 int len = 0;
208 const Byte *Buffer;
209 const Byte *BufferLim;
210 int look_ahead_ptr = sizeof(SizeT);
211 union {
212 Byte raw[sizeof(SizeT)];
213 SizeT dw;
214 } look_ahead;
215 UInt32 Range;
216 UInt32 Code;
217
218 *inSizeProcessed = 0;
219 *outSizeProcessed = 0;
220
221 {
222 UInt32 i;
223 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc
224 + vs->Properties.lp));
225 for (i = 0; i < numProbs; i++)
226 p[i] = kBitModelTotal >> 1;
227 }
228
229 RC_INIT(inStream, inSize);
230
231
232 while (nowPos < outSize) {
233 CProb *prob;
234 UInt32 bound;
235 int posState = (int)((nowPos)&posStateMask);
236
237 prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
238 IfBit0(prob) {
239 int symbol = 1;
240 UpdateBit0(prob);
241 prob = p + Literal + (LZMA_LIT_SIZE *
242 ((((nowPos) & literalPosMask) << lc)
243 + (previousByte >> (8 - lc))));
244
245 if (state >= kNumLitStates) {
246 int matchByte;
247 matchByte = outStream[nowPos - rep0];
248 do {
249 int bit;
250 CProb *probLit;
251 matchByte <<= 1;
252 bit = (matchByte & 0x100);
253 probLit = prob + 0x100 + bit + symbol;
254 RC_GET_BIT2(probLit, symbol,
255 if (bit != 0)
256 break,
257 if (bit == 0)
258 break)
259 } while (symbol < 0x100);
260 }
261 while (symbol < 0x100) {
262 CProb *probLit = prob + symbol;
263 RC_GET_BIT(probLit, symbol)
264 }
265 previousByte = (Byte)symbol;
266
267 outStream[nowPos++] = previousByte;
268 if (state < 4)
269 state = 0;
270 else if (state < 10)
271 state -= 3;
272 else
273 state -= 6;
274 } else {
275 UpdateBit1(prob);
276 prob = p + IsRep + state;
277 IfBit0(prob) {
278 UpdateBit0(prob);
279 rep3 = rep2;
280 rep2 = rep1;
281 rep1 = rep0;
282 state = state < kNumLitStates ? 0 : 3;
283 prob = p + LenCoder;
284 } else {
285 UpdateBit1(prob);
286 prob = p + IsRepG0 + state;
287 IfBit0(prob) {
288 UpdateBit0(prob);
289 prob = p + IsRep0Long
290 + (state << kNumPosBitsMax)
291 + posState;
292 IfBit0(prob) {
293 UpdateBit0(prob);
294
295 if (nowPos == 0)
296 return LZMA_RESULT_DATA_ERROR;
297
298 state = state < kNumLitStates
299 ? 9 : 11;
300 previousByte = outStream[nowPos
301 - rep0];
302 outStream[nowPos++] =
303 previousByte;
304
305 continue;
306 } else {
307 UpdateBit1(prob);
308 }
309 } else {
310 UInt32 distance;
311 UpdateBit1(prob);
312 prob = p + IsRepG1 + state;
313 IfBit0(prob) {
314 UpdateBit0(prob);
315 distance = rep1;
316 } else {
317 UpdateBit1(prob);
318 prob = p + IsRepG2 + state;
319 IfBit0(prob) {
320 UpdateBit0(prob);
321 distance = rep2;
322 } else {
323 UpdateBit1(prob);
324 distance = rep3;
325 rep3 = rep2;
326 }
327 rep2 = rep1;
328 }
329 rep1 = rep0;
330 rep0 = distance;
331 }
332 state = state < kNumLitStates ? 8 : 11;
333 prob = p + RepLenCoder;
334 }
335 {
336 int numBits, offset;
337 CProb *probLen = prob + LenChoice;
338 IfBit0(probLen) {
339 UpdateBit0(probLen);
340 probLen = prob + LenLow
341 + (posState << kLenNumLowBits);
342 offset = 0;
343 numBits = kLenNumLowBits;
344 } else {
345 UpdateBit1(probLen);
346 probLen = prob + LenChoice2;
347 IfBit0(probLen) {
348 UpdateBit0(probLen);
349 probLen = prob + LenMid
350 + (posState <<
351 kLenNumMidBits);
352 offset = kLenNumLowSymbols;
353 numBits = kLenNumMidBits;
354 } else {
355 UpdateBit1(probLen);
356 probLen = prob + LenHigh;
357 offset = kLenNumLowSymbols
358 + kLenNumMidSymbols;
359 numBits = kLenNumHighBits;
360 }
361 }
362 RangeDecoderBitTreeDecode(probLen, numBits,
363 len);
364 len += offset;
365 }
366
367 if (state < 4) {
368 int posSlot;
369 state += kNumLitStates;
370 prob = p + PosSlot +
371 ((len < kNumLenToPosStates ? len :
372 kNumLenToPosStates - 1) <<
373 kNumPosSlotBits);
374 RangeDecoderBitTreeDecode(prob, kNumPosSlotBits,
375 posSlot);
376 if (posSlot >= kStartPosModelIndex) {
377 int numDirectBits = ((posSlot >> 1)
378 - 1);
379 rep0 = (2 | ((UInt32)posSlot & 1));
380 if (posSlot < kEndPosModelIndex) {
381 rep0 <<= numDirectBits;
382 prob = p + SpecPos + rep0
383 - posSlot - 1;
384 } else {
385 numDirectBits -= kNumAlignBits;
386 do {
387 RC_NORMALIZE
388 Range >>= 1;
389 rep0 <<= 1;
390 if (Code >= Range) {
391 Code -= Range;
392 rep0 |= 1;
393 }
394 } while (--numDirectBits != 0);
395 prob = p + Align;
396 rep0 <<= kNumAlignBits;
397 numDirectBits = kNumAlignBits;
398 }
399 {
400 int i = 1;
401 int mi = 1;
402 do {
403 CProb *prob3 = prob
404 + mi;
405 RC_GET_BIT2(prob3, mi,
406 ;, rep0 |= i);
407 i <<= 1;
408 } while (--numDirectBits != 0);
409 }
410 } else
411 rep0 = posSlot;
412 if (++rep0 == (UInt32)(0)) {
413 /* it's for stream version */
414 len = kLzmaStreamWasFinishedId;
415 break;
416 }
417 }
418
419 len += kMatchMinLen;
420 if (rep0 > nowPos)
421 return LZMA_RESULT_DATA_ERROR;
422
423
424 do {
425 previousByte = outStream[nowPos - rep0];
426 len--;
427 outStream[nowPos++] = previousByte;
428 } while (len != 0 && nowPos < outSize);
429 }
430 }
431 RC_NORMALIZE;
432 /*
433 * Tell static analysis we know len can have a dead assignment.
434 */
435 (void)len;
436
437
438 *inSizeProcessed = (SizeT)(Buffer - inStream);
439 *outSizeProcessed = nowPos;
440 return LZMA_RESULT_OK;
441 }
442