OLD | NEW |
| (Empty) |
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)) >> kNumMove
Bits; | |
40 #define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveB
its; | |
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_NORMA
LIZE) | |
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 *propsDa
ta, 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 //BEGIN_GOOGLE_ADDITION(jeanluc) | |
175 int usesInternalTempDictionary = (dictionarySize == 0); | |
176 //END_GOOGLE_ADDITION(jeanluc) | |
177 | |
178 (*inSizeProcessed) = 0; | |
179 (*outSizeProcessed) = 0; | |
180 if (len == kLzmaStreamWasFinishedId) | |
181 return LZMA_RESULT_OK; | |
182 | |
183 if (dictionarySize == 0) | |
184 { | |
185 dictionary = tempDictionary; | |
186 dictionarySize = 1; | |
187 tempDictionary[0] = vs->TempDictionary[0]; | |
188 } | |
189 | |
190 if (len == kLzmaNeedInitId) | |
191 { | |
192 while (inSize > 0 && BufferSize < kLzmaInBufferSize) | |
193 { | |
194 Buffer[BufferSize++] = *inStream++; | |
195 (*inSizeProcessed)++; | |
196 inSize--; | |
197 } | |
198 if (BufferSize < 5) | |
199 { | |
200 vs->BufferSize = BufferSize; | |
201 return finishDecoding ? LZMA_RESULT_DATA_ERROR : LZMA_RESULT_OK; | |
202 } | |
203 { | |
204 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties
.lp)); | |
205 UInt32 i; | |
206 for (i = 0; i < numProbs; i++) | |
207 p[i] = kBitModelTotal >> 1; | |
208 rep0 = rep1 = rep2 = rep3 = 1; | |
209 state = 0; | |
210 globalPos = 0; | |
211 distanceLimit = 0; | |
212 dictionaryPos = 0; | |
213 dictionary[dictionarySize - 1] = 0; | |
214 RC_INIT; | |
215 } | |
216 len = 0; | |
217 } | |
218 while(len != 0 && nowPos < outSize) | |
219 { | |
220 UInt32 pos = dictionaryPos - rep0; | |
221 if (pos >= dictionarySize) | |
222 pos += dictionarySize; | |
223 outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos]; | |
224 if (++dictionaryPos == dictionarySize) | |
225 dictionaryPos = 0; | |
226 len--; | |
227 } | |
228 if (dictionaryPos == 0) | |
229 previousByte = dictionary[dictionarySize - 1]; | |
230 else | |
231 previousByte = dictionary[dictionaryPos - 1]; | |
232 | |
233 while(1) | |
234 { | |
235 int bufferPos = (int)(Buffer - vs->Buffer); | |
236 if (BufferSize - bufferPos < kRequiredInBufferSize) | |
237 { | |
238 int i; | |
239 BufferSize -= bufferPos; | |
240 if (BufferSize < 0) | |
241 return LZMA_RESULT_DATA_ERROR; | |
242 for (i = 0; i < BufferSize; i++) | |
243 vs->Buffer[i] = Buffer[i]; | |
244 Buffer = vs->Buffer; | |
245 while (inSize > 0 && BufferSize < kLzmaInBufferSize) | |
246 { | |
247 Buffer[BufferSize++] = *inStream++; | |
248 (*inSizeProcessed)++; | |
249 inSize--; | |
250 } | |
251 if (BufferSize < kRequiredInBufferSize && !finishDecoding) | |
252 break; | |
253 } | |
254 if (nowPos >= outSize) | |
255 break; | |
256 { | |
257 CProb *prob; | |
258 UInt32 bound; | |
259 int posState = (int)((nowPos + globalPos) & posStateMask); | |
260 | |
261 prob = p + IsMatch + (state << kNumPosBitsMax) + posState; | |
262 IfBit0(prob) | |
263 { | |
264 int symbol = 1; | |
265 UpdateBit0(prob) | |
266 prob = p + Literal + (LZMA_LIT_SIZE * | |
267 ((((nowPos + globalPos)& literalPosMask) << lc) + (previousByte >> (8 -
lc)))); | |
268 | |
269 if (state >= kNumLitStates) | |
270 { | |
271 int matchByte; | |
272 UInt32 pos = dictionaryPos - rep0; | |
273 if (pos >= dictionarySize) | |
274 pos += dictionarySize; | |
275 matchByte = dictionary[pos]; | |
276 do | |
277 { | |
278 int bit; | |
279 CProb *probLit; | |
280 matchByte <<= 1; | |
281 bit = (matchByte & 0x100); | |
282 probLit = prob + 0x100 + bit + symbol; | |
283 RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break) | |
284 } | |
285 while (symbol < 0x100); | |
286 } | |
287 while (symbol < 0x100) | |
288 { | |
289 CProb *probLit = prob + symbol; | |
290 RC_GET_BIT(probLit, symbol) | |
291 } | |
292 previousByte = (unsigned char)symbol; | |
293 | |
294 outStream[nowPos++] = previousByte; | |
295 if (distanceLimit < dictionarySize) | |
296 distanceLimit++; | |
297 | |
298 dictionary[dictionaryPos] = previousByte; | |
299 if (++dictionaryPos == dictionarySize) | |
300 dictionaryPos = 0; | |
301 if (state < 4) state = 0; | |
302 else if (state < 10) state -= 3; | |
303 else state -= 6; | |
304 } | |
305 else | |
306 { | |
307 UpdateBit1(prob); | |
308 prob = p + IsRep + state; | |
309 IfBit0(prob) | |
310 { | |
311 UpdateBit0(prob); | |
312 rep3 = rep2; | |
313 rep2 = rep1; | |
314 rep1 = rep0; | |
315 state = state < kNumLitStates ? 0 : 3; | |
316 prob = p + LenCoder; | |
317 } | |
318 else | |
319 { | |
320 UpdateBit1(prob); | |
321 prob = p + IsRepG0 + state; | |
322 IfBit0(prob) | |
323 { | |
324 UpdateBit0(prob); | |
325 prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState; | |
326 IfBit0(prob) | |
327 { | |
328 UInt32 pos; | |
329 UpdateBit0(prob); | |
330 if (distanceLimit == 0) | |
331 return LZMA_RESULT_DATA_ERROR; | |
332 if (distanceLimit < dictionarySize) | |
333 distanceLimit++; | |
334 state = state < kNumLitStates ? 9 : 11; | |
335 pos = dictionaryPos - rep0; | |
336 if (pos >= dictionarySize) | |
337 pos += dictionarySize; | |
338 previousByte = dictionary[pos]; | |
339 dictionary[dictionaryPos] = previousByte; | |
340 if (++dictionaryPos == dictionarySize) | |
341 dictionaryPos = 0; | |
342 outStream[nowPos++] = previousByte; | |
343 continue; | |
344 } | |
345 else | |
346 { | |
347 UpdateBit1(prob); | |
348 } | |
349 } | |
350 else | |
351 { | |
352 UInt32 distance; | |
353 UpdateBit1(prob); | |
354 prob = p + IsRepG1 + state; | |
355 IfBit0(prob) | |
356 { | |
357 UpdateBit0(prob); | |
358 distance = rep1; | |
359 } | |
360 else | |
361 { | |
362 UpdateBit1(prob); | |
363 prob = p + IsRepG2 + state; | |
364 IfBit0(prob) | |
365 { | |
366 UpdateBit0(prob); | |
367 distance = rep2; | |
368 } | |
369 else | |
370 { | |
371 UpdateBit1(prob); | |
372 distance = rep3; | |
373 rep3 = rep2; | |
374 } | |
375 rep2 = rep1; | |
376 } | |
377 rep1 = rep0; | |
378 rep0 = distance; | |
379 } | |
380 state = state < kNumLitStates ? 8 : 11; | |
381 prob = p + RepLenCoder; | |
382 } | |
383 { | |
384 int numBits, offset; | |
385 CProb *probLen = prob + LenChoice; | |
386 IfBit0(probLen) | |
387 { | |
388 UpdateBit0(probLen); | |
389 probLen = prob + LenLow + (posState << kLenNumLowBits); | |
390 offset = 0; | |
391 numBits = kLenNumLowBits; | |
392 } | |
393 else | |
394 { | |
395 UpdateBit1(probLen); | |
396 probLen = prob + LenChoice2; | |
397 IfBit0(probLen) | |
398 { | |
399 UpdateBit0(probLen); | |
400 probLen = prob + LenMid + (posState << kLenNumMidBits); | |
401 offset = kLenNumLowSymbols; | |
402 numBits = kLenNumMidBits; | |
403 } | |
404 else | |
405 { | |
406 UpdateBit1(probLen); | |
407 probLen = prob + LenHigh; | |
408 offset = kLenNumLowSymbols + kLenNumMidSymbols; | |
409 numBits = kLenNumHighBits; | |
410 } | |
411 } | |
412 RangeDecoderBitTreeDecode(probLen, numBits, len); | |
413 len += offset; | |
414 } | |
415 | |
416 if (state < 4) | |
417 { | |
418 int posSlot; | |
419 state += kNumLitStates; | |
420 prob = p + PosSlot + | |
421 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << | |
422 kNumPosSlotBits); | |
423 RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot); | |
424 if (posSlot >= kStartPosModelIndex) | |
425 { | |
426 int numDirectBits = ((posSlot >> 1) - 1); | |
427 rep0 = (2 | ((UInt32)posSlot & 1)); | |
428 if (posSlot < kEndPosModelIndex) | |
429 { | |
430 rep0 <<= numDirectBits; | |
431 prob = p + SpecPos + rep0 - posSlot - 1; | |
432 } | |
433 else | |
434 { | |
435 numDirectBits -= kNumAlignBits; | |
436 do | |
437 { | |
438 RC_NORMALIZE | |
439 Range >>= 1; | |
440 rep0 <<= 1; | |
441 if (Code >= Range) | |
442 { | |
443 Code -= Range; | |
444 rep0 |= 1; | |
445 } | |
446 } | |
447 while (--numDirectBits != 0); | |
448 prob = p + Align; | |
449 rep0 <<= kNumAlignBits; | |
450 numDirectBits = kNumAlignBits; | |
451 } | |
452 { | |
453 int i = 1; | |
454 int mi = 1; | |
455 do | |
456 { | |
457 CProb *prob3 = prob + mi; | |
458 RC_GET_BIT2(prob3, mi, ; , rep0 |= i); | |
459 i <<= 1; | |
460 } | |
461 while(--numDirectBits != 0); | |
462 } | |
463 } | |
464 else | |
465 rep0 = posSlot; | |
466 if (++rep0 == (UInt32)(0)) | |
467 { | |
468 /* it's for stream version */ | |
469 len = kLzmaStreamWasFinishedId; | |
470 break; | |
471 } | |
472 } | |
473 | |
474 len += kMatchMinLen; | |
475 if (rep0 > distanceLimit) | |
476 return LZMA_RESULT_DATA_ERROR; | |
477 if (dictionarySize - distanceLimit > (UInt32)len) | |
478 distanceLimit += len; | |
479 else | |
480 distanceLimit = dictionarySize; | |
481 | |
482 do | |
483 { | |
484 UInt32 pos = dictionaryPos - rep0; | |
485 if (pos >= dictionarySize) | |
486 pos += dictionarySize; | |
487 previousByte = dictionary[pos]; | |
488 dictionary[dictionaryPos] = previousByte; | |
489 if (++dictionaryPos == dictionarySize) | |
490 dictionaryPos = 0; | |
491 len--; | |
492 outStream[nowPos++] = previousByte; | |
493 } | |
494 while(len != 0 && nowPos < outSize); | |
495 } | |
496 } | |
497 } | |
498 RC_NORMALIZE; | |
499 | |
500 BufferSize -= (int)(Buffer - vs->Buffer); | |
501 if (BufferSize < 0) | |
502 return LZMA_RESULT_DATA_ERROR; | |
503 { | |
504 int i; | |
505 for (i = 0; i < BufferSize; i++) | |
506 vs->Buffer[i] = Buffer[i]; | |
507 } | |
508 vs->BufferSize = BufferSize; | |
509 vs->Range = Range; | |
510 vs->Code = Code; | |
511 vs->DictionaryPos = dictionaryPos; | |
512 vs->GlobalPos = (UInt32)(globalPos + nowPos); | |
513 vs->DistanceLimit = distanceLimit; | |
514 vs->Reps[0] = rep0; | |
515 vs->Reps[1] = rep1; | |
516 vs->Reps[2] = rep2; | |
517 vs->Reps[3] = rep3; | |
518 vs->State = state; | |
519 vs->RemainLen = len; | |
520 //BEGIN_GOOGLE_ADDITION(jeanluc) | |
521 if (usesInternalTempDictionary) | |
522 //END_GOOGLE_ADDITION(jeanluc) | |
523 vs->TempDictionary[0] = tempDictionary[0]; | |
524 | |
525 (*outSizeProcessed) = nowPos; | |
526 return LZMA_RESULT_OK; | |
527 } | |
OLD | NEW |