diff options
Diffstat (limited to 'toys')
| -rw-r--r-- | toys/other/bzcat.c | 626 |
1 files changed, 625 insertions, 1 deletions
diff --git a/toys/other/bzcat.c b/toys/other/bzcat.c index 8266484c..642590d1 100644 --- a/toys/other/bzcat.c +++ b/toys/other/bzcat.c @@ -1,6 +1,15 @@ /* bzcat.c - decompress stdin to stdout using bunzip2. * - * Copyright 2007 Rob Landley <rob@landley.net> + * Copyright 2003, 2007 Rob Landley <rob@landley.net> + * + * Based on a close reading (but not the actual code) of the original bzip2 + * decompression code by Julian R Seward (jseward@acm.org), which also + * acknowledges contributions by Mike Burrows, David Wheeler, Peter Fenwick, + * Alistair Moffat, Radford Neal, Ian H. Witten, Robert Sedgewick, and + * Jon L. Bentley. + * + * No standard. + USE_BZCAT(NEWTOY(bzcat, NULL, TOYFLAG_USR|TOYFLAG_BIN)) @@ -15,6 +24,621 @@ config BZCAT #include "toys.h" +#define THREADS 1 + +// Constants for huffman coding +#define MAX_GROUPS 6 +#define GROUP_SIZE 50 /* 64 would have been more efficient */ +#define MAX_HUFCODE_BITS 20 /* Longest huffman code allowed */ +#define MAX_SYMBOLS 258 /* 256 literals + RUNA + RUNB */ +#define SYMBOL_RUNA 0 +#define SYMBOL_RUNB 1 + +// Other housekeeping constants +#define IOBUF_SIZE 4096 + +// Status return values +#define RETVAL_LAST_BLOCK (-100) +#define RETVAL_NOT_BZIP_DATA (-1) +#define RETVAL_DATA_ERROR (-2) +#define RETVAL_OBSOLETE_INPUT (-3) + +// This is what we know about each huffman coding group +struct group_data { + int limit[MAX_HUFCODE_BITS+1], base[MAX_HUFCODE_BITS], permute[MAX_SYMBOLS]; + char minLen, maxLen; +}; + +// Data for burrows wheeler transform + +struct bwdata { + unsigned int origPtr; + int byteCount[256]; + // State saved when interrupting output + int writePos, writeRun, writeCount, writeCurrent; + unsigned int dataCRC, headerCRC; + unsigned int *dbuf; +}; + +// Structure holding all the housekeeping data, including IO buffers and +// memory that persists between calls to bunzip +struct bunzip_data { + // Input stream, input buffer, input bit buffer + int in_fd, inbufCount, inbufPos; + char *inbuf; + unsigned int inbufBitCount, inbufBits; + + // Output buffer + char outbuf[IOBUF_SIZE]; + int outbufPos; + + unsigned int totalCRC; + + // First pass decompression data (Huffman and MTF decoding) + char selectors[32768]; // nSelectors=15 bits + struct group_data groups[MAX_GROUPS]; // huffman coding tables + int symTotal, groupCount, nSelectors; + unsigned char symToByte[256], mtfSymbol[256]; + + // The CRC values stored in the block header and calculated from the data + unsigned int crc32Table[256]; + + // Second pass decompression data (burrows-wheeler transform) + unsigned int dbufSize; + struct bwdata bwdata[THREADS]; +}; + +// Return the next nnn bits of input. All reads from the compressed input +// are done through this function. All reads are big endian. +static unsigned int get_bits(struct bunzip_data *bd, char bits_wanted) +{ + unsigned int bits = 0; + + // If we need to get more data from the byte buffer, do so. (Loop getting + // one byte at a time to enforce endianness and avoid unaligned access.) + while (bd->inbufBitCount < bits_wanted) { + + // If we need to read more data from file into byte buffer, do so + if (bd->inbufPos == bd->inbufCount) { + if (0 >= (bd->inbufCount = read(bd->in_fd, bd->inbuf, IOBUF_SIZE))) + error_exit("input EOF"); + bd->inbufPos = 0; + } + + // Avoid 32-bit overflow (dump bit buffer to top of output) + if (bd->inbufBitCount>=24) { + bits = bd->inbufBits&((1<<bd->inbufBitCount)-1); + bits_wanted -= bd->inbufBitCount; + bits <<= bits_wanted; + bd->inbufBitCount = 0; + } + + // Grab next 8 bits of input from buffer. + bd->inbufBits = (bd->inbufBits<<8) | bd->inbuf[bd->inbufPos++]; + bd->inbufBitCount += 8; + } + + // Calculate result + bd->inbufBitCount -= bits_wanted; + bits |= (bd->inbufBits>>bd->inbufBitCount) & ((1<<bits_wanted)-1); + + return bits; +} + +/* Read block header at start of a new compressed data block. Consists of: + * + * 48 bits : Block signature, either pi (data block) or e (EOF block). + * 32 bits : bw->headerCRC + * 1 bit : obsolete feature flag. + * 24 bits : origPtr (Burrows-wheeler unwind index, only 20 bits ever used) + * 16 bits : Mapping table index. + *[16 bits]: symToByte[symTotal] (Mapping table. For each bit set in mapping + * table index above, read another 16 bits of mapping table data. + * If correspondig bit is unset, all bits in that mapping table + * section are 0.) + * 3 bits : groupCount (how many huffman tables used to encode, anywhere + * from 2 to MAX_GROUPS) + * variable: hufGroup[groupCount] (MTF encoded huffman table data.) + */ + +static int read_block_header(struct bunzip_data *bd, struct bwdata *bw) +{ + struct group_data *hufGroup; + int hh, ii, jj, kk, symCount, *base, *limit; + unsigned char uc; + + // Read in header signature and CRC (which is stored big endian) + ii = get_bits(bd, 24); + jj = get_bits(bd, 24); + bw->headerCRC = get_bits(bd,32); + + // Is this the EOF block with CRC for whole file? (Constant is "e") + if (ii==0x177245 && jj==0x385090) return RETVAL_LAST_BLOCK; + + // Is this a valid data block? (Constant is "pi".) + if (ii!=0x314159 || jj!=0x265359) return RETVAL_NOT_BZIP_DATA; + + // We can add support for blockRandomised if anybody complains. + if (get_bits(bd,1)) return RETVAL_OBSOLETE_INPUT; + if ((bw->origPtr = get_bits(bd,24)) > bd->dbufSize) return RETVAL_DATA_ERROR; + + // mapping table: if some byte values are never used (encoding things + // like ascii text), the compression code removes the gaps to have fewer + // symbols to deal with, and writes a sparse bitfield indicating which + // values were present. We make a translation table to convert the symbols + // back to the corresponding bytes. + hh = get_bits(bd, 16); + bd->symTotal = 0; + for (ii=0; ii<16; ii++) { + if (hh & (1 << (15 - ii))) { + kk = get_bits(bd, 16); + for (jj=0; jj<16; jj++) + if (kk & (1 << (15 - jj))) + bd->symToByte[bd->symTotal++] = (16 * ii) + jj; + } + } + + // How many different huffman coding groups does this block use? + bd->groupCount = get_bits(bd,3); + if (bd->groupCount<2 || bd->groupCount>MAX_GROUPS) return RETVAL_DATA_ERROR; + + // nSelectors: Every GROUP_SIZE many symbols we switch huffman coding + // tables. Each group has a selector, which is an index into the huffman + // coding table arrays. + // + // Read in the group selector array, which is stored as MTF encoded + // bit runs. (MTF = Move To Front. Every time a symbol occurs it's moved + // to the front of the table, so it has a shorter encoding next time.) + if (!(bd->nSelectors = get_bits(bd, 15))) return RETVAL_DATA_ERROR; + for (ii=0; ii<bd->groupCount; ii++) bd->mtfSymbol[ii] = ii; + for (ii=0; ii<bd->nSelectors; ii++) { + + // Get next value + for(jj=0;get_bits(bd,1);jj++) + if (jj>=bd->groupCount) return RETVAL_DATA_ERROR; + + // Decode MTF to get the next selector, and move it to the front. + uc = bd->mtfSymbol[jj]; + memmove(bd->mtfSymbol+1, bd->mtfSymbol, jj); + bd->mtfSymbol[0] = bd->selectors[ii] = uc; + } + + // Read the huffman coding tables for each group, which code for symTotal + // literal symbols, plus two run symbols (RUNA, RUNB) + symCount = bd->symTotal+2; + for (jj=0; jj<bd->groupCount; jj++) { + unsigned char length[MAX_SYMBOLS]; + unsigned temp[MAX_HUFCODE_BITS+1]; + int minLen, maxLen, pp; + + // Read lengths + hh = get_bits(bd, 5); + for (ii = 0; ii < symCount; ii++) { + for(;;) { + // !hh || hh > MAX_HUFCODE_BITS in one test. + if (MAX_HUFCODE_BITS-1 < (unsigned)hh-1) return RETVAL_DATA_ERROR; + // Grab 2 bits instead of 1 (slightly smaller/faster). Stop if + // first bit is 0, otherwise second bit says whether to + // increment or decrement. + kk = get_bits(bd, 2); + if (kk & 2) hh += 1 - ((kk&1)<<1); + else { + bd->inbufBitCount++; + break; + } + } + length[ii] = hh; + } + + // Find largest and smallest lengths in this group + minLen = maxLen = length[0]; + for (ii = 1; ii < symCount; ii++) { + if(length[ii] > maxLen) maxLen = length[ii]; + else if(length[ii] < minLen) minLen = length[ii]; + } + + /* Calculate permute[], base[], and limit[] tables from length[]. + * + * permute[] is the lookup table for converting huffman coded symbols + * into decoded symbols. It contains symbol values sorted by length. + * + * base[] is the amount to subtract from the 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]]. + */ + hufGroup = bd->groups+jj; + hufGroup->minLen = minLen; + hufGroup->maxLen = maxLen; + + // Note that minLen can't be smaller than 1, so we adjust the base + // and limit array pointers so we're not always wasting the first + // entry. We do this again when using them (during symbol decoding). + base = hufGroup->base-1; + limit = hufGroup->limit-1; + + // zero temp[] and limit[], and calculate permute[] + pp = 0; + for (ii = minLen; ii <= maxLen; ii++) { + temp[ii] = limit[ii] = 0; + for (hh = 0; hh < symCount; hh++) + if (length[hh] == ii) hufGroup->permute[pp++] = hh; + } + + // Count symbols coded for at each bit length + for (ii = 0; ii < symCount; ii++) temp[length[ii]]++; + + /* 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 minus the cumulative count of symbols coded for already). */ + pp = hh = 0; + for (ii = minLen; ii < maxLen; ii++) { + pp += temp[ii]; + limit[ii] = pp-1; + pp <<= 1; + base[ii+1] = pp-(hh+=temp[ii]); + } + limit[maxLen] = pp+temp[maxLen]-1; + limit[maxLen+1] = INT_MAX; + base[minLen] = 0; + } + + return 0; +} + +/* First pass, read block's symbols into dbuf[dbufCount]. + * + * This undoes three types of compression: huffman coding, run length encoding, + * and move to front encoding. We have to undo all those to know when we've + * read enough input. + */ + +static int read_huffman_data(struct bunzip_data *bd, struct bwdata *bw) +{ + struct group_data *hufGroup; + int hh, ii, jj, kk, runPos, dbufCount, symCount, selector, nextSym, + *byteCount, *base, *limit; + unsigned int *dbuf = bw->dbuf; + unsigned char uc; + + // We've finished reading and digesting the block header. Now read this + // 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 + byteCount = bw->byteCount; + for(ii=0; ii<256; ii++) { + byteCount[ii] = 0; + bd->mtfSymbol[ii] = ii; + } + + // Loop through compressed symbols. This is the first "tight inner loop" + // that needs to be micro-optimized for speed. (This one fills out dbuf[] + // linearly, staying in cache more, so isn't as limited by DRAM access.) + runPos = dbufCount = symCount = selector = 0; + // Some unnecessary initializations to shut gcc up. + base = limit = 0; + hufGroup = 0; + hh = 0; + + for (;;) { + // Have we reached the end of this huffman group? + if (!(symCount--)) { + // Determine which huffman coding group to use. + symCount = GROUP_SIZE-1; + if (selector >= bd->nSelectors) return RETVAL_DATA_ERROR; + hufGroup = bd->groups + bd->selectors[selector++]; + base = hufGroup->base-1; + limit = hufGroup->limit-1; + } + + // Read next huffman-coded symbol (into jj). + ii = hufGroup->minLen; + jj = get_bits(bd, ii); + while (jj > limit[ii]) { + // if (ii > hufGroup->maxLen) return RETVAL_DATA_ERROR; + ii++; + + // Unroll get_bits() to avoid a function call when the data's in + // the buffer already. + kk = bd->inbufBitCount + ? (bd->inbufBits >> --(bd->inbufBitCount)) & 1 : get_bits(bd, 1); + jj = (jj << 1) | kk; + } + // Huffman decode jj into nextSym (with bounds checking) + jj-=base[ii]; + + if (ii > hufGroup->maxLen || (unsigned)jj >= MAX_SYMBOLS) + return RETVAL_DATA_ERROR; + nextSym = hufGroup->permute[jj]; + + // If this is a repeated run, loop collecting data + if ((unsigned)nextSym <= SYMBOL_RUNB) { + // If this is the start of a new run, zero out counter + if(!runPos) { + runPos = 1; + hh = 0; + } + + /* Neat trick that saves 1 symbol: instead of or-ing 0 or 1 at + each bit position, add 1 or 2 instead. For example, + 1011 is 1<<0 + 1<<1 + 2<<2. 1010 is 2<<0 + 2<<1 + 1<<2. + You can make any bit pattern that way using 1 less symbol than + the basic or 0/1 method (except all bits 0, which would use no + symbols, but a run of length 0 doesn't mean anything in this + context). Thus space is saved. */ + hh += (runPos << nextSym); // +runPos if RUNA; +2*runPos if RUNB + runPos <<= 1; + continue; + } + + /* When we hit the first non-run symbol after a run, we now know + how many times to repeat the last literal, so append that many + copies to our buffer of decoded symbols (dbuf) now. (The last + literal used is the one at the head of the mtfSymbol array.) */ + if (runPos) { + runPos = 0; + if (dbufCount+hh > bd->dbufSize) return RETVAL_DATA_ERROR; + + uc = bd->symToByte[bd->mtfSymbol[0]]; + byteCount[uc] += hh; + while (hh--) dbuf[dbufCount++] = uc; + } + + // Is this the terminating symbol? + if (nextSym>bd->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.) */ + if (dbufCount>=bd->dbufSize) return RETVAL_DATA_ERROR; + ii = nextSym - 1; + uc = bd->mtfSymbol[ii]; + // On my laptop, unrolling this memmove() into a loop shaves 3.5% off + // the total running time. + while(ii--) bd->mtfSymbol[ii+1] = bd->mtfSymbol[ii]; + bd->mtfSymbol[0] = uc; + uc = bd->symToByte[uc]; + + // We have our literal byte. Save it into dbuf. + byteCount[uc]++; + dbuf[dbufCount++] = (unsigned int)uc; + } + + // Now we know what dbufCount is, do a better sanity check on origPtr. + if (bw->origPtr >= (bw->writeCount = dbufCount)) return RETVAL_DATA_ERROR; + + return 0; +} + +// Flush output buffer to disk +void flush_bunzip_outbuf(struct bunzip_data *bd, int out_fd) +{ + if (bd->outbufPos) { + if (write(out_fd, bd->outbuf, bd->outbufPos) != bd->outbufPos) + error_exit("output EOF"); + bd->outbufPos = 0; + } +} + +void burrows_wheeler_prep(struct bunzip_data *bd, struct bwdata *bw) +{ + int ii, jj; + unsigned int *dbuf = bw->dbuf; + int *byteCount = bw->byteCount; + + // Technically this part is preparation for the burrows-wheeler + // transform, but it's quick and convenient to do here. + + // Turn byteCount into cumulative occurrence counts of 0 to n-1. + jj = 0; + for (ii=0; ii<256; ii++) { + int kk = jj + byteCount[ii]; + byteCount[ii] = jj; + jj = kk; + } + + // Use occurrence counts to quickly figure out what order dbuf would be in + // if we sorted it. + for (ii=0; ii < bw->writeCount; ii++) { + unsigned char uc = dbuf[ii]; + dbuf[byteCount[uc]] |= (ii << 8); + byteCount[uc]++; + } + + // blockRandomised support would go here. + + // Using ii as position, jj as previous character, hh as current character, + // and uc as run count. + bw->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). */ + if (bw->writeCount) { + bw->writePos = dbuf[bw->origPtr]; + bw->writeCurrent = (unsigned char)bw->writePos; + bw->writePos >>= 8; + bw->writeRun = -1; + } +} + +// Decompress a block of text to intermediate buffer +int read_bunzip_data(struct bunzip_data *bd) +{ + int rc = read_block_header(bd, bd->bwdata); + if (!rc) rc=read_huffman_data(bd, bd->bwdata); + + // First thing that can be done by a background thread. + burrows_wheeler_prep(bd, bd->bwdata); + + return rc; +} + +// 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 : 0. Notice all errors are negative #'s. +// +// Burrows-wheeler transform is described at: +// http://dogma.net/markn/articles/bwt/bwt.htm +// http://marknelson.us/1996/09/01/bwt/ + +int write_bunzip_data(struct bunzip_data *bd, struct bwdata *bw, int out_fd, char *outbuf, int len) +{ + unsigned int *dbuf = bw->dbuf; + int count, pos, current, run, copies, outbyte, previous, gotcount = 0; + + for (;;) { + // If last read was short due to end of file, return last block now + if (bw->writeCount < 0) return bw->writeCount; + + // If we need to refill dbuf, do it. + if (!bw->writeCount) { + int i = read_bunzip_data(bd); + if (i) { + if (i == RETVAL_LAST_BLOCK) { + bw->writeCount = i; + return gotcount; + } else return i; + } + } + + // loop generating output + count = bw->writeCount; + pos = bw->writePos; + current = bw->writeCurrent; + run = bw->writeRun; + while (count) { + + // If somebody (like 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--; + + // 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; + } 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; + bw->dataCRC = (bw->dataCRC << 8) + ^ bd->crc32Table[(bw->dataCRC >> 24) ^ outbyte]; + } + if (current != previous) run=0; + } + + // decompression of this block completed successfully + bw->dataCRC = ~(bw->dataCRC); + bd->totalCRC = ((bd->totalCRC << 1) | (bd->totalCRC >> 31)) ^ bw->dataCRC; + + // if this block had a crc error, force file level crc error. + if (bw->dataCRC != bw->headerCRC) { + bd->totalCRC = bw->headerCRC+1; + + return RETVAL_LAST_BLOCK; + } +dataus_interruptus: + bw->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); + bw->writePos = pos; + bw->writeCurrent = current; + bw->writeRun = run; + + return gotcount; + } + } + } +} + +// Allocate the structure, read file header. If !len, src_fd contains +// filehandle to read from. Else inbuf contains data. +int start_bunzip(struct bunzip_data **bdp, int src_fd, char *inbuf, int len) +{ + struct bunzip_data *bd; + unsigned int i; + + // Figure out how much data to allocate. + i = sizeof(struct bunzip_data); + if (!len) i += IOBUF_SIZE; + + // Allocate bunzip_data. Most fields initialize to zero. + bd = *bdp = xzalloc(i); + if (len) { + bd->inbuf = inbuf; + bd->inbufCount = len; + bd->in_fd = -1; + } else { + bd->inbuf = (char *)(bd+1); + bd->in_fd = src_fd; + } + + crc_init(bd->crc32Table, 0); + + // 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 + // 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')*THREADS; + for (i=0; i<THREADS; i++) + bd->bwdata[i].dbuf = xmalloc(bd->dbufSize * sizeof(int)); + + return 0; +} + +// Example usage: decompress src_fd to dst_fd. (Stops at end of bzip data, +// not end of file.) +void bunzipStream(int src_fd, int dst_fd) +{ + struct bunzip_data *bd; + char *bunzip_errors[]={NULL, "not bzip", "bad data", "old format"}; + int i, j; + + if (!(i = start_bunzip(&bd,src_fd, 0, 0))) { + i = write_bunzip_data(bd,bd->bwdata, dst_fd, 0, 0); + if (i==RETVAL_LAST_BLOCK && bd->bwdata[0].headerCRC==bd->totalCRC) i = 0; + } + flush_bunzip_outbuf(bd, dst_fd); + + for (j=0; j<THREADS; j++) free(bd->bwdata[j].dbuf); + free(bd); + if (i) error_exit(bunzip_errors[-i]); +} + static void do_bzcat(int fd, char *name) { bunzipStream(fd, 1); |