Bug 1394995 - RollingNumber - r?froydnj,jwwang draft
authorGerald Squelart <gsquelart@mozilla.com>
Fri, 15 Sep 2017 14:31:13 +1200
changeset 668848 60c262faa90adfeae430adebfeb1a992e76acec7
parent 668847 75ac112bb7d606b6c12e1d614fdcfe12d2da80d2
child 668849 15fb61d62f0615c922cab6f1483e32a0cc941b95
push id81138
push usergsquelart@mozilla.com
push dateFri, 22 Sep 2017 03:33:12 +0000
reviewersfroydnj, jwwang
bugs1394995
milestone58.0a1
Bug 1394995 - RollingNumber - r?froydnj,jwwang Unsigned-number value-class with modified comparison operators that keep ordering consistent across overflows. I.e., numbers before the overflow (close to the maximum) will be considered smaller than numbers after the overflow (close to 0). (Note that such comparisons break down for numbers separated by more than half the type range.) MozReview-Commit-ID: 1hdK2JknlqZ
dom/media/doctor/RollingNumber.h
dom/media/doctor/gtest/TestRollingNumber.cpp
dom/media/doctor/gtest/moz.build
dom/media/doctor/moz.build
new file mode 100644
--- /dev/null
+++ b/dom/media/doctor/RollingNumber.h
@@ -0,0 +1,151 @@
+/* -*- 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/. */
+
+#ifndef mozilla_RollingNumber_h_
+#define mozilla_RollingNumber_h_
+
+#include "mozilla/Attributes.h"
+#include <limits>
+
+namespace mozilla {
+
+// Unsigned number suited to index elements in a never-ending queue, as
+// order-comparison behaves nicely around the overflow.
+//
+// Additive operators work the same as for the underlying value type, but
+// expect "small" jumps, as should normally happen when manipulating indices.
+//
+// Comparison functions are different, they keep the ordering based on the
+// distance between numbers, modulo the value type range:
+// If the distance is less than half the range of the value type, the usual
+// ordering stays.
+// 0 < 1, 2^23 < 2^24
+// However if the distance is more than half the range, we assume that we are
+// continuing along the queue, and therefore consider the smaller number to
+// actually be greater!
+// uint(-1) < 0.
+template<typename T>
+class RollingNumber
+{
+  static_assert(!std::numeric_limits<T>::is_signed,
+                "RollingNumber only accepts unsigned number types");
+
+public:
+  using ValueType = T;
+
+  RollingNumber()
+    : mIndex(0)
+  {
+  }
+
+  explicit RollingNumber(ValueType aIndex)
+    : mIndex(aIndex)
+  {
+  }
+
+  RollingNumber(const RollingNumber&) = default;
+  RollingNumber& operator=(const RollingNumber&) = default;
+
+  ValueType Value() const { return mIndex; }
+
+  // Normal increments/decrements.
+
+  RollingNumber& operator++()
+  {
+    ++mIndex;
+    return *this;
+  }
+
+  RollingNumber operator++(int) { return RollingNumber{ mIndex++ }; }
+
+  RollingNumber& operator--()
+  {
+    --mIndex;
+    return *this;
+  }
+
+  RollingNumber operator--(int) { return RollingNumber{ mIndex-- }; }
+
+  RollingNumber operator+(ValueType aIncrement) const
+  {
+    // Don't allow jumps across more than half the type range.
+    MOZ_ASSERT(aIncrement <= MidWay);
+    return RollingNumber(Value() + aIncrement);
+  }
+
+  RollingNumber& operator+=(ValueType aIncrement)
+  {
+    // Don't allow jumps across more than half the type range.
+    MOZ_ASSERT(aIncrement <= MidWay);
+    mIndex += aIncrement;
+    return *this;
+  }
+
+  RollingNumber operator-(ValueType aDecrement) const
+  {
+    // Don't allow jumps across more than half the type range.
+    MOZ_ASSERT(aDecrement <= MidWay);
+    return RollingNumber(Value() - aDecrement);
+  }
+
+  RollingNumber& operator-=(ValueType aDecrement)
+  {
+    // Don't allow jumps across more than half the type range.
+    MOZ_ASSERT(aDecrement <= MidWay);
+    mIndex -= aDecrement;
+    return *this;
+  }
+
+  // Distance between numbers.
+
+  ValueType operator-(RollingNumber aOther) const
+  {
+    // Don't allow differences of more than half the type range.
+    MOZ_ASSERT(Value() - aOther.Value() <= MidWay);
+    return Value() - aOther.Value();
+  }
+
+  // Normal (in)equality operators.
+
+  bool operator==(RollingNumber aOther) const
+  {
+    return Value() == aOther.Value();
+  }
+  bool operator!=(RollingNumber aOther) const
+  {
+    return Value() != aOther.Value();
+  }
+
+  // Modified comparison operators.
+
+  bool operator<(RollingNumber aOther) const
+  {
+    return ValueType(Value() - aOther.Value()) > MidWay;
+  }
+
+  bool operator<=(RollingNumber aOther) const
+  {
+    return ValueType(aOther.Value() - Value()) <= MidWay;
+  }
+
+  bool operator>=(RollingNumber aOther) const
+  {
+    return ValueType(Value() - aOther.Value()) <= MidWay;
+  }
+
+  bool operator>(RollingNumber aOther) const
+  {
+    return ValueType(aOther.Value() - Value()) > MidWay;
+  }
+
+private:
+  static const T MidWay = std::numeric_limits<T>::max() / 2;
+  ValueType mIndex;
+};
+
+} // namespace mozilla
+
+#endif // mozilla_RollingNumber_h_
new file mode 100644
--- /dev/null
+++ b/dom/media/doctor/gtest/TestRollingNumber.cpp
@@ -0,0 +1,141 @@
+/* -*- 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 "RollingNumber.h"
+
+#include "mozilla/Assertions.h"
+#include "mozilla/TypeTraits.h"
+
+#include <cstdint>
+#include <gtest/gtest.h>
+
+using RN8 = mozilla::RollingNumber<uint8_t>;
+
+TEST(RollingNumber, Value)
+{
+  // Value type should reflect template argument.
+  static_assert(mozilla::IsSame<RN8::ValueType, uint8_t>::value, "");
+
+  // Default init to 0.
+  const RN8 n;
+  // Access through Value().
+  EXPECT_EQ(0, n.Value());
+  // Implicit conversion constructor: 0 -> RollingNumber{0} as needed by
+  // operator==.
+  EXPECT_EQ(0, n.Value());
+
+  // Conversion constructor.
+  RN8 n42{ 42 };
+  EXPECT_EQ(42, n42.Value());
+
+  // Copy Constructor.
+  RN8 n42Copied{ n42 };
+  EXPECT_EQ(42, n42Copied.Value());
+
+  // Assignment construction.
+  RN8 n42Assigned = n42;
+  EXPECT_EQ(42, n42Assigned.Value());
+
+  // Assignment.
+  n42 = n;
+  EXPECT_EQ(0, n42.Value());
+}
+
+TEST(RollingNumber, Operations)
+{
+  RN8 n;
+  EXPECT_EQ(0, n.Value());
+
+  RN8 nPreInc = ++n;
+  EXPECT_EQ(1, n.Value());
+  EXPECT_EQ(1, nPreInc.Value());
+
+  RN8 nPostInc = n++;
+  EXPECT_EQ(2, n.Value());
+  EXPECT_EQ(1, nPostInc.Value());
+
+  RN8 nPreDec = --n;
+  EXPECT_EQ(1, n.Value());
+  EXPECT_EQ(1, nPreDec.Value());
+
+  RN8 nPostDec = n--;
+  EXPECT_EQ(0, n.Value());
+  EXPECT_EQ(1, nPostDec.Value());
+
+  RN8 nPlus = n + 10;
+  EXPECT_EQ(0, n.Value());
+  EXPECT_EQ(10, nPlus.Value());
+
+  n += 20;
+  EXPECT_EQ(20, n.Value());
+
+  RN8 nMinus = n - 2;
+  EXPECT_EQ(20, n.Value());
+  EXPECT_EQ(18, nMinus.Value());
+
+  n -= 5;
+  EXPECT_EQ(15, n.Value());
+
+  uint8_t diff = nMinus - n;
+  EXPECT_EQ(3, diff);
+
+  // Overflows.
+  n = RN8(0);
+  EXPECT_EQ(0, n.Value());
+  n--;
+  EXPECT_EQ(255, n.Value());
+  n++;
+  EXPECT_EQ(0, n.Value());
+  n -= 10;
+  EXPECT_EQ(246, n.Value());
+  n += 20;
+  EXPECT_EQ(10, n.Value());
+}
+
+TEST(RollingNumber, Comparisons)
+{
+  uint8_t i = 0;
+  do {
+    RN8 n{ i };
+    EXPECT_EQ(i, n.Value());
+    EXPECT_TRUE(n == n);
+    EXPECT_FALSE(n != n);
+    EXPECT_FALSE(n < n);
+    EXPECT_TRUE(n <= n);
+    EXPECT_FALSE(n > n);
+    EXPECT_TRUE(n >= n);
+
+    RN8 same = n;
+    EXPECT_TRUE(n == same);
+    EXPECT_FALSE(n != same);
+    EXPECT_FALSE(n < same);
+    EXPECT_TRUE(n <= same);
+    EXPECT_FALSE(n > same);
+    EXPECT_TRUE(n >= same);
+
+    for (uint8_t add = 1; add < 128; ++add) {
+      RN8 bigger = n + add;
+      EXPECT_FALSE(n == bigger);
+      EXPECT_TRUE(n != bigger);
+      EXPECT_TRUE(n < bigger);
+      EXPECT_TRUE(n <= bigger);
+      EXPECT_FALSE(n > bigger);
+      EXPECT_FALSE(n >= bigger);
+    }
+
+    for (uint8_t sub = 1; sub < 128; ++sub) {
+      RN8 smaller = n - sub;
+      EXPECT_FALSE(n == smaller);
+      EXPECT_TRUE(n != smaller);
+      EXPECT_FALSE(n < smaller);
+      EXPECT_FALSE(n <= smaller);
+      EXPECT_TRUE(n > smaller);
+      EXPECT_TRUE(n >= smaller);
+    }
+
+    ++i;
+  } while (i != 0);
+}
new file mode 100644
--- /dev/null
+++ b/dom/media/doctor/gtest/moz.build
@@ -0,0 +1,20 @@
+# -*- Mode: python; indent-tabs-mode: nil; tab-width: 40 -*-
+# vim: set filetype=python:
+# 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/.
+
+UNIFIED_SOURCES += [
+    'TestRollingNumber.cpp',
+]
+
+include('/ipc/chromium/chromium-config.mozbuild')
+
+LOCAL_INCLUDES += [
+    '/dom/media/doctor',
+]
+
+FINAL_LIBRARY = 'xul-gtest'
+
+if CONFIG['GNU_CXX']:
+    CXXFLAGS += ['-Wno-error=shadow']
--- a/dom/media/doctor/moz.build
+++ b/dom/media/doctor/moz.build
@@ -1,14 +1,18 @@
 # -*- Mode: python; indent-tabs-mode: nil; tab-width: 40 -*-
 # vim: set filetype=python:
 # 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/.
 
+TEST_DIRS += [
+    'gtest',
+]
+
 EXPORTS += [
     'DecoderDoctorDiagnostics.h',
 ]
 
 UNIFIED_SOURCES += [
     'DecoderDoctorDiagnostics.cpp',
 ]