1 /* Copyright (C) 1994, 1995, 1996, 1998 Aladdin Enterprises. All rights reserved.
2
3 This software is provided AS-IS with no warranty, either express or
4 implied.
5
6 This software is distributed under license and may not be copied,
7 modified or distributed except as expressly authorized under the terms
8 of the license contained in the file LICENSE in this distribution.
9
10 For more information about licensing, please refer to
11 http://www.ghostscript.com/licensing/. For information on
12 commercial licensing, go to http://www.artifex.com/licensing/ or
13 contact Artifex Software, Inc., 101 Lucas Valley Road #110,
14 San Rafael, CA 94903, U.S.A., +1(415)492-9861.
15 */
16
17 /* $Id: sbhc.c,v 1.5 2002/02/21 22:24:53 giles Exp $ */
18 /* Bounded Huffman code filters */
19 #include "memory_.h"
20 #include "stdio_.h"
21 #include "gdebug.h"
22 #include "strimpl.h"
23 #include "sbhc.h"
24 #include "shcgen.h"
25
26 /* ------ BoundedHuffmanEncode ------ */
27
28 private_st_BHCE_state();
29
30 /* Initialize BoundedHuffmanEncode filter. */
31 private int
s_BHCE_reinit(stream_state * st)32 s_BHCE_reinit(stream_state * st)
33 {
34 stream_BHCE_state *const ss = (stream_BHCE_state *) st;
35
36 ss->encode.count = ss->definition.num_values;
37 s_bhce_init_inline(ss);
38 return 0;
39 }
40 private int
s_BHCE_init(register stream_state * st)41 s_BHCE_init(register stream_state * st)
42 {
43 stream_BHCE_state *const ss = (stream_BHCE_state *) st;
44 hce_code *encode = ss->encode.codes =
45 (hce_code *) gs_alloc_byte_array(st->memory,
46 ss->definition.num_values,
47 sizeof(hce_code), "BHCE encode");
48
49 if (encode == 0)
50 return ERRC;
51 /****** WRONG ******/
52 hc_make_encoding(encode, &ss->definition);
53 return s_BHCE_reinit(st);
54 }
55
56 /* Release the filter. */
57 private void
s_BHCE_release(stream_state * st)58 s_BHCE_release(stream_state * st)
59 {
60 stream_BHCE_state *const ss = (stream_BHCE_state *) st;
61
62 gs_free_object(st->memory, ss->encode.codes, "BHCE encode");
63 }
64
65 /* Process a buffer. */
66 private int
s_BHCE_process(stream_state * st,stream_cursor_read * pr,stream_cursor_write * pw,bool last)67 s_BHCE_process(stream_state * st, stream_cursor_read * pr,
68 stream_cursor_write * pw, bool last)
69 {
70 stream_BHCE_state *const ss = (stream_BHCE_state *) st;
71 const byte *p = pr->ptr;
72 const byte *rlimit = pr->limit;
73 byte *q = pw->ptr;
74 byte *wlimit = pw->limit - (hc_bits_size >> 3);
75 const hce_code *encode = ss->encode.codes;
76 uint num_values = ss->definition.num_values;
77 uint zero_runs = ss->EncodeZeroRuns;
78 uint zero_max = num_values - zero_runs + (ss->EndOfData ? 0 : 1);
79 uint zero_value = (zero_max > 1 ? 0 : 0x100);
80 int zeros = ss->zeros;
81 int status = 0;
82
83 hce_declare_state;
84
85 hce_load_state();
86 while (p < rlimit && q < wlimit) {
87 uint value = *++p;
88 const hce_code *cp;
89
90 if (value >= num_values) {
91 status = ERRC;
92 break;
93 }
94 if (value == zero_value) { /* Accumulate a run of zeros. */
95 ++zeros;
96 if (zeros != zero_max)
97 continue;
98 /* We've scanned the longest run we can encode. */
99 cp = &encode[zeros - 2 + zero_runs];
100 zeros = 0;
101 hc_put_code((stream_hc_state *) ss, q, cp);
102 continue;
103 }
104 /* Check whether we need to put out a zero run. */
105 if (zeros > 0) {
106 --p;
107 cp = (zeros == 1 ? &encode[0] :
108 &encode[zeros - 2 + zero_runs]);
109 zeros = 0;
110 hc_put_code((stream_hc_state *) ss, q, cp);
111 continue;
112 }
113 cp = &encode[value];
114 hc_put_code((stream_hc_state *) ss, q, cp);
115 }
116 if (q >= wlimit)
117 status = 1;
118 wlimit = pw->limit;
119 if (last && status == 0) {
120 if (zeros > 0) { /* Put out a final run of zeros. */
121 const hce_code *cp = (zeros == 1 ? &encode[0] :
122 &encode[zeros - 2 + zero_runs]);
123
124 if (!hce_bits_available(cp->code_length))
125 status = 1;
126 else {
127 hc_put_code((stream_hc_state *) ss, q, cp);
128 zeros = 0;
129 }
130 }
131 if (ss->EndOfData) { /* Put out the EOD code if we have room. */
132 const hce_code *cp = &encode[num_values - 1];
133
134 if (!hce_bits_available(cp->code_length))
135 status = 1;
136 else
137 hc_put_code((stream_hc_state *) ss, q, cp);
138 } else {
139 if (q >= wlimit)
140 status = 1;
141 }
142 if (!status) {
143 q = hc_put_last_bits((stream_hc_state *) ss, q);
144 goto ns;
145 }
146 }
147 hce_store_state();
148 ns:pr->ptr = p;
149 pw->ptr = q;
150 ss->zeros = zeros;
151 return (p == rlimit ? 0 : 1);
152 }
153
154 /* Stream template */
155 const stream_template s_BHCE_template =
156 {&st_BHCE_state, s_BHCE_init, s_BHCE_process,
157 1, hc_bits_size >> 3, s_BHCE_release, NULL, s_BHCE_reinit
158 };
159
160 /* ------ BoundedHuffmanDecode ------ */
161
162 private_st_BHCD_state();
163
164 #define hcd_initial_bits 7 /* arbitrary, >= 1 and <= 8 */
165
166 /* Initialize BoundedHuffmanDecode filter. */
167 private int
s_BHCD_reinit(stream_state * st)168 s_BHCD_reinit(stream_state * st)
169 {
170 stream_BHCD_state *const ss = (stream_BHCD_state *) st;
171
172 ss->decode.count = ss->definition.num_values;
173 s_bhcd_init_inline(ss);
174 return 0;
175 }
176 private int
s_BHCD_init(register stream_state * st)177 s_BHCD_init(register stream_state * st)
178 {
179 stream_BHCD_state *const ss = (stream_BHCD_state *) st;
180 uint initial_bits = ss->decode.initial_bits =
181 min(hcd_initial_bits, ss->definition.num_counts);
182 uint dsize = hc_sizeof_decoding(&ss->definition, initial_bits);
183 hcd_code *decode = ss->decode.codes =
184 (hcd_code *) gs_alloc_byte_array(st->memory, dsize,
185 sizeof(hcd_code), "BHCD decode");
186
187 if (decode == 0)
188 return ERRC;
189 /****** WRONG ******/
190 hc_make_decoding(decode, &ss->definition, initial_bits);
191 st->min_left = 1;
192 return s_BHCD_reinit(st);
193 }
194
195 /* Release the filter. */
196 private void
s_BHCD_release(stream_state * st)197 s_BHCD_release(stream_state * st)
198 {
199 stream_BHCD_state *const ss = (stream_BHCD_state *) st;
200
201 gs_free_object(st->memory, ss->decode.codes, "BHCD decode");
202 }
203
204 /* Process a buffer. */
205 private int
s_BHCD_process(stream_state * st,stream_cursor_read * pr,stream_cursor_write * pw,bool last)206 s_BHCD_process(stream_state * st, stream_cursor_read * pr,
207 stream_cursor_write * pw, bool last)
208 {
209 stream_BHCD_state *const ss = (stream_BHCD_state *) st;
210
211 bhcd_declare_state;
212 byte *q = pw->ptr;
213 byte *wlimit = pw->limit;
214 const hcd_code *decode = ss->decode.codes;
215 uint initial_bits = ss->decode.initial_bits;
216 uint zero_runs = ss->EncodeZeroRuns;
217 int status = 0;
218 int eod = (ss->EndOfData ? ss->definition.num_values - 1 : -1);
219
220 bhcd_load_state();
221 z:for (; zeros > 0; --zeros) {
222 if (q >= wlimit) {
223 status = 1;
224 goto out;
225 }
226 *++q = 0;
227 }
228 for (;;) {
229 const hcd_code *cp;
230 int clen;
231
232 hcd_ensure_bits(initial_bits, x1);
233 cp = &decode[hcd_peek_var_bits(initial_bits)];
234 w1:if (q >= wlimit) {
235 status = 1;
236 break;
237 }
238 if ((clen = cp->code_length) > initial_bits) {
239 if (!hcd_bits_available(clen)) { /* We don't have enough bits for */
240 /* all possible codes that begin this way, */
241 /* but we might have enough for */
242 /* the next code. */
243 /****** NOT IMPLEMENTED YET ******/
244 break;
245 }
246 clen -= initial_bits;
247 hcd_skip_bits(initial_bits);
248 hcd_ensure_bits(clen, out); /* can't exit */
249 cp = &decode[cp->value + hcd_peek_var_bits(clen)];
250 hcd_skip_bits(cp->code_length);
251 } else {
252 hcd_skip_bits(clen);
253 }
254 if (cp->value >= zero_runs) {
255 if (cp->value == eod) {
256 status = EOFC;
257 goto out;
258 }
259 /* This code represents a run of zeros, */
260 /* not a single output value. */
261 zeros = cp->value - zero_runs + 2;
262 goto z;
263 }
264 *++q = cp->value;
265 continue;
266 /* We don't have enough bits for all possible */
267 /* codes, but we might have enough for */
268 /* the next code. */
269 x1:cp = &decode[(bits & ((1 << bits_left) - 1)) <<
270 (initial_bits - bits_left)];
271 if ((clen = cp->code_length) <= bits_left)
272 goto w1;
273 break;
274 }
275 out:bhcd_store_state();
276 pw->ptr = q;
277 return status;
278 }
279
280 /* Stream template */
281 const stream_template s_BHCD_template =
282 {&st_BHCD_state, s_BHCD_init, s_BHCD_process, 1, 1, s_BHCD_release,
283 NULL, s_BHCD_reinit
284 };
285