indexedlog/
base16.rs

1/*
2 * Copyright (c) Meta Platforms, Inc. and affiliates.
3 *
4 * This source code is licensed under the MIT license found in the
5 * LICENSE file in the root directory of this source tree.
6 */
7
8//! Base16 iterator.
9
10/// Iterating through base16 bytes (0 to 15).
11#[derive(Debug, Copy, Clone)]
12pub struct Base16Iter<'a, T: 'a>(&'a T, usize, usize);
13
14impl<'a, T: AsRef<[u8]>> Base16Iter<'a, T> {
15    /// Convert base256 binary sequence to a base16 iterator.
16    pub fn from_base256(binary: &'a T) -> Self {
17        let len = binary.as_ref().len() * 2;
18        Base16Iter(binary, 0, len)
19    }
20}
21
22/// Base16 iterator for `[u8]`
23impl<'a, T: AsRef<[u8]>> Iterator for Base16Iter<'a, T> {
24    type Item = u8;
25
26    #[inline]
27    fn next(&mut self) -> Option<u8> {
28        if self.2 <= self.1 {
29            None
30        } else {
31            let i = self.1;
32            self.1 = i + 1;
33            let v = self.0.as_ref()[i / 2];
34            if i & 1 == 0 { v >> 4 } else { v & 0xf }.into()
35        }
36    }
37
38    #[inline]
39    fn size_hint(&self) -> (usize, Option<usize>) {
40        let len = self.len();
41        (len, Some(len))
42    }
43
44    #[inline]
45    fn count(self) -> usize {
46        self.len()
47    }
48}
49
50impl<'a, T: AsRef<[u8]>> DoubleEndedIterator for Base16Iter<'a, T> {
51    #[inline]
52    fn next_back(&mut self) -> Option<Self::Item> {
53        if self.2 <= self.1 {
54            None
55        } else {
56            let i = self.2 - 1;
57            self.2 = i;
58            let v = self.0.as_ref()[i / 2];
59            if i & 1 == 0 { v >> 4 } else { v & 0xf }.into()
60        }
61    }
62}
63
64impl<'a, T: AsRef<[u8]>> ExactSizeIterator for Base16Iter<'a, T> {
65    #[inline]
66    fn len(&self) -> usize {
67        self.2 - self.1
68    }
69}
70
71impl<'a, T: AsRef<[u8]>> Base16Iter<'a, T> {
72    #[inline]
73    pub fn skip(self, n: usize) -> Self {
74        Base16Iter(self.0, self.1 + n, self.2)
75    }
76
77    #[inline]
78    pub fn take(self, n: usize) -> Self {
79        let end = self.2.min(self.1 + n);
80        Base16Iter(self.0, self.1, end)
81    }
82}
83
84/// Convert base16 to base256. base16 must have 2 * N items.
85///
86/// Panic if base16 has 2 * N + 1 items.
87pub(crate) fn base16_to_base256(base16: &[u8]) -> Vec<u8> {
88    assert!(base16.len() & 1 == 0);
89    let mut bytes = Vec::with_capacity(base16.len() / 2);
90    let mut next_byte: u8 = 0;
91    for (i, b16) in base16.iter().cloned().enumerate() {
92        if i & 1 == 0 {
93            next_byte = b16 << 4;
94        } else {
95            bytes.push(next_byte | b16);
96        }
97    }
98    bytes
99}
100
101/// Convert a single hex digit to base16 value.
102///
103/// Return 16 if the digit is invalid.
104#[inline]
105pub(crate) fn single_hex_to_base16(ch: u8) -> u8 {
106    // Does not depend on ASCII order (ex. b'1' - b'0' == 1).
107    // Compiler can turn this into a lookup table. It is fast when cached.
108    match ch {
109        b'0' => 0,
110        b'1' => 1,
111        b'2' => 2,
112        b'3' => 3,
113        b'4' => 4,
114        b'5' => 5,
115        b'6' => 6,
116        b'7' => 7,
117        b'8' => 8,
118        b'9' => 9,
119        b'a' | b'A' => 10,
120        b'b' | b'B' => 11,
121        b'c' | b'C' => 12,
122        b'd' | b'D' => 13,
123        b'e' | b'E' => 14,
124        b'f' | b'F' => 15,
125        _ => 16,
126    }
127}
128
129#[cfg(test)]
130mod tests {
131    use quickcheck::quickcheck;
132
133    use super::*;
134
135    quickcheck! {
136        fn check_skip_rev(src: Vec<u8>) -> bool {
137            let iter = Base16Iter::from_base256(&src);
138            let full: Vec<u8> = iter.clone().collect();
139            let rev: Vec<u8> = iter.clone().rev().collect();
140            (0..full.len()).all(|i| {
141                let v: Vec<u8> = iter.clone().skip(i).collect();
142                let r: Vec<u8> = iter.clone().skip(i).rev().rev().rev().collect();
143                v[..] == full[i..] && r[..] == rev[..(rev.len() - i)]
144            })
145        }
146
147        fn check_roundtrip(src: Vec<u8>) -> bool {
148            let iter = Base16Iter::from_base256(&src);
149            base16_to_base256(&iter.collect::<Vec<u8>>()) == src
150        }
151    }
152
153    // The below patterns (skip, zip, rev; skip, take, rev) are used in radix.rs.
154    // Make sure they work at iterator level without needing an extra container.
155
156    #[test]
157    fn test_zip_skip_rev() {
158        let x = [0x12, 0x34, 0x56, 0x21u8];
159        let y = [0x78, 0x90, 0xab, 0xcdu8];
160        let i = Base16Iter::from_base256(&x)
161            .skip(2)
162            .zip(Base16Iter::from_base256(&y).skip(3))
163            .rev(); // .rev() works directly
164        let v: Vec<(u8, u8)> = i.collect();
165        assert_eq!(v.capacity(), v.len());
166        assert_eq!(v, vec![(2, 0xd), (6, 0xc), (5, 0xb), (4, 0xa), (3, 0)]);
167    }
168
169    #[test]
170    fn test_skip_take_rev() {
171        let x = [0x12, 0x34, 0x56u8];
172        let i = Base16Iter::from_base256(&x).skip(3).take(3).rev(); // .rev() works directly
173        let v: Vec<u8> = i.collect();
174        assert_eq!(v, vec![6, 5, 4]);
175    }
176}
indexedlog/base16.rs

indexedlog/
base16.rs
