2911504003

Build Type

github

Committed by GitHub

Commit Message

<a href="https://github.com/google/OpenSK/commit/<a class=hub.com/google/OpenSK/commit/<a class="double-link" href="https://git"><a class=hub.com/google/OpenSK/commit/<a class="double-link" href="https://git"><a class=hub.com/google/OpenSK/commit/<a class="double-link" href="https://git"><a class=hub.com/google/OpenSK/commit/b9f2f4028324e17dfb04f35f236e27f83dbe2c71">b9f2f4028">&lt;a href=&quot;https://github.com/google/OpenSK/commit/</a><a class="double-link" href="https://github.com/google/OpenSK/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/google/OpenSK/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/google/OpenSK/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/google/OpenSK/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/google/OpenSK/commit/b9f2f4028324e17dfb04f35f236e27f83dbe2c71">b9f2f4028</a><a href="https://github.com/google/OpenSK/commit/b9f2f4028324e17dfb04f35f236e27f83dbe2c71">&quot;&gt;&amp;lt;a href=&amp;quot;https://github.com/google/OpenSK/commit/&lt;/a&gt;&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/google/OpenSK/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/google/OpenSK/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/google/OpenSK/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/google/OpenSK/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/google/OpenSK/commit/b9f2f4028324e17dfb04f35f236e27f83dbe2c71&quot;&gt;b9f2f4028&lt;/a&gt;&lt;a href=&quot;https://github.com/google/OpenSK/commit/b9f2f4028324e17dfb04f35f236e27f83dbe2c71&quot;&gt;&amp;quot;&amp;gt;&amp;amp;lt;a href=&amp;amp;quot;https://github.com/google/OpenSK/commit/&amp;lt;/a&amp;gt;&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://github.com/google/OpenSK/commit/&amp;amp;lt;a class=&amp;amp;quot;double-link&amp;amp;quot; href=&amp;amp;quot;htt... (continued)

Pull Request Pull Request #530: Add basic setup for multi-PIN

Run Details

521 of 521 new or added lines in 10 files covered. (100.0%)

14805 of 16710 relevant lines covered (88.6%)

522219.25 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

77.14

/libraries/persistent_store/src/concat.rs

// Copyright 2022 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

//! Support for concatenated entries.
//!
//! This module permits to store multiple indexed values under the same key by concatenation. Such
//! values must be at most 255 bytes and there can't be more than 255 such values under the same
//! key (they are indexed with a `u8`).
//!
//! The rationale for using those particular constraints is that we want the number of bits to store
//! the index and the number of bits to store the length to fit in an integer number of bytes
//! (because the values are an integer number of bytes). Using only one byte is too restrictive
//! (e.g. 8 values of at most 31 bytes or 16 values of at most 15 bytes). Using 2 bytes is plenty of
//! space, so using one byte for each field makes parsing simpler and faster.
//!
//! The format is thus `(index:u8 length:u8 payload:[u8; length])*`. The concatenation is not
//! particularly sorted.

use crate::{Storage, Store, StoreError, StoreResult};
use alloc::vec::Vec;
use core::cmp::Ordering;
use core::ops::Range;

/// Reads a value from a concatenated entry.
pub fn read(store: &Store<impl Storage>, key: usize, index: u8) -> StoreResult<Option<Vec<u8>>> {
    let values = match store.find(key)? {
        None => return Ok(None),
        Some(x) => x,
    };
    Ok(find(&values, index)?.map(|range| values[range].to_vec()))
}

/// Writes a value to a concatenated entry.
pub fn write(
    store: &mut Store<impl Storage>,
    key: usize,
    index: u8,
    value: &[u8],
) -> StoreResult<()> {
    if value.len() > 255 {
        return Err(StoreError::InvalidArgument);
    }
    let mut values = store.find(key)?.unwrap_or(vec![]);
    match find(&values, index)? {
        None => {
            values.push(index);
            values.push(value.len() as u8);
            values.extend_from_slice(value);
        }
        Some(mut range) => {
            values[range.start - 1] = value.len() as u8;
            match range.len().cmp(&value.len()) {
                Ordering::Less => {
                    let diff = value.len() - range.len();
                    values.resize(values.len() + diff, 0);
                    values[range.end..].rotate_right(diff);
                    range.end += diff;
                }
                Ordering::Equal => (),
                Ordering::Greater => {
                    let diff = range.len() - value.len();
                    range.end -= diff;
                    values[range.end..].rotate_left(diff);
                    values.truncate(values.len() - diff);
                }
            }
            values[range].copy_from_slice(value);
        }
    }
    store.insert(key, &values)
}

