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