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