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