Defining a functions for all integers available on a platform

Question

I would like to write a family of functions for different integers types INT whose signature is

INT safe_product(INT a, INT b, bool& error);

which takes two integers a and b and returns a * b if a * b does not overflow and returns 0 and sets error to true if a * b does overflow. I also want this function to be efficient and I want it to run on 32-bit and 64-bit platforms.

I am thinking of overloading safe_product using std::int32_t, std::uint32_t, std::int64_t, std::uint64_t, etc. I believe that std::int64_t is not always defined with a 32-bit compiler. Is there a way to know at compile time if it is defined?

Moreover, if we are on a 64-bit plateform, the best way to implement a safe product in between 2 32-bit integers is the following:

std::int32_t safe_product(std::int32_t a, std::int32_t b,
                          bool& error) {
  const std::int64_t a_64 = a;
  const std::int64_t b_64 = b;
  const std::int64_t ab_64 = a_64 * b_64;
  if (ab_64 > std::numeric_limits<std::int32_t>::max() ||
      ab_64 < std::numeric_limits<std::int32_t>::min()) {
    error = true;
    return 0;
  } else {
    error = false;
    return static_cast<std::int32_t>(ab_64);
  }
}

but if we are a 32-bit platform, the fastest algorithm might imply computing some integer division.

So I have 2 questions:

• How do I declare my safe_product so it is defined for all integers types available on my platform (and obviously not for the ones that don't exist)?

• How do I make it efficient on both 32-bit and 64-bit using the algorithms I know?

Answer 1

Deducing the fastest integer type in a totally portable way is not a simple task. You might consider using int_fastXX_t family of types, but they are not guaranteed to be what you want. You can also look at the size of void* and introduce your own logic for deducing the integer type you want to use. For simplicity, I've defined int and unsigned int to be the fastest integers.

First, define our "fastest" integer types and a helper trait to know if a type is small enough to promote. Anything smaller will be promoted to the "fastest" integer type as you did your in example. Anything equal in size or larger will use integer division to predict overflow.

#include <cstdint>
#include <limits>
#include <type_traits>

// Define the fastest types for our case
using t_fast_int = int;
using t_fast_uint = unsigned int;

// Helper trait, to indicate if a type is small enough to promote
template<class T>
struct t_is_small : std::bool_constant<sizeof(T) < sizeof(t_fast_int)> {};

Second, define a generic function and use enable_if ([link(http://en.cppreference.com/w/cpp/types/enable_if)) to only enable it for small types. This uses the method you describe in your question.

template<class T>
std::enable_if_t<t_is_small<T>::value, T>
safe_product(T a, T b, bool& error)
{
    // Should we use intmax_t or uintmax_t in this case?
    using t_large = std::conditional_t<std::is_signed<T>::value, t_fast_int, t_fast_uint>;

    const t_large a_64 = a;
    const t_large b_64 = b;
    const t_large ab_64 = a_64 * b_64;
    if (ab_64 > std::numeric_limits<T>::max() ||
        ab_64 < std::numeric_limits<T>::min())
    {
        error = true;
        return 0;
    }
    else
    {
        error = false;
        return static_cast<T>(ab_64);
    }
}

Finally, add another overload for large integer types. Notice that the enable_if condition is inverted. I've used integer division to anticipate an overflow or underflow.

template<class T>
std::enable_if_t<t_is_small<T>::value == false, T>
safe_product(T a, T b, bool& error)
{
    if(b == 0) {
        // The result will be zero (avoids division by zero below)
        error = false;
    }
    else {
        // Calculate the largest `a` that would not result in an overflow
        constexpr auto max_int = std::numeric_limits<T>::max();
        auto max_a = max_int / b;

        // Calculate the smallest `a` that would not result in underflow
        constexpr auto min_int = std::numeric_limits<T>::min();
        auto min_a = min_int / b;

        // If a is greater than max_a an overflow would occur
        // If a is less than min_a an undeflow would occur
        if(b > 0) {
            error = (a > max_a) || (a < min_a);
        }
        else {
            error = (a < max_a) || (a > min_a);
        }
    }
    if(error) {
        return 0;
    }
    else {
        return a * b;
    }
}