=====================================================
redis源码学习系列文章：
redis源码分析之内存编码分析intset, ziplist编码分析
redis源码分析之对象系统源码分析string, list链表,hash哈希,set集合,zset有序集合
redis源码分析之异步进程保存数据rdb文件和aof文件源码分析
redis源码分析之集群之一的槽的分配算法crc16原理分析
=====================================================
在我的github上会持续更新Redis代码的中文分析，地址送出https://github.com/chensongpoixs/credis_source，共同学习进步
前言
redis中为什么单线程效率怎么高呢， 其中很大一部分是redis使用哈希算法查询的效率都O(1), 今天我们来分析我们redis中集群使用crc16这种哈希算法呢，而不使用正常redis使用siphash,MurmurHash64A这个两个哈希算法呢
正文
一, 聊一聊 哈希算法
哈希算法有分为大致的两种一种是不开破解的，另外一种就可破解
不可破解也不是绝对的相对一些简单是可以破解的
不可破解: md5, sha1等等
可以破解:siphash, MurmurHash64A,crc 的系列等等
正常md5，sha1是用来加密使用， 一个因为他们是很难被破解的，还有他们每次计算都对CPU的消化非常比siphash和MurmurHash64A的时间长，
想siphash和MurmurHash64A哈希算法是用来作为线性分布的一个是线性分布非常均匀性，满射性，确定性， 快速性
而我们本文章主要分析是crc16算法， 也是线性分布的一个是线性分布非常均匀性，满射性，确定性， 而且哈希碰撞比siphash和MurmurHash64A还要小很多， 就是有一个缺点是和md5，sha1算法一样对CPU占用的时间非常长，这就redis为什么集群使用这个crc16算法。
二, crc系列的算法
crc是正常用于网络层差错检测使用的
这就有crc8,crc16,crc32,crc64一些标准
CRC编码的基本思想是：将二进制位串的操作被解释为多项式算法运算。
二进制数据可以看作是一个k-1 次多项式的系数列表，该多项式共有k项，从x^(k-1)到x^0。这样的多项式被认为是k-1阶多项式。高次(左边)位是x^(k-1)项的系数，接下来的位是x(k-2)项的系数，以此类推。例如： 100101有6位，因此代表了一个有6项的多项式，其系数分别是1、0、0、1、0和1, 即1x^5 + 0x^4 + 0x^3 + 1x^2 + 0x^1 + 1x^0 == x^5 + x^2 + 1。
CRC-8 x8+x5+x4+1 0x31（0x131）
CRC-8 x8+x2+x1+1 0x07（0x107）
CRC-8 x8+x6+x4+x3+x2+x1 0x5E（0x15E）
三, crc16的表的生成
crc16
* Name : "XMODEM", also known as "ZMODEM", "CRC-16/ACORN"
* Width : 16 bit
* Poly : 1021 (That is actually x^16 + x^12 + x^5 + 1) ==>Poly_src 1 0001 0000 0010 0001
* Initialization : 0000
* Reflect Input byte : False
* Reflect Output CRC : False
* Xor constant to output CRC : 0000
* Output for "123456789" : 31C3
对应poly = 1 0001 0000 0010 0001
举例编码串是 0001， 多项式是 1 0001 0000 0010 0001
0001向左16位-> crc1-> 0001 0000 0000 0000 0000 0000
计算
先和编码串crc1 前16位进行或操作
1 0000 0000 0000 0000 0000
^ 1 0001 0000 0010 0001
0 0001 0000 0010 0001
得到 1 0000 0010 0001 -> 把后面4个bit添加得到crc2 -> 1 0000 0010 0001 0000
crc2就是对应表中1下标0x1021的值
现在由于crc2bit小于16就结束了如果不小于16就接着前16位进行或操作
下面是生成 crc16的表的生成的程序
static const uint16_t crc16tab[256]= {
0x0000,0x1021 /*0001 0000 0010 0001*/,0x2042 /*0010 0000 0100 0010*/,0x3063 /*0011 0000 0110 0011*/,0x4084 /*100000010000100*/,0x50a5/*101000010100101*/,0x60c6 /*110000011000110*/,0x70e7/*111000011100111*/,
0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef,
0x1231,0x0210,0x3273,0x2252,0x52b5,0x4294,0x72f7,0x62d6,
0x9339,0x8318,0xb37b,0xa35a,0xd3bd /*1101001110111101*/,0xc39c,0xf3ff,0xe3de,
0x2462,0x3443,0x0420,0x1401,0x64e6,0x74c7,0x44a4,0x5485,
0xa56a,0xb54b,0x8528,0x9509,0xe5ee,0xf5cf,0xc5ac,0xd58d,
0x3653,0x2672,0x1611,0x0630,0x76d7,0x66f6,0x5695,0x46b4,
0xb75b,0xa77a,0x9719,0x8738,0xf7df,0xe7fe,0xd79d,0xc7bc,
0x48c4,0x58e5,0x6886,0x78a7,0x0840,0x1861,0x2802,0x3823,
0xc9cc,0xd9ed,0xe98e,0xf9af,0x8948,0x9969,0xa90a,0xb92b,
0x5af5,0x4ad4,0x7ab7,0x6a96,0x1a71,0x0a50,0x3a33,0x2a12,
0xdbfd,0xcbdc,0xfbbf,0xeb9e,0x9b79,0x8b58,0xbb3b,0xab1a,
0x6ca6,0x7c87,0x4ce4,0x5cc5,0x2c22,0x3c03,0x0c60,0x1c41,
0xedae,0xfd8f,0xcdec,0xddcd,0xad2a,0xbd0b,0x8d68,0x9d49,
0x7e97,0x6eb6,0x5ed5,0x4ef4,0x3e13,0x2e32,0x1e51,0x0e70,
0xff9f,0xefbe,0xdfdd,0xcffc,0xbf1b,0xaf3a,0x9f59,0x8f78,
0x9188,0x81a9,0xb1ca,0xa1eb,0xd10c,0xc12d,0xf14e,0xe16f,
0x1080,0x00a1,0x30c2,0x20e3,0x5004,0x4025,0x7046,0x6067,
0x83b9,0x9398,0xa3fb,0xb3da,0xc33d,0xd31c,0xe37f,0xf35e,
0x02b1,0x1290,0x22f3,0x32d2,0x4235,0x5214,0x6277,0x7256,
0xb5ea,0xa5cb,0x95a8,0x8589,0xf56e,0xe54f,0xd52c,0xc50d,
0x34e2,0x24c3,0x14a0,0x0481,0x7466,0x6447,0x5424,0x4405,
0xa7db,0xb7fa,0x8799,0x97b8,0xe75f,0xf77e,0xc71d,0xd73c,
0x26d3,0x36f2,0x0691,0x16b0,0x6657,0x7676,0x4615,0x5634,
0xd94c,0xc96d,0xf90e,0xe92f,0x99c8,0x89e9,0xb98a,0xa9ab,
0x5844,0x4865,0x7806,0x6827,0x18c0,0x08e1,0x3882,0x28a3,
0xcb7d,0xdb5c,0xeb3f,0xfb1e,0x8bf9,0x9bd8,0xabbb,0xbb9a,
0x4a75,0x5a54,0x6a37,0x7a16,0x0af1,0x1ad0,0x2ab3,0x3a92,
0xfd2e,0xed0f,0xdd6c,0xcd4d,0xbdaa,0xad8b,0x9de8,0x8dc9,
0x7c26,0x6c07,0x5c64,0x4c45,0x3ca2,0x2c83,0x1ce0,0x0cc1,
0xef1f,0xff3e,0xcf5d,0xdf7c,0xaf9b,0xbfba,0x8fd9,0x9ff8,
0x6e17,0x7e36,0x4e55,0x5e74,0x2e93,0x3eb2,0x0ed1 /*1110 1101 0001*/,0x1ef0 /*1 1110 1111 0000*/
};
/**
*获取value二进制的位数
*/
int byte_size(unsigned int value)
{
int byte = 0;
if (value == 0)
{
return byte;
}
while (value >>= 1)
{
++byte;
}
return byte;
}
void show_crc16_table()
{
int i = 0;
int poly = 0X11021;//
//start of calculating the CRC8 table
for (i = 0;i < 256; ++i)
{
table[i] = i;
}
FILE * fp = NULL;
fp = fopen("crc16_table.txt", "w+");
if (!fp)
{
printf("not open file !!!\n");
return -1;
}
for (i = 0;i < 256; ++i)
{
// 把下标的数向左移动16位
unsigned int table1 = table[i] << 16;
int byte = byte_size(table1);
while (byte > 15)
{
byte = byte_size(table1);
//fprintf(fp, "table1 = %u, byte = %u\n", table1, byte);
if (byte > 15)
{ //进行差错计算 [x^16 + x^12 + x^5 + 1]
table1 = ((((table1 >> (byte - 16)) ) ^ poly) &0XFFFF)<< (byte - 16);
}
byte = byte_size(table1);
}
table[i] = table1 ;
}
for (i = 0; i < 256; ++i) // 256
{
if (i % 10)
{
fprintf(fp, "table[%u]=0x%.2x\n", i, table[i]);
printf( "table[%u]=0x%.2x\n", i, table[i]);
}
else
{
fprintf(fp, "table[%u]=0x%.2x\n", i, table[i]);
printf( "table[%u]=0x%.2x\n", i, table[i]);
}
}
if (fp)
{
fclose(fp);
fp = NULL;
}
}
int main(int argc, char **argv)
{
show_crc16_table();
return 0;
}
四,crc系列
几种CRC16计算公式、初始值、标志位等参数汇总
一、CRC16/IBM 或 CRC16/ARC 或 CRC16/LHA：
公式：x16+x15+x2+1
宽度：16
Poly值：0x8005
初始值：0x0000
基准输入：true
基准输出：true
标志位：0x0000
二、CRC16/MAXIM：
公式：x16+x15+x2+1
宽度：16
Poly值：0x8005
初始值：0x0000
基准输入：true
基准输出：true
标志位：0xFFFF
三、CRC16/USB：
公式：x16+x15+x2+1
宽度：16
Poly值：0x8005
初始值：0xFFFF
基准输入：true
基准输出：true
标志位：0xFFFF
四、CRC16/MODBUS(最常见)：
公式：x16+x15+x2+1
宽度：16
Poly值：0x8005
初始值：0x0000
基准输入：true
基准输出：true
标志位：0x0000
五、CRC16/CCITT 或 CRC-CCITT 或CRC16/CCITT-TRUE或 CRC16/KERMIT：
公式：x16+x15+x5+1
宽度：16
Poly值：0x1021
初始值：0x0000
基准输入：true
基准输出：true
标志位：0x0000
六、 CRC16/CCITT-FALSE：
公式：x16+x15+x5+1
宽度：16
Poly值：0x1021
初始值：0xFFFF
基准输入：false
基准输出：false
标志位：0x0000
七、CRC16/X25：
公式：x16+x15+x5+1
宽度：16
Poly值：0x1021
初始值：0x0000
基准输入：true
基准输出：true
标志位：0xFFFF
八、CRC16/XMODEM 或 CRC16/ZMODEM 或 CRC16/ACORN：
公式：x16+x15+x5+1
宽度：16
Poly值：0x1021
初始值：0x0000
基准输入：false
基准输出：false
标志位：0x0000
九、CRC16/DNP：
公式：x16+x13+x12+x11+x10+x8+x6+x5+x2+1
宽度：16
Poly值：0x3D65
初始值：0x0000
基准输入：true
基准输出：true
标志位：0xFFFF
使用：M-Bus, ect
附加其它：
一、CRC4/ITU：
公式：x4+x+1
宽度：4
Poly值：0x03
初始值：0x00
基准输入：true
基准输出：true
标志位：0x00
二、CRC5/EPC：
公式：x5+x3+1
宽度：5
Poly值：0x09
初始值：0x09
基准输入：false
基准输出：false
标志位：0x00
三、CRC5/ITU：
公式：x5+x4+x2+1
宽度：5
Poly值：0x15
初始值：0x00
基准输入：true
基准输出：true
标志位：0x00
四、CRC5/USB：
公式：x5+x2+1
宽度：5
Poly值：0x05
初始值：0x1F
基准输入：true
基准输出：true
标志位：0x1F
四、CRC6/ITU：
公式：x6+x+1
宽度：6
Poly值：0x03
初始值：0x00
基准输入：true
基准输出：true
标志位：0x00
五、CRC6/MMC：
公式：x7+x3+1
宽度：7
Poly值：0x09
初始值：0x00
基准输入：false
基准输出：false
标志位：0x00
使用：MutiMediaCard,SD卡， ect
六、CRC-8：
公式：x8+x2+x+1
宽度：8
Poly值：0x07
初始值：0x00
基准输入：false
基准输出：false
标志位：0x00
七、CRC8/ITU：
公式：x8+x2+x+1
宽度：8
Poly值：0x07
初始值：0x00
基准输入：false
基准输出：false
标志位：0x55
八、CRC-8：
公式：x8+x2+x+1
宽度：8
Poly值：0x07
初始值：0x00
基准输入：false
基准输出：false
标志位：0x00
九、CRC8/ROHC：
公式：x8+x2+x+1
宽度：8
Poly值：0x07
初始值：0xFF
基准输入：true
基准输出：true
标志位：0x00
九、CRC8/ROHC 或 DOW-CRC：
公式：x8+x5+x4+1
宽度：8
Poly值：0x31
初始值：0x00
基准输入：true
基准输出：true
标志位：0x00
