1 /*
2 LzmaDecode.c
3 LZMA Decoder (optimized for Speed version)
4
5 LZMA SDK 4.22 Copyright (c) 1999-2005 Igor Pavlov (2005-06-10)
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 { SizeT 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
LzmaDecodeProperties(CLzmaProperties * propsRes,const unsigned char * propsData,int size)124 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
125 {
126 unsigned char prop0;
127 if (size < LZMA_PROPERTIES_SIZE)
128 return LZMA_RESULT_DATA_ERROR;
129 prop0 = propsData[0];
130 if (prop0 >= (9 * 5 * 5))
131 return LZMA_RESULT_DATA_ERROR;
132 {
133 for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
134 for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
135 propsRes->lc = prop0;
136 /*
137 unsigned char remainder = (unsigned char)(prop0 / 9);
138 propsRes->lc = prop0 % 9;
139 propsRes->pb = remainder / 5;
140 propsRes->lp = remainder % 5;
141 */
142 }
143
144 #ifdef _LZMA_OUT_READ
145 {
146 int i;
147 propsRes->DictionarySize = 0;
148 for (i = 0; i < 4; i++)
149 propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);
150 if (propsRes->DictionarySize == 0)
151 propsRes->DictionarySize = 1;
152 }
153 #endif
154 return LZMA_RESULT_OK;
155 }
156
157 #define kLzmaStreamWasFinishedId (-1)
158
LzmaDecode(CLzmaDecoderState * vs,ILzmaInCallback * InCallback,unsigned char * outStream,SizeT outSize,SizeT * outSizeProcessed)159 int LzmaDecode(CLzmaDecoderState *vs,
160 #ifdef _LZMA_IN_CB
161 ILzmaInCallback *InCallback,
162 #else
163 const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
164 #endif
165 unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
166 {
167 CProb *p = vs->Probs;
168 SizeT nowPos = 0;
169 Byte previousByte = 0;
170 UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
171 UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
172 int lc = vs->Properties.lc;
173
174 #ifdef _LZMA_OUT_READ
175
176 UInt32 Range = vs->Range;
177 UInt32 Code = vs->Code;
178 #ifdef _LZMA_IN_CB
179 const Byte *Buffer = vs->Buffer;
180 const Byte *BufferLim = vs->BufferLim;
181 #else
182 const Byte *Buffer = inStream;
183 const Byte *BufferLim = inStream + inSize;
184 #endif
185 int state = vs->State;
186 UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
187 int len = vs->RemainLen;
188 UInt32 globalPos = vs->GlobalPos;
189 UInt32 distanceLimit = vs->DistanceLimit;
190
191 Byte *dictionary = vs->Dictionary;
192 UInt32 dictionarySize = vs->Properties.DictionarySize;
193 UInt32 dictionaryPos = vs->DictionaryPos;
194
195 Byte tempDictionary[4];
196
197 #ifndef _LZMA_IN_CB
198 *inSizeProcessed = 0;
199 #endif
200 *outSizeProcessed = 0;
201 if (len == kLzmaStreamWasFinishedId)
202 return LZMA_RESULT_OK;
203
204 if (dictionarySize == 0)
205 {
206 dictionary = tempDictionary;
207 dictionarySize = 1;
208 tempDictionary[0] = vs->TempDictionary[0];
209 }
210
211 if (len == kLzmaNeedInitId)
212 {
213 {
214 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
215 UInt32 i;
216 for (i = 0; i < numProbs; i++)
217 p[i] = kBitModelTotal >> 1;
218 rep0 = rep1 = rep2 = rep3 = 1;
219 state = 0;
220 globalPos = 0;
221 distanceLimit = 0;
222 dictionaryPos = 0;
223 dictionary[dictionarySize - 1] = 0;
224 #ifdef _LZMA_IN_CB
225 RC_INIT;
226 #else
227 RC_INIT(inStream, inSize);
228 #endif
229 }
230 len = 0;
231 }
232 while(len != 0 && nowPos < outSize)
233 {
234 UInt32 pos = dictionaryPos - rep0;
235 if (pos >= dictionarySize)
236 pos += dictionarySize;
237 outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
238 if (++dictionaryPos == dictionarySize)
239 dictionaryPos = 0;
240 len--;
241 }
242 if (dictionaryPos == 0)
243 previousByte = dictionary[dictionarySize - 1];
244 else
245 previousByte = dictionary[dictionaryPos - 1];
246
247 #else /* if !_LZMA_OUT_READ */
248
249 int state = 0;
250 UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
251 int len = 0;
252 const Byte *Buffer;
253 const Byte *BufferLim;
254 UInt32 Range;
255 UInt32 Code;
256
257 #ifndef _LZMA_IN_CB
258 *inSizeProcessed = 0;
259 #endif
260 *outSizeProcessed = 0;
261
262 {
263 UInt32 i;
264 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
265 for (i = 0; i < numProbs; i++)
266 p[i] = kBitModelTotal >> 1;
267 }
268
269 #ifdef _LZMA_IN_CB
270 RC_INIT;
271 #else
272 RC_INIT(inStream, inSize);
273 #endif
274
275 #endif /* _LZMA_OUT_READ */
276
277 while(nowPos < outSize)
278 {
279 CProb *prob;
280 UInt32 bound;
281 int posState = (int)(
282 (nowPos
283 #ifdef _LZMA_OUT_READ
284 + globalPos
285 #endif
286 )
287 & posStateMask);
288
289 prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
290 IfBit0(prob)
291 {
292 int symbol = 1;
293 UpdateBit0(prob)
294 prob = p + Literal + (LZMA_LIT_SIZE *
295 (((
296 (nowPos
297 #ifdef _LZMA_OUT_READ
298 + globalPos
299 #endif
300 )
301 & literalPosMask) << lc) + (previousByte >> (8 - lc))));
302
303 if (state >= kNumLitStates)
304 {
305 int matchByte;
306 #ifdef _LZMA_OUT_READ
307 UInt32 pos = dictionaryPos - rep0;
308 if (pos >= dictionarySize)
309 pos += dictionarySize;
310 matchByte = dictionary[pos];
311 #else
312 matchByte = outStream[nowPos - rep0];
313 #endif
314 do
315 {
316 int bit;
317 CProb *probLit;
318 matchByte <<= 1;
319 bit = (matchByte & 0x100);
320 probLit = prob + 0x100 + bit + symbol;
321 RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
322 }
323 while (symbol < 0x100);
324 }
325 while (symbol < 0x100)
326 {
327 CProb *probLit = prob + symbol;
328 RC_GET_BIT(probLit, symbol)
329 }
330 previousByte = (Byte)symbol;
331
332 outStream[nowPos++] = previousByte;
333 #ifdef _LZMA_OUT_READ
334 if (distanceLimit < dictionarySize)
335 distanceLimit++;
336
337 dictionary[dictionaryPos] = previousByte;
338 if (++dictionaryPos == dictionarySize)
339 dictionaryPos = 0;
340 #endif
341 if (state < 4) state = 0;
342 else if (state < 10) state -= 3;
343 else state -= 6;
344 }
345 else
346 {
347 UpdateBit1(prob);
348 prob = p + IsRep + state;
349 IfBit0(prob)
350 {
351 UpdateBit0(prob);
352 rep3 = rep2;
353 rep2 = rep1;
354 rep1 = rep0;
355 state = state < kNumLitStates ? 0 : 3;
356 prob = p + LenCoder;
357 }
358 else
359 {
360 UpdateBit1(prob);
361 prob = p + IsRepG0 + state;
362 IfBit0(prob)
363 {
364 UpdateBit0(prob);
365 prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
366 IfBit0(prob)
367 {
368 #ifdef _LZMA_OUT_READ
369 UInt32 pos;
370 #endif
371 UpdateBit0(prob);
372
373 #ifdef _LZMA_OUT_READ
374 if (distanceLimit == 0)
375 #else
376 if (nowPos == 0)
377 #endif
378 return LZMA_RESULT_DATA_ERROR;
379
380 state = state < kNumLitStates ? 9 : 11;
381 #ifdef _LZMA_OUT_READ
382 pos = dictionaryPos - rep0;
383 if (pos >= dictionarySize)
384 pos += dictionarySize;
385 previousByte = dictionary[pos];
386 dictionary[dictionaryPos] = previousByte;
387 if (++dictionaryPos == dictionarySize)
388 dictionaryPos = 0;
389 #else
390 previousByte = outStream[nowPos - rep0];
391 #endif
392 outStream[nowPos++] = previousByte;
393 #ifdef _LZMA_OUT_READ
394 if (distanceLimit < dictionarySize)
395 distanceLimit++;
396 #endif
397
398 continue;
399 }
400 else
401 {
402 UpdateBit1(prob);
403 }
404 }
405 else
406 {
407 UInt32 distance;
408 UpdateBit1(prob);
409 prob = p + IsRepG1 + state;
410 IfBit0(prob)
411 {
412 UpdateBit0(prob);
413 distance = rep1;
414 }
415 else
416 {
417 UpdateBit1(prob);
418 prob = p + IsRepG2 + state;
419 IfBit0(prob)
420 {
421 UpdateBit0(prob);
422 distance = rep2;
423 }
424 else
425 {
426 UpdateBit1(prob);
427 distance = rep3;
428 rep3 = rep2;
429 }
430 rep2 = rep1;
431 }
432 rep1 = rep0;
433 rep0 = distance;
434 }
435 state = state < kNumLitStates ? 8 : 11;
436 prob = p + RepLenCoder;
437 }
438 {
439 int numBits, offset;
440 CProb *probLen = prob + LenChoice;
441 IfBit0(probLen)
442 {
443 UpdateBit0(probLen);
444 probLen = prob + LenLow + (posState << kLenNumLowBits);
445 offset = 0;
446 numBits = kLenNumLowBits;
447 }
448 else
449 {
450 UpdateBit1(probLen);
451 probLen = prob + LenChoice2;
452 IfBit0(probLen)
453 {
454 UpdateBit0(probLen);
455 probLen = prob + LenMid + (posState << kLenNumMidBits);
456 offset = kLenNumLowSymbols;
457 numBits = kLenNumMidBits;
458 }
459 else
460 {
461 UpdateBit1(probLen);
462 probLen = prob + LenHigh;
463 offset = kLenNumLowSymbols + kLenNumMidSymbols;
464 numBits = kLenNumHighBits;
465 }
466 }
467 RangeDecoderBitTreeDecode(probLen, numBits, len);
468 len += offset;
469 }
470
471 if (state < 4)
472 {
473 int posSlot;
474 state += kNumLitStates;
475 prob = p + PosSlot +
476 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
477 kNumPosSlotBits);
478 RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
479 if (posSlot >= kStartPosModelIndex)
480 {
481 int numDirectBits = ((posSlot >> 1) - 1);
482 rep0 = (2 | ((UInt32)posSlot & 1));
483 if (posSlot < kEndPosModelIndex)
484 {
485 rep0 <<= numDirectBits;
486 prob = p + SpecPos + rep0 - posSlot - 1;
487 }
488 else
489 {
490 numDirectBits -= kNumAlignBits;
491 do
492 {
493 RC_NORMALIZE
494 Range >>= 1;
495 rep0 <<= 1;
496 if (Code >= Range)
497 {
498 Code -= Range;
499 rep0 |= 1;
500 }
501 }
502 while (--numDirectBits != 0);
503 prob = p + Align;
504 rep0 <<= kNumAlignBits;
505 numDirectBits = kNumAlignBits;
506 }
507 {
508 int i = 1;
509 int mi = 1;
510 do
511 {
512 CProb *prob3 = prob + mi;
513 RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
514 i <<= 1;
515 }
516 while(--numDirectBits != 0);
517 }
518 }
519 else
520 rep0 = posSlot;
521 if (++rep0 == (UInt32)(0))
522 {
523 /* it's for stream version */
524 len = kLzmaStreamWasFinishedId;
525 break;
526 }
527 }
528
529 len += kMatchMinLen;
530 #ifdef _LZMA_OUT_READ
531 if (rep0 > distanceLimit)
532 #else
533 if (rep0 > nowPos)
534 #endif
535 return LZMA_RESULT_DATA_ERROR;
536
537 #ifdef _LZMA_OUT_READ
538 if (dictionarySize - distanceLimit > (UInt32)len)
539 distanceLimit += len;
540 else
541 distanceLimit = dictionarySize;
542 #endif
543
544 do
545 {
546 #ifdef _LZMA_OUT_READ
547 UInt32 pos = dictionaryPos - rep0;
548 if (pos >= dictionarySize)
549 pos += dictionarySize;
550 previousByte = dictionary[pos];
551 dictionary[dictionaryPos] = previousByte;
552 if (++dictionaryPos == dictionarySize)
553 dictionaryPos = 0;
554 #else
555 previousByte = outStream[nowPos - rep0];
556 #endif
557 len--;
558 outStream[nowPos++] = previousByte;
559 }
560 while(len != 0 && nowPos < outSize);
561 }
562 }
563 RC_NORMALIZE;
564
565 #ifdef _LZMA_OUT_READ
566 vs->Range = Range;
567 vs->Code = Code;
568 vs->DictionaryPos = dictionaryPos;
569 vs->GlobalPos = globalPos + (UInt32)nowPos;
570 vs->DistanceLimit = distanceLimit;
571 vs->Reps[0] = rep0;
572 vs->Reps[1] = rep1;
573 vs->Reps[2] = rep2;
574 vs->Reps[3] = rep3;
575 vs->State = state;
576 vs->RemainLen = len;
577 vs->TempDictionary[0] = tempDictionary[0];
578 #endif
579
580 #ifdef _LZMA_IN_CB
581 vs->Buffer = Buffer;
582 vs->BufferLim = BufferLim;
583 #else
584 *inSizeProcessed = (SizeT)(Buffer - inStream);
585 #endif
586 *outSizeProcessed = nowPos;
587 return LZMA_RESULT_OK;
588 }
589