{- CRC16 checksum inspired by http://hackage.haskell.org/package/crc16-table
   As of 2011-04-13, this module is about 20x faster than crc16-table.
-}
module Data.Acid.CRC
    ( crc16
    ) where

import Data.Word                                ( Word16 )
import Data.Array.Unboxed                       ( UArray, listArray )
import Data.Array.Base                          ( unsafeAt )
import Data.Bits                                ( Bits(..) )

import qualified Data.ByteString.Lazy as Lazy   ( ByteString, foldl' )


tableList :: [Word16]
tableList :: [Word16]
tableList =
  [Word16
0x00000,Word16
0x01189,Word16
0x02312,Word16
0x0329B,Word16
0x04624,Word16
0x057AD,Word16
0x06536,Word16
0x074BF,
   Word16
0x08C48,Word16
0x09DC1,Word16
0x0AF5A,Word16
0x0BED3,Word16
0x0CA6C,Word16
0x0DBE5,Word16
0x0E97E,Word16
0x0F8F7,
   Word16
0x01081,Word16
0x00108,Word16
0x03393,Word16
0x0221A,Word16
0x056A5,Word16
0x0472C,Word16
0x075B7,Word16
0x0643E,
   Word16
0x09CC9,Word16
0x08D40,Word16
0x0BFDB,Word16
0x0AE52,Word16
0x0DAED,Word16
0x0CB64,Word16
0x0F9FF,Word16
0x0E876,
   Word16
0x02102,Word16
0x0308B,Word16
0x00210,Word16
0x01399,Word16
0x06726,Word16
0x076AF,Word16
0x04434,Word16
0x055BD,
   Word16
0x0AD4A,Word16
0x0BCC3,Word16
0x08E58,Word16
0x09FD1,Word16
0x0EB6E,Word16
0x0FAE7,Word16
0x0C87C,Word16
0x0D9F5,
   Word16
0x03183,Word16
0x0200A,Word16
0x01291,Word16
0x00318,Word16
0x077A7,Word16
0x0662E,Word16
0x054B5,Word16
0x0453C,
   Word16
0x0BDCB,Word16
0x0AC42,Word16
0x09ED9,Word16
0x08F50,Word16
0x0FBEF,Word16
0x0EA66,Word16
0x0D8FD,Word16
0x0C974,
   Word16
0x04204,Word16
0x0538D,Word16
0x06116,Word16
0x0709F,Word16
0x00420,Word16
0x015A9,Word16
0x02732,Word16
0x036BB,
   Word16
0x0CE4C,Word16
0x0DFC5,Word16
0x0ED5E,Word16
0x0FCD7,Word16
0x08868,Word16
0x099E1,Word16
0x0AB7A,Word16
0x0BAF3,
   Word16
0x05285,Word16
0x0430C,Word16
0x07197,Word16
0x0601E,Word16
0x014A1,Word16
0x00528,Word16
0x037B3,Word16
0x0263A,
   Word16
0x0DECD,Word16
0x0CF44,Word16
0x0FDDF,Word16
0x0EC56,Word16
0x098E9,Word16
0x08960,Word16
0x0BBFB,Word16
0x0AA72,
   Word16
0x06306,Word16
0x0728F,Word16
0x04014,Word16
0x0519D,Word16
0x02522,Word16
0x034AB,Word16
0x00630,Word16
0x017B9,
   Word16
0x0EF4E,Word16
0x0FEC7,Word16
0x0CC5C,Word16
0x0DDD5,Word16
0x0A96A,Word16
0x0B8E3,Word16
0x08A78,Word16
0x09BF1,
   Word16
0x07387,Word16
0x0620E,Word16
0x05095,Word16
0x0411C,Word16
0x035A3,Word16
0x0242A,Word16
0x016B1,Word16
0x00738,
   Word16
0x0FFCF,Word16
0x0EE46,Word16
0x0DCDD,Word16
0x0CD54,Word16
0x0B9EB,Word16
0x0A862,Word16
0x09AF9,Word16
0x08B70,
   Word16
0x08408,Word16
0x09581,Word16
0x0A71A,Word16
0x0B693,Word16
0x0C22C,Word16
0x0D3A5,Word16
0x0E13E,Word16
0x0F0B7,
   Word16
0x00840,Word16
0x019C9,Word16
0x02B52,Word16
0x03ADB,Word16
0x04E64,Word16
0x05FED,Word16
0x06D76,Word16
0x07CFF,
   Word16
0x09489,Word16
0x08500,Word16
0x0B79B,Word16
0x0A612,Word16
0x0D2AD,Word16
0x0C324,Word16
0x0F1BF,Word16
0x0E036,
   Word16
0x018C1,Word16
0x00948,Word16
0x03BD3,Word16
0x02A5A,Word16
0x05EE5,Word16
0x04F6C,Word16
0x07DF7,Word16
0x06C7E,
   Word16
0x0A50A,Word16
0x0B483,Word16
0x08618,Word16
0x09791,Word16
0x0E32E,Word16
0x0F2A7,Word16
0x0C03C,Word16
0x0D1B5,
   Word16
0x02942,Word16
0x038CB,Word16
0x00A50,Word16
0x01BD9,Word16
0x06F66,Word16
0x07EEF,Word16
0x04C74,Word16
0x05DFD,
   Word16
0x0B58B,Word16
0x0A402,Word16
0x09699,Word16
0x08710,Word16
0x0F3AF,Word16
0x0E226,Word16
0x0D0BD,Word16
0x0C134,
   Word16
0x039C3,Word16
0x0284A,Word16
0x01AD1,Word16
0x00B58,Word16
0x07FE7,Word16
0x06E6E,Word16
0x05CF5,Word16
0x04D7C,
   Word16
0x0C60C,Word16
0x0D785,Word16
0x0E51E,Word16
0x0F497,Word16
0x08028,Word16
0x091A1,Word16
0x0A33A,Word16
0x0B2B3,
   Word16
0x04A44,Word16
0x05BCD,Word16
0x06956,Word16
0x078DF,Word16
0x00C60,Word16
0x01DE9,Word16
0x02F72,Word16
0x03EFB,
   Word16
0x0D68D,Word16
0x0C704,Word16
0x0F59F,Word16
0x0E416,Word16
0x090A9,Word16
0x08120,Word16
0x0B3BB,Word16
0x0A232,
   Word16
0x05AC5,Word16
0x04B4C,Word16
0x079D7,Word16
0x0685E,Word16
0x01CE1,Word16
0x00D68,Word16
0x03FF3,Word16
0x02E7A,
   Word16
0x0E70E,Word16
0x0F687,Word16
0x0C41C,Word16
0x0D595,Word16
0x0A12A,Word16
0x0B0A3,Word16
0x08238,Word16
0x093B1,
   Word16
0x06B46,Word16
0x07ACF,Word16
0x04854,Word16
0x059DD,Word16
0x02D62,Word16
0x03CEB,Word16
0x00E70,Word16
0x01FF9,
   Word16
0x0F78F,Word16
0x0E606,Word16
0x0D49D,Word16
0x0C514,Word16
0x0B1AB,Word16
0x0A022,Word16
0x092B9,Word16
0x08330,
   Word16
0x07BC7,Word16
0x06A4E,Word16
0x058D5,Word16
0x0495C,Word16
0x03DE3,Word16
0x02C6A,Word16
0x01EF1,Word16
0x00F78]

table :: UArray Word16 Word16
table :: UArray Word16 Word16
table = (Word16, Word16) -> [Word16] -> UArray Word16 Word16
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
(i, i) -> [e] -> a i e
listArray (Word16
0,Word16
255) [Word16]
tableList

crc16 :: Lazy.ByteString -> Word16
crc16 :: ByteString -> Word16
crc16 = UArray Word16 Word16
table UArray Word16 Word16
-> (ByteString -> Word16) -> ByteString -> Word16
forall a b. a -> b -> b
`seq` Word16 -> Word16
forall a. Bits a => a -> a
complement (Word16 -> Word16)
-> (ByteString -> Word16) -> ByteString -> Word16
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Word16 -> Word8 -> Word16) -> Word16 -> ByteString -> Word16
forall a. (a -> Word8 -> a) -> a -> ByteString -> a
Lazy.foldl' Word16 -> Word8 -> Word16
forall {p}. Integral p => Word16 -> p -> Word16
worker Word16
0xFFFF
    where worker :: Word16 -> p -> Word16
worker Word16
acc p
x = (Word16
acc Word16 -> Int -> Word16
forall a. Bits a => a -> Int -> a
`shiftR` Int
8) Word16 -> Word16 -> Word16
forall a. Bits a => a -> a -> a
`xor` (UArray Word16 Word16
table UArray Word16 Word16 -> Int -> Word16
forall i. Ix i => UArray i Word16 -> Int -> Word16
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt` Int
idx)
              where idx :: Int
idx = Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral ((Word16
acc Word16 -> Word16 -> Word16
forall a. Bits a => a -> a -> a
`xor` p -> Word16
forall a b. (Integral a, Num b) => a -> b
fromIntegral p
x) Word16 -> Word16 -> Word16
forall a. Bits a => a -> a -> a
.&. Word16
0xFF)