bzip2: Add missing checks for malloc returning NULL
[linux-3.10.git] / 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 };
111
112
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)
116 {
117         unsigned int bits = 0;
118
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;
132                         }
133                         bd->inbufPos = 0;
134                 }
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;
141                 }
142                 /* Grab next 8 bits of input from buffer. */
143                 bd->inbufBits = (bd->inbufBits << 8)|bd->inbuf[bd->inbufPos++];
144                 bd->inbufBitCount += 8;
145         }
146         /* Calculate result */
147         bd->inbufBitCount -= bits_wanted;
148         bits |= (bd->inbufBits >> bd->inbufBitCount)&((1 << bits_wanted)-1);
149
150         return bits;
151 }
152
153 /* Unpacks the next block and sets up for the inverse burrows-wheeler step. */
154
155 static int INIT get_next_block(struct bunzip_data *bd)
156 {
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;
165
166         dbuf = bd->dbuf;
167         dbufSize = bd->dbufSize;
168         selectors = bd->selectors;
169
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;
200                 }
201         }
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;
226         }
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;
248
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. */
254
255                                 k = get_bits(bd, 2);
256                                 if (k < 2) {
257                                         bd->inbufBitCount++;
258                                         break;
259                                 }
260                                 /* Add one if second bit 1, else
261                                  * subtract 1.  Avoids if/else */
262                                 t += (((k+1)&2)-1);
263                         }
264                         /* Correct for the initial -1, to get the
265                          * final symbol length */
266                         length[i] = t+1;
267                 }
268                 /* Find largest and smallest lengths in this group */
269                 minLen = maxLen = length[0];
270
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];
276                 }
277
278                 /* Calculate permute[], base[], and limit[] tables from
279                  * length[].
280                  *
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[].
286                  *
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.
292                  */
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;
310                 }
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]);
336                 }
337                 limit[maxLen+1] = INT_MAX; /* Sentinal value for
338                                             * reading next sym. */
339                 limit[maxLen] = pp+temp[maxLen]-1;
340                 base[minLen] = 0;
341         }
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 */
346
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;
352         }
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;
364                 }
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);
376                  */
377                 while (bd->inbufBitCount < hufGroup->maxLen) {
378                         if (bd->inbufPos == bd->inbufCount) {
379                                 j = get_bits(bd, hufGroup->maxLen);
380                                 goto got_huff_bits;
381                         }
382                         bd->inbufBits =
383                                 (bd->inbufBits << 8)|bd->inbuf[bd->inbufPos++];
384                         bd->inbufBitCount += 8;
385                 };
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;
413                         }
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 */
426
427                         runPos <<= 1;
428                         continue;
429                 }
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;
440
441                         uc = symToByte[mtfSymbol[0]];
442                         byteCount[uc] += t;
443                         while (t--)
444                                 dbuf[dbufCount++] = uc;
445                 }
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;
475         }
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
482          */
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;
489         }
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]++;
495         }
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;
507         }
508         bd->writeCount = dbufCount;
509
510         return RETVAL_OK;
511 }
512
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.
518 */
519
520 static int INIT read_bunzip(struct bunzip_data *bd, char *outbuf, int len)
521 {
522         const unsigned int *dbuf;
523         int pos, xcurrent, previous, gotcount;
524
525         /* If last read was short due to end of file, return last block now */
526         if (bd->writeCount < 0)
527                 return bd->writeCount;
528
529         gotcount = 0;
530         dbuf = bd->dbuf;
531         pos = bd->writePos;
532         xcurrent = bd->writeCurrent;
533
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). */
537
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;
550                         }
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;
561                         }
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;
591                         }
592                 }
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;
601                 }
602         }
603
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;
611         }
612         bd->writeCRC = 0xffffffffUL;
613         pos = bd->writePos;
614         xcurrent = bd->writeCurrent;
615         goto decode_next_byte;
616 }
617
618 static int INIT nofill(void *buf, unsigned int len)
619 {
620         return -1;
621 }
622
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))
628 {
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';
634
635         /* Figure out how much data to allocate */
636         i = sizeof(struct bunzip_data);
637
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;
650
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;
657         }
658
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;
663
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);
667
668         bd->dbuf = large_malloc(bd->dbufSize * sizeof(int));
669         if (!bd->dbuf)
670                 return RETVAL_OUT_OF_MEMORY;
671         return RETVAL_OK;
672 }
673
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))
682 {
683         struct bunzip_data *bd;
684         int i = -1;
685         unsigned char *inbuf;
686
687         set_error_fn(error_fn);
688         if (flush)
689                 outbuf = malloc(BZIP2_IOBUF_SIZE);
690
691         if (!outbuf) {
692                 error("Could not allocate output bufer");
693                 return RETVAL_OUT_OF_MEMORY;
694         }
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;
703         }
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;
716                                 }
717                 }
718         }
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");
727         }
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;
742 }
743
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))
751 {
752         return bunzip2(buf, len - 4, fill, flush, outbuf, pos, error_fn);
753 }
754 #endif