良く使うアルゴリズムをC言語で書く [CRC32]

目的 -
頻繁に利用する処理をC言語で記述し、
各言語でC言語のライブラリを使う為のラッパーを記述する事で、パフォーマンス＆再利用生の向上を図る。

JAVAVM, Parrot, Rotor(EMCA-335 CLI)等、複数の言語の
言語中立のランタイムを提供するものは幾つかあるが、
ここでは別のアプローチで、SWIGの利用を想定する。

例としてCRCを取り上げて、実装してみる。

CRCとは。。。

• PNGのチェックサムに使われる。
• GZIPでも使っていた。(option)
• 詳しくは、RFC 1952. PNGの仕様書にも実装例が載っている。
• ZLibのソース。

 import binascii
 
 if __name__ == '__main__':
   import sys
   print "%lu" % (binascii.crc32(sys.argv[1]))

binascii.crc32は、4 byteのIntegerを返すので、
出力時にフォーマット指定で変換する。
PythonやPHPでは標準モジュールには含まれているのだけど、
他の言語の標準module/libraryにはあまり見当たらない。
ZLibにcrc32関数が含まれているので、ライブラリとして提供されているものは多いかも知れないが。

CRC32を例に、

# テーブル作成
crc_table = [0] * 256
for n in xrange(256):
  c = n
  for m in xrange(8):
    if c & 1:
      c = 0xedb88320 ^ (c >> 1)
    else:
      c = c >> 1
  crc_table[n] = c

def print_csource():
  """C言語のソースを出力"""
  global crc_table
  print "static unsigned long crc_table[256] ={\n\t",
  for n in xrange(len(crc_table)):
    print "0x%08lxUL," % crc_table[n],
    if n % 5 == 0:
      print "\n\t",
  print "};"


def crc32(data, crc=0xffffffffL):
  for i in xrange(data):
    crc = crc_table[(crc ^ i) & 0xff] ^ (crc >> 8)
  return crc ^ 0xffffffffL

とりあえず書いてみたが、型情報がどうなっているのか
曖昧なので不安。

アルゴリズムは大体こんな感じ。
テーブル作成部分は一度しか実行しないのであまり気にならないが、crc32関数は何度も呼び出される事があるので、最適化したい。

• Pythonコードの最適化(引数のパースを避ける為に関数を分ける)。
• アルゴリズムの最適化。
• pychoモジュールを使う。
• C言語で書く。(binasciiモジュール, zlibモジュール)

続く ...