finally move buildroot-ng to trunk
[openwrt/staging/dedeckeh.git] / target / image / ar7 / src / LzmaDecode.c
1 /*
2 LzmaDecode.c
3 LZMA Decoder
4
5 LZMA SDK 4.05 Copyright (c) 1999-2004 Igor Pavlov (2004-08-25)
6 http://www.7-zip.org/
7
8 LZMA SDK is licensed under two licenses:
9 1) GNU Lesser General Public License (GNU LGPL)
10 2) Common Public License (CPL)
11 It means that you can select one of these two licenses and
12 follow rules of that license.
13
14 SPECIAL EXCEPTION:
15 Igor Pavlov, as the author of this code, expressly permits you to
16 statically or dynamically link your code (or bind by name) to the
17 interfaces of this file without subjecting your linked code to the
18 terms of the CPL or GNU LGPL. Any modifications or additions
19 to this file, however, are subject to the LGPL or CPL terms.
20 */
21
22 #include "LzmaDecode.h"
23
24 #ifndef Byte
25 #define Byte unsigned char
26 #endif
27
28 #define kNumTopBits 24
29 #define kTopValue ((UInt32)1 << kNumTopBits)
30
31 #define kNumBitModelTotalBits 11
32 #define kBitModelTotal (1 << kNumBitModelTotalBits)
33 #define kNumMoveBits 5
34
35 typedef struct _CRangeDecoder
36 {
37 Byte *Buffer;
38 Byte *BufferLim;
39 UInt32 Range;
40 UInt32 Code;
41 #ifdef _LZMA_IN_CB
42 ILzmaInCallback *InCallback;
43 int Result;
44 #endif
45 int ExtraBytes;
46 } CRangeDecoder;
47
48 Byte RangeDecoderReadByte(CRangeDecoder *rd)
49 {
50 if (rd->Buffer == rd->BufferLim)
51 {
52 #ifdef _LZMA_IN_CB
53 UInt32 size;
54 rd->Result = rd->InCallback->Read(rd->InCallback, &rd->Buffer, &size);
55 rd->BufferLim = rd->Buffer + size;
56 if (size == 0)
57 #endif
58 {
59 rd->ExtraBytes = 1;
60 return 0xFF;
61 }
62 }
63 return (*rd->Buffer++);
64 }
65
66 /* #define ReadByte (*rd->Buffer++) */
67 #define ReadByte (RangeDecoderReadByte(rd))
68
69 void RangeDecoderInit(CRangeDecoder *rd,
70 #ifdef _LZMA_IN_CB
71 ILzmaInCallback *inCallback
72 #else
73 Byte *stream, UInt32 bufferSize
74 #endif
75 )
76 {
77 int i;
78 #ifdef _LZMA_IN_CB
79 rd->InCallback = inCallback;
80 rd->Buffer = rd->BufferLim = 0;
81 #else
82 rd->Buffer = stream;
83 rd->BufferLim = stream + bufferSize;
84 #endif
85 rd->ExtraBytes = 0;
86 rd->Code = 0;
87 rd->Range = (0xFFFFFFFF);
88 for(i = 0; i < 5; i++)
89 rd->Code = (rd->Code << 8) | ReadByte;
90 }
91
92 #define RC_INIT_VAR UInt32 range = rd->Range; UInt32 code = rd->Code;
93 #define RC_FLUSH_VAR rd->Range = range; rd->Code = code;
94 #define RC_NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | ReadByte; }
95
96 UInt32 RangeDecoderDecodeDirectBits(CRangeDecoder *rd, int numTotalBits)
97 {
98 RC_INIT_VAR
99 UInt32 result = 0;
100 int i;
101 for (i = numTotalBits; i > 0; i--)
102 {
103 /* UInt32 t; */
104 range >>= 1;
105
106 result <<= 1;
107 if (code >= range)
108 {
109 code -= range;
110 result |= 1;
111 }
112 /*
113 t = (code - range) >> 31;
114 t &= 1;
115 code -= range & (t - 1);
116 result = (result + result) | (1 - t);
117 */
118 RC_NORMALIZE
119 }
120 RC_FLUSH_VAR
121 return result;
122 }
123
124 int RangeDecoderBitDecode(CProb *prob, CRangeDecoder *rd)
125 {
126 UInt32 bound = (rd->Range >> kNumBitModelTotalBits) * *prob;
127 if (rd->Code < bound)
128 {
129 rd->Range = bound;
130 *prob += (kBitModelTotal - *prob) >> kNumMoveBits;
131 if (rd->Range < kTopValue)
132 {
133 rd->Code = (rd->Code << 8) | ReadByte;
134 rd->Range <<= 8;
135 }
136 return 0;
137 }
138 else
139 {
140 rd->Range -= bound;
141 rd->Code -= bound;
142 *prob -= (*prob) >> kNumMoveBits;
143 if (rd->Range < kTopValue)
144 {
145 rd->Code = (rd->Code << 8) | ReadByte;
146 rd->Range <<= 8;
147 }
148 return 1;
149 }
150 }
151
152 #define RC_GET_BIT2(prob, mi, A0, A1) \
153 UInt32 bound = (range >> kNumBitModelTotalBits) * *prob; \
154 if (code < bound) \
155 { A0; range = bound; *prob += (kBitModelTotal - *prob) >> kNumMoveBits; mi <<= 1; } \
156 else \
157 { A1; range -= bound; code -= bound; *prob -= (*prob) >> kNumMoveBits; mi = (mi + mi) + 1; } \
158 RC_NORMALIZE
159
160 #define RC_GET_BIT(prob, mi) RC_GET_BIT2(prob, mi, ; , ;)
161
162 int RangeDecoderBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd)
163 {
164 int mi = 1;
165 int i;
166 #ifdef _LZMA_LOC_OPT
167 RC_INIT_VAR
168 #endif
169 for(i = numLevels; i > 0; i--)
170 {
171 #ifdef _LZMA_LOC_OPT
172 CProb *prob = probs + mi;
173 RC_GET_BIT(prob, mi)
174 #else
175 mi = (mi + mi) + RangeDecoderBitDecode(probs + mi, rd);
176 #endif
177 }
178 #ifdef _LZMA_LOC_OPT
179 RC_FLUSH_VAR
180 #endif
181 return mi - (1 << numLevels);
182 }
183
184 int RangeDecoderReverseBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd)
185 {
186 int mi = 1;
187 int i;
188 int symbol = 0;
189 #ifdef _LZMA_LOC_OPT
190 RC_INIT_VAR
191 #endif
192 for(i = 0; i < numLevels; i++)
193 {
194 #ifdef _LZMA_LOC_OPT
195 CProb *prob = probs + mi;
196 RC_GET_BIT2(prob, mi, ; , symbol |= (1 << i))
197 #else
198 int bit = RangeDecoderBitDecode(probs + mi, rd);
199 mi = mi + mi + bit;
200 symbol |= (bit << i);
201 #endif
202 }
203 #ifdef _LZMA_LOC_OPT
204 RC_FLUSH_VAR
205 #endif
206 return symbol;
207 }
208
209 Byte LzmaLiteralDecode(CProb *probs, CRangeDecoder *rd)
210 {
211 int symbol = 1;
212 #ifdef _LZMA_LOC_OPT
213 RC_INIT_VAR
214 #endif
215 do
216 {
217 #ifdef _LZMA_LOC_OPT
218 CProb *prob = probs + symbol;
219 RC_GET_BIT(prob, symbol)
220 #else
221 symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd);
222 #endif
223 }
224 while (symbol < 0x100);
225 #ifdef _LZMA_LOC_OPT
226 RC_FLUSH_VAR
227 #endif
228 return symbol;
229 }
230
231 Byte LzmaLiteralDecodeMatch(CProb *probs, CRangeDecoder *rd, Byte matchByte)
232 {
233 int symbol = 1;
234 #ifdef _LZMA_LOC_OPT
235 RC_INIT_VAR
236 #endif
237 do
238 {
239 int bit;
240 int matchBit = (matchByte >> 7) & 1;
241 matchByte <<= 1;
242 #ifdef _LZMA_LOC_OPT
243 {
244 CProb *prob = probs + ((1 + matchBit) << 8) + symbol;
245 RC_GET_BIT2(prob, symbol, bit = 0, bit = 1)
246 }
247 #else
248 bit = RangeDecoderBitDecode(probs + ((1 + matchBit) << 8) + symbol, rd);
249 symbol = (symbol << 1) | bit;
250 #endif
251 if (matchBit != bit)
252 {
253 while (symbol < 0x100)
254 {
255 #ifdef _LZMA_LOC_OPT
256 CProb *prob = probs + symbol;
257 RC_GET_BIT(prob, symbol)
258 #else
259 symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd);
260 #endif
261 }
262 break;
263 }
264 }
265 while (symbol < 0x100);
266 #ifdef _LZMA_LOC_OPT
267 RC_FLUSH_VAR
268 #endif
269 return symbol;
270 }
271
272 #define kNumPosBitsMax 4
273 #define kNumPosStatesMax (1 << kNumPosBitsMax)
274
275 #define kLenNumLowBits 3
276 #define kLenNumLowSymbols (1 << kLenNumLowBits)
277 #define kLenNumMidBits 3
278 #define kLenNumMidSymbols (1 << kLenNumMidBits)
279 #define kLenNumHighBits 8
280 #define kLenNumHighSymbols (1 << kLenNumHighBits)
281
282 #define LenChoice 0
283 #define LenChoice2 (LenChoice + 1)
284 #define LenLow (LenChoice2 + 1)
285 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
286 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
287 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
288
289 int LzmaLenDecode(CProb *p, CRangeDecoder *rd, int posState)
290 {
291 if(RangeDecoderBitDecode(p + LenChoice, rd) == 0)
292 return RangeDecoderBitTreeDecode(p + LenLow +
293 (posState << kLenNumLowBits), kLenNumLowBits, rd);
294 if(RangeDecoderBitDecode(p + LenChoice2, rd) == 0)
295 return kLenNumLowSymbols + RangeDecoderBitTreeDecode(p + LenMid +
296 (posState << kLenNumMidBits), kLenNumMidBits, rd);
297 return kLenNumLowSymbols + kLenNumMidSymbols +
298 RangeDecoderBitTreeDecode(p + LenHigh, kLenNumHighBits, rd);
299 }
300
301 #define kNumStates 12
302
303 #define kStartPosModelIndex 4
304 #define kEndPosModelIndex 14
305 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
306
307 #define kNumPosSlotBits 6
308 #define kNumLenToPosStates 4
309
310 #define kNumAlignBits 4
311 #define kAlignTableSize (1 << kNumAlignBits)
312
313 #define kMatchMinLen 2
314
315 #define IsMatch 0
316 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
317 #define IsRepG0 (IsRep + kNumStates)
318 #define IsRepG1 (IsRepG0 + kNumStates)
319 #define IsRepG2 (IsRepG1 + kNumStates)
320 #define IsRep0Long (IsRepG2 + kNumStates)
321 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
322 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
323 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
324 #define LenCoder (Align + kAlignTableSize)
325 #define RepLenCoder (LenCoder + kNumLenProbs)
326 #define Literal (RepLenCoder + kNumLenProbs)
327
328 #if Literal != LZMA_BASE_SIZE
329 StopCompilingDueBUG
330 #endif
331
332 #ifdef _LZMA_OUT_READ
333
334 typedef struct _LzmaVarState
335 {
336 CRangeDecoder RangeDecoder;
337 Byte *Dictionary;
338 UInt32 DictionarySize;
339 UInt32 DictionaryPos;
340 UInt32 GlobalPos;
341 UInt32 Reps[4];
342 int lc;
343 int lp;
344 int pb;
345 int State;
346 int PreviousIsMatch;
347 int RemainLen;
348 } LzmaVarState;
349
350 int LzmaDecoderInit(
351 unsigned char *buffer, UInt32 bufferSize,
352 int lc, int lp, int pb,
353 unsigned char *dictionary, UInt32 dictionarySize,
354 #ifdef _LZMA_IN_CB
355 ILzmaInCallback *inCallback
356 #else
357 unsigned char *inStream, UInt32 inSize
358 #endif
359 )
360 {
361 LzmaVarState *vs = (LzmaVarState *)buffer;
362 CProb *p = (CProb *)(buffer + sizeof(LzmaVarState));
363 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + lp));
364 UInt32 i;
365 if (bufferSize < numProbs * sizeof(CProb) + sizeof(LzmaVarState))
366 return LZMA_RESULT_NOT_ENOUGH_MEM;
367 vs->Dictionary = dictionary;
368 vs->DictionarySize = dictionarySize;
369 vs->DictionaryPos = 0;
370 vs->GlobalPos = 0;
371 vs->Reps[0] = vs->Reps[1] = vs->Reps[2] = vs->Reps[3] = 1;
372 vs->lc = lc;
373 vs->lp = lp;
374 vs->pb = pb;
375 vs->State = 0;
376 vs->PreviousIsMatch = 0;
377 vs->RemainLen = 0;
378 dictionary[dictionarySize - 1] = 0;
379 for (i = 0; i < numProbs; i++)
380 p[i] = kBitModelTotal >> 1;
381 RangeDecoderInit(&vs->RangeDecoder,
382 #ifdef _LZMA_IN_CB
383 inCallback
384 #else
385 inStream, inSize
386 #endif
387 );
388 return LZMA_RESULT_OK;
389 }
390
391 int LzmaDecode(unsigned char *buffer,
392 unsigned char *outStream, UInt32 outSize,
393 UInt32 *outSizeProcessed)
394 {
395 LzmaVarState *vs = (LzmaVarState *)buffer;
396 CProb *p = (CProb *)(buffer + sizeof(LzmaVarState));
397 CRangeDecoder rd = vs->RangeDecoder;
398 int state = vs->State;
399 int previousIsMatch = vs->PreviousIsMatch;
400 Byte previousByte;
401 UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
402 UInt32 nowPos = 0;
403 UInt32 posStateMask = (1 << (vs->pb)) - 1;
404 UInt32 literalPosMask = (1 << (vs->lp)) - 1;
405 int lc = vs->lc;
406 int len = vs->RemainLen;
407 UInt32 globalPos = vs->GlobalPos;
408
409 Byte *dictionary = vs->Dictionary;
410 UInt32 dictionarySize = vs->DictionarySize;
411 UInt32 dictionaryPos = vs->DictionaryPos;
412
413 if (len == -1)
414 {
415 *outSizeProcessed = 0;
416 return LZMA_RESULT_OK;
417 }
418
419 while(len > 0 && nowPos < outSize)
420 {
421 UInt32 pos = dictionaryPos - rep0;
422 if (pos >= dictionarySize)
423 pos += dictionarySize;
424 outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
425 if (++dictionaryPos == dictionarySize)
426 dictionaryPos = 0;
427 len--;
428 }
429 if (dictionaryPos == 0)
430 previousByte = dictionary[dictionarySize - 1];
431 else
432 previousByte = dictionary[dictionaryPos - 1];
433 #else
434
435 int LzmaDecode(
436 Byte *buffer, UInt32 bufferSize,
437 int lc, int lp, int pb,
438 #ifdef _LZMA_IN_CB
439 ILzmaInCallback *inCallback,
440 #else
441 unsigned char *inStream, UInt32 inSize,
442 #endif
443 unsigned char *outStream, UInt32 outSize,
444 UInt32 *outSizeProcessed)
445 {
446 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + lp));
447 CProb *p = (CProb *)buffer;
448 CRangeDecoder rd;
449 UInt32 i;
450 int state = 0;
451 int previousIsMatch = 0;
452 Byte previousByte = 0;
453 UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
454 UInt32 nowPos = 0;
455 UInt32 posStateMask = (1 << pb) - 1;
456 UInt32 literalPosMask = (1 << lp) - 1;
457 int len = 0;
458 if (bufferSize < numProbs * sizeof(CProb))
459 return LZMA_RESULT_NOT_ENOUGH_MEM;
460 for (i = 0; i < numProbs; i++)
461 p[i] = kBitModelTotal >> 1;
462 RangeDecoderInit(&rd,
463 #ifdef _LZMA_IN_CB
464 inCallback
465 #else
466 inStream, inSize
467 #endif
468 );
469 #endif
470
471 *outSizeProcessed = 0;
472 while(nowPos < outSize)
473 {
474 int posState = (int)(
475 (nowPos
476 #ifdef _LZMA_OUT_READ
477 + globalPos
478 #endif
479 )
480 & posStateMask);
481 #ifdef _LZMA_IN_CB
482 if (rd.Result != LZMA_RESULT_OK)
483 return rd.Result;
484 #endif
485 if (rd.ExtraBytes != 0)
486 return LZMA_RESULT_DATA_ERROR;
487 if (RangeDecoderBitDecode(p + IsMatch + (state << kNumPosBitsMax) + posState, &rd) == 0)
488 {
489 CProb *probs = p + Literal + (LZMA_LIT_SIZE *
490 (((
491 (nowPos
492 #ifdef _LZMA_OUT_READ
493 + globalPos
494 #endif
495 )
496 & literalPosMask) << lc) + (previousByte >> (8 - lc))));
497
498 if (state < 4) state = 0;
499 else if (state < 10) state -= 3;
500 else state -= 6;
501 if (previousIsMatch)
502 {
503 Byte matchByte;
504 #ifdef _LZMA_OUT_READ
505 UInt32 pos = dictionaryPos - rep0;
506 if (pos >= dictionarySize)
507 pos += dictionarySize;
508 matchByte = dictionary[pos];
509 #else
510 matchByte = outStream[nowPos - rep0];
511 #endif
512 previousByte = LzmaLiteralDecodeMatch(probs, &rd, matchByte);
513 previousIsMatch = 0;
514 }
515 else
516 previousByte = LzmaLiteralDecode(probs, &rd);
517 outStream[nowPos++] = previousByte;
518 #ifdef _LZMA_OUT_READ
519 dictionary[dictionaryPos] = previousByte;
520 if (++dictionaryPos == dictionarySize)
521 dictionaryPos = 0;
522 #endif
523 }
524 else
525 {
526 previousIsMatch = 1;
527 if (RangeDecoderBitDecode(p + IsRep + state, &rd) == 1)
528 {
529 if (RangeDecoderBitDecode(p + IsRepG0 + state, &rd) == 0)
530 {
531 if (RangeDecoderBitDecode(p + IsRep0Long + (state << kNumPosBitsMax) + posState, &rd) == 0)
532 {
533 #ifdef _LZMA_OUT_READ
534 UInt32 pos;
535 #endif
536 if (
537 (nowPos
538 #ifdef _LZMA_OUT_READ
539 + globalPos
540 #endif
541 )
542 == 0)
543 return LZMA_RESULT_DATA_ERROR;
544 state = state < 7 ? 9 : 11;
545 #ifdef _LZMA_OUT_READ
546 pos = dictionaryPos - rep0;
547 if (pos >= dictionarySize)
548 pos += dictionarySize;
549 previousByte = dictionary[pos];
550 dictionary[dictionaryPos] = previousByte;
551 if (++dictionaryPos == dictionarySize)
552 dictionaryPos = 0;
553 #else
554 previousByte = outStream[nowPos - rep0];
555 #endif
556 outStream[nowPos++] = previousByte;
557 continue;
558 }
559 }
560 else
561 {
562 UInt32 distance;
563 if(RangeDecoderBitDecode(p + IsRepG1 + state, &rd) == 0)
564 distance = rep1;
565 else
566 {
567 if(RangeDecoderBitDecode(p + IsRepG2 + state, &rd) == 0)
568 distance = rep2;
569 else
570 {
571 distance = rep3;
572 rep3 = rep2;
573 }
574 rep2 = rep1;
575 }
576 rep1 = rep0;
577 rep0 = distance;
578 }
579 len = LzmaLenDecode(p + RepLenCoder, &rd, posState);
580 state = state < 7 ? 8 : 11;
581 }
582 else
583 {
584 int posSlot;
585 rep3 = rep2;
586 rep2 = rep1;
587 rep1 = rep0;
588 state = state < 7 ? 7 : 10;
589 len = LzmaLenDecode(p + LenCoder, &rd, posState);
590 posSlot = RangeDecoderBitTreeDecode(p + PosSlot +
591 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
592 kNumPosSlotBits), kNumPosSlotBits, &rd);
593 if (posSlot >= kStartPosModelIndex)
594 {
595 int numDirectBits = ((posSlot >> 1) - 1);
596 rep0 = ((2 | ((UInt32)posSlot & 1)) << numDirectBits);
597 if (posSlot < kEndPosModelIndex)
598 {
599 rep0 += RangeDecoderReverseBitTreeDecode(
600 p + SpecPos + rep0 - posSlot - 1, numDirectBits, &rd);
601 }
602 else
603 {
604 rep0 += RangeDecoderDecodeDirectBits(&rd,
605 numDirectBits - kNumAlignBits) << kNumAlignBits;
606 rep0 += RangeDecoderReverseBitTreeDecode(p + Align, kNumAlignBits, &rd);
607 }
608 }
609 else
610 rep0 = posSlot;
611 rep0++;
612 }
613 if (rep0 == (UInt32)(0))
614 {
615 /* it's for stream version */
616 len = -1;
617 break;
618 }
619 if (rep0 > nowPos
620 #ifdef _LZMA_OUT_READ
621 + globalPos
622 #endif
623 )
624 {
625 return LZMA_RESULT_DATA_ERROR;
626 }
627 len += kMatchMinLen;
628 do
629 {
630 #ifdef _LZMA_OUT_READ
631 UInt32 pos = dictionaryPos - rep0;
632 if (pos >= dictionarySize)
633 pos += dictionarySize;
634 previousByte = dictionary[pos];
635 dictionary[dictionaryPos] = previousByte;
636 if (++dictionaryPos == dictionarySize)
637 dictionaryPos = 0;
638 #else
639 previousByte = outStream[nowPos - rep0];
640 #endif
641 outStream[nowPos++] = previousByte;
642 len--;
643 }
644 while(len > 0 && nowPos < outSize);
645 }
646 }
647
648 #ifdef _LZMA_OUT_READ
649 vs->RangeDecoder = rd;
650 vs->DictionaryPos = dictionaryPos;
651 vs->GlobalPos = globalPos + nowPos;
652 vs->Reps[0] = rep0;
653 vs->Reps[1] = rep1;
654 vs->Reps[2] = rep2;
655 vs->Reps[3] = rep3;
656 vs->State = state;
657 vs->PreviousIsMatch = previousIsMatch;
658 vs->RemainLen = len;
659 #endif
660
661 *outSizeProcessed = nowPos;
662 return LZMA_RESULT_OK;
663 }