crc学习

​ 循环冗余校验（英语：Cyclic redundancy check，通称“CRC”）是一种根据网络数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者存储之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。由于本函数易于用二进制的电脑硬件使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误，因此获得广泛应用。redis学习、“计算机网络”、“计算机组成”等都有提及。

1、简介

​ 循环冗余校验（英语：Cyclic redundancy check，通称“CRC”）是一种根据网络数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者存储之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。由于本函数易于用二进制的电脑硬件使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误，因此获得广泛应用。redis学习、“计算机网络”、“计算机组成”等都有提及。

2、算法原理

已知：
	（1）需要发送16位的二进制信息g=1010110010001111,二进制码可表示为多项式g(x) = x^15 + x^13 + x^11 + x^10 + x^7 + x^3 + x^2 + x^1 + 1(15阶)
	（2）生成多项式为m阶多项式h(x),对应的二进制信息为h
计算：	
	 g后加m个0，然后除以h，计算采用XOR(逻辑异或) ,得到的余项r。
	 r就是CRC编码。

3、计算实例

设计算机准备传送的信息是：1010110010001111，生成多项式是h(x) = x^5 + x^2 + 1 ，计算校验位，写出CRC
码。

解答：

生成多项式 h(x) = x^5 + x^2 + 1 = 100101
首先将准备传送的信息左移5位：101011001000111100000
然后101011001000111100000 / 100101,余数 = 10011。（xor运算）
所以CRC码=10011

发送方：发送的真实数据为：101011001000111110011
接收方：101011001000111110011 / 100101,余数 = 0信息正确。（xor运算）

4、计算机模拟过程java

/**
 * 测试： 解决场景:把1亿的用户 存储在一个队列里，过大。用sharding 摸拟redis 集群 sharding Redis
 * 集群使用数据分片（sharding）而非一致性哈希（consistency hashing）来实现： 一个 Redis 集群包含 16384
 * 个哈希槽（hash slot）， 数据库中的每个键都属于这 16384 个哈希槽的其中一个， 集群使用公式 CRC16(key) % 16384 来计算键
 * key 属于哪个槽， 其中 CRC16(key) 语句用于计算键 key 的 CRC16 校验和 。
 * <p>
 *
 * @author dailong
 * @date 2019/10/16
 */
public class CRC16Util {

    public final static int maxInt = 1000;// 00000;//1亿
    public final static int USER_KEY_SLOT_COUNT = 20; // 定议分配存储用户的Slot位

    /******************************************************************************
     * Compilation: javac CRC16CCITT.java Execution: java CRC16CCITT s
     * Dependencies:
     *
     * Reads in a sequence of bytes and prints out its 16 bit Cylcic Redundancy
     * Check (CRC-CCIIT 0xFFFF).
     *
     * 1 + x + x^5 + x^12 + x^16 is irreducible polynomial.
     *
     * % java CRC16-CCITT 123456789 CRC16-CCITT = 29b1
     *
     ******************************************************************************/

    public static int crc16(final byte[] buffer) {
        // 总槽数 initial value 65535
        int crc = 0xFFFF;
        // CRC-16常见的标准h(x)  0001 0000 0010 0001 (0, 5, 12)
        int polynomial = 0x1021;
        for (byte b : buffer) {
            for (int i = 0; i < 8; i++) {
                boolean bit = ((b >> (7 - i) & 1) == 1);
                boolean c15 = ((crc >> 15 & 1) == 1);
                crc <<= 1;
                if (c15 ^ bit) {
                    crc ^= polynomial;
                }
            }
        }
        return crc & 0xffff;
    }

    /**
     * @param buffer 字节数组
     * @return
     */
    static int crc162(final byte[] buffer) {
        int crc = 0xFFFF;

        for (int j = 0; j < buffer.length; j++) {
            crc = ((crc >>> 8) | (crc << 8)) & 0xffff;
            // byte to int, trunc sign
            crc ^= (buffer[j] & 0xff);
            crc ^= ((crc & 0xff) >> 4);
            crc ^= (crc << 12) & 0xffff;
            crc ^= ((crc & 0xFF) << 5) & 0xffff;
        }
        crc &= 0xffff;
        return crc;
    }


    /**
     * 如果存储有压力，可调大槽位
     * @param args 入参
     */
    public static void main(String[] args) throws IOException {

/*        // int 不用crc16
        for (int i = 1; i < maxInt; i++) {
            // 根据玩家id 分布指定到Slot位
            int ranInt = i % USER_KEY_SLOT_COUNT;
            String key = "key:" + ranInt;
            System.out.println("key:" + key);

            // redisList.lpush(randomKey, String.valueOf(playerId));
        }*/

        String a = "init_tager_temp";
        int soltCount = 2<<14;
        //集群也是用这种方式分配key crc16 redis
        int solt1 = crc16(a.getBytes()) % soltCount;
        int solt2 = crc162(a.getBytes()) % soltCount;

        String key1 = "key:" + solt1;
        String key2 = "key:" + solt2;
        System.out.println("crc%solt=key:" + key1);
        System.out.println("crc%solt=key:" + key2);
    }

}

5、redis与crc

(1)、哈希槽运算

​ redis集群使用哈希槽实现，其对key进行哈希计算采用crc16(key) & 0x3fff（16383）,得到在16384个槽的其中一个，每个槽对应一个redis节点，如果为当前节点则执行请求，否则返回重定向节点操作。CRC16算法产生的hash值有16bit，该算法可以产生2^16-=65536个值。

计算过程 https://blog.csdn.net/qq_16097611/article/details/82428397
为什么redis计算crc-16使用查表法：https://blog.csdn.net/guodongxiaren/article/details/44706613
为什么Redis集群有16384个槽 https://www.cnblogs.com/rjzheng/p/11430592.html

6、引用

https://www.jianshu.com/p/cb62b77d0359
https://www.cnblogs.com/rjzheng/p/11430592.html
https://blog.csdn.net/guodongxiaren/article/details/44706613
https://blog.csdn.net/qq_16097611/article/details/82428397

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： 初心
• 本文链接： http://funzzz.fun/2021/01/04/crc循环冗余码/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！