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