零填充的 CRC32 计算 Buffer/File

Question

如果我想计算大量连续零字节的 CRC32 值，在给定运行个零字节的长度的情况下，是否可以使用常数时间公式？例如，如果我知道我有 1000 个字节全部用零填充，有没有办法避免 1000 次迭代的循环（只是一个例子，为了这个问题，零的实际数量是无限的）？

Answer 1

使用 table 查找后跟乘法可以将时间复杂度降低到 O(1)。解释和示例代码显示在本答案的第三部分。

如果 1000 是常数，则预先计算 table 32 个值，每个值代表可以使用 CRC 的 8000 次方mod poly 的每一位。一组矩阵（每个 CRC 字节一组）可用于一次处理一个字节。两种方法都是恒定时间（固定循环次数）O(1).

如上所述，如果 1000 不是常量，则可以使用平方求幂，这将是 O(log2(n)) 时间复杂度，或者一些预先计算的 tables 的组合常数个零位，例如 256，然后可以使用平方求幂，这样最后一步将是 O(log2(n%256)).

一般优化：对于具有零和非零元素的普通数据，在带有 pclmulqdq（使用 xmm 寄存器）的 modern X86 上，可以实现快速 crc32（或 crc16），尽管它是接近 500 行汇编代码。英特尔文档：crc using pclmulqdq. Example source code for github fast crc16。对于 32 位 CRC，需要一组不同的常量。如果有兴趣，我将源代码转换为使用 Visual Studio ML64.EXE（64 位 MASM），并为左移和右移 32 位 CRC 创建了示例，每个都有两组常量用于两个最流行的 CRC 32 位多项式（左移多项式：crc32:0x104C11DB7 和 crc32c：0x11EDC6F41，右移多项式的位反转）。

使用基于软件的无进位乘法快速调整 CRC 的示例代码modulo CRC 多项式。这比使用 32 x 32 矩阵乘法要快得多。为非零数据计算 CRC：crf = GenCrc(msg, ...)。为 n 个零字节计算调整常数：pmc = pow(2^(8*n))%poly（通过重复平方使用求幂）。然后针对零字节调整 CRC：crf = (crf*pmc)%poly.

请注意，对于 i = 1 到 n，通过生成 table 的 pow(2^(8*i))%poly 常数，时间复杂度可以降低到 O(1)。然后计算是table查找和固定迭代（32个循环）乘以% poly.

#include <stdio.h>
#include <stdlib.h>

typedef unsigned char       uint8_t;
typedef unsigned int       uint32_t;

static uint32_t crctbl[256];

void GenTbl(void)                       /* generate crc table */
{
uint32_t crc;
uint32_t c;
uint32_t i;
    for(c = 0; c < 0x100; c++){
        crc = c<<24;
        for(i = 0; i < 8; i++)
            crc = (crc<<1)^((0-(crc>>31))&0x04c11db7);
        crctbl[c] = crc;
    }
}

uint32_t GenCrc(uint8_t * bfr, size_t size) /* generate crc */
{
uint32_t crc = 0u;
    while(size--)
        crc = (crc<<8)^crctbl[(crc>>24)^*bfr++];
    return(crc);
}

/* carryless multiply modulo crc */
uint32_t MpyModCrc(uint32_t a, uint32_t b) /* (a*b)%crc */
{
uint32_t pd = 0;
uint32_t i;
    for(i = 0; i < 32; i++){
        pd = (pd<<1)^((0-(pd>>31))&0x04c11db7u);
        pd ^= (0-(b>>31))&a;
        b <<= 1;
    }
    return pd;
}

/* exponentiate by repeated squaring modulo crc */
uint32_t PowModCrc(uint32_t p)          /* pow(2,p)%crc */
{
uint32_t prd = 0x1u;                    /* current product */
uint32_t sqr = 0x2u;                    /* current square */
    while(p){
        if(p&1)
            prd = MpyModCrc(prd, sqr);
        sqr = MpyModCrc(sqr, sqr);
        p >>= 1;
    }
    return prd;
}

/* # data bytes */
#define DAT  ( 32)
/* # zero bytes */
#define PAD  (992)
/* DATA+PAD */
#define CNT (1024)

int main()
{
uint32_t pmc;
uint32_t crc;
uint32_t crf;
uint32_t i;
uint8_t *msg = malloc(CNT);

    for(i = 0; i < DAT; i++)           /* generate msg */
        msg[i] = (uint8_t)rand();
    for( ; i < CNT; i++)
        msg[i] = 0;
    GenTbl();                           /* generate crc table */
    crc = GenCrc(msg, CNT);             /* generate crc normally */
    crf = GenCrc(msg, DAT);             /* generate crc for data */
    pmc = PowModCrc(PAD*8);             /* pmc = pow(2,PAD*8)%crc */
    crf = MpyModCrc(crf, pmc);          /* crf = (crf*pmc)%crc */
    printf("%08x %08x\n", crc, crf);    /* crf == crc */
    free(msg);
    return 0;
}

Answer 2

您可以计算应用 n 零的结果，而不是在 O(1) 时间内，而是在 O(log n) 时间内.这是在 zlib 的 crc32_combine() 中完成的。构造一个二进制矩阵，表示将单个零位应用于 CRC 的操作。 32x32 矩阵将 32 位 CRC 与 GF(2) 相乘，其中加法由异或 (^) 代替，乘法由与 (&) 逐位代替。

然后可以对该矩阵求平方以获得两个零的运算符。将其平方以获得四个零的运算符。第三个是平方以获得八个零的运算符。依此类推。

现在可以根据要计算其 CRC 的 n 个零位中的一位将这组运算符应用于 CRC。

您可以为任意数量的零位预先计算结果矩阵运算符，如果您碰巧知道您将经常应用那么多的零。那么它只是一个矩阵乘以一个向量，实际上是O(1)。

您不需要使用此处另一个答案中建议的 pclmulqdq 指令，但如果有它会更快一些。它不会改变操作的 O()。

Answer 3

CRC32 基于 GF(2)[X] 模多项式的乘法，它是乘法的。棘手的部分是将非乘法与乘法分开。

首先定义一个具有以下结构的稀疏文件（在 Go 中）：

type SparseFile struct {
    FileBytes []SparseByte
    Size      uint64
}
type SparseByte struct {
    Position uint64
    Value    byte
}

你的情况是 SparseFile{[]FileByte{}, 1000}

那么函数就是：

func IEEESparse (file SparseFile) uint32 {
    position2Index := map[uint64]int{}
    for i , v := range(file.FileBytes) {
        file.FileBytes[i].Value = bits.Reverse8(v.Value)
        position2Index[v.Position] = i
    }
    for i := 0; i < 4; i++ {
        index, ok := position2Index[uint64(i)]
        if !ok {
            file.FileBytes = append(file.FileBytes, SparseByte{Position: uint64(i), Value: 0xFF})
        } else {
            file.FileBytes[index].Value ^= 0xFF
        }
    }

    // Add padding
    file.Size += 4
    newReminder := bits.Reverse32(reminderIEEESparse(file))

    return newReminder ^ 0xFFFFFFFF
}

所以请注意：

以相反的顺序（每个字节）对位执行除法。
前四个字节与 0xFF 异或。
文件用 4 个字节填充。
提醒再次反转。
提醒再次异或。

内部函数reminderIEEESparse是真正的提醒，很容易在O(log n)中实现它，其中n是文件的大小。

您可以找到完整的实现 here。

零填充的 CRC32 计算 Buffer/File

CRC32 Calculation for Zero Filled Buffer/File

algorithm

crc

crc32