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

/ 0评 / 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检验算法

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

作者:Klavor Lee
来源:Klavor's Blog
原文:https://www.klavor.com/dev/20190618-552.html
版权声明:本文为博主原创文章,转载请附上博文链接!

发表评论

电子邮件地址不会被公开。 必填项已用*标注