C ulong数组运算CRC32

Question

我对 C 语言很生疏，我需要理解另一个开发人员基于 CRC32 编写的代码。我有一个 ulong 数组

static const ulong crc32_table[256] =
{
      0x00000000ul, 0x04c11db7ul, 0x09823b6eul, 0x0d4326d9ul,
      0x130476dcul, 0x17c56b6bul, 0x1a864db2ul, 0x1e475005ul,
      0x2608edb8ul, 0x22c9f00ful, 0x2f8ad6d6ul, 0x2b4bcb61ul,
      0x350c9b64ul, 0x31cd86d3ul, 0x3c8ea00aul, 0x384fbdbdul,
      ...
};

这个数组然后用于加密数据，这样：

void CRC32(const byte *buf, uint len, const byte init[4], byte crc[4]) {
    memcpy(crc, init, 4);
    while (len--) {
        const byte * tmp = (const byte *)(crc32_table + (crc[3] ^ *buf));
        crc[3] = crc[2] ^ tmp[3];
        crc[2] = crc[1] ^ tmp[2];
        crc[1] = crc[0] ^ tmp[1];
        crc[0] = tmp[0];
        ++buf;
    }
}

我不明白的是：

const byte * tmp = (const byte *)(crc32_table + (crc[3] ^ *buf));

似乎整个数组都被另外使用并转换为字节（实际上是 uint），但我没有使用对这种操作。

有人可以帮助我吗？

我需要用 C# 编写与 CRC32 函数等效的函数这行得通吗：

            uint[] crc = sharedkey;
            uint[] buff = new uint[] { 0x4fu, 0xaeu, 0x07u, 0x0bu, 0x68u, 0x56u, 0x34u, 0x12u };

            for(int i=0; i < len; i++)
            {
                byte[] tmp = BitConverter.GetBytes(crc32_table[(int)(crc[3] ^ buff[i])]);            

                crc[3] = crc[2] ^ tmp[3];
                crc[2] = crc[1] ^ tmp[2];
                crc[1] = crc[0] ^ tmp[1];
                crc[0] = tmp[0];
            }

Answer 1

让我们剖析整个函数。函数声明如下：

void CRC32(const byte *buf, uint len, const byte init[4], byte crc[4])

const byte *buf - 正在为其计算 CRC 的输入缓冲区

uint len - 要计算的CRC长度

const byte init[4] - CRC

的初始化向量

byte crc[4] - CRC计算的输出/结果

我们首先看到crc被初始化为memcpy(crc, init, 4);中的初始化向量，然后我们有一个循环迭代len次。在此循环结束时，buf 指针增加 ++buf。

下面是你理解有困难的部分。

buf 的每个字节都与 crc[3] 进行异或运算，其结果用作 crc32_table 的偏移量。结果值存储在 tmp 中，然后用于加扰 crc 的四个字节。这项工作背后的关键因素涉及 crc32_table 有 256 个条目，并且一个字节有 256 个可能的值（这是您试图理解的操作的结果）。因此偏移索引始终有效。

剩下的操作只是进一步打乱crc的异或运算。

更新

尽管我已经剖析了该函数，但主要的混淆涉及一个称为指针算术的概念。在C语言中，无索引数组（如crc32_table）的值是指向存储连续类型数据的内存位置的指针，基于数组类型和长度。例如，

假设我们在内存位置 0x400000.

有以下数组 ulong crc32_table[256]

那么crc32_table的值为0x400000.

此外，&crc32_table[0] 也是 0x400000（这转换为 crc32_table 数组 中第一个条目的地址）。

但是，&crc32_table[1] 是 0x400008（如果 sizeof(ulong) 在您的系统上是 8 个字节）

这是有趣的部分。

crc32_table + 1 也是 0x400008，（与 &crc32_table[1] 相同）。

这称为指针运算，它与您提供的 CRC 代码中使用的概念相同。该代码只是将偏移量 0-255 计算到大小为 256 的数组中，因此每个可能的偏移量都是有效的并转换为适当的数组索引。

Answer 2

这里，

const byte * tmp = (const byte *)(crc32_table + (crc[3] ^ *buf));

与 buf 指向输入的下一个字节，这会将下一个输入字节与当前 CRC 值的高字节进行异或，并在 table 中查找。或者更确切地说，它在 table 中查找该元素的地址，并将其转换为 const byte *，以便稍后可以读取字节。（crc32_table + (foo) 等同于 &crc32_table[foo]。）

然后，这个：

crc[3] = crc[2] ^ tmp[3];
crc[2] = crc[1] ^ tmp[2];
crc[1] = crc[0] ^ tmp[1];
crc[0] = tmp[0];

将 CRC 的值移动 8 位（注意索引），并对从 table 中选取的值进行异或运算。这里，tmp 是一个指向字节的指针（可能是 unsigned char *），然后它指向 table 中的一个值的第一个字节。通过 tmp[0] 到 tmp[3] 的访问然后分别读取该字节和值的后续字节。如果 ulong 是 unsigned long，它至少是 32 位或四个字节，因此访问不会转到以下值。不过，需要知道字节顺序是正确的才能正常工作。

我会使用 uint32_ts 而不是 char 数组来做到这一点，但无论如何。大概是这样的，也就是虽然我没有测试，但估计是错误的：

uint32_t tmp, crc = init;
while (len--) { 
    tmp = crc32_table(((crc >> 24) & 0xff) ^ *buf++);
    crc = (crc << 8) ^ tmp; 
}

使用预先计算的 table 是计算 CRC 的优化。如果您查看定义，您通常会将它们视为电路，其中一位从寄存器的一端移出，用于可能翻转寄存器中的某些位，并且输入位同时移入时间。 table 查找一次只处理这 8 位； table 中的值是当这 8 位被移出时在寄存器中翻转的净位。

Answer 3

我将此问题标记为已回答，因为这里有足够的信息来解决我的问题

C ulong数组运算CRC32

C ulong array operation CRC32

arrays

c

crc

operation

crc32