1 /* Copyright (C) 1993, 1996, 1998, 1999 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: slzwd.c,v 1.7 2005/10/20 19:42:18 ray Exp $ */
18 /* LZW decoding filter */
19 #include "stdio_.h" /* includes std.h */
20 #include "gdebug.h"
21 #include "strimpl.h"
22 #include "slzwx.h"
23
24 /* ------ LZWDecode ------ */
25
26 /********************************************************/
27 /* LZW routines are based on: */
28 /* Dr. Dobbs Journal --- Oct. 1989. */
29 /* Article on LZW Data Compression by Mark R. Nelson */
30 /********************************************************/
31
32 /* Define the special codes in terms of code_escape, which is */
33 /* 1 << InitialCodeLength. */
34 #define code_reset (code_escape + 0)
35 #define code_eod (code_escape + 1)
36 #define code_0 (code_escape + 2) /* first assignable code */
37
38 struct lzw_decode_s {
39 byte datum;
40 byte len; /* length of code */
41 ushort prefix; /* code to be prefixed */
42 };
43
44 gs_private_st_simple(st_lzw_decode, lzw_decode, "lzw_decode");
45 /* We can use a simple type as the element type, */
46 /* because there are no pointers to enumerate or relocate. */
47 #define st_lzw_decode_element st_lzw_decode
48 #define lzw_decode_max 4096 /* must be 4096 */
49
50 /* Initialize LZWDecode filter */
51 /* We separate out the reset function for some non-stream clients. */
52 private int
s_LZWD_reset(stream_state * st)53 s_LZWD_reset(stream_state * st)
54 {
55 stream_LZW_state *const ss = (stream_LZW_state *) st;
56 register lzw_decode *dc = ss->table.decode;
57 register int i;
58 uint code_escape = 1 << ss->InitialCodeLength;
59
60 ss->bits_left = 0;
61 ss->bytes_left = 0;
62 ss->next_code = code_0;
63 ss->code_size = ss->InitialCodeLength + 1;
64 ss->prev_code = -1;
65 ss->copy_code = -1;
66 dc[code_reset].len = 255;
67 dc[code_eod].len = 255;
68 for (i = 0; i < code_escape; i++, dc++)
69 dc->datum = i, dc->len = 1, dc->prefix = code_eod;
70 return 0;
71 }
72 private int
s_LZWD_init(stream_state * st)73 s_LZWD_init(stream_state * st)
74 {
75 stream_LZW_state *const ss = (stream_LZW_state *) st;
76 lzw_decode *dc =
77 gs_alloc_struct_array(st->memory, lzw_decode_max + 1,
78 lzw_decode, &st_lzw_decode_element,
79 "LZWDecode(init)");
80
81 if (dc == 0)
82 return ERRC;
83 /****** WRONG ******/
84 ss->table.decode = dc;
85 ss->min_left = 1;
86 return s_LZWD_reset(st);
87 }
88
89 /* Process a buffer */
90 private int
s_LZWD_process(stream_state * st,stream_cursor_read * pr,stream_cursor_write * pw,bool last)91 s_LZWD_process(stream_state * st, stream_cursor_read * pr,
92 stream_cursor_write * pw, bool last)
93 {
94 stream_LZW_state *const ss = (stream_LZW_state *) st;
95 register const byte *p = pr->ptr;
96 register byte *q = pw->ptr;
97
98 #ifdef DEBUG
99 byte *q0 = q;
100
101 #endif
102 const byte *rlimit = pr->limit; /* constant pointer */
103 byte *wlimit = pw->limit; /* constant pointer */
104 int status = 0;
105 int code = ss->copy_code;
106 int prev_code = ss->prev_code;
107 uint prev_len = ss->prev_len;
108 byte bits = ss->bits;
109 int bits_left = ss->bits_left;
110 int bytes_left = ss->bytes_left;
111 int code_size = ss->code_size;
112 int code_mask;
113 int switch_code;
114 int next_code = ss->next_code;
115 lzw_decode *table = ss->table.decode; /* constant pointer */
116 lzw_decode *dc_next = table + next_code; /* invariant */
117 lzw_decode *dc;
118 int code_escape = 1 << ss->InitialCodeLength;
119 int eod = code_eod;
120 bool low_order = ss->FirstBitLowOrder;
121 uint len;
122 int c;
123 byte b;
124 byte *q1;
125
126 if_debug2('w', "[w]process decode: code_size=%d next_code=%d\n",
127 code_size, next_code);
128 #define set_code_size()\
129 code_mask = (1 << code_size) - 1,\
130 switch_code = code_mask + 1 - ss->EarlyChange
131 set_code_size();
132 if (!ss->BlockData)
133 bytes_left = rlimit - p + 2; /* never stop for bytes_left */
134 /* If we are in the middle of copying a string, */
135 /* do some more now. */
136 if (code >= 0) {
137 int rlen = ss->copy_left;
138 int wlen = wlimit - q;
139 int n = len = min(rlen, wlen);
140
141 c = code;
142 ss->copy_left = rlen -= len;
143 if_debug3('W', "[W]copying 0x%x, %d byte(s) out of %d left\n",
144 code, len, rlen + len);
145 while (rlen)
146 c = table[c].prefix,
147 rlen--;
148 q1 = q += len;
149 n = len;
150 while (--n >= 0) {
151 *q1-- = (dc = &table[c])->datum;
152 c = dc->prefix;
153 }
154 if (ss->copy_left) { /* more to do */
155 pw->ptr = q;
156 return 1;
157 }
158 ss->copy_code = -1;
159 len = ss->copy_len;
160 /* Retrieve the first byte of the code just copied. */
161 if (c == eod) { /* We just copied the entire code, */
162 /* so the byte we want is immediately available. */
163 b = q1[1];
164 } else { /* We have to scan to the beginning of the code. */
165 for (; c != eod; c = table[c].prefix)
166 b = (byte) c;
167 }
168 goto add;
169 }
170 top:if (code_size > bits_left) {
171 if (bytes_left == 0) {
172 if (p == rlimit)
173 goto out;
174 bytes_left = *++p;
175 if_debug1('W', "[W]block count %d\n", bytes_left);
176 if (bytes_left == 0) {
177 status = EOFC;
178 goto out;
179 }
180 goto top;
181 }
182 if (low_order)
183 code = bits >> (8 - bits_left);
184 else
185 code = (uint) bits << (code_size - bits_left);
186 if (bits_left + 8 < code_size) { /* Need 2 more data bytes */
187 if (bytes_left == 1) {
188 if (rlimit - p < 3)
189 goto out;
190 bytes_left = p[2];
191 if_debug1('W', "[W]block count %d\n",
192 bytes_left);
193 if (bytes_left == 0) {
194 status = EOFC;
195 goto out;
196 }
197 bytes_left++;
198 bits = p[1];
199 p++;
200 } else {
201 if (rlimit - p < 2)
202 goto out;
203 bits = p[1];
204 }
205 if (low_order)
206 code += (uint) bits << bits_left;
207 else
208 code += (uint) bits << (code_size - 8 - bits_left);
209 bits_left += 8;
210 bits = p[2];
211 p += 2;
212 bytes_left -= 2;
213 } else {
214 if (p == rlimit)
215 goto out;
216 bits = *++p;
217 bytes_left--;
218 }
219 if (low_order)
220 code += (uint) bits << bits_left,
221 bits_left += 8 - code_size;
222 else
223 bits_left += 8 - code_size,
224 code += bits >> bits_left;
225 } else {
226 if (low_order)
227 code = bits >> (8 - bits_left),
228 bits_left -= code_size;
229 else
230 bits_left -= code_size,
231 code = bits >> bits_left;
232 }
233 code &= code_mask;
234 if_debug2('W', "[W]reading 0x%x,%d\n", code, code_size);
235 /*
236 * There is an anomalous case where a code S is followed
237 * immediately by another occurrence of the S string.
238 * In this case, the next available code will be defined as
239 * S followed by the first character of S, and will be
240 * emitted immediately after the code S. We have to
241 * recognize this case specially, by noting that the code is
242 * equal to next_code.
243 */
244 if (code >= next_code) {
245 if (code > next_code) {
246 #ifdef DEBUG
247 lprintf2("[W]code = %d > next_code = %d\n",
248 code, next_code);
249 #endif
250 status = ERRC;
251 goto out;
252 }
253 /* Fabricate the entry for the code. It will be */
254 /* overwritten immediately, of course. */
255 for (c = prev_code; c != eod; c = table[c].prefix)
256 dc_next->datum = c;
257 len = prev_len + 1;
258 dc_next->len = min(len, 255);
259 dc_next->prefix = prev_code;
260 if_debug3('w', "[w]decoding anomalous 0x%x=0x%x+%c\n",
261 next_code, prev_code, dc_next->datum);
262 }
263 /* See if there is enough room for the code. */
264 reset:
265 len = table[code].len;
266 if (len == 255) { /* Check for special code (reset or end). */
267 /* We set their lengths to 255 to avoid doing */
268 /* an extra check in the normal case. */
269 if (code == code_reset) {
270 if_debug1('w', "[w]reset: next_code was %d\n",
271 next_code);
272 next_code = code_0;
273 dc_next = table + code_0;
274 code_size = ss->InitialCodeLength + 1;
275 set_code_size();
276 prev_code = -1;
277 goto top;
278 } else if (code == eod) {
279 status = EOFC;
280 goto out;
281 }
282 /* The code length won't fit in a byte, */
283 /* compute it the hard way. */
284 for (c = code, len = 0; c != eod; len++)
285 c = table[c].prefix;
286 if_debug2('w', "[w]long code %d, length=%d\n", code, len);
287 }
288 if (wlimit - q < len) {
289 ss->copy_code = code;
290 ss->copy_left = ss->copy_len = len;
291 status = 1;
292 goto out;
293 }
294 /* Copy the string to the buffer (back to front). */
295 /* Optimize for short codes, which are the most frequent. */
296 dc = &table[code];
297 switch (len) {
298 default:
299 {
300 byte *q1 = q += len;
301
302 c = code;
303 do {
304 *q1-- = (dc = &table[c])->datum;
305 }
306 while ((c = dc->prefix) != eod);
307 b = q1[1];
308 }
309 break;
310 case 3:
311 q[3] = dc->datum;
312 dc = &table[dc->prefix];
313 case 2:
314 q[2] = dc->datum;
315 dc = &table[dc->prefix];
316 case 1:
317 q[1] = b = dc->datum;
318 q += len;
319 }
320 add: /* Add a new entry to the table */
321 if (prev_code >= 0) {
322 /*
323 * Unfortunately, we have to check for next_code ==
324 * lzw_decode_max every time: just checking at power
325 * of 2 boundaries stops us one code too soon.
326 */
327 if (next_code == lzw_decode_max) {
328 /*
329 * A few anomalous files have one data item too many before the
330 * reset code. We think this is a bug in the application that
331 * produced the files, but Acrobat accepts the files, so we do
332 * too.
333 */
334 if (!ss->BlockData) { /* don't do this for GIF */
335 if (bits_left < 8 && p >= rlimit && last) {
336 /* We're at EOD. */
337 goto out;
338 }
339 if (bits_left + ((rlimit - p) << 3) < code_size) {
340 /*
341 * We need more data to decide whether a reset is next.
342 * Return an error if we cannot get more.
343 */
344 if (last)
345 status = ERRC;
346 goto out;
347 }
348 if (low_order) {
349 code = bits >> (8 - bits_left);
350 code += (bits = *++p) << bits_left;
351 if (bits_left + 8 < code_size)
352 code += (bits = *++p) << (bits_left + 8);
353 } else {
354 code = bits & ((1 << bits_left) - 1);
355 code = (code << 8) + (bits = *++p);
356 if (bits_left + 8 < code_size)
357 code = (code << 8) + (bits = *++p);
358 code >>= (bits_left - code_size) & 7;
359 }
360 bits_left = (bits_left - code_size) & 7;
361 if (code == code_reset)
362 goto reset;
363 }
364 status = ERRC;
365 goto out;
366 }
367 dc_next->datum = b; /* added char of string */
368 dc_next->len = min(prev_len, 254) + 1;
369 dc_next->prefix = prev_code;
370 dc_next++;
371 if_debug4('W', "[W]adding 0x%x=0x%x+%c(%d)\n",
372 next_code, prev_code, b, min(len, 255));
373 if (++next_code == switch_code) { /* Crossed a power of 2. */
374 /* We have to make a strange special check for */
375 /* reaching the end of the code space. */
376 if (next_code < lzw_decode_max - 1) {
377 code_size++;
378 set_code_size();
379 if_debug2('w', "[w]crossed power of 2: new code_size=%d, next_code=%d\n",
380 code_size, next_code);
381 }
382 }
383 }
384 prev_code = code;
385 prev_len = len;
386 goto top;
387 out:pr->ptr = p;
388 pw->ptr = q;
389 ss->code_size = code_size;
390 ss->prev_code = prev_code;
391 ss->prev_len = prev_len;
392 ss->bits = bits;
393 ss->bits_left = bits_left;
394 ss->bytes_left = bytes_left;
395 ss->next_code = next_code;
396 if_debug3('w', "[w]decoded %d bytes, prev_code=%d, next_code=%d\n",
397 (int)(q - q0), prev_code, next_code);
398 return status;
399 }
400
401 /* Stream template */
402 const stream_template s_LZWD_template =
403 {&st_LZW_state, s_LZWD_init, s_LZWD_process, 3, 1, s_LZW_release,
404 s_LZW_set_defaults, s_LZWD_reset
405 };
406