1 : /* -*- mode: C -*-
2 : *
3 : * File: pdf-stm-f-lzw.c
4 : * Date: Wed Aug 15 14:41:18 2007
5 : *
6 : * GNU PDF Library - LZW encoder/decoder filter
7 : *
8 : */
9 :
10 : /* Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. */
11 :
12 : /* This program is free software: you can redistribute it and/or modify
13 : * it under the terms of the GNU General Public License as published by
14 : * the Free Software Foundation, either version 3 of the License, or
15 : * (at your option) any later version.
16 : *
17 : * This program is distributed in the hope that it will be useful,
18 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 : * GNU General Public License for more details.
21 : *
22 : * You should have received a copy of the GNU General Public License
23 : * along with this program. If not, see <http://www.gnu.org/licenses/>.
24 : */
25 :
26 : #include <config.h>
27 :
28 : #include <string.h>
29 :
30 : #include <pdf-alloc.h>
31 : #include <pdf-hash-helper.h>
32 : #include <pdf-stm-f-lzw.h>
33 :
34 : #define LZW_DEFAULT_EARLY_CHANGE 1
35 :
36 : #define LZW_CACHE_SIZE (sizeof (lzw_code_t) << 3)
37 : #define LZW_MIN_BITSIZE 9
38 : #define LZW_MAX_BITSIZE 12
39 : #define LZW_MAX_DICTSIZE (1 << LZW_MAX_BITSIZE)
40 : #define LZW_NULL_INDEX ~0U
41 :
42 : enum lzw_special_codes_e
43 : {
44 : LZW_RESET_CODE = 256,
45 : LZW_EOD_CODE,
46 : LZW_FIRST_CODE
47 : };
48 :
49 : typedef unsigned lzw_code_t;
50 : #define LZW_CODE_SIZE (sizeof (lzw_code_t) << 3)
51 :
52 : /* -- LZW code output/input -- */
53 : /*
54 : * Object to read and write codes of variable bitsize in a buffer.
55 : * Warning: using both get and put functions may break the buffer.
56 : */
57 : struct lzw_buffer_s
58 : {
59 : pdf_buffer_t buf;
60 : pdf_char_t cache [LZW_CACHE_SIZE];
61 : pdf_size_t cache_rp;
62 : pdf_size_t cache_wp;
63 : lzw_code_t valbuf;
64 : lzw_code_t maxval;
65 : int bitsize;
66 : int valbits;
67 : };
68 : typedef struct lzw_buffer_s* lzw_buffer_t;
69 :
70 : static void
71 : lzw_buffer_init (lzw_buffer_t b,
72 : int bitsize)
73 : {
74 2 : b->buf = NULL;
75 2 : b->valbuf = 0;
76 2 : b->valbits = 0;
77 2 : b->bitsize = bitsize;
78 2 : b->maxval = (1 << bitsize) - 1;
79 2 : b->cache_wp = 0;
80 2 : b->cache_rp = 0;
81 : }
82 :
83 : static void
84 : lzw_buffer_set (lzw_buffer_t b,
85 : pdf_buffer_t buf)
86 : {
87 58 : b->buf = buf;
88 : }
89 :
90 : static pdf_status_t
91 : lzw_buffer_get_code (lzw_buffer_t b,
92 : lzw_code_t* code,
93 : pdf_bool_t finish_p)
94 30 : {
95 : lzw_code_t r;
96 :
97 69 : while (b->valbits <= LZW_CODE_SIZE - 8 && !finish_p)
98 : {
99 31 : if (pdf_buffer_eob_p (b->buf))
100 : {
101 22 : return PDF_ENINPUT;
102 : }
103 : else
104 : {
105 9 : b->valbuf |=
106 : (lzw_code_t) b->buf->data [b->buf->rp++]
107 : << (LZW_CODE_SIZE - 8 - b->valbits);
108 :
109 9 : b->valbits += 8;
110 : }
111 : }
112 :
113 8 : if (b->valbits < b->bitsize)
114 : {
115 0 : return PDF_EEOF;
116 : }
117 :
118 8 : r = b->valbuf >> (LZW_CODE_SIZE - b->bitsize);
119 8 : b->valbuf <<= b->bitsize;
120 8 : b->valbits -= b->bitsize;
121 :
122 8 : *code = r;
123 :
124 8 : return PDF_OK;
125 : }
126 :
127 : /* Once finished, call with 0 as code value to flush the buffer. */
128 : static void
129 : lzw_buffer_put_code (lzw_buffer_t b,
130 : lzw_code_t code)
131 9 : {
132 9 : b->valbuf |= (lzw_code_t) code << (LZW_CODE_SIZE - b->bitsize - b->valbits);
133 9 : b->valbits += b->bitsize;
134 :
135 28 : while (b->valbits >= 8)
136 : {
137 10 : if (pdf_buffer_full_p (b->buf))
138 : {
139 3 : b->cache [b->cache_wp++] =
140 : (pdf_char_t) (b->valbuf >> (LZW_CODE_SIZE - 8));
141 : }
142 : else
143 : {
144 7 : b->buf->data [b->buf->wp++] =
145 : (pdf_char_t) (b->valbuf >> (LZW_CODE_SIZE - 8));
146 : }
147 10 : b->valbuf <<= 8;
148 10 : b->valbits -= 8;
149 : }
150 9 : }
151 :
152 : static pdf_status_t
153 : lzw_buffer_flush (lzw_buffer_t b)
154 : {
155 34 : while (b->cache_rp != b->cache_wp &&
156 : !pdf_buffer_full_p (b->buf))
157 : {
158 3 : b->buf->data [b->buf->wp++] = b->cache [b->cache_rp++];
159 : }
160 :
161 31 : if (pdf_buffer_full_p (b->buf))
162 : {
163 3 : return PDF_ENOUTPUT;
164 : }
165 :
166 28 : b->cache_wp = 0;
167 28 : b->cache_rp = 0;
168 :
169 28 : return PDF_OK;
170 : }
171 :
172 : static pdf_status_t
173 : lzw_buffer_inc_bitsize (lzw_buffer_t b)
174 : {
175 0 : if (b->bitsize == LZW_MAX_BITSIZE)
176 : {
177 0 : return PDF_ERROR;
178 : }
179 :
180 0 : ++b->bitsize;
181 0 : b->maxval = (1 << b->bitsize) - 1;
182 :
183 0 : return PDF_OK;
184 : }
185 :
186 : static void
187 : lzw_buffer_set_bitsize (lzw_buffer_t b,
188 : int newsize)
189 : {
190 1 : b->bitsize = newsize;
191 1 : b->maxval = (1 << newsize) - 1;
192 : }
193 :
194 : /* -- LZW dictionary handler -- */
195 :
196 : /*
197 : * The strings are stored in a non balanced ordered binary tree.
198 : */
199 : struct lzw_string_s
200 : {
201 : lzw_code_t prefix; /* Prefix string code */
202 : pdf_char_t suffix; /* Appended character */
203 :
204 : lzw_code_t first; /* First string with the same prefix. */
205 : lzw_code_t left; /* Next string with smaller suffix and same prefix. */
206 : lzw_code_t right; /* Next string with greater suffix and same prefix. */
207 : };
208 :
209 : typedef struct lzw_string_s* lzw_string_t;
210 :
211 : static void
212 : lzw_string_init (lzw_string_t s)
213 : {
214 1 : memset (s, 0xFF, sizeof (struct lzw_string_s));
215 : }
216 :
217 : struct lzw_dict_s
218 : {
219 : struct lzw_string_s table [LZW_MAX_DICTSIZE];
220 : pdf_size_t size;
221 : };
222 : typedef struct lzw_dict_s* lzw_dict_t;
223 :
224 : static void
225 : lzw_dict_init (lzw_dict_t d)
226 : {
227 : int i;
228 :
229 3 : memset (d->table,
230 : 0xFF,
231 : sizeof (struct lzw_string_s) * LZW_MAX_DICTSIZE);
232 :
233 777 : for (i = 0; i < LZW_FIRST_CODE; i++)
234 : {
235 774 : d->table[i].suffix = (pdf_char_t) (i & 0xFF);
236 : }
237 :
238 3 : d->size = LZW_FIRST_CODE;
239 : }
240 :
241 : static pdf_bool_t
242 : lzw_dict_add (lzw_dict_t d,
243 : lzw_string_t s)
244 : {
245 : lzw_code_t index;
246 : pdf_bool_t must_add;
247 :
248 10 : if (s->prefix == LZW_NULL_INDEX)
249 : {
250 1 : s->prefix = s->suffix;
251 1 : return PDF_FALSE; /* The string is a basic character, found! */
252 : }
253 :
254 9 : index = d->table[s->prefix].first;
255 :
256 9 : if (index == LZW_NULL_INDEX)
257 : {
258 4 : d->table[s->prefix].first = d->size;
259 : }
260 : else
261 : {
262 5 : must_add = PDF_FALSE;
263 6 : while (!must_add)
264 : {
265 5 : if (s->suffix == d->table[index].suffix)
266 : {
267 4 : s->prefix = index;
268 4 : return PDF_FALSE; /* The string is already in the table, found! */
269 : }
270 1 : else if (s->suffix < d->table[index].suffix)
271 : {
272 0 : if (d->table[index].left == LZW_NULL_INDEX)
273 : {
274 0 : d->table[index].left = d->size;
275 0 : must_add = PDF_TRUE;
276 : }
277 : else
278 : {
279 0 : index = d->table[index].left;
280 : }
281 : }
282 : else
283 : {
284 1 : if (d->table[index].right == LZW_NULL_INDEX)
285 : {
286 1 : d->table[index].right = d->size;
287 1 : must_add = PDF_TRUE;
288 : }
289 : else
290 : {
291 0 : index = d->table[index].right;
292 : }
293 : }
294 : }
295 : }
296 :
297 5 : d->table[d->size++] = *s;
298 :
299 5 : return PDF_TRUE;
300 : }
301 :
302 : static void
303 : lzw_dict_reset (lzw_dict_t dict)
304 : {
305 : lzw_dict_init (dict);
306 : }
307 :
308 : static void
309 : lzw_dict_fast_add (lzw_dict_t d,
310 : lzw_code_t prefix,
311 : pdf_char_t suffix)
312 : {
313 5 : d->table[d->size].prefix = prefix;
314 5 : d->table[d->size].suffix = suffix;
315 5 : d->size++;
316 : }
317 :
318 : static void
319 : lzw_dict_decode (lzw_dict_t d,
320 : lzw_code_t code,
321 : pdf_char_t** decode,
322 : pdf_size_t* size)
323 : {
324 5 : *size = 0;
325 :
326 : do
327 : {
328 8 : *(*decode)-- = d->table[code].suffix;
329 8 : ++(*size);
330 8 : code = d->table[code].prefix;
331 : }
332 8 : while (code != LZW_NULL_INDEX);
333 :
334 5 : (*decode)++;
335 : }
336 :
337 : /* -- THE ENCODER -- */
338 :
339 : struct lzwenc_state_s
340 : {
341 : /* cached params */
342 : pdf_i32_t early_change;
343 :
344 : /* encoding state */
345 : pdf_bool_t must_reset_p;
346 : struct lzw_buffer_s buffer;
347 : struct lzw_dict_s dict;
348 : struct lzw_string_s string;
349 :
350 : pdf_bool_t really_finish_p;
351 : };
352 : typedef struct lzwenc_state_s* lzwenc_state_t;
353 :
354 : pdf_status_t
355 : pdf_stm_f_lzwenc_init (pdf_hash_t params,
356 : void **ext_state)
357 1 : {
358 : pdf_char_t *early_change_str;
359 : lzwenc_state_t state;
360 :
361 1 : state = pdf_alloc (sizeof (struct lzwenc_state_s));
362 1 : if (!state)
363 : {
364 0 : return PDF_ERROR;
365 : }
366 :
367 1 : state->early_change = 1; /* set default */
368 :
369 1 : if (pdf_hash_key_p (params, "EarlyChange") == PDF_TRUE)
370 : {
371 0 : pdf_hash_get_string (params, "EarlyChange", &early_change_str);
372 0 : if (early_change_str[0] == '0')
373 : {
374 0 : state->early_change = 0;
375 : }
376 : }
377 :
378 1 : lzw_buffer_init (&state->buffer, LZW_MIN_BITSIZE);
379 1 : lzw_dict_init (&state->dict);
380 1 : lzw_string_init (&state->string);
381 1 : state->must_reset_p = PDF_TRUE;
382 1 : state->really_finish_p = PDF_FALSE;
383 :
384 1 : *ext_state = state;
385 1 : return PDF_OK;
386 : }
387 :
388 : pdf_status_t
389 : pdf_stm_f_lzwenc_apply (pdf_hash_t params,
390 : void *ext_state,
391 : pdf_buffer_t in,
392 : pdf_buffer_t out,
393 : pdf_bool_t finish_p)
394 31 : {
395 : pdf_status_t ret;
396 : lzwenc_state_t st;
397 :
398 31 : ret = PDF_OK;
399 31 : st = ext_state;
400 31 : lzw_buffer_set (&st->buffer, out);
401 :
402 62 : ret = lzw_buffer_flush (&st->buffer);
403 31 : if (ret != PDF_OK)
404 : {
405 3 : return ret;
406 : }
407 :
408 28 : if (st->really_finish_p)
409 : {
410 1 : return PDF_EEOF;
411 : }
412 :
413 27 : if (st->must_reset_p)
414 : {
415 1 : lzw_buffer_put_code (&st->buffer, LZW_RESET_CODE);
416 1 : st->must_reset_p = PDF_FALSE;
417 : }
418 :
419 37 : while (!pdf_buffer_eob_p (in) &&
420 : !pdf_buffer_full_p (out))
421 : {
422 10 : st->string.suffix = in->data [in->rp++];
423 20 : if (lzw_dict_add (&st->dict, &st->string))
424 : {
425 5 : lzw_buffer_put_code (&st->buffer, st->string.prefix);
426 5 : st->string.prefix = st->string.suffix;
427 :
428 5 : if (st->buffer.maxval - st->early_change == st->dict.size)
429 : {
430 0 : if (!lzw_buffer_inc_bitsize(&st->buffer))
431 : {
432 0 : lzw_buffer_put_code (&st->buffer, LZW_RESET_CODE);
433 0 : lzw_buffer_set_bitsize (&st->buffer, LZW_MIN_BITSIZE);
434 0 : lzw_dict_reset (&st->dict);
435 : }
436 : }
437 : }
438 : }
439 :
440 27 : if (finish_p)
441 : {
442 1 : lzw_buffer_put_code (&st->buffer, st->string.prefix);
443 1 : if ((st->buffer.maxval - st->early_change) == st->dict.size)
444 : {
445 0 : lzw_buffer_inc_bitsize(&st->buffer);
446 : }
447 :
448 1 : lzw_buffer_put_code (&st->buffer, LZW_EOD_CODE);
449 1 : lzw_buffer_put_code (&st->buffer, 0); /* flush */
450 :
451 1 : if (pdf_buffer_full_p (out))
452 : {
453 1 : ret = PDF_ENOUTPUT;
454 : }
455 : else
456 : {
457 0 : ret = PDF_EEOF;
458 : }
459 :
460 1 : st->really_finish_p = PDF_TRUE;
461 : }
462 26 : else if (pdf_buffer_full_p (out))
463 : {
464 6 : ret = PDF_ENOUTPUT;
465 : }
466 20 : else if (pdf_buffer_eob_p (in))
467 : {
468 20 : ret = PDF_ENINPUT;
469 : }
470 :
471 27 : return ret;
472 : }
473 :
474 : pdf_status_t
475 : pdf_stm_f_lzwenc_dealloc_state (void *state)
476 1 : {
477 1 : pdf_dealloc (state);
478 1 : return PDF_OK;
479 : }
480 :
481 : /* -- THE DECODER -- */
482 :
483 : enum lzwdec_state
484 : {
485 : LZWDEC_STATE_START,
486 : LZWDEC_STATE_CLEAN,
487 : LZWDEC_STATE_WRITE,
488 : LZWDEC_STATE_READ,
489 : LZWDEC_STATE_LOOP_WRITE,
490 : LZWDEC_STATE_LOOP_READ
491 : };
492 :
493 : struct lzwdec_state_s
494 : {
495 : /* cached params */
496 : pdf_i32_t early_change;
497 :
498 : /* state */
499 : pdf_char_t dec_buf [LZW_MAX_DICTSIZE];
500 : pdf_char_t* decoded;
501 : pdf_size_t dec_size;
502 :
503 : lzw_code_t new_code;
504 : lzw_code_t old_code;
505 :
506 : /* flow managment */
507 : enum lzwdec_state state_pos;
508 : pdf_status_t tmp_ret;
509 :
510 : struct lzw_buffer_s buffer;
511 : struct lzw_dict_s dict;
512 : };
513 : typedef struct lzwdec_state_s* lzwdec_state_t;
514 :
515 :
516 : pdf_status_t
517 : pdf_stm_f_lzwdec_init (pdf_hash_t params,
518 : void **ext_state)
519 1 : {
520 : pdf_char_t *early_change_str;
521 : lzwdec_state_t state;
522 :
523 1 : state = pdf_alloc (sizeof (struct lzwdec_state_s));
524 1 : if (!state)
525 : {
526 0 : return PDF_ERROR;
527 : }
528 :
529 1 : state->early_change = 1; /* set default */
530 :
531 1 : if (pdf_hash_key_p (params, "EarlyChange") == PDF_TRUE)
532 : {
533 0 : pdf_hash_get_string (params, "EarlyChange", &early_change_str);
534 0 : if (early_change_str[0] == '0')
535 : {
536 0 : state->early_change = 0;
537 : }
538 : }
539 :
540 1 : lzw_buffer_init (&state->buffer, LZW_MIN_BITSIZE);
541 1 : lzw_dict_init (&state->dict);
542 1 : state->old_code = LZW_NULL_INDEX;
543 1 : state->decoded = state->dec_buf + (LZW_MAX_DICTSIZE-2);
544 1 : state->dec_size = 0;
545 1 : state->state_pos = LZWDEC_STATE_START;
546 1 : state->tmp_ret = 0;
547 :
548 1 : *ext_state = state;
549 1 : return PDF_OK;
550 : }
551 :
552 : pdf_status_t
553 : lzwdec_put_decoded (lzwdec_state_t st, pdf_buffer_t out)
554 9 : {
555 : pdf_status_t ret;
556 : pdf_size_t to_write;
557 :
558 9 : ret = PDF_OK;
559 :
560 9 : if (st->dec_size)
561 : {
562 : /* output the decoded string */
563 9 : to_write = st->dec_size;
564 9 : if (st->dec_size > (out->size - out->wp))
565 : {
566 4 : to_write = out->size - out->wp;
567 4 : ret = PDF_ENOUTPUT;
568 : }
569 :
570 9 : memcpy (out->data + out->wp, st->decoded, to_write);
571 9 : out->wp += to_write;
572 9 : st->decoded += to_write;
573 9 : st->dec_size -= to_write;
574 : }
575 :
576 9 : return ret;
577 : }
578 :
579 : pdf_status_t
580 : lzwdec_put_code (lzwdec_state_t st,
581 : pdf_buffer_t out,
582 : unsigned long code)
583 1 : {
584 1 : if (pdf_buffer_full_p (out))
585 : {
586 0 : return PDF_ENOUTPUT;
587 : }
588 :
589 1 : out->data [out->wp++] = (pdf_char_t) (code & 0xFF);
590 :
591 1 : return PDF_OK;
592 : }
593 :
594 : #define LZWDEC_CHECK(st, pos, what) \
595 : do { (st)->state_pos = (pos); \
596 : if (((st)->tmp_ret = (what)) != PDF_OK) \
597 : { return ((st)->tmp_ret); } \
598 : } while (0);
599 :
600 : pdf_status_t
601 : pdf_stm_f_lzwdec_apply (pdf_hash_t params,
602 : void *ext_state,
603 : pdf_buffer_t in,
604 : pdf_buffer_t out,
605 : pdf_bool_t finish_p)
606 27 : {
607 : lzwdec_state_t st;
608 :
609 27 : st = ext_state;
610 27 : lzw_buffer_set (&st->buffer, in);
611 :
612 27 : switch (st->state_pos)
613 : {
614 : case LZWDEC_STATE_START:
615 : break;
616 : case LZWDEC_STATE_CLEAN:
617 : goto lzwdec_state_clean;
618 : case LZWDEC_STATE_WRITE:
619 : goto lzwdec_state_write;
620 : case LZWDEC_STATE_READ:
621 : goto lzwdec_state_read;
622 : case LZWDEC_STATE_LOOP_WRITE:
623 : goto lzwdec_state_loop_write;
624 : case LZWDEC_STATE_LOOP_READ:
625 : goto lzwdec_state_loop_read;
626 : default:
627 : break;
628 : }
629 :
630 : do
631 : {
632 : /* need a reset */
633 1 : lzw_buffer_set_bitsize (&st->buffer, LZW_MIN_BITSIZE);
634 1 : lzw_dict_reset (&st->dict);
635 :
636 : do
637 : {
638 11 : lzwdec_state_clean:
639 11 : LZWDEC_CHECK (st, LZWDEC_STATE_CLEAN,
640 : lzw_buffer_get_code (&st->buffer, &st->new_code, finish_p));
641 : }
642 2 : while (st->new_code == LZW_RESET_CODE);
643 :
644 1 : if (st->new_code != LZW_EOD_CODE)
645 : {
646 1 : lzwdec_state_write:
647 1 : LZWDEC_CHECK (st, LZWDEC_STATE_WRITE,
648 : lzwdec_put_code (st, out, st->new_code));
649 :
650 1 : st->old_code = st->new_code;
651 4 : lzwdec_state_read:
652 4 : LZWDEC_CHECK (st, LZWDEC_STATE_READ,
653 : lzw_buffer_get_code (&st->buffer, &st->new_code, finish_p));
654 : }
655 :
656 6 : while (st->new_code != LZW_EOD_CODE &&
657 : st->new_code != LZW_RESET_CODE)
658 : {
659 5 : st->decoded = st->dec_buf + (LZW_MAX_DICTSIZE-2);
660 :
661 : /* Is new code in the dict? */
662 5 : if (st->new_code < st->dict.size)
663 : {
664 4 : lzw_dict_decode (&st->dict, st->new_code,
665 : &st->decoded, &st->dec_size);
666 4 : lzw_dict_fast_add (&st->dict, st->old_code, st->decoded[0]);
667 : }
668 : else
669 : {
670 1 : lzw_dict_decode (&st->dict, st->old_code,
671 : &st->decoded, &st->dec_size);
672 1 : lzw_dict_fast_add (&st->dict, st->old_code, st->decoded[0]);
673 1 : st->decoded [st->dec_size++] = st->decoded [0];
674 : }
675 :
676 : /* output the decoded string */
677 9 : lzwdec_state_loop_write:
678 9 : LZWDEC_CHECK (st, LZWDEC_STATE_LOOP_WRITE,
679 : lzwdec_put_decoded (st, out));
680 :
681 5 : if (st->dict.size == st->buffer.maxval - 1 - st->early_change)
682 : {
683 0 : if (!lzw_buffer_inc_bitsize (&st->buffer));
684 : /* break; We must wait for the reset code, don't reset yet. */
685 : }
686 :
687 : /* get next code */
688 5 : st->old_code = st->new_code;
689 15 : lzwdec_state_loop_read:
690 15 : LZWDEC_CHECK (st, LZWDEC_STATE_LOOP_READ,
691 : lzw_buffer_get_code (&st->buffer, &st->new_code, finish_p));
692 : }
693 : }
694 1 : while (st->new_code != LZW_EOD_CODE);
695 :
696 1 : st->state_pos = LZWDEC_STATE_START;
697 :
698 1 : return PDF_EEOF;
699 : }
700 :
701 : pdf_status_t
702 : pdf_stm_f_lzwdec_dealloc_state (void *state)
703 1 : {
704 1 : pdf_dealloc (state);
705 1 : return PDF_OK;
706 : }
707 :
708 : /* End of pdf_stm_f_lzw.c */
|
