Make git__strntol64() ~70%* faster This change uses compiler intrinsics to detect overflows instead of using divisions to detect potential overflow. This makes the code faster and makes it easier to read as a bonus side-effect! Some of the things this quickens: * Config parsing. * Tree parsing. * Smart protocol negotiation. \* Measured by running `libgit2_clar` with `-fno-optimize-sibling-calls -fno-omit-frame-pointer` under `perf(1)`: ```shell $ perf diff --symbols=git__strntol64 --compute=ratio \ --percentage=absolute baseline.data perf.data \# Event 'cycles' \# \# Baseline Ratio Shared Object \# ........ .............. ............. \# 0.25% 0.321836 libgit2_clar ```
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
diff --git a/src/integer.h b/src/integer.h
index 067c0be..026a1fa 100644
--- a/src/integer.h
+++ b/src/integer.h
@@ -77,6 +77,11 @@ GIT_INLINE(int) git__is_int(long long p)
# define git__sub_int_overflow(out, one, two) \
__builtin_ssub_overflow(one, two, out)
+# define git__add_int64_overflow(out, one, two) \
+ __builtin_add_overflow(one, two, out)
+# define git__multiply_int64_overflow(out, one, two) \
+ __builtin_mul_overflow(one, two, out)
+
/* Use Microsoft's safe integer handling functions where available */
#elif defined(_MSC_VER)
@@ -87,11 +92,17 @@ GIT_INLINE(int) git__is_int(long long p)
(SizeTAdd(one, two, out) != S_OK)
# define git__multiply_sizet_overflow(out, one, two) \
(SizeTMult(one, two, out) != S_OK)
+
#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)
+#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)
+
#else
/**
@@ -136,6 +147,26 @@ GIT_INLINE(bool) git__sub_int_overflow(int *out, int one, int two)
return false;
}
+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;
+}
+
+GIT_INLINE(bool) git__multiply_int64_overflow(int64_t *out, int64_t one, int64_t two)
+{
+ if ((one == -1 && two == INT_MIN) ||
+ (two == -1 && one == INT_MIN) ||
+ (one && INT64_MAX / one < two) ||
+ (one && INT64_MIN / one > two))
+ return true;
+ *out = one * two;
+ return false;
+}
+
#endif
#endif
diff --git a/src/util.c b/src/util.c
index 87ccf32..af825e4 100644
--- a/src/util.c
+++ b/src/util.c
@@ -34,8 +34,8 @@
int git__strntol64(int64_t *result, const char *nptr, size_t nptr_len, const char **endptr, int base)
{
const char *p;
- int64_t n, nn;
- int c, ovfl, v, neg, ndig;
+ int64_t n, nn, v;
+ int c, ovfl, neg, ndig;
p = nptr;
neg = 0;
@@ -110,19 +110,11 @@ int git__strntol64(int64_t *result, const char *nptr, size_t nptr_len, const cha
if (v >= base)
break;
v = neg ? -v : v;
- if (n > INT64_MAX / base || n < INT64_MIN / base) {
+ if (git__multiply_int64_overflow(&nn, n, base) || git__add_int64_overflow(&n, nn, v)) {
ovfl = 1;
/* Keep on iterating until the end of this number */
continue;
}
- nn = n * base;
- if ((v > 0 && nn > INT64_MAX - v) ||
- (v < 0 && nn < INT64_MIN - v)) {
- ovfl = 1;
- /* Keep on iterating until the end of this number */
- continue;
- }
- n = nn + v;
}
Return: