1use core::fmt;
4
5use crate::{Field, RepairPayloadId, tinymt::TinyMt32};
6
7const RFC_MAX_WINDOW_SYMBOLS: usize = 0x0fff;
8
9#[derive(Clone, Copy, Debug, Eq, PartialEq)]
11pub enum Error {
12 EmptySymbol,
14 SymbolCapacityExceeded,
16 SymbolSizeMismatch,
18 EmptyWindow,
20 WindowCapacityExceeded,
22 EquationCapacityExceeded,
24 InvalidDensityThreshold,
26 RepairKeyMustBeZero,
28 EmptyEncodingWindow,
30 RepairWindowTooLarge,
32 WindowExpired,
34 AmbiguousSequence,
36 EquationStoreFull,
38 ConflictingSource,
40 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#[derive(Clone, Copy, Debug, Eq, PartialEq)]
70pub struct RlcConfig {
71 symbol_size: usize,
72 window_symbols: usize,
73 field: Field,
74}
75
76#[repr(transparent)]
81#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
82pub struct EncodingSymbolId(u32);
83
84impl EncodingSymbolId {
85 pub const fn new(value: u32) -> Self {
87 Self(value)
88 }
89
90 pub const fn get(self) -> u32 {
92 self.0
93 }
94
95 pub const fn wrapping_add(self, count: u32) -> Self {
97 Self(self.0.wrapping_add(count))
98 }
99
100 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 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 pub const fn symbol_size(self) -> usize {
152 self.symbol_size
153 }
154
155 pub const fn window_symbols(self) -> usize {
157 self.window_symbols
158 }
159
160 pub const fn field(self) -> Field {
162 self.field
163 }
164}
165
166#[derive(Clone, Copy, Debug, Eq, PartialEq)]
168pub struct DensityThreshold(u8);
169
170impl DensityThreshold {
171 pub const FULL: Self = Self(15);
173
174 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 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#[derive(Clone, Copy, Debug, Eq, PartialEq)]
205pub struct RepairParameters {
206 repair_key: u16,
207 density: DensityThreshold,
208}
209
210impl RepairParameters {
211 pub const fn new(repair_key: u16, density: DensityThreshold) -> Self {
213 Self {
214 repair_key,
215 density,
216 }
217 }
218
219 pub const fn repair_key(self) -> u16 {
221 self.repair_key
222 }
223
224 pub const fn density(self) -> DensityThreshold {
226 self.density
227 }
228}
229
230#[derive(Clone, Copy, Debug, Eq, PartialEq)]
232pub enum SourceStatus {
233 New,
235 Duplicate,
237}
238
239#[must_use]
241#[derive(Clone, Copy, Debug, Eq, PartialEq)]
242pub struct DecodeReport {
243 innovative: bool,
244 recovered: usize,
245}
246
247#[must_use]
249#[derive(Clone, Copy, Debug, Eq, PartialEq)]
250pub struct SourceReport {
251 status: SourceStatus,
252 recovered: usize,
253}
254
255impl SourceReport {
256 pub const fn status(self) -> SourceStatus {
258 self.status
259 }
260
261 pub const fn recovered(self) -> usize {
263 self.recovered
264 }
265}
266
267impl DecodeReport {
268 pub const fn is_innovative(self) -> bool {
270 self.innovative
271 }
272
273 pub const fn recovered(self) -> usize {
275 self.recovered
276 }
277}
278
279pub 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
322pub 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 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 pub const fn config(&self) -> RlcConfig {
353 self.config
354 }
355
356 pub const fn window_len(&self) -> usize {
358 self.len
359 }
360
361 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 pub const fn next_esi(&self) -> EncodingSymbolId {
372 self.next_esi
373 }
374
375 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 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 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
507pub 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
530pub 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 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 pub const fn config(&self) -> RlcConfig {
596 self.config
597 }
598
599 pub const fn rank(&self) -> usize {
601 self.rank
602 }
603
604 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 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 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 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 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 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}