diff options
Diffstat (limited to 'archival')
| -rw-r--r-- | archival/libunarchive/decompress_bunzip2.c | 490 |
1 files changed, 267 insertions, 223 deletions
diff --git a/archival/libunarchive/decompress_bunzip2.c b/archival/libunarchive/decompress_bunzip2.c index b4bcb0b..f00c439 100644 --- a/archival/libunarchive/decompress_bunzip2.c +++ b/archival/libunarchive/decompress_bunzip2.c @@ -10,6 +10,36 @@ LGPL (http://www.gnu.org/copyleft/lgpl.html */ +/* + Size and speed optimizations by Manuel Novoa III (mjn3@codepoet.org). + + More efficient reading of huffman codes, a streamlined read_bunzip() + function, and various other tweaks. In (limited) tests, approximately + 20% faster than bzcat on x86 and about 10% faster on arm. + + Note that about 2/3 of the time is spent in read_unzip() reversing + the Burrows-Wheeler transformation. Much of that time is delay + resulting from cache misses. + + I would ask that anyone benefiting from this work, especially those + using it in commercial products, consider making a donation to my local + non-profit hospice organization in the name of the woman I loved, who + passed away Feb. 12, 2003. + + In memory of Toni W. Hagan + + Hospice of Acadiana, Inc. + 2600 Johnston St., Suite 200 + Lafayette, LA 70503-3240 + + Phone (337) 232-1234 or 1-800-738-2226 + Fax (337) 232-1297 + + http://www.hospiceacadiana.com/ + + Manuel + */ + #include <setjmp.h> #include <stdio.h> #include <stdlib.h> @@ -38,39 +68,31 @@ /* Other housekeeping constants */ #define IOBUF_SIZE 4096 -static char * const bunzip_errors[]={NULL,"Bad file checksum","Not bzip data", - "Unexpected input EOF","Unexpected output EOF","Data error", - "Out of memory","Obsolete (pre 0.9.5) bzip format not supported."}; - /* This is what we know about each huffman coding group */ struct group_data { /* We have an extra slot at the end of limit[] for a sentinal value. */ int limit[MAX_HUFCODE_BITS+1],base[MAX_HUFCODE_BITS],permute[MAX_SYMBOLS]; - char minLen, maxLen; + int minLen, maxLen; }; /* Structure holding all the housekeeping data, including IO buffers and memory that persists between calls to bunzip */ typedef struct { - /* For I/O error handling */ - jmp_buf jmpbuf; - /* Input stream, input buffer, input bit buffer */ - int in_fd,inbufCount,inbufPos; - unsigned char *inbuf; + /* State for interrupting output loop */ + int writeCopies,writePos,writeRunCountdown,writeCount,writeCurrent; + /* I/O tracking data (file handles, buffers, positions, etc.) */ + int in_fd,out_fd,inbufCount,inbufPos /*,outbufPos*/; + unsigned char *inbuf /*,*outbuf*/; unsigned int inbufBitCount, inbufBits; - /* Output buffer */ - char outbuf[IOBUF_SIZE]; - int outbufPos; /* The CRC values stored in the block header and calculated from the data */ - unsigned int crc32Table[256],headerCRC, dataCRC, totalCRC; + unsigned int crc32Table[256],headerCRC, totalCRC, writeCRC; /* Intermediate buffer and its size (in bytes) */ unsigned int *dbuf, dbufSize; - /* State for interrupting output loop */ - int writePos,writeRun,writeCount,writeCurrent; - /* These things are a bit too big to go on the stack */ unsigned char selectors[32768]; /* nSelectors=15 bits */ struct group_data groups[MAX_GROUPS]; /* huffman coding tables */ + /* For I/O error handling */ + jmp_buf jmpbuf; } bunzip_data; /* Return the next nnn bits of input. All reads from the compressed input @@ -106,39 +128,29 @@ static unsigned int get_bits(bunzip_data *bd, char bits_wanted) return bits; } -/* At certain times, it pays to have an optimized inline version of - * get_bits() which gets a single bit. */ -#define GET_A_BIT(bd) \ - ((bd->inbufBitCount > 0) \ - ? ((unsigned int)(((bd)->inbufBits >> --(bd)->inbufBitCount) & 1)) \ - : get_bits((bd), 1)) - - -/* Decompress a block of text to into intermediate buffer */ +/* Unpacks the next block and sets up for the inverse burrows-wheeler step. */ -extern int read_bunzip_data(bunzip_data *bd) +static int get_next_block(bunzip_data *bd) { struct group_data *hufGroup; - int dbufCount,nextSym,dbufSize,origPtr,groupCount,*base,*limit,selector, + int dbufCount,nextSym,dbufSize,groupCount,*base,*limit,selector, i,j,k,t,runPos,symCount,symTotal,nSelectors,byteCount[256]; unsigned char uc, symToByte[256], mtfSymbol[256], *selectors; - unsigned int *dbuf; - - /* Read in header signature (borrowing mtfSymbol for temp space). */ - for(i=0;i<6;i++) mtfSymbol[i]=get_bits(bd,8); - mtfSymbol[6]=0; - /* Read CRC (which is stored big endian). */ - bd->headerCRC=get_bits(bd,32); - /* Is this the last block (with CRC for file)? */ - if(!strcmp(mtfSymbol,"\x17\x72\x45\x38\x50\x90")) - return RETVAL_LAST_BLOCK; - /* If it's not a valid data block, barf. */ - if(strcmp(mtfSymbol,"\x31\x41\x59\x26\x53\x59")) - return RETVAL_NOT_BZIP_DATA; + unsigned int *dbuf,origPtr; dbuf=bd->dbuf; dbufSize=bd->dbufSize; selectors=bd->selectors; + /* Reset longjmp I/O error handling */ + i=setjmp(bd->jmpbuf); + if(i) return i; + /* Read in header signature and CRC, then validate signature. + (last block signature means CRC is for whole file, return now) */ + i = get_bits(bd,24); + j = get_bits(bd,24); + bd->headerCRC=get_bits(bd,32); + if ((i == 0x177245) && (j == 0x385090)) return RETVAL_LAST_BLOCK; + if ((i != 0x314159) || (j != 0x265359)) return RETVAL_NOT_BZIP_DATA; /* We can add support for blockRandomised if anybody complains. There was some code for this in busybox 1.0.0-pre3, but nobody ever noticed that it didn't actually work. */ @@ -150,10 +162,6 @@ extern int read_bunzip_data(bunzip_data *bd) values were present. We make a translation table to convert the symbols back to the corresponding bytes. */ t=get_bits(bd, 16); -#if 0 - /* I don't believe this is necessary. Rob? */ - memset(symToByte,0,256); -#endif symTotal=0; for (i=0;i<16;i++) { if(t&(1<<(15-i))) { @@ -167,7 +175,8 @@ extern int read_bunzip_data(bunzip_data *bd) if (groupCount<2 || groupCount>MAX_GROUPS) return RETVAL_DATA_ERROR; /* nSelectors: Every GROUP_SIZE many symbols we select a new huffman coding group. Read in the group selector list, which is stored as MTF encoded - bit runs. */ + bit runs. (MTF=Move To Front, as each value is used it's moved to the + start of the list.) */ if(!(nSelectors=get_bits(bd, 15))) return RETVAL_DATA_ERROR; for(i=0; i<groupCount; i++) mtfSymbol[i] = i; for(i=0; i<nSelectors; i++) { @@ -175,13 +184,7 @@ extern int read_bunzip_data(bunzip_data *bd) for(j=0;get_bits(bd,1);j++) if (j>=groupCount) return RETVAL_DATA_ERROR; /* Decode MTF to get the next selector */ uc = mtfSymbol[j]; - /* A very small amount of data to move, so memmove is overkill - * and bigger at least in my tests. */ - k = j; - while (k) { - mtfSymbol[k] = mtfSymbol[k-1]; - --k; - } + for(;j;j--) mtfSymbol[j] = mtfSymbol[j-1]; mtfSymbol[0]=selectors[i]=uc; } /* Read the huffman coding tables for each group, which code for symTotal @@ -190,16 +193,30 @@ extern int read_bunzip_data(bunzip_data *bd) for (j=0; j<groupCount; j++) { unsigned char length[MAX_SYMBOLS],temp[MAX_HUFCODE_BITS+1]; int minLen, maxLen, pp; - /* Read lengths */ - t=get_bits(bd, 5) - 1; /* This lets us avoid a test in the loop. */ + /* Read huffman code lengths for each symbol. They're stored in + a way similar to mtf; record a starting value for the first symbol, + and an offset from the previous value for everys symbol after that. + (Subtracting 1 before the loop and then adding it back at the end is + an optimization that makes the test inside the loop simpler: symbol + length 0 becomes negative, so an unsigned inequality catches it.) */ + t=get_bits(bd, 5)-1; for (i = 0; i < symCount; i++) { for(;;) { - if (((unsigned)t) > (MAX_HUFCODE_BITS-1)) return RETVAL_DATA_ERROR; - if(!get_bits(bd, 1)) break; - /* We can avoid an if/else with a little arithmetic. */ - t += (1 - 2*get_bits(bd, 1)); /* 0 -> t++ ; 1 -> t-- */ + if (((unsigned)t) > (MAX_HUFCODE_BITS-1)) + return RETVAL_DATA_ERROR; + /* If first bit is 0, stop. Else second bit indicates whether + to increment or decrement the value. Optimization: grab 2 + bits and unget the second if the first was 0. */ + k = get_bits(bd,2); + if (k < 2) { + bd->inbufBitCount++; + break; + } + /* Add one if second bit 1, else subtract 1. Avoids if/else */ + t+=(((k+1)&2)-1); } - length[i] = t + 1; /* Correct for the initial -1 adjustment. */ + /* Correct for the initial -1, to get the final symbol length */ + length[i]=t+1; } /* Find largest and smallest lengths in this group */ minLen=maxLen=length[0]; @@ -214,11 +231,8 @@ extern int read_bunzip_data(bunzip_data *bd) * value of a huffman symbol of a given length when using permute[]. * * limit[] indicates the largest numerical value a symbol with a given - * number of bits can have. It lets us know when to stop reading. - * - * To use these, keep reading bits until value<=limit[bitcount] or - * you've read over 20 bits (error). Then the decoded symbol - * equals permute[hufcode_value-base[hufcode_bitcount]]. + * number of bits can have. This is how the huffman codes can vary in + * length: each code with a value>limit[length] needs another bit. */ hufGroup=bd->groups+j; hufGroup->minLen = minLen; @@ -228,22 +242,29 @@ extern int read_bunzip_data(bunzip_data *bd) entry. We do this again when using them (during symbol decoding).*/ base=hufGroup->base-1; limit=hufGroup->limit-1; - /* Calculate permute[] */ - pp = 0; - for(i=minLen;i<=maxLen;i++) + /* Calculate permute[]. Concurently, initialize temp[] and limit[]. */ + pp=0; + for(i=minLen;i<=maxLen;i++) { + temp[i]=limit[i]=0; for(t=0;t<symCount;t++) if(length[t]==i) hufGroup->permute[pp++] = t; - /* Count cumulative symbols coded for at each bit length */ - for (i=minLen;i<=maxLen;i++) temp[i]=limit[i]=0; + } + /* Count symbols coded for at each bit length */ for (i=0;i<symCount;i++) temp[length[i]]++; /* Calculate limit[] (the largest symbol-coding value at each bit * length, which is (previous limit<<1)+symbols at this level), and * base[] (number of symbols to ignore at each bit length, which is - * limit-cumulative count of symbols coded for already). */ + * limit minus the cumulative count of symbols coded for already). */ pp=t=0; for (i=minLen; i<maxLen; i++) { pp+=temp[i]; - limit[i]=pp-1; + /* We read the largest possible symbol size and then unget bits + after determining how many we need, and those extra bits could + be set to anything. (They're noise from future symbols.) At + each level we're really only interested in the first few bits, + so here we set all the trailing to-be-ignored bits to 1 so they + don't affect the value>limit[length] comparison. */ + limit[i]= (pp << (maxLen - i)) - 1; pp<<=1; base[i+1]=pp-(t+=temp[i]); } @@ -255,10 +276,12 @@ extern int read_bunzip_data(bunzip_data *bd) block's huffman coded symbols from the file and undo the huffman coding and run length encoding, saving the result into dbuf[dbufCount++]=uc */ - /* Initialize symbol occurrence counters and symbol mtf table */ - memset(byteCount,0,256*sizeof(int)); - for(i=0;i<256;i++) mtfSymbol[i]=(unsigned char)i; - /* Loop through compressed symbols */ + /* Initialize symbol occurrence counters and symbol Move To Front table */ + for(i=0;i<256;i++) { + byteCount[i] = 0; + mtfSymbol[i]=(unsigned char)i; + } + /* Loop through compressed symbols. */ runPos=dbufCount=symCount=selector=0; for(;;) { /* Determine which huffman coding group to use. */ @@ -269,17 +292,41 @@ extern int read_bunzip_data(bunzip_data *bd) base=hufGroup->base-1; limit=hufGroup->limit-1; } - /* Read next huffman-coded symbol */ - i = hufGroup->minLen; - j=get_bits(bd, i); - while (j > limit[i]) { /* The sentinal allows us to avoid testing i. */ - j = (j << 1) | GET_A_BIT(bd); - ++i; - } - /* Huffman decode nextSym (with bounds checking) */ - if ((i > hufGroup->maxLen) || (((unsigned)(j-=base[i])) >= MAX_SYMBOLS)) return RETVAL_DATA_ERROR; + /* Read next huffman-coded symbol. */ + /* Note: It is far cheaper to read maxLen bits and back up than it is + to read minLen bits and then an additional bit at a time, testing + as we go. Because there is a trailing last block (with file CRC), + there is no danger of the overread causing an unexpected EOF for a + valid compressed file. As a further optimization, we do the read + inline (falling back to a call to get_bits if the buffer runs + dry). The following (up to got_huff_bits:) is equivalent to + j=get_bits(bd,hufGroup->maxLen); + */ + while (bd->inbufBitCount<hufGroup->maxLen) { + if(bd->inbufPos==bd->inbufCount) { + j = get_bits(bd,hufGroup->maxLen); + goto got_huff_bits; + } + bd->inbufBits=(bd->inbufBits<<8)|bd->inbuf[bd->inbufPos++]; + bd->inbufBitCount+=8; + }; + bd->inbufBitCount-=hufGroup->maxLen; + j = (bd->inbufBits>>bd->inbufBitCount)&((1<<hufGroup->maxLen)-1); +got_huff_bits: + /* Figure how how many bits are in next symbol and unget extras */ + i=hufGroup->minLen; + while(j>limit[i]) ++i; + bd->inbufBitCount += (hufGroup->maxLen - i); + /* Huffman decode value to get nextSym (with bounds checking) */ + if ((i > hufGroup->maxLen) + || (((unsigned)(j=(j>>(hufGroup->maxLen-i))-base[i])) + >= MAX_SYMBOLS)) + return RETVAL_DATA_ERROR; nextSym = hufGroup->permute[j]; - /* If this is a repeated run, loop collecting data */ + /* We have now decoded the symbol, which indicates either a new literal + byte, or a repeated run of the most recent literal byte. First, + check if nextSym indicates a repeated run, and if so loop collecting + how many times to repeat the last literal. */ if (((unsigned)nextSym) <= SYMBOL_RUNB) { /* RUNA or RUNB */ /* If this is the start of a new run, zero out counter */ if(!runPos) { @@ -311,19 +358,20 @@ extern int read_bunzip_data(bunzip_data *bd) } /* Is this the terminating symbol? */ if(nextSym>symTotal) break; - /* At this point, the symbol we just decoded indicates a new literal - character. Subtract one to get the position in the MTF array - at which this literal is currently to be found. (Note that the - result can't be -1 or 0, because 0 and 1 are RUNA and RUNB. - Another instance of the first symbol in the mtf array, position 0, - would have been handled as part of a run.) */ + /* At this point, nextSym indicates a new literal character. Subtract + one to get the position in the MTF array at which this literal is + currently to be found. (Note that the result can't be -1 or 0, + because 0 and 1 are RUNA and RUNB. But another instance of the + first symbol in the mtf array, position 0, would have been handled + as part of a run above. Therefore 1 unused mtf position minus + 2 non-literal nextSym values equals -1.) */ if(dbufCount>=dbufSize) return RETVAL_DATA_ERROR; i = nextSym - 1; uc = mtfSymbol[i]; - /* Since we typically expect to move only a small number of symbols, - * and are bound by 256 in any case, using memmove here would - * typically be slower due to function call overhead and other - * assorted setup costs. */ + /* Adjust the MTF array. Since we typically expect to move only a + * small number of symbols, and are bound by 256 in any case, using + * memmove here would typically be bigger and slower due to function + * call overhead and other assorted setup costs. */ do { mtfSymbol[i] = mtfSymbol[i-1]; } while (--i); @@ -333,14 +381,12 @@ extern int read_bunzip_data(bunzip_data *bd) byteCount[uc]++; dbuf[dbufCount++] = (unsigned int)uc; } - /* At this point, we've finished reading huffman-coded symbols and - compressed runs from the input stream. There are dbufCount many of - them in dbuf[]. Now undo the Burrows-Wheeler transform on dbuf. + /* At this point, we've read all the huffman-coded symbols (and repeated + runs) for this block from the input stream, and decoded them into the + intermediate buffer. There are dbufCount many decoded bytes in dbuf[]. + Now undo the Burrows-Wheeler transform on dbuf. See http://dogma.net/markn/articles/bwt/bwt.htm */ - - /* Now we know what dbufCount is, do a better sanity check on origPtr. */ - if (((unsigned)origPtr)>=dbufCount) return RETVAL_DATA_ERROR; /* Turn byteCount into cumulative occurrence counts of 0 to n-1. */ j=0; for(i=0;i<256;i++) { @@ -350,144 +396,137 @@ extern int read_bunzip_data(bunzip_data *bd) } /* Figure out what order dbuf would be in if we sorted it. */ for (i=0;i<dbufCount;i++) { - uc = (unsigned char)(dbuf[i] & 0xff); + uc=(unsigned char)(dbuf[i] & 0xff); dbuf[byteCount[uc]] |= (i << 8); byteCount[uc]++; } - /* blockRandomised support would go here. */ - - /* Using i as position, j as previous character, t as current character, - and uc as run count */ - bd->dataCRC = 0xffffffffL; /* Decode first byte by hand to initialize "previous" byte. Note that it doesn't get output, and if the first three characters are identical - it doesn't qualify as a run (hence uc=255, which will either wrap - to 1 or get reset). */ + it doesn't qualify as a run (hence writeRunCountdown=5). */ if(dbufCount) { + if(origPtr>=dbufCount) return RETVAL_DATA_ERROR; bd->writePos=dbuf[origPtr]; bd->writeCurrent=(unsigned char)(bd->writePos&0xff); bd->writePos>>=8; - bd->writeRun=-1; + bd->writeRunCountdown=5; } bd->writeCount=dbufCount; return RETVAL_OK; } -/* Flush output buffer to disk */ -extern void flush_bunzip_outbuf(bunzip_data *bd, int out_fd) -{ - if(bd->outbufPos) { - if(write(out_fd, bd->outbuf, bd->outbufPos) != bd->outbufPos) - longjmp(bd->jmpbuf,RETVAL_UNEXPECTED_OUTPUT_EOF); - bd->outbufPos=0; - } -} - - /* Undo burrows-wheeler transform on intermediate buffer to produce output. - If !len, write up to len bytes of data to buf. Otherwise write to out_fd. - Returns len ? bytes written : RETVAL_OK. Notice all errors negative #'s. */ -extern int write_bunzip_data(bunzip_data *bd, int out_fd, char *outbuf, int len) + If start_bunzip was initialized with out_fd=-1, then up to len bytes of + data are written to outbuf. Return value is number of bytes written or + error (all errors are negative numbers). If out_fd!=-1, outbuf and len + are ignored, data is written to out_fd and return is RETVAL_OK or error. +*/ + +extern int read_bunzip(bunzip_data *bd, char *outbuf, int len) { - unsigned int *dbuf=bd->dbuf; - int count,pos,current, run,copies,outbyte,previous,gotcount=0; + const unsigned int *dbuf; + int pos,current,previous,gotcount; - for(;;) { - /* If last read was short due to end of file, return last block now */ - if(bd->writeCount<0) return bd->writeCount; - /* If we need to refill dbuf, do it. */ - if(!bd->writeCount) { - int i=read_bunzip_data(bd); - if(i) { - if(i==RETVAL_LAST_BLOCK) { - bd->writeCount=i; - return gotcount; - } else return i; + /* If last read was short due to end of file, return last block now */ + if(bd->writeCount<0) return bd->writeCount; + + gotcount = 0; + dbuf=bd->dbuf; + pos=bd->writePos; + current=bd->writeCurrent; + + /* We will always have pending decoded data to write into the output + buffer unless this is the very first call (in which case we haven't + huffman-decoded a block into the intermediate buffer yet). */ + + if (bd->writeCopies) { + /* Inside the loop, writeCopies means extra copies (beyond 1) */ + --bd->writeCopies; + /* Loop outputting bytes */ + for(;;) { + /* If the output buffer is full, snapshot state and return */ + if(gotcount >= len) { + bd->writePos=pos; + bd->writeCurrent=current; + bd->writeCopies++; + return len; } - } - /* Loop generating output */ - count=bd->writeCount; - pos=bd->writePos; - current=bd->writeCurrent; - run=bd->writeRun; - while(count) { - /* If somebody (like busybox tar) wants a certain number of bytes of - data from memory instead of written to a file, humor them */ - if(len && bd->outbufPos>=len) goto dataus_interruptus; - count--; + /* Write next byte into output buffer, updating CRC */ + outbuf[gotcount++] = current; + bd->writeCRC=(((bd->writeCRC)<<8) + ^bd->crc32Table[((bd->writeCRC)>>24)^current]); + /* Loop now if we're outputting multiple copies of this byte */ + if (bd->writeCopies) { + --bd->writeCopies; + continue; + } +decode_next_byte: + if (!bd->writeCount--) break; /* Follow sequence vector to undo Burrows-Wheeler transform */ previous=current; pos=dbuf[pos]; current=pos&0xff; pos>>=8; - /* Whenever we see 3 consecutive copies of the same byte, - the 4th is a repeat count */ - if(run++==3) { - copies=current; - outbyte=previous; - current=-1; + /* After 3 consecutive copies of the same byte, the 4th is a repeat + count. We count down from 4 instead + * of counting up because testing for non-zero is faster */ + if(--bd->writeRunCountdown) { + if(current!=previous) bd->writeRunCountdown=4; } else { - copies=1; - outbyte=current; - } - /* Output bytes to buffer, flushing to file if necessary */ - while(copies--) { - if(bd->outbufPos == IOBUF_SIZE) flush_bunzip_outbuf(bd,out_fd); - bd->outbuf[bd->outbufPos++] = outbyte; - bd->dataCRC = (bd->dataCRC << 8) - ^ bd->crc32Table[(bd->dataCRC >> 24) ^ outbyte]; + /* We have a repeated run, this byte indicates the count */ + bd->writeCopies=current; + current=previous; + bd->writeRunCountdown=5; + /* Sometimes there are just 3 bytes (run length 0) */ + if(!bd->writeCopies) goto decode_next_byte; + /* Subtract the 1 copy we'd output anyway to get extras */ + --bd->writeCopies; } - if(current!=previous) run=0; } /* Decompression of this block completed successfully */ - bd->dataCRC=~(bd->dataCRC); - bd->totalCRC=((bd->totalCRC << 1) | (bd->totalCRC >> 31)) ^ bd->dataCRC; + bd->writeCRC=~bd->writeCRC; + bd->totalCRC=((bd->totalCRC<<1) | (bd->totalCRC>>31)) ^ bd->writeCRC; /* If this block had a CRC error, force file level CRC error. */ - if(bd->dataCRC!=bd->headerCRC) { + if(bd->writeCRC!=bd->headerCRC) { bd->totalCRC=bd->headerCRC+1; return RETVAL_LAST_BLOCK; } -dataus_interruptus: - bd->writeCount=count; - if(len) { - gotcount+=bd->outbufPos; - memcpy(outbuf,bd->outbuf,len); - /* If we got enough data, checkpoint loop state and return */ - if((len-=bd->outbufPos)<1) { - bd->outbufPos-=len; - if(bd->outbufPos) - memmove(bd->outbuf,bd->outbuf+len,bd->outbufPos); - bd->writePos=pos; - bd->writeCurrent=current; - bd->writeRun=run; - return gotcount; - } - } } + + /* Refill the intermediate buffer by huffman-decoding next block of input */ + /* (previous is just a convenient unused temp variable here) */ + previous=get_next_block(bd); + if(previous) { + bd->writeCount=previous; + return (previous!=RETVAL_LAST_BLOCK) ? previous : gotcount; + } + bd->writeCRC=0xffffffffUL; + pos=bd->writePos; + current=bd->writeCurrent; + goto decode_next_byte; } -/* Allocate the structure, read file header. If !len, src_fd contains - filehandle to read from. Else inbuf contains data. */ -extern int start_bunzip(bunzip_data **bdp, int src_fd, char *inbuf, int len) +/* Allocate the structure, read file header. If in_fd==-1, inbuf must contain + a complete bunzip file (len bytes long). If in_fd!=-1, inbuf and len are + ignored, and data is read from file handle into temporary buffer. */ +extern int start_bunzip(bunzip_data **bdp, int in_fd, char *inbuf, int len) { bunzip_data *bd; unsigned int i,j,c; + const unsigned int BZh0=(((unsigned int)'B')<<24)+(((unsigned int)'Z')<<16) + +(((unsigned int)'h')<<8)+(unsigned int)'0'; /* Figure out how much data to allocate */ i=sizeof(bunzip_data); - if(!len) i+=IOBUF_SIZE; + if(in_fd!=-1) i+=IOBUF_SIZE; /* Allocate bunzip_data. Most fields initialize to zero. */ if(!(bd=*bdp=malloc(i))) return RETVAL_OUT_OF_MEMORY; memset(bd,0,sizeof(bunzip_data)); - if(len) { + /* Setup input buffer */ + if(-1==(bd->in_fd=in_fd)) { bd->inbuf=inbuf; bd->inbufCount=len; - bd->in_fd=-1; - } else { - bd->inbuf=(char *)(bd+1); - bd->in_fd=src_fd; - } + } else bd->inbuf=(unsigned char *)(bd+1); /* Init the CRC32 table (big endian) */ for(i=0;i<256;i++) { c=i<<24; @@ -498,55 +537,60 @@ extern int start_bunzip(bunzip_data **bdp, int src_fd, char *inbuf, int len) /* Setup for I/O error handling via longjmp */ i=setjmp(bd->jmpbuf); if(i) return i; - /* Ensure that file starts with "BZh" */ - for(i=0;i<3;i++) if(get_bits(bd,8)!="BZh"[i]) return RETVAL_NOT_BZIP_DATA; - /* Next byte ascii '1'-'9', indicates block size in units of 100k of + + /* Ensure that file starts with "BZh['1'-'9']." */ + i = get_bits(bd,32); + if (((unsigned int)(i-BZh0-1)) >= 9) return RETVAL_NOT_BZIP_DATA; + + /* Fourth byte (ascii '1'-'9'), indicates block size in units of 100k of uncompressed data. Allocate intermediate buffer for block. */ - i=get_bits(bd,8); - if (i<'1' || i>'9') return RETVAL_NOT_BZIP_DATA; - bd->dbufSize=100000*(i-'0'); + bd->dbufSize=100000*(i-BZh0); + if(!(bd->dbuf=malloc(bd->dbufSize * sizeof(int)))) return RETVAL_OUT_OF_MEMORY; return RETVAL_OK; } -extern char *uncompressStream(int src_fd, int dst_fd) +/* Example usage: decompress src_fd to dst_fd. (Stops at end of bzip data, + not end of file.) */ +extern int uncompressStream(int src_fd, int dst_fd) { + char *outbuf; bunzip_data *bd; int i; + if(!(outbuf=malloc(IOBUF_SIZE))) return RETVAL_OUT_OF_MEMORY; if(!(i=start_bunzip(&bd,src_fd,0,0))) { - i=write_bunzip_data(bd,dst_fd,0,0); - if(i==RETVAL_LAST_BLOCK && bd->headerCRC==bd->totalCRC) i=RETVAL_OK; + for(;;) { + if((i=read_bunzip(bd,outbuf,IOBUF_SIZE)) <= 0) break; + if(i!=write(dst_fd,outbuf,i)) { + i=RETVAL_UNEXPECTED_OUTPUT_EOF; + break; + } + } } - flush_bunzip_outbuf(bd,dst_fd); + /* Check CRC and release memory */ + if(i==RETVAL_LAST_BLOCK && bd->headerCRC==bd->totalCRC) i=RETVAL_OK; if(bd->dbuf) free(bd->dbuf); free(bd); - return bunzip_errors[-i]; + free(outbuf); + return i; } -/* This new version is not yet properly integrated with tar */ -extern ssize_t read_bz2(int fd, void *buf, size_t count) -{ -#warning FIXME - return(0); -} +#ifdef TESTING -extern void BZ2_bzReadOpen(int fd, void *unused, int nUnused) -{ -#warning FIXME - return; -} -extern void BZ2_bzReadClose(void) -{ -#warning FIXME -} +static char * const bunzip_errors[]={NULL,"Bad file checksum","Not bzip data", + "Unexpected input EOF","Unexpected output EOF","Data error", + "Out of memory","Obsolete (pre 0.9.5) bzip format not supported."}; -#if 0 /* Dumb little test thing, decompress stdin to stdout */ int main(int argc, char *argv[]) { - char *c=uncompressStream(0,1); - fprintf(stderr,"\n%s\n", c ? c : "Completed OK"); + int i=uncompressStream(0,1); + char c; + + if(i) fprintf(stderr,"%s\n", bunzip_errors[-i]); + else if(read(0,&c,1)) fprintf(stderr,"Trailing garbage ignored\n"); + return -i; } #endif |