monero_io/
varint.rs

1//! Monero's VarInt type, frequently used to encode integers expected to be of low norm.
2//!
3//! This corresponds to
4//! https://github.com/monero-project/monero/blob/8e9ab9677f90492bca3c7555a246f2a8677bd570
5//!   /src/common/varint.h.
6
7#[allow(unused_imports)]
8use std_shims::prelude::*;
9use std_shims::io::{self, Read, Write};
10
11use crate::{read_byte, write_byte};
12
13const VARINT_CONTINUATION_FLAG: u8 = 0b1000_0000;
14const VARINT_VALUE_MASK: u8 = !VARINT_CONTINUATION_FLAG;
15
16mod sealed {
17  /// A seal to prevent implementing `VarInt` on foreign types.
18  pub trait Sealed {
19    /// Lossless, guaranteed conversion into a `u64`.
20    ///
21    /// This is due to internally implementing encoding for `u64` alone and `usize` not implementing
22    /// `From<u64>`.
23    // This is placed here so it's not within our public API commitment.
24    fn into_u64(self) -> u64;
25  }
26}
27
28/// Compute the upper bound for the encoded length of a integer type as a VarInt.
29///
30/// This is a private function only called at compile-time, hence why it panics on unexpected
31/// input.
32#[allow(clippy::cast_possible_truncation)]
33const fn upper_bound(bits: u32) -> usize {
34  // This assert ensures the following cast is correct even on 8-bit platforms
35  assert!(bits <= 256, "defining a number exceeding u256 as a VarInt");
36  // Manually implement `div_ceil` as it was introduced with 1.73 and `std-shims` cannot provide
37  // a `const fn` shim due to using a trait to provide this as a method
38  ((bits + (7 - 1)) / 7) as usize
39}
40
41/// A trait for a number readable/writable as a VarInt.
42///
43/// This is sealed to prevent unintended implementations. It MUST only be implemented for primitive
44/// types (or sufficiently approximate types like `NonZero<_>`).
45pub trait VarInt: TryFrom<u64> + Copy + sealed::Sealed {
46  /// The lower bound on the amount of bytes this will take up when encoded.
47  const LOWER_BOUND: usize;
48
49  /// The upper bound on the amount of bytes this will take up when encoded.
50  const UPPER_BOUND: usize;
51
52  /// The amount of bytes this number will take when serialized as a VarInt.
53  fn varint_len(self) -> usize {
54    let varint_u64 = self.into_u64();
55    usize::try_from(u64::BITS - varint_u64.leading_zeros()).expect("64 > usize::MAX?").div_ceil(7)
56  }
57
58  /// Read a canonically-encoded VarInt.
59  fn read<R: Read>(r: &mut R) -> io::Result<Self> {
60    let mut bits = 0;
61    let mut res = 0;
62    while {
63      let b = read_byte(r)?;
64      // Reject trailing zero bytes
65      // https://github.com/monero-project/monero/blob/8e9ab9677f90492bca3c7555a246f2a8677bd570
66      //   /src/common/varint.h#L107
67      if (bits != 0) && (b == 0) {
68        Err(io::Error::other("non-canonical varint"))?;
69      }
70
71      // We use `size_of` here as we control what `VarInt` is implemented for, and it's only for
72      // types whose size correspond to their range
73      #[allow(non_snake_case)]
74      let U_BITS = core::mem::size_of::<Self>() * 8;
75      if ((bits + 7) >= U_BITS) && (b >= (1 << (U_BITS - bits))) {
76        Err(io::Error::other("varint overflow"))?;
77      }
78
79      res += u64::from(b & VARINT_VALUE_MASK) << bits;
80      bits += 7;
81      (b & VARINT_CONTINUATION_FLAG) == VARINT_CONTINUATION_FLAG
82    } {}
83    res.try_into().map_err(|_| io::Error::other("VarInt does not fit into integer type"))
84  }
85
86  /// Encode a number as a VarInt.
87  ///
88  /// This doesn't accept `self` to force writing it as `VarInt::write`, making it clear it's being
89  /// written with the VarInt encoding.
90  fn write<W: Write>(varint: &Self, w: &mut W) -> io::Result<()> {
91    let mut varint: u64 = varint.into_u64();
92
93    // A do-while loop as we always encode at least one byte
94    while {
95      // Take the next seven bits
96      let mut b = u8::try_from(varint & u64::from(VARINT_VALUE_MASK))
97        .expect("& 0b0111_1111 left more than 8 bits set");
98      varint >>= 7;
99
100      // If there's more, set the continuation flag
101      if varint != 0 {
102        b |= VARINT_CONTINUATION_FLAG;
103      }
104
105      // Write this byte
106      write_byte(&b, w)?;
107
108      // Continue until the number is fully encoded
109      varint != 0
110    } {}
111
112    Ok(())
113  }
114}
115
116impl sealed::Sealed for u8 {
117  fn into_u64(self) -> u64 {
118    self.into()
119  }
120}
121impl VarInt for u8 {
122  const LOWER_BOUND: usize = 1;
123  const UPPER_BOUND: usize = upper_bound(Self::BITS);
124}
125
126impl sealed::Sealed for u32 {
127  fn into_u64(self) -> u64 {
128    self.into()
129  }
130}
131impl VarInt for u32 {
132  const LOWER_BOUND: usize = 1;
133  const UPPER_BOUND: usize = upper_bound(Self::BITS);
134}
135
136impl sealed::Sealed for u64 {
137  fn into_u64(self) -> u64 {
138    self
139  }
140}
141impl VarInt for u64 {
142  const LOWER_BOUND: usize = 1;
143  const UPPER_BOUND: usize = upper_bound(Self::BITS);
144}
145
146impl sealed::Sealed for usize {
147  fn into_u64(self) -> u64 {
148    // Ensure the falling conversion is infallible
149    const _NO_128_BIT_PLATFORMS: [(); (u64::BITS - usize::BITS) as usize] =
150      [(); (u64::BITS - usize::BITS) as usize];
151
152    self.try_into().expect("compiling on platform with <64-bit usize yet value didn't fit in u64")
153  }
154}
155impl VarInt for usize {
156  const LOWER_BOUND: usize = 1;
157  const UPPER_BOUND: usize = upper_bound(Self::BITS);
158}
monero_io/varint.rs

monero_io/
varint.rs
