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