Skip to main content

cu_fec/
rlc.rs

1//! Bounded sliding-window RLC encoder and decoder.
2
3use core::fmt;
4
5use crate::{Field, RepairPayloadId, tinymt::TinyMt32};
6
7const RFC_MAX_WINDOW_SYMBOLS: usize = 0x0fff;
8
9/// A codec configuration error or an error encountered while processing a symbol.
10#[derive(Clone, Copy, Debug, Eq, PartialEq)]
11pub enum Error {
12    /// The symbol size is zero.
13    EmptySymbol,
14    /// The configured active symbol size exceeds the type's hard capacity.
15    SymbolCapacityExceeded,
16    /// A source or repair symbol does not have the configured size.
17    SymbolSizeMismatch,
18    /// The coding window size is zero.
19    EmptyWindow,
20    /// The coding window exceeds either the RFC limit or the type's hard capacity.
21    WindowCapacityExceeded,
22    /// The active decoder equation capacity is zero or exceeds its hard capacity.
23    EquationCapacityExceeded,
24    /// The supplied density threshold is greater than 15.
25    InvalidDensityThreshold,
26    /// GF(2) at full density requires a zero repair key on the sending side.
27    RepairKeyMustBeZero,
28    /// No source symbol is currently available for repair generation.
29    EmptyEncodingWindow,
30    /// A received repair window is larger than the configured decoding window.
31    RepairWindowTooLarge,
32    /// A symbol or repair window is older than the retained decoding window.
33    WindowExpired,
34    /// Sequence ordering is ambiguous at exactly half the `u32` sequence space.
35    AmbiguousSequence,
36    /// The bounded equation store has no room for another innovative equation.
37    EquationStoreFull,
38    /// Received data contradicts data already known to the decoder.
39    ConflictingSource,
40    /// A reduced equation has no variables but has a nonzero right-hand side.
41    InconsistentEquation,
42}
43
44impl fmt::Display for Error {
45    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
46        formatter.write_str(match self {
47            Self::EmptySymbol => "symbol size must be nonzero",
48            Self::SymbolCapacityExceeded => "symbol size exceeds the hard capacity",
49            Self::SymbolSizeMismatch => "symbol length does not match the configured size",
50            Self::EmptyWindow => "coding window size must be nonzero",
51            Self::WindowCapacityExceeded => "coding window exceeds a capacity",
52            Self::EquationCapacityExceeded => "invalid decoder equation capacity",
53            Self::InvalidDensityThreshold => "density threshold must be in 0..=15",
54            Self::RepairKeyMustBeZero => "full-density GF(2) repairs require repair key zero",
55            Self::EmptyEncodingWindow => "cannot encode a repair without source symbols",
56            Self::RepairWindowTooLarge => "repair window exceeds the decoder window",
57            Self::WindowExpired => "symbol range has expired from the decoder window",
58            Self::AmbiguousSequence => "sequence ordering is ambiguous",
59            Self::EquationStoreFull => "decoder equation store is full",
60            Self::ConflictingSource => "source symbol conflicts with known data",
61            Self::InconsistentEquation => "repair equation contradicts known data",
62        })
63    }
64}
65
66impl core::error::Error for Error {}
67
68/// The active parameters for an RLC encoder or decoder.
69#[derive(Clone, Copy, Debug, Eq, PartialEq)]
70pub struct RlcConfig {
71    symbol_size: usize,
72    window_symbols: usize,
73    field: Field,
74}
75
76/// A wrapping RFC 8681 Encoding Symbol ID (ESI).
77///
78/// This transparent newtype prevents symbol identifiers from being confused
79/// with packet sequence numbers or ordinary counters.
80#[repr(transparent)]
81#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
82pub struct EncodingSymbolId(u32);
83
84impl EncodingSymbolId {
85    /// Creates an ESI from its RFC wire value.
86    pub const fn new(value: u32) -> Self {
87        Self(value)
88    }
89
90    /// Returns the RFC wire value.
91    pub const fn get(self) -> u32 {
92        self.0
93    }
94
95    /// Advances this ESI with RFC sequence-space wrapping.
96    pub const fn wrapping_add(self, count: u32) -> Self {
97        Self(self.0.wrapping_add(count))
98    }
99
100    /// Moves this ESI backward with RFC sequence-space wrapping.
101    pub const fn wrapping_sub(self, count: u32) -> Self {
102        Self(self.0.wrapping_sub(count))
103    }
104}
105
106impl From<u32> for EncodingSymbolId {
107    fn from(value: u32) -> Self {
108        Self::new(value)
109    }
110}
111
112impl From<EncodingSymbolId> for u32 {
113    fn from(value: EncodingSymbolId) -> Self {
114        value.get()
115    }
116}
117
118impl fmt::Display for EncodingSymbolId {
119    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
120        self.0.fmt(formatter)
121    }
122}
123
124impl RlcConfig {
125    /// Creates a configuration.
126    pub const fn new(
127        symbol_size: usize,
128        window_symbols: usize,
129        field: Field,
130    ) -> Result<Self, Error> {
131        if symbol_size == 0 {
132            return Err(Error::EmptySymbol);
133        }
134        if symbol_size > u16::MAX as usize {
135            return Err(Error::SymbolCapacityExceeded);
136        }
137        if window_symbols == 0 {
138            return Err(Error::EmptyWindow);
139        }
140        if window_symbols > RFC_MAX_WINDOW_SYMBOLS {
141            return Err(Error::WindowCapacityExceeded);
142        }
143        Ok(Self {
144            symbol_size,
145            window_symbols,
146            field,
147        })
148    }
149
150    /// Returns the active size of every source and repair symbol, in bytes.
151    pub const fn symbol_size(self) -> usize {
152        self.symbol_size
153    }
154
155    /// Returns the maximum number of symbols in the active coding window.
156    pub const fn window_symbols(self) -> usize {
157        self.window_symbols
158    }
159
160    /// Returns the configured finite field.
161    pub const fn field(self) -> Field {
162        self.field
163    }
164}
165
166/// An RFC 8681 coding-coefficient density threshold in the range `0..=15`.
167#[derive(Clone, Copy, Debug, Eq, PartialEq)]
168pub struct DensityThreshold(u8);
169
170impl DensityThreshold {
171    /// Full density: every coding coefficient is nonzero.
172    pub const FULL: Self = Self(15);
173
174    /// Creates a checked threshold.
175    pub const fn new(value: u8) -> Result<Self, Error> {
176        if value <= 15 {
177            Ok(Self(value))
178        } else {
179            Err(Error::InvalidDensityThreshold)
180        }
181    }
182
183    /// Returns the wire value.
184    pub const fn get(self) -> u8 {
185        self.0
186    }
187}
188
189impl TryFrom<u8> for DensityThreshold {
190    type Error = Error;
191
192    fn try_from(value: u8) -> Result<Self, Self::Error> {
193        Self::new(value)
194    }
195}
196
197impl From<DensityThreshold> for u8 {
198    fn from(value: DensityThreshold) -> Self {
199        value.get()
200    }
201}
202
203/// Per-repair parameters that need not be fixed for the lifetime of an encoder.
204#[derive(Clone, Copy, Debug, Eq, PartialEq)]
205pub struct RepairParameters {
206    repair_key: u16,
207    density: DensityThreshold,
208}
209
210impl RepairParameters {
211    /// Creates repair parameters from a coefficient-generator seed and density.
212    pub const fn new(repair_key: u16, density: DensityThreshold) -> Self {
213        Self {
214            repair_key,
215            density,
216        }
217    }
218
219    /// Returns the repair key.
220    pub const fn repair_key(self) -> u16 {
221        self.repair_key
222    }
223
224    /// Returns the density threshold.
225    pub const fn density(self) -> DensityThreshold {
226        self.density
227    }
228}
229
230/// The result of submitting a source symbol to a decoder.
231#[derive(Clone, Copy, Debug, Eq, PartialEq)]
232pub enum SourceStatus {
233    /// This source symbol was not previously known.
234    New,
235    /// This exact source symbol was already known, either received or recovered.
236    Duplicate,
237}
238
239/// The result of submitting a repair symbol to a decoder.
240#[must_use]
241#[derive(Clone, Copy, Debug, Eq, PartialEq)]
242pub struct DecodeReport {
243    innovative: bool,
244    recovered: usize,
245}
246
247/// The result of submitting a systematic source symbol to a decoder.
248#[must_use]
249#[derive(Clone, Copy, Debug, Eq, PartialEq)]
250pub struct SourceReport {
251    status: SourceStatus,
252    recovered: usize,
253}
254
255impl SourceReport {
256    /// Returns whether the submitted source was new or a duplicate.
257    pub const fn status(self) -> SourceStatus {
258        self.status
259    }
260
261    /// Returns the number of other source symbols recovered while processing it.
262    pub const fn recovered(self) -> usize {
263        self.recovered
264    }
265}
266
267impl DecodeReport {
268    /// Returns whether the repair increased the decoder's equation rank.
269    pub const fn is_innovative(self) -> bool {
270        self.innovative
271    }
272
273    /// Returns the number of source symbols recovered while processing the repair.
274    pub const fn recovered(self) -> usize {
275        self.recovered
276    }
277}
278
279/// Generates RFC 8681 coding coefficients into `output`.
280///
281/// The repair key initializes RFC 8682 TinyMT32. Each output byte is `0` or `1`
282/// for [`Field::Gf2`] and is an arbitrary field element for [`Field::Gf256`].
283pub fn generate_coding_coefficients(
284    field: Field,
285    repair_key: u16,
286    density: DensityThreshold,
287    output: &mut [u8],
288) {
289    if field == Field::Gf2 && density == DensityThreshold::FULL {
290        output.fill(1);
291        return;
292    }
293
294    let mut generator = TinyMt32::new(u32::from(repair_key));
295    match field {
296        Field::Gf2 => {
297            for coefficient in output {
298                *coefficient = u8::from(generator.next_u4() <= density.get());
299            }
300        }
301        Field::Gf256 => {
302            for coefficient in output {
303                if density != DensityThreshold::FULL && generator.next_u4() > density.get() {
304                    *coefficient = 0;
305                    continue;
306                }
307                *coefficient = nonzero_byte(&mut generator);
308            }
309        }
310    }
311}
312
313fn nonzero_byte(generator: &mut TinyMt32) -> u8 {
314    loop {
315        let value = generator.next_u8();
316        if value != 0 {
317            return value;
318        }
319    }
320}
321
322/// A systematic, bounded sliding-window RFC 8681 encoder.
323///
324/// `MAX_SYMBOL_SIZE` and `MAX_WINDOW_SYMBOLS` are hard memory capacities. The
325/// active sizes come from [`RlcConfig`] and may be smaller.
326pub struct Encoder<const MAX_SYMBOL_SIZE: usize, const MAX_WINDOW_SYMBOLS: usize> {
327    config: RlcConfig,
328    symbols: [[u8; MAX_SYMBOL_SIZE]; MAX_WINDOW_SYMBOLS],
329    head: usize,
330    len: usize,
331    first_esi: EncodingSymbolId,
332    next_esi: EncodingSymbolId,
333}
334
335impl<const MAX_SYMBOL_SIZE: usize, const MAX_WINDOW_SYMBOLS: usize>
336    Encoder<MAX_SYMBOL_SIZE, MAX_WINDOW_SYMBOLS>
337{
338    /// Creates an empty encoder whose first source symbol uses `initial_esi`.
339    pub fn new(config: RlcConfig, initial_esi: EncodingSymbolId) -> Result<Self, Error> {
340        validate_capacities::<MAX_SYMBOL_SIZE, MAX_WINDOW_SYMBOLS>(config)?;
341        Ok(Self {
342            config,
343            symbols: [[0; MAX_SYMBOL_SIZE]; MAX_WINDOW_SYMBOLS],
344            head: 0,
345            len: 0,
346            first_esi: initial_esi,
347            next_esi: initial_esi,
348        })
349    }
350
351    /// Returns the active configuration.
352    pub const fn config(&self) -> RlcConfig {
353        self.config
354    }
355
356    /// Returns the number of source symbols currently retained.
357    pub const fn window_len(&self) -> usize {
358        self.len
359    }
360
361    /// Returns the ESI and length of the current encoding window.
362    pub const fn window(&self) -> Option<(EncodingSymbolId, usize)> {
363        if self.len == 0 {
364            None
365        } else {
366            Some((self.first_esi, self.len))
367        }
368    }
369
370    /// Returns the ESI that will be assigned by the next [`push_source`](Self::push_source).
371    pub const fn next_esi(&self) -> EncodingSymbolId {
372        self.next_esi
373    }
374
375    /// Copies a source symbol into the encoding window and returns its ESI.
376    ///
377    /// Once the active window is full, this evicts exactly one oldest symbol.
378    pub fn push_source(&mut self, symbol: &[u8]) -> Result<EncodingSymbolId, Error> {
379        self.check_symbol_size(symbol)?;
380        let esi = self.next_esi;
381        self.next_esi = self.next_esi.wrapping_add(1);
382
383        let index = if self.len < self.config.window_symbols {
384            let index = (self.head + self.len) % self.config.window_symbols;
385            self.len += 1;
386            index
387        } else {
388            let index = self.head;
389            self.head = (self.head + 1) % self.config.window_symbols;
390            self.first_esi = self.first_esi.wrapping_add(1);
391            index
392        };
393        self.symbols[index][..self.config.symbol_size].copy_from_slice(symbol);
394        Ok(esi)
395    }
396
397    /// Removes up to `count` oldest symbols from the coding window.
398    ///
399    /// This supports application-level validity expiry in addition to automatic
400    /// eviction at the configured window size.
401    pub fn discard_oldest(&mut self, count: usize) {
402        let removed = count.min(self.len);
403        if removed == 0 {
404            return;
405        }
406        self.head = (self.head + removed) % self.config.window_symbols;
407        self.len -= removed;
408        self.first_esi = self.first_esi.wrapping_add(removed as u32);
409        if self.len == 0 {
410            self.first_esi = self.next_esi;
411        }
412    }
413
414    /// Encodes one repair symbol for the current window.
415    ///
416    /// The returned value contains all metadata needed to regenerate the coding
417    /// coefficients. The caller owns packetization and transport.
418    pub fn encode_repair(
419        &self,
420        parameters: RepairParameters,
421        output: &mut [u8],
422    ) -> Result<RepairPayloadId, Error> {
423        self.check_symbol_size(output)?;
424        if self.len == 0 {
425            return Err(Error::EmptyEncodingWindow);
426        }
427        if self.config.field == Field::Gf2
428            && parameters.density == DensityThreshold::FULL
429            && parameters.repair_key != 0
430        {
431            return Err(Error::RepairKeyMustBeZero);
432        }
433
434        output.fill(0);
435        match self.config.field {
436            Field::Gf2 if parameters.density == DensityThreshold::FULL => {
437                for offset in 0..self.len {
438                    self.add_source_to_repair(output, offset, 1);
439                }
440            }
441            Field::Gf2 => {
442                let mut generator = TinyMt32::new(u32::from(parameters.repair_key));
443                for offset in 0..self.len {
444                    let coefficient = u8::from(generator.next_u4() <= parameters.density.get());
445                    if coefficient != 0 {
446                        self.add_source_to_repair(output, offset, coefficient);
447                    }
448                }
449            }
450            Field::Gf256 => {
451                let mut generator = TinyMt32::new(u32::from(parameters.repair_key));
452                for offset in 0..self.len {
453                    if parameters.density != DensityThreshold::FULL
454                        && generator.next_u4() > parameters.density.get()
455                    {
456                        continue;
457                    }
458                    self.add_source_to_repair(output, offset, nonzero_byte(&mut generator));
459                }
460            }
461        }
462
463        RepairPayloadId::new(
464            parameters.repair_key,
465            parameters.density,
466            self.len as u16,
467            self.first_esi,
468        )
469        .map_err(|_| Error::WindowCapacityExceeded)
470    }
471
472    fn check_symbol_size(&self, symbol: &[u8]) -> Result<(), Error> {
473        if symbol.len() == self.config.symbol_size {
474            Ok(())
475        } else {
476            Err(Error::SymbolSizeMismatch)
477        }
478    }
479
480    #[inline]
481    fn add_source_to_repair(&self, output: &mut [u8], offset: usize, coefficient: u8) {
482        let index = (self.head + offset) % self.config.window_symbols;
483        add_scaled(
484            self.config.field,
485            output,
486            coefficient,
487            &self.symbols[index][..self.config.symbol_size],
488        );
489    }
490}
491
492#[derive(Clone, Copy)]
493struct Row<const MAX_SYMBOL_SIZE: usize, const MAX_WINDOW_SYMBOLS: usize> {
494    coefficients: [u8; MAX_WINDOW_SYMBOLS],
495    data: [u8; MAX_SYMBOL_SIZE],
496}
497
498impl<const MAX_SYMBOL_SIZE: usize, const MAX_WINDOW_SYMBOLS: usize>
499    Row<MAX_SYMBOL_SIZE, MAX_WINDOW_SYMBOLS>
500{
501    const ZERO: Self = Self {
502        coefficients: [0; MAX_WINDOW_SYMBOLS],
503        data: [0; MAX_SYMBOL_SIZE],
504    };
505}
506
507/// A bounded RFC 8681 sliding-window decoder.
508///
509/// The decoder maintains a reduced linear system without allocation. Source
510/// symbols are addressable with [`symbol`](Self::symbol) while they remain in
511/// the active window. Packet integrity must be checked before symbols are passed
512/// here because erasure coding cannot authenticate corrupted input.
513pub struct Decoder<
514    const MAX_SYMBOL_SIZE: usize,
515    const MAX_WINDOW_SYMBOLS: usize,
516    const MAX_EQUATIONS: usize,
517> {
518    config: RlcConfig,
519    equation_capacity: usize,
520    base_esi: EncodingSymbolId,
521    base_initialized: bool,
522    span: usize,
523    known: [bool; MAX_WINDOW_SYMBOLS],
524    symbols: [[u8; MAX_SYMBOL_SIZE]; MAX_WINDOW_SYMBOLS],
525    occupied: [bool; MAX_EQUATIONS],
526    rows: [Row<MAX_SYMBOL_SIZE, MAX_WINDOW_SYMBOLS>; MAX_EQUATIONS],
527    rank: usize,
528}
529
530/// An iterator over received and recovered symbols retained by a decoder.
531pub struct KnownSymbols<
532    'a,
533    const MAX_SYMBOL_SIZE: usize,
534    const MAX_WINDOW_SYMBOLS: usize,
535    const MAX_EQUATIONS: usize,
536> {
537    decoder: &'a Decoder<MAX_SYMBOL_SIZE, MAX_WINDOW_SYMBOLS, MAX_EQUATIONS>,
538    index: usize,
539}
540
541impl<'a, const MAX_SYMBOL_SIZE: usize, const MAX_WINDOW_SYMBOLS: usize, const MAX_EQUATIONS: usize>
542    Iterator for KnownSymbols<'a, MAX_SYMBOL_SIZE, MAX_WINDOW_SYMBOLS, MAX_EQUATIONS>
543{
544    type Item = (EncodingSymbolId, &'a [u8]);
545
546    fn next(&mut self) -> Option<Self::Item> {
547        while self.index < self.decoder.span {
548            let index = self.index;
549            self.index += 1;
550            if self.decoder.known[index] {
551                return Some((
552                    self.decoder.base_esi.wrapping_add(index as u32),
553                    &self.decoder.symbols[index][..self.decoder.config.symbol_size],
554                ));
555            }
556        }
557        None
558    }
559
560    fn size_hint(&self) -> (usize, Option<usize>) {
561        (0, Some(self.decoder.span.saturating_sub(self.index)))
562    }
563}
564
565impl<const MAX_SYMBOL_SIZE: usize, const MAX_WINDOW_SYMBOLS: usize, const MAX_EQUATIONS: usize>
566    core::iter::FusedIterator
567    for KnownSymbols<'_, MAX_SYMBOL_SIZE, MAX_WINDOW_SYMBOLS, MAX_EQUATIONS>
568{
569}
570
571impl<const MAX_SYMBOL_SIZE: usize, const MAX_WINDOW_SYMBOLS: usize, const MAX_EQUATIONS: usize>
572    Decoder<MAX_SYMBOL_SIZE, MAX_WINDOW_SYMBOLS, MAX_EQUATIONS>
573{
574    /// Creates an empty decoder with a bounded active equation count.
575    pub fn new(config: RlcConfig, equation_capacity: usize) -> Result<Self, Error> {
576        validate_capacities::<MAX_SYMBOL_SIZE, MAX_WINDOW_SYMBOLS>(config)?;
577        if equation_capacity == 0 || equation_capacity > MAX_EQUATIONS {
578            return Err(Error::EquationCapacityExceeded);
579        }
580        Ok(Self {
581            config,
582            equation_capacity,
583            base_esi: EncodingSymbolId::new(0),
584            base_initialized: false,
585            span: 0,
586            known: [false; MAX_WINDOW_SYMBOLS],
587            symbols: [[0; MAX_SYMBOL_SIZE]; MAX_WINDOW_SYMBOLS],
588            occupied: [false; MAX_EQUATIONS],
589            rows: [Row::ZERO; MAX_EQUATIONS],
590            rank: 0,
591        })
592    }
593
594    /// Returns the active configuration.
595    pub const fn config(&self) -> RlcConfig {
596        self.config
597    }
598
599    /// Returns the current rank of unresolved repair equations.
600    pub const fn rank(&self) -> usize {
601        self.rank
602    }
603
604    /// Returns the ESI and total span of the retained decoding window.
605    pub const fn window(&self) -> Option<(EncodingSymbolId, usize)> {
606        if self.span == 0 {
607            None
608        } else {
609            Some((self.base_esi, self.span))
610        }
611    }
612
613    /// Discards decoder state older than `first_retained_esi`.
614    ///
615    /// Equations that still depend on an unknown expired symbol are discarded.
616    /// This lets an integrating real-time protocol enforce its latency budget
617    /// even when no newer source symbol arrives.
618    pub fn discard_before(&mut self, first_retained_esi: EncodingSymbolId) -> Result<(), Error> {
619        if self.span == 0 {
620            if !self.base_initialized {
621                self.base_esi = first_retained_esi;
622                self.base_initialized = true;
623                return Ok(());
624            }
625            let count = sequence_delta(first_retained_esi, self.base_esi)?;
626            if count > 0 {
627                self.base_esi = first_retained_esi;
628            }
629            return Ok(());
630        }
631        let count = sequence_delta(first_retained_esi, self.base_esi)?;
632        if count > 0 {
633            self.drop_front(count as usize);
634        }
635        Ok(())
636    }
637
638    /// Returns a received or recovered symbol while it remains in the window.
639    pub fn symbol(&self, esi: EncodingSymbolId) -> Option<&[u8]> {
640        let offset = sequence_delta(esi, self.base_esi).ok()?;
641        if offset < 0 {
642            return None;
643        }
644        let index = offset as usize;
645        if index >= self.span || !self.known[index] {
646            return None;
647        }
648        Some(&self.symbols[index][..self.config.symbol_size])
649    }
650
651    /// Iterates over all known symbols in ascending wrapping ESI order.
652    pub fn known_symbols(
653        &self,
654    ) -> KnownSymbols<'_, MAX_SYMBOL_SIZE, MAX_WINDOW_SYMBOLS, MAX_EQUATIONS> {
655        KnownSymbols {
656            decoder: self,
657            index: 0,
658        }
659    }
660
661    /// Submits a systematic source symbol.
662    pub fn receive_source(
663        &mut self,
664        esi: EncodingSymbolId,
665        symbol: &[u8],
666    ) -> Result<SourceReport, Error> {
667        self.check_symbol_size(symbol)?;
668        let index = self.ensure_range(esi, 1)?;
669        if self.known[index] {
670            if self.symbols[index][..self.config.symbol_size] == *symbol {
671                return Ok(SourceReport {
672                    status: SourceStatus::Duplicate,
673                    recovered: 0,
674                });
675            }
676            return Err(Error::ConflictingSource);
677        }
678
679        self.store_known(index, symbol);
680        self.substitute_known(index)?;
681        let recovered = self.recover_singletons()?;
682        Ok(SourceReport {
683            status: SourceStatus::New,
684            recovered,
685        })
686    }
687
688    /// Submits one repair symbol and returns its contribution to decoding.
689    pub fn receive_repair(
690        &mut self,
691        id: RepairPayloadId,
692        symbol: &[u8],
693    ) -> Result<DecodeReport, Error> {
694        self.check_symbol_size(symbol)?;
695        let source_count = usize::from(id.source_symbols());
696        if source_count > self.config.window_symbols {
697            return Err(Error::RepairWindowTooLarge);
698        }
699        let start = self.ensure_range(id.first_source_esi(), source_count)?;
700
701        let mut row = Row::ZERO;
702        generate_coding_coefficients(
703            self.config.field,
704            id.repair_key(),
705            id.density(),
706            &mut row.coefficients[start..start + source_count],
707        );
708        row.data[..self.config.symbol_size].copy_from_slice(symbol);
709
710        for index in start..start + source_count {
711            let coefficient = row.coefficients[index];
712            if coefficient != 0 && self.known[index] {
713                add_scaled(
714                    self.config.field,
715                    &mut row.data[..self.config.symbol_size],
716                    coefficient,
717                    &self.symbols[index][..self.config.symbol_size],
718                );
719                row.coefficients[index] = 0;
720            }
721        }
722
723        for row_index in 0..self.equation_capacity {
724            if !self.occupied[row_index] {
725                continue;
726            }
727            let Some(pivot) = first_nonzero(&self.rows[row_index].coefficients[..self.span]) else {
728                continue;
729            };
730            let factor = row.coefficients[pivot];
731            if factor != 0 {
732                row_add_scaled(
733                    self.config.field,
734                    &mut row,
735                    factor,
736                    &self.rows[row_index],
737                    self.span,
738                    self.config.symbol_size,
739                );
740            }
741        }
742
743        let Some(pivot) = first_nonzero(&row.coefficients[..self.span]) else {
744            if row.data[..self.config.symbol_size]
745                .iter()
746                .any(|byte| *byte != 0)
747            {
748                return Err(Error::InconsistentEquation);
749            }
750            return Ok(DecodeReport {
751                innovative: false,
752                recovered: 0,
753            });
754        };
755
756        let Some(slot) = self.occupied[..self.equation_capacity]
757            .iter()
758            .position(|occupied| !occupied)
759        else {
760            return Err(Error::EquationStoreFull);
761        };
762
763        let inverse = self.config.field.inv(row.coefficients[pivot]);
764        row_scale(
765            self.config.field,
766            &mut row,
767            inverse,
768            self.span,
769            self.config.symbol_size,
770        );
771
772        for row_index in 0..self.equation_capacity {
773            if !self.occupied[row_index] {
774                continue;
775            }
776            let factor = self.rows[row_index].coefficients[pivot];
777            if factor != 0 {
778                row_add_scaled(
779                    self.config.field,
780                    &mut self.rows[row_index],
781                    factor,
782                    &row,
783                    self.span,
784                    self.config.symbol_size,
785                );
786            }
787        }
788
789        self.rows[slot] = row;
790        self.occupied[slot] = true;
791        self.rank += 1;
792        let recovered = self.recover_singletons()?;
793        Ok(DecodeReport {
794            innovative: true,
795            recovered,
796        })
797    }
798
799    fn check_symbol_size(&self, symbol: &[u8]) -> Result<(), Error> {
800        if symbol.len() == self.config.symbol_size {
801            Ok(())
802        } else {
803            Err(Error::SymbolSizeMismatch)
804        }
805    }
806
807    fn ensure_range(&mut self, first_esi: EncodingSymbolId, count: usize) -> Result<usize, Error> {
808        debug_assert!(count > 0);
809        if self.span == 0 {
810            if !self.base_initialized {
811                self.base_esi = first_esi;
812                self.base_initialized = true;
813                self.span = count;
814                return Ok(0);
815            }
816
817            let start = sequence_delta(first_esi, self.base_esi)?;
818            if start < 0 {
819                return Err(Error::WindowExpired);
820            }
821            let end = start as usize + count;
822            if end <= self.config.window_symbols {
823                self.extend_to(end);
824                return Ok(start as usize);
825            }
826            self.base_esi = first_esi
827                .wrapping_add(count as u32)
828                .wrapping_sub(self.config.window_symbols as u32);
829            self.span = self.config.window_symbols;
830            return Ok(self.config.window_symbols - count);
831        }
832
833        let start = sequence_delta(first_esi, self.base_esi)?;
834        let end = start + count as i64 - 1;
835        let current_end = self.span as i64 - 1;
836        let union_start = start.min(0);
837        let union_end = end.max(current_end);
838        let union_len = union_end - union_start + 1;
839        let capacity = self.config.window_symbols as i64;
840
841        if union_len <= capacity {
842            if union_start < 0 {
843                self.prepend((-union_start) as usize);
844            }
845            let wanted_span = union_len as usize;
846            self.extend_to(wanted_span);
847            return sequence_delta(first_esi, self.base_esi).map(|offset| offset as usize);
848        }
849
850        let new_base_offset = union_end - capacity + 1;
851        if new_base_offset <= 0 || start < new_base_offset {
852            return Err(Error::WindowExpired);
853        }
854        self.drop_front(new_base_offset as usize);
855        let new_end = sequence_delta(first_esi.wrapping_add((count - 1) as u32), self.base_esi)?;
856        self.extend_to(new_end as usize + 1);
857        sequence_delta(first_esi, self.base_esi).map(|offset| offset as usize)
858    }
859
860    fn prepend(&mut self, count: usize) {
861        debug_assert!(self.span + count <= self.config.window_symbols);
862        for index in (0..self.span).rev() {
863            self.known[index + count] = self.known[index];
864            self.symbols[index + count] = self.symbols[index];
865        }
866        for index in 0..count {
867            self.known[index] = false;
868            self.symbols[index].fill(0);
869        }
870        for row_index in 0..self.equation_capacity {
871            if !self.occupied[row_index] {
872                continue;
873            }
874            for index in (0..self.span).rev() {
875                self.rows[row_index].coefficients[index + count] =
876                    self.rows[row_index].coefficients[index];
877            }
878            self.rows[row_index].coefficients[..count].fill(0);
879        }
880        self.base_esi = self.base_esi.wrapping_sub(count as u32);
881        self.span += count;
882    }
883
884    fn extend_to(&mut self, new_span: usize) {
885        debug_assert!(new_span <= self.config.window_symbols);
886        for index in self.span..new_span {
887            self.known[index] = false;
888            self.symbols[index].fill(0);
889        }
890        self.span = self.span.max(new_span);
891    }
892
893    fn drop_front(&mut self, count: usize) {
894        if count >= self.span {
895            self.known[..self.span].fill(false);
896            self.clear_equations();
897            self.base_esi = self.base_esi.wrapping_add(count as u32);
898            self.span = 0;
899            return;
900        }
901
902        let old_span = self.span;
903        let retained = old_span - count;
904        for row_index in 0..self.equation_capacity {
905            if !self.occupied[row_index] {
906                continue;
907            }
908            if self.rows[row_index].coefficients[..count]
909                .iter()
910                .any(|coefficient| *coefficient != 0)
911            {
912                self.occupied[row_index] = false;
913                self.rank -= 1;
914                continue;
915            }
916            self.rows[row_index]
917                .coefficients
918                .copy_within(count..old_span, 0);
919            self.rows[row_index].coefficients[retained..old_span].fill(0);
920        }
921        self.known.copy_within(count..old_span, 0);
922        self.symbols.copy_within(count..old_span, 0);
923        self.known[retained..old_span].fill(false);
924        for symbol in &mut self.symbols[retained..old_span] {
925            symbol.fill(0);
926        }
927        self.base_esi = self.base_esi.wrapping_add(count as u32);
928        self.span = retained;
929    }
930
931    fn clear_equations(&mut self) {
932        self.occupied[..self.equation_capacity].fill(false);
933        self.rank = 0;
934    }
935
936    fn store_known(&mut self, index: usize, symbol: &[u8]) {
937        self.symbols[index][..self.config.symbol_size].copy_from_slice(symbol);
938        self.known[index] = true;
939    }
940
941    fn substitute_known(&mut self, index: usize) -> Result<(), Error> {
942        for row_index in 0..self.equation_capacity {
943            if !self.occupied[row_index] {
944                continue;
945            }
946            let coefficient = self.rows[row_index].coefficients[index];
947            if coefficient == 0 {
948                continue;
949            }
950            add_scaled(
951                self.config.field,
952                &mut self.rows[row_index].data[..self.config.symbol_size],
953                coefficient,
954                &self.symbols[index][..self.config.symbol_size],
955            );
956            self.rows[row_index].coefficients[index] = 0;
957        }
958        self.remove_zero_rows()
959    }
960
961    fn remove_zero_rows(&mut self) -> Result<(), Error> {
962        for row_index in 0..self.equation_capacity {
963            if !self.occupied[row_index]
964                || self.rows[row_index].coefficients[..self.span]
965                    .iter()
966                    .any(|coefficient| *coefficient != 0)
967            {
968                continue;
969            }
970            if self.rows[row_index].data[..self.config.symbol_size]
971                .iter()
972                .any(|byte| *byte != 0)
973            {
974                return Err(Error::InconsistentEquation);
975            }
976            self.occupied[row_index] = false;
977            self.rank -= 1;
978        }
979        Ok(())
980    }
981
982    fn recover_singletons(&mut self) -> Result<usize, Error> {
983        let mut recovered = 0;
984        loop {
985            let mut singleton = None;
986            for row_index in 0..self.equation_capacity {
987                if !self.occupied[row_index] {
988                    continue;
989                }
990                let mut only = None;
991                let mut multiple = false;
992                for (index, coefficient) in self.rows[row_index].coefficients[..self.span]
993                    .iter()
994                    .copied()
995                    .enumerate()
996                {
997                    if coefficient == 0 {
998                        continue;
999                    }
1000                    if only.is_some() {
1001                        multiple = true;
1002                        break;
1003                    }
1004                    only = Some(index);
1005                }
1006                if !multiple && let Some(symbol_index) = only {
1007                    singleton = Some((row_index, symbol_index));
1008                    break;
1009                }
1010            }
1011
1012            let Some((row_index, symbol_index)) = singleton else {
1013                break;
1014            };
1015            let coefficient = self.rows[row_index].coefficients[symbol_index];
1016            let inverse = self.config.field.inv(coefficient);
1017            if self.known[symbol_index] {
1018                let matches = if inverse == 1 {
1019                    self.symbols[symbol_index][..self.config.symbol_size]
1020                        == self.rows[row_index].data[..self.config.symbol_size]
1021                } else {
1022                    self.symbols[symbol_index][..self.config.symbol_size]
1023                        .iter()
1024                        .zip(&self.rows[row_index].data[..self.config.symbol_size])
1025                        .all(|(known, encoded)| *known == self.config.field.mul(*encoded, inverse))
1026                };
1027                if !matches {
1028                    return Err(Error::ConflictingSource);
1029                }
1030            } else {
1031                if inverse == 1 {
1032                    self.symbols[symbol_index][..self.config.symbol_size]
1033                        .copy_from_slice(&self.rows[row_index].data[..self.config.symbol_size]);
1034                } else {
1035                    for (decoded, encoded) in self.symbols[symbol_index][..self.config.symbol_size]
1036                        .iter_mut()
1037                        .zip(&self.rows[row_index].data[..self.config.symbol_size])
1038                    {
1039                        *decoded = self.config.field.mul(*encoded, inverse);
1040                    }
1041                }
1042                self.known[symbol_index] = true;
1043                recovered += 1;
1044            }
1045            self.occupied[row_index] = false;
1046            self.rank -= 1;
1047            self.substitute_known(symbol_index)?;
1048        }
1049        Ok(recovered)
1050    }
1051}
1052
1053fn validate_capacities<const MAX_SYMBOL_SIZE: usize, const MAX_WINDOW_SYMBOLS: usize>(
1054    config: RlcConfig,
1055) -> Result<(), Error> {
1056    if config.symbol_size > MAX_SYMBOL_SIZE {
1057        return Err(Error::SymbolCapacityExceeded);
1058    }
1059    if config.window_symbols > MAX_WINDOW_SYMBOLS {
1060        return Err(Error::WindowCapacityExceeded);
1061    }
1062    Ok(())
1063}
1064
1065fn sequence_delta(value: EncodingSymbolId, base: EncodingSymbolId) -> Result<i64, Error> {
1066    let distance = value.get().wrapping_sub(base.get());
1067    if distance == 0x8000_0000 {
1068        return Err(Error::AmbiguousSequence);
1069    }
1070    Ok(i64::from(distance as i32))
1071}
1072
1073fn add_scaled(field: Field, target: &mut [u8], coefficient: u8, source: &[u8]) {
1074    debug_assert_eq!(target.len(), source.len());
1075    match (field, coefficient) {
1076        (_, 0) => {}
1077        (Field::Gf2, _) | (Field::Gf256, 1) => {
1078            for (target, source) in target.iter_mut().zip(source) {
1079                *target ^= source;
1080            }
1081        }
1082        (Field::Gf256, _) => {
1083            for (target, source) in target.iter_mut().zip(source) {
1084                *target ^= field.mul(coefficient, *source);
1085            }
1086        }
1087    }
1088}
1089
1090fn first_nonzero(values: &[u8]) -> Option<usize> {
1091    values.iter().position(|value| *value != 0)
1092}
1093
1094fn row_add_scaled<const MAX_SYMBOL_SIZE: usize, const MAX_WINDOW_SYMBOLS: usize>(
1095    field: Field,
1096    target: &mut Row<MAX_SYMBOL_SIZE, MAX_WINDOW_SYMBOLS>,
1097    coefficient: u8,
1098    source: &Row<MAX_SYMBOL_SIZE, MAX_WINDOW_SYMBOLS>,
1099    span: usize,
1100    symbol_size: usize,
1101) {
1102    for (target, source) in target.coefficients[..span]
1103        .iter_mut()
1104        .zip(&source.coefficients[..span])
1105    {
1106        *target ^= field.mul(coefficient, *source);
1107    }
1108    add_scaled(
1109        field,
1110        &mut target.data[..symbol_size],
1111        coefficient,
1112        &source.data[..symbol_size],
1113    );
1114}
1115
1116fn row_scale<const MAX_SYMBOL_SIZE: usize, const MAX_WINDOW_SYMBOLS: usize>(
1117    field: Field,
1118    row: &mut Row<MAX_SYMBOL_SIZE, MAX_WINDOW_SYMBOLS>,
1119    coefficient: u8,
1120    span: usize,
1121    symbol_size: usize,
1122) {
1123    if coefficient == 1 {
1124        return;
1125    }
1126    for value in &mut row.coefficients[..span] {
1127        *value = field.mul(*value, coefficient);
1128    }
1129    for value in &mut row.data[..symbol_size] {
1130        *value = field.mul(*value, coefficient);
1131    }
1132}
1133
1134#[cfg(test)]
1135mod tests {
1136    use super::*;
1137
1138    const SYMBOL_CAPACITY: usize = 16;
1139    const WINDOW_CAPACITY: usize = 8;
1140    const EQUATION_CAPACITY: usize = 8;
1141
1142    fn config(field: Field) -> RlcConfig {
1143        RlcConfig::new(4, WINDOW_CAPACITY, field).unwrap()
1144    }
1145
1146    const fn esi(value: u32) -> EncodingSymbolId {
1147        EncodingSymbolId::new(value)
1148    }
1149
1150    #[test]
1151    fn coefficient_vectors_match_rfc_small_integer_outputs() {
1152        let mut coefficients = [0; 10];
1153        generate_coding_coefficients(Field::Gf256, 1, DensityThreshold::FULL, &mut coefficients);
1154        assert_eq!(
1155            coefficients,
1156            [37, 225, 177, 176, 21, 246, 54, 139, 168, 237]
1157        );
1158
1159        generate_coding_coefficients(
1160            Field::Gf2,
1161            1,
1162            DensityThreshold::new(7).unwrap(),
1163            &mut coefficients,
1164        );
1165        assert_eq!(coefficients, [1, 1, 1, 1, 1, 1, 1, 0, 0, 0]);
1166
1167        generate_coding_coefficients(
1168            Field::Gf256,
1169            1,
1170            DensityThreshold::new(7).unwrap(),
1171            &mut coefficients,
1172        );
1173        assert_eq!(coefficients, [225, 176, 246, 139, 0, 0, 187, 0, 0, 0]);
1174    }
1175
1176    #[test]
1177    fn encoder_is_systematic_and_slides_across_esi_wrap() {
1178        let mut encoder = Encoder::<SYMBOL_CAPACITY, 3>::new(
1179            RlcConfig::new(4, 3, Field::Gf2).unwrap(),
1180            esi(u32::MAX - 1),
1181        )
1182        .unwrap();
1183        assert_eq!(encoder.push_source(&[1, 2, 3, 4]), Ok(esi(u32::MAX - 1)));
1184        assert_eq!(encoder.push_source(&[5, 6, 7, 8]), Ok(esi(u32::MAX)));
1185        assert_eq!(encoder.push_source(&[9, 10, 11, 12]), Ok(esi(0)));
1186        assert_eq!(encoder.push_source(&[13, 14, 15, 16]), Ok(esi(1)));
1187
1188        let mut repair = [0; 4];
1189        let id = encoder
1190            .encode_repair(
1191                RepairParameters::new(0, DensityThreshold::FULL),
1192                &mut repair,
1193            )
1194            .unwrap();
1195        assert_eq!(id.first_source_esi(), esi(u32::MAX));
1196        assert_eq!(id.source_symbols(), 3);
1197        assert_eq!(repair, [1, 2, 3, 20]);
1198    }
1199
1200    #[test]
1201    fn decoder_recovers_one_missing_binary_symbol() {
1202        let config = config(Field::Gf2);
1203        let mut encoder =
1204            Encoder::<SYMBOL_CAPACITY, WINDOW_CAPACITY>::new(config, esi(10)).unwrap();
1205        let mut decoder = Decoder::<SYMBOL_CAPACITY, WINDOW_CAPACITY, EQUATION_CAPACITY>::new(
1206            config,
1207            EQUATION_CAPACITY,
1208        )
1209        .unwrap();
1210
1211        let symbols = [[1, 2, 3, 4], [9, 8, 7, 6], [3, 1, 4, 1]];
1212        for symbol in &symbols {
1213            encoder.push_source(symbol).unwrap();
1214        }
1215        let _ = decoder.receive_source(esi(10), &symbols[0]).unwrap();
1216        let _ = decoder.receive_source(esi(12), &symbols[2]).unwrap();
1217
1218        let mut repair = [0; 4];
1219        let id = encoder
1220            .encode_repair(
1221                RepairParameters::new(0, DensityThreshold::FULL),
1222                &mut repair,
1223            )
1224            .unwrap();
1225        let report = decoder.receive_repair(id, &repair).unwrap();
1226        assert!(report.is_innovative());
1227        assert_eq!(report.recovered(), 1);
1228        assert_eq!(decoder.symbol(esi(11)), Some(symbols[1].as_slice()));
1229        assert!(!decoder.receive_repair(id, &repair).unwrap().is_innovative());
1230    }
1231
1232    #[test]
1233    fn decoder_reduces_multiple_gf256_equations() {
1234        let config = config(Field::Gf256);
1235        let mut encoder =
1236            Encoder::<SYMBOL_CAPACITY, WINDOW_CAPACITY>::new(config, esi(50)).unwrap();
1237        let mut decoder = Decoder::<SYMBOL_CAPACITY, WINDOW_CAPACITY, EQUATION_CAPACITY>::new(
1238            config,
1239            EQUATION_CAPACITY,
1240        )
1241        .unwrap();
1242        let symbols = [[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15]];
1243        for symbol in &symbols {
1244            encoder.push_source(symbol).unwrap();
1245        }
1246        let _ = decoder.receive_source(esi(50), &symbols[0]).unwrap();
1247        let _ = decoder.receive_source(esi(53), &symbols[3]).unwrap();
1248
1249        let mut repair_a = [0; 4];
1250        let mut repair_b = [0; 4];
1251        let id_a = encoder
1252            .encode_repair(
1253                RepairParameters::new(41, DensityThreshold::FULL),
1254                &mut repair_a,
1255            )
1256            .unwrap();
1257        let id_b = encoder
1258            .encode_repair(
1259                RepairParameters::new(42, DensityThreshold::FULL),
1260                &mut repair_b,
1261            )
1262            .unwrap();
1263
1264        let _ = decoder.receive_repair(id_b, &repair_b).unwrap();
1265        let report = decoder.receive_repair(id_a, &repair_a).unwrap();
1266        assert_eq!(report.recovered(), 2);
1267        assert_eq!(decoder.symbol(esi(51)), Some(symbols[1].as_slice()));
1268        assert_eq!(decoder.symbol(esi(52)), Some(symbols[2].as_slice()));
1269        assert_eq!(decoder.rank(), 0);
1270    }
1271
1272    #[test]
1273    fn decoder_accepts_reorder_duplicates_and_wrap() {
1274        let config = RlcConfig::new(4, 5, Field::Gf256).unwrap();
1275        let mut decoder = Decoder::<8, 5, 5>::new(config, 5).unwrap();
1276        let before_wrap = [1, 2, 3, 4];
1277        let after_wrap = [5, 6, 7, 8];
1278
1279        assert_eq!(
1280            decoder
1281                .receive_source(esi(0), &after_wrap)
1282                .map(SourceReport::status),
1283            Ok(SourceStatus::New),
1284        );
1285        assert_eq!(
1286            decoder
1287                .receive_source(esi(u32::MAX), &before_wrap)
1288                .map(SourceReport::status),
1289            Ok(SourceStatus::New),
1290        );
1291        assert_eq!(
1292            decoder
1293                .receive_source(esi(0), &after_wrap)
1294                .map(SourceReport::status),
1295            Ok(SourceStatus::Duplicate),
1296        );
1297        assert_eq!(decoder.symbol(esi(u32::MAX)), Some(before_wrap.as_slice()));
1298        assert_eq!(decoder.symbol(esi(0)), Some(after_wrap.as_slice()));
1299    }
1300
1301    #[test]
1302    fn repair_can_arrive_before_systematic_symbols() {
1303        let config = RlcConfig::new(4, 4, Field::Gf256).unwrap();
1304        let mut encoder = Encoder::<4, 4>::new(config, esi(100)).unwrap();
1305        let mut decoder = Decoder::<4, 4, 4>::new(config, 4).unwrap();
1306        let symbols = [[1, 3, 3, 7], [2, 4, 6, 8], [5, 5, 5, 5]];
1307        for symbol in &symbols {
1308            encoder.push_source(symbol).unwrap();
1309        }
1310        assert_eq!(encoder.window(), Some((esi(100), 3)));
1311
1312        let mut repair = [0; 4];
1313        let id = encoder
1314            .encode_repair(
1315                RepairParameters::new(99, DensityThreshold::FULL),
1316                &mut repair,
1317            )
1318            .unwrap();
1319        assert_eq!(decoder.receive_repair(id, &repair).unwrap().recovered(), 0);
1320        let _ = decoder.receive_source(esi(102), &symbols[2]).unwrap();
1321        let source_report = decoder.receive_source(esi(100), &symbols[0]).unwrap();
1322        assert_eq!(source_report.recovered(), 1);
1323        assert_eq!(decoder.symbol(esi(101)), Some(symbols[1].as_slice()));
1324
1325        decoder.discard_before(esi(102)).unwrap();
1326        assert_eq!(decoder.window(), Some((esi(102), 1)));
1327        assert_eq!(decoder.symbol(esi(100)), None);
1328
1329        decoder.discard_before(esi(200)).unwrap();
1330        assert_eq!(decoder.window(), None);
1331        assert_eq!(
1332            decoder.receive_source(esi(199), &[0; 4]),
1333            Err(Error::WindowExpired)
1334        );
1335        assert_eq!(
1336            decoder
1337                .receive_source(esi(200), &[0; 4])
1338                .map(SourceReport::status),
1339            Ok(SourceStatus::New),
1340        );
1341        assert!(decoder.known_symbols().map(|(id, _)| id).eq([esi(200)]));
1342    }
1343
1344    #[test]
1345    fn validates_sizes_capacities_and_binary_key_rule() {
1346        assert_eq!(RlcConfig::new(0, 1, Field::Gf2), Err(Error::EmptySymbol));
1347        assert_eq!(
1348            RlcConfig::new(1, 4096, Field::Gf2),
1349            Err(Error::WindowCapacityExceeded)
1350        );
1351        let config = RlcConfig::new(4, 4, Field::Gf2).unwrap();
1352        assert!(matches!(
1353            Encoder::<3, 4>::new(config, esi(0)),
1354            Err(Error::SymbolCapacityExceeded)
1355        ));
1356        assert!(matches!(
1357            Decoder::<4, 4, 1>::new(config, 2),
1358            Err(Error::EquationCapacityExceeded)
1359        ));
1360
1361        let mut encoder = Encoder::<4, 4>::new(config, esi(0)).unwrap();
1362        assert_eq!(encoder.push_source(&[1, 2]), Err(Error::SymbolSizeMismatch));
1363        encoder.push_source(&[1, 2, 3, 4]).unwrap();
1364        assert_eq!(
1365            encoder.encode_repair(
1366                RepairParameters::new(1, DensityThreshold::FULL),
1367                &mut [0; 4],
1368            ),
1369            Err(Error::RepairKeyMustBeZero)
1370        );
1371    }
1372
1373    #[test]
1374    fn equation_capacity_is_a_hard_bound() {
1375        let config = RlcConfig::new(1, 3, Field::Gf256).unwrap();
1376        let mut encoder = Encoder::<1, 3>::new(config, esi(0)).unwrap();
1377        let mut decoder = Decoder::<1, 3, 1>::new(config, 1).unwrap();
1378        for byte in 1..=3 {
1379            encoder.push_source(&[byte]).unwrap();
1380        }
1381
1382        let mut repair = [0];
1383        let first = encoder
1384            .encode_repair(
1385                RepairParameters::new(1, DensityThreshold::FULL),
1386                &mut repair,
1387            )
1388            .unwrap();
1389        let _ = decoder.receive_repair(first, &repair).unwrap();
1390        let second = encoder
1391            .encode_repair(
1392                RepairParameters::new(2, DensityThreshold::FULL),
1393                &mut repair,
1394            )
1395            .unwrap();
1396        assert_eq!(
1397            decoder.receive_repair(second, &repair),
1398            Err(Error::EquationStoreFull)
1399        );
1400    }
1401
1402    #[test]
1403    fn old_ranges_and_conflicting_duplicates_are_rejected() {
1404        let config = RlcConfig::new(1, 3, Field::Gf256).unwrap();
1405        let mut decoder = Decoder::<1, 3, 3>::new(config, 3).unwrap();
1406        let _ = decoder.receive_source(esi(10), &[10]).unwrap();
1407        let _ = decoder.receive_source(esi(11), &[11]).unwrap();
1408        let _ = decoder.receive_source(esi(12), &[12]).unwrap();
1409        let _ = decoder.receive_source(esi(13), &[13]).unwrap();
1410
1411        assert_eq!(
1412            decoder.receive_source(esi(10), &[10]),
1413            Err(Error::WindowExpired),
1414        );
1415        assert_eq!(
1416            decoder.receive_source(esi(13), &[99]),
1417            Err(Error::ConflictingSource)
1418        );
1419    }
1420}