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@xxxxxxxxx> 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@xxxxxxxxx> :::::: CC: Linus Torvalds <torvalds@xxxxxxxxxxx> --- 0-DAY CI Kernel Test Service, Intel Corporation https://lists.01.org/hyperkitty/list/kbuild-all@xxxxxxxxxxxx
Attachment:
.config.gz
Description: application/gzip
