LzmaDecode.c

Revision 12325, 15.4 kB (checked in by BrainSlayer, 5 months ago)
increase lzma decoder speed by 2
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,;, symbol \|= (1 << i))
171	#else
172	int bit = RangeDecoderBitDecode(probs + mi, rd);
173	mi = mi + mi + bit;
174	symbol \|= (bit << i);
175	#endif
176	}
177	#ifdef _LZMA_LOC_OPT
178	RC_FLUSH_VAR
179	#endif
180	return symbol;
181	}
182
183	static Byte inline LzmaLiteralDecode(CProb * probs, CRangeDecoder * rd)
184	{
185	int symbol = 1;
186	#ifdef _LZMA_LOC_OPT
187	RC_INIT_VAR
188	#endif
189	do {
190	#ifdef _LZMA_LOC_OPT
191	CProb *prob = probs + symbol;
192	RC_GET_BIT(prob, symbol)
193	#else
194	symbol =
195	(symbol + symbol) \| RangeDecoderBitDecode(probs + symbol,
196	rd);
197	#endif
198	}
199	while (symbol < 0x100);
200	#ifdef _LZMA_LOC_OPT
201	RC_FLUSH_VAR
202	#endif
203	return symbol;
204	}
205
206	static inline Byte LzmaLiteralDecodeMatch(CProb * probs, CRangeDecoder * rd,
207	Byte matchByte)
208	{
209	int symbol = 1;
210	#ifdef _LZMA_LOC_OPT
211	RC_INIT_VAR
212	#endif
213	do {
214	int bit;
215	int matchBit = (matchByte >> 7) & 1;
216	matchByte <<= 1;
217	#ifdef _LZMA_LOC_OPT
218	{
219	CProb *prob = probs + ((1 + matchBit) << 8) + symbol;
220	RC_GET_BIT2(prob, symbol, bit = 0, bit = 1)
221	}
222	#else
223	bit =
224	RangeDecoderBitDecode(probs + ((1 + matchBit) << 8) +
225	symbol, rd);
226	symbol = (symbol << 1) \| bit;
227	#endif
228	if (matchBit != bit) {
229	while (symbol < 0x100) {
230	#ifdef _LZMA_LOC_OPT
231	CProb *prob = probs + symbol;
232	RC_GET_BIT(prob, symbol)
233	#else
234	symbol =
235	(symbol +
236	symbol) \| RangeDecoderBitDecode(probs +
237	symbol,
238	rd);
239	#endif
240	}
241	break;
242	}
243	}
244	while (symbol < 0x100);
245	#ifdef _LZMA_LOC_OPT
246	RC_FLUSH_VAR
247	#endif
248	return symbol;
249	}
250
251	#define kNumPosBitsMax 4
252	#define kNumPosStatesMax (1 << kNumPosBitsMax)
253
254	#define kLenNumLowBits 3
255	#define kLenNumLowSymbols (1 << kLenNumLowBits)
256	#define kLenNumMidBits 3
257	#define kLenNumMidSymbols (1 << kLenNumMidBits)
258	#define kLenNumHighBits 8
259	#define kLenNumHighSymbols (1 << kLenNumHighBits)
260
261	#define LenChoice 0
262	#define LenChoice2 (LenChoice + 1)
263	#define LenLow (LenChoice2 + 1)
264	#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
265	#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
266	#define kNumLenProbs (LenHigh + kLenNumHighSymbols)
267
268	static inline int LzmaLenDecode(CProb * p, CRangeDecoder * rd, int posState)
269	{
270	if (RangeDecoderBitDecode(p + LenChoice, rd) == 0)
271	return RangeDecoderBitTreeDecode(p + LenLow +
272	(posState << kLenNumLowBits),
273	kLenNumLowBits, rd);
274	if (RangeDecoderBitDecode(p + LenChoice2, rd) == 0)
275	return kLenNumLowSymbols + RangeDecoderBitTreeDecode(p +
276	LenMid +
277	(posState
278	<<
279	kLenNumMidBits),
280	kLenNumMidBits,
281	rd);
282	return kLenNumLowSymbols + kLenNumMidSymbols +
283	RangeDecoderBitTreeDecode(p + LenHigh, kLenNumHighBits, rd);
284	}
285
286	#define kNumStates 12
287
288	#define kStartPosModelIndex 4
289	#define kEndPosModelIndex 14
290	#define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
291
292	#define kNumPosSlotBits 6
293	#define kNumLenToPosStates 4
294
295	#define kNumAlignBits 4
296	#define kAlignTableSize (1 << kNumAlignBits)
297
298	#define kMatchMinLen 2
299
300	#define IsMatch 0
301	#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
302	#define IsRepG0 (IsRep + kNumStates)
303	#define IsRepG1 (IsRepG0 + kNumStates)
304	#define IsRepG2 (IsRepG1 + kNumStates)
305	#define IsRep0Long (IsRepG2 + kNumStates)
306	#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
307	#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
308	#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
309	#define LenCoder (Align + kAlignTableSize)
310	#define RepLenCoder (LenCoder + kNumLenProbs)
311	#define Literal (RepLenCoder + kNumLenProbs)
312
313	#if Literal != LZMA_BASE_SIZE
314	StopCompilingDueBUG
315	#endif
316	#ifdef _LZMA_OUT_READ
317	typedef struct _LzmaVarState {
318	CRangeDecoder RangeDecoder;
319	Byte *Dictionary;
320	UInt32 DictionarySize;
321	UInt32 DictionaryPos;
322	UInt32 GlobalPos;
323	UInt32 Reps[4];
324	int lc;
325	int lp;
326	int pb;
327	int State;
328	int PreviousIsMatch;
329	int RemainLen;
330	} LzmaVarState;
331
332	static int LzmaDecoderInit(unsigned char *buffer, UInt32 bufferSize,
333	int lc, int lp, int pb,
334	unsigned char *dictionary, UInt32 dictionarySize,)
335	{
336	LzmaVarState vs = (LzmaVarState ) buffer;
337	CProb p = (CProb ) (buffer + sizeof(LzmaVarState));
338	UInt32 numProbs = Literal + ((UInt32) LZMA_LIT_SIZE << (lc + lp));
339	UInt32 i;
340	if (bufferSize < numProbs * sizeof(CProb) + sizeof(LzmaVarState))
341	return LZMA_RESULT_NOT_ENOUGH_MEM;
342	vs->Dictionary = dictionary;
343	vs->DictionarySize = dictionarySize;
344	vs->DictionaryPos = 0;
345	vs->GlobalPos = 0;
346	vs->Reps[0] = vs->Reps[1] = vs->Reps[2] = vs->Reps[3] = 1;
347	vs->lc = lc;
348	vs->lp = lp;
349	vs->pb = pb;
350	vs->State = 0;
351	vs->PreviousIsMatch = 0;
352	vs->RemainLen = 0;
353	dictionary[dictionarySize - 1] = 0;
354	for (i = 0; i < numProbs; i++)
355	p[i] = kBitModelTotal >> 1;
356	RangeDecoderInit(&vs->RangeDecoder,);
357	return LZMA_RESULT_OK;
358	}
359
360	int LzmaDecode(unsigned char *buffer,
361	unsigned char *outStream, UInt32 outSize,
362	UInt32 * outSizeProcessed)
363	{
364	LzmaVarState vs = (LzmaVarState ) buffer;
365	CProb p = (CProb ) (buffer + sizeof(LzmaVarState));
366	CRangeDecoder rd = vs->RangeDecoder;
367	int state = vs->State;
368	int previousIsMatch = vs->PreviousIsMatch;
369	Byte previousByte;
370	UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 =
371	vs->Reps[2], rep3 = vs->Reps[3];
372	UInt32 nowPos = 0;
373	UInt32 posStateMask = (1 << (vs->pb)) - 1;
374	UInt32 literalPosMask = (1 << (vs->lp)) - 1;
375	int lc = vs->lc;
376	int len = vs->RemainLen;
377	UInt32 globalPos = vs->GlobalPos;
378
379	Byte *dictionary = vs->Dictionary;
380	UInt32 dictionarySize = vs->DictionarySize;
381	UInt32 dictionaryPos = vs->DictionaryPos;
382
383	if (len == -1) {
384	*outSizeProcessed = 0;
385	return LZMA_RESULT_OK;
386	}
387
388	while (len > 0 && nowPos < outSize) {
389	UInt32 pos = dictionaryPos - rep0;
390	if (pos >= dictionarySize)
391	pos += dictionarySize;
392	outStream[nowPos++] = dictionary[dictionaryPos] =
393	dictionary[pos];
394	if (++dictionaryPos == dictionarySize)
395	dictionaryPos = 0;
396	len--;
397	}
398	if (dictionaryPos == 0)
399	previousByte = dictionary[dictionarySize - 1];
400	else
401	previousByte = dictionary[dictionaryPos - 1];
402	#else
403	static int LzmaDecode(Byte * buffer, UInt32 bufferSize,
404	int lc, int lp, int pb,
405	unsigned char *outStream, UInt32 outSize,
406	UInt32 * outSizeProcessed)
407	{
408	UInt32 numProbs = Literal + ((UInt32) LZMA_LIT_SIZE << (lc + lp));
409	CProb p = (CProb ) buffer;
410	CRangeDecoder rd;
411	UInt32 i;
412	int state = 0;
413	int previousIsMatch = 0;
414	Byte previousByte = 0;
415	UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
416	UInt32 nowPos = 0;
417	UInt32 posStateMask = (1 << pb) - 1;
418	UInt32 literalPosMask = (1 << lp) - 1;
419	int len = 0;
420	if (bufferSize < numProbs * sizeof(CProb))
421	return LZMA_RESULT_NOT_ENOUGH_MEM;
422	for (i = 0; i < numProbs; i++)
423	p[i] = kBitModelTotal >> 1;
424	RangeDecoderInit(&rd);
425	#endif
426
427	*outSizeProcessed = 0;
428	while (nowPos < outSize) {
429	int posState = (int)((nowPos
430	#ifdef _LZMA_OUT_READ
431	+ globalPos
432	#endif
433	)
434	& posStateMask);
435	#ifdef _LZMA_IN_CB
436	if (rd.Result != LZMA_RESULT_OK)
437	return rd.Result;
438	#endif
439	if (RangeDecoderBitDecode
440	(p + IsMatch + (state << kNumPosBitsMax) + posState,
441	&rd) == 0) {
442	CProb probs = p + Literal + (LZMA_LIT_SIZE ((((nowPos
443	#ifdef _LZMA_OUT_READ
444	+
445	globalPos
446	#endif
447	)
448	&
449	literalPosMask)
450	<< lc) +
451	(previousByte
452	>> (8 -
453	lc))));
454
455	if (state < 4)
456	state = 0;
457	else if (state < 10)
458	state -= 3;
459	else
460	state -= 6;
461	if (previousIsMatch) {
462	Byte matchByte;
463	#ifdef _LZMA_OUT_READ
464	UInt32 pos = dictionaryPos - rep0;
465	if (pos >= dictionarySize)
466	pos += dictionarySize;
467	matchByte = dictionary[pos];
468	#else
469	matchByte = outStream[nowPos - rep0];
470	#endif
471	previousByte =
472	LzmaLiteralDecodeMatch(probs, &rd,
473	matchByte);
474	previousIsMatch = 0;
475	} else
476	previousByte = LzmaLiteralDecode(probs, &rd);
477	outStream[nowPos++] = previousByte;
478	#ifdef _LZMA_OUT_READ
479	dictionary[dictionaryPos] = previousByte;
480	if (++dictionaryPos == dictionarySize)
481	dictionaryPos = 0;
482	#endif
483	} else {
484	previousIsMatch = 1;
485	if (RangeDecoderBitDecode(p + IsRep + state, &rd) == 1) {
486	if (RangeDecoderBitDecode
487	(p + IsRepG0 + state, &rd) == 0) {
488	if (RangeDecoderBitDecode
489	(p + IsRep0Long +
490	(state << kNumPosBitsMax) +
491	posState, &rd) == 0) {
492	#ifdef _LZMA_OUT_READ
493	UInt32 pos;
494	#endif
495	if ((nowPos
496	#ifdef _LZMA_OUT_READ
497	+ globalPos
498	#endif
499	)
500	== 0)
501	return
502	LZMA_RESULT_DATA_ERROR;
503	state = state < 7 ? 9 : 11;
504	#ifdef _LZMA_OUT_READ
505	pos = dictionaryPos - rep0;
506	if (pos >= dictionarySize)
507	pos += dictionarySize;
508	previousByte = dictionary[pos];
509	dictionary[dictionaryPos] =
510	previousByte;
511	if (++dictionaryPos ==
512	dictionarySize)
513	dictionaryPos = 0;
514	#else
515	previousByte =
516	outStream[nowPos - rep0];
517	#endif
518	outStream[nowPos++] =
519	previousByte;
520	continue;
521	}
522	} else {
523	UInt32 distance;
524	if (RangeDecoderBitDecode
525	(p + IsRepG1 + state, &rd) == 0)
526	distance = rep1;
527	else {
528	if (RangeDecoderBitDecode
529	(p + IsRepG2 + state,
530	&rd) == 0)
531	distance = rep2;
532	else {
533	distance = rep3;
534	rep3 = rep2;
535	}
536	rep2 = rep1;
537	}
538	rep1 = rep0;
539	rep0 = distance;
540	}
541	len =
542	LzmaLenDecode(p + RepLenCoder, &rd,
543	posState);
544	state = state < 7 ? 8 : 11;
545	} else {
546	int posSlot;
547	rep3 = rep2;
548	rep2 = rep1;
549	rep1 = rep0;
550	state = state < 7 ? 7 : 10;
551	len =
552	LzmaLenDecode(p + LenCoder, &rd, posState);
553	posSlot =
554	RangeDecoderBitTreeDecode(p + PosSlot +
555	((len <
556	kNumLenToPosStates
557	? len :
558	kNumLenToPosStates
559	-
560	1) <<
561	kNumPosSlotBits),
562	kNumPosSlotBits,
563	&rd);
564	if (posSlot >= kStartPosModelIndex) {
565	int numDirectBits =
566	((posSlot >> 1) - 1);
567	rep0 =
568	((2 \| ((UInt32) posSlot & 1)) <<
569	numDirectBits);
570	if (posSlot < kEndPosModelIndex) {
571	rep0 +=
572	RangeDecoderReverseBitTreeDecode
573	(p + SpecPos + rep0 -
574	posSlot - 1, numDirectBits,
575	&rd);
576	} else {
577	rep0 +=
578	RangeDecoderDecodeDirectBits
579	(&rd,
580	numDirectBits -
581	kNumAlignBits) <<
582	kNumAlignBits;
583	rep0 +=
584	RangeDecoderReverseBitTreeDecode
585	(p + Align, kNumAlignBits,
586	&rd);
587	}
588	} else
589	rep0 = posSlot;
590	rep0++;
591	}
592	if (rep0 == (UInt32) (0)) {
593	/* it's for stream version */
594	len = -1;
595	break;
596	}
597	if (rep0 > nowPos
598	#ifdef _LZMA_OUT_READ
599	+ globalPos
600	#endif
601	) {
602	return LZMA_RESULT_DATA_ERROR;
603	}
604	len += kMatchMinLen;
605	do {
606	#ifdef _LZMA_OUT_READ
607	UInt32 pos = dictionaryPos - rep0;
608	if (pos >= dictionarySize)
609	pos += dictionarySize;
610	previousByte = dictionary[pos];
611	dictionary[dictionaryPos] = previousByte;
612	if (++dictionaryPos == dictionarySize)
613	dictionaryPos = 0;
614	#else
615	previousByte = outStream[nowPos - rep0];
616	#endif
617	outStream[nowPos++] = previousByte;
618	len--;
619	}
620	while (len > 0 && nowPos < outSize);
621	}
622	}
623
624	#ifdef _LZMA_OUT_READ
625	vs->RangeDecoder = rd;
626	vs->DictionaryPos = dictionaryPos;
627	vs->GlobalPos = globalPos + nowPos;
628	vs->Reps[0] = rep0;
629	vs->Reps[1] = rep1;
630	vs->Reps[2] = rep2;
631	vs->Reps[3] = rep3;
632	vs->State = state;
633	vs->PreviousIsMatch = previousIsMatch;
634	vs->RemainLen = len;
635	#endif
636
637	*outSizeProcessed = nowPos;
638	return LZMA_RESULT_OK;
639	}

Note: See TracBrowser for help on using the browser.

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

Download in other formats: