SkSafeMath for tracking size_t overflow

Do multiply (mul) and add while tracking that the
calculation does not overflow, which can be checked with
ok().

The new unit test shows a couple examples.

Author:  Herb Derby <herb@google.com>
Change-Id: I7e67671d2488d67f21d47d9618736a6bae8f23c3
Reviewed-on: https://skia-review.googlesource.com/33721
Reviewed-by: Mike Klein <mtklein@chromium.org>
Commit-Queue: Herb Derby <herb@google.com>

3 files changed, 121 insertions, 0 deletions

diff --git a/gn/tests.gni b/gn/tests.gni
index 26bdc94745..c2f3759cd2 100644
--- a/gn/tests.gni
+++ b/gn/tests.gni
@@ -191,6 +191,7 @@ tests_sources = [
   "$_tests/RoundRectTest.cpp",
   "$_tests/RRectInPathTest.cpp",
   "$_tests/RTreeTest.cpp",
+  "$_tests/SafeMathTest.cpp",
   "$_tests/ScalarTest.cpp",
   "$_tests/ScaleToSidesTest.cpp",
   "$_tests/SerializationTest.cpp",
diff --git a/src/core/SkSafeMath.h b/src/core/SkSafeMath.h
new file mode 100644
index 0000000000..91200fbb56
--- /dev/null
+++ b/src/core/SkSafeMath.h
@@ -0,0 +1,69 @@
+/*
+ * Copyright 2017 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkSafeMath_DEFINED
+#define SkSafeMath_DEFINED
+
+// SkSafeMath always check that a series of operations do not overflow.
+// This must be correct for all platforms, because this is a check for safety at runtime.
+
+class SkSafeMath {
+public:
+    SkSafeMath() = default;
+
+    bool ok() const { return fOK; }
+    explicit operator bool() const { return fOK; }
+
+    size_t mul(size_t x, size_t y) {
+        return sizeof(size_t) == sizeof(uint64_t) ? mul64(x, y) : mul32(x, y);
+    }
+
+    size_t add(size_t x, size_t y) {
+        size_t result = x + y;
+        fOK &= result >= x;
+        return result;
+    }
+
+private:
+    uint32_t mul32(uint32_t x, uint32_t y) {
+        uint64_t bx = x;
+        uint64_t by = y;
+        uint64_t result = bx * by;
+        fOK &= result >> 32 == 0;
+        return result;
+    }
+
+    uint64_t mul64(uint64_t x, uint64_t y) {
+        if (x <= std::numeric_limits<uint64_t>::max() >> 32
+            && y <= std::numeric_limits<uint64_t>::max() >> 32) {
+            return x * y;
+        } else {
+            auto hi = [](uint64_t x) { return x >> 32; };
+            auto lo = [](uint64_t x) { return x & 0xFFFFFFFF; };
+
+            uint64_t lx_ly = lo(x) * lo(y);
+            uint64_t hx_ly = hi(x) * lo(y);
+            uint64_t lx_hy = lo(x) * hi(y);
+            uint64_t hx_hy = hi(x) * hi(y);
+            uint64_t result = 0;
+            result = this->add(lx_ly, (hx_ly << 32));
+            result = this->add(result, (lx_hy << 32));
+            fOK &= (hx_hy + (hx_ly >> 32) + (lx_hy >> 32)) == 0;
+
+            #if defined(SK_DEBUG) && defined(__clang__) && defined(__x86_64__)
+                auto double_check = (unsigned __int128)x * y;
+                SkASSERT(result == (double_check & 0xFFFFFFFFFFFFFFFF));
+                SkASSERT(!fOK || (double_check >> 64 == 0));
+            #endif
+
+            return result;
+        }
+    }
+    bool fOK = true;
+};
+
+#endif//SkSafeMath_DEFINED
diff --git a/tests/SafeMathTest.cpp b/tests/SafeMathTest.cpp
new file mode 100644
index 0000000000..7f597393d0
--- /dev/null
+++ b/tests/SafeMathTest.cpp
@@ -0,0 +1,51 @@
+/*
+ * Copyright 2017 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "Test.h"
+#include "SkSafeMath.h"
+
+DEF_TEST(SafeMath, r) {
+    size_t max = std::numeric_limits<size_t>::max();
+
+    {
+        size_t halfMax = max >> 1;
+        size_t halfMaxPlus1 = halfMax + 1;
+        SkSafeMath safe;
+        REPORTER_ASSERT(r, safe.add(halfMax, halfMax) == 2 * halfMax);
+        REPORTER_ASSERT(r, safe);
+        REPORTER_ASSERT(r, safe.add(halfMax, halfMaxPlus1) == max);
+        REPORTER_ASSERT(r, safe);
+        REPORTER_ASSERT(r, safe.add(max, 1) == 0);
+        REPORTER_ASSERT(r, !safe);
+    }
+
+    {
+        SkSafeMath safe;
+        (void) safe.add(max, max);
+        REPORTER_ASSERT(r, !safe);
+    }
+
+    {
+        size_t bits = (sizeof(size_t) * 8);
+        size_t halfBits = bits / 2;
+        size_t sqrtMax = max >> halfBits;
+        size_t sqrtMaxPlus1 = sqrtMax + 1;
+        SkSafeMath safe;
+        REPORTER_ASSERT(r, safe.mul(sqrtMax, sqrtMax) == sqrtMax * sqrtMax);
+        REPORTER_ASSERT(r, safe);
+        REPORTER_ASSERT(r, safe.mul(sqrtMax, sqrtMaxPlus1) == sqrtMax << halfBits);
+        REPORTER_ASSERT(r, safe);
+        REPORTER_ASSERT(r, safe.mul(sqrtMaxPlus1, sqrtMaxPlus1) == 0);
+        REPORTER_ASSERT(r, !safe);
+    }
+
+    {
+        SkSafeMath safe;
+        (void) safe.mul(max, max);
+        REPORTER_ASSERT(r, !safe);
+    }
+}