Geant4 Cross Reference

Cross-Referencing   Geant4
Geant4/externals/zlib/src/inftrees.c

Version: [ ReleaseNotes ] [ 1.0 ] [ 1.1 ] [ 2.0 ] [ 3.0 ] [ 3.1 ] [ 3.2 ] [ 4.0 ] [ 4.0.p1 ] [ 4.0.p2 ] [ 4.1 ] [ 4.1.p1 ] [ 5.0 ] [ 5.0.p1 ] [ 5.1 ] [ 5.1.p1 ] [ 5.2 ] [ 5.2.p1 ] [ 5.2.p2 ] [ 6.0 ] [ 6.0.p1 ] [ 6.1 ] [ 6.2 ] [ 6.2.p1 ] [ 6.2.p2 ] [ 7.0 ] [ 7.0.p1 ] [ 7.1 ] [ 7.1.p1 ] [ 8.0 ] [ 8.0.p1 ] [ 8.1 ] [ 8.1.p1 ] [ 8.1.p2 ] [ 8.2 ] [ 8.2.p1 ] [ 8.3 ] [ 8.3.p1 ] [ 8.3.p2 ] [ 9.0 ] [ 9.0.p1 ] [ 9.0.p2 ] [ 9.1 ] [ 9.1.p1 ] [ 9.1.p2 ] [ 9.1.p3 ] [ 9.2 ] [ 9.2.p1 ] [ 9.2.p2 ] [ 9.2.p3 ] [ 9.2.p4 ] [ 9.3 ] [ 9.3.p1 ] [ 9.3.p2 ] [ 9.4 ] [ 9.4.p1 ] [ 9.4.p2 ] [ 9.4.p3 ] [ 9.4.p4 ] [ 9.5 ] [ 9.5.p1 ] [ 9.5.p2 ] [ 9.6 ] [ 9.6.p1 ] [ 9.6.p2 ] [ 9.6.p3 ] [ 9.6.p4 ] [ 10.0 ] [ 10.0.p1 ] [ 10.0.p2 ] [ 10.0.p3 ] [ 10.0.p4 ] [ 10.1 ] [ 10.1.p1 ] [ 10.1.p2 ] [ 10.1.p3 ] [ 10.2 ] [ 10.2.p1 ] [ 10.2.p2 ] [ 10.2.p3 ] [ 10.3 ] [ 10.3.p1 ] [ 10.3.p2 ] [ 10.3.p3 ] [ 10.4 ] [ 10.4.p1 ] [ 10.4.p2 ] [ 10.4.p3 ] [ 10.5 ] [ 10.5.p1 ] [ 10.6 ] [ 10.6.p1 ] [ 10.6.p2 ] [ 10.6.p3 ] [ 10.7 ] [ 10.7.p1 ] [ 10.7.p2 ] [ 10.7.p3 ] [ 10.7.p4 ] [ 11.0 ] [ 11.0.p1 ] [ 11.0.p2 ] [ 11.0.p3, ] [ 11.0.p4 ] [ 11.1 ] [ 11.1.1 ] [ 11.1.2 ] [ 11.1.3 ] [ 11.2 ] [ 11.2.1 ] [ 11.2.2 ] [ 11.3.0 ]

Diff markup

