1193600 - Add IsPowerOfTwo and Clamp to MFBT

Status: RESOLVED FIXED

(Core :: MFBT, defect)

Description

[Kelsey Gilbert [:jgilbert]]

Attachment: 0015-Add-IsPowerOfTwo-and-Clamp-to-mfbt-MathAlgorithms.h.patch

We use these a bunch in WebGL, and often end with with a couple different functions for them.

Let's just standardize them into MFBT.

Comment 1

[Jeff Walden [:Waldo]]

Comment on attachment 8646717 [details] [diff] [review]
0015-Add-IsPowerOfTwo-and-Clamp-to-mfbt-MathAlgorithms.h.patch

Review of attachment 8646717 [details] [diff] [review]:
-----------------------------------------------------------------

Needs some tests in the appropriate test file, or in TestMathAlgorithms.cpp if it doesn't exist yet -- for all the usual boundary cases, and for the cases where compiler warnings might rear.

::: mfbt/MathAlgorithms.h
@@ +504,5 @@
> + * Returns true if |x| is a power of two.
> + * Zero is not an integer power of two. (-Inf is not an integer)
> + */
> +inline bool
> +IsPowerOfTwo(size_t x)

Maybe preferable:

template<typename T>
inline bool
IsPowerOfTwo(T t)
{
  static_assert(mozilla::IsUnsigned<T>::value, "only unsigned types supported");
  return x && (x & (x - 1)) == 0;
}

so that use with signed values will fail to compile, not just convert into modulo possibly-nonsense.

