Deleted Added
sdiff udiff text old ( 17651 ) new ( 33904 )
full compact
trees.c (17651) trees.c (33904)
1/* trees.c -- output deflated data using Huffman coding
1/* trees.c -- output deflated data using Huffman coding
2 * Copyright (C) 1995-1996 Jean-loup Gailly
2 * Copyright (C) 1995-1998 Jean-loup Gailly
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/*
7 * ALGORITHM
8 *
9 * The "deflation" process uses several Huffman trees. The more
10 * common source values are represented by shorter bit sequences.

--- 13 unchanged lines hidden (view full) ---

24 * Data Compression: Methods and Theory, pp. 49-50.
25 * Computer Science Press, 1988. ISBN 0-7167-8156-5.
26 *
27 * Sedgewick, R.
28 * Algorithms, p290.
29 * Addison-Wesley, 1983. ISBN 0-201-06672-6.
30 */
31
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/*
7 * ALGORITHM
8 *
9 * The "deflation" process uses several Huffman trees. The more
10 * common source values are represented by shorter bit sequences.

--- 13 unchanged lines hidden (view full) ---

24 * Data Compression: Methods and Theory, pp. 49-50.
25 * Computer Science Press, 1988. ISBN 0-7167-8156-5.
26 *
27 * Sedgewick, R.
28 * Algorithms, p290.
29 * Addison-Wesley, 1983. ISBN 0-201-06672-6.
30 */
31
32/* $Id: trees.c,v 1.11 1996/07/24 13:41:06 me Exp $ */
32/* @(#) $Id$ */
33
33
34/* #define GEN_TREES_H */
35
34#include "deflate.h"
35
36#ifdef DEBUG
37# include <ctype.h>
38#endif
39
40/* ===========================================================================
41 * Constants

--- 9 unchanged lines hidden (view full) ---

51/* repeat previous bit length 3-6 times (2 bits of repeat count) */
52
53#define REPZ_3_10 17
54/* repeat a zero length 3-10 times (3 bits of repeat count) */
55
56#define REPZ_11_138 18
57/* repeat a zero length 11-138 times (7 bits of repeat count) */
58
36#include "deflate.h"
37
38#ifdef DEBUG
39# include <ctype.h>
40#endif
41
42/* ===========================================================================
43 * Constants

--- 9 unchanged lines hidden (view full) ---

53/* repeat previous bit length 3-6 times (2 bits of repeat count) */
54
55#define REPZ_3_10 17
56/* repeat a zero length 3-10 times (3 bits of repeat count) */
57
58#define REPZ_11_138 18
59/* repeat a zero length 11-138 times (7 bits of repeat count) */
60
59local int extra_lbits[LENGTH_CODES] /* extra bits for each length code */
61local const int extra_lbits[LENGTH_CODES] /* extra bits for each length code */
60 = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0};
61
62 = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0};
63
62local int extra_dbits[D_CODES] /* extra bits for each distance code */
64local const int extra_dbits[D_CODES] /* extra bits for each distance code */
63 = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};
64
65 = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};
66
65local int extra_blbits[BL_CODES]/* extra bits for each bit length code */
67local const int extra_blbits[BL_CODES]/* extra bits for each bit length code */
66 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
67
68 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
69
68local uch bl_order[BL_CODES]
70local const uch bl_order[BL_CODES]
69 = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
70/* The lengths of the bit length codes are sent in order of decreasing
71 * probability, to avoid transmitting the lengths for unused bit length codes.
72 */
73
74#define Buf_size (8 * 2*sizeof(char))
75/* Number of bits used within bi_buf. (bi_buf might be implemented on
76 * more than 16 bits on some systems.)
77 */
78
79/* ===========================================================================
80 * Local data. These are initialized only once.
81 */
82
71 = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
72/* The lengths of the bit length codes are sent in order of decreasing
73 * probability, to avoid transmitting the lengths for unused bit length codes.
74 */
75
76#define Buf_size (8 * 2*sizeof(char))
77/* Number of bits used within bi_buf. (bi_buf might be implemented on
78 * more than 16 bits on some systems.)
79 */
80
81/* ===========================================================================
82 * Local data. These are initialized only once.
83 */
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
83local ct_data static_ltree[L_CODES+2];
84/* 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
86 * The codes 286 and 287 are needed to build a canonical tree (see _tr_init
87 * below).
88 */
89
90local ct_data static_dtree[D_CODES];
91/* The static distance tree. (Actually a trivial tree since all codes use
92 * 5 bits.)
93 */
94
90local ct_data static_ltree[L_CODES+2];
91/* The static literal tree. Since the bit lengths are imposed, there is no
92 * need for the L_CODES extra codes used during heap construction. However
93 * The codes 286 and 287 are needed to build a canonical tree (see _tr_init
94 * below).
95 */
96
97local ct_data static_dtree[D_CODES];
98/* The static distance tree. (Actually a trivial tree since all codes use
99 * 5 bits.)
100 */
101
95local uch dist_code[512];
96/* distance codes. The first 256 values correspond to the distances
102uch _dist_code[DIST_CODE_LEN];
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
98 * the 15 bit distances.
99 */
100
104 * 3 .. 258, the last 256 values correspond to the top 8 bits of
105 * the 15 bit distances.
106 */
107
101local uch length_code[MAX_MATCH-MIN_MATCH+1];
108uch _length_code[MAX_MATCH-MIN_MATCH+1];
102/* length code for each normalized match length (0 == MIN_MATCH) */
103
104local int base_length[LENGTH_CODES];
105/* First normalized length for each code (0 = MIN_MATCH) */
106
107local int base_dist[D_CODES];
108/* First normalized distance for each code (0 = distance of 1) */
109
109/* length code for each normalized match length (0 == MIN_MATCH) */
110
111local int base_length[LENGTH_CODES];
112/* First normalized length for each code (0 = MIN_MATCH) */
113
114local int base_dist[D_CODES];
115/* First normalized distance for each code (0 = distance of 1) */
116
117#else
118# include "trees.h"
119#endif /* GEN_TREES_H */
120
110struct static_tree_desc_s {
121struct static_tree_desc_s {
111 ct_data *static_tree; /* static tree or NULL */
112 intf *extra_bits; /* extra bits for each code or NULL */
122 const ct_data *static_tree; /* static tree or NULL */
123 const intf *extra_bits; /* extra bits for each code or NULL */
113 int extra_base; /* base index for extra_bits */
114 int elems; /* max number of elements in the tree */
115 int max_length; /* max bit length for the codes */
116};
117
118local static_tree_desc static_l_desc =
119{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
120
121local static_tree_desc static_d_desc =
122{static_dtree, extra_dbits, 0, D_CODES, MAX_BITS};
123
124local static_tree_desc static_bl_desc =
124 int extra_base; /* base index for extra_bits */
125 int elems; /* max number of elements in the tree */
126 int max_length; /* max bit length for the codes */
127};
128
129local static_tree_desc static_l_desc =
130{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
131
132local static_tree_desc static_d_desc =
133{static_dtree, extra_dbits, 0, D_CODES, MAX_BITS};
134
135local 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
127/* ===========================================================================
128 * Local (static) routines in this file.
129 */
130
131local void tr_static_init OF((void));
132local void init_block OF((deflate_state *s));
133local void pqdownheap OF((deflate_state *s, ct_data *tree, int k));

--- 9 unchanged lines hidden (view full) ---

143 ct_data *dtree));
144local void set_data_type OF((deflate_state *s));
145local unsigned bi_reverse OF((unsigned value, int length));
146local void bi_windup OF((deflate_state *s));
147local void bi_flush OF((deflate_state *s));
148local void copy_block OF((deflate_state *s, charf *buf, unsigned len,
149 int header));
150
137
138/* ===========================================================================
139 * Local (static) routines in this file.
140 */
141
142local void tr_static_init OF((void));
143local void init_block OF((deflate_state *s));
144local void pqdownheap OF((deflate_state *s, ct_data *tree, int k));