Differences between /externals/zlib/src/inftrees.c (Version 11.3.0) and /externals/zlib/src/inftrees.c (Version 9.6.p2)


  1 /* inftrees.c -- generate Huffman trees for ef      1 
  2  * Copyright (C) 1995-2022 Mark Adler             
  3  * For conditions of distribution and use, see    
  4  */                                               
  5                                                   
  6 #include "zutil.h"                                
  7 #include "inftrees.h"                             
  8                                                   
  9 #define MAXBITS 15                                
 10                                                   
 11 const char inflate_copyright[] =                  
 12    " inflate 1.2.13 Copyright 1995-2022 Mark A    
 13 /*                                                
 14   If you use the zlib library in a product, an    
 15   in the documentation of your product. If for    
 16   include such an acknowledgment, I would appr    
 17   copyright string in the executable of your p    
 18  */                                               
 19                                                   
 20 /*                                                
 21    Build a set of tables to decode the provide    
 22    The code lengths are lens[0..codes-1].  The    
 23    whose indices are 0..2^bits-1.  work is a w    
 24    lens shorts, which is used as a work area.     
 25    to be generated, CODES, LENS, or DISTS.  On    
 26    -1 is an invalid code, and +1 means that EN    
 27    on return points to the next available entr    
 28    requested root table index bits, and on ret    
 29    table index bits.  It will differ if the re    
 30    longest code or if it is less than the shor    
 31  */                                               
 32 int ZLIB_INTERNAL inflate_table(type, lens, co    
 33 codetype type;                                    
 34 unsigned short FAR *lens;                         
 35 unsigned codes;                                   
 36 code FAR * FAR *table;                            
 37 unsigned FAR *bits;                               
 38 unsigned short FAR *work;                         
 39 {                                                 
 40     unsigned len;               /* a code's le    
 41     unsigned sym;               /* index of co    
 42     unsigned min, max;          /* minimum and    
 43     unsigned root;              /* number of i    
 44     unsigned curr;              /* number of i    
 45     unsigned drop;              /* code bits t    
 46     int left;                   /* number of p    
 47     unsigned used;              /* code entrie    
 48     unsigned huff;              /* Huffman cod    
 49     unsigned incr;              /* for increme    
 50     unsigned fill;              /* index for r    
 51     unsigned low;               /* low bits fo    
 52     unsigned mask;              /* mask for lo    
 53     code here;                  /* table entry    
 54     code FAR *next;             /* next availa    
 55     const unsigned short FAR *base;     /* bas    
 56     const unsigned short FAR *extra;    /* ext    
 57     unsigned match;             /* use base an    
 58     unsigned short count[MAXBITS+1];    /* num    
 59     unsigned short offs[MAXBITS+1];     /* off    
 60     static const unsigned short lbase[31] = {     
 61         3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 1    
 62         35, 43, 51, 59, 67, 83, 99, 115, 131,     
 63     static const unsigned short lext[31] = { /    
 64         16, 16, 16, 16, 16, 16, 16, 16, 17, 17    
 65         19, 19, 19, 19, 20, 20, 20, 20, 21, 21    
 66     static const unsigned short dbase[32] = {     
 67         1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 4    
 68         257, 385, 513, 769, 1025, 1537, 2049,     
 69         8193, 12289, 16385, 24577, 0, 0};         
 70     static const unsigned short dext[32] = { /    
 71         16, 16, 16, 16, 17, 17, 18, 18, 19, 19    
 72         23, 23, 24, 24, 25, 25, 26, 26, 27, 27    
 73         28, 28, 29, 29, 64, 64};                  
 74                                                   
 75     /*                                            
 76        Process a set of code lengths to create    
 77        code lengths are lens[0..codes-1].  Eac    
 78        symbols 0..codes-1.  The Huffman code i    
 79        symbols by length from short to long, a    
 80        for codes with equal lengths.  Then the    
 81        for the first code of the shortest leng    
 82        increments for the same length, and zer    
 83        increases.  For the deflate format, the    
 84        from their more natural integer increme    
 85        decoding tables are built in the large     
 86        are incremented backwards.                 
 87                                                   
 88        This routine assumes, but does not chec    
 89        lens[] are in the range 0..MAXBITS.  Th    
 90        1..MAXBITS is interpreted as that code     
 91        symbol does not occur in this code.        
 92                                                   
 93        The codes are sorted by computing a cou    
 94        creating from that a table of starting     
 95        sorted table, and then entering the sym    
 96        table.  The sorted table is work[], wit    
 97        the caller.                                
 98                                                   
 99        The length counts are used for other pu    
100        the minimum and maximum length codes, d    
101        codes at all, checking for a valid set     
102        at length counts to determine sub-table    
103        decoding tables.                           
104      */                                           
105                                                   
106     /* accumulate lengths for codes (assumes l    
107     for (len = 0; len <= MAXBITS; len++)          
108         count[len] = 0;                           
109     for (sym = 0; sym < codes; sym++)             
110         count[lens[sym]]++;                       
111                                                   
112     /* bound code lengths, force root to be wi    
113     root = *bits;                                 
114     for (max = MAXBITS; max >= 1; max--)          
115         if (count[max] != 0) break;               
116     if (root > max) root = max;                   
117     if (max == 0) {                     /* no     
118         here.op = (unsigned char)64;    /* inv    
119         here.bits = (unsigned char)1;             
120         here.val = (unsigned short)0;             
121         *(*table)++ = here;             /* mak    
122         *(*table)++ = here;                       
123         *bits = 1;                                
124         return 0;     /* no symbols, but wait     
125     }                                             
126     for (min = 1; min < max; min++)               
127         if (count[min] != 0) break;               
128     if (root < min) root = min;                   
129                                                   
130     /* check for an over-subscribed or incompl    
131     left = 1;                                     
132     for (len = 1; len <= MAXBITS; len++) {        
133         left <<= 1;                               
134         left -= count[len];                       
135         if (left < 0) return -1;        /* ove    
136     }                                             
137     if (left > 0 && (type == CODES || max != 1    
138         return -1;                      /* inc    
139                                                   
140     /* generate offsets into symbol table for     
141     offs[1] = 0;                                  
142     for (len = 1; len < MAXBITS; len++)           
143         offs[len + 1] = offs[len] + count[len]    
144                                                   
145     /* sort symbols by length, by symbol order    
146     for (sym = 0; sym < codes; sym++)             
147         if (lens[sym] != 0) work[offs[lens[sym    
148                                                   
149     /*                                            
150        Create and fill in decoding tables.  In    
151        filled is at next and has curr index bi    
152        with length len.  That code is converte    
153        bits off of the bottom.  For codes wher    
154        those top drop + curr - len bits are in    
155        fill the table with replicated entries.    
156                                                   
157        root is the number of index bits for th    
158        root, sub-tables are created pointed to    
159        of the low root bits of huff.  This is     
160        new sub-table should be started.  drop     
161        being filled, and drop is root when sub    
162                                                   
163        When a new sub-table is needed, it is n    
164        code lengths to determine what size sub    
165        counts are used for this, and so count[    
166        entered in the tables.                     
167                                                   
168        used keeps track of how many table entr    
169        provided *table space.  It is checked f    
170        the constants ENOUGH_LENS and ENOUGH_DI    
171        the initial root table size constants.     
172        for more information.                      
173                                                   
174        sym increments through all symbols, and    
175        all codes of length max, i.e. all codes    
176        routine permits incomplete codes, so an    
177        in the rest of the decoding tables with    
178      */                                           
179                                                   
180     /* set up for code type */                    
181     switch (type) {                               
182     case CODES:                                   
183         base = extra = work;    /* dummy value    
184         match = 20;                               
185         break;                                    
186     case LENS:                                    
187         base = lbase;                             
188         extra = lext;                             
189         match = 257;                              
190         break;                                    
191     default:    /* DISTS */                       
192         base = dbase;                             
193         extra = dext;                             
194         match = 0;                                
195     }                                             
196                                                   
197     /* initialize state for loop */               
198     huff = 0;                   /* starting co    
199     sym = 0;                    /* starting co    
200     len = min;                  /* starting co    
201     next = *table;              /* current tab    
202     curr = root;                /* current tab    
203     drop = 0;                   /* current bit    
204     low = (unsigned)(-1);       /* trigger new    
205     used = 1U << root;          /* use root ta    
206     mask = used - 1;            /* mask for co    
207                                                   
208     /* check available table space */             
209     if ((type == LENS && used > ENOUGH_LENS) |    
210         (type == DISTS && used > ENOUGH_DISTS)    
211         return 1;                                 
212                                                   
213     /* process all codes and make table entrie    
214     for (;;) {                                    
215         /* create table entry */                  
216         here.bits = (unsigned char)(len - drop    
217         if (work[sym] + 1U < match) {             
218             here.op = (unsigned char)0;           
219             here.val = work[sym];                 
220         }                                         
221         else if (work[sym] >= match) {            
222             here.op = (unsigned char)(extra[wo    
223             here.val = base[work[sym] - match]    
224         }                                         
225         else {                                    
226             here.op = (unsigned char)(32 + 64)    
227             here.val = 0;                         
228         }                                         
229                                                   
230         /* replicate for those indices with lo    
231         incr = 1U << (len - drop);                
232         fill = 1U << curr;                        
233         min = fill;                 /* save of    
234         do {                                      
235             fill -= incr;                         
236             next[(huff >> drop) + fill] = here    
237         } while (fill != 0);                      
238                                                   
239         /* backwards increment the len-bit cod    
240         incr = 1U << (len - 1);                   
241         while (huff & incr)                       
242             incr >>= 1;                           
243         if (incr != 0) {                          
244             huff &= incr - 1;                     
245             huff += incr;                         
246         }                                         
247         else                                      
248             huff = 0;                             
249                                                   
250         /* go to next symbol, update count, le    
251         sym++;                                    
252         if (--(count[len]) == 0) {                
253             if (len == max) break;                
254             len = lens[work[sym]];                
255         }                                         
256                                                   
257         /* create new sub-table if needed */      
258         if (len > root && (huff & mask) != low    
259             /* if first time, transition to su    
260             if (drop == 0)                        
261                 drop = root;                      
262                                                   
263             /* increment past last table */       
264             next += min;            /* here mi    
265                                                   
266             /* determine length of next table     
267             curr = len - drop;                    
268             left = (int)(1 << curr);              
269             while (curr + drop < max) {           
270                 left -= count[curr + drop];       
271                 if (left <= 0) break;             
272                 curr++;                           
273                 left <<= 1;                       
274             }                                     
275                                                   
276             /* check for enough space */          
277             used += 1U << curr;                   
278             if ((type == LENS && used > ENOUGH    
279                 (type == DISTS && used > ENOUG    
280                 return 1;                         
281                                                   
282             /* point entry in root table to su    
283             low = huff & mask;                    
284             (*table)[low].op = (unsigned char)    
285             (*table)[low].bits = (unsigned cha    
286             (*table)[low].val = (unsigned shor    
287         }                                         
288     }                                             
289                                                   
290     /* fill in remaining table entry if code i    
291        at most one remaining entry, since if t    
292        maximum code length that was allowed to    
293     if (huff != 0) {                              
294         here.op = (unsigned char)64;              
295         here.bits = (unsigned char)(len - drop    
296         here.val = (unsigned short)0;             
297         next[huff] = here;                        
298     }                                             
299                                                   
300     /* set return parameters */                   
301     *table += used;                               
302     *bits = root;                                 
303     return 0;                                     
304 }                                                 
305