OpenWrt – Blame information for rev 4

Subversion Repositories:
Rev:
Rev Author Line No. Line
4 office 1 /*
2 LzmaDecode.c
3 LZMA Decoder (optimized for Speed version)
4  
5 LZMA SDK 4.22 Copyright (c) 1999-2005 Igor Pavlov (2005-06-10)
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  
24 #ifndef Byte
25 #define Byte unsigned char
26 #endif
27  
28 #define kNumTopBits 24
29 #define kTopValue ((UInt32)1 << kNumTopBits)
30  
31 #define kNumBitModelTotalBits 11
32 #define kBitModelTotal (1 << kNumBitModelTotalBits)
33 #define kNumMoveBits 5
34  
35 #define RC_READ_BYTE (*Buffer++)
36  
37 #define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \
38 { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }}
39  
40 #ifdef _LZMA_IN_CB
41  
42 #define RC_TEST { if (Buffer == BufferLim) \
43 { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) return result; \
44 BufferLim = Buffer + size; if (size == 0) return LZMA_RESULT_DATA_ERROR; }}
45  
46 #define RC_INIT Buffer = BufferLim = 0; RC_INIT2
47  
48 #else
49  
50 #define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
51  
52 #define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
53  
54 #endif
55  
56 #define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
57  
58 #define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)
59 #define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;
60 #define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;
61  
62 #define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \
63 { UpdateBit0(p); mi <<= 1; A0; } else \
64 { UpdateBit1(p); mi = (mi + mi) + 1; A1; }
65  
66 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
67  
68 #define RangeDecoderBitTreeDecode(probs, numLevels, res) \
69 { int i = numLevels; res = 1; \
70 do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \
71 res -= (1 << numLevels); }
72  
73  
74 #define kNumPosBitsMax 4
75 #define kNumPosStatesMax (1 << kNumPosBitsMax)
76  
77 #define kLenNumLowBits 3
78 #define kLenNumLowSymbols (1 << kLenNumLowBits)
79 #define kLenNumMidBits 3
80 #define kLenNumMidSymbols (1 << kLenNumMidBits)
81 #define kLenNumHighBits 8
82 #define kLenNumHighSymbols (1 << kLenNumHighBits)
83  
84 #define LenChoice 0
85 #define LenChoice2 (LenChoice + 1)
86 #define LenLow (LenChoice2 + 1)
87 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
88 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
89 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
90  
91  
92 #define kNumStates 12
93 #define kNumLitStates 7
94  
95 #define kStartPosModelIndex 4
96 #define kEndPosModelIndex 14
97 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
98  
99 #define kNumPosSlotBits 6
100 #define kNumLenToPosStates 4
101  
102 #define kNumAlignBits 4
103 #define kAlignTableSize (1 << kNumAlignBits)
104  
105 #define kMatchMinLen 2
106  
107 #define IsMatch 0
108 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
109 #define IsRepG0 (IsRep + kNumStates)
110 #define IsRepG1 (IsRepG0 + kNumStates)
111 #define IsRepG2 (IsRepG1 + kNumStates)
112 #define IsRep0Long (IsRepG2 + kNumStates)
113 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
114 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
115 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
116 #define LenCoder (Align + kAlignTableSize)
117 #define RepLenCoder (LenCoder + kNumLenProbs)
118 #define Literal (RepLenCoder + kNumLenProbs)
119  
120 #if Literal != LZMA_BASE_SIZE
121 StopCompilingDueBUG
122 #endif
123  
124 #if 0
125 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
126 {
127 unsigned char prop0;
128 if (size < LZMA_PROPERTIES_SIZE)
129 return LZMA_RESULT_DATA_ERROR;
130 prop0 = propsData[0];
131 if (prop0 >= (9 * 5 * 5))
132 return LZMA_RESULT_DATA_ERROR;
133 {
134 for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
135 for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
136 propsRes->lc = prop0;
137 /*
138 unsigned char remainder = (unsigned char)(prop0 / 9);
139 propsRes->lc = prop0 % 9;
140 propsRes->pb = remainder / 5;
141 propsRes->lp = remainder % 5;
142 */
143 }
144  
145 #ifdef _LZMA_OUT_READ
146 {
147 int i;
148 propsRes->DictionarySize = 0;
149 for (i = 0; i < 4; i++)
150 propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);
151 if (propsRes->DictionarySize == 0)
152 propsRes->DictionarySize = 1;
153 }
154 #endif
155 return LZMA_RESULT_OK;
156 }
157 #endif
158  
159 #define kLzmaStreamWasFinishedId (-1)
160  
161 int LzmaDecode(CLzmaDecoderState *vs,
162 #ifdef _LZMA_IN_CB
163 ILzmaInCallback *InCallback,
164 #else
165 const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
166 #endif
167 unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
168 {
169 CProb *p = vs->Probs;
170 SizeT nowPos = 0;
171 Byte previousByte = 0;
172 UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
173 UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
174 int lc = vs->Properties.lc;
175  
176 #ifdef _LZMA_OUT_READ
177  
178 UInt32 Range = vs->Range;
179 UInt32 Code = vs->Code;
180 #ifdef _LZMA_IN_CB
181 const Byte *Buffer = vs->Buffer;
182 const Byte *BufferLim = vs->BufferLim;
183 #else
184 const Byte *Buffer = inStream;
185 const Byte *BufferLim = inStream + inSize;
186 #endif
187 int state = vs->State;
188 UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
189 int len = vs->RemainLen;
190 UInt32 globalPos = vs->GlobalPos;
191 UInt32 distanceLimit = vs->DistanceLimit;
192  
193 Byte *dictionary = vs->Dictionary;
194 UInt32 dictionarySize = vs->Properties.DictionarySize;
195 UInt32 dictionaryPos = vs->DictionaryPos;
196  
197 Byte tempDictionary[4];
198  
199 #ifndef _LZMA_IN_CB
200 *inSizeProcessed = 0;
201 #endif
202 *outSizeProcessed = 0;
203 if (len == kLzmaStreamWasFinishedId)
204 return LZMA_RESULT_OK;
205  
206 if (dictionarySize == 0)
207 {
208 dictionary = tempDictionary;
209 dictionarySize = 1;
210 tempDictionary[0] = vs->TempDictionary[0];
211 }
212  
213 if (len == kLzmaNeedInitId)
214 {
215 {
216 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
217 UInt32 i;
218 for (i = 0; i < numProbs; i++)
219 p[i] = kBitModelTotal >> 1;
220 rep0 = rep1 = rep2 = rep3 = 1;
221 state = 0;
222 globalPos = 0;
223 distanceLimit = 0;
224 dictionaryPos = 0;
225 dictionary[dictionarySize - 1] = 0;
226 #ifdef _LZMA_IN_CB
227 RC_INIT;
228 #else
229 RC_INIT(inStream, inSize);
230 #endif
231 }
232 len = 0;
233 }
234 while(len != 0 && nowPos < outSize)
235 {
236 UInt32 pos = dictionaryPos - rep0;
237 if (pos >= dictionarySize)
238 pos += dictionarySize;
239 outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
240 if (++dictionaryPos == dictionarySize)
241 dictionaryPos = 0;
242 len--;
243 }
244 if (dictionaryPos == 0)
245 previousByte = dictionary[dictionarySize - 1];
246 else
247 previousByte = dictionary[dictionaryPos - 1];
248  
249 #else /* if !_LZMA_OUT_READ */
250  
251 int state = 0;
252 UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
253 int len = 0;
254 const Byte *Buffer;
255 const Byte *BufferLim;
256 UInt32 Range;
257 UInt32 Code;
258  
259 #ifndef _LZMA_IN_CB
260 *inSizeProcessed = 0;
261 #endif
262 *outSizeProcessed = 0;
263  
264 {
265 UInt32 i;
266 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
267 for (i = 0; i < numProbs; i++)
268 p[i] = kBitModelTotal >> 1;
269 }
270  
271 #ifdef _LZMA_IN_CB
272 RC_INIT;
273 #else
274 RC_INIT(inStream, inSize);
275 #endif
276  
277 #endif /* _LZMA_OUT_READ */
278  
279 while(nowPos < outSize)
280 {
281 CProb *prob;
282 UInt32 bound;
283 int posState = (int)(
284 (nowPos
285 #ifdef _LZMA_OUT_READ
286 + globalPos
287 #endif
288 )
289 & posStateMask);
290  
291 prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
292 IfBit0(prob)
293 {
294 int symbol = 1;
295 UpdateBit0(prob)
296 prob = p + Literal + (LZMA_LIT_SIZE *
297 (((
298 (nowPos
299 #ifdef _LZMA_OUT_READ
300 + globalPos
301 #endif
302 )
303 & literalPosMask) << lc) + (previousByte >> (8 - lc))));
304  
305 if (state >= kNumLitStates)
306 {
307 int matchByte;
308 #ifdef _LZMA_OUT_READ
309 UInt32 pos = dictionaryPos - rep0;
310 if (pos >= dictionarySize)
311 pos += dictionarySize;
312 matchByte = dictionary[pos];
313 #else
314 matchByte = outStream[nowPos - rep0];
315 #endif
316 do
317 {
318 int bit;
319 CProb *probLit;
320 matchByte <<= 1;
321 bit = (matchByte & 0x100);
322 probLit = prob + 0x100 + bit + symbol;
323 RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
324 }
325 while (symbol < 0x100);
326 }
327 while (symbol < 0x100)
328 {
329 CProb *probLit = prob + symbol;
330 RC_GET_BIT(probLit, symbol)
331 }
332 previousByte = (Byte)symbol;
333  
334 outStream[nowPos++] = previousByte;
335 #ifdef _LZMA_OUT_READ
336 if (distanceLimit < dictionarySize)
337 distanceLimit++;
338  
339 dictionary[dictionaryPos] = previousByte;
340 if (++dictionaryPos == dictionarySize)
341 dictionaryPos = 0;
342 #endif
343 if (state < 4) state = 0;
344 else if (state < 10) state -= 3;
345 else state -= 6;
346 }
347 else
348 {
349 UpdateBit1(prob);
350 prob = p + IsRep + state;
351 IfBit0(prob)
352 {
353 UpdateBit0(prob);
354 rep3 = rep2;
355 rep2 = rep1;
356 rep1 = rep0;
357 state = state < kNumLitStates ? 0 : 3;
358 prob = p + LenCoder;
359 }
360 else
361 {
362 UpdateBit1(prob);
363 prob = p + IsRepG0 + state;
364 IfBit0(prob)
365 {
366 UpdateBit0(prob);
367 prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
368 IfBit0(prob)
369 {
370 #ifdef _LZMA_OUT_READ
371 UInt32 pos;
372 #endif
373 UpdateBit0(prob);
374  
375 #ifdef _LZMA_OUT_READ
376 if (distanceLimit == 0)
377 #else
378 if (nowPos == 0)
379 #endif
380 return LZMA_RESULT_DATA_ERROR;
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 return LZMA_RESULT_DATA_ERROR;
538  
539 #ifdef _LZMA_OUT_READ
540 if (dictionarySize - distanceLimit > (UInt32)len)
541 distanceLimit += len;
542 else
543 distanceLimit = dictionarySize;
544 #endif
545  
546 do
547 {
548 #ifdef _LZMA_OUT_READ
549 UInt32 pos = dictionaryPos - rep0;
550 if (pos >= dictionarySize)
551 pos += dictionarySize;
552 previousByte = dictionary[pos];
553 dictionary[dictionaryPos] = previousByte;
554 if (++dictionaryPos == dictionarySize)
555 dictionaryPos = 0;
556 #else
557 previousByte = outStream[nowPos - rep0];
558 #endif
559 len--;
560 outStream[nowPos++] = previousByte;
561 }
562 while(len != 0 && nowPos < outSize);
563 }
564 }
565 RC_NORMALIZE;
566  
567 #ifdef _LZMA_OUT_READ
568 vs->Range = Range;
569 vs->Code = Code;
570 vs->DictionaryPos = dictionaryPos;
571 vs->GlobalPos = globalPos + (UInt32)nowPos;
572 vs->DistanceLimit = distanceLimit;
573 vs->Reps[0] = rep0;
574 vs->Reps[1] = rep1;
575 vs->Reps[2] = rep2;
576 vs->Reps[3] = rep3;
577 vs->State = state;
578 vs->RemainLen = len;
579 vs->TempDictionary[0] = tempDictionary[0];
580 #endif
581  
582 #ifdef _LZMA_IN_CB
583 vs->Buffer = Buffer;
584 vs->BufferLim = BufferLim;
585 #else
586 *inSizeProcessed = (SizeT)(Buffer - inStream);
587 #endif
588 *outSizeProcessed = nowPos;
589 return LZMA_RESULT_OK;
590 }