pintos-os.org Git - pspp/blob - doc/intprops.texi

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