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

前言

  这段时间处于待业状态中，所以就自己捣鼓些东西，学习学习有趣的算法。因为对于文件的校验可以通过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检验算法

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算法解释得更简单。因此，这里也就只能作为一次学习笔记来看了。很久没更新技术类博客了，但愿自己以后能够积极更新。