forked from google/cel-go
/
overflow.go
389 lines (345 loc) · 12.3 KB
/
overflow.go
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
// Copyright 2021 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package types
import (
"math"
"time"
)
var (
doubleTwoTo64 = math.Ldexp(1.0, 64)
)
// addInt64Checked performs addition with overflow detection of two int64 values.
//
// If the operation fails the error return value will be non-nil.
func addInt64Checked(x, y int64) (int64, error) {
if (y > 0 && x > math.MaxInt64-y) || (y < 0 && x < math.MinInt64-y) {
return 0, errIntOverflow
}
return x + y, nil
}
// subtractInt64Checked performs subtraction with overflow detection of two int64 values.
//
// If the operation fails the error return value will be non-nil.
func subtractInt64Checked(x, y int64) (int64, error) {
if (y < 0 && x > math.MaxInt64+y) || (y > 0 && x < math.MinInt64+y) {
return 0, errIntOverflow
}
return x - y, nil
}
// negateInt64Checked performs negation with overflow detection of an int64.
//
// If the operation fails the error return value will be non-nil.
func negateInt64Checked(x int64) (int64, error) {
// In twos complement, negating MinInt64 would result in a valid of MaxInt64+1.
if x == math.MinInt64 {
return 0, errIntOverflow
}
return -x, nil
}
// multiplyInt64Checked performs multiplication with overflow detection of two int64 value.
//
// If the operation fails the error return value will be non-nil.
func multiplyInt64Checked(x, y int64) (int64, error) {
// Detecting multiplication overflow is more complicated than the others. The first two detect
// attempting to negate MinInt64, which would result in MaxInt64+1. The other four detect normal
// overflow conditions.
if (x == -1 && y == math.MinInt64) || (y == -1 && x == math.MinInt64) ||
// x is positive, y is positive
(x > 0 && y > 0 && x > math.MaxInt64/y) ||
// x is positive, y is negative
(x > 0 && y < 0 && y < math.MinInt64/x) ||
// x is negative, y is positive
(x < 0 && y > 0 && x < math.MinInt64/y) ||
// x is negative, y is negative
(x < 0 && y < 0 && y < math.MaxInt64/x) {
return 0, errIntOverflow
}
return x * y, nil
}
// divideInt64Checked performs division with overflow detection of two int64 values,
// as well as a division by zero check.
//
// If the operation fails the error return value will be non-nil.
func divideInt64Checked(x, y int64) (int64, error) {
// Division by zero.
if y == 0 {
return 0, errDivideByZero
}
// In twos complement, negating MinInt64 would result in a valid of MaxInt64+1.
if x == math.MinInt64 && y == -1 {
return 0, errIntOverflow
}
return x / y, nil
}
// moduloInt64Checked performs modulo with overflow detection of two int64 values
// as well as a modulus by zero check.
//
// If the operation fails the error return value will be non-nil.
func moduloInt64Checked(x, y int64) (int64, error) {
// Modulus by zero.
if y == 0 {
return 0, errModulusByZero
}
// In twos complement, negating MinInt64 would result in a valid of MaxInt64+1.
if x == math.MinInt64 && y == -1 {
return 0, errIntOverflow
}
return x % y, nil
}
// addUint64Checked performs addition with overflow detection of two uint64 values.
//
// If the operation fails due to overflow the error return value will be non-nil.
func addUint64Checked(x, y uint64) (uint64, error) {
if y > 0 && x > math.MaxUint64-y {
return 0, errUintOverflow
}
return x + y, nil
}
// subtractUint64Checked performs subtraction with overflow detection of two uint64 values.
//
// If the operation fails due to overflow the error return value will be non-nil.
func subtractUint64Checked(x, y uint64) (uint64, error) {
if y > x {
return 0, errUintOverflow
}
return x - y, nil
}
// multiplyUint64Checked performs multiplication with overflow detection of two uint64 values.
//
// If the operation fails due to overflow the error return value will be non-nil.
func multiplyUint64Checked(x, y uint64) (uint64, error) {
if y != 0 && x > math.MaxUint64/y {
return 0, errUintOverflow
}
return x * y, nil
}
// divideUint64Checked performs division with a test for division by zero.
//
// If the operation fails the error return value will be non-nil.
func divideUint64Checked(x, y uint64) (uint64, error) {
if y == 0 {
return 0, errDivideByZero
}
return x / y, nil
}
// moduloUint64Checked performs modulo with a test for modulus by zero.
//
// If the operation fails the error return value will be non-nil.
func moduloUint64Checked(x, y uint64) (uint64, error) {
if y == 0 {
return 0, errModulusByZero
}
return x % y, nil
}
// addDurationChecked performs addition with overflow detection of two time.Durations.
//
// If the operation fails due to overflow the error return value will be non-nil.
func addDurationChecked(x, y time.Duration) (time.Duration, error) {
val, err := addInt64Checked(int64(x), int64(y))
if err != nil {
return time.Duration(0), err
}
return time.Duration(val), nil
}
// subtractDurationChecked performs subtraction with overflow detection of two time.Durations.
//
// If the operation fails due to overflow the error return value will be non-nil.
func subtractDurationChecked(x, y time.Duration) (time.Duration, error) {
val, err := subtractInt64Checked(int64(x), int64(y))
if err != nil {
return time.Duration(0), err
}
return time.Duration(val), nil
}
// negateDurationChecked performs negation with overflow detection of a time.Duration.
//
// If the operation fails due to overflow the error return value will be non-nil.
func negateDurationChecked(x time.Duration) (time.Duration, error) {
val, err := negateInt64Checked(int64(x))
if err != nil {
return time.Duration(0), err
}
return time.Duration(val), nil
}
// addDurationChecked performs addition with overflow detection of a time.Time and time.Duration.
//
// If the operation fails due to overflow the error return value will be non-nil.
func addTimeDurationChecked(x time.Time, y time.Duration) (time.Time, error) {
// This is tricky. A time is represented as (int64, int32) where the first is seconds and second
// is nanoseconds. A duration is int64 representing nanoseconds. We cannot normalize time to int64
// as it could potentially overflow. The only way to proceed is to break time and duration into
// second and nanosecond components.
// First we break time into its components by truncating and subtracting.
sec1 := x.Truncate(time.Second).Unix() // Truncate to seconds.
nsec1 := x.Sub(x.Truncate(time.Second)).Nanoseconds() // Get nanoseconds by truncating and subtracting.
// Second we break duration into its components by dividing and modulo.
sec2 := int64(y) / int64(time.Second) // Truncate to seconds.
nsec2 := int64(y) % int64(time.Second) // Get remainder.
// Add seconds first, detecting any overflow.
sec, err := addInt64Checked(sec1, sec2)
if err != nil {
return time.Time{}, err
}
// Nanoseconds cannot overflow as time.Time normalizes them to [0, 999999999].
nsec := nsec1 + nsec2
// We need to normalize nanoseconds to be positive and carry extra nanoseconds to seconds.
// Adapted from time.Unix(int64, int64).
if nsec < 0 || nsec >= int64(time.Second) {
// Add seconds.
sec, err = addInt64Checked(sec, nsec/int64(time.Second))
if err != nil {
return time.Time{}, err
}
nsec -= (nsec / int64(time.Second)) * int64(time.Second)
if nsec < 0 {
// Subtract an extra second
sec, err = addInt64Checked(sec, -1)
if err != nil {
return time.Time{}, err
}
nsec += int64(time.Second)
}
}
// Check if the the number of seconds from Unix epoch is within our acceptable range.
if sec < minUnixTime || sec > maxUnixTime {
return time.Time{}, errTimestampOverflow
}
// Return resulting time and propagate time zone.
return time.Unix(sec, nsec).In(x.Location()), nil
}
// subtractTimeChecked performs subtraction with overflow detection of two time.Time.
//
// If the operation fails due to overflow the error return value will be non-nil.
func subtractTimeChecked(x, y time.Time) (time.Duration, error) {
// Similar to addTimeDurationOverflow() above.
// First we break time into its components by truncating and subtracting.
sec1 := x.Truncate(time.Second).Unix() // Truncate to seconds.
nsec1 := x.Sub(x.Truncate(time.Second)).Nanoseconds() // Get nanoseconds by truncating and subtracting.
// Second we break duration into its components by truncating and subtracting.
sec2 := y.Truncate(time.Second).Unix() // Truncate to seconds.
nsec2 := y.Sub(y.Truncate(time.Second)).Nanoseconds() // Get nanoseconds by truncating and subtracting.
// Subtract seconds first, detecting any overflow.
sec, err := subtractInt64Checked(sec1, sec2)
if err != nil {
return time.Duration(0), err
}
// Nanoseconds cannot overflow as time.Time normalizes them to [0, 999999999].
nsec := nsec1 - nsec2
// Scale seconds to nanoseconds detecting overflow.
tsec, err := multiplyInt64Checked(sec, int64(time.Second))
if err != nil {
return time.Duration(0), err
}
// Lastly we need to add the two nanoseconds together.
val, err := addInt64Checked(tsec, nsec)
if err != nil {
return time.Duration(0), err
}
return time.Duration(val), nil
}
// subtractTimeDurationChecked performs subtraction with overflow detection of a time.Time and
// time.Duration.
//
// If the operation fails due to overflow the error return value will be non-nil.
func subtractTimeDurationChecked(x time.Time, y time.Duration) (time.Time, error) {
// The easiest way to implement this is to negate y and add them.
// x - y = x + -y
val, err := negateDurationChecked(y)
if err != nil {
return time.Time{}, err
}
return addTimeDurationChecked(x, val)
}
// doubleToInt64Checked converts a double to an int64 value.
//
// If the conversion fails due to overflow the error return value will be non-nil.
func doubleToInt64Checked(v float64) (int64, error) {
if math.IsInf(v, 0) || math.IsNaN(v) || v <= float64(math.MinInt64) || v >= float64(math.MaxInt64) {
return 0, errIntOverflow
}
return int64(v), nil
}
// doubleToInt64Checked converts a double to a uint64 value.
//
// If the conversion fails due to overflow the error return value will be non-nil.
func doubleToUint64Checked(v float64) (uint64, error) {
if math.IsInf(v, 0) || math.IsNaN(v) || v < 0 || v >= doubleTwoTo64 {
return 0, errUintOverflow
}
return uint64(v), nil
}
// int64ToUint64Checked converts an int64 to a uint64 value.
//
// If the conversion fails due to overflow the error return value will be non-nil.
func int64ToUint64Checked(v int64) (uint64, error) {
if v < 0 {
return 0, errUintOverflow
}
return uint64(v), nil
}
// int64ToInt32Checked converts an int64 to an int32 value.
//
// If the conversion fails due to overflow the error return value will be non-nil.
func int64ToInt32Checked(v int64) (int32, error) {
if v < math.MinInt32 || v > math.MaxInt32 {
return 0, errIntOverflow
}
return int32(v), nil
}
// uint64ToUint32Checked converts a uint64 to a uint32 value.
//
// If the conversion fails due to overflow the error return value will be non-nil.
func uint64ToUint32Checked(v uint64) (uint32, error) {
if v > math.MaxUint32 {
return 0, errUintOverflow
}
return uint32(v), nil
}
// uint64ToInt64Checked converts a uint64 to an int64 value.
//
// If the conversion fails due to overflow the error return value will be non-nil.
func uint64ToInt64Checked(v uint64) (int64, error) {
if v > math.MaxInt64 {
return 0, errIntOverflow
}
return int64(v), nil
}
func doubleToUint64Lossless(v float64) (uint64, bool) {
u, err := doubleToUint64Checked(v)
if err != nil {
return 0, false
}
if float64(u) != v {
return 0, false
}
return u, true
}
func doubleToInt64Lossless(v float64) (int64, bool) {
i, err := doubleToInt64Checked(v)
if err != nil {
return 0, false
}
if float64(i) != v {
return 0, false
}
return i, true
}
func int64ToUint64Lossless(v int64) (uint64, bool) {
u, err := int64ToUint64Checked(v)
return u, err == nil
}
func uint64ToInt64Lossless(v uint64) (int64, bool) {
i, err := uint64ToInt64Checked(v)
return i, err == nil
}