class_groups/crypto_bigint/encoding/compressed/
varint.rs

1//! Simple and efficient encoding of variably-sized integers
2//!
3//! This encoding is little-endian, appending the seven _least_-significant bits to a byte vector,
4//! until the remaining bits are zero. The eight bit is reserved to mark whether or not the
5//! encoding continues.
6//!
7//! ```py
8//! VARINT_VALUE_MASK = (1 << 7) - 1
9//! fn encode_varint(value) {
10//!   if value == 0 {
11//!     return [0]
12//!   }
13//!
14//!   result = []
15//!   while value != 0 {
16//!     next_byte = value & VARINT_VALUE_MASK
17//!     value >>= 7
18//!     next_byte |= (value != 0) << 7
19//!     result.push(next_byte)
20//!   }
21//!   return result
22//! }
23//!
24//! fn decode_varint(bytestream) {
25//!   result = 0
26//!   i = 0
27//!   while true {
28//!     next_byte = bytestream.next_byte()
29//!     result |= (next_byte & VARINT_VALUE_MASK) << i
30//!     if (next_byte >> 7) == 0 {
31//!       # Check this was canonical, without unnecessary extra bytes
32//!       assert (i == 0) || (next_byte != 0)
33//!       return result
34//!     }
35//!     i += 7
36//!   }
37//! }
38//! ```
39//!
40//! Implementations MUST ensure that `(next_byte & mask) << i` DOES NOT shift any set bits past
41//! the boundary of the container. Implementations SHOULD terminate early if `i` exceeds the
42//! bit-length of the container (as either a bit will overflow the container, or the final byte
43//! will be zero and therefore the number is non-canonically encoded, either case being invalid).
44
45use alloc::{vec::Vec, vec};
46
47#[cfg(feature = "std")]
48use std::io;
49
50use super::Error;
51
52const VARINT_VALUE_MASK: u8 = (1 << 7) - 1;
53
54/// This function runs in time variable to the input.
55pub(super) fn encode_varint(mut value: usize) -> Vec<u8> {
56  if value == 0 {
57    return vec![0];
58  }
59
60  let mut result = vec![];
61  while value != 0 {
62    let mut next_byte = u8::try_from(value & usize::from(VARINT_VALUE_MASK)).unwrap();
63    value >>= 7;
64    next_byte |= u8::from(value != 0) << 7;
65    result.push(next_byte);
66  }
67
68  result
69}
70
71/// This function runs in time variable to the input.
72pub(super) fn decode_varint(mut reader: impl io::Read) -> Result<usize, Error> {
73  let mut result = 0;
74  let mut i = 0;
75  while i < usize::BITS {
76    let mut next_byte = [0xff];
77    reader.read_exact(&mut next_byte).map_err(|_| Error::UnexpectedEof)?;
78    let next_byte = next_byte[0];
79
80    let to_shift = next_byte & VARINT_VALUE_MASK;
81    {
82      let bits_remaining = usize::BITS - i;
83      if let Some(expected_not_set_bits) = u8::BITS.checked_sub(bits_remaining) {
84        if to_shift.leading_zeros() < expected_not_set_bits {
85          Err(Error::Overflow)?;
86        }
87      }
88    }
89
90    result |= usize::from(to_shift) << i;
91
92    if (next_byte >> 7) == 0 {
93      if (next_byte == 0) && (i != 0) {
94        Err(Error::NonCanonical)?;
95      }
96      return Ok(result);
97    }
98
99    i += 7;
100  }
101  Err(Error::Overflow)
102}
103
104#[test]
105fn varint() {
106  use rand::Rng as _;
107  let mut rng = rand::rand_core::UnwrapErr(rand::rngs::SysRng);
108
109  let test = |value| {
110    let encoding = encode_varint(value);
111    {
112      let mut encoding = encoding.as_slice();
113      assert_eq!(decode_varint(&mut encoding).unwrap(), value);
114      assert!(encoding.is_empty());
115    }
116    encoding
117  };
118
119  assert_eq!(test(0), vec![0]);
120  assert_eq!(test(1), vec![1]);
121  assert_eq!(test(usize::from(u8::MAX >> 1)), vec![u8::MAX >> 1]);
122  assert_eq!(test(usize::from((u8::MAX >> 1) + 1)), vec![(1 << 7), 1]);
123
124  for _ in 0 .. 256 {
125    #[expect(clippy::as_conversions, clippy::cast_possible_truncation)]
126    test(rng.next_u64() as usize);
127  }
128
129  // TODO: Test error cases
130}
class_groups/crypto_bigint/encoding/compressed/varint.rs

class_groups/crypto_bigint/encoding/compressed/
varint.rs
