bitcoin_consensus_encoding/
compact_size.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! Compact size codec.
4//!
5//! Compact size is a variable-length integer encoding used throughout the Bitcoin
6//! consensus protocol to encode collection lengths. However, there are also some
7//! unique non-length use cases.
8
9use internals::array_vec::ArrayVec;
10
11use crate::decode::Decoder;
12use crate::encode::{Encoder, EncoderStatus, ExactSizeEncoder};
13use crate::error::{
14    CompactSizeDecoderError, CompactSizeDecoderErrorInner, LengthPrefixExceedsMaxError,
15};
16use crate::DecoderStatus;
17
18/// Default maximum size of a decoded object in bytes.
19///
20/// Matches Bitcoin Core's default [serialization limit]. This is
21/// a high level anti-DoS limit which all bitcoin types should
22/// easily fit within.
23///
24/// [serialization limit]: https://github.com/bitcoin/bitcoin/blob/a7c29df0e5ace05b6186612671d6103c112ec922/src/serialize.h#L32
25const MAX_COMPACT_SIZE: usize = 0x0200_0000;
26
27/// The maximum length of a compact size encoding.
28const SIZE: usize = 9;
29
30/// Compact size prefix byte indicating a 2-byte `u16` payload follows.
31const PREFIX_U16: u8 = 0xFD;
32/// Compact size prefix byte indicating a 4-byte `u32` payload follows.
33const PREFIX_U32: u8 = 0xFE;
34/// Compact size prefix byte indicating an 8-byte `u64` payload follows.
35const PREFIX_U64: u8 = 0xFF;
36
37/// Encoder for a compact size encoded integer.
38#[derive(Debug, Clone)]
39pub struct CompactSizeEncoder {
40    buf: ArrayVec<u8, SIZE>,
41}
42
43impl CompactSizeEncoder {
44    /// Constructs a new `CompactSizeEncoder` for a length prefix.
45    ///
46    /// The `usize` type is the natural Rust type for lengths and collection sizes, which is the
47    /// dominant use case for compact size encoding in the Bitcoin protocol. Prefer this constructor
48    /// whenever you are encoding the length of a collection or a byte slice.
49    ///
50    /// Compact size encodings are defined only over the `u64` range. Hypothetical future platforms
51    /// that have `usize` greater than 64 bits are currently not supported.
52    ///
53    /// If you need to encode an arbitrary `u64` integer that is not a length prefix, use
54    /// [`Self::new_u64`] instead.
55    pub fn new(value: usize) -> Self {
56        const _WE_ONLY_SUPPORT_ARCHITECTURES_WITH_UP_TO_64_BIT_USIZE: () = {
57            assert!(core::mem::size_of::<usize>() <= 8);
58        };
59        Self { buf: Self::encode(value as u64) }
60    }
61
62    /// Constructs a new `CompactSizeEncoder` for an arbitrary `u64` integer.
63    ///
64    /// Prefer [`Self::new`] unless you are encoding a non-length integer.
65    ///
66    /// A small number of fields in the Bitcoin protocol are compact-size-encoded integers that are
67    /// not collection lengths (e.g. service flags). Use this constructor for those cases, where the
68    /// natural type of the value is `u64` rather than `usize`.
69    pub fn new_u64(value: u64) -> Self { Self { buf: Self::encode(value) } }
70
71    /// Returns the number of bytes used to encode this `CompactSize` value.
72    ///
73    /// # Returns
74    ///
75    /// - 1 for 0..=0xFC
76    /// - 3 for 0xFD..=(2^16-1)
77    /// - 5 for 0x10000..=(2^32-1)
78    /// - 9 otherwise.
79    #[inline]
80    pub const fn encoded_size(value: usize) -> usize {
81        match value {
82            0..=0xFC => 1,
83            0xFD..=0xFFFF => 3,
84            0x10000..=0xFFFF_FFFF => 5,
85            _ => 9,
86        }
87    }
88
89    /// Encodes `CompactSize` without allocating.
90    #[inline]
91    fn encode(value: u64) -> ArrayVec<u8, SIZE> {
92        let mut res = ArrayVec::<u8, SIZE>::new();
93        match value {
94            0..=0xFC => {
95                res.push(value as u8); // Cast ok because of match.
96            }
97            0xFD..=0xFFFF => {
98                let v = value as u16; // Cast ok because of match.
99                res.push(PREFIX_U16);
100                res.extend_from_slice(&v.to_le_bytes());
101            }
102            0x10000..=0xFFFF_FFFF => {
103                let v = value as u32; // Cast ok because of match.
104                res.push(PREFIX_U32);
105                res.extend_from_slice(&v.to_le_bytes());
106            }
107            _ => {
108                res.push(PREFIX_U64);
109                res.extend_from_slice(&value.to_le_bytes());
110            }
111        }
112        res
113    }
114}
115
116impl Encoder for CompactSizeEncoder {
117    #[inline]
118    fn current_chunk(&self) -> &[u8] { &self.buf }
119
120    #[inline]
121    fn advance(&mut self) -> EncoderStatus { EncoderStatus::Finished }
122}
123
124impl ExactSizeEncoder for CompactSizeEncoder {
125    #[inline]
126    fn len(&self) -> usize { self.buf.len() }
127}
128
129/// Decodes a compact size encoded integer as a length prefix.
130///
131/// The decoded value is returned as a `usize` and is bounded by a configurable limit (default:
132/// 4,000,000). This limit is a denial-of-service protection: a malicious peer can send a compact
133/// size value up to 2^64-1, and without a limit check the caller might attempt to allocate an
134/// enormous buffer based on that value. [`CompactSizeDecoder`] prevents this by rejecting values
135/// that exceed the limit before returning them to the caller.
136///
137/// If you are decoding an arbitrary `u64` integer that is genuinely not a length prefix, use
138/// [`CompactSizeU64Decoder`] instead.
139///
140/// For more information about decoders see the documentation of the [`Decoder`] trait.
141#[derive(Debug, Clone)]
142pub struct CompactSizeDecoder {
143    buf: ArrayVec<u8, 9>,
144    limit: usize,
145}
146
147impl CompactSizeDecoder {
148    /// Constructs a new compact size decoder with the default 32MB length limit.
149    pub const fn new() -> Self { Self { buf: ArrayVec::new(), limit: MAX_COMPACT_SIZE } }
150
151    /// Constructs a new compact size decoder with a custom length limit.
152    ///
153    /// The decoded value must not exceed `limit`, otherwise [`end`](Self::end) will return an
154    /// error. Use this when you know the field you are decoding has a tighter bound than the
155    /// default limit of 32MB.
156    pub const fn new_with_limit(limit: usize) -> Self { Self { buf: ArrayVec::new(), limit } }
157}
158
159impl Default for CompactSizeDecoder {
160    fn default() -> Self { Self::new() }
161}
162
163impl Decoder for CompactSizeDecoder {
164    type Output = usize;
165    type Error = CompactSizeDecoderError;
166
167    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<DecoderStatus, Self::Error> {
168        Ok(compact_size_push_bytes(&mut self.buf, bytes))
169    }
170
171    fn end(self) -> Result<Self::Output, Self::Error> {
172        use CompactSizeDecoderErrorInner as E;
173
174        let dec_value = compact_size_decode_u64(&self.buf)?;
175
176        match usize::try_from(dec_value) {
177            Ok(nsize) if nsize <= self.limit => Ok(nsize),
178            _ => Err(CompactSizeDecoderError(E::ValueExceedsLimit(LengthPrefixExceedsMaxError {
179                limit: self.limit,
180                value: dec_value,
181            }))),
182        }
183    }
184
185    fn read_limit(&self) -> usize { compact_size_read_limit(&self.buf) }
186}
187
188/// Decodes a compact size encoded integer as a raw `u64`.
189///
190/// If you are decoding a length prefix, you probably want [`CompactSizeDecoder`] instead.
191///
192/// This decoder performs no limit check and no conversion to `usize`. It exists for the small
193/// number of Bitcoin protocol fields that are compact-size-encoded integers but are not length
194/// prefixes (e.g. service flags in the `version` message). For those fields the full `u64` range is
195/// meaningful and there is no associated allocation whose size would be controlled by the decoded
196/// value.
197///
198/// # Denial-of-service warning
199///
200/// Do not use this decoder for length prefixes. If the decoded value is used to size an allocation,
201/// for example as the length of a `Vec`, a malicious peer can send a compact size value of up to
202/// 2^64-1 and cause an out-of-memory condition. [`CompactSizeDecoder`] prevents this by enforcing a
203/// configurable upper bound before returning the value.
204///
205/// For more information about decoders see the documentation of the [`Decoder`] trait.
206#[derive(Debug, Clone)]
207pub struct CompactSizeU64Decoder {
208    buf: ArrayVec<u8, 9>,
209}
210
211impl CompactSizeU64Decoder {
212    /// Constructs a new `CompactSizeU64Decoder`.
213    ///
214    /// See the [struct-level documentation](Self) for guidance on when to use this decoder versus
215    /// [`CompactSizeDecoder`].
216    pub const fn new() -> Self { Self { buf: ArrayVec::new() } }
217}
218
219impl Default for CompactSizeU64Decoder {
220    fn default() -> Self { Self::new() }
221}
222
223impl Decoder for CompactSizeU64Decoder {
224    type Output = u64;
225    type Error = CompactSizeDecoderError;
226
227    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<DecoderStatus, Self::Error> {
228        Ok(compact_size_push_bytes(&mut self.buf, bytes))
229    }
230
231    fn end(self) -> Result<Self::Output, Self::Error> { compact_size_decode_u64(&self.buf) }
232
233    fn read_limit(&self) -> usize { compact_size_read_limit(&self.buf) }
234}
235
236/// Pushes bytes into a compact size buffer, returning the decoder status.
237fn compact_size_push_bytes(buf: &mut ArrayVec<u8, 9>, bytes: &mut &[u8]) -> DecoderStatus {
238    if bytes.is_empty() {
239        return DecoderStatus::NeedsMore;
240    }
241
242    if buf.is_empty() {
243        buf.push(bytes[0]);
244        *bytes = &bytes[1..];
245    }
246    let len = match buf[0] {
247        PREFIX_U64 => 9,
248        PREFIX_U32 => 5,
249        PREFIX_U16 => 3,
250        _ => 1,
251    };
252    let to_copy = bytes.len().min(len - buf.len());
253    buf.extend_from_slice(&bytes[..to_copy]);
254    *bytes = &bytes[to_copy..];
255
256    if buf.len() == len {
257        DecoderStatus::Ready
258    } else {
259        DecoderStatus::NeedsMore
260    }
261}
262
263/// Returns the number of bytes the compact size decoder still needs to read.
264fn compact_size_read_limit(buf: &ArrayVec<u8, 9>) -> usize {
265    match buf.len() {
266        0 => 1,
267        already_read => match buf[0] {
268            PREFIX_U64 => 9_usize.saturating_sub(already_read),
269            PREFIX_U32 => 5_usize.saturating_sub(already_read),
270            PREFIX_U16 => 3_usize.saturating_sub(already_read),
271            _ => 0,
272        },
273    }
274}
275
276/// Decodes a compact size buffer to a u64, checking for minimal encoding.
277fn compact_size_decode_u64(buf: &ArrayVec<u8, 9>) -> Result<u64, CompactSizeDecoderError> {
278    use CompactSizeDecoderErrorInner as E;
279
280    fn arr<const N: usize>(slice: &[u8]) -> Result<[u8; N], CompactSizeDecoderError> {
281        slice
282            .try_into()
283            .map_err(|_| E::UnexpectedEof { required: N, received: slice.len() })
284            .map_err(CompactSizeDecoderError)
285    }
286
287    let (first, payload) = buf
288        .split_first()
289        .ok_or(E::UnexpectedEof { required: 1, received: 0 })
290        .map_err(CompactSizeDecoderError)?;
291
292    match *first {
293        PREFIX_U64 => {
294            let x = u64::from_le_bytes(arr(payload)?);
295            if x < 0x100_000_000 {
296                Err(CompactSizeDecoderError(E::NonMinimal { value: x }))
297            } else {
298                Ok(x)
299            }
300        }
301        PREFIX_U32 => {
302            let x = u32::from_le_bytes(arr(payload)?);
303            if x < 0x10000 {
304                Err(CompactSizeDecoderError(E::NonMinimal { value: x.into() }))
305            } else {
306                Ok(x.into())
307            }
308        }
309        PREFIX_U16 => {
310            let x = u16::from_le_bytes(arr(payload)?);
311            if x < 0xFD {
312                Err(CompactSizeDecoderError(E::NonMinimal { value: x.into() }))
313            } else {
314                Ok(x.into())
315            }
316        }
317        n => Ok(n.into()),
318    }
319}
320
321#[cfg(test)]
322mod tests {
323    use super::*;
324
325    #[test]
326    fn encoded_value_1_byte() {
327        // Check lower bound, upper bound (and implicitly endian-ness).
328        for v in [0x00u64, 0x01, 0x02, 0xFA, 0xFB, 0xFC] {
329            assert_eq!(CompactSizeEncoder::encoded_size(v as usize), 1);
330            // Should be encoded as the value as a u8.
331            let want = [v as u8];
332            let got = CompactSizeEncoder::encode(v);
333            assert_eq!(got.as_slice().len(), 1); // sanity check
334            assert_eq!(got.as_slice(), want);
335        }
336    }
337
338    macro_rules! check_encode {
339        ($($test_name:ident, $size:expr, $value:expr, $want:expr);* $(;)?) => {
340            $(
341                #[test]
342                fn $test_name() {
343                    let value = $value as u64; // Because default integer type is i32.
344                    assert_eq!(CompactSizeEncoder::encoded_size(value as usize), $size);
345                    let got = CompactSizeEncoder::encode(value);
346                    assert_eq!(got.as_slice().len(), $size); // sanity check
347                    assert_eq!(got.as_slice(), &$want);
348                }
349            )*
350        }
351    }
352
353    check_encode! {
354        // 3 byte encoding.
355        encoded_value_3_byte_lower_bound, 3, 0xFD, [0xFD, 0xFD, 0x00]; // 0x00FD
356        encoded_value_3_byte_endianness, 3, 0xABCD, [0xFD, 0xCD, 0xAB];
357        encoded_value_3_byte_upper_bound, 3, 0xFFFF, [0xFD, 0xFF, 0xFF];
358        // 5 byte encoding.
359        encoded_value_5_byte_lower_bound, 5, 0x0001_0000, [0xFE, 0x00, 0x00, 0x01, 0x00];
360        encoded_value_5_byte_endianness, 5, 0x0123_4567, [0xFE, 0x67, 0x45, 0x23, 0x01];
361        encoded_value_5_byte_upper_bound, 5, 0xFFFF_FFFF, [0xFE, 0xFF, 0xFF, 0xFF, 0xFF];
362    }
363
364    // 9-byte encoding requires values above u32::MAX which don't fit in usize on 32-bit platforms.
365    #[cfg(target_pointer_width = "64")]
366    check_encode! {
367        encoded_value_9_byte_lower_bound, 9, 0x0000_0001_0000_0000u64, [0xFF, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00];
368        encoded_value_9_byte_endianness, 9, 0x0123_4567_89AB_CDEFu64, [0xFF, 0xEF, 0xCD, 0xAB, 0x89, 0x67, 0x45, 0x23, 0x01];
369        encoded_value_9_byte_upper_bound, 9, u64::MAX, [0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF];
370    }
371
372    #[test]
373    fn compact_size_new_values_too_large() {
374        use CompactSizeDecoderErrorInner as E;
375
376        const EXCESS_COMPACT_SIZE: u64 = (MAX_COMPACT_SIZE + 1) as u64;
377
378        // MAX_COMPACT_SIZE should succeed for `new` constructor
379        // 0x0200_0000 as minimal 5-byte compact size: 0xFE + u32 little-endian
380        let mut decoder = CompactSizeDecoder::new();
381        let _ = decoder.push_bytes(&mut [0xFE, 0x00, 0x00, 0x00, 0x02].as_slice()).unwrap();
382        let got = decoder.end().unwrap();
383        assert_eq!(got, MAX_COMPACT_SIZE);
384
385        // MAX_COMPACT_SIZE + 1 should fail for `new` constructor
386        // 0x0200_0001 as minimal 5-byte compact size: 0xFE + u32 little-endian
387        let mut decoder = CompactSizeDecoder::new();
388        let _ = decoder.push_bytes(&mut [0xFE, 0x01, 0x00, 0x00, 0x02].as_slice()).unwrap();
389        let got = decoder.end().unwrap_err();
390        assert!(matches!(
391            got,
392            CompactSizeDecoderError(E::ValueExceedsLimit(LengthPrefixExceedsMaxError {
393                limit: MAX_COMPACT_SIZE,
394                value: EXCESS_COMPACT_SIZE,
395            })),
396        ));
397    }
398
399    #[test]
400    fn compact_size_new_with_limit_values_too_large() {
401        use CompactSizeDecoderErrorInner as E;
402
403        // 240 should succeed for `new_with_limit` constructor
404        let mut decoder = CompactSizeDecoder::new_with_limit(240);
405        let _ = decoder.push_bytes(&mut [0xf0].as_slice()).unwrap();
406        let got = decoder.end().unwrap();
407        assert_eq!(got, 240);
408
409        // 241 should fail for `new_with_limit` constructor
410        let mut decoder = CompactSizeDecoder::new_with_limit(240);
411        let _ = decoder.push_bytes(&mut [0xf1].as_slice()).unwrap();
412        let got = decoder.end().unwrap_err();
413        assert!(matches!(
414            got,
415            CompactSizeDecoderError(E::ValueExceedsLimit(LengthPrefixExceedsMaxError {
416                limit: 240,
417                value: 241,
418            })),
419        ));
420    }
421}
bitcoin_consensus_encoding/compact_size.rs

bitcoin_consensus_encoding/
compact_size.rs
