Hello world !

2003 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2004 | 01 | 02 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2005 | 02 | 05 |
2006 | 09 |
2007 | 05 | 08 |
2008 | 05 | 10 |
2009 | 07 |

2004-04-02 CRC32

良く使うアルゴリズム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を返すので、

出力時にフォーマット指定で変換する。

PythonPHPでは標準モジュールには含まれているのだけど、

他の言語の標準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モジュール)

続く ...

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/teamikl/20040402