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