1ca3e8d88SDave Plauger
2ca3e8d88SDave Plauger /*-------------------------------------------------------------*/
3ca3e8d88SDave Plauger /*--- Decompression machinery ---*/
4ca3e8d88SDave Plauger /*--- decompress.c ---*/
5ca3e8d88SDave Plauger /*-------------------------------------------------------------*/
6ca3e8d88SDave Plauger
7ca3e8d88SDave Plauger /* ------------------------------------------------------------------
8ca3e8d88SDave Plauger This file is part of bzip2/libbzip2, a program and library for
9ca3e8d88SDave Plauger lossless, block-sorting data compression.
10ca3e8d88SDave Plauger
11b9071c34SGordon Ross bzip2/libbzip2 version 1.0.6 of 6 September 2010
12b9071c34SGordon Ross Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
13ca3e8d88SDave Plauger
14*238e18a0SToomas Soome Please read the WARNING, DISCLAIMER and PATENTS sections in the
15ca3e8d88SDave Plauger README file.
16ca3e8d88SDave Plauger
17ca3e8d88SDave Plauger This program is released under the terms of the license contained
18ca3e8d88SDave Plauger in the file LICENSE.
19ca3e8d88SDave Plauger ------------------------------------------------------------------ */
20ca3e8d88SDave Plauger
21ca3e8d88SDave Plauger
22ca3e8d88SDave Plauger #include "bzlib_private.h"
23ca3e8d88SDave Plauger
24ca3e8d88SDave Plauger
25ca3e8d88SDave Plauger /*---------------------------------------------------*/
26ca3e8d88SDave Plauger static
makeMaps_d(DState * s)27ca3e8d88SDave Plauger void makeMaps_d ( DState* s )
28ca3e8d88SDave Plauger {
29ca3e8d88SDave Plauger Int32 i;
30ca3e8d88SDave Plauger s->nInUse = 0;
31ca3e8d88SDave Plauger for (i = 0; i < 256; i++)
32ca3e8d88SDave Plauger if (s->inUse[i]) {
33ca3e8d88SDave Plauger s->seqToUnseq[s->nInUse] = i;
34ca3e8d88SDave Plauger s->nInUse++;
35ca3e8d88SDave Plauger }
36ca3e8d88SDave Plauger }
37ca3e8d88SDave Plauger
38ca3e8d88SDave Plauger
39ca3e8d88SDave Plauger /*---------------------------------------------------*/
40ca3e8d88SDave Plauger #define RETURN(rrr) \
41ca3e8d88SDave Plauger { retVal = rrr; goto save_state_and_return; }
42ca3e8d88SDave Plauger
43ca3e8d88SDave Plauger #define GET_BITS(lll,vvv,nnn) \
44db044905SToomas Soome /* FALLTHROUGH */ \
45ca3e8d88SDave Plauger case lll: s->state = lll; \
46ca3e8d88SDave Plauger while (True) { \
47ca3e8d88SDave Plauger if (s->bsLive >= nnn) { \
48ca3e8d88SDave Plauger UInt32 v; \
49ca3e8d88SDave Plauger v = (s->bsBuff >> \
50ca3e8d88SDave Plauger (s->bsLive-nnn)) & ((1 << nnn)-1); \
51ca3e8d88SDave Plauger s->bsLive -= nnn; \
52ca3e8d88SDave Plauger vvv = v; \
53ca3e8d88SDave Plauger break; \
54ca3e8d88SDave Plauger } \
55ca3e8d88SDave Plauger if (s->strm->avail_in == 0) RETURN(BZ_OK); \
56ca3e8d88SDave Plauger s->bsBuff \
57ca3e8d88SDave Plauger = (s->bsBuff << 8) | \
58ca3e8d88SDave Plauger ((UInt32) \
59ca3e8d88SDave Plauger (*((UChar*)(s->strm->next_in)))); \
60ca3e8d88SDave Plauger s->bsLive += 8; \
61ca3e8d88SDave Plauger s->strm->next_in++; \
62ca3e8d88SDave Plauger s->strm->avail_in--; \
63ca3e8d88SDave Plauger s->strm->total_in_lo32++; \
64ca3e8d88SDave Plauger if (s->strm->total_in_lo32 == 0) \
65ca3e8d88SDave Plauger s->strm->total_in_hi32++; \
66ca3e8d88SDave Plauger }
67ca3e8d88SDave Plauger
68ca3e8d88SDave Plauger #define GET_UCHAR(lll,uuu) \
69ca3e8d88SDave Plauger GET_BITS(lll,uuu,8)
70ca3e8d88SDave Plauger
71ca3e8d88SDave Plauger #define GET_BIT(lll,uuu) \
72ca3e8d88SDave Plauger GET_BITS(lll,uuu,1)
73ca3e8d88SDave Plauger
74ca3e8d88SDave Plauger /*---------------------------------------------------*/
75ca3e8d88SDave Plauger #define GET_MTF_VAL(label1,label2,lval) \
76ca3e8d88SDave Plauger { \
77ca3e8d88SDave Plauger if (groupPos == 0) { \
78ca3e8d88SDave Plauger groupNo++; \
79ca3e8d88SDave Plauger if (groupNo >= nSelectors) \
80ca3e8d88SDave Plauger RETURN(BZ_DATA_ERROR); \
81ca3e8d88SDave Plauger groupPos = BZ_G_SIZE; \
82ca3e8d88SDave Plauger gSel = s->selector[groupNo]; \
83ca3e8d88SDave Plauger gMinlen = s->minLens[gSel]; \
84ca3e8d88SDave Plauger gLimit = &(s->limit[gSel][0]); \
85ca3e8d88SDave Plauger gPerm = &(s->perm[gSel][0]); \
86ca3e8d88SDave Plauger gBase = &(s->base[gSel][0]); \
87ca3e8d88SDave Plauger } \
88ca3e8d88SDave Plauger groupPos--; \
89ca3e8d88SDave Plauger zn = gMinlen; \
90ca3e8d88SDave Plauger GET_BITS(label1, zvec, zn); \
91ca3e8d88SDave Plauger while (1) { \
92ca3e8d88SDave Plauger if (zn > 20 /* the longest code */) \
93ca3e8d88SDave Plauger RETURN(BZ_DATA_ERROR); \
94ca3e8d88SDave Plauger if (zvec <= gLimit[zn]) break; \
95ca3e8d88SDave Plauger zn++; \
96ca3e8d88SDave Plauger GET_BIT(label2, zj); \
97ca3e8d88SDave Plauger zvec = (zvec << 1) | zj; \
98ca3e8d88SDave Plauger }; \
99ca3e8d88SDave Plauger if (zvec - gBase[zn] < 0 \
100ca3e8d88SDave Plauger || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \
101ca3e8d88SDave Plauger RETURN(BZ_DATA_ERROR); \
102ca3e8d88SDave Plauger lval = gPerm[zvec - gBase[zn]]; \
103ca3e8d88SDave Plauger }
104ca3e8d88SDave Plauger
105ca3e8d88SDave Plauger
106ca3e8d88SDave Plauger /*---------------------------------------------------*/
BZ2_decompress(DState * s)107ca3e8d88SDave Plauger Int32 BZ2_decompress ( DState* s )
108ca3e8d88SDave Plauger {
109ca3e8d88SDave Plauger UChar uc;
110ca3e8d88SDave Plauger Int32 retVal;
111ca3e8d88SDave Plauger Int32 minLen, maxLen;
112ca3e8d88SDave Plauger bz_stream* strm = s->strm;
113ca3e8d88SDave Plauger
114ca3e8d88SDave Plauger /* stuff that needs to be saved/restored */
115ca3e8d88SDave Plauger Int32 i;
116ca3e8d88SDave Plauger Int32 j;
117ca3e8d88SDave Plauger Int32 t;
118ca3e8d88SDave Plauger Int32 alphaSize;
119ca3e8d88SDave Plauger Int32 nGroups;
120ca3e8d88SDave Plauger Int32 nSelectors;
121ca3e8d88SDave Plauger Int32 EOB;
122ca3e8d88SDave Plauger Int32 groupNo;
123ca3e8d88SDave Plauger Int32 groupPos;
124ca3e8d88SDave Plauger Int32 nextSym;
125ca3e8d88SDave Plauger Int32 nblockMAX;
126ca3e8d88SDave Plauger Int32 nblock;
127ca3e8d88SDave Plauger Int32 es;
128ca3e8d88SDave Plauger Int32 N;
129ca3e8d88SDave Plauger Int32 curr;
130ca3e8d88SDave Plauger Int32 zt;
131*238e18a0SToomas Soome Int32 zn;
132ca3e8d88SDave Plauger Int32 zvec;
133ca3e8d88SDave Plauger Int32 zj;
134ca3e8d88SDave Plauger Int32 gSel;
135ca3e8d88SDave Plauger Int32 gMinlen;
136ca3e8d88SDave Plauger Int32* gLimit;
137ca3e8d88SDave Plauger Int32* gBase;
138ca3e8d88SDave Plauger Int32* gPerm;
139ca3e8d88SDave Plauger
140ca3e8d88SDave Plauger if (s->state == BZ_X_MAGIC_1) {
141ca3e8d88SDave Plauger /*initialise the save area*/
142ca3e8d88SDave Plauger s->save_i = 0;
143ca3e8d88SDave Plauger s->save_j = 0;
144ca3e8d88SDave Plauger s->save_t = 0;
145ca3e8d88SDave Plauger s->save_alphaSize = 0;
146ca3e8d88SDave Plauger s->save_nGroups = 0;
147ca3e8d88SDave Plauger s->save_nSelectors = 0;
148ca3e8d88SDave Plauger s->save_EOB = 0;
149ca3e8d88SDave Plauger s->save_groupNo = 0;
150ca3e8d88SDave Plauger s->save_groupPos = 0;
151ca3e8d88SDave Plauger s->save_nextSym = 0;
152ca3e8d88SDave Plauger s->save_nblockMAX = 0;
153ca3e8d88SDave Plauger s->save_nblock = 0;
154ca3e8d88SDave Plauger s->save_es = 0;
155ca3e8d88SDave Plauger s->save_N = 0;
156ca3e8d88SDave Plauger s->save_curr = 0;
157ca3e8d88SDave Plauger s->save_zt = 0;
158ca3e8d88SDave Plauger s->save_zn = 0;
159ca3e8d88SDave Plauger s->save_zvec = 0;
160ca3e8d88SDave Plauger s->save_zj = 0;
161ca3e8d88SDave Plauger s->save_gSel = 0;
162ca3e8d88SDave Plauger s->save_gMinlen = 0;
163ca3e8d88SDave Plauger s->save_gLimit = NULL;
164ca3e8d88SDave Plauger s->save_gBase = NULL;
165ca3e8d88SDave Plauger s->save_gPerm = NULL;
166ca3e8d88SDave Plauger }
167ca3e8d88SDave Plauger
168ca3e8d88SDave Plauger /*restore from the save area*/
169ca3e8d88SDave Plauger i = s->save_i;
170ca3e8d88SDave Plauger j = s->save_j;
171ca3e8d88SDave Plauger t = s->save_t;
172ca3e8d88SDave Plauger alphaSize = s->save_alphaSize;
173ca3e8d88SDave Plauger nGroups = s->save_nGroups;
174ca3e8d88SDave Plauger nSelectors = s->save_nSelectors;
175ca3e8d88SDave Plauger EOB = s->save_EOB;
176ca3e8d88SDave Plauger groupNo = s->save_groupNo;
177ca3e8d88SDave Plauger groupPos = s->save_groupPos;
178ca3e8d88SDave Plauger nextSym = s->save_nextSym;
179ca3e8d88SDave Plauger nblockMAX = s->save_nblockMAX;
180ca3e8d88SDave Plauger nblock = s->save_nblock;
181ca3e8d88SDave Plauger es = s->save_es;
182ca3e8d88SDave Plauger N = s->save_N;
183ca3e8d88SDave Plauger curr = s->save_curr;
184ca3e8d88SDave Plauger zt = s->save_zt;
185*238e18a0SToomas Soome zn = s->save_zn;
186ca3e8d88SDave Plauger zvec = s->save_zvec;
187ca3e8d88SDave Plauger zj = s->save_zj;
188ca3e8d88SDave Plauger gSel = s->save_gSel;
189ca3e8d88SDave Plauger gMinlen = s->save_gMinlen;
190ca3e8d88SDave Plauger gLimit = s->save_gLimit;
191ca3e8d88SDave Plauger gBase = s->save_gBase;
192ca3e8d88SDave Plauger gPerm = s->save_gPerm;
193ca3e8d88SDave Plauger
194ca3e8d88SDave Plauger retVal = BZ_OK;
195ca3e8d88SDave Plauger
196ca3e8d88SDave Plauger switch (s->state) {
197ca3e8d88SDave Plauger
198ca3e8d88SDave Plauger GET_UCHAR(BZ_X_MAGIC_1, uc);
199ca3e8d88SDave Plauger if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);
200ca3e8d88SDave Plauger
201ca3e8d88SDave Plauger GET_UCHAR(BZ_X_MAGIC_2, uc);
202ca3e8d88SDave Plauger if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);
203ca3e8d88SDave Plauger
204ca3e8d88SDave Plauger GET_UCHAR(BZ_X_MAGIC_3, uc)
205ca3e8d88SDave Plauger if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);
206ca3e8d88SDave Plauger
207ca3e8d88SDave Plauger GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
208*238e18a0SToomas Soome if (s->blockSize100k < (BZ_HDR_0 + 1) ||
209ca3e8d88SDave Plauger s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
210ca3e8d88SDave Plauger s->blockSize100k -= BZ_HDR_0;
211ca3e8d88SDave Plauger
212ca3e8d88SDave Plauger if (s->smallDecompress) {
213ca3e8d88SDave Plauger s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
214*238e18a0SToomas Soome s->ll4 = BZALLOC(
215*238e18a0SToomas Soome ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
216ca3e8d88SDave Plauger );
217ca3e8d88SDave Plauger if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
218ca3e8d88SDave Plauger } else {
219ca3e8d88SDave Plauger s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
220ca3e8d88SDave Plauger if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
221ca3e8d88SDave Plauger }
222ca3e8d88SDave Plauger
223ca3e8d88SDave Plauger GET_UCHAR(BZ_X_BLKHDR_1, uc);
224ca3e8d88SDave Plauger
225ca3e8d88SDave Plauger if (uc == 0x17) goto endhdr_2;
226ca3e8d88SDave Plauger if (uc != 0x31) RETURN(BZ_DATA_ERROR);
227ca3e8d88SDave Plauger GET_UCHAR(BZ_X_BLKHDR_2, uc);
228ca3e8d88SDave Plauger if (uc != 0x41) RETURN(BZ_DATA_ERROR);
229ca3e8d88SDave Plauger GET_UCHAR(BZ_X_BLKHDR_3, uc);
230ca3e8d88SDave Plauger if (uc != 0x59) RETURN(BZ_DATA_ERROR);
231ca3e8d88SDave Plauger GET_UCHAR(BZ_X_BLKHDR_4, uc);
232ca3e8d88SDave Plauger if (uc != 0x26) RETURN(BZ_DATA_ERROR);
233ca3e8d88SDave Plauger GET_UCHAR(BZ_X_BLKHDR_5, uc);
234ca3e8d88SDave Plauger if (uc != 0x53) RETURN(BZ_DATA_ERROR);
235ca3e8d88SDave Plauger GET_UCHAR(BZ_X_BLKHDR_6, uc);
236ca3e8d88SDave Plauger if (uc != 0x59) RETURN(BZ_DATA_ERROR);
237ca3e8d88SDave Plauger
238ca3e8d88SDave Plauger s->currBlockNo++;
239ca3e8d88SDave Plauger if (s->verbosity >= 2)
240ca3e8d88SDave Plauger VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo );
241*238e18a0SToomas Soome
242ca3e8d88SDave Plauger s->storedBlockCRC = 0;
243ca3e8d88SDave Plauger GET_UCHAR(BZ_X_BCRC_1, uc);
244ca3e8d88SDave Plauger s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
245ca3e8d88SDave Plauger GET_UCHAR(BZ_X_BCRC_2, uc);
246ca3e8d88SDave Plauger s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
247ca3e8d88SDave Plauger GET_UCHAR(BZ_X_BCRC_3, uc);
248ca3e8d88SDave Plauger s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
249ca3e8d88SDave Plauger GET_UCHAR(BZ_X_BCRC_4, uc);
250ca3e8d88SDave Plauger s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
251ca3e8d88SDave Plauger
252ca3e8d88SDave Plauger GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
253ca3e8d88SDave Plauger
254ca3e8d88SDave Plauger s->origPtr = 0;
255ca3e8d88SDave Plauger GET_UCHAR(BZ_X_ORIGPTR_1, uc);
256ca3e8d88SDave Plauger s->origPtr = (s->origPtr << 8) | ((Int32)uc);
257ca3e8d88SDave Plauger GET_UCHAR(BZ_X_ORIGPTR_2, uc);
258ca3e8d88SDave Plauger s->origPtr = (s->origPtr << 8) | ((Int32)uc);
259ca3e8d88SDave Plauger GET_UCHAR(BZ_X_ORIGPTR_3, uc);
260ca3e8d88SDave Plauger s->origPtr = (s->origPtr << 8) | ((Int32)uc);
261ca3e8d88SDave Plauger
262ca3e8d88SDave Plauger if (s->origPtr < 0)
263ca3e8d88SDave Plauger RETURN(BZ_DATA_ERROR);
264*238e18a0SToomas Soome if (s->origPtr > 10 + 100000*s->blockSize100k)
265ca3e8d88SDave Plauger RETURN(BZ_DATA_ERROR);
266ca3e8d88SDave Plauger
267ca3e8d88SDave Plauger /*--- Receive the mapping table ---*/
268ca3e8d88SDave Plauger for (i = 0; i < 16; i++) {
269ca3e8d88SDave Plauger GET_BIT(BZ_X_MAPPING_1, uc);
270*238e18a0SToomas Soome if (uc == 1)
271*238e18a0SToomas Soome s->inUse16[i] = True; else
272ca3e8d88SDave Plauger s->inUse16[i] = False;
273ca3e8d88SDave Plauger }
274ca3e8d88SDave Plauger
275ca3e8d88SDave Plauger for (i = 0; i < 256; i++) s->inUse[i] = False;
276ca3e8d88SDave Plauger
277ca3e8d88SDave Plauger for (i = 0; i < 16; i++)
278ca3e8d88SDave Plauger if (s->inUse16[i])
279ca3e8d88SDave Plauger for (j = 0; j < 16; j++) {
280ca3e8d88SDave Plauger GET_BIT(BZ_X_MAPPING_2, uc);
281ca3e8d88SDave Plauger if (uc == 1) s->inUse[i * 16 + j] = True;
282ca3e8d88SDave Plauger }
283ca3e8d88SDave Plauger makeMaps_d ( s );
284ca3e8d88SDave Plauger if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
285ca3e8d88SDave Plauger alphaSize = s->nInUse+2;
286ca3e8d88SDave Plauger
287ca3e8d88SDave Plauger /*--- Now the selectors ---*/
288ca3e8d88SDave Plauger GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
289ca3e8d88SDave Plauger if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
290ca3e8d88SDave Plauger GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
291ca3e8d88SDave Plauger if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
292ca3e8d88SDave Plauger for (i = 0; i < nSelectors; i++) {
293ca3e8d88SDave Plauger j = 0;
294ca3e8d88SDave Plauger while (True) {
295ca3e8d88SDave Plauger GET_BIT(BZ_X_SELECTOR_3, uc);
296ca3e8d88SDave Plauger if (uc == 0) break;
297ca3e8d88SDave Plauger j++;
298ca3e8d88SDave Plauger if (j >= nGroups) RETURN(BZ_DATA_ERROR);
299ca3e8d88SDave Plauger }
300ca3e8d88SDave Plauger s->selectorMtf[i] = j;
301ca3e8d88SDave Plauger }
302ca3e8d88SDave Plauger
303ca3e8d88SDave Plauger /*--- Undo the MTF values for the selectors. ---*/
304ca3e8d88SDave Plauger {
305ca3e8d88SDave Plauger UChar pos[BZ_N_GROUPS], tmp, v;
306ca3e8d88SDave Plauger for (v = 0; v < nGroups; v++) pos[v] = v;
307*238e18a0SToomas Soome
308ca3e8d88SDave Plauger for (i = 0; i < nSelectors; i++) {
309ca3e8d88SDave Plauger v = s->selectorMtf[i];
310ca3e8d88SDave Plauger tmp = pos[v];
311ca3e8d88SDave Plauger while (v > 0) { pos[v] = pos[v-1]; v--; }
312ca3e8d88SDave Plauger pos[0] = tmp;
313ca3e8d88SDave Plauger s->selector[i] = tmp;
314ca3e8d88SDave Plauger }
315ca3e8d88SDave Plauger }
316ca3e8d88SDave Plauger
317ca3e8d88SDave Plauger /*--- Now the coding tables ---*/
318ca3e8d88SDave Plauger for (t = 0; t < nGroups; t++) {
319ca3e8d88SDave Plauger GET_BITS(BZ_X_CODING_1, curr, 5);
320ca3e8d88SDave Plauger for (i = 0; i < alphaSize; i++) {
321ca3e8d88SDave Plauger while (True) {
322ca3e8d88SDave Plauger if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
323ca3e8d88SDave Plauger GET_BIT(BZ_X_CODING_2, uc);
324ca3e8d88SDave Plauger if (uc == 0) break;
325ca3e8d88SDave Plauger GET_BIT(BZ_X_CODING_3, uc);
326ca3e8d88SDave Plauger if (uc == 0) curr++; else curr--;
327ca3e8d88SDave Plauger }
328ca3e8d88SDave Plauger s->len[t][i] = curr;
329ca3e8d88SDave Plauger }
330ca3e8d88SDave Plauger }
331ca3e8d88SDave Plauger
332ca3e8d88SDave Plauger /*--- Create the Huffman decoding tables ---*/
333ca3e8d88SDave Plauger for (t = 0; t < nGroups; t++) {
334ca3e8d88SDave Plauger minLen = 32;
335ca3e8d88SDave Plauger maxLen = 0;
336ca3e8d88SDave Plauger for (i = 0; i < alphaSize; i++) {
337ca3e8d88SDave Plauger if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
338ca3e8d88SDave Plauger if (s->len[t][i] < minLen) minLen = s->len[t][i];
339ca3e8d88SDave Plauger }
340*238e18a0SToomas Soome BZ2_hbCreateDecodeTables (
341*238e18a0SToomas Soome &(s->limit[t][0]),
342*238e18a0SToomas Soome &(s->base[t][0]),
343*238e18a0SToomas Soome &(s->perm[t][0]),
344ca3e8d88SDave Plauger &(s->len[t][0]),
345ca3e8d88SDave Plauger minLen, maxLen, alphaSize
346ca3e8d88SDave Plauger );
347ca3e8d88SDave Plauger s->minLens[t] = minLen;
348ca3e8d88SDave Plauger }
349ca3e8d88SDave Plauger
350ca3e8d88SDave Plauger /*--- Now the MTF values ---*/
351ca3e8d88SDave Plauger
352ca3e8d88SDave Plauger EOB = s->nInUse+1;
353ca3e8d88SDave Plauger nblockMAX = 100000 * s->blockSize100k;
354ca3e8d88SDave Plauger groupNo = -1;
355ca3e8d88SDave Plauger groupPos = 0;
356ca3e8d88SDave Plauger
357ca3e8d88SDave Plauger for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
358ca3e8d88SDave Plauger
359ca3e8d88SDave Plauger /*-- MTF init --*/
360ca3e8d88SDave Plauger {
361ca3e8d88SDave Plauger Int32 ii, jj, kk;
362ca3e8d88SDave Plauger kk = MTFA_SIZE-1;
363ca3e8d88SDave Plauger for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
364ca3e8d88SDave Plauger for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
365ca3e8d88SDave Plauger s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
366ca3e8d88SDave Plauger kk--;
367ca3e8d88SDave Plauger }
368ca3e8d88SDave Plauger s->mtfbase[ii] = kk + 1;
369ca3e8d88SDave Plauger }
370ca3e8d88SDave Plauger }
371ca3e8d88SDave Plauger /*-- end MTF init --*/
372ca3e8d88SDave Plauger
373ca3e8d88SDave Plauger nblock = 0;
374ca3e8d88SDave Plauger GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
375ca3e8d88SDave Plauger
376ca3e8d88SDave Plauger while (True) {
377ca3e8d88SDave Plauger
378ca3e8d88SDave Plauger if (nextSym == EOB) break;
379ca3e8d88SDave Plauger
380ca3e8d88SDave Plauger if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
381ca3e8d88SDave Plauger
382ca3e8d88SDave Plauger es = -1;
383ca3e8d88SDave Plauger N = 1;
384ca3e8d88SDave Plauger do {
385b9071c34SGordon Ross /* Check that N doesn't get too big, so that es doesn't
386b9071c34SGordon Ross go negative. The maximum value that can be
387b9071c34SGordon Ross RUNA/RUNB encoded is equal to the block size (post
388b9071c34SGordon Ross the initial RLE), viz, 900k, so bounding N at 2
389b9071c34SGordon Ross million should guard against overflow without
390b9071c34SGordon Ross rejecting any legitimate inputs. */
391b9071c34SGordon Ross if (N >= 2*1024*1024) RETURN(BZ_DATA_ERROR);
392ca3e8d88SDave Plauger if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
393ca3e8d88SDave Plauger if (nextSym == BZ_RUNB) es = es + (1+1) * N;
394ca3e8d88SDave Plauger N = N * 2;
395ca3e8d88SDave Plauger GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
396ca3e8d88SDave Plauger }
397ca3e8d88SDave Plauger while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
398ca3e8d88SDave Plauger
399ca3e8d88SDave Plauger es++;
400ca3e8d88SDave Plauger uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
401ca3e8d88SDave Plauger s->unzftab[uc] += es;
402ca3e8d88SDave Plauger
403ca3e8d88SDave Plauger if (s->smallDecompress)
404ca3e8d88SDave Plauger while (es > 0) {
405ca3e8d88SDave Plauger if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
406ca3e8d88SDave Plauger s->ll16[nblock] = (UInt16)uc;
407ca3e8d88SDave Plauger nblock++;
408ca3e8d88SDave Plauger es--;
409ca3e8d88SDave Plauger }
410ca3e8d88SDave Plauger else
411ca3e8d88SDave Plauger while (es > 0) {
412ca3e8d88SDave Plauger if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
413ca3e8d88SDave Plauger s->tt[nblock] = (UInt32)uc;
414ca3e8d88SDave Plauger nblock++;
415ca3e8d88SDave Plauger es--;
416ca3e8d88SDave Plauger };
417ca3e8d88SDave Plauger
418ca3e8d88SDave Plauger continue;
419ca3e8d88SDave Plauger
420ca3e8d88SDave Plauger } else {
421ca3e8d88SDave Plauger
422ca3e8d88SDave Plauger if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
423ca3e8d88SDave Plauger
424ca3e8d88SDave Plauger /*-- uc = MTF ( nextSym-1 ) --*/
425ca3e8d88SDave Plauger {
426ca3e8d88SDave Plauger Int32 ii, jj, kk, pp, lno, off;
427ca3e8d88SDave Plauger UInt32 nn;
428ca3e8d88SDave Plauger nn = (UInt32)(nextSym - 1);
429ca3e8d88SDave Plauger
430ca3e8d88SDave Plauger if (nn < MTFL_SIZE) {
431ca3e8d88SDave Plauger /* avoid general-case expense */
432ca3e8d88SDave Plauger pp = s->mtfbase[0];
433ca3e8d88SDave Plauger uc = s->mtfa[pp+nn];
434ca3e8d88SDave Plauger while (nn > 3) {
435ca3e8d88SDave Plauger Int32 z = pp+nn;
436ca3e8d88SDave Plauger s->mtfa[(z) ] = s->mtfa[(z)-1];
437ca3e8d88SDave Plauger s->mtfa[(z)-1] = s->mtfa[(z)-2];
438ca3e8d88SDave Plauger s->mtfa[(z)-2] = s->mtfa[(z)-3];
439ca3e8d88SDave Plauger s->mtfa[(z)-3] = s->mtfa[(z)-4];
440ca3e8d88SDave Plauger nn -= 4;
441ca3e8d88SDave Plauger }
442*238e18a0SToomas Soome while (nn > 0) {
443*238e18a0SToomas Soome s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
444ca3e8d88SDave Plauger };
445ca3e8d88SDave Plauger s->mtfa[pp] = uc;
446*238e18a0SToomas Soome } else {
447ca3e8d88SDave Plauger /* general case */
448ca3e8d88SDave Plauger lno = nn / MTFL_SIZE;
449ca3e8d88SDave Plauger off = nn % MTFL_SIZE;
450ca3e8d88SDave Plauger pp = s->mtfbase[lno] + off;
451ca3e8d88SDave Plauger uc = s->mtfa[pp];
452*238e18a0SToomas Soome while (pp > s->mtfbase[lno]) {
453*238e18a0SToomas Soome s->mtfa[pp] = s->mtfa[pp-1]; pp--;
454ca3e8d88SDave Plauger };
455ca3e8d88SDave Plauger s->mtfbase[lno]++;
456ca3e8d88SDave Plauger while (lno > 0) {
457ca3e8d88SDave Plauger s->mtfbase[lno]--;
458*238e18a0SToomas Soome s->mtfa[s->mtfbase[lno]]
459ca3e8d88SDave Plauger = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
460ca3e8d88SDave Plauger lno--;
461ca3e8d88SDave Plauger }
462ca3e8d88SDave Plauger s->mtfbase[0]--;
463ca3e8d88SDave Plauger s->mtfa[s->mtfbase[0]] = uc;
464ca3e8d88SDave Plauger if (s->mtfbase[0] == 0) {
465ca3e8d88SDave Plauger kk = MTFA_SIZE-1;
466ca3e8d88SDave Plauger for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
467ca3e8d88SDave Plauger for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
468ca3e8d88SDave Plauger s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
469ca3e8d88SDave Plauger kk--;
470ca3e8d88SDave Plauger }
471ca3e8d88SDave Plauger s->mtfbase[ii] = kk + 1;
472ca3e8d88SDave Plauger }
473ca3e8d88SDave Plauger }
474ca3e8d88SDave Plauger }
475ca3e8d88SDave Plauger }
476ca3e8d88SDave Plauger /*-- end uc = MTF ( nextSym-1 ) --*/
477ca3e8d88SDave Plauger
478ca3e8d88SDave Plauger s->unzftab[s->seqToUnseq[uc]]++;
479ca3e8d88SDave Plauger if (s->smallDecompress)
480ca3e8d88SDave Plauger s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
481ca3e8d88SDave Plauger s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]);
482ca3e8d88SDave Plauger nblock++;
483ca3e8d88SDave Plauger
484ca3e8d88SDave Plauger GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
485ca3e8d88SDave Plauger continue;
486ca3e8d88SDave Plauger }
487ca3e8d88SDave Plauger }
488ca3e8d88SDave Plauger
489ca3e8d88SDave Plauger /* Now we know what nblock is, we can do a better sanity
490ca3e8d88SDave Plauger check on s->origPtr.
491ca3e8d88SDave Plauger */
492ca3e8d88SDave Plauger if (s->origPtr < 0 || s->origPtr >= nblock)
493ca3e8d88SDave Plauger RETURN(BZ_DATA_ERROR);
494ca3e8d88SDave Plauger
495ca3e8d88SDave Plauger /*-- Set up cftab to facilitate generation of T^(-1) --*/
496b9071c34SGordon Ross /* Check: unzftab entries in range. */
497b9071c34SGordon Ross for (i = 0; i <= 255; i++) {
498b9071c34SGordon Ross if (s->unzftab[i] < 0 || s->unzftab[i] > nblock)
499b9071c34SGordon Ross RETURN(BZ_DATA_ERROR);
500b9071c34SGordon Ross }
501b9071c34SGordon Ross /* Actually generate cftab. */
502ca3e8d88SDave Plauger s->cftab[0] = 0;
503ca3e8d88SDave Plauger for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
504ca3e8d88SDave Plauger for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
505b9071c34SGordon Ross /* Check: cftab entries in range. */
506ca3e8d88SDave Plauger for (i = 0; i <= 256; i++) {
507ca3e8d88SDave Plauger if (s->cftab[i] < 0 || s->cftab[i] > nblock) {
508ca3e8d88SDave Plauger /* s->cftab[i] can legitimately be == nblock */
509ca3e8d88SDave Plauger RETURN(BZ_DATA_ERROR)
510ca3e8d88SDave Plauger }
511ca3e8d88SDave Plauger }
512b9071c34SGordon Ross /* Check: cftab entries non-descending. */
513b9071c34SGordon Ross for (i = 1; i <= 256; i++) {
514b9071c34SGordon Ross if (s->cftab[i-1] > s->cftab[i]) {
515b9071c34SGordon Ross RETURN(BZ_DATA_ERROR)
516b9071c34SGordon Ross }
517b9071c34SGordon Ross }
518ca3e8d88SDave Plauger
519ca3e8d88SDave Plauger s->state_out_len = 0;
520ca3e8d88SDave Plauger s->state_out_ch = 0;
521ca3e8d88SDave Plauger BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
522ca3e8d88SDave Plauger s->state = BZ_X_OUTPUT;
523ca3e8d88SDave Plauger if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
524ca3e8d88SDave Plauger
525ca3e8d88SDave Plauger if (s->smallDecompress) {
526ca3e8d88SDave Plauger
527ca3e8d88SDave Plauger /*-- Make a copy of cftab, used in generation of T --*/
528ca3e8d88SDave Plauger for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
529ca3e8d88SDave Plauger
530ca3e8d88SDave Plauger /*-- compute the T vector --*/
531ca3e8d88SDave Plauger for (i = 0; i < nblock; i++) {
532ca3e8d88SDave Plauger uc = (UChar)(s->ll16[i]);
533ca3e8d88SDave Plauger SET_LL(i, s->cftabCopy[uc]);
534ca3e8d88SDave Plauger s->cftabCopy[uc]++;
535ca3e8d88SDave Plauger }
536ca3e8d88SDave Plauger
537ca3e8d88SDave Plauger /*-- Compute T^(-1) by pointer reversal on T --*/
538ca3e8d88SDave Plauger i = s->origPtr;
539ca3e8d88SDave Plauger j = GET_LL(i);
540ca3e8d88SDave Plauger do {
541ca3e8d88SDave Plauger Int32 tmp = GET_LL(j);
542ca3e8d88SDave Plauger SET_LL(j, i);
543ca3e8d88SDave Plauger i = j;
544ca3e8d88SDave Plauger j = tmp;
545ca3e8d88SDave Plauger }
546ca3e8d88SDave Plauger while (i != s->origPtr);
547ca3e8d88SDave Plauger
548ca3e8d88SDave Plauger s->tPos = s->origPtr;
549ca3e8d88SDave Plauger s->nblock_used = 0;
550ca3e8d88SDave Plauger if (s->blockRandomised) {
551ca3e8d88SDave Plauger BZ_RAND_INIT_MASK;
552*238e18a0SToomas Soome BZ_GET_SMALL(s->k0);
553*238e18a0SToomas Soome s->nblock_used++;
554*238e18a0SToomas Soome BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
555ca3e8d88SDave Plauger } else {
556ca3e8d88SDave Plauger BZ_GET_SMALL(s->k0); s->nblock_used++;
557ca3e8d88SDave Plauger }
558ca3e8d88SDave Plauger
559ca3e8d88SDave Plauger } else {
560ca3e8d88SDave Plauger
561ca3e8d88SDave Plauger /*-- compute the T^(-1) vector --*/
562ca3e8d88SDave Plauger for (i = 0; i < nblock; i++) {
563ca3e8d88SDave Plauger uc = (UChar)(s->tt[i] & 0xff);
564ca3e8d88SDave Plauger s->tt[s->cftab[uc]] |= (i << 8);
565ca3e8d88SDave Plauger s->cftab[uc]++;
566ca3e8d88SDave Plauger }
567ca3e8d88SDave Plauger
568ca3e8d88SDave Plauger s->tPos = s->tt[s->origPtr] >> 8;
569ca3e8d88SDave Plauger s->nblock_used = 0;
570ca3e8d88SDave Plauger if (s->blockRandomised) {
571ca3e8d88SDave Plauger BZ_RAND_INIT_MASK;
572*238e18a0SToomas Soome BZ_GET_FAST(s->k0);
573*238e18a0SToomas Soome s->nblock_used++;
574*238e18a0SToomas Soome BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
575ca3e8d88SDave Plauger } else {
576ca3e8d88SDave Plauger BZ_GET_FAST(s->k0); s->nblock_used++;
577ca3e8d88SDave Plauger }
578ca3e8d88SDave Plauger
579ca3e8d88SDave Plauger }
580ca3e8d88SDave Plauger
581ca3e8d88SDave Plauger RETURN(BZ_OK)
582ca3e8d88SDave Plauger
583ca3e8d88SDave Plauger
584ca3e8d88SDave Plauger
585ca3e8d88SDave Plauger endhdr_2:
586ca3e8d88SDave Plauger
587ca3e8d88SDave Plauger GET_UCHAR(BZ_X_ENDHDR_2, uc);
588ca3e8d88SDave Plauger if (uc != 0x72) RETURN(BZ_DATA_ERROR);
589ca3e8d88SDave Plauger GET_UCHAR(BZ_X_ENDHDR_3, uc);
590ca3e8d88SDave Plauger if (uc != 0x45) RETURN(BZ_DATA_ERROR);
591ca3e8d88SDave Plauger GET_UCHAR(BZ_X_ENDHDR_4, uc);
592ca3e8d88SDave Plauger if (uc != 0x38) RETURN(BZ_DATA_ERROR);
593ca3e8d88SDave Plauger GET_UCHAR(BZ_X_ENDHDR_5, uc);
594ca3e8d88SDave Plauger if (uc != 0x50) RETURN(BZ_DATA_ERROR);
595ca3e8d88SDave Plauger GET_UCHAR(BZ_X_ENDHDR_6, uc);
596ca3e8d88SDave Plauger if (uc != 0x90) RETURN(BZ_DATA_ERROR);
597ca3e8d88SDave Plauger
598ca3e8d88SDave Plauger s->storedCombinedCRC = 0;
599ca3e8d88SDave Plauger GET_UCHAR(BZ_X_CCRC_1, uc);
600ca3e8d88SDave Plauger s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
601ca3e8d88SDave Plauger GET_UCHAR(BZ_X_CCRC_2, uc);
602ca3e8d88SDave Plauger s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
603ca3e8d88SDave Plauger GET_UCHAR(BZ_X_CCRC_3, uc);
604ca3e8d88SDave Plauger s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
605ca3e8d88SDave Plauger GET_UCHAR(BZ_X_CCRC_4, uc);
606ca3e8d88SDave Plauger s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
607ca3e8d88SDave Plauger
608ca3e8d88SDave Plauger s->state = BZ_X_IDLE;
609ca3e8d88SDave Plauger RETURN(BZ_STREAM_END)
610ca3e8d88SDave Plauger
611ca3e8d88SDave Plauger default: AssertH ( False, 4001 );
612ca3e8d88SDave Plauger }
613ca3e8d88SDave Plauger
614ca3e8d88SDave Plauger AssertH ( False, 4002 );
615ca3e8d88SDave Plauger
616ca3e8d88SDave Plauger save_state_and_return:
617ca3e8d88SDave Plauger
618ca3e8d88SDave Plauger s->save_i = i;
619ca3e8d88SDave Plauger s->save_j = j;
620ca3e8d88SDave Plauger s->save_t = t;
621ca3e8d88SDave Plauger s->save_alphaSize = alphaSize;
622ca3e8d88SDave Plauger s->save_nGroups = nGroups;
623ca3e8d88SDave Plauger s->save_nSelectors = nSelectors;
624ca3e8d88SDave Plauger s->save_EOB = EOB;
625ca3e8d88SDave Plauger s->save_groupNo = groupNo;
626ca3e8d88SDave Plauger s->save_groupPos = groupPos;
627ca3e8d88SDave Plauger s->save_nextSym = nextSym;
628ca3e8d88SDave Plauger s->save_nblockMAX = nblockMAX;
629ca3e8d88SDave Plauger s->save_nblock = nblock;
630ca3e8d88SDave Plauger s->save_es = es;
631ca3e8d88SDave Plauger s->save_N = N;
632ca3e8d88SDave Plauger s->save_curr = curr;
633ca3e8d88SDave Plauger s->save_zt = zt;
634ca3e8d88SDave Plauger s->save_zn = zn;
635ca3e8d88SDave Plauger s->save_zvec = zvec;
636ca3e8d88SDave Plauger s->save_zj = zj;
637ca3e8d88SDave Plauger s->save_gSel = gSel;
638ca3e8d88SDave Plauger s->save_gMinlen = gMinlen;
639ca3e8d88SDave Plauger s->save_gLimit = gLimit;
640ca3e8d88SDave Plauger s->save_gBase = gBase;
641ca3e8d88SDave Plauger s->save_gPerm = gPerm;
642ca3e8d88SDave Plauger
643*238e18a0SToomas Soome return retVal;
644ca3e8d88SDave Plauger }
645ca3e8d88SDave Plauger
646ca3e8d88SDave Plauger
647ca3e8d88SDave Plauger /*-------------------------------------------------------------*/
648ca3e8d88SDave Plauger /*--- end decompress.c ---*/
649ca3e8d88SDave Plauger /*-------------------------------------------------------------*/
650