Thursday, July 2, 2020

Mac Hash Table 


 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);
}
Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)