Bug 1194721: Add |Saturate| template for saturation arithmetics, r=nfroyd
☠☠ backed out by 454ca590e200 ☠ ☠
authorThomas Zimmermann <tdz@users.sourceforge.net>
Wed, 03 Feb 2016 15:16:00 +0100
changeset 282856 8d6c228ef008aed235cc1c9ec922d55ce1e9a265
parent 282855 52a2a349ff2ad0c7831cd6649820f901058b9327
child 282857 bbadd0a1367ddd8894c615867ce3a16e27afe128
push id71333
push usertdz@users.sourceforge.net
push dateWed, 03 Feb 2016 14:17:14 +0000
treeherdermozilla-inbound@8adcb4e83cf4 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersnfroyd
bugs1194721
milestone47.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1194721: Add |Saturate| template for saturation arithmetics, r=nfroyd |Saturate<T>| implements saturation arithmetics for arbitrary basic types. Operations on its value won't over- or underflow the type's range.
mfbt/Saturate.h
mfbt/moz.build
mfbt/tests/TestSaturate.cpp
mfbt/tests/moz.build
testing/cppunittest.ini
new file mode 100644
--- /dev/null
+++ b/mfbt/Saturate.h
@@ -0,0 +1,287 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/* Provides saturation arithmetics for scalar types. */
+
+#ifndef mozilla_Saturate_h
+#define mozilla_Saturate_h
+
+#include "mozilla/Attributes.h"
+#include "mozilla/Move.h"
+#include "mozilla/NumericLimits.h"
+#include "mozilla/TypeTraits.h"
+
+namespace mozilla {
+namespace detail {
+
+/**
+ * |SaturateOp<T>| wraps scalar values for saturation arithmetics. Usage:
+ *
+ *    uint32_t value = 1;
+ *
+ *    ++SaturateOp<uint32_t>(value); // value is 2
+ *    --SaturateOp<uint32_t>(value); // value is 1
+ *    --SaturateOp<uint32_t>(value); // value is 0
+ *    --SaturateOp<uint32_t>(value); // value is still 0
+ *
+ * Please add new operators when required.
+ *
+ * |SaturateOp<T>| will saturate at the minimum and maximum values of
+ * type T. If you need other bounds, implement a clamped-type class and
+ * specialize the type traits accordingly.
+ */
+template <typename T>
+class SaturateOp
+{
+public:
+  explicit SaturateOp(T& aValue)
+    : mValue(aValue)
+  {
+    // We should actually check for |std::is_scalar<T>::value| to be
+    // true, but this type trait is not available everywhere. Relax
+    // this assertion if you want to use floating point values as well.
+    static_assert(IsIntegral<T>::value,
+                  "Integral type required in instantiation");
+  }
+
+  // Add and subtract operators
+
+  T operator+(const T& aRhs) const
+  {
+    return T(mValue) += aRhs;
+  }
+
+  T operator-(const T& aRhs) const
+  {
+    return T(mValue) -= aRhs;
+  }
+
+  // Compound operators
+
+  const T& operator+=(const T& aRhs) const
+  {
+    const T min = NumericLimits<T>::min();
+    const T max = NumericLimits<T>::max();
+
+    if (aRhs > static_cast<T>(0)) {
+      mValue = (max - aRhs) < mValue ? max : mValue + aRhs;
+    } else {
+      mValue = (min - aRhs) > mValue ? min : mValue + aRhs;
+    }
+    return mValue;
+  }
+
+  const T& operator-=(const T& aRhs) const
+  {
+    const T min = NumericLimits<T>::min();
+    const T max = NumericLimits<T>::max();
+
+    if (aRhs > static_cast<T>(0)) {
+      mValue = (min + aRhs) > mValue ? min : mValue - aRhs;
+    } else {
+      mValue = (max + aRhs) < mValue ? max : mValue - aRhs;
+    }
+    return mValue;
+  }
+
+  // Increment and decrement operators
+
+  const T& operator++() const // prefix
+  {
+    return operator+=(static_cast<T>(1));
+  }
+
+  T operator++(int) const // postfix
+  {
+    const T value(mValue);
+    operator++();
+    return value;
+  }
+
+  const T& operator--() const // prefix
+  {
+    return operator-=(static_cast<T>(1));
+  }
+
+  T operator--(int) const // postfix
+  {
+    const T value(mValue);
+    operator--();
+    return value;
+  }
+
+private:
+  SaturateOp(const SaturateOp<T>&) = delete;
+  SaturateOp(SaturateOp<T>&&) = delete;
+  SaturateOp& operator=(const SaturateOp<T>&) = delete;
+  SaturateOp& operator=(SaturateOp<T>&&) = delete;
+
+  T& mValue;
+};
+
+/**
+ * |Saturate<T>| is a value type for saturation arithmetics. It's
+ * build on top of |SaturateOp<T>|.
+ */
+template <typename T>
+class Saturate
+{
+public:
+  Saturate() = default;
+  MOZ_IMPLICIT Saturate(const Saturate<T>&) = default;
+
+  MOZ_IMPLICIT Saturate(Saturate<T>&& aValue)
+  {
+    mValue = Move(aValue.mValue);
+  }
+
+  explicit Saturate(const T& aValue)
+    : mValue(aValue)
+  { }
+
+  const T& value() const
+  {
+    return mValue;
+  }
+
+  // Compare operators
+
+  bool operator==(const Saturate<T>& aRhs) const
+  {
+    return mValue == aRhs.mValue;
+  }
+
+  bool operator!=(const Saturate<T>& aRhs) const
+  {
+    return !operator==(aRhs);
+  }
+
+  bool operator==(const T& aRhs) const
+  {
+    return mValue == aRhs;
+  }
+
+  bool operator!=(const T& aRhs) const
+  {
+    return !operator==(aRhs);
+  }
+
+  // Assignment operators
+
+  Saturate<T>& operator=(const Saturate<T>&) = default;
+
+  Saturate<T>& operator=(Saturate<T>&& aRhs)
+  {
+    mValue = Move(aRhs.mValue);
+    return *this;
+  }
+
+  // Add and subtract operators
+
+  Saturate<T> operator+(const Saturate<T>& aRhs) const
+  {
+    Saturate<T> lhs(mValue);
+    return lhs += aRhs.mValue;
+  }
+
+  Saturate<T> operator+(const T& aRhs) const
+  {
+    Saturate<T> lhs(mValue);
+    return lhs += aRhs;
+  }
+
+  Saturate<T> operator-(const Saturate<T>& aRhs) const
+  {
+    Saturate<T> lhs(mValue);
+    return lhs -= aRhs.mValue;
+  }
+
+  Saturate<T> operator-(const T& aRhs) const
+  {
+    Saturate<T> lhs(mValue);
+    return lhs -= aRhs;
+  }
+
+  // Compound operators
+
+  Saturate<T>& operator+=(const Saturate<T>& aRhs)
+  {
+    SaturateOp<T>(mValue) += aRhs.mValue;
+    return *this;
+  }
+
+  Saturate<T>& operator+=(const T& aRhs)
+  {
+    SaturateOp<T>(mValue) += aRhs;
+    return *this;
+  }
+
+  Saturate<T>& operator-=(const Saturate<T>& aRhs)
+  {
+    SaturateOp<T>(mValue) -= aRhs.mValue;
+    return *this;
+  }
+
+  Saturate<T>& operator-=(const T& aRhs)
+  {
+    SaturateOp<T>(mValue) -= aRhs;
+    return *this;
+  }
+
+  // Increment and decrement operators
+
+  Saturate<T>& operator++() // prefix
+  {
+    ++SaturateOp<T>(mValue);
+    return *this;
+  }
+
+  Saturate<T> operator++(int) // postfix
+  {
+    return Saturate<T>(SaturateOp<T>(mValue)++);
+  }
+
+  Saturate<T>& operator--() // prefix
+  {
+    --SaturateOp<T>(mValue);
+    return *this;
+  }
+
+  Saturate<T> operator--(int) // postfix
+  {
+    return Saturate<T>(SaturateOp<T>(mValue)--);
+  }
+
+private:
+  T mValue;
+};
+
+} // namespace detail
+
+typedef detail::Saturate<int8_t> SaturateInt8;
+typedef detail::Saturate<int16_t> SaturateInt16;
+typedef detail::Saturate<int32_t> SaturateInt32;
+typedef detail::Saturate<uint8_t> SaturateUint8;
+typedef detail::Saturate<uint16_t> SaturateUint16;
+typedef detail::Saturate<uint32_t> SaturateUint32;
+
+} // namespace mozilla
+
+template<typename LhsT, typename RhsT>
+bool
+operator==(LhsT aLhs, const mozilla::detail::Saturate<RhsT>& aRhs)
+{
+  return aRhs.operator==(static_cast<RhsT>(aLhs));
+}
+
+template<typename LhsT, typename RhsT>
+bool
+operator!=(LhsT aLhs, const mozilla::detail::Saturate<RhsT>& aRhs)
+{
+  return !(aLhs == aRhs);
+}
+
+#endif // mozilla_Saturate_h
--- a/mfbt/moz.build
+++ b/mfbt/moz.build
@@ -68,16 +68,17 @@ EXPORTS.mozilla = [
     'RangedArray.h',
     'RangedPtr.h',
     'ReentrancyGuard.h',
     'RefCounted.h',
     'RefCountType.h',
     'RefPtr.h',
     'ReverseIterator.h',
     'RollingMean.h',
+    'Saturate.h',
     'Scoped.h',
     'ScopeExit.h',
     'SegmentedVector.h',
     'SHA1.h',
     'SizePrintfMacros.h',
     'Snprintf.h',
     'SplayTree.h',
     'TaggedAnonymousMemory.h',
new file mode 100644
--- /dev/null
+++ b/mfbt/tests/TestSaturate.cpp
@@ -0,0 +1,215 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include <mozilla/Saturate.h>
+
+#include <mozilla/Assertions.h>
+#include <mozilla/NumericLimits.h>
+
+using mozilla::detail::Saturate;
+using mozilla::NumericLimits;
+
+#define A(a) MOZ_RELEASE_ASSERT(a, "Test \'" #a "\'  failed.")
+
+static const unsigned long sNumOps = 32;
+
+template<typename T>
+static T
+StartValue()
+{
+  // Specialize |StartValue| for the given type.
+  A(false);
+}
+
+template<>
+int8_t
+StartValue<int8_t>()
+{
+  return 0;
+}
+
+template<>
+int16_t
+StartValue<int16_t>()
+{
+  return 0;
+}
+
+template<>
+int32_t
+StartValue<int32_t>()
+{
+  return 0;
+}
+
+template<>
+uint8_t
+StartValue<uint8_t>()
+{
+  // Picking a value near middle of uint8_t's range.
+  return static_cast<uint8_t>(NumericLimits<int8_t>::max());
+}
+
+template<>
+uint16_t
+StartValue<uint16_t>()
+{
+  // Picking a value near middle of uint16_t's range.
+  return static_cast<uint8_t>(NumericLimits<int16_t>::max());
+}
+
+template<>
+uint32_t
+StartValue<uint32_t>()
+{
+  // Picking a value near middle of uint32_t's range.
+  return static_cast<uint8_t>(NumericLimits<int32_t>::max());
+}
+
+// Add
+//
+
+template<typename T>
+static void
+TestPrefixIncr()
+{
+  T value = StartValue<T>();
+  Saturate<T> satValue(value);
+
+  for (T i = 0; i < static_cast<T>(sNumOps); ++i) {
+    A(++value == ++satValue);
+  }
+}
+
+template<typename T>
+static void
+TestPostfixIncr()
+{
+  T value = StartValue<T>();
+  Saturate<T> satValue(value);
+
+  for (T i = 0; i < static_cast<T>(sNumOps); ++i) {
+    A(value++ == satValue++);
+  }
+}
+
+template<typename T>
+static void
+TestAdd()
+{
+  T value = StartValue<T>();
+  Saturate<T> satValue(value);
+
+  for (T i = 0; i < static_cast<T>(sNumOps); ++i) {
+    A((value + i) == (satValue + i));
+  }
+}
+
+// Subtract
+//
+
+template<typename T>
+static void
+TestPrefixDecr()
+{
+  T value = StartValue<T>();
+  Saturate<T> satValue(value);
+
+  for (T i = 0; i < static_cast<T>(sNumOps); ++i) {
+    A(--value == --satValue);
+  }
+}
+
+template<typename T>
+static void
+TestPostfixDecr()
+{
+  T value = StartValue<T>();
+  Saturate<T> satValue(value);
+
+  for (T i = 0; i < static_cast<T>(sNumOps); ++i) {
+    A(value-- == satValue--);
+  }
+}
+
+template<typename T>
+static void
+TestSub()
+{
+  T value = StartValue<T>();
+  Saturate<T> satValue(value);
+
+  for (T i = 0; i < static_cast<T>(sNumOps); ++i) {
+    A((value - i) == (satValue - i));
+  }
+}
+
+// Corner cases near bounds
+//
+
+template<typename T>
+static void
+TestUpperBound()
+{
+  Saturate<T> satValue(NumericLimits<T>::max());
+
+  A(--satValue == (NumericLimits<T>::max() - 1));
+  A(++satValue == (NumericLimits<T>::max()));
+  A(++satValue == (NumericLimits<T>::max())); // don't overflow here
+  A(++satValue == (NumericLimits<T>::max())); // don't overflow here
+  A(--satValue == (NumericLimits<T>::max() - 1)); // back at (max - 1)
+  A(--satValue == (NumericLimits<T>::max() - 2));
+}
+
+template<typename T>
+static void
+TestLowerBound()
+{
+  Saturate<T> satValue(NumericLimits<T>::min());
+
+  A(++satValue == (NumericLimits<T>::min() + 1));
+  A(--satValue == (NumericLimits<T>::min()));
+  A(--satValue == (NumericLimits<T>::min())); // don't overflow here
+  A(--satValue == (NumericLimits<T>::min())); // don't overflow here
+  A(++satValue == (NumericLimits<T>::min() + 1)); // back at (max + 1)
+  A(++satValue == (NumericLimits<T>::min() + 2));
+}
+
+// Framework
+//
+
+template<typename T>
+static void
+TestAll()
+{
+  // Assert that we don't accidently hit type's range limits in tests.
+  const T value = StartValue<T>();
+  A(NumericLimits<T>::min() + static_cast<T>(sNumOps) <= value);
+  A(NumericLimits<T>::max() - static_cast<T>(sNumOps) >= value);
+
+  TestPrefixIncr<T>();
+  TestPostfixIncr<T>();
+  TestAdd<T>();
+
+  TestPrefixDecr<T>();
+  TestPostfixDecr<T>();
+  TestSub<T>();
+
+  TestUpperBound<T>();
+  TestLowerBound<T>();
+}
+
+int
+main()
+{
+  TestAll<int8_t>();
+  TestAll<int16_t>();
+  TestAll<int32_t>();
+  TestAll<uint8_t>();
+  TestAll<uint16_t>();
+  TestAll<uint32_t>();
+  return 0;
+}
--- a/mfbt/tests/moz.build
+++ b/mfbt/tests/moz.build
@@ -26,16 +26,17 @@ CppUnitTests([
     'TestLinkedList',
     'TestMacroArgs',
     'TestMacroForEach',
     'TestMathAlgorithms',
     'TestMaybe',
     'TestPair',
     'TestRefPtr',
     'TestRollingMean',
+    'TestSaturate',
     'TestScopeExit',
     'TestSegmentedVector',
     'TestSHA1',
     'TestSplayTree',
     'TestTemplateLib',
     'TestTuple',
     'TestTypedEnum',
     'TestTypeTraits',
--- a/testing/cppunittest.ini
+++ b/testing/cppunittest.ini
@@ -62,16 +62,17 @@ skip-if = os == 'b2g'  #Bug 1038197
 [TestPlainTextSerializer]
 skip-if = os == 'b2g' || os == 'android'  #Bug 919599
 [TestPoisonArea]
 skip-if = os == 'android' # Bug 1147630
 [TestRefPtr]
 [TestRollingMean]
 [TestSHA1]
 [TestSTSParser]
+[TestSaturate]
 [TestSplayTree]
 [TestStartupCache]
 skip-if = os == 'b2g' || os == 'android'  # Bug 929655
 support-files = TestStartupCacheTelemetry.js TestStartupCacheTelemetry.manifest
 [TestStringAPI]
 [TestSyncRunnable]
 [TestTArray]
 skip-if = os == 'b2g' || os == 'android'  # Bug 1054251, 1171296