toys/other/bzcat.c

   1 /* bzcat.c - bzip2 decompression
   2  *
   3  * Copyright 2003, 2007 Rob Landley <rob@landley.net>
   4  *
   5  * Based on a close reading (but not the actual code) of the original bzip2
   6  * decompression code by Julian R Seward (jseward@acm.org), which also
   7  * acknowledges contributions by Mike Burrows, David Wheeler, Peter Fenwick,
   8  * Alistair Moffat, Radford Neal, Ian H. Witten, Robert Sedgewick, and
   9  * Jon L. Bentley.
  10  *
  11  * No standard.
  12
  13
  14 USE_BZCAT(NEWTOY(bzcat, NULL, TOYFLAG_USR|TOYFLAG_BIN))
  15 USE_BUNZIP2(NEWTOY(bunzip2, "cftkv", TOYFLAG_USR|TOYFLAG_BIN))
  16
  17 config BUNZIP2
  18   bool "bunzip2"
  19   default y
  20   help
  21     usage: bunzip2 [-cftkv] [FILE...]
  22
  23     Decompress listed files (file.bz becomes file) deleting archive file(s).
  24     Read from stdin if no files listed.
  25
  26     -c  force output to stdout
  27     -f  force decompression. (If FILE doesn't end in .bz, replace original.)
  28     -k  keep input files (-c and -t imply this)
  29     -t  test integrity
  30     -v  verbose
  31
  32 config BZCAT
  33   bool "bzcat"
  34   default y
  35   help
  36     usage: bzcat [FILE...]
  37
  38     Decompress listed files to stdout. Use stdin if no files listed.
  39 */
  40
  41 #define FOR_bunzip2
  42 #include "toys.h"
  43
  44 #define THREADS 1
  45
  46 // Constants for huffman coding
  47 #define MAX_GROUPS               6
  48 #define GROUP_SIZE               50     /* 64 would have been more efficient */
  49 #define MAX_HUFCODE_BITS         20     /* Longest huffman code allowed */
  50 #define MAX_SYMBOLS              258    /* 256 literals + RUNA + RUNB */
  51 #define SYMBOL_RUNA              0
  52 #define SYMBOL_RUNB              1
  53
  54 // Other housekeeping constants
  55 #define IOBUF_SIZE               4096
  56
  57 // Status return values
  58 #define RETVAL_LAST_BLOCK        (-100)
  59 #define RETVAL_NOT_BZIP_DATA     (-1)
  60 #define RETVAL_DATA_ERROR        (-2)
  61 #define RETVAL_OBSOLETE_INPUT    (-3)
  62
  63 // This is what we know about each huffman coding group
  64 struct group_data {
  65   int limit[MAX_HUFCODE_BITS+1], base[MAX_HUFCODE_BITS], permute[MAX_SYMBOLS];
  66   char minLen, maxLen;
  67 };
  68
  69 // Data for burrows wheeler transform
  70
  71 struct bwdata {
  72   unsigned int origPtr;
  73   int byteCount[256];
  74   // State saved when interrupting output
  75   int writePos, writeRun, writeCount, writeCurrent;
  76   unsigned int dataCRC, headerCRC;
  77   unsigned int *dbuf;
  78 };
  79
  80 // Structure holding all the housekeeping data, including IO buffers and
  81 // memory that persists between calls to bunzip
  82 struct bunzip_data {
  83   // Input stream, input buffer, input bit buffer
  84   int in_fd, inbufCount, inbufPos;
  85   char *inbuf;
  86   unsigned int inbufBitCount, inbufBits;
  87
  88   // Output buffer
  89   char outbuf[IOBUF_SIZE];
  90   int outbufPos;
  91
  92   unsigned int totalCRC;
  93
  94   // First pass decompression data (Huffman and MTF decoding)
  95   char selectors[32768];                  // nSelectors=15 bits
  96   struct group_data groups[MAX_GROUPS];   // huffman coding tables
  97   int symTotal, groupCount, nSelectors;
  98   unsigned char symToByte[256], mtfSymbol[256];
  99
 100   // The CRC values stored in the block header and calculated from the data
 101   unsigned int crc32Table[256];
 102
 103   // Second pass decompression data (burrows-wheeler transform)
 104   unsigned int dbufSize;
 105   struct bwdata bwdata[THREADS];
 106 };
 107
 108 // Return the next nnn bits of input.  All reads from the compressed input
 109 // are done through this function.  All reads are big endian.
 110 static unsigned int get_bits(struct bunzip_data *bd, char bits_wanted)
 111 {
 112   unsigned int bits = 0;
 113
 114   // If we need to get more data from the byte buffer, do so.  (Loop getting
 115   // one byte at a time to enforce endianness and avoid unaligned access.)
 116   while (bd->inbufBitCount < bits_wanted) {
 117
 118     // If we need to read more data from file into byte buffer, do so
 119     if (bd->inbufPos == bd->inbufCount) {
 120       if (0 >= (bd->inbufCount = read(bd->in_fd, bd->inbuf, IOBUF_SIZE)))
 121         error_exit("input EOF");
 122       bd->inbufPos = 0;
 123     }
 124
 125     // Avoid 32-bit overflow (dump bit buffer to top of output)
 126     if (bd->inbufBitCount>=24) {
 127       bits = bd->inbufBits&((1<<bd->inbufBitCount)-1);
 128       bits_wanted -= bd->inbufBitCount;
 129       bits <<= bits_wanted;
 130       bd->inbufBitCount = 0;
 131     }
 132
 133     // Grab next 8 bits of input from buffer.
 134     bd->inbufBits = (bd->inbufBits<<8) | bd->inbuf[bd->inbufPos++];
 135     bd->inbufBitCount += 8;
 136   }
 137
 138   // Calculate result
 139   bd->inbufBitCount -= bits_wanted;
 140   bits |= (bd->inbufBits>>bd->inbufBitCount) & ((1<<bits_wanted)-1);
 141
 142   return bits;
 143 }
 144
 145 /* Read block header at start of a new compressed data block.  Consists of:
 146  *
 147  * 48 bits : Block signature, either pi (data block) or e (EOF block).
 148  * 32 bits : bw->headerCRC
 149  * 1  bit  : obsolete feature flag.
 150  * 24 bits : origPtr (Burrows-wheeler unwind index, only 20 bits ever used)
 151  * 16 bits : Mapping table index.
 152  *[16 bits]: symToByte[symTotal] (Mapping table.  For each bit set in mapping
 153  *           table index above, read another 16 bits of mapping table data.
 154  *           If correspondig bit is unset, all bits in that mapping table
 155  *           section are 0.)
 156  *  3 bits : groupCount (how many huffman tables used to encode, anywhere
 157  *           from 2 to MAX_GROUPS)
 158  * variable: hufGroup[groupCount] (MTF encoded huffman table data.)
 159  */
 160
 161 static int read_block_header(struct bunzip_data *bd, struct bwdata *bw)
 162 {
 163   struct group_data *hufGroup;
 164   int hh, ii, jj, kk, symCount, *base, *limit;
 165   unsigned char uc;
 166
 167   // Read in header signature and CRC (which is stored big endian)
 168   ii = get_bits(bd, 24);
 169   jj = get_bits(bd, 24);
 170   bw->headerCRC = get_bits(bd,32);
 171
 172   // Is this the EOF block with CRC for whole file?  (Constant is "e")
 173   if (ii==0x177245 && jj==0x385090) return RETVAL_LAST_BLOCK;
 174
 175   // Is this a valid data block?  (Constant is "pi".)
 176   if (ii!=0x314159 || jj!=0x265359) return RETVAL_NOT_BZIP_DATA;
 177
 178   // We can add support for blockRandomised if anybody complains.
 179   if (get_bits(bd,1)) return RETVAL_OBSOLETE_INPUT;
 180   if ((bw->origPtr = get_bits(bd,24)) > bd->dbufSize) return RETVAL_DATA_ERROR;
 181
 182   // mapping table: if some byte values are never used (encoding things
 183   // like ascii text), the compression code removes the gaps to have fewer
 184   // symbols to deal with, and writes a sparse bitfield indicating which
 185   // values were present.  We make a translation table to convert the symbols
 186   // back to the corresponding bytes.
 187   hh = get_bits(bd, 16);
 188   bd->symTotal = 0;
 189   for (ii=0; ii<16; ii++) {
 190     if (hh & (1 << (15 - ii))) {
 191       kk = get_bits(bd, 16);
 192       for (jj=0; jj<16; jj++)
 193         if (kk & (1 << (15 - jj)))
 194           bd->symToByte[bd->symTotal++] = (16 * ii) + jj;
 195     }
 196   }
 197
 198   // How many different huffman coding groups does this block use?
 199   bd->groupCount = get_bits(bd,3);
 200   if (bd->groupCount<2 || bd->groupCount>MAX_GROUPS) return RETVAL_DATA_ERROR;
 201
 202   // nSelectors: Every GROUP_SIZE many symbols we switch huffman coding
 203   // tables.  Each group has a selector, which is an index into the huffman
 204   // coding table arrays.
 205   //
 206   // Read in the group selector array, which is stored as MTF encoded
 207   // bit runs.  (MTF = Move To Front.  Every time a symbol occurs it's moved
 208   // to the front of the table, so it has a shorter encoding next time.)
 209   if (!(bd->nSelectors = get_bits(bd, 15))) return RETVAL_DATA_ERROR;
 210   for (ii=0; ii<bd->groupCount; ii++) bd->mtfSymbol[ii] = ii;
 211   for (ii=0; ii<bd->nSelectors; ii++) {
 212
 213     // Get next value
 214     for(jj=0;get_bits(bd,1);jj++)
 215       if (jj>=bd->groupCount) return RETVAL_DATA_ERROR;
 216
 217     // Decode MTF to get the next selector, and move it to the front.
 218     uc = bd->mtfSymbol[jj];
 219     memmove(bd->mtfSymbol+1, bd->mtfSymbol, jj);
 220     bd->mtfSymbol[0] = bd->selectors[ii] = uc;
 221   }
 222
 223   // Read the huffman coding tables for each group, which code for symTotal
 224   // literal symbols, plus two run symbols (RUNA, RUNB)
 225   symCount = bd->symTotal+2;
 226   for (jj=0; jj<bd->groupCount; jj++) {
 227     unsigned char length[MAX_SYMBOLS];
 228     unsigned temp[MAX_HUFCODE_BITS+1];
 229     int minLen, maxLen, pp;
 230
 231     // Read lengths
 232     hh = get_bits(bd, 5);
 233     for (ii = 0; ii < symCount; ii++) {
 234       for(;;) {
 235         // !hh || hh > MAX_HUFCODE_BITS in one test.
 236         if (MAX_HUFCODE_BITS-1 < (unsigned)hh-1) return RETVAL_DATA_ERROR;
 237         // Grab 2 bits instead of 1 (slightly smaller/faster).  Stop if
 238         // first bit is 0, otherwise second bit says whether to
 239         // increment or decrement.
 240         kk = get_bits(bd, 2);
 241         if (kk & 2) hh += 1 - ((kk&1)<<1);
 242         else {
 243           bd->inbufBitCount++;
 244           break;
 245         }
 246       }
 247       length[ii] = hh;
 248     }
 249
 250     // Find largest and smallest lengths in this group
 251     minLen = maxLen = length[0];
 252     for (ii = 1; ii < symCount; ii++) {
 253       if(length[ii] > maxLen) maxLen = length[ii];
 254       else if(length[ii] < minLen) minLen = length[ii];
 255     }
 256
 257     /* Calculate permute[], base[], and limit[] tables from length[].
 258      *
 259      * permute[] is the lookup table for converting huffman coded symbols
 260      * into decoded symbols.  It contains symbol values sorted by length.
 261      *
 262      * base[] is the amount to subtract from the value of a huffman symbol
 263      * of a given length when using permute[].
 264      *
 265      * limit[] indicates the largest numerical value a symbol with a given
 266      * number of bits can have.  It lets us know when to stop reading.
 267      *
 268      * To use these, keep reading bits until value <= limit[bitcount] or
 269      * you've read over 20 bits (error).  Then the decoded symbol
 270      * equals permute[hufcode_value - base[hufcode_bitcount]].
 271      */
 272     hufGroup = bd->groups+jj;
 273     hufGroup->minLen = minLen;
 274     hufGroup->maxLen = maxLen;
 275
 276     // Note that minLen can't be smaller than 1, so we adjust the base
 277     // and limit array pointers so we're not always wasting the first
 278     // entry.  We do this again when using them (during symbol decoding).
 279     base = hufGroup->base-1;
 280     limit = hufGroup->limit-1;
 281
 282     // zero temp[] and limit[], and calculate permute[]
 283     pp = 0;
 284     for (ii = minLen; ii <= maxLen; ii++) {
 285       temp[ii] = limit[ii] = 0;
 286       for (hh = 0; hh < symCount; hh++)
 287         if (length[hh] == ii) hufGroup->permute[pp++] = hh;
 288     }
 289
 290     // Count symbols coded for at each bit length
 291     for (ii = 0; ii < symCount; ii++) temp[length[ii]]++;
 292
 293     /* Calculate limit[] (the largest symbol-coding value at each bit
 294      * length, which is (previous limit<<1)+symbols at this level), and
 295      * base[] (number of symbols to ignore at each bit length, which is
 296      * limit minus the cumulative count of symbols coded for already). */
 297     pp = hh = 0;
 298     for (ii = minLen; ii < maxLen; ii++) {
 299       pp += temp[ii];
 300       limit[ii] = pp-1;
 301       pp <<= 1;
 302       base[ii+1] = pp-(hh+=temp[ii]);
 303     }
 304     limit[maxLen] = pp+temp[maxLen]-1;
 305     limit[maxLen+1] = INT_MAX;
 306     base[minLen] = 0;
 307   }
 308
 309   return 0;
 310 }
 311
 312 /* First pass, read block's symbols into dbuf[dbufCount].
 313  *
 314  * This undoes three types of compression: huffman coding, run length encoding,
 315  * and move to front encoding.  We have to undo all those to know when we've
 316  * read enough input.
 317  */
 318
 319 static int read_huffman_data(struct bunzip_data *bd, struct bwdata *bw)
 320 {
 321   struct group_data *hufGroup;
 322   int ii, jj, kk, runPos, dbufCount, symCount, selector, nextSym,
 323     *byteCount, *base, *limit;
 324   unsigned hh, *dbuf = bw->dbuf;
 325   unsigned char uc;
 326
 327   // We've finished reading and digesting the block header.  Now read this
 328   // block's huffman coded symbols from the file and undo the huffman coding
 329   // and run length encoding, saving the result into dbuf[dbufCount++] = uc
 330
 331   // Initialize symbol occurrence counters and symbol mtf table
 332   byteCount = bw->byteCount;
 333   for(ii=0; ii<256; ii++) {
 334     byteCount[ii] = 0;
 335     bd->mtfSymbol[ii] = ii;
 336   }
 337
 338   // Loop through compressed symbols.  This is the first "tight inner loop"
 339   // that needs to be micro-optimized for speed.  (This one fills out dbuf[]
 340   // linearly, staying in cache more, so isn't as limited by DRAM access.)
 341   runPos = dbufCount = symCount = selector = 0;
 342   // Some unnecessary initializations to shut gcc up.
 343   base = limit = 0;
 344   hufGroup = 0;
 345   hh = 0;
 346
 347   for (;;) {
 348     // Have we reached the end of this huffman group?
 349     if (!(symCount--)) {
 350       // Determine which huffman coding group to use.
 351       symCount = GROUP_SIZE-1;
 352       if (selector >= bd->nSelectors) return RETVAL_DATA_ERROR;
 353       hufGroup = bd->groups + bd->selectors[selector++];
 354       base = hufGroup->base-1;
 355       limit = hufGroup->limit-1;
 356     }
 357
 358     // Read next huffman-coded symbol (into jj).
 359     ii = hufGroup->minLen;
 360     jj = get_bits(bd, ii);
 361     while (jj > limit[ii]) {
 362       // if (ii > hufGroup->maxLen) return RETVAL_DATA_ERROR;
 363       ii++;
 364
 365       // Unroll get_bits() to avoid a function call when the data's in
 366       // the buffer already.
 367       kk = bd->inbufBitCount
 368         ? (bd->inbufBits >> --(bd->inbufBitCount)) & 1 : get_bits(bd, 1);
 369       jj = (jj << 1) | kk;
 370     }
 371     // Huffman decode jj into nextSym (with bounds checking)
 372     jj-=base[ii];
 373
 374     if (ii > hufGroup->maxLen || (unsigned)jj >= MAX_SYMBOLS)
 375       return RETVAL_DATA_ERROR;
 376     nextSym = hufGroup->permute[jj];
 377
 378     // If this is a repeated run, loop collecting data
 379     if ((unsigned)nextSym <= SYMBOL_RUNB) {
 380       // If this is the start of a new run, zero out counter
 381       if(!runPos) {
 382         runPos = 1;
 383         hh = 0;
 384       }
 385
 386       /* Neat trick that saves 1 symbol: instead of or-ing 0 or 1 at
 387          each bit position, add 1 or 2 instead. For example,
 388          1011 is 1<<0 + 1<<1 + 2<<2. 1010 is 2<<0 + 2<<1 + 1<<2.
 389          You can make any bit pattern that way using 1 less symbol than
 390          the basic or 0/1 method (except all bits 0, which would use no
 391          symbols, but a run of length 0 doesn't mean anything in this
 392          context). Thus space is saved. */
 393       hh += (runPos << nextSym); // +runPos if RUNA; +2*runPos if RUNB
 394       runPos <<= 1;
 395       continue;
 396     }
 397
 398     /* When we hit the first non-run symbol after a run, we now know
 399        how many times to repeat the last literal, so append that many
 400        copies to our buffer of decoded symbols (dbuf) now. (The last
 401        literal used is the one at the head of the mtfSymbol array.) */
 402     if (runPos) {
 403       runPos = 0;
 404       // Check for integer overflow
 405       if (hh>bd->dbufSize || dbufCount+hh>bd->dbufSize)
 406         return RETVAL_DATA_ERROR;
 407
 408       uc = bd->symToByte[bd->mtfSymbol[0]];
 409       byteCount[uc] += hh;
 410       while (hh--) dbuf[dbufCount++] = uc;
 411     }
 412
 413     // Is this the terminating symbol?
 414     if (nextSym>bd->symTotal) break;
 415
 416     /* At this point, the symbol we just decoded indicates a new literal
 417        character. Subtract one to get the position in the MTF array
 418        at which this literal is currently to be found. (Note that the
 419        result can't be -1 or 0, because 0 and 1 are RUNA and RUNB.
 420        Another instance of the first symbol in the mtf array, position 0,
 421        would have been handled as part of a run.) */
 422     if (dbufCount>=bd->dbufSize) return RETVAL_DATA_ERROR;
 423     ii = nextSym - 1;
 424     uc = bd->mtfSymbol[ii];
 425     // On my laptop, unrolling this memmove() into a loop shaves 3.5% off
 426     // the total running time.
 427     while(ii--) bd->mtfSymbol[ii+1] = bd->mtfSymbol[ii];
 428     bd->mtfSymbol[0] = uc;
 429     uc = bd->symToByte[uc];
 430
 431     // We have our literal byte.  Save it into dbuf.
 432     byteCount[uc]++;
 433     dbuf[dbufCount++] = (unsigned int)uc;
 434   }
 435
 436   // Now we know what dbufCount is, do a better sanity check on origPtr.
 437   if (bw->origPtr >= (bw->writeCount = dbufCount)) return RETVAL_DATA_ERROR;
 438
 439   return 0;
 440 }
 441
 442 // Flush output buffer to disk
 443 static void flush_bunzip_outbuf(struct bunzip_data *bd, int out_fd)
 444 {
 445   if (bd->outbufPos) {
 446     if (write(out_fd, bd->outbuf, bd->outbufPos) != bd->outbufPos)
 447       error_exit("output EOF");
 448     bd->outbufPos = 0;
 449   }
 450 }
 451
 452 static void burrows_wheeler_prep(struct bunzip_data *bd, struct bwdata *bw)
 453 {
 454   int ii, jj;
 455   unsigned int *dbuf = bw->dbuf;
 456   int *byteCount = bw->byteCount;
 457
 458   // Turn byteCount into cumulative occurrence counts of 0 to n-1.
 459   jj = 0;
 460   for (ii=0; ii<256; ii++) {
 461     int kk = jj + byteCount[ii];
 462     byteCount[ii] = jj;
 463     jj = kk;
 464   }
 465
 466   // Use occurrence counts to quickly figure out what order dbuf would be in
 467   // if we sorted it.
 468   for (ii=0; ii < bw->writeCount; ii++) {
 469     unsigned char uc = dbuf[ii];
 470     dbuf[byteCount[uc]] |= (ii << 8);
 471     byteCount[uc]++;
 472   }
 473
 474   // blockRandomised support would go here.
 475
 476   // Using ii as position, jj as previous character, hh as current character,
 477   // and uc as run count.
 478   bw->dataCRC = 0xffffffffL;
 479
 480   /* Decode first byte by hand to initialize "previous" byte. Note that it
 481      doesn't get output, and if the first three characters are identical
 482      it doesn't qualify as a run (hence uc=255, which will either wrap
 483      to 1 or get reset). */
 484   if (bw->writeCount) {
 485     bw->writePos = dbuf[bw->origPtr];
 486     bw->writeCurrent = (unsigned char)bw->writePos;
 487     bw->writePos >>= 8;
 488     bw->writeRun = -1;
 489   }
 490 }
 491
 492 // Decompress a block of text to intermediate buffer
 493 static int read_bunzip_data(struct bunzip_data *bd)
 494 {
 495   int rc = read_block_header(bd, bd->bwdata);
 496   if (!rc) rc=read_huffman_data(bd, bd->bwdata);
 497
 498   // First thing that can be done by a background thread.
 499   burrows_wheeler_prep(bd, bd->bwdata);
 500
 501   return rc;
 502 }
 503
 504 // Undo burrows-wheeler transform on intermediate buffer to produce output.
 505 // If !len, write up to len bytes of data to buf.  Otherwise write to out_fd.
 506 // Returns len ? bytes written : 0.  Notice all errors are negative #'s.
 507 //
 508 // Burrows-wheeler transform is described at:
 509 // http://dogma.net/markn/articles/bwt/bwt.htm
 510 // http://marknelson.us/1996/09/01/bwt/
 511
 512 static int write_bunzip_data(struct bunzip_data *bd, struct bwdata *bw,
 513   int out_fd, char *outbuf, int len)
 514 {
 515   unsigned int *dbuf = bw->dbuf;
 516   int count, pos, current, run, copies, outbyte, previous, gotcount = 0;
 517
 518   for (;;) {
 519     // If last read was short due to end of file, return last block now
 520     if (bw->writeCount < 0) return bw->writeCount;
 521
 522     // If we need to refill dbuf, do it.
 523     if (!bw->writeCount) {
 524       int i = read_bunzip_data(bd);
 525       if (i) {
 526         if (i == RETVAL_LAST_BLOCK) {
 527           bw->writeCount = i;
 528           return gotcount;
 529         } else return i;
 530       }
 531     }
 532
 533     // loop generating output
 534     count = bw->writeCount;
 535     pos = bw->writePos;
 536     current = bw->writeCurrent;
 537     run = bw->writeRun;
 538     while (count) {
 539
 540       // If somebody (like tar) wants a certain number of bytes of
 541       // data from memory instead of written to a file, humor them.
 542       if (len && bd->outbufPos >= len) goto dataus_interruptus;
 543       count--;
 544
 545       // Follow sequence vector to undo Burrows-Wheeler transform.
 546       previous = current;
 547       pos = dbuf[pos];
 548       current = pos&0xff;
 549       pos >>= 8;
 550
 551       // Whenever we see 3 consecutive copies of the same byte,
 552       // the 4th is a repeat count
 553       if (run++ == 3) {
 554         copies = current;
 555         outbyte = previous;
 556         current = -1;
 557       } else {
 558         copies = 1;
 559         outbyte = current;
 560       }
 561
 562       // Output bytes to buffer, flushing to file if necessary
 563       while (copies--) {
 564         if (bd->outbufPos == IOBUF_SIZE) flush_bunzip_outbuf(bd, out_fd);
 565         bd->outbuf[bd->outbufPos++] = outbyte;
 566         bw->dataCRC = (bw->dataCRC << 8)
 567                 ^ bd->crc32Table[(bw->dataCRC >> 24) ^ outbyte];
 568       }
 569       if (current != previous) run=0;
 570     }
 571
 572     // decompression of this block completed successfully
 573     bw->dataCRC = ~(bw->dataCRC);
 574     bd->totalCRC = ((bd->totalCRC << 1) | (bd->totalCRC >> 31)) ^ bw->dataCRC;
 575
 576     // if this block had a crc error, force file level crc error.
 577     if (bw->dataCRC != bw->headerCRC) {
 578       bd->totalCRC = bw->headerCRC+1;
 579
 580       return RETVAL_LAST_BLOCK;
 581     }
 582 dataus_interruptus:
 583     bw->writeCount = count;
 584     if (len) {
 585       gotcount += bd->outbufPos;
 586       memcpy(outbuf, bd->outbuf, len);
 587
 588       // If we got enough data, checkpoint loop state and return
 589       if ((len -= bd->outbufPos)<1) {
 590         bd->outbufPos -= len;
 591         if (bd->outbufPos) memmove(bd->outbuf, bd->outbuf+len, bd->outbufPos);
 592         bw->writePos = pos;
 593         bw->writeCurrent = current;
 594         bw->writeRun = run;
 595
 596         return gotcount;
 597       }
 598     }
 599   }
 600 }
 601
 602 // Allocate the structure, read file header. If !len, src_fd contains
 603 // filehandle to read from. Else inbuf contains data.
 604 static int start_bunzip(struct bunzip_data **bdp, int src_fd, char *inbuf,
 605   int len)
 606 {
 607   struct bunzip_data *bd;
 608   unsigned int i;
 609
 610   // Figure out how much data to allocate.
 611   i = sizeof(struct bunzip_data);
 612   if (!len) i += IOBUF_SIZE;
 613
 614   // Allocate bunzip_data. Most fields initialize to zero.
 615   bd = *bdp = xzalloc(i);
 616   if (len) {
 617     bd->inbuf = inbuf;
 618     bd->inbufCount = len;
 619     bd->in_fd = -1;
 620   } else {
 621     bd->inbuf = (char *)(bd+1);
 622     bd->in_fd = src_fd;
 623   }
 624
 625   crc_init(bd->crc32Table, 0);
 626
 627   // Ensure that file starts with "BZh".
 628   for (i=0;i<3;i++) if (get_bits(bd,8)!="BZh"[i]) return RETVAL_NOT_BZIP_DATA;
 629
 630   // Next byte ascii '1'-'9', indicates block size in units of 100k of
 631   // uncompressed data. Allocate intermediate buffer for block.
 632   i = get_bits(bd, 8);
 633   if (i<'1' || i>'9') return RETVAL_NOT_BZIP_DATA;
 634   bd->dbufSize = 100000*(i-'0')*THREADS;
 635   for (i=0; i<THREADS; i++)
 636     bd->bwdata[i].dbuf = xmalloc(bd->dbufSize * sizeof(int));
 637
 638   return 0;
 639 }
 640
 641 // Example usage: decompress src_fd to dst_fd. (Stops at end of bzip data,
 642 // not end of file.)
 643 static char *bunzipStream(int src_fd, int dst_fd)
 644 {
 645   struct bunzip_data *bd;
 646   char *bunzip_errors[] = {0, "not bzip", "bad data", "old format"};
 647   int i, j;
 648
 649   if (!(i = start_bunzip(&bd,src_fd, 0, 0))) {
 650     i = write_bunzip_data(bd,bd->bwdata, dst_fd, 0, 0);
 651     if (i==RETVAL_LAST_BLOCK) {
 652       if (bd->bwdata[0].headerCRC==bd->totalCRC) i = 0;
 653       else i = RETVAL_DATA_ERROR;
 654     }
 655   }
 656   flush_bunzip_outbuf(bd, dst_fd);
 657
 658   for (j=0; j<THREADS; j++) free(bd->bwdata[j].dbuf);
 659   free(bd);
 660
 661   return bunzip_errors[-i];
 662 }
 663
 664 static void do_bzcat(int fd, char *name)
 665 {
 666   char *err = bunzipStream(fd, 1);
 667
 668   if (err) error_exit_raw(err);
 669 }
 670
 671 void bzcat_main(void)
 672 {
 673   loopfiles(toys.optargs, do_bzcat);
 674 }
 675
 676 static void do_bunzip2(int fd, char *name)
 677 {
 678   int outfd = 1, rename = 0, len = strlen(name);
 679   char *tmp, *err, *dotbz = 0;
 680
 681   // Trim off .bz or .bz2 extension
 682   dotbz = name+len-3;
 683   if ((len>3 && !strcmp(dotbz, ".bz")) || (len>4 && !strcmp(--dotbz, ".bz2")))
 684     dotbz = 0;
 685
 686   // For - no replace
 687   if (toys.optflags&FLAG_t) outfd = xopen("/dev/null", O_WRONLY);
 688   else if ((fd || strcmp(name, "-")) && !(toys.optflags&FLAG_c)) {
 689     if (toys.optflags&FLAG_k) {
 690       if (!dotbz || !access(name, X_OK)) {
 691         error_msg("%s exists", name);
 692
 693         return;
 694       }
 695     }
 696     outfd = copy_tempfile(fd, name, &tmp);
 697     rename++;
 698   }
 699
 700   if (toys.optflags&FLAG_v) printf("%s:", name);
 701   err = bunzipStream(fd, outfd);
 702   if (toys.optflags&FLAG_v) {
 703     printf("%s\n", err ? err : "ok");
 704     toys.exitval |= !!err;
 705   } else if (err) error_msg_raw(err);
 706
 707   // can't test outfd==1 because may have been called with stdin+stdout closed
 708   if (rename) {
 709     if (toys.optflags&FLAG_k) {
 710       free(tmp);
 711       tmp = 0;
 712     } else {
 713       if (dotbz) *dotbz = '.';
 714       if (!unlink(name)) perror_msg_raw(name);
 715     }
 716     (err ? delete_tempfile : replace_tempfile)(-1, outfd, &tmp);
 717   }
 718 }
 719
 720 void bunzip2_main(void)
 721 {
 722   loopfiles(toys.optargs, do_bunzip2);
 723 }