LzmaDecode.c

Revision 12370, 15.4 kB (checked in by BrainSlayer, 5 months ago)
support for senao firmware format
Property svn:executable set to ``*

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

Note: See TracBrowser for help on using the browser.

root/ar5315_microredboot/microredboot/boot/src/lib/LzmaDecode.c

Download in other formats: