deftree.c (e5451c8f8330e03ad3cfa16048b4daf961af434f) deftree.c (aa5b395b69b65450e008b95ec623b4fc4b175f9f)
1/* +++ trees.c */
2/* trees.c -- output deflated data using Huffman coding
3 * Copyright (C) 1995-1996 Jean-loup Gailly
4 * For conditions of distribution and use, see copyright notice in zlib.h
5 */
6
7/*
8 * ALGORITHM

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

71 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
72
73static const uch bl_order[BL_CODES]
74 = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
75/* The lengths of the bit length codes are sent in order of decreasing
76 * probability, to avoid transmitting the lengths for unused bit length codes.
77 */
78
1/* +++ trees.c */
2/* trees.c -- output deflated data using Huffman coding
3 * Copyright (C) 1995-1996 Jean-loup Gailly
4 * For conditions of distribution and use, see copyright notice in zlib.h
5 */
6
7/*
8 * ALGORITHM

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

71 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
72
73static const uch bl_order[BL_CODES]
74 = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
75/* The lengths of the bit length codes are sent in order of decreasing
76 * probability, to avoid transmitting the lengths for unused bit length codes.
77 */
78
79#define Buf_size (8 * 2*sizeof(char))
80/* Number of bits used within bi_buf. (bi_buf might be implemented on
81 * more than 16 bits on some systems.)
82 */
83
84/* ===========================================================================
85 * Local data. These are initialized only once.
86 */
87
88static ct_data static_ltree[L_CODES+2];
89/* The static literal tree. Since the bit lengths are imposed, there is no
90 * need for the L_CODES extra codes used during heap construction. However
91 * The codes 286 and 287 are needed to build a canonical tree (see zlib_tr_init

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

142static void scan_tree (deflate_state *s, ct_data *tree, int max_code);
143static void send_tree (deflate_state *s, ct_data *tree, int max_code);
144static int build_bl_tree (deflate_state *s);
145static void send_all_trees (deflate_state *s, int lcodes, int dcodes,
146 int blcodes);
147static void compress_block (deflate_state *s, ct_data *ltree,
148 ct_data *dtree);
149static void set_data_type (deflate_state *s);
79/* ===========================================================================
80 * Local data. These are initialized only once.
81 */
82
83static 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 zlib_tr_init

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

137static void scan_tree (deflate_state *s, ct_data *tree, int max_code);
138static void send_tree (deflate_state *s, ct_data *tree, int max_code);
139static int build_bl_tree (deflate_state *s);
140static void send_all_trees (deflate_state *s, int lcodes, int dcodes,
141 int blcodes);
142static void compress_block (deflate_state *s, ct_data *ltree,
143 ct_data *dtree);
144static void set_data_type (deflate_state *s);
150static void bi_windup (deflate_state *s);
151static void bi_flush (deflate_state *s);
152static void copy_block (deflate_state *s, char *buf, unsigned len,
153 int header);
154
155#ifndef DEBUG_ZLIB
156# define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
157 /* Send a code of the given tree. c and tree must not have side effects */
158

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

165#define d_code(dist) \
166 ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])
167/* Mapping from a distance to a distance code. dist is the distance - 1 and
168 * must not have side effects. dist_code[256] and dist_code[257] are never
169 * used.
170 */
171
172/* ===========================================================================
145static void bi_flush (deflate_state *s);
146static void copy_block (deflate_state *s, char *buf, unsigned len,
147 int header);
148
149#ifndef DEBUG_ZLIB
150# define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
151 /* Send a code of the given tree. c and tree must not have side effects */
152

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

159#define d_code(dist) \
160 ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])
161/* Mapping from a distance to a distance code. dist is the distance - 1 and
162 * must not have side effects. dist_code[256] and dist_code[257] are never
163 * used.
164 */
165
166/* ===========================================================================
173 * Send a value on a given number of bits.
174 * IN assertion: length <= 16 and value fits in length bits.
175 */
176#ifdef DEBUG_ZLIB
177static void send_bits (deflate_state *s, int value, int length);
178
179static void send_bits(
180 deflate_state *s,
181 int value, /* value to send */
182 int length /* number of bits */
183)
184{
185 Tracevv((stderr," l %2d v %4x ", length, value));
186 Assert(length > 0 && length <= 15, "invalid length");
187 s->bits_sent += (ulg)length;
188
189 /* If not enough room in bi_buf, use (valid) bits from bi_buf and
190 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
191 * unused bits in value.
192 */
193 if (s->bi_valid > (int)Buf_size - length) {
194 s->bi_buf |= (value << s->bi_valid);
195 put_short(s, s->bi_buf);
196 s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
197 s->bi_valid += length - Buf_size;
198 } else {
199 s->bi_buf |= value << s->bi_valid;
200 s->bi_valid += length;
201 }
202}
203#else /* !DEBUG_ZLIB */
204
205#define send_bits(s, value, length) \
206{ int len = length;\
207 if (s->bi_valid > (int)Buf_size - len) {\
208 int val = value;\
209 s->bi_buf |= (val << s->bi_valid);\
210 put_short(s, s->bi_buf);\
211 s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
212 s->bi_valid += len - Buf_size;\
213 } else {\
214 s->bi_buf |= (value) << s->bi_valid;\
215 s->bi_valid += len;\
216 }\
217}
218#endif /* DEBUG_ZLIB */
219
220/* ===========================================================================
221 * Initialize the various 'constant' tables. In a multi-threaded environment,
222 * this function may be called by two threads concurrently, but this is
223 * harmless since both invocations do exactly the same thing.
224 */
225static void tr_static_init(void)
226{
227 static int static_init_done;
228 int n; /* iterates over tree elements */

--- 885 unchanged lines hidden --- 		167 * Initialize the various 'constant' tables. In a multi-threaded environment,
168 * this function may be called by two threads concurrently, but this is
169 * harmless since both invocations do exactly the same thing.
170 */
171static void tr_static_init(void)
172{
173 static int static_init_done;
174 int n; /* iterates over tree elements */

--- 885 unchanged lines hidden ---