csm_core_lib/
hyperdim_binary.rs

1//! Binary Hypervectors (ADR-0075)
2//!
3//! 10240-bit hypervectors packed into 160 x u64 words.
4//! Provides 32x compression compared to f32 hypervectors.
5#![allow(clippy::cast_precision_loss, clippy::cast_possible_truncation)]
6
7use crate::error::{MemoryError, Result};
8use crate::hyperdim::{HVec10240, Hypervector};
9use crate::hyperdim_ops::bundle_word_u64;
10use rand::RngExt;
11
12#[cfg(all(not(target_arch = "wasm32"), feature = "parallel"))]
13use rayon::prelude::*;
14
15use serde::de::{self, Visitor};
16use serde::{Deserialize, Deserializer, Serialize, Serializer};
17use std::fmt;
18
19#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
20#[must_use]
21pub struct BHVec10240 {
22    pub bits: [u64; 160],
23}
24
25impl Serialize for BHVec10240 {
26    fn serialize<S>(&self, serializer: S) -> std::result::Result<S::Ok, S::Error>
27    where
28        S: Serializer,
29    {
30        if serializer.is_human_readable() {
31            use base64::Engine;
32            use base64::engine::general_purpose::STANDARD;
33            let bytes = self.to_bytes();
34            let b64 = STANDARD.encode(&bytes);
35            serializer.serialize_str(&b64)
36        } else {
37            let bytes = self.to_bytes();
38            serializer.serialize_bytes(&bytes)
39        }
40    }
41}
42
43struct BHVecVisitor;
44
45impl<'de> Visitor<'de> for BHVecVisitor {
46    type Value = BHVec10240;
47
48    fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
49        formatter.write_str("a base64-encoded string or byte array")
50    }
51
52    fn visit_str<E>(self, v: &str) -> std::result::Result<Self::Value, E>
53    where
54        E: de::Error,
55    {
56        use base64::Engine;
57        use base64::engine::general_purpose::STANDARD;
58        let bytes = STANDARD.decode(v).map_err(de::Error::custom)?;
59        BHVec10240::from_bytes(&bytes).map_err(de::Error::custom)
60    }
61
62    fn visit_bytes<E>(self, v: &[u8]) -> std::result::Result<Self::Value, E>
63    where
64        E: de::Error,
65    {
66        BHVec10240::from_bytes(v).map_err(de::Error::custom)
67    }
68}
69
70impl<'de> Deserialize<'de> for BHVec10240 {
71    fn deserialize<D>(deserializer: D) -> std::result::Result<Self, D::Error>
72    where
73        D: Deserializer<'de>,
74    {
75        if deserializer.is_human_readable() {
76            deserializer.deserialize_any(BHVecVisitor)
77        } else {
78            let bytes = <Vec<u8>>::deserialize(deserializer)?;
79            Self::from_bytes(&bytes).map_err(de::Error::custom)
80        }
81    }
82}
83
84impl Hypervector for BHVec10240 {
85    const DIMENSION: usize = 10240;
86    const FORMAT_NAME: &'static str = "binary";
87
88    fn zero() -> Self {
89        Self::zero()
90    }
91
92    fn random() -> Self {
93        Self::random()
94    }
95
96    fn new_seeded(seed: u64) -> Self {
97        Self::new_seeded(seed)
98    }
99
100    fn bundle(vectors: &[&Self]) -> Result<Self> {
101        Ok(Self::bundle(vectors))
102    }
103
104    fn bind(&self, other: &Self) -> Self {
105        self.xor(other)
106    }
107
108    fn cosine_similarity(&self, other: &Self) -> f32 {
109        self.cosine_similarity(other)
110    }
111
112    fn hamming_distance(&self, other: &Self) -> u32 {
113        self.hamming(other)
114    }
115
116    fn permute(&self, shift: usize) -> Self {
117        self.permute(shift)
118    }
119
120    fn to_bytes(&self) -> Vec<u8> {
121        self.to_bytes()
122    }
123
124    fn from_bytes(bytes: &[u8]) -> Result<Self> {
125        Self::from_bytes(bytes)
126    }
127}
128
129impl BHVec10240 {
130    pub const DIMENSION: usize = 10240;
131    pub const WORDS: usize = 160;
132
133    /// Create a new hypervector with all zeros
134    pub const fn zero() -> Self {
135        Self { bits: [0u64; 160] }
136    }
137
138    /// Create a random hypervector
139    pub fn random() -> Self {
140        let mut rng = rand::rng();
141        let mut bits = [0u64; 160];
142        rng.fill(&mut bits);
143        Self { bits }
144    }
145
146    /// Create a deterministic random hypervector from a seed
147    pub fn new_seeded(seed: u64) -> Self {
148        use rand::SeedableRng;
149        use rand::rngs::StdRng;
150        let mut rng = StdRng::seed_from_u64(seed);
151        let mut bits = [0u64; 160];
152        rng.fill(&mut bits);
153        Self { bits }
154    }
155
156    /// Convert HVec10240 (bit-packed u128) to BHVec10240 (bit-packed u64)
157    /// This is just a layout conversion.
158    pub fn from_hvec(v: &HVec10240) -> Self {
159        let mut bits = [0u64; 160];
160        for i in 0..80 {
161            bits[i * 2] = v.data[i] as u64;
162            bits[i * 2 + 1] = (v.data[i] >> 64) as u64;
163        }
164        Self { bits }
165    }
166
167    /// Convert BHVec10240 (bit-packed u64) to HVec10240 (bit-packed u128)
168    pub fn to_hvec(&self) -> HVec10240 {
169        let mut data = [0u128; 80];
170        for i in 0..80 {
171            data[i] = (self.bits[i * 2] as u128) | ((self.bits[i * 2 + 1] as u128) << 64);
172        }
173        HVec10240 { data }
174    }
175
176    /// XOR binding
177    pub fn xor(&self, other: &Self) -> Self {
178        let mut result = [0u64; 160];
179        for i in 0..160 {
180            result[i] = self.bits[i] ^ other.bits[i];
181        }
182        Self { bits: result }
183    }
184
185    /// Hamming distance (popcount of XOR)
186    pub fn hamming(&self, other: &Self) -> u32 {
187        let mut dist = 0u32;
188        for i in 0..160 {
189            dist += (self.bits[i] ^ other.bits[i]).count_ones();
190        }
191        dist
192    }
193
194    /// Cosine similarity (approximated for binary as 1 - Hamming/Dimension/2)
195    /// Similarity = 1.0 - (HammingDistance / 5120.0)
196    pub fn cosine_similarity(&self, other: &Self) -> f32 {
197        let dist = self.hamming(other);
198        1.0 - (dist as f32 / 5120.0)
199    }
200
201    /// Bundle multiple hypervectors using bit-sliced addition.
202    ///
203    /// Algorithmic Optimization: Replaces the O(D * N) bit-by-bit loop with a transposed
204    /// bit-sliced addition approach. By processing all 160 words of each vector contiguously,
205    /// we eliminate 160x redundant memory loads, achieving a massive locality speedup
206    /// with 100% safe Rust.
207    ///
208    /// Majority rule: a bit is set when `count >= N/2 + 1` (equivalent to `count > N/2`).
209    /// N=2 is a fast path (bitwise AND). Accumulation capacity matches HVec via
210    /// [`crate::hyperdim_ops::BUNDLE_MAX_PLANES`] (64 planes).
211    pub fn bundle(vectors: &[&Self]) -> Self {
212        let num_vectors = vectors.len();
213        if num_vectors == 0 {
214            return Self::zero();
215        }
216        if num_vectors == 1 {
217            return *vectors[0];
218        }
219        // N=2 majority is bitwise AND (threshold = 2). Match HVec fast path.
220        if num_vectors == 2 {
221            let mut bits = [0u64; 160];
222            for i in 0..160 {
223                bits[i] = vectors[0].bits[i] & vectors[1].bits[i];
224            }
225            return Self { bits };
226        }
227
228        let threshold = num_vectors / 2 + 1;
229        let num_planes = (usize::BITS - num_vectors.leading_zeros()) as usize;
230
231        #[cfg(all(not(target_arch = "wasm32"), feature = "parallel"))]
232        if num_vectors >= 256 {
233            let mut bits = [0u64; 160];
234            bits.par_iter_mut().enumerate().for_each(|(i, word)| {
235                let mut planes = [0u64; 64];
236                for v in vectors {
237                    let mut carry = v.bits[i];
238                    for p in 0..num_planes {
239                        let next_carry = planes[p] & carry;
240                        planes[p] ^= carry;
241                        carry = next_carry;
242                        if carry == 0 {
243                            break;
244                        }
245                    }
246                }
247                let (mut current_eq, mut current_gt) = (!0u64, 0u64);
248                for p in (0..num_planes).rev() {
249                    if ((threshold >> p) & 1) == 1 {
250                        current_eq &= planes[p];
251                    } else {
252                        current_gt |= current_eq & planes[p];
253                        current_eq &= !planes[p];
254                    }
255                }
256                *word = current_gt | current_eq;
257            });
258            return Self { bits };
259        }
260
261        // Cache-friendly transposed bit-sliced addition
262        let mut planes = vec![[0u64; 160]; num_planes];
263        for v in vectors {
264            for i in 0..160 {
265                let mut carry = v.bits[i];
266                for p in 0..num_planes {
267                    let next_carry = planes[p][i] & carry;
268                    planes[p][i] ^= carry;
269                    carry = next_carry;
270                    if carry == 0 {
271                        break;
272                    }
273                }
274            }
275        }
276
277        let mut bits = [0u64; 160];
278        for i in 0..160 {
279            let (mut current_eq, mut current_gt) = (!0u64, 0u64);
280            for p in (0..num_planes).rev() {
281                if ((threshold >> p) & 1) == 1 {
282                    current_eq &= planes[p][i];
283                } else {
284                    current_gt |= current_eq & planes[p][i];
285                    current_eq &= !planes[p][i];
286                }
287            }
288            bits[i] = current_gt | current_eq;
289        }
290
291        Self { bits }
292    }
293
294    /// Cyclic permutation (shift)
295    pub fn permute(&self, shift: usize) -> Self {
296        let mut result = [0u64; 160];
297        let bit_shift = shift % 64;
298        let word_shift = (shift / 64) % 160;
299
300        for i in 0..160 {
301            let src_idx = (i + 160 - word_shift) % 160;
302            let next_idx = (src_idx + 159) % 160;
303
304            let val = if bit_shift == 0 {
305                self.bits[src_idx]
306            } else {
307                (self.bits[src_idx] << bit_shift) | (self.bits[next_idx] >> (64 - bit_shift))
308            };
309            result[i] = val;
310        }
311
312        Self { bits: result }
313    }
314
315    /// Serialize to bytes
316    pub fn to_bytes(&self) -> Vec<u8> {
317        let mut bytes = Vec::with_capacity(1280);
318        for word in &self.bits {
319            bytes.extend_from_slice(&word.to_le_bytes());
320        }
321        bytes
322    }
323
324    /// Deserialize from bytes
325    pub fn from_bytes(bytes: &[u8]) -> Result<Self> {
326        if bytes.len() != 1280 {
327            return Err(MemoryError::InvalidDimension {
328                expected: 1280,
329                actual: bytes.len(),
330            });
331        }
332        let mut bits = [0u64; 160];
333        for i in 0..160 {
334            let mut word_bytes = [0u8; 8];
335            word_bytes.copy_from_slice(&bytes[i * 8..(i + 1) * 8]);
336            bits[i] = u64::from_le_bytes(word_bytes);
337        }
338        Ok(Self { bits })
339    }
340}
341
342#[cfg(test)]
343mod tests {
344    #![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
345    use super::*;
346
347    #[test]
348    fn test_bhvec_random() {
349        let v1 = BHVec10240::random();
350        let v2 = BHVec10240::random();
351        assert_ne!(v1, v2);
352    }
353
354    #[test]
355    fn test_bhvec_xor_hamming() {
356        let v1 = BHVec10240::random();
357        let v2 = BHVec10240::random();
358        let bound = v1.xor(&v2);
359        let dist = v1.hamming(&v2);
360        assert_eq!(bound.bits.iter().map(|w| w.count_ones()).sum::<u32>(), dist);
361    }
362
363    #[test]
364    fn test_bhvec_permute() {
365        let v1 = BHVec10240::random();
366        let v2 = v1.permute(1);
367        assert_ne!(v1, v2);
368        let v3 = v2.permute(BHVec10240::DIMENSION - 1);
369        assert_eq!(v1, v3);
370    }
371
372    #[test]
373    fn test_bhvec_roundtrip_hvec() {
374        let h1 = HVec10240::random();
375        let bh1 = BHVec10240::from_hvec(&h1);
376        let h2 = bh1.to_hvec();
377        assert_eq!(h1, h2);
378    }
379
380    /// Naive per-bit majority oracle (`count >= N/2 + 1`).
381    fn naive_bundle_majority(vectors: &[&BHVec10240]) -> BHVec10240 {
382        let n = vectors.len();
383        if n == 0 {
384            return BHVec10240::zero();
385        }
386        if n == 1 {
387            return *vectors[0];
388        }
389        let threshold = n / 2 + 1;
390        let mut bits = [0u64; 160];
391        for word_idx in 0..160 {
392            for bit_idx in 0..64 {
393                let mask = 1u64 << bit_idx;
394                let count = vectors
395                    .iter()
396                    .filter(|v| (v.bits[word_idx] & mask) != 0)
397                    .count();
398                if count >= threshold {
399                    bits[word_idx] |= mask;
400                }
401            }
402        }
403        BHVec10240 { bits }
404    }
405
406    #[test]
407    fn test_bhvec_bundle_empty_and_single() {
408        assert_eq!(BHVec10240::bundle(&[]), BHVec10240::zero());
409        let v = BHVec10240::new_seeded(42);
410        assert_eq!(BHVec10240::bundle(&[&v]), v);
411    }
412
413    #[test]
414    fn test_bhvec_bundle_n2_is_and() {
415        let v1 = BHVec10240::new_seeded(1);
416        let v2 = BHVec10240::new_seeded(2);
417        let bundled = BHVec10240::bundle(&[&v1, &v2]);
418        for i in 0..160 {
419            assert_eq!(
420                bundled.bits[i],
421                v1.bits[i] & v2.bits[i],
422                "N=2 must be bitwise AND at word {i}"
423            );
424        }
425    }
426
427    #[test]
428    fn test_bhvec_bundle_threshold_consistency() {
429        // Span early returns, even-N ties, plane widths, and larger N (parity with HVec).
430        for n in [2usize, 3, 4, 10, 255, 256, 1000] {
431            let vectors: Vec<BHVec10240> =
432                (0..n).map(|i| BHVec10240::new_seeded(i as u64)).collect();
433            let refs: Vec<&BHVec10240> = vectors.iter().collect();
434            let actual = BHVec10240::bundle(&refs);
435            let expected = naive_bundle_majority(&refs);
436            assert_eq!(
437                actual.bits, expected.bits,
438                "Bundling inconsistency at N={n} vectors"
439            );
440        }
441    }
442}
csm_core_lib/hyperdim_binary.rs

csm_core_lib/
hyperdim_binary.rs
