/*
    lz78.c -- Copyleft (C) 1990 by James A. Woods,
	RIACS, NASA Ames Research Center.

    essence of U.S. patent #4,464,650 by Lempel/Ziv/Cohn/Eastman,
	assignees Sperry Corporation and AT&T Bell Laboratories.
	invented 1976, published IEEE Trans. Info Theory, 1978,
	filed Aug. 10, 1981, awarded Aug. 7, 1984.
*/

#include <stdio.h>

#define BITS 14
short table[(1<<BITS) * 256];	/* 8MB for 14-bit codes, 32MB for 16-bit */

main()
{
    register int K, i, p, prefix;
    register long code;

    i++;
    prefix = 0;

    while ((K = (getchar())) != EOF) {
	code = (long) ((K << BITS) + prefix);
	if ( (p = table[code]) != 0 )
            prefix = p;
	else {
/*
	    output(prefix, BITS);  /* bitstuff or cascade with arithmetic coder
	    output(K, 8);
*/
	    putchar((prefix>>8) & 0377);  /* tokens hardcoded at 16 bits here */
	    putchar(prefix & 0377);
	    putchar(K);

	    prefix = 0;

	    if (i < (1<<BITS)) 
		table[code] = (short) i++;
    	}
    }
}

-----------------------------------------------------------------------------
/*
    lzw.c -- Copyleft (C) 1985 by James A. Woods, NASA Ames Research Center

    essence of U.S. patent #4,558,302 by Terry Welch, assignee Sperry Corp.,
	filed Jun. 20, 1983, published 1984, awarded Dec. 10, 1985.

    LZW is also known as LZMW1.  independently discovered by Victor Miller /
	Mark Wegman, U.S. patent #4,814,746, assignee IBM,
	filed June 1, 1983, published 1984, awarded March 21, 1989.
	earlier file date takes precedence!

    code adds one table initialization plus three lines of change to lz78.c
*/

#include <stdio.h>

#define BITS 14
short table[(1<<BITS) * 256];	/* 8MB for 14-bit codes, 32MB for 16-bit */

main()
{
    register int K, i, p, prefix;
    register long code;

    for (i = 0; i < 256; i++)
	table[i] = i;
    i++;
    prefix = getchar();

    while ((K = (getchar())) != EOF) {
	code = (long) ((K << BITS) + prefix);
	if ( (p = table[code]) != 0 )
            prefix = p;
	else {
/*
	    output(prefix, BITS);  /* bitstuff or cascade with arithmetic coder
*/
	    putchar((prefix>>8) & 0377);  /* tokens hardcoded at 16 bits here */
	    putchar(prefix & 0377);

	    prefix = K;

	    if (i < (1<<BITS)) 
		table[code] = (short) i++;
    	}
    }
}

-----------------------------------------------------------------------------
/*
    lzwap.c -- Copyleft (C) 1990 by James A. Woods,
	RIACS, NASA Ames Research Center.

    essence of U.S. patent #4,876,541 by James A. Storer, Brandeis Univ.,
	assignee Data Compression Corporation, filed Oct. 25, 1987,
	awarded Oct. 24, 1989.  Independently rediscovered by
	Daniel J. Bernstein, NYU, 1990, and Nigel Horspool, U. Victoria
	(see DCC '91 conference proceedings).

    LZW-based, with "all-prefixes" addition.
*/

#include <stdio.h>

#define BITS 14
short table[(1<<BITS) * 256];   /* 8MB for 14-bit codes, 32MB for 16-bit */

int curmatch[2000];

main()
{
    register int K, i, j, p, prefix;
    register long code;
    long oldmatch, newcode;
    int count;

    count = 1;

    for (i = 0; i < 256; i++)
	table[i] = i;

    i++;
    curmatch[0] = prefix = getchar();

    while ((K = (getchar())) != EOF) {
	curmatch[count] = K;
	code = (long) ((K << BITS) + prefix);
	if ( (p = table[code]) != 0 ) {
	    count++;
	    prefix = p;
	}
	else {
/*
	    output(prefix, BITS);  /* bitstuff or cascade with arithmetic coder
*/
	    putchar((prefix>>8) & 0377);  /* tokens hardcoded at 16 bits here */
	    putchar(prefix & 0377);

	    if (i < (1<<BITS)) {
		if ( count > 1) {
		    for (j = 1; j < count; j++) {
			newcode = (long) (((curmatch[j]) << BITS) + oldmatch);
	    		if (i < (1<<BITS)) 
			    oldmatch = table[newcode] = (short) i++;
		    }
		}
	    	if (i < (1<<BITS)) 
		    oldmatch = table[code] = (short) i++;
	    }
	    prefix = K;
	    curmatch[0] = K;
	    count = 1;
    	}
    }
}
-----------------------------------------------------------------------------