巡回冗長検査(CRC-32)のHaskellでの実装

計算方法

巡回冗長検査(CRC)のよくある計算方法の説明

テーブルを作る

1. はじめにtにeを代入する
2. 3から6を8回くりかえす
3. tを最下位ビットbと残りrにわける
4. rを右シフトする
5. bが0ならばrをtとする
6. bが1ならばrとわる数'とをxorしてtとする

eに0から255までを代入し結果をテーブルに保存する。

CRCを求める

1. tに2 ^ n - 1を代入する
2. tを先頭8ビットeと残りrにわける
3. rを8ビット右シフトする
4. 8ビット読みだしeとのxorをとりe'とする
   1. ただし、読みこめなければtが結果となる
5. e'に対応する値をテーブルから読みこみsとする
6. sとrとをxorしtに代入する
7. 2へもどる

コード

必要なモジュール

crc32.hs

import Control.Arrow
import Data.Array
import Data.Bits
import Data.Bool
import Data.Word
import qualified Data.ByteString.Lazy as LBS

テーブルの作成

補助関数

最下位ビットと残りのビット列とにわける。

crc32.hs

popBit :: Bits a => a -> (Bool, a)
popBit n = (n `testBit` 0, n `shiftR` 1)

1ビットぶんの計算

crc32.hs

crc1 :: Word32 -> Word32
crc1 = uncurry (bool id (`xor` 0xedb88320)) . popBit

最下位ビットが0ならば残りのビット列そのままとし、1ならば残りのビット列と定数値とをxorする。

8ビットぶんの計算

crc32.hs

crc8 :: Word8 -> Word32
crc8 n = iterate crc1 (fromIntegral n) !! 8

返り値は8ビットを読みこんだときの続くビット列に対する「変換」を表す。

テーブルの作成

crc32.hs

table :: Array Word8 Word32
table = listArray (0, 255) $ map crc8 [0 .. 255]

CRCを求める

補助関数

crc32.hs

popByte :: (Integral a, Bits a) => a -> (Word8, a)
popByte n = (fromIntegral n, n `shiftR` 8)

1バイトぶんの計算

crc32.hs

step :: Word32 -> Word8 -> Word32
step n b = uncurry xor . (first $ (table !) . (`xor` b)) $ popByte n

「変換」を下位8ビットと残りのビット列とにわける。下位8ビットと読みこんだ1バイトとをxorする。それに対応する「変換」をテーブルから読みこみ残りのビット列とのxorをとる。これが新しい「変換」となる。
バイト列に対する計算

crc32.hs

crc :: LBS.ByteString -> Word32
crc = complement . LBS.foldl' step 0xffffffff

「変換」の初期値はすべてのビットが1の4バイトの値である。またCRCは最後に補数をとる。

CRCをチェックする

CRCのチェックはCRCを求めて同値性を比較しても良いがもっとスマートなやりかたがある。もとデータの末尾にCRCの値を追加したもののCRCをとると定数になるという性質を利用する。

補助関数

crc32.hs

word32ToBytes :: Word32 -> [Word8]
word32ToBytes = wtl (4 :: Int)
        where
        wtl i | i < 1 = const []
        wtl i = uncurry (:) . (wtl (i - 1) `second`) . popByte

Word32の値をリトルエンディアンでバイト値のリストにする。

チェック

crc32.hs

check :: LBS.ByteString -> Word32 -> Bool
check bs n = crc (bs `LBS.append` (LBS.pack $ word32ToBytes n)) == 0x2144df1c