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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115 | #include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
static unsigned char PseudoRandomHash[256] = {
1, 87, 49, 12, 176, 178, 102, 166, 121, 193, 6, 84, 249, 230, 44, 163,
14, 197, 213, 181, 161, 85, 218, 80, 64, 239, 24, 226, 236, 142, 38, 200,
110, 177, 104, 103, 141, 253, 255, 50, 77, 101, 81, 18, 45, 96, 31, 222,
25, 107, 190, 70, 86, 237, 240, 34, 72, 242, 20, 214, 244, 227, 149, 235,
97, 234, 57, 22, 60, 250, 82, 175, 208, 5, 127, 199, 111, 62, 135, 248,
174, 169, 211, 58, 66, 154, 106, 195, 245, 171, 17, 187, 182, 179, 0, 243,
132, 56, 148, 75, 128, 133, 158, 100, 130, 126, 91, 13, 153, 246, 216, 219,
119, 68, 223, 78, 83, 88, 201, 99, 122, 11, 92, 32, 136, 114, 52, 10,
138, 30, 48, 183, 156, 35, 61, 26, 143, 74, 251, 94, 129, 162, 63, 152,
170, 7, 115, 167, 241, 206, 3, 150, 55, 59, 151, 220, 90, 53, 23, 131,
125, 173, 15, 238, 79, 95, 89, 16, 105, 137, 225, 224, 217, 160, 37, 123,
118, 73, 2, 157, 46, 116, 9, 145, 134, 228, 207, 212, 202, 215, 69, 229,
27, 188, 67, 124, 168, 252, 42, 4, 29, 108, 21, 247, 19, 205, 39, 203,
233, 40, 186, 147, 198, 192, 155, 33, 164, 191, 98, 204, 165, 180, 117, 76,
140, 36, 210, 172, 41, 54, 159, 8, 185, 232, 113, 196, 231, 47, 146, 120,
51, 65, 28, 144, 254, 221, 93, 189, 194, 139, 112, 43, 71, 109, 184, 209};
#define N 256
int PearsonHash(uint64_t macAddr)
{
int i;
uint8_t h[sizeof(uint64_t)];
int result;
bzero(h, sizeof(h));
for(i=1; i<sizeof(h); i++)
{
uint8_t byte = (uint8_t)(macAddr & 0xff);
h[i] = PseudoRandomHash[(h[i-1] ^ byte) & 0xFF];
macAddr >>= 8;
result = h[i];
}
return result;
}
typedef struct
{
uint64_t macAddr;
int aid;
} RecordT;
RecordT* buildHashTable(int sz)
{
RecordT *p = calloc(sz, sizeof(RecordT));
return p;
}
void addRecord(RecordT* table, RecordT* rec)
{
int slot = PearsonHash(rec->macAddr);
table[slot].macAddr = rec->macAddr;
table[slot].aid = rec->aid;
}
RecordT* findRecord(RecordT *table, uint64_t mac)
{
int slot = PearsonHash(mac);
return &table[slot];
}
int main()
{
int i;
int n;
const uint64_t MacBase = 0x000011BABEBEEF00ULL;
uint64_t macTable[N];
for(i=0; i<N; i++)
{
printf(" %03u ", PseudoRandomHash[i]);
if ((i+1)%16 == 0)
printf("\n");
}
RecordT *hashTable = buildHashTable(N);
for(i=0; i<N; i++)
{
uint64_t mac;
macTable[i] = mac = MacBase + i;
}
for(i=0; i<N; ++i)
{
RecordT rec;
rec.macAddr = macTable[i];
rec.aid = N-i;
addRecord(hashTable, &rec);
}
for(i=0; i<N; i++)
{
printf("%d\t %08lX: \tSlot=%u\n", i, macTable[i], PearsonHash(macTable[i]));
}
for(int k=0; k<N; ++k)
{
uint64_t mac = macTable[k];
RecordT *p = findRecord(hashTable, mac);
printf("mac[%d]=%08lX \trec(%08lX,%d)\n", k, macTable[k], p->macAddr, p->aid);
}
free(hashTable);
} |
