用java实现一个CRC校验算法

分享讨论IT相关的内容
回复
头像
BobMaster
锋芒初露
锋芒初露
帖子: 1187
注册时间: 2020年 12月 7日 08:05
来自: 神秘的东方
我的状态: 🎯
为圈友点赞: 338 次
被赞次数: 178 次
联系:

用java实现一个CRC校验算法

帖子 BobMaster »

代码: 全选

/*
本程序尝试实现一个普适的CRC算法

例子:
CRC-3-GSM
请输入通信数据: 11010011101101
请输入检验起点: 0
请输入校验长度: 14
(x^3+x+1)CRC算法对应多项式的二进制表示: 1011
请输入初始填充字符,0或者1: 1
CRC校验码为: 000
下面进行数据校验
请输入测试数据1: 11010011101101
请输入测试数据2: 1101001110110
请输入测试数据3: 11010011101
测试数据1的校验结果为: 校验通过
测试数据2的校验结果为: 校验失败,数据有误
测试数据3的校验结果为: 校验失败,数据有误


CRC-16-CCITT
请输入数据: 1101001110110011010011101100
请输入检验起点: 0
请输入校验长度: 5
(x^16+x^12+x^5+1)请输入多项式系数:10001000000100001
请输入初始填充字符,0或者1: 1
CRC校验码为: 1100011001001111
下面进行数据校验
请输入测试数据1: 11010
请输入测试数据2: 10001000000100001
请输入测试数据3: 1101001110110011010011101100
测试数据1的校验结果为: 校验通过
测试数据2的校验结果为: 校验失败,数据有误
测试数据3的校验结果为: 校验失败,数据有误
 */

import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.Objects;
import java.util.Scanner;

public class Work1 {
    public static void main(String[] args) {
        Work1 work1 = new Work1();
        Scanner sc = new Scanner(System.in);
        System.out.println("计算特定长度通信数据的CRC校验码");
        System.out.print("请输入通信数据: ");
        /*
        测试数据
        通信数据:11010011101100
        校验起点: 0
        检验长度: 14
        CRC算法对应多项式的二进制表示: 1011
        请输入初始填充字符,0或者1: 0
        CRC校验码为: 100
        测试数据1: 11010011101100
        测试数据2: 11010011101101
        测试数据3: 11010011111101
         */

        // 输入通信数据
        // 本来不想这么麻烦的,如果不是为了写题,怎么还要把String类型转byte呢,叹气
        byte[] data = sc.nextLine().getBytes(StandardCharsets.UTF_8);

        // 输入检验起点
        System.out.print("请输入检验起点: ");
        int start = sc.nextInt();

        // 校验长度
        System.out.print("请输入校验长度: ");
        int len = sc.nextInt();


        // CRC算法对应多项式的二进制表示,如 1011 (x^3+x+1)
        System.out.print("CRC算法对应多项式的二进制表示: ");
        sc.nextLine();  // 读取上面 sc.nextInt() 留下的 \n
        String polynomial_bitstring = sc.nextLine();

        // 初始填充字符 0或者1
        System.out.print("请输入初始填充字符,0或者1: ");
        String initial_filter = sc.next();

        // 计算校验码
        String CRC_CODE = work1.GetCRC(data, start, len, polynomial_bitstring, initial_filter);

        // 数据校验
        System.out.println("下面进行数据校验");
        sc.nextLine();  // 读取上面sc.next()留下的\n
        System.out.print("请输入测试数据1: ");
        // 本来不想这么麻烦的,如果不是为了写题,怎么还要把String类型转byte呢,叹气
        String input_test1_bitstring = byteToString(sc.nextLine().getBytes(StandardCharsets.UTF_8));
        System.out.print("请输入测试数据2: ");
        // 本来不想这么麻烦的,如果不是为了写题,怎么还要把String类型转byte呢,叹气
        String input_test2_bitstring = byteToString(sc.nextLine().getBytes(StandardCharsets.UTF_8));
        System.out.print("请输入测试数据3: ");
        String input_test3_bitstring = sc.nextLine();

        // 关闭 Scanner 对象
        sc.close();

        // 测试数据1的校验结果
        boolean result1 = work1.Check_CRC(input_test1_bitstring, polynomial_bitstring,
                String.valueOf(CRC_CODE), initial_filter);

        if (result1){
            System.out.print("测试数据1的校验结果为: 校验通过\n");
        } else {
            System.out.print("测试数据1的校验结果为: 校验失败,数据有误\n");
        }

        // 测试数据2的校验结果
        boolean result2 = work1.Check_CRC(input_test2_bitstring, polynomial_bitstring,
                String.valueOf(CRC_CODE), initial_filter);

        if (result2){
            System.out.print("测试数据2的校验结果为: 校验通过\n");
        } else {
            System.out.print("测试数据2的校验结果为: 校验失败,数据有误\n");
        }

        // 测试数据3的校验结果
        boolean result3 = work1.Check_CRC(input_test3_bitstring, polynomial_bitstring,
                String.valueOf(CRC_CODE), initial_filter);

        if (result3){
            System.out.print("测试数据3的校验结果为: 校验通过\n");
        } else {
            System.out.print("测试数据3的校验结果为: 校验失败,数据有误\n");
        }
    }

