196935 2019-04-15 14:30:16 -0700 Add an overflow check to HashTable 2019-04-16 22:23:57 -0700 1 1 1 Unclassified WebKit Web Template Framework WebKit Nightly Build Unspecified Unspecified NEW InRadar P2 Normal --- 197000 1 rniwa rniwa benjamin bfulgham cdumez cmarcelo darin dbates ews-watchlist fpizlo ggaren keith_miller saam webkit-bug-importer oldest_to_newest 1527406 0 rniwa 2019-04-15 14:30:16 -0700 We should check for an integer overflow when expanding HashTable. 1527596 1 367492 rniwa 2019-04-15 20:32:15 -0700 Created attachment 367492 Fixes the bug 1527597 2 webkit-bug-importer 2019-04-15 20:33:01 -0700 <rdar://problem/49928688> 1527607 3 367492 ggaren 2019-04-15 21:17:20 -0700 Comment on attachment 367492 Fixes the bug View in context: https://bugs.webkit.org/attachment.cgi?id=367492&action=review r=me > Source/WTF/wtf/HashTable.h:1206 > + Checked<unsigned, CrashOnOverflow> bestTableSize = WTF::roundUpToPowerOfTwo(keyCount); > + if (bestTableSize.unsafeGet() < keyCount) > + bestTableSize.overflowed(); > + bestTableSize *= 2; If we needed a check here, I would recommend doing using Checked<T>. But we don't need this less-than check. roundUpToPowerOfTwo(2^32) is 2^32. There's no overflow case. I think I would write this as auto bestTableSize = Checked<unsigned, CrashOnOverflow>(WTF::roundUpToPowerOfTwo(keyCount)) * 2; 1527613 4 rniwa 2019-04-15 21:45:57 -0700 (In reply to Geoffrey Garen from comment #3) > Comment on attachment 367492 [details] > Fixes the bug > > View in context: > https://bugs.webkit.org/attachment.cgi?id=367492&action=review > > r=me > > > Source/WTF/wtf/HashTable.h:1206 > > + Checked<unsigned, CrashOnOverflow> bestTableSize = WTF::roundUpToPowerOfTwo(keyCount); > > + if (bestTableSize.unsafeGet() < keyCount) > > + bestTableSize.overflowed(); > > + bestTableSize *= 2; > > If we needed a check here, I would recommend doing using Checked<T>. > > But we don't need this less-than check. roundUpToPowerOfTwo(2^32) is 2^32. > There's no overflow case. Hm... roundUpToPowerOfTwo(0x8fffffff) is 0 though. Do we have some guarantee that 0x80000000 would be the maximum key count? 1527775 5 ggaren 2019-04-16 10:55:41 -0700 > > If we needed a check here, I would recommend doing using Checked<T>. > > > > But we don't need this less-than check. roundUpToPowerOfTwo(2^32) is 2^32. > > There's no overflow case. > > Hm... roundUpToPowerOfTwo(0x8fffffff) is 0 though. Do we have some guarantee > that 0x80000000 would be the maximum key count? Eep! I have immortalized in Bugzilla my inability to do binary arithmetic. Don't tell Gavin. :) I think the problem input case is anything in the range (0x80000000, 0xffffffff], which is (2^31, 2^32-1]. In that case, the correct answer is 0x0000000100000000, which is not representable as uint32_t. And the implementation of roundUpToPowerOfTwo() will happen to return 0 (as you said). Maybe the right solution is to templatize roundUpToPowerOfTwo() to accept uint32_t or Checked<uint32_t>, so it can naturally catch the overflow to zero on the final ++ operation? I'm open to any solution that doesn't require an explicit check in the calling code. That's the primary benefit of Checked<T>. 1528000 6 rniwa 2019-04-16 21:03:35 -0700 Interesting, in the process of adding Checked<U, V> support to roundUpToPowerOfTwo, I found out that CachedTypes::malloc converts size_t to uint32_t that's probably a bug... 367492 2019-04-15 20:32:15 -0700 2019-04-15 21:17:20 -0700 Fixes the bug bug-196935-20190415203214.patch text/plain 11576 rniwa SW5kZXg6IFNvdXJjZS9XVEYvQ2hhbmdlTG9nCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFNvdXJjZS9XVEYvQ2hh bmdlTG9nCShyZXZpc2lvbiAyNDQzMjQpCisrKyBTb3VyY2UvV1RGL0NoYW5nZUxvZwkod29ya2lu ZyBjb3B5KQpAQCAtMSwzICsxLDM1IEBACisyMDE5LTA0LTE1ICBSeW9zdWtlIE5pd2EgIDxybml3 YUB3ZWJraXQub3JnPgorCisgICAgICAgIEFkZCBhbiBvdmVyZmxvdyBjaGVjayB0byBIYXNoVGFi bGUKKyAgICAgICAgaHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTE5Njkz NQorCisgICAgICAgIFJldmlld2VkIGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAgIFVzZSBD aGVja2VkPHVuc2lnbmVkLCBDcmFzaE9uT3ZlcmZsb3c+IGFzIHRoZSB0YWJsZSBzaXplIGluIEhh c2hUYWJsZSB0byBhdm9pZCBvdmVyZmxvd3MuCisKKyAgICAgICAgKiB3dGYvSGFzaFRhYmxlLmg6 CisgICAgICAgIChXVEY6Okhhc2hUYWJsZTo6fkhhc2hUYWJsZSk6CisgICAgICAgIChXVEY6Okhh c2hUYWJsZTo6ZW5kKToKKyAgICAgICAgKFdURjo6SGFzaFRhYmxlOjplbmQgY29uc3QpOgorICAg ICAgICAoV1RGOjpIYXNoVGFibGU6OmNhcGFjaXR5IGNvbnN0KToKKyAgICAgICAgKFdURjo6SGFz aFRhYmxlOjpzaG91bGRFeHBhbmQgY29uc3QpOgorICAgICAgICAoV1RGOjpIYXNoVGFibGU6Om11 c3RSZWhhc2hJblBsYWNlIGNvbnN0KTogRGl2aWRlIHRoZSBMSFMgaW5zdGVhZCBvZiBtdWx0aXBs eWluZyBtX3RhYmxlU2l6ZQorICAgICAgICB0byBhdm9pZCBvdmVyZmxvdyBhbmQgYW4gZXhwZW5z aXZlIG92ZXJmbG93IGNoZWNrLgorICAgICAgICAoV1RGOjpIYXNoVGFibGU6OnNob3VsZFNocmlu ayBjb25zdCk6CisgICAgICAgIChXVEY6Okhhc2hUYWJsZTo6c2hyaW5rKTogSXQncyBhbHdheXMg c2FmZSB0byBkaXZpZGUgbV90YWJsZVNpemUgYnkgMi4KKyAgICAgICAgKFdURjo6SGFzaFRhYmxl OjptYWtlSXRlcmF0b3IpOgorICAgICAgICAoV1RGOjpIYXNoVGFibGU6Om1ha2VDb25zdEl0ZXJh dG9yIGNvbnN0KToKKyAgICAgICAgKFdURjo6SGFzaFRhYmxlOjptYWtlS25vd25Hb29kSXRlcmF0 b3IpOgorICAgICAgICAoV1RGOjpIYXNoVGFibGU6Om1ha2VLbm93bkdvb2RDb25zdEl0ZXJhdG9y IGNvbnN0KToKKyAgICAgICAgKFdURjo6S2V5VHJhaXRzPjo6cmVtb3ZlSWYpOgorICAgICAgICAo V1RGOjpLZXlUcmFpdHM+OjpleHBhbmQpOiBVc2UgQ2hlY2tlZDx1bnNpZ25lZCwgQ3Jhc2hPbk92 ZXJmbG93PiBmb3IgbmV3U2l6ZS4KKyAgICAgICAgKFdURjo6S2V5VHJhaXRzPjo6Y29tcHV0ZUJl c3RUYWJsZVNpemUpOiBEaXR0by4KKyAgICAgICAgKFdURjo6S2V5VHJhaXRzPjo6ZGVsZXRlUmVs ZWFzZWRXZWFrQnVja2V0cyk6CisgICAgICAgIChXVEY6OktleVRyYWl0cz46OnJlaGFzaCk6Cisg ICAgICAgIChXVEY6OktleVRyYWl0cz46OmNsZWFyKToKKyAgICAgICAgKFdURjo6S2V5VHJhaXRz Pjo6SGFzaFRhYmxlKToKKyAgICAgICAgKFdURjo6S2V5VHJhaXRzPjo6Y2hlY2tUYWJsZUNvbnNp c3RlbmN5RXhjZXB0U2l6ZSBjb25zdCk6CisKIDIwMTktMDQtMTUgIE15bGVzIEMuIE1heGZpZWxk ICA8bW1heGZpZWxkQGFwcGxlLmNvbT4KIAogICAgICAgICBbQ29jb2FdIEZvbnRQbGF0Zm9ybURh dGEgb2JqZWN0cyBhcmVuJ3QgY2FjaGVkIGF0IGFsbCB3aGVuIHVzaW5nIGZvbnQtZmFtaWx5OnN5 c3RlbS11aQpJbmRleDogU291cmNlL1dURi93dGYvSGFzaFRhYmxlLmgKPT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0g U291cmNlL1dURi93dGYvSGFzaFRhYmxlLmgJKHJldmlzaW9uIDI0NDMwMSkKKysrIFNvdXJjZS9X VEYvd3RmL0hhc2hUYWJsZS5oCSh3b3JraW5nIGNvcHkpCkBAIC0zNTksNyArMzU5LDcgQEAgbmFt ZXNwYWNlIFdURiB7CiAgICAgICAgIHsKICAgICAgICAgICAgIGludmFsaWRhdGVJdGVyYXRvcnMo KTsgCiAgICAgICAgICAgICBpZiAobV90YWJsZSkKLSAgICAgICAgICAgICAgICBkZWFsbG9jYXRl VGFibGUobV90YWJsZSwgbV90YWJsZVNpemUpOworICAgICAgICAgICAgICAgIGRlYWxsb2NhdGVU YWJsZShtX3RhYmxlLCBtX3RhYmxlU2l6ZS51bnNhZmVHZXQoKSk7CiAjaWYgQ0hFQ0tfSEFTSFRB QkxFX1VTRV9BRlRFUl9ERVNUUlVDVElPTgogICAgICAgICAgICAgbV90YWJsZSA9IChWYWx1ZVR5 cGUqKSh1aW50cHRyX3QpMHhiYmFkYmVlZjsKICNlbmRpZgpAQCAtMzc2LDkgKzM3Niw5IEBAIG5h bWVzcGFjZSBXVEYgewogICAgICAgICAvLyBUaGlzIGlzIG1vcmUgZWZmaWNpZW50IGJlY2F1c2Ug d2UgZG9uJ3QgaGF2ZSB0byBza2lwIGFsbCB0aGUgZW1wdHkgYW5kIGRlbGV0ZWQKICAgICAgICAg Ly8gYnVja2V0cywgYW5kIGl0ZXJhdGluZyBhbiBlbXB0eSB0YWJsZSBpcyBhIGNvbW1vbiBjYXNl IHRoYXQncyB3b3J0aCBvcHRpbWl6aW5nLgogICAgICAgICBpdGVyYXRvciBiZWdpbigpIHsgcmV0 dXJuIGlzRW1wdHkoKSA/IGVuZCgpIDogbWFrZUl0ZXJhdG9yKG1fdGFibGUpOyB9Ci0gICAgICAg IGl0ZXJhdG9yIGVuZCgpIHsgcmV0dXJuIG1ha2VLbm93bkdvb2RJdGVyYXRvcihtX3RhYmxlICsg bV90YWJsZVNpemUpOyB9CisgICAgICAgIGl0ZXJhdG9yIGVuZCgpIHsgcmV0dXJuIG1ha2VLbm93 bkdvb2RJdGVyYXRvcihtX3RhYmxlICsgbV90YWJsZVNpemUudW5zYWZlR2V0KCkpOyB9CiAgICAg ICAgIGNvbnN0X2l0ZXJhdG9yIGJlZ2luKCkgY29uc3QgeyByZXR1cm4gaXNFbXB0eSgpID8gZW5k KCkgOiBtYWtlQ29uc3RJdGVyYXRvcihtX3RhYmxlKTsgfQotICAgICAgICBjb25zdF9pdGVyYXRv ciBlbmQoKSBjb25zdCB7IHJldHVybiBtYWtlS25vd25Hb29kQ29uc3RJdGVyYXRvcihtX3RhYmxl ICsgbV90YWJsZVNpemUpOyB9CisgICAgICAgIGNvbnN0X2l0ZXJhdG9yIGVuZCgpIGNvbnN0IHsg cmV0dXJuIG1ha2VLbm93bkdvb2RDb25zdEl0ZXJhdG9yKG1fdGFibGUgKyBtX3RhYmxlU2l6ZS51 bnNhZmVHZXQoKSk7IH0KIAogICAgICAgICBpdGVyYXRvciByYW5kb20oKQogICAgICAgICB7CkBA IC0zOTUsNyArMzk1LDcgQEAgbmFtZXNwYWNlIFdURiB7CiAgICAgICAgIGNvbnN0X2l0ZXJhdG9y IHJhbmRvbSgpIGNvbnN0IHsgcmV0dXJuIHN0YXRpY19jYXN0PGNvbnN0X2l0ZXJhdG9yPihjb25z dF9jYXN0PEhhc2hUYWJsZSo+KHRoaXMpLT5yYW5kb20oKSk7IH0KIAogICAgICAgICB1bnNpZ25l ZCBzaXplKCkgY29uc3QgeyByZXR1cm4gbV9rZXlDb3VudDsgfQotICAgICAgICB1bnNpZ25lZCBj YXBhY2l0eSgpIGNvbnN0IHsgcmV0dXJuIG1fdGFibGVTaXplOyB9CisgICAgICAgIHVuc2lnbmVk IGNhcGFjaXR5KCkgY29uc3QgeyByZXR1cm4gbV90YWJsZVNpemUudW5zYWZlR2V0KCk7IH0KICAg ICAgICAgYm9vbCBpc0VtcHR5KCkgY29uc3QgeyByZXR1cm4gIW1fa2V5Q291bnQ7IH0KIAogICAg ICAgICBBZGRSZXN1bHQgYWRkKGNvbnN0IFZhbHVlVHlwZSYgdmFsdWUpIHsgcmV0dXJuIGFkZDxJ ZGVudGl0eVRyYW5zbGF0b3JUeXBlPihFeHRyYWN0b3I6OmV4dHJhY3QodmFsdWUpLCB2YWx1ZSk7 IH0KQEAgLTQ2NCwxMiArNDY0LDEyIEBAIG5hbWVzcGFjZSBXVEYgewogICAgICAgICB2b2lkIHJl bW92ZUFuZEludmFsaWRhdGUoVmFsdWVUeXBlKik7CiAgICAgICAgIHZvaWQgcmVtb3ZlKFZhbHVl VHlwZSopOwogCi0gICAgICAgIHN0YXRpYyBjb25zdGV4cHIgdW5zaWduZWQgY29tcHV0ZUJlc3RU YWJsZVNpemUodW5zaWduZWQga2V5Q291bnQpOwotICAgICAgICBib29sIHNob3VsZEV4cGFuZCgp IGNvbnN0IHsgcmV0dXJuIChtX2tleUNvdW50ICsgbV9kZWxldGVkQ291bnQpICogbV9tYXhMb2Fk ID49IG1fdGFibGVTaXplOyB9Ci0gICAgICAgIGJvb2wgbXVzdFJlaGFzaEluUGxhY2UoKSBjb25z dCB7IHJldHVybiBtX2tleUNvdW50ICogbV9taW5Mb2FkIDwgbV90YWJsZVNpemUgKiAyOyB9Ci0g ICAgICAgIGJvb2wgc2hvdWxkU2hyaW5rKCkgY29uc3QgeyByZXR1cm4gbV9rZXlDb3VudCAqIG1f bWluTG9hZCA8IG1fdGFibGVTaXplICYmIG1fdGFibGVTaXplID4gS2V5VHJhaXRzOjptaW5pbXVt VGFibGVTaXplOyB9CisgICAgICAgIHN0YXRpYyB1bnNpZ25lZCBjb21wdXRlQmVzdFRhYmxlU2l6 ZSh1bnNpZ25lZCBrZXlDb3VudCk7CisgICAgICAgIGJvb2wgc2hvdWxkRXhwYW5kKCkgY29uc3Qg eyByZXR1cm4gKG1fa2V5Q291bnQgKyBtX2RlbGV0ZWRDb3VudCkgKiBtX21heExvYWQgPj0gbV90 YWJsZVNpemUudW5zYWZlR2V0KCk7IH0KKyAgICAgICAgYm9vbCBtdXN0UmVoYXNoSW5QbGFjZSgp IGNvbnN0IHsgcmV0dXJuIG1fa2V5Q291bnQgKiBtX21pbkxvYWQgLyAyIDwgbV90YWJsZVNpemUu dW5zYWZlR2V0KCk7IH0KKyAgICAgICAgYm9vbCBzaG91bGRTaHJpbmsoKSBjb25zdCB7IHJldHVy biBtX2tleUNvdW50ICogbV9taW5Mb2FkIDwgbV90YWJsZVNpemUudW5zYWZlR2V0KCkgJiYgbV90 YWJsZVNpemUudW5zYWZlR2V0KCkgPiBLZXlUcmFpdHM6Om1pbmltdW1UYWJsZVNpemU7IH0KICAg ICAgICAgVmFsdWVUeXBlKiBleHBhbmQoVmFsdWVUeXBlKiBlbnRyeSA9IG51bGxwdHIpOwotICAg ICAgICB2b2lkIHNocmluaygpIHsgcmVoYXNoKG1fdGFibGVTaXplIC8gMiwgbnVsbHB0cik7IH0K KyAgICAgICAgdm9pZCBzaHJpbmsoKSB7IHJlaGFzaChtX3RhYmxlU2l6ZS51bnNhZmVHZXQoKSAv IDIsIG51bGxwdHIpOyB9CiAgICAgICAgIHZvaWQgc2hyaW5rVG9CZXN0U2l6ZSgpOwogICAgIAog ICAgICAgICB2b2lkIGRlbGV0ZVJlbGVhc2VkV2Vha0J1Y2tldHMoKTsKQEAgLTQ4MywxMCArNDgz LDEwIEBAIG5hbWVzcGFjZSBXVEYgewogICAgICAgICBGdWxsTG9va3VwVHlwZSBtYWtlTG9va3Vw UmVzdWx0KFZhbHVlVHlwZSogcG9zaXRpb24sIGJvb2wgZm91bmQsIHVuc2lnbmVkIGhhc2gpCiAg ICAgICAgICAgICB7IHJldHVybiBGdWxsTG9va3VwVHlwZShMb29rdXBUeXBlKHBvc2l0aW9uLCBm b3VuZCksIGhhc2gpOyB9CiAKLSAgICAgICAgaXRlcmF0b3IgbWFrZUl0ZXJhdG9yKFZhbHVlVHlw ZSogcG9zKSB7IHJldHVybiBpdGVyYXRvcih0aGlzLCBwb3MsIG1fdGFibGUgKyBtX3RhYmxlU2l6 ZSk7IH0KLSAgICAgICAgY29uc3RfaXRlcmF0b3IgbWFrZUNvbnN0SXRlcmF0b3IoVmFsdWVUeXBl KiBwb3MpIGNvbnN0IHsgcmV0dXJuIGNvbnN0X2l0ZXJhdG9yKHRoaXMsIHBvcywgbV90YWJsZSAr IG1fdGFibGVTaXplKTsgfQotICAgICAgICBpdGVyYXRvciBtYWtlS25vd25Hb29kSXRlcmF0b3Io VmFsdWVUeXBlKiBwb3MpIHsgcmV0dXJuIGl0ZXJhdG9yKHRoaXMsIHBvcywgbV90YWJsZSArIG1f dGFibGVTaXplLCBIYXNoSXRlbUtub3duR29vZCk7IH0KLSAgICAgICAgY29uc3RfaXRlcmF0b3Ig bWFrZUtub3duR29vZENvbnN0SXRlcmF0b3IoVmFsdWVUeXBlKiBwb3MpIGNvbnN0IHsgcmV0dXJu IGNvbnN0X2l0ZXJhdG9yKHRoaXMsIHBvcywgbV90YWJsZSArIG1fdGFibGVTaXplLCBIYXNoSXRl bUtub3duR29vZCk7IH0KKyAgICAgICAgaXRlcmF0b3IgbWFrZUl0ZXJhdG9yKFZhbHVlVHlwZSog cG9zKSB7IHJldHVybiBpdGVyYXRvcih0aGlzLCBwb3MsIG1fdGFibGUgKyBtX3RhYmxlU2l6ZS51 bnNhZmVHZXQoKSk7IH0KKyAgICAgICAgY29uc3RfaXRlcmF0b3IgbWFrZUNvbnN0SXRlcmF0b3Io VmFsdWVUeXBlKiBwb3MpIGNvbnN0IHsgcmV0dXJuIGNvbnN0X2l0ZXJhdG9yKHRoaXMsIHBvcywg bV90YWJsZSArIG1fdGFibGVTaXplLnVuc2FmZUdldCgpKTsgfQorICAgICAgICBpdGVyYXRvciBt YWtlS25vd25Hb29kSXRlcmF0b3IoVmFsdWVUeXBlKiBwb3MpIHsgcmV0dXJuIGl0ZXJhdG9yKHRo aXMsIHBvcywgbV90YWJsZSArIG1fdGFibGVTaXplLnVuc2FmZUdldCgpLCBIYXNoSXRlbUtub3du R29vZCk7IH0KKyAgICAgICAgY29uc3RfaXRlcmF0b3IgbWFrZUtub3duR29vZENvbnN0SXRlcmF0 b3IoVmFsdWVUeXBlKiBwb3MpIGNvbnN0IHsgcmV0dXJuIGNvbnN0X2l0ZXJhdG9yKHRoaXMsIHBv cywgbV90YWJsZSArIG1fdGFibGVTaXplLnVuc2FmZUdldCgpLCBIYXNoSXRlbUtub3duR29vZCk7 IH0KIAogI2lmICFBU1NFUlRfRElTQUJMRUQKICAgICAgICAgdm9pZCBjaGVja1RhYmxlQ29uc2lz dGVuY3lFeGNlcHRTaXplKCkgY29uc3Q7CkBAIC01MDQsNyArNTA0LDcgQEAgbmFtZXNwYWNlIFdU RiB7CiAgICAgICAgIHN0YXRpYyBjb25zdCB1bnNpZ25lZCBtX21pbkxvYWQgPSA2OwogCiAgICAg ICAgIFZhbHVlVHlwZSogbV90YWJsZTsKLSAgICAgICAgdW5zaWduZWQgbV90YWJsZVNpemU7Cisg ICAgICAgIENoZWNrZWQ8dW5zaWduZWQsIENyYXNoT25PdmVyZmxvdz4gbV90YWJsZVNpemU7CiAg ICAgICAgIHVuc2lnbmVkIG1fdGFibGVTaXplTWFzazsKICAgICAgICAgdW5zaWduZWQgbV9rZXlD b3VudDsKICAgICAgICAgdW5zaWduZWQgbV9kZWxldGVkQ291bnQ7CkBAIC0xMTM2LDcgKzExMzYs NyBAQCBuYW1lc3BhY2UgV1RGIHsKICAgICAgICAgdW5zaWduZWQgcmVtb3ZlZEJ1Y2tldENvdW50 ID0gMDsKICAgICAgICAgVmFsdWVUeXBlKiB0YWJsZSA9IG1fdGFibGU7CiAKLSAgICAgICAgZm9y ICh1bnNpZ25lZCBpID0gbV90YWJsZVNpemU7IGktLTspIHsKKyAgICAgICAgZm9yICh1bnNpZ25l ZCBpID0gbV90YWJsZVNpemUudW5zYWZlR2V0KCk7IGktLTspIHsKICAgICAgICAgICAgIFZhbHVl VHlwZSYgYnVja2V0ID0gdGFibGVbaV07CiAgICAgICAgICAgICBpZiAoaXNFbXB0eU9yRGVsZXRl ZEJ1Y2tldChidWNrZXQpKQogICAgICAgICAgICAgICAgIGNvbnRpbnVlOwpAQCAtMTE4Niw0NCAr MTE4Niw0NyBAQCBuYW1lc3BhY2UgV1RGIHsKICAgICAgICAgaWYgKEtleVRyYWl0czo6aGFzSXNS ZWxlYXNlZFdlYWtWYWx1ZUZ1bmN0aW9uKQogICAgICAgICAgICAgZGVsZXRlUmVsZWFzZWRXZWFr QnVja2V0cygpOwogCi0gICAgICAgIHVuc2lnbmVkIG5ld1NpemU7Ci0gICAgICAgIGlmIChtX3Rh YmxlU2l6ZSA9PSAwKQorICAgICAgICBDaGVja2VkPHVuc2lnbmVkLCBDcmFzaE9uT3ZlcmZsb3c+ IG5ld1NpemU7CisgICAgICAgIGlmICghbV90YWJsZVNpemUpCiAgICAgICAgICAgICBuZXdTaXpl ID0gS2V5VHJhaXRzOjptaW5pbXVtVGFibGVTaXplOwogICAgICAgICBlbHNlIGlmIChtdXN0UmVo YXNoSW5QbGFjZSgpKQogICAgICAgICAgICAgbmV3U2l6ZSA9IG1fdGFibGVTaXplOwogICAgICAg ICBlbHNlCiAgICAgICAgICAgICBuZXdTaXplID0gbV90YWJsZVNpemUgKiAyOwogCi0gICAgICAg IHJldHVybiByZWhhc2gobmV3U2l6ZSwgZW50cnkpOworICAgICAgICByZXR1cm4gcmVoYXNoKG5l d1NpemUudW5zYWZlR2V0KCksIGVudHJ5KTsKICAgICB9CiAKICAgICB0ZW1wbGF0ZTx0eXBlbmFt ZSBLZXksIHR5cGVuYW1lIFZhbHVlLCB0eXBlbmFtZSBFeHRyYWN0b3IsIHR5cGVuYW1lIEhhc2hG dW5jdGlvbnMsIHR5cGVuYW1lIFRyYWl0cywgdHlwZW5hbWUgS2V5VHJhaXRzPgotICAgIGNvbnN0 ZXhwciB1bnNpZ25lZCBIYXNoVGFibGU8S2V5LCBWYWx1ZSwgRXh0cmFjdG9yLCBIYXNoRnVuY3Rp b25zLCBUcmFpdHMsIEtleVRyYWl0cz46OmNvbXB1dGVCZXN0VGFibGVTaXplKHVuc2lnbmVkIGtl eUNvdW50KQorICAgIHVuc2lnbmVkIEhhc2hUYWJsZTxLZXksIFZhbHVlLCBFeHRyYWN0b3IsIEhh c2hGdW5jdGlvbnMsIFRyYWl0cywgS2V5VHJhaXRzPjo6Y29tcHV0ZUJlc3RUYWJsZVNpemUodW5z aWduZWQga2V5Q291bnQpCiAgICAgewotICAgICAgICB1bnNpZ25lZCBiZXN0VGFibGVTaXplID0g V1RGOjpyb3VuZFVwVG9Qb3dlck9mVHdvKGtleUNvdW50KSAqIDI7CisgICAgICAgIENoZWNrZWQ8 dW5zaWduZWQsIENyYXNoT25PdmVyZmxvdz4gYmVzdFRhYmxlU2l6ZSA9IFdURjo6cm91bmRVcFRv UG93ZXJPZlR3byhrZXlDb3VudCk7CisgICAgICAgIGlmIChiZXN0VGFibGVTaXplLnVuc2FmZUdl dCgpIDwga2V5Q291bnQpCisgICAgICAgICAgICBiZXN0VGFibGVTaXplLm92ZXJmbG93ZWQoKTsK KyAgICAgICAgYmVzdFRhYmxlU2l6ZSAqPSAyOwogCiAgICAgICAgIC8vIFdpdGggbWF4TG9hZCBh dCAxLzIgYW5kIG1pbkxvYWQgYXQgMS82LCBvdXIgYXZlcmFnZSBsb2FkIGlzIDIvNi4KICAgICAg ICAgLy8gSWYgd2UgYXJlIGdldHRpbmcgaGFsZndheSBiZXR3ZWVuIDIvNiBhbmQgMS8yIChwYXN0 IDUvMTIpLCB3ZSBkb3VibGUgdGhlIHNpemUgdG8gYXZvaWQgYmVpbmcgdG9vIGNsb3NlIHRvCiAg ICAgICAgIC8vIGxvYWRNYXggYW5kIGJyaW5nIHRoZSByYXRpbyBjbG9zZSB0byAyLzYuIFRoaXMg Z2l2ZSB1cyBhIGxvYWQgaW4gdGhlIGJvdW5kcyBbMy8xMiwgNS8xMikuCi0gICAgICAgIGJvb2wg YWJvdmVUaHJlZVF1YXJ0ZXJMb2FkID0ga2V5Q291bnQgKiAxMiA+PSBiZXN0VGFibGVTaXplICog NTsKKyAgICAgICAgYm9vbCBhYm92ZVRocmVlUXVhcnRlckxvYWQgPSBrZXlDb3VudCAqIDEyID49 IGJlc3RUYWJsZVNpemUudW5zYWZlR2V0KCkgKiA1OwogICAgICAgICBpZiAoYWJvdmVUaHJlZVF1 YXJ0ZXJMb2FkKQogICAgICAgICAgICAgYmVzdFRhYmxlU2l6ZSAqPSAyOwogCiAgICAgICAgIHVu c2lnbmVkIG1pbmltdW1UYWJsZVNpemUgPSBLZXlUcmFpdHM6Om1pbmltdW1UYWJsZVNpemU7Ci0g ICAgICAgIHJldHVybiBzdGQ6Om1heDx1bnNpZ25lZD4oYmVzdFRhYmxlU2l6ZSwgbWluaW11bVRh YmxlU2l6ZSk7CisgICAgICAgIHJldHVybiBzdGQ6Om1heChiZXN0VGFibGVTaXplLnVuc2FmZUdl dCgpLCBtaW5pbXVtVGFibGVTaXplKTsKICAgICB9CiAKICAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBL ZXksIHR5cGVuYW1lIFZhbHVlLCB0eXBlbmFtZSBFeHRyYWN0b3IsIHR5cGVuYW1lIEhhc2hGdW5j dGlvbnMsIHR5cGVuYW1lIFRyYWl0cywgdHlwZW5hbWUgS2V5VHJhaXRzPgogICAgIHZvaWQgSGFz aFRhYmxlPEtleSwgVmFsdWUsIEV4dHJhY3RvciwgSGFzaEZ1bmN0aW9ucywgVHJhaXRzLCBLZXlU cmFpdHM+OjpzaHJpbmtUb0Jlc3RTaXplKCkKICAgICB7CiAgICAgICAgIHVuc2lnbmVkIG1pbmlt dW1UYWJsZVNpemUgPSBLZXlUcmFpdHM6Om1pbmltdW1UYWJsZVNpemU7Ci0gICAgICAgIHJlaGFz aChzdGQ6Om1heDx1bnNpZ25lZD4obWluaW11bVRhYmxlU2l6ZSwgY29tcHV0ZUJlc3RUYWJsZVNp emUobV9rZXlDb3VudCkpLCBudWxscHRyKTsKKyAgICAgICAgcmVoYXNoKHN0ZDo6bWF4KG1pbmlt dW1UYWJsZVNpemUsIGNvbXB1dGVCZXN0VGFibGVTaXplKG1fa2V5Q291bnQpKSwgbnVsbHB0cik7 CiAgICAgfQogCiAgICAgdGVtcGxhdGU8dHlwZW5hbWUgS2V5LCB0eXBlbmFtZSBWYWx1ZSwgdHlw ZW5hbWUgRXh0cmFjdG9yLCB0eXBlbmFtZSBIYXNoRnVuY3Rpb25zLCB0eXBlbmFtZSBUcmFpdHMs IHR5cGVuYW1lIEtleVRyYWl0cz4KICAgICB2b2lkIEhhc2hUYWJsZTxLZXksIFZhbHVlLCBFeHRy YWN0b3IsIEhhc2hGdW5jdGlvbnMsIFRyYWl0cywgS2V5VHJhaXRzPjo6ZGVsZXRlUmVsZWFzZWRX ZWFrQnVja2V0cygpCiAgICAgewotICAgICAgICBmb3IgKHVuc2lnbmVkIGkgPSAwOyBpIDwgbV90 YWJsZVNpemU7ICsraSkgeworICAgICAgICBmb3IgKHVuc2lnbmVkIGkgPSAwOyBpIDwgbV90YWJs ZVNpemUudW5zYWZlR2V0KCk7ICsraSkgewogICAgICAgICAgICAgYXV0byYgZW50cnkgPSBtX3Rh YmxlW2ldOwogICAgICAgICAgICAgaWYgKGlzUmVsZWFzZWRXZWFrQnVja2V0KGVudHJ5KSkgewog ICAgICAgICAgICAgICAgIGRlbGV0ZUJ1Y2tldChlbnRyeSk7CkBAIC0xMjM4LDcgKzEyNDEsNyBA QCBuYW1lc3BhY2UgV1RGIHsKICAgICB7CiAgICAgICAgIGludGVybmFsQ2hlY2tUYWJsZUNvbnNp c3RlbmN5RXhjZXB0U2l6ZSgpOwogCi0gICAgICAgIHVuc2lnbmVkIG9sZFRhYmxlU2l6ZSA9IG1f dGFibGVTaXplOworICAgICAgICB1bnNpZ25lZCBvbGRUYWJsZVNpemUgPSBtX3RhYmxlU2l6ZS51 bnNhZmVHZXQoKTsKICAgICAgICAgVmFsdWVUeXBlKiBvbGRUYWJsZSA9IG1fdGFibGU7CiAKICNp ZiBEVU1QX0hBU0hUQUJMRV9TVEFUUwpAQCAtMTI5OSw3ICsxMzAyLDcgQEAgbmFtZXNwYWNlIFdU RiB7CiAgICAgICAgIGlmICghbV90YWJsZSkKICAgICAgICAgICAgIHJldHVybjsKIAotICAgICAg ICBkZWFsbG9jYXRlVGFibGUobV90YWJsZSwgbV90YWJsZVNpemUpOworICAgICAgICBkZWFsbG9j YXRlVGFibGUobV90YWJsZSwgbV90YWJsZVNpemUudW5zYWZlR2V0KCkpOwogICAgICAgICBtX3Rh YmxlID0gMDsKICAgICAgICAgbV90YWJsZVNpemUgPSAwOwogICAgICAgICBtX3RhYmxlU2l6ZU1h c2sgPSAwOwpAQCAtMTMyNyw5ICsxMzMwLDkgQEAgbmFtZXNwYWNlIFdURiB7CiAgICAgICAgICAg ICByZXR1cm47CiAKICAgICAgICAgbV90YWJsZVNpemUgPSBjb21wdXRlQmVzdFRhYmxlU2l6ZShv dGhlcktleUNvdW50KTsKLSAgICAgICAgbV90YWJsZVNpemVNYXNrID0gbV90YWJsZVNpemUgLSAx OworICAgICAgICBtX3RhYmxlU2l6ZU1hc2sgPSBtX3RhYmxlU2l6ZS51bnNhZmVHZXQoKSAtIDE7 CiAgICAgICAgIG1fa2V5Q291bnQgPSBvdGhlcktleUNvdW50OwotICAgICAgICBtX3RhYmxlID0g YWxsb2NhdGVUYWJsZShtX3RhYmxlU2l6ZSk7CisgICAgICAgIG1fdGFibGUgPSBhbGxvY2F0ZVRh YmxlKG1fdGFibGVTaXplLnVuc2FmZUdldCgpKTsKIAogICAgICAgICBmb3IgKGNvbnN0IGF1dG8m IG90aGVyVmFsdWUgOiBvdGhlcikKICAgICAgICAgICAgIGFkZFVuaXF1ZUZvckluaXRpYWxpemF0 aW9uPElkZW50aXR5VHJhbnNsYXRvclR5cGU+KEV4dHJhY3Rvcjo6ZXh0cmFjdChvdGhlclZhbHVl KSwgb3RoZXJWYWx1ZSk7CkBAIC0xNDEzLDcgKzE0MTYsNyBAQCBuYW1lc3BhY2UgV1RGIHsKIAog ICAgICAgICB1bnNpZ25lZCBjb3VudCA9IDA7CiAgICAgICAgIHVuc2lnbmVkIGRlbGV0ZWRDb3Vu dCA9IDA7Ci0gICAgICAgIGZvciAodW5zaWduZWQgaiA9IDA7IGogPCBtX3RhYmxlU2l6ZTsgKytq KSB7CisgICAgICAgIGZvciAodW5zaWduZWQgaiA9IDA7IGogPCBtX3RhYmxlU2l6ZS51bnNhZmVH ZXQoKTsgKytqKSB7CiAgICAgICAgICAgICBWYWx1ZVR5cGUqIGVudHJ5ID0gbV90YWJsZSArIGo7 CiAgICAgICAgICAgICBpZiAoaXNFbXB0eUJ1Y2tldCgqZW50cnkpKQogICAgICAgICAgICAgICAg IGNvbnRpbnVlOwpAQCAtMTQzNSw3ICsxNDM4LDcgQEAgbmFtZXNwYWNlIFdURiB7CiAgICAgICAg IEFTU0VSVChkZWxldGVkQ291bnQgPT0gbV9kZWxldGVkQ291bnQpOwogICAgICAgICBBU1NFUlQo bV90YWJsZVNpemUgPj0gS2V5VHJhaXRzOjptaW5pbXVtVGFibGVTaXplKTsKICAgICAgICAgQVNT RVJUKG1fdGFibGVTaXplTWFzayk7Ci0gICAgICAgIEFTU0VSVChtX3RhYmxlU2l6ZSA9PSBtX3Rh YmxlU2l6ZU1hc2sgKyAxKTsKKyAgICAgICAgQVNTRVJUKG1fdGFibGVTaXplLnVuc2FmZUdldCgp ID09IG1fdGFibGVTaXplTWFzayArIDEpOwogICAgIH0KIAogI2VuZGlmIC8vIEFTU0VSVF9ESVNB QkxFRAo=