data-hash 0.1.0.0 → 0.2.0.1
raw patch · 8 files changed
Files
- AUTHORS +3/−0
- Setup.lhs +1/−1
- data-hash.cabal +19/−5
- src/Data/Hash.hs +4/−1
- src/Data/Hash/Base.hs +5/−6
- src/Data/Hash/Instances.hs +0/−1
- src/Data/Hash/Rolling.hs +90/−0
- tests/Main.hs +57/−0
+ AUTHORS view
@@ -0,0 +1,3 @@+Daniel Gorin++The Rolling hash implementation was contributed by Boris Sukholitko.
Setup.lhs view
@@ -2,4 +2,4 @@ > module Main where > import Distribution.Simple > main :: IO ()-> main = defaultMainWithHooks defaultUserHooks+> main = defaultMain
data-hash.cabal view
@@ -1,5 +1,5 @@ name: data-hash-version: 0.1.0.0+version: 0.2.0.1 description: Combinators for building fast hashing functions. Includes hashing functions for all basic Haskell98 types.@@ -10,18 +10,32 @@ license: BSD3 license-file: LICENSE maintainer: jcpetruzza@gmail.com-homepage: http://code.haskell.org/~jcpetruzza/data-hash -cabal-version: >= 1.2+cabal-version: >= 1.8 build-type: Simple tested-with: GHC==6.10 +extra-source-files: AUTHORS++source-repository head+ type: darcs+ location: http://hub.darcs.net/jcpetruzza/data-hash+ Library- build-depends: base >= 3, array+ build-depends: base >= 3 && <= 5, array, containers ghc-options: -Wall -O2 hs-source-dirs: src - exposed-modules: Data.Hash+ exposed-modules: Data.Hash, Data.Hash.Rolling other-modules: Data.Hash.Base, Data.Hash.Instances extensions: CPP+++test-suite Main+ type: exitcode-stdio-1.0+ x-uses-tf: true+ build-depends: base, QuickCheck, test-framework, test-framework-quickcheck2, data-hash+ ghc-options: -Wall+ hs-source-dirs: tests+ main-is: Main.hs
src/Data/Hash.hs view
@@ -21,9 +21,12 @@ hashWord16, hashWord32, hashWord64, hashInt, hashStorable, hashFoldable, -- * The @Hashable@ class- Hashable(..) )+ Hashable(..),+ -- * Rolling hashes+ module Data.Hash.Rolling ) where import Data.Hash.Base import Data.Hash.Instances+import Data.Hash.Rolling
src/Data/Hash/Base.hs view
@@ -1,11 +1,10 @@-module Data.Hash.Base ( Hash, asWord64, combine,- hashWord8, hashWord16, hashWord32, hashWord64, hashInt,- hashStorable,- h0, hT, hF )-where+module Data.Hash.Base where import Data.Array-import Foreign+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 )
src/Data/Hash/Instances.hs view
@@ -7,7 +7,6 @@ import Data.Word import Data.Int import Data.Ratio-import Data.Char import Data.Foldable class Hashable a where
+ src/Data/Hash/Rolling.hs view
@@ -0,0 +1,90 @@+------------------------------------------------------------------------------+-- |+-- Module : Data.Hash.Rolling+-- License : BSD-style+--+-- Maintainer : jcpetruzza@gmail.com+-- Stability : experimental+-- Portability : portable+--+-- Efficient implementation of a rolling hash, i.e., the computation of a hash through+-- a moving window of a fixed size @n@ over some stream. All operations are O(1) (in+-- particular, they do not depend on the size of the window).+--+-- Some laws that this type satisfies:+--+-- * @currentHash rh == foldl1 combine (lastHashes rh)@+--+-- * @length (lastHashes rh) <= windowSize rh@+--+-- * @length (lastHashes $ addAndRoll rh a) == windowSize rh -- whenever length (lastHashes rh) == windowSize rh@+--+-- * @last (lastHashes $ addAndRoll rh x) == hash a@+--+-- * @init (lastHashes $ addAndRoll rh a) `isSuffixOf` (lastHashes rh)@+-------------------------------------------------------------------------------+module Data.Hash.Rolling (+ -- * The @RollingHash@ type+ RollingHash,+ -- ** Construction and manipulation+ rollingHash, addAndRoll,+ -- ** Querying+ currentHash, lastHashes, windowSize+)++where++import Data.Hash.Base+import Data.Hash.Instances+import Data.Bits+import qualified Data.Sequence as S+import Data.Foldable+import Text.Show.Functions ()+++data RollingHash a = RH {+ currentHash :: Hash+ ,windowSize :: Int+ ,hseq :: S.Seq Hash+ ,addHashImpl :: RollingHash a -> Hash -> RollingHash a+ } deriving Show++-- | @rollingHash n@ creates a @RollingHash@ of window+-- size @n@ (for @n > 0@)+rollingHash :: Int -> RollingHash a+rollingHash n+ | n == 0 = error $ "rollingHash: invalid window size " ++ show n+ | otherwise = RH {+ currentHash = initial_hash+ ,windowSize = n+ ,hseq = S.singleton initial_hash+ ,addHashImpl = accumulateNext (n - 1)+ }+ where initial_hash = hash () `combine` hash n++defaultAddHash :: RollingHash a -> Hash -> RollingHash a+defaultAddHash rh hv = rh { currentHash = (currentHash rh) `combine` (Hash $ rotate c1 k `xor` ck)+ , hseq = (S.drop 1 $ hseq rh) S.|> hv+ }+ where ck = asWord64 hv+ c1 = asWord64 $ S.index (hseq rh) 0+ k = S.length $ hseq rh+++-- | @addAndRoll x rh@ adds a new input element and rolls the window+-- one place through the input (if at least @n@ elements were+-- already consumed).+addAndRoll :: Hashable a => RollingHash a -> a -> RollingHash a+addAndRoll r a = (addHashImpl r) r (hash a)++accumulateNext :: Int -> RollingHash a -> Hash -> RollingHash a+accumulateNext n | n > 0 = \rh h -> rh {+ currentHash = currentHash rh `combine` h,+ hseq = (hseq rh) S.|> h,+ addHashImpl = accumulateNext (n - 1)+ }+ | otherwise = defaultAddHash++-- | @lastHashes rh@ returns the last @n@ hashes.+lastHashes :: RollingHash a -> [Hash]+lastHashes = toList . hseq
+ tests/Main.hs view
@@ -0,0 +1,57 @@+module Main where++import Control.Applicative+import Test.QuickCheck+import Data.List++import Test.Framework as TF (defaultMain, testGroup, Test)+import Test.Framework.Providers.QuickCheck2 (testProperty)+import Data.Hash++main :: IO ()+main = defaultMain tests++instance (Arbitrary a, Hashable a) => Arbitrary (RollingHash a) where+ arbitrary = do Positive n <- arbitrary+ foldl' addAndRoll (rollingHash n) <$> (arbitrary :: Arbitrary a => Gen [a])++foldH :: [Int] -> Hash+foldH (i:xs) = foldl combine (hash i) $ map hash xs+foldH _ = error "Cannot happen"++rhArr :: Int -> [Int] -> RollingHash Int+rhArr x xs = foldl addAndRoll (rollingHash (length (x:xs))) (x:xs)++prop_cycle :: Int -> [Int] -> Bool+prop_cycle x xs = (currentHash rh) == (currentHash $ foldl addAndRoll rh $ x:x:xs)+ where rh = rhArr x xs++prop_curr :: RollingHash Int -> Bool+prop_curr rh = currentHash rh == foldl1' combine (lastHashes rh)++prop_len1 :: RollingHash Int -> Bool+prop_len1 rh = length (lastHashes rh) <= windowSize rh++prop_len2 :: RollingHash Int -> Int -> Bool+prop_len2 rh x+ | length (lastHashes rh) == n = length (lastHashes $ addAndRoll rh x) == n+ | otherwise = length (lastHashes $ addAndRoll rh x) == length (lastHashes rh) + 1+ where n = windowSize rh++prop_last :: RollingHash Int -> Int -> Bool+prop_last rh x = last (lastHashes $ addAndRoll rh x) == hash x++prop_suff :: RollingHash Int -> Int -> Bool+prop_suff rh x = init (lastHashes $ addAndRoll rh x) `isSuffixOf` (lastHashes rh)+++tests :: [TF.Test]+tests = [ testGroup "QuickCheck tests" [+ testProperty "curr" prop_curr+ , testProperty "len1" prop_len1+ , testProperty "len2" prop_len2+ , testProperty "last" prop_last+ , testProperty "suff" prop_suff+ , testProperty "cycle" prop_cycle+ ]+ ]