lib/decompress_bunzip2.c

   1 /* vi: set sw = 4 ts = 4: */
   2 /*      Small bzip2 deflate implementation, by Rob Landley (rob@landley.net).
   3
   4         Based on bzip2 decompression code by Julian R Seward (jseward@acm.org),
   5         which also acknowledges contributions by Mike Burrows, David Wheeler,
   6         Peter Fenwick, Alistair Moffat, Radford Neal, Ian H. Witten,
   7         Robert Sedgewick, and Jon L. Bentley.
   8
   9         This code is licensed under the LGPLv2:
  10                 LGPL (http://www.gnu.org/copyleft/lgpl.html
  11 */
  12
  13 /*
  14         Size and speed optimizations by Manuel Novoa III  (mjn3@codepoet.org).
  15
  16         More efficient reading of Huffman codes, a streamlined read_bunzip()
  17         function, and various other tweaks.  In (limited) tests, approximately
  18         20% faster than bzcat on x86 and about 10% faster on arm.
  19
  20         Note that about 2/3 of the time is spent in read_unzip() reversing
  21         the Burrows-Wheeler transformation.  Much of that time is delay
  22         resulting from cache misses.
  23
  24         I would ask that anyone benefiting from this work, especially those
  25         using it in commercial products, consider making a donation to my local
  26         non-profit hospice organization in the name of the woman I loved, who
  27         passed away Feb. 12, 2003.
  28
  29                 In memory of Toni W. Hagan
  30
  31                 Hospice of Acadiana, Inc.
  32                 2600 Johnston St., Suite 200
  33                 Lafayette, LA 70503-3240
  34
  35                 Phone (337) 232-1234 or 1-800-738-2226
  36                 Fax   (337) 232-1297
  37
  38                 http://www.hospiceacadiana.com/
  39
  40         Manuel
  41  */
  42
  43 /*
  44         Made it fit for running in Linux Kernel by Alain Knaff (alain@knaff.lu)
  45 */
  46
  47
  48 #ifdef STATIC
  49 #define PREBOOT
  50 #else
  51 #include <linux/decompress/bunzip2.h>
  52 #include <linux/slab.h>
  53 #endif /* STATIC */
  54
  55 #include <linux/decompress/mm.h>
  56
  57 #ifndef INT_MAX
  58 #define INT_MAX 0x7fffffff
  59 #endif
  60
  61 /* Constants for Huffman coding */
  62 #define MAX_GROUPS              6
  63 #define GROUP_SIZE              50      /* 64 would have been more efficient */
  64 #define MAX_HUFCODE_BITS        20      /* Longest Huffman code allowed */
  65 #define MAX_SYMBOLS             258     /* 256 literals + RUNA + RUNB */
  66 #define SYMBOL_RUNA             0
  67 #define SYMBOL_RUNB             1
  68
  69 /* Status return values */
  70 #define RETVAL_OK                       0
  71 #define RETVAL_LAST_BLOCK               (-1)
  72 #define RETVAL_NOT_BZIP_DATA            (-2)
  73 #define RETVAL_UNEXPECTED_INPUT_EOF     (-3)
  74 #define RETVAL_UNEXPECTED_OUTPUT_EOF    (-4)
  75 #define RETVAL_DATA_ERROR               (-5)
  76 #define RETVAL_OUT_OF_MEMORY            (-6)
  77 #define RETVAL_OBSOLETE_INPUT           (-7)
  78
  79 /* Other housekeeping constants */
  80 #define BZIP2_IOBUF_SIZE                4096
  81
  82 /* This is what we know about each Huffman coding group */
  83 struct group_data {
  84         /* We have an extra slot at the end of limit[] for a sentinal value. */
  85         int limit[MAX_HUFCODE_BITS+1];
  86         int base[MAX_HUFCODE_BITS];
  87         int permute[MAX_SYMBOLS];
  88         int minLen, maxLen;
  89 };
  90
  91 /* Structure holding all the housekeeping data, including IO buffers and
  92    memory that persists between calls to bunzip */
  93 struct bunzip_data {
  94         /* State for interrupting output loop */
  95         int writeCopies, writePos, writeRunCountdown, writeCount, writeCurrent;
  96         /* I/O tracking data (file handles, buffers, positions, etc.) */
  97         int (*fill)(void*, unsigned int);
  98         int inbufCount, inbufPos /*, outbufPos*/;
  99         unsigned char *inbuf /*,*outbuf*/;
 100         unsigned int inbufBitCount, inbufBits;
 101         /* The CRC values stored in the block header and calculated from the
 102         data */
 103         unsigned int crc32Table[256], headerCRC, totalCRC, writeCRC;
 104         /* Intermediate buffer and its size (in bytes) */
 105         unsigned int *dbuf, dbufSize;
 106         /* These things are a bit too big to go on the stack */
 107         unsigned char selectors[32768];         /* nSelectors = 15 bits */
 108         struct group_data groups[MAX_GROUPS];   /* Huffman coding tables */
 109         int io_error;                   /* non-zero if we have IO error */
 110         int byteCount[256];
 111         unsigned char symToByte[256], mtfSymbol[256];
 112 };
 113
 114
 115 /* Return the next nnn bits of input.  All reads from the compressed input
 116    are done through this function.  All reads are big endian */
 117 static unsigned int INIT get_bits(struct bunzip_data *bd, char bits_wanted)
 118 {
 119         unsigned int bits = 0;
 120
 121         /* If we need to get more data from the byte buffer, do so.
 122            (Loop getting one byte at a time to enforce endianness and avoid
 123            unaligned access.) */
 124         while (bd->inbufBitCount < bits_wanted) {
 125                 /* If we need to read more data from file into byte buffer, do
 126                    so */
 127                 if (bd->inbufPos == bd->inbufCount) {
 128                         if (bd->io_error)
 129                                 return 0;
 130                         bd->inbufCount = bd->fill(bd->inbuf, BZIP2_IOBUF_SIZE);
 131                         if (bd->inbufCount <= 0) {
 132                                 bd->io_error = RETVAL_UNEXPECTED_INPUT_EOF;
 133                                 return 0;
 134                         }
 135                         bd->inbufPos = 0;
 136                 }
 137                 /* Avoid 32-bit overflow (dump bit buffer to top of output) */
 138                 if (bd->inbufBitCount >= 24) {
 139                         bits = bd->inbufBits&((1 << bd->inbufBitCount)-1);
 140                         bits_wanted -= bd->inbufBitCount;
 141                         bits <<= bits_wanted;
 142                         bd->inbufBitCount = 0;
 143                 }
 144                 /* Grab next 8 bits of input from buffer. */
 145                 bd->inbufBits = (bd->inbufBits << 8)|bd->inbuf[bd->inbufPos++];
 146                 bd->inbufBitCount += 8;
 147         }
 148         /* Calculate result */
 149         bd->inbufBitCount -= bits_wanted;
 150         bits |= (bd->inbufBits >> bd->inbufBitCount)&((1 << bits_wanted)-1);
 151
 152         return bits;
 153 }
 154
 155 /* Unpacks the next block and sets up for the inverse burrows-wheeler step. */
 156
 157 static int INIT get_next_block(struct bunzip_data *bd)
 158 {
 159         struct group_data *hufGroup = NULL;
 160         int *base = NULL;
 161         int *limit = NULL;
 162         int dbufCount, nextSym, dbufSize, groupCount, selector,
 163                 i, j, k, t, runPos, symCount, symTotal, nSelectors, *byteCount;
 164         unsigned char uc, *symToByte, *mtfSymbol, *selectors;
 165         unsigned int *dbuf, origPtr;
 166
 167         dbuf = bd->dbuf;
 168         dbufSize = bd->dbufSize;
 169         selectors = bd->selectors;
 170         byteCount = bd->byteCount;
 171         symToByte = bd->symToByte;
 172         mtfSymbol = bd->mtfSymbol;
 173
 174         /* Read in header signature and CRC, then validate signature.
 175            (last block signature means CRC is for whole file, return now) */
 176         i = get_bits(bd, 24);
 177         j = get_bits(bd, 24);
 178         bd->headerCRC = get_bits(bd, 32);
 179         if ((i == 0x177245) && (j == 0x385090))
 180                 return RETVAL_LAST_BLOCK;
 181         if ((i != 0x314159) || (j != 0x265359))
 182                 return RETVAL_NOT_BZIP_DATA;
 183         /* We can add support for blockRandomised if anybody complains.
 184            There was some code for this in busybox 1.0.0-pre3, but nobody ever
 185            noticed that it didn't actually work. */
 186         if (get_bits(bd, 1))
 187                 return RETVAL_OBSOLETE_INPUT;
 188         origPtr = get_bits(bd, 24);
 189         if (origPtr > dbufSize)
 190                 return RETVAL_DATA_ERROR;
 191         /* mapping table: if some byte values are never used (encoding things
 192            like ascii text), the compression code removes the gaps to have fewer
 193            symbols to deal with, and writes a sparse bitfield indicating which
 194            values were present.  We make a translation table to convert the
 195            symbols back to the corresponding bytes. */
 196         t = get_bits(bd, 16);
 197         symTotal = 0;
 198         for (i = 0; i < 16; i++) {
 199                 if (t&(1 << (15-i))) {
 200                         k = get_bits(bd, 16);
 201                         for (j = 0; j < 16; j++)
 202                                 if (k&(1 << (15-j)))
 203                                         symToByte[symTotal++] = (16*i)+j;
 204                 }
 205         }
 206         /* How many different Huffman coding groups does this block use? */
 207         groupCount = get_bits(bd, 3);
 208         if (groupCount < 2 || groupCount > MAX_GROUPS)
 209                 return RETVAL_DATA_ERROR;
 210         /* nSelectors: Every GROUP_SIZE many symbols we select a new
 211            Huffman coding group.  Read in the group selector list,
 212            which is stored as MTF encoded bit runs.  (MTF = Move To
 213            Front, as each value is used it's moved to the start of the
 214            list.) */
 215         nSelectors = get_bits(bd, 15);
 216         if (!nSelectors)
 217                 return RETVAL_DATA_ERROR;
 218         for (i = 0; i < groupCount; i++)
 219                 mtfSymbol[i] = i;
 220         for (i = 0; i < nSelectors; i++) {
 221                 /* Get next value */
 222                 for (j = 0; get_bits(bd, 1); j++)
 223                         if (j >= groupCount)
 224                                 return RETVAL_DATA_ERROR;
 225                 /* Decode MTF to get the next selector */
 226                 uc = mtfSymbol[j];
 227                 for (; j; j--)
 228                         mtfSymbol[j] = mtfSymbol[j-1];
 229                 mtfSymbol[0] = selectors[i] = uc;
 230         }
 231         /* Read the Huffman coding tables for each group, which code
 232            for symTotal literal symbols, plus two run symbols (RUNA,
 233            RUNB) */
 234         symCount = symTotal+2;
 235         for (j = 0; j < groupCount; j++) {
 236                 unsigned char length[MAX_SYMBOLS], temp[MAX_HUFCODE_BITS+1];
 237                 int     minLen, maxLen, pp;
 238                 /* Read Huffman code lengths for each symbol.  They're
 239                    stored in a way similar to mtf; record a starting
 240                    value for the first symbol, and an offset from the
 241                    previous value for everys symbol after that.
 242                    (Subtracting 1 before the loop and then adding it
 243                    back at the end is an optimization that makes the
 244                    test inside the loop simpler: symbol length 0
 245                    becomes negative, so an unsigned inequality catches
 246                    it.) */
 247                 t = get_bits(bd, 5)-1;
 248                 for (i = 0; i < symCount; i++) {
 249                         for (;;) {
 250                                 if (((unsigned)t) > (MAX_HUFCODE_BITS-1))
 251                                         return RETVAL_DATA_ERROR;
 252
 253                                 /* If first bit is 0, stop.  Else
 254                                    second bit indicates whether to
 255                                    increment or decrement the value.
 256                                    Optimization: grab 2 bits and unget
 257                                    the second if the first was 0. */
 258
 259                                 k = get_bits(bd, 2);
 260                                 if (k < 2) {
 261                                         bd->inbufBitCount++;
 262                                         break;
 263                                 }
 264                                 /* Add one if second bit 1, else
 265                                  * subtract 1.  Avoids if/else */
 266                                 t += (((k+1)&2)-1);
 267                         }
 268                         /* Correct for the initial -1, to get the
 269                          * final symbol length */
 270                         length[i] = t+1;
 271                 }
 272                 /* Find largest and smallest lengths in this group */
 273                 minLen = maxLen = length[0];
 274
 275                 for (i = 1; i < symCount; i++) {
 276                         if (length[i] > maxLen)
 277                                 maxLen = length[i];
 278                         else if (length[i] < minLen)
 279                                 minLen = length[i];
 280                 }
 281
 282                 /* Calculate permute[], base[], and limit[] tables from
 283                  * length[].
 284                  *
 285                  * permute[] is the lookup table for converting
 286                  * Huffman coded symbols into decoded symbols.  base[]
 287                  * is the amount to subtract from the value of a
 288                  * Huffman symbol of a given length when using
 289                  * permute[].
 290                  *
 291                  * limit[] indicates the largest numerical value a
 292                  * symbol with a given number of bits can have.  This
 293                  * is how the Huffman codes can vary in length: each
 294                  * code with a value > limit[length] needs another
 295                  * bit.
 296                  */
 297                 hufGroup = bd->groups+j;
 298                 hufGroup->minLen = minLen;
 299                 hufGroup->maxLen = maxLen;
 300                 /* Note that minLen can't be smaller than 1, so we
 301                    adjust the base and limit array pointers so we're
 302                    not always wasting the first entry.  We do this
 303                    again when using them (during symbol decoding).*/
 304                 base = hufGroup->base-1;
 305                 limit = hufGroup->limit-1;
 306                 /* Calculate permute[].  Concurrently, initialize
 307                  * temp[] and limit[]. */
 308                 pp = 0;
 309                 for (i = minLen; i <= maxLen; i++) {
 310                         temp[i] = limit[i] = 0;
 311                         for (t = 0; t < symCount; t++)
 312                                 if (length[t] == i)
 313                                         hufGroup->permute[pp++] = t;
 314                 }
 315                 /* Count symbols coded for at each bit length */
 316                 for (i = 0; i < symCount; i++)
 317                         temp[length[i]]++;
 318                 /* Calculate limit[] (the largest symbol-coding value
 319                  *at each bit length, which is (previous limit <<
 320                  *1)+symbols at this level), and base[] (number of
 321                  *symbols to ignore at each bit length, which is limit
 322                  *minus the cumulative count of symbols coded for
 323                  *already). */
 324                 pp = t = 0;
 325                 for (i = minLen; i < maxLen; i++) {
 326                         pp += temp[i];
 327                         /* We read the largest possible symbol size
 328                            and then unget bits after determining how
 329                            many we need, and those extra bits could be
 330                            set to anything.  (They're noise from
 331                            future symbols.)  At each level we're
 332                            really only interested in the first few
 333                            bits, so here we set all the trailing
 334                            to-be-ignored bits to 1 so they don't
 335                            affect the value > limit[length]
 336                            comparison. */
 337                         limit[i] = (pp << (maxLen - i)) - 1;
 338                         pp <<= 1;
 339                         base[i+1] = pp-(t += temp[i]);
 340                 }
 341                 limit[maxLen+1] = INT_MAX; /* Sentinal value for
 342                                             * reading next sym. */
 343                 limit[maxLen] = pp+temp[maxLen]-1;
 344                 base[minLen] = 0;
 345         }
 346         /* We've finished reading and digesting the block header.  Now
 347            read this block's Huffman coded symbols from the file and
 348            undo the Huffman coding and run length encoding, saving the
 349            result into dbuf[dbufCount++] = uc */
 350
 351         /* Initialize symbol occurrence counters and symbol Move To
 352          * Front table */
 353         for (i = 0; i < 256; i++) {
 354                 byteCount[i] = 0;
 355                 mtfSymbol[i] = (unsigned char)i;
 356         }
 357         /* Loop through compressed symbols. */
 358         runPos = dbufCount = symCount = selector = 0;
 359         for (;;) {
 360                 /* Determine which Huffman coding group to use. */
 361                 if (!(symCount--)) {
 362                         symCount = GROUP_SIZE-1;
 363                         if (selector >= nSelectors)
 364                                 return RETVAL_DATA_ERROR;
 365                         hufGroup = bd->groups+selectors[selector++];
 366                         base = hufGroup->base-1;
 367                         limit = hufGroup->limit-1;
 368                 }
 369                 /* Read next Huffman-coded symbol. */
 370                 /* Note: It is far cheaper to read maxLen bits and
 371                    back up than it is to read minLen bits and then an
 372                    additional bit at a time, testing as we go.
 373                    Because there is a trailing last block (with file
 374                    CRC), there is no danger of the overread causing an
 375                    unexpected EOF for a valid compressed file.  As a
 376                    further optimization, we do the read inline
 377                    (falling back to a call to get_bits if the buffer
 378                    runs dry).  The following (up to got_huff_bits:) is
 379                    equivalent to j = get_bits(bd, hufGroup->maxLen);
 380                  */
 381                 while (bd->inbufBitCount < hufGroup->maxLen) {
 382                         if (bd->inbufPos == bd->inbufCount) {
 383                                 j = get_bits(bd, hufGroup->maxLen);
 384                                 goto got_huff_bits;
 385                         }
 386                         bd->inbufBits =
 387                                 (bd->inbufBits << 8)|bd->inbuf[bd->inbufPos++];
 388                         bd->inbufBitCount += 8;
 389                 };
 390                 bd->inbufBitCount -= hufGroup->maxLen;
 391                 j = (bd->inbufBits >> bd->inbufBitCount)&
 392                         ((1 << hufGroup->maxLen)-1);
 393 got_huff_bits:
 394                 /* Figure how how many bits are in next symbol and
 395                  * unget extras */
 396                 i = hufGroup->minLen;
 397                 while (j > limit[i])
 398                         ++i;
 399                 bd->inbufBitCount += (hufGroup->maxLen - i);
 400                 /* Huffman decode value to get nextSym (with bounds checking) */
 401                 if ((i > hufGroup->maxLen)
 402                         || (((unsigned)(j = (j>>(hufGroup->maxLen-i))-base[i]))
 403                                 >= MAX_SYMBOLS))
 404                         return RETVAL_DATA_ERROR;
 405                 nextSym = hufGroup->permute[j];
 406                 /* We have now decoded the symbol, which indicates
 407                    either a new literal byte, or a repeated run of the
 408                    most recent literal byte.  First, check if nextSym
 409                    indicates a repeated run, and if so loop collecting
 410                    how many times to repeat the last literal. */
 411                 if (((unsigned)nextSym) <= SYMBOL_RUNB) { /* RUNA or RUNB */
 412                         /* If this is the start of a new run, zero out
 413                          * counter */
 414                         if (!runPos) {
 415                                 runPos = 1;
 416                                 t = 0;
 417                         }
 418                         /* Neat trick that saves 1 symbol: instead of
 419                            or-ing 0 or 1 at each bit position, add 1
 420                            or 2 instead.  For example, 1011 is 1 << 0
 421                            + 1 << 1 + 2 << 2.  1010 is 2 << 0 + 2 << 1
 422                            + 1 << 2.  You can make any bit pattern
 423                            that way using 1 less symbol than the basic
 424                            or 0/1 method (except all bits 0, which
 425                            would use no symbols, but a run of length 0
 426                            doesn't mean anything in this context).
 427                            Thus space is saved. */
 428                         t += (runPos << nextSym);
 429                         /* +runPos if RUNA; +2*runPos if RUNB */
 430
 431                         runPos <<= 1;
 432                         continue;
 433                 }
 434                 /* When we hit the first non-run symbol after a run,
 435                    we now know how many times to repeat the last
 436                    literal, so append that many copies to our buffer
 437                    of decoded symbols (dbuf) now.  (The last literal
 438                    used is the one at the head of the mtfSymbol
 439                    array.) */
 440                 if (runPos) {
 441                         runPos = 0;
 442                         if (dbufCount+t >= dbufSize)
 443                                 return RETVAL_DATA_ERROR;
 444
 445                         uc = symToByte[mtfSymbol[0]];
 446                         byteCount[uc] += t;
 447                         while (t--)
 448                                 dbuf[dbufCount++] = uc;
 449                 }
 450                 /* Is this the terminating symbol? */
 451                 if (nextSym > symTotal)
 452                         break;
 453                 /* At this point, nextSym indicates a new literal
 454                    character.  Subtract one to get the position in the
 455                    MTF array at which this literal is currently to be
 456                    found.  (Note that the result can't be -1 or 0,
 457                    because 0 and 1 are RUNA and RUNB.  But another
 458                    instance of the first symbol in the mtf array,
 459                    position 0, would have been handled as part of a
 460                    run above.  Therefore 1 unused mtf position minus 2
 461                    non-literal nextSym values equals -1.) */
 462                 if (dbufCount >= dbufSize)
 463                         return RETVAL_DATA_ERROR;
 464                 i = nextSym - 1;
 465                 uc = mtfSymbol[i];
 466                 /* Adjust the MTF array.  Since we typically expect to
 467                  *move only a small number of symbols, and are bound
 468                  *by 256 in any case, using memmove here would
 469                  *typically be bigger and slower due to function call
 470                  *overhead and other assorted setup costs. */
 471                 do {
 472                         mtfSymbol[i] = mtfSymbol[i-1];
 473                 } while (--i);
 474                 mtfSymbol[0] = uc;
 475                 uc = symToByte[uc];
 476                 /* We have our literal byte.  Save it into dbuf. */
 477                 byteCount[uc]++;
 478                 dbuf[dbufCount++] = (unsigned int)uc;
 479         }
 480         /* At this point, we've read all the Huffman-coded symbols
 481            (and repeated runs) for this block from the input stream,
 482            and decoded them into the intermediate buffer.  There are
 483            dbufCount many decoded bytes in dbuf[].  Now undo the
 484            Burrows-Wheeler transform on dbuf.  See
 485            http://dogma.net/markn/articles/bwt/bwt.htm
 486          */
 487         /* Turn byteCount into cumulative occurrence counts of 0 to n-1. */
 488         j = 0;
 489         for (i = 0; i < 256; i++) {
 490                 k = j+byteCount[i];
 491                 byteCount[i] = j;
 492                 j = k;
 493         }
 494         /* Figure out what order dbuf would be in if we sorted it. */
 495         for (i = 0; i < dbufCount; i++) {
 496                 uc = (unsigned char)(dbuf[i] & 0xff);
 497                 dbuf[byteCount[uc]] |= (i << 8);
 498                 byteCount[uc]++;
 499         }
 500         /* Decode first byte by hand to initialize "previous" byte.
 501            Note that it doesn't get output, and if the first three
 502            characters are identical it doesn't qualify as a run (hence
 503            writeRunCountdown = 5). */
 504         if (dbufCount) {
 505                 if (origPtr >= dbufCount)
 506                         return RETVAL_DATA_ERROR;
 507                 bd->writePos = dbuf[origPtr];
 508                 bd->writeCurrent = (unsigned char)(bd->writePos&0xff);
 509                 bd->writePos >>= 8;
 510                 bd->writeRunCountdown = 5;
 511         }
 512         bd->writeCount = dbufCount;
 513
 514         return RETVAL_OK;
 515 }
 516
 517 /* Undo burrows-wheeler transform on intermediate buffer to produce output.
 518    If start_bunzip was initialized with out_fd =-1, then up to len bytes of
 519    data are written to outbuf.  Return value is number of bytes written or
 520    error (all errors are negative numbers).  If out_fd!=-1, outbuf and len
 521    are ignored, data is written to out_fd and return is RETVAL_OK or error.
 522 */
 523
 524 static int INIT read_bunzip(struct bunzip_data *bd, char *outbuf, int len)
 525 {
 526         const unsigned int *dbuf;
 527         int pos, xcurrent, previous, gotcount;
 528
 529         /* If last read was short due to end of file, return last block now */
 530         if (bd->writeCount < 0)
 531                 return bd->writeCount;
 532
 533         gotcount = 0;
 534         dbuf = bd->dbuf;
 535         pos = bd->writePos;
 536         xcurrent = bd->writeCurrent;
 537
 538         /* We will always have pending decoded data to write into the output
 539            buffer unless this is the very first call (in which case we haven't
 540            Huffman-decoded a block into the intermediate buffer yet). */
 541
 542         if (bd->writeCopies) {
 543                 /* Inside the loop, writeCopies means extra copies (beyond 1) */
 544                 --bd->writeCopies;
 545                 /* Loop outputting bytes */
 546                 for (;;) {
 547                         /* If the output buffer is full, snapshot
 548                          * state and return */
 549                         if (gotcount >= len) {
 550                                 bd->writePos = pos;
 551                                 bd->writeCurrent = xcurrent;
 552                                 bd->writeCopies++;
 553                                 return len;
 554                         }
 555                         /* Write next byte into output buffer, updating CRC */
 556                         outbuf[gotcount++] = xcurrent;
 557                         bd->writeCRC = (((bd->writeCRC) << 8)
 558                                 ^bd->crc32Table[((bd->writeCRC) >> 24)
 559                                 ^xcurrent]);
 560                         /* Loop now if we're outputting multiple
 561                          * copies of this byte */
 562                         if (bd->writeCopies) {
 563                                 --bd->writeCopies;
 564                                 continue;
 565                         }
 566 decode_next_byte:
 567                         if (!bd->writeCount--)
 568                                 break;
 569                         /* Follow sequence vector to undo
 570                          * Burrows-Wheeler transform */
 571                         previous = xcurrent;
 572                         pos = dbuf[pos];
 573                         xcurrent = pos&0xff;
 574                         pos >>= 8;
 575                         /* After 3 consecutive copies of the same
 576                            byte, the 4th is a repeat count.  We count
 577                            down from 4 instead *of counting up because
 578                            testing for non-zero is faster */
 579                         if (--bd->writeRunCountdown) {
 580                                 if (xcurrent != previous)
 581                                         bd->writeRunCountdown = 4;
 582                         } else {
 583                                 /* We have a repeated run, this byte
 584                                  * indicates the count */
 585                                 bd->writeCopies = xcurrent;
 586                                 xcurrent = previous;
 587                                 bd->writeRunCountdown = 5;
 588                                 /* Sometimes there are just 3 bytes
 589                                  * (run length 0) */
 590                                 if (!bd->writeCopies)
 591                                         goto decode_next_byte;
 592                                 /* Subtract the 1 copy we'd output
 593                                  * anyway to get extras */
 594                                 --bd->writeCopies;
 595                         }
 596                 }
 597                 /* Decompression of this block completed successfully */
 598                 bd->writeCRC = ~bd->writeCRC;
 599                 bd->totalCRC = ((bd->totalCRC << 1) |
 600                                 (bd->totalCRC >> 31)) ^ bd->writeCRC;
 601                 /* If this block had a CRC error, force file level CRC error. */
 602                 if (bd->writeCRC != bd->headerCRC) {
 603                         bd->totalCRC = bd->headerCRC+1;
 604                         return RETVAL_LAST_BLOCK;
 605                 }
 606         }
 607
 608         /* Refill the intermediate buffer by Huffman-decoding next
 609          * block of input */
 610         /* (previous is just a convenient unused temp variable here) */
 611         previous = get_next_block(bd);
 612         if (previous) {
 613                 bd->writeCount = previous;
 614                 return (previous != RETVAL_LAST_BLOCK) ? previous : gotcount;
 615         }
 616         bd->writeCRC = 0xffffffffUL;
 617         pos = bd->writePos;
 618         xcurrent = bd->writeCurrent;
 619         goto decode_next_byte;
 620 }
 621
 622 static int INIT nofill(void *buf, unsigned int len)
 623 {
 624         return -1;
 625 }
 626
 627 /* Allocate the structure, read file header.  If in_fd ==-1, inbuf must contain
 628    a complete bunzip file (len bytes long).  If in_fd!=-1, inbuf and len are
 629    ignored, and data is read from file handle into temporary buffer. */
 630 static int INIT start_bunzip(struct bunzip_data **bdp, void *inbuf, int len,
 631                              int (*fill)(void*, unsigned int))
 632 {
 633         struct bunzip_data *bd;
 634         unsigned int i, j, c;
 635         const unsigned int BZh0 =
 636                 (((unsigned int)'B') << 24)+(((unsigned int)'Z') << 16)
 637                 +(((unsigned int)'h') << 8)+(unsigned int)'0';
 638
 639         /* Figure out how much data to allocate */
 640         i = sizeof(struct bunzip_data);
 641
 642         /* Allocate bunzip_data.  Most fields initialize to zero. */
 643         bd = *bdp = malloc(i);
 644         if (!bd)
 645                 return RETVAL_OUT_OF_MEMORY;
 646         memset(bd, 0, sizeof(struct bunzip_data));
 647         /* Setup input buffer */
 648         bd->inbuf = inbuf;
 649         bd->inbufCount = len;
 650         if (fill != NULL)
 651                 bd->fill = fill;
 652         else
 653                 bd->fill = nofill;
 654
 655         /* Init the CRC32 table (big endian) */
 656         for (i = 0; i < 256; i++) {
 657                 c = i << 24;
 658                 for (j = 8; j; j--)
 659                         c = c&0x80000000 ? (c << 1)^0x04c11db7 : (c << 1);
 660                 bd->crc32Table[i] = c;
 661         }
 662
 663         /* Ensure that file starts with "BZh['1'-'9']." */
 664         i = get_bits(bd, 32);
 665         if (((unsigned int)(i-BZh0-1)) >= 9)
 666                 return RETVAL_NOT_BZIP_DATA;
 667
 668         /* Fourth byte (ascii '1'-'9'), indicates block size in units of 100k of
 669            uncompressed data.  Allocate intermediate buffer for block. */
 670         bd->dbufSize = 100000*(i-BZh0);
 671
 672         bd->dbuf = large_malloc(bd->dbufSize * sizeof(int));
 673         if (!bd->dbuf)
 674                 return RETVAL_OUT_OF_MEMORY;
 675         return RETVAL_OK;
 676 }
 677
 678 /* Example usage: decompress src_fd to dst_fd.  (Stops at end of bzip2 data,
 679    not end of file.) */
 680 STATIC int INIT bunzip2(unsigned char *buf, int len,
 681                         int(*fill)(void*, unsigned int),
 682                         int(*flush)(void*, unsigned int),
 683                         unsigned char *outbuf,
 684                         int *pos,
 685                         void(*error_fn)(char *x))
 686 {
 687         struct bunzip_data *bd;
 688         int i = -1;
 689         unsigned char *inbuf;
 690
 691         set_error_fn(error_fn);
 692         if (flush)
 693                 outbuf = malloc(BZIP2_IOBUF_SIZE);
 694
 695         if (!outbuf) {
 696                 error("Could not allocate output bufer");
 697                 return RETVAL_OUT_OF_MEMORY;
 698         }
 699         if (buf)
 700                 inbuf = buf;
 701         else
 702                 inbuf = malloc(BZIP2_IOBUF_SIZE);
 703         if (!inbuf) {
 704                 error("Could not allocate input bufer");
 705                 i = RETVAL_OUT_OF_MEMORY;
 706                 goto exit_0;
 707         }
 708         i = start_bunzip(&bd, inbuf, len, fill);
 709         if (!i) {
 710                 for (;;) {
 711                         i = read_bunzip(bd, outbuf, BZIP2_IOBUF_SIZE);
 712                         if (i <= 0)
 713                                 break;
 714                         if (!flush)
 715                                 outbuf += i;
 716                         else
 717                                 if (i != flush(outbuf, i)) {
 718                                         i = RETVAL_UNEXPECTED_OUTPUT_EOF;
 719                                         break;
 720                                 }
 721                 }
 722         }
 723         /* Check CRC and release memory */
 724         if (i == RETVAL_LAST_BLOCK) {
 725                 if (bd->headerCRC != bd->totalCRC)
 726                         error("Data integrity error when decompressing.");
 727                 else
 728                         i = RETVAL_OK;
 729         } else if (i == RETVAL_UNEXPECTED_OUTPUT_EOF) {
 730                 error("Compressed file ends unexpectedly");
 731         }
 732         if (!bd)
 733                 goto exit_1;
 734         if (bd->dbuf)
 735                 large_free(bd->dbuf);
 736         if (pos)
 737                 *pos = bd->inbufPos;
 738         free(bd);
 739 exit_1:
 740         if (!buf)
 741                 free(inbuf);
 742 exit_0:
 743         if (flush)
 744                 free(outbuf);
 745         return i;
 746 }
 747
 748 #ifdef PREBOOT
 749 STATIC int INIT decompress(unsigned char *buf, int len,
 750                         int(*fill)(void*, unsigned int),
 751                         int(*flush)(void*, unsigned int),
 752                         unsigned char *outbuf,
 753                         int *pos,
 754                         void(*error_fn)(char *x))
 755 {
 756         return bunzip2(buf, len - 4, fill, flush, outbuf, pos, error_fn);
 757 }
 758 #endif