logo标签列表

在软件中实现SSE 4.2的CRC32C

c++polynomial-mathcrc32
35

我的设计中使用了CRC32C校验和来确保数据没有损坏。我决定使用CRC32C，因为如果运行软件的计算机支持SSE 4.2，我可以同时拥有软件版本和硬件加速版本。

我正在参考英特尔的开发者手册（卷2A），该手册似乎提供了crc32指令背后的算法。然而，我遇到了一些问题。英特尔的开发者指南如下所示：

BIT_REFLECT32: DEST[31-0] = SRC[0-31]
MOD2: Remainder from Polynomial division modulus 2

TEMP1[31-0] <- BIT_REFLECT(SRC[31-0])
TEMP2[31-0] <- BIT_REFLECT(DEST[31-0])
TEMP3[63-0] <- TEMP1[31-0] << 32
TEMP4[63-0] <- TEMP2[31-0] << 32
TEMP5[63-0] <- TEMP3[63-0] XOR TEMP4[63-0]
TEMP6[31-0] <- TEMP5[63-0] MOD2 0x11EDC6F41
DEST[31-0]  <- BIT_REFLECT(TEMP6[31-0])

据我所知，直到以TEMP6开头的那一行，我已经做得都正确，但我认为我可能要么误解了多项式除法，要么实现方式有误。如果我的理解是正确的，1 / 1 mod 2 = 1，0 / 1 mod 2 = 0，并且除以零均未定义。

我不明白的是，使用64位和33位操作数的二进制除法将如何运作。如果SRC为0x00000000，DEST为0xFFFFFFFF，TEMP5 [63-32]将是所有设置位，而TEMP5 [31-0]将是所有未设置位。

如果我要使用TEMP5中的位作为分子，由于多项式11EDC6F41只有33位长（因此将其转换为64位无符号整数会使顶部30位未设置），因此将有30个除以零的部分，因为分母对30位未设置。

然而，如果我要将多项式用作分子，则TEMP5的底部32位未设置，在那里导致除以零，结果中的前30位将为零，因为分子的前30位将为零，因为0 / 1 mod 2 = 0。

我是否误解了这是如何工作的？还是漏掉了一些关键步骤？或者英特尔在其文档中遗漏了一些重要步骤？

我去查阅英特尔开发人员指南，因为他们使用了一个33位多项式，而我想使输出结果相同，但当我使用32位多项式1EDC6F41时（如下所示），输出结果并不相同。

uint32_t poly = 0x1EDC6F41, sres, crcTable[256], data = 0x00000000;

for (n = 0; n < 256; n++) {
    sres = n;
    for (k = 0; k < 8; k++)
        sres = (sres & 1) == 1 ? poly ^ (sres >> 1) : (sres >> 1);
    crcTable[n] = sres;
}
sres = 0xFFFFFFFF;

for (n = 0; n < 4; n++) {
    sres = crcTable[(sres ^ data) & 0xFF] ^ (sres >> 8);
}

上面的代码输出为4138093821，而crc32指令在输入0x00000000时产生2346497208。

如果有地方写得很糟糕或难以理解，对不起，因为现在对我来说已经很晚了。

1
对于那些使用Delphi的人，我已经编写了一些开源代码，如果可用，使用新的crc32硬件指令，并且如果SSE 4.2不可用，则使用快速的x86汇编或纯Pascal代码（使用预计算表）。朴素的滚动版本运行速度为330 MB/s，优化展开的x86汇编在1.7 GB/s处执行，而SSE 4.2硬件则提供惊人的3.7 GB/s速度（在Win32和Win64平台上均可）。 - Arnaud Bouchez
如果您可以合法地阅读LGPL代码，请参见http://code.woboq.org/qt5/qtbase/src/corelib/tools/qhash.cpp.html#95 - peppe
4个回答
84

这里有 CRC-32C 的软件和硬件版本。 软件版本被优化为一次处理八个字节。 硬件版本被优化为在单个核心上有效地并行运行三个 crc32q 指令，因为该指令的吞吐量是一个周期，但延迟是三个周期。

crc32c.c：

/* crc32c.c -- compute CRC-32C using the Intel crc32 instruction
 * Copyright (C) 2013, 2021 Mark Adler
 * Version 1.2  5 Jun 2021  Mark Adler
 */

