capsules_extra/
sip_hash.rs

1// Licensed under the Apache License, Version 2.0 or the MIT License.
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3// Copyright Tock Contributors 2022.
4
5//! Tock SipHash capsule.
6//!
7//! This is a async implementation of the SipHash.
8//!
9//! This capsule was originally written to be used as part of Tock's
10//! key/value store. SipHash was used as it is generally fast, while also
11//! being resilient against DOS attacks from userspace
12//! (unlike <https://github.com/servo/rust-fnv>).
13//!
14//! Read <https://github.com/veorq/SipHash/blob/master/README.md> for more
15//! details on SipHash.
16//!
17//! The implementation is based on the Rust implementation from
18//! rust-core, available here: <https://github.com/jedisct1/rust-siphash>
19//!
20//! Copyright 2012-2016 The Rust Project Developers.
21//! Copyright 2016-2021 Frank Denis.
22//! Copyright 2021 Western Digital
23//!
24//! Licensed under the Apache License, Version 2.0 LICENSE-APACHE or
25//! <http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
26//! LICENSE-MIT or <http://opensource.org/licenses/MIT>, at your
27//! option.
28
29use core::cell::Cell;
30use core::{cmp, mem};
31use kernel::deferred_call::{DeferredCall, DeferredCallClient};
32use kernel::hil::hasher::{Client, Hasher, SipHash};
33use kernel::utilities::cells::{OptionalCell, TakeCell};
34use kernel::utilities::leasable_buffer::SubSlice;
35use kernel::utilities::leasable_buffer::SubSliceMut;
36use kernel::utilities::leasable_buffer::SubSliceMutImmut;
37use kernel::ErrorCode;
38
39pub struct SipHasher24<'a> {
40    client: OptionalCell<&'a dyn Client<8>>,
41
42    hasher: Cell<SipHasher>,
43
44    add_data_deferred_call: Cell<bool>,
45    complete_deferred_call: Cell<bool>,
46    deferred_call: DeferredCall,
47
48    data_buffer: Cell<Option<SubSliceMutImmut<'static, u8>>>,
49    out_buffer: TakeCell<'static, [u8; 8]>,
50}
51
52#[derive(Debug, Clone, Copy)]
53struct SipHasher {
54    k0: u64,
55    k1: u64,
56    length: usize, // how many bytes we've processed
57    state: State,  // hash State
58    tail: u64,     // unprocessed bytes le
59    ntail: usize,  // how many bytes in tail are valid
60}
61
62#[derive(Debug, Clone, Copy)]
63struct State {
64    // v0, v2 and v1, v3 show up in pairs in the algorithm,
65    // and simd implementations of SipHash will use vectors
66    // of v02 and v13. By placing them in this order in the struct,
67    // the compiler can pick up on just a few simd optimizations by itself.
68    v0: u64,
69    v2: u64,
70    v1: u64,
71    v3: u64,
72}
73
74impl SipHasher24<'_> {
75    pub fn new() -> Self {
76        let hasher = SipHasher {
77            k0: 0,
78            k1: 0,
79            length: 0,
80            state: State {
81                v0: 0x736f6d6570736575,
82                v1: 0x646f72616e646f6d,
83                v2: 0x6c7967656e657261,
84                v3: 0x7465646279746573,
85            },
86            ntail: 0,
87            tail: 0,
88        };
89
90        Self {
91            client: OptionalCell::empty(),
92            hasher: Cell::new(hasher),
93            add_data_deferred_call: Cell::new(false),
94            complete_deferred_call: Cell::new(false),
95            deferred_call: DeferredCall::new(),
96            data_buffer: Cell::new(None),
97            out_buffer: TakeCell::empty(),
98        }
99    }
100
101    pub fn new_with_keys(k0: u64, k1: u64) -> Self {
102        let hasher = SipHasher {
103            k0,
104            k1,
105            length: 0,
106            state: State {
107                v0: 0x736f6d6570736575,
108                v1: 0x646f72616e646f6d,
109                v2: 0x6c7967656e657261,
110                v3: 0x7465646279746573,
111            },
112            ntail: 0,
113            tail: 0,
114        };
115
116        Self {
117            client: OptionalCell::empty(),
118            hasher: Cell::new(hasher),
119            add_data_deferred_call: Cell::new(false),
120            complete_deferred_call: Cell::new(false),
121            deferred_call: DeferredCall::new(),
122            data_buffer: Cell::new(None),
123            out_buffer: TakeCell::empty(),
124        }
125    }
126}
127
128macro_rules! compress {
129    ($state:expr) => {{
130        compress!($state.v0, $state.v1, $state.v2, $state.v3)
131    }};
132    ($v0:expr, $v1:expr, $v2:expr, $v3:expr) => {{
133        $v0 = $v0.wrapping_add($v1);
134        $v1 = $v1.rotate_left(13);
135        $v1 ^= $v0;
136        $v0 = $v0.rotate_left(32);
137        $v2 = $v2.wrapping_add($v3);
138        $v3 = $v3.rotate_left(16);
139        $v3 ^= $v2;
140        $v0 = $v0.wrapping_add($v3);
141        $v3 = $v3.rotate_left(21);
142        $v3 ^= $v0;
143        $v2 = $v2.wrapping_add($v1);
144        $v1 = $v1.rotate_left(17);
145        $v1 ^= $v2;
146        $v2 = $v2.rotate_left(32);
147    }};
148}
149
150fn read_le_u64(input: &[u8]) -> u64 {
151    let mut eight_buf: [u8; 8] = [0; 8];
152    for i in 0..8 {
153        eight_buf[i] = *input.get(i).unwrap_or(&0);
154    }
155    u64::from_le_bytes(eight_buf)
156}
157
158fn read_le_u16(input: &[u8]) -> u16 {
159    let (int_bytes, _rest) = input.split_at(mem::size_of::<u16>());
160    u16::from_le_bytes(int_bytes.try_into().unwrap())
161}
162
163#[inline]
164fn u8to64_le(buf: &[u8], start: usize, len: usize) -> u64 {
165    debug_assert!(len < 8);
166    let mut i = 0; // current byte index (from LSB) in the output u64
167    let mut out = 0;
168    if i + 3 < len {
169        out = read_le_u64(&buf[start + i..]);
170        i += 4;
171    }
172    if i + 1 < len {
173        out |= (read_le_u16(&buf[start + i..]) as u64) << (i * 8);
174        i += 2
175    }
176    if i < len {
177        out |= (buf[start + i] as u64) << (i * 8);
178        i += 1;
179    }
180    debug_assert_eq!(i, len);
181    out
182}
183
184impl<'a> Hasher<'a, 8> for SipHasher24<'a> {
185    fn set_client(&'a self, client: &'a dyn Client<8>) {
186        self.client.set(client);
187    }
188
189    fn add_data(
190        &self,
191        data: SubSlice<'static, u8>,
192    ) -> Result<usize, (ErrorCode, SubSlice<'static, u8>)> {
193        let length = data.len();
194        let mut hasher = self.hasher.get();
195
196        hasher.length += length;
197
198        let mut needed = 0;
199
200        if hasher.ntail != 0 {
201            needed = 8 - hasher.ntail;
202            hasher.tail |=
203                u8to64_le(data.as_slice(), 0, cmp::min(length, needed)) << (8 * hasher.ntail);
204            if length < needed {
205                return Ok(length);
206            } else {
207                hasher.state.v3 ^= hasher.tail;
208                compress!(&mut hasher.state);
209                compress!(&mut hasher.state);
210                hasher.state.v0 ^= hasher.tail;
211                hasher.ntail = 0;
212            }
213        }
214
215        // Buffered tail is now flushed, process new input.
216        let len = length - needed;
217        let left = len & 0x7;
218
219        let mut i = needed;
220        while i < len - left {
221            let mi = read_le_u64(&data[i..]);
222
223            hasher.state.v3 ^= mi;
224            compress!(&mut hasher.state);
225            compress!(&mut hasher.state);
226            hasher.state.v0 ^= mi;
227
228            i += 8;
229        }
230
231        hasher.tail = u8to64_le(data.as_slice(), i, left);
232        hasher.ntail = left;
233
234        self.hasher.set(hasher);
235        self.data_buffer
236            .set(Some(SubSliceMutImmut::Immutable(data)));
237
238        self.add_data_deferred_call.set(true);
239        self.deferred_call.set();
240
241        Ok(length)
242    }
243
244    fn add_mut_data(
245        &self,
246        mut data: SubSliceMut<'static, u8>,
247    ) -> Result<usize, (ErrorCode, SubSliceMut<'static, u8>)> {
248        let length = data.len();
249        let mut hasher = self.hasher.get();
250
251        hasher.length += length;
252
253        let mut needed = 0;
254
255        if hasher.ntail != 0 {
256            needed = 8 - hasher.ntail;
257            hasher.tail |=
258                u8to64_le(data.as_mut_slice(), 0, cmp::min(length, needed)) << (8 * hasher.ntail);
259            if length < needed {
260                return Ok(length);
261            } else {
262                hasher.state.v3 ^= hasher.tail;
263                compress!(&mut hasher.state);
264                compress!(&mut hasher.state);
265                hasher.state.v0 ^= hasher.tail;
266                hasher.ntail = 0;
267            }
268        }
269
270        // Buffered tail is now flushed, process new input.
271        let len = length - needed;
272        let left = len & 0x7;
273
274        let mut i = needed;
275        while i < len - left {
276            let mi = read_le_u64(&data[i..]);
277
278            hasher.state.v3 ^= mi;
279            compress!(&mut hasher.state);
280            compress!(&mut hasher.state);
281            hasher.state.v0 ^= mi;
282
283            i += 8;
284        }
285
286        hasher.tail = u8to64_le(data.as_slice(), i, left);
287        hasher.ntail = left;
288
289        self.hasher.set(hasher);
290        self.data_buffer.set(Some(SubSliceMutImmut::Mutable(data)));
291
292        self.add_data_deferred_call.set(true);
293        self.deferred_call.set();
294
295        Ok(length)
296    }
297
298    fn run(
299        &'a self,
300        digest: &'static mut [u8; 8],
301    ) -> Result<(), (ErrorCode, &'static mut [u8; 8])> {
302        let mut hasher = self.hasher.get();
303
304        let b: u64 = ((hasher.length as u64 & 0xff) << 56) | hasher.tail;
305
306        hasher.state.v3 ^= b;
307        compress!(&mut hasher.state);
308        compress!(&mut hasher.state);
309        hasher.state.v0 ^= b;
310
311        hasher.state.v2 ^= 0xff;
312        compress!(&mut hasher.state);
313        compress!(&mut hasher.state);
314        compress!(&mut hasher.state);
315        compress!(&mut hasher.state);
316
317        self.hasher.set(hasher);
318        self.out_buffer.replace(digest);
319
320        self.complete_deferred_call.set(true);
321        self.deferred_call.set();
322
323        Ok(())
324    }
325
326    fn clear_data(&self) {
327        let mut hasher = self.hasher.get();
328
329        hasher.length = 0;
330        hasher.state.v0 = hasher.k0 ^ 0x736f6d6570736575;
331        hasher.state.v1 = hasher.k1 ^ 0x646f72616e646f6d;
332        hasher.state.v2 = hasher.k0 ^ 0x6c7967656e657261;
333        hasher.state.v3 = hasher.k1 ^ 0x7465646279746573;
334        hasher.ntail = 0;
335
336        self.hasher.set(hasher);
337    }
338}
339
340impl SipHash for SipHasher24<'_> {
341    fn set_keys(&self, k0: u64, k1: u64) -> Result<(), ErrorCode> {
342        let mut hasher = self.hasher.get();
343
344        hasher.k0 = k0;
345        hasher.k1 = k1;
346
347        self.hasher.set(hasher);
348        self.clear_data();
349
350        Ok(())
351    }
352}
353
354impl DeferredCallClient for SipHasher24<'_> {
355    fn handle_deferred_call(&self) {
356        if self.add_data_deferred_call.get() {
357            self.add_data_deferred_call.set(false);
358
359            self.client.map(|client| {
360                self.data_buffer.take().map(|buffer| match buffer {
361                    SubSliceMutImmut::Immutable(b) => client.add_data_done(Ok(()), b),
362                    SubSliceMutImmut::Mutable(b) => client.add_mut_data_done(Ok(()), b),
363                });
364            });
365        }
366
367        if self.complete_deferred_call.get() {
368            self.complete_deferred_call.set(false);
369
370            self.client.map(|client| {
371                self.out_buffer.take().map(|buffer| {
372                    let state = self.hasher.get().state;
373
374                    let result = state.v0 ^ state.v1 ^ state.v2 ^ state.v3;
375                    buffer.copy_from_slice(&result.to_le_bytes());
376
377                    client.hash_done(Ok(()), buffer);
378                });
379            });
380        }
381    }
382
383    fn register(&'static self) {
384        self.deferred_call.register(self);
385    }
386}
capsules_extra/sip_hash.rs

capsules_extra/
sip_hash.rs
