Klavor's Blog

「算法原理」CRC检验算法原理及其Java实现

时间: 2019-06-18 / 分类: 开发 / 阅读时长: 6分钟 / 阅读次数: 0

前言

这段时间处于待业状态中，所以就自己捣鼓些东西，学习学习有趣的算法。因为对于文件的校验可以通过CRC、SHA和MD5等方式进行，所以有了一个想法，做一个文件校验的网站和应用，提供一套服务给广大用户校验文件的正确性。
因此，对于这几种校验的算法，当然要了解一下，于是从CRC开始着手。想起当初学习base64编码的时候，感觉这些算法还是挺有意思的，可以玩弄一番，虽然对就业帮助并不是很大。
这篇文章主要是记录一下查阅过的参考博客以及用java实现CRC校验算法。

参考资料

CRC检验算法原理
CRC校验原理与程序设计——(RS485总线系统应用之1)
CRC32校验原理及实现
CRC8/CRC16/CRC32常见几个标准的算法及C语言实现

常见CRC参数模型如下:

有些博客中提到多项式，例如CRC32，多项式为04C11DB7或EDB88320，其实，常用的标准CRC32的多项式应该是04C11DB7，这个标准的CRC32算法中输入值需要进行反转，而反转后的结果为EDB88320。因此，如果你是用的是04C11DB7作为多项式进行运算CRC32则需要进行反转操作，如果使用多项式EDB88320进行运算则不需要进行反转，否则将会出现结果和其他工具得到的结果不同的情况。以下是通过博客找到的一部分CRC算法的规则，在参考资料中有博客链接，这里摘抄一份备份一下。

CRC算法名称 多项式公式 宽度 多项式 初始值 结果异或值 输入值反转 输出值反转
CRC-4/ITU x4 + x + 1 4 03 00 00 true true
CRC-5/EPC x4 + x3 + 1 5 09 09 00 false false
CRC-5/ITU x5 + x4 + x2 + 1 5 15 00 00 true true
CRC-5/USB x5 + x2 + 1 5 05 1F 1F true true
CRC-6/ITU x6 + x + 1 6 03 00 00 true true
CRC-7/MMC x7 + x3 + 1 7 09 00 00 false false
CRC-8 x8 + x2 + x + 1 8 07 00 00 false false
CRC-8/ITU x8 + x2 + x + 1 8 07 00 55 false false
CRC-8/ROHC x8 + x2 + x + 1 8 07 FF 00 true true
CRC-8/MAXIM x8 + x5 + x4 + 1 8 31 00 00 true true
CRC-16/IBM x6 + x5 + x2 + 1 16 8005 0000 0000 true true
CRC-16/MAXIM x6 + x5 + x2 + 1 16 8005 0000 FFFF true true
CRC-16/USB x6 + x5 + x2 + 1 16 8005 FFFF FFFF true true
CRC-16/MODBUS x6 + x5 + x2 + 1 16 8005 FFFF 0000 true true
CRC-16/CCITT x6 + x2 + x5 + 1 16 1021 0000 0000 true true
CRC-16/CCITT-FALSE x6 + x2 + x5 + 1 16 1021 FFFF 0000 false false
CRC-16/x5 x6 + x2 + x5 + 1 16 1021 FFFF FFFF true true
CRC-16/XMODEM x6 + x2 + x5 + 1 16 1021 0000 0000 false false
CRC-16/DNP x6 + x3 + x2 + x1 + x0 + x8 + x6 + x5 + x2 + 1 16 3D65 0000 FFFF true true
CRC-32 x2 + x6 + x3 + x2 + x6 + x2 + x1 + x0 + x8 + x7 + x5 + x4 + x2 + x + 1 32 04C11DB7 FFFFFFFF FFFFFFFF true true
CRC-32/MPEG-2 x32 + x6 + x3 + x2 + x6 + x2 + x1 + x0 + x8 + x7 + x5 + x4 + x2 + x + 1 32 04C11DB7 FFFFFFFF 00000000 false false

JAVA实现CRC32检验算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
public class CRC {

    private static long[] tables = new long[256];

