PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
int.h
Go to the documentation of this file.
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 */
66static inline bool
68{
69#if defined(HAVE__BUILTIN_OP_OVERFLOW)
70 return __builtin_add_overflow(a, b, result);
71#else
72 int32 res = (int32) a + (int32) b;
73
75 {
76 *result = 0x5EED; /* to avoid spurious warnings */
77 return true;
78 }
79 *result = (int16) res;
80 return false;
81#endif
82}
83
84static inline bool
86{
87#if defined(HAVE__BUILTIN_OP_OVERFLOW)
88 return __builtin_sub_overflow(a, b, result);
89#else
90 int32 res = (int32) a - (int32) b;
91
93 {
94 *result = 0x5EED; /* to avoid spurious warnings */
95 return true;
96 }
97 *result = (int16) res;
98 return false;
99#endif
100}
101
102static inline bool
104{
105#if defined(HAVE__BUILTIN_OP_OVERFLOW)
106 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
120static inline bool
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
136static inline uint16
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 */
150static inline bool
152{
153#if defined(HAVE__BUILTIN_OP_OVERFLOW)
154 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
168static inline bool
170{
171#if defined(HAVE__BUILTIN_OP_OVERFLOW)
172 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
186static inline bool
188{
189#if defined(HAVE__BUILTIN_OP_OVERFLOW)
190 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
204static inline bool
206{
207#if defined(HAVE__BUILTIN_OP_OVERFLOW)
208 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
220static inline uint32
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 return (uint32) i64abs((int64) a);
229}
230
231/*
232 * INT64
233 */
234static inline bool
236{
237#if defined(HAVE__BUILTIN_OP_OVERFLOW)
238 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
261static inline bool
263{
264#if defined(HAVE__BUILTIN_OP_OVERFLOW)
265 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
292static inline bool
294{
295#if defined(HAVE__BUILTIN_OP_OVERFLOW)
296 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
335static inline bool
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
351static inline uint64
353{
354 if (unlikely(a == PG_INT64_MIN))
355 return (uint64) PG_INT64_MAX + 1;
356 return (uint64) i64abs(a);
357}
358
359/*------------------------------------------------------------------------
360 * Overflow routines for unsigned integers
361 *------------------------------------------------------------------------
362 */
363
364/*
365 * UINT16
366 */
367static inline bool
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
385static inline bool
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
401static inline bool
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
419static inline bool
421{
422#if defined(HAVE__BUILTIN_OP_OVERFLOW)
423 return __builtin_sub_overflow(0, a, result);
424#else
425 int32 res = -((int32) a);
426
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 */
440static inline bool
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
458static inline bool
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
474static inline bool
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
492static inline bool
494{
495#if defined(HAVE__BUILTIN_OP_OVERFLOW)
496 return __builtin_sub_overflow(0, a, result);
497#else
498 int64 res = -((int64) a);
499
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 */
513static inline bool
515{
516#if defined(HAVE__BUILTIN_OP_OVERFLOW)
517 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
531static inline bool
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
547static inline bool
549{
550#if defined(HAVE__BUILTIN_OP_OVERFLOW)
551 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
575static inline bool
577{
578#if defined(HAVE__BUILTIN_OP_OVERFLOW)
579 return __builtin_sub_overflow(0, a, result);
580#elif defined(HAVE_INT128)
581 int128 res = -((int128) a);
582
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
633static inline int
635{
636 return (int32) a - (int32) b;
637}
638
639static inline int
641{
642 return (int32) a - (int32) b;
643}
644
645static inline int
647{
648 return (a > b) - (a < b);
649}
650
651static inline int
653{
654 return (a > b) - (a < b);
655}
656
657static inline int
659{
660 return (a > b) - (a < b);
661}
662
663static inline int
665{
666 return (a > b) - (a < b);
667}
668
669static inline int
670pg_cmp_size(size_t a, size_t b)
671{
672 return (a > b) - (a < b);
673}
674
675#endif /* COMMON_INT_H */
#define PG_INT32_MAX
Definition: c.h:543
#define PG_UINT32_MAX
Definition: c.h:544
int64_t int64
Definition: c.h:482
int16_t int16
Definition: c.h:480
#define PG_INT16_MIN
Definition: c.h:539
int32_t int32
Definition: c.h:481
#define PG_INT64_MAX
Definition: c.h:546
#define PG_INT64_MIN
Definition: c.h:545
uint64_t uint64
Definition: c.h:486
uint16_t uint16
Definition: c.h:484
#define unlikely(x)
Definition: c.h:330
uint32_t uint32
Definition: c.h:485
#define PG_UINT16_MAX
Definition: c.h:541
#define PG_UINT64_MAX
Definition: c.h:547
#define PG_INT32_MIN
Definition: c.h:542
#define PG_INT16_MAX
Definition: c.h:540
static bool pg_mul_s64_overflow(int64 a, int64 b, int64 *result)
Definition: int.h:293
static bool pg_neg_s32_overflow(int32 a, int32 *result)
Definition: int.h:205
static int pg_cmp_s16(int16 a, int16 b)
Definition: int.h:634
static uint64 pg_abs_s64(int64 a)
Definition: int.h:352
static bool pg_sub_u32_overflow(uint32 a, uint32 b, uint32 *result)
Definition: int.h:459
static int pg_cmp_u32(uint32 a, uint32 b)
Definition: int.h:652
static bool pg_add_u32_overflow(uint32 a, uint32 b, uint32 *result)
Definition: int.h:441
static bool pg_neg_s16_overflow(int16 a, int16 *result)
Definition: int.h:121
static bool pg_sub_s64_overflow(int64 a, int64 b, int64 *result)
Definition: int.h:262
static bool pg_add_u64_overflow(uint64 a, uint64 b, uint64 *result)
Definition: int.h:514
static int pg_cmp_u16(uint16 a, uint16 b)
Definition: int.h:640
static bool pg_neg_u32_overflow(uint32 a, int32 *result)
Definition: int.h:493
static bool pg_sub_s16_overflow(int16 a, int16 b, int16 *result)
Definition: int.h:85
static bool pg_neg_u16_overflow(uint16 a, int16 *result)
Definition: int.h:420
static bool pg_neg_s64_overflow(int64 a, int64 *result)
Definition: int.h:336
static bool pg_mul_s32_overflow(int32 a, int32 b, int32 *result)
Definition: int.h:187
static bool pg_mul_u16_overflow(uint16 a, uint16 b, uint16 *result)
Definition: int.h:402
static bool pg_mul_u32_overflow(uint32 a, uint32 b, uint32 *result)
Definition: int.h:475
static bool pg_mul_s16_overflow(int16 a, int16 b, int16 *result)
Definition: int.h:103
static int pg_cmp_s64(int64 a, int64 b)
Definition: int.h:658
static bool pg_mul_u64_overflow(uint64 a, uint64 b, uint64 *result)
Definition: int.h:548
static bool pg_sub_u16_overflow(uint16 a, uint16 b, uint16 *result)
Definition: int.h:386
static bool pg_add_u16_overflow(uint16 a, uint16 b, uint16 *result)
Definition: int.h:368
static bool pg_add_s16_overflow(int16 a, int16 b, int16 *result)
Definition: int.h:67
static uint32 pg_abs_s32(int32 a)
Definition: int.h:221
static int pg_cmp_s32(int32 a, int32 b)
Definition: int.h:646
static int pg_cmp_u64(uint64 a, uint64 b)
Definition: int.h:664
static int pg_cmp_size(size_t a, size_t b)
Definition: int.h:670
static uint16 pg_abs_s16(int16 a)
Definition: int.h:137
static bool pg_sub_s32_overflow(int32 a, int32 b, int32 *result)
Definition: int.h:169
static bool pg_neg_u64_overflow(uint64 a, int64 *result)
Definition: int.h:576
static bool pg_add_s64_overflow(int64 a, int64 b, int64 *result)
Definition: int.h:235
static bool pg_sub_u64_overflow(uint64 a, uint64 b, uint64 *result)
Definition: int.h:532
static bool pg_add_s32_overflow(int32 a, int32 b, int32 *result)
Definition: int.h:151
int b
Definition: isn.c:69
int a
Definition: isn.c:68