rapidhash (empty) → 0.1.0.0
raw patch · 18 files changed
+2593/−0 lines, 18 filesdep +aesondep +basedep +binary
Dependencies added: aeson, base, binary, bytestring, bytestring-lexing, deepseq, doctest-parallel, hashable, hedgehog, murmur-hash, primitive, rapidhash, tasty, tasty-bench, tasty-hedgehog, tasty-hunit, text, text-builder-linear, vector, xxhash-ffi
Files
- CHANGELOG.md +19/−0
- LICENSE +29/−0
- LICENSE_rapidhash +19/−0
- README.md +218/−0
- bench/Bench.hs +71/−0
- cbits/rapidhash.h +571/−0
- cbits/rapidhash_ext.h +26/−0
- doctest/Doctest.hs +7/−0
- rapidhash.cabal +240/−0
- src/Data/Hash/RapidHash.hs +105/−0
- src/Data/Hash/RapidHash/Aeson.hs +36/−0
- src/Data/Hash/RapidHash/Class.hs +137/−0
- src/Data/Hash/RapidHash/FFI.hs +194/−0
- src/Data/Hash/RapidHash/Types.hs +364/−0
- test/Driver.hs +1/−0
- test/RapidHashTest.hs +105/−0
- test/pin/pin.c +67/−0
- test/pin/rapidhash-v3-pin.txt +384/−0
+ CHANGELOG.md view
@@ -0,0 +1,19 @@+# Changelog — rapidhash++## 0.1.0.0 - 2026-07-26++Initial release.++- FFI bindings to rapidhash v3, vendored at upstream commit `5c62c4b` and+ shipped in the sdist (`cbits/rapidhash.h`, `cbits/rapidhash_ext.h`).+- `RapidHashable` with zero-copy instances for strict `ByteString`,+ `ShortByteString`, `Text`, `ByteArray`, `PrimArray`, and+ primitive/storable `Vector`.+- Self-describing tagged textual digests (`rhv3:` followed by 16 hex digits)+ with parsers, a `text-builder-linear` builder, and `Show`/`Read`/`Binary`+ instances.+- Optional `ToJSON`/`FromJSON` and `ToJSONKey`/`FromJSONKey` instances behind+ flag `aeson` (keys use the same tagged hex form as values).+- A `Hashable` instance for `RapidHash` itself, so a digest works directly as a+ `HashMap`/`HashSet` key.+- `HashViaRapidHash` for deriving `Hashable` via rapidhash.
+ LICENSE view
@@ -0,0 +1,29 @@+Copyright (c) 2026 Jeremy Nuttall++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are+met:++ * Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.++ * Redistributions in binary form must reproduce the above+ copyright notice, this list of conditions and the following+ disclaimer in the documentation and/or other materials provided+ with the distribution.++ * Neither the name of Jeremy Nuttall nor the names of other+ contributors may be used to endorse or promote products derived+ from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ LICENSE_rapidhash view
@@ -0,0 +1,19 @@+Copyright 2025 Nicolas De Carli++Permission is hereby granted, free of charge, to any person obtaining a copy+of this software and associated documentation files (the "Software"), to deal+in the Software without restriction, including without limitation the rights+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell+copies of the Software, and to permit persons to whom the Software is+furnished to do so, subject to the following conditions:++The above copyright notice and this permission notice shall be included in all+copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE+SOFTWARE.
+ README.md view
@@ -0,0 +1,218 @@+# rapidhash++Haskell bindings to [rapidhash](https://github.com/Nicoshev/rapidhash) v3 –+a very fast, high-quality, platform-independent hash.++Like `xxhash-ffi` and `murmur-hash`, this package provides a stable hash+that can be safely persisted for types with a stable byte representation+(e.g., `ByteString`, `Text`); see [supported input types](#supported-input-types).++This library appears to outperform `xxhash-ffi`, `murmur-hash`, and `hashable` by+a reasonable margin in [microbenchmarks](#benchmarks).++Upstream claims wins over every major noncryptographic hashing algorithm on+performance; on quality, it [passes both SMHasher and SMHasher3](https://github.com/Nicoshev/rapidhash/tree/master#collision-based-hash-quality-study).+Your mileage may vary.++**This is not a cryptographically secure hash. Use something else if+you need cryptographic security.**++## Example++```haskell+{-# LANGUAGE OverloadedStrings #-}+{-# LANGUAGE TypeApplications #-}++import Data.Text (Text)+import Data.Hash.RapidHash (RapidHash, rapidhash)++digest :: RapidHash+digest = rapidhash @Text "hello, world"++main :: IO ()+main = print digest+```++`rapidhashWithSeed` takes an explicit `RapidSeed` if you need one. To use+rapidhash as your `Hashable` implementation, derive through+`HashViaRapidHash`:++```haskell+newtype ContentKey = ContentKey ByteString+ deriving newtype (Eq, RapidHashable)+ deriving (Hashable) via HashViaRapidHash ContentKey+```++## Status++First release, but I consider the API stable. Used for change detection in+[lithon](https://github.com/jtnuttall/lithon).++This project follows the PVP. For stability, pin to the major (e.g., `^>= 0.1`).++### Streaming++Right now, this library supports only a strict block hash: the whole input+must be in memory. (`rapidhashFile` handles the common file case — a+strict read, then one hash.)++rapidhash v3 was rewritten to be streamable: its block functions can be+driven incrementally as long as the caller threads the hash state itself+(the Rust port does exactly this). This binding does not yet expose that+stateful API; I'll add it when the need arises. If you need streaming+before then, feel free to open an issue or PR against the project repository.++## Serialization and deserialization++`RapidHash` serializes and deserializes as a self-describing tagged hex+string — for example, `rhv3:0123456789abcdef`. This reduces the likelihood+that stored digests get confused with the output of other hash algorithms,+or of future rapidhash versions.++The convention applies to every mechanism that produces string output:+`Show`/`Read`, the `Text`/`ByteString` renderers and parsers, and the+`text-builder-linear` builder. (`Binary` instead uses a compact tagged+9-byte encoding.)++The `RapidHash` constructor is exported wholesale; if the tagging doesn't+fit your needs, rewrap the underlying `Word64` however you like.++### Aeson++Efficient `Aeson.ToJSON`/`FromJSON` and `Aeson.ToJSONKey`/`FromJSONKey`+instances are provided behind flag `aeson`; map keys use the same tagged+hex form as values. To use these, add:++cabal.project:++```cabal+package rapidhash+ flags: +aeson+```++stack.yaml:++```yaml+flags:+ rapidhash:+ aeson: true+```++## Supported input types++This library only supports strict types that can be passed to C with zero+allocations. Right now, that is:++- `Data.Text.Text`+- `Data.ByteString.ByteString`+- `Data.ByteString.Short.ShortByteString`+- `Data.Array.Byte.ByteArray`+- `Data.Primitive.PrimArray`+- `Data.Vector.Storable.Vector`+- `Data.Vector.Primitive.Vector`++The byte-oriented instances (`Text`, `ByteString`, `ShortByteString`,+`ByteArray`) produce the same digest on every platform. The element-typed+instances (`PrimArray` and both `Vector`s) hash the underlying memory raw,+so their digests depend on word width and endianness — do not persist+those across platforms. Each instance's haddock says which kind it is, and+the `Storable` vector instance carries an additional warning about padding.++A lazy/streaming API is not provided; see [streaming](#streaming).++## Benchmarks++Measured with `tasty-bench` on a 13th-gen Intel i7-1370P (GHC 9.12.4, NCG,+default flags for every package, meaning what `cabal build` gives you;+your numbers will vary).++Inputs are built once and forced before timing, so payload allocation is not+measured. Reproduce with:++```sh+cabal bench rapidhash-bench --benchmark-options='--csv bench.csv --stdev 2'+```++### Results++> [!NOTE]+>+> 1. The same inputs are fed to every hasher.+> 2. Strict `Text` is only benchmarked for libraries with native `Text` support.+> 3. Lower is better; fastest library is **bold** on each row.++#### Strict `ByteString`++| Input | rapidhash | xxh3 (`xxhash-ffi`) | `hashable` | murmur2 (`murmur-hash`) |+| ------ | ---------: | ------------------: | ---------: | ----------------------: |+| 8 B | 4.8 ns | 6.8 ns | **4.1 ns** | 8.1 ns |+| 64 B | **6.0 ns** | 8.3 ns | 9.9 ns | 107 ns |+| 1 KiB | **25 ns** | 60 ns | 55 ns | 2.0 μs |+| 64 KiB | **1.3 μs** | 3.1 μs | 3.0 μs | 129 μs |+| 1 MiB | **21 μs** | 50 μs | 52 μs | 2.2 ms |++#### Strict `Text`++| Input | rapidhash | xxh3 (`xxhash-ffi`) | `hashable` |+| ------ | ---------: | ------------------: | ---------: |+| 8 B | **3.5 ns** | 9.4 ns | 4.8 ns |+| 64 B | **4.5 ns** | 10.5 ns | 10 ns |+| 1 KiB | **24 ns** | 66 ns | 62 ns |+| 64 KiB | **1.4 μs** | 3.2 μs | 3.2 μs |+| 1 MiB | **23 μs** | 57 μs | 51 μs |++#### Notes++- `hashable` is the most straightforward baseline. Its `ByteString`/`Text`+ hashers are presently C calls, both to xxhash3[^1]. It is presented for+ speed comparison against a known-optimized hasher.+- rapidhash measures meaningfully faster than `hashable`, except at very+ small inputs, where it seems to pay more in constant factors.+- `murmur-hash` is pure Haskell (MurmurHash2).+- `xxhash-ffi` is measured through its `XXH3` newtype `Hashable` instance.+- [Upstream reports](https://github.com/Nicoshev/rapidhash/tree/master#outstanding-performance)+ \~47-71 GB/s for rapidhash across M1 Pro-M4/Ryzen 9700X. This library+ measures \~46-50 GB/s at the 64 KiB-1 MiB sizes on a laptop CPU, which+ seats it neatly within range.++## Compilation++This library is a thin FFI binding to the upstream single-header C+implementation, vendored and shipped in the sdist, which means this+library should compile anywhere there is a compliant C compiler.++Compilation issues are mine, not rapidhash's; please report any such+issues in [the repository for this Haskell package](https://github.com/jtnuttall/lithon/issues).++### Optimizations++Given that this library is small and rapidhash's performance is contingent+on compiler optimizations, the `optimize` flag defaults to on: `-O2` for+GHC, `-O3` for the C compiler. Disable it by passing `-f -optimize` to Cabal.++A second flag, `llvm-bench`, rebuilds the benchmarks with GHC's LLVM backend+so its effect can be measured; it needs an LLVM toolchain matching your GHC,+and GHC >= 9.10. At this time I do not believe the library's performance to be+substantially altered by LLVM compilation, and the implementation is plenty fast+enough on the NCG for my purposes.++## Technical notes++### Verification++- The library is parity-tested against 384 known-answer vectors, which are+ generated by a C program that uses the rapidhash header directly.+- Property tests check that every supported input representation hashes its+ underlying bytes identically.++### Performance and safety++- The hashing algorithm is pure and does not modify its input, so the FFI+ call is wrapped in `unsafeDupablePerformIO`, the cheapest option that+ is safe here.+- Zero-copy FFI is trivial for types that wrap a `ForeignPtr`.+- Types that wrap an unsliced `ByteArray` go directly through `UnliftedFFITypes`.+- Types that wrap a sliced `ByteArray` (offset + length) go through a small+ C shim in `cbits/rapidhash_ext.h`, again with `UnliftedFFITypes`.++[^1]: Implementations for [ByteString](https://hackage-content.haskell.org/package/hashable-1.5.1.0/docs/src/Data.Hashable.Class.html#line-578) and [Text](https://hackage-content.haskell.org/package/hashable-1.5.1.0/docs/src/Data.Hashable.Class.html#line-622) as of writing.
+ bench/Bench.hs view
@@ -0,0 +1,71 @@+{-# LANGUAGE OverloadedStrings #-}++-- |+-- Comparative benchmarks for rapidhash.+--+-- Methodology notes:+--+-- * The ByteString group is the canonical comparison: every hasher+-- consumes exactly the same bytes. The Text group only includes hashers+-- with native Text support.+-- * @hashable@ is a familiar throughput baseline, but it is not a stable+-- digest intended for persistence. It is here to compare relative speed only.+-- At present, its ByteString/Text paths are calls to the C implementation of xxhash3.+-- * @murmur-hash@ is a pure-Haskell implementation (MurmurHash2, 64-bit).+--+-- Run:+--+-- > cabal bench rapidhash-bench --benchmark-options='--csv bench.csv --stdev 2'+module Main (main) where++import Data.ByteString (ByteString)+import Data.ByteString qualified as BS+import Data.Digest.Murmur64 (asWord64, hash64)+import Data.Digest.XXHash.FFI (XXH3 (XXH3))+import Data.Hashable (hash)+import Data.Text (Text)+import Data.Text qualified as T+import Test.Tasty.Bench (Benchmark, bench, bgroup, defaultMain, env, whnf)++import Data.Hash.RapidHash (rapidhash)++sizes :: [Int]+sizes = [8, 64, 1024, 64 * 1024, 1024 * 1024]++sizeLabel :: Int -> String+sizeLabel n+ | n < 1024 = show n <> "B"+ | n < 1024 * 1024 = show (n `div` 1024) <> "KiB"+ | otherwise = show (n `div` (1024 * 1024)) <> "MiB"++mkBS :: Int -> ByteString+mkBS n = BS.pack [fromIntegral (i * 167 + 13) | i <- [0 .. n - 1]]++mkText :: Int -> Text+mkText n = T.pack (take n (cycle ['a' .. 'z']))++byteStringBench :: Int -> Benchmark+byteStringBench n = env (pure (mkBS n)) \bs ->+ bgroup+ (sizeLabel n)+ [ bench "rapidhash" $ whnf rapidhash bs+ , bench "xxh3 (xxhash-ffi)" $ whnf (hash . XXH3) bs+ , bench "hashable" $ whnf hash bs+ , bench "murmur2 (murmur-hash)" $ whnf (asWord64 . hash64) bs+ ]++textBench :: Int -> Benchmark+textBench n = env (pure (mkText n)) \t ->+ bgroup+ (sizeLabel n)+ [ bench "rapidhash" $ whnf rapidhash t+ , bench "xxh3 (xxhash-ffi)" $ whnf (hash . XXH3) t+ , bench "hashable" $ whnf hash t+ ]++main :: IO ()+main =+ defaultMain+ [ bgroup "ByteString" (map byteStringBench sizes)+ , bgroup "Text" (map textBench sizes)+ ]
+ cbits/rapidhash.h view
@@ -0,0 +1,571 @@+/* + * NOTE: This file is pulled from rapidhash v3. + * permalink: https://raw.githubusercontent.com/Nicoshev/rapidhash/5c62c4b3352c7d4c87ed3429d2329ddaf9b74df9/rapidhash.h + * + * rapidhash V3 - Very fast, high quality, platform-independent hashing algorithm. + * + * Based on 'wyhash', by Wang Yi <godspeed_china@yeah.net> + * + * Copyright (C) 2025 Nicolas De Carli + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + * + * You can contact the author at: + * - rapidhash source repository: https://github.com/Nicoshev/rapidhash + */ + + #pragma once + +/* + * Includes. + */ + #include <stdint.h> + #include <string.h> + #if defined(_MSC_VER) + # include <intrin.h> + # if defined(_M_X64) && !defined(_M_ARM64EC) + # pragma intrinsic(_umul128) + # endif + #endif + + /* + * C/C++ macros. + */ + + #ifdef _MSC_VER + # define RAPIDHASH_ALWAYS_INLINE __forceinline + #elif defined(__GNUC__) + # define RAPIDHASH_ALWAYS_INLINE inline __attribute__((__always_inline__)) + #else + # define RAPIDHASH_ALWAYS_INLINE inline + #endif + + #ifdef __cplusplus + # define RAPIDHASH_NOEXCEPT noexcept + # define RAPIDHASH_CONSTEXPR constexpr + # ifndef RAPIDHASH_INLINE + # define RAPIDHASH_INLINE RAPIDHASH_ALWAYS_INLINE + # endif + # if __cplusplus >= 201402L && !defined(_MSC_VER) + # define RAPIDHASH_INLINE_CONSTEXPR RAPIDHASH_ALWAYS_INLINE constexpr + # else + # define RAPIDHASH_INLINE_CONSTEXPR RAPIDHASH_ALWAYS_INLINE + # endif + #else + # define RAPIDHASH_NOEXCEPT + # define RAPIDHASH_CONSTEXPR static const + # ifndef RAPIDHASH_INLINE + # define RAPIDHASH_INLINE static RAPIDHASH_ALWAYS_INLINE + # endif + # define RAPIDHASH_INLINE_CONSTEXPR RAPIDHASH_INLINE + #endif + + /* + * Unrolled macro. + * Improves large input speed, but increases code size and worsens small input speed. + * + * RAPIDHASH_COMPACT: Normal behavior. + * RAPIDHASH_UNROLLED: + * + */ + #ifndef RAPIDHASH_UNROLLED + # define RAPIDHASH_COMPACT + #elif defined(RAPIDHASH_COMPACT) + # error "cannot define RAPIDHASH_COMPACT and RAPIDHASH_UNROLLED simultaneously." + #endif + + /* + * Protection macro, alters behaviour of rapid_mum multiplication function. + * + * RAPIDHASH_FAST: Normal behavior, max speed. + * RAPIDHASH_PROTECTED: Extra protection against entropy loss. + */ + #ifndef RAPIDHASH_PROTECTED + # define RAPIDHASH_FAST + #elif defined(RAPIDHASH_FAST) + # error "cannot define RAPIDHASH_PROTECTED and RAPIDHASH_FAST simultaneously." + #endif + + /* + * Likely and unlikely macros. + */ + #if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__) + # define _likely_(x) __builtin_expect(x,1) + # define _unlikely_(x) __builtin_expect(x,0) + #else + # define _likely_(x) (x) + # define _unlikely_(x) (x) + #endif + + /* + * Endianness macros. + */ + #ifndef RAPIDHASH_LITTLE_ENDIAN + # if defined(_WIN32) || defined(__LITTLE_ENDIAN__) || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) + # define RAPIDHASH_LITTLE_ENDIAN + # elif defined(__BIG_ENDIAN__) || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__) + # define RAPIDHASH_BIG_ENDIAN + # else + # warning "could not determine endianness! Falling back to little endian." + # define RAPIDHASH_LITTLE_ENDIAN + # endif + #endif + + /* + * Default secret parameters. + */ + RAPIDHASH_CONSTEXPR uint64_t rapid_secret[8] = { + 0x2d358dccaa6c78a5ull, + 0x8bb84b93962eacc9ull, + 0x4b33a62ed433d4a3ull, + 0x4d5a2da51de1aa47ull, + 0xa0761d6478bd642full, + 0xe7037ed1a0b428dbull, + 0x90ed1765281c388cull, + 0xaaaaaaaaaaaaaaaaull}; + + /* + * 64*64 -> 128bit multiply function. + * + * @param A Address of 64-bit number. + * @param B Address of 64-bit number. + * + * Calculates 128-bit C = *A * *B. + * + * When RAPIDHASH_FAST is defined: + * Overwrites A contents with C's low 64 bits. + * Overwrites B contents with C's high 64 bits. + * + * When RAPIDHASH_PROTECTED is defined: + * Xors and overwrites A contents with C's low 64 bits. + * Xors and overwrites B contents with C's high 64 bits. + */ + RAPIDHASH_INLINE_CONSTEXPR void rapid_mum(uint64_t *A, uint64_t *B) RAPIDHASH_NOEXCEPT { + #if defined(__SIZEOF_INT128__) + __uint128_t r=*A; r*=*B; + #ifdef RAPIDHASH_PROTECTED + *A^=(uint64_t)r; *B^=(uint64_t)(r>>64); + #else + *A=(uint64_t)r; *B=(uint64_t)(r>>64); + #endif + #elif defined(_MSC_VER) && (defined(_WIN64) || defined(_M_HYBRID_CHPE_ARM64)) + #if defined(_M_X64) + #ifdef RAPIDHASH_PROTECTED + uint64_t a, b; + a=_umul128(*A,*B,&b); + *A^=a; *B^=b; + #else + *A=_umul128(*A,*B,B); + #endif + #else + #ifdef RAPIDHASH_PROTECTED + uint64_t a, b; + b = __umulh(*A, *B); + a = *A * *B; + *A^=a; *B^=b; + #else + uint64_t c = __umulh(*A, *B); + *A = *A * *B; + *B = c; + #endif + #endif + #else + uint64_t ha=*A>>32, hb=*B>>32, la=(uint32_t)*A, lb=(uint32_t)*B; + uint64_t rh=ha*hb, rm0=ha*lb, rm1=hb*la, rl=la*lb, t=rl+(rm0<<32), c=t<rl; + uint64_t lo=t+(rm1<<32); + c+=lo<t; + uint64_t hi=rh+(rm0>>32)+(rm1>>32)+c; + #ifdef RAPIDHASH_PROTECTED + *A^=lo; *B^=hi; + #else + *A=lo; *B=hi; + #endif + #endif + } + + /* + * Multiply and xor mix function. + * + * @param A 64-bit number. + * @param B 64-bit number. + * + * Calculates 128-bit C = A * B. + * Returns 64-bit xor between high and low 64 bits of C. + */ + RAPIDHASH_INLINE_CONSTEXPR uint64_t rapid_mix(uint64_t A, uint64_t B) RAPIDHASH_NOEXCEPT { rapid_mum(&A,&B); return A^B; } + + /* + * Read functions. + */ + #ifdef RAPIDHASH_LITTLE_ENDIAN + RAPIDHASH_INLINE uint64_t rapid_read64(const uint8_t *p) RAPIDHASH_NOEXCEPT { uint64_t v; memcpy(&v, p, sizeof(uint64_t)); return v;} + RAPIDHASH_INLINE uint64_t rapid_read32(const uint8_t *p) RAPIDHASH_NOEXCEPT { uint32_t v; memcpy(&v, p, sizeof(uint32_t)); return v;} + #elif defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__) + RAPIDHASH_INLINE uint64_t rapid_read64(const uint8_t *p) RAPIDHASH_NOEXCEPT { uint64_t v; memcpy(&v, p, sizeof(uint64_t)); return __builtin_bswap64(v);} + RAPIDHASH_INLINE uint64_t rapid_read32(const uint8_t *p) RAPIDHASH_NOEXCEPT { uint32_t v; memcpy(&v, p, sizeof(uint32_t)); return __builtin_bswap32(v);} + #elif defined(_MSC_VER) + RAPIDHASH_INLINE uint64_t rapid_read64(const uint8_t *p) RAPIDHASH_NOEXCEPT { uint64_t v; memcpy(&v, p, sizeof(uint64_t)); return _byteswap_uint64(v);} + RAPIDHASH_INLINE uint64_t rapid_read32(const uint8_t *p) RAPIDHASH_NOEXCEPT { uint32_t v; memcpy(&v, p, sizeof(uint32_t)); return _byteswap_ulong(v);} + #else + RAPIDHASH_INLINE uint64_t rapid_read64(const uint8_t *p) RAPIDHASH_NOEXCEPT { + uint64_t v; memcpy(&v, p, 8); + return (((v >> 56) & 0xff)| ((v >> 40) & 0xff00)| ((v >> 24) & 0xff0000)| ((v >> 8) & 0xff000000)| ((v << 8) & 0xff00000000)| ((v << 24) & 0xff0000000000)| ((v << 40) & 0xff000000000000)| ((v << 56) & 0xff00000000000000)); + } + RAPIDHASH_INLINE uint64_t rapid_read32(const uint8_t *p) RAPIDHASH_NOEXCEPT { + uint32_t v; memcpy(&v, p, 4); + return (((v >> 24) & 0xff)| ((v >> 8) & 0xff00)| ((v << 8) & 0xff0000)| ((v << 24) & 0xff000000)); + } + #endif + + /* + * rapidhash main function. + * + * @param key Buffer to be hashed. + * @param len @key length, in bytes. + * @param seed 64-bit seed used to alter the hash result predictably. + * @param secret Triplet of 64-bit secrets used to alter hash result predictably. + * + * Returns a 64-bit hash. + */ +RAPIDHASH_INLINE_CONSTEXPR uint64_t rapidhash_internal(const void *key, size_t len, uint64_t seed, const uint64_t* secret) RAPIDHASH_NOEXCEPT { + const uint8_t *p=(const uint8_t *)key; + seed ^= rapid_mix(seed ^ secret[2], secret[1]); + uint64_t a=0, b=0; + size_t i = len; + if (_likely_(len <= 16)) { + if (len >= 4) { + seed ^= len; + if (len >= 8) { + const uint8_t* plast = p + len - 8; + a = rapid_read64(p); + b = rapid_read64(plast); + } else { + const uint8_t* plast = p + len - 4; + a = rapid_read32(p); + b = rapid_read32(plast); + } + } else if (len > 0) { + a = (((uint64_t)p[0])<<45)|p[len-1]; + b = p[len>>1]; + } else + a = b = 0; + } else { + if (len > 112) { + uint64_t see1 = seed, see2 = seed; + uint64_t see3 = seed, see4 = seed; + uint64_t see5 = seed, see6 = seed; +#ifdef RAPIDHASH_COMPACT + do { + seed = rapid_mix(rapid_read64(p) ^ secret[0], rapid_read64(p + 8) ^ seed); + see1 = rapid_mix(rapid_read64(p + 16) ^ secret[1], rapid_read64(p + 24) ^ see1); + see2 = rapid_mix(rapid_read64(p + 32) ^ secret[2], rapid_read64(p + 40) ^ see2); + see3 = rapid_mix(rapid_read64(p + 48) ^ secret[3], rapid_read64(p + 56) ^ see3); + see4 = rapid_mix(rapid_read64(p + 64) ^ secret[4], rapid_read64(p + 72) ^ see4); + see5 = rapid_mix(rapid_read64(p + 80) ^ secret[5], rapid_read64(p + 88) ^ see5); + see6 = rapid_mix(rapid_read64(p + 96) ^ secret[6], rapid_read64(p + 104) ^ see6); + p += 112; + i -= 112; + } while(i > 112); +#else + while (i > 224) { + seed = rapid_mix(rapid_read64(p) ^ secret[0], rapid_read64(p + 8) ^ seed); + see1 = rapid_mix(rapid_read64(p + 16) ^ secret[1], rapid_read64(p + 24) ^ see1); + see2 = rapid_mix(rapid_read64(p + 32) ^ secret[2], rapid_read64(p + 40) ^ see2); + see3 = rapid_mix(rapid_read64(p + 48) ^ secret[3], rapid_read64(p + 56) ^ see3); + see4 = rapid_mix(rapid_read64(p + 64) ^ secret[4], rapid_read64(p + 72) ^ see4); + see5 = rapid_mix(rapid_read64(p + 80) ^ secret[5], rapid_read64(p + 88) ^ see5); + see6 = rapid_mix(rapid_read64(p + 96) ^ secret[6], rapid_read64(p + 104) ^ see6); + seed = rapid_mix(rapid_read64(p + 112) ^ secret[0], rapid_read64(p + 120) ^ seed); + see1 = rapid_mix(rapid_read64(p + 128) ^ secret[1], rapid_read64(p + 136) ^ see1); + see2 = rapid_mix(rapid_read64(p + 144) ^ secret[2], rapid_read64(p + 152) ^ see2); + see3 = rapid_mix(rapid_read64(p + 160) ^ secret[3], rapid_read64(p + 168) ^ see3); + see4 = rapid_mix(rapid_read64(p + 176) ^ secret[4], rapid_read64(p + 184) ^ see4); + see5 = rapid_mix(rapid_read64(p + 192) ^ secret[5], rapid_read64(p + 200) ^ see5); + see6 = rapid_mix(rapid_read64(p + 208) ^ secret[6], rapid_read64(p + 216) ^ see6); + p += 224; + i -= 224; + } + if (i > 112) { + seed = rapid_mix(rapid_read64(p) ^ secret[0], rapid_read64(p + 8) ^ seed); + see1 = rapid_mix(rapid_read64(p + 16) ^ secret[1], rapid_read64(p + 24) ^ see1); + see2 = rapid_mix(rapid_read64(p + 32) ^ secret[2], rapid_read64(p + 40) ^ see2); + see3 = rapid_mix(rapid_read64(p + 48) ^ secret[3], rapid_read64(p + 56) ^ see3); + see4 = rapid_mix(rapid_read64(p + 64) ^ secret[4], rapid_read64(p + 72) ^ see4); + see5 = rapid_mix(rapid_read64(p + 80) ^ secret[5], rapid_read64(p + 88) ^ see5); + see6 = rapid_mix(rapid_read64(p + 96) ^ secret[6], rapid_read64(p + 104) ^ see6); + p += 112; + i -= 112; + } +#endif + seed ^= see1; + see2 ^= see3; + see4 ^= see5; + seed ^= see6; + see2 ^= see4; + seed ^= see2; + } + if (i > 16) { + seed = rapid_mix(rapid_read64(p) ^ secret[2], rapid_read64(p + 8) ^ seed); + if (i > 32) { + seed = rapid_mix(rapid_read64(p + 16) ^ secret[2], rapid_read64(p + 24) ^ seed); + if (i > 48) { + seed = rapid_mix(rapid_read64(p + 32) ^ secret[1], rapid_read64(p + 40) ^ seed); + if (i > 64) { + seed = rapid_mix(rapid_read64(p + 48) ^ secret[1], rapid_read64(p + 56) ^ seed); + if (i > 80) { + seed = rapid_mix(rapid_read64(p + 64) ^ secret[2], rapid_read64(p + 72) ^ seed); + if (i > 96) { + seed = rapid_mix(rapid_read64(p + 80) ^ secret[1], rapid_read64(p + 88) ^ seed); + } + } + } + } + } + } + a=rapid_read64(p+i-16) ^ i; b=rapid_read64(p+i-8); + } + a ^= secret[1]; + b ^= seed; + rapid_mum(&a, &b); + return rapid_mix(a ^ secret[7], b ^ secret[1] ^ i); +} + + /* + * rapidhashMicro main function. + * + * @param key Buffer to be hashed. + * @param len @key length, in bytes. + * @param seed 64-bit seed used to alter the hash result predictably. + * @param secret Triplet of 64-bit secrets used to alter hash result predictably. + * + * Returns a 64-bit hash. + */ + RAPIDHASH_INLINE_CONSTEXPR uint64_t rapidhashMicro_internal(const void *key, size_t len, uint64_t seed, const uint64_t* secret) RAPIDHASH_NOEXCEPT { + const uint8_t *p=(const uint8_t *)key; + seed ^= rapid_mix(seed ^ secret[2], secret[1]); + uint64_t a=0, b=0; + size_t i = len; + if (_likely_(len <= 16)) { + if (len >= 4) { + seed ^= len; + if (len >= 8) { + const uint8_t* plast = p + len - 8; + a = rapid_read64(p); + b = rapid_read64(plast); + } else { + const uint8_t* plast = p + len - 4; + a = rapid_read32(p); + b = rapid_read32(plast); + } + } else if (len > 0) { + a = (((uint64_t)p[0])<<45)|p[len-1]; + b = p[len>>1]; + } else + a = b = 0; + } else { + if (i > 80) { + uint64_t see1 = seed, see2 = seed; + uint64_t see3 = seed, see4 = seed; + do { + seed = rapid_mix(rapid_read64(p) ^ secret[0], rapid_read64(p + 8) ^ seed); + see1 = rapid_mix(rapid_read64(p + 16) ^ secret[1], rapid_read64(p + 24) ^ see1); + see2 = rapid_mix(rapid_read64(p + 32) ^ secret[2], rapid_read64(p + 40) ^ see2); + see3 = rapid_mix(rapid_read64(p + 48) ^ secret[3], rapid_read64(p + 56) ^ see3); + see4 = rapid_mix(rapid_read64(p + 64) ^ secret[4], rapid_read64(p + 72) ^ see4); + p += 80; + i -= 80; + } while(i > 80); + seed ^= see1; + see2 ^= see3; + seed ^= see4; + seed ^= see2; + } + if (i > 16) { + seed = rapid_mix(rapid_read64(p) ^ secret[2], rapid_read64(p + 8) ^ seed); + if (i > 32) { + seed = rapid_mix(rapid_read64(p + 16) ^ secret[2], rapid_read64(p + 24) ^ seed); + if (i > 48) { + seed = rapid_mix(rapid_read64(p + 32) ^ secret[1], rapid_read64(p + 40) ^ seed); + if (i > 64) { + seed = rapid_mix(rapid_read64(p + 48) ^ secret[1], rapid_read64(p + 56) ^ seed); + } + } + } + } + a=rapid_read64(p+i-16) ^ i; b=rapid_read64(p+i-8); + } + a ^= secret[1]; + b ^= seed; + rapid_mum(&a, &b); + return rapid_mix(a ^ secret[7], b ^ secret[1] ^ i); + } + + /* + * rapidhashNano main function. + * + * @param key Buffer to be hashed. + * @param len @key length, in bytes. + * @param seed 64-bit seed used to alter the hash result predictably. + * @param secret Triplet of 64-bit secrets used to alter hash result predictably. + * + * Returns a 64-bit hash. + */ + RAPIDHASH_INLINE_CONSTEXPR uint64_t rapidhashNano_internal(const void *key, size_t len, uint64_t seed, const uint64_t* secret) RAPIDHASH_NOEXCEPT { + const uint8_t *p=(const uint8_t *)key; + seed ^= rapid_mix(seed ^ secret[2], secret[1]); + uint64_t a=0, b=0; + size_t i = len; + if (_likely_(len <= 16)) { + if (len >= 4) { + seed ^= len; + if (len >= 8) { + const uint8_t* plast = p + len - 8; + a = rapid_read64(p); + b = rapid_read64(plast); + } else { + const uint8_t* plast = p + len - 4; + a = rapid_read32(p); + b = rapid_read32(plast); + } + } else if (len > 0) { + a = (((uint64_t)p[0])<<45)|p[len-1]; + b = p[len>>1]; + } else + a = b = 0; + } else { + if (i > 48) { + uint64_t see1 = seed, see2 = seed; + do { + seed = rapid_mix(rapid_read64(p) ^ secret[0], rapid_read64(p + 8) ^ seed); + see1 = rapid_mix(rapid_read64(p + 16) ^ secret[1], rapid_read64(p + 24) ^ see1); + see2 = rapid_mix(rapid_read64(p + 32) ^ secret[2], rapid_read64(p + 40) ^ see2); + p += 48; + i -= 48; + } while(i > 48); + seed ^= see1; + seed ^= see2; + } + if (i > 16) { + seed = rapid_mix(rapid_read64(p) ^ secret[2], rapid_read64(p + 8) ^ seed); + if (i > 32) { + seed = rapid_mix(rapid_read64(p + 16) ^ secret[2], rapid_read64(p + 24) ^ seed); + } + } + a=rapid_read64(p+i-16) ^ i; b=rapid_read64(p+i-8); + } + a ^= secret[1]; + b ^= seed; + rapid_mum(&a, &b); + return rapid_mix(a ^ secret[7], b ^ secret[1] ^ i); + } + +/* + * rapidhash seeded hash function. + * + * @param key Buffer to be hashed. + * @param len @key length, in bytes. + * @param seed 64-bit seed used to alter the hash result predictably. + * + * Calls rapidhash_internal using provided parameters and default secrets. + * + * Returns a 64-bit hash. + */ +RAPIDHASH_INLINE_CONSTEXPR uint64_t rapidhash_withSeed(const void *key, size_t len, uint64_t seed) RAPIDHASH_NOEXCEPT { + return rapidhash_internal(key, len, seed, rapid_secret); +} + +/* + * rapidhash general purpose hash function. + * + * @param key Buffer to be hashed. + * @param len @key length, in bytes. + * + * Calls rapidhash_withSeed using provided parameters and the default seed. + * + * Returns a 64-bit hash. + */ +RAPIDHASH_INLINE_CONSTEXPR uint64_t rapidhash(const void *key, size_t len) RAPIDHASH_NOEXCEPT { + return rapidhash_withSeed(key, len, 0); +} + +/* + * rapidhashMicro seeded hash function. + * + * Designed for HPC and server applications, where cache misses make a noticeable performance detriment. + * Clang-18+ compiles it to ~140 instructions without stack usage, both on x86-64 and aarch64. + * Faster for sizes up to 512 bytes, just 15%-20% slower for inputs above 1kb. + * + * @param key Buffer to be hashed. + * @param len @key length, in bytes. + * @param seed 64-bit seed used to alter the hash result predictably. + * + * Calls rapidhash_internal using provided parameters and default secrets. + * + * Returns a 64-bit hash. + */ + RAPIDHASH_INLINE_CONSTEXPR uint64_t rapidhashMicro_withSeed(const void *key, size_t len, uint64_t seed) RAPIDHASH_NOEXCEPT { + return rapidhashMicro_internal(key, len, seed, rapid_secret); +} + +/* + * rapidhashMicro hash function. + * + * @param key Buffer to be hashed. + * @param len @key length, in bytes. + * + * Calls rapidhash_withSeed using provided parameters and the default seed. + * + * Returns a 64-bit hash. + */ +RAPIDHASH_INLINE_CONSTEXPR uint64_t rapidhashMicro(const void *key, size_t len) RAPIDHASH_NOEXCEPT { + return rapidhashMicro_withSeed(key, len, 0); +} + +/* + * rapidhashNano seeded hash function. + * + * @param key Buffer to be hashed. + * @param len @key length, in bytes. + * @param seed 64-bit seed used to alter the hash result predictably. + * + * Calls rapidhash_internal using provided parameters and default secrets. + * + * Returns a 64-bit hash. + */ + RAPIDHASH_INLINE_CONSTEXPR uint64_t rapidhashNano_withSeed(const void *key, size_t len, uint64_t seed) RAPIDHASH_NOEXCEPT { + return rapidhashNano_internal(key, len, seed, rapid_secret); +} + +/* + * rapidhashNano hash function. + * + * Designed for Mobile and embedded applications, where keeping a small code size is a top priority. + * Clang-18+ compiles it to less than 100 instructions without stack usage, both on x86-64 and aarch64. + * The fastest for sizes up to 48 bytes, but may be considerably slower for larger inputs. + * + * @param key Buffer to be hashed. + * @param len @key length, in bytes. + * + * Calls rapidhash_withSeed using provided parameters and the default seed. + * + * Returns a 64-bit hash. + */ +RAPIDHASH_INLINE_CONSTEXPR uint64_t rapidhashNano(const void *key, size_t len) RAPIDHASH_NOEXCEPT { + return rapidhashNano_withSeed(key, len, 0); +}
+ cbits/rapidhash_ext.h view
@@ -0,0 +1,26 @@+// Small extensions to rapidhash so that, for example, zero-cost Text+// manipulation is possible.+#pragma once++#include "rapidhash.h"+#include <stddef.h>+#include <stdint.h>++/*+ * rapidhash seeded hash function.+ *+ * @param key Buffer to be hashed.+ * @param offset Offset into the buffer, in bytes.+ * @param len @key length, in bytes.+ * @param seed 64-bit seed used to alter the hash result predictably.+ *+ * Calls rapidhash_internal using provided parameters and default secrets.+ *+ * Returns a 64-bit hash.+ */+RAPIDHASH_INLINE uint64_t+rapidhash_offset_withSeed(const void *key, size_t offset, size_t len,+ uint64_t seed) RAPIDHASH_NOEXCEPT {+ return rapidhash_internal((const uint8_t *)key + offset, len, seed,+ rapid_secret);+}
+ doctest/Doctest.hs view
@@ -0,0 +1,7 @@+module Main (main) where++import System.Environment (getArgs)+import Test.DocTest (mainFromCabal)++main :: IO ()+main = mainFromCabal "rapidhash" =<< getArgs
+ rapidhash.cabal view
@@ -0,0 +1,240 @@+cabal-version: 2.2++-- This file has been generated from package.yaml by hpack version 0.39.6.+--+-- see: https://github.com/sol/hpack++name: rapidhash+version: 0.1.0.0+synopsis: rapidhash v3 - very fast, high-quality, non-cryptographic hashing+description: Zero-copy FFI bindings to rapidhash v3, a very fast, high-quality,+ non-cryptographic hash. The upstream single-header C implementation is+ vendored and ships with this package, so there is no system dependency.+ .+ The rapidhash algorithm itself is platform-independent. This package's+ byte-oriented instances (Text, ByteString, ShortByteString, ByteArray)+ produce stable, portable digests you can persist and compare across+ machines; the element-typed Vector and PrimArray instances hash raw memory+ as a fast path for large in-memory working sets and are not portable across+ word width or endianness.+ .+ This is not a cryptographically secure hash. Use something else if you need cryptographic+ security.+ .+ For more information, see the upstream repository: https://github.com/Nicoshev/rapidhash+category: Data+homepage: https://github.com/jtnuttall/lithon#readme+bug-reports: https://github.com/jtnuttall/lithon/issues+author: Jeremy Nuttall+maintainer: jeremy@jeremy-nuttall.com+copyright: (c) 2026 Jeremy Nuttall+license: BSD-3-Clause+license-files: LICENSE,+ LICENSE_rapidhash+build-type: Simple+tested-with:+ GHC == 9.8.4+ , GHC == 9.10.3+ , GHC == 9.12.4+extra-source-files:+ cbits/rapidhash.h+ cbits/rapidhash_ext.h+ test/pin/pin.c+ test/pin/rapidhash-v3-pin.txt+extra-doc-files:+ README.md+ CHANGELOG.md++source-repository head+ type: git+ location: https://github.com/jtnuttall/lithon+ subdir: rapidhash++flag aeson+ description: Include ToJSON/FromJSON and ToJSONKey/FromJSONKey instances.+ manual: True+ default: False++flag llvm-bench+ description: Builds the benchmarks with GHC's LLVM backend so its effect can be measured+ on your hardware. Requires an LLVM toolchain matching your GHC's supported+ window, and GHC >= 9.10 for -pgmlas.+ manual: True+ default: False++flag optimize+ description: Turns on optimizations. Right now, this means -O2 for GHC and -O3 for the C compiler.+ .+ Since the library is tiny, this shouldn't be too much trouble, but you can disable+ this flag if it's slowing your builds too much.+ manual: True+ default: True++library+ exposed-modules:+ Data.Hash.RapidHash+ Data.Hash.RapidHash.Aeson+ Data.Hash.RapidHash.Class+ Data.Hash.RapidHash.FFI+ Data.Hash.RapidHash.Types+ other-modules:+ Paths_rapidhash+ autogen-modules:+ Paths_rapidhash+ hs-source-dirs:+ src+ default-extensions:+ BlockArguments+ DeriveAnyClass+ DerivingStrategies+ DerivingVia+ DuplicateRecordFields+ LambdaCase+ NoFieldSelectors+ OverloadedLabels+ OverloadedRecordDot+ RecordWildCards+ ghc-options: -Wmissing-deriving-strategies -Wmissing-export-lists -Wredundant-constraints -Wall+ include-dirs:+ cbits+ build-depends:+ base >=4.19 && <4.22+ , binary ==0.8.*+ , bytestring ==0.12.*+ , bytestring-lexing ==0.5.*+ , hashable ==1.5.*+ , primitive >=0.8 && <0.10+ , text ==2.1.*+ , text-builder-linear >=0.1.1 && <0.2+ , vector ==0.13.*+ default-language: GHC2021+ if flag(optimize)+ ghc-options: -O2+ cc-options: -O3+ if flag(aeson)+ cpp-options: -DWANT_AESON+ build-depends:+ aeson >=2.2 && <2.4++test-suite rapidhash-doctest+ type: exitcode-stdio-1.0+ main-is: Doctest.hs+ other-modules:+ Paths_rapidhash+ autogen-modules:+ Paths_rapidhash+ hs-source-dirs:+ doctest+ default-extensions:+ BlockArguments+ DeriveAnyClass+ DerivingStrategies+ DerivingVia+ DuplicateRecordFields+ LambdaCase+ NoFieldSelectors+ OverloadedLabels+ OverloadedRecordDot+ RecordWildCards+ ghc-options: -Wmissing-deriving-strategies -Wmissing-export-lists -Wredundant-constraints -Wall -threaded+ include-dirs:+ cbits+ build-depends:+ base >=4.19 && <4.22+ , binary ==0.8.*+ , bytestring ==0.12.*+ , bytestring-lexing ==0.5.*+ , doctest-parallel ==0.4.*+ , hashable ==1.5.*+ , primitive >=0.8 && <0.10+ , rapidhash+ , text ==2.1.*+ , text-builder-linear >=0.1.1 && <0.2+ , vector ==0.13.*+ default-language: GHC2021++test-suite rapidhash-test+ type: exitcode-stdio-1.0+ main-is: Driver.hs+ other-modules:+ RapidHashTest+ Paths_rapidhash+ autogen-modules:+ Paths_rapidhash+ hs-source-dirs:+ test+ default-extensions:+ BlockArguments+ DeriveAnyClass+ DerivingStrategies+ DerivingVia+ DuplicateRecordFields+ LambdaCase+ NoFieldSelectors+ OverloadedLabels+ OverloadedRecordDot+ RecordWildCards+ ghc-options: -Wmissing-deriving-strategies -Wmissing-export-lists -Wredundant-constraints -Wall -Wno-missing-export-lists -threaded -rtsopts -with-rtsopts=-N+ include-dirs:+ cbits+ build-tool-depends:+ tasty-discover:tasty-discover ==5.2.*+ build-depends:+ base >=4.19 && <4.22+ , binary ==0.8.*+ , bytestring ==0.12.*+ , bytestring-lexing ==0.5.*+ , hashable ==1.5.*+ , hedgehog ==1.7.*+ , primitive >=0.8 && <0.10+ , rapidhash+ , tasty ==1.5.*+ , tasty-hedgehog ==1.4.*+ , tasty-hunit ==0.10.*+ , text ==2.1.*+ , text-builder-linear >=0.1.1 && <0.2+ , vector ==0.13.*+ default-language: GHC2021++benchmark rapidhash-bench+ type: exitcode-stdio-1.0+ main-is: Bench.hs+ other-modules:+ Paths_rapidhash+ autogen-modules:+ Paths_rapidhash+ hs-source-dirs:+ bench+ default-extensions:+ BlockArguments+ DeriveAnyClass+ DerivingStrategies+ DerivingVia+ DuplicateRecordFields+ LambdaCase+ NoFieldSelectors+ OverloadedLabels+ OverloadedRecordDot+ RecordWildCards+ ghc-options: -Wmissing-deriving-strategies -Wmissing-export-lists -Wredundant-constraints -Wall -threaded -rtsopts "-with-rtsopts=-N -A32m -T" -O2+ include-dirs:+ cbits+ build-depends:+ base >=4.19 && <4.22+ , binary ==0.8.*+ , bytestring ==0.12.*+ , bytestring-lexing ==0.5.*+ , deepseq >=1.5 && <1.7+ , hashable ==1.5.*+ , murmur-hash ==0.1.*+ , primitive >=0.8 && <0.10+ , rapidhash+ , tasty ==1.5.*+ , tasty-bench ==0.5.*+ , text ==2.1.*+ , text-builder-linear >=0.1.1 && <0.2+ , vector ==0.13.*+ , xxhash-ffi ==0.3.*+ default-language: GHC2021+ if flag(llvm-bench)+ ghc-options: -fllvm -pgmlo opt -pgmlc llc -pgmlas clang
+ src/Data/Hash/RapidHash.hs view
@@ -0,0 +1,105 @@+{-# LANGUAGE CPP #-}++-- |+-- [rapidhash](https://github.com/Nicoshev/rapidhash) is a very fast, high-quality,+-- non-cryptographic and platform-independent hash.+--+-- This library provides rapidhash v3.+--+-- In microbenchmarks it outperforms xxhash3 (and+-- 'Data.Hashable.hashWithSalt', which is currently based on xxhash3) at+-- all but the smallest inputs; below ~16 bytes, constant factors dominate+-- and xxhash3-based hashers can edge it out (see the README benchmarks).+--+-- This module can be imported unqualified.+--+-- 'Data.Aeson.ToJSON'\/'Data.Aeson.FromJSON' and+-- 'Data.Aeson.ToJSONKey'\/'Data.Aeson.FromJSONKey' are provided behind the+-- @aeson@ Cabal flag.+--+-- === __Security and HashDoS__+--+-- This is not a cryptographically secure hash. Use something else if+-- you need cryptographic security.+--+-- rapidhash's C implementation supports a @RAPIDHASH_PROTECTED@ preprocessor+-- define that trades performance for more collision resistance. It is off by+-- default.+--+-- See the [upstream documentation](https://github.com/Nicoshev/rapidhash) for more+-- configuration flags and technical details.+module Data.Hash.RapidHash (+ -- |+ -- To use rapidhash, you'll generally just use the 'rapidhash' helper function.+ -- A seed override can be provided by using 'rapidhashWithSeed' if desired.+ rapidhash,+ RapidHashable (..),+ RapidSeed (..),++ -- * Hashes++ --++ -- | 'RapidHash' is a newtype that provides some affordances for ergonomic, efficient use.+ RapidHash (..),++ -- * Serialization+ rapidHashTextBuilder,+ showRapidHashText,+ showRapidHashBS,++ -- * Parsing+ parseRapidHashText,+ parseRapidHashBS,++ -- * File hashing++ --++ -- |+ -- These are simply useful helpers for hashing a file, assuming you don't need+ -- to do anything else with the contents. They use strict 'Data.ByteString.ByteString'+ -- under the hood, so beware very large files: besides residency, the hash+ -- itself is a single @unsafe@ FFI call, which blocks garbage collection+ -- across all capabilities for its duration (rapidhash processes tens of+ -- GB/s, so this matters only for very large inputs).+ rapidhashFileWithSeed,+ rapidhashFile,++ -- * DerivingVia++ --++ -- | Helpers for deriving 'Data.Hashable.Hashable' and other useful classes.+ HashViaRapidHash (..),++ -- * Re-exports+ Prim,+ Storable,+) where++import Data.Primitive.Types (Prim)+import Foreign.Storable (Storable)+import Prelude ()++import Data.Hash.RapidHash.Class (+ HashViaRapidHash (..),+ RapidHashable (..),+ rapidhash,+ rapidhashFile,+ rapidhashFileWithSeed,+ )+import Data.Hash.RapidHash.Types (+ RapidHash (..),+ RapidSeed (..),+ parseRapidHashBS,+ parseRapidHashText,+ rapidHashTextBuilder,+ showRapidHashBS,+ showRapidHashText,+ )++#ifdef WANT_AESON+-- Orphans only+import Data.Hash.RapidHash.Aeson ()+#endif
+ src/Data/Hash/RapidHash/Aeson.hs view
@@ -0,0 +1,36 @@+{-# LANGUAGE CPP #-}+{-# OPTIONS_GHC -Wno-orphans #-}++-- | Orphan aeson instances for 'Data.Hash.RapidHash.Types.RapidHash', encoding+-- to and from the tagged hex form (e.g. @"rhv3:0123456789abcdef"@).+--+-- Opt-in with the @aeson@ flag; without it this module is empty and the+-- instances do not exist.+module Data.Hash.RapidHash.Aeson () where++#ifdef WANT_AESON+import Data.Aeson qualified as A+import Data.Aeson.Types qualified as A++import Data.Hash.RapidHash.Types++instance A.ToJSON RapidHash where+ toJSON = A.String . showRapidHashText+ {-# INLINEABLE toJSON #-}++instance A.FromJSON RapidHash where+ parseJSON = A.withText "rapidhashv3" \t -> case parseRapidHashText t of+ Right h -> pure h+ Left err -> fail err+ {-# INLINEABLE parseJSON #-}++-- | Keys use the same tagged hex form as the value instances, so a map+-- keyed by @RapidHash@ serializes to a JSON object with @rhv3:@-prefixed keys.+instance A.ToJSONKey RapidHash where+ toJSONKey = A.toJSONKeyText showRapidHashText+ {-# INLINEABLE toJSONKey #-}++instance A.FromJSONKey RapidHash where+ fromJSONKey = A.FromJSONKeyTextParser \t -> either fail pure (parseRapidHashText t)+ {-# INLINEABLE fromJSONKey #-}+#endif
+ src/Data/Hash/RapidHash/Class.hs view
@@ -0,0 +1,137 @@+-- |+-- The polymorphic implementation of 'RapidHash'. If needed, 'RapidHashable'+-- can be extended at-will.+--+-- Be aware, however, that rapidhash is a block hasher, and this library does not+-- yet implement streaming, so you must process the whole block you want to target at+-- once.+--+-- See 'Data.Hash.RapidHash' and the README for more details.+module Data.Hash.RapidHash.Class (+ -- * rapidhash+ RapidHashable (..),+ rapidhash,++ -- ** File hashing helpers+ rapidhashFileWithSeed,+ rapidhashFile,++ -- * DerivingVia helpers+ HashViaRapidHash (..),+) where++import Control.Monad.IO.Class (MonadIO (liftIO))+import Data.Array.Byte (ByteArray)+import Data.ByteString qualified as BS+import Data.ByteString.Short (ShortByteString)+import Data.Coerce (coerce)+import Data.Hashable (Hashable (hashWithSalt))+import Data.Primitive (Prim)+import Data.Primitive.PrimArray (PrimArray)+import Data.Text qualified as T+import Data.Vector.Primitive qualified as PrimitiveVector+import Data.Vector.Storable qualified as StorableVector+import Foreign.Storable (Storable)+import Prelude (Eq, FilePath, fromIntegral, (<$>))++import Data.Hash.RapidHash.FFI+import Data.Hash.RapidHash.Types (RapidHash (RapidHash), RapidSeed (RapidSeed), defaultSeed)++-- $setup+-- >>> :set -XOverloadedStrings+-- >>> import Data.Hashable (Hashable, hashWithSalt)+-- >>> import Data.Text (Text)++-- | A class for things that can be efficiently passed to rapidhash.+--+-- If you implement your own instance of this class, keep in mind that+-- rapidhash is a block hasher that works over a chunk of information.+--+-- === __Cross-platform stability__+--+-- Instances for types that hold byte representations underneath are+-- cross-platform stable. Instances for types that contain elements reinterpret+-- the underlying memory to get zero-cost copies, and so are __NOT__ stable+-- across platforms.+--+-- There are two ways that these instances break portability:+--+-- 1. Machine word width - this is trivially solvable by using fixed-width+-- types (e.g., Int64 instead of Int)+-- 2. Endianness - no real solution, although for common application development+-- tasks you'll almost certainly know if this applies to you.+class RapidHashable a where+ -- | Run rapidhash with the given seed+ rapidhashWithSeed :: RapidSeed -> a -> RapidHash++-- | This instance is stable across platforms.+instance RapidHashable ByteArray where+ rapidhashWithSeed = coerce rapidhashWithSeed_ByteArray+ {-# INLINE rapidhashWithSeed #-}++-- | This instance is stable across platforms.+instance RapidHashable BS.ByteString where+ rapidhashWithSeed = coerce rapidhashWithSeed_ByteString+ {-# INLINE rapidhashWithSeed #-}++-- | This instance is stable across platforms.+instance RapidHashable T.Text where+ rapidhashWithSeed = coerce rapidhashWithSeed_Text+ {-# INLINE rapidhashWithSeed #-}++-- | This instance is stable across platforms.+instance RapidHashable ShortByteString where+ rapidhashWithSeed = coerce rapidhashWithSeed_ShortByteString+ {-# INLINE rapidhashWithSeed #-}++-- | This instance is __NOT__ stable across platforms.+instance RapidHashable (PrimArray a) where+ rapidhashWithSeed = coerce rapidhashWithSeed_PrimArray+ {-# INLINE rapidhashWithSeed #-}++-- | This instance is __NOT__ stable across platforms.+instance (Prim a) => RapidHashable (PrimitiveVector.Vector a) where+ rapidhashWithSeed = coerce rapidhashWithSeed_PrimitiveVector+ {-# INLINE rapidhashWithSeed #-}++-- | This instance is __NOT__ stable across platforms.+--+-- __Warning__: element memory is hashed raw, so the element type's+-- 'Foreign.Storable.Storable' layout must have no padding (i.e.+-- 'Foreign.Storable.poke' must write every byte of+-- 'Foreign.Storable.sizeOf'). Padding bytes are uninitialized memory:+-- with a padded element type, @a == b@ does not imply equal hashes —+-- which also breaks lawful 'Data.Hashable.Hashable' use via+-- 'Data.Hash.RapidHash.HashViaRapidHash'.+instance (Storable a) => RapidHashable (StorableVector.Vector a) where+ rapidhashWithSeed = coerce rapidhashWithSeed_StorableVector+ {-# INLINE rapidhashWithSeed #-}++-- | Run rapidhash with its default seed+rapidhash :: (RapidHashable a) => a -> RapidHash+rapidhash = rapidhashWithSeed defaultSeed+{-# INLINE rapidhash #-}++-- | Read a file into memory strictly, and immediately hash it.+rapidhashFileWithSeed :: (MonadIO m) => RapidSeed -> FilePath -> m RapidHash+rapidhashFileWithSeed seed path = rapidhashWithSeed seed <$> liftIO (BS.readFile path)+{-# INLINE rapidhashFileWithSeed #-}++-- | Read a file into memory strictly, and immediately hash it, with+-- rapidhash's default seed.+rapidhashFile :: (MonadIO m) => FilePath -> m RapidHash+rapidhashFile = rapidhashFileWithSeed defaultSeed+{-# INLINE rapidhashFile #-}++-- |+-- Newtype wrapper implementing 'Hashable' via 'RapidHashable' - works only for+-- types that already implement 'RapidHashable'. All such types should be efficiently+-- block-hashable.+newtype HashViaRapidHash a = HashViaRapidHash a+ deriving newtype (Eq)++instance (RapidHashable a, Eq a) => Hashable (HashViaRapidHash a) where+ hashWithSalt salt (HashViaRapidHash a) =+ let RapidHash h = rapidhashWithSeed (RapidSeed (fromIntegral salt)) a+ in fromIntegral h+ {-# INLINE hashWithSalt #-}
+ src/Data/Hash/RapidHash/FFI.hs view
@@ -0,0 +1,194 @@+{-# LANGUAGE AllowAmbiguousTypes #-}+{-# LANGUAGE CApiFFI #-}+{-# LANGUAGE MagicHash #-}+{-# LANGUAGE Strict #-}+{-# LANGUAGE UnliftedFFITypes #-}++{- HLINT ignore "Use camelCase" -}++-- |+-- Low-level FFI for RapidHash. You probably want to use 'Data.Hash.RapidHash.RapidHashable'+-- instead. These may be useful if you have a very specific need or performance requirement.+--+-- For all functions, you must maintain the invariant that the data to be hashed is not+-- mutated during the call. Type tetris won't work here.+--+-- All foreign calls in this module are @unsafe@, so they will briefly pause the capability and+-- garbage collector.+module Data.Hash.RapidHash.FFI (+ COffset,+ CSeed,++ -- * Monomorphic wrappers around FFI+ rapidhashWithSeed_Text,+ rapidhashWithSeed_ShortByteString,+ rapidhashWithSeed_ByteString,+ rapidhashWithSeed_PrimArray,+ rapidhashWithSeed_PrimitiveVector,+ rapidhashWithSeed_StorableVector,++ -- * Bare 'unsafeDupablePerformIO' wrappers around FFI+ rapidhashWithSeed_ByteArray,++ -- ** Unlifted+ rapidhashOffsetWithSeed_ByteArray#,+ rapidhashWithSeed_ByteArray#,++ -- ** Raw FFI+ rapidhashOffsetWithSeedFFI_ByteArray#,+ rapidhashWithSeedFFI_ByteArray#,+ rapidhashWithSeedFFI_Ptr,+) where++import Data.Array.Byte (ByteArray (ByteArray))+import Data.ByteString qualified as BS+import Data.ByteString.Short qualified as SBS+import Data.ByteString.Unsafe qualified as BSUnsafe+import Data.Primitive (Prim (sizeOf#))+import Data.Primitive.PrimArray (PrimArray (PrimArray))+import Data.Text.Internal qualified as TI+import Data.Vector.Primitive qualified as PrimitiveVector+import Data.Vector.Storable qualified as StorableVector+import Data.Void (Void)+import Foreign (Ptr, Storable (sizeOf), castPtr)+import Foreign.C.Types (CSize (CSize))+import GHC.Exts (+ ByteArray#,+ sizeofByteArray#,+ )+import GHC.Int (Int (I#))+import GHC.Word (Word64)+import System.IO.Unsafe (unsafeDupablePerformIO)+import Prelude (IO, Num ((*)), error, fromIntegral, ($), (.))++type CSeed = Word64+type COffset = CSize++----------------------------------------------------------------------------------------------------+-- FFI+----------------------------------------------------------------------------------------------------++foreign import capi unsafe "rapidhash_ext.h rapidhash_offset_withSeed"+ rapidhashOffsetWithSeedFFI_ByteArray#+ :: ByteArray#+ -- ^ The buffer+ -> COffset+ -- ^ Offset into buffer, in bytes+ -> CSize+ -- ^ Length of buffer after offset, in bytes+ -> CSeed+ -> IO Word64++-- |+-- Binding to @rapidhash_ext.h rapidhash_offset_withSeed@.+--+-- This is a small custom shim local to this library, which allows zero-copy hashing of+-- anything wrapping a 'ByteArray#' with an offset, by offloading the offset math to C.+rapidhashOffsetWithSeed_ByteArray# :: CSeed -> ByteArray# -> COffset -> CSize -> Word64+rapidhashOffsetWithSeed_ByteArray# seed ba# off len =+ unsafeDupablePerformIO $+ rapidhashOffsetWithSeedFFI_ByteArray# ba# off len seed+{-# INLINE rapidhashOffsetWithSeed_ByteArray# #-}++foreign import capi unsafe "rapidhash.h rapidhash_withSeed"+ rapidhashWithSeedFFI_ByteArray# :: ByteArray# -> CSize -> CSeed -> IO Word64++-- |+-- Direct binding to @rapidhash.h rapidhash_withSeed@, for anything wrapping a 'ByteArray#'+-- without an offset.+rapidhashWithSeed_ByteArray# :: CSeed -> ByteArray# -> Word64+rapidhashWithSeed_ByteArray# seed arr =+ unsafeDupablePerformIO $+ rapidhashWithSeedFFI_ByteArray# arr (csizeofByteArray# arr) seed+{-# INLINE rapidhashWithSeed_ByteArray# #-}++foreign import capi unsafe "rapidhash.h rapidhash_withSeed"+ rapidhashWithSeedFFI_Ptr :: Ptr Void -> CSize -> CSeed -> IO Word64++----------------------------------------------------------------------------------------------------+-- Data.Array.Byte+----------------------------------------------------------------------------------------------------++-- |+-- Lifted 'rapidhashWithSeed_ByteArray#' for 'ByteArray'.+rapidhashWithSeed_ByteArray :: CSeed -> ByteArray -> Word64+rapidhashWithSeed_ByteArray seed (ByteArray ba#) = rapidhashWithSeed_ByteArray# seed ba#+{-# INLINE rapidhashWithSeed_ByteArray #-}++----------------------------------------------------------------------------------------------------+-- Data.Text+----------------------------------------------------------------------------------------------------++-- |+-- Lifted 'rapidhashOffsetWithSeed_ByteArray#' for 'T.Text'.+--+-- This function reaches into 'T.Text'\'s internals to grab the offset and length into the underlying+-- 'ByteArray#', which lets us do a zero-copy hash.+rapidhashWithSeed_Text :: CSeed -> TI.Text -> Word64+rapidhashWithSeed_Text seed (TI.Text (ByteArray ba#) off len) =+ rapidhashOffsetWithSeed_ByteArray# seed ba# (CSize (fromIntegral off)) (CSize (fromIntegral len))+{-# INLINE rapidhashWithSeed_Text #-}++----------------------------------------------------------------------------------------------------+-- Data.ByteString+----------------------------------------------------------------------------------------------------++-- |+-- Applied 'rapidhashWithSeed_ByteArray' for 'SBS.ShortByteString'.+rapidhashWithSeed_ShortByteString :: CSeed -> SBS.ShortByteString -> Word64+rapidhashWithSeed_ShortByteString seed (SBS.ShortByteString ba) = rapidhashWithSeed_ByteArray seed ba+{-# INLINE rapidhashWithSeed_ShortByteString #-}++-- |+-- Applied 'rapidhashWithSeedFFI_Ptr' for 'BS.ByteString'+rapidhashWithSeed_ByteString :: CSeed -> BS.ByteString -> Word64+rapidhashWithSeed_ByteString seed bs = unsafeDupablePerformIO $+ BSUnsafe.unsafeUseAsCStringLen bs \(cstr, len) ->+ rapidhashWithSeedFFI_Ptr (castPtr cstr) (CSize (fromIntegral len)) seed+{-# INLINE rapidhashWithSeed_ByteString #-}++----------------------------------------------------------------------------------------------------+-- Data.Primitive+----------------------------------------------------------------------------------------------------++rapidhashWithSeed_PrimArray :: CSeed -> PrimArray a -> Word64+rapidhashWithSeed_PrimArray seed (PrimArray ba#) = rapidhashWithSeed_ByteArray# seed ba#+{-# INLINE rapidhashWithSeed_PrimArray #-}++----------------------------------------------------------------------------------------------------+-- Data.Vector+----------------------------------------------------------------------------------------------------++rapidhashWithSeed_PrimitiveVector+ :: forall a. (Prim a) => CSeed -> PrimitiveVector.Vector a -> Word64+rapidhashWithSeed_PrimitiveVector seed (PrimitiveVector.Vector off len (ByteArray ba#)) =+ rapidhashOffsetWithSeed_ByteArray#+ seed+ ba#+ (int2CSize (sizeOfType @a * off))+ (int2CSize (sizeOfType @a * len))+{-# INLINE rapidhashWithSeed_PrimitiveVector #-}++rapidhashWithSeed_StorableVector+ :: forall a. (Storable a) => CSeed -> StorableVector.Vector a -> Word64+rapidhashWithSeed_StorableVector seed v = unsafeDupablePerformIO $+ StorableVector.unsafeWith v \ptr ->+ let len = CSize $ fromIntegral (StorableVector.length v * sizeOf @a (error "sizeOf evaluated"))+ in rapidhashWithSeedFFI_Ptr (castPtr ptr) len seed+{-# INLINE rapidhashWithSeed_StorableVector #-}++----------------------------------------------------------------------------------------------------+-- Utilities+----------------------------------------------------------------------------------------------------++sizeOfType :: forall a. (Prim a) => Int+sizeOfType = I# (sizeOf# (error "sizeOf# evaluated" :: a))+{-# INLINE sizeOfType #-}++csizeofByteArray# :: ByteArray# -> CSize+csizeofByteArray# arr = CSize (fromIntegral (I# (sizeofByteArray# arr)))+{-# INLINE csizeofByteArray# #-}++int2CSize :: Int -> CSize+int2CSize = CSize . fromIntegral+{-# INLINE int2CSize #-}
+ src/Data/Hash/RapidHash/Types.hs view
@@ -0,0 +1,364 @@+{-# LANGUAGE LinearTypes #-}+{-# LANGUAGE MagicHash #-}+{-# LANGUAGE OverloadedStrings #-}+{-# LANGUAGE PatternSynonyms #-}++module Data.Hash.RapidHash.Types (+ -- * Seeds+ RapidSeed (..),+ defaultSeed,++ -- * Hashes+ RapidHash (..),+ pattern RAPIDHASH_V3_PREFIX,+ pattern RAPIDHASH_V3_HEX_LENGTH,++ -- ** Serializing+ rapidHashTextBuilder,+ showRapidHashText,+ showRapidHashBS,+ showsRapidHash,++ -- ** Deserializing+ parseRapidHashText,+ parseRapidHashBS,+ readsRapidHash,+) where++import Control.Monad (when)+import Control.Monad.ST.Strict (ST)+import Data.Binary (Binary)+import Data.Binary qualified as Binary+import Data.Bits (Bits (shiftR, (.&.)))+import Data.ByteString (ByteString)+import Data.ByteString qualified as BS+import Data.ByteString.Char8 qualified as BSC8+import Data.ByteString.Lex.Integral qualified as BS+import Data.Char (isSpace)+import Data.Foldable (for_, length)+import Data.Hashable (Hashable)+import Data.List qualified as L+import Data.Maybe (maybe)+import Data.String (IsString)+import Data.Text (Text)+import Data.Text qualified as T+import Data.Text.Array qualified as A+import Data.Text.Builder.Linear qualified as TB+import Data.Text.Builder.Linear.Buffer qualified as TBuff+import Data.Text.Builder.Linear.Core qualified as TB+import Data.Text.Read qualified as T+import Data.Word (Word64)+import GHC.Exts (Int (I#), (>#))+import GHC.Generics (Generic)+import Prelude (+ Applicative (pure),+ Either (Left, Right),+ Eq ((==)),+ MonadFail (fail),+ Num ((*), (+), (-)),+ Ord,+ Read (readsPrec),+ ReadS,+ Semigroup ((<>)),+ Show (show, showsPrec),+ ShowS,+ String,+ fromIntegral,+ otherwise,+ showString,+ ($),+ (.),+ (<$>),+ (||),+ )++-- $setup+-- >>> :set -XOverloadedStrings+-- >>> import Data.Text qualified as T++-- | Minimal wrapper around a rapidhash seed.+newtype RapidSeed = RapidSeed Word64+ deriving stock (Generic, Read, Show)+ deriving newtype (Eq, Num, Ord)++-- | rapidhash's default seed is 0 in the reference implementation+defaultSeed :: RapidSeed+defaultSeed = RapidSeed 0++-- | A rapidhash v3 digest.+--+-- The textual form is @rhv3:@ followed by exactly 16 hex digits, always+-- rendered lowercase. Parsing accepts either case (normalizing on+-- re-render), but rejects any other prefix, length, or stray characters.+-- The version tag makes stored digests self-describing: a future+-- rapidhash version bump (which changes outputs) can never be mistaken+-- for a v3 digest.+--+-- === __Examples__+-- >>> RapidHash 0xabc+-- rhv3:0000000000000abc+--+-- >>> Prelude.read "rhv3:0000000000000abc" :: RapidHash+-- rhv3:0000000000000abc+newtype RapidHash = RapidHash Word64+ deriving stock (Generic)+ deriving newtype (Eq, Hashable, Ord)++-- |+-- The prefix used during serialization and deserialization. This is not a universal+-- convention, but an identifier that should help prevent confusing these hashes+-- with others.+--+-- Exported for convenience.+pattern RAPIDHASH_V3_PREFIX :: (IsString a, Eq a) => a+pattern RAPIDHASH_V3_PREFIX = "rhv3:"++-- | The length of the hash part of a valid rapidhash.+--+-- Exported for convenience.+--+-- === __Total length__+--+-- >>> RAPIDHASH_V3_HEX_LENGTH + length (RAPIDHASH_V3_PREFIX :: String)+-- 21+pattern RAPIDHASH_V3_HEX_LENGTH :: (Num a, Eq a) => a+pattern RAPIDHASH_V3_HEX_LENGTH = 16++pattern ZERO_CHAR :: (Num a, Eq a) => a+pattern ZERO_CHAR = 0x30++prefixLen :: Int+prefixLen = length (RAPIDHASH_V3_PREFIX :: String)++instance Show RapidHash where+ showsPrec _ = showsRapidHash++-- |+--+-- === __Examples__+--+-- >>> Prelude.read (show (Prelude.Just (RapidHash 0x1234))) :: Prelude.Maybe RapidHash+-- Just rhv3:0000000000001234+instance Read RapidHash where+ readsPrec _ = readsRapidHash++-- |+-- Efficient binary serialization and deserialization, with a just-good-enough tag.+--+-- Encodes in 9 bytes: One byte for the tag, 8 for the 'Word64'.+instance Binary RapidHash where+ put (RapidHash h) = do+ Binary.putWord8 3+ Binary.put h+ {-# INLINE put #-}+ get = do+ tag <- Binary.getWord8+ case tag of+ 3 -> RapidHash <$> Binary.get+ _ -> fail "did not find magic tag for rapidhash"+ {-# INLINE get #-}++----------------------------------------------------------------------------------------------------+-- Serializing+----------------------------------------------------------------------------------------------------++-- |+-- Efficiently render a 'RapidHash' as a 'TB.Builder'+--+-- === __Examples__+--+-- >>> rapidHashTextBuilder (RapidHash 0x0)+-- "rhv3:0000000000000000"+--+-- >>> rapidHashTextBuilder (RapidHash 0xabcd3)+-- "rhv3:00000000000abcd3"+--+-- >>> rapidHashTextBuilder (RapidHash 0xfffff2381)+-- "rhv3:0000000fffff2381"+--+-- === __Prefixing__+--+-- >>> RAPIDHASH_V3_PREFIX `T.isPrefixOf` showRapidHashText (RapidHash 0x0)+-- True+rapidHashTextBuilder :: RapidHash -> TB.Builder+rapidHashTextBuilder h = TB.Builder \b -> appendPaddedHashHexBuf (b TBuff.|># "rhv3:"#) h+{-# INLINEABLE rapidHashTextBuilder #-}++-- |+-- Efficiently render a 'RapidHash' as 'Text'.+--+-- Prefer 'rapidHashTextBuilder' when composing.+showRapidHashText :: RapidHash -> Text+showRapidHashText = TB.runBuilder . rapidHashTextBuilder+{-# INLINEABLE showRapidHashText #-}++-- |+-- Efficiently render a 'RapidHash' as 'ByteString'. If your text blob is utf-8, it may be worth+-- composing using 'TB.Builder' and extracting with 'TB.runBuilderBS' yourself.+--+-- The resulting 'ByteString' is utf-8 encoded, using 'TB.runBuilderBS'+--+-- See 'rapidHashTextBuilder'+showRapidHashBS :: RapidHash -> ByteString+showRapidHashBS = TB.runBuilderBS . rapidHashTextBuilder+{-# INLINEABLE showRapidHashBS #-}++-- |+-- Somewhat inefficiently render a 'RapidHash' as a 'String'.+--+-- Present for debugging purposes. Goes through 'rapidHashTextBuilder'+showsRapidHash :: RapidHash -> ShowS+showsRapidHash h = showString $ T.unpack (showRapidHashText h)++-- |+-- This is a specialized reimplementation of 'TBuff.|>&' from Andrew Lelechenko's+-- text-builder-linear that additionally pads with zeros.+appendPaddedHashHexBuf :: TBuff.Buffer %1 -> RapidHash -> TBuff.Buffer+appendPaddedHashHexBuf buffer (RapidHash h) =+ -- appendBounded function preallocates a given length, and takes a callback that+ -- mutates the array and returns how many characters it wrote.+ TB.appendBounded+ RAPIDHASH_V3_HEX_LENGTH+ ( \dst off -> do+ endOff <- unsafeAppendHexW64 dst (off + RAPIDHASH_V3_HEX_LENGTH - 1) h++ -- Core lowering here is consistently fused, but if there's a regression I'd+ -- look here first.+ for_ @[] [off .. endOff] \i ->+ A.unsafeWrite dst i ZERO_CHAR++ pure RAPIDHASH_V3_HEX_LENGTH+ )+ buffer+{-# INLINEABLE appendPaddedHashHexBuf #-}++unsafeAppendHexW64 :: A.MArray s -> Int -> Word64 -> ST s Int+unsafeAppendHexW64 marr = go+ where+ go !off = \case+ 0 -> pure off+ m -> do+ let nibble = m .&. 0x0F+ A.unsafeWrite marr off $ hex (fromIntegral nibble)+ unsafeAppendHexW64 marr (off - 1) (m `shiftR` 4)++ -- Vendored from text-builder-linear - branchless conversion+ hex n@(I# n#) = fromIntegral $ ZERO_CHAR + n + I# (n# ># 9#) * (0x60 - 0x39)+{-# INLINEABLE unsafeAppendHexW64 #-}++----------------------------------------------------------------------------------------------------+-- Deserializing+----------------------------------------------------------------------------------------------------++-- |+-- Efficiently parse a 'RapidHash' from a 'Text'.+--+-- == __Examples__+--+-- >>> parseRapidHashText "rhv3:deadbeefdeadbeef"+-- Right rhv3:deadbeefdeadbeef+--+-- >>> parseRapidHashText "rhv3:abracadabratoomany"+-- Left "rapidhash hashes should have a length of exactly 16, but found length 18"+--+-- >>> parseRapidHashText "rhv3:nothexnothexnoth"+-- Left "input does not start with a hexadecimal digit"+--+-- >>> parseRapidHashText "rhv3:tooshort"+-- Left "rapidhash hashes should have a length of exactly 16, but found length 8"+--+-- >>> parseRapidHashText "noprefix"+-- Left "missing required prefix \"rhv3:\": \"noprefix\""+--+-- >>> parseRapidHashText "rhv3:abcdefabcdefabcg"+-- Left "leftovers after parsing hash: \"g\""+--+-- >>> parseRapidHashText "rhv3:0xadbeefdeadbeef"+-- Left "input does not start with a hexadecimal digit"+parseRapidHashText :: Text -> Either String RapidHash+parseRapidHashText t = do+ mhash <- guardPrefix (T.splitAt prefixLen t)+ guardLength (T.length mhash)+ -- T.hexadecimal helpfully strips 0x/0X, which is not so helpful for our purposes+ let pre = T.take 2 mhash+ when (pre == "0x" || pre == "0X") $ Left "input does not start with a hexadecimal digit"+ (hash, rest) <- T.hexadecimal mhash+ guardLeftovers rest+ pure $ RapidHash hash+{-# INLINEABLE parseRapidHashText #-}++-- |+-- Efficiently parse a 'RapidHash' from a 'ByteString'.+--+-- == __Examples__+--+-- >>> parseRapidHashBS "rhv3:deadbeefdeadbeef"+-- Right rhv3:deadbeefdeadbeef+--+-- >>> parseRapidHashBS "rhv3:abracadabratoomany"+-- Left "rapidhash hashes should have a length of exactly 16, but found length 18"+--+-- >>> parseRapidHashBS "rhv3:nothexnothexnoth"+-- Left "Could not parse hexadecimal from \"nothexnothexnoth\""+--+-- >>> parseRapidHashBS "rhv3:tooshort"+-- Left "rapidhash hashes should have a length of exactly 16, but found length 8"+--+-- >>> parseRapidHashBS "noprefix"+-- Left "missing required prefix \"rhv3:\": \"noprefix\""+--+-- >>> parseRapidHashBS "rhv3:abcdefabcdefabcg"+-- Left "leftovers after parsing hash: \"g\""+--+-- >>> parseRapidHashBS "rhv3:0xadbeefdeadbeef"+-- Left "leftovers after parsing hash: \"xadbeefdeadbeef\""+parseRapidHashBS :: ByteString -> Either String RapidHash+parseRapidHashBS b = do+ mhash <- guardPrefix (BS.splitAt prefixLen b)+ guardLength (BS.length mhash)+ (hash, rest) <- maybe (badHex mhash) Right (BS.readHexadecimal mhash)+ guardLeftovers rest+ pure $ RapidHash hash+ where+ badHex mhash = Left $ "Could not parse hexadecimal from \"" <> BSC8.unpack mhash <> "\""+{-# INLINEABLE parseRapidHashBS #-}++-- |+-- Somewhat inefficiently parse a 'RapidHash' from a 'String'.+--+-- Present for debugging purposes. Goes through 'parseRapidHashText'. Unlike the other+-- parse functions, this allows trailing characters.+--+-- === __Examples__+-- >>> readsRapidHash "rhv3:0000000000000abcdagk"+-- [(rhv3:0000000000000abc,"dagk")]+readsRapidHash :: ReadS RapidHash+readsRapidHash s =+ let (this, rest) = L.splitAt (prefixLen + RAPIDHASH_V3_HEX_LENGTH) (L.dropWhile isSpace s)+ in case parseRapidHashText (T.pack this) of+ Right parsed -> [(parsed, rest)]+ Left _ -> []++guardPrefix :: (IsString a, Show a, Semigroup a, Eq a) => (a, a) -> Either String a+guardPrefix = \case+ (RAPIDHASH_V3_PREFIX, mhash) -> Right mhash+ (pre, post) -> Left $ "missing required prefix \"" <> RAPIDHASH_V3_PREFIX <> "\": " <> show (pre <> post)++guardLength :: (Show a, Eq a, Num a) => a -> Either String ()+guardLength len+ | len == RAPIDHASH_V3_HEX_LENGTH = Right ()+ | otherwise = Left badLength+ where+ badLength =+ "rapidhash hashes should have a length of exactly "+ <> show @Int RAPIDHASH_V3_HEX_LENGTH+ <> ", but found length "+ <> show len++guardLeftovers :: (Show a, Eq a, IsString a) => a -> Either String ()+guardLeftovers = \case+ "" -> Right ()+ bad ->+ Left $+ "leftovers after parsing hash: "+ <> show bad
+ test/Driver.hs view
@@ -0,0 +1,1 @@+{-# OPTIONS_GHC -F -pgmF tasty-discover #-}
+ test/RapidHashTest.hs view
@@ -0,0 +1,105 @@+module RapidHashTest where++import Control.Monad (forM_)+import Data.ByteString qualified as BS+import Data.ByteString.Short qualified as SBS+import Data.Primitive.PrimArray (primArrayFromList)+import Data.Text qualified as T+import Data.Text.Encoding qualified as TE+import Data.Vector.Primitive qualified as PV+import Data.Vector.Storable qualified as SV+import Data.Word (Word64, Word8)+import Hedgehog (Property, forAll, property, (===))+import Hedgehog.Gen qualified as Gen+import Hedgehog.Range qualified as Range+import Numeric (readHex)+import Test.Tasty.HUnit (Assertion, assertBool, assertEqual, assertFailure, (@?=))++import Data.Hash.RapidHash (+ RapidHash (RapidHash),+ RapidSeed (RapidSeed),+ rapidhash,+ rapidhashWithSeed,+ )++unit_showIsTaggedPaddedHex :: Assertion+unit_showIsTaggedPaddedHex =+ show (RapidHash 0xabc) @?= "rhv3:0000000000000abc"++unit_readRejectsForeignTags :: Assertion+unit_readRejectsForeignTags = do+ reads @RapidHash "rhv4:0000000000000abc" @?= [] -- future+ reads @RapidHash "fnv1a64:0000000000000abc" @?= [] -- other hash+ reads @RapidHash "rhv3:abc" @?= [] -- invalid hash length++hprop_showReadRoundtrip :: Property+hprop_showReadRoundtrip = property do+ w <- forAll (Gen.word64 Range.linearBounded)+ let h = RapidHash w+ read (show h) === h++-- | The Text entry hashes the UTF-8 payload in place; it must agree with+-- hashing the encoded bytes (and the ShortByteString copy of them) — at+-- the default seed, at a random seed (pinning the seed plumbing of the+-- ByteArray# entry points), and for a Text with a nonzero internal offset.+hprop_representationsAgree :: Property+hprop_representationsAgree = property do+ t <- forAll (Gen.text (Range.linear 0 300) Gen.unicode)+ s <- forAll (Gen.word64 Range.linearBounded)+ let bytes = TE.encodeUtf8 t+ seed = RapidSeed s+ rapidhash t === rapidhash bytes+ rapidhash (SBS.toShort bytes) === rapidhash bytes+ rapidhash (BS.copy bytes) === rapidhash bytes+ rapidhashWithSeed seed t === rapidhashWithSeed seed bytes+ rapidhashWithSeed seed (SBS.toShort bytes) === rapidhashWithSeed seed bytes+ let t' = T.drop 1 t+ rapidhash t' === rapidhash (TE.encodeUtf8 t')++hprop_vectorInstancesAgreeWithBytes :: Property+hprop_vectorInstancesAgreeWithBytes = property do+ ws <- forAll (Gen.list (Range.linear 0 64) (Gen.word64 Range.linearBounded))+ k <- forAll (Gen.int (Range.linear 0 (length ws)))+ let sv = SV.fromList ws+ pv = PV.fromList ws+ pvSlice = PV.drop k pv+ pvBytes (PV.Vector off len ba) = PV.Vector (8 * off) (8 * len) ba :: PV.Vector Word8+ rapidhash sv === rapidhash (SV.unsafeCast sv :: SV.Vector Word8)+ rapidhash pv === rapidhash (pvBytes pv)+ rapidhash sv === rapidhash pv+ rapidhash (primArrayFromList ws) === rapidhash pv+ rapidhash pvSlice === rapidhash (pvBytes pvSlice)++-- | Known-answer vectors generated from the vendored upstream header by+-- @test/pin/pin.c@ (verify or regenerate with @scripts/rapidhash-pin.sh@+-- in the project repository).+unit_matchesUpstreamCReference :: Assertion+unit_matchesUpstreamCReference = do+ golden <- lines <$> readFile "test/pin/rapidhash-v3-pin.txt"+ assertBool "golden file contains vectors" (not (null golden))+ forM_ golden \line -> case words line of+ ["default", lenS, hashS] ->+ assertEqual line (RapidHash (hex hashS)) $+ rapidhash (bufBS (read lenS))+ ["withSeed", lenS, seedS, hashS] ->+ assertEqual line (RapidHash (hex hashS)) $+ rapidhashWithSeed (RapidSeed (hex seedS)) (bufBS (read lenS))+ ["offset", offS, lenS, seedS, hashS] -> do+ let off = read offS+ len = read lenS+ slice = PV.drop off (PV.fromList (bufBytes (off + len)) :: PV.Vector Word8)+ assertEqual line (RapidHash (hex hashS)) $+ rapidhashWithSeed (RapidSeed (hex seedS)) slice+ _ -> assertFailure ("unparseable golden line: " <> line)+ where+ hex :: String -> Word64+ hex s = case readHex s of+ [(v, "")] -> v+ _ -> error ("bad hex field in golden file: " <> s)++ -- Deterministic filler; mirrors byte_at in test/pin/pin.c.+ bufBytes :: Int -> [Word8]+ bufBytes n = [fromIntegral (i * 167 + 13) | i <- [0 .. n - 1]]++ bufBS :: Int -> BS.ByteString+ bufBS = BS.pack . bufBytes
+ test/pin/pin.c view
@@ -0,0 +1,67 @@+/*+ * Known-answer vector generator for the rapidhash Haskell binding.+ *+ * Compiled against the vendored upstream header (cbits/rapidhash.h) and the+ * local shim (cbits/rapidhash_ext.h), it prints reference digests to stdout.+ * The committed golden file (test/pin/rapidhash-v3-pin.txt) is this program's+ * output; the Haskell test suite recomputes every line through the binding's+ * ByteString entrypoint (and the sliced Vector path for the offset shim).+ *+ * verify: scripts/rapidhash-pin.sh (in the project repository,+ * regenerate: scripts/rapidhash-pin.sh --regen not in the sdist)+ */+#include <inttypes.h>+#include <stdio.h>+#include <stdlib.h>++#include "rapidhash_ext.h"++/* Deterministic, non-degenerate filler; mirrored in test/RapidHashTest.hs. */+static uint8_t byte_at(size_t i) { return (uint8_t)(i * 167u + 13u); }++/* Lengths bracketing rapidhash v3's internal branch boundaries. */+static const size_t lengths[] = {+ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,+ 12, 13, 14, 15, 16, 17, 31, 32, 33, 47, 48, 49,+ 63, 64, 65, 79, 80, 81, 111, 112, 113, 127, 128, 129,+ 191, 192, 193, 223, 224, 225, 255, 256, 257, 447, 448, 449,+ 511, 512, 1023, 1024, 4096, 65535, 65536, 300007};++static const uint64_t seeds[] = {0ULL, 1ULL, 0xDEADBEEFULL,+ 0x123456789ABCDEF0ULL, 0xFFFFFFFFFFFFFFFFULL};++static const size_t offsets[] = {1, 3, 8, 17};+static const size_t offset_lengths[] = {0, 7, 16, 63, 64, 257};+static const uint64_t offset_seeds[] = {0ULL, 0xDEADBEEFULL};++#define COUNT(xs) (sizeof(xs) / sizeof((xs)[0]))++int main(void) {+ size_t max_len = 0;+ for (size_t i = 0; i < COUNT(lengths); i++)+ if (lengths[i] > max_len) max_len = lengths[i];++ uint8_t *buf = malloc(max_len);+ if (!buf) return 1;+ for (size_t i = 0; i < max_len; i++) buf[i] = byte_at(i);++ for (size_t li = 0; li < COUNT(lengths); li++)+ printf("default %zu %016" PRIx64 "\n", lengths[li],+ rapidhash(buf, lengths[li]));++ for (size_t li = 0; li < COUNT(lengths); li++)+ for (size_t si = 0; si < COUNT(seeds); si++)+ printf("withSeed %zu %016" PRIx64 " %016" PRIx64 "\n", lengths[li],+ seeds[si], rapidhash_withSeed(buf, lengths[li], seeds[si]));++ for (size_t oi = 0; oi < COUNT(offsets); oi++)+ for (size_t li = 0; li < COUNT(offset_lengths); li++)+ for (size_t si = 0; si < COUNT(offset_seeds); si++)+ printf("offset %zu %zu %016" PRIx64 " %016" PRIx64 "\n", offsets[oi],+ offset_lengths[li], offset_seeds[si],+ rapidhash_offset_withSeed(buf, offsets[oi], offset_lengths[li],+ offset_seeds[si]));++ free(buf);+ return 0;+}
+ test/pin/rapidhash-v3-pin.txt view
@@ -0,0 +1,384 @@+default 0 0338dc4be2cecdae+default 1 e8d3b882671125a6+default 2 72f646f85991e6ff+default 3 c76c8514de0eb9f0+default 4 54ceab033b17ed48+default 5 927048267a1e0e6c+default 6 8a479b23d49ea8c0+default 7 6c91739e11166758+default 8 cb1c61491fd8ed0c+default 9 c8c920654ad0a214+default 10 1c197f92a46cd6a8+default 11 ed353bd1078d750d+default 12 a7d066f68974928b+default 13 784066c84e806ea5+default 14 4ae43dd7c228e5d0+default 15 cf0671c9f0e79123+default 16 51cf6b59dc9af20b+default 17 d72787ae7a2963b8+default 31 9e168ae2c0b51969+default 32 0214629041803a0c+default 33 c8c2c6562d2ec99b+default 47 d86d732eb077836d+default 48 5f31b4484305dbe9+default 49 842be8c228f50882+default 63 fd8fc3f2f5223ee6+default 64 44d70d4c8b15579f+default 65 f6bbae844d4d4181+default 79 58026c3618a2a508+default 80 df336fbf7f62d83b+default 81 dd5cfcedca049d93+default 111 43fb5caeeb06a43e+default 112 6286b4021fd2dd8d+default 113 5244e1630212c36d+default 127 42502792104fdc71+default 128 b5347fd6743165ea+default 129 c4a217dabcaa4de2+default 191 f2b52e696d1dacf5+default 192 6e6218c972743315+default 193 305a310ec4cff602+default 223 30cb092fa2c2a816+default 224 200c8e2c66466ddd+default 225 73ddb2d3e0e680f3+default 255 c044b4166dc82562+default 256 4c9cbe062b4099ba+default 257 fe5ec46d93ff9252+default 447 249b614fd83132c1+default 448 f820c5318ecc7bc0+default 449 cb8f7371c843a244+default 511 403b7a95b7336894+default 512 30225ad0615ab280+default 1023 077265f8db655b2f+default 1024 fa31a83534ebe036+default 4096 9101be11098a4217+default 65535 96522749db3a9805+default 65536 f913310ce3e324ab+default 300007 455fb2dc9cfa6803+withSeed 0 0000000000000000 0338dc4be2cecdae+withSeed 0 0000000000000001 ad700ecdf353d5ca+withSeed 0 00000000deadbeef 842e1a82b8ea7243+withSeed 0 123456789abcdef0 66db63b3916becf4+withSeed 0 ffffffffffffffff 9a9c59147a213be8+withSeed 1 0000000000000000 e8d3b882671125a6+withSeed 1 0000000000000001 ab407ce6511467c4+withSeed 1 00000000deadbeef 6129164d197e499c+withSeed 1 123456789abcdef0 6833d7e3e8065a9f+withSeed 1 ffffffffffffffff af19bbe1857eda2b+withSeed 2 0000000000000000 72f646f85991e6ff+withSeed 2 0000000000000001 2eee397c4532100e+withSeed 2 00000000deadbeef caac963ed10e31e5+withSeed 2 123456789abcdef0 f22714f0fdf61dde+withSeed 2 ffffffffffffffff c4b1f8698f1cdd9a+withSeed 3 0000000000000000 c76c8514de0eb9f0+withSeed 3 0000000000000001 fa3c53e10185181c+withSeed 3 00000000deadbeef f5f25d77cd27c8c3+withSeed 3 123456789abcdef0 e7da94088e9d352a+withSeed 3 ffffffffffffffff d72c2937bcd00a14+withSeed 4 0000000000000000 54ceab033b17ed48+withSeed 4 0000000000000001 4986b01041f8f9d8+withSeed 4 00000000deadbeef 9de3be9cd249d4d3+withSeed 4 123456789abcdef0 403fbc89ba50a3e0+withSeed 4 ffffffffffffffff 572e595c91494030+withSeed 5 0000000000000000 927048267a1e0e6c+withSeed 5 0000000000000001 5193f513a7783e25+withSeed 5 00000000deadbeef b7e5650ac2a5170e+withSeed 5 123456789abcdef0 0787592e5c0f371e+withSeed 5 ffffffffffffffff f832cd04e84e96b0+withSeed 6 0000000000000000 8a479b23d49ea8c0+withSeed 6 0000000000000001 6f87e160ee3f0d00+withSeed 6 00000000deadbeef a522b82d7180e9f4+withSeed 6 123456789abcdef0 856349c2ac3dec25+withSeed 6 ffffffffffffffff 62a7140fe38a9f23+withSeed 7 0000000000000000 6c91739e11166758+withSeed 7 0000000000000001 11017bb55c556f75+withSeed 7 00000000deadbeef 5ff42368a57cfc48+withSeed 7 123456789abcdef0 7b321310e63b13c5+withSeed 7 ffffffffffffffff f57e96782b26e319+withSeed 8 0000000000000000 cb1c61491fd8ed0c+withSeed 8 0000000000000001 4221eaa066d079a0+withSeed 8 00000000deadbeef a43716be5754d9c8+withSeed 8 123456789abcdef0 69e33dd175f91269+withSeed 8 ffffffffffffffff 3e021c1802c19e61+withSeed 9 0000000000000000 c8c920654ad0a214+withSeed 9 0000000000000001 d3cda3b2b3fb361a+withSeed 9 00000000deadbeef b1606a4eb9d49c12+withSeed 9 123456789abcdef0 80d7ad6b0f34c372+withSeed 9 ffffffffffffffff 454f767d1e729858+withSeed 10 0000000000000000 1c197f92a46cd6a8+withSeed 10 0000000000000001 f4aaa18c11b1880a+withSeed 10 00000000deadbeef 2335184b7457b759+withSeed 10 123456789abcdef0 d00ed7c6ccf3b1c9+withSeed 10 ffffffffffffffff 51333ee955674cdb+withSeed 11 0000000000000000 ed353bd1078d750d+withSeed 11 0000000000000001 c0aaf8ec129962df+withSeed 11 00000000deadbeef 5e3ba7f5376e28c2+withSeed 11 123456789abcdef0 7316224e1217eeda+withSeed 11 ffffffffffffffff 1501e404ed0c8173+withSeed 12 0000000000000000 a7d066f68974928b+withSeed 12 0000000000000001 18fa41a627de8ae6+withSeed 12 00000000deadbeef d0df8a7a79a40a40+withSeed 12 123456789abcdef0 d488a65dd82b12e0+withSeed 12 ffffffffffffffff 451c70f6b6907acf+withSeed 13 0000000000000000 784066c84e806ea5+withSeed 13 0000000000000001 99fa1f10497a31db+withSeed 13 00000000deadbeef e1ec8947c089c530+withSeed 13 123456789abcdef0 b344d1bd2e98f286+withSeed 13 ffffffffffffffff d225da173586c005+withSeed 14 0000000000000000 4ae43dd7c228e5d0+withSeed 14 0000000000000001 d09aa54913bc8b20+withSeed 14 00000000deadbeef 1cb5455fc4da65d4+withSeed 14 123456789abcdef0 3958ad503597c1e4+withSeed 14 ffffffffffffffff b59881651749ae07+withSeed 15 0000000000000000 cf0671c9f0e79123+withSeed 15 0000000000000001 ffcd5b7587b3e03b+withSeed 15 00000000deadbeef e5337aa3e048c6fb+withSeed 15 123456789abcdef0 eea33d3c96cdbc23+withSeed 15 ffffffffffffffff d33d8734a2b79584+withSeed 16 0000000000000000 51cf6b59dc9af20b+withSeed 16 0000000000000001 84ab3e852806f36a+withSeed 16 00000000deadbeef a9762803b339f0fd+withSeed 16 123456789abcdef0 e4be0a162a51e769+withSeed 16 ffffffffffffffff 2ea6a93e9ce31a37+withSeed 17 0000000000000000 d72787ae7a2963b8+withSeed 17 0000000000000001 9093dae1bd413ea0+withSeed 17 00000000deadbeef d6c07c2008ef78d7+withSeed 17 123456789abcdef0 46a516c54320aa5c+withSeed 17 ffffffffffffffff b4e97bd9a73141f0+withSeed 31 0000000000000000 9e168ae2c0b51969+withSeed 31 0000000000000001 8f2391580911c9e4+withSeed 31 00000000deadbeef 80275fc3bfac3335+withSeed 31 123456789abcdef0 7634b61596605b71+withSeed 31 ffffffffffffffff 8603fa15b02d472d+withSeed 32 0000000000000000 0214629041803a0c+withSeed 32 0000000000000001 082341b09271e938+withSeed 32 00000000deadbeef 1074a288def125c8+withSeed 32 123456789abcdef0 c58c04deaced7e90+withSeed 32 ffffffffffffffff ee2301861ae63206+withSeed 33 0000000000000000 c8c2c6562d2ec99b+withSeed 33 0000000000000001 52ce883d43df49e3+withSeed 33 00000000deadbeef 5963dad2db66368b+withSeed 33 123456789abcdef0 f8d6ffc1efd49dcf+withSeed 33 ffffffffffffffff 70a8eea0202f83dd+withSeed 47 0000000000000000 d86d732eb077836d+withSeed 47 0000000000000001 a98da65e2ac325c6+withSeed 47 00000000deadbeef 65f7976f3bc306f8+withSeed 47 123456789abcdef0 8270fa92c75b6810+withSeed 47 ffffffffffffffff 144281ea7877c5f2+withSeed 48 0000000000000000 5f31b4484305dbe9+withSeed 48 0000000000000001 5a6418ef65972d4f+withSeed 48 00000000deadbeef e53b01b9b393c510+withSeed 48 123456789abcdef0 c7959121472d055a+withSeed 48 ffffffffffffffff d88f445b35e4715b+withSeed 49 0000000000000000 842be8c228f50882+withSeed 49 0000000000000001 1de81b8817a8f2ca+withSeed 49 00000000deadbeef cac1555db0979cbf+withSeed 49 123456789abcdef0 a809d1335aa96fef+withSeed 49 ffffffffffffffff d59cc76de50d9c53+withSeed 63 0000000000000000 fd8fc3f2f5223ee6+withSeed 63 0000000000000001 0318cd1daf57d224+withSeed 63 00000000deadbeef d2cd6e2634856170+withSeed 63 123456789abcdef0 644ce15944af559a+withSeed 63 ffffffffffffffff a2e3a95ec415bbee+withSeed 64 0000000000000000 44d70d4c8b15579f+withSeed 64 0000000000000001 7c2b184ad7a6be12+withSeed 64 00000000deadbeef 06abbe2cf54b915e+withSeed 64 123456789abcdef0 2e200f15432403d2+withSeed 64 ffffffffffffffff 8393fe721236a9bc+withSeed 65 0000000000000000 f6bbae844d4d4181+withSeed 65 0000000000000001 08a7b7d8e1e46e8a+withSeed 65 00000000deadbeef 8838e9a62419e83e+withSeed 65 123456789abcdef0 567fedbbdf09484e+withSeed 65 ffffffffffffffff 428ac41664fa5e19+withSeed 79 0000000000000000 58026c3618a2a508+withSeed 79 0000000000000001 70311e9471ead990+withSeed 79 00000000deadbeef ebb07db8ea173c54+withSeed 79 123456789abcdef0 f9a2970aed707e73+withSeed 79 ffffffffffffffff 2dd5b590dda181c6+withSeed 80 0000000000000000 df336fbf7f62d83b+withSeed 80 0000000000000001 a62239ae33152fd6+withSeed 80 00000000deadbeef 547ceac21c5de14f+withSeed 80 123456789abcdef0 8463e1bbfaf437d0+withSeed 80 ffffffffffffffff 5978ffc6cd7c56d1+withSeed 81 0000000000000000 dd5cfcedca049d93+withSeed 81 0000000000000001 d525cf9371f29fc8+withSeed 81 00000000deadbeef 6f98993cb30ed887+withSeed 81 123456789abcdef0 f570fb595e840eef+withSeed 81 ffffffffffffffff 5347be85fff24f57+withSeed 111 0000000000000000 43fb5caeeb06a43e+withSeed 111 0000000000000001 0d77df9ce3829031+withSeed 111 00000000deadbeef d31acdf327c728b8+withSeed 111 123456789abcdef0 33aa93fd0fb78fd3+withSeed 111 ffffffffffffffff 5e6e37c6e55c5825+withSeed 112 0000000000000000 6286b4021fd2dd8d+withSeed 112 0000000000000001 5d6b8257f09852ec+withSeed 112 00000000deadbeef bd73cf8d9775ec1a+withSeed 112 123456789abcdef0 9af7cdfbce612b55+withSeed 112 ffffffffffffffff 1f9bccc50d58707d+withSeed 113 0000000000000000 5244e1630212c36d+withSeed 113 0000000000000001 91e7effbd950aac6+withSeed 113 00000000deadbeef 77764d3ad4e83c1f+withSeed 113 123456789abcdef0 d1c0a683d1331548+withSeed 113 ffffffffffffffff 4ba5aaa2cb70d6a6+withSeed 127 0000000000000000 42502792104fdc71+withSeed 127 0000000000000001 39f18caf0dba71a5+withSeed 127 00000000deadbeef 43a1d8e3a3e51716+withSeed 127 123456789abcdef0 597f0c10a53238d5+withSeed 127 ffffffffffffffff f84711f0ba18056e+withSeed 128 0000000000000000 b5347fd6743165ea+withSeed 128 0000000000000001 a76946b6ec160f54+withSeed 128 00000000deadbeef f05a4f78716093d1+withSeed 128 123456789abcdef0 59f993ae715bbe22+withSeed 128 ffffffffffffffff 53a92476e2480a74+withSeed 129 0000000000000000 c4a217dabcaa4de2+withSeed 129 0000000000000001 287bb5dd7629e821+withSeed 129 00000000deadbeef 5f84e6b6047cfafb+withSeed 129 123456789abcdef0 dc1fdb2702f37dbc+withSeed 129 ffffffffffffffff bcbc52d1eef42e3c+withSeed 191 0000000000000000 f2b52e696d1dacf5+withSeed 191 0000000000000001 b26a7006b97b5368+withSeed 191 00000000deadbeef 402edc1eac2ac7aa+withSeed 191 123456789abcdef0 a5010c106f278969+withSeed 191 ffffffffffffffff aa2d314f5b4cfb9a+withSeed 192 0000000000000000 6e6218c972743315+withSeed 192 0000000000000001 b1bb2221c6b7428d+withSeed 192 00000000deadbeef d0ed8d0eab01ca8b+withSeed 192 123456789abcdef0 9fe99d50ceb99f2a+withSeed 192 ffffffffffffffff 0d43f2c5b14eafa1+withSeed 193 0000000000000000 305a310ec4cff602+withSeed 193 0000000000000001 3a3f33d82b500522+withSeed 193 00000000deadbeef d89140fb50bf1666+withSeed 193 123456789abcdef0 c819b9b858d98b97+withSeed 193 ffffffffffffffff e407cbb27148504b+withSeed 223 0000000000000000 30cb092fa2c2a816+withSeed 223 0000000000000001 016b77278aea4b26+withSeed 223 00000000deadbeef 5ea2070d8f26f3ba+withSeed 223 123456789abcdef0 11ff9544097b9516+withSeed 223 ffffffffffffffff 2541daa34e65d155+withSeed 224 0000000000000000 200c8e2c66466ddd+withSeed 224 0000000000000001 6646614b5640069b+withSeed 224 00000000deadbeef da2e9ceddd30a222+withSeed 224 123456789abcdef0 ce368a3a49540ada+withSeed 224 ffffffffffffffff a02b1b5d30949e40+withSeed 225 0000000000000000 73ddb2d3e0e680f3+withSeed 225 0000000000000001 86a9b0086ba543de+withSeed 225 00000000deadbeef 2108db2565b43f8c+withSeed 225 123456789abcdef0 ca7be3b0e3047bfc+withSeed 225 ffffffffffffffff c3fe96c6c291139a+withSeed 255 0000000000000000 c044b4166dc82562+withSeed 255 0000000000000001 87081cb45e5aec27+withSeed 255 00000000deadbeef 6627008fdbf7baa6+withSeed 255 123456789abcdef0 97a6fea276aec429+withSeed 255 ffffffffffffffff 0d5ebd964719d862+withSeed 256 0000000000000000 4c9cbe062b4099ba+withSeed 256 0000000000000001 34debed6278f0b04+withSeed 256 00000000deadbeef 9e14e89f4028e72b+withSeed 256 123456789abcdef0 0c354ab84fc7532e+withSeed 256 ffffffffffffffff 178dc6ac56326fd0+withSeed 257 0000000000000000 fe5ec46d93ff9252+withSeed 257 0000000000000001 9a06c7d7f29bf201+withSeed 257 00000000deadbeef b8bd06172a83b3bd+withSeed 257 123456789abcdef0 b6660958f0e58473+withSeed 257 ffffffffffffffff d8c02d30e97adc0a+withSeed 447 0000000000000000 249b614fd83132c1+withSeed 447 0000000000000001 97613b205b14adec+withSeed 447 00000000deadbeef 8ab61b6dd68fc4f4+withSeed 447 123456789abcdef0 bda30eb7364c869a+withSeed 447 ffffffffffffffff 6c4c6ee6c4ab296d+withSeed 448 0000000000000000 f820c5318ecc7bc0+withSeed 448 0000000000000001 088f39383d7811ce+withSeed 448 00000000deadbeef ee09f725a52e91c7+withSeed 448 123456789abcdef0 4cc584338e469154+withSeed 448 ffffffffffffffff f3d40277475856b0+withSeed 449 0000000000000000 cb8f7371c843a244+withSeed 449 0000000000000001 239bff2e8e8ebd31+withSeed 449 00000000deadbeef a051a2c58cba34ac+withSeed 449 123456789abcdef0 5b92a58e155194b4+withSeed 449 ffffffffffffffff 4a15db87d2df726b+withSeed 511 0000000000000000 403b7a95b7336894+withSeed 511 0000000000000001 d71305bf94bd53bf+withSeed 511 00000000deadbeef eda8be5c17b4b4cf+withSeed 511 123456789abcdef0 b198a146803906f4+withSeed 511 ffffffffffffffff 793352133cbd9e67+withSeed 512 0000000000000000 30225ad0615ab280+withSeed 512 0000000000000001 ece9fb6025b12fc0+withSeed 512 00000000deadbeef 022805eae596bbdd+withSeed 512 123456789abcdef0 dd0e788fbd4ad08c+withSeed 512 ffffffffffffffff d9f08db8a8da35b0+withSeed 1023 0000000000000000 077265f8db655b2f+withSeed 1023 0000000000000001 6de48a0fb5438022+withSeed 1023 00000000deadbeef 4dd9fb6c7164ffb0+withSeed 1023 123456789abcdef0 94b368de94eb2a1a+withSeed 1023 ffffffffffffffff c12086b4194d051c+withSeed 1024 0000000000000000 fa31a83534ebe036+withSeed 1024 0000000000000001 5cdc71a68964c7c6+withSeed 1024 00000000deadbeef 622d5678f498a351+withSeed 1024 123456789abcdef0 399eb2e7cca6f2a4+withSeed 1024 ffffffffffffffff 8fac8dfa95663a43+withSeed 4096 0000000000000000 9101be11098a4217+withSeed 4096 0000000000000001 b8b4a472e8f3a47d+withSeed 4096 00000000deadbeef f988f0ca4cb3fabe+withSeed 4096 123456789abcdef0 fd532a006ffddafc+withSeed 4096 ffffffffffffffff fe8ee36141e93eb0+withSeed 65535 0000000000000000 96522749db3a9805+withSeed 65535 0000000000000001 e9d57a340abc3483+withSeed 65535 00000000deadbeef 2bcdc7641b4e645b+withSeed 65535 123456789abcdef0 659caceec57af265+withSeed 65535 ffffffffffffffff 1a2f959d040103d5+withSeed 65536 0000000000000000 f913310ce3e324ab+withSeed 65536 0000000000000001 3111f0bb639072aa+withSeed 65536 00000000deadbeef de25e05f4eaf735b+withSeed 65536 123456789abcdef0 99e8da40ba4742c5+withSeed 65536 ffffffffffffffff dc098cf6b4ca2842+withSeed 300007 0000000000000000 455fb2dc9cfa6803+withSeed 300007 0000000000000001 35c45e53754b4e57+withSeed 300007 00000000deadbeef 83bf44f619a0de0e+withSeed 300007 123456789abcdef0 ad4254e3a5a41350+withSeed 300007 ffffffffffffffff 1d3b59796bc1b8ac+offset 1 0 0000000000000000 0338dc4be2cecdae+offset 1 0 00000000deadbeef 842e1a82b8ea7243+offset 1 7 0000000000000000 f7854b11f9682cd0+offset 1 7 00000000deadbeef ecdfba4a43fe7737+offset 1 16 0000000000000000 17aeb00945b41c70+offset 1 16 00000000deadbeef 0d2fbc3c4cbaa6e9+offset 1 63 0000000000000000 1599640c41715038+offset 1 63 00000000deadbeef ef83c73a68443ad6+offset 1 64 0000000000000000 55023c50907b1303+offset 1 64 00000000deadbeef 39f2097c2146e40d+offset 1 257 0000000000000000 b152a9f7c93711d2+offset 1 257 00000000deadbeef acb742ab4fd57634+offset 3 0 0000000000000000 0338dc4be2cecdae+offset 3 0 00000000deadbeef 842e1a82b8ea7243+offset 3 7 0000000000000000 da92d24f8013069c+offset 3 7 00000000deadbeef 1bd08cb2b539f027+offset 3 16 0000000000000000 ad13b6d5232be413+offset 3 16 00000000deadbeef c20ae581e6351fee+offset 3 63 0000000000000000 a39e7ab833156c09+offset 3 63 00000000deadbeef 3073dc0f20034461+offset 3 64 0000000000000000 c807fd33c06b1a8c+offset 3 64 00000000deadbeef ec371bd0069403cf+offset 3 257 0000000000000000 dc5184defbb1ab89+offset 3 257 00000000deadbeef 4cc51a8b37e3c5f3+offset 8 0 0000000000000000 0338dc4be2cecdae+offset 8 0 00000000deadbeef 842e1a82b8ea7243+offset 8 7 0000000000000000 2129ff6a4225f316+offset 8 7 00000000deadbeef 38f3d3ad12f181ce+offset 8 16 0000000000000000 25ec3172c4972990+offset 8 16 00000000deadbeef 706eb2d1bb3e0469+offset 8 63 0000000000000000 705ee8c91cc34e14+offset 8 63 00000000deadbeef 7b109ede278365db+offset 8 64 0000000000000000 4b9b56e6ba4f60c9+offset 8 64 00000000deadbeef 149c32c6cc8d70d1+offset 8 257 0000000000000000 b9933ffefdb9edf7+offset 8 257 00000000deadbeef 6bfc54394d5a5949+offset 17 0 0000000000000000 0338dc4be2cecdae+offset 17 0 00000000deadbeef 842e1a82b8ea7243+offset 17 7 0000000000000000 5023d7ddd4325e35+offset 17 7 00000000deadbeef 704bf26ff2d3c989+offset 17 16 0000000000000000 e193e06a17813552+offset 17 16 00000000deadbeef 54d2b9ee93de7b87+offset 17 63 0000000000000000 4d37066d271a344d+offset 17 63 00000000deadbeef 25baa3dcd571ef7c+offset 17 64 0000000000000000 583de726b937be09+offset 17 64 00000000deadbeef 15c05b7fa243027f+offset 17 257 0000000000000000 4bd9fa46f08c671b+offset 17 257 00000000deadbeef 858abb96791bc043