--- 9 unchanged lines hidden (view full) ---

154 ct_data *dtree));
155local void set_data_type OF((deflate_state *s));
156local unsigned bi_reverse OF((unsigned value, int length));
157local void bi_windup OF((deflate_state *s));
158local void bi_flush OF((deflate_state *s));
159local void copy_block OF((deflate_state *s, charf *buf, unsigned len,
160 int header));
161
162#ifdef GEN_TREES_H
163local void gen_trees_header OF((void));
164#endif
165
151#ifndef DEBUG
152# 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 */
154
155#else /* DEBUG */
156# define send_code(s, c, tree) \
166#ifndef DEBUG
167# define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
168 /* Send a code of the given tree. c and tree must not have side effects */
169
170#else /* DEBUG */
171# define send_code(s, c, tree) \
157 { if (verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
172 { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
158 send_bits(s, tree[c].Code, tree[c].Len); }
159#endif
160
173 send_bits(s, tree[c].Code, tree[c].Len); }
174#endif
175
161#define d_code(dist) \
162 ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])
163/* Mapping from a distance to a distance code. dist is the distance - 1 and
164 * must not have side effects. dist_code[256] and dist_code[257] are never
165 * used.
166 */
167
168/* ===========================================================================
169 * Output a short LSB first on the stream.
170 * IN assertion: there is enough room in pendingBuf.
171 */
172#define put_short(s, w) { \
173 put_byte(s, (uch)((w) & 0xff)); \
174 put_byte(s, (uch)((ush)(w) >> 8)); \
175}

