crc32_combine()的矩阵技巧的逆是什么? [英] What is the inverse of crc32_combine()'s matrix trick?

问题描述

zlib的crc32_combine()使用crcA，crcB和lengthB来计算crcAB.

zlib's crc32_combine() takes crcA, crcB, and lengthB to calculate crcAB.

# returns crcAB
crc32_combine(crcA, crcB, lenB)

使用Mark Adler出色文章中的概念此处和此处产生 crc32_trim_trailing.pl ， ，和lengthB来计算crcA(我用它来剥离已知长度和值的填充).

Using concepts from Mark Adler's awesome posts here and here I was able to produce crc32_trim_trailing.pl which takes crcAB, crcB, and lengthB to calculate crcA (I use this to peel off padding of a known length and value).

# prints crcA
perl crc32_trim_trailing.pl $crcAB $crcB $lenB

不幸的是，它使用了所描述的慢速方法的原理，其中每个空字节必须一次被剥离一个.速度很慢，但是很好地证明了这一点.

Unfortunately, this uses the principles of the slow method described, where each null byte must be peeled off one at a time. It's slow, but is a good proof of concept.

我一直在努力制作crc32_trim_trailing的快速版本，该版本利用了Mark帖子中描述的矩阵技巧，并在zlib的crc32_combine()中实现了组合用例.

I've been working to make a fast version of crc32_trim_trailing which makes use of the matrix trick described in Mark's posts and implemented for the combining use case in zlib's crc32_combine().

这是我对crc32_trim_trailing.c的尝试.

Here is my attempt at crc32_trim_trailing.c.

/* crc32_trim_trailing.c
  This code is borrows heavily from crc32.c from zlib version 1.2.8, but has
  been altered.
*/

#include <stdio.h>

#define GF2_DIM 32      /* dimension of GF(2) vectors (length of CRC) */

/* ========================================================================= */
unsigned long gf2_matrix_times(mat, vec)
    unsigned long *mat;
    unsigned long vec;
{
    unsigned long sum;

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

/* ========================================================================= */
void gf2_matrix_square(square, mat)
    unsigned long *square;
    unsigned long *mat;
{
    int n;

    for (n = 0; n < GF2_DIM; n++)
        square[n] = gf2_matrix_times(mat, mat[n]);
}

/* ========================================================================= */
int main(int argc, char *argv[])
{
    unsigned long crc1;
    unsigned long crc2;
    int len2;

    sscanf(argv[1], "%lx", &crc1);
    sscanf(argv[2], "%lx", &crc2);
    sscanf(argv[3],  "%d", &len2);

    int n;
    unsigned long row;
    unsigned long even[GF2_DIM];    /* even-power-of-two zeros operator */
    unsigned long odd[GF2_DIM];     /* odd-power-of-two zeros operator */

    /* degenerate case (also disallow negative lengths) */
    if (len2 <= 0)
        return crc1;

    /* get crcA0 */
    crc1 ^= crc2;

    /* put operator for one zero bit in odd */
    odd[0] = 0x82608edbUL;          /* used sage math to get inverse matrix polynomial */
    row = 1;
    for (n = 1; n < GF2_DIM; n++) {
        odd[n] = row;
        row <<= 1;
    }

    /* put operator for two zero bits in even */
    gf2_matrix_square(even, odd);

    /* put operator for four zero bits in odd */
    gf2_matrix_square(odd, even);

    /* apply len2 zeros to crc1 (first square will put the operator for one
       zero byte, eight zero bits, in even) */
    do {
        /* apply zeros operator for this bit of len2 */
        gf2_matrix_square(even, odd);
        if (len2 & 1)
            crc1 = gf2_matrix_times(even, crc1);
        len2 >>= 1;

        /* if no more bits set, then done */
        if (len2 == 0)
            break;

        /* another iteration of the loop with odd and even swapped */
        gf2_matrix_square(odd, even);
        if (len2 & 1)
            crc1 = gf2_matrix_times(odd, crc1);
        len2 >>= 1;

        /* if no more bits set, then done */
    } while (len2 != 0);

    printf("\nCRC: %lx\n", crc1);

    return 0;
}

我将xor移到矩阵乘法之前.这似乎没有问题，并且通过对crcAB和crcB进行异或运算而为我们提供了crcA0.

I moved the xor to be before the matrix multiplication. This appears to work without issue and gives us crcA0 by xoring crcAB and crcB.

接下来，使用鼠尾草数学运算，我能够找到crc32_combine()中使用的初始矩阵的逆矩阵.

Next, using sage math I was able to find the inverse matrix of the initial matrix used in crc32_combine().

将这些矩阵中的每个矩阵运行3个平方会导致矩阵crc32_combine()用于添加1个空字节(matrixA)，然后将其取反(matrixB).

Running each of these matricies through 3 squares results in the matrix crc32_combine() uses to add 1 null byte (matrixA) and it's inverse (matrixB).

使用鼠尾草数学，我确认了以下内容.

Using sage math I confirmed the following.

• 矩阵A *矩阵B =身份
• crc *身份= crc
• crc *矩阵A *矩阵B = crc

代码:

M = MatrixSpace(GF(2),32,32)
A = M([0,1,1,1,0,1,1,1,0,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,1,0,0,1,0,1,1,0,
1,1,1,0,1,1,1,0,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,1,0,0,1,0,1,1,0,0,
0,0,0,0,0,1,1,1,0,1,1,0,1,1,0,1,1,1,0,0,0,1,0,0,0,0,0,1,1,0,0,1,
0,0,0,0,1,1,1,0,1,1,0,1,1,0,1,1,1,0,0,0,1,0,0,0,0,0,1,1,0,0,1,0,
0,0,0,1,1,1,0,1,1,0,1,1,0,1,1,1,0,0,0,1,0,0,0,0,0,1,1,0,0,1,0,0,
0,0,1,1,1,0,1,1,0,1,1,0,1,1,1,0,0,0,1,0,0,0,0,0,1,1,0,0,1,0,0,0,
0,1,1,1,0,1,1,0,1,1,0,1,1,1,0,0,0,1,0,0,0,0,0,1,1,0,0,1,0,0,0,0,
1,1,1,0,1,1,0,1,1,0,1,1,1,0,0,0,1,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0])

B = A^-1

I = A*B

print "matrixA"
print A.str()
print "matrixB"
print B.str()
print "identity"
print I.str()

N = MatrixSpace(GF(2),1,32)
THIS=N([1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,1,1,1])

print "'this' crc * identity"
print THIS * I
print "'this' crc * maxtrixA"
print THIS * A
print "'this' crc * maxtrixA * matrixB"
print THIS * A * B

输出:

matrixA
[0 1 1 1 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 0]
[1 1 1 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 0 0]
[0 0 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1]
[0 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0]
[0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0]
[0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0]
[0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0]
[1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
matrixB
[1 0 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0]
[0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1 1 0 1 0 0 0 0 1 1 1 1 1 0 1 1]
[1 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1 1 0 1 0 0 0 0 1 1 1 1 1 0 1 1 0]
[0 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 0 0 1 0 1 1 0 1 1]
[1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 0 0 1 0 1 1 0 1 1 0]
[0 1 1 0 0 0 0 1 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 1]
[1 1 0 0 0 0 1 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 1 0]
[1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
identity
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
'this' crc * identity
[1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 1 1]
'this' crc * maxtrixA
[1 1 0 0 0 0 0 0 0 1 0 1 1 1 1 0 0 0 1 0 1 1 0 1 1 1 0 1 1 0 1 0]
'this' crc * maxtrixA * matrixB
[1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 1 1]

我使用crc和恒等矩阵测试了gf2_matrix_times()，正如预期的那样，crc没有变化.

I tested gf2_matrix_times() using a crc and the identity matrix which as expected resulted in no change to the crc.

由于gf2_matrix_times(crc，matrixA)可用于向crc添加1个空字节，所以我希望gf2_matrix_times(crc，matrixB)可用于删除1个空字节.但是，这似乎开箱即用.

Since gf2_matrix_times(crc, matrixA) can be used to add 1 null byte to the crc, I had hoped gf2_matrix_times(crc, matrixB) could be used to remove 1 null byte. However, this does not appear to work out of the box.

另外，当lengthB为1时，贤哲数学中的crc * matrixA与crc32_combine()中的crcA0(0xa5f45be9)产生不同的结果(0xc05e2dda).

Additionally, crc * matrixA in sage math produces a different result (0xc05e2dda) than crcA0 (0xa5f45be9) in crc32_combine() when lengthB is 1.

为什么鼠尾草数学和gf2_matrix_times()之间的GF(2)矩阵乘法有差异? 为什么当矩阵A和矩阵B取反时，gf2_matrix_times(crc，matrixB)不能反转gf2_matrix_times(crc，matrixA)?

Why is there disparity in GF(2) matrix multiplication between sage math and gf2_matrix_times()? Why does gf2_matrix_times(crc, matrixB) not reverse gf2_matrix_times(crc, matrixA) when matrixA and matrixB are inverse?

推荐答案

我们将首先研究标准CRC-32的简单逐位实现(作为CRC的自包含定义，此例程将返回初始CRC，即data为NULL时空字符串的CRC):

We will begin by looking at a simple bit-wise implementation of the standard CRC-32 (to be a self-contained definition of the CRC, this routine returns the initial CRC, i.e. the CRC of the empty string, when data is NULL):

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

#define POLY 0xedb88320

uint32_t crc32(uint32_t crc, void const *data, size_t len) {
    if (data == NULL)
        return 0;
    crc = ~crc;
    while (len--) {
        crc ^= *(unsigned char const *)data++;
        for (int k = 0; k < 8; k++)
            crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
    }
    crc = ~crc;
    return crc;
}

我们可以简化为将n零应用于CRC的操作:

We can simplify that for applying n zeros to a CRC:

uint32_t crc32_zeros(uint32_t crc, size_t n) {
    crc = ~crc;
    while (n--)
        for (int k = 0; k < 8; k++)
            crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
    crc = ~crc;
    return crc;
}

现在让我们仔细研究一下单个零位在CRC中的应用:

Now let's look carefully at the application of single zero bit to the CRC:

crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;

应用该位时可能采取了两条路径.在最后一个运算中，多项式与CRC异或，或者不是.如果我们想扭转这种情况，我们想知道它的发展方向.

There are two paths that could have been taken when applying the bit. In the last operation, either the polynomial was exclusive-ored with the CRC, or it wasn't. If we want to reverse this, we would like to know which way it went.

我们可以通过查看结果的高位来判断.我们可以看到，如果多项式不是异或的，那么高位必须为0.但是，如果它是异或的呢?在这种情况下，结果的高位是POLY的高位.我们可以看到那个高位是1.所以我们只看结果的高位就可以知道.实际上，对于任何有效的CRC多项式都必须是这种情况，因为对于x ⁰ 项，所有系数都为1. (该项在此反射多项式的最高位.)

We can tell by looking at the high bit of the result. We can see that if the polynomial was not exclusive-ored, then the high bit must be 0. But what if it was exclusive-ored? In that case, the high bit of the result is the high bit of POLY. We can see that that high bit is 1. So we can tell just by looking at the high bit of the result. In fact, this must be the case for any valid CRC polynomial, since all have the coefficient 1 for the x⁰ term. (That term is in the high bit for this reflected polynomial.)

通过检查，我们可以轻松地反转该操作，其中crc进入是应用0位之后的最终CRC，而crc出来的是应用0位之前的CRC:

By inspection we can easily reverse that operation, where here crc going in is the final CRC after applying a 0 bit, and crc coming out is what that CRC was before applying the 0 bit:

crc = crc & 0x80000000 ? ((crc ^ POLY) << 1) + 1 : crc << 1;

这将需要最终的CRC，并在单个0位上反转计算CRC的操作.请注意，在这种情况下，我们必须插入将引起异或的低1位.

That will take a final CRC and reverse the action of computing the CRC over a single 0 bit. Note that we have to insert the low 1 bit that would have caused the exclusive-or, for that case.

我们可以将POLY排除在外而得到:

We can factor out POLY to get:

crc = crc & 0x80000000 ? (crc << 1) ^ ((POLY << 1) + 1) : crc << 1;

这与将多项式(POLY << 1) + 1旋转了多项式(POLY << 1) + 1的未反映的CRC 附加 0位的操作完全相同剩下一位.

That is exactly the same as the operation to append a 0 bit to a non-reflected CRC with the polynomial (POLY << 1) + 1, which is just POLY rotated left one bit.

然后我们可以编写一个函数以从标准CRC-32中删除n个零字节:

We can then write a function to remove n zero bytes from a standard CRC-32:

#define UNPOLY ((POLY << 1) + 1)

uint32_t crc32_remove_zeros(uint32_t crc, size_t n) {
    crc = ~crc;
    while (n--)
        for (int k = 0; k < 8; k++)
            crc = crc & 0x80000000 ? (crc << 1) ^ UNPOLY : crc << 1;
    crc = ~crc;
    return crc;
}

现在我们可以使用与zlib中相同的方法，但是使用非反射CRC，编写一个函数以从O(log( n ))时间.因为我们已经反转了原始运算，所以我们不需要反转任何矩阵.

Now we can use the same approach as used in zlib, but with a non-reflected CRC, to write a function to remove n zeros from a CRC-32 in O(log(n)) time. We do not need to invert any matrices, since we have already inverted the original operation.

其余部分留给读者练习.

The remainder is left as an exercise for the reader.

这篇关于crc32_combine()的矩阵技巧的逆是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！