Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * int.h
4 : * Overflow-aware integer math and integer comparison routines.
5 : *
6 : * The routines in this file are intended to be well defined C, without
7 : * relying on compiler flags like -fwrapv.
8 : *
9 : * To reduce the overhead of these routines try to use compiler intrinsics
10 : * where available. That's not that important for the 16, 32 bit cases, but
11 : * the 64 bit cases can be considerably faster with intrinsics. In case no
12 : * intrinsics are available 128 bit math is used where available.
13 : *
14 : * Copyright (c) 2017-2024, PostgreSQL Global Development Group
15 : *
16 : * src/include/common/int.h
17 : *
18 : *-------------------------------------------------------------------------
19 : */
20 : #ifndef COMMON_INT_H
21 : #define COMMON_INT_H
22 :
23 :
24 : /*---------
25 : * The following guidelines apply to all the overflow routines:
26 : *
27 : * If the result overflows, return true, otherwise store the result into
28 : * *result. The content of *result is implementation defined in case of
29 : * overflow.
30 : *
31 : * bool pg_add_*_overflow(a, b, *result)
32 : *
33 : * Calculate a + b
34 : *
35 : * bool pg_sub_*_overflow(a, b, *result)
36 : *
37 : * Calculate a - b
38 : *
39 : * bool pg_mul_*_overflow(a, b, *result)
40 : *
41 : * Calculate a * b
42 : *
43 : * bool pg_neg_*_overflow(a, *result)
44 : *
45 : * Calculate -a
46 : *
47 : *
48 : * In addition, this file contains:
49 : *
50 : * <unsigned int type> pg_abs_*(<signed int type> a)
51 : *
52 : * Calculate absolute value of a. Unlike the standard library abs()
53 : * and labs() functions, the return type is unsigned, so the operation
54 : * cannot overflow.
55 : *---------
56 : */
57 :
58 : /*------------------------------------------------------------------------
59 : * Overflow routines for signed integers
60 : *------------------------------------------------------------------------
61 : */
62 :
63 : /*
64 : * INT16
65 : */
66 : static inline bool
67 6606 : pg_add_s16_overflow(int16 a, int16 b, int16 *result)
68 : {
69 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
70 6606 : return __builtin_add_overflow(a, b, result);
71 : #else
72 : int32 res = (int32) a + (int32) b;
73 :
74 : if (res > PG_INT16_MAX || res < PG_INT16_MIN)
75 : {
76 : *result = 0x5EED; /* to avoid spurious warnings */
77 : return true;
78 : }
79 : *result = (int16) res;
80 : return false;
81 : #endif
82 : }
83 :
84 : static inline bool
85 1218 : pg_sub_s16_overflow(int16 a, int16 b, int16 *result)
86 : {
87 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
88 1218 : return __builtin_sub_overflow(a, b, result);
89 : #else
90 : int32 res = (int32) a - (int32) b;
91 :
92 : if (res > PG_INT16_MAX || res < PG_INT16_MIN)
93 : {
94 : *result = 0x5EED; /* to avoid spurious warnings */
95 : return true;
96 : }
97 : *result = (int16) res;
98 : return false;
99 : #endif
100 : }
101 :
102 : static inline bool
103 54 : pg_mul_s16_overflow(int16 a, int16 b, int16 *result)
104 : {
105 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
106 54 : return __builtin_mul_overflow(a, b, result);
107 : #else
108 : int32 res = (int32) a * (int32) b;
109 :
110 : if (res > PG_INT16_MAX || res < PG_INT16_MIN)
111 : {
112 : *result = 0x5EED; /* to avoid spurious warnings */
113 : return true;
114 : }
115 : *result = (int16) res;
116 : return false;
117 : #endif
118 : }
119 :
120 : static inline uint16
121 : pg_abs_s16(int16 a)
122 : {
123 : /*
124 : * This first widens the argument from int16 to int32 for use with abs().
125 : * The result is then narrowed from int32 to uint16. This prevents any
126 : * possibility of overflow.
127 : */
128 : return (uint16) abs((int32) a);
129 : }
130 :
131 : /*
132 : * INT32
133 : */
134 : static inline bool
135 20954412 : pg_add_s32_overflow(int32 a, int32 b, int32 *result)
136 : {
137 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
138 20954412 : return __builtin_add_overflow(a, b, result);
139 : #else
140 : int64 res = (int64) a + (int64) b;
141 :
142 : if (res > PG_INT32_MAX || res < PG_INT32_MIN)
143 : {
144 : *result = 0x5EED; /* to avoid spurious warnings */
145 : return true;
146 : }
147 : *result = (int32) res;
148 : return false;
149 : #endif
150 : }
151 :
152 : static inline bool
153 1458210 : pg_sub_s32_overflow(int32 a, int32 b, int32 *result)
154 : {
155 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
156 1458210 : return __builtin_sub_overflow(a, b, result);
157 : #else
158 : int64 res = (int64) a - (int64) b;
159 :
160 : if (res > PG_INT32_MAX || res < PG_INT32_MIN)
161 : {
162 : *result = 0x5EED; /* to avoid spurious warnings */
163 : return true;
164 : }
165 : *result = (int32) res;
166 : return false;
167 : #endif
168 : }
169 :
170 : static inline bool
171 3748612 : pg_mul_s32_overflow(int32 a, int32 b, int32 *result)
172 : {
173 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
174 3748612 : return __builtin_mul_overflow(a, b, result);
175 : #else
176 : int64 res = (int64) a * (int64) b;
177 :
178 : if (res > PG_INT32_MAX || res < PG_INT32_MIN)
179 : {
180 : *result = 0x5EED; /* to avoid spurious warnings */
181 : return true;
182 : }
183 : *result = (int32) res;
184 : return false;
185 : #endif
186 : }
187 :
188 : static inline uint32
189 1146 : pg_abs_s32(int32 a)
190 : {
191 : /*
192 : * This first widens the argument from int32 to int64 for use with
193 : * i64abs(). The result is then narrowed from int64 to uint32. This
194 : * prevents any possibility of overflow.
195 : */
196 1146 : return (uint32) i64abs((int64) a);
197 : }
198 :
199 : /*
200 : * INT64
201 : */
202 : static inline bool
203 22054628 : pg_add_s64_overflow(int64 a, int64 b, int64 *result)
204 : {
205 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
206 22054628 : return __builtin_add_overflow(a, b, result);
207 : #elif defined(HAVE_INT128)
208 : int128 res = (int128) a + (int128) b;
209 :
210 : if (res > PG_INT64_MAX || res < PG_INT64_MIN)
211 : {
212 : *result = 0x5EED; /* to avoid spurious warnings */
213 : return true;
214 : }
215 : *result = (int64) res;
216 : return false;
217 : #else
218 : if ((a > 0 && b > 0 && a > PG_INT64_MAX - b) ||
219 : (a < 0 && b < 0 && a < PG_INT64_MIN - b))
220 : {
221 : *result = 0x5EED; /* to avoid spurious warnings */
222 : return true;
223 : }
224 : *result = a + b;
225 : return false;
226 : #endif
227 : }
228 :
229 : static inline bool
230 250706 : pg_sub_s64_overflow(int64 a, int64 b, int64 *result)
231 : {
232 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
233 250706 : return __builtin_sub_overflow(a, b, result);
234 : #elif defined(HAVE_INT128)
235 : int128 res = (int128) a - (int128) b;
236 :
237 : if (res > PG_INT64_MAX || res < PG_INT64_MIN)
238 : {
239 : *result = 0x5EED; /* to avoid spurious warnings */
240 : return true;
241 : }
242 : *result = (int64) res;
243 : return false;
244 : #else
245 : /*
246 : * Note: overflow is also possible when a == 0 and b < 0 (specifically,
247 : * when b == PG_INT64_MIN).
248 : */
249 : if ((a < 0 && b > 0 && a < PG_INT64_MIN + b) ||
250 : (a >= 0 && b < 0 && a > PG_INT64_MAX + b))
251 : {
252 : *result = 0x5EED; /* to avoid spurious warnings */
253 : return true;
254 : }
255 : *result = a - b;
256 : return false;
257 : #endif
258 : }
259 :
260 : static inline bool
261 234660 : pg_mul_s64_overflow(int64 a, int64 b, int64 *result)
262 : {
263 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
264 234660 : return __builtin_mul_overflow(a, b, result);
265 : #elif defined(HAVE_INT128)
266 : int128 res = (int128) a * (int128) b;
267 :
268 : if (res > PG_INT64_MAX || res < PG_INT64_MIN)
269 : {
270 : *result = 0x5EED; /* to avoid spurious warnings */
271 : return true;
272 : }
273 : *result = (int64) res;
274 : return false;
275 : #else
276 : /*
277 : * Overflow can only happen if at least one value is outside the range
278 : * sqrt(min)..sqrt(max) so check that first as the division can be quite a
279 : * bit more expensive than the multiplication.
280 : *
281 : * Multiplying by 0 or 1 can't overflow of course and checking for 0
282 : * separately avoids any risk of dividing by 0. Be careful about dividing
283 : * INT_MIN by -1 also, note reversing the a and b to ensure we're always
284 : * dividing it by a positive value.
285 : *
286 : */
287 : if ((a > PG_INT32_MAX || a < PG_INT32_MIN ||
288 : b > PG_INT32_MAX || b < PG_INT32_MIN) &&
289 : a != 0 && a != 1 && b != 0 && b != 1 &&
290 : ((a > 0 && b > 0 && a > PG_INT64_MAX / b) ||
291 : (a > 0 && b < 0 && b < PG_INT64_MIN / a) ||
292 : (a < 0 && b > 0 && a < PG_INT64_MIN / b) ||
293 : (a < 0 && b < 0 && a < PG_INT64_MAX / b)))
294 : {
295 : *result = 0x5EED; /* to avoid spurious warnings */
296 : return true;
297 : }
298 : *result = a * b;
299 : return false;
300 : #endif
301 : }
302 :
303 : static inline uint64
304 2230 : pg_abs_s64(int64 a)
305 : {
306 2230 : if (unlikely(a == PG_INT64_MIN))
307 12 : return (uint64) PG_INT64_MAX + 1;
308 2218 : return (uint64) i64abs(a);
309 : }
310 :
311 : /*------------------------------------------------------------------------
312 : * Overflow routines for unsigned integers
313 : *------------------------------------------------------------------------
314 : */
315 :
316 : /*
317 : * UINT16
318 : */
319 : static inline bool
320 : pg_add_u16_overflow(uint16 a, uint16 b, uint16 *result)
321 : {
322 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
323 : return __builtin_add_overflow(a, b, result);
324 : #else
325 : uint16 res = a + b;
326 :
327 : if (res < a)
328 : {
329 : *result = 0x5EED; /* to avoid spurious warnings */
330 : return true;
331 : }
332 : *result = res;
333 : return false;
334 : #endif
335 : }
336 :
337 : static inline bool
338 : pg_sub_u16_overflow(uint16 a, uint16 b, uint16 *result)
339 : {
340 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
341 : return __builtin_sub_overflow(a, b, result);
342 : #else
343 : if (b > a)
344 : {
345 : *result = 0x5EED; /* to avoid spurious warnings */
346 : return true;
347 : }
348 : *result = a - b;
349 : return false;
350 : #endif
351 : }
352 :
353 : static inline bool
354 : pg_mul_u16_overflow(uint16 a, uint16 b, uint16 *result)
355 : {
356 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
357 : return __builtin_mul_overflow(a, b, result);
358 : #else
359 : uint32 res = (uint32) a * (uint32) b;
360 :
361 : if (res > PG_UINT16_MAX)
362 : {
363 : *result = 0x5EED; /* to avoid spurious warnings */
364 : return true;
365 : }
366 : *result = (uint16) res;
367 : return false;
368 : #endif
369 : }
370 :
371 : static inline bool
372 17000 : pg_neg_u16_overflow(uint16 a, int16 *result)
373 : {
374 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
375 17000 : return __builtin_sub_overflow(0, a, result);
376 : #else
377 : int32 res = -((int32) a);
378 :
379 : if (unlikely(res < PG_INT16_MIN))
380 : {
381 : *result = 0x5EED; /* to avoid spurious warnings */
382 : return true;
383 : }
384 : *result = res;
385 : return false;
386 : #endif
387 : }
388 :
389 : /*
390 : * INT32
391 : */
392 : static inline bool
393 : pg_add_u32_overflow(uint32 a, uint32 b, uint32 *result)
394 : {
395 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
396 : return __builtin_add_overflow(a, b, result);
397 : #else
398 : uint32 res = a + b;
399 :
400 : if (res < a)
401 : {
402 : *result = 0x5EED; /* to avoid spurious warnings */
403 : return true;
404 : }
405 : *result = res;
406 : return false;
407 : #endif
408 : }
409 :
410 : static inline bool
411 : pg_sub_u32_overflow(uint32 a, uint32 b, uint32 *result)
412 : {
413 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
414 : return __builtin_sub_overflow(a, b, result);
415 : #else
416 : if (b > a)
417 : {
418 : *result = 0x5EED; /* to avoid spurious warnings */
419 : return true;
420 : }
421 : *result = a - b;
422 : return false;
423 : #endif
424 : }
425 :
426 : static inline bool
427 : pg_mul_u32_overflow(uint32 a, uint32 b, uint32 *result)
428 : {
429 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
430 : return __builtin_mul_overflow(a, b, result);
431 : #else
432 : uint64 res = (uint64) a * (uint64) b;
433 :
434 : if (res > PG_UINT32_MAX)
435 : {
436 : *result = 0x5EED; /* to avoid spurious warnings */
437 : return true;
438 : }
439 : *result = (uint32) res;
440 : return false;
441 : #endif
442 : }
443 :
444 : static inline bool
445 62638 : pg_neg_u32_overflow(uint32 a, int32 *result)
446 : {
447 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
448 62638 : return __builtin_sub_overflow(0, a, result);
449 : #else
450 : int64 res = -((int64) a);
451 :
452 : if (unlikely(res < PG_INT32_MIN))
453 : {
454 : *result = 0x5EED; /* to avoid spurious warnings */
455 : return true;
456 : }
457 : *result = res;
458 : return false;
459 : #endif
460 : }
461 :
462 : /*
463 : * UINT64
464 : */
465 : static inline bool
466 178 : pg_add_u64_overflow(uint64 a, uint64 b, uint64 *result)
467 : {
468 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
469 178 : return __builtin_add_overflow(a, b, result);
470 : #else
471 : uint64 res = a + b;
472 :
473 : if (res < a)
474 : {
475 : *result = 0x5EED; /* to avoid spurious warnings */
476 : return true;
477 : }
478 : *result = res;
479 : return false;
480 : #endif
481 : }
482 :
483 : static inline bool
484 : pg_sub_u64_overflow(uint64 a, uint64 b, uint64 *result)
485 : {
486 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
487 : return __builtin_sub_overflow(a, b, result);
488 : #else
489 : if (b > a)
490 : {
491 : *result = 0x5EED; /* to avoid spurious warnings */
492 : return true;
493 : }
494 : *result = a - b;
495 : return false;
496 : #endif
497 : }
498 :
499 : static inline bool
500 178 : pg_mul_u64_overflow(uint64 a, uint64 b, uint64 *result)
501 : {
502 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
503 178 : return __builtin_mul_overflow(a, b, result);
504 : #elif defined(HAVE_INT128)
505 : uint128 res = (uint128) a * (uint128) b;
506 :
507 : if (res > PG_UINT64_MAX)
508 : {
509 : *result = 0x5EED; /* to avoid spurious warnings */
510 : return true;
511 : }
512 : *result = (uint64) res;
513 : return false;
514 : #else
515 : uint64 res = a * b;
516 :
517 : if (a != 0 && b != res / a)
518 : {
519 : *result = 0x5EED; /* to avoid spurious warnings */
520 : return true;
521 : }
522 : *result = res;
523 : return false;
524 : #endif
525 : }
526 :
527 : static inline bool
528 1102 : pg_neg_u64_overflow(uint64 a, int64 *result)
529 : {
530 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
531 1102 : return __builtin_sub_overflow(0, a, result);
532 : #elif defined(HAVE_INT128)
533 : int128 res = -((int128) a);
534 :
535 : if (unlikely(res < PG_INT64_MIN))
536 : {
537 : *result = 0x5EED; /* to avoid spurious warnings */
538 : return true;
539 : }
540 : *result = res;
541 : return false;
542 : #else
543 : if (unlikely(a > (uint64) PG_INT64_MAX + 1))
544 : {
545 : *result = 0x5EED; /* to avoid spurious warnings */
546 : return true;
547 : }
548 : if (unlikely(a == (uint64) PG_INT64_MAX + 1))
549 : *result = PG_INT64_MIN;
550 : else
551 : *result = -((int64) a);
552 : return false;
553 : #endif
554 : }
555 :
556 : /*------------------------------------------------------------------------
557 : *
558 : * Comparison routines for integer types.
559 : *
560 : * These routines are primarily intended for use in qsort() comparator
561 : * functions and therefore return a positive integer, 0, or a negative
562 : * integer depending on whether "a" is greater than, equal to, or less
563 : * than "b", respectively. These functions are written to be as efficient
564 : * as possible without introducing overflow risks, thereby helping ensure
565 : * the comparators that use them are transitive.
566 : *
567 : * Types with fewer than 32 bits are cast to signed integers and
568 : * subtracted. Other types are compared using > and <, and the results of
569 : * those comparisons (which are either (int) 0 or (int) 1 per the C
570 : * standard) are subtracted.
571 : *
572 : * NB: If the comparator function is inlined, some compilers may produce
573 : * worse code with these helper functions than with code with the
574 : * following form:
575 : *
576 : * if (a < b)
577 : * return -1;
578 : * if (a > b)
579 : * return 1;
580 : * return 0;
581 : *
582 : *------------------------------------------------------------------------
583 : */
584 :
585 : static inline int
586 74346742 : pg_cmp_s16(int16 a, int16 b)
587 : {
588 74346742 : return (int32) a - (int32) b;
589 : }
590 :
591 : static inline int
592 11160762 : pg_cmp_u16(uint16 a, uint16 b)
593 : {
594 11160762 : return (int32) a - (int32) b;
595 : }
596 :
597 : static inline int
598 480583066 : pg_cmp_s32(int32 a, int32 b)
599 : {
600 480583066 : return (a > b) - (a < b);
601 : }
602 :
603 : static inline int
604 70438138 : pg_cmp_u32(uint32 a, uint32 b)
605 : {
606 70438138 : return (a > b) - (a < b);
607 : }
608 :
609 : static inline int
610 : pg_cmp_s64(int64 a, int64 b)
611 : {
612 : return (a > b) - (a < b);
613 : }
614 :
615 : static inline int
616 15156164 : pg_cmp_u64(uint64 a, uint64 b)
617 : {
618 15156164 : return (a > b) - (a < b);
619 : }
620 :
621 : static inline int
622 4 : pg_cmp_size(size_t a, size_t b)
623 : {
624 4 : return (a > b) - (a < b);
625 : }
626 :
627 : #endif /* COMMON_INT_H */
|
