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-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
2359 andres@anarazel.de 47 :CBC 27 : pg_add_s16_overflow(int16 a, int16 b, int16 *result)
48 : : {
49 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
50 : 27 : 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 : 609 : pg_sub_s16_overflow(int16 a, int16 b, int16 *result)
66 : : {
67 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
68 : 609 : 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 : 27 : pg_mul_s16_overflow(int16 a, int16 b, int16 *result)
84 : : {
85 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
86 : 27 : 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 : 11069230 : pg_add_s32_overflow(int32 a, int32 b, int32 *result)
105 : : {
106 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
107 : 11069230 : 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 : 1447331 : pg_sub_s32_overflow(int32 a, int32 b, int32 *result)
123 : : {
124 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
125 : 1447331 : 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 : 1877818 : pg_mul_s32_overflow(int32 a, int32 b, int32 *result)
141 : : {
142 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
143 : 1877818 : 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 : 10144195 : pg_add_s64_overflow(int64 a, int64 b, int64 *result)
162 : : {
163 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
164 : 10144195 : 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 : 175603 : pg_sub_s64_overflow(int64 a, int64 b, int64 *result)
189 : : {
190 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
191 : 175603 : 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 : 33251 : pg_mul_s64_overflow(int64 a, int64 b, int64 *result)
220 : : {
221 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
222 : 33251 : 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
1686 michael@paquier.xyz 380 : 89 : pg_add_u64_overflow(uint64 a, uint64 b, uint64 *result)
381 : : {
382 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
383 : 89 : 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 : 89 : pg_mul_u64_overflow(uint64 a, uint64 b, uint64 *result)
415 : : {
416 : : #if defined(HAVE__BUILTIN_OP_OVERFLOW)
417 : 89 : 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
58 nathan@postgresql.or 471 :GNC 37198353 : pg_cmp_s16(int16 a, int16 b)
472 : : {
473 : 37198353 : return (int32) a - (int32) b;
474 : : }
475 : :
476 : : static inline int
477 : 6408859 : pg_cmp_u16(uint16 a, uint16 b)
478 : : {
479 : 6408859 : return (int32) a - (int32) b;
480 : : }
481 : :
482 : : static inline int
483 : 272864386 : pg_cmp_s32(int32 a, int32 b)
484 : : {
485 : 272864386 : return (a > b) - (a < b);
486 : : }
487 : :
488 : : static inline int
489 : 35205236 : pg_cmp_u32(uint32 a, uint32 b)
490 : : {
491 : 35205236 : 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 : 8146753 : pg_cmp_u64(uint64 a, uint64 b)
502 : : {
503 : 8146753 : return (a > b) - (a < b);
504 : : }
505 : :
506 : : static inline int
507 : 2 : pg_cmp_size(size_t a, size_t b)
508 : : {
509 : 2 : return (a > b) - (a < b);
510 : : }
511 : :
512 : : #endif /* COMMON_INT_H */
|
