CRC32C with out-of-order blocks

crc32c.c

#include <stddef.h>
#include <stdint.h>

#define CRC_INITIAL                   0xFFFFFFFFUL
#define CRC_OUTPUT_XOR                0xFFFFFFFFUL
#define CRC_RESIDUE_BEFORE_OUTPUT_XOR 0xB798B438UL
#define CRC_RESIDUE_AFTER_OUTPUT_XOR  (CRC_RESIDUE_BEFORE_OUTPUT_XOR ^ CRC_OUTPUT_XOR)
#define CRC_SIZE_BYTES                4U

static const uint32_t crc_table[256] = {
    0x00000000UL, 0xF26B8303UL, 0xE13B70F7UL, 0x1350F3F4UL, 0xC79A971FUL, 0x35F1141CUL, 0x26A1E7E8UL, 0xD4CA64EBUL,
    0x8AD958CFUL, 0x78B2DBCCUL, 0x6BE22838UL, 0x9989AB3BUL, 0x4D43CFD0UL, 0xBF284CD3UL, 0xAC78BF27UL, 0x5E133C24UL,
    0x105EC76FUL, 0xE235446CUL, 0xF165B798UL, 0x030E349BUL, 0xD7C45070UL, 0x25AFD373UL, 0x36FF2087UL, 0xC494A384UL,
    0x9A879FA0UL, 0x68EC1CA3UL, 0x7BBCEF57UL, 0x89D76C54UL, 0x5D1D08BFUL, 0xAF768BBCUL, 0xBC267848UL, 0x4E4DFB4BUL,
    0x20BD8EDEUL, 0xD2D60DDDUL, 0xC186FE29UL, 0x33ED7D2AUL, 0xE72719C1UL, 0x154C9AC2UL, 0x061C6936UL, 0xF477EA35UL,
    0xAA64D611UL, 0x580F5512UL, 0x4B5FA6E6UL, 0xB93425E5UL, 0x6DFE410EUL, 0x9F95C20DUL, 0x8CC531F9UL, 0x7EAEB2FAUL,
    0x30E349B1UL, 0xC288CAB2UL, 0xD1D83946UL, 0x23B3BA45UL, 0xF779DEAEUL, 0x05125DADUL, 0x1642AE59UL, 0xE4292D5AUL,
    0xBA3A117EUL, 0x4851927DUL, 0x5B016189UL, 0xA96AE28AUL, 0x7DA08661UL, 0x8FCB0562UL, 0x9C9BF696UL, 0x6EF07595UL,
    0x417B1DBCUL, 0xB3109EBFUL, 0xA0406D4BUL, 0x522BEE48UL, 0x86E18AA3UL, 0x748A09A0UL, 0x67DAFA54UL, 0x95B17957UL,
    0xCBA24573UL, 0x39C9C670UL, 0x2A993584UL, 0xD8F2B687UL, 0x0C38D26CUL, 0xFE53516FUL, 0xED03A29BUL, 0x1F682198UL,
    0x5125DAD3UL, 0xA34E59D0UL, 0xB01EAA24UL, 0x42752927UL, 0x96BF4DCCUL, 0x64D4CECFUL, 0x77843D3BUL, 0x85EFBE38UL,
    0xDBFC821CUL, 0x2997011FUL, 0x3AC7F2EBUL, 0xC8AC71E8UL, 0x1C661503UL, 0xEE0D9600UL, 0xFD5D65F4UL, 0x0F36E6F7UL,
    0x61C69362UL, 0x93AD1061UL, 0x80FDE395UL, 0x72966096UL, 0xA65C047DUL, 0x5437877EUL, 0x4767748AUL, 0xB50CF789UL,
    0xEB1FCBADUL, 0x197448AEUL, 0x0A24BB5AUL, 0xF84F3859UL, 0x2C855CB2UL, 0xDEEEDFB1UL, 0xCDBE2C45UL, 0x3FD5AF46UL,
    0x7198540DUL, 0x83F3D70EUL, 0x90A324FAUL, 0x62C8A7F9UL, 0xB602C312UL, 0x44694011UL, 0x5739B3E5UL, 0xA55230E6UL,
    0xFB410CC2UL, 0x092A8FC1UL, 0x1A7A7C35UL, 0xE811FF36UL, 0x3CDB9BDDUL, 0xCEB018DEUL, 0xDDE0EB2AUL, 0x2F8B6829UL,
    0x82F63B78UL, 0x709DB87BUL, 0x63CD4B8FUL, 0x91A6C88CUL, 0x456CAC67UL, 0xB7072F64UL, 0xA457DC90UL, 0x563C5F93UL,
    0x082F63B7UL, 0xFA44E0B4UL, 0xE9141340UL, 0x1B7F9043UL, 0xCFB5F4A8UL, 0x3DDE77ABUL, 0x2E8E845FUL, 0xDCE5075CUL,
    0x92A8FC17UL, 0x60C37F14UL, 0x73938CE0UL, 0x81F80FE3UL, 0x55326B08UL, 0xA759E80BUL, 0xB4091BFFUL, 0x466298FCUL,
    0x1871A4D8UL, 0xEA1A27DBUL, 0xF94AD42FUL, 0x0B21572CUL, 0xDFEB33C7UL, 0x2D80B0C4UL, 0x3ED04330UL, 0xCCBBC033UL,
    0xA24BB5A6UL, 0x502036A5UL, 0x4370C551UL, 0xB11B4652UL, 0x65D122B9UL, 0x97BAA1BAUL, 0x84EA524EUL, 0x7681D14DUL,
    0x2892ED69UL, 0xDAF96E6AUL, 0xC9A99D9EUL, 0x3BC21E9DUL, 0xEF087A76UL, 0x1D63F975UL, 0x0E330A81UL, 0xFC588982UL,
    0xB21572C9UL, 0x407EF1CAUL, 0x532E023EUL, 0xA145813DUL, 0x758FE5D6UL, 0x87E466D5UL, 0x94B49521UL, 0x66DF1622UL,
    0x38CC2A06UL, 0xCAA7A905UL, 0xD9F75AF1UL, 0x2B9CD9F2UL, 0xFF56BD19UL, 0x0D3D3E1AUL, 0x1E6DCDEEUL, 0xEC064EEDUL,
    0xC38D26C4UL, 0x31E6A5C7UL, 0x22B65633UL, 0xD0DDD530UL, 0x0417B1DBUL, 0xF67C32D8UL, 0xE52CC12CUL, 0x1747422FUL,
    0x49547E0BUL, 0xBB3FFD08UL, 0xA86F0EFCUL, 0x5A048DFFUL, 0x8ECEE914UL, 0x7CA56A17UL, 0x6FF599E3UL, 0x9D9E1AE0UL,
    0xD3D3E1ABUL, 0x21B862A8UL, 0x32E8915CUL, 0xC083125FUL, 0x144976B4UL, 0xE622F5B7UL, 0xF5720643UL, 0x07198540UL,
    0x590AB964UL, 0xAB613A67UL, 0xB831C993UL, 0x4A5A4A90UL, 0x9E902E7BUL, 0x6CFBAD78UL, 0x7FAB5E8CUL, 0x8DC0DD8FUL,
    0xE330A81AUL, 0x115B2B19UL, 0x020BD8EDUL, 0xF0605BEEUL, 0x24AA3F05UL, 0xD6C1BC06UL, 0xC5914FF2UL, 0x37FACCF1UL,
    0x69E9F0D5UL, 0x9B8273D6UL, 0x88D28022UL, 0x7AB90321UL, 0xAE7367CAUL, 0x5C18E4C9UL, 0x4F48173DUL, 0xBD23943EUL,
    0xF36E6F75UL, 0x0105EC76UL, 0x12551F82UL, 0xE03E9C81UL, 0x34F4F86AUL, 0xC69F7B69UL, 0xD5CF889DUL, 0x27A40B9EUL,
    0x79B737BAUL, 0x8BDCB4B9UL, 0x988C474DUL, 0x6AE7C44EUL, 0xBE2DA0A5UL, 0x4C4623A6UL, 0x5F16D052UL, 0xAD7D5351UL,
};

