151641 2015-11-28 05:51:36 -0800 Use a better RNG for Math.random() 2015-12-01 00:27:11 -0800 1 1 1 Unclassified WebKit JavaScriptCore WebKit Nightly Build Unspecified Unspecified RESOLVED FIXED P2 Normal --- 1 jdemooij ggaren barraclough benjamin cdumez cmarcelo commit-queue ggaren keith_miller mark.lam msaboff oliver saam ysuzuki oldest_to_newest 1144649 0 jdemooij 2015-11-28 05:51:36 -0800 The GameRand-based RNG Safari/JSC uses is very weak. Furthermore, it only uses 32 bits of precision. I blogged about this here: http://jandemooij.nl/blog/2015/11/27/math-random-and-32-bit-precision/ V8 moved to a better RNG and we're switching the one in SpiderMonkey as well. JSC should probably do the same. 1144652 1 oliver 2015-11-28 09:55:10 -0800 If we really do consider more than 32bits necessary id just move up to a 64bit variant of gamerand which should not have a significant perf impact, then value & (2^53-1) / 2^53 (I can recall if the rand includes 1 as a valid result). Has someone done something to find it's aggressively non-uniform in some space? 1145036 2 266302 ggaren 2015-11-30 17:01:13 -0800 Created attachment 266302 Patch 1145038 3 ggaren 2015-11-30 17:04:17 -0800 I kind of wanted to stick with GameRandom in order to troll the internet commentators who keep confusing / conflating RNG algorithm with number of bits provided by RNG interface. But there's literally no downside to upgrading to Xorshift+, so I've done it. 1145042 4 266302 andersca 2015-11-30 17:10:54 -0800 Comment on attachment 266302 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=266302&action=review > Source/WTF/ChangeLog:10 > + prevents programs that mulitply a random number by a large constant from typo, multiply. 1145104 5 ggaren 2015-11-30 19:40:09 -0800 Committed r192855: <http://trac.webkit.org/changeset/192855> 1145174 6 jdemooij 2015-12-01 00:27:11 -0800 (In reply to comment #3) > I kind of wanted to stick with GameRandom in order to troll the internet > commentators who keep confusing / conflating RNG algorithm with number of > bits provided by RNG interface. It's not just that; GameRand also doesn't do well in statistical tests: http://jandemooij.nl/blog/2015/11/30/testing-math-random-crushing-the-browser/ No big deal probably, but it shows the algorithm has other issues. > But there's literally no downside to upgrading to Xorshift+, so I've done it. \o/ 266302 2015-11-30 17:01:13 -0800 2015-11-30 17:10:54 -0800 Patch bug-151641-20151130170051.patch text/plain 7297 ggaren SW5kZXg6IFNvdXJjZS9KYXZhU2NyaXB0Q29yZS9DaGFuZ2VMb2cKPT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gU291 cmNlL0phdmFTY3JpcHRDb3JlL0NoYW5nZUxvZwkocmV2aXNpb24gMTkyODQ0KQorKysgU291cmNl L0phdmFTY3JpcHRDb3JlL0NoYW5nZUxvZwkod29ya2luZyBjb3B5KQpAQCAtMSwzICsxLDE1IEBA CisyMDE1LTExLTMwICBHZW9mZnJleSBHYXJlbiAgPGdnYXJlbkBhcHBsZS5jb20+CisKKyAgICAg ICAgVXNlIGEgYmV0dGVyIFJORyBmb3IgTWF0aC5yYW5kb20oKQorICAgICAgICBodHRwczovL2J1 Z3Mud2Via2l0Lm9yZy9zaG93X2J1Zy5jZ2k/aWQ9MTUxNjQxCisKKyAgICAgICAgUmV2aWV3ZWQg YnkgTk9CT0RZIChPT1BTISkuCisKKyAgICAgICAgVXBkYXRlZCBmb3IgaW50ZXJmYWNlIGNoYW5n ZS4KKworICAgICAgICAqIHJ1bnRpbWUvSlNHbG9iYWxPYmplY3QuY3BwOgorICAgICAgICAoSlND OjpKU0dsb2JhbE9iamVjdDo6c2V0SW5wdXRDdXJzb3IpOgorCiAyMDE1LTExLTMwICBNYXJrIExh bSAgPG1hcmsubGFtQGFwcGxlLmNvbT4KIAogICAgICAgICBSZWZhY3RvciB0aGUgb3BfYWRkLCBv cF9zdWIsIGFuZCBvcF9tdWwgc25pcHBldHMgdG8gdXNlIHRoZSBTbmlwcGV0T3BlcmFuZCBjbGFz cy4KSW5kZXg6IFNvdXJjZS9KYXZhU2NyaXB0Q29yZS9ydW50aW1lL0pTR2xvYmFsT2JqZWN0LmNw cAo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09Ci0tLSBTb3VyY2UvSmF2YVNjcmlwdENvcmUvcnVudGltZS9KU0dsb2JhbE9i amVjdC5jcHAJKHJldmlzaW9uIDE5MjgwNSkKKysrIFNvdXJjZS9KYXZhU2NyaXB0Q29yZS9ydW50 aW1lL0pTR2xvYmFsT2JqZWN0LmNwcAkod29ya2luZyBjb3B5KQpAQCAtMTAxNCwxMCArMTAxNCwx MCBAQCB2b2lkIEpTR2xvYmFsT2JqZWN0OjpzZXRJbnB1dEN1cnNvcihQYXNzCiAgICAgLy8gU2F2 ZSBvciBzZXQgdGhlIHJhbmRvbSBzZWVkLiBUaGlzIHBlcmZvcm1lZCBoZXJlIHJhdGhlciB0aGFu IHRoZSBjb25zdHJ1Y3RvcgogICAgIC8vIHRvIGF2b2lkIHRocmVhZGluZyB0aGUgaW5wdXQgY3Vy c29yIHRocm91Z2ggYWxsIHRoZSBhYnN0cmFjdGlvbiBsYXllcnMuCiAgICAgaWYgKGN1cnNvci5p c0NhcHR1cmluZygpKQotICAgICAgICBjdXJzb3IuYXBwZW5kSW5wdXQ8U2V0UmFuZG9tU2VlZD4o bV93ZWFrUmFuZG9tLnNlZWRVbnNhZmUoKSk7CisgICAgICAgIGN1cnNvci5hcHBlbmRJbnB1dDxT ZXRSYW5kb21TZWVkPihtX3dlYWtSYW5kb20uc2VlZCgpKTsKICAgICBlbHNlIGlmIChjdXJzb3Iu aXNSZXBsYXlpbmcoKSkgewogICAgICAgICBpZiAoU2V0UmFuZG9tU2VlZCogaW5wdXQgPSBjdXJz b3IuZmV0Y2hJbnB1dDxTZXRSYW5kb21TZWVkPigpKQotICAgICAgICAgICAgbV93ZWFrUmFuZG9t LmluaXRpYWxpemVTZWVkKHN0YXRpY19jYXN0PHVuc2lnbmVkPihpbnB1dC0+cmFuZG9tU2VlZCgp KSk7CisgICAgICAgICAgICBtX3dlYWtSYW5kb20uc2V0U2VlZChzdGF0aWNfY2FzdDx1bnNpZ25l ZD4oaW5wdXQtPnJhbmRvbVNlZWQoKSkpOwogICAgIH0KIH0KICNlbmRpZgpJbmRleDogU291cmNl L1dURi9DaGFuZ2VMb2cKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gU291cmNlL1dURi9DaGFuZ2VMb2cJKHJldmlz aW9uIDE5MjgwNSkKKysrIFNvdXJjZS9XVEYvQ2hhbmdlTG9nCSh3b3JraW5nIGNvcHkpCkBAIC0x LDMgKzEsMzcgQEAKKzIwMTUtMTEtMzAgIEdlb2ZmcmV5IEdhcmVuICA8Z2dhcmVuQGFwcGxlLmNv bT4KKworICAgICAgICBVc2UgYSBiZXR0ZXIgUk5HIGZvciBNYXRoLnJhbmRvbSgpCisgICAgICAg IGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD0xNTE2NDEKKworICAgICAg ICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAgICAgICBVc2UgNjQgYml0cyBpbiB0 aGUgcmFuZG9tIG51bWJlciBnZW5lcmF0b3IgaW5zdGVhZCBvZiAzMiBiaXQuIChJbgorICAgICAg ICB0aGUgZW5kLCBKYXZhU2NyaXB0LCB3aGljaCB1c2VzIGRvdWJsZXMsIHdpbGwgb25seSBzZWUg NTIgYml0cy4pIFRoaXMKKyAgICAgICAgcHJldmVudHMgcHJvZ3JhbXMgdGhhdCBtdWxpdHBseSBh IHJhbmRvbSBudW1iZXIgYnkgYSBsYXJnZSBjb25zdGFudCBmcm9tCisgICAgICAgIHNlZWluZyBu b24tcmFuZG9tICJiYW5kaW5nIiBjYXVzZWQgYnkgemVyb2VzIGluIHRoZSBsb3cgMjAgYml0cy4K KworICAgICAgICBJIGFsc28gdG9vayB0aGUgb3Bwb3J0dW5pdHkgdG8gdXBncmFkZSBmcm9tIEdh bWVSYW5kb20gdG8gWG9yc2hpZnQrLAorICAgICAgICBzaW5jZSBYb3JzaGlmdCsgcGFzc2VzIG1v cmUgYmVuY2htYXJrcyBmb3IgcmFuZG9tbmVzcywgYW5kIGlzIG5vdCBhbnkKKyAgICAgICAgc2xv d2VyIG9yIG1vcmUgY29tcGxpY2F0ZWQuCisKKyAgICAgICAgTm93IGxldCB1cyBhbGwgcmVtZW1i ZXIgdGhlIGZhdGVmdWwgd29yZHMgb2YgU3RldmUgV2VpYmUsIHdobyB3b3VsZCBiZQorICAgICAg ICBLaW5nIG9mIEtvbmc6ICJUaGUgcmFuZG9tbmVzcyB3ZW50IHRoZSBvcHBvc2l0ZSB3YXkgdGhh dCBpdCB1c3VhbGx5IGdvZXMuIgorCisgICAgICAgICogd3RmL1dlYWtSYW5kb20uaDoKKyAgICAg ICAgKFdURjo6V2Vha1JhbmRvbTo6V2Vha1JhbmRvbSk6CisgICAgICAgIChXVEY6OldlYWtSYW5k b206OnNldFNlZWQpOiBVc2Ugc3RhbmRhcmQgbmFtaW5nLgorCisgICAgICAgIChXVEY6OldlYWtS YW5kb206OnNlZWQpOiBUaGlzIGZ1bmN0aW9uIGlzIHNhZmUgbm93LiAiVW5zYWZlIiBpbiBmdW5j dGlvbgorICAgICAgICBuYW1lcyBtYWtlcyBtZSBpdGNoLgorCisgICAgICAgIChXVEY6OldlYWtS YW5kb206OmdldCk6CisgICAgICAgIChXVEY6OldlYWtSYW5kb206OmdldFVpbnQzMik6IFVwZGF0 ZSB0byA2NGJpdC4KKworICAgICAgICAoV1RGOjpXZWFrUmFuZG9tOjphZHZhbmNlKTogVGhlIFhv cnNoaWZ0KyBhbGdvcml0aG0uCisKKyAgICAgICAgKFdURjo6V2Vha1JhbmRvbTo6aW5pdGlhbGl6 ZVNlZWQpOiBEZWxldGVkLgorICAgICAgICAoV1RGOjpXZWFrUmFuZG9tOjpzZWVkVW5zYWZlKTog RGVsZXRlZC4KKwogMjAxNS0xMS0zMCAgQ2FybG9zIEdhcmNpYSBDYW1wb3MgIDxjZ2FyY2lhQGln YWxpYS5jb20+CiAKICAgICAgICAgW0dMSUJdIFJlbW92ZSBHTWFpbkxvb3BTb3VyY2UgYW5kIEdU aHJlYWRTYWZlTWFpbkxvb3BTb3VyY2UKSW5kZXg6IFNvdXJjZS9XVEYvd3RmL1dlYWtSYW5kb20u aAo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV1RGL3d0Zi9XZWFrUmFuZG9tLmgJKHJldmlzaW9uIDE5 MjgwNSkKKysrIFNvdXJjZS9XVEYvd3RmL1dlYWtSYW5kb20uaAkod29ya2luZyBjb3B5KQpAQCAt MjIsNzYgKzIyLDU3IEBACiAgKiAoSU5DTFVESU5HIE5FR0xJR0VOQ0UgT1IgT1RIRVJXSVNFKSBB UklTSU5HIElOIEFOWSBXQVkgT1VUIE9GIFRIRSBVU0UKICAqIE9GIFRISVMgU09GVFdBUkUsIEVW RU4gSUYgQURWSVNFRCBPRiBUSEUgUE9TU0lCSUxJVFkgT0YgU1VDSCBEQU1BR0UuIAogICoKKyAq IFZpZ25hLCBTZWJhc3RpYW5vICgyMDE0KS4gIkZ1cnRoZXIgc2NyYW1ibGluZ3Mgb2YgTWFyc2Fn bGlhJ3MgeG9yc2hpZnQKKyAqIGdlbmVyYXRvcnMiLiBhclhpdjoxNDA0LjAzOTAgKGh0dHA6Ly9h cnhpdi5vcmcvYWJzLzE0MDQuMDM5MCkKICAqCi0gKiBDb3B5cmlnaHQgKGMpIDIwMDkgSWFuIEMu IEJ1bGxhcmQKLSAqIAotICogUGVybWlzc2lvbiBpcyBoZXJlYnkgZ3JhbnRlZCwgZnJlZSBvZiBj aGFyZ2UsIHRvIGFueSBwZXJzb24KLSAqIG9idGFpbmluZyBhIGNvcHkgb2YgdGhpcyBzb2Z0d2Fy ZSBhbmQgYXNzb2NpYXRlZCBkb2N1bWVudGF0aW9uCi0gKiBmaWxlcyAodGhlICJTb2Z0d2FyZSIp LCB0byBkZWFsIGluIHRoZSBTb2Z0d2FyZSB3aXRob3V0Ci0gKiByZXN0cmljdGlvbiwgaW5jbHVk aW5nIHdpdGhvdXQgbGltaXRhdGlvbiB0aGUgcmlnaHRzIHRvIHVzZSwKLSAqIGNvcHksIG1vZGlm eSwgbWVyZ2UsIHB1Ymxpc2gsIGRpc3RyaWJ1dGUsIHN1YmxpY2Vuc2UsIGFuZC9vciBzZWxsCi0g KiBjb3BpZXMgb2YgdGhlIFNvZnR3YXJlLCBhbmQgdG8gcGVybWl0IHBlcnNvbnMgdG8gd2hvbSB0 aGUKLSAqIFNvZnR3YXJlIGlzIGZ1cm5pc2hlZCB0byBkbyBzbywgc3ViamVjdCB0byB0aGUgZm9s bG93aW5nCi0gKiBjb25kaXRpb25zOgotICogCi0gKiBUaGUgYWJvdmUgY29weXJpZ2h0IG5vdGlj ZSBhbmQgdGhpcyBwZXJtaXNzaW9uIG5vdGljZSBzaGFsbCBiZQotICogaW5jbHVkZWQgaW4gYWxs IGNvcGllcyBvciBzdWJzdGFudGlhbCBwb3J0aW9ucyBvZiB0aGUgU29mdHdhcmUuCi0gKiAKLSAq IFRIRSBTT0ZUV0FSRSBJUyBQUk9WSURFRCAiQVMgSVMiLCBXSVRIT1VUIFdBUlJBTlRZIE9GIEFO WSBLSU5ELAotICogRVhQUkVTUyBPUiBJTVBMSUVELCBJTkNMVURJTkcgQlVUIE5PVCBMSU1JVEVE IFRPIFRIRSBXQVJSQU5USUVTCi0gKiBPRiBNRVJDSEFOVEFCSUxJVFksIEZJVE5FU1MgRk9SIEEg UEFSVElDVUxBUiBQVVJQT1NFIEFORAotICogTk9OSU5GUklOR0VNRU5ULiBJTiBOTyBFVkVOVCBT SEFMTCBUSEUgQVVUSE9SUyBPUiBDT1BZUklHSFQKLSAqIEhPTERFUlMgQkUgTElBQkxFIEZPUiBB TlkgQ0xBSU0sIERBTUFHRVMgT1IgT1RIRVIgTElBQklMSVRZLAotICogV0hFVEhFUiBJTiBBTiBB Q1RJT04gT0YgQ09OVFJBQ1QsIFRPUlQgT1IgT1RIRVJXSVNFLCBBUklTSU5HCi0gKiBGUk9NLCBP VVQgT0YgT1IgSU4gQ09OTkVDVElPTiBXSVRIIFRIRSBTT0ZUV0FSRSBPUiBUSEUgVVNFIE9SCi0g KiBPVEhFUiBERUFMSU5HUyBJTiBUSEUgU09GVFdBUkUuCisgKiBTZWUgYWxzbyBodHRwczovL2Vu Lndpa2lwZWRpYS5vcmcvd2lraS9Yb3JzaGlmdC4KICAqLwogCiAjaWZuZGVmIFdlYWtSYW5kb21f aAogI2RlZmluZSBXZWFrUmFuZG9tX2gKIAogI2luY2x1ZGUgPGxpbWl0cy5oPgotI2luY2x1ZGUg PHd0Zi9SYW5kb21OdW1iZXIuaD4KKyNpbmNsdWRlIDx3dGYvQ3J5cHRvZ3JhcGhpY2FsbHlSYW5k b21OdW1iZXIuaD4KICNpbmNsdWRlIDx3dGYvU3RkTGliRXh0cmFzLmg+CiAKIG5hbWVzcGFjZSBX VEYgewogCiBjbGFzcyBXZWFrUmFuZG9tIHsKIHB1YmxpYzoKLSAgICBXZWFrUmFuZG9tKCkKKyAg ICBXZWFrUmFuZG9tKHVuc2lnbmVkIHNlZWQgPSBjcnlwdG9ncmFwaGljYWxseVJhbmRvbU51bWJl cigpKQogICAgIHsKLSAgICAgICAgaW5pdGlhbGl6ZVNlZWQocmFuZG9tTnVtYmVyKCkgKiAoc3Rk OjpudW1lcmljX2xpbWl0czx1bnNpZ25lZD46Om1heCgpICsgMS4wKSk7CisgICAgICAgIHNldFNl ZWQoc2VlZCk7CiAgICAgfQotICAgIAotICAgIFdlYWtSYW5kb20odW5zaWduZWQgc2VlZCkKLSAg ICB7Ci0gICAgICAgIGluaXRpYWxpemVTZWVkKHNlZWQpOwotICAgIH0KLSAgICAKLSAgICB2b2lk IGluaXRpYWxpemVTZWVkKHVuc2lnbmVkIHNlZWQpCisKKyAgICB2b2lkIHNldFNlZWQodW5zaWdu ZWQgc2VlZCkKICAgICB7Ci0gICAgICAgIG1fbG93ID0gc2VlZCBeIDB4NDk2MTZFNDI7CisgICAg ICAgIG1fc2VlZCA9IHNlZWQ7CisKKyAgICAgICAgLy8gQSB6ZXJvIHNlZWQgd291bGQgY2F1c2Ug YW4gaW5maW5pdGUgc2VyaWVzIG9mIHplcm9lcy4KKyAgICAgICAgaWYgKCFzZWVkKQorICAgICAg ICAgICAgc2VlZCA9IDE7CisKKyAgICAgICAgbV9sb3cgPSBzZWVkOwogICAgICAgICBtX2hpZ2gg PSBzZWVkOwogICAgIH0KIAotICAgIC8vIFJldHVybnMgdGhlIHNlZWQgcHJvdmlkZWQgdGhhdCB5 b3UndmUgbmV2ZXIgY2FsbGVkIGdldCgpIG9yIGdldFVpbnQzMigpLgotICAgIHVuc2lnbmVkIHNl ZWRVbnNhZmUoKSBjb25zdCB7IHJldHVybiBtX2hpZ2g7IH0KKyAgICB1bnNpZ25lZCBzZWVkKCkg Y29uc3QgeyByZXR1cm4gbV9zZWVkOyB9CiAKICAgICBkb3VibGUgZ2V0KCkKICAgICB7Ci0gICAg ICAgIHJldHVybiBhZHZhbmNlKCkgLyAoVUlOVF9NQVggKyAxLjApOworICAgICAgICByZXR1cm4g YWR2YW5jZSgpIC8gKHN0ZDo6bnVtZXJpY19saW1pdHM8dWludDY0X3Q+OjptYXgoKSArIDEuMCk7 CiAgICAgfQogCiAgICAgdW5zaWduZWQgZ2V0VWludDMyKCkKICAgICB7Ci0gICAgICAgIHJldHVy biBhZHZhbmNlKCk7CisgICAgICAgIHJldHVybiBzdGF0aWNfY2FzdDx1bnNpZ25lZD4oYWR2YW5j ZSgpKTsKICAgICB9CiAKICAgICB1bnNpZ25lZCBnZXRVaW50MzIodW5zaWduZWQgbGltaXQpCiAg ICAgewogICAgICAgICBpZiAobGltaXQgPD0gMSkKICAgICAgICAgICAgIHJldHVybiAwOwotICAg ICAgICB1aW50NjRfdCBjdXRvZmYgPSAoc3RhdGljX2Nhc3Q8dWludDY0X3Q+KFVJTlRfTUFYKSAr IDEpIC8gbGltaXQgKiBsaW1pdDsKKyAgICAgICAgdWludDY0X3QgY3V0b2ZmID0gKHN0YXRpY19j YXN0PHVpbnQ2NF90PihzdGQ6Om51bWVyaWNfbGltaXRzPHVuc2lnbmVkPjo6bWF4KCkpICsgMSkg LyBsaW1pdCAqIGxpbWl0OwogICAgICAgICBmb3IgKDs7KSB7CiAgICAgICAgICAgICB1aW50NjRf dCB2YWx1ZSA9IGdldFVpbnQzMigpOwogICAgICAgICAgICAgaWYgKHZhbHVlID49IGN1dG9mZikK QEAgLTEwMSwxNiArODIsMjEgQEAgcHVibGljOgogICAgIH0KIAogcHJpdmF0ZToKLSAgICB1bnNp Z25lZCBhZHZhbmNlKCkKKyAgICB1aW50NjRfdCBhZHZhbmNlKCkKICAgICB7Ci0gICAgICAgIG1f aGlnaCA9IChtX2hpZ2ggPDwgMTYpICsgKG1faGlnaCA+PiAxNik7Ci0gICAgICAgIG1faGlnaCAr PSBtX2xvdzsKLSAgICAgICAgbV9sb3cgKz0gbV9oaWdoOwotICAgICAgICByZXR1cm4gbV9oaWdo OworICAgICAgICB1aW50NjRfdCB4ID0gbV9sb3c7CisgICAgICAgIHVpbnQ2NF90IHkgPSBtX2hp Z2g7CisgICAgICAgIG1fbG93ID0geTsKKyAgICAgICAgeCBePSB4IDw8IDIzOworICAgICAgICB4 IF49IHggPj4gMTc7CisgICAgICAgIHggXj0geSBeICh5ID4+IDI2KTsKKyAgICAgICAgbV9oaWdo ID0geDsKKyAgICAgICAgcmV0dXJuIHggKyB5OwogICAgIH0KIAotICAgIHVuc2lnbmVkIG1fbG93 OwotICAgIHVuc2lnbmVkIG1faGlnaDsKKyAgICB1bnNpZ25lZCBtX3NlZWQ7CisgICAgdWludDY0 X3QgbV9sb3c7CisgICAgdWludDY0X3QgbV9oaWdoOwogfTsKIAogfSAvLyBuYW1lc3BhY2UgV1RG Cg==