/* Overflow-safe math functions
 * Portable Snippets - https://github.com/nemequ/portable-snippets
 * Created by Evan Nemerson <evan@nemerson.com>
 *
 *   To the extent possible under law, the authors have waived all
 *   copyright and related or neighboring rights to this code.  For
 *   details, see the Creative Commons Zero 1.0 Universal license at
 *   https://creativecommons.org/publicdomain/zero/1.0/
 */

#if !defined(PSNIP_SAFE_H)
#define PSNIP_SAFE_H

#if !defined(PSNIP_SAFE_FORCE_PORTABLE)
#  if defined(__has_builtin)
#    if __has_builtin(__builtin_add_overflow) && !defined(__ibmxl__)
#      define PSNIP_SAFE_HAVE_BUILTIN_OVERFLOW
#    endif
#  elif defined(__GNUC__) && (__GNUC__ >= 5) && !defined(__INTEL_COMPILER)
#    define PSNIP_SAFE_HAVE_BUILTIN_OVERFLOW
#  endif
#  if defined(__has_include)
#    if __has_include(<intsafe.h>)
#      define PSNIP_SAFE_HAVE_INTSAFE_H
#    endif
#  elif defined(_WIN32)
#    define PSNIP_SAFE_HAVE_INTSAFE_H
#  endif
#endif /* !defined(PSNIP_SAFE_FORCE_PORTABLE) */

#if defined(__GNUC__)
#  define PSNIP_SAFE_LIKELY(expr)   __builtin_expect(!!(expr), 1)
#  define PSNIP_SAFE_UNLIKELY(expr) __builtin_expect(!!(expr), 0)
#else
#  define PSNIP_SAFE_LIKELY(expr) !!(expr)
#  define PSNIP_SAFE_UNLIKELY(expr) !!(expr)
#endif /* defined(__GNUC__) */

#if !defined(PSNIP_SAFE_STATIC_INLINE)
#  if defined(__GNUC__)
#    define PSNIP_SAFE__COMPILER_ATTRIBUTES __attribute__((__unused__))
#  else
#    define PSNIP_SAFE__COMPILER_ATTRIBUTES
#  endif

#  if defined(HEDLEY_INLINE)
#    define PSNIP_SAFE__INLINE HEDLEY_INLINE
#  elif defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L
#    define PSNIP_SAFE__INLINE inline
#  elif defined(__GNUC_STDC_INLINE__)
#    define PSNIP_SAFE__INLINE __inline__
#  elif defined(_MSC_VER) && _MSC_VER >= 1200
#    define PSNIP_SAFE__INLINE __inline
#  else
#    define PSNIP_SAFE__INLINE
#  endif

#  define PSNIP_SAFE__FUNCTION PSNIP_SAFE__COMPILER_ATTRIBUTES static PSNIP_SAFE__INLINE
#endif

// !defined(__cplusplus) added for Solaris support
#if !defined(__cplusplus) && defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L
#  define psnip_safe_bool _Bool
#else
#  define psnip_safe_bool int
#endif

#if !defined(PSNIP_SAFE_NO_FIXED)
/* For maximum portability include the exact-int module from
   portable snippets. */
#  if \
    !defined(psnip_int64_t) || !defined(psnip_uint64_t) || \
    !defined(psnip_int32_t) || !defined(psnip_uint32_t) || \
    !defined(psnip_int16_t) || !defined(psnip_uint16_t) || \
    !defined(psnip_int8_t)  || !defined(psnip_uint8_t)
#    include <stdint.h>
#    if !defined(psnip_int64_t)
#      define psnip_int64_t int64_t
#    endif
#    if !defined(psnip_uint64_t)
#      define psnip_uint64_t uint64_t
#    endif
#    if !defined(psnip_int32_t)
#      define psnip_int32_t int32_t
#    endif
#    if !defined(psnip_uint32_t)
#      define psnip_uint32_t uint32_t
#    endif
#    if !defined(psnip_int16_t)
#      define psnip_int16_t int16_t
#    endif
#    if !defined(psnip_uint16_t)
#      define psnip_uint16_t uint16_t
#    endif
#    if !defined(psnip_int8_t)
#      define psnip_int8_t int8_t
#    endif
#    if !defined(psnip_uint8_t)
#      define psnip_uint8_t uint8_t
#    endif
#  endif
#endif /* !defined(PSNIP_SAFE_NO_FIXED) */
#include <limits.h>
#include <stdlib.h>

#if !defined(PSNIP_SAFE_SIZE_MAX)
#  if defined(__SIZE_MAX__)
#    define PSNIP_SAFE_SIZE_MAX __SIZE_MAX__
#  elif defined(PSNIP_EXACT_INT_HAVE_STDINT)
#    include <stdint.h>
#  endif
#endif

