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