commonware_storage/
translator.rs

1//! Primitive implementations of [Translator].
2
3use commonware_utils::GOLDEN_RATIO;
4use core::hash::{BuildHasher, Hash, Hasher};
5
6/// Translate keys into a new representation (often a smaller one).
7///
8/// # Warning
9///
10/// The output of [Translator::transform] is often used as a key in a hash table. If the output is
11/// not uniformly distributed, the performance of said hash table will degrade substantially.
12pub trait Translator: Clone + BuildHasher + Send + Sync + 'static {
13    /// The type of the internal representation of keys.
14    ///
15    /// Although [Translator] is a [BuildHasher], the `Key` type must still implement [Hash] for
16    /// compatibility with any hash table that wraps [Translator]. We also require [Ord] for
17    /// compatibility with ordered collections. [Send] and [Sync] are required for thread-safe
18    /// concurrent access.
19    type Key: Ord + Hash + Copy + Send + Sync;
20
21    /// Transform a key into its new representation.
22    fn transform(&self, key: &[u8]) -> Self::Key;
23}
24
25/// A [Translator] whose output preserves the lexicographic order of its input.
26///
27/// For all byte strings `a <= b`, `transform(a) <= transform(b)`. Distinct keys may still map to the
28/// same translated key. Ordered indices rely on this to find a key's neighbors.
29pub trait OrderedTranslator: Translator {}
30
31/// A lightweight hasher for translated `uint` keys.
32///
33/// Most users typically store keys that are **already hashed** (shortened by the [Translator]).
34/// Re-hashing them with SipHash (by [std::collections::HashMap]) would waste CPU, so we give
35/// [std::collections::HashMap] this custom hasher instead:
36///
37/// * [Hasher::write_u8], [Hasher::write_u16], [Hasher::write_u32], [Hasher::write_u64] copies the
38///   input into an internal field;
39/// * [Hasher::finish] returns that value multiplied by a mixing constant.
40///
41/// # Warning
42///
43/// This hasher is not suitable for general use. If the hasher is called on a byte slice longer
44/// than `size_of::<u64>()`, it will panic.
45#[derive(Default, Clone)]
46pub struct UintIdentity {
47    value: u64,
48}
49
50impl Hasher for UintIdentity {
51    #[inline]
52    fn write(&mut self, bytes: &[u8]) {
53        assert!(bytes.len() <= 8, "UintIdenty hasher cannot handle >8 bytes");
54        // Treat the input array as a little-endian int to ensure low-order bits don't end up mostly
55        // 0s, given that we right-pad.
56        self.value = u64::from_le_bytes(cap::<8>(bytes));
57    }
58
59    #[inline]
60    fn write_u8(&mut self, i: u8) {
61        self.value = i as u64;
62    }
63
64    #[inline]
65    fn write_u16(&mut self, i: u16) {
66        self.value = i as u64;
67    }
68
69    #[inline]
70    fn write_u32(&mut self, i: u32) {
71        self.value = i as u64;
72    }
73
74    #[inline]
75    fn write_u64(&mut self, i: u64) {
76        self.value = i;
77    }
78
79    #[inline]
80    fn finish(&self) -> u64 {
81        // Multiply by the mixing constant to spread low-order bits across all 64 bits.
82        // Without this, hashbrown's h2 control bytes (top 7 bits) are all zero for small
83        // keys, defeating its SIMD fast-reject filter.
84        self.value.wrapping_mul(GOLDEN_RATIO)
85    }
86}
87
88/// Cap the key to a fixed length.
89///
90/// # Behavior
91///
92/// - If input is shorter than `N`, the output is zero-padded.
93/// - If input is longer than `N`, the output is truncated.
94/// - If input is exactly `N`, the output is identical.
95fn cap<const N: usize>(key: &[u8]) -> [u8; N] {
96    let mut capped = [0; N];
97    let len = key.len().min(N);
98    capped[..len].copy_from_slice(&key[..len]);
99    capped
100}
101
102macro_rules! define_cap_translator {
103    ($name:ident, $size:expr, $int:ty) => {
104        #[doc = concat!("Translator that caps the key to ", stringify!($size), " byte(s) and returns it packed in a ", stringify!($int), ".")]
105        ///
106        /// Truncation, zero-padding, and big-endian packing preserve key order, so this translator
107        /// implements [OrderedTranslator].
108        #[derive(Clone, Default)]
109        pub struct $name;
110
111        impl Translator for $name {
112            // Minimal uint size for the key.
113            type Key = $int;
114
115            #[inline]
116            fn transform(&self, key: &[u8]) -> Self::Key {
117                let capped = cap::<$size>(key);
118                <$int>::from_be_bytes(capped)
119            }
120        }
121
122        impl OrderedTranslator for $name {}
123
124        // Implement the `BuildHasher` trait for `IdentityHasher`.
125        impl BuildHasher for $name {
126            type Hasher = UintIdentity;
127
128            #[inline]
129            fn build_hasher(&self) -> Self::Hasher {
130                UintIdentity::default()
131            }
132        }
133    };
134}
135
136define_cap_translator!(OneCap, 1, u8);
137define_cap_translator!(TwoCap, 2, u16);
138define_cap_translator!(FourCap, 4, u32);
139define_cap_translator!(EightCap, 8, u64);
140
141/// Define a special array type for which we'll implement our own lightweight hasher. This avoids the
142/// overhead of the default Array hasher which unnecessarily (for our use case) includes a length
143/// prefix.
144#[derive(Clone, Copy, PartialEq, Eq, Debug)]
145pub struct UnhashedArray<const N: usize> {
146    pub inner: [u8; N],
147}
148
149impl<const N: usize> UnhashedArray<N> {
150    /// The array as a big-endian integer, zero-padded on the right.
151    ///
152    /// # Panics
153    ///
154    /// Panics if `N > 8`, so callers check `N <= 8` first.
155    #[inline]
156    fn word(&self) -> u64 {
157        let mut word = [0u8; 8];
158        word[..N].copy_from_slice(&self.inner);
159        u64::from_be_bytes(word)
160    }
161}
162
163impl<const N: usize> Ord for UnhashedArray<N> {
164    #[inline]
165    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
166        // Equal-length byte strings order like their big-endian values, so an array that fits in a
167        // word compares as one 8-byte integer, in a single compare without a branch.
168        if N <= 8 {
169            return self.word().cmp(&other.word());
170        }
171        self.inner.cmp(&other.inner)
172    }
173}
174
175impl<const N: usize> PartialOrd for UnhashedArray<N> {
176    #[inline]
177    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
178        Some(self.cmp(other))
179    }
180}
181
182impl<const N: usize> Hash for UnhashedArray<N> {
183    #[inline]
184    fn hash<H: Hasher>(&self, state: &mut H) {
185        state.write(&self.inner);
186    }
187}
188
189impl<const N: usize> PartialEq<[u8; N]> for UnhashedArray<N> {
190    fn eq(&self, other: &[u8; N]) -> bool {
191        &self.inner == other
192    }
193}
194
195/// Translators for keys that are not the length of a standard integer.
196///
197/// Like the fixed-width cap translators, [Cap] implements [OrderedTranslator].
198#[derive(Clone, Copy)]
199pub struct Cap<const N: usize>;
200
201impl<const N: usize> Cap<N> {
202    pub const fn new() -> Self {
203        const {
204            assert!(N <= 8 && N > 0, "Cap must be between 1 and 8");
205        };
206        Self
207    }
208}
209
210// Manually implement Default for Cap<N> so it calls new() which validates N.
211impl<const N: usize> Default for Cap<N> {
212    fn default() -> Self {
213        Self::new()
214    }
215}
216
217impl<const N: usize> Translator for Cap<N> {
218    type Key = UnhashedArray<N>;
219
220    #[inline]
221    fn transform(&self, key: &[u8]) -> Self::Key {
222        const {
223            assert!(N <= 8 && N > 0, "Cap must be between 1 and 8");
224        };
225        UnhashedArray {
226            inner: cap::<N>(key),
227        }
228    }
229}
230
231impl<const N: usize> OrderedTranslator for Cap<N> {}
232
233impl<const N: usize> BuildHasher for Cap<N> {
234    type Hasher = UintIdentity;
235
236    #[inline]
237    fn build_hasher(&self) -> Self::Hasher {
238        UintIdentity::default()
239    }
240}
241
242/// Collision-resistant wrapper for any [Translator].
243///
244/// Hashes the full key with a per-instance secret seed before delegating to the inner translator.
245/// This makes translated-key collisions unpredictable to an adversary who
246/// does not know the seed, similar to how [std::collections::HashMap] uses
247/// [std::collections::hash_map::RandomState] to prevent HashDoS attacks. It can also be used to
248/// ensure uniform distribution of skewed keyspaces when used by non-hashing structures such as
249/// [crate::index].
250///
251/// # No Ordering
252///
253/// Hashing destroys lexicographic key ordering, so [Hashed] does not implement [OrderedTranslator]
254/// and cannot back an ordered index or the ordered QMDB. It is safe for unordered indices and
255/// partitioned unordered indices.
256///
257/// An ordered index over [Hashed] does not compile:
258///
259/// ```compile_fail
260/// use commonware_storage::{
261///     index::{Ordered, ordered::Index},
262///     translator::{Hashed, TwoCap},
263/// };
264///
265/// fn ordered<I: Ordered>() {}
266/// ordered::<Index<Hashed<TwoCap>, u64>>();
267/// ```
268///
269/// # `no_std` Support
270///
271/// [Hashed::new] and [Default] are available only with this crate's `std` feature. They use
272/// [ahash::RandomState::new], which requires OS-provided randomness (the `runtime-rng` feature of
273/// `ahash`, enabled by `std` here). In `no_std` environments, use [Hashed::from_seed] with an
274/// externally-sourced random seed instead.
275///
276/// # No Stability Guarantees
277///
278/// [ahash::RandomState] is used as the underlying hasher. While `ahash` is robust, its exact
279/// algorithm might change across versions. As a result, transformed outputs are not stable across
280/// Rust versions or platforms. Treat this translator as an in-memory collision-hardening mechanism,
281/// not as a stable/persisted encoding.
282///
283/// # Examples
284///
285/// ```
286/// use commonware_storage::translator::{Hashed, TwoCap, Translator};
287///
288/// # #[cfg(feature = "std")]
289/// # {
290/// // Random seed (production use, requires `std`):
291/// let t = Hashed::new(TwoCap);
292/// let _k = t.transform(b"hello");
293/// # }
294///
295/// // Deterministic seed (testing within the same toolchain/runtime):
296/// let t = Hashed::from_seed(42, TwoCap);
297/// assert_eq!(t.transform(b"hello"), t.transform(b"hello"));
298/// ```
299#[derive(Clone)]
300pub struct Hashed<T: Translator> {
301    random_state: ahash::RandomState,
302    inner: T,
303}
304
305#[cfg(feature = "std")]
306impl<T: Translator + Default> Default for Hashed<T> {
307    fn default() -> Self {
308        Self::new(T::default())
309    }
310}
311
312impl<T: Translator> Hashed<T> {
313    /// Create a new [Hashed] translator with a random seed.
314    #[cfg(feature = "std")]
315    pub fn new(inner: T) -> Self {
316        Self {
317            random_state: ahash::RandomState::new(),
318            inner,
319        }
320    }
321
322    /// Create a new [Hashed] translator with a specific seed.
323    pub const fn from_seed(seed: u64, inner: T) -> Self {
324        Self {
325            random_state: ahash::RandomState::with_seeds(seed, 0, 0, 0),
326            inner,
327        }
328    }
329}
330
331impl<T: Translator> Translator for Hashed<T> {
332    type Key = T::Key;
333
334    #[inline]
335    fn transform(&self, key: &[u8]) -> T::Key {
336        let hash_val = self.random_state.hash_one(key);
337        self.inner.transform(&hash_val.to_le_bytes())
338    }
339}
340
341impl<T: Translator> BuildHasher for Hashed<T> {
342    type Hasher = <T as BuildHasher>::Hasher;
343
344    #[inline]
345    fn build_hasher(&self) -> Self::Hasher {
346        self.inner.build_hasher()
347    }
348}
349
350#[cfg(test)]
351mod tests {
352    use super::*;
353    use commonware_utils::test_rng;
354    use core::hash::Hasher;
355    use rand::RngExt as _;
356
357    #[test]
358    fn test_one_cap() {
359        let t = OneCap;
360        assert_eq!(t.transform(b""), 0);
361        assert_eq!(t.transform(b"a"), b'a');
362        assert_eq!(t.transform(b"ab"), b'a');
363        assert_eq!(t.transform(b"abc"), b'a');
364    }
365
366    #[test]
367    fn test_two_cap() {
368        let t = TwoCap;
369        assert_eq!(t.transform(b""), 0);
370        assert_eq!(t.transform(b"abc"), t.transform(b"ab"));
371        assert!(t.transform(b"") < t.transform(b"a"));
372        assert!(t.transform(b"a") < t.transform(b"b"));
373        assert!(t.transform(b"ab") < t.transform(b"ac"));
374        assert!(t.transform(b"z") < t.transform(b"zz"));
375        assert_eq!(t.transform(b"zz"), t.transform(b"zzabc"));
376    }
377
378    #[test]
379    fn test_four_cap() {
380        let t = FourCap;
381        let t1 = t.transform(b"");
382        let t2 = t.transform(b"a");
383        let t3 = t.transform(b"abcd");
384        let t4 = t.transform(b"abcdef");
385        let t5 = t.transform(b"b");
386
387        assert_eq!(t1, 0);
388        assert!(t1 < t2);
389        assert!(t2 < t3);
390        assert_eq!(t3, t4);
391        assert!(t3 < t5);
392        assert!(t4 < t5);
393    }
394
395    #[test]
396    fn test_unhashed_array_orders_like_its_bytes() {
397        fn check<const N: usize>(rng: &mut impl rand::Rng) {
398            // Random arrays that mostly differ in their first byte.
399            let mut arrays: Vec<UnhashedArray<N>> = (0..200)
400                .map(|_| {
401                    let mut inner = [0u8; N];
402                    rng.fill_bytes(&mut inner);
403                    UnhashedArray { inner }
404                })
405                .collect();
406
407            // Arrays equal in every byte but the last, and arrays with high bits set.
408            let mut last = [0xab; N];
409            arrays.push(UnhashedArray { inner: last });
410            last[N - 1] = 0xac;
411            arrays.push(UnhashedArray { inner: last });
412            arrays.push(UnhashedArray { inner: [0xff; N] });
413            arrays.push(UnhashedArray { inner: [0; N] });
414
415            // Every pair orders as its bytes do, through `Ord` and `PartialOrd` alike.
416            for a in &arrays {
417                for b in &arrays {
418                    assert_eq!(a.cmp(b), a.inner.cmp(&b.inner), "{a:?} vs {b:?}");
419                    assert_eq!(a.partial_cmp(b), Some(a.inner.cmp(&b.inner)));
420                }
421            }
422        }
423
424        // Every width a `Cap` translator produces, plus one too wide to compare as a word.
425        let mut rng = test_rng();
426        check::<1>(&mut rng);
427        check::<2>(&mut rng);
428        check::<3>(&mut rng);
429        check::<4>(&mut rng);
430        check::<5>(&mut rng);
431        check::<6>(&mut rng);
432        check::<7>(&mut rng);
433        check::<8>(&mut rng);
434        check::<9>(&mut rng);
435    }
436
437    #[test]
438    fn test_cap_3() {
439        let t = Cap::<3>::new();
440        assert_eq!(t.transform(b""), [0; 3]);
441        assert_eq!(t.transform(b"abc"), *b"abc");
442        assert_eq!(t.transform(b"abcdef"), *b"abc");
443        assert_eq!(t.transform(b"ab"), [b'a', b'b', 0]);
444    }
445
446    #[test]
447    fn test_cap_6() {
448        let t = Cap::<6>::new();
449        assert_eq!(t.transform(b""), [0; 6]);
450        assert_eq!(t.transform(b"abcdef"), *b"abcdef");
451        assert_eq!(t.transform(b"abcdefghi"), *b"abcdef");
452        assert_eq!(t.transform(b"abc"), [b'a', b'b', b'c', 0, 0, 0]);
453    }
454
455    #[test]
456    fn test_eight_cap() {
457        let t = EightCap;
458        let t1 = t.transform(b"");
459        let t2 = t.transform(b"a");
460        let t3 = t.transform(b"abcdefghaaaaaaa");
461        let t4 = t.transform(b"abcdefghijkzzzzzzzzzzzzzzzzzz");
462        let t5 = t.transform(b"b");
463
464        assert_eq!(t1, 0);
465        assert!(t1 < t2);
466        assert!(t2 < t3);
467        assert_eq!(t3, t4);
468        assert!(t3 < t5);
469        assert!(t4 < t5);
470    }
471
472    /// Asserts that `t` maps byte-sorted keys to non-decreasing translated keys.
473    fn assert_order_preserving<T: OrderedTranslator>(t: T) {
474        // A small alphabet makes shared prefixes, zero padding, and high bytes common.
475        const ALPHABET: [u8; 6] = [0x00, 0x01, 0x7F, 0x80, 0xFE, 0xFF];
476        let mut rng = test_rng();
477        let mut keys: Vec<Vec<u8>> = (0..10_000)
478            .map(|_| {
479                let len = rng.random_range(0..=10);
480                (0..len)
481                    .map(|_| ALPHABET[rng.random_range(0..ALPHABET.len())])
482                    .collect()
483            })
484            .collect();
485        keys.sort();
486        for pair in keys.windows(2) {
487            assert!(t.transform(&pair[0]) <= t.transform(&pair[1]), "{pair:?}");
488        }
489    }
490
491    #[test]
492    fn test_cap_translators_preserve_order() {
493        assert_order_preserving(OneCap);
494        assert_order_preserving(TwoCap);
495        assert_order_preserving(FourCap);
496        assert_order_preserving(EightCap);
497        assert_order_preserving(Cap::<1>::new());
498        assert_order_preserving(Cap::<3>::new());
499        assert_order_preserving(Cap::<5>::new());
500        assert_order_preserving(Cap::<8>::new());
501    }
502
503    #[test]
504    fn identity_hasher_small_slices_differ() {
505        let hash = |bytes: &[u8]| {
506            let mut h = UintIdentity::default();
507            h.write(bytes);
508            h.finish()
509        };
510        assert_ne!(hash(b"abc"), hash(b"abd"));
511        assert_ne!(hash(b"a"), hash(b"b"));
512        assert_ne!(hash(b""), hash(b"a"));
513    }
514
515    #[test]
516    fn identity_hasher_sets_high_bits() {
517        // The mixing step must spread small values into the top 7 bits so that
518        // hashbrown's h2 SIMD filter is effective.
519        for i in [1u64, 7, 17, 255] {
520            let mut h = UintIdentity::default();
521            h.write_u64(i);
522            assert_ne!(h.finish() >> 57, 0, "high bits all zero for input {i}");
523        }
524    }
525
526    #[test]
527    fn identity_hasher_integer_writes_differ() {
528        let hash_u8 = |v: u8| {
529            let mut h = UintIdentity::default();
530            h.write_u8(v);
531            h.finish()
532        };
533        let hash_u16 = |v: u16| {
534            let mut h = UintIdentity::default();
535            h.write_u16(v);
536            h.finish()
537        };
538        let hash_u32 = |v: u32| {
539            let mut h = UintIdentity::default();
540            h.write_u32(v);
541            h.finish()
542        };
543        let hash_u64 = |v: u64| {
544            let mut h = UintIdentity::default();
545            h.write_u64(v);
546            h.finish()
547        };
548        assert_ne!(hash_u8(0), hash_u8(1));
549        assert_ne!(hash_u16(0), hash_u16(1));
550        assert_ne!(hash_u32(0), hash_u32(1));
551        assert_ne!(hash_u64(0), hash_u64(1));
552
553        // Same numeric value through different write widths must agree.
554        assert_eq!(hash_u8(7), hash_u16(7));
555        assert_eq!(hash_u16(7), hash_u32(7));
556        assert_eq!(hash_u32(7), hash_u64(7));
557    }
558
559    #[test]
560    #[should_panic]
561    fn identity_hasher_panics_on_large_write_slice() {
562        let mut h = UintIdentity::default();
563        h.write(b"too big for an int");
564    }
565
566    #[test]
567    fn test_hashed_consistency() {
568        let t = Hashed::from_seed(42, TwoCap);
569        assert_eq!(t.transform(b"hello"), t.transform(b"hello"));
570        assert_eq!(t.transform(b""), t.transform(b""));
571        assert_eq!(t.transform(b"abcdef"), t.transform(b"abcdef"));
572    }
573
574    #[test]
575    fn test_hashed_seed_determinism() {
576        let t1 = Hashed::from_seed(42, TwoCap);
577        let t2 = Hashed::from_seed(42, TwoCap);
578        assert_eq!(t1.transform(b"hello"), t2.transform(b"hello"));
579        assert_eq!(t1.transform(b"world"), t2.transform(b"world"));
580    }
581
582    #[test]
583    fn test_hashed_seed_independence() {
584        let t1 = Hashed::from_seed(1, EightCap);
585        let t2 = Hashed::from_seed(2, EightCap);
586        // Different seeds should (with overwhelming probability) produce different outputs.
587        assert_ne!(t1.transform(b"hello"), t2.transform(b"hello"));
588    }
589
590    #[test]
591    fn test_hashed_prefix_collisions_avoided() {
592        // Without hashing, keys sharing a prefix collide. With hashing, they should not.
593        let t = Hashed::from_seed(99, TwoCap);
594        let k1 = t.transform(b"abXXX");
595        let k2 = t.transform(b"abYYY");
596        // The unhashed TwoCap would map both to the same value (first 2 bytes "ab").
597        assert_ne!(k1, k2);
598    }
599
600    #[test]
601    fn test_hashed_all_cap_sizes() {
602        let t1 = Hashed::from_seed(7, OneCap);
603        assert_eq!(t1.transform(b"test"), t1.transform(b"test"));
604
605        let t4 = Hashed::from_seed(7, FourCap);
606        assert_eq!(t4.transform(b"test"), t4.transform(b"test"));
607
608        let t8 = Hashed::from_seed(7, EightCap);
609        assert_eq!(t8.transform(b"test"), t8.transform(b"test"));
610
611        let tc = Hashed::from_seed(7, Cap::<3>::new());
612        assert_eq!(tc.transform(b"test"), tc.transform(b"test"));
613    }
614
615    #[cfg(feature = "std")]
616    #[test]
617    fn test_hashed_random_seed() {
618        // Two instances with random seeds should (with overwhelming probability)
619        // produce different outputs.
620        let t1 = Hashed::new(EightCap);
621        let t2 = Hashed::new(EightCap);
622        assert_ne!(t1.transform(b"hello"), t2.transform(b"hello"));
623    }
624}
commonware_storage/translator.rs

commonware_storage/
translator.rs
