1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
#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;
}
|
