ChibiHash 0.1.0.0 → 0.2.0.0
raw patch · 9 files changed
+391/−169 lines, 9 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
+ ChibiHash: chibihash64V1 :: ByteString -> Word64 -> Word64
+ ChibiHash: chibihash64V2 :: ByteString -> Word64 -> Word64
+ ChibiHash.V1: chibihash64 :: ByteString -> Word64 -> Word64
+ ChibiHash.V2: chibihash64 :: ByteString -> Word64 -> Word64
Files
- CHANGELOG.md +6/−0
- ChibiHash.cabal +4/−1
- LICENSE +1/−1
- README.md +8/−6
- example/Main.hs +9/−3
- src/ChibiHash.hs +22/−148
- src/ChibiHash/V1.hs +158/−0
- src/ChibiHash/V2.hs +158/−0
- test/ChibiHashSpec.hs +25/−10
CHANGELOG.md view
@@ -1,5 +1,11 @@ # Changelog for ChibiHash +## 0.2.0.0 -- 2024-12-02++* Added V2 implementation of ChibiHash - v1 still the default+* Module exports both v1 and v2, API is the same+* Added example usage to README+ ## 0.1.0.0 -- 2024-11-27 * First version.
ChibiHash.cabal view
@@ -1,5 +1,5 @@ name: ChibiHash-version: 0.1.0.0+version: 0.2.0.0 synopsis: a simple and fast 64-bit hash function description: Haskell port of ChibiHash, a simple and fast 64-bit hash function. .@@ -7,6 +7,7 @@ . * Fast 64-bit hashing * Suitable for hash tables and hash-based data structures+ * Supports both V1 and V2 implementations . For more information, see the article "ChibiHash: A small, fast 64-bit hash function" at https://nrk.neocities.org/articles/chibihash@@ -33,6 +34,8 @@ library exposed-modules: ChibiHash+ , ChibiHash.V1+ , ChibiHash.V2 hs-source-dirs: src build-depends: base >= 4.7 && < 5 , bytestring >= 0.10 && < 0.13
LICENSE view
@@ -1,6 +1,6 @@ MIT License -Copyright (c) 2024 [Your Name]+Copyright (c) 2024 Ville Vesilehto Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal
README.md view
@@ -1,5 +1,7 @@ # ChibiHash-hs +[<img alt="Hackage Version" src="https://img.shields.io/hackage/v/ChibiHash">](https://hackage.haskell.org/package/ChibiHash)+ Haskell port of [N-R-K/ChibiHash](https://github.com/N-R-K/ChibiHash). See the article [ChibiHash: A small, fast 64-bit hash function](https://nrk.neocities.org/articles/chibihash) for more information. All credit for the algorithm goes to [N-R-K](https://github.com/N-R-K).@@ -7,23 +9,23 @@ ## Usage ```haskell-module Main where+module Main (main) where import ChibiHash (chibihash64)-import qualified Data.ByteString as BS+import qualified Data.ByteString.Char8 as C8 main :: IO () main = do- let input = BS.pack [1,2,3,4]- let seed = 0- print $ chibihash64 input seed+ let text = "Hello, ChibiHash!"+ putStrLn $ "Input text: " ++ show text+ putStrLn $ "Hash (seed 0): " ++ show (chibihash64 (C8.pack text) 0) ``` You may also run the example program with `cabal run`. ## Tests -Run tests with `cabal test`.+Run tests with `cabal test`. Both v1 and v2 are tested. ## License
example/Main.hs view
@@ -1,6 +1,7 @@ module Main (main) where -import ChibiHash (chibihash64)+import ChibiHash (chibihash64) -- v1 by default+import qualified ChibiHash.V2 as V2 -- v2 explicitly import qualified Data.ByteString as BS import qualified Data.ByteString.Char8 as C8 @@ -17,6 +18,11 @@ let binary = BS.pack [1, 2, 3, 4, 5] putStrLn $ "Input bytes: " ++ show binary putStrLn $ "Hash (seed 0): " ++ show (chibihash64 binary 0)- + -- Example 3: Hash an empty string- putStrLn $ "\nHash of empty string: " ++ show (chibihash64 BS.empty 0) + putStrLn $ "\nHash of empty string: " ++ show (chibihash64 BS.empty 0)++ -- Example 4: Hash a string with ChibiHash v2+ let text2 = "Hello, ChibiHash!"+ putStrLn $ "\nInput text: " ++ show text2+ putStrLn $ "Hash (seed 0): " ++ show (V2.chibihash64 (C8.pack text2) 0)
src/ChibiHash.hs view
@@ -8,170 +8,44 @@ Portability : portable ChibiHash is a simple and fast 64-bit hash function suitable for hash tables and-hash-based data structures. This is a Haskell port of the original implementation-by [N-R-K](https://github.com/N-R-K) at [https://github.com/N-R-K/ChibiHash](https://github.com/N-R-K/ChibiHash).+hash-based data structures. This module provides both V1 and V2 implementations. Example usage: @-import ChibiHash (chibihash64)-import qualified Data.ByteString as BS+import ChibiHash (chibihash64) -- Uses V1 by default+import qualified ChibiHash.V2 as V2 main :: IO () main = do let input = BS.pack [1,2,3,4] let seed = 0- print $ chibihash64 input seed+ print $ chibihash64 input seed -- V1 hash+ print $ V2.chibihash64 input seed -- V2 hash @ -} module ChibiHash- ( -- * Hash Function- chibihash64- ) where--import Data.Word-import Data.Bits-import Data.List (unfoldr)-import Data.Int (Int64)-import qualified Data.ByteString as BS-import Data.ByteString (ByteString)+ ( -- * Hash Functions+ chibihash64 -- Default (V1 implementation)+ , chibihash64V1 -- Explicit V1 implementation+ , chibihash64V2 -- Explicit V2 implementation+ ) where --- | Prime-like constants used for mixing-p1, p2, p3 :: Word64-p1 = 0x2B7E151628AED2A5 -- Used in main block processing-p2 = 0x9E3793492EEDC3F7 -- Used in remaining bytes processing-p3 = 0x3243F6A8885A308D -- Used in 2-byte chunk processing+import qualified ChibiHash.V1 as V1+import qualified ChibiHash.V2 as V2 --- | Convert 8 bytes into a Word64 using little-endian ordering--- Each byte is shifted left by its position (0, 8, 16, ...) and combined-load64le :: [Word8] -> Word64-load64le bytes = foldr (\(pos, b) acc -> acc .|. (fromIntegral b `shiftL` pos))- 0- (zip [0,8..] (take 8 bytes))+import Data.ByteString (ByteString)+import Data.Word (Word64) --- | Main hash function that processes input in several stages:--- 1. Process full 32-byte blocks--- 2. Process remaining bytes (< 32 bytes)--- 3. Apply final mixing function+-- | Hash a ByteString with the default (V1) implementation chibihash64 :: ByteString -> Word64 -> Word64-chibihash64 input seed = finalMix x- where- bytes = BS.unpack input- len = fromIntegral $ BS.length input-- -- Initial state- h0 = [p1, p2, p3, seed]-- -- Process full 32-byte blocks- (h1, remaining) = processBlocks bytes h0-- -- Process remaining bytes- h2 = processRemaining remaining len h1-- -- Final mixing- (ha', hb', hc', hd') = case h2 of- [a, b, c, d] -> (a, b, c, d)- _ -> error "Impossible: hash state must contain exactly 4 elements"-- x = seed -- Start with seed- `xor` (ha' * ((hc' `shiftR` 32) .|. 1))- `xor` (hb' * ((hd' `shiftR` 32) .|. 1))- `xor` (hc' * ((ha' `shiftR` 32) .|. 1))- `xor` (hd' * ((hb' `shiftR` 32) .|. 1))---- | Process input in 32-byte blocks (4 lanes of 8 bytes each)--- Returns the updated hash state and any remaining bytes-processBlocks :: [Word8] -> [Word64] -> ([Word64], [Word8])-processBlocks input h- | length input < 32 = (h, input) -- Not enough bytes for a full block- | otherwise = - let (block, rest) = splitAt 32 input- h' = processBlock block h- in processBlocks rest h'- where- -- Process each 8-byte lane within the 32-byte block- processBlock block hashState =- foldl processLane hashState (zip [0..3] (chunksOf 8 block))- -- Process a single 8-byte lane:- -- 1. Load 8 bytes as Word64- -- 2. XOR with current state and multiply- -- 3. Update next state with rotated value- processLane hashState (i, lane) =- let v = load64le lane- hi = hashState !! i- hi' = (hi `xor` v) * p1 -- Mix current lane- nextIdx = (i + 1) .&. 3 -- Circular index for next lane- next = (v `shiftL` 40) .|. (v `shiftR` 24) -- Rotate input by 40 bits- h' = take i hashState ++ [hi'] ++ drop (i + 1) hashState -- Update current lane- h'' = take nextIdx h' ++ [h' !! nextIdx `xor` next] ++ drop (nextIdx + 1) h' -- Update next lane- in h''---- | Process remaining bytes that didn't fill a complete 32-byte block--- Handles:--- 1. Length mixing into first hash value--- 2. Single odd byte (if present)--- 3. Remaining 8-byte chunks--- 4. Final 2-byte chunks-processRemaining :: [Word8] -> Int64 -> [Word64] -> [Word64]-processRemaining bytes len _state@[a, b, c, d] =- let -- First add length mix to h[0]- ha' = a + ((fromIntegral len `shiftL` 32) .|. (fromIntegral len `shiftR` 32))-- -- Handle single byte if length is odd- (ha'', bytes', len') = if not (null bytes) && (length bytes .&. 1) == 1- then (ha' `xor` fromIntegral (head bytes), tail bytes, length bytes - 1)- else (ha', bytes, length bytes)-- -- Multiply and shift h[0]- ha''' = ha'' * p2- ha4 = ha''' `xor` (ha''' `shiftR` 31)-- -- Process 8-byte chunks into h[1], h[2], h[3]- h1 = process8ByteChunks bytes' 1 [ha4, b, c, d]-- -- Process remaining 2-byte chunks- h2 = process2ByteChunks (drop (len' .&. complement 7) bytes') 0 h1- in h2-processRemaining _ _ _ = error "Unexpected state: processRemaining requires exactly 4 elements in the state"---- | Process 8-byte chunks into h[1], h[2], h[3]-process8ByteChunks :: [Word8] -> Int -> [Word64] -> [Word64]-process8ByteChunks bs i h- | length bs >= 8 && i < 4 =- let v = load64le bs- hi = h !! i- hi' = hi `xor` v- hi'' = hi' * p2- hi''' = hi'' `xor` (hi'' `shiftR` 31)- h' = take i h ++ [hi'''] ++ drop (i + 1) h- in process8ByteChunks (drop 8 bs) (i + 1) h'- | otherwise = h---- | Process remaining 2-byte chunks-process2ByteChunks :: [Word8] -> Int -> [Word64] -> [Word64]-process2ByteChunks bs i h- | length bs >= 2 =- let v = fromIntegral (head bs) .|. (fromIntegral (bs !! 1) `shiftL` 8)- hi = h !! i- hi' = hi `xor` v- hi'' = hi' * p3- hi''' = hi'' `xor` (hi'' `shiftR` 31)- h' = take i h ++ [hi'''] ++ drop (i + 1) h- in process2ByteChunks (drop 2 bs) ((i + 1) .&. 3) h'- | otherwise = h+chibihash64 = V1.chibihash64 --- | Final mixing function to improve avalanche effect--- Applies a series of xor, shift, and multiply operations-finalMix :: Word64 -> Word64-finalMix x = x3- where- -- Each step: XOR with right shift, then multiply by a large prime- x1 = (x `xor` (x `shiftR` 27)) * 0x3C79AC492BA7B653- x2 = (x1 `xor` (x1 `shiftR` 33)) * 0x1C69B3F74AC4AE35- x3 = x2 `xor` (x2 `shiftR` 27)+-- | Hash a ByteString with the V1 implementation+chibihash64V1 :: ByteString -> Word64 -> Word64+chibihash64V1 = V1.chibihash64 --- | Split a list into chunks of size n--- Used to break input into 8-byte lanes-chunksOf :: Int -> [a] -> [[a]]-chunksOf n = takeWhile (not . null) . unfoldr (Just . splitAt n)+-- | Hash a ByteString with the V2 implementation+chibihash64V2 :: ByteString -> Word64 -> Word64+chibihash64V2 = V2.chibihash64
+ src/ChibiHash/V1.hs view
@@ -0,0 +1,158 @@+{-| V1 implementation of ChibiHash++ This is a 64-bit non-cryptographic hash function optimized for:++ - Fast performance on short strings+ - Good distribution of hash values+ - Simple implementation with no lookup tables+-}++module ChibiHash.V1+ ( chibihash64+ ) where++import Data.Word+import Data.Bits+import Data.List (unfoldr)+import Data.Int (Int64)+import qualified Data.ByteString as BS+import Data.ByteString (ByteString)++-- | Prime-like constants used for mixing+p1, p2, p3 :: Word64+p1 = 0x2B7E151628AED2A5 -- Used in main block processing+p2 = 0x9E3793492EEDC3F7 -- Used in remaining bytes processing+p3 = 0x3243F6A8885A308D -- Used in 2-byte chunk processing++-- | Convert 8 bytes into a Word64 using little-endian ordering+-- Each byte is shifted left by its position (0, 8, 16, ...) and combined+load64le :: [Word8] -> Word64+load64le bytes = foldr (\(pos, b) acc -> acc .|. (fromIntegral b `shiftL` pos))+ 0+ (zip [0,8..] (take 8 bytes))++-- | Main hash function that processes input in several stages:+-- 1. Process full 32-byte blocks+-- 2. Process remaining bytes (< 32 bytes)+-- 3. Apply final mixing function+chibihash64 :: ByteString -> Word64 -> Word64+chibihash64 input seed = finalMix x+ where+ bytes = BS.unpack input+ len = fromIntegral $ BS.length input++ -- Initial state+ h0 = [p1, p2, p3, seed]++ -- Process full 32-byte blocks+ (h1, remaining) = processBlocks bytes h0++ -- Process remaining bytes+ h2 = processRemaining remaining len h1++ -- Final mixing+ (ha', hb', hc', hd') = case h2 of+ [a, b, c, d] -> (a, b, c, d)+ _ -> error "Impossible: hash state must contain exactly 4 elements"++ x = seed -- Start with seed+ `xor` (ha' * ((hc' `shiftR` 32) .|. 1))+ `xor` (hb' * ((hd' `shiftR` 32) .|. 1))+ `xor` (hc' * ((ha' `shiftR` 32) .|. 1))+ `xor` (hd' * ((hb' `shiftR` 32) .|. 1))++-- | Process input in 32-byte blocks (4 lanes of 8 bytes each)+-- Returns the updated hash state and any remaining bytes+processBlocks :: [Word8] -> [Word64] -> ([Word64], [Word8])+processBlocks input h+ | length input < 32 = (h, input) -- Not enough bytes for a full block+ | otherwise = + let (block, rest) = splitAt 32 input+ h' = processBlock block h+ in processBlocks rest h'+ where+ -- Process each 8-byte lane within the 32-byte block+ processBlock block hashState =+ foldl processLane hashState (zip [0..3] (chunksOf 8 block))+ -- Process a single 8-byte lane:+ -- 1. Load 8 bytes as Word64+ -- 2. XOR with current state and multiply+ -- 3. Update next state with rotated value+ processLane hashState (i, lane) =+ let v = load64le lane+ hi = hashState !! i+ hi' = (hi `xor` v) * p1 -- Mix current lane+ nextIdx = (i + 1) .&. 3 -- Circular index for next lane+ next = (v `shiftL` 40) .|. (v `shiftR` 24) -- Rotate input by 40 bits+ h' = take i hashState ++ [hi'] ++ drop (i + 1) hashState -- Update current lane+ h'' = take nextIdx h' ++ [h' !! nextIdx `xor` next] ++ drop (nextIdx + 1) h' -- Update next lane+ in h''++-- | Process remaining bytes that didn't fill a complete 32-byte block+-- Handles:+-- 1. Length mixing into first hash value+-- 2. Single odd byte (if present)+-- 3. Remaining 8-byte chunks+-- 4. Final 2-byte chunks+processRemaining :: [Word8] -> Int64 -> [Word64] -> [Word64]+processRemaining bytes len _state@[a, b, c, d] =+ let -- First add length mix to h[0]+ ha' = a + ((fromIntegral len `shiftL` 32) .|. (fromIntegral len `shiftR` 32))++ -- Handle single byte if length is odd+ (ha'', bytes', len') = if not (null bytes) && (length bytes .&. 1) == 1+ then (ha' `xor` fromIntegral (head bytes), tail bytes, length bytes - 1)+ else (ha', bytes, length bytes)++ -- Multiply and shift h[0]+ ha''' = ha'' * p2+ ha4 = ha''' `xor` (ha''' `shiftR` 31)++ -- Process 8-byte chunks into h[1], h[2], h[3]+ h1 = process8ByteChunks bytes' 1 [ha4, b, c, d]++ -- Process remaining 2-byte chunks+ h2 = process2ByteChunks (drop (len' .&. complement 7) bytes') 0 h1+ in h2+processRemaining _ _ _ = error "Unexpected state: processRemaining requires exactly 4 elements in the state"++-- | Process 8-byte chunks into h[1], h[2], h[3]+process8ByteChunks :: [Word8] -> Int -> [Word64] -> [Word64]+process8ByteChunks bs i h+ | length bs >= 8 && i < 4 =+ let v = load64le bs+ hi = h !! i+ hi' = hi `xor` v+ hi'' = hi' * p2+ hi''' = hi'' `xor` (hi'' `shiftR` 31)+ h' = take i h ++ [hi'''] ++ drop (i + 1) h+ in process8ByteChunks (drop 8 bs) (i + 1) h'+ | otherwise = h++-- | Process remaining 2-byte chunks+process2ByteChunks :: [Word8] -> Int -> [Word64] -> [Word64]+process2ByteChunks bs i h+ | length bs >= 2 =+ let v = fromIntegral (head bs) .|. (fromIntegral (bs !! 1) `shiftL` 8)+ hi = h !! i+ hi' = hi `xor` v+ hi'' = hi' * p3+ hi''' = hi'' `xor` (hi'' `shiftR` 31)+ h' = take i h ++ [hi'''] ++ drop (i + 1) h+ in process2ByteChunks (drop 2 bs) ((i + 1) .&. 3) h'+ | otherwise = h++-- | Final mixing function to improve avalanche effect+-- Applies a series of xor, shift, and multiply operations+finalMix :: Word64 -> Word64+finalMix x = x3+ where+ -- Each step: XOR with right shift, then multiply by a large prime+ x1 = (x `xor` (x `shiftR` 27)) * 0x3C79AC492BA7B653+ x2 = (x1 `xor` (x1 `shiftR` 33)) * 0x1C69B3F74AC4AE35+ x3 = x2 `xor` (x2 `shiftR` 27)++-- | Split a list into chunks of size n+-- Used to break input into 8-byte lanes+chunksOf :: Int -> [a] -> [[a]]+chunksOf n = takeWhile (not . null) . unfoldr (Just . splitAt n)
+ src/ChibiHash/V2.hs view
@@ -0,0 +1,158 @@+{-| V2 implementation of ChibiHash ++ This is a 64-bit non-cryptographic hash function optimized for:+ - Fast performance on short strings+ - Good distribution of hash values+ - Simple implementation with no lookup tables++ Version 2 improvements over V1, from the original C implementation:++ - Faster performance on short strings (42 cycles/hash vs 34 cycles/hash)+ - Improved seeding that affects all 256 bits of internal state+ - Better mixing in bulk data processing+ - Passes all 252 tests in smhasher3 (commit 34093a3), v1 failed 3.++-}+module ChibiHash.V2+ ( chibihash64+ ) where++import Data.Word+import Data.Bits+import Data.ByteString (ByteString)+import qualified Data.ByteString as BS++-- | Prime-like constant used for mixing, derived from digits of e+k :: Word64+k = 0x2B7E151628AED2A7++-- | Convert bytes to Word64 using little-endian ordering+-- Takes 8 bytes and combines them into a single 64-bit word+load64le :: [Word8] -> Word64+load64le bytes = + let lo = load32le bytes+ hi = load32le (drop 4 bytes)+ in lo .|. (hi `shiftL` 32)++-- | Convert bytes to Word32 using little-endian ordering+-- Takes 4 bytes and combines them into the lower 32 bits of a Word64+load32le :: [Word8] -> Word64+load32le bytes = + let b0 = fromIntegral (head bytes)+ b1 = fromIntegral (bytes !! 1) `shiftL` 8+ b2 = fromIntegral (bytes !! 2) `shiftL` 16+ b3 = fromIntegral (bytes !! 3) `shiftL` 24+ in b0 .|. b1 .|. b2 .|. b3++-- | Basic arithmetic operations used throughout the hash function+add, subtract, mul :: Word64 -> Word64 -> Word64+add a b = a + b+subtract a b = a - b+mul a b = a * b++-- | Main hash function for V2+-- Takes a ByteString input and 64-bit seed value+-- Returns a 64-bit hash value+chibihash64 :: ByteString -> Word64 -> Word64+chibihash64 input seed = + let bytes = BS.unpack input+ len = fromIntegral (BS.length input) :: Word64++ -- Initialize state with seed-dependent values+ seed2 = ((seed `ChibiHash.V2.subtract` k) `rotateL` 15) `add` + ((seed `ChibiHash.V2.subtract` k) `rotateL` 47)++ h0 = [ seed+ , seed `add` k+ , seed2+ , seed2 `add` ((k `mul` k) `xor` k)+ ]++ -- Process input in stages+ (h1, remaining) = processBlocks bytes h0 -- Process 32-byte blocks+ h2 = processRemaining remaining (length remaining) h1 -- Handle remaining bytes++ in case h2 of+ [ha, hb, hc, hd] -> + let -- Final mixing steps+ h_final_0 = ha `add` ((hc `mul` k) `rotateL` 31 `xor` (hc `shiftR` 31))+ h_final_1 = hb `add` ((hd `mul` k) `rotateL` 31 `xor` (hd `shiftR` 31))+ h_final_0' = h_final_0 `mul` k+ h_final_0'' = h_final_0' `xor` (h_final_0' `shiftR` 31)+ h_final_1' = h_final_1 `add` h_final_0''++ -- Length-dependent mixing+ x = len `mul` k+ x' = x `xor` (x `rotateL` 29)+ x'' = x' `add` seed+ x''' = x'' `xor` h_final_1'+ x'''' = x''' `xor` (x''' `rotateL` 15) `xor` (x''' `rotateL` 42)+ x''''' = x'''' `mul` k+ final = x''''' `xor` (x''''' `rotateL` 13) `xor` (x''''' `rotateL` 31)+ in final+ _ -> error "Invalid state: processRemaining must return 4 values"++-- | Process input in 32-byte blocks+-- Each block is split into four 8-byte stripes+processBlocks :: [Word8] -> [Word64] -> ([Word64], [Word8])+processBlocks input h+ | length input < 32 = (h, input)+ | otherwise =+ let (block, rest) = splitAt 32 input+ stripes = chunksOf 8 block+ h' = foldl (\acc (i, s) -> processStripe (acc, i, s)) + h + (zip [0..3] stripes)+ in processBlocks rest h'++-- | Process an 8-byte stripe within a block+-- Updates the 4-element state array based on stripe index+processStripe :: ([Word64], Int, [Word8]) -> [Word64]+processStripe (state, i, stripe) | i >= 0 && i < 4 =+ let v = load64le stripe+ hi' = (v `add` (state !! i)) `mul` k+ nextIdx = (i + 1) .&. 3+ next = (state !! nextIdx) `add` (v `rotateL` 27)+ in case i of+ 0 -> [hi', next, state !! 2, state !! 3]+ 1 -> [head state, hi', next, state !! 3]+ 2 -> [head state, state !! 1, hi', next]+ 3 -> [next, state !! 1, state !! 2, hi']+ _ -> error "Invalid index"+processStripe _ = error "Invalid state: expected 4 hash values"++-- | Process remaining bytes after block processing+-- Handles different cases based on number of remaining bytes:+-- - 8 or more bytes: process in 8-byte chunks+-- - 4-7 bytes: special handling with two 32-bit reads+-- - 1-3 bytes: special handling for very short remainders+processRemaining :: [Word8] -> Int -> [Word64] -> [Word64]+processRemaining bytes len state@[ha, hb, hc, hd]+ | len >= 8 = + let (chunk, rest) = splitAt 8 bytes+ ha' = ha `xor` load32le chunk+ ha'' = ha' `mul` k+ hb' = hb `xor` load32le (drop 4 chunk)+ hb'' = hb' `mul` k+ remaining_len = len - 8+ in processRemaining rest remaining_len [ha'', hb'', hc, hd]+ | len >= 4 = + let hc' = hc `xor` load32le bytes+ hd' = hd `xor` load32le (drop (len - 4) bytes)+ in [ha, hb, hc', hd']+ | len > 0 = + let hc' = hc `xor` fromIntegral (head bytes)+ mid_byte = fromIntegral (bytes !! (len `div` 2))+ last_byte = fromIntegral (last bytes) `shiftL` 8+ hd' = hd `xor` (mid_byte .|. last_byte)+ in [ha, hb, hc', hd']+ | otherwise = state+processRemaining _ _ _ = error "Invalid state"++-- | Split a list into chunks of specified size+chunksOf :: Int -> [a] -> [[a]]+chunksOf n = takeWhile (not . null) . unfoldr (Just . splitAt n)+ where+ unfoldr f x = case f x of+ Just (y, ys) -> y : unfoldr f ys+ Nothing -> []
test/ChibiHashSpec.hs view
@@ -1,26 +1,41 @@ module ChibiHashSpec (spec) where import Test.Hspec-import ChibiHash (chibihash64)+import qualified ChibiHash.V1 as V1+import qualified ChibiHash.V2 as V2 import Data.ByteString.Char8 (pack) + spec :: Spec spec = describe "ChibiHash" $ do- describe "chibihash64" $ do+ describe "V1.chibihash64" $ do it "handles empty string" $ do- chibihash64 (pack "") 0 `shouldBe` 0x9EA80F3B18E26CFB- chibihash64 (pack "") 55555 `shouldBe` 0x2EED9399FC4AC7E5+ V1.chibihash64 (pack "") 0 `shouldBe` 0x9EA80F3B18E26CFB+ V1.chibihash64 (pack "") 55555 `shouldBe` 0x2EED9399FC4AC7E5 it "handles short strings" $ do- chibihash64 (pack "hi") 0 `shouldBe` 0xAF98F3924F5C80D6- chibihash64 (pack "123") 0 `shouldBe` 0x893A5CCA05B0A883- chibihash64 (pack "abcdefgh") 0 `shouldBe` 0x8F922660063E3E75- chibihash64 (pack "Hello, world!") 0 `shouldBe` 0x5AF920D8C0EBFE9F+ V1.chibihash64 (pack "hi") 0 `shouldBe` 0xAF98F3924F5C80D6+ V1.chibihash64 (pack "123") 0 `shouldBe` 0x893A5CCA05B0A883+ V1.chibihash64 (pack "abcdefgh") 0 `shouldBe` 0x8F922660063E3E75+ V1.chibihash64 (pack "Hello, world!") 0 `shouldBe` 0x5AF920D8C0EBFE9F it "handles exactly 32-byte string" $ do- chibihash64 (pack "qwertyuiopasdfghjklzxcvbnm123456") 0+ V1.chibihash64 (pack "qwertyuiopasdfghjklzxcvbnm123456") 0 `shouldBe` 0x2EF296DB634F6551 it "handles string longer than 32 bytes" $ do- chibihash64 (pack "qwertyuiopasdfghjklzxcvbnm123456789") 0+ V1.chibihash64 (pack "qwertyuiopasdfghjklzxcvbnm123456789") 0 `shouldBe` 0x0F56CF3735FFA943++ describe "V2.chibihash64" $ do+ it "matches Rust implementation test vectors" $ do+ V2.chibihash64 (pack "") 55555 `shouldBe` 0x58AEE94CA9FB5092+ V2.chibihash64 (pack "") 0 `shouldBe` 0xD4F69E3ECCF128FC+ V2.chibihash64 (pack "hi") 0 `shouldBe` 0x92C85CA994367DAC+ V2.chibihash64 (pack "123") 0 `shouldBe` 0x788A224711FF6E25+ V2.chibihash64 (pack "abcdefgh") 0 `shouldBe` 0xA2E39BE0A0689B32+ V2.chibihash64 (pack "Hello, world!") 0 `shouldBe` 0xABF8EB3100B2FEC7+ V2.chibihash64 (pack "qwertyuiopasdfghjklzxcvbnm123456") 0 + `shouldBe` 0x90FC5DB7F56967FA+ V2.chibihash64 (pack "qwertyuiopasdfghjklzxcvbnm123456789") 0 + `shouldBe` 0x6DCDCE02882A4975