blob: a4a16879e7dce16a970cac52d1bd5ce4208ba230 [file] [log] [blame]
wdenkc29fdfc2003-08-29 20:57:53 +00001#include <config.h>
2#ifdef CONFIG_BZIP2
3
4/*-------------------------------------------------------------*/
5/*--- Decompression machinery ---*/
6/*--- decompress.c ---*/
7/*-------------------------------------------------------------*/
8
9/*--
10 This file is a part of bzip2 and/or libbzip2, a program and
11 library for lossless, block-sorting data compression.
12
13 Copyright (C) 1996-2002 Julian R Seward. All rights reserved.
14
15 Redistribution and use in source and binary forms, with or without
16 modification, are permitted provided that the following conditions
17 are met:
18
19 1. Redistributions of source code must retain the above copyright
20 notice, this list of conditions and the following disclaimer.
21
22 2. The origin of this software must not be misrepresented; you must
23 not claim that you wrote the original software. If you use this
24 software in a product, an acknowledgment in the product
25 documentation would be appreciated but is not required.
26
27 3. Altered source versions must be plainly marked as such, and must
28 not be misrepresented as being the original software.
29
30 4. The name of the author may not be used to endorse or promote
31 products derived from this software without specific prior written
32 permission.
33
34 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
35 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
36 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
38 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
39 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
40 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
41 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
42 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
43 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
44 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
45
46 Julian Seward, Cambridge, UK.
47 jseward@acm.org
48 bzip2/libbzip2 version 1.0 of 21 March 2000
49
50 This program is based on (at least) the work of:
51 Mike Burrows
52 David Wheeler
53 Peter Fenwick
54 Alistair Moffat
55 Radford Neal
56 Ian H. Witten
57 Robert Sedgewick
58 Jon L. Bentley
59
60 For more information on these sources, see the manual.
61--*/
62
63
64#include "bzlib_private.h"
65
66
67/*---------------------------------------------------*/
68static
69void makeMaps_d ( DState* s )
70{
71 Int32 i;
72 s->nInUse = 0;
73 for (i = 0; i < 256; i++)
74 if (s->inUse[i]) {
wdenk42d1f032003-10-15 23:53:47 +000075 s->seqToUnseq[s->nInUse] = i;
76 s->nInUse++;
wdenkc29fdfc2003-08-29 20:57:53 +000077 }
78}
79
80
81/*---------------------------------------------------*/
82#define RETURN(rrr) \
83 { retVal = rrr; goto save_state_and_return; };
84
85#define GET_BITS(lll,vvv,nnn) \
86 case lll: s->state = lll; \
87 while (True) { \
88 if (s->bsLive >= nnn) { \
wdenk42d1f032003-10-15 23:53:47 +000089 UInt32 v; \
90 v = (s->bsBuff >> \
91 (s->bsLive-nnn)) & ((1 << nnn)-1); \
92 s->bsLive -= nnn; \
93 vvv = v; \
94 break; \
wdenkc29fdfc2003-08-29 20:57:53 +000095 } \
96 if (s->strm->avail_in == 0) RETURN(BZ_OK); \
97 s->bsBuff \
wdenk42d1f032003-10-15 23:53:47 +000098 = (s->bsBuff << 8) | \
99 ((UInt32) \
100 (*((UChar*)(s->strm->next_in)))); \
wdenkc29fdfc2003-08-29 20:57:53 +0000101 s->bsLive += 8; \
102 s->strm->next_in++; \
103 s->strm->avail_in--; \
104 s->strm->total_in_lo32++; \
105 if (s->strm->total_in_lo32 == 0) \
wdenk42d1f032003-10-15 23:53:47 +0000106 s->strm->total_in_hi32++; \
wdenkc29fdfc2003-08-29 20:57:53 +0000107 }
108
109#define GET_UCHAR(lll,uuu) \
110 GET_BITS(lll,uuu,8)
111
112#define GET_BIT(lll,uuu) \
113 GET_BITS(lll,uuu,1)
114
115/*---------------------------------------------------*/
116#define GET_MTF_VAL(label1,label2,lval) \
117{ \
118 if (groupPos == 0) { \
119 groupNo++; \
120 if (groupNo >= nSelectors) \
wdenk42d1f032003-10-15 23:53:47 +0000121 RETURN(BZ_DATA_ERROR); \
wdenkc29fdfc2003-08-29 20:57:53 +0000122 groupPos = BZ_G_SIZE; \
123 gSel = s->selector[groupNo]; \
124 gMinlen = s->minLens[gSel]; \
125 gLimit = &(s->limit[gSel][0]); \
126 gPerm = &(s->perm[gSel][0]); \
127 gBase = &(s->base[gSel][0]); \
128 } \
129 groupPos--; \
130 zn = gMinlen; \
131 GET_BITS(label1, zvec, zn); \
132 while (1) { \
133 if (zn > 20 /* the longest code */) \
wdenk42d1f032003-10-15 23:53:47 +0000134 RETURN(BZ_DATA_ERROR); \
wdenkc29fdfc2003-08-29 20:57:53 +0000135 if (zvec <= gLimit[zn]) break; \
136 zn++; \
137 GET_BIT(label2, zj); \
138 zvec = (zvec << 1) | zj; \
139 }; \
140 if (zvec - gBase[zn] < 0 \
141 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \
142 RETURN(BZ_DATA_ERROR); \
143 lval = gPerm[zvec - gBase[zn]]; \
144}
145
146
147/*---------------------------------------------------*/
148Int32 BZ2_decompress ( DState* s )
149{
150 UChar uc;
151 Int32 retVal;
152 Int32 minLen, maxLen;
153 bz_stream* strm = s->strm;
154
155 /* stuff that needs to be saved/restored */
156 Int32 i;
157 Int32 j;
158 Int32 t;
159 Int32 alphaSize;
160 Int32 nGroups;
161 Int32 nSelectors;
162 Int32 EOB;
163 Int32 groupNo;
164 Int32 groupPos;
165 Int32 nextSym;
166 Int32 nblockMAX;
167 Int32 nblock;
168 Int32 es;
169 Int32 N;
170 Int32 curr;
171 Int32 zt;
172 Int32 zn;
173 Int32 zvec;
174 Int32 zj;
175 Int32 gSel;
176 Int32 gMinlen;
177 Int32* gLimit;
178 Int32* gBase;
179 Int32* gPerm;
180
181 if (s->state == BZ_X_MAGIC_1) {
182 /*initialise the save area*/
183 s->save_i = 0;
184 s->save_j = 0;
185 s->save_t = 0;
186 s->save_alphaSize = 0;
187 s->save_nGroups = 0;
188 s->save_nSelectors = 0;
189 s->save_EOB = 0;
190 s->save_groupNo = 0;
191 s->save_groupPos = 0;
192 s->save_nextSym = 0;
193 s->save_nblockMAX = 0;
194 s->save_nblock = 0;
195 s->save_es = 0;
196 s->save_N = 0;
197 s->save_curr = 0;
198 s->save_zt = 0;
199 s->save_zn = 0;
200 s->save_zvec = 0;
201 s->save_zj = 0;
202 s->save_gSel = 0;
203 s->save_gMinlen = 0;
204 s->save_gLimit = NULL;
205 s->save_gBase = NULL;
206 s->save_gPerm = NULL;
207 }
208
209 /*restore from the save area*/
210 i = s->save_i;
211 j = s->save_j;
212 t = s->save_t;
213 alphaSize = s->save_alphaSize;
214 nGroups = s->save_nGroups;
215 nSelectors = s->save_nSelectors;
216 EOB = s->save_EOB;
217 groupNo = s->save_groupNo;
218 groupPos = s->save_groupPos;
219 nextSym = s->save_nextSym;
220 nblockMAX = s->save_nblockMAX;
221 nblock = s->save_nblock;
222 es = s->save_es;
223 N = s->save_N;
224 curr = s->save_curr;
225 zt = s->save_zt;
226 zn = s->save_zn;
227 zvec = s->save_zvec;
228 zj = s->save_zj;
229 gSel = s->save_gSel;
230 gMinlen = s->save_gMinlen;
231 gLimit = s->save_gLimit;
232 gBase = s->save_gBase;
233 gPerm = s->save_gPerm;
234
235 retVal = BZ_OK;
236
237 switch (s->state) {
238
239 GET_UCHAR(BZ_X_MAGIC_1, uc);
240 if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);
241
242 GET_UCHAR(BZ_X_MAGIC_2, uc);
243 if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);
244
245 GET_UCHAR(BZ_X_MAGIC_3, uc)
246 if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);
247
248 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
249 if (s->blockSize100k < (BZ_HDR_0 + 1) ||
wdenk42d1f032003-10-15 23:53:47 +0000250 s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
wdenkc29fdfc2003-08-29 20:57:53 +0000251 s->blockSize100k -= BZ_HDR_0;
252
253 if (s->smallDecompress) {
wdenk42d1f032003-10-15 23:53:47 +0000254 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
255 s->ll4 = BZALLOC(
256 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
257 );
258 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
wdenkc29fdfc2003-08-29 20:57:53 +0000259 } else {
wdenk42d1f032003-10-15 23:53:47 +0000260 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
261 if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
wdenkc29fdfc2003-08-29 20:57:53 +0000262 }
263
264 GET_UCHAR(BZ_X_BLKHDR_1, uc);
265
266 if (uc == 0x17) goto endhdr_2;
267 if (uc != 0x31) RETURN(BZ_DATA_ERROR);
268 GET_UCHAR(BZ_X_BLKHDR_2, uc);
269 if (uc != 0x41) RETURN(BZ_DATA_ERROR);
270 GET_UCHAR(BZ_X_BLKHDR_3, uc);
271 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
272 GET_UCHAR(BZ_X_BLKHDR_4, uc);
273 if (uc != 0x26) RETURN(BZ_DATA_ERROR);
274 GET_UCHAR(BZ_X_BLKHDR_5, uc);
275 if (uc != 0x53) RETURN(BZ_DATA_ERROR);
276 GET_UCHAR(BZ_X_BLKHDR_6, uc);
277 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
278
279 s->currBlockNo++;
280 if (s->verbosity >= 2)
wdenk42d1f032003-10-15 23:53:47 +0000281 VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo );
wdenkc29fdfc2003-08-29 20:57:53 +0000282
283 s->storedBlockCRC = 0;
284 GET_UCHAR(BZ_X_BCRC_1, uc);
285 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
286 GET_UCHAR(BZ_X_BCRC_2, uc);
287 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
288 GET_UCHAR(BZ_X_BCRC_3, uc);
289 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
290 GET_UCHAR(BZ_X_BCRC_4, uc);
291 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
292
293 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
294
295 s->origPtr = 0;
296 GET_UCHAR(BZ_X_ORIGPTR_1, uc);
297 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
298 GET_UCHAR(BZ_X_ORIGPTR_2, uc);
299 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
300 GET_UCHAR(BZ_X_ORIGPTR_3, uc);
301 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
302
303 if (s->origPtr < 0)
wdenk42d1f032003-10-15 23:53:47 +0000304 RETURN(BZ_DATA_ERROR);
wdenkc29fdfc2003-08-29 20:57:53 +0000305 if (s->origPtr > 10 + 100000*s->blockSize100k)
wdenk42d1f032003-10-15 23:53:47 +0000306 RETURN(BZ_DATA_ERROR);
wdenkc29fdfc2003-08-29 20:57:53 +0000307
308 /*--- Receive the mapping table ---*/
309 for (i = 0; i < 16; i++) {
wdenk42d1f032003-10-15 23:53:47 +0000310 GET_BIT(BZ_X_MAPPING_1, uc);
311 if (uc == 1)
312 s->inUse16[i] = True; else
313 s->inUse16[i] = False;
wdenkc29fdfc2003-08-29 20:57:53 +0000314 }
315
316 for (i = 0; i < 256; i++) s->inUse[i] = False;
317
318 for (i = 0; i < 16; i++)
wdenk42d1f032003-10-15 23:53:47 +0000319 if (s->inUse16[i])
320 for (j = 0; j < 16; j++) {
321 GET_BIT(BZ_X_MAPPING_2, uc);
322 if (uc == 1) s->inUse[i * 16 + j] = True;
323 }
wdenkc29fdfc2003-08-29 20:57:53 +0000324 makeMaps_d ( s );
325 if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
326 alphaSize = s->nInUse+2;
327
328 /*--- Now the selectors ---*/
329 GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
330 if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
331 GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
332 if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
333 for (i = 0; i < nSelectors; i++) {
wdenk42d1f032003-10-15 23:53:47 +0000334 j = 0;
335 while (True) {
336 GET_BIT(BZ_X_SELECTOR_3, uc);
337 if (uc == 0) break;
338 j++;
339 if (j >= nGroups) RETURN(BZ_DATA_ERROR);
340 }
341 s->selectorMtf[i] = j;
wdenkc29fdfc2003-08-29 20:57:53 +0000342 }
343
344 /*--- Undo the MTF values for the selectors. ---*/
345 {
wdenk42d1f032003-10-15 23:53:47 +0000346 UChar pos[BZ_N_GROUPS], tmp, v;
347 for (v = 0; v < nGroups; v++) pos[v] = v;
wdenkc29fdfc2003-08-29 20:57:53 +0000348
wdenk42d1f032003-10-15 23:53:47 +0000349 for (i = 0; i < nSelectors; i++) {
350 v = s->selectorMtf[i];
351 tmp = pos[v];
352 while (v > 0) { pos[v] = pos[v-1]; v--; }
353 pos[0] = tmp;
354 s->selector[i] = tmp;
355 }
wdenkc29fdfc2003-08-29 20:57:53 +0000356 }
357
358 /*--- Now the coding tables ---*/
359 for (t = 0; t < nGroups; t++) {
wdenk42d1f032003-10-15 23:53:47 +0000360 GET_BITS(BZ_X_CODING_1, curr, 5);
361 for (i = 0; i < alphaSize; i++) {
362 while (True) {
363 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
364 GET_BIT(BZ_X_CODING_2, uc);
365 if (uc == 0) break;
366 GET_BIT(BZ_X_CODING_3, uc);
367 if (uc == 0) curr++; else curr--;
368 }
369 s->len[t][i] = curr;
370 }
wdenkc29fdfc2003-08-29 20:57:53 +0000371 }
372
373 /*--- Create the Huffman decoding tables ---*/
374 for (t = 0; t < nGroups; t++) {
wdenk42d1f032003-10-15 23:53:47 +0000375 minLen = 32;
376 maxLen = 0;
377 for (i = 0; i < alphaSize; i++) {
378 if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
379 if (s->len[t][i] < minLen) minLen = s->len[t][i];
380 }
381 BZ2_hbCreateDecodeTables (
382 &(s->limit[t][0]),
383 &(s->base[t][0]),
384 &(s->perm[t][0]),
385 &(s->len[t][0]),
386 minLen, maxLen, alphaSize
387 );
388 s->minLens[t] = minLen;
wdenkc29fdfc2003-08-29 20:57:53 +0000389 }
390
391 /*--- Now the MTF values ---*/
392
393 EOB = s->nInUse+1;
394 nblockMAX = 100000 * s->blockSize100k;
395 groupNo = -1;
396 groupPos = 0;
397
398 for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
399
400 /*-- MTF init --*/
401 {
wdenk42d1f032003-10-15 23:53:47 +0000402 Int32 ii, jj, kk;
403 kk = MTFA_SIZE-1;
404 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
405 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
406 s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
407 kk--;
408 }
409 s->mtfbase[ii] = kk + 1;
410 }
wdenkc29fdfc2003-08-29 20:57:53 +0000411 }
412 /*-- end MTF init --*/
413
414 nblock = 0;
415 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
416
417 while (True) {
418
wdenk42d1f032003-10-15 23:53:47 +0000419 if (nextSym == EOB) break;
wdenkc29fdfc2003-08-29 20:57:53 +0000420
wdenk42d1f032003-10-15 23:53:47 +0000421 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
wdenkc29fdfc2003-08-29 20:57:53 +0000422
wdenk42d1f032003-10-15 23:53:47 +0000423 es = -1;
424 N = 1;
425 do {
426 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
427 if (nextSym == BZ_RUNB) es = es + (1+1) * N;
428 N = N * 2;
429 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
430 }
431 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
wdenkc29fdfc2003-08-29 20:57:53 +0000432
wdenk42d1f032003-10-15 23:53:47 +0000433 es++;
434 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
435 s->unzftab[uc] += es;
wdenkc29fdfc2003-08-29 20:57:53 +0000436
wdenk42d1f032003-10-15 23:53:47 +0000437 if (s->smallDecompress)
438 while (es > 0) {
439 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
440 s->ll16[nblock] = (UInt16)uc;
441 nblock++;
442 es--;
443 }
444 else
445 while (es > 0) {
446 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
447 s->tt[nblock] = (UInt32)uc;
448 nblock++;
449 es--;
450 };
wdenkc29fdfc2003-08-29 20:57:53 +0000451
wdenk42d1f032003-10-15 23:53:47 +0000452 continue;
wdenkc29fdfc2003-08-29 20:57:53 +0000453
wdenk42d1f032003-10-15 23:53:47 +0000454 } else {
wdenkc29fdfc2003-08-29 20:57:53 +0000455
wdenk42d1f032003-10-15 23:53:47 +0000456 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
wdenkc29fdfc2003-08-29 20:57:53 +0000457
wdenk42d1f032003-10-15 23:53:47 +0000458 /*-- uc = MTF ( nextSym-1 ) --*/
459 {
460 Int32 ii, jj, kk, pp, lno, off;
461 UInt32 nn;
462 nn = (UInt32)(nextSym - 1);
wdenkc29fdfc2003-08-29 20:57:53 +0000463
wdenk42d1f032003-10-15 23:53:47 +0000464 if (nn < MTFL_SIZE) {
465 /* avoid general-case expense */
466 pp = s->mtfbase[0];
467 uc = s->mtfa[pp+nn];
468 while (nn > 3) {
469 Int32 z = pp+nn;
470 s->mtfa[(z) ] = s->mtfa[(z)-1];
471 s->mtfa[(z)-1] = s->mtfa[(z)-2];
472 s->mtfa[(z)-2] = s->mtfa[(z)-3];
473 s->mtfa[(z)-3] = s->mtfa[(z)-4];
474 nn -= 4;
475 }
476 while (nn > 0) {
477 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
478 };
479 s->mtfa[pp] = uc;
480 } else {
481 /* general case */
482 lno = nn / MTFL_SIZE;
483 off = nn % MTFL_SIZE;
484 pp = s->mtfbase[lno] + off;
485 uc = s->mtfa[pp];
486 while (pp > s->mtfbase[lno]) {
487 s->mtfa[pp] = s->mtfa[pp-1]; pp--;
488 };
489 s->mtfbase[lno]++;
490 while (lno > 0) {
491 s->mtfbase[lno]--;
492 s->mtfa[s->mtfbase[lno]]
493 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
494 lno--;
495 }
496 s->mtfbase[0]--;
497 s->mtfa[s->mtfbase[0]] = uc;
498 if (s->mtfbase[0] == 0) {
499 kk = MTFA_SIZE-1;
500 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
501 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
502 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
503 kk--;
504 }
505 s->mtfbase[ii] = kk + 1;
506 }
507 }
508 }
509 }
510 /*-- end uc = MTF ( nextSym-1 ) --*/
wdenkc29fdfc2003-08-29 20:57:53 +0000511
wdenk42d1f032003-10-15 23:53:47 +0000512 s->unzftab[s->seqToUnseq[uc]]++;
513 if (s->smallDecompress)
514 s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
515 s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]);
516 nblock++;
wdenkc29fdfc2003-08-29 20:57:53 +0000517
wdenk42d1f032003-10-15 23:53:47 +0000518 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
519 continue;
520 }
wdenkc29fdfc2003-08-29 20:57:53 +0000521 }
522
523 /* Now we know what nblock is, we can do a better sanity
wdenk42d1f032003-10-15 23:53:47 +0000524 check on s->origPtr.
wdenkc29fdfc2003-08-29 20:57:53 +0000525 */
526 if (s->origPtr < 0 || s->origPtr >= nblock)
wdenk42d1f032003-10-15 23:53:47 +0000527 RETURN(BZ_DATA_ERROR);
wdenkc29fdfc2003-08-29 20:57:53 +0000528
529 s->state_out_len = 0;
530 s->state_out_ch = 0;
531 BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
532 s->state = BZ_X_OUTPUT;
533 if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
534
535 /*-- Set up cftab to facilitate generation of T^(-1) --*/
536 s->cftab[0] = 0;
537 for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
538 for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
539
540 if (s->smallDecompress) {
541
wdenk42d1f032003-10-15 23:53:47 +0000542 /*-- Make a copy of cftab, used in generation of T --*/
543 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
wdenkc29fdfc2003-08-29 20:57:53 +0000544
wdenk42d1f032003-10-15 23:53:47 +0000545 /*-- compute the T vector --*/
546 for (i = 0; i < nblock; i++) {
547 uc = (UChar)(s->ll16[i]);
548 SET_LL(i, s->cftabCopy[uc]);
549 s->cftabCopy[uc]++;
550 }
wdenkc29fdfc2003-08-29 20:57:53 +0000551
wdenk42d1f032003-10-15 23:53:47 +0000552 /*-- Compute T^(-1) by pointer reversal on T --*/
553 i = s->origPtr;
554 j = GET_LL(i);
555 do {
556 Int32 tmp = GET_LL(j);
557 SET_LL(j, i);
558 i = j;
559 j = tmp;
560 }
561 while (i != s->origPtr);
wdenkc29fdfc2003-08-29 20:57:53 +0000562
wdenk42d1f032003-10-15 23:53:47 +0000563 s->tPos = s->origPtr;
564 s->nblock_used = 0;
565 if (s->blockRandomised) {
566 BZ_RAND_INIT_MASK;
567 BZ_GET_SMALL(s->k0); s->nblock_used++;
568 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
569 } else {
570 BZ_GET_SMALL(s->k0); s->nblock_used++;
571 }
wdenkc29fdfc2003-08-29 20:57:53 +0000572
573 } else {
574
wdenk42d1f032003-10-15 23:53:47 +0000575 /*-- compute the T^(-1) vector --*/
576 for (i = 0; i < nblock; i++) {
577 uc = (UChar)(s->tt[i] & 0xff);
578 s->tt[s->cftab[uc]] |= (i << 8);
579 s->cftab[uc]++;
580 }
wdenkc29fdfc2003-08-29 20:57:53 +0000581
wdenk42d1f032003-10-15 23:53:47 +0000582 s->tPos = s->tt[s->origPtr] >> 8;
583 s->nblock_used = 0;
584 if (s->blockRandomised) {
585 BZ_RAND_INIT_MASK;
586 BZ_GET_FAST(s->k0); s->nblock_used++;
587 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
588 } else {
589 BZ_GET_FAST(s->k0); s->nblock_used++;
590 }
wdenkc29fdfc2003-08-29 20:57:53 +0000591
592 }
593
594 RETURN(BZ_OK);
595
596
wdenkc29fdfc2003-08-29 20:57:53 +0000597 endhdr_2:
598
599 GET_UCHAR(BZ_X_ENDHDR_2, uc);
600 if (uc != 0x72) RETURN(BZ_DATA_ERROR);
601 GET_UCHAR(BZ_X_ENDHDR_3, uc);
602 if (uc != 0x45) RETURN(BZ_DATA_ERROR);
603 GET_UCHAR(BZ_X_ENDHDR_4, uc);
604 if (uc != 0x38) RETURN(BZ_DATA_ERROR);
605 GET_UCHAR(BZ_X_ENDHDR_5, uc);
606 if (uc != 0x50) RETURN(BZ_DATA_ERROR);
607 GET_UCHAR(BZ_X_ENDHDR_6, uc);
608 if (uc != 0x90) RETURN(BZ_DATA_ERROR);
609
610 s->storedCombinedCRC = 0;
611 GET_UCHAR(BZ_X_CCRC_1, uc);
612 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
613 GET_UCHAR(BZ_X_CCRC_2, uc);
614 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
615 GET_UCHAR(BZ_X_CCRC_3, uc);
616 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
617 GET_UCHAR(BZ_X_CCRC_4, uc);
618 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
619
620 s->state = BZ_X_IDLE;
621 RETURN(BZ_STREAM_END);
622
623 default: AssertH ( False, 4001 );
624 }
625
626 AssertH ( False, 4002 );
627
628 save_state_and_return:
629
630 s->save_i = i;
631 s->save_j = j;
632 s->save_t = t;
633 s->save_alphaSize = alphaSize;
634 s->save_nGroups = nGroups;
635 s->save_nSelectors = nSelectors;
636 s->save_EOB = EOB;
637 s->save_groupNo = groupNo;
638 s->save_groupPos = groupPos;
639 s->save_nextSym = nextSym;
640 s->save_nblockMAX = nblockMAX;
641 s->save_nblock = nblock;
642 s->save_es = es;
643 s->save_N = N;
644 s->save_curr = curr;
645 s->save_zt = zt;
646 s->save_zn = zn;
647 s->save_zvec = zvec;
648 s->save_zj = zj;
649 s->save_gSel = gSel;
650 s->save_gMinlen = gMinlen;
651 s->save_gLimit = gLimit;
652 s->save_gBase = gBase;
653 s->save_gPerm = gPerm;
654
655 return retVal;
656}
657
658
659/*-------------------------------------------------------------*/
660/*--- end decompress.c ---*/
661/*-------------------------------------------------------------*/
662
663#endif /* CONFIG_BZIP2 */