6
\$\begingroup\$

I wrote a solution in Java to solve the problem here. I use BigInteger to convert first from base 16 to base 10, then base 10 to base 64.

This seems quite inefficient to me, and I would have no idea how to do this if I couldn't use BigInteger. I'm sure there's a nice and clever way to do this using a lot more bit manipulation.

import java.math.BigInteger;


public class Base64{

    //according to RFC 4648 and RFC 2045
    public final static char[] base64alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/".toCharArray();
    public final static char base64pad = '='; //unused

    public static void main(String[] args){

        String test = "49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d";
        System.out.println( base16to64( test ) );
    }

    /**Return the base 64 value of an input base 16 string.
     */
    public static String base16to64(String hex){
        BigInteger value = base16to10(hex); //base 10 value

        // --- convert base 10 to 64 ---
        int digits = 1; // # digits in base 64 we'll need
        while( value.compareTo(new BigInteger("64").pow(digits)) != -1 ){ //while the decimal value >= 64^i
            digits++;
        }

        String ret = "";
        for(int i = digits - 1; i >= 0; i--){ //start at most significant digit

            //this digit must be an A (represents 0)
            if( value.subtract(new BigInteger("64").pow(i)).compareTo(BigInteger.ZERO) == -1){
                ret += "A";
            }
            else{
                for(int d = 63; d >= 1; d--){
                    //digit found: [ value - (64^i)*d >= 0 ]  with d the greatest possible
                    if( value.subtract(new BigInteger("64").pow(i).multiply(
                            new BigInteger(Integer.toString(d)))).compareTo(BigInteger.ZERO) != -1){
                        value = value.subtract(new BigInteger("64").pow(i).multiply( new BigInteger(Integer.toString(d))));
                        ret += base64alphabet[d];
                        break;
                    }
                }
            }//end else
        }

        return ret;
    }//end base16to64()

    /**Return the BigInteger decimal value of an input hexadecimal string.
     */
    public static BigInteger base16to10(String hex){
        hex = hex.toLowerCase();

        //hex is 0-9 then a-f
        BigInteger value = BigInteger.ZERO; //base 10 value
        for(int i = 0; i < hex.length(); i++){ //moving from most significant digit towards 16^0

            int digit = (int) hex.charAt(i);
            //if the hex digit is 0-9
            if( '0' <= hex.charAt(i) && hex.charAt(i) <= '9')
                digit = digit - '0'; 
            //else the hex digit is a-f
            else
                digit = digit - 'a' + 10; 

            BigInteger temp = new BigInteger("" + digit); // digit as BigInt
            temp = temp.multiply( new BigInteger("16").pow( hex.length() - 1 - i) ); // digit * 16^index
            value = value.add(temp);
        }

        return value;
    }//end base16to10()
}
\$\endgroup\$
5
\$\begingroup\$

You are working too hard. Java has a Base64 class that does most of the work for you, all you need to do is combine it and the constructor for BigInteger, and you are done.

public static String base16to64(String hex){
    return Base64.getEncoder().encodeToString(new BigInteger(hex, 16).toByteArray());
}

For the linked example input:

49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d

We get the correct output:

SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t


If you wanted to implement the base 64 conversion yourself, note that you are still doing too much work. Your base16to10 function could be replaced with

BigInteger value = new BigInteger(hex, 16);

One function completely cut out.


However, if you don't want to use BigInteger at all (this is generally a bad idea, but for programming practice, you might want to), notice that log(64)/log(16) == 1.5. Thus, for every 1.5 hex digits, we can obtain 1 base 64 digits.

So take the last 2 hex digits of the hex string: 6d. In binary, this is 01101101. We only need to consider 101101, which is 45. So we take the 45th element of the base 64 alphabet: t. That's the last digit of the base 64 string. Now just shift the hex string over by 6 bits, and repeat (note, shifting by 6 bits won't be clean, so it's probably easier to instead process 3 hex digits to 2 base 64 digits, and take off the last two elements of the hex string).

