doc/intprops.texi

   1 @node Integer Properties
   2 @section Integer Properties
   3
   4 @c Copyright (C) 2011-2012 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, with no Front-Cover Texts, and with 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, GCC's @option{-ftrapv} option, GCC's
  34 no-undefined-overflow branch, the As-if Infinitely Ranged (AIR) model
  35 implemented in Clang, saturation semantics where overflow reliably
  36 yields an extreme value, the RICH static transformer to an
  37 overflow-checking variant, and special testing methods.  For more
  38 information about these techniques, see: Dannenberg R, Dormann W,
  39 Keaton D @emph{et al.},
  40 @url{http://www.sei.cmu.edu/library/abstracts/reports/10tn008.cfm,
  41 As-if Infinitely Ranged integer model -- 2nd ed.}, Software Engineering
  42 Institute Technical Note CMU/SEI-2010-TN-008, April 2010.
  43
  44 Gnulib supports the precondition testing technique, as this is easy to
  45 support portably.  There are two families of precondition tests: the
  46 first, for integer ranges, has a simple and straightforward implementation,
  47 while the second, for integer types, is easier to use.
  48
  49 @menu
  50 * Integer Type Determination::  Whether a type has integer properties.
  51 * Integer Bounds::              Bounds on integer values and representations.
  52 * Integer Range Overflow::      Integer overflow checking if bounds are known.
  53 * Integer Type Overflow::       General integer overflow checking.
  54 @end menu
  55
  56 @node Integer Type Determination
  57 @subsection Integer Type Determination
  58
  59 @findex TYPE_IS_INTEGER
  60 @code{TYPE_IS_INTEGER (@var{t})} expands to a constant
  61 expression that is 1 if the arithmetic type @var{t} is an integer type.
  62 @code{_Bool} counts as an integer type.
  63
  64 @findex TYPE_SIGNED
  65 @code{TYPE_SIGNED (@var{t})} expands to a constant expression
  66 that is 1 if the arithmetic type @var{t} is a signed integer type or a
  67 floating type.  If @var{t} is an integer type, @code{TYPE_SIGNED (@var{t})}
  68 expands to an integer constant expression.
  69
  70 Example usage:
  71
  72 @example
  73 #include <intprops.h>
  74 #include <time.h>
  75 enum
  76 @{
  77   time_t_is_signed_integer =
  78     TYPE_IS_INTEGER (time_t) && TYPE_SIGNED (time_t)
  79 @};
  80 @end example
  81
  82 @node Integer Bounds
  83 @subsection Integer Bounds
  84
  85 @cindex integer bounds
  86
  87 @findex INT_BUFSIZE_BOUND
  88 @code{INT_BUFSIZE_BOUND (@var{t})} expands to an integer constant
  89 expression that is a bound on the size of the string representing an
  90 integer type or expression @var{t} in decimal notation, including the
  91 terminating null character and any leading @code{-} character.  For
  92 example, if @code{INT_STRLEN_BOUND (int)} is 12, any value of type
  93 @code{int} can be represented in 12 bytes or less, including the
  94 terminating null.  The bound is not necessarily tight.
  95
  96 Example usage:
  97
  98 @example
  99 #include <intprops.h>
 100 #include <stdio.h>
 101 int
 102 int_strlen (int i)
 103 @{
 104   char buf[INT_BUFSIZE_BOUND (int)];
 105   return sprintf (buf, "%d", i);
 106 @}
 107 @end example
 108
 109 @findex INT_STRLEN_BOUND
 110 @code{INT_STRLEN_BOUND (@var{t})} expands to an integer constant
 111 expression that is a bound on the length of the string representing an
 112 integer type or expression @var{t} in decimal notation, including any
 113 leading @code{-} character.  This is one less than
 114 @code{INT_BUFSIZE_BOUND (@var{t})}.
 115
 116 @findex TYPE_MINIMUM
 117 @findex TYPE_MAXIMUM
 118 @code{TYPE_MINIMUM (@var{t})} and @code{TYPE_MAXIMUM (@var{t})} expand
 119 to integer constant expressions equal to the minimum and maximum
 120 values of the integer type @var{t}.  These expressions are of the type
 121 @var{t} (or more precisely, the type @var{t} after integer
 122 promotions).
 123
 124 Example usage:
 125
 126 @example
 127 #include <stdint.h>
 128 #include <sys/types.h>
 129 #include <intprops.h>
 130 int
 131 in_off_t_range (intmax_t a)
 132 @{
 133   return TYPE_MINIMUM (off_t) <= a && a <= TYPE_MAXIMUM (off_t);
 134 @}
 135 @end example
 136
 137 @node Integer Range Overflow
 138 @subsection Integer Range Overflow
 139
 140 @cindex integer range overflow
 141 @cindex overflow, integer range
 142
 143 These macros yield 1 if the corresponding C operators might not yield
 144 numerically correct answers due to arithmetic overflow.  They do not
 145 rely on undefined or implementation-defined behavior.  They expand to
 146 integer constant expressions if their arguments are.  Their
 147 implementations are simple and straightforward, but they are typically
 148 harder to use than the integer type overflow macros.  @xref{Integer
 149 Type Overflow}.
 150
 151 Although the implementation of these macros is similar to that
 152 suggested in Seacord R, The CERT C Secure Coding Standard (2009,
 153 revised 2011), in its two sections
 154 ``@url{https://www.securecoding.cert.org/confluence/display/seccode/INT30-C.+Ensure+that+unsigned+integer+operations+do+not+wrap,
 155 INT30-C. Ensure that unsigned integer operations do not wrap}'' and
 156 ``@url{https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow,
 157 INT32-C. Ensure that operations on signed integers do not result in
 158 overflow}'', Gnulib's implementation was derived independently of
 159 CERT's suggestions.
 160
 161 Example usage:
 162
 163 @example
 164 #include <intprops.h>
 165 void
 166 print_product (long int a, long int b)
 167 @{
 168   if (INT_MULTIPLY_RANGE_OVERFLOW (a, b, LONG_MIN, LONG_MAX))
 169     printf ("multiply would overflow");
 170   else
 171     printf ("product is %ld", a * b);
 172 @}
 173 @end example
 174
 175 @noindent
 176 These macros have the following restrictions:
 177
 178 @itemize @bullet
 179 @item
 180 Their arguments must be integer expressions.
 181
 182 @item
 183 They may evaluate their arguments zero or multiple times, so
 184 the arguments should not have side effects.
 185
 186 @item
 187 The arithmetic arguments (including the @var{min} and @var{max}
 188 arguments) must be of the same integer type after the usual arithmetic
 189 conversions, and the type must have minimum value @var{min} and
 190 maximum @var{max}.  Unsigned values should use a zero @var{min} of the
 191 proper type, for example, @code{(unsigned int) 0}.
 192 @end itemize
 193
 194 These macros are tuned for constant @var{min} and @var{max}.  For
 195 commutative operations such as @code{@var{a} + @var{b}}, they are also
 196 tuned for constant @var{b}.
 197
 198 @table @code
 199 @item INT_ADD_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max})
 200 @findex INT_ADD_RANGE_OVERFLOW
 201 Yield 1 if @code{@var{a} + @var{b}} would overflow in
 202 [@var{min},@var{max}] integer arithmetic.  See above for restrictions.
 203
 204 @item INT_SUBTRACT_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max})
 205 @findex INT_SUBTRACT_RANGE_OVERFLOW
 206 Yield 1 if @code{@var{a} - @var{b}} would overflow in
 207 [@var{min},@var{max}] integer arithmetic.  See above for restrictions.
 208
 209 @item INT_NEGATE_RANGE_OVERFLOW (@var{a}, @var{min}, @var{max})
 210 @findex INT_NEGATE_RANGE_OVERFLOW
 211 Yield 1 if @code{-@var{a}} would overflow in [@var{min},@var{max}]
 212 integer arithmetic.  See above for restrictions.
 213
 214 @item INT_MULTIPLY_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max})
 215 @findex INT_MULTIPLY_RANGE_OVERFLOW
 216 Yield 1 if @code{@var{a} * @var{b}} would overflow in
 217 [@var{min},@var{max}] integer arithmetic.  See above for restrictions.
 218
 219 @item INT_DIVIDE_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max})
 220 @findex INT_DIVIDE_RANGE_OVERFLOW
 221 Yield 1 if @code{@var{a} / @var{b}} would overflow in
 222 [@var{min},@var{max}] integer arithmetic.  See above for restrictions.
 223 Division overflow can happen on two's complement hosts when dividing
 224 the most negative integer by @minus{}1.  This macro does not check for
 225 division by zero.
 226
 227 @item INT_REMAINDER_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max})
 228 @findex INT_REMAINDER_RANGE_OVERFLOW
 229 Yield 1 if @code{@var{a} % @var{b}} would overflow in
 230 [@var{min},@var{max}] integer arithmetic.  See above for restrictions.
 231 Remainder overflow can happen on two's complement hosts when dividing
 232 the most negative integer by @minus{}1; although the mathematical
 233 result is always 0, in practice some implementations trap, so this
 234 counts as an overflow.  This macro does not check for division by
 235 zero.
 236
 237 @item INT_LEFT_SHIFT_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max})
 238 @findex INT_LEFT_SHIFT_RANGE_OVERFLOW
 239 Yield 1 if @code{@var{a} << @var{b}} would overflow in
 240 [@var{min},@var{max}] integer arithmetic.  See above for restrictions.
 241 Here, @var{min} and @var{max} are for @var{a} only, and @var{b} need
 242 not be of the same type as the other arguments.  The C standard says
 243 that behavior is undefined for shifts unless 0@leq{}@var{b}<@var{w}
 244 where @var{w} is @var{a}'s word width, and that when @var{a} is negative
 245 then @code{@var{a} << @var{b}} has undefined behavior and
 246 @code{@var{a} >> @var{b}} has implementation-defined behavior, but
 247 this macro does not check these other restrictions.
 248 @end table
 249
 250 @node Integer Type Overflow
 251 @subsection Integer Type Overflow
 252
 253 @cindex integer type overflow
 254 @cindex overflow, integer type
 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 expand to integer constant expressions if their arguments are.  They
 261 are easier to use than the integer range overflow macros
 262 (@pxref{Integer Range Overflow}).
 263
 264 Example usage:
 265
 266 @example
 267 #include <intprops.h>
 268 void
 269 print_product (long int a, long int b)
 270 @{
 271   if (INT_MULTIPLY_OVERFLOW (a, b))
 272     printf ("multiply would overflow");
 273   else
 274     printf ("product is %ld", a * b);
 275 @}
 276 @end example
 277
 278 @noindent
 279 These macros have the following restrictions:
 280
 281 @itemize @bullet
 282 @item
 283 Their arguments must be integer expressions.
 284
 285 @item
 286 They may evaluate their arguments zero or multiple times, so the
 287 arguments should not have side effects.
 288 @end itemize
 289
 290 These macros are tuned for their last argument being a constant.
 291
 292 @table @code
 293 @item INT_ADD_OVERFLOW (@var{a}, @var{b})
 294 @findex INT_ADD_OVERFLOW
 295 Yield 1 if @code{@var{a} + @var{b}} would overflow.  See above for
 296 restrictions.
 297
 298 @item INT_SUBTRACT_OVERFLOW (@var{a}, @var{b})
 299 @findex INT_SUBTRACT_OVERFLOW
 300 Yield 1 if @code{@var{a} - @var{b}} would overflow.  See above for
 301 restrictions.
 302
 303 @item INT_NEGATE_OVERFLOW (@var{a})
 304 @findex INT_NEGATE_OVERFLOW
 305 Yields 1 if @code{-@var{a}} would overflow.  See above for restrictions.
 306
 307 @item INT_MULTIPLY_OVERFLOW (@var{a}, @var{b})
 308 @findex INT_MULTIPLY_OVERFLOW
 309 Yield 1 if @code{@var{a} * @var{b}} would overflow.  See above for
 310 restrictions.
 311
 312 @item INT_DIVIDE_OVERFLOW (@var{a}, @var{b})
 313 @findex INT_DIVIDE_OVERFLOW
 314 Yields 1 if @code{@var{a} / @var{b}} would overflow.  See above for
 315 restrictions.  Division overflow can happen on two's complement hosts
 316 when dividing the most negative integer by @minus{}1.  This macro does
 317 not check for division by zero.
 318
 319 @item INT_REMAINDER_OVERFLOW (@var{a}, @var{b})
 320 @findex INT_REMAINDER_OVERFLOW
 321 Yield 1 if @code{@var{a} % @var{b}} would overflow.  See above for
 322 restrictions.  Remainder overflow can happen on two's complement hosts
 323 when dividing the most negative integer by @minus{}1; although the
 324 mathematical result is always 0, in practice some implementations
 325 trap, so this counts as an overflow.  This macro does not check for
 326 division by zero.
 327
 328 @item INT_LEFT_SHIFT_OVERFLOW (@var{a}, @var{b})
 329 @findex INT_LEFT_SHIFT_OVERFLOW
 330 Yield 1 if @code{@var{a} << @var{b}} would overflow.  See above for
 331 restrictions.  The C standard says that behavior is undefined for
 332 shifts unless 0@leq{}@var{b}<@var{w} where @var{w} is @var{a}'s word
 333 width, and that when @var{a} is negative then @code{@var{a} <<
 334 @var{b}} has undefined behavior and @code{@var{a} >> @var{b}} has
 335 implementation-defined behavior, but this macro does not check these
 336 other restrictions.
 337 @end table