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 encoding filter */
18 #include "stdio_.h" /* includes std.h */
19 #include "gdebug.h"
20 #include "strimpl.h"
21 #include "slzwx.h"
22
23 /********************************************************/
24 /* LZW routines are based on: */
25 /* Dr. Dobbs Journal --- Oct. 1989. */
26 /* Article on LZW Data Compression by Mark R. Nelson */
27 /********************************************************/
28
29 /* Define the special codes */
30 #define code_reset 256
31 #define code_eod 257
32 #define code_0 258 /* first assignable code */
33
34 /* Import the stream closing procedure */
35 extern stream_proc_release(s_LZW_release);
36
37 typedef struct lzw_encode_s {
38 byte datum; /* last byte of this code */
39 ushort prefix; /* code for prefix of this code */
40 } lzw_encode;
41
42 #define encode_max 4095 /* max # of codes, must be */
43 /* > code_0 and <= 4095 */
44 #define hash_size (encode_max + encode_max / 4)
45
46 struct lzw_encode_table_s {
47 lzw_encode encode[encode_max];
48 ushort hashed[hash_size];
49 };
50 gs_private_st_simple(st_lzwe_table, lzw_encode_table, "lzw_encode_table");
51
52 /* Hashing function */
53 #define encode_hash(code, chr)\
54 ((uint)((code) * 59 + (chr) * ((hash_size / 256) | 1)) % hash_size)
55
56 /* Internal routine to put a code into the output buffer. */
57 /* Let S = ss->code_size, M = ss->next_code, N = 1 << M. */
58 /* Relevant invariants: 9 <= S <= 12; N / 2 <= M < N; 0 <= code < N; */
59 /* 1 <= ss->bits_left <= 8; only the rightmost (8 - ss->bits_left) */
60 /* bits of ss->bits contain valid data. */
61 static byte *
lzw_put_code(register stream_LZW_state * ss,byte * q,uint code)62 lzw_put_code(register stream_LZW_state *ss, byte *q, uint code)
63 { uint size = ss->code_size;
64 byte cb = (ss->bits << ss->bits_left) +
65 (code >> (size - ss->bits_left));
66 if_debug2('W', "[w]writing 0x%x,%d\n", code, ss->code_size);
67 *++q = cb;
68 if ( (ss->bits_left += 8 - size) <= 0 )
69 { *++q = code >> -ss->bits_left;
70 ss->bits_left += 8;
71 }
72 ss->bits = code;
73 return q;
74 }
75
76 /* Internal routine to reset the encoding table */
77 static void
lzw_reset_encode(stream_LZW_state * ss)78 lzw_reset_encode(stream_LZW_state *ss)
79 { register int c;
80 lzw_encode_table *table = ss->table.encode;
81 ss->next_code = code_0;
82 ss->code_size = 9;
83 ss->prev_code = code_eod;
84 for ( c = 0; c < hash_size; c++ )
85 table->hashed[c] = code_eod;
86 for ( c = 0; c < 256; c++ )
87 { lzw_encode *ec = &table->encode[c];
88 register ushort *tc = &table->hashed[encode_hash(code_eod, c)];
89 while ( *tc != code_eod )
90 if ( ++tc == &table->hashed[hash_size] )
91 tc = &table->hashed[0];
92 *tc = c;
93 ec->datum = c, ec->prefix = code_eod;
94 }
95 table->encode[code_eod].prefix = code_reset; /* guarantee no match */
96 }
97
98 #define ss ((stream_LZW_state *)st)
99
100 /* Initialize LZWEncode filter */
101 static int
s_LZWE_init(stream_state * st)102 s_LZWE_init(stream_state *st)
103 { ss->bits_left = 8;
104 ss->bits = 0; /* for Purify, the value unimportant due to ss->bits_left == 8 */
105 ss->table.encode = gs_alloc_struct(st->memory,
106 lzw_encode_table, &st_lzwe_table, "LZWEncode init");
107 if ( ss->table.encode == 0 )
108 return ERRC; /****** WRONG ******/
109 ss->first = true;
110 lzw_reset_encode(ss);
111 return 0;
112 }
113
114 /* Process a buffer */
115 static int
s_LZWE_process(stream_state * st,stream_cursor_read * pr,stream_cursor_write * pw,bool last)116 s_LZWE_process(stream_state *st, stream_cursor_read *pr,
117 stream_cursor_write *pw, bool last)
118 { register const byte *p = pr->ptr;
119 const byte *rlimit = pr->limit;
120 register byte *q = pw->ptr;
121 byte *wlimit = pw->limit;
122 int code = ss->prev_code;
123 lzw_encode_table *table = ss->table.encode;
124 ushort *table_end = &table->hashed[hash_size];
125 int status = 0;
126 int limit_code;
127 #define set_limit_code()\
128 limit_code = (1 << ss->code_size) - ss->EarlyChange;\
129 if ( limit_code > encode_max ) limit_code = encode_max
130 set_limit_code();
131 if ( ss->first )
132 { /* Emit the initial reset code. */
133 if ( wlimit - q < 2 )
134 return 1;
135 q = lzw_put_code(ss, q, code_reset);
136 ss->first = false;
137 }
138 while ( p < rlimit )
139 { byte c = p[1];
140 ushort *tp;
141 for ( tp = &table->hashed[encode_hash(code, c)]; ; )
142 { lzw_encode *ep = &table->encode[*tp];
143 if ( ep->prefix == code && ep->datum == c )
144 { code = *tp;
145 p++;
146 break;
147 }
148 else if ( *tp != code_eod )
149 { if ( ++tp == table_end )
150 tp = &table->hashed[0]; /* wrap around */
151 }
152 else
153 { /* end of recognized sequence */
154 if ( wlimit - q <= 4 )
155 { status = 1;
156 goto out;
157 }
158 q = lzw_put_code(ss, q, code);
159 if ( ss->next_code == limit_code )
160 { /* Reached power of 2 or limit. */
161 /* Determine which. */
162 if ( ss->next_code == encode_max )
163 { q = lzw_put_code(ss, q, code_reset);
164 lzw_reset_encode(ss);
165 set_limit_code();
166 goto cx;
167 }
168 ss->code_size++;
169 set_limit_code();
170 }
171 if_debug3('W', "[W]encoding 0x%x=0x%x+%c\n",
172 ss->next_code, code, c);
173 *tp = ss->next_code++;
174 ep = &table->encode[*tp];
175 ep->datum = c;
176 ep->prefix = code;
177 cx: code = code_eod;
178 break;
179 }
180 }
181 }
182 if ( last && status == 0 )
183 { if ( wlimit - q < 4 )
184 status = 1;
185 else
186 { if ( code != code_eod )
187 { q = lzw_put_code(ss, q, code); /* put out final code */
188 if (ss->next_code == limit_code && ss->next_code != encode_max)
189 ss->code_size++;
190 }
191 q = lzw_put_code(ss, q, code_eod);
192 if ( ss->bits_left < 8 )
193 *++q = ss->bits << ss->bits_left; /* final byte */
194 }
195 }
196 out: ss->prev_code = code;
197 pr->ptr = p;
198 pw->ptr = q;
199 return status;
200 }
201
202 #undef ss
203
204 /* Stream template */
205 const stream_template s_LZWE_template =
206 { &st_LZW_state, s_LZWE_init, s_LZWE_process, 1, 4, s_LZW_release,
207 s_LZW_set_defaults
208 };
209