ref: 0880ac333a2bde53d6bd090b97bafadc7435ad58
dir: /src/lzw/zopen.c/
/* $NetBSD: zopen.c,v 1.8 2003/08/07 11:13:29 agc Exp $ */ /*- * Copyright (c) 1985, 1986, 1992, 1993 * The Regents of the University of California. All rights reserved. * * This code is derived from software contributed to Berkeley by * Diomidis Spinellis and James A. Woods, derived from original * work by Spencer Thomas and Joseph Orost. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ /*- * * Copyright (c) 2004, 2005 * Albert Chin-A-Young. * * Modified to work with FreeType's PCF driver. * */ #if defined(LIBC_SCCS) && !defined(lint) #if 0 static char sccsid[] = "@(#)zopen.c 8.1 (Berkeley) 6/27/93"; #else static char rcsid[] = "$NetBSD: zopen.c,v 1.8 2003/08/07 11:13:29 agc Exp $"; #endif #endif /* LIBC_SCCS and not lint */ /*- * fcompress.c - File compression ala IEEE Computer, June 1984. * * Compress authors: * Spencer W. Thomas (decvax!utah-cs!thomas) * Jim McKie (decvax!mcvax!jim) * Steve Davies (decvax!vax135!petsd!peora!srd) * Ken Turkowski (decvax!decwrl!turtlevax!ken) * James A. Woods (decvax!ihnp4!ames!jaw) * Joe Orost (decvax!vax135!petsd!joe) * * Cleaned up and converted to library returning I/O streams by * Diomidis Spinellis <[email protected]>. */ #include <ctype.h> #if 0 #include <signal.h> #endif #include <stdlib.h> #include <string.h> #if 0 #include <unistd.h> #endif #if 0 static char_type magic_header[] = { 0x1f, 0x9d }; /* 1F 9D */ #endif #define BIT_MASK 0x1f /* Defines for third byte of header. */ #define BLOCK_MASK 0x80 /* * Masks 0x40 and 0x20 are free. I think 0x20 should mean that there is * a fourth header byte (for expansion). */ #define INIT_BITS 9 /* Initial number of bits/code. */ #define MAXCODE(n_bits) ((1 << (n_bits)) - 1) /* Definitions to retain old variable names */ #define fp zs->zs_fp #define state zs->zs_state #define n_bits zs->zs_n_bits #define maxbits zs->zs_maxbits #define maxcode zs->zs_maxcode #define maxmaxcode zs->zs_maxmaxcode #define htab zs->zs_htab #define codetab zs->zs_codetab #define hsize zs->zs_hsize #define free_ent zs->zs_free_ent #define block_compress zs->zs_block_compress #define clear_flg zs->zs_clear_flg #define offset zs->zs_offset #define in_count zs->zs_in_count #define buf_len zs->zs_buf_len #define buf zs->zs_buf #define stackp zs->u.r.zs_stackp #define finchar zs->u.r.zs_finchar #define code zs->u.r.zs_code #define oldcode zs->u.r.zs_oldcode #define incode zs->u.r.zs_incode #define roffset zs->u.r.zs_roffset #define size zs->u.r.zs_size #define gbuf zs->u.r.zs_gbuf /* * To save much memory, we overlay the table used by compress() with those * used by decompress(). The tab_prefix table is the same size and type as * the codetab. The tab_suffix table needs 2**BITS characters. We get this * from the beginning of htab. The output stack uses the rest of htab, and * contains characters. There is plenty of room for any possible stack * (stack used to be 8000 characters). */ #define htabof(i) htab[i] #define codetabof(i) codetab[i] #define tab_prefixof(i) codetabof(i) #define tab_suffixof(i) ((char_type *)(htab))[i] #define de_stack ((char_type *)&tab_suffixof(1 << BITS)) #define CHECK_GAP 10000 /* Ratio check interval. */ /* * the next two codes should not be changed lightly, as they must not * lie within the contiguous general code space. */ #define FIRST 257 /* First free entry. */ #define CLEAR 256 /* Table clear output code. */ /*- * Algorithm from "A Technique for High Performance Data Compression", * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19. * * Algorithm: * Modified Lempel-Ziv method (LZW). Basically finds common * substrings and replaces them with a variable size code. This is * deterministic, and can be done on the fly. Thus, the decompression * procedure needs no input table, but tracks the way the table was built. */ #if 0 static int zclose(s_zstate_t *zs) { free(zs); return (0); } #endif /*- * Output the given code. * Inputs: * code: A n_bits-bit integer. If == -1, then EOF. This assumes * that n_bits =< (long)wordsize - 1. * Outputs: * Outputs code to the file. * Assumptions: * Chars are 8 bits long. * Algorithm: * Maintain a BITS character long buffer (so that 8 codes will * fit in it exactly). Use the VAX insv instruction to insert each * code in turn. When the buffer fills up empty it and start over. */ static const char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff}; /* * Decompress read. This routine adapts to the codes in the file building * the "string" table on-the-fly; requiring no table to be stored in the * compressed file. The tables used herein are shared with those of the * compress() routine. See the definitions above. */ static int zread(s_zstate_t *zs) { unsigned int count; if (in_count == 0) return -1; if (zs->avail_out == 0) return 0; count = zs->avail_out; switch (state) { case S_START: state = S_MIDDLE; break; case S_MIDDLE: goto middle; case S_EOF: goto eof; } maxbits = *(zs->next_in); /* Set -b from file. */ zs->avail_in--; zs->next_in++; zs->total_in++; in_count--; block_compress = maxbits & BLOCK_MASK; maxbits &= BIT_MASK; maxmaxcode = 1L << maxbits; if (maxbits > BITS) { return -1; } /* As above, initialize the first 256 entries in the table. */ maxcode = MAXCODE(n_bits = INIT_BITS); for (code = 255; code >= 0; code--) { tab_prefixof(code) = 0; tab_suffixof(code) = (char_type) code; } free_ent = block_compress ? FIRST : 256; finchar = oldcode = getcode(zs); if (oldcode == -1) /* EOF already? */ return 0; /* Get out of here */ /* First code must be 8 bits = char. */ *(zs->next_out)++ = (unsigned char)finchar; zs->total_out++; count--; stackp = de_stack; while ((code = getcode(zs)) > -1) { if ((code == CLEAR) && block_compress) { for (code = 255; code >= 0; code--) tab_prefixof(code) = 0; clear_flg = 1; free_ent = FIRST - 1; if ((code = getcode(zs)) == -1) /* O, untimely death! */ break; } incode = code; /* Special case for KwKwK string. */ if (code >= free_ent) { *stackp++ = (unsigned char)finchar; code = oldcode; } /* Generate output characters in reverse order. */ while (code >= 256) { *stackp++ = tab_suffixof(code); code = tab_prefixof(code); } *stackp++ = (unsigned char)(finchar = tab_suffixof(code)); /* And put them out in forward order. */ middle: if (stackp == de_stack) continue; do { if (count-- == 0) { return zs->avail_out; } *(zs->next_out)++ = *--stackp; zs->total_out++; } while (stackp > de_stack); /* Generate the new entry. */ if ((code = free_ent) < maxmaxcode) { tab_prefixof(code) = (unsigned short)oldcode; tab_suffixof(code) = (unsigned char)finchar; free_ent = code + 1; } /* Remember previous code. */ oldcode = incode; } /* state = S_EOF; */ eof: return (zs->avail_out - count); } /*- * Read one code from the standard input. If EOF, return -1. * Inputs: * stdin * Outputs: * code or -1 is returned. */ static code_int getcode(s_zstate_t *zs) { code_int gcode; int r_off, bits; char_type *bp; bp = gbuf; if (clear_flg > 0 || roffset >= size || free_ent > maxcode) { /* * If the next entry will be too big for the current gcode * size, then we must increase the size. This implies reading * a new buffer full, too. */ if (free_ent > maxcode) { n_bits++; if (n_bits == maxbits) /* Won't get any bigger now. */ maxcode = maxmaxcode; else maxcode = MAXCODE(n_bits); } if (clear_flg > 0) { maxcode = MAXCODE(n_bits = INIT_BITS); clear_flg = 0; } if ( zs->avail_in < (unsigned int)n_bits && in_count > (long)n_bits ) { memcpy (buf, zs->next_in, zs->avail_in); buf_len = (unsigned char)zs->avail_in; zs->avail_in = 0; return -1; } if (buf_len) { memcpy (gbuf, buf, buf_len); memcpy (gbuf + buf_len, zs->next_in, n_bits - buf_len); zs->next_in += n_bits - buf_len; zs->avail_in -= n_bits - buf_len; buf_len = 0; zs->total_in += n_bits; size = n_bits; in_count -= n_bits; } else { if (in_count > n_bits) { memcpy (gbuf, zs->next_in, n_bits); zs->next_in += n_bits; zs->avail_in -= n_bits; zs->total_in += n_bits; size = n_bits; in_count -= n_bits; } else { memcpy (gbuf, zs->next_in, in_count); zs->next_in += in_count; zs->avail_in -= in_count; zs->total_in += in_count; size = in_count; in_count = 0; } } roffset = 0; /* Round size down to integral number of codes. */ size = (size << 3) - (n_bits - 1); } r_off = roffset; bits = n_bits; /* Get to the first byte. */ bp += (r_off >> 3); r_off &= 7; /* Get first part (low order bits). */ gcode = (*bp++ >> r_off); bits -= (8 - r_off); r_off = 8 - r_off; /* Now, roffset into gcode word. */ /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */ if (bits >= 8) { gcode |= *bp++ << r_off; r_off += 8; bits -= 8; } /* High order bits. */ gcode |= (*bp & rmask[bits]) << r_off; roffset += n_bits; return (gcode); } static void zinit(s_zstate_t *zs) { memset(zs, 0, sizeof (s_zstate_t)); maxbits = BITS; /* User settable max # bits/code. */ maxmaxcode = 1 << maxbits; /* Should NEVER generate this code. */ hsize = HSIZE; /* For dynamic table sizing. */ free_ent = 0; /* First unused entry. */ block_compress = BLOCK_MASK; clear_flg = 0; state = S_START; roffset = 0; size = 0; }