^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /* inftrees.c -- generate Huffman trees for efficient decoding
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) * Copyright (C) 1995-2005 Mark Adler
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * For conditions of distribution and use, see copyright notice in zlib.h
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) #include <linux/zutil.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) #include "inftrees.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) #define MAXBITS 15
^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) Build a set of tables to decode the provided canonical Huffman code.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) The code lengths are lens[0..codes-1]. The result starts at *table,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) whose indices are 0..2^bits-1. work is a writable array of at least
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) lens shorts, which is used as a work area. type is the type of code
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) to be generated, CODES, LENS, or DISTS. On return, zero is success,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) on return points to the next available entry's address. bits is the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) requested root table index bits, and on return it is the actual root
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) table index bits. It will differ if the request is greater than the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) longest code or if it is less than the shortest code.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) int zlib_inflate_table(codetype type, unsigned short *lens, unsigned codes,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) code **table, unsigned *bits, unsigned short *work)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) unsigned len; /* a code's length in bits */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) unsigned sym; /* index of code symbols */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) unsigned min, max; /* minimum and maximum code lengths */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) unsigned root; /* number of index bits for root table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) unsigned curr; /* number of index bits for current table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) unsigned drop; /* code bits to drop for sub-table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) int left; /* number of prefix codes available */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) unsigned used; /* code entries in table used */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) unsigned huff; /* Huffman code */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) unsigned incr; /* for incrementing code, index */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) unsigned fill; /* index for replicating entries */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) unsigned low; /* low bits for current root entry */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) unsigned mask; /* mask for low root bits */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) code this; /* table entry for duplication */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) code *next; /* next available space in table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) const unsigned short *base; /* base value table to use */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) const unsigned short *extra; /* extra bits table to use */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) int end; /* use base and extra for symbol > end */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) unsigned short count[MAXBITS+1]; /* number of codes of each length */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) static const unsigned short lbase[31] = { /* Length codes 257..285 base */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) static const unsigned short lext[31] = { /* Length codes 257..285 extra */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196};
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) 8193, 12289, 16385, 24577, 0, 0};
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) 28, 28, 29, 29, 64, 64};
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) Process a set of code lengths to create a canonical Huffman code. The
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) code lengths are lens[0..codes-1]. Each length corresponds to the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) symbols 0..codes-1. The Huffman code is generated by first sorting the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) symbols by length from short to long, and retaining the symbol order
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) for codes with equal lengths. Then the code starts with all zero bits
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) for the first code of the shortest length, and the codes are integer
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) increments for the same length, and zeros are appended as the length
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) increases. For the deflate format, these bits are stored backwards
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) from their more natural integer increment ordering, and so when the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) decoding tables are built in the large loop below, the integer codes
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) are incremented backwards.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) This routine assumes, but does not check, that all of the entries in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) lens[] are in the range 0..MAXBITS. The caller must assure this.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) 1..MAXBITS is interpreted as that code length. zero means that that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) symbol does not occur in this code.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) The codes are sorted by computing a count of codes for each length,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) creating from that a table of starting indices for each length in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) sorted table, and then entering the symbols in order in the sorted
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) table. The sorted table is work[], with that space being provided by
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) the caller.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) The length counts are used for other purposes as well, i.e. finding
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) the minimum and maximum length codes, determining if there are any
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) codes at all, checking for a valid set of lengths, and looking ahead
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) at length counts to determine sub-table sizes when building the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) decoding tables.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) for (len = 0; len <= MAXBITS; len++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) count[len] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) for (sym = 0; sym < codes; sym++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) count[lens[sym]]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) /* bound code lengths, force root to be within code lengths */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) root = *bits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) for (max = MAXBITS; max >= 1; max--)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) if (count[max] != 0) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) if (root > max) root = max;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) if (max == 0) { /* no symbols to code at all */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) this.op = (unsigned char)64; /* invalid code marker */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) this.bits = (unsigned char)1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) this.val = (unsigned short)0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) *(*table)++ = this; /* make a table to force an error */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) *(*table)++ = this;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) *bits = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) return 0; /* no symbols, but wait for decoding to report error */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) for (min = 1; min < MAXBITS; min++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) if (count[min] != 0) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) if (root < min) root = min;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) /* check for an over-subscribed or incomplete set of lengths */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) left = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) for (len = 1; len <= MAXBITS; len++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) left <<= 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) left -= count[len];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) if (left < 0) return -1; /* over-subscribed */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) if (left > 0 && (type == CODES || max != 1))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) return -1; /* incomplete set */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) /* generate offsets into symbol table for each length for sorting */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) offs[1] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) for (len = 1; len < MAXBITS; len++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) offs[len + 1] = offs[len] + count[len];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) /* sort symbols by length, by symbol order within each length */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) for (sym = 0; sym < codes; sym++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) Create and fill in decoding tables. In this loop, the table being
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) filled is at next and has curr index bits. The code being used is huff
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) with length len. That code is converted to an index by dropping drop
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) bits off of the bottom. For codes where len is less than drop + curr,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) those top drop + curr - len bits are incremented through all values to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) fill the table with replicated entries.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) root is the number of index bits for the root table. When len exceeds
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) root, sub-tables are created pointed to by the root entry with an index
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) of the low root bits of huff. This is saved in low to check for when a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) new sub-table should be started. drop is zero when the root table is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) being filled, and drop is root when sub-tables are being filled.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) When a new sub-table is needed, it is necessary to look ahead in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) code lengths to determine what size sub-table is needed. The length
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) counts are used for this, and so count[] is decremented as codes are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) entered in the tables.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) used keeps track of how many table entries have been allocated from the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) provided *table space. It is checked when a LENS table is being made
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) against the space in *table, ENOUGH, minus the maximum space needed by
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) the worst case distance code, MAXD. This should never happen, but the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) sufficiency of ENOUGH has not been proven exhaustively, hence the check.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) This assumes that when type == LENS, bits == 9.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) sym increments through all symbols, and the loop terminates when
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) all codes of length max, i.e. all codes, have been processed. This
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) routine permits incomplete codes, so another loop after this one fills
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) in the rest of the decoding tables with invalid code markers.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) /* set up for code type */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) switch (type) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) case CODES:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) base = extra = work; /* dummy value--not used */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) end = 19;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) case LENS:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) base = lbase;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) base -= 257;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) extra = lext;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) extra -= 257;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) end = 256;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) default: /* DISTS */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) base = dbase;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) extra = dext;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) end = -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) /* initialize state for loop */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) huff = 0; /* starting code */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) sym = 0; /* starting code symbol */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) len = min; /* starting code length */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) next = *table; /* current table to fill in */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) curr = root; /* current table index bits */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) drop = 0; /* current bits to drop from code for index */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) low = (unsigned)(-1); /* trigger new sub-table when len > root */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) used = 1U << root; /* use root table entries */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) mask = used - 1; /* mask for comparing low */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) /* check available table space */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) if (type == LENS && used >= ENOUGH - MAXD)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) /* process all codes and make table entries */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) for (;;) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) /* create table entry */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) this.bits = (unsigned char)(len - drop);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) if ((int)(work[sym]) < end) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) this.op = (unsigned char)0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) this.val = work[sym];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) else if ((int)(work[sym]) > end) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) this.op = (unsigned char)(extra[work[sym]]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) this.val = base[work[sym]];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) this.op = (unsigned char)(32 + 64); /* end of block */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) this.val = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) /* replicate for those indices with low len bits equal to huff */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) incr = 1U << (len - drop);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) fill = 1U << curr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) min = fill; /* save offset to next table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) fill -= incr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) next[(huff >> drop) + fill] = this;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) } while (fill != 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) /* backwards increment the len-bit code huff */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) incr = 1U << (len - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) while (huff & incr)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) incr >>= 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) if (incr != 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) huff &= incr - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) huff += incr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) huff = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) /* go to next symbol, update count, len */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) sym++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) if (--(count[len]) == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) if (len == max) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) len = lens[work[sym]];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) /* create new sub-table if needed */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) if (len > root && (huff & mask) != low) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) /* if first time, transition to sub-tables */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) if (drop == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) drop = root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) /* increment past last table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) next += min; /* here min is 1 << curr */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) /* determine length of next table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) curr = len - drop;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) left = (int)(1 << curr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) while (curr + drop < max) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) left -= count[curr + drop];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) if (left <= 0) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) curr++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) left <<= 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) /* check for enough space */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) used += 1U << curr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) if (type == LENS && used >= ENOUGH - MAXD)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) /* point entry in root table to sub-table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) low = huff & mask;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) (*table)[low].op = (unsigned char)curr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) (*table)[low].bits = (unsigned char)root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) (*table)[low].val = (unsigned short)(next - *table);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) Fill in rest of table for incomplete codes. This loop is similar to the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) loop above in incrementing huff for table indices. It is assumed that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) len is equal to curr + drop, so there is no loop needed to increment
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) through high index bits. When the current sub-table is filled, the loop
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) drops back to the root table to fill in any remaining entries there.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) this.op = (unsigned char)64; /* invalid code marker */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) this.bits = (unsigned char)(len - drop);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) this.val = (unsigned short)0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) while (huff != 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) /* when done with sub-table, drop back to root table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) if (drop != 0 && (huff & mask) != low) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) drop = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) len = root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) next = *table;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) this.bits = (unsigned char)len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) /* put invalid code marker in table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) next[huff >> drop] = this;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) /* backwards increment the len-bit code huff */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) incr = 1U << (len - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) while (huff & incr)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) incr >>= 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) if (incr != 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) huff &= incr - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) huff += incr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) huff = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) /* set return parameters */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) *table += used;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) *bits = root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags