1 /* Modified for busybox by Glenn McGrath <bug1@optushome.com.au> */
2 /* Added support output to stdout by Thomas Lundquist <thomasez@zelow.no> */
4 This file is a part of bzip2 and/or libbzip2, a program and
5 library for lossless, block-sorting data compression.
7 Copyright (C) 1996-2000 Julian R Seward. All rights reserved.
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions
13 1. Redistributions of source code must retain the above copyright
14 notice, this list of conditions and the following disclaimer.
16 2. The origin of this software must not be misrepresented; you must
17 not claim that you wrote the original software. If you use this
18 software in a product, an acknowledgment in the product
19 documentation would be appreciated but is not required.
21 3. Altered source versions must be plainly marked as such, and must
22 not be misrepresented as being the original software.
24 4. The name of the author may not be used to endorse or promote
25 products derived from this software without specific prior written
28 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
29 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
30 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
31 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
32 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
33 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
34 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
35 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
36 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
37 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
38 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
40 Julian Seward, Cambridge, UK.
42 bzip2/libbzip2 version 1.0 of 21 March 2000
44 This program is based on (at least) the work of:
54 For more information on these sources, see the manual.
67 #define MTFA_SIZE 4096
71 #define BZ_MAX_ALPHA_SIZE 258
74 #define BZ_STREAM_END 4
75 #define BZ_SEQUENCE_ERROR (-1)
76 #define BZ_DATA_ERROR (-4)
77 #define BZ_DATA_ERROR_MAGIC (-5)
78 #define BZ_IO_ERROR (-6)
79 #define BZ_UNEXPECTED_EOF (-7)
84 #define BZ_MAX_UNUSED 5000
85 #define FILE_NAME_LEN 1034
86 /*-- states for decompression. --*/
91 #define BZ_X_MAGIC_1 10
92 #define BZ_X_MAGIC_2 11
93 #define BZ_X_MAGIC_3 12
94 #define BZ_X_MAGIC_4 13
95 #define BZ_X_BLKHDR_1 14
96 #define BZ_X_BLKHDR_2 15
97 #define BZ_X_BLKHDR_3 16
98 #define BZ_X_BLKHDR_4 17
99 #define BZ_X_BLKHDR_5 18
100 #define BZ_X_BLKHDR_6 19
101 #define BZ_X_BCRC_1 20
102 #define BZ_X_BCRC_2 21
103 #define BZ_X_BCRC_3 22
104 #define BZ_X_BCRC_4 23
105 #define BZ_X_RANDBIT 24
106 #define BZ_X_ORIGPTR_1 25
107 #define BZ_X_ORIGPTR_2 26
108 #define BZ_X_ORIGPTR_3 27
109 #define BZ_X_MAPPING_1 28
110 #define BZ_X_MAPPING_2 29
111 #define BZ_X_SELECTOR_1 30
112 #define BZ_X_SELECTOR_2 31
113 #define BZ_X_SELECTOR_3 32
114 #define BZ_X_CODING_1 33
115 #define BZ_X_CODING_2 34
116 #define BZ_X_CODING_3 35
117 #define BZ_X_MTF_1 36
118 #define BZ_X_MTF_2 37
119 #define BZ_X_MTF_3 38
120 #define BZ_X_MTF_4 39
121 #define BZ_X_MTF_5 40
122 #define BZ_X_MTF_6 41
123 #define BZ_X_ENDHDR_2 42
124 #define BZ_X_ENDHDR_3 43
125 #define BZ_X_ENDHDR_4 44
126 #define BZ_X_ENDHDR_5 45
127 #define BZ_X_ENDHDR_6 46
128 #define BZ_X_CCRC_1 47
129 #define BZ_X_CCRC_2 48
130 #define BZ_X_CCRC_3 49
131 #define BZ_X_CCRC_4 50
133 #define BZ_MAX_CODE_LEN 23
138 unsigned int avail_in;
141 unsigned int avail_out;
150 unsigned char initialisedOk;
151 char buf[BZ_MAX_UNUSED];
156 /*-- Structure holding all the decompression-side stuff. --*/
158 /* pointer back to the struct bz_stream */
161 /* state indicator for this stream */
164 /* for doing the final run-length decoding */
165 unsigned char state_out_ch;
167 unsigned char blockRandomised;
171 /* the buffer for bit stream reading */
175 /* misc administratium */
179 /* for undoing the Burrows-Wheeler transform */
188 /* for undoing the Burrows-Wheeler transform (FAST) */
191 /* stored and calculated CRCs */
192 unsigned int storedBlockCRC;
193 unsigned int storedCombinedCRC;
194 unsigned int calculatedBlockCRC;
195 unsigned int calculatedCombinedCRC;
197 /* map of bytes used in block */
199 unsigned char inUse[256];
200 unsigned char inUse16[16];
201 unsigned char seqToUnseq[256];
203 /* for decoding the MTF values */
204 unsigned char mtfa [MTFA_SIZE];
205 unsigned char selector [2 + (900000 / BZ_G_SIZE)];
206 unsigned char selectorMtf[2 + (900000 / BZ_G_SIZE)];
207 unsigned char len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
208 int mtfbase[256 / MTFL_SIZE];
210 int limit [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
211 int base [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
212 int perm [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
213 int minLens[BZ_N_GROUPS];
215 /* save area for scalars in the main decompress code */
243 char inName[FILE_NAME_LEN];
244 char outName[FILE_NAME_LEN];
247 unsigned char deleteOutputOnInterrupt;
248 FILE *outputHandleJustInCase;
250 int numFilesProcessed;
253 const unsigned int BZ2_crc32Table[256] = {
255 /*-- Ugly, innit? --*/
257 0x00000000L, 0x04c11db7L, 0x09823b6eL, 0x0d4326d9L,
258 0x130476dcL, 0x17c56b6bL, 0x1a864db2L, 0x1e475005L,
259 0x2608edb8L, 0x22c9f00fL, 0x2f8ad6d6L, 0x2b4bcb61L,
260 0x350c9b64L, 0x31cd86d3L, 0x3c8ea00aL, 0x384fbdbdL,
261 0x4c11db70L, 0x48d0c6c7L, 0x4593e01eL, 0x4152fda9L,
262 0x5f15adacL, 0x5bd4b01bL, 0x569796c2L, 0x52568b75L,
263 0x6a1936c8L, 0x6ed82b7fL, 0x639b0da6L, 0x675a1011L,
264 0x791d4014L, 0x7ddc5da3L, 0x709f7b7aL, 0x745e66cdL,
265 0x9823b6e0L, 0x9ce2ab57L, 0x91a18d8eL, 0x95609039L,
266 0x8b27c03cL, 0x8fe6dd8bL, 0x82a5fb52L, 0x8664e6e5L,
267 0xbe2b5b58L, 0xbaea46efL, 0xb7a96036L, 0xb3687d81L,
268 0xad2f2d84L, 0xa9ee3033L, 0xa4ad16eaL, 0xa06c0b5dL,
269 0xd4326d90L, 0xd0f37027L, 0xddb056feL, 0xd9714b49L,
270 0xc7361b4cL, 0xc3f706fbL, 0xceb42022L, 0xca753d95L,
271 0xf23a8028L, 0xf6fb9d9fL, 0xfbb8bb46L, 0xff79a6f1L,
272 0xe13ef6f4L, 0xe5ffeb43L, 0xe8bccd9aL, 0xec7dd02dL,
273 0x34867077L, 0x30476dc0L, 0x3d044b19L, 0x39c556aeL,
274 0x278206abL, 0x23431b1cL, 0x2e003dc5L, 0x2ac12072L,
275 0x128e9dcfL, 0x164f8078L, 0x1b0ca6a1L, 0x1fcdbb16L,
276 0x018aeb13L, 0x054bf6a4L, 0x0808d07dL, 0x0cc9cdcaL,
277 0x7897ab07L, 0x7c56b6b0L, 0x71159069L, 0x75d48ddeL,
278 0x6b93dddbL, 0x6f52c06cL, 0x6211e6b5L, 0x66d0fb02L,
279 0x5e9f46bfL, 0x5a5e5b08L, 0x571d7dd1L, 0x53dc6066L,
280 0x4d9b3063L, 0x495a2dd4L, 0x44190b0dL, 0x40d816baL,
281 0xaca5c697L, 0xa864db20L, 0xa527fdf9L, 0xa1e6e04eL,
282 0xbfa1b04bL, 0xbb60adfcL, 0xb6238b25L, 0xb2e29692L,
283 0x8aad2b2fL, 0x8e6c3698L, 0x832f1041L, 0x87ee0df6L,
284 0x99a95df3L, 0x9d684044L, 0x902b669dL, 0x94ea7b2aL,
285 0xe0b41de7L, 0xe4750050L, 0xe9362689L, 0xedf73b3eL,
286 0xf3b06b3bL, 0xf771768cL, 0xfa325055L, 0xfef34de2L,
287 0xc6bcf05fL, 0xc27dede8L, 0xcf3ecb31L, 0xcbffd686L,
288 0xd5b88683L, 0xd1799b34L, 0xdc3abdedL, 0xd8fba05aL,
289 0x690ce0eeL, 0x6dcdfd59L, 0x608edb80L, 0x644fc637L,
290 0x7a089632L, 0x7ec98b85L, 0x738aad5cL, 0x774bb0ebL,
291 0x4f040d56L, 0x4bc510e1L, 0x46863638L, 0x42472b8fL,
292 0x5c007b8aL, 0x58c1663dL, 0x558240e4L, 0x51435d53L,
293 0x251d3b9eL, 0x21dc2629L, 0x2c9f00f0L, 0x285e1d47L,
294 0x36194d42L, 0x32d850f5L, 0x3f9b762cL, 0x3b5a6b9bL,
295 0x0315d626L, 0x07d4cb91L, 0x0a97ed48L, 0x0e56f0ffL,
296 0x1011a0faL, 0x14d0bd4dL, 0x19939b94L, 0x1d528623L,
297 0xf12f560eL, 0xf5ee4bb9L, 0xf8ad6d60L, 0xfc6c70d7L,
298 0xe22b20d2L, 0xe6ea3d65L, 0xeba91bbcL, 0xef68060bL,
299 0xd727bbb6L, 0xd3e6a601L, 0xdea580d8L, 0xda649d6fL,
300 0xc423cd6aL, 0xc0e2d0ddL, 0xcda1f604L, 0xc960ebb3L,
301 0xbd3e8d7eL, 0xb9ff90c9L, 0xb4bcb610L, 0xb07daba7L,
302 0xae3afba2L, 0xaafbe615L, 0xa7b8c0ccL, 0xa379dd7bL,
303 0x9b3660c6L, 0x9ff77d71L, 0x92b45ba8L, 0x9675461fL,
304 0x8832161aL, 0x8cf30badL, 0x81b02d74L, 0x857130c3L,
305 0x5d8a9099L, 0x594b8d2eL, 0x5408abf7L, 0x50c9b640L,
306 0x4e8ee645L, 0x4a4ffbf2L, 0x470cdd2bL, 0x43cdc09cL,
307 0x7b827d21L, 0x7f436096L, 0x7200464fL, 0x76c15bf8L,
308 0x68860bfdL, 0x6c47164aL, 0x61043093L, 0x65c52d24L,
309 0x119b4be9L, 0x155a565eL, 0x18197087L, 0x1cd86d30L,
310 0x029f3d35L, 0x065e2082L, 0x0b1d065bL, 0x0fdc1becL,
311 0x3793a651L, 0x3352bbe6L, 0x3e119d3fL, 0x3ad08088L,
312 0x2497d08dL, 0x2056cd3aL, 0x2d15ebe3L, 0x29d4f654L,
313 0xc5a92679L, 0xc1683bceL, 0xcc2b1d17L, 0xc8ea00a0L,
314 0xd6ad50a5L, 0xd26c4d12L, 0xdf2f6bcbL, 0xdbee767cL,
315 0xe3a1cbc1L, 0xe760d676L, 0xea23f0afL, 0xeee2ed18L,
316 0xf0a5bd1dL, 0xf464a0aaL, 0xf9278673L, 0xfde69bc4L,
317 0x89b8fd09L, 0x8d79e0beL, 0x803ac667L, 0x84fbdbd0L,
318 0x9abc8bd5L, 0x9e7d9662L, 0x933eb0bbL, 0x97ffad0cL,
319 0xafb010b1L, 0xab710d06L, 0xa6322bdfL, 0xa2f33668L,
320 0xbcb4666dL, 0xb8757bdaL, 0xb5365d03L, 0xb1f740b4L
323 static void bz_rand_udp_mask(DState *s)
325 if (s->rNToGo == 0) {
326 s->rNToGo = BZ2_rNums[s->rTPos];
328 if (s->rTPos == 512) {
335 static unsigned char myfeof(FILE *f)
345 static void BZ2_hbCreateDecodeTables(int *limit, int *base, int *perm, unsigned char *length, int minLen, int maxLen, int alphaSize )
350 for (i = minLen; i <= maxLen; i++) {
351 for (j = 0; j < alphaSize; j++) {
352 if (length[j] == i) {
359 for (i = 0; i < BZ_MAX_CODE_LEN; i++) {
363 for (i = 0; i < alphaSize; i++) {
367 for (i = 1; i < BZ_MAX_CODE_LEN; i++) {
368 base[i] += base[i-1];
371 for (i = 0; i < BZ_MAX_CODE_LEN; i++) {
376 for (i = minLen; i <= maxLen; i++) {
377 vec += (base[i+1] - base[i]);
381 for (i = minLen + 1; i <= maxLen; i++) {
382 base[i] = ((limit[i-1] + 1) << 1) - base[i];
387 static int get_bits(DState *s, int *vvv, char nnn)
390 if (s->bsLive >= nnn) {
391 *vvv = (s->bsBuff >> (s->bsLive-nnn)) & ((1 << nnn)-1);
395 if (s->strm->avail_in == 0) {
398 s->bsBuff = (s->bsBuff << 8) | ((unsigned int) (*((unsigned char*)(s->strm->next_in))));
406 static int bz_get_fast(DState *s)
409 s->tPos = s->tt[s->tPos];
410 cccc = (unsigned char)(s->tPos & 0xff);
415 /*---------------------------------------------------*/
416 static inline int BZ2_decompress(DState *s)
422 /* stuff that needs to be saved/restored */
449 int get_mtf_val_init(void)
453 if (groupNo >= nSelectors) {
454 retVal = BZ_DATA_ERROR;
457 groupPos = BZ_G_SIZE;
458 gSel = s->selector[groupNo];
459 gMinlen = s->minLens[gSel];
460 gLimit = &(s->limit[gSel][0]);
461 gPerm = &(s->perm[gSel][0]);
462 gBase = &(s->base[gSel][0]);
469 if (s->state == BZ_X_MAGIC_1) {
470 /*initialise the save area*/
474 s->save_alphaSize = 0;
476 s->save_nSelectors = 0;
479 s->save_groupPos = 0;
481 s->save_nblockMAX = 0;
492 s->save_gLimit = NULL;
493 s->save_gBase = NULL;
494 s->save_gPerm = NULL;
497 /*restore from the save area*/
501 alphaSize = s->save_alphaSize;
502 nGroups = s->save_nGroups;
503 nSelectors = s->save_nSelectors;
505 groupNo = s->save_groupNo;
506 groupPos = s->save_groupPos;
507 nextSym = s->save_nextSym;
508 nblockMAX = s->save_nblockMAX;
509 nblock = s->save_nblock;
518 gMinlen = s->save_gMinlen;
519 gLimit = s->save_gLimit;
520 gBase = s->save_gBase;
521 gPerm = s->save_gPerm;
524 switch_val = s->state;
525 switch (switch_val) {
527 s->state = BZ_X_MAGIC_1;
528 if (! get_bits(s, &uc, 8)) {
530 goto save_state_and_return;
533 retVal = BZ_DATA_ERROR_MAGIC;
534 goto save_state_and_return;
538 s->state = BZ_X_MAGIC_2;
539 if (! get_bits(s, &uc, 8)) {
541 goto save_state_and_return;
544 retVal = BZ_DATA_ERROR_MAGIC;
545 goto save_state_and_return;
549 s->state = BZ_X_MAGIC_3;
550 if (! get_bits(s, &uc, 8)) {
552 goto save_state_and_return;
555 retVal = BZ_DATA_ERROR_MAGIC;
556 goto save_state_and_return;
560 s->state = BZ_X_MAGIC_4;
561 if (! get_bits(s, &s->blockSize100k, 8)) {
563 goto save_state_and_return;
565 if ((s->blockSize100k < '1') || (s->blockSize100k > '9')) {
566 retVal = BZ_DATA_ERROR_MAGIC;
567 goto save_state_and_return;
569 s->blockSize100k -= '0';
571 s->tt = xmalloc(s->blockSize100k * 100000 * sizeof(int));
574 s->state = BZ_X_BLKHDR_1;
575 if (! get_bits(s, &uc, 8)) {
577 goto save_state_and_return;
584 retVal = BZ_DATA_ERROR;
585 goto save_state_and_return;
589 s->state = BZ_X_BLKHDR_2;
590 if (! get_bits(s, &uc, 8)) {
592 goto save_state_and_return;
595 retVal = BZ_DATA_ERROR;
596 goto save_state_and_return;
600 s->state = BZ_X_BLKHDR_3;
601 if (! get_bits(s, &uc, 8)) {
603 goto save_state_and_return;
606 retVal = BZ_DATA_ERROR;
607 goto save_state_and_return;
611 s->state = BZ_X_BLKHDR_4;
612 if (! get_bits(s, &uc, 8)) {
614 goto save_state_and_return;
617 retVal = BZ_DATA_ERROR;
618 goto save_state_and_return;
622 s->state = BZ_X_BLKHDR_5;
623 if (! get_bits(s, &uc, 8)) {
625 goto save_state_and_return;
628 retVal = BZ_DATA_ERROR;
629 goto save_state_and_return;
633 s->state = BZ_X_BLKHDR_6;
634 if (! get_bits(s, &uc, 8)) {
636 goto save_state_and_return;
639 retVal = BZ_DATA_ERROR;
640 goto save_state_and_return;
644 s->storedBlockCRC = 0;
647 s->state = BZ_X_BCRC_1;
648 if (! get_bits(s, &uc, 8)) {
650 goto save_state_and_return;
652 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
655 s->state = BZ_X_BCRC_2;
656 if (! get_bits(s, &uc, 8)) {
658 goto save_state_and_return;
660 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
663 s->state = BZ_X_BCRC_3;
664 if (! get_bits(s, &uc, 8)) {
666 goto save_state_and_return;
668 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
671 s->state = BZ_X_BCRC_4;
672 if (! get_bits(s, &uc, 8)) {
674 goto save_state_and_return;
676 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
679 s->state = BZ_X_RANDBIT;
681 int tmp = s->blockRandomised;
682 const int ret = get_bits(s, &tmp, 1);
683 s->blockRandomised = tmp;
686 goto save_state_and_return;
693 s->state = BZ_X_ORIGPTR_1;
694 if (! get_bits(s, &uc, 8)) {
696 goto save_state_and_return;
698 s->origPtr = (s->origPtr << 8) | ((int)uc);
701 s->state = BZ_X_ORIGPTR_2;
702 if (! get_bits(s, &uc, 8)) {
704 goto save_state_and_return;
706 s->origPtr = (s->origPtr << 8) | ((int)uc);
709 s->state = BZ_X_ORIGPTR_3;
710 if (! get_bits(s, &uc, 8)) {
712 goto save_state_and_return;
714 s->origPtr = (s->origPtr << 8) | ((int)uc);
716 if (s->origPtr < 0) {
717 retVal = BZ_DATA_ERROR;
718 goto save_state_and_return;
720 if (s->origPtr > 10 + 100000*s->blockSize100k) {
721 retVal = BZ_DATA_ERROR;
722 goto save_state_and_return;
725 /*--- Receive the mapping table ---*/
727 for (i = 0; i < 16; i++) {
728 s->state = BZ_X_MAPPING_1;
729 if (! get_bits(s, &uc, 1)) {
731 goto save_state_and_return;
734 s->inUse16[i] = TRUE;
736 s->inUse16[i] = FALSE;
740 for (i = 0; i < 256; i++) {
744 for (i = 0; i < 16; i++) {
746 for (j = 0; j < 16; j++) {
748 s->state = BZ_X_MAPPING_2;
749 if (! get_bits(s, &uc, 1)) {
751 goto save_state_and_return;
754 s->inUse[i * 16 + j] = TRUE;
761 for (i = 0; i < 256; i++) {
763 s->seqToUnseq[s->nInUse] = i;
767 if (s->nInUse == 0) {
768 retVal = BZ_DATA_ERROR;
769 goto save_state_and_return;
771 alphaSize = s->nInUse+2;
773 /*--- Now the selectors ---*/
774 case BZ_X_SELECTOR_1:
775 s->state = BZ_X_SELECTOR_1;
776 if (! get_bits(s, &nGroups, 3)) {
778 goto save_state_and_return;
780 if (nGroups < 2 || nGroups > 6) {
781 retVal = BZ_DATA_ERROR;
782 goto save_state_and_return;
785 case BZ_X_SELECTOR_2:
786 s->state = BZ_X_SELECTOR_2;
787 if (! get_bits(s, &nSelectors, 15)) {
789 goto save_state_and_return;
791 if (nSelectors < 1) {
792 retVal = BZ_DATA_ERROR;
793 goto save_state_and_return;
798 for (i = 0; i < nSelectors; i++) {
801 case BZ_X_SELECTOR_3:
802 s->state = BZ_X_SELECTOR_3;
803 if (! get_bits(s, &uc, 1)) {
805 goto save_state_and_return;
812 retVal = BZ_DATA_ERROR;
813 goto save_state_and_return;
816 s->selectorMtf[i] = j;
819 /*--- Undo the MTF values for the selectors. ---*/
821 unsigned char pos[BZ_N_GROUPS], tmp, v;
822 for (v = 0; v < nGroups; v++) {
825 for (i = 0; i < nSelectors; i++) {
826 v = s->selectorMtf[i];
833 s->selector[i] = tmp;
837 /*--- Now the coding tables ---*/
838 for (t = 0; t < nGroups; t++) {
840 s->state = BZ_X_CODING_1;
841 if (! get_bits(s, &curr, 5)) {
843 goto save_state_and_return;
845 for (i = 0; i < alphaSize; i++) {
847 if (curr < 1 || curr > 20) {
848 retVal = BZ_DATA_ERROR;
849 goto save_state_and_return;
853 s->state = BZ_X_CODING_2;
854 if (! get_bits(s, &uc, 1)) {
856 goto save_state_and_return;
863 s->state = BZ_X_CODING_3;
864 if (! get_bits(s, &uc, 1)) {
866 goto save_state_and_return;
878 /*--- Create the Huffman decoding tables ---*/
879 for (t = 0; t < nGroups; t++) {
882 for (i = 0; i < alphaSize; i++) {
883 if (s->len[t][i] > maxLen) {
884 maxLen = s->len[t][i];
886 if (s->len[t][i] < minLen) {
887 minLen = s->len[t][i];
891 BZ2_hbCreateDecodeTables (
896 minLen, maxLen, alphaSize
900 s->minLens[t] = minLen;
903 /*--- Now the MTF values ---*/
906 nblockMAX = 100000 * s->blockSize100k;
910 for (i = 0; i <= 255; i++) {
917 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
918 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
919 s->mtfa[kk] = (unsigned char)(ii * MTFL_SIZE + jj);
922 s->mtfbase[ii] = kk + 1;
925 /*-- end MTF init --*/
929 if (! get_mtf_val_init()) {
930 goto save_state_and_return;
933 s->state = BZ_X_MTF_1;
934 if (! get_bits(s, &zvec, zn)) {
936 goto save_state_and_return;
939 if (zn > 20 /* the longest code */) {
940 retVal = BZ_DATA_ERROR;
941 goto save_state_and_return;
943 if (zvec <= gLimit[zn]) {
949 s->state = BZ_X_MTF_2;
950 if (! get_bits(s, &zj, 1)) {
952 goto save_state_and_return;
954 zvec = (zvec << 1) | zj;
956 if (zvec - gBase[zn] < 0 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) {
957 retVal = BZ_DATA_ERROR;
958 goto save_state_and_return;
960 nextSym = gPerm[zvec - gBase[zn]];
963 if (nextSym == EOB) {
967 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
971 if (nextSym == BZ_RUNA) {
974 if (nextSym == BZ_RUNB) {
979 if (! get_mtf_val_init()) {
980 goto save_state_and_return;
983 s->state = BZ_X_MTF_3;
984 if (! get_bits(s, &zvec, zn)) {
986 goto save_state_and_return;
989 if (zn > 20 /* the longest code */) {
990 retVal = BZ_DATA_ERROR;
991 goto save_state_and_return;
993 if (zvec <= gLimit[zn]) {
999 s->state = BZ_X_MTF_4;
1000 if (! get_bits(s, &zj, 1)) {
1002 goto save_state_and_return;
1004 zvec = (zvec << 1) | zj;
1006 if (zvec - gBase[zn] < 0 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) {
1007 retVal = BZ_DATA_ERROR;
1008 goto save_state_and_return;
1011 nextSym = gPerm[zvec - gBase[zn]];
1013 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
1016 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
1017 s->unzftab[uc] += es;
1020 if (nblock >= nblockMAX) {
1021 retVal = BZ_DATA_ERROR;
1022 goto save_state_and_return;
1024 s->tt[nblock] = (unsigned int)uc;
1030 if (nblock >= nblockMAX) {
1031 retVal = BZ_DATA_ERROR;
1032 goto save_state_and_return;
1034 /*-- uc = MTF ( nextSym-1 ) --*/
1036 int ii, jj, kk, pp, lno, off;
1038 nn = (unsigned int)(nextSym - 1);
1040 if (nn < MTFL_SIZE) {
1041 /* avoid general-case expense */
1043 uc = s->mtfa[pp+nn];
1046 s->mtfa[(z) ] = s->mtfa[(z)-1];
1047 s->mtfa[(z)-1] = s->mtfa[(z)-2];
1048 s->mtfa[(z)-2] = s->mtfa[(z)-3];
1049 s->mtfa[(z)-3] = s->mtfa[(z)-4];
1053 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
1058 lno = nn / MTFL_SIZE;
1059 off = nn % MTFL_SIZE;
1060 pp = s->mtfbase[lno] + off;
1062 while (pp > s->mtfbase[lno]) {
1063 s->mtfa[pp] = s->mtfa[pp-1];
1069 s->mtfa[s->mtfbase[lno]] = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
1073 s->mtfa[s->mtfbase[0]] = uc;
1074 if (s->mtfbase[0] == 0) {
1076 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
1077 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
1078 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
1081 s->mtfbase[ii] = kk + 1;
1086 /*-- end uc = MTF ( nextSym-1 ) --*/
1088 s->unzftab[s->seqToUnseq[uc]]++;
1089 s->tt[nblock] = (unsigned int)(s->seqToUnseq[uc]);
1092 if (! get_mtf_val_init()) {
1093 goto save_state_and_return;
1096 s->state = BZ_X_MTF_5;
1097 if (! get_bits(s, &zvec, zn)) {
1099 goto save_state_and_return;
1102 if (zn > 20 /* the longest code */) {
1103 retVal = BZ_DATA_ERROR;
1104 goto save_state_and_return;
1106 if (zvec <= gLimit[zn]) {
1112 s->state = BZ_X_MTF_6;
1113 if (! get_bits(s, &zj, 1)) {
1115 goto save_state_and_return;
1117 zvec = (zvec << 1) | zj;
1119 if (zvec - gBase[zn] < 0 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) {
1120 retVal = BZ_DATA_ERROR;
1121 goto save_state_and_return;
1123 nextSym = gPerm[zvec - gBase[zn]];
1128 /* Now we know what nblock is, we can do a better sanity
1129 check on s->origPtr.
1131 if (s->origPtr < 0 || s->origPtr >= nblock) {
1132 retVal = BZ_DATA_ERROR;
1133 goto save_state_and_return;
1135 s->state_out_len = 0;
1136 s->state_out_ch = 0;
1137 s->calculatedBlockCRC = 0xffffffffL;
1138 s->state = BZ_X_OUTPUT;
1140 /*-- Set up cftab to facilitate generation of T^(-1) --*/
1142 for (i = 1; i <= 256; i++) {
1143 s->cftab[i] = s->unzftab[i-1];
1145 for (i = 1; i <= 256; i++) {
1146 s->cftab[i] += s->cftab[i-1];
1149 /*-- compute the T^(-1) vector --*/
1150 for (i = 0; i < nblock; i++) {
1151 uc = (unsigned char)(s->tt[i] & 0xff);
1152 s->tt[s->cftab[uc]] |= (i << 8);
1156 s->tPos = s->tt[s->origPtr] >> 8;
1158 if (s->blockRandomised) {
1161 s->k0 = bz_get_fast(s);
1164 bz_rand_udp_mask(s);
1165 s->k0 ^= ((s->rNToGo == 1) ? 1 : 0);
1167 s->k0 = bz_get_fast(s);
1172 goto save_state_and_return;
1176 s->state = BZ_X_ENDHDR_2;
1177 if (! get_bits(s, &uc, 8)) {
1179 goto save_state_and_return;
1182 retVal = BZ_DATA_ERROR;
1183 goto save_state_and_return;
1187 s->state = BZ_X_ENDHDR_3;
1188 if (! get_bits(s, &uc, 8)) {
1190 goto save_state_and_return;
1193 retVal = BZ_DATA_ERROR;
1194 goto save_state_and_return;
1198 s->state = BZ_X_ENDHDR_4;
1199 if (! get_bits(s, &uc, 8)) {
1201 goto save_state_and_return;
1204 retVal = BZ_DATA_ERROR;
1205 goto save_state_and_return;
1209 s->state = BZ_X_ENDHDR_5;
1210 if (! get_bits(s, &uc, 8)) {
1212 goto save_state_and_return;
1215 retVal = BZ_DATA_ERROR;
1216 goto save_state_and_return;
1220 s->state = BZ_X_ENDHDR_6;
1221 if (! get_bits(s, &uc, 8)) {
1223 goto save_state_and_return;
1226 retVal = BZ_DATA_ERROR;
1227 goto save_state_and_return;
1229 s->storedCombinedCRC = 0;
1232 s->state = BZ_X_CCRC_1;
1233 if (! get_bits(s, &uc, 8)) {
1235 goto save_state_and_return;
1237 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1239 s->state = BZ_X_CCRC_2;
1240 if (! get_bits(s, &uc, 8)) {
1242 goto save_state_and_return;
1244 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1247 s->state = BZ_X_CCRC_3;
1248 if (! get_bits(s, &uc, 8)) {
1250 goto save_state_and_return;
1252 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1255 s->state = BZ_X_CCRC_4;
1256 if (! get_bits(s, &uc, 8)) {
1258 goto save_state_and_return;
1260 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1262 s->state = BZ_X_IDLE;
1263 retVal = BZ_STREAM_END;
1264 goto save_state_and_return;
1268 save_state_and_return:
1272 s->save_alphaSize = alphaSize;
1273 s->save_nGroups = nGroups;
1274 s->save_nSelectors = nSelectors;
1276 s->save_groupNo = groupNo;
1277 s->save_groupPos = groupPos;
1278 s->save_nextSym = nextSym;
1279 s->save_nblockMAX = nblockMAX;
1280 s->save_nblock = nblock;
1283 s->save_curr = curr;
1286 s->save_zvec = zvec;
1288 s->save_gSel = gSel;
1289 s->save_gMinlen = gMinlen;
1290 s->save_gLimit = gLimit;
1291 s->save_gBase = gBase;
1292 s->save_gPerm = gPerm;
1297 //int BZ2_bzDecompressInit(bz_stream* strm, int verbosity_level, int small)
1298 static inline int BZ2_bzDecompressInit(bz_stream* strm)
1302 // if (verbosity_level < 0 || verbosity_level > 4) {
1303 // return BZ_PARAM_ERROR;
1305 s = xmalloc(sizeof(DState));
1308 s->state = BZ_X_MAGIC_1;
1311 s->calculatedCombinedCRC = 0;
1318 static void bz_seterr(int eee, int *bzerror, bzFile **bzf)
1320 if (bzerror != NULL) {
1324 (*bzf)->lastErr = eee;
1328 static void BZ2_bzReadClose(int *bzerror, void *b)
1330 bzFile* bzf = (bzFile*)b;
1332 bz_seterr(BZ_OK, bzerror, &bzf);
1334 if (bzf->initialisedOk) {
1335 bz_stream *strm = &(bzf->strm);
1341 if ((s == NULL) || (s->strm != strm)) {
1352 static void unRLE_obuf_to_output_FAST(DState *s)
1356 if (s->blockRandomised) {
1358 /* try to finish existing run */
1360 if (s->strm->avail_out == 0) {
1363 if (s->state_out_len == 0) {
1366 *((unsigned char *)(s->strm->next_out)) = s->state_out_ch;
1367 s->calculatedBlockCRC = (s->calculatedBlockCRC << 8) ^
1368 BZ2_crc32Table[(s->calculatedBlockCRC >> 24) ^
1369 ((unsigned char)s->state_out_ch)];
1371 s->strm->next_out++;
1372 s->strm->avail_out--;
1375 /* can a new run be started? */
1376 if (s->nblock_used == s->save_nblock+1) {
1379 s->state_out_len = 1;
1380 s->state_out_ch = s->k0;
1381 k1 = bz_get_fast(s);
1382 bz_rand_udp_mask(s);
1383 k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1385 if (s->nblock_used == s->save_nblock+1) {
1393 s->state_out_len = 2;
1394 k1 = bz_get_fast(s);
1395 bz_rand_udp_mask(s);
1396 k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1398 if (s->nblock_used == s->save_nblock+1) {
1405 s->state_out_len = 3;
1406 k1 = bz_get_fast(s);
1407 bz_rand_udp_mask(s);
1408 k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1410 if (s->nblock_used == s->save_nblock+1) {
1418 k1 = bz_get_fast(s);
1419 bz_rand_udp_mask(s);
1420 k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1422 s->state_out_len = ((int)k1) + 4;
1423 s->k0 = bz_get_fast(s);
1424 bz_rand_udp_mask(s);
1425 s->k0 ^= ((s->rNToGo == 1) ? 1 : 0);
1430 unsigned int c_calculatedBlockCRC = s->calculatedBlockCRC;
1431 unsigned char c_state_out_ch = s->state_out_ch;
1432 int c_state_out_len = s->state_out_len;
1433 int c_nblock_used = s->nblock_used;
1435 unsigned int *c_tt = s->tt;
1436 unsigned int c_tPos = s->tPos;
1437 char *cs_next_out = s->strm->next_out;
1438 unsigned int cs_avail_out = s->strm->avail_out;
1441 int s_save_nblockPP = s->save_nblock+1;
1444 /* try to finish existing run */
1445 if (c_state_out_len > 0) {
1447 if (cs_avail_out == 0) {
1450 if (c_state_out_len == 1) {
1453 *((unsigned char *)(cs_next_out)) = c_state_out_ch;
1454 c_calculatedBlockCRC = (c_calculatedBlockCRC << 8) ^
1455 BZ2_crc32Table[(c_calculatedBlockCRC >> 24) ^
1456 ((unsigned char)c_state_out_ch)];
1461 s_state_out_len_eq_one:
1463 if (cs_avail_out == 0) {
1464 c_state_out_len = 1;
1467 *((unsigned char *)(cs_next_out)) = c_state_out_ch;
1468 c_calculatedBlockCRC = (c_calculatedBlockCRC << 8) ^
1469 BZ2_crc32Table[(c_calculatedBlockCRC >> 24) ^
1470 ((unsigned char)c_state_out_ch)];
1475 /* can a new run be started? */
1476 if (c_nblock_used == s_save_nblockPP) {
1477 c_state_out_len = 0; goto return_notr;
1479 c_state_out_ch = c_k0;
1480 c_tPos = c_tt[c_tPos];
1481 k1 = (unsigned char)(c_tPos & 0xff);
1488 goto s_state_out_len_eq_one;
1491 if (c_nblock_used == s_save_nblockPP) {
1492 goto s_state_out_len_eq_one;
1495 c_state_out_len = 2;
1496 c_tPos = c_tt[c_tPos];
1497 k1 = (unsigned char)(c_tPos & 0xff);
1501 if (c_nblock_used == s_save_nblockPP) {
1509 c_state_out_len = 3;
1510 c_tPos = c_tt[c_tPos];
1511 k1 = (unsigned char)(c_tPos & 0xff);
1515 if (c_nblock_used == s_save_nblockPP) {
1523 c_tPos = c_tt[c_tPos];
1524 k1 = (unsigned char)(c_tPos & 0xff);
1528 c_state_out_len = ((int)k1) + 4;
1530 c_tPos = c_tt[c_tPos];
1531 c_k0 = (unsigned char)(c_tPos & 0xff);
1540 s->calculatedBlockCRC = c_calculatedBlockCRC;
1541 s->state_out_ch = c_state_out_ch;
1542 s->state_out_len = c_state_out_len;
1543 s->nblock_used = c_nblock_used;
1547 s->strm->next_out = cs_next_out;
1548 s->strm->avail_out = cs_avail_out;
1553 int BZ2_bzDecompress(bz_stream *strm)
1559 if (s->state == BZ_X_IDLE) {
1560 return BZ_SEQUENCE_ERROR;
1562 if (s->state == BZ_X_OUTPUT) {
1563 unRLE_obuf_to_output_FAST(s);
1564 if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) {
1565 s->calculatedBlockCRC = ~(s->calculatedBlockCRC);
1566 if (s->calculatedBlockCRC != s->storedBlockCRC) {
1567 return BZ_DATA_ERROR;
1569 s->calculatedCombinedCRC = (s->calculatedCombinedCRC << 1) | (s->calculatedCombinedCRC >> 31);
1570 s->calculatedCombinedCRC ^= s->calculatedBlockCRC;
1571 s->state = BZ_X_BLKHDR_1;
1576 if (s->state >= BZ_X_MAGIC_1) {
1577 int r = BZ2_decompress(s);
1578 if (r == BZ_STREAM_END) {
1579 if (s->calculatedCombinedCRC != s->storedCombinedCRC) {
1580 return BZ_DATA_ERROR;
1584 if (s->state != BZ_X_OUTPUT) {
1590 return(0); /*NOTREACHED*/
1593 static inline int BZ2_bzRead(int *bzerror, void *b, void *buf, int len)
1596 bzFile *bzf = (bzFile*)b;
1598 bz_seterr(BZ_OK, bzerror, &bzf);
1601 bz_seterr(BZ_OK, bzerror, &bzf);
1605 bzf->strm.avail_out = len;
1606 bzf->strm.next_out = buf;
1609 if (ferror(bzf->handle)) {
1610 bz_seterr(BZ_IO_ERROR, bzerror, &bzf);
1613 if ((bzf->strm.avail_in == 0) && !myfeof(bzf->handle)) {
1614 n = fread(bzf->buf, sizeof(unsigned char), BZ_MAX_UNUSED, bzf->handle);
1615 if (ferror(bzf->handle)) {
1616 bz_seterr(BZ_IO_ERROR, bzerror, &bzf);
1620 bzf->strm.avail_in = bzf->bufN;
1621 bzf->strm.next_in = bzf->buf;
1624 ret = BZ2_bzDecompress(&(bzf->strm));
1626 if ((ret != BZ_OK) && (ret != BZ_STREAM_END)) {
1627 bz_seterr(ret, bzerror, &bzf);
1631 if ((ret == BZ_OK) && myfeof(bzf->handle) &&
1632 (bzf->strm.avail_in == 0) && (bzf->strm.avail_out > 0)) {
1633 bz_seterr(BZ_UNEXPECTED_EOF, bzerror, &bzf);
1637 if (ret == BZ_STREAM_END) {
1638 bz_seterr(BZ_STREAM_END, bzerror, &bzf);
1639 return(len - bzf->strm.avail_out);
1641 if (bzf->strm.avail_out == 0) {
1642 bz_seterr(BZ_OK, bzerror, &bzf);
1646 return(0); /*not reached*/
1649 static inline void *BZ2_bzReadOpen(int *bzerror, FILE *f, void *unused, int nUnused)
1651 bzFile *bzf = xmalloc(sizeof(bzFile));
1654 bz_seterr(BZ_OK, bzerror, &bzf);
1656 bzf->initialisedOk = FALSE;
1660 ret = BZ2_bzDecompressInit(&(bzf->strm));
1662 bz_seterr(ret, bzerror, &bzf);
1667 while (nUnused > 0) {
1668 bzf->buf[bzf->bufN] = *((unsigned char *)(unused)); bzf->bufN++;
1669 unused = ((void *)( 1 + ((unsigned char *)(unused)) ));
1672 bzf->strm.avail_in = bzf->bufN;
1673 bzf->strm.next_in = bzf->buf;
1675 bzf->initialisedOk = TRUE;
1679 static inline unsigned char uncompressStream(FILE *zStream, FILE *stream)
1681 unsigned char unused[BZ_MAX_UNUSED];
1682 unsigned char *unusedTmp;
1683 unsigned char obuf[5000];
1696 if (ferror(stream)) {
1699 if (ferror(zStream)) {
1704 bzf = BZ2_bzReadOpen(&bzerr, zStream, unused, nUnused);
1705 if (bzf == NULL || bzerr != BZ_OK) {
1710 while (bzerr == BZ_OK) {
1711 nread = BZ2_bzRead(&bzerr, bzf, obuf, 5000);
1712 if (bzerr == BZ_DATA_ERROR_MAGIC) {
1715 if ((bzerr == BZ_OK || bzerr == BZ_STREAM_END) && nread > 0) {
1716 fwrite(obuf, sizeof(unsigned char), nread, stream);
1718 if (ferror(stream)) {
1722 if (bzerr != BZ_STREAM_END) {
1725 nUnused = bzf->strm.avail_in;
1726 unusedTmp = bzf->strm.next_in;
1727 bz_seterr(BZ_OK, &bzerr, &bzf);
1728 for (i = 0; i < nUnused; i++) {
1729 unused[i] = unusedTmp[i];
1731 BZ2_bzReadClose(&bzerr, bzf);
1732 if ((nUnused == 0) && myfeof(zStream)) {
1737 if (ferror(zStream)) {
1740 ret = fclose(zStream);
1744 if (ferror(stream)) {
1747 ret = fflush(stream);
1751 if (stream != stdout) {
1752 ret = fclose(stream);
1760 BZ2_bzReadClose ( &bzerr_dummy, bzf );
1764 error_msg("\n%s: I/O or other error, bailing out. "
1765 "Possible reason follows.\n", applet_name);
1766 perror(applet_name);
1769 error_msg("\n%s: Data integrity error when decompressing.\n", applet_name);
1771 case BZ_UNEXPECTED_EOF:
1772 error_msg("\n%s: Compressed file ends unexpectedly;\n\t"
1773 "perhaps it is corrupted? *Possible* reason follows.\n", applet_name);
1774 perror(applet_name);
1776 case BZ_DATA_ERROR_MAGIC:
1777 if (zStream != stdin) {
1780 if (stream != stdout) {
1783 if (streamNo == 1) {
1790 return(TRUE); /*notreached*/
1793 int bunzip2_main(int argc, char **argv)
1795 const int bunzip_to_stdout = 1;
1796 const int bunzip_force = 2;
1803 char *save_name = NULL;
1804 char *delete_name = NULL;
1806 /* if called as bzcat */
1807 if (strcmp(applet_name, "bzcat") == 0)
1808 flags |= bunzip_to_stdout;
1810 while ((opt = getopt(argc, argv, "cfh")) != -1) {
1813 flags |= bunzip_to_stdout;
1816 flags |= bunzip_force;
1820 show_usage(); /* exit's inside usage */
1824 /* Set input filename and number */
1825 if (argv[optind] == NULL || strcmp(argv[optind], "-") == 0) {
1826 flags |= bunzip_to_stdout;
1829 /* Open input file */
1830 src_stream = xfopen(argv[optind], "r");
1832 save_name = xstrdup(argv[optind]);
1833 if (strcmp(save_name + strlen(save_name) - 4, ".bz2") != 0)
1834 error_msg_and_die("Invalid extension");
1835 save_name[strlen(save_name) - 4] = '\0';
1838 /* Check that the input is sane. */
1839 if (isatty(fileno(src_stream)) && (flags & bunzip_force) == 0)
1840 error_msg_and_die("compressed data not read from terminal. Use -f to force it.");
1842 if (flags & bunzip_to_stdout) {
1843 dst_stream = stdout;
1845 dst_stream = xfopen(save_name, "w");
1848 if (uncompressStream(src_stream, dst_stream)) {
1849 if (!(flags & bunzip_to_stdout))
1850 delete_name = argv[optind];
1851 status = EXIT_SUCCESS;
1853 if (!(flags & bunzip_to_stdout))
1854 delete_name = save_name;
1855 status = EXIT_FAILURE;
1859 if (unlink(delete_name) < 0) {
1860 error_msg_and_die("Couldn't remove %s", delete_name);