[go: up one dir, main page]
Skip to content

Commit

Permalink
chore: remove path encoding (#12)
Browse files Browse the repository at this point in the history 
* chore: remove path encoding

* bump msrv
  • Loading branch information
@rkrasiuk
rkrasiuk authored May 17, 2024
1 parent 25e897f commit 602543c
Show file tree
Hide file tree
Showing 5 changed files with 5 additions and 133 deletions.
6 changes: 3 additions & 3 deletions .github/workflows/ci.yml
View file
Original file line number Diff line number Diff line change
Expand Up @@ -23,7 +23,7 @@ jobs:
fail-fast: false
matrix:
target: [aarch64-unknown-linux-gnu, i686-unknown-linux-gnu, x86_64-unknown-linux-gnu]
rust: [nightly, stable, 1.64] # MSRV
rust: [nightly, stable, 1.66] # MSRV
timeout-minutes: 30
steps:
- uses: actions/checkout@v4
Expand All @@ -43,10 +43,10 @@ jobs:

- run: cargo build
- run: cargo test
if: matrix.rust != '1.64' # MSRV
if: matrix.rust != '1.66' # MSRV
- run: cargo build --no-default-features
- run: cargo test --tests --no-default-features
if: matrix.rust != '1.64' # MSRV
if: matrix.rust != '1.66' # MSRV

miri:
name: Miri
Expand Down
2 changes: 1 addition & 1 deletion Cargo.toml
View file
Original file line number Diff line number Diff line change
Expand Up @@ -4,7 +4,7 @@ version = "0.2.1"
authors = ["DaniPopes <57450786+DaniPopes@users.noreply.github.com>"]
description = "Efficient nibble-sized (4-bit) byte sequence data structure"
edition = "2021"
rust-version = "1.64"
rust-version = "1.66"
license = "MIT OR Apache-2.0"
categories = ["data-structures", "no-std"]
keywords = ["nibbles", "vector", "ethereum"]
Expand Down
12 changes: 0 additions & 12 deletions benches/bench.rs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -46,18 +46,6 @@ pub fn nibbles_benchmark(c: &mut Criterion) {
});
}
}

{
let mut g = group(c, "encode_path_leaf");
for len in lengths {
g.throughput(criterion::Throughput::Bytes(len));
let id = criterion::BenchmarkId::new("nybbles", len);
g.bench_function(id, |b| {
let nibbles = get_nibbles(len as usize);
b.iter(|| black_box(&nibbles).encode_path_leaf(false))
});
}
}
}

fn group<'c>(c: &'c mut Criterion, name: &str) -> BenchmarkGroup<'c, WallTime> {
Expand Down
2 changes: 1 addition & 1 deletion clippy.toml
View file
Original file line number Diff line number Diff line change
@@ -1 +1 @@
msrv = "1.64"
msrv = "1.66"
116 changes: 0 additions & 116 deletions src/nibbles.rs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -544,87 +544,6 @@ impl Nibbles {
(hi << 4) | lo
}

