1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
#pragma once
#include <limits.h>
#include <algorithm>
#include <iostream>
#include <utility>
namespace itv {
//==============================================================================
// Definitions of signed and unsigned intervals for bitwise operations
//==============================================================================
// Intervals are represented as pairs of numbers.
template <typename T>
struct BitwiseInterval {
T lo;
T hi;
};
// We need signed and unisgned intervals
using SInterval = BitwiseInterval<int>;
using UInterval = BitwiseInterval<unsigned int>;
// Empty intervals represented by (.lo > .hi)
constexpr UInterval UEMPTY{UINT_MAX, 0};
constexpr SInterval SEMPTY{INT_MAX, INT_MIN};
//==============================================================================
// Predicates
//==============================================================================
// Empty intervals are intervals such that: lo > hi
template <typename T>
bool isEmpty(const BitwiseInterval<T>& i)
{
return i.lo > i.hi;
}
// Equality of intervals.
template <typename T>
bool operator==(const BitwiseInterval<T>& a, const BitwiseInterval<T>& b)
{
if (isEmpty(a)) {
return isEmpty(b);
}
return (a.lo == b.lo) && (a.hi == b.hi);
}
// Equality of intervals.
template <typename T>
bool operator!=(const BitwiseInterval<T>& a, const BitwiseInterval<T>& b)
{
if (isEmpty(a)) {
return !isEmpty(b);
}
return (a.lo != b.lo) || (a.hi != b.hi);
}
//==============================================================================
// Printing
//==============================================================================
inline std::ostream& operator<<(std::ostream& os, const UInterval& x)
{
if (isEmpty(x)) {
return os << "U[]";
}
return os << "U[" << x.lo << ".." << x.hi << "]";
}
inline std::ostream& operator<<(std::ostream& os, const SInterval& x)
{
if (isEmpty(x)) {
return os << "S[]";
}
return os << "S[" << x.lo << ".." << x.hi << "]";
}
//==============================================================================
// Operations
//==============================================================================
// Union of intervals
template <typename T>
BitwiseInterval<T> operator+(const BitwiseInterval<T>& a, const BitwiseInterval<T>& b)
{
if (isEmpty(a)) {
return b;
}
if (isEmpty(b)) {
return a;
}
return {std::min(a.lo, b.lo), std::max(a.hi, b.hi)};
}
std::pair<UInterval, UInterval> signSplit(const SInterval& x);
SInterval signMerge(const UInterval& np, const UInterval& pp);
UInterval bitwiseUnsignedNot(const UInterval& a);
SInterval bitwiseSignedNot(const SInterval& a);
UInterval bitwiseUnsignedOr(const UInterval& a, const UInterval& b);
SInterval bitwiseSignedOr(const SInterval& a, const SInterval& b);
UInterval bitwiseUnsignedAnd(const UInterval& a, const UInterval& b);
SInterval bitwiseSignedAnd(const SInterval& a, const SInterval& b);
UInterval bitwiseUnsignedXOr(const UInterval& a, const UInterval& b);
SInterval bitwiseSignedXOr(const SInterval& a, const SInterval& b);
} // namespace itv
|
