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