diff options
Diffstat (limited to 'libraries/irrlicht-1.8.1/source/Irrlicht/lzma/LzmaDec.c')
-rw-r--r-- | libraries/irrlicht-1.8.1/source/Irrlicht/lzma/LzmaDec.c | 999 |
1 files changed, 999 insertions, 0 deletions
diff --git a/libraries/irrlicht-1.8.1/source/Irrlicht/lzma/LzmaDec.c b/libraries/irrlicht-1.8.1/source/Irrlicht/lzma/LzmaDec.c new file mode 100644 index 0000000..4fdc11d --- /dev/null +++ b/libraries/irrlicht-1.8.1/source/Irrlicht/lzma/LzmaDec.c | |||
@@ -0,0 +1,999 @@ | |||
1 | /* LzmaDec.c -- LZMA Decoder | ||
2 | 2009-09-20 : Igor Pavlov : Public domain */ | ||
3 | |||
4 | #include "LzmaDec.h" | ||
5 | |||
6 | #include <string.h> | ||
7 | |||
8 | #define kNumTopBits 24 | ||
9 | #define kTopValue ((UInt32)1 << kNumTopBits) | ||
10 | |||
11 | #define kNumBitModelTotalBits 11 | ||
12 | #define kBitModelTotal (1 << kNumBitModelTotalBits) | ||
13 | #define kNumMoveBits 5 | ||
14 | |||
15 | #define RC_INIT_SIZE 5 | ||
16 | |||
17 | #define NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | (*buf++); } | ||
18 | |||
19 | #define IF_BIT_0(p) ttt = *(p); NORMALIZE; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound) | ||
20 | #define UPDATE_0(p) range = bound; *(p) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits)); | ||
21 | #define UPDATE_1(p) range -= bound; code -= bound; *(p) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits)); | ||
22 | #define GET_BIT2(p, i, A0, A1) IF_BIT_0(p) \ | ||
23 | { UPDATE_0(p); i = (i + i); A0; } else \ | ||
24 | { UPDATE_1(p); i = (i + i) + 1; A1; } | ||
25 | #define GET_BIT(p, i) GET_BIT2(p, i, ; , ;) | ||
26 | |||
27 | #define TREE_GET_BIT(probs, i) { GET_BIT((probs + i), i); } | ||
28 | #define TREE_DECODE(probs, limit, i) \ | ||
29 | { i = 1; do { TREE_GET_BIT(probs, i); } while (i < limit); i -= limit; } | ||
30 | |||
31 | /* #define _LZMA_SIZE_OPT */ | ||
32 | |||
33 | #ifdef _LZMA_SIZE_OPT | ||
34 | #define TREE_6_DECODE(probs, i) TREE_DECODE(probs, (1 << 6), i) | ||
35 | #else | ||
36 | #define TREE_6_DECODE(probs, i) \ | ||
37 | { i = 1; \ | ||
38 | TREE_GET_BIT(probs, i); \ | ||
39 | TREE_GET_BIT(probs, i); \ | ||
40 | TREE_GET_BIT(probs, i); \ | ||
41 | TREE_GET_BIT(probs, i); \ | ||
42 | TREE_GET_BIT(probs, i); \ | ||
43 | TREE_GET_BIT(probs, i); \ | ||
44 | i -= 0x40; } | ||
45 | #endif | ||
46 | |||
47 | #define NORMALIZE_CHECK if (range < kTopValue) { if (buf >= bufLimit) return DUMMY_ERROR; range <<= 8; code = (code << 8) | (*buf++); } | ||
48 | |||
49 | #define IF_BIT_0_CHECK(p) ttt = *(p); NORMALIZE_CHECK; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound) | ||
50 | #define UPDATE_0_CHECK range = bound; | ||
51 | #define UPDATE_1_CHECK range -= bound; code -= bound; | ||
52 | #define GET_BIT2_CHECK(p, i, A0, A1) IF_BIT_0_CHECK(p) \ | ||
53 | { UPDATE_0_CHECK; i = (i + i); A0; } else \ | ||
54 | { UPDATE_1_CHECK; i = (i + i) + 1; A1; } | ||
55 | #define GET_BIT_CHECK(p, i) GET_BIT2_CHECK(p, i, ; , ;) | ||
56 | #define TREE_DECODE_CHECK(probs, limit, i) \ | ||
57 | { i = 1; do { GET_BIT_CHECK(probs + i, i) } while (i < limit); i -= limit; } | ||
58 | |||
59 | |||
60 | #define kNumPosBitsMax 4 | ||
61 | #define kNumPosStatesMax (1 << kNumPosBitsMax) | ||
62 | |||
63 | #define kLenNumLowBits 3 | ||
64 | #define kLenNumLowSymbols (1 << kLenNumLowBits) | ||
65 | #define kLenNumMidBits 3 | ||
66 | #define kLenNumMidSymbols (1 << kLenNumMidBits) | ||
67 | #define kLenNumHighBits 8 | ||
68 | #define kLenNumHighSymbols (1 << kLenNumHighBits) | ||
69 | |||
70 | #define LenChoice 0 | ||
71 | #define LenChoice2 (LenChoice + 1) | ||
72 | #define LenLow (LenChoice2 + 1) | ||
73 | #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits)) | ||
74 | #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits)) | ||
75 | #define kNumLenProbs (LenHigh + kLenNumHighSymbols) | ||
76 | |||
77 | |||
78 | #define kNumStates 12 | ||
79 | #define kNumLitStates 7 | ||
80 | |||
81 | #define kStartPosModelIndex 4 | ||
82 | #define kEndPosModelIndex 14 | ||
83 | #define kNumFullDistances (1 << (kEndPosModelIndex >> 1)) | ||
84 | |||
85 | #define kNumPosSlotBits 6 | ||
86 | #define kNumLenToPosStates 4 | ||
87 | |||
88 | #define kNumAlignBits 4 | ||
89 | #define kAlignTableSize (1 << kNumAlignBits) | ||
90 | |||
91 | #define kMatchMinLen 2 | ||
92 | #define kMatchSpecLenStart (kMatchMinLen + kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols) | ||
93 | |||
94 | #define IsMatch 0 | ||
95 | #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax)) | ||
96 | #define IsRepG0 (IsRep + kNumStates) | ||
97 | #define IsRepG1 (IsRepG0 + kNumStates) | ||
98 | #define IsRepG2 (IsRepG1 + kNumStates) | ||
99 | #define IsRep0Long (IsRepG2 + kNumStates) | ||
100 | #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax)) | ||
101 | #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits)) | ||
102 | #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex) | ||
103 | #define LenCoder (Align + kAlignTableSize) | ||
104 | #define RepLenCoder (LenCoder + kNumLenProbs) | ||
105 | #define Literal (RepLenCoder + kNumLenProbs) | ||
106 | |||
107 | #define LZMA_BASE_SIZE 1846 | ||
108 | #define LZMA_LIT_SIZE 768 | ||
109 | |||
110 | #define LzmaProps_GetNumProbs(p) ((UInt32)LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((p)->lc + (p)->lp))) | ||
111 | |||
112 | #if Literal != LZMA_BASE_SIZE | ||
113 | StopCompilingDueBUG | ||
114 | #endif | ||
115 | |||
116 | #define LZMA_DIC_MIN (1 << 12) | ||
117 | |||
118 | /* First LZMA-symbol is always decoded. | ||
119 | And it decodes new LZMA-symbols while (buf < bufLimit), but "buf" is without last normalization | ||
120 | Out: | ||
121 | Result: | ||
122 | SZ_OK - OK | ||
123 | SZ_ERROR_DATA - Error | ||
124 | p->remainLen: | ||
125 | < kMatchSpecLenStart : normal remain | ||
126 | = kMatchSpecLenStart : finished | ||
127 | = kMatchSpecLenStart + 1 : Flush marker | ||
128 | = kMatchSpecLenStart + 2 : State Init Marker | ||
129 | */ | ||
130 | |||
131 | static int MY_FAST_CALL LzmaDec_DecodeReal(CLzmaDec *p, SizeT limit, const Byte *bufLimit) | ||
132 | { | ||
133 | CLzmaProb *probs = p->probs; | ||
134 | |||
135 | unsigned state = p->state; | ||
136 | UInt32 rep0 = p->reps[0], rep1 = p->reps[1], rep2 = p->reps[2], rep3 = p->reps[3]; | ||
137 | unsigned pbMask = ((unsigned)1 << (p->prop.pb)) - 1; | ||
138 | unsigned lpMask = ((unsigned)1 << (p->prop.lp)) - 1; | ||
139 | unsigned lc = p->prop.lc; | ||
140 | |||
141 | Byte *dic = p->dic; | ||
142 | SizeT dicBufSize = p->dicBufSize; | ||
143 | SizeT dicPos = p->dicPos; | ||
144 | |||
145 | UInt32 processedPos = p->processedPos; | ||
146 | UInt32 checkDicSize = p->checkDicSize; | ||
147 | unsigned len = 0; | ||
148 | |||
149 | const Byte *buf = p->buf; | ||
150 | UInt32 range = p->range; | ||
151 | UInt32 code = p->code; | ||
152 | |||
153 | do | ||
154 | { | ||
155 | CLzmaProb *prob; | ||
156 | UInt32 bound; | ||
157 | unsigned ttt; | ||
158 | unsigned posState = processedPos & pbMask; | ||
159 | |||
160 | prob = probs + IsMatch + (state << kNumPosBitsMax) + posState; | ||
161 | IF_BIT_0(prob) | ||
162 | { | ||
163 | unsigned symbol; | ||
164 | UPDATE_0(prob); | ||
165 | prob = probs + Literal; | ||
166 | if (checkDicSize != 0 || processedPos != 0) | ||
167 | prob += (LZMA_LIT_SIZE * (((processedPos & lpMask) << lc) + | ||
168 | (dic[(dicPos == 0 ? dicBufSize : dicPos) - 1] >> (8 - lc)))); | ||
169 | |||
170 | if (state < kNumLitStates) | ||
171 | { | ||
172 | state -= (state < 4) ? state : 3; | ||
173 | symbol = 1; | ||
174 | do { GET_BIT(prob + symbol, symbol) } while (symbol < 0x100); | ||
175 | } | ||
176 | else | ||
177 | { | ||
178 | unsigned matchByte = p->dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)]; | ||
179 | unsigned offs = 0x100; | ||
180 | state -= (state < 10) ? 3 : 6; | ||
181 | symbol = 1; | ||
182 | do | ||
183 | { | ||
184 | unsigned bit; | ||
185 | CLzmaProb *probLit; | ||
186 | matchByte <<= 1; | ||
187 | bit = (matchByte & offs); | ||
188 | probLit = prob + offs + bit + symbol; | ||
189 | GET_BIT2(probLit, symbol, offs &= ~bit, offs &= bit) | ||
190 | } | ||
191 | while (symbol < 0x100); | ||
192 | } | ||
193 | dic[dicPos++] = (Byte)symbol; | ||
194 | processedPos++; | ||
195 | continue; | ||
196 | } | ||
197 | else | ||
198 | { | ||
199 | UPDATE_1(prob); | ||
200 | prob = probs + IsRep + state; | ||
201 | IF_BIT_0(prob) | ||
202 | { | ||
203 | UPDATE_0(prob); | ||
204 | state += kNumStates; | ||
205 | prob = probs + LenCoder; | ||
206 | } | ||
207 | else | ||
208 | { | ||
209 | UPDATE_1(prob); | ||
210 | if (checkDicSize == 0 && processedPos == 0) | ||
211 | return SZ_ERROR_DATA; | ||
212 | prob = probs + IsRepG0 + state; | ||
213 | IF_BIT_0(prob) | ||
214 | { | ||
215 | UPDATE_0(prob); | ||
216 | prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState; | ||
217 | IF_BIT_0(prob) | ||
218 | { | ||
219 | UPDATE_0(prob); | ||
220 | dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)]; | ||
221 | dicPos++; | ||
222 | processedPos++; | ||
223 | state = state < kNumLitStates ? 9 : 11; | ||
224 | continue; | ||
225 | } | ||
226 | UPDATE_1(prob); | ||
227 | } | ||
228 | else | ||
229 | { | ||
230 | UInt32 distance; | ||
231 | UPDATE_1(prob); | ||
232 | prob = probs + IsRepG1 + state; | ||
233 | IF_BIT_0(prob) | ||
234 | { | ||
235 | UPDATE_0(prob); | ||
236 | distance = rep1; | ||
237 | } | ||
238 | else | ||
239 | { | ||
240 | UPDATE_1(prob); | ||
241 | prob = probs + IsRepG2 + state; | ||
242 | IF_BIT_0(prob) | ||
243 | { | ||
244 | UPDATE_0(prob); | ||
245 | distance = rep2; | ||
246 | } | ||
247 | else | ||
248 | { | ||
249 | UPDATE_1(prob); | ||
250 | distance = rep3; | ||
251 | rep3 = rep2; | ||
252 | } | ||
253 | rep2 = rep1; | ||
254 | } | ||
255 | rep1 = rep0; | ||
256 | rep0 = distance; | ||
257 | } | ||
258 | state = state < kNumLitStates ? 8 : 11; | ||
259 | prob = probs + RepLenCoder; | ||
260 | } | ||
261 | { | ||
262 | unsigned limit, offset; | ||
263 | CLzmaProb *probLen = prob + LenChoice; | ||
264 | IF_BIT_0(probLen) | ||
265 | { | ||
266 | UPDATE_0(probLen); | ||
267 | probLen = prob + LenLow + (posState << kLenNumLowBits); | ||
268 | offset = 0; | ||
269 | limit = (1 << kLenNumLowBits); | ||
270 | } | ||
271 | else | ||
272 | { | ||
273 | UPDATE_1(probLen); | ||
274 | probLen = prob + LenChoice2; | ||
275 | IF_BIT_0(probLen) | ||
276 | { | ||
277 | UPDATE_0(probLen); | ||
278 | probLen = prob + LenMid + (posState << kLenNumMidBits); | ||
279 | offset = kLenNumLowSymbols; | ||
280 | limit = (1 << kLenNumMidBits); | ||
281 | } | ||
282 | else | ||
283 | { | ||
284 | UPDATE_1(probLen); | ||
285 | probLen = prob + LenHigh; | ||
286 | offset = kLenNumLowSymbols + kLenNumMidSymbols; | ||
287 | limit = (1 << kLenNumHighBits); | ||
288 | } | ||
289 | } | ||
290 | TREE_DECODE(probLen, limit, len); | ||
291 | len += offset; | ||
292 | } | ||
293 | |||
294 | if (state >= kNumStates) | ||
295 | { | ||
296 | UInt32 distance; | ||
297 | prob = probs + PosSlot + | ||
298 | ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits); | ||
299 | TREE_6_DECODE(prob, distance); | ||
300 | if (distance >= kStartPosModelIndex) | ||
301 | { | ||
302 | unsigned posSlot = (unsigned)distance; | ||
303 | int numDirectBits = (int)(((distance >> 1) - 1)); | ||
304 | distance = (2 | (distance & 1)); | ||
305 | if (posSlot < kEndPosModelIndex) | ||
306 | { | ||
307 | distance <<= numDirectBits; | ||
308 | prob = probs + SpecPos + distance - posSlot - 1; | ||
309 | { | ||
310 | UInt32 mask = 1; | ||
311 | unsigned i = 1; | ||
312 | do | ||
313 | { | ||
314 | GET_BIT2(prob + i, i, ; , distance |= mask); | ||
315 | mask <<= 1; | ||
316 | } | ||
317 | while (--numDirectBits != 0); | ||
318 | } | ||
319 | } | ||
320 | else | ||
321 | { | ||
322 | numDirectBits -= kNumAlignBits; | ||
323 | do | ||
324 | { | ||
325 | NORMALIZE | ||
326 | range >>= 1; | ||
327 | |||
328 | { | ||
329 | UInt32 t; | ||
330 | code -= range; | ||
331 | t = (0 - ((UInt32)code >> 31)); /* (UInt32)((Int32)code >> 31) */ | ||
332 | distance = (distance << 1) + (t + 1); | ||
333 | code += range & t; | ||
334 | } | ||
335 | /* | ||
336 | distance <<= 1; | ||
337 | if (code >= range) | ||
338 | { | ||
339 | code -= range; | ||
340 | distance |= 1; | ||
341 | } | ||
342 | */ | ||
343 | } | ||
344 | while (--numDirectBits != 0); | ||
345 | prob = probs + Align; | ||
346 | distance <<= kNumAlignBits; | ||
347 | { | ||
348 | unsigned i = 1; | ||
349 | GET_BIT2(prob + i, i, ; , distance |= 1); | ||
350 | GET_BIT2(prob + i, i, ; , distance |= 2); | ||
351 | GET_BIT2(prob + i, i, ; , distance |= 4); | ||
352 | GET_BIT2(prob + i, i, ; , distance |= 8); | ||
353 | } | ||
354 | if (distance == (UInt32)0xFFFFFFFF) | ||
355 | { | ||
356 | len += kMatchSpecLenStart; | ||
357 | state -= kNumStates; | ||
358 | break; | ||
359 | } | ||
360 | } | ||
361 | } | ||
362 | rep3 = rep2; | ||
363 | rep2 = rep1; | ||
364 | rep1 = rep0; | ||
365 | rep0 = distance + 1; | ||
366 | if (checkDicSize == 0) | ||
367 | { | ||
368 | if (distance >= processedPos) | ||
369 | return SZ_ERROR_DATA; | ||
370 | } | ||
371 | else if (distance >= checkDicSize) | ||
372 | return SZ_ERROR_DATA; | ||
373 | state = (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3; | ||
374 | } | ||
375 | |||
376 | len += kMatchMinLen; | ||
377 | |||
378 | if (limit == dicPos) | ||
379 | return SZ_ERROR_DATA; | ||
380 | { | ||
381 | SizeT rem = limit - dicPos; | ||
382 | unsigned curLen = ((rem < len) ? (unsigned)rem : len); | ||
383 | SizeT pos = (dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0); | ||
384 | |||
385 | processedPos += curLen; | ||
386 | |||
387 | len -= curLen; | ||
388 | if (pos + curLen <= dicBufSize) | ||
389 | { | ||
390 | Byte *dest = dic + dicPos; | ||
391 | ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos; | ||
392 | const Byte *lim = dest + curLen; | ||
393 | dicPos += curLen; | ||
394 | do | ||
395 | *(dest) = (Byte)*(dest + src); | ||
396 | while (++dest != lim); | ||
397 | } | ||
398 | else | ||
399 | { | ||
400 | do | ||
401 | { | ||
402 | dic[dicPos++] = dic[pos]; | ||
403 | if (++pos == dicBufSize) | ||
404 | pos = 0; | ||
405 | } | ||
406 | while (--curLen != 0); | ||
407 | } | ||
408 | } | ||
409 | } | ||
410 | } | ||
411 | while (dicPos < limit && buf < bufLimit); | ||
412 | NORMALIZE; | ||
413 | p->buf = buf; | ||
414 | p->range = range; | ||
415 | p->code = code; | ||
416 | p->remainLen = len; | ||
417 | p->dicPos = dicPos; | ||
418 | p->processedPos = processedPos; | ||
419 | p->reps[0] = rep0; | ||
420 | p->reps[1] = rep1; | ||
421 | p->reps[2] = rep2; | ||
422 | p->reps[3] = rep3; | ||
423 | p->state = state; | ||
424 | |||
425 | return SZ_OK; | ||
426 | } | ||
427 | |||
428 | static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, SizeT limit) | ||
429 | { | ||
430 | if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart) | ||
431 | { | ||
432 | Byte *dic = p->dic; | ||
433 | SizeT dicPos = p->dicPos; | ||
434 | SizeT dicBufSize = p->dicBufSize; | ||
435 | unsigned len = p->remainLen; | ||
436 | UInt32 rep0 = p->reps[0]; | ||
437 | if (limit - dicPos < len) | ||
438 | len = (unsigned)(limit - dicPos); | ||
439 | |||
440 | if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len) | ||
441 | p->checkDicSize = p->prop.dicSize; | ||
442 | |||
443 | p->processedPos += len; | ||
444 | p->remainLen -= len; | ||
445 | while (len-- != 0) | ||
446 | { | ||
447 | dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)]; | ||
448 | dicPos++; | ||
449 | } | ||
450 | p->dicPos = dicPos; | ||
451 | } | ||
452 | } | ||
453 | |||
454 | static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, SizeT limit, const Byte *bufLimit) | ||
455 | { | ||
456 | do | ||
457 | { | ||
458 | SizeT limit2 = limit; | ||
459 | if (p->checkDicSize == 0) | ||
460 | { | ||
461 | UInt32 rem = p->prop.dicSize - p->processedPos; | ||
462 | if (limit - p->dicPos > rem) | ||
463 | limit2 = p->dicPos + rem; | ||
464 | } | ||
465 | RINOK(LzmaDec_DecodeReal(p, limit2, bufLimit)); | ||
466 | if (p->processedPos >= p->prop.dicSize) | ||
467 | p->checkDicSize = p->prop.dicSize; | ||
468 | LzmaDec_WriteRem(p, limit); | ||
469 | } | ||
470 | while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart); | ||
471 | |||
472 | if (p->remainLen > kMatchSpecLenStart) | ||
473 | { | ||
474 | p->remainLen = kMatchSpecLenStart; | ||
475 | } | ||
476 | return 0; | ||
477 | } | ||
478 | |||
479 | typedef enum | ||
480 | { | ||
481 | DUMMY_ERROR, /* unexpected end of input stream */ | ||
482 | DUMMY_LIT, | ||
483 | DUMMY_MATCH, | ||
484 | DUMMY_REP | ||
485 | } ELzmaDummy; | ||
486 | |||
487 | static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const Byte *buf, SizeT inSize) | ||
488 | { | ||
489 | UInt32 range = p->range; | ||
490 | UInt32 code = p->code; | ||
491 | const Byte *bufLimit = buf + inSize; | ||
492 | CLzmaProb *probs = p->probs; | ||
493 | unsigned state = p->state; | ||
494 | ELzmaDummy res; | ||
495 | |||
496 | { | ||
497 | CLzmaProb *prob; | ||
498 | UInt32 bound; | ||
499 | unsigned ttt; | ||
500 | unsigned posState = (p->processedPos) & ((1 << p->prop.pb) - 1); | ||
501 | |||
502 | prob = probs + IsMatch + (state << kNumPosBitsMax) + posState; | ||
503 | IF_BIT_0_CHECK(prob) | ||
504 | { | ||
505 | UPDATE_0_CHECK | ||
506 | |||
507 | /* if (bufLimit - buf >= 7) return DUMMY_LIT; */ | ||
508 | |||
509 | prob = probs + Literal; | ||
510 | if (p->checkDicSize != 0 || p->processedPos != 0) | ||
511 | prob += (LZMA_LIT_SIZE * | ||
512 | ((((p->processedPos) & ((1 << (p->prop.lp)) - 1)) << p->prop.lc) + | ||
513 | (p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >> (8 - p->prop.lc)))); | ||
514 | |||
515 | if (state < kNumLitStates) | ||
516 | { | ||
517 | unsigned symbol = 1; | ||
518 | do { GET_BIT_CHECK(prob + symbol, symbol) } while (symbol < 0x100); | ||
519 | } | ||
520 | else | ||
521 | { | ||
522 | unsigned matchByte = p->dic[p->dicPos - p->reps[0] + | ||
523 | ((p->dicPos < p->reps[0]) ? p->dicBufSize : 0)]; | ||
524 | unsigned offs = 0x100; | ||
525 | unsigned symbol = 1; | ||
526 | do | ||
527 | { | ||
528 | unsigned bit; | ||
529 | CLzmaProb *probLit; | ||
530 | matchByte <<= 1; | ||
531 | bit = (matchByte & offs); | ||
532 | probLit = prob + offs + bit + symbol; | ||
533 | GET_BIT2_CHECK(probLit, symbol, offs &= ~bit, offs &= bit) | ||
534 | } | ||
535 | while (symbol < 0x100); | ||
536 | } | ||
537 | res = DUMMY_LIT; | ||
538 | } | ||
539 | else | ||
540 | { | ||
541 | unsigned len; | ||
542 | UPDATE_1_CHECK; | ||
543 | |||
544 | prob = probs + IsRep + state; | ||
545 | IF_BIT_0_CHECK(prob) | ||
546 | { | ||
547 | UPDATE_0_CHECK; | ||
548 | state = 0; | ||
549 | prob = probs + LenCoder; | ||
550 | res = DUMMY_MATCH; | ||
551 | } | ||
552 | else | ||
553 | { | ||
554 | UPDATE_1_CHECK; | ||
555 | res = DUMMY_REP; | ||
556 | prob = probs + IsRepG0 + state; | ||
557 | IF_BIT_0_CHECK(prob) | ||
558 | { | ||
559 | UPDATE_0_CHECK; | ||
560 | prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState; | ||
561 | IF_BIT_0_CHECK(prob) | ||
562 | { | ||
563 | UPDATE_0_CHECK; | ||
564 | NORMALIZE_CHECK; | ||
565 | return DUMMY_REP; | ||
566 | } | ||
567 | else | ||
568 | { | ||
569 | UPDATE_1_CHECK; | ||
570 | } | ||
571 | } | ||
572 | else | ||
573 | { | ||
574 | UPDATE_1_CHECK; | ||
575 | prob = probs + IsRepG1 + state; | ||
576 | IF_BIT_0_CHECK(prob) | ||
577 | { | ||
578 | UPDATE_0_CHECK; | ||
579 | } | ||
580 | else | ||
581 | { | ||
582 | UPDATE_1_CHECK; | ||
583 | prob = probs + IsRepG2 + state; | ||
584 | IF_BIT_0_CHECK(prob) | ||
585 | { | ||
586 | UPDATE_0_CHECK; | ||
587 | } | ||
588 | else | ||
589 | { | ||
590 | UPDATE_1_CHECK; | ||
591 | } | ||
592 | } | ||
593 | } | ||
594 | state = kNumStates; | ||
595 | prob = probs + RepLenCoder; | ||
596 | } | ||
597 | { | ||
598 | unsigned limit, offset; | ||
599 | CLzmaProb *probLen = prob + LenChoice; | ||
600 | IF_BIT_0_CHECK(probLen) | ||
601 | { | ||
602 | UPDATE_0_CHECK; | ||
603 | probLen = prob + LenLow + (posState << kLenNumLowBits); | ||
604 | offset = 0; | ||
605 | limit = 1 << kLenNumLowBits; | ||
606 | } | ||
607 | else | ||
608 | { | ||
609 | UPDATE_1_CHECK; | ||
610 | probLen = prob + LenChoice2; | ||
611 | IF_BIT_0_CHECK(probLen) | ||
612 | { | ||
613 | UPDATE_0_CHECK; | ||
614 | probLen = prob + LenMid + (posState << kLenNumMidBits); | ||
615 | offset = kLenNumLowSymbols; | ||
616 | limit = 1 << kLenNumMidBits; | ||
617 | } | ||
618 | else | ||
619 | { | ||
620 | UPDATE_1_CHECK; | ||
621 | probLen = prob + LenHigh; | ||
622 | offset = kLenNumLowSymbols + kLenNumMidSymbols; | ||
623 | limit = 1 << kLenNumHighBits; | ||
624 | } | ||
625 | } | ||
626 | TREE_DECODE_CHECK(probLen, limit, len); | ||
627 | len += offset; | ||
628 | } | ||
629 | |||
630 | if (state < 4) | ||
631 | { | ||
632 | unsigned posSlot; | ||
633 | prob = probs + PosSlot + | ||
634 | ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << | ||
635 | kNumPosSlotBits); | ||
636 | TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot); | ||
637 | if (posSlot >= kStartPosModelIndex) | ||
638 | { | ||
639 | int numDirectBits = ((posSlot >> 1) - 1); | ||
640 | |||
641 | /* if (bufLimit - buf >= 8) return DUMMY_MATCH; */ | ||
642 | |||
643 | if (posSlot < kEndPosModelIndex) | ||
644 | { | ||
645 | prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits) - posSlot - 1; | ||
646 | } | ||
647 | else | ||
648 | { | ||
649 | numDirectBits -= kNumAlignBits; | ||
650 | do | ||
651 | { | ||
652 | NORMALIZE_CHECK | ||
653 | range >>= 1; | ||
654 | code -= range & (((code - range) >> 31) - 1); | ||
655 | /* if (code >= range) code -= range; */ | ||
656 | } | ||
657 | while (--numDirectBits != 0); | ||
658 | prob = probs + Align; | ||
659 | numDirectBits = kNumAlignBits; | ||
660 | } | ||
661 | { | ||
662 | unsigned i = 1; | ||
663 | do | ||
664 | { | ||
665 | GET_BIT_CHECK(prob + i, i); | ||
666 | } | ||
667 | while (--numDirectBits != 0); | ||
668 | } | ||
669 | } | ||
670 | } | ||
671 | } | ||
672 | } | ||
673 | NORMALIZE_CHECK; | ||
674 | return res; | ||
675 | } | ||
676 | |||
677 | |||
678 | static void LzmaDec_InitRc(CLzmaDec *p, const Byte *data) | ||
679 | { | ||
680 | p->code = ((UInt32)data[1] << 24) | ((UInt32)data[2] << 16) | ((UInt32)data[3] << 8) | ((UInt32)data[4]); | ||
681 | p->range = 0xFFFFFFFF; | ||
682 | p->needFlush = 0; | ||
683 | } | ||
684 | |||
685 | void LzmaDec_InitDicAndState(CLzmaDec *p, Bool initDic, Bool initState) | ||
686 | { | ||
687 | p->needFlush = 1; | ||
688 | p->remainLen = 0; | ||
689 | p->tempBufSize = 0; | ||
690 | |||
691 | if (initDic) | ||
692 | { | ||
693 | p->processedPos = 0; | ||
694 | p->checkDicSize = 0; | ||
695 | p->needInitState = 1; | ||
696 | } | ||
697 | if (initState) | ||
698 | p->needInitState = 1; | ||
699 | } | ||
700 | |||
701 | void LzmaDec_Init(CLzmaDec *p) | ||
702 | { | ||
703 | p->dicPos = 0; | ||
704 | LzmaDec_InitDicAndState(p, True, True); | ||
705 | } | ||
706 | |||
707 | static void LzmaDec_InitStateReal(CLzmaDec *p) | ||
708 | { | ||
709 | UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (p->prop.lc + p->prop.lp)); | ||
710 | UInt32 i; | ||
711 | CLzmaProb *probs = p->probs; | ||
712 | for (i = 0; i < numProbs; i++) | ||
713 | probs[i] = kBitModelTotal >> 1; | ||
714 | p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1; | ||
715 | p->state = 0; | ||
716 | p->needInitState = 0; | ||
717 | } | ||
718 | |||
719 | SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit, const Byte *src, SizeT *srcLen, | ||
720 | ELzmaFinishMode finishMode, ELzmaStatus *status) | ||
721 | { | ||
722 | SizeT inSize = *srcLen; | ||
723 | (*srcLen) = 0; | ||
724 | LzmaDec_WriteRem(p, dicLimit); | ||
725 | |||
726 | *status = LZMA_STATUS_NOT_SPECIFIED; | ||
727 | |||
728 | while (p->remainLen != kMatchSpecLenStart) | ||
729 | { | ||
730 | int checkEndMarkNow; | ||
731 | |||
732 | if (p->needFlush != 0) | ||
733 | { | ||
734 | for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--) | ||
735 | p->tempBuf[p->tempBufSize++] = *src++; | ||
736 | if (p->tempBufSize < RC_INIT_SIZE) | ||
737 | { | ||
738 | *status = LZMA_STATUS_NEEDS_MORE_INPUT; | ||
739 | return SZ_OK; | ||
740 | } | ||
741 | if (p->tempBuf[0] != 0) | ||
742 | return SZ_ERROR_DATA; | ||
743 | |||
744 | LzmaDec_InitRc(p, p->tempBuf); | ||
745 | p->tempBufSize = 0; | ||
746 | } | ||
747 | |||
748 | checkEndMarkNow = 0; | ||
749 | if (p->dicPos >= dicLimit) | ||
750 | { | ||
751 | if (p->remainLen == 0 && p->code == 0) | ||
752 | { | ||
753 | *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK; | ||
754 | return SZ_OK; | ||
755 | } | ||
756 | if (finishMode == LZMA_FINISH_ANY) | ||
757 | { | ||
758 | *status = LZMA_STATUS_NOT_FINISHED; | ||
759 | return SZ_OK; | ||
760 | } | ||
761 | if (p->remainLen != 0) | ||
762 | { | ||
763 | *status = LZMA_STATUS_NOT_FINISHED; | ||
764 | return SZ_ERROR_DATA; | ||
765 | } | ||
766 | checkEndMarkNow = 1; | ||
767 | } | ||
768 | |||
769 | if (p->needInitState) | ||
770 | LzmaDec_InitStateReal(p); | ||
771 | |||
772 | if (p->tempBufSize == 0) | ||
773 | { | ||
774 | SizeT processed; | ||
775 | const Byte *bufLimit; | ||
776 | if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow) | ||
777 | { | ||
778 | int dummyRes = LzmaDec_TryDummy(p, src, inSize); | ||
779 | if (dummyRes == DUMMY_ERROR) | ||
780 | { | ||
781 | memcpy(p->tempBuf, src, inSize); | ||
782 | p->tempBufSize = (unsigned)inSize; | ||
783 | (*srcLen) += inSize; | ||
784 | *status = LZMA_STATUS_NEEDS_MORE_INPUT; | ||
785 | return SZ_OK; | ||
786 | } | ||
787 | if (checkEndMarkNow && dummyRes != DUMMY_MATCH) | ||
788 | { | ||
789 | *status = LZMA_STATUS_NOT_FINISHED; | ||
790 | return SZ_ERROR_DATA; | ||
791 | } | ||
792 | bufLimit = src; | ||
793 | } | ||
794 | else | ||
795 | bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX; | ||
796 | p->buf = src; | ||
797 | if (LzmaDec_DecodeReal2(p, dicLimit, bufLimit) != 0) | ||
798 | return SZ_ERROR_DATA; | ||
799 | processed = (SizeT)(p->buf - src); | ||
800 | (*srcLen) += processed; | ||
801 | src += processed; | ||
802 | inSize -= processed; | ||
803 | } | ||
804 | else | ||
805 | { | ||
806 | unsigned rem = p->tempBufSize, lookAhead = 0; | ||
807 | while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize) | ||
808 | p->tempBuf[rem++] = src[lookAhead++]; | ||
809 | p->tempBufSize = rem; | ||
810 | if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow) | ||
811 | { | ||
812 | int dummyRes = LzmaDec_TryDummy(p, p->tempBuf, rem); | ||
813 | if (dummyRes == DUMMY_ERROR) | ||
814 | { | ||
815 | (*srcLen) += lookAhead; | ||
816 | *status = LZMA_STATUS_NEEDS_MORE_INPUT; | ||
817 | return SZ_OK; | ||
818 | } | ||
819 | if (checkEndMarkNow && dummyRes != DUMMY_MATCH) | ||
820 | { | ||
821 | *status = LZMA_STATUS_NOT_FINISHED; | ||
822 | return SZ_ERROR_DATA; | ||
823 | } | ||
824 | } | ||
825 | p->buf = p->tempBuf; | ||
826 | if (LzmaDec_DecodeReal2(p, dicLimit, p->buf) != 0) | ||
827 | return SZ_ERROR_DATA; | ||
828 | lookAhead -= (rem - (unsigned)(p->buf - p->tempBuf)); | ||
829 | (*srcLen) += lookAhead; | ||
830 | src += lookAhead; | ||
831 | inSize -= lookAhead; | ||
832 | p->tempBufSize = 0; | ||
833 | } | ||
834 | } | ||
835 | if (p->code == 0) | ||
836 | *status = LZMA_STATUS_FINISHED_WITH_MARK; | ||
837 | return (p->code == 0) ? SZ_OK : SZ_ERROR_DATA; | ||
838 | } | ||
839 | |||
840 | SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status) | ||
841 | { | ||
842 | SizeT outSize = *destLen; | ||
843 | SizeT inSize = *srcLen; | ||
844 | *srcLen = *destLen = 0; | ||
845 | for (;;) | ||
846 | { | ||
847 | SizeT inSizeCur = inSize, outSizeCur, dicPos; | ||
848 | ELzmaFinishMode curFinishMode; | ||
849 | SRes res; | ||
850 | if (p->dicPos == p->dicBufSize) | ||
851 | p->dicPos = 0; | ||
852 | dicPos = p->dicPos; | ||
853 | if (outSize > p->dicBufSize - dicPos) | ||
854 | { | ||
855 | outSizeCur = p->dicBufSize; | ||
856 | curFinishMode = LZMA_FINISH_ANY; | ||
857 | } | ||
858 | else | ||
859 | { | ||
860 | outSizeCur = dicPos + outSize; | ||
861 | curFinishMode = finishMode; | ||
862 | } | ||
863 | |||
864 | res = LzmaDec_DecodeToDic(p, outSizeCur, src, &inSizeCur, curFinishMode, status); | ||
865 | src += inSizeCur; | ||
866 | inSize -= inSizeCur; | ||
867 | *srcLen += inSizeCur; | ||
868 | outSizeCur = p->dicPos - dicPos; | ||
869 | memcpy(dest, p->dic + dicPos, outSizeCur); | ||
870 | dest += outSizeCur; | ||
871 | outSize -= outSizeCur; | ||
872 | *destLen += outSizeCur; | ||
873 | if (res != 0) | ||
874 | return res; | ||
875 | if (outSizeCur == 0 || outSize == 0) | ||
876 | return SZ_OK; | ||
877 | } | ||
878 | } | ||
879 | |||
880 | void LzmaDec_FreeProbs(CLzmaDec *p, ISzAlloc *alloc) | ||
881 | { | ||
882 | alloc->Free(alloc, p->probs); | ||
883 | p->probs = 0; | ||
884 | } | ||
885 | |||
886 | static void LzmaDec_FreeDict(CLzmaDec *p, ISzAlloc *alloc) | ||
887 | { | ||
888 | alloc->Free(alloc, p->dic); | ||
889 | p->dic = 0; | ||
890 | } | ||
891 | |||
892 | void LzmaDec_Free(CLzmaDec *p, ISzAlloc *alloc) | ||
893 | { | ||
894 | LzmaDec_FreeProbs(p, alloc); | ||
895 | LzmaDec_FreeDict(p, alloc); | ||
896 | } | ||
897 | |||
898 | SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size) | ||
899 | { | ||
900 | UInt32 dicSize; | ||
901 | Byte d; | ||
902 | |||
903 | if (size < LZMA_PROPS_SIZE) | ||
904 | return SZ_ERROR_UNSUPPORTED; | ||
905 | else | ||
906 | dicSize = data[1] | ((UInt32)data[2] << 8) | ((UInt32)data[3] << 16) | ((UInt32)data[4] << 24); | ||
907 | |||
908 | if (dicSize < LZMA_DIC_MIN) | ||
909 | dicSize = LZMA_DIC_MIN; | ||
910 | p->dicSize = dicSize; | ||
911 | |||
912 | d = data[0]; | ||
913 | if (d >= (9 * 5 * 5)) | ||
914 | return SZ_ERROR_UNSUPPORTED; | ||
915 | |||
916 | p->lc = d % 9; | ||
917 | d /= 9; | ||
918 | p->pb = d / 5; | ||
919 | p->lp = d % 5; | ||
920 | |||
921 | return SZ_OK; | ||
922 | } | ||
923 | |||
924 | static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew, ISzAlloc *alloc) | ||
925 | { | ||
926 | UInt32 numProbs = LzmaProps_GetNumProbs(propNew); | ||
927 | if (p->probs == 0 || numProbs != p->numProbs) | ||
928 | { | ||
929 | LzmaDec_FreeProbs(p, alloc); | ||
930 | p->probs = (CLzmaProb *)alloc->Alloc(alloc, numProbs * sizeof(CLzmaProb)); | ||
931 | p->numProbs = numProbs; | ||
932 | if (p->probs == 0) | ||
933 | return SZ_ERROR_MEM; | ||
934 | } | ||
935 | return SZ_OK; | ||
936 | } | ||
937 | |||
938 | SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc) | ||
939 | { | ||
940 | CLzmaProps propNew; | ||
941 | RINOK(LzmaProps_Decode(&propNew, props, propsSize)); | ||
942 | RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc)); | ||
943 | p->prop = propNew; | ||
944 | return SZ_OK; | ||
945 | } | ||
946 | |||
947 | SRes LzmaDec_Allocate(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc) | ||
948 | { | ||
949 | CLzmaProps propNew; | ||
950 | SizeT dicBufSize; | ||
951 | RINOK(LzmaProps_Decode(&propNew, props, propsSize)); | ||
952 | RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc)); | ||
953 | dicBufSize = propNew.dicSize; | ||
954 | if (p->dic == 0 || dicBufSize != p->dicBufSize) | ||
955 | { | ||
956 | LzmaDec_FreeDict(p, alloc); | ||
957 | p->dic = (Byte *)alloc->Alloc(alloc, dicBufSize); | ||
958 | if (p->dic == 0) | ||
959 | { | ||
960 | LzmaDec_FreeProbs(p, alloc); | ||
961 | return SZ_ERROR_MEM; | ||
962 | } | ||
963 | } | ||
964 | p->dicBufSize = dicBufSize; | ||
965 | p->prop = propNew; | ||
966 | return SZ_OK; | ||
967 | } | ||
968 | |||
969 | SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, | ||
970 | const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode, | ||
971 | ELzmaStatus *status, ISzAlloc *alloc) | ||
972 | { | ||
973 | CLzmaDec p; | ||
974 | SRes res; | ||
975 | SizeT inSize = *srcLen; | ||
976 | SizeT outSize = *destLen; | ||
977 | *srcLen = *destLen = 0; | ||
978 | if (inSize < RC_INIT_SIZE) | ||
979 | return SZ_ERROR_INPUT_EOF; | ||
980 | |||
981 | LzmaDec_Construct(&p); | ||
982 | res = LzmaDec_AllocateProbs(&p, propData, propSize, alloc); | ||
983 | if (res != 0) | ||
984 | return res; | ||
985 | p.dic = dest; | ||
986 | p.dicBufSize = outSize; | ||
987 | |||
988 | LzmaDec_Init(&p); | ||
989 | |||
990 | *srcLen = inSize; | ||
991 | res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status); | ||
992 | |||
993 | if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT) | ||
994 | res = SZ_ERROR_INPUT_EOF; | ||
995 | |||
996 | (*destLen) = p.dicPos; | ||
997 | LzmaDec_FreeProbs(&p, alloc); | ||
998 | return res; | ||
999 | } | ||