xref: /src/sys/arch/sgimips/stand/undist/util.c

/*	$NetBSD: util.c,v 1.1 2026/06/11 08:29:49 rumble Exp $	*/

/*
 * Cribbed from 4.4BSD/Net2 and NetBSD 4.99.42 with some stuff ripped out and
 * cleaned up.
 */

/*-
 * Copyright (c) 1991, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * 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.
 */

#include <sys/types.h>
#include <stdint.h>
#include <stdio.h>
#include <unistd.h>

#include "util.h"

/* 'thecrc' must initially be 0. */
int
sum1(int thecrc, u_char *buf, uint32_t len)
{
	/*
	 * 16-bit checksum, rotating right before each addition;
	 * overflow is discarded.
	 */
	for (u_char *p = buf; p < &buf[len]; ++p) {
		if (thecrc & 1)
			thecrc |= 0x10000;
		thecrc = ((thecrc >> 1) + *p) & 0xffff;
	}

	return (thecrc);
}

/*
 * Copyright (c) 1985, 1986 The Regents of the University of California.
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * 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. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 4. 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.
 */

/*
 * compress.c - File compression ala IEEE Computer, June 1984.
 *
 * 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)
 */

#include <sys/param.h>
#include <sys/stat.h>
#include <signal.h>
#include <utime.h>
#include <errno.h>
#include <unistd.h>
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>

#define BITS	16
#define HSIZE	69001		/* 95% occupancy */

/*
 * a code_int must be able to hold 2**BITS values of type int, and also -1
 */
typedef long int	code_int;
typedef long int	count_int;

static const unsigned char magic_header[] = { "\037\235" };	/* 1F 9D */

/* Defines for third byte of header */
#define BIT_MASK	0x1f
#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 */

static int n_bits;			/* number of bits/code */
static int maxbits = BITS;		/* user settable max # bits/code */
static code_int maxcode;		/* maximum code, given n_bits */
static code_int maxmaxcode = 1 << BITS;	/* should NEVER generate this code */
#define MAXCODE(n_bits)	((1 << (n_bits)) - 1)

static count_int htab [HSIZE];
static unsigned short codetab [HSIZE];

#define codetabof(i)	codetab[i]

/*
 * 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 tab_prefixof(i)	codetabof(i)
#define tab_suffixof(i)	((unsigned char *)(htab))[i]
#define de_stack		((unsigned char *)&tab_suffixof(1<<BITS))

static code_int free_ent = 0;			/* first unused entry */

static code_int getcode(FILE *);

/*
 * block compression parameters -- after all codes are used up,
 * and compression rate changes, start over.
 */
static int block_compress = BLOCK_MASK;
static int clear_flg = 0;

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

static const unsigned char rmask[9] = {
	0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff
};

#ifndef BUFFER_SIZE
#define BUFFER_SIZE	16384
#endif

/* maximum number of bytes to return from getcode(). if 0, no limit. */
static uint32_t getcode_maxreadbytes;

/* number of bytes getcode has returned since decompress() was called */
static uint32_t getcode_readbytes;

/* this shouldn't be here, but it's faster to just do it on the fly */
static int output_checksum;

/*
 * Decompress 'input' to 'output'.  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.  See the definitions above.
 *
 * Returns the number of bytes written to 'output'.
 */
static uint32_t
do_decompression(FILE *input, FILE *output) {
    unsigned char *stackp;
    int finchar;
    code_int code, oldcode, incode;
    int    n, nwritten, offset;		/* Variables for buffered write */
    char buff[BUFFER_SIZE];		/* Buffer for buffered write */
    uint32_t byteswritten;

    byteswritten = 0;

    /*
     * 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) = (unsigned char)code;
    }
    free_ent = ((block_compress) ? FIRST : 256 );

    finchar = oldcode = getcode(input);
    if(oldcode == -1)	/* EOF already? */
	return (0);

    /* first code must be 8 bits = char */
    n=0;
    buff[n++] = (char)finchar;

    stackp = de_stack;

    while ( (code = getcode(input)) > -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(input)) == -1 )	/* O, untimely death! */
		break;
	}
	incode = code;
	/*
	 * Special case for KwKwK string.
	 */
	if ( code >= free_ent ) {
            *stackp++ = finchar;
	    code = oldcode;
	}

	/*
	 * Generate output characters in reverse order
	 */
	while ( code >= 256 ) {
	    *stackp++ = tab_suffixof(code);
	    code = tab_prefixof(code);
	}
	*stackp++ = finchar = tab_suffixof(code);

	/*
	 * And put them out in forward order
	 */
	do {
	    /*
	     * About 60% of the time is spent in the putchar() call
	     * that appeared here.  It was originally
	     *		putchar ( *--stackp );
	     * If we buffer the writes ourselves, we can go faster (about
	     * 30%).
	     *
	     * At this point, the next line is the next *big* time
	     * sink in the code.  It takes up about 10% of the time.
	     */
	     buff[n++] = *--stackp;
	     if (n == BUFFER_SIZE) {
		 offset = 0;
		 do {
		     output_checksum = sum1(output_checksum,
			 (u_char *)&buff[offset], n);
		     if (output == NULL)
			nwritten = n;
		     else
			nwritten = write(fileno(output), &buff[offset], n);
		     if (nwritten < 0)
			 return (0);
		     offset += nwritten;
		     byteswritten += nwritten;
		 } while ((n -= nwritten) > 0);
	      }
	} while ( stackp > de_stack );

	/*
	 * Generate the new entry.
	 */
	if ( (code=free_ent) < maxmaxcode ) {
	    tab_prefixof(code) = (unsigned short)oldcode;
	    tab_suffixof(code) = finchar;
	    free_ent = code+1;
	}
	/*
	 * Remember previous code.
	 */
	oldcode = incode;
    }
    /*
     * Flush the stuff remaining in our buffer...
     */
    offset = 0;
    while (n > 0) {
	output_checksum = sum1(output_checksum, (u_char *)&buff[offset], n);
	if (output == NULL)
	    nwritten = n;
	else
	    nwritten = write(fileno(output), &buff[offset], n);
	if (nwritten < 0)
	    return (0);
	offset += nwritten;
	n -= nwritten;
	byteswritten += nwritten;
    }

    return (byteswritten);
}

