Age Owner Branch data TLA 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
2869 andres@anarazel.de 67 :CBC 3837 : pg_add_s16_overflow(int16 a, int16 b, int16 *result)
68 : : {
69 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
70 : 3837 : 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 : 614 : pg_sub_s16_overflow(int16 a, int16 b, int16 *result)
86 : : {
87 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
88 : 614 : 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 : 27 : pg_mul_s16_overflow(int16 a, int16 b, int16 *result)
104 : : {
105 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
106 : 27 : 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 : 12162111 : pg_add_s32_overflow(int32 a, int32 b, int32 *result)
152 : : {
153 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
154 : 12162111 : 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 : 1464954 : pg_sub_s32_overflow(int32 a, int32 b, int32 *result)
170 : : {
171 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
172 : 1464954 : 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 : 1849470 : pg_mul_s32_overflow(int32 a, int32 b, int32 *result)
188 : : {
189 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
190 : 1849470 : 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
271 nathan@postgresql.or 205 : 6 : pg_neg_s32_overflow(int32 a, int32 *result)
206 : : {
207 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
208 : 6 : 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
387 221 : 573 : 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 : 573 : return (uint32) i64abs((int64) a);
229 : : }
230 : :
231 : : /*
232 : : * INT64
233 : : */
234 : : static inline bool
2869 andres@anarazel.de 235 : 11938046 : pg_add_s64_overflow(int64 a, int64 b, int64 *result)
236 : : {
237 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
238 : 11938046 : 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 : 269912 : pg_sub_s64_overflow(int64 a, int64 b, int64 *result)
263 : : {
264 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
265 : 269912 : 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 : 144913 : pg_mul_s64_overflow(int64 a, int64 b, int64 *result)
294 : : {
295 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
296 : 144913 : 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
387 nathan@postgresql.or 352 : 1112 : pg_abs_s64(int64 a)
353 : : {
354 [ + + ]: 1112 : if (unlikely(a == PG_INT64_MIN))
355 : 6 : return (uint64) PG_INT64_MAX + 1;
356 : 1106 : 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 : 9479 : pg_neg_u16_overflow(uint16 a, int16 *result)
421 : : {
422 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
423 : 9479 : 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 : 26767 : pg_neg_u32_overflow(uint32 a, int32 *result)
494 : : {
495 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
496 : 26767 : 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
2196 michael@paquier.xyz 514 : 89 : pg_add_u64_overflow(uint64 a, uint64 b, uint64 *result)
515 : : {
516 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
517 : 89 : 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 : 89 : pg_mul_u64_overflow(uint64 a, uint64 b, uint64 *result)
549 : : {
550 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
551 : 89 : 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
387 nathan@postgresql.or 576 : 557 : pg_neg_u64_overflow(uint64 a, int64 *result)
577 : : {
578 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
579 : 557 : 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
568 634 : 39431029 : pg_cmp_s16(int16 a, int16 b)
635 : : {
636 : 39431029 : return (int32) a - (int32) b;
637 : : }
638 : :
639 : : static inline int
640 : 6606990 : pg_cmp_u16(uint16 a, uint16 b)
641 : : {
642 : 6606990 : return (int32) a - (int32) b;
643 : : }
644 : :
645 : : static inline int
646 : 36213773 : pg_cmp_s32(int32 a, int32 b)
647 : : {
648 : 36213773 : return (a > b) - (a < b);
649 : : }
650 : :
651 : : static inline int
652 : 33872665 : pg_cmp_u32(uint32 a, uint32 b)
653 : : {
654 : 33872665 : 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 : 8625222 : pg_cmp_u64(uint64 a, uint64 b)
665 : : {
666 : 8625222 : return (a > b) - (a < b);
667 : : }
668 : :
669 : : static inline int
568 nathan@postgresql.or 670 :UBC 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 */
|
