#![doc = include_str!("../README.md")]
#![no_std]
#![cfg_attr(docsrs, feature(doc_cfg))]
#![cfg_attr(docsrs, allow(unused_attributes))]
#![deny(missing_docs)]
use core::{num::NonZeroU64, ops::RangeInclusive};
pub use char::*;
pub use duration::*;
mod char;
mod duration;
macro_rules! impl_varint {
($($ty:literal), +$(,)?) => {
$(
paste::paste! {
impl Varint for [< u $ty >] {
const MIN_ENCODED_LEN: usize = [< encoded_ u $ty _varint_len >](0);
const MAX_ENCODED_LEN: usize = [< encoded_ u $ty _varint_len >](<[< u $ty >]>::MAX);
#[inline]
fn encoded_len(&self) -> usize {
[< encoded_ u $ty _varint_len >](*self)
}
fn encode(&self, buf: &mut [u8]) -> Result<usize, EncodeError> {
[< encode_ u $ty _varint_to >](*self, buf)
}
#[inline]
fn decode(buf: &[u8]) -> Result<(usize, Self), DecodeError> {
[< decode_ u $ty _varint >](buf)
}
}
impl Varint for [< i $ty >] {
const MIN_ENCODED_LEN: usize = [< encoded_ i $ty _varint_len >](0);
const MAX_ENCODED_LEN: usize = [< encoded_ i $ty _varint_len >](<[< i $ty >]>::MAX);
#[inline]
fn encoded_len(&self) -> usize {
[< encoded_ i $ty _varint_len >](*self)
}
fn encode(&self, buf: &mut [u8]) -> Result<usize, EncodeError> {
[< encode_ i $ty _varint_to >](*self, buf)
}
#[inline]
fn decode(buf: &[u8]) -> Result<(usize, Self), DecodeError> {
[< decode_ i $ty _varint >](buf)
}
}
}
)*
};
}
macro_rules! decode_varint {
(|$buf:ident| $ty:ident) => {{
let mut result = 0;
let mut shift = 0;
let mut index = 0;
loop {
if index == $ty::MAX_ENCODED_LEN {
return Err(DecodeError::Overflow);
}
if index >= $buf.len() {
return Err(DecodeError::Underflow);
}
let next = $buf[index] as $ty;
let v = $ty::BITS as usize / 7 * 7;
let has_overflow = if shift < v {
false
} else if shift == v {
next & ((u8::MAX << (::core::mem::size_of::<$ty>() % 7)) as $ty) != 0
} else {
true
};
if has_overflow {
return Err(DecodeError::Overflow);
}
result += (next & 0x7F) << shift;
if next & 0x80 == 0 {
break;
}
shift += 7;
index += 1;
}
Ok((index + 1, result))
}};
}
macro_rules! encode_varint {
($buf:ident[$x:ident]) => {{
let mut i = 0;
while $x >= 0x80 {
if i >= $buf.len() {
panic!("insufficient buffer capacity");
}
$buf[i] = ($x as u8) | 0x80;
$x >>= 7;
i += 1;
}
if i >= $buf.len() {
panic!("insufficient buffer capacity");
}
$buf[i] = $x as u8;
i + 1
}};
(@to_buf $ty:ident::$buf:ident[$x:ident]) => {{
paste::paste! {
let mut i = 0;
let orig = $x;
while $x >= 0x80 {
if i >= $buf.len() {
return Err(EncodeError::underflow([< encoded_ $ty _varint_len >](orig), $buf.len()));
}
$buf[i] = ($x as u8) | 0x80;
$x >>= 7;
i += 1;
}
if i >= $buf.len() {
return Err(EncodeError::underflow(i + 1, $buf.len()));
}
$buf[i] = $x as u8;
Ok(i + 1)
}
}};
}
macro_rules! varint_len {
($($ty:ident),+$(,)?) => {
$(
paste::paste! {
#[doc = "The returned value will be in range of [`" $ty "::ENCODED_LEN_RANGE`]."]
#[inline]
pub const fn [< encoded_ $ty _varint_len >](value: $ty) -> usize {
encoded_u64_varint_len(value as u64)
}
}
)*
};
(@zigzag $($ty:ident),+$(,)?) => {
$(
paste::paste! {
#[doc = "The returned value will be in range of [`" $ty "::ENCODED_LEN_RANGE`]."]
#[inline]
pub const fn [< encoded_ $ty _varint_len >](value: $ty) -> usize {
encoded_i64_varint_len(value as i64)
}
}
)*
};
}
macro_rules! buffer {
($($ty:ident), +$(,)?) => {
$(
paste::paste! {
#[doc = "A buffer for storing LEB128 encoded " $ty " values."]
#[derive(Copy, Clone, Eq)]
pub struct [< $ty:camel VarintBuffer >]([u8; $ty::MAX_ENCODED_LEN + 1]);
impl core::fmt::Debug for [< $ty:camel VarintBuffer >] {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
self.0[..self.len()].fmt(f)
}
}
impl PartialEq for [< $ty:camel VarintBuffer >] {
fn eq(&self, other: &Self) -> bool {
self.as_bytes().eq(other.as_bytes())
}
}
impl core::hash::Hash for [< $ty:camel VarintBuffer >] {
fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
self.as_bytes().hash(state)
}
}
impl [< $ty:camel VarintBuffer >] {
const LAST_INDEX: usize = $ty::MAX_ENCODED_LEN;
#[allow(dead_code)]
#[inline]
const fn new(mut val: $ty) -> Self {
let mut buf = [0; $ty::MAX_ENCODED_LEN + 1];
let mut_buf = &mut buf;
let len = encode_varint!(mut_buf[val]);
buf[Self::LAST_INDEX] = len as u8;
Self(buf)
}
#[inline]
#[allow(clippy::len_without_is_empty)]
pub const fn len(&self) -> usize {
self.0[Self::LAST_INDEX] as usize
}
#[inline]
pub const fn as_bytes(&self) -> &[u8] {
self.0.split_at(self.len()).0
}
}
impl core::ops::Deref for [< $ty:camel VarintBuffer >] {
type Target = [u8];
fn deref(&self) -> &Self::Target {
&self.0[..self.len()]
}
}
impl core::borrow::Borrow<[u8]> for [< $ty:camel VarintBuffer >] {
fn borrow(&self) -> &[u8] {
self
}
}
impl AsRef<[u8]> for [< $ty:camel VarintBuffer >] {
fn as_ref(&self) -> &[u8] {
self
}
}
}
)*
};
}
macro_rules! encode {
($($ty:literal), +$(,)?) => {
$(
paste::paste! {
#[doc = "Encodes an `u" $ty "` value into LEB128 variable length format, and writes it to the buffer."]
#[inline]
pub const fn [< encode_ u $ty _varint >](x: [< u $ty >]) -> [< U $ty:camel VarintBuffer >] {
[< U $ty:camel VarintBuffer >]::new(x)
}
#[doc = "Encodes an `i" $ty "` value into LEB128 variable length format, and writes it to the buffer."]
#[inline]
pub const fn [< encode_ i $ty _varint >](x: [< i $ty >]) -> [< I $ty:camel VarintBuffer >] {
let x = (x << 1) ^ (x >> ($ty - 1)); [< I $ty:camel VarintBuffer >]([< U $ty:camel VarintBuffer >]::new(x as [< u $ty >]).0)
}
#[doc = "Encodes an `u" $ty "` value into LEB128 variable length format, and writes it to the buffer."]
#[inline]
pub const fn [< encode_ u $ty _varint_to >](mut x: [< u $ty >], buf: &mut [u8]) -> Result<usize, EncodeError> {
encode_varint!(@to_buf [< u $ty >]::buf[x])
}
#[doc = "Encodes an `i" $ty "` value into LEB128 variable length format, and writes it to the buffer."]
#[inline]
pub const fn [< encode_ i $ty _varint_to >](x: [< i $ty >], buf: &mut [u8]) -> Result<usize, EncodeError> {
let mut x = {
((x << 1) ^ (x >> ($ty - 1))) as [< u $ty >]
};
encode_varint!(@to_buf [<u $ty>]::buf[x])
}
}
)*
};
}
macro_rules! decode {
($($ty:literal), + $(,)?) => {
$(
paste::paste! {
#[doc = "Decodes an `i" $ty "` in LEB128 encoded format from the buffer."]
pub const fn [< decode_ u $ty _varint >](buf: &[u8]) -> Result<(usize, [< u $ty >]), DecodeError> {
decode_varint!(|buf| [< u $ty >])
}
#[doc = "Decodes an `u" $ty "` in LEB128 encoded format from the buffer."]
pub const fn [< decode_ i $ty _varint >](buf: &[u8]) -> Result<(usize, [< i $ty >]), DecodeError> {
match [< decode_ u $ty _varint >](buf) {
Ok((bytes_read, value)) => {
let value = ((value >> 1) as [< i $ty >]) ^ { -((value & 1) as [< i $ty >]) }; Ok((bytes_read, value))
},
Err(e) => Err(e),
}
}
}
)*
};
}
impl_varint!(8, 16, 32, 64, 128,);
varint_len!(u8, u16, u32,);
varint_len!(@zigzag i8, i16, i32,);
buffer!(u8, u16, u32, u64, u128, i16, i32, i64, i128);
encode!(128, 64, 32, 16);
decode!(128, 64, 32, 16, 8);
#[doc = "Encodes an `u8` value into LEB128 variable length format, and writes it to the buffer."]
#[inline]
pub const fn encode_u8_varint_to(mut x: u8, buf: &mut [u8]) -> Result<usize, EncodeError> {
encode_varint!(@to_buf u8::buf[x])
}
#[doc = "Encodes an `i8` value into LEB128 variable length format, and writes it to the buffer."]
#[inline]
pub const fn encode_i8_varint_to(orig: i8, buf: &mut [u8]) -> Result<usize, EncodeError> {
let mut n = {
((orig << 1) ^ (orig >> 7)) as u8
};
let mut i = 0;
while n > 0x7F {
if i >= buf.len() {
return Err(EncodeError::underflow(
encoded_i8_varint_len(orig),
buf.len(),
));
}
buf[i] = (n & 0x7F) | 0x80;
i += 1;
n >>= 7;
}
if i >= buf.len() {
return Err(EncodeError::underflow(i + 1, buf.len()));
}
buf[i] = n;
Ok(i + 1)
}
#[doc = "Encodes an `u8` value into LEB128 variable length format, and writes it to the buffer."]
#[inline]
pub const fn encode_u8_varint(x: u8) -> U8VarintBuffer {
U8VarintBuffer::new(x)
}
#[doc = "Encodes an `i8` value into LEB128 variable length format, and writes it to the buffer."]
#[inline]
pub const fn encode_i8_varint(x: i8) -> I8VarintBuffer {
let x = (x << 1) ^ (x >> (8 - 1)); I8VarintBuffer(U8VarintBuffer::new(x as u8).0)
}
pub trait Varint {
const MIN_ENCODED_LEN: usize;
const MAX_ENCODED_LEN: usize;
const ENCODED_LEN_RANGE: RangeInclusive<usize> = Self::MIN_ENCODED_LEN..=Self::MAX_ENCODED_LEN;
fn encoded_len(&self) -> usize;
fn encode(&self, buf: &mut [u8]) -> Result<usize, EncodeError>;
fn decode(buf: &[u8]) -> Result<(usize, Self), DecodeError>
where
Self: Sized;
}
#[inline]
pub const fn encoded_u128_varint_len(value: u128) -> usize {
if value < 128 {
return 1;
}
let highest_bit = 128 - value.leading_zeros();
highest_bit.div_ceil(7) as usize
}
#[inline]
pub const fn encoded_i128_varint_len(x: i128) -> usize {
let x = (x << 1) ^ (x >> 127); encoded_u128_varint_len(x as u128)
}
#[inline]
pub const fn encoded_i64_varint_len(x: i64) -> usize {
let x = (x << 1) ^ (x >> 63); encoded_u64_varint_len(x as u64)
}
#[inline]
pub const fn encoded_u64_varint_len(value: u64) -> usize {
let log2value = unsafe { NonZeroU64::new_unchecked(value | 1) }.ilog2();
((log2value * 9 + (64 + 9)) / 64) as usize
}
pub const fn consume_varint(buf: &[u8]) -> Result<usize, DecodeError> {
if buf.is_empty() {
return Ok(0);
}
let mut idx = 0;
let buf_len = buf.len();
while idx < buf_len {
let byte = buf[idx];
if byte & 0x80 == 0 {
return Ok(idx + 1);
}
if idx == buf_len - 1 {
return Err(DecodeError::Underflow);
}
idx += 1;
}
Err(DecodeError::Underflow)
}
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, thiserror::Error)]
#[non_exhaustive]
pub enum EncodeError {
#[error("buffer does not have enough capacity to encode the value")]
Underflow {
required: usize,
remaining: usize,
},
#[error("{0}")]
Custom(&'static str),
}
impl EncodeError {
#[inline]
pub const fn underflow(required: usize, remaining: usize) -> Self {
Self::Underflow {
required,
remaining,
}
}
#[inline]
pub const fn custom(msg: &'static str) -> Self {
Self::Custom(msg)
}
}
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, thiserror::Error)]
#[non_exhaustive]
pub enum DecodeError {
#[error("value would overflow the target type")]
Overflow,
#[error("buffer does not contain enough data to decode a value")]
Underflow,
#[error("{0}")]
Custom(&'static str),
}
impl DecodeError {
#[inline]
pub const fn custom(msg: &'static str) -> Self {
Self::Custom(msg)
}
}
#[derive(Clone, Copy, PartialEq, Eq)]
pub struct I8VarintBuffer([u8; i8::MAX_ENCODED_LEN + 1]);
impl core::fmt::Debug for I8VarintBuffer {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
self.0[..self.len()].fmt(f)
}
}
impl I8VarintBuffer {
const LAST_INDEX: usize = i8::MAX_ENCODED_LEN;
#[allow(dead_code)]
#[inline]
const fn new(val: i8) -> Self {
let mut buf = [0; i8::MAX_ENCODED_LEN + 1];
let mut_buf = &mut buf;
let len = {
let mut n = {
((val << 1) ^ (val >> 7)) as u8
};
let mut i = 0;
while n > 0x7F {
if i >= mut_buf.len() {
panic!("insufficient buffer capacity");
}
mut_buf[i] = (n & 0x7F) | 0x80;
i += 1;
n >>= 7;
}
if i >= mut_buf.len() {
panic!("insufficient buffer capacity");
}
mut_buf[i] = n;
i + 1
};
buf[Self::LAST_INDEX] = len as u8;
Self(buf)
}
#[inline]
#[allow(clippy::len_without_is_empty)]
pub const fn len(&self) -> usize {
self.0[Self::LAST_INDEX] as usize
}
#[inline]
pub const fn as_bytes(&self) -> &[u8] {
self.0.split_at(self.len()).0
}
}
impl core::ops::Deref for I8VarintBuffer {
type Target = [u8];
fn deref(&self) -> &Self::Target {
&self.0[..self.len()]
}
}
impl core::borrow::Borrow<[u8]> for I8VarintBuffer {
fn borrow(&self) -> &[u8] {
self
}
}
impl AsRef<[u8]> for I8VarintBuffer {
fn as_ref(&self) -> &[u8] {
self
}
}
mod non_zero;
#[cfg(feature = "ruint_1")]
mod ruint_impl;
#[cfg(feature = "arbitrary-int_1")]
#[cfg_attr(docsrs, doc(cfg(feature = "arbitrary-int")))]
pub mod arbitrary_int;
#[cfg(feature = "primitive-types_0_13")]
mod primitive_types;
#[cfg(feature = "ethereum-types_0_15")]
mod ethereum_types;
#[cfg(test)]
mod tests {
extern crate std;
use super::*;
fn check(value: u64, encoded: &[u8]) {
let a = encode_u64_varint(value);
assert_eq!(a.as_ref(), encoded);
assert_eq!(a.len(), encoded.len());
assert_eq!(a.len(), encoded_u64_varint_len(value));
let (read, decoded) = decode_u64_varint(&a).unwrap();
assert_eq!(decoded, value);
assert_eq!(read, encoded.len());
assert_eq!(a.len(), encoded_u64_varint_len(value));
}
#[test]
fn roundtrip_u64() {
check(2u64.pow(0) - 1, &[0x00]);
check(2u64.pow(0), &[0x01]);
check(2u64.pow(7) - 1, &[0x7F]);
check(2u64.pow(7), &[0x80, 0x01]);
check(300u64, &[0xAC, 0x02]);
check(2u64.pow(14) - 1, &[0xFF, 0x7F]);
check(2u64.pow(14), &[0x80, 0x80, 0x01]);
check(2u64.pow(21) - 1, &[0xFF, 0xFF, 0x7F]);
check(2u64.pow(21), &[0x80, 0x80, 0x80, 0x01]);
check(2u64.pow(28) - 1, &[0xFF, 0xFF, 0xFF, 0x7F]);
check(2u64.pow(28), &[0x80, 0x80, 0x80, 0x80, 0x01]);
check(2u64.pow(35) - 1, &[0xFF, 0xFF, 0xFF, 0xFF, 0x7F]);
check(2u64.pow(35), &[0x80, 0x80, 0x80, 0x80, 0x80, 0x01]);
check(2u64.pow(42) - 1, &[0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x7F]);
check(2u64.pow(42), &[0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x01]);
check(
2u64.pow(49) - 1,
&[0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x7F],
);
check(
2u64.pow(49),
&[0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x01],
);
check(
2u64.pow(56) - 1,
&[0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x7F],
);
check(
2u64.pow(56),
&[0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x01],
);
check(
2u64.pow(63) - 1,
&[0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x7F],
);
check(
2u64.pow(63),
&[0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x01],
);
check(
u64::MAX,
&[0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x01],
);
}
#[test]
fn test_large_number_encode_decode() {
let original = 30000u64;
let encoded = encode_u64_varint(original);
let (bytes_read, decoded) = decode_u64_varint(&encoded).unwrap();
assert_eq!(original, decoded);
assert_eq!(bytes_read, encoded.len());
}
#[test]
fn test_decode_overflow_error() {
let buffer = [0x80u8; 11]; match decode_u64_varint(&buffer) {
Err(DecodeError::Overflow) => (),
_ => panic!("Expected Overflow error"),
}
let buffer = [0x80u8; 6]; match decode_u32_varint(&buffer) {
Err(DecodeError::Overflow) => (),
_ => panic!("Expected Overflow error"),
}
let buffer = [0x80u8; 4]; match decode_u16_varint(&buffer) {
Err(DecodeError::Overflow) => (),
_ => panic!("Expected Overflow error"),
}
}
fn test_zigzag_encode_decode<T>(value: T)
where
T: Copy
+ PartialEq
+ core::fmt::Debug
+ core::ops::Shl<Output = T>
+ core::ops::Shr<Output = T>
+ Into<i64>
+ core::convert::TryInto<usize>
+ core::convert::TryFrom<usize>,
{
let encoded = encode_i64_varint(value.into());
let bytes_written = encoded.len();
let decode_result = decode_i64_varint(&encoded);
assert!(decode_result.is_ok(), "Decoding failed");
let (decoded_bytes, decoded_value) = decode_result.unwrap();
assert_eq!(
decoded_bytes, bytes_written,
"Incorrect number of bytes decoded"
);
assert_eq!(
decoded_value,
value.into(),
"Decoded value does not match original"
);
}
#[test]
fn test_zigzag_encode_decode_i8() {
let values = [-1, 0, 1, -100, 100, i8::MIN, i8::MAX];
for &value in &values {
test_zigzag_encode_decode(value);
}
}
#[test]
fn test_zigzag_encode_decode_i16() {
let values = [-1, 0, 1, -100, 100, i16::MIN, i16::MAX];
for &value in &values {
test_zigzag_encode_decode(value);
}
}
#[test]
fn test_zigzag_encode_decode_i32() {
let values = [-1, 0, 1, -10000, 10000, i32::MIN, i32::MAX];
for &value in &values {
test_zigzag_encode_decode(value);
}
}
#[test]
fn test_zigzag_encode_decode_i64() {
let values = [-1, 0, 1, -1000000000, 1000000000, i64::MIN, i64::MAX];
for &value in &values {
test_zigzag_encode_decode(value);
}
}
}
#[cfg(test)]
mod fuzzy {
use super::*;
use quickcheck_macros::quickcheck;
macro_rules! fuzzy {
($($ty:ty), +$(,)?) => {
$(
paste::paste! {
#[quickcheck]
fn [< fuzzy_ $ty >](value: $ty) -> bool {
let encoded = [< encode_ $ty _varint >](value);
if encoded.len() != [< encoded_ $ty _varint_len >] (value) || !(encoded.len() <= <$ty>::MAX_ENCODED_LEN) {
return false;
}
let Ok(consumed) = consume_varint(&encoded) else {
return false;
};
if consumed != encoded.len() {
return false;
}
if let Ok((bytes_read, decoded)) = [< decode_ $ty _varint >](&encoded) {
value == decoded && encoded.len() == bytes_read
} else {
false
}
}
#[quickcheck]
fn [< fuzzy_ $ty _varint>](value: $ty) -> bool {
let mut buf = [0; <$ty>::MAX_ENCODED_LEN];
let Ok(encoded_len) = value.encode(&mut buf) else { return false; };
if encoded_len != value.encoded_len() || !(value.encoded_len() <= <$ty>::MAX_ENCODED_LEN) {
return false;
}
let Ok(consumed) = consume_varint(&buf) else {
return false;
};
if consumed != encoded_len {
return false;
}
if let Ok((bytes_read, decoded)) = <$ty>::decode(&buf) {
value == decoded && encoded_len == bytes_read
} else {
false
}
}
}
)*
};
}
fuzzy!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128);
#[cfg(feature = "std")]
mod with_std {
use super::*;
extern crate std;
use std::{vec, vec::Vec};
#[quickcheck]
fn fuzzy_buffer_underflow(value: u64, short_len: usize) -> bool {
let short_len = short_len % 9; if short_len >= value.encoded_len() {
return true; }
let mut short_buffer = vec![0u8; short_len];
matches!(
value.encode(&mut short_buffer),
Err(EncodeError::Underflow { .. })
)
}
#[quickcheck]
fn fuzzy_invalid_sequences(bytes: Vec<u8>) -> bool {
if bytes.is_empty() {
return matches!(decode_u64_varint(&bytes), Err(DecodeError::Underflow));
}
if bytes.len() > 10 {
return true;
}
if bytes.iter().all(|b| b & 0x80 != 0) {
return matches!(decode_u64_varint(&bytes), Err(DecodeError::Underflow));
}
match decode_u64_varint(&bytes) {
Ok(_) => true,
Err(_) => true,
}
}
}
}