2

我需要一个脚本，该脚本将为 Python 和 C 计算具有相同输出的 crc32。

我现在正在使用 zlib.crc32，但是对于 C 没有这样的库，我们正在根据维基百科自己编写它。但它不会返回相同的值。

这是我们的 C 脚本代码（从 wikipedia 复制，基于 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 的 ram 内存，程序本身并不存在。通过 crc32 脚本占用 1KB 的内存可能太多了，不适合那里。感谢您指出 C 也存在 ZLIB 库。

4

3 回答 3

11

我现在正在使用 zlib.crc32，但是对于 C 没有这样的库

嗯，是的，有。它被称为zlib。zlib 是用 C 编写的，它是 Python 使用的！因此类的名称。

您可以使用crc32()zlib 中的函数。该实现比您可能发现的其他实现要快得多。阅读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 最初设置为零。

使用~将给出正确的结果，因为输入的uint32_t类型stdint.h保证为 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 KB 的“内存”。那只是程序的工作记忆，还是程序也必须在那里？例如，如果您在闪存中有更多空间用于代码，则可以预先计算表格并将其与代码一起存储。表驱动的 CRC 会快得多。zlib 代码提供表驱动的 CRC，一次执行一个字节，一次执行四个字节，分别需要一个 1Kbyte 或 4Kbyte 的表。

更新 2：

既然您在评论中回答说 4KBytes 只是工作内存，那么您应该使用表驱动的 CRC。您可以简单地使用crc32()zlib 中的函数和未定义crc32.c的表。crc32.hBYFOUR

于 2013-02-22T18:54:51.270 回答
4

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)
于 2015-04-12T20:20:12.560 回答
3

由于您需要一个不使用查找表（大多数实现都使用）和匹配的 Python 等效项的 C 实现，因此您可以按照 Mark Ransom ( binascii.crc32 ) 的建议使用 ZIP 的 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 
}
于 2013-02-22T18:02:30.470 回答