#!/usr/bin/perl

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

use warnings;
use strict;

 
my @lzwTable;
my ($i, $code, $lastStr, $str);

# Initialize the string table with the root set (character 0-255)
for ($i=0; $i<256; $i++) { $lzwTable[$i] = "" . chr($i) . ""; }


##
## Now actually decompress
##

# Read the first LZW code and lookup/print it's string value.  This will always
# result in a singe character being emitted.
read STDIN, $code, 4;
($code) =  unpack "L", $code;
print $lastStr = $lzwTable[$code];


# for the rest of the input...
while (read STDIN, $code, 4) {
	($code) = unpack "L", $code;
	if ($code < @lzwTable) {     # Is the code in the table?
		$str = $lzwTable[$code];  # lookup the code's string
		# add new entry to table which is last string + first char of current str
		push @lzwTable, ($lastStr . substr ($str, 0, 1));
	} else {
		# Not in the table so we need to construct it from the last string and
		# the first char of the last string
		push @lzwTable, $str=($lastStr . substr ($lastStr, 0, 1));
	}
	print $lastStr = $str; # This is now the string associated with the code.
}

## and we're done.



##
## Dump the LZW String Table (except the root-set (entries 1-256)) for fun.
##
sub dumpLZWTable {
 for ($i=256; $i<@lzwTable; $i++) {
	$str = $lzwTable[$i];
	$str =~ s/\n/{RET}/g;
	print "$i = [$str]\n";
 }
}