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