从 HDL 到软件的 CRC-32 算法
CRC-32 algorithm from HDL to software
我在 Verilog 中实现了伽罗瓦线性反馈移位寄存器(也在 MATLAB 中,主要是为了模拟 HDL 设计)。它运行良好,据我所知,我使用 MATLAB 计算 CRC-32 字段,然后将它们包含在我的 HDL 模拟中以验证数据包是否已正确到达(使用 CRC-32 填充数据),这会产生良好的结果。
问题是我希望能够计算我在软件中实现的 CRC-32,因为我将使用 Raspberry Pi 通过我的 FPGA 中的 GPIO 输入数据,而且我还没有没能做到。我试过 this online calculator,使用相同的参数,但从未得到相同的结果。
这是我用来计算 CRC-32 的 MATLAB 代码:
N = 74*16;
data = [round(rand(1,N)) zeros(1,32)];
lfsr = ones(1,32);
next_lfsr = zeros(1,32);
for i = 1:length(data)
next_lfsr(1) = lfsr(2);
next_lfsr(2) = lfsr(3);
next_lfsr(3) = lfsr(4);
next_lfsr(4) = lfsr(5);
next_lfsr(5) = lfsr(6);
next_lfsr(6) = xor(lfsr(7),lfsr(1));
next_lfsr(7) = lfsr(8);
next_lfsr(8) = lfsr(9);
next_lfsr(9) = xor(lfsr(10),lfsr(1));
next_lfsr(10) = xor(lfsr(11),lfsr(1));
next_lfsr(11) = lfsr(12);
next_lfsr(12) = lfsr(13);
next_lfsr(13) = lfsr(14);
next_lfsr(14) = lfsr(15);
next_lfsr(15) = lfsr(16);
next_lfsr(16) = xor(lfsr(17), lfsr(1));
next_lfsr(17) = lfsr(18);
next_lfsr(18) = lfsr(19);
next_lfsr(19) = lfsr(20);
next_lfsr(20) = xor(lfsr(21),lfsr(1));
next_lfsr(21) = xor(lfsr(22),lfsr(1));
next_lfsr(22) = xor(lfsr(23),lfsr(1));
next_lfsr(23) = lfsr(24);
next_lfsr(24) = xor(lfsr(25), lfsr(1));
next_lfsr(25) = xor(lfsr(26), lfsr(1));
next_lfsr(26) = lfsr(27);
next_lfsr(27) = xor(lfsr(28), lfsr(1));
next_lfsr(28) = xor(lfsr(29), lfsr(1));
next_lfsr(29) = lfsr(30);
next_lfsr(30) = xor(lfsr(31), lfsr(1));
next_lfsr(31) = xor(lfsr(32), lfsr(1));
next_lfsr(32) = xor(data2(i), lfsr(1));
lfsr = next_lfsr;
end
crc32 = lfsr;
看到我首先使用 32 个零填充来计算 CRC-32(最后 LFSR 中剩下的就是我的 CRC-32,如果我这样做,用这个 CRC 替换零-32,最后我的LFSR也变空了,说明验证通过了)。
我使用的多项式是 CRC-32 的标准:04C11DB7。另请参阅顺序似乎颠倒了,但这只是因为它被镜像为在 MSB 中输入。当输入相同时,使用此表示和镜像的结果相同,只是结果也会被镜像。
任何想法都会有很大帮助。
提前致谢
您的 CRC 不是 CRC。输入的最后 32 位实际上并不参与计算,只是被异或运算到结果中。也就是说,如果你将数据的最后 32 位替换为零,进行你的计算,然后将数据的最后 32 位与结果 "crc32" 进行异或运算,那么你将得到相同的结果。[=16] =]
所以你永远不会让它匹配另一个 CRC 计算,因为它不是 CRC。
这段 C 代码复制了您的函数,其中数据位来自 p
处的 n
字节序列,最低有效位在前,结果是一个 32 位值:
unsigned long notacrc(void const *p, unsigned n) {
unsigned char const *dat = p;
unsigned long reg = 0xffffffff;
while (n) {
for (unsigned k = 0; k < 8; k++)
reg = reg & 1 ? (reg >> 1) ^ 0xedb88320 : reg >> 1;
reg ^= (unsigned long)*dat++ << 24;
n--;
}
return reg;
}
您可以立即看到数据的最后一个字节与最终寄存器值进行了简单的异或运算。不太明显的是,最后 4 个字节只是异或运算。这个完全等效的版本使这一点显而易见:
unsigned long notacrc_xor(void const *p, unsigned n) {
unsigned char const *dat = p;
// initial register values
unsigned long const init[] = {
0xffffffff, 0x2dfd1072, 0xbe26ed00, 0x00be26ed, 0xdebb20e3};
unsigned xor = n > 3 ? 4 : n; // number of bytes merely xor'ed
unsigned long reg = init[xor];
while (n > xor) {
reg ^= *dat++;
for (unsigned k = 0; k < 8; k++)
reg = reg & 1 ? (reg >> 1) ^ 0xedb88320 : reg >> 1;
n--;
}
switch (n) {
case 4:
reg ^= *dat++;
case 3:
reg ^= (unsigned long)*dat++ << 8;
case 2:
reg ^= (unsigned long)*dat++ << 16;
case 1:
reg ^= (unsigned long)*dat++ << 24;
}
return reg;
}
在那里你可以看到消息的最后四个字节,或者消息的所有字节,如果它是三个或更少的字节,与最后的最终寄存器值进行异或运算。
实际的 CRC 必须使用所有输入数据位来确定何时对寄存器进行异或多项式。最后一个函数的内部部分是 CRC 实现的样子(尽管更高效的版本利用预先计算的表一次处理一个或更多字节)。这是一个计算实际 CRC 的函数:
unsigned long crc32_jam(void const *p, unsigned n) {
unsigned char const *dat = p;
unsigned long reg = 0xffffffff;
while (n) {
reg ^= *dat++;
for (unsigned k = 0; k < 8; k++)
reg = reg & 1 ? (reg >> 1) ^ 0xedb88320 : reg >> 1;
n--;
}
return reg;
}
那个被称为 crc32_jam
是因为它实现了一个名为 "JAMCRC" 的特定 CRC。该 CRC 最接近您尝试实施的内容。
如果您想使用真正的 CRC,您将需要更新您的 Verilog 实现。
我在 Verilog 中实现了伽罗瓦线性反馈移位寄存器(也在 MATLAB 中,主要是为了模拟 HDL 设计)。它运行良好,据我所知,我使用 MATLAB 计算 CRC-32 字段,然后将它们包含在我的 HDL 模拟中以验证数据包是否已正确到达(使用 CRC-32 填充数据),这会产生良好的结果。
问题是我希望能够计算我在软件中实现的 CRC-32,因为我将使用 Raspberry Pi 通过我的 FPGA 中的 GPIO 输入数据,而且我还没有没能做到。我试过 this online calculator,使用相同的参数,但从未得到相同的结果。
这是我用来计算 CRC-32 的 MATLAB 代码:
N = 74*16;
data = [round(rand(1,N)) zeros(1,32)];
lfsr = ones(1,32);
next_lfsr = zeros(1,32);
for i = 1:length(data)
next_lfsr(1) = lfsr(2);
next_lfsr(2) = lfsr(3);
next_lfsr(3) = lfsr(4);
next_lfsr(4) = lfsr(5);
next_lfsr(5) = lfsr(6);
next_lfsr(6) = xor(lfsr(7),lfsr(1));
next_lfsr(7) = lfsr(8);
next_lfsr(8) = lfsr(9);
next_lfsr(9) = xor(lfsr(10),lfsr(1));
next_lfsr(10) = xor(lfsr(11),lfsr(1));
next_lfsr(11) = lfsr(12);
next_lfsr(12) = lfsr(13);
next_lfsr(13) = lfsr(14);
next_lfsr(14) = lfsr(15);
next_lfsr(15) = lfsr(16);
next_lfsr(16) = xor(lfsr(17), lfsr(1));
next_lfsr(17) = lfsr(18);
next_lfsr(18) = lfsr(19);
next_lfsr(19) = lfsr(20);
next_lfsr(20) = xor(lfsr(21),lfsr(1));
next_lfsr(21) = xor(lfsr(22),lfsr(1));
next_lfsr(22) = xor(lfsr(23),lfsr(1));
next_lfsr(23) = lfsr(24);
next_lfsr(24) = xor(lfsr(25), lfsr(1));
next_lfsr(25) = xor(lfsr(26), lfsr(1));
next_lfsr(26) = lfsr(27);
next_lfsr(27) = xor(lfsr(28), lfsr(1));
next_lfsr(28) = xor(lfsr(29), lfsr(1));
next_lfsr(29) = lfsr(30);
next_lfsr(30) = xor(lfsr(31), lfsr(1));
next_lfsr(31) = xor(lfsr(32), lfsr(1));
next_lfsr(32) = xor(data2(i), lfsr(1));
lfsr = next_lfsr;
end
crc32 = lfsr;
看到我首先使用 32 个零填充来计算 CRC-32(最后 LFSR 中剩下的就是我的 CRC-32,如果我这样做,用这个 CRC 替换零-32,最后我的LFSR也变空了,说明验证通过了)。
我使用的多项式是 CRC-32 的标准:04C11DB7。另请参阅顺序似乎颠倒了,但这只是因为它被镜像为在 MSB 中输入。当输入相同时,使用此表示和镜像的结果相同,只是结果也会被镜像。
任何想法都会有很大帮助。
提前致谢
您的 CRC 不是 CRC。输入的最后 32 位实际上并不参与计算,只是被异或运算到结果中。也就是说,如果你将数据的最后 32 位替换为零,进行你的计算,然后将数据的最后 32 位与结果 "crc32" 进行异或运算,那么你将得到相同的结果。[=16] =]
所以你永远不会让它匹配另一个 CRC 计算,因为它不是 CRC。
这段 C 代码复制了您的函数,其中数据位来自 p
处的 n
字节序列,最低有效位在前,结果是一个 32 位值:
unsigned long notacrc(void const *p, unsigned n) {
unsigned char const *dat = p;
unsigned long reg = 0xffffffff;
while (n) {
for (unsigned k = 0; k < 8; k++)
reg = reg & 1 ? (reg >> 1) ^ 0xedb88320 : reg >> 1;
reg ^= (unsigned long)*dat++ << 24;
n--;
}
return reg;
}
您可以立即看到数据的最后一个字节与最终寄存器值进行了简单的异或运算。不太明显的是,最后 4 个字节只是异或运算。这个完全等效的版本使这一点显而易见:
unsigned long notacrc_xor(void const *p, unsigned n) {
unsigned char const *dat = p;
// initial register values
unsigned long const init[] = {
0xffffffff, 0x2dfd1072, 0xbe26ed00, 0x00be26ed, 0xdebb20e3};
unsigned xor = n > 3 ? 4 : n; // number of bytes merely xor'ed
unsigned long reg = init[xor];
while (n > xor) {
reg ^= *dat++;
for (unsigned k = 0; k < 8; k++)
reg = reg & 1 ? (reg >> 1) ^ 0xedb88320 : reg >> 1;
n--;
}
switch (n) {
case 4:
reg ^= *dat++;
case 3:
reg ^= (unsigned long)*dat++ << 8;
case 2:
reg ^= (unsigned long)*dat++ << 16;
case 1:
reg ^= (unsigned long)*dat++ << 24;
}
return reg;
}
在那里你可以看到消息的最后四个字节,或者消息的所有字节,如果它是三个或更少的字节,与最后的最终寄存器值进行异或运算。
实际的 CRC 必须使用所有输入数据位来确定何时对寄存器进行异或多项式。最后一个函数的内部部分是 CRC 实现的样子(尽管更高效的版本利用预先计算的表一次处理一个或更多字节)。这是一个计算实际 CRC 的函数:
unsigned long crc32_jam(void const *p, unsigned n) {
unsigned char const *dat = p;
unsigned long reg = 0xffffffff;
while (n) {
reg ^= *dat++;
for (unsigned k = 0; k < 8; k++)
reg = reg & 1 ? (reg >> 1) ^ 0xedb88320 : reg >> 1;
n--;
}
return reg;
}
那个被称为 crc32_jam
是因为它实现了一个名为 "JAMCRC" 的特定 CRC。该 CRC 最接近您尝试实施的内容。
如果您想使用真正的 CRC,您将需要更新您的 Verilog 实现。