prototype Math.imul

RESOLVED FIXED in mozilla20

Status

()

Core
JavaScript Engine
RESOLVED FIXED
5 years ago
4 years ago

People

(Reporter: dherman, Assigned: evilpie)

Tracking

({dev-doc-complete})

unspecified
mozilla20
x86
Mac OS X
dev-doc-complete
Points:
---
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [js:p2], URL)

Attachments

(1 attachment, 2 obsolete attachments)

(Reporter)

Description

5 years ago
Emscripten and similar code generators really want an optimized and concise way to do 32-bit integer multiplication. I have proposed Math.imul to es-discuss:

https://mail.mozilla.org/pipermail/es-discuss/2012-November/026126.html

This bug is for prototyping this in the JS engine.

Dave
(Reporter)

Updated

5 years ago
(Reporter)

Comment 1

5 years ago
Concretely, the semantics of imul is:

    imul(a, b) = ToInt32((ToUint32(a) x ToUint32(b)) mod 2^32)

where "x" is the "true" mathematical integer multiplication.

Or, more intuitively, the semantics is "coerce to int and do what C does."

Dave
(Assignee)

Updated

5 years ago
Assignee: general → evilpies

Comment 2

5 years ago
Wow, already have an assignee!
(Assignee)

Comment 3

5 years ago
Created attachment 677895 [details] [diff] [review]
v1

Are there any other interesting values to test with (probably yes)? I assumed that everything below < 2 args produces 0, because (undefined >>> 0) == 0.

I am going to add JIT support for Ion soon, but it looks like this doesn't really want to implemented in terms of MMul (the normal multiplication operator).
Attachment #677895 - Flags: review?(jwalden+bmo)
(Assignee)

Updated

5 years ago
Attachment #677895 - Flags: review?(jwalden+bmo)
(Assignee)

Comment 4

5 years ago
Created attachment 677908 [details] [diff] [review]
v1 with tests

Yes the tests actually exists. Currently running through try: https://tbpl.mozilla.org/?tree=Try&rev=2fc501518375.
for (let [x, y, z] of table)
    assertEq(Math.imul(x, y), z);
(Assignee)

Comment 6

5 years ago
(In reply to Jason Orendorff [:jorendorff] from comment #5)
> for (let [x, y, z] of table)
>     assertEq(Math.imul(x, y), z);
This aborts Ion compilation at the moment.
(Assignee)

Comment 7

5 years ago
Comment on attachment 677908 [details] [diff] [review]
v1 with tests

Actually why not. Finishing the ionmonkey patch is going to take me a few more days.
Attachment #677908 - Flags: review?(jwalden+bmo)
Comment on attachment 677908 [details] [diff] [review]
v1 with tests

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

r- until the various should-be questions are addressed -- rest is all trivial style changes or whatever.

dherman, should imul do a ToUint32 on the first argument if only a single argument is provided?  Or should it short-circuit to returning 0?  The spelled-out semantics here don't break it down step-by-step enough to say (and ideally they'd be clearer about the ordering of ToUint32 on the two arguments).  Any chance we could get an exact, step-by-step algorithm here, and be sure semantics for the edges considered here actually have been considered and deliberately chosen?

::: js/src/jit-test/tests/basic/mathImul.js
@@ +14,5 @@
> +	[0xffffffff, 0xffffffff, 1],
> +	[0xffffffff, -0xffffffff, -1],
> +	[0xffffffff, 0xfffffffe, 2],
> +	[0xffffffff, -0xfffffffe, -2],
> +

A random smattering of other tests I'd add here, in some vaguely logical place for each:

[0x10000, 0x10000, 0]
[-0, 0, 0]
[0, -0, 0]
[-1, -0, 0]
[1, -0, 0]
[{}, [], 0]
[[], {}, 0]

And a one-off test for Math.imul({ valueOf: function() { throw "ha ha ha"; } });.

@@ +28,5 @@
> +assertEq(Math.imul(100), 0);
> +assertEq(Math.imul(NaN, 100), 0);
> +assertEq(Math.imul(NaN, NaN), 0);
> +assertEq(Math.imul(5, Infinity), 0);
> +

A one-off test for this is needed, too:

var order = [];
assertEq(Math.imul({ valueOf: function() { order.push("first"); return 0; } },
                   { valueOf: function() { order.push("second"); return 0; } }),
         0);
assertEq(order[0], "first");
assertEq(order[1], "second");

Note that if the result of the first-performed ToUint32 is 0, we still need to ToUint32 the second one in case it has side effects or throws.  So we should probably have this as well:

var seen = [];
try
{
  Math.imul({ valueOf: function() { seen.push("one"); return 17; } },
            { valueOf: function() { throw "abort!"; } });
  assertEq(true, false, "no error thrown");
}
catch (e)
{
  assertEq(e, "abort!", "should have thrown partway through, instead threw " + e);
}
assertEq(seen.length, 1);
assertEq(seen[0], "one");

