Struct Nibbles

#[repr(C)]
pub struct Nibbles { /* private fields */ }

Structure representing a sequence of nibbles.

A nibble is a 4-bit value, and this structure is used to store the nibble sequence representing the keys in a Merkle Patricia Trie (MPT). Using nibbles simplifies trie operations and enables consistent key representation in the MPT.

Internal representation

The internal representation is currently a U256 that stores two nibbles per byte. Nibbles are stored inline (on the stack), and can be up to a length of 64 nibbles, or 32 unpacked bytes.

Additionally, a separate length field is stored to track the actual length of the nibble sequence. When the U256 is modified directly, the length field must be updated accordingly. Otherwise, the behavior is undefined.

Nibbles are stored with most significant bits set first, meaning that a nibble sequence 0x101 will be stored as 0x101...0, and not 0x0...101.

Examples

use nybbles::Nibbles;

let bytes = [0xAB, 0xCD];
let nibbles = Nibbles::unpack(&bytes);
assert_eq!(nibbles, Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]));
assert_eq!(nibbles.to_vec(), vec![0x0A, 0x0B, 0x0C, 0x0D]);

let packed = nibbles.pack();
assert_eq!(&packed[..], &bytes[..]);

Implementations

impl Nibbles

pub const fn new() -> Self

Creates a new empty Nibbles instance.

Examples

let nibbles = Nibbles::new();
assert_eq!(nibbles.len(), 0);

pub fn from_iter_unchecked<I>(iter: I) -> Self

where I: IntoIterator<Item = u8>,

Creates a new Nibbles instance from the given iterator over nibbles, without checking their validity.

Note that only the low nibble of every byte will be stored as a nibble, i.e. for 0x12 we will store a nibble 2.

For checked version, use the FromIterator implementation.

Examples

let nibbles = Nibbles::from_iter_unchecked([0x0A, 0x0B, 0x0C, 0x0D]);
assert_eq!(nibbles.to_vec(), vec![0x0A, 0x0B, 0x0C, 0x0D]);

pub fn from_nibbles<T: AsRef<[u8]>>(nibbles: T) -> Self

Creates a new Nibbles instance from the given nibbles.

Panics

Panics if the any of the bytes is not a valid nibble (0..=0x0f).

Examples

let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
assert_eq!(nibbles.to_vec(), vec![0x0A, 0x0B, 0x0C, 0x0D]);

Invalid values will cause panics:

let nibbles = Nibbles::from_nibbles(&[0xFF]);

pub fn from_nibbles_unchecked<T: AsRef<[u8]>>(nibbles: T) -> Self

Creates a new Nibbles instance from the given nibbles.

Note that only the low nibble of every byte will be stored as a nibble, i.e. for 0x12 we will store a nibble 2.

For checked version, use Nibbles::from_nibbles.

Examples

let nibbles = Nibbles::from_nibbles_unchecked(&[0x0A, 0x0B, 0x0C, 0x0D]);
assert_eq!(nibbles.to_vec(), vec![0x0A, 0x0B, 0x0C, 0x0D]);

Invalid values will not cause panics:

let nibbles = Nibbles::from_nibbles_unchecked(&[0xFF]);
assert_eq!(nibbles.to_vec(), vec![0x0F]);

pub fn unpack(data: impl AsRef<[u8]>) -> Self

Converts a byte slice into a Nibbles instance containing the nibbles (half-bytes or 4 bits) that make up the input byte data.

Panics

Panics if the length of the input is greater than 32 bytes.

Examples

let nibbles = Nibbles::unpack(&[0xAB, 0xCD]);
assert_eq!(nibbles.to_vec(), vec![0x0A, 0x0B, 0x0C, 0x0D]);

let nibbles = Nibbles::unpack(&[0xAB; 33]);

pub unsafe fn unpack_unchecked(data: &[u8]) -> Self

Converts a byte slice into a Nibbles instance containing the nibbles (half-bytes or 4 bits) that make up the input byte data.

Safety

The caller must ensure that the length of the input is less than or equal to the size of U256, which is 32 bytes.

Examples

// SAFETY: the length of the input is less than 32 bytes.
let nibbles = unsafe { Nibbles::unpack_unchecked(&[0xAB, 0xCD]) };
assert_eq!(nibbles.to_vec(), vec![0x0A, 0x0B, 0x0C, 0x0D]);

pub fn pack(&self) -> SmallVec<[u8; 32]>

Packs the nibbles into the given slice.

This method combines each pair of consecutive nibbles into a single byte, effectively reducing the size of the data by a factor of two.

If the number of nibbles is odd, the last nibble is shifted left by 4 bits and added to the packed byte vector.

Examples

let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C]);
assert_eq!(nibbles.pack()[..], [0xAB, 0xC0]);

pub fn pack_to(&self, out: &mut [u8])

Packs the nibbles into the given slice.

See pack for more information.

Panics

Panics if the slice is not at least (self.len() + 1) / 2 bytes long.

Examples

let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C]);
let mut packed = [0; 2];
nibbles.pack_to(&mut packed);
assert_eq!(packed[..], [0xAB, 0xC0]);

pub unsafe fn pack_to_unchecked(&self, ptr: *mut u8)

Packs the nibbles into the given pointer.

See pack for more information.

Safety

ptr must be valid for at least (self.len() + 1) / 2 bytes.

Examples

let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
let mut packed = [0; 2];
// SAFETY: enough capacity.
unsafe { nibbles.pack_to_unchecked(packed.as_mut_ptr()) };
assert_eq!(packed[..], [0xAB, 0xCD]);

pub unsafe fn pack_to_slice_unchecked(&self, out: &mut [MaybeUninit<u8>])

Packs the nibbles into the given slice without checking its length.

