nybbles/nibbles.rs
1use core::{borrow::Borrow, fmt, mem::MaybeUninit, ops::Index, slice};
2use smallvec::SmallVec;
3
4#[cfg(not(feature = "nightly"))]
5#[allow(unused_imports)]
6use core::convert::{identity as likely, identity as unlikely};
7#[cfg(feature = "nightly")]
8#[allow(unused_imports)]
9use core::intrinsics::{likely, unlikely};
10
11#[cfg(not(feature = "std"))]
12use alloc::vec::Vec;
13
14type Repr = SmallVec<[u8; 64]>;
15
16/// Structure representing a sequence of nibbles.
17///
18/// A nibble is a 4-bit value, and this structure is used to store the nibble sequence representing
19/// the keys in a Merkle Patricia Trie (MPT).
20/// Using nibbles simplifies trie operations and enables consistent key representation in the MPT.
21///
22/// # Internal representation
23///
24/// The internal representation is currently a [`SmallVec`] that stores one nibble per byte. Nibbles
25/// are stored inline (on the stack) up to a length of 64 nibbles, or 32 unpacked bytes. This means
26/// that each byte has its upper 4 bits set to zero and the lower 4 bits representing the nibble
27/// value.
28///
29/// This is enforced in the public API, but it is possible to create invalid [`Nibbles`] instances
30/// using methods suffixed with `_unchecked`. These methods are not marked as `unsafe` as they
31/// are not memory-unsafe, but creating invalid values will cause unexpected behavior in other
32/// methods, and users should exercise caution when using them.
33///
34/// # Examples
35///
36/// ```
37/// use nybbles::Nibbles;
38///
39/// let bytes = [0xAB, 0xCD];
40/// let nibbles = Nibbles::unpack(&bytes);
41/// assert_eq!(nibbles, Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]));
42/// assert_eq!(nibbles[..], [0x0A, 0x0B, 0x0C, 0x0D]);
43///
44/// let packed = nibbles.pack();
45/// assert_eq!(&packed[..], &bytes[..]);
46/// ```
47#[derive(Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
48#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
49#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
50pub struct Nibbles(Repr);
51
52impl core::ops::Deref for Nibbles {
53 type Target = [u8];
54
55 #[inline]
56 fn deref(&self) -> &Self::Target {
57 self.as_slice()
58 }
59}
60
61// Override `SmallVec::from` in the default `Clone` implementation since it's not specialized for
62// `Copy` types.
63impl Clone for Nibbles {
64 #[inline]
65 fn clone(&self) -> Self {
66 Self(SmallVec::from_slice(&self.0))
67 }
68
69 #[inline]
70 fn clone_from(&mut self, source: &Self) {
71 self.0.clone_from(&source.0);
72 }
73}
74
75impl fmt::Debug for Nibbles {
76 #[inline]
77 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
78 write!(f, "Nibbles(0x{})", const_hex::encode(self.as_slice()))
79 }
80}
81
82impl From<Nibbles> for Vec<u8> {
83 #[inline]
84 fn from(value: Nibbles) -> Self {
85 value.0.into_vec()
86 }
87}
88
89impl PartialEq<[u8]> for Nibbles {
90 #[inline]
91 fn eq(&self, other: &[u8]) -> bool {
92 self.as_slice() == other
93 }
94}
95
96impl PartialEq<Nibbles> for [u8] {
97 #[inline]
98 fn eq(&self, other: &Nibbles) -> bool {
99 self == other.as_slice()
100 }
101}
102
103impl PartialOrd<[u8]> for Nibbles {
104 #[inline]
105 fn partial_cmp(&self, other: &[u8]) -> Option<core::cmp::Ordering> {
106 self.as_slice().partial_cmp(other)
107 }
108}
109
110impl PartialOrd<Nibbles> for [u8] {
111 #[inline]
112 fn partial_cmp(&self, other: &Nibbles) -> Option<core::cmp::Ordering> {
113 self.partial_cmp(other.as_slice())
114 }
115}
116
117impl Borrow<[u8]> for Nibbles {
118 #[inline]
119 fn borrow(&self) -> &[u8] {
120 self.as_slice()
121 }
122}
123
124impl<Idx> core::ops::Index<Idx> for Nibbles
125where
126 Repr: core::ops::Index<Idx>,
127{
128 type Output = <Repr as core::ops::Index<Idx>>::Output;
129
130 #[inline]
131 fn index(&self, index: Idx) -> &Self::Output {
132 self.0.index(index)
133 }
134}
135
136#[cfg(feature = "rlp")]
137impl alloy_rlp::Encodable for Nibbles {
138 #[inline]
139 fn length(&self) -> usize {
140 alloy_rlp::Encodable::length(self.as_slice())
141 }
142
143 #[inline]
144 fn encode(&self, out: &mut dyn alloy_rlp::BufMut) {
145 alloy_rlp::Encodable::encode(self.as_slice(), out)
146 }
147}
148
149#[cfg(feature = "arbitrary")]
150impl proptest::arbitrary::Arbitrary for Nibbles {
151 type Parameters = proptest::collection::SizeRange;
152 type Strategy = proptest::strategy::Map<
153 proptest::collection::VecStrategy<core::ops::RangeInclusive<u8>>,
154 fn(Vec<u8>) -> Self,
155 >;
156
157 #[inline]
158 fn arbitrary_with(size: proptest::collection::SizeRange) -> Self::Strategy {
159 use proptest::prelude::*;
160 proptest::collection::vec(0x0..=0xf, size).prop_map(Self::from_nibbles_unchecked)
161 }
162}
163
164impl Nibbles {
165 /// Creates a new empty [`Nibbles`] instance.
166 ///
167 /// # Examples
168 ///
169 /// ```
170 /// # use nybbles::Nibbles;
171 /// let nibbles = Nibbles::new();
172 /// assert_eq!(nibbles.len(), 0);
173 /// ```
174 #[inline]
175 pub const fn new() -> Self {
176 Self(SmallVec::new_const())
177 }
178
179 /// Creates a new [`Nibbles`] instance with the given capacity.
180 ///
181 /// # Examples
182 ///
183 /// ```
184 /// # use nybbles::Nibbles;
185 /// let nibbles = Nibbles::with_capacity(10);
186 /// assert_eq!(nibbles.len(), 0);
187 /// ```
188 #[inline]
189 pub fn with_capacity(capacity: usize) -> Self {
190 Self(SmallVec::with_capacity(capacity))
191 }
192
193 /// Creates a new [`Nibbles`] instance with the given nibbles.
194 #[inline]
195 pub fn from_repr(nibbles: Repr) -> Self {
196 check_nibbles(&nibbles);
197 Self::from_repr_unchecked(nibbles)
198 }
199
200 /// Creates a new [`Nibbles`] instance with the given nibbles.
201 ///
202 /// This will not unpack the bytes into nibbles, and will instead store the bytes as-is.
203 ///
204 /// Note that it is possible to create a [`Nibbles`] instance with invalid nibble values (i.e.
205 /// values greater than 0xf) using this method. See [the type docs](Self) for more details.
206 ///
207 /// # Panics
208 ///
209 /// Panics if the any of the bytes is not a valid nibble (`0..=0x0f`).
210 #[inline]
211 pub const fn from_repr_unchecked(small_vec: Repr) -> Self {
212 Self(small_vec)
213 }
214
215 /// Creates a new [`Nibbles`] instance by copying the given bytes.
216 ///
217 /// # Panics
218 ///
219 /// Panics if the any of the bytes is not a valid nibble (`0..=0x0f`).
220 ///
221 /// # Examples
222 ///
223 /// ```
224 /// # use nybbles::Nibbles;
225 /// let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
226 /// assert_eq!(nibbles[..], [0x0A, 0x0B, 0x0C, 0x0D]);
227 /// ```
228 ///
229 /// Invalid values will cause panics:
230 ///
231 /// ```should_panic
232 /// # use nybbles::Nibbles;
233 /// let nibbles = Nibbles::from_nibbles(&[0xFF]);
234 /// ```
235 #[inline]
236 #[track_caller]
237 pub fn from_nibbles<T: AsRef<[u8]>>(nibbles: T) -> Self {
238 let nibbles = nibbles.as_ref();
239 check_nibbles(nibbles);
240 Self::from_nibbles_unchecked(nibbles)
241 }
242
243 /// Creates a new [`Nibbles`] instance by copying the given bytes, without checking their
244 /// validity.
245 ///
246 /// This will not unpack the bytes into nibbles, and will instead store the bytes as-is.
247 ///
248 /// Note that it is possible to create a [`Nibbles`] instance with invalid nibble values (i.e.
249 /// values greater than 0xf) using this method. See [the type docs](Self) for more details.
250 ///
251 /// # Examples
252 ///
253 /// ```
254 /// # use nybbles::Nibbles;
255 /// let nibbles = Nibbles::from_nibbles_unchecked(&[0x0A, 0x0B, 0x0C, 0x0D]);
256 /// assert_eq!(nibbles[..], [0x0A, 0x0B, 0x0C, 0x0D]);
257 ///
258 /// // Invalid value!
259 /// let nibbles = Nibbles::from_nibbles_unchecked(&[0xFF]);
260 /// assert_eq!(nibbles[..], [0xFF]);
261 /// ```
262 #[inline]
263 pub fn from_nibbles_unchecked<T: AsRef<[u8]>>(nibbles: T) -> Self {
264 Self(SmallVec::from_slice(nibbles.as_ref()))
265 }
266
267 /// Creates a new [`Nibbles`] instance from a byte vector, without checking its validity.
268 ///
269 /// This will not unpack the bytes into nibbles, and will instead store the bytes as-is.
270 ///
271 /// Note that it is possible to create a [`Nibbles`] instance with invalid nibble values (i.e.
272 /// values greater than 0xf) using this method. See [the type docs](Self) for more details.
273 ///
274 /// # Examples
275 ///
276 /// ```
277 /// # use nybbles::Nibbles;
278 /// let nibbles = Nibbles::from_vec_unchecked(vec![0x0A, 0x0B, 0x0C, 0x0D]);
279 /// assert_eq!(nibbles[..], [0x0A, 0x0B, 0x0C, 0x0D]);
280 /// ```
281 ///
282 /// Invalid values will cause panics:
283 ///
284 /// ```should_panic
285 /// # use nybbles::Nibbles;
286 /// let nibbles = Nibbles::from_vec(vec![0xFF]);
287 /// ```
288 #[inline]
289 #[track_caller]
290 pub fn from_vec(vec: Vec<u8>) -> Self {
291 check_nibbles(&vec);
292 Self::from_vec_unchecked(vec)
293 }
294
295 /// Creates a new [`Nibbles`] instance from a byte vector, without checking its validity.
296 ///
297 /// Note that it is possible to create a [`Nibbles`] instance with invalid nibble values (i.e.
298 /// values greater than 0xf) using this method. See [the type docs](Self) for more details.
299 ///
300 /// # Examples
301 ///
302 /// ```
303 /// # use nybbles::Nibbles;
304 /// let nibbles = Nibbles::from_vec_unchecked(vec![0x0A, 0x0B, 0x0C, 0x0D]);
305 /// assert_eq!(nibbles[..], [0x0A, 0x0B, 0x0C, 0x0D]);
306 ///
307 /// // Invalid value!
308 /// let nibbles = Nibbles::from_vec_unchecked(vec![0xFF]);
309 /// assert_eq!(nibbles[..], [0xFF]);
310 /// ```
311 #[inline]
312 pub fn from_vec_unchecked(vec: Vec<u8>) -> Self {
313 Self(SmallVec::from_vec(vec))
314 }
315
316 /// Converts a byte slice into a [`Nibbles`] instance containing the nibbles (half-bytes or 4
317 /// bits) that make up the input byte data.
318 ///
319 /// # Panics
320 ///
321 /// Panics if the length of the input is greater than `usize::MAX / 2`.
322 ///
323 /// # Examples
324 ///
325 /// ```
326 /// # use nybbles::Nibbles;
327 /// let nibbles = Nibbles::unpack(&[0xAB, 0xCD]);
328 /// assert_eq!(nibbles[..], [0x0A, 0x0B, 0x0C, 0x0D]);
329 /// ```
330 #[inline]
331 pub fn unpack<T: AsRef<[u8]>>(data: T) -> Self {
332 Self::unpack_(data.as_ref())
333 }
334
335 #[inline]
336 fn unpack_(data: &[u8]) -> Self {
337 let unpacked_len =
338 data.len().checked_mul(2).expect("trying to unpack usize::MAX / 2 bytes");
339 Self(unsafe { smallvec_with(unpacked_len, |out| Self::unpack_to_unchecked(data, out)) })
340 }
341
342 /// Unpacks into the given slice rather than allocating a new [`Nibbles`] instance.
343 #[inline]
344 pub fn unpack_to(data: &[u8], out: &mut [u8]) {
345 assert!(out.len() >= data.len() * 2);
346 // SAFETY: asserted length.
347 unsafe {
348 let out = slice::from_raw_parts_mut(out.as_mut_ptr().cast(), out.len());
349 Self::unpack_to_unchecked(data, out)
350 }
351 }
352
353 /// Unpacks into the given slice rather than allocating a new [`Nibbles`] instance.
354 ///
355 /// # Safety
356 ///
357 /// `out` must be valid for at least `data.len() * 2` bytes.
358 #[inline]
359 pub unsafe fn unpack_to_unchecked(data: &[u8], out: &mut [MaybeUninit<u8>]) {
360 debug_assert!(out.len() >= data.len() * 2);
361 let ptr = out.as_mut_ptr().cast::<u8>();
362 for (i, &byte) in data.iter().enumerate() {
363 ptr.add(i * 2).write(byte >> 4);
364 ptr.add(i * 2 + 1).write(byte & 0x0f);
365 }
366 }
367
368 /// Packs the nibbles into the given slice.
369 ///
370 /// This method combines each pair of consecutive nibbles into a single byte,
371 /// effectively reducing the size of the data by a factor of two.
372 /// If the number of nibbles is odd, the last nibble is shifted left by 4 bits and
373 /// added to the packed byte vector.
374 ///
375 /// # Examples
376 ///
377 /// ```
378 /// # use nybbles::Nibbles;
379 /// let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
380 /// assert_eq!(nibbles.pack()[..], [0xAB, 0xCD]);
381 /// ```
382 #[inline]
383 pub fn pack(&self) -> SmallVec<[u8; 32]> {
384 let packed_len = (self.len() + 1) / 2;
385 unsafe { smallvec_with(packed_len, |out| self.pack_to_unchecked2(out)) }
386 }
387
388 /// Packs the nibbles into the given slice.
389 ///
390 /// See [`pack`](Self::pack) for more information.
391 ///
392 /// # Panics
393 ///
394 /// Panics if the slice is not at least `(self.len() + 1) / 2` bytes long.
395 ///
396 /// # Examples
397 ///
398 /// ```
399 /// # use nybbles::Nibbles;
400 /// let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
401 /// let mut packed = [0; 2];
402 /// nibbles.pack_to(&mut packed);
403 /// assert_eq!(packed[..], [0xAB, 0xCD]);
404 /// ```
405 #[inline]
406 #[track_caller]
407 pub fn pack_to(&self, out: &mut [u8]) {
408 pack_to(self, out);
409 }
410
411 /// Packs the nibbles into the given pointer.
412 ///
413 /// See [`pack`](Self::pack) for more information.
414 ///
415 /// # Safety
416 ///
417 /// `ptr` must be valid for at least `(self.len() + 1) / 2` bytes.
418 ///
419 /// # Examples
420 ///
421 /// ```
422 /// # use nybbles::Nibbles;
423 /// let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
424 /// let mut packed = [0; 2];
425 /// // SAFETY: enough capacity.
426 /// unsafe { nibbles.pack_to_unchecked(packed.as_mut_ptr()) };
427 /// assert_eq!(packed[..], [0xAB, 0xCD]);
428 /// ```
429 #[inline]
430 #[deprecated = "prefer using `pack_to` or `pack_to_unchecked2` instead"]
431 pub unsafe fn pack_to_unchecked(&self, ptr: *mut u8) {
432 self.pack_to_unchecked2(slice::from_raw_parts_mut(ptr.cast(), (self.len() + 1) / 2));
433 }
434
435 /// Packs the nibbles into the given slice without checking its length.
436 ///
437 /// # Safety
438 ///
439 /// `out` must be valid for at least `(self.len() + 1) / 2` bytes.
440 #[inline]
441 pub unsafe fn pack_to_unchecked2(&self, out: &mut [MaybeUninit<u8>]) {
442 pack_to_unchecked(self, out);
443 }
444
445 /// Gets the byte at the given index by combining two consecutive nibbles.
446 ///
447 /// # Examples
448 ///
449 /// ```
450 /// # use nybbles::Nibbles;
451 /// let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
452 /// assert_eq!(nibbles.get_byte(0), Some(0xAB));
453 /// assert_eq!(nibbles.get_byte(1), Some(0xBC));
454 /// assert_eq!(nibbles.get_byte(2), Some(0xCD));
455 /// assert_eq!(nibbles.get_byte(3), None);
456 /// ```
457 #[inline]
458 pub fn get_byte(&self, i: usize) -> Option<u8> {
459 get_byte(self, i)
460 }
461
462 /// Gets the byte at the given index by combining two consecutive nibbles.
463 ///
464 /// # Safety
465 ///
466 /// `i..i + 1` must be in range.
467 ///
468 /// # Examples
469 ///
470 /// ```
471 /// # use nybbles::Nibbles;
472 /// let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
473 /// // SAFETY: in range.
474 /// unsafe {
475 /// assert_eq!(nibbles.get_byte_unchecked(0), 0xAB);
476 /// assert_eq!(nibbles.get_byte_unchecked(1), 0xBC);
477 /// assert_eq!(nibbles.get_byte_unchecked(2), 0xCD);
478 /// }
479 /// ```
480 #[inline]
481 pub unsafe fn get_byte_unchecked(&self, i: usize) -> u8 {
482 get_byte_unchecked(self, i)
483 }
484
485 /// Increments the nibble sequence by one.
486 #[inline]
487 pub fn increment(&self) -> Option<Self> {
488 let mut incremented = self.clone();
489
490 for nibble in incremented.0.iter_mut().rev() {
491 debug_assert!(*nibble <= 0xf);
492 if *nibble < 0xf {
493 *nibble += 1;
494 return Some(incremented);
495 } else {
496 *nibble = 0;
497 }
498 }
499
500 None
501 }
502
503 /// The last element of the hex vector is used to determine whether the nibble sequence
504 /// represents a leaf or an extension node. If the last element is 0x10 (16), then it's a leaf.
505 #[inline]
506 pub fn is_leaf(&self) -> bool {
507 self.last() == Some(16)
508 }
509
510 /// Returns `true` if this nibble sequence starts with the given prefix.
511 #[inline]
512 pub fn has_prefix(&self, other: &[u8]) -> bool {
513 self.starts_with(other)
514 }
515
516 /// Returns the nibble at the given index.
517 ///
518 /// # Panics
519 ///
520 /// Panics if the index is out of bounds.
521 #[inline]
522 #[track_caller]
523 pub fn at(&self, i: usize) -> usize {
524 self[i] as usize
525 }
526
527 /// Sets the nibble at the given index.
528 ///
529 /// # Panics
530 ///
531 /// Panics if the index is out of bounds, or if `value` is not a valid nibble (`0..=0x0f`).
532 #[inline]
533 #[track_caller]
534 pub fn set_at(&mut self, i: usize, value: u8) {
535 assert!(value <= 0xf);
536 self.set_at_unchecked(i, value);
537 }
538
539 /// Sets the nibble at the given index, without checking its validity.
540 ///
541 /// # Panics
542 ///
543 /// Panics if the index is out of bounds.
544 #[inline]
545 #[track_caller]
546 pub fn set_at_unchecked(&mut self, i: usize, value: u8) {
547 self.0[i] = value;
548 }
549
550 /// Returns the first nibble of this nibble sequence.
551 #[inline]
552 pub fn first(&self) -> Option<u8> {
553 self.0.first().copied()
554 }
555
556 /// Returns the last nibble of this nibble sequence.
557 #[inline]
558 pub fn last(&self) -> Option<u8> {
559 self.0.last().copied()
560 }
561
562 /// Returns the length of the common prefix between this nibble sequence and the given.
563 ///
564 /// # Examples
565 ///
566 /// ```
567 /// # use nybbles::Nibbles;
568 /// let a = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F]);
569 /// let b = &[0x0A, 0x0B, 0x0C, 0x0E];
570 /// assert_eq!(a.common_prefix_length(b), 3);
571 /// ```
572 #[inline]
573 pub fn common_prefix_length(&self, other: &[u8]) -> usize {
574 common_prefix_length(self, other)
575 }
576
577 /// Returns a reference to the underlying byte slice.
578 #[inline]
579 pub fn as_slice(&self) -> &[u8] {
580 &self.0
581 }
582
583 /// Returns a mutable reference to the underlying byte slice.
584 ///
585 /// Note that it is possible to create invalid [`Nibbles`] instances using this method. See
586 /// [the type docs](Self) for more details.
587 #[inline]
588 pub fn as_mut_slice_unchecked(&mut self) -> &mut [u8] {
589 &mut self.0
590 }
591
592 /// Returns a mutable reference to the underlying byte vector.
593 ///
594 /// Note that it is possible to create invalid [`Nibbles`] instances using this method. See
595 /// [the type docs](Self) for more details.
596 #[inline]
597 pub fn as_mut_vec_unchecked(&mut self) -> &mut Repr {
598 &mut self.0
599 }
600
601 /// Slice the current nibbles within the provided index range.
602 ///
603 /// # Panics
604 ///
605 /// Panics if the range is out of bounds.
606 #[inline]
607 #[track_caller]
608 pub fn slice<I>(&self, range: I) -> Self
609 where
610 Self: Index<I, Output = [u8]>,
611 {
612 Self::from_nibbles_unchecked(&self[range])
613 }
614
615 /// Join two nibbles together.
616 #[inline]
617 pub fn join(&self, b: &Self) -> Self {
618 let mut nibbles = SmallVec::with_capacity(self.len() + b.len());
619 nibbles.extend_from_slice(self);
620 nibbles.extend_from_slice(b);
621 Self(nibbles)
622 }
623
624 /// Pushes a nibble to the end of the current nibbles.
625 ///
626 /// # Panics
627 ///
628 /// Panics if the nibble is not a valid nibble (`0..=0x0f`).
629 #[inline]
630 #[track_caller]
631 pub fn push(&mut self, nibble: u8) {
632 assert!(nibble <= 0xf);
633 self.push_unchecked(nibble);
634 }
635
636 /// Pushes a nibble to the end of the current nibbles without checking its validity.
637 ///
638 /// Note that it is possible to create invalid [`Nibbles`] instances using this method. See
639 /// [the type docs](Self) for more details.
640 #[inline]
641 pub fn push_unchecked(&mut self, nibble: u8) {
642 self.0.push(nibble);
643 }
644
645 /// Pops a nibble from the end of the current nibbles.
646 #[inline]
647 pub fn pop(&mut self) -> Option<u8> {
648 self.0.pop()
649 }
650
651 /// Extend the current nibbles with another nibbles.
652 #[inline]
653 pub fn extend_from_slice(&mut self, b: &Nibbles) {
654 self.0.extend_from_slice(b.as_slice());
655 }
656
657 /// Extend the current nibbles with another byte slice.
658 ///
659 /// Note that it is possible to create invalid [`Nibbles`] instances using this method. See
660 /// [the type docs](Self) for more details.
661 #[inline]
662 pub fn extend_from_slice_unchecked(&mut self, b: &[u8]) {
663 self.0.extend_from_slice(b);
664 }
665
666 /// Truncates the current nibbles to the given length.
667 #[inline]
668 pub fn truncate(&mut self, new_len: usize) {
669 self.0.truncate(new_len);
670 }
671
672 /// Clears the current nibbles.
673 #[inline]
674 pub fn clear(&mut self) {
675 self.0.clear();
676 }
677}
678
679/// Gets the byte at the given index by combining two consecutive nibbles.
680///
681/// # Examples
682///
683/// ```
684/// # use nybbles::get_byte;
685/// let nibbles: &[u8] = &[0x0A, 0x0B, 0x0C, 0x0D];
686/// assert_eq!(get_byte(nibbles, 0), Some(0xAB));
687/// assert_eq!(get_byte(nibbles, 1), Some(0xBC));
688/// assert_eq!(get_byte(nibbles, 2), Some(0xCD));
689/// assert_eq!(get_byte(nibbles, 3), None);
690/// ```
691#[inline]
692pub fn get_byte(nibbles: &[u8], i: usize) -> Option<u8> {
693 if likely((i < usize::MAX) & (i.wrapping_add(1) < nibbles.len())) {
694 Some(unsafe { get_byte_unchecked(nibbles, i) })
695 } else {
696 None
697 }
698}
699
700/// Gets the byte at the given index by combining two consecutive nibbles.
701///
702/// # Safety
703///
704/// `i..i + 1` must be in range.
705///
706/// # Examples
707///
708/// ```
709/// # use nybbles::get_byte_unchecked;
710/// let nibbles: &[u8] = &[0x0A, 0x0B, 0x0C, 0x0D];
711/// // SAFETY: in range.
712/// unsafe {
713/// assert_eq!(get_byte_unchecked(nibbles, 0), 0xAB);
714/// assert_eq!(get_byte_unchecked(nibbles, 1), 0xBC);
715/// assert_eq!(get_byte_unchecked(nibbles, 2), 0xCD);
716/// }
717/// ```
718#[inline]
719pub unsafe fn get_byte_unchecked(nibbles: &[u8], i: usize) -> u8 {
720 debug_assert!(
721 i < usize::MAX && i + 1 < nibbles.len(),
722 "index {i}..{} out of bounds of {}",
723 i + 1,
724 nibbles.len()
725 );
726 let hi = *nibbles.get_unchecked(i);
727 let lo = *nibbles.get_unchecked(i + 1);
728 (hi << 4) | lo
729}
730
731/// Packs the nibbles into the given slice.
732///
733/// See [`Nibbles::pack`] for more information.
734///
735/// # Panics
736///
737/// Panics if the slice is not at least `(self.len() + 1) / 2` bytes long.
738///
739/// # Examples
740///
741/// ```
742/// # use nybbles::Nibbles;
743/// let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
744/// let mut packed = [0; 2];
745/// nibbles.pack_to(&mut packed);
746/// assert_eq!(packed[..], [0xAB, 0xCD]);
747/// ```
748#[inline]
749pub fn pack_to(nibbles: &[u8], out: &mut [u8]) {
750 assert!(out.len() >= (nibbles.len() + 1) / 2);
751 // SAFETY: asserted length.
752 unsafe {
753 let out = slice::from_raw_parts_mut(out.as_mut_ptr().cast(), out.len());
754 pack_to_unchecked(nibbles, out)
755 }
756}
757
758/// Packs the nibbles into the given slice without checking its length.
759///
760/// # Safety
761///
762/// `out` must be valid for at least `(self.len() + 1) / 2` bytes.
763#[inline]
764pub unsafe fn pack_to_unchecked(nibbles: &[u8], out: &mut [MaybeUninit<u8>]) {
765 let len = nibbles.len();
766 debug_assert!(out.len() >= (len + 1) / 2);
767 let ptr = out.as_mut_ptr().cast::<u8>();
768 for i in 0..len / 2 {
769 ptr.add(i).write(get_byte_unchecked(nibbles, i * 2));
770 }
771 if len % 2 != 0 {
772 let i = len / 2;
773 ptr.add(i).write(nibbles.last().unwrap_unchecked() << 4);
774 }
775}
776
777/// Returns the length of the common prefix between the two slices.
778///
779/// # Examples
780///
781/// ```
782/// # use nybbles::common_prefix_length;
783/// let a = &[0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F];
784/// let b = &[0x0A, 0x0B, 0x0C, 0x0E];
785/// assert_eq!(common_prefix_length(a, b), 3);
786/// ```
787#[inline]
788pub fn common_prefix_length(a: &[u8], b: &[u8]) -> usize {
789 let len = core::cmp::min(a.len(), b.len());
790 let a = &a[..len];
791 let b = &b[..len];
792 for i in 0..len {
793 if a[i] != b[i] {
794 return i;
795 }
796 }
797 len
798}
799
800/// Initializes a smallvec with the given length and a closure that initializes the buffer.
801///
802/// Optimized version of `SmallVec::with_capacity` + `f()` + `.set_len`.
803///
804/// # Safety
805///
806/// The closure must fully initialize the buffer with the given length.
807#[inline]
808pub unsafe fn smallvec_with<const N: usize>(
809 len: usize,
810 f: impl FnOnce(&mut [MaybeUninit<u8>]),
811) -> SmallVec<[u8; N]> {
812 let mut buf = smallvec_with_len::<N>(len);
813 f(unsafe { slice::from_raw_parts_mut(buf.as_mut_ptr().cast(), len) });
814 buf
815}
816
817#[inline]
818#[allow(clippy::uninit_vec)]
819unsafe fn smallvec_with_len<const N: usize>(len: usize) -> SmallVec<[u8; N]> {
820 if likely(len <= N) {
821 SmallVec::from_buf_and_len_unchecked(MaybeUninit::<[u8; N]>::uninit(), len)
822 } else {
823 let mut vec = Vec::with_capacity(len);
824 unsafe { vec.set_len(len) };
825 SmallVec::from_vec(vec)
826 }
827}
828
829#[inline]
830#[track_caller]
831fn check_nibbles(nibbles: &[u8]) {
832 if !valid_nibbles(nibbles) {
833 panic_invalid_nibbles();
834 }
835}
836
837fn valid_nibbles(nibbles: &[u8]) -> bool {
838 nibbles.iter().all(|&nibble| nibble <= 0xf)
839}
840
841#[cold]
842#[track_caller]
843const fn panic_invalid_nibbles() -> ! {
844 panic!("attempted to create invalid nibbles");
845}
846
847#[cfg(test)]
848mod tests {
849 use super::*;
850 use hex_literal::hex;
851
852 #[test]
853 fn pack_nibbles() {
854 let tests = [
855 (&[][..], &[][..]),
856 (&[0xa], &[0xa0]),
857 (&[0xa, 0x0], &[0xa0]),
858 (&[0xa, 0xb], &[0xab]),
859 (&[0xa, 0xb, 0x2], &[0xab, 0x20]),
860 (&[0xa, 0xb, 0x2, 0x0], &[0xab, 0x20]),
861 (&[0xa, 0xb, 0x2, 0x7], &[0xab, 0x27]),
862 ];
863 for (input, expected) in tests {
864 assert!(valid_nibbles(input));
865 let nibbles = Nibbles::from_nibbles(input);
866 let encoded = nibbles.pack();
867 assert_eq!(&encoded[..], expected);
868 }
869 }
870
871 #[test]
872 fn slice() {
873 const RAW: &[u8] = &hex!("05010406040a040203030f010805020b050c04070003070e0909070f010b0a0805020301070c0a0902040b0f000f0006040a04050f020b090701000a0a040b");
874
875 #[track_caller]
876 fn test_slice<I>(range: I, expected: &[u8])
877 where
878 Nibbles: Index<I, Output = [u8]>,
879 {
880 let nibbles = Nibbles::from_nibbles_unchecked(RAW);
881 let sliced = nibbles.slice(range);
882 assert_eq!(sliced, Nibbles::from_nibbles(expected));
883 assert_eq!(sliced.as_slice(), expected);
884 }
885
886 test_slice(0..0, &[]);
887 test_slice(0..1, &[0x05]);
888 test_slice(1..1, &[]);
889 test_slice(1..=1, &[0x01]);
890 test_slice(0..=1, &[0x05, 0x01]);
891 test_slice(0..2, &[0x05, 0x01]);
892
893 test_slice(..0, &[]);
894 test_slice(..1, &[0x05]);
895 test_slice(..=1, &[0x05, 0x01]);
896 test_slice(..2, &[0x05, 0x01]);
897
898 test_slice(.., RAW);
899 test_slice(..RAW.len(), RAW);
900 test_slice(0.., RAW);
901 test_slice(0..RAW.len(), RAW);
902 }
903
904 #[test]
905 fn indexing() {
906 let mut nibbles = Nibbles::from_nibbles([0x0A]);
907 assert_eq!(nibbles.at(0), 0x0A);
908 nibbles.set_at(0, 0x0B);
909 assert_eq!(nibbles.at(0), 0x0B);
910 }
911
912 #[test]
913 fn push_pop() {
914 let mut nibbles = Nibbles::new();
915 nibbles.push(0x0A);
916 assert_eq!(nibbles[0], 0x0A);
917 assert_eq!(nibbles.len(), 1);
918
919 assert_eq!(nibbles.pop(), Some(0x0A));
920 assert_eq!(nibbles.len(), 0);
921 }
922
923 #[test]
924 fn get_byte_max() {
925 let nibbles = Nibbles::from_nibbles([0x0A, 0x0B, 0x0C, 0x0D]);
926 assert_eq!(nibbles.get_byte(usize::MAX), None);
927 }
928
929 #[cfg(feature = "arbitrary")]
930 mod arbitrary {
931 use super::*;
932 use proptest::{collection::vec, prelude::*};
933
934 proptest::proptest! {
935 #[test]
936 #[cfg_attr(miri, ignore = "no proptest")]
937 fn pack_unpack_roundtrip(input in vec(any::<u8>(), 0..64)) {
938 let nibbles = Nibbles::unpack(&input);
939 prop_assert!(valid_nibbles(&nibbles));
940 let packed = nibbles.pack();
941 prop_assert_eq!(&packed[..], input);
942 }
943 }
944 }
945}