git.iko.soy/Idris-dev
on 7d42ba2 help sign in
Idris-dev/libs/base/Data/Hash.idr
87 lines 2.8 kB history raw
1module Data.Hash
3import Data.Vect
5%access public
6%default total
8{- A general purpose Hashing library (not cryptographic)
10 The core hash is djb2, which is very fast but does not have the best distribution
11 Source: http://www.cse.yorku.ca/~oz/hash.html
13 The salted version and the magic salt are copied from Haskell's bloomfilter library
14 Source: https://hackage.haskell.org/package/bloomfilter-2.0.0.0/docs/src/Data-BloomFilter-Hash.html#Hashable
15-}
17||| A type that can be hashed
18class Hashable a where
19 saltedHash64 : a -> Bits64 -> Bits64 -- value to hash, salt, hash
21||| Computes a non cryptographic hash
22hash : Hashable a => a -> Bits64
23hash x = saltedHash64 x 0x16fc397cf62f64d3
25||| Given a user provided salt, computes a non cryptographic hash.
26||| This version is meant to mitigate hash-flooding DoS attacks.
27saltedHash : Hashable a => Bits64 -> a -> Bits64
28saltedHash salt x = saltedHash64 x salt
31||| Nth byte of a Bits64
32private
33byte : Bits64 -> Bits64 -> Bits64
34byte n w = prim__lshrB64 (prim__andB64 mask w) offset
35 where offset = 8*n
36 mask = prim__shlB64 0xff (the Bits64 offset)
38||| Modulo of an integer, downsized to a Bits64
39private
40mod64 : Integer -> Bits64
41mod64 i = assert_total $ prim__truncBigInt_B64 (abs i `mod` 0xffffffffffffffff)
43instance Hashable Bits64 where
44 saltedHash64 w salt = foldr (\b,acc => (acc `prim__shlB64` 10) + acc + b)
45 salt
46 [byte (fromInteger n) w | n <- [7,6..0]] -- djb2 hash function. Not meant for crypto
48instance Hashable Integer where
49 saltedHash64 i = saltedHash64 (mod64 i)
51instance Hashable () where
52 saltedHash64 _ salt = salt
54instance Hashable Bool where
55 saltedHash64 True = saltedHash64 (the Bits64 1)
56 saltedHash64 False = saltedHash64 (the Bits64 0)
58instance Hashable Int where
59 saltedHash64 w = saltedHash64 (prim__zextInt_B64 w)
61instance Hashable Char where
62 saltedHash64 w = saltedHash64 (the Int (cast w))
64instance Hashable Bits8 where
65 saltedHash64 w = saltedHash64 (prim__zextB8_B64 w)
67instance Hashable Bits16 where
68 saltedHash64 w = saltedHash64 (prim__zextB16_B64 w)
70instance Hashable Bits32 where
71 saltedHash64 w = saltedHash64 (prim__zextB32_B64 w)
73instance Hashable a => Hashable (Maybe a) where
74 saltedHash64 Nothing salt = salt
75 saltedHash64 (Just k) salt = saltedHash64 k salt
77instance (Hashable a, Hashable b) => Hashable (a, b) where
78 saltedHash64 (a,b) salt = saltedHash64 b (saltedHash64 a salt)
80instance Hashable a => Hashable (List a) where
81 saltedHash64 l salt = foldr (\c,acc => saltedHash64 c acc) salt l
83instance Hashable a => Hashable (Vect n a) where
84 saltedHash64 l salt = foldr (\c,acc => saltedHash64 c acc) salt l
86instance Hashable String where
87 saltedHash64 s = saltedHash64 (unpack s)