1 /* vi: set sw=4 ts=4: */
2 /* Small bzip2 deflate implementation, by Rob Landley (rob@landley.net).
4 Based on bzip2 decompression code by Julian R Seward (jseward@acm.org),
5 which also acknowledges contributions by Mike Burrows, David Wheeler,
6 Peter Fenwick, Alistair Moffat, Radford Neal, Ian H. Witten,
7 Robert Sedgewick, and Jon L. Bentley.
9 This code is licensed under the LGPLv2:
10 LGPL (http://www.gnu.org/copyleft/lgpl.html
14 Size and speed optimizations by Manuel Novoa III (mjn3@codepoet.org).
16 More efficient reading of huffman codes, a streamlined read_bunzip()
17 function, and various other tweaks. In (limited) tests, approximately
18 20% faster than bzcat on x86 and about 10% faster on arm.
20 Note that about 2/3 of the time is spent in read_unzip() reversing
21 the Burrows-Wheeler transformation. Much of that time is delay
22 resulting from cache misses.
24 I would ask that anyone benefiting from this work, especially those
25 using it in commercial products, consider making a donation to my local
26 non-profit hospice organization in the name of the woman I loved, who
27 passed away Feb. 12, 2003.
29 In memory of Toni W. Hagan
31 Hospice of Acadiana, Inc.
32 2600 Johnston St., Suite 200
33 Lafayette, LA 70503-3240
35 Phone (337) 232-1234 or 1-800-738-2226
38 http://www.hospiceacadiana.com/
50 /* Constants for huffman coding */
52 #define GROUP_SIZE 50 /* 64 would have been more efficient */
53 #define MAX_HUFCODE_BITS 20 /* Longest huffman code allowed */
54 #define MAX_SYMBOLS 258 /* 256 literals + RUNA + RUNB */
58 /* Status return values */
60 #define RETVAL_LAST_BLOCK (-1)
61 #define RETVAL_NOT_BZIP_DATA (-2)
62 #define RETVAL_UNEXPECTED_INPUT_EOF (-3)
63 #define RETVAL_UNEXPECTED_OUTPUT_EOF (-4)
64 #define RETVAL_DATA_ERROR (-5)
65 #define RETVAL_OUT_OF_MEMORY (-6)
66 #define RETVAL_OBSOLETE_INPUT (-7)
68 /* Other housekeeping constants */
69 #define IOBUF_SIZE 4096
71 /* This is what we know about each huffman coding group */
73 /* We have an extra slot at the end of limit[] for a sentinal value. */
74 int limit[MAX_HUFCODE_BITS+1],base[MAX_HUFCODE_BITS],permute[MAX_SYMBOLS];
78 /* Structure holding all the housekeeping data, including IO buffers and
79 memory that persists between calls to bunzip */
81 /* State for interrupting output loop */
82 int writeCopies,writePos,writeRunCountdown,writeCount,writeCurrent;
83 /* I/O tracking data (file handles, buffers, positions, etc.) */
84 int in_fd,out_fd,inbufCount,inbufPos /*,outbufPos*/;
85 unsigned char *inbuf /*,*outbuf*/;
86 unsigned int inbufBitCount, inbufBits;
87 /* The CRC values stored in the block header and calculated from the data */
88 unsigned int crc32Table[256],headerCRC, totalCRC, writeCRC;
89 /* Intermediate buffer and its size (in bytes) */
90 unsigned int *dbuf, dbufSize;
91 /* These things are a bit too big to go on the stack */
92 unsigned char selectors[32768]; /* nSelectors=15 bits */
93 struct group_data groups[MAX_GROUPS]; /* huffman coding tables */
94 /* For I/O error handling */
98 /* Return the next nnn bits of input. All reads from the compressed input
99 are done through this function. All reads are big endian */
100 static unsigned int get_bits(bunzip_data *bd, char bits_wanted)
104 /* If we need to get more data from the byte buffer, do so. (Loop getting
105 one byte at a time to enforce endianness and avoid unaligned access.) */
106 while (bd->inbufBitCount<bits_wanted) {
107 /* If we need to read more data from file into byte buffer, do so */
108 if(bd->inbufPos==bd->inbufCount) {
109 if((bd->inbufCount = read(bd->in_fd, bd->inbuf, IOBUF_SIZE)) <= 0)
110 longjmp(bd->jmpbuf,RETVAL_UNEXPECTED_INPUT_EOF);
113 /* Avoid 32-bit overflow (dump bit buffer to top of output) */
114 if(bd->inbufBitCount>=24) {
115 bits=bd->inbufBits&((1<<bd->inbufBitCount)-1);
116 bits_wanted-=bd->inbufBitCount;
120 /* Grab next 8 bits of input from buffer. */
121 bd->inbufBits=(bd->inbufBits<<8)|bd->inbuf[bd->inbufPos++];
122 bd->inbufBitCount+=8;
124 /* Calculate result */
125 bd->inbufBitCount-=bits_wanted;
126 bits|=(bd->inbufBits>>bd->inbufBitCount)&((1<<bits_wanted)-1);
131 /* Unpacks the next block and sets up for the inverse burrows-wheeler step. */
133 static int get_next_block(bunzip_data *bd)
135 struct group_data *hufGroup;
136 int dbufCount,nextSym,dbufSize,groupCount,*base,*limit,selector,
137 i,j,k,t,runPos,symCount,symTotal,nSelectors,byteCount[256];
138 unsigned char uc, symToByte[256], mtfSymbol[256], *selectors;
139 unsigned int *dbuf,origPtr;
142 dbufSize=bd->dbufSize;
143 selectors=bd->selectors;
144 /* Reset longjmp I/O error handling */
145 i=setjmp(bd->jmpbuf);
147 /* Read in header signature and CRC, then validate signature.
148 (last block signature means CRC is for whole file, return now) */
151 bd->headerCRC=get_bits(bd,32);
152 if ((i == 0x177245) && (j == 0x385090)) return RETVAL_LAST_BLOCK;
153 if ((i != 0x314159) || (j != 0x265359)) return RETVAL_NOT_BZIP_DATA;
154 /* We can add support for blockRandomised if anybody complains. There was
155 some code for this in busybox 1.0.0-pre3, but nobody ever noticed that
156 it didn't actually work. */
157 if(get_bits(bd,1)) return RETVAL_OBSOLETE_INPUT;
158 if((origPtr=get_bits(bd,24)) > dbufSize) return RETVAL_DATA_ERROR;
159 /* mapping table: if some byte values are never used (encoding things
160 like ascii text), the compression code removes the gaps to have fewer
161 symbols to deal with, and writes a sparse bitfield indicating which
162 values were present. We make a translation table to convert the symbols
163 back to the corresponding bytes. */
170 if(k&(1<<(15-j))) symToByte[symTotal++]=(16*i)+j;
173 /* How many different huffman coding groups does this block use? */
174 groupCount=get_bits(bd,3);
175 if (groupCount<2 || groupCount>MAX_GROUPS) return RETVAL_DATA_ERROR;
176 /* nSelectors: Every GROUP_SIZE many symbols we select a new huffman coding
177 group. Read in the group selector list, which is stored as MTF encoded
178 bit runs. (MTF=Move To Front, as each value is used it's moved to the
179 start of the list.) */
180 if(!(nSelectors=get_bits(bd, 15))) return RETVAL_DATA_ERROR;
181 for(i=0; i<groupCount; i++) mtfSymbol[i] = i;
182 for(i=0; i<nSelectors; i++) {
184 for(j=0;get_bits(bd,1);j++) if (j>=groupCount) return RETVAL_DATA_ERROR;
185 /* Decode MTF to get the next selector */
187 for(;j;j--) mtfSymbol[j] = mtfSymbol[j-1];
188 mtfSymbol[0]=selectors[i]=uc;
190 /* Read the huffman coding tables for each group, which code for symTotal
191 literal symbols, plus two run symbols (RUNA, RUNB) */
193 for (j=0; j<groupCount; j++) {
194 unsigned char length[MAX_SYMBOLS],temp[MAX_HUFCODE_BITS+1];
195 int minLen, maxLen, pp;
196 /* Read huffman code lengths for each symbol. They're stored in
197 a way similar to mtf; record a starting value for the first symbol,
198 and an offset from the previous value for everys symbol after that.
199 (Subtracting 1 before the loop and then adding it back at the end is
200 an optimization that makes the test inside the loop simpler: symbol
201 length 0 becomes negative, so an unsigned inequality catches it.) */
203 for (i = 0; i < symCount; i++) {
205 if (((unsigned)t) > (MAX_HUFCODE_BITS-1))
206 return RETVAL_DATA_ERROR;
207 /* If first bit is 0, stop. Else second bit indicates whether
208 to increment or decrement the value. Optimization: grab 2
209 bits and unget the second if the first was 0. */
215 /* Add one if second bit 1, else subtract 1. Avoids if/else */
218 /* Correct for the initial -1, to get the final symbol length */
221 /* Find largest and smallest lengths in this group */
222 minLen=maxLen=length[0];
223 for(i = 1; i < symCount; i++) {
224 if(length[i] > maxLen) maxLen = length[i];
225 else if(length[i] < minLen) minLen = length[i];
227 /* Calculate permute[], base[], and limit[] tables from length[].
229 * permute[] is the lookup table for converting huffman coded symbols
230 * into decoded symbols. base[] is the amount to subtract from the
231 * value of a huffman symbol of a given length when using permute[].
233 * limit[] indicates the largest numerical value a symbol with a given
234 * number of bits can have. This is how the huffman codes can vary in
235 * length: each code with a value>limit[length] needs another bit.
237 hufGroup=bd->groups+j;
238 hufGroup->minLen = minLen;
239 hufGroup->maxLen = maxLen;
240 /* Note that minLen can't be smaller than 1, so we adjust the base
241 and limit array pointers so we're not always wasting the first
242 entry. We do this again when using them (during symbol decoding).*/
243 base=hufGroup->base-1;
244 limit=hufGroup->limit-1;
245 /* Calculate permute[]. Concurently, initialize temp[] and limit[]. */
247 for(i=minLen;i<=maxLen;i++) {
249 for(t=0;t<symCount;t++)
250 if(length[t]==i) hufGroup->permute[pp++] = t;
252 /* Count symbols coded for at each bit length */
253 for (i=0;i<symCount;i++) temp[length[i]]++;
254 /* Calculate limit[] (the largest symbol-coding value at each bit
255 * length, which is (previous limit<<1)+symbols at this level), and
256 * base[] (number of symbols to ignore at each bit length, which is
257 * limit minus the cumulative count of symbols coded for already). */
259 for (i=minLen; i<maxLen; i++) {
261 /* We read the largest possible symbol size and then unget bits
262 after determining how many we need, and those extra bits could
263 be set to anything. (They're noise from future symbols.) At
264 each level we're really only interested in the first few bits,
265 so here we set all the trailing to-be-ignored bits to 1 so they
266 don't affect the value>limit[length] comparison. */
267 limit[i]= (pp << (maxLen - i)) - 1;
269 base[i+1]=pp-(t+=temp[i]);
271 limit[maxLen+1] = INT_MAX; /* Sentinal value for reading next sym. */
272 limit[maxLen]=pp+temp[maxLen]-1;
275 /* We've finished reading and digesting the block header. Now read this
276 block's huffman coded symbols from the file and undo the huffman coding
277 and run length encoding, saving the result into dbuf[dbufCount++]=uc */
279 /* Initialize symbol occurrence counters and symbol Move To Front table */
282 mtfSymbol[i]=(unsigned char)i;
284 /* Loop through compressed symbols. */
285 runPos=dbufCount=symCount=selector=0;
287 /* Determine which huffman coding group to use. */
289 symCount=GROUP_SIZE-1;
290 if(selector>=nSelectors) return RETVAL_DATA_ERROR;
291 hufGroup=bd->groups+selectors[selector++];
292 base=hufGroup->base-1;
293 limit=hufGroup->limit-1;
295 /* Read next huffman-coded symbol. */
296 /* Note: It is far cheaper to read maxLen bits and back up than it is
297 to read minLen bits and then an additional bit at a time, testing
298 as we go. Because there is a trailing last block (with file CRC),
299 there is no danger of the overread causing an unexpected EOF for a
300 valid compressed file. As a further optimization, we do the read
301 inline (falling back to a call to get_bits if the buffer runs
302 dry). The following (up to got_huff_bits:) is equivalent to
303 j=get_bits(bd,hufGroup->maxLen);
305 while (bd->inbufBitCount<hufGroup->maxLen) {
306 if(bd->inbufPos==bd->inbufCount) {
307 j = get_bits(bd,hufGroup->maxLen);
310 bd->inbufBits=(bd->inbufBits<<8)|bd->inbuf[bd->inbufPos++];
311 bd->inbufBitCount+=8;
313 bd->inbufBitCount-=hufGroup->maxLen;
314 j = (bd->inbufBits>>bd->inbufBitCount)&((1<<hufGroup->maxLen)-1);
316 /* Figure how how many bits are in next symbol and unget extras */
318 while(j>limit[i]) ++i;
319 bd->inbufBitCount += (hufGroup->maxLen - i);
320 /* Huffman decode value to get nextSym (with bounds checking) */
321 if ((i > hufGroup->maxLen)
322 || (((unsigned)(j=(j>>(hufGroup->maxLen-i))-base[i]))
324 return RETVAL_DATA_ERROR;
325 nextSym = hufGroup->permute[j];
326 /* We have now decoded the symbol, which indicates either a new literal
327 byte, or a repeated run of the most recent literal byte. First,
328 check if nextSym indicates a repeated run, and if so loop collecting
329 how many times to repeat the last literal. */
330 if (((unsigned)nextSym) <= SYMBOL_RUNB) { /* RUNA or RUNB */
331 /* If this is the start of a new run, zero out counter */
336 /* Neat trick that saves 1 symbol: instead of or-ing 0 or 1 at
337 each bit position, add 1 or 2 instead. For example,
338 1011 is 1<<0 + 1<<1 + 2<<2. 1010 is 2<<0 + 2<<1 + 1<<2.
339 You can make any bit pattern that way using 1 less symbol than
340 the basic or 0/1 method (except all bits 0, which would use no
341 symbols, but a run of length 0 doesn't mean anything in this
342 context). Thus space is saved. */
343 t += (runPos << nextSym); /* +runPos if RUNA; +2*runPos if RUNB */
347 /* When we hit the first non-run symbol after a run, we now know
348 how many times to repeat the last literal, so append that many
349 copies to our buffer of decoded symbols (dbuf) now. (The last
350 literal used is the one at the head of the mtfSymbol array.) */
353 if(dbufCount+t>=dbufSize) return RETVAL_DATA_ERROR;
355 uc = symToByte[mtfSymbol[0]];
357 while(t--) dbuf[dbufCount++]=uc;
359 /* Is this the terminating symbol? */
360 if(nextSym>symTotal) break;
361 /* At this point, nextSym indicates a new literal character. Subtract
362 one to get the position in the MTF array at which this literal is
363 currently to be found. (Note that the result can't be -1 or 0,
364 because 0 and 1 are RUNA and RUNB. But another instance of the
365 first symbol in the mtf array, position 0, would have been handled
366 as part of a run above. Therefore 1 unused mtf position minus
367 2 non-literal nextSym values equals -1.) */
368 if(dbufCount>=dbufSize) return RETVAL_DATA_ERROR;
371 /* Adjust the MTF array. Since we typically expect to move only a
372 * small number of symbols, and are bound by 256 in any case, using
373 * memmove here would typically be bigger and slower due to function
374 * call overhead and other assorted setup costs. */
376 mtfSymbol[i] = mtfSymbol[i-1];
380 /* We have our literal byte. Save it into dbuf. */
382 dbuf[dbufCount++] = (unsigned int)uc;
384 /* At this point, we've read all the huffman-coded symbols (and repeated
385 runs) for this block from the input stream, and decoded them into the
386 intermediate buffer. There are dbufCount many decoded bytes in dbuf[].
387 Now undo the Burrows-Wheeler transform on dbuf.
388 See http://dogma.net/markn/articles/bwt/bwt.htm
390 /* Turn byteCount into cumulative occurrence counts of 0 to n-1. */
397 /* Figure out what order dbuf would be in if we sorted it. */
398 for (i=0;i<dbufCount;i++) {
399 uc=(unsigned char)(dbuf[i] & 0xff);
400 dbuf[byteCount[uc]] |= (i << 8);
403 /* Decode first byte by hand to initialize "previous" byte. Note that it
404 doesn't get output, and if the first three characters are identical
405 it doesn't qualify as a run (hence writeRunCountdown=5). */
407 if(origPtr>=dbufCount) return RETVAL_DATA_ERROR;
408 bd->writePos=dbuf[origPtr];
409 bd->writeCurrent=(unsigned char)(bd->writePos&0xff);
411 bd->writeRunCountdown=5;
413 bd->writeCount=dbufCount;
418 /* Undo burrows-wheeler transform on intermediate buffer to produce output.
419 If start_bunzip was initialized with out_fd=-1, then up to len bytes of
420 data are written to outbuf. Return value is number of bytes written or
421 error (all errors are negative numbers). If out_fd!=-1, outbuf and len
422 are ignored, data is written to out_fd and return is RETVAL_OK or error.
425 extern int read_bunzip(bunzip_data *bd, char *outbuf, int len)
427 const unsigned int *dbuf;
428 int pos,current,previous,gotcount;
430 /* If last read was short due to end of file, return last block now */
431 if(bd->writeCount<0) return bd->writeCount;
436 current=bd->writeCurrent;
438 /* We will always have pending decoded data to write into the output
439 buffer unless this is the very first call (in which case we haven't
440 huffman-decoded a block into the intermediate buffer yet). */
442 if (bd->writeCopies) {
443 /* Inside the loop, writeCopies means extra copies (beyond 1) */
445 /* Loop outputting bytes */
447 /* If the output buffer is full, snapshot state and return */
448 if(gotcount >= len) {
450 bd->writeCurrent=current;
454 /* Write next byte into output buffer, updating CRC */
455 outbuf[gotcount++] = current;
456 bd->writeCRC=(((bd->writeCRC)<<8)
457 ^bd->crc32Table[((bd->writeCRC)>>24)^current]);
458 /* Loop now if we're outputting multiple copies of this byte */
459 if (bd->writeCopies) {
464 if (!bd->writeCount--) break;
465 /* Follow sequence vector to undo Burrows-Wheeler transform */
470 /* After 3 consecutive copies of the same byte, the 4th is a repeat
471 count. We count down from 4 instead
472 * of counting up because testing for non-zero is faster */
473 if(--bd->writeRunCountdown) {
474 if(current!=previous) bd->writeRunCountdown=4;
476 /* We have a repeated run, this byte indicates the count */
477 bd->writeCopies=current;
479 bd->writeRunCountdown=5;
480 /* Sometimes there are just 3 bytes (run length 0) */
481 if(!bd->writeCopies) goto decode_next_byte;
482 /* Subtract the 1 copy we'd output anyway to get extras */
486 /* Decompression of this block completed successfully */
487 bd->writeCRC=~bd->writeCRC;
488 bd->totalCRC=((bd->totalCRC<<1) | (bd->totalCRC>>31)) ^ bd->writeCRC;
489 /* If this block had a CRC error, force file level CRC error. */
490 if(bd->writeCRC!=bd->headerCRC) {
491 bd->totalCRC=bd->headerCRC+1;
492 return RETVAL_LAST_BLOCK;
496 /* Refill the intermediate buffer by huffman-decoding next block of input */
497 /* (previous is just a convenient unused temp variable here) */
498 previous=get_next_block(bd);
500 bd->writeCount=previous;
501 return (previous!=RETVAL_LAST_BLOCK) ? previous : gotcount;
503 bd->writeCRC=0xffffffffUL;
505 current=bd->writeCurrent;
506 goto decode_next_byte;
509 /* Allocate the structure, read file header. If in_fd==-1, inbuf must contain
510 a complete bunzip file (len bytes long). If in_fd!=-1, inbuf and len are
511 ignored, and data is read from file handle into temporary buffer. */
512 extern int start_bunzip(bunzip_data **bdp, int in_fd, char *inbuf, int len)
516 const unsigned int BZh0=(((unsigned int)'B')<<24)+(((unsigned int)'Z')<<16)
517 +(((unsigned int)'h')<<8)+(unsigned int)'0';
519 /* Figure out how much data to allocate */
520 i=sizeof(bunzip_data);
521 if(in_fd!=-1) i+=IOBUF_SIZE;
522 /* Allocate bunzip_data. Most fields initialize to zero. */
523 if(!(bd=*bdp=malloc(i))) return RETVAL_OUT_OF_MEMORY;
524 memset(bd,0,sizeof(bunzip_data));
525 /* Setup input buffer */
526 if(-1==(bd->in_fd=in_fd)) {
529 } else bd->inbuf=(unsigned char *)(bd+1);
530 /* Init the CRC32 table (big endian) */
534 c=c&0x80000000 ? (c<<1)^0x04c11db7 : (c<<1);
537 /* Setup for I/O error handling via longjmp */
538 i=setjmp(bd->jmpbuf);
541 /* Ensure that file starts with "BZh['1'-'9']." */
543 if (((unsigned int)(i-BZh0-1)) >= 9) return RETVAL_NOT_BZIP_DATA;
545 /* Fourth byte (ascii '1'-'9'), indicates block size in units of 100k of
546 uncompressed data. Allocate intermediate buffer for block. */
547 bd->dbufSize=100000*(i-BZh0);
549 if(!(bd->dbuf=malloc(bd->dbufSize * sizeof(int))))
550 return RETVAL_OUT_OF_MEMORY;
554 /* Example usage: decompress src_fd to dst_fd. (Stops at end of bzip data,
556 extern int uncompressStream(int src_fd, int dst_fd)
562 if(!(outbuf=malloc(IOBUF_SIZE))) return RETVAL_OUT_OF_MEMORY;
563 if(!(i=start_bunzip(&bd,src_fd,0,0))) {
565 if((i=read_bunzip(bd,outbuf,IOBUF_SIZE)) <= 0) break;
566 if(i!=write(dst_fd,outbuf,i)) {
567 i=RETVAL_UNEXPECTED_OUTPUT_EOF;
572 /* Check CRC and release memory */
573 if(i==RETVAL_LAST_BLOCK && bd->headerCRC==bd->totalCRC) i=RETVAL_OK;
574 if(bd->dbuf) free(bd->dbuf);
582 static char * const bunzip_errors[]={NULL,"Bad file checksum","Not bzip data",
583 "Unexpected input EOF","Unexpected output EOF","Data error",
584 "Out of memory","Obsolete (pre 0.9.5) bzip format not supported."};
586 /* Dumb little test thing, decompress stdin to stdout */
587 int main(int argc, char *argv[])
589 int i=uncompressStream(0,1);
592 if(i) fprintf(stderr,"%s\n", bunzip_errors[-i]);
593 else if(read(0,&c,1)) fprintf(stderr,"Trailing garbage ignored\n");