    {- 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)