2
\$\begingroup\$

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;
}
\$\endgroup\$
3
\$\begingroup\$

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=".

\$\endgroup\$
  • \$\begingroup\$ I've revised the code and made a new question. It is here if you're interested in taking a look. \$\endgroup\$ – liewl Oct 20 '16 at 18:53

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.