Matasano Cryptopals Challenge 1: convert hex to base64

Question

Cryptopals challenge 1

Using binary strings to convert from hex to binary felt kinda hacky. I'd like to hear if there are better ways to do that.

I used memcpy() and pointer to the end of the string instead of strcat() to avoid the Shlemiel the Painter problem.

EDIT: follow up question

#include <stdio.h>
#include <assert.h>

char* hex_2_base64(char *_hex)
{
  char *hex_2_bin[16] = { "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111" };
  char *dec_2_base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

  //allocating memory for binary string
  int bin_size = strlen(_hex) * 4;
  while (bin_size % 6 != 0) //add space for zero padding
    bin_size += 8;
  char *bin = malloc(bin_size + 1);
  memset(bin, 0, bin_size + 1);

  //these are for strtol, its arguments need the zero terminator
  char buf[2] = { 0 };
  char b64buf[6 + 1] = { 0 };

  //converting hex input to binary
  char *bin_end = bin;
  for (int i = 0; i < strlen(_hex); i++)
  {
    buf[0] = _hex[i];
    memcpy(bin_end, hex_2_bin[strtol(buf, NULL, 16)], 4);
    bin_end += 4;
  }

  //pad binary string w/ zeroes
  while (strlen(bin) < bin_size)
    strcat(bin, "00000000");

  //allocating memory for b64 output
  int b64size = (strlen(bin) / 6) + 1;
  char *out = malloc(b64size);
  memset(out, 0, b64size);

  //walk through binary string, converting chunks of 6 bytes into base64 chars
  char *bin_ptr = bin;
  char *out_end = out;
  int index_b64;
  while (*bin_ptr)
  {
    strncpy(b64buf, bin_ptr, 6);
    index_b64 = strtol(b64buf, NULL, 2);
    if (index_b64 == 0)
      buf[0] = '=';
    else
      buf[0] = dec_2_base64[index_b64];
    memcpy(out_end, buf, 1);
    out_end += 1;
    bin_ptr += 6;
  }

  free(bin);
  return out;
}

int main(void) {
  char *out = NULL;

  out = hex_2_base64("49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d");
  assert(strcmp(out, "SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t") == 0);
  free(out);

  //Man is distinguished, not only by his reason, but by this singular passion from other animals, which is a lust of the mind, that by a perseverance of delight in the continued and indefatigable generation of knowledge, exceeds the short vehemence of any carnal pleasure.
  out = hex_2_base64("4d616e2069732064697374696e677569736865642c206e6f74206f6e6c792062792068697320726561736f6e2c2062757420627920746869732073696e67756c61722070617373696f6e2066726f6d206f7468657220616e696d616c732c2077686963682069732061206c757374206f6620746865206d696e642c20746861742062792061207065727365766572616e6365206f662064656c6967687420696e2074686520636f6e74696e75656420616e6420696e6465666174696761626c652067656e65726174696f6e206f66206b6e6f776c656467652c2065786365656473207468652073686f727420766568656d656e6365206f6620616e79206361726e616c20706c6561737572652e");
  assert(strcmp(out, "TWFuIGlzIGRpc3Rpbmd1aXNoZWQsIG5vdCBvbmx5IGJ5IGhpcyByZWFzb24sIGJ1dCBieSB0aGlzIHNpbmd1bGFyIHBhc3Npb24gZnJvbSBvdGhlciBhbmltYWxzLCB3aGljaCBpcyBhIGx1c3Qgb2YgdGhlIG1pbmQsIHRoYXQgYnkgYSBwZXJzZXZlcmFuY2Ugb2YgZGVsaWdodCBpbiB0aGUgY29udGludWVkIGFuZCBpbmRlZmF0aWdhYmxlIGdlbmVyYXRpb24gb2Yga25vd2xlZGdlLCBleGNlZWRzIHRoZSBzaG9ydCB2ZWhlbWVuY2Ugb2YgYW55IGNhcm5hbCBwbGVhc3VyZS4=") == 0);
  free(out);

  //f
  out = hex_2_base64("66");
  assert(strcmp(out, "Zg==") == 0);
  free(out);

  //fo
  out = hex_2_base64("666f");
  assert(strcmp(out, "Zm8=") == 0);
  free(out);

  //foo
  out = hex_2_base64("666f6f");
  assert(strcmp(out, "Zm9v") == 0);
  free(out);

  //foob
  out = hex_2_base64("666f6f62");
  assert(strcmp(out, "Zm9vYg==") == 0);
  free(out);

  //fooba
  out = hex_2_base64("666f6f6261");
  assert(strcmp(out, "Zm9vYmE=") == 0);
  free(out);

  //foobar
  out = hex_2_base64("666f6f626172");
  assert(strcmp(out, "Zm9vYmFy") == 0);
  free(out);

  printf("OK!");

  return 0;
}

Answer 1

Base 16 -> Base 2 -> Base 64: Cut out the middleman

You are currently converting each hex digit to 4 binary digits, then converting 6 binary digits into one Base64 digit. Instead of doing two conversions, how about if you took each three hex digits (= 12 binary digits) and converted that into two Base64 digits? You can do this up until the end of your hex string, where you might have 1 or 2 leftover hex digits. You can handle those leftover digits by padding with extra zero bits and outputting extra Base64 digits, including the special '=' digit.

Bug

Your code doesn't convert zeros correctly. The problem is here:

if (index_b64 == 0)
  buf[0] = '=';
else
  buf[0] = dec_2_base64[index_b64];

As you can see, you output '=' for each Base64 zero digit. However, the correct digit to output is 'A'. The special '=' digit is only used to indicate zero bits for padding. Therefore, if I try to convert the hex string "0000", your program returns "====" when the correct answer is "AAA=".