For my post yesterday on the HD-DVD key I needed to convert the 128bit HEX key into a decimal number and then divide it by two. I figured this would be easy. I’d wander over to Google, search for “convert hex to decimal” and hey-presto, I’d get a web-based converter somewhere to bang the hex key into and get out a decimal number. This soon proved not to work in practice for large numbers. All the converters I tried gave me back floating point numbers with very large exponents. The means loads of precision was lost and hence I couldn’t get the exact number the MPAA claimed to own. So I did what I always do when I can’t find a program to do what I want, I hacked something together in Perl! Now, when I say hacked I do mean hacked. It only took me a few minutes to do and what do ya know, Perl lost precision too, giving me an answer of 1.32562788879895e+37. So, I needed to re-implement this algorithm in a language that could give me basically unlimited integer arithmetic. I chose Java because of the java.math.BigInteger class and because Java is the language I know best. I implemented the same basic algorithm in both languages. It’s interesting to see just how much bigger the Java code is!

[tags]Java, Perl[/tags]

The Algorithm

The algorithm was very simple and doubtless not ‘best practice’. Because my binary operator knowledge is very rusty I converted from HEX to binary using a lookup table (only took a minute or so to throw together a quick hash indexed by the 16 hex characters that contained the 16 equivalent binary strings). So, in one quick foreach loop the program converted the hex to a binary string, then the binary string was reversed, and finally looped through multiplying each binary digit by two to the power of its position in the string and all those results summed together for an answer. This is a very simple algorithm that’s easy to implement and that works. Remember, the aim in hacking a solution is to get an answer as quick as possible, not to write a great program!

Before we go any further lets have a look at the code.

The Perl Implementation

#!/usr/bin/perl

use strict;

my $hex = $ARGV[0];
$hex =~ s/\-//g;
my $bin = '';
my $hexToBin = {
  0 => '0000',
  1 => '0001',
  2 => '0010',
  3 => '0011',
  4 => '0100',
  5 => '0101',
  6 => '0110',
  7 => '0111',
  8 => '1000',
  9 => '1001',
  A => '1010',
  B => '1011',
  C => '1100',
  D => '1101',
  E => '1110',
  F => '1111',
};

foreach my $i (0..length($hex)){
  $bin .= $hexToBin->{substr($hex, $i, 1)}
}

print "Binary: $bin\n";

my $binRev = reverse($bin);
my $ans = 0;
foreach my $i (0..length($binRev)){
  $ans += substr($binRev, $i, 1) * 2**$i;
}

print "Decimal: $ans\n";

The Java Implementation

import java.math.BigInteger;

public class hex2dec {
public static void main(String args[]) {
String hex = args[0].replaceAll(“-“, “”);
String bin = hex2bin(hex);
System.out.println(“Binary: ” + bin);
BigInteger ans = bin2dec(bin);
System.out.println(“Decimal: ” + ans.toString());
}

public static String hexCharToBinString(char h) {
switch (h) {
case ‘0’:
return “0000”;
case ‘1’:
return “0001”;
case ‘2’:
return “0010”;
case ‘3’:
return “0011”;
case ‘4’:
return “0100”;
case ‘5’:
return “0101”;
case ‘6’:
return “0110”;
case ‘7’:
return “0111”;
case ‘8’:
return “1000”;
case ‘9’:
return “1001”;
case ‘A’:
return “1010”;
case ‘B’:
return “1011”;
case ‘C’:
return “1100”;
case ‘D’:
return “1101”;
case ‘E’:
return “1110”;
case ‘F’:
return “1111”;
}
return “”;
}

public static String hex2bin(final String hex) {
StringBuffer ans = new StringBuffer();
for(int i = 0; i < hex.length(); i++) { ans.append(hexCharToBinString(hex.charAt(i))); } return ans.toString(); } public static BigInteger bin2dec(final String b) { BigInteger ans = new BigInteger("0"); String binRev = ((new StringBuffer(b)).reverse()).toString(); for(int i = 0; i < binRev.length(); i++) { ans = ans.add(binCharToBigInt(binRev.charAt(i)).multiply(twoToThePowerOf(i))); } return ans; } public static BigInteger binCharToBigInt(char b) { if(b == '1') { return new BigInteger("1"); } return new BigInteger("0"); } public static BigInteger twoToThePowerOf(int n) { if(n == 0) { return new BigInteger("1"); } if(n == 1) { return new BigInteger("2"); } BigInteger ans = new BigInteger("2"); for(int i = 1; i < n; i++) { //ans *= 2; ans = ans.multiply(new BigInteger("2")); } return ans; } } [/java]

Some Points I Noted

As the title suggests, this is not even a remotely scientific comparison. But I do just want to point out some things that struck me while implementing the same algorithm in the two languages one after the other.

1. Size – Well, if you’re surprised that the Perl implementation is a lot shorter you probably don’t know very much about Perl 🙂 However, in this case the solution in Java is well over twice as long (38 lines v 88 lines).
2. Data Structures – It’s far easier to create a simple hash in Perl. I Java you have to jump through too many hoops with boxing and un-boxing so I didn’t even bother and just used a function with a switch statement.
3. Loops – I find the Perl foreach loops a lot simpler to understand at a glance.
4. Operators – It’s easier to see what’s going on in the Perl loops thanks to the range operator (..). Raising two to the power of i is also easier in Perl because of the ** operator. Java is missing both these operators. Java does have power functions via the java.lang.Math but this function uses floating point arithmetic and hence is no good for integer maths. So, I had to implement my own function for raising two to the appropriate power.
5. String Manipulation – The Java String class is missing some pretty basic functionality, including a function for reversing it. In Perl this is trivial, there is a built in reverse function! In Java I had to temporarily convert my String to a StringBuffer to reverse it. This is responsible for the following very ugly line of code:

   String binRev = ((new StringBuffer(b)).reverse()).toString();