source: branches/3.2/mindi-busybox/archival/libarchive/decompress_bunzip2.c @ 3232

Last change on this file since 3232 was 3232, checked in by bruno, 5 years ago
  • Update mindi-busybox to 1.21.1
  • Property svn:eol-style set to native
File size: 26.5 KB
Line 
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   Licensed under GPLv2 or later, see file LICENSE in this source tree.
10*/
11
12/*
13    Size and speed optimizations by Manuel Novoa III  (mjn3@codepoet.org).
14
15    More efficient reading of Huffman codes, a streamlined read_bunzip()
16    function, and various other tweaks.  In (limited) tests, approximately
17    20% faster than bzcat on x86 and about 10% faster on arm.
18
19    Note that about 2/3 of the time is spent in read_bunzip() reversing
20    the Burrows-Wheeler transformation.  Much of that time is delay
21    resulting from cache misses.
22
23    (2010 update by vda: profiled "bzcat <84mbyte.bz2 >/dev/null"
24    on x86-64 CPU with L2 > 1M: get_next_block is hotter than read_bunzip:
25    %time seconds   calls function
26    71.01   12.69     444 get_next_block
27    28.65    5.12   93065 read_bunzip
28    00.22    0.04 7736490 get_bits
29    00.11    0.02      47 dealloc_bunzip
30    00.00    0.00   93018 full_write
31    ...)
32
33
34    I would ask that anyone benefiting from this work, especially those
35    using it in commercial products, consider making a donation to my local
36    non-profit hospice organization (www.hospiceacadiana.com) in the name of
37    the woman I loved, Toni W. Hagan, who passed away Feb. 12, 2003.
38
39    Manuel
40 */
41
42#include "libbb.h"
43#include "bb_archive.h"
44
45/* Constants for Huffman coding */
46#define MAX_GROUPS          6
47#define GROUP_SIZE          50      /* 64 would have been more efficient */
48#define MAX_HUFCODE_BITS    20      /* Longest Huffman code allowed */
49#define MAX_SYMBOLS         258     /* 256 literals + RUNA + RUNB */
50#define SYMBOL_RUNA         0
51#define SYMBOL_RUNB         1
52
53/* Status return values */
54#define RETVAL_OK                       0
55#define RETVAL_LAST_BLOCK               (-1)
56#define RETVAL_NOT_BZIP_DATA            (-2)
57#define RETVAL_UNEXPECTED_INPUT_EOF     (-3)
58#define RETVAL_SHORT_WRITE              (-4)
59#define RETVAL_DATA_ERROR               (-5)
60#define RETVAL_OUT_OF_MEMORY            (-6)
61#define RETVAL_OBSOLETE_INPUT           (-7)
62
63/* Other housekeeping constants */
64#define IOBUF_SIZE          4096
65
66/* This is what we know about each Huffman coding group */
67struct group_data {
68    /* We have an extra slot at the end of limit[] for a sentinel value. */
69    int limit[MAX_HUFCODE_BITS+1], base[MAX_HUFCODE_BITS], permute[MAX_SYMBOLS];
70    int minLen, maxLen;
71};
72
73/* Structure holding all the housekeeping data, including IO buffers and
74 * memory that persists between calls to bunzip
75 * Found the most used member:
76 *  cat this_file.c | sed -e 's/"/ /g' -e "s/'/ /g" | xargs -n1 \
77 *  | grep 'bd->' | sed 's/^.*bd->/bd->/' | sort | $PAGER
78 * and moved it (inbufBitCount) to offset 0.
79 */
80struct bunzip_data {
81    /* I/O tracking data (file handles, buffers, positions, etc.) */
82    unsigned inbufBitCount, inbufBits;
83    int in_fd, out_fd, inbufCount, inbufPos /*, outbufPos*/;
84    uint8_t *inbuf /*,*outbuf*/;
85
86    /* State for interrupting output loop */
87    int writeCopies, writePos, writeRunCountdown, writeCount;
88    int writeCurrent; /* actually a uint8_t */
89
90    /* The CRC values stored in the block header and calculated from the data */
91    uint32_t headerCRC, totalCRC, writeCRC;
92
93    /* Intermediate buffer and its size (in bytes) */
94    uint32_t *dbuf;
95    unsigned dbufSize;
96
97    /* For I/O error handling */
98    jmp_buf jmpbuf;
99
100    /* Big things go last (register-relative addressing can be larger for big offsets) */
101    uint32_t crc32Table[256];
102    uint8_t selectors[32768];  /* nSelectors=15 bits */
103    struct group_data groups[MAX_GROUPS];  /* Huffman coding tables */
104};
105/* typedef struct bunzip_data bunzip_data; -- done in .h file */
106
107
108/* Return the next nnn bits of input.  All reads from the compressed input
109   are done through this function.  All reads are big endian */
110static unsigned get_bits(bunzip_data *bd, int bits_wanted)
111{
112    unsigned bits = 0;
113    /* Cache bd->inbufBitCount in a CPU register (hopefully): */
114    int bit_count = bd->inbufBitCount;
115
116    /* If we need to get more data from the byte buffer, do so.  (Loop getting
117       one byte at a time to enforce endianness and avoid unaligned access.) */
118    while (bit_count < bits_wanted) {
119
120        /* If we need to read more data from file into byte buffer, do so */
121        if (bd->inbufPos == bd->inbufCount) {
122            /* if "no input fd" case: in_fd == -1, read fails, we jump */
123            bd->inbufCount = read(bd->in_fd, bd->inbuf, IOBUF_SIZE);
124            if (bd->inbufCount <= 0)
125                longjmp(bd->jmpbuf, RETVAL_UNEXPECTED_INPUT_EOF);
126            bd->inbufPos = 0;
127        }
128
129        /* Avoid 32-bit overflow (dump bit buffer to top of output) */
130        if (bit_count >= 24) {
131            bits = bd->inbufBits & ((1 << bit_count) - 1);
132            bits_wanted -= bit_count;
133            bits <<= bits_wanted;
134            bit_count = 0;
135        }
136
137        /* Grab next 8 bits of input from buffer. */
138        bd->inbufBits = (bd->inbufBits << 8) | bd->inbuf[bd->inbufPos++];
139        bit_count += 8;
140    }
141
142    /* Calculate result */
143    bit_count -= bits_wanted;
144    bd->inbufBitCount = bit_count;
145    bits |= (bd->inbufBits >> bit_count) & ((1 << bits_wanted) - 1);
146
147    return bits;
148}
149
150/* Unpacks the next block and sets up for the inverse Burrows-Wheeler step. */
151static int get_next_block(bunzip_data *bd)
152{
153    struct group_data *hufGroup;
154    int dbufCount, dbufSize, groupCount, *base, *limit, selector,
155        i, j, t, runPos, symCount, symTotal, nSelectors, byteCount[256];
156    int runCnt = runCnt; /* for compiler */
157    uint8_t uc, symToByte[256], mtfSymbol[256], *selectors;
158    uint32_t *dbuf;
159    unsigned origPtr;
160
161    dbuf = bd->dbuf;
162    dbufSize = bd->dbufSize;
163    selectors = bd->selectors;
164
165/* In bbox, we are ok with aborting through setjmp which is set up in start_bunzip */
166#if 0
167    /* Reset longjmp I/O error handling */
168    i = setjmp(bd->jmpbuf);
169    if (i) return i;
170#endif
171
172    /* Read in header signature and CRC, then validate signature.
173       (last block signature means CRC is for whole file, return now) */
174    i = get_bits(bd, 24);
175    j = get_bits(bd, 24);
176    bd->headerCRC = get_bits(bd, 32);
177    if ((i == 0x177245) && (j == 0x385090)) return RETVAL_LAST_BLOCK;
178    if ((i != 0x314159) || (j != 0x265359)) return RETVAL_NOT_BZIP_DATA;
179
180    /* We can add support for blockRandomised if anybody complains.  There was
181       some code for this in busybox 1.0.0-pre3, but nobody ever noticed that
182       it didn't actually work. */
183    if (get_bits(bd, 1)) return RETVAL_OBSOLETE_INPUT;
184    origPtr = get_bits(bd, 24);
185    if ((int)origPtr > dbufSize) return RETVAL_DATA_ERROR;
186
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 symbols
191       back to the corresponding bytes. */
192    symTotal = 0;
193    i = 0;
194    t = get_bits(bd, 16);
195    do {
196        if (t & (1 << 15)) {
197            unsigned inner_map = get_bits(bd, 16);
198            do {
199                if (inner_map & (1 << 15))
200                    symToByte[symTotal++] = i;
201                inner_map <<= 1;
202                i++;
203            } while (i & 15);
204            i -= 16;
205        }
206        t <<= 1;
207        i += 16;
208    } while (i < 256);
209
210    /* How many different Huffman coding groups does this block use? */
211    groupCount = get_bits(bd, 3);
212    if (groupCount < 2 || groupCount > MAX_GROUPS)
213        return RETVAL_DATA_ERROR;
214
215    /* nSelectors: Every GROUP_SIZE many symbols we select a new Huffman coding
216       group.  Read in the group selector list, which is stored as MTF encoded
217       bit runs.  (MTF=Move To Front, as each value is used it's moved to the
218       start of the list.) */
219    for (i = 0; i < groupCount; i++)
220        mtfSymbol[i] = i;
221    nSelectors = get_bits(bd, 15);
222    if (!nSelectors)
223        return RETVAL_DATA_ERROR;
224    for (i = 0; i < nSelectors; i++) {
225        uint8_t tmp_byte;
226        /* Get next value */
227        int n = 0;
228        while (get_bits(bd, 1)) {
229            if (n >= groupCount) return RETVAL_DATA_ERROR;
230            n++;
231        }
232        /* Decode MTF to get the next selector */
233        tmp_byte = mtfSymbol[n];
234        while (--n >= 0)
235            mtfSymbol[n + 1] = mtfSymbol[n];
236        mtfSymbol[0] = selectors[i] = tmp_byte;
237    }
238
239    /* Read the Huffman coding tables for each group, which code for symTotal
240       literal symbols, plus two run symbols (RUNA, RUNB) */
241    symCount = symTotal + 2;
242    for (j = 0; j < groupCount; j++) {
243        uint8_t length[MAX_SYMBOLS];
244        /* 8 bits is ALMOST enough for temp[], see below */
245        unsigned temp[MAX_HUFCODE_BITS+1];
246        int minLen, maxLen, pp, len_m1;
247
248        /* Read Huffman code lengths for each symbol.  They're stored in
249           a way similar to mtf; record a starting value for the first symbol,
250           and an offset from the previous value for every symbol after that.
251           (Subtracting 1 before the loop and then adding it back at the end is
252           an optimization that makes the test inside the loop simpler: symbol
253           length 0 becomes negative, so an unsigned inequality catches it.) */
254        len_m1 = get_bits(bd, 5) - 1;
255        for (i = 0; i < symCount; i++) {
256            for (;;) {
257                int two_bits;
258                if ((unsigned)len_m1 > (MAX_HUFCODE_BITS-1))
259                    return RETVAL_DATA_ERROR;
260
261                /* If first bit is 0, stop.  Else second bit indicates whether
262                   to increment or decrement the value.  Optimization: grab 2
263                   bits and unget the second if the first was 0. */
264                two_bits = get_bits(bd, 2);
265                if (two_bits < 2) {
266                    bd->inbufBitCount++;
267                    break;
268                }
269
270                /* Add one if second bit 1, else subtract 1.  Avoids if/else */
271                len_m1 += (((two_bits+1) & 2) - 1);
272            }
273
274            /* Correct for the initial -1, to get the final symbol length */
275            length[i] = len_m1 + 1;
276        }
277
278        /* Find largest and smallest lengths in this group */
279        minLen = maxLen = length[0];
280        for (i = 1; i < symCount; i++) {
281            if (length[i] > maxLen) maxLen = length[i];
282            else if (length[i] < minLen) minLen = length[i];
283        }
284
285        /* Calculate permute[], base[], and limit[] tables from length[].
286         *
287         * permute[] is the lookup table for converting Huffman coded symbols
288         * into decoded symbols.  base[] is the amount to subtract from the
289         * value of a Huffman symbol of a given length when using permute[].
290         *
291         * limit[] indicates the largest numerical value a symbol with a given
292         * number of bits can have.  This is how the Huffman codes can vary in
293         * length: each code with a value>limit[length] needs another bit.
294         */
295        hufGroup = bd->groups + j;
296        hufGroup->minLen = minLen;
297        hufGroup->maxLen = maxLen;
298
299        /* Note that minLen can't be smaller than 1, so we adjust the base
300           and limit array pointers so we're not always wasting the first
301           entry.  We do this again when using them (during symbol decoding). */
302        base = hufGroup->base - 1;
303        limit = hufGroup->limit - 1;
304
305        /* Calculate permute[].  Concurently, initialize temp[] and limit[]. */
306        pp = 0;
307        for (i = minLen; i <= maxLen; i++) {
308            int k;
309            temp[i] = limit[i] = 0;
310            for (k = 0; k < symCount; k++)
311                if (length[k] == i)
312                    hufGroup->permute[pp++] = k;
313        }
314
315        /* Count symbols coded for at each bit length */
316        /* NB: in pathological cases, temp[8] can end ip being 256.
317         * That's why uint8_t is too small for temp[]. */
318        for (i = 0; i < symCount; i++) temp[length[i]]++;
319
320        /* Calculate limit[] (the largest symbol-coding value at each bit
321         * length, which is (previous limit<<1)+symbols at this level), and
322         * base[] (number of symbols to ignore at each bit length, which is
323         * limit minus the cumulative count of symbols coded for already). */
324        pp = t = 0;
325        for (i = minLen; i < maxLen;) {
326            unsigned temp_i = temp[i];
327
328            pp += temp_i;
329
330            /* We read the largest possible symbol size and then unget bits
331               after determining how many we need, and those extra bits could
332               be set to anything.  (They're noise from future symbols.)  At
333               each level we're really only interested in the first few bits,
334               so here we set all the trailing to-be-ignored bits to 1 so they
335               don't affect the value>limit[length] comparison. */
336            limit[i] = (pp << (maxLen - i)) - 1;
337            pp <<= 1;
338            t += temp_i;
339            base[++i] = pp - t;
340        }
341        limit[maxLen] = pp + temp[maxLen] - 1;
342        limit[maxLen+1] = INT_MAX; /* Sentinel value for reading next sym. */
343        base[minLen] = 0;
344    }
345
346    /* We've finished reading and digesting the block header.  Now read this
347       block's Huffman coded symbols from the file and undo the Huffman coding
348       and run length encoding, saving the result into dbuf[dbufCount++] = uc */
349
350    /* Initialize symbol occurrence counters and symbol Move To Front table */
351    /*memset(byteCount, 0, sizeof(byteCount)); - smaller, but slower */
352    for (i = 0; i < 256; i++) {
353        byteCount[i] = 0;
354        mtfSymbol[i] = (uint8_t)i;
355    }
356
357    /* Loop through compressed symbols. */
358
359    runPos = dbufCount = selector = 0;
360    for (;;) {
361        int nextSym;
362
363        /* Fetch next Huffman coding group from list. */
364        symCount = GROUP_SIZE - 1;
365        if (selector >= nSelectors) return RETVAL_DATA_ERROR;
366        hufGroup = bd->groups + selectors[selector++];
367        base = hufGroup->base - 1;
368        limit = hufGroup->limit - 1;
369
370 continue_this_group:
371        /* Read next Huffman-coded symbol. */
372
373        /* Note: It is far cheaper to read maxLen bits and back up than it is
374           to read minLen bits and then add additional bit at a time, testing
375           as we go.  Because there is a trailing last block (with file CRC),
376           there is no danger of the overread causing an unexpected EOF for a
377           valid compressed file.
378         */
379        if (1) {
380            /* As a further optimization, we do the read inline
381               (falling back to a call to get_bits if the buffer runs dry).
382             */
383            int new_cnt;
384            while ((new_cnt = bd->inbufBitCount - hufGroup->maxLen) < 0) {
385                /* bd->inbufBitCount < hufGroup->maxLen */
386                if (bd->inbufPos == bd->inbufCount) {
387                    nextSym = get_bits(bd, hufGroup->maxLen);
388                    goto got_huff_bits;
389                }
390                bd->inbufBits = (bd->inbufBits << 8) | bd->inbuf[bd->inbufPos++];
391                bd->inbufBitCount += 8;
392            };
393            bd->inbufBitCount = new_cnt; /* "bd->inbufBitCount -= hufGroup->maxLen;" */
394            nextSym = (bd->inbufBits >> new_cnt) & ((1 << hufGroup->maxLen) - 1);
395 got_huff_bits: ;
396        } else { /* unoptimized equivalent */
397            nextSym = get_bits(bd, hufGroup->maxLen);
398        }
399        /* Figure how many bits are in next symbol and unget extras */
400        i = hufGroup->minLen;
401        while (nextSym > limit[i]) ++i;
402        j = hufGroup->maxLen - i;
403        if (j < 0)
404            return RETVAL_DATA_ERROR;
405        bd->inbufBitCount += j;
406
407        /* Huffman decode value to get nextSym (with bounds checking) */
408        nextSym = (nextSym >> j) - base[i];
409        if ((unsigned)nextSym >= MAX_SYMBOLS)
410            return RETVAL_DATA_ERROR;
411        nextSym = hufGroup->permute[nextSym];
412
413        /* We have now decoded the symbol, which indicates either a new literal
414           byte, or a repeated run of the most recent literal byte.  First,
415           check if nextSym indicates a repeated run, and if so loop collecting
416           how many times to repeat the last literal. */
417        if ((unsigned)nextSym <= SYMBOL_RUNB) { /* RUNA or RUNB */
418
419            /* If this is the start of a new run, zero out counter */
420            if (runPos == 0) {
421                runPos = 1;
422                runCnt = 0;
423            }
424
425            /* Neat trick that saves 1 symbol: instead of or-ing 0 or 1 at
426               each bit position, add 1 or 2 instead.  For example,
427               1011 is 1<<0 + 1<<1 + 2<<2.  1010 is 2<<0 + 2<<1 + 1<<2.
428               You can make any bit pattern that way using 1 less symbol than
429               the basic or 0/1 method (except all bits 0, which would use no
430               symbols, but a run of length 0 doesn't mean anything in this
431               context).  Thus space is saved. */
432            runCnt += (runPos << nextSym); /* +runPos if RUNA; +2*runPos if RUNB */
433            if (runPos < dbufSize) runPos <<= 1;
434            goto end_of_huffman_loop;
435        }
436
437        /* When we hit the first non-run symbol after a run, we now know
438           how many times to repeat the last literal, so append that many
439           copies to our buffer of decoded symbols (dbuf) now.  (The last
440           literal used is the one at the head of the mtfSymbol array.) */
441        if (runPos != 0) {
442            uint8_t tmp_byte;
443            if (dbufCount + runCnt >= dbufSize) return RETVAL_DATA_ERROR;
444            tmp_byte = symToByte[mtfSymbol[0]];
445            byteCount[tmp_byte] += runCnt;
446            while (--runCnt >= 0) dbuf[dbufCount++] = (uint32_t)tmp_byte;
447            runPos = 0;
448        }
449
450        /* Is this the terminating symbol? */
451        if (nextSym > symTotal) break;
452
453        /* At this point, nextSym indicates a new literal character.  Subtract
454           one to get the position in the MTF array at which this literal is
455           currently to be found.  (Note that the result can't be -1 or 0,
456           because 0 and 1 are RUNA and RUNB.  But another instance of the
457           first symbol in the mtf array, position 0, would have been handled
458           as part of a run above.  Therefore 1 unused mtf position minus
459           2 non-literal nextSym values equals -1.) */
460        if (dbufCount >= dbufSize) return RETVAL_DATA_ERROR;
461        i = nextSym - 1;
462        uc = mtfSymbol[i];
463
464        /* Adjust the MTF array.  Since we typically expect to move only a
465         * small number of symbols, and are bound by 256 in any case, using
466         * memmove here would typically be bigger and slower due to function
467         * call overhead and other assorted setup costs. */
468        do {
469            mtfSymbol[i] = mtfSymbol[i-1];
470        } while (--i);
471        mtfSymbol[0] = uc;
472        uc = symToByte[uc];
473
474        /* We have our literal byte.  Save it into dbuf. */
475        byteCount[uc]++;
476        dbuf[dbufCount++] = (uint32_t)uc;
477
478        /* Skip group initialization if we're not done with this group.  Done
479         * this way to avoid compiler warning. */
480 end_of_huffman_loop:
481        if (--symCount >= 0) goto continue_this_group;
482    }
483
484    /* At this point, we've read all the Huffman-coded symbols (and repeated
485       runs) for this block from the input stream, and decoded them into the
486       intermediate buffer.  There are dbufCount many decoded bytes in dbuf[].
487       Now undo the Burrows-Wheeler transform on dbuf.
488       See http://dogma.net/markn/articles/bwt/bwt.htm
489     */
490
491    /* Turn byteCount into cumulative occurrence counts of 0 to n-1. */
492    j = 0;
493    for (i = 0; i < 256; i++) {
494        int tmp_count = j + byteCount[i];
495        byteCount[i] = j;
496        j = tmp_count;
497    }
498
499    /* Figure out what order dbuf would be in if we sorted it. */
500    for (i = 0; i < dbufCount; i++) {
501        uint8_t tmp_byte = (uint8_t)dbuf[i];
502        int tmp_count = byteCount[tmp_byte];
503        dbuf[tmp_count] |= (i << 8);
504        byteCount[tmp_byte] = tmp_count + 1;
505    }
506
507    /* Decode first byte by hand to initialize "previous" byte.  Note that it
508       doesn't get output, and if the first three characters are identical
509       it doesn't qualify as a run (hence writeRunCountdown=5). */
510    if (dbufCount) {
511        uint32_t tmp;
512        if ((int)origPtr >= dbufCount) return RETVAL_DATA_ERROR;
513        tmp = dbuf[origPtr];
514        bd->writeCurrent = (uint8_t)tmp;
515        bd->writePos = (tmp >> 8);
516        bd->writeRunCountdown = 5;
517    }
518    bd->writeCount = dbufCount;
519
520    return RETVAL_OK;
521}
522
523/* Undo Burrows-Wheeler transform on intermediate buffer to produce output.
524   If start_bunzip was initialized with out_fd=-1, then up to len bytes of
525   data are written to outbuf.  Return value is number of bytes written or
526   error (all errors are negative numbers).  If out_fd!=-1, outbuf and len
527   are ignored, data is written to out_fd and return is RETVAL_OK or error.
528
529   NB: read_bunzip returns < 0 on error, or the number of *unfilled* bytes
530   in outbuf. IOW: on EOF returns len ("all bytes are not filled"), not 0.
531   (Why? This allows to get rid of one local variable)
532*/
533int FAST_FUNC read_bunzip(bunzip_data *bd, char *outbuf, int len)
534{
535    const uint32_t *dbuf;
536    int pos, current, previous;
537    uint32_t CRC;
538
539    /* If we already have error/end indicator, return it */
540    if (bd->writeCount < 0)
541        return bd->writeCount;
542
543    dbuf = bd->dbuf;
544
545    /* Register-cached state (hopefully): */
546    pos = bd->writePos;
547    current = bd->writeCurrent;
548    CRC = bd->writeCRC; /* small loss on x86-32 (not enough regs), win on x86-64 */
549
550    /* We will always have pending decoded data to write into the output
551       buffer unless this is the very first call (in which case we haven't
552       Huffman-decoded a block into the intermediate buffer yet). */
553    if (bd->writeCopies) {
554
555 dec_writeCopies:
556        /* Inside the loop, writeCopies means extra copies (beyond 1) */
557        --bd->writeCopies;
558
559        /* Loop outputting bytes */
560        for (;;) {
561
562            /* If the output buffer is full, save cached state and return */
563            if (--len < 0) {
564                /* Unlikely branch.
565                 * Use of "goto" instead of keeping code here
566                 * helps compiler to realize this. */
567                goto outbuf_full;
568            }
569
570            /* Write next byte into output buffer, updating CRC */
571            *outbuf++ = current;
572            CRC = (CRC << 8) ^ bd->crc32Table[(CRC >> 24) ^ current];
573
574            /* Loop now if we're outputting multiple copies of this byte */
575            if (bd->writeCopies) {
576                /* Unlikely branch */
577                /*--bd->writeCopies;*/
578                /*continue;*/
579                /* Same, but (ab)using other existing --writeCopies operation
580                 * (and this if() compiles into just test+branch pair): */
581                goto dec_writeCopies;
582            }
583 decode_next_byte:
584            if (--bd->writeCount < 0)
585                break; /* input block is fully consumed, need next one */
586
587            /* Follow sequence vector to undo Burrows-Wheeler transform */
588            previous = current;
589            pos = dbuf[pos];
590            current = (uint8_t)pos;
591            pos >>= 8;
592
593            /* After 3 consecutive copies of the same byte, the 4th
594             * is a repeat count.  We count down from 4 instead
595             * of counting up because testing for non-zero is faster */
596            if (--bd->writeRunCountdown != 0) {
597                if (current != previous)
598                    bd->writeRunCountdown = 4;
599            } else {
600                /* Unlikely branch */
601                /* We have a repeated run, this byte indicates the count */
602                bd->writeCopies = current;
603                current = previous;
604                bd->writeRunCountdown = 5;
605
606                /* Sometimes there are just 3 bytes (run length 0) */
607                if (!bd->writeCopies) goto decode_next_byte;
608
609                /* Subtract the 1 copy we'd output anyway to get extras */
610                --bd->writeCopies;
611            }
612        } /* for(;;) */
613
614        /* Decompression of this input block completed successfully */
615        bd->writeCRC = CRC = ~CRC;
616        bd->totalCRC = ((bd->totalCRC << 1) | (bd->totalCRC >> 31)) ^ CRC;
617
618        /* If this block had a CRC error, force file level CRC error */
619        if (CRC != bd->headerCRC) {
620            bd->totalCRC = bd->headerCRC + 1;
621            return RETVAL_LAST_BLOCK;
622        }
623    }
624
625    /* Refill the intermediate buffer by Huffman-decoding next block of input */
626    {
627        int r = get_next_block(bd);
628        if (r) { /* error/end */
629            bd->writeCount = r;
630            return (r != RETVAL_LAST_BLOCK) ? r : len;
631        }
632    }
633
634    CRC = ~0;
635    pos = bd->writePos;
636    current = bd->writeCurrent;
637    goto decode_next_byte;
638
639 outbuf_full:
640    /* Output buffer is full, save cached state and return */
641    bd->writePos = pos;
642    bd->writeCurrent = current;
643    bd->writeCRC = CRC;
644
645    bd->writeCopies++;
646
647    return 0;
648}
649
650/* Allocate the structure, read file header.  If in_fd==-1, inbuf must contain
651   a complete bunzip file (len bytes long).  If in_fd!=-1, inbuf and len are
652   ignored, and data is read from file handle into temporary buffer. */
653
654/* Because bunzip2 is used for help text unpacking, and because bb_show_usage()
655   should work for NOFORK applets too, we must be extremely careful to not leak
656   any allocations! */
657int FAST_FUNC start_bunzip(bunzip_data **bdp, int in_fd,
658        const void *inbuf, int len)
659{
660    bunzip_data *bd;
661    unsigned i;
662    enum {
663        BZh0 = ('B' << 24) + ('Z' << 16) + ('h' << 8) + '0',
664        h0 = ('h' << 8) + '0',
665    };
666
667    /* Figure out how much data to allocate */
668    i = sizeof(bunzip_data);
669    if (in_fd != -1) i += IOBUF_SIZE;
670
671    /* Allocate bunzip_data.  Most fields initialize to zero. */
672    bd = *bdp = xzalloc(i);
673
674    /* Setup input buffer */
675    bd->in_fd = in_fd;
676    if (-1 == in_fd) {
677        /* in this case, bd->inbuf is read-only */
678        bd->inbuf = (void*)inbuf; /* cast away const-ness */
679    } else {
680        bd->inbuf = (uint8_t*)(bd + 1);
681        memcpy(bd->inbuf, inbuf, len);
682    }
683    bd->inbufCount = len;
684
685    /* Init the CRC32 table (big endian) */
686    crc32_filltable(bd->crc32Table, 1);
687
688    /* Setup for I/O error handling via longjmp */
689    i = setjmp(bd->jmpbuf);
690    if (i) return i;
691
692    /* Ensure that file starts with "BZh['1'-'9']." */
693    /* Update: now caller verifies 1st two bytes, makes .gz/.bz2
694     * integration easier */
695    /* was: */
696    /* i = get_bits(bd, 32); */
697    /* if ((unsigned)(i - BZh0 - 1) >= 9) return RETVAL_NOT_BZIP_DATA; */
698    i = get_bits(bd, 16);
699    if ((unsigned)(i - h0 - 1) >= 9) return RETVAL_NOT_BZIP_DATA;
700
701    /* Fourth byte (ascii '1'-'9') indicates block size in units of 100k of
702       uncompressed data.  Allocate intermediate buffer for block. */
703    /* bd->dbufSize = 100000 * (i - BZh0); */
704    bd->dbufSize = 100000 * (i - h0);
705
706    /* Cannot use xmalloc - may leak bd in NOFORK case! */
707    bd->dbuf = malloc_or_warn(bd->dbufSize * sizeof(bd->dbuf[0]));
708    if (!bd->dbuf) {
709        free(bd);
710        xfunc_die();
711    }
712    return RETVAL_OK;
713}
714
715void FAST_FUNC dealloc_bunzip(bunzip_data *bd)
716{
717    free(bd->dbuf);
718    free(bd);
719}
720
721
722/* Decompress src_fd to dst_fd.  Stops at end of bzip data, not end of file. */
723IF_DESKTOP(long long) int FAST_FUNC
724unpack_bz2_stream(transformer_aux_data_t *aux, int src_fd, int dst_fd)
725{
726    IF_DESKTOP(long long total_written = 0;)
727    bunzip_data *bd;
728    char *outbuf;
729    int i;
730    unsigned len;
731
732    if (check_signature16(aux, src_fd, BZIP2_MAGIC))
733        return -1;
734
735    outbuf = xmalloc(IOBUF_SIZE);
736    len = 0;
737    while (1) { /* "Process one BZ... stream" loop */
738
739        i = start_bunzip(&bd, src_fd, outbuf + 2, len);
740
741        if (i == 0) {
742            while (1) { /* "Produce some output bytes" loop */
743                i = read_bunzip(bd, outbuf, IOBUF_SIZE);
744                if (i < 0) /* error? */
745                    break;
746                i = IOBUF_SIZE - i; /* number of bytes produced */
747                if (i == 0) /* EOF? */
748                    break;
749                if (i != full_write(dst_fd, outbuf, i)) {
750                    bb_error_msg("short write");
751                    i = RETVAL_SHORT_WRITE;
752                    goto release_mem;
753                }
754                IF_DESKTOP(total_written += i;)
755            }
756        }
757
758        if (i != RETVAL_LAST_BLOCK
759        /* Observed case when i == RETVAL_OK:
760         * "bzcat z.bz2", where "z.bz2" is a bzipped zero-length file
761         * (to be exact, z.bz2 is exactly these 14 bytes:
762         * 42 5a 68 39 17 72 45 38  50 90 00 00 00 00).
763         */
764         && i != RETVAL_OK
765        ) {
766            bb_error_msg("bunzip error %d", i);
767            break;
768        }
769        if (bd->headerCRC != bd->totalCRC) {
770            bb_error_msg("CRC error");
771            break;
772        }
773
774        /* Successfully unpacked one BZ stream */
775        i = RETVAL_OK;
776
777        /* Do we have "BZ..." after last processed byte?
778         * pbzip2 (parallelized bzip2) produces such files.
779         */
780        len = bd->inbufCount - bd->inbufPos;
781        memcpy(outbuf, &bd->inbuf[bd->inbufPos], len);
782        if (len < 2) {
783            if (safe_read(src_fd, outbuf + len, 2 - len) != 2 - len)
784                break;
785            len = 2;
786        }
787        if (*(uint16_t*)outbuf != BZIP2_MAGIC) /* "BZ"? */
788            break;
789        dealloc_bunzip(bd);
790        len -= 2;
791    }
792
793 release_mem:
794    dealloc_bunzip(bd);
795    free(outbuf);
796
797    return i ? i : IF_DESKTOP(total_written) + 0;
798}
799
800#ifdef TESTING
801
802static char *const bunzip_errors[] = {
803    NULL, "Bad file checksum", "Not bzip data",
804    "Unexpected input EOF", "Unexpected output EOF", "Data error",
805    "Out of memory", "Obsolete (pre 0.9.5) bzip format not supported"
806};
807
808/* Dumb little test thing, decompress stdin to stdout */
809int main(int argc, char **argv)
810{
811    int i;
812    char c;
813
814    int i = unpack_bz2_stream(0, 1);
815    if (i < 0)
816        fprintf(stderr, "%s\n", bunzip_errors[-i]);
817    else if (read(STDIN_FILENO, &c, 1))
818        fprintf(stderr, "Trailing garbage ignored\n");
819    return -i;
820}
821#endif
Note: See TracBrowser for help on using the repository browser.