0

代码（用C编写）：

unsigned long chksum_crc32 (unsigned char *block, unsigned int length)
{
   register unsigned long crc;
   unsigned long i;

   crc = 0xFFFFFFFF;
   for (i = 0; i < length; i++)
   {
      crc = ((crc >> 8) & 0x00FFFFFF) ^ crc_tab[(crc ^ *block++) & 0xFF];
   }
   return (crc ^ 0xFFFFFFFF);
}


/* chksum_crc32gentab() --      to a global crc_tab[256], this one will
 *              calculate the crcTable for crc32-checksums.
 *              it is generated to the polynom [..]
 */

void chksum_crc32gentab ()
{
   unsigned long crc, poly;
   int i, j;

   poly = 0xEDB88320L;
   for (i = 0; i < 256; i++)
   {
      crc = i;
      for (j = 8; j > 0; j--)
      {
         if (crc & 1)
         {
            crc = (crc >> 1) ^ poly;
         }
         else
         {
            crc >>= 1;
         }
      }
      crc_tab[i] = crc;
   }
}

对于初学者; 我知道 CRC 是如何工作的，首先使用指定的多项式计算除数，然后将此 FCS（帧校验序列）附加到数据集并发送到最终用户系统。传输完成后，使用用于计算 FCS 的相同多项式检查 FCS，如果具有该除数的数据的余数为零，则您知道数据是正确的。

我不明白这两个功能的实现。据我所知，函数 chksum_crc32gentab() 生成校验和可以采用 32 位 CRC 多项式的所有可能的十六进制值。我不明白的一件事是poly = 0xEDB88320L; 等价于多项式。我也不明白这个函数底部的逻辑。例如，条件if (crc & 1)，这是否意味着对于 crc 中为 1 的每一位，计算，否则右移一位？

我也不明白chksum_crc32(unsigned char *block, unsigned int length); . 这个函数是否只接收一串字节并将它们转换为使用表计算的正确 crc 值？我想我对它在 for 循环中使用的逻辑感到困惑。

如果有人理解这段代码，解释会很好；这确实适用于 .net 类的 crc32 转换，如何转换数据然后由这些函数使用的示例如下：（C# 源代码）

      MemoryStream ms = new MemoryStream(System.Text.Encoding.Default.GetBytes(input));

            foreach (byte b in crc32.ComputeHash(ms))
                hash += b.ToString("x2").ToLower();

这是 C 代码的原始站点和项目。http://www.codeproject.com/Articles/35134/How-to-calculate-CRC-in-C

任何解释都会有所帮助

4

2 回答 2

3

或者只是谷歌它......第二次点击是：http ://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/libkern/crc32.c

从 C# 向后移植它是很难做到的，这些算法中的大多数已经在 C 中了。

于 2012-07-30T15:49:10.870 回答
2

在 CRC 计算中，二进制多项式是x^n系数为 0 或 1 的总和，它们被简单地表示为二进制字，其中 0 或 1 的位置指示它的哪个幂x是系数。

0xEDB88320L将 CRC32 多项式的系数表示为 1，其中有一个x^n项（项除外x^32，它被省略了）。CRC32多项式（为什么stackoverflow没有像math.stackexchange这样的TeX方程——我不能在这里写出像样的方程！叹息，抱歉咆哮......）是：

x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1

由于该 CRC 是如何根据位排序定义的，因此最低系数位于最高位中。所以E上面十六进制常量中的第一个1110表示（按位从左到右的顺序）1 + x + x^2，。

您可以在zlibcrc32.c的源文件中找到该结构，此处显示了其中的一个片段：

static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};

    /* make exclusive-or pattern from polynomial (0xedb88320UL) */
    poly = 0;
    for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++)
        poly |= (z_crc_t)1 << (31 - p[n]);

    /* generate a crc for every 8-bit value */
    for (n = 0; n < 256; n++) {
        c = (z_crc_t)n;
        for (k = 0; k < 8; k++)
            c = c & 1 ? poly ^ (c >> 1) : c >> 1;
        crc_table[0][n] = c;
    }

if (crc & 1)或以上在移开之前在每一步查看c & 1 ?CRC 的低位。这实际上是多项式减法运算的进位位，因此如果它是 1，则从 CRC 中的下移多项式（乘以x）中减去（异或）多项式。无论低位是否为 1，CRC 都会下移。

您显示的chksum_crc32()函数确实计算了提供的数据块上的 CRC。它是对字节串进行 CRC 计算的标准基于表的方法，它通过数据字节和 CRC 的低字节的异或来索引表。这与一次移入一个位并将多项式应用于 1 位的作用相同，但它是一步完成的，而不是八位。CRC 有效地乘以x^8(the >> 8)，并且根据索引值在不同的移位位置处与多项式进行异或 0 到 8 次的异或运算。这只是使用预先计算的表格的速度技巧。

您可以找到 zlib 中使用的更极端的速度技巧，这些技巧crc32.c使用更大的表并一次处理更多数据。

于 2012-07-30T19:12:59.120 回答