amari_core/gf2/
vector.rs

1//! Bit-packed vectors over GF(2).
2
3use super::scalar::GF2;
4use alloc::vec;
5use alloc::vec::Vec;
6use core::fmt;
7use core::ops::{Add, BitAnd, BitXor};
8
9const WORD_BITS: usize = 64;
10
11#[inline]
12const fn word_index(i: usize) -> usize {
13    i / WORD_BITS
14}
15
16#[inline]
17const fn bit_index(i: usize) -> usize {
18    i % WORD_BITS
19}
20
21#[inline]
22fn num_words(dim: usize) -> usize {
23    dim.div_ceil(WORD_BITS)
24}
25
26/// Mask for the valid bits in the last word (zeros out trailing bits beyond dim).
27#[inline]
28fn trailing_mask(dim: usize) -> u64 {
29    let rem = dim % WORD_BITS;
30    if rem == 0 && dim > 0 {
31        u64::MAX
32    } else if dim == 0 {
33        0
34    } else {
35        (1u64 << rem) - 1
36    }
37}
38
39/// A vector in F₂ⁿ, stored as packed bits in u64 words.
40///
41/// Operations are word-parallel: XOR for addition, AND + popcount for dot product.
42/// Vectors of dimension ≤ 64 fit in a single word with no heap allocation overhead.
43#[derive(Debug, Clone, PartialEq, Eq, Hash)]
44pub struct GF2Vector {
45    words: Vec<u64>,
46    dim: usize,
47}
48
49impl GF2Vector {
50    /// Create the zero vector of given dimension.
51    #[must_use]
52    pub fn zero(dim: usize) -> Self {
53        Self {
54            words: vec![0u64; num_words(dim)],
55            dim,
56        }
57    }
58
59    /// Create from a slice of 0/1 u8 values.
60    #[must_use]
61    pub fn from_bits(bits: &[u8]) -> Self {
62        let dim = bits.len();
63        let mut v = Self::zero(dim);
64        for (i, &b) in bits.iter().enumerate() {
65            if b & 1 != 0 {
66                v.words[word_index(i)] |= 1u64 << bit_index(i);
67            }
68        }
69        v
70    }
71
72    /// Create from a u64 value for dimensions ≤ 64.
73    #[must_use]
74    pub fn from_u64(dim: usize, value: u64) -> Self {
75        assert!(dim <= WORD_BITS, "from_u64 requires dim <= 64");
76        let masked = value & trailing_mask(dim);
77        Self {
78            words: vec![masked],
79            dim,
80        }
81    }
82
83    /// Number of components.
84    #[inline]
85    #[must_use]
86    pub fn dim(&self) -> usize {
87        self.dim
88    }
89
90    /// Get component i.
91    #[inline]
92    #[must_use]
93    pub fn get(&self, i: usize) -> GF2 {
94        assert!(
95            i < self.dim,
96            "index {} out of bounds for dim {}",
97            i,
98            self.dim
99        );
100        GF2::new(((self.words[word_index(i)] >> bit_index(i)) & 1) as u8)
101    }
102
103    /// Set component i.
104    #[inline]
105    pub fn set(&mut self, i: usize, value: GF2) {
106        assert!(
107            i < self.dim,
108            "index {} out of bounds for dim {}",
109            i,
110            self.dim
111        );
112        let w = word_index(i);
113        let b = bit_index(i);
114        self.words[w] = (self.words[w] & !(1u64 << b)) | ((value.value() as u64) << b);
115    }
116
117    /// Hamming weight (number of 1-bits).
118    #[must_use]
119    pub fn weight(&self) -> usize {
120        self.words.iter().map(|w| w.count_ones() as usize).sum()
121    }
122
123    /// Hamming distance to another vector.
124    #[must_use]
125    pub fn hamming_distance(&self, other: &Self) -> usize {
126        assert_eq!(self.dim, other.dim, "dimension mismatch");
127        self.words
128            .iter()
129            .zip(other.words.iter())
130            .map(|(a, b)| (a ^ b).count_ones() as usize)
131            .sum()
132    }
133
134    /// Dot product in F₂ (popcount of AND, mod 2).
135    #[must_use]
136    pub fn dot(&self, other: &Self) -> GF2 {
137        assert_eq!(self.dim, other.dim, "dimension mismatch");
138        let parity: u32 = self
139            .words
140            .iter()
141            .zip(other.words.iter())
142            .map(|(a, b)| (a & b).count_ones())
143            .sum();
144        GF2::new((parity & 1) as u8)
145    }
146
147    /// Component-wise XOR (addition in F₂ⁿ).
148    #[must_use]
149    pub fn add(&self, other: &Self) -> Self {
150        assert_eq!(self.dim, other.dim, "dimension mismatch");
151        let words: Vec<u64> = self
152            .words
153            .iter()
154            .zip(other.words.iter())
155            .map(|(a, b)| a ^ b)
156            .collect();
157        Self {
158            words,
159            dim: self.dim,
160        }
161    }
162
163    /// Component-wise AND.
164    #[must_use]
165    pub fn bitwise_and(&self, other: &Self) -> Self {
166        assert_eq!(self.dim, other.dim, "dimension mismatch");
167        let words: Vec<u64> = self
168            .words
169            .iter()
170            .zip(other.words.iter())
171            .map(|(a, b)| a & b)
172            .collect();
173        Self {
174            words,
175            dim: self.dim,
176        }
177    }
178
179    /// Whether this is the zero vector.
180    #[must_use]
181    pub fn is_zero(&self) -> bool {
182        self.words.iter().all(|&w| w == 0)
183    }
184
185    /// Raw access to packed words.
186    #[must_use]
187    pub fn as_words(&self) -> &[u64] {
188        &self.words
189    }
190}
191
192// --- Operator impls ---
193
194impl Add for &GF2Vector {
195    type Output = GF2Vector;
196    fn add(self, rhs: Self) -> GF2Vector {
197        self.add(rhs)
198    }
199}
200
201impl BitXor for &GF2Vector {
202    type Output = GF2Vector;
203    fn bitxor(self, rhs: Self) -> GF2Vector {
204        self.add(rhs)
205    }
206}
207
208impl BitAnd for &GF2Vector {
209    type Output = GF2Vector;
210    fn bitand(self, rhs: Self) -> GF2Vector {
211        self.bitwise_and(rhs)
212    }
213}
214
215impl fmt::Display for GF2Vector {
216    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
217        write!(f, "[")?;
218        for i in 0..self.dim {
219            if i > 0 {
220                write!(f, ", ")?;
221            }
222            write!(f, "{}", self.get(i))?;
223        }
224        write!(f, "]")
225    }
226}
227
228#[cfg(test)]
229mod tests {
230    use super::*;
231
232    #[test]
233    fn test_zero_vector() {
234        let v = GF2Vector::zero(8);
235        assert_eq!(v.dim(), 8);
236        assert!(v.is_zero());
237        assert_eq!(v.weight(), 0);
238    }
239
240    #[test]
241    fn test_get_set_roundtrip() {
242        let mut v = GF2Vector::zero(10);
243        v.set(0, GF2::ONE);
244        v.set(5, GF2::ONE);
245        v.set(9, GF2::ONE);
246        assert_eq!(v.get(0), GF2::ONE);
247        assert_eq!(v.get(1), GF2::ZERO);
248        assert_eq!(v.get(5), GF2::ONE);
249        assert_eq!(v.get(9), GF2::ONE);
250        assert_eq!(v.weight(), 3);
251    }
252
253    #[test]
254    fn test_from_bits() {
255        let v = GF2Vector::from_bits(&[1, 0, 1, 1, 0]);
256        assert_eq!(v.dim(), 5);
257        assert_eq!(v.get(0), GF2::ONE);
258        assert_eq!(v.get(1), GF2::ZERO);
259        assert_eq!(v.get(2), GF2::ONE);
260        assert_eq!(v.get(3), GF2::ONE);
261        assert_eq!(v.get(4), GF2::ZERO);
262    }
263
264    #[test]
265    fn test_xor_addition() {
266        let a = GF2Vector::from_bits(&[1, 0, 1, 0]);
267        let b = GF2Vector::from_bits(&[1, 1, 0, 0]);
268        let c = a.add(&b);
269        assert_eq!(c, GF2Vector::from_bits(&[0, 1, 1, 0]));
270    }
271
272    #[test]
273    fn test_dot_product() {
274        let a = GF2Vector::from_bits(&[1, 1, 0, 1]);
275        let b = GF2Vector::from_bits(&[1, 0, 1, 1]);
276        // AND = [1,0,0,1], popcount = 2, mod 2 = 0
277        assert_eq!(a.dot(&b), GF2::ZERO);
278
279        let c = GF2Vector::from_bits(&[1, 1, 1]);
280        let d = GF2Vector::from_bits(&[1, 0, 1]);
281        // AND = [1,0,1], popcount = 2, mod 2 = 0
282        assert_eq!(c.dot(&d), GF2::ZERO);
283
284        let e = GF2Vector::from_bits(&[1, 1, 0]);
285        let f = GF2Vector::from_bits(&[1, 0, 0]);
286        // AND = [1,0,0], popcount = 1, mod 2 = 1
287        assert_eq!(e.dot(&f), GF2::ONE);
288    }
289
290    #[test]
291    fn test_hamming_weight_and_distance() {
292        let a = GF2Vector::from_bits(&[1, 0, 1, 1, 0, 1]);
293        assert_eq!(a.weight(), 4);
294
295        let b = GF2Vector::from_bits(&[0, 1, 1, 0, 0, 1]);
296        assert_eq!(a.hamming_distance(&b), 3);
297    }
298
299    #[test]
300    fn test_from_u64_roundtrip() {
301        let v = GF2Vector::from_u64(8, 0b10110011);
302        assert_eq!(v.get(0), GF2::ONE);
303        assert_eq!(v.get(1), GF2::ONE);
304        assert_eq!(v.get(2), GF2::ZERO);
305        assert_eq!(v.get(3), GF2::ZERO);
306        assert_eq!(v.get(4), GF2::ONE);
307        assert_eq!(v.get(5), GF2::ONE);
308        assert_eq!(v.get(6), GF2::ZERO);
309        assert_eq!(v.get(7), GF2::ONE);
310    }
311
312    #[test]
313    fn test_large_vector() {
314        let mut v = GF2Vector::zero(128);
315        v.set(0, GF2::ONE);
316        v.set(63, GF2::ONE);
317        v.set(64, GF2::ONE);
318        v.set(127, GF2::ONE);
319        assert_eq!(v.weight(), 4);
320        assert_eq!(v.get(63), GF2::ONE);
321        assert_eq!(v.get(64), GF2::ONE);
322        assert_eq!(v.get(65), GF2::ZERO);
323    }
324}
amari_core/gf2/vector.rs

amari_core/gf2/
vector.rs
