CRCを計算する関数

ビット演算 + Arrayの練習として、CRCを計算する関数を実装してみました。CRCは、RFC1592の付録のソースを参考にしています(というかそのままHaskellに移植しただけです)。Haskellだったら一回目の呼び出しのときだけテーブルを初期化して…とか考えなくてもいいので楽です。

module Main (main) where

import Data.Array (Array, (!), listArray)
import Data.Bits ((.&.), xor, shiftR)
import Data.Char (ord)
import Data.Word (Word32)
import Numeric (showHex)

crc :: String -> Word32
crc = xor 0xffffffff . foldl crc' 0xffffffff
  where
    crc' :: Word32 -> Char -> Word32
    crc' c x = 
      let i = (xor c $ fromIntegral $ ord x) .&. 0xff
      in xor (table ! i) $ shiftR c 8

    table :: Array Word32 Word32
    table =
      listArray (0, 255) $ map (\ n -> foldl table' n [0 .. 7]) [0 .. 255]
      where
        table' :: Word32 -> Int -> Word32
        table' c _
          | c .&. 1 == 0 = shiftR c 1
          | otherwise    = xor 0xedb88320 $ shiftR c 1

main :: IO ()
main = p . crc =<< getContents
  where
    p :: Word32 -> IO ()
    p c = putStrLn $ "0x" ++ showHex c ""

-- Local Variables:
-- compile-command: "ghc -W -fno-warn-unused-matches --make -o crc crc"
-- End:

参照: RFC1592