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