Struct Matrix

Source

pub struct Matrix { /* private fields */ }

Expand description

A row-major rows x cols matrix over GF(2^8).

For an encode matrix, rows = k + p (sources + parity, ISA-L’s m) and cols = k; the top k x k block is the identity, so source shards pass through unchanged and the bottom p rows generate parity.

Implementations§

Source §

impl Matrix

Source

pub fn reed_solomon(k: usize, p: usize) -> Result<Self, MatrixError>

Vandermonde-style encode matrix for k sources and p parity rows — ISA-L’s gf_gen_rs_matrix, refusing the configurations ISA-L’s own documentation marks unsafe (where some decode submatrices are singular). Outside the safe region use Matrix::cauchy.

Source

pub fn cauchy(k: usize, p: usize) -> Result<Self, MatrixError>

Cauchy encode matrix for k sources and p parity rows — ISA-L’s gf_gen_cauchy1_matrix. Every square submatrix is invertible, so any (k, p) within the field limit is a valid configuration; this is the recommended general-purpose construction.

Examples found in repository ?

examples/scalar_baseline.rs (line 25)

15fn main() {
16    let args: Vec<usize> = std::env::args()
17        .skip(1)
18        .filter_map(|a| a.parse().ok())
19        .collect();
20    let &[k, p, len, reps] = args.as_slice() else {
21        eprintln!("usage: scalar_baseline <k> <p> <shard_len> <reps>");
22        std::process::exit(2);
23    };
24
25    let coder = match Matrix::cauchy(k, p).and_then(Coder::new) {
26        Ok(c) => c,
27        Err(e) => {
28            eprintln!("bad config: {e}");
29            std::process::exit(2);
30        }
31    };
32
33    // Deterministic data (splitmix64) so every run encodes identical bytes.
34    let mut state: u64 = (k as u64) << 32 | (p as u64) << 16 | len as u64;
35    let mut next = move || {
36        state = state.wrapping_add(0x9E37_79B9_7F4A_7C15);
37        let mut z = state;
38        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
39        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
40        z ^ (z >> 31)
41    };
42    let data: Vec<Vec<u8>> = (0..k)
43        .map(|_| (0..len).map(|_| next() as u8).collect())
44        .collect();
45    let data_refs: Vec<&[u8]> = data.iter().map(|d| d.as_slice()).collect();
46    let mut parity = vec![vec![0u8; len]; p];
47
48    // Warmup (untimed), then the timed reps.
49    for _ in 0..3 {
50        let mut refs: Vec<&mut [u8]> = parity.iter_mut().map(|b| b.as_mut_slice()).collect();
51        coder.encode(&data_refs, &mut refs).expect("encode");
52    }
53    let mut per_rep_ns: Vec<u128> = Vec::with_capacity(reps);
54    let total = Instant::now();
55    for _ in 0..reps {
56        let t = Instant::now();
57        let mut refs: Vec<&mut [u8]> = parity.iter_mut().map(|b| b.as_mut_slice()).collect();
58        coder
59            .encode(&data_refs, black_box(&mut refs))
60            .expect("encode");
61        per_rep_ns.push(t.elapsed().as_nanos());
62        black_box(&parity);
63    }
64    let wall = total.elapsed();
65
66    let checksum = parity.iter().flatten().fold(0u8, |a, &b| a ^ b);
67    per_rep_ns.sort_unstable();
68    let src_bytes = (k * len) as u128 * reps as u128;
69    let mul_count = (k * p * len) as u128 * reps as u128;
70    println!("cell k={k} p={p} len={len} reps={reps}");
71    println!("work: source_bytes={src_bytes} table_muls={mul_count} checksum={checksum:#04x}");
72    println!(
73        "wall: total_ms={} rep_min_us={} rep_median_us={}",
74        wall.as_millis(),
75        per_rep_ns.first().unwrap_or(&0) / 1000,
76        per_rep_ns.get(reps / 2).unwrap_or(&0) / 1000,
77    );
78}

Source

pub fn from_bytes( rows: usize, cols: usize, data: Vec<u8>, ) -> Result<Self, MatrixError>

Build a matrix from raw row-major bytes. data.len() must equal rows * cols, and both dimensions must be in 1..=256 (the GF(2^8) shard-index limit; the field-based constructors are stricter because their constructions need ≤ 255 distinct nonzero elements).

Source

pub fn rows(&self) -> usize

Number of rows (k + p for an encode matrix — ISA-L’s m).

Source

pub fn cols(&self) -> usize

Number of columns (k, the source count, for an encode matrix).

Source

pub fn get(&self, row: usize, col: usize) -> Option<u8>

The coefficient at (row, col), or None out of bounds.

Source

pub fn as_bytes(&self) -> &[u8] ⓘ

The raw row-major coefficient bytes.

Source

pub fn parity_bytes(&self) -> &[u8] ⓘ

The bottom p rows — the parity-generating block, in exactly the layout tables::init_tables expects.

Source

pub fn select_rows(&self, indices: &[usize]) -> Result<Self, MatrixError>

Select indices.len() rows (in order) into a new matrix — the step that builds a decode matrix from the surviving shards’ rows. Indices must be in range; duplicates are allowed here and will simply produce a singular matrix at inversion.

Source

pub fn invert(&self) -> Result<Self, MatrixError>

Invert a square matrix — ISA-L’s gf_invert_matrix (Gauss-Jordan with row-swap pivoting), except non-destructive and with singularity as a typed error. Non-square input is a dimension error.

Source