doc/intprops.texi

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