Bug 80465

Summary: Integer overflow check code in arithmetic operation in classic interpreter
Product: WebKit Reporter: SangGyu Lee <sg5.lee>
Component: JavaScriptCoreAssignee: Nobody <webkit-unassigned>
Severity: Minor CC: barraclough, fpizlo, webkit.review.bot
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: All   
OS: All   
Description Flags
Patch none

Description SangGyu Lee 2012-03-06 18:04:11 PST
Classic Interpreter checks whether integer arithmetic operation will cause overflow in privateExecute().

Currently the check code is like followings:

    DEFINE_OPCODE(op_add) {
        /* add dst(r) src1(r) src2(r)

           Adds register src1 and register src2, and puts the result
           in register dst. (JS add may be string concatenation or
           numeric add, depending on the types of the operands.)
        int dst = vPC[1].u.operand;
        JSValue src1 = callFrame->r(vPC[2].u.operand).jsValue();
        JSValue src2 = callFrame->r(vPC[3].u.operand).jsValue();
        if (src1.isInt32() && src2.isInt32() && !(src1.asInt32() | (src2.asInt32() & 0xc0000000))) // no overflow            callFrame->uncheckedR(dst) = jsNumber(src1.asInt32() + src2.asInt32());
        else {
            JSValue result = jsAdd(callFrame, src1, src2);
            callFrame->uncheckedR(dst) = result;

I can't understand the test condition

   ... && !(src1.asInt32() | (src2.asInt32() & 0xc0000000))) // no overflow

If src1 is not zero, it would falling to else condition (jsAdd).

For simple example, both src1 and src2 is 1, it fails the condition:

   ... && !((src1.asInt32() | src2.asInt32()) & 0xc0000000))

I wonder if is a mistake, and the original intention is 

   ... && !((src1.asInt32() | src2.asInt32()) & 0xc0000000))

Please see the change in parenthesis.

If both of src1 and src2 have most two significant bits as zero, no overflow can occurs.
Although, it is conservative, but is fast and simple check.

op_sub has same condition.

I have same question about op_mul.

        if (src1.isInt32() && src2.isInt32() && !(src1.asInt32() | src2.asInt32() >> 15)) // no overflow

the test expression should be like followings:

 ... && !( (src1.asInt32() | src2.asInt32()) >> 15)) // no overflow

Please see added parenthesis. 
Since bit-shift operator's precedence is high than bit OR, parenthesis is necessary.

If both src1 and src2 have most 16 significant bits as zero, no overflow can occurs.
Comment 1 Gavin Barraclough 2012-03-07 00:24:43 PST
(In reply to comment #0)
> I wonder if is a mistake, and the original intention is 

Ouch, yes, I think you're right.

> Although, it is conservative, but is fast and simple check.

Yes, that is the intention.

> If both src1 and src2 have most 16 significant bits as zero, no overflow can occurs.

Yes, again I think you're right.

One detail, actually you need the top 17 bits to be zero.  Multiplying two 16 bit values requires nearly the full 32-bit range (2^16 - 1)^2 == 2^32 - 2^17 + 1, so cannot be  represented with a signed integer.
Comment 2 SangGyu Lee 2012-03-11 18:20:24 PDT
Created attachment 131266 [details]
Comment 3 Gavin Barraclough 2012-03-11 19:28:11 PDT
Comment on attachment 131266 [details]

See my last comment, changing the value '15' to '16' is incorrect, you will fail to detect overflow in the case of values such as 0xFFFF * 0xFFFF.
Comment 4 SangGyu Lee 2012-03-11 19:49:48 PDT
I am sorry for my mistake. I incorrectly assumed the operand is a unsigned number. As your kind and concise comment, 16 bit is not enough for the cases like 0xFFFF x 0xFFFF.
Comment 5 SangGyu Lee 2012-03-11 19:52:36 PDT
Created attachment 131274 [details]
Comment 6 Gavin Barraclough 2012-03-11 22:17:15 PDT
Comment on attachment 131274 [details]

Sorry, still not quite there! - we need to check the top 17 bits are all zero - we can ignore the bottom 15 bits.  So the shift count needs to be 15, not 17!
Comment 7 SangGyu Lee 2012-03-12 02:15:46 PDT
I am sorry, and thank you for fixing my stupid mistake.
Comment 8 SangGyu Lee 2012-03-12 02:20:47 PDT
Created attachment 131299 [details]
Comment 9 Gavin Barraclough 2012-03-12 10:04:10 PDT
Comment on attachment 131299 [details]

Looks good, great catch - thanks for fixing this.
Comment 10 WebKit Review Bot 2012-03-12 10:31:42 PDT
Comment on attachment 131299 [details]

Clearing flags on attachment: 131299

Committed r110443: <http://trac.webkit.org/changeset/110443>
Comment 11 WebKit Review Bot 2012-03-12 10:31:47 PDT
All reviewed patches have been landed.  Closing bug.