    // 计算特定长度通信数据的CRC校验码
    public String GetCRC(byte[] data,int start,int len, String polynomial_bitstring, String initial_filter){
        // 截取特定长度的数据
        byte[] input_data = Arrays.copyOfRange(data, start, start+len);


        String input_bitstring = byteToString(input_data);
        // 调用CRC_Remainder函数求校验码
        String CRC_CODE = CRC_Remainder(input_bitstring, polynomial_bitstring, initial_filter);
        System.out.println("CRC校验码为: " + CRC_CODE);
        // 这里就不返回short类型了,会将CRC校验码左边的0给截断
        return CRC_CODE;
    }

    // 校验码生成函数
    // input_bitstring 数据输入,polynomial_bitstring CRC算法对应多项式的二进制表示,initial_filter 初始填充字符,‘0’或者‘1’
    // initial_filter 取‘0’,校验结果全为“0”则校验通过,intial_filter取“1”,校验结果全为“1”则校验通过
    public static String CRC_Remainder(String input_bitstring, String polynomial_bitstring, String initial_filter){
        // 如果有“0”,则去除多项式系数左边的“0”,这里用到了正则表达式,^匹配字符串的开头,0表示字符串0,*表示有零个或者多个(贪婪匹配)
        polynomial_bitstring = polynomial_bitstring.replaceAll("^0*", "");

        // 待计算数据的字符长度
        int len_input = input_bitstring.length();

        // 初始填充字符,其长度为CRC算法对应多项式长度-1
        // 比如使用CRC-3-GSM算法,其多项式为x^3+x+1,二进制表示为1011,长度为4,取初始填充字符为0,则填充部分为000
        String initial_padding = initial_filter.repeat(polynomial_bitstring.length()-1);

        // 将待计算数据与填充字符串合并为一个新的字符串,并转换为字符数组
        char[] input_padded_array = (input_bitstring + initial_padding).toCharArray();

        // 根据文献上的算法,每一次做除法(异或运算)之后,需要将多项式的头部对齐至字符数组中第一个字符'1'所出现的位置
        // 即不断的将多项式头部从左向右移,直到原数据所对应的长度内没有字符'1'为止
        /*
       | 原数据长度|填充长度|
       | 00000001|000|
       |        1011| 做异或运算
       | 00000000|011|
       此时原数据长度内没有字符'1'了,运算结束,CRC校验码为011
       下面的循环就是文献上计算过程的实现
         */
        // Arrays.copyOfRange(arr[], from, to)
        // Arrays.copyOfRange(input_padded_array,0, len_input) 按原数据长度从填充后的新字符数组中截取对应的片段
        // arrayContainChar(char[], char) 函数实现的功能是判断原数据长度内所对应的新字符数组是否还存在字符'1'
        while (arrayContainChar(Arrays.copyOfRange(input_padded_array,0, len_input), '1')){
            // cur_shitft 多项式的头部,将多项式的头部对齐至截取的字符数组中第一个字符'1'所出现的位置
            int cur_shift = new String(Arrays.copyOfRange(input_padded_array,0, len_input)).indexOf("1");
            for (int i=0; i< polynomial_bitstring.length(); i++){
                // 该循环实现的是二进制做除法运算(相当于异或运算)
                // booleanToNumberChar(boolean)函数实现将布尔类型的true/false转为字符'1'/'0'
                input_padded_array[cur_shift+i] = booleanToNumberChar(polynomial_bitstring.charAt(i) != input_padded_array[cur_shift+i]);
            }
        }
        // 经过上面的运算后,新字符数组在原数据所对应的长度内已没有字符"1",填充的位置即为校验码,返回即可
        // Arrays.copyOfRange(新字符数组, 从原数据所对应长度开始,到新字符数组的末尾),注意数组是从0开始,所以这里的len_input所对应的位置为填充段的首字符
        return new String(Arrays.copyOfRange(input_padded_array, len_input, input_padded_array.length));
    }