/// Deletes the value from a concatenated entry.
pub fn delete(store: &mut Store<impl Storage>, key: usize, index: u8) -> StoreResult<()> {
    let mut values = match store.find(key)? {
        None => return Ok(()),
        Some(x) => x,
    };
    let mut range = match find(&values, index)? {
        None => return Ok(()),
        Some(x) => x,
    };
    range.start -= 2;
    values[range.start..].rotate_left(range.len());
    values.truncate(values.len() - range.len());
    store.insert(key, &values)
}

fn find(values: &[u8], index: u8) -> StoreResult<Option<Range<usize>>> {
    let mut pos = 0;
    while pos < values.len() {
        if pos == values.len() - 1 {
            return Err(StoreError::InvalidStorage);
        }
        let len = values[pos + 1] as usize;
        if len > values.len() - 2 || pos > values.len() - 2 - len {
            return Err(StoreError::InvalidStorage);
        }
        if index == values[pos] {
            return Ok(Some(pos + 2..pos + 2 + len));
        }
        pos += 2 + len;
    }
    Ok(None)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::test::MINIMAL;

    #[test]
    fn read_empty_entry() {
        let store = MINIMAL.new_store();
        assert_eq!(read(&store, 0, 0), Ok(None));
        assert_eq!(read(&store, 0, 1), Ok(None));
    }

    #[test]
    fn read_missing_value() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo\x02\x05hello".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(read(&store, 0, 1), Ok(None));
    }

    #[test]
    fn read_existing_value() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo\x02\x05hello".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(read(&store, 0, 0), Ok(Some(b"foo".to_vec())));
        assert_eq!(read(&store, 0, 2), Ok(Some(b"hello".to_vec())));
    }

    #[test]
    fn read_invalid_entry_too_long() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo\x02\x08hello".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(read(&store, 0, 1), Err(StoreError::InvalidStorage));
    }

    #[test]
    fn read_invalid_entry_too_short() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo\x02".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(read(&store, 0, 1), Err(StoreError::InvalidStorage));
    }

    #[test]
    fn write_empty_entry() {
        let mut store = MINIMAL.new_store();
        assert_eq!(write(&mut store, 0, 0, b"foo"), Ok(()));
        assert_eq!(store.find(0), Ok(Some(b"\x00\x03foo".to_vec())));
    }

    #[test]
    fn write_missing_value() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(write(&mut store, 0, 1, b"bar"), Ok(()));
        assert_eq!(store.find(0), Ok(Some(b"\x00\x03foo\x01\x03bar".to_vec())));
    }

    #[test]
    fn write_existing_value_same_size() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo\x02\x05hello".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(write(&mut store, 0, 0, b"bar"), Ok(()));
        assert_eq!(
            store.find(0),
            Ok(Some(b"\x00\x03bar\x02\x05hello".to_vec()))
        );
    }

    #[test]
    fn write_existing_value_longer() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo\x02\x05hello".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(write(&mut store, 0, 0, b"barrage"), Ok(()));
        assert_eq!(
            store.find(0),
            Ok(Some(b"\x00\x07barrage\x02\x05hello".to_vec()))
        );
    }

    #[test]
    fn write_existing_value_shorter() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x08football\x02\x05hello".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(write(&mut store, 0, 0, b"bar"), Ok(()));
        assert_eq!(
            store.find(0),
            Ok(Some(b"\x00\x03bar\x02\x05hello".to_vec()))
        );
    }

    #[test]
    fn delete_empty_entry() {
        let mut store = MINIMAL.new_store();
        assert_eq!(delete(&mut store, 0, 0), Ok(()));
        assert_eq!(delete(&mut store, 0, 1), Ok(()));
    }

    #[test]
    fn delete_missing_value() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo\x02\x05hello".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(delete(&mut store, 0, 1), Ok(()));
        assert_eq!(
            store.find(0),
            Ok(Some(b"\x00\x03foo\x02\x05hello".to_vec()))
        );
    }

    #[test]
    fn delete_existing_value() {
        let mut store = MINIMAL.new_store();
        let value = b"\x00\x03foo\x02\x05hello".to_vec();
        store.insert(0, &value).unwrap();
        assert_eq!(delete(&mut store, 0, 0), Ok(()));
        assert_eq!(store.find(0), Ok(Some(b"\x02\x05hello".to_vec())));
    }
}

