#!/usr/local/bin/perl

$msg = 'print "Just another Perl Hacker.\n";';

sub dec2bin {
    my $str = unpack("B32", pack("N", shift));
    $str =~ s/^0+(?=\d)//;   # otherwise you'll get leading zeros
    return $str;
}

sub bin2dec {
    return unpack("N", pack("B32", substr("0" x 32 . shift, -32)));
}

@msg_ascii = unpack ('C*',$msg);

print "ASCII:\n$msg\n\n";
print "Decimal:\n";

foreach $c (@msg_ascii)
{
  $c -= 32;
  print "$c ";
  $t = substr(dec2bin($c),-7);
  $bin_msg .= $t;
#  $tbl{substr($t,0,2)}++;
#  $tbl{substr($t,3,4)}++;
}

print "\n\nBinary:\n$bin_msg\n\n";

print "Frequency Table:\n";

foreach $item (sort keys %tbl)
{
  print "$item: $tbl{$item}\n";
  $etree[$#etree+1] = [$tbl{$item},$item];
}


print "\n";

while(scalar(@etree)>1)
{
  @etree = map {$_->[1]}
    sort {$a->[0] <=> $b->[0]}
    map {[$_->[0], $_]} @etree;

  $newent[0] = $etree[0][0] + $etree[1][0];
  $newent[1] = [[shift @etree], [shift @etree]];

  push @etree,[@newent];
}

$indent = "";

sub dump_etree
{
  my($tr) = @_;
  foreach $item (@$tr)
  {
    if(ref $item) {
      $indent .= '|' unless (ref $item->[0]);
      dump_etree($item);
      $indent = substr($indent,0,-1) unless (ref $item->[0]);
    } else {
      print $indent;
      print '+-';
      print "$item\n";
    }
  }
}

sub make_table
{
  my($st) = shift;
  my(@tr) = @_;
  if(ref $tr[1])
  {
    make_table($st.'0',@{$tr[1][0][0]});
    make_table($st.'1',@{$tr[1][1][0]});
  } else {
    $ttbl{$tr[1]} = $st;
  }
}


print "\nEncoding Tree:\n";

dump_etree(@etree);

print "\nEncoding Table:\n";
my (%ttbl);
make_table('',@{$etree[0]});

foreach $t (keys %ttbl)
{
  print "$t: $ttbl{$t}\n";
}

foreach $c (@msg_ascii)
{
  $t = substr(dec2bin($c),-7);
  $huf_msg .= $ttbl{substr($t,0,2)};
  $huf_msg .= $ttbl{substr($t,2)};
}

print "\nEncoded binary:\n$huf_msg\n";

print "\n\nBinary length: " . (length $bin_msg) . "\n";
print "Huffman length: " . (length $huf_msg) . "\n";

print "Saved bits: " . (length $bin_msg - length $huf_msg) . "\n";


while (length $huf_msg)
{
  push @huf_dec,bin2dec(substr($huf_msg,0,6))+32;
  $huf_msg = substr($huf_msg,7);
}

foreach $dec (@huf_dec)
{
  print "$dec ";
}

$huf_ascii = pack("C*",@huf_dec);

print "\n\n$huf_ascii\n$msg\n";