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