Last active
April 21, 2023 23:28
-
-
Save skeeto/65e74302355bb5e51af639738f2ef872 to your computer and use it in GitHub Desktop.
Avalanche matrix graphs for various hash functions
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment