changeset 1197:c08555a9d948 draft

Move bunzip2 logic from lib into bzcat.
author Rob Landley <rob@landley.net>
date Fri, 07 Feb 2014 07:56:46 -0600
parents 37ea9dff9c27
children ce31c87e1862
files lib/bunzip.c lib/lib.h toys/other/bzcat.c
diffstat 3 files changed, 625 insertions(+), 630 deletions(-) [+]
line wrap: on
line diff
--- a/lib/bunzip.c	Tue Feb 04 06:20:14 2014 -0600
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,627 +0,0 @@
-/* micro-bunzip, a small, simple bzip2 decompression implementation.
- *
- * Copyright 2003, 2006 by 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.
- */
-
-#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]);
-}
--- a/lib/lib.h	Tue Feb 04 06:20:14 2014 -0600
+++ b/lib/lib.h	Fri Feb 07 07:56:46 2014 -0600
@@ -168,8 +168,6 @@
 
 struct mtab_list *xgetmountlist(char *path);
 
-void bunzipStream(int src_fd, int dst_fd);
-
 // signal
 
 void sigatexit(void *handler);
--- a/toys/other/bzcat.c	Tue Feb 04 06:20:14 2014 -0600
+++ b/toys/other/bzcat.c	Fri Feb 07 07:56:46 2014 -0600
@@ -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 @@
 
 #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);