/// Encodes a given path leaf as a compact array of bytes, where each byte represents two
/// "nibbles" (half-bytes or 4 bits) of the original hex data, along with additional information
/// about the leaf itself.
///
/// The method takes the following input:
/// `is_leaf`: A boolean value indicating whether the current node is a leaf node or not.
///
/// The first byte of the encoded vector is set based on the `is_leaf` flag and the parity of
/// the hex data length (even or odd number of nibbles).
/// - If the node is an extension with even length, the header byte is `0x00`.
/// - If the node is an extension with odd length, the header byte is `0x10 + <first nibble>`.
/// - If the node is a leaf with even length, the header byte is `0x20`.
/// - If the node is a leaf with odd length, the header byte is `0x30 + <first nibble>`.
///
/// If there is an odd number of nibbles, store the first nibble in the lower 4 bits of the
/// first byte of encoded.
///
/// # Returns
///
/// A vector containing the compact byte representation of the nibble sequence, including the
/// header byte.
///
/// This vector's length is `self.len() / 2 + 1`. For stack-allocated nibbles, this is at most
/// 33 bytes, so 36 was chosen as the stack capacity to round up to the next usize-aligned
/// size.
///
/// # Examples
///
/// ```
/// # use nybbles::Nibbles;
/// // Extension node with an even path length:
/// let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
/// assert_eq!(nibbles.encode_path_leaf(false)[..], [0x00, 0xAB, 0xCD]);
///
/// // Extension node with an odd path length:
/// let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C]);
/// assert_eq!(nibbles.encode_path_leaf(false)[..], [0x1A, 0xBC]);
///
/// // Leaf node with an even path length:
/// let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
/// assert_eq!(nibbles.encode_path_leaf(true)[..], [0x20, 0xAB, 0xCD]);
///
/// // Leaf node with an odd path length:
/// let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C]);
/// assert_eq!(nibbles.encode_path_leaf(true)[..], [0x3A, 0xBC]);
/// ```
#[inline]
pub fn encode_path_leaf(&self, is_leaf: bool) -> SmallVec<[u8; 36]> {
let encoded_len = self.len() / 2 + 1;
let mut encoded = SmallVec::with_capacity(encoded_len);
// SAFETY: enough capacity.
unsafe { self.encode_path_leaf_to(is_leaf, encoded.as_mut_ptr()) };
// SAFETY: within capacity and `encode_path_leaf_to` initialized the memory.
unsafe { encoded.set_len(encoded_len) };
encoded
}

/// # Safety
///
/// `ptr` must be valid for at least `self.len() / 2 + 1` bytes.
#[inline]
unsafe fn encode_path_leaf_to(&self, is_leaf: bool, ptr: *mut u8) {
let odd_nibbles = self.len() % 2 != 0;
*ptr = self.encode_path_leaf_first_byte(is_leaf, odd_nibbles);
let mut nibble_idx = if odd_nibbles { 1 } else { 0 };
for i in 0..self.len() / 2 {
ptr.add(i + 1).write(self.get_byte_unchecked(nibble_idx));
nibble_idx += 2;
}
}

#[inline]
fn encode_path_leaf_first_byte(&self, is_leaf: bool, odd_nibbles: bool) -> u8 {
match (is_leaf, odd_nibbles) {
(true, true) => 0x30 | self[0],
(true, false) => 0x20,
(false, true) => 0x10 | self[0],
(false, false) => 0x00,
}
}

/// Increments the nibble sequence by one.
#[inline]
pub fn increment(&self) -> Option<Self> {
Expand Down Expand Up @@ -827,14 +746,6 @@ mod tests {
use super::*;
use hex_literal::hex;

#[test]
fn hashed_regression() {
let nibbles = Nibbles::from_nibbles(hex!("05010406040a040203030f010805020b050c04070003070e0909070f010b0a0805020301070c0a0902040b0f000f0006040a04050f020b090701000a0a040b"));
let path = nibbles.encode_path_leaf(true);
let expected = hex!("351464a4233f1852b5c47037e997f1ba852317ca924bf0f064a45f2b9710aa4b");
assert_eq!(path[..], expected);
}

#[test]
fn pack_nibbles() {
let tests = [
Expand Down Expand Up @@ -925,33 +836,6 @@ mod tests {
let packed = nibbles.pack();
prop_assert_eq!(&packed[..], input);
}

#[test]
fn encode_path_first_byte(input in vec(any::<u8>(), 1..64)) {
prop_assume!(!input.is_empty());
let input = Nibbles::unpack(input);
prop_assert!(input.iter().all(|&nibble| nibble <= 0xf));
let input_is_odd = input.len() % 2 == 1;

let compact_leaf = input.encode_path_leaf(true);
let leaf_flag = compact_leaf[0];
// Check flag
assert_ne!(leaf_flag & 0x20, 0);
assert_eq!(input_is_odd, (leaf_flag & 0x10) != 0);
if input_is_odd {
assert_eq!(leaf_flag & 0x0f, input.first().unwrap());
}


let compact_extension = input.encode_path_leaf(false);
let extension_flag = compact_extension[0];
// Check first byte
assert_eq!(extension_flag & 0x20, 0);
assert_eq!(input_is_odd, (extension_flag & 0x10) != 0);
if input_is_odd {
assert_eq!(extension_flag & 0x0f, input.first().unwrap());
}
}
}
}
}

0 comments on commit 602543c

Please sign in to comment.