7 * THIS FILE IS NOT IDENTICAL TO THE ORIGINAL
8 * FROM THE BZIP2 DISTRIBUTION.
10 * It has been modified, mainly to break the library
11 * into smaller pieces.
14 * rsc@plan9.bell-labs.com
18 /*---------------------------------------------*/
20 Place a 1 beside your platform, and 0 elsewhere.
21 Attempts to autosniff this even if you don't.
31 #define exit(x) exits((x) ? "whoops" : nil)
35 # define NORETURN __attribute__ ((noreturn))
37 # define NORETURN /**/
41 Some more stuff for all platforms :-)
42 This might have to get moved into the platform-specific
43 header files if we encounter a machine with different sizes.
47 typedef unsigned char Bool;
48 typedef unsigned char UChar;
50 typedef unsigned int UInt32;
52 typedef unsigned short UInt16;
54 #define True ((Bool)1)
55 #define False ((Bool)0)
58 IntNative is your platform's `native' int size.
59 Only here to avoid probs with 64-bit platforms.
61 typedef int IntNative;
65 #include "bzlib_private.h"
68 bunzip(int ofd, char *ofile, Biobuf *bin)
70 int e, n, done, onemore;
78 memset(&strm, 0, sizeof strm);
79 BZ2_bzDecompressInit(&strm, 0, 0);
84 strm.avail_out = sizeof obuf;
87 Binit(&bout, ofd, OWRITE);
90 * onemore is a crummy hack to go 'round the loop
91 * once after we finish, to flush the output buffer.
96 if(!done && strm.avail_in < sizeof buf) {
98 memmove(buf, strm.next_in, strm.avail_in);
100 n = Bread(bin, buf+strm.avail_in, sizeof(buf)-strm.avail_in);
107 if(strm.avail_out < sizeof obuf) {
108 Bwrite(&bout, obuf, sizeof(obuf)-strm.avail_out);
109 strm.next_out = obuf;
110 strm.avail_out = sizeof obuf;
115 } while((e=BZ2_bzDecompress(&strm)) == BZ_OK || onemore--);
117 if(e != BZ_STREAM_END) {
118 fprint(2, "bunzip2: decompress failed\n");
122 if(BZ2_bzDecompressEnd(&strm) != BZ_OK) {
123 fprint(2, "bunzip2: decompress end failed (can't happen)\n");
133 _unbzip(int in, int out)
137 Binit(&bin, in, OREAD);
138 if(bunzip(out, nil, &bin) != 1) {
139 fprint(2, "bunzip2 failed\n");
150 sysfatal("pipe: %r");
154 switch(rfork(RFPROC|RFFDG|RFNOTEG|RFMEM)){
156 sysfatal("fork: %r");
168 return -1; /* not reached */
171 int bz_config_ok ( void )
173 if (sizeof(int) != 4) return 0;
174 if (sizeof(short) != 2) return 0;
175 if (sizeof(char) != 1) return 0;
179 void* default_bzalloc(void *o, int items, int size)
182 return sbrk(items*size);
185 void default_bzfree(void*, void*)
190 bz_internal_error(int)
195 /*-------------------------------------------------------------*/
196 /*--- Decompression machinery ---*/
197 /*--- decompress.c ---*/
198 /*-------------------------------------------------------------*/
201 This file is a part of bzip2 and/or libbzip2, a program and
202 library for lossless, block-sorting data compression.
204 Copyright (C) 1996-2000 Julian R Seward. All rights reserved.
206 Redistribution and use in source and binary forms, with or without
207 modification, are permitted provided that the following conditions
210 1. Redistributions of source code must retain the above copyright
211 notice, this list of conditions and the following disclaimer.
213 2. The origin of this software must not be misrepresented; you must
214 not claim that you wrote the original software. If you use this
215 software in a product, an acknowledgment in the product
216 documentation would be appreciated but is not required.
218 3. Altered source versions must be plainly marked as such, and must
219 not be misrepresented as being the original software.
221 4. The name of the author may not be used to endorse or promote
222 products derived from this software without specific prior written
225 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
226 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
227 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
228 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
229 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
230 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
231 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
232 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
233 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
234 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
235 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
237 Julian Seward, Cambridge, UK.
239 bzip2/libbzip2 version 1.0 of 21 March 2000
241 This program is based on (at least) the work of:
251 For more information on these sources, see the manual.
256 /*---------------------------------------------------*/
258 void makeMaps_d ( DState* s )
262 for (i = 0; i < 256; i++)
264 s->seqToUnseq[s->nInUse] = i;
270 /*---------------------------------------------------*/
271 #define RETURN(rrr) \
272 { retVal = rrr; goto save_state_and_return; };
274 #define GET_BITS(lll,vvv,nnn) \
276 { int x; if((retVal = getbits(s, lll, &x, nnn)) != 99) \
277 goto save_state_and_return; vvv=x; }\
280 getbits(DState *s, int lll, int *vvv, int nnn)
285 if (s->bsLive >= nnn) {
288 (s->bsLive-nnn)) & ((1 << nnn)-1);
293 if (s->strm->avail_in == 0) return BZ_OK;
297 (*((UChar*)(s->strm->next_in))));
301 s->strm->total_in_lo32++;
302 if (s->strm->total_in_lo32 == 0)
303 s->strm->total_in_hi32++;
307 #define GET_UCHAR(lll,uuu) \
310 #define GET_BIT(lll,uuu) \
313 /*---------------------------------------------------*/
314 #define GET_MTF_VAL(label1,label2,lval) \
316 if (groupPos == 0) { \
318 if (groupNo >= nSelectors) \
319 RETURN(BZ_DATA_ERROR); \
320 groupPos = BZ_G_SIZE; \
321 gSel = s->selector[groupNo]; \
322 gMinlen = s->minLens[gSel]; \
323 gLimit = &(s->limit[gSel][0]); \
324 gPerm = &(s->perm[gSel][0]); \
325 gBase = &(s->base[gSel][0]); \
329 GET_BITS(label1, zvec, zn); \
331 if (zn > 20 /* the longest code */) \
332 RETURN(BZ_DATA_ERROR); \
333 if (zvec <= gLimit[zn]) break; \
335 GET_BIT(label2, zj); \
336 zvec = (zvec << 1) | zj; \
338 if (zvec - gBase[zn] < 0 \
339 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \
340 RETURN(BZ_DATA_ERROR); \
341 lval = gPerm[zvec - gBase[zn]]; \
345 /*---------------------------------------------------*/
346 Int32 BZ2_decompress ( DState* s )
350 Int32 minLen, maxLen;
351 bz_stream* strm = s->strm;
353 /* stuff that needs to be saved/restored */
379 if (s->state == BZ_X_MAGIC_1) {
380 /*initialise the save area*/
384 s->save_alphaSize = 0;
386 s->save_nSelectors = 0;
389 s->save_groupPos = 0;
391 s->save_nblockMAX = 0;
402 s->save_gLimit = NULL;
403 s->save_gBase = NULL;
404 s->save_gPerm = NULL;
407 /*restore from the save area*/
411 alphaSize = s->save_alphaSize;
412 nGroups = s->save_nGroups;
413 nSelectors = s->save_nSelectors;
415 groupNo = s->save_groupNo;
416 groupPos = s->save_groupPos;
417 nextSym = s->save_nextSym;
418 nblockMAX = s->save_nblockMAX;
419 nblock = s->save_nblock;
428 gMinlen = s->save_gMinlen;
429 gLimit = s->save_gLimit;
430 gBase = s->save_gBase;
431 gPerm = s->save_gPerm;
437 GET_UCHAR(BZ_X_MAGIC_1, uc);
438 if (uc != 'B') RETURN(BZ_DATA_ERROR_MAGIC);
440 GET_UCHAR(BZ_X_MAGIC_2, uc);
441 if (uc != 'Z') RETURN(BZ_DATA_ERROR_MAGIC);
443 GET_UCHAR(BZ_X_MAGIC_3, uc)
444 if (uc != 'h') RETURN(BZ_DATA_ERROR_MAGIC);
446 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
447 if (s->blockSize100k < '1' ||
448 s->blockSize100k > '9') RETURN(BZ_DATA_ERROR_MAGIC);
449 s->blockSize100k -= '0';
451 if (0 && s->smallDecompress) {
452 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
454 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
456 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
458 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
459 if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
462 GET_UCHAR(BZ_X_BLKHDR_1, uc);
464 if (uc == 0x17) goto endhdr_2;
465 if (uc != 0x31) RETURN(BZ_DATA_ERROR);
466 GET_UCHAR(BZ_X_BLKHDR_2, uc);
467 if (uc != 0x41) RETURN(BZ_DATA_ERROR);
468 GET_UCHAR(BZ_X_BLKHDR_3, uc);
469 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
470 GET_UCHAR(BZ_X_BLKHDR_4, uc);
471 if (uc != 0x26) RETURN(BZ_DATA_ERROR);
472 GET_UCHAR(BZ_X_BLKHDR_5, uc);
473 if (uc != 0x53) RETURN(BZ_DATA_ERROR);
474 GET_UCHAR(BZ_X_BLKHDR_6, uc);
475 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
478 // if (s->verbosity >= 2)
479 // VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo );
481 s->storedBlockCRC = 0;
482 GET_UCHAR(BZ_X_BCRC_1, uc);
483 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
484 GET_UCHAR(BZ_X_BCRC_2, uc);
485 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
486 GET_UCHAR(BZ_X_BCRC_3, uc);
487 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
488 GET_UCHAR(BZ_X_BCRC_4, uc);
489 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
491 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
494 GET_UCHAR(BZ_X_ORIGPTR_1, uc);
495 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
496 GET_UCHAR(BZ_X_ORIGPTR_2, uc);
497 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
498 GET_UCHAR(BZ_X_ORIGPTR_3, uc);
499 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
502 RETURN(BZ_DATA_ERROR);
503 if (s->origPtr > 10 + 100000*s->blockSize100k)
504 RETURN(BZ_DATA_ERROR);
506 /*--- Receive the mapping table ---*/
507 for (i = 0; i < 16; i++) {
508 GET_BIT(BZ_X_MAPPING_1, uc);
510 s->inUse16[i] = True; else
511 s->inUse16[i] = False;
514 for (i = 0; i < 256; i++) s->inUse[i] = False;
516 for (i = 0; i < 16; i++)
518 for (j = 0; j < 16; j++) {
519 GET_BIT(BZ_X_MAPPING_2, uc);
520 if (uc == 1) s->inUse[i * 16 + j] = True;
523 if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
524 alphaSize = s->nInUse+2;
526 /*--- Now the selectors ---*/
527 GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
528 if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
529 GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
530 if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
531 for (i = 0; i < nSelectors; i++) {
534 GET_BIT(BZ_X_SELECTOR_3, uc);
537 if (j >= nGroups) RETURN(BZ_DATA_ERROR);
539 s->selectorMtf[i] = j;
542 /*--- Undo the MTF values for the selectors. ---*/
544 UChar pos[BZ_N_GROUPS], tmp, v;
545 for (v = 0; v < nGroups; v++) pos[v] = v;
547 for (i = 0; i < nSelectors; i++) {
548 v = s->selectorMtf[i];
550 while (v > 0) { pos[v] = pos[v-1]; v--; }
552 s->selector[i] = tmp;
556 /*--- Now the coding tables ---*/
557 for (t = 0; t < nGroups; t++) {
558 GET_BITS(BZ_X_CODING_1, curr, 5);
559 for (i = 0; i < alphaSize; i++) {
561 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
562 GET_BIT(BZ_X_CODING_2, uc);
564 GET_BIT(BZ_X_CODING_3, uc);
565 if (uc == 0) curr++; else curr--;
571 /*--- Create the Huffman decoding tables ---*/
572 for (t = 0; t < nGroups; t++) {
575 for (i = 0; i < alphaSize; i++) {
576 if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
577 if (s->len[t][i] < minLen) minLen = s->len[t][i];
579 BZ2_hbCreateDecodeTables (
584 minLen, maxLen, alphaSize
586 s->minLens[t] = minLen;
589 /*--- Now the MTF values ---*/
592 nblockMAX = 100000 * s->blockSize100k;
596 for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
602 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
603 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
604 s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
607 s->mtfbase[ii] = kk + 1;
610 /*-- end MTF init --*/
613 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
617 if (nextSym == EOB) break;
619 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
624 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
625 if (nextSym == BZ_RUNB) es = es + (1+1) * N;
627 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
629 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
632 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
633 s->unzftab[uc] += es;
635 if (0 && s->smallDecompress)
637 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
638 s->ll16[nblock] = (UInt16)uc;
644 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
645 s->tt[nblock] = (UInt32)uc;
654 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
656 /*-- uc = MTF ( nextSym-1 ) --*/
658 Int32 ii, jj, kk, pp, lno, off;
660 nn = (UInt32)(nextSym - 1);
662 if (nn < MTFL_SIZE) {
663 /* avoid general-case expense */
668 s->mtfa[(z) ] = s->mtfa[(z)-1];
669 s->mtfa[(z)-1] = s->mtfa[(z)-2];
670 s->mtfa[(z)-2] = s->mtfa[(z)-3];
671 s->mtfa[(z)-3] = s->mtfa[(z)-4];
675 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
680 lno = nn / MTFL_SIZE;
681 off = nn % MTFL_SIZE;
682 pp = s->mtfbase[lno] + off;
684 while (pp > s->mtfbase[lno]) {
685 s->mtfa[pp] = s->mtfa[pp-1]; pp--;
690 s->mtfa[s->mtfbase[lno]]
691 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
695 s->mtfa[s->mtfbase[0]] = uc;
696 if (s->mtfbase[0] == 0) {
698 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
699 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
700 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
703 s->mtfbase[ii] = kk + 1;
708 /*-- end uc = MTF ( nextSym-1 ) --*/
710 s->unzftab[s->seqToUnseq[uc]]++;
711 if (0 && s->smallDecompress)
712 s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
713 s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]);
716 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
721 /* Now we know what nblock is, we can do a better sanity
724 if (s->origPtr < 0 || s->origPtr >= nblock)
725 RETURN(BZ_DATA_ERROR);
727 s->state_out_len = 0;
729 BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
730 s->state = BZ_X_OUTPUT;
731 // if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
733 /*-- Set up cftab to facilitate generation of T^(-1) --*/
735 for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
736 for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
738 if (0 && s->smallDecompress) {
740 /*-- Make a copy of cftab, used in generation of T --*/
741 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
743 /*-- compute the T vector --*/
744 for (i = 0; i < nblock; i++) {
745 uc = (UChar)(s->ll16[i]);
746 SET_LL(i, s->cftabCopy[uc]);
750 /*-- Compute T^(-1) by pointer reversal on T --*/
754 Int32 tmp = GET_LL(j);
759 while (i != s->origPtr);
761 s->tPos = s->origPtr;
763 if (s->blockRandomised) {
765 BZ_GET_SMALL(s->k0); s->nblock_used++;
766 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
768 BZ_GET_SMALL(s->k0); s->nblock_used++;
773 /*-- compute the T^(-1) vector --*/
774 for (i = 0; i < nblock; i++) {
775 uc = (UChar)(s->tt[i] & 0xff);
776 s->tt[s->cftab[uc]] |= (i << 8);
780 s->tPos = s->tt[s->origPtr] >> 8;
782 if (s->blockRandomised) {
784 BZ_GET_FAST(s->k0); s->nblock_used++;
785 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
787 BZ_GET_FAST(s->k0); s->nblock_used++;
798 GET_UCHAR(BZ_X_ENDHDR_2, uc);
799 if (uc != 0x72) RETURN(BZ_DATA_ERROR);
800 GET_UCHAR(BZ_X_ENDHDR_3, uc);
801 if (uc != 0x45) RETURN(BZ_DATA_ERROR);
802 GET_UCHAR(BZ_X_ENDHDR_4, uc);
803 if (uc != 0x38) RETURN(BZ_DATA_ERROR);
804 GET_UCHAR(BZ_X_ENDHDR_5, uc);
805 if (uc != 0x50) RETURN(BZ_DATA_ERROR);
806 GET_UCHAR(BZ_X_ENDHDR_6, uc);
807 if (uc != 0x90) RETURN(BZ_DATA_ERROR);
809 s->storedCombinedCRC = 0;
810 GET_UCHAR(BZ_X_CCRC_1, uc);
811 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
812 GET_UCHAR(BZ_X_CCRC_2, uc);
813 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
814 GET_UCHAR(BZ_X_CCRC_3, uc);
815 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
816 GET_UCHAR(BZ_X_CCRC_4, uc);
817 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
819 s->state = BZ_X_IDLE;
820 RETURN(BZ_STREAM_END);
822 default: AssertH ( False, 4001 );
825 AssertH ( False, 4002 );
827 save_state_and_return:
832 s->save_alphaSize = alphaSize;
833 s->save_nGroups = nGroups;
834 s->save_nSelectors = nSelectors;
836 s->save_groupNo = groupNo;
837 s->save_groupPos = groupPos;
838 s->save_nextSym = nextSym;
839 s->save_nblockMAX = nblockMAX;
840 s->save_nblock = nblock;
849 s->save_gMinlen = gMinlen;
850 s->save_gLimit = gLimit;
851 s->save_gBase = gBase;
852 s->save_gPerm = gPerm;
858 /*-------------------------------------------------------------*/
859 /*--- end decompress.c ---*/
860 /*-------------------------------------------------------------*/