Let RTC_[D]CHECK_op accept arguments of different signedness

webrtc/base/safe_compare.h

+/*
+ *  Copyright 2016 The WebRTC Project Authors. All rights reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+// This file defines six functions:
+//
+//   rtc::safe_cmp::Eq  // ==
+//   rtc::safe_cmp::Ne  // !=
+//   rtc::safe_cmp::Lt  // <
+//   rtc::safe_cmp::Le  // <=
+//   rtc::safe_cmp::Gt  // >
+//   rtc::safe_cmp::Ge  // >=
+//
+// They each accept two arguments of arbitrary types, and in almost all cases,
+// they simply call the appropriate comparison operator. However, if both
+// arguments are integers, they don't compare them using C++'s quirky rules,
+// but instead adhere to the true mathematical definitions. It is as if the
+// arguments were first converted to infinite-range signed integers, and then
+// compared, although of course nothing expensive like that actually takes
+// place. In practice, for signed/signed and unsigned/unsigned comparisons and
+// some mixed-signed comparisons with a compile-time constant, the overhead is
+// zero; in the remaining cases, it is just a few machine instructions (no

[ossu, 2016/10/31 16:44:57]

I bet the ?: operator could turn into a branch on one platform or other, at some
level of (non-)optimization.

[kwiberg-webrtc, 2016/10/31 21:32:26]

Probably. I didn't even try to look at unoptimized assembly, because it's always
so hard to read due to the redundant work being done all over the place.

I'd say it's a safe bet that it'll work as advertised when compiling with
optimizations, though. Compilers are good at replacing conditionals with bit
twiddling (probably because it's a big gain), and that's exactly what we're
asking for here.

[ossu, 2016/11/01 15:36:57]

Not sure if it matters, but perhaps turning the ?: into && and || would ensure
it never branches, i.e.:
(a < 0 && Op::Op(-1, 0)) || Op::Op(safe_cmp_impl::MakeUnsigned(a), b);

[kwiberg-webrtc, 2016/11/01 16:14:06]

No, this is the sort of transformation the compiler can do in its sleep. You and
me, on the other hand, are sure to slip up and write bugs if we try this... (I'm
exaggerating, but not by a lot; this version of the code is harder to read than
the ?: version, so bugs have more complexity to hide behind.)

[ossu, 2016/11/01 16:48:07]

You think? Yeah, maybe. Granted, if the compiler isn't making any attempts to
optimize, the && and || version of the code would still lead to the same
problem: it would only allow one of the Op::Ops to get called and I don't think
that can be avoided without branches.

I'll just tear down this bike shed and let you on your way.

+// branches).
+
+#ifndef WEBRTC_BASE_SAFE_COMPARE_H_
+#define WEBRTC_BASE_SAFE_COMPARE_H_
+
+#include <stddef.h>
+#include <stdint.h>
+
+#include <type_traits>
+#include <utility>
+
+namespace rtc {
+namespace safe_cmp {
+
+namespace safe_cmp_impl {
+
+template <size_t N>
+struct LargerIntImpl : std::false_type {};
+template <>
+struct LargerIntImpl<sizeof(int8_t)> : std::true_type {
+  using type = int16_t;
+};
+template <>
+struct LargerIntImpl<sizeof(int16_t)> : std::true_type {
+  using type = int32_t;
+};
+template <>
+struct LargerIntImpl<sizeof(int32_t)> : std::true_type {
+  using type = int64_t;
+};
+
+// LargerInt<T1, T2>::value is true iff there's a signed type that's larger
+// than T1 (and no larger than the larger of T2 and int*, for performance
+// reasons); and if there is such a type, LargerInt<T1, T2>::type is an alias
+// for it.
+template <typename T1, typename T2>
+struct LargerInt
+    : LargerIntImpl<sizeof(T1) < sizeof(T2) || sizeof(T1) < sizeof(int*)
+                        ? sizeof(T1)
+                        : 0> {};
+
+template <typename T>
+inline typename std::make_unsigned<T>::type MakeUnsigned(T a) {
+  return static_cast<typename std::make_unsigned<T>::type>(a);
+}
+
+// Overload for when both T1 and T2 have the same signedness.
+template <typename Op,
+          typename T1,
+          typename T2,
+          typename std::enable_if<std::is_signed<T1>::value ==
+                                  std::is_signed<T2>::value>::type* = nullptr>
+inline bool Cmp(T1 a, T2 b) {
+  return Op::Op(a, b);
+}
+
+// Overload for signed - unsigned comparison that can be promoted to a bigger
+// signed type.
+template <typename Op,
+          typename T1,
+          typename T2,
+          typename std::enable_if<std::is_signed<T1>::value &&
+                                  std::is_unsigned<T2>::value &&
+                                  LargerInt<T2, T1>::value>::type* = nullptr>
+inline bool Cmp(T1 a, T2 b) {
+  return Op::Op(a, static_cast<typename LargerInt<T2, T1>::type>(b));
+}
+
+// Overload for unsigned - signed comparison that can be promoted to a bigger
+// signed type.
+template <typename Op,
+          typename T1,
+          typename T2,
+          typename std::enable_if<std::is_unsigned<T1>::value &&
+                                  std::is_signed<T2>::value &&
+                                  LargerInt<T1, T2>::value>::type* = nullptr>
+inline bool Cmp(T1 a, T2 b) {
+  return Op::Op(static_cast<typename LargerInt<T1, T2>::type>(a), b);
+}
+
+// Overload for signed - unsigned comparison that can't be promoted to a bigger
+// signed type.
+template <typename Op,
+          typename T1,
+          typename T2,
+          typename std::enable_if<std::is_signed<T1>::value &&
+                                  std::is_unsigned<T2>::value &&
+                                  !LargerInt<T2, T1>::value>::type* = nullptr>
+inline bool Cmp(T1 a, T2 b) {
+  return a < 0 ? Op::Op(-1, 0) : Op::Op(safe_cmp_impl::MakeUnsigned(a), b);
+}
+
+// Overload for unsigned - signed comparison that can't be promoted to a bigger
+// signed type.
+template <typename Op,
+          typename T1,
+          typename T2,
+          typename std::enable_if<std::is_unsigned<T1>::value &&
+                                  std::is_signed<T2>::value &&
+                                  !LargerInt<T1, T2>::value>::type* = nullptr>
+inline bool Cmp(T1 a, T2 b) {
+  return b < 0 ? Op::Op(0, -1) : Op::Op(a, safe_cmp_impl::MakeUnsigned(b));

[ossu, 2016/11/01 15:36:57]

Isn't Op::Op(0, -1) a bad choice here if Op is supposed to work only with
unsigneds? Or does the Op::Op to the left of the colon resolve to a different
function than the Op::Op to the right of it.

Wouldn't 1, 0 (and 0, 1 in the Cmp above) be better?

[kwiberg-webrtc, 2016/11/01 16:14:06]

Op::Op<T1, T2> will accept any two types, and the compiler will dutifully
complain if we use types that differ in signedness. But -1 and 0 are both int,
so we're good. (I chose -1 and 0 because they're the canonical negative and
nonnegative integers, so it's easier to see what the code does that way IMO. But
0 and 1 would of course work too.)

[ossu, 2016/11/01 16:48:07]

Ah, right, yes. I somehow expected them to be typed based on T1 or something...
not sure why. Proceed.

+}
+
+#define RTC_SAFECMP_MAKE_OP(name, op)          \
+  struct name {                                \
+    template <typename T1, typename T2>        \
+    static constexpr bool Op(T1&& a, T2&& b) { \

[kwiberg-webrtc, 2016/10/31 09:16:01]

Should I perhaps take a and b by value instead?

[ossu, 2016/10/31 16:44:57]

I'd say const&. That's what comparison operators usually work on.

[kwiberg-webrtc, 2016/10/31 21:32:26]

Yes, but this is specifically for built-in integer types. We usually pass those
by value. (And as you can see, I consistently do so everywhere else.)

[ossu, 2016/11/01 15:36:57]

Ah, right. Yes, pass by value instead!

[kwiberg-webrtc, 2016/11/01 16:14:06]

Done.

+      return a op b;                           \
+    }                                          \
+  };
+RTC_SAFECMP_MAKE_OP(EqOp, ==)
+RTC_SAFECMP_MAKE_OP(NeOp, !=)
+RTC_SAFECMP_MAKE_OP(LtOp, <)
+RTC_SAFECMP_MAKE_OP(LeOp, <=)
+RTC_SAFECMP_MAKE_OP(GtOp, >)
+RTC_SAFECMP_MAKE_OP(GeOp, >=)
+#undef RTC_SAFECMP_MAKE_OP
+
+}  // namespace safe_cmp_impl
+
+#define RTC_SAFECMP_MAKE_FUN(name)                                             \

[ossu, 2016/10/31 16:44:57]

I like fun! Make more fun! :D

[kwiberg-webrtc, 2016/10/31 21:32:26]

Acknowledged.

+  template <                                                                   \
+      typename T1, typename T2,                                                \
+      typename std::enable_if<                                                 \
+          std::is_integral<typename std::remove_reference<T1>::type>::value && \
+          std::is_integral<typename std::remove_reference<T2>::type>::value>:: \
+          type* = nullptr>                                                     \
+  inline bool name(T1 a, T2 b) {                                               \
+    return safe_cmp_impl::Cmp<safe_cmp_impl::name##Op>(a, b);                  \
+  }                                                                            \
+  template <typename T1, typename T2,                                          \
+            typename std::enable_if<                                           \
+                !std::is_integral<                                             \
+                    typename std::remove_reference<T1>::type>::value ||        \
+                !std::is_integral<typename std::remove_reference<T2>::type>::  \
+                    value>::type* = nullptr>                                   \
+  inline bool name(T1&& a, T2&& b) {                                           \
+    return safe_cmp_impl::name##Op::Op(a, b);                                  \
+  }
+RTC_SAFECMP_MAKE_FUN(Eq)
+RTC_SAFECMP_MAKE_FUN(Ne)
+RTC_SAFECMP_MAKE_FUN(Lt)
+RTC_SAFECMP_MAKE_FUN(Le)
+RTC_SAFECMP_MAKE_FUN(Gt)
+RTC_SAFECMP_MAKE_FUN(Ge)
+#undef RTC_SAFECMP_MAKE_FUN
+
+}  // namespace safe_cmp
+}  // namespace rtc
+
+#endif  // WEBRTC_BASE_SAFE_COMPARE_H_