1 /* Copyright (C) 1993 Aladdin Enterprises. All rights reserved.
2
3 This file is part of Aladdin Ghostscript.
4
5 Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND. No author
6 or distributor accepts any responsibility for the consequences of using it,
7 or for whether it serves any particular purpose or works at all, unless he
8 or she says so in writing. Refer to the Aladdin Ghostscript Free Public
9 License (the "License") for full details.
10
11 Every copy of Aladdin Ghostscript must include a copy of the License,
12 normally in a plain ASCII text file named PUBLIC. The License grants you
13 the right to copy, modify and redistribute Aladdin Ghostscript, but only
14 under certain conditions described in the License. Among other things, the
15 License requires that the copyright notice and this notice be preserved on
16 all copies.
17 */
18
19 /* $Id: slzwe.c,v 1.4 2005/04/04 23:00:24 igor Exp $ */
20 /* LZW encoding filter */
21 #include "stdio_.h" /* includes std.h */
22 #include "gdebug.h"
23 #include "strimpl.h"
24 #include "slzwx.h"
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 */
33 #define code_reset 256
34 #define code_eod 257
35 #define code_0 258 /* first assignable code */
36
37 /* Import the stream closing procedure */
38 extern stream_proc_release(s_LZW_release);
39
40 typedef struct lzw_encode_s {
41 byte datum; /* last byte of this code */
42 ushort prefix; /* code for prefix of this code */
43 } lzw_encode;
44
45 #define encode_max 4095 /* max # of codes, must be */
46 /* > code_0 and <= 4095 */
47 #define hash_size (encode_max + encode_max / 4)
48
49 struct lzw_encode_table_s {
50 lzw_encode encode[encode_max];
51 ushort hashed[hash_size];
52 };
53 gs_private_st_simple(st_lzwe_table, lzw_encode_table, "lzw_encode_table");
54
55 /* Hashing function */
56 #define encode_hash(code, chr)\
57 ((uint)((code) * 59 + (chr) * ((hash_size / 256) | 1)) % hash_size)
58
59 /* Internal routine to put a code into the output buffer. */
60 /* Let S = ss->code_size, M = ss->next_code, N = 1 << M. */
61 /* Relevant invariants: 9 <= S <= 12; N / 2 <= M < N; 0 <= code < N; */
62 /* 1 <= ss->bits_left <= 8; only the rightmost (8 - ss->bits_left) */
63 /* bits of ss->bits contain valid data. */
64 private byte *
lzw_put_code(register stream_LZW_state * ss,byte * q,uint code)65 lzw_put_code(register stream_LZW_state *ss, byte *q, uint code)
66 { uint size = ss->code_size;
67 byte cb = (ss->bits << ss->bits_left) +
68 (code >> (size - ss->bits_left));
69 if_debug2('W', "[w]writing 0x%x,%d\n", code, ss->code_size);
70 *++q = cb;
71 if ( (ss->bits_left += 8 - size) <= 0 )
72 { *++q = code >> -ss->bits_left;
73 ss->bits_left += 8;
74 }
75 ss->bits = code;
76 return q;
77 }
78
79 /* Internal routine to reset the encoding table */
80 private void
lzw_reset_encode(stream_LZW_state * ss)81 lzw_reset_encode(stream_LZW_state *ss)
82 { register int c;
83 lzw_encode_table *table = ss->table.encode;
84 ss->next_code = code_0;
85 ss->code_size = 9;
86 ss->prev_code = code_eod;
87 for ( c = 0; c < hash_size; c++ )
88 table->hashed[c] = code_eod;
89 for ( c = 0; c < 256; c++ )
90 { lzw_encode *ec = &table->encode[c];
91 register ushort *tc = &table->hashed[encode_hash(code_eod, c)];
92 while ( *tc != code_eod )
93 if ( ++tc == &table->hashed[hash_size] )
94 tc = &table->hashed[0];
95 *tc = c;
96 ec->datum = c, ec->prefix = code_eod;
97 }
98 table->encode[code_eod].prefix = code_reset; /* guarantee no match */
99 }
100
101 #define ss ((stream_LZW_state *)st)
102
103 /* Initialize LZWEncode filter */
104 private int
s_LZWE_init(stream_state * st)105 s_LZWE_init(stream_state *st)
106 { ss->bits_left = 8;
107 ss->table.encode = gs_alloc_struct(st->memory,
108 lzw_encode_table, &st_lzwe_table, "LZWEncode init");
109 if ( ss->table.encode == 0 )
110 return ERRC; /****** WRONG ******/
111 ss->first = true;
112 lzw_reset_encode(ss);
113 return 0;
114 }
115
116 /* Process a buffer */
117 private int
s_LZWE_process(stream_state * st,stream_cursor_read * pr,stream_cursor_write * pw,bool last)118 s_LZWE_process(stream_state *st, stream_cursor_read *pr,
119 stream_cursor_write *pw, bool last)
120 { register const byte *p = pr->ptr;
121 const byte *rlimit = pr->limit;
122 register byte *q = pw->ptr;
123 byte *wlimit = pw->limit;
124 int code = ss->prev_code;
125 lzw_encode_table *table = ss->table.encode;
126 ushort *table_end = &table->hashed[hash_size];
127 int status = 0;
128 int limit_code;
129 #define set_limit_code()\
130 limit_code = (1 << ss->code_size) - ss->EarlyChange;\
131 if ( limit_code > encode_max ) limit_code = encode_max
132 set_limit_code();
133 if ( ss->first )
134 { /* Emit the initial reset code. */
135 if ( wlimit - q < 2 )
136 return 1;
137 q = lzw_put_code(ss, q, code_reset);
138 ss->first = false;
139 }
140 while ( p < rlimit )
141 { byte c = p[1];
142 ushort *tp;
143 for ( tp = &table->hashed[encode_hash(code, c)]; ; )
144 { lzw_encode *ep = &table->encode[*tp];
145 if ( ep->prefix == code && ep->datum == c )
146 { code = *tp;
147 p++;
148 break;
149 }
150 else if ( *tp != code_eod )
151 { if ( ++tp == table_end )
152 tp = &table->hashed[0]; /* wrap around */
153 }
154 else
155 { /* end of recognized sequence */
156 if ( wlimit - q <= 4 )
157 { status = 1;
158 goto out;
159 }
160 q = lzw_put_code(ss, q, code);
161 if ( ss->next_code == limit_code )
162 { /* Reached power of 2 or limit. */
163 /* Determine which. */
164 if ( ss->next_code == encode_max )
165 { q = lzw_put_code(ss, q, code_reset);
166 lzw_reset_encode(ss);
167 set_limit_code();
168 goto cx;
169 }
170 ss->code_size++;
171 set_limit_code();
172 }
173 if_debug3('W', "[W]encoding 0x%x=0x%x+%c\n",
174 ss->next_code, code, c);
175 *tp = ss->next_code++;
176 ep = &table->encode[*tp];
177 ep->datum = c;
178 ep->prefix = code;
179 cx: code = code_eod;
180 break;
181 }
182 }
183 }
184 if ( last && status == 0 )
185 { if ( wlimit - q < 4 )
186 status = 1;
187 else
188 { if ( code != code_eod )
189 { q = lzw_put_code(ss, q, code); /* put out final code */
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