soc/mediatek/mt8196: Initialize SSPM
[coreboot.git] / payloads / libpayload / liblzma / lzmadecode.c
blobc8115d308a7c3870e45e5160f617a7b94f25903e
1 /*
2 LzmaDecode.c
3 LZMA Decoder (optimized for Speed version)
5 LZMA SDK 4.40 Copyright (c) 1999-2006 Igor Pavlov (2006-05-01)
6 http://www.7-zip.org/
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.
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.
22 #include "lzmadecode.h"
24 #define kNumTopBits 24
25 #define kTopValue ((UInt32)1 << kNumTopBits)
27 #define kNumBitModelTotalBits 11
28 #define kBitModelTotal (1 << kNumBitModelTotalBits)
29 #define kNumMoveBits 5
31 #define RC_READ_BYTE (*Buffer++)
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; }}
36 #define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
38 #define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
40 #define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
42 #define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)
43 #define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;
44 #define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;
46 #define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \
47 { UpdateBit0(p); mi <<= 1; A0; } else \
48 { UpdateBit1(p); mi = (mi + mi) + 1; A1; }
50 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
52 #define RangeDecoderBitTreeDecode(probs, numLevels, res) \
53 { int i = numLevels; res = 1; \
54 do { CProb *cp = probs + res; RC_GET_BIT(cp, res) } while(--i != 0); \
55 res -= (1 << numLevels); }
57 #define kNumPosBitsMax 4
58 #define kNumPosStatesMax (1 << kNumPosBitsMax)
60 #define kLenNumLowBits 3
61 #define kLenNumLowSymbols (1 << kLenNumLowBits)
62 #define kLenNumMidBits 3
63 #define kLenNumMidSymbols (1 << kLenNumMidBits)
64 #define kLenNumHighBits 8
65 #define kLenNumHighSymbols (1 << kLenNumHighBits)
67 #define LenChoice 0
68 #define LenChoice2 (LenChoice + 1)
69 #define LenLow (LenChoice2 + 1)
70 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
71 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
72 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
74 #define kNumStates 12
75 #define kNumLitStates 7
77 #define kStartPosModelIndex 4
78 #define kEndPosModelIndex 14
79 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
81 #define kNumPosSlotBits 6
82 #define kNumLenToPosStates 4
84 #define kNumAlignBits 4
85 #define kAlignTableSize (1 << kNumAlignBits)
87 #define kMatchMinLen 2
89 #define IsMatch 0
90 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
91 #define IsRepG0 (IsRep + kNumStates)
92 #define IsRepG1 (IsRepG0 + kNumStates)
93 #define IsRepG2 (IsRepG1 + kNumStates)
94 #define IsRep0Long (IsRepG2 + kNumStates)
95 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
96 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
97 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
98 #define LenCoder (Align + kAlignTableSize)
99 #define RepLenCoder (LenCoder + kNumLenProbs)
100 #define Literal (RepLenCoder + kNumLenProbs)
102 #if Literal != LZMA_BASE_SIZE
103 StopCompilingDueBUG
104 #endif
106 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
108 unsigned char prop0;
109 if (size < LZMA_PROPERTIES_SIZE)
110 return LZMA_RESULT_DATA_ERROR;
111 prop0 = propsData[0];
112 if (prop0 >= (9 * 5 * 5))
113 return LZMA_RESULT_DATA_ERROR;
115 for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
116 for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
117 propsRes->lc = prop0;
119 unsigned char remainder = (unsigned char)(prop0 / 9);
120 propsRes->lc = prop0 % 9;
121 propsRes->pb = remainder / 5;
122 propsRes->lp = remainder % 5;
126 return LZMA_RESULT_OK;
129 #define kLzmaStreamWasFinishedId (-1)
131 int LzmaDecode(CLzmaDecoderState *vs,
132 const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
133 unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
135 CProb *p = vs->Probs;
136 SizeT nowPos = 0;
137 Byte previousByte = 0;
138 UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
139 UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
140 int lc = vs->Properties.lc;
142 int state = 0;
143 UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
144 int len = 0;
145 const Byte *Buffer;
146 const Byte *BufferLim;
147 UInt32 Range;
148 UInt32 Code;
150 *inSizeProcessed = 0;
151 *outSizeProcessed = 0;
154 UInt32 i;
155 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
156 for (i = 0; i < numProbs; i++)
157 p[i] = kBitModelTotal >> 1;
160 RC_INIT(inStream, inSize);
162 while(nowPos < outSize)
164 CProb *prob;
165 UInt32 bound;
166 int posState = (int)(
167 (nowPos
169 & posStateMask);
171 prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
172 IfBit0(prob)
174 int symbol = 1;
175 UpdateBit0(prob)
176 prob = p + Literal + (LZMA_LIT_SIZE *
178 (nowPos
180 & literalPosMask) << lc) + (previousByte >> (8 - lc))));
182 if (state >= kNumLitStates)
184 int matchByte;
185 matchByte = outStream[nowPos - rep0];
188 int bit;
189 CProb *probLit;
190 matchByte <<= 1;
191 bit = (matchByte & 0x100);
192 probLit = prob + 0x100 + bit + symbol;
193 RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
195 while (symbol < 0x100);
197 while (symbol < 0x100)
199 CProb *probLit = prob + symbol;
200 RC_GET_BIT(probLit, symbol)
202 previousByte = (Byte)symbol;
204 outStream[nowPos++] = previousByte;
205 if (state < 4) state = 0;
206 else if (state < 10) state -= 3;
207 else state -= 6;
209 else
211 UpdateBit1(prob);
212 prob = p + IsRep + state;
213 IfBit0(prob)
215 UpdateBit0(prob);
216 rep3 = rep2;
217 rep2 = rep1;
218 rep1 = rep0;
219 state = state < kNumLitStates ? 0 : 3;
220 prob = p + LenCoder;
222 else
224 UpdateBit1(prob);
225 prob = p + IsRepG0 + state;
226 IfBit0(prob)
228 UpdateBit0(prob);
229 prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
230 IfBit0(prob)
232 UpdateBit0(prob);
234 if (nowPos == 0)
235 return LZMA_RESULT_DATA_ERROR;
237 state = state < kNumLitStates ? 9 : 11;
238 previousByte = outStream[nowPos - rep0];
239 outStream[nowPos++] = previousByte;
241 continue;
243 else
245 UpdateBit1(prob);
248 else
250 UInt32 distance;
251 UpdateBit1(prob);
252 prob = p + IsRepG1 + state;
253 IfBit0(prob)
255 UpdateBit0(prob);
256 distance = rep1;
258 else
260 UpdateBit1(prob);
261 prob = p + IsRepG2 + state;
262 IfBit0(prob)
264 UpdateBit0(prob);
265 distance = rep2;
267 else
269 UpdateBit1(prob);
270 distance = rep3;
271 rep3 = rep2;
273 rep2 = rep1;
275 rep1 = rep0;
276 rep0 = distance;
278 state = state < kNumLitStates ? 8 : 11;
279 prob = p + RepLenCoder;
282 int numBits, offset;
283 CProb *probLen = prob + LenChoice;
284 IfBit0(probLen)
286 UpdateBit0(probLen);
287 probLen = prob + LenLow + (posState << kLenNumLowBits);
288 offset = 0;
289 numBits = kLenNumLowBits;
291 else
293 UpdateBit1(probLen);
294 probLen = prob + LenChoice2;
295 IfBit0(probLen)
297 UpdateBit0(probLen);
298 probLen = prob + LenMid + (posState << kLenNumMidBits);
299 offset = kLenNumLowSymbols;
300 numBits = kLenNumMidBits;
302 else
304 UpdateBit1(probLen);
305 probLen = prob + LenHigh;
306 offset = kLenNumLowSymbols + kLenNumMidSymbols;
307 numBits = kLenNumHighBits;
310 RangeDecoderBitTreeDecode(probLen, numBits, len);
311 len += offset;
314 if (state < 4)
316 int posSlot;
317 state += kNumLitStates;
318 prob = p + PosSlot +
319 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
320 kNumPosSlotBits);
321 RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
322 if (posSlot >= kStartPosModelIndex)
324 int numDirectBits = ((posSlot >> 1) - 1);
325 rep0 = (2 | ((UInt32)posSlot & 1));
326 if (posSlot < kEndPosModelIndex)
328 rep0 <<= numDirectBits;
329 prob = p + SpecPos + rep0 - posSlot - 1;
331 else
333 numDirectBits -= kNumAlignBits;
336 RC_NORMALIZE
337 Range >>= 1;
338 rep0 <<= 1;
339 if (Code >= Range)
341 Code -= Range;
342 rep0 |= 1;
345 while (--numDirectBits != 0);
346 prob = p + Align;
347 rep0 <<= kNumAlignBits;
348 numDirectBits = kNumAlignBits;
351 int i = 1;
352 int mi = 1;
355 CProb *prob3 = prob + mi;
356 RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
357 i <<= 1;
359 while(--numDirectBits != 0);
362 else
363 rep0 = posSlot;
364 if (++rep0 == (UInt32)(0))
366 /* it's for stream version */
367 len = kLzmaStreamWasFinishedId;
368 break;
372 len += kMatchMinLen;
373 if (rep0 > nowPos)
374 return LZMA_RESULT_DATA_ERROR;
378 previousByte = outStream[nowPos - rep0];
379 len--;
380 outStream[nowPos++] = previousByte;
382 while(len != 0 && nowPos < outSize);
385 RC_NORMALIZE;
387 *inSizeProcessed = (SizeT)(Buffer - inStream);
388 *outSizeProcessed = nowPos;
389 return LZMA_RESULT_OK;