1@node Integer Properties 2@section Integer Properties 3 4@c Copyright (C) 2011--2021 Free Software Foundation, Inc. 5 6@c Permission is granted to copy, distribute and/or modify this document 7@c under the terms of the GNU Free Documentation License, Version 1.3 or 8@c any later version published by the Free Software Foundation; with no 9@c Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A 10@c copy of the license is at <https://www.gnu.org/licenses/fdl-1.3.en.html>. 11 12@c Written by Paul Eggert. 13 14@cindex integer properties 15 16The @code{intprops} module consists of an include file @code{<intprops.h>} 17that defines several macros useful for testing properties of integer 18types. 19 20@cindex integer overflow 21@cindex overflow, integer 22 23Integer overflow is a common source of problems in programs written in 24C and other languages. In some cases, such as signed integer 25arithmetic in C programs, the resulting behavior is undefined, and 26practical platforms do not always behave as if integers wrap around 27reliably. In other cases, such as unsigned integer arithmetic in C, 28the resulting behavior is well-defined, but programs may still 29misbehave badly after overflow occurs. 30 31Many techniques have been proposed to attack these problems. These 32include precondition testing, wraparound behavior where signed integer 33arithmetic is guaranteed to be modular, saturation semantics where 34overflow reliably yields an extreme value, undefined behavior 35sanitizers where overflow is guaranteed to trap, and various static 36analysis techniques. 37 38Gnulib supports wraparound arithmetic and precondition testing, as 39these are relatively easy to support portably and efficiently. There 40are two families of precondition tests: the first, for integer types, 41is easier to use, while the second, for integer ranges, has a simple 42and straightforward portable implementation. 43 44Like other Gnulib modules, the implementation of the @code{intprops} 45module assumes that integers use a two's complement representation, 46but it does not assume that signed integer arithmetic wraps around. 47@xref{Other portability assumptions}. 48 49@menu 50* Arithmetic Type Properties:: Determining properties of arithmetic types. 51* Integer Bounds:: Bounds on integer values and representations. 52* Checking Integer Overflow:: Checking for overflow while computing integers. 53* Wraparound Arithmetic:: Well-defined behavior on integer overflow. 54* Integer Type Overflow:: General integer overflow checking. 55* Integer Range Overflow:: Integer overflow checking if bounds are known. 56@end menu 57 58@node Arithmetic Type Properties 59@subsection Arithmetic Type Properties 60 61@findex TYPE_IS_INTEGER 62@code{TYPE_IS_INTEGER (@var{t})} is an arithmetic constant 63expression that is 1 if the arithmetic type @var{t} is an integer type. 64@code{_Bool} counts as an integer type. 65 66@findex TYPE_SIGNED 67@code{TYPE_SIGNED (@var{t})} is an arithmetic constant expression 68that is 1 if the real type @var{t} is a signed integer type or a 69floating type. If @var{t} is an integer type, @code{TYPE_SIGNED (@var{t})} 70is an integer constant expression. 71 72@findex EXPR_SIGNED 73@code{EXPR_SIGNED (@var{e})} is 1 if the real expression @var{e} 74has a signed integer type or a floating type. If @var{e} is an 75integer constant expression or an arithmetic constant expression, 76@code{EXPR_SIGNED (@var{e})} is likewise. The expression 77@var{e} is not evaluated, and @code{EXPR_SIGNED 78(@var{e})} is typically optimized to a constant. 79 80Example usage: 81 82@example 83#include <intprops.h> 84#include <sys/types.h> 85 86enum 87@{ 88 clock_t_is_integer = TYPE_IS_INTEGER (clock_t), 89 uid_t_is_signed = TYPE_SIGNED (uid_t) 90@}; 91 92int 93CLOCKS_PER_SEC_is_signed (void) 94@{ 95 return EXPR_SIGNED (CLOCKS_PER_SEC); 96@} 97@end example 98 99@node Integer Bounds 100@subsection Integer Bounds 101 102@cindex integer bounds 103 104@findex INT_BUFSIZE_BOUND 105@code{INT_BUFSIZE_BOUND (@var{t})} is an integer constant 106expression that is a bound on the size of the string representing an 107integer type or expression @var{t} in decimal notation, including the 108terminating null character and any leading @code{-} character. For 109example, if @code{INT_BUFSIZE_BOUND (int)} is 12, any value of type 110@code{int} can be represented in 12 bytes or less, including the 111terminating null. The bound is not necessarily tight. 112 113Example usage: 114 115@example 116#include <intprops.h> 117#include <stdio.h> 118int 119int_strlen (int i) 120@{ 121 char buf[INT_BUFSIZE_BOUND (int)]; 122 return sprintf (buf, "%d", i); 123@} 124@end example 125 126@findex INT_STRLEN_BOUND 127@code{INT_STRLEN_BOUND (@var{t})} is an integer constant 128expression that is a bound on the length of the string representing an 129integer type or expression @var{t} in decimal notation, including any 130leading @code{-} character. This is one less than 131@code{INT_BUFSIZE_BOUND (@var{t})}. 132 133@findex TYPE_MINIMUM 134@findex TYPE_MAXIMUM 135@code{TYPE_MINIMUM (@var{t})} and @code{TYPE_MAXIMUM (@var{t})} are 136integer constant expressions equal to the minimum and maximum 137values of the integer type @var{t}. These expressions are of the type 138@var{t}. 139 140Example usage: 141 142@example 143#include <stdbool.h> 144#include <sys/types.h> 145#include <intprops.h> 146bool 147in_off_t_range (long long int a) 148@{ 149 return TYPE_MINIMUM (off_t) <= a && a <= TYPE_MAXIMUM (off_t); 150@} 151@end example 152 153@node Checking Integer Overflow 154@subsection Checking Integer Overflow 155 156@cindex integer overflow checking 157 158Signed integer arithmetic has undefined behavior on overflow in C@. 159Although almost all modern computers use two's complement signed 160arithmetic that is well-defined to wrap around, C compilers routinely 161optimize assuming that signed integer overflow cannot occur, which 162means that a C program cannot easily get at the underlying machine 163arithmetic. For example: 164 165@example 166if ((a + b < b) == (a < 0)) 167 a += b; 168else 169 printf ("overflow\n"); 170@end example 171 172@noindent 173might not work as expected if @code{a} and @code{b} are signed, 174because a compiler can assume that signed overflow cannot occur and 175treat the entire @code{if} expression as if it were true. And even if 176@code{a} is unsigned, the expression might not work as expected if 177@code{b} is negative or is wider than @code{a}. 178 179The following macros work around this problem by returning an overflow 180indication while computing the sum, difference, or product of two 181integers. For example, if @code{i} is of type @code{int}, 182@code{INT_ADD_OK (INT_MAX - 1, 1, &i)} sets @code{i} to 183@code{INT_MAX} and returns true, whereas @code{INT_ADD_OK (INT_MAX, 1, 184&i)} returns false. 185 186Example usage: 187 188@example 189#include <intprops.h> 190#include <stdio.h> 191 192/* Compute A * B, reporting whether overflow occurred. */ 193void 194print_product (long int a, long int b) 195@{ 196 long int r; 197 if (INT_MULTIPLY_OK (a, b, &r)) 198 printf ("result is %ld\n", r); 199 else 200 printf ("overflow\n"); 201@} 202@end example 203 204These macros work for both signed and unsigned integers, so they can 205be used with integer types like @code{time_t} that may or may not be 206signed, depending on the platform. 207 208These macros have the following restrictions: 209 210@itemize @bullet 211@item 212Their first two arguments must be integer expressions. 213 214@item 215Their last argument must be a non-null pointer to an integer. 216 217@item 218They may evaluate their arguments zero or multiple times, so the 219arguments should not have side effects. 220 221@item 222They are not necessarily constant expressions, even if all their 223arguments are constant expressions. 224@end itemize 225 226@table @code 227@item INT_ADD_OK (@var{a}, @var{b}, @var{r}) 228@findex INT_ADD_OK 229Compute the sum of @var{a} and @var{b}. If it fits into 230@code{*@var{r}}, store it there and return true. Otherwise return 231false, possibly modifying @code{*@var{r}} to an unspecified value. 232See above for restrictions. 233 234@item INT_SUBTRACT_OK (@var{a}, @var{b}, @var{r}) 235@findex INT_SUBTRACT_OK 236Compute the difference between @var{a} and @var{b}. If it fits into 237@code{*@var{r}}, store it there and return true. Otherwise return 238false, possibly modifying @code{*@var{r}} to an unspecified value. 239See above for restrictions. 240 241@item INT_MULTIPLY_OK (@var{a}, @var{b}, @var{r}) 242@findex INT_MULTIPLY_OK 243Compute the product of @var{a} and @var{b}. If it fits into 244@code{*@var{r}}, store it there and return true. Otherwise return 245false, possibly modifying @code{*@var{r}} to an unspecified value. 246See above for restrictions. 247@end table 248 249Other macros are available if you need wrapped-around results when 250overflow occurs (@pxref{Wraparound Arithmetic}), or if you need to 251check for overflow in operations other than addition, subtraction, and 252multiplication (@pxref{Integer Type Overflow}). 253 254@node Wraparound Arithmetic 255@subsection Wraparound Arithmetic with Integers 256 257@cindex wraparound integer arithmetic 258 259Signed integer arithmetic has undefined behavior on overflow in C@. 260Although almost all modern computers use two's complement signed 261arithmetic that is well-defined to wrap around, C compilers routinely 262optimize assuming that signed integer overflow cannot occur, which 263means that a C program cannot easily get at the underlying machine 264arithmetic. For example, on a typical machine with 32-bit two's 265complement @code{int} the expression @code{INT_MAX + 1} does not 266necessarily yield @code{INT_MIN}, because the compiler may do 267calculations with a 64-bit register, or may generate code that 268traps on signed integer overflow. 269 270The following macros work around this problem by storing the 271wraparound value, i.e., the low-order bits of the correct answer, and 272by returning an overflow indication. For example, if @code{i} is of 273type @code{int}, @code{INT_ADD_WRAPV (INT_MAX, 1, &i)} sets @code{i} 274to @code{INT_MIN} and returns 1 on a two's complement machine. 275@xref{Integer Type Overflow}. 276 277Example usage: 278 279@example 280#include <intprops.h> 281#include <stdio.h> 282 283/* Print the low order bits of A * B, 284 reporting whether overflow occurred. */ 285void 286print_product (long int a, long int b) 287@{ 288 long int r; 289 int overflow = INT_MULTIPLY_WRAPV (a, b, &r); 290 printf ("result is %ld (%s)\n", r, 291 (overflow 292 ? "after overflow" 293 : "no overflow")); 294@} 295@end example 296 297These macros work for both signed and unsigned integers, so they can 298be used with integer types like @code{time_t} that may or may not be 299signed, depending on the platform. 300 301These macros have the following restrictions: 302 303@itemize @bullet 304@item 305Their first two arguments must be integer expressions. 306 307@item 308Their last argument must be a non-null pointer to an integer. 309 310@item 311They may evaluate their arguments zero or multiple times, so the 312arguments should not have side effects. 313 314@item 315They are not necessarily constant expressions, even if all their 316arguments are constant expressions. 317@end itemize 318 319@table @code 320@item INT_ADD_WRAPV (@var{a}, @var{b}, @var{r}) 321@findex INT_ADD_WRAPV 322Store the low-order bits of the sum of @var{a} and @var{b} into 323@code{*@var{r}}. Return true if overflow occurred, false if the 324low-order bits are the mathematically-correct sum. See above for 325restrictions. 326 327@item INT_SUBTRACT_WRAPV (@var{a}, @var{b}, @var{r}) 328@findex INT_SUBTRACT_WRAPV 329Store the low-order bits of the difference between @var{a} and @var{b} 330into @code{*@var{r}}. Return true if overflow occurred, false if the 331low-order bits are the mathematically-correct difference. See above 332for restrictions. 333 334@item INT_MULTIPLY_WRAPV (@var{a}, @var{b}, @var{r}) 335@findex INT_MULTIPLY_WRAPV 336Store the low-order bits of the product of @var{a} and @var{b} into 337@code{*@var{r}}. Return true if overflow occurred, false if the 338low-order bits are the mathematically-correct product. See above for 339restrictions. 340@end table 341 342Other macros are available if you do not need wrapped-around results 343when overflow occurs (@pxref{Checking Integer Overflow}), or if you 344need to check for overflow in operations other than addition, 345subtraction, and multiplication (@pxref{Integer Type Overflow}). 346 347@node Integer Type Overflow 348@subsection Integer Type Overflow 349 350@cindex integer type overflow 351@cindex overflow, integer type 352 353Although unsigned integer arithmetic wraps around modulo a power of 354two, signed integer arithmetic has undefined behavior on overflow in 355C@. Almost all modern computers use two's complement signed 356arithmetic that is well-defined to wrap around, but C compilers 357routinely optimize based on the assumption that signed integer 358overflow cannot occur, which means that a C program cannot easily get 359at the underlying machine behavior. For example, the signed integer 360expression @code{(a + b < b) != (a < 0)} is not a reliable test for 361whether @code{a + b} overflows, because a compiler can assume that 362signed overflow cannot occur and treat the entire expression as if it 363were false. 364 365These macros yield 1 if the corresponding C operators might not yield 366numerically correct answers due to arithmetic overflow of an integer 367type. They work correctly on all known practical hosts, and do not 368rely on undefined behavior due to signed arithmetic overflow. They 369are integer constant expressions if their arguments are. They 370are typically easier to use than the integer range overflow macros 371(@pxref{Integer Range Overflow}), and they support more operations and 372evaluation contexts than the wraparound macros (@pxref{Wraparound 373Arithmetic}). 374 375Example usage: 376 377@example 378#include <intprops.h> 379#include <limits.h> 380#include <stdio.h> 381 382/* Print A * B if in range, an overflow 383 indicator otherwise. */ 384void 385print_product (long int a, long int b) 386@{ 387 if (INT_MULTIPLY_OVERFLOW (a, b)) 388 printf ("multiply would overflow"); 389 else 390 printf ("product is %ld", a * b); 391@} 392 393/* Does the product of two ints always fit 394 in a long int? */ 395enum @{ 396 INT_PRODUCTS_FIT_IN_LONG 397 = ! (INT_MULTIPLY_OVERFLOW 398 ((long int) INT_MIN, INT_MIN)) 399@}; 400@end example 401 402@noindent 403These macros have the following restrictions: 404 405@itemize @bullet 406@item 407Their arguments must be integer expressions. 408 409@item 410They may evaluate their arguments zero or multiple times, so the 411arguments should not have side effects. 412@end itemize 413 414@noindent 415These macros are tuned for their last argument being a constant. 416 417@table @code 418@item INT_ADD_OVERFLOW (@var{a}, @var{b}) 419@findex INT_ADD_OVERFLOW 420Yield 1 if @code{@var{a} + @var{b}} would overflow. See above for 421restrictions. 422 423@item INT_SUBTRACT_OVERFLOW (@var{a}, @var{b}) 424@findex INT_SUBTRACT_OVERFLOW 425Yield 1 if @code{@var{a} - @var{b}} would overflow. See above for 426restrictions. 427 428@item INT_NEGATE_OVERFLOW (@var{a}) 429@findex INT_NEGATE_OVERFLOW 430Yields 1 if @code{-@var{a}} would overflow. See above for restrictions. 431 432@item INT_MULTIPLY_OVERFLOW (@var{a}, @var{b}) 433@findex INT_MULTIPLY_OVERFLOW 434Yield 1 if @code{@var{a} * @var{b}} would overflow. See above for 435restrictions. 436 437@item INT_DIVIDE_OVERFLOW (@var{a}, @var{b}) 438@findex INT_DIVIDE_OVERFLOW 439Yields 1 if @code{@var{a} / @var{b}} would overflow. See above for 440restrictions. Division overflow can happen on two's complement hosts 441when dividing the most negative integer by @minus{}1. This macro does 442not check for division by zero. 443 444@item INT_REMAINDER_OVERFLOW (@var{a}, @var{b}) 445@findex INT_REMAINDER_OVERFLOW 446Yield 1 if @code{@var{a} % @var{b}} would overflow. See above for 447restrictions. Remainder overflow can happen on two's complement hosts 448when dividing the most negative integer by @minus{}1; although the 449mathematical result is always 0, in practice some implementations 450trap, so this counts as an overflow. This macro does not check for 451division by zero. 452 453@item INT_LEFT_SHIFT_OVERFLOW (@var{a}, @var{b}) 454@findex INT_LEFT_SHIFT_OVERFLOW 455Yield 1 if @code{@var{a} << @var{b}} would overflow. See above for 456restrictions. The C standard says that behavior is undefined for 457shifts unless 0@leq{}@var{b}<@var{w} where @var{w} is @var{a}'s word 458width, and that when @var{a} is negative then @code{@var{a} << 459@var{b}} has undefined behavior, but this macro does not check these 460other restrictions. 461@end table 462 463@node Integer Range Overflow 464@subsection Integer Range Overflow 465 466@cindex integer range overflow 467@cindex overflow, integer range 468 469These macros yield 1 if the corresponding C operators might not yield 470numerically correct answers due to arithmetic overflow. They do not 471rely on undefined or implementation-defined behavior. They are 472integer constant expressions if their arguments are. Their 473implementations are simple and straightforward, but they are typically 474harder to use than the integer type overflow macros. @xref{Integer 475Type Overflow}. 476 477Although the implementation of these macros is similar to that 478suggested in the SEI CERT C Secure Coding Standard, 479in its two sections 480``@url{https://www.securecoding.cert.org/confluence/display/c/INT30-C.+Ensure+that+unsigned+integer+operations+do+not+wrap, 481INT30-C@. Ensure that unsigned integer operations do not wrap}'' and 482``@url{https://www.securecoding.cert.org/confluence/display/c/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow, 483INT32-C@. Ensure that operations on signed integers do not result in 484overflow}'', Gnulib's implementation was derived independently of 485CERT's suggestions. 486 487Example usage: 488 489@example 490#include <intprops.h> 491#include <limits.h> 492#include <stdio.h> 493 494void 495print_product (long int a, long int b) 496@{ 497 if (INT_MULTIPLY_RANGE_OVERFLOW (a, b, LONG_MIN, LONG_MAX)) 498 printf ("multiply would overflow"); 499 else 500 printf ("product is %ld", a * b); 501@} 502 503/* Does the product of two ints always fit 504 in a long int? */ 505enum @{ 506 INT_PRODUCTS_FIT_IN_LONG 507 = ! (INT_MULTIPLY_RANGE_OVERFLOW 508 ((long int) INT_MIN, (long int) INT_MIN, 509 LONG_MIN, LONG_MAX)) 510@}; 511@end example 512 513@noindent 514These macros have the following restrictions: 515 516@itemize @bullet 517@item 518Their arguments must be integer expressions. 519 520@item 521They may evaluate their arguments zero or multiple times, so 522the arguments should not have side effects. 523 524@item 525The arithmetic arguments (including the @var{min} and @var{max} 526arguments) must be of the same integer type after the usual arithmetic 527conversions, and the type must have minimum value @var{min} and 528maximum @var{max}. Unsigned values should use a zero @var{min} of the 529proper type, for example, @code{(unsigned int) 0}. 530@end itemize 531 532@noindent 533These macros are tuned for constant @var{min} and @var{max}. For 534commutative operations such as @code{@var{a} + @var{b}}, they are also 535tuned for constant @var{b}. 536 537@table @code 538@item INT_ADD_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max}) 539@findex INT_ADD_RANGE_OVERFLOW 540Yield 1 if @code{@var{a} + @var{b}} would overflow in 541[@var{min},@var{max}] integer arithmetic. See above for restrictions. 542 543@item INT_SUBTRACT_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max}) 544@findex INT_SUBTRACT_RANGE_OVERFLOW 545Yield 1 if @code{@var{a} - @var{b}} would overflow in 546[@var{min},@var{max}] integer arithmetic. See above for restrictions. 547 548@item INT_NEGATE_RANGE_OVERFLOW (@var{a}, @var{min}, @var{max}) 549@findex INT_NEGATE_RANGE_OVERFLOW 550Yield 1 if @code{-@var{a}} would overflow in [@var{min},@var{max}] 551integer arithmetic. See above for restrictions. 552 553@item INT_MULTIPLY_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max}) 554@findex INT_MULTIPLY_RANGE_OVERFLOW 555Yield 1 if @code{@var{a} * @var{b}} would overflow in 556[@var{min},@var{max}] integer arithmetic. See above for restrictions. 557 558@item INT_DIVIDE_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max}) 559@findex INT_DIVIDE_RANGE_OVERFLOW 560Yield 1 if @code{@var{a} / @var{b}} would overflow in 561[@var{min},@var{max}] integer arithmetic. See above for restrictions. 562Division overflow can happen on two's complement hosts when dividing 563the most negative integer by @minus{}1. This macro does not check for 564division by zero. 565 566@item INT_REMAINDER_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max}) 567@findex INT_REMAINDER_RANGE_OVERFLOW 568Yield 1 if @code{@var{a} % @var{b}} would overflow in 569[@var{min},@var{max}] integer arithmetic. See above for restrictions. 570Remainder overflow can happen on two's complement hosts when dividing 571the most negative integer by @minus{}1; although the mathematical 572result is always 0, in practice some implementations trap, so this 573counts as an overflow. This macro does not check for division by 574zero. 575 576@item INT_LEFT_SHIFT_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max}) 577@findex INT_LEFT_SHIFT_RANGE_OVERFLOW 578Yield 1 if @code{@var{a} << @var{b}} would overflow in 579[@var{min},@var{max}] integer arithmetic. See above for restrictions. 580Here, @var{min} and @var{max} are for @var{a} only, and @var{b} need 581not be of the same type as the other arguments. The C standard says 582that behavior is undefined for shifts unless 0@leq{}@var{b}<@var{w} 583where @var{w} is @var{a}'s word width, and that when @var{a} is negative 584then @code{@var{a} << @var{b}} has undefined behavior, but this macro 585does not check these other restrictions. 586@end table 587