How to calculate CRC32 over blocks that are splitted and buffered of a large data?

Question

Let's say I have a 1024kb data, which is 1kB buffered and transfered 1024 times from a transmitter to a receiver.

The last buffer contains a calculated CRC32 value as the last 4 bytes.

However, the receiver has to calculate the CRC32 buffer by buffer, because of the RAM constraints.

I wonder how to apply a linear distributed addition of CRC32 calculations to match the total CRC32 value.

I looked at CRC calculation and its distributive preference. The calculation and its linearity is not much clear to implement.

So, is there a mathematical expression for addition of calculated CRC32s over buffers to match with the CRC32 result which is calculated over total?

Such as:

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

Kind Regards

Answer 1

When you start the transfer, reset the CrcChecksum to its initial value with the OnFirstBlock method. For every block received, call the OnBlockReceived to update the checksum. Note that the blocks must be processed in the correct order. When the final block has been processed, the final CRC is in the CrcChecksum variable.

// 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

You did not provide any clues as to what implementation or even what language for which you "looked at CRC calculation". However every implementation I've seen is designed to compute CRCs piecemeal, exactly like you want.

For the crc32() routine provided in zlib, it is used thusly (in 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

Then crc is the CRC of the concatenation of all of the chunks. You do not need a function to combine the CRCs of individual chunks.

If for some other reason you do want a function to combine CRCs, e.g. if you need to split the CRC calculation over multiple CPUs, then zlib provides the crc32_combine() function for that purpose.

Answer 3

To complement my comment to your question, I have added code here that goes thru the whole process: data generation as a linear array, CRC32 added to the transmitted data, injection of errors, and reception in 'chunks' with computed CRC32 and detection of errors. You're probably only interested in the 'reception' part, but I think having a complete example makes it more clear for your comprehension.

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