如何计算大数据拆分和缓冲的块的CRC32?
How to calculate CRC32 over blocks that are splitted and buffered of a large data?
假设我有一个 1024kb 的数据,该数据经过 1kB 缓冲并从发送器传输到接收器 1024 次。
最后一个缓冲区包含计算出的 CRC32 值作为最后 4 个字节。
但是,由于 RAM 的限制,接收方必须逐个缓冲区计算 CRC32 缓冲区。
我想知道如何应用 CRC32 计算的线性分布式加法来匹配总的 CRC32 值。
我查看了 CRC 计算及其分配偏好。计算及其线性度实施起来不是很清楚。
那么,是否有一个数学表达式可以将计算出的 CRC32 加到缓冲区上以匹配总计计算出的 CRC32 结果?
如:
int CRC32Total = 0;
int CRC32[1024];
for(int i = 0; i < 1024; i++){
CRC32Total = CRC32Total + CRC32[i];
}
亲切的问候
开始传输时,使用 OnFirstBlock 方法将 CrcChecksum 重置为其初始值。对于接收到的每个块,调用 OnBlockReceived 来更新校验和。请注意,必须以正确的顺序处理块。处理完最后一个块后,最终的 CRC 校验码位于 CrcChecksum 变量中。
// In crc32.c
uint32_t UpdateCrc(uint32_t crc, const void *data, size_t length)
const uint8_t *current = data;
while (length--)
crc = (crc >> 8) ^ Crc32Lookup[(crc & 0xFF) ^ *current++];
}
// In your block processing application
static uint32_t CrcChecksum;
void OnFirstBlock(void) {
CrcChecksum = 0;
}
void OnBlockReceived(const void *data, size_t length) {
CrcChecksum = UpdateCrc(CrcChecksum, data, length);
}
您没有提供任何关于您 "looked at CRC calculation" 的实现方式甚至语言的线索。然而,我见过的每个实现都旨在零碎地计算 CRC,完全按照您的需要。
对于zlib中提供的crc32()
例程,是这样使用的(在C中):
crc = crc32(0, NULL, 0); // initialize CRC value
crc = crc32(crc, firstchunk, 1024); // update CRC value with first chunk
crc = crc32(crc, secondchunk, 1024); // update CRC with second chunk
...
crc = crc32(crc, lastchunk, 1024); // complete CRC with the last chunk
然后crc
是所有块串联的CRC。您不需要一个函数来组合各个块的 CRC。
如果出于某些其他原因您确实想要一个函数来组合 CRC,例如如果您需要在多个 CPU 上拆分 CRC 计算,那么 zlib 会为此目的提供 crc32_combine()
函数。
为了补充我对你的问题的评论,我在此处添加了贯穿整个过程的代码:数据生成为线性数组、CRC32 添加到传输数据、错误注入和接收 'chunks' 计算出的 CRC32 和错误检测。你可能只对 'reception' 部分感兴趣,但我认为有一个完整的例子会让你的理解更清楚。
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
// ---------------------- buildCRC32table ------------------------------
static const uint32_t CRC32_POLY = 0xEDB88320;
static const uint32_t CRC32_XOR_MASK = 0xFFFFFFFF;
static uint32_t CRC32TABLE[256];
void buildCRC32table (void)
{
uint32_t crc32;
for (uint16_t byte = 0; byte < 256; byte++)
{
crc32 = byte;
// iterate thru all 8 bits
for (int i = 0; i < 8; i++)
{
uint8_t feedback = crc32 & 1;
crc32 = (crc32 >> 1);
if (feedback)
{
crc32 ^= CRC32_POLY;
}
}
CRC32TABLE[byte] = crc32;
}
}
// -------------------------- myCRC32 ----------------------------------
uint32_t myCRC32 (uint32_t previousCRC32, uint8_t *pData, int dataLen)
{
uint32_t newCRC32 = previousCRC32 ^ CRC32_XOR_MASK; // remove last XOR mask (or add first)
// add new data to CRC32
while (dataLen--)
{
uint32_t crc32Top24bits = newCRC32 >> 8;
uint8_t crc32Low8bits = newCRC32 & 0x000000FF;
uint8_t data = *pData++;
newCRC32 = crc32Top24bits ^ CRC32TABLE[crc32Low8bits ^ data];
}
newCRC32 ^= CRC32_XOR_MASK; // put XOR mask back
return newCRC32;
}
// ------------------------------ main ---------------------------------
int main()
{
// build CRC32 table
buildCRC32table();
uint32_t crc32;
// use a union so we can access the same data linearly (TX) or by chunks (RX)
union
{
uint8_t array[1024*1024];
uint8_t chunk[1024][1024];
} data;
// use time to seed randomizer so we have different data every run
srand((unsigned int)time(NULL));
/////////////////////////////////////////////////////////////////////////// Build data to be transmitted
////////////////////////////////////////////////////////////////////////////////////////////////////////
// populate array with random data sparing space for the CRC32 at the end
for (int i = 0; i < (sizeof(data.array) - sizeof(uint32_t)); i++)
{
data.array[i] = (uint8_t) (rand() & 0xFF);
}
// now compute array's CRC32
crc32 = myCRC32(0, data.array, sizeof(data.array) - sizeof(uint32_t));
printf ("array CRC32 = 0x%08X\n", crc32);
// to store the CRC32 into the array, we want to remove the XOR mask so we can compute the CRC32
// of all received data (including the CRC32 itself) and expect the same result all the time,
// regardless of the data, when no errors are present
crc32 ^= CRC32_XOR_MASK;
// load CRC32 at the very end of the array
data.array[sizeof(data.array) - 1] = (uint8_t)((crc32 >> 24) & 0xFF);
data.array[sizeof(data.array) - 2] = (uint8_t)((crc32 >> 16) & 0xFF);
data.array[sizeof(data.array) - 3] = (uint8_t)((crc32 >> 8) & 0xFF);
data.array[sizeof(data.array) - 4] = (uint8_t)((crc32 >> 0) & 0xFF);
/////////////////////////////////////////////// At this point, data is transmitted and errors may happen
////////////////////////////////////////////////////////////////////////////////////////////////////////
// to make things interesting, let's add one bit error with 1/8 probability
if ((rand() % 8) == 0)
{
uint32_t index = rand() % sizeof(data.array);
uint8_t errorBit = 1 << (rand() & 0x7);
// add error
data.array[index] ^= errorBit;
printf("Error injected on byte %u, bit mask = 0x%02X\n", index, errorBit);
}
else
{
printf("No error injected\n");
}
/////////////////////////////////////////////////////// Once received, the data is processed in 'chunks'
////////////////////////////////////////////////////////////////////////////////////////////////////////
// now we access the data and compute its CRC32 one chunk at a time
crc32 = 0; // initialize CRC32
for (int i = 0; i < 1024; i++)
{
crc32 = myCRC32(crc32, data.chunk[i], sizeof data.chunk[i]);
}
printf ("Final CRC32 = 0x%08X\n", crc32);
// because the CRC32 algorithm applies an XOR mask at the end, when we have no errors, the computed
// CRC32 will be the mask itself
if (crc32 == CRC32_XOR_MASK)
{
printf ("No errors detected!\n");
}
else
{
printf ("Errors detected!\n");
}
}
假设我有一个 1024kb 的数据,该数据经过 1kB 缓冲并从发送器传输到接收器 1024 次。
最后一个缓冲区包含计算出的 CRC32 值作为最后 4 个字节。
但是,由于 RAM 的限制,接收方必须逐个缓冲区计算 CRC32 缓冲区。
我想知道如何应用 CRC32 计算的线性分布式加法来匹配总的 CRC32 值。
我查看了 CRC 计算及其分配偏好。计算及其线性度实施起来不是很清楚。
那么,是否有一个数学表达式可以将计算出的 CRC32 加到缓冲区上以匹配总计计算出的 CRC32 结果?
如:
int CRC32Total = 0;
int CRC32[1024];
for(int i = 0; i < 1024; i++){
CRC32Total = CRC32Total + CRC32[i];
}
亲切的问候
开始传输时,使用 OnFirstBlock 方法将 CrcChecksum 重置为其初始值。对于接收到的每个块,调用 OnBlockReceived 来更新校验和。请注意,必须以正确的顺序处理块。处理完最后一个块后,最终的 CRC 校验码位于 CrcChecksum 变量中。
// In crc32.c
uint32_t UpdateCrc(uint32_t crc, const void *data, size_t length)
const uint8_t *current = data;
while (length--)
crc = (crc >> 8) ^ Crc32Lookup[(crc & 0xFF) ^ *current++];
}
// In your block processing application
static uint32_t CrcChecksum;
void OnFirstBlock(void) {
CrcChecksum = 0;
}
void OnBlockReceived(const void *data, size_t length) {
CrcChecksum = UpdateCrc(CrcChecksum, data, length);
}
您没有提供任何关于您 "looked at CRC calculation" 的实现方式甚至语言的线索。然而,我见过的每个实现都旨在零碎地计算 CRC,完全按照您的需要。
对于zlib中提供的crc32()
例程,是这样使用的(在C中):
crc = crc32(0, NULL, 0); // initialize CRC value
crc = crc32(crc, firstchunk, 1024); // update CRC value with first chunk
crc = crc32(crc, secondchunk, 1024); // update CRC with second chunk
...
crc = crc32(crc, lastchunk, 1024); // complete CRC with the last chunk
然后crc
是所有块串联的CRC。您不需要一个函数来组合各个块的 CRC。
如果出于某些其他原因您确实想要一个函数来组合 CRC,例如如果您需要在多个 CPU 上拆分 CRC 计算,那么 zlib 会为此目的提供 crc32_combine()
函数。
为了补充我对你的问题的评论,我在此处添加了贯穿整个过程的代码:数据生成为线性数组、CRC32 添加到传输数据、错误注入和接收 'chunks' 计算出的 CRC32 和错误检测。你可能只对 'reception' 部分感兴趣,但我认为有一个完整的例子会让你的理解更清楚。
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
// ---------------------- buildCRC32table ------------------------------
static const uint32_t CRC32_POLY = 0xEDB88320;
static const uint32_t CRC32_XOR_MASK = 0xFFFFFFFF;
static uint32_t CRC32TABLE[256];
void buildCRC32table (void)
{
uint32_t crc32;
for (uint16_t byte = 0; byte < 256; byte++)
{
crc32 = byte;
// iterate thru all 8 bits
for (int i = 0; i < 8; i++)
{
uint8_t feedback = crc32 & 1;
crc32 = (crc32 >> 1);
if (feedback)
{
crc32 ^= CRC32_POLY;
}
}
CRC32TABLE[byte] = crc32;
}
}
// -------------------------- myCRC32 ----------------------------------
uint32_t myCRC32 (uint32_t previousCRC32, uint8_t *pData, int dataLen)
{
uint32_t newCRC32 = previousCRC32 ^ CRC32_XOR_MASK; // remove last XOR mask (or add first)
// add new data to CRC32
while (dataLen--)
{
uint32_t crc32Top24bits = newCRC32 >> 8;
uint8_t crc32Low8bits = newCRC32 & 0x000000FF;
uint8_t data = *pData++;
newCRC32 = crc32Top24bits ^ CRC32TABLE[crc32Low8bits ^ data];
}
newCRC32 ^= CRC32_XOR_MASK; // put XOR mask back
return newCRC32;
}
// ------------------------------ main ---------------------------------
int main()
{
// build CRC32 table
buildCRC32table();
uint32_t crc32;
// use a union so we can access the same data linearly (TX) or by chunks (RX)
union
{
uint8_t array[1024*1024];
uint8_t chunk[1024][1024];
} data;
// use time to seed randomizer so we have different data every run
srand((unsigned int)time(NULL));
/////////////////////////////////////////////////////////////////////////// Build data to be transmitted
////////////////////////////////////////////////////////////////////////////////////////////////////////
// populate array with random data sparing space for the CRC32 at the end
for (int i = 0; i < (sizeof(data.array) - sizeof(uint32_t)); i++)
{
data.array[i] = (uint8_t) (rand() & 0xFF);
}
// now compute array's CRC32
crc32 = myCRC32(0, data.array, sizeof(data.array) - sizeof(uint32_t));
printf ("array CRC32 = 0x%08X\n", crc32);
// to store the CRC32 into the array, we want to remove the XOR mask so we can compute the CRC32
// of all received data (including the CRC32 itself) and expect the same result all the time,
// regardless of the data, when no errors are present
crc32 ^= CRC32_XOR_MASK;
// load CRC32 at the very end of the array
data.array[sizeof(data.array) - 1] = (uint8_t)((crc32 >> 24) & 0xFF);
data.array[sizeof(data.array) - 2] = (uint8_t)((crc32 >> 16) & 0xFF);
data.array[sizeof(data.array) - 3] = (uint8_t)((crc32 >> 8) & 0xFF);
data.array[sizeof(data.array) - 4] = (uint8_t)((crc32 >> 0) & 0xFF);
/////////////////////////////////////////////// At this point, data is transmitted and errors may happen
////////////////////////////////////////////////////////////////////////////////////////////////////////
// to make things interesting, let's add one bit error with 1/8 probability
if ((rand() % 8) == 0)
{
uint32_t index = rand() % sizeof(data.array);
uint8_t errorBit = 1 << (rand() & 0x7);
// add error
data.array[index] ^= errorBit;
printf("Error injected on byte %u, bit mask = 0x%02X\n", index, errorBit);
}
else
{
printf("No error injected\n");
}
/////////////////////////////////////////////////////// Once received, the data is processed in 'chunks'
////////////////////////////////////////////////////////////////////////////////////////////////////////
// now we access the data and compute its CRC32 one chunk at a time
crc32 = 0; // initialize CRC32
for (int i = 0; i < 1024; i++)
{
crc32 = myCRC32(crc32, data.chunk[i], sizeof data.chunk[i]);
}
printf ("Final CRC32 = 0x%08X\n", crc32);
// because the CRC32 algorithm applies an XOR mask at the end, when we have no errors, the computed
// CRC32 will be the mask itself
if (crc32 == CRC32_XOR_MASK)
{
printf ("No errors detected!\n");
}
else
{
printf ("Errors detected!\n");
}
}