Geant4 Cross Reference

Cross-Referencing   Geant4
Geant4/externals/zlib/src/inffast.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/inffast.c (Version 11.3.0) and /externals/zlib/src/inffast.c (Version 11.2.2)


  1 /* inffast.c -- fast decoding                       1 /* inffast.c -- fast decoding
  2  * Copyright (C) 1995-2017 Mark Adler               2  * Copyright (C) 1995-2017 Mark Adler
  3  * For conditions of distribution and use, see      3  * For conditions of distribution and use, see copyright notice in zlib.h
  4  */                                                 4  */
  5                                                     5 
  6 #include "zutil.h"                                  6 #include "zutil.h"
  7 #include "inftrees.h"                               7 #include "inftrees.h"
  8 #include "inflate.h"                                8 #include "inflate.h"
  9 #include "inffast.h"                                9 #include "inffast.h"
 10                                                    10 
 11 #ifdef ASMINF                                      11 #ifdef ASMINF
 12 #  pragma message("Assembler code may have bug     12 #  pragma message("Assembler code may have bugs -- use at your own risk")
 13 #else                                              13 #else
 14                                                    14 
 15 /*                                                 15 /*
 16    Decode literal, length, and distance codes      16    Decode literal, length, and distance codes and write out the resulting
 17    literal and match bytes until either not en     17    literal and match bytes until either not enough input or output is
 18    available, an end-of-block is encountered,      18    available, an end-of-block is encountered, or a data error is encountered.
 19    When large enough input and output buffers      19    When large enough input and output buffers are supplied to inflate(), for
 20    example, a 16K input buffer and a 64K outpu     20    example, a 16K input buffer and a 64K output buffer, more than 95% of the
 21    inflate execution time is spent in this rou     21    inflate execution time is spent in this routine.
 22                                                    22 
 23    Entry assumptions:                              23    Entry assumptions:
 24                                                    24 
 25         state->mode == LEN                         25         state->mode == LEN
 26         strm->avail_in >= 6                        26         strm->avail_in >= 6
 27         strm->avail_out >= 258                     27         strm->avail_out >= 258
 28         start >= strm->avail_out                   28         start >= strm->avail_out
 29         state->bits < 8                            29         state->bits < 8
 30                                                    30 
 31    On return, state->mode is one of:               31    On return, state->mode is one of:
 32                                                    32 
 33         LEN -- ran out of enough output space      33         LEN -- ran out of enough output space or enough available input
 34         TYPE -- reached end of block code, inf     34         TYPE -- reached end of block code, inflate() to interpret next block
 35         BAD -- error in block data                 35         BAD -- error in block data
 36                                                    36 
 37    Notes:                                          37    Notes:
 38                                                    38 
 39     - The maximum input bits used by a length/     39     - The maximum input bits used by a length/distance pair is 15 bits for the
 40       length code, 5 bits for the length extra     40       length code, 5 bits for the length extra, 15 bits for the distance code,
 41       and 13 bits for the distance extra.  Thi     41       and 13 bits for the distance extra.  This totals 48 bits, or six bytes.
 42       Therefore if strm->avail_in >= 6, then t     42       Therefore if strm->avail_in >= 6, then there is enough input to avoid
 43       checking for available input while decod     43       checking for available input while decoding.
 44                                                    44 
 45     - The maximum bytes that a single length/d     45     - The maximum bytes that a single length/distance pair can output is 258
 46       bytes, which is the maximum length that      46       bytes, which is the maximum length that can be coded.  inflate_fast()
 47       requires strm->avail_out >= 258 for each     47       requires strm->avail_out >= 258 for each loop to avoid checking for
 48       output space.                                48       output space.
 49  */                                                49  */
 50 void ZLIB_INTERNAL inflate_fast(strm, start)       50 void ZLIB_INTERNAL inflate_fast(strm, start)
 51 z_streamp strm;                                    51 z_streamp strm;
 52 unsigned start;         /* inflate()'s startin     52 unsigned start;         /* inflate()'s starting value for strm->avail_out */
 53 {                                                  53 {
 54     struct inflate_state FAR *state;               54     struct inflate_state FAR *state;
 55     z_const unsigned char FAR *in;      /* loc     55     z_const unsigned char FAR *in;      /* local strm->next_in */
 56     z_const unsigned char FAR *last;    /* hav     56     z_const unsigned char FAR *last;    /* have enough input while in < last */
 57     unsigned char FAR *out;     /* local strm-     57     unsigned char FAR *out;     /* local strm->next_out */
 58     unsigned char FAR *beg;     /* inflate()'s     58     unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
 59     unsigned char FAR *end;     /* while out <     59     unsigned char FAR *end;     /* while out < end, enough space available */
 60 #ifdef INFLATE_STRICT                              60 #ifdef INFLATE_STRICT
 61     unsigned dmax;              /* maximum dis     61     unsigned dmax;              /* maximum distance from zlib header */
 62 #endif                                             62 #endif
 63     unsigned wsize;             /* window size     63     unsigned wsize;             /* window size or zero if not using window */
 64     unsigned whave;             /* valid bytes     64     unsigned whave;             /* valid bytes in the window */
 65     unsigned wnext;             /* window writ     65     unsigned wnext;             /* window write index */
 66     unsigned char FAR *window;  /* allocated s     66     unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
 67     unsigned long hold;         /* local strm-     67     unsigned long hold;         /* local strm->hold */
 68     unsigned bits;              /* local strm-     68     unsigned bits;              /* local strm->bits */
 69     code const FAR *lcode;      /* local strm-     69     code const FAR *lcode;      /* local strm->lencode */
 70     code const FAR *dcode;      /* local strm-     70     code const FAR *dcode;      /* local strm->distcode */
 71     unsigned lmask;             /* mask for fi     71     unsigned lmask;             /* mask for first level of length codes */
 72     unsigned dmask;             /* mask for fi     72     unsigned dmask;             /* mask for first level of distance codes */
 73     code const *here;           /* retrieved t     73     code const *here;           /* retrieved table entry */
 74     unsigned op;                /* code bits,      74     unsigned op;                /* code bits, operation, extra bits, or */
 75                                 /*  window pos     75                                 /*  window position, window bytes to copy */
 76     unsigned len;               /* match lengt     76     unsigned len;               /* match length, unused bytes */
 77     unsigned dist;              /* match dista     77     unsigned dist;              /* match distance */
 78     unsigned char FAR *from;    /* where to co     78     unsigned char FAR *from;    /* where to copy match from */
 79                                                    79 
 80     /* copy state to local variables */            80     /* copy state to local variables */
 81     state = (struct inflate_state FAR *)strm->     81     state = (struct inflate_state FAR *)strm->state;
 82     in = strm->next_in;                            82     in = strm->next_in;
 83     last = in + (strm->avail_in - 5);              83     last = in + (strm->avail_in - 5);
 84     out = strm->next_out;                          84     out = strm->next_out;
 85     beg = out - (start - strm->avail_out);         85     beg = out - (start - strm->avail_out);
 86     end = out + (strm->avail_out - 257);           86     end = out + (strm->avail_out - 257);
 87 #ifdef INFLATE_STRICT                              87 #ifdef INFLATE_STRICT
 88     dmax = state->dmax;                            88     dmax = state->dmax;
 89 #endif                                             89 #endif
 90     wsize = state->wsize;                          90     wsize = state->wsize;
 91     whave = state->whave;                          91     whave = state->whave;
 92     wnext = state->wnext;                          92     wnext = state->wnext;
 93     window = state->window;                        93     window = state->window;
 94     hold = state->hold;                            94     hold = state->hold;
 95     bits = state->bits;                            95     bits = state->bits;
 96     lcode = state->lencode;                        96     lcode = state->lencode;
 97     dcode = state->distcode;                       97     dcode = state->distcode;
 98     lmask = (1U << state->lenbits) - 1;            98     lmask = (1U << state->lenbits) - 1;
 99     dmask = (1U << state->distbits) - 1;           99     dmask = (1U << state->distbits) - 1;
100                                                   100 
101     /* decode literals and length/distances un    101     /* decode literals and length/distances until end-of-block or not enough
102        input data or output space */              102        input data or output space */
103     do {                                          103     do {
104         if (bits < 15) {                          104         if (bits < 15) {
105             hold += (unsigned long)(*in++) <<     105             hold += (unsigned long)(*in++) << bits;
106             bits += 8;                            106             bits += 8;
107             hold += (unsigned long)(*in++) <<     107             hold += (unsigned long)(*in++) << bits;
108             bits += 8;                            108             bits += 8;
109         }                                         109         }
110         here = lcode + (hold & lmask);            110         here = lcode + (hold & lmask);
111       dolen:                                      111       dolen:
112         op = (unsigned)(here->bits);              112         op = (unsigned)(here->bits);
113         hold >>= op;                              113         hold >>= op;
114         bits -= op;                               114         bits -= op;
115         op = (unsigned)(here->op);                115         op = (unsigned)(here->op);
116         if (op == 0) {                            116         if (op == 0) {                          /* literal */
117             Tracevv((stderr, here->val >= 0x20    117             Tracevv((stderr, here->val >= 0x20 && here->val < 0x7f ?
118                     "inflate:         literal     118                     "inflate:         literal '%c'\n" :
119                     "inflate:         literal     119                     "inflate:         literal 0x%02x\n", here->val));
120             *out++ = (unsigned char)(here->val    120             *out++ = (unsigned char)(here->val);
121         }                                         121         }
122         else if (op & 16) {                       122         else if (op & 16) {                     /* length base */
123             len = (unsigned)(here->val);          123             len = (unsigned)(here->val);
124             op &= 15;                             124             op &= 15;                           /* number of extra bits */
125             if (op) {                             125             if (op) {
126                 if (bits < op) {                  126                 if (bits < op) {
127                     hold += (unsigned long)(*i    127                     hold += (unsigned long)(*in++) << bits;
128                     bits += 8;                    128                     bits += 8;
129                 }                                 129                 }
130                 len += (unsigned)hold & ((1U <    130                 len += (unsigned)hold & ((1U << op) - 1);
131                 hold >>= op;                      131                 hold >>= op;
132                 bits -= op;                       132                 bits -= op;
133             }                                     133             }
134             Tracevv((stderr, "inflate:            134             Tracevv((stderr, "inflate:         length %u\n", len));
135             if (bits < 15) {                      135             if (bits < 15) {
136                 hold += (unsigned long)(*in++)    136                 hold += (unsigned long)(*in++) << bits;
137                 bits += 8;                        137                 bits += 8;
138                 hold += (unsigned long)(*in++)    138                 hold += (unsigned long)(*in++) << bits;
139                 bits += 8;                        139                 bits += 8;
140             }                                     140             }
141             here = dcode + (hold & dmask);        141             here = dcode + (hold & dmask);
142           dodist:                                 142           dodist:
143             op = (unsigned)(here->bits);          143             op = (unsigned)(here->bits);
144             hold >>= op;                          144             hold >>= op;
145             bits -= op;                           145             bits -= op;
146             op = (unsigned)(here->op);            146             op = (unsigned)(here->op);
147             if (op & 16) {                        147             if (op & 16) {                      /* distance base */
148                 dist = (unsigned)(here->val);     148                 dist = (unsigned)(here->val);
149                 op &= 15;                         149                 op &= 15;                       /* number of extra bits */
150                 if (bits < op) {                  150                 if (bits < op) {
151                     hold += (unsigned long)(*i    151                     hold += (unsigned long)(*in++) << bits;
152                     bits += 8;                    152                     bits += 8;
153                     if (bits < op) {              153                     if (bits < op) {
154                         hold += (unsigned long    154                         hold += (unsigned long)(*in++) << bits;
155                         bits += 8;                155                         bits += 8;
156                     }                             156                     }
157                 }                                 157                 }
158                 dist += (unsigned)hold & ((1U     158                 dist += (unsigned)hold & ((1U << op) - 1);
159 #ifdef INFLATE_STRICT                             159 #ifdef INFLATE_STRICT
160                 if (dist > dmax) {                160                 if (dist > dmax) {
161                     strm->msg = (char *)"inval    161                     strm->msg = (char *)"invalid distance too far back";
162                     state->mode = BAD;            162                     state->mode = BAD;
163                     break;                        163                     break;
164                 }                                 164                 }
165 #endif                                            165 #endif
166                 hold >>= op;                      166                 hold >>= op;
167                 bits -= op;                       167                 bits -= op;
168                 Tracevv((stderr, "inflate:        168                 Tracevv((stderr, "inflate:         distance %u\n", dist));
169                 op = (unsigned)(out - beg);       169                 op = (unsigned)(out - beg);     /* max distance in output */
170                 if (dist > op) {                  170                 if (dist > op) {                /* see if copy from window */
171                     op = dist - op;               171                     op = dist - op;             /* distance back in window */
172                     if (op > whave) {             172                     if (op > whave) {
173                         if (state->sane) {        173                         if (state->sane) {
174                             strm->msg =           174                             strm->msg =
175                                 (char *)"inval    175                                 (char *)"invalid distance too far back";
176                             state->mode = BAD;    176                             state->mode = BAD;
177                             break;                177                             break;
178                         }                         178                         }
179 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_A    179 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
180                         if (len <= op - whave)    180                         if (len <= op - whave) {
181                             do {                  181                             do {
182                                 *out++ = 0;       182                                 *out++ = 0;
183                             } while (--len);      183                             } while (--len);
184                             continue;             184                             continue;
185                         }                         185                         }
186                         len -= op - whave;        186                         len -= op - whave;
187                         do {                      187                         do {
188                             *out++ = 0;           188                             *out++ = 0;
189                         } while (--op > whave)    189                         } while (--op > whave);
190                         if (op == 0) {            190                         if (op == 0) {
191                             from = out - dist;    191                             from = out - dist;
192                             do {                  192                             do {
193                                 *out++ = *from    193                                 *out++ = *from++;
194                             } while (--len);      194                             } while (--len);
195                             continue;             195                             continue;
196                         }                         196                         }
197 #endif                                            197 #endif
198                     }                             198                     }
199                     from = window;                199                     from = window;
200                     if (wnext == 0) {             200                     if (wnext == 0) {           /* very common case */
201                         from += wsize - op;       201                         from += wsize - op;
202                         if (op < len) {           202                         if (op < len) {         /* some from window */
203                             len -= op;            203                             len -= op;
204                             do {                  204                             do {
205                                 *out++ = *from    205                                 *out++ = *from++;
206                             } while (--op);       206                             } while (--op);
207                             from = out - dist;    207                             from = out - dist;  /* rest from output */
208                         }                         208                         }
209                     }                             209                     }
210                     else if (wnext < op) {        210                     else if (wnext < op) {      /* wrap around window */
211                         from += wsize + wnext     211                         from += wsize + wnext - op;
212                         op -= wnext;              212                         op -= wnext;
213                         if (op < len) {           213                         if (op < len) {         /* some from end of window */
214                             len -= op;            214                             len -= op;
215                             do {                  215                             do {
216                                 *out++ = *from    216                                 *out++ = *from++;
217                             } while (--op);       217                             } while (--op);
218                             from = window;        218                             from = window;
219                             if (wnext < len) {    219                             if (wnext < len) {  /* some from start of window */
220                                 op = wnext;       220                                 op = wnext;
221                                 len -= op;        221                                 len -= op;
222                                 do {              222                                 do {
223                                     *out++ = *    223                                     *out++ = *from++;
224                                 } while (--op)    224                                 } while (--op);
225                                 from = out - d    225                                 from = out - dist;      /* rest from output */
226                             }                     226                             }
227                         }                         227                         }
228                     }                             228                     }
229                     else {                        229                     else {                      /* contiguous in window */
230                         from += wnext - op;       230                         from += wnext - op;
231                         if (op < len) {           231                         if (op < len) {         /* some from window */
232                             len -= op;            232                             len -= op;
233                             do {                  233                             do {
234                                 *out++ = *from    234                                 *out++ = *from++;
235                             } while (--op);       235                             } while (--op);
236                             from = out - dist;    236                             from = out - dist;  /* rest from output */
237                         }                         237                         }
238                     }                             238                     }
239                     while (len > 2) {             239                     while (len > 2) {
240                         *out++ = *from++;         240                         *out++ = *from++;
241                         *out++ = *from++;         241                         *out++ = *from++;
242                         *out++ = *from++;         242                         *out++ = *from++;
243                         len -= 3;                 243                         len -= 3;
244                     }                             244                     }
245                     if (len) {                    245                     if (len) {
246                         *out++ = *from++;         246                         *out++ = *from++;
247                         if (len > 1)              247                         if (len > 1)
248                             *out++ = *from++;     248                             *out++ = *from++;
249                     }                             249                     }
250                 }                                 250                 }
251                 else {                            251                 else {
252                     from = out - dist;            252                     from = out - dist;          /* copy direct from output */
253                     do {                          253                     do {                        /* minimum length is three */
254                         *out++ = *from++;         254                         *out++ = *from++;
255                         *out++ = *from++;         255                         *out++ = *from++;
256                         *out++ = *from++;         256                         *out++ = *from++;
257                         len -= 3;                 257                         len -= 3;
258                     } while (len > 2);            258                     } while (len > 2);
259                     if (len) {                    259                     if (len) {
260                         *out++ = *from++;         260                         *out++ = *from++;
261                         if (len > 1)              261                         if (len > 1)
262                             *out++ = *from++;     262                             *out++ = *from++;
263                     }                             263                     }
264                 }                                 264                 }
265             }                                     265             }
266             else if ((op & 64) == 0) {            266             else if ((op & 64) == 0) {          /* 2nd level distance code */
267                 here = dcode + here->val + (ho    267                 here = dcode + here->val + (hold & ((1U << op) - 1));
268                 goto dodist;                      268                 goto dodist;
269             }                                     269             }
270             else {                                270             else {
271                 strm->msg = (char *)"invalid d    271                 strm->msg = (char *)"invalid distance code";
272                 state->mode = BAD;                272                 state->mode = BAD;
273                 break;                            273                 break;
274             }                                     274             }
275         }                                         275         }
276         else if ((op & 64) == 0) {                276         else if ((op & 64) == 0) {              /* 2nd level length code */
277             here = lcode + here->val + (hold &    277             here = lcode + here->val + (hold & ((1U << op) - 1));
278             goto dolen;                           278             goto dolen;
279         }                                         279         }
280         else if (op & 32) {                       280         else if (op & 32) {                     /* end-of-block */
281             Tracevv((stderr, "inflate:            281             Tracevv((stderr, "inflate:         end of block\n"));
282             state->mode = TYPE;                   282             state->mode = TYPE;
283             break;                                283             break;
284         }                                         284         }
285         else {                                    285         else {
286             strm->msg = (char *)"invalid liter    286             strm->msg = (char *)"invalid literal/length code";
287             state->mode = BAD;                    287             state->mode = BAD;
288             break;                                288             break;
289         }                                         289         }
290     } while (in < last && out < end);             290     } while (in < last && out < end);
291                                                   291 
292     /* return unused bytes (on entry, bits < 8    292     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
293     len = bits >> 3;                              293     len = bits >> 3;
294     in -= len;                                    294     in -= len;
295     bits -= len << 3;                             295     bits -= len << 3;
296     hold &= (1U << bits) - 1;                     296     hold &= (1U << bits) - 1;
297                                                   297 
298     /* update state and return */                 298     /* update state and return */
299     strm->next_in = in;                           299     strm->next_in = in;
300     strm->next_out = out;                         300     strm->next_out = out;
301     strm->avail_in = (unsigned)(in < last ? 5     301     strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
302     strm->avail_out = (unsigned)(out < end ?      302     strm->avail_out = (unsigned)(out < end ?
303                                  257 + (end -     303                                  257 + (end - out) : 257 - (out - end));
304     state->hold = hold;                           304     state->hold = hold;
305     state->bits = bits;                           305     state->bits = bits;
306     return;                                       306     return;
307 }                                                 307 }
308                                                   308 
309 /*                                                309 /*
310    inflate_fast() speedups that turned out slo    310    inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
311    - Using bit fields for code structure          311    - Using bit fields for code structure
312    - Different op definition to avoid & for ex    312    - Different op definition to avoid & for extra bits (do & for table bits)
313    - Three separate decoding do-loops for dire    313    - Three separate decoding do-loops for direct, window, and wnext == 0
314    - Special case for distance > 1 copies to d    314    - Special case for distance > 1 copies to do overlapped load and store copy
315    - Explicit branch predictions (based on mea    315    - Explicit branch predictions (based on measured branch probabilities)
316    - Deferring match copy and interspersed it     316    - Deferring match copy and interspersed it with decoding subsequent codes
317    - Swapping literal/length else                 317    - Swapping literal/length else
318    - Swapping window/direct else                  318    - Swapping window/direct else
319    - Larger unrolled copy loops (three is abou    319    - Larger unrolled copy loops (three is about right)
320    - Moving len -= 3 statement into middle of     320    - Moving len -= 3 statement into middle of loop
321  */                                               321  */
322                                                   322 
323 #endif /* !ASMINF */                              323 #endif /* !ASMINF */
324                                                   324