Skip to main content

nodedb_vector/distance/simd/
hamming.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! Fast Hamming distance using u64 POPCNT.
4
5pub fn fast_hamming(a: &[u8], b: &[u8]) -> u32 {
6    assert_eq!(a.len(), b.len(), "fast_hamming: length mismatch");
7    let mut dist = 0u32;
8    let chunks = a.len() / 8;
9    for i in 0..chunks {
10        let off = i * 8;
11        let xa = u64::from_le_bytes([
12            a[off],
13            a[off + 1],
14            a[off + 2],
15            a[off + 3],
16            a[off + 4],
17            a[off + 5],
18            a[off + 6],
19            a[off + 7],
20        ]);
21        let xb = u64::from_le_bytes([
22            b[off],
23            b[off + 1],
24            b[off + 2],
25            b[off + 3],
26            b[off + 4],
27            b[off + 5],
28            b[off + 6],
29            b[off + 7],
30        ]);
31        dist += (xa ^ xb).count_ones();
32    }
33    for i in (chunks * 8)..a.len() {
34        dist += (a[i] ^ b[i]).count_ones();
35    }
36    dist
37}