integer.h 6.34 KB
Newer Older
1 2 3 4 5 6 7 8 9 10
/*
 * Copyright (C) the libgit2 contributors. All rights reserved.
 *
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
 */
#ifndef INCLUDE_integer_h__
#define INCLUDE_integer_h__

/** @return true if p fits into the range of a size_t */
11
GIT_INLINE(int) git__is_sizet(int64_t p)
12 13
{
	size_t r = (size_t)p;
14
	return p == (int64_t)r;
15 16 17 18 19 20 21 22 23
}

/** @return true if p fits into the range of an ssize_t */
GIT_INLINE(int) git__is_ssizet(size_t p)
{
	ssize_t r = (ssize_t)p;
	return p == (size_t)r;
}

24 25 26 27 28 29 30
/** @return true if p fits into the range of a uint16_t */
GIT_INLINE(int) git__is_uint16(size_t p)
{
	uint16_t r = (uint16_t)p;
	return p == (size_t)r;
}

31 32 33 34 35 36 37 38
/** @return true if p fits into the range of a uint32_t */
GIT_INLINE(int) git__is_uint32(size_t p)
{
	uint32_t r = (uint32_t)p;
	return p == (size_t)r;
}

/** @return true if p fits into the range of an unsigned long */
39
GIT_INLINE(int) git__is_ulong(int64_t p)
40 41
{
	unsigned long r = (unsigned long)p;
42
	return p == (int64_t)r;
43 44
}

45
/** @return true if p fits into the range of an int */
46
GIT_INLINE(int) git__is_int(int64_t p)
47 48
{
	int r = (int)p;
49
	return p == (int64_t)r;
50 51
}

52
/* Use clang/gcc compiler intrinsics whenever possible */
53 54 55
#if (__has_builtin(__builtin_add_overflow) || \
     (defined(__GNUC__) && (__GNUC__ >= 5)))

56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
# if (SIZE_MAX == UINT_MAX)
#  define git__add_sizet_overflow(out, one, two) \
     __builtin_uadd_overflow(one, two, out)
#  define git__multiply_sizet_overflow(out, one, two) \
     __builtin_umul_overflow(one, two, out)
# elif (SIZE_MAX == ULONG_MAX)
#  define git__add_sizet_overflow(out, one, two) \
     __builtin_uaddl_overflow(one, two, out)
#  define git__multiply_sizet_overflow(out, one, two) \
     __builtin_umull_overflow(one, two, out)
# elif (SIZE_MAX == ULLONG_MAX)
#  define git__add_sizet_overflow(out, one, two) \
     __builtin_uaddll_overflow(one, two, out)
#  define git__multiply_sizet_overflow(out, one, two) \
     __builtin_umulll_overflow(one, two, out)
# else
#  error compiler has add with overflow intrinsics but SIZE_MAX is unknown
# endif
74

75 76 77 78 79
# define git__add_int_overflow(out, one, two) \
    __builtin_sadd_overflow(one, two, out)
# define git__sub_int_overflow(out, one, two) \
    __builtin_ssub_overflow(one, two, out)

80 81
# define git__add_int64_overflow(out, one, two) \
    __builtin_add_overflow(one, two, out)
82 83 84 85 86 87

/* clang on 32-bit systems produces an undefined reference to `__mulodi4`. */
# if !defined(__clang__) || !defined(GIT_ARCH_32)
#  define git__multiply_int64_overflow(out, one, two) \
     __builtin_mul_overflow(one, two, out)
# endif
88

89 90 91
/* Use Microsoft's safe integer handling functions where available */
#elif defined(_MSC_VER)

92
# define ENABLE_INTSAFE_SIGNED_FUNCTIONS
93 94 95 96 97 98
# include <intsafe.h>

# define git__add_sizet_overflow(out, one, two) \
    (SizeTAdd(one, two, out) != S_OK)
# define git__multiply_sizet_overflow(out, one, two) \
    (SizeTMult(one, two, out) != S_OK)
99

100 101 102 103
#define git__add_int_overflow(out, one, two) \
    (IntAdd(one, two, out) != S_OK)
#define git__sub_int_overflow(out, one, two) \
    (IntSub(one, two, out) != S_OK)
104

105 106 107 108 109
#define git__add_int64_overflow(out, one, two) \
    (LongLongAdd(one, two, out) != S_OK)
#define git__multiply_int64_overflow(out, one, two) \
    (LongLongMult(one, two, out) != S_OK)

110 111
#else

112 113
/**
 * Sets `one + two` into `out`, unless the arithmetic would overflow.
114
 * @return false if the result fits in a `size_t`, true on overflow.
115 116 117 118
 */
GIT_INLINE(bool) git__add_sizet_overflow(size_t *out, size_t one, size_t two)
{
	if (SIZE_MAX - one < two)
119 120 121
		return true;
	*out = one + two;
	return false;
122 123 124 125
}

/**
 * Sets `one * two` into `out`, unless the arithmetic would overflow.
126
 * @return false if the result fits in a `size_t`, true on overflow.
127 128 129 130
 */
GIT_INLINE(bool) git__multiply_sizet_overflow(size_t *out, size_t one, size_t two)
{
	if (one && SIZE_MAX / one < two)
131 132 133
		return true;
	*out = one * two;
	return false;
134 135
}

136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
GIT_INLINE(bool) git__add_int_overflow(int *out, int one, int two)
{
	if ((two > 0 && one > (INT_MAX - two)) ||
	    (two < 0 && one < (INT_MIN - two)))
		return true;
	*out = one + two;
	return false;
}

GIT_INLINE(bool) git__sub_int_overflow(int *out, int one, int two)
{
	if ((two > 0 && one < (INT_MIN + two)) ||
	    (two < 0 && one > (INT_MAX + two)))
		return true;
	*out = one - two;
	return false;
}

154 155 156 157 158 159 160 161 162
GIT_INLINE(bool) git__add_int64_overflow(int64_t *out, int64_t one, int64_t two)
{
	if ((two > 0 && one > (INT64_MAX - two)) ||
	    (two < 0 && one < (INT64_MIN - two)))
		return true;
	*out = one + two;
	return false;
}

163 164 165 166
#endif

/* If we could not provide an intrinsic implementation for this, provide a (slow) fallback. */
#if !defined(git__multiply_int64_overflow)
167 168
GIT_INLINE(bool) git__multiply_int64_overflow(int64_t *out, int64_t one, int64_t two)
{
169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187
	/*
	 * Detects whether `INT64_MAX < (one * two) || INT64_MIN > (one * two)`,
	 * without incurring in undefined behavior. That is done by performing the
	 * comparison with a division instead of a multiplication, which translates
	 * to `INT64_MAX / one < two || INT64_MIN / one > two`. Some caveats:
	 *
	 * - The comparison sign is inverted when both sides of the inequality are
	 *   multiplied/divided by a negative number, so if `one < 0` the comparison
	 *   needs to be flipped.
	 * - `INT64_MAX / -1` itself overflows (or traps), so that case should be
	 *   avoided.
	 * - Since the overflow flag is defined as the discrepance between the result
	 *   of performing the multiplication in a signed integer at twice the width
	 *   of the operands, and the truncated+sign-extended version of that same
	 *   result, there are four cases where the result is the opposite of what
	 *   would be expected:
	 *   * `INT64_MIN * -1` / `-1 * INT64_MIN`
	 *   * `INT64_MIN * 1 / `1 * INT64_MIN`
	 */
188
	if (one && two) {
189
		if (one > 0 && two > 0) {
190 191
			if (INT64_MAX / one < two)
				return true;
192 193 194 195 196 197 198 199 200 201 202 203 204 205 206
		} else if (one < 0 && two < 0) {
			if ((one == -1 && two == INT64_MIN) ||
				  (two == -1 && one == INT64_MIN)) {
				*out = INT64_MIN;
				return false;
			}
			if (INT64_MAX / one > two)
				return true;
		} else if (one > 0 && two < 0) {
			if ((one == 1 && two == INT64_MIN) ||
			    (INT64_MIN / one > two))
				return true;
		} else if (one == -1) {
			if (INT64_MIN / two > one)
				return true;
207
		} else {
208 209
			if ((one == INT64_MIN && two == 1) ||
			    (INT64_MIN / one < two))
210 211 212
				return true;
		}
	}
213 214 215
	*out = one * two;
	return false;
}
216 217
#endif

218
#endif