python - Same crc32 for Python and C

Question

I need script that will calculate crc32 with the same output for both Python and C.

I'm using right now zlib.crc32, but for C there is no such library and we are writing it on our own basing on Wikipedia. But it doesn't return the same value.

This is our code of C script (copied from wikipedia, based on 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;
}

EDIT:

RAM メモリは 4KB しかありません。プログラム自体はそこにはありません。crc32 スクリプトで 1KB のメモリを使用するのは、おそらく多すぎて収まりません。CにもZLIBライブラリが存在することを指摘してくれてありがとう。

score 11 · Accepted Answer

現在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 は、最初はゼロに設定されています。

タイプ inは 32 ビットであることが保証されているため、を使用する~と正しい結果が得られます。uint32_tstdint.h

もう少しコードスペースに余裕がある場合は、ループを展開すると速度が向上する可能性があります (コンパイラがまだこれを行っていない場合)。

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キロバイトしかないとおっしゃいました。それはプログラムの単なる作業メモリですか、それともプログラムもそこに存在する必要がありますか? たとえばコード用にフラッシュにもっと多くのスペースがある場合は、テーブルを事前に計算してコードとともに保存できます。テーブル駆動型 CRC ははるかに高速です。zlib コードは、一度に 1 バイトと一度に 4 バイトを実行するテーブル駆動型 CRC を提供し、それぞれ 1K バイトまたは 4K バイトのテーブルを必要とします。

更新 2:

コメントで 4KBytes は単なる作業メモリであると答えたので、テーブル駆動型 CRC を使用する必要があります。crc32()zlib の関数とundefinedcrc32.cのテーブルを単純に使用できます。crc32.hBYFOUR

score 4 · Accepted Answer

子：

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);
}

パイソン:

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)

score 3 · Accepted Answer

ルックアップテーブルを使用しない C 実装 (ほとんどの実装では使用されています) が必要なため、対応する Python と同等のものを使用できます。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 */ }

編集: 上記のコードには問題があると複数の人が指摘しているように、以下のコードは Wikipedia のもの ( 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 
}

python - Same crc32 for Python and C

3 に答える 3

Related

Reference