/*-
 * Read one code from the standard input.  If EOF, return -1.
 * Inputs:
 *  	FILE stream.
 * Outputs:
 * 	code or -1 is returned.
 */
static code_int
getcode(FILE *input)
{
    code_int code;
    static int offset = 0, size = 0;
    static unsigned char buf[BITS];
    int r_off, bits;
    size_t readbytes;
    unsigned char *bp = buf;

    if ( clear_flg > 0 || offset >= size || free_ent > maxcode ) {
	/*
	 * If the next entry will be too big for the current code
	 * size, then we must increase the size.  This implies reading
	 * a new buffer full, too.
	 *
	 * Bail immediately if we've read in our maximum.
	 */
	if (getcode_maxreadbytes != 0 &&
	    getcode_readbytes == getcode_maxreadbytes)
		return (-1);


	if ( free_ent > maxcode ) {
	    n_bits++;
	    if ( n_bits == maxbits )
		maxcode = maxmaxcode;	/* won't get any bigger now */
	    else
		maxcode = MAXCODE(n_bits);
	}
	if ( clear_flg > 0) {
    	    maxcode = MAXCODE (n_bits = INIT_BITS);
	    clear_flg = 0;
	}

	if (getcode_maxreadbytes != 0 &&
	    n_bits > (getcode_maxreadbytes - getcode_readbytes))
		readbytes = getcode_maxreadbytes - getcode_readbytes;
	else
		readbytes = n_bits;

	size = fread( buf, 1, readbytes, input );
	if ( size <= 0 )
	    return -1;			/* end of file */
	getcode_readbytes += size;
	offset = 0;
	/* Round size down to integral number of codes */
	size = (size << 3) - (n_bits - 1);
    }
    r_off = offset;
    bits = n_bits;
	/*
	 * Get to the first byte.
	 */
	bp += (r_off >> 3);
	r_off &= 7;
	/* Get first part (low order bits) */
	code = (*bp++ >> r_off);
	bits -= (8 - r_off);
	r_off = 8 - r_off;		/* now, offset into code word */
	/* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
	if ( bits >= 8 ) {
	    code |= *bp++ << r_off;
	    r_off += 8;
	    bits -= 8;
	}
	/* high order bits. */
	code |= (*bp & rmask[bits]) << r_off;
    offset += n_bits;

    return code;
}

/*
 * Decompress from stream 'input' into stream 'output', reading at most
 * 'maxinput' bytes from 'input'.
 *
 * The special value 0 for maxinput indicates no limit.
 *
 * Returns the number of bytes outputted.
 */
uint32_t
decompress(FILE *input, FILE *output, uint32_t maxinput, int *cksum)
{
	uint32_t ret;

	if (maxinput != 0 && maxinput < 4)
		return (0);

	if ((getc(input) & 0xff) != magic_header[0] ||
	    (getc(input) & 0xff) != magic_header[1])
		return (0);

	clear_flg = 0;
	maxbits = getc(input);
	block_compress = maxbits & BLOCK_MASK;
	maxbits &= BIT_MASK;
	maxmaxcode = 1 << maxbits;
	if (maxbits > BITS)
		return (0);

	getcode_maxreadbytes = (maxinput == 0) ? 0 : maxinput - 3;
	getcode_readbytes = 0;
	output_checksum = 0;
	ret = do_decompression(input, output);
	*cksum = output_checksum;

	return (ret);
}