misc/libfreetype/src/gzip/inftrees.c
author sheepluva
Fri, 21 Oct 2011 19:17:08 +0200
changeset 6171 8627698134b6
parent 5172 88f2e05288ba
permissions -rw-r--r--
fix layout of net page
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
5172
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     1
/* inftrees.c -- generate Huffman trees for efficient decoding
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     2
 * Copyright (C) 1995-2002 Mark Adler
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     3
 * For conditions of distribution and use, see copyright notice in zlib.h
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     4
 */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     5
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     6
#include "zutil.h"
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     7
#include "inftrees.h"
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     8
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
     9
#if !defined(BUILDFIXED) && !defined(STDC)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    10
#  define BUILDFIXED   /* non ANSI compilers may not accept inffixed.h */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    11
#endif
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    12
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    13
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    14
#if 0
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    15
local const char inflate_copyright[] =
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    16
   " inflate 1.1.4 Copyright 1995-2002 Mark Adler ";
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    17
#endif
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    18
/*
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    19
  If you use the zlib library in a product, an acknowledgment is welcome
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    20
  in the documentation of your product. If for some reason you cannot
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    21
  include such an acknowledgment, I would appreciate that you keep this
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    22
  copyright string in the executable of your product.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    23
 */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    24
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    25
/* simplify the use of the inflate_huft type with some defines */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    26
#define exop word.what.Exop
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    27
#define bits word.what.Bits
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    28
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    29
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    30
local int huft_build OF((
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    31
    uIntf *,            /* code lengths in bits */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    32
    uInt,               /* number of codes */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    33
    uInt,               /* number of "simple" codes */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    34
    const uIntf *,      /* list of base values for non-simple codes */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    35
    const uIntf *,      /* list of extra bits for non-simple codes */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    36
    inflate_huft * FAR*,/* result: starting table */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    37
    uIntf *,            /* maximum lookup bits (returns actual) */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    38
    inflate_huft *,     /* space for trees */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    39
    uInt *,             /* hufts used in space */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    40
    uIntf * ));         /* space for values */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    41
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    42
/* Tables for deflate from PKZIP's appnote.txt. */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    43
local const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    44
        3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    45
        35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    46
        /* see note #13 above about 258 */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    47
local const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    48
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    49
        3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112}; /* 112==invalid */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    50
