diff options
author | Mark Adler <madler@alumni.caltech.edu> | 2011-09-09 23:18:57 -0700 |
---|---|---|
committer | Mark Adler <madler@alumni.caltech.edu> | 2011-09-09 23:18:57 -0700 |
commit | 6759211ad8a5006689216a86c3267bb503bfccc1 (patch) | |
tree | dc0f61f4c4a44828ad7d30e376ef21840b137f44 /trees.c | |
parent | 7850e4e406dce1f7a819297eeb151d1ca18e7cd9 (diff) | |
download | zlib-6759211ad8a5006689216a86c3267bb503bfccc1.tar.gz zlib-6759211ad8a5006689216a86c3267bb503bfccc1.tar.bz2 zlib-6759211ad8a5006689216a86c3267bb503bfccc1.zip |
zlib 1.0.8v1.0.8
Diffstat (limited to 'trees.c')
-rw-r--r-- | trees.c | 112 |
1 files changed, 96 insertions, 16 deletions
@@ -31,6 +31,8 @@ | |||
31 | 31 | ||
32 | /* @(#) $Id$ */ | 32 | /* @(#) $Id$ */ |
33 | 33 | ||
34 | /* #define GEN_TREES_H */ | ||
35 | |||
34 | #include "deflate.h" | 36 | #include "deflate.h" |
35 | 37 | ||
36 | #ifdef DEBUG | 38 | #ifdef DEBUG |
@@ -80,6 +82,11 @@ local const uch bl_order[BL_CODES] | |||
80 | * Local data. These are initialized only once. | 82 | * Local data. These are initialized only once. |
81 | */ | 83 | */ |
82 | 84 | ||
85 | #define DIST_CODE_LEN 512 /* see definition of array dist_code below */ | ||
86 | |||
87 | #if defined(GEN_TREES_H) || !defined(STDC) | ||
88 | /* non ANSI compilers may not accept trees.h */ | ||
89 | |||
83 | local ct_data static_ltree[L_CODES+2]; | 90 | local ct_data static_ltree[L_CODES+2]; |
84 | /* The static literal tree. Since the bit lengths are imposed, there is no | 91 | /* The static literal tree. Since the bit lengths are imposed, there is no |
85 | * need for the L_CODES extra codes used during heap construction. However | 92 | * need for the L_CODES extra codes used during heap construction. However |
@@ -92,8 +99,8 @@ local ct_data static_dtree[D_CODES]; | |||
92 | * 5 bits.) | 99 | * 5 bits.) |
93 | */ | 100 | */ |
94 | 101 | ||
95 | local uch dist_code[512]; | 102 | local uch dist_code[DIST_CODE_LEN]; |
96 | /* distance codes. The first 256 values correspond to the distances | 103 | /* Distance codes. The first 256 values correspond to the distances |
97 | * 3 .. 258, the last 256 values correspond to the top 8 bits of | 104 | * 3 .. 258, the last 256 values correspond to the top 8 bits of |
98 | * the 15 bit distances. | 105 | * the 15 bit distances. |
99 | */ | 106 | */ |
@@ -107,8 +114,12 @@ local int base_length[LENGTH_CODES]; | |||
107 | local int base_dist[D_CODES]; | 114 | local int base_dist[D_CODES]; |
108 | /* First normalized distance for each code (0 = distance of 1) */ | 115 | /* First normalized distance for each code (0 = distance of 1) */ |
109 | 116 | ||
117 | #else | ||
118 | # include "trees.h" | ||
119 | #endif /* GEN_TREES_H */ | ||
120 | |||
110 | struct static_tree_desc_s { | 121 | struct static_tree_desc_s { |
111 | ct_data *static_tree; /* static tree or NULL */ | 122 | const ct_data *static_tree; /* static tree or NULL */ |
112 | const intf *extra_bits; /* extra bits for each code or NULL */ | 123 | const intf *extra_bits; /* extra bits for each code or NULL */ |
113 | int extra_base; /* base index for extra_bits */ | 124 | int extra_base; /* base index for extra_bits */ |
114 | int elems; /* max number of elements in the tree */ | 125 | int elems; /* max number of elements in the tree */ |
@@ -122,7 +133,7 @@ local static_tree_desc static_d_desc = | |||
122 | {static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; | 133 | {static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; |
123 | 134 | ||
124 | local static_tree_desc static_bl_desc = | 135 | local static_tree_desc static_bl_desc = |
125 | {(ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; | 136 | {(const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; |
126 | 137 | ||
127 | /* =========================================================================== | 138 | /* =========================================================================== |
128 | * Local (static) routines in this file. | 139 | * Local (static) routines in this file. |
@@ -148,6 +159,10 @@ local void bi_flush OF((deflate_state *s)); | |||
148 | local void copy_block OF((deflate_state *s, charf *buf, unsigned len, | 159 | local void copy_block OF((deflate_state *s, charf *buf, unsigned len, |
149 | int header)); | 160 | int header)); |
150 | 161 | ||
162 | #ifdef GEN_TREES_H | ||
163 | local void gen_trees_header OF((void)); | ||
164 | #endif | ||
165 | |||
151 | #ifndef DEBUG | 166 | #ifndef DEBUG |
152 | # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) | 167 | # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) |
153 | /* Send a code of the given tree. c and tree must not have side effects */ | 168 | /* 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) | |||
226 | /* the arguments must not have side effects */ | 241 | /* the arguments must not have side effects */ |
227 | 242 | ||
228 | /* =========================================================================== | 243 | /* =========================================================================== |
229 | * Initialize the various 'constant' tables. In a multi-threaded environment, | 244 | * Initialize the various 'constant' tables. |
230 | * this function may be called by two threads concurrently, but this is | ||
231 | * harmless since both invocations do exactly the same thing. | ||
232 | */ | 245 | */ |
233 | local void tr_static_init() | 246 | local void tr_static_init() |
234 | { | 247 | { |
248 | #if defined(GEN_TREES_H) || !defined(STDC) | ||
235 | static int static_init_done = 0; | 249 | static int static_init_done = 0; |
236 | int n; /* iterates over tree elements */ | 250 | int n; /* iterates over tree elements */ |
237 | int bits; /* bit counter */ | 251 | int bits; /* bit counter */ |
@@ -295,7 +309,73 @@ local void tr_static_init() | |||
295 | static_dtree[n].Code = bi_reverse((unsigned)n, 5); | 309 | static_dtree[n].Code = bi_reverse((unsigned)n, 5); |
296 | } | 310 | } |
297 | static_init_done = 1; | 311 | static_init_done = 1; |
312 | |||
313 | # ifdef GEN_TREES_H | ||
314 | gen_trees_header(); | ||
315 | # endif | ||
316 | #endif /* defined(GEN_TREES_H) || !defined(STDC) */ | ||
317 | } | ||
318 | |||
319 | /* =========================================================================== | ||
320 | * Genererate the file trees.h describing the static trees. | ||
321 | */ | ||
322 | #ifdef GEN_TREES_H | ||
323 | # ifndef DEBUG | ||
324 | # include <stdio.h> | ||
325 | # endif | ||
326 | |||
327 | # define SEPARATOR(i, last, width) \ | ||
328 | ((i) == (last)? "\n};\n\n" : \ | ||
329 | ((i) % (width) == (width)-1 ? ",\n" : ", ")) | ||
330 | |||
331 | void gen_trees_header() | ||
332 | { | ||
333 | FILE *header = fopen("trees.h", "w"); | ||
334 | int i; | ||
335 | |||
336 | Assert (header != NULL, "Can't open trees.h"); | ||
337 | fprintf(header, | ||
338 | "/* header created automatically with -DGEN_TREES_H */\n\n"); | ||
339 | |||
340 | fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n"); | ||
341 | for (i = 0; i < L_CODES+2; i++) { | ||
342 | fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code, | ||
343 | static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5)); | ||
344 | } | ||
345 | |||
346 | fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n"); | ||
347 | for (i = 0; i < D_CODES; i++) { | ||
348 | fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code, | ||
349 | static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5)); | ||
350 | } | ||
351 | |||
352 | fprintf(header, "local const uch dist_code[DIST_CODE_LEN] = {\n"); | ||
353 | for (i = 0; i < DIST_CODE_LEN; i++) { | ||
354 | fprintf(header, "%2u%s", dist_code[i], | ||
355 | SEPARATOR(i, DIST_CODE_LEN-1, 20)); | ||
356 | } | ||
357 | |||
358 | fprintf(header, "local const uch length_code[MAX_MATCH-MIN_MATCH+1]= {\n"); | ||
359 | for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) { | ||
360 | fprintf(header, "%2u%s", length_code[i], | ||
361 | SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20)); | ||
362 | } | ||
363 | |||
364 | fprintf(header, "local const int base_length[LENGTH_CODES] = {\n"); | ||
365 | for (i = 0; i < LENGTH_CODES; i++) { | ||
366 | fprintf(header, "%1u%s", base_length[i], | ||
367 | SEPARATOR(i, LENGTH_CODES-1, 20)); | ||
368 | } | ||
369 | |||
370 | fprintf(header, "local const int base_dist[D_CODES] = {\n"); | ||
371 | for (i = 0; i < D_CODES; i++) { | ||
372 | fprintf(header, "%5u%s", base_dist[i], | ||
373 | SEPARATOR(i, D_CODES-1, 10)); | ||
374 | } | ||
375 | |||
376 | fclose(header); | ||
298 | } | 377 | } |
378 | #endif /* GEN_TREES_H */ | ||
299 | 379 | ||
300 | /* =========================================================================== | 380 | /* =========================================================================== |
301 | * Initialize the tree data structures for a new zlib stream. | 381 | * Initialize the tree data structures for a new zlib stream. |
@@ -413,12 +493,12 @@ local void gen_bitlen(s, desc) | |||
413 | deflate_state *s; | 493 | deflate_state *s; |
414 | tree_desc *desc; /* the tree descriptor */ | 494 | tree_desc *desc; /* the tree descriptor */ |
415 | { | 495 | { |
416 | ct_data *tree = desc->dyn_tree; | 496 | ct_data *tree = desc->dyn_tree; |
417 | int max_code = desc->max_code; | 497 | int max_code = desc->max_code; |
418 | ct_data *stree = desc->stat_desc->static_tree; | 498 | const ct_data *stree = desc->stat_desc->static_tree; |
419 | const intf *extra = desc->stat_desc->extra_bits; | 499 | const intf *extra = desc->stat_desc->extra_bits; |
420 | int base = desc->stat_desc->extra_base; | 500 | int base = desc->stat_desc->extra_base; |
421 | int max_length = desc->stat_desc->max_length; | 501 | int max_length = desc->stat_desc->max_length; |
422 | int h; /* heap index */ | 502 | int h; /* heap index */ |
423 | int n, m; /* iterate over the tree elements */ | 503 | int n, m; /* iterate over the tree elements */ |
424 | int bits; /* bit length */ | 504 | int bits; /* bit length */ |
@@ -542,9 +622,9 @@ local void build_tree(s, desc) | |||
542 | deflate_state *s; | 622 | deflate_state *s; |
543 | tree_desc *desc; /* the tree descriptor */ | 623 | tree_desc *desc; /* the tree descriptor */ |
544 | { | 624 | { |
545 | ct_data *tree = desc->dyn_tree; | 625 | ct_data *tree = desc->dyn_tree; |
546 | ct_data *stree = desc->stat_desc->static_tree; | 626 | const ct_data *stree = desc->stat_desc->static_tree; |
547 | int elems = desc->stat_desc->elems; | 627 | int elems = desc->stat_desc->elems; |
548 | int n, m; /* iterate over heap elements */ | 628 | int n, m; /* iterate over heap elements */ |
549 | int max_code = -1; /* largest code with non zero frequency */ | 629 | int max_code = -1; /* largest code with non zero frequency */ |
550 | int node; /* new node being created */ | 630 | int node; /* new node being created */ |