qec_code/
packed_gf2.rs

1//! Stable, dependency-facing packed GF(2) primitives.
2//!
3//! This module deliberately wraps the crate's internal elimination machinery
4//! instead of exposing its storage layout. Downstream crates can use packed
5//! rows, reusable kernel workspaces, and reduced row-space membership without
6//! depending on private implementation details.
7//!
8//! # Example
9//!
10//! ```
11//! use qec_code::packed_gf2::{KernelWorkspace, PackedRow, ReducedRowSpace};
12//!
13//! let rows = vec![vec![1, 1, 0], vec![0, 1, 1]];
14//! let span = ReducedRowSpace::from_dense_rows(&rows, 3)?;
15//! let target = PackedRow::from_dense(&[1, 0, 1])?;
16//! assert!(span.contains(&target)?);
17//!
18//! let mut workspace = KernelWorkspace::new();
19//! let basis = workspace.kernel_basis(&rows, 3, &[0, 1, 2])?;
20//! assert_eq!(basis, &[vec![1, 1, 1]]);
21//! # Ok::<(), qec_code::QecError>(())
22//! ```
23
24use crate::error::Result;
25use crate::gf2;
26
27/// A binary row represented internally by packed machine words.
28#[derive(Debug, Clone, PartialEq, Eq)]
29pub struct PackedRow {
30    inner: gf2::BitPackedRow,
31}
32
33impl PackedRow {
34    /// Pack one dense binary row.
35    pub fn from_dense(row: &[u8]) -> Result<Self> {
36        Ok(Self {
37            inner: gf2::BitPackedRow::try_from_dense(row, row.len())?,
38        })
39    }
40
41    /// Construct an all-zero row with an explicit width.
42    pub fn zeros(width: usize) -> Self {
43        Self {
44            inner: gf2::BitPackedRow::zeros(width),
45        }
46    }
47
48    /// Return the logical width, excluding storage padding.
49    pub fn width(&self) -> usize {
50        self.inner.width()
51    }
52
53    /// Read one logical bit, rejecting an out-of-range index.
54    pub fn bit(&self, index: usize) -> Result<u8> {
55        self.inner.try_bit(index)
56    }
57
58    /// Convert the packed row back to a dense binary vector.
59    pub fn to_dense(&self) -> Vec<u8> {
60        self.inner.to_dense()
61    }
62
63    /// XOR another row into this row.
64    pub fn xor_assign(&mut self, rhs: &Self) -> Result<()> {
65        self.inner.xor_assign(&rhs.inner)
66    }
67
68    /// Return the GF(2) dot product.
69    pub fn dot_parity(&self, rhs: &Self) -> Result<u8> {
70        self.inner.dot_parity(&rhs.inner)
71    }
72
73    /// Return the Hamming weight.
74    pub fn weight(&self) -> usize {
75        self.inner.weight()
76    }
77
78    /// Return whether every logical bit is zero.
79    pub fn is_zero(&self) -> bool {
80        self.inner.is_zero()
81    }
82}
83
84/// A row space reduced once for repeated packed membership queries.
85#[derive(Debug, Clone)]
86pub struct ReducedRowSpace {
87    inner: gf2::PackedReducedRows,
88    rank: usize,
89}
90
91impl ReducedRowSpace {
92    /// Reduce dense binary rows with an explicit width.
93    ///
94    /// An explicit width preserves the meaning of an empty matrix.
95    pub fn from_dense_rows(rows: &[Vec<u8>], width: usize) -> Result<Self> {
96        let reduced = gf2::try_rref_with_width(rows, width)?;
97        let rank = reduced.pivot_cols.len();
98        Ok(Self {
99            inner: gf2::PackedReducedRows::try_from_reduced_rows(&reduced)?,
100            rank,
101        })
102    }
103
104    /// Return the ambient vector width.
105    pub fn width(&self) -> usize {
106        self.inner.width()
107    }
108
109    /// Return the dimension of the row space.
110    pub fn rank(&self) -> usize {
111        self.rank
112    }
113
114    /// Test whether a packed row belongs to this row space.
115    pub fn contains(&self, target: &PackedRow) -> Result<bool> {
116        gf2::try_in_packed_reduced_row_span(&self.inner, &target.inner)
117    }
118
119    /// Pack a dense target and test row-space membership.
120    pub fn contains_dense(&self, target: &[u8]) -> Result<bool> {
121        self.contains(&PackedRow::from_dense(target)?)
122    }
123}
124
125/// Reusable allocation workspace for permuted GF(2) kernel bases.
126#[derive(Debug, Default)]
127pub struct KernelWorkspace {
128    inner: gf2::RandomWindowKernelWorkspace,
129}
130
131impl KernelWorkspace {
132    /// Construct an empty workspace.
133    pub fn new() -> Self {
134        Self::default()
135    }
136
137    /// Compute a kernel basis after applying a column permutation.
138    ///
139    /// `column_permutation[permuted_column]` names the corresponding input
140    /// column. The returned rows use the original column order and borrow the
141    /// workspace until the next mutable call.
142    pub fn kernel_basis(
143        &mut self,
144        matrix: &[Vec<u8>],
145        width: usize,
146        column_permutation: &[usize],
147    ) -> Result<&[Vec<u8>]> {
148        self.inner
149            .try_kernel_basis_with_width(matrix, width, column_permutation)
150    }
151}
qec_code/packed_gf2.rs

qec_code/
packed_gf2.rs
