1290001Sglebius/* intprops.h -- properties of integer types 2290001Sglebius 3290001Sglebius Copyright (C) 2001-2005, 2009-2015 Free Software Foundation, Inc. 4290001Sglebius 5290001Sglebius This program is free software: you can redistribute it and/or modify 6290001Sglebius it under the terms of the GNU Lesser General Public License as published by 7290001Sglebius the Free Software Foundation; either version 2.1 of the License, or 8290001Sglebius (at your option) any later version. 9290001Sglebius 10290001Sglebius This program is distributed in the hope that it will be useful, 11290001Sglebius but WITHOUT ANY WARRANTY; without even the implied warranty of 12290001Sglebius MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13290001Sglebius GNU Lesser General Public License for more details. 14290001Sglebius 15290001Sglebius You should have received a copy of the GNU Lesser General Public License 16290001Sglebius along with this program. If not, see <http://www.gnu.org/licenses/>. */ 17290001Sglebius 18290001Sglebius/* Written by Paul Eggert. */ 19290001Sglebius 20290001Sglebius#ifndef _GL_INTPROPS_H 21290001Sglebius#define _GL_INTPROPS_H 22290001Sglebius 23290001Sglebius#include <limits.h> 24290001Sglebius 25290001Sglebius/* Return an integer value, converted to the same type as the integer 26290001Sglebius expression E after integer type promotion. V is the unconverted value. */ 27290001Sglebius#define _GL_INT_CONVERT(e, v) (0 * (e) + (v)) 28290001Sglebius 29290001Sglebius/* Act like _GL_INT_CONVERT (E, -V) but work around a bug in IRIX 6.5 cc; see 30290001Sglebius <http://lists.gnu.org/archive/html/bug-gnulib/2011-05/msg00406.html>. */ 31290001Sglebius#define _GL_INT_NEGATE_CONVERT(e, v) (0 * (e) - (v)) 32290001Sglebius 33290001Sglebius/* The extra casts in the following macros work around compiler bugs, 34290001Sglebius e.g., in Cray C 5.0.3.0. */ 35290001Sglebius 36290001Sglebius/* True if the arithmetic type T is an integer type. bool counts as 37290001Sglebius an integer. */ 38290001Sglebius#define TYPE_IS_INTEGER(t) ((t) 1.5 == 1) 39290001Sglebius 40290001Sglebius/* True if negative values of the signed integer type T use two's 41290001Sglebius complement, ones' complement, or signed magnitude representation, 42290001Sglebius respectively. Much GNU code assumes two's complement, but some 43290001Sglebius people like to be portable to all possible C hosts. */ 44290001Sglebius#define TYPE_TWOS_COMPLEMENT(t) ((t) ~ (t) 0 == (t) -1) 45290001Sglebius#define TYPE_ONES_COMPLEMENT(t) ((t) ~ (t) 0 == 0) 46290001Sglebius#define TYPE_SIGNED_MAGNITUDE(t) ((t) ~ (t) 0 < (t) -1) 47290001Sglebius 48290001Sglebius/* True if the signed integer expression E uses two's complement. */ 49290001Sglebius#define _GL_INT_TWOS_COMPLEMENT(e) (~ _GL_INT_CONVERT (e, 0) == -1) 50290001Sglebius 51290001Sglebius/* True if the arithmetic type T is signed. */ 52290001Sglebius#define TYPE_SIGNED(t) (! ((t) 0 < (t) -1)) 53290001Sglebius 54290001Sglebius/* Return 1 if the integer expression E, after integer promotion, has 55290001Sglebius a signed type. */ 56290001Sglebius#define _GL_INT_SIGNED(e) (_GL_INT_NEGATE_CONVERT (e, 1) < 0) 57290001Sglebius 58290001Sglebius 59290001Sglebius/* Minimum and maximum values for integer types and expressions. These 60290001Sglebius macros have undefined behavior if T is signed and has padding bits. 61290001Sglebius If this is a problem for you, please let us know how to fix it for 62290001Sglebius your host. */ 63290001Sglebius 64290001Sglebius/* The maximum and minimum values for the integer type T. */ 65290001Sglebius#define TYPE_MINIMUM(t) \ 66290001Sglebius ((t) (! TYPE_SIGNED (t) \ 67290001Sglebius ? (t) 0 \ 68290001Sglebius : TYPE_SIGNED_MAGNITUDE (t) \ 69290001Sglebius ? ~ (t) 0 \ 70290001Sglebius : ~ TYPE_MAXIMUM (t))) 71290001Sglebius#define TYPE_MAXIMUM(t) \ 72290001Sglebius ((t) (! TYPE_SIGNED (t) \ 73290001Sglebius ? (t) -1 \ 74290001Sglebius : ((((t) 1 << (sizeof (t) * CHAR_BIT - 2)) - 1) * 2 + 1))) 75290001Sglebius 76290001Sglebius/* The maximum and minimum values for the type of the expression E, 77290001Sglebius after integer promotion. E should not have side effects. */ 78290001Sglebius#define _GL_INT_MINIMUM(e) \ 79290001Sglebius (_GL_INT_SIGNED (e) \ 80290001Sglebius ? - _GL_INT_TWOS_COMPLEMENT (e) - _GL_SIGNED_INT_MAXIMUM (e) \ 81290001Sglebius : _GL_INT_CONVERT (e, 0)) 82290001Sglebius#define _GL_INT_MAXIMUM(e) \ 83290001Sglebius (_GL_INT_SIGNED (e) \ 84290001Sglebius ? _GL_SIGNED_INT_MAXIMUM (e) \ 85290001Sglebius : _GL_INT_NEGATE_CONVERT (e, 1)) 86290001Sglebius#define _GL_SIGNED_INT_MAXIMUM(e) \ 87290001Sglebius (((_GL_INT_CONVERT (e, 1) << (sizeof ((e) + 0) * CHAR_BIT - 2)) - 1) * 2 + 1) 88290001Sglebius 89290001Sglebius 90290001Sglebius/* Return 1 if the __typeof__ keyword works. This could be done by 91290001Sglebius 'configure', but for now it's easier to do it by hand. */ 92290001Sglebius#if (2 <= __GNUC__ || defined __IBM__TYPEOF__ \ 93290001Sglebius || (0x5110 <= __SUNPRO_C && !__STDC__)) 94290001Sglebius# define _GL_HAVE___TYPEOF__ 1 95290001Sglebius#else 96290001Sglebius# define _GL_HAVE___TYPEOF__ 0 97290001Sglebius#endif 98290001Sglebius 99290001Sglebius/* Return 1 if the integer type or expression T might be signed. Return 0 100290001Sglebius if it is definitely unsigned. This macro does not evaluate its argument, 101290001Sglebius and expands to an integer constant expression. */ 102290001Sglebius#if _GL_HAVE___TYPEOF__ 103290001Sglebius# define _GL_SIGNED_TYPE_OR_EXPR(t) TYPE_SIGNED (__typeof__ (t)) 104290001Sglebius#else 105290001Sglebius# define _GL_SIGNED_TYPE_OR_EXPR(t) 1 106290001Sglebius#endif 107290001Sglebius 108290001Sglebius/* Bound on length of the string representing an unsigned integer 109290001Sglebius value representable in B bits. log10 (2.0) < 146/485. The 110290001Sglebius smallest value of B where this bound is not tight is 2621. */ 111290001Sglebius#define INT_BITS_STRLEN_BOUND(b) (((b) * 146 + 484) / 485) 112290001Sglebius 113290001Sglebius/* Bound on length of the string representing an integer type or expression T. 114290001Sglebius Subtract 1 for the sign bit if T is signed, and then add 1 more for 115290001Sglebius a minus sign if needed. 116290001Sglebius 117290001Sglebius Because _GL_SIGNED_TYPE_OR_EXPR sometimes returns 0 when its argument is 118290001Sglebius signed, this macro may overestimate the true bound by one byte when 119290001Sglebius applied to unsigned types of size 2, 4, 16, ... bytes. */ 120290001Sglebius#define INT_STRLEN_BOUND(t) \ 121290001Sglebius (INT_BITS_STRLEN_BOUND (sizeof (t) * CHAR_BIT \ 122290001Sglebius - _GL_SIGNED_TYPE_OR_EXPR (t)) \ 123290001Sglebius + _GL_SIGNED_TYPE_OR_EXPR (t)) 124290001Sglebius 125290001Sglebius/* Bound on buffer size needed to represent an integer type or expression T, 126290001Sglebius including the terminating null. */ 127290001Sglebius#define INT_BUFSIZE_BOUND(t) (INT_STRLEN_BOUND (t) + 1) 128290001Sglebius 129290001Sglebius 130290001Sglebius/* Range overflow checks. 131290001Sglebius 132290001Sglebius The INT_<op>_RANGE_OVERFLOW macros return 1 if the corresponding C 133290001Sglebius operators might not yield numerically correct answers due to 134290001Sglebius arithmetic overflow. They do not rely on undefined or 135290001Sglebius implementation-defined behavior. Their implementations are simple 136290001Sglebius and straightforward, but they are a bit harder to use than the 137290001Sglebius INT_<op>_OVERFLOW macros described below. 138290001Sglebius 139290001Sglebius Example usage: 140290001Sglebius 141290001Sglebius long int i = ...; 142290001Sglebius long int j = ...; 143290001Sglebius if (INT_MULTIPLY_RANGE_OVERFLOW (i, j, LONG_MIN, LONG_MAX)) 144290001Sglebius printf ("multiply would overflow"); 145290001Sglebius else 146290001Sglebius printf ("product is %ld", i * j); 147290001Sglebius 148290001Sglebius Restrictions on *_RANGE_OVERFLOW macros: 149290001Sglebius 150290001Sglebius These macros do not check for all possible numerical problems or 151290001Sglebius undefined or unspecified behavior: they do not check for division 152290001Sglebius by zero, for bad shift counts, or for shifting negative numbers. 153290001Sglebius 154290001Sglebius These macros may evaluate their arguments zero or multiple times, 155290001Sglebius so the arguments should not have side effects. The arithmetic 156290001Sglebius arguments (including the MIN and MAX arguments) must be of the same 157290001Sglebius integer type after the usual arithmetic conversions, and the type 158290001Sglebius must have minimum value MIN and maximum MAX. Unsigned types should 159290001Sglebius use a zero MIN of the proper type. 160290001Sglebius 161290001Sglebius These macros are tuned for constant MIN and MAX. For commutative 162290001Sglebius operations such as A + B, they are also tuned for constant B. */ 163290001Sglebius 164290001Sglebius/* Return 1 if A + B would overflow in [MIN,MAX] arithmetic. 165290001Sglebius See above for restrictions. */ 166290001Sglebius#define INT_ADD_RANGE_OVERFLOW(a, b, min, max) \ 167290001Sglebius ((b) < 0 \ 168290001Sglebius ? (a) < (min) - (b) \ 169290001Sglebius : (max) - (b) < (a)) 170290001Sglebius 171290001Sglebius/* Return 1 if A - B would overflow in [MIN,MAX] arithmetic. 172290001Sglebius See above for restrictions. */ 173290001Sglebius#define INT_SUBTRACT_RANGE_OVERFLOW(a, b, min, max) \ 174290001Sglebius ((b) < 0 \ 175290001Sglebius ? (max) + (b) < (a) \ 176290001Sglebius : (a) < (min) + (b)) 177290001Sglebius 178290001Sglebius/* Return 1 if - A would overflow in [MIN,MAX] arithmetic. 179290001Sglebius See above for restrictions. */ 180290001Sglebius#define INT_NEGATE_RANGE_OVERFLOW(a, min, max) \ 181290001Sglebius ((min) < 0 \ 182290001Sglebius ? (a) < - (max) \ 183290001Sglebius : 0 < (a)) 184290001Sglebius 185290001Sglebius/* Return 1 if A * B would overflow in [MIN,MAX] arithmetic. 186290001Sglebius See above for restrictions. Avoid && and || as they tickle 187290001Sglebius bugs in Sun C 5.11 2010/08/13 and other compilers; see 188290001Sglebius <http://lists.gnu.org/archive/html/bug-gnulib/2011-05/msg00401.html>. */ 189290001Sglebius#define INT_MULTIPLY_RANGE_OVERFLOW(a, b, min, max) \ 190290001Sglebius ((b) < 0 \ 191290001Sglebius ? ((a) < 0 \ 192290001Sglebius ? (a) < (max) / (b) \ 193290001Sglebius : (b) == -1 \ 194290001Sglebius ? 0 \ 195290001Sglebius : (min) / (b) < (a)) \ 196290001Sglebius : (b) == 0 \ 197290001Sglebius ? 0 \ 198290001Sglebius : ((a) < 0 \ 199290001Sglebius ? (a) < (min) / (b) \ 200290001Sglebius : (max) / (b) < (a))) 201290001Sglebius 202290001Sglebius/* Return 1 if A / B would overflow in [MIN,MAX] arithmetic. 203290001Sglebius See above for restrictions. Do not check for division by zero. */ 204290001Sglebius#define INT_DIVIDE_RANGE_OVERFLOW(a, b, min, max) \ 205290001Sglebius ((min) < 0 && (b) == -1 && (a) < - (max)) 206290001Sglebius 207290001Sglebius/* Return 1 if A % B would overflow in [MIN,MAX] arithmetic. 208290001Sglebius See above for restrictions. Do not check for division by zero. 209290001Sglebius Mathematically, % should never overflow, but on x86-like hosts 210290001Sglebius INT_MIN % -1 traps, and the C standard permits this, so treat this 211290001Sglebius as an overflow too. */ 212290001Sglebius#define INT_REMAINDER_RANGE_OVERFLOW(a, b, min, max) \ 213290001Sglebius INT_DIVIDE_RANGE_OVERFLOW (a, b, min, max) 214290001Sglebius 215290001Sglebius/* Return 1 if A << B would overflow in [MIN,MAX] arithmetic. 216290001Sglebius See above for restrictions. Here, MIN and MAX are for A only, and B need 217290001Sglebius not be of the same type as the other arguments. The C standard says that 218290001Sglebius behavior is undefined for shifts unless 0 <= B < wordwidth, and that when 219290001Sglebius A is negative then A << B has undefined behavior and A >> B has 220290001Sglebius implementation-defined behavior, but do not check these other 221290001Sglebius restrictions. */ 222290001Sglebius#define INT_LEFT_SHIFT_RANGE_OVERFLOW(a, b, min, max) \ 223290001Sglebius ((a) < 0 \ 224290001Sglebius ? (a) < (min) >> (b) \ 225290001Sglebius : (max) >> (b) < (a)) 226290001Sglebius 227290001Sglebius 228290001Sglebius/* The _GL*_OVERFLOW macros have the same restrictions as the 229290001Sglebius *_RANGE_OVERFLOW macros, except that they do not assume that operands 230290001Sglebius (e.g., A and B) have the same type as MIN and MAX. Instead, they assume 231290001Sglebius that the result (e.g., A + B) has that type. */ 232290001Sglebius#define _GL_ADD_OVERFLOW(a, b, min, max) \ 233290001Sglebius ((min) < 0 ? INT_ADD_RANGE_OVERFLOW (a, b, min, max) \ 234290001Sglebius : (a) < 0 ? (b) <= (a) + (b) \ 235290001Sglebius : (b) < 0 ? (a) <= (a) + (b) \ 236290001Sglebius : (a) + (b) < (b)) 237290001Sglebius#define _GL_SUBTRACT_OVERFLOW(a, b, min, max) \ 238290001Sglebius ((min) < 0 ? INT_SUBTRACT_RANGE_OVERFLOW (a, b, min, max) \ 239290001Sglebius : (a) < 0 ? 1 \ 240290001Sglebius : (b) < 0 ? (a) - (b) <= (a) \ 241290001Sglebius : (a) < (b)) 242290001Sglebius#define _GL_MULTIPLY_OVERFLOW(a, b, min, max) \ 243290001Sglebius (((min) == 0 && (((a) < 0 && 0 < (b)) || ((b) < 0 && 0 < (a)))) \ 244290001Sglebius || INT_MULTIPLY_RANGE_OVERFLOW (a, b, min, max)) 245290001Sglebius#define _GL_DIVIDE_OVERFLOW(a, b, min, max) \ 246290001Sglebius ((min) < 0 ? (b) == _GL_INT_NEGATE_CONVERT (min, 1) && (a) < - (max) \ 247290001Sglebius : (a) < 0 ? (b) <= (a) + (b) - 1 \ 248290001Sglebius : (b) < 0 && (a) + (b) <= (a)) 249290001Sglebius#define _GL_REMAINDER_OVERFLOW(a, b, min, max) \ 250290001Sglebius ((min) < 0 ? (b) == _GL_INT_NEGATE_CONVERT (min, 1) && (a) < - (max) \ 251290001Sglebius : (a) < 0 ? (a) % (b) != ((max) - (b) + 1) % (b) \ 252290001Sglebius : (b) < 0 && ! _GL_UNSIGNED_NEG_MULTIPLE (a, b, max)) 253290001Sglebius 254290001Sglebius/* Return a nonzero value if A is a mathematical multiple of B, where 255290001Sglebius A is unsigned, B is negative, and MAX is the maximum value of A's 256290001Sglebius type. A's type must be the same as (A % B)'s type. Normally (A % 257290001Sglebius -B == 0) suffices, but things get tricky if -B would overflow. */ 258290001Sglebius#define _GL_UNSIGNED_NEG_MULTIPLE(a, b, max) \ 259290001Sglebius (((b) < -_GL_SIGNED_INT_MAXIMUM (b) \ 260290001Sglebius ? (_GL_SIGNED_INT_MAXIMUM (b) == (max) \ 261290001Sglebius ? (a) \ 262290001Sglebius : (a) % (_GL_INT_CONVERT (a, _GL_SIGNED_INT_MAXIMUM (b)) + 1)) \ 263290001Sglebius : (a) % - (b)) \ 264290001Sglebius == 0) 265290001Sglebius 266290001Sglebius 267290001Sglebius/* Integer overflow checks. 268290001Sglebius 269290001Sglebius The INT_<op>_OVERFLOW macros return 1 if the corresponding C operators 270290001Sglebius might not yield numerically correct answers due to arithmetic overflow. 271290001Sglebius They work correctly on all known practical hosts, and do not rely 272290001Sglebius on undefined behavior due to signed arithmetic overflow. 273290001Sglebius 274290001Sglebius Example usage: 275290001Sglebius 276290001Sglebius long int i = ...; 277290001Sglebius long int j = ...; 278290001Sglebius if (INT_MULTIPLY_OVERFLOW (i, j)) 279290001Sglebius printf ("multiply would overflow"); 280290001Sglebius else 281290001Sglebius printf ("product is %ld", i * j); 282290001Sglebius 283290001Sglebius These macros do not check for all possible numerical problems or 284290001Sglebius undefined or unspecified behavior: they do not check for division 285290001Sglebius by zero, for bad shift counts, or for shifting negative numbers. 286290001Sglebius 287290001Sglebius These macros may evaluate their arguments zero or multiple times, so the 288290001Sglebius arguments should not have side effects. 289290001Sglebius 290290001Sglebius These macros are tuned for their last argument being a constant. 291290001Sglebius 292290001Sglebius Return 1 if the integer expressions A * B, A - B, -A, A * B, A / B, 293290001Sglebius A % B, and A << B would overflow, respectively. */ 294290001Sglebius 295290001Sglebius#define INT_ADD_OVERFLOW(a, b) \ 296290001Sglebius _GL_BINARY_OP_OVERFLOW (a, b, _GL_ADD_OVERFLOW) 297290001Sglebius#define INT_SUBTRACT_OVERFLOW(a, b) \ 298290001Sglebius _GL_BINARY_OP_OVERFLOW (a, b, _GL_SUBTRACT_OVERFLOW) 299290001Sglebius#define INT_NEGATE_OVERFLOW(a) \ 300290001Sglebius INT_NEGATE_RANGE_OVERFLOW (a, _GL_INT_MINIMUM (a), _GL_INT_MAXIMUM (a)) 301290001Sglebius#define INT_MULTIPLY_OVERFLOW(a, b) \ 302290001Sglebius _GL_BINARY_OP_OVERFLOW (a, b, _GL_MULTIPLY_OVERFLOW) 303290001Sglebius#define INT_DIVIDE_OVERFLOW(a, b) \ 304290001Sglebius _GL_BINARY_OP_OVERFLOW (a, b, _GL_DIVIDE_OVERFLOW) 305290001Sglebius#define INT_REMAINDER_OVERFLOW(a, b) \ 306290001Sglebius _GL_BINARY_OP_OVERFLOW (a, b, _GL_REMAINDER_OVERFLOW) 307290001Sglebius#define INT_LEFT_SHIFT_OVERFLOW(a, b) \ 308290001Sglebius INT_LEFT_SHIFT_RANGE_OVERFLOW (a, b, \ 309290001Sglebius _GL_INT_MINIMUM (a), _GL_INT_MAXIMUM (a)) 310290001Sglebius 311290001Sglebius/* Return 1 if the expression A <op> B would overflow, 312290001Sglebius where OP_RESULT_OVERFLOW (A, B, MIN, MAX) does the actual test, 313290001Sglebius assuming MIN and MAX are the minimum and maximum for the result type. 314290001Sglebius Arguments should be free of side effects. */ 315290001Sglebius#define _GL_BINARY_OP_OVERFLOW(a, b, op_result_overflow) \ 316290001Sglebius op_result_overflow (a, b, \ 317290001Sglebius _GL_INT_MINIMUM (0 * (b) + (a)), \ 318290001Sglebius _GL_INT_MAXIMUM (0 * (b) + (a))) 319290001Sglebius 320290001Sglebius#endif /* _GL_INTPROPS_H */ 321