/rust/registry/src/index.crates.io-6f17d22bba15001f/nibble_vec-0.1.0/src/lib.rs

Source (jump to first uncovered line)
#[cfg(test)]
mod test;

use smallvec::{Array, SmallVec};

use std::convert::{From, Into};
use std::fmt::{self, Debug, Formatter};
use std::iter::FromIterator;

/// A `NibbleVec` backed by a `SmallVec` with 64 inline element slots.
/// This will not allocate until more than 64 elements are added.
pub type Nibblet = NibbleVec<[u8; 64]>;

/// A data-structure for storing a sequence of 4-bit values.
///
/// Values are stored in a `Vec<u8>`, with two values per byte.
///
/// Values at even indices are stored in the most-significant half of their byte,
/// while values at odd indices are stored in the least-significant half.
///
/// Imagine a vector of [MSB][msb-wiki] first bytes, and you'll be right.
///
/// n = [_ _ | _ _ | _ _]
///
/// [msb-wiki]: http://en.wikipedia.org/wiki/Most_significant_bit
#[derive(Clone, Default)]
pub struct NibbleVec<A: Array<Item = u8>> {
    length: usize,
    data: SmallVec<A>,
}

impl<A: Array<Item = u8>> NibbleVec<A> {
    /// Create an empty nibble vector.
    pub fn new() -> NibbleVec<A> {
        NibbleVec {
            length: 0,
            data: SmallVec::new(),
        }
    }

    /// Create a nibble vector from a vector of bytes.
    ///
    /// Each byte is split into two 4-bit entries (MSB, LSB).
    #[inline]
    pub fn from_byte_vec(vec: Vec<u8>) -> NibbleVec<A> {
        let length = 2 * vec.len();
        NibbleVec {
            length,
            data: SmallVec::from_iter(vec),
        }
    }

    /// Returns a byte slice of the nibble vector's contents.
    #[inline]
    pub fn as_bytes(&self) -> &[u8] {
        &self.data[..]
    }

    /// Converts a nibble vector into a byte vector.
    ///
    /// This consumes the nibble vector, so we do not need to copy its contents.
    #[inline]
    pub fn into_bytes(self) -> Vec<u8> {
        self.data.to_vec()
    }

    /// Get the number of elements stored in the vector.
    #[inline]
    pub fn len(&self) -> usize {
        self.length
    }

    /// Returns `true` if the nibble vector has a length of 0.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }

    /// Fetch a single entry from the vector.
    ///
    /// Guaranteed to be a value in the interval [0, 15].
    ///
    /// **Panics** if `idx >= self.len()`.
    #[inline]
    pub fn get(&self, idx: usize) -> u8 {
        if idx >= self.length {
            panic!(
                "NibbleVec index out of bounds: len is {}, index is {}",
                self.length, idx
            );
        }
        let vec_idx = idx / 2;
        match idx % 2 {
            // If the index is even, take the first (most significant) half of the stored byte.
            0 => self.data[vec_idx] >> 4,
            // If the index is odd, take the second (least significant) half.
            _ => self.data[vec_idx] & 0x0F,
        }
    }

    /// Add a single nibble to the vector.
    ///
    /// Only the 4 least-significant bits of the value are used.
    #[inline]
    pub fn push(&mut self, val: u8) {
        if self.length % 2 == 0 {
            self.data.push(val << 4);
        } else {
            let vec_len = self.data.len();

            // Zero the second half of the last byte just to be safe.
            self.data[vec_len - 1] &= 0xF0;

            // Write the new value.
            self.data[vec_len - 1] |= val & 0x0F;
        }
        self.length += 1;
    }

    /// Split the vector into two parts.
    ///
    /// All elements at or following the given index are returned in a new `NibbleVec`,
    /// with exactly `idx` elements remaining in this vector.
    ///
    /// **Panics** if `idx > self.len()`.
    pub fn split(&mut self, idx: usize) -> NibbleVec<A> {
        // assert! is a few percent slower surprisingly
        if idx > self.length {
            panic!(
                "attempted to split past vector end. len is {}, index is {}",
                self.length, idx
            );
        } else if idx == self.length {
            NibbleVec::new()
        } else if idx % 2 == 0 {
            self.split_even(idx)
        } else {
            self.split_odd(idx)
        }
    }

