[C++知识库]设计一个可用于无线传输业务的 纠删码(c语言版本)

本文来源：某兄弟是搞电子信息的，公司的产品出现丢包率太高问题。使用的是rfid射频信号。据分析后，发现rfid波长太长，容易收到干扰，造成byte数据bit反转问题(例如，一根弹簧的长度被压缩或拉伸了，代表的值就不一样)。
在分布式存储例如ceph，gluster，minio，hdfs中都有纠删码的使用，可以实现数据受损检测和恢复。纠删码最先出现在无线传输技术领域，被用于对讲机的音频传输中，发扬光大与互联网领域。 因此考虑使用纠删码来补救，提升rfid无线射频信号的传输正确率。 由于这3年用golang做开发，3年没有写c语言代码，从晚上10点开始，大概熬了一个晚上到凌晨2点才全部调试完毕。（一边温习gcc, gdb调试，一边写代码）。

代码：

root@jack-VirtualBox:~/test/xor/zz# cat main.c 
/*
 *sz 星xxx电子科技有限公司，无线数据编解码，部分数据损坏的恢复算法。
 * */
#include <stdio.h>
#include <string.h>

// 纠删比例4:1, 4个byte数据跟1个冗余数据，5个数据里面任意4个数据，可以恢复出全部5个数据。
#define SECTOR_SIZE (4)

#define POLYNOMIAL 0xCa  /* 11011后面补0凑8位数：11011010*/

unsigned char CheckCrc6(unsigned char const message)
{
        unsigned char remainder;        //余数
        unsigned char i = 0;         //循环变量

        /* 初始化，余数=原始数据 */
        remainder = message;

        /* 从最高位开始依次计算  */
        for (i = 0; i < 8; i++)
        {
                if (remainder & 0x80)
                {
                        remainder ^= POLYNOMIAL;
                }
                remainder = (remainder << 1);
        }

        /* 返回计算的CRC码 */
        return (remainder >> 2);
}

char byte_bit_count(unsigned char d)
{
        char i = 0, sum = 0;
        for (i = 0; d; d >>= 1) {
                sum += d & 0x01;
        }

        return sum;
}

unsigned char encode_crc(unsigned char data)
{
        unsigned char cnt = 0;

        data &= ~(1 << 7);
        cnt = byte_bit_count(data);
        if ((cnt % 2) == 0) {
                // bit[0~6]中，为1个bit是偶数个
                data |= 1 << 7;
        } else {
                // bit[0~6]中，为1个bit是奇数个
                data &= ~(1 << 7);
        }

        return data;
}

/*
 *字节是否完整？
 *返回0，字节没有发生位反转。 返回1，字节发生位反转
 * */
char is_byte_whole(unsigned char data) {
        unsigned char cnt = 0;
        unsigned char src = data & (~(1 << 7));

        cnt = byte_bit_count(src);
        if ((cnt % 2) == 0) {
                if (data & (1 << 7)) {
                        return 0;
                } else {
                        return -1;
                }
        } else {
                if (data & (1 << 7)) {
                        return -1;
                } else {
                        return 0;
                }
        }   

        return -1;
}


/*
 *函数功能：对src按照4:1纠删比例进行编码
 * */
char xorencode(
                unsigned char *src,
                int src_len,
                unsigned char *dst,
                int dst_len)
{
        if (src == NULL || dst == NULL) {
                printf("src 或 dst为Null指针\r\n");
                return -1;
        }
        if ((src_len % SECTOR_SIZE) != 0) {
                printf("src 数据需要在编码前设置为SECTOR_SIZE=%d的整数倍\r\n", SECTOR_SIZE);
                return -1;
        }
        if (src_len * 5 >  dst_len * 4) {
                printf("dst_len太小，不能存储下xor erase code编码后的数据\r\n");
                return -1;
        }

        int i, j;
        unsigned char xor = 0;
        int block_cnt = src_len / SECTOR_SIZE; // 数据块数量(每 SECTOR_SIZE 个src数据是一块数据 )

        for (i = 0; i < block_cnt; i++) {
                for(j = 0; j < SECTOR_SIZE; j++) {
                        dst[i * (SECTOR_SIZE + 1) + j] = src[i * SECTOR_SIZE + j];
                }
                dst[i * (SECTOR_SIZE + 1) + j] = (src[i * SECTOR_SIZE + 0] ^ src[i * SECTOR_SIZE + 1] ^ src[i * SECTOR_SIZE + 2] ^ src[i * SECTOR_SIZE + 3]);
        }
        //printf("\r\n");

        return 0;
}


/*
 *函数功能：对src按照4:1的纠删比例，进行解码(如果发现数据损坏，则尽量去恢复数据)
 *返回值：0，解码成功。 -1，解码失败，丢去该包数据。
 * */
