1 |
/* $NetBSD: zopen.c,v 1.8 2003/08/07 11:13:29 agc Exp $ */ |
2 |
|
3 |
/*- |
4 |
* Copyright (c) 1985, 1986, 1992, 1993 |
5 |
* The Regents of the University of California. All rights reserved. |
6 |
* |
7 |
* This code is derived from software contributed to Berkeley by |
8 |
* Diomidis Spinellis and James A. Woods, derived from original |
9 |
* work by Spencer Thomas and Joseph Orost. |
10 |
* |
11 |
* Redistribution and use in source and binary forms, with or without |
12 |
* modification, are permitted provided that the following conditions |
13 |
* are met: |
14 |
* 1. Redistributions of source code must retain the above copyright |
15 |
* notice, this list of conditions and the following disclaimer. |
16 |
* 2. Redistributions in binary form must reproduce the above copyright |
17 |
* notice, this list of conditions and the following disclaimer in the |
18 |
* documentation and/or other materials provided with the distribution. |
19 |
* 3. Neither the name of the University nor the names of its contributors |
20 |
* may be used to endorse or promote products derived from this software |
21 |
* without specific prior written permission. |
22 |
* |
23 |
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
24 |
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
25 |
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
26 |
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
27 |
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
28 |
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
29 |
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
30 |
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
31 |
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
32 |
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
33 |
* SUCH DAMAGE. |
34 |
*/ |
35 |
|
36 |
/*- |
37 |
* |
38 |
* Copyright (c) 2004, 2005 |
39 |
* Albert Chin-A-Young. |
40 |
* |
41 |
* Modified to work with FreeType's PCF driver. |
42 |
* |
43 |
*/ |
44 |
|
45 |
#if defined(LIBC_SCCS) && !defined(lint) |
46 |
#if 0 |
47 |
static char sccsid[] = "@(#)zopen.c 8.1 (Berkeley) 6/27/93"; |
48 |
#else |
49 |
static char rcsid[] = "$NetBSD: zopen.c,v 1.8 2003/08/07 11:13:29 agc Exp $"; |
50 |
#endif |
51 |
#endif /* LIBC_SCCS and not lint */ |
52 |
|
53 |
/*- |
54 |
* fcompress.c - File compression ala IEEE Computer, June 1984. |
55 |
* |
56 |
* Compress authors: |
57 |
* Spencer W. Thomas (decvax!utah-cs!thomas) |
58 |
* Jim McKie (decvax!mcvax!jim) |
59 |
* Steve Davies (decvax!vax135!petsd!peora!srd) |
60 |
* Ken Turkowski (decvax!decwrl!turtlevax!ken) |
61 |
* James A. Woods (decvax!ihnp4!ames!jaw) |
62 |
* Joe Orost (decvax!vax135!petsd!joe) |
63 |
* |
64 |
* Cleaned up and converted to library returning I/O streams by |
65 |
* Diomidis Spinellis <dds@doc.ic.ac.uk>. |
66 |
*/ |
67 |
|
68 |
#include <ctype.h> |
69 |
#if 0 |
70 |
#include <signal.h> |
71 |
#endif |
72 |
#include <stdlib.h> |
73 |
#include <string.h> |
74 |
#if 0 |
75 |
#include <unistd.h> |
76 |
#endif |
77 |
|
78 |
#if 0 |
79 |
static char_type magic_header[] = |
80 |
{ 0x1f, 0x9d }; /* 1F 9D */ |
81 |
#endif |
82 |
|
83 |
#define BIT_MASK 0x1f /* Defines for third byte of header. */ |
84 |
#define BLOCK_MASK 0x80 |
85 |
|
86 |
/* |
87 |
* Masks 0x40 and 0x20 are free. I think 0x20 should mean that there is |
88 |
* a fourth header byte (for expansion). |
89 |
*/ |
90 |
#define INIT_BITS 9 /* Initial number of bits/code. */ |
91 |
|
92 |
#define MAXCODE(n_bits) ((1 << (n_bits)) - 1) |
93 |
|
94 |
/* Definitions to retain old variable names */ |
95 |
#define fp zs->zs_fp |
96 |
#define state zs->zs_state |
97 |
#define n_bits zs->zs_n_bits |
98 |
#define maxbits zs->zs_maxbits |
99 |
#define maxcode zs->zs_maxcode |
100 |
#define maxmaxcode zs->zs_maxmaxcode |
101 |
#define htab zs->zs_htab |
102 |
#define codetab zs->zs_codetab |
103 |
#define hsize zs->zs_hsize |
104 |
#define free_ent zs->zs_free_ent |
105 |
#define block_compress zs->zs_block_compress |
106 |
#define clear_flg zs->zs_clear_flg |
107 |
#define offset zs->zs_offset |
108 |
#define in_count zs->zs_in_count |
109 |
#define buf_len zs->zs_buf_len |
110 |
#define buf zs->zs_buf |
111 |
#define stackp zs->u.r.zs_stackp |
112 |
#define finchar zs->u.r.zs_finchar |
113 |
#define code zs->u.r.zs_code |
114 |
#define oldcode zs->u.r.zs_oldcode |
115 |
#define incode zs->u.r.zs_incode |
116 |
#define roffset zs->u.r.zs_roffset |
117 |
#define size zs->u.r.zs_size |
118 |
#define gbuf zs->u.r.zs_gbuf |
119 |
|
120 |
/* |
121 |
* To save much memory, we overlay the table used by compress() with those |
122 |
* used by decompress(). The tab_prefix table is the same size and type as |
123 |
* the codetab. The tab_suffix table needs 2**BITS characters. We get this |
124 |
* from the beginning of htab. The output stack uses the rest of htab, and |
125 |
* contains characters. There is plenty of room for any possible stack |
126 |
* (stack used to be 8000 characters). |
127 |
*/ |
128 |
|
129 |
#define htabof(i) htab[i] |
130 |
#define codetabof(i) codetab[i] |
131 |
|
132 |
#define tab_prefixof(i) codetabof(i) |
133 |
#define tab_suffixof(i) ((char_type *)(htab))[i] |
134 |
#define de_stack ((char_type *)&tab_suffixof(1 << BITS)) |
135 |
|
136 |
#define CHECK_GAP 10000 /* Ratio check interval. */ |
137 |
|
138 |
/* |
139 |
* the next two codes should not be changed lightly, as they must not |
140 |
* lie within the contiguous general code space. |
141 |
*/ |
142 |
#define FIRST 257 /* First free entry. */ |
143 |
#define CLEAR 256 /* Table clear output code. */ |
144 |
|
145 |
/*- |
146 |
* Algorithm from "A Technique for High Performance Data Compression", |
147 |
* Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19. |
148 |
* |
149 |
* Algorithm: |
150 |
* Modified Lempel-Ziv method (LZW). Basically finds common |
151 |
* substrings and replaces them with a variable size code. This is |
152 |
* deterministic, and can be done on the fly. Thus, the decompression |
153 |
* procedure needs no input table, but tracks the way the table was built. |
154 |
*/ |
155 |
|
156 |
#if 0 |
157 |
static int |
158 |
zclose(s_zstate_t *zs) |
159 |
{ |
160 |
free(zs); |
161 |
return (0); |
162 |
} |
163 |
#endif |
164 |
|
165 |
/*- |
166 |
* Output the given code. |
167 |
* Inputs: |
168 |
* code: A n_bits-bit integer. If == -1, then EOF. This assumes |
169 |
* that n_bits =< (long)wordsize - 1. |
170 |
* Outputs: |
171 |
* Outputs code to the file. |
172 |
* Assumptions: |
173 |
* Chars are 8 bits long. |
174 |
* Algorithm: |
175 |
* Maintain a BITS character long buffer (so that 8 codes will |
176 |
* fit in it exactly). Use the VAX insv instruction to insert each |
177 |
* code in turn. When the buffer fills up empty it and start over. |
178 |
*/ |
179 |
|
180 |
static const char_type rmask[9] = |
181 |
{0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff}; |
182 |
|
183 |
/* |
184 |
* Decompress read. This routine adapts to the codes in the file building |
185 |
* the "string" table on-the-fly; requiring no table to be stored in the |
186 |
* compressed file. The tables used herein are shared with those of the |
187 |
* compress() routine. See the definitions above. |
188 |
*/ |
189 |
static int |
190 |
zread(s_zstate_t *zs) |
191 |
{ |
192 |
unsigned int count; |
193 |
|
194 |
if (in_count == 0) |
195 |
return -1; |
196 |
if (zs->avail_out == 0) |
197 |
return 0; |
198 |
|
199 |
count = zs->avail_out; |
200 |
switch (state) { |
201 |
case S_START: |
202 |
state = S_MIDDLE; |
203 |
break; |
204 |
case S_MIDDLE: |
205 |
goto middle; |
206 |
case S_EOF: |
207 |
goto eof; |
208 |
} |
209 |
|
210 |
maxbits = *(zs->next_in); /* Set -b from file. */ |
211 |
zs->avail_in--; |
212 |
zs->next_in++; |
213 |
zs->total_in++; |
214 |
in_count--; |
215 |
block_compress = maxbits & BLOCK_MASK; |
216 |
maxbits &= BIT_MASK; |
217 |
maxmaxcode = 1L << maxbits; |
218 |
if (maxbits > BITS) { |
219 |
return -1; |
220 |
} |
221 |
/* As above, initialize the first 256 entries in the table. */ |
222 |
maxcode = MAXCODE(n_bits = INIT_BITS); |
223 |
for (code = 255; code >= 0; code--) { |
224 |
tab_prefixof(code) = 0; |
225 |
tab_suffixof(code) = (char_type) code; |
226 |
} |
227 |
free_ent = block_compress ? FIRST : 256; |
228 |
|
229 |
finchar = oldcode = getcode(zs); |
230 |
if (oldcode == -1) /* EOF already? */ |
231 |
return 0; /* Get out of here */ |
232 |
|
233 |
/* First code must be 8 bits = char. */ |
234 |
*(zs->next_out)++ = (unsigned char)finchar; |
235 |
zs->total_out++; |
236 |
count--; |
237 |
stackp = de_stack; |
238 |
|
239 |
while ((code = getcode(zs)) > -1) { |
240 |
if ((code == CLEAR) && block_compress) { |
241 |
for (code = 255; code >= 0; code--) |
242 |
tab_prefixof(code) = 0; |
243 |
clear_flg = 1; |
244 |
free_ent = FIRST - 1; |
245 |
if ((code = getcode(zs)) == -1) |
246 |
/* O, untimely death! */ |
247 |
break; |
248 |
} |
249 |
incode = code; |
250 |
|
251 |
/* Special case for KwKwK string. */ |
252 |
if (code >= free_ent) { |
253 |
*stackp++ = (unsigned char)finchar; |
254 |
code = oldcode; |
255 |
} |
256 |
|
257 |
/* Generate output characters in reverse order. */ |
258 |
while (code >= 256) { |
259 |
*stackp++ = tab_suffixof(code); |
260 |
code = tab_prefixof(code); |
261 |
} |
262 |
*stackp++ = (unsigned char)(finchar = tab_suffixof(code)); |
263 |
|
264 |
/* And put them out in forward order. */ |
265 |
middle: |
266 |
if (stackp == de_stack) |
267 |
continue; |
268 |
|
269 |
do { |
270 |
if (count-- == 0) { |
271 |
return zs->avail_out; |
272 |
} |
273 |
*(zs->next_out)++ = *--stackp; |
274 |
zs->total_out++; |
275 |
} while (stackp > de_stack); |
276 |
|
277 |
/* Generate the new entry. */ |
278 |
if ((code = free_ent) < maxmaxcode) { |
279 |
tab_prefixof(code) = (unsigned short)oldcode; |
280 |
tab_suffixof(code) = (unsigned char)finchar; |
281 |
free_ent = code + 1; |
282 |
} |
283 |
|
284 |
/* Remember previous code. */ |
285 |
oldcode = incode; |
286 |
} |
287 |
/* state = S_EOF; */ |
288 |
eof: return (zs->avail_out - count); |
289 |
} |
290 |
|
291 |
/*- |
292 |
* Read one code from the standard input. If EOF, return -1. |
293 |
* Inputs: |
294 |
* stdin |
295 |
* Outputs: |
296 |
* code or -1 is returned. |
297 |
*/ |
298 |
static code_int |
299 |
getcode(s_zstate_t *zs) |
300 |
{ |
301 |
code_int gcode; |
302 |
int r_off, bits; |
303 |
char_type *bp; |
304 |
|
305 |
bp = gbuf; |
306 |
if (clear_flg > 0 || roffset >= size || free_ent > maxcode) { |
307 |
/* |
308 |
* If the next entry will be too big for the current gcode |
309 |
* size, then we must increase the size. This implies reading |
310 |
* a new buffer full, too. |
311 |
*/ |
312 |
if (free_ent > maxcode) { |
313 |
n_bits++; |
314 |
if (n_bits == maxbits) /* Won't get any bigger now. */ |
315 |
maxcode = maxmaxcode; |
316 |
else |
317 |
maxcode = MAXCODE(n_bits); |
318 |
} |
319 |
if (clear_flg > 0) { |
320 |
maxcode = MAXCODE(n_bits = INIT_BITS); |
321 |
clear_flg = 0; |
322 |
} |
323 |
if ( zs->avail_in < (unsigned int)n_bits && in_count > (long)n_bits ) { |
324 |
memcpy (buf, zs->next_in, zs->avail_in); |
325 |
buf_len = (unsigned char)zs->avail_in; |
326 |
zs->avail_in = 0; |
327 |
return -1; |
328 |
} |
329 |
if (buf_len) { |
330 |
memcpy (gbuf, buf, buf_len); |
331 |
memcpy (gbuf + buf_len, zs->next_in, |
332 |
n_bits - buf_len); |
333 |
zs->next_in += n_bits - buf_len; |
334 |
zs->avail_in -= n_bits - buf_len; |
335 |
buf_len = 0; |
336 |
zs->total_in += n_bits; |
337 |
size = n_bits; |
338 |
in_count -= n_bits; |
339 |
} else { |
340 |
if (in_count > n_bits) { |
341 |
memcpy (gbuf, zs->next_in, n_bits); |
342 |
zs->next_in += n_bits; |
343 |
zs->avail_in -= n_bits; |
344 |
zs->total_in += n_bits; |
345 |
size = n_bits; |
346 |
in_count -= n_bits; |
347 |
} else { |
348 |
memcpy (gbuf, zs->next_in, in_count); |
349 |
zs->next_in += in_count; |
350 |
zs->avail_in -= in_count; |
351 |
zs->total_in += in_count; |
352 |
size = in_count; |
353 |
in_count = 0; |
354 |
} |
355 |
} |
356 |
roffset = 0; |
357 |
/* Round size down to integral number of codes. */ |
358 |
size = (size << 3) - (n_bits - 1); |
359 |
} |
360 |
r_off = roffset; |
361 |
bits = n_bits; |
362 |
|
363 |
/* Get to the first byte. */ |
364 |
bp += (r_off >> 3); |
365 |
r_off &= 7; |
366 |
|
367 |
/* Get first part (low order bits). */ |
368 |
gcode = (*bp++ >> r_off); |
369 |
bits -= (8 - r_off); |
370 |
r_off = 8 - r_off; /* Now, roffset into gcode word. */ |
371 |
|
372 |
/* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */ |
373 |
if (bits >= 8) { |
374 |
gcode |= *bp++ << r_off; |
375 |
r_off += 8; |
376 |
bits -= 8; |
377 |
} |
378 |
|
379 |
/* High order bits. */ |
380 |
gcode |= (*bp & rmask[bits]) << r_off; |
381 |
roffset += n_bits; |
382 |
|
383 |
return (gcode); |
384 |
} |
385 |
|
386 |
static void |
387 |
zinit(s_zstate_t *zs) |
388 |
{ |
389 |
memset(zs, 0, sizeof (s_zstate_t)); |
390 |
|
391 |
maxbits = BITS; /* User settable max # bits/code. */ |
392 |
maxmaxcode = 1 << maxbits; /* Should NEVER generate this code. */ |
393 |
hsize = HSIZE; /* For dynamic table sizing. */ |
394 |
free_ent = 0; /* First unused entry. */ |
395 |
block_compress = BLOCK_MASK; |
396 |
clear_flg = 0; |
397 |
state = S_START; |
398 |
roffset = 0; |
399 |
size = 0; |
400 |
} |