LCOV - code coverage report
Current view: top level - lib/zlib_inflate - inftrees.c (source / functions) Hit Total Coverage
Test: landlock.info Lines: 0 135 0.0 %
Date: 2021-04-22 12:43:58 Functions: 0 1 0.0 %

          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           0 :     unsigned len;               /* a code's length in bits */
      27           0 :     unsigned sym;               /* index of code symbols */
      28           0 :     unsigned min, max;          /* minimum and maximum code lengths */
      29           0 :     unsigned root;              /* number of index bits for root table */
      30           0 :     unsigned curr;              /* number of index bits for current table */
      31           0 :     unsigned drop;              /* code bits to drop for sub-table */
      32           0 :     int left;                   /* number of prefix codes available */
      33           0 :     unsigned used;              /* code entries in table used */
      34           0 :     unsigned huff;              /* Huffman code */
      35           0 :     unsigned incr;              /* for incrementing code, index */
      36           0 :     unsigned fill;              /* index for replicating entries */
      37           0 :     unsigned low;               /* low bits for current root entry */
      38           0 :     unsigned mask;              /* mask for low root bits */
      39           0 :     code this;                  /* table entry for duplication */
      40           0 :     code *next;             /* next available space in table */
      41           0 :     const unsigned short *base;     /* base value table to use */
      42           0 :     const unsigned short *extra;    /* extra bits table to use */
      43           0 :     int end;                    /* use base and extra for symbol > end */
      44           0 :     unsigned short count[MAXBITS+1];    /* number of codes of each length */
      45           0 :     unsigned short offs[MAXBITS+1];     /* offsets in table for each length */
      46           0 :     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           0 :     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           0 :     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           0 :     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           0 :         this.op = (unsigned char)64;    /* invalid code marker */
     105           0 :         this.bits = (unsigned char)1;
     106           0 :         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           0 :     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             :         break;
     173           0 :     case LENS:
     174           0 :         base = lbase;
     175           0 :         base -= 257;
     176           0 :         extra = lext;
     177           0 :         extra -= 257;
     178           0 :         end = 256;
     179           0 :         break;
     180           0 :     default:            /* DISTS */
     181           0 :         base = dbase;
     182           0 :         extra = dext;
     183           0 :         end = -1;
     184             :     }
     185             : 
     186             :     /* initialize state for loop */
     187           0 :     huff = 0;                   /* starting code */
     188           0 :     sym = 0;                    /* starting code symbol */
     189           0 :     len = min;                  /* starting code length */
     190           0 :     next = *table;              /* current table to fill in */
     191           0 :     curr = root;                /* current table index bits */
     192           0 :     drop = 0;                   /* current bits to drop from code for index */
     193           0 :     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           0 :     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           0 :         min = fill;                 /* save offset to next table */
     222           0 :         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           0 :                 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           0 :             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           0 :     this.op = (unsigned char)64;                /* invalid code marker */
     285             :     this.bits = (unsigned char)(len - drop);
     286           0 :     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           0 :             drop = 0;
     291           0 :             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