--- 45 unchanged lines hidden (view full) ---

221}
222#endif /* DEBUG */
223
224
225#define MAX(a,b) (a >= b ? a : b)
226/* the arguments must not have side effects */
227
228/* ===========================================================================
176/* ===========================================================================
177 * Output a short LSB first on the stream.
178 * IN assertion: there is enough room in pendingBuf.
179 */
180#define put_short(s, w) { \
181 put_byte(s, (uch)((w) & 0xff)); \
182 put_byte(s, (uch)((ush)(w) >> 8)); \
183}

--- 45 unchanged lines hidden (view full) ---

229}
230#endif /* DEBUG */
231
232
233#define MAX(a,b) (a >= b ? a : b)
234/* the arguments must not have side effects */
235
236/* ===========================================================================
229 * Initialize the various 'constant' tables. In a multi-threaded environment,
230 * this function may be called by two threads concurrently, but this is
231 * harmless since both invocations do exactly the same thing.
237 * Initialize the various 'constant' tables.
232 */
233local void tr_static_init()
234{
238 */
239local void tr_static_init()
240{
241#if defined(GEN_TREES_H) || !defined(STDC)
235 static int static_init_done = 0;
236 int n; /* iterates over tree elements */
237 int bits; /* bit counter */
238 int length; /* length value */
239 int code; /* code value */
240 int dist; /* distance index */
241 ush bl_count[MAX_BITS+1];
242 /* number of codes at each bit length for an optimal tree */
243
244 if (static_init_done) return;
245
246 /* Initialize the mapping length (0..255) -> length code (0..28) */
247 length = 0;
248 for (code = 0; code < LENGTH_CODES-1; code++) {
249 base_length[code] = length;
250 for (n = 0; n < (1<<extra_lbits[code]); n++) {
242 static int static_init_done = 0;
243 int n; /* iterates over tree elements */
244 int bits; /* bit counter */
245 int length; /* length value */
246 int code; /* code value */
247 int dist; /* distance index */
248 ush bl_count[MAX_BITS+1];
249 /* number of codes at each bit length for an optimal tree */
250
251 if (static_init_done) return;
252
253 /* Initialize the mapping length (0..255) -> length code (0..28) */
254 length = 0;
255 for (code = 0; code < LENGTH_CODES-1; code++) {
256 base_length[code] = length;
257 for (n = 0; n < (1<<extra_lbits[code]); n++) {
251 length_code[length++] = (uch)code;
258 _length_code[length++] = (uch)code;
252 }
253 }
254 Assert (length == 256, "tr_static_init: length != 256");
255 /* Note that the length 255 (match length 258) can be represented
256 * in two different ways: code 284 + 5 bits or code 285, so we
257 * overwrite length_code[255] to use the best encoding:
258 */
259 }
260 }
261 Assert (length == 256, "tr_static_init: length != 256");
262 /* Note that the length 255 (match length 258) can be represented
263 * in two different ways: code 284 + 5 bits or code 285, so we
264 * overwrite length_code[255] to use the best encoding:
265 */
259 length_code[length-1] = (uch)code;
266 _length_code[length-1] = (uch)code;
260
261 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
262 dist = 0;
263 for (code = 0 ; code < 16; code++) {
264 base_dist[code] = dist;
265 for (n = 0; n < (1<<extra_dbits[code]); n++) {
267
268 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
269 dist = 0;
270 for (code = 0 ; code < 16; code++) {
271 base_dist[code] = dist;
272 for (n = 0; n < (1<<extra_dbits[code]); n++) {
266 dist_code[dist++] = (uch)code;
273 _dist_code[dist++] = (uch)code;
267 }
268 }
269 Assert (dist == 256, "tr_static_init: dist != 256");
270 dist >>= 7; /* from now on, all distances are divided by 128 */
271 for ( ; code < D_CODES; code++) {
272 base_dist[code] = dist << 7;
273 for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
274 }
275 }
276 Assert (dist == 256, "tr_static_init: dist != 256");
277 dist >>= 7; /* from now on, all distances are divided by 128 */
278 for ( ; code < D_CODES; code++) {
279 base_dist[code] = dist << 7;
280 for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
274 dist_code[256 + dist++] = (uch)code;
281 _dist_code[256 + dist++] = (uch)code;
275 }
276 }
277 Assert (dist == 256, "tr_static_init: 256+dist != 512");
278
279 /* Construct the codes of the static literal tree */
280 for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
281 n = 0;
282 while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;

--- 7 unchanged lines hidden (view full) ---

290 gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
291
292 /* The static distance tree is trivial: */
293 for (n = 0; n < D_CODES; n++) {
294 static_dtree[n].Len = 5;
295 static_dtree[n].Code = bi_reverse((unsigned)n, 5);
296 }
297 static_init_done = 1;
282 }
283 }
284 Assert (dist == 256, "tr_static_init: 256+dist != 512");
285
286 /* Construct the codes of the static literal tree */
287 for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
288 n = 0;
289 while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;

