Safely check if signed multiplication would overflow in C++17

Question

I'm looking for a convenient idiom to check if a multiplication of two signed integers (longs or long longs) would overflow in versions of C++ where signed arithmetic overflow is undefined behavior (C or C++17 and earlier). I'm okay using any library functions available in C++17, but in an ideal world would like something cheaper than integer division (e.g., checking b <= std::numeric_limits<long long>::max() / a or b >= std::numeric_limits<long long>::lowest() / a or permutations with -b depending on the signedness of the arguments). In an ideal world the solution would be something the compiler could optimize away (so also not manually performing the multiplication one word at a time).

I'd like to avoid any idioms that first perform the multiplication, then sanity-check the result, because a compiler might remove the sanity check based on the assumption that signed arithmetic cannot overflow. (After all, overflow would be undefined behavior, so the compiler can assume the programmer would never let that happen.) Unfortunately, most algorithms I've seen suggested are of this form, so would appear to be unsafe.

Answer 1

See function multiplication_would_overflow.

// main.ixx
//
// RESOURCES:
// 
// Chapter 5 of "Secure Coding in C and C++" by Seacord
// https://ptgmedia.pearsoncmg.com/images/0321335724/samplechapter/seacord_ch05.pdf
//
// How do I detect unsigned integer multiply overflow?
// https://stackoverflow.com/questions/199333/how-do-i-detect-unsigned-integer-multiply-overflow
//
// Detecting signed overflow in C/C++
// https://stackoverflow.com/questions/3944505/detecting-signed-overflow-in-c-c
//
// SafeInt
// https://github.com/dcleblanc/SafeInt/blob/master/SafeInt.hpp
//
// Clang: Checked Arithmetic Builtins
// http://clang.llvm.org/docs/LanguageExtensions.html#checked-arithmetic-builtins

export module main;
import std;

template< typename integer_type >
constexpr bool addition_would_overflow(
    integer_type const lop, 
    integer_type const rop)
{
    enum : integer_type { zero };
    auto const max{ std::numeric_limits<integer_type>::max() };
    auto const min{ std::numeric_limits<integer_type>::min() };
    return rop < zero
        ? (lop < min - rop)
        : (lop > max - rop);
}
template< typename integer_type >
constexpr bool subtraction_would_overflow(
    integer_type const lop, 
    integer_type const rop)
{
    enum : integer_type { zero };
    auto const max{ std::numeric_limits<integer_type>::max() };
    auto const min{ std::numeric_limits<integer_type>::min() };
    return rop < zero
        ? (lop > max + rop)
        : (lop < min + rop);
}
template< typename integer_type >
constexpr bool multiplication_would_overflow(
    integer_type const lop, 
    integer_type const rop)
{
    enum : integer_type { zero };
    auto const max{ std::numeric_limits<integer_type>::max() };
    auto const min{ std::numeric_limits<integer_type>::min() };
    return lop != zero
        && rop != zero
        && (lop < zero
            ? (rop < zero ? lop < max / rop : lop < min / rop)
            : (rop < zero ? rop < min / lop : lop > max / rop)
            );
}
template< typename integer_type >
constexpr bool division_would_overflow(
    integer_type const lop, 
    integer_type const rop)
{
    enum : integer_type { zero, minus1 = -1 };
    auto const max{ std::numeric_limits<integer_type>::max() };
    auto const min{ std::numeric_limits<integer_type>::min() };
    if constexpr (std::is_signed_v<integer_type>)
    {
        if (lop == min && rop == minus1 ||
            rop == min && lop == minus1)
            return true;
    }
    return rop == zero;
}

export int main()
{
    using integer_type = long long;
    integer_type const one{ 1 }, two{ 2 }, minus1{ -1 };
    auto const max{ std::numeric_limits<integer_type>::max() };
    auto const min{ std::numeric_limits<integer_type>::min() };

    std::cout << std::boolalpha
        << "addition       : " << addition_would_overflow(max, one)
        << "\nsubtraction    : " << subtraction_would_overflow(min, one)
        << "\nmultiplication : " << multiplication_would_overflow(max, two)
        << "\ndivision       : " << division_would_overflow(min, minus1)
        << "\n\n";
    return 0;
}
// end file: main.ixx

Answer 2

For clang and gcc, just use their builtins

#include<optional>

template<typename I>
std::optional<I> mul(I x, I y) {
    I res;
    if(__builtin_mul_overflow(x, y, &res))
        return {};
    return res;
}

For msvc, perform multiplication in wider integers when possible, and use __mulh otherwise

#include<intrin.h>
#include<cstdint>
#include<optional>
#include<limits>

template<typename I>
std::optional<I> mul(I x, I y)
{
    if constexpr(std::is_same_v<I, std::int64_t>)
    {
        auto hi = __mulh(x, y);
        auto lo = std::uint64_t(x) * std::uint64_t(y);
        auto neg = lo >> 63;

        if(hi != 0 && hi != -1)
            return {};
        if((hi == 0 && neg) || (hi == -1 && !neg))
            return {};
        return x * y;
    }
    else
    {
        auto res = std::int64_t(x) * y;
        if(res > std::numeric_limits<I>::max() || res < std::numeric_limits<I>::min())
            return {};
        return I(res);
    }
}

While test division is often taught and somewhat simpler conceptually, it is atrociously slow. Using these intrinsics are expected to be significantly faster due to hardware support and less branching. For example, micro benchmarking shows a 81x speedup for clang intrinsics over test division.