use crate::gf16::Gf16;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Gf16Matrix {
n: usize,
data: Vec<u16>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SingularMatrix;
impl std::fmt::Display for SingularMatrix {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(
f,
"GF(2^16) matrix is singular: no non-zero pivot found; \
this indicates a bad block selection, not damaged input data"
)
}
}
impl std::error::Error for SingularMatrix {}
impl Gf16Matrix {
pub fn zero(n: usize) -> Self {
Self {
n,
data: vec![0u16; n * n],
}
}
pub fn identity(n: usize) -> Self {
let mut m = Self::zero(n);
for i in 0..n {
m.set(i, i, 1);
}
m
}
pub fn build_reduced(gf: &Gf16, bases: &[u16], exponents: &[u32]) -> Self {
assert_eq!(
bases.len(),
exponents.len(),
"the reduced matrix must be square: got {} bases and {} exponents",
bases.len(),
exponents.len()
);
let n = bases.len();
let mut m = Self::zero(n);
for (r, &e) in exponents.iter().enumerate() {
for (c, &b) in bases.iter().enumerate() {
m.set(r, c, gf.pow(b, e));
}
}
m
}
pub fn n(&self) -> usize {
self.n
}
pub fn get(&self, r: usize, c: usize) -> u16 {
self.data[r * self.n + c]
}
pub fn set(&mut self, r: usize, c: usize, v: u16) {
self.data[r * self.n + c] = v;
}
pub fn row(&self, r: usize) -> &[u16] {
&self.data[r * self.n..(r + 1) * self.n]
}
fn swap_rows(&mut self, a: usize, b: usize) {
if a == b {
return;
}
let n = self.n;
let (lo, hi) = if a < b { (a, b) } else { (b, a) };
let (head, tail) = self.data.split_at_mut(hi * n);
head[lo * n..lo * n + n].swap_with_slice(&mut tail[..n]);
}
pub fn invert(&self, gf: &Gf16) -> Result<Self, SingularMatrix> {
let n = self.n;
let mut a = self.clone();
let mut inv = Self::identity(n);
for col in 0..n {
let pivot_row = (col..n)
.find(|&r| a.get(r, col) != 0)
.ok_or(SingularMatrix)?;
a.swap_rows(col, pivot_row);
inv.swap_rows(col, pivot_row);
let pivot_inv = gf.inverse(a.get(col, col));
if pivot_inv != 1 {
for c in 0..n {
let v = a.get(col, c);
if v != 0 {
a.set(col, c, gf.mul(v, pivot_inv));
}
let v = inv.get(col, c);
if v != 0 {
inv.set(col, c, gf.mul(v, pivot_inv));
}
}
}
for r in 0..n {
if r == col {
continue;
}
let factor = a.get(r, col);
if factor == 0 {
continue;
}
for c in 0..n {
let a_val = a.get(col, c);
if a_val != 0 {
let new = a.get(r, c) ^ gf.mul(factor, a_val);
a.set(r, c, new);
}
let inv_val = inv.get(col, c);
if inv_val != 0 {
let new = inv.get(r, c) ^ gf.mul(factor, inv_val);
inv.set(r, c, new);
}
}
}
}
Ok(inv)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn mat_mul(gf: &Gf16, a: &Gf16Matrix, b: &Gf16Matrix) -> Gf16Matrix {
assert_eq!(a.n(), b.n());
let n = a.n();
let mut out = Gf16Matrix::zero(n);
for r in 0..n {
for c in 0..n {
let mut acc = 0u16;
for k in 0..n {
acc ^= gf.mul(a.get(r, k), b.get(k, c));
}
out.set(r, c, acc);
}
}
out
}
#[test]
fn identity_inverts_to_itself() {
let gf = Gf16::new();
let id = Gf16Matrix::identity(5);
let inv = id.invert(&gf).unwrap();
assert_eq!(inv, id);
}
#[test]
fn reduced_matrix_inverts_and_satisfies_a_times_a_inv_is_identity() {
let gf = Gf16::new();
for &m in &[1usize, 2, 5, 16, 37] {
let bases = gf.input_bases(m);
let exponents: Vec<u32> = (0..m as u32).map(|i| i * 3 + 1).collect();
let a = Gf16Matrix::build_reduced(&gf, &bases, &exponents);
let inv = a.invert(&gf).expect("RS submatrix must be invertible");
let product = mat_mul(&gf, &a, &inv);
assert_eq!(product, Gf16Matrix::identity(m), "m={m}");
}
}
#[test]
fn reduced_matrix_is_invertible_for_this_non_consecutive_choice() {
let gf = Gf16::new();
let bases = gf.input_bases(20);
let exponents: Vec<u32> = vec![
0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361,
];
let a = Gf16Matrix::build_reduced(&gf, &bases, &exponents);
let inv = a.invert(&gf).expect("RS submatrix must be invertible");
let product = mat_mul(&gf, &a, &inv);
assert_eq!(product, Gf16Matrix::identity(20));
}
#[test]
fn some_non_consecutive_exponent_choices_are_singular() {
let gf = Gf16::new();
let bases = gf.input_bases(24);
let exponents: Vec<u32> = vec![
5616, 6439, 6769, 8303, 10100, 15905, 18261, 21236, 37296, 38005, 38623, 42429, 43782,
43796, 44165, 45329, 52435, 52522, 54087, 55200, 55652, 60808, 64172, 65456,
];
let a = Gf16Matrix::build_reduced(&gf, &bases, &exponents);
assert_eq!(a.invert(&gf), Err(SingularMatrix));
}
#[test]
fn a_genuinely_singular_matrix_returns_an_error_not_a_panic() {
let gf = Gf16::new();
let mut m = Gf16Matrix::zero(3);
m.set(0, 0, 1);
m.set(0, 1, 2);
m.set(0, 2, 3);
m.set(1, 0, 1);
m.set(1, 1, 2);
m.set(1, 2, 3);
m.set(2, 0, 5);
m.set(2, 1, 6);
m.set(2, 2, 7);
assert_eq!(m.invert(&gf), Err(SingularMatrix));
}
#[test]
fn an_all_zero_matrix_is_singular() {
let gf = Gf16::new();
let m = Gf16Matrix::zero(4);
assert_eq!(m.invert(&gf), Err(SingularMatrix));
}
#[test]
#[should_panic(expected = "must be square")]
fn build_reduced_panics_on_mismatched_lengths() {
let gf = Gf16::new();
let bases = gf.input_bases(3);
let exponents = vec![0u32, 1];
Gf16Matrix::build_reduced(&gf, &bases, &exponents);
}
mod props {
use super::*;
use proptest::prelude::*;
fn missing_bases_and_first_exponent() -> impl Strategy<Value = (Vec<u16>, u32)> {
(1usize..300).prop_flat_map(|inputs| {
let all = Gf16::new().input_bases(inputs);
(1..=inputs.min(40)).prop_flat_map(move |m| {
(
prop::sample::subsequence(all.clone(), m),
0..crate::gf16::ORDER - 40,
)
})
})
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(200))]
#[test]
fn reduced_matrix_inverts_for_consecutive_exponents(
(bases, first) in missing_bases_and_first_exponent()
) {
let gf = Gf16::new();
let m = bases.len();
let exponents: Vec<u32> = (first..first + m as u32).collect();
let a = Gf16Matrix::build_reduced(&gf, &bases, &exponents);
let inv = a.invert(&gf);
prop_assert!(inv.is_ok(), "singular for bases={bases:?}, first={first}");
let product = mat_mul(&gf, &a, &inv.unwrap());
prop_assert_eq!(product, Gf16Matrix::identity(m));
}
}
}
}