4 /*-------------------------------------------------------------*/
5 /*--- Decompression machinery ---*/
6 /*--- decompress.c ---*/
7 /*-------------------------------------------------------------*/
10 This file is a part of bzip2 and/or libbzip2, a program and
11 library for lossless, block-sorting data compression.
13 Copyright (C) 1996-2002 Julian R Seward. All rights reserved.
15 Redistribution and use in source and binary forms, with or without
16 modification, are permitted provided that the following conditions
19 1. Redistributions of source code must retain the above copyright
20 notice, this list of conditions and the following disclaimer.
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.
27 3. Altered source versions must be plainly marked as such, and must
28 not be misrepresented as being the original software.
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
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.
46 Julian Seward, Cambridge, UK.
48 bzip2/libbzip2 version 1.0 of 21 March 2000
50 This program is based on (at least) the work of:
60 For more information on these sources, see the manual.
64 #include "bzlib_private.h"
67 /*---------------------------------------------------*/
69 void makeMaps_d ( DState* s )
73 for (i = 0; i < 256; i++)
75 s->seqToUnseq[s->nInUse] = i;
81 /*---------------------------------------------------*/
83 { retVal = rrr; goto save_state_and_return; };
85 #define GET_BITS(lll,vvv,nnn) \
86 case lll: s->state = lll; \
88 if (s->bsLive >= nnn) { \
91 (s->bsLive-nnn)) & ((1 << nnn)-1); \
96 if (s->strm->avail_in == 0) RETURN(BZ_OK); \
98 = (s->bsBuff << 8) | \
100 (*((UChar*)(s->strm->next_in)))); \
102 s->strm->next_in++; \
103 s->strm->avail_in--; \
104 s->strm->total_in_lo32++; \
105 if (s->strm->total_in_lo32 == 0) \
106 s->strm->total_in_hi32++; \
109 #define GET_UCHAR(lll,uuu) \
112 #define GET_BIT(lll,uuu) \
115 /*---------------------------------------------------*/
116 #define GET_MTF_VAL(label1,label2,lval) \
118 if (groupPos == 0) { \
120 if (groupNo >= nSelectors) \
121 RETURN(BZ_DATA_ERROR); \
122 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]); \
131 GET_BITS(label1, zvec, zn); \
133 if (zn > 20 /* the longest code */) \
134 RETURN(BZ_DATA_ERROR); \
135 if (zvec <= gLimit[zn]) break; \
137 GET_BIT(label2, zj); \
138 zvec = (zvec << 1) | zj; \
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]]; \
147 /*---------------------------------------------------*/
148 Int32 BZ2_decompress ( DState* s )
152 Int32 minLen, maxLen;
153 bz_stream* strm = s->strm;
155 /* stuff that needs to be saved/restored */
181 if (s->state == BZ_X_MAGIC_1) {
182 /*initialise the save area*/
186 s->save_alphaSize = 0;
188 s->save_nSelectors = 0;
191 s->save_groupPos = 0;
193 s->save_nblockMAX = 0;
204 s->save_gLimit = NULL;
205 s->save_gBase = NULL;
206 s->save_gPerm = NULL;
209 /*restore from the save area*/
213 alphaSize = s->save_alphaSize;
214 nGroups = s->save_nGroups;
215 nSelectors = s->save_nSelectors;
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;
230 gMinlen = s->save_gMinlen;
231 gLimit = s->save_gLimit;
232 gBase = s->save_gBase;
233 gPerm = s->save_gPerm;
239 GET_UCHAR(BZ_X_MAGIC_1, uc);
240 if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);
242 GET_UCHAR(BZ_X_MAGIC_2, uc);
243 if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);
245 GET_UCHAR(BZ_X_MAGIC_3, uc)
246 if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);
248 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
249 if (s->blockSize100k < (BZ_HDR_0 + 1) ||
250 s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
251 s->blockSize100k -= BZ_HDR_0;
253 if (s->smallDecompress) {
254 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
256 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
258 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
260 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
261 if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
264 GET_UCHAR(BZ_X_BLKHDR_1, uc);
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);
280 if (s->verbosity >= 2)
281 VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo );
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);
293 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
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);
304 RETURN(BZ_DATA_ERROR);
305 if (s->origPtr > 10 + 100000*s->blockSize100k)
306 RETURN(BZ_DATA_ERROR);
308 /*--- Receive the mapping table ---*/
309 for (i = 0; i < 16; i++) {
310 GET_BIT(BZ_X_MAPPING_1, uc);
312 s->inUse16[i] = True; else
313 s->inUse16[i] = False;
316 for (i = 0; i < 256; i++) s->inUse[i] = False;
318 for (i = 0; i < 16; 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;
325 if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
326 alphaSize = s->nInUse+2;
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++) {
336 GET_BIT(BZ_X_SELECTOR_3, uc);
339 if (j >= nGroups) RETURN(BZ_DATA_ERROR);
341 s->selectorMtf[i] = j;
344 /*--- Undo the MTF values for the selectors. ---*/
346 UChar pos[BZ_N_GROUPS], tmp, v;
347 for (v = 0; v < nGroups; v++) pos[v] = v;
349 for (i = 0; i < nSelectors; i++) {
350 v = s->selectorMtf[i];
352 while (v > 0) { pos[v] = pos[v-1]; v--; }
354 s->selector[i] = tmp;
358 /*--- Now the coding tables ---*/
359 for (t = 0; t < nGroups; t++) {
360 GET_BITS(BZ_X_CODING_1, curr, 5);
361 for (i = 0; i < alphaSize; i++) {
363 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
364 GET_BIT(BZ_X_CODING_2, uc);
366 GET_BIT(BZ_X_CODING_3, uc);
367 if (uc == 0) curr++; else curr--;
373 /*--- Create the Huffman decoding tables ---*/
374 for (t = 0; t < nGroups; t++) {
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];
381 BZ2_hbCreateDecodeTables (
386 minLen, maxLen, alphaSize
388 s->minLens[t] = minLen;
391 /*--- Now the MTF values ---*/
394 nblockMAX = 100000 * s->blockSize100k;
398 for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
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);
409 s->mtfbase[ii] = kk + 1;
412 /*-- end MTF init --*/
415 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
419 if (nextSym == EOB) break;
421 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
426 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
427 if (nextSym == BZ_RUNB) es = es + (1+1) * N;
429 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
431 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
434 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
435 s->unzftab[uc] += es;
437 if (s->smallDecompress)
439 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
440 s->ll16[nblock] = (UInt16)uc;
446 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
447 s->tt[nblock] = (UInt32)uc;
456 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
458 /*-- uc = MTF ( nextSym-1 ) --*/
460 Int32 ii, jj, kk, pp, lno, off;
462 nn = (UInt32)(nextSym - 1);
464 if (nn < MTFL_SIZE) {
465 /* avoid general-case expense */
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];
477 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
482 lno = nn / MTFL_SIZE;
483 off = nn % MTFL_SIZE;
484 pp = s->mtfbase[lno] + off;
486 while (pp > s->mtfbase[lno]) {
487 s->mtfa[pp] = s->mtfa[pp-1]; pp--;
492 s->mtfa[s->mtfbase[lno]]
493 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
497 s->mtfa[s->mtfbase[0]] = uc;
498 if (s->mtfbase[0] == 0) {
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];
505 s->mtfbase[ii] = kk + 1;
510 /*-- end uc = MTF ( nextSym-1 ) --*/
512 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]);
518 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
523 /* Now we know what nblock is, we can do a better sanity
526 if (s->origPtr < 0 || s->origPtr >= nblock)
527 RETURN(BZ_DATA_ERROR);
529 s->state_out_len = 0;
531 BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
532 s->state = BZ_X_OUTPUT;
533 if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
535 /*-- Set up cftab to facilitate generation of T^(-1) --*/
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];
540 if (s->smallDecompress) {
542 /*-- Make a copy of cftab, used in generation of T --*/
543 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
545 /*-- compute the T vector --*/
546 for (i = 0; i < nblock; i++) {
547 uc = (UChar)(s->ll16[i]);
548 SET_LL(i, s->cftabCopy[uc]);
552 /*-- Compute T^(-1) by pointer reversal on T --*/
556 Int32 tmp = GET_LL(j);
561 while (i != s->origPtr);
563 s->tPos = s->origPtr;
565 if (s->blockRandomised) {
567 BZ_GET_SMALL(s->k0); s->nblock_used++;
568 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
570 BZ_GET_SMALL(s->k0); s->nblock_used++;
575 /*-- 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);
582 s->tPos = s->tt[s->origPtr] >> 8;
584 if (s->blockRandomised) {
586 BZ_GET_FAST(s->k0); s->nblock_used++;
587 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
589 BZ_GET_FAST(s->k0); s->nblock_used++;
600 GET_UCHAR(BZ_X_ENDHDR_2, uc);
601 if (uc != 0x72) RETURN(BZ_DATA_ERROR);
602 GET_UCHAR(BZ_X_ENDHDR_3, uc);
603 if (uc != 0x45) RETURN(BZ_DATA_ERROR);
604 GET_UCHAR(BZ_X_ENDHDR_4, uc);
605 if (uc != 0x38) RETURN(BZ_DATA_ERROR);
606 GET_UCHAR(BZ_X_ENDHDR_5, uc);
607 if (uc != 0x50) RETURN(BZ_DATA_ERROR);
608 GET_UCHAR(BZ_X_ENDHDR_6, uc);
609 if (uc != 0x90) RETURN(BZ_DATA_ERROR);
611 s->storedCombinedCRC = 0;
612 GET_UCHAR(BZ_X_CCRC_1, uc);
613 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
614 GET_UCHAR(BZ_X_CCRC_2, uc);
615 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
616 GET_UCHAR(BZ_X_CCRC_3, uc);
617 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
618 GET_UCHAR(BZ_X_CCRC_4, uc);
619 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
621 s->state = BZ_X_IDLE;
622 RETURN(BZ_STREAM_END);
624 default: AssertH ( False, 4001 );
627 AssertH ( False, 4002 );
629 save_state_and_return:
634 s->save_alphaSize = alphaSize;
635 s->save_nGroups = nGroups;
636 s->save_nSelectors = nSelectors;
638 s->save_groupNo = groupNo;
639 s->save_groupPos = groupPos;
640 s->save_nextSym = nextSym;
641 s->save_nblockMAX = nblockMAX;
642 s->save_nblock = nblock;
651 s->save_gMinlen = gMinlen;
652 s->save_gLimit = gLimit;
653 s->save_gBase = gBase;
654 s->save_gPerm = gPerm;
660 /*-------------------------------------------------------------*/
661 /*--- end decompress.c ---*/
662 /*-------------------------------------------------------------*/
664 #endif /* CONFIG_BZIP2 */