@@ +30,5 @@
> +assertEq(Math.imul(NaN, NaN), 0);
> +assertEq(Math.imul(5, Infinity), 0);
> +
> +for (var i = 0; i < table.length; i++) {
> +	assertEq(Math.imul(table[i][0], table[i][1]), table[i][2]);

A tab character, really?  :-P

::: js/src/jsmath.cpp
@@ +335,5 @@
> +
> +    if (args.length() < 2) {
> +        args.rval().setInt32(0);
> +        return true;
> +    }

What should be the result of this?

  Math.imul({ valueOf: function() { throw "ha ha ha"; } });

dherman?  Having that throw is consistent with everything else in the language, so that seems desirable to me, no matter that it makes this a bit messy.  :-\

@@ +341,5 @@
> +    uint32_t a, b;
> +    if (!ToUint32(cx, args[0], &a) || !ToUint32(cx, args[1], &b))
> +        return false;
> +
> +    args.rval().setInt32(static_cast<int32_t>(a * b));

You ignore C++ undefined behavior at your peril when you assign a uint32_t that doesn't fit in an int32_t, into an int32_t.  This is a little messy but I think fixes it:

    uint32_t product = a * b;
    args.rval().setInt32(product > INT32_MAX
                         ? int32_t(INT32_MIN + (product - INT32_MAX))
                         : int32_t(product));
Attachment #677908 - Flags: review?(jwalden+bmo)
Attachment #677908 - Flags: review-
Attachment #677908 - Flags: feedback?(dherman)
(Assignee)

Comment 9

5 years ago
Created attachment 685707 [details] [diff] [review]
v2

Fixed all the comments. Still waiting on feedback from dherman.
Attachment #677895 - Attachment is obsolete: true
Attachment #677908 - Attachment is obsolete: true
Attachment #677908 - Flags: feedback?(dherman)
Flags: needinfo?(dherman)
(Reporter)

Comment 10

5 years ago
> dherman, should imul do a ToUint32 on the first argument if only a single
> argument is provided?  Or should it short-circuit to returning 0?

Let's avoid special short-circuiting cases, since conceptually it should be considered a set of coercions wrapping a pure (int x int) -> int operation.

> The spelled-out semantics here don't break it down step-by-step enough to say
> (and ideally they'd be clearer about the ordering of ToUint32 on the two
> arguments).

The semantics should perform ToUint32 to each of the first two arguments (using `undefined` as the value to pass to ToUint32 if the argument is not provided), in left-to-right order -- this is consistent with the other Math functions, which all perform their ToNumber coercions in left-to-right order. If either one of the coercions throws, the entire operation throws.

> Any chance we could get an exact, step-by-step algorithm here,
> and be sure semantics for the edges considered here actually have been
> considered and deliberately chosen?

That's about as much step-by-step instruction as you get from any of the other parts of the spec for Math functions. Perform the coercions in left-to-right order, then if neither one throws, do the mathematical operation.

> What should be the result of this?
> 
>   Math.imul({ valueOf: function() { throw "ha ha ha"; } });
> 
> dherman?  Having that throw is consistent with everything else in the
> language, so that seems desirable to me, no matter that it makes this a bit
> messy.  :-\

Yes, it throws. This isn't spelled out in ES5:

    http://ecma-international.org/ecma-262/5.1/#sec-15.8.2

but the latest edition of Allen's draft ES6 does spell it out explicitly. If either coercion fails with an abrupt completion, then the operation is canceled and the abrupt completion becomes the completion of the entire operation.

Dave
Flags: needinfo?(dherman)
Whiteboard: [js:p2]
(Assignee)

Comment 11

4 years ago
Comment on attachment 685707 [details] [diff] [review]
v2

Thank you for answering these questions dherman. Looks like Waldo predicted the right semantics, and thus this patch should be okay.
Attachment #685707 - Flags: review?(jwalden+bmo)
Comment on attachment 685707 [details] [diff] [review]
v2

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

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

Why not setNumber(uint32_t)?
Comment on attachment 685707 [details] [diff] [review]
v2

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

::: js/src/jit-test/tests/basic/mathImul.js
@@ +31,5 @@
> +    [3.4, 6, 18]
> +];
> +
> +try {
> +    assertEq(Math.imul({ valueOf: function() { throw "ha ha ha"; } }, 0));

Remove the assertEq on this line, since it's actively misleading about what this Math.imul() is expected to do until you read the subsequent line.

@@ +67,5 @@
> +
> +for (var i = 0; i < table.length; i++) {
> +    print(table[i][0] + " * " + table[i][1])
> +    assertEq(Math.imul(table[i][0], table[i][1]), table[i][2]);
> +}

Any reason not to repeat this loop, but switching the order of the arguments to Math.imul?  All the entries should be effect-free and so perfectly commutative, looks like.

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

setNumber(uint32_t) isn't what this does -- this does setInt32(ToInt32(product)), just that the only ToInt32 we have takes double and not uint32_t.
Attachment #685707 - Flags: review?(jwalden+bmo) → review+
(Assignee)

Comment 14

4 years ago
https://hg.mozilla.org/integration/mozilla-inbound/rev/1237d9a6ce46
https://hg.mozilla.org/mozilla-central/rev/1237d9a6ce46
Status: NEW → RESOLVED
Last Resolved: 4 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla20
(Assignee)

Updated

4 years ago
Keywords: dev-doc-needed
(Assignee)

Updated

4 years ago
Blocks: 822436
:evilpie documented:
https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Math/imul

I updated
https://developer.mozilla.org/en-US/docs/Firefox_20_for_developers and
https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Math
Keywords: dev-doc-needed → dev-doc-complete

Comment 17

4 years ago
Any 64 bit mul flavor of Math.imul as well? The high and low 32 bit halfs can be stored in two Numbers if needed to ensure no precision loss.
There is work on 64-bit ints in ES7, so adding Math.imul64(low1, high1, low2, high2) or such might be redundant.
You need to log in before you can comment on or make changes to this bug.