/*	$OpenBSD: zopen.c,v 1.4 2017/01/22 01:55:08 krw Exp $	*/

/*	$NetBSD: zopen.c,v 1.5 1995/03/26 09:44:53 glass 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.

 *

 *	From: @(#)zopen.c	8.1 (Berkeley) 6/27/93

 */

/*-

 * 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 <dds@doc.ic.ac.uk>.

 *

 * zopen(filename, mode, bits)

 *	Returns a FILE * that can be used for read or write.  The modes

 *	supported are only "r" and "w".  Seeking is not allowed.  On

 *	reading the file is decompressed, on writing it is compressed.

 *	The output is compatible with compress(1) with 16 bit tables.

 *	Any file produced by compress(1) can be read.

 */

#include <sys/stat.h>

#include <ctype.h>

#include <errno.h>

#include <signal.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <unistd.h>

#include <fcntl.h>

#include "compress.h"

#define MINIMUM(a, b)	(((a) < (b)) ? (a) : (b))

#define	BITS		16		/* Default bits. */

#define	HSIZE		69001		/* 95% occupancy */

#define	ZBUFSIZ		8192		/* I/O buffer size */

/* A code_int must be able to hold 2**BITS values of type int, and also -1. */

typedef long code_int;

typedef long count_int;

static const u_char z_magic[] =

	{'\037', '\235'};		/* 1F 9D */

#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)

struct s_zstate {

	int zs_fd;			/* File stream for I/O */

	char zs_mode;			/* r or w */

	enum {

		S_START, S_MAGIC, S_MIDDLE, S_EOF

	} zs_state;			/* State of computation */

	int zs_n_bits;			/* Number of bits/code. */

	int zs_maxbits;			/* User settable max # bits/code. */

	code_int zs_maxcode;		/* Maximum code, given n_bits. */

	code_int zs_maxmaxcode;		/* Should NEVER generate this code. */

	count_int zs_htab[HSIZE];

	u_short zs_codetab[HSIZE];

	code_int zs_hsize;		/* For dynamic table sizing. */

	code_int zs_free_ent;		/* First unused entry. */

	/*

	 * Block compression parameters -- after all codes are used up,

	 * and compression rate changes, start over.

	 */

	int zs_block_compress;

	int zs_clear_flg;

	long zs_ratio;

	count_int zs_checkpoint;

	long zs_in_count;		/* Length of input. */

	long zs_bytes_out;		/* Length of output. */

	long zs_out_count;		/* # of codes output (for debugging).*/

	u_char zs_buf[ZBUFSIZ];		/* I/O buffer */

	u_char *zs_bp;			/* Current I/O window in the zs_buf */

	int zs_offset;			/* Number of bits in the zs_buf */

	union {

		struct {

			long zs_fcode;

			code_int zs_ent;

			code_int zs_hsize_reg;

			int zs_hshift;

		} w;			/* Write parameters */

		struct {

			u_char *zs_stackp, *zs_ebp;

			int zs_finchar;

			code_int zs_code, zs_oldcode, zs_incode;

			int zs_size;

		} r;			/* Read parameters */

	} u;

};

/* Definitions to retain old variable names */

#define zs_fcode	u.w.zs_fcode

#define zs_ent		u.w.zs_ent

#define zs_hsize_reg	u.w.zs_hsize_reg

#define zs_hshift	u.w.zs_hshift

#define zs_stackp	u.r.zs_stackp

#define zs_finchar	u.r.zs_finchar

#define zs_code		u.r.zs_code

#define zs_oldcode	u.r.zs_oldcode

#define zs_incode	u.r.zs_incode

#define zs_size		u.r.zs_size

#define zs_ebp		u.r.zs_ebp

/*

 * 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)	zs->zs_htab[i]

#define	codetabof(i)	zs->zs_codetab[i]

#define	tab_prefixof(i)	codetabof(i)

#define	tab_suffixof(i)	((u_char *)(zs->zs_htab))[i]

#define	de_stack	((u_char *)&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. */

static int	cl_block(struct s_zstate *);

static void	cl_hash(struct s_zstate *, count_int);

static int	output(struct s_zstate *, code_int);

/*-

 * 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.

 */

/*-

 * compress write

 *

 * Algorithm:  use open addressing double hashing (no chaining) on the

 * prefix code / next character combination.  We do a variant of Knuth's

 * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime

 * secondary probe.  Here, the modular division first probe is gives way

 * to a faster exclusive-or manipulation.  Also do block compression with

 * an adaptive reset, whereby the code table is cleared when the compression

 * ratio decreases, but after the table fills.  The variable-length output

 * codes are re-sized at this point, and a special CLEAR code is generated

 * for the decompressor.  Late addition:  construct the table according to

 * file size for noticeable speed improvement on small files.  Please direct

 * questions about this implementation to ames!jaw.

 */

int

zwrite(void *cookie, const char *wbp, int num)

{

	code_int i;

	int c, disp;

	struct s_zstate *zs;

	const u_char *bp;

	int count;

	count = num;

	bp = (u_char *)wbp;

	case S_MAGIC:

	case S_EOF:

	case S_START:

		    sizeof(z_magic))

		/* Set hash code range bound. */

		/* Clear hash table. */

	case S_MIDDLE:

			/* Xor hashing. */

				goto nomatch;

			/* Secondary hash (after G. Knott). */

				disp = 1;

			}

				goto probe;

				/* code -> hashtable */

			}

		}

	}

}

int

z_close(void *cookie, struct z_info *info, const char *name, struct stat *sb)

{

	struct s_zstate *zs;

	int rval;

		}

		}

	}

	}

}

static int

zclose(void *cookie)

{

}

/*-

 * 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 u_char lmask[9] =

	{0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00};

static const u_char rmask[9] =

	{0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};

static int

output(struct s_zstate *zs, code_int ocode)

{

	int bits;

		int r_off;

		u_char *bp;

		/* Get to the first byte. */

		/*

		 * Since ocode is always >= 8 bits, only need to mask the first

		 * hunk on the left.

		 */

		/* Get any 8 bit parts in the middle (<=1 for up to 16 bits) */

		}

		/* Last bits. */

		}

		/*

		 * If the next entry is going to be too big for the ocode size,

		 * then increase it, if possible.

		 */

			/*

			 * Write the whole buffer, because the input side won't

			 * discover the size increase until after it has read it

			 */

			}

				else

					zs->zs_maxcode =

			}

		}

		}

		/* At EOF, write the rest of the buffer. */

		}

	}

}

/* Table clear for block compress. */

static int

cl_block(struct s_zstate *zs)

{

	long rat;

		else

	} else {

		/* 8 fractional bits. */

	}

	else {

	}

}

/* Reset code table. */

static void

cl_hash(struct s_zstate *zs, count_int cl_hsize)

{

	count_int *htab_p;

	long i, m1;

	m1 = -1;

		htab_p -= 16;

}

FILE *

zopen(const char *name, const char *mode, int bits)

{

	FILE *fp;

	int fd;

	void *cookie;

	}

	}

}

void *

z_open(int fd, const char *mode, char *name, int bits,

    u_int32_t mtime, int gotmagic)

{

	struct s_zstate *zs;

	}

	/* User settable max # bits/code. */

	/* Should NEVER generate this code. */

}