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
44namespace ue2 {
45
46/**
47 * \brief Exception thrown if a depth operation overflows.
48 */
49struct 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 */
55class depth : totally_ordered<depth> {
56public:
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
228private:
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 */
238struct 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 */
266DepthMinMax unionDepthMinMax(const DepthMinMax &a, const DepthMinMax &b);
267
268} // namespace ue2
269
270namespace std {
271
272template<>
273struct hash<ue2::depth> {
274 size_t operator()(const ue2::depth &d) const {
275 return d.hash();
276 }
277};
278
279template<>
280struct 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