doc/intprops.texi

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