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