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