1275970Scy/* intprops.h -- properties of integer types 2275970Scy 3290000Sglebius Copyright (C) 2001-2005, 2009-2015 Free Software Foundation, Inc. 4275970Scy 5275970Scy This program is free software: you can redistribute it and/or modify 6275970Scy it under the terms of the GNU Lesser General Public License as published by 7275970Scy the Free Software Foundation; either version 2.1 of the License, or 8275970Scy (at your option) any later version. 9275970Scy 10275970Scy This program is distributed in the hope that it will be useful, 11275970Scy but WITHOUT ANY WARRANTY; without even the implied warranty of 12275970Scy MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13275970Scy GNU Lesser General Public License for more details. 14275970Scy 15275970Scy You should have received a copy of the GNU Lesser General Public License 16275970Scy along with this program. If not, see <http://www.gnu.org/licenses/>. */ 17275970Scy 18275970Scy/* Written by Paul Eggert. */ 19275970Scy 20275970Scy#ifndef _GL_INTPROPS_H 21275970Scy#define _GL_INTPROPS_H 22275970Scy 23275970Scy#include <limits.h> 24275970Scy 25275970Scy/* Return an integer value, converted to the same type as the integer 26275970Scy expression E after integer type promotion. V is the unconverted value. */ 27275970Scy#define _GL_INT_CONVERT(e, v) (0 * (e) + (v)) 28275970Scy 29275970Scy/* Act like _GL_INT_CONVERT (E, -V) but work around a bug in IRIX 6.5 cc; see 30275970Scy <http://lists.gnu.org/archive/html/bug-gnulib/2011-05/msg00406.html>. */ 31275970Scy#define _GL_INT_NEGATE_CONVERT(e, v) (0 * (e) - (v)) 32275970Scy 33275970Scy/* The extra casts in the following macros work around compiler bugs, 34275970Scy e.g., in Cray C 5.0.3.0. */ 35275970Scy 36275970Scy/* True if the arithmetic type T is an integer type. bool counts as 37275970Scy an integer. */ 38275970Scy#define TYPE_IS_INTEGER(t) ((t) 1.5 == 1) 39275970Scy 40275970Scy/* True if negative values of the signed integer type T use two's 41275970Scy complement, ones' complement, or signed magnitude representation, 42275970Scy respectively. Much GNU code assumes two's complement, but some 43275970Scy people like to be portable to all possible C hosts. */ 44275970Scy#define TYPE_TWOS_COMPLEMENT(t) ((t) ~ (t) 0 == (t) -1) 45275970Scy#define TYPE_ONES_COMPLEMENT(t) ((t) ~ (t) 0 == 0) 46275970Scy#define TYPE_SIGNED_MAGNITUDE(t) ((t) ~ (t) 0 < (t) -1) 47275970Scy 48275970Scy/* True if the signed integer expression E uses two's complement. */ 49275970Scy#define _GL_INT_TWOS_COMPLEMENT(e) (~ _GL_INT_CONVERT (e, 0) == -1) 50275970Scy 51275970Scy/* True if the arithmetic type T is signed. */ 52275970Scy#define TYPE_SIGNED(t) (! ((t) 0 < (t) -1)) 53275970Scy 54275970Scy/* Return 1 if the integer expression E, after integer promotion, has 55275970Scy a signed type. */ 56275970Scy#define _GL_INT_SIGNED(e) (_GL_INT_NEGATE_CONVERT (e, 1) < 0) 57275970Scy 58275970Scy 59275970Scy/* Minimum and maximum values for integer types and expressions. These 60275970Scy macros have undefined behavior if T is signed and has padding bits. 61275970Scy If this is a problem for you, please let us know how to fix it for 62275970Scy your host. */ 63275970Scy 64275970Scy/* The maximum and minimum values for the integer type T. */ 65275970Scy#define TYPE_MINIMUM(t) \ 66275970Scy ((t) (! TYPE_SIGNED (t) \ 67275970Scy ? (t) 0 \ 68275970Scy : TYPE_SIGNED_MAGNITUDE (t) \ 69275970Scy ? ~ (t) 0 \ 70275970Scy : ~ TYPE_MAXIMUM (t))) 71275970Scy#define TYPE_MAXIMUM(t) \ 72275970Scy ((t) (! TYPE_SIGNED (t) \ 73275970Scy ? (t) -1 \ 74275970Scy : ((((t) 1 << (sizeof (t) * CHAR_BIT - 2)) - 1) * 2 + 1))) 75275970Scy 76275970Scy/* The maximum and minimum values for the type of the expression E, 77275970Scy after integer promotion. E should not have side effects. */ 78275970Scy#define _GL_INT_MINIMUM(e) \ 79275970Scy (_GL_INT_SIGNED (e) \ 80275970Scy ? - _GL_INT_TWOS_COMPLEMENT (e) - _GL_SIGNED_INT_MAXIMUM (e) \ 81275970Scy : _GL_INT_CONVERT (e, 0)) 82275970Scy#define _GL_INT_MAXIMUM(e) \ 83275970Scy (_GL_INT_SIGNED (e) \ 84275970Scy ? _GL_SIGNED_INT_MAXIMUM (e) \ 85275970Scy : _GL_INT_NEGATE_CONVERT (e, 1)) 86275970Scy#define _GL_SIGNED_INT_MAXIMUM(e) \ 87275970Scy (((_GL_INT_CONVERT (e, 1) << (sizeof ((e) + 0) * CHAR_BIT - 2)) - 1) * 2 + 1) 88275970Scy 89275970Scy 90275970Scy/* Return 1 if the __typeof__ keyword works. This could be done by 91275970Scy 'configure', but for now it's easier to do it by hand. */ 92275970Scy#if (2 <= __GNUC__ || defined __IBM__TYPEOF__ \ 93275970Scy || (0x5110 <= __SUNPRO_C && !__STDC__)) 94275970Scy# define _GL_HAVE___TYPEOF__ 1 95275970Scy#else 96275970Scy# define _GL_HAVE___TYPEOF__ 0 97275970Scy#endif 98275970Scy 99275970Scy/* Return 1 if the integer type or expression T might be signed. Return 0 100275970Scy if it is definitely unsigned. This macro does not evaluate its argument, 101275970Scy and expands to an integer constant expression. */ 102275970Scy#if _GL_HAVE___TYPEOF__ 103275970Scy# define _GL_SIGNED_TYPE_OR_EXPR(t) TYPE_SIGNED (__typeof__ (t)) 104275970Scy#else 105275970Scy# define _GL_SIGNED_TYPE_OR_EXPR(t) 1 106275970Scy#endif 107275970Scy 108275970Scy/* Bound on length of the string representing an unsigned integer 109275970Scy value representable in B bits. log10 (2.0) < 146/485. The 110275970Scy smallest value of B where this bound is not tight is 2621. */ 111275970Scy#define INT_BITS_STRLEN_BOUND(b) (((b) * 146 + 484) / 485) 112275970Scy 113275970Scy/* Bound on length of the string representing an integer type or expression T. 114275970Scy Subtract 1 for the sign bit if T is signed, and then add 1 more for 115275970Scy a minus sign if needed. 116275970Scy 117275970Scy Because _GL_SIGNED_TYPE_OR_EXPR sometimes returns 0 when its argument is 118275970Scy signed, this macro may overestimate the true bound by one byte when 119275970Scy applied to unsigned types of size 2, 4, 16, ... bytes. */ 120275970Scy#define INT_STRLEN_BOUND(t) \ 121275970Scy (INT_BITS_STRLEN_BOUND (sizeof (t) * CHAR_BIT \ 122275970Scy - _GL_SIGNED_TYPE_OR_EXPR (t)) \ 123275970Scy + _GL_SIGNED_TYPE_OR_EXPR (t)) 124275970Scy 125275970Scy/* Bound on buffer size needed to represent an integer type or expression T, 126275970Scy including the terminating null. */ 127275970Scy#define INT_BUFSIZE_BOUND(t) (INT_STRLEN_BOUND (t) + 1) 128275970Scy 129275970Scy 130275970Scy/* Range overflow checks. 131275970Scy 132275970Scy The INT_<op>_RANGE_OVERFLOW macros return 1 if the corresponding C 133275970Scy operators might not yield numerically correct answers due to 134275970Scy arithmetic overflow. They do not rely on undefined or 135275970Scy implementation-defined behavior. Their implementations are simple 136275970Scy and straightforward, but they are a bit harder to use than the 137275970Scy INT_<op>_OVERFLOW macros described below. 138275970Scy 139275970Scy Example usage: 140275970Scy 141275970Scy long int i = ...; 142275970Scy long int j = ...; 143275970Scy if (INT_MULTIPLY_RANGE_OVERFLOW (i, j, LONG_MIN, LONG_MAX)) 144275970Scy printf ("multiply would overflow"); 145275970Scy else 146275970Scy printf ("product is %ld", i * j); 147275970Scy 148275970Scy Restrictions on *_RANGE_OVERFLOW macros: 149275970Scy 150275970Scy These macros do not check for all possible numerical problems or 151275970Scy undefined or unspecified behavior: they do not check for division 152275970Scy by zero, for bad shift counts, or for shifting negative numbers. 153275970Scy 154275970Scy These macros may evaluate their arguments zero or multiple times, 155275970Scy so the arguments should not have side effects. The arithmetic 156275970Scy arguments (including the MIN and MAX arguments) must be of the same 157275970Scy integer type after the usual arithmetic conversions, and the type 158275970Scy must have minimum value MIN and maximum MAX. Unsigned types should 159275970Scy use a zero MIN of the proper type. 160275970Scy 161275970Scy These macros are tuned for constant MIN and MAX. For commutative 162275970Scy operations such as A + B, they are also tuned for constant B. */ 163275970Scy 164275970Scy/* Return 1 if A + B would overflow in [MIN,MAX] arithmetic. 165275970Scy See above for restrictions. */ 166275970Scy#define INT_ADD_RANGE_OVERFLOW(a, b, min, max) \ 167275970Scy ((b) < 0 \ 168275970Scy ? (a) < (min) - (b) \ 169275970Scy : (max) - (b) < (a)) 170275970Scy 171275970Scy/* Return 1 if A - B would overflow in [MIN,MAX] arithmetic. 172275970Scy See above for restrictions. */ 173275970Scy#define INT_SUBTRACT_RANGE_OVERFLOW(a, b, min, max) \ 174275970Scy ((b) < 0 \ 175275970Scy ? (max) + (b) < (a) \ 176275970Scy : (a) < (min) + (b)) 177275970Scy 178275970Scy/* Return 1 if - A would overflow in [MIN,MAX] arithmetic. 179275970Scy See above for restrictions. */ 180275970Scy#define INT_NEGATE_RANGE_OVERFLOW(a, min, max) \ 181275970Scy ((min) < 0 \ 182275970Scy ? (a) < - (max) \ 183275970Scy : 0 < (a)) 184275970Scy 185275970Scy/* Return 1 if A * B would overflow in [MIN,MAX] arithmetic. 186275970Scy See above for restrictions. Avoid && and || as they tickle 187275970Scy bugs in Sun C 5.11 2010/08/13 and other compilers; see 188275970Scy <http://lists.gnu.org/archive/html/bug-gnulib/2011-05/msg00401.html>. */ 189275970Scy#define INT_MULTIPLY_RANGE_OVERFLOW(a, b, min, max) \ 190275970Scy ((b) < 0 \ 191275970Scy ? ((a) < 0 \ 192275970Scy ? (a) < (max) / (b) \ 193275970Scy : (b) == -1 \ 194275970Scy ? 0 \ 195275970Scy : (min) / (b) < (a)) \ 196275970Scy : (b) == 0 \ 197275970Scy ? 0 \ 198275970Scy : ((a) < 0 \ 199275970Scy ? (a) < (min) / (b) \ 200275970Scy : (max) / (b) < (a))) 201275970Scy 202275970Scy/* Return 1 if A / B would overflow in [MIN,MAX] arithmetic. 203275970Scy See above for restrictions. Do not check for division by zero. */ 204275970Scy#define INT_DIVIDE_RANGE_OVERFLOW(a, b, min, max) \ 205275970Scy ((min) < 0 && (b) == -1 && (a) < - (max)) 206275970Scy 207275970Scy/* Return 1 if A % B would overflow in [MIN,MAX] arithmetic. 208275970Scy See above for restrictions. Do not check for division by zero. 209275970Scy Mathematically, % should never overflow, but on x86-like hosts 210275970Scy INT_MIN % -1 traps, and the C standard permits this, so treat this 211275970Scy as an overflow too. */ 212275970Scy#define INT_REMAINDER_RANGE_OVERFLOW(a, b, min, max) \ 213275970Scy INT_DIVIDE_RANGE_OVERFLOW (a, b, min, max) 214275970Scy 215275970Scy/* Return 1 if A << B would overflow in [MIN,MAX] arithmetic. 216275970Scy See above for restrictions. Here, MIN and MAX are for A only, and B need 217275970Scy not be of the same type as the other arguments. The C standard says that 218275970Scy behavior is undefined for shifts unless 0 <= B < wordwidth, and that when 219275970Scy A is negative then A << B has undefined behavior and A >> B has 220275970Scy implementation-defined behavior, but do not check these other 221275970Scy restrictions. */ 222275970Scy#define INT_LEFT_SHIFT_RANGE_OVERFLOW(a, b, min, max) \ 223275970Scy ((a) < 0 \ 224275970Scy ? (a) < (min) >> (b) \ 225275970Scy : (max) >> (b) < (a)) 226275970Scy 227275970Scy 228275970Scy/* The _GL*_OVERFLOW macros have the same restrictions as the 229275970Scy *_RANGE_OVERFLOW macros, except that they do not assume that operands 230275970Scy (e.g., A and B) have the same type as MIN and MAX. Instead, they assume 231275970Scy that the result (e.g., A + B) has that type. */ 232275970Scy#define _GL_ADD_OVERFLOW(a, b, min, max) \ 233275970Scy ((min) < 0 ? INT_ADD_RANGE_OVERFLOW (a, b, min, max) \ 234275970Scy : (a) < 0 ? (b) <= (a) + (b) \ 235275970Scy : (b) < 0 ? (a) <= (a) + (b) \ 236275970Scy : (a) + (b) < (b)) 237275970Scy#define _GL_SUBTRACT_OVERFLOW(a, b, min, max) \ 238275970Scy ((min) < 0 ? INT_SUBTRACT_RANGE_OVERFLOW (a, b, min, max) \ 239275970Scy : (a) < 0 ? 1 \ 240275970Scy : (b) < 0 ? (a) - (b) <= (a) \ 241275970Scy : (a) < (b)) 242275970Scy#define _GL_MULTIPLY_OVERFLOW(a, b, min, max) \ 243275970Scy (((min) == 0 && (((a) < 0 && 0 < (b)) || ((b) < 0 && 0 < (a)))) \ 244275970Scy || INT_MULTIPLY_RANGE_OVERFLOW (a, b, min, max)) 245275970Scy#define _GL_DIVIDE_OVERFLOW(a, b, min, max) \ 246275970Scy ((min) < 0 ? (b) == _GL_INT_NEGATE_CONVERT (min, 1) && (a) < - (max) \ 247275970Scy : (a) < 0 ? (b) <= (a) + (b) - 1 \ 248275970Scy : (b) < 0 && (a) + (b) <= (a)) 249275970Scy#define _GL_REMAINDER_OVERFLOW(a, b, min, max) \ 250275970Scy ((min) < 0 ? (b) == _GL_INT_NEGATE_CONVERT (min, 1) && (a) < - (max) \ 251275970Scy : (a) < 0 ? (a) % (b) != ((max) - (b) + 1) % (b) \ 252275970Scy : (b) < 0 && ! _GL_UNSIGNED_NEG_MULTIPLE (a, b, max)) 253275970Scy 254275970Scy/* Return a nonzero value if A is a mathematical multiple of B, where 255275970Scy A is unsigned, B is negative, and MAX is the maximum value of A's 256275970Scy type. A's type must be the same as (A % B)'s type. Normally (A % 257275970Scy -B == 0) suffices, but things get tricky if -B would overflow. */ 258275970Scy#define _GL_UNSIGNED_NEG_MULTIPLE(a, b, max) \ 259275970Scy (((b) < -_GL_SIGNED_INT_MAXIMUM (b) \ 260275970Scy ? (_GL_SIGNED_INT_MAXIMUM (b) == (max) \ 261275970Scy ? (a) \ 262275970Scy : (a) % (_GL_INT_CONVERT (a, _GL_SIGNED_INT_MAXIMUM (b)) + 1)) \ 263275970Scy : (a) % - (b)) \ 264275970Scy == 0) 265275970Scy 266275970Scy 267275970Scy/* Integer overflow checks. 268275970Scy 269275970Scy The INT_<op>_OVERFLOW macros return 1 if the corresponding C operators 270275970Scy might not yield numerically correct answers due to arithmetic overflow. 271275970Scy They work correctly on all known practical hosts, and do not rely 272275970Scy on undefined behavior due to signed arithmetic overflow. 273275970Scy 274275970Scy Example usage: 275275970Scy 276275970Scy long int i = ...; 277275970Scy long int j = ...; 278275970Scy if (INT_MULTIPLY_OVERFLOW (i, j)) 279275970Scy printf ("multiply would overflow"); 280275970Scy else 281275970Scy printf ("product is %ld", i * j); 282275970Scy 283275970Scy These macros do not check for all possible numerical problems or 284275970Scy undefined or unspecified behavior: they do not check for division 285275970Scy by zero, for bad shift counts, or for shifting negative numbers. 286275970Scy 287275970Scy These macros may evaluate their arguments zero or multiple times, so the 288275970Scy arguments should not have side effects. 289275970Scy 290275970Scy These macros are tuned for their last argument being a constant. 291275970Scy 292275970Scy Return 1 if the integer expressions A * B, A - B, -A, A * B, A / B, 293275970Scy A % B, and A << B would overflow, respectively. */ 294275970Scy 295275970Scy#define INT_ADD_OVERFLOW(a, b) \ 296275970Scy _GL_BINARY_OP_OVERFLOW (a, b, _GL_ADD_OVERFLOW) 297275970Scy#define INT_SUBTRACT_OVERFLOW(a, b) \ 298275970Scy _GL_BINARY_OP_OVERFLOW (a, b, _GL_SUBTRACT_OVERFLOW) 299275970Scy#define INT_NEGATE_OVERFLOW(a) \ 300275970Scy INT_NEGATE_RANGE_OVERFLOW (a, _GL_INT_MINIMUM (a), _GL_INT_MAXIMUM (a)) 301275970Scy#define INT_MULTIPLY_OVERFLOW(a, b) \ 302275970Scy _GL_BINARY_OP_OVERFLOW (a, b, _GL_MULTIPLY_OVERFLOW) 303275970Scy#define INT_DIVIDE_OVERFLOW(a, b) \ 304275970Scy _GL_BINARY_OP_OVERFLOW (a, b, _GL_DIVIDE_OVERFLOW) 305275970Scy#define INT_REMAINDER_OVERFLOW(a, b) \ 306275970Scy _GL_BINARY_OP_OVERFLOW (a, b, _GL_REMAINDER_OVERFLOW) 307275970Scy#define INT_LEFT_SHIFT_OVERFLOW(a, b) \ 308275970Scy INT_LEFT_SHIFT_RANGE_OVERFLOW (a, b, \ 309275970Scy _GL_INT_MINIMUM (a), _GL_INT_MAXIMUM (a)) 310275970Scy 311275970Scy/* Return 1 if the expression A <op> B would overflow, 312275970Scy where OP_RESULT_OVERFLOW (A, B, MIN, MAX) does the actual test, 313275970Scy assuming MIN and MAX are the minimum and maximum for the result type. 314275970Scy Arguments should be free of side effects. */ 315275970Scy#define _GL_BINARY_OP_OVERFLOW(a, b, op_result_overflow) \ 316275970Scy op_result_overflow (a, b, \ 317275970Scy _GL_INT_MINIMUM (0 * (b) + (a)), \ 318275970Scy _GL_INT_MAXIMUM (0 * (b) + (a))) 319275970Scy 320275970Scy#endif /* _GL_INTPROPS_H */ 321