反转CRC32 /从CRC32中删除字节

Question

我有一个应用程序，它计算一些长度为l的数据流的crc32。但是，我想从最终的crc32结果中删除最后4个字节，这意味着我实际上希望结果是长度为(l-4)的数据的crc32。有没有一种有效的方法来做到这一点？

编辑:我知道我想排除的最后4个字节。

Answer 1

是的这是可能的。

首先，CRC是线性的，所以我们可以通过计算crcOfData ^ crc(last4Bytes)找到如果最后4个字节是0的CRC。不过，根据CRC的详细情况，这里有一些细微的变化。

其次，“移除最后一位假定它是零”的动作可以由一个32x32布尔矩阵来建模，即：

uint32_t inv1[32];
uint32_t row = 2;
for (int n = 0; n < 31; n++) {
    inv1[n] = row;
    row <<= 1;
}
inv1[31] = 0x05EC76F1; // reciprocal of your crc polynomial (I used the one that matches _mm_crc32)

“删除32个零位”的矩阵可以通过对矩阵平方几次来找到：

uint32_t inv[32];
gf2_matrix_square(inv, inv1); // 2
gf2_matrix_square(inv1, inv); // 4
gf2_matrix_square(inv, inv1); // 8
gf2_matrix_square(inv1, inv); // 16
gf2_matrix_square(inv, inv1); // 32


uint32_t gf2_matrix_times(uint32_t *mat, uint32_t vec)
{
    uint32_t sum = 0;
    while (vec) {
        if (vec & 1)
            sum ^= *mat;
        vec >>= 1;
        mat++;
    }
    return sum;
}

void gf2_matrix_square(uint32_t *square, uint32_t *mat)
{
    for (int n = 0; n < 32; n++)
        square[n] = gf2_matrix_times(mat, mat[n]);
}

由于矩阵平方5次与数据无关，因此可以对结果进行硬编码。

实际的“删除4个字节”可以在gf2_matrix_times(inv, crcOfData ^ crc(last4Bytes))中找到，例如，只是为了验证它是否工作：

auto crc0 = _mm_crc32_u32(0, 0xDEADBEEF);
auto crc1 = _mm_crc32_u32(crc0, 0xCAFEBABE);
auto undo = gf2_matrix_times(inv, crc1 ^ _mm_crc32_u32(0, 0xCAFEBABE));