Как рассчитать CRC32 по блокам, которые разбиты и буферизованы из больших данных?

Question

Допустим, у меня есть данные размером 1024 КБ, которые буферизуются 1 КБ и передаются 1024 раза от передатчика к приемнику.

Последний буфер содержит вычисленное значение CRC32 как последние 4 байта.

Однако получатель должен вычислять буфер CRC32 по буферу из-за ограничений ОЗУ.

Интересно, как применить линейное распределенное сложение вычислений CRC32, чтобы соответствовать общему значению CRC32.

Я посмотрел на расчет CRC и его распределительные предпочтения. Расчет и его линейность не очень понятны для реализации.

Итак, существует ли математическое выражение для добавления вычисленных значений CRC32 к буферам для соответствия результату CRC32, который рассчитывается по общему количеству?

Такие как:

int CRC32Total = 0;
int CRC32[1024];
for(int i = 0; i < 1024; i++){
    CRC32Total = CRC32Total + CRC32[i];
}

С уважением

Answer 1

Когда вы начнете передачу, сбросьте CrcChecksum к его начальному значению с помощью метода OnFirstBlock. Для каждого полученного блока вызовите 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);
}

Answer 2

Вы не предоставили никаких подсказок относительно того, какую реализацию или даже какой язык вы "рассматривали при расчете CRC". Однако каждая реализация, которую я видел, предназначена для вычисления CRC по частям, точно так, как вы хотите.

Для crc32() подпрограмма, представленная в zlib, используется следующим образом (в 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, например, если вам нужно разделить вычисление CRC на несколько ЦП, тогда zlib предоставляет crc32_combine() функция для этой цели.

Answer 3

Чтобы дополнить свой комментарий к вашему вопросу, я добавил здесь код, который проходит весь процесс: генерация данных в виде линейного массива, добавление CRC32 к передаваемым данным, внедрение ошибок и получение "кусочков" с вычисленным CRC32 и обнаружение ошибки. Вы, вероятно, интересуетесь только частью "приема", но я думаю, что полный пример делает это более понятным для вашего понимания.

#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");
    }
}