fast-tlsh 0.1.1

Library to generate / parse / compare TLSH locality sensitive hashes
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

// SPDX-License-Identifier: Apache-2.0 OR MIT
// SPDX-FileCopyrightText: Copyright (C) 2024 Tsukasa OI <floss_ssdeep@irq.a4lg.com>.

//! Tests: [`crate::compare::dist_body`].

#![cfg(test)]

use super::naive::{self, distance_dibits};
use super::{pseudo_simd_32, pseudo_simd_64};

use crate::hash::body::{BODY_SIZE_LONG, BODY_SIZE_NORMAL, BODY_SIZE_SHORT};

#[test]
fn max_quartile_distance() {
    // Before substitution by BODY_OUTLIAR_VALUE, the maximum value is 3.
    for x in 0b00..=0b11u8 {
        for y in 0b00..=0b11u8 {
            assert!(x.abs_diff(y) <= 0b11);
        }
    }
}

trait BodyDistanceImpls<const SIZE_BODY: usize> {
    fn naive(body1: &[u8; SIZE_BODY], body2: &[u8; SIZE_BODY]) -> u32;
    fn fast(body1: &[u8; SIZE_BODY], body2: &[u8; SIZE_BODY]) -> u32;
    fn pseudo_simd_32(body1: &[u8; SIZE_BODY], body2: &[u8; SIZE_BODY]) -> u32;
    fn pseudo_simd_64(body1: &[u8; SIZE_BODY], body2: &[u8; SIZE_BODY]) -> u32;
}

struct BodyDistance<const SIZE_BODY: usize>;

impl BodyDistanceImpls<BODY_SIZE_SHORT> for BodyDistance<BODY_SIZE_SHORT> {
    fn naive(body1: &[u8; BODY_SIZE_SHORT], body2: &[u8; BODY_SIZE_SHORT]) -> u32 {
        naive::distance(body1, body2)
    }

    fn fast(body1: &[u8; BODY_SIZE_SHORT], body2: &[u8; BODY_SIZE_SHORT]) -> u32 {
        super::distance_12(body1, body2)
    }

    fn pseudo_simd_32(body1: &[u8; BODY_SIZE_SHORT], body2: &[u8; BODY_SIZE_SHORT]) -> u32 {
        pseudo_simd_32::distance_12(body1, body2)
    }

    fn pseudo_simd_64(body1: &[u8; BODY_SIZE_SHORT], body2: &[u8; BODY_SIZE_SHORT]) -> u32 {
        // THIS IS INTENTIONAL (since there's no distance_12 on pseudo_simd_32)
        pseudo_simd_32::distance_12(body1, body2)
    }
}

impl BodyDistanceImpls<BODY_SIZE_NORMAL> for BodyDistance<BODY_SIZE_NORMAL> {
    fn naive(body1: &[u8; BODY_SIZE_NORMAL], body2: &[u8; BODY_SIZE_NORMAL]) -> u32 {
        naive::distance(body1, body2)
    }

    fn fast(body1: &[u8; BODY_SIZE_NORMAL], body2: &[u8; BODY_SIZE_NORMAL]) -> u32 {
        super::distance_32(body1, body2)
    }

    fn pseudo_simd_32(body1: &[u8; BODY_SIZE_NORMAL], body2: &[u8; BODY_SIZE_NORMAL]) -> u32 {
        pseudo_simd_32::distance_32(body1, body2)
    }

    fn pseudo_simd_64(body1: &[u8; BODY_SIZE_NORMAL], body2: &[u8; BODY_SIZE_NORMAL]) -> u32 {
        pseudo_simd_64::distance_32(body1, body2)
    }
}

impl BodyDistanceImpls<BODY_SIZE_LONG> for BodyDistance<BODY_SIZE_LONG> {
    fn naive(body1: &[u8; BODY_SIZE_LONG], body2: &[u8; BODY_SIZE_LONG]) -> u32 {
        naive::distance(body1, body2)
    }

    fn fast(body1: &[u8; BODY_SIZE_LONG], body2: &[u8; BODY_SIZE_LONG]) -> u32 {
        super::distance_64(body1, body2)
    }

    fn pseudo_simd_32(body1: &[u8; BODY_SIZE_LONG], body2: &[u8; BODY_SIZE_LONG]) -> u32 {
        pseudo_simd_32::distance_64(body1, body2)
    }

    fn pseudo_simd_64(body1: &[u8; BODY_SIZE_LONG], body2: &[u8; BODY_SIZE_LONG]) -> u32 {
        pseudo_simd_64::distance_64(body1, body2)
    }
}

#[test]
fn equivalence_optimized_impl() {
    fn test<const SIZE_BODY: usize>()
    where
        BodyDistance<SIZE_BODY>: BodyDistanceImpls<SIZE_BODY>,
    {
        // Single dibit difference
        for index in 0..SIZE_BODY * 4 {
            for a in 0..4 {
                let mut body_a = [0u8; SIZE_BODY];
                body_a[SIZE_BODY - 1 - index / 4] |= a << (2 * (index % 4));
                let body_a = body_a;
                for b in 0..4 {
                    let mut body_b = [0u8; SIZE_BODY];
                    body_b[SIZE_BODY - 1 - index / 4] |= b << (2 * (index % 4));
                    let body_b = body_b;
                    let expected = distance_dibits(a, b);
                    assert_eq!(BodyDistance::<SIZE_BODY>::naive(&body_a, &body_b), expected);
                    assert_eq!(BodyDistance::<SIZE_BODY>::fast(&body_a, &body_b), expected);
                    assert_eq!(
                        BodyDistance::<SIZE_BODY>::pseudo_simd_32(&body_a, &body_b),
                        expected
                    );
                    assert_eq!(
                        BodyDistance::<SIZE_BODY>::pseudo_simd_64(&body_a, &body_b),
                        expected
                    );
                }
            }
        }
        // All dibit difference
        for a in 0..4 {
            let value_a = (0..4).fold(0u8, |x, _| (x << 2) | a);
            let body_a = [value_a; SIZE_BODY];
            for b in 0..4 {
                let value_b = (0..4).fold(0u8, |x, _| (x << 2) | b);
                let body_b = [value_b; SIZE_BODY];
                let expected = distance_dibits(a, b) * (SIZE_BODY * 4) as u32;
                assert_eq!(BodyDistance::<SIZE_BODY>::naive(&body_a, &body_b), expected);
                assert_eq!(BodyDistance::<SIZE_BODY>::fast(&body_a, &body_b), expected);
                assert_eq!(
                    BodyDistance::<SIZE_BODY>::pseudo_simd_32(&body_a, &body_b),
                    expected
                );
                assert_eq!(
                    BodyDistance::<SIZE_BODY>::pseudo_simd_64(&body_a, &body_b),
                    expected
                );
            }
        }
    }
    test::<BODY_SIZE_SHORT>();
    test::<BODY_SIZE_NORMAL>();
    test::<BODY_SIZE_LONG>();
}