Python和C的crc32相同吗

Question

我需要一个脚本，可以计算crc32，并且在Python和C中输出的结果是一样的。

我现在用的是zlib.crc32，但在C语言中没有这样的库，所以我们根据维基百科自己写了一个。但是返回的值不一样。

这是我们在C语言中写的脚本代码（从维基百科复制的，基于RFC）：

unsigned int crc32( unsigned char *message, unsigned int n )
{
   //int i, crc;
   unsigned int crc;
   unsigned int i;
   unsigned int byte, c;
   const unsigned int g0 = 0xEDB88320,    g1 = g0>>1,
      g2 = g0>>2, g3 = g0>>3, g4 = g0>>4, g5 = g0>>5,
      g6 = (g0>>6)^g0, g7 = ((g0>>6)^g0)>>1;

   i = 0;
   crc = 0xFFFFFFFF;
   //while ((byte = message[i]) != 0)
   while( i != n)
   {
               byte = message[i];                   // Get next byte.
               // byte = FrmReadByte( i );  // Get next byte.

               crc = crc ^ byte;
               c = ((crc<<31>>31) & g7) ^ ((crc<<30>>31) & g6) ^
               ((crc<<29>>31) & g5) ^ ((crc<<28>>31) & g4) ^
               ((crc<<27>>31) & g3) ^ ((crc<<26>>31) & g2) ^
               ((crc<<25>>31) & g1) ^ ((crc<<24>>31) & g0);

               crc = ((unsigned)crc >> 8) ^ c;
               i = i + 1;
   }
   return ~crc;
}

编辑：

我们只有4KB的内存，程序本身不在这里。crc32脚本占用1KB内存可能太多了，放不下。感谢你提到C语言中也有ZLIB库。

Answer 1

你需要一个C语言的实现，这个实现不使用查找表（大多数实现都是用查找表的），而且要有一个和Python相匹配的版本。你可以使用ZIP中的CRC32，正如Mark Ransom所建议的（binascii.crc32）。

/* Calculating ZIP CRC-32 in 'C'
   =============================
   Reference model for the translated code */

#define poly 0xEDB88320
/* Some compilers need
   #define poly 0xEDB88320uL
 */

/* On entry, addr=>start of data
             num = length of data
             crc = incoming CRC     */
int crc32(char *addr, int num, int crc)
{
int i;

for (; num>0; num--)              /* Step through bytes in memory */
  {
  crc = crc ^ *addr++;            /* Fetch byte from memory, XOR into CRC */
  for (i=0; i<8; i++)             /* Prepare to rotate 8 bits */
  {
    if (crc & 1)                  /* b0 is set... */
      crc = (crc >> 1) ^ poly;    /* rotate and XOR with ZIP polynomic */
    else                          /* b0 is clear... */
      crc >>= 1;                  /* just rotate */
  /* Some compilers need:
    crc &= 0xFFFFFFFF;
   */
    }                             /* Loop for 8 bits */
  }                               /* Loop until num=0 */
  return(crc);                    /* Return updated CRC */
}

补充说明：因为有好几个人指出上面的代码存在问题，下面的代码与维基百科的版本相符（见http://ideone.com/pWLVSo）以及Python的版本（http://ideone.com/SvYuyE - 1277644989==0x4c2750bd）。这段代码来自这个页面，那里还有其他实现和我复制的基本版本的可能改进。

const uint32_t Polynomial = 0xEDB88320;

uint32_t crc32_bitwise(const void* data, size_t length, uint32_t previousCrc32 = 0) { 
     uint32_t crc = ~previousCrc32; // same as previousCrc32 ^ 0xFFFFFFFF 
     unsigned char* current = (unsigned char*) data; 
     while (length--) { 
         crc ^= *current++; 
         for (unsigned int j = 0; j < 8; j++) {
             if (crc & 1) 
                 crc = (crc >> 1) ^ Polynomial; 
             else 
                 crc = crc >> 1; 
         }

     } 
     return ~crc; // same as crc ^ 0xFFFFFFFF 
} 

Answer 2

C:

UInt32
crc32(UInt32 crc, UInt8 *p, SInt len)
{
  crc = ~crc;
  while (--len >= 0) {
    crc = crc ^ *p++;
    for (SInt i = 8; --i >= 0;) {
      crc = (crc >> 1) ^ (0xedb88320 & -(crc & 1));
    }
  }
  return ~crc;
}

void
crc_unitTest(void)
{
  UInt8 b1[] = { 0, 0, 0, 0, 0, 0, 0, 0 };
  UInt8 b2[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  UInt8 b3[] = { 0xff, 0, 0xff, 0, 0xff, 0, 0xff, 0 };
  assert(crc32(0, b1,  8) == 0x6522df69);
  assert(crc32(0, b2, 10) == 0x456cd746);
  assert(crc32(0, b3,  8) == 0xea8c89c0);
}

Python:

def crc32(crc, p, len):
  crc = 0xffffffff & ~crc
  for i in range(len):
    crc = crc ^ p[i]
    for j in range(8):
      crc = (crc >> 1) ^ (0xedb88320 & -(crc & 1))
  return 0xffffffff & ~crc

def unitTest():
  b1 = [ 0, 0, 0, 0, 0, 0, 0, 0 ]
  b2 = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
  b3 = [ 0xff, 0, 0xff, 0, 0xff, 0, 0xff, 0 ]
  assert(crc32(0, b1,  8) == 0x6522df69)
  assert(crc32(0, b2, 10) == 0x456cd746)
  assert(crc32(0, b3,  8) == 0xea8c89c0)

Answer 3

我现在在用 zlib.crc32，但在 C 语言里没有这样的库。

其实是有的，叫做 zlib。zlib 是用 C 语言写的，Python 也在用这个库！所以这个类的名字就是由此而来的。

你可以在 zlib 里使用 crc32() 这个函数。这个实现比你可能找到的其他实现要快很多。想了解接口信息，可以看看 zlib.h。

你可以自己编译 zlib，或者它可能已经在你的系统上安装好了。

更新：

我现在看到你在评论里提到（这条评论应该加到问题里，因为它对得到正确答案很重要）你有非常有限的内存。那么你可以使用这个：

static uint32_t crc32(uint32_t crc, unsigned char *buf, size_t len)
{
    int k;

    crc = ~crc;
    while (len--) {
        crc ^= *buf++;
        for (k = 0; k < 8; k++)
            crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
    }
    return ~crc;
}

crc 一开始设为零。

使用 ~ 可以得到正确的结果，因为 stdint.h 里的 uint32_t 类型保证是 32 位的。

如果你能多用一点代码空间，展开循环可能会让它更快（如果编译器没有自动这样做的话）：

static uint32_t crc32(uint32_t crc, unsigned char *buf, size_t len)
{
    crc = ~crc;
    while (len--) {
        crc ^= *buf++;
        crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
    }
    return ~crc;
}

你说你只有 4 KBytes 的“内存”。这只是程序的工作内存吗，还是程序也必须在这里运行？如果你在闪存里有更多空间，比如用来存放代码，那么可以预先计算一个表并和代码一起存储。使用表驱动的 CRC 会快很多。zlib 的代码提供了表驱动的 CRC，可以一次处理一个字节或四个字节，分别需要 1Kbyte 或 4Kbyte 的表。

更新 2：

因为你在评论里回答说这 4KBytes 只是工作内存，所以你应该使用表驱动的 CRC。你可以直接使用 zlib 的 crc32() 函数和 crc32.h 中的表，前提是 BYFOUR 没有被定义。