Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1vGFC9-00AlSv-QH for pgsql-hackers@arkaria.postgresql.org; Tue, 04 Nov 2025 11:27:25 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1vGFC8-00D7zI-P5 for pgsql-hackers@arkaria.postgresql.org; Tue, 04 Nov 2025 11:27:23 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1vGFC8-00D7xO-7U for pgsql-hackers@lists.postgresql.org; Tue, 04 Nov 2025 11:27:23 +0000 Received: from mail-qt1-x841.google.com ([2607:f8b0:4864:20::841]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.96) (envelope-from ) id 1vGFC5-005OVS-1N for pgsql-hackers@lists.postgresql.org; Tue, 04 Nov 2025 11:27:22 +0000 Received: by mail-qt1-x841.google.com with SMTP id d75a77b69052e-4e4d9fc4316so60405741cf.2 for ; Tue, 04 Nov 2025 03:27:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762255640; x=1762860440; darn=lists.postgresql.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=aS/yb4Jpsq6Ms5NuIhqTWqVGFa3FmrWWwxdZWGt9ZSA=; b=c/AuUkx0wJQnWPdYQDIasFdgMWmqjr5wyZVHvEaK80vB/JOpQFBzY4lx9x82vUrNjd Zd5iJQnBlHcozYq24Z7ARE35ZpimatCfPIdx5ychMunMthJsaBMTzEFMD26qaCLhS3pW 9GpN+7pD/yk0a0kwIPLmvcF+KCDMPxXkycIHDqswasxmOCie7y1tjIfhz5nFytdTgWEv WKN1Qy3vemIBXrCPDV7rx5FKKIeXBWBI/RTTv3/muwfy9YBkR6bb0z3kqnJ5LG9SR7L6 0XBNe/LXKa5NUV70u932Jn3qG4Jnlfb241TnZHQBQGBrQlunI9cexyqxWFzQoLZ+fu8O EGMQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762255640; x=1762860440; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=aS/yb4Jpsq6Ms5NuIhqTWqVGFa3FmrWWwxdZWGt9ZSA=; b=VCpw/lJPGLxV/55a3U0a9k9D++oOSBert6mgxuzJCFV08mNbjJITLWtY3RcC4F1wlM ok6biUH0UYu68rjYEYsF3mipMry3YWrHUXJU7ybHhTMlIUPQJZARZG9X6n+p6a0zhtrC xbRajjY0fHL3X8cqcnNj+8rSmhhYxFE7EhIkRITx1lguwy99wBNokAaYS4X6nVlBQVRG ysPEiwRG5Ij05sA+HuwpTEWJoaDQ3qEdgFIQfEGqIYkIlPxNeDfrYiH+J0X+5Ybgsni8 DmhdXGiaXZxkl591XWXw2AFP15C+2LOSEvN/tA4PxtSYNFNq0ay5S1wtZ6FvG0EdnBf6 cmAA== X-Gm-Message-State: AOJu0YweO7lCNHmCKOqv+P0wtGBQLaUlKJusspMiy3W6j9kDpMtQcHkd usyHW40AWYT0QNpVpsH/ij3CmKeom11BnANyJR243nFrPoCo509chrUD3jUQ7FYv5R1KR7ZMs/f tb/dDHbb/fLkXSPa27PsSknhSuaRlzczZxfg6kxpAEA== X-Gm-Gg: ASbGncvQqty3QjmfmZsGuVWo1RsCRjpqloOhRzPqoLZ3iAoAQEFW5hqEmEhcB69U1PM qkV9yZniCAZiuSfd6Po3IEQ3GuNx1YXweBkC7SOKvKcxFppHdZD3qU4RY25XGxeMzh5U0bugMqs 2M7WuhAa9pLx5JhJDKDJCk2fyZjtkyIjpJAgifOvNo1xU1BZ4IU+xSkV2IpdRtYPyHdnkuEKtfV HmSbS7S/B+5LpK7EarfV1qqfLtISyOfeuguTR5yp3cN5q0tkR4uXGPOm0WnGSZVicd6BoEP+apO r4Iz6ileZbRmN25mBVqmVUQKmCASwYANKfBgiEhLGNl+SB8= X-Google-Smtp-Source: AGHT+IHgpX67Cm1mUfyINCyV+GYuqjuVnczUJq9ZrYl/NVg5H+o+le2YyEQVPVp5tBIe/RDNdkqz59RwLyrV58SNFFg= X-Received: by 2002:a05:622a:5a15:b0:4ec:fafd:7605 with SMTP id d75a77b69052e-4ed31004db9mr182411901cf.60.1762255640284; Tue, 04 Nov 2025 03:27:20 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: John Naylor Date: Tue, 4 Nov 2025 18:27:08 +0700 X-Gm-Features: AWmQ_blO1ex98gvo3kvGYYGeUqDW3KDj6qvVICsOwScPhtA7kKHRL4rtL0_90JI Message-ID: Subject: Re: tuple radix sort To: PostgreSQL Hackers Cc: Peter Geoghegan Content-Type: multipart/mixed; boundary="0000000000007172f50642c31d6d" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --0000000000007172f50642c31d6d Content-Type: text/plain; charset="UTF-8" I wrote: > I've set the threshold to 400 for now, but I'm not claiming that's the > end story. In addition to the underestimation mentioned above, > unrolling the counting step is a factor. Unrolling makes smaller > inputs worse (which we can reach by recursing from larger inputs), but > unrolling seems important for large inputs with low cardinality (a few > percent, but I haven't shared numbers yet). We've found that a large > input with only 4-5 distinct values just barely wins with radix sort. > I'll be curious to see if unrolling is actually needed to prevent > regressions there. Looking more closely at my development history, it turns out I added loop unrolling before adding common prefix detection. Most real-world non-negative integers have the upper bytes the same, especially since the datum is 8 bytes regardless of underlying type. For those bytes, the radix sort finds only one unique byte and continues on to the next byte. By detecting the common prefix as we condition the datums, it matters less how fast we can count since we simply skip some useless work. (This is not as relevant when we have an abbreviated datum) Repeating part of the microbenchmark from last time with no unrolling, a threshold of 200 works for all but the lowest cardinality inputs: cardinality: 256 number of elements: 100 qsort: 34.8 radix: 38.3 number of elements: 200 qsort: 34.9 radix: 29.7 number of elements: 400 qsort: 40.8 radix: 29.2 cardinality: 16 number of elements: 100 qsort: 19.3 radix: 26.2 number of elements: 200 qsort: 18.9 radix: 18.2 number of elements: 400 qsort: 18.5 radix: 14.5 cardinality: 2 number of elements: 100 qsort: 09.3 radix: 21.6 number of elements: 200 qsort: 08.9 radix: 15.4 number of elements: 400 qsort: 10.3 radix: 14.0 To test further, I dug up a test from [1] that stresses low cardinality on multiple sort keys (attached in a form to allow turing radix sort on and off via a command line argument), and found no regression with or without loop unrolling: V2: off: 4 ^ 8: latency average = 101.070 ms 5 ^ 8: latency average = 704.862 ms 6 ^ 8: latency average = 3651.015 ms 7 ^ 8: latency average = 15141.412 ms on: 4 ^ 8: latency average = 99.939 ms 5 ^ 8: latency average = 683.018 ms 6 ^ 8: latency average = 3545.626 ms 7 ^ 8: latency average = 14095.677 ms V3: off: 4 ^ 8: latency average = 99.486 ms 5 ^ 8: latency average = 693.434 ms 6 ^ 8: latency average = 3607.940 ms 7 ^ 8: latency average = 14602.325 ms on: 4 ^ 8: latency average = 97.664 ms 5 ^ 8: latency average = 678.752 ms 6 ^ 8: latency average = 3361.765 ms 7 ^ 8: latency average = 14121.190 ms So v3 gets rid of loop unrolling, reduces the threshold to 200. [1] https://www.postgresql.org/message-id/flat/CAApHDvqkHZsT2gaAWFM7D%3D7qyQ%3DeKXQvvn%2BBkwCn4Rvj1w4EKQ%40mail.gmail.com#1c67321e09be15e031d3995d45a1b8fd TODOs: - adding a "sorted pre-check" to keep up with our qsort for ascending inputs - further performance validation - possibly doing NULL partitioning differently - possibly specializing qsort on the NULL partition - code cleanup -- John Naylor Amazon Web Services --0000000000007172f50642c31d6d Content-Type: application/x-sh; name="bench_cartesiansort.sh" Content-Disposition: attachment; filename="bench_cartesiansort.sh" Content-Transfer-Encoding: base64 Content-ID: X-Attachment-Id: f_mhkg5wy40 IyEvYmluL2Jhc2gKCnNldCAtZQoKcHNxbCAtYyAic2hvdyBodWdlX3BhZ2VzOyIgcG9zdGdyZXMK cHNxbCAtYyAic2hvdyBzaGFyZWRfYnVmZmVyczsiIHBvc3RncmVzCnBzcWwgLWMgImNyZWF0ZSBl eHRlbnNpb24gaWYgbm90IGV4aXN0cyBwZ19wcmV3YXJtIiBwb3N0Z3JlcwoKcHNxbCAtYyAiYWx0 ZXIgc3lzdGVtIHNldCBtYXhfcGFyYWxsZWxfd29ya2VycyA9IDA7IiBwb3N0Z3JlcyA+IC9kZXYv bnVsbApwc3FsIC1jICJhbHRlciBzeXN0ZW0gc2V0IHdvcmtfbWVtID0gJzRHQic7IiBwb3N0Z3Jl cyA+IC9kZXYvbnVsbApwc3FsIC1jICJhbHRlciBzeXN0ZW0gc2V0IHdpcF9yYWRpeF9zb3J0ID0g JyQxJzsiIHBvc3RncmVzCgpwc3FsIC1jICJzZWxlY3QgcGdfcmVsb2FkX2NvbmYoKTsiIHBvc3Rn cmVzID4gL2Rldi9udWxsCgpwc3FsIC1jICJjcmVhdGUgdGFibGUgaWYgbm90IGV4aXN0cyBhYmNk ZWZnaCAoYSBpbnQsIGIgaW50LCBjIGludCwgZCBpbnQsIGUgaW50LCBmIGludCwgZyBpbnQsIGgg aW50KTsiIHBvc3RncmVzCgpmb3IgZXhwIGluIDQgNSA2IDcKZG8KCXBzcWwgLWMgInRydW5jYXRl IHRhYmxlIGFiY2RlZmdoOyIgcG9zdGdyZXMgPiAvZGV2L251bGwKCXBzcWwgLWQgcG9zdGdyZXMg PiAvZGV2L251bGwgIDw8RU9GCmluc2VydCBpbnRvIGFiY2RlZmdoCnNlbGVjdCBhLGIsYyxkLGUs ZixnLGggZnJvbQpnZW5lcmF0ZV9zZXJpZXMoMSwkZXhwKSBhLApnZW5lcmF0ZV9zZXJpZXMoMSwk ZXhwKSBiLApnZW5lcmF0ZV9zZXJpZXMoMSwkZXhwKSBjLApnZW5lcmF0ZV9zZXJpZXMoMSwkZXhw KSBkLApnZW5lcmF0ZV9zZXJpZXMoMSwkZXhwKSBlLApnZW5lcmF0ZV9zZXJpZXMoMSwkZXhwKSBm LApnZW5lcmF0ZV9zZXJpZXMoMSwkZXhwKSBnLApnZW5lcmF0ZV9zZXJpZXMoMSwkZXhwKSBoOwpF T0YKCXBzcWwgLWMgInZhY3V1bSBmcmVlemUgYWJjZGVmZ2g7IiBwb3N0Z3JlcyA+IC9kZXYvbnVs bAoJcHNxbCAtYyAic2VsZWN0IHBnX3ByZXdhcm0oJ2FiY2RlZmdoJyk7IiBwb3N0Z3JlcyA+IC9k ZXYvbnVsbAoJZWNobyAic2VsZWN0ICogZnJvbSBhYmNkZWZnaCBvcmRlciBieSBhLGIsYyxkLGUs ZixnLGg7IiA+IGJlbmNoLnNxbAoJZWNobyAtbiAiJGV4cCBeIDg6ICIKCXBnYmVuY2ggLW4gLWYg YmVuY2guc3FsIC1UIDMwIC1NIHByZXBhcmVkIHBvc3RncmVzIHwgZ3JlcCBsYXRlbmN5CmRvbmUK --0000000000007172f50642c31d6d Content-Type: application/x-patch; name="v3-0001-Use-radix-sort-when-datum1-is-an-integer-type.patch" Content-Disposition: attachment; filename="v3-0001-Use-radix-sort-when-datum1-is-an-integer-type.patch" Content-Transfer-Encoding: base64 Content-ID: X-Attachment-Id: f_mhkg8ror1 RnJvbSA4MjQ3NzkzNDIzZGExNWU2Yzc1NTg4MDg4OTcyMDNmMzIzNGIyNjY2IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBKb2huIE5heWxvciA8am9obi5uYXlsb3JAcG9zdGdyZXNxbC5v cmc+CkRhdGU6IEZyaSwgMTcgT2N0IDIwMjUgMDk6NTc6NDMgKzA3MDAKU3ViamVjdDogW1BBVENI IHYzXSBVc2UgcmFkaXggc29ydCB3aGVuIGRhdHVtMSBpcyBhbiBpbnRlZ2VyIHR5cGUKClhYWCBy ZWdyZXNzaW9uIHRlc3RzIGRvbid0IHBhc3MgZm9yIHVuZGVyc3BlY2lmaWVkIHF1ZXJpZXM7IHRo aXMKaXMgZXhwZWN0ZWQKLS0tCiBzcmMvYmFja2VuZC91dGlscy9taXNjL2d1Y19wYXJhbWV0ZXJz LmRhdCB8ICAgNyArCiBzcmMvYmFja2VuZC91dGlscy9zb3J0L3R1cGxlc29ydC5jICAgICAgICB8 IDQ4OCArKysrKysrKysrKysrKysrKysrKystCiBzcmMvaW5jbHVkZS91dGlscy9ndWMuaCAgICAg ICAgICAgICAgICAgICB8ICAgMSArCiBzcmMvaW5jbHVkZS91dGlscy90dXBsZXNvcnQuaCAgICAg ICAgICAgICB8ICAxMiArLQogNCBmaWxlcyBjaGFuZ2VkLCA0ODcgaW5zZXJ0aW9ucygrKSwgMjEg ZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2JhY2tlbmQvdXRpbHMvbWlzYy9ndWNfcGFy YW1ldGVycy5kYXQgYi9zcmMvYmFja2VuZC91dGlscy9taXNjL2d1Y19wYXJhbWV0ZXJzLmRhdApp bmRleCAyNWRhNzY5ZWIzNS4uYmJmYzUyYWRjYWYgMTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL3V0 aWxzL21pc2MvZ3VjX3BhcmFtZXRlcnMuZGF0CisrKyBiL3NyYy9iYWNrZW5kL3V0aWxzL21pc2Mv Z3VjX3BhcmFtZXRlcnMuZGF0CkBAIC0zNDY5LDYgKzM0NjksMTMgQEAKICAgbWF4ID0+ICdJTlRf TUFYJywKIH0sCiAKK3sgbmFtZSA9PiAnd2lwX3JhZGl4X3NvcnQnLCB0eXBlID0+ICdib29sJywg Y29udGV4dCA9PiAnUEdDX1VTRVJTRVQnLCBncm91cCA9PiAnREVWRUxPUEVSX09QVElPTlMnLAor ICBzaG9ydF9kZXNjID0+ICdUZXN0IHJhZGl4IHNvcnQgZm9yIGRlYnVnZ2luZy4nLAorICBmbGFn cyA9PiAnR1VDX05PVF9JTl9TQU1QTEUnLAorICB2YXJpYWJsZSA9PiAnd2lwX3JhZGl4X3NvcnQn LAorICBib290X3ZhbCA9PiAndHJ1ZScsCit9LAorCiB7IG5hbWUgPT4gJ3dvcmtfbWVtJywgdHlw ZSA9PiAnaW50JywgY29udGV4dCA9PiAnUEdDX1VTRVJTRVQnLCBncm91cCA9PiAnUkVTT1VSQ0VT X01FTScsCiAgIHNob3J0X2Rlc2MgPT4gJ1NldHMgdGhlIG1heGltdW0gbWVtb3J5IHRvIGJlIHVz ZWQgZm9yIHF1ZXJ5IHdvcmtzcGFjZXMuJywKICAgbG9uZ19kZXNjID0+ICdUaGlzIG11Y2ggbWVt b3J5IGNhbiBiZSB1c2VkIGJ5IGVhY2ggaW50ZXJuYWwgc29ydCBvcGVyYXRpb24gYW5kIGhhc2gg dGFibGUgYmVmb3JlIHN3aXRjaGluZyB0byB0ZW1wb3JhcnkgZGlzayBmaWxlcy4nLApkaWZmIC0t Z2l0IGEvc3JjL2JhY2tlbmQvdXRpbHMvc29ydC90dXBsZXNvcnQuYyBiL3NyYy9iYWNrZW5kL3V0 aWxzL3NvcnQvdHVwbGVzb3J0LmMKaW5kZXggNWQ0NDExZGMzM2YuLjg0YWJkMTk5NWY3IDEwMDY0 NAotLS0gYS9zcmMvYmFja2VuZC91dGlscy9zb3J0L3R1cGxlc29ydC5jCisrKyBiL3NyYy9iYWNr ZW5kL3V0aWxzL3NvcnQvdHVwbGVzb3J0LmMKQEAgLTEwNCw2ICsxMDQsNyBAQAogI2luY2x1ZGUg ImNvbW1hbmRzL3RhYmxlc3BhY2UuaCIKICNpbmNsdWRlICJtaXNjYWRtaW4uaCIKICNpbmNsdWRl ICJwZ190cmFjZS5oIgorI2luY2x1ZGUgInBvcnQvcGdfYml0dXRpbHMuaCIKICNpbmNsdWRlICJz dG9yYWdlL3NobWVtLmgiCiAjaW5jbHVkZSAidXRpbHMvZ3VjLmgiCiAjaW5jbHVkZSAidXRpbHMv bWVtdXRpbHMuaCIKQEAgLTEyMiw2ICsxMjMsNyBAQAogCiAvKiBHVUMgdmFyaWFibGVzICovCiBi b29sCQl0cmFjZV9zb3J0ID0gZmFsc2U7Citib29sCQl3aXBfcmFkaXhfc29ydCA9IHRydWU7CiAK ICNpZmRlZiBERUJVR19CT1VOREVEX1NPUlQKIGJvb2wJCW9wdGltaXplX2JvdW5kZWRfc29ydCA9 IHRydWU7CkBAIC00OTAsNiArNDkyLDI1IEBAIHN0YXRpYyB2b2lkIHR1cGxlc29ydF91cGRhdGVt YXgoVHVwbGVzb3J0c3RhdGUgKnN0YXRlKTsKICAqIGFiYnJldmlhdGlvbnMgb2YgdGV4dCBvciBt dWx0aS1rZXkgc29ydHMuICBUaGVyZSBjb3VsZCBiZSEgIElzIGl0IHdvcnRoIGl0PwogICovCiAK Ky8qIFVzZWQgZm9yIGNvbmRpdGlvbmVkIGRhdHVtcywgc28gd2UgY2FuIGlnbm9yZSBOVUxMcyBh bmQgc29ydCBkaXJlY3Rpb24uICovCitzdGF0aWMgcGdfYXR0cmlidXRlX2Fsd2F5c19pbmxpbmUg aW50Citxc29ydF90dXBsZV9jb25kaXRpb25lZF9jb21wYXJlKFNvcnRUdXBsZSAqYSwgU29ydFR1 cGxlICpiLCBUdXBsZXNvcnRzdGF0ZSAqc3RhdGUpCit7CisJaWYgKGEtPmNvbmRfZGF0dW0xIDwg Yi0+Y29uZF9kYXR1bTEpCisJCXJldHVybiAtMTsKKwlpZiAoYS0+Y29uZF9kYXR1bTEgPiBiLT5j b25kX2RhdHVtMSkKKwkJcmV0dXJuIDE7CisKKwkvKgorCSAqIE5vIG5lZWQgdG8gd2FzdGUgZWZm b3J0IGNhbGxpbmcgdGhlIHRpZWJyZWFrIGZ1bmN0aW9uIHdoZW4gdGhlcmUgYXJlIG5vCisJICog b3RoZXIga2V5cyB0byBzb3J0IG9uLgorCSAqLworCWlmIChzdGF0ZS0+YmFzZS5vbmx5S2V5ICE9 IE5VTEwpCisJCXJldHVybiAwOworCisJcmV0dXJuIHN0YXRlLT5iYXNlLmNvbXBhcmV0dXBfdGll YnJlYWsoYSwgYiwgc3RhdGUpOworfQorCiAvKiBVc2VkIGlmIGZpcnN0IGtleSdzIGNvbXBhcmF0 b3IgaXMgc3N1cF9kYXR1bV91bnNpZ25lZF9jbXAgKi8KIHN0YXRpYyBwZ19hdHRyaWJ1dGVfYWx3 YXlzX2lubGluZSBpbnQKIHFzb3J0X3R1cGxlX3Vuc2lnbmVkX2NvbXBhcmUoU29ydFR1cGxlICph LCBTb3J0VHVwbGUgKmIsIFR1cGxlc29ydHN0YXRlICpzdGF0ZSkKQEAgLTU2Nyw2ICs1ODgsMTUg QEAgcXNvcnRfdHVwbGVfaW50MzJfY29tcGFyZShTb3J0VHVwbGUgKmEsIFNvcnRUdXBsZSAqYiwg VHVwbGVzb3J0c3RhdGUgKnN0YXRlKQogICogY29tbW9uIGNvbXBhcmlzb24gZnVuY3Rpb25zIG9u IHBhc3MtYnktdmFsdWUgbGVhZGluZyBkYXR1bXMuCiAgKi8KIAorI2RlZmluZSBTVF9TT1JUIHFz b3J0X3R1cGxlX2NvbmRpdGlvbmVkCisjZGVmaW5lIFNUX0VMRU1FTlRfVFlQRSBTb3J0VHVwbGUK KyNkZWZpbmUgU1RfQ09NUEFSRShhLCBiLCBzdGF0ZSkgcXNvcnRfdHVwbGVfY29uZGl0aW9uZWRf Y29tcGFyZShhLCBiLCBzdGF0ZSkKKyNkZWZpbmUgU1RfQ09NUEFSRV9BUkdfVFlQRSBUdXBsZXNv cnRzdGF0ZQorI2RlZmluZSBTVF9DSEVDS19GT1JfSU5URVJSVVBUUworI2RlZmluZSBTVF9TQ09Q RSBzdGF0aWMKKyNkZWZpbmUgU1RfREVGSU5FCisjaW5jbHVkZSAibGliL3NvcnRfdGVtcGxhdGUu aCIKKwogI2RlZmluZSBTVF9TT1JUIHFzb3J0X3R1cGxlX3Vuc2lnbmVkCiAjZGVmaW5lIFNUX0VM RU1FTlRfVFlQRSBTb3J0VHVwbGUKICNkZWZpbmUgU1RfQ09NUEFSRShhLCBiLCBzdGF0ZSkgcXNv cnRfdHVwbGVfdW5zaWduZWRfY29tcGFyZShhLCBiLCBzdGF0ZSkKQEAgLTYxNSw2ICs2NDUsMjEy IEBAIHFzb3J0X3R1cGxlX2ludDMyX2NvbXBhcmUoU29ydFR1cGxlICphLCBTb3J0VHVwbGUgKmIs IFR1cGxlc29ydHN0YXRlICpzdGF0ZSkKICNkZWZpbmUgU1RfREVGSU5FCiAjaW5jbHVkZSAibGli L3NvcnRfdGVtcGxhdGUuaCIKIAorCisvKgorICogV0lQOiBGb3Igbm93IHByZWZlciB0ZXN0IGNv dmVyYWdlIG9mIHJhZGl4IHNvcnQgaW4gQXNzZXJ0IGJ1aWxkcy4KKyAqLworI2lmZGVmIFVTRV9B U1NFUlRfQ0hFQ0tJTkcKKyNkZWZpbmUgUVNPUlRfVEhSRVNIT0xEIDAKKyNlbHNlCisjZGVmaW5l IFFTT1JUX1RIUkVTSE9MRCAyMDAKKyNlbmRpZgorCit0eXBlZGVmIHN0cnVjdCBQYXJ0aXRpb25J bmZvCit7CisJdW5pb24KKwl7CisJCXNpemVfdAkJY291bnQ7CisJCXNpemVfdAkJb2Zmc2V0Owor CX07CisJc2l6ZV90CQluZXh0X29mZnNldDsKK30JCQlQYXJ0aXRpb25JbmZvOworCitzdGF0aWMg aW5saW5lIHVpbnQ4X3QKK2V4dHJhY3Rfa2V5KERhdHVtIGtleSwgaW50IGxldmVsKQoreworCXJl dHVybiAoa2V5ID4+ICgoKFNJWkVPRl9EQVRVTSAtIDEpIC0gbGV2ZWwpICogOCkpICYgMHhGRjsK K30KKworc3RhdGljIGlubGluZSB2b2lkCitzd2FwKFNvcnRUdXBsZSAqYSwgU29ydFR1cGxlICpi KQoreworCVNvcnRUdXBsZQl0bXAgPSAqYTsKKworCSphID0gKmI7CisJKmIgPSB0bXA7Cit9CisK Ky8qCisgKiBDb25kaXRpb24gZGF0dW0gdG8gd29yayB3aXRoIHB1cmUgdW5zaWduZWQgY29tcGFy aXNvbiwKKyAqIHRha2luZyBBU0MvREVTQyBpbnRvIGFjY291bnQgYXMgd2VsbC4KKyAqLworc3Rh dGljIGlubGluZSBEYXR1bQorY29uZGl0aW9uX2RhdHVtKERhdHVtIG9yaWcsIFNvcnRTdXBwb3J0 IHNzdXApCit7CisJRGF0dW0JCWNvbmRfZGF0dW0xOworCisJaWYgKHNzdXAtPmNvbXBhcmF0b3Ig PT0gc3N1cF9kYXR1bV9zaWduZWRfY21wKQorCXsKKwkJLyogaXQgd2FzIGFscmVhZHkgY2FzdCB0 byB1bnNpZ25lZCB3aGVuIHN0b3JlZCAqLworCQljb25kX2RhdHVtMSA9IG9yaWcgXiAoVUlOVDY0 Q09OU1QoMSkgPDwgNjMpOworCX0KKwllbHNlIGlmIChzc3VwLT5jb21wYXJhdG9yID09IHNzdXBf ZGF0dW1faW50MzJfY21wKQorCXsKKwkJLyoKKwkJICogRmlyc3Qgbm9ybWFsaXplIHRvIHVpbnQz Mi4gVGVjaG5pY2FsbHksIHdlIGRvbid0IG5lZWQgdG8gZG8gdGhpcywKKwkJICogYnV0IGl0IGZv cmNlcyB0aGUgdXBwZXIgYnl0ZXMgdG8gcmVtYWluIHRoZSBzYW1lIHJlZ2FyZGxlc3Mgb2YKKwkJ ICogc2lnbi4KKwkJICovCisJCXVpbnQzMgkJdTMyID0gRGF0dW1HZXRVSW50MzIob3JpZykgXiAo KHVpbnQzMikgMSA8PCAzMSk7CisKKwkJY29uZF9kYXR1bTEgPSBVSW50MzJHZXREYXR1bSh1MzIp OworCX0KKwllbHNlCisJeworCQlBc3NlcnQoc3N1cC0+Y29tcGFyYXRvciA9PSBzc3VwX2RhdHVt X3Vuc2lnbmVkX2NtcCk7CisJCWNvbmRfZGF0dW0xID0gb3JpZzsKKwl9CisKKwlpZiAoc3N1cC0+ c3N1cF9yZXZlcnNlKQorCQljb25kX2RhdHVtMSA9IH5jb25kX2RhdHVtMTsKKworCXJldHVybiBj b25kX2RhdHVtMTsKK30KKworLyoKKyAqIEJhc2VkIG9uIGltcGxlbWVudGF0aW9uIGluIGh0dHBz Oi8vZ2l0aHViLmNvbS9za2FydXBrZS9za2Ffc29ydCAoQm9vc3QgbGljZW5zZSksCisgKiB3aXRo IHRoZSBmb2xsb3dpbmcgY2hhbmdlczoKKyAqICAtIHVucm9sbCBsb29wIGluIGNvdW50aW5nIHN0 ZXAKKyAqICAtIGNvdW50IHNvcnRlZCBwYXJ0aXRpb25zIGluIGV2ZXJ5IHBhc3MsIHJhdGhlciB0 aGFuIG1haW50YWluaW5nIGxpc3Qgb2YgdW5zb3J0ZWQgcGFydGl0aW9ucworICogVE9ETzogbWF0 Y2ggcXNvcnQgQVBJIHdpdGggbnVtYmVyIG9mIGVsZW1lbnRzIHJhdGhlciB0aGFuIGVuZCBwb2lu dGVyCisgKi8KK3N0YXRpYyB2b2lkCitza2FfYnl0ZV9zb3J0KFNvcnRUdXBsZSAqYmVnaW4sCisJ CQkgIFNvcnRUdXBsZSAqZW5kLCBpbnQgbGV2ZWwsIFR1cGxlc29ydHN0YXRlICpzdGF0ZSkKK3sK KwlQYXJ0aXRpb25JbmZvIHBhcnRpdGlvbnNbMjU2XSA9IHswfTsKKwl1aW50OF90CQlyZW1haW5p bmdfcGFydGl0aW9uc1syNTZdID0gezB9OworCXNpemVfdAkJdG90YWwgPSAwOworCWludAkJCW51 bV9wYXJ0aXRpb25zID0gMDsKKwlpbnQJCQludW1fcmVtYWluaW5nOworCisJLyogY291bnQga2V5 IGNodW5rcyAqLworCWZvciAoU29ydFR1cGxlICp0dXAgPSBiZWdpbjsgdHVwIDwgZW5kOyB0dXAr KykKKwl7CisJCXVpbnQ4CQlrZXlfY2h1bms7CisKKwkJa2V5X2NodW5rID0gZXh0cmFjdF9rZXko dHVwLT5jb25kX2RhdHVtMSwgbGV2ZWwpOworCQlwYXJ0aXRpb25zW2tleV9jaHVua10uY291bnQr KzsKKwl9CisKKwkvKiBjb21wdXRlIHBhcnRpdGlvbiBvZmZzZXRzICovCisJZm9yIChpbnQgaSA9 IDA7IGkgPCAyNTY7ICsraSkKKwl7CisJCXNpemVfdAkJY291bnQgPSBwYXJ0aXRpb25zW2ldLmNv dW50OworCisJCWlmIChjb3VudCkKKwkJeworCQkJcGFydGl0aW9uc1tpXS5vZmZzZXQgPSB0b3Rh bDsKKwkJCXRvdGFsICs9IGNvdW50OworCQkJcmVtYWluaW5nX3BhcnRpdGlvbnNbbnVtX3BhcnRp dGlvbnNdID0gaTsKKwkJCSsrbnVtX3BhcnRpdGlvbnM7CisJCX0KKwkJcGFydGl0aW9uc1tpXS5u ZXh0X29mZnNldCA9IHRvdGFsOworCX0KKworCW51bV9yZW1haW5pbmcgPSBudW1fcGFydGl0aW9u czsKKworCS8qCisJICogUGVybXV0ZSB0dXBsZXMgdG8gY29ycmVjdCBwYXJ0aXRpb24uIElmIHdl IHN0YXJ0ZWQgd2l0aCBvbmUgcGFydGl0aW9uLAorCSAqIHRoZXJlIGlzIG5vdGhpbmcgdG8gZG8u IElmIGEgcGVybXV0YXRpb24gZnJvbSBhIHByZXZpb3VzIGl0ZXJhdGlvbgorCSAqIHJlc3VsdHMg aW4gYSBzaW5nbGUgcGFydGl0aW9uIHRoYXQgaGFzbid0IGJlZW4gbWFya2VkIGFzIHNvcnRlZCwg d2UKKwkgKiBrbm93IGl0J3MgYWN0dWFsbHkgc29ydGVkLgorCSAqLworCXdoaWxlIChudW1fcmVt YWluaW5nID4gMSkKKwl7CisJCS8qCisJCSAqIFdlIGNhbiBvbmx5IGV4aXQgdGhlIGxvb3Agd2hl biBhbGwgcGFydGl0aW9ucyBhcmUgc29ydGVkLCBzbyBtdXN0CisJCSAqIHJlc2V0IGV2ZXJ5IGl0 ZXJhdGlvbgorCQkgKi8KKwkJbnVtX3JlbWFpbmluZyA9IG51bV9wYXJ0aXRpb25zOworCisJCWZv ciAoaW50IGkgPSAwOyBpIDwgbnVtX3BhcnRpdGlvbnM7IGkrKykKKwkJeworCQkJdWludDgJCWlk eCA9IHJlbWFpbmluZ19wYXJ0aXRpb25zW2ldOworCisJCQlQYXJ0aXRpb25JbmZvIHBhcnQgPSBw YXJ0aXRpb25zW2lkeF07CisKKwkJCWZvciAoU29ydFR1cGxlICpzdCA9IGJlZ2luICsgcGFydC5v ZmZzZXQ7CisJCQkJIHN0IDwgYmVnaW4gKyBwYXJ0Lm5leHRfb2Zmc2V0OworCQkJCSBzdCsrKQor CQkJeworCQkJCXVpbnQ4CQl0aGlzX3BhcnRpdGlvbiA9IGV4dHJhY3Rfa2V5KHN0LT5jb25kX2Rh dHVtMSwgbGV2ZWwpOworCQkJCXNpemVfdAkJb2Zmc2V0ID0gcGFydGl0aW9uc1t0aGlzX3BhcnRp dGlvbl0ub2Zmc2V0Kys7CisKKwkJCQlBc3NlcnQoYmVnaW4gKyBvZmZzZXQgPCBlbmQpOworCQkJ CXN3YXAoc3QsIGJlZ2luICsgb2Zmc2V0KTsKKwkJCX07CisKKwkJCWlmIChwYXJ0Lm9mZnNldCA9 PSBwYXJ0Lm5leHRfb2Zmc2V0KQorCQkJeworCQkJCS8qIHBhcnRpdGlvbiBpcyBzb3J0ZWQgKi8K KwkJCQludW1fcmVtYWluaW5nLS07CisJCQl9CisJCX0KKwl9CisKKwl7CisJCXNpemVfdAkJc3Rh cnRfb2Zmc2V0ID0gMDsKKwkJU29ydFR1cGxlICAqcGFydGl0aW9uX2JlZ2luID0gYmVnaW47CisK KwkJZm9yICh1aW50OF90ICppdCA9IHJlbWFpbmluZ19wYXJ0aXRpb25zLCAqZW5kID0gcmVtYWlu aW5nX3BhcnRpdGlvbnMgKyBudW1fcGFydGl0aW9uczsKKwkJCSBpdCAhPSBlbmQ7CisJCQkgKytp dCkKKwkJeworCQkJc2l6ZV90CQllbmRfb2Zmc2V0ID0gcGFydGl0aW9uc1sqaXRdLm5leHRfb2Zm c2V0OworCQkJU29ydFR1cGxlICAqcGFydGl0aW9uX2VuZCA9IGJlZ2luICsgZW5kX29mZnNldDsK KwkJCXB0cmRpZmZfdAludW1fZWxlbWVudHMgPSBlbmRfb2Zmc2V0IC0gc3RhcnRfb2Zmc2V0Owor CisJCQlpZiAobnVtX2VsZW1lbnRzID4gMSkKKwkJCXsKKwkJCQlpZiAobGV2ZWwgPCBTSVpFT0Zf REFUVU0gLSAxKQorCQkJCXsKKwkJCQkJaWYgKG51bV9lbGVtZW50cyA8IFFTT1JUX1RIUkVTSE9M RCkKKwkJCQkJeworCQkJCQkJcXNvcnRfdHVwbGVfY29uZGl0aW9uZWQocGFydGl0aW9uX2JlZ2lu LAorCQkJCQkJCQkJCQkJbnVtX2VsZW1lbnRzLAorCQkJCQkJCQkJCQkJc3RhdGUpOworCQkJCQl9 CisJCQkJCWVsc2UKKwkJCQkJeworCQkJCQkJc2thX2J5dGVfc29ydChwYXJ0aXRpb25fYmVnaW4s CisJCQkJCQkJCQkgIHBhcnRpdGlvbl9lbmQsCisJCQkJCQkJCQkgIGxldmVsICsgMSwKKwkJCQkJ CQkJCSAgc3RhdGUpOworCQkJCQl9CisJCQkJfQorCQkJCWVsc2UgaWYgKHN0YXRlLT5iYXNlLm9u bHlLZXkgPT0gTlVMTCkKKwkJCQl7CisJCQkJCS8qCisJCQkJCSAqIEZpbmlzaGVkIHJhZGl4IHNv cnQgb24gYWxsIGJ5dGVzIG9mIGNvbmRfZGF0dW0xCisJCQkJCSAqIChwb3NzaWJpbHkgYWJicmV2 aWF0ZWQpLCBub3cgcXNvcnQgd2l0aCB0aWVicmVhaworCQkJCQkgKiBjb21wYXJhdG9yLiBYWFgg Y29tcGFyZXR1cF90aWVicmVhayBjYW5ub3QgaW5zcGVjdAorCQkJCQkgKiBpc251bGwxLiBJbiBj b3JlLCB0aGUgb25seSB0aWVicmVhayB0aGF0IGRvZXMgc28gaXMKKwkJCQkJICogY29tcGFyZXR1 cF9kYXR1bV90aWVicmVhaywgYnV0IHdlIHdvdWxkbid0IGhhdmUgZ290dGVuCisJCQkJCSAqIGhl cmUgaWYgdGhhdCdzIHRoZSBjYXNlLgorCQkJCQkgKi8KKwkJCQkJcXNvcnRfdHVwbGUocGFydGl0 aW9uX2JlZ2luLAorCQkJCQkJCQludW1fZWxlbWVudHMsCisJCQkJCQkJCXN0YXRlLT5iYXNlLmNv bXBhcmV0dXBfdGllYnJlYWssCisJCQkJCQkJCXN0YXRlKTsKKwkJCQl9CisJCQl9CisJCQlzdGFy dF9vZmZzZXQgPSBlbmRfb2Zmc2V0OworCQkJcGFydGl0aW9uX2JlZ2luID0gcGFydGl0aW9uX2Vu ZDsKKwkJfQorCX0KK30KKwogLyoKICAqCQl0dXBsZXNvcnRfYmVnaW5feHh4CiAgKgpAQCAtMjY2 MywxMCArMjg5OSwyMDggQEAgc29ydF9ib3VuZGVkX2hlYXAoVHVwbGVzb3J0c3RhdGUgKnN0YXRl KQogCXN0YXRlLT5ib3VuZFVzZWQgPSB0cnVlOwogfQogCisvKiBXSVA6IGFsbG93IHR1cm5pbmcg Y29tbW9uIHByZWZpeCBza2lwcGluZyBvZmYgZm9yIHRlc3RpbmcgKi8KKyNkZWZpbmUgQ09NTU9O X1BSRUZJWAorCisvKgorICogQ29tcHV0ZSBjb25kaXRpb25lZCBkYXR1bXMgZm9yIFNvcnRUdXBs ZXMgc28gdGhhdCBhIHNpbmdsZQorICogdW5zaWduZWQgY29tcGFyaXNvbiByZXNvbHZlcyB0aGUg c29ydCBvcmRlciBvZiBkYXR1bTEuCisgKiBUaGVuIGRpc3BhdGNoIHRvIGVpdGhlciByYWRpeCBz b3J0IG9yIGEgc3BlY2lhbGl6ZWQgcXNvcnQuCisgKi8KK3N0YXRpYyB2b2lkCitzb3J0X3R1cGxl X2NvbmRpdGlvbmVkKFR1cGxlc29ydHN0YXRlICpzdGF0ZSkKK3sKKwlTb3J0U3VwcG9ydERhdGEg c3N1cCA9IHN0YXRlLT5iYXNlLnNvcnRLZXlzWzBdOworCisJYm9vbAkJbnVsbHNfZmlyc3QgPSBz c3VwLnNzdXBfbnVsbHNfZmlyc3Q7CisJU29ydFR1cGxlICAqZmlyc3QgPSBzdGF0ZS0+bWVtdHVw bGVzOworCVNvcnRUdXBsZSAgKmxhc3QgPSBzdGF0ZS0+bWVtdHVwbGVzICsgc3RhdGUtPm1lbXR1 cGNvdW50OworCVNvcnRUdXBsZSAgKm5vdF9udWxsX3N0YXJ0OworCXNpemVfdAkJZDEsCisJCQkJ ZDIsCisJCQkJbm90X251bGxfY291bnQ7CisjaWZkZWYgQ09NTU9OX1BSRUZJWAorCURhdHVtCQlm aXJzdF9kYXR1bSA9IDA7CisJRGF0dW0JCWNvbW1vbl91cHBlcl9iaXRzID0gMDsKKyNlbmRpZgor CWludAkJCWNvbW1vbl9wcmVmaXg7CisKKwkvKgorCSAqIFBhcnRpdGlvbiBieSBpc251bGwxLCBz aW5jZSB3ZSBjYW4gb25seSByYWRpeCBzb3J0IG9uIG5vbi1OVUxMCisJICogZWxlbWVudHMuIFRo aXMgYWxzbyBhbGxvd3MgdGhlIHFzb3J0IGZhbGxiYWNrIHRvIGlnbm9yZSBOVUxMcy4KKwkgKi8K KworCS8qCisJICogRmluZCB0aGUgbGVmdG1vc3QgTk9UIE5VTEwgdHVwbGUgaWYgTlVMTFMgRklS U1QsIG9yIGxlZnRtb3N0IE5VTEwKKwkgKiBlbGVtZW50IGlmIE5VTExTIExBU1QuCisJICovCisJ d2hpbGUgKGZpcnN0IDwgbGFzdCAmJiBmaXJzdC0+aXNudWxsMSA9PSBudWxsc19maXJzdCkKKwkJ Zmlyc3QrKzsKKworCS8qCisJICogWFhYIFdlIG11c3Qgc3RhcnQgImxhc3QiIGFmdGVyIHRoZSBm aW5hbCB0dXBsZSB0byBtYWludGFpbiB0aGUKKwkgKiBpbnZhcmlhbnQgdGhhdCBpdCBlbmRzIHVw IG9uZSBhZnRlciB0aGUgZmlyc3QgcGFydGl0aW9uLCBhbmQgdGhlIGZpcnN0CisJICogcGFydGl0 aW9uIG1heSBjb3JyZXNwb25kIHRvIHRoZSBlbnRpcmUgYXJyYXkuIElmICJmaXJzdCIgaXNuJ3Qg Z290dGVuCisJICogdGhpcyBmYXIsIHdlIG5lZWQgdG8gcHJlLWRlY3JlbWVudCAibGFzdCIgYmVm b3JlIGJlZ2lubmluZyBpdHMgbG9vcC4KKwkgKi8KKwlpZiAoZmlyc3QgPCBsYXN0KQorCQlsYXN0 LS07CisKKwkvKgorCSAqIEZpbmQgdGhlIHJpZ2h0bW9zdCBOVUxMIHR1cGxlIGlmIE5VTExTIEZJ UlNULCBvciByaWdodG1vc3QgTk9UIE5VTEwKKwkgKiB0dXBsZSBpZiBOVUxMUyBMQVNULgorCSAq LworCXdoaWxlIChmaXJzdCA8IGxhc3QgJiYgbGFzdC0+aXNudWxsMSAhPSBudWxsc19maXJzdCkK KwkJbGFzdC0tOworCisJLyogc3dhcCBwYWlycyBvZiB0dXBsZXMgdGhhdCBhcmUgaW4gdGhlIHdy b25nIG9yZGVyICovCisJd2hpbGUgKGZpcnN0IDwgbGFzdCkKKwl7CisJCXN3YXAoZmlyc3QsIGxh c3QpOworCQl3aGlsZSAoZmlyc3QgPCBsYXN0ICYmIGZpcnN0LT5pc251bGwxID09IG51bGxzX2Zp cnN0KQorCQkJZmlyc3QrKzsKKwkJd2hpbGUgKGZpcnN0IDwgbGFzdCAmJiBsYXN0LT5pc251bGwx ICE9IG51bGxzX2ZpcnN0KQorCQkJbGFzdC0tOworCX0KKworCWQxID0gbGFzdCAtIHN0YXRlLT5t ZW10dXBsZXM7CisJZDIgPSBzdGF0ZS0+bWVtdHVwY291bnQgLSBkMTsKKworCUFzc2VydChsYXN0 ID09IGZpcnN0KTsKKwlBc3NlcnQobGFzdCArIGQyID09IHN0YXRlLT5tZW10dXBsZXMgKyBzdGF0 ZS0+bWVtdHVwY291bnQpOworCWZvciAoU29ydFR1cGxlICpwbSA9IHN0YXRlLT5tZW10dXBsZXM7 CisJCSBwbSA8IHN0YXRlLT5tZW10dXBsZXMgKyBkMTsKKwkJIHBtKyspCisJCUFzc2VydChwbS0+ aXNudWxsMSA9PSBudWxsc19maXJzdCk7CisJZm9yIChTb3J0VHVwbGUgKnBtID0gbGFzdDsKKwkJ IHBtIDwgbGFzdCArIGQyOworCQkgcG0rKykKKwkJQXNzZXJ0KHBtLT5pc251bGwxICE9IG51bGxz X2ZpcnN0KTsKKworCS8qCisJICogU29ydCBOVUxMIHBhcnRpdGlvbiB1c2luZyB0aWVicmVhayBj b21wYXJhdG9yLiBYWFggdGhpcyB3aWxsIHJlcGVhdCB0aGUKKwkgKiBOVUxMIGNoZWNrIGZvciBh YmJyZXZpYXRlZCBrZXlzLgorCSAqLworCWlmIChudWxsc19maXJzdCkKKwl7CisJCXFzb3J0X3R1 cGxlKHN0YXRlLT5tZW10dXBsZXMsCisJCQkJCWQxLAorCQkJCQlzdGF0ZS0+YmFzZS5jb21wYXJl dHVwX3RpZWJyZWFrLAorCQkJCQlzdGF0ZSk7CisJCW5vdF9udWxsX3N0YXJ0ID0gbGFzdDsKKwkJ bm90X251bGxfY291bnQgPSBkMjsKKwl9CisJZWxzZQorCXsKKwkJcXNvcnRfdHVwbGUobGFzdCwK KwkJCQkJZDIsCisJCQkJCXN0YXRlLT5iYXNlLmNvbXBhcmV0dXBfdGllYnJlYWssCisJCQkJCXN0 YXRlKTsKKwkJbm90X251bGxfc3RhcnQgPSBzdGF0ZS0+bWVtdHVwbGVzOworCQlub3RfbnVsbF9j b3VudCA9IGQxOworCX0KKworCS8qCisJICogQ29uZGl0aW9uIGRhdHVtIHNvIHRoYXQgdW5zaWdu ZWQgY29tcGFyaXNpb24gaXMgb3JkZXItcHJlc2VydmluZywgYW5kCisJICogY29tcHV0ZSB0aGUg Y29tbW9uIHByZWZpeCB0byBza2lwIHVucHJvZHVjdGl2ZSByZWN1cnNpb24gc3RlcHMgZHVyaW5n CisJICogcmFkaXggc29ydC4KKwkgKi8KKwlmb3IgKFNvcnRUdXBsZSAqdHVwID0gbm90X251bGxf c3RhcnQ7CisJCSB0dXAgPCBub3RfbnVsbF9zdGFydCArIG5vdF9udWxsX2NvdW50OworCQkgdHVw KyspCisJeworCQlEYXR1bQkJY29uZF9kYXR1bTEgPSBjb25kaXRpb25fZGF0dW0odHVwLT5kYXR1 bTEsICZzc3VwKTsKKyNpZmRlZiBDT01NT05fUFJFRklYCisJCWlmICh0dXAgPT0gbm90X251bGxf c3RhcnQpCisJCXsKKwkJCS8qIE5lZWQgdG8gc3RhcnQgd2l0aCBzb21lIHZhbHVlLCBtYXkgYXMg d2VsbCBiZSB0aGUgZmlyc3Qgb25lLiAqLworCQkJZmlyc3RfZGF0dW0gPSBjb25kX2RhdHVtMTsK KwkJfQorCQllbHNlCisJCXsKKwkJCURhdHVtCQl0aGlzX2NvbW1vbl9iaXRzOworCisJCQkvKiBU aGUgYml0cyBpbiBjb21tb24gd2lsbCBiZSB6ZXJvICovCisJCQl0aGlzX2NvbW1vbl9iaXRzID0g Zmlyc3RfZGF0dW0gXiBjb25kX2RhdHVtMTsKKworCQkJLyoKKwkJCSAqIFdlJ3JlIHJlYWxseSBv bmx5IGludGVyZXN0ZWQgaW4gdGhlIGNhc2Ugd2hlcmUgdGhlIGxlZnRtb3N0IG9uZQorCQkJICog Yml0IGlzIGZ1cnRoZXIgbGVmdCwgYnV0IHRoaXMgYnJhbmNoIHNob3VsZCBiZSBwcmVkaWN0YWJs ZQorCQkJICogZW5vdWdoIG5vdCB0byB3YXN0ZSBjeWNsZXMgdHJ5aW5nIGhhcmRlci4KKwkJCSAq LworCQkJaWYgKHRoaXNfY29tbW9uX2JpdHMgPiBjb21tb25fdXBwZXJfYml0cykKKwkJCQljb21t b25fdXBwZXJfYml0cyA9IHRoaXNfY29tbW9uX2JpdHM7CisJCX0KKyNlbmRpZgorCQl0dXAtPmNv bmRfZGF0dW0xID0gY29uZF9kYXR1bTE7CisJfQorCisJLyoKKwkgKiBTb3J0IHRoZSBub3QtTlVM TCBwYXJ0aXRpb24sIHVzaW5nIHJhZGl4IHNvcnQgaWYgbGFyZ2UgZW5vdWdoLAorCSAqIG90aGVy d2lzZSBmYWxsIGJhY2sgdG8gcXVpY2tzb3J0LgorCSAqLworCWlmIChub3RfbnVsbF9jb3VudCA8 IFFTT1JUX1RIUkVTSE9MRCkKKwkJcXNvcnRfdHVwbGVfY29uZGl0aW9uZWQobm90X251bGxfc3Rh cnQsCisJCQkJCQkJCW5vdF9udWxsX2NvdW50LAorCQkJCQkJCQlzdGF0ZSk7CisJZWxzZQorCXsK KworCQkvKgorCQkgKiBUaGUgdXBwZXIgYml0cyBvZiBjb21tb25fdXBwZXJfYml0cyBhcmUgemVy byB3aGVyZSBhbGwgdmFsdWVzIGhhdmUKKwkJICogdGhlIHNhbWUgYml0cy4gVGhlIGJ5dGUgcG9z aXRpb24gb2YgdGhlIGxlZnRtb3N0IG9uZSBiaXQgaXMgdGhlCisJCSAqIGJ5dGUgd2hlcmUgcmFk aXggc29ydCBzaG91bGQgc3RhcnQgYnVja2V0aW5nLiBPUi1pbmcgaW4gdGhlIGxvd2VzdAorCQkg KiBiaXQgZ3VhcmRzIGFnYWluc3QgdW5kZWZpbmVkIGJlaGF2aW9yIHdpdGhvdXQgY2hhbmdpbmcg dGhlIHJlc3VsdC4KKwkJICovCisjaWZkZWYgQ09NTU9OX1BSRUZJWAorCQljb21tb25fcHJlZml4 ID0gc2l6ZW9mKERhdHVtKSAtIDEgLQorCQkJKHBnX2xlZnRtb3N0X29uZV9wb3M2NChjb21tb25f dXBwZXJfYml0cyB8IDEpIC8gQklUU19QRVJfQllURSk7CisjZWxzZQorCQljb21tb25fcHJlZml4 ID0gMDsKKyNlbmRpZgorCQlza2FfYnl0ZV9zb3J0KG5vdF9udWxsX3N0YXJ0LAorCQkJCQkgIG5v dF9udWxsX3N0YXJ0ICsgbm90X251bGxfY291bnQsCisJCQkJCSAgY29tbW9uX3ByZWZpeCwKKwkJ CQkJICBzdGF0ZSk7CisJfQorCisJLyoKKwkgKiBSZXN0b3JlIGZpZWxkcyB0aGF0IHdlcmUgb3Zl cndyaXR0ZW4gd2l0aCB0ZW1wb3JhcnkgY29uZGl0aW9uZWQgZGF0dW0xCisJICovCisJZm9yIChT b3J0VHVwbGUgKnR1cCA9IG5vdF9udWxsX3N0YXJ0OworCQkgdHVwIDwgbm90X251bGxfc3RhcnQg KyBub3RfbnVsbF9jb3VudDsKKwkJIHR1cCsrKQorCXsKKwkJLyogbmVlZCB0byByZXN0b3JlIE5P VCBOVUxMICovCisJCXR1cC0+aXNudWxsMSA9IGZhbHNlOworCQkvKiBiZSB0aWR5ICovCisJCXR1 cC0+c3JjdGFwZSA9IDA7CisJfQorfQorCisvKiBWZXJpZnkgc29ydCB1c2luZyBzdGFuZGFyZCBj b21wYXJhdG9yLiAqLworc3RhdGljIHZvaWQKK2NoZWNrX3NvcnRlZChUdXBsZXNvcnRzdGF0ZSAq c3RhdGUpCit7CisjaWZkZWYgVVNFX0FTU0VSVF9DSEVDS0lORworCWZvciAoU29ydFR1cGxlICpw bSA9IHN0YXRlLT5tZW10dXBsZXMgKyAxOworCQkgcG0gPCBzdGF0ZS0+bWVtdHVwbGVzICsgc3Rh dGUtPm1lbXR1cGNvdW50OworCQkgcG0rKykKKwl7CisjaWYgMAorCQlBc3NlcnQoQ09NUEFSRVRV UChzdGF0ZSwgcG0gLSAxLCBwbSkgPD0gMCk7CisjZWxzZQorCQlpZiAoQ09NUEFSRVRVUChzdGF0 ZSwgcG0gLSAxLCBwbSkgPiAwKQorCQkJZWxvZyhFUlJPUiwgIlNPUlQgRkFJTEVEIik7CisjZW5k aWYKKwl9CisjZW5kaWYKK30KKwogLyoKLSAqIFNvcnQgYWxsIG1lbXR1cGxlcyB1c2luZyBzcGVj aWFsaXplZCBxc29ydCgpIHJvdXRpbmVzLgorICogU29ydCBhbGwgbWVtdHVwbGVzIHVzaW5nIHNw ZWNpYWxpemVkIHJvdXRpbmVzLgogICoKLSAqIFF1aWNrc29ydCBpcyB1c2VkIGZvciBzbWFsbCBp bi1tZW1vcnkgc29ydHMsIGFuZCBleHRlcm5hbCBzb3J0IHJ1bnMuCisgKiBRdWlja3NvcnQgb3Ig cmFkaXggc29ydCBpcyB1c2VkIGZvciBzbWFsbCBpbi1tZW1vcnkgc29ydHMsIGFuZCBleHRlcm5h bCBzb3J0IHJ1bnMuCiAgKi8KIHN0YXRpYyB2b2lkCiB0dXBsZXNvcnRfc29ydF9tZW10dXBsZXMo VHVwbGVzb3J0c3RhdGUgKnN0YXRlKQpAQCAtMjY4MSwyNiArMzExNSw0MiBAQCB0dXBsZXNvcnRf c29ydF9tZW10dXBsZXMoVHVwbGVzb3J0c3RhdGUgKnN0YXRlKQogCQkgKi8KIAkJaWYgKHN0YXRl LT5iYXNlLmhhdmVEYXR1bTEgJiYgc3RhdGUtPmJhc2Uuc29ydEtleXMpCiAJCXsKLQkJCWlmIChz dGF0ZS0+YmFzZS5zb3J0S2V5c1swXS5jb21wYXJhdG9yID09IHNzdXBfZGF0dW1fdW5zaWduZWRf Y21wKQotCQkJewotCQkJCXFzb3J0X3R1cGxlX3Vuc2lnbmVkKHN0YXRlLT5tZW10dXBsZXMsCi0J CQkJCQkJCQkgc3RhdGUtPm1lbXR1cGNvdW50LAotCQkJCQkJCQkJIHN0YXRlKTsKLQkJCQlyZXR1 cm47Ci0JCQl9Ci0JCQllbHNlIGlmIChzdGF0ZS0+YmFzZS5zb3J0S2V5c1swXS5jb21wYXJhdG9y ID09IHNzdXBfZGF0dW1fc2lnbmVkX2NtcCkKKwkJCVNvcnRTdXBwb3J0RGF0YSBzc3VwID0gc3Rh dGUtPmJhc2Uuc29ydEtleXNbMF07CisKKwkJCWlmICh3aXBfcmFkaXhfc29ydCkKIAkJCXsKLQkJ CQlxc29ydF90dXBsZV9zaWduZWQoc3RhdGUtPm1lbXR1cGxlcywKLQkJCQkJCQkJICAgc3RhdGUt Pm1lbXR1cGNvdW50LAotCQkJCQkJCQkgICBzdGF0ZSk7Ci0JCQkJcmV0dXJuOworCQkJCWlmICgo c3N1cC5jb21wYXJhdG9yID09IHNzdXBfZGF0dW1fdW5zaWduZWRfY21wIHx8CisJCQkJCSBzc3Vw LmNvbXBhcmF0b3IgPT0gc3N1cF9kYXR1bV9zaWduZWRfY21wIHx8CisJCQkJCSBzc3VwLmNvbXBh cmF0b3IgPT0gc3N1cF9kYXR1bV9pbnQzMl9jbXApKQorCQkJCXsKKwkJCQkJc29ydF90dXBsZV9j b25kaXRpb25lZChzdGF0ZSk7CisJCQkJCWNoZWNrX3NvcnRlZChzdGF0ZSk7CisJCQkJCXJldHVy bjsKKwkJCQl9CiAJCQl9Ci0JCQllbHNlIGlmIChzdGF0ZS0+YmFzZS5zb3J0S2V5c1swXS5jb21w YXJhdG9yID09IHNzdXBfZGF0dW1faW50MzJfY21wKQorCQkJZWxzZQogCQkJewotCQkJCXFzb3J0 X3R1cGxlX2ludDMyKHN0YXRlLT5tZW10dXBsZXMsCi0JCQkJCQkJCSAgc3RhdGUtPm1lbXR1cGNv dW50LAotCQkJCQkJCQkgIHN0YXRlKTsKLQkJCQlyZXR1cm47CisJCQkJaWYgKHN0YXRlLT5iYXNl LnNvcnRLZXlzWzBdLmNvbXBhcmF0b3IgPT0gc3N1cF9kYXR1bV91bnNpZ25lZF9jbXApCisJCQkJ eworCQkJCQlxc29ydF90dXBsZV91bnNpZ25lZChzdGF0ZS0+bWVtdHVwbGVzLAorCQkJCQkJCQkJ CSBzdGF0ZS0+bWVtdHVwY291bnQsCisJCQkJCQkJCQkJIHN0YXRlKTsKKwkJCQkJcmV0dXJuOwor CQkJCX0KKwkJCQllbHNlIGlmIChzdGF0ZS0+YmFzZS5zb3J0S2V5c1swXS5jb21wYXJhdG9yID09 IHNzdXBfZGF0dW1fc2lnbmVkX2NtcCkKKwkJCQl7CisJCQkJCXFzb3J0X3R1cGxlX3NpZ25lZChz dGF0ZS0+bWVtdHVwbGVzLAorCQkJCQkJCQkJICAgc3RhdGUtPm1lbXR1cGNvdW50LAorCQkJCQkJ CQkJICAgc3RhdGUpOworCQkJCQlyZXR1cm47CisJCQkJfQorCQkJCWVsc2UgaWYgKHN0YXRlLT5i YXNlLnNvcnRLZXlzWzBdLmNvbXBhcmF0b3IgPT0gc3N1cF9kYXR1bV9pbnQzMl9jbXApCisJCQkJ eworCQkJCQlxc29ydF90dXBsZV9pbnQzMihzdGF0ZS0+bWVtdHVwbGVzLAorCQkJCQkJCQkJICBz dGF0ZS0+bWVtdHVwY291bnQsCisJCQkJCQkJCQkgIHN0YXRlKTsKKwkJCQkJcmV0dXJuOworCQkJ CX0KIAkJCX0KIAkJfQogCmRpZmYgLS1naXQgYS9zcmMvaW5jbHVkZS91dGlscy9ndWMuaCBiL3Ny Yy9pbmNsdWRlL3V0aWxzL2d1Yy5oCmluZGV4IGYyMWVjMzdkYTg5Li5iYzZmN2ZhNjBmMyAxMDA2 NDQKLS0tIGEvc3JjL2luY2x1ZGUvdXRpbHMvZ3VjLmgKKysrIGIvc3JjL2luY2x1ZGUvdXRpbHMv Z3VjLmgKQEAgLTMyNCw2ICszMjQsNyBAQCBleHRlcm4gUEdETExJTVBPUlQgaW50IHRjcF91c2Vy X3RpbWVvdXQ7CiBleHRlcm4gUEdETExJTVBPUlQgY2hhciAqcm9sZV9zdHJpbmc7CiBleHRlcm4g UEdETExJTVBPUlQgYm9vbCBpbl9ob3Rfc3RhbmRieV9ndWM7CiBleHRlcm4gUEdETExJTVBPUlQg Ym9vbCB0cmFjZV9zb3J0OworZXh0ZXJuIFBHRExMSU1QT1JUIGJvb2wgd2lwX3JhZGl4X3NvcnQ7 CiAKICNpZmRlZiBERUJVR19CT1VOREVEX1NPUlQKIGV4dGVybiBQR0RMTElNUE9SVCBib29sIG9w dGltaXplX2JvdW5kZWRfc29ydDsKZGlmZiAtLWdpdCBhL3NyYy9pbmNsdWRlL3V0aWxzL3R1cGxl c29ydC5oIGIvc3JjL2luY2x1ZGUvdXRpbHMvdHVwbGVzb3J0LmgKaW5kZXggMGJmNTU5MDJhYTEu LjI3Y2QxMjk4NWZhIDEwMDY0NAotLS0gYS9zcmMvaW5jbHVkZS91dGlscy90dXBsZXNvcnQuaAor KysgYi9zcmMvaW5jbHVkZS91dGlscy90dXBsZXNvcnQuaApAQCAtMTQ5LDggKzE0OSwxNiBAQCB0 eXBlZGVmIHN0cnVjdAogewogCXZvaWQJICAgKnR1cGxlOwkJCS8qIHRoZSB0dXBsZSBpdHNlbGYg Ki8KIAlEYXR1bQkJZGF0dW0xOwkJCS8qIHZhbHVlIG9mIGZpcnN0IGtleSBjb2x1bW4gKi8KLQli b29sCQlpc251bGwxOwkJLyogaXMgZmlyc3Qga2V5IGNvbHVtbiBOVUxMPyAqLwotCWludAkJCXNy Y3RhcGU7CQkvKiBzb3VyY2UgdGFwZSBudW1iZXIgKi8KKworCXVuaW9uCisJeworCQlzdHJ1Y3QK KwkJeworCQkJYm9vbAkJaXNudWxsMTsJCS8qIGlzIGZpcnN0IGtleSBjb2x1bW4gTlVMTD8gKi8K KwkJCWludAkJCXNyY3RhcGU7CQkvKiBzb3VyY2UgdGFwZSBudW1iZXIgKi8KKwkJfTsKKwkJRGF0 dW0JCWNvbmRfZGF0dW0xOwkJLyogc29ydCBrZXkgZm9yIHJhZGl4IHNvcnQgKi8KKwl9OwogfSBT b3J0VHVwbGU7CiAKIHR5cGVkZWYgaW50ICgqU29ydFR1cGxlQ29tcGFyYXRvcikgKGNvbnN0IFNv cnRUdXBsZSAqYSwgY29uc3QgU29ydFR1cGxlICpiLAotLSAKMi41MS4xCgo= --0000000000007172f50642c31d6d--