1	// Copyright 2022 Google LLC
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	//! Support for concatenated entries.
16	//!
17	//! This module permits to store multiple indexed values under the same key by concatenation. Such
18	//! values must be at most 255 bytes and there can't be more than 255 such values under the same
19	//! key (they are indexed with a `u8`).
20	//!
21	//! The rationale for using those particular constraints is that we want the number of bits to store
22	//! the index and the number of bits to store the length to fit in an integer number of bytes
23	//! (because the values are an integer number of bytes). Using only one byte is too restrictive
24	//! (e.g. 8 values of at most 31 bytes or 16 values of at most 15 bytes). Using 2 bytes is plenty of
25	//! space, so using one byte for each field makes parsing simpler and faster.
26	//!
27	//! The format is thus `(index:u8 length:u8 payload:[u8; length])*`. The concatenation is not
28	//! particularly sorted.
29
30	use crate::{Storage, Store, StoreError, StoreResult};
31	use alloc::vec::Vec;
32	use core::cmp::Ordering;
33	use core::ops::Range;
34
35	/// Reads a value from a concatenated entry.
36	pub fn read(store: &Store<impl Storage>, key: usize, index: u8) -> StoreResult<Option<Vec<u8>>> {	160✔
37	let values = match store.find(key)? {	160✔
38	None => return Ok(None),	160✔
39	Some(x) => x,	82✔
40	};
41	Ok(find(&values, index)?.map(\|range\| values[range].to_vec()))	82✔
42	}	160✔
43
44	/// Writes a value to a concatenated entry.
45	pub fn write(	54✔
46	store: &mut Store<impl Storage>,	54✔
47	key: usize,	54✔
48	index: u8,	54✔
49	value: &[u8],	54✔
50	) -> StoreResult<()> {	54✔
51	if value.len() > 255 {	54✔
52	return Err(StoreError::InvalidArgument);	×
53	}	54✔
54	let mut values = store.find(key)?.unwrap_or(vec![]);	54✔
55	match find(&values, index)? {	54✔
56	None => {	54✔
57	values.push(index);	51✔
58	values.push(value.len() as u8);	51✔
59	values.extend_from_slice(value);	51✔
60	}	51✔
61	Some(mut range) => {	3✔
62	values[range.start - 1] = value.len() as u8;	3✔
63	match range.len().cmp(&value.len()) {	3✔
64	Ordering::Less => {	3✔
65	let diff = value.len() - range.len();	×
66	values.resize(values.len() + diff, 0);	×
67	values[range.end..].rotate_right(diff);	×
68	range.end += diff;	×
69	}	×
70	Ordering::Equal => (),	3✔
71	Ordering::Greater => {	×
72	let diff = range.len() - value.len();	×
73	range.end -= diff;	×
74	values[range.end..].rotate_left(diff);	×
75	values.truncate(values.len() - diff);	×
76	}	×
77	}
78	values[range].copy_from_slice(value);	3✔
79	}
80	}
81	store.insert(key, &values)	54✔
82	}	54✔
83
84	/// Deletes the value from a concatenated entry.
85	pub fn delete(store: &mut Store<impl Storage>, key: usize, index: u8) -> StoreResult<()> {	47✔
86	let mut values = match store.find(key)? {	47✔
87	None => return Ok(()),	47✔
88	Some(x) => x,	1✔
89	};
90	let mut range = match find(&values, index)? {	1✔
91	None => return Ok(()),	1✔
92	Some(x) => x,	1✔
93	};	1✔
94	range.start -= 2;	1✔
95	values[range.start..].rotate_left(range.len());	1✔
96	values.truncate(values.len() - range.len());	1✔
97	store.insert(key, &values)	1✔
98	}	47✔
99
100	fn find(values: &[u8], index: u8) -> StoreResult<Option<Range<usize>>> {	685✔
101	let mut pos = 0;	685✔
102	while pos < values.len() {	685✔
103	if pos == values.len() - 1 {	425✔
104	return Err(StoreError::InvalidStorage);	×
105	}	425✔
106	let len = values[pos + 1] as usize;	425✔
107	if len > values.len() - 2 \|\| pos > values.len() - 2 - len {	425✔
108	return Err(StoreError::InvalidStorage);	×
109	}	425✔
110	if index == values[pos] {	425✔
111	return Ok(Some(pos + 2..pos + 2 + len));	425✔
112	}	×
113	pos += 2 + len;	×
114	}
115	Ok(None)	260✔
116	}	685✔
117
118	#[cfg(test)]
119	mod tests {
120	use super::*;
121	use crate::test::MINIMAL;
122
123	#[test]
124	fn read_empty_entry() {
125	let store = MINIMAL.new_store();
126	assert_eq!(read(&store, 0, 0), Ok(None));
127	assert_eq!(read(&store, 0, 1), Ok(None));
128	}
129
130	#[test]
131	fn read_missing_value() {
132	let mut store = MINIMAL.new_store();
133	let value = b"\x00\x03foo\x02\x05hello".to_vec();
134	store.insert(0, &value).unwrap();
135	assert_eq!(read(&store, 0, 1), Ok(None));
136	}
137
138	#[test]
139	fn read_existing_value() {
140	let mut store = MINIMAL.new_store();
141	let value = b"\x00\x03foo\x02\x05hello".to_vec();
142	store.insert(0, &value).unwrap();
143	assert_eq!(read(&store, 0, 0), Ok(Some(b"foo".to_vec())));
144	assert_eq!(read(&store, 0, 2), Ok(Some(b"hello".to_vec())));
145	}
146
147	#[test]
148	fn read_invalid_entry_too_long() {
149	let mut store = MINIMAL.new_store();
150	let value = b"\x00\x03foo\x02\x08hello".to_vec();
151	store.insert(0, &value).unwrap();
152	assert_eq!(read(&store, 0, 1), Err(StoreError::InvalidStorage));
153	}
154
155	#[test]
156	fn read_invalid_entry_too_short() {
157	let mut store = MINIMAL.new_store();
158	let value = b"\x00\x03foo\x02".to_vec();
159	store.insert(0, &value).unwrap();
160	assert_eq!(read(&store, 0, 1), Err(StoreError::InvalidStorage));
161	}
162
163	#[test]
164	fn write_empty_entry() {
165	let mut store = MINIMAL.new_store();
166	assert_eq!(write(&mut store, 0, 0, b"foo"), Ok(()));
167	assert_eq!(store.find(0), Ok(Some(b"\x00\x03foo".to_vec())));
168	}
169
170	#[test]
171	fn write_missing_value() {
172	let mut store = MINIMAL.new_store();
173	let value = b"\x00\x03foo".to_vec();
174	store.insert(0, &value).unwrap();
175	assert_eq!(write(&mut store, 0, 1, b"bar"), Ok(()));
176	assert_eq!(store.find(0), Ok(Some(b"\x00\x03foo\x01\x03bar".to_vec())));
177	}
178
179	#[test]
180	fn write_existing_value_same_size() {
181	let mut store = MINIMAL.new_store();
182	let value = b"\x00\x03foo\x02\x05hello".to_vec();
183	store.insert(0, &value).unwrap();
184	assert_eq!(write(&mut store, 0, 0, b"bar"), Ok(()));
185	assert_eq!(
186	store.find(0),
187	Ok(Some(b"\x00\x03bar\x02\x05hello".to_vec()))
188	);
189	}
190
191	#[test]
192	fn write_existing_value_longer() {
193	let mut store = MINIMAL.new_store();
194	let value = b"\x00\x03foo\x02\x05hello".to_vec();
195	store.insert(0, &value).unwrap();
196	assert_eq!(write(&mut store, 0, 0, b"barrage"), Ok(()));
197	assert_eq!(
198	store.find(0),
199	Ok(Some(b"\x00\x07barrage\x02\x05hello".to_vec()))
200	);
201	}
202
203	#[test]
204	fn write_existing_value_shorter() {
205	let mut store = MINIMAL.new_store();
206	let value = b"\x00\x08football\x02\x05hello".to_vec();
207	store.insert(0, &value).unwrap();
208	assert_eq!(write(&mut store, 0, 0, b"bar"), Ok(()));
209	assert_eq!(
210	store.find(0),
211	Ok(Some(b"\x00\x03bar\x02\x05hello".to_vec()))
212	);
213	}
214
215	#[test]
216	fn delete_empty_entry() {
217	let mut store = MINIMAL.new_store();
218	assert_eq!(delete(&mut store, 0, 0), Ok(()));
219	assert_eq!(delete(&mut store, 0, 1), Ok(()));
220	}
221
222	#[test]
223	fn delete_missing_value() {
224	let mut store = MINIMAL.new_store();
225	let value = b"\x00\x03foo\x02\x05hello".to_vec();
226	store.insert(0, &value).unwrap();
227	assert_eq!(delete(&mut store, 0, 1), Ok(()));
228	assert_eq!(
229	store.find(0),
230	Ok(Some(b"\x00\x03foo\x02\x05hello".to_vec()))
231	);
232	}
233
234	#[test]
235	fn delete_existing_value() {
236	let mut store = MINIMAL.new_store();
237	let value = b"\x00\x03foo\x02\x05hello".to_vec();
238	store.insert(0, &value).unwrap();
239	assert_eq!(delete(&mut store, 0, 0), Ok(()));
240	assert_eq!(store.find(0), Ok(Some(b"\x02\x05hello".to_vec())));
241	}
242	}

google / OpenSK / 2911504003

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous