    module Data.Hash.Base where

    import Data.Array
    import Foreign (Storable, with, sizeOf, castPtr, Ptr, peek, plusPtr)
    import System.IO.Unsafe (unsafePerformIO)
    import Data.Word
    import Data.Bits

    #ifdef __GLASGOW_HASKELL__
    import GHC.Arr ( unsafeAt )

    {-# INLINE myArrayRead #-}
    myArrayRead :: Array Word8 Word64 -> Word8 -> Word64
    myArrayRead :: Array Word8 Word64 -> Word8 -> Word64
    myArrayRead Array Word8 Word64
    a Word8
    i = Array Word8 Word64 -> Int -> Word64
    forall i e. Array i e -> Int -> e
    unsafeAt Array Word8 Word64
    a (Word8 -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Word8
    i)
    #else
    {-# INLINE myArrayRead #-}
    myArrayRead :: Array Word8 Word64 -> Word8 -> Word64
    myArrayRead = (!)
    #endif

    -- | A 64-bit hash
    newtype Hash = Hash{Hash -> Word64
    asWord64 :: Word64} deriving (Hash -> Hash -> Bool
    (Hash -> Hash -> Bool) -> (Hash -> Hash -> Bool) -> Eq Hash
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: Hash -> Hash -> Bool
    == :: Hash -> Hash -> Bool
    $c/= :: Hash -> Hash -> Bool
    /= :: Hash -> Hash -> Bool
    Eq, Eq Hash
    Eq Hash =>
    (Hash -> Hash -> Ordering)
    -> (Hash -> Hash -> Bool)
    -> (Hash -> Hash -> Bool)
    -> (Hash -> Hash -> Bool)
    -> (Hash -> Hash -> Bool)
    -> (Hash -> Hash -> Hash)
    -> (Hash -> Hash -> Hash)
    -> Ord Hash
    Hash -> Hash -> Bool
    Hash -> Hash -> Ordering
    Hash -> Hash -> Hash
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    $ccompare :: Hash -> Hash -> Ordering
    compare :: Hash -> Hash -> Ordering
    $c< :: Hash -> Hash -> Bool
    < :: Hash -> Hash -> Bool
    $c<= :: Hash -> Hash -> Bool
    <= :: Hash -> Hash -> Bool
    $c> :: Hash -> Hash -> Bool
    > :: Hash -> Hash -> Bool
    $c>= :: Hash -> Hash -> Bool
    >= :: Hash -> Hash -> Bool
    $cmax :: Hash -> Hash -> Hash
    max :: Hash -> Hash -> Hash
    $cmin :: Hash -> Hash -> Hash
    min :: Hash -> Hash -> Hash
    Ord, Hash
    Hash -> Hash -> Bounded Hash
    forall a. a -> a -> Bounded a
    $cminBound :: Hash
    minBound :: Hash
    $cmaxBound :: Hash
    maxBound :: Hash
    Bounded, Int -> Hash -> ShowS
    [Hash] -> ShowS
    Hash -> String
    (Int -> Hash -> ShowS)
    -> (Hash -> String) -> ([Hash] -> ShowS) -> Show Hash
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> Hash -> ShowS
    showsPrec :: Int -> Hash -> ShowS
    $cshow :: Hash -> String
    show :: Hash -> String
    $cshowList :: [Hash] -> ShowS
    showList :: [Hash] -> ShowS
    Show)

    -- | @h1 \`combine\` h2@ combines hashes @h1@ and @h2@ into a new hash.
    --
    -- It is used to generate hash functions for complex types. For example:
    --
    -- @
    -- hashPair :: (Hashable a, Hashable b) => (a,b) -> Hash
    -- hashPair (a,b) = hash a \`combine\` hash b
    -- @
    {-# INLINE combine #-}
    combine :: Hash -> Hash -> Hash
    combine :: Hash -> Hash -> Hash
    combine (Hash Word64
    a) (Hash Word64
    b) = Word64 -> Hash
    Hash (Word64 -> Hash) -> Word64 -> Hash
    forall a b. (a -> b) -> a -> b
    $ (Word64 -> Int -> Word64
    forall a. Bits a => a -> Int -> a
    rotate Word64
    a Int
    1) Word64 -> Word64 -> Word64
    forall a. Bits a => a -> a -> a
    `xor` Word64
    b

    {-# INLINE hashWord8 #-}
    hashWord8 :: Word8 -> Hash
    hashWord8 :: Word8 -> Hash
    hashWord8 = Word64 -> Hash
    Hash (Word64 -> Hash) -> (Word8 -> Word64) -> Word8 -> Hash
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Array Word8 Word64 -> Word8 -> Word64
    myArrayRead Array Word8 Word64
    hashArrW8

    {-# INLINE hashWord16 #-}
    hashWord16 :: Word16 -> Hash
    hashWord16 :: Word16 -> Hash
    hashWord16 Word16
    w = Word8 -> Hash
    hashWord8 Word8
    lo Hash -> Hash -> Hash
    `combine` Word8 -> Hash
    hashWord8 Word8
    hi
        where lo :: Word8
    lo = Word16 -> Word8
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Word16
    w
              hi :: Word8
    hi = Word16 -> Word8
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral (Word16 -> Int -> Word16
    forall a. Bits a => a -> Int -> a
    rotateR Word16
    w Int
    8)

    {-# INLINE hashWord32 #-}
    hashWord32 :: Word32 -> Hash
    hashWord32 :: Word32 -> Hash
    hashWord32 Word32
    w = Word16 -> Hash
    hashWord16 Word16
    lo Hash -> Hash -> Hash
    `combine` Word16 -> Hash
    hashWord16 Word16
    hi
        where lo :: Word16
    lo = Word32 -> Word16
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Word32
    w
              hi :: Word16
    hi = Word32 -> Word16
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral (Word32 -> Int -> Word32
    forall a. Bits a => a -> Int -> a
    rotateR Word32
    w Int
    16)

    {-# INLINE hashWord64 #-}
    hashWord64 :: Word64 -> Hash
    hashWord64 :: Word64 -> Hash
    hashWord64 Word64
    w = Word32 -> Hash
    hashWord32 Word32
    lo Hash -> Hash -> Hash
    `combine` Word32 -> Hash
    hashWord32 Word32
    hi
        where lo :: Word32
    lo = Word64 -> Word32
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Word64
    w
              hi :: Word32
    hi = Word64 -> Word32
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral (Word64 -> Int -> Word64
    forall a. Bits a => a -> Int -> a
    rotateR Word64
    w Int
    16)

    {-# INLINE hashInt #-}
    hashInt :: Int -> Hash
    hashInt :: Int -> Hash
    hashInt = if Int -> Int
    forall a. Bits a => a -> Int
    bitSize (Int
    forall a. HasCallStack => a
    undefined :: Int)  Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    32
                then Word32 -> Hash
    hashWord32 (Word32 -> Hash) -> (Int -> Word32) -> Int -> Hash
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Int -> Word32
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral
                else Word64 -> Hash
    hashWord64 (Word64 -> Hash) -> (Int -> Word64) -> Int -> Hash
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Int -> Word64
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral

    -- | Observe that, unlike the other functions in this module,
    -- @hashStorable@ is machine-dependent (the computed hash depends
    -- on endianness, etc.).
    hashStorable :: Storable a => a -> Hash
    hashStorable :: forall a. Storable a => a -> Hash
    hashStorable a
    a = IO Hash -> Hash
    forall a. IO a -> a
    unsafePerformIO (a -> (Ptr a -> IO Hash) -> IO Hash
    forall a b. Storable a => a -> (Ptr a -> IO b) -> IO b
    with a
    a ((Ptr a -> IO Hash) -> IO Hash) -> (Ptr a -> IO Hash) -> IO Hash
    forall a b. (a -> b) -> a -> b
    $ Int -> Hash -> Ptr Word8 -> IO Hash
    go  (a -> Int
    forall a. Storable a => a -> Int
    sizeOf a
    a) Hash
    h0 (Ptr Word8 -> IO Hash) -> (Ptr a -> Ptr Word8) -> Ptr a -> IO Hash
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Ptr a -> Ptr Word8
    forall a b. Ptr a -> Ptr b
    castPtr)
        where go :: Int -> Hash -> Ptr Word8 -> IO Hash
              go :: Int -> Hash -> Ptr Word8 -> IO Hash
    go Int
    0 Hash
    h Ptr Word8
    _ = Hash -> IO Hash
    forall a. a -> IO a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Hash
    h
              go Int
    n Hash
    h Ptr Word8
    p = do b <- Ptr Word8 -> IO Word8
    forall a. Storable a => Ptr a -> IO a
    peek Ptr Word8
    p
                            go  (n-1) (h `combine` hashWord8 b) (plusPtr p 1)

    -- This array must satisfy the property that, if seen as a matrix of
    -- 256 x 64 bits, then on each of the 64 columns one must have 128 ones
    -- and 128 zeros.
    -- This particular selection of values was taken from
    -- http://www.serve.net/buz/hash.adt/java.008.html
    hashArrW8 :: Array Word8 Word64
    hashArrW8 :: Array Word8 Word64
    hashArrW8 = (Word8, Word8) -> [Word64] -> Array Word8 Word64
    forall i e. Ix i => (i, i) -> [e] -> Array i e
    listArray (Word8
    0,Word8
    255) [
     {- 000 -} Word64
    0x4476081a7043a46f, Word64
    0x45768b8a6e7eac19, Word64
    0xebd556c1cf055952,
     {-     -} Word64
    0x72ed2da1bf010101, Word64
    0x3ff2030b128e8a64,
     {- 005 -} Word64
    0xcbc330238adcfef2, Word64
    0x737807fe42e20c6c, Word64
    0x74dabaedb1095c58,
     {-     -} Word64
    0x968f065c65361d67, Word64
    0xd3f4018ac7a4b199,
     {- 010 -} Word64
    0x954b389b52f24df2, Word64
    0x2f97a9d8d0549327, Word64
    0xb9bea2b49a3b180f,
     {-     -} Word64
    0xaf2f42536b21f2eb, Word64
    0x85d991663cff1325,
     {- 015 -} Word64
    0xb9e1260207b575b9, Word64
    0xf3ea88398a23b7e2, Word64
    0xfaf8c83ffbd9091d,
     {-     -} Word64
    0x4274fe90834dbdf9, Word64
    0x3f20b157b68d6313,
     {- 020 -} Word64
    0x68b48972b6d06b93, Word64
    0x694837b6eba548af, Word64
    0xeecb51d1acc917c9,
     {-     -} Word64
    0xf1c633f02dffbcfa, Word64
    0xa6549ec9d301f3b5,
     {- 025 -} Word64
    0x451dc944f1663592, Word64
    0x446d6acef6ce9e4f, Word64
    0x1c8a5b3013206f02,
     {-     -} Word64
    0x5908ca36f2dc50f7, Word64
    0x4fd55d3f3e880a87,
     {- 030 -} Word64
    0xa03a8dbeabbf065d, Word64
    0x3ccbbe078fabcb6d, Word64
    0x1da53a259116f2d0,
     {-     -} Word64
    0xfb27a96fcb9af152, Word64
    0x50aba242e85aec09,
     {- 035 -} Word64
    0x24d4e414fc4fc987, Word64
    0x83971844a9ce535e, Word64
    0xc26a3fdeb849398e,
     {-     -} Word64
    0xc2380d044d2e70d8, Word64
    0xab418aa8ae19b18f,
     {- 040 -} Word64
    0xd95b6b9247d5ebea, Word64
    0x8b3b2171fdc60511, Word64
    0xe15cd0ae3fcc44af,
     {-     -} Word64
    0x5a4e27f914a68f17, Word64
    0x377bd28ca09aafdc,
     {- 045 -} Word64
    0xbbeb9828594a3294, Word64
    0x7c8df263ae1de1b9, Word64
    0xba0a48a5fd1c1dd0,
     {-     -} Word64
    0x57cc1b8818b98ee6, Word64
    0x8c570975d357dabc,
     {- 050 -} Word64
    0x76bdcd6f2e8826aa, Word64
    0x529b15b6ec4055f1, Word64
    0x9147c7a54c34f8a9,
     {-     -} Word64
    0x2f96a7728170e402, Word64
    0xe46602f455eca72e,
     {- 055 -} Word64
    0x22834c4dd1bde03f, Word64
    0x2644cf5a25e368ff, Word64
    0x907c6de90b120f4a,
     {-     -} Word64
    0xadfe8ba99028f728, Word64
    0xa85199ae14df0433,
     {- 060 -} Word64
    0x2d749b946dd3601e, Word64
    0x76e35457aa052772, Word64
    0x90410bf6e427f736,
     {-     -} Word64
    0x536ad04d13e35041, Word64
    0x8cc0d76769b76914,
     {- 065 -} Word64
    0xae0249f6e3b3c01c, Word64
    0x1bdfd075307d6faf, Word64
    0xd8e04f70c221decc,
     {-     -} Word64
    0x4ab23622a4281a5d, Word64
    0x37a5613da2fcaba7,
     {- 070 -} Word64
    0x19a56203666d4a9f, Word64
    0x158ffab502c4be93, Word64
    0x0bee714e332ecb2f,
     {-     -} Word64
    0x69b71a59f6f74ab0, Word64
    0x0fc7fc622f1dfe8f,
     {- 075 -} Word64
    0x513966de7152a6f9, Word64
    0xc16fae9cc2ea9be7, Word64
    0xb66f0ac586c1899e,
     {-     -} Word64
    0x11e124aee3bdefd7, Word64
    0x86cf5a577512901b,
     {- 080 -} Word64
    0x33f33ba6994a1fbd, Word64
    0xde6c4d1d3d47ff0d, Word64
    0x6a99220dc6f78e66,
     {-     -} Word64
    0x2dc06ca93e2d25d2, Word64
    0x96413b520134d573,
     {- 085 -} Word64
    0xb4715ce8e1023afa, Word64
    0xe6a75900c8c66c0a, Word64
    0x6448f13ad54c12ed,
     {-     -} Word64
    0xb9057c28cf6689f0, Word64
    0xf4023daf67f7677a,
     {- 090 -} Word64
    0x877c2650767b9867, Word64
    0xb7ea587dcd5b2341, Word64
    0xc048cf111733f9bc,
     {-     -} Word64
    0x112012c15bc867bf, Word64
    0xc95f52b1d9418811,
     {- 095 -} Word64
    0xa47e624ee7499083, Word64
    0x26928606df9b12e8, Word64
    0x5d020462ec3e0928,
     {-     -} Word64
    0x8bbde651f6d08914, Word64
    0xd5db83db758e524a,
     {- 100 -} Word64
    0x3105e355c000f455, Word64
    0xdd7fe1b81a786c79, Word64
    0x1f3a818c8e012db1,
     {-     -} Word64
    0xd902de819d7b42fa, Word64
    0x4200e63325cda5f0,
     {- 105 -} Word64
    0x0e919cdc5fba9220, Word64
    0x5360dd54605a11e1, Word64
    0xa3182d0e6cb23e6c,
     {-     -} Word64
    0x13ee462c1b483b87, Word64
    0x1b1b6087b997ee22,
     {- 110 -} Word64
    0x81c36d0b877f7362, Word64
    0xc24879932c1768d4, Word64
    0x1faa756e1673f9ad,
     {-     -} Word64
    0x61651b24d11fe93d, Word64
    0x30fe3d9304e1cde4,
     {- 115 -} Word64
    0x7be867c750747250, Word64
    0x973e52c7005b5db6, Word64
    0x75d6b699bbaf4817,
     {-     -} Word64
    0x25d2a9e97379e196, Word64
    0xe65fb599aca98701,
     {- 120 -} Word64
    0x6ac27960d24bde84, Word64
    0xdfacc04c9fabbcb6, Word64
    0xa46cd07f4a97882b,
     {-     -} Word64
    0x652031d8e59a1fd8, Word64
    0x1185bd967ec7ce10,
     {- 125 -} Word64
    0xfc9bd84c6780f244, Word64
    0x0a0c59872f61b3ff, Word64
    0x63885727a1c71c95,
     {-     -} Word64
    0x5e88b4390b2d765c, Word64
    0xf0005ccaf988514d,
     {- 130 -} Word64
    0x474e44280a98e840, Word64
    0x32de151c1411bc42, Word64
    0x2c4b86d5aa4482c2,
     {-     -} Word64
    0xccd93deb2d9d47da, Word64
    0x3743236ff128a622,
     {- 135 -} Word64
    0x42ed2f2635ba5647, Word64
    0x99c74afd18962dbd, Word64
    0x2d663bb870f6d242,
     {-     -} Word64
    0x7912033bc7635d81, Word64
    0xb442862f43753680,
     {- 140 -} Word64
    0x94b1a5400aeaab4c, Word64
    0x5ce285fe810f2220, Word64
    0xe8a7dbe565d9c0b1,
     {-     -} Word64
    0x219131af78356c94, Word64
    0x7b3a80d130f27e2f,
     {- 145 -} Word64
    0xbaa5d2859d16b440, Word64
    0x821cfb6935771070, Word64
    0xf68cfb6ee9bc2336,
     {-     -} Word64
    0x18244132e935d2fd, Word64
    0x2ed0bda1f4720cff,
     {- 150 -} Word64
    0x4ed48cdf6975173c, Word64
    0xfd37a7a2520e2405, Word64
    0x82c102b2a9e73ce2,
     {-     -} Word64
    0xadac6517062623a7, Word64
    0x5a1294d318e26104,
     {- 155 -} Word64
    0xea84fe65c0e4f061, Word64
    0x4f96f8a9464cfee9, Word64
    0x9831dff8ccdc534a,
     {-     -} Word64
    0x4ca927cd0f192a14, Word64
    0x030900b294b71649,
     {- 160 -} Word64
    0x644b263b9aeb0675, Word64
    0xa601d4e34647e040, Word64
    0x34d897eb397f1004,
     {-     -} Word64
    0xa6101c37f4ec8dfc, Word64
    0xc29d2a8bbfd0006b,
     {- 165 -} Word64
    0xc6b07df8c5b4ed0f, Word64
    0xce1b7d92ba6bccbe, Word64
    0xfa2f99442e03fe1b,
     {-     -} Word64
    0xd8863e4c16f0b363, Word64
    0x033b2cccc3392942,
     {- 170 -} Word64
    0x757dc33522d6cf9c, Word64
    0xf07b1ff6ce55fec5, Word64
    0x1569e75f09b40463,
     {-     -} Word64
    0xfa33fa08f14a310b, Word64
    0x6eb79aa27bbcf76b,
     {- 175 -} Word64
    0x157061207c249602, Word64
    0x25e5a71fc4e99555, Word64
    0x5df1fe93de625355,
     {-     -} Word64
    0x235b56090c1aa55d, Word64
    0xe51068613eaced91,
     {- 180 -} Word64
    0x45bd47b893b9ff1e, Word64
    0x6595e1798d381f2d, Word64
    0xc9b5848cbcdb5ba8,
     {-     -} Word64
    0x65985146ff7792bc, Word64
    0x4ab4a17bf05a19a0,
     {- 185 -} Word64
    0xfd94f4ca560ffb0c, Word64
    0xcf9bad581a68fa68, Word64
    0x92b4f0b502b1ce1a,
     {-     -} Word64
    0xbcbec0769a610474, Word64
    0x8dbd31ded1a0fecb,
     {- 190 -} Word64
    0xdd1f5ed9f90e8533, Word64
    0x61c1e6a523f84d95, Word64
    0xf24475f383c110c4,
     {-     -} Word64
    0xdb2dffa66f90588d, Word64
    0xac06d88e9ee04455,
     {- 195 -} Word64
    0xa215fc47c40504ba, Word64
    0x86d7caebfee93369, Word64
    0x9eaec31985804099,
     {-     -} Word64
    0x0fba2214abe5d01b, Word64
    0x5a32975a4b3865d6,
     {- 200 -} Word64
    0x8cceebc98a5c108f, Word64
    0x7e12c4589654f2dc, Word64
    0xa49ad49fb0d19772,
     {-     -} Word64
    0x3d142dd9c406152b, Word64
    0x9f13589e7be2b8a5,
     {- 205 -} Word64
    0x5e8dbac1892967ad, Word64
    0xcc23b93a6308e597, Word64
    0x1ef35f5fe874e16a,
     {-     -} Word64
    0x63ae9cc08d2e274f, Word64
    0x5bbabee56007fc05,
     {- 210 -} Word64
    0xabfd72994230fc39, Word64
    0x9d71a13a99144de1, Word64
    0xd9daf5aa8dcc89b3,
     {-     -} Word64
    0xe145ec0514161bfd, Word64
    0x143befc2498cd270,
     {- 215 -} Word64
    0xa8e192557dbbd9f8, Word64
    0xcbeda2445628d7d0, Word64
    0x997f0a93205d9ea4,
     {-     -} Word64
    0x01014a97f214ebfa, Word64
    0x70c026ffd1ebedaf,
     {- 220 -} Word64
    0xf8737b1b3237002f, Word64
    0x8afcbef3147e6e5e, Word64
    0x0e1bb0684483ebd3,
     {-     -} Word64
    0x4cbad70ae9b05aa6, Word64
    0xd4a31f523517c363,
     {- 225 -} Word64
    0xdb0f057ae8e9e8a2, Word64
    0x400894a919d89df6, Word64
    0x6a626a9b62defab3,
     {-     -} Word64
    0xf907fd7e14f4e201, Word64
    0xe10e4a5657c48f3f,
     {- 230 -} Word64
    0xb17f9f54b8e6e5dc, Word64
    0x6b9e69045fa6d27a, Word64
    0x8b74b6a41dc3078e,
     {-     -} Word64
    0x027954d45ca367f9, Word64
    0xd07207b8fdcbb7cc,
     {- 235 -} Word64
    0xf397c47d2f36414b, Word64
    0x05e4e8b11d3a034f, Word64
    0x36adb3f7122d654f,
     {-     -} Word64
    0x607d9540eb336078, Word64
    0xb639118e3a8b9600,
     {- 240 -} Word64
    0xd0a406770b5f1484, Word64
    0x3cbee8213ccfb7c6, Word64
    0x467967bb2ff89cf1,
     {-     -} Word64
    0xb115fe29609919a6, Word64
    0xba740e6ffa83287e,
     {- 245 -} Word64
    0xb4e51be9b694b7cd, Word64
    0xc9a081c677df5aea, Word64
    0x2e1fbcd8944508cc,
     {-     -} Word64
    0xf626e7895581fbb8, Word64
    0x3ce6e9b5728a05cb,
     {- 250 -} Word64
    0x46e87f2664a31712, Word64
    0x8c1dc526c2f6acfa, Word64
    0x7b4826726e560b10,
     {-     -} Word64
    0x2966e0099d8d7ce1, Word64
    0xbb0dd5240d2b2ade, Word64
    0x0d527cc60bbaa936
     ]

    h0, hT, hF :: Hash
    h0 :: Hash
    h0 = Word64 -> Hash
    Hash Word64
    0xe12398c6d9ae3b8a
    hT :: Hash
    hT = Word64 -> Hash
    Hash Word64
    0x851dcaa2656c6af4
    hF :: Hash
    hF = Word64 -> Hash
    Hash Word64
    0x1af84a6b589285f7