216101 2020-09-02 14:53:31 -0700 Make TransformationMatrix::inverse() faster in the case of affine transformation matrices 2020-09-03 07:21:18 -0700 1 1 1 Unclassified WebKit WebCore Misc. WebKit Nightly Build Unspecified Unspecified RESOLVED FIXED InRadar P2 Normal --- 1 wenson_hsieh wenson_hsieh dino koivisto sam simon.fraser thorton webkit-bug-importer oldest_to_newest 1685011 0 wenson_hsieh 2020-09-02 14:53:31 -0700 This function currently computes the inverse transformation using a generic algorithm for 4x4 matrices. 1685024 1 407822 wenson_hsieh 2020-09-02 15:23:05 -0700 Created attachment 407822 Patch 1685050 2 407822 sam 2020-09-02 16:12:46 -0700 Comment on attachment 407822 Patch Fun. Our of curiosity, did you try / benchmark using something like simd_inverse(simd_double4x4) (or try rolling your own simd inverse, there are few good resources on this - https://lxjk.github.io/2017/09/03/Fast-4x4-Matrix-Inverse-with-SSE-SIMD-Explained.html, https://github.com/niswegmann/small-matrix-inverse) for the general case? 1685056 3 wenson_hsieh 2020-09-02 16:26:43 -0700 (In reply to Sam Weinig from comment #2) > Comment on attachment 407822 [details] > Patch > > Fun. Our of curiosity, did you try / benchmark using something like > simd_inverse(simd_double4x4) (or try rolling your own simd inverse, there > are few good resources on this - > https://lxjk.github.io/2017/09/03/Fast-4x4-Matrix-Inverse-with-SSE-SIMD- > Explained.html, https://github.com/niswegmann/small-matrix-inverse) for the > general case? Ah, so I did look into doing something similar to this briefly (like we do in TransformationMatrix::multiply), but decided to stick with this because it was platform/architecture-agnostic, simpler to implement, and non-affine transformation matrices are relatively uncommon vs. affine transformation matrices. That said, as I continue hunting for progression opportunities, I think we can apply these techniques to some other hot codepaths around the vicinity (e.g. TransformationMatrix::map*()). 1685082 4 sam 2020-09-02 17:54:38 -0700 (In reply to Wenson Hsieh from comment #3) > (In reply to Sam Weinig from comment #2) > > Comment on attachment 407822 [details] > > Patch > > > > Fun. Our of curiosity, did you try / benchmark using something like > > simd_inverse(simd_double4x4) (or try rolling your own simd inverse, there > > are few good resources on this - > > https://lxjk.github.io/2017/09/03/Fast-4x4-Matrix-Inverse-with-SSE-SIMD- > > Explained.html, https://github.com/niswegmann/small-matrix-inverse) for the > > general case? > > Ah, so I did look into doing something similar to this briefly (like we do > in TransformationMatrix::multiply), but decided to stick with this because > it was platform/architecture-agnostic, simpler to implement, and non-affine > transformation matrices are relatively uncommon vs. affine transformation > matrices. > > That said, as I continue hunting for progression opportunities, I think we > can apply these techniques to some other hot codepaths around the vicinity > (e.g. TransformationMatrix::map*()). Ok. We are going to need to start thinking more about how we want to work with simd types in WebCore over time, as we are definitely leaving perf on the table. Doing what TransformationMatrix::multiply() does (inlining #ifdef'd assembly and intrinsics) is probably not a very scalable or reusable solution. I think we will will likely want to build out a bunch of primitives (similar to what Darwin's simd provides) and have good fallback. More related to this change, can the new logic be used to optimize TransformationMatrix::isInvertible() for the affine case? 1685099 5 wenson_hsieh 2020-09-02 18:29:16 -0700 (In reply to Sam Weinig from comment #4) > (In reply to Wenson Hsieh from comment #3) > > (In reply to Sam Weinig from comment #2) > > > Comment on attachment 407822 [details] > > > Patch > > > > > > Fun. Our of curiosity, did you try / benchmark using something like > > > simd_inverse(simd_double4x4) (or try rolling your own simd inverse, there > > > are few good resources on this - > > > https://lxjk.github.io/2017/09/03/Fast-4x4-Matrix-Inverse-with-SSE-SIMD- > > > Explained.html, https://github.com/niswegmann/small-matrix-inverse) for the > > > general case? > > > > Ah, so I did look into doing something similar to this briefly (like we do > > in TransformationMatrix::multiply), but decided to stick with this because > > it was platform/architecture-agnostic, simpler to implement, and non-affine > > transformation matrices are relatively uncommon vs. affine transformation > > matrices. > > > > That said, as I continue hunting for progression opportunities, I think we > > can apply these techniques to some other hot codepaths around the vicinity > > (e.g. TransformationMatrix::map*()). > > Ok. We are going to need to start thinking more about how we want to work > with simd types in WebCore over time, as we are definitely leaving perf on > the table. Doing what TransformationMatrix::multiply() does (inlining > #ifdef'd assembly and intrinsics) is probably not a very scalable or > reusable solution. I think we will will likely want to build out a bunch of > primitives (similar to what Darwin's simd provides) and have good fallback. This sounds great! I plan to experiment more with this. > > More related to this change, can the new logic be used to optimize > TransformationMatrix::isInvertible() for the affine case? Good point — I think that is very likely, though this only showed up a little bit in traces. I suspect that is because it only computes the determinant and not the adjoint matrix, the latter of which contains the bulk of the expense (~720 floating point multiplies and adds/subtracts, and the former with about 187). I should be able to bring this down to just 2 multiplications and 1 subtraction for the affine transform case. Some quick experiments showed that it is called ~7-8 million times in this test (roughly as many times as invert()), so it seems like it would be worth optimizing as well. I’ll do some perf testing and see! 1685113 6 wenson_hsieh 2020-09-02 19:29:04 -0700 (In reply to Wenson Hsieh from comment #5) > (In reply to Sam Weinig from comment #4) > > (In reply to Wenson Hsieh from comment #3) > > > (In reply to Sam Weinig from comment #2) > > > > Comment on attachment 407822 [details] > > > > Patch > > > > > > > > Fun. Our of curiosity, did you try / benchmark using something like > > > > simd_inverse(simd_double4x4) (or try rolling your own simd inverse, there > > > > are few good resources on this - > > > > https://lxjk.github.io/2017/09/03/Fast-4x4-Matrix-Inverse-with-SSE-SIMD- > > > > Explained.html, https://github.com/niswegmann/small-matrix-inverse) for the > > > > general case? > > > > > > Ah, so I did look into doing something similar to this briefly (like we do > > > in TransformationMatrix::multiply), but decided to stick with this because > > > it was platform/architecture-agnostic, simpler to implement, and non-affine > > > transformation matrices are relatively uncommon vs. affine transformation > > > matrices. > > > > > > That said, as I continue hunting for progression opportunities, I think we > > > can apply these techniques to some other hot codepaths around the vicinity > > > (e.g. TransformationMatrix::map*()). > > > > Ok. We are going to need to start thinking more about how we want to work > > with simd types in WebCore over time, as we are definitely leaving perf on > > the table. Doing what TransformationMatrix::multiply() does (inlining > > #ifdef'd assembly and intrinsics) is probably not a very scalable or > > reusable solution. I think we will will likely want to build out a bunch of > > primitives (similar to what Darwin's simd provides) and have good fallback. > > This sounds great! I plan to experiment more with this. > > > > > More related to this change, can the new logic be used to optimize > > TransformationMatrix::isInvertible() for the affine case? > > Good point — I think that is very likely, though this only showed up a > little bit in traces. I suspect that is because it only computes the > determinant and not the adjoint matrix, the latter of which contains the > bulk of the expense (~720 floating point multiplies and adds/subtracts, and > the former with about 187). I should be able to bring this down to just 2 > multiplications and 1 subtraction for the affine transform case. > > Some quick experiments showed that it is called ~7-8 million times in this > test (roughly as many times as invert()), so it seems like it would be worth > optimizing as well. I’ll do some perf testing and see! Results are more or less the same compared to just optimizing TransformationMatrix::inverse(), but I’ll include isInvertible in this patch as well, as it does seem to reduce the amount of time spent in that function (from looking at resulting artraces). 1685115 7 407851 wenson_hsieh 2020-09-02 19:36:50 -0700 Created attachment 407851 Patch 1685249 8 ews-feeder 2020-09-03 07:20:30 -0700 Committed r266513: <https://trac.webkit.org/changeset/266513> All reviewed patches have been landed. Closing bug and clearing flags on attachment 407851. 1685250 9 webkit-bug-importer 2020-09-03 07:21:18 -0700 <rdar://problem/68277416> 407822 2020-09-02 15:23:05 -0700 2020-09-02 19:36:48 -0700 Patch bug-216101-20200902152304.patch text/plain 5738 wenson_hsieh U3VidmVyc2lvbiBSZXZpc2lvbjogMjY2MzgzCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggM2ExZWU1Njg3ODkxYTZk ZDNkZTIxZWMxYWExN2E1NDIyMDAyNTExMi4uODZjZTFjNTZkMzhmYzg4N2Q5Zjg0ZDIwZDA1Yjhh MmZkZmJmMjIwMiAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSwzICsxLDM5IEBACisyMDIwLTA5LTAyICBXZW5z b24gSHNpZWggIDx3ZW5zb25faHNpZWhAYXBwbGUuY29tPgorCisgICAgICAgIE1ha2UgVHJhbnNm b3JtYXRpb25NYXRyaXg6OmludmVyc2UoKSBmYXN0ZXIgaW4gdGhlIGNhc2Ugb2YgYWZmaW5lIHRy YW5zZm9ybWF0aW9uIG1hdHJpY2VzCisgICAgICAgIGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3No b3dfYnVnLmNnaT9pZD0yMTYxMDEKKworICAgICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMh KS4KKworICAgICAgICBUaGUgTXVsdGlwbHkgc3VidGVzdCBvZiBNb3Rpb25NYXJrIHBsYWNlcyBh IGxhcmdlIG51bWJlciBvZiBlbGVtZW50cyB0aGF0IGFyZSBhbGwgcm90YXRlZCBieSBzb21lIGFu Z2xlOyB3aGVuCisgICAgICAgIHBhaW50aW5nIHRoZXNlLCB3ZSBjdXJyZW50bHkgc3BlbmQgYWJv dXQgNyUgb2YgdGhlIHRpbWUgdW5kZXIgYFJlbmRlckxheWVyOjpwYWludExheWVyQnlBcHBseWlu Z1RyYW5zZm9ybWAganVzdAorICAgICAgICBpbnZlcnRpbmcgdGhlIHRyYW5zZm9ybWF0aW9uIG1h dHJpeCAodW5kZXJuZWF0aCBgVHJhbnNmb3JtYXRpb25NYXRyaXg6OmludmVyc2UoKWApIHNvIHRo YXQgd2UgY2FuIG1hcCB0aGUgYm91bmRzCisgICAgICAgIG9mIHRoZSBkaXJ0eSByZWN0IHRocm91 Z2ggdGhpcyBpbnZlcnNlLgorCisgICAgICAgIGBUcmFuc2Zvcm1hdGlvbk1hdHJpeDo6aW52ZXJz ZSgpYCBjdXJyZW50bHkgaGFzIGEgZmFzdCBwYXRoIGZvciBpZGVudGl0eSBhbmQgdHJhbnNsYXRp b24gbWF0cmljZXMgdGhhdCBhdm9pZHMKKyAgICAgICAgaGF2aW5nIHRvIGZhbGwgYmFjayB0byB0 aGUgZ2VuZXJhbGl6ZWQgNC1ieS00IG1hdHJpeCBpbnZlcnNlIGVxdWF0aW9uOyB0aGlzIGdlbmVy YWxpemVkIGFsZ29yaXRobSB3b3JrcyBieQorICAgICAgICBkaXZpZGluZyB0aGUgZW50aXJlIGFk am9pbnQgbWF0cml4IGJ5IHRoZSBkZXRlcm1pbmFudCwgYSBwcm9jZXNzIHRoYXQgaW52b2x2ZXMg bmVhcmx5IDEwMDAgZmxvYXRpbmcgcG9pbnQKKyAgICAgICAgYWRkaXRpb25zIGFuZCBtdWx0aXBs aWNhdGlvbnMuCisKKyAgICAgICAgSG93ZXZlciwgaW4gdGhpcyBjYXNlLCBhbGwgb2YgdGhlIG1h dHJpY2VzIGFyZSBhIGNvbWJpbmF0aW9uIG9mIHRyYW5zbGF0aW9ucyBhbmQgcm90YXRpb25zLCB3 aGljaCBhbGwgcmVzdWx0IGluCisgICAgICAgIGFmZmluZSB0cmFuc2Zvcm1hdGlvbnMuIEFzIHN1 Y2gsIHRoZXJlJ3Mgbm8gbmVlZCB0byBmYWxsIGJhY2sgdG8gdGhlIGdlbmVyYWxpemVkIGFsZ29y aXRobSBmb3IgY29tcHV0aW5nIHRoZQorICAgICAgICBpbnZlcnNlOyBpbnN0ZWFkLCB3ZSBjYW4g YmFpbCBlYXJseSB3aXRoIHNpbXBsZXIgc3RyYXRlZ3kgdGhhdCBvbmx5IHJlcXVpcmVzIDE1IGZs b2F0aW5nIHBvaW50IGFkZGl0aW9ucyBhbmQKKyAgICAgICAgbXVsdGlwbGljYXRpb25zLgorCisg ICAgICAgIFdlIGNhbiBhbHNvIHRha2UgYWR2YW50YW5nZSBvZiB0aGUgZmFjdCB0aGF0IHdlIGN1 cnJlbnRseSBnbyB0aHJvdWdoIG1vc3Qgb2YgdGhlIGVudHJpZXMgaW4gdGhlIDR4NCBtYXRyaXgg dG8KKyAgICAgICAgZGV0ZXJtaW5lIHdoZXRoZXIgdGhlIG1hdHJpeCBpcyBhbiBpZGVudGl0eSBv ciB0cmFuc2xhdGlvbiBtYXRyaXgsIGJ5IGludHJvZHVjaW5nIGEgbmV3IGhlbHBlciBtZXRob2Qg dGhhdAorICAgICAgICByZXR1cm5zIG5vdCBvbmx5IHdoZXRoZXIgdGhlIG1hdHJpeCBpcyB0aGUg aWRlbnRpdHkgbWF0cml4IG9yIHRyYW5zbGF0aW9uLCBidXQgYWxzbyB3aGV0aGVyIHRoZSBtYXRy aXggaXMgYWZmaW5lCisgICAgICAgIChieSB0aGUgZGVmaW5pdGlvbiBvZiBgVHJhbnNmb3JtYXRp b25NYXRyaXg6OmlzQWZmaW5lKClgKS4gU2luY2UgbW9zdCBvZiB0aGUgZW50cmllcyB0aGF0IG5l ZWQgdG8gYmUgMSBvciAwIGluCisgICAgICAgIG9yZGVyIGZvciBhIG1hdHJpeCB0byBiZSBhIHRy YW5zbGF0aW9uIG1hdHJpeCB2cy4ganVzdCBhbiBhZmZpbmUgdHJhbnNmb3JtYXRpb24gbWF0cml4 IGFyZSB0aGUgc2FtZSwgdGhpcyBoZWxwcworICAgICAgICBhdm9pZCBzb21lIHJlZHVuZGFudCBj aGVja3MgaW4gYFRyYW5zZm9ybWF0aW9uTWF0cml4OjppbnZlcnNlKClgLgorCisgICAgICAgIEkg bWVhc3VyZWQgdGhpcyBsb2NhbGx5IHRvIGJlIGEgKHN0YXRpc3RpY2FsbHkgc2lnbmlmaWNhbnQp IDIlIGltcHJvdmVtZW50IG9uIE11bHRpcGx5LgorCisgICAgICAgICogcGxhdGZvcm0vZ3JhcGhp Y3MvdHJhbnNmb3Jtcy9UcmFuc2Zvcm1hdGlvbk1hdHJpeC5jcHA6CisgICAgICAgIChXZWJDb3Jl OjpUcmFuc2Zvcm1hdGlvbk1hdHJpeDo6aW52ZXJzZSBjb25zdCk6CisgICAgICAgICogcGxhdGZv cm0vZ3JhcGhpY3MvdHJhbnNmb3Jtcy9UcmFuc2Zvcm1hdGlvbk1hdHJpeC5oOgorICAgICAgICAo V2ViQ29yZTo6VHJhbnNmb3JtYXRpb25NYXRyaXg6OnR5cGUgY29uc3QpOgorCiAyMDIwLTA4LTMx ICBNYXJrIExhbSAgPG1hcmsubGFtQGFwcGxlLmNvbT4KIAogICAgICAgICBNaXNzaW5nIGV4Y2Vw dGlvbiBjaGVjayB3aGlsZSBoYW5kbGluZyB0aGUgb25iZWZvcmV1bmxvYWQgZXZlbnQuCmRpZmYg LS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9wbGF0Zm9ybS9ncmFwaGljcy90cmFuc2Zvcm1zL1RyYW5z Zm9ybWF0aW9uTWF0cml4LmNwcCBiL1NvdXJjZS9XZWJDb3JlL3BsYXRmb3JtL2dyYXBoaWNzL3Ry YW5zZm9ybXMvVHJhbnNmb3JtYXRpb25NYXRyaXguY3BwCmluZGV4IGMxNDdhMzk3ZWU3MmRhNjAz NzhiNmM1NWQzOTAyNDc2MzcwY2E3MzguLjljOWU1YzczZTZhMjdmYzE3YmNkZmM4OTE2NzJkZjY0 YjZlODFmYTUgMTAwNjQ0Ci0tLSBhL1NvdXJjZS9XZWJDb3JlL3BsYXRmb3JtL2dyYXBoaWNzL3Ry YW5zZm9ybXMvVHJhbnNmb3JtYXRpb25NYXRyaXguY3BwCisrKyBiL1NvdXJjZS9XZWJDb3JlL3Bs YXRmb3JtL2dyYXBoaWNzL3RyYW5zZm9ybXMvVHJhbnNmb3JtYXRpb25NYXRyaXguY3BwCkBAIC0x NDcyLDcgKzE0NzIsOCBAQCBib29sIFRyYW5zZm9ybWF0aW9uTWF0cml4Ojppc0ludmVydGlibGUo KSBjb25zdAogCiBPcHRpb25hbDxUcmFuc2Zvcm1hdGlvbk1hdHJpeD4gVHJhbnNmb3JtYXRpb25N YXRyaXg6OmludmVyc2UoKSBjb25zdAogewotICAgIGlmIChpc0lkZW50aXR5T3JUcmFuc2xhdGlv bigpKSB7CisgICAgYXV0byB0eXBlID0gdGhpcy0+dHlwZSgpOworICAgIGlmICh0eXBlID09IFR5 cGU6OklkZW50aXR5T3JUcmFuc2xhdGlvbikgewogICAgICAgICAvLyBpZGVudGl0eSBtYXRyaXgK ICAgICAgICAgaWYgKG1fbWF0cml4WzNdWzBdID09IDAgJiYgbV9tYXRyaXhbM11bMV0gPT0gMCAm JiBtX21hdHJpeFszXVsyXSA9PSAwKQogICAgICAgICAgICAgcmV0dXJuIFRyYW5zZm9ybWF0aW9u TWF0cml4KCk7CkBAIC0xNDg0LDYgKzE0ODUsMjQgQEAgT3B0aW9uYWw8VHJhbnNmb3JtYXRpb25N YXRyaXg+IFRyYW5zZm9ybWF0aW9uTWF0cml4OjppbnZlcnNlKCkgY29uc3QKICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgIC1tX21hdHJpeFszXVswXSwgLW1fbWF0cml4WzNdWzFd LCAtbV9tYXRyaXhbM11bMl0sIDEpOwogICAgIH0KIAorICAgIGlmICh0eXBlID09IFR5cGU6OkFm ZmluZSkgeworICAgICAgICBkb3VibGUgYSA9IG0xMSgpOworICAgICAgICBkb3VibGUgYiA9IG0x MigpOworICAgICAgICBkb3VibGUgYyA9IG0yMSgpOworICAgICAgICBkb3VibGUgZCA9IG0yMigp OworICAgICAgICBkb3VibGUgZSA9IG00MSgpOworICAgICAgICBkb3VibGUgZiA9IG00MigpOwor ICAgICAgICBkb3VibGUgaW52ZXJzZURldGVybWluYW50ID0gMSAvIChhICogZCAtIGIgKiBjKTsK KyAgICAgICAgcmV0dXJuIHt7CisgICAgICAgICAgICBkICogaW52ZXJzZURldGVybWluYW50LAor ICAgICAgICAgICAgLWIgKiBpbnZlcnNlRGV0ZXJtaW5hbnQsCisgICAgICAgICAgICAtYyAqIGlu dmVyc2VEZXRlcm1pbmFudCwKKyAgICAgICAgICAgIGEgKiBpbnZlcnNlRGV0ZXJtaW5hbnQsCisg ICAgICAgICAgICAoYyAqIGYgLSBkICogZSkgKiBpbnZlcnNlRGV0ZXJtaW5hbnQsCisgICAgICAg ICAgICAoYiAqIGUgLSBhICogZikgKiBpbnZlcnNlRGV0ZXJtaW5hbnQKKyAgICAgICAgfX07Cisg ICAgfQorCiAgICAgVHJhbnNmb3JtYXRpb25NYXRyaXggaW52TWF0OwogICAgIC8vIEZJWE1FOiBV c2UgTFUgZGVjb21wb3NpdGlvbiB0byBhcHBseSB0aGUgaW52ZXJzZSBpbnN0ZWFkIG9mIGNhbGN1 bGF0aW5nIHRoZSBpbnZlcnNlIGV4cGxpY2l0bHkuCiAgICAgLy8gQ2FsY3VsYXRpbmcgdGhlIGlu dmVyc2Ugb2YgYSA0eDQgbWF0cml4IHVzaW5nIGNvZmFjdG9ycyBpcyBudW1lcmljYWxseSB1bnN0 YWJsZSBhbmQgdW5uZWNlc3NhcnkgdG8gYXBwbHkgdGhlIGludmVyc2UgdHJhbnNmb3JtYXRpb24g dG8gYSBwb2ludC4KZGlmZiAtLWdpdCBhL1NvdXJjZS9XZWJDb3JlL3BsYXRmb3JtL2dyYXBoaWNz L3RyYW5zZm9ybXMvVHJhbnNmb3JtYXRpb25NYXRyaXguaCBiL1NvdXJjZS9XZWJDb3JlL3BsYXRm b3JtL2dyYXBoaWNzL3RyYW5zZm9ybXMvVHJhbnNmb3JtYXRpb25NYXRyaXguaAppbmRleCBjNzFm NDRhODliNDExM2MwN2Y5YzVjNTMxNWIyNzQxMTMyMzIzOGJhLi5jZGQ1MmJjYTQyZjA5MDY3ODlh ZDRhZWMxZGFhOWYyOWJjNjRkYzNiIDEwMDY0NAotLS0gYS9Tb3VyY2UvV2ViQ29yZS9wbGF0Zm9y bS9ncmFwaGljcy90cmFuc2Zvcm1zL1RyYW5zZm9ybWF0aW9uTWF0cml4LmgKKysrIGIvU291cmNl L1dlYkNvcmUvcGxhdGZvcm0vZ3JhcGhpY3MvdHJhbnNmb3Jtcy9UcmFuc2Zvcm1hdGlvbk1hdHJp eC5oCkBAIC00MzUsNiArNDM1LDIzIEBAIHByaXZhdGU6CiAgICAgICAgIHJldHVybiBGbG9hdFBv aW50M0Qoc3RhdGljX2Nhc3Q8ZmxvYXQ+KHJlc3VsdFgpLCBzdGF0aWNfY2FzdDxmbG9hdD4ocmVz dWx0WSksIHN0YXRpY19jYXN0PGZsb2F0PihyZXN1bHRaKSk7CiAgICAgfQogCisgICAgZW51bSBj bGFzcyBUeXBlIDogdWludDhfdCB7CisgICAgICAgIElkZW50aXR5T3JUcmFuc2xhdGlvbiwKKyAg ICAgICAgQWZmaW5lLAorICAgICAgICBPdGhlcgorICAgIH07CisKKyAgICBUeXBlIHR5cGUoKSBj b25zdAorICAgIHsKKyAgICAgICAgaWYgKCFtMTMoKSAmJiAhbTE0KCkgJiYgIW0yMygpICYmICFt MjQoKSAmJiAhbTM0KCkgJiYgIW0zMSgpICYmICFtMzIoKSAmJiBtMzMoKSA9PSAxICYmIG00NCgp ID09IDEpIHsKKyAgICAgICAgICAgIGlmICghbTEyKCkgJiYgIW0yMSgpICYmIG0xMSgpID09IDEg JiYgbTIyKCkgPT0gMSkKKyAgICAgICAgICAgICAgICByZXR1cm4gVHlwZTo6SWRlbnRpdHlPclRy YW5zbGF0aW9uOworICAgICAgICAgICAgaWYgKCFtNDMoKSkKKyAgICAgICAgICAgICAgICByZXR1 cm4gVHlwZTo6QWZmaW5lOworICAgICAgICB9CisgICAgICAgIHJldHVybiBUeXBlOjpPdGhlcjsK KyAgICB9CisKICAgICBNYXRyaXg0IG1fbWF0cml4OwogfTsKIAo= 407851 2020-09-02 19:36:50 -0700 2020-09-03 07:20:30 -0700 Patch bug-216101-20200902193649.patch text/plain 6583 wenson_hsieh U3VidmVyc2lvbiBSZXZpc2lvbjogMjY2MzgzCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggM2ExZWU1Njg3ODkxYTZk ZDNkZTIxZWMxYWExN2E1NDIyMDAyNTExMi4uYmFmZGFiOTAxOWUyZDljOTA5NTRjNzllZGZlZjdh NTEzZmQ0OGM5NSAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSwzICsxLDQzIEBACisyMDIwLTA5LTAyICBXZW5z b24gSHNpZWggIDx3ZW5zb25faHNpZWhAYXBwbGUuY29tPgorCisgICAgICAgIE1ha2UgVHJhbnNm b3JtYXRpb25NYXRyaXg6OmludmVyc2UoKSBmYXN0ZXIgaW4gdGhlIGNhc2Ugb2YgYWZmaW5lIHRy YW5zZm9ybWF0aW9uIG1hdHJpY2VzCisgICAgICAgIGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3No b3dfYnVnLmNnaT9pZD0yMTYxMDEKKworICAgICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMh KS4KKworICAgICAgICBUaGUgTXVsdGlwbHkgc3VidGVzdCBvZiBNb3Rpb25NYXJrIHBsYWNlcyBh IGxhcmdlIG51bWJlciBvZiBlbGVtZW50cyB0aGF0IGFyZSBhbGwgcm90YXRlZCBieSBzb21lIGFu Z2xlOyB3aGVuCisgICAgICAgIHBhaW50aW5nIHRoZXNlLCB3ZSBjdXJyZW50bHkgc3BlbmQgYWJv dXQgNyUgb2YgdGhlIHRpbWUgdW5kZXIgYFJlbmRlckxheWVyOjpwYWludExheWVyQnlBcHBseWlu Z1RyYW5zZm9ybWAganVzdAorICAgICAgICBpbnZlcnRpbmcgdGhlIHRyYW5zZm9ybWF0aW9uIG1h dHJpeCAodW5kZXJuZWF0aCBgVHJhbnNmb3JtYXRpb25NYXRyaXg6OmludmVyc2UoKWApIHNvIHRo YXQgd2UgY2FuIG1hcCB0aGUgYm91bmRzCisgICAgICAgIG9mIHRoZSBkaXJ0eSByZWN0IHRocm91 Z2ggdGhpcyBpbnZlcnNlLgorCisgICAgICAgIGBUcmFuc2Zvcm1hdGlvbk1hdHJpeDo6aW52ZXJz ZSgpYCBjdXJyZW50bHkgaGFzIGEgZmFzdCBwYXRoIGZvciBpZGVudGl0eSBhbmQgdHJhbnNsYXRp b24gbWF0cmljZXMgdGhhdCBhdm9pZHMKKyAgICAgICAgaGF2aW5nIHRvIGZhbGwgYmFjayB0byB0 aGUgZ2VuZXJhbGl6ZWQgNC1ieS00IG1hdHJpeCBpbnZlcnNlIGVxdWF0aW9uOyB0aGlzIGdlbmVy YWxpemVkIGFsZ29yaXRobSB3b3JrcyBieQorICAgICAgICBkaXZpZGluZyB0aGUgZW50aXJlIGFk am9pbnQgbWF0cml4IGJ5IHRoZSBkZXRlcm1pbmFudCwgYSBwcm9jZXNzIHRoYXQgaW52b2x2ZXMg bmVhcmx5IDEwMDAgZmxvYXRpbmcgcG9pbnQKKyAgICAgICAgYWRkaXRpb25zIGFuZCBtdWx0aXBs aWNhdGlvbnMuCisKKyAgICAgICAgSG93ZXZlciwgaW4gdGhpcyBjYXNlLCBhbGwgb2YgdGhlIG1h dHJpY2VzIGFyZSBhIGNvbWJpbmF0aW9uIG9mIHRyYW5zbGF0aW9ucyBhbmQgcm90YXRpb25zLCB3 aGljaCBhbGwgcmVzdWx0IGluCisgICAgICAgIGFmZmluZSB0cmFuc2Zvcm1hdGlvbnMuIEFzIHN1 Y2gsIHRoZXJlJ3Mgbm8gbmVlZCB0byBmYWxsIGJhY2sgdG8gdGhlIGdlbmVyYWxpemVkIGFsZ29y aXRobSBmb3IgY29tcHV0aW5nIHRoZQorICAgICAgICBpbnZlcnNlOyBpbnN0ZWFkLCB3ZSBjYW4g YmFpbCBlYXJseSB3aXRoIHNpbXBsZXIgc3RyYXRlZ3kgdGhhdCBvbmx5IHJlcXVpcmVzIDE1IGZs b2F0aW5nIHBvaW50IGFkZGl0aW9ucyBhbmQKKyAgICAgICAgbXVsdGlwbGljYXRpb25zLgorCisg ICAgICAgIFdlIGNhbiBhbHNvIHRha2UgYWR2YW50YW5nZSBvZiB0aGUgZmFjdCB0aGF0IHdlIGN1 cnJlbnRseSBnbyB0aHJvdWdoIG1vc3Qgb2YgdGhlIGVudHJpZXMgaW4gdGhlIDR4NCBtYXRyaXgg dG8KKyAgICAgICAgZGV0ZXJtaW5lIHdoZXRoZXIgdGhlIG1hdHJpeCBpcyBhbiBpZGVudGl0eSBv ciB0cmFuc2xhdGlvbiBtYXRyaXgsIGJ5IGludHJvZHVjaW5nIGEgbmV3IGhlbHBlciBtZXRob2Qg dGhhdAorICAgICAgICByZXR1cm5zIG5vdCBvbmx5IHdoZXRoZXIgdGhlIG1hdHJpeCBpcyB0aGUg aWRlbnRpdHkgbWF0cml4IG9yIHRyYW5zbGF0aW9uLCBidXQgYWxzbyB3aGV0aGVyIHRoZSBtYXRy aXggaXMgYWZmaW5lCisgICAgICAgIChieSB0aGUgZGVmaW5pdGlvbiBvZiBgVHJhbnNmb3JtYXRp b25NYXRyaXg6OmlzQWZmaW5lKClgKS4gU2luY2UgbW9zdCBvZiB0aGUgZW50cmllcyB0aGF0IG5l ZWQgdG8gYmUgMSBvciAwIGluCisgICAgICAgIG9yZGVyIGZvciBhIG1hdHJpeCB0byBiZSBhIHRy YW5zbGF0aW9uIG1hdHJpeCB2cy4ganVzdCBhbiBhZmZpbmUgdHJhbnNmb3JtYXRpb24gbWF0cml4 IGFyZSB0aGUgc2FtZSwgdGhpcyBoZWxwcworICAgICAgICBhdm9pZCBzb21lIHJlZHVuZGFudCBj aGVja3MgaW4gYFRyYW5zZm9ybWF0aW9uTWF0cml4OjppbnZlcnNlKClgLgorCisgICAgICAgIFdl IGFsc28gYXBwbHkgYSBzaW1pbGFyIG9wdGltaXphdGlvbiB0byBgVHJhbnNmb3JtYXRpb25NYXRy aXg6OmlzSW52ZXJ0aWJsZSgpYCwgcmVkdWNpbmcgdGhlIG11bHRpcGxpY2F0aW9ucyBhbmQKKyAg ICAgICAgYWRkaXRpb25zIGZyb20gcm91Z2hseSAyMDAgdG8ganVzdCAzLgorCisgICAgICAgIEkg bWVhc3VyZWQgdGhpcyBsb2NhbGx5IHRvIGJlIGEgKHN0YXRpc3RpY2FsbHkgc2lnbmlmaWNhbnQp IDIlIGltcHJvdmVtZW50IG9uIE11bHRpcGx5LgorCisgICAgICAgICogcGxhdGZvcm0vZ3JhcGhp Y3MvdHJhbnNmb3Jtcy9UcmFuc2Zvcm1hdGlvbk1hdHJpeC5jcHA6CisgICAgICAgIChXZWJDb3Jl OjpUcmFuc2Zvcm1hdGlvbk1hdHJpeDo6aXNJbnZlcnRpYmxlIGNvbnN0KToKKyAgICAgICAgKFdl YkNvcmU6OlRyYW5zZm9ybWF0aW9uTWF0cml4OjppbnZlcnNlIGNvbnN0KToKKyAgICAgICAgKiBw bGF0Zm9ybS9ncmFwaGljcy90cmFuc2Zvcm1zL1RyYW5zZm9ybWF0aW9uTWF0cml4Lmg6CisgICAg ICAgIChXZWJDb3JlOjpUcmFuc2Zvcm1hdGlvbk1hdHJpeDo6dHlwZSBjb25zdCk6CisKIDIwMjAt MDgtMzEgIE1hcmsgTGFtICA8bWFyay5sYW1AYXBwbGUuY29tPgogCiAgICAgICAgIE1pc3Npbmcg ZXhjZXB0aW9uIGNoZWNrIHdoaWxlIGhhbmRsaW5nIHRoZSBvbmJlZm9yZXVubG9hZCBldmVudC4K ZGlmZiAtLWdpdCBhL1NvdXJjZS9XZWJDb3JlL3BsYXRmb3JtL2dyYXBoaWNzL3RyYW5zZm9ybXMv VHJhbnNmb3JtYXRpb25NYXRyaXguY3BwIGIvU291cmNlL1dlYkNvcmUvcGxhdGZvcm0vZ3JhcGhp Y3MvdHJhbnNmb3Jtcy9UcmFuc2Zvcm1hdGlvbk1hdHJpeC5jcHAKaW5kZXggYzE0N2EzOTdlZTcy ZGE2MDM3OGI2YzU1ZDM5MDI0NzYzNzBjYTczOC4uZmIyZjEzYTc4OTY2NmNjNGJkYzU3Y2RiYmRl ZGQwZTFhNDg1OGVmMiAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvcGxhdGZvcm0vZ3JhcGhp Y3MvdHJhbnNmb3Jtcy9UcmFuc2Zvcm1hdGlvbk1hdHJpeC5jcHAKKysrIGIvU291cmNlL1dlYkNv cmUvcGxhdGZvcm0vZ3JhcGhpY3MvdHJhbnNmb3Jtcy9UcmFuc2Zvcm1hdGlvbk1hdHJpeC5jcHAK QEAgLTE0NTksMjAgKzE0NTksMTcgQEAgdm9pZCBUcmFuc2Zvcm1hdGlvbk1hdHJpeDo6bXVsdFZl Y01hdHJpeChkb3VibGUgeCwgZG91YmxlIHksIGRvdWJsZSB6LCBkb3VibGUmIHIKIAogYm9vbCBU cmFuc2Zvcm1hdGlvbk1hdHJpeDo6aXNJbnZlcnRpYmxlKCkgY29uc3QKIHsKLSAgICBpZiAoaXNJ ZGVudGl0eU9yVHJhbnNsYXRpb24oKSkKKyAgICBhdXRvIHR5cGUgPSB0aGlzLT50eXBlKCk7Cisg ICAgaWYgKHR5cGUgPT0gVHlwZTo6SWRlbnRpdHlPclRyYW5zbGF0aW9uKQogICAgICAgICByZXR1 cm4gdHJ1ZTsKIAotICAgIGRvdWJsZSBkZXQgPSBXZWJDb3JlOjpkZXRlcm1pbmFudDR4NChtX21h dHJpeCk7Ci0KLSAgICBpZiAoZmFicyhkZXQpIDwgU01BTExfTlVNQkVSKQotICAgICAgICByZXR1 cm4gZmFsc2U7Ci0KLSAgICByZXR1cm4gdHJ1ZTsKKyAgICByZXR1cm4gZmFicyh0eXBlID09IFR5 cGU6OkFmZmluZSA/IChtMTEoKSAqIG0yMigpIC0gbTEyKCkgKiBtMjEoKSkgOiBXZWJDb3JlOjpk ZXRlcm1pbmFudDR4NChtX21hdHJpeCkpID49IFNNQUxMX05VTUJFUjsKIH0KIAogT3B0aW9uYWw8 VHJhbnNmb3JtYXRpb25NYXRyaXg+IFRyYW5zZm9ybWF0aW9uTWF0cml4OjppbnZlcnNlKCkgY29u c3QKIHsKLSAgICBpZiAoaXNJZGVudGl0eU9yVHJhbnNsYXRpb24oKSkgeworICAgIGF1dG8gdHlw ZSA9IHRoaXMtPnR5cGUoKTsKKyAgICBpZiAodHlwZSA9PSBUeXBlOjpJZGVudGl0eU9yVHJhbnNs YXRpb24pIHsKICAgICAgICAgLy8gaWRlbnRpdHkgbWF0cml4CiAgICAgICAgIGlmIChtX21hdHJp eFszXVswXSA9PSAwICYmIG1fbWF0cml4WzNdWzFdID09IDAgJiYgbV9tYXRyaXhbM11bMl0gPT0g MCkKICAgICAgICAgICAgIHJldHVybiBUcmFuc2Zvcm1hdGlvbk1hdHJpeCgpOwpAQCAtMTQ4NCw2 ICsxNDgxLDI4IEBAIE9wdGlvbmFsPFRyYW5zZm9ybWF0aW9uTWF0cml4PiBUcmFuc2Zvcm1hdGlv bk1hdHJpeDo6aW52ZXJzZSgpIGNvbnN0CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAtbV9tYXRyaXhbM11bMF0sIC1tX21hdHJpeFszXVsxXSwgLW1fbWF0cml4WzNdWzJdLCAx KTsKICAgICB9CiAKKyAgICBpZiAodHlwZSA9PSBUeXBlOjpBZmZpbmUpIHsKKyAgICAgICAgZG91 YmxlIGEgPSBtMTEoKTsKKyAgICAgICAgZG91YmxlIGIgPSBtMTIoKTsKKyAgICAgICAgZG91Ymxl IGMgPSBtMjEoKTsKKyAgICAgICAgZG91YmxlIGQgPSBtMjIoKTsKKyAgICAgICAgZG91YmxlIGUg PSBtNDEoKTsKKyAgICAgICAgZG91YmxlIGYgPSBtNDIoKTsKKyAgICAgICAgZG91YmxlIGRldGVy bWluYW50ID0gYSAqIGQgLSBiICogYzsKKyAgICAgICAgaWYgKGZhYnMoZGV0ZXJtaW5hbnQpIDwg U01BTExfTlVNQkVSKQorICAgICAgICAgICAgcmV0dXJuIFdURjo6bnVsbG9wdDsKKworICAgICAg ICBkb3VibGUgaW52ZXJzZURldGVybWluYW50ID0gMSAvIGRldGVybWluYW50OworICAgICAgICBy ZXR1cm4ge3sKKyAgICAgICAgICAgIGQgKiBpbnZlcnNlRGV0ZXJtaW5hbnQsCisgICAgICAgICAg ICAtYiAqIGludmVyc2VEZXRlcm1pbmFudCwKKyAgICAgICAgICAgIC1jICogaW52ZXJzZURldGVy bWluYW50LAorICAgICAgICAgICAgYSAqIGludmVyc2VEZXRlcm1pbmFudCwKKyAgICAgICAgICAg IChjICogZiAtIGQgKiBlKSAqIGludmVyc2VEZXRlcm1pbmFudCwKKyAgICAgICAgICAgIChiICog ZSAtIGEgKiBmKSAqIGludmVyc2VEZXRlcm1pbmFudAorICAgICAgICB9fTsKKyAgICB9CisKICAg ICBUcmFuc2Zvcm1hdGlvbk1hdHJpeCBpbnZNYXQ7CiAgICAgLy8gRklYTUU6IFVzZSBMVSBkZWNv bXBvc2l0aW9uIHRvIGFwcGx5IHRoZSBpbnZlcnNlIGluc3RlYWQgb2YgY2FsY3VsYXRpbmcgdGhl IGludmVyc2UgZXhwbGljaXRseS4KICAgICAvLyBDYWxjdWxhdGluZyB0aGUgaW52ZXJzZSBvZiBh IDR4NCBtYXRyaXggdXNpbmcgY29mYWN0b3JzIGlzIG51bWVyaWNhbGx5IHVuc3RhYmxlIGFuZCB1 bm5lY2Vzc2FyeSB0byBhcHBseSB0aGUgaW52ZXJzZSB0cmFuc2Zvcm1hdGlvbiB0byBhIHBvaW50 LgpkaWZmIC0tZ2l0IGEvU291cmNlL1dlYkNvcmUvcGxhdGZvcm0vZ3JhcGhpY3MvdHJhbnNmb3Jt cy9UcmFuc2Zvcm1hdGlvbk1hdHJpeC5oIGIvU291cmNlL1dlYkNvcmUvcGxhdGZvcm0vZ3JhcGhp Y3MvdHJhbnNmb3Jtcy9UcmFuc2Zvcm1hdGlvbk1hdHJpeC5oCmluZGV4IGM3MWY0NGE4OWI0MTEz YzA3ZjljNWM1MzE1YjI3NDExMzIzMjM4YmEuLmNkZDUyYmNhNDJmMDkwNjc4OWFkNGFlYzFkYWE5 ZjI5YmM2NGRjM2IgMTAwNjQ0Ci0tLSBhL1NvdXJjZS9XZWJDb3JlL3BsYXRmb3JtL2dyYXBoaWNz L3RyYW5zZm9ybXMvVHJhbnNmb3JtYXRpb25NYXRyaXguaAorKysgYi9Tb3VyY2UvV2ViQ29yZS9w bGF0Zm9ybS9ncmFwaGljcy90cmFuc2Zvcm1zL1RyYW5zZm9ybWF0aW9uTWF0cml4LmgKQEAgLTQz NSw2ICs0MzUsMjMgQEAgcHJpdmF0ZToKICAgICAgICAgcmV0dXJuIEZsb2F0UG9pbnQzRChzdGF0 aWNfY2FzdDxmbG9hdD4ocmVzdWx0WCksIHN0YXRpY19jYXN0PGZsb2F0PihyZXN1bHRZKSwgc3Rh dGljX2Nhc3Q8ZmxvYXQ+KHJlc3VsdFopKTsKICAgICB9CiAKKyAgICBlbnVtIGNsYXNzIFR5cGUg OiB1aW50OF90IHsKKyAgICAgICAgSWRlbnRpdHlPclRyYW5zbGF0aW9uLAorICAgICAgICBBZmZp bmUsCisgICAgICAgIE90aGVyCisgICAgfTsKKworICAgIFR5cGUgdHlwZSgpIGNvbnN0CisgICAg eworICAgICAgICBpZiAoIW0xMygpICYmICFtMTQoKSAmJiAhbTIzKCkgJiYgIW0yNCgpICYmICFt MzQoKSAmJiAhbTMxKCkgJiYgIW0zMigpICYmIG0zMygpID09IDEgJiYgbTQ0KCkgPT0gMSkgewor ICAgICAgICAgICAgaWYgKCFtMTIoKSAmJiAhbTIxKCkgJiYgbTExKCkgPT0gMSAmJiBtMjIoKSA9 PSAxKQorICAgICAgICAgICAgICAgIHJldHVybiBUeXBlOjpJZGVudGl0eU9yVHJhbnNsYXRpb247 CisgICAgICAgICAgICBpZiAoIW00MygpKQorICAgICAgICAgICAgICAgIHJldHVybiBUeXBlOjpB ZmZpbmU7CisgICAgICAgIH0KKyAgICAgICAgcmV0dXJuIFR5cGU6Ok90aGVyOworICAgIH0KKwog ICAgIE1hdHJpeDQgbV9tYXRyaXg7CiB9OwogCg==