Skip to main content

lattice_simd/
binary.rs

1//! Binary sign quantization and Hamming-distance operations.
2//!
3//! Packed format and partial-byte handling remain part of the API contract.
4//!
5//! See docs/simd.md for the format and cosine approximation.
6
7#[cfg(target_arch = "aarch64")]
8use std::arch::aarch64::*;
9
10#[cfg(target_arch = "x86_64")]
11use std::arch::x86_64::*;
12
13use super::simd_config;
14
15/// **Unstable**: binary quantization format and struct layout are under active design.
16///
17/// Binary quantized vector with packed bit storage.
18#[derive(Debug, Clone)]
19pub struct BinaryVector {
20    /// **Unstable**: packed bit data; bit layout may change with format revision.
21    pub data: Vec<u8>,
22    /// **Unstable**: number of original dimensions.
23    pub dims: usize,
24    /// **Unstable**: L2 norm of the original float vector; field may be removed.
25    pub norm: f32,
26}
27
28impl BinaryVector {
29    /// **Unstable**: quantization API; threshold default may change.
30    ///
31    /// Values >= threshold map to 1, values < threshold map to 0.
32    /// Default threshold is 0.0 (sign bit).
33    pub fn from_f32(vector: &[f32]) -> Self {
34        Self::from_f32_with_threshold(vector, 0.0)
35    }
36
37    /// **Unstable**: custom-threshold variant; may be merged into a config struct.
38    pub fn from_f32_with_threshold(vector: &[f32], threshold: f32) -> Self {
39        let dims = vector.len();
40
41        // Compute norm
42        let mut norm_sq = 0.0f32;
43        for &v in vector {
44            if v.is_finite() {
45                norm_sq += v * v;
46            }
47        }
48        let norm = norm_sq.sqrt();
49
50        let packed_len = dims.div_ceil(8);
51        let data = quantize_binary(vector, threshold, packed_len);
52
53        Self { data, dims, norm }
54    }
55
56    /// **Unstable**: dequantize to float32; output semantics may change.
57    ///
58    /// Binary quantization is lossy: 1 -> +1.0, 0 -> -1.0.
59    ///
60    /// Returns an empty `Vec` if the packed buffer is shorter than `dims.div_ceil(8)`
61    /// bytes — i.e. the vector was constructed with mismatched fields.
62    pub fn to_f32(&self) -> Vec<f32> {
63        let required_bytes = self.dims.div_ceil(8);
64        if self.data.len() < required_bytes {
65            return Vec::new();
66        }
67        let mut result = Vec::with_capacity(self.dims);
68        for i in 0..self.dims {
69            let byte_idx = i / 8;
70            let bit_idx = 7 - (i % 8);
71            let bit = (self.data[byte_idx] >> bit_idx) & 1;
72            result.push(if bit == 1 { 1.0 } else { -1.0 });
73        }
74        result
75    }
76
77    /// **Unstable**: Hamming dispatch; delegates to NEON or scalar based on runtime detection.
78    ///
79    /// Returns the number of differing bits (dimensions with different signs).
80    #[inline]
81    pub fn hamming_distance(&self, other: &BinaryVector) -> u32 {
82        hamming_distance_binary(self, other)
83    }
84
85    /// **Unstable**: approximation formula may be revised; do not use in latency-sensitive production paths.
86    ///
87    /// The relationship between Hamming distance and angular distance:
88    /// `cos_approx = 1.0 - 2.0 * hamming / dims`
89    /// `cosine_distance_approx = 2.0 * hamming / dims`
90    #[inline]
91    pub fn cosine_distance_approx(&self, other: &BinaryVector) -> f32 {
92        if self.dims == 0 {
93            return 0.0;
94        }
95        let hamming = self.hamming_distance(other) as f32;
96        2.0 * hamming / self.dims as f32
97    }
98
99    /// **Unstable**: approximation formula may be revised; complement of `cosine_distance_approx`.
100    #[inline]
101    pub fn cosine_similarity_approx(&self, other: &BinaryVector) -> f32 {
102        1.0 - self.cosine_distance_approx(other)
103    }
104}
105
106fn quantize_binary(vector: &[f32], threshold: f32, packed_len: usize) -> Vec<u8> {
107    #[cfg(target_arch = "x86_64")]
108    {
109        if simd_config().avx2_enabled {
110            // SAFETY: AVX2 was detected at runtime; the kernel bounds every load and store.
111            return unsafe { quantize_binary_avx2(vector, threshold, packed_len) };
112        }
113    }
114    #[cfg(target_arch = "aarch64")]
115    {
116        if simd_config().neon_enabled {
117            // SAFETY: NEON was detected at runtime; the kernel bounds every load and store.
118            return unsafe { quantize_binary_neon(vector, threshold, packed_len) };
119        }
120    }
121    quantize_binary_scalar(vector, threshold, packed_len)
122}
123
124fn quantize_binary_scalar(vector: &[f32], threshold: f32, packed_len: usize) -> Vec<u8> {
125    let mut data = vec![0u8; packed_len];
126    quantize_binary_scalar_tail(vector, threshold, &mut data, 0);
127    data
128}
129
130fn quantize_binary_scalar_tail(vector: &[f32], threshold: f32, data: &mut [u8], start: usize) {
131    for (i, &value) in vector.iter().enumerate().skip(start) {
132        let finite_value = if value.is_finite() { value } else { 0.0 };
133        if finite_value >= threshold {
134            data[i / 8] |= 1 << (7 - i % 8);
135        }
136    }
137}
138
139#[cfg(test)]
140thread_local! {
141    static BINARY_QUANTIZE_SIMD_HITS: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
142}
143
144#[cfg(target_arch = "x86_64")]
145#[target_feature(enable = "avx2")]
146unsafe fn quantize_binary_avx2(vector: &[f32], threshold: f32, packed_len: usize) -> Vec<u8> {
147    #[cfg(test)]
148    BINARY_QUANTIZE_SIMD_HITS.with(|hits| hits.set(hits.get() + 1));
149
150    let mut data = vec![0u8; packed_len];
151    let chunks = vector.len() / 8;
152    let threshold_scalar = threshold;
153    let sign = _mm256_set1_ps(-0.0);
154    let inf = _mm256_set1_ps(f32::INFINITY);
155    let threshold = _mm256_set1_ps(threshold_scalar);
156
157    for i in 0..chunks {
158        let input = _mm256_loadu_ps(vector.as_ptr().add(i * 8));
159        let abs = _mm256_andnot_ps(sign, input);
160        let finite = _mm256_cmp_ps(abs, inf, _CMP_LT_OQ);
161        let values = _mm256_and_ps(input, finite);
162        let above_threshold = _mm256_cmp_ps(values, threshold, _CMP_GE_OQ);
163        data[i] = (_mm256_movemask_ps(above_threshold) as u8).reverse_bits();
164    }
165
166    quantize_binary_scalar_tail(vector, threshold_scalar, &mut data, chunks * 8);
167    data
168}
169
170#[cfg(target_arch = "aarch64")]
171#[target_feature(enable = "neon")]
172unsafe fn quantize_binary_neon(vector: &[f32], threshold: f32, packed_len: usize) -> Vec<u8> {
173    #[cfg(test)]
174    BINARY_QUANTIZE_SIMD_HITS.with(|hits| hits.set(hits.get() + 1));
175
176    let mut data = vec![0u8; packed_len];
177    let chunks = vector.len() / 8;
178    let inf = vdupq_n_f32(f32::INFINITY);
179    let zero = vdupq_n_f32(0.0);
180    let threshold_vector = vdupq_n_f32(threshold);
181
182    for i in 0..chunks {
183        let base = i * 8;
184        let first = vld1q_f32(vector.as_ptr().add(base));
185        let second = vld1q_f32(vector.as_ptr().add(base + 4));
186        let first_values = vbslq_f32(vcaltq_f32(first, inf), first, zero);
187        let second_values = vbslq_f32(vcaltq_f32(second, inf), second, zero);
188        let first_mask = vcgeq_f32(first_values, threshold_vector);
189        let second_mask = vcgeq_f32(second_values, threshold_vector);
190        let mut first_lanes = [0u32; 4];
191        let mut second_lanes = [0u32; 4];
192        vst1q_u32(first_lanes.as_mut_ptr(), first_mask);
193        vst1q_u32(second_lanes.as_mut_ptr(), second_mask);
194
195        let mut packed = 0u8;
196        for (lane, mask) in first_lanes.into_iter().chain(second_lanes).enumerate() {
197            if mask != 0 {
198                packed |= 1 << (7 - lane);
199            }
200        }
201        data[i] = packed;
202    }
203
204    quantize_binary_scalar_tail(vector, threshold, &mut data, chunks * 8);
205    data
206}
207
208/// **Unstable**: returns packed-bit Hamming distance or `u32::MAX` for invalid inputs.
209///
210/// See [`docs/simd.md`](../docs/simd.md#binary-vectors) for packing, masking, and approximation semantics.
211#[inline]
212pub fn hamming_distance_binary(a: &BinaryVector, b: &BinaryVector) -> u32 {
213    if a.dims != b.dims {
214        return u32::MAX;
215    }
216
217    let required_bytes = a.dims.div_ceil(8);
218    if a.data.len() < required_bytes || b.data.len() < required_bytes {
219        return u32::MAX;
220    }
221
222    let config = simd_config();
223
224    #[cfg(target_arch = "aarch64")]
225    {
226        if config.neon_enabled {
227            // SAFETY: NEON is available on aarch64. Both slices have been verified above
228            // to contain at least `required_bytes` elements, which is the exact packed
229            // length for `dims` bits. The callee uses unaligned loads and chunk/remainder
230            // bounds strictly within those slices; no out-of-bounds read is possible.
231            return unsafe {
232                hamming_distance_neon(&a.data[..required_bytes], &b.data[..required_bytes], a.dims)
233            };
234        }
235    }
236
237    #[cfg(not(target_arch = "aarch64"))]
238    {
239        let _ = config;
240    }
241
242    hamming_distance_scalar(&a.data[..required_bytes], &b.data[..required_bytes], a.dims)
243}
244
245/// Computes Hamming distance with scalar popcount, masking a partial final byte.
246///
247/// See [`docs/simd.md`](../docs/simd.md#binary-vectors) for the MSB-first padding invariant.
248fn hamming_distance_scalar(a: &[u8], b: &[u8], dims: usize) -> u32 {
249    let mut total: u32 = 0;
250
251    // Number of fully-populated 8-byte chunks (all bits valid).
252    let full_bytes = dims / 8; // bytes where every bit is a real dimension
253    let chunks = full_bytes / 8;
254
255    // Process 8 bytes at a time as u64
256    for c in 0..chunks {
257        let offset = c * 8;
258        let a_u64 = u64::from_ne_bytes([
259            a[offset],
260            a[offset + 1],
261            a[offset + 2],
262            a[offset + 3],
263            a[offset + 4],
264            a[offset + 5],
265            a[offset + 6],
266            a[offset + 7],
267        ]);
268        let b_u64 = u64::from_ne_bytes([
269            b[offset],
270            b[offset + 1],
271            b[offset + 2],
272            b[offset + 3],
273            b[offset + 4],
274            b[offset + 5],
275            b[offset + 6],
276            b[offset + 7],
277        ]);
278        total += (a_u64 ^ b_u64).count_ones();
279    }
280
281    // Handle the remaining full bytes (between the last u64 chunk and the partial byte)
282    let remainder_start = chunks * 8;
283    for i in remainder_start..full_bytes {
284        total += (a[i] ^ b[i]).count_ones();
285    }
286
287    // Handle the single partial byte (if dims is not a multiple of 8).
288    // The `r` valid bits occupy the top `r` bits of the byte (MSB = dim 0 within byte).
289    let r = dims % 8;
290    if r != 0 {
291        let mask = 0xFFu8 << (8 - r); // top `r` bits set, bottom `(8-r)` clear
292        total += ((a[full_bytes] ^ b[full_bytes]) & mask).count_ones();
293    }
294
295    total
296}
297
298/// Computes Hamming distance with NEON `vcnt`, masking a partial final byte.
299///
300/// # Safety
301/// Caller must run on aarch64 with equal packed slices for `dims` dimensions.
302/// See [`docs/simd.md`](../docs/simd.md#binary-vectors) for the MSB-first padding invariant.
303#[cfg(target_arch = "aarch64")]
304#[inline]
305unsafe fn hamming_distance_neon(a: &[u8], b: &[u8], dims: usize) -> u32 {
306    // SA-163/164: verify equal-length backing slices before the SIMD loop.
307    debug_assert_eq!(
308        a.len(),
309        b.len(),
310        "hamming_distance_neon: slice lengths differ ({} vs {})",
311        a.len(),
312        b.len()
313    );
314
315    // Only full bytes (where every bit is a real dimension) go through the SIMD loop.
316    let full_bytes = dims / 8;
317    const SIMD_WIDTH: usize = 16;
318    let chunks = full_bytes / SIMD_WIDTH;
319
320    // Accumulate popcount bytes into u16 to avoid overflow
321    // (max 8 bits per byte, 16 bytes per register = 128 per chunk, fits u8 for ~1 chunk)
322    // Use vpaddlq to widen: u8 -> u16 -> u32 -> u64
323    let mut sum_u64 = vdupq_n_u64(0);
324
325    for c in 0..chunks {
326        let base = c * SIMD_WIDTH;
327        let va = vld1q_u8(a.as_ptr().add(base));
328        let vb = vld1q_u8(b.as_ptr().add(base));
329
330        // XOR to find differing bits
331        let xor = veorq_u8(va, vb);
332
333        // Population count per byte
334        let popcnt = vcntq_u8(xor);
335
336        // Widen and accumulate: u8 -> u16 -> u32 -> u64
337        let sum_u16 = vpaddlq_u8(popcnt);
338        let sum_u32 = vpaddlq_u16(sum_u16);
339        sum_u64 = vaddq_u64(sum_u64, vpaddlq_u32(sum_u32));
340    }
341
342    // Extract final sum
343    let total = vgetq_lane_u64(sum_u64, 0) + vgetq_lane_u64(sum_u64, 1);
344    let mut result = total as u32;
345
346    // Handle remaining full bytes (between last SIMD chunk and the partial byte)
347    let remainder_start = chunks * SIMD_WIDTH;
348    for i in remainder_start..full_bytes {
349        result += (a[i] ^ b[i]).count_ones();
350    }
351
352    // Handle the single partial byte (if dims is not a multiple of 8).
353    // Top `r` bits are real dimensions; bottom `(8 - r)` bits are padding.
354    let r = dims % 8;
355    if r != 0 {
356        let mask = 0xFFu8 << (8 - r); // top `r` bits set, bottom `(8-r)` clear
357        result += ((a[full_bytes] ^ b[full_bytes]) & mask).count_ones();
358    }
359
360    result
361}
362
363#[cfg(test)]
364mod tests;