Fossil

Hex Artifact Content
Login

Artifact f1ae4935697dd305bde334835d7d3139e06197b9:


0000: 2f 2a 20 69 6e 66 74 72 65 65 73 2e 63 20 2d 2d  /* inftrees.c --
0010: 20 67 65 6e 65 72 61 74 65 20 48 75 66 66 6d 61   generate Huffma
0020: 6e 20 74 72 65 65 73 20 66 6f 72 20 65 66 66 69  n trees for effi
0030: 63 69 65 6e 74 20 64 65 63 6f 64 69 6e 67 0a 20  cient decoding. 
0040: 2a 20 43 6f 70 79 72 69 67 68 74 20 28 43 29 20  * Copyright (C) 
0050: 31 39 39 35 2d 32 30 31 33 20 4d 61 72 6b 20 41  1995-2013 Mark A
0060: 64 6c 65 72 0a 20 2a 20 46 6f 72 20 63 6f 6e 64  dler. * For cond
0070: 69 74 69 6f 6e 73 20 6f 66 20 64 69 73 74 72 69  itions of distri
0080: 62 75 74 69 6f 6e 20 61 6e 64 20 75 73 65 2c 20  bution and use, 
0090: 73 65 65 20 63 6f 70 79 72 69 67 68 74 20 6e 6f  see copyright no
00a0: 74 69 63 65 20 69 6e 20 7a 6c 69 62 2e 68 0a 20  tice in zlib.h. 
00b0: 2a 2f 0a 0a 23 69 6e 63 6c 75 64 65 20 22 7a 75  */..#include "zu
00c0: 74 69 6c 2e 68 22 0a 23 69 6e 63 6c 75 64 65 20  til.h".#include 
00d0: 22 69 6e 66 74 72 65 65 73 2e 68 22 0a 0a 23 64  "inftrees.h"..#d
00e0: 65 66 69 6e 65 20 4d 41 58 42 49 54 53 20 31 35  efine MAXBITS 15
00f0: 0a 0a 63 6f 6e 73 74 20 63 68 61 72 20 69 6e 66  ..const char inf
0100: 6c 61 74 65 5f 63 6f 70 79 72 69 67 68 74 5b 5d  late_copyright[]
0110: 20 3d 0a 20 20 20 22 20 69 6e 66 6c 61 74 65 20   =.   " inflate 
0120: 31 2e 32 2e 38 20 43 6f 70 79 72 69 67 68 74 20  1.2.8 Copyright 
0130: 31 39 39 35 2d 32 30 31 33 20 4d 61 72 6b 20 41  1995-2013 Mark A
0140: 64 6c 65 72 20 22 3b 0a 2f 2a 0a 20 20 49 66 20  dler ";./*.  If 
0150: 79 6f 75 20 75 73 65 20 74 68 65 20 7a 6c 69 62  you use the zlib
0160: 20 6c 69 62 72 61 72 79 20 69 6e 20 61 20 70 72   library in a pr
0170: 6f 64 75 63 74 2c 20 61 6e 20 61 63 6b 6e 6f 77  oduct, an acknow
0180: 6c 65 64 67 6d 65 6e 74 20 69 73 20 77 65 6c 63  ledgment is welc
0190: 6f 6d 65 0a 20 20 69 6e 20 74 68 65 20 64 6f 63  ome.  in the doc
01a0: 75 6d 65 6e 74 61 74 69 6f 6e 20 6f 66 20 79 6f  umentation of yo
01b0: 75 72 20 70 72 6f 64 75 63 74 2e 20 49 66 20 66  ur product. If f
01c0: 6f 72 20 73 6f 6d 65 20 72 65 61 73 6f 6e 20 79  or some reason y
01d0: 6f 75 20 63 61 6e 6e 6f 74 0a 20 20 69 6e 63 6c  ou cannot.  incl
01e0: 75 64 65 20 73 75 63 68 20 61 6e 20 61 63 6b 6e  ude such an ackn
01f0: 6f 77 6c 65 64 67 6d 65 6e 74 2c 20 49 20 77 6f  owledgment, I wo
0200: 75 6c 64 20 61 70 70 72 65 63 69 61 74 65 20 74  uld appreciate t
0210: 68 61 74 20 79 6f 75 20 6b 65 65 70 20 74 68 69  hat you keep thi
0220: 73 0a 20 20 63 6f 70 79 72 69 67 68 74 20 73 74  s.  copyright st
0230: 72 69 6e 67 20 69 6e 20 74 68 65 20 65 78 65 63  ring in the exec
0240: 75 74 61 62 6c 65 20 6f 66 20 79 6f 75 72 20 70  utable of your p
0250: 72 6f 64 75 63 74 2e 0a 20 2a 2f 0a 0a 2f 2a 0a  roduct.. */../*.
0260: 20 20 20 42 75 69 6c 64 20 61 20 73 65 74 20 6f     Build a set o
0270: 66 20 74 61 62 6c 65 73 20 74 6f 20 64 65 63 6f  f tables to deco
0280: 64 65 20 74 68 65 20 70 72 6f 76 69 64 65 64 20  de the provided 
0290: 63 61 6e 6f 6e 69 63 61 6c 20 48 75 66 66 6d 61  canonical Huffma
02a0: 6e 20 63 6f 64 65 2e 0a 20 20 20 54 68 65 20 63  n code..   The c
02b0: 6f 64 65 20 6c 65 6e 67 74 68 73 20 61 72 65 20  ode lengths are 
02c0: 6c 65 6e 73 5b 30 2e 2e 63 6f 64 65 73 2d 31 5d  lens[0..codes-1]
02d0: 2e 20 20 54 68 65 20 72 65 73 75 6c 74 20 73 74  .  The result st
02e0: 61 72 74 73 20 61 74 20 2a 74 61 62 6c 65 2c 0a  arts at *table,.
02f0: 20 20 20 77 68 6f 73 65 20 69 6e 64 69 63 65 73     whose indices
0300: 20 61 72 65 20 30 2e 2e 32 5e 62 69 74 73 2d 31   are 0..2^bits-1
0310: 2e 20 20 77 6f 72 6b 20 69 73 20 61 20 77 72 69  .  work is a wri
0320: 74 61 62 6c 65 20 61 72 72 61 79 20 6f 66 20 61  table array of a
0330: 74 20 6c 65 61 73 74 0a 20 20 20 6c 65 6e 73 20  t least.   lens 
0340: 73 68 6f 72 74 73 2c 20 77 68 69 63 68 20 69 73  shorts, which is
0350: 20 75 73 65 64 20 61 73 20 61 20 77 6f 72 6b 20   used as a work 
0360: 61 72 65 61 2e 20 20 74 79 70 65 20 69 73 20 74  area.  type is t
0370: 68 65 20 74 79 70 65 20 6f 66 20 63 6f 64 65 0a  he type of code.
0380: 20 20 20 74 6f 20 62 65 20 67 65 6e 65 72 61 74     to be generat
0390: 65 64 2c 20 43 4f 44 45 53 2c 20 4c 45 4e 53 2c  ed, CODES, LENS,
03a0: 20 6f 72 20 44 49 53 54 53 2e 20 20 4f 6e 20 72   or DISTS.  On r
03b0: 65 74 75 72 6e 2c 20 7a 65 72 6f 20 69 73 20 73  eturn, zero is s
03c0: 75 63 63 65 73 73 2c 0a 20 20 20 2d 31 20 69 73  uccess,.   -1 is
03d0: 20 61 6e 20 69 6e 76 61 6c 69 64 20 63 6f 64 65   an invalid code
03e0: 2c 20 61 6e 64 20 2b 31 20 6d 65 61 6e 73 20 74  , and +1 means t
03f0: 68 61 74 20 45 4e 4f 55 47 48 20 69 73 6e 27 74  hat ENOUGH isn't
0400: 20 65 6e 6f 75 67 68 2e 20 20 74 61 62 6c 65 0a   enough.  table.
0410: 20 20 20 6f 6e 20 72 65 74 75 72 6e 20 70 6f 69     on return poi
0420: 6e 74 73 20 74 6f 20 74 68 65 20 6e 65 78 74 20  nts to the next 
0430: 61 76 61 69 6c 61 62 6c 65 20 65 6e 74 72 79 27  available entry'
0440: 73 20 61 64 64 72 65 73 73 2e 20 20 62 69 74 73  s address.  bits
0450: 20 69 73 20 74 68 65 0a 20 20 20 72 65 71 75 65   is the.   reque
0460: 73 74 65 64 20 72 6f 6f 74 20 74 61 62 6c 65 20  sted root table 
0470: 69 6e 64 65 78 20 62 69 74 73 2c 20 61 6e 64 20  index bits, and 
0480: 6f 6e 20 72 65 74 75 72 6e 20 69 74 20 69 73 20  on return it is 
0490: 74 68 65 20 61 63 74 75 61 6c 20 72 6f 6f 74 0a  the actual root.
04a0: 20 20 20 74 61 62 6c 65 20 69 6e 64 65 78 20 62     table index b
04b0: 69 74 73 2e 20 20 49 74 20 77 69 6c 6c 20 64 69  its.  It will di
04c0: 66 66 65 72 20 69 66 20 74 68 65 20 72 65 71 75  ffer if the requ
04d0: 65 73 74 20 69 73 20 67 72 65 61 74 65 72 20 74  est is greater t
04e0: 68 61 6e 20 74 68 65 0a 20 20 20 6c 6f 6e 67 65  han the.   longe
04f0: 73 74 20 63 6f 64 65 20 6f 72 20 69 66 20 69 74  st code or if it
0500: 20 69 73 20 6c 65 73 73 20 74 68 61 6e 20 74 68   is less than th
0510: 65 20 73 68 6f 72 74 65 73 74 20 63 6f 64 65 2e  e shortest code.
0520: 0a 20 2a 2f 0a 69 6e 74 20 5a 4c 49 42 5f 49 4e  . */.int ZLIB_IN
0530: 54 45 52 4e 41 4c 20 69 6e 66 6c 61 74 65 5f 74  TERNAL inflate_t
0540: 61 62 6c 65 28 74 79 70 65 2c 20 6c 65 6e 73 2c  able(type, lens,
0550: 20 63 6f 64 65 73 2c 20 74 61 62 6c 65 2c 20 62   codes, table, b
0560: 69 74 73 2c 20 77 6f 72 6b 29 0a 63 6f 64 65 74  its, work).codet
0570: 79 70 65 20 74 79 70 65 3b 0a 75 6e 73 69 67 6e  ype type;.unsign
0580: 65 64 20 73 68 6f 72 74 20 46 41 52 20 2a 6c 65  ed short FAR *le
0590: 6e 73 3b 0a 75 6e 73 69 67 6e 65 64 20 63 6f 64  ns;.unsigned cod
05a0: 65 73 3b 0a 63 6f 64 65 20 46 41 52 20 2a 20 46  es;.code FAR * F
05b0: 41 52 20 2a 74 61 62 6c 65 3b 0a 75 6e 73 69 67  AR *table;.unsig
05c0: 6e 65 64 20 46 41 52 20 2a 62 69 74 73 3b 0a 75  ned FAR *bits;.u
05d0: 6e 73 69 67 6e 65 64 20 73 68 6f 72 74 20 46 41  nsigned short FA
05e0: 52 20 2a 77 6f 72 6b 3b 0a 7b 0a 20 20 20 20 75  R *work;.{.    u
05f0: 6e 73 69 67 6e 65 64 20 6c 65 6e 3b 20 20 20 20  nsigned len;    
0600: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 61 20             /* a 
0610: 63 6f 64 65 27 73 20 6c 65 6e 67 74 68 20 69 6e  code's length in
0620: 20 62 69 74 73 20 2a 2f 0a 20 20 20 20 75 6e 73   bits */.    uns
0630: 69 67 6e 65 64 20 73 79 6d 3b 20 20 20 20 20 20  igned sym;      
0640: 20 20 20 20 20 20 20 20 20 2f 2a 20 69 6e 64 65           /* inde
0650: 78 20 6f 66 20 63 6f 64 65 20 73 79 6d 62 6f 6c  x of code symbol
0660: 73 20 2a 2f 0a 20 20 20 20 75 6e 73 69 67 6e 65  s */.    unsigne
0670: 64 20 6d 69 6e 2c 20 6d 61 78 3b 20 20 20 20 20  d min, max;     
0680: 20 20 20 20 20 2f 2a 20 6d 69 6e 69 6d 75 6d 20       /* minimum 
0690: 61 6e 64 20 6d 61 78 69 6d 75 6d 20 63 6f 64 65  and maximum code
06a0: 20 6c 65 6e 67 74 68 73 20 2a 2f 0a 20 20 20 20   lengths */.    
06b0: 75 6e 73 69 67 6e 65 64 20 72 6f 6f 74 3b 20 20  unsigned root;  
06c0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 6e              /* n
06d0: 75 6d 62 65 72 20 6f 66 20 69 6e 64 65 78 20 62  umber of index b
06e0: 69 74 73 20 66 6f 72 20 72 6f 6f 74 20 74 61 62  its for root tab
06f0: 6c 65 20 2a 2f 0a 20 20 20 20 75 6e 73 69 67 6e  le */.    unsign
0700: 65 64 20 63 75 72 72 3b 20 20 20 20 20 20 20 20  ed curr;        
0710: 20 20 20 20 20 20 2f 2a 20 6e 75 6d 62 65 72 20        /* number 
0720: 6f 66 20 69 6e 64 65 78 20 62 69 74 73 20 66 6f  of index bits fo
0730: 72 20 63 75 72 72 65 6e 74 20 74 61 62 6c 65 20  r current table 
0740: 2a 2f 0a 20 20 20 20 75 6e 73 69 67 6e 65 64 20  */.    unsigned 
0750: 64 72 6f 70 3b 20 20 20 20 20 20 20 20 20 20 20  drop;           
0760: 20 20 20 2f 2a 20 63 6f 64 65 20 62 69 74 73 20     /* code bits 
0770: 74 6f 20 64 72 6f 70 20 66 6f 72 20 73 75 62 2d  to drop for sub-
0780: 74 61 62 6c 65 20 2a 2f 0a 20 20 20 20 69 6e 74  table */.    int
0790: 20 6c 65 66 74 3b 20 20 20 20 20 20 20 20 20 20   left;          
07a0: 20 20 20 20 20 20 20 20 20 2f 2a 20 6e 75 6d 62           /* numb
07b0: 65 72 20 6f 66 20 70 72 65 66 69 78 20 63 6f 64  er of prefix cod
07c0: 65 73 20 61 76 61 69 6c 61 62 6c 65 20 2a 2f 0a  es available */.
07d0: 20 20 20 20 75 6e 73 69 67 6e 65 64 20 75 73 65      unsigned use
07e0: 64 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  d;              
07f0: 2f 2a 20 63 6f 64 65 20 65 6e 74 72 69 65 73 20  /* code entries 
0800: 69 6e 20 74 61 62 6c 65 20 75 73 65 64 20 2a 2f  in table used */
0810: 0a 20 20 20 20 75 6e 73 69 67 6e 65 64 20 68 75  .    unsigned hu
0820: 66 66 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  ff;             
0830: 20 2f 2a 20 48 75 66 66 6d 61 6e 20 63 6f 64 65   /* Huffman code
0840: 20 2a 2f 0a 20 20 20 20 75 6e 73 69 67 6e 65 64   */.    unsigned
0850: 20 69 6e 63 72 3b 20 20 20 20 20 20 20 20 20 20   incr;          
0860: 20 20 20 20 2f 2a 20 66 6f 72 20 69 6e 63 72 65      /* for incre
0870: 6d 65 6e 74 69 6e 67 20 63 6f 64 65 2c 20 69 6e  menting code, in
0880: 64 65 78 20 2a 2f 0a 20 20 20 20 75 6e 73 69 67  dex */.    unsig
0890: 6e 65 64 20 66 69 6c 6c 3b 20 20 20 20 20 20 20  ned fill;       
08a0: 20 20 20 20 20 20 20 2f 2a 20 69 6e 64 65 78 20         /* index 
08b0: 66 6f 72 20 72 65 70 6c 69 63 61 74 69 6e 67 20  for replicating 
08c0: 65 6e 74 72 69 65 73 20 2a 2f 0a 20 20 20 20 75  entries */.    u
08d0: 6e 73 69 67 6e 65 64 20 6c 6f 77 3b 20 20 20 20  nsigned low;    
08e0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 6c 6f             /* lo
08f0: 77 20 62 69 74 73 20 66 6f 72 20 63 75 72 72 65  w bits for curre
0900: 6e 74 20 72 6f 6f 74 20 65 6e 74 72 79 20 2a 2f  nt root entry */
0910: 0a 20 20 20 20 75 6e 73 69 67 6e 65 64 20 6d 61  .    unsigned ma
0920: 73 6b 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  sk;             
0930: 20 2f 2a 20 6d 61 73 6b 20 66 6f 72 20 6c 6f 77   /* mask for low
0940: 20 72 6f 6f 74 20 62 69 74 73 20 2a 2f 0a 20 20   root bits */.  
0950: 20 20 63 6f 64 65 20 68 65 72 65 3b 20 20 20 20    code here;    
0960: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
0970: 20 74 61 62 6c 65 20 65 6e 74 72 79 20 66 6f 72   table entry for
0980: 20 64 75 70 6c 69 63 61 74 69 6f 6e 20 2a 2f 0a   duplication */.
0990: 20 20 20 20 63 6f 64 65 20 46 41 52 20 2a 6e 65      code FAR *ne
09a0: 78 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  xt;             
09b0: 2f 2a 20 6e 65 78 74 20 61 76 61 69 6c 61 62 6c  /* next availabl
09c0: 65 20 73 70 61 63 65 20 69 6e 20 74 61 62 6c 65  e space in table
09d0: 20 2a 2f 0a 20 20 20 20 63 6f 6e 73 74 20 75 6e   */.    const un
09e0: 73 69 67 6e 65 64 20 73 68 6f 72 74 20 46 41 52  signed short FAR
09f0: 20 2a 62 61 73 65 3b 20 20 20 20 20 2f 2a 20 62   *base;     /* b
0a00: 61 73 65 20 76 61 6c 75 65 20 74 61 62 6c 65 20  ase value table 
0a10: 74 6f 20 75 73 65 20 2a 2f 0a 20 20 20 20 63 6f  to use */.    co
0a20: 6e 73 74 20 75 6e 73 69 67 6e 65 64 20 73 68 6f  nst unsigned sho
0a30: 72 74 20 46 41 52 20 2a 65 78 74 72 61 3b 20 20  rt FAR *extra;  
0a40: 20 20 2f 2a 20 65 78 74 72 61 20 62 69 74 73 20    /* extra bits 
0a50: 74 61 62 6c 65 20 74 6f 20 75 73 65 20 2a 2f 0a  table to use */.
0a60: 20 20 20 20 69 6e 74 20 65 6e 64 3b 20 20 20 20      int end;    
0a70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0a80: 2f 2a 20 75 73 65 20 62 61 73 65 20 61 6e 64 20  /* use base and 
0a90: 65 78 74 72 61 20 66 6f 72 20 73 79 6d 62 6f 6c  extra for symbol
0aa0: 20 3e 20 65 6e 64 20 2a 2f 0a 20 20 20 20 75 6e   > end */.    un
0ab0: 73 69 67 6e 65 64 20 73 68 6f 72 74 20 63 6f 75  signed short cou
0ac0: 6e 74 5b 4d 41 58 42 49 54 53 2b 31 5d 3b 20 20  nt[MAXBITS+1];  
0ad0: 20 20 2f 2a 20 6e 75 6d 62 65 72 20 6f 66 20 63    /* number of c
0ae0: 6f 64 65 73 20 6f 66 20 65 61 63 68 20 6c 65 6e  odes of each len
0af0: 67 74 68 20 2a 2f 0a 20 20 20 20 75 6e 73 69 67  gth */.    unsig
0b00: 6e 65 64 20 73 68 6f 72 74 20 6f 66 66 73 5b 4d  ned short offs[M
0b10: 41 58 42 49 54 53 2b 31 5d 3b 20 20 20 20 20 2f  AXBITS+1];     /
0b20: 2a 20 6f 66 66 73 65 74 73 20 69 6e 20 74 61 62  * offsets in tab
0b30: 6c 65 20 66 6f 72 20 65 61 63 68 20 6c 65 6e 67  le for each leng
0b40: 74 68 20 2a 2f 0a 20 20 20 20 73 74 61 74 69 63  th */.    static
0b50: 20 63 6f 6e 73 74 20 75 6e 73 69 67 6e 65 64 20   const unsigned 
0b60: 73 68 6f 72 74 20 6c 62 61 73 65 5b 33 31 5d 20  short lbase[31] 
0b70: 3d 20 7b 20 2f 2a 20 4c 65 6e 67 74 68 20 63 6f  = { /* Length co
0b80: 64 65 73 20 32 35 37 2e 2e 32 38 35 20 62 61 73  des 257..285 bas
0b90: 65 20 2a 2f 0a 20 20 20 20 20 20 20 20 33 2c 20  e */.        3, 
0ba0: 34 2c 20 35 2c 20 36 2c 20 37 2c 20 38 2c 20 39  4, 5, 6, 7, 8, 9
0bb0: 2c 20 31 30 2c 20 31 31 2c 20 31 33 2c 20 31 35  , 10, 11, 13, 15
0bc0: 2c 20 31 37 2c 20 31 39 2c 20 32 33 2c 20 32 37  , 17, 19, 23, 27
0bd0: 2c 20 33 31 2c 0a 20 20 20 20 20 20 20 20 33 35  , 31,.        35
0be0: 2c 20 34 33 2c 20 35 31 2c 20 35 39 2c 20 36 37  , 43, 51, 59, 67
0bf0: 2c 20 38 33 2c 20 39 39 2c 20 31 31 35 2c 20 31  , 83, 99, 115, 1
0c00: 33 31 2c 20 31 36 33 2c 20 31 39 35 2c 20 32 32  31, 163, 195, 22
0c10: 37 2c 20 32 35 38 2c 20 30 2c 20 30 7d 3b 0a 20  7, 258, 0, 0};. 
0c20: 20 20 20 73 74 61 74 69 63 20 63 6f 6e 73 74 20     static const 
0c30: 75 6e 73 69 67 6e 65 64 20 73 68 6f 72 74 20 6c  unsigned short l
0c40: 65 78 74 5b 33 31 5d 20 3d 20 7b 20 2f 2a 20 4c  ext[31] = { /* L
0c50: 65 6e 67 74 68 20 63 6f 64 65 73 20 32 35 37 2e  ength codes 257.
0c60: 2e 32 38 35 20 65 78 74 72 61 20 2a 2f 0a 20 20  .285 extra */.  
0c70: 20 20 20 20 20 20 31 36 2c 20 31 36 2c 20 31 36        16, 16, 16
0c80: 2c 20 31 36 2c 20 31 36 2c 20 31 36 2c 20 31 36  , 16, 16, 16, 16
0c90: 2c 20 31 36 2c 20 31 37 2c 20 31 37 2c 20 31 37  , 16, 17, 17, 17
0ca0: 2c 20 31 37 2c 20 31 38 2c 20 31 38 2c 20 31 38  , 17, 18, 18, 18
0cb0: 2c 20 31 38 2c 0a 20 20 20 20 20 20 20 20 31 39  , 18,.        19
0cc0: 2c 20 31 39 2c 20 31 39 2c 20 31 39 2c 20 32 30  , 19, 19, 19, 20
0cd0: 2c 20 32 30 2c 20 32 30 2c 20 32 30 2c 20 32 31  , 20, 20, 20, 21
0ce0: 2c 20 32 31 2c 20 32 31 2c 20 32 31 2c 20 31 36  , 21, 21, 21, 16
0cf0: 2c 20 37 32 2c 20 37 38 7d 3b 0a 20 20 20 20 73  , 72, 78};.    s
0d00: 74 61 74 69 63 20 63 6f 6e 73 74 20 75 6e 73 69  tatic const unsi
0d10: 67 6e 65 64 20 73 68 6f 72 74 20 64 62 61 73 65  gned short dbase
0d20: 5b 33 32 5d 20 3d 20 7b 20 2f 2a 20 44 69 73 74  [32] = { /* Dist
0d30: 61 6e 63 65 20 63 6f 64 65 73 20 30 2e 2e 32 39  ance codes 0..29
0d40: 20 62 61 73 65 20 2a 2f 0a 20 20 20 20 20 20 20   base */.       
0d50: 20 31 2c 20 32 2c 20 33 2c 20 34 2c 20 35 2c 20   1, 2, 3, 4, 5, 
0d60: 37 2c 20 39 2c 20 31 33 2c 20 31 37 2c 20 32 35  7, 9, 13, 17, 25
0d70: 2c 20 33 33 2c 20 34 39 2c 20 36 35 2c 20 39 37  , 33, 49, 65, 97
0d80: 2c 20 31 32 39 2c 20 31 39 33 2c 0a 20 20 20 20  , 129, 193,.    
0d90: 20 20 20 20 32 35 37 2c 20 33 38 35 2c 20 35 31      257, 385, 51
0da0: 33 2c 20 37 36 39 2c 20 31 30 32 35 2c 20 31 35  3, 769, 1025, 15
0db0: 33 37 2c 20 32 30 34 39 2c 20 33 30 37 33 2c 20  37, 2049, 3073, 
0dc0: 34 30 39 37 2c 20 36 31 34 35 2c 0a 20 20 20 20  4097, 6145,.    
0dd0: 20 20 20 20 38 31 39 33 2c 20 31 32 32 38 39 2c      8193, 12289,
0de0: 20 31 36 33 38 35 2c 20 32 34 35 37 37 2c 20 30   16385, 24577, 0
0df0: 2c 20 30 7d 3b 0a 20 20 20 20 73 74 61 74 69 63  , 0};.    static
0e00: 20 63 6f 6e 73 74 20 75 6e 73 69 67 6e 65 64 20   const unsigned 
0e10: 73 68 6f 72 74 20 64 65 78 74 5b 33 32 5d 20 3d  short dext[32] =
0e20: 20 7b 20 2f 2a 20 44 69 73 74 61 6e 63 65 20 63   { /* Distance c
0e30: 6f 64 65 73 20 30 2e 2e 32 39 20 65 78 74 72 61  odes 0..29 extra
0e40: 20 2a 2f 0a 20 20 20 20 20 20 20 20 31 36 2c 20   */.        16, 
0e50: 31 36 2c 20 31 36 2c 20 31 36 2c 20 31 37 2c 20  16, 16, 16, 17, 
0e60: 31 37 2c 20 31 38 2c 20 31 38 2c 20 31 39 2c 20  17, 18, 18, 19, 
0e70: 31 39 2c 20 32 30 2c 20 32 30 2c 20 32 31 2c 20  19, 20, 20, 21, 
0e80: 32 31 2c 20 32 32 2c 20 32 32 2c 0a 20 20 20 20  21, 22, 22,.    
0e90: 20 20 20 20 32 33 2c 20 32 33 2c 20 32 34 2c 20      23, 23, 24, 
0ea0: 32 34 2c 20 32 35 2c 20 32 35 2c 20 32 36 2c 20  24, 25, 25, 26, 
0eb0: 32 36 2c 20 32 37 2c 20 32 37 2c 0a 20 20 20 20  26, 27, 27,.    
0ec0: 20 20 20 20 32 38 2c 20 32 38 2c 20 32 39 2c 20      28, 28, 29, 
0ed0: 32 39 2c 20 36 34 2c 20 36 34 7d 3b 0a 0a 20 20  29, 64, 64};..  
0ee0: 20 20 2f 2a 0a 20 20 20 20 20 20 20 50 72 6f 63    /*.       Proc
0ef0: 65 73 73 20 61 20 73 65 74 20 6f 66 20 63 6f 64  ess a set of cod
0f00: 65 20 6c 65 6e 67 74 68 73 20 74 6f 20 63 72 65  e lengths to cre
0f10: 61 74 65 20 61 20 63 61 6e 6f 6e 69 63 61 6c 20  ate a canonical 
0f20: 48 75 66 66 6d 61 6e 20 63 6f 64 65 2e 20 20 54  Huffman code.  T
0f30: 68 65 0a 20 20 20 20 20 20 20 63 6f 64 65 20 6c  he.       code l
0f40: 65 6e 67 74 68 73 20 61 72 65 20 6c 65 6e 73 5b  engths are lens[
0f50: 30 2e 2e 63 6f 64 65 73 2d 31 5d 2e 20 20 45 61  0..codes-1].  Ea
0f60: 63 68 20 6c 65 6e 67 74 68 20 63 6f 72 72 65 73  ch length corres
0f70: 70 6f 6e 64 73 20 74 6f 20 74 68 65 0a 20 20 20  ponds to the.   
0f80: 20 20 20 20 73 79 6d 62 6f 6c 73 20 30 2e 2e 63      symbols 0..c
0f90: 6f 64 65 73 2d 31 2e 20 20 54 68 65 20 48 75 66  odes-1.  The Huf
0fa0: 66 6d 61 6e 20 63 6f 64 65 20 69 73 20 67 65 6e  fman code is gen
0fb0: 65 72 61 74 65 64 20 62 79 20 66 69 72 73 74 20  erated by first 
0fc0: 73 6f 72 74 69 6e 67 20 74 68 65 0a 20 20 20 20  sorting the.    
0fd0: 20 20 20 73 79 6d 62 6f 6c 73 20 62 79 20 6c 65     symbols by le
0fe0: 6e 67 74 68 20 66 72 6f 6d 20 73 68 6f 72 74 20  ngth from short 
0ff0: 74 6f 20 6c 6f 6e 67 2c 20 61 6e 64 20 72 65 74  to long, and ret
1000: 61 69 6e 69 6e 67 20 74 68 65 20 73 79 6d 62 6f  aining the symbo
1010: 6c 20 6f 72 64 65 72 0a 20 20 20 20 20 20 20 66  l order.       f
1020: 6f 72 20 63 6f 64 65 73 20 77 69 74 68 20 65 71  or codes with eq
1030: 75 61 6c 20 6c 65 6e 67 74 68 73 2e 20 20 54 68  ual lengths.  Th
1040: 65 6e 20 74 68 65 20 63 6f 64 65 20 73 74 61 72  en the code star
1050: 74 73 20 77 69 74 68 20 61 6c 6c 20 7a 65 72 6f  ts with all zero
1060: 20 62 69 74 73 0a 20 20 20 20 20 20 20 66 6f 72   bits.       for
1070: 20 74 68 65 20 66 69 72 73 74 20 63 6f 64 65 20   the first code 
1080: 6f 66 20 74 68 65 20 73 68 6f 72 74 65 73 74 20  of the shortest 
1090: 6c 65 6e 67 74 68 2c 20 61 6e 64 20 74 68 65 20  length, and the 
10a0: 63 6f 64 65 73 20 61 72 65 20 69 6e 74 65 67 65  codes are intege
10b0: 72 0a 20 20 20 20 20 20 20 69 6e 63 72 65 6d 65  r.       increme
10c0: 6e 74 73 20 66 6f 72 20 74 68 65 20 73 61 6d 65  nts for the same
10d0: 20 6c 65 6e 67 74 68 2c 20 61 6e 64 20 7a 65 72   length, and zer
10e0: 6f 73 20 61 72 65 20 61 70 70 65 6e 64 65 64 20  os are appended 
10f0: 61 73 20 74 68 65 20 6c 65 6e 67 74 68 0a 20 20  as the length.  
1100: 20 20 20 20 20 69 6e 63 72 65 61 73 65 73 2e 20       increases. 
1110: 20 46 6f 72 20 74 68 65 20 64 65 66 6c 61 74 65   For the deflate
1120: 20 66 6f 72 6d 61 74 2c 20 74 68 65 73 65 20 62   format, these b
1130: 69 74 73 20 61 72 65 20 73 74 6f 72 65 64 20 62  its are stored b
1140: 61 63 6b 77 61 72 64 73 0a 20 20 20 20 20 20 20  ackwards.       
1150: 66 72 6f 6d 20 74 68 65 69 72 20 6d 6f 72 65 20  from their more 
1160: 6e 61 74 75 72 61 6c 20 69 6e 74 65 67 65 72 20  natural integer 
1170: 69 6e 63 72 65 6d 65 6e 74 20 6f 72 64 65 72 69  increment orderi
1180: 6e 67 2c 20 61 6e 64 20 73 6f 20 77 68 65 6e 20  ng, and so when 
1190: 74 68 65 0a 20 20 20 20 20 20 20 64 65 63 6f 64  the.       decod
11a0: 69 6e 67 20 74 61 62 6c 65 73 20 61 72 65 20 62  ing tables are b
11b0: 75 69 6c 74 20 69 6e 20 74 68 65 20 6c 61 72 67  uilt in the larg
11c0: 65 20 6c 6f 6f 70 20 62 65 6c 6f 77 2c 20 74 68  e loop below, th
11d0: 65 20 69 6e 74 65 67 65 72 20 63 6f 64 65 73 0a  e integer codes.
11e0: 20 20 20 20 20 20 20 61 72 65 20 69 6e 63 72 65         are incre
11f0: 6d 65 6e 74 65 64 20 62 61 63 6b 77 61 72 64 73  mented backwards
1200: 2e 0a 0a 20 20 20 20 20 20 20 54 68 69 73 20 72  ...       This r
1210: 6f 75 74 69 6e 65 20 61 73 73 75 6d 65 73 2c 20  outine assumes, 
1220: 62 75 74 20 64 6f 65 73 20 6e 6f 74 20 63 68 65  but does not che
1230: 63 6b 2c 20 74 68 61 74 20 61 6c 6c 20 6f 66 20  ck, that all of 
1240: 74 68 65 20 65 6e 74 72 69 65 73 20 69 6e 0a 20  the entries in. 
1250: 20 20 20 20 20 20 6c 65 6e 73 5b 5d 20 61 72 65        lens[] are
1260: 20 69 6e 20 74 68 65 20 72 61 6e 67 65 20 30 2e   in the range 0.
1270: 2e 4d 41 58 42 49 54 53 2e 20 20 54 68 65 20 63  .MAXBITS.  The c
1280: 61 6c 6c 65 72 20 6d 75 73 74 20 61 73 73 75 72  aller must assur
1290: 65 20 74 68 69 73 2e 0a 20 20 20 20 20 20 20 31  e this..       1
12a0: 2e 2e 4d 41 58 42 49 54 53 20 69 73 20 69 6e 74  ..MAXBITS is int
12b0: 65 72 70 72 65 74 65 64 20 61 73 20 74 68 61 74  erpreted as that
12c0: 20 63 6f 64 65 20 6c 65 6e 67 74 68 2e 20 20 7a   code length.  z
12d0: 65 72 6f 20 6d 65 61 6e 73 20 74 68 61 74 20 74  ero means that t
12e0: 68 61 74 0a 20 20 20 20 20 20 20 73 79 6d 62 6f  hat.       symbo
12f0: 6c 20 64 6f 65 73 20 6e 6f 74 20 6f 63 63 75 72  l does not occur
1300: 20 69 6e 20 74 68 69 73 20 63 6f 64 65 2e 0a 0a   in this code...
1310: 20 20 20 20 20 20 20 54 68 65 20 63 6f 64 65 73         The codes
1320: 20 61 72 65 20 73 6f 72 74 65 64 20 62 79 20 63   are sorted by c
1330: 6f 6d 70 75 74 69 6e 67 20 61 20 63 6f 75 6e 74  omputing a count
1340: 20 6f 66 20 63 6f 64 65 73 20 66 6f 72 20 65 61   of codes for ea
1350: 63 68 20 6c 65 6e 67 74 68 2c 0a 20 20 20 20 20  ch length,.     
1360: 20 20 63 72 65 61 74 69 6e 67 20 66 72 6f 6d 20    creating from 
1370: 74 68 61 74 20 61 20 74 61 62 6c 65 20 6f 66 20  that a table of 
1380: 73 74 61 72 74 69 6e 67 20 69 6e 64 69 63 65 73  starting indices
1390: 20 66 6f 72 20 65 61 63 68 20 6c 65 6e 67 74 68   for each length
13a0: 20 69 6e 20 74 68 65 0a 20 20 20 20 20 20 20 73   in the.       s
13b0: 6f 72 74 65 64 20 74 61 62 6c 65 2c 20 61 6e 64  orted table, and
13c0: 20 74 68 65 6e 20 65 6e 74 65 72 69 6e 67 20 74   then entering t
13d0: 68 65 20 73 79 6d 62 6f 6c 73 20 69 6e 20 6f 72  he symbols in or
13e0: 64 65 72 20 69 6e 20 74 68 65 20 73 6f 72 74 65  der in the sorte
13f0: 64 0a 20 20 20 20 20 20 20 74 61 62 6c 65 2e 20  d.       table. 
1400: 20 54 68 65 20 73 6f 72 74 65 64 20 74 61 62 6c   The sorted tabl
1410: 65 20 69 73 20 77 6f 72 6b 5b 5d 2c 20 77 69 74  e is work[], wit
1420: 68 20 74 68 61 74 20 73 70 61 63 65 20 62 65 69  h that space bei
1430: 6e 67 20 70 72 6f 76 69 64 65 64 20 62 79 0a 20  ng provided by. 
1440: 20 20 20 20 20 20 74 68 65 20 63 61 6c 6c 65 72        the caller
1450: 2e 0a 0a 20 20 20 20 20 20 20 54 68 65 20 6c 65  ...       The le
1460: 6e 67 74 68 20 63 6f 75 6e 74 73 20 61 72 65 20  ngth counts are 
1470: 75 73 65 64 20 66 6f 72 20 6f 74 68 65 72 20 70  used for other p
1480: 75 72 70 6f 73 65 73 20 61 73 20 77 65 6c 6c 2c  urposes as well,
1490: 20 69 2e 65 2e 20 66 69 6e 64 69 6e 67 0a 20 20   i.e. finding.  
14a0: 20 20 20 20 20 74 68 65 20 6d 69 6e 69 6d 75 6d       the minimum
14b0: 20 61 6e 64 20 6d 61 78 69 6d 75 6d 20 6c 65 6e   and maximum len
14c0: 67 74 68 20 63 6f 64 65 73 2c 20 64 65 74 65 72  gth codes, deter
14d0: 6d 69 6e 69 6e 67 20 69 66 20 74 68 65 72 65 20  mining if there 
14e0: 61 72 65 20 61 6e 79 0a 20 20 20 20 20 20 20 63  are any.       c
14f0: 6f 64 65 73 20 61 74 20 61 6c 6c 2c 20 63 68 65  odes at all, che
1500: 63 6b 69 6e 67 20 66 6f 72 20 61 20 76 61 6c 69  cking for a vali
1510: 64 20 73 65 74 20 6f 66 20 6c 65 6e 67 74 68 73  d set of lengths
1520: 2c 20 61 6e 64 20 6c 6f 6f 6b 69 6e 67 20 61 68  , and looking ah
1530: 65 61 64 0a 20 20 20 20 20 20 20 61 74 20 6c 65  ead.       at le
1540: 6e 67 74 68 20 63 6f 75 6e 74 73 20 74 6f 20 64  ngth counts to d
1550: 65 74 65 72 6d 69 6e 65 20 73 75 62 2d 74 61 62  etermine sub-tab
1560: 6c 65 20 73 69 7a 65 73 20 77 68 65 6e 20 62 75  le sizes when bu
1570: 69 6c 64 69 6e 67 20 74 68 65 0a 20 20 20 20 20  ilding the.     
1580: 20 20 64 65 63 6f 64 69 6e 67 20 74 61 62 6c 65    decoding table
1590: 73 2e 0a 20 20 20 20 20 2a 2f 0a 0a 20 20 20 20  s..     */..    
15a0: 2f 2a 20 61 63 63 75 6d 75 6c 61 74 65 20 6c 65  /* accumulate le
15b0: 6e 67 74 68 73 20 66 6f 72 20 63 6f 64 65 73 20  ngths for codes 
15c0: 28 61 73 73 75 6d 65 73 20 6c 65 6e 73 5b 5d 20  (assumes lens[] 
15d0: 61 6c 6c 20 69 6e 20 30 2e 2e 4d 41 58 42 49 54  all in 0..MAXBIT
15e0: 53 29 20 2a 2f 0a 20 20 20 20 66 6f 72 20 28 6c  S) */.    for (l
15f0: 65 6e 20 3d 20 30 3b 20 6c 65 6e 20 3c 3d 20 4d  en = 0; len <= M
1600: 41 58 42 49 54 53 3b 20 6c 65 6e 2b 2b 29 0a 20  AXBITS; len++). 
1610: 20 20 20 20 20 20 20 63 6f 75 6e 74 5b 6c 65 6e         count[len
1620: 5d 20 3d 20 30 3b 0a 20 20 20 20 66 6f 72 20 28  ] = 0;.    for (
1630: 73 79 6d 20 3d 20 30 3b 20 73 79 6d 20 3c 20 63  sym = 0; sym < c
1640: 6f 64 65 73 3b 20 73 79 6d 2b 2b 29 0a 20 20 20  odes; sym++).   
1650: 20 20 20 20 20 63 6f 75 6e 74 5b 6c 65 6e 73 5b       count[lens[
1660: 73 79 6d 5d 5d 2b 2b 3b 0a 0a 20 20 20 20 2f 2a  sym]]++;..    /*
1670: 20 62 6f 75 6e 64 20 63 6f 64 65 20 6c 65 6e 67   bound code leng
1680: 74 68 73 2c 20 66 6f 72 63 65 20 72 6f 6f 74 20  ths, force root 
1690: 74 6f 20 62 65 20 77 69 74 68 69 6e 20 63 6f 64  to be within cod
16a0: 65 20 6c 65 6e 67 74 68 73 20 2a 2f 0a 20 20 20  e lengths */.   
16b0: 20 72 6f 6f 74 20 3d 20 2a 62 69 74 73 3b 0a 20   root = *bits;. 
16c0: 20 20 20 66 6f 72 20 28 6d 61 78 20 3d 20 4d 41     for (max = MA
16d0: 58 42 49 54 53 3b 20 6d 61 78 20 3e 3d 20 31 3b  XBITS; max >= 1;
16e0: 20 6d 61 78 2d 2d 29 0a 20 20 20 20 20 20 20 20   max--).        
16f0: 69 66 20 28 63 6f 75 6e 74 5b 6d 61 78 5d 20 21  if (count[max] !
1700: 3d 20 30 29 20 62 72 65 61 6b 3b 0a 20 20 20 20  = 0) break;.    
1710: 69 66 20 28 72 6f 6f 74 20 3e 20 6d 61 78 29 20  if (root > max) 
1720: 72 6f 6f 74 20 3d 20 6d 61 78 3b 0a 20 20 20 20  root = max;.    
1730: 69 66 20 28 6d 61 78 20 3d 3d 20 30 29 20 7b 20  if (max == 0) { 
1740: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1750: 20 20 20 20 2f 2a 20 6e 6f 20 73 79 6d 62 6f 6c      /* no symbol
1760: 73 20 74 6f 20 63 6f 64 65 20 61 74 20 61 6c 6c  s to code at all
1770: 20 2a 2f 0a 20 20 20 20 20 20 20 20 68 65 72 65   */.        here
1780: 2e 6f 70 20 3d 20 28 75 6e 73 69 67 6e 65 64 20  .op = (unsigned 
1790: 63 68 61 72 29 36 34 3b 20 20 20 20 2f 2a 20 69  char)64;    /* i
17a0: 6e 76 61 6c 69 64 20 63 6f 64 65 20 6d 61 72 6b  nvalid code mark
17b0: 65 72 20 2a 2f 0a 20 20 20 20 20 20 20 20 68 65  er */.        he
17c0: 72 65 2e 62 69 74 73 20 3d 20 28 75 6e 73 69 67  re.bits = (unsig
17d0: 6e 65 64 20 63 68 61 72 29 31 3b 0a 20 20 20 20  ned char)1;.    
17e0: 20 20 20 20 68 65 72 65 2e 76 61 6c 20 3d 20 28      here.val = (
17f0: 75 6e 73 69 67 6e 65 64 20 73 68 6f 72 74 29 30  unsigned short)0
1800: 3b 0a 20 20 20 20 20 20 20 20 2a 28 2a 74 61 62  ;.        *(*tab
1810: 6c 65 29 2b 2b 20 3d 20 68 65 72 65 3b 20 20 20  le)++ = here;   
1820: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 6d 61 6b            /* mak
1830: 65 20 61 20 74 61 62 6c 65 20 74 6f 20 66 6f 72  e a table to for
1840: 63 65 20 61 6e 20 65 72 72 6f 72 20 2a 2f 0a 20  ce an error */. 
1850: 20 20 20 20 20 20 20 2a 28 2a 74 61 62 6c 65 29         *(*table)
1860: 2b 2b 20 3d 20 68 65 72 65 3b 0a 20 20 20 20 20  ++ = here;.     
1870: 20 20 20 2a 62 69 74 73 20 3d 20 31 3b 0a 20 20     *bits = 1;.  
1880: 20 20 20 20 20 20 72 65 74 75 72 6e 20 30 3b 20        return 0; 
1890: 20 20 20 20 2f 2a 20 6e 6f 20 73 79 6d 62 6f 6c      /* no symbol
18a0: 73 2c 20 62 75 74 20 77 61 69 74 20 66 6f 72 20  s, but wait for 
18b0: 64 65 63 6f 64 69 6e 67 20 74 6f 20 72 65 70 6f  decoding to repo
18c0: 72 74 20 65 72 72 6f 72 20 2a 2f 0a 20 20 20 20  rt error */.    
18d0: 7d 0a 20 20 20 20 66 6f 72 20 28 6d 69 6e 20 3d  }.    for (min =
18e0: 20 31 3b 20 6d 69 6e 20 3c 20 6d 61 78 3b 20 6d   1; min < max; m
18f0: 69 6e 2b 2b 29 0a 20 20 20 20 20 20 20 20 69 66  in++).        if
1900: 20 28 63 6f 75 6e 74 5b 6d 69 6e 5d 20 21 3d 20   (count[min] != 
1910: 30 29 20 62 72 65 61 6b 3b 0a 20 20 20 20 69 66  0) break;.    if
1920: 20 28 72 6f 6f 74 20 3c 20 6d 69 6e 29 20 72 6f   (root < min) ro
1930: 6f 74 20 3d 20 6d 69 6e 3b 0a 0a 20 20 20 20 2f  ot = min;..    /
1940: 2a 20 63 68 65 63 6b 20 66 6f 72 20 61 6e 20 6f  * check for an o
1950: 76 65 72 2d 73 75 62 73 63 72 69 62 65 64 20 6f  ver-subscribed o
1960: 72 20 69 6e 63 6f 6d 70 6c 65 74 65 20 73 65 74  r incomplete set
1970: 20 6f 66 20 6c 65 6e 67 74 68 73 20 2a 2f 0a 20   of lengths */. 
1980: 20 20 20 6c 65 66 74 20 3d 20 31 3b 0a 20 20 20     left = 1;.   
1990: 20 66 6f 72 20 28 6c 65 6e 20 3d 20 31 3b 20 6c   for (len = 1; l
19a0: 65 6e 20 3c 3d 20 4d 41 58 42 49 54 53 3b 20 6c  en <= MAXBITS; l
19b0: 65 6e 2b 2b 29 20 7b 0a 20 20 20 20 20 20 20 20  en++) {.        
19c0: 6c 65 66 74 20 3c 3c 3d 20 31 3b 0a 20 20 20 20  left <<= 1;.    
19d0: 20 20 20 20 6c 65 66 74 20 2d 3d 20 63 6f 75 6e      left -= coun
19e0: 74 5b 6c 65 6e 5d 3b 0a 20 20 20 20 20 20 20 20  t[len];.        
19f0: 69 66 20 28 6c 65 66 74 20 3c 20 30 29 20 72 65  if (left < 0) re
1a00: 74 75 72 6e 20 2d 31 3b 20 20 20 20 20 20 20 20  turn -1;        
1a10: 2f 2a 20 6f 76 65 72 2d 73 75 62 73 63 72 69 62  /* over-subscrib
1a20: 65 64 20 2a 2f 0a 20 20 20 20 7d 0a 20 20 20 20  ed */.    }.    
1a30: 69 66 20 28 6c 65 66 74 20 3e 20 30 20 26 26 20  if (left > 0 && 
1a40: 28 74 79 70 65 20 3d 3d 20 43 4f 44 45 53 20 7c  (type == CODES |
1a50: 7c 20 6d 61 78 20 21 3d 20 31 29 29 0a 20 20 20  | max != 1)).   
1a60: 20 20 20 20 20 72 65 74 75 72 6e 20 2d 31 3b 20       return -1; 
1a70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1a80: 20 20 20 20 20 2f 2a 20 69 6e 63 6f 6d 70 6c 65       /* incomple
1a90: 74 65 20 73 65 74 20 2a 2f 0a 0a 20 20 20 20 2f  te set */..    /
1aa0: 2a 20 67 65 6e 65 72 61 74 65 20 6f 66 66 73 65  * generate offse
1ab0: 74 73 20 69 6e 74 6f 20 73 79 6d 62 6f 6c 20 74  ts into symbol t
1ac0: 61 62 6c 65 20 66 6f 72 20 65 61 63 68 20 6c 65  able for each le
1ad0: 6e 67 74 68 20 66 6f 72 20 73 6f 72 74 69 6e 67  ngth for sorting
1ae0: 20 2a 2f 0a 20 20 20 20 6f 66 66 73 5b 31 5d 20   */.    offs[1] 
1af0: 3d 20 30 3b 0a 20 20 20 20 66 6f 72 20 28 6c 65  = 0;.    for (le
1b00: 6e 20 3d 20 31 3b 20 6c 65 6e 20 3c 20 4d 41 58  n = 1; len < MAX
1b10: 42 49 54 53 3b 20 6c 65 6e 2b 2b 29 0a 20 20 20  BITS; len++).   
1b20: 20 20 20 20 20 6f 66 66 73 5b 6c 65 6e 20 2b 20       offs[len + 
1b30: 31 5d 20 3d 20 6f 66 66 73 5b 6c 65 6e 5d 20 2b  1] = offs[len] +
1b40: 20 63 6f 75 6e 74 5b 6c 65 6e 5d 3b 0a 0a 20 20   count[len];..  
1b50: 20 20 2f 2a 20 73 6f 72 74 20 73 79 6d 62 6f 6c    /* sort symbol
1b60: 73 20 62 79 20 6c 65 6e 67 74 68 2c 20 62 79 20  s by length, by 
1b70: 73 79 6d 62 6f 6c 20 6f 72 64 65 72 20 77 69 74  symbol order wit
1b80: 68 69 6e 20 65 61 63 68 20 6c 65 6e 67 74 68 20  hin each length 
1b90: 2a 2f 0a 20 20 20 20 66 6f 72 20 28 73 79 6d 20  */.    for (sym 
1ba0: 3d 20 30 3b 20 73 79 6d 20 3c 20 63 6f 64 65 73  = 0; sym < codes
1bb0: 3b 20 73 79 6d 2b 2b 29 0a 20 20 20 20 20 20 20  ; sym++).       
1bc0: 20 69 66 20 28 6c 65 6e 73 5b 73 79 6d 5d 20 21   if (lens[sym] !
1bd0: 3d 20 30 29 20 77 6f 72 6b 5b 6f 66 66 73 5b 6c  = 0) work[offs[l
1be0: 65 6e 73 5b 73 79 6d 5d 5d 2b 2b 5d 20 3d 20 28  ens[sym]]++] = (
1bf0: 75 6e 73 69 67 6e 65 64 20 73 68 6f 72 74 29 73  unsigned short)s
1c00: 79 6d 3b 0a 0a 20 20 20 20 2f 2a 0a 20 20 20 20  ym;..    /*.    
1c10: 20 20 20 43 72 65 61 74 65 20 61 6e 64 20 66 69     Create and fi
1c20: 6c 6c 20 69 6e 20 64 65 63 6f 64 69 6e 67 20 74  ll in decoding t
1c30: 61 62 6c 65 73 2e 20 20 49 6e 20 74 68 69 73 20  ables.  In this 
1c40: 6c 6f 6f 70 2c 20 74 68 65 20 74 61 62 6c 65 20  loop, the table 
1c50: 62 65 69 6e 67 0a 20 20 20 20 20 20 20 66 69 6c  being.       fil
1c60: 6c 65 64 20 69 73 20 61 74 20 6e 65 78 74 20 61  led is at next a
1c70: 6e 64 20 68 61 73 20 63 75 72 72 20 69 6e 64 65  nd has curr inde
1c80: 78 20 62 69 74 73 2e 20 20 54 68 65 20 63 6f 64  x bits.  The cod
1c90: 65 20 62 65 69 6e 67 20 75 73 65 64 20 69 73 20  e being used is 
1ca0: 68 75 66 66 0a 20 20 20 20 20 20 20 77 69 74 68  huff.       with
1cb0: 20 6c 65 6e 67 74 68 20 6c 65 6e 2e 20 20 54 68   length len.  Th
1cc0: 61 74 20 63 6f 64 65 20 69 73 20 63 6f 6e 76 65  at code is conve
1cd0: 72 74 65 64 20 74 6f 20 61 6e 20 69 6e 64 65 78  rted to an index
1ce0: 20 62 79 20 64 72 6f 70 70 69 6e 67 20 64 72 6f   by dropping dro
1cf0: 70 0a 20 20 20 20 20 20 20 62 69 74 73 20 6f 66  p.       bits of
1d00: 66 20 6f 66 20 74 68 65 20 62 6f 74 74 6f 6d 2e  f of the bottom.
1d10: 20 20 46 6f 72 20 63 6f 64 65 73 20 77 68 65 72    For codes wher
1d20: 65 20 6c 65 6e 20 69 73 20 6c 65 73 73 20 74 68  e len is less th
1d30: 61 6e 20 64 72 6f 70 20 2b 20 63 75 72 72 2c 0a  an drop + curr,.
1d40: 20 20 20 20 20 20 20 74 68 6f 73 65 20 74 6f 70         those top
1d50: 20 64 72 6f 70 20 2b 20 63 75 72 72 20 2d 20 6c   drop + curr - l
1d60: 65 6e 20 62 69 74 73 20 61 72 65 20 69 6e 63 72  en bits are incr
1d70: 65 6d 65 6e 74 65 64 20 74 68 72 6f 75 67 68 20  emented through 
1d80: 61 6c 6c 20 76 61 6c 75 65 73 20 74 6f 0a 20 20  all values to.  
1d90: 20 20 20 20 20 66 69 6c 6c 20 74 68 65 20 74 61       fill the ta
1da0: 62 6c 65 20 77 69 74 68 20 72 65 70 6c 69 63 61  ble with replica
1db0: 74 65 64 20 65 6e 74 72 69 65 73 2e 0a 0a 20 20  ted entries...  
1dc0: 20 20 20 20 20 72 6f 6f 74 20 69 73 20 74 68 65       root is the
1dd0: 20 6e 75 6d 62 65 72 20 6f 66 20 69 6e 64 65 78   number of index
1de0: 20 62 69 74 73 20 66 6f 72 20 74 68 65 20 72 6f   bits for the ro
1df0: 6f 74 20 74 61 62 6c 65 2e 20 20 57 68 65 6e 20  ot table.  When 
1e00: 6c 65 6e 20 65 78 63 65 65 64 73 0a 20 20 20 20  len exceeds.    
1e10: 20 20 20 72 6f 6f 74 2c 20 73 75 62 2d 74 61 62     root, sub-tab
1e20: 6c 65 73 20 61 72 65 20 63 72 65 61 74 65 64 20  les are created 
1e30: 70 6f 69 6e 74 65 64 20 74 6f 20 62 79 20 74 68  pointed to by th
1e40: 65 20 72 6f 6f 74 20 65 6e 74 72 79 20 77 69 74  e root entry wit
1e50: 68 20 61 6e 20 69 6e 64 65 78 0a 20 20 20 20 20  h an index.     
1e60: 20 20 6f 66 20 74 68 65 20 6c 6f 77 20 72 6f 6f    of the low roo
1e70: 74 20 62 69 74 73 20 6f 66 20 68 75 66 66 2e 20  t bits of huff. 
1e80: 20 54 68 69 73 20 69 73 20 73 61 76 65 64 20 69   This is saved i
1e90: 6e 20 6c 6f 77 20 74 6f 20 63 68 65 63 6b 20 66  n low to check f
1ea0: 6f 72 20 77 68 65 6e 20 61 0a 20 20 20 20 20 20  or when a.      
1eb0: 20 6e 65 77 20 73 75 62 2d 74 61 62 6c 65 20 73   new sub-table s
1ec0: 68 6f 75 6c 64 20 62 65 20 73 74 61 72 74 65 64  hould be started
1ed0: 2e 20 20 64 72 6f 70 20 69 73 20 7a 65 72 6f 20  .  drop is zero 
1ee0: 77 68 65 6e 20 74 68 65 20 72 6f 6f 74 20 74 61  when the root ta
1ef0: 62 6c 65 20 69 73 0a 20 20 20 20 20 20 20 62 65  ble is.       be
1f00: 69 6e 67 20 66 69 6c 6c 65 64 2c 20 61 6e 64 20  ing filled, and 
1f10: 64 72 6f 70 20 69 73 20 72 6f 6f 74 20 77 68 65  drop is root whe
1f20: 6e 20 73 75 62 2d 74 61 62 6c 65 73 20 61 72 65  n sub-tables are
1f30: 20 62 65 69 6e 67 20 66 69 6c 6c 65 64 2e 0a 0a   being filled...
1f40: 20 20 20 20 20 20 20 57 68 65 6e 20 61 20 6e 65         When a ne
1f50: 77 20 73 75 62 2d 74 61 62 6c 65 20 69 73 20 6e  w sub-table is n
1f60: 65 65 64 65 64 2c 20 69 74 20 69 73 20 6e 65 63  eeded, it is nec
1f70: 65 73 73 61 72 79 20 74 6f 20 6c 6f 6f 6b 20 61  essary to look a
1f80: 68 65 61 64 20 69 6e 20 74 68 65 0a 20 20 20 20  head in the.    
1f90: 20 20 20 63 6f 64 65 20 6c 65 6e 67 74 68 73 20     code lengths 
1fa0: 74 6f 20 64 65 74 65 72 6d 69 6e 65 20 77 68 61  to determine wha
1fb0: 74 20 73 69 7a 65 20 73 75 62 2d 74 61 62 6c 65  t size sub-table
1fc0: 20 69 73 20 6e 65 65 64 65 64 2e 20 20 54 68 65   is needed.  The
1fd0: 20 6c 65 6e 67 74 68 0a 20 20 20 20 20 20 20 63   length.       c
1fe0: 6f 75 6e 74 73 20 61 72 65 20 75 73 65 64 20 66  ounts are used f
1ff0: 6f 72 20 74 68 69 73 2c 20 61 6e 64 20 73 6f 20  or this, and so 
2000: 63 6f 75 6e 74 5b 5d 20 69 73 20 64 65 63 72 65  count[] is decre
2010: 6d 65 6e 74 65 64 20 61 73 20 63 6f 64 65 73 20  mented as codes 
2020: 61 72 65 0a 20 20 20 20 20 20 20 65 6e 74 65 72  are.       enter
2030: 65 64 20 69 6e 20 74 68 65 20 74 61 62 6c 65 73  ed in the tables
2040: 2e 0a 0a 20 20 20 20 20 20 20 75 73 65 64 20 6b  ...       used k
2050: 65 65 70 73 20 74 72 61 63 6b 20 6f 66 20 68 6f  eeps track of ho
2060: 77 20 6d 61 6e 79 20 74 61 62 6c 65 20 65 6e 74  w many table ent
2070: 72 69 65 73 20 68 61 76 65 20 62 65 65 6e 20 61  ries have been a
2080: 6c 6c 6f 63 61 74 65 64 20 66 72 6f 6d 20 74 68  llocated from th
2090: 65 0a 20 20 20 20 20 20 20 70 72 6f 76 69 64 65  e.       provide
20a0: 64 20 2a 74 61 62 6c 65 20 73 70 61 63 65 2e 20  d *table space. 
20b0: 20 49 74 20 69 73 20 63 68 65 63 6b 65 64 20 66   It is checked f
20c0: 6f 72 20 4c 45 4e 53 20 61 6e 64 20 44 49 53 54  or LENS and DIST
20d0: 20 74 61 62 6c 65 73 20 61 67 61 69 6e 73 74 0a   tables against.
20e0: 20 20 20 20 20 20 20 74 68 65 20 63 6f 6e 73 74         the const
20f0: 61 6e 74 73 20 45 4e 4f 55 47 48 5f 4c 45 4e 53  ants ENOUGH_LENS
2100: 20 61 6e 64 20 45 4e 4f 55 47 48 5f 44 49 53 54   and ENOUGH_DIST
2110: 53 20 74 6f 20 67 75 61 72 64 20 61 67 61 69 6e  S to guard again
2120: 73 74 20 63 68 61 6e 67 65 73 20 69 6e 0a 20 20  st changes in.  
2130: 20 20 20 20 20 74 68 65 20 69 6e 69 74 69 61 6c       the initial
2140: 20 72 6f 6f 74 20 74 61 62 6c 65 20 73 69 7a 65   root table size
2150: 20 63 6f 6e 73 74 61 6e 74 73 2e 20 20 53 65 65   constants.  See
2160: 20 74 68 65 20 63 6f 6d 6d 65 6e 74 73 20 69 6e   the comments in
2170: 20 69 6e 66 74 72 65 65 73 2e 68 0a 20 20 20 20   inftrees.h.    
2180: 20 20 20 66 6f 72 20 6d 6f 72 65 20 69 6e 66 6f     for more info
2190: 72 6d 61 74 69 6f 6e 2e 0a 0a 20 20 20 20 20 20  rmation...      
21a0: 20 73 79 6d 20 69 6e 63 72 65 6d 65 6e 74 73 20   sym increments 
21b0: 74 68 72 6f 75 67 68 20 61 6c 6c 20 73 79 6d 62  through all symb
21c0: 6f 6c 73 2c 20 61 6e 64 20 74 68 65 20 6c 6f 6f  ols, and the loo
21d0: 70 20 74 65 72 6d 69 6e 61 74 65 73 20 77 68 65  p terminates whe
21e0: 6e 0a 20 20 20 20 20 20 20 61 6c 6c 20 63 6f 64  n.       all cod
21f0: 65 73 20 6f 66 20 6c 65 6e 67 74 68 20 6d 61 78  es of length max
2200: 2c 20 69 2e 65 2e 20 61 6c 6c 20 63 6f 64 65 73  , i.e. all codes
2210: 2c 20 68 61 76 65 20 62 65 65 6e 20 70 72 6f 63  , have been proc
2220: 65 73 73 65 64 2e 20 20 54 68 69 73 0a 20 20 20  essed.  This.   
2230: 20 20 20 20 72 6f 75 74 69 6e 65 20 70 65 72 6d      routine perm
2240: 69 74 73 20 69 6e 63 6f 6d 70 6c 65 74 65 20 63  its incomplete c
2250: 6f 64 65 73 2c 20 73 6f 20 61 6e 6f 74 68 65 72  odes, so another
2260: 20 6c 6f 6f 70 20 61 66 74 65 72 20 74 68 69 73   loop after this
2270: 20 6f 6e 65 20 66 69 6c 6c 73 0a 20 20 20 20 20   one fills.     
2280: 20 20 69 6e 20 74 68 65 20 72 65 73 74 20 6f 66    in the rest of
2290: 20 74 68 65 20 64 65 63 6f 64 69 6e 67 20 74 61   the decoding ta
22a0: 62 6c 65 73 20 77 69 74 68 20 69 6e 76 61 6c 69  bles with invali
22b0: 64 20 63 6f 64 65 20 6d 61 72 6b 65 72 73 2e 0a  d code markers..
22c0: 20 20 20 20 20 2a 2f 0a 0a 20 20 20 20 2f 2a 20       */..    /* 
22d0: 73 65 74 20 75 70 20 66 6f 72 20 63 6f 64 65 20  set up for code 
22e0: 74 79 70 65 20 2a 2f 0a 20 20 20 20 73 77 69 74  type */.    swit
22f0: 63 68 20 28 74 79 70 65 29 20 7b 0a 20 20 20 20  ch (type) {.    
2300: 63 61 73 65 20 43 4f 44 45 53 3a 0a 20 20 20 20  case CODES:.    
2310: 20 20 20 20 62 61 73 65 20 3d 20 65 78 74 72 61      base = extra
2320: 20 3d 20 77 6f 72 6b 3b 20 20 20 20 2f 2a 20 64   = work;    /* d
2330: 75 6d 6d 79 20 76 61 6c 75 65 2d 2d 6e 6f 74 20  ummy value--not 
2340: 75 73 65 64 20 2a 2f 0a 20 20 20 20 20 20 20 20  used */.        
2350: 65 6e 64 20 3d 20 31 39 3b 0a 20 20 20 20 20 20  end = 19;.      
2360: 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 63 61 73    break;.    cas
2370: 65 20 4c 45 4e 53 3a 0a 20 20 20 20 20 20 20 20  e LENS:.        
2380: 62 61 73 65 20 3d 20 6c 62 61 73 65 3b 0a 20 20  base = lbase;.  
2390: 20 20 20 20 20 20 62 61 73 65 20 2d 3d 20 32 35        base -= 25
23a0: 37 3b 0a 20 20 20 20 20 20 20 20 65 78 74 72 61  7;.        extra
23b0: 20 3d 20 6c 65 78 74 3b 0a 20 20 20 20 20 20 20   = lext;.       
23c0: 20 65 78 74 72 61 20 2d 3d 20 32 35 37 3b 0a 20   extra -= 257;. 
23d0: 20 20 20 20 20 20 20 65 6e 64 20 3d 20 32 35 36         end = 256
23e0: 3b 0a 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b  ;.        break;
23f0: 0a 20 20 20 20 64 65 66 61 75 6c 74 3a 20 20 20  .    default:   
2400: 20 20 20 20 20 20 20 20 20 2f 2a 20 44 49 53 54           /* DIST
2410: 53 20 2a 2f 0a 20 20 20 20 20 20 20 20 62 61 73  S */.        bas
2420: 65 20 3d 20 64 62 61 73 65 3b 0a 20 20 20 20 20  e = dbase;.     
2430: 20 20 20 65 78 74 72 61 20 3d 20 64 65 78 74 3b     extra = dext;
2440: 0a 20 20 20 20 20 20 20 20 65 6e 64 20 3d 20 2d  .        end = -
2450: 31 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f 2a  1;.    }..    /*
2460: 20 69 6e 69 74 69 61 6c 69 7a 65 20 73 74 61 74   initialize stat
2470: 65 20 66 6f 72 20 6c 6f 6f 70 20 2a 2f 0a 20 20  e for loop */.  
2480: 20 20 68 75 66 66 20 3d 20 30 3b 20 20 20 20 20    huff = 0;     
2490: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
24a0: 20 73 74 61 72 74 69 6e 67 20 63 6f 64 65 20 2a   starting code *
24b0: 2f 0a 20 20 20 20 73 79 6d 20 3d 20 30 3b 20 20  /.    sym = 0;  
24c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
24d0: 20 20 2f 2a 20 73 74 61 72 74 69 6e 67 20 63 6f    /* starting co
24e0: 64 65 20 73 79 6d 62 6f 6c 20 2a 2f 0a 20 20 20  de symbol */.   
24f0: 20 6c 65 6e 20 3d 20 6d 69 6e 3b 20 20 20 20 20   len = min;     
2500: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
2510: 73 74 61 72 74 69 6e 67 20 63 6f 64 65 20 6c 65  starting code le
2520: 6e 67 74 68 20 2a 2f 0a 20 20 20 20 6e 65 78 74  ngth */.    next
2530: 20 3d 20 2a 74 61 62 6c 65 3b 20 20 20 20 20 20   = *table;      
2540: 20 20 20 20 20 20 20 20 2f 2a 20 63 75 72 72 65          /* curre
2550: 6e 74 20 74 61 62 6c 65 20 74 6f 20 66 69 6c 6c  nt table to fill
2560: 20 69 6e 20 2a 2f 0a 20 20 20 20 63 75 72 72 20   in */.    curr 
2570: 3d 20 72 6f 6f 74 3b 20 20 20 20 20 20 20 20 20  = root;         
2580: 20 20 20 20 20 20 20 2f 2a 20 63 75 72 72 65 6e         /* curren
2590: 74 20 74 61 62 6c 65 20 69 6e 64 65 78 20 62 69  t table index bi
25a0: 74 73 20 2a 2f 0a 20 20 20 20 64 72 6f 70 20 3d  ts */.    drop =
25b0: 20 30 3b 20 20 20 20 20 20 20 20 20 20 20 20 20   0;             
25c0: 20 20 20 20 20 20 2f 2a 20 63 75 72 72 65 6e 74        /* current
25d0: 20 62 69 74 73 20 74 6f 20 64 72 6f 70 20 66 72   bits to drop fr
25e0: 6f 6d 20 63 6f 64 65 20 66 6f 72 20 69 6e 64 65  om code for inde
25f0: 78 20 2a 2f 0a 20 20 20 20 6c 6f 77 20 3d 20 28  x */.    low = (
2600: 75 6e 73 69 67 6e 65 64 29 28 2d 31 29 3b 20 20  unsigned)(-1);  
2610: 20 20 20 20 20 2f 2a 20 74 72 69 67 67 65 72 20       /* trigger 
2620: 6e 65 77 20 73 75 62 2d 74 61 62 6c 65 20 77 68  new sub-table wh
2630: 65 6e 20 6c 65 6e 20 3e 20 72 6f 6f 74 20 2a 2f  en len > root */
2640: 0a 20 20 20 20 75 73 65 64 20 3d 20 31 55 20 3c  .    used = 1U <
2650: 3c 20 72 6f 6f 74 3b 20 20 20 20 20 20 20 20 20  < root;         
2660: 20 2f 2a 20 75 73 65 20 72 6f 6f 74 20 74 61 62   /* use root tab
2670: 6c 65 20 65 6e 74 72 69 65 73 20 2a 2f 0a 20 20  le entries */.  
2680: 20 20 6d 61 73 6b 20 3d 20 75 73 65 64 20 2d 20    mask = used - 
2690: 31 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  1;            /*
26a0: 20 6d 61 73 6b 20 66 6f 72 20 63 6f 6d 70 61 72   mask for compar
26b0: 69 6e 67 20 6c 6f 77 20 2a 2f 0a 0a 20 20 20 20  ing low */..    
26c0: 2f 2a 20 63 68 65 63 6b 20 61 76 61 69 6c 61 62  /* check availab
26d0: 6c 65 20 74 61 62 6c 65 20 73 70 61 63 65 20 2a  le table space *
26e0: 2f 0a 20 20 20 20 69 66 20 28 28 74 79 70 65 20  /.    if ((type 
26f0: 3d 3d 20 4c 45 4e 53 20 26 26 20 75 73 65 64 20  == LENS && used 
2700: 3e 20 45 4e 4f 55 47 48 5f 4c 45 4e 53 29 20 7c  > ENOUGH_LENS) |
2710: 7c 0a 20 20 20 20 20 20 20 20 28 74 79 70 65 20  |.        (type 
2720: 3d 3d 20 44 49 53 54 53 20 26 26 20 75 73 65 64  == DISTS && used
2730: 20 3e 20 45 4e 4f 55 47 48 5f 44 49 53 54 53 29   > ENOUGH_DISTS)
2740: 29 0a 20 20 20 20 20 20 20 20 72 65 74 75 72 6e  ).        return
2750: 20 31 3b 0a 0a 20 20 20 20 2f 2a 20 70 72 6f 63   1;..    /* proc
2760: 65 73 73 20 61 6c 6c 20 63 6f 64 65 73 20 61 6e  ess all codes an
2770: 64 20 6d 61 6b 65 20 74 61 62 6c 65 20 65 6e 74  d make table ent
2780: 72 69 65 73 20 2a 2f 0a 20 20 20 20 66 6f 72 20  ries */.    for 
2790: 28 3b 3b 29 20 7b 0a 20 20 20 20 20 20 20 20 2f  (;;) {.        /
27a0: 2a 20 63 72 65 61 74 65 20 74 61 62 6c 65 20 65  * create table e
27b0: 6e 74 72 79 20 2a 2f 0a 20 20 20 20 20 20 20 20  ntry */.        
27c0: 68 65 72 65 2e 62 69 74 73 20 3d 20 28 75 6e 73  here.bits = (uns
27d0: 69 67 6e 65 64 20 63 68 61 72 29 28 6c 65 6e 20  igned char)(len 
27e0: 2d 20 64 72 6f 70 29 3b 0a 20 20 20 20 20 20 20  - drop);.       
27f0: 20 69 66 20 28 28 69 6e 74 29 28 77 6f 72 6b 5b   if ((int)(work[
2800: 73 79 6d 5d 29 20 3c 20 65 6e 64 29 20 7b 0a 20  sym]) < end) {. 
2810: 20 20 20 20 20 20 20 20 20 20 20 68 65 72 65 2e             here.
2820: 6f 70 20 3d 20 28 75 6e 73 69 67 6e 65 64 20 63  op = (unsigned c
2830: 68 61 72 29 30 3b 0a 20 20 20 20 20 20 20 20 20  har)0;.         
2840: 20 20 20 68 65 72 65 2e 76 61 6c 20 3d 20 77 6f     here.val = wo
2850: 72 6b 5b 73 79 6d 5d 3b 0a 20 20 20 20 20 20 20  rk[sym];.       
2860: 20 7d 0a 20 20 20 20 20 20 20 20 65 6c 73 65 20   }.        else 
2870: 69 66 20 28 28 69 6e 74 29 28 77 6f 72 6b 5b 73  if ((int)(work[s
2880: 79 6d 5d 29 20 3e 20 65 6e 64 29 20 7b 0a 20 20  ym]) > end) {.  
2890: 20 20 20 20 20 20 20 20 20 20 68 65 72 65 2e 6f            here.o
28a0: 70 20 3d 20 28 75 6e 73 69 67 6e 65 64 20 63 68  p = (unsigned ch
28b0: 61 72 29 28 65 78 74 72 61 5b 77 6f 72 6b 5b 73  ar)(extra[work[s
28c0: 79 6d 5d 5d 29 3b 0a 20 20 20 20 20 20 20 20 20  ym]]);.         
28d0: 20 20 20 68 65 72 65 2e 76 61 6c 20 3d 20 62 61     here.val = ba
28e0: 73 65 5b 77 6f 72 6b 5b 73 79 6d 5d 5d 3b 0a 20  se[work[sym]];. 
28f0: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20         }.       
2900: 20 65 6c 73 65 20 7b 0a 20 20 20 20 20 20 20 20   else {.        
2910: 20 20 20 20 68 65 72 65 2e 6f 70 20 3d 20 28 75      here.op = (u
2920: 6e 73 69 67 6e 65 64 20 63 68 61 72 29 28 33 32  nsigned char)(32
2930: 20 2b 20 36 34 29 3b 20 20 20 20 20 20 20 20 20   + 64);         
2940: 2f 2a 20 65 6e 64 20 6f 66 20 62 6c 6f 63 6b 20  /* end of block 
2950: 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 20 20 68  */.            h
2960: 65 72 65 2e 76 61 6c 20 3d 20 30 3b 0a 20 20 20  ere.val = 0;.   
2970: 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 20 20 20       }..        
2980: 2f 2a 20 72 65 70 6c 69 63 61 74 65 20 66 6f 72  /* replicate for
2990: 20 74 68 6f 73 65 20 69 6e 64 69 63 65 73 20 77   those indices w
29a0: 69 74 68 20 6c 6f 77 20 6c 65 6e 20 62 69 74 73  ith low len bits
29b0: 20 65 71 75 61 6c 20 74 6f 20 68 75 66 66 20 2a   equal to huff *
29c0: 2f 0a 20 20 20 20 20 20 20 20 69 6e 63 72 20 3d  /.        incr =
29d0: 20 31 55 20 3c 3c 20 28 6c 65 6e 20 2d 20 64 72   1U << (len - dr
29e0: 6f 70 29 3b 0a 20 20 20 20 20 20 20 20 66 69 6c  op);.        fil
29f0: 6c 20 3d 20 31 55 20 3c 3c 20 63 75 72 72 3b 0a  l = 1U << curr;.
2a00: 20 20 20 20 20 20 20 20 6d 69 6e 20 3d 20 66 69          min = fi
2a10: 6c 6c 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  ll;             
2a20: 20 20 20 20 2f 2a 20 73 61 76 65 20 6f 66 66 73      /* save offs
2a30: 65 74 20 74 6f 20 6e 65 78 74 20 74 61 62 6c 65  et to next table
2a40: 20 2a 2f 0a 20 20 20 20 20 20 20 20 64 6f 20 7b   */.        do {
2a50: 0a 20 20 20 20 20 20 20 20 20 20 20 20 66 69 6c  .            fil
2a60: 6c 20 2d 3d 20 69 6e 63 72 3b 0a 20 20 20 20 20  l -= incr;.     
2a70: 20 20 20 20 20 20 20 6e 65 78 74 5b 28 68 75 66         next[(huf
2a80: 66 20 3e 3e 20 64 72 6f 70 29 20 2b 20 66 69 6c  f >> drop) + fil
2a90: 6c 5d 20 3d 20 68 65 72 65 3b 0a 20 20 20 20 20  l] = here;.     
2aa0: 20 20 20 7d 20 77 68 69 6c 65 20 28 66 69 6c 6c     } while (fill
2ab0: 20 21 3d 20 30 29 3b 0a 0a 20 20 20 20 20 20 20   != 0);..       
2ac0: 20 2f 2a 20 62 61 63 6b 77 61 72 64 73 20 69 6e   /* backwards in
2ad0: 63 72 65 6d 65 6e 74 20 74 68 65 20 6c 65 6e 2d  crement the len-
2ae0: 62 69 74 20 63 6f 64 65 20 68 75 66 66 20 2a 2f  bit code huff */
2af0: 0a 20 20 20 20 20 20 20 20 69 6e 63 72 20 3d 20  .        incr = 
2b00: 31 55 20 3c 3c 20 28 6c 65 6e 20 2d 20 31 29 3b  1U << (len - 1);
2b10: 0a 20 20 20 20 20 20 20 20 77 68 69 6c 65 20 28  .        while (
2b20: 68 75 66 66 20 26 20 69 6e 63 72 29 0a 20 20 20  huff & incr).   
2b30: 20 20 20 20 20 20 20 20 20 69 6e 63 72 20 3e 3e           incr >>
2b40: 3d 20 31 3b 0a 20 20 20 20 20 20 20 20 69 66 20  = 1;.        if 
2b50: 28 69 6e 63 72 20 21 3d 20 30 29 20 7b 0a 20 20  (incr != 0) {.  
2b60: 20 20 20 20 20 20 20 20 20 20 68 75 66 66 20 26            huff &
2b70: 3d 20 69 6e 63 72 20 2d 20 31 3b 0a 20 20 20 20  = incr - 1;.    
2b80: 20 20 20 20 20 20 20 20 68 75 66 66 20 2b 3d 20          huff += 
2b90: 69 6e 63 72 3b 0a 20 20 20 20 20 20 20 20 7d 0a  incr;.        }.
2ba0: 20 20 20 20 20 20 20 20 65 6c 73 65 0a 20 20 20          else.   
2bb0: 20 20 20 20 20 20 20 20 20 68 75 66 66 20 3d 20           huff = 
2bc0: 30 3b 0a 0a 20 20 20 20 20 20 20 20 2f 2a 20 67  0;..        /* g
2bd0: 6f 20 74 6f 20 6e 65 78 74 20 73 79 6d 62 6f 6c  o to next symbol
2be0: 2c 20 75 70 64 61 74 65 20 63 6f 75 6e 74 2c 20  , update count, 
2bf0: 6c 65 6e 20 2a 2f 0a 20 20 20 20 20 20 20 20 73  len */.        s
2c00: 79 6d 2b 2b 3b 0a 20 20 20 20 20 20 20 20 69 66  ym++;.        if
2c10: 20 28 2d 2d 28 63 6f 75 6e 74 5b 6c 65 6e 5d 29   (--(count[len])
2c20: 20 3d 3d 20 30 29 20 7b 0a 20 20 20 20 20 20 20   == 0) {.       
2c30: 20 20 20 20 20 69 66 20 28 6c 65 6e 20 3d 3d 20       if (len == 
2c40: 6d 61 78 29 20 62 72 65 61 6b 3b 0a 20 20 20 20  max) break;.    
2c50: 20 20 20 20 20 20 20 20 6c 65 6e 20 3d 20 6c 65          len = le
2c60: 6e 73 5b 77 6f 72 6b 5b 73 79 6d 5d 5d 3b 0a 20  ns[work[sym]];. 
2c70: 20 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 20         }..      
2c80: 20 20 2f 2a 20 63 72 65 61 74 65 20 6e 65 77 20    /* create new 
2c90: 73 75 62 2d 74 61 62 6c 65 20 69 66 20 6e 65 65  sub-table if nee
2ca0: 64 65 64 20 2a 2f 0a 20 20 20 20 20 20 20 20 69  ded */.        i
2cb0: 66 20 28 6c 65 6e 20 3e 20 72 6f 6f 74 20 26 26  f (len > root &&
2cc0: 20 28 68 75 66 66 20 26 20 6d 61 73 6b 29 20 21   (huff & mask) !
2cd0: 3d 20 6c 6f 77 29 20 7b 0a 20 20 20 20 20 20 20  = low) {.       
2ce0: 20 20 20 20 20 2f 2a 20 69 66 20 66 69 72 73 74       /* if first
2cf0: 20 74 69 6d 65 2c 20 74 72 61 6e 73 69 74 69 6f   time, transitio
2d00: 6e 20 74 6f 20 73 75 62 2d 74 61 62 6c 65 73 20  n to sub-tables 
2d10: 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 20 20 69  */.            i
2d20: 66 20 28 64 72 6f 70 20 3d 3d 20 30 29 0a 20 20  f (drop == 0).  
2d30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 64 72                dr
2d40: 6f 70 20 3d 20 72 6f 6f 74 3b 0a 0a 20 20 20 20  op = root;..    
2d50: 20 20 20 20 20 20 20 20 2f 2a 20 69 6e 63 72 65          /* incre
2d60: 6d 65 6e 74 20 70 61 73 74 20 6c 61 73 74 20 74  ment past last t
2d70: 61 62 6c 65 20 2a 2f 0a 20 20 20 20 20 20 20 20  able */.        
2d80: 20 20 20 20 6e 65 78 74 20 2b 3d 20 6d 69 6e 3b      next += min;
2d90: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 68              /* h
2da0: 65 72 65 20 6d 69 6e 20 69 73 20 31 20 3c 3c 20  ere min is 1 << 
2db0: 63 75 72 72 20 2a 2f 0a 0a 20 20 20 20 20 20 20  curr */..       
2dc0: 20 20 20 20 20 2f 2a 20 64 65 74 65 72 6d 69 6e       /* determin
2dd0: 65 20 6c 65 6e 67 74 68 20 6f 66 20 6e 65 78 74  e length of next
2de0: 20 74 61 62 6c 65 20 2a 2f 0a 20 20 20 20 20 20   table */.      
2df0: 20 20 20 20 20 20 63 75 72 72 20 3d 20 6c 65 6e        curr = len
2e00: 20 2d 20 64 72 6f 70 3b 0a 20 20 20 20 20 20 20   - drop;.       
2e10: 20 20 20 20 20 6c 65 66 74 20 3d 20 28 69 6e 74       left = (int
2e20: 29 28 31 20 3c 3c 20 63 75 72 72 29 3b 0a 20 20  )(1 << curr);.  
2e30: 20 20 20 20 20 20 20 20 20 20 77 68 69 6c 65 20            while 
2e40: 28 63 75 72 72 20 2b 20 64 72 6f 70 20 3c 20 6d  (curr + drop < m
2e50: 61 78 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20  ax) {.          
2e60: 20 20 20 20 20 20 6c 65 66 74 20 2d 3d 20 63 6f        left -= co
2e70: 75 6e 74 5b 63 75 72 72 20 2b 20 64 72 6f 70 5d  unt[curr + drop]
2e80: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;.              
2e90: 20 20 69 66 20 28 6c 65 66 74 20 3c 3d 20 30 29    if (left <= 0)
2ea0: 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 20 20   break;.        
2eb0: 20 20 20 20 20 20 20 20 63 75 72 72 2b 2b 3b 0a          curr++;.
2ec0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2ed0: 6c 65 66 74 20 3c 3c 3d 20 31 3b 0a 20 20 20 20  left <<= 1;.    
2ee0: 20 20 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 20          }..     
2ef0: 20 20 20 20 20 20 20 2f 2a 20 63 68 65 63 6b 20         /* check 
2f00: 66 6f 72 20 65 6e 6f 75 67 68 20 73 70 61 63 65  for enough space
2f10: 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 20 20   */.            
2f20: 75 73 65 64 20 2b 3d 20 31 55 20 3c 3c 20 63 75  used += 1U << cu
2f30: 72 72 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20  rr;.            
2f40: 69 66 20 28 28 74 79 70 65 20 3d 3d 20 4c 45 4e  if ((type == LEN
2f50: 53 20 26 26 20 75 73 65 64 20 3e 20 45 4e 4f 55  S && used > ENOU
2f60: 47 48 5f 4c 45 4e 53 29 20 7c 7c 0a 20 20 20 20  GH_LENS) ||.    
2f70: 20 20 20 20 20 20 20 20 20 20 20 20 28 74 79 70              (typ
2f80: 65 20 3d 3d 20 44 49 53 54 53 20 26 26 20 75 73  e == DISTS && us
2f90: 65 64 20 3e 20 45 4e 4f 55 47 48 5f 44 49 53 54  ed > ENOUGH_DIST
2fa0: 53 29 29 0a 20 20 20 20 20 20 20 20 20 20 20 20  S)).            
2fb0: 20 20 20 20 72 65 74 75 72 6e 20 31 3b 0a 0a 20      return 1;.. 
2fc0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 70 6f             /* po
2fd0: 69 6e 74 20 65 6e 74 72 79 20 69 6e 20 72 6f 6f  int entry in roo
2fe0: 74 20 74 61 62 6c 65 20 74 6f 20 73 75 62 2d 74  t table to sub-t
2ff0: 61 62 6c 65 20 2a 2f 0a 20 20 20 20 20 20 20 20  able */.        
3000: 20 20 20 20 6c 6f 77 20 3d 20 68 75 66 66 20 26      low = huff &
3010: 20 6d 61 73 6b 3b 0a 20 20 20 20 20 20 20 20 20   mask;.         
3020: 20 20 20 28 2a 74 61 62 6c 65 29 5b 6c 6f 77 5d     (*table)[low]
3030: 2e 6f 70 20 3d 20 28 75 6e 73 69 67 6e 65 64 20  .op = (unsigned 
3040: 63 68 61 72 29 63 75 72 72 3b 0a 20 20 20 20 20  char)curr;.     
3050: 20 20 20 20 20 20 20 28 2a 74 61 62 6c 65 29 5b         (*table)[
3060: 6c 6f 77 5d 2e 62 69 74 73 20 3d 20 28 75 6e 73  low].bits = (uns
3070: 69 67 6e 65 64 20 63 68 61 72 29 72 6f 6f 74 3b  igned char)root;
3080: 0a 20 20 20 20 20 20 20 20 20 20 20 20 28 2a 74  .            (*t
3090: 61 62 6c 65 29 5b 6c 6f 77 5d 2e 76 61 6c 20 3d  able)[low].val =
30a0: 20 28 75 6e 73 69 67 6e 65 64 20 73 68 6f 72 74   (unsigned short
30b0: 29 28 6e 65 78 74 20 2d 20 2a 74 61 62 6c 65 29  )(next - *table)
30c0: 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20  ;.        }.    
30d0: 7d 0a 0a 20 20 20 20 2f 2a 20 66 69 6c 6c 20 69  }..    /* fill i
30e0: 6e 20 72 65 6d 61 69 6e 69 6e 67 20 74 61 62 6c  n remaining tabl
30f0: 65 20 65 6e 74 72 79 20 69 66 20 63 6f 64 65 20  e entry if code 
3100: 69 73 20 69 6e 63 6f 6d 70 6c 65 74 65 20 28 67  is incomplete (g
3110: 75 61 72 61 6e 74 65 65 64 20 74 6f 20 68 61 76  uaranteed to hav
3120: 65 0a 20 20 20 20 20 20 20 61 74 20 6d 6f 73 74  e.       at most
3130: 20 6f 6e 65 20 72 65 6d 61 69 6e 69 6e 67 20 65   one remaining e
3140: 6e 74 72 79 2c 20 73 69 6e 63 65 20 69 66 20 74  ntry, since if t
3150: 68 65 20 63 6f 64 65 20 69 73 20 69 6e 63 6f 6d  he code is incom
3160: 70 6c 65 74 65 2c 20 74 68 65 0a 20 20 20 20 20  plete, the.     
3170: 20 20 6d 61 78 69 6d 75 6d 20 63 6f 64 65 20 6c    maximum code l
3180: 65 6e 67 74 68 20 74 68 61 74 20 77 61 73 20 61  ength that was a
3190: 6c 6c 6f 77 65 64 20 74 6f 20 67 65 74 20 74 68  llowed to get th
31a0: 69 73 20 66 61 72 20 69 73 20 6f 6e 65 20 62 69  is far is one bi
31b0: 74 29 20 2a 2f 0a 20 20 20 20 69 66 20 28 68 75  t) */.    if (hu
31c0: 66 66 20 21 3d 20 30 29 20 7b 0a 20 20 20 20 20  ff != 0) {.     
31d0: 20 20 20 68 65 72 65 2e 6f 70 20 3d 20 28 75 6e     here.op = (un
31e0: 73 69 67 6e 65 64 20 63 68 61 72 29 36 34 3b 20  signed char)64; 
31f0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 69 6e             /* in
3200: 76 61 6c 69 64 20 63 6f 64 65 20 6d 61 72 6b 65  valid code marke
3210: 72 20 2a 2f 0a 20 20 20 20 20 20 20 20 68 65 72  r */.        her
3220: 65 2e 62 69 74 73 20 3d 20 28 75 6e 73 69 67 6e  e.bits = (unsign
3230: 65 64 20 63 68 61 72 29 28 6c 65 6e 20 2d 20 64  ed char)(len - d
3240: 72 6f 70 29 3b 0a 20 20 20 20 20 20 20 20 68 65  rop);.        he
3250: 72 65 2e 76 61 6c 20 3d 20 28 75 6e 73 69 67 6e  re.val = (unsign
3260: 65 64 20 73 68 6f 72 74 29 30 3b 0a 20 20 20 20  ed short)0;.    
3270: 20 20 20 20 6e 65 78 74 5b 68 75 66 66 5d 20 3d      next[huff] =
3280: 20 68 65 72 65 3b 0a 20 20 20 20 7d 0a 0a 20 20   here;.    }..  
3290: 20 20 2f 2a 20 73 65 74 20 72 65 74 75 72 6e 20    /* set return 
32a0: 70 61 72 61 6d 65 74 65 72 73 20 2a 2f 0a 20 20  parameters */.  
32b0: 20 20 2a 74 61 62 6c 65 20 2b 3d 20 75 73 65 64    *table += used
32c0: 3b 0a 20 20 20 20 2a 62 69 74 73 20 3d 20 72 6f  ;.    *bits = ro
32d0: 6f 74 3b 0a 20 20 20 20 72 65 74 75 72 6e 20 30  ot;.    return 0
32e0: 3b 0a 7d 0a                                      ;.}.