1 /* Copyright (C) 2001-2019 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., 1305 Grant Avenue - Suite 200, Novato,
13 CA 94945, 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 bool old_tiff = ss->OldTiff;
121 uint len;
122 int c;
123 byte b;
124 byte *q1;
125
126 if_debug2m('w', ss->memory, "[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_debug3m('W', ss->memory, "[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_debug1m('W', ss->memory, "[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_debug1m('W', ss->memory, "[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_debug2m('W', ss->memory, "[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) || (prev_code < 0)) {
246 #ifdef DEBUG
247 mlprintf3(ss->memory, "[W]code = %d > next_code = %d or prev_code = %d < 0\n",
248 code, next_code, prev_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_debug3m('w', ss->memory, "[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_debug1m('w', ss->memory, "[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_debug2m('w', ss->memory, "[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 (!old_tiff && 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 if (next_code < lzw_decode_max) {
368 dc_next->datum = b; /* added char of string */
369 dc_next->len = min(prev_len, 254) + 1;
370 dc_next->prefix = prev_code;
371 dc_next++;
372 if_debug4m('W', ss->memory, "[W]adding 0x%x=0x%x+%c(%d)\n",
373 next_code, prev_code, b, min(len, 255));
374 }
375 if (++next_code == switch_code) { /* Crossed a power of 2. */
376 /* We have to make a strange special check for */
377 /* reaching the end of the code space. */
378 if (next_code < lzw_decode_max - 1) {
379 code_size++;
380 set_code_size();
381 if_debug2m('w', ss->memory, "[w]crossed power of 2: new code_size=%d, next_code=%d\n",
382 code_size, next_code);
383 }
384 }
385 }
386 prev_code = code;
387 prev_len = len;
388 goto top;
389 out:pr->ptr = p;
390 pw->ptr = q;
391 ss->code_size = code_size;
392 ss->prev_code = prev_code;
393 ss->prev_len = prev_len;
394 ss->bits = bits;
395 ss->bits_left = bits_left;
396 ss->bytes_left = bytes_left;
397 ss->next_code = next_code;
398 if_debug3m('w', ss->memory, "[w]decoded %d bytes, prev_code=%d, next_code=%d\n",
399 (int)(q - q0), prev_code, next_code);
400 return status;
401 }
402
403 /* Stream template */
404 const stream_template s_LZWD_template =
405 {&st_LZW_state, s_LZWD_init, s_LZWD_process, 3, 1, s_LZW_release,
406 s_LZW_set_defaults, s_LZWD_reset
407 };
408