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-2025, 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 8824 : pg_add_s16_overflow(int16 a, int16 b, int16 *result)
68 : {
69 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
70 8824 : 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 1228 : pg_sub_s16_overflow(int16 a, int16 b, int16 *result)
86 : {
87 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
88 1228 : 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 bool
121 : pg_neg_s16_overflow(int16 a, int16 *result)
122 : {
123 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
124 : return __builtin_sub_overflow(0, a, result);
125 : #else
126 : if (unlikely(a == PG_INT16_MIN))
127 : {
128 : *result = 0x5EED; /* to avoid spurious warnings */
129 : return true;
130 : }
131 : *result = -a;
132 : return false;
133 : #endif
134 : }
135 :
136 : static inline uint16
137 : pg_abs_s16(int16 a)
138 : {
139 : /*
140 : * This first widens the argument from int16 to int32 for use with abs().
141 : * The result is then narrowed from int32 to uint16. This prevents any
142 : * possibility of overflow.
143 : */
144 : return (uint16) abs((int32) a);
145 : }
146 :
147 : /*
148 : * INT32
149 : */
150 : static inline bool
151 22901362 : pg_add_s32_overflow(int32 a, int32 b, int32 *result)
152 : {
153 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
154 22901362 : return __builtin_add_overflow(a, b, result);
155 : #else
156 : int64 res = (int64) a + (int64) b;
157 :
158 : if (res > PG_INT32_MAX || res < PG_INT32_MIN)
159 : {
160 : *result = 0x5EED; /* to avoid spurious warnings */
161 : return true;
162 : }
163 : *result = (int32) res;
164 : return false;
165 : #endif
166 : }
167 :
168 : static inline bool
169 1498956 : pg_sub_s32_overflow(int32 a, int32 b, int32 *result)
170 : {
171 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
172 1498956 : return __builtin_sub_overflow(a, b, result);
173 : #else
174 : int64 res = (int64) a - (int64) b;
175 :
176 : if (res > PG_INT32_MAX || res < PG_INT32_MIN)
177 : {
178 : *result = 0x5EED; /* to avoid spurious warnings */
179 : return true;
180 : }
181 : *result = (int32) res;
182 : return false;
183 : #endif
184 : }
185 :
186 : static inline bool
187 3806080 : pg_mul_s32_overflow(int32 a, int32 b, int32 *result)
188 : {
189 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
190 3806080 : return __builtin_mul_overflow(a, b, result);
191 : #else
192 : int64 res = (int64) a * (int64) b;
193 :
194 : if (res > PG_INT32_MAX || res < PG_INT32_MIN)
195 : {
196 : *result = 0x5EED; /* to avoid spurious warnings */
197 : return true;
198 : }
199 : *result = (int32) res;
200 : return false;
201 : #endif
202 : }
203 :
204 : static inline bool
205 12 : pg_neg_s32_overflow(int32 a, int32 *result)
206 : {
207 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
208 12 : return __builtin_sub_overflow(0, a, result);
209 : #else
210 : if (unlikely(a == PG_INT32_MIN))
211 : {
212 : *result = 0x5EED; /* to avoid spurious warnings */
213 : return true;
214 : }
215 : *result = -a;
216 : return false;
217 : #endif
218 : }
219 :
220 : static inline uint32
221 1146 : pg_abs_s32(int32 a)
222 : {
223 : /*
224 : * This first widens the argument from int32 to int64 for use with
225 : * i64abs(). The result is then narrowed from int64 to uint32. This
226 : * prevents any possibility of overflow.
227 : */
228 1146 : return (uint32) i64abs((int64) a);
229 : }
230 :
231 : /*
232 : * INT64
233 : */
234 : static inline bool
235 23292062 : pg_add_s64_overflow(int64 a, int64 b, int64 *result)
236 : {
237 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
238 23292062 : return __builtin_add_overflow(a, b, result);
239 : #elif defined(HAVE_INT128)
240 : int128 res = (int128) a + (int128) b;
241 :
242 : if (res > PG_INT64_MAX || res < PG_INT64_MIN)
243 : {
244 : *result = 0x5EED; /* to avoid spurious warnings */
245 : return true;
246 : }
247 : *result = (int64) res;
248 : return false;
249 : #else
250 : if ((a > 0 && b > 0 && a > PG_INT64_MAX - b) ||
251 : (a < 0 && b < 0 && a < PG_INT64_MIN - b))
252 : {
253 : *result = 0x5EED; /* to avoid spurious warnings */
254 : return true;
255 : }
256 : *result = a + b;
257 : return false;
258 : #endif
259 : }
260 :
261 : static inline bool
262 455180 : pg_sub_s64_overflow(int64 a, int64 b, int64 *result)
263 : {
264 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
265 455180 : return __builtin_sub_overflow(a, b, result);
266 : #elif defined(HAVE_INT128)
267 : int128 res = (int128) a - (int128) b;
268 :
269 : if (res > PG_INT64_MAX || res < PG_INT64_MIN)
270 : {
271 : *result = 0x5EED; /* to avoid spurious warnings */
272 : return true;
273 : }
274 : *result = (int64) res;
275 : return false;
276 : #else
277 : /*
278 : * Note: overflow is also possible when a == 0 and b < 0 (specifically,
279 : * when b == PG_INT64_MIN).
280 : */
281 : if ((a < 0 && b > 0 && a < PG_INT64_MIN + b) ||
282 : (a >= 0 && b < 0 && a > PG_INT64_MAX + b))
283 : {
284 : *result = 0x5EED; /* to avoid spurious warnings */
285 : return true;
286 : }
287 : *result = a - b;
288 : return false;
289 : #endif
290 : }
291 :
292 : static inline bool
293 292318 : pg_mul_s64_overflow(int64 a, int64 b, int64 *result)
294 : {
295 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
296 292318 : return __builtin_mul_overflow(a, b, result);
297 : #elif defined(HAVE_INT128)
298 : int128 res = (int128) a * (int128) b;
299 :
300 : if (res > PG_INT64_MAX || res < PG_INT64_MIN)
301 : {
302 : *result = 0x5EED; /* to avoid spurious warnings */
303 : return true;
304 : }
305 : *result = (int64) res;
306 : return false;
307 : #else
308 : /*
309 : * Overflow can only happen if at least one value is outside the range
310 : * sqrt(min)..sqrt(max) so check that first as the division can be quite a
311 : * bit more expensive than the multiplication.
312 : *
313 : * Multiplying by 0 or 1 can't overflow of course and checking for 0
314 : * separately avoids any risk of dividing by 0. Be careful about dividing
315 : * INT_MIN by -1 also, note reversing the a and b to ensure we're always
316 : * dividing it by a positive value.
317 : *
318 : */
319 : if ((a > PG_INT32_MAX || a < PG_INT32_MIN ||
320 : b > PG_INT32_MAX || b < PG_INT32_MIN) &&
321 : a != 0 && a != 1 && b != 0 && b != 1 &&
322 : ((a > 0 && b > 0 && a > PG_INT64_MAX / b) ||
323 : (a > 0 && b < 0 && b < PG_INT64_MIN / a) ||
324 : (a < 0 && b > 0 && a < PG_INT64_MIN / b) ||
325 : (a < 0 && b < 0 && a < PG_INT64_MAX / b)))
326 : {
327 : *result = 0x5EED; /* to avoid spurious warnings */
328 : return true;
329 : }
330 : *result = a * b;
331 : return false;
332 : #endif
333 : }
334 :
335 : static inline bool
336 : pg_neg_s64_overflow(int64 a, int64 *result)
337 : {
338 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
339 : return __builtin_sub_overflow(0, a, result);
340 : #else
341 : if (unlikely(a == PG_INT64_MIN))
342 : {
343 : *result = 0x5EED; /* to avoid spurious warnings */
344 : return true;
345 : }
346 : *result = -a;
347 : return false;
348 : #endif
349 : }
350 :
351 : static inline uint64
352 2242 : pg_abs_s64(int64 a)
353 : {
354 2242 : if (unlikely(a == PG_INT64_MIN))
355 12 : return (uint64) PG_INT64_MAX + 1;
356 2230 : return (uint64) i64abs(a);
357 : }
358 :
359 : /*------------------------------------------------------------------------
360 : * Overflow routines for unsigned integers
361 : *------------------------------------------------------------------------
362 : */
363 :
364 : /*
365 : * UINT16
366 : */
367 : static inline bool
368 : pg_add_u16_overflow(uint16 a, uint16 b, uint16 *result)
369 : {
370 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
371 : return __builtin_add_overflow(a, b, result);
372 : #else
373 : uint16 res = a + b;
374 :
375 : if (res < a)
376 : {
377 : *result = 0x5EED; /* to avoid spurious warnings */
378 : return true;
379 : }
380 : *result = res;
381 : return false;
382 : #endif
383 : }
384 :
385 : static inline bool
386 : pg_sub_u16_overflow(uint16 a, uint16 b, uint16 *result)
387 : {
388 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
389 : return __builtin_sub_overflow(a, b, result);
390 : #else
391 : if (b > a)
392 : {
393 : *result = 0x5EED; /* to avoid spurious warnings */
394 : return true;
395 : }
396 : *result = a - b;
397 : return false;
398 : #endif
399 : }
400 :
401 : static inline bool
402 : pg_mul_u16_overflow(uint16 a, uint16 b, uint16 *result)
403 : {
404 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
405 : return __builtin_mul_overflow(a, b, result);
406 : #else
407 : uint32 res = (uint32) a * (uint32) b;
408 :
409 : if (res > PG_UINT16_MAX)
410 : {
411 : *result = 0x5EED; /* to avoid spurious warnings */
412 : return true;
413 : }
414 : *result = (uint16) res;
415 : return false;
416 : #endif
417 : }
418 :
419 : static inline bool
420 18572 : pg_neg_u16_overflow(uint16 a, int16 *result)
421 : {
422 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
423 18572 : return __builtin_sub_overflow(0, a, result);
424 : #else
425 : int32 res = -((int32) a);
426 :
427 : if (unlikely(res < PG_INT16_MIN))
428 : {
429 : *result = 0x5EED; /* to avoid spurious warnings */
430 : return true;
431 : }
432 : *result = res;
433 : return false;
434 : #endif
435 : }
436 :
437 : /*
438 : * INT32
439 : */
440 : static inline bool
441 : pg_add_u32_overflow(uint32 a, uint32 b, uint32 *result)
442 : {
443 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
444 : return __builtin_add_overflow(a, b, result);
445 : #else
446 : uint32 res = a + b;
447 :
448 : if (res < a)
449 : {
450 : *result = 0x5EED; /* to avoid spurious warnings */
451 : return true;
452 : }
453 : *result = res;
454 : return false;
455 : #endif
456 : }
457 :
458 : static inline bool
459 : pg_sub_u32_overflow(uint32 a, uint32 b, uint32 *result)
460 : {
461 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
462 : return __builtin_sub_overflow(a, b, result);
463 : #else
464 : if (b > a)
465 : {
466 : *result = 0x5EED; /* to avoid spurious warnings */
467 : return true;
468 : }
469 : *result = a - b;
470 : return false;
471 : #endif
472 : }
473 :
474 : static inline bool
475 : pg_mul_u32_overflow(uint32 a, uint32 b, uint32 *result)
476 : {
477 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
478 : return __builtin_mul_overflow(a, b, result);
479 : #else
480 : uint64 res = (uint64) a * (uint64) b;
481 :
482 : if (res > PG_UINT32_MAX)
483 : {
484 : *result = 0x5EED; /* to avoid spurious warnings */
485 : return true;
486 : }
487 : *result = (uint32) res;
488 : return false;
489 : #endif
490 : }
491 :
492 : static inline bool
493 53100 : pg_neg_u32_overflow(uint32 a, int32 *result)
494 : {
495 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
496 53100 : return __builtin_sub_overflow(0, a, result);
497 : #else
498 : int64 res = -((int64) a);
499 :
500 : if (unlikely(res < PG_INT32_MIN))
501 : {
502 : *result = 0x5EED; /* to avoid spurious warnings */
503 : return true;
504 : }
505 : *result = res;
506 : return false;
507 : #endif
508 : }
509 :
510 : /*
511 : * UINT64
512 : */
513 : static inline bool
514 178 : pg_add_u64_overflow(uint64 a, uint64 b, uint64 *result)
515 : {
516 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
517 178 : return __builtin_add_overflow(a, b, result);
518 : #else
519 : uint64 res = a + b;
520 :
521 : if (res < a)
522 : {
523 : *result = 0x5EED; /* to avoid spurious warnings */
524 : return true;
525 : }
526 : *result = res;
527 : return false;
528 : #endif
529 : }
530 :
531 : static inline bool
532 : pg_sub_u64_overflow(uint64 a, uint64 b, uint64 *result)
533 : {
534 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
535 : return __builtin_sub_overflow(a, b, result);
536 : #else
537 : if (b > a)
538 : {
539 : *result = 0x5EED; /* to avoid spurious warnings */
540 : return true;
541 : }
542 : *result = a - b;
543 : return false;
544 : #endif
545 : }
546 :
547 : static inline bool
548 178 : pg_mul_u64_overflow(uint64 a, uint64 b, uint64 *result)
549 : {
550 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
551 178 : return __builtin_mul_overflow(a, b, result);
552 : #elif defined(HAVE_INT128)
553 : uint128 res = (uint128) a * (uint128) b;
554 :
555 : if (res > PG_UINT64_MAX)
556 : {
557 : *result = 0x5EED; /* to avoid spurious warnings */
558 : return true;
559 : }
560 : *result = (uint64) res;
561 : return false;
562 : #else
563 : uint64 res = a * b;
564 :
565 : if (a != 0 && b != res / a)
566 : {
567 : *result = 0x5EED; /* to avoid spurious warnings */
568 : return true;
569 : }
570 : *result = res;
571 : return false;
572 : #endif
573 : }
574 :
575 : static inline bool
576 1118 : pg_neg_u64_overflow(uint64 a, int64 *result)
577 : {
578 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
579 1118 : return __builtin_sub_overflow(0, a, result);
580 : #elif defined(HAVE_INT128)
581 : int128 res = -((int128) a);
582 :
583 : if (unlikely(res < PG_INT64_MIN))
584 : {
585 : *result = 0x5EED; /* to avoid spurious warnings */
586 : return true;
587 : }
588 : *result = res;
589 : return false;
590 : #else
591 : if (unlikely(a > (uint64) PG_INT64_MAX + 1))
592 : {
593 : *result = 0x5EED; /* to avoid spurious warnings */
594 : return true;
595 : }
596 : if (unlikely(a == (uint64) PG_INT64_MAX + 1))
597 : *result = PG_INT64_MIN;
598 : else
599 : *result = -((int64) a);
600 : return false;
601 : #endif
602 : }
603 :
604 : /*------------------------------------------------------------------------
605 : *
606 : * Comparison routines for integer types.
607 : *
608 : * These routines are primarily intended for use in qsort() comparator
609 : * functions and therefore return a positive integer, 0, or a negative
610 : * integer depending on whether "a" is greater than, equal to, or less
611 : * than "b", respectively. These functions are written to be as efficient
612 : * as possible without introducing overflow risks, thereby helping ensure
613 : * the comparators that use them are transitive.
614 : *
615 : * Types with fewer than 32 bits are cast to signed integers and
616 : * subtracted. Other types are compared using > and <, and the results of
617 : * those comparisons (which are either (int) 0 or (int) 1 per the C
618 : * standard) are subtracted.
619 : *
620 : * NB: If the comparator function is inlined, some compilers may produce
621 : * worse code with these helper functions than with code with the
622 : * following form:
623 : *
624 : * if (a < b)
625 : * return -1;
626 : * if (a > b)
627 : * return 1;
628 : * return 0;
629 : *
630 : *------------------------------------------------------------------------
631 : */
632 :
633 : static inline int
634 77901138 : pg_cmp_s16(int16 a, int16 b)
635 : {
636 77901138 : return (int32) a - (int32) b;
637 : }
638 :
639 : static inline int
640 11838588 : pg_cmp_u16(uint16 a, uint16 b)
641 : {
642 11838588 : return (int32) a - (int32) b;
643 : }
644 :
645 : static inline int
646 79279954 : pg_cmp_s32(int32 a, int32 b)
647 : {
648 79279954 : return (a > b) - (a < b);
649 : }
650 :
651 : static inline int
652 79105036 : pg_cmp_u32(uint32 a, uint32 b)
653 : {
654 79105036 : return (a > b) - (a < b);
655 : }
656 :
657 : static inline int
658 : pg_cmp_s64(int64 a, int64 b)
659 : {
660 : return (a > b) - (a < b);
661 : }
662 :
663 : static inline int
664 16119682 : pg_cmp_u64(uint64 a, uint64 b)
665 : {
666 16119682 : return (a > b) - (a < b);
667 : }
668 :
669 : static inline int
670 0 : pg_cmp_size(size_t a, size_t b)
671 : {
672 0 : return (a > b) - (a < b);
673 : }
674 :
675 : #endif /* COMMON_INT_H */
|
