758 lines · c
1/* Small bzip2 deflate implementation, by Rob Landley (rob@landley.net).2 3 Based on bzip2 decompression code by Julian R Seward (jseward@acm.org),4 which also acknowledges contributions by Mike Burrows, David Wheeler,5 Peter Fenwick, Alistair Moffat, Radford Neal, Ian H. Witten,6 Robert Sedgewick, and Jon L. Bentley.7 8 This code is licensed under the LGPLv2:9 LGPL (http://www.gnu.org/copyleft/lgpl.html10*/11 12/*13 Size and speed optimizations by Manuel Novoa III (mjn3@codepoet.org).14 15 More efficient reading of Huffman codes, a streamlined read_bunzip()16 function, and various other tweaks. In (limited) tests, approximately17 20% faster than bzcat on x86 and about 10% faster on arm.18 19 Note that about 2/3 of the time is spent in read_unzip() reversing20 the Burrows-Wheeler transformation. Much of that time is delay21 resulting from cache misses.22 23 I would ask that anyone benefiting from this work, especially those24 using it in commercial products, consider making a donation to my local25 non-profit hospice organization in the name of the woman I loved, who26 passed away Feb. 12, 2003.27 28 In memory of Toni W. Hagan29 30 Hospice of Acadiana, Inc.31 2600 Johnston St., Suite 20032 Lafayette, LA 70503-324033 34 Phone (337) 232-1234 or 1-800-738-222635 Fax (337) 232-129736 37 https://www.hospiceacadiana.com/38 39 Manuel40 */41 42/*43 Made it fit for running in Linux Kernel by Alain Knaff (alain@knaff.lu)44*/45 46 47#ifdef STATIC48#define PREBOOT49#else50#include <linux/decompress/bunzip2.h>51#endif /* STATIC */52 53#include <linux/decompress/mm.h>54#include <linux/crc32poly.h>55 56#ifndef INT_MAX57#define INT_MAX 0x7fffffff58#endif59 60/* Constants for Huffman coding */61#define MAX_GROUPS 662#define GROUP_SIZE 50 /* 64 would have been more efficient */63#define MAX_HUFCODE_BITS 20 /* Longest Huffman code allowed */64#define MAX_SYMBOLS 258 /* 256 literals + RUNA + RUNB */65#define SYMBOL_RUNA 066#define SYMBOL_RUNB 167 68/* Status return values */69#define RETVAL_OK 070#define RETVAL_LAST_BLOCK (-1)71#define RETVAL_NOT_BZIP_DATA (-2)72#define RETVAL_UNEXPECTED_INPUT_EOF (-3)73#define RETVAL_UNEXPECTED_OUTPUT_EOF (-4)74#define RETVAL_DATA_ERROR (-5)75#define RETVAL_OUT_OF_MEMORY (-6)76#define RETVAL_OBSOLETE_INPUT (-7)77 78/* Other housekeeping constants */79#define BZIP2_IOBUF_SIZE 409680 81/* This is what we know about each Huffman coding group */82struct group_data {83 /* We have an extra slot at the end of limit[] for a sentinel value. */84 int limit[MAX_HUFCODE_BITS+1];85 int base[MAX_HUFCODE_BITS];86 int permute[MAX_SYMBOLS];87 int minLen, maxLen;88};89 90/* Structure holding all the housekeeping data, including IO buffers and91 memory that persists between calls to bunzip */92struct bunzip_data {93 /* State for interrupting output loop */94 int writeCopies, writePos, writeRunCountdown, writeCount, writeCurrent;95 /* I/O tracking data (file handles, buffers, positions, etc.) */96 long (*fill)(void*, unsigned long);97 long inbufCount, inbufPos /*, outbufPos*/;98 unsigned char *inbuf /*,*outbuf*/;99 unsigned int inbufBitCount, inbufBits;100 /* The CRC values stored in the block header and calculated from the101 data */102 unsigned int crc32Table[256], headerCRC, totalCRC, writeCRC;103 /* Intermediate buffer and its size (in bytes) */104 unsigned int *dbuf, dbufSize;105 /* These things are a bit too big to go on the stack */106 unsigned char selectors[32768]; /* nSelectors = 15 bits */107 struct group_data groups[MAX_GROUPS]; /* Huffman coding tables */108 int io_error; /* non-zero if we have IO error */109 int byteCount[256];110 unsigned char symToByte[256], mtfSymbol[256];111};112 113 114/* Return the next nnn bits of input. All reads from the compressed input115 are done through this function. All reads are big endian */116static unsigned int INIT get_bits(struct bunzip_data *bd, char bits_wanted)117{118 unsigned int bits = 0;119 120 /* If we need to get more data from the byte buffer, do so.121 (Loop getting one byte at a time to enforce endianness and avoid122 unaligned access.) */123 while (bd->inbufBitCount < bits_wanted) {124 /* If we need to read more data from file into byte buffer, do125 so */126 if (bd->inbufPos == bd->inbufCount) {127 if (bd->io_error)128 return 0;129 bd->inbufCount = bd->fill(bd->inbuf, BZIP2_IOBUF_SIZE);130 if (bd->inbufCount <= 0) {131 bd->io_error = RETVAL_UNEXPECTED_INPUT_EOF;132 return 0;133 }134 bd->inbufPos = 0;135 }136 /* Avoid 32-bit overflow (dump bit buffer to top of output) */137 if (bd->inbufBitCount >= 24) {138 bits = bd->inbufBits&((1 << bd->inbufBitCount)-1);139 bits_wanted -= bd->inbufBitCount;140 bits <<= bits_wanted;141 bd->inbufBitCount = 0;142 }143 /* Grab next 8 bits of input from buffer. */144 bd->inbufBits = (bd->inbufBits << 8)|bd->inbuf[bd->inbufPos++];145 bd->inbufBitCount += 8;146 }147 /* Calculate result */148 bd->inbufBitCount -= bits_wanted;149 bits |= (bd->inbufBits >> bd->inbufBitCount)&((1 << bits_wanted)-1);150 151 return bits;152}153 154/* Unpacks the next block and sets up for the inverse burrows-wheeler step. */155 156static int INIT get_next_block(struct bunzip_data *bd)157{158 struct group_data *hufGroup = NULL;159 int *base = NULL;160 int *limit = NULL;161 int dbufCount, nextSym, dbufSize, groupCount, selector,162 i, j, k, t, runPos, symCount, symTotal, nSelectors, *byteCount;163 unsigned char uc, *symToByte, *mtfSymbol, *selectors;164 unsigned int *dbuf, origPtr;165 166 dbuf = bd->dbuf;167 dbufSize = bd->dbufSize;168 selectors = bd->selectors;169 byteCount = bd->byteCount;170 symToByte = bd->symToByte;171 mtfSymbol = bd->mtfSymbol;172 173 /* Read in header signature and CRC, then validate signature.174 (last block signature means CRC is for whole file, return now) */175 i = get_bits(bd, 24);176 j = get_bits(bd, 24);177 bd->headerCRC = get_bits(bd, 32);178 if ((i == 0x177245) && (j == 0x385090))179 return RETVAL_LAST_BLOCK;180 if ((i != 0x314159) || (j != 0x265359))181 return RETVAL_NOT_BZIP_DATA;182 /* We can add support for blockRandomised if anybody complains.183 There was some code for this in busybox 1.0.0-pre3, but nobody ever184 noticed that it didn't actually work. */185 if (get_bits(bd, 1))186 return RETVAL_OBSOLETE_INPUT;187 origPtr = get_bits(bd, 24);188 if (origPtr >= dbufSize)189 return RETVAL_DATA_ERROR;190 /* mapping table: if some byte values are never used (encoding things191 like ascii text), the compression code removes the gaps to have fewer192 symbols to deal with, and writes a sparse bitfield indicating which193 values were present. We make a translation table to convert the194 symbols back to the corresponding bytes. */195 t = get_bits(bd, 16);196 symTotal = 0;197 for (i = 0; i < 16; i++) {198 if (t&(1 << (15-i))) {199 k = get_bits(bd, 16);200 for (j = 0; j < 16; j++)201 if (k&(1 << (15-j)))202 symToByte[symTotal++] = (16*i)+j;203 }204 }205 /* How many different Huffman coding groups does this block use? */206 groupCount = get_bits(bd, 3);207 if (groupCount < 2 || groupCount > MAX_GROUPS)208 return RETVAL_DATA_ERROR;209 /* nSelectors: Every GROUP_SIZE many symbols we select a new210 Huffman coding group. Read in the group selector list,211 which is stored as MTF encoded bit runs. (MTF = Move To212 Front, as each value is used it's moved to the start of the213 list.) */214 nSelectors = get_bits(bd, 15);215 if (!nSelectors)216 return RETVAL_DATA_ERROR;217 for (i = 0; i < groupCount; i++)218 mtfSymbol[i] = i;219 for (i = 0; i < nSelectors; i++) {220 /* Get next value */221 for (j = 0; get_bits(bd, 1); j++)222 if (j >= groupCount)223 return RETVAL_DATA_ERROR;224 /* Decode MTF to get the next selector */225 uc = mtfSymbol[j];226 for (; j; j--)227 mtfSymbol[j] = mtfSymbol[j-1];228 mtfSymbol[0] = selectors[i] = uc;229 }230 /* Read the Huffman coding tables for each group, which code231 for symTotal literal symbols, plus two run symbols (RUNA,232 RUNB) */233 symCount = symTotal+2;234 for (j = 0; j < groupCount; j++) {235 unsigned char length[MAX_SYMBOLS];236 unsigned short temp[MAX_HUFCODE_BITS+1];237 int minLen, maxLen, pp;238 /* Read Huffman code lengths for each symbol. They're239 stored in a way similar to mtf; record a starting240 value for the first symbol, and an offset from the241 previous value for everys symbol after that.242 (Subtracting 1 before the loop and then adding it243 back at the end is an optimization that makes the244 test inside the loop simpler: symbol length 0245 becomes negative, so an unsigned inequality catches246 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. Else254 second bit indicates whether to255 increment or decrement the value.256 Optimization: grab 2 bits and unget257 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, else265 * subtract 1. Avoids if/else */266 t += (((k+1)&2)-1);267 }268 /* Correct for the initial -1, to get the269 * 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 from283 * length[].284 *285 * permute[] is the lookup table for converting286 * Huffman coded symbols into decoded symbols. base[]287 * is the amount to subtract from the value of a288 * Huffman symbol of a given length when using289 * permute[].290 *291 * limit[] indicates the largest numerical value a292 * symbol with a given number of bits can have. This293 * is how the Huffman codes can vary in length: each294 * code with a value > limit[length] needs another295 * 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 we301 adjust the base and limit array pointers so we're302 not always wasting the first entry. We do this303 again when using them (during symbol decoding).*/304 base = hufGroup->base-1;305 limit = hufGroup->limit-1;306 /* Calculate permute[]. Concurrently, initialize307 * 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 value319 *at each bit length, which is (previous limit <<320 *1)+symbols at this level), and base[] (number of321 *symbols to ignore at each bit length, which is limit322 *minus the cumulative count of symbols coded for323 *already). */324 pp = t = 0;325 for (i = minLen; i < maxLen; i++) {326 pp += temp[i];327 /* We read the largest possible symbol size328 and then unget bits after determining how329 many we need, and those extra bits could be330 set to anything. (They're noise from331 future symbols.) At each level we're332 really only interested in the first few333 bits, so here we set all the trailing334 to-be-ignored bits to 1 so they don't335 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; /* Sentinel value for342 * 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. Now347 read this block's Huffman coded symbols from the file and348 undo the Huffman coding and run length encoding, saving the349 result into dbuf[dbufCount++] = uc */350 351 /* Initialize symbol occurrence counters and symbol Move To352 * 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 and371 back up than it is to read minLen bits and then an372 additional bit at a time, testing as we go.373 Because there is a trailing last block (with file374 CRC), there is no danger of the overread causing an375 unexpected EOF for a valid compressed file. As a376 further optimization, we do the read inline377 (falling back to a call to get_bits if the buffer378 runs dry). The following (up to got_huff_bits:) is379 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);393got_huff_bits:394 /* Figure how many bits are in next symbol and395 * 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 indicates407 either a new literal byte, or a repeated run of the408 most recent literal byte. First, check if nextSym409 indicates a repeated run, and if so loop collecting410 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 out413 * counter */414 if (!runPos) {415 runPos = 1;416 t = 0;417 }418 /* Neat trick that saves 1 symbol: instead of419 or-ing 0 or 1 at each bit position, add 1420 or 2 instead. For example, 1011 is 1 << 0421 + 1 << 1 + 2 << 2. 1010 is 2 << 0 + 2 << 1422 + 1 << 2. You can make any bit pattern423 that way using 1 less symbol than the basic424 or 0/1 method (except all bits 0, which425 would use no symbols, but a run of length 0426 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 last436 literal, so append that many copies to our buffer437 of decoded symbols (dbuf) now. (The last literal438 used is the one at the head of the mtfSymbol439 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 literal454 character. Subtract one to get the position in the455 MTF array at which this literal is currently to be456 found. (Note that the result can't be -1 or 0,457 because 0 and 1 are RUNA and RUNB. But another458 instance of the first symbol in the mtf array,459 position 0, would have been handled as part of a460 run above. Therefore 1 unused mtf position minus 2461 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 to467 *move only a small number of symbols, and are bound468 *by 256 in any case, using memmove here would469 *typically be bigger and slower due to function call470 *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 symbols481 (and repeated runs) for this block from the input stream,482 and decoded them into the intermediate buffer. There are483 dbufCount many decoded bytes in dbuf[]. Now undo the484 Burrows-Wheeler transform on dbuf. See485 http://dogma.net/markn/articles/bwt/bwt.htm486 */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 three502 characters are identical it doesn't qualify as a run (hence503 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 of519 data are written to outbuf. Return value is number of bytes written or520 error (all errors are negative numbers). If out_fd!=-1, outbuf and len521 are ignored, data is written to out_fd and return is RETVAL_OK or error.522*/523 524static 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 output539 buffer unless this is the very first call (in which case we haven't540 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, snapshot548 * 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 multiple561 * copies of this byte */562 if (bd->writeCopies) {563 --bd->writeCopies;564 continue;565 }566decode_next_byte:567 if (!bd->writeCount--)568 break;569 /* Follow sequence vector to undo570 * Burrows-Wheeler transform */571 previous = xcurrent;572 pos = dbuf[pos];573 xcurrent = pos&0xff;574 pos >>= 8;575 /* After 3 consecutive copies of the same576 byte, the 4th is a repeat count. We count577 down from 4 instead *of counting up because578 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 byte584 * indicates the count */585 bd->writeCopies = xcurrent;586 xcurrent = previous;587 bd->writeRunCountdown = 5;588 /* Sometimes there are just 3 bytes589 * (run length 0) */590 if (!bd->writeCopies)591 goto decode_next_byte;592 /* Subtract the 1 copy we'd output593 * 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 next609 * 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 622static long INIT nofill(void *buf, unsigned long len)623{624 return -1;625}626 627/* Allocate the structure, read file header. If in_fd ==-1, inbuf must contain628 a complete bunzip file (len bytes long). If in_fd!=-1, inbuf and len are629 ignored, and data is read from file handle into temporary buffer. */630static int INIT start_bunzip(struct bunzip_data **bdp, void *inbuf, long len,631 long (*fill)(void*, unsigned long))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 else653 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)^(CRC32_POLY_BE) : (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 of669 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.) */680STATIC int INIT bunzip2(unsigned char *buf, long len,681 long (*fill)(void*, unsigned long),682 long (*flush)(void*, unsigned long),683 unsigned char *outbuf,684 long *pos,685 void(*error)(char *x))686{687 struct bunzip_data *bd;688 int i = -1;689 unsigned char *inbuf;690 691 if (flush)692 outbuf = malloc(BZIP2_IOBUF_SIZE);693 694 if (!outbuf) {695 error("Could not allocate output buffer");696 return RETVAL_OUT_OF_MEMORY;697 }698 if (buf)699 inbuf = buf;700 else701 inbuf = malloc(BZIP2_IOBUF_SIZE);702 if (!inbuf) {703 error("Could not allocate input buffer");704 i = RETVAL_OUT_OF_MEMORY;705 goto exit_0;706 }707 i = start_bunzip(&bd, inbuf, len, fill);708 if (!i) {709 for (;;) {710 i = read_bunzip(bd, outbuf, BZIP2_IOBUF_SIZE);711 if (i <= 0)712 break;713 if (!flush)714 outbuf += i;715 else716 if (i != flush(outbuf, i)) {717 i = RETVAL_UNEXPECTED_OUTPUT_EOF;718 break;719 }720 }721 }722 /* Check CRC and release memory */723 if (i == RETVAL_LAST_BLOCK) {724 if (bd->headerCRC != bd->totalCRC)725 error("Data integrity error when decompressing.");726 else727 i = RETVAL_OK;728 } else if (i == RETVAL_UNEXPECTED_OUTPUT_EOF) {729 error("Compressed file ends unexpectedly");730 }731 if (!bd)732 goto exit_1;733 if (bd->dbuf)734 large_free(bd->dbuf);735 if (pos)736 *pos = bd->inbufPos;737 free(bd);738exit_1:739 if (!buf)740 free(inbuf);741exit_0:742 if (flush)743 free(outbuf);744 return i;745}746 747#ifdef PREBOOT748STATIC int INIT __decompress(unsigned char *buf, long len,749 long (*fill)(void*, unsigned long),750 long (*flush)(void*, unsigned long),751 unsigned char *outbuf, long olen,752 long *pos,753 void (*error)(char *x))754{755 return bunzip2(buf, len - 4, fill, flush, outbuf, pos, error);756}757#endif758