1441657 - Implement mfbt/WrappingOperations.h for wraparound math operations and conversions

Status: RESOLVED FIXED

(Core :: MFBT, enhancement)

Description

[Jeff Walden [:Waldo]]

If we're to get a handle on various forms of signed overflow, we probably will have to have forms of them that wrap *safely*.  This header will be where those can be defined.

Comment 1

[Jeff Walden [:Waldo]]

Attachment: Create a new mozilla/WrappingOperations.h header, move WrapToSigned to it

Comment 2

[Jeff Walden [:Waldo]]

Attachment: Implement mozilla::WrappingMultiply

If you can point at other depends-on-wrapping places that demand implementation of the other basic math operations, I'd love to know so they can be implemented and people can be pointed at them.  In advance of that, tho, it's hard to justify just implementing without identified users.

Comment 3

[Jeff Walden [:Waldo]]

Attachment: Implement mozilla::WrappingMultiply

Let's add a few more uses/remove a couple blacklist entries.

Comment 4

[Jeff Walden [:Waldo]]

Hrm:

https://developercommunity.visualstudio.com/content/problem/55671/c4307-issued-for-unsigned.html

Might be the patch needs to be augmented with some MSVC-specific #pragmas to disable that warning in WrappingMultiply.  Or then again, https://stackoverflow.com/questions/37658794/integer-constant-overflow-warning-in-constexpr claims even that doesn't work.  Will do some more futzing.

Comment 5

[Nathan Froyd [:froydnj]]

Comment on attachment 8954510 [details] [diff] [review]
Create a new mozilla/WrappingOperations.h header, move WrapToSigned to it

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

::: js/src/jsmath.cpp
@@ -490,5 @@
>  
>      uint32_t product = a * b;
> -    res.setInt32(product > INT32_MAX
> -                 ? int32_t(INT32_MIN + (product - INT32_MAX - 1))
> -                 : int32_t(product));

o.O

Comment 6

[Nathan Froyd [:froydnj]]

Comment on attachment 8954642 [details] [diff] [review]
Implement mozilla::WrappingMultiply

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

r=me with some changes below.

::: mfbt/WrappingOperations.h
@@ +125,5 @@
> +} // namespace detail
> +
> +/**
> + * Multiply two integers of the same type, and return that result converted to
> + * that type using wraparound semantics.

Do we want to say something here about "this is what you get normally with unsigned types, but this operator both makes it more explicit that this behavior is expected and desired, and also prevents ubsan from complaining about it" (as well as handling the signed integer case with aplomb)?  It's not immediately obvious to me why you would want to use this otherwise.

Maybe such a comment belongs at the head of WrappingOperations.h instead?  Not sure.

@@ +131,5 @@
> + * For N-bit unsigned integer types, this is equivalent to multiplying the two
> + * numbers, then taking the result mod 2**N:
> + *
> + *   WrappingMultiply(uint8_t(16), uint8_t(24)) is 128 (384 mod 2**8);
> + *   WrappingMultiply(int32_t(16), int32_t(255)) is 240 (4080 mod 2*32);

This example refers to `mod 2*32`, but the above comment refers to `mod 2**N`; it's not really obvious to me where the 2*32 comes in...  Did you mean `mod 2**8` here, and to cast the constants to `uint8_t`?

Comment 7

[Jeff Walden [:Waldo]]

MSVC #pragmas don't work, unfortunately, I guess because constexpr causes the warnings to be emitted *for call sites* and pragmas can't touch that.  So I removed all the constexpr and used MOZ_RELEASE_ASSERT for tests.

(In reply to Nathan Froyd [:froydnj] from comment #6)
> Do we want to say something here about "this is what you get normally with
> unsigned types, but this operator both makes it more explicit that this
> behavior is expected and desired, and also prevents ubsan from complaining
> about it" (as well as handling the signed integer case with aplomb)?  It's
> not immediately obvious to me why you would want to use this otherwise.

Seems fair.

There is one additional reason to use this function: uint16_t*uint16_t can invoke undefined behavior, *if* the operands are big enough that when promoted to |int|, the now-signed multiplication overflows |int|.  See http://kqueue.org/blog/2013/09/17/cltq/ for more.  (The same is instead possible with uint32_t if |int| is a signed 64-bit integer, although I'm not sure we compile with anything like that now.)

I added a bunch of comments along these lines and others to lay out the reasons for the function and why to use it.

> This example refers to `mod 2*32`, but the above comment refers to `mod
> 2**N`; it's not really obvious to me where the 2*32 comes in...  Did you
> mean `mod 2**8` here, and to cast the constants to `uint8_t`?

Yeah, this is a bit off.  I've beefed up the examples here and fixed the boogs in them.

Will probably land the whole thing tomorrow after a try-run today.

Comment 8

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/bc01e52c16d7
Create a new mozilla/WrappingOperations.h header to contain implementations of common math operations with well-defined wraparound semantics.  r=froydnj
https://hg.mozilla.org/integration/mozilla-inbound/rev/cf32e82edfb7
Implement mozilla::WrappingMultiply.  r=froydnj

Comment 9

[Andreea Pavel [:apavel]]

https://hg.mozilla.org/mozilla-central/rev/bc01e52c16d7
https://hg.mozilla.org/mozilla-central/rev/cf32e82edfb7

Comment 10

[Jeff Walden [:Waldo]]

I filed https://developercommunity.visualstudio.com/content/problem/211134/unsigned-integer-overflows-in-constexpr-functionsa.html as an MSVC bug on the unsigned overflow warning.  Will note it in comments in WrappingOperations.h either in passing at some point, or as part of a future patch.