@@ +512,5 @@
> +
> +template<typename T>
> +inline T
> +Clamp(const T aValue, const T aMin, const T aMax)
> +{

static_assert(mozilla::IsIntegral<T>::value, "only integral types supported");

Specifically, I'd really like to exclude floating point types here, because such users might or might not want to order -0/+0 here, and I'd rather not impose the cost on every user when only some need it.

If you want it specifically for that case (and that wouldn't surprise me), let's discuss Thursday when I'm back in the office.

@@ +515,5 @@
> +Clamp(const T aValue, const T aMin, const T aMax)
> +{
> +    if (aValue < aMin)
> +        return aMin;
> +    if (aMax < aValue)

This makes me worry/wonder about compilers that warn somewhat too aggressively about vacuous comparisons, should someone ever do Clamp(0u, 15u, unsigned(-1)), say -- unsigned(v) < 0u and unsigned(-1) < unsigned(v) always being false.  Convert these two comparisons to <= so that while < might be vacuously false, == is always possible and so the comparisons are never impossible.

Comment 2

[Kelsey Gilbert [:jgilbert]]

Attachment: 0002-Review-comments-and-add-tests.patch

Comment 3

[Jeff Walden [:Waldo]]

Comment on attachment 8655763 [details] [diff] [review]
0002-Review-comments-and-add-tests.patch

Review of attachment 8655763 [details] [diff] [review]:
-----------------------------------------------------------------

::: mfbt/MathAlgorithms.h
@@ +510,2 @@
>  {
> +    static_assert(IsUnsigned<T>::value, "IsPowerOfTwo requries unsigned values.");

requires, and remove the trailing "." at the end -- these are generally sentence fragments.

@@ +516,4 @@
>  inline T
>  Clamp(const T aValue, const T aMin, const T aMax)
>  {
> +    static_assert(IsIntegral<T>::value, "Clamp requries integral values.");

Same again here.

@@ +517,5 @@
>  Clamp(const T aValue, const T aMin, const T aMax)
>  {
> +    static_assert(IsIntegral<T>::value, "Clamp requries integral values.");
> +    MOZ_ASSERT(aMin <= aMax);
> +    // We require integral values so that we don't have to support weird floatisms.

static_assert(IsIntegral<T>::value,
                "Clamp accepts only integral types, so that it doesn't have to "
                "distinguish differently-signed zeroes (which users may or may "
                "not care to distinguish, likely at a perf cost) or to decide "
                "how to clamp NaN or a range with a NaN endpoint");

to be a little more precise.  And put a linebreak before the static_assert.  (This also lets you get rid of the comment -- generally a comment by a static_assert, or touching upon it, should move into the static_assert reason itself.)

::: mfbt/tests/TestMathAlgorithms.cpp
@@ +6,5 @@
> +
> +#include "mozilla/MathAlgorithms.h"
> +
> +using mozilla::IsPowerOfTwo;
> +using mozilla::Clamp;

Flip ordering to be alphabetical.

@@ +28,5 @@
> +  MOZ_RELEASE_ASSERT(!IsPowerOfTwo(uint8_t(UINT8_MAX/2 + 2)));  // 129
> +  MOZ_RELEASE_ASSERT(!IsPowerOfTwo(uint8_t(UINT8_MAX - 1)));    // 254
> +  MOZ_RELEASE_ASSERT(!IsPowerOfTwo(uint8_t(UINT8_MAX)));        // 255
> +
> +  MOZ_RELEASE_ASSERT(!IsPowerOfTwo(uint16_t(UINT16_MAX/2)));

// 32767
and similar comments after all these, and the 32/64-bit cases.

That said, it might perhaps be better to use

UINT8_C(127)
UINT16_C(65535)

and so on for these, to be clearer.  But then the boundary-checking is less obvious, so maybe stick with what you have, with the added comments, I guess.

@@ +65,5 @@
> +  MOZ_RELEASE_ASSERT(Clamp(1, 1, 3) == 1);
> +  MOZ_RELEASE_ASSERT(Clamp(2, 1, 3) == 2);
> +  MOZ_RELEASE_ASSERT(Clamp(3, 1, 3) == 3);
> +  MOZ_RELEASE_ASSERT(Clamp(4, 1, 3) == 3);
> +  MOZ_RELEASE_ASSERT(Clamp(5, 1, 3) == 3);

Add

  MOZ_RELEASE_ASSERT(Clamp(uint8_t(-1), uint8_t(0), uint8_t(-1)) == uint8_t(-1));
  MOZ_RELEASE_ASSERT(Clamp(uint8_t(0), uint8_t(0), uint8_t(-1)) == uint8_t(0));

to verify type-boundary conditions for an unsigned type, and add

  MOZ_RELEASE_ASSERT(Clamp(int8_t(INT8_MIN), int8_t(INT8_MIN), int8_t(INT8_MAX)) == int8_t(INT8_MIN));
  MOZ_RELEASE_ASSERT(Clamp(int8_t(INT8_MIN), int8_t(0), int8_t(INT8_MAX)) == int8_t(0));
  MOZ_RELEASE_ASSERT(Clamp(int8_t(INT8_MAX), int8_t(INT8_MIN), int8_t(INT8_MAX)) == int8_t(INT8_MAX));
  MOZ_RELEASE_ASSERT(Clamp(int8_t(INT8_MAX), int8_t(INT8_MIN), int8_t(0)) == int8_t(0));

to verify them for a signed type.

Comment 4

[Jeff Walden [:Waldo]]

Comment on attachment 8646717 [details] [diff] [review]
0015-Add-IsPowerOfTwo-and-Clamp-to-mfbt-MathAlgorithms.h.patch

Review of attachment 8646717 [details] [diff] [review]:
-----------------------------------------------------------------

r=me with the other patch's changes folded in, and with comments addressed.

Comment 5

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/dff32fe11db9

Comment 6

[Mats Palmgren (inactive)]

Should we remove "clamped" in xpcom/base/nsAlgorithm.h and change consumers
to use "Clamp" instead?

Comment 7

[Jeff Walden [:Waldo]]

Yes, I think so.  Note that Clamp doesn't accept floating-point types, so you might hit cases that can't just be converted.  We'll have to add new methods for that, and we'll have to decide how to handle -0/+0/NaN edge cases (and their perf) not present in simple integral clamping.

Comment 8

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/dff32fe11db9