ssdeep/generate/hashes/

partial_fnv.rs

// SPDX-License-Identifier: GPL-2.0-or-later
// SPDX-FileCopyrightText: Copyright Andrew Tridgell <tridge@samba.org> 2002
// SPDX-FileCopyrightText: Copyright (C) 2006 ManTech International Corporation
// SPDX-FileCopyrightText: Copyright (C) 2013 Helmut Grohne <helmut@subdivi.de>
// SPDX-FileCopyrightText: Copyright (C) 2017, 2023–2025 Tsukasa OI <floss_ssdeep@irq.a4lg.com>

//! Partial FNV-1 hash as used in the fuzzy hash generator.

use core::ops::AddAssign;

use crate::hash::block::block_hash;

#[cfg(not(feature = "opt-reduce-fnv-table"))]
use crate::macros::invariant;

/// Hasher which computes the lowest 6 bits of a 32-bit FNV-1 variant.
///
/// This variant of FNV-1 hash has the regular prime constant of `0x01000193`
/// but has a different initial state: `0x28021967` (in contrast to regular
/// FNV-1-32's `0x811c9dc5`).
///
/// Since ssdeep only uses the lowest 6 bits of the hash value, it ignores any
/// higher bits, enabling updating the state table-based (instead of multiply
/// and xor).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct PartialFNVHash(u8);

impl PartialFNVHash {
    /// The initial value of this variant of the FNV-1 hash (`0x28021967`).
    ///
    /// This is different from the regular variant of the FNV-1 hash
    /// (FNV-1-32: `0x811c9dc5`).
    const OLD_HASH_INIT: u32 = 0x28021967;

    /// The initial value of this variant of the partial FNV-1 hash.
    ///
    /// This is generated by masking [`Self::OLD_HASH_INIT`].
    const FNV_HASH_INIT: u8 = (Self::OLD_HASH_INIT % block_hash::ALPHABET_SIZE as u32) as u8;

    /// The prime constant for the FNV-1 hash.
    ///
    /// This is the same as the regular FNV-1.
    const FNV_HASH_PRIME: u32 = 0x01000193;

    /// The partial FNV-1 update table.
    ///
    /// This is used by the [`update_by_byte()`](Self::update_by_byte()) method
    /// to update the current state using a new byte, unless the feature
    /// `opt-reduce-fnv-table` is enabled.
    #[cfg(not(feature = "opt-reduce-fnv-table"))]
    const FNV_TABLE: [[u8; block_hash::ALPHABET_SIZE]; block_hash::ALPHABET_SIZE] = {
        let mut array = [[0u8; block_hash::ALPHABET_SIZE]; block_hash::ALPHABET_SIZE];
        let mut state = 0u8;
        while state < 64 {
            let mut ch = 0u8;
            while ch < 64 {
                array[state as usize][ch as usize] =
                    (((state as u32).wrapping_mul(Self::FNV_HASH_PRIME) as u8) ^ ch)
                        % block_hash::ALPHABET_SIZE as u8;
                ch += 1;
            }
            state += 1;
        }
        array
    };

    /// Creates a new [`PartialFNVHash`] with the initial value.
    #[inline]
    pub fn new() -> Self {
        PartialFNVHash(Self::FNV_HASH_INIT)
    }

    /// Updates the hash value by processing a byte.
    #[inline]
    pub fn update_by_byte(&mut self, ch: u8) -> &mut Self {
        cfg_if::cfg_if! {
            if #[cfg(not(feature = "opt-reduce-fnv-table"))] {
                invariant!((self.value() as usize) < block_hash::ALPHABET_SIZE);
                self.0 = Self::FNV_TABLE
                    [self.value() as usize] // grcov-excl-br-line:ARRAY
                    [ch as usize % block_hash::ALPHABET_SIZE]; // grcov-excl-br-line:ARRAY
            } else {
                self.0 = ((self.0 as u32).wrapping_mul(Self::FNV_HASH_PRIME) ^ (ch as u32)) as u8;
            }
        }
        self
    }

    /// Updates the hash value by processing an iterator of [`u8`].
    pub fn update_by_iter(&mut self, iter: impl Iterator<Item = u8>) -> &mut Self {
        for ch in iter {
            self.update_by_byte(ch);
        }
        self
    }

    /// Updates the hash value by processing a slice of [`u8`].
    pub fn update(&mut self, buf: &[u8]) -> &mut Self {
        for &ch in buf.iter() {
            self.update_by_byte(ch);
        }
        self
    }

    /// Returns the current hash value.
    ///
    /// Note that there's no "finalization" on the FNV hash.
    /// You can even continue updating after reading the hash value.
    #[inline]
    pub fn value(&self) -> u8 {
        cfg_if::cfg_if! {
            if #[cfg(not(feature = "opt-reduce-fnv-table"))] {
                invariant!(self.0 < (block_hash::ALPHABET_SIZE as u8));
                self.0
            } else {
                self.0 & (block_hash::ALPHABET_SIZE as u8).wrapping_sub(1)
            }
        }
    }
}

impl Default for PartialFNVHash {
    fn default() -> Self {
        Self::new()
    }
}

impl AddAssign<&[u8]> for PartialFNVHash {
    /// Updates the hash value by processing a slice of [`u8`].
    #[inline(always)]
    fn add_assign(&mut self, buffer: &[u8]) {
        self.update(buffer);
    }
}

impl<const N: usize> AddAssign<&[u8; N]> for PartialFNVHash {
    /// Updates the hash value by processing an array of [`u8`].
    #[inline(always)]
    fn add_assign(&mut self, buffer: &[u8; N]) {
        self.update(&buffer[..]);
    }
}

impl AddAssign<u8> for PartialFNVHash {
    /// Updates the hash value by processing a byte.
    #[inline(always)]
    fn add_assign(&mut self, byte: u8) {
        self.update_by_byte(byte);
    }
}

/// Constant assertions related to this module.
#[doc(hidden)]
mod const_asserts {
    use static_assertions::{const_assert, const_assert_eq};

    use super::*;

    // Compare with original ssdeep constants
    // fuzzy.c: HASH_INIT
    const_assert_eq!(PartialFNVHash::FNV_HASH_INIT, 0x27);

    // ALPHABET_SIZE and FNV_HASH_INIT properties (for PartialFNVHash)
    const_assert!(0 < block_hash::ALPHABET_SIZE && block_hash::ALPHABET_SIZE <= 256);
    const_assert!(block_hash::ALPHABET_SIZE.is_power_of_two());
    const_assert!((PartialFNVHash::FNV_HASH_INIT as u16) < (block_hash::ALPHABET_SIZE as u16));
}

pub(crate) mod test_utils;
mod tests;