2 This file is a part of bzip2 and/or libbzip2, a program and
3 library for lossless, block-sorting data compression.
5 Copyright (C) 1996-2000 Julian R Seward. All rights reserved.
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions
11 1. Redistributions of source code must retain the above copyright
12 notice, this list of conditions and the following disclaimer.
14 2. The origin of this software must not be misrepresented; you must
15 not claim that you wrote the original software. If you use this
16 software in a product, an acknowledgment in the product
17 documentation would be appreciated but is not required.
19 3. Altered source versions must be plainly marked as such, and must
20 not be misrepresented as being the original software.
22 4. The name of the author may not be used to endorse or promote
23 products derived from this software without specific prior written
26 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
27 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
28 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
30 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
32 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
33 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
34 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 Julian Seward, Cambridge, UK.
40 bzip2/libbzip2 version 1.0 of 21 March 2000
42 This program is based on (at least) the work of:
52 For more information on these sources, see the manual.
63 #define MTFA_SIZE 4096
67 #define BZ_MAX_ALPHA_SIZE 258
70 #define BZ_STREAM_END 4
71 #define BZ_SEQUENCE_ERROR (-1)
72 #define BZ_DATA_ERROR (-4)
73 #define BZ_DATA_ERROR_MAGIC (-5)
74 #define BZ_IO_ERROR (-6)
75 #define BZ_UNEXPECTED_EOF (-7)
80 #define BZ_MAX_UNUSED 5000
81 #define FILE_NAME_LEN 1034
82 /*-- states for decompression. --*/
87 #define BZ_X_MAGIC_1 10
88 #define BZ_X_MAGIC_2 11
89 #define BZ_X_MAGIC_3 12
90 #define BZ_X_MAGIC_4 13
91 #define BZ_X_BLKHDR_1 14
92 #define BZ_X_BLKHDR_2 15
93 #define BZ_X_BLKHDR_3 16
94 #define BZ_X_BLKHDR_4 17
95 #define BZ_X_BLKHDR_5 18
96 #define BZ_X_BLKHDR_6 19
97 #define BZ_X_BCRC_1 20
98 #define BZ_X_BCRC_2 21
99 #define BZ_X_BCRC_3 22
100 #define BZ_X_BCRC_4 23
101 #define BZ_X_RANDBIT 24
102 #define BZ_X_ORIGPTR_1 25
103 #define BZ_X_ORIGPTR_2 26
104 #define BZ_X_ORIGPTR_3 27
105 #define BZ_X_MAPPING_1 28
106 #define BZ_X_MAPPING_2 29
107 #define BZ_X_SELECTOR_1 30
108 #define BZ_X_SELECTOR_2 31
109 #define BZ_X_SELECTOR_3 32
110 #define BZ_X_CODING_1 33
111 #define BZ_X_CODING_2 34
112 #define BZ_X_CODING_3 35
113 #define BZ_X_MTF_1 36
114 #define BZ_X_MTF_2 37
115 #define BZ_X_MTF_3 38
116 #define BZ_X_MTF_4 39
117 #define BZ_X_MTF_5 40
118 #define BZ_X_MTF_6 41
119 #define BZ_X_ENDHDR_2 42
120 #define BZ_X_ENDHDR_3 43
121 #define BZ_X_ENDHDR_4 44
122 #define BZ_X_ENDHDR_5 45
123 #define BZ_X_ENDHDR_6 46
124 #define BZ_X_CCRC_1 47
125 #define BZ_X_CCRC_2 48
126 #define BZ_X_CCRC_3 49
127 #define BZ_X_CCRC_4 50
129 #define BZ_MAX_CODE_LEN 23
134 unsigned int avail_in;
137 unsigned int avail_out;
143 #define BZ_MAX_UNUSED 5000
147 unsigned char initialisedOk;
148 char buf[BZ_MAX_UNUSED];
153 /*-- Structure holding all the decompression-side stuff. --*/
155 /* pointer back to the struct bz_stream */
158 /* state indicator for this stream */
161 /* for doing the final run-length decoding */
162 unsigned char state_out_ch;
164 unsigned char blockRandomised;
168 /* the buffer for bit stream reading */
172 /* misc administratium */
176 /* for undoing the Burrows-Wheeler transform */
185 /* for undoing the Burrows-Wheeler transform (FAST) */
188 /* stored and calculated CRCs */
189 unsigned int storedBlockCRC;
190 unsigned int storedCombinedCRC;
191 unsigned int calculatedBlockCRC;
192 unsigned int calculatedCombinedCRC;
194 /* map of bytes used in block */
196 unsigned char inUse[256];
197 unsigned char inUse16[16];
198 unsigned char seqToUnseq[256];
200 /* for decoding the MTF values */
201 unsigned char mtfa [MTFA_SIZE];
202 unsigned char selector [2 + (900000 / BZ_G_SIZE)];
203 unsigned char selectorMtf[2 + (900000 / BZ_G_SIZE)];
204 unsigned char len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
205 int mtfbase[256 / MTFL_SIZE];
207 int limit [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
208 int base [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
209 int perm [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
210 int minLens[BZ_N_GROUPS];
212 /* save area for scalars in the main decompress code */
239 static int BZ2_rNums[512];
241 static int bzerr = BZ_OK;
243 static const unsigned int BZ2_crc32Table[256] = {
245 /*-- Ugly, innit? --*/
247 0x00000000L, 0x04c11db7L, 0x09823b6eL, 0x0d4326d9L,
248 0x130476dcL, 0x17c56b6bL, 0x1a864db2L, 0x1e475005L,
249 0x2608edb8L, 0x22c9f00fL, 0x2f8ad6d6L, 0x2b4bcb61L,
250 0x350c9b64L, 0x31cd86d3L, 0x3c8ea00aL, 0x384fbdbdL,
251 0x4c11db70L, 0x48d0c6c7L, 0x4593e01eL, 0x4152fda9L,
252 0x5f15adacL, 0x5bd4b01bL, 0x569796c2L, 0x52568b75L,
253 0x6a1936c8L, 0x6ed82b7fL, 0x639b0da6L, 0x675a1011L,
254 0x791d4014L, 0x7ddc5da3L, 0x709f7b7aL, 0x745e66cdL,
255 0x9823b6e0L, 0x9ce2ab57L, 0x91a18d8eL, 0x95609039L,
256 0x8b27c03cL, 0x8fe6dd8bL, 0x82a5fb52L, 0x8664e6e5L,
257 0xbe2b5b58L, 0xbaea46efL, 0xb7a96036L, 0xb3687d81L,
258 0xad2f2d84L, 0xa9ee3033L, 0xa4ad16eaL, 0xa06c0b5dL,
259 0xd4326d90L, 0xd0f37027L, 0xddb056feL, 0xd9714b49L,
260 0xc7361b4cL, 0xc3f706fbL, 0xceb42022L, 0xca753d95L,
261 0xf23a8028L, 0xf6fb9d9fL, 0xfbb8bb46L, 0xff79a6f1L,
262 0xe13ef6f4L, 0xe5ffeb43L, 0xe8bccd9aL, 0xec7dd02dL,
263 0x34867077L, 0x30476dc0L, 0x3d044b19L, 0x39c556aeL,
264 0x278206abL, 0x23431b1cL, 0x2e003dc5L, 0x2ac12072L,
265 0x128e9dcfL, 0x164f8078L, 0x1b0ca6a1L, 0x1fcdbb16L,
266 0x018aeb13L, 0x054bf6a4L, 0x0808d07dL, 0x0cc9cdcaL,
267 0x7897ab07L, 0x7c56b6b0L, 0x71159069L, 0x75d48ddeL,
268 0x6b93dddbL, 0x6f52c06cL, 0x6211e6b5L, 0x66d0fb02L,
269 0x5e9f46bfL, 0x5a5e5b08L, 0x571d7dd1L, 0x53dc6066L,
270 0x4d9b3063L, 0x495a2dd4L, 0x44190b0dL, 0x40d816baL,
271 0xaca5c697L, 0xa864db20L, 0xa527fdf9L, 0xa1e6e04eL,
272 0xbfa1b04bL, 0xbb60adfcL, 0xb6238b25L, 0xb2e29692L,
273 0x8aad2b2fL, 0x8e6c3698L, 0x832f1041L, 0x87ee0df6L,
274 0x99a95df3L, 0x9d684044L, 0x902b669dL, 0x94ea7b2aL,
275 0xe0b41de7L, 0xe4750050L, 0xe9362689L, 0xedf73b3eL,
276 0xf3b06b3bL, 0xf771768cL, 0xfa325055L, 0xfef34de2L,
277 0xc6bcf05fL, 0xc27dede8L, 0xcf3ecb31L, 0xcbffd686L,
278 0xd5b88683L, 0xd1799b34L, 0xdc3abdedL, 0xd8fba05aL,
279 0x690ce0eeL, 0x6dcdfd59L, 0x608edb80L, 0x644fc637L,
280 0x7a089632L, 0x7ec98b85L, 0x738aad5cL, 0x774bb0ebL,
281 0x4f040d56L, 0x4bc510e1L, 0x46863638L, 0x42472b8fL,
282 0x5c007b8aL, 0x58c1663dL, 0x558240e4L, 0x51435d53L,
283 0x251d3b9eL, 0x21dc2629L, 0x2c9f00f0L, 0x285e1d47L,
284 0x36194d42L, 0x32d850f5L, 0x3f9b762cL, 0x3b5a6b9bL,
285 0x0315d626L, 0x07d4cb91L, 0x0a97ed48L, 0x0e56f0ffL,
286 0x1011a0faL, 0x14d0bd4dL, 0x19939b94L, 0x1d528623L,
287 0xf12f560eL, 0xf5ee4bb9L, 0xf8ad6d60L, 0xfc6c70d7L,
288 0xe22b20d2L, 0xe6ea3d65L, 0xeba91bbcL, 0xef68060bL,
289 0xd727bbb6L, 0xd3e6a601L, 0xdea580d8L, 0xda649d6fL,
290 0xc423cd6aL, 0xc0e2d0ddL, 0xcda1f604L, 0xc960ebb3L,
291 0xbd3e8d7eL, 0xb9ff90c9L, 0xb4bcb610L, 0xb07daba7L,
292 0xae3afba2L, 0xaafbe615L, 0xa7b8c0ccL, 0xa379dd7bL,
293 0x9b3660c6L, 0x9ff77d71L, 0x92b45ba8L, 0x9675461fL,
294 0x8832161aL, 0x8cf30badL, 0x81b02d74L, 0x857130c3L,
295 0x5d8a9099L, 0x594b8d2eL, 0x5408abf7L, 0x50c9b640L,
296 0x4e8ee645L, 0x4a4ffbf2L, 0x470cdd2bL, 0x43cdc09cL,
297 0x7b827d21L, 0x7f436096L, 0x7200464fL, 0x76c15bf8L,
298 0x68860bfdL, 0x6c47164aL, 0x61043093L, 0x65c52d24L,
299 0x119b4be9L, 0x155a565eL, 0x18197087L, 0x1cd86d30L,
300 0x029f3d35L, 0x065e2082L, 0x0b1d065bL, 0x0fdc1becL,
301 0x3793a651L, 0x3352bbe6L, 0x3e119d3fL, 0x3ad08088L,
302 0x2497d08dL, 0x2056cd3aL, 0x2d15ebe3L, 0x29d4f654L,
303 0xc5a92679L, 0xc1683bceL, 0xcc2b1d17L, 0xc8ea00a0L,
304 0xd6ad50a5L, 0xd26c4d12L, 0xdf2f6bcbL, 0xdbee767cL,
305 0xe3a1cbc1L, 0xe760d676L, 0xea23f0afL, 0xeee2ed18L,
306 0xf0a5bd1dL, 0xf464a0aaL, 0xf9278673L, 0xfde69bc4L,
307 0x89b8fd09L, 0x8d79e0beL, 0x803ac667L, 0x84fbdbd0L,
308 0x9abc8bd5L, 0x9e7d9662L, 0x933eb0bbL, 0x97ffad0cL,
309 0xafb010b1L, 0xab710d06L, 0xa6322bdfL, 0xa2f33668L,
310 0xbcb4666dL, 0xb8757bdaL, 0xb5365d03L, 0xb1f740b4L
313 static void bz_rand_udp_mask(DState *s)
315 if (s->rNToGo == 0) {
316 s->rNToGo = BZ2_rNums[s->rTPos];
318 if (s->rTPos == 512) {
325 static void BZ2_hbCreateDecodeTables(int *limit, int *base, int *perm, unsigned char *length, int minLen, int maxLen, int alphaSize )
330 for (i = minLen; i <= maxLen; i++) {
331 for (j = 0; j < alphaSize; j++) {
332 if (length[j] == i) {
339 for (i = 0; i < BZ_MAX_CODE_LEN; i++) {
343 for (i = 0; i < alphaSize; i++) {
347 for (i = 1; i < BZ_MAX_CODE_LEN; i++) {
348 base[i] += base[i-1];
351 for (i = 0; i < BZ_MAX_CODE_LEN; i++) {
356 for (i = minLen; i <= maxLen; i++) {
357 vec += (base[i+1] - base[i]);
361 for (i = minLen + 1; i <= maxLen; i++) {
362 base[i] = ((limit[i-1] + 1) << 1) - base[i];
367 static int get_bits(DState *s, int *vvv, char nnn)
370 if (s->bsLive >= nnn) {
371 *vvv = (s->bsBuff >> (s->bsLive-nnn)) & ((1 << nnn)-1);
375 if (s->strm->avail_in == 0) {
378 s->bsBuff = (s->bsBuff << 8) | ((unsigned int) (*((unsigned char*)(s->strm->next_in))));
386 static int bz_get_fast(DState *s)
389 s->tPos = s->tt[s->tPos];
390 cccc = (unsigned char)(s->tPos & 0xff);
395 /*---------------------------------------------------*/
396 static inline int BZ2_decompress(DState *s)
402 /* stuff that needs to be saved/restored */
429 int get_mtf_val_init(void)
433 if (groupNo >= nSelectors) {
434 retVal = BZ_DATA_ERROR;
437 groupPos = BZ_G_SIZE;
438 gSel = s->selector[groupNo];
439 gMinlen = s->minLens[gSel];
440 gLimit = &(s->limit[gSel][0]);
441 gPerm = &(s->perm[gSel][0]);
442 gBase = &(s->base[gSel][0]);
449 if (s->state == BZ_X_MAGIC_1) {
450 /*initialise the save area*/
454 s->save_alphaSize = 0;
456 s->save_nSelectors = 0;
459 s->save_groupPos = 0;
461 s->save_nblockMAX = 0;
472 s->save_gLimit = NULL;
473 s->save_gBase = NULL;
474 s->save_gPerm = NULL;
477 /*restore from the save area*/
481 alphaSize = s->save_alphaSize;
482 nGroups = s->save_nGroups;
483 nSelectors = s->save_nSelectors;
485 groupNo = s->save_groupNo;
486 groupPos = s->save_groupPos;
487 nextSym = s->save_nextSym;
488 nblockMAX = s->save_nblockMAX;
489 nblock = s->save_nblock;
498 gMinlen = s->save_gMinlen;
499 gLimit = s->save_gLimit;
500 gBase = s->save_gBase;
501 gPerm = s->save_gPerm;
504 switch_val = s->state;
505 switch (switch_val) {
507 s->state = BZ_X_MAGIC_1;
508 if (! get_bits(s, &uc, 8)) {
510 goto save_state_and_return;
513 retVal = BZ_DATA_ERROR_MAGIC;
514 goto save_state_and_return;
518 s->state = BZ_X_MAGIC_2;
519 if (! get_bits(s, &uc, 8)) {
521 goto save_state_and_return;
524 retVal = BZ_DATA_ERROR_MAGIC;
525 goto save_state_and_return;
529 s->state = BZ_X_MAGIC_3;
530 if (! get_bits(s, &uc, 8)) {
532 goto save_state_and_return;
535 retVal = BZ_DATA_ERROR_MAGIC;
536 goto save_state_and_return;
540 s->state = BZ_X_MAGIC_4;
541 if (! get_bits(s, &s->blockSize100k, 8)) {
543 goto save_state_and_return;
545 if ((s->blockSize100k < '1') || (s->blockSize100k > '9')) {
546 retVal = BZ_DATA_ERROR_MAGIC;
547 goto save_state_and_return;
549 s->blockSize100k -= '0';
551 s->tt = xmalloc(s->blockSize100k * 100000 * sizeof(int));
554 s->state = BZ_X_BLKHDR_1;
555 if (! get_bits(s, &uc, 8)) {
557 goto save_state_and_return;
564 retVal = BZ_DATA_ERROR;
565 goto save_state_and_return;
569 s->state = BZ_X_BLKHDR_2;
570 if (! get_bits(s, &uc, 8)) {
572 goto save_state_and_return;
575 retVal = BZ_DATA_ERROR;
576 goto save_state_and_return;
580 s->state = BZ_X_BLKHDR_3;
581 if (! get_bits(s, &uc, 8)) {
583 goto save_state_and_return;
586 retVal = BZ_DATA_ERROR;
587 goto save_state_and_return;
591 s->state = BZ_X_BLKHDR_4;
592 if (! get_bits(s, &uc, 8)) {
594 goto save_state_and_return;
597 retVal = BZ_DATA_ERROR;
598 goto save_state_and_return;
602 s->state = BZ_X_BLKHDR_5;
603 if (! get_bits(s, &uc, 8)) {
605 goto save_state_and_return;
608 retVal = BZ_DATA_ERROR;
609 goto save_state_and_return;
613 s->state = BZ_X_BLKHDR_6;
614 if (! get_bits(s, &uc, 8)) {
616 goto save_state_and_return;
619 retVal = BZ_DATA_ERROR;
620 goto save_state_and_return;
624 s->storedBlockCRC = 0;
627 s->state = BZ_X_BCRC_1;
628 if (! get_bits(s, &uc, 8)) {
630 goto save_state_and_return;
632 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
635 s->state = BZ_X_BCRC_2;
636 if (! get_bits(s, &uc, 8)) {
638 goto save_state_and_return;
640 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
643 s->state = BZ_X_BCRC_3;
644 if (! get_bits(s, &uc, 8)) {
646 goto save_state_and_return;
648 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
651 s->state = BZ_X_BCRC_4;
652 if (! get_bits(s, &uc, 8)) {
654 goto save_state_and_return;
656 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((unsigned int)uc);
659 s->state = BZ_X_RANDBIT;
661 int tmp = s->blockRandomised;
662 const int ret = get_bits(s, &tmp, 1);
663 s->blockRandomised = tmp;
666 goto save_state_and_return;
673 s->state = BZ_X_ORIGPTR_1;
674 if (! get_bits(s, &uc, 8)) {
676 goto save_state_and_return;
678 s->origPtr = (s->origPtr << 8) | ((int)uc);
681 s->state = BZ_X_ORIGPTR_2;
682 if (! get_bits(s, &uc, 8)) {
684 goto save_state_and_return;
686 s->origPtr = (s->origPtr << 8) | ((int)uc);
689 s->state = BZ_X_ORIGPTR_3;
690 if (! get_bits(s, &uc, 8)) {
692 goto save_state_and_return;
694 s->origPtr = (s->origPtr << 8) | ((int)uc);
696 if (s->origPtr < 0) {
697 retVal = BZ_DATA_ERROR;
698 goto save_state_and_return;
700 if (s->origPtr > 10 + 100000*s->blockSize100k) {
701 retVal = BZ_DATA_ERROR;
702 goto save_state_and_return;
705 /*--- Receive the mapping table ---*/
707 for (i = 0; i < 16; i++) {
708 s->state = BZ_X_MAPPING_1;
709 if (! get_bits(s, &uc, 1)) {
711 goto save_state_and_return;
714 s->inUse16[i] = TRUE;
716 s->inUse16[i] = FALSE;
720 for (i = 0; i < 256; i++) {
724 for (i = 0; i < 16; i++) {
726 for (j = 0; j < 16; j++) {
728 s->state = BZ_X_MAPPING_2;
729 if (! get_bits(s, &uc, 1)) {
731 goto save_state_and_return;
734 s->inUse[i * 16 + j] = TRUE;
741 for (i = 0; i < 256; i++) {
743 s->seqToUnseq[s->nInUse] = i;
747 if (s->nInUse == 0) {
748 retVal = BZ_DATA_ERROR;
749 goto save_state_and_return;
751 alphaSize = s->nInUse+2;
753 /*--- Now the selectors ---*/
754 case BZ_X_SELECTOR_1:
755 s->state = BZ_X_SELECTOR_1;
756 if (! get_bits(s, &nGroups, 3)) {
758 goto save_state_and_return;
760 if (nGroups < 2 || nGroups > 6) {
761 retVal = BZ_DATA_ERROR;
762 goto save_state_and_return;
765 case BZ_X_SELECTOR_2:
766 s->state = BZ_X_SELECTOR_2;
767 if (! get_bits(s, &nSelectors, 15)) {
769 goto save_state_and_return;
771 if (nSelectors < 1) {
772 retVal = BZ_DATA_ERROR;
773 goto save_state_and_return;
778 for (i = 0; i < nSelectors; i++) {
781 case BZ_X_SELECTOR_3:
782 s->state = BZ_X_SELECTOR_3;
783 if (! get_bits(s, &uc, 1)) {
785 goto save_state_and_return;
792 retVal = BZ_DATA_ERROR;
793 goto save_state_and_return;
796 s->selectorMtf[i] = j;
799 /*--- Undo the MTF values for the selectors. ---*/
801 unsigned char pos[BZ_N_GROUPS], tmp, v;
802 for (v = 0; v < nGroups; v++) {
805 for (i = 0; i < nSelectors; i++) {
806 v = s->selectorMtf[i];
813 s->selector[i] = tmp;
817 /*--- Now the coding tables ---*/
818 for (t = 0; t < nGroups; t++) {
820 s->state = BZ_X_CODING_1;
821 if (! get_bits(s, &curr, 5)) {
823 goto save_state_and_return;
825 for (i = 0; i < alphaSize; i++) {
827 if (curr < 1 || curr > 20) {
828 retVal = BZ_DATA_ERROR;
829 goto save_state_and_return;
833 s->state = BZ_X_CODING_2;
834 if (! get_bits(s, &uc, 1)) {
836 goto save_state_and_return;
843 s->state = BZ_X_CODING_3;
844 if (! get_bits(s, &uc, 1)) {
846 goto save_state_and_return;
858 /*--- Create the Huffman decoding tables ---*/
859 for (t = 0; t < nGroups; t++) {
862 for (i = 0; i < alphaSize; i++) {
863 if (s->len[t][i] > maxLen) {
864 maxLen = s->len[t][i];
866 if (s->len[t][i] < minLen) {
867 minLen = s->len[t][i];
871 BZ2_hbCreateDecodeTables (
876 minLen, maxLen, alphaSize
880 s->minLens[t] = minLen;
883 /*--- Now the MTF values ---*/
886 nblockMAX = 100000 * s->blockSize100k;
890 for (i = 0; i <= 255; i++) {
897 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
898 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
899 s->mtfa[kk] = (unsigned char)(ii * MTFL_SIZE + jj);
902 s->mtfbase[ii] = kk + 1;
905 /*-- end MTF init --*/
909 if (! get_mtf_val_init()) {
910 goto save_state_and_return;
913 s->state = BZ_X_MTF_1;
914 if (! get_bits(s, &zvec, zn)) {
916 goto save_state_and_return;
919 if (zn > 20 /* the longest code */) {
920 retVal = BZ_DATA_ERROR;
921 goto save_state_and_return;
923 if (zvec <= gLimit[zn]) {
929 s->state = BZ_X_MTF_2;
930 if (! get_bits(s, &zj, 1)) {
932 goto save_state_and_return;
934 zvec = (zvec << 1) | zj;
936 if (zvec - gBase[zn] < 0 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) {
937 retVal = BZ_DATA_ERROR;
938 goto save_state_and_return;
940 nextSym = gPerm[zvec - gBase[zn]];
943 if (nextSym == EOB) {
947 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
951 if (nextSym == BZ_RUNA) {
954 if (nextSym == BZ_RUNB) {
959 if (! get_mtf_val_init()) {
960 goto save_state_and_return;
963 s->state = BZ_X_MTF_3;
964 if (! get_bits(s, &zvec, zn)) {
966 goto save_state_and_return;
969 if (zn > 20 /* the longest code */) {
970 retVal = BZ_DATA_ERROR;
971 goto save_state_and_return;
973 if (zvec <= gLimit[zn]) {
979 s->state = BZ_X_MTF_4;
980 if (! get_bits(s, &zj, 1)) {
982 goto save_state_and_return;
984 zvec = (zvec << 1) | zj;
986 if (zvec - gBase[zn] < 0 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) {
987 retVal = BZ_DATA_ERROR;
988 goto save_state_and_return;
991 nextSym = gPerm[zvec - gBase[zn]];
993 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
996 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
997 s->unzftab[uc] += es;
1000 if (nblock >= nblockMAX) {
1001 retVal = BZ_DATA_ERROR;
1002 goto save_state_and_return;
1004 s->tt[nblock] = (unsigned int)uc;
1010 if (nblock >= nblockMAX) {
1011 retVal = BZ_DATA_ERROR;
1012 goto save_state_and_return;
1014 /*-- uc = MTF ( nextSym-1 ) --*/
1016 int ii, jj, kk, pp, lno, off;
1018 nn = (unsigned int)(nextSym - 1);
1020 if (nn < MTFL_SIZE) {
1021 /* avoid general-case expense */
1023 uc = s->mtfa[pp+nn];
1026 s->mtfa[(z) ] = s->mtfa[(z)-1];
1027 s->mtfa[(z)-1] = s->mtfa[(z)-2];
1028 s->mtfa[(z)-2] = s->mtfa[(z)-3];
1029 s->mtfa[(z)-3] = s->mtfa[(z)-4];
1033 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
1038 lno = nn / MTFL_SIZE;
1039 off = nn % MTFL_SIZE;
1040 pp = s->mtfbase[lno] + off;
1042 while (pp > s->mtfbase[lno]) {
1043 s->mtfa[pp] = s->mtfa[pp-1];
1049 s->mtfa[s->mtfbase[lno]] = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
1053 s->mtfa[s->mtfbase[0]] = uc;
1054 if (s->mtfbase[0] == 0) {
1056 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
1057 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
1058 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
1061 s->mtfbase[ii] = kk + 1;
1066 /*-- end uc = MTF ( nextSym-1 ) --*/
1068 s->unzftab[s->seqToUnseq[uc]]++;
1069 s->tt[nblock] = (unsigned int)(s->seqToUnseq[uc]);
1072 if (! get_mtf_val_init()) {
1073 goto save_state_and_return;
1076 s->state = BZ_X_MTF_5;
1077 if (! get_bits(s, &zvec, zn)) {
1079 goto save_state_and_return;
1082 if (zn > 20 /* the longest code */) {
1083 retVal = BZ_DATA_ERROR;
1084 goto save_state_and_return;
1086 if (zvec <= gLimit[zn]) {
1092 s->state = BZ_X_MTF_6;
1093 if (! get_bits(s, &zj, 1)) {
1095 goto save_state_and_return;
1097 zvec = (zvec << 1) | zj;
1099 if (zvec - gBase[zn] < 0 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) {
1100 retVal = BZ_DATA_ERROR;
1101 goto save_state_and_return;
1103 nextSym = gPerm[zvec - gBase[zn]];
1108 /* Now we know what nblock is, we can do a better sanity
1109 check on s->origPtr.
1111 if (s->origPtr < 0 || s->origPtr >= nblock) {
1112 retVal = BZ_DATA_ERROR;
1113 goto save_state_and_return;
1115 s->state_out_len = 0;
1116 s->state_out_ch = 0;
1117 s->calculatedBlockCRC = 0xffffffffL;
1118 s->state = BZ_X_OUTPUT;
1120 /*-- Set up cftab to facilitate generation of T^(-1) --*/
1122 for (i = 1; i <= 256; i++) {
1123 s->cftab[i] = s->unzftab[i-1];
1125 for (i = 1; i <= 256; i++) {
1126 s->cftab[i] += s->cftab[i-1];
1129 /*-- compute the T^(-1) vector --*/
1130 for (i = 0; i < nblock; i++) {
1131 uc = (unsigned char)(s->tt[i] & 0xff);
1132 s->tt[s->cftab[uc]] |= (i << 8);
1136 s->tPos = s->tt[s->origPtr] >> 8;
1138 if (s->blockRandomised) {
1141 s->k0 = bz_get_fast(s);
1144 bz_rand_udp_mask(s);
1145 s->k0 ^= ((s->rNToGo == 1) ? 1 : 0);
1147 s->k0 = bz_get_fast(s);
1152 goto save_state_and_return;
1156 s->state = BZ_X_ENDHDR_2;
1157 if (! get_bits(s, &uc, 8)) {
1159 goto save_state_and_return;
1162 retVal = BZ_DATA_ERROR;
1163 goto save_state_and_return;
1167 s->state = BZ_X_ENDHDR_3;
1168 if (! get_bits(s, &uc, 8)) {
1170 goto save_state_and_return;
1173 retVal = BZ_DATA_ERROR;
1174 goto save_state_and_return;
1178 s->state = BZ_X_ENDHDR_4;
1179 if (! get_bits(s, &uc, 8)) {
1181 goto save_state_and_return;
1184 retVal = BZ_DATA_ERROR;
1185 goto save_state_and_return;
1189 s->state = BZ_X_ENDHDR_5;
1190 if (! get_bits(s, &uc, 8)) {
1192 goto save_state_and_return;
1195 retVal = BZ_DATA_ERROR;
1196 goto save_state_and_return;
1200 s->state = BZ_X_ENDHDR_6;
1201 if (! get_bits(s, &uc, 8)) {
1203 goto save_state_and_return;
1206 retVal = BZ_DATA_ERROR;
1207 goto save_state_and_return;
1209 s->storedCombinedCRC = 0;
1212 s->state = BZ_X_CCRC_1;
1213 if (! get_bits(s, &uc, 8)) {
1215 goto save_state_and_return;
1217 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1219 s->state = BZ_X_CCRC_2;
1220 if (! get_bits(s, &uc, 8)) {
1222 goto save_state_and_return;
1224 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1227 s->state = BZ_X_CCRC_3;
1228 if (! get_bits(s, &uc, 8)) {
1230 goto save_state_and_return;
1232 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1235 s->state = BZ_X_CCRC_4;
1236 if (! get_bits(s, &uc, 8)) {
1238 goto save_state_and_return;
1240 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((unsigned int)uc);
1242 s->state = BZ_X_IDLE;
1243 retVal = BZ_STREAM_END;
1244 goto save_state_and_return;
1248 save_state_and_return:
1252 s->save_alphaSize = alphaSize;
1253 s->save_nGroups = nGroups;
1254 s->save_nSelectors = nSelectors;
1256 s->save_groupNo = groupNo;
1257 s->save_groupPos = groupPos;
1258 s->save_nextSym = nextSym;
1259 s->save_nblockMAX = nblockMAX;
1260 s->save_nblock = nblock;
1263 s->save_curr = curr;
1266 s->save_zvec = zvec;
1268 s->save_gSel = gSel;
1269 s->save_gMinlen = gMinlen;
1270 s->save_gLimit = gLimit;
1271 s->save_gBase = gBase;
1272 s->save_gPerm = gPerm;
1277 static void BZ2_bzReadClose(void)
1279 if (bzf->initialisedOk) {
1280 bz_stream *strm = &(bzf->strm);
1286 if ((s == NULL) || (s->strm != strm)) {
1297 static void unRLE_obuf_to_output_FAST(DState *s)
1301 if (s->blockRandomised) {
1303 /* try to finish existing run */
1305 if (s->strm->avail_out == 0) {
1308 if (s->state_out_len == 0) {
1311 *((unsigned char *)(s->strm->next_out)) = s->state_out_ch;
1312 s->calculatedBlockCRC = (s->calculatedBlockCRC << 8) ^
1313 BZ2_crc32Table[(s->calculatedBlockCRC >> 24) ^
1314 ((unsigned char)s->state_out_ch)];
1316 s->strm->next_out++;
1317 s->strm->avail_out--;
1320 /* can a new run be started? */
1321 if (s->nblock_used == s->save_nblock+1) {
1324 s->state_out_len = 1;
1325 s->state_out_ch = s->k0;
1326 k1 = bz_get_fast(s);
1327 bz_rand_udp_mask(s);
1328 k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1330 if (s->nblock_used == s->save_nblock+1) {
1338 s->state_out_len = 2;
1339 k1 = bz_get_fast(s);
1340 bz_rand_udp_mask(s);
1341 k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1343 if (s->nblock_used == s->save_nblock+1) {
1350 s->state_out_len = 3;
1351 k1 = bz_get_fast(s);
1352 bz_rand_udp_mask(s);
1353 k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1355 if (s->nblock_used == s->save_nblock+1) {
1363 k1 = bz_get_fast(s);
1364 bz_rand_udp_mask(s);
1365 k1 ^= ((s->rNToGo == 1) ? 1 : 0);
1367 s->state_out_len = ((int)k1) + 4;
1368 s->k0 = bz_get_fast(s);
1369 bz_rand_udp_mask(s);
1370 s->k0 ^= ((s->rNToGo == 1) ? 1 : 0);
1375 unsigned int c_calculatedBlockCRC = s->calculatedBlockCRC;
1376 unsigned char c_state_out_ch = s->state_out_ch;
1377 int c_state_out_len = s->state_out_len;
1378 int c_nblock_used = s->nblock_used;
1380 unsigned int *c_tt = s->tt;
1381 unsigned int c_tPos = s->tPos;
1382 char *cs_next_out = s->strm->next_out;
1383 unsigned int cs_avail_out = s->strm->avail_out;
1386 int s_save_nblockPP = s->save_nblock+1;
1389 /* try to finish existing run */
1390 if (c_state_out_len > 0) {
1392 if (cs_avail_out == 0) {
1395 if (c_state_out_len == 1) {
1398 *((unsigned char *)(cs_next_out)) = c_state_out_ch;
1399 c_calculatedBlockCRC = (c_calculatedBlockCRC << 8) ^
1400 BZ2_crc32Table[(c_calculatedBlockCRC >> 24) ^
1401 ((unsigned char)c_state_out_ch)];
1406 s_state_out_len_eq_one:
1408 if (cs_avail_out == 0) {
1409 c_state_out_len = 1;
1412 *((unsigned char *)(cs_next_out)) = c_state_out_ch;
1413 c_calculatedBlockCRC = (c_calculatedBlockCRC << 8) ^
1414 BZ2_crc32Table[(c_calculatedBlockCRC >> 24) ^
1415 ((unsigned char)c_state_out_ch)];
1420 /* can a new run be started? */
1421 if (c_nblock_used == s_save_nblockPP) {
1422 c_state_out_len = 0; goto return_notr;
1424 c_state_out_ch = c_k0;
1425 c_tPos = c_tt[c_tPos];
1426 k1 = (unsigned char)(c_tPos & 0xff);
1433 goto s_state_out_len_eq_one;
1436 if (c_nblock_used == s_save_nblockPP) {
1437 goto s_state_out_len_eq_one;
1440 c_state_out_len = 2;
1441 c_tPos = c_tt[c_tPos];
1442 k1 = (unsigned char)(c_tPos & 0xff);
1446 if (c_nblock_used == s_save_nblockPP) {
1454 c_state_out_len = 3;
1455 c_tPos = c_tt[c_tPos];
1456 k1 = (unsigned char)(c_tPos & 0xff);
1460 if (c_nblock_used == s_save_nblockPP) {
1468 c_tPos = c_tt[c_tPos];
1469 k1 = (unsigned char)(c_tPos & 0xff);
1473 c_state_out_len = ((int)k1) + 4;
1475 c_tPos = c_tt[c_tPos];
1476 c_k0 = (unsigned char)(c_tPos & 0xff);
1485 s->calculatedBlockCRC = c_calculatedBlockCRC;
1486 s->state_out_ch = c_state_out_ch;
1487 s->state_out_len = c_state_out_len;
1488 s->nblock_used = c_nblock_used;
1492 s->strm->next_out = cs_next_out;
1493 s->strm->avail_out = cs_avail_out;
1498 int BZ2_bzDecompress(bz_stream *strm)
1504 if (s->state == BZ_X_IDLE) {
1505 return BZ_SEQUENCE_ERROR;
1507 if (s->state == BZ_X_OUTPUT) {
1508 unRLE_obuf_to_output_FAST(s);
1509 if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) {
1510 s->calculatedBlockCRC = ~(s->calculatedBlockCRC);
1511 if (s->calculatedBlockCRC != s->storedBlockCRC) {
1512 return BZ_DATA_ERROR;
1514 s->calculatedCombinedCRC = (s->calculatedCombinedCRC << 1) | (s->calculatedCombinedCRC >> 31);
1515 s->calculatedCombinedCRC ^= s->calculatedBlockCRC;
1516 s->state = BZ_X_BLKHDR_1;
1521 if (s->state >= BZ_X_MAGIC_1) {
1522 int r = BZ2_decompress(s);
1523 if (r == BZ_STREAM_END) {
1524 if (s->calculatedCombinedCRC != s->storedCombinedCRC) {
1525 return BZ_DATA_ERROR;
1529 if (s->state != BZ_X_OUTPUT) {
1535 return(0); /*NOTREACHED*/
1538 extern ssize_t read_bz2(int fd, void *buf, size_t count)
1546 bzf->strm.avail_out = count;
1547 bzf->strm.next_out = buf;
1550 if (bzf->strm.avail_in == 0) {
1551 n = xread(bzf->fd, bzf->buf, BZ_MAX_UNUSED);
1556 bzf->strm.avail_in = bzf->bufN;
1557 bzf->strm.next_in = bzf->buf;
1560 ret = BZ2_bzDecompress(&(bzf->strm));
1562 if ((ret != BZ_OK) && (ret != BZ_STREAM_END)) {
1563 error_msg_and_die("Error decompressing");
1566 if (ret == BZ_STREAM_END) {
1567 bzerr = BZ_STREAM_END;
1568 return(count - bzf->strm.avail_out);
1570 if (bzf->strm.avail_out == 0) {
1578 extern void BZ2_bzReadOpen(int fd, void *unused, int nUnused)
1582 bzf = xmalloc(sizeof(bzFile));
1583 bzf->initialisedOk = FALSE;
1587 s = xmalloc(sizeof(DState));
1588 s->strm = &bzf->strm;
1589 s->state = BZ_X_MAGIC_1;
1592 s->calculatedCombinedCRC = 0;
1595 bzf->strm.state = s;
1597 while (nUnused > 0) {
1598 bzf->buf[bzf->bufN] = *((unsigned char *)(unused));
1600 unused = ((void *)( 1 + ((unsigned char *)(unused)) ));
1603 bzf->strm.avail_in = bzf->bufN;
1604 bzf->strm.next_in = bzf->buf;
1606 bzf->initialisedOk = TRUE;
1611 extern unsigned char uncompressStream(int src_fd, int dst_fd)
1613 unsigned char unused[BZ_MAX_UNUSED];
1614 unsigned char *unusedTmp;
1615 unsigned char obuf[5000];
1625 BZ2_bzReadOpen(src_fd, unused, nUnused);
1628 while (bzerr == BZ_OK) {
1629 nread = read_bz2(src_fd, obuf, 5000);
1630 if (bzerr == BZ_DATA_ERROR_MAGIC) {
1631 error_msg_and_die("invalid magic");
1633 if (((bzerr == BZ_OK) || (bzerr == BZ_STREAM_END)) && (nread > 0)) {
1634 if (write(dst_fd, obuf, nread) != nread) {
1636 perror_msg_and_die("Couldnt write to file");
1640 nUnused = bzf->strm.avail_in;
1641 unusedTmp = bzf->strm.next_in;
1643 for (i = 0; i < nUnused; i++) {
1644 unused[i] = unusedTmp[i];
1653 if (dst_fd != fileno(stdout)) {