    /**
     * 初始化CRC字符表
     * @param poly 多项式
     * @param polySize 多项式长度
     * @param revese 是否翻转处理
     */
    public void initTable(long poly, int polySize, boolean revese) {
        if (revese) {
            poly = reversePoly(poly, polySize);
        }
        long charValue;
        for (int i = 0, length = tables.length; i < length; i++) {
            charValue = i;
            //由于ascii为8bit的字符，因此这里的maxLength为8。
            for (int j = 0; j < 8; j++) {
                if ((charValue & 0x01) == 1) {
                    charValue = (charValue >> 1) ^ poly;
                } else {
                    charValue = charValue >> 1;
                }
            }
            tables[i] = charValue;
        }
    }

    /**
     * 按位翻转
     * @param poly 多项式
     * @param bitLength 翻转长度
     * @return 翻转多项式结果
     */
    private long reversePoly(long poly, int bitLength) {
        long reversePoly = 0;
        for (int i = 0; i < bitLength; i++) {
            reversePoly <<= 1;
            reversePoly |= (poly & 0x01);
            poly >>>= 1;
        }
        return reversePoly;
    }

    /**
     * 获取整型CRC检验码
     * @param data 数据源
     * @return 整型CRC检验码
     */
    private int getCRCValue(byte[] data) {
        //因为crcValue要做位运算，因此这里应该使用长整型避免负数造成计算结果错误
        long crcValue = 0xFFFFFFFFL;
        int length = data.length;
        for (int i = 0; i < length; i++) {
            int crcIndex = (int) (crcValue ^ data[i]) & 0xFF;
            crcValue = (crcValue >> 8) ^ tables[crcIndex];
        }
        return (int) (crcValue ^ 0XFFFFFFFFL);
    }

    /**
     * 获取十六进制CRC检验码
     * @param data 数据源
     * @return 十六进制CRC检验码
     */
    public String getCRC(byte[] data) {
        long crcValue = getCRCValue(data) | 0x0000000100000000L;
        String crcHex = Long.toHexString(crcValue);
        int crcHexLength = crcHex.length();
        return crcHex.substring(crcHexLength - 8, crcHexLength).toUpperCase();
    }

    public static void main(String[] args) {
        
        //CRC校验码测试用例
        {
            CRC crc = new CRC();
            crc.initTable(0x04C11DB7L, 32, true);
            //需要输入长整型，避免有符号位运算影响
            // crc.initTable(0xEDB88320L, false);
            String crcResult = null;
            byte[] data = { (byte) 0x31, (byte) 0x32, (byte) 0x33, (byte) 0x34, (byte) 0x35, (byte) 0x36, (byte) 0x37,
                    (byte) 0x38, (byte) 0x39, (byte) 0x30 };
            crcResult = crc.getCRC(data);
            System.out.println(crcResult);

            //翻转检验
            {
                System.out.println(Long.toBinaryString(0XFFFFFFFFFFFFFFF0L));
                System.out.println(Long.toBinaryString(crc.reversePoly(0XFFFFFFFFFFFFFFF0L, 64)));
            }
        }

        //CRC字符表输出
        {
            StringBuffer sb = new StringBuffer();
            sb.append("{");
            for (int i = 0, length = tables.length; i < length; i++) {
                long crcValue = tables[i] | 0x0000000100000000L;
                String hexValue = Long.toHexString(crcValue);
                int hexValueLength = hexValue.length();
                hexValue = hexValue.substring(hexValueLength - 8, hexValueLength);
                sb.append("0x");
                sb.append(hexValue.toUpperCase());
                sb.append(",");
            }
            sb.deleteCharAt(sb.length() - 1);
            sb.append("}");
            System.out.println(sb);
        }
    }
}

后记

感觉各种技术都有人在之前写好了，而且写的都很好，而我一上手写这篇博客的时候发现完全没有下手的空间，没有任何创新点，也不能把CRC算法解释得更简单。因此，这里也就只能作为一次学习笔记来看了。很久没更新技术类博客了，但愿自己以后能够积极更新。

#Java #CRC #算法原理 #多项式
上一篇: 「Nginx」CentOS7.6操作系统下通过源码安装Nginx教程
下一篇: 理幻