foundation_ur/fountain/
part.rs

1// SPDX-FileCopyrightText: © 2023 Foundation Devices, Inc. <hello@foundationdevices.com>
2// SPDX-FileCopyrightText: © 2020 Dominik Spicher <dominikspicher@gmail.com>
3// SPDX-License-Identifier: MIT
4
5//! Parts.
6
7use core::{fmt, ops::DerefMut};
8
9use crate::{
10    bytewords,
11    collections::Set,
12    fountain::{chooser, chooser::BaseFragmentChooser, util::xor_into},
13};
14
15/// Description of how a message is split into parts.
16///
17/// This structure is a subset of the information of a [`Part`].
18#[derive(Debug, Clone, PartialEq, Eq, Hash)]
19pub struct MessageDescription {
20    /// The total sequence count.
21    pub sequence_count: u32,
22    /// The total message length, in bytes, excluding the padding bytes size.
23    pub message_length: usize,
24    /// The CRC32 checksum of the entire message.
25    pub checksum: u32,
26    /// The length of a single fragment.
27    pub fragment_length: usize,
28}
29
30/// A part emitted by a fountain [encoder](crate::fountain::BaseEncoder).
31///
32/// Most commonly, this is obtained by calling [`next_part`] on the encoder.
33///
34/// [`next_part`]: crate::fountain::BaseEncoder::next_part
35#[derive(Clone, Debug, PartialEq, Eq)]
36#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
37pub struct Part<'a> {
38    /// The sequence number of this part. Can be higher than
39    /// [`sequence_count`](Self::sequence_count).
40    pub sequence: u32,
41    /// The total sequence count of the entire message.
42    pub sequence_count: u32,
43    /// The total message length, in bytes, excluding the padding bytes size.
44    pub message_length: usize,
45    /// The CRC32 checksum of the entire message.
46    pub checksum: u32,
47    /// The data of this part.
48    ///
49    /// If [`sequence`](Self::sequence), is higher than
50    /// [`sequence_count`](Self::sequence_count) it's very likely that the data
51    /// data contained is mixed, however there may be some cases where the
52    /// former is true and this is a "simple part".
53    pub data: &'a [u8],
54}
55
56impl<'a> Part<'a> {
57    /// Returns `true` if this part is valid.
58    ///
59    /// Verifies that:
60    ///
61    /// - `sequence`, `sequence_count` are positive values.
62    /// - `message_length` is a positive value and is .
63    /// - `data` contains data and is smaller or equal to `message_length`.
64    pub fn is_valid(&self) -> bool {
65        self.sequence > 0
66            && self.sequence_count > 0
67            && self.message_length > 0
68            && !self.data.is_empty()
69            && self.data.len() <= self.message_length
70    }
71
72    /// Calculate the indexes contained on this [`Part`].
73    ///
74    /// **Note:** this is a costly operating that can take a lot of memory in
75    /// the stack or the heap depending on the
76    /// [fragment chooser types](chooser::Types) used.
77    pub fn indexes<C, I>(&self) -> I
78    where
79        C: chooser::Types,
80        I: Set<usize>,
81    {
82        BaseFragmentChooser::<C>::default().choose_fragments(
83            self.sequence,
84            self.sequence_count,
85            self.checksum,
86        )
87    }
88
89    /// Returns the maximum length that an encoded `Part` can have excluding
90    /// the `data` contents.
91    pub const fn max_encoded_len() -> usize {
92        #[rustfmt::skip]
93        const MAX_CBOR: &[u8] = &[
94            0x85,                                                     // array(5)
95                0x1A, 0xFF, 0xFF, 0xFF, 0xFF,                         // unsigned(0xFFFFFFF)
96                0x1B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // unsigned(0xFFFFFFFFFFFFFFFF)
97                0x1B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // unsigned(0xFFFFFFFFFFFFFFFF)
98                0x1A, 0xFF, 0xFF, 0xFF, 0xFF,                         // unsigned(0xFFFFFFF)
99                0x5B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, // bytes(0xFFFFFFFFFFFFFFFF)
100        ];
101
102        MAX_CBOR.len()
103    }
104
105    /// Convert this [`Part`] to a [`MessageDescription`].
106    pub fn to_message_description(&self) -> MessageDescription {
107        MessageDescription {
108            sequence_count: self.sequence_count,
109            message_length: self.message_length,
110            checksum: self.checksum,
111            fragment_length: self.data.len(),
112        }
113    }
114}
115
116/// Display this [`Part`] as encoded bytewords.
117impl<'a> fmt::Display for Part<'a> {
118    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
119        // Use custom minicbor writer that writes directly to `Formatter` instead of
120        // using an intermediate buffer, so CBOR is directly encoded as bytewords.
121        let mut encoder = minicbor::Encoder::new(bytewords::minicbor::Writer::new(f));
122        encoder.encode(self).map_err(|_| fmt::Error)?;
123
124        // Call finish to write CRC32 at the end.
125        encoder.into_writer().finish()?;
126
127        Ok(())
128    }
129}
130
131impl<'a> PartialEq<MessageDescription> for Part<'a> {
132    fn eq(&self, other: &MessageDescription) -> bool {
133        self.sequence_count == other.sequence_count
134            && self.message_length == other.message_length
135            && self.checksum == other.checksum
136            && self.data.len() == other.fragment_length
137    }
138}
139
140/// Encodes [`Part`] to it's CBOR representation.
141impl<'a, C> minicbor::Encode<C> for Part<'a> {
142    fn encode<W: minicbor::encode::Write>(
143        &self,
144        e: &mut minicbor::Encoder<W>,
145        _ctx: &mut C,
146    ) -> Result<(), minicbor::encode::Error<W::Error>> {
147        e.array(5)?
148            .u32(self.sequence)?
149            .u64(u64::from(self.sequence_count))?
150            .u64(
151                self.message_length
152                    .try_into()
153                    .map_err(|_| minicbor::encode::Error::message("expected u64"))?,
154            )?
155            .u32(self.checksum)?
156            .bytes(self.data)?;
157
158        Ok(())
159    }
160}
161
162/// Decodes [`Part`] from it's CBOR representation.
163impl<'b, C> minicbor::Decode<'b, C> for Part<'b> {
164    fn decode(
165        d: &mut minicbor::Decoder<'b>,
166        _ctx: &mut C,
167    ) -> Result<Self, minicbor::decode::Error> {
168        if !matches!(d.array()?, Some(5)) {
169            return Err(minicbor::decode::Error::message(
170                "invalid CBOR array length",
171            ));
172        }
173
174        Ok(Self {
175            sequence: d.u32()?,
176            sequence_count: d.u32()?,
177            message_length: d
178                .u32()?
179                .try_into()
180                .map_err(|_| minicbor::decode::Error::message("expected usize"))?,
181            checksum: d.u32()?,
182            data: d.bytes()?,
183        })
184    }
185}
186
187/// A part with the indexes of the simple parts mixed.
188#[derive(Debug, Clone)]
189pub struct IndexedPart<D, I> {
190    /// The data of this part.
191    pub data: D,
192    /// The indexes contained in this part.
193    pub indexes: I,
194}
195
196impl<D, I> IndexedPart<D, I> {
197    /// Create a new [`IndexedPart`] from `data` and the indexes of the parts
198    /// mixed in `data`.
199    pub fn new(data: D, indexes: I) -> Self {
200        Self { data, indexes }
201    }
202
203    /// Returns `true` if the part is simple.
204    ///
205    /// A part is simple if it only contains a single mixed, e.g: the data is
206    /// already decoded (or unmixed).
207    #[inline]
208    pub fn is_simple(&self) -> bool
209    where
210        I: Set<usize>,
211    {
212        self.indexes.len() == 1
213    }
214
215    /// Reduce this part by another part.
216    ///
217    /// # Panics
218    ///
219    /// This function panics if this part is already simple.
220    pub fn reduce(&mut self, part: &IndexedPart<D, I>)
221    where
222        D: DerefMut<Target = [u8]>,
223        I: Set<usize>,
224    {
225        if self.indexes.len() == 1 {
226            return;
227        }
228
229        if part.indexes.is_subset(&self.indexes) {
230            self.indexes = self.indexes.sub(&part.indexes);
231            xor_into(&mut self.data, &part.data);
232        }
233    }
234
235    /// Reduce this part by a simple part.
236    ///
237    /// # Panics
238    ///
239    /// This function panics if this part is already simple.
240    pub fn reduce_by_simple(&mut self, data: &[u8], index: usize)
241    where
242        D: DerefMut<Target = [u8]>,
243        I: Set<usize>,
244    {
245        assert!(self.indexes.len() > 1, "cannot reduce a simple part");
246
247        if self.indexes.contains(&index) {
248            self.indexes.remove(&index);
249            xor_into(&mut self.data, data);
250        }
251    }
252}
253
254#[cfg(test)]
255pub mod tests {
256    use super::*;
257
258    #[test]
259    #[cfg(feature = "alloc")]
260    fn test_part_cbor_roundtrip() {
261        const PART: Part = Part {
262            sequence: 12,
263            sequence_count: 8,
264            message_length: 100,
265            checksum: 0x1234_5678,
266            data: &[1, 5, 3, 3, 5],
267        };
268
269        let mut cbor = alloc::vec::Vec::new();
270        minicbor::encode(&PART, &mut cbor).unwrap();
271
272        let part2: Part = minicbor::decode(&cbor).unwrap();
273        assert_eq!(part2, PART);
274
275        let mut cbor2 = alloc::vec::Vec::new();
276        minicbor::encode(&part2, &mut cbor2).unwrap();
277        assert_eq!(cbor, cbor2);
278    }
279
280    #[test]
281    fn test_part_cbor_decode() {
282        // 0x18 is the first byte value that doesn't directly encode a u8,
283        // but implies a following value
284        assert!(minicbor::decode::<'_, Part>(&[0x18]).is_err());
285        // the top-level item must be an array
286        assert!(minicbor::decode::<'_, Part>(&[0x1]).is_err());
287        // the array must be of length five
288        assert!(minicbor::decode::<'_, Part>(&[0x84, 0x1, 0x2, 0x3, 0x4]).is_err());
289        assert!(minicbor::decode::<'_, Part>(&[0x86, 0x1, 0x2, 0x3, 0x4, 0x5, 0x6]).is_err());
290        // the first item must be an unsigned integer
291        assert!(
292            minicbor::decode::<'_, Part>(&[0x85, 0x41, 0x1, 0x2, 0x3, 0x4, 0x41, 0x1]).is_err()
293        );
294        // the second item must be an unsigned integer
295        assert!(
296            minicbor::decode::<'_, Part>(&[0x85, 0x1, 0x41, 0x2, 0x3, 0x4, 0x41, 0x1]).is_err()
297        );
298        // the third item must be an unsigned integer
299        assert!(
300            minicbor::decode::<'_, Part>(&[0x85, 0x1, 0x2, 0x41, 0x3, 0x4, 0x41, 0x1]).is_err()
301        );
302        // the fourth item must be an unsigned integer
303        assert!(
304            minicbor::decode::<'_, Part>(&[0x85, 0x1, 0x2, 0x3, 0x41, 0x4, 0x41, 0x1]).is_err()
305        );
306        // the fifth item must be byte string
307        assert!(minicbor::decode::<'_, Part>(&[0x85, 0x1, 0x2, 0x3, 0x4, 0x5]).is_err());
308        assert!(minicbor::decode::<'_, Part>(&[0x85, 0x1, 0x2, 0x3, 0x4, 0x5]).is_err());
309        minicbor::decode::<'_, Part>(&[0x85, 0x1, 0x2, 0x3, 0x4, 0x41, 0x5]).unwrap();
310    }
311
312    #[test]
313    fn test_part_cbor_decode_unsigned_types() {
314        // u8
315        minicbor::decode::<'_, Part>(&[0x85, 0x1, 0x2, 0x3, 0x4, 0x41, 0x5]).unwrap();
316        // u16
317        minicbor::decode::<'_, Part>(&[
318            0x85, 0x19, 0x1, 0x2, 0x19, 0x3, 0x4, 0x19, 0x5, 0x6, 0x19, 0x7, 0x8, 0x41, 0x5,
319        ])
320        .unwrap();
321        // u32
322        minicbor::decode::<'_, Part>(&[
323            0x85, 0x1a, 0x1, 0x2, 0x3, 0x4, 0x1a, 0x5, 0x6, 0x7, 0x8, 0x1a, 0x9, 0x10, 0x11, 0x12,
324            0x1a, 0x13, 0x14, 0x15, 0x16, 0x41, 0x5,
325        ])
326        .unwrap();
327        // u64
328        assert!(minicbor::decode::<'_, Part>(&[
329            0x85, 0x1b, 0x1, 0x2, 0x3, 0x4, 0xa, 0xb, 0xc, 0xd, 0x1a, 0x5, 0x6, 0x7, 0x8, 0x1a,
330            0x9, 0x10, 0x11, 0x12, 0x1a, 0x13, 0x14, 0x15, 0x16, 0x41, 0x5,
331        ])
332        .is_err());
333        assert!(minicbor::decode::<'_, Part>(&[
334            0x85, 0x1a, 0x1, 0x2, 0x3, 0x4, 0x1b, 0x5, 0x6, 0x7, 0x8, 0xa, 0xb, 0xc, 0xd, 0x1a,
335            0x9, 0x10, 0x11, 0x12, 0x1a, 0x13, 0x14, 0x15, 0x16, 0x41, 0x5,
336        ])
337        .is_err());
338        assert!(minicbor::decode::<'_, Part>(&[
339            0x85, 0x1a, 0x1, 0x2, 0x3, 0x4, 0x1a, 0x5, 0x6, 0x7, 0x8, 0x1b, 0x9, 0x10, 0x11, 0x12,
340            0xa, 0xb, 0xc, 0xd, 0x1a, 0x13, 0x14, 0x15, 0x16, 0x41, 0x5,
341        ])
342        .is_err());
343        assert!(minicbor::decode::<'_, Part>(&[
344            0x85, 0x1a, 0x1, 0x2, 0x3, 0x4, 0x1a, 0x5, 0x6, 0x7, 0x8, 0x1a, 0x9, 0x10, 0x11, 0x12,
345            0x1b, 0x13, 0x14, 0x15, 0x16, 0xa, 0xb, 0xc, 0xd, 0x41, 0x5,
346        ])
347        .is_err());
348    }
349}
foundation_ur/fountain/part.rs

foundation_ur/fountain/
part.rs
