Avalanche matrix graphs for various hash functions

avalanche.c

/* Avalanche matrix visualizer
 * $ cc -Ofast -fopenmp -Wall -Wextra avalanche.c
 * This is free and unencumbered software released into the public domain.
 */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define NSAMPLES (1L << 24)
#define SCALE    24

static uint64_t
xoshiro256ss(uint64_t s[4])
{
    uint64_t x = s[1] * 5;
    uint64_t r = ((x << 7) | (x >> 57)) * 9;
    uint64_t t = s[1] << 17;
    s[2] ^= s[0];
    s[3] ^= s[1];
    s[1] ^= s[2];
    s[0] ^= s[3];
    s[2] ^= t;
    s[3] = (s[3] << 45) | (s[3] >> 19);
    return r;
}

// Turn (-1..+1) into RGB.
static unsigned long
hue(double v)
{
    unsigned long h = (int)((v + 1)*179.5) / 60;
    unsigned long f = (int)((v + 1)*179.5) % 60;
    unsigned long t = 0xff * f / 60;
    unsigned long q = 0xff - t;
    switch (h) {
    case 0: return 0xff0000UL | (t << 8);
    case 1: return (q << 16) | 0x00ff00UL;
    case 2: return 0x00ff00UL | t;
    case 3: return (q << 8) | 0x0000ffUL;
    case 4: return (t << 16) | 0x0000ffUL;
    case 5: return 0xff0000UL | q;
    }
    abort();
}

static uint64_t
dumb64(uint64_t x)
{
    x *= 0x881cf9e71fbdd5b9;
    x ^= x >> 32;
    return x;
}

static uint64_t
better64(uint64_t x)
{
    x ^= x >> 32;
    x *= 0x881cf9e71fbdd5b9;
    x ^= x >> 32;
    x *= 0xbcf746f9ee677775;
    x ^= x >> 32;
    return x;
}

static uint64_t
betterer64(uint64_t x)
{
    x ^= x >> 32;
    x *= 0xe68e0860ce559b5b;
    x ^= x >> 32;
    x *= 0xbca6b7d7acc9d61b;
    x ^= x >> 32;
    return x;
}

static uint64_t
hash64shift(uint64_t x)
{
    x = ~x + (x << 21);
    x = x ^ (x >> 24);
    x = (x + (x << 3)) + (x << 8);
    x = x ^ (x >> 14);
    x = (x + (x << 2)) + (x << 4);
    x = x ^ (x >> 28);
    x = x + (x << 31);
    return x;
}

static uint64_t
splittable64(uint64_t x)
{
    x ^= x >> 30;
    x *= 0xbf58476d1ce4e5b9;
    x ^= x >> 27;
    x *= 0x94d049bb133111eb;
    x ^= x >> 31;
    return x;
}

static uint64_t
unnamed(uint64_t x)
{
    x ^= x >> 32;
    x *= 0xd6e8feb86659fd93;
    x ^= x >> 32;
    x *= 0xd6e8feb86659fd93;
    x ^= x >> 32;
    return x;
}

static void
eval64(uint64_t (*hash)(uint64_t), FILE *f)
{
    long matrix[64][64] = {{0}};
    uint64_t s[] = {
        0x243f6a8885a308d3, 0x13198a2e03707344,
        0xa4093822299f31d0, 0x082efa98ec4e6c89,
    };

    for (long n = 0; n < NSAMPLES; n++) {
        uint64_t x = xoshiro256ss(s);
        uint64_t c = hash(x);
        for (int i = 0; i < 64; i++) {
            uint64_t o = hash(x ^ UINT64_C(1)<<i) ^ c;
            for (int j = 0; j < 64; j++) {
                matrix[i][j] += o>>j & 1;
            }
        }
    }

    long max = 0;
    for (int i = 0; i < 64; i++) {
        for (int j = 0; j < 64; j++) {
            long v = matrix[i][j] - NSAMPLES/2;
            max = labs(v) > max ? labs(v) : max;
        }
    }
    fprintf(stderr, "max = %ld\n", max);

    fprintf(f, "P6\n%d %d\n255\n", 64*SCALE/2, 64*SCALE/2);
    for (int i = 0; i < 64 * SCALE/2; i++) {
        for (int j = 0; j < 64 * SCALE/2; j++) {
            double v = matrix[i/(SCALE/2)][j/(SCALE/2)] - NSAMPLES/2;
            long c = hue(v / max);
            fputc(c >> 16, f);
            fputc(c >>  8, f);
            fputc(c >>  0, f);
        }
    }
}

static uint32_t
hash32shift(uint32_t x)
{
    x = ~x + (x << 15);
    x = x ^ (x >> 12);
    x = x + (x << 2);
    x = x ^ (x >> 4);
    x = x * 2057;
    x = x ^ (x >> 16);
    return x;
}

static uint32_t
jenkins32(uint32_t x)
{
    x = (x+0x7ed55d16) + (x<<12);
    x = (x^0xc761c23c) ^ (x>>19);
    x = (x+0x165667b1) + (x<<5);
    x = (x+0xd3a2646c) ^ (x<<9);
    x = (x+0xfd7046c5) + (x<<3);
    x = (x^0xb55a4f09) ^ (x>>16);
    return x;
}

static uint32_t
hash32shiftmult(uint32_t x)
{
    x = (x ^ 61) ^ (x >> 16);
    x = x + (x << 3);
    x = x ^ (x >> 4);
    x = x * 0x27d4eb2d;
    x = x ^ (x >> 15);
    return x;
}

static uint32_t
dumb32(uint32_t x)
{
    x *= 0x96310aa7;
    x ^= x >> 16;
    return x;
}

static uint32_t
better32(uint32_t x)
{
    x ^= x >> 16;
    x *= 0x96310aa7;
    x ^= x >> 16;
    x *= 0x74471A67;
    x ^= x >> 16;
    return x;
}

static uint32_t
betterer32(uint32_t x)
{
    x ^= x >> 16;
    x *= 0xdaaa6a5d;
    x ^= x >> 16;
    x *= 0xefe65e63;
    x ^= x >> 16;
    return x;
}

static uint32_t
lowbias32(uint32_t x)
{
    x ^= x >> 16;
    x *= 0x7feb352d;
    x ^= x >> 15;
    x *= 0x846ca68b;
    x ^= x >> 16;
    return x;
}

static uint32_t
lowerbias32(uint32_t x)
{
    x ^= x >> 16;
    x *= 0xa812d533;
    x ^= x >> 15;
    x *= 0xb278e4ad;
    x ^= x >> 17;
    return x;
}

static void
eval32(uint32_t (*hash)(uint32_t), FILE *f)
{
    long matrix[32][32] = {{0}};
    uint64_t s[] = {
        0x243f6a8885a308d3, 0x13198a2e03707344,
        0xa4093822299f31d0, 0x082efa98ec4e6c89,
    };

    for (long n = 0; n < NSAMPLES; n++) {
        uint32_t x = xoshiro256ss(s);
        uint32_t c = hash(x);
        for (int i = 0; i < 32; i++) {
            uint32_t o = hash(x ^ UINT32_C(1)<<i) ^ c;
            for (int j = 0; j < 32; j++) {
                matrix[i][j] += o>>j & 1;
            }
        }
    }

    long max = 0;
    for (int i = 0; i < 32; i++) {
        for (int j = 0; j < 32; j++) {
            long v = matrix[i][j] - NSAMPLES/2;
            max = labs(v) > max ? labs(v) : max;
        }
    }
    fprintf(stderr, "max = %ld\n", max);

    fprintf(f, "P6\n%d %d\n255\n", 32*SCALE, 32*SCALE);
    for (int i = 0; i < 32 * SCALE; i++) {
        for (int j = 0; j < 32 * SCALE; j++) {
            double v = matrix[i/SCALE][j/SCALE] - NSAMPLES/2;
            long c = hue(v / max);
            fputc(c >> 16, f);
            fputc(c >>  8, f);
            fputc(c >>  0, f);
        }
    }
}

static uint32_t
djb2(uint32_t x)
{
    uint32_t hash = 5381;
    for (int i = 0; i < 4; i++) {
        uint32_t c = x>>(i*8) & 0xff;
        hash = ((hash << 5) + hash) + c;
    }
    return hash;
}

static uint32_t
sdbm(uint32_t x)
{
    uint32_t hash = 0;
    for (int i = 0; i < 4; i++) {
        uint32_t c = x>>(i*8) & 0xff;
        hash = c + (hash << 6) + (hash << 16) - hash;
    }
    return hash;
}

static uint32_t
loselose(uint32_t x)
{
    uint32_t hash = 0;
    for (int i = 0; i < 4; i++) {
        uint32_t c = x>>(i*8) & 0xff;
        hash += c;
    }
    return hash;
}

static uint32_t
fnv1a(uint32_t x)
{
    uint32_t hash = 0x811c9dc5;
    for (int i = 0; i < 4; i++) {
        uint32_t c = x>>(i*8) & 0xff;
        hash ^= c;
        hash *= 0x01000193;
    }
    return hash;
}

int
main(void)
{
    struct {
        const char *name;
        uint64_t (*hash)(uint64_t);
    } hash64[] = {
        {"dumb64.ppm",       dumb64},
        {"better64.ppm",     better64},
        {"betterer64.ppm",   betterer64},
        {"hash64shift.ppm",  hash64shift},
        {"splittable64.ppm", splittable64},
        {"unnamed.ppm",      unnamed},
    };
    #pragma omp parallel for schedule(dynamic, 1)
    for (int i = 0; i < (int)(sizeof(hash64)/sizeof(*hash64)); i++) {
        FILE *f = fopen(hash64[i].name, "w");
        eval64(hash64[i].hash, f);
        fclose(f);
    }

    struct {
        const char *name;
        uint32_t (*hash)(uint32_t);
    } hash32[] = {
        {"hash32shift.ppm",     hash32shift},
        {"jenkins32.ppm",       jenkins32},
        {"hash32shiftmult.ppm", hash32shiftmult},
        {"dumb32.ppm",          dumb32},
        {"better32.ppm",        better32},
        {"betterer32.ppm",      betterer32},
        {"lowbias32.ppm",       lowbias32},
        {"lowerbias32.ppm",     lowerbias32},
        /* string hash functions, not expected to do well: */
        {"djb2.ppm",            djb2},
        {"sdbm.ppm",            sdbm},
        {"loselose.ppm",        loselose},
        {"fnv1a.ppm",           fnv1a},
    };
    #pragma omp parallel for schedule(dynamic, 1)
    for (int i = 0; i < (int)(sizeof(hash32)/sizeof(*hash32)); i++) {
        FILE *f = fopen(hash32[i].name, "w");
        eval32(hash32[i].hash, f);
        fclose(f);
    }
}