bitcoin_consensus_encoding/encode/
encoders.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! Collection of "standard encoders".
4//!
5//! These encoders should not be used directly. Instead, when implementing the
6//! [`super::Encodable`] trait on a type, you should define a newtype around one
7//! or more of these encoders, and pass through the [`Encoder`] implementation
8//! to your newtype. This avoids leaking encoding implementation details to the
9//! users of your type.
10//!
11//! For implementing these newtypes, we provide the [`encoder_newtype`] macro.
12//!
13
14use internals::array_vec::ArrayVec;
15use internals::{compact_size, ToU64};
16
17use super::{Encodable, Encoder};
18
19/// The maximum length of a compact size encoding.
20const SIZE: usize = 9;
21
22/// An encoder for a single byte slice.
23pub struct BytesEncoder<'sl> {
24    sl: Option<&'sl [u8]>,
25}
26
27impl<'sl> BytesEncoder<'sl> {
28    /// Constructs a byte encoder which encodes the given byte slice, with no length prefix.
29    pub const fn without_length_prefix(sl: &'sl [u8]) -> Self { Self { sl: Some(sl) } }
30}
31
32impl Encoder for BytesEncoder<'_> {
33    fn current_chunk(&self) -> &[u8] { self.sl.unwrap_or_default() }
34
35    fn advance(&mut self) -> bool {
36        self.sl = None;
37        false
38    }
39}
40
41/// An encoder for a single array.
42pub struct ArrayEncoder<const N: usize> {
43    arr: Option<[u8; N]>,
44}
45
46impl<const N: usize> ArrayEncoder<N> {
47    /// Constructs an encoder which encodes the array with no length prefix.
48    pub const fn without_length_prefix(arr: [u8; N]) -> Self { Self { arr: Some(arr) } }
49}
50
51impl<const N: usize> Encoder for ArrayEncoder<N> {
52    #[inline]
53    fn current_chunk(&self) -> &[u8] { self.arr.as_ref().map(|x| &x[..]).unwrap_or_default() }
54
55    #[inline]
56    fn advance(&mut self) -> bool {
57        self.arr = None;
58        false
59    }
60}
61
62/// An encoder for a list of encodable types.
63pub struct SliceEncoder<'e, T: Encodable> {
64    /// The list of references to the objects we are encoding.
65    sl: &'e [T],
66    /// Encoder for the current object being encoded.
67    cur_enc: Option<T::Encoder<'e>>,
68}
69
70impl<'e, T: Encodable> SliceEncoder<'e, T> {
71    /// Constructs an encoder which encodes the slice _without_ adding the length prefix.
72    ///
73    /// To encode with a length prefix consider using the `Encoder2`.
74    ///
75    /// E.g, `Encoder2<CompactSizeEncoder, SliceEncoder<'e, Foo>>`.
76    pub fn without_length_prefix(sl: &'e [T]) -> Self {
77        // In this `map` call we cannot remove the closure. Seems to be a bug in the compiler.
78        // Perhaps https://github.com/rust-lang/rust/issues/102540 which is 3 years old with
79        // no replies or even an acknowledgement. We will not bother filing our own issue.
80        Self { sl, cur_enc: sl.first().map(|x| T::encoder(x)) }
81    }
82}
83
84impl<T: Encodable> Encoder for SliceEncoder<'_, T> {
85    fn current_chunk(&self) -> &[u8] {
86        // `advance` sets `cur_enc` to `None` once the slice encoder is completely exhausted.
87        self.cur_enc.as_ref().map(T::Encoder::current_chunk).unwrap_or_default()
88    }
89
90    fn advance(&mut self) -> bool {
91        let Some(cur) = self.cur_enc.as_mut() else {
92            return false;
93        };
94
95        loop {
96            // On subsequent calls, attempt to advance the current encoder and return
97            // success if this succeeds.
98            if cur.advance() {
99                return true;
100            }
101            // self.sl guaranteed to be non-empty if cur is non-None.
102            self.sl = &self.sl[1..];
103
104            // If advancing the current encoder failed, attempt to move to the next encoder.
105            if let Some(x) = self.sl.first() {
106                *cur = x.encoder();
107                if !cur.current_chunk().is_empty() {
108                    return true;
109                }
110            } else {
111                self.cur_enc = None; // shortcut the next call to advance()
112                return false;
113            }
114        }
115    }
116}
117
118/// An encoder which encodes two objects, one after the other.
119pub struct Encoder2<A, B> {
120    enc_idx: usize,
121    enc_1: A,
122    enc_2: B,
123}
124
125impl<A, B> Encoder2<A, B> {
126    /// Constructs a new composite encoder.
127    pub const fn new(enc_1: A, enc_2: B) -> Self { Self { enc_idx: 0, enc_1, enc_2 } }
128}
129
130impl<A: Encoder, B: Encoder> Encoder for Encoder2<A, B> {
131    #[inline]
132    fn current_chunk(&self) -> &[u8] {
133        if self.enc_idx == 0 {
134            self.enc_1.current_chunk()
135        } else {
136            self.enc_2.current_chunk()
137        }
138    }
139
140    #[inline]
141    fn advance(&mut self) -> bool {
142        if self.enc_idx == 0 {
143            if !self.enc_1.advance() {
144                self.enc_idx += 1;
145            }
146            true
147        } else {
148            self.enc_2.advance()
149        }
150    }
151}
152
153// For now we implement every higher encoder by composing Encoder2s, because
154// I'm lazy and this is trivial both to write and to review. For efficiency, we
155// should eventually unroll all of these. There are only a couple of them. The
156// unrolled versions should be macro-izable, if we want to do that.
157
158/// An encoder which encodes three objects, one after the other.
159pub struct Encoder3<A, B, C> {
160    inner: Encoder2<Encoder2<A, B>, C>,
161}
162
163impl<A, B, C> Encoder3<A, B, C> {
164    /// Constructs a new composite encoder.
165    pub const fn new(enc_1: A, enc_2: B, enc_3: C) -> Self {
166        Self { inner: Encoder2::new(Encoder2::new(enc_1, enc_2), enc_3) }
167    }
168}
169
170impl<A: Encoder, B: Encoder, C: Encoder> Encoder for Encoder3<A, B, C> {
171    #[inline]
172    fn current_chunk(&self) -> &[u8] { self.inner.current_chunk() }
173    #[inline]
174    fn advance(&mut self) -> bool { self.inner.advance() }
175}
176
177/// An encoder which encodes four objects, one after the other.
178pub struct Encoder4<A, B, C, D> {
179    inner: Encoder2<Encoder2<A, B>, Encoder2<C, D>>,
180}
181
182impl<A, B, C, D> Encoder4<A, B, C, D> {
183    /// Constructs a new composite encoder.
184    pub const fn new(enc_1: A, enc_2: B, enc_3: C, enc_4: D) -> Self {
185        Self { inner: Encoder2::new(Encoder2::new(enc_1, enc_2), Encoder2::new(enc_3, enc_4)) }
186    }
187}
188
189impl<A: Encoder, B: Encoder, C: Encoder, D: Encoder> Encoder for Encoder4<A, B, C, D> {
190    #[inline]
191    fn current_chunk(&self) -> &[u8] { self.inner.current_chunk() }
192    #[inline]
193    fn advance(&mut self) -> bool { self.inner.advance() }
194}
195
196/// An encoder which encodes six objects, one after the other.
197pub struct Encoder6<A, B, C, D, E, F> {
198    inner: Encoder2<Encoder3<A, B, C>, Encoder3<D, E, F>>,
199}
200
201impl<A, B, C, D, E, F> Encoder6<A, B, C, D, E, F> {
202    /// Constructs a new composite encoder.
203    pub const fn new(enc_1: A, enc_2: B, enc_3: C, enc_4: D, enc_5: E, enc_6: F) -> Self {
204        Self {
205            inner: Encoder2::new(
206                Encoder3::new(enc_1, enc_2, enc_3),
207                Encoder3::new(enc_4, enc_5, enc_6),
208            ),
209        }
210    }
211}
212
213impl<A: Encoder, B: Encoder, C: Encoder, D: Encoder, E: Encoder, F: Encoder> Encoder
214    for Encoder6<A, B, C, D, E, F>
215{
216    #[inline]
217    fn current_chunk(&self) -> &[u8] { self.inner.current_chunk() }
218    #[inline]
219    fn advance(&mut self) -> bool { self.inner.advance() }
220}
221
222/// Encoder for a compact size encoded integer.
223pub struct CompactSizeEncoder {
224    buf: Option<ArrayVec<u8, SIZE>>,
225}
226
227impl CompactSizeEncoder {
228    /// Constructs a new `CompactSizeEncoder`.
229    pub fn new(value: impl ToU64) -> Self { Self { buf: Some(compact_size::encode(value)) } }
230}
231
232impl Encoder for CompactSizeEncoder {
233    #[inline]
234    fn current_chunk(&self) -> &[u8] { self.buf.as_ref().map(|b| &b[..]).unwrap_or_default() }
235
236    #[inline]
237    fn advance(&mut self) -> bool {
238        self.buf = None;
239        false
240    }
241}
242
243#[cfg(test)]
244mod tests {
245    use super::*;
246
247    struct TestBytes<'a>(&'a [u8]);
248
249    impl Encodable for TestBytes<'_> {
250        type Encoder<'s>
251            = BytesEncoder<'s>
252        where
253            Self: 's;
254
255        fn encoder(&self) -> Self::Encoder<'_> { BytesEncoder::without_length_prefix(self.0) }
256    }
257
258    struct TestArray<const N: usize>([u8; N]);
259
260    impl<const N: usize> Encodable for TestArray<N> {
261        type Encoder<'s>
262            = ArrayEncoder<N>
263        where
264            Self: 's;
265
266        fn encoder(&self) -> Self::Encoder<'_> { ArrayEncoder::without_length_prefix(self.0) }
267    }
268
269    #[test]
270    fn encode_array_with_data() {
271        // Should have one chunk with the array data, then exhausted.
272        let test_array = TestArray([1u8, 2, 3, 4]);
273        let mut encoder = test_array.encoder();
274        assert_eq!(encoder.current_chunk(), &[1u8, 2, 3, 4][..]);
275        assert!(!encoder.advance());
276        assert!(encoder.current_chunk().is_empty());
277    }
278
279    #[test]
280    fn encode_empty_array() {
281        // Empty array should have one empty chunk, then exhausted.
282        let test_array = TestArray([]);
283        let mut encoder = test_array.encoder();
284        assert!(encoder.current_chunk().is_empty());
285        assert!(!encoder.advance());
286        assert!(encoder.current_chunk().is_empty());
287    }
288
289    #[test]
290    fn encode_byte_slice_without_prefix() {
291        // Should have one chunk with the byte data, then exhausted.
292        let obj = [1u8, 2, 3];
293        let test_bytes = TestBytes(&obj);
294        let mut encoder = test_bytes.encoder();
295
296        assert_eq!(encoder.current_chunk(), &[1u8, 2, 3][..]);
297        assert!(!encoder.advance());
298        assert!(encoder.current_chunk().is_empty());
299    }
300
301    #[test]
302    fn encode_empty_byte_slice_without_prefix() {
303        // Should have one empty chunk, then exhausted.
304        let obj = [];
305        let test_bytes = TestBytes(&obj);
306        let mut encoder = test_bytes.encoder();
307
308        assert!(encoder.current_chunk().is_empty());
309        assert!(!encoder.advance());
310        assert!(encoder.current_chunk().is_empty());
311    }
312
313    #[test]
314    fn encode_slice_with_elements() {
315        // Should have the element chunks, then exhausted.
316        let slice = &[TestArray([0x34, 0x12, 0x00, 0x00]), TestArray([0x78, 0x56, 0x00, 0x00])];
317        let mut encoder = SliceEncoder::without_length_prefix(slice);
318
319        assert_eq!(encoder.current_chunk(), &[0x34, 0x12, 0x00, 0x00][..]);
320        assert!(encoder.advance());
321        assert_eq!(encoder.current_chunk(), &[0x78, 0x56, 0x00, 0x00][..]);
322        assert!(!encoder.advance());
323        assert!(encoder.current_chunk().is_empty());
324    }
325
326    #[test]
327    fn encode_empty_slice() {
328        // Should immediately be exhausted.
329        let slice: &[TestArray<4>] = &[];
330        let mut encoder = SliceEncoder::without_length_prefix(slice);
331
332        assert!(!encoder.advance());
333        assert!(encoder.current_chunk().is_empty());
334    }
335
336    #[test]
337    fn encode_slice_with_zero_sized_arrays() {
338        // Should have empty array chunks, then exhausted.
339        let slice = &[TestArray([]), TestArray([])];
340        let mut encoder = SliceEncoder::without_length_prefix(slice);
341
342        assert!(encoder.current_chunk().is_empty());
343        // The slice advanced is optimized to skip over empty chunks.
344        assert!(!encoder.advance());
345        assert!(encoder.current_chunk().is_empty());
346    }
347
348    #[test]
349    fn encode_two_arrays() {
350        // Should encode first array, then second array, then exhausted.
351        let enc1 = TestArray([1u8, 2]).encoder();
352        let enc2 = TestArray([3u8, 4]).encoder();
353        let mut encoder = Encoder2::new(enc1, enc2);
354
355        assert_eq!(encoder.current_chunk(), &[1u8, 2][..]);
356        assert!(encoder.advance());
357        assert_eq!(encoder.current_chunk(), &[3u8, 4][..]);
358        assert!(!encoder.advance());
359        assert!(encoder.current_chunk().is_empty());
360    }
361
362    #[test]
363    fn encode_two_empty_arrays() {
364        // Should encode first empty array, then second empty array, then exhausted.
365        let enc1 = TestArray([]).encoder();
366        let enc2 = TestArray([]).encoder();
367        let mut encoder = Encoder2::new(enc1, enc2);
368
369        assert!(encoder.current_chunk().is_empty());
370        assert!(encoder.advance());
371        assert!(encoder.current_chunk().is_empty());
372        assert!(!encoder.advance());
373        assert!(encoder.current_chunk().is_empty());
374    }
375
376    #[test]
377    fn encode_three_arrays() {
378        // Should encode three arrays in sequence, then exhausted.
379        let enc1 = TestArray([1u8]).encoder();
380        let enc2 = TestArray([2u8, 3u8]).encoder();
381        let enc3 = TestArray([4u8, 5u8, 6u8]).encoder();
382        let mut encoder = Encoder3::new(enc1, enc2, enc3);
383
384        assert_eq!(encoder.current_chunk(), &[1u8][..]);
385        assert!(encoder.advance());
386        assert_eq!(encoder.current_chunk(), &[2u8, 3u8][..]);
387        assert!(encoder.advance());
388        assert_eq!(encoder.current_chunk(), &[4u8, 5u8, 6u8][..]);
389        assert!(!encoder.advance());
390        assert!(encoder.current_chunk().is_empty());
391    }
392
393    #[test]
394    fn encode_four_arrays() {
395        // Should encode four arrays in sequence, then exhausted.
396        let enc1 = TestArray([0x10]).encoder();
397        let enc2 = TestArray([0x20]).encoder();
398        let enc3 = TestArray([0x30]).encoder();
399        let enc4 = TestArray([0x40]).encoder();
400        let mut encoder = Encoder4::new(enc1, enc2, enc3, enc4);
401
402        assert_eq!(encoder.current_chunk(), &[0x10][..]);
403        assert!(encoder.advance());
404        assert_eq!(encoder.current_chunk(), &[0x20][..]);
405        assert!(encoder.advance());
406        assert_eq!(encoder.current_chunk(), &[0x30][..]);
407        assert!(encoder.advance());
408        assert_eq!(encoder.current_chunk(), &[0x40][..]);
409        assert!(!encoder.advance());
410        assert!(encoder.current_chunk().is_empty());
411    }
412
413    #[test]
414    fn encode_six_arrays() {
415        // Should encode six arrays in sequence, then exhausted.
416        let enc1 = TestArray([0x01]).encoder();
417        let enc2 = TestArray([0x02]).encoder();
418        let enc3 = TestArray([0x03]).encoder();
419        let enc4 = TestArray([0x04]).encoder();
420        let enc5 = TestArray([0x05]).encoder();
421        let enc6 = TestArray([0x06]).encoder();
422        let mut encoder = Encoder6::new(enc1, enc2, enc3, enc4, enc5, enc6);
423
424        assert_eq!(encoder.current_chunk(), &[0x01][..]);
425        assert!(encoder.advance());
426        assert_eq!(encoder.current_chunk(), &[0x02][..]);
427        assert!(encoder.advance());
428        assert_eq!(encoder.current_chunk(), &[0x03][..]);
429        assert!(encoder.advance());
430        assert_eq!(encoder.current_chunk(), &[0x04][..]);
431        assert!(encoder.advance());
432        assert_eq!(encoder.current_chunk(), &[0x05][..]);
433        assert!(encoder.advance());
434        assert_eq!(encoder.current_chunk(), &[0x06][..]);
435        assert!(!encoder.advance());
436        assert!(encoder.current_chunk().is_empty());
437    }
438
439    #[test]
440    fn encode_mixed_composition_with_byte_slices() {
441        // Should encode byte slice, then array, then exhausted.
442        let enc1 = TestBytes(&[0xFF, 0xEE]).encoder();
443        let enc2 = TestArray([0xDD, 0xCC]).encoder();
444        let mut encoder = Encoder2::new(enc1, enc2);
445
446        assert_eq!(encoder.current_chunk(), &[0xFF, 0xEE][..]);
447        assert!(encoder.advance());
448        assert_eq!(encoder.current_chunk(), &[0xDD, 0xCC][..]);
449        assert!(!encoder.advance());
450        assert!(encoder.current_chunk().is_empty());
451    }
452
453    #[test]
454    fn encode_nested_composition() {
455        // Should encode empty array, single byte array, then three byte array, then exhausted.
456        let enc1 = TestArray([]).encoder();
457        let enc2 = TestArray([0x42]).encoder();
458        let enc3 = TestArray([0x43, 0x44, 0x45]).encoder();
459        let mut encoder = Encoder3::new(enc1, enc2, enc3);
460
461        assert!(encoder.current_chunk().is_empty());
462        assert!(encoder.advance());
463        assert_eq!(encoder.current_chunk(), &[0x42][..]);
464        assert!(encoder.advance());
465        assert_eq!(encoder.current_chunk(), &[0x43, 0x44, 0x45][..]);
466        assert!(!encoder.advance());
467        assert!(encoder.current_chunk().is_empty());
468    }
469
470    #[test]
471    fn encode_slice_with_array_composition() {
472        // Should encode slice elements, then array, then exhausted.
473        let slice = &[TestArray([0x10, 0x11]), TestArray([0x12, 0x13])];
474        let slice_enc = SliceEncoder::without_length_prefix(slice);
475        let array_enc = TestArray([0x20, 0x21]).encoder();
476        let mut encoder = Encoder2::new(slice_enc, array_enc);
477
478        assert_eq!(encoder.current_chunk(), &[0x10, 0x11][..]);
479        assert!(encoder.advance());
480        assert_eq!(encoder.current_chunk(), &[0x12, 0x13][..]);
481        assert!(encoder.advance());
482        assert_eq!(encoder.current_chunk(), &[0x20, 0x21][..]);
483        assert!(!encoder.advance());
484        assert!(encoder.current_chunk().is_empty());
485    }
486
487    #[test]
488    fn encode_array_with_slice_composition() {
489        // Should encode header array, then slice elements, then exhausted.
490        let header = TestArray([0xFF, 0xFE]).encoder();
491        let slice = &[TestArray([0x01]), TestArray([0x02]), TestArray([0x03])];
492        let slice_enc = SliceEncoder::without_length_prefix(slice);
493        let mut encoder = Encoder2::new(header, slice_enc);
494
495        assert_eq!(encoder.current_chunk(), &[0xFF, 0xFE][..]);
496        assert!(encoder.advance());
497        assert_eq!(encoder.current_chunk(), &[0x01][..]);
498        assert!(encoder.advance());
499        assert_eq!(encoder.current_chunk(), &[0x02][..]);
500        assert!(encoder.advance());
501        assert_eq!(encoder.current_chunk(), &[0x03][..]);
502        assert!(!encoder.advance());
503        assert!(encoder.current_chunk().is_empty());
504    }
505
506    #[test]
507    fn encode_multiple_slices_composition() {
508        // Should encode three slices in sequence, then exhausted.
509        let slice1 = &[TestArray([0xA1]), TestArray([0xA2])];
510        let slice2: &[TestArray<1>] = &[];
511        let slice3 = &[TestArray([0xC1]), TestArray([0xC2]), TestArray([0xC3])];
512
513        let enc1 = SliceEncoder::without_length_prefix(slice1);
514        let enc2 = SliceEncoder::without_length_prefix(slice2);
515        let enc3 = SliceEncoder::without_length_prefix(slice3);
516        let mut encoder = Encoder3::new(enc1, enc2, enc3);
517
518        assert_eq!(encoder.current_chunk(), &[0xA1][..]);
519        assert!(encoder.advance());
520        assert_eq!(encoder.current_chunk(), &[0xA2][..]);
521
522        // Skip the empty slice
523        assert!(encoder.advance());
524
525        assert!(encoder.advance());
526        assert_eq!(encoder.current_chunk(), &[0xC1][..]);
527        assert!(encoder.advance());
528        assert_eq!(encoder.current_chunk(), &[0xC2][..]);
529        assert!(encoder.advance());
530        assert_eq!(encoder.current_chunk(), &[0xC3][..]);
531        assert!(!encoder.advance());
532        assert!(encoder.current_chunk().is_empty());
533    }
534
535    #[test]
536    fn encode_complex_nested_structure() {
537        // Should encode header, slice with elements, and footer with prefix, then exhausted.
538        let header = TestBytes(&[0xDE, 0xAD]).encoder();
539        let data_slice = &[TestArray([0x01, 0x02]), TestArray([0x03, 0x04])];
540        let slice_enc = SliceEncoder::without_length_prefix(data_slice);
541        let footer = TestBytes(&[0xBE, 0xEF]).encoder();
542        let mut encoder = Encoder3::new(header, slice_enc, footer);
543
544        assert_eq!(encoder.current_chunk(), &[0xDE, 0xAD][..]);
545        assert!(encoder.advance());
546        assert_eq!(encoder.current_chunk(), &[0x01, 0x02][..]);
547        assert!(encoder.advance());
548        assert_eq!(encoder.current_chunk(), &[0x03, 0x04][..]);
549        assert!(encoder.advance());
550        assert_eq!(encoder.current_chunk(), &[0xBE, 0xEF][..]);
551        assert!(!encoder.advance());
552        assert!(encoder.current_chunk().is_empty());
553    }
554    #[test]
555    fn encode_compact_size() {
556        // 1-byte
557        let mut e = CompactSizeEncoder::new(0x10u64);
558        assert_eq!(e.current_chunk(), &[0x10][..]);
559        assert!(!e.advance());
560        assert!(e.current_chunk().is_empty());
561
562        let mut e = CompactSizeEncoder::new(0xFCu64);
563        assert_eq!(e.current_chunk(), &[0xFC][..]);
564        assert!(!e.advance());
565        assert!(e.current_chunk().is_empty());
566
567        // 0xFD + u16
568        let mut e = CompactSizeEncoder::new(0x00FDu64);
569        assert_eq!(e.current_chunk(), &[0xFD, 0xFD, 0x00][..]);
570        assert!(!e.advance());
571        assert!(e.current_chunk().is_empty());
572
573        let mut e = CompactSizeEncoder::new(0x0FFFu64);
574        assert_eq!(e.current_chunk(), &[0xFD, 0xFF, 0x0F][..]);
575        assert!(!e.advance());
576        assert!(e.current_chunk().is_empty());
577
578        // 0xFE + u32
579        let mut e = CompactSizeEncoder::new(0x0001_0000u64);
580        assert_eq!(e.current_chunk(), &[0xFE, 0x00, 0x00, 0x01, 0x00][..]);
581        assert!(!e.advance());
582        assert!(e.current_chunk().is_empty());
583
584        let mut e = CompactSizeEncoder::new(0x0F0F_0F0Fu64);
585        assert_eq!(e.current_chunk(), &[0xFE, 0x0F, 0x0F, 0x0F, 0x0F][..]);
586        assert!(!e.advance());
587        assert!(e.current_chunk().is_empty());
588
589        // 0xFF + u64
590        let mut e = CompactSizeEncoder::new(0x0000_F0F0_F0F0_F0E0u64);
591        assert_eq!(e.current_chunk(), &[0xFF, 0xE0, 0xF0, 0xF0, 0xF0, 0xF0, 0xF0, 0x00, 0x00][..]);
592        assert!(!e.advance());
593        assert!(e.current_chunk().is_empty());
594    }
595}
bitcoin_consensus_encoding/encode/encoders.rs

bitcoin_consensus_encoding/encode/
encoders.rs
