ssdeep/internals/generate/hashes/
partial_fnv.rs

1// SPDX-License-Identifier: GPL-2.0-or-later
2// SPDX-FileCopyrightText: Copyright Andrew Tridgell <tridge@samba.org> 2002
3// SPDX-FileCopyrightText: Copyright (C) 2006 ManTech International Corporation
4// SPDX-FileCopyrightText: Copyright (C) 2013 Helmut Grohne <helmut@subdivi.de>
5// SPDX-FileCopyrightText: Copyright (C) 2017, 2023–2025 Tsukasa OI <floss_ssdeep@irq.a4lg.com>
6
7//! Partial FNV-1 hash as used in the fuzzy hash generator.
8
9use core::ops::AddAssign;
10
11use crate::internals::hash::block::block_hash;
12
13#[cfg(not(feature = "opt-reduce-fnv-table"))]
14use crate::internals::macros::invariant;
15
16/// Hasher which computes the lowest 6 bits of a 32-bit FNV-1 variant.
17///
18/// This variant of FNV-1 hash has the regular prime constant of `0x01000193`
19/// but has a different initial state: `0x28021967` (in contrast to regular
20/// FNV-1-32's `0x811c9dc5`).
21///
22/// Since ssdeep only uses the lowest 6 bits of the hash value, it ignores any
23/// higher bits, enabling updating the state table-based (instead of multiply
24/// and xor).
25#[derive(Debug, Clone, Copy, PartialEq, Eq)]
26pub struct PartialFNVHash(u8);
27
28impl PartialFNVHash {
29    /// The initial value of this variant of the FNV-1 hash (`0x28021967`).
30    ///
31    /// This is different from the regular variant of the FNV-1 hash
32    /// (FNV-1-32: `0x811c9dc5`).
33    const OLD_HASH_INIT: u32 = 0x28021967;
34
35    /// The initial value of this variant of the partial FNV-1 hash.
36    ///
37    /// This is generated by masking [`Self::OLD_HASH_INIT`].
38    const FNV_HASH_INIT: u8 = (Self::OLD_HASH_INIT % block_hash::ALPHABET_SIZE as u32) as u8;
39
40    /// The prime constant for the FNV-1 hash.
41    ///
42    /// This is the same as the regular FNV-1.
43    const FNV_HASH_PRIME: u32 = 0x01000193;
44
45    /// The partial FNV-1 update table.
46    ///
47    /// This is used by the [`update_by_byte()`](Self::update_by_byte()) method
48    /// to update the current state using a new byte, unless the feature
49    /// `opt-reduce-fnv-table` is enabled.
50    #[cfg(not(feature = "opt-reduce-fnv-table"))]
51    const FNV_TABLE: [[u8; block_hash::ALPHABET_SIZE]; block_hash::ALPHABET_SIZE] = {
52        let mut array = [[0u8; block_hash::ALPHABET_SIZE]; block_hash::ALPHABET_SIZE];
53        let mut state = 0u8;
54        while state < 64 {
55            let mut ch = 0u8;
56            while ch < 64 {
57                array[state as usize][ch as usize] =
58                    (((state as u32).wrapping_mul(Self::FNV_HASH_PRIME) as u8) ^ ch)
59                        % block_hash::ALPHABET_SIZE as u8;
60                ch += 1;
61            }
62            state += 1;
63        }
64        array
65    };
66
67    /// Creates a new [`PartialFNVHash`] with the initial value.
68    #[inline]
69    pub fn new() -> Self {
70        PartialFNVHash(Self::FNV_HASH_INIT)
71    }
72
73    /// Updates the hash value by processing a byte.
74    #[inline]
75    pub fn update_by_byte(&mut self, ch: u8) -> &mut Self {
76        cfg_if::cfg_if! {
77            if #[cfg(not(feature = "opt-reduce-fnv-table"))] {
78                invariant!((self.value() as usize) < block_hash::ALPHABET_SIZE);
79                self.0 = Self::FNV_TABLE
80                    [self.value() as usize] // grcov-excl-br-line:ARRAY
81                    [ch as usize % block_hash::ALPHABET_SIZE]; // grcov-excl-br-line:ARRAY
82            } else {
83                self.0 = ((self.0 as u32).wrapping_mul(Self::FNV_HASH_PRIME) ^ (ch as u32)) as u8;
84            }
85        }
86        self
87    }
88
89    /// Updates the hash value by processing an iterator of [`u8`].
90    pub fn update_by_iter(&mut self, iter: impl Iterator<Item = u8>) -> &mut Self {
91        for ch in iter {
92            self.update_by_byte(ch);
93        }
94        self
95    }
96
97    /// Updates the hash value by processing a slice of [`u8`].
98    pub fn update(&mut self, buf: &[u8]) -> &mut Self {
99        for &ch in buf.iter() {
100            self.update_by_byte(ch);
101        }
102        self
103    }
104
105    /// Returns the current hash value.
106    ///
107    /// Note that there's no "finalization" on the FNV hash.
108    /// You can even continue updating after reading the hash value.
109    #[inline]
110    pub fn value(&self) -> u8 {
111        cfg_if::cfg_if! {
112            if #[cfg(not(feature = "opt-reduce-fnv-table"))] {
113                invariant!(self.0 < (block_hash::ALPHABET_SIZE as u8));
114                self.0
115            } else {
116                self.0 & (block_hash::ALPHABET_SIZE as u8).wrapping_sub(1)
117            }
118        }
119    }
120}
121
122impl Default for PartialFNVHash {
123    fn default() -> Self {
124        Self::new()
125    }
126}
127
128impl AddAssign<&[u8]> for PartialFNVHash {
129    /// Updates the hash value by processing a slice of [`u8`].
130    #[inline(always)]
131    fn add_assign(&mut self, buffer: &[u8]) {
132        self.update(buffer);
133    }
134}
135
136impl<const N: usize> AddAssign<&[u8; N]> for PartialFNVHash {
137    /// Updates the hash value by processing an array of [`u8`].
138    #[inline(always)]
139    fn add_assign(&mut self, buffer: &[u8; N]) {
140        self.update(&buffer[..]);
141    }
142}
143
144impl AddAssign<u8> for PartialFNVHash {
145    /// Updates the hash value by processing a byte.
146    #[inline(always)]
147    fn add_assign(&mut self, byte: u8) {
148        self.update_by_byte(byte);
149    }
150}
151
152/// Constant assertions related to this module.
153#[doc(hidden)]
154mod const_asserts {
155    use static_assertions::{const_assert, const_assert_eq};
156
157    use super::*;
158
159    // Compare with original ssdeep constants
160    // fuzzy.c: HASH_INIT
161    const_assert_eq!(PartialFNVHash::FNV_HASH_INIT, 0x27);
162
163    // ALPHABET_SIZE and FNV_HASH_INIT properties (for PartialFNVHash)
164    const_assert!(0 < block_hash::ALPHABET_SIZE && block_hash::ALPHABET_SIZE <= 256);
165    const_assert!(block_hash::ALPHABET_SIZE.is_power_of_two());
166    const_assert!((PartialFNVHash::FNV_HASH_INIT as u16) < (block_hash::ALPHABET_SIZE as u16));
167}
168
169pub(crate) mod test_utils;
170mod tests;
ssdeep/internals/generate/hashes/partial_fnv.rs

ssdeep/internals/generate/hashes/
partial_fnv.rs
