rmt_flute/fec.rs
1//! FEC Building Block — Block Partitioning Algorithm (RFC 5052 §9.1).
2//!
3//! RFC 5052 §9 ("FEC Schemes and CDPs SHOULD use these algorithms in
4//! preference to scheme- or protocol-specific algorithms, where appropriate")
5//! defines exactly one concrete *algorithm*: how to split an `L`-octet
6//! transport object into `N` source blocks of as-equal-as-possible length,
7//! given a maximum source block length `B` (symbols) and an encoding symbol
8//! length `E` (octets). [`SourceBlockPartition`] is that algorithm — see
9//! `docs/fec.md` §5/§9 for the full transcription and for why this module
10//! stops there rather than reproducing any FEC-scheme-specific FEC Payload ID
11//! (`docs/fec.md` §3/§8) or Scheme-specific FEC OTI layout (§2.3/§8). Those
12//! stay opaque byte slices the caller supplies — exactly like
13//! [`crate::AlcPacket::fec_payload_id`] and [`crate::FecPayloadId128`] already
14//! do — because their bit layout is FEC-scheme dependent, not defined by
15//! ALC/FLUTE/NORM or by this crate.
16//!
17//! This is deliberately the *only* thing this module does: it operates
18//! entirely on symbol **counts**, never on FEC-scheme-specific bytes, so it is
19//! equally usable by a Compact-No-Code, Raptor, RaptorQ, or any future FEC
20//! scheme's consumer — `dvb-mabr` and `atsc3-route` both need exactly this
21//! shape (issue #944).
22
23use crate::error::{Error, Result};
24
25/// The source-block structure of a transport object, per RFC 5052 §9.1's
26/// Block Partitioning Algorithm.
27///
28/// Given a transport object of `transfer_length` octets (`L`), an
29/// `encoding_symbol_length` (`E`) and a `max_source_block_length` (`B`), RFC
30/// 5052 splits the object into `num_blocks` (`N`) source blocks: the first
31/// `larger_blocks` (`I`) blocks each have `larger_block_len` (`A_large`)
32/// source symbols, and the remaining `num_blocks - larger_blocks` blocks each
33/// have `smaller_block_len` (`A_small`) source symbols. Every source symbol is
34/// `E` octets, **except** the very last source symbol of the very last source
35/// block ([`Self::last_symbol_len`]).
36///
37/// All three inputs are RFC 5052 Common FEC OTI elements (§6.2.4) — this type
38/// does not read wire bytes; the caller supplies them from wherever the CDP
39/// carried them (ALC's `EXT_FTI`, a FLUTE FDT attribute, …).
40#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
41#[cfg_attr(feature = "serde", derive(serde::Serialize))]
42pub struct SourceBlockPartition {
43 /// The transport object length in octets (`L`, Transfer-Length).
44 pub transfer_length: u64,
45 /// The encoding symbol length in octets (`E`, Encoding-Symbol-Length).
46 pub encoding_symbol_length: u32,
47 /// Total source symbols in the object (`T = ceil(L / E)`).
48 pub source_symbols: u64,
49 /// Number of source blocks (`N = ceil(T / B)`).
50 pub num_blocks: u64,
51 /// Source symbols in each of the first `larger_blocks` blocks
52 /// (`A_large = ceil(T / N)`).
53 pub larger_block_len: u64,
54 /// Source symbols in each of the remaining blocks
55 /// (`A_small = floor(T / N)`).
56 pub smaller_block_len: u64,
57 /// Number of "larger" blocks (`I = T - A_small * N`).
58 pub larger_blocks: u64,
59}
60
61impl SourceBlockPartition {
62 /// Apply RFC 5052 §9.1's Block Partitioning Algorithm.
63 ///
64 /// `transfer_length` is the transport object length in octets (`L`),
65 /// `encoding_symbol_length` is `E`, and `max_source_block_length` is `B`.
66 ///
67 /// A zero-length object (`transfer_length == 0`) yields zero source
68 /// symbols and zero source blocks — RFC 5052's ceiling division treats
69 /// `ceil(0/E)` as `0`, not `1`.
70 ///
71 /// # Errors
72 ///
73 /// Returns [`Error::InvalidField`] if `encoding_symbol_length` or
74 /// `max_source_block_length` is `0` (both are divisors in the algorithm;
75 /// RFC 5052 gives no meaning to either being zero).
76 pub fn new(
77 transfer_length: u64,
78 encoding_symbol_length: u32,
79 max_source_block_length: u32,
80 ) -> Result<Self> {
81 if encoding_symbol_length == 0 {
82 return Err(Error::InvalidField {
83 what: "Encoding-Symbol-Length",
84 reason: "must be non-zero",
85 });
86 }
87 if max_source_block_length == 0 {
88 return Err(Error::InvalidField {
89 what: "Maximum-Source-Block-Length",
90 reason: "must be non-zero",
91 });
92 }
93 let e = encoding_symbol_length as u64;
94 let b = max_source_block_length as u64;
95
96 // First step (§9.1.1): T = ceil(L/E); N = ceil(T/B). `div_ceil` is
97 // division-based (not addition-based), so it cannot overflow here.
98 let source_symbols = transfer_length.div_ceil(e);
99 let num_blocks = if source_symbols == 0 {
100 0
101 } else {
102 source_symbols.div_ceil(b)
103 };
104
105 // Second step (§9.1.2): A_large, A_small, I.
106 let (larger_block_len, smaller_block_len, larger_blocks) = if num_blocks == 0 {
107 (0, 0, 0)
108 } else {
109 let a_large = source_symbols.div_ceil(num_blocks);
110 let a_small = source_symbols / num_blocks;
111 let i = source_symbols - a_small * num_blocks;
112 (a_large, a_small, i)
113 };
114
115 Ok(SourceBlockPartition {
116 transfer_length,
117 encoding_symbol_length,
118 source_symbols,
119 num_blocks,
120 larger_block_len,
121 smaller_block_len,
122 larger_blocks,
123 })
124 }
125
126 /// Number of source symbols in source block `index` (0-based), or `None`
127 /// if `index >= num_blocks`.
128 ///
129 /// The first `larger_blocks` blocks (indices `0..larger_blocks`) each have
130 /// `larger_block_len` symbols; the remaining blocks have
131 /// `smaller_block_len`.
132 pub fn block_len(&self, index: u64) -> Option<u64> {
133 if index < self.larger_blocks {
134 Some(self.larger_block_len)
135 } else if index < self.num_blocks {
136 Some(self.smaller_block_len)
137 } else {
138 None
139 }
140 }
141
142 /// Length in octets of the very last source symbol of the very last
143 /// source block (RFC 5052 §9.1: `L - floor((L-1)/E)*E`) — the object's
144 /// actual trailing remainder, since `L` is not generally an exact
145 /// multiple of `E`. `None` if the object has zero source symbols (there
146 /// is no "last symbol" to speak of).
147 pub fn last_symbol_len(&self) -> Option<u32> {
148 if self.source_symbols == 0 {
149 return None;
150 }
151 let l = self.transfer_length;
152 let e = self.encoding_symbol_length as u64;
153 let len = l - ((l - 1) / e) * e;
154 Some(len as u32)
155 }
156}
157
158#[cfg(test)]
159mod tests {
160 use super::*;
161 use alloc::vec::Vec;
162
163 #[test]
164 fn rejects_zero_divisors() {
165 assert!(matches!(
166 SourceBlockPartition::new(100, 0, 10),
167 Err(Error::InvalidField {
168 what: "Encoding-Symbol-Length",
169 ..
170 })
171 ));
172 assert!(matches!(
173 SourceBlockPartition::new(100, 10, 0),
174 Err(Error::InvalidField {
175 what: "Maximum-Source-Block-Length",
176 ..
177 })
178 ));
179 }
180
181 #[test]
182 fn zero_length_object_has_no_symbols_or_blocks() {
183 // L=0: T = ceil(0/E) = 0, N = ceil(0/B) = 0 (RFC 5052 §9.1.1).
184 let p = SourceBlockPartition::new(0, 1000, 10).unwrap();
185 assert_eq!(p.source_symbols, 0);
186 assert_eq!(p.num_blocks, 0);
187 assert_eq!(p.larger_block_len, 0);
188 assert_eq!(p.smaller_block_len, 0);
189 assert_eq!(p.larger_blocks, 0);
190 assert_eq!(p.block_len(0), None);
191 assert_eq!(p.last_symbol_len(), None);
192 }
193
194 // Exact-multiple worked example, hand-derived from RFC 5052 §9.1's own
195 // formulas (the RFC gives no numeric worked example itself — verified
196 // against the IETF-published text of RFC 5052 §9.1):
197 // L=10000, E=1000, B=3
198 // T = ceil(10000/1000) = 10
199 // N = ceil(10/3) = 4
200 // A_large = ceil(10/4) = 3, A_small = floor(10/4) = 2, I = 10-2*4 = 2
201 // so blocks 0,1 have 3 symbols; blocks 2,3 have 2 symbols (3+3+2+2=10).
202 #[test]
203 fn exact_multiple_worked_example() {
204 let p = SourceBlockPartition::new(10_000, 1000, 3).unwrap();
205 assert_eq!(p.source_symbols, 10);
206 assert_eq!(p.num_blocks, 4);
207 assert_eq!(p.larger_block_len, 3);
208 assert_eq!(p.smaller_block_len, 2);
209 assert_eq!(p.larger_blocks, 2);
210
211 let lens: Vec<u64> = (0..p.num_blocks).map(|i| p.block_len(i).unwrap()).collect();
212 assert_eq!(lens, [3, 3, 2, 2]);
213 assert_eq!(lens.iter().sum::<u64>(), p.source_symbols);
214 assert_eq!(p.block_len(p.num_blocks), None);
215
216 // L is an exact multiple of E, so the trailing remainder is a full
217 // symbol.
218 assert_eq!(p.last_symbol_len(), Some(1000));
219 }
220
221 // Non-exact-multiple worked example (trailing remainder exercised):
222 // L=10005, E=1000, B=3
223 // T = ceil(10005/1000) = 11
224 // N = ceil(11/3) = 4
225 // A_large = ceil(11/4) = 3, A_small = floor(11/4) = 2, I = 11-2*4 = 3
226 // so blocks 0,1,2 have 3 symbols; block 3 has 2 symbols (3+3+3+2=11).
227 #[test]
228 fn non_exact_multiple_worked_example() {
229 let p = SourceBlockPartition::new(10_005, 1000, 3).unwrap();
230 assert_eq!(p.source_symbols, 11);
231 assert_eq!(p.num_blocks, 4);
232 assert_eq!(p.larger_block_len, 3);
233 assert_eq!(p.smaller_block_len, 2);
234 assert_eq!(p.larger_blocks, 3);
235
236 let lens: Vec<u64> = (0..p.num_blocks).map(|i| p.block_len(i).unwrap()).collect();
237 assert_eq!(lens, [3, 3, 3, 2]);
238 assert_eq!(lens.iter().sum::<u64>(), p.source_symbols);
239
240 // 10005 = 10*1000 + 5, so the trailing remainder is 5 octets.
241 assert_eq!(p.last_symbol_len(), Some(5));
242 }
243
244 // B larger than T collapses to a single source block (N=1), and A_large
245 // == A_small == T in that case (I = T - T*1 = 0).
246 #[test]
247 fn max_block_length_exceeding_total_symbols_yields_one_block() {
248 let p = SourceBlockPartition::new(100, 10, 1000).unwrap();
249 assert_eq!(p.source_symbols, 10);
250 assert_eq!(p.num_blocks, 1);
251 assert_eq!(p.larger_block_len, 10);
252 assert_eq!(p.smaller_block_len, 10);
253 assert_eq!(p.larger_blocks, 0);
254 assert_eq!(p.block_len(0), Some(10));
255 assert_eq!(p.block_len(1), None);
256 }
257
258 // A single-symbol object smaller than E: T=1 regardless of how small L is.
259 #[test]
260 fn sub_symbol_object_rounds_up_to_one_symbol() {
261 let p = SourceBlockPartition::new(5, 1000, 10).unwrap();
262 assert_eq!(p.source_symbols, 1);
263 assert_eq!(p.num_blocks, 1);
264 // The one and only symbol IS the last symbol: full L, not full E.
265 assert_eq!(p.last_symbol_len(), Some(5));
266 }
267
268 #[test]
269 fn mutating_transfer_length_changes_partition() {
270 let a = SourceBlockPartition::new(10_000, 1000, 3).unwrap();
271 let b = SourceBlockPartition::new(10_005, 1000, 3).unwrap();
272 assert_ne!(a.source_symbols, b.source_symbols);
273 assert_ne!(a.larger_blocks, b.larger_blocks);
274 assert_ne!(a.last_symbol_len(), b.last_symbol_len());
275 }
276}