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
111
112
113
|
#include <stdio.h>
#include <limits.h>
#include <assert.h>
#include <stdint.h>
/*
Addition that saturates to TMIN or TMAX
2^(w-2) + 2^(w-2)
w=4
0100
0100
+
1000 (-8)
Normally overflow wraps around to the other extreme.
z mod 2w
and do unsigned addition
positive overflow -> TMAX
negative overflow -> TMIN
for w=4
1000
1000
+
1000
0100
0100
+
0111
z +
note: you can apparently also do something like
thing_is_true && (x = my_value)
in c :/.
Now I did it with a weird method using masks based on booleans.
*/
int saturating_add(int x, int y) {
int sum = x + y;
printf("sum: %x\n", sum);
int min = INT_MIN;
int did_negative_overflow = ((min & x) && (min & y) && !(min & sum)) - 1;
int did_positive_overflow = (!(min & x) && !(min & y) && (min & sum)) - 1;
sum |= INT_MIN & ~did_negative_overflow;
sum &= INT_MIN | did_negative_overflow;
sum |= INT_MAX & ~did_positive_overflow;
sum &= INT_MAX | did_positive_overflow;
return sum;
}
/*
Determine whether arguments can be subtracted without overflow.
important to note is that the positive range of integers is shorter than the negative.
positive [0, 2^{w-1} - 1]
negative [-2^{w-1}, 0]
*/
int tsub_ok(int x, int y) {
if (y == INT_MIN) {
return 0;
}
int positive_overflow = x > 0 && y < 0 && x - y < 0;
int negative_overflow = x < 0 && y > 0 && x - y >= 0;
return !positive_overflow && !negative_overflow;
}
/*
The result of 2.18 shows us
T2B(x*y) <=> U2B(x'*y')
but this is only for w bits.
In this case we are looking at the 2w bits.
*/
int signed_high_prod(int x, int y) {
int64_t result = (int64_t) x * y;
return result >> 32;
}
unsigned correct_unsigned_high_prod(unsigned x, unsigned y) {
uint64_t result = (uint64_t) x * y;
return result >> 32;
}
unsigned unsigned_high_prod(unsigned x, unsigned y) {
unsigned xl = x>>31;
unsigned yl = y>>31;
return signed_high_prod(x, y) + xl*y + yl*x;
}
int main() {
/* assert(unsigned_high_prod(0xFFFFFFFF, 3) == correct_unsigned_high_prod(0xFFFFFFFF, 3)); */
unsigned x = 0x12345678;
unsigned y = 0xFFFFFFFF;
assert(correct_unsigned_high_prod(x, y) == unsigned_high_prod(x, y));
return 0;
printf("%d\n", tsub_ok(1, INT_MIN>>1));
printf("%d\n", tsub_ok(1, (INT_MIN>>1) - 1));
printf("%d\n", tsub_ok(1, INT_MIN));
printf("%d\n", tsub_ok(INT_MIN, INT_MAX));
printf("%d\n", -((INT_MIN>>1) - 1));
printf("%d\n", INT_MAX);
return 0;
printf("%x\n", INT_MIN);
printf("%x\n", saturating_add(INT_MIN, INT_MIN));
printf("%x\n", saturating_add(4, 4));
printf("%x\n", saturating_add(-3, 4));
return 0;
}
|
