CRC：将前一个余数放在哪里
CRC: where to put previous remainder
现在我正在编写带有多项式除法且没有位移的 CRC16 实现（出于教育目的）。
我的问题是：当我有前一个字节的 CRC 并读取新字节时，我需要放置前一个余数以计算新的 CRC？ （在新字节之前、新字节之后或与新字节异或等...）
我的代码适用于文本文件中的一个符号，但它不适用于多个符号。在我看来，我把第一个余数放错了地方:)
完整代码将放在下面。
#include <stdio.h>
#include <stdint.h>
void printBits(uint32_t inbyte, int width)
{
char modres = inbyte % 2;
inbyte = inbyte >> 1;
if (width > 0) {
printBits(inbyte, --width);
}
printf("%d", modres);
}
struct polynom
{
uint8_t x16;uint8_t x15;uint8_t x14;uint8_t x13;uint8_t x12;
uint8_t x11;uint8_t x10;uint8_t x9;uint8_t x8;uint8_t x7;
uint8_t x6;uint8_t x5;uint8_t x4;uint8_t x3;uint8_t x2;
uint8_t x1;uint8_t x0;
};
struct polycrc
{
uint8_t x15; uint8_t x14; uint8_t x13; uint8_t x12;
uint8_t x11; uint8_t x10; uint8_t x9; uint8_t x8; uint8_t x7;
uint8_t x6; uint8_t x5; uint8_t x4; uint8_t x3; uint8_t x2;
uint8_t x1; uint8_t x0;
};
struct byte
{
uint8_t x7; uint8_t x6; uint8_t x5; uint8_t x4;
uint8_t x3; uint8_t x2; uint8_t x1; uint8_t x0;
};
void printPolynom(struct polynom inp)
{
printf("%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d",
inp.x16, inp.x15, inp.x14, inp.x13, inp.x12, inp.x11, inp.x10,
inp.x9, inp.x8, inp.x7, inp.x6, inp.x5, inp.x4, inp.x3, inp.x2,
inp.x1, inp.x0);
}
void printCRC(struct polycrc inp)
{
printf("%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d",
inp.x15, inp.x14, inp.x13, inp.x12, inp.x11, inp.x10,
inp.x9, inp.x8, inp.x7, inp.x6, inp.x5, inp.x4, inp.x3, inp.x2,
inp.x1, inp.x0);
}
struct polycrc getCRC(uint8_t inByte, struct polycrc inCRC,
struct polynom inp)
{
struct delim
{
uint8_t xb7, xb6, xb5, xb4, xb3, xb2, xb1, xb0,
xa15, xa14, xa13, xa12, xa11, xa10, xa9, xa8, xa7,
xa6, xa5, xa4, xa3, xa2, xa1, xa0;
};
struct Bytes
{
uint8_t b7; uint8_t b6; uint8_t b5;
uint8_t b4; uint8_t b3; uint8_t b2;
uint8_t b1; uint8_t b0;
};
printBits(inByte, 7);
printf("|");
printCRC(inCRC);
printf("\n");
struct Bytes oneByte;
oneByte.b0 = inByte % 2; inByte = inByte / 2;
oneByte.b1 = inByte % 2; inByte = inByte / 2;
oneByte.b2 = inByte % 2; inByte = inByte / 2;
oneByte.b3 = inByte % 2; inByte = inByte / 2;
oneByte.b4 = inByte % 2; inByte = inByte / 2;
oneByte.b5 = inByte % 2; inByte = inByte / 2;
oneByte.b6 = inByte % 2; inByte = inByte / 2;
oneByte.b7 = inByte % 2; inByte = inByte / 2;
if (oneByte.b7 == 1){
inCRC.x7 ^= inp.x0; inCRC.x8 ^= inp.x1; inCRC.x9 ^= inp.x2;
inCRC.x10 ^= inp.x3; inCRC.x11 ^= inp.x4; inCRC.x12 ^= inp.x5;
inCRC.x13 ^= inp.x6; inCRC.x14 ^= inp.x7; inCRC.x15 ^= inp.x8;
oneByte.b0 ^= inp.x9; oneByte.b1 ^= inp.x10; oneByte.b2 ^= inp.x11;
oneByte.b3 ^= inp.x12; oneByte.b4 ^= inp.x13; oneByte.b5 ^= inp.x14;
oneByte.b6 ^= inp.x15; oneByte.b7 ^= inp.x16;
inByte = oneByte.b6 * 2 * 2 * 2 * 2 * 2 * 2;
inByte += oneByte.b5 * 2 * 2 * 2 * 2 * 2;
inByte += oneByte.b4 * 2 * 2 * 2 * 2;
inByte += oneByte.b3 * 2 * 2 * 2;
inByte += oneByte.b2 * 2 * 2;
inByte += oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b6 == 1){
inCRC.x6 ^= inp.x0; inCRC.x7 ^= inp.x1; inCRC.x8 ^= inp.x2;
inCRC.x9 ^= inp.x3; inCRC.x10 ^= inp.x4; inCRC.x11 ^= inp.x5;
inCRC.x12 ^= inp.x6; inCRC.x13 ^= inp.x7; inCRC.x14 ^= inp.x8;
inCRC.x15 ^= inp.x9; oneByte.b0 ^= inp.x10; oneByte.b1 ^= inp.x11;
oneByte.b2 ^= inp.x12; oneByte.b3 ^= inp.x13; oneByte.b4 ^= inp.x14;
oneByte.b5 ^= inp.x15; oneByte.b6 ^= inp.x16;
inByte = oneByte.b5 * 2 * 2 * 2 * 2 * 2;
inByte += oneByte.b4 * 2 * 2 * 2 * 2;
inByte += oneByte.b3 * 2 * 2 * 2;
inByte += oneByte.b2 * 2 * 2;
inByte += oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b5 == 1){
inCRC.x5 ^= inp.x0; inCRC.x6 ^= inp.x1; inCRC.x7 ^= inp.x2;
inCRC.x8 ^= inp.x3; inCRC.x9 ^= inp.x4; inCRC.x10 ^= inp.x5;
inCRC.x11 ^= inp.x6; inCRC.x12 ^= inp.x7; inCRC.x13 ^= inp.x8;
inCRC.x14 ^= inp.x9; inCRC.x15 ^= inp.x10; oneByte.b0 ^= inp.x11;
oneByte.b1 ^= inp.x12; oneByte.b2 ^= inp.x13; oneByte.b3 ^= inp.x14;
oneByte.b4 ^= inp.x15; oneByte.b5 ^= inp.x16;
inByte = oneByte.b4 * 2 * 2 * 2 * 2;
inByte += oneByte.b3 * 2 * 2 * 2;
inByte += oneByte.b2 * 2 * 2;
inByte += oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b4 == 1){
inCRC.x4 ^= inp.x0; inCRC.x5 ^= inp.x1; inCRC.x6 ^= inp.x2;
inCRC.x7 ^= inp.x3; inCRC.x8 ^= inp.x4; inCRC.x9 ^= inp.x5;
inCRC.x10 ^= inp.x6; inCRC.x11 ^= inp.x7; inCRC.x12 ^= inp.x8;
inCRC.x13 ^= inp.x9; inCRC.x14 ^= inp.x10; inCRC.x15 ^= inp.x11;
oneByte.b0 ^= inp.x12; oneByte.b1 ^= inp.x13; oneByte.b2 ^= inp.x14;
oneByte.b3 ^= inp.x15; oneByte.b4 ^= inp.x16;
inByte = oneByte.b3 * 2 * 2 * 2;
inByte += oneByte.b2 * 2 * 2;
inByte += oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b3 == 1){
inCRC.x3 ^= inp.x0; inCRC.x4 ^= inp.x1; inCRC.x5 ^= inp.x2;
inCRC.x6 ^= inp.x3; inCRC.x7 ^= inp.x4; inCRC.x8 ^= inp.x5;
inCRC.x9 ^= inp.x6; inCRC.x10 ^= inp.x7; inCRC.x11 ^= inp.x8;
inCRC.x12 ^= inp.x9; inCRC.x13 ^= inp.x10; inCRC.x14 ^= inp.x11;
inCRC.x15 ^= inp.x12; oneByte.b0 ^= inp.x13; oneByte.b1 ^= inp.x14;
oneByte.b2 ^= inp.x15; oneByte.b3 ^= inp.x16;
inByte = oneByte.b2 * 2 * 2;
inByte += oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b2 == 1){
inCRC.x2 ^= inp.x0; inCRC.x3 ^= inp.x1; inCRC.x4 ^= inp.x2;
inCRC.x5 ^= inp.x3; inCRC.x6 ^= inp.x4; inCRC.x7 ^= inp.x5;
inCRC.x8 ^= inp.x6; inCRC.x9 ^= inp.x7; inCRC.x10 ^= inp.x8;
inCRC.x11 ^= inp.x9; inCRC.x12 ^= inp.x10; inCRC.x13 ^= inp.x11;
inCRC.x14 ^= inp.x12; inCRC.x15 ^= inp.x13; oneByte.b0 ^= inp.x14;
oneByte.b1 ^= inp.x15; oneByte.b2 ^= inp.x16;
inByte = oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b1 == 1){
inCRC.x1 ^= inp.x0; inCRC.x2 ^= inp.x1; inCRC.x3 ^= inp.x2;
inCRC.x4 ^= inp.x3; inCRC.x5 ^= inp.x4; inCRC.x6 ^= inp.x5;
inCRC.x7 ^= inp.x6; inCRC.x8 ^= inp.x7; inCRC.x9 ^= inp.x8;
inCRC.x10 ^= inp.x9; inCRC.x11 ^= inp.x10; inCRC.x12 ^= inp.x11;
inCRC.x13 ^= inp.x12; inCRC.x14 ^= inp.x13; inCRC.x15 ^= inp.x14;
oneByte.b0 ^= inp.x15; oneByte.b1 ^= inp.x16;
inByte = oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b0 == 1){
inCRC.x0 ^= inp.x0; inCRC.x1 ^= inp.x1; inCRC.x2 ^= inp.x2;
inCRC.x3 ^= inp.x3; inCRC.x4 ^= inp.x4; inCRC.x5 ^= inp.x5;
inCRC.x6 ^= inp.x6; inCRC.x7 ^= inp.x7; inCRC.x8 ^= inp.x8;
inCRC.x9 ^= inp.x9; inCRC.x10 ^= inp.x10; inCRC.x11 ^= inp.x11;
inCRC.x12 ^= inp.x12; inCRC.x13 ^= inp.x13; inCRC.x14 ^= inp.x14;
inCRC.x15 ^= inp.x15; oneByte.b0 ^= inp.x16;
inByte = 0;
return getCRC(inByte, inCRC, inp);
}
else {
return inCRC;
}
}
int main()
{
// Initializing polynomial
struct polynom p;
p.x16 = 1; p.x15 = 1; p.x2 = 1; p.x0 = 1;
p.x14 = 0; p.x13 = 0; p.x12 = 0; p.x11 = 0; p.x10 = 0; p.x9 = 0;
p.x8 = 0; p.x7 = 0; p.x6 = 0; p.x5 = 0; p.x4 = 0;
p.x3 = 0; p.x1 = 0;
// Initializing CRC
struct polycrc crc;
crc.x15 = 0; crc.x14 = 0; crc.x13 = 0; crc.x12 = 0; crc.x11 = 0;
crc.x10 = 0; crc.x9 = 0; crc.x8 = 0; crc.x7 = 0; crc.x6 = 0;
crc.x5 = 0; crc.x4 = 0; crc.x3 = 0; crc.x2 = 0; crc.x1 = 0;
crc.x0 = 0;
// Print p and crc to check
printPolynom(p);
printf("\n");
printCRC(crc);
printf("\n");
char* inFileName = "input1.txt";
FILE* inputFile;
uint8_t c = 0;
fopen_s(&inputFile, inFileName, "r");
if (inputFile == NULL) {
printf("Error opening file %s", inFileName);
return 1;
}
// Read file and count CRC
c = fgetc(inputFile);
while (!feof(inputFile)) {
crc = getCRC(c, crc, p);
printf("Byte %0x CRC: ", c);
printCRC(crc);
printf("\n");
c = fgetc(inputFile);
}
fclose(inputFile);
return 0;
}
为了一次处理一个字节的CRC序列，该序列是一个输入字节与高位（如果左移）或低位（如果右移）CRC的xor，然后循环16位CRC就像线性反馈移位寄存器一样，使用 CRC 多项式进行反馈 8 次。这可以使用 256 个条目查找来加速 table。问题是寻求一种类似硬件的解决方案，使用位域结构将未循环的 16 位输入 CRC 映射到 8 循环的 16 位输出 CRC。
映射是二进制线性映射（如二进制（与、异或）矩阵乘以 16 x 16 位矩阵），顺序无关紧要。可以使用一组 16 个方程式，每个方程式将未循环 CRC 位的一个子集异或为循环 CRC 位。对于一组 16 个输入 CRC 值，每个设置 1 位：{0x0001、0x0002、0x0004、...、0x2000、0x4000、0x8000} 和注意哪些输入位对每个输出位有贡献。
对于每个输入字节，多项式 0x11021 的左移 CRC 示例：
/* xor the input byte to the upper 8 bits of the CRC */
crcin.b8 ^= dat.b0;
crcin.b9 ^= dat.b1;
crcin.ba ^= dat.b2;
crcin.bb ^= dat.b3;
crcin.bc ^= dat.b4;
crcin.bd ^= dat.b5;
crcin.be ^= dat.b6;
crcin.bf ^= dat.b7;
/* cycle the 16 bit CRC 8 times via mapping */
crcot.b0 = crcin.b8 ^ crcin.bc;
crcot.b1 = crcin.b9 ^ crcin.bd;
crcot.b2 = crcin.ba ^ crcin.be;
crcot.b3 = crcin.bb ^ crcin.bf;
crcot.b4 = crcin.bc;
crcot.b5 = crcin.b8 ^ crcin.bc ^ crcin.bd;
crcot.b6 = crcin.b9 ^ crcin.bd ^ crcin.be;
crcot.b7 = crcin.ba ^ crcin.be ^ crcin.bf;
crcot.b8 = crcin.b0 ^ crcin.bb ^ crcin.bf;
crcot.b9 = crcin.b1 ^ crcin.bc;
crcot.ba = crcin.b2 ^ crcin.bd;
crcot.bb = crcin.b3 ^ crcin.be;
crcot.bc = crcin.b4 ^ crcin.b8 ^ crcin.bc ^ crcin.bf;
crcot.bd = crcin.b5 ^ crcin.b9 ^ crcin.bd;
crcot.be = crcin.b6 ^ crcin.ba ^ crcin.be;
crcot.bf = crcin.b7 ^ crcin.bb ^ crcin.bf;
crcin = crcot;
现在我正在编写带有多项式除法且没有位移的 CRC16 实现（出于教育目的）。
我的问题是：当我有前一个字节的 CRC 并读取新字节时，我需要放置前一个余数以计算新的 CRC？ （在新字节之前、新字节之后或与新字节异或等...）
我的代码适用于文本文件中的一个符号，但它不适用于多个符号。在我看来，我把第一个余数放错了地方:)
完整代码将放在下面。
#include <stdio.h>
#include <stdint.h>
void printBits(uint32_t inbyte, int width)
{
char modres = inbyte % 2;
inbyte = inbyte >> 1;
if (width > 0) {
printBits(inbyte, --width);
}
printf("%d", modres);
}
struct polynom
{
uint8_t x16;uint8_t x15;uint8_t x14;uint8_t x13;uint8_t x12;
uint8_t x11;uint8_t x10;uint8_t x9;uint8_t x8;uint8_t x7;
uint8_t x6;uint8_t x5;uint8_t x4;uint8_t x3;uint8_t x2;
uint8_t x1;uint8_t x0;
};
struct polycrc
{
uint8_t x15; uint8_t x14; uint8_t x13; uint8_t x12;
uint8_t x11; uint8_t x10; uint8_t x9; uint8_t x8; uint8_t x7;
uint8_t x6; uint8_t x5; uint8_t x4; uint8_t x3; uint8_t x2;
uint8_t x1; uint8_t x0;
};
struct byte
{
uint8_t x7; uint8_t x6; uint8_t x5; uint8_t x4;
uint8_t x3; uint8_t x2; uint8_t x1; uint8_t x0;
};
void printPolynom(struct polynom inp)
{
printf("%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d",
inp.x16, inp.x15, inp.x14, inp.x13, inp.x12, inp.x11, inp.x10,
inp.x9, inp.x8, inp.x7, inp.x6, inp.x5, inp.x4, inp.x3, inp.x2,
inp.x1, inp.x0);
}
void printCRC(struct polycrc inp)
{
printf("%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d",
inp.x15, inp.x14, inp.x13, inp.x12, inp.x11, inp.x10,
inp.x9, inp.x8, inp.x7, inp.x6, inp.x5, inp.x4, inp.x3, inp.x2,
inp.x1, inp.x0);
}
struct polycrc getCRC(uint8_t inByte, struct polycrc inCRC,
struct polynom inp)
{
struct delim
{
uint8_t xb7, xb6, xb5, xb4, xb3, xb2, xb1, xb0,
xa15, xa14, xa13, xa12, xa11, xa10, xa9, xa8, xa7,
xa6, xa5, xa4, xa3, xa2, xa1, xa0;
};
struct Bytes
{
uint8_t b7; uint8_t b6; uint8_t b5;
uint8_t b4; uint8_t b3; uint8_t b2;
uint8_t b1; uint8_t b0;
};
printBits(inByte, 7);
printf("|");
printCRC(inCRC);
printf("\n");
struct Bytes oneByte;
oneByte.b0 = inByte % 2; inByte = inByte / 2;
oneByte.b1 = inByte % 2; inByte = inByte / 2;
oneByte.b2 = inByte % 2; inByte = inByte / 2;
oneByte.b3 = inByte % 2; inByte = inByte / 2;
oneByte.b4 = inByte % 2; inByte = inByte / 2;
oneByte.b5 = inByte % 2; inByte = inByte / 2;
oneByte.b6 = inByte % 2; inByte = inByte / 2;
oneByte.b7 = inByte % 2; inByte = inByte / 2;
if (oneByte.b7 == 1){
inCRC.x7 ^= inp.x0; inCRC.x8 ^= inp.x1; inCRC.x9 ^= inp.x2;
inCRC.x10 ^= inp.x3; inCRC.x11 ^= inp.x4; inCRC.x12 ^= inp.x5;
inCRC.x13 ^= inp.x6; inCRC.x14 ^= inp.x7; inCRC.x15 ^= inp.x8;
oneByte.b0 ^= inp.x9; oneByte.b1 ^= inp.x10; oneByte.b2 ^= inp.x11;
oneByte.b3 ^= inp.x12; oneByte.b4 ^= inp.x13; oneByte.b5 ^= inp.x14;
oneByte.b6 ^= inp.x15; oneByte.b7 ^= inp.x16;
inByte = oneByte.b6 * 2 * 2 * 2 * 2 * 2 * 2;
inByte += oneByte.b5 * 2 * 2 * 2 * 2 * 2;
inByte += oneByte.b4 * 2 * 2 * 2 * 2;
inByte += oneByte.b3 * 2 * 2 * 2;
inByte += oneByte.b2 * 2 * 2;
inByte += oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b6 == 1){
inCRC.x6 ^= inp.x0; inCRC.x7 ^= inp.x1; inCRC.x8 ^= inp.x2;
inCRC.x9 ^= inp.x3; inCRC.x10 ^= inp.x4; inCRC.x11 ^= inp.x5;
inCRC.x12 ^= inp.x6; inCRC.x13 ^= inp.x7; inCRC.x14 ^= inp.x8;
inCRC.x15 ^= inp.x9; oneByte.b0 ^= inp.x10; oneByte.b1 ^= inp.x11;
oneByte.b2 ^= inp.x12; oneByte.b3 ^= inp.x13; oneByte.b4 ^= inp.x14;
oneByte.b5 ^= inp.x15; oneByte.b6 ^= inp.x16;
inByte = oneByte.b5 * 2 * 2 * 2 * 2 * 2;
inByte += oneByte.b4 * 2 * 2 * 2 * 2;
inByte += oneByte.b3 * 2 * 2 * 2;
inByte += oneByte.b2 * 2 * 2;
inByte += oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b5 == 1){
inCRC.x5 ^= inp.x0; inCRC.x6 ^= inp.x1; inCRC.x7 ^= inp.x2;
inCRC.x8 ^= inp.x3; inCRC.x9 ^= inp.x4; inCRC.x10 ^= inp.x5;
inCRC.x11 ^= inp.x6; inCRC.x12 ^= inp.x7; inCRC.x13 ^= inp.x8;
inCRC.x14 ^= inp.x9; inCRC.x15 ^= inp.x10; oneByte.b0 ^= inp.x11;
oneByte.b1 ^= inp.x12; oneByte.b2 ^= inp.x13; oneByte.b3 ^= inp.x14;
oneByte.b4 ^= inp.x15; oneByte.b5 ^= inp.x16;
inByte = oneByte.b4 * 2 * 2 * 2 * 2;
inByte += oneByte.b3 * 2 * 2 * 2;
inByte += oneByte.b2 * 2 * 2;
inByte += oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b4 == 1){
inCRC.x4 ^= inp.x0; inCRC.x5 ^= inp.x1; inCRC.x6 ^= inp.x2;
inCRC.x7 ^= inp.x3; inCRC.x8 ^= inp.x4; inCRC.x9 ^= inp.x5;
inCRC.x10 ^= inp.x6; inCRC.x11 ^= inp.x7; inCRC.x12 ^= inp.x8;
inCRC.x13 ^= inp.x9; inCRC.x14 ^= inp.x10; inCRC.x15 ^= inp.x11;
oneByte.b0 ^= inp.x12; oneByte.b1 ^= inp.x13; oneByte.b2 ^= inp.x14;
oneByte.b3 ^= inp.x15; oneByte.b4 ^= inp.x16;
inByte = oneByte.b3 * 2 * 2 * 2;
inByte += oneByte.b2 * 2 * 2;
inByte += oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b3 == 1){
inCRC.x3 ^= inp.x0; inCRC.x4 ^= inp.x1; inCRC.x5 ^= inp.x2;
inCRC.x6 ^= inp.x3; inCRC.x7 ^= inp.x4; inCRC.x8 ^= inp.x5;
inCRC.x9 ^= inp.x6; inCRC.x10 ^= inp.x7; inCRC.x11 ^= inp.x8;
inCRC.x12 ^= inp.x9; inCRC.x13 ^= inp.x10; inCRC.x14 ^= inp.x11;
inCRC.x15 ^= inp.x12; oneByte.b0 ^= inp.x13; oneByte.b1 ^= inp.x14;
oneByte.b2 ^= inp.x15; oneByte.b3 ^= inp.x16;
inByte = oneByte.b2 * 2 * 2;
inByte += oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b2 == 1){
inCRC.x2 ^= inp.x0; inCRC.x3 ^= inp.x1; inCRC.x4 ^= inp.x2;
inCRC.x5 ^= inp.x3; inCRC.x6 ^= inp.x4; inCRC.x7 ^= inp.x5;
inCRC.x8 ^= inp.x6; inCRC.x9 ^= inp.x7; inCRC.x10 ^= inp.x8;
inCRC.x11 ^= inp.x9; inCRC.x12 ^= inp.x10; inCRC.x13 ^= inp.x11;
inCRC.x14 ^= inp.x12; inCRC.x15 ^= inp.x13; oneByte.b0 ^= inp.x14;
oneByte.b1 ^= inp.x15; oneByte.b2 ^= inp.x16;
inByte = oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b1 == 1){
inCRC.x1 ^= inp.x0; inCRC.x2 ^= inp.x1; inCRC.x3 ^= inp.x2;
inCRC.x4 ^= inp.x3; inCRC.x5 ^= inp.x4; inCRC.x6 ^= inp.x5;
inCRC.x7 ^= inp.x6; inCRC.x8 ^= inp.x7; inCRC.x9 ^= inp.x8;
inCRC.x10 ^= inp.x9; inCRC.x11 ^= inp.x10; inCRC.x12 ^= inp.x11;
inCRC.x13 ^= inp.x12; inCRC.x14 ^= inp.x13; inCRC.x15 ^= inp.x14;
oneByte.b0 ^= inp.x15; oneByte.b1 ^= inp.x16;
inByte = oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b0 == 1){
inCRC.x0 ^= inp.x0; inCRC.x1 ^= inp.x1; inCRC.x2 ^= inp.x2;
inCRC.x3 ^= inp.x3; inCRC.x4 ^= inp.x4; inCRC.x5 ^= inp.x5;
inCRC.x6 ^= inp.x6; inCRC.x7 ^= inp.x7; inCRC.x8 ^= inp.x8;
inCRC.x9 ^= inp.x9; inCRC.x10 ^= inp.x10; inCRC.x11 ^= inp.x11;
inCRC.x12 ^= inp.x12; inCRC.x13 ^= inp.x13; inCRC.x14 ^= inp.x14;
inCRC.x15 ^= inp.x15; oneByte.b0 ^= inp.x16;
inByte = 0;
return getCRC(inByte, inCRC, inp);
}
else {
return inCRC;
}
}
int main()
{
// Initializing polynomial
struct polynom p;
p.x16 = 1; p.x15 = 1; p.x2 = 1; p.x0 = 1;
p.x14 = 0; p.x13 = 0; p.x12 = 0; p.x11 = 0; p.x10 = 0; p.x9 = 0;
p.x8 = 0; p.x7 = 0; p.x6 = 0; p.x5 = 0; p.x4 = 0;
p.x3 = 0; p.x1 = 0;
// Initializing CRC
struct polycrc crc;
crc.x15 = 0; crc.x14 = 0; crc.x13 = 0; crc.x12 = 0; crc.x11 = 0;
crc.x10 = 0; crc.x9 = 0; crc.x8 = 0; crc.x7 = 0; crc.x6 = 0;
crc.x5 = 0; crc.x4 = 0; crc.x3 = 0; crc.x2 = 0; crc.x1 = 0;
crc.x0 = 0;
// Print p and crc to check
printPolynom(p);
printf("\n");
printCRC(crc);
printf("\n");
char* inFileName = "input1.txt";
FILE* inputFile;
uint8_t c = 0;
fopen_s(&inputFile, inFileName, "r");
if (inputFile == NULL) {
printf("Error opening file %s", inFileName);
return 1;
}
// Read file and count CRC
c = fgetc(inputFile);
while (!feof(inputFile)) {
crc = getCRC(c, crc, p);
printf("Byte %0x CRC: ", c);
printCRC(crc);
printf("\n");
c = fgetc(inputFile);
}
fclose(inputFile);
return 0;
}
为了一次处理一个字节的CRC序列，该序列是一个输入字节与高位（如果左移）或低位（如果右移）CRC的xor，然后循环16位CRC就像线性反馈移位寄存器一样，使用 CRC 多项式进行反馈 8 次。这可以使用 256 个条目查找来加速 table。问题是寻求一种类似硬件的解决方案，使用位域结构将未循环的 16 位输入 CRC 映射到 8 循环的 16 位输出 CRC。
映射是二进制线性映射（如二进制（与、异或）矩阵乘以 16 x 16 位矩阵），顺序无关紧要。可以使用一组 16 个方程式，每个方程式将未循环 CRC 位的一个子集异或为循环 CRC 位。对于一组 16 个输入 CRC 值，每个设置 1 位：{0x0001、0x0002、0x0004、...、0x2000、0x4000、0x8000} 和注意哪些输入位对每个输出位有贡献。
对于每个输入字节，多项式 0x11021 的左移 CRC 示例：
/* xor the input byte to the upper 8 bits of the CRC */
crcin.b8 ^= dat.b0;
crcin.b9 ^= dat.b1;
crcin.ba ^= dat.b2;
crcin.bb ^= dat.b3;
crcin.bc ^= dat.b4;
crcin.bd ^= dat.b5;
crcin.be ^= dat.b6;
crcin.bf ^= dat.b7;
/* cycle the 16 bit CRC 8 times via mapping */
crcot.b0 = crcin.b8 ^ crcin.bc;
crcot.b1 = crcin.b9 ^ crcin.bd;
crcot.b2 = crcin.ba ^ crcin.be;
crcot.b3 = crcin.bb ^ crcin.bf;
crcot.b4 = crcin.bc;
crcot.b5 = crcin.b8 ^ crcin.bc ^ crcin.bd;
crcot.b6 = crcin.b9 ^ crcin.bd ^ crcin.be;
crcot.b7 = crcin.ba ^ crcin.be ^ crcin.bf;
crcot.b8 = crcin.b0 ^ crcin.bb ^ crcin.bf;
crcot.b9 = crcin.b1 ^ crcin.bc;
crcot.ba = crcin.b2 ^ crcin.bd;
crcot.bb = crcin.b3 ^ crcin.be;
crcot.bc = crcin.b4 ^ crcin.b8 ^ crcin.bc ^ crcin.bf;
crcot.bd = crcin.b5 ^ crcin.b9 ^ crcin.bd;
crcot.be = crcin.b6 ^ crcin.ba ^ crcin.be;
crcot.bf = crcin.b7 ^ crcin.bb ^ crcin.bf;
crcin = crcot;