Math Javascript Bug on Safari 5 (webkit 533.16) under "32bit" mode

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Darth]

Summary:

This issue comes with the use of BigInteger library from the link below.
The issue happens only in Safari 5 32bit on mac and windows
This library works fine on every other browser under 32bit.

This bug is reproducible with webkit nightly in 32bit

Library in use
-----------
http://www-cs-students.stanford.edu/~tjw/jsbn/

Files
---- 
jsbn.js - basic BigInteger implementation, just enough for RSA encryption and not much more.
jsbn2.js - the rest of the library, including most public BigInteger methods.


Steps to Reproduce:

1] Goto http://www-cs-students.stanford.edu/~tjw/jsbn/rsa2.html
This is a demo page of the above libraries. Once this page is loaded, the js files above should be in the browsers cache and usable.

2] Once the page is loaded, type this in the address bar
javascript:var x = new BigInteger("10000"); var y = new BigInteger("10000"); alert(x.multiply(y));


Expected Results:

All browsers on any platform: An alert popup with the value 100000000


Actual Results:

Safari 5 32bit - an alert with the value 184217728
All other browsers on any platform - an alert popup with the value 100000000


Notes:

A word from the author of that math library

"The "am" functions are various implementations of the core inner 
add-and-multiply loop.  There are several implementations to account for 
the fact that different browsers' JS engines have different bugs when 
doing bitwise math on large Numbers, and also vary in performance.

It sounds like Safari on 32-bit systems has a bug or unexpected 
behavior that prevents am1 and/or am3 from working properly.  The fix 
would be to identify what assumption am1/am3 depend on that isn't being 
met by that JS engine and codify it into a test that forces use of am2 
under those circumstances.

Thanks for the report - I will try to reproduce it on a 32-bit Windows 
Safari and if successful, will add the appropriate test to the next 
version of jsbn."


Methods in question -
Based on the logic below, the am3 algorithm is chosen for safari, firefox and chrome


// am: Compute w_j += (x*this_i), propagate carries,
// c is initial carry, returns final carry.
// c < 3*dvalue, x < 2*dvalue, this_i < dvalue
// We need to select the fastest one that works in this environment.

// am1: use a single mult and divide to get the high bits,
// max digit bits should be 26 because
// max internal value = 2*dvalue^2-2*dvalue (< 2^53)
function am1(i,x,w,j,c,n) {
  while(--n >= 0) {
    var v = x*this[i++]+w[j]+c;
    c = Math.floor(v/0x4000000);
    w[j++] = v&0x3ffffff;
  }
  return c;
}
// am2 avoids a big mult-and-extract completely.
// Max digit bits should be <= 30 because we do bitwise ops
// on values up to 2*hdvalue^2-hdvalue-1 (< 2^31)
function am2(i,x,w,j,c,n) {
  var xl = x&0x7fff, xh = x>>15;
  while(--n >= 0) {
    var l = this[i]&0x7fff;
    var h = this[i++]>>15;
    var m = xh*l+h*xl;
    l = xl*l+((m&0x7fff)<<15)+w[j]+(c&0x3fffffff);
    c = (l>>>30)+(m>>>15)+xh*h+(c>>>30);
    w[j++] = l&0x3fffffff;
  }
  return c;
}
// Alternately, set max digit bits to 28 since some
// browsers slow down when dealing with 32-bit numbers.
function am3(i,x,w,j,c,n) {
  var xl = x&0x3fff, xh = x>>14;
  while(--n >= 0) {
    var l = this[i]&0x3fff;
    var h = this[i++]>>14;
    var m = xh*l+h*xl;
    l = xl*l+((m&0x3fff)<<14)+w[j]+c;
    c = (l>>28)+(m>>14)+xh*h;
    w[j++] = l&0xfffffff;
  }
  return c;
}
if(j_lm && (navigator.appName == "Microsoft Internet Explorer")) {
  BigInteger.prototype.am = am2;
  dbits = 30;
}
else if(j_lm && (navigator.appName != "Netscape")) {
  BigInteger.prototype.am = am1;
  dbits = 26;
}
else { // Mozilla/Netscape seems to prefer am3
  BigInteger.prototype.am = am3;
  dbits = 28; <<<<<<<<<<<<<<<< changing to 30 bits fixes the issue
}

[Darth]

Actually changing it to 30 bits as mentioned above has other multiplication/subtraction issues, so it is not a fix.

[Gavin Barraclough]

<rdar://problem/8076479>

[Darth]

Additional information from the author -


After some further investigation, there appears to be a bug in Safari's JS 
engine.  The following code/URL demonstrates the problem:

javascript:var a=new Array();a[0]=Math.pow(10,8);alert((a[0]>>27)|0);

If you inspect the code, you can easily prove to yourself that the correct 
value for the alert is "0", which is what you get on most browsers.  On 
Safari for Windows 32-bit, I get "100000000".

Given the subtlety of this bug and the fact that I don't really 
understand its root cause, I don't think it makes sense to try to 
make a workaround in JSBN since it is not clear where else this bug might 
manifest itself.  One of us should file a bug report with Apple for this.

Tom

[Darth]

Changed the title to mention its a general problem and not in particular with the library mentioned.
Typing javascript:alert((Math.pow(10,8)>>27 | 0)) in the browser address bar shows.

[Oliver Hunt]

(In reply to comment #4)
> Changed the title to mention its a general problem and not in particular with the library mentioned.
> Typing javascript:alert((Math.pow(10,8)>>27 | 0)) in the browser address bar shows.

I'll look at this tonight, i suspect it's my fault.

[Oliver Hunt]

Slightly simplified: javascript:g=100000000.1;alert((g >> 27 | 0))

I would guess is that we're assuming any integer result is in a specific register when we get to the | but in the double case we're not actually doing that.

[Oliver Hunt]

Turning a build with my fix now.

[Oliver Hunt]

(In reply to comment #1)
> Actually changing it to 30 bits as mentioned above has other multiplication/subtraction issues, so it is not a fix.

Also it was papering over the issue -- basically the issue is that a right shift of a value that is internally stored as a double fails to correctly set the integer flag on the internal value at the end of the shift.  A few work arounds are possible but it depends on exactly what's happening.

If the issue is specifically an expression of the form
a >> n | 0

My question is what range of values do you expect a to have?

(a | 0) >> n

Should produce the desired result (if my understanding of what you're trying to do is correct)

[Oliver Hunt]

Created attachment 58442 [details]
Patch

[Oliver Hunt]

Committed r60990: <http://trac.webkit.org/changeset/60990>

[Oliver Hunt]

*** Bug 40355 has been marked as a duplicate of this bug. ***

[Oliver Hunt]

*** Bug 40306 has been marked as a duplicate of this bug. ***