#!/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 ($minbitsneeded, $tablelength, $bitbuffer);
my ($char, $strlength, $string);
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";
while(<INFILE>) { push(@lines, $_); }
close(INFILE);

$line = join('', @lines);
$line = unpack("B*", $line);
@lines = split(//, $line);
print "Length of data read in bits: ", $#lines+1, "\n";
$minbitsneeded = join('', @lines[0..3]);
for (0..3) { shift @lines; }
$tablelength = join('', @lines[0..11]);
for (0..11) { shift @lines; }
$bitbuffer = join('', @lines[0..2]);
for (0..2) { shift @lines; }
#print "$minbitsneeded :: $tablelength :: $bitbuffer\n";
$minbitsneeded = b2d($minbitsneeded);
$tablelength = b2d($tablelength);
$bitbuffer = b2d($bitbuffer);
print "$minbitsneeded :: $tablelength :: $bitbuffer\n";

print "Bits left: ", scalar(@lines), "\n";
print "Processing and removing the table entries...\n";
$bitsread = 0;
while ($bitsread < $tablelength) {
	$char = pack("B*", join('', @lines[0..7]));
	for (0..7) { shift @lines; }
	$strlength = b2d(join('', @lines[0..$minbitsneeded-1]));
	for (0..$minbitsneeded-1) { shift @lines; }
	$string = join('', @lines[0..$strlength-1]);
	for (0..$strlength-1) { shift @lines; }
	$bitsread += (8+$minbitsneeded+$strlength);
	$decodetable{$string} = $char;
	print "$char (Length: $strlength) $string\n";
}
print "Bits left: ", scalar(@lines), "\n";
print "Removing the bit buffer...\n";
for (1..$bitbuffer) { pop @lines; }
print "Bits left: ", scalar(@lines), "\n";

$bitlength = scalar(@lines);
print "Data Length: $bitlength\n";
print @lines, "\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};

}

### 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";

##########################################################################
##########################################################################

sub b2d {
	my $temp = 0;
	my @temp = split(//, shift @_);
	for (my $i=0; @temp > 0; $i++) {
		$_ = pop @temp;
		$temp += (2**$i)*$_;
	}
	return $temp;
}