/*
  This software is provided 'as-is', without any express or implied
  warranty.  In no event will the author be held liable for any damages
  arising from the use of this software.

  Permission is granted to anyone to use this software for any purpose,
  including commercial applications, and to alter it and redistribute it
  freely, subject to the following restrictions:

  1. The origin of this software must not be misrepresented; you must not
     claim that you wrote the original software. If you use this software
     in a product, an acknowledgment in the product documentation would be
     appreciated but is not required.
  2. Altered source versions must be plainly marked as such, and must not be
     misrepresented as being the original software.
  3. This notice may not be removed or altered from any source distribution.

  Mark Adler
  madler@alumni.caltech.edu
 */

/* Version History:
 1.0  10 Feb 2013  First version
 1.1  31 May 2021  Correct register constraints on assembly instructions
                   Include pre-computed tables to avoid use of pthreads
                   Return zero for the CRC when buf is NULL, as initial value
 1.2   5 Jun 2021  Make tables constant
 */

// Use hardware CRC instruction on Intel SSE 4.2 processors.  This computes a
// CRC-32C, *not* the CRC-32 used by Ethernet and zip, gzip, etc.  A software
// version is provided as a fall-back, as well as for speed comparisons.

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

// Tables for CRC word-wise calculation, definitions of LONG and SHORT, and CRC
// shifts by LONG and SHORT bytes.
#include "crc32c.h"

// Table-driven software version as a fall-back.  This is about 15 times slower
// than using the hardware instructions.  This assumes little-endian integers,
// as is the case on Intel processors that the assembler code here is for.
static uint32_t crc32c_sw(uint32_t crc, void const *buf, size_t len) {
    if (buf == NULL)
        return 0;
    unsigned char const *data = buf;
    while (len && ((uintptr_t)data & 7) != 0) {
        crc = (crc >> 8) ^ crc32c_table[0][(crc ^ *data++) & 0xff];
        len--;
    }
    size_t n = len >> 3;
    for (size_t i = 0; i < n; i++) {
        uint64_t word = crc ^ ((uint64_t const *)data)[i];
        crc = crc32c_table[7][word & 0xff] ^
              crc32c_table[6][(word >> 8) & 0xff] ^
              crc32c_table[5][(word >> 16) & 0xff] ^
              crc32c_table[4][(word >> 24) & 0xff] ^
              crc32c_table[3][(word >> 32) & 0xff] ^
              crc32c_table[2][(word >> 40) & 0xff] ^
              crc32c_table[1][(word >> 48) & 0xff] ^
              crc32c_table[0][word >> 56];
    }
    data += n << 3;
    len &= 7;
    while (len) {
        len--;
        crc = (crc >> 8) ^ crc32c_table[0][(crc ^ *data++) & 0xff];
    }
    return crc;
}

// Apply the zeros operator table to crc.
static uint32_t crc32c_shift(uint32_t const zeros[][256], uint32_t crc) {
    return zeros[0][crc & 0xff] ^ zeros[1][(crc >> 8) & 0xff] ^
           zeros[2][(crc >> 16) & 0xff] ^ zeros[3][crc >> 24];
}

// Compute CRC-32C using the Intel hardware instruction. Three crc32q
// instructions are run in parallel on a single core. This gives a
// factor-of-three speedup over a single crc32q instruction, since the
// throughput of that instruction is one cycle, but the latency is three
// cycles.
static uint32_t crc32c_hw(uint32_t crc, void const *buf, size_t len) {
    if (buf == NULL)
        return 0;

    // Pre-process the crc.
    uint64_t crc0 = crc ^ 0xffffffff;

    // Compute the crc for up to seven leading bytes, bringing the data pointer
    // to an eight-byte boundary.
    unsigned char const *next = buf;
    while (len && ((uintptr_t)next & 7) != 0) {
        __asm__("crc32b\t" "(%1), %0"
                : "+r"(crc0)
                : "r"(next), "m"(*next));
        next++;
        len--;
    }

    // Compute the crc on sets of LONG*3 bytes, making use of three ALUs in
    // parallel on a single core.
    while (len >= LONG*3) {
        uint64_t crc1 = 0;
        uint64_t crc2 = 0;
        unsigned char const *end = next + LONG;
        do {
            __asm__("crc32q\t" "(%3), %0\n\t"
                    "crc32q\t" LONGx1 "(%3), %1\n\t"
                    "crc32q\t" LONGx2 "(%3), %2"
                    : "+r"(crc0), "+r"(crc1), "+r"(crc2)
                    : "r"(next), "m"(*next));
            next += 8;
        } while (next < end);
        crc0 = crc32c_shift(crc32c_long, crc0) ^ crc1;
        crc0 = crc32c_shift(crc32c_long, crc0) ^ crc2;
        next += LONG*2;
        len -= LONG*3;
    }

    // Do the same thing, but now on SHORT*3 blocks for the remaining data less
    // than a LONG*3 block.
    while (len >= SHORT*3) {
        uint64_t crc1 = 0;
        uint64_t crc2 = 0;
        unsigned char const *end = next + SHORT;
        do {
            __asm__("crc32q\t" "(%3), %0\n\t"
                    "crc32q\t" SHORTx1 "(%3), %1\n\t"
                    "crc32q\t" SHORTx2 "(%3), %2"
                    : "+r"(crc0), "+r"(crc1), "+r"(crc2)
                    : "r"(next), "m"(*next));
            next += 8;
        } while (next < end);
        crc0 = crc32c_shift(crc32c_short, crc0) ^ crc1;
        crc0 = crc32c_shift(crc32c_short, crc0) ^ crc2;
        next += SHORT*2;
        len -= SHORT*3;
    }

    // Compute the crc on the remaining eight-byte units less than a SHORT*3
    // block.
    unsigned char const *end = next + (len - (len & 7));
    while (next < end) {
        __asm__("crc32q\t" "(%1), %0"
                : "+r"(crc0)
                : "r"(next), "m"(*next));
        next += 8;
    }
    len &= 7;

    // Compute the crc for up to seven trailing bytes.
    while (len) {
        __asm__("crc32b\t" "(%1), %0"
                : "+r"(crc0)
                : "r"(next), "m"(*next));
        next++;
        len--;
    }

    // Return the crc, post-processed.
    return ~(uint32_t)crc0;
}

// Check for SSE 4.2.  SSE 4.2 was first supported in Nehalem processors
// introduced in November, 2008.  This does not check for the existence of the
// cpuid instruction itself, which was introduced on the 486SL in 1992, so this
// will fail on earlier x86 processors.  cpuid works on all Pentium and later
// processors.
#define SSE42(have) \
    do { \
        uint32_t eax, ecx; \
        eax = 1; \
        __asm__("cpuid" \
                : "=c"(ecx) \
                : "a"(eax) \
                : "%ebx", "%edx"); \
        (have) = (ecx >> 20) & 1; \
    } while (0)

// Compute a CRC-32C.  If the crc32 instruction is available, use the hardware
// version.  Otherwise, use the software version.
uint32_t crc32c(uint32_t crc, void const *buf, size_t len) {
    int sse42;
    SSE42(sse42);
    return sse42 ? crc32c_hw(crc, buf, len) : crc32c_sw(crc, buf, len);
}

生成crc32c.h的代码（由于答案中有30,000个字符限制，stackoverflow不允许我发布表格本身）：

// Generate crc32c.h for crc32c.c.

#include <stdio.h>
#include <stdint.h>

#define LONG 8192
#define SHORT 256

// Print a 2-D table of four-byte constants in hex.
static void print_table(uint32_t *tab, size_t rows, size_t cols, char *name) {
    printf("static uint32_t const %s[][%zu] = {\n", name, cols);
    size_t end = rows * cols;
    size_t k = 0;
    for (;;) {
        fputs("   {", stdout);
        size_t n = 0, j = 0;
        for (;;) {
            printf("0x%08x", tab[k + n]);
            if (++n == cols)
                break;
            putchar(',');
            if (++j == 6) {
                fputs("\n   ", stdout);
                j = 0;
            }
            putchar(' ');
        }
        k += cols;
        if (k == end)
            break;
        puts("},");
    }
    puts("}\n};");
}

/* CRC-32C (iSCSI) polynomial in reversed bit order. */
#define POLY 0x82f63b78

static void crc32c_word_table(void) {
    uint32_t table[8][256];

    // Generate byte-wise table.
    for (unsigned n = 0; n < 256; n++) {
        uint32_t crc = ~n;
        for (unsigned k = 0; k < 8; k++)
            crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        table[0][n] = ~crc;
    }

    // Use byte-wise table to generate word-wise table.
    for (unsigned n = 0; n < 256; n++) {
        uint32_t crc = ~table[0][n];
        for (unsigned k = 1; k < 8; k++) {
            crc = table[0][crc & 0xff] ^ (crc >> 8);
            table[k][n] = ~crc;
        }
    }

    // Print table.
    print_table(table[0], 8, 256, "crc32c_table");
}

// Return a(x) multiplied by b(x) modulo p(x), where p(x) is the CRC
// polynomial. For speed, this requires that a not be zero.
static uint32_t multmodp(uint32_t a, uint32_t b) {
    uint32_t prod = 0;
    for (;;) {
        if (a & 0x80000000) {
            prod ^= b;
            if ((a & 0x7fffffff) == 0)
                break;
        }
        a <<= 1;
        b = b & 1 ? (b >> 1) ^ POLY : b >> 1;
    }
    return prod;
}

/* Take a length and build four lookup tables for applying the zeros operator
   for that length, byte-by-byte, on the operand. */
static void crc32c_zero_table(size_t len, char *name) {
    // Generate operator for len zeros.
    uint32_t op = 0x80000000;               // 1 (x^0)
    uint32_t sq = op >> 4;                  // x^4
    while (len) {
        sq = multmodp(sq, sq);              // x^2^(k+3), k == len bit position
        if (len & 1)
            op = multmodp(sq, op);
        len >>= 1;
    }

    // Generate table to update each byte of a CRC using op.
    uint32_t table[4][256];
    for (unsigned n = 0; n < 256; n++) {
        table[0][n] = multmodp(op, n);
        table[1][n] = multmodp(op, n << 8);
        table[2][n] = multmodp(op, n << 16);
        table[3][n] = multmodp(op, n << 24);
    }

    // Print the table to stdout.
    print_table(table[0], 4, 256, name);
}

int main(void) {
    puts(
"// crc32c.h\n"
"// Tables and constants for crc32c.c software and hardware calculations.\n"
"\n"
"// Table for a 64-bits-at-a-time software CRC-32C calculation. This table\n"
"// has built into it the pre and post bit inversion of the CRC."
    );
    crc32c_word_table();
    puts(
"\n// Block sizes for three-way parallel crc computation.  LONG and SHORT\n"
"// must both be powers of two.  The associated string constants must be set\n"
"// accordingly, for use in constructing the assembler instructions."
        );
    printf("#define LONG %d\n", LONG);
    printf("#define LONGx1 \"%d\"\n", LONG);
    printf("#define LONGx2 \"%d\"\n", 2 * LONG);
    printf("#define SHORT %d\n", SHORT);
    printf("#define SHORTx1 \"%d\"\n", SHORT);
    printf("#define SHORTx2 \"%d\"\n", 2 * SHORT);
    puts(
"\n// Table to shift a CRC-32C by LONG bytes."
    );
    crc32c_zero_table(8192, "crc32c_long");
    puts(
"\n// Table to shift a CRC-32C by SHORT bytes."
    );
    crc32c_zero_table(256, "crc32c_short");
    return 0;
}
8
这段话是针对GNU编译器（gcc）编写的，它使用AT＆T语法来进行汇编指令，而不是英特尔语法。 AT＆T语法更清楚地表明生成了哪个指令，因为它不依赖于参数类型（例如dword ptr等）。 您的汇编程序可能使用英特尔语法，其中“crc32”“指令”实际上可以生成六种不同的指令之一。 必须由汇编器以及试图读取代码的人根据参数的性质来确定使用哪一个指令。 - Mark Adler
6
并行处理3个缓冲区的原因是CRC32C指令具有流水线功能，其延迟为3个周期，吞吐量为1个周期 - 只要结果在3个周期内不用作另一个CRC32C指令的输入，就可以每个时钟周期获取一个CRC32C指令。只有一个ALU能够执行CRC32C - 指令通过端口1分派到该ALU，该ALU执行“复杂/缓慢”的整数指令。其他ALU无法处理CRC32C。http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf - amdn
2
谢谢！我误解了为什么并行执行四个CRC指令没有帮助。我会修正注释。 - Mark Adler
2
我已经将代码封装到了一个Windows库中，并加入了.NET封装程序和NuGet包。我还将软件回退速度提高了50%。 - Robert Važan
1
不错的答案，但请注意，C++中使用constexpr初始化查找表可能比这个C版本更快，因为由于pthread_once_t的存在，您可能会在每次调用时支付一些成本。 - NoSenseEtAl
显示剩余29条评论
17
马克·阿德勒的答案正确而完整，但那些寻求快速简便地在他们的应用程序中集成CRC-32C的人可能会发现难以适应代码，特别是如果他们使用的是Windows和.NET。
我创建了一个实现CRC-32C的库，使用可用的硬件或软件方法，它可作为C++和.NET的NuGet包提供。当然，它是开源的。
除了打包以上的马克·阿德勒的代码外，我还找到了一种简单的方法来提高软件回退的吞吐量50%。在我的计算机上，该库现在在软件中实现了2 GB/s，在硬件上实现了超过20 GB/s。对于那些好奇的人，这里是优化后的软件实现：
static uint32_t append_table(uint32_t crci, buffer input, size_t length)
{
    buffer next = input;
#ifdef _M_X64
    uint64_t crc;
#else
    uint32_t crc;
#endif

    crc = crci ^ 0xffffffff;
#ifdef _M_X64
    while (length && ((uintptr_t)next & 7) != 0)
    {
        crc = table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
        --length;
    }
    while (length >= 16)
    {
        crc ^= *(uint64_t *)next;
        uint64_t high = *(uint64_t *)(next + 8);
        crc = table[15][crc & 0xff]
            ^ table[14][(crc >> 8) & 0xff]
            ^ table[13][(crc >> 16) & 0xff]
            ^ table[12][(crc >> 24) & 0xff]
            ^ table[11][(crc >> 32) & 0xff]
            ^ table[10][(crc >> 40) & 0xff]
            ^ table[9][(crc >> 48) & 0xff]
            ^ table[8][crc >> 56]
            ^ table[7][high & 0xff]
            ^ table[6][(high >> 8) & 0xff]
            ^ table[5][(high >> 16) & 0xff]
            ^ table[4][(high >> 24) & 0xff]
            ^ table[3][(high >> 32) & 0xff]
            ^ table[2][(high >> 40) & 0xff]
            ^ table[1][(high >> 48) & 0xff]
            ^ table[0][high >> 56];
        next += 16;
        length -= 16;
    }
#else
    while (length && ((uintptr_t)next & 3) != 0)
    {
        crc = table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
        --length;
    }
    while (length >= 12)
    {
        crc ^= *(uint32_t *)next;
        uint32_t high = *(uint32_t *)(next + 4);
        uint32_t high2 = *(uint32_t *)(next + 8);
        crc = table[11][crc & 0xff]
            ^ table[10][(crc >> 8) & 0xff]
            ^ table[9][(crc >> 16) & 0xff]
            ^ table[8][crc >> 24]
            ^ table[7][high & 0xff]
            ^ table[6][(high >> 8) & 0xff]
            ^ table[5][(high >> 16) & 0xff]
            ^ table[4][high >> 24]
            ^ table[3][high2 & 0xff]
            ^ table[2][(high2 >> 8) & 0xff]
            ^ table[1][(high2 >> 16) & 0xff]
            ^ table[0][high2 >> 24];
        next += 12;
        length -= 12;
    }
#endif
    while (length)
    {
        crc = table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
        --length;
    }
    return (uint32_t)crc ^ 0xffffffff;
}

正如您所看到的，它只是一次压缩更大的块。它需要更大的查找表，但它仍然很友好地缓存。该表以相同的方式生成，只是行数更多。

我探索的一件额外的事情是使用PCLMULQDQ指令在AMD处理器上获得硬件加速。我已经成功地将Intel针对zlib的CRC补丁（也可以在GitHub上获取）移植到CRC-32C多项式除了神奇常数0x9db42487。如果有人能解密它，请告诉我。在supersaw7在Reddit上提供的出色解释之后，我还移植了难以捉摸的0x9db42487常数，现在我只需要找时间来完善和测试它。

我修复了补丁的链接并添加了一些额外的链接。Robert，你在这个问题上有进展吗？ - Janus Troelsen
似乎Cloudflare的带有PCLMULQDQ支持的zlib没有使用该常量...也许这对您有用？ - Janus Troelsen
PCLMULQDQ不再是一个谜。请查看更新的答案。 - Robert Važan
@RobertVažan - 可能有点晚了，但我已经有使用 pclmulqdq 的工作版本，并将其转换为适用于 Visual Studio 汇编程序（ML64.EXE），用于左移和右移 CRCs 以及两个多项式。在我的系统上，Intel 3770K 3.5 GHz，速度约为每秒 3.3 GB。 - rcgldr
@rcgldr 如果您能将其发布为库，我将很高兴链接到它。我目前主要进行非Windows开发，我的Windows项目并没有得到太多关注。您还可以采用我的crc32c项目并在其中添加您的代码。如果您有兴趣，请给我发送电子邮件。 - Robert Važan
显示剩余2条评论
15
首先，英特尔的 CRC32 指令用于计算 CRC-32C（使用不同的多项式而不是常规 CRC32。请查看Wikipedia CRC32条目）。
要使用英特尔的硬件加速进行CRC32C，可以使用gcc：
  1. 通过asm语句在C代码中内联汇编语言
  2. 使用内部函数 _mm_crc32_u8、_mm_crc32_u16、_mm_crc32_u32 或 _mm_crc32_u64。在Intel编译器icc中，可以查看 Intel Intrinsics Guide 来了解它们的描述，但gcc也实现了它们。
以下是使用 __mm_crc32_u8 的方法，它一次处理一个字节。如果使用 __mm_crc32_u64，会进一步提高性能，因为它可以一次处理8个字节。
uint32_t sse42_crc32(const uint8_t *bytes, size_t len)
{
  uint32_t hash = 0;
  size_t i = 0;
  for (i=0;i<len;i++) {
    hash = _mm_crc32_u8(hash, bytes[i]);
  }

  return hash;
}

编译此代码需要在 CFLAGS 中添加 -msse4.2。例如：gcc -g -msse4.2 test.c，否则会报错：undefined reference to _mm_crc32_u8。

如果希望在可执行文件所在的平台上不支持该指令时返回到普通 C 实现，可以使用 GCC 的 ifunc 属性。例如：

uint32_t sse42_crc32(const uint8_t *bytes, size_t len)
{
  /* use _mm_crc32_u* here */
}

uint32_t default_crc32(const uint8_t *bytes, size_t len)
{
  /* pure C implementation */
}

/* this will be called at load time to decide which function really use */
/* sse42_crc32 if SSE 4.2 is supported */
/* default_crc32 if not */
static void * resolve_crc32(void) {
  __builtin_cpu_init();
  if (__builtin_cpu_supports("sse4.2")) return sse42_crc32;

  return default_crc32;
}

/* crc32() implementation will be resolved at load time to either */
/* sse42_crc32() or default_crc32() */
uint32_t crc32(const uint8_t *bytes, size_t len) __attribute__ ((ifunc ("resolve_crc32")));
如果我正在处理一个1MB的块，并使用上述方法，是否有一种方法可以获取校验和？ - ajax_velu
你可以创建一个版本的这个函数，其中初始哈希值作为参数传递。这将允许您逐块处理。 - RubenLaguna
9
我在这里比较了各种算法：https://github.com/htot/crc32c 最快的算法来自英特尔的crc_iscsi_v_pcl.asm汇编代码（在Linux内核中以修改后的形式可用），并使用一个C包装器（crcintelasm.cc）包含在此项目中。
为了能够在32位平台上运行此代码，首先将其移植到C语言（crc32intelc），需要一小部分内联汇编。代码的某些部分取决于位数，crc32q在32位上不可用，movq也是如此，这些被放在宏中（crc32intel.h），并提供32位平台的替代代码。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接