local const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    51
        1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    52
        257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    53
        8193, 12289, 16385, 24577};
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    54
local const uInt cpdext[30] = { /* Extra bits for distance codes */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    55
        0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    56
        7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    57
        12, 12, 13, 13};
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    58
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    59
/*
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    60
   Huffman code decoding is performed using a multi-level table lookup.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    61
   The fastest way to decode is to simply build a lookup table whose
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    62
   size is determined by the longest code.  However, the time it takes
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    63
   to build this table can also be a factor if the data being decoded
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    64
   is not very long.  The most common codes are necessarily the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    65
   shortest codes, so those codes dominate the decoding time, and hence
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    66
   the speed.  The idea is you can have a shorter table that decodes the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    67
   shorter, more probable codes, and then point to subsidiary tables for
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    68
   the longer codes.  The time it costs to decode the longer codes is
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    69
   then traded against the time it takes to make longer tables.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    70
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    71
   This results of this trade are in the variables lbits and dbits
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    72
   below.  lbits is the number of bits the first level table for literal/
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    73
   length codes can decode in one step, and dbits is the same thing for
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    74
   the distance codes.  Subsequent tables are also less than or equal to
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    75
   those sizes.  These values may be adjusted either when all of the
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    76
   codes are shorter than that, in which case the longest code length in
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    77
   bits is used, or when the shortest code is *longer* than the requested
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    78
   table size, in which case the length of the shortest code in bits is
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    79
   used.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    80
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    81
   There are two different values for the two tables, since they code a
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    82
   different number of possibilities each.  The literal/length table
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    83
   codes 286 possible values, or in a flat code, a little over eight
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    84
   bits.  The distance table codes 30 possible values, or a little less
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    85
   than five bits, flat.  The optimum values for speed end up being
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    86
   about one bit more than those, so lbits is 8+1 and dbits is 5+1.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    87
   The optimum values may differ though from machine to machine, and
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    88
   possibly even between compilers.  Your mileage may vary.
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    89
 */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    90
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    91
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    92
/* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    93
#define BMAX 15         /* maximum bit length of any code */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    94
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    95
local int huft_build( /* b, n, s, d, e, t, m, hp, hn, v) */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    96
uIntf *b,               /* code lengths in bits (all assumed <= BMAX) */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    97
uInt n,                 /* number of codes (assumed <= 288) */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    98
uInt s,                 /* number of simple-valued codes (0..s-1) */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
    99
const uIntf *d,         /* list of base values for non-simple codes */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   100
const uIntf *e,         /* list of extra bits for non-simple codes */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   101
inflate_huft * FAR *t,  /* result: starting table */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   102
uIntf *m,               /* maximum lookup bits, returns actual */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   103
inflate_huft *hp,       /* space for trees */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   104
uInt *hn,               /* hufts used in space */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   105
uIntf *v                /* working area: values in order of bit length */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   106
/* Given a list of code lengths and a maximum table size, make a set of
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   107
   tables to decode that set of codes.  Return Z_OK on success, Z_BUF_ERROR
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   108
   if the given code set is incomplete (the tables are still built in this
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   109
   case), or Z_DATA_ERROR if the input is invalid. */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   110
)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   111
{
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   112
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   113
  uInt a;                       /* counter for codes of length k */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   114
  uInt c[BMAX+1];               /* bit length count table */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   115
  uInt f;                       /* i repeats in table every f entries */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   116
  int g;                        /* maximum code length */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   117
  int h;                        /* table level */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   118
  register uInt i;              /* counter, current code */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   119
  register uInt j;              /* counter */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   120
  register int k;               /* number of bits in current code */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   121
  int l;                        /* bits per table (returned in m) */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   122
  uInt mask;                    /* (1 << w) - 1, to avoid cc -O bug on HP */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   123
  register uIntf *p;            /* pointer into c[], b[], or v[] */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   124
  inflate_huft *q;              /* points to current table */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   125
  struct inflate_huft_s r;      /* table entry for structure assignment */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   126
  inflate_huft *u[BMAX];        /* table stack */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   127
  register int w;               /* bits before this table == (l * h) */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   128
  uInt x[BMAX+1];               /* bit offsets, then code stack */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   129
  uIntf *xp;                    /* pointer into x */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   130
  int y;                        /* number of dummy codes added */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   131
  uInt z;                       /* number of entries in current table */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   132
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   133
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   134
  /* Make compiler happy */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   135
  r.base = 0;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   136
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   137
  /* Generate counts for each bit length */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   138
  p = c;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   139
#define C0 *p++ = 0;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   140
#define C2 C0 C0 C0 C0
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   141
#define C4 C2 C2 C2 C2
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   142
  C4                            /* clear c[]--assume BMAX+1 is 16 */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   143
  p = b;  i = n;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   144
  do {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   145
    c[*p++]++;                  /* assume all entries <= BMAX */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   146
  } while (--i);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   147
  if (c[0] == n)                /* null input--all zero length codes */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   148
  {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   149
    *t = (inflate_huft *)Z_NULL;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   150
    *m = 0;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   151
    return Z_OK;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   152
  }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   153
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   154
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   155
  /* Find minimum and maximum length, bound *m by those */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   156
  l = *m;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   157
  for (j = 1; j <= BMAX; j++)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   158
    if (c[j])
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   159
      break;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   160
  k = j;                        /* minimum code length */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   161
  if ((uInt)l < j)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   162
    l = j;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   163
  for (i = BMAX; i; i--)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   164
    if (c[i])
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   165
      break;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   166
  g = i;                        /* maximum code length */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   167
  if ((uInt)l > i)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   168
    l = i;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   169
  *m = l;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   170
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   171
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   172
  /* Adjust last length count to fill out codes, if needed */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   173
  for (y = 1 << j; j < i; j++, y <<= 1)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   174
    if ((y -= c[j]) < 0)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   175
      return Z_DATA_ERROR;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   176
  if ((y -= c[i]) < 0)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   177
    return Z_DATA_ERROR;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   178
  c[i] += y;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   179
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   180
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   181
  /* Generate starting offsets into the value table for each length */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   182
  x[1] = j = 0;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   183
  p = c + 1;  xp = x + 2;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   184
  while (--i) {                 /* note that i == g from above */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   185
    *xp++ = (j += *p++);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   186
  }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   187
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   188
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   189
  /* Make a table of values in order of bit lengths */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   190
  p = b;  i = 0;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   191
  do {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   192
    if ((j = *p++) != 0)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   193
      v[x[j]++] = i;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   194
  } while (++i < n);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   195
  n = x[g];                     /* set n to length of v */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   196
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   197
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   198
  /* Generate the Huffman codes and for each, make the table entries */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   199
  x[0] = i = 0;                 /* first Huffman code is zero */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   200
  p = v;                        /* grab values in bit order */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   201
  h = -1;                       /* no tables yet--level -1 */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   202
  w = -l;                       /* bits decoded == (l * h) */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   203
  u[0] = (inflate_huft *)Z_NULL;        /* just to keep compilers happy */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   204
  q = (inflate_huft *)Z_NULL;   /* ditto */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   205
  z = 0;                        /* ditto */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   206
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   207
  /* go through the bit lengths (k already is bits in shortest code) */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   208
  for (; k <= g; k++)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   209
  {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   210
    a = c[k];
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   211
    while (a--)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   212
    {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   213
      /* here i is the Huffman code of length k bits for value *p */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   214
      /* make tables up to required level */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   215
      while (k > w + l)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   216
      {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   217
        h++;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   218
        w += l;                 /* previous table always l bits */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   219
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   220
        /* compute minimum size table less than or equal to l bits */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   221
        z = g - w;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   222
        z = z > (uInt)l ? (uInt)l : z;        /* table size upper limit */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   223
        if ((f = 1 << (j = k - w)) > a + 1)     /* try a k-w bit table */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   224
        {                       /* too few codes for k-w bit table */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   225
          f -= a + 1;           /* deduct codes from patterns left */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   226
          xp = c + k;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   227
          if (j < z)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   228
            while (++j < z)     /* try smaller tables up to z bits */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   229
            {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   230
              if ((f <<= 1) <= *++xp)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   231
                break;          /* enough codes to use up j bits */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   232
              f -= *xp;         /* else deduct codes from patterns */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   233
            }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   234
        }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   235
        z = 1 << j;             /* table entries for j-bit table */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   236
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   237
        /* allocate new table */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   238
        if (*hn + z > MANY)     /* (note: doesn't matter for fixed) */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   239
          return Z_DATA_ERROR;  /* overflow of MANY */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   240
        u[h] = q = hp + *hn;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   241
        *hn += z;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   242
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   243
        /* connect to last table, if there is one */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   244
        if (h)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   245
        {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   246
          x[h] = i;             /* save pattern for backing up */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   247
          r.bits = (Byte)l;     /* bits to dump before this table */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   248
          r.exop = (Byte)j;     /* bits in this table */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   249
          j = i >> (w - l);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   250
          r.base = (uInt)(q - u[h-1] - j);   /* offset to this table */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   251
          u[h-1][j] = r;        /* connect to last table */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   252
        }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   253
        else
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   254
          *t = q;               /* first table is returned result */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   255
      }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   256
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   257
      /* set up table entry in r */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   258
      r.bits = (Byte)(k - w);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   259
      if (p >= v + n)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   260
        r.exop = 128 + 64;      /* out of values--invalid code */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   261
      else if (*p < s)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   262
      {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   263
        r.exop = (Byte)(*p < 256 ? 0 : 32 + 64);     /* 256 is end-of-block */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   264
        r.base = *p++;          /* simple code is just the value */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   265
      }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   266
      else
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   267
      {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   268
        r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   269
        r.base = d[*p++ - s];
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   270
      }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   271
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   272
      /* fill code-like entries with r */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   273
      f = 1 << (k - w);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   274
      for (j = i >> w; j < z; j += f)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   275
        q[j] = r;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   276
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   277
      /* backwards increment the k-bit code i */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   278
      for (j = 1 << (k - 1); i & j; j >>= 1)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   279
        i ^= j;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   280
      i ^= j;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   281
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   282
      /* backup over finished tables */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   283
      mask = (1 << w) - 1;      /* needed on HP, cc -O bug */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   284
      while ((i & mask) != x[h])
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   285
      {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   286
        h--;                    /* don't need to update q */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   287
        w -= l;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   288
        mask = (1 << w) - 1;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   289
      }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   290
    }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   291
  }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   292
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   293
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   294
  /* Return Z_BUF_ERROR if we were given an incomplete table */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   295
  return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   296
}
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   297
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   298
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   299
local int inflate_trees_bits( /* c, bb, tb, hp, z) */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   300
uIntf *c,               /* 19 code lengths */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   301
uIntf *bb,              /* bits tree desired/actual depth */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   302
inflate_huft * FAR *tb, /* bits tree result */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   303
inflate_huft *hp,       /* space for trees */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   304
z_streamp z             /* for messages */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   305
)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   306
{
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   307
  int r;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   308
  uInt hn = 0;          /* hufts used in space */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   309
  uIntf *v;             /* work area for huft_build */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   310
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   311
  if ((v = (uIntf*)ZALLOC(z, 19, sizeof(uInt))) == Z_NULL)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   312
    return Z_MEM_ERROR;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   313
  r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   314
                 tb, bb, hp, &hn, v);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   315
  if (r == Z_DATA_ERROR)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   316
    z->msg = (char*)"oversubscribed dynamic bit lengths tree";
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   317
  else if (r == Z_BUF_ERROR || *bb == 0)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   318
  {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   319
    z->msg = (char*)"incomplete dynamic bit lengths tree";
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   320
    r = Z_DATA_ERROR;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   321
  }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   322
  ZFREE(z, v);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   323
  return r;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   324
}
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   325
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   326
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   327
local int inflate_trees_dynamic( /* nl, nd, c, bl, bd, tl, td, hp, z) */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   328
uInt nl,                /* number of literal/length codes */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   329
uInt nd,                /* number of distance codes */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   330
uIntf *c,               /* that many (total) code lengths */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   331
uIntf *bl,              /* literal desired/actual bit depth */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   332
uIntf *bd,              /* distance desired/actual bit depth */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   333
inflate_huft * FAR *tl, /* literal/length tree result */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   334
inflate_huft * FAR *td, /* distance tree result */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   335
inflate_huft *hp,       /* space for trees */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   336
z_streamp z             /* for messages */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   337
)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   338
{
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   339
  int r;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   340
  uInt hn = 0;          /* hufts used in space */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   341
  uIntf *v;             /* work area for huft_build */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   342
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   343
  /* allocate work area */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   344
  if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   345
    return Z_MEM_ERROR;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   346
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   347
  /* build literal/length tree */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   348
  r = huft_build(c, nl, 257, cplens, cplext, tl, bl, hp, &hn, v);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   349
  if (r != Z_OK || *bl == 0)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   350
  {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   351
    if (r == Z_DATA_ERROR)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   352
      z->msg = (char*)"oversubscribed literal/length tree";
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   353
    else if (r != Z_MEM_ERROR)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   354
    {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   355
      z->msg = (char*)"incomplete literal/length tree";
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   356
      r = Z_DATA_ERROR;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   357
    }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   358
    ZFREE(z, v);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   359
    return r;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   360
  }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   361
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   362
  /* build distance tree */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   363
  r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, hp, &hn, v);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   364
  if (r != Z_OK || (*bd == 0 && nl > 257))
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   365
  {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   366
    if (r == Z_DATA_ERROR)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   367
      z->msg = (char*)"oversubscribed distance tree";
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   368
    else if (r == Z_BUF_ERROR) {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   369
#if 0
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   370
    {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   371
#endif
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   372
#ifdef PKZIP_BUG_WORKAROUND
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   373
      r = Z_OK;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   374
    }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   375
#else
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   376
      z->msg = (char*)"incomplete distance tree";
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   377
      r = Z_DATA_ERROR;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   378
    }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   379
    else if (r != Z_MEM_ERROR)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   380
    {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   381
      z->msg = (char*)"empty distance tree with lengths";
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   382
      r = Z_DATA_ERROR;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   383
    }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   384
    ZFREE(z, v);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   385
    return r;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   386
#endif
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   387
  }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   388
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   389
  /* done */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   390
  ZFREE(z, v);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   391
  return Z_OK;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   392
}
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   393
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   394
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   395
/* build fixed tables only once--keep them here */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   396
#ifdef BUILDFIXED
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   397
local int fixed_built = 0;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   398
#define FIXEDH 544      /* number of hufts used by fixed tables */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   399
local inflate_huft fixed_mem[FIXEDH];
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   400
local uInt fixed_bl;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   401
local uInt fixed_bd;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   402
local inflate_huft *fixed_tl;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   403
local inflate_huft *fixed_td;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   404
#else
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   405
#include "inffixed.h"
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   406
#endif
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   407
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   408
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   409
local int inflate_trees_fixed( /* bl, bd, tl, td, z) */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   410
uIntf *bl,                      /* literal desired/actual bit depth */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   411
uIntf *bd,                      /* distance desired/actual bit depth */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   412
const inflate_huft * FAR *tl,   /* literal/length tree result */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   413
const inflate_huft * FAR *td,   /* distance tree result */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   414
z_streamp z                     /* for memory allocation */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   415
)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   416
{
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   417
#ifdef BUILDFIXED
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   418
  /* build fixed tables if not already */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   419
  if (!fixed_built)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   420
  {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   421
    int k;              /* temporary variable */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   422
    uInt f = 0;         /* number of hufts used in fixed_mem */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   423
    uIntf *c;           /* length list for huft_build */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   424
    uIntf *v;           /* work area for huft_build */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   425
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   426
    /* allocate memory */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   427
    if ((c = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   428
      return Z_MEM_ERROR;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   429
    if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   430
    {
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   431
      ZFREE(z, c);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   432
      return Z_MEM_ERROR;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   433
    }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   434
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   435
    /* literal table */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   436
    for (k = 0; k < 144; k++)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   437
      c[k] = 8;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   438
    for (; k < 256; k++)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   439
      c[k] = 9;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   440
    for (; k < 280; k++)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   441
      c[k] = 7;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   442
    for (; k < 288; k++)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   443
      c[k] = 8;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   444
    fixed_bl = 9;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   445
    huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   446
               fixed_mem, &f, v);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   447
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   448
    /* distance table */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   449
    for (k = 0; k < 30; k++)
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   450
      c[k] = 5;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   451
    fixed_bd = 5;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   452
    huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd,
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   453
               fixed_mem, &f, v);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   454
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   455
    /* done */
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   456
    ZFREE(z, v);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   457
    ZFREE(z, c);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   458
    fixed_built = 1;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   459
  }
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   460
#else
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   461
  FT_UNUSED(z);
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   462
#endif
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   463
  *bl = fixed_bl;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   464
  *bd = fixed_bd;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   465
  *tl = fixed_tl;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   466
  *td = fixed_td;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   467
  return Z_OK;
88f2e05288ba aaand let's add freetype as well while we are at it
koda
parents:
diff changeset
   468
}