module Data.StableTree.Types.Key
( IsKey(..)
, Key(fromKey)
, SomeKey(..)
, Terminal
, Nonterminal
, wrap
, unwrap
, hashSerialize
, hashBinary
, hashByteString
) where
import qualified Data.ByteString.Lazy as Lazy
import qualified Data.ByteString as BS
import qualified Data.Serialize as S
import qualified Data.Binary as B
import Data.Bits ( (.&.), shiftR, xor )
import Data.ByteString ( ByteString )
import Data.Int ( Int8, Int16, Int32, Int64 )
import Data.Word ( Word, Word8, Word16, Word32, Word64 )
data Terminal
data Nonterminal
newtype Key t k = Key { fromKey :: k } deriving ( Eq, Ord, Show )
data SomeKey k = SomeKey_T (Key Terminal k)
| SomeKey_N (Key Nonterminal k)
deriving ( Eq, Ord, Show )
wrap :: IsKey k => k -> SomeKey k
wrap k =
let w8 = hash k
x = w8 `xor` (w8 `shiftR` 4)
w4 = x .&. 0xf
in if w4 == 0xf
then SomeKey_T $ Key k
else SomeKey_N $ Key k
unwrap :: SomeKey k -> k
unwrap (SomeKey_T (Key k)) = k
unwrap (SomeKey_N (Key k)) = k
hashSerialize :: S.Serialize t => t -> Word8
hashSerialize = hashByteString . S.encode
hashBinary :: B.Binary t => t -> Word8
hashBinary = hashByteString . Lazy.toStrict . B.encode
hashByteString :: ByteString -> Word8
hashByteString bs =
let fnv = fnv1a bs
w32 = fnv `xor` (fnv `shiftR` 32)
w16 = w32 `xor` (w32 `shiftR` 16)
w8 = w16 `xor` (w16 `shiftR` 8)
in toEnum $ fromEnum $ 0xff .&. w8
class IsKey k where
hash :: k -> Word8
instance IsKey Char where
hash = hashSerialize
instance IsKey Double where
hash = hashSerialize
instance IsKey Float where
hash = hashSerialize
instance IsKey Int where
hash = hashSerialize
instance IsKey Int8 where
hash = hashSerialize
instance IsKey Int16 where
hash = hashSerialize
instance IsKey Int32 where
hash = hashSerialize
instance IsKey Int64 where
hash = hashSerialize
instance IsKey Integer where
hash = hashSerialize
instance IsKey Word where
hash = hashSerialize
instance IsKey Word8 where
hash = hashSerialize
instance IsKey Word16 where
hash = hashSerialize
instance IsKey Word32 where
hash = hashSerialize
instance IsKey Word64 where
hash = hashSerialize
instance IsKey ByteString where
hash = hashByteString
instance IsKey Lazy.ByteString where
hash = hashByteString . Lazy.toStrict
fnv1a :: ByteString -> Word64
fnv1a = BS.foldl upd basis
where
upd hsh oct = prime * (hsh `xor` (toEnum $ fromEnum oct))
prime = 1099511628211
basis = 14695981039346656037