source: trunk/poppler/freetype-2.1.10/src/lzw/zopen.c @ 2

Last change on this file since 2 was 2, checked in by Eugene Romanenko, 15 years ago

First import

File size: 10.7 KB
Line 
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
47static char sccsid[] = "@(#)zopen.c     8.1 (Berkeley) 6/27/93";
48#else
49static 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
79static 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
157static int
158zclose(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
180static 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 */
189static int
190zread(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.  */
265middle:
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; */
288eof:    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 */
298static code_int
299getcode(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
386static void
387zinit(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}
Note: See TracBrowser for help on using the repository browser.