Python和C的crc32相同

Question

我需要一个脚本来计算crc32，同时为Python和C提供相同的输出

我现在正在使用zlib.crc32，但是对于C来说没有这样的库，我们是基于Wikipedia自己编写的。但它不返回相同的值。

这是我们的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内存可能太多，不适合那里。 感谢您指出ZLIB库也适用于C。

Answer 1

I'm using right now zlib.crc32, but for C there is no such library

嗯，是的，有。它叫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千字节的“内存”。这只是程序的工作内存，还是程序也必须存在于其中？例如，如果flash中有更多的代码空间，那么可以预先计算表并将其与代码一起存储。表驱动的CRC将快得多。zlib代码提供表驱动的crc，它们一次执行一个字节，一次执行四个字节，分别需要一个1Kbyte或4Kbyte表。

更新2:

由于您在注释中回答4KBytes只是工作内存，那么您应该使用表驱动的CRC。您可以简单地使用zlib的crc32.c中的crc32()函数和crc32.h中未定义BYFOUR的表。

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

由于您需要一个不使用查找表（大多数实现都是这样）的C实现和一个匹配的Python等价物，因此可以使用Mark Ransom（binasci.CRC32）建议的ZIP的CRC32和我借用的匹配的无表实现here

/* 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 */
}

编辑：正如一些人指出的，上面的代码有问题，下面的代码与Wikipedia（参见http://ideone.com/pWLVSo）和Python（参见http://ideone.com/SvYuyE-1277644989==0x4c2750bd）匹配。这段代码来自this page，在这里，我复制的基本版本的其他实现和可能的改进

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 
}