2 /*-------------------------------------------------------------*/
3 /*--- Decompression machinery ---*/
4 /*--- decompress.c ---*/
5 /*-------------------------------------------------------------*/
8 This file is a part of bzip2 and/or libbzip2, a program and
9 library for lossless, block-sorting data compression.
11 Copyright (C) 1996-2002 Julian R Seward. All rights reserved.
13 Redistribution and use in source and binary forms, with or without
14 modification, are permitted provided that the following conditions
17 1. Redistributions of source code must retain the above copyright
18 notice, this list of conditions and the following disclaimer.
20 2. The origin of this software must not be misrepresented; you must
21 not claim that you wrote the original software. If you use this
22 software in a product, an acknowledgment in the product
23 documentation would be appreciated but is not required.
25 3. Altered source versions must be plainly marked as such, and must
26 not be misrepresented as being the original software.
28 4. The name of the author may not be used to endorse or promote
29 products derived from this software without specific prior written
32 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
33 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
34 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
35 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
36 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
37 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
38 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
39 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
40 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
41 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
42 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
44 Julian Seward, Cambridge, UK.
46 bzip2/libbzip2 version 1.0 of 21 March 2000
48 This program is based on (at least) the work of:
58 For more information on these sources, see the manual.
62 #include "bzlib_private.h"
65 /*---------------------------------------------------*/
67 void makeMaps_d ( DState
* s
)
71 for (i
= 0; i
< 256; i
++)
73 s
->seqToUnseq
[s
->nInUse
] = i
;
79 /*---------------------------------------------------*/
81 { retVal = rrr; goto save_state_and_return; };
83 #define GET_BITS(lll,vvv,nnn) \
84 case lll: s->state = lll; \
86 if (s->bsLive >= nnn) { \
89 (s->bsLive-nnn)) & ((1 << nnn)-1); \
94 if (s->strm->avail_in == 0) RETURN(BZ_OK); \
96 = (s->bsBuff << 8) | \
98 (*((UChar*)(s->strm->next_in)))); \
100 s->strm->next_in++; \
101 s->strm->avail_in--; \
102 s->strm->total_in_lo32++; \
103 if (s->strm->total_in_lo32 == 0) \
104 s->strm->total_in_hi32++; \
107 #define GET_UCHAR(lll,uuu) \
110 #define GET_BIT(lll,uuu) \
113 /*---------------------------------------------------*/
114 #define GET_MTF_VAL(label1,label2,lval) \
116 if (groupPos == 0) { \
118 if (groupNo >= nSelectors) \
119 RETURN(BZ_DATA_ERROR); \
120 groupPos = BZ_G_SIZE; \
121 gSel = s->selector[groupNo]; \
122 gMinlen = s->minLens[gSel]; \
123 gLimit = &(s->limit[gSel][0]); \
124 gPerm = &(s->perm[gSel][0]); \
125 gBase = &(s->base[gSel][0]); \
129 GET_BITS(label1, zvec, zn); \
131 if (zn > 20 /* the longest code */) \
132 RETURN(BZ_DATA_ERROR); \
133 if (zvec <= gLimit[zn]) break; \
135 GET_BIT(label2, zj); \
136 zvec = (zvec << 1) | zj; \
138 if (zvec - gBase[zn] < 0 \
139 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \
140 RETURN(BZ_DATA_ERROR); \
141 lval = gPerm[zvec - gBase[zn]]; \
145 /*---------------------------------------------------*/
146 Int32
BZ2_decompress ( DState
* s
)
150 Int32 minLen
, maxLen
;
151 bz_stream
* strm
= s
->strm
;
153 /* stuff that needs to be saved/restored */
179 if (s
->state
== BZ_X_MAGIC_1
) {
180 /*initialise the save area*/
184 s
->save_alphaSize
= 0;
186 s
->save_nSelectors
= 0;
189 s
->save_groupPos
= 0;
191 s
->save_nblockMAX
= 0;
202 s
->save_gLimit
= NULL
;
203 s
->save_gBase
= NULL
;
204 s
->save_gPerm
= NULL
;
207 /*restore from the save area*/
211 alphaSize
= s
->save_alphaSize
;
212 nGroups
= s
->save_nGroups
;
213 nSelectors
= s
->save_nSelectors
;
215 groupNo
= s
->save_groupNo
;
216 groupPos
= s
->save_groupPos
;
217 nextSym
= s
->save_nextSym
;
218 nblockMAX
= s
->save_nblockMAX
;
219 nblock
= s
->save_nblock
;
228 gMinlen
= s
->save_gMinlen
;
229 gLimit
= s
->save_gLimit
;
230 gBase
= s
->save_gBase
;
231 gPerm
= s
->save_gPerm
;
237 GET_UCHAR(BZ_X_MAGIC_1
, uc
);
238 if (uc
!= BZ_HDR_B
) RETURN(BZ_DATA_ERROR_MAGIC
);
240 GET_UCHAR(BZ_X_MAGIC_2
, uc
);
241 if (uc
!= BZ_HDR_Z
) RETURN(BZ_DATA_ERROR_MAGIC
);
243 GET_UCHAR(BZ_X_MAGIC_3
, uc
)
244 if (uc
!= BZ_HDR_h
) RETURN(BZ_DATA_ERROR_MAGIC
);
246 GET_BITS(BZ_X_MAGIC_4
, s
->blockSize100k
, 8)
247 if (s
->blockSize100k
< (BZ_HDR_0
+ 1) ||
248 s
->blockSize100k
> (BZ_HDR_0
+ 9)) RETURN(BZ_DATA_ERROR_MAGIC
);
249 s
->blockSize100k
-= BZ_HDR_0
;
251 if (s
->smallDecompress
) {
252 s
->ll16
= BZALLOC( s
->blockSize100k
* 100000 * sizeof(UInt16
) );
254 ((1 + s
->blockSize100k
* 100000) >> 1) * sizeof(UChar
)
256 if (s
->ll16
== NULL
|| s
->ll4
== NULL
) RETURN(BZ_MEM_ERROR
);
258 s
->tt
= BZALLOC( s
->blockSize100k
* 100000 * sizeof(Int32
) );
259 if (s
->tt
== NULL
) RETURN(BZ_MEM_ERROR
);
262 GET_UCHAR(BZ_X_BLKHDR_1
, uc
);
264 if (uc
== 0x17) goto endhdr_2
;
265 if (uc
!= 0x31) RETURN(BZ_DATA_ERROR
);
266 GET_UCHAR(BZ_X_BLKHDR_2
, uc
);
267 if (uc
!= 0x41) RETURN(BZ_DATA_ERROR
);
268 GET_UCHAR(BZ_X_BLKHDR_3
, uc
);
269 if (uc
!= 0x59) RETURN(BZ_DATA_ERROR
);
270 GET_UCHAR(BZ_X_BLKHDR_4
, uc
);
271 if (uc
!= 0x26) RETURN(BZ_DATA_ERROR
);
272 GET_UCHAR(BZ_X_BLKHDR_5
, uc
);
273 if (uc
!= 0x53) RETURN(BZ_DATA_ERROR
);
274 GET_UCHAR(BZ_X_BLKHDR_6
, uc
);
275 if (uc
!= 0x59) RETURN(BZ_DATA_ERROR
);
278 if (s
->verbosity
>= 2)
279 VPrintf1 ( "\n [%d: huff+mtf ", s
->currBlockNo
);
281 s
->storedBlockCRC
= 0;
282 GET_UCHAR(BZ_X_BCRC_1
, uc
);
283 s
->storedBlockCRC
= (s
->storedBlockCRC
<< 8) | ((UInt32
)uc
);
284 GET_UCHAR(BZ_X_BCRC_2
, uc
);
285 s
->storedBlockCRC
= (s
->storedBlockCRC
<< 8) | ((UInt32
)uc
);
286 GET_UCHAR(BZ_X_BCRC_3
, uc
);
287 s
->storedBlockCRC
= (s
->storedBlockCRC
<< 8) | ((UInt32
)uc
);
288 GET_UCHAR(BZ_X_BCRC_4
, uc
);
289 s
->storedBlockCRC
= (s
->storedBlockCRC
<< 8) | ((UInt32
)uc
);
291 GET_BITS(BZ_X_RANDBIT
, s
->blockRandomised
, 1);
294 GET_UCHAR(BZ_X_ORIGPTR_1
, uc
);
295 s
->origPtr
= (s
->origPtr
<< 8) | ((Int32
)uc
);
296 GET_UCHAR(BZ_X_ORIGPTR_2
, uc
);
297 s
->origPtr
= (s
->origPtr
<< 8) | ((Int32
)uc
);
298 GET_UCHAR(BZ_X_ORIGPTR_3
, uc
);
299 s
->origPtr
= (s
->origPtr
<< 8) | ((Int32
)uc
);
302 RETURN(BZ_DATA_ERROR
);
303 if (s
->origPtr
> 10 + 100000*s
->blockSize100k
)
304 RETURN(BZ_DATA_ERROR
);
306 /*--- Receive the mapping table ---*/
307 for (i
= 0; i
< 16; i
++) {
308 GET_BIT(BZ_X_MAPPING_1
, uc
);
310 s
->inUse16
[i
] = True
; else
311 s
->inUse16
[i
] = False
;
314 for (i
= 0; i
< 256; i
++) s
->inUse
[i
] = False
;
316 for (i
= 0; i
< 16; i
++)
318 for (j
= 0; j
< 16; j
++) {
319 GET_BIT(BZ_X_MAPPING_2
, uc
);
320 if (uc
== 1) s
->inUse
[i
* 16 + j
] = True
;
323 if (s
->nInUse
== 0) RETURN(BZ_DATA_ERROR
);
324 alphaSize
= s
->nInUse
+2;
326 /*--- Now the selectors ---*/
327 GET_BITS(BZ_X_SELECTOR_1
, nGroups
, 3);
328 if (nGroups
< 2 || nGroups
> 6) RETURN(BZ_DATA_ERROR
);
329 GET_BITS(BZ_X_SELECTOR_2
, nSelectors
, 15);
330 if (nSelectors
< 1) RETURN(BZ_DATA_ERROR
);
331 for (i
= 0; i
< nSelectors
; i
++) {
334 GET_BIT(BZ_X_SELECTOR_3
, uc
);
337 if (j
>= nGroups
) RETURN(BZ_DATA_ERROR
);
339 s
->selectorMtf
[i
] = j
;
342 /*--- Undo the MTF values for the selectors. ---*/
344 UChar pos
[BZ_N_GROUPS
], tmp
, v
;
345 for (v
= 0; v
< nGroups
; v
++) pos
[v
] = v
;
347 for (i
= 0; i
< nSelectors
; i
++) {
348 v
= s
->selectorMtf
[i
];
350 while (v
> 0) { pos
[v
] = pos
[v
-1]; v
--; }
352 s
->selector
[i
] = tmp
;
356 /*--- Now the coding tables ---*/
357 for (t
= 0; t
< nGroups
; t
++) {
358 GET_BITS(BZ_X_CODING_1
, curr
, 5);
359 for (i
= 0; i
< alphaSize
; i
++) {
361 if (curr
< 1 || curr
> 20) RETURN(BZ_DATA_ERROR
);
362 GET_BIT(BZ_X_CODING_2
, uc
);
364 GET_BIT(BZ_X_CODING_3
, uc
);
365 if (uc
== 0) curr
++; else curr
--;
371 /*--- Create the Huffman decoding tables ---*/
372 for (t
= 0; t
< nGroups
; t
++) {
375 for (i
= 0; i
< alphaSize
; i
++) {
376 if (s
->len
[t
][i
] > maxLen
) maxLen
= s
->len
[t
][i
];
377 if (s
->len
[t
][i
] < minLen
) minLen
= s
->len
[t
][i
];
379 BZ2_hbCreateDecodeTables (
384 minLen
, maxLen
, alphaSize
386 s
->minLens
[t
] = minLen
;
389 /*--- Now the MTF values ---*/
392 nblockMAX
= 100000 * s
->blockSize100k
;
396 for (i
= 0; i
<= 255; i
++) s
->unzftab
[i
] = 0;
402 for (ii
= 256 / MTFL_SIZE
- 1; ii
>= 0; ii
--) {
403 for (jj
= MTFL_SIZE
-1; jj
>= 0; jj
--) {
404 s
->mtfa
[kk
] = (UChar
)(ii
* MTFL_SIZE
+ jj
);
407 s
->mtfbase
[ii
] = kk
+ 1;
410 /*-- end MTF init --*/
413 GET_MTF_VAL(BZ_X_MTF_1
, BZ_X_MTF_2
, nextSym
);
417 if (nextSym
== EOB
) break;
419 if (nextSym
== BZ_RUNA
|| nextSym
== BZ_RUNB
) {
424 if (nextSym
== BZ_RUNA
) es
= es
+ (0+1) * N
; else
425 if (nextSym
== BZ_RUNB
) es
= es
+ (1+1) * N
;
427 GET_MTF_VAL(BZ_X_MTF_3
, BZ_X_MTF_4
, nextSym
);
429 while (nextSym
== BZ_RUNA
|| nextSym
== BZ_RUNB
);
432 uc
= s
->seqToUnseq
[ s
->mtfa
[s
->mtfbase
[0]] ];
433 s
->unzftab
[uc
] += es
;
435 if (s
->smallDecompress
)
437 if (nblock
>= nblockMAX
) RETURN(BZ_DATA_ERROR
);
438 s
->ll16
[nblock
] = (UInt16
)uc
;
444 if (nblock
>= nblockMAX
) RETURN(BZ_DATA_ERROR
);
445 s
->tt
[nblock
] = (UInt32
)uc
;
454 if (nblock
>= nblockMAX
) RETURN(BZ_DATA_ERROR
);
456 /*-- uc = MTF ( nextSym-1 ) --*/
458 Int32 ii
, jj
, kk
, pp
, lno
, off
;
460 nn
= (UInt32
)(nextSym
- 1);
462 if (nn
< MTFL_SIZE
) {
463 /* avoid general-case expense */
468 s
->mtfa
[(z
) ] = s
->mtfa
[(z
)-1];
469 s
->mtfa
[(z
)-1] = s
->mtfa
[(z
)-2];
470 s
->mtfa
[(z
)-2] = s
->mtfa
[(z
)-3];
471 s
->mtfa
[(z
)-3] = s
->mtfa
[(z
)-4];
475 s
->mtfa
[(pp
+nn
)] = s
->mtfa
[(pp
+nn
)-1]; nn
--;
480 lno
= nn
/ MTFL_SIZE
;
481 off
= nn
% MTFL_SIZE
;
482 pp
= s
->mtfbase
[lno
] + off
;
484 while (pp
> s
->mtfbase
[lno
]) {
485 s
->mtfa
[pp
] = s
->mtfa
[pp
-1]; pp
--;
490 s
->mtfa
[s
->mtfbase
[lno
]]
491 = s
->mtfa
[s
->mtfbase
[lno
-1] + MTFL_SIZE
- 1];
495 s
->mtfa
[s
->mtfbase
[0]] = uc
;
496 if (s
->mtfbase
[0] == 0) {
498 for (ii
= 256 / MTFL_SIZE
-1; ii
>= 0; ii
--) {
499 for (jj
= MTFL_SIZE
-1; jj
>= 0; jj
--) {
500 s
->mtfa
[kk
] = s
->mtfa
[s
->mtfbase
[ii
] + jj
];
503 s
->mtfbase
[ii
] = kk
+ 1;
508 /*-- end uc = MTF ( nextSym-1 ) --*/
510 s
->unzftab
[s
->seqToUnseq
[uc
]]++;
511 if (s
->smallDecompress
)
512 s
->ll16
[nblock
] = (UInt16
)(s
->seqToUnseq
[uc
]); else
513 s
->tt
[nblock
] = (UInt32
)(s
->seqToUnseq
[uc
]);
516 GET_MTF_VAL(BZ_X_MTF_5
, BZ_X_MTF_6
, nextSym
);
521 /* Now we know what nblock is, we can do a better sanity
524 if (s
->origPtr
< 0 || s
->origPtr
>= nblock
)
525 RETURN(BZ_DATA_ERROR
);
527 s
->state_out_len
= 0;
529 BZ_INITIALISE_CRC ( s
->calculatedBlockCRC
);
530 s
->state
= BZ_X_OUTPUT
;
531 if (s
->verbosity
>= 2) VPrintf0 ( "rt+rld" );
533 /*-- Set up cftab to facilitate generation of T^(-1) --*/
535 for (i
= 1; i
<= 256; i
++) s
->cftab
[i
] = s
->unzftab
[i
-1];
536 for (i
= 1; i
<= 256; i
++) s
->cftab
[i
] += s
->cftab
[i
-1];
538 if (s
->smallDecompress
) {
540 /*-- Make a copy of cftab, used in generation of T --*/
541 for (i
= 0; i
<= 256; i
++) s
->cftabCopy
[i
] = s
->cftab
[i
];
543 /*-- compute the T vector --*/
544 for (i
= 0; i
< nblock
; i
++) {
545 uc
= (UChar
)(s
->ll16
[i
]);
546 SET_LL(i
, s
->cftabCopy
[uc
]);
550 /*-- Compute T^(-1) by pointer reversal on T --*/
554 Int32 tmp
= GET_LL(j
);
559 while (i
!= s
->origPtr
);
561 s
->tPos
= s
->origPtr
;
563 if (s
->blockRandomised
) {
565 BZ_GET_SMALL(s
->k0
); s
->nblock_used
++;
566 BZ_RAND_UPD_MASK
; s
->k0
^= BZ_RAND_MASK
;
568 BZ_GET_SMALL(s
->k0
); s
->nblock_used
++;
573 /*-- compute the T^(-1) vector --*/
574 for (i
= 0; i
< nblock
; i
++) {
575 uc
= (UChar
)(s
->tt
[i
] & 0xff);
576 s
->tt
[s
->cftab
[uc
]] |= (i
<< 8);
580 s
->tPos
= s
->tt
[s
->origPtr
] >> 8;
582 if (s
->blockRandomised
) {
584 BZ_GET_FAST(s
->k0
); s
->nblock_used
++;
585 BZ_RAND_UPD_MASK
; s
->k0
^= BZ_RAND_MASK
;
587 BZ_GET_FAST(s
->k0
); s
->nblock_used
++;
598 GET_UCHAR(BZ_X_ENDHDR_2
, uc
);
599 if (uc
!= 0x72) RETURN(BZ_DATA_ERROR
);
600 GET_UCHAR(BZ_X_ENDHDR_3
, uc
);
601 if (uc
!= 0x45) RETURN(BZ_DATA_ERROR
);
602 GET_UCHAR(BZ_X_ENDHDR_4
, uc
);
603 if (uc
!= 0x38) RETURN(BZ_DATA_ERROR
);
604 GET_UCHAR(BZ_X_ENDHDR_5
, uc
);
605 if (uc
!= 0x50) RETURN(BZ_DATA_ERROR
);
606 GET_UCHAR(BZ_X_ENDHDR_6
, uc
);
607 if (uc
!= 0x90) RETURN(BZ_DATA_ERROR
);
609 s
->storedCombinedCRC
= 0;
610 GET_UCHAR(BZ_X_CCRC_1
, uc
);
611 s
->storedCombinedCRC
= (s
->storedCombinedCRC
<< 8) | ((UInt32
)uc
);
612 GET_UCHAR(BZ_X_CCRC_2
, uc
);
613 s
->storedCombinedCRC
= (s
->storedCombinedCRC
<< 8) | ((UInt32
)uc
);
614 GET_UCHAR(BZ_X_CCRC_3
, uc
);
615 s
->storedCombinedCRC
= (s
->storedCombinedCRC
<< 8) | ((UInt32
)uc
);
616 GET_UCHAR(BZ_X_CCRC_4
, uc
);
617 s
->storedCombinedCRC
= (s
->storedCombinedCRC
<< 8) | ((UInt32
)uc
);
619 s
->state
= BZ_X_IDLE
;
620 RETURN(BZ_STREAM_END
);
622 default: AssertH ( False
, 4001 );
625 AssertH ( False
, 4002 );
627 save_state_and_return
:
632 s
->save_alphaSize
= alphaSize
;
633 s
->save_nGroups
= nGroups
;
634 s
->save_nSelectors
= nSelectors
;
636 s
->save_groupNo
= groupNo
;
637 s
->save_groupPos
= groupPos
;
638 s
->save_nextSym
= nextSym
;
639 s
->save_nblockMAX
= nblockMAX
;
640 s
->save_nblock
= nblock
;
649 s
->save_gMinlen
= gMinlen
;
650 s
->save_gLimit
= gLimit
;
651 s
->save_gBase
= gBase
;
652 s
->save_gPerm
= gPerm
;
658 /*-------------------------------------------------------------*/
659 /*--- end decompress.c ---*/
660 /*-------------------------------------------------------------*/