gear-fingerprinter 0.0.0

GEAR and MinHash based data fingerprinting
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

use crate::consts::{gear, Aligned, M_TABLE, N_TABLE};
use crate::Fingerprint;

#[cfg(target_arch = "x86")]
use core::arch::x86::{
    __m128i, __m256i, _mm256_add_epi32, _mm256_load_si256, _mm256_min_epu32, _mm256_mullo_epi32,
    _mm256_set1_epi32, _mm256_set1_epi8, _mm256_store_si256, _mm_add_epi32, _mm_load_si128,
    _mm_min_epu32, _mm_mullo_eip32, _mm_set1_epi32, _mm_set1_epi8, _mm_store_si128,
};
#[cfg(target_arch = "x86_64")]
use core::arch::x86_64::{
    __m128i, __m256i, _mm256_add_epi32, _mm256_load_si256, _mm256_min_epu32, _mm256_mullo_epi32,
    _mm256_set1_epi32, _mm256_set1_epi8, _mm256_store_si256, _mm_add_epi32, _mm_load_si128,
    _mm_min_epu32, _mm_mullo_epi32, _mm_set1_epi32, _mm_set1_epi8, _mm_store_si128,
};

/// Reforms GEAR based MinHash fingerprinting of the provided data, using an AVX2
/// accelerated implementation to handle multiple derived hashes in parallel
#[target_feature(enable = "avx")]
#[target_feature(enable = "avx2")]
pub unsafe fn fingerprint_avx2(bytes: &[u8]) -> Fingerprint {
    let mut mins = Aligned([_mm256_set1_epi8(i8::MIN); 3]);
    let mut hash = 0;
    for byte in bytes {
        hash = gear(hash, *byte);
        let hash_vector = _mm256_set1_epi32(hash as i32);
        for (i, min) in mins.0.iter_mut().enumerate() {
            let x = _mm256_mullo_epi32(
                hash_vector,
                _mm256_load_si256(N_TABLE.0[i * 8..].as_ptr() as *const __m256i),
            );

            let x = _mm256_add_epi32(
                x,
                _mm256_load_si256(M_TABLE.0[i * 8..].as_ptr() as *const __m256i),
            );
            *min = _mm256_min_epu32(x, *min);
        }
    }
    let mut ret = Aligned([0_u32; 24]);
    for (i, min) in mins.0.iter().enumerate() {
        _mm256_store_si256((&mut ret.0[i * 8..]).as_mut_ptr() as *mut __m256i, *min);
    }
    Fingerprint { fingerprint: ret.0 }
}

#[target_feature(enable = "sse2")]
#[target_feature(enable = "sse4.1")]
pub unsafe fn fingerprint_sse41(bytes: &[u8]) -> Fingerprint {
    let mut mins = Aligned([_mm_set1_epi8(i8::MIN); 6]);
    let mut hash = 0;
    for byte in bytes {
        hash = gear(hash, *byte);
        let hash_vector = _mm_set1_epi32(hash as i32);
        for (i, min) in mins.0.iter_mut().enumerate() {
            let x = _mm_mullo_epi32(
                hash_vector,
                _mm_load_si128(N_TABLE.0[i * 4..].as_ptr() as *const __m128i),
            );

            let x = _mm_add_epi32(
                x,
                _mm_load_si128(M_TABLE.0[i * 4..].as_ptr() as *const __m128i),
            );

            *min = _mm_min_epu32(x, *min);
        }
    }
    let mut ret = Aligned([0_u32; 24]);
    for (i, min) in mins.0.iter().enumerate() {
        _mm_store_si128((&mut ret.0[i * 4..]).as_mut_ptr() as *mut __m128i, *min);
    }

    Fingerprint { fingerprint: ret.0 }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::raw::fingerprint_scalar;
    use crate::test_utils::make_data;
    use rand::prelude::*;
    use rand_chacha::*;
    #[test]
    fn avx2_once() {
        let mut data = [0_u8; 16001];
        let mut rand = ChaChaRng::seed_from_u64(0);
        rand.fill(&mut data[..]);
        let scan = fingerprint_scalar(&data[..]);
        let scan_avx2 = unsafe { fingerprint_avx2(&data[..]) };
        assert_eq!(scan, scan_avx2);
    }

    #[test]
    fn sse41_once() {
        let mut data = [0_u8; 16001];
        let mut rand = ChaChaRng::seed_from_u64(0);
        rand.fill(&mut data[..]);
        let scan = fingerprint_scalar(&data[..]);
        let scan_avx2 = unsafe { fingerprint_sse41(&data[..]) };
        assert_eq!(scan, scan_avx2);
    }

    #[test]
    fn avx2_100() {
        for i in 0..100 {
            let data = make_data(i);
            let scan = fingerprint_scalar(&data[..]);
            let scan_avx2 = unsafe { fingerprint_avx2(&data[..]) };
            println!("Iteration: {}, data length: {}", i, data.len());
            assert_eq!(scan, scan_avx2);
        }
    }

    #[test]
    fn sse41_100() {
        for i in 0..100 {
            let data = make_data(i);
            let scan = fingerprint_scalar(&data[..]);
            let scan_avx2 = unsafe { fingerprint_sse41(&data[..]) };
            println!("Iteration: {}, data length: {}", i, data.len());
            assert_eq!(scan, scan_avx2);
        }
    }
}