static const uint32_t crc_zero_byte_mat[32] = {
    0xF26B8303UL, 0xE13B70F7UL, 0xC79A971FUL, 0x8AD958CFUL, 0x105EC76FUL, 0x20BD8EDEUL, 0x417B1DBCUL, 0x82F63B78UL,
    0x00000001UL, 0x00000002UL, 0x00000004UL, 0x00000008UL, 0x00000010UL, 0x00000020UL, 0x00000040UL, 0x00000080UL,
    0x00000100UL, 0x00000200UL, 0x00000400UL, 0x00000800UL, 0x00001000UL, 0x00002000UL, 0x00004000UL, 0x00008000UL,
    0x00010000UL, 0x00020000UL, 0x00040000UL, 0x00080000UL, 0x00100000UL, 0x00200000UL, 0x00400000UL, 0x00800000UL,
};

/// Do not forget to apply the output XOR when done, or use crc_compute().
static uint32_t crc_add(uint32_t crc, const size_t n_bytes, const void* const data)
{
    UDPARD_ASSERT((data != NULL) || (n_bytes == 0U));
    const byte_t* p = (const byte_t*)data;
    for (size_t i = 0; i < n_bytes; i++) {
        crc = (crc >> 8U) ^ crc_table[(*p++) ^ (crc & 0xFFU)];
    }
    return crc;
}

/// Multiply 32x32 GF(2) column-major matrix by a 32-bit vector.
static uint32_t gf2_matrix_vector_product(const uint32_t mat[32], uint32_t vec)
{
    uint32_t     sum = 0;
    uint_fast8_t bit = 0;
    while (vec > 0) {
        if ((vec & 1U) != 0) {
            sum ^= mat[bit];
        }
        vec >>= 1U;
        bit++;
    }
    return sum;
}

/// Square a 32x32 GF(2) column-major matrix. Both out_result and mat may refer to the same memory.
static void gf2_matrix_square(uint32_t out_result[32], const uint32_t mat[32])
{
    uint32_t tmp[32];
    for (uint_fast8_t i = 0; i < 32; i++) {
        tmp[i] = gf2_matrix_vector_product(mat, mat[i]);
    }
    memcpy(out_result, tmp, sizeof(tmp));
}

/// Advance a CRC remainder by n_bytes of zero bytes. I.e. returns crc(M||0...0) given crc(M).
static uint32_t crc_shift_zeros_bytes(uint32_t crc, size_t n_bytes)
{
    uint32_t power[32]; // Exponentiation-by-squaring on the 32x32 matrix for one zero byte.
    memcpy(power, crc_zero_byte_mat, sizeof(crc_zero_byte_mat));
    while (n_bytes > 0) {
        if ((n_bytes & 1U) != 0) {
            crc = gf2_matrix_vector_product(power, crc);
        }
        n_bytes >>= 1U;
        if (n_bytes > 0) {
            gf2_matrix_square(power, power);
        }
    }
    return crc;
}

static uint32_t crc_full(const size_t n_bytes, const void* const data)
{
    return crc_add(CRC_INITIAL, n_bytes, data) ^ CRC_OUTPUT_XOR;
}

/// All partial CRC values must be xor-ed together and passed to crc_partial_finalize() to obtain the final CRC.
/// Xor is commutative, so the fragments may appear in any order.
static uint32_t crc_partial(const size_t      total_size_bytes,
                            const size_t      fragment_offset_bytes,
                            const size_t      fragment_size_bytes,
                            const void* const fragment_data)
{
    const uint32_t crc         = crc_add(0, fragment_size_bytes, fragment_data);
    const size_t   bytes_after = total_size_bytes - (fragment_offset_bytes + fragment_size_bytes);
    return crc_shift_zeros_bytes(crc, bytes_after); // Move this fragment's remainder as if trail zeros followed.
}

/// Finalize the CRC computation for unordered data fragments.
/// Accepts the total data size in bytes and the xor of all partial CRCs in an arbitrary order.
static uint32_t crc_partial_finalize(const size_t n_bytes, const uint32_t crc_acc_raw)
{
    const uint32_t K = ~crc_shift_zeros_bytes(CRC_INITIAL, n_bytes); // Correction term K(L) = ~advance(CRC_INITIAL, L)
    return crc_acc_raw ^ K;                                          // Standard CRC = raw(M) xor K(L)
}

crc32c_test.c

#include <unity.h>
#include <stddef.h>
#include <stdint.h>

static void test_crc_streamed(void)
{
    uint32_t crc = crc_add(CRC_INITIAL, 3, "123");
    crc          = crc_add(crc, 6, "456789");
    TEST_ASSERT_EQUAL_UINT32(0x1CF96D7CUL, crc);
    TEST_ASSERT_EQUAL_UINT32(0xE3069283UL, crc ^ CRC_OUTPUT_XOR);
    crc = crc_add(crc, 4, "\x83\x92\x06\xE3"); // Least significant byte first.
    TEST_ASSERT_EQUAL_UINT32(CRC_RESIDUE_BEFORE_OUTPUT_XOR, crc);
    TEST_ASSERT_EQUAL_UINT32(CRC_RESIDUE_AFTER_OUTPUT_XOR, crc ^ CRC_OUTPUT_XOR);
}

static void test_crc_unordered(void)
{
    {
        const uint32_t partials[] = {
            crc_partial(9, 0, 2, "12"),
            crc_partial(9, 2, 3, "345"),
            crc_partial(9, 5, 4, "6789"),
        };
        const uint32_t crc = crc_partial_finalize(9, partials[1] ^ partials[2] ^ partials[0]); // xor is commutative
        TEST_ASSERT_EQUAL_UINT32(0xE3069283UL, crc);
    }
    {
        const uint32_t partials[] = {
            crc_partial(13, 0, 2, "12"),
            crc_partial(13, 2, 3, "345"),
            crc_partial(13, 5, 4, "6789"),
            crc_partial(13, 9, 4, "\x83\x92\x06\xE3"),
        };
        const uint32_t crc = crc_partial_finalize(13, partials[1] ^ partials[3] ^ partials[2] ^ partials[0]);
        TEST_ASSERT_EQUAL_UINT32(CRC_RESIDUE_AFTER_OUTPUT_XOR, crc);
    }
}