char xordecode(
                unsigned char *src,
                int src_len,
                unsigned char *dst,
                int dst_len)
{
        if (src == NULL || dst == NULL) {
                printf("src 或 dst为Null指针\r\n");
                return -1;
        }
        if ((src_len % (SECTOR_SIZE + 1)) != 0) {
                printf("src 数据需要在编码前设置为SECTOR_SIZE=%d的整数倍\r\n", SECTOR_SIZE);
                return -1;
        }
        if (src_len * 4 >  dst_len * 5) {
                printf("dst太小，不能存储下xor erase code解码后的数据\r\n");
                return -1;
        }


        int i, j, k, z = 0;
        unsigned char xor = 0;
        int block_cnt = src_len / (SECTOR_SIZE + 1); // 数据块数量(每 SECTOR_SIZE + 1 个src数据是一块数据 )

        for (i = 0; i < block_cnt; i++) {
                unsigned char x = 0;     // 受损字节数
                unsigned char index1 = 0;
                unsigned char xxor = 0;
                unsigned char tmp[SECTOR_SIZE];

                // 遍历一块数据
                x = 0;
                index1 = 0;
                xxor = 0;
                for(j = 0; j < (SECTOR_SIZE + 1); j++) {

                        if (is_byte_whole(src[i * (SECTOR_SIZE + 1 ) + j]) == 0) {
                                continue;
                        } else {
                                // 不检测冗余byte突变
                                unsigned char index = i * (SECTOR_SIZE + 1 ) + j;
                                if (((index + 1) % (SECTOR_SIZE + 1 ) == 0)) {
                                        continue;
                                }

                                index1 = j;
                                x++;

                                //printf("第src[%d]=%X字节受损\r\n", i * (SECTOR_SIZE + 1 ) + j, src[i * (SECTOR_SIZE + 1 ) + j]);
                                printf("第src[%d]=%X字节受损\r\n", index, src[index]);
                                // 恢复字节数据
                                index = 0;
                                for(k = 0; k < (SECTOR_SIZE + 1); k++) {
                                        if (k == j) {
                                                continue;
                                        }
                                        tmp[index++] = src[i * (SECTOR_SIZE + 1) + k]; 
                                }
                                xxor = tmp[0] ^ tmp[1] ^ tmp[2] ^ tmp[3];
                        }
                }

                // 判断本块数据是否不可恢复？
                if (x > 1) {
                        printf("数据受损超过阀值，不可恢复成功\r\n");
                        return -1;
                }

                // 如果扇区受损，则恢复
                if (x == 1) {
                        printf("数据受损，已被恢复\r\n");
                        src[i * (SECTOR_SIZE + 1) + index1] = xxor;       
                }
                
                // 恢复数据
                for(j = 0; j < SECTOR_SIZE; j++) {
                        dst[i * SECTOR_SIZE + j] = src[i * (SECTOR_SIZE + 1) + j];
                }
        }

        return 0;
}


int main() {
        unsigned char src[24]; 
        unsigned char src_len = 24;
        char i = 0;
        printf("原始数据为：\r\n");
        for (i = 0; i < src_len; i++) {
                src[i] = 79 + i;
                
                // 设置bit7，用于检测byte在无线传输时，是否发生奇数个数据损失。 因此应用程序在使用数据进行编码时，只能使用bit0~bit6，不能使用bit7。
                src[i] = encode_crc(src[i]);
                
                printf("%X ", src[i]);      
        }
        printf("\r\n\r\n");

        char ret = -1;
        unsigned char dst[30]; 
        unsigned char dst_len = 30;
        ret = xorencode(src, src_len, dst, dst_len);
        if (ret == 0) {
                printf("4:1 纠删码编码成功，编码后数据为：\r\n");
                for (i = 0; i < dst_len; i++) {
                        printf("%X ", dst[i]);      
                } 
                printf("\r\n");
        } else {
                printf("4:1纠删编码失败\r\n");
                return -1;
        }

        memset(src, 0x00, sizeof(src)/sizeof(src[0]));
        printf("\r\n人为破坏掉纠删码编码后的数据，第0 Byte , 第8 Byte, 第 28 Byte \r\n");
        dst[0] &= ~(1 << 3);
        dst[7] &= ~(1 << 6);
        dst[27] &= ~(1 << 2);

        printf("4:1 纠删码编码认为模拟破坏后数据为：\r\n");
        for (i = 0; i < dst_len; i++) {
                printf("%X ", dst[i]);      
        } 
        printf("\r\n");

        // 恢复数据
        ret = xordecode(dst, dst_len, src, src_len);
        if (ret == 0) {
                // 打印恢复后的数据
                printf("恢复数据成功\r\n");       
                for (i = 0; i < src_len; i++) {
                        printf("%X ", src[i]);      
                } 
                printf("\r\n");
        }
}
root@jack-VirtualBox:~/test/xor/zz#

执行：