trie_db_fun/nibble/
mod.rs

1// Copyright 2019 Parity Technologies
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Nibble oriented methods.
16
17use crate::{node::NodeKey, rstd::cmp};
18
19pub use self::leftnibbleslice::LeftNibbleSlice;
20
21mod leftnibbleslice;
22mod nibbleslice;
23mod nibblevec;
24
25/// Utility methods to work on radix 16 nibble.
26pub mod nibble_ops {
27	use super::*;
28
29	/// Single nibble length in bit.
30	pub const BIT_PER_NIBBLE: usize = 4;
31	/// Number of nibble per byte.
32	pub const NIBBLE_PER_BYTE: usize = 2;
33	/// Number of child for a branch (trie radix).
34	pub const NIBBLE_LENGTH: usize = 16;
35	/// Nibble (half a byte).
36	pub const PADDING_BITMASK: u8 = 0x0F;
37	/// Size of header.
38	pub const CONTENT_HEADER_SIZE: u8 = 1;
39
40	/// Mask a byte, keeping left nibble.
41	#[inline(always)]
42	pub fn pad_left(b: u8) -> u8 {
43		b & !PADDING_BITMASK
44	}
45
46	/// Mask a byte, keeping right byte.
47	#[inline(always)]
48	pub fn pad_right(b: u8) -> u8 {
49		b & PADDING_BITMASK
50	}
51
52	/// Get u8 nibble value at a given index of a byte.
53	#[inline(always)]
54	pub fn at_left(ix: u8, b: u8) -> u8 {
55		if ix == 1 {
56			b & PADDING_BITMASK
57		} else {
58			b >> BIT_PER_NIBBLE
59		}
60	}
61
62	/// Get u8 nibble value at a given index in a left aligned array.
63	#[inline(always)]
64	pub fn left_nibble_at(v1: &[u8], ix: usize) -> u8 {
65		at_left((ix % NIBBLE_PER_BYTE) as u8, v1[ix / NIBBLE_PER_BYTE])
66	}
67
68	/// Get u8 nibble value at a given index in a `NibbleSlice`.
69	#[inline(always)]
70	pub fn at(s: &NibbleSlice, i: usize) -> u8 {
71		let ix = (s.offset + i) / NIBBLE_PER_BYTE;
72		let pad = (s.offset + i) % NIBBLE_PER_BYTE;
73		at_left(pad as u8, s.data[ix])
74	}
75
76	/// Push u8 nibble value at a given index into an existing byte.
77	#[inline(always)]
78	pub fn push_at_left(ix: u8, v: u8, into: u8) -> u8 {
79		into | if ix == 1 { v } else { v << BIT_PER_NIBBLE }
80	}
81
82	/// Calculate the number of needed padding a array of nibble length `i`.
83	#[inline]
84	pub fn number_padding(i: usize) -> usize {
85		i % NIBBLE_PER_BYTE
86	}
87
88	/// The nibble shifts needed to align.
89	/// We use two value, one is a left shift and
90	/// the other is a right shift.
91	pub const SPLIT_SHIFTS: (usize, usize) = (4, 4);
92
93	/// Count the biggest common depth between two left aligned packed nibble slice.
94	pub fn biggest_depth(v1: &[u8], v2: &[u8]) -> usize {
95		let upper_bound = cmp::min(v1.len(), v2.len());
96		for a in 0..upper_bound {
97			if v1[a] != v2[a] {
98				return a * NIBBLE_PER_BYTE + left_common(v1[a], v2[a])
99			}
100		}
101		upper_bound * NIBBLE_PER_BYTE
102	}
103
104	/// Calculate the number of common nibble between two left aligned bytes.
105	#[inline(always)]
106	pub fn left_common(a: u8, b: u8) -> usize {
107		if a == b {
108			2
109		} else if pad_left(a) == pad_left(b) {
110			1
111		} else {
112			0
113		}
114	}
115
116	/// Shifts right aligned key to add a given left offset.
117	/// Resulting in possibly padding at both left and right
118	/// (example usage when combining two keys).
119	pub fn shift_key(key: &mut NodeKey, offset: usize) -> bool {
120		let old_offset = key.0;
121		key.0 = offset;
122		if old_offset > offset {
123			// shift left
124			let (s1, s2) = nibble_ops::SPLIT_SHIFTS;
125			let kl = key.1.len();
126			(0..kl - 1).for_each(|i| key.1[i] = key.1[i] << s2 | key.1[i + 1] >> s1);
127			key.1[kl - 1] = key.1[kl - 1] << s2;
128			true
129		} else if old_offset < offset {
130			// shift right
131			let (s1, s2) = nibble_ops::SPLIT_SHIFTS;
132			key.1.push(0);
133			(1..key.1.len())
134				.rev()
135				.for_each(|i| key.1[i] = key.1[i - 1] << s1 | key.1[i] >> s2);
136			key.1[0] = key.1[0] >> s2;
137			true
138		} else {
139			false
140		}
141	}
142}
143
144/// Backing storage for `NibbleVec`s.
145pub(crate) type BackingByteVec = smallvec::SmallVec<[u8; 40]>;
146
147/// Owning, nibble-oriented byte vector. Counterpart to `NibbleSlice`.
148/// Nibbles are always left aligned, so making a `NibbleVec` from
149/// a `NibbleSlice` can get costy.
150#[cfg_attr(feature = "std", derive(Debug))]
151#[derive(Clone, PartialEq, Eq)]
152pub struct NibbleVec {
153	inner: BackingByteVec,
154	len: usize,
155}
156
157/// Nibble-orientated view onto byte-slice, allowing nibble-precision offsets.
158///
159/// This is an immutable struct. No operations actually change it.
160///
161/// # Example
162/// ```snippet
163/// use patricia_trie::nibbleslice::NibbleSlice;
164/// fn main() {
165///   let d1 = &[0x01u8, 0x23, 0x45];
166///   let d2 = &[0x34u8, 0x50, 0x12];
167///   let d3 = &[0x00u8, 0x12];
168///   let n1 = NibbleSlice::new(d1);			// 0,1,2,3,4,5
169///   let n2 = NibbleSlice::new(d2);			// 3,4,5,0,1,2
170///   let n3 = NibbleSlice::new_offset(d3, 1);	// 0,1,2
171///   assert!(n1 > n3);							// 0,1,2,... > 0,1,2
172///   assert!(n1 < n2);							// 0,... < 3,...
173///   assert!(n2.mid(3) == n3);					// 0,1,2 == 0,1,2
174///   assert!(n1.starts_with(&n3));
175///   assert_eq!(n1.common_prefix(&n3), 3);
176///   assert_eq!(n2.mid(3).common_prefix(&n1), 3);
177/// }
178/// ```
179#[derive(Copy, Clone)]
180pub struct NibbleSlice<'a> {
181	data: &'a [u8],
182	offset: usize,
183}
184
185/// Iterator type for a nibble slice.
186pub struct NibbleSliceIterator<'a> {
187	p: &'a NibbleSlice<'a>,
188	i: usize,
189}
190
191#[cfg(test)]
192mod tests {
193	use super::*;
194
195	#[test]
196	fn nibble_vec_size() {
197		assert_eq!(std::mem::size_of::<NibbleVec>(), 56);
198	}
199}
trie_db_fun/nibble/mod.rs

trie_db_fun/nibble/
mod.rs