--- 7 unchanged lines hidden (view full) ---

297 gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
298
299 /* The static distance tree is trivial: */
300 for (n = 0; n < D_CODES; n++) {
301 static_dtree[n].Len = 5;
302 static_dtree[n].Code = bi_reverse((unsigned)n, 5);
303 }
304 static_init_done = 1;
305
306# ifdef GEN_TREES_H
307 gen_trees_header();
308# endif
309#endif /* defined(GEN_TREES_H) || !defined(STDC) */
298}
299
300/* ===========================================================================
310}
311
312/* ===========================================================================
313 * Genererate the file trees.h describing the static trees.
314 */
315#ifdef GEN_TREES_H
316# ifndef DEBUG
317# include <stdio.h>
318# endif
319
320# define SEPARATOR(i, last, width) \
321 ((i) == (last)? "\n};\n\n" : \
322 ((i) % (width) == (width)-1 ? ",\n" : ", "))
323
324void gen_trees_header()
325{
326 FILE *header = fopen("trees.h", "w");
327 int i;
328
329 Assert (header != NULL, "Can't open trees.h");
330 fprintf(header,
331 "/* header created automatically with -DGEN_TREES_H */\n\n");
332
333 fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n");
334 for (i = 0; i < L_CODES+2; i++) {
335 fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code,
336 static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));
337 }
338
339 fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n");
340 for (i = 0; i < D_CODES; i++) {
341 fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code,
342 static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));
343 }
344
345 fprintf(header, "const uch _dist_code[DIST_CODE_LEN] = {\n");
346 for (i = 0; i < DIST_CODE_LEN; i++) {
347 fprintf(header, "%2u%s", _dist_code[i],
348 SEPARATOR(i, DIST_CODE_LEN-1, 20));
349 }
350
351 fprintf(header, "const uch _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");
352 for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {
353 fprintf(header, "%2u%s", _length_code[i],
354 SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));
355 }
356
357 fprintf(header, "local const int base_length[LENGTH_CODES] = {\n");
358 for (i = 0; i < LENGTH_CODES; i++) {
359 fprintf(header, "%1u%s", base_length[i],
360 SEPARATOR(i, LENGTH_CODES-1, 20));
361 }
362
363 fprintf(header, "local const int base_dist[D_CODES] = {\n");
364 for (i = 0; i < D_CODES; i++) {
365 fprintf(header, "%5u%s", base_dist[i],
366 SEPARATOR(i, D_CODES-1, 10));
367 }
368
369 fclose(header);
370}
371#endif /* GEN_TREES_H */
372
373/* ===========================================================================
301 * Initialize the tree data structures for a new zlib stream.
302 */
303void _tr_init(s)
304 deflate_state *s;
305{
306 tr_static_init();
307
308 s->compressed_len = 0L;

--- 99 unchanged lines hidden (view full) ---

408 * array bl_count contains the frequencies for each bit length.
409 * The length opt_len is updated; static_len is also updated if stree is
410 * not null.
411 */
412local void gen_bitlen(s, desc)
413 deflate_state *s;
414 tree_desc *desc; /* the tree descriptor */
415{
374 * Initialize the tree data structures for a new zlib stream.
375 */
376void _tr_init(s)
377 deflate_state *s;
378{
379 tr_static_init();
380
381 s->compressed_len = 0L;

--- 99 unchanged lines hidden (view full) ---

481 * array bl_count contains the frequencies for each bit length.
482 * The length opt_len is updated; static_len is also updated if stree is
483 * not null.
484 */
485local void gen_bitlen(s, desc)
486 deflate_state *s;
487 tree_desc *desc; /* the tree descriptor */
488{
416 ct_data *tree = desc->dyn_tree;
417 int max_code = desc->max_code;
418 ct_data *stree = desc->stat_desc->static_tree;
419 intf *extra = desc->stat_desc->extra_bits;
420 int base = desc->stat_desc->extra_base;
421 int max_length = desc->stat_desc->max_length;
489 ct_data *tree = desc->dyn_tree;
490 int max_code = desc->max_code;
491 const ct_data *stree = desc->stat_desc->static_tree;
492 const intf *extra = desc->stat_desc->extra_bits;
493 int base = desc->stat_desc->extra_base;
494 int max_length = desc->stat_desc->max_length;
422 int h; /* heap index */
423 int n, m; /* iterate over the tree elements */
424 int bits; /* bit length */
425 int xbits; /* extra bits */
426 ush f; /* frequency */
427 int overflow = 0; /* number of elements with bit length too large */
428
429 for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;

--- 107 unchanged lines hidden (view full) ---

537 * OUT assertions: the fields len and code are set to the optimal bit length
538 * and corresponding code. The length opt_len is updated; static_len is
539 * also updated if stree is not null. The field max_code is set.
540 */
541local void build_tree(s, desc)
542 deflate_state *s;
543 tree_desc *desc; /* the tree descriptor */
544{
495 int h; /* heap index */
496 int n, m; /* iterate over the tree elements */
497 int bits; /* bit length */
498 int xbits; /* extra bits */
499 ush f; /* frequency */
500 int overflow = 0; /* number of elements with bit length too large */
501
502 for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;

--- 107 unchanged lines hidden (view full) ---

610 * OUT assertions: the fields len and code are set to the optimal bit length
611 * and corresponding code. The length opt_len is updated; static_len is
612 * also updated if stree is not null. The field max_code is set.
613 */
614local void build_tree(s, desc)
615 deflate_state *s;
616 tree_desc *desc; /* the tree descriptor */
617{
545 ct_data *tree = desc->dyn_tree;
546 ct_data *stree = desc->stat_desc->static_tree;
547 int elems = desc->stat_desc->elems;
618 ct_data *tree = desc->dyn_tree;
619 const ct_data *stree = desc->stat_desc->static_tree;
620 int elems = desc->stat_desc->elems;
548 int n, m; /* iterate over heap elements */
549 int max_code = -1; /* largest code with non zero frequency */
550 int node; /* new node being created */
551
552 /* Construct the initial heap, with least frequent element in
553 * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
554 * heap[0] is not used.
555 */

--- 404 unchanged lines hidden (view full) ---

960 } else {
961 s->matches++;
962 /* Here, lc is the match length - MIN_MATCH */
963 dist--; /* dist = match distance - 1 */
964 Assert((ush)dist < (ush)MAX_DIST(s) &&
965 (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
966 (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match");
967
621 int n, m; /* iterate over heap elements */
622 int max_code = -1; /* largest code with non zero frequency */
623 int node; /* new node being created */
624
625 /* Construct the initial heap, with least frequent element in
626 * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
627 * heap[0] is not used.
628 */

--- 404 unchanged lines hidden (view full) ---

1033 } else {
1034 s->matches++;
1035 /* Here, lc is the match length - MIN_MATCH */
1036 dist--; /* dist = match distance - 1 */
1037 Assert((ush)dist < (ush)MAX_DIST(s) &&
1038 (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
1039 (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match");
1040
968 s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++;
1041 s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;
969 s->dyn_dtree[d_code(dist)].Freq++;
970 }
971
1042 s->dyn_dtree[d_code(dist)].Freq++;
1043 }
1044
1045#ifdef TRUNCATE_BLOCK
972 /* Try to guess if it is profitable to stop the current block here */
1046 /* Try to guess if it is profitable to stop the current block here */
973 if (s->level > 2 && (s->last_lit & 0xfff) == 0) {
1047 if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
974 /* Compute an upper bound for the compressed length */
975 ulg out_length = (ulg)s->last_lit*8L;
976 ulg in_length = (ulg)((long)s->strstart - s->block_start);
977 int dcode;
978 for (dcode = 0; dcode < D_CODES; dcode++) {
979 out_length += (ulg)s->dyn_dtree[dcode].Freq *
980 (5L+extra_dbits[dcode]);
981 }
982 out_length >>= 3;
983 Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
984 s->last_lit, in_length, out_length,
985 100L - out_length*100L/in_length));
986 if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
987 }
1048 /* Compute an upper bound for the compressed length */
1049 ulg out_length = (ulg)s->last_lit*8L;
1050 ulg in_length = (ulg)((long)s->strstart - s->block_start);
1051 int dcode;
1052 for (dcode = 0; dcode < D_CODES; dcode++) {
1053 out_length += (ulg)s->dyn_dtree[dcode].Freq *
1054 (5L+extra_dbits[dcode]);
1055 }
1056 out_length >>= 3;
1057 Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
1058 s->last_lit, in_length, out_length,
1059 100L - out_length*100L/in_length));
1060 if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
1061 }
1062#endif
988 return (s->last_lit == s->lit_bufsize-1);
989 /* We avoid equality with lit_bufsize because of wraparound at 64K
990 * on 16 bit machines and because stored blocks are restricted to
991 * 64K-1 bytes.
992 */
993}
994
995/* ===========================================================================

--- 13 unchanged lines hidden (view full) ---

1009 if (s->last_lit != 0) do {
1010 dist = s->d_buf[lx];
1011 lc = s->l_buf[lx++];
1012 if (dist == 0) {
1013 send_code(s, lc, ltree); /* send a literal byte */
1014 Tracecv(isgraph(lc), (stderr," '%c' ", lc));
1015 } else {
1016 /* Here, lc is the match length - MIN_MATCH */
1063 return (s->last_lit == s->lit_bufsize-1);
1064 /* We avoid equality with lit_bufsize because of wraparound at 64K
1065 * on 16 bit machines and because stored blocks are restricted to
1066 * 64K-1 bytes.
1067 */
1068}
1069
1070/* ===========================================================================

--- 13 unchanged lines hidden (view full) ---

1084 if (s->last_lit != 0) do {
1085 dist = s->d_buf[lx];
1086 lc = s->l_buf[lx++];
1087 if (dist == 0) {
1088 send_code(s, lc, ltree); /* send a literal byte */
1089 Tracecv(isgraph(lc), (stderr," '%c' ", lc));
1090 } else {
1091 /* Here, lc is the match length - MIN_MATCH */
1017 code = length_code[lc];
1092 code = _length_code[lc];
1018 send_code(s, code+LITERALS+1, ltree); /* send the length code */
1019 extra = extra_lbits[code];
1020 if (extra != 0) {
1021 lc -= base_length[code];
1022 send_bits(s, lc, extra); /* send the extra length bits */
1023 }
1024 dist--; /* dist is now the match distance - 1 */
1025 code = d_code(dist);

--- 116 unchanged lines hidden --- 		1093 send_code(s, code+LITERALS+1, ltree); /* send the length code */
1094 extra = extra_lbits[code];
1095 if (extra != 0) {
1096 lc -= base_length[code];
1097 send_bits(s, lc, extra); /* send the extra length bits */
1098 }
1099 dist--; /* dist is now the match distance - 1 */
1100 code = d_code(dist);

--- 116 unchanged lines hidden ---