c++ SSE 4.2的CRC32C软件实现

ecbunoof  于 2023-06-25  发布在  其他
关注(0)|答案(4)|浏览(192)

因此，我有一个设计，其中纳入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中的位作为分子，则会有30次除以0，因为多项式11EDC6F41只有33位长（因此将其转换为64位无符号整数会留下前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。
对不起，如果这是写得不好或无法理解的地方，这是相当晚了我。

c++

4条答案

按热度按时间
ma8fv8wu

ma8fv8wu1#

这里是CRC-32 C的软件和硬件版本。该软件版本经过优化，可一次处理8个字节。硬件版本经过优化，可在单个内核上有效并行运行三条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的代码（stackoverflow不允许我发布表格本身，因为答案中有30，000个字符的限制）：

// 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;
}
赞(0）分享  回复(0）举报  2023-06-25
vuv7lop3

vuv7lop32#

Mark Adler的答案是正确和完整的，但是那些寻求快速和简单的方法来将CRC-32 C集成到他们的应用程序中的人可能会发现适应代码有点困难，特别是如果他们使用Windows和. NET。
根据可用的硬件，我使用硬件或软件方法创建了library that implements CRC-32C。它作为C++和. NET的NuGet包提供。当然是开源的。
除了打包上面的MarkAdler的代码之外，我还发现了一种简单的方法，可以将软件回退的吞吐量提高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's CRC patch for zlib（也就是available on GitHub）移植到CRC-32 C多项式，除了神奇常量0x 9db 42487。如果有人能破译这个，请告诉我。在supersaw7's excellent explanation on reddit之后，我还移植了难以捉摸的0x 9db 42487常量，我只需要找一些时间来完善和测试它。

赞(0）分享  回复(0）举报  2023-06-25
wdebmtf2

wdebmtf23#

首先，英特尔的CRC32指令用于计算CRC-32C（即使用与常规CRC32不同的多项式）。查看Wikipedia CRC32条目）
要使用英特尔的CRC32C硬件加速gcc，您可以：
1.通过asm语句在C代码中使用内联汇编语言
1.使用内部函数_mm_crc32_u8、_mm_crc32_u16、_mm_crc32_u32或_mm_crc32_u64。参见Intel Intrinsics Guide以了解Intel的编译器icc的描述，但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")));
赞(0）分享  回复(0）举报  2023-06-25
yx2lnoni

yx2lnoni4#

我在这里比较各种算法：https://github.com/htot/crc32c
最快的算法取自Intels crc_iscsi_v_pcl.asm汇编代码（可在Linux内核中以修改的形式获得），并使用本项目中包含的C Package 器（crcintelasm.cc）。
为了能够在32位平台上运行这些代码，首先它已经被移植到C（crc32intelc），在可能的情况下，需要少量的内联汇编。代码的某些部分取决于位数，crc32q在32位上不可用，movq也不可用，这些都放在宏的（crc32intel.h）中，具有32位平台的替代代码。

赞(0）分享  回复(0）举报  2023-06-25
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com