commonware_cryptography/reed_solomon/

mod.rs

//! Encode and reconstruct shards using Reed-Solomon erasure coding over GF(2^16).
//!
//! [`Encoder`] and [`Decoder`] select a rate and CPU engine automatically. Every shard
//! must have the same nonzero, even byte length. [`Encoder::supports`] checks whether
//! a pair of original and recovery shard counts is supported.
//!
//! Decoding requires at least as many distinct shards as there were original shards.
//! All supplied shards must belong to the same codeword: this module reconstructs
//! missing shards and does not authenticate their contents.
//!
//! [`Plan`] prepares erasure coefficients once for decoders that share shard
//! counts and received indices, even when their shard byte lengths differ.
//!
//! # Basic Usage
//!
//! ```
//! use commonware_cryptography::reed_solomon::{Decoder, Encoder};
//!
//! let originals = [[1, 2, 3, 4, 5, 6], [7, 8, 9, 10, 11, 12]];
//! let mut encoder = Encoder::new(2, 1, 6)?;
//! for shard in &originals {
//!     encoder.add_original_shard(shard)?;
//! }
//! let encoded = encoder.encode()?;
//!
//! let mut decoder = Decoder::new(2, 1, 6)?;
//! decoder.add_original_shard(0, originals[0])?;
//! decoder.add_recovery_shard(0, encoded.recovery(0).unwrap())?;
//! let decoded = decoder.decode()?.unwrap();
//! assert_eq!(decoded.original(1), Some(originals[1].as_slice()));
//! # Ok::<(), commonware_cryptography::reed_solomon::Error>(())
//! ```
//!
//! Result objects borrow the working buffers. Dropping a result resets its encoder
//! or decoder for another round with the same configuration.
//!
//! # Working Space
//!
//! A coder sizes its working space when it is created or reset: up to
//! `2 * (original_count + recovery_count).next_power_of_two()` shards of `shard_bytes` bytes,
//! each rounded up to whole [`SHARD_CHUNK_BYTES`] blocks. The space is one allocation that a
//! reset can grow but never shrinks. Creating or resetting a coder returns an error for
//! unsupported shard counts, a zero or odd `shard_bytes`, or a working space larger than
//! `isize::MAX` bytes, the largest allocation a `Vec` can hold.
//!
//! Callers that take shard counts or widths from an untrusted source must bound them against
//! their own memory budget before creating or resetting a coder. Wide shards can be coded as
//! independent byte ranges so that the range width, not the shard width, sets the working space.
//! The ranges produce the same bytes as coding each shard whole when every range except the last
//! is a whole number of [`SHARD_CHUNK_BYTES`] blocks, as [algorithm > Shard] explains.
//!
//! # Changes vs. Upstream
//!
//! This module vendors [`reed_solomon_simd`].
//!
//! - Moved the crate into `commonware_cryptography::reed_solomon` and rewrote internal
//!   `crate::` paths accordingly.
//! - Retained the upstream `LICENSE` file, including the BSD-3-Clause notice for Leopard-RS.
//! - Removed the build script and README rustdoc generation.
//! - Removed upstream examples. Kept upstream-style benchmarks under Commonware's benchmark layout
//!   and naming rules.
//! - Uses workspace dependencies and [`commonware_formatting`] in the test harness.
//! - Uses [`thiserror`] for error display formatting.
//! - Renamed upstream `ReedSolomonEncoder` and `ReedSolomonDecoder` to [`Encoder`] and [`Decoder`],
//!   and the `NoSimd` engine to [`Scalar`](engine::Scalar).
//! - Uses plain code references for cfg-gated SIMD engine docs so rustdoc works on all targets.
//! - Validates transform domains, shard ranges, and working-space sizes at their public boundaries.
//! - Supports AVX-512 with GFNI multiplication and runtime CPU feature checks.
//! - Removed the SSSE3 engine.
//! - Adds [`Plan`] and plan-based decoding to reuse erasure coefficients across decoders.
//! - Sizes decoder Walsh transforms to the decoding domain.
//! - Fuses AVX-512 butterfly layers.
//! - Fuses formal-derivative leaves in blocks of four shards for every engine. When the `Avx512`
//!   engine's CPU features are present, blocks of 16 shards use an AVX-512 leaf for suitable shard
//!   counts and sizes, regardless of the selected engine.
//! - Builds the 128-bit multiplication tables in native byte order, since the Neon and Avx2
//!   engines read each table as a vector of its in-memory bytes.
//! - Includes independent field-arithmetic checks, lifecycle regressions, and differential fuzzing.
//! - Rewrote comments in Commonware style: removed section banners and uppercase step headers,
//!   and attached floating comments to the code they describe.
//!
//! [`reed_solomon_simd`]: https://crates.io/crates/reed-solomon-simd
//! [`thiserror`]: https://docs.rs/thiserror
//! [algorithm > Shard]: crate::reed_solomon::algorithm#shard

#![allow(
    clippy::multiple_inherent_impl,
    reason = "Keep the vendored implementation aligned with its upstream layout."
)]

pub use self::{
    decoder_result::{DecoderResult, Originals, Recoveries, RecoveryDecoderResult},
    encoder_result::{EncoderResult, Recovery},
    engine::SHARD_CHUNK_BYTES,
    plan::Plan,
    wrappers::{Decoder, Encoder},
};
use thiserror::Error;

#[cfg(test)]
#[macro_use]
mod test_util;

#[cfg(any(test, feature = "fuzz"))]
pub mod fuzz;

mod decoder_result;
mod encoder_result;
mod plan;
mod wrappers;

