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