• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

vbpf / ebpf-verifier / 13955273819

19 Mar 2025 07:38PM UTC coverage: 88.66% (+0.5%) from 88.134%
13955273819

push

github

web-flow
Fix sign extension (#850)

* fix sign extension
* add exhaustive tests for sign extension of <=3 bits
* fix interval::size()
* streamline bit/width operations

---------
Signed-off-by: Elazar Gershuni <elazarg@gmail.com>

203 of 214 new or added lines in 9 files covered. (94.86%)

9 existing lines in 5 files now uncovered.

8639 of 9744 relevant lines covered (88.66%)

8977818.22 hits per line

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

92.86
/src/crab/interval.hpp
1
// Copyright (c) Prevail Verifier contributors.
2
// SPDX-License-Identifier: Apache-2.0
3
/*******************************************************************************
4
 *
5
 * A simple class for representing intervals and performing interval arithmetic.
6
 *
7
 ******************************************************************************/
8

9
#pragma once
10

11
#include <optional>
12
#include <utility>
13

14
#include "crab_utils/num_big.hpp"
15
#include "crab_utils/num_extended.hpp"
16
#include "crab_utils/stats.hpp"
17

18
namespace crab {
19

20
using bound_t = extended_number;
21

22
class interval_t final {
60,616,864✔
23
    bound_t _lb;
24
    bound_t _ub;
25

26
  public:
27
    static interval_t top() { return interval_t{bound_t::minus_infinity(), bound_t::plus_infinity()}; }
27,333,251✔
28

29
    static interval_t bottom() { return interval_t{}; }
191,148✔
30

31
    [[nodiscard]]
32
    std::optional<number_t> finite_size() const {
31,048✔
33
        return (_ub - _lb).number();
46,572✔
34
    }
35

36
  private:
37
    interval_t() : _lb(number_t{0}), _ub(-1) {}
254,118✔
38

39
  public:
40
    interval_t(const bound_t& lb, const bound_t& ub)
92,750,231✔
41
        : _lb(lb > ub ? bound_t{number_t{0}} : lb), _ub(lb > ub ? bound_t{-1} : ub) {}
92,750,231✔
42

43
    template <std::integral T>
44
    interval_t(T lb, T ub) : _lb(bound_t{lb}), _ub(bound_t{ub}) {
124,968✔
45
        if (lb > ub) {
124,968✔
UNCOV
46
            _lb = bound_t{number_t{0}};
×
UNCOV
47
            _ub = bound_t{-1};
×
48
        }
49
    }
124,968✔
50

51
    template <is_enum T>
52
    interval_t(T lb, T ub) : _lb(bound_t{lb}), _ub(bound_t{ub}) {
53
        if (lb > ub) {
54
            _lb = bound_t{number_t{0}};
55
            _ub = bound_t{-1};
56
        }
57
    }
58
    explicit interval_t(const bound_t& b)
13,114✔
59
        : _lb(b.is_infinite() ? bound_t{number_t{0}} : b), _ub(b.is_infinite() ? bound_t{-1} : b) {}
13,114✔
60

61
    explicit interval_t(const number_t& n) : _lb(n), _ub(n) {}
114,195,526✔
62
    explicit interval_t(std::integral auto n) : _lb(n), _ub(n) {}
239,880✔
63

64
    interval_t(const interval_t& i) = default;
760,128✔
65

66
    interval_t& operator=(const interval_t& i) = default;
42,573,206✔
67

68
    [[nodiscard]]
69
    bound_t lb() const {
5,049,021✔
70
        return _lb;
7,885,556✔
71
    }
72

73
    [[nodiscard]]
74
    bound_t ub() const {
5,954,672✔
75
        return _ub;
9,285,089✔
76
    }
77

78
    [[nodiscard]]
79
    std::tuple<bound_t, bound_t> pair() const {
25,068✔
80
        return {_lb, _ub};
25,068✔
81
    }
82

83
    template <std::integral T>
84
    [[nodiscard]]
85
    std::tuple<T, T> pair() const {
86
        return {_lb.narrow<T>(), _ub.narrow<T>()};
87
    }
88

89
    [[nodiscard]]
90
    std::tuple<number_t, number_t> pair_number() const {
712✔
91
        return {_lb.number().value(), _ub.number().value()};
1,780✔
92
    }
93

94
    template <std::integral T>
95
    [[nodiscard]]
96
    std::tuple<T, T> bound(T lb, T ub) const {
120,574✔
97
        const interval_t b = interval_t{lb, ub} & *this;
120,574✔
98
        if (b.is_bottom()) {
120,574✔
99
            CRAB_ERROR("Cannot convert bottom to tuple");
×
100
        }
101
        return {b._lb.narrow<T>(), b._ub.narrow<T>()};
180,861✔
102
    }
120,574✔
103

104
    template <is_enum T>
105
    [[nodiscard]]
106
    std::tuple<T, T> bound(T elb, T eub) const {
120,574✔
107
        using C = std::underlying_type_t<T>;
108
        auto [lb, ub] = bound(static_cast<C>(elb), static_cast<C>(eub));
120,574✔
109
        return {static_cast<T>(lb), static_cast<T>(ub)};
120,574✔
110
    }
111

112
    [[nodiscard]]
113
    explicit operator bool() const {
142,016✔
114
        return !is_bottom();
213,024✔
115
    }
116

117
    [[nodiscard]]
118
    bool is_bottom() const {
142,575,345✔
119
        return _lb > _ub;
102,093,750✔
120
    }
121

122
    [[nodiscard]]
123
    bool is_top() const {
2,203,391✔
124
        return _lb.is_infinite() && _ub.is_infinite();
2,201,673✔
125
    }
126

127
    bool operator==(const interval_t& x) const {
995,082✔
128
        if (is_bottom()) {
995,082✔
129
            return x.is_bottom();
×
130
        } else {
131
            return _lb == x._lb && _ub == x._ub;
995,082✔
132
        }
133
    }
134

135
    bool operator!=(const interval_t& x) const { return !operator==(x); }
269,296✔
136

137
    bool operator<=(const interval_t& x) const {
106,204✔
138
        if (is_bottom()) {
106,204✔
139
            return true;
140
        } else if (x.is_bottom()) {
106,204✔
141
            return false;
142
        } else {
143
            return x._lb <= _lb && _ub <= x._ub;
106,204✔
144
        }
145
    }
146

147
    interval_t operator|(const interval_t& x) const {
16,592✔
148
        if (is_bottom()) {
16,592✔
149
            return x;
6,756✔
150
        } else if (x.is_bottom()) {
9,836✔
151
            return *this;
7,272✔
152
        } else {
153
            return interval_t{std::min(_lb, x._lb), std::max(_ub, x._ub)};
5,128✔
154
        }
155
    }
156

157
    interval_t operator&(const interval_t& x) const {
912,748✔
158
        if (is_bottom() || x.is_bottom()) {
1,369,122✔
159
            return bottom();
×
160
        } else {
161
            return interval_t{std::max(_lb, x._lb), std::min(_ub, x._ub)};
1,825,496✔
162
        }
163
    }
164

165
    [[nodiscard]]
166
    interval_t widen(const interval_t& x) const {
167
        if (is_bottom()) {
168
            return x;
169
        } else if (x.is_bottom()) {
170
            return *this;
171
        } else {
172
            return interval_t{x._lb < _lb ? bound_t::minus_infinity() : _lb,
173
                              _ub < x._ub ? bound_t::plus_infinity() : _ub};
174
        }
175
    }
176

177
    template <typename Thresholds>
178
    interval_t widening_thresholds(interval_t x, const Thresholds& ts) {
179
        if (is_bottom()) {
180
            return x;
181
        } else if (x.is_bottom()) {
182
            return *this;
183
        } else {
184
            const bound_t lb = x._lb < _lb ? ts.get_prev(x._lb) : _lb;
185
            const bound_t ub = _ub < x._ub ? ts.get_next(x._ub) : _ub;
186
            return interval_t{lb, ub};
187
        }
188
    }
189

190
    [[nodiscard]]
191
    interval_t narrow(const interval_t& x) const {
192
        if (is_bottom() || x.is_bottom()) {
193
            return bottom();
194
        } else {
195
            return interval_t{_lb.is_infinite() && x._lb.is_finite() ? x._lb : _lb,
196
                              _ub.is_infinite() && x._ub.is_finite() ? x._ub : _ub};
197
        }
198
    }
199

200
    interval_t operator+(const interval_t& x) const {
28,001,094✔
201
        if (is_bottom() || x.is_bottom()) {
42,001,643✔
202
            return bottom();
×
203
        } else {
204
            return interval_t{_lb + x._lb, _ub + x._ub};
42,001,643✔
205
        }
206
    }
207

208
    interval_t& operator+=(const interval_t& x) { return operator=(operator+(x)); }
42,001,634✔
209

210
    interval_t operator-() const {
211
        if (is_bottom()) {
212
            return bottom();
213
        } else {
214
            return interval_t{-_ub, -_lb};
215
        }
216
    }
217

218
    interval_t operator-(const interval_t& x) const {
1,854✔
219
        if (is_bottom() || x.is_bottom()) {
2,781✔
220
            return bottom();
×
221
        } else {
222
            return interval_t{_lb - x._ub, _ub - x._lb};
2,781✔
223
        }
224
    }
225

226
    interval_t& operator-=(const interval_t& x) { return operator=(operator-(x)); }
227

228
    interval_t operator*(const interval_t& x) const;
229

230
    interval_t& operator*=(const interval_t& x) { return operator=(operator*(x)); }
231

232
    interval_t operator/(const interval_t& x) const;
233

234
    interval_t& operator/=(const interval_t& x) { return operator=(operator/(x)); }
235

236
    bound_t size() const {
1,047,956✔
237
        if (is_bottom()) {
1,047,956✔
238
            return bound_t{number_t{0}};
8,008✔
239
        }
240
        return _ub - _lb + 1;
2,079,896✔
241
    }
242

243
    [[nodiscard]]
244
    bool is_singleton() const {
1,983,774✔
245
        return _lb == _ub;
1,983,774✔
246
    }
247

248
    [[nodiscard]]
249
    std::optional<number_t> singleton() const {
1,253,946✔
250
        if (is_singleton()) {
1,253,946✔
251
            return _lb.number();
1,165,836✔
252
        } else {
253
            return std::optional<number_t>();
88,110✔
254
        }
255
    }
256

257
    bool contains(const number_t& n) const {
23,696,781✔
258
        if (is_bottom()) {
23,696,781✔
259
            return false;
88✔
260
        }
261
        const bound_t b{n};
35,544,908✔
262
        return _lb <= b && b <= _ub;
29,090,185✔
263
    }
23,696,605✔
264

265
    friend std::ostream& operator<<(std::ostream& o, const interval_t& interval);
266

267
    // division and remainder operations
268

269
    [[nodiscard]]
270
    interval_t sdiv(const interval_t& x) const;
271

272
    [[nodiscard]]
273
    interval_t udiv(const interval_t& x) const;
274

275
    [[nodiscard]]
276
    interval_t srem(const interval_t& x) const;
277

278
    [[nodiscard]]
279
    interval_t urem(const interval_t& x) const;
280

281
    // bitwise operations
282
    [[nodiscard]]
283
    interval_t bitwise_and(const interval_t& x) const;
284

285
    [[nodiscard]]
286
    interval_t bitwise_or(const interval_t& x) const;
287

288
    [[nodiscard]]
289
    interval_t bitwise_xor(const interval_t& x) const;
290

291
    [[nodiscard]]
292
    interval_t shl(const interval_t& x) const;
293

294
    [[nodiscard]]
295
    interval_t lshr(const interval_t& x) const;
296

297
    [[nodiscard]]
298
    interval_t ashr(const interval_t& x) const;
299

300
    interval_t sign_extend(bool is64) const = delete;
301
    [[nodiscard]]
302
    interval_t sign_extend(int width) const;
303

304
    interval_t zero_extend(bool is64) const = delete;
305
    [[nodiscard]]
306
    interval_t zero_extend(int width) const;
307

308
    template <std::signed_integral T>
309
    [[nodiscard]]
310
    interval_t truncate_to() const {
55,900✔
311
        return sign_extend(static_cast<int>(sizeof(T)) * 8);
55,900✔
312
    }
313

314
    template <std::unsigned_integral T>
315
    [[nodiscard]]
316
    interval_t truncate_to() const {
74,084✔
317
        return zero_extend(static_cast<int>(sizeof(T)) * 8);
74,084✔
318
    }
319

320
    interval_t signed_int(bool is64) const = delete;
321
    // Return an interval in the range [INT_MIN, INT_MAX] which can only
322
    // be represented as an svalue.
323
    static interval_t signed_int(const int width) {
62,854✔
324
        return interval_t{number_t::min_int(width), number_t::max_int(width)};
157,135✔
325
    }
326

327
    interval_t unsigned_int(bool is64) const = delete;
328
    // Return an interval in the range [0, UINT_MAX] which can only be
329
    // represented as a uvalue.
330
    static interval_t unsigned_int(const int width) { return interval_t{0, number_t::max_uint(width)}; }
725,031✔
331

332
    interval_t nonnegative(bool is64) const = delete;
333
    // Return a non-negative interval in the range [0, INT_MAX],
334
    // which can be represented as both an svalue and a uvalue.
335
    static interval_t nonnegative(const int width) { return interval_t{number_t{0}, number_t::max_int(width)}; }
204,000✔
336

337
    interval_t negative(bool is64) const = delete;
338
    // Return a negative interval in the range [INT_MIN, -1],
339
    // which can be represented as both an svalue and a uvalue.
340
    static interval_t negative(const int width) { return interval_t{number_t::min_int(width), number_t{-1}}; }
57,876✔
341

342
    interval_t unsigned_high(bool is64) const = delete;
343
    // Return an interval in the range [INT_MAX+1, UINT_MAX], which can only be represented as a uvalue.
344
    // The svalue equivalent using the same width would be negative().
345
    static interval_t unsigned_high(const int width) {
41,786✔
346
        return interval_t{number_t::max_int(width) + 1, number_t::max_uint(width)};
83,572✔
347
    }
348

349
    [[nodiscard]]
350
    std::string to_string() const;
351
}; //  class interval
352

353
namespace interval_operators {
354

355
inline interval_t operator+(const number_t& c, const interval_t& x) { return interval_t{c} + x; }
356

357
inline interval_t operator+(const interval_t& x, const number_t& c) { return x + interval_t{c}; }
358

359
inline interval_t operator*(const number_t& c, const interval_t& x) { return interval_t{c} * x; }
42,001,634✔
360

361
inline interval_t operator*(const interval_t& x, const number_t& c) { return x * interval_t{c}; }
362

363
inline interval_t operator/(const number_t& c, const interval_t& x) { return interval_t{c} / x; }
364

365
inline interval_t operator/(const interval_t& x, const number_t& c) { return x / interval_t{c}; }
366

367
inline interval_t operator-(const number_t& c, const interval_t& x) { return interval_t{c} - x; }
368

369
inline interval_t operator-(const interval_t& x, const number_t& c) { return x - interval_t{c}; }
370

371
} // namespace interval_operators
372

373
} // namespace crab
374

375
std::string to_string(const crab::interval_t& interval) noexcept;
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc