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  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [day] [month] [year] [list]
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