pub mod algorithm {
    #![doc = include_str!("algorithm.md")]
}
pub mod engine;
pub mod rate;

/// Represents all possible errors that can occur in this library.
#[derive(Clone, Copy, Debug, Error, PartialEq)]
pub enum Error {
    /// Given shard has different size than the configured shard size.
    #[error("different shard size: expected {shard_bytes} bytes, got {got} bytes")]
    DifferentShardSize {
        /// Configured shard size.
        shard_bytes: usize,
        /// Size of the given shard.
        got: usize,
    },

    /// Decoder or [`Plan`] was given the same original shard index twice.
    #[error("duplicate original shard index: {index}")]
    DuplicateOriginalShardIndex {
        /// Given duplicate index.
        index: usize,
    },

    /// Decoder or [`Plan`] was given the same recovery shard index twice.
    #[error("duplicate recovery shard index: {index}")]
    DuplicateRecoveryShardIndex {
        /// Given duplicate index.
        index: usize,
    },

    /// Decoder or [`Plan`] was given an invalid original shard index,
    /// i.e. `index >= original_count`.
    #[error("invalid original shard index: {index} >= original_count {original_count}")]
    InvalidOriginalShardIndex {
        /// Configured number of original shards.
        original_count: usize,
        /// Given invalid index.
        index: usize,
    },

    /// Decoder or [`Plan`] was given an invalid recovery shard index,
    /// i.e. `index >= recovery_count`.
    #[error("invalid recovery shard index: {index} >= recovery_count {recovery_count}")]
    InvalidRecoveryShardIndex {
        /// Configured number of recovery shards.
        recovery_count: usize,
        /// Given invalid index.
        index: usize,
    },

    /// Configured shard size is zero, odd, or requires more working space than a single
    /// allocation can hold.
    #[error("invalid shard size: {shard_bytes} bytes (zero, odd, or working space too large)")]
    InvalidShardSize {
        /// Configured shard size.
        shard_bytes: usize,
    },

    /// Decoder or [`Plan`] was given too few shards.
    ///
    /// Decoding requires as many shards as there were original shards
    /// in total, in any combination of original shards and recovery shards.
    #[error(
        "not enough shards: {original_received_count} original + {recovery_received_count} recovery < {original_count} original_count"
    )]
    NotEnoughShards {
        /// Configured number of original shards.
        original_count: usize,
        /// Number of original shards given.
        original_received_count: usize,
        /// Number of recovery shards given.
        recovery_received_count: usize,
    },

    /// Decoder was given a [`Plan`] built for different shard counts or received
    /// shard indices.
    #[error("plan does not match decoder")]
    PlanMismatch,

    /// Encoder was given less than `original_count` original shards.
    #[error(
        "too few original shards: got {original_received_count} shards while original_count is {original_count}"
    )]
    TooFewOriginalShards {
        /// Configured number of original shards.
        original_count: usize,
        /// Number of original shards given to encoder.
        original_received_count: usize,
    },

    /// Encoder was given more than `original_count` original shards.
    #[error("too many original shards: got more than original_count ({original_count}) shards")]
    TooManyOriginalShards {
        /// Configured number of original shards.
        original_count: usize,
    },

    /// Given `original_count` / `recovery_count` combination is not supported.
    #[error(
        "unsupported shard count: {original_count} original shards with {recovery_count} recovery shards"
    )]
    UnsupportedShardCount {
        /// Given number of original shards.
        original_count: usize,
        /// Given number of recovery shards.
        recovery_count: usize,
    },
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::reed_solomon::{engine::DefaultEngine, rate::DefaultRate};

    #[test]
    fn roundtrip() {
        let original = test_util::generate_original(2, 1024, 123);

        let mut encoder = Encoder::new(2, 3, 1024).unwrap();
        for shard in &original {
            encoder.add_original_shard(shard).unwrap();
        }
        let encoding = encoder.encode().unwrap();
        let recovery: Vec<_> = encoding.recovery_iter().map(<[u8]>::to_vec).collect();

        test_util::assert_hash(&recovery, test_util::LOW_2_3);

        let mut decoder = Decoder::new(2, 3, 1024).unwrap();
        decoder.add_recovery_shard(0, &recovery[0]).unwrap();
        decoder.add_recovery_shard(1, &recovery[1]).unwrap();
        let decoding = decoder.decode().unwrap().unwrap();
        let mut restored = decoding.original_iter();

        assert_eq!(restored.next(), Some((0, original[0].as_slice())));
        assert_eq!(restored.next(), Some((1, original[1].as_slice())));
        assert_eq!(restored.next(), None);
    }

    #[test]
    fn test_send() {
        fn assert_send<T: Send>() {}
        assert_send::<Encoder>();
        assert_send::<Decoder>();
        assert_send::<Plan>();
        assert_send::<DefaultEngine>();
        assert_send::<DefaultRate<DefaultEngine>>();
        assert_send::<DecoderResult<'_>>();
        assert_send::<RecoveryDecoderResult<'_>>();
        assert_send::<EncoderResult<'_>>();
        assert_send::<Error>();
    }

    #[test]
    fn test_sync() {
        fn assert_sync<T: Sync>() {}
        assert_sync::<Encoder>();
        assert_sync::<Decoder>();
        assert_sync::<Plan>();
        assert_sync::<DefaultEngine>();
        assert_sync::<DefaultRate<DefaultEngine>>();
        assert_sync::<DecoderResult<'_>>();
        assert_sync::<RecoveryDecoderResult<'_>>();
        assert_sync::<EncoderResult<'_>>();
        assert_sync::<Error>();
    }
}