#!/usr/bin/perl -w
# Huffman Decompression - Operating on a string of ASCII characters
# Lossless compression - fixed length data to variable length representation
###############################################################################

use strict;

die "Usage: dehuff.pl <input file> <output file>\n" if @ARGV != 2;

my $line; 
my @lines = ();
my @temp = ();
my %decodetable = ();
my ($longest, $second);
my %node = ();
my $probe;
my ($bit, $bitlength, $bitsread);
my @newdata = ();
my ($chopped1, $chopped2);

### Step 0: Open the file passed as the first argument to the program
########### 1) Read the decoding table into the %decodetable hash
########### 2) Read the packed data into the @lines array

open(INFILE, "<$ARGV[0]") or die "Cannot read from $ARGV[0]: $!\n";
$line = <INFILE>;
until ($line =~ /_BITLENGTH_ : \d+/) {
	if ($line =~ /(.+) : (.+)/) {
		$decodetable{$2} = $1;
		$line = <INFILE>;
		next;
	}
	if ($line =~ /^\n$/) {
		$line = <INFILE>;
		$line =~ /: (.+)/;
		$decodetable{$1} = "\n";
		$line = <INFILE>;
		next;
	}
}
chomp($bitlength = (split(' : ', $line))[1]);
while ($line = <INFILE>) {
	push(@lines, $line);
}
close(INFILE);

######################################################################
######################################################################
#print "Data has been read in from $ARGV[0]...\n";
#print "BITLENGTH = $bitlength\n";
#foreach (keys %decodetable) { print "$decodetable{$_} : $_\n"; }
#print '-' x 80, "\n";
$line = join('', @lines);
$line = unpack("B*", $line);
@lines = split(//, $line);
#for (my $i=0; $i<$bitlength; $i++) { print $lines[$i]; }
#print "\n", '-' x 80, "\n";
######################################################################
######################################################################

while (keys %decodetable > 1) {

	### Step 1: Find the character with the longest code string
	########### and save it into $longest

	### Initialize $longest to the first character in %decodetable
	$longest = (keys %decodetable)[0];
	foreach (keys %decodetable) {
		if (length($_) > length($longest)) {
			$longest = $_;
		}
	}

	### Step 2: Find the character with the second longest code string
	########### and save it into $second

	### Initialize $second to the first value in %decodetable if
	### it is not $longest.  Otherwise, initialize $second to
	### the last character in %decodetable
	if ($longest ne (keys %decodetable)[0]) { 
		$second = (keys %decodetable)[0]; 
	} else {
		$second = (keys %decodetable)[-1];
	}
	foreach (keys(%decodetable)) {
		if ($_ ne $longest && length($_) > length($second)) {
			$second = $_;
		}
	}

	### Step 3: Create nodes for $longest and $second and
	########### plug the two into the binary tree structure

	unless (defined($node{$longest})) {
		$node{$longest}[0] = undef;
		$node{$longest}[1] = undef;
		$node{$longest}[2] = $decodetable{$longest};
#		print "Made node $longest ($decodetable{$longest})\n";
	}
	unless (defined($node{$second})) {
		$node{$second}[0] = undef;
		$node{$second}[1] = undef;
		$node{$second}[2] = $decodetable{$second};
#		print "Made node $second ($decodetable{$second})\n";
	}	

	$chopped1 = chop $longest;
	$chopped2 = chop $second;
	if (length($longest) > 0) {
		unless (defined($node{$longest})) {
			$node{$longest}[0] = $longest . '0';
			$node{$longest}[1] = $longest . '1';
			$node{$longest}[2] = undef;
#			print "Branch node => $longest (", 
#				$longest.'0', " ", $longest.'1', ")\n";
		}
		unless (defined($node{$second})) {
			$node{$second}[0]  = $second . '0';
			$node{$second}[1]  = $second . '1';
			$node{$second}[2]  = undef;
#			print "Branch node => $second (", 
#				$second.'0', " ", $second.'1', ")\n";
		}
	} else {
		$node{'TOP'} = [0, 1, undef];
#		print "Binary Tree created\n";
	}
	
	### Step 4: Remove $longest and $second from %decodetable
	########### and replace them with a combination of their values

	$decodetable{$longest} = $decodetable{$longest . $chopped1};
	$decodetable{$second} = $decodetable{$second . $chopped2};
	delete $decodetable{$longest . $chopped1};
	delete $decodetable{$second . $chopped2};

}

#print '-' x 80, "\n";
#foreach (sort keys %node) {
#	print "$_ => [$node{$_}[0], $node{$_}[1], $node{$_}[2]]\n";
#}

### Step 5: Decode the data from the file using the binary tree

$bitsread = 0;
$probe = 'TOP';
while (defined($node{$probe}[0]) && $bitsread < $bitlength) {
	$bit = shift(@lines);
	$bitsread++;
	if ($bit eq '0') { $probe = $node{$probe}[0]; }
	if ($bit eq '1') { $probe = $node{$probe}[1]; }
	if (defined($node{$probe}[2])) { 
		push(@newdata, $node{$probe}[2]); 
		$probe = 'TOP';
	}
}

### Step 6: Write the decoded data out to a file

open(OUTFILE, ">$ARGV[1]") or die "Cannot write to $ARGV[1]: $!\n";
print OUTFILE join('', @newdata);
close(OUTFILE) or die "Cannot close $ARGV[1]: $!\n";

print "Data has been written to $ARGV[1]\n";