But noticing the "Cryptopals Rule":

Always operate on raw bytes, never on encoded strings. Only use hex and base64 for pretty-printing.

You should probably parse the hex string into a byte[] or ArrayList<Byte> before working on it. Honestly, I think this is way easier to do using BigInteger.

\$\endgroup\$
  • \$\begingroup\$ Thanks, I feel a little silly. Any suggestions on how to do this without using BigInteger/ using more bit manipulation if I were to fully implement this myself? \$\endgroup\$ – Kolibrie Nov 23 '15 at 21:42
2
\$\begingroup\$

Some general concerns:

/**Return the BigInteger decimal value of an input hexadecimal string.
 */

Usually we format Javadoc comments like so:

/**
 * Return the BigInteger decimal value of an input hexadecimal string.
 */

public static BigInteger base16to10(String hex){

This function isn't actually converting base 16 to base 10. It seems like it is, but that's not really what it's doing. BigInteger doesn't store its data in base 10 format, so this function would be better named parseBase16, or something along those lines.


for(int i = 0; i < hex.length(); i++){
    int digit = (int) hex.charAt(i);
    //if the hex digit is 0-9
    if( '0' <= hex.charAt(i) && hex.charAt(i) <= '9')
        digit = digit - '0'; 
    //else the hex digit is a-f
    else
        digit = digit - 'a' + 10; 

That's a lot of hex.charAt(i) calls. Instead, you could just do:

for(int i = 0; i < hex.length(); i++){
    char digit = hex.charAt(i);
    int digitValue = (int) digit;

    if('0' <= digit && digit <= '9')
        digit = digitValue - '0'; 
    else
        digitValue = digitValue - 'a' + 10; 

    BigInteger temp = new BigInteger("" + digit);
    temp = temp.multiply( new BigInteger("16").pow( hex.length() - 1 - i) ); 
    value = value.add(temp);
}

This is an inefficient method of constructing BigIntegers. Instead:

     BigInteger temp = BigInteger.valueOf(digit);
    temp = temp.multiply(BigInteger.valueOf(16).pow( hex.length() - 1 - i)); 
    value = value.add(temp);
}

Although, since we always have BigInteger.valueOf(16), you should really make that a final BigInteger SIXTEEN = BigInteger.valueOf(16) outside of the loop.

But wait. If you instead iterated over the digits in reverse, you'd start with a BigInteger currentPowerOf16 = BigInteger.ONE, and all you'd have to do is currentPowerOf16 = currentPowerOf16.multiply(SIXTEEN);, which would automatically take care of the powers for you. That would be the better way to do it; it's notably more efficient too.


Let's also consider your comments:

//hex is 0-9 then a-f

You can expect your reader to know this. We all know that hexadecimal is 0-9 then a-f, so just leave this comment out.

BigInteger value = BigInteger.ZERO; //base 10 value

I'm not sure what //base 10 value means. I'm guessing this is the result of the conversion. So I'd remove the comment and instead name this variable result (yes, I'm lazy on variable names).

for(int i = 0; i < hex.length(); i++){ //moving from most significant digit towards 16^0

What is this? How am I "moving from the most significant digit towards 16^0"? Oh, you must mean "iterate over the digits, starting from the leftmost".

//if the hex digit is 0-9
  if( '0' <= hex.charAt(i) && hex.charAt(i) <= '9')

This comment is redundant with the next line of code.

//else the hex digit is a-f
  else

This is a good comment. However, it's best to format comments with a space:

// Else, the hex digit is a-f.
BigInteger temp = new BigInteger("" + digit); // digit as BigInt

This is another redundant comment

}//end base16to10()

Don't use comments to show flow of the methods. // end if, // end base16to10, etc are not useful comments. If it is necessary to include such comments to be able to figure out what is being closed with the }, you should refactor into yet another function. In this case, it is perfectly clear that you are ending the base16to10 function.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.