?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
mb/google/soraka: Fine-tune USB 2.0 port4
[coreboot.git] / src / lib / lzmadecode.c
blobc25001f26aa1560426a3a394ac4140ce6c02ec9c
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 #include <stdint.h>
24
25 #define kNumTopBits 24
26 #define kTopValue ((UInt32)1 << kNumTopBits)
27
28 #define kNumBitModelTotalBits 11
29 #define kBitModelTotal (1 << kNumBitModelTotalBits)
30 #define kNumMoveBits 5
31
32 /* Use 32-bit reads whenever possible to avoid bad flash performance. Fall back
33 * to byte reads for last 4 bytes since RC_TEST returns an error when BufferLim
34 * is *reached* (not surpassed!), meaning we can't allow that to happen while
35 * there are still bytes to decode from the algorithm's point of view. */
36 #define RC_READ_BYTE \
37 (look_ahead_ptr < 4 ? look_ahead.raw[look_ahead_ptr++] \
38 : ((((uintptr_t) Buffer & 3) \
39 || ((SizeT) (BufferLim - Buffer) <= 4)) ? (*Buffer++) \
40 : ((look_ahead.dw = *(UInt32 *)Buffer), (Buffer += 4), \
41 (look_ahead_ptr = 1), look_ahead.raw[0])))
42
43 #define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \
44 { \
45 int i; \
46 \
47 for (i = 0; i < 5; i++) { \
48 RC_TEST; \
49 Code = (Code << 8) | RC_READ_BYTE; \
50 } \
51 }
52
53
54 #define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
55
56 #define RC_INIT(buffer, bufferSize) Buffer = buffer; \
57 BufferLim = buffer + bufferSize; RC_INIT2
58
59
60 #define RC_NORMALIZE \
61 if (Range < kTopValue) { \
62 RC_TEST; \
63 Range <<= 8; \
64 Code = (Code << 8) | RC_READ_BYTE; \
65 }
66
67 #define IfBit0(p) \
68 RC_NORMALIZE; \
69 bound = (Range >> kNumBitModelTotalBits) * *(p); \
70 if (Code < bound)
71
72 #define UpdateBit0(p) \
73 Range = bound; \
74 *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits
75
76 #define UpdateBit1(p) \
77 Range -= bound; \
78 Code -= bound; \
79 *(p) -= (*(p)) >> kNumMoveBits
80
81 #define RC_GET_BIT2(p, mi, A0, A1) \
82 IfBit0(p) { \
83 UpdateBit0(p); \
84 mi <<= 1; \
85 A0; \
86 } else { \
87 UpdateBit1(p); \
88 mi = (mi + mi) + 1; \
89 A1; \
90 }
91
92 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ;, ;)
93
94 #define RangeDecoderBitTreeDecode(probs, numLevels, res) \
95 { \
96 int i = numLevels; \
97 \
98 res = 1; \
99 do { \
100 CProb *cp = probs + res; \
101 RC_GET_BIT(cp, res) \
102 } while (--i != 0); \
103 res -= (1 << numLevels); \
104 }
105
106
107 #define kNumPosBitsMax 4
108 #define kNumPosStatesMax (1 << kNumPosBitsMax)
109
110 #define kLenNumLowBits 3
111 #define kLenNumLowSymbols (1 << kLenNumLowBits)
112 #define kLenNumMidBits 3
113 #define kLenNumMidSymbols (1 << kLenNumMidBits)
114 #define kLenNumHighBits 8
115 #define kLenNumHighSymbols (1 << kLenNumHighBits)
116
117 #define LenChoice 0
118 #define LenChoice2 (LenChoice + 1)
119 #define LenLow (LenChoice2 + 1)
120 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
121 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
122 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
123
124
125 #define kNumStates 12
126 #define kNumLitStates 7
127
128 #define kStartPosModelIndex 4
129 #define kEndPosModelIndex 14
130 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
131
132 #define kNumPosSlotBits 6
133 #define kNumLenToPosStates 4
134
135 #define kNumAlignBits 4
136 #define kAlignTableSize (1 << kNumAlignBits)
137
138 #define kMatchMinLen 2
139
140 #define IsMatch 0
141 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
142 #define IsRepG0 (IsRep + kNumStates)
143 #define IsRepG1 (IsRepG0 + kNumStates)
144 #define IsRepG2 (IsRepG1 + kNumStates)
145 #define IsRep0Long (IsRepG2 + kNumStates)
146 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
147 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
148 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
149 #define LenCoder (Align + kAlignTableSize)
150 #define RepLenCoder (LenCoder + kNumLenProbs)
151 #define Literal (RepLenCoder + kNumLenProbs)
152
153 #if Literal != LZMA_BASE_SIZE
154 StopCompilingDueBUG
155 #endif
156
157 int LzmaDecodeProperties(CLzmaProperties *propsRes,
158 const unsigned char *propsData, int size)
159 {
160 unsigned char prop0;
161 if (size < LZMA_PROPERTIES_SIZE)
162 return LZMA_RESULT_DATA_ERROR;
163 prop0 = propsData[0];
164 if (prop0 >= (9 * 5 * 5))
165 return LZMA_RESULT_DATA_ERROR;
166 {
167 for (propsRes->pb = 0; prop0 >= (9 * 5);
168 propsRes->pb++, prop0 -= (9 * 5))
169 ;
170 for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9)
171 ;
172 propsRes->lc = prop0;
173 /*
174 * unsigned char remainder = (unsigned char)(prop0 / 9);
175 * propsRes->lc = prop0 % 9;
176 * propsRes->pb = remainder / 5;
177 * propsRes->lp = remainder % 5;
178 */
179 }
180
181 return LZMA_RESULT_OK;
182 }
183
184 #define kLzmaStreamWasFinishedId (-1)
185
186 int LzmaDecode(CLzmaDecoderState *vs,
187 const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
188 unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
189 {
190 CProb *p = vs->Probs;
191 SizeT nowPos = 0;
192 Byte previousByte = 0;
193 UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
194 UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
195 int lc = vs->Properties.lc;
196
197
198 int state = 0;
199 UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
200 int len = 0;
201 const Byte *Buffer;
202 const Byte *BufferLim;
203 int look_ahead_ptr = 4;
204 union {
205 Byte raw[4];
206 UInt32 dw;
207 } look_ahead;
208 UInt32 Range;
209 UInt32 Code;
210
211 *inSizeProcessed = 0;
212 *outSizeProcessed = 0;
213
214 {
215 UInt32 i;
216 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc
217 + vs->Properties.lp));
218 for (i = 0; i < numProbs; i++)
219 p[i] = kBitModelTotal >> 1;
220 }
221
222 RC_INIT(inStream, inSize);
223
224
225 while (nowPos < outSize) {
226 CProb *prob;
227 UInt32 bound;
228 int posState = (int)((nowPos)&posStateMask);
229
230 prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
231 IfBit0(prob) {
232 int symbol = 1;
233 UpdateBit0(prob);
234 prob = p + Literal + (LZMA_LIT_SIZE *
235 ((((nowPos) & literalPosMask) << lc)
236 + (previousByte >> (8 - lc))));
237
238 if (state >= kNumLitStates) {
239 int matchByte;
240 matchByte = outStream[nowPos - rep0];
241 do {
242 int bit;
243 CProb *probLit;
244 matchByte <<= 1;
245 bit = (matchByte & 0x100);
246 probLit = prob + 0x100 + bit + symbol;
247 RC_GET_BIT2(probLit, symbol,
248 if (bit != 0)
249 break,
250 if (bit == 0)
251 break)
252 } while (symbol < 0x100);
253 }
254 while (symbol < 0x100) {
255 CProb *probLit = prob + symbol;
256 RC_GET_BIT(probLit, symbol)
257 }
258 previousByte = (Byte)symbol;
259
260 outStream[nowPos++] = previousByte;
261 if (state < 4)
262 state = 0;
263 else if (state < 10)
264 state -= 3;
265 else
266 state -= 6;
267 } else {
268 UpdateBit1(prob);
269 prob = p + IsRep + state;
270 IfBit0(prob) {
271 UpdateBit0(prob);
272 rep3 = rep2;
273 rep2 = rep1;
274 rep1 = rep0;
275 state = state < kNumLitStates ? 0 : 3;
276 prob = p + LenCoder;
277 } else {
278 UpdateBit1(prob);
279 prob = p + IsRepG0 + state;
280 IfBit0(prob) {
281 UpdateBit0(prob);
282 prob = p + IsRep0Long
283 + (state << kNumPosBitsMax)
284 + posState;
285 IfBit0(prob) {
286 UpdateBit0(prob);
287
288 if (nowPos == 0)
289 return LZMA_RESULT_DATA_ERROR;
290
291 state = state < kNumLitStates
292 ? 9 : 11;
293 previousByte = outStream[nowPos
294 - rep0];
295 outStream[nowPos++] =
296 previousByte;
297
298 continue;
299 } else
300 UpdateBit1(prob);
301 } else {
302 UInt32 distance;
303 UpdateBit1(prob);
304 prob = p + IsRepG1 + state;
305 IfBit0(prob) {
306 UpdateBit0(prob);
307 distance = rep1;
308 } else {
309 UpdateBit1(prob);
310 prob = p + IsRepG2 + state;
311 IfBit0(prob) {
312 UpdateBit0(prob);
313 distance = rep2;
314 } else {
315 UpdateBit1(prob);
316 distance = rep3;
317 rep3 = rep2;
318 }
319 rep2 = rep1;
320 }
321 rep1 = rep0;
322 rep0 = distance;
323 }
324 state = state < kNumLitStates ? 8 : 11;
325 prob = p + RepLenCoder;
326 }
327 {
328 int numBits, offset;
329 CProb *probLen = prob + LenChoice;
330 IfBit0(probLen) {
331 UpdateBit0(probLen);
332 probLen = prob + LenLow
333 + (posState << kLenNumLowBits);
334 offset = 0;
335 numBits = kLenNumLowBits;
336 } else {
337 UpdateBit1(probLen);
338 probLen = prob + LenChoice2;
339 IfBit0(probLen) {
340 UpdateBit0(probLen);
341 probLen = prob + LenMid
342 + (posState <<
343 kLenNumMidBits);
344 offset = kLenNumLowSymbols;
345 numBits = kLenNumMidBits;
346 } else {
347 UpdateBit1(probLen);
348 probLen = prob + LenHigh;
349 offset = kLenNumLowSymbols
350 + kLenNumMidSymbols;
351 numBits = kLenNumHighBits;
352 }
353 }
354 RangeDecoderBitTreeDecode(probLen, numBits,
355 len);
356 len += offset;
357 }
358
359 if (state < 4) {
360 int posSlot;
361 state += kNumLitStates;
362 prob = p + PosSlot +
363 ((len < kNumLenToPosStates ? len :
364 kNumLenToPosStates - 1) <<
365 kNumPosSlotBits);
366 RangeDecoderBitTreeDecode(prob, kNumPosSlotBits,
367 posSlot);
368 if (posSlot >= kStartPosModelIndex) {
369 int numDirectBits = ((posSlot >> 1)
370 - 1);
371 rep0 = (2 | ((UInt32)posSlot & 1));
372 if (posSlot < kEndPosModelIndex) {
373 rep0 <<= numDirectBits;
374 prob = p + SpecPos + rep0
375 - posSlot - 1;
376 } else {
377 numDirectBits -= kNumAlignBits;
378 do {
379 RC_NORMALIZE
380 Range >>= 1;
381 rep0 <<= 1;
382 if (Code >= Range) {
383 Code -= Range;
384 rep0 |= 1;
385 }
386 } while (--numDirectBits != 0);
387 prob = p + Align;
388 rep0 <<= kNumAlignBits;
389 numDirectBits = kNumAlignBits;
390 }
391 {
392 int i = 1;
393 int mi = 1;
394 do {
395 CProb *prob3 = prob
396 + mi;
397 RC_GET_BIT2(prob3, mi,
398 ;, rep0 |= i);
399 i <<= 1;
400 } while (--numDirectBits != 0);
401 }
402 } else
403 rep0 = posSlot;
404 if (++rep0 == (UInt32)(0)) {
405 /* it's for stream version */
406 len = kLzmaStreamWasFinishedId;
407 break;
408 }
409 }
410
411 len += kMatchMinLen;
412 if (rep0 > nowPos)
413 return LZMA_RESULT_DATA_ERROR;
414
415
416 do {
417 previousByte = outStream[nowPos - rep0];
418 len--;
419 outStream[nowPos++] = previousByte;
420 } while (len != 0 && nowPos < outSize);
421 }
422 }
423 RC_NORMALIZE;
424
425
426 *inSizeProcessed = (SizeT)(Buffer - inStream);
427 *outSizeProcessed = nowPos;
428 return LZMA_RESULT_OK;
429 }
ast, secure and flexible OpenSource firmware