source: trunk/package/uboot-ifxmips/files/lib_generic/LzmaDecode.c @ 13291

Last change on this file since 13291 was 13291, checked in by thl, 8 years ago

[ifxmips] cleanup uboot package

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