superbit/simhash/
bitarray.rs

1//! Fixed-size bit array. `LANES` = number of 64-bit words.
2//! Total bits = `LANES * 64`.  Works on stable Rust.
3
4use core::{
5    cmp::Ordering,
6    fmt,
7    hash::{Hash, Hasher},
8    ops::*,
9};
10use num_traits::{One, Zero};
11
12#[derive(Clone, Copy)]
13pub struct BitArray<const LANES: usize> {
14    lanes: [u64; LANES],
15}
16impl<const LANES: usize> Default for BitArray<LANES> {
17    fn default() -> Self {
18        Self {
19            lanes: [0u64; LANES],
20        }
21    }
22}
23
24// simple traits
25
26impl<const L: usize> fmt::Debug for BitArray<L> {
27    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
28        write!(f, "BitArray<{}×64>(…)", L)
29    }
30}
31impl<const L: usize> PartialEq for BitArray<L> {
32    fn eq(&self, o: &Self) -> bool {
33        self.lanes == o.lanes
34    }
35}
36impl<const L: usize> Eq for BitArray<L> {}
37impl<const L: usize> PartialOrd for BitArray<L> {
38    fn partial_cmp(&self, o: &Self) -> Option<Ordering> {
39        Some(self.lanes.cmp(&o.lanes))
40    }
41}
42impl<const L: usize> Hash for BitArray<L> {
43    fn hash<H: Hasher>(&self, st: &mut H) {
44        for &x in &self.lanes {
45            st.write_u64(x)
46        }
47    }
48}
49
50/* ---------- Zero / One (need Add / Mul dummies) -------------------------- */
51
52impl<const L: usize> Add for BitArray<L> {
53    type Output = Self;
54    fn add(self, _: Self) -> Self {
55        self
56    }
57}
58impl<const L: usize> Mul for BitArray<L> {
59    type Output = Self;
60    fn mul(self, _: Self) -> Self {
61        self
62    }
63}
64
65impl<const L: usize> Zero for BitArray<L> {
66    fn zero() -> Self {
67        Self { lanes: [0; L] }
68    }
69    fn is_zero(&self) -> bool {
70        self.lanes.iter().all(|&x| x == 0)
71    }
72}
73impl<const L: usize> One for BitArray<L> {
74    fn one() -> Self {
75        let mut a = [0u64; L];
76        a[0] = 1;
77        Self { lanes: a }
78    }
79}
80
81/* ---------- bitwise ops -------------------------------------------------- */
82
83macro_rules! impl_bin {
84    ($Trait:ident,$func:ident,$op:tt) => {
85        impl<const L: usize> $Trait for BitArray<L>{
86            type Output = Self;
87            fn $func(mut self, rhs:Self)->Self{
88                for (a,b) in self.lanes.iter_mut().zip(rhs.lanes){ *a = *a $op b }
89                self
90            }
91        }
92        impl<const L: usize> $Trait<&Self> for BitArray<L>{
93            type Output = Self;
94            fn $func(self, rhs:&Self)->Self{ self.$func(*rhs) }
95        }
96    };
97}
98impl_bin!(BitOr,  bitor , |);
99impl_bin!(BitAnd, bitand, &);
100impl_bin!(BitXor, bitxor, ^);
101
102impl<const L: usize> Not for BitArray<L> {
103    type Output = Self;
104    fn not(mut self) -> Self {
105        for x in &mut self.lanes {
106            *x = !*x
107        }
108        self
109    }
110}
111impl<const L: usize> BitOrAssign for BitArray<L> {
112    fn bitor_assign(&mut self, rhs: Self) {
113        for (a, b) in self.lanes.iter_mut().zip(rhs.lanes) {
114            *a |= b;
115        }
116    }
117}
118
119/* ---------- shifts ------------------------------------------------------- */
120
121impl<const L: usize> ShlAssign<usize> for BitArray<L> {
122    fn shl_assign(&mut self, n: usize) {
123        let words = n / 64;
124        let bits = n % 64;
125        if words > 0 {
126            for i in (0..L).rev() {
127                self.lanes[i] = if i >= words { self.lanes[i - words] } else { 0 };
128            }
129        }
130        if bits > 0 {
131            for i in (0..L).rev() {
132                self.lanes[i] <<= bits;
133                if i > 0 {
134                    self.lanes[i] |= self.lanes[i - 1] >> (64 - bits);
135                }
136            }
137        }
138    }
139}
140impl<const L: usize> Shl<usize> for BitArray<L> {
141    type Output = Self;
142    fn shl(mut self, n: usize) -> Self {
143        self <<= n;
144        self
145    }
146}
147
148impl<const L: usize> ShrAssign<usize> for BitArray<L> {
149    fn shr_assign(&mut self, n: usize) {
150        let words = n / 64;
151        let bits = n % 64;
152        if words > 0 {
153            for i in 0..L {
154                self.lanes[i] = if i + words < L {
155                    self.lanes[i + words]
156                } else {
157                    0
158                };
159            }
160        }
161        if bits > 0 {
162            for i in 0..L {
163                self.lanes[i] >>= bits;
164                if i + 1 < L {
165                    self.lanes[i] |= self.lanes[i + 1] << (64 - bits);
166                }
167            }
168        }
169    }
170}
171impl<const L: usize> Shr<usize> for BitArray<L> {
172    type Output = Self;
173    fn shr(mut self, n: usize) -> Self {
174        self >>= n;
175        self
176    }
177}
178
179impl<const L: usize> super::SimHashBits for BitArray<L> {
180    fn count_ones(self) -> usize {
181        self.lanes.iter().map(|x| x.count_ones() as usize).sum()
182    }
183    fn to_u32_high_bits(self) -> u32 {
184        (self.lanes[L - 1] >> 32) as u32
185    }
186    fn to_u64_high_bits(self) -> u64 {
187        self.lanes[L - 1]
188    }
189    fn hamming_distance(&self, r: &Self) -> usize {
190        self.lanes
191            .iter()
192            .zip(r.lanes)
193            .map(|(a, b)| (a ^ b).count_ones() as usize)
194            .sum()
195    }
196    fn bit_length() -> usize {
197        L * 64
198    }
199}
superbit/simhash/bitarray.rs

superbit/simhash/
bitarray.rs
