40367 2010-06-09 10:00:45 -0700 Math Javascript Bug on Safari 5 (webkit 533.16) under "32bit" mode 2010-06-11 17:22:57 -0700 1 1 1 Unclassified WebKit JavaScriptCore 528+ (Nightly build) All All RESOLVED FIXED InRadar P1 Critical --- 1 priyajeet.hora webkit-unassigned ap barraclough noel.gordon oliver priyajeet.hora oldest_to_newest 235840 0 priyajeet.hora 2010-06-09 10:00:45 -0700 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 } 235914 1 priyajeet.hora 2010-06-09 11:47:57 -0700 Actually changing it to 30 bits as mentioned above has other multiplication/subtraction issues, so it is not a fix. 235959 2 barraclough 2010-06-09 13:06:43 -0700 <rdar://problem/8076479> 236026 3 priyajeet.hora 2010-06-09 14:55:54 -0700 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 236041 4 priyajeet.hora 2010-06-09 15:17:31 -0700 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. 236044 5 oliver 2010-06-09 15:25:01 -0700 (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. 236046 6 oliver 2010-06-09 15:29:29 -0700 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. 236652 7 oliver 2010-06-10 19:45:34 -0700 Turning a build with my fix now. 236658 8 oliver 2010-06-10 20:02:29 -0700 (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) 236663 9 58442 oliver 2010-06-10 20:41:14 -0700 Created attachment 58442 Patch 236688 10 oliver 2010-06-10 22:37:00 -0700 Committed r60990: <http://trac.webkit.org/changeset/60990> 236874 11 oliver 2010-06-11 09:42:56 -0700 *** Bug 40355 has been marked as a duplicate of this bug. *** 237174 12 oliver 2010-06-11 17:22:57 -0700 *** Bug 40306 has been marked as a duplicate of this bug. *** 58442 2010-06-10 20:41:14 -0700 2010-06-10 22:33:04 -0700 Patch bug-40367-20100610204113.patch text/plain 4791 oliver ZGlmZiAtLWdpdCBhL0phdmFTY3JpcHRDb3JlL0NoYW5nZUxvZyBiL0phdmFTY3JpcHRDb3JlL0No YW5nZUxvZwppbmRleCA3ZmU5ZTU5MWY0MjYxZTUyZjQxZjEyMzNjODE3OTMzZDFhZGY4M2QxLi5j MjY1MjE1ZjM5NDIzN2MxMjIwYWMwMjNjMjBjYTZmMGUxNjk3ZGY3IDEwMDY0NAotLS0gYS9KYXZh U2NyaXB0Q29yZS9DaGFuZ2VMb2cKKysrIGIvSmF2YVNjcmlwdENvcmUvQ2hhbmdlTG9nCkBAIC0x LDMgKzEsMTcgQEAKKzIwMTAtMDYtMTAgIE9saXZlciBIdW50ICA8b2xpdmVyQGFwcGxlLmNvbT4K KworICAgICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAgICAgICBNYXRoIEph dmFzY3JpcHQgQnVnIG9uIFNhZmFyaSA1ICh3ZWJraXQgNTMzLjE2KSB1bmRlciAiMzJiaXQiIG1v ZGUKKyAgICAgICAgaHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTQwMzY3 CisKKyAgICAgICAgSWYgd2UncmUgaW4gdGhlIHNsb3cgY2FzZSBvZiByaWdodCBzaGlmdCB3ZSBt dXN0IHdyaXRlIHRoZSB0eXBlIHRhZyBhcworICAgICAgICB0aGUgb25seSByZWFzb24gd2UgaGl0 IHRoaXMgY29kZSBwYXRoIGlzIGJlY2F1c2Ugd2Uga25vdyB3ZSdyZSB3b3JraW5nCisgICAgICAg IHdpdGggYSBkb3VibGUuICBlZy4gd2UgYXJlIGd1YXJhbnRlZWQgdGhhdCB0aGUgdGFnIGNhbm5v dCBiZSByZXVzZWQuCisKKyAgICAgICAgKiBqaXQvSklUQXJpdGhtZXRpYzMyXzY0LmNwcDoKKyAg ICAgICAgKEpTQzo6SklUOjplbWl0UmlnaHRTaGlmdFNsb3dDYXNlKToKKwogMjAxMC0wNi0xMCAg S3dhbmcgWXVsIFNlbyAgPHNreXVsQGNvbXBhbnkxMDAubmV0PgogCiAgICAgICAgIFJldmlld2Vk IGJ5IEVyaWMgU2VpZGVsLgpkaWZmIC0tZ2l0IGEvSmF2YVNjcmlwdENvcmUvaml0L0pJVEFyaXRo bWV0aWMzMl82NC5jcHAgYi9KYXZhU2NyaXB0Q29yZS9qaXQvSklUQXJpdGhtZXRpYzMyXzY0LmNw cAppbmRleCAwMjM0MjZlMDhlMzZmNTE5MGNlNjRlYTM3NTQ3MmY3MWYyNzYzMzg3Li40ZjM2ZDY2 MDk3MzkwMDY2MjQ4M2Q3NjI4MjYxOGZjYjA2NDczNGNkIDEwMDY0NAotLS0gYS9KYXZhU2NyaXB0 Q29yZS9qaXQvSklUQXJpdGhtZXRpYzMyXzY0LmNwcAorKysgYi9KYXZhU2NyaXB0Q29yZS9qaXQv SklUQXJpdGhtZXRpYzMyXzY0LmNwcApAQCAtNDYwLDcgKzQ2MCw3IEBAIHZvaWQgSklUOjplbWl0 UmlnaHRTaGlmdFNsb3dDYXNlKEluc3RydWN0aW9uKiBjdXJyZW50SW5zdHJ1Y3Rpb24sIFZlY3Rv cjxTbG93Q2FzCiAgICAgICAgICAgICAgICAgICAgIGZhaWx1cmVzLmFwcGVuZChicmFuY2gzMihM ZXNzVGhhbiwgcmVnVDAsIEltbTMyKDApKSk7CiAgICAgICAgICAgICB9IGVsc2UgaWYgKHNoaWZ0 KQogICAgICAgICAgICAgICAgIHJzaGlmdDMyKEltbTMyKHNoaWZ0ICYgMHgxZiksIHJlZ1QwKTsK LSAgICAgICAgICAgIGVtaXRTdG9yZUludDMyKGRzdCwgcmVnVDAsIGRzdCA9PSBvcDEgfHwgZHN0 ID09IG9wMik7CisgICAgICAgICAgICBlbWl0U3RvcmVJbnQzMihkc3QsIHJlZ1QwLCBmYWxzZSk7 CiAgICAgICAgICAgICBlbWl0SnVtcFNsb3dUb0hvdChqdW1wKCksIE9QQ09ERV9MRU5HVEgob3Bf cnNoaWZ0KSk7CiAgICAgICAgICAgICBmYWlsdXJlcy5saW5rKHRoaXMpOwogICAgICAgICB9CkBA IC00ODAsNyArNDgwLDcgQEAgdm9pZCBKSVQ6OmVtaXRSaWdodFNoaWZ0U2xvd0Nhc2UoSW5zdHJ1 Y3Rpb24qIGN1cnJlbnRJbnN0cnVjdGlvbiwgVmVjdG9yPFNsb3dDYXMKICAgICAgICAgICAgICAg ICAgICAgdXJzaGlmdDMyKHJlZ1QyLCByZWdUMCk7CiAgICAgICAgICAgICAgICAgZWxzZQogICAg ICAgICAgICAgICAgICAgICByc2hpZnQzMihyZWdUMiwgcmVnVDApOwotICAgICAgICAgICAgICAg IGVtaXRTdG9yZUludDMyKGRzdCwgcmVnVDAsIGRzdCA9PSBvcDEgfHwgZHN0ID09IG9wMik7Cisg ICAgICAgICAgICAgICAgZW1pdFN0b3JlSW50MzIoZHN0LCByZWdUMCwgZmFsc2UpOwogICAgICAg ICAgICAgICAgIGVtaXRKdW1wU2xvd1RvSG90KGp1bXAoKSwgT1BDT0RFX0xFTkdUSChvcF9yc2hp ZnQpKTsKICAgICAgICAgICAgICAgICBub3REb3VibGUubGluayh0aGlzKTsKICAgICAgICAgICAg ICAgICBub3RJbnQubGluayh0aGlzKTsKZGlmZiAtLWdpdCBhL0xheW91dFRlc3RzL0NoYW5nZUxv ZyBiL0xheW91dFRlc3RzL0NoYW5nZUxvZwppbmRleCAzOWQ1ZDQ2ZmM5MDRmY2YyOTkzOTE1YzJl NmU0Y2MxZWFlMzQ0ZjI4Li44NDBmNTVlNDkxYjQ0YWY3Y2YyYzRiYTYzYmZhMTYxOTg5N2IwZmRh IDEwMDY0NAotLS0gYS9MYXlvdXRUZXN0cy9DaGFuZ2VMb2cKKysrIGIvTGF5b3V0VGVzdHMvQ2hh bmdlTG9nCkBAIC0xLDMgKzEsMTUgQEAKKzIwMTAtMDYtMTAgIE9saXZlciBIdW50ICA8b2xpdmVy QGFwcGxlLmNvbT4KKworICAgICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAg ICAgICBNYXRoIEphdmFzY3JpcHQgQnVnIG9uIFNhZmFyaSA1ICh3ZWJraXQgNTMzLjE2KSB1bmRl ciAiMzJiaXQiIG1vZGUKKyAgICAgICAgaHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcu Y2dpP2lkPTQwMzY3CisKKyAgICAgICAgQWRkIHNvbWUgdGVzdHMgdG8gZW5zdXJlIGNvcnJlY3Qg YmVoYXZpb3VyIG9mIHJpZ2h0IHNoaWZ0LgorCisgICAgICAgICogZmFzdC9qcy9iaXRvcHMtdHlw ZS10YWcuaHRtbDogQWRkZWQuCisgICAgICAgICogZmFzdC9qcy9zY3JpcHQtdGVzdHMvYml0b3Bz LXR5cGUtdGFnLmpzOiBBZGRlZC4KKwogMjAxMC0wNi0xMCAgVG9ueSBDaGFuZyAgPHRvbnlAY2hy b21pdW0ub3JnPgogCiAgICAgICAgIFJldmlld2VkIGJ5IEtlbnQgVGFtdXJhLgpkaWZmIC0tZ2l0 IGEvTGF5b3V0VGVzdHMvZmFzdC9qcy9iaXRvcHMtdHlwZS10YWctZXhwZWN0ZWQudHh0IGIvTGF5 b3V0VGVzdHMvZmFzdC9qcy9iaXRvcHMtdHlwZS10YWctZXhwZWN0ZWQudHh0Cm5ldyBmaWxlIG1v ZGUgMTAwNjQ0CmluZGV4IDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAu LjI1M2Q2MGRmNTJhNGZjYjAxNTNhN2QwMWM1Y2EyMjA1MDNjOTA4NDYKLS0tIC9kZXYvbnVsbAor KysgYi9MYXlvdXRUZXN0cy9mYXN0L2pzL2JpdG9wcy10eXBlLXRhZy1leHBlY3RlZC50eHQKQEAg LTAsMCArMSwxNCBAQAorRW5zdXJlIHZhcmlvdXMgYml0IG9wZXJhdG9ycyBjb3JyZWN0bHkgdGFn IHRoZSBmaW5hbCByZXN1bHQgdmFsdWUKKworT24gc3VjY2VzcywgeW91IHdpbGwgc2VlIGEgc2Vy aWVzIG9mICJQQVNTIiBtZXNzYWdlcywgZm9sbG93ZWQgYnkgIlRFU1QgQ09NUExFVEUiLgorCisK K1BBU1MgYURvdWJsZT4+MjcgaXMgMAorUEFTUyBhRG91YmxlPj4yN3wwIGlzIDAKK1BBU1MgYURv dWJsZT4+MCBpcyAxMDAwMDAwMDAKK1BBU1MgYURvdWJsZT4+MHwwIGlzIDEwMDAwMDAwMAorUEFT UyBhRG91YmxlfDAgaXMgMTAwMDAwMDAwCitQQVNTIHN1Y2Nlc3NmdWxseVBhcnNlZCBpcyB0cnVl CisKK1RFU1QgQ09NUExFVEUKKwpkaWZmIC0tZ2l0IGEvTGF5b3V0VGVzdHMvZmFzdC9qcy9iaXRv cHMtdHlwZS10YWcuaHRtbCBiL0xheW91dFRlc3RzL2Zhc3QvanMvYml0b3BzLXR5cGUtdGFnLmh0 bWwKbmV3IGZpbGUgbW9kZSAxMDA2NDQKaW5kZXggMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAw MDAwMDAwMDAwMDAwMC4uNDk4ODYyZWIyNjllNTJkN2Y1MTdlZTYxNjZkNDhiMDQyNzk3Zjg1Zgot LS0gL2Rldi9udWxsCisrKyBiL0xheW91dFRlc3RzL2Zhc3QvanMvYml0b3BzLXR5cGUtdGFnLmh0 bWwKQEAgLTAsMCArMSwxMyBAQAorPCFET0NUWVBFIEhUTUwgUFVCTElDICItLy9JRVRGLy9EVEQg SFRNTC8vRU4iPgorPGh0bWw+Cis8aGVhZD4KKzxsaW5rIHJlbD0ic3R5bGVzaGVldCIgaHJlZj0i cmVzb3VyY2VzL2pzLXRlc3Qtc3R5bGUuY3NzIj4KKzxzY3JpcHQgc3JjPSJyZXNvdXJjZXMvanMt dGVzdC1wcmUuanMiPjwvc2NyaXB0PgorPC9oZWFkPgorPGJvZHk+Cis8cCBpZD0iZGVzY3JpcHRp b24iPjwvcD4KKzxkaXYgaWQ9ImNvbnNvbGUiPjwvZGl2PgorPHNjcmlwdCBzcmM9InNjcmlwdC10 ZXN0cy9iaXRvcHMtdHlwZS10YWcuanMiPjwvc2NyaXB0PgorPHNjcmlwdCBzcmM9InJlc291cmNl cy9qcy10ZXN0LXBvc3QuanMiPjwvc2NyaXB0PgorPC9ib2R5PgorPC9odG1sPgpkaWZmIC0tZ2l0 IGEvTGF5b3V0VGVzdHMvZmFzdC9qcy9zY3JpcHQtdGVzdHMvYml0b3BzLXR5cGUtdGFnLmpzIGIv TGF5b3V0VGVzdHMvZmFzdC9qcy9zY3JpcHQtdGVzdHMvYml0b3BzLXR5cGUtdGFnLmpzCm5ldyBm aWxlIG1vZGUgMTAwNjQ0CmluZGV4IDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAw MDAwMDAuLmRmYTRmOWQ1YTU2ZTRmMWMwNTA0NWM5ODEyNjcyODM4ODg2YmI3MDYKLS0tIC9kZXYv bnVsbAorKysgYi9MYXlvdXRUZXN0cy9mYXN0L2pzL3NjcmlwdC10ZXN0cy9iaXRvcHMtdHlwZS10 YWcuanMKQEAgLTAsMCArMSwxMCBAQAorZGVzY3JpcHRpb24oIkVuc3VyZSB2YXJpb3VzIGJpdCBv cGVyYXRvcnMgY29ycmVjdGx5IHRhZyB0aGUgZmluYWwgcmVzdWx0IHZhbHVlIik7CisKK2FEb3Vi bGUgPSAxMDAwMDAwMDAuNTsKK3Nob3VsZEJlKCJhRG91YmxlPj4yNyIsICIwIik7CitzaG91bGRC ZSgiYURvdWJsZT4+Mjd8MCIsICIwIik7CitzaG91bGRCZSgiYURvdWJsZT4+MCIsICIxMDAwMDAw MDAiKTsKK3Nob3VsZEJlKCJhRG91YmxlPj4wfDAiLCAiMTAwMDAwMDAwIik7CitzaG91bGRCZSgi YURvdWJsZXwwIiwgIjEwMDAwMDAwMCIpOworCit2YXIgc3VjY2Vzc2Z1bGx5UGFyc2VkID0gdHJ1 ZTsK