ic_stable_memory/encoding/
fixed_size.rs

1//! Sized data encoding algorithms that power this crate.
2//!
3//! The main idea is to make sized data encoding as fast as possible, taking as little space as possible.
4//! Each type implementing [AsFixedSizeBytes] trait is aware of its encoded size and of data type of
5//! the byte buffer that is used to encode it. Constant generics enable us to encode such fixed size
6//! types in `[u8; N]`, which is very good, since arrays are stack-based data structures and don't
7//! involve expensive heap allocations, so most types encode themselves into such generic arrays.
8//!
9//! Generic types (such as [Option]) are not yet compatible with constant generics and therefore they
10//! are encoded to [Vec] of [u8].
11//!
12//! [AsFixedSizeBytes] trait encapusaltes these differences providing a simple API.
13
14use candid::{Int, Nat, Principal};
15use num_bigint::{BigInt, BigUint, Sign};
16
17/// Allows fast and space-efficient fixed size data encoding.
18///
19/// This trait can be implemented by using [derive::AsFixedSizeBytes] macro.
20/// By default it is implemented for the following types:
21/// 1. All primitive types: [i8], [u8], [i16], [u16], [i32], [u32], [i64], [u64], [i128], [u128], [f32], [f64], [bool], [()]
22/// 2. Primitive type generic arrays: [i8; N], [u8; N], [i16; N], [u16; N], [i32; N], [u32; N], [i64: N], [u64; N], [i128; N], [u128; N], [f32; N], [f64; N], [bool; N], [(); N]
23/// 3. Tuples up to 6 elements, where each element implements [AsFixedSizeBytes]
24/// 4. [Option] of `T`, where `T`: [AsFixedSizeBytes]
25/// 5. IC native types: [candid::Principal], [candid::Nat], [candid::Int]
26pub trait AsFixedSizeBytes {
27    /// Size of self when encoded
28    const SIZE: usize;
29
30    /// [Buffer] that is used to encode this value into
31    type Buf: Buffer;
32
33    /// Encodes itself into a slice of bytes.
34    ///
35    /// # Panics
36    /// Will panic if out of bounds.
37    fn as_fixed_size_bytes(&self, buf: &mut [u8]);
38
39    /// Decodes itself from a slice of bytes.
40    ///
41    /// # Panics
42    /// Will panic if out of bounds.
43    fn from_fixed_size_bytes(buf: &[u8]) -> Self;
44
45    /// Encodes itself into a new [Self::Buf] of size == [Self::SIZE]
46    fn as_new_fixed_size_bytes(&self) -> Self::Buf {
47        let mut buf = Self::Buf::new(Self::SIZE);
48        self.as_fixed_size_bytes(buf._deref_mut());
49
50        buf
51    }
52}
53
54macro_rules! impl_for_number {
55    ($ty:ty) => {
56        impl AsFixedSizeBytes for $ty {
57            const SIZE: usize = std::mem::size_of::<$ty>();
58            type Buf = [u8; Self::SIZE];
59
60            #[inline]
61            fn as_fixed_size_bytes(&self, buf: &mut [u8]) {
62                buf.copy_from_slice(&self.to_le_bytes())
63            }
64
65            #[inline]
66            fn from_fixed_size_bytes(buf: &[u8]) -> Self {
67                let mut b = Self::Buf::new(Self::SIZE);
68                b.copy_from_slice(buf);
69
70                Self::from_le_bytes(b)
71            }
72        }
73    };
74}
75
76impl_for_number!(i8);
77impl_for_number!(u8);
78impl_for_number!(i16);
79impl_for_number!(u16);
80impl_for_number!(i32);
81impl_for_number!(u32);
82impl_for_number!(i64);
83impl_for_number!(u64);
84impl_for_number!(i128);
85impl_for_number!(u128);
86impl_for_number!(isize);
87impl_for_number!(usize);
88impl_for_number!(f32);
89impl_for_number!(f64);
90
91impl AsFixedSizeBytes for char {
92    const SIZE: usize = u32::SIZE;
93    type Buf = [u8; Self::SIZE];
94
95    fn as_fixed_size_bytes(&self, buf: &mut [u8]) {
96        u32::from(*self).as_fixed_size_bytes(buf)
97    }
98
99    fn from_fixed_size_bytes(buf: &[u8]) -> Self {
100        char::try_from(u32::from_fixed_size_bytes(buf)).unwrap()
101    }
102}
103
104impl AsFixedSizeBytes for () {
105    const SIZE: usize = 0;
106    type Buf = [u8; 0];
107
108    #[inline]
109    fn as_fixed_size_bytes(&self, _: &mut [u8]) {}
110
111    #[inline]
112    fn from_fixed_size_bytes(_: &[u8]) -> Self {}
113}
114
115impl AsFixedSizeBytes for bool {
116    const SIZE: usize = 1;
117    type Buf = [u8; 1];
118
119    #[inline]
120    fn as_fixed_size_bytes(&self, buf: &mut [u8]) {
121        if *self {
122            buf[0] = 1;
123        } else {
124            buf[0] = 0;
125        }
126    }
127
128    #[inline]
129    fn from_fixed_size_bytes(buf: &[u8]) -> Self {
130        assert!(buf[0] < 2);
131
132        buf[0] == 1
133    }
134}
135
136impl<T: AsFixedSizeBytes> AsFixedSizeBytes for Option<T> {
137    const SIZE: usize = T::SIZE + 1;
138    type Buf = Vec<u8>;
139
140    #[inline]
141    fn as_fixed_size_bytes(&self, buf: &mut [u8]) {
142        if let Some(it) = self {
143            buf[0] = 1;
144            it.as_fixed_size_bytes(&mut buf[1..Self::SIZE]);
145        } else {
146            buf[0] = 0;
147        }
148    }
149
150    #[inline]
151    fn from_fixed_size_bytes(buf: &[u8]) -> Self {
152        if buf[0] == 1 {
153            Some(T::from_fixed_size_bytes(&buf[1..Self::SIZE]))
154        } else {
155            None
156        }
157    }
158}
159
160impl<const N: usize> AsFixedSizeBytes for [(); N] {
161    const SIZE: usize = 0;
162    type Buf = [u8; 0];
163
164    #[inline]
165    fn as_fixed_size_bytes(&self, _: &mut [u8]) {}
166
167    #[inline]
168    fn from_fixed_size_bytes(_: &[u8]) -> Self {
169        [(); N]
170    }
171}
172
173macro_rules! impl_for_single_byte_type_arr {
174    ($ty:ty, $zero:expr) => {
175        impl<const N: usize> AsFixedSizeBytes for [$ty; N] {
176            const SIZE: usize = N;
177            type Buf = [u8; N];
178
179            fn as_fixed_size_bytes(&self, buf: &mut [u8]) {
180                for i in 0..N {
181                    let from = i * <$ty>::SIZE;
182                    let to = from + <$ty>::SIZE;
183
184                    self[i].as_fixed_size_bytes(&mut buf[from..to]);
185                }
186            }
187
188            fn from_fixed_size_bytes(buf: &[u8]) -> Self {
189                let mut it = [$zero; N];
190
191                for i in 0..N {
192                    let from = i * <$ty>::SIZE;
193                    let to = from + <$ty>::SIZE;
194
195                    it[i] = <$ty>::from_fixed_size_bytes(&buf[from..to]);
196                }
197
198                it
199            }
200        }
201    };
202}
203
204impl_for_single_byte_type_arr!(bool, false);
205impl_for_single_byte_type_arr!(i8, 0);
206impl_for_single_byte_type_arr!(u8, 0);
207
208macro_rules! impl_for_number_arr {
209    ($ty:ty, $zero:expr) => {
210        impl<const N: usize> AsFixedSizeBytes for [$ty; N] {
211            const SIZE: usize = N;
212            type Buf = Vec<u8>;
213
214            fn as_fixed_size_bytes(&self, buf: &mut [u8]) {
215                for i in 0..N {
216                    let from = i * <$ty>::SIZE;
217                    let to = from + <$ty>::SIZE;
218
219                    self[i].as_fixed_size_bytes(&mut buf[from..to]);
220                }
221            }
222
223            fn from_fixed_size_bytes(buf: &[u8]) -> Self {
224                let mut it = [$zero; N];
225
226                for i in 0..N {
227                    let from = i * <$ty>::SIZE;
228                    let to = from + <$ty>::SIZE;
229
230                    it[i] = <$ty>::from_fixed_size_bytes(&buf[from..to]);
231                }
232
233                it
234            }
235        }
236    };
237}
238
239impl_for_number_arr!(i16, 0);
240impl_for_number_arr!(u16, 0);
241impl_for_number_arr!(i32, 0);
242impl_for_number_arr!(u32, 0);
243impl_for_number_arr!(i64, 0);
244impl_for_number_arr!(u64, 0);
245impl_for_number_arr!(i128, 0);
246impl_for_number_arr!(u128, 0);
247impl_for_number_arr!(isize, 0);
248impl_for_number_arr!(usize, 0);
249impl_for_number_arr!(f32, 0.0);
250impl_for_number_arr!(f64, 0.0);
251
252impl<const N: usize> AsFixedSizeBytes for [char; N] {
253    const SIZE: usize = N * char::SIZE;
254    type Buf = Vec<u8>;
255
256    fn as_fixed_size_bytes(&self, buf: &mut [u8]) {
257        let mut from = 0;
258
259        for c in self {
260            c.as_fixed_size_bytes(&mut buf[from..(from + u32::SIZE)]);
261            from += u32::SIZE;
262        }
263    }
264
265    fn from_fixed_size_bytes(buf: &[u8]) -> Self {
266        let mut s = [char::default(); N];
267
268        for from in 0..N {
269            s[from] =
270                char::from_fixed_size_bytes(&buf[(from * u32::SIZE)..((from + 1) * u32::SIZE)]);
271        }
272
273        s
274    }
275}
276
277impl<A: AsFixedSizeBytes> AsFixedSizeBytes for (A,) {
278    const SIZE: usize = A::SIZE;
279    type Buf = Vec<u8>;
280
281    fn as_fixed_size_bytes(&self, buf: &mut [u8]) {
282        self.0.as_fixed_size_bytes(buf)
283    }
284
285    fn from_fixed_size_bytes(buf: &[u8]) -> Self {
286        (A::from_fixed_size_bytes(buf),)
287    }
288}
289impl<A: AsFixedSizeBytes, B: AsFixedSizeBytes> AsFixedSizeBytes for (A, B) {
290    const SIZE: usize = A::SIZE + B::SIZE;
291    type Buf = Vec<u8>;
292
293    fn as_fixed_size_bytes(&self, buf: &mut [u8]) {
294        self.0.as_fixed_size_bytes(&mut buf[0..A::SIZE]);
295        self.1
296            .as_fixed_size_bytes(&mut buf[A::SIZE..(A::SIZE + B::SIZE)]);
297    }
298
299    fn from_fixed_size_bytes(buf: &[u8]) -> Self {
300        (
301            A::from_fixed_size_bytes(&buf[0..A::SIZE]),
302            B::from_fixed_size_bytes(&buf[A::SIZE..(A::SIZE + B::SIZE)]),
303        )
304    }
305}
306impl<A: AsFixedSizeBytes, B: AsFixedSizeBytes, C: AsFixedSizeBytes> AsFixedSizeBytes for (A, B, C) {
307    const SIZE: usize = A::SIZE + B::SIZE + C::SIZE;
308    type Buf = Vec<u8>;
309
310    fn as_fixed_size_bytes(&self, buf: &mut [u8]) {
311        self.0.as_fixed_size_bytes(&mut buf[0..A::SIZE]);
312        self.1
313            .as_fixed_size_bytes(&mut buf[A::SIZE..(A::SIZE + B::SIZE)]);
314        self.2
315            .as_fixed_size_bytes(&mut buf[(A::SIZE + B::SIZE)..(A::SIZE + B::SIZE + C::SIZE)]);
316    }
317
318    fn from_fixed_size_bytes(buf: &[u8]) -> Self {
319        (
320            A::from_fixed_size_bytes(&buf[0..A::SIZE]),
321            B::from_fixed_size_bytes(&buf[A::SIZE..(A::SIZE + B::SIZE)]),
322            C::from_fixed_size_bytes(&buf[(A::SIZE + B::SIZE)..(A::SIZE + B::SIZE + C::SIZE)]),
323        )
324    }
325}
326impl<A: AsFixedSizeBytes, B: AsFixedSizeBytes, C: AsFixedSizeBytes, D: AsFixedSizeBytes>
327    AsFixedSizeBytes for (A, B, C, D)
328{
329    const SIZE: usize = A::SIZE + B::SIZE + C::SIZE + D::SIZE;
330    type Buf = Vec<u8>;
331
332    fn as_fixed_size_bytes(&self, buf: &mut [u8]) {
333        self.0.as_fixed_size_bytes(&mut buf[0..A::SIZE]);
334        self.1
335            .as_fixed_size_bytes(&mut buf[A::SIZE..(A::SIZE + B::SIZE)]);
336        self.2
337            .as_fixed_size_bytes(&mut buf[(A::SIZE + B::SIZE)..(A::SIZE + B::SIZE + C::SIZE)]);
338        self.3.as_fixed_size_bytes(
339            &mut buf[(A::SIZE + B::SIZE + C::SIZE)..(A::SIZE + B::SIZE + C::SIZE + D::SIZE)],
340        );
341    }
342
343    fn from_fixed_size_bytes(buf: &[u8]) -> Self {
344        (
345            A::from_fixed_size_bytes(&buf[0..A::SIZE]),
346            B::from_fixed_size_bytes(&buf[A::SIZE..(A::SIZE + B::SIZE)]),
347            C::from_fixed_size_bytes(&buf[(A::SIZE + B::SIZE)..(A::SIZE + B::SIZE + C::SIZE)]),
348            D::from_fixed_size_bytes(
349                &buf[(A::SIZE + B::SIZE + C::SIZE)..(A::SIZE + B::SIZE + C::SIZE + D::SIZE)],
350            ),
351        )
352    }
353}
354impl<
355        A: AsFixedSizeBytes,
356        B: AsFixedSizeBytes,
357        C: AsFixedSizeBytes,
358        D: AsFixedSizeBytes,
359        E: AsFixedSizeBytes,
360    > AsFixedSizeBytes for (A, B, C, D, E)
361{
362    const SIZE: usize = A::SIZE + B::SIZE + C::SIZE + D::SIZE + E::SIZE;
363    type Buf = Vec<u8>;
364
365    fn as_fixed_size_bytes(&self, buf: &mut [u8]) {
366        self.0.as_fixed_size_bytes(&mut buf[0..A::SIZE]);
367        self.1
368            .as_fixed_size_bytes(&mut buf[A::SIZE..(A::SIZE + B::SIZE)]);
369        self.2
370            .as_fixed_size_bytes(&mut buf[(A::SIZE + B::SIZE)..(A::SIZE + B::SIZE + C::SIZE)]);
371        self.3.as_fixed_size_bytes(
372            &mut buf[(A::SIZE + B::SIZE + C::SIZE)..(A::SIZE + B::SIZE + C::SIZE + D::SIZE)],
373        );
374        self.4.as_fixed_size_bytes(
375            &mut buf[(A::SIZE + B::SIZE + C::SIZE + D::SIZE)
376                ..(A::SIZE + B::SIZE + C::SIZE + D::SIZE + E::SIZE)],
377        );
378    }
379
380    fn from_fixed_size_bytes(buf: &[u8]) -> Self {
381        (
382            A::from_fixed_size_bytes(&buf[0..A::SIZE]),
383            B::from_fixed_size_bytes(&buf[A::SIZE..(A::SIZE + B::SIZE)]),
384            C::from_fixed_size_bytes(&buf[(A::SIZE + B::SIZE)..(A::SIZE + B::SIZE + C::SIZE)]),
385            D::from_fixed_size_bytes(
386                &buf[(A::SIZE + B::SIZE + C::SIZE)..(A::SIZE + B::SIZE + C::SIZE + D::SIZE)],
387            ),
388            E::from_fixed_size_bytes(
389                &buf[(A::SIZE + B::SIZE + C::SIZE + D::SIZE)
390                    ..(A::SIZE + B::SIZE + C::SIZE + D::SIZE + E::SIZE)],
391            ),
392        )
393    }
394}
395impl<
396        A: AsFixedSizeBytes,
397        B: AsFixedSizeBytes,
398        C: AsFixedSizeBytes,
399        D: AsFixedSizeBytes,
400        E: AsFixedSizeBytes,
401        F: AsFixedSizeBytes,
402    > AsFixedSizeBytes for (A, B, C, D, E, F)
403{
404    const SIZE: usize = A::SIZE + B::SIZE + C::SIZE + D::SIZE + E::SIZE + F::SIZE;
405    type Buf = Vec<u8>;
406
407    fn as_fixed_size_bytes(&self, buf: &mut [u8]) {
408        self.0.as_fixed_size_bytes(&mut buf[0..A::SIZE]);
409        self.1
410            .as_fixed_size_bytes(&mut buf[A::SIZE..(A::SIZE + B::SIZE)]);
411        self.2
412            .as_fixed_size_bytes(&mut buf[(A::SIZE + B::SIZE)..(A::SIZE + B::SIZE + C::SIZE)]);
413        self.3.as_fixed_size_bytes(
414            &mut buf[(A::SIZE + B::SIZE + C::SIZE)..(A::SIZE + B::SIZE + C::SIZE + D::SIZE)],
415        );
416        self.4.as_fixed_size_bytes(
417            &mut buf[(A::SIZE + B::SIZE + C::SIZE + D::SIZE)
418                ..(A::SIZE + B::SIZE + C::SIZE + D::SIZE + E::SIZE)],
419        );
420        self.5.as_fixed_size_bytes(
421            &mut buf[(A::SIZE + B::SIZE + C::SIZE + D::SIZE + E::SIZE)
422                ..(A::SIZE + B::SIZE + C::SIZE + D::SIZE + E::SIZE + F::SIZE)],
423        );
424    }
425
426    fn from_fixed_size_bytes(buf: &[u8]) -> Self {
427        (
428            A::from_fixed_size_bytes(&buf[0..A::SIZE]),
429            B::from_fixed_size_bytes(&buf[A::SIZE..(A::SIZE + B::SIZE)]),
430            C::from_fixed_size_bytes(&buf[(A::SIZE + B::SIZE)..(A::SIZE + B::SIZE + C::SIZE)]),
431            D::from_fixed_size_bytes(
432                &buf[(A::SIZE + B::SIZE + C::SIZE)..(A::SIZE + B::SIZE + C::SIZE + D::SIZE)],
433            ),
434            E::from_fixed_size_bytes(
435                &buf[(A::SIZE + B::SIZE + C::SIZE + D::SIZE)
436                    ..(A::SIZE + B::SIZE + C::SIZE + D::SIZE + E::SIZE)],
437            ),
438            F::from_fixed_size_bytes(
439                &buf[(A::SIZE + B::SIZE + C::SIZE + D::SIZE + E::SIZE)
440                    ..(A::SIZE + B::SIZE + C::SIZE + D::SIZE + E::SIZE + F::SIZE)],
441            ),
442        )
443    }
444}
445
446impl AsFixedSizeBytes for Principal {
447    const SIZE: usize = 30;
448    type Buf = [u8; Self::SIZE];
449
450    fn as_fixed_size_bytes(&self, buf: &mut [u8]) {
451        let slice = self.as_slice();
452
453        buf[0] = slice.len() as u8;
454        buf[1..(1 + slice.len())].copy_from_slice(slice);
455    }
456
457    fn from_fixed_size_bytes(buf: &[u8]) -> Self {
458        let len = buf[0] as usize;
459
460        Principal::from_slice(&buf[1..(1 + len)])
461    }
462}
463
464impl AsFixedSizeBytes for Nat {
465    const SIZE: usize = 32;
466    type Buf = [u8; Self::SIZE];
467
468    fn as_fixed_size_bytes(&self, buf: &mut [u8]) {
469        let vec = self.0.to_bytes_le();
470        buf[0..vec.len()].copy_from_slice(&vec);
471    }
472
473    fn from_fixed_size_bytes(buf: &[u8]) -> Self {
474        let it = BigUint::from_bytes_le(buf);
475
476        Nat(it)
477    }
478}
479
480impl AsFixedSizeBytes for Int {
481    const SIZE: usize = 32;
482    type Buf = [u8; Self::SIZE];
483
484    fn as_fixed_size_bytes(&self, buf: &mut [u8]) {
485        let (sign, bytes) = self.0.to_bytes_le();
486
487        buf[0] = match sign {
488            Sign::Plus => 0u8,
489            Sign::Minus => 1u8,
490            Sign::NoSign => 2u8,
491        };
492
493        buf[1..(1 + bytes.len())].copy_from_slice(&bytes);
494    }
495
496    fn from_fixed_size_bytes(buf: &[u8]) -> Self {
497        let sign = match buf[0] {
498            0 => Sign::Plus,
499            1 => Sign::Minus,
500            2 => Sign::NoSign,
501            _ => unreachable!(),
502        };
503
504        let it = BigInt::from_bytes_le(sign, &buf[1..]);
505
506        Int(it)
507    }
508}
509
510/// Either [u8; N] or [Vec] of [u8]
511///
512/// You can't implement this trait for any other type than these two.
513pub trait Buffer: private::Sealed {
514    #[doc(hidden)]
515    fn new(size: usize) -> Self;
516    #[doc(hidden)]
517    fn _deref(&self) -> &[u8];
518    #[doc(hidden)]
519    fn _deref_mut(&mut self) -> &mut [u8];
520}
521
522impl<const N: usize> Buffer for [u8; N] {
523    #[inline]
524    fn new(_: usize) -> Self {
525        [0u8; N]
526    }
527
528    #[inline]
529    fn _deref(&self) -> &[u8] {
530        unsafe { std::slice::from_raw_parts(self as *const u8, self.len()) }
531    }
532
533    #[inline]
534    fn _deref_mut(&mut self) -> &mut [u8] {
535        unsafe { std::slice::from_raw_parts_mut(self as *mut u8, self.len()) }
536    }
537}
538
539impl Buffer for Vec<u8> {
540    #[inline]
541    fn new(size: usize) -> Self {
542        vec![0u8; size]
543    }
544
545    #[inline]
546    fn _deref(&self) -> &[u8] {
547        unsafe { std::slice::from_raw_parts(self.as_ptr(), self.len()) }
548    }
549
550    #[inline]
551    fn _deref_mut(&mut self) -> &mut [u8] {
552        unsafe { std::slice::from_raw_parts_mut(self.as_mut_ptr(), self.len()) }
553    }
554}
555
556mod private {
557    pub trait Sealed {}
558
559    impl<const N: usize> Sealed for [u8; N] {}
560    impl Sealed for Vec<u8> {}
561}
ic_stable_memory/encoding/fixed_size.rs

ic_stable_memory/encoding/
fixed_size.rs