See pack for more information.

Safety

out must be valid for at least (self.len() + 1) / 2 bytes.

pub fn to_vec(&self) -> Vec<u8>

Converts the nibbles into a vector of nibbles.

Examples

let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
assert_eq!(nibbles.to_vec(), vec![0x0A, 0x0B, 0x0C, 0x0D]);

pub const fn iter(&self) -> NibblesIter<'_>

Returns an iterator over the nibbles.

Examples

let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
let collected: Vec<u8> = nibbles.iter().collect();
assert_eq!(collected, vec![0x0A, 0x0B, 0x0C, 0x0D]);

pub fn get_byte(&self, i: usize) -> Option<u8>

Gets the byte at the given index by combining two consecutive nibbles.

Examples

let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
assert_eq!(nibbles.get_byte(0), Some(0xAB));
assert_eq!(nibbles.get_byte(1), Some(0xBC));
assert_eq!(nibbles.get_byte(2), Some(0xCD));
assert_eq!(nibbles.get_byte(3), None);

pub fn get_byte_unchecked(&self, i: usize) -> u8

Gets the byte at the given index by combining two consecutive nibbles.

Panics

Panics if i..i + 1 is out of bounds.

Examples

let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
// SAFETY: in range.
unsafe {
    assert_eq!(nibbles.get_byte_unchecked(0), 0xAB);
    assert_eq!(nibbles.get_byte_unchecked(1), 0xBC);
    assert_eq!(nibbles.get_byte_unchecked(2), 0xCD);
}

pub fn increment(&self) -> Option<Self>

Increments the nibble sequence by one.

pub fn is_leaf(&self) -> bool

The last element of the hex vector is used to determine whether the nibble sequence represents a leaf or an extension node. If the last element is 0x10 (16), then it’s a leaf.

pub fn starts_with(&self, other: &Self) -> bool

Returns true if this nibble sequence starts with the given prefix.

pub fn ends_with(&self, other: &Self) -> bool

Returns true if this nibble sequence ends with the given suffix.

pub fn get(&self, i: usize) -> Option<u8>

Returns the nibble at the given index.

pub fn get_unchecked(&self, i: usize) -> u8

Returns the nibble at the given index.

Panics

Panics if the index is out of bounds.

pub fn set_at(&mut self, i: usize, value: u8)

Sets the nibble at the given index.

Panics

Panics if the index is out of bounds, or if value is not a valid nibble (0..=0x0f).

pub unsafe fn set_at_unchecked(&mut self, i: usize, value: u8)

Sets the nibble at the given index, without checking its validity.

Safety

The caller must ensure that the index is within bounds.

pub fn first(&self) -> Option<u8>

Returns the first nibble of this nibble sequence.

pub fn last(&self) -> Option<u8>

Returns the last nibble of this nibble sequence.

pub fn common_prefix_length(&self, other: &Self) -> usize

Returns the length of the common prefix between this nibble sequence and the given.

Examples

let a = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F]);
let b = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0E]);
assert_eq!(a.common_prefix_length(&b), 3);

pub const fn is_empty(&self) -> bool

Returns true if this Nibbles is empty.

pub const fn len(&self) -> usize

Returns the total number of nibbles in this Nibbles.

pub fn as_mut_uint_unchecked(&mut self) -> &mut U256

Returns a mutable reference to the underlying U256.

Note that it is possible to create invalid Nibbles instances using this method. See the type docs for more details.

pub fn slice_unchecked(&self, start: usize, end: usize) -> Self

Creates new nibbles containing the nibbles in the specified range [start, end) without checking bounds.

Safety

This method does not verify that the provided range is valid for this nibble sequence. The caller must ensure that start <= end and end <= self.len().

pub fn slice(&self, range: impl RangeBounds<usize>) -> Self

Creates new nibbles containing the nibbles in the specified range.

Panics

This method will panic if the range is out of bounds for this nibble sequence.

pub fn join(&self, other: &Self) -> Self

Join two nibble sequences together.

pub fn push(&mut self, nibble: u8)

Pushes a nibble to the end of the current nibbles.

Panics

Panics if the nibble is not a valid nibble (0..=0x0f).

pub fn push_unchecked(&mut self, nibble: u8)

Pushes a nibble to the end of the current nibbles without checking its validity.

Note that only the low nibble of the byte is used. For example, for byte 0x12, only the nibble 0x2 is pushed.

pub fn pop(&mut self) -> Option<u8>

Pops a nibble from the end of the current nibbles.

pub fn extend(&mut self, other: &Nibbles)

Extend the current nibbles with another nibbles.

pub fn extend_from_slice(&mut self, other: &[u8])

Extend the current nibbles with another byte slice.

pub fn extend_from_slice_unchecked(&mut self, other: &[u8])

Extend the current nibbles with another byte slice.

Caution

This method does not check if the resulting length would exceed the maximum capacity of Nibbles.

pub fn truncate(&mut self, new_len: usize)

Truncates the current nibbles to the given length.

pub fn clear(&mut self)

Clears the current nibbles.

Trait Implementations

impl Clone for Nibbles

fn clone(&self) -> Nibbles

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Nibbles

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Nibbles

fn default() -> Nibbles

Returns the “default value” for a type.

impl<'de> Deserialize<'de> for Nibbles

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl FromIterator<u8> for Nibbles

fn from_iter<T: IntoIterator<Item = u8>>(iter: T) -> Self

Creates a value from an iterator.

impl Hash for Nibbles

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl Ord for Nibbles

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for Nibbles

fn eq(&self, other: &Nibbles) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for Nibbles

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Serialize for Nibbles

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl Copy for Nibbles

impl Eq for Nibbles

impl StructuralPartialEq for Nibbles