1 // Copyright 2024, The Android Open Source Project
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 //! Helper functions to verify image buffers
16 use core::cmp::{max, min};
17 extern crate itertools_noalloc;
18 use itertools_noalloc::Itertools;
19
20 /// Check if provided buffers overlap in any way.
21 ///
22 /// Note that zero length buffer is considered to contain no elements.
23 /// And would not overlap with any other buffer.
24 ///
25 /// # Args
26 ///
27 /// * `buffers`: slice of buffers to verify
28 ///
29 /// # Returns
30 ///
31 /// * true: if any of the buffers have common elements
32 /// * false: if there are no common elements in buffers
is_overlap(buffers: &[&[u8]]) -> bool33 pub fn is_overlap(buffers: &[&[u8]]) -> bool {
34 // Compare each with each since we can't use alloc and sort buffers.
35 // Since the number of buffers we expect is not big, O(n^2) complexity will do.
36 //
37 // Note: this is nice way to find out if 2 ranges overlap:
38 // max(a_start, b_start) > min(a_end, b_end)) -> no overlap
39 buffers
40 .iter()
41 .filter(|buffer| !buffer.is_empty())
42 .map(|slice: &&[u8]| (slice.as_ptr(), slice.last_chunk::<1>().unwrap().as_ptr()))
43 .tuple_combinations()
44 .any(|((a_start, a_end), (b_start, b_end))| !(max(a_start, b_start) > min(a_end, b_end)))
45 }
46
47 #[cfg(test)]
48 mod tests {
49 use super::*;
50 use itertools::Itertools;
51
52 // Creates slice of specified range: [first; last)
53 // Max range value is SIZE = 64;
get_range(first: usize, last: usize) -> &'static [u8]54 fn get_range(first: usize, last: usize) -> &'static [u8] {
55 const SIZE: usize = 64;
56 assert!(first < SIZE);
57 assert!(last <= SIZE);
58 static BUFFER: &'static [u8; SIZE] = &[0; SIZE];
59 &BUFFER[first..last]
60 }
61
62 // Check if ranges overlap, testing all permutations
check_overlap(ranges_set: &[(usize, usize)]) -> bool63 fn check_overlap(ranges_set: &[(usize, usize)]) -> bool {
64 ranges_set.iter().permutations(ranges_set.len()).all(|ranges| {
65 let ranges_slices: Vec<&[u8]> =
66 ranges.iter().map(|&(start, end)| get_range(*start, *end)).collect();
67 is_overlap(&ranges_slices)
68 })
69 }
70
71 // Check if ranges don't overlap, testing all permutations
check_not_overlap(ranges_set: &[(usize, usize)]) -> bool72 fn check_not_overlap(ranges_set: &[(usize, usize)]) -> bool {
73 ranges_set.iter().permutations(ranges_set.len()).all(|ranges| {
74 let ranges_slices: Vec<&[u8]> =
75 ranges.iter().map(|&(start, end)| get_range(*start, *end)).collect();
76 !is_overlap(&ranges_slices)
77 })
78 }
79
80 #[test]
test_is_overlap_false()81 fn test_is_overlap_false() {
82 assert!(check_not_overlap(&[(10, 15), (20, 25), (30, 35)]));
83 }
84
85 #[test]
test_is_overlap_true()86 fn test_is_overlap_true() {
87 assert!(check_overlap(&[(10, 19), (15, 25)]));
88 }
89
90 #[test]
test_is_overlap_included()91 fn test_is_overlap_included() {
92 assert!(check_overlap(&[(10, 11), (10, 11)]));
93 assert!(check_overlap(&[(10, 12), (10, 12)]));
94 assert!(check_overlap(&[(10, 13), (11, 12)]));
95 assert!(check_overlap(&[(10, 14), (11, 13)]));
96 assert!(check_overlap(&[(10, 20), (15, 18)]));
97 assert!(check_overlap(&[(10, 20), (11, 19), (12, 18), (13, 17)]));
98 }
99
100 #[test]
test_is_overlap_touching()101 fn test_is_overlap_touching() {
102 assert!(check_not_overlap(&[(10, 20), (20, 30), (30, 31)]));
103 }
104
105 #[test]
test_is_overlap_last_element()106 fn test_is_overlap_last_element() {
107 assert!(check_overlap(&[(10, 20), (19, 21)]));
108 }
109
110 #[test]
test_is_overlap_short()111 fn test_is_overlap_short() {
112 assert!(check_not_overlap(&[(10, 11), (11, 12), (12, 13)]));
113 }
114
115 #[test]
test_is_overlap_empty_slice()116 fn test_is_overlap_empty_slice() {
117 assert!(check_not_overlap(&[]));
118 assert!(check_not_overlap(&[(10, 10)]));
119 assert!(check_not_overlap(&[(10, 20), (10, 10), (20, 30), (11, 11), (23, 23)]));
120 }
121 }
122