使用CRC20算法对IP五元组hash键值计算

发布于

本文主要对IP五元组的key值计算进行说明

通过对IP五元组计算得出一个int类型的值。

1 常见的hash算法步骤：

  • 1 初始化hash数组，如char a200；
  • 2 对需要存储的数据求hash的key，求key值的得法一般有：

a. 利用异或，然后求模得到key

b. 利用crc32，crc16，sha，md5等进行key值计算

c. 其他

  • 3 在相应的key值位置分配内存，并存储数据

     如：得到的key为100，那么a100=malloc(...)，存储数据

2 crc算法介绍

crc算法是用来校验使用，可以自行查看crc算法的一些介绍，目前利用此算法进行hash也不少，本方法提出crc20算法来进行hash计算,crc的生成多项式有下：

名称

生成多项式

简记式

CRC-4

x^4+x+1

3

CRC-12

x^12+x^11+x^3+x+1

-

CRC-16

x^16+x^15+x^2+1

8005

CRC-ITU**

x^16+x^12+x^5+1

1021

CRC-20

x^20+x^12+x^8+1

01101

CRC-32

x^32+x^26+x^23+...+x^2+x+1

04C11DB7

CRC-32c

x^32+x^28+x^27+...+x^8+x^6+1

1EDC6F41

3 利用CRC20多项式来计算五元组hash

利用CRC20多项式来计算五元组（源IP 源端口 目的IP 目的端口 协议）的hash，取得计算得来的值的后20位作为key值：

  • 1 假设五元组结构如下：
代码语言：c
复制
typedef struct pkt_info {
    unsigned int   srcip;
    unsigned short sport;
    unsigned int   dstip;
    unsigned short dport;
    unsigned short proto;
} pkt_info;
  • 2 CRC20_key函数的定义实现：
代码语言：c
复制
#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值
}
  • 3 计算key值：
代码语言：c
复制
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));
#tcp/ip#hash