    // 数据校验函数
    /*
    该函数和上面的计算基本相同,只不过初始填充部分变为了上面的校验码,根据最后得到的填充部分判断输入
    数据数据是否校验通过
    initial_filter 取‘0’,最后计算结果的填充部分全为“0”校验通过,initial_filter取“1”,最后计算结果的填充部分全为“1”校验通过
     */
    public boolean Check_CRC(String input_bitstring, String polynomial_bitstring, String check_code, String initial_filter){
        // 去除多项式左边的“0”
        polynomial_bitstring = polynomial_bitstring.replaceAll("^0*", "");
        int len_input = input_bitstring.length();
        String initial_padding = check_code;
        char[] input_padded_array = (input_bitstring+initial_padding).toCharArray();

        while (arrayContainChar(Arrays.copyOfRange(input_padded_array, 0, len_input), '1')){
            int cur_shift = new String(Arrays.copyOfRange(input_padded_array, 0, len_input)).indexOf("1");
            for (int i=0; i<polynomial_bitstring.length();i++){
                input_padded_array[cur_shift+i] = booleanToNumberChar(polynomial_bitstring.charAt(i) !=
                        input_padded_array[cur_shift+i]);
            }
        }
        boolean flag = true;
        // foreach 遍历填充段的内容,根据initial_filter 判断是否包含'0'或'1'决定最后的结果
        for (char a: Arrays.copyOfRange(input_padded_array, len_input, input_padded_array.length)){
            // Objects.equals函数用于深度比较,判断字符串是否完全相等
            if (Objects.equals(initial_filter, "0")) {
                // 当initial_filter 取‘0’时,如果填充部分有字符'1',则校验失败
                if (a == '1') {
                    flag = false;
                    break;
                }
            }
            if (Objects.equals(initial_filter, "1")) {
                // 当initial_filter 取‘1’时,如果填充部分有字符'0',则校验失败
               if (a == '0'){
                   flag = false;
                   break;
               }
           }
        }
        return flag;
    }

    // 布尔类型转为字符类型的'1'与'0'
    public static char booleanToNumberChar(final boolean input){
        return input ? '1' : '0';
    }

    // 判断字符数组是否包含某一字符
    public static boolean arrayContainChar(char[] arr, char c){
        boolean contains = false;
        for(char f: arr){
            if (f == c){
                contains = true;
                break;
            }
        }
        return contains;
    }

    // byte 在 java 中是一个8位有符号的二进制补码整数
    // byte转字符串函数
    // 参考:https://stackoverflow.com/a/12310078
    // 创建StringBuilder对象,用于字符串拼接
    public static String byteToString(byte[] data){
        StringBuilder input_bitstring = new StringBuilder();
        // foreach 把byte数组中的元素依次转为字符串拼接起来
        for (byte b: data) {
            input_bitstring.append(String.format("%8s", Integer.toBinaryString(b & 0xFF)).replaceAll("\s", "0"));
        }
        return input_bitstring.toString();
    }
}
参考资料:
https://en.wikipedia.org/wiki/Cyclic_redundancy_check
人生如音乐,欢乐且自由
回复

在线用户

正浏览此版面之用户: 没有注册用户 和 2 访客