1 // Copyright 2016 The Fuchsia Authors
2 // Copyright (c) 2014 Travis Geiselbrecht
3 //
4 // Use of this source code is governed by a MIT-style
5 // license that can be found in the LICENSE file or at
6 // https://opensource.org/licenses/MIT
7
8 #pragma once
9
10 #include <fbl/algorithm.h>
11 #include <fbl/limits.h>
12
13 // utility function to test that offset + len is entirely within a range
14 // returns false if out of range
15 // NOTE: only use unsigned lengths
16 template <typename O, typename L>
InRange(O offset,L len,O trim_to_len)17 static inline bool InRange(O offset, L len, O trim_to_len) {
18 static_assert(fbl::numeric_limits<O>::is_signed == false, "InRange requires unsigned type O");
19 static_assert(fbl::numeric_limits<L>::is_signed == false, "InRange requires unsigned type L");
20
21 // trim offset/len to the range
22 if (offset + len < offset) {
23 return false; // offset + len wrapped
24 }
25
26 // we started off the end of the range
27 if (offset > trim_to_len) {
28 return false;
29 }
30
31 // does the end exceed the range?
32 if (offset + len > trim_to_len) {
33 return false;
34 }
35
36 return true;
37 }
38
39 // utility function to trim offset + len to trim_to_len
40 // returns new length in *len_out
41 // returns false if out of range
42 // may return length 0 if it precisely trims
43 // NOTE: only use unsigned lengths
44 template <typename O, typename L>
TrimRange(O offset,L len,O trim_to_len,L * len_out)45 static inline bool TrimRange(O offset, L len, O trim_to_len, L* len_out) {
46 static_assert(fbl::numeric_limits<O>::is_signed == false, "TrimRange requires unsigned type O");
47 static_assert(fbl::numeric_limits<L>::is_signed == false, "TrimRange requires unsigned type L");
48
49 // start off returning the initial value
50 *len_out = len;
51
52 // trim offset/len to the range
53 if (offset + len < offset) {
54 return false; // offset + len wrapped
55 }
56
57 // we started off the end of the range
58 if (offset > trim_to_len) {
59 return false;
60 }
61
62 // trim to the range
63 if (offset + len > trim_to_len) {
64 *len_out = static_cast<L>(trim_to_len - offset);
65 }
66
67 return true;
68 }
69
70 // given two offset/length pairs, determine if they overlap at all
71 template <typename O, typename L>
Intersects(O offset1,L len1,O offset2,L len2)72 static inline bool Intersects(O offset1, L len1, O offset2, L len2) {
73 static_assert(fbl::numeric_limits<O>::is_signed == false, "Intersects requires unsigned type O");
74 static_assert(fbl::numeric_limits<L>::is_signed == false, "Intersects requires unsigned type L");
75
76 // Can't overlap a zero-length region.
77 if (len1 == 0 || len2 == 0) {
78 return false;
79 }
80
81 if (offset1 <= offset2) {
82 // doesn't intersect, 1 is completely below 2
83 if (offset1 + len1 <= offset2) {
84 return false;
85 }
86 } else if (offset1 >= offset2 + len2) {
87 // 1 is completely above 2
88 return false;
89 }
90
91 return true;
92 }
93
94 // given two offset/length pairs, determine if they overlap and compute the intersection
95 // returns results in *offset_out and *len_out
96 template <typename O, typename L>
GetIntersect(O offset1,L len1,O offset2,L len2,O * offset_out,L * len_out)97 static inline bool GetIntersect(O offset1, L len1, O offset2, L len2, O* offset_out, L* len_out) {
98 static_assert(fbl::numeric_limits<O>::is_signed == false, "GetIntersect requires unsigned type O");
99 static_assert(fbl::numeric_limits<L>::is_signed == false, "GetIntersect requires unsigned type L");
100
101 // see if they intersect at all
102 if (!Intersects(offset1, len1, offset2, len2)) {
103 return false;
104 }
105
106 // they intersect in some way, 2 cases
107 if (offset1 < offset2) {
108 // range 1 starts lower then range 2, but must extend into it or across it
109 *offset_out = offset2;
110 *len_out = fbl::min((offset1 + len1) - offset2, len2);
111 } else { // (offset2 <= offset1)
112 // range 2 starts lower then range 1, but must extend into it or across it
113 // also range 1 and two may start at the same address
114 *offset_out = offset1;
115 *len_out = fbl::min((offset2 + len2) - offset1, len1);
116 }
117
118 return true;
119 }
120