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
139 unsigned int avail_in;
142 unsigned int avail_out;
151 unsigned char initialisedOk;
152 char buf[BZ_MAX_UNUSED];
157 /*-- Structure holding all the decompression-side stuff. --*/
159 /* pointer back to the struct bz_stream */
162 /* state indicator for this stream */
165 /* for doing the final run-length decoding */
166 unsigned char state_out_ch;
168 unsigned char blockRandomised;
172 /* the buffer for bit stream reading */
176 /* misc administratium */
180 /* for undoing the Burrows-Wheeler transform */
189 /* for undoing the Burrows-Wheeler transform (FAST) */
192 /* stored and calculated CRCs */
193 unsigned int storedBlockCRC;
194 unsigned int storedCombinedCRC;
195 unsigned int calculatedBlockCRC;
196 unsigned int calculatedCombinedCRC;
198 /* map of bytes used in block */
200 unsigned char inUse[256];
201 unsigned char inUse16[16];
202 unsigned char seqToUnseq[256];
204 /* for decoding the MTF values */
205 unsigned char mtfa [MTFA_SIZE];
206 unsigned char selector [2 + (900000 / BZ_G_SIZE)];
207 unsigned char selectorMtf[2 + (900000 / BZ_G_SIZE)];
208 unsigned char len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
209 int mtfbase[256 / MTFL_SIZE];
211 int limit [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
212 int base [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
213 int perm [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
214 int minLens[BZ_N_GROUPS];
216 /* save area for scalars in the main decompress code */
244 char inName[FILE_NAME_LEN];
245 char outName[FILE_NAME_LEN];
248 unsigned char deleteOutputOnInterrupt;
249 FILE *outputHandleJustInCase;
251 int numFilesProcessed;
254 const unsigned int BZ2_crc32Table[256] = {
256 /*-- Ugly, innit? --*/
258 0x00000000L, 0x04c11db7L, 0x09823b6eL, 0x0d4326d9L,
259 0x130476dcL, 0x17c56b6bL, 0x1a864db2L, 0x1e475005L,
260 0x2608edb8L, 0x22c9f00fL, 0x2f8ad6d6L, 0x2b4bcb61L,
261 0x350c9b64L, 0x31cd86d3L, 0x3c8ea00aL, 0x384fbdbdL,
262 0x4c11db70L, 0x48d0c6c7L, 0x4593e01eL, 0x4152fda9L,
263 0x5f15adacL, 0x5bd4b01bL, 0x569796c2L, 0x52568b75L,
264 0x6a1936c8L, 0x6ed82b7fL, 0x639b0da6L, 0x675a1011L,
265 0x791d4014L, 0x7ddc5da3L, 0x709f7b7aL, 0x745e66cdL,
266 0x9823b6e0L, 0x9ce2ab57L, 0x91a18d8eL, 0x95609039L,
267 0x8b27c03cL, 0x8fe6dd8bL, 0x82a5fb52L, 0x8664e6e5L,
268 0xbe2b5b58L, 0xbaea46efL, 0xb7a96036L, 0xb3687d81L,
269 0xad2f2d84L, 0xa9ee3033L, 0xa4ad16eaL, 0xa06c0b5dL,
270 0xd4326d90L, 0xd0f37027L, 0xddb056feL, 0xd9714b49L,
271 0xc7361b4cL, 0xc3f706fbL, 0xceb42022L, 0xca753d95L,
272 0xf23a8028L, 0xf6fb9d9fL, 0xfbb8bb46L, 0xff79a6f1L,
273 0xe13ef6f4L, 0xe5ffeb43L, 0xe8bccd9aL, 0xec7dd02dL,
274 0x34867077L, 0x30476dc0L, 0x3d044b19L, 0x39c556aeL,
275 0x278206abL, 0x23431b1cL, 0x2e003dc5L, 0x2ac12072L,
276 0x128e9dcfL, 0x164f8078L, 0x1b0ca6a1L, 0x1fcdbb16L,
277 0x018aeb13L, 0x054bf6a4L, 0x0808d07dL, 0x0cc9cdcaL,
278 0x7897ab07L, 0x7c56b6b0L, 0x71159069L, 0x75d48ddeL,
279 0x6b93dddbL, 0x6f52c06cL, 0x6211e6b5L, 0x66d0fb02L,
280 0x5e9f46bfL, 0x5a5e5b08L, 0x571d7dd1L, 0x53dc6066L,
281 0x4d9b3063L, 0x495a2dd4L, 0x44190b0dL, 0x40d816baL,
282 0xaca5c697L, 0xa864db20L, 0xa527fdf9L, 0xa1e6e04eL,
283 0xbfa1b04bL, 0xbb60adfcL, 0xb6238b25L, 0xb2e29692L,
284 0x8aad2b2fL, 0x8e6c3698L, 0x832f1041L, 0x87ee0df6L,
285 0x99a95df3L, 0x9d684044L, 0x902b669dL, 0x94ea7b2aL,
286 0xe0b41de7L, 0xe4750050L, 0xe9362689L, 0xedf73b3eL,
287 0xf3b06b3bL, 0xf771768cL, 0xfa325055L, 0xfef34de2L,
288 0xc6bcf05fL, 0xc27dede8L, 0xcf3ecb31L, 0xcbffd686L,
289 0xd5b88683L, 0xd1799b34L, 0xdc3abdedL, 0xd8fba05aL,
290 0x690ce0eeL, 0x6dcdfd59L, 0x608edb80L, 0x644fc637L,
291 0x7a089632L, 0x7ec98b85L, 0x738aad5cL, 0x774bb0ebL,
292 0x4f040d56L, 0x4bc510e1L, 0x46863638L, 0x42472b8fL,
293 0x5c007b8aL, 0x58c1663dL, 0x558240e4L, 0x51435d53L,
294 0x251d3b9eL, 0x21dc2629L, 0x2c9f00f0L, 0x285e1d47L,
295 0x36194d42L, 0x32d850f5L, 0x3f9b762cL, 0x3b5a6b9bL,
296 0x0315d626L, 0x07d4cb91L, 0x0a97ed48L, 0x0e56f0ffL,
297 0x1011a0faL, 0x14d0bd4dL, 0x19939b94L, 0x1d528623L,
298 0xf12f560eL, 0xf5ee4bb9L, 0xf8ad6d60L, 0xfc6c70d7L,
299 0xe22b20d2L, 0xe6ea3d65L, 0xeba91bbcL, 0xef68060bL,
300 0xd727bbb6L, 0xd3e6a601L, 0xdea580d8L, 0xda649d6fL,
301 0xc423cd6aL, 0xc0e2d0ddL, 0xcda1f604L, 0xc960ebb3L,
302 0xbd3e8d7eL, 0xb9ff90c9L, 0xb4bcb610L, 0xb07daba7L,
303 0xae3afba2L, 0xaafbe615L, 0xa7b8c0ccL, 0xa379dd7bL,
304 0x9b3660c6L, 0x9ff77d71L, 0x92b45ba8L, 0x9675461fL,
305 0x8832161aL, 0x8cf30badL, 0x81b02d74L, 0x857130c3L,
306 0x5d8a9099L, 0x594b8d2eL, 0x5408abf7L, 0x50c9b640L,
307 0x4e8ee645L, 0x4a4ffbf2L, 0x470cdd2bL, 0x43cdc09cL,
308 0x7b827d21L, 0x7f436096L, 0x7200464fL, 0x76c15bf8L,
309 0x68860bfdL, 0x6c47164aL, 0x61043093L, 0x65c52d24L,
310 0x119b4be9L, 0x155a565eL, 0x18197087L, 0x1cd86d30L,
311 0x029f3d35L, 0x065e2082L, 0x0b1d065bL, 0x0fdc1becL,
312 0x3793a651L, 0x3352bbe6L, 0x3e119d3fL, 0x3ad08088L,
313 0x2497d08dL, 0x2056cd3aL, 0x2d15ebe3L, 0x29d4f654L,
314 0xc5a92679L, 0xc1683bceL, 0xcc2b1d17L, 0xc8ea00a0L,
315 0xd6ad50a5L, 0xd26c4d12L, 0xdf2f6bcbL, 0xdbee767cL,
316 0xe3a1cbc1L, 0xe760d676L, 0xea23f0afL, 0xeee2ed18L,
317 0xf0a5bd1dL, 0xf464a0aaL, 0xf9278673L, 0xfde69bc4L,
318 0x89b8fd09L, 0x8d79e0beL, 0x803ac667L, 0x84fbdbd0L,
319 0x9abc8bd5L, 0x9e7d9662L, 0x933eb0bbL, 0x97ffad0cL,
320 0xafb010b1L, 0xab710d06L, 0xa6322bdfL, 0xa2f33668L,
321 0xbcb4666dL, 0xb8757bdaL, 0xb5365d03L, 0xb1f740b4L
324 void bz_rand_udp_mask(DState *s)
326 if (s->rNToGo == 0) {
327 s->rNToGo = BZ2_rNums[s->rTPos];
329 if (s->rTPos == 512) {
336 static unsigned char myfeof(FILE *f)
346 static void cleanUpAndFail(int ec)
350 if ((srcMode == SM_F2F) && (opMode != OM_TEST) && deleteOutputOnInterrupt) {
351 if (outputHandleJustInCase != NULL) {
352 fclose(outputHandleJustInCase);
354 retVal = remove(outName);
356 error_msg("%s: WARNING: deletion of output file (apparently) failed.\n", applet_name);
364 void BZ2_hbCreateDecodeTables(int *limit, int *base, int *perm, unsigned char *length, int minLen, int maxLen, int alphaSize )
369 for (i = minLen; i <= maxLen; i++) {
370 for (j = 0; j < alphaSize; j++) {
371 if (length[j] == i) {
378 for (i = 0; i < BZ_MAX_CODE_LEN; i++) {
382 for (i = 0; i < alphaSize; i++) {
386 for (i = 1; i < BZ_MAX_CODE_LEN; i++) {
387 base[i] += base[i-1];
390 for (i = 0; i < BZ_MAX_CODE_LEN; i++) {
395 for (i = minLen; i <= maxLen; i++) {
396 vec += (base[i+1] - base[i]);
400 for (i = minLen + 1; i <= maxLen; i++) {
401 base[i] = ((limit[i-1] + 1) << 1) - base[i];
406 static int get_bits(DState *s, int *vvv, char nnn)
409 if (s->bsLive >= nnn) {
410 *vvv = (s->bsBuff >> (s->bsLive-nnn)) & ((1 << nnn)-1);
414 if (s->strm->avail_in == 0) {
417 s->bsBuff = (s->bsBuff << 8) | ((unsigned int) (*((unsigned char*)(s->strm->next_in))));
425 int bz_get_fast(DState *s)
428 s->tPos = s->tt[s->tPos];
429 cccc = (unsigned char)(s->tPos & 0xff);
434 /*---------------------------------------------------*/
435 int BZ2_decompress(DState *s)
441 /* stuff that needs to be saved/restored */
468 int get_mtf_val_init(void)
472 if (groupNo >= nSelectors) {
473 retVal = BZ_DATA_ERROR;
476 groupPos = BZ_G_SIZE;
477 gSel = s->selector[groupNo];
478 gMinlen = s->minLens[gSel];
479 gLimit = &(s->limit[gSel][0]);
480 gPerm = &(s->perm[gSel][0]);
481 gBase = &(s->base[gSel][0]);
488 if (s->state == BZ_X_MAGIC_1) {
489 /*initialise the save area*/
493 s->save_alphaSize = 0;
495 s->save_nSelectors = 0;
498 s->save_groupPos = 0;
500 s->save_nblockMAX = 0;
511 s->save_gLimit = NULL;
512 s->save_gBase = NULL;
513 s->save_gPerm = NULL;
516 /*restore from the save area*/
520 alphaSize = s->save_alphaSize;
521 nGroups = s->save_nGroups;
522 nSelectors = s->save_nSelectors;
524 groupNo = s->save_groupNo;
525 groupPos = s->save_groupPos;
526 nextSym = s->save_nextSym;
527 nblockMAX = s->save_nblockMAX;
528 nblock = s->save_nblock;
537 gMinlen = s->save_gMinlen;
538 gLimit = s->save_gLimit;
539 gBase = s->save_gBase;
540 gPerm = s->save_gPerm;
543 switch_val = s->state;
544 switch (switch_val) {
546 s->state = BZ_X_MAGIC_1;
547 if (! get_bits(s, &uc, 8)) {
549 goto save_state_and_return;
552 retVal = BZ_DATA_ERROR_MAGIC;
553 goto save_state_and_return;
557 s->state = BZ_X_MAGIC_2;
558 if (! get_bits(s, &uc, 8)) {
560 goto save_state_and_return;
563 retVal = BZ_DATA_ERROR_MAGIC;
564 goto save_state_and_return;
568 s->state = BZ_X_MAGIC_3;
569 if (! get_bits(s, &uc, 8)) {
571 goto save_state_and_return;
574 retVal = BZ_DATA_ERROR_MAGIC;
575 goto save_state_and_return;
579 s->state = BZ_X_MAGIC_4;
580 if (! get_bits(s, &s->blockSize100k, 8)) {
582 goto save_state_and_return;
584 if ((s->blockSize100k < '1') || (s->blockSize100k > '9')) {
585 retVal = BZ_DATA_ERROR_MAGIC;
586 goto save_state_and_return;
588 s->blockSize100k -= '0';
590 s->tt = xmalloc(s->blockSize100k * 100000 * sizeof(int));
593 s->state = BZ_X_BLKHDR_1;
594 if (! get_bits(s, &uc, 8)) {
596 goto save_state_and_return;
603 retVal = BZ_DATA_ERROR;
604 goto save_state_and_return;
608 s->state = BZ_X_BLKHDR_2;
609 if (! get_bits(s, &uc, 8)) {
611 goto save_state_and_return;
614 retVal = BZ_DATA_ERROR;
615 goto save_state_and_return;
619 s->state = BZ_X_BLKHDR_3;
620 if (! get_bits(s, &uc, 8)) {
622 goto save_state_and_return;
625 retVal = BZ_DATA_ERROR;
626 goto save_state_and_return;
630 s->state = BZ_X_BLKHDR_4;
631 if (! get_bits(s, &uc, 8)) {
633 goto save_state_and_return;
636 retVal = BZ_DATA_ERROR;
637 goto save_state_and_return;
641 s->state = BZ_X_BLKHDR_5;
642 if (! get_bits(s, &uc, 8)) {
644 goto save_state_and_return;
647 retVal = BZ_DATA_ERROR;
648 goto save_state_and_return;
652 s->state = BZ_X_BLKHDR_6;
653 if (! get_bits(s, &uc, 8)) {
655 goto save_state_and_return;
658 retVal = BZ_DATA_ERROR;
659 goto save_state_and_return;
663 s->storedBlockCRC = 0;
666 s->state = BZ_X_BCRC_1;
667 if (! get_bits(s, &uc, 8)) {
669 goto save_state_and_return;
671 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
674 s->state = BZ_X_BCRC_2;
675 if (! get_bits(s, &uc, 8)) {
677 goto save_state_and_return;
679 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
682 s->state = BZ_X_BCRC_3;
683 if (! get_bits(s, &uc, 8)) {
685 goto save_state_and_return;
687 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
690 s->state = BZ_X_BCRC_4;
691 if (! get_bits(s, &uc, 8)) {
693 goto save_state_and_return;
695 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
698 s->state = BZ_X_RANDBIT;
700 int tmp = s->blockRandomised;
701 const int ret = get_bits(s, &tmp, 1);
702 s->blockRandomised = tmp;
705 goto save_state_and_return;
712 s->state = BZ_X_ORIGPTR_1;
713 if (! get_bits(s, &uc, 8)) {
715 goto save_state_and_return;
717 s->origPtr = (s->origPtr << 8) | ((int)uc);
720 s->state = BZ_X_ORIGPTR_2;
721 if (! get_bits(s, &uc, 8)) {
723 goto save_state_and_return;
725 s->origPtr = (s->origPtr << 8) | ((int)uc);
728 s->state = BZ_X_ORIGPTR_3;
729 if (! get_bits(s, &uc, 8)) {
731 goto save_state_and_return;
733 s->origPtr = (s->origPtr << 8) | ((int)uc);
735 if (s->origPtr < 0) {
736 retVal = BZ_DATA_ERROR;
737 goto save_state_and_return;
739 if (s->origPtr > 10 + 100000*s->blockSize100k) {
740 retVal = BZ_DATA_ERROR;
741 goto save_state_and_return;
744 /*--- Receive the mapping table ---*/
746 for (i = 0; i < 16; i++) {
747 s->state = BZ_X_MAPPING_1;
748 if (! get_bits(s, &uc, 1)) {
750 goto save_state_and_return;
753 s->inUse16[i] = TRUE;
755 s->inUse16[i] = FALSE;
759 for (i = 0; i < 256; i++) {
763 for (i = 0; i < 16; i++) {
765 for (j = 0; j < 16; j++) {
767 s->state = BZ_X_MAPPING_2;
768 if (! get_bits(s, &uc, 1)) {
770 goto save_state_and_return;
773 s->inUse[i * 16 + j] = TRUE;
780 for (i = 0; i < 256; i++) {
782 s->seqToUnseq[s->nInUse] = i;
786 if (s->nInUse == 0) {
787 retVal = BZ_DATA_ERROR;
788 goto save_state_and_return;
790 alphaSize = s->nInUse+2;
792 /*--- Now the selectors ---*/
793 case BZ_X_SELECTOR_1:
794 s->state = BZ_X_SELECTOR_1;
795 if (! get_bits(s, &nGroups, 3)) {
797 goto save_state_and_return;
799 if (nGroups < 2 || nGroups > 6) {
800 retVal = BZ_DATA_ERROR;
801 goto save_state_and_return;
804 case BZ_X_SELECTOR_2:
805 s->state = BZ_X_SELECTOR_2;
806 if (! get_bits(s, &nSelectors, 15)) {
808 goto save_state_and_return;
810 if (nSelectors < 1) {
811 retVal = BZ_DATA_ERROR;
812 goto save_state_and_return;
817 for (i = 0; i < nSelectors; i++) {
820 case BZ_X_SELECTOR_3:
821 s->state = BZ_X_SELECTOR_3;
822 if (! get_bits(s, &uc, 1)) {
824 goto save_state_and_return;
831 retVal = BZ_DATA_ERROR;
832 goto save_state_and_return;
835 s->selectorMtf[i] = j;
838 /*--- Undo the MTF values for the selectors. ---*/
840 unsigned char pos[BZ_N_GROUPS], tmp, v;
841 for (v = 0; v < nGroups; v++) {
844 for (i = 0; i < nSelectors; i++) {
845 v = s->selectorMtf[i];
852 s->selector[i] = tmp;
856 /*--- Now the coding tables ---*/
857 for (t = 0; t < nGroups; t++) {
859 s->state = BZ_X_CODING_1;
860 if (! get_bits(s, &curr, 5)) {
862 goto save_state_and_return;
864 for (i = 0; i < alphaSize; i++) {
866 if (curr < 1 || curr > 20) {
867 retVal = BZ_DATA_ERROR;
868 goto save_state_and_return;
872 s->state = BZ_X_CODING_2;
873 if (! get_bits(s, &uc, 1)) {
875 goto save_state_and_return;
882 s->state = BZ_X_CODING_3;
883 if (! get_bits(s, &uc, 1)) {
885 goto save_state_and_return;
897 /*--- Create the Huffman decoding tables ---*/
898 for (t = 0; t < nGroups; t++) {
901 for (i = 0; i < alphaSize; i++) {
902 if (s->len[t][i] > maxLen) {
903 maxLen = s->len[t][i];
905 if (s->len[t][i] < minLen) {
906 minLen = s->len[t][i];
910 BZ2_hbCreateDecodeTables (
915 minLen, maxLen, alphaSize
919 s->minLens[t] = minLen;
922 /*--- Now the MTF values ---*/
925 nblockMAX = 100000 * s->blockSize100k;
929 for (i = 0; i <= 255; i++) {
936 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
937 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
938 s->mtfa[kk] = (unsigned char)(ii * MTFL_SIZE + jj);
941 s->mtfbase[ii] = kk + 1;
944 /*-- end MTF init --*/
948 if (! get_mtf_val_init()) {
949 goto save_state_and_return;
952 s->state = BZ_X_MTF_1;
953 if (! get_bits(s, &zvec, zn)) {
955 goto save_state_and_return;
958 if (zn > 20 /* the longest code */) {
959 retVal = BZ_DATA_ERROR;
960 goto save_state_and_return;
962 if (zvec <= gLimit[zn]) {
968 s->state = BZ_X_MTF_2;
969 if (! get_bits(s, &zj, 1)) {
971 goto save_state_and_return;
973 zvec = (zvec << 1) | zj;
975 if (zvec - gBase[zn] < 0 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) {
976 retVal = BZ_DATA_ERROR;
977 goto save_state_and_return;
979 nextSym = gPerm[zvec - gBase[zn]];
982 if (nextSym == EOB) {
986 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
990 if (nextSym == BZ_RUNA) {
993 if (nextSym == BZ_RUNB) {
998 if (! get_mtf_val_init()) {
999 goto save_state_and_return;
1002 s->state = BZ_X_MTF_3;
1003 if (! get_bits(s, &zvec, zn)) {
1005 goto save_state_and_return;
1008 if (zn > 20 /* the longest code */) {
1009 retVal = BZ_DATA_ERROR;
1010 goto save_state_and_return;
1012 if (zvec <= gLimit[zn]) {
1018 s->state = BZ_X_MTF_4;
1019 if (! get_bits(s, &zj, 1)) {
1021 goto save_state_and_return;
1023 zvec = (zvec << 1) | zj;
1025 if (zvec - gBase[zn] < 0 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) {
1026 retVal = BZ_DATA_ERROR;
1027 goto save_state_and_return;
1030 nextSym = gPerm[zvec - gBase[zn]];
1032 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
1035 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
1036 s->unzftab[uc] += es;
1039 if (nblock >= nblockMAX) {
1040 retVal = BZ_DATA_ERROR;
1041 goto save_state_and_return;
1043 s->tt[nblock] = (unsigned int)uc;
1049 if (nblock >= nblockMAX) {
1050 retVal = BZ_DATA_ERROR;
1051 goto save_state_and_return;
1053 /*-- uc = MTF ( nextSym-1 ) --*/
1055 int ii, jj, kk, pp, lno, off;
1057 nn = (unsigned int)(nextSym - 1);
1059 if (nn < MTFL_SIZE) {
1060 /* avoid general-case expense */
1062 uc = s->mtfa[pp+nn];
1065 s->mtfa[(z) ] = s->mtfa[(z)-1];
1066 s->mtfa[(z)-1] = s->mtfa[(z)-2];
1067 s->mtfa[(z)-2] = s->mtfa[(z)-3];
1068 s->mtfa[(z)-3] = s->mtfa[(z)-4];
1072 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
1077 lno = nn / MTFL_SIZE;
1078 off = nn % MTFL_SIZE;
1079 pp = s->mtfbase[lno] + off;
1081 while (pp > s->mtfbase[lno]) {
1082 s->mtfa[pp] = s->mtfa[pp-1];
1088 s->mtfa[s->mtfbase[lno]] = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
1092 s->mtfa[s->mtfbase[0]] = uc;
1093 if (s->mtfbase[0] == 0) {
1095 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
1096 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
1097 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
1100 s->mtfbase[ii] = kk + 1;
1105 /*-- end uc = MTF ( nextSym-1 ) --*/
1107 s->unzftab[s->seqToUnseq[uc]]++;
1108 s->tt[nblock] = (unsigned int)(s->seqToUnseq[uc]);
1111 if (! get_mtf_val_init()) {
1112 goto save_state_and_return;
1115 s->state = BZ_X_MTF_5;
1116 if (! get_bits(s, &zvec, zn)) {
1118 goto save_state_and_return;
1121 if (zn > 20 /* the longest code */) {
1122 retVal = BZ_DATA_ERROR;
1123 goto save_state_and_return;
1125 if (zvec <= gLimit[zn]) {
1131 s->state = BZ_X_MTF_6;
1132 if (! get_bits(s, &zj, 1)) {
1134 goto save_state_and_return;
1136 zvec = (zvec << 1) | zj;
1138 if (zvec - gBase[zn] < 0 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) {
1139 retVal = BZ_DATA_ERROR;
1140 goto save_state_and_return;
1142 nextSym = gPerm[zvec - gBase[zn]];
1147 /* Now we know what nblock is, we can do a better sanity
1148 check on s->origPtr.
1150 if (s->origPtr < 0 || s->origPtr >= nblock) {
1151 retVal = BZ_DATA_ERROR;
1152 goto save_state_and_return;
1154 s->state_out_len = 0;
1155 s->state_out_ch = 0;
1156 s->calculatedBlockCRC = 0xffffffffL;
1157 s->state = BZ_X_OUTPUT;
1159 /*-- Set up cftab to facilitate generation of T^(-1) --*/
1161 for (i = 1; i <= 256; i++) {
1162 s->cftab[i] = s->unzftab[i-1];
1164 for (i = 1; i <= 256; i++) {
1165 s->cftab[i] += s->cftab[i-1];
1168 /*-- compute the T^(-1) vector --*/
1169 for (i = 0; i < nblock; i++) {
1170 uc = (unsigned char)(s->tt[i] & 0xff);
1171 s->tt[s->cftab[uc]] |= (i << 8);
1175 s->tPos = s->tt[s->origPtr] >> 8;
1177 if (s->blockRandomised) {
1180 s->k0 = bz_get_fast(s);
1183 bz_rand_udp_mask(s);
1184 s->k0 ^= ((s->rNToGo == 1) ? 1 : 0);
1186 s->k0 = bz_get_fast(s);
1191 goto save_state_and_return;
1195 s->state = BZ_X_ENDHDR_2;
1196 if (! get_bits(s, &uc, 8)) {
1198 goto save_state_and_return;
1201 retVal = BZ_DATA_ERROR;
1202 goto save_state_and_return;
1206 s->state = BZ_X_ENDHDR_3;
1207 if (! get_bits(s, &uc, 8)) {
1209 goto save_state_and_return;
1212 retVal = BZ_DATA_ERROR;
1213 goto save_state_and_return;
1217 s->state = BZ_X_ENDHDR_4;
1218 if (! get_bits(s, &uc, 8)) {
1220 goto save_state_and_return;
1223 retVal = BZ_DATA_ERROR;
1224 goto save_state_and_return;
1228 s->state = BZ_X_ENDHDR_5;
1229 if (! get_bits(s, &uc, 8)) {
1231 goto save_state_and_return;
1234 retVal = BZ_DATA_ERROR;
1235 goto save_state_and_return;
1239 s->state = BZ_X_ENDHDR_6;
1240 if (! get_bits(s, &uc, 8)) {
1242 goto save_state_and_return;
1245 retVal = BZ_DATA_ERROR;
1246 goto save_state_and_return;
1248 s->storedCombinedCRC = 0;
1251 s->state = BZ_X_CCRC_1;
1252 if (! get_bits(s, &uc, 8)) {
1254 goto save_state_and_return;
1256 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1258 s->state = BZ_X_CCRC_2;
1259 if (! get_bits(s, &uc, 8)) {
1261 goto save_state_and_return;
1263 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1266 s->state = BZ_X_CCRC_3;
1267 if (! get_bits(s, &uc, 8)) {
1269 goto save_state_and_return;
1271 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1274 s->state = BZ_X_CCRC_4;
1275 if (! get_bits(s, &uc, 8)) {
1277 goto save_state_and_return;
1279 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1281 s->state = BZ_X_IDLE;
1282 retVal = BZ_STREAM_END;
1283 goto save_state_and_return;
1287 save_state_and_return:
1291 s->save_alphaSize = alphaSize;
1292 s->save_nGroups = nGroups;
1293 s->save_nSelectors = nSelectors;
1295 s->save_groupNo = groupNo;
1296 s->save_groupPos = groupPos;
1297 s->save_nextSym = nextSym;
1298 s->save_nblockMAX = nblockMAX;
1299 s->save_nblock = nblock;
1302 s->save_curr = curr;
1305 s->save_zvec = zvec;
1307 s->save_gSel = gSel;
1308 s->save_gMinlen = gMinlen;
1309 s->save_gLimit = gLimit;
1310 s->save_gBase = gBase;
1311 s->save_gPerm = gPerm;
1316 //int BZ2_bzDecompressInit(bz_stream* strm, int verbosity_level, int small)
1317 int BZ2_bzDecompressInit(bz_stream* strm)
1321 // if (verbosity_level < 0 || verbosity_level > 4) {
1322 // return BZ_PARAM_ERROR;
1324 s = xmalloc(sizeof(DState));
1327 s->state = BZ_X_MAGIC_1;
1330 s->calculatedCombinedCRC = 0;
1337 void bz_seterr(int eee, int *bzerror, bzFile **bzf)
1339 if (bzerror != NULL) {
1343 (*bzf)->lastErr = eee;
1347 static void BZ2_bzReadClose(int *bzerror, void *b)
1349 bzFile* bzf = (bzFile*)b;
1351 bz_seterr(BZ_OK, bzerror, &bzf);
1353 if (bzf->initialisedOk) {
1354 bz_stream *strm = &(bzf->strm);
1360 if ((s == NULL) || (s->strm != strm)) {
1371 static void unRLE_obuf_to_output_FAST(DState *s)
1375 if (s->blockRandomised) {
1377 /* try to finish existing run */
1379 if (s->strm->avail_out == 0) {
1382 if (s->state_out_len == 0) {
1385 *((unsigned char *)(s->strm->next_out)) = s->state_out_ch;
1386 s->calculatedBlockCRC = (s->calculatedBlockCRC << 8) ^
1387 BZ2_crc32Table[(s->calculatedBlockCRC >> 24) ^
1388 ((unsigned char)s->state_out_ch)];
1390 s->strm->next_out++;
1391 s->strm->avail_out--;
1394 /* can a new run be started? */
1395 if (s->nblock_used == s->save_nblock+1) {
1398 s->state_out_len = 1;
1399 s->state_out_ch = s->k0;
1400 k1 = bz_get_fast(s);
1401 bz_rand_udp_mask(s);
1402 k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1404 if (s->nblock_used == s->save_nblock+1) {
1412 s->state_out_len = 2;
1413 k1 = bz_get_fast(s);
1414 bz_rand_udp_mask(s);
1415 k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1417 if (s->nblock_used == s->save_nblock+1) {
1424 s->state_out_len = 3;
1425 k1 = bz_get_fast(s);
1426 bz_rand_udp_mask(s);
1427 k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1429 if (s->nblock_used == s->save_nblock+1) {
1437 k1 = bz_get_fast(s);
1438 bz_rand_udp_mask(s);
1439 k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1441 s->state_out_len = ((int)k1) + 4;
1442 s->k0 = bz_get_fast(s);
1443 bz_rand_udp_mask(s);
1444 s->k0 ^= ((s->rNToGo == 1) ? 1 : 0);
1449 unsigned int c_calculatedBlockCRC = s->calculatedBlockCRC;
1450 unsigned char c_state_out_ch = s->state_out_ch;
1451 int c_state_out_len = s->state_out_len;
1452 int c_nblock_used = s->nblock_used;
1454 unsigned int *c_tt = s->tt;
1455 unsigned int c_tPos = s->tPos;
1456 char *cs_next_out = s->strm->next_out;
1457 unsigned int cs_avail_out = s->strm->avail_out;
1460 int s_save_nblockPP = s->save_nblock+1;
1463 /* try to finish existing run */
1464 if (c_state_out_len > 0) {
1466 if (cs_avail_out == 0) {
1469 if (c_state_out_len == 1) {
1472 *((unsigned char *)(cs_next_out)) = c_state_out_ch;
1473 c_calculatedBlockCRC = (c_calculatedBlockCRC << 8) ^
1474 BZ2_crc32Table[(c_calculatedBlockCRC >> 24) ^
1475 ((unsigned char)c_state_out_ch)];
1480 s_state_out_len_eq_one:
1482 if (cs_avail_out == 0) {
1483 c_state_out_len = 1;
1486 *((unsigned char *)(cs_next_out)) = c_state_out_ch;
1487 c_calculatedBlockCRC = (c_calculatedBlockCRC << 8) ^
1488 BZ2_crc32Table[(c_calculatedBlockCRC >> 24) ^
1489 ((unsigned char)c_state_out_ch)];
1494 /* can a new run be started? */
1495 if (c_nblock_used == s_save_nblockPP) {
1496 c_state_out_len = 0; goto return_notr;
1498 c_state_out_ch = c_k0;
1499 c_tPos = c_tt[c_tPos];
1500 k1 = (unsigned char)(c_tPos & 0xff);
1507 goto s_state_out_len_eq_one;
1510 if (c_nblock_used == s_save_nblockPP) {
1511 goto s_state_out_len_eq_one;
1514 c_state_out_len = 2;
1515 c_tPos = c_tt[c_tPos];
1516 k1 = (unsigned char)(c_tPos & 0xff);
1520 if (c_nblock_used == s_save_nblockPP) {
1528 c_state_out_len = 3;
1529 c_tPos = c_tt[c_tPos];
1530 k1 = (unsigned char)(c_tPos & 0xff);
1534 if (c_nblock_used == s_save_nblockPP) {
1542 c_tPos = c_tt[c_tPos];
1543 k1 = (unsigned char)(c_tPos & 0xff);
1547 c_state_out_len = ((int)k1) + 4;
1549 c_tPos = c_tt[c_tPos];
1550 c_k0 = (unsigned char)(c_tPos & 0xff);
1559 s->calculatedBlockCRC = c_calculatedBlockCRC;
1560 s->state_out_ch = c_state_out_ch;
1561 s->state_out_len = c_state_out_len;
1562 s->nblock_used = c_nblock_used;
1566 s->strm->next_out = cs_next_out;
1567 s->strm->avail_out = cs_avail_out;
1572 int BZ2_bzDecompress(bz_stream *strm)
1578 if (s->state == BZ_X_IDLE) {
1579 return BZ_SEQUENCE_ERROR;
1581 if (s->state == BZ_X_OUTPUT) {
1582 unRLE_obuf_to_output_FAST(s);
1583 if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) {
1584 s->calculatedBlockCRC = ~(s->calculatedBlockCRC);
1585 if (s->calculatedBlockCRC != s->storedBlockCRC) {
1586 return BZ_DATA_ERROR;
1588 s->calculatedCombinedCRC = (s->calculatedCombinedCRC << 1) | (s->calculatedCombinedCRC >> 31);
1589 s->calculatedCombinedCRC ^= s->calculatedBlockCRC;
1590 s->state = BZ_X_BLKHDR_1;
1595 if (s->state >= BZ_X_MAGIC_1) {
1596 int r = BZ2_decompress(s);
1597 if (r == BZ_STREAM_END) {
1598 if (s->calculatedCombinedCRC != s->storedCombinedCRC) {
1599 return BZ_DATA_ERROR;
1603 if (s->state != BZ_X_OUTPUT) {
1609 return(0); /*NOTREACHED*/
1612 int BZ2_bzRead(int *bzerror, void *b, void *buf, int len)
1615 bzFile *bzf = (bzFile*)b;
1617 bz_seterr(BZ_OK, bzerror, &bzf);
1620 bz_seterr(BZ_OK, bzerror, &bzf);
1624 bzf->strm.avail_out = len;
1625 bzf->strm.next_out = buf;
1628 if (ferror(bzf->handle)) {
1629 bz_seterr(BZ_IO_ERROR, bzerror, &bzf);
1632 if ((bzf->strm.avail_in == 0) && !myfeof(bzf->handle)) {
1633 n = fread(bzf->buf, sizeof(unsigned char), BZ_MAX_UNUSED, bzf->handle);
1634 if (ferror(bzf->handle)) {
1635 bz_seterr(BZ_IO_ERROR, bzerror, &bzf);
1639 bzf->strm.avail_in = bzf->bufN;
1640 bzf->strm.next_in = bzf->buf;
1643 ret = BZ2_bzDecompress(&(bzf->strm));
1645 if ((ret != BZ_OK) && (ret != BZ_STREAM_END)) {
1646 bz_seterr(ret, bzerror, &bzf);
1650 if ((ret == BZ_OK) && myfeof(bzf->handle) &&
1651 (bzf->strm.avail_in == 0) && (bzf->strm.avail_out > 0)) {
1652 bz_seterr(BZ_UNEXPECTED_EOF, bzerror, &bzf);
1656 if (ret == BZ_STREAM_END) {
1657 bz_seterr(BZ_STREAM_END, bzerror, &bzf);
1658 return(len - bzf->strm.avail_out);
1660 if (bzf->strm.avail_out == 0) {
1661 bz_seterr(BZ_OK, bzerror, &bzf);
1665 return(0); /*not reached*/
1668 void *BZ2_bzReadOpen(int *bzerror, FILE *f, void *unused, int nUnused)
1670 bzFile *bzf = xmalloc(sizeof(bzFile));
1673 bz_seterr(BZ_OK, bzerror, &bzf);
1675 bzf->initialisedOk = FALSE;
1679 ret = BZ2_bzDecompressInit(&(bzf->strm));
1681 bz_seterr(ret, bzerror, &bzf);
1686 while (nUnused > 0) {
1687 bzf->buf[bzf->bufN] = *((unsigned char *)(unused)); bzf->bufN++;
1688 unused = ((void *)( 1 + ((unsigned char *)(unused)) ));
1691 bzf->strm.avail_in = bzf->bufN;
1692 bzf->strm.next_in = bzf->buf;
1694 bzf->initialisedOk = TRUE;
1698 static unsigned char uncompressStream(FILE *zStream, FILE *stream)
1700 unsigned char unused[BZ_MAX_UNUSED];
1701 unsigned char *unusedTmp;
1702 unsigned char obuf[5000];
1715 if (ferror(stream)) {
1718 if (ferror(zStream)) {
1723 bzf = BZ2_bzReadOpen(&bzerr, zStream, unused, nUnused);
1724 if (bzf == NULL || bzerr != BZ_OK) {
1729 while (bzerr == BZ_OK) {
1730 nread = BZ2_bzRead(&bzerr, bzf, obuf, 5000);
1731 if (bzerr == BZ_DATA_ERROR_MAGIC) {
1734 if ((bzerr == BZ_OK || bzerr == BZ_STREAM_END) && nread > 0) {
1735 fwrite(obuf, sizeof(unsigned char), nread, stream);
1737 if (ferror(stream)) {
1741 if (bzerr != BZ_STREAM_END) {
1744 nUnused = bzf->strm.avail_in;
1745 unusedTmp = bzf->strm.next_in;
1746 bz_seterr(BZ_OK, &bzerr, &bzf);
1747 for (i = 0; i < nUnused; i++) {
1748 unused[i] = unusedTmp[i];
1750 BZ2_bzReadClose(&bzerr, bzf);
1751 if ((nUnused == 0) && myfeof(zStream)) {
1756 if (ferror(zStream)) {
1759 ret = fclose(zStream);
1763 if (ferror(stream)) {
1766 ret = fflush(stream);
1770 if (stream != stdout) {
1771 ret = fclose(stream);
1779 BZ2_bzReadClose ( &bzerr_dummy, bzf );
1783 error_msg("\n%s: I/O or other error, bailing out. "
1784 "Possible reason follows.\n", applet_name);
1785 perror(applet_name);
1788 error_msg("\n%s: Data integrity error when decompressing.\n", applet_name);
1790 case BZ_UNEXPECTED_EOF:
1791 error_msg("\n%s: Compressed file ends unexpectedly;\n\t"
1792 "perhaps it is corrupted? *Possible* reason follows.\n", applet_name);
1793 perror(applet_name);
1795 case BZ_DATA_ERROR_MAGIC:
1796 if (zStream != stdin) {
1799 if (stream != stdout) {
1802 if (streamNo == 1) {
1809 return(TRUE); /*notreached*/
1812 int bunzip2_main(int argc, char **argv)
1814 const int bunzip_to_stdout = 1;
1815 const int bunzip_force = 2;
1822 char *save_name = NULL;
1823 char *delete_name = NULL;
1825 /* if called as bzcat */
1826 if (strcmp(applet_name, "bzcat") == 0)
1827 flags |= bunzip_to_stdout;
1829 while ((opt = getopt(argc, argv, "cfh")) != -1) {
1832 flags |= bunzip_to_stdout;
1835 flags |= bunzip_force;
1839 show_usage(); /* exit's inside usage */
1843 /* Set input filename and number */
1844 if (argv[optind] == NULL || strcmp(argv[optind], "-") == 0) {
1845 flags |= bunzip_to_stdout;
1848 /* Open input file */
1849 src_stream = xfopen(argv[optind], "r");
1851 save_name = xstrdup(argv[optind]);
1852 if (strcmp(save_name + strlen(save_name) - 4, ".bz2") != 0)
1853 error_msg_and_die("Invalid extension");
1854 save_name[strlen(save_name) - 4] = '\0';
1857 /* Check that the input is sane. */
1858 if (isatty(fileno(src_stream)) && (flags & bunzip_force) == 0)
1859 error_msg_and_die("compressed data not read from terminal. Use -f to force it.");
1861 if (flags & bunzip_to_stdout) {
1862 dst_stream = stdout;
1864 dst_stream = xfopen(save_name, "w");
1867 if (uncompressStream(src_stream, dst_stream)) {
1868 if (!(flags & bunzip_to_stdout))
1869 delete_name = argv[optind];
1870 status = EXIT_SUCCESS;
1872 if (!(flags & bunzip_to_stdout))
1873 delete_name = save_name;
1874 status = EXIT_FAILURE;
1878 if (unlink(delete_name) < 0) {
1879 error_msg_and_die("Couldn't remove %s", delete_name);