1 | /* |
2 | * Copyright (c) 2015-2017, Intel Corporation |
3 | * |
4 | * Redistribution and use in source and binary forms, with or without |
5 | * modification, are permitted provided that the following conditions are met: |
6 | * |
7 | * * Redistributions of source code must retain the above copyright notice, |
8 | * this list of conditions and the following disclaimer. |
9 | * * Redistributions in binary form must reproduce the above copyright |
10 | * notice, this list of conditions and the following disclaimer in the |
11 | * documentation and/or other materials provided with the distribution. |
12 | * * Neither the name of Intel Corporation nor the names of its contributors |
13 | * may be used to endorse or promote products derived from this software |
14 | * without specific prior written permission. |
15 | * |
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
26 | * POSSIBILITY OF SUCH DAMAGE. |
27 | */ |
28 | |
29 | /** \file |
30 | * \brief Data types used to represent depth quantities. |
31 | */ |
32 | |
33 | #ifndef DEPTH_H |
34 | #define DEPTH_H |
35 | |
36 | #include "ue2common.h" |
37 | #include "util/hash.h" |
38 | #include "util/operators.h" |
39 | |
40 | #ifdef DUMP_SUPPORT |
41 | #include <string> |
42 | #endif |
43 | |
44 | namespace ue2 { |
45 | |
46 | /** |
47 | * \brief Exception thrown if a depth operation overflows. |
48 | */ |
49 | struct DepthOverflowError {}; |
50 | |
51 | /** |
52 | * \brief Type used to represent depth information; value is either a count, |
53 | * or the special values "infinity" and "unreachable". |
54 | */ |
55 | class depth : totally_ordered<depth> { |
56 | public: |
57 | /** \brief The default depth is special value "unreachable". */ |
58 | depth() = default; |
59 | |
60 | explicit depth(u32 v) : val(v) { |
61 | if (v > max_value()) { |
62 | DEBUG_PRINTF("depth %u too large to represent!\n" , v); |
63 | throw DepthOverflowError(); |
64 | } |
65 | } |
66 | |
67 | static depth unreachable() { |
68 | depth d; |
69 | d.val = val_unreachable; |
70 | return d; |
71 | } |
72 | |
73 | static depth infinity() { |
74 | depth d; |
75 | d.val = val_infinity; |
76 | return d; |
77 | } |
78 | |
79 | /** \brief Returns the max finite value representable as a depth. */ |
80 | static constexpr u32 max_value() { return val_infinity - 1; } |
81 | |
82 | bool is_finite() const { return val < val_infinity; } |
83 | bool is_infinite() const { return val == val_infinity; } |
84 | bool is_unreachable() const { return val == val_unreachable; } |
85 | bool is_reachable() const { return !is_unreachable(); } |
86 | |
87 | /** \brief Convert a finite depth to an integer. */ |
88 | operator u32() const { |
89 | if (!is_finite()) { |
90 | throw DepthOverflowError(); |
91 | } |
92 | return val; |
93 | } |
94 | |
95 | bool operator<(const depth &d) const { return val < d.val; } |
96 | bool operator==(const depth &d) const { return val == d.val; } |
97 | |
98 | // The following comparison operators exist for use against integer types |
99 | // that are bigger than what we can safely convert to depth (such as those |
100 | // in extparam). |
101 | |
102 | bool operator<(u64a d) const { |
103 | if (!is_finite()) { |
104 | return false; |
105 | } |
106 | return val < d; |
107 | } |
108 | bool operator<=(u64a d) const { |
109 | if (!is_finite()) { |
110 | return false; |
111 | } |
112 | return val <= d; |
113 | } |
114 | bool operator==(u64a d) const { |
115 | if (!is_finite()) { |
116 | return false; |
117 | } |
118 | return val == d; |
119 | } |
120 | bool operator>(u64a d) const { return !(*this <= d); } |
121 | bool operator>=(u64a d) const { return !(*this < d); } |
122 | bool operator!=(u64a d) const { return !(*this == d); } |
123 | |
124 | depth operator+(const depth &d) const { |
125 | if (is_unreachable() || d.is_unreachable()) { |
126 | return unreachable(); |
127 | } |
128 | if (is_infinite() || d.is_infinite()) { |
129 | return infinity(); |
130 | } |
131 | |
132 | u64a rv = val + d.val; |
133 | if (rv >= val_infinity) { |
134 | DEBUG_PRINTF("depth %llu too large to represent!\n" , rv); |
135 | throw DepthOverflowError(); |
136 | } |
137 | |
138 | return depth((u32)rv); |
139 | } |
140 | |
141 | depth &operator+=(const depth &d) { |
142 | depth rv = *this + d; |
143 | *this = rv; |
144 | return *this; |
145 | } |
146 | |
147 | depth operator-(const depth &d) const { |
148 | if (!d.is_finite()) { |
149 | throw DepthOverflowError(); |
150 | } |
151 | |
152 | if (is_unreachable()) { |
153 | return unreachable(); |
154 | } |
155 | if (is_infinite()) { |
156 | return infinity(); |
157 | } |
158 | |
159 | if (val < d.val) { |
160 | throw DepthOverflowError(); |
161 | } |
162 | |
163 | u32 rv = val - d.val; |
164 | return depth(rv); |
165 | } |
166 | |
167 | depth &operator-=(const depth &d) { |
168 | depth rv = *this - d; |
169 | *this = rv; |
170 | return *this; |
171 | } |
172 | |
173 | depth operator+(s32 d) const { |
174 | if (is_unreachable()) { |
175 | return unreachable(); |
176 | } |
177 | if (is_infinite()) { |
178 | return infinity(); |
179 | } |
180 | |
181 | s64a rv = val + d; |
182 | if (rv < 0 || (u64a)rv >= val_infinity) { |
183 | DEBUG_PRINTF("depth %lld too large to represent!\n" , rv); |
184 | throw DepthOverflowError(); |
185 | } |
186 | |
187 | return depth((u32)rv); |
188 | } |
189 | |
190 | depth operator+=(s32 d) { |
191 | depth rv = *this + d; |
192 | *this = rv; |
193 | return *this; |
194 | } |
195 | |
196 | depth operator-(s32 d) const { |
197 | if (is_unreachable()) { |
198 | return unreachable(); |
199 | } |
200 | if (is_infinite()) { |
201 | return infinity(); |
202 | } |
203 | |
204 | s64a rv = val - d; |
205 | if (rv < 0 || (u64a)rv >= val_infinity) { |
206 | DEBUG_PRINTF("depth %lld too large to represent!\n" , rv); |
207 | throw DepthOverflowError(); |
208 | } |
209 | |
210 | return depth((u32)rv); |
211 | } |
212 | |
213 | depth operator-=(s32 d) { |
214 | depth rv = *this - d; |
215 | *this = rv; |
216 | return *this; |
217 | } |
218 | |
219 | #ifdef DUMP_SUPPORT |
220 | /** \brief Render as a string, useful for debugging. */ |
221 | std::string str() const; |
222 | #endif |
223 | |
224 | size_t hash() const { |
225 | return val; |
226 | } |
227 | |
228 | private: |
229 | static constexpr u32 val_infinity = (1u << 31) - 1; |
230 | static constexpr u32 val_unreachable = 1u << 31; |
231 | |
232 | u32 val = val_unreachable; |
233 | }; |
234 | |
235 | /** |
236 | * \brief Encapsulates a min/max pair. |
237 | */ |
238 | struct DepthMinMax : totally_ordered<DepthMinMax> { |
239 | depth min{depth::infinity()}; |
240 | depth max{0}; |
241 | |
242 | DepthMinMax() = default; |
243 | DepthMinMax(const depth &mn, const depth &mx) : min(mn), max(mx) {} |
244 | |
245 | bool operator<(const DepthMinMax &b) const { |
246 | if (min != b.min) { |
247 | return min < b.min; |
248 | } |
249 | return max < b.max; |
250 | } |
251 | |
252 | bool operator==(const DepthMinMax &b) const { |
253 | return min == b.min && max == b.max; |
254 | } |
255 | |
256 | #ifdef DUMP_SUPPORT |
257 | /** \brief Render as a string, useful for debugging. */ |
258 | std::string str() const; |
259 | #endif |
260 | |
261 | }; |
262 | |
263 | /** |
264 | * \brief Merge two DepthMinMax values together to produce their union. |
265 | */ |
266 | DepthMinMax unionDepthMinMax(const DepthMinMax &a, const DepthMinMax &b); |
267 | |
268 | } // namespace ue2 |
269 | |
270 | namespace std { |
271 | |
272 | template<> |
273 | struct hash<ue2::depth> { |
274 | size_t operator()(const ue2::depth &d) const { |
275 | return d.hash(); |
276 | } |
277 | }; |
278 | |
279 | template<> |
280 | struct hash<ue2::DepthMinMax> { |
281 | size_t operator()(const ue2::DepthMinMax &d) const { |
282 | return hash_all(d.min, d.max); |
283 | } |
284 | }; |
285 | |
286 | } // namespace |
287 | |
288 | #endif // DEPTH_H |
289 | |