Test framework for John Regehr's Nibble Sort Programming Contest: http://blog.regehr.org/archives/1213

Makefile

test_sort: test.c
        gcc -std=gnu99 -O3 test.c -o test_sort

test.c

#include <assert.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define TEST_SIZE (1024*128)


/**** Nibble sorting algorithms ************************************************/

int regehr_read_nibble(unsigned long w, int i) {
  assert(i >= 0 && i < 16);
  unsigned long res = w >> (i * 4);
  return res & 0xf;
}

void regehr_write_nibble(unsigned long *w, int i, int v) {
  assert(i >= 0 && i < 16);
  unsigned long mask = 0xf;
  mask <<= (i * 4);
  *w &= ~mask;
  unsigned long prom = v;
  prom <<= (i * 4);
  *w |= prom;
}

unsigned long regehr_nibble_sort_word(unsigned long arg) {
  for (int i = 0; i < 16; ++i) {
    int min = i;
    for (int j = i+1; j < 16; ++j) {
      if (regehr_read_nibble(arg, j) < regehr_read_nibble(arg, min))
        min = j;
    }
    if (min != i) {
      int tmp = regehr_read_nibble(arg, i);
      regehr_write_nibble(&arg, i, regehr_read_nibble(arg, min));
      regehr_write_nibble(&arg, min, tmp);
    }
  }
  return arg;
}

void regehr_nibble_sort(unsigned long *buf)
{
  for (int i = 0; i < TEST_SIZE; i++)
  {
    buf[i] = regehr_nibble_sort_word(buf[i]);
  }
}

void my_nibble_sort(unsigned long *buf)
{
  // TODO: put your own awesome algorithm here
  regehr_nibble_sort(buf);
}


/**** Benchmarking framework ***************************************************/

unsigned long input[TEST_SIZE];
unsigned long expected_output[TEST_SIZE];
unsigned long actual_output[TEST_SIZE];

unsigned char random_byte()
{
  return rand();
}

typedef void buffer_sorter(unsigned long *buf);

void sort_buffer_timed(unsigned long *input, unsigned long *output,
    buffer_sorter * sorter)
{
  memcpy(output, input, TEST_SIZE * sizeof(unsigned long));
  clock_t start = clock();
  sorter(output);
  clock_t end = clock();
  unsigned long diff = end - start;
  assert(CLOCKS_PER_SEC == 1000000);
  printf("Time (\u00B5s): %d\n", diff);
}

void generate_input_data()
{
  srand(44);
  for (int i = 0; i < TEST_SIZE; i++)
  {
    input[i] =
      ((unsigned long)random_byte() << 0) |
      ((unsigned long)random_byte() << 8) |
      ((unsigned long)random_byte() << 16) |
      ((unsigned long)random_byte() << 24) |
      ((unsigned long)random_byte() << 32) |
      ((unsigned long)random_byte() << 40) |
      ((unsigned long)random_byte() << 48) |
      ((unsigned long)random_byte() << 56);
  }

}

int error_count;

void check_output(unsigned long *input, unsigned long *expected, unsigned long *actual)
{
  error_count = 0;
  for (int i = 0; i < TEST_SIZE; i++)
  {
    if (expected[i] != actual[i])
    {
      fprintf(stderr, "Error (i=%d, input=%lx): expected %lx, got %lx\n",
          i, input[i], expected[i], actual[i]);
      error_count++;
      if (error_count >= 100)
      {
        fprintf(stderr, "Too many errors, aborting.\n");
        return;
      }
    }
  }
}

int main()
{
  generate_input_data();
  sort_buffer_timed(input, expected_output, regehr_nibble_sort);
  sort_buffer_timed(input, actual_output, my_nibble_sort);
  check_output(input, expected_output, actual_output);
  return error_count ? 1 : 0;
}