LCOV - code coverage report
Current view: top level - lib/zlib_inflate - inftrees.c (source / functions) Hit Total Coverage
Test: gcov_data_raspi2_real_modules_combined.info Lines: 0 84 0.0 %
Date: 2020-09-30 20:25:40 Functions: 0 1 0.0 %
Branches: 0 73 0.0 %

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

Generated by: LCOV version 1.14