本文主要对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 假设五元组结构如下：
typedef struct pkt_info {
unsigned int srcip;
unsigned short sport;
unsigned int dstip;
unsigned short dport;
unsigned short proto;
} pkt_info;- 2 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值
}- 3 计算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));