#if defined(PSNIP_SAFE_SIZE_MAX)
#  define PSNIP_SAFE__SIZE_MAX_RT PSNIP_SAFE_SIZE_MAX
#else
#  define PSNIP_SAFE__SIZE_MAX_RT (~((size_t) 0))
#endif

#if defined(PSNIP_SAFE_HAVE_INTSAFE_H)
/* In VS 10, stdint.h and intsafe.h both define (U)INTN_MIN/MAX, which
   triggers warning C4005 (level 1). */
#  if defined(_MSC_VER) && (_MSC_VER == 1600)
#    pragma warning(push)
#    pragma warning(disable:4005)
#  endif
#  include <intsafe.h>
#  if defined(_MSC_VER) && (_MSC_VER == 1600)
#    pragma warning(pop)
#  endif
#endif /* defined(PSNIP_SAFE_HAVE_INTSAFE_H) */

/* If there is a type larger than the one we're concerned with it's
 * likely much faster to simply promote the operands, perform the
 * requested operation, verify that the result falls within the
 * original type, then cast the result back to the original type. */

#if !defined(PSNIP_SAFE_NO_PROMOTIONS)

#define PSNIP_SAFE_DEFINE_LARGER_BINARY_OP(T, name, op_name, op) \
  PSNIP_SAFE__FUNCTION psnip_safe_##name##_larger \
  psnip_safe_larger_##name##_##op_name (T a, T b) { \
    return ((psnip_safe_##name##_larger) a) op ((psnip_safe_##name##_larger) b); \
  }

#define PSNIP_SAFE_DEFINE_LARGER_UNARY_OP(T, name, op_name, op) \
  PSNIP_SAFE__FUNCTION psnip_safe_##name##_larger \
  psnip_safe_larger_##name##_##op_name (T value) { \
    return (op ((psnip_safe_##name##_larger) value)); \
  }

#define PSNIP_SAFE_DEFINE_LARGER_SIGNED_OPS(T, name) \
  PSNIP_SAFE_DEFINE_LARGER_BINARY_OP(T, name, add, +) \
  PSNIP_SAFE_DEFINE_LARGER_BINARY_OP(T, name, sub, -) \
  PSNIP_SAFE_DEFINE_LARGER_BINARY_OP(T, name, mul, *) \
  PSNIP_SAFE_DEFINE_LARGER_BINARY_OP(T, name, div, /) \
  PSNIP_SAFE_DEFINE_LARGER_BINARY_OP(T, name, mod, %) \
  PSNIP_SAFE_DEFINE_LARGER_UNARY_OP (T, name, neg, -)

#define PSNIP_SAFE_DEFINE_LARGER_UNSIGNED_OPS(T, name) \
  PSNIP_SAFE_DEFINE_LARGER_BINARY_OP(T, name, add, +) \
  PSNIP_SAFE_DEFINE_LARGER_BINARY_OP(T, name, sub, -) \
  PSNIP_SAFE_DEFINE_LARGER_BINARY_OP(T, name, mul, *) \
  PSNIP_SAFE_DEFINE_LARGER_BINARY_OP(T, name, div, /) \
  PSNIP_SAFE_DEFINE_LARGER_BINARY_OP(T, name, mod, %)

#define PSNIP_SAFE_IS_LARGER(ORIG_MAX, DEST_MAX) ((DEST_MAX / ORIG_MAX) >= ORIG_MAX)

#if defined(__GNUC__) && ((__GNUC__ >= 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6)) && defined(__SIZEOF_INT128__) && !defined(__ibmxl__)
#define PSNIP_SAFE_HAVE_128
typedef __int128  psnip_safe_int128_t;
typedef unsigned __int128 psnip_safe_uint128_t;
#endif /* defined(__GNUC__) */

#if !defined(PSNIP_SAFE_NO_FIXED)
#define PSNIP_SAFE_HAVE_INT8_LARGER
#define PSNIP_SAFE_HAVE_UINT8_LARGER
typedef psnip_int16_t  psnip_safe_int8_larger;
typedef psnip_uint16_t psnip_safe_uint8_larger;

#define PSNIP_SAFE_HAVE_INT16_LARGER
typedef psnip_int32_t  psnip_safe_int16_larger;
typedef psnip_uint32_t psnip_safe_uint16_larger;

#define PSNIP_SAFE_HAVE_INT32_LARGER
typedef psnip_int64_t  psnip_safe_int32_larger;
typedef psnip_uint64_t psnip_safe_uint32_larger;

#if defined(PSNIP_SAFE_HAVE_128)
#define PSNIP_SAFE_HAVE_INT64_LARGER
typedef psnip_safe_int128_t psnip_safe_int64_larger;
typedef psnip_safe_uint128_t psnip_safe_uint64_larger;
#endif /* defined(PSNIP_SAFE_HAVE_128) */
#endif /* !defined(PSNIP_SAFE_NO_FIXED) */

#define PSNIP_SAFE_HAVE_LARGER_SCHAR
#if PSNIP_SAFE_IS_LARGER(SCHAR_MAX, SHRT_MAX)
typedef short psnip_safe_schar_larger;
#elif PSNIP_SAFE_IS_LARGER(SCHAR_MAX, INT_MAX)
typedef int psnip_safe_schar_larger;
#elif PSNIP_SAFE_IS_LARGER(SCHAR_MAX, LONG_MAX)
typedef long psnip_safe_schar_larger;
#elif PSNIP_SAFE_IS_LARGER(SCHAR_MAX, LLONG_MAX)
typedef long long psnip_safe_schar_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(SCHAR_MAX, 0x7fff)
typedef psnip_int16_t psnip_safe_schar_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(SCHAR_MAX, 0x7fffffffLL)
typedef psnip_int32_t psnip_safe_schar_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(SCHAR_MAX, 0x7fffffffffffffffLL)
typedef psnip_int64_t psnip_safe_schar_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && defined(PSNIP_SAFE_HAVE_128) && (SCHAR_MAX <= 0x7fffffffffffffffLL)
typedef psnip_safe_int128_t psnip_safe_schar_larger;
#else
#undef PSNIP_SAFE_HAVE_LARGER_SCHAR
#endif

#define PSNIP_SAFE_HAVE_LARGER_UCHAR
#if PSNIP_SAFE_IS_LARGER(UCHAR_MAX, USHRT_MAX)
typedef unsigned short psnip_safe_uchar_larger;
#elif PSNIP_SAFE_IS_LARGER(UCHAR_MAX, UINT_MAX)
typedef unsigned int psnip_safe_uchar_larger;
#elif PSNIP_SAFE_IS_LARGER(UCHAR_MAX, ULONG_MAX)
typedef unsigned long psnip_safe_uchar_larger;
#elif PSNIP_SAFE_IS_LARGER(UCHAR_MAX, ULLONG_MAX)
typedef unsigned long long psnip_safe_uchar_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(UCHAR_MAX, 0xffffU)
typedef psnip_uint16_t psnip_safe_uchar_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(UCHAR_MAX, 0xffffffffUL)
typedef psnip_uint32_t psnip_safe_uchar_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(UCHAR_MAX, 0xffffffffffffffffULL)
typedef psnip_uint64_t psnip_safe_uchar_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && defined(PSNIP_SAFE_HAVE_128) && (UCHAR_MAX <= 0xffffffffffffffffULL)
typedef psnip_safe_uint128_t psnip_safe_uchar_larger;
#else
#undef PSNIP_SAFE_HAVE_LARGER_UCHAR
#endif

#if CHAR_MIN == 0 && defined(PSNIP_SAFE_HAVE_LARGER_UCHAR)
#define PSNIP_SAFE_HAVE_LARGER_CHAR
typedef psnip_safe_uchar_larger psnip_safe_char_larger;
#elif CHAR_MIN < 0 && defined(PSNIP_SAFE_HAVE_LARGER_SCHAR)
#define PSNIP_SAFE_HAVE_LARGER_CHAR
typedef psnip_safe_schar_larger psnip_safe_char_larger;
#endif

#define PSNIP_SAFE_HAVE_LARGER_SHRT
#if PSNIP_SAFE_IS_LARGER(SHRT_MAX, INT_MAX)
typedef int psnip_safe_short_larger;
#elif PSNIP_SAFE_IS_LARGER(SHRT_MAX, LONG_MAX)
typedef long psnip_safe_short_larger;
#elif PSNIP_SAFE_IS_LARGER(SHRT_MAX, LLONG_MAX)
typedef long long psnip_safe_short_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(SHRT_MAX, 0x7fff)
typedef psnip_int16_t psnip_safe_short_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(SHRT_MAX, 0x7fffffffLL)
typedef psnip_int32_t psnip_safe_short_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(SHRT_MAX, 0x7fffffffffffffffLL)
typedef psnip_int64_t psnip_safe_short_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && defined(PSNIP_SAFE_HAVE_128) && (SHRT_MAX <= 0x7fffffffffffffffLL)
typedef psnip_safe_int128_t psnip_safe_short_larger;
#else
#undef PSNIP_SAFE_HAVE_LARGER_SHRT
#endif

#define PSNIP_SAFE_HAVE_LARGER_USHRT
#if PSNIP_SAFE_IS_LARGER(USHRT_MAX, UINT_MAX)
typedef unsigned int psnip_safe_ushort_larger;
#elif PSNIP_SAFE_IS_LARGER(USHRT_MAX, ULONG_MAX)
typedef unsigned long psnip_safe_ushort_larger;
#elif PSNIP_SAFE_IS_LARGER(USHRT_MAX, ULLONG_MAX)
typedef unsigned long long psnip_safe_ushort_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(USHRT_MAX, 0xffff)
typedef psnip_uint16_t psnip_safe_ushort_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(USHRT_MAX, 0xffffffffUL)
typedef psnip_uint32_t psnip_safe_ushort_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(USHRT_MAX, 0xffffffffffffffffULL)
typedef psnip_uint64_t psnip_safe_ushort_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && defined(PSNIP_SAFE_HAVE_128) && (USHRT_MAX <= 0xffffffffffffffffULL)
typedef psnip_safe_uint128_t psnip_safe_ushort_larger;
#else
#undef PSNIP_SAFE_HAVE_LARGER_USHRT
#endif

#define PSNIP_SAFE_HAVE_LARGER_INT
#if PSNIP_SAFE_IS_LARGER(INT_MAX, LONG_MAX)
typedef long psnip_safe_int_larger;
#elif PSNIP_SAFE_IS_LARGER(INT_MAX, LLONG_MAX)
typedef long long psnip_safe_int_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(INT_MAX, 0x7fff)
typedef psnip_int16_t psnip_safe_int_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(INT_MAX, 0x7fffffffLL)
typedef psnip_int32_t psnip_safe_int_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(INT_MAX, 0x7fffffffffffffffLL)
typedef psnip_int64_t psnip_safe_int_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && defined(PSNIP_SAFE_HAVE_128) && (INT_MAX <= 0x7fffffffffffffffLL)
typedef psnip_safe_int128_t psnip_safe_int_larger;
#else
#undef PSNIP_SAFE_HAVE_LARGER_INT
#endif

#define PSNIP_SAFE_HAVE_LARGER_UINT
#if PSNIP_SAFE_IS_LARGER(UINT_MAX, ULONG_MAX)
typedef unsigned long psnip_safe_uint_larger;
#elif PSNIP_SAFE_IS_LARGER(UINT_MAX, ULLONG_MAX)
typedef unsigned long long psnip_safe_uint_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(UINT_MAX, 0xffff)
typedef psnip_uint16_t psnip_safe_uint_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(UINT_MAX, 0xffffffffUL)
typedef psnip_uint32_t psnip_safe_uint_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(UINT_MAX, 0xffffffffffffffffULL)
typedef psnip_uint64_t psnip_safe_uint_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && defined(PSNIP_SAFE_HAVE_128) && (UINT_MAX <= 0xffffffffffffffffULL)
typedef psnip_safe_uint128_t psnip_safe_uint_larger;
#else
#undef PSNIP_SAFE_HAVE_LARGER_UINT
#endif

#define PSNIP_SAFE_HAVE_LARGER_LONG
#if PSNIP_SAFE_IS_LARGER(LONG_MAX, LLONG_MAX)
typedef long long psnip_safe_long_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(LONG_MAX, 0x7fff)
typedef psnip_int16_t psnip_safe_long_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(LONG_MAX, 0x7fffffffLL)
typedef psnip_int32_t psnip_safe_long_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(LONG_MAX, 0x7fffffffffffffffLL)
typedef psnip_int64_t psnip_safe_long_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && defined(PSNIP_SAFE_HAVE_128) && (LONG_MAX <= 0x7fffffffffffffffLL)
typedef psnip_safe_int128_t psnip_safe_long_larger;
#else
#undef PSNIP_SAFE_HAVE_LARGER_LONG
#endif

#define PSNIP_SAFE_HAVE_LARGER_ULONG
#if PSNIP_SAFE_IS_LARGER(ULONG_MAX, ULLONG_MAX)
typedef unsigned long long psnip_safe_ulong_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(ULONG_MAX, 0xffff)
typedef psnip_uint16_t psnip_safe_ulong_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(ULONG_MAX, 0xffffffffUL)
typedef psnip_uint32_t psnip_safe_ulong_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && PSNIP_SAFE_IS_LARGER(ULONG_MAX, 0xffffffffffffffffULL)
typedef psnip_uint64_t psnip_safe_ulong_larger;
#elif !defined(PSNIP_SAFE_NO_FIXED) && defined(PSNIP_SAFE_HAVE_128) && (ULONG_MAX <= 0xffffffffffffffffULL)
typedef psnip_safe_uint128_t psnip_safe_ulong_larger;
#else
#undef PSNIP_SAFE_HAVE_LARGER_ULONG