onepass_base/
dict.rs

1use core::{
2    fmt::{self, Write},
3    ops::Deref,
4};
5use std::ops::Range;
6
7use blake2::Blake2b256;
8use digest::Digest;
9
10use crate::fmt::{DigestWriter, Lines, TsvField};
11
12/// This trait implements a hashed word list suitable for use in deterministic password generation.
13/// The hash may be used as part of a derivation path to make generated passwords depend upon the
14/// exact word list used.
15pub trait Dict: fmt::Debug + Send + Sync {
16    /// Returns the number of words in the list.
17    fn len(&self) -> usize;
18
19    /// Returns true iff the word list is empty.
20    fn is_empty(&self) -> bool {
21        self.len() == 0
22    }
23
24    /// Return the `i`th word in the list.
25    fn word(&self, i: usize) -> &str;
26
27    /// Return the unique BLAKE2b256 hash of this word list.
28    fn hash(&self) -> &[u8; 32];
29}
30
31/// This is a runtime generated, owned [`Dict`] with string slices out of some backing store.
32/// These slices may come from a `Vec<String>`, or else from slices out of a single `String`.
33#[derive(Debug, PartialEq, Eq, Hash)]
34pub struct BoxDict {
35    backing: Box<str>,
36    spans: Box<[Range<usize>]>,
37    hash: [u8; 32],
38}
39
40/// This type provides a [`Dict`] over non-owned data. It may be used in tests, or to implement a
41/// static compile-time dictionary, giving the compiler maximum freedom as to how to lay out the
42/// string slices.
43#[derive(Debug, PartialEq, Eq, Hash)]
44pub struct RefDict<'a>(&'a [&'a str], &'a [u8; 32]);
45
46impl BoxDict {
47    /// Construct a dictionary from a single string slice, taking each non-empty line, with leading
48    /// and trailing whitespace trimmed, as a single word.
49    pub fn from_lines(backing: impl Into<Box<str>>) -> Self {
50        let backing = backing.into();
51        let (words, hash) = canonicalize(backing.lines().map(str::trim));
52        let spans = adopt(&backing, words);
53        Self {
54            backing,
55            spans,
56            hash,
57        }
58    }
59
60    /// Construct a dictionary from a single string slice, with fields separated by a separator.
61    /// Individual words are not trimmed.
62    pub fn from_sep(backing: impl Into<Box<str>>, sep: &str) -> Self {
63        let backing = backing.into();
64        let (words, hash) = canonicalize(backing.split(sep));
65        let spans = adopt(&backing, words);
66        Self {
67            backing,
68            spans,
69            hash,
70        }
71    }
72}
73
74fn canonicalize<'a>(words: impl Iterator<Item = &'a str>) -> (Vec<&'a str>, [u8; 32]) {
75    let mut words: Vec<_> = words.filter(|&w| !w.is_empty()).collect();
76    words.sort_unstable();
77    words.dedup();
78    let mut w = DigestWriter(Blake2b256::new());
79    write!(w, "{}", Lines(words.iter().map(TsvField))).unwrap();
80    (words, w.0.finalize().into())
81}
82
83fn adopt(backing: &str, words: Vec<&str>) -> Box<[Range<usize>]> {
84    let base = backing.as_ptr() as usize;
85    words
86        .into_iter()
87        .map(|w| {
88            let offset = (w.as_ptr() as usize).checked_sub(base).unwrap();
89            let end = offset.checked_add(w.len()).unwrap();
90            assert!(end <= backing.len());
91            offset..end
92        })
93        .collect()
94}
95
96fn compact(words: Vec<&str>) -> (Box<str>, Box<[Range<usize>]>) {
97    let len = words.iter().copied().map(|w| w.len()).sum();
98    let mut backing = String::with_capacity(len);
99    let spans = words
100        .into_iter()
101        .map(|word| {
102            let start = backing.len();
103            backing.push_str(word);
104            start..backing.len()
105        })
106        .collect();
107    (backing.into(), spans)
108}
109
110impl<S: AsRef<str>> FromIterator<S> for BoxDict {
111    fn from_iter<T: IntoIterator<Item = S>>(iter: T) -> Self {
112        let words: Vec<_> = iter.into_iter().collect();
113        let (words, hash) = canonicalize(words.iter().map(S::as_ref));
114        let (backing, spans) = compact(words);
115        BoxDict {
116            backing,
117            spans,
118            hash,
119        }
120    }
121}
122
123impl<'a> RefDict<'a> {
124    /// Construct a dictionary from the given word slice and hash reference.
125    /// # Safety
126    /// This function is only safe if `hash` is the `BLAKE2b256` hash of the word list as if
127    /// constructed via `BoxDict::from_iter(words.into_iter())`.
128    pub const unsafe fn new(words: &'a [&'a str], hash: &'a [u8; 32]) -> Self {
129        RefDict(words, hash)
130    }
131}
132
133impl Deref for BoxDict {
134    type Target = dyn Dict;
135    fn deref(&self) -> &Self::Target {
136        self
137    }
138}
139
140impl Deref for RefDict<'static> {
141    type Target = dyn Dict;
142    fn deref(&self) -> &Self::Target {
143        self
144    }
145}
146
147impl Dict for BoxDict {
148    fn len(&self) -> usize {
149        self.spans.len()
150    }
151
152    fn word(&self, i: usize) -> &str {
153        &self.backing[self.spans[i].clone()]
154    }
155
156    fn hash(&self) -> &[u8; 32] {
157        &self.hash
158    }
159}
160
161impl Dict for RefDict<'_> {
162    fn len(&self) -> usize {
163        self.0.len()
164    }
165    fn word(&self, i: usize) -> &str {
166        self.0[i]
167    }
168    fn hash(&self) -> &[u8; 32] {
169        self.1
170    }
171}
172
173#[cfg(test)]
174mod tests {
175    use super::*;
176
177    #[test]
178    fn box_dict_hash_vectors() {
179        let tests: &[(&str, &str, Option<&str>)] = &[
180            (
181                "749a7ee32cf838199eae943516767f7ef02d49b212202f1aad74cacd645e2edf",
182                "bob\ndole",
183                None,
184            ),
185            (
186                "0e5751c026e543b2e8ab2eb06099daa1d1e5df47778f7787faab45cdf12fe3a8",
187                "",
188                None,
189            ),
190            (
191                "0e5751c026e543b2e8ab2eb06099daa1d1e5df47778f7787faab45cdf12fe3a8",
192                " \n",
193                None,
194            ),
195            (
196                "f9a96c938288e95ab3b8804104a69daf44e925fd962565233d9de5d26e951068",
197                "bob\ndole",
198                Some("\0"),
199            ),
200            (
201                "3b4312af5a1f7e9eb79c27b4503f734d303e6664d2df2796ec034b4c34195dbf",
202                "a\nb\nc",
203                None,
204            ),
205            (
206                "3b4312af5a1f7e9eb79c27b4503f734d303e6664d2df2796ec034b4c34195dbf",
207                "b\nc\na",
208                None,
209            ),
210            (
211                "3b4312af5a1f7e9eb79c27b4503f734d303e6664d2df2796ec034b4c34195dbf",
212                "  b \na   \nc\n\n\n",
213                None,
214            ),
215            (
216                "3b4312af5a1f7e9eb79c27b4503f734d303e6664d2df2796ec034b4c34195dbf",
217                "a\0b\0c",
218                Some("\0"),
219            ),
220            (
221                "3b4312af5a1f7e9eb79c27b4503f734d303e6664d2df2796ec034b4c34195dbf",
222                "c\0b\0a\0a\0a",
223                Some("\0"),
224            ),
225            (
226                "3b42ee5c745153f2fe8533b19c35411d8d45c70bbecf0dc3ac9e60b7eb5ea07d",
227                " \0",
228                Some("\0"),
229            ),
230            (
231                "ff11901891de4daf46c9ffc4a5c23ae22c4fa2597dc1beb86d2ef5bf87d9c878",
232                "\\\r\n\t",
233                Some("\0"),
234            ),
235            (
236                "dec3a7b8941401737abb9ff3f37cde4b47c79c5be60bba8ba2ffb02fb84864ba",
237                "a a",
238                None,
239            ),
240        ];
241        for &(want, inp, sep) in tests {
242            let dict = match sep {
243                None => BoxDict::from_lines(inp),
244                Some(sep) => BoxDict::from_sep(inp, sep),
245            };
246            assert_eq!(want, &hex::encode(dict.hash()), "{inp:?}");
247        }
248    }
249}
onepass_base/dict.rs

onepass_base/
dict.rs
