From a2b658cdccd4a13a5cef87144447f96cd1079e8c Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Tue, 17 May 2011 13:09:08 -0700 Subject: [PATCH] intprops: add doc * doc/intprops.texi: New file, documenting intprops. * doc/gnulib.texi (Particular Modules): Include it. --- ChangeLog | 4 + doc/gnulib.texi | 3 + doc/intprops.texi | 336 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 343 insertions(+) create mode 100644 doc/intprops.texi diff --git a/ChangeLog b/ChangeLog index 73d186b3ce..982b868937 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,9 @@ 2011-05-17 Paul Eggert + intprops: add doc + * doc/intprops.texi: New file, documenting intprops. + * doc/gnulib.texi (Particular Modules): Include it. + verify: add doc to gnulib manual and fix example * doc/gnulib.texi (Compile-time Assertions): New node, for 'verify'. * doc/verify.texi (Compile-time Assertions): Update 'assert' doc. diff --git a/doc/gnulib.texi b/doc/gnulib.texi index d6e43d8ed8..fef0d76705 100644 --- a/doc/gnulib.texi +++ b/doc/gnulib.texi @@ -6497,6 +6497,7 @@ This list of functions is sorted according to the header that declares them. * alloca-opt:: * Safe Allocation Macros:: * Compile-time Assertions:: +* Integer Properties:: * String Functions in C Locale:: * Quoting:: * error and progname:: @@ -6527,6 +6528,8 @@ This list of functions is sorted according to the header that declares them. @include verify.texi +@include intprops.texi + @node String Functions in C Locale @section Character and String Functions in C Locale diff --git a/doc/intprops.texi b/doc/intprops.texi new file mode 100644 index 0000000000..b4a8c6a610 --- /dev/null +++ b/doc/intprops.texi @@ -0,0 +1,336 @@ +@node Integer Properties +@section Integer Properties + +@c Copyright (C) 011 Free Software Foundation, Inc. + +@c Permission is granted to copy, distribute and/or modify this document +@c under the terms of the GNU Free Documentation License, Version 1.3 or +@c any later version published by the Free Software Foundation; with no +@c Invariant Sections, with no Front-Cover Texts, and with no Back-Cover +@c Texts. A copy of the license is included in the ``GNU Free +@c Documentation License'' file as part of this distribution. + +@c Written by Paul Eggert. + +@cindex integer properties + +The @code{intprops} module consists of an include file @code{} +that defines several macros useful for testing properties of integer +types. + +@cindex integer overflow +@cindex overflow, integer + +Integer overflow is a common source of problems in programs written in +C and other languages. In some cases, such as signed integer +arithmetic in C programs, the resulting behavior is undefined, and +practical platforms do not always behave as if integers wrap around +reliably. In other cases, such as unsigned integer arithmetic in C, +the resulting behavior is well-defined, but programs may still +misbehave badly after overflow occurs. + +Many techniques have been proposed to attack these problems. These +include precondition testing, GCC's @option{-ftrapv} option, GCC's +no-undefined-overflow branch, the As-if Infinitely Ranged (AIR) model +implemented in Clang, saturation semantics where overflow reliably +yields an extreme value, the RICH static transformer to an +overflow-checking variant, and special testing methods. For more +information about these techniques, see: Dannenberg R, Dormann W, +Keaton D @emph{et al.}, +@url{http://www.sei.cmu.edu/library/abstracts/reports/10tn008.cfm, +As-if Infinitely Ranged integer model -- 2nd ed.}, Software Engineering +Institute Technical Note CMU/SEI-2010-TN-008, April 2010. + +Gnulib supports the precondition testing technique, as this is easy to +support portably. There are two families of precondition tests: the +first, for integer ranges, has a simple and straightforward implementation, +while the second, for integer types, is easier to use. + +@menu +* Integer Type Determination:: Whether a type has integer properties. +* Integer Bounds:: Bounds on integer values and representations. +* Integer Range Overflow:: Integer overflow checking if bounds are known. +* Integer Type Overflow:: General integer overflow checking. +@end menu + +@node Integer Type Determination +@subsection Integer Type Determination + +@findex TYPE_IS_INTEGER +@code{TYPE_IS_INTEGER (@var{t})} expands to an integer constant +expression that is 1 if the arithmetic type @var{t} is a integer type. +@code{_Bool} counts as an integer type. + +@findex TYPE_SIGNED +@code{TYPE_SIGNED (@var{t})} expands to an integer constant expression +that is 1 if the arithmetic type @var{t} is a signed integer type or a +floating type. + +Example usage: + +@example +#include +#include +enum +@{ + time_t_is_signed_integer = + TYPE_IS_INTEGER (time_t) && TYPE_SIGNED (time_t) +@}; +@end example + +@node Integer Bounds +@subsection Integer Bounds + +@cindex integer bounds + +@findex INT_BUFSIZE_BOUND +@code{INT_BUFSIZE_BOUND (@var{t})} expands to an integer constant +expression that is a bound on the size of the string representing an +integer type or expression @var{t} in decimal notation, including the +terminating null character and any leading @code{-} character. For +example, if @code{INT_STRLEN_BOUND (int)} is 12, any value of type +@code{int} can be represented in 12 bytes or less, including the +terminating null. The bound is not necessarily tight. + +Example usage: + +@example +#include +#include +int +int_strlen (int i) +@{ + char buf[INT_BUFSIZE_BOUND (int)]; + return sprintf (buf, "%d", i); +@} +@end example + +@findex INT_STRLEN_BOUND +@code{INT_STRLEN_BOUND (@var{t})} expands to an integer constant +expression that is a bound on the length of the string representing an +integer type or expression @var{t} in decimal notation, including any +leading @code{-} character. This is one less than +@code{INT_BUFSIZE_BOUND (@var{t})}. + +@findex TYPE_MINIMUM +@findex TYPE_MAXIMUM +@code{TYPE_MINIMUM (@var{t})} and @code{TYPE_MAXIMUM (@var{t})} expand +to integer constant expressions equal to the minimum and maximum +values of the integer type @var{t}. These expressions are of the type +@var{t} (or more precisely, the type @var{t} after integer +promotions). + +Example usage: + +@example +#include +#include +#include +int +in_off_t_range (intmax_t a) +@{ + return TYPE_MINIMUM (off_t) <= a && a <= TYPE_MAXIMUM (off_t); +@} +@end example + +@node Integer Range Overflow +@subsection Integer Range Overflow + +@cindex integer range overflow +@cindex overflow, integer range + +These macros yield 1 if the corresponding C operators might not yield +numerically correct answers due to arithmetic overflow. They do not +rely on undefined or implementation-defined behavior. They expand to +integer constant expresssions if their arguments are. Their +implementations are simple and straightforward, but they are typically +harder to use than the integer type overflow macros. @xref{Integer +Type Overflow}. + +Although the implementation of these macros is similar to that +suggested in Seacord R, The CERT C Secure Coding Standard (2009, +revised 2011), in its two sections +``@url{https://www.securecoding.cert.org/confluence/display/seccode/INT30-C.+Ensure+that+unsigned+integer+operations+do+not+wrap, +INT30-C. Ensure that unsigned integer operations do not wrap}'' and +``@url{https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow, +INT32-C. Ensure that operations on signed integers do not result in +overflow}'', Gnulib's implementation was derived independently of +CERT's suggestions. + +Example usage: + +@example +#include +void +print_product (long int a, long int b) +@{ + if (INT_MULTIPLY_RANGE_OVERFLOW (a, b, LONG_MIN, LONG_MAX)) + printf ("multiply would overflow"); + else + printf ("product is %ld", a * b); +@} +@end example + +@noindent +These macros have the following restrictions: + +@itemize @bullet +@item +Their arguments must be integer expressions. + +@item +They may evaluate their arguments zero or multiple times, so +the arguments should not have side effects. + +@item +The arithmetic arguments (including the @var{min} and @var{max} +arguments) must be of the same integer type after the usual arithmetic +conversions, and the type must have minimum value @var{min} and +maximum @var{max}. Unsigned values should use a zero @var{min} of the +proper type, for example, @code{(unsigned int) 0}. +@end itemize + +These macros are tuned for constant @var{min} and @var{max}. For +commutative operations such as @code{@var{a} + @var{b}}, they are also +tuned for constant @var{b}. + +@table @code +@item INT_ADD_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max}) +@findex INT_ADD_RANGE_OVERFLOW +Yield 1 if @code{@var{a} + @var{b}} would overflow in +[@var{min},@var{max}] integer arithmetic. See above for restrictions. + +@item INT_SUBTRACT_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max}) +@findex INT_SUBTRACT_RANGE_OVERFLOW +Yield 1 if @code{@var{a} - @var{b}} would overflow in +[@var{min},@var{max}] integer arithmetic. See above for restrictions. + +@item INT_NEGATE_RANGE_OVERFLOW (@var{a}, @var{min}, @var{max}) +@findex INT_NEGATE_RANGE_OVERFLOW +Yield 1 if @code{-@var{a}} would overflow in [@var{min},@var{max}] +integer arithmetic. See above for restrictions. + +@item INT_MULTIPLY_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max}) +@findex INT_MULTIPLY_RANGE_OVERFLOW +Yield 1 if @code{@var{a} * @var{b}} would overflow in +[@var{min},@var{max}] integer arithmetic. See above for restrictions. + +@item INT_DIVIDE_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max}) +@findex INT_DIVIDE_RANGE_OVERFLOW +Yield 1 if @code{@var{a} / @var{b}} would overflow in +[@var{min},@var{max}] integer arithmetic. See above for restrictions. +Division overflow can happen on two's complement hosts when dividing +the most negative integer by @minus{}1. This macro does not check for +division by zero. + +@item INT_REMAINDER_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max}) +@findex INT_REMAINDER_RANGE_OVERFLOW +Yield 1 if @code{@var{a} % @var{b}} would overflow in +[@var{min},@var{max}] integer arithmetic. See above for restrictions. +Remainder overflow can happen on two's complement hosts when dividing +the most negative integer by @minus{}1; although the mathematical +result is always 0, in practice some implementations trap, so this +counts as an overflow. This macro does not check for division by +zero. + +@item INT_LEFT_SHIFT_RANGE_OVERFLOW (@var{a}, @var{b}, @var{min}, @var{max}) +@findex INT_LEFT_SHIFT_RANGE_OVERFLOW +Yield 1 if @code{@var{a} << @var{b}} would overflow in +[@var{min},@var{max}] integer arithmetic. See above for restrictions. +Here, @var{min} and @var{max} are for @var{a} only, and @var{b} need +not be of the same type as the other arguments. The C standard says +that behavior is undefined for shifts unless 0@leq{}@var{b}<@var{w} +where @var{w} is @var{a}'s word width, and that when @var{a} is negative +then @code{@var{a} << @var{b}} has undefined behavior and +@code{@var{a} >> @var{b}} has implementation-defined behavior, but +this macro does not check these other restrictions. +@end table + +@node Integer Type Overflow +@subsection Integer Type Overflow + +@cindex integer type overflow +@cindex overflow, integer type + +These macros yield 1 if the corresponding C operators might not yield +numerically correct answers due to arithmetic overflow of an integer +type. They work correctly on all known practical hosts, and do not +rely on undefined behavior due to signed arithmetic overflow. They +expand to integer constant expresssions if their arguments are. They +are easier to use than the integer range overflow macros +(@pxref{Integer Range Overflow}). + +Example usage: + +@example +#include +void +print_product (long int a, long int b) +@{ + if (INT_MULTIPLY_OVERFLOW (a, b)) + printf ("multiply would overflow"); + else + printf ("product is %ld", a * b); +@} +@end example + +@noindent +These macros have the following restrictions: + +@itemize @bullet +@item +Their arguments must be integer expressions. + +@item +They may evaluate their arguments zero or multiple times, so the +arguments should not have side effects. +@end itemize + +These macros are tuned for their last argument being a constant. + +@table @code +@item INT_ADD_OVERFLOW (@var{a}, @var{b}) +@findex INT_ADD_OVERFLOW +Yield 1 if @code{@var{a} + @var{b}} would overflow. See above for +restrictions. + +@item INT_SUBTRACT_OVERFLOW (@var{a}, @var{b}) +@findex INT_SUBTRACT_OVERFLOW +Yield 1 if @code{@var{a} - @var{b}} would overflow. See above for +restrictions. + +@item INT_NEGATE_OVERFLOW (@var{a}) +@findex INT_NEGATE_OVERFLOW +Yields 1 if @code{-@var{a}} would overflow. See above for restrictions. + +@item INT_MULTIPLY_OVERFLOW (@var{a}, @var{b}) +@findex INT_MULTIPLY_OVERFLOW +Yield 1 if @code{@var{a} * @var{b}} would overflow. See above for +restrictions. + +@item INT_DIVIDE_OVERFLOW (@var{a}, @var{b}) +@findex INT_DIVIDE_OVERFLOW +Yields 1 if @code{@var{a} / @var{b}} would overflow. See above for +restrictions. Division overflow can happen on two's complement hosts +when dividing the most negative integer by @minus{}1. This macro does +not check for division by zero. + +@item INT_REMAINDER_OVERFLOW (@var{a}, @var{b}) +@findex INT_REMAINDER_OVERFLOW +Yield 1 if @code{@var{a} % @var{b}} would overflow. See above for +restrictions. Remainder overflow can happen on two's complement hosts +when dividing the most negative integer by @minus{}1; although the +mathematical result is always 0, in practice some implementations +trap, so this counts as an overflow. This macro does not check for +division by zero. + +@item INT_LEFT_SHIFT_OVERFLOW (@var{a}, @var{b}) +@findex INT_LEFT_SHIFT_OVERFLOW +Yield 1 if @code{@var{a} << @var{b}} would overflow. See above for +restrictions. The C standard says that behavior is undefined for +shifts unless 0@leq{}@var{b}<@var{w} where @var{w} is @var{a}'s word +width, and that when @var{a} is negative then @code{@var{a} << +@var{b}} has undefined behavior and @code{@var{a} >> @var{b}} has +implementation-defined behavior, but this macro does not check these +other restrictions. +@end table -- 2.30.2