miden_serde_utils/
lib.rs

1// Copyright (c) Facebook, Inc. and its affiliates.
2//
3// This source code is licensed under the MIT license found in the
4// LICENSE file in the root directory of this source tree.
5
6#![cfg_attr(not(feature = "std"), no_std)]
7
8extern crate alloc;
9
10use alloc::{
11    collections::{BTreeMap, BTreeSet},
12    format,
13    string::String,
14    vec::Vec,
15};
16
17// ERROR
18// ================================================================================================
19
20/// Defines errors which can occur during deserialization.
21#[derive(Clone, Debug, PartialEq, Eq)]
22pub enum DeserializationError {
23    /// Indicates that the deserialization failed because of insufficient data.
24    UnexpectedEOF,
25    /// Indicates that the deserialization failed because the value was not valid.
26    InvalidValue(String),
27    /// Indicates that deserialization failed for an unknown reason.
28    UnknownError(String),
29}
30
31#[cfg(feature = "std")]
32impl std::error::Error for DeserializationError {}
33
34impl core::fmt::Display for DeserializationError {
35    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
36        match self {
37            Self::UnexpectedEOF => write!(f, "unexpected end of file"),
38            Self::InvalidValue(msg) => write!(f, "invalid value: {}", msg),
39            Self::UnknownError(msg) => write!(f, "unknown error: {}", msg),
40        }
41    }
42}
43
44mod byte_reader;
45#[cfg(feature = "std")]
46pub use byte_reader::ReadAdapter;
47pub use byte_reader::{BudgetedReader, ByteReader, ReadManyIter, SliceReader};
48
49mod byte_writer;
50pub use byte_writer::ByteWriter;
51
52// SERIALIZABLE TRAIT
53// ================================================================================================
54
55/// Defines how to serialize `Self` into bytes.
56pub trait Serializable {
57    // REQUIRED METHODS
58    // --------------------------------------------------------------------------------------------
59    /// Serializes `self` into bytes and writes these bytes into the `target`.
60    fn write_into<W: ByteWriter>(&self, target: &mut W);
61
62    // PROVIDED METHODS
63    // --------------------------------------------------------------------------------------------
64
65    /// Serializes `self` into a vector of bytes.
66    fn to_bytes(&self) -> Vec<u8> {
67        let mut result = Vec::with_capacity(self.get_size_hint());
68        self.write_into(&mut result);
69        result
70    }
71
72    /// Returns an estimate of how many bytes are needed to represent self.
73    ///
74    /// The default implementation returns zero.
75    fn get_size_hint(&self) -> usize {
76        0
77    }
78}
79
80impl<T: Serializable> Serializable for &T {
81    fn write_into<W: ByteWriter>(&self, target: &mut W) {
82        (*self).write_into(target)
83    }
84
85    fn get_size_hint(&self) -> usize {
86        (*self).get_size_hint()
87    }
88}
89
90impl Serializable for () {
91    fn write_into<W: ByteWriter>(&self, _target: &mut W) {}
92
93    fn get_size_hint(&self) -> usize {
94        0
95    }
96}
97
98impl<T1> Serializable for (T1,)
99where
100    T1: Serializable,
101{
102    fn write_into<W: ByteWriter>(&self, target: &mut W) {
103        self.0.write_into(target);
104    }
105
106    fn get_size_hint(&self) -> usize {
107        self.0.get_size_hint()
108    }
109}
110
111impl<T1, T2> Serializable for (T1, T2)
112where
113    T1: Serializable,
114    T2: Serializable,
115{
116    fn write_into<W: ByteWriter>(&self, target: &mut W) {
117        self.0.write_into(target);
118        self.1.write_into(target);
119    }
120
121    fn get_size_hint(&self) -> usize {
122        self.0.get_size_hint() + self.1.get_size_hint()
123    }
124}
125
126impl<T1, T2, T3> Serializable for (T1, T2, T3)
127where
128    T1: Serializable,
129    T2: Serializable,
130    T3: Serializable,
131{
132    fn write_into<W: ByteWriter>(&self, target: &mut W) {
133        self.0.write_into(target);
134        self.1.write_into(target);
135        self.2.write_into(target);
136    }
137
138    fn get_size_hint(&self) -> usize {
139        self.0.get_size_hint() + self.1.get_size_hint() + self.2.get_size_hint()
140    }
141}
142
143impl<T1, T2, T3, T4> Serializable for (T1, T2, T3, T4)
144where
145    T1: Serializable,
146    T2: Serializable,
147    T3: Serializable,
148    T4: Serializable,
149{
150    fn write_into<W: ByteWriter>(&self, target: &mut W) {
151        self.0.write_into(target);
152        self.1.write_into(target);
153        self.2.write_into(target);
154        self.3.write_into(target);
155    }
156
157    fn get_size_hint(&self) -> usize {
158        self.0.get_size_hint()
159            + self.1.get_size_hint()
160            + self.2.get_size_hint()
161            + self.3.get_size_hint()
162    }
163}
164
165impl<T1, T2, T3, T4, T5> Serializable for (T1, T2, T3, T4, T5)
166where
167    T1: Serializable,
168    T2: Serializable,
169    T3: Serializable,
170    T4: Serializable,
171    T5: Serializable,
172{
173    fn write_into<W: ByteWriter>(&self, target: &mut W) {
174        self.0.write_into(target);
175        self.1.write_into(target);
176        self.2.write_into(target);
177        self.3.write_into(target);
178        self.4.write_into(target);
179    }
180
181    fn get_size_hint(&self) -> usize {
182        self.0.get_size_hint()
183            + self.1.get_size_hint()
184            + self.2.get_size_hint()
185            + self.3.get_size_hint()
186            + self.4.get_size_hint()
187    }
188}
189
190impl<T1, T2, T3, T4, T5, T6> Serializable for (T1, T2, T3, T4, T5, T6)
191where
192    T1: Serializable,
193    T2: Serializable,
194    T3: Serializable,
195    T4: Serializable,
196    T5: Serializable,
197    T6: Serializable,
198{
199    fn write_into<W: ByteWriter>(&self, target: &mut W) {
200        self.0.write_into(target);
201        self.1.write_into(target);
202        self.2.write_into(target);
203        self.3.write_into(target);
204        self.4.write_into(target);
205        self.5.write_into(target);
206    }
207
208    fn get_size_hint(&self) -> usize {
209        self.0.get_size_hint()
210            + self.1.get_size_hint()
211            + self.2.get_size_hint()
212            + self.3.get_size_hint()
213            + self.4.get_size_hint()
214            + self.5.get_size_hint()
215    }
216}
217
218impl Serializable for u8 {
219    fn write_into<W: ByteWriter>(&self, target: &mut W) {
220        target.write_u8(*self);
221    }
222
223    fn get_size_hint(&self) -> usize {
224        core::mem::size_of::<u8>()
225    }
226}
227
228impl Serializable for u16 {
229    fn write_into<W: ByteWriter>(&self, target: &mut W) {
230        target.write_u16(*self);
231    }
232
233    fn get_size_hint(&self) -> usize {
234        core::mem::size_of::<u16>()
235    }
236}
237
238impl Serializable for u32 {
239    fn write_into<W: ByteWriter>(&self, target: &mut W) {
240        target.write_u32(*self);
241    }
242
243    fn get_size_hint(&self) -> usize {
244        core::mem::size_of::<u32>()
245    }
246}
247
248impl Serializable for u64 {
249    fn write_into<W: ByteWriter>(&self, target: &mut W) {
250        target.write_u64(*self);
251    }
252
253    fn get_size_hint(&self) -> usize {
254        core::mem::size_of::<u64>()
255    }
256}
257
258impl Serializable for u128 {
259    fn write_into<W: ByteWriter>(&self, target: &mut W) {
260        target.write_u128(*self);
261    }
262
263    fn get_size_hint(&self) -> usize {
264        core::mem::size_of::<u128>()
265    }
266}
267
268impl Serializable for usize {
269    fn write_into<W: ByteWriter>(&self, target: &mut W) {
270        target.write_usize(*self)
271    }
272
273    fn get_size_hint(&self) -> usize {
274        byte_writer::usize_encoded_len(*self as u64)
275    }
276}
277
278impl<T: Serializable> Serializable for Option<T> {
279    fn write_into<W: ByteWriter>(&self, target: &mut W) {
280        match self {
281            Some(v) => {
282                target.write_bool(true);
283                v.write_into(target);
284            },
285            None => target.write_bool(false),
286        }
287    }
288
289    fn get_size_hint(&self) -> usize {
290        core::mem::size_of::<bool>() + self.as_ref().map(|value| value.get_size_hint()).unwrap_or(0)
291    }
292}
293
294impl<T: Serializable, const C: usize> Serializable for [T; C] {
295    fn write_into<W: ByteWriter>(&self, target: &mut W) {
296        target.write_many(self)
297    }
298
299    fn get_size_hint(&self) -> usize {
300        let mut size = 0;
301        for item in self {
302            size += item.get_size_hint();
303        }
304        size
305    }
306}
307
308impl<T: Serializable> Serializable for [T] {
309    fn write_into<W: ByteWriter>(&self, target: &mut W) {
310        target.write_usize(self.len());
311        for element in self.iter() {
312            element.write_into(target);
313        }
314    }
315
316    fn get_size_hint(&self) -> usize {
317        let mut size = self.len().get_size_hint();
318        for element in self {
319            size += element.get_size_hint();
320        }
321        size
322    }
323}
324
325impl<T: Serializable> Serializable for Vec<T> {
326    fn write_into<W: ByteWriter>(&self, target: &mut W) {
327        target.write_usize(self.len());
328        target.write_many(self);
329    }
330
331    fn get_size_hint(&self) -> usize {
332        let mut size = self.len().get_size_hint();
333        for item in self {
334            size += item.get_size_hint();
335        }
336        size
337    }
338}
339
340impl<K: Serializable, V: Serializable> Serializable for BTreeMap<K, V> {
341    fn write_into<W: ByteWriter>(&self, target: &mut W) {
342        target.write_usize(self.len());
343        target.write_many(self);
344    }
345
346    fn get_size_hint(&self) -> usize {
347        let mut size = self.len().get_size_hint();
348        for item in self {
349            size += item.get_size_hint();
350        }
351        size
352    }
353}
354
355impl<T: Serializable> Serializable for BTreeSet<T> {
356    fn write_into<W: ByteWriter>(&self, target: &mut W) {
357        target.write_usize(self.len());
358        target.write_many(self);
359    }
360
361    fn get_size_hint(&self) -> usize {
362        let mut size = self.len().get_size_hint();
363        for item in self {
364            size += item.get_size_hint();
365        }
366        size
367    }
368}
369
370impl Serializable for str {
371    fn write_into<W: ByteWriter>(&self, target: &mut W) {
372        target.write_usize(self.len());
373        target.write_many(self.as_bytes());
374    }
375
376    fn get_size_hint(&self) -> usize {
377        self.len().get_size_hint() + self.len()
378    }
379}
380
381impl Serializable for String {
382    fn write_into<W: ByteWriter>(&self, target: &mut W) {
383        target.write_usize(self.len());
384        target.write_many(self.as_bytes());
385    }
386
387    fn get_size_hint(&self) -> usize {
388        self.len().get_size_hint() + self.len()
389    }
390}
391
392// DESERIALIZABLE
393// ================================================================================================
394
395/// Defines how to deserialize `Self` from bytes.
396pub trait Deserializable: Sized {
397    // REQUIRED METHODS
398    // --------------------------------------------------------------------------------------------
399
400    /// Reads a sequence of bytes from the provided `source`, attempts to deserialize these bytes
401    /// into `Self`, and returns the result.
402    ///
403    /// # Errors
404    /// Returns an error if:
405    /// * The `source` does not contain enough bytes to deserialize `Self`.
406    /// * Bytes read from the `source` do not represent a valid value for `Self`.
407    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError>;
408
409    /// Returns the minimum serialized size for one instance of this type.
410    ///
411    /// This is used by [`ByteReader::max_alloc`] to estimate how many elements can be
412    /// deserialized from the remaining budget, preventing denial-of-service attacks from
413    /// malicious length prefixes.
414    ///
415    /// The default implementation returns `size_of::<Self>()`, which is conservative: it may
416    /// reject valid input for types where the serialized size is smaller than the in-memory
417    /// size (e.g., structs with computed/cached fields that aren't serialized).
418    ///
419    /// Override this method for types where the serialized representation is smaller than
420    /// the in-memory representation to allow more elements to be deserialized.
421    fn min_serialized_size() -> usize {
422        core::mem::size_of::<Self>()
423    }
424
425    // PROVIDED METHODS
426    // --------------------------------------------------------------------------------------------
427
428    /// Attempts to deserialize the provided `bytes` into `Self` and returns the result.
429    ///
430    /// # Errors
431    /// Returns an error if:
432    /// * The `bytes` do not contain enough information to deserialize `Self`.
433    /// * The `bytes` do not represent a valid value for `Self`.
434    ///
435    /// Note: if `bytes` contains more data than needed to deserialize `self`, no error is
436    /// returned.
437    fn read_from_bytes(bytes: &[u8]) -> Result<Self, DeserializationError> {
438        Self::read_from(&mut SliceReader::new(bytes))
439    }
440
441    /// Deserializes `Self` from bytes with a byte budget limit.
442    ///
443    /// This is the recommended method for deserializing untrusted input. The budget limits
444    /// how many bytes can be consumed during deserialization, preventing denial-of-service
445    /// attacks that exploit length fields to cause huge allocations.
446    ///
447    /// # Errors
448    /// Returns an error if:
449    /// * The budget is exhausted before deserialization completes.
450    /// * The `bytes` do not contain enough information to deserialize `Self`.
451    /// * The `bytes` do not represent a valid value for `Self`.
452    fn read_from_bytes_with_budget(
453        bytes: &[u8],
454        budget: usize,
455    ) -> Result<Self, DeserializationError> {
456        Self::read_from(&mut BudgetedReader::new(SliceReader::new(bytes), budget))
457    }
458}
459
460impl Deserializable for () {
461    fn read_from<R: ByteReader>(_source: &mut R) -> Result<Self, DeserializationError> {
462        Ok(())
463    }
464}
465
466impl<T1> Deserializable for (T1,)
467where
468    T1: Deserializable,
469{
470    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
471        let v1 = T1::read_from(source)?;
472        Ok((v1,))
473    }
474}
475
476impl<T1, T2> Deserializable for (T1, T2)
477where
478    T1: Deserializable,
479    T2: Deserializable,
480{
481    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
482        let v1 = T1::read_from(source)?;
483        let v2 = T2::read_from(source)?;
484        Ok((v1, v2))
485    }
486
487    fn min_serialized_size() -> usize {
488        T1::min_serialized_size().saturating_add(T2::min_serialized_size())
489    }
490}
491
492impl<T1, T2, T3> Deserializable for (T1, T2, T3)
493where
494    T1: Deserializable,
495    T2: Deserializable,
496    T3: Deserializable,
497{
498    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
499        let v1 = T1::read_from(source)?;
500        let v2 = T2::read_from(source)?;
501        let v3 = T3::read_from(source)?;
502        Ok((v1, v2, v3))
503    }
504
505    fn min_serialized_size() -> usize {
506        T1::min_serialized_size()
507            .saturating_add(T2::min_serialized_size())
508            .saturating_add(T3::min_serialized_size())
509    }
510}
511
512impl<T1, T2, T3, T4> Deserializable for (T1, T2, T3, T4)
513where
514    T1: Deserializable,
515    T2: Deserializable,
516    T3: Deserializable,
517    T4: Deserializable,
518{
519    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
520        let v1 = T1::read_from(source)?;
521        let v2 = T2::read_from(source)?;
522        let v3 = T3::read_from(source)?;
523        let v4 = T4::read_from(source)?;
524        Ok((v1, v2, v3, v4))
525    }
526
527    fn min_serialized_size() -> usize {
528        T1::min_serialized_size()
529            .saturating_add(T2::min_serialized_size())
530            .saturating_add(T3::min_serialized_size())
531            .saturating_add(T4::min_serialized_size())
532    }
533}
534
535impl<T1, T2, T3, T4, T5> Deserializable for (T1, T2, T3, T4, T5)
536where
537    T1: Deserializable,
538    T2: Deserializable,
539    T3: Deserializable,
540    T4: Deserializable,
541    T5: Deserializable,
542{
543    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
544        let v1 = T1::read_from(source)?;
545        let v2 = T2::read_from(source)?;
546        let v3 = T3::read_from(source)?;
547        let v4 = T4::read_from(source)?;
548        let v5 = T5::read_from(source)?;
549        Ok((v1, v2, v3, v4, v5))
550    }
551
552    fn min_serialized_size() -> usize {
553        T1::min_serialized_size()
554            .saturating_add(T2::min_serialized_size())
555            .saturating_add(T3::min_serialized_size())
556            .saturating_add(T4::min_serialized_size())
557            .saturating_add(T5::min_serialized_size())
558    }
559}
560
561impl<T1, T2, T3, T4, T5, T6> Deserializable for (T1, T2, T3, T4, T5, T6)
562where
563    T1: Deserializable,
564    T2: Deserializable,
565    T3: Deserializable,
566    T4: Deserializable,
567    T5: Deserializable,
568    T6: Deserializable,
569{
570    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
571        let v1 = T1::read_from(source)?;
572        let v2 = T2::read_from(source)?;
573        let v3 = T3::read_from(source)?;
574        let v4 = T4::read_from(source)?;
575        let v5 = T5::read_from(source)?;
576        let v6 = T6::read_from(source)?;
577        Ok((v1, v2, v3, v4, v5, v6))
578    }
579
580    fn min_serialized_size() -> usize {
581        T1::min_serialized_size()
582            .saturating_add(T2::min_serialized_size())
583            .saturating_add(T3::min_serialized_size())
584            .saturating_add(T4::min_serialized_size())
585            .saturating_add(T5::min_serialized_size())
586            .saturating_add(T6::min_serialized_size())
587    }
588}
589
590impl Deserializable for u8 {
591    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
592        source.read_u8()
593    }
594}
595
596impl Deserializable for u16 {
597    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
598        source.read_u16()
599    }
600}
601
602impl Deserializable for u32 {
603    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
604        source.read_u32()
605    }
606}
607
608impl Deserializable for u64 {
609    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
610        source.read_u64()
611    }
612}
613
614impl Deserializable for u128 {
615    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
616        source.read_u128()
617    }
618}
619
620impl Deserializable for usize {
621    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
622        source.read_usize()
623    }
624
625    fn min_serialized_size() -> usize {
626        1 // vint64 encoding: minimum 1 byte for values 0-127
627    }
628}
629
630impl<T: Deserializable> Deserializable for Option<T> {
631    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
632        if source.read_bool()? {
633            Ok(Some(T::read_from(source)?))
634        } else {
635            Ok(None)
636        }
637    }
638
639    /// Returns 1 (just the bool discriminator).
640    ///
641    /// The `Some` variant would be `1 + T::min_serialized_size()`, but we use the minimum
642    /// to allow more elements through the early check.
643    fn min_serialized_size() -> usize {
644        1
645    }
646}
647
648impl<T: Deserializable, const C: usize> Deserializable for [T; C] {
649    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
650        let data: Vec<T> = source.read_many_iter(C)?.collect::<Result<_, _>>()?;
651
652        // The iterator yields exactly C elements (or fails early), so this always succeeds
653        Ok(data.try_into().unwrap_or_else(|v: Vec<T>| {
654            panic!("Expected a Vec of length {} but it was {}", C, v.len())
655        }))
656    }
657
658    fn min_serialized_size() -> usize {
659        C.saturating_mul(T::min_serialized_size())
660    }
661}
662
663impl<T: Deserializable> Deserializable for Vec<T> {
664    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
665        let len = source.read_usize()?;
666        source.read_many_iter(len)?.collect()
667    }
668
669    /// Returns 1 (the minimum vint length prefix size).
670    ///
671    /// The actual serialized size depends on the number of elements, which we don't know
672    /// at the point this is called. Using the minimum allows more elements through the
673    /// early check; budget enforcement during actual reads provides the real protection.
674    fn min_serialized_size() -> usize {
675        1
676    }
677}
678
679impl<K: Deserializable + Ord, V: Deserializable> Deserializable for BTreeMap<K, V> {
680    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
681        let len = source.read_usize()?;
682        source.read_many_iter(len)?.collect()
683    }
684
685    fn min_serialized_size() -> usize {
686        1 // minimum vint length prefix
687    }
688}
689
690impl<T: Deserializable + Ord> Deserializable for BTreeSet<T> {
691    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
692        let len = source.read_usize()?;
693        source.read_many_iter(len)?.collect()
694    }
695
696    fn min_serialized_size() -> usize {
697        1 // minimum vint length prefix
698    }
699}
700
701impl Deserializable for String {
702    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
703        let len = source.read_usize()?;
704        let data: Vec<u8> = source.read_many_iter(len)?.collect::<Result<_, _>>()?;
705
706        String::from_utf8(data).map_err(|err| DeserializationError::InvalidValue(format!("{err}")))
707    }
708
709    fn min_serialized_size() -> usize {
710        1 // minimum vint length prefix
711    }
712}
713
714// GOLDILOCKS FIELD ELEMENT IMPLEMENTATIONS
715// ================================================================================================
716
717impl Serializable for p3_goldilocks::Goldilocks {
718    fn write_into<W: ByteWriter>(&self, target: &mut W) {
719        use p3_field::PrimeField64;
720        target.write_u64(self.as_canonical_u64());
721    }
722
723    fn get_size_hint(&self) -> usize {
724        core::mem::size_of::<u64>()
725    }
726}
727
728impl Deserializable for p3_goldilocks::Goldilocks {
729    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
730        use p3_field::integers::QuotientMap;
731
732        let value = source.read_u64()?;
733        Self::from_canonical_checked(value).ok_or_else(|| {
734            DeserializationError::InvalidValue(format!(
735                "value {} is not a valid Goldilocks field element",
736                value
737            ))
738        })
739    }
740}
miden_serde_utils/lib.rs

miden_serde_utils/
lib.rs
