Trait ssdeep::internal_comparison::BlockHashPositionArrayImplUnsafe

pub unsafe trait BlockHashPositionArrayImplUnsafe: BlockHashPositionArrayData {
    // Required methods
    unsafe fn is_equiv_unchecked(&self, other: &[u8]) -> bool;
    unsafe fn has_common_substring_unchecked(&self, other: &[u8]) -> bool;
    unsafe fn edit_distance_unchecked(&self, other: &[u8]) -> u32;
    unsafe fn score_strings_raw_unchecked(&self, other: &[u8]) -> u32;
    unsafe fn score_strings_unchecked(
        &self,
        other: &[u8],
        log_block_size: u8
    ) -> u32;
}

Available on crate feature unsafe only.

The implementation of the block hash position array (unsafe; immutable).

Safety

This trait contains unsafe methods and need to comply with constraints described in each method.

Required Methods

unsafe fn is_equiv_unchecked(&self, other: &[u8]) -> bool

Compare whether two block hashes are equivalent.

Safety

• The length of other must not exceed 64.
• All elements in other must be less than BlockHash::ALPHABET_SIZE.

If they are not satisfied, it will return a meaningless value.

unsafe fn has_common_substring_unchecked(&self, other: &[u8]) -> bool

Checks whether two given strings have common substrings with a length of BlockHash::MIN_LCS_FOR_COMPARISON.

Algorithm Implemented (By Default)

This function implements a Boyer–Moore-like bit-parallel algorithm to find a fixed-length common substring. The original algorithm is the Backward Shift-Add algorithm for the k-LCF problem [Hirvola, 2016] (which searches the longest common substring with up to k errors under the Hamming distance).

This algorithm is modified:

• to search only perfect matches (up to 0 errors),
• to return as soon as possible if it finds a common substring and
• to share the position array representation with BlockHashPositionArrayImpl::edit_distance (the original algorithm used reverse “incidence matrix”).

Safety

• All elements in other must be less than BlockHash::ALPHABET_SIZE.

If the condition above is not satisfied, it will return a meaningless value.

unsafe fn edit_distance_unchecked(&self, other: &[u8]) -> u32

Computes the edit distance between two given strings.

Specifically, it computes the Longest Common Subsequence (LCS) distance, allowing character insertion and deletion as two primitive operations (in cost 1).

Algorithm Implemented (By Default)

[Hyyrö et al., 2005] (doi:10.1007/11427186_33) presented a way to compute so called Indel-Distance using a bit-parallel approach and this method is based on it.

This algorithm is needed to be modified for our purpose because the purpose of the original algorithm is to find a “substring” similar to a pattern string.

Safety

• The length of other must be short enough (up to BlockHash::FULL_SIZE is guaranteed to be safe).
• All elements in other must be less than BlockHash::ALPHABET_SIZE.

If they are not satisfied, it will return a meaningless distance.

unsafe fn score_strings_raw_unchecked(&self, other: &[u8]) -> u32

Compare two block hashes and computes the similarity score without capping.

This method does not “cap” the score to prevent exaggregating the matches that are not meaningful enough, making this function block size independent.

Safety

• The lengths of both self and other must not exceed BlockHash::FULL_SIZE.
• All elements in other must be less than BlockHash::ALPHABET_SIZE.

If they are not satisfied, it will return a meaningless score.

unsafe fn score_strings_unchecked( &self, other: &[u8], log_block_size: u8 ) -> u32

Compare two block hashes and computes the similarity score.

This method “caps” the score to prevent exaggregating the matches that are not meaningful enough. This behavior depends on the block size (score cap gets higher when block size gets higher).

Safety

• The lengths of both self and other must not exceed BlockHash::FULL_SIZE.
• All elements in other must be less than BlockHash::ALPHABET_SIZE.
• log_block_size must be valid or must be equal to BlockSize::NUM_VALID (this value itself is not valid as a block size for a fuzzy hash object but valid for this method).

If they are not satisfied, it will return a meaningless score.

Implementors

impl<T> BlockHashPositionArrayImplUnsafe for Twhere T: BlockHashPositionArrayImplInternal,