#!/usr/bin/perl

#
# Perl implementation of LZW compression on stdio
# Features: Code word size is 4 bytes.
#           String table is allowed to grow unbounded
#

use warnings;
use strict;

my %lzwTable;
my ($i, $c, $str, $strc, $tableCount);

#
# Initialize string hash table.
#
for ($i=0; $i<256; $i++) { $lzwTable{chr($i)} = $i; }
$tableCount = 255; 


##
## Now actually compress
##

# First step is to read a char and emit an LZW code
read STDIN, $str, 1;

# For the rest of the input...
while (read STDIN, $c, 1 ) {
	$strc = "$str$c";
	if ($lzwTable{$strc}) { # Is last matched string and next char in table?
		$str = $strc;        # If so then keep this string and keep going.
	} else {
		$lzwTable{$strc} = ++$tableCount; #If not add it to table
		print pack "L", $lzwTable{"$str"};   # emit the code of just the string
		$str = $c;                           # & start over with just the char
	}
}

#
# Last thing we do is emit the code for the string we've built up
#
print pack "L", $lzwTable{"$str"};

## and we're done!!!



##
## Dump the LZW String Table (except the root-set (entries 1-256)) for fun.
##
sub dumpLZWTable {
 my @lzwTable;

 # Reverse the lzw hash table so we can index the strings by index number.
 foreach (keys %lzwTable) { $lzwTable[$lzwTable{"$_"}] = $_; }

 for ($i=256; $i<$tableCount; $i++) {
	$str = $lzwTable[$i];
	$str =~ s/\n/{RET}/g;
	print "$i = [$str]\n";
 }
}