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