Utility functions for checked arithmetic

[george.karpenkov]

Summary

Provide checkedAdd and checkedMul functions, providing checked arithmetic on signed 64 bit integers.

[vsk]

It would be great to have checked* utilities which work with all the different kinds of integers.

include/llvm/Support/MathExtras.h

852 ↗

(On Diff #135743)

Once this lands, I think people will want to use it for more than just int64_t. To make this generic we'll need templates, and that introduces a cyclic-dependency problem with APInt.h.

Sorry for not thinking of this earlier, but: wdyt of moving this to Support/CheckedArithmetic.h (or similar)?

lib/Support/MathExtras.cpp

21 ↗

(On Diff #135743)

Could you move the APInt include up to the right spot?

26 ↗

(On Diff #135743)

Please clang-format your diffs.

29 ↗

(On Diff #135743)

llvm::function_ref is more appropriate for non-owning callables.

[george.karpenkov]

lib/Support/MathExtras.cpp

29 ↗

(On Diff #135743)

...except it does not work here, and I don't think it's worth it to investigate why

[vsk]

include/llvm/Support/CheckedArithmetic.h

32

Can you move this out of the llvm namespace, into an anonymous namespace?

34

I'd rather just have the type of the function be some free template parameter, then, so it's clear the object isn't copied.

[george.karpenkov]

include/llvm/Support/CheckedArithmetic.h

34

Could you elaborate?

[vsk]

include/llvm/Support/CheckedArithmetic.h

34

I'm suggesting adding 'typename F' to the template parameter list and using F as the type of Op. It's shorter, and since there's no std::function, it signals to the reader that there are no unnecessary copies happening. Taken together this makes the code easier to read.

[vsk]

Thanks! Please wait a day or so before committing to give others time to provide feedback.

include/llvm/Support/CheckedArithmetic.h

21

This include can go away now.

[delcypher]

This comment was removed by delcypher.

include/llvm/Support/CheckedArithmetic.h

+//==-- llvm/Support/CheckedArithmetic.h - Safe arithmetical operations *- C++ //
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains generic functions for operating on integers which
+// give the indication on whether the operation has overflown.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_CHECKEDARITHMETIC_H
+#define LLVM_SUPPORT_CHECKEDARITHMETIC_H
+
+#include "llvm/ADT/APInt.h"
+
+#include <type_traits>
+
+namespace {
+
+/// Utility function to apply a given method of \c APInt \p F to \p LHS and
+/// \p RHS, and write the output into \p Res.
+/// \return Whether the operation overflows.
+template <typename T, typename F>
+typename std::enable_if<std::is_integral<T>::value && sizeof(T) * 8 <= 64,
+                        bool>::type
+checkedOp(T LHS, T RHS, F Op, T *Res = nullptr, bool Signed = true) {
+  llvm::APInt ALHS(/*BitSize=*/sizeof(T) * 8, LHS, Signed);
+  llvm::APInt ARHS(/*BitSize=*/sizeof(T) * 8, RHS, Signed);
+  bool Overflow;
+  llvm::APInt Out = (ALHS.*Op)(ARHS, Overflow);
+  if (Res)
+    *Res = Signed ? Out.getSExtValue() : Out.getZExtValue();
+  return Overflow;
+}
+}
+
+namespace llvm {
+
+/// Add two signed integers \p LHS and \p RHS, write into \p Res if non-null.
+/// Does not guarantee saturating arithmetic.
+/// \return Whether the result overflows.
+template <typename T>
+typename std::enable_if<std::is_signed<T>::value, bool>::type
+checkedAdd(T LHS, T RHS, T *Res = nullptr) {
+  return checkedOp(LHS, RHS, &llvm::APInt::sadd_ov, Res);
+}
+
+/// Multiply two signed integers \p LHS and \p RHS, write into \p Res if
+/// non-null.
+/// Does not guarantee saturating arithmetic.
+/// \return Whether the result overflows.
+template <typename T>
+typename std::enable_if<std::is_signed<T>::value, bool>::type
+checkedMul(T LHS, T RHS, T *Res = nullptr) {
+  return checkedOp(LHS, RHS, &llvm::APInt::smul_ov, Res);
+}
+
+/// Add two unsigned integers \p LHS and \p RHS, write into \p Res if non-null.
+/// Does not guarantee saturating arithmetic.
+/// \return Whether the result overflows.
+template <typename T>
+typename std::enable_if<std::is_unsigned<T>::value, bool>::type
+checkedAddUnsigned(T LHS, T RHS, T *Res = nullptr) {
+  return checkedOp(LHS, RHS, &llvm::APInt::uadd_ov, Res, /*Signed=*/false);
+}
+
+/// Multiply two unsigned integers \p LHS and \p RHS, write into \p Res if
+/// non-null.
+/// Does not guarantee saturating arithmetic.
+/// \return Whether the result overflows.
+template <typename T>
+typename std::enable_if<std::is_unsigned<T>::value, bool>::type
+checkedMulUnsigned(T LHS, T RHS, T *Res = nullptr) {
+  return checkedOp(LHS, RHS, &llvm::APInt::umul_ov, Res, /*Signed=*/false);
+}
+
+} // End llvm namespace
+
+#endif

unittests/Support/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_llvm_unittest(SupportTests
   AlignOfTest.cpp
   AllocatorTest.cpp
   ARMAttributeParser.cpp
   ArrayRecyclerTest.cpp
   BinaryStreamTest.cpp
   BlockFrequencyTest.cpp
   BranchProbabilityTest.cpp
   CachePruningTest.cpp
   CrashRecoveryTest.cpp
   Casting.cpp
+  CheckedArithmeticTest.cpp
   Chrono.cpp
   CommandLineTest.cpp
   CompressionTest.cpp
   ConvertUTFTest.cpp
   DataExtractorTest.cpp
   DebugTest.cpp
   DJBTest.cpp
   EndianStreamTest.cpp

unittests/Support/CheckedArithmeticTest.cpp

+#include "llvm/Support/CheckedArithmetic.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+TEST(CheckedArithmetic, CheckedAdd) {
+  int64_t Out;
+  const int64_t Max = std::numeric_limits<int64_t>::max();
+  const int64_t Min = std::numeric_limits<int64_t>::min();
+  EXPECT_EQ(checkedAdd<int64_t>(Max, Max, &Out), true);
+  EXPECT_EQ(checkedAdd<int64_t>(Min, -1, &Out), true);
+  EXPECT_EQ(checkedAdd<int64_t>(Max, 1, &Out), true);
+  EXPECT_EQ(checkedAdd<int64_t>(10, 1, &Out), false);
+  EXPECT_EQ(Out, 11);
+}
+
+TEST(CheckedArithmetic, CheckedAddSmall) {
+  int16_t Out;
+  const int16_t Max = std::numeric_limits<int16_t>::max();
+  const int16_t Min = std::numeric_limits<int16_t>::min();
+  EXPECT_EQ(checkedAdd<int16_t>(Max, Max, &Out), true);
+  EXPECT_EQ(checkedAdd<int16_t>(Min, -1, &Out), true);
+  EXPECT_EQ(checkedAdd<int16_t>(Max, 1, &Out), true);
+  EXPECT_EQ(checkedAdd<int16_t>(10, 1, &Out), false);
+  EXPECT_EQ(Out, 11);
+}
+
+TEST(CheckedArithmetic, CheckedMul) {
+  int64_t Out;
+  const int64_t Max = std::numeric_limits<int64_t>::max();
+  const int64_t Min = std::numeric_limits<int64_t>::min();
+  EXPECT_EQ(checkedMul<int64_t>(Max, 2, &Out), true);
+  EXPECT_EQ(checkedMul<int64_t>(Max, Max, &Out), true);
+  EXPECT_EQ(checkedMul<int64_t>(Min, 2, &Out), true);
+  EXPECT_EQ(checkedMul<int64_t>(10, 2, &Out), false);
+  EXPECT_EQ(Out, 20);
+}
+
+TEST(CheckedArithmetic, CheckedMulSmall) {
+  int16_t Out;
+  const int16_t Max = std::numeric_limits<int16_t>::max();
+  const int16_t Min = std::numeric_limits<int16_t>::min();
+  EXPECT_EQ(checkedMul<int16_t>(Max, 2, &Out), true);
+  EXPECT_EQ(checkedMul<int16_t>(Max, Max, &Out), true);
+  EXPECT_EQ(checkedMul<int16_t>(Min, 2, &Out), true);
+  EXPECT_EQ(checkedMul<int16_t>(10, 2, &Out), false);
+  EXPECT_EQ(Out, 20);
+}
+
+TEST(CheckedArithmetic, CheckedAddUnsigned) {
+  uint64_t Out;
+  const uint64_t Max = std::numeric_limits<uint64_t>::max();
+  EXPECT_EQ(checkedAddUnsigned<uint64_t>(Max, Max, &Out), true);
+  EXPECT_EQ(checkedAddUnsigned<uint64_t>(Max, 1, &Out), true);
+  EXPECT_EQ(checkedAddUnsigned<uint64_t>(10, 1, &Out), false);
+  EXPECT_EQ(Out, uint64_t(11));
+}
+
+TEST(CheckedArithmetic, CheckedMulUnsigned) {
+  uint64_t Out;
+  const uint64_t Max = std::numeric_limits<uint64_t>::max();
+  EXPECT_EQ(checkedMulUnsigned<uint64_t>(Max, 2, &Out), true);
+  EXPECT_EQ(checkedMulUnsigned<uint64_t>(Max, Max, &Out), true);
+  EXPECT_EQ(checkedMulUnsigned<uint64_t>(10, 2, &Out), false);
+  EXPECT_EQ(Out, uint64_t(20));
+}
+
+
+} // namespace