使用CRC20算法对ip信息五元组hash键值计算

本文主要对ip信息五元组的key值计算进行说明
常见的hash算法步骤:
    1. 初始化hash数组,如char *a[200];
    2. 对需要存储的数据求hash的key
        求key值的得法一般有:
        1) 利用异或,然后求模得到key
        2) 利用crc32,crc16,sha,md5等进行key值计算
        3) 其他
    3. 在相应的key值位置分配内存,并存储数据
        如:得到的key为100,那么a[100]=malloc(...),存储数据
crc算法是用来校验使用,可以自行查看crc算法的一些介绍,目前利用此算法进行hash也不少,本方法提出crc20算法来进行hash计算,crc的生成多项式有下:

而本文的crc20的多项式为:x^20+x^12+x^8+1,简记式为:01101;
利用此多项式来计算五元组(源IP 源端口 目的IP 目的端口 协议)的hash,取得计算得来的值的后20位作为key值:
1.假设五元组结构如下:

typedef struct pkt_info{
    unsigned int srcip;
    unsigned short sport;
    unsigned int dstip;
    unsigned short dport;
    unsigned short proto;
}pkt_info;

2.计算key值:

pkt_info ptf;
unsigned int key=0;
/*假设此结构里面的数据*/
ptf.srcip=...
ptf.sport=...
ptf.dstip=...
ptf.dport=...
ptf.proto=...
/*计算key*/
key=CRC20_key((unsigned char *)&ptf,sizeof(pkt_info));

3. CRC20_key函数的定义实现:

#define POLY 0x01101 // CRC20生成多项式x^20+x^12+x^8+1即:01101 CRC32:04C11DB7L
static unsigned int crc_table[256];
unsigned int get_sum_poly(unsigned char data)
{
    unsigned int sum_poly = data;
    int j;
    sum_poly <<= 24;
    for(j = 0; j < 8; j++)
    {
        int hi = sum_poly&0x80000000; // 取得reg的最高位
        sum_poly <<= 1;
        if(hi) sum_poly = sum_poly^POLY;
    }
    return sum_poly;
}
void create_crc_table(void)  //在使用CRC20_key函数应该先建立crc表
{
    int i;
    for(i = 0; i < 256; i++)
    {
    crc_table[i] = get_sum_poly(i&0xFF);
    }
}
unsigned int CRC20_key(unsigned char* data, int len)
{
    int i;
    unsigned int reg = 0xFFFFFFFF;// 0xFFFFFFFF，见后面解释
    for(i = 0; i < len; i++)
    {
        reg = (reg<<8) ^ crc_table[(reg>>24)&0xFF ^ data[i]];
    }
    return (reg&0XFFFFF);//得到的reg取后20作为key值
}

注:初始化hash数组大小确定:
#define maxhash    1<<20
pkt_info *root
root=malloc(maxhash * sizeof(pkt_info *));

冲突的解决方法可以采用链表方式,即同一个key值位置元素不同,在此位置用链表向后连接,可以查看linux的内核链表,或者自己实现