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 : * - If a + b overflows, return true, otherwise store the result of a + b
27 : * into *result. The content of *result is implementation defined in case of
28 : * overflow.
29 : * - If a - b overflows, return true, otherwise store the result of a - b
30 : * into *result. The content of *result is implementation defined in case of
31 : * overflow.
32 : * - If a * b overflows, return true, otherwise store the result of a * b
33 : * into *result. The content of *result is implementation defined in case of
34 : * overflow.
35 : *---------
36 : */
37 :
38 : /*------------------------------------------------------------------------
39 : * Overflow routines for signed integers
40 : *------------------------------------------------------------------------
41 : */
42 :
43 : /*
44 : * INT16
45 : */
46 : static inline bool
47 54 : pg_add_s16_overflow(int16 a, int16 b, int16 *result)
48 : {
49 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
50 54 : return __builtin_add_overflow(a, b, result);
51 : #else
52 : int32 res = (int32) a + (int32) b;
53 :
54 : if (res > PG_INT16_MAX || res < PG_INT16_MIN)
55 : {
56 : *result = 0x5EED; /* to avoid spurious warnings */
57 : return true;
58 : }
59 : *result = (int16) res;
60 : return false;
61 : #endif
62 : }
63 :
64 : static inline bool
65 1218 : pg_sub_s16_overflow(int16 a, int16 b, int16 *result)
66 : {
67 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
68 1218 : return __builtin_sub_overflow(a, b, result);
69 : #else
70 : int32 res = (int32) a - (int32) b;
71 :
72 : if (res > PG_INT16_MAX || res < PG_INT16_MIN)
73 : {
74 : *result = 0x5EED; /* to avoid spurious warnings */
75 : return true;
76 : }
77 : *result = (int16) res;
78 : return false;
79 : #endif
80 : }
81 :
82 : static inline bool
83 54 : pg_mul_s16_overflow(int16 a, int16 b, int16 *result)
84 : {
85 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
86 54 : return __builtin_mul_overflow(a, b, result);
87 : #else
88 : int32 res = (int32) a * (int32) b;
89 :
90 : if (res > PG_INT16_MAX || res < PG_INT16_MIN)
91 : {
92 : *result = 0x5EED; /* to avoid spurious warnings */
93 : return true;
94 : }
95 : *result = (int16) res;
96 : return false;
97 : #endif
98 : }
99 :
100 : /*
101 : * INT32
102 : */
103 : static inline bool
104 19917380 : pg_add_s32_overflow(int32 a, int32 b, int32 *result)
105 : {
106 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
107 19917380 : return __builtin_add_overflow(a, b, result);
108 : #else
109 : int64 res = (int64) a + (int64) b;
110 :
111 : if (res > PG_INT32_MAX || res < PG_INT32_MIN)
112 : {
113 : *result = 0x5EED; /* to avoid spurious warnings */
114 : return true;
115 : }
116 : *result = (int32) res;
117 : return false;
118 : #endif
119 : }
120 :
121 : static inline bool
122 1445998 : pg_sub_s32_overflow(int32 a, int32 b, int32 *result)
123 : {
124 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
125 1445998 : return __builtin_sub_overflow(a, b, result);
126 : #else
127 : int64 res = (int64) a - (int64) b;
128 :
129 : if (res > PG_INT32_MAX || res < PG_INT32_MIN)
130 : {
131 : *result = 0x5EED; /* to avoid spurious warnings */
132 : return true;
133 : }
134 : *result = (int32) res;
135 : return false;
136 : #endif
137 : }
138 :
139 : static inline bool
140 3576934 : pg_mul_s32_overflow(int32 a, int32 b, int32 *result)
141 : {
142 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
143 3576934 : return __builtin_mul_overflow(a, b, result);
144 : #else
145 : int64 res = (int64) a * (int64) b;
146 :
147 : if (res > PG_INT32_MAX || res < PG_INT32_MIN)
148 : {
149 : *result = 0x5EED; /* to avoid spurious warnings */
150 : return true;
151 : }
152 : *result = (int32) res;
153 : return false;
154 : #endif
155 : }
156 :
157 : /*
158 : * INT64
159 : */
160 : static inline bool
161 20773240 : pg_add_s64_overflow(int64 a, int64 b, int64 *result)
162 : {
163 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
164 20773240 : return __builtin_add_overflow(a, b, result);
165 : #elif defined(HAVE_INT128)
166 : int128 res = (int128) a + (int128) b;
167 :
168 : if (res > PG_INT64_MAX || res < PG_INT64_MIN)
169 : {
170 : *result = 0x5EED; /* to avoid spurious warnings */
171 : return true;
172 : }
173 : *result = (int64) res;
174 : return false;
175 : #else
176 : if ((a > 0 && b > 0 && a > PG_INT64_MAX - b) ||
177 : (a < 0 && b < 0 && a < PG_INT64_MIN - b))
178 : {
179 : *result = 0x5EED; /* to avoid spurious warnings */
180 : return true;
181 : }
182 : *result = a + b;
183 : return false;
184 : #endif
185 : }
186 :
187 : static inline bool
188 337496 : pg_sub_s64_overflow(int64 a, int64 b, int64 *result)
189 : {
190 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
191 337496 : return __builtin_sub_overflow(a, b, result);
192 : #elif defined(HAVE_INT128)
193 : int128 res = (int128) a - (int128) b;
194 :
195 : if (res > PG_INT64_MAX || res < PG_INT64_MIN)
196 : {
197 : *result = 0x5EED; /* to avoid spurious warnings */
198 : return true;
199 : }
200 : *result = (int64) res;
201 : return false;
202 : #else
203 : /*
204 : * Note: overflow is also possible when a == 0 and b < 0 (specifically,
205 : * when b == PG_INT64_MIN).
206 : */
207 : if ((a < 0 && b > 0 && a < PG_INT64_MIN + b) ||
208 : (a >= 0 && b < 0 && a > PG_INT64_MAX + b))
209 : {
210 : *result = 0x5EED; /* to avoid spurious warnings */
211 : return true;
212 : }
213 : *result = a - b;
214 : return false;
215 : #endif
216 : }
217 :
218 : static inline bool
219 66688 : pg_mul_s64_overflow(int64 a, int64 b, int64 *result)
220 : {
221 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
222 66688 : return __builtin_mul_overflow(a, b, result);
223 : #elif defined(HAVE_INT128)
224 : int128 res = (int128) a * (int128) b;
225 :
226 : if (res > PG_INT64_MAX || res < PG_INT64_MIN)
227 : {
228 : *result = 0x5EED; /* to avoid spurious warnings */
229 : return true;
230 : }
231 : *result = (int64) res;
232 : return false;
233 : #else
234 : /*
235 : * Overflow can only happen if at least one value is outside the range
236 : * sqrt(min)..sqrt(max) so check that first as the division can be quite a
237 : * bit more expensive than the multiplication.
238 : *
239 : * Multiplying by 0 or 1 can't overflow of course and checking for 0
240 : * separately avoids any risk of dividing by 0. Be careful about dividing
241 : * INT_MIN by -1 also, note reversing the a and b to ensure we're always
242 : * dividing it by a positive value.
243 : *
244 : */
245 : if ((a > PG_INT32_MAX || a < PG_INT32_MIN ||
246 : b > PG_INT32_MAX || b < PG_INT32_MIN) &&
247 : a != 0 && a != 1 && b != 0 && b != 1 &&
248 : ((a > 0 && b > 0 && a > PG_INT64_MAX / b) ||
249 : (a > 0 && b < 0 && b < PG_INT64_MIN / a) ||
250 : (a < 0 && b > 0 && a < PG_INT64_MIN / b) ||
251 : (a < 0 && b < 0 && a < PG_INT64_MAX / 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 : /*------------------------------------------------------------------------
262 : * Overflow routines for unsigned integers
263 : *------------------------------------------------------------------------
264 : */
265 :
266 : /*
267 : * UINT16
268 : */
269 : static inline bool
270 : pg_add_u16_overflow(uint16 a, uint16 b, uint16 *result)
271 : {
272 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
273 : return __builtin_add_overflow(a, b, result);
274 : #else
275 : uint16 res = a + b;
276 :
277 : if (res < a)
278 : {
279 : *result = 0x5EED; /* to avoid spurious warnings */
280 : return true;
281 : }
282 : *result = res;
283 : return false;
284 : #endif
285 : }
286 :
287 : static inline bool
288 : pg_sub_u16_overflow(uint16 a, uint16 b, uint16 *result)
289 : {
290 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
291 : return __builtin_sub_overflow(a, b, result);
292 : #else
293 : if (b > a)
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 bool
304 : pg_mul_u16_overflow(uint16 a, uint16 b, uint16 *result)
305 : {
306 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
307 : return __builtin_mul_overflow(a, b, result);
308 : #else
309 : uint32 res = (uint32) a * (uint32) b;
310 :
311 : if (res > PG_UINT16_MAX)
312 : {
313 : *result = 0x5EED; /* to avoid spurious warnings */
314 : return true;
315 : }
316 : *result = (uint16) res;
317 : return false;
318 : #endif
319 : }
320 :
321 : /*
322 : * INT32
323 : */
324 : static inline bool
325 : pg_add_u32_overflow(uint32 a, uint32 b, uint32 *result)
326 : {
327 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
328 : return __builtin_add_overflow(a, b, result);
329 : #else
330 : uint32 res = a + b;
331 :
332 : if (res < a)
333 : {
334 : *result = 0x5EED; /* to avoid spurious warnings */
335 : return true;
336 : }
337 : *result = res;
338 : return false;
339 : #endif
340 : }
341 :
342 : static inline bool
343 : pg_sub_u32_overflow(uint32 a, uint32 b, uint32 *result)
344 : {
345 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
346 : return __builtin_sub_overflow(a, b, result);
347 : #else
348 : if (b > a)
349 : {
350 : *result = 0x5EED; /* to avoid spurious warnings */
351 : return true;
352 : }
353 : *result = a - b;
354 : return false;
355 : #endif
356 : }
357 :
358 : static inline bool
359 : pg_mul_u32_overflow(uint32 a, uint32 b, uint32 *result)
360 : {
361 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
362 : return __builtin_mul_overflow(a, b, result);
363 : #else
364 : uint64 res = (uint64) a * (uint64) b;
365 :
366 : if (res > PG_UINT32_MAX)
367 : {
368 : *result = 0x5EED; /* to avoid spurious warnings */
369 : return true;
370 : }
371 : *result = (uint32) res;
372 : return false;
373 : #endif
374 : }
375 :
376 : /*
377 : * UINT64
378 : */
379 : static inline bool
380 178 : pg_add_u64_overflow(uint64 a, uint64 b, uint64 *result)
381 : {
382 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
383 178 : return __builtin_add_overflow(a, b, result);
384 : #else
385 : uint64 res = a + b;
386 :
387 : if (res < a)
388 : {
389 : *result = 0x5EED; /* to avoid spurious warnings */
390 : return true;
391 : }
392 : *result = res;
393 : return false;
394 : #endif
395 : }
396 :
397 : static inline bool
398 : pg_sub_u64_overflow(uint64 a, uint64 b, uint64 *result)
399 : {
400 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
401 : return __builtin_sub_overflow(a, b, result);
402 : #else
403 : if (b > a)
404 : {
405 : *result = 0x5EED; /* to avoid spurious warnings */
406 : return true;
407 : }
408 : *result = a - b;
409 : return false;
410 : #endif
411 : }
412 :
413 : static inline bool
414 178 : pg_mul_u64_overflow(uint64 a, uint64 b, uint64 *result)
415 : {
416 : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
417 178 : return __builtin_mul_overflow(a, b, result);
418 : #elif defined(HAVE_INT128)
419 : uint128 res = (uint128) a * (uint128) b;
420 :
421 : if (res > PG_UINT64_MAX)
422 : {
423 : *result = 0x5EED; /* to avoid spurious warnings */
424 : return true;
425 : }
426 : *result = (uint64) res;
427 : return false;
428 : #else
429 : uint64 res = a * b;
430 :
431 : if (a != 0 && b != res / a)
432 : {
433 : *result = 0x5EED; /* to avoid spurious warnings */
434 : return true;
435 : }
436 : *result = res;
437 : return false;
438 : #endif
439 : }
440 :
441 : /*------------------------------------------------------------------------
442 : *
443 : * Comparison routines for integer types.
444 : *
445 : * These routines are primarily intended for use in qsort() comparator
446 : * functions and therefore return a positive integer, 0, or a negative
447 : * integer depending on whether "a" is greater than, equal to, or less
448 : * than "b", respectively. These functions are written to be as efficient
449 : * as possible without introducing overflow risks, thereby helping ensure
450 : * the comparators that use them are transitive.
451 : *
452 : * Types with fewer than 32 bits are cast to signed integers and
453 : * subtracted. Other types are compared using > and <, and the results of
454 : * those comparisons (which are either (int) 0 or (int) 1 per the C
455 : * standard) are subtracted.
456 : *
457 : * NB: If the comparator function is inlined, some compilers may produce
458 : * worse code with these helper functions than with code with the
459 : * following form:
460 : *
461 : * if (a < b)
462 : * return -1;
463 : * if (a > b)
464 : * return 1;
465 : * return 0;
466 : *
467 : *------------------------------------------------------------------------
468 : */
469 :
470 : static inline int
471 68744684 : pg_cmp_s16(int16 a, int16 b)
472 : {
473 68744684 : return (int32) a - (int32) b;
474 : }
475 :
476 : static inline int
477 9779688 : pg_cmp_u16(uint16 a, uint16 b)
478 : {
479 9779688 : return (int32) a - (int32) b;
480 : }
481 :
482 : static inline int
483 548743872 : pg_cmp_s32(int32 a, int32 b)
484 : {
485 548743872 : return (a > b) - (a < b);
486 : }
487 :
488 : static inline int
489 57389466 : pg_cmp_u32(uint32 a, uint32 b)
490 : {
491 57389466 : return (a > b) - (a < b);
492 : }
493 :
494 : static inline int
495 : pg_cmp_s64(int64 a, int64 b)
496 : {
497 : return (a > b) - (a < b);
498 : }
499 :
500 : static inline int
501 15153296 : pg_cmp_u64(uint64 a, uint64 b)
502 : {
503 15153296 : return (a > b) - (a < b);
504 : }
505 :
506 : static inline int
507 4 : pg_cmp_size(size_t a, size_t b)
508 : {
509 4 : return (a > b) - (a < b);
510 : }
511 :
512 : #endif /* COMMON_INT_H */
|
