From 6759211ad8a5006689216a86c3267bb503bfccc1 Mon Sep 17 00:00:00 2001 From: Mark Adler Date: Fri, 9 Sep 2011 23:18:57 -0700 Subject: zlib 1.0.8 --- trees.c | 112 ++++++++++++++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 96 insertions(+), 16 deletions(-) (limited to 'trees.c') diff --git a/trees.c b/trees.c index fe86c77..e2c230f 100644 --- a/trees.c +++ b/trees.c @@ -31,6 +31,8 @@ /* @(#) $Id$ */ +/* #define GEN_TREES_H */ + #include "deflate.h" #ifdef DEBUG @@ -80,6 +82,11 @@ local const uch bl_order[BL_CODES] * Local data. These are initialized only once. */ +#define DIST_CODE_LEN 512 /* see definition of array dist_code below */ + +#if defined(GEN_TREES_H) || !defined(STDC) +/* non ANSI compilers may not accept trees.h */ + local ct_data static_ltree[L_CODES+2]; /* The static literal tree. Since the bit lengths are imposed, there is no * need for the L_CODES extra codes used during heap construction. However @@ -92,8 +99,8 @@ local ct_data static_dtree[D_CODES]; * 5 bits.) */ -local uch dist_code[512]; -/* distance codes. The first 256 values correspond to the distances +local uch dist_code[DIST_CODE_LEN]; +/* Distance codes. The first 256 values correspond to the distances * 3 .. 258, the last 256 values correspond to the top 8 bits of * the 15 bit distances. */ @@ -107,8 +114,12 @@ local int base_length[LENGTH_CODES]; local int base_dist[D_CODES]; /* First normalized distance for each code (0 = distance of 1) */ +#else +# include "trees.h" +#endif /* GEN_TREES_H */ + struct static_tree_desc_s { - ct_data *static_tree; /* static tree or NULL */ + const ct_data *static_tree; /* static tree or NULL */ const intf *extra_bits; /* extra bits for each code or NULL */ int extra_base; /* base index for extra_bits */ int elems; /* max number of elements in the tree */ @@ -122,7 +133,7 @@ local static_tree_desc static_d_desc = {static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; local static_tree_desc static_bl_desc = -{(ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; +{(const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; /* =========================================================================== * Local (static) routines in this file. @@ -148,6 +159,10 @@ local void bi_flush OF((deflate_state *s)); local void copy_block OF((deflate_state *s, charf *buf, unsigned len, int header)); +#ifdef GEN_TREES_H +local void gen_trees_header OF((void)); +#endif + #ifndef DEBUG # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) /* Send a code of the given tree. c and tree must not have side effects */ @@ -226,12 +241,11 @@ local void send_bits(s, value, length) /* the arguments must not have side effects */ /* =========================================================================== - * Initialize the various 'constant' tables. In a multi-threaded environment, - * this function may be called by two threads concurrently, but this is - * harmless since both invocations do exactly the same thing. + * Initialize the various 'constant' tables. */ local void tr_static_init() { +#if defined(GEN_TREES_H) || !defined(STDC) static int static_init_done = 0; int n; /* iterates over tree elements */ int bits; /* bit counter */ @@ -295,7 +309,73 @@ local void tr_static_init() static_dtree[n].Code = bi_reverse((unsigned)n, 5); } static_init_done = 1; + +# ifdef GEN_TREES_H + gen_trees_header(); +# endif +#endif /* defined(GEN_TREES_H) || !defined(STDC) */ +} + +/* =========================================================================== + * Genererate the file trees.h describing the static trees. + */ +#ifdef GEN_TREES_H +# ifndef DEBUG +# include +# endif + +# define SEPARATOR(i, last, width) \ + ((i) == (last)? "\n};\n\n" : \ + ((i) % (width) == (width)-1 ? ",\n" : ", ")) + +void gen_trees_header() +{ + FILE *header = fopen("trees.h", "w"); + int i; + + Assert (header != NULL, "Can't open trees.h"); + fprintf(header, + "/* header created automatically with -DGEN_TREES_H */\n\n"); + + fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n"); + for (i = 0; i < L_CODES+2; i++) { + fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code, + static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5)); + } + + fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n"); + for (i = 0; i < D_CODES; i++) { + fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code, + static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5)); + } + + fprintf(header, "local const uch dist_code[DIST_CODE_LEN] = {\n"); + for (i = 0; i < DIST_CODE_LEN; i++) { + fprintf(header, "%2u%s", dist_code[i], + SEPARATOR(i, DIST_CODE_LEN-1, 20)); + } + + fprintf(header, "local const uch length_code[MAX_MATCH-MIN_MATCH+1]= {\n"); + for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) { + fprintf(header, "%2u%s", length_code[i], + SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20)); + } + + fprintf(header, "local const int base_length[LENGTH_CODES] = {\n"); + for (i = 0; i < LENGTH_CODES; i++) { + fprintf(header, "%1u%s", base_length[i], + SEPARATOR(i, LENGTH_CODES-1, 20)); + } + + fprintf(header, "local const int base_dist[D_CODES] = {\n"); + for (i = 0; i < D_CODES; i++) { + fprintf(header, "%5u%s", base_dist[i], + SEPARATOR(i, D_CODES-1, 10)); + } + + fclose(header); } +#endif /* GEN_TREES_H */ /* =========================================================================== * Initialize the tree data structures for a new zlib stream. @@ -413,12 +493,12 @@ local void gen_bitlen(s, desc) deflate_state *s; tree_desc *desc; /* the tree descriptor */ { - ct_data *tree = desc->dyn_tree; - int max_code = desc->max_code; - ct_data *stree = desc->stat_desc->static_tree; - const intf *extra = desc->stat_desc->extra_bits; - int base = desc->stat_desc->extra_base; - int max_length = desc->stat_desc->max_length; + ct_data *tree = desc->dyn_tree; + int max_code = desc->max_code; + const ct_data *stree = desc->stat_desc->static_tree; + const intf *extra = desc->stat_desc->extra_bits; + int base = desc->stat_desc->extra_base; + int max_length = desc->stat_desc->max_length; int h; /* heap index */ int n, m; /* iterate over the tree elements */ int bits; /* bit length */ @@ -542,9 +622,9 @@ local void build_tree(s, desc) deflate_state *s; tree_desc *desc; /* the tree descriptor */ { - ct_data *tree = desc->dyn_tree; - ct_data *stree = desc->stat_desc->static_tree; - int elems = desc->stat_desc->elems; + ct_data *tree = desc->dyn_tree; + const ct_data *stree = desc->stat_desc->static_tree; + int elems = desc->stat_desc->elems; int n, m; /* iterate over heap elements */ int max_code = -1; /* largest code with non zero frequency */ int node; /* new node being created */ -- cgit v1.2.3-55-g6feb