HackSoc's attempt on the XKCD challenge

xkcd.c

/* This needs the Skein functions from the NIST distribution. You can
 * get the zip file from http://www.schneier.com/skein.html ("Source
 * code and test vectors for Skein and Threefish (12 MB)"), and then
 * you need to stick the contents of NIST/CD/Reference_Implementation
 * in the same directory as this file.
 *
 * Compile with clang -std=c99 *.c -lcurl -lpthread -O3 -o xkcd-skein
 */

#include <time.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#include <curl/curl.h>
#include <string.h>
#include <pthread.h>
#include <sys/time.h>
#include <signal.h>
#include "skein.h"

/* The number of bits to use for the Skein 1024 hash */
#define SKEIN_BITS      1024
/* The length of the generated hash in bytes */
#define SKEIN_HASH_SIZE (SKEIN_BITS / 8)
/* The minimum length of our generated strings */
#define STR_MIN         1
/* The maximum length of our generated strings */
#define STR_MAX         30
/* The number of threads to run */
#define NUM_THREADS     4
/* The name of our institution */
#define INSTITUTION     "york.ac.uk"
/* The allowed characters in the generated strings */
#define ALLOWED         "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"
/* The length of allowed characters */
#define ALLOWED_LEN     (sizeof(ALLOWED) - 1)
/* The granularity of the counting (power of 2) */
#define COUNT_GRANULARITY 16384
/* The timer update */
#define TIMER_INTERVAL  5

size_t best = SKEIN_BITS + 1;
size_t count = 0;
size_t elapsed = 0;
pthread_mutex_t best_mutex = PTHREAD_MUTEX_INITIALIZER;

/* The xkcd-provided hash */
const uint8_t xkcdhash[] =
  {0x5b, 0x4d, 0xa9, 0x5f, 0x5f, 0xa0, 0x82, 0x80, 0xfc, 0x98, 0x79, 0xdf,
   0x44, 0xf4, 0x18, 0xc8, 0xf9, 0xf1, 0x2b, 0xa4, 0x24, 0xb7, 0x75, 0x7d,
   0xe0, 0x2b, 0xbd, 0xfb, 0xae, 0x0d, 0x4c, 0x4f, 0xdf, 0x93, 0x17, 0xc8,
   0x0c, 0xc5, 0xfe, 0x04, 0xc6, 0x42, 0x90, 0x73, 0x46, 0x6c, 0xf2, 0x97,
   0x06, 0xb8, 0xc2, 0x59, 0x99, 0xdd, 0xd2, 0xf6, 0x54, 0x0d, 0x44, 0x75,
   0xcc, 0x97, 0x7b, 0x87, 0xf4, 0x75, 0x7b, 0xe0, 0x23, 0xf1, 0x9b, 0x8f,
   0x40, 0x35, 0xd7, 0x72, 0x28, 0x86, 0xb7, 0x88, 0x69, 0x82, 0x6d, 0xe9,
   0x16, 0xa7, 0x9c, 0xf9, 0xc9, 0x4c, 0xc7, 0x9c, 0xd4, 0x34, 0x7d, 0x24,
   0xb5, 0x67, 0xaa, 0x3e, 0x23, 0x90, 0xa5, 0x73, 0xa3, 0x73, 0xa4, 0x8a,
   0x5e, 0x67, 0x66, 0x40, 0xc7, 0x9c, 0xc7, 0x01, 0x97, 0xe1, 0xc5, 0xe7,
   0xf9, 0x02, 0xfb, 0x53, 0xca, 0x18, 0x58, 0xb6};

/**
 * Generate a random number in a given range (inclusive)
 */
static inline size_t randrange(size_t min, size_t max)
{
  return (rand() % (1 + max - min)) + min;
}

/**
 * Generate a random string of the given length
 */
void randbytes(char *out, size_t len)
{
  for(size_t i = 0; i < len; i++)
    out[i] = ALLOWED[randrange(0, ALLOWED_LEN)];

  out[len] = '\0';
}

/**
 * Calculate the difference between the two strings
 */
size_t distance(const uint8_t* str1, const uint8_t* str2, size_t len)
{
  size_t score = 0;

  for(size_t i = 0; i < len; i++)
    score += __builtin_popcountll(str1[i] ^ str2[i]);

  return score;
}

/**
 * Convert a string of bytes into a hexadecimal string
 */
void to_hex(const uint8_t* str, char *out, size_t len)
{
  char* p = out;

  for(size_t i = 0; i < len; i++)
    p += sprintf(p, "%.2x", str[i]);

  *p = '\0';
}

/**
 * Calculate the Skein 1024 hash of a string
 */
static inline void hash(const char* str, size_t len, size_t bytes,
                        uint8_t skeinhash[SKEIN_HASH_SIZE])
{
  Skein1024_Ctxt_t ctx;

  Skein1024_Init(&ctx, bytes);
  Skein1024_Update(&ctx, (uint8_t *)str, len);
  Skein1024_Final(&ctx, skeinhash);
}

/**
 * Discard the curl output
 */
size_t curl_devnull(char *ptr, size_t size, size_t nmemb, void *userdata)
{
  return size * nmemb;
}

/**
 * Submit a string to xkcd
 */
void submit_to_xkcd(const char* str)
{
  CURL *curl;
  CURLcode res;
  char postdata[STR_MAX + 12] = "hashable=";

  strcat(postdata, (char*)str);

  curl = curl_easy_init();
  if(curl) {
    curl_easy_setopt(curl, CURLOPT_URL, "http://almamater.xkcd.com/?edu=" INSTITUTION);
    curl_easy_setopt(curl, CURLOPT_POSTFIELDS, postdata);
    curl_easy_setopt(curl, CURLOPT_WRITEFUNCTION, curl_devnull);

    res = curl_easy_perform(curl);

    curl_easy_cleanup(curl);
  }
}

void* threaded_solver(void* data)
{
  size_t threadid = (size_t)data;
  uint8_t skeinhash[SKEIN_HASH_SIZE];
  char str[STR_MAX + 1];
  size_t mybest = best;
  size_t mycount = 0;

  printf("Thread %zu started.\n", threadid);

  while(true) {
    size_t len = randrange(STR_MIN, STR_MAX);
    randbytes(str, len);

    hash(str, len, SKEIN_BITS, skeinhash);
    size_t score = distance(skeinhash, xkcdhash, SKEIN_HASH_SIZE);
    mycount++;

    if (!(mycount & (COUNT_GRANULARITY - 1)))
      __sync_fetch_and_add(&count, COUNT_GRANULARITY);

#ifdef __APPLE__
    if (mybest > score) {
      mybest = score;
      if (best > mybest) {
        pthread_mutex_lock(&best_mutex);
        if (best > mybest) {
          printf("[%zu] New best string: %s (old: %zu) (new: %zu)\n", threadid, str, mybest, score);
          best = mybest;
          submit_to_xkcd(str);
        }
        pthread_mutex_unlock(&best_mutex);
      }
    }
#else
    while (mybest > score) {
      if (__sync_bool_compare_and_swap(&best, mybest, score)) {
        printf("[%d] New best string: %s (old: %d) (new: %d)\n", threadid, str, mybest, score);
        mybest = score;
        submit_to_xkcd(str);
      } else {
        mybest = best;
      }
    }
#endif
  }
}

static inline void set_timer()
{
  struct itimerval tout_val;

  tout_val.it_interval.tv_sec = 0;
  tout_val.it_interval.tv_usec = 0;
  tout_val.it_value.tv_sec = TIMER_INTERVAL;
  tout_val.it_value.tv_usec = 0;

  setitimer(ITIMER_REAL, &tout_val,0);
}

void alarm_benchmark(int i)
{
  signal(SIGALRM, alarm_benchmark);
  elapsed += TIMER_INTERVAL;

  printf("Count: %zu, Elapsed: %zu, Speed: %g hash/sec\n",
         count, elapsed,
         (double)count / (double)elapsed);

  set_timer();
}

int main(void)
{
  srand((unsigned int) time(NULL));
  curl_global_init(CURL_GLOBAL_ALL);

  pthread_t threads[NUM_THREADS];

  // Start the benchmarking.
  set_timer();
  signal(SIGALRM, alarm_benchmark);

  // Fire off the threads.
  if (NUM_THREADS == 1) {
    threaded_solver(NULL);
  } else {
    for(size_t i = 0; i < NUM_THREADS; i++)
      pthread_create(&(threads[i]), NULL, threaded_solver, (void*) i);

    for(size_t i = 0; i < NUM_THREADS; i++)
      pthread_join(threads[i], NULL);
  }

  curl_global_cleanup();
}