Generates a table for Pearson hashing, using Fisher-Yates.

pearson-hashing.c

//
// Generates a table for Pearson hashing.
//

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

// Uniformly distributed random value between [min, max].
static unsigned random(unsigned min, unsigned max) {
  const unsigned range = 1 + max - min;
  const unsigned buckets = RAND_MAX / range;
  const unsigned limit = buckets * range;

  unsigned candidate;

  do {
    candidate = rand();
  } while (candidate >= limit);

  return min + (candidate / buckets);
}

void swap(unsigned char *x, unsigned char *y) {
  if (x != y) {
    *x ^= *y;
    *y ^= *x;
    *x ^= *y;
  }
}

int main(int argc, const char *argv[]) {
  // Seed the standard random number generator.
  srand(time(NULL));

  unsigned char T[256];

  for (unsigned i = 0; i <= 255; ++i)
    T[i] = i;

  // Fisher-Yates shuffle w/ Durstenfeld's trick.
  for (unsigned i = 255, j = random(0, 255); i >= 1; --i, j = random(0, i))
    swap(&T[i], &T[j]);

  // Produce a nicely formatted table.
  printf("static const unsigned char T[256] = {\n"); {
    for (unsigned y = 0; y < 16; ++y) {
      printf("  ");
      for (unsigned x = 0; x < 16; ++x)
        printf("%3u, ", (unsigned)T[y * 16 + x]);
      printf("\n");
    }
  } printf("};\n");

  return EXIT_SUCCESS;
}