    /// Split function for odd *indices*.
    #[inline]
    fn split_odd(&mut self, idx: usize) -> NibbleVec<A> {
        let mut tail = NibbleVec::new();

        // Perform an overlap copy, copying the last nibble of the original vector only if
        // the length of the new tail is *odd*.
        let tail_length = self.length - idx;
        let take_last = tail_length % 2 == 1;
        self.overlap_copy(
            idx / 2,
            self.data.len(),
            &mut tail.data,
            &mut tail.length,
            take_last,
        );

        // Remove the copied bytes, being careful to skip the idx byte.
        for _ in (idx / 2 + 1)..self.data.len() {
            self.data.pop();
        }

        // Zero the second half of the index byte so as to maintain the last-nibble invariant.
        self.data[idx / 2] &= 0xF0;

        // Update the length of the first NibbleVec.
        self.length = idx;

        tail
    }

    /// Split function for even *indices*.
    #[inline]
    fn split_even(&mut self, idx: usize) -> NibbleVec<A> {
        // Avoid allocating a temporary vector by copying all the bytes in order, then popping them.

        // Possible to prove: l_d - ⌊i / 2⌋ = ⌊(l_v - i + 1) / 2⌋
        //  where l_d = self.data.len()
        //        l_v = self.length

        let half_idx = idx / 2;
        let mut tail = NibbleVec::new();

        // Copy the bytes.
        for i in half_idx..self.data.len() {
            tail.data.push(self.data[i]);
        }

        // Pop the same bytes.
        for _ in half_idx..self.data.len() {
            self.data.pop();
        }

        // Update lengths.
        tail.length = self.length - idx;
        self.length = idx;

        tail
    }

    /// Copy data between the second half of self.data[start] and
    /// self.data[end - 1]. The second half of the last entry is included
    /// if include_last is true.
    #[inline]
    fn overlap_copy(
        &self,
        start: usize,
        end: usize,
        vec: &mut SmallVec<A>,
        length: &mut usize,
        include_last: bool,
    ) {
        // Copy up to the first half of the last byte.
        for i in start..(end - 1) {
            // The first half is the second half of the old entry.
            let first_half = self.data[i] & 0x0f;

            // The second half is the first half of the next entry.
            let second_half = self.data[i + 1] >> 4;

            vec.push((first_half << 4) | second_half);
            *length += 2;
        }

        if include_last {
            let last = self.data[end - 1] & 0x0f;
            vec.push(last << 4);
            *length += 1;
        }
    }

    /// Append another nibble vector whilst consuming this vector.
    #[inline]
    pub fn join(mut self, other: &NibbleVec<A>) -> NibbleVec<A> {
        // If the length is even, we can append directly.
        if self.length % 2 == 0 {
            self.length += other.length;
            self.data.extend_from_slice(&other.data);
            return self;
        }

        // If the other vector is empty, bail out.
        if other.is_empty() {
            return self;
        }

        // If the length is odd, we have to perform an overlap copy.
        // Copy the first half of the first element, to make the vector an even length.
        self.push(other.get(0));

        // Copy the rest of the vector using an overlap copy.
        let take_last = other.len() % 2 == 0;
        other.overlap_copy(
            0,
            other.data.len(),
            &mut self.data,
            &mut self.length,
            take_last,
        );

        self
    }
}

impl<A: Array<Item = u8>> PartialEq<NibbleVec<A>> for NibbleVec<A> {
    #[inline]
    fn eq(&self, other: &NibbleVec<A>) -> bool {
        self.length == other.length && self.data == other.data
    }
}

impl<A: Array<Item = u8>> Eq for NibbleVec<A> {}

/// Compare a `NibbleVec` and a slice of bytes *element-by-element*.
/// Bytes are **not** interpreted as two `NibbleVec` entries.
impl<A: Array<Item = u8>> PartialEq<[u8]> for NibbleVec<A> {
    #[inline]
    fn eq(&self, other: &[u8]) -> bool {
        if other.len() != self.len() {
            return false;
        }

        for (i, x) in other.iter().enumerate() {
            if self.get(i) != *x {
                return false;
            }
        }
        true
    }
}

impl<A: Array<Item = u8>> Debug for NibbleVec<A> {
    fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
        write!(fmt, "NibbleVec [")?;

        if !self.is_empty() {
            write!(fmt, "{}", self.get(0))?;
        }

        for i in 1..self.len() {
            write!(fmt, ", {}", self.get(i))?;
        }
        write!(fmt, "]")
    }
}

impl<A: Array<Item = u8>> From<Vec<u8>> for NibbleVec<A> {
    #[inline]
    fn from(v: Vec<u8>) -> NibbleVec<A> {
        NibbleVec::from_byte_vec(v)
    }
}

impl<'a, A: Array<Item = u8>> From<&'a [u8]> for NibbleVec<A> {
    #[inline]
    fn from(v: &[u8]) -> NibbleVec<A> {
        NibbleVec::from_byte_vec(v.into())
    }
}

impl<A: Array<Item = u8>> Into<Vec<u8>> for NibbleVec<A> {
    #[inline]
    fn into(self) -> Vec<u8> {
        self.data.to_vec()
    }
}

impl<'a, A: Array<Item = u8>> Into<Vec<u8>> for &'a NibbleVec<A> {
    #[inline]
    fn into(self) -> Vec<u8> {
        self.data.to_vec()
    }
}

Coverage Report

Created: 2025-02-21 07:11

Line	Count	Source (jump to first uncovered line)
1		#[cfg(test)]
2		mod test;
3
4		use smallvec::{Array, SmallVec};
5
6		use std::convert::{From, Into};
7		use std::fmt::{self, Debug, Formatter};
8		use std::iter::FromIterator;
9
10		/// A `NibbleVec` backed by a `SmallVec` with 64 inline element slots.
11		/// This will not allocate until more than 64 elements are added.
12		pub type Nibblet = NibbleVec<[u8; 64]>;
13
14		/// A data-structure for storing a sequence of 4-bit values.
15		///
16		/// Values are stored in a `Vec<u8>`, with two values per byte.
17		///
18		/// Values at even indices are stored in the most-significant half of their byte,
19		/// while values at odd indices are stored in the least-significant half.
20		///
21		/// Imagine a vector of [MSB][msb-wiki] first bytes, and you'll be right.
22		///
23		/// n = [_ _ \| _ _ \| _ _]
24		///
25		/// [msb-wiki]: http://en.wikipedia.org/wiki/Most_significant_bit
26		#[derive(Clone, Default)]
27		pub struct NibbleVec<A: Array<Item = u8>> {
28		length: usize,
29		data: SmallVec<A>,
30		}
31
32		impl<A: Array<Item = u8>> NibbleVec<A> {
33		/// Create an empty nibble vector.
34	0	pub fn new() -> NibbleVec<A> {
35	0	NibbleVec {
36	0	length: 0,
37	0	data: SmallVec::new(),
38	0	}
39	0	}
40
41		/// Create a nibble vector from a vector of bytes.
42		///
43		/// Each byte is split into two 4-bit entries (MSB, LSB).
44		#[inline]
45	0	pub fn from_byte_vec(vec: Vec<u8>) -> NibbleVec<A> {
46	0	let length = 2 * vec.len();
47	0	NibbleVec {
48	0	length,
49	0	data: SmallVec::from_iter(vec),
50	0	}
51	0	}
52
53		/// Returns a byte slice of the nibble vector's contents.
54		#[inline]
55		pub fn as_bytes(&self) -> &[u8] {
56		&self.data[..]
57		}
58
59		/// Converts a nibble vector into a byte vector.
60		///
61		/// This consumes the nibble vector, so we do not need to copy its contents.
62		#[inline]
63		pub fn into_bytes(self) -> Vec<u8> {
64		self.data.to_vec()
65		}
66
67		/// Get the number of elements stored in the vector.
68		#[inline]
69	0	pub fn len(&self) -> usize {
70	0	self.length
71	0	}
72
73		/// Returns `true` if the nibble vector has a length of 0.
74		#[inline]
75	0	pub fn is_empty(&self) -> bool {
76	0	self.data.is_empty()
77	0	}
78
79		/// Fetch a single entry from the vector.
80		///
81		/// Guaranteed to be a value in the interval [0, 15].
82		///
83		/// Panics if `idx >= self.len()`.
84		#[inline]
85	0	pub fn get(&self, idx: usize) -> u8 {
86	0	if idx >= self.length {
87	0	panic!(
88	0	"NibbleVec index out of bounds: len is {}, index is {}",
89	0	self.length, idx
90	0	);
91	0	}
92	0	let vec_idx = idx / 2;
93	0	match idx % 2 {
94		// If the index is even, take the first (most significant) half of the stored byte.
95	0	0 => self.data[vec_idx] >> 4,
96		// If the index is odd, take the second (least significant) half.
97	0	_ => self.data[vec_idx] & 0x0F,
98		}
99	0	}
100
101		/// Add a single nibble to the vector.
102		///
103		/// Only the 4 least-significant bits of the value are used.
104		#[inline]
105	0	pub fn push(&mut self, val: u8) {
106	0	if self.length % 2 == 0 {
107	0	self.data.push(val << 4);
108	0	} else {
109	0	let vec_len = self.data.len();
110	0
111	0	// Zero the second half of the last byte just to be safe.
112	0	self.data[vec_len - 1] &= 0xF0;
113	0
114	0	// Write the new value.
115	0	self.data[vec_len - 1] \|= val & 0x0F;
116	0	}
117	0	self.length += 1;
118	0	}
119
120		/// Split the vector into two parts.
121		///
122		/// All elements at or following the given index are returned in a new `NibbleVec`,
123		/// with exactly `idx` elements remaining in this vector.
124		///
125		/// Panics if `idx > self.len()`.
126	0	pub fn split(&mut self, idx: usize) -> NibbleVec<A> {
127	0	// assert! is a few percent slower surprisingly
128	0	if idx > self.length {
129	0	panic!(
130	0	"attempted to split past vector end. len is {}, index is {}",
131	0	self.length, idx
132	0	);
133	0	} else if idx == self.length {
134	0	NibbleVec::new()
135	0	} else if idx % 2 == 0 {
136	0	self.split_even(idx)
137		} else {
138	0	self.split_odd(idx)
139		}
140	0	}
141
142		/// Split function for odd indices.
143		#[inline]
144	0	fn split_odd(&mut self, idx: usize) -> NibbleVec<A> {
145	0	let mut tail = NibbleVec::new();
146	0
147	0	// Perform an overlap copy, copying the last nibble of the original vector only if
148	0	// the length of the new tail is odd.
149	0	let tail_length = self.length - idx;
150	0	let take_last = tail_length % 2 == 1;
151	0	self.overlap_copy(
152	0	idx / 2,
153	0	self.data.len(),
154	0	&mut tail.data,
155	0	&mut tail.length,
156	0	take_last,
157	0	);
158	0
159	0	// Remove the copied bytes, being careful to skip the idx byte.
160	0	for _ in (idx / 2 + 1)..self.data.len() {
161	0	self.data.pop();
162	0	}
163
164		// Zero the second half of the index byte so as to maintain the last-nibble invariant.
165	0	self.data[idx / 2] &= 0xF0;
166	0
167	0	// Update the length of the first NibbleVec.
168	0	self.length = idx;
169	0
170	0	tail
171	0	}
172
173		/// Split function for even indices.
174		#[inline]
175	0	fn split_even(&mut self, idx: usize) -> NibbleVec<A> {
176	0	// Avoid allocating a temporary vector by copying all the bytes in order, then popping them.
177	0
178	0	// Possible to prove: l_d - ⌊i / 2⌋ = ⌊(l_v - i + 1) / 2⌋
179	0	// where l_d = self.data.len()
180	0	// l_v = self.length
181	0
182	0	let half_idx = idx / 2;
183	0	let mut tail = NibbleVec::new();
184
185		// Copy the bytes.
186	0	for i in half_idx..self.data.len() {
187	0	tail.data.push(self.data[i]);
188	0	}
189
190		// Pop the same bytes.
191	0	for _ in half_idx..self.data.len() {
192	0	self.data.pop();
193	0	}
194
195		// Update lengths.
196	0	tail.length = self.length - idx;
197	0	self.length = idx;
198	0
199	0	tail
200	0	}
201
202		/// Copy data between the second half of self.data[start] and
203		/// self.data[end - 1]. The second half of the last entry is included
204		/// if include_last is true.
205		#[inline]
206	0	fn overlap_copy(
207	0	&self,
208	0	start: usize,
209	0	end: usize,
210	0	vec: &mut SmallVec<A>,
211	0	length: &mut usize,
212	0	include_last: bool,
213	0	) {
214		// Copy up to the first half of the last byte.
215	0	for i in start..(end - 1) {
216	0	// The first half is the second half of the old entry.
217	0	let first_half = self.data[i] & 0x0f;
218	0
219	0	// The second half is the first half of the next entry.
220	0	let second_half = self.data[i + 1] >> 4;
221	0
222	0	vec.push((first_half << 4) \| second_half);
223	0	*length += 2;
224	0	}
225
226	0	if include_last {
227	0	let last = self.data[end - 1] & 0x0f;
228	0	vec.push(last << 4);
229	0	*length += 1;
230	0	}
231	0	}
232
233		/// Append another nibble vector whilst consuming this vector.
234		#[inline]
235	0	pub fn join(mut self, other: &NibbleVec<A>) -> NibbleVec<A> {
236	0	// If the length is even, we can append directly.
237	0	if self.length % 2 == 0 {
238	0	self.length += other.length;
239	0	self.data.extend_from_slice(&other.data);
240	0	return self;
241	0	}
242	0
243	0	// If the other vector is empty, bail out.
244	0	if other.is_empty() {
245	0	return self;
246	0	}
247	0
248	0	// If the length is odd, we have to perform an overlap copy.
249	0	// Copy the first half of the first element, to make the vector an even length.
250	0	self.push(other.get(0));
251	0
252	0	// Copy the rest of the vector using an overlap copy.
253	0	let take_last = other.len() % 2 == 0;
254	0	other.overlap_copy(
255	0	0,
256	0	other.data.len(),
257	0	&mut self.data,
258	0	&mut self.length,
259	0	take_last,
260	0	);
261	0
262	0	self
263	0	}
264		}
265
266		impl<A: Array<Item = u8>> PartialEq<NibbleVec<A>> for NibbleVec<A> {
267		#[inline]
268		fn eq(&self, other: &NibbleVec<A>) -> bool {
269		self.length == other.length && self.data == other.data
270		}
271		}
272
273		impl<A: Array<Item = u8>> Eq for NibbleVec<A> {}
274
275		/// Compare a `NibbleVec` and a slice of bytes element-by-element.
276		/// Bytes are not interpreted as two `NibbleVec` entries.
277		impl<A: Array<Item = u8>> PartialEq<[u8]> for NibbleVec<A> {
278		#[inline]
279		fn eq(&self, other: &[u8]) -> bool {
280		if other.len() != self.len() {
281		return false;
282		}
283
284		for (i, x) in other.iter().enumerate() {
285		if self.get(i) != *x {
286		return false;
287		}
288		}
289		true
290		}
291		}
292
293		impl<A: Array<Item = u8>> Debug for NibbleVec<A> {
294		fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
295		write!(fmt, "NibbleVec [")?;
296
297		if !self.is_empty() {
298		write!(fmt, "{}", self.get(0))?;
299		}
300
301		for i in 1..self.len() {
302		write!(fmt, ", {}", self.get(i))?;
303		}
304		write!(fmt, "]")
305		}
306		}
307
308		impl<A: Array<Item = u8>> From<Vec<u8>> for NibbleVec<A> {
309		#[inline]
310		fn from(v: Vec<u8>) -> NibbleVec<A> {
311		NibbleVec::from_byte_vec(v)
312		}
313		}
314
315		impl<'a, A: Array<Item = u8>> From<&'a [u8]> for NibbleVec<A> {
316		#[inline]
317		fn from(v: &[u8]) -> NibbleVec<A> {
318		NibbleVec::from_byte_vec(v.into())
319		}
320		}
321
322		impl<A: Array<Item = u8>> Into<Vec<u8>> for NibbleVec<A> {
323		#[inline]
324		fn into(self) -> Vec<u8> {
325		self.data.to_vec()
326		}
327		}
328
329		impl<'a, A: Array<Item = u8>> Into<Vec<u8>> for &'a NibbleVec<A> {
330		#[inline]
331		fn into(self) -> Vec<u8> {
332		self.data.to_vec()
333		}
334		}