| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <202008300858.7W4rp9Ir%lkp@intel.com>
Date: Sun, 30 Aug 2020 08:50:08 +0800
From: kernel test robot <lkp@...el.com>
To: Kees Cook <keescook@...omium.org>
Cc: kbuild-all@...ts.01.org, linux-kernel@...r.kernel.org,
Andrew Morton <akpm@...ux-foundation.org>,
Linux Memory Management List <linux-mm@...ck.org>
Subject: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:258:
undefined reference to `__ubsan_handle_type_mismatch_v1'
tree: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git master
head: 1127b219ce9481c84edad9711626d856127d5e51
commit: 8d58f222e85f01da0c0e1fc1e77986c86de889e2 ubsan: disable UBSAN_ALIGNMENT under COMPILE_TEST
date: 4 months ago
config: mips-randconfig-r025-20200829 (attached as .config)
compiler: mipsel-linux-gcc (GCC) 9.3.0
reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
chmod +x ~/bin/make.cross
git checkout 8d58f222e85f01da0c0e1fc1e77986c86de889e2
# save the attached .config to linux build tree
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-9.3.0 make.cross ARCH=mips
If you fix the issue, kindly add following tag as appropriate
Reported-by: kernel test robot <lkp@...el.com>
All errors (new ones prefixed by >>):
mipsel-linux-ld: arch/mips/boot/compressed/decompress.o: in function `zlib_inflate_table':
>> arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:258: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:258: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:240: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:240: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:240: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:240: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:96: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:96: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:94: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:94: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:101: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:96: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:101: undefined reference to `__ubsan_handle_type_mismatch_v1'
>> mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:258: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:258: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:133: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:133: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:133: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:113: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:113: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:129: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:129: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:129: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:129: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:129: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:129: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:120: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:120: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:219: undefined reference to `__ubsan_handle_shift_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:256: undefined reference to `__ubsan_handle_shift_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:265: undefined reference to `__ubsan_handle_shift_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:228: undefined reference to `__ubsan_handle_shift_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:220: undefined reference to `__ubsan_handle_shift_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:258: undefined reference to `__ubsan_handle_out_of_bounds'
>> mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c:258: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/decompress.o: in function `inflate_fast':
arch/mips/boot/compressed/../../../../lib/zlib_inflate/inffast.c:318: undefined reference to `__ubsan_handle_shift_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inffast.c:308: undefined reference to `__ubsan_handle_shift_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inffast.c:176: undefined reference to `__ubsan_handle_shift_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inffast.c:135: undefined reference to `__ubsan_handle_shift_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inffast.c:134: undefined reference to `__ubsan_handle_shift_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/decompress.o:arch/mips/boot/compressed/../../../../lib/zlib_inflate/inffast.c:149: more undefined references to `__ubsan_handle_shift_out_of_bounds' follow
mipsel-linux-ld: arch/mips/boot/compressed/decompress.o: in function `zlib_inflate':
arch/mips/boot/compressed/../../../../lib/zlib_inflate/inflate.c:550: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inflate.c:491: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inflate.c:491: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inflate.c:491: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inflate.c:526: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inflate.c:515: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inflate.c:487: undefined reference to `__ubsan_handle_type_mismatch_v1'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inflate.c:487: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inflate.c:487: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inflate.c:514: undefined reference to `__ubsan_handle_shift_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inflate.c:532: undefined reference to `__ubsan_handle_shift_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inflate.c:587: undefined reference to `__ubsan_handle_shift_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inflate.c:641: undefined reference to `__ubsan_handle_shift_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/../../../../lib/zlib_inflate/inflate.c:510: undefined reference to `__ubsan_handle_shift_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/decompress.o:arch/mips/boot/compressed/../../../../lib/zlib_inflate/inflate.c:508: more undefined references to `__ubsan_handle_shift_out_of_bounds' follow
mipsel-linux-ld: arch/mips/boot/compressed/dbg.o: in function `puthex':
arch/mips/boot/compressed/dbg.c:32: undefined reference to `__ubsan_handle_out_of_bounds'
mipsel-linux-ld: arch/mips/boot/compressed/dbg.c:32: undefined reference to `__ubsan_handle_type_mismatch_v1'
# https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=8d58f222e85f01da0c0e1fc1e77986c86de889e2
git remote add linus https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
git fetch --no-tags linus master
git checkout 8d58f222e85f01da0c0e1fc1e77986c86de889e2
vim +258 arch/mips/boot/compressed/../../../../lib/zlib_inflate/inftrees.c
4f3865fb57a04db Richard Purdie 2006-06-22 10
4f3865fb57a04db Richard Purdie 2006-06-22 11 /*
4f3865fb57a04db Richard Purdie 2006-06-22 12 Build a set of tables to decode the provided canonical Huffman code.
4f3865fb57a04db Richard Purdie 2006-06-22 13 The code lengths are lens[0..codes-1]. The result starts at *table,
4f3865fb57a04db Richard Purdie 2006-06-22 14 whose indices are 0..2^bits-1. work is a writable array of at least
4f3865fb57a04db Richard Purdie 2006-06-22 15 lens shorts, which is used as a work area. type is the type of code
4f3865fb57a04db Richard Purdie 2006-06-22 16 to be generated, CODES, LENS, or DISTS. On return, zero is success,
4f3865fb57a04db Richard Purdie 2006-06-22 17 -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
4f3865fb57a04db Richard Purdie 2006-06-22 18 on return points to the next available entry's address. bits is the
4f3865fb57a04db Richard Purdie 2006-06-22 19 requested root table index bits, and on return it is the actual root
4f3865fb57a04db Richard Purdie 2006-06-22 20 table index bits. It will differ if the request is greater than the
4f3865fb57a04db Richard Purdie 2006-06-22 21 longest code or if it is less than the shortest code.
4f3865fb57a04db Richard Purdie 2006-06-22 22 */
b762450e84e20a1 Randy Dunlap 2006-06-27 23 int zlib_inflate_table(codetype type, unsigned short *lens, unsigned codes,
b762450e84e20a1 Randy Dunlap 2006-06-27 24 code **table, unsigned *bits, unsigned short *work)
4f3865fb57a04db Richard Purdie 2006-06-22 25 {
4f3865fb57a04db Richard Purdie 2006-06-22 26 unsigned len; /* a code's length in bits */
4f3865fb57a04db Richard Purdie 2006-06-22 27 unsigned sym; /* index of code symbols */
4f3865fb57a04db Richard Purdie 2006-06-22 28 unsigned min, max; /* minimum and maximum code lengths */
4f3865fb57a04db Richard Purdie 2006-06-22 29 unsigned root; /* number of index bits for root table */
4f3865fb57a04db Richard Purdie 2006-06-22 30 unsigned curr; /* number of index bits for current table */
4f3865fb57a04db Richard Purdie 2006-06-22 31 unsigned drop; /* code bits to drop for sub-table */
4f3865fb57a04db Richard Purdie 2006-06-22 32 int left; /* number of prefix codes available */
4f3865fb57a04db Richard Purdie 2006-06-22 33 unsigned used; /* code entries in table used */
4f3865fb57a04db Richard Purdie 2006-06-22 34 unsigned huff; /* Huffman code */
4f3865fb57a04db Richard Purdie 2006-06-22 35 unsigned incr; /* for incrementing code, index */
4f3865fb57a04db Richard Purdie 2006-06-22 36 unsigned fill; /* index for replicating entries */
4f3865fb57a04db Richard Purdie 2006-06-22 37 unsigned low; /* low bits for current root entry */
4f3865fb57a04db Richard Purdie 2006-06-22 38 unsigned mask; /* mask for low root bits */
4f3865fb57a04db Richard Purdie 2006-06-22 39 code this; /* table entry for duplication */
4f3865fb57a04db Richard Purdie 2006-06-22 40 code *next; /* next available space in table */
4f3865fb57a04db Richard Purdie 2006-06-22 41 const unsigned short *base; /* base value table to use */
4f3865fb57a04db Richard Purdie 2006-06-22 42 const unsigned short *extra; /* extra bits table to use */
4f3865fb57a04db Richard Purdie 2006-06-22 43 int end; /* use base and extra for symbol > end */
4f3865fb57a04db Richard Purdie 2006-06-22 44 unsigned short count[MAXBITS+1]; /* number of codes of each length */
4f3865fb57a04db Richard Purdie 2006-06-22 45 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
4f3865fb57a04db Richard Purdie 2006-06-22 46 static const unsigned short lbase[31] = { /* Length codes 257..285 base */
^1da177e4c3f415 Linus Torvalds 2005-04-16 47 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
^1da177e4c3f415 Linus Torvalds 2005-04-16 48 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
4f3865fb57a04db Richard Purdie 2006-06-22 49 static const unsigned short lext[31] = { /* Length codes 257..285 extra */
4f3865fb57a04db Richard Purdie 2006-06-22 50 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
4f3865fb57a04db Richard Purdie 2006-06-22 51 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196};
4f3865fb57a04db Richard Purdie 2006-06-22 52 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
^1da177e4c3f415 Linus Torvalds 2005-04-16 53 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
^1da177e4c3f415 Linus Torvalds 2005-04-16 54 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
4f3865fb57a04db Richard Purdie 2006-06-22 55 8193, 12289, 16385, 24577, 0, 0};
4f3865fb57a04db Richard Purdie 2006-06-22 56 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
4f3865fb57a04db Richard Purdie 2006-06-22 57 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
4f3865fb57a04db Richard Purdie 2006-06-22 58 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
4f3865fb57a04db Richard Purdie 2006-06-22 59 28, 28, 29, 29, 64, 64};
^1da177e4c3f415 Linus Torvalds 2005-04-16 60
^1da177e4c3f415 Linus Torvalds 2005-04-16 61 /*
4f3865fb57a04db Richard Purdie 2006-06-22 62 Process a set of code lengths to create a canonical Huffman code. The
4f3865fb57a04db Richard Purdie 2006-06-22 63 code lengths are lens[0..codes-1]. Each length corresponds to the
4f3865fb57a04db Richard Purdie 2006-06-22 64 symbols 0..codes-1. The Huffman code is generated by first sorting the
4f3865fb57a04db Richard Purdie 2006-06-22 65 symbols by length from short to long, and retaining the symbol order
4f3865fb57a04db Richard Purdie 2006-06-22 66 for codes with equal lengths. Then the code starts with all zero bits
4f3865fb57a04db Richard Purdie 2006-06-22 67 for the first code of the shortest length, and the codes are integer
4f3865fb57a04db Richard Purdie 2006-06-22 68 increments for the same length, and zeros are appended as the length
4f3865fb57a04db Richard Purdie 2006-06-22 69 increases. For the deflate format, these bits are stored backwards
4f3865fb57a04db Richard Purdie 2006-06-22 70 from their more natural integer increment ordering, and so when the
4f3865fb57a04db Richard Purdie 2006-06-22 71 decoding tables are built in the large loop below, the integer codes
4f3865fb57a04db Richard Purdie 2006-06-22 72 are incremented backwards.
4f3865fb57a04db Richard Purdie 2006-06-22 73
4f3865fb57a04db Richard Purdie 2006-06-22 74 This routine assumes, but does not check, that all of the entries in
4f3865fb57a04db Richard Purdie 2006-06-22 75 lens[] are in the range 0..MAXBITS. The caller must assure this.
4f3865fb57a04db Richard Purdie 2006-06-22 76 1..MAXBITS is interpreted as that code length. zero means that that
4f3865fb57a04db Richard Purdie 2006-06-22 77 symbol does not occur in this code.
4f3865fb57a04db Richard Purdie 2006-06-22 78
4f3865fb57a04db Richard Purdie 2006-06-22 79 The codes are sorted by computing a count of codes for each length,
4f3865fb57a04db Richard Purdie 2006-06-22 80 creating from that a table of starting indices for each length in the
4f3865fb57a04db Richard Purdie 2006-06-22 81 sorted table, and then entering the symbols in order in the sorted
4f3865fb57a04db Richard Purdie 2006-06-22 82 table. The sorted table is work[], with that space being provided by
4f3865fb57a04db Richard Purdie 2006-06-22 83 the caller.
4f3865fb57a04db Richard Purdie 2006-06-22 84
4f3865fb57a04db Richard Purdie 2006-06-22 85 The length counts are used for other purposes as well, i.e. finding
4f3865fb57a04db Richard Purdie 2006-06-22 86 the minimum and maximum length codes, determining if there are any
4f3865fb57a04db Richard Purdie 2006-06-22 87 codes at all, checking for a valid set of lengths, and looking ahead
4f3865fb57a04db Richard Purdie 2006-06-22 88 at length counts to determine sub-table sizes when building the
4f3865fb57a04db Richard Purdie 2006-06-22 89 decoding tables.
^1da177e4c3f415 Linus Torvalds 2005-04-16 90 */
^1da177e4c3f415 Linus Torvalds 2005-04-16 91
4f3865fb57a04db Richard Purdie 2006-06-22 92 /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
4f3865fb57a04db Richard Purdie 2006-06-22 93 for (len = 0; len <= MAXBITS; len++)
4f3865fb57a04db Richard Purdie 2006-06-22 94 count[len] = 0;
4f3865fb57a04db Richard Purdie 2006-06-22 95 for (sym = 0; sym < codes; sym++)
4f3865fb57a04db Richard Purdie 2006-06-22 96 count[lens[sym]]++;
4f3865fb57a04db Richard Purdie 2006-06-22 97
4f3865fb57a04db Richard Purdie 2006-06-22 98 /* bound code lengths, force root to be within code lengths */
4f3865fb57a04db Richard Purdie 2006-06-22 99 root = *bits;
4f3865fb57a04db Richard Purdie 2006-06-22 100 for (max = MAXBITS; max >= 1; max--)
4f3865fb57a04db Richard Purdie 2006-06-22 101 if (count[max] != 0) break;
4f3865fb57a04db Richard Purdie 2006-06-22 102 if (root > max) root = max;
4f3865fb57a04db Richard Purdie 2006-06-22 103 if (max == 0) { /* no symbols to code at all */
4f3865fb57a04db Richard Purdie 2006-06-22 104 this.op = (unsigned char)64; /* invalid code marker */
4f3865fb57a04db Richard Purdie 2006-06-22 105 this.bits = (unsigned char)1;
4f3865fb57a04db Richard Purdie 2006-06-22 106 this.val = (unsigned short)0;
4f3865fb57a04db Richard Purdie 2006-06-22 107 *(*table)++ = this; /* make a table to force an error */
4f3865fb57a04db Richard Purdie 2006-06-22 108 *(*table)++ = this;
4f3865fb57a04db Richard Purdie 2006-06-22 109 *bits = 1;
4f3865fb57a04db Richard Purdie 2006-06-22 110 return 0; /* no symbols, but wait for decoding to report error */
4f3865fb57a04db Richard Purdie 2006-06-22 111 }
da5e108b0288d39 Guenter Roeck 2017-05-08 112 for (min = 1; min < MAXBITS; min++)
4f3865fb57a04db Richard Purdie 2006-06-22 113 if (count[min] != 0) break;
4f3865fb57a04db Richard Purdie 2006-06-22 114 if (root < min) root = min;
4f3865fb57a04db Richard Purdie 2006-06-22 115
4f3865fb57a04db Richard Purdie 2006-06-22 116 /* check for an over-subscribed or incomplete set of lengths */
4f3865fb57a04db Richard Purdie 2006-06-22 117 left = 1;
4f3865fb57a04db Richard Purdie 2006-06-22 118 for (len = 1; len <= MAXBITS; len++) {
4f3865fb57a04db Richard Purdie 2006-06-22 119 left <<= 1;
4f3865fb57a04db Richard Purdie 2006-06-22 120 left -= count[len];
4f3865fb57a04db Richard Purdie 2006-06-22 121 if (left < 0) return -1; /* over-subscribed */
4f3865fb57a04db Richard Purdie 2006-06-22 122 }
4f3865fb57a04db Richard Purdie 2006-06-22 123 if (left > 0 && (type == CODES || max != 1))
4f3865fb57a04db Richard Purdie 2006-06-22 124 return -1; /* incomplete set */
^1da177e4c3f415 Linus Torvalds 2005-04-16 125
4f3865fb57a04db Richard Purdie 2006-06-22 126 /* generate offsets into symbol table for each length for sorting */
4f3865fb57a04db Richard Purdie 2006-06-22 127 offs[1] = 0;
4f3865fb57a04db Richard Purdie 2006-06-22 128 for (len = 1; len < MAXBITS; len++)
4f3865fb57a04db Richard Purdie 2006-06-22 129 offs[len + 1] = offs[len] + count[len];
^1da177e4c3f415 Linus Torvalds 2005-04-16 130
4f3865fb57a04db Richard Purdie 2006-06-22 131 /* sort symbols by length, by symbol order within each length */
4f3865fb57a04db Richard Purdie 2006-06-22 132 for (sym = 0; sym < codes; sym++)
4f3865fb57a04db Richard Purdie 2006-06-22 133 if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
^1da177e4c3f415 Linus Torvalds 2005-04-16 134
4f3865fb57a04db Richard Purdie 2006-06-22 135 /*
4f3865fb57a04db Richard Purdie 2006-06-22 136 Create and fill in decoding tables. In this loop, the table being
4f3865fb57a04db Richard Purdie 2006-06-22 137 filled is at next and has curr index bits. The code being used is huff
4f3865fb57a04db Richard Purdie 2006-06-22 138 with length len. That code is converted to an index by dropping drop
4f3865fb57a04db Richard Purdie 2006-06-22 139 bits off of the bottom. For codes where len is less than drop + curr,
4f3865fb57a04db Richard Purdie 2006-06-22 140 those top drop + curr - len bits are incremented through all values to
4f3865fb57a04db Richard Purdie 2006-06-22 141 fill the table with replicated entries.
4f3865fb57a04db Richard Purdie 2006-06-22 142
4f3865fb57a04db Richard Purdie 2006-06-22 143 root is the number of index bits for the root table. When len exceeds
4f3865fb57a04db Richard Purdie 2006-06-22 144 root, sub-tables are created pointed to by the root entry with an index
4f3865fb57a04db Richard Purdie 2006-06-22 145 of the low root bits of huff. This is saved in low to check for when a
4f3865fb57a04db Richard Purdie 2006-06-22 146 new sub-table should be started. drop is zero when the root table is
4f3865fb57a04db Richard Purdie 2006-06-22 147 being filled, and drop is root when sub-tables are being filled.
4f3865fb57a04db Richard Purdie 2006-06-22 148
4f3865fb57a04db Richard Purdie 2006-06-22 149 When a new sub-table is needed, it is necessary to look ahead in the
4f3865fb57a04db Richard Purdie 2006-06-22 150 code lengths to determine what size sub-table is needed. The length
4f3865fb57a04db Richard Purdie 2006-06-22 151 counts are used for this, and so count[] is decremented as codes are
4f3865fb57a04db Richard Purdie 2006-06-22 152 entered in the tables.
4f3865fb57a04db Richard Purdie 2006-06-22 153
4f3865fb57a04db Richard Purdie 2006-06-22 154 used keeps track of how many table entries have been allocated from the
4f3865fb57a04db Richard Purdie 2006-06-22 155 provided *table space. It is checked when a LENS table is being made
4f3865fb57a04db Richard Purdie 2006-06-22 156 against the space in *table, ENOUGH, minus the maximum space needed by
4f3865fb57a04db Richard Purdie 2006-06-22 157 the worst case distance code, MAXD. This should never happen, but the
4f3865fb57a04db Richard Purdie 2006-06-22 158 sufficiency of ENOUGH has not been proven exhaustively, hence the check.
4f3865fb57a04db Richard Purdie 2006-06-22 159 This assumes that when type == LENS, bits == 9.
4f3865fb57a04db Richard Purdie 2006-06-22 160
4f3865fb57a04db Richard Purdie 2006-06-22 161 sym increments through all symbols, and the loop terminates when
4f3865fb57a04db Richard Purdie 2006-06-22 162 all codes of length max, i.e. all codes, have been processed. This
4f3865fb57a04db Richard Purdie 2006-06-22 163 routine permits incomplete codes, so another loop after this one fills
4f3865fb57a04db Richard Purdie 2006-06-22 164 in the rest of the decoding tables with invalid code markers.
4f3865fb57a04db Richard Purdie 2006-06-22 165 */
^1da177e4c3f415 Linus Torvalds 2005-04-16 166
4f3865fb57a04db Richard Purdie 2006-06-22 167 /* set up for code type */
4f3865fb57a04db Richard Purdie 2006-06-22 168 switch (type) {
4f3865fb57a04db Richard Purdie 2006-06-22 169 case CODES:
4f3865fb57a04db Richard Purdie 2006-06-22 170 base = extra = work; /* dummy value--not used */
4f3865fb57a04db Richard Purdie 2006-06-22 171 end = 19;
^1da177e4c3f415 Linus Torvalds 2005-04-16 172 break;
4f3865fb57a04db Richard Purdie 2006-06-22 173 case LENS:
4f3865fb57a04db Richard Purdie 2006-06-22 174 base = lbase;
4f3865fb57a04db Richard Purdie 2006-06-22 175 base -= 257;
4f3865fb57a04db Richard Purdie 2006-06-22 176 extra = lext;
4f3865fb57a04db Richard Purdie 2006-06-22 177 extra -= 257;
4f3865fb57a04db Richard Purdie 2006-06-22 178 end = 256;
^1da177e4c3f415 Linus Torvalds 2005-04-16 179 break;
4f3865fb57a04db Richard Purdie 2006-06-22 180 default: /* DISTS */
4f3865fb57a04db Richard Purdie 2006-06-22 181 base = dbase;
4f3865fb57a04db Richard Purdie 2006-06-22 182 extra = dext;
4f3865fb57a04db Richard Purdie 2006-06-22 183 end = -1;
^1da177e4c3f415 Linus Torvalds 2005-04-16 184 }
^1da177e4c3f415 Linus Torvalds 2005-04-16 185
4f3865fb57a04db Richard Purdie 2006-06-22 186 /* initialize state for loop */
4f3865fb57a04db Richard Purdie 2006-06-22 187 huff = 0; /* starting code */
4f3865fb57a04db Richard Purdie 2006-06-22 188 sym = 0; /* starting code symbol */
4f3865fb57a04db Richard Purdie 2006-06-22 189 len = min; /* starting code length */
4f3865fb57a04db Richard Purdie 2006-06-22 190 next = *table; /* current table to fill in */
4f3865fb57a04db Richard Purdie 2006-06-22 191 curr = root; /* current table index bits */
4f3865fb57a04db Richard Purdie 2006-06-22 192 drop = 0; /* current bits to drop from code for index */
4f3865fb57a04db Richard Purdie 2006-06-22 193 low = (unsigned)(-1); /* trigger new sub-table when len > root */
4f3865fb57a04db Richard Purdie 2006-06-22 194 used = 1U << root; /* use root table entries */
4f3865fb57a04db Richard Purdie 2006-06-22 195 mask = used - 1; /* mask for comparing low */
4f3865fb57a04db Richard Purdie 2006-06-22 196
4f3865fb57a04db Richard Purdie 2006-06-22 197 /* check available table space */
4f3865fb57a04db Richard Purdie 2006-06-22 198 if (type == LENS && used >= ENOUGH - MAXD)
4f3865fb57a04db Richard Purdie 2006-06-22 199 return 1;
4f3865fb57a04db Richard Purdie 2006-06-22 200
4f3865fb57a04db Richard Purdie 2006-06-22 201 /* process all codes and make table entries */
4f3865fb57a04db Richard Purdie 2006-06-22 202 for (;;) {
4f3865fb57a04db Richard Purdie 2006-06-22 203 /* create table entry */
4f3865fb57a04db Richard Purdie 2006-06-22 204 this.bits = (unsigned char)(len - drop);
4f3865fb57a04db Richard Purdie 2006-06-22 205 if ((int)(work[sym]) < end) {
4f3865fb57a04db Richard Purdie 2006-06-22 206 this.op = (unsigned char)0;
4f3865fb57a04db Richard Purdie 2006-06-22 207 this.val = work[sym];
^1da177e4c3f415 Linus Torvalds 2005-04-16 208 }
4f3865fb57a04db Richard Purdie 2006-06-22 209 else if ((int)(work[sym]) > end) {
4f3865fb57a04db Richard Purdie 2006-06-22 210 this.op = (unsigned char)(extra[work[sym]]);
4f3865fb57a04db Richard Purdie 2006-06-22 211 this.val = base[work[sym]];
^1da177e4c3f415 Linus Torvalds 2005-04-16 212 }
4f3865fb57a04db Richard Purdie 2006-06-22 213 else {
4f3865fb57a04db Richard Purdie 2006-06-22 214 this.op = (unsigned char)(32 + 64); /* end of block */
4f3865fb57a04db Richard Purdie 2006-06-22 215 this.val = 0;
^1da177e4c3f415 Linus Torvalds 2005-04-16 216 }
^1da177e4c3f415 Linus Torvalds 2005-04-16 217
4f3865fb57a04db Richard Purdie 2006-06-22 218 /* replicate for those indices with low len bits equal to huff */
4f3865fb57a04db Richard Purdie 2006-06-22 219 incr = 1U << (len - drop);
4f3865fb57a04db Richard Purdie 2006-06-22 220 fill = 1U << curr;
4f3865fb57a04db Richard Purdie 2006-06-22 221 min = fill; /* save offset to next table */
4f3865fb57a04db Richard Purdie 2006-06-22 222 do {
4f3865fb57a04db Richard Purdie 2006-06-22 223 fill -= incr;
4f3865fb57a04db Richard Purdie 2006-06-22 224 next[(huff >> drop) + fill] = this;
4f3865fb57a04db Richard Purdie 2006-06-22 225 } while (fill != 0);
4f3865fb57a04db Richard Purdie 2006-06-22 226
4f3865fb57a04db Richard Purdie 2006-06-22 227 /* backwards increment the len-bit code huff */
4f3865fb57a04db Richard Purdie 2006-06-22 228 incr = 1U << (len - 1);
4f3865fb57a04db Richard Purdie 2006-06-22 229 while (huff & incr)
4f3865fb57a04db Richard Purdie 2006-06-22 230 incr >>= 1;
4f3865fb57a04db Richard Purdie 2006-06-22 231 if (incr != 0) {
4f3865fb57a04db Richard Purdie 2006-06-22 232 huff &= incr - 1;
4f3865fb57a04db Richard Purdie 2006-06-22 233 huff += incr;
^1da177e4c3f415 Linus Torvalds 2005-04-16 234 }
^1da177e4c3f415 Linus Torvalds 2005-04-16 235 else
4f3865fb57a04db Richard Purdie 2006-06-22 236 huff = 0;
^1da177e4c3f415 Linus Torvalds 2005-04-16 237
4f3865fb57a04db Richard Purdie 2006-06-22 238 /* go to next symbol, update count, len */
4f3865fb57a04db Richard Purdie 2006-06-22 239 sym++;
4f3865fb57a04db Richard Purdie 2006-06-22 240 if (--(count[len]) == 0) {
4f3865fb57a04db Richard Purdie 2006-06-22 241 if (len == max) break;
4f3865fb57a04db Richard Purdie 2006-06-22 242 len = lens[work[sym]];
^1da177e4c3f415 Linus Torvalds 2005-04-16 243 }
^1da177e4c3f415 Linus Torvalds 2005-04-16 244
4f3865fb57a04db Richard Purdie 2006-06-22 245 /* create new sub-table if needed */
4f3865fb57a04db Richard Purdie 2006-06-22 246 if (len > root && (huff & mask) != low) {
4f3865fb57a04db Richard Purdie 2006-06-22 247 /* if first time, transition to sub-tables */
4f3865fb57a04db Richard Purdie 2006-06-22 248 if (drop == 0)
4f3865fb57a04db Richard Purdie 2006-06-22 249 drop = root;
4f3865fb57a04db Richard Purdie 2006-06-22 250
4f3865fb57a04db Richard Purdie 2006-06-22 251 /* increment past last table */
4f3865fb57a04db Richard Purdie 2006-06-22 252 next += min; /* here min is 1 << curr */
4f3865fb57a04db Richard Purdie 2006-06-22 253
4f3865fb57a04db Richard Purdie 2006-06-22 254 /* determine length of next table */
4f3865fb57a04db Richard Purdie 2006-06-22 255 curr = len - drop;
4f3865fb57a04db Richard Purdie 2006-06-22 256 left = (int)(1 << curr);
4f3865fb57a04db Richard Purdie 2006-06-22 257 while (curr + drop < max) {
4f3865fb57a04db Richard Purdie 2006-06-22 @258 left -= count[curr + drop];
:::::: The code at line 258 was first introduced by commit
:::::: 4f3865fb57a04db7cca068fed1c15badc064a302 [PATCH] zlib_inflate: Upgrade library code to a recent version
:::::: TO: Richard Purdie <rpurdie@...ys.net>
:::::: CC: Linus Torvalds <torvalds@...osdl.org>
---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all@lists.01.org
Download attachment ".config.gz" of type "application/gzip" (26371 bytes)
Powered by blists - more mailing lists