#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <assert.h>

#define ARRAY_LENGTH(a) (sizeof (a) / sizeof (a)[0])

int main(int argc, char *argv[])
{
	/* nice big primes: 0x5b6d745d 0x1f821e2d */
	const uint32_t prime = 0x1f821e2d;
	uint32_t end_prime;
	uint32_t pixels[64];
	uint32_t hash, verify, inverse, p;
	int i, j, length = 8;

	end_prime = 1;
	for (i = 0; i < length; i++)
		end_prime *= prime;

	/* We don't need the inverse, we just compute it for fun. */
	inverse = 1;
	p = prime;
	for (i = 0; i < 31; i++) {
		inverse *= p;
		p *= p;
	}

	/* Verify the inverse really is the inverse. */
	for (i = 0; i < 10; i++) {
		p = random();
		printf("%08x * %08x = %08x, %08x * %08x (inverse) = %08x ",
		       prime, p, prime * p,
		       prime * p, inverse,
		       prime * p * inverse);
		if (p == prime * p * inverse)
			printf("(ok!)\n");
		else
			printf("(bad!)\n");
	}

	printf("prime %08x, inverse %08x, end_prime %08x\n",
	       prime, inverse, end_prime);

	for (i = 0; i < ARRAY_LENGTH(pixels); i++)
		pixels[i] = random();

	hash = 0;
	for (i = 0; i < length; i++)
		hash = hash * prime + pixels[i];

	for (i = length; i < ARRAY_LENGTH(pixels); i++) {
		printf("%08x ", pixels[i]);

		verify = 0;
		for (j = 0; j < length; j++)
			verify = verify * prime + pixels[i - length + j];

		printf("%08x ", hash);
		if (hash == verify)
			printf("(ok!)\n");
		else
			printf("(should be %08x)\n", verify);

		hash = hash * prime + pixels[i] -
			pixels[i - length] * end_prime;
	}

	printf("\n");

	return 0;
}