1 /* $NetBSD: decompress.c,v 1.3 2012/05/07 00:45:48 wiz Exp $ */
4 /*-------------------------------------------------------------*/
5 /*--- Decompression machinery ---*/
6 /*--- decompress.c ---*/
7 /*-------------------------------------------------------------*/
9 /* ------------------------------------------------------------------
10 This file is part of bzip2/libbzip2, a program and library for
11 lossless, block-sorting data compression.
13 bzip2/libbzip2 version 1.0.6 of 6 September 2010
14 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
16 Please read the WARNING, DISCLAIMER and PATENTS sections in the
19 This program is released under the terms of the license contained
21 ------------------------------------------------------------------ */
24 #include "bzlib_private.h"
27 /*---------------------------------------------------*/
29 void makeMaps_d ( DState
* s
)
33 for (i
= 0; i
< 256; i
++)
35 s
->seqToUnseq
[s
->nInUse
] = i
;
41 /*---------------------------------------------------*/
43 { retVal = rrr; goto save_state_and_return; };
45 #define GET_BITS(lll,vvv,nnn) \
46 case lll: s->state = lll; \
48 if (s->bsLive >= nnn) { \
51 (s->bsLive-nnn)) & ((1 << nnn)-1); \
56 if (s->strm->avail_in == 0) RETURN(BZ_OK); \
58 = (s->bsBuff << 8) | \
60 (*((UChar*)(s->strm->next_in)))); \
63 s->strm->avail_in--; \
64 s->strm->total_in_lo32++; \
65 if (s->strm->total_in_lo32 == 0) \
66 s->strm->total_in_hi32++; \
69 #define GET_UCHAR(lll,uuu) \
72 #define GET_BIT(lll,uuu) \
75 /*---------------------------------------------------*/
76 #define GET_MTF_VAL(label1,label2,lval) \
78 if (groupPos == 0) { \
80 if (groupNo >= nSelectors) \
81 RETURN(BZ_DATA_ERROR); \
82 groupPos = BZ_G_SIZE; \
83 gSel = s->selector[groupNo]; \
84 gMinlen = s->minLens[gSel]; \
85 gLimit = &(s->limit[gSel][0]); \
86 gPerm = &(s->perm[gSel][0]); \
87 gBase = &(s->base[gSel][0]); \
91 GET_BITS(label1, zvec, zn); \
93 if (zn > 20 /* the longest code */) \
94 RETURN(BZ_DATA_ERROR); \
95 if (zvec <= gLimit[zn]) break; \
97 GET_BIT(label2, zj); \
98 zvec = (zvec << 1) | zj; \
100 if (zvec - gBase[zn] < 0 \
101 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \
102 RETURN(BZ_DATA_ERROR); \
103 lval = gPerm[zvec - gBase[zn]]; \
107 /*---------------------------------------------------*/
108 Int32
BZ2_decompress ( DState
* s
)
112 Int32 minLen
, maxLen
;
113 bz_stream
* strm
= s
->strm
;
115 /* stuff that needs to be saved/restored */
141 if (s
->state
== BZ_X_MAGIC_1
) {
142 /*initialise the save area*/
146 s
->save_alphaSize
= 0;
148 s
->save_nSelectors
= 0;
151 s
->save_groupPos
= 0;
153 s
->save_nblockMAX
= 0;
164 s
->save_gLimit
= NULL
;
165 s
->save_gBase
= NULL
;
166 s
->save_gPerm
= NULL
;
169 /*restore from the save area*/
173 alphaSize
= s
->save_alphaSize
;
174 nGroups
= s
->save_nGroups
;
175 nSelectors
= s
->save_nSelectors
;
177 groupNo
= s
->save_groupNo
;
178 groupPos
= s
->save_groupPos
;
179 nextSym
= s
->save_nextSym
;
180 nblockMAX
= s
->save_nblockMAX
;
181 nblock
= s
->save_nblock
;
190 gMinlen
= s
->save_gMinlen
;
191 gLimit
= s
->save_gLimit
;
192 gBase
= s
->save_gBase
;
193 gPerm
= s
->save_gPerm
;
199 GET_UCHAR(BZ_X_MAGIC_1
, uc
);
200 if (uc
!= BZ_HDR_B
) RETURN(BZ_DATA_ERROR_MAGIC
);
202 GET_UCHAR(BZ_X_MAGIC_2
, uc
);
203 if (uc
!= BZ_HDR_Z
) RETURN(BZ_DATA_ERROR_MAGIC
);
205 GET_UCHAR(BZ_X_MAGIC_3
, uc
)
206 if (uc
!= BZ_HDR_h
) RETURN(BZ_DATA_ERROR_MAGIC
);
208 GET_BITS(BZ_X_MAGIC_4
, s
->blockSize100k
, 8)
209 if (s
->blockSize100k
< (BZ_HDR_0
+ 1) ||
210 s
->blockSize100k
> (BZ_HDR_0
+ 9)) RETURN(BZ_DATA_ERROR_MAGIC
);
211 s
->blockSize100k
-= BZ_HDR_0
;
213 if (s
->smallDecompress
) {
214 s
->ll16
= BZALLOC( s
->blockSize100k
* 100000 * sizeof(UInt16
) );
216 ((1 + s
->blockSize100k
* 100000) >> 1) * sizeof(UChar
)
218 if (s
->ll16
== NULL
|| s
->ll4
== NULL
) RETURN(BZ_MEM_ERROR
);
220 s
->tt
= BZALLOC( s
->blockSize100k
* 100000 * sizeof(Int32
) );
221 if (s
->tt
== NULL
) RETURN(BZ_MEM_ERROR
);
224 GET_UCHAR(BZ_X_BLKHDR_1
, uc
);
226 if (uc
== 0x17) goto endhdr_2
;
227 if (uc
!= 0x31) RETURN(BZ_DATA_ERROR
);
228 GET_UCHAR(BZ_X_BLKHDR_2
, uc
);
229 if (uc
!= 0x41) RETURN(BZ_DATA_ERROR
);
230 GET_UCHAR(BZ_X_BLKHDR_3
, uc
);
231 if (uc
!= 0x59) RETURN(BZ_DATA_ERROR
);
232 GET_UCHAR(BZ_X_BLKHDR_4
, uc
);
233 if (uc
!= 0x26) RETURN(BZ_DATA_ERROR
);
234 GET_UCHAR(BZ_X_BLKHDR_5
, uc
);
235 if (uc
!= 0x53) RETURN(BZ_DATA_ERROR
);
236 GET_UCHAR(BZ_X_BLKHDR_6
, uc
);
237 if (uc
!= 0x59) RETURN(BZ_DATA_ERROR
);
240 if (s
->verbosity
>= 2)
241 VPrintf1 ( "\n [%d: huff+mtf ", s
->currBlockNo
);
243 s
->storedBlockCRC
= 0;
244 GET_UCHAR(BZ_X_BCRC_1
, uc
);
245 s
->storedBlockCRC
= (s
->storedBlockCRC
<< 8) | ((UInt32
)uc
);
246 GET_UCHAR(BZ_X_BCRC_2
, uc
);
247 s
->storedBlockCRC
= (s
->storedBlockCRC
<< 8) | ((UInt32
)uc
);
248 GET_UCHAR(BZ_X_BCRC_3
, uc
);
249 s
->storedBlockCRC
= (s
->storedBlockCRC
<< 8) | ((UInt32
)uc
);
250 GET_UCHAR(BZ_X_BCRC_4
, uc
);
251 s
->storedBlockCRC
= (s
->storedBlockCRC
<< 8) | ((UInt32
)uc
);
253 GET_BITS(BZ_X_RANDBIT
, s
->blockRandomised
, 1);
256 GET_UCHAR(BZ_X_ORIGPTR_1
, uc
);
257 s
->origPtr
= (s
->origPtr
<< 8) | ((Int32
)uc
);
258 GET_UCHAR(BZ_X_ORIGPTR_2
, uc
);
259 s
->origPtr
= (s
->origPtr
<< 8) | ((Int32
)uc
);
260 GET_UCHAR(BZ_X_ORIGPTR_3
, uc
);
261 s
->origPtr
= (s
->origPtr
<< 8) | ((Int32
)uc
);
264 RETURN(BZ_DATA_ERROR
);
265 if (s
->origPtr
> 10 + 100000*s
->blockSize100k
)
266 RETURN(BZ_DATA_ERROR
);
268 /*--- Receive the mapping table ---*/
269 for (i
= 0; i
< 16; i
++) {
270 GET_BIT(BZ_X_MAPPING_1
, uc
);
272 s
->inUse16
[i
] = True
; else
273 s
->inUse16
[i
] = False
;
276 for (i
= 0; i
< 256; i
++) s
->inUse
[i
] = False
;
278 for (i
= 0; i
< 16; i
++)
280 for (j
= 0; j
< 16; j
++) {
281 GET_BIT(BZ_X_MAPPING_2
, uc
);
282 if (uc
== 1) s
->inUse
[i
* 16 + j
] = True
;
285 if (s
->nInUse
== 0) RETURN(BZ_DATA_ERROR
);
286 alphaSize
= s
->nInUse
+2;
288 /*--- Now the selectors ---*/
289 GET_BITS(BZ_X_SELECTOR_1
, nGroups
, 3);
290 if (nGroups
< 2 || nGroups
> 6) RETURN(BZ_DATA_ERROR
);
291 GET_BITS(BZ_X_SELECTOR_2
, nSelectors
, 15);
292 if (nSelectors
< 1) RETURN(BZ_DATA_ERROR
);
293 for (i
= 0; i
< nSelectors
; i
++) {
296 GET_BIT(BZ_X_SELECTOR_3
, uc
);
299 if (j
>= nGroups
) RETURN(BZ_DATA_ERROR
);
301 s
->selectorMtf
[i
] = j
;
304 /*--- Undo the MTF values for the selectors. ---*/
306 UChar pos
[BZ_N_GROUPS
], tmp
, v
;
307 for (v
= 0; v
< nGroups
; v
++) pos
[v
] = v
;
309 for (i
= 0; i
< nSelectors
; i
++) {
310 v
= s
->selectorMtf
[i
];
312 while (v
> 0) { pos
[v
] = pos
[v
-1]; v
--; }
314 s
->selector
[i
] = tmp
;
318 /*--- Now the coding tables ---*/
319 for (t
= 0; t
< nGroups
; t
++) {
320 GET_BITS(BZ_X_CODING_1
, curr
, 5);
321 for (i
= 0; i
< alphaSize
; i
++) {
323 if (curr
< 1 || curr
> 20) RETURN(BZ_DATA_ERROR
);
324 GET_BIT(BZ_X_CODING_2
, uc
);
326 GET_BIT(BZ_X_CODING_3
, uc
);
327 if (uc
== 0) curr
++; else curr
--;
333 /*--- Create the Huffman decoding tables ---*/
334 for (t
= 0; t
< nGroups
; t
++) {
337 for (i
= 0; i
< alphaSize
; i
++) {
338 if (s
->len
[t
][i
] > maxLen
) maxLen
= s
->len
[t
][i
];
339 if (s
->len
[t
][i
] < minLen
) minLen
= s
->len
[t
][i
];
341 BZ2_hbCreateDecodeTables (
346 minLen
, maxLen
, alphaSize
348 s
->minLens
[t
] = minLen
;
351 /*--- Now the MTF values ---*/
354 nblockMAX
= 100000 * s
->blockSize100k
;
358 for (i
= 0; i
<= 255; i
++) s
->unzftab
[i
] = 0;
364 for (ii
= 256 / MTFL_SIZE
- 1; ii
>= 0; ii
--) {
365 for (jj
= MTFL_SIZE
-1; jj
>= 0; jj
--) {
366 s
->mtfa
[kk
] = (UChar
)(ii
* MTFL_SIZE
+ jj
);
369 s
->mtfbase
[ii
] = kk
+ 1;
372 /*-- end MTF init --*/
375 GET_MTF_VAL(BZ_X_MTF_1
, BZ_X_MTF_2
, nextSym
);
379 if (nextSym
== EOB
) break;
381 if (nextSym
== BZ_RUNA
|| nextSym
== BZ_RUNB
) {
386 /* Check that N doesn't get too big, so that es doesn't
387 go negative. The maximum value that can be
388 RUNA/RUNB encoded is equal to the block size (post
389 the initial RLE), viz, 900k, so bounding N at 2
390 million should guard against overflow without
391 rejecting any legitimate inputs. */
392 if (N
>= 2*1024*1024) RETURN(BZ_DATA_ERROR
);
393 if (nextSym
== BZ_RUNA
) es
= es
+ (0+1) * N
; else
394 if (nextSym
== BZ_RUNB
) es
= es
+ (1+1) * N
;
396 GET_MTF_VAL(BZ_X_MTF_3
, BZ_X_MTF_4
, nextSym
);
398 while (nextSym
== BZ_RUNA
|| nextSym
== BZ_RUNB
);
401 uc
= s
->seqToUnseq
[ s
->mtfa
[s
->mtfbase
[0]] ];
402 s
->unzftab
[uc
] += es
;
404 if (s
->smallDecompress
)
406 if (nblock
>= nblockMAX
) RETURN(BZ_DATA_ERROR
);
407 s
->ll16
[nblock
] = (UInt16
)uc
;
413 if (nblock
>= nblockMAX
) RETURN(BZ_DATA_ERROR
);
414 s
->tt
[nblock
] = (UInt32
)uc
;
423 if (nblock
>= nblockMAX
) RETURN(BZ_DATA_ERROR
);
425 /*-- uc = MTF ( nextSym-1 ) --*/
427 Int32 ii
, jj
, kk
, pp
, lno
, off
;
429 nn
= (UInt32
)(nextSym
- 1);
431 if (nn
< MTFL_SIZE
) {
432 /* avoid general-case expense */
437 s
->mtfa
[(z
) ] = s
->mtfa
[(z
)-1];
438 s
->mtfa
[(z
)-1] = s
->mtfa
[(z
)-2];
439 s
->mtfa
[(z
)-2] = s
->mtfa
[(z
)-3];
440 s
->mtfa
[(z
)-3] = s
->mtfa
[(z
)-4];
444 s
->mtfa
[(pp
+nn
)] = s
->mtfa
[(pp
+nn
)-1]; nn
--;
449 lno
= nn
/ MTFL_SIZE
;
450 off
= nn
% MTFL_SIZE
;
451 pp
= s
->mtfbase
[lno
] + off
;
453 while (pp
> s
->mtfbase
[lno
]) {
454 s
->mtfa
[pp
] = s
->mtfa
[pp
-1]; pp
--;
459 s
->mtfa
[s
->mtfbase
[lno
]]
460 = s
->mtfa
[s
->mtfbase
[lno
-1] + MTFL_SIZE
- 1];
464 s
->mtfa
[s
->mtfbase
[0]] = uc
;
465 if (s
->mtfbase
[0] == 0) {
467 for (ii
= 256 / MTFL_SIZE
-1; ii
>= 0; ii
--) {
468 for (jj
= MTFL_SIZE
-1; jj
>= 0; jj
--) {
469 s
->mtfa
[kk
] = s
->mtfa
[s
->mtfbase
[ii
] + jj
];
472 s
->mtfbase
[ii
] = kk
+ 1;
477 /*-- end uc = MTF ( nextSym-1 ) --*/
479 s
->unzftab
[s
->seqToUnseq
[uc
]]++;
480 if (s
->smallDecompress
)
481 s
->ll16
[nblock
] = (UInt16
)(s
->seqToUnseq
[uc
]); else
482 s
->tt
[nblock
] = (UInt32
)(s
->seqToUnseq
[uc
]);
485 GET_MTF_VAL(BZ_X_MTF_5
, BZ_X_MTF_6
, nextSym
);
490 /* Now we know what nblock is, we can do a better sanity
493 if (s
->origPtr
< 0 || s
->origPtr
>= nblock
)
494 RETURN(BZ_DATA_ERROR
);
496 /*-- Set up cftab to facilitate generation of T^(-1) --*/
497 /* Check: unzftab entries in range. */
498 for (i
= 0; i
<= 255; i
++) {
499 if (s
->unzftab
[i
] < 0 || s
->unzftab
[i
] > nblock
)
500 RETURN(BZ_DATA_ERROR
);
502 /* Actually generate cftab. */
504 for (i
= 1; i
<= 256; i
++) s
->cftab
[i
] = s
->unzftab
[i
-1];
505 for (i
= 1; i
<= 256; i
++) s
->cftab
[i
] += s
->cftab
[i
-1];
506 /* Check: cftab entries in range. */
507 for (i
= 0; i
<= 256; i
++) {
508 if (s
->cftab
[i
] < 0 || s
->cftab
[i
] > nblock
) {
509 /* s->cftab[i] can legitimately be == nblock */
510 RETURN(BZ_DATA_ERROR
);
513 /* Check: cftab entries non-descending. */
514 for (i
= 1; i
<= 256; i
++) {
515 if (s
->cftab
[i
-1] > s
->cftab
[i
]) {
516 RETURN(BZ_DATA_ERROR
);
520 s
->state_out_len
= 0;
522 BZ_INITIALISE_CRC ( s
->calculatedBlockCRC
);
523 s
->state
= BZ_X_OUTPUT
;
524 if (s
->verbosity
>= 2) VPrintf0 ( "rt+rld" );
526 if (s
->smallDecompress
) {
528 /*-- Make a copy of cftab, used in generation of T --*/
529 for (i
= 0; i
<= 256; i
++) s
->cftabCopy
[i
] = s
->cftab
[i
];
531 /*-- compute the T vector --*/
532 for (i
= 0; i
< nblock
; i
++) {
533 uc
= (UChar
)(s
->ll16
[i
]);
534 SET_LL(i
, s
->cftabCopy
[uc
]);
538 /*-- Compute T^(-1) by pointer reversal on T --*/
542 Int32 tmp
= GET_LL(j
);
547 while (i
!= s
->origPtr
);
549 s
->tPos
= s
->origPtr
;
551 if (s
->blockRandomised
) {
553 BZ_GET_SMALL(s
->k0
); s
->nblock_used
++;
554 BZ_RAND_UPD_MASK
; s
->k0
^= BZ_RAND_MASK
;
556 BZ_GET_SMALL(s
->k0
); s
->nblock_used
++;
561 /*-- compute the T^(-1) vector --*/
562 for (i
= 0; i
< nblock
; i
++) {
563 uc
= (UChar
)(s
->tt
[i
] & 0xff);
564 s
->tt
[s
->cftab
[uc
]] |= (i
<< 8);
568 s
->tPos
= s
->tt
[s
->origPtr
] >> 8;
570 if (s
->blockRandomised
) {
572 BZ_GET_FAST(s
->k0
); s
->nblock_used
++;
573 BZ_RAND_UPD_MASK
; s
->k0
^= BZ_RAND_MASK
;
575 BZ_GET_FAST(s
->k0
); s
->nblock_used
++;
586 GET_UCHAR(BZ_X_ENDHDR_2
, uc
);
587 if (uc
!= 0x72) RETURN(BZ_DATA_ERROR
);
588 GET_UCHAR(BZ_X_ENDHDR_3
, uc
);
589 if (uc
!= 0x45) RETURN(BZ_DATA_ERROR
);
590 GET_UCHAR(BZ_X_ENDHDR_4
, uc
);
591 if (uc
!= 0x38) RETURN(BZ_DATA_ERROR
);
592 GET_UCHAR(BZ_X_ENDHDR_5
, uc
);
593 if (uc
!= 0x50) RETURN(BZ_DATA_ERROR
);
594 GET_UCHAR(BZ_X_ENDHDR_6
, uc
);
595 if (uc
!= 0x90) RETURN(BZ_DATA_ERROR
);
597 s
->storedCombinedCRC
= 0;
598 GET_UCHAR(BZ_X_CCRC_1
, uc
);
599 s
->storedCombinedCRC
= (s
->storedCombinedCRC
<< 8) | ((UInt32
)uc
);
600 GET_UCHAR(BZ_X_CCRC_2
, uc
);
601 s
->storedCombinedCRC
= (s
->storedCombinedCRC
<< 8) | ((UInt32
)uc
);
602 GET_UCHAR(BZ_X_CCRC_3
, uc
);
603 s
->storedCombinedCRC
= (s
->storedCombinedCRC
<< 8) | ((UInt32
)uc
);
604 GET_UCHAR(BZ_X_CCRC_4
, uc
);
605 s
->storedCombinedCRC
= (s
->storedCombinedCRC
<< 8) | ((UInt32
)uc
);
607 s
->state
= BZ_X_IDLE
;
608 RETURN(BZ_STREAM_END
);
610 default: AssertH ( False
, 4001 );
613 AssertH ( False
, 4002 );
615 save_state_and_return
:
620 s
->save_alphaSize
= alphaSize
;
621 s
->save_nGroups
= nGroups
;
622 s
->save_nSelectors
= nSelectors
;
624 s
->save_groupNo
= groupNo
;
625 s
->save_groupPos
= groupPos
;
626 s
->save_nextSym
= nextSym
;
627 s
->save_nblockMAX
= nblockMAX
;
628 s
->save_nblock
= nblock
;
637 s
->save_gMinlen
= gMinlen
;
638 s
->save_gLimit
= gLimit
;
639 s
->save_gBase
= gBase
;
640 s
->save_gPerm
= gPerm
;
646 /*-------------------------------------------------------------*/
647 /*--- end decompress.c ---*/
648 /*-------------------------------------------------------------*/