From b15afff85c2eddec43025a1e7a63d7916c7d102e Mon Sep 17 00:00:00 2001 From: Olly Betts Date: Thu, 28 Apr 2022 18:21:27 +1200 Subject: [PATCH] Add function to subtract with overflow check This is implemented with compiler builtins or equivalent where possible, so the overflow check will typically just require a check of the processor's overflow or carry flag. (cherry picked from commit 54fe547542543fa983f9f31d496a7a6b2fdba545) --- xapian-applications/omega/configure.ac | 6 ++++ xapian-core/common/overflow.h | 66 ++++++++++++++++++++++++++++++++-- xapian-core/configure.ac | 5 ++- xapian-core/tests/unittest.cc | 19 +++++++++- 4 files changed, 91 insertions(+), 5 deletions(-) diff --git a/xapian-applications/omega/configure.ac b/xapian-applications/omega/configure.ac index d68167723..8d7a5bc5a 100644 --- a/xapian-applications/omega/configure.ac +++ b/xapian-applications/omega/configure.ac @@ -102,12 +102,18 @@ CXXFLAGS="$CXXFLAGS $XAPIAN_CXXFLAGS" dnl We need to specify the argument types for builtin functions, or else dnl AC_CHECK_DECLS fails to detect them when the compiler is clang. AC_CHECK_DECLS([__builtin_add_overflow(int, int, int*), + __builtin_sub_overflow(int, int, int*), __builtin_mul_overflow(int, int, int*)], [], [], [ ]) AC_CHECK_DECLS([__builtin_bswap32(uint32_t)], [], [], [#include ]) AC_CHECK_DECLS([_byteswap_ulong], [], [], [#include ]) AC_CHECK_DECLS([__builtin_expect(long, long)], [], [], [ ]) +AC_CHECK_DECLS([_addcarry_u32(unsigned char, unsigned, unsigned, unsigned*), + _addcarry_u64(unsigned char, unsigned __int64, unsigned __int64, unsigned __int64*), + _subborrow_u32(unsigned char, unsigned, unsigned, unsigned*), + _subborrow_u64(unsigned char, unsigned __int64, unsigned __int64, unsigned __int64*)], + [], [], [#include ]) dnl Check for time functions. AC_FUNC_STRFTIME diff --git a/xapian-core/common/overflow.h b/xapian-core/common/overflow.h index 94d3edff3..2a51a03e0 100644 --- a/xapian-core/common/overflow.h +++ b/xapian-core/common/overflow.h @@ -31,8 +31,9 @@ #include -#if !HAVE_DECL___BUILTIN_ADD_OVERFLOW -# if HAVE_DECL__ADDCARRY_U32 || HAVE_DECL__ADDCARRY_U64 +#if !HAVE_DECL___BUILTIN_ADD_OVERFLOW || !HAVE_DECL___BUILTIN_SUB_OVERFLOW +# if HAVE_DECL__ADDCARRY_U32 || HAVE_DECL__ADDCARRY_U64 || \ + HAVE_DECL__SUBBORROW_U32 || HAVE_DECL__SUBBORROW_U64 # include # endif #endif @@ -68,7 +69,7 @@ add_overflows(T1 a, T2 b, R& res) { } #if !HAVE_DECL___BUILTIN_ADD_OVERFLOW -// Only use the addcarry instrinsics where the builtins aren't available. +// Only use the addcarry intrinsics where the builtins aren't available. // GCC and clang support both, but _addcarry_u64() uses `unsigned long // long` instead of `unsigned __int64` and the two types aren't compatible. # if HAVE_DECL__ADDCARRY_U32 @@ -96,6 +97,65 @@ add_overflows +typename std::enable_if::value && + std::is_unsigned::value && + std::is_unsigned::value, bool>::type +sub_overflows(T1 a, T2 b, R& res) { +#if HAVE_DECL___BUILTIN_ADD_OVERFLOW + return __builtin_sub_overflow(a, b, &res); +#else + // Use a local variable to test for overflow so we don't need to worry if + // res could be modified by another thread between us setting and testing + // it. + R r = R(a) - R(b); + res = r; + return (sizeof(R) <= sizeof(T1) || sizeof(R) <= sizeof(T2)) && r > R(a); +#endif +} + +#if !HAVE_DECL___BUILTIN_SUB_OVERFLOW +// Only use the subborrow intrinsics where the builtins aren't available. +// GCC and clang support both, but _subborrow_u64() uses `unsigned long +// long` instead of `unsigned __int64` and the two types aren't compatible. +# if HAVE_DECL__SUBBORROW_U32 +template<> +inline bool +sub_overflows(unsigned a, + unsigned b, + unsigned& res) { + return _subborrow_u32(0, a, b, &res) != 0; +} +# endif + +# if HAVE_DECL__SUBBORROW_U64 +template<> +inline bool +sub_overflows(unsigned __int64 a, + unsigned __int64 b, + unsigned __int64& res) { + return _subborrow_u64(0, a, b, &res) != 0; +} +# endif +#endif + /** Multiplication with overflow checking. * * Multiply @a a and @a b in infinite precision, and store the result in diff --git a/xapian-core/configure.ac b/xapian-core/configure.ac index d7a3b83f1..3b9115c23 100644 --- a/xapian-core/configure.ac +++ b/xapian-core/configure.ac @@ -447,6 +447,7 @@ CXXFLAGS=$save_CXXFLAGS dnl We need to specify the argument types for builtin functions, or else dnl AC_CHECK_DECLS fails to detect them when the compiler is clang. AC_CHECK_DECLS([__builtin_add_overflow(int, int, int*), + __builtin_sub_overflow(int, int, int*), __builtin_mul_overflow(int, int, int*)], [], [], [ ]) AC_CHECK_DECLS([__builtin_bswap16(uint16_t), __builtin_bswap32(uint32_t), @@ -466,7 +467,9 @@ AC_CHECK_DECLS([__builtin_popcount(unsigned), __builtin_popcountll(unsigned long long)], [], [], [ ]) AC_CHECK_DECLS([__popcnt, __popcnt64], [], [], [#include ]) AC_CHECK_DECLS([_addcarry_u32(unsigned char, unsigned, unsigned, unsigned*), - _addcarry_u64(unsigned char, unsigned __int64, unsigned __int64, unsigned __int64*)], + _addcarry_u64(unsigned char, unsigned __int64, unsigned __int64, unsigned __int64*), + _subborrow_u32(unsigned char, unsigned, unsigned, unsigned*), + _subborrow_u64(unsigned char, unsigned __int64, unsigned __int64, unsigned __int64*)], [], [], [#include ]) dnl Check for poll(). diff --git a/xapian-core/tests/unittest.cc b/xapian-core/tests/unittest.cc index ce68e0d63..6f24fc3e4 100644 --- a/xapian-core/tests/unittest.cc +++ b/xapian-core/tests/unittest.cc @@ -1,7 +1,7 @@ /** @file * @brief Unit tests of non-Xapian-specific internal code. */ -/* Copyright (C) 2006,2007,2009,2010,2012,2015,2016,2018,2019 Olly Betts +/* Copyright (C) 2006-2022 Olly Betts * Copyright (C) 2007 Richard Boulton * * This program is free software; you can redistribute it and/or @@ -759,6 +759,22 @@ static void test_addoverflows1() TEST_EQUAL(res, ULONG_MAX - 1UL); } +static void test_suboverflows1() +{ + unsigned long res; + TEST(!sub_overflows(0UL, 0UL, res)); + TEST_EQUAL(res, 0); + + TEST(sub_overflows(0UL, 1UL, res)); + TEST_EQUAL(res, ULONG_MAX); + + TEST(sub_overflows(ULONG_MAX - 1UL, ULONG_MAX, res)); + TEST_EQUAL(res, ULONG_MAX); + + TEST(sub_overflows(0UL, ULONG_MAX, res)); + TEST_EQUAL(res, 1); +} + static void test_muloverflows1() { unsigned long res; @@ -872,6 +888,7 @@ static const test_desc tests[] = { TESTCASE(uuid1), TESTCASE(movesupport1), TESTCASE(addoverflows1), + TESTCASE(suboverflows1), TESTCASE(muloverflows1), TESTCASE(parseunsigned1), TESTCASE(parsesigned1), -- 2.11.4.GIT