Fossil

Hex Artifact Content
Login

Artifact fe2fdfb8f51d9f84881cc453ba64f60e3d7c9cbc:


0000: 2f 2a 20 69 6e 66 66 61 73 74 2e 63 20 2d 2d 20  /* inffast.c -- 
0010: 66 61 73 74 20 64 65 63 6f 64 69 6e 67 0a 20 2a  fast decoding. *
0020: 20 43 6f 70 79 72 69 67 68 74 20 28 43 29 20 31   Copyright (C) 1
0030: 39 39 35 2d 32 30 31 37 20 4d 61 72 6b 20 41 64  995-2017 Mark Ad
0040: 6c 65 72 0a 20 2a 20 46 6f 72 20 63 6f 6e 64 69  ler. * For condi
0050: 74 69 6f 6e 73 20 6f 66 20 64 69 73 74 72 69 62  tions of distrib
0060: 75 74 69 6f 6e 20 61 6e 64 20 75 73 65 2c 20 73  ution and use, s
0070: 65 65 20 63 6f 70 79 72 69 67 68 74 20 6e 6f 74  ee copyright not
0080: 69 63 65 20 69 6e 20 7a 6c 69 62 2e 68 0a 20 2a  ice in zlib.h. *
0090: 2f 0a 0a 23 69 6e 63 6c 75 64 65 20 22 7a 75 74  /..#include "zut
00a0: 69 6c 2e 68 22 0a 23 69 6e 63 6c 75 64 65 20 22  il.h".#include "
00b0: 69 6e 66 74 72 65 65 73 2e 68 22 0a 23 69 6e 63  inftrees.h".#inc
00c0: 6c 75 64 65 20 22 69 6e 66 6c 61 74 65 2e 68 22  lude "inflate.h"
00d0: 0a 23 69 6e 63 6c 75 64 65 20 22 69 6e 66 66 61  .#include "inffa
00e0: 73 74 2e 68 22 0a 0a 23 69 66 64 65 66 20 41 53  st.h"..#ifdef AS
00f0: 4d 49 4e 46 0a 23 20 20 70 72 61 67 6d 61 20 6d  MINF.#  pragma m
0100: 65 73 73 61 67 65 28 22 41 73 73 65 6d 62 6c 65  essage("Assemble
0110: 72 20 63 6f 64 65 20 6d 61 79 20 68 61 76 65 20  r code may have 
0120: 62 75 67 73 20 2d 2d 20 75 73 65 20 61 74 20 79  bugs -- use at y
0130: 6f 75 72 20 6f 77 6e 20 72 69 73 6b 22 29 0a 23  our own risk").#
0140: 65 6c 73 65 0a 0a 2f 2a 0a 20 20 20 44 65 63 6f  else../*.   Deco
0150: 64 65 20 6c 69 74 65 72 61 6c 2c 20 6c 65 6e 67  de literal, leng
0160: 74 68 2c 20 61 6e 64 20 64 69 73 74 61 6e 63 65  th, and distance
0170: 20 63 6f 64 65 73 20 61 6e 64 20 77 72 69 74 65   codes and write
0180: 20 6f 75 74 20 74 68 65 20 72 65 73 75 6c 74 69   out the resulti
0190: 6e 67 0a 20 20 20 6c 69 74 65 72 61 6c 20 61 6e  ng.   literal an
01a0: 64 20 6d 61 74 63 68 20 62 79 74 65 73 20 75 6e  d match bytes un
01b0: 74 69 6c 20 65 69 74 68 65 72 20 6e 6f 74 20 65  til either not e
01c0: 6e 6f 75 67 68 20 69 6e 70 75 74 20 6f 72 20 6f  nough input or o
01d0: 75 74 70 75 74 20 69 73 0a 20 20 20 61 76 61 69  utput is.   avai
01e0: 6c 61 62 6c 65 2c 20 61 6e 20 65 6e 64 2d 6f 66  lable, an end-of
01f0: 2d 62 6c 6f 63 6b 20 69 73 20 65 6e 63 6f 75 6e  -block is encoun
0200: 74 65 72 65 64 2c 20 6f 72 20 61 20 64 61 74 61  tered, or a data
0210: 20 65 72 72 6f 72 20 69 73 20 65 6e 63 6f 75 6e   error is encoun
0220: 74 65 72 65 64 2e 0a 20 20 20 57 68 65 6e 20 6c  tered..   When l
0230: 61 72 67 65 20 65 6e 6f 75 67 68 20 69 6e 70 75  arge enough inpu
0240: 74 20 61 6e 64 20 6f 75 74 70 75 74 20 62 75 66  t and output buf
0250: 66 65 72 73 20 61 72 65 20 73 75 70 70 6c 69 65  fers are supplie
0260: 64 20 74 6f 20 69 6e 66 6c 61 74 65 28 29 2c 20  d to inflate(), 
0270: 66 6f 72 0a 20 20 20 65 78 61 6d 70 6c 65 2c 20  for.   example, 
0280: 61 20 31 36 4b 20 69 6e 70 75 74 20 62 75 66 66  a 16K input buff
0290: 65 72 20 61 6e 64 20 61 20 36 34 4b 20 6f 75 74  er and a 64K out
02a0: 70 75 74 20 62 75 66 66 65 72 2c 20 6d 6f 72 65  put buffer, more
02b0: 20 74 68 61 6e 20 39 35 25 20 6f 66 20 74 68 65   than 95% of the
02c0: 0a 20 20 20 69 6e 66 6c 61 74 65 20 65 78 65 63  .   inflate exec
02d0: 75 74 69 6f 6e 20 74 69 6d 65 20 69 73 20 73 70  ution time is sp
02e0: 65 6e 74 20 69 6e 20 74 68 69 73 20 72 6f 75 74  ent in this rout
02f0: 69 6e 65 2e 0a 0a 20 20 20 45 6e 74 72 79 20 61  ine...   Entry a
0300: 73 73 75 6d 70 74 69 6f 6e 73 3a 0a 0a 20 20 20  ssumptions:..   
0310: 20 20 20 20 20 73 74 61 74 65 2d 3e 6d 6f 64 65       state->mode
0320: 20 3d 3d 20 4c 45 4e 0a 20 20 20 20 20 20 20 20   == LEN.        
0330: 73 74 72 6d 2d 3e 61 76 61 69 6c 5f 69 6e 20 3e  strm->avail_in >
0340: 3d 20 36 0a 20 20 20 20 20 20 20 20 73 74 72 6d  = 6.        strm
0350: 2d 3e 61 76 61 69 6c 5f 6f 75 74 20 3e 3d 20 32  ->avail_out >= 2
0360: 35 38 0a 20 20 20 20 20 20 20 20 73 74 61 72 74  58.        start
0370: 20 3e 3d 20 73 74 72 6d 2d 3e 61 76 61 69 6c 5f   >= strm->avail_
0380: 6f 75 74 0a 20 20 20 20 20 20 20 20 73 74 61 74  out.        stat
0390: 65 2d 3e 62 69 74 73 20 3c 20 38 0a 0a 20 20 20  e->bits < 8..   
03a0: 4f 6e 20 72 65 74 75 72 6e 2c 20 73 74 61 74 65  On return, state
03b0: 2d 3e 6d 6f 64 65 20 69 73 20 6f 6e 65 20 6f 66  ->mode is one of
03c0: 3a 0a 0a 20 20 20 20 20 20 20 20 4c 45 4e 20 2d  :..        LEN -
03d0: 2d 20 72 61 6e 20 6f 75 74 20 6f 66 20 65 6e 6f  - ran out of eno
03e0: 75 67 68 20 6f 75 74 70 75 74 20 73 70 61 63 65  ugh output space
03f0: 20 6f 72 20 65 6e 6f 75 67 68 20 61 76 61 69 6c   or enough avail
0400: 61 62 6c 65 20 69 6e 70 75 74 0a 20 20 20 20 20  able input.     
0410: 20 20 20 54 59 50 45 20 2d 2d 20 72 65 61 63 68     TYPE -- reach
0420: 65 64 20 65 6e 64 20 6f 66 20 62 6c 6f 63 6b 20  ed end of block 
0430: 63 6f 64 65 2c 20 69 6e 66 6c 61 74 65 28 29 20  code, inflate() 
0440: 74 6f 20 69 6e 74 65 72 70 72 65 74 20 6e 65 78  to interpret nex
0450: 74 20 62 6c 6f 63 6b 0a 20 20 20 20 20 20 20 20  t block.        
0460: 42 41 44 20 2d 2d 20 65 72 72 6f 72 20 69 6e 20  BAD -- error in 
0470: 62 6c 6f 63 6b 20 64 61 74 61 0a 0a 20 20 20 4e  block data..   N
0480: 6f 74 65 73 3a 0a 0a 20 20 20 20 2d 20 54 68 65  otes:..    - The
0490: 20 6d 61 78 69 6d 75 6d 20 69 6e 70 75 74 20 62   maximum input b
04a0: 69 74 73 20 75 73 65 64 20 62 79 20 61 20 6c 65  its used by a le
04b0: 6e 67 74 68 2f 64 69 73 74 61 6e 63 65 20 70 61  ngth/distance pa
04c0: 69 72 20 69 73 20 31 35 20 62 69 74 73 20 66 6f  ir is 15 bits fo
04d0: 72 20 74 68 65 0a 20 20 20 20 20 20 6c 65 6e 67  r the.      leng
04e0: 74 68 20 63 6f 64 65 2c 20 35 20 62 69 74 73 20  th code, 5 bits 
04f0: 66 6f 72 20 74 68 65 20 6c 65 6e 67 74 68 20 65  for the length e
0500: 78 74 72 61 2c 20 31 35 20 62 69 74 73 20 66 6f  xtra, 15 bits fo
0510: 72 20 74 68 65 20 64 69 73 74 61 6e 63 65 20 63  r the distance c
0520: 6f 64 65 2c 0a 20 20 20 20 20 20 61 6e 64 20 31  ode,.      and 1
0530: 33 20 62 69 74 73 20 66 6f 72 20 74 68 65 20 64  3 bits for the d
0540: 69 73 74 61 6e 63 65 20 65 78 74 72 61 2e 20 20  istance extra.  
0550: 54 68 69 73 20 74 6f 74 61 6c 73 20 34 38 20 62  This totals 48 b
0560: 69 74 73 2c 20 6f 72 20 73 69 78 20 62 79 74 65  its, or six byte
0570: 73 2e 0a 20 20 20 20 20 20 54 68 65 72 65 66 6f  s..      Therefo
0580: 72 65 20 69 66 20 73 74 72 6d 2d 3e 61 76 61 69  re if strm->avai
0590: 6c 5f 69 6e 20 3e 3d 20 36 2c 20 74 68 65 6e 20  l_in >= 6, then 
05a0: 74 68 65 72 65 20 69 73 20 65 6e 6f 75 67 68 20  there is enough 
05b0: 69 6e 70 75 74 20 74 6f 20 61 76 6f 69 64 0a 20  input to avoid. 
05c0: 20 20 20 20 20 63 68 65 63 6b 69 6e 67 20 66 6f       checking fo
05d0: 72 20 61 76 61 69 6c 61 62 6c 65 20 69 6e 70 75  r available inpu
05e0: 74 20 77 68 69 6c 65 20 64 65 63 6f 64 69 6e 67  t while decoding
05f0: 2e 0a 0a 20 20 20 20 2d 20 54 68 65 20 6d 61 78  ...    - The max
0600: 69 6d 75 6d 20 62 79 74 65 73 20 74 68 61 74 20  imum bytes that 
0610: 61 20 73 69 6e 67 6c 65 20 6c 65 6e 67 74 68 2f  a single length/
0620: 64 69 73 74 61 6e 63 65 20 70 61 69 72 20 63 61  distance pair ca
0630: 6e 20 6f 75 74 70 75 74 20 69 73 20 32 35 38 0a  n output is 258.
0640: 20 20 20 20 20 20 62 79 74 65 73 2c 20 77 68 69        bytes, whi
0650: 63 68 20 69 73 20 74 68 65 20 6d 61 78 69 6d 75  ch is the maximu
0660: 6d 20 6c 65 6e 67 74 68 20 74 68 61 74 20 63 61  m length that ca
0670: 6e 20 62 65 20 63 6f 64 65 64 2e 20 20 69 6e 66  n be coded.  inf
0680: 6c 61 74 65 5f 66 61 73 74 28 29 0a 20 20 20 20  late_fast().    
0690: 20 20 72 65 71 75 69 72 65 73 20 73 74 72 6d 2d    requires strm-
06a0: 3e 61 76 61 69 6c 5f 6f 75 74 20 3e 3d 20 32 35  >avail_out >= 25
06b0: 38 20 66 6f 72 20 65 61 63 68 20 6c 6f 6f 70 20  8 for each loop 
06c0: 74 6f 20 61 76 6f 69 64 20 63 68 65 63 6b 69 6e  to avoid checkin
06d0: 67 20 66 6f 72 0a 20 20 20 20 20 20 6f 75 74 70  g for.      outp
06e0: 75 74 20 73 70 61 63 65 2e 0a 20 2a 2f 0a 76 6f  ut space.. */.vo
06f0: 69 64 20 5a 4c 49 42 5f 49 4e 54 45 52 4e 41 4c  id ZLIB_INTERNAL
0700: 20 69 6e 66 6c 61 74 65 5f 66 61 73 74 28 73 74   inflate_fast(st
0710: 72 6d 2c 20 73 74 61 72 74 29 0a 7a 5f 73 74 72  rm, start).z_str
0720: 65 61 6d 70 20 73 74 72 6d 3b 0a 75 6e 73 69 67  eamp strm;.unsig
0730: 6e 65 64 20 73 74 61 72 74 3b 20 20 20 20 20 20  ned start;      
0740: 20 20 20 2f 2a 20 69 6e 66 6c 61 74 65 28 29 27     /* inflate()'
0750: 73 20 73 74 61 72 74 69 6e 67 20 76 61 6c 75 65  s starting value
0760: 20 66 6f 72 20 73 74 72 6d 2d 3e 61 76 61 69 6c   for strm->avail
0770: 5f 6f 75 74 20 2a 2f 0a 7b 0a 20 20 20 20 73 74  _out */.{.    st
0780: 72 75 63 74 20 69 6e 66 6c 61 74 65 5f 73 74 61  ruct inflate_sta
0790: 74 65 20 46 41 52 20 2a 73 74 61 74 65 3b 0a 20  te FAR *state;. 
07a0: 20 20 20 7a 5f 63 6f 6e 73 74 20 75 6e 73 69 67     z_const unsig
07b0: 6e 65 64 20 63 68 61 72 20 46 41 52 20 2a 69 6e  ned char FAR *in
07c0: 3b 20 20 20 20 20 20 2f 2a 20 6c 6f 63 61 6c 20  ;      /* local 
07d0: 73 74 72 6d 2d 3e 6e 65 78 74 5f 69 6e 20 2a 2f  strm->next_in */
07e0: 0a 20 20 20 20 7a 5f 63 6f 6e 73 74 20 75 6e 73  .    z_const uns
07f0: 69 67 6e 65 64 20 63 68 61 72 20 46 41 52 20 2a  igned char FAR *
0800: 6c 61 73 74 3b 20 20 20 20 2f 2a 20 68 61 76 65  last;    /* have
0810: 20 65 6e 6f 75 67 68 20 69 6e 70 75 74 20 77 68   enough input wh
0820: 69 6c 65 20 69 6e 20 3c 20 6c 61 73 74 20 2a 2f  ile in < last */
0830: 0a 20 20 20 20 75 6e 73 69 67 6e 65 64 20 63 68  .    unsigned ch
0840: 61 72 20 46 41 52 20 2a 6f 75 74 3b 20 20 20 20  ar FAR *out;    
0850: 20 2f 2a 20 6c 6f 63 61 6c 20 73 74 72 6d 2d 3e   /* local strm->
0860: 6e 65 78 74 5f 6f 75 74 20 2a 2f 0a 20 20 20 20  next_out */.    
0870: 75 6e 73 69 67 6e 65 64 20 63 68 61 72 20 46 41  unsigned char FA
0880: 52 20 2a 62 65 67 3b 20 20 20 20 20 2f 2a 20 69  R *beg;     /* i
0890: 6e 66 6c 61 74 65 28 29 27 73 20 69 6e 69 74 69  nflate()'s initi
08a0: 61 6c 20 73 74 72 6d 2d 3e 6e 65 78 74 5f 6f 75  al strm->next_ou
08b0: 74 20 2a 2f 0a 20 20 20 20 75 6e 73 69 67 6e 65  t */.    unsigne
08c0: 64 20 63 68 61 72 20 46 41 52 20 2a 65 6e 64 3b  d char FAR *end;
08d0: 20 20 20 20 20 2f 2a 20 77 68 69 6c 65 20 6f 75       /* while ou
08e0: 74 20 3c 20 65 6e 64 2c 20 65 6e 6f 75 67 68 20  t < end, enough 
08f0: 73 70 61 63 65 20 61 76 61 69 6c 61 62 6c 65 20  space available 
0900: 2a 2f 0a 23 69 66 64 65 66 20 49 4e 46 4c 41 54  */.#ifdef INFLAT
0910: 45 5f 53 54 52 49 43 54 0a 20 20 20 20 75 6e 73  E_STRICT.    uns
0920: 69 67 6e 65 64 20 64 6d 61 78 3b 20 20 20 20 20  igned dmax;     
0930: 20 20 20 20 20 20 20 20 20 2f 2a 20 6d 61 78 69           /* maxi
0940: 6d 75 6d 20 64 69 73 74 61 6e 63 65 20 66 72 6f  mum distance fro
0950: 6d 20 7a 6c 69 62 20 68 65 61 64 65 72 20 2a 2f  m zlib header */
0960: 0a 23 65 6e 64 69 66 0a 20 20 20 20 75 6e 73 69  .#endif.    unsi
0970: 67 6e 65 64 20 77 73 69 7a 65 3b 20 20 20 20 20  gned wsize;     
0980: 20 20 20 20 20 20 20 20 2f 2a 20 77 69 6e 64 6f          /* windo
0990: 77 20 73 69 7a 65 20 6f 72 20 7a 65 72 6f 20 69  w size or zero i
09a0: 66 20 6e 6f 74 20 75 73 69 6e 67 20 77 69 6e 64  f not using wind
09b0: 6f 77 20 2a 2f 0a 20 20 20 20 75 6e 73 69 67 6e  ow */.    unsign
09c0: 65 64 20 77 68 61 76 65 3b 20 20 20 20 20 20 20  ed whave;       
09d0: 20 20 20 20 20 20 2f 2a 20 76 61 6c 69 64 20 62        /* valid b
09e0: 79 74 65 73 20 69 6e 20 74 68 65 20 77 69 6e 64  ytes in the wind
09f0: 6f 77 20 2a 2f 0a 20 20 20 20 75 6e 73 69 67 6e  ow */.    unsign
0a00: 65 64 20 77 6e 65 78 74 3b 20 20 20 20 20 20 20  ed wnext;       
0a10: 20 20 20 20 20 20 2f 2a 20 77 69 6e 64 6f 77 20        /* window 
0a20: 77 72 69 74 65 20 69 6e 64 65 78 20 2a 2f 0a 20  write index */. 
0a30: 20 20 20 75 6e 73 69 67 6e 65 64 20 63 68 61 72     unsigned char
0a40: 20 46 41 52 20 2a 77 69 6e 64 6f 77 3b 20 20 2f   FAR *window;  /
0a50: 2a 20 61 6c 6c 6f 63 61 74 65 64 20 73 6c 69 64  * allocated slid
0a60: 69 6e 67 20 77 69 6e 64 6f 77 2c 20 69 66 20 77  ing window, if w
0a70: 73 69 7a 65 20 21 3d 20 30 20 2a 2f 0a 20 20 20  size != 0 */.   
0a80: 20 75 6e 73 69 67 6e 65 64 20 6c 6f 6e 67 20 68   unsigned long h
0a90: 6f 6c 64 3b 20 20 20 20 20 20 20 20 20 2f 2a 20  old;         /* 
0aa0: 6c 6f 63 61 6c 20 73 74 72 6d 2d 3e 68 6f 6c 64  local strm->hold
0ab0: 20 2a 2f 0a 20 20 20 20 75 6e 73 69 67 6e 65 64   */.    unsigned
0ac0: 20 62 69 74 73 3b 20 20 20 20 20 20 20 20 20 20   bits;          
0ad0: 20 20 20 20 2f 2a 20 6c 6f 63 61 6c 20 73 74 72      /* local str
0ae0: 6d 2d 3e 62 69 74 73 20 2a 2f 0a 20 20 20 20 63  m->bits */.    c
0af0: 6f 64 65 20 63 6f 6e 73 74 20 46 41 52 20 2a 6c  ode const FAR *l
0b00: 63 6f 64 65 3b 20 20 20 20 20 20 2f 2a 20 6c 6f  code;      /* lo
0b10: 63 61 6c 20 73 74 72 6d 2d 3e 6c 65 6e 63 6f 64  cal strm->lencod
0b20: 65 20 2a 2f 0a 20 20 20 20 63 6f 64 65 20 63 6f  e */.    code co
0b30: 6e 73 74 20 46 41 52 20 2a 64 63 6f 64 65 3b 20  nst FAR *dcode; 
0b40: 20 20 20 20 20 2f 2a 20 6c 6f 63 61 6c 20 73 74       /* local st
0b50: 72 6d 2d 3e 64 69 73 74 63 6f 64 65 20 2a 2f 0a  rm->distcode */.
0b60: 20 20 20 20 75 6e 73 69 67 6e 65 64 20 6c 6d 61      unsigned lma
0b70: 73 6b 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  sk;             
0b80: 2f 2a 20 6d 61 73 6b 20 66 6f 72 20 66 69 72 73  /* mask for firs
0b90: 74 20 6c 65 76 65 6c 20 6f 66 20 6c 65 6e 67 74  t level of lengt
0ba0: 68 20 63 6f 64 65 73 20 2a 2f 0a 20 20 20 20 75  h codes */.    u
0bb0: 6e 73 69 67 6e 65 64 20 64 6d 61 73 6b 3b 20 20  nsigned dmask;  
0bc0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 6d 61             /* ma
0bd0: 73 6b 20 66 6f 72 20 66 69 72 73 74 20 6c 65 76  sk for first lev
0be0: 65 6c 20 6f 66 20 64 69 73 74 61 6e 63 65 20 63  el of distance c
0bf0: 6f 64 65 73 20 2a 2f 0a 20 20 20 20 63 6f 64 65  odes */.    code
0c00: 20 68 65 72 65 3b 20 20 20 20 20 20 20 20 20 20   here;          
0c10: 20 20 20 20 20 20 20 20 2f 2a 20 72 65 74 72 69          /* retri
0c20: 65 76 65 64 20 74 61 62 6c 65 20 65 6e 74 72 79  eved table entry
0c30: 20 2a 2f 0a 20 20 20 20 75 6e 73 69 67 6e 65 64   */.    unsigned
0c40: 20 6f 70 3b 20 20 20 20 20 20 20 20 20 20 20 20   op;            
0c50: 20 20 20 20 2f 2a 20 63 6f 64 65 20 62 69 74 73      /* code bits
0c60: 2c 20 6f 70 65 72 61 74 69 6f 6e 2c 20 65 78 74  , operation, ext
0c70: 72 61 20 62 69 74 73 2c 20 6f 72 20 2a 2f 0a 20  ra bits, or */. 
0c80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0c90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
0ca0: 2a 20 20 77 69 6e 64 6f 77 20 70 6f 73 69 74 69  *  window positi
0cb0: 6f 6e 2c 20 77 69 6e 64 6f 77 20 62 79 74 65 73  on, window bytes
0cc0: 20 74 6f 20 63 6f 70 79 20 2a 2f 0a 20 20 20 20   to copy */.    
0cd0: 75 6e 73 69 67 6e 65 64 20 6c 65 6e 3b 20 20 20  unsigned len;   
0ce0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 6d              /* m
0cf0: 61 74 63 68 20 6c 65 6e 67 74 68 2c 20 75 6e 75  atch length, unu
0d00: 73 65 64 20 62 79 74 65 73 20 2a 2f 0a 20 20 20  sed bytes */.   
0d10: 20 75 6e 73 69 67 6e 65 64 20 64 69 73 74 3b 20   unsigned dist; 
0d20: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
0d30: 6d 61 74 63 68 20 64 69 73 74 61 6e 63 65 20 2a  match distance *
0d40: 2f 0a 20 20 20 20 75 6e 73 69 67 6e 65 64 20 63  /.    unsigned c
0d50: 68 61 72 20 46 41 52 20 2a 66 72 6f 6d 3b 20 20  har FAR *from;  
0d60: 20 20 2f 2a 20 77 68 65 72 65 20 74 6f 20 63 6f    /* where to co
0d70: 70 79 20 6d 61 74 63 68 20 66 72 6f 6d 20 2a 2f  py match from */
0d80: 0a 0a 20 20 20 20 2f 2a 20 63 6f 70 79 20 73 74  ..    /* copy st
0d90: 61 74 65 20 74 6f 20 6c 6f 63 61 6c 20 76 61 72  ate to local var
0da0: 69 61 62 6c 65 73 20 2a 2f 0a 20 20 20 20 73 74  iables */.    st
0db0: 61 74 65 20 3d 20 28 73 74 72 75 63 74 20 69 6e  ate = (struct in
0dc0: 66 6c 61 74 65 5f 73 74 61 74 65 20 46 41 52 20  flate_state FAR 
0dd0: 2a 29 73 74 72 6d 2d 3e 73 74 61 74 65 3b 0a 20  *)strm->state;. 
0de0: 20 20 20 69 6e 20 3d 20 73 74 72 6d 2d 3e 6e 65     in = strm->ne
0df0: 78 74 5f 69 6e 3b 0a 20 20 20 20 6c 61 73 74 20  xt_in;.    last 
0e00: 3d 20 69 6e 20 2b 20 28 73 74 72 6d 2d 3e 61 76  = in + (strm->av
0e10: 61 69 6c 5f 69 6e 20 2d 20 35 29 3b 0a 20 20 20  ail_in - 5);.   
0e20: 20 6f 75 74 20 3d 20 73 74 72 6d 2d 3e 6e 65 78   out = strm->nex
0e30: 74 5f 6f 75 74 3b 0a 20 20 20 20 62 65 67 20 3d  t_out;.    beg =
0e40: 20 6f 75 74 20 2d 20 28 73 74 61 72 74 20 2d 20   out - (start - 
0e50: 73 74 72 6d 2d 3e 61 76 61 69 6c 5f 6f 75 74 29  strm->avail_out)
0e60: 3b 0a 20 20 20 20 65 6e 64 20 3d 20 6f 75 74 20  ;.    end = out 
0e70: 2b 20 28 73 74 72 6d 2d 3e 61 76 61 69 6c 5f 6f  + (strm->avail_o
0e80: 75 74 20 2d 20 32 35 37 29 3b 0a 23 69 66 64 65  ut - 257);.#ifde
0e90: 66 20 49 4e 46 4c 41 54 45 5f 53 54 52 49 43 54  f INFLATE_STRICT
0ea0: 0a 20 20 20 20 64 6d 61 78 20 3d 20 73 74 61 74  .    dmax = stat
0eb0: 65 2d 3e 64 6d 61 78 3b 0a 23 65 6e 64 69 66 0a  e->dmax;.#endif.
0ec0: 20 20 20 20 77 73 69 7a 65 20 3d 20 73 74 61 74      wsize = stat
0ed0: 65 2d 3e 77 73 69 7a 65 3b 0a 20 20 20 20 77 68  e->wsize;.    wh
0ee0: 61 76 65 20 3d 20 73 74 61 74 65 2d 3e 77 68 61  ave = state->wha
0ef0: 76 65 3b 0a 20 20 20 20 77 6e 65 78 74 20 3d 20  ve;.    wnext = 
0f00: 73 74 61 74 65 2d 3e 77 6e 65 78 74 3b 0a 20 20  state->wnext;.  
0f10: 20 20 77 69 6e 64 6f 77 20 3d 20 73 74 61 74 65    window = state
0f20: 2d 3e 77 69 6e 64 6f 77 3b 0a 20 20 20 20 68 6f  ->window;.    ho
0f30: 6c 64 20 3d 20 73 74 61 74 65 2d 3e 68 6f 6c 64  ld = state->hold
0f40: 3b 0a 20 20 20 20 62 69 74 73 20 3d 20 73 74 61  ;.    bits = sta
0f50: 74 65 2d 3e 62 69 74 73 3b 0a 20 20 20 20 6c 63  te->bits;.    lc
0f60: 6f 64 65 20 3d 20 73 74 61 74 65 2d 3e 6c 65 6e  ode = state->len
0f70: 63 6f 64 65 3b 0a 20 20 20 20 64 63 6f 64 65 20  code;.    dcode 
0f80: 3d 20 73 74 61 74 65 2d 3e 64 69 73 74 63 6f 64  = state->distcod
0f90: 65 3b 0a 20 20 20 20 6c 6d 61 73 6b 20 3d 20 28  e;.    lmask = (
0fa0: 31 55 20 3c 3c 20 73 74 61 74 65 2d 3e 6c 65 6e  1U << state->len
0fb0: 62 69 74 73 29 20 2d 20 31 3b 0a 20 20 20 20 64  bits) - 1;.    d
0fc0: 6d 61 73 6b 20 3d 20 28 31 55 20 3c 3c 20 73 74  mask = (1U << st
0fd0: 61 74 65 2d 3e 64 69 73 74 62 69 74 73 29 20 2d  ate->distbits) -
0fe0: 20 31 3b 0a 0a 20 20 20 20 2f 2a 20 64 65 63 6f   1;..    /* deco
0ff0: 64 65 20 6c 69 74 65 72 61 6c 73 20 61 6e 64 20  de literals and 
1000: 6c 65 6e 67 74 68 2f 64 69 73 74 61 6e 63 65 73  length/distances
1010: 20 75 6e 74 69 6c 20 65 6e 64 2d 6f 66 2d 62 6c   until end-of-bl
1020: 6f 63 6b 20 6f 72 20 6e 6f 74 20 65 6e 6f 75 67  ock or not enoug
1030: 68 0a 20 20 20 20 20 20 20 69 6e 70 75 74 20 64  h.       input d
1040: 61 74 61 20 6f 72 20 6f 75 74 70 75 74 20 73 70  ata or output sp
1050: 61 63 65 20 2a 2f 0a 20 20 20 20 64 6f 20 7b 0a  ace */.    do {.
1060: 20 20 20 20 20 20 20 20 69 66 20 28 62 69 74 73          if (bits
1070: 20 3c 20 31 35 29 20 7b 0a 20 20 20 20 20 20 20   < 15) {.       
1080: 20 20 20 20 20 68 6f 6c 64 20 2b 3d 20 28 75 6e       hold += (un
1090: 73 69 67 6e 65 64 20 6c 6f 6e 67 29 28 2a 69 6e  signed long)(*in
10a0: 2b 2b 29 20 3c 3c 20 62 69 74 73 3b 0a 20 20 20  ++) << bits;.   
10b0: 20 20 20 20 20 20 20 20 20 62 69 74 73 20 2b 3d           bits +=
10c0: 20 38 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20   8;.            
10d0: 68 6f 6c 64 20 2b 3d 20 28 75 6e 73 69 67 6e 65  hold += (unsigne
10e0: 64 20 6c 6f 6e 67 29 28 2a 69 6e 2b 2b 29 20 3c  d long)(*in++) <
10f0: 3c 20 62 69 74 73 3b 0a 20 20 20 20 20 20 20 20  < bits;.        
1100: 20 20 20 20 62 69 74 73 20 2b 3d 20 38 3b 0a 20      bits += 8;. 
1110: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20         }.       
1120: 20 68 65 72 65 20 3d 20 6c 63 6f 64 65 5b 68 6f   here = lcode[ho
1130: 6c 64 20 26 20 6c 6d 61 73 6b 5d 3b 0a 20 20 20  ld & lmask];.   
1140: 20 20 20 64 6f 6c 65 6e 3a 0a 20 20 20 20 20 20     dolen:.      
1150: 20 20 6f 70 20 3d 20 28 75 6e 73 69 67 6e 65 64    op = (unsigned
1160: 29 28 68 65 72 65 2e 62 69 74 73 29 3b 0a 20 20  )(here.bits);.  
1170: 20 20 20 20 20 20 68 6f 6c 64 20 3e 3e 3d 20 6f        hold >>= o
1180: 70 3b 0a 20 20 20 20 20 20 20 20 62 69 74 73 20  p;.        bits 
1190: 2d 3d 20 6f 70 3b 0a 20 20 20 20 20 20 20 20 6f  -= op;.        o
11a0: 70 20 3d 20 28 75 6e 73 69 67 6e 65 64 29 28 68  p = (unsigned)(h
11b0: 65 72 65 2e 6f 70 29 3b 0a 20 20 20 20 20 20 20  ere.op);.       
11c0: 20 69 66 20 28 6f 70 20 3d 3d 20 30 29 20 7b 20   if (op == 0) { 
11d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
11e0: 20 20 20 20 20 20 20 20 20 2f 2a 20 6c 69 74 65           /* lite
11f0: 72 61 6c 20 2a 2f 0a 20 20 20 20 20 20 20 20 20  ral */.         
1200: 20 20 20 54 72 61 63 65 76 76 28 28 73 74 64 65     Tracevv((stde
1210: 72 72 2c 20 68 65 72 65 2e 76 61 6c 20 3e 3d 20  rr, here.val >= 
1220: 30 78 32 30 20 26 26 20 68 65 72 65 2e 76 61 6c  0x20 && here.val
1230: 20 3c 20 30 78 37 66 20 3f 0a 20 20 20 20 20 20   < 0x7f ?.      
1240: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 22 69                "i
1250: 6e 66 6c 61 74 65 3a 20 20 20 20 20 20 20 20 20  nflate:         
1260: 6c 69 74 65 72 61 6c 20 27 25 63 27 5c 6e 22 20  literal '%c'\n" 
1270: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
1280: 20 20 20 20 20 20 22 69 6e 66 6c 61 74 65 3a 20        "inflate: 
1290: 20 20 20 20 20 20 20 20 6c 69 74 65 72 61 6c 20          literal 
12a0: 30 78 25 30 32 78 5c 6e 22 2c 20 68 65 72 65 2e  0x%02x\n", here.
12b0: 76 61 6c 29 29 3b 0a 20 20 20 20 20 20 20 20 20  val));.         
12c0: 20 20 20 2a 6f 75 74 2b 2b 20 3d 20 28 75 6e 73     *out++ = (uns
12d0: 69 67 6e 65 64 20 63 68 61 72 29 28 68 65 72 65  igned char)(here
12e0: 2e 76 61 6c 29 3b 0a 20 20 20 20 20 20 20 20 7d  .val);.        }
12f0: 0a 20 20 20 20 20 20 20 20 65 6c 73 65 20 69 66  .        else if
1300: 20 28 6f 70 20 26 20 31 36 29 20 7b 20 20 20 20   (op & 16) {    
1310: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1320: 20 2f 2a 20 6c 65 6e 67 74 68 20 62 61 73 65 20   /* length base 
1330: 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 20 20 6c  */.            l
1340: 65 6e 20 3d 20 28 75 6e 73 69 67 6e 65 64 29 28  en = (unsigned)(
1350: 68 65 72 65 2e 76 61 6c 29 3b 0a 20 20 20 20 20  here.val);.     
1360: 20 20 20 20 20 20 20 6f 70 20 26 3d 20 31 35 3b         op &= 15;
1370: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1380: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 6e 75             /* nu
1390: 6d 62 65 72 20 6f 66 20 65 78 74 72 61 20 62 69  mber of extra bi
13a0: 74 73 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20  ts */.          
13b0: 20 20 69 66 20 28 6f 70 29 20 7b 0a 20 20 20 20    if (op) {.    
13c0: 20 20 20 20 20 20 20 20 20 20 20 20 69 66 20 28              if (
13d0: 62 69 74 73 20 3c 20 6f 70 29 20 7b 0a 20 20 20  bits < op) {.   
13e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
13f0: 20 68 6f 6c 64 20 2b 3d 20 28 75 6e 73 69 67 6e   hold += (unsign
1400: 65 64 20 6c 6f 6e 67 29 28 2a 69 6e 2b 2b 29 20  ed long)(*in++) 
1410: 3c 3c 20 62 69 74 73 3b 0a 20 20 20 20 20 20 20  << bits;.       
1420: 20 20 20 20 20 20 20 20 20 20 20 20 20 62 69 74               bit
1430: 73 20 2b 3d 20 38 3b 0a 20 20 20 20 20 20 20 20  s += 8;.        
1440: 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20          }.      
1450: 20 20 20 20 20 20 20 20 20 20 6c 65 6e 20 2b 3d            len +=
1460: 20 28 75 6e 73 69 67 6e 65 64 29 68 6f 6c 64 20   (unsigned)hold 
1470: 26 20 28 28 31 55 20 3c 3c 20 6f 70 29 20 2d 20  & ((1U << op) - 
1480: 31 29 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20  1);.            
1490: 20 20 20 20 68 6f 6c 64 20 3e 3e 3d 20 6f 70 3b      hold >>= op;
14a0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
14b0: 20 62 69 74 73 20 2d 3d 20 6f 70 3b 0a 20 20 20   bits -= op;.   
14c0: 20 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20           }.     
14d0: 20 20 20 20 20 20 20 54 72 61 63 65 76 76 28 28         Tracevv((
14e0: 73 74 64 65 72 72 2c 20 22 69 6e 66 6c 61 74 65  stderr, "inflate
14f0: 3a 20 20 20 20 20 20 20 20 20 6c 65 6e 67 74 68  :         length
1500: 20 25 75 5c 6e 22 2c 20 6c 65 6e 29 29 3b 0a 20   %u\n", len));. 
1510: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 28 62             if (b
1520: 69 74 73 20 3c 20 31 35 29 20 7b 0a 20 20 20 20  its < 15) {.    
1530: 20 20 20 20 20 20 20 20 20 20 20 20 68 6f 6c 64              hold
1540: 20 2b 3d 20 28 75 6e 73 69 67 6e 65 64 20 6c 6f   += (unsigned lo
1550: 6e 67 29 28 2a 69 6e 2b 2b 29 20 3c 3c 20 62 69  ng)(*in++) << bi
1560: 74 73 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20  ts;.            
1570: 20 20 20 20 62 69 74 73 20 2b 3d 20 38 3b 0a 20      bits += 8;. 
1580: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 68                 h
1590: 6f 6c 64 20 2b 3d 20 28 75 6e 73 69 67 6e 65 64  old += (unsigned
15a0: 20 6c 6f 6e 67 29 28 2a 69 6e 2b 2b 29 20 3c 3c   long)(*in++) <<
15b0: 20 62 69 74 73 3b 0a 20 20 20 20 20 20 20 20 20   bits;.         
15c0: 20 20 20 20 20 20 20 62 69 74 73 20 2b 3d 20 38         bits += 8
15d0: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a  ;.            }.
15e0: 20 20 20 20 20 20 20 20 20 20 20 20 68 65 72 65              here
15f0: 20 3d 20 64 63 6f 64 65 5b 68 6f 6c 64 20 26 20   = dcode[hold & 
1600: 64 6d 61 73 6b 5d 3b 0a 20 20 20 20 20 20 20 20  dmask];.        
1610: 20 20 64 6f 64 69 73 74 3a 0a 20 20 20 20 20 20    dodist:.      
1620: 20 20 20 20 20 20 6f 70 20 3d 20 28 75 6e 73 69        op = (unsi
1630: 67 6e 65 64 29 28 68 65 72 65 2e 62 69 74 73 29  gned)(here.bits)
1640: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 68 6f  ;.            ho
1650: 6c 64 20 3e 3e 3d 20 6f 70 3b 0a 20 20 20 20 20  ld >>= op;.     
1660: 20 20 20 20 20 20 20 62 69 74 73 20 2d 3d 20 6f         bits -= o
1670: 70 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 6f  p;.            o
1680: 70 20 3d 20 28 75 6e 73 69 67 6e 65 64 29 28 68  p = (unsigned)(h
1690: 65 72 65 2e 6f 70 29 3b 0a 20 20 20 20 20 20 20  ere.op);.       
16a0: 20 20 20 20 20 69 66 20 28 6f 70 20 26 20 31 36       if (op & 16
16b0: 29 20 7b 20 20 20 20 20 20 20 20 20 20 20 20 20  ) {             
16c0: 20 20 20 20 20 20 20 20 20 2f 2a 20 64 69 73 74           /* dist
16d0: 61 6e 63 65 20 62 61 73 65 20 2a 2f 0a 20 20 20  ance base */.   
16e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 64 69 73               dis
16f0: 74 20 3d 20 28 75 6e 73 69 67 6e 65 64 29 28 68  t = (unsigned)(h
1700: 65 72 65 2e 76 61 6c 29 3b 0a 20 20 20 20 20 20  ere.val);.      
1710: 20 20 20 20 20 20 20 20 20 20 6f 70 20 26 3d 20            op &= 
1720: 31 35 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  15;             
1730: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 6e 75 6d            /* num
1740: 62 65 72 20 6f 66 20 65 78 74 72 61 20 62 69 74  ber of extra bit
1750: 73 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 20  s */.           
1760: 20 20 20 20 20 69 66 20 28 62 69 74 73 20 3c 20       if (bits < 
1770: 6f 70 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20  op) {.          
1780: 20 20 20 20 20 20 20 20 20 20 68 6f 6c 64 20 2b            hold +
1790: 3d 20 28 75 6e 73 69 67 6e 65 64 20 6c 6f 6e 67  = (unsigned long
17a0: 29 28 2a 69 6e 2b 2b 29 20 3c 3c 20 62 69 74 73  )(*in++) << bits
17b0: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;.              
17c0: 20 20 20 20 20 20 62 69 74 73 20 2b 3d 20 38 3b        bits += 8;
17d0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
17e0: 20 20 20 20 20 69 66 20 28 62 69 74 73 20 3c 20       if (bits < 
17f0: 6f 70 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20  op) {.          
1800: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 68 6f                ho
1810: 6c 64 20 2b 3d 20 28 75 6e 73 69 67 6e 65 64 20  ld += (unsigned 
1820: 6c 6f 6e 67 29 28 2a 69 6e 2b 2b 29 20 3c 3c 20  long)(*in++) << 
1830: 62 69 74 73 3b 0a 20 20 20 20 20 20 20 20 20 20  bits;.          
1840: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 62 69                bi
1850: 74 73 20 2b 3d 20 38 3b 0a 20 20 20 20 20 20 20  ts += 8;.       
1860: 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a 20               }. 
1870: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 7d                 }
1880: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1890: 20 64 69 73 74 20 2b 3d 20 28 75 6e 73 69 67 6e   dist += (unsign
18a0: 65 64 29 68 6f 6c 64 20 26 20 28 28 31 55 20 3c  ed)hold & ((1U <
18b0: 3c 20 6f 70 29 20 2d 20 31 29 3b 0a 23 69 66 64  < op) - 1);.#ifd
18c0: 65 66 20 49 4e 46 4c 41 54 45 5f 53 54 52 49 43  ef INFLATE_STRIC
18d0: 54 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  T.              
18e0: 20 20 69 66 20 28 64 69 73 74 20 3e 20 64 6d 61    if (dist > dma
18f0: 78 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20  x) {.           
1900: 20 20 20 20 20 20 20 20 20 73 74 72 6d 2d 3e 6d           strm->m
1910: 73 67 20 3d 20 28 63 68 61 72 20 2a 29 22 69 6e  sg = (char *)"in
1920: 76 61 6c 69 64 20 64 69 73 74 61 6e 63 65 20 74  valid distance t
1930: 6f 6f 20 66 61 72 20 62 61 63 6b 22 3b 0a 20 20  oo far back";.  
1940: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1950: 20 20 73 74 61 74 65 2d 3e 6d 6f 64 65 20 3d 20    state->mode = 
1960: 42 41 44 3b 0a 20 20 20 20 20 20 20 20 20 20 20  BAD;.           
1970: 20 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a           break;.
1980: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1990: 7d 0a 23 65 6e 64 69 66 0a 20 20 20 20 20 20 20  }.#endif.       
19a0: 20 20 20 20 20 20 20 20 20 68 6f 6c 64 20 3e 3e           hold >>
19b0: 3d 20 6f 70 3b 0a 20 20 20 20 20 20 20 20 20 20  = op;.          
19c0: 20 20 20 20 20 20 62 69 74 73 20 2d 3d 20 6f 70        bits -= op
19d0: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;.              
19e0: 20 20 54 72 61 63 65 76 76 28 28 73 74 64 65 72    Tracevv((stder
19f0: 72 2c 20 22 69 6e 66 6c 61 74 65 3a 20 20 20 20  r, "inflate:    
1a00: 20 20 20 20 20 64 69 73 74 61 6e 63 65 20 25 75       distance %u
1a10: 5c 6e 22 2c 20 64 69 73 74 29 29 3b 0a 20 20 20  \n", dist));.   
1a20: 20 20 20 20 20 20 20 20 20 20 20 20 20 6f 70 20               op 
1a30: 3d 20 28 75 6e 73 69 67 6e 65 64 29 28 6f 75 74  = (unsigned)(out
1a40: 20 2d 20 62 65 67 29 3b 20 20 20 20 20 2f 2a 20   - beg);     /* 
1a50: 6d 61 78 20 64 69 73 74 61 6e 63 65 20 69 6e 20  max distance in 
1a60: 6f 75 74 70 75 74 20 2a 2f 0a 20 20 20 20 20 20  output */.      
1a70: 20 20 20 20 20 20 20 20 20 20 69 66 20 28 64 69            if (di
1a80: 73 74 20 3e 20 6f 70 29 20 7b 20 20 20 20 20 20  st > op) {      
1a90: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 73 65 65            /* see
1aa0: 20 69 66 20 63 6f 70 79 20 66 72 6f 6d 20 77 69   if copy from wi
1ab0: 6e 64 6f 77 20 2a 2f 0a 20 20 20 20 20 20 20 20  ndow */.        
1ac0: 20 20 20 20 20 20 20 20 20 20 20 20 6f 70 20 3d              op =
1ad0: 20 64 69 73 74 20 2d 20 6f 70 3b 20 20 20 20 20   dist - op;     
1ae0: 20 20 20 20 20 20 20 20 2f 2a 20 64 69 73 74 61          /* dista
1af0: 6e 63 65 20 62 61 63 6b 20 69 6e 20 77 69 6e 64  nce back in wind
1b00: 6f 77 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20  ow */.          
1b10: 20 20 20 20 20 20 20 20 20 20 69 66 20 28 6f 70            if (op
1b20: 20 3e 20 77 68 61 76 65 29 20 7b 0a 20 20 20 20   > whave) {.    
1b30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1b40: 20 20 20 20 69 66 20 28 73 74 61 74 65 2d 3e 73      if (state->s
1b50: 61 6e 65 29 20 7b 0a 20 20 20 20 20 20 20 20 20  ane) {.         
1b60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1b70: 20 20 20 73 74 72 6d 2d 3e 6d 73 67 20 3d 0a 20     strm->msg =. 
1b80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1b90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 28                 (
1ba0: 63 68 61 72 20 2a 29 22 69 6e 76 61 6c 69 64 20  char *)"invalid 
1bb0: 64 69 73 74 61 6e 63 65 20 74 6f 6f 20 66 61 72  distance too far
1bc0: 20 62 61 63 6b 22 3b 0a 20 20 20 20 20 20 20 20   back";.        
1bd0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1be0: 20 20 20 20 73 74 61 74 65 2d 3e 6d 6f 64 65 20      state->mode 
1bf0: 3d 20 42 41 44 3b 0a 20 20 20 20 20 20 20 20 20  = BAD;.         
1c00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1c10: 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20     break;.      
1c20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1c30: 20 20 7d 0a 23 69 66 64 65 66 20 49 4e 46 4c 41    }.#ifdef INFLA
1c40: 54 45 5f 41 4c 4c 4f 57 5f 49 4e 56 41 4c 49 44  TE_ALLOW_INVALID
1c50: 5f 44 49 53 54 41 4e 43 45 5f 54 4f 4f 46 41 52  _DISTANCE_TOOFAR
1c60: 5f 41 52 52 52 0a 20 20 20 20 20 20 20 20 20 20  _ARRR.          
1c70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 66                if
1c80: 20 28 6c 65 6e 20 3c 3d 20 6f 70 20 2d 20 77 68   (len <= op - wh
1c90: 61 76 65 29 20 7b 0a 20 20 20 20 20 20 20 20 20  ave) {.         
1ca0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1cb0: 20 20 20 64 6f 20 7b 0a 20 20 20 20 20 20 20 20     do {.        
1cc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1cd0: 20 20 20 20 20 20 20 20 2a 6f 75 74 2b 2b 20 3d          *out++ =
1ce0: 20 30 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20   0;.            
1cf0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1d00: 7d 20 77 68 69 6c 65 20 28 2d 2d 6c 65 6e 29 3b  } while (--len);
1d10: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1d20: 20 20 20 20 20 20 20 20 20 20 20 20 20 63 6f 6e               con
1d30: 74 69 6e 75 65 3b 0a 20 20 20 20 20 20 20 20 20  tinue;.         
1d40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 7d                 }
1d50: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1d60: 20 20 20 20 20 20 20 20 20 6c 65 6e 20 2d 3d 20           len -= 
1d70: 6f 70 20 2d 20 77 68 61 76 65 3b 0a 20 20 20 20  op - whave;.    
1d80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1d90: 20 20 20 20 64 6f 20 7b 0a 20 20 20 20 20 20 20      do {.       
1da0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1db0: 20 20 20 20 20 2a 6f 75 74 2b 2b 20 3d 20 30 3b       *out++ = 0;
1dc0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1dd0: 20 20 20 20 20 20 20 20 20 7d 20 77 68 69 6c 65           } while
1de0: 20 28 2d 2d 6f 70 20 3e 20 77 68 61 76 65 29 3b   (--op > whave);
1df0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1e00: 20 20 20 20 20 20 20 20 20 69 66 20 28 6f 70 20           if (op 
1e10: 3d 3d 20 30 29 20 7b 0a 20 20 20 20 20 20 20 20  == 0) {.        
1e20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1e30: 20 20 20 20 66 72 6f 6d 20 3d 20 6f 75 74 20 2d      from = out -
1e40: 20 64 69 73 74 3b 0a 20 20 20 20 20 20 20 20 20   dist;.         
1e50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1e60: 20 20 20 64 6f 20 7b 0a 20 20 20 20 20 20 20 20     do {.        
1e70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1e80: 20 20 20 20 20 20 20 20 2a 6f 75 74 2b 2b 20 3d          *out++ =
1e90: 20 2a 66 72 6f 6d 2b 2b 3b 0a 20 20 20 20 20 20   *from++;.      
1ea0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1eb0: 20 20 20 20 20 20 7d 20 77 68 69 6c 65 20 28 2d        } while (-
1ec0: 2d 6c 65 6e 29 3b 0a 20 20 20 20 20 20 20 20 20  -len);.         
1ed0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1ee0: 20 20 20 63 6f 6e 74 69 6e 75 65 3b 0a 20 20 20     continue;.   
1ef0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1f00: 20 20 20 20 20 7d 0a 23 65 6e 64 69 66 0a 20 20       }.#endif.  
1f10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1f20: 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20 20 20    }.            
1f30: 20 20 20 20 20 20 20 20 66 72 6f 6d 20 3d 20 77          from = w
1f40: 69 6e 64 6f 77 3b 0a 20 20 20 20 20 20 20 20 20  indow;.         
1f50: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 28 77             if (w
1f60: 6e 65 78 74 20 3d 3d 20 30 29 20 7b 20 20 20 20  next == 0) {    
1f70: 20 20 20 20 20 20 20 2f 2a 20 76 65 72 79 20 63         /* very c
1f80: 6f 6d 6d 6f 6e 20 63 61 73 65 20 2a 2f 0a 20 20  ommon case */.  
1f90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1fa0: 20 20 20 20 20 20 66 72 6f 6d 20 2b 3d 20 77 73        from += ws
1fb0: 69 7a 65 20 2d 20 6f 70 3b 0a 20 20 20 20 20 20  ize - op;.      
1fc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1fd0: 20 20 69 66 20 28 6f 70 20 3c 20 6c 65 6e 29 20    if (op < len) 
1fe0: 7b 20 20 20 20 20 20 20 20 20 2f 2a 20 73 6f 6d  {         /* som
1ff0: 65 20 66 72 6f 6d 20 77 69 6e 64 6f 77 20 2a 2f  e from window */
2000: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
2010: 20 20 20 20 20 20 20 20 20 20 20 20 20 6c 65 6e               len
2020: 20 2d 3d 20 6f 70 3b 0a 20 20 20 20 20 20 20 20   -= op;.        
2030: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2040: 20 20 20 20 64 6f 20 7b 0a 20 20 20 20 20 20 20      do {.       
2050: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2060: 20 20 20 20 20 20 20 20 20 2a 6f 75 74 2b 2b 20           *out++ 
2070: 3d 20 2a 66 72 6f 6d 2b 2b 3b 0a 20 20 20 20 20  = *from++;.     
2080: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2090: 20 20 20 20 20 20 20 7d 20 77 68 69 6c 65 20 28         } while (
20a0: 2d 2d 6f 70 29 3b 0a 20 20 20 20 20 20 20 20 20  --op);.         
20b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
20c0: 20 20 20 66 72 6f 6d 20 3d 20 6f 75 74 20 2d 20     from = out - 
20d0: 64 69 73 74 3b 20 20 2f 2a 20 72 65 73 74 20 66  dist;  /* rest f
20e0: 72 6f 6d 20 6f 75 74 70 75 74 20 2a 2f 0a 20 20  rom output */.  
20f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2100: 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20        }.        
2110: 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a 20 20              }.  
2120: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2130: 20 20 65 6c 73 65 20 69 66 20 28 77 6e 65 78 74    else if (wnext
2140: 20 3c 20 6f 70 29 20 7b 20 20 20 20 20 20 2f 2a   < op) {      /*
2150: 20 77 72 61 70 20 61 72 6f 75 6e 64 20 77 69 6e   wrap around win
2160: 64 6f 77 20 2a 2f 0a 20 20 20 20 20 20 20 20 20  dow */.         
2170: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 66                 f
2180: 72 6f 6d 20 2b 3d 20 77 73 69 7a 65 20 2b 20 77  rom += wsize + w
2190: 6e 65 78 74 20 2d 20 6f 70 3b 0a 20 20 20 20 20  next - op;.     
21a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
21b0: 20 20 20 6f 70 20 2d 3d 20 77 6e 65 78 74 3b 0a     op -= wnext;.
21c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
21d0: 20 20 20 20 20 20 20 20 69 66 20 28 6f 70 20 3c          if (op <
21e0: 20 6c 65 6e 29 20 7b 20 20 20 20 20 20 20 20 20   len) {         
21f0: 2f 2a 20 73 6f 6d 65 20 66 72 6f 6d 20 65 6e 64  /* some from end
2200: 20 6f 66 20 77 69 6e 64 6f 77 20 2a 2f 0a 20 20   of window */.  
2210: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2220: 20 20 20 20 20 20 20 20 20 20 6c 65 6e 20 2d 3d            len -=
2230: 20 6f 70 3b 0a 20 20 20 20 20 20 20 20 20 20 20   op;.           
2240: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2250: 20 64 6f 20 7b 0a 20 20 20 20 20 20 20 20 20 20   do {.          
2260: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2270: 20 20 20 20 20 20 2a 6f 75 74 2b 2b 20 3d 20 2a        *out++ = *
2280: 66 72 6f 6d 2b 2b 3b 0a 20 20 20 20 20 20 20 20  from++;.        
2290: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
22a0: 20 20 20 20 7d 20 77 68 69 6c 65 20 28 2d 2d 6f      } while (--o
22b0: 70 29 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20  p);.            
22c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
22d0: 66 72 6f 6d 20 3d 20 77 69 6e 64 6f 77 3b 0a 20  from = window;. 
22e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
22f0: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 28 77             if (w
2300: 6e 65 78 74 20 3c 20 6c 65 6e 29 20 7b 20 20 2f  next < len) {  /
2310: 2a 20 73 6f 6d 65 20 66 72 6f 6d 20 73 74 61 72  * some from star
2320: 74 20 6f 66 20 77 69 6e 64 6f 77 20 2a 2f 0a 20  t of window */. 
2330: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2340: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6f                 o
2350: 70 20 3d 20 77 6e 65 78 74 3b 0a 20 20 20 20 20  p = wnext;.     
2360: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2370: 20 20 20 20 20 20 20 20 20 20 20 6c 65 6e 20 2d             len -
2380: 3d 20 6f 70 3b 0a 20 20 20 20 20 20 20 20 20 20  = op;.          
2390: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
23a0: 20 20 20 20 20 20 64 6f 20 7b 0a 20 20 20 20 20        do {.     
23b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
23c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2a                 *
23d0: 6f 75 74 2b 2b 20 3d 20 2a 66 72 6f 6d 2b 2b 3b  out++ = *from++;
23e0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
23f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2400: 20 7d 20 77 68 69 6c 65 20 28 2d 2d 6f 70 29 3b   } while (--op);
2410: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
2420: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2430: 20 66 72 6f 6d 20 3d 20 6f 75 74 20 2d 20 64 69   from = out - di
2440: 73 74 3b 20 20 20 20 20 20 2f 2a 20 72 65 73 74  st;      /* rest
2450: 20 66 72 6f 6d 20 6f 75 74 70 75 74 20 2a 2f 0a   from output */.
2460: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2470: 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a 20 20              }.  
2480: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2490: 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20        }.        
24a0: 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a 20 20              }.  
24b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
24c0: 20 20 65 6c 73 65 20 7b 20 20 20 20 20 20 20 20    else {        
24d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
24e0: 20 63 6f 6e 74 69 67 75 6f 75 73 20 69 6e 20 77   contiguous in w
24f0: 69 6e 64 6f 77 20 2a 2f 0a 20 20 20 20 20 20 20  indow */.       
2500: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2510: 20 66 72 6f 6d 20 2b 3d 20 77 6e 65 78 74 20 2d   from += wnext -
2520: 20 6f 70 3b 0a 20 20 20 20 20 20 20 20 20 20 20   op;.           
2530: 20 20 20 20 20 20 20 20 20 20 20 20 20 69 66 20               if 
2540: 28 6f 70 20 3c 20 6c 65 6e 29 20 7b 20 20 20 20  (op < len) {    
2550: 20 20 20 20 20 2f 2a 20 73 6f 6d 65 20 66 72 6f       /* some fro
2560: 6d 20 77 69 6e 64 6f 77 20 2a 2f 0a 20 20 20 20  m window */.    
2570: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2580: 20 20 20 20 20 20 20 20 6c 65 6e 20 2d 3d 20 6f          len -= o
2590: 70 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  p;.             
25a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 64                 d
25b0: 6f 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20  o {.            
25c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
25d0: 20 20 20 20 2a 6f 75 74 2b 2b 20 3d 20 2a 66 72      *out++ = *fr
25e0: 6f 6d 2b 2b 3b 0a 20 20 20 20 20 20 20 20 20 20  om++;.          
25f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2600: 20 20 7d 20 77 68 69 6c 65 20 28 2d 2d 6f 70 29    } while (--op)
2610: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;.              
2620: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 66 72                fr
2630: 6f 6d 20 3d 20 6f 75 74 20 2d 20 64 69 73 74 3b  om = out - dist;
2640: 20 20 2f 2a 20 72 65 73 74 20 66 72 6f 6d 20 6f    /* rest from o
2650: 75 74 70 75 74 20 2a 2f 0a 20 20 20 20 20 20 20  utput */.       
2660: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2670: 20 7d 0a 20 20 20 20 20 20 20 20 20 20 20 20 20   }.             
2680: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20         }.       
2690: 20 20 20 20 20 20 20 20 20 20 20 20 20 77 68 69               whi
26a0: 6c 65 20 28 6c 65 6e 20 3e 20 32 29 20 7b 0a 20  le (len > 2) {. 
26b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
26c0: 20 20 20 20 20 20 20 2a 6f 75 74 2b 2b 20 3d 20         *out++ = 
26d0: 2a 66 72 6f 6d 2b 2b 3b 0a 20 20 20 20 20 20 20  *from++;.       
26e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
26f0: 20 2a 6f 75 74 2b 2b 20 3d 20 2a 66 72 6f 6d 2b   *out++ = *from+
2700: 2b 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  +;.             
2710: 20 20 20 20 20 20 20 20 20 20 20 2a 6f 75 74 2b             *out+
2720: 2b 20 3d 20 2a 66 72 6f 6d 2b 2b 3b 0a 20 20 20  + = *from++;.   
2730: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2740: 20 20 20 20 20 6c 65 6e 20 2d 3d 20 33 3b 0a 20       len -= 3;. 
2750: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2760: 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20 20     }.           
2770: 20 20 20 20 20 20 20 20 20 69 66 20 28 6c 65 6e           if (len
2780: 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20  ) {.            
2790: 20 20 20 20 20 20 20 20 20 20 20 20 2a 6f 75 74              *out
27a0: 2b 2b 20 3d 20 2a 66 72 6f 6d 2b 2b 3b 0a 20 20  ++ = *from++;.  
27b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
27c0: 20 20 20 20 20 20 69 66 20 28 6c 65 6e 20 3e 20        if (len > 
27d0: 31 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  1).             
27e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2a                 *
27f0: 6f 75 74 2b 2b 20 3d 20 2a 66 72 6f 6d 2b 2b 3b  out++ = *from++;
2800: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
2810: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20       }.         
2820: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20         }.       
2830: 20 20 20 20 20 20 20 20 20 65 6c 73 65 20 7b 0a           else {.
2840: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2850: 20 20 20 20 66 72 6f 6d 20 3d 20 6f 75 74 20 2d      from = out -
2860: 20 64 69 73 74 3b 20 20 20 20 20 20 20 20 20 20   dist;          
2870: 2f 2a 20 63 6f 70 79 20 64 69 72 65 63 74 20 66  /* copy direct f
2880: 72 6f 6d 20 6f 75 74 70 75 74 20 2a 2f 0a 20 20  rom output */.  
2890: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
28a0: 20 20 64 6f 20 7b 20 20 20 20 20 20 20 20 20 20    do {          
28b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
28c0: 20 6d 69 6e 69 6d 75 6d 20 6c 65 6e 67 74 68 20   minimum length 
28d0: 69 73 20 74 68 72 65 65 20 2a 2f 0a 20 20 20 20  is three */.    
28e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
28f0: 20 20 20 20 2a 6f 75 74 2b 2b 20 3d 20 2a 66 72      *out++ = *fr
2900: 6f 6d 2b 2b 3b 0a 20 20 20 20 20 20 20 20 20 20  om++;.          
2910: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2a 6f                *o
2920: 75 74 2b 2b 20 3d 20 2a 66 72 6f 6d 2b 2b 3b 0a  ut++ = *from++;.
2930: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2940: 20 20 20 20 20 20 20 20 2a 6f 75 74 2b 2b 20 3d          *out++ =
2950: 20 2a 66 72 6f 6d 2b 2b 3b 0a 20 20 20 20 20 20   *from++;.      
2960: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2970: 20 20 6c 65 6e 20 2d 3d 20 33 3b 0a 20 20 20 20    len -= 3;.    
2980: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2990: 7d 20 77 68 69 6c 65 20 28 6c 65 6e 20 3e 20 32  } while (len > 2
29a0: 29 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  );.             
29b0: 20 20 20 20 20 20 20 69 66 20 28 6c 65 6e 29 20         if (len) 
29c0: 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  {.              
29d0: 20 20 20 20 20 20 20 20 20 20 2a 6f 75 74 2b 2b            *out++
29e0: 20 3d 20 2a 66 72 6f 6d 2b 2b 3b 0a 20 20 20 20   = *from++;.    
29f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2a00: 20 20 20 20 69 66 20 28 6c 65 6e 20 3e 20 31 29      if (len > 1)
2a10: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
2a20: 20 20 20 20 20 20 20 20 20 20 20 20 20 2a 6f 75               *ou
2a30: 74 2b 2b 20 3d 20 2a 66 72 6f 6d 2b 2b 3b 0a 20  t++ = *from++;. 
2a40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2a50: 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20 20     }.           
2a60: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20       }.         
2a70: 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20 20     }.           
2a80: 20 65 6c 73 65 20 69 66 20 28 28 6f 70 20 26 20   else if ((op & 
2a90: 36 34 29 20 3d 3d 20 30 29 20 7b 20 20 20 20 20  64) == 0) {     
2aa0: 20 20 20 20 20 2f 2a 20 32 6e 64 20 6c 65 76 65       /* 2nd leve
2ab0: 6c 20 64 69 73 74 61 6e 63 65 20 63 6f 64 65 20  l distance code 
2ac0: 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  */.             
2ad0: 20 20 20 68 65 72 65 20 3d 20 64 63 6f 64 65 5b     here = dcode[
2ae0: 68 65 72 65 2e 76 61 6c 20 2b 20 28 68 6f 6c 64  here.val + (hold
2af0: 20 26 20 28 28 31 55 20 3c 3c 20 6f 70 29 20 2d   & ((1U << op) -
2b00: 20 31 29 29 5d 3b 0a 20 20 20 20 20 20 20 20 20   1))];.         
2b10: 20 20 20 20 20 20 20 67 6f 74 6f 20 64 6f 64 69         goto dodi
2b20: 73 74 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20  st;.            
2b30: 7d 0a 20 20 20 20 20 20 20 20 20 20 20 20 65 6c  }.            el
2b40: 73 65 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20  se {.           
2b50: 20 20 20 20 20 73 74 72 6d 2d 3e 6d 73 67 20 3d       strm->msg =
2b60: 20 28 63 68 61 72 20 2a 29 22 69 6e 76 61 6c 69   (char *)"invali
2b70: 64 20 64 69 73 74 61 6e 63 65 20 63 6f 64 65 22  d distance code"
2b80: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;.              
2b90: 20 20 73 74 61 74 65 2d 3e 6d 6f 64 65 20 3d 20    state->mode = 
2ba0: 42 41 44 3b 0a 20 20 20 20 20 20 20 20 20 20 20  BAD;.           
2bb0: 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20       break;.    
2bc0: 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20          }.      
2bd0: 20 20 7d 0a 20 20 20 20 20 20 20 20 65 6c 73 65    }.        else
2be0: 20 69 66 20 28 28 6f 70 20 26 20 36 34 29 20 3d   if ((op & 64) =
2bf0: 3d 20 30 29 20 7b 20 20 20 20 20 20 20 20 20 20  = 0) {          
2c00: 20 20 20 20 2f 2a 20 32 6e 64 20 6c 65 76 65 6c      /* 2nd level
2c10: 20 6c 65 6e 67 74 68 20 63 6f 64 65 20 2a 2f 0a   length code */.
2c20: 20 20 20 20 20 20 20 20 20 20 20 20 68 65 72 65              here
2c30: 20 3d 20 6c 63 6f 64 65 5b 68 65 72 65 2e 76 61   = lcode[here.va
2c40: 6c 20 2b 20 28 68 6f 6c 64 20 26 20 28 28 31 55  l + (hold & ((1U
2c50: 20 3c 3c 20 6f 70 29 20 2d 20 31 29 29 5d 3b 0a   << op) - 1))];.
2c60: 20 20 20 20 20 20 20 20 20 20 20 20 67 6f 74 6f              goto
2c70: 20 64 6f 6c 65 6e 3b 0a 20 20 20 20 20 20 20 20   dolen;.        
2c80: 7d 0a 20 20 20 20 20 20 20 20 65 6c 73 65 20 69  }.        else i
2c90: 66 20 28 6f 70 20 26 20 33 32 29 20 7b 20 20 20  f (op & 32) {   
2ca0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2cb0: 20 20 2f 2a 20 65 6e 64 2d 6f 66 2d 62 6c 6f 63    /* end-of-bloc
2cc0: 6b 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 20  k */.           
2cd0: 20 54 72 61 63 65 76 76 28 28 73 74 64 65 72 72   Tracevv((stderr
2ce0: 2c 20 22 69 6e 66 6c 61 74 65 3a 20 20 20 20 20  , "inflate:     
2cf0: 20 20 20 20 65 6e 64 20 6f 66 20 62 6c 6f 63 6b      end of block
2d00: 5c 6e 22 29 29 3b 0a 20 20 20 20 20 20 20 20 20  \n"));.         
2d10: 20 20 20 73 74 61 74 65 2d 3e 6d 6f 64 65 20 3d     state->mode =
2d20: 20 54 59 50 45 3b 0a 20 20 20 20 20 20 20 20 20   TYPE;.         
2d30: 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20     break;.      
2d40: 20 20 7d 0a 20 20 20 20 20 20 20 20 65 6c 73 65    }.        else
2d50: 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 73   {.            s
2d60: 74 72 6d 2d 3e 6d 73 67 20 3d 20 28 63 68 61 72  trm->msg = (char
2d70: 20 2a 29 22 69 6e 76 61 6c 69 64 20 6c 69 74 65   *)"invalid lite
2d80: 72 61 6c 2f 6c 65 6e 67 74 68 20 63 6f 64 65 22  ral/length code"
2d90: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 73 74  ;.            st
2da0: 61 74 65 2d 3e 6d 6f 64 65 20 3d 20 42 41 44 3b  ate->mode = BAD;
2db0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 62 72 65  .            bre
2dc0: 61 6b 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20  ak;.        }.  
2dd0: 20 20 7d 20 77 68 69 6c 65 20 28 69 6e 20 3c 20    } while (in < 
2de0: 6c 61 73 74 20 26 26 20 6f 75 74 20 3c 20 65 6e  last && out < en
2df0: 64 29 3b 0a 0a 20 20 20 20 2f 2a 20 72 65 74 75  d);..    /* retu
2e00: 72 6e 20 75 6e 75 73 65 64 20 62 79 74 65 73 20  rn unused bytes 
2e10: 28 6f 6e 20 65 6e 74 72 79 2c 20 62 69 74 73 20  (on entry, bits 
2e20: 3c 20 38 2c 20 73 6f 20 69 6e 20 77 6f 6e 27 74  < 8, so in won't
2e30: 20 67 6f 20 74 6f 6f 20 66 61 72 20 62 61 63 6b   go too far back
2e40: 29 20 2a 2f 0a 20 20 20 20 6c 65 6e 20 3d 20 62  ) */.    len = b
2e50: 69 74 73 20 3e 3e 20 33 3b 0a 20 20 20 20 69 6e  its >> 3;.    in
2e60: 20 2d 3d 20 6c 65 6e 3b 0a 20 20 20 20 62 69 74   -= len;.    bit
2e70: 73 20 2d 3d 20 6c 65 6e 20 3c 3c 20 33 3b 0a 20  s -= len << 3;. 
2e80: 20 20 20 68 6f 6c 64 20 26 3d 20 28 31 55 20 3c     hold &= (1U <
2e90: 3c 20 62 69 74 73 29 20 2d 20 31 3b 0a 0a 20 20  < bits) - 1;..  
2ea0: 20 20 2f 2a 20 75 70 64 61 74 65 20 73 74 61 74    /* update stat
2eb0: 65 20 61 6e 64 20 72 65 74 75 72 6e 20 2a 2f 0a  e and return */.
2ec0: 20 20 20 20 73 74 72 6d 2d 3e 6e 65 78 74 5f 69      strm->next_i
2ed0: 6e 20 3d 20 69 6e 3b 0a 20 20 20 20 73 74 72 6d  n = in;.    strm
2ee0: 2d 3e 6e 65 78 74 5f 6f 75 74 20 3d 20 6f 75 74  ->next_out = out
2ef0: 3b 0a 20 20 20 20 73 74 72 6d 2d 3e 61 76 61 69  ;.    strm->avai
2f00: 6c 5f 69 6e 20 3d 20 28 75 6e 73 69 67 6e 65 64  l_in = (unsigned
2f10: 29 28 69 6e 20 3c 20 6c 61 73 74 20 3f 20 35 20  )(in < last ? 5 
2f20: 2b 20 28 6c 61 73 74 20 2d 20 69 6e 29 20 3a 20  + (last - in) : 
2f30: 35 20 2d 20 28 69 6e 20 2d 20 6c 61 73 74 29 29  5 - (in - last))
2f40: 3b 0a 20 20 20 20 73 74 72 6d 2d 3e 61 76 61 69  ;.    strm->avai
2f50: 6c 5f 6f 75 74 20 3d 20 28 75 6e 73 69 67 6e 65  l_out = (unsigne
2f60: 64 29 28 6f 75 74 20 3c 20 65 6e 64 20 3f 0a 20  d)(out < end ?. 
2f70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2f80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2f90: 32 35 37 20 2b 20 28 65 6e 64 20 2d 20 6f 75 74  257 + (end - out
2fa0: 29 20 3a 20 32 35 37 20 2d 20 28 6f 75 74 20 2d  ) : 257 - (out -
2fb0: 20 65 6e 64 29 29 3b 0a 20 20 20 20 73 74 61 74   end));.    stat
2fc0: 65 2d 3e 68 6f 6c 64 20 3d 20 68 6f 6c 64 3b 0a  e->hold = hold;.
2fd0: 20 20 20 20 73 74 61 74 65 2d 3e 62 69 74 73 20      state->bits 
2fe0: 3d 20 62 69 74 73 3b 0a 20 20 20 20 72 65 74 75  = bits;.    retu
2ff0: 72 6e 3b 0a 7d 0a 0a 2f 2a 0a 20 20 20 69 6e 66  rn;.}../*.   inf
3000: 6c 61 74 65 5f 66 61 73 74 28 29 20 73 70 65 65  late_fast() spee
3010: 64 75 70 73 20 74 68 61 74 20 74 75 72 6e 65 64  dups that turned
3020: 20 6f 75 74 20 73 6c 6f 77 65 72 20 28 6f 6e 20   out slower (on 
3030: 61 20 50 6f 77 65 72 50 43 20 47 33 20 37 35 30  a PowerPC G3 750
3040: 43 58 65 29 3a 0a 20 20 20 2d 20 55 73 69 6e 67  CXe):.   - Using
3050: 20 62 69 74 20 66 69 65 6c 64 73 20 66 6f 72 20   bit fields for 
3060: 63 6f 64 65 20 73 74 72 75 63 74 75 72 65 0a 20  code structure. 
3070: 20 20 2d 20 44 69 66 66 65 72 65 6e 74 20 6f 70    - Different op
3080: 20 64 65 66 69 6e 69 74 69 6f 6e 20 74 6f 20 61   definition to a
3090: 76 6f 69 64 20 26 20 66 6f 72 20 65 78 74 72 61  void & for extra
30a0: 20 62 69 74 73 20 28 64 6f 20 26 20 66 6f 72 20   bits (do & for 
30b0: 74 61 62 6c 65 20 62 69 74 73 29 0a 20 20 20 2d  table bits).   -
30c0: 20 54 68 72 65 65 20 73 65 70 61 72 61 74 65 20   Three separate 
30d0: 64 65 63 6f 64 69 6e 67 20 64 6f 2d 6c 6f 6f 70  decoding do-loop
30e0: 73 20 66 6f 72 20 64 69 72 65 63 74 2c 20 77 69  s for direct, wi
30f0: 6e 64 6f 77 2c 20 61 6e 64 20 77 6e 65 78 74 20  ndow, and wnext 
3100: 3d 3d 20 30 0a 20 20 20 2d 20 53 70 65 63 69 61  == 0.   - Specia
3110: 6c 20 63 61 73 65 20 66 6f 72 20 64 69 73 74 61  l case for dista
3120: 6e 63 65 20 3e 20 31 20 63 6f 70 69 65 73 20 74  nce > 1 copies t
3130: 6f 20 64 6f 20 6f 76 65 72 6c 61 70 70 65 64 20  o do overlapped 
3140: 6c 6f 61 64 20 61 6e 64 20 73 74 6f 72 65 20 63  load and store c
3150: 6f 70 79 0a 20 20 20 2d 20 45 78 70 6c 69 63 69  opy.   - Explici
3160: 74 20 62 72 61 6e 63 68 20 70 72 65 64 69 63 74  t branch predict
3170: 69 6f 6e 73 20 28 62 61 73 65 64 20 6f 6e 20 6d  ions (based on m
3180: 65 61 73 75 72 65 64 20 62 72 61 6e 63 68 20 70  easured branch p
3190: 72 6f 62 61 62 69 6c 69 74 69 65 73 29 0a 20 20  robabilities).  
31a0: 20 2d 20 44 65 66 65 72 72 69 6e 67 20 6d 61 74   - Deferring mat
31b0: 63 68 20 63 6f 70 79 20 61 6e 64 20 69 6e 74 65  ch copy and inte
31c0: 72 73 70 65 72 73 65 64 20 69 74 20 77 69 74 68  rspersed it with
31d0: 20 64 65 63 6f 64 69 6e 67 20 73 75 62 73 65 71   decoding subseq
31e0: 75 65 6e 74 20 63 6f 64 65 73 0a 20 20 20 2d 20  uent codes.   - 
31f0: 53 77 61 70 70 69 6e 67 20 6c 69 74 65 72 61 6c  Swapping literal
3200: 2f 6c 65 6e 67 74 68 20 65 6c 73 65 0a 20 20 20  /length else.   
3210: 2d 20 53 77 61 70 70 69 6e 67 20 77 69 6e 64 6f  - Swapping windo
3220: 77 2f 64 69 72 65 63 74 20 65 6c 73 65 0a 20 20  w/direct else.  
3230: 20 2d 20 4c 61 72 67 65 72 20 75 6e 72 6f 6c 6c   - Larger unroll
3240: 65 64 20 63 6f 70 79 20 6c 6f 6f 70 73 20 28 74  ed copy loops (t
3250: 68 72 65 65 20 69 73 20 61 62 6f 75 74 20 72 69  hree is about ri
3260: 67 68 74 29 0a 20 20 20 2d 20 4d 6f 76 69 6e 67  ght).   - Moving
3270: 20 6c 65 6e 20 2d 3d 20 33 20 73 74 61 74 65 6d   len -= 3 statem
3280: 65 6e 74 20 69 6e 74 6f 20 6d 69 64 64 6c 65 20  ent into middle 
3290: 6f 66 20 6c 6f 6f 70 0a 20 2a 2f 0a 0a 23 65 6e  of loop. */..#en
32a0: 64 69 66 20 2f 2a 20 21 41 53 4d 49 4e 46 20 2a  dif /* !ASMINF *
32b0: 2f 0a                                            /.