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.96) (envelope-from ) id 1x65qU-0001Vb-0Z for pgsql-hackers@arkaria.postgresql.org; Mon, 14 Sep 2026 12:31:39 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.96) (envelope-from ) id 1x65qT-00Ckw5-1M for pgsql-hackers@arkaria.postgresql.org; Mon, 14 Sep 2026 12:31:37 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.96) (envelope-from ) id 1x65qN-00Ck0o-1W for pgsql-hackers@lists.postgresql.org; Mon, 14 Sep 2026 12:31:31 +0000 Received: from mail-ej2-x10.google.com ([2a00:1450:4864:34::10]) by magus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.98.2) (envelope-from ) id 1x65qI-00000000Npz-2Fku for pgsql-hackers@postgresql.org; Mon, 14 Sep 2026 12:31:31 +0000 Received: by mail-ej2-x10.google.com with SMTP id a640c23a62f3a-c254f55efe5so255373766b.2 for ; Mon, 14 Sep 2026 05:31:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1789389086; x=1789993886; darn=postgresql.org; h=in-reply-to:content-language:references:cc:to:subject:user-agent :mime-version:date:message-id:content-type:from:from:to:cc:subject :date:message-id:reply-to:content-type; bh=PlBYF3++GzlLm5oNWmnYbOPMkJ9m0+cBgGrAJl8CwQ0=; b=h05/Ahv7RHk/hRaoX+dQjJAK0yp4Xtb9+c/3Lo7MlRxG8xoqJ9oLy/1HNGESr+uV/6 vAC09/8TpMLePwodkvUMRlkSBk6pikmDRbttztUUAEaNVtd8HNa2JAUBfsa2HMrLfDjI c6LZq9miYFMUCla6Zcoi2NOhPhfw7IcZOTpj1QxauTJZ4Vb0njXDAFG5a0wv6e4c5XtI TUsaryi1dYYgSnFXIt6i9ACgh2CrEMUvEUry7eRWTY90/DVhzkwkgXfw+FgvXQXgca8X Xt8lfjnZrTnLTk0LLht6iLsuf++tq+Yu2hDqO+1B8WEeXc9H9eAQanvpj43q4IOxKW+p We+Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1789389086; x=1789993886; h=in-reply-to:content-language:references:cc:to:subject:user-agent :mime-version:date:message-id:content-type:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=PlBYF3++GzlLm5oNWmnYbOPMkJ9m0+cBgGrAJl8CwQ0=; b=HO0YvGZtGqEADCS9UEv0MyT3Qyxpeua//9tViynVueJIyy/PbwtEe/HtEQrCMxJXUB yzPfVcUhcCR4iDVszlQVMXrblt3gMJtaqWKSv59fRtv4tWr5RM5n9S7SYkOd3IsSjATT R/qPWNfWtHuWh47zQDJCnr34CCZtBVFUnnnKGN8OyagEsmXTbUyXjwsw6cz3dXQzPzeJ QtDA/AtcSWZB1C8tnJ4Y2mJ1efxIGk4t//AyyhI+Eg9P/bm2FkOo8NSrNnLGQvSXJE+8 jq3n55EJf2ZbkY3cKSc8aUcDULCpD6Wtpbc4bxjGDmLod2sd1hFyB/PYd7K71e90q+om TC7Q== X-Forwarded-Encrypted: i=1; AKwUvBzi+SFWEiM/NIXyX4Pet4oNWpV+6bsxurGXaakJLeYKt4VchVgZcp3WxvQ1cSBkTh7Pz2HOhYlibpoXZXFM@postgresql.org X-Gm-Message-State: AFuF++kGtRzAUV4969KFXXVQl6AC5yAVRiyPZwlyYxr/9wzCeyHo+QLl cjV5c7LhamigCg+UrD+geUDCh1xy6bVwXvthMWAgoxahJu6qNUU1GQw1 X-Gm-Gg: AYBFou3Akkmhne18JZ/UZbD+7pgWzUVr0w9t/tj5U7JLUyP3zVcqalZZejD2jlJQMfQ 1XmsxEACirqt3ttOYkPFQ85eIELILGgzQxVDH4X4yIhU2Az4537uVOuMIrz4YFkw0rREodC92PI NfyXteVVWdMuPcI5yuL+ll02kJQLQT4sIknYPrtHtO2voNjclE2S4rCeVUcHMLZ3v6OuAixTlNE lM9Bzu5k8T+RaUa6exIK4Dl+TpfdUAwD4hBSiv4HdxIVfRMZmDFncL1HDl4GrcX/MxoxekCpcu0 oNelto1JJ/yUZ8Z5JnYzP9X3zbbA/s1+isHhUDuW8Dsw0C21h9R3oIbZ6aD7pTFnue0pplpjoR+ +CbXuZ/ff2URlq9SEU2cuTr1h4PJM3BSKZP/Gu4+e9gl3kEnBrkzXY72Ed+Io0qYayGp+kaTZlQ iltjWS5NYv3eXtKMUlutcVuh0BTfTVPdXh3kWN4ezPOQbRmUUpumnUDSgkDBD3URyMaoAQwlUKM 8VR+ExullZkDF6GXGzh6mOhw4UjIowJr99KGkJB7pIRoyvdRhDfDmHKPOGB9T4H8ItbBRRLWnUl 0WHfmPSFcHxTE3vP1ZywvjPjfkUv/jyRzrlp X-Received: by 2002:a17:907:d25:b0:c20:f4ee:7c97 with SMTP id a640c23a62f3a-c29b84c7112mr168755966b.5.1789389086098; Mon, 14 Sep 2026 05:31:26 -0700 (PDT) Received: from ?IPV6:2003:c1:5f42:fe9b:c5fa:ec48:1c9e:ceaf? (p200300062339a69bc5faec481c9eceaf.dip0.t-ipconnect.de. [2003:6:2339:a69b:c5fa:ec48:1c9e:ceaf]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-c296614323csm425699866b.59.2026.09.14.05.31.24 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 14 Sep 2026 05:31:24 -0700 (PDT) From: David Geier X-Google-Original-From: David Geier Content-Type: multipart/mixed; boundary="------------i0uBgFL0BR4Os7d0xe0pjhHC" Message-ID: <10afd923-38f4-451c-af89-34f8654533cb@googlemail.com> Date: Mon, 14 Sep 2026 14:31:23 +0200 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: Reduce build times of pg_trgm GIN indexes To: Matthias van de Meent , David Geier Cc: Japin Li , Heikki Linnakangas , pgsql-hackers References: <5d366878-2007-4d31-861e-19294b7a583b@gmail.com> <2e11134f-02c3-43da-8c39-fb520a1a251d@iki.fi> <66620ec7-0f81-4813-9cf1-b901a56efcc3@gmail.com> <2a76b5ef-4b12-4023-93a1-eed6e64968f3@gmail.com> <6439c655-e281-409d-b884-6586750d5820@iki.fi> <5e74f77a-1dfc-45b5-9fcf-62afe8dbbaf2@gmail.com> <5650bf75-dcb8-446d-8cba-e626eb44594b@gmail.com> <10395cb6-a804-49ac-b2f1-3f98d7204359@gmail.com> <1c90691c-db53-420a-be6c-e0323e6ae9f1@gmail.com> Content-Language: en-US In-Reply-To: List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk This is a multi-part message in MIME format. --------------i0uBgFL0BR4Os7d0xe0pjhHC Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit >>> 2. This increases the memory requirements of trigram_qsort by a huge margin. >>> Could you change the radixsort to operate in-place, so that the new >>> buffer is not needed? >> Trigram radix sort is only called from generate_trgm() and >> generate_wildcard_trgm() which are both used to extract the unique >> trigrams from a _single_ string value. >> We don't radix sort trigrams of multiple string values. Hence, the >> maximum increase in memory, while building the GIN index, is in the size >> of the longest string encountered, not in the number of rows. >> >> Given that in-place radix sort is a lot more complex and slower, I think >> the current tradeoff is fine. >> >> Beyond that, other GIN index functions also allocate extra memory on a >> per-value basis which shows that this should not be a problem in >> practice (e.g. ginarrayextract(), gin_extract_value_trgm(), ...). > It happens, but I'd still like to avoid new O(large) allocations, if > that's possible without losing performance; allocations aren't free, > after all. I've played around with an in-place MSD radix sort which partitions the data and then recurses into each partition. With that code the overall performance regresses significantly (> 30%) which means the regression for just the sort is even higher. I've attached my code, in case you want to take a look. >>> 3. The implementation for trigram_qsort_unsigned has not been adjusted >>> nor replaced, and so keeps the same old performance that >>> trigram_qsort_signed had. >>> Please make sure to also adjust that implementation. >> Done. >> >> I laid out the code such that the compiler has the possibility to fully >> inline both variants to get rid of the extra code in radix_key() for >> flipping the sign bit in the unsigned case. But even if it doesn't, >> radix_key() can be branchless and the performance is anyway dominated by >> memory traffic. > Yes, did you check that it actually gets inlined and/or optimized for > signed/unsigned versions in your local compiler? Yes, it does. The compiler opted for putting upfront either 0 or 0x80 into the register it later uses to XOR with, depending on if char_is_signed is true or false. It always does the XOR but it's completely branchless inside the loops. That's fine, given that the XOR is by no means the hotspot and duplicating the function would increase code size. > Further note: > Now that trigram_radix_sort_with_signedness ends with a memcpy, and > every caller then calls trigram_qunique on that output, wouldn't it > make sense to include `trigram_qunique` in that final memcpy of > trigram_radix_sort? > Checking that the output is unique during the copy operation could > avoid another n_entries memory accesses vs post-copy uniqify > operations, and also save memmoves. Good idea. I've tried that but it's slower than doing it in-place. At least for my benchmark which mostly processes trigram arrays of ~10 to a few thousand trigrams with a high number of duplicates (which is pretty realistic because in most cases, the input strings are short to medium long). What we could do instead is allocate a new TRGM varlena and use it as temporary radix sort buffer. The qunique() can then run on that buffer and we then replace the input TRGM with the temporary TRGM. This is marginally faster but the code is uglier as now the trigram radix sort function is concerned with messing around with the TRGM varlena. Hence, I'm leaning towards not using it. A third variant I've tried is running qunique() on the final buffer from the radix sort and then only copying over the unique trigrams back to the input buffer. The difference is within noise but I kept it because it doesn't make the code harder to read, see attached patch. Speaking about performance: apart from such small tweaks there are the following bigger optimizations I'm still planning to do, once this patch set went in: 1. Optimize the string processing code in generate_trgm_only() which extracts the non-unique trigrams from the input strings. Currently, this function takes up ~40% of all runtime. 2. Store trigrams as 32-bit integers inside the arrays to improve qunique() and sorting performance, as well as avoid the conversion to int-arrays in some places. > Newly noticed: > > The new sort template for ItemPointerData should probably be a public > and reusable function, as I see many cases of qsort(..., ..., > sizeof(ItemPointerData), someItemPtrCompareFn), where qsort itself is > backed by a generic sort_template.h implementation. Pulling the > specialized implementation into its own function would allow those > callsites to be updated to the specialized version that we're > generating here. > I had a look but only found four occurrences apart from the new sort in my patch: 1. 1x in nodeTidScan.c 2. 1x in heap_surgery.c 3. 2x in test_tidstore.c Have you come across any other? Attached is the updated patch set. Only change is doing the qunique() inside the radix sort function and renaming a few function to better reflect that apart from sorting it now also deduplicates. -- David Geier --------------i0uBgFL0BR4Os7d0xe0pjhHC Content-Type: text/x-csrc; charset=UTF-8; name="trigram_in_place_radix_sort.c" Content-Disposition: attachment; filename="trigram_in_place_radix_sort.c" Content-Transfer-Encoding: base64 c3RhdGljIHNpemVfdAp0cmlncmFtX3JhZGl4X3NvcnRfYW5kX3VuaXF1ZV9yZWN1cnNlKHRy Z20gKnRyZywgc2l6ZV90IGNvdW50LCBpbnQgYmFzZSwKCQkJCQkJCQkJICBib29sIGNoYXJf aXNfc2lnbmVkKQp7CglzaXplX3QJCWZyZXFzWzI1Nl07CglzaXplX3QJCXN0YXJ0c1syNTZd OwoJc2l6ZV90CQljdXJbMjU2XTsKCXNpemVfdAkJaTsKCWludAkJCWs7CgoJaWYgKGNvdW50 IDw9IDEpCgkJcmV0dXJuIGNvdW50OwoJaWYgKGJhc2UgPj0gMykKCQlyZXR1cm4gcXVuaXF1 ZSh0cmcsIGNvdW50LCBzaXplb2YodHJnbSksIENNUFRSR01fRVEpOwoKCW1lbXNldChmcmVx cywgMCwgc2l6ZW9mKGZyZXFzKSk7Cglmb3IgKGkgPSAwOyBpIDwgY291bnQ7IGkrKykKCQlm cmVxc1tyYWRpeF9rZXkodHJnW2ldW2Jhc2VdLCBjaGFyX2lzX3NpZ25lZCldKys7CgoJc3Rh cnRzWzBdID0gMDsKCWZvciAoayA9IDE7IGsgPCAyNTY7IGsrKykKCQlzdGFydHNba10gPSBz dGFydHNbayAtIDFdICsgZnJlcXNbayAtIDFdOwoKCW1lbWNweShjdXIsIHN0YXJ0cywgc2l6 ZW9mKGN1cikpOwoKCWZvciAoaSA9IDA7IGkgPCBjb3VudDsgaSsrKQoJewoJCWZvciAoOzsp CgkJewoJCQl1bnNpZ25lZCBjaGFyIGIgPSByYWRpeF9rZXkodHJnW2ldW2Jhc2VdLCBjaGFy X2lzX3NpZ25lZCk7CgoJCQlpZiAoaSA+PSBzdGFydHNbYl0gJiYgaSA8IGN1cltiXSkKCQkJ CWJyZWFrOwoKCQkJewoJCQkJc2l6ZV90CQlqID0gY3VyW2JdKys7CgkJCQl0cmdtCQl0bXA7 CgoJCQkJbWVtY3B5KHRtcCwgdHJnW2ldLCBzaXplb2YodHJnbSkpOwoJCQkJbWVtY3B5KHRy Z1tpXSwgdHJnW2pdLCBzaXplb2YodHJnbSkpOwoJCQkJbWVtY3B5KHRyZ1tqXSwgdG1wLCBz aXplb2YodHJnbSkpOwoJCQl9CgkJfQoJfQoKCWZvciAoayA9IDA7IGsgPCAyNTY7IGsrKykK CQlpZiAoZnJlcXNba10gPiAxKQoJCQl0cmlncmFtX3JhZGl4X3NvcnRfYW5kX3VuaXF1ZV9y ZWN1cnNlKHRyZyArIHN0YXJ0c1trXSwgZnJlcXNba10sIGJhc2UgKyAxLCBjaGFyX2lzX3Np Z25lZCk7Cn0= --------------i0uBgFL0BR4Os7d0xe0pjhHC Content-Type: text/x-patch; charset=UTF-8; name="v11-0003-Replace-GIN-build-accumulator-RB-tree-with-a-has.patch" Content-Disposition: attachment; filename*0="v11-0003-Replace-GIN-build-accumulator-RB-tree-with-a-has.pa"; filename*1="tch" Content-Transfer-Encoding: base64 RnJvbSA2ZDkyZjAzY2EyODQ4NzZkNzE5ODQyMzQzMmQ2NTQwMDcxNzM4M2ExIE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBEYXZpZCBHZWllciA8Z2VpZGF2LnBnQGdtYWlsLmNv bT4KRGF0ZTogV2VkLCAyMiBBcHIgMjAyNiAxNDowMDo0MCArMDIwMApTdWJqZWN0OiBbUEFU Q0ggdjExIDMvM10gUmVwbGFjZSBHSU4gYnVpbGQgYWNjdW11bGF0b3IgUkItdHJlZSB3aXRo IGEgaGFzaG1hcAoKUmVwbGFjZSB0aGUgcmVkLWJsYWNrIHRyZWUgdXNlZCBieSBnaW5JbnNl cnRCQUVudHJpZXMoKSB3aXRoIGEgaGFzaCB0YWJsZQpiYXNlZCBvbiBzaW1wbGVoYXNoLmgu IFRoaXMga2VlcHMgdGhlIHNhbWUgYmFzaWMgYWNjdW11bGF0aW9uIHN0cmF0ZWd5CmFzIHRo ZSBwcmV2aW91cyBpbXBsZW1lbnRhdGlvbiB3aGlsZSBjaGFuZ2luZyBrZXkgbG9va3VwIGFu ZCBkZWR1cGxpY2F0aW9uCmZyb20gTyhsb2cobnVtX3VuaXF1ZV9rZXlzKSkgdHJlZSBvcGVy YXRpb25zIHRvIGV4cGVjdGVkIE8oMSkgaGFzaC10YWJsZQpvcGVyYXRpb25zLiBBcyBhIHJl c3VsdCwgdGhlIG92ZXJhbGwgY29tcGxleGl0eSBjaGFuZ2VzIGZyb20KCiAgICBPKG51bV90 b3RhbF9rZXlzICogbG9nKG51bV91bmlxdWVfa2V5cykpCgp0bwoKICAgIE8obnVtX3RvdGFs X2tleXMgKyBudW1fdW5pcXVlX2tleXMgKiBsb2cobnVtX3VuaXF1ZV9rZXlzKSkKClRoZSBs YXR0ZXIgaXMgcHJlZmVyYWJsZSBmb3IgdGhlIHVzdWFsIGNhc2UsIHdoZXJlIHRoZSBudW1i ZXIgb2YgdW5pcXVlCmtleXMgaXMgbXVjaCBzbWFsbGVyIHRoYW4gdGhlIG51bWJlciBvZiBy b3dzLiBFdmVuIHdoZW4gbW9zdCBvciBhbGwga2V5cwphcmUgdW5pcXVlLCB0aGUgUkItdHJl ZSByZWJhbGFuY2luZyBvcGVyYXRpb25zIGFyZSBzdWZmaWNpZW50bHkKZXhwZW5zaXZlIHRo YXQgdGhlIHRoZW9yZXRpY2FsIHdvcnN0LWNhc2UgYWR2YW50YWdlIG9mIHRoZSB0cmVlIGRv ZXMgbm90Cm5lY2Vzc2FyaWx5IHRyYW5zbGF0ZSBpbnRvIGJldHRlciBydW50aW1lLgoKVGhl IGl0ZW0gcG9pbnRlciBsaXN0cyBhc3NvY2lhdGVkIHdpdGggZWFjaCBrZXkgY29udGludWUg dG8gYmUgc29ydGVkCmJlZm9yZSB0aGUgYWNjdW11bGF0ZWQgZW50cmllcyBhcmUgZW1pdHRl ZC4gVXNlIHNvcnRfdGVtcGxhdGUuaCBmb3IgdGhpcwpzb3J0aW5nIGluc3RlYWQgb2YgcXNv cnQoKS4gVGhlIGRpc3RpbmN0IGhhc2ggZW50cmllcyBhcmUgY29waWVkIGludG8gYW4KYXJy YXkgYW5kIHNvcnRlZCB1c2luZyB0aGUgZXhpc3RpbmcgR0lOIGtleSBjb21wYXJpc29uIGZ1 bmN0aW9uIHNvIHRoYXQKdGhlIG91dHB1dCBvcmRlciByZW1haW5zIHVuY2hhbmdlZC4KCmdp bkluc2VydEJBRW50cmllcygpIGdvdCBtdWNoIHNpbXBsZXIgYXMgd2VsbC4gVGhlIHByZXZp b3VzIGltcGxlbWVudGF0aW9uCmluc2VydGVkIGVudHJpZXMgaW4gYW4gb3JkZXIgaW50ZW5k ZWQgdG8gbWluaW1pemUgcmVkLWJsYWNrIHRyZWUgcmViYWxhbmNpbmcKZm9yIHNvcnRlZCBp bnB1dHMuIFdpdGggYSBoYXNoIHRhYmxlLCBpbnNlcnRpbmcgdGhlIGVudHJpZXMgaW4gdGhl aXIgb3JpZ2luYWwKb3JkZXIgaXMgcHJlZmVyYWJsZSBiZWNhdXNlIHJlcGVhdGVkIGtleXMg YXJlIG1vcmUgbGlrZWx5IHRvIGJlIGZvdW5kIGluIHRoZQpzYW1lIGhhc2gtdGFibGUgZW50 cnkuCgpVc2UgZGF0dW1Jc0VxdWFsKCkgYW5kIGRhdHVtX2ltYWdlX2hhc2goKSBmb3Igbm9y bWFsIEdJTiBrZXlzLiBUaGlzIGlzCmNvbnNpc3RlbnQgd2l0aCB0aGUgY3VycmVudCBHSU4g aW1wbGVtZW50YXRpb24sIHdoaWNoIGRvZXMgbm90IGNvcnJlY3RseQpzdXBwb3J0IG5vbi1k ZXRlcm1pbmlzdGljIGNvbGxhdGlvbnMgb3IgdHlwZXMgZm9yIHdoaWNoIGxvZ2ljYWxseSBl cXVhbAp2YWx1ZXMgYXJlIG5vdCBpbWFnZS1lcXVhbC4KCkJlY2F1c2UgcGFyYWxsZWwgR0lO IGluZGV4IGJ1aWxkcyBhbHNvIHVzZSBnaW5JbnNlcnRCQUVudHJpZXMoKSwgdGhpcwpjaGFu Z2UgaW1wcm92ZXMgdGhlIGFjY3VtdWxhdGlvbiBwaGFzZSBvZiBwYXJhbGxlbCBpbmRleCBi dWlsZHMgYXMgd2VsbC4KLS0tCiBzcmMvYmFja2VuZC9hY2Nlc3MvZ2luL2dpbmJ1bGsuYyB8 IDMzOSArKysrKysrKysrKysrKystLS0tLS0tLS0tLS0tLS0tCiBzcmMvaW5jbHVkZS9hY2Nl c3MvZ2luX3ByaXZhdGUuaCB8ICAyNCArLS0KIHNyYy90b29scy9wZ2luZGVudC90eXBlZGVm cy5saXN0IHwgICA0ICstCiAzIGZpbGVzIGNoYW5nZWQsIDE3NSBpbnNlcnRpb25zKCspLCAx OTIgZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2JhY2tlbmQvYWNjZXNzL2dpbi9n aW5idWxrLmMgYi9zcmMvYmFja2VuZC9hY2Nlc3MvZ2luL2dpbmJ1bGsuYwppbmRleCA4NTg2 NWIzOTEwNS4uNzdjMTJiYTkzMmIgMTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL2FjY2Vzcy9n aW4vZ2luYnVsay5jCisrKyBiL3NyYy9iYWNrZW5kL2FjY2Vzcy9naW4vZ2luYnVsay5jCkBA IC0xNywxMDcgKzE3LDExOCBAQAogI2luY2x1ZGUgPGxpbWl0cy5oPgogCiAjaW5jbHVkZSAi YWNjZXNzL2dpbl9wcml2YXRlLmgiCisjaW5jbHVkZSAiY29tbW9uL2hhc2hmbi5oIgogI2lu Y2x1ZGUgInV0aWxzL2RhdHVtLmgiCiAjaW5jbHVkZSAidXRpbHMvbWVtdXRpbHMuaCIKIAor I2RlZmluZSBERUZfTkVOVFJZCQkJMjA0OAkvKiBJbml0aWFsIGhhc2ggdGFibGUgc2l6ZSAq LworI2RlZmluZSBERUZfSVRFTVNfUEVSX0tFWQk4CQkvKiBJbml0aWFsIEl0ZW1Qb2ludGVy IGFycmF5IHNpemUgcGVyIGtleSAqLwogCi0jZGVmaW5lIERFRl9ORU5UUlkJMjA0OAkJLyog R2luRW50cnlBY2N1bXVsYXRvciBhbGxvY2F0aW9uIHF1YW50dW0gKi8KLSNkZWZpbmUgREVG X05QVFIJNQkJCS8qIEl0ZW1Qb2ludGVyIGluaXRpYWwgYWxsb2NhdGlvbiBxdWFudHVtICov Ci0KLQotLyogQ29tYmluZXIgZnVuY3Rpb24gZm9yIHJidHJlZS5jICovCi1zdGF0aWMgdm9p ZAotZ2luQ29tYmluZURhdGEoUkJUTm9kZSAqZXhpc3RpbmcsIGNvbnN0IFJCVE5vZGUgKm5l d2RhdGEsIHZvaWQgKmFyZykKK3R5cGVkZWYgc3RydWN0IEdpbkhhc2hLZXkKIHsKLQlHaW5F bnRyeUFjY3VtdWxhdG9yICplbyA9IChHaW5FbnRyeUFjY3VtdWxhdG9yICopIGV4aXN0aW5n OwotCWNvbnN0IEdpbkVudHJ5QWNjdW11bGF0b3IgKmVuID0gKGNvbnN0IEdpbkVudHJ5QWNj dW11bGF0b3IgKikgbmV3ZGF0YTsKLQlCdWlsZEFjY3VtdWxhdG9yICphY2N1bSA9IChCdWls ZEFjY3VtdWxhdG9yICopIGFyZzsKKwlPZmZzZXROdW1iZXIJYXR0bnVtOworCUdpbk51bGxD YXRlZ29yeQljYXRlZ29yeTsKKwlEYXR1bQkJCWtleTsKK30gR2luSGFzaEtleTsKIAotCS8q Ci0JICogTm90ZSB0aGlzIGNvZGUgYXNzdW1lcyB0aGF0IG5ld2RhdGEgY29udGFpbnMgb25s eSBvbmUgaXRlbXBvaW50ZXIuCi0JICovCi0JaWYgKGVvLT5jb3VudCA+PSBlby0+bWF4Y291 bnQpCi0JewotCQlpZiAoZW8tPm1heGNvdW50ID4gSU5UX01BWCkKLQkJCWVyZXBvcnQoRVJS T1IsCi0JCQkJCShlcnJjb2RlKEVSUkNPREVfUFJPR1JBTV9MSU1JVF9FWENFRURFRCksCi0J CQkJCSBlcnJtc2coInBvc3RpbmcgbGlzdCBpcyB0b28gbG9uZyIpLAotCQkJCQkgZXJyaGlu dCgiUmVkdWNlIFwibWFpbnRlbmFuY2Vfd29ya19tZW1cIi4iKSkpOwordHlwZWRlZiBzdHJ1 Y3QgR2luSGFzaEVudHJ5Cit7CisJR2luSGFzaEtleQkJaGFzaGtleTsKKwl1aW50MzIJCQlo YXNoOworCWNoYXIJCQlzdGF0dXM7CisJSXRlbVBvaW50ZXJEYXRhCSppdGVtczsKKwl1aW50 MzIJCQludW1JdGVtczsKKwl1aW50MzIJCQlhbGxvY2F0ZWRJdGVtczsKK30gR2luSGFzaEVu dHJ5OworCit0eXBlZGVmIHN0cnVjdCBHaW5Tb3J0RW50cnkKK3sKKwlHaW5IYXNoS2V5CQlo YXNoa2V5OworCUl0ZW1Qb2ludGVyRGF0YSAqaXRlbXM7CisJdWludDMyCQkJbnVtSXRlbXM7 Cit9IEdpblNvcnRFbnRyeTsKKworc3RhdGljIHVpbnQzMiBnaW5faGFzaF9rZXkoc3RydWN0 IGdpbmJ1aWxkX2hhc2ggKnRiLCBHaW5IYXNoS2V5ICprZXkpOworc3RhdGljIGJvb2wgZ2lu X2VxdWFsX2tleShzdHJ1Y3QgZ2luYnVpbGRfaGFzaCAqdGIsIEdpbkhhc2hLZXkgKmEsIEdp bkhhc2hLZXkgKmIpOworCisjZGVmaW5lIFNIX1BSRUZJWCBnaW5idWlsZAorI2RlZmluZSBT SF9FTEVNRU5UX1RZUEUgR2luSGFzaEVudHJ5CisjZGVmaW5lIFNIX0tFWV9UWVBFIEdpbkhh c2hLZXkKKyNkZWZpbmUgU0hfS0VZIGhhc2hrZXkKKyNkZWZpbmUgU0hfSEFTSF9LRVkodGIs IGtleSkgZ2luX2hhc2hfa2V5KHRiLCAma2V5KQorI2RlZmluZSBTSF9FUVVBTCh0YiwgYSwg YikgZ2luX2VxdWFsX2tleSh0YiwgJmEsICZiKQorI2RlZmluZSBTSF9TQ09QRSBzdGF0aWMg aW5saW5lCisjZGVmaW5lIFNIX1NUT1JFX0hBU0gKKyNkZWZpbmUgU0hfR0VUX0hBU0godGIs IGEpIChhKS0+aGFzaAorI2RlZmluZSBTSF9ERUZJTkUKKyNkZWZpbmUgU0hfREVDTEFSRQor I2luY2x1ZGUgImxpYi9zaW1wbGVoYXNoLmgiCisKK3N0YXRpYyB1aW50MzIKK2dpbl9oYXNo X2tleShzdHJ1Y3QgZ2luYnVpbGRfaGFzaCAqdGIsIEdpbkhhc2hLZXkgKmtleSkKK3sKKwlC dWlsZEFjY3VtdWxhdG9yICphY2N1bSA9IChCdWlsZEFjY3VtdWxhdG9yICopIHRiLT5wcml2 YXRlX2RhdGE7CisJdWludDMyCQloYXNoOwogCi0JCWFjY3VtLT5hbGxvY2F0ZWRNZW1vcnkg LT0gR2V0TWVtb3J5Q2h1bmtTcGFjZShlby0+bGlzdCk7Ci0JCWVvLT5tYXhjb3VudCAqPSAy OwotCQllby0+bGlzdCA9IChJdGVtUG9pbnRlckRhdGEgKikKLQkJCXJlcGFsbG9jX2h1Z2Uo ZW8tPmxpc3QsIHNpemVvZihJdGVtUG9pbnRlckRhdGEpICogZW8tPm1heGNvdW50KTsKLQkJ YWNjdW0tPmFsbG9jYXRlZE1lbW9yeSArPSBHZXRNZW1vcnlDaHVua1NwYWNlKGVvLT5saXN0 KTsKLQl9CisJaGFzaCA9IGhhc2hfY29tYmluZSgwLCBtdXJtdXJoYXNoMzIoKHVpbnQzMikg a2V5LT5hdHRudW0pKTsKKwloYXNoID0gaGFzaF9jb21iaW5lKGhhc2gsIG11cm11cmhhc2gz MigodWludDMyKSBrZXktPmNhdGVnb3J5KSk7CiAKLQkvKiBJZiBpdGVtIHBvaW50ZXJzIGFy ZSBub3Qgb3JkZXJlZCwgdGhleSB3aWxsIG5lZWQgdG8gYmUgc29ydGVkIGxhdGVyICovCi0J aWYgKGVvLT5zaG91bGRTb3J0ID09IGZhbHNlKQorCWlmIChrZXktPmNhdGVnb3J5ID09IEdJ Tl9DQVRfTk9STV9LRVkpCiAJewotCQlpbnQJCQlyZXM7Ci0KLQkJcmVzID0gZ2luQ29tcGFy ZUl0ZW1Qb2ludGVycyhlby0+bGlzdCArIGVvLT5jb3VudCAtIDEsIGVuLT5saXN0KTsKLQkJ QXNzZXJ0KHJlcyAhPSAwKTsKKwkJQ29tcGFjdEF0dHJpYnV0ZSAqYXR0OwogCi0JCWlmIChy ZXMgPiAwKQotCQkJZW8tPnNob3VsZFNvcnQgPSB0cnVlOworCQlhdHQgPSBUdXBsZURlc2ND b21wYWN0QXR0cihhY2N1bS0+Z2luc3RhdGUtPm9yaWdUdXBkZXNjLCBrZXktPmF0dG51bSAt IDEpOworCQloYXNoID0gaGFzaF9jb21iaW5lKGhhc2gsIGRhdHVtX2ltYWdlX2hhc2goa2V5 LT5rZXksIGF0dC0+YXR0Ynl2YWwsIGF0dC0+YXR0bGVuKSk7CiAJfQogCi0JZW8tPmxpc3Rb ZW8tPmNvdW50XSA9IGVuLT5saXN0WzBdOwotCWVvLT5jb3VudCsrOworCXJldHVybiBoYXNo OwogfQogCi0vKiBDb21wYXJhdG9yIGZ1bmN0aW9uIGZvciByYnRyZWUuYyAqLwotc3RhdGlj IGludAotY21wRW50cnlBY2N1bXVsYXRvcihjb25zdCBSQlROb2RlICphLCBjb25zdCBSQlRO b2RlICpiLCB2b2lkICphcmcpCitzdGF0aWMgYm9vbAorZ2luX2VxdWFsX2tleShzdHJ1Y3Qg Z2luYnVpbGRfaGFzaCAqdGIsIEdpbkhhc2hLZXkgKmEsIEdpbkhhc2hLZXkgKmIpCiB7Ci0J Y29uc3QgR2luRW50cnlBY2N1bXVsYXRvciAqZWEgPSAoY29uc3QgR2luRW50cnlBY2N1bXVs YXRvciAqKSBhOwotCWNvbnN0IEdpbkVudHJ5QWNjdW11bGF0b3IgKmViID0gKGNvbnN0IEdp bkVudHJ5QWNjdW11bGF0b3IgKikgYjsKLQlCdWlsZEFjY3VtdWxhdG9yICphY2N1bSA9IChC dWlsZEFjY3VtdWxhdG9yICopIGFyZzsKLQotCXJldHVybiBnaW5Db21wYXJlQXR0RW50cmll cyhhY2N1bS0+Z2luc3RhdGUsCi0JCQkJCQkJCWVhLT5hdHRudW0sIGVhLT5rZXksIGVhLT5j YXRlZ29yeSwKLQkJCQkJCQkJZWItPmF0dG51bSwgZWItPmtleSwgZWItPmNhdGVnb3J5KTsK LX0KKwlCdWlsZEFjY3VtdWxhdG9yICphY2N1bSA9IChCdWlsZEFjY3VtdWxhdG9yICopIHRi LT5wcml2YXRlX2RhdGE7CisJQ29tcGFjdEF0dHJpYnV0ZSAqYXR0OwogCi0vKiBBbGxvY2F0 b3IgZnVuY3Rpb24gZm9yIHJidHJlZS5jICovCi1zdGF0aWMgUkJUTm9kZSAqCi1naW5BbGxv Y0VudHJ5QWNjdW11bGF0b3Iodm9pZCAqYXJnKQotewotCUJ1aWxkQWNjdW11bGF0b3IgKmFj Y3VtID0gKEJ1aWxkQWNjdW11bGF0b3IgKikgYXJnOwotCUdpbkVudHJ5QWNjdW11bGF0b3Ig KmVhOworCWlmIChhLT5hdHRudW0gIT0gYi0+YXR0bnVtKQorCQlyZXR1cm4gZmFsc2U7CisJ aWYgKGEtPmNhdGVnb3J5ICE9IGItPmNhdGVnb3J5KQorCQlyZXR1cm4gZmFsc2U7CisJaWYg KGEtPmNhdGVnb3J5ICE9IEdJTl9DQVRfTk9STV9LRVkpCisJCXJldHVybiB0cnVlOwogCiAJ LyoKLQkgKiBBbGxvY2F0ZSBtZW1vcnkgYnkgcmF0aGVyIGJpZyBjaHVua3MgdG8gZGVjcmVh c2Ugb3ZlcmhlYWQuICBXZSBoYXZlIG5vCi0JICogbmVlZCB0byByZWNsYWltIFJCVE5vZGVz IGluZGl2aWR1YWxseSwgc28gdGhpcyBjb3N0cyBub3RoaW5nLgorCSAqIENvbXBhcmUgdGhl IGFjdHVhbCBrZXkgdmFsdWVzIHVzaW5nIGltYWdlIGVxdWFsaXR5LgorCSAqIFRoaXMgaXMg Y29ycmVjdCBiZWNhdXNlIHdlIGRvbid0IHdhbnQgdG8gZGVkdXBsaWNhdGUgYXQgdGhpcyBw b2ludC4KIAkgKi8KLQlpZiAoYWNjdW0tPmVudHJ5YWxsb2NhdG9yID09IE5VTEwgfHwgYWNj dW0tPmVhc191c2VkID49IERFRl9ORU5UUlkpCi0JewotCQlhY2N1bS0+ZW50cnlhbGxvY2F0 b3IgPSBwYWxsb2NfYXJyYXkoR2luRW50cnlBY2N1bXVsYXRvciwgREVGX05FTlRSWSk7Ci0J CWFjY3VtLT5hbGxvY2F0ZWRNZW1vcnkgKz0gR2V0TWVtb3J5Q2h1bmtTcGFjZShhY2N1bS0+ ZW50cnlhbGxvY2F0b3IpOwotCQlhY2N1bS0+ZWFzX3VzZWQgPSAwOwotCX0KLQotCS8qIEFs bG9jYXRlIG5ldyBSQlROb2RlIGZyb20gY3VycmVudCBjaHVuayAqLwotCWVhID0gYWNjdW0t PmVudHJ5YWxsb2NhdG9yICsgYWNjdW0tPmVhc191c2VkOwotCWFjY3VtLT5lYXNfdXNlZCsr OwotCi0JcmV0dXJuIChSQlROb2RlICopIGVhOworCWF0dCA9IFR1cGxlRGVzY0NvbXBhY3RB dHRyKGFjY3VtLT5naW5zdGF0ZS0+b3JpZ1R1cGRlc2MsIGEtPmF0dG51bSAtIDEpOworCXJl dHVybiBkYXR1bUlzRXF1YWwoYS0+a2V5LCBiLT5rZXksIGF0dC0+YXR0Ynl2YWwsIGF0dC0+ YXR0bGVuKTsKIH0KIAorI2RlZmluZSBTVF9TT1JUIHNvcnRfaXRlbXBvaW50ZXJzCisjZGVm aW5lIFNUX0VMRU1FTlRfVFlQRSBJdGVtUG9pbnRlckRhdGEKKyNkZWZpbmUgU1RfQ09NUEFS RShhLCBiKSBnaW5Db21wYXJlSXRlbVBvaW50ZXJzKGEsIGIpCisjZGVmaW5lIFNUX1NDT1BF IHN0YXRpYworI2RlZmluZSBTVF9ERUZJTkUKKyNpbmNsdWRlICJsaWIvc29ydF90ZW1wbGF0 ZS5oIgorCisjZGVmaW5lIFNUX1NPUlQgc29ydF9rZXlzCisjZGVmaW5lIFNUX0VMRU1FTlRf VFlQRSBHaW5Tb3J0RW50cnkKKyNkZWZpbmUgU1RfQ09NUEFSRV9BUkdfVFlQRSBHaW5TdGF0 ZQorI2RlZmluZSBTVF9DT01QQVJFKGEsIGIsIHN0YXRlKSBnaW5Db21wYXJlQXR0RW50cmll cyhzdGF0ZSwgYS0+aGFzaGtleS5hdHRudW0sIGEtPmhhc2hrZXkua2V5LCBhLT5oYXNoa2V5 LmNhdGVnb3J5LCBiLT5oYXNoa2V5LmF0dG51bSwgYi0+aGFzaGtleS5rZXksIGItPmhhc2hr ZXkuY2F0ZWdvcnkpCisjZGVmaW5lIFNUX1NDT1BFIHN0YXRpYworI2RlZmluZSBTVF9ERUZJ TkUKKyNpbmNsdWRlICJsaWIvc29ydF90ZW1wbGF0ZS5oIgorCiB2b2lkCiBnaW5Jbml0QkEo QnVpbGRBY2N1bXVsYXRvciAqYWNjdW0pCiB7CiAJLyogYWNjdW0tPmdpbnN0YXRlIGlzIGlu dGVudGlvbmFsbHkgbm90IHNldCBoZXJlICovCi0JYWNjdW0tPmFsbG9jYXRlZE1lbW9yeSA9 IDA7Ci0JYWNjdW0tPmVudHJ5YWxsb2NhdG9yID0gTlVMTDsKLQlhY2N1bS0+ZWFzX3VzZWQg PSAwOwotCWFjY3VtLT50cmVlID0gcmJ0X2NyZWF0ZShzaXplb2YoR2luRW50cnlBY2N1bXVs YXRvciksCi0JCQkJCQkJIGNtcEVudHJ5QWNjdW11bGF0b3IsCi0JCQkJCQkJIGdpbkNvbWJp bmVEYXRhLAotCQkJCQkJCSBnaW5BbGxvY0VudHJ5QWNjdW11bGF0b3IsCi0JCQkJCQkJIE5V TEwsCS8qIG5vIGZyZWVmdW5jIG5lZWRlZCAqLwotCQkJCQkJCSBhY2N1bSk7CisJYWNjdW0t Pmhhc2ggPSBnaW5idWlsZF9jcmVhdGUoQ3VycmVudE1lbW9yeUNvbnRleHQsIERFRl9ORU5U UlksIGFjY3VtKTsKKwlhY2N1bS0+YWxsb2NhdGVkTWVtb3J5ID0gYWNjdW0tPmhhc2gtPnNp emUgKiBzaXplb2YoR2luSGFzaEVudHJ5KTsKKwlhY2N1bS0+c29ydGVkX2VudHJpZXMgPSBO VUxMOworCWFjY3VtLT5udW1fZW50cmllcyA9IDA7CisJYWNjdW0tPmN1cnJlbnRfcG9zID0g MDsKIH0KIAogLyoKQEAgLTE0MiwxMjQgKzE1MywxMTMgQEAgZ2V0RGF0dW1Db3B5KEJ1aWxk QWNjdW11bGF0b3IgKmFjY3VtLCBPZmZzZXROdW1iZXIgYXR0bnVtLCBEYXR1bSB2YWx1ZSkK IH0KIAogLyoKLSAqIEZpbmQvc3RvcmUgb25lIGVudHJ5IGZyb20gaW5kZXhlZCB2YWx1ZS4K KyAqIEluc2VydCBvbmUgZW50cnkgaW50byB0aGUgaGFzaCBtYXAuCisgKiBJZiB0aGUga2V5 IGFscmVhZHkgZXhpc3RzLCBhcHBlbmQgdG8gaXRzIEl0ZW1Qb2ludGVyIGFycmF5LgorICog T3RoZXJ3aXNlLCBjcmVhdGUgYSBuZXcgaGFzaCBlbnRyeSB3aXRoIGEgbmV3IEl0ZW1Qb2lu dGVyIGFycmF5LgogICovCiBzdGF0aWMgdm9pZAogZ2luSW5zZXJ0QkFFbnRyeShCdWlsZEFj Y3VtdWxhdG9yICphY2N1bSwKIAkJCQkgSXRlbVBvaW50ZXIgaGVhcHB0ciwgT2Zmc2V0TnVt YmVyIGF0dG51bSwKIAkJCQkgRGF0dW0ga2V5LCBHaW5OdWxsQ2F0ZWdvcnkgY2F0ZWdvcnkp CiB7Ci0JR2luRW50cnlBY2N1bXVsYXRvciBlYXRtcDsKLQlHaW5FbnRyeUFjY3VtdWxhdG9y ICplYTsKLQlib29sCQlpc05ldzsKKwlHaW5IYXNoS2V5CWhhc2hrZXk7CisJR2luSGFzaEVu dHJ5ICplbnRyeTsKKwlib29sCQlmb3VuZDsKKwl1aW50NjQJCW9sZHNpemU7CiAKLQkvKgot CSAqIEZvciB0aGUgbW9tZW50LCBmaWxsIG9ubHkgdGhlIGZpZWxkcyBvZiBlYXRtcCB0aGF0 IHdpbGwgYmUgbG9va2VkIGF0IGJ5Ci0JICogY21wRW50cnlBY2N1bXVsYXRvciBvciBnaW5D b21iaW5lRGF0YS4KLQkgKi8KLQllYXRtcC5hdHRudW0gPSBhdHRudW07Ci0JZWF0bXAua2V5 ID0ga2V5OwotCWVhdG1wLmNhdGVnb3J5ID0gY2F0ZWdvcnk7Ci0JLyogdGVtcG9yYXJpbHkg c2V0IHVwIHNpbmdsZS1lbnRyeSBpdGVtcG9pbnRlciBsaXN0ICovCi0JZWF0bXAubGlzdCA9 IGhlYXBwdHI7CisJaGFzaGtleS5hdHRudW0gPSBhdHRudW07CisJaGFzaGtleS5jYXRlZ29y eSA9IGNhdGVnb3J5OworCWhhc2hrZXkua2V5ID0ga2V5OwogCi0JZWEgPSAoR2luRW50cnlB Y2N1bXVsYXRvciAqKSByYnRfaW5zZXJ0KGFjY3VtLT50cmVlLCAoUkJUTm9kZSAqKSAmZWF0 bXAsCi0JCQkJCQkJCQkJCSZpc05ldyk7CisJb2xkc2l6ZSA9IGFjY3VtLT5oYXNoLT5zaXpl OworCWVudHJ5ID0gZ2luYnVpbGRfaW5zZXJ0KGFjY3VtLT5oYXNoLCBoYXNoa2V5LCAmZm91 bmQpOwogCi0JaWYgKGlzTmV3KQorCWlmICghZm91bmQpCiAJewogCQkvKgotCQkgKiBGaW5p c2ggaW5pdGlhbGl6aW5nIG5ldyB0cmVlIGVudHJ5LCBpbmNsdWRpbmcgbWFraW5nIHBlcm1h bmVudAotCQkgKiBjb3BpZXMgb2YgdGhlIGRhdHVtIChpZiBpdCdzIG5vdCBudWxsKSBhbmQg aXRlbXBvaW50ZXIuCisJCSAqIEZpbmlzaCBpbml0aWFsaXppbmcgbmV3IGhhc2htYXAgZW50 cnkgaW5jbHVkaW5nIG1ha2luZyBhIHBlcm1hbmVudAorCQkgKiBjb3B5IG9mIHRoZSBrZXku CiAJCSAqLwogCQlpZiAoY2F0ZWdvcnkgPT0gR0lOX0NBVF9OT1JNX0tFWSkKLQkJCWVhLT5r ZXkgPSBnZXREYXR1bUNvcHkoYWNjdW0sIGF0dG51bSwga2V5KTsKLQkJZWEtPm1heGNvdW50 ID0gREVGX05QVFI7Ci0JCWVhLT5jb3VudCA9IDE7Ci0JCWVhLT5zaG91bGRTb3J0ID0gZmFs c2U7Ci0JCWVhLT5saXN0ID0gcGFsbG9jX2FycmF5KEl0ZW1Qb2ludGVyRGF0YSwgREVGX05Q VFIpOwotCQllYS0+bGlzdFswXSA9ICpoZWFwcHRyOwotCQlhY2N1bS0+YWxsb2NhdGVkTWVt b3J5ICs9IEdldE1lbW9yeUNodW5rU3BhY2UoZWEtPmxpc3QpOworCQkJZW50cnktPmhhc2hr ZXkua2V5ID0gZ2V0RGF0dW1Db3B5KGFjY3VtLCBhdHRudW0sIGtleSk7CisKKwkJZW50cnkt Pml0ZW1zID0gcGFsbG9jX2FycmF5KEl0ZW1Qb2ludGVyRGF0YSwgREVGX0lURU1TX1BFUl9L RVkpOworCQllbnRyeS0+bnVtSXRlbXMgPSAwOworCQllbnRyeS0+YWxsb2NhdGVkSXRlbXMg PSBERUZfSVRFTVNfUEVSX0tFWTsKKwkJYWNjdW0tPmFsbG9jYXRlZE1lbW9yeSArPSAoYWNj dW0tPmhhc2gtPnNpemUgLSBvbGRzaXplKSAqIHNpemVvZihHaW5IYXNoRW50cnkpOworCQlh Y2N1bS0+YWxsb2NhdGVkTWVtb3J5ICs9IEdldE1lbW9yeUNodW5rU3BhY2UoZW50cnktPml0 ZW1zKTsKIAl9Ci0JZWxzZQorCisJaWYgKGVudHJ5LT5udW1JdGVtcyA+PSBlbnRyeS0+YWxs b2NhdGVkSXRlbXMpCiAJewotCQkvKgotCQkgKiBnaW5Db21iaW5lRGF0YSBkaWQgZXZlcnl0 aGluZyBuZWVkZWQuCi0JCSAqLworCQl1aW50MzIJCW5ld19hbGxvY2F0ZWQ7CisKKwkJaWYg KGVudHJ5LT5hbGxvY2F0ZWRJdGVtcyA+IFVJTlQzMl9NQVggLyAyKQorCQkJZXJlcG9ydChF UlJPUiwKKwkJCQkJKGVycmNvZGUoRVJSQ09ERV9QUk9HUkFNX0xJTUlUX0VYQ0VFREVEKSwK KwkJCQkJIGVycm1zZygidG9vIG1hbnkgR0lOIGl0ZW0gcG9pbnRlcnMgZm9yIGEgc2luZ2xl IGtleSIpLAorCQkJCQkgZXJyaGludCgiUmVkdWNlIFwibWFpbnRlbmFuY2Vfd29ya19tZW1c Ii4iKSkpOworCisJCWFjY3VtLT5hbGxvY2F0ZWRNZW1vcnkgLT0gR2V0TWVtb3J5Q2h1bmtT cGFjZShlbnRyeS0+aXRlbXMpOworCQluZXdfYWxsb2NhdGVkID0gZW50cnktPmFsbG9jYXRl ZEl0ZW1zICogMjsKKwkJZW50cnktPml0ZW1zID0gcmVwYWxsb2NfaHVnZShlbnRyeS0+aXRl bXMsIG11bF9zaXplKHNpemVvZihJdGVtUG9pbnRlckRhdGEpLCBuZXdfYWxsb2NhdGVkKSk7 CisJCWVudHJ5LT5hbGxvY2F0ZWRJdGVtcyA9IG5ld19hbGxvY2F0ZWQ7CisJCWFjY3VtLT5h bGxvY2F0ZWRNZW1vcnkgKz0gR2V0TWVtb3J5Q2h1bmtTcGFjZShlbnRyeS0+aXRlbXMpOwog CX0KKworCWVudHJ5LT5pdGVtc1tlbnRyeS0+bnVtSXRlbXMrK10gPSAqaGVhcHB0cjsKIH0K IAotLyoKLSAqIEluc2VydCB0aGUgZW50cmllcyBmb3Igb25lIGhlYXAgcG9pbnRlci4KLSAq Ci0gKiBTaW5jZSB0aGUgZW50cmllcyBhcmUgYmVpbmcgaW5zZXJ0ZWQgaW50byBhIGJhbGFu Y2VkIGJpbmFyeSB0cmVlLCB5b3UKLSAqIG1pZ2h0IHRoaW5rIHRoYXQgdGhlIG9yZGVyIG9m IGluc2VydGlvbiB3b3VsZG4ndCBiZSBjcml0aWNhbCwgYnV0IGl0IHR1cm5zCi0gKiBvdXQg dGhhdCBpbnNlcnRpbmcgdGhlIGVudHJpZXMgaW4gc29ydGVkIG9yZGVyIHJlc3VsdHMgaW4g YSBsb3Qgb2YKLSAqIHJlYmFsYW5jaW5nIG9wZXJhdGlvbnMgYW5kIGlzIHNsb3cuICBUbyBw cmV2ZW50IHRoaXMsIHdlIGF0dGVtcHQgdG8gaW5zZXJ0Ci0gKiB0aGUgbm9kZXMgaW4gYW4g b3JkZXIgdGhhdCB3aWxsIHByb2R1Y2UgYSBuZWFybHktYmFsYW5jZWQgdHJlZSBpZiB0aGUg aW5wdXQKLSAqIGlzIGluIGZhY3Qgc29ydGVkLgotICoKLSAqIFdlIGRvIHRoaXMgYXMgZm9s bG93cy4gIEZpcnN0LCB3ZSBpbWFnaW5lIHRoYXQgd2UgaGF2ZSBhbiBhcnJheSB3aG9zZSBz aXplCi0gKiBpcyB0aGUgc21hbGxlc3QgcG93ZXIgb2YgdHdvIGdyZWF0ZXIgdGhhbiBvciBl cXVhbCB0byB0aGUgYWN0dWFsIGFycmF5Ci0gKiBzaXplLiAgU2Vjb25kLCB3ZSBpbnNlcnQg dGhlIG1pZGRsZSBlbnRyeSBvZiBvdXIgdmlydHVhbCBhcnJheSBpbnRvIHRoZQotICogdHJl ZTsgdGhlbiwgd2UgaW5zZXJ0IHRoZSBtaWRkbGVzIG9mIGVhY2ggaGFsZiBvZiBvdXIgdmly dHVhbCBhcnJheSwgdGhlbgotICogbWlkZGxlcyBvZiBxdWFydGVycywgZXRjLgotICovCiB2 b2lkCiBnaW5JbnNlcnRCQUVudHJpZXMoQnVpbGRBY2N1bXVsYXRvciAqYWNjdW0sCiAJCQkJ ICAgSXRlbVBvaW50ZXIgaGVhcHB0ciwgT2Zmc2V0TnVtYmVyIGF0dG51bSwKIAkJCQkgICBE YXR1bSAqZW50cmllcywgR2luTnVsbENhdGVnb3J5ICpjYXRlZ29yaWVzLAogCQkJCSAgIGlu dDMyIG5lbnRyaWVzKQogewotCXVpbnQzMgkJc3RlcCA9IG5lbnRyaWVzOwotCiAJaWYgKG5l bnRyaWVzIDw9IDApCiAJCXJldHVybjsKIAogCUFzc2VydChJdGVtUG9pbnRlcklzVmFsaWQo aGVhcHB0cikgJiYgYXR0bnVtID49IEZpcnN0T2Zmc2V0TnVtYmVyKTsKIAotCS8qCi0JICog c3RlcCB3aWxsIGNvbnRhaW4gbGFyZ2VzdCBwb3dlciBvZiAyIGFuZCA8PSBuZW50cmllcwot CSAqLwotCXN0ZXAgfD0gKHN0ZXAgPj4gMSk7Ci0Jc3RlcCB8PSAoc3RlcCA+PiAyKTsKLQlz dGVwIHw9IChzdGVwID4+IDQpOwotCXN0ZXAgfD0gKHN0ZXAgPj4gOCk7Ci0Jc3RlcCB8PSAo c3RlcCA+PiAxNik7Ci0Jc3RlcCA+Pj0gMTsKLQlzdGVwKys7Ci0KLQl3aGlsZSAoc3RlcCA+ IDApCi0JewotCQlpbnQJCQlpOwotCi0JCWZvciAoaSA9IHN0ZXAgLSAxOyBpIDwgbmVudHJp ZXMgJiYgaSA+PSAwOyBpICs9IHN0ZXAgPDwgMSAvKiAqMiAqLyApCi0JCQlnaW5JbnNlcnRC QUVudHJ5KGFjY3VtLCBoZWFwcHRyLCBhdHRudW0sCi0JCQkJCQkJIGVudHJpZXNbaV0sIGNh dGVnb3JpZXNbaV0pOwotCi0JCXN0ZXAgPj49IDE7CQkJCS8qIC8yICovCi0JfQorCWZvciAo aW50IGkgPSAwOyBpIDwgbmVudHJpZXM7IGkrKykKKwkJZ2luSW5zZXJ0QkFFbnRyeShhY2N1 bSwgaGVhcHB0ciwgYXR0bnVtLCBlbnRyaWVzW2ldLCBjYXRlZ29yaWVzW2ldKTsKIH0KIAot c3RhdGljIGludAotcXNvcnRDb21wYXJlSXRlbVBvaW50ZXJzKGNvbnN0IHZvaWQgKmEsIGNv bnN0IHZvaWQgKmIpCi17Ci0JaW50CQkJcmVzID0gZ2luQ29tcGFyZUl0ZW1Qb2ludGVycygo Y29uc3QgSXRlbVBvaW50ZXJEYXRhICopIGEsIChjb25zdCBJdGVtUG9pbnRlckRhdGEgKikg Yik7Ci0KLQkvKiBBc3NlcnQgdGhhdCB0aGVyZSBhcmUgbm8gZXF1YWwgaXRlbSBwb2ludGVy cyBiZWluZyBzb3J0ZWQgKi8KLQlBc3NlcnQocmVzICE9IDApOwotCXJldHVybiByZXM7Ci19 Ci0KLS8qIFByZXBhcmUgdG8gcmVhZCBvdXQgdGhlIHJidHJlZSBjb250ZW50cyB1c2luZyBn aW5HZXRCQUVudHJ5ICovCisvKiBQcmVwYXJlIHRvIHJlYWQgb3V0IHRoZSBoYXNoIHRhYmxl IGNvbnRlbnRzIHVzaW5nIGdpbkdldEJBRW50cnkgKi8KIHZvaWQKIGdpbkJlZ2luQkFTY2Fu KEJ1aWxkQWNjdW11bGF0b3IgKmFjY3VtKQogewotCXJidF9iZWdpbl9pdGVyYXRlKGFjY3Vt LT50cmVlLCBMZWZ0UmlnaHRXYWxrLCAmYWNjdW0tPnRyZWVfd2Fsayk7CisJZ2luYnVpbGRf aXRlcmF0b3IgaXRlcjsKKwlHaW5IYXNoRW50cnkgKmVudHJ5OworCXVpbnQzMgkJaSA9IDA7 CisKKwlhY2N1bS0+bnVtX2VudHJpZXMgPSBhY2N1bS0+aGFzaC0+bWVtYmVyczsKKwlhY2N1 bS0+Y3VycmVudF9wb3MgPSAwOworCisJaWYgKGFjY3VtLT5udW1fZW50cmllcyA9PSAwKQor CQlyZXR1cm47CisKKwlhY2N1bS0+c29ydGVkX2VudHJpZXMgPSBwYWxsb2NfYXJyYXkoR2lu U29ydEVudHJ5LCBhY2N1bS0+bnVtX2VudHJpZXMpOworCWdpbmJ1aWxkX3N0YXJ0X2l0ZXJh dGUoYWNjdW0tPmhhc2gsICZpdGVyKTsKKworCXdoaWxlICgoZW50cnkgPSBnaW5idWlsZF9p dGVyYXRlKGFjY3VtLT5oYXNoLCAmaXRlcikpICE9IE5VTEwpCisJeworCQlHaW5Tb3J0RW50 cnkgKnNlID0gJmFjY3VtLT5zb3J0ZWRfZW50cmllc1tpXTsKKwkJc29ydF9pdGVtcG9pbnRl cnMoZW50cnktPml0ZW1zLCBlbnRyeS0+bnVtSXRlbXMpOworCisJCXNlLT5oYXNoa2V5ID0g ZW50cnktPmhhc2hrZXk7CisJCXNlLT5pdGVtcyA9IGVudHJ5LT5pdGVtczsKKwkJc2UtPm51 bUl0ZW1zID0gZW50cnktPm51bUl0ZW1zOworCQlpKys7CisJfQorCisJQXNzZXJ0KGkgPT0g YWNjdW0tPm51bV9lbnRyaWVzKTsKKwlzb3J0X2tleXMoYWNjdW0tPnNvcnRlZF9lbnRyaWVz LCBhY2N1bS0+bnVtX2VudHJpZXMsIGFjY3VtLT5naW5zdGF0ZSk7CisJYWNjdW0tPmN1cnJl bnRfcG9zID0gMDsKIH0KIAogLyoKLSAqIEdldCB0aGUgbmV4dCBlbnRyeSBpbiBzZXF1ZW5j ZSBmcm9tIHRoZSBCdWlsZEFjY3VtdWxhdG9yJ3MgcmJ0cmVlLgorICogR2V0IHRoZSBuZXh0 IGVudHJ5IGluIHNlcXVlbmNlIGZyb20gdGhlIEJ1aWxkQWNjdW11bGF0b3IncyBzb3J0ZWQg aGFzaCBlbnRyaWVzLgogICogVGhpcyBjb25zaXN0cyBvZiBhIHNpbmdsZSBrZXkgZGF0dW0g YW5kIGEgbGlzdCAoYXJyYXkpIG9mIG9uZSBvciBtb3JlCiAgKiBoZWFwIFRJRHMgaW4gd2hp Y2ggdGhhdCBrZXkgaXMgZm91bmQuICBUaGUgbGlzdCBpcyBndWFyYW50ZWVkIHNvcnRlZC4K ICAqLwpAQCAtMjY4LDI1ICsyNjgsMTggQEAgZ2luR2V0QkFFbnRyeShCdWlsZEFjY3VtdWxh dG9yICphY2N1bSwKIAkJCSAgT2Zmc2V0TnVtYmVyICphdHRudW0sIERhdHVtICprZXksIEdp bk51bGxDYXRlZ29yeSAqY2F0ZWdvcnksCiAJCQkgIHVpbnQzMiAqbikKIHsKLQlHaW5FbnRy eUFjY3VtdWxhdG9yICplbnRyeTsKLQlJdGVtUG9pbnRlckRhdGEgKmxpc3Q7Ci0KLQllbnRy eSA9IChHaW5FbnRyeUFjY3VtdWxhdG9yICopIHJidF9pdGVyYXRlKCZhY2N1bS0+dHJlZV93 YWxrKTsKKwlHaW5Tb3J0RW50cnkgKmVudHJ5OwogCi0JaWYgKGVudHJ5ID09IE5VTEwpCisJ aWYgKGFjY3VtLT5jdXJyZW50X3BvcyA+PSBhY2N1bS0+bnVtX2VudHJpZXMpCiAJCXJldHVy biBOVUxMOwkJCS8qIG5vIG1vcmUgZW50cmllcyAqLwogCi0JKmF0dG51bSA9IGVudHJ5LT5h dHRudW07Ci0JKmtleSA9IGVudHJ5LT5rZXk7Ci0JKmNhdGVnb3J5ID0gZW50cnktPmNhdGVn b3J5OwotCWxpc3QgPSBlbnRyeS0+bGlzdDsKLQkqbiA9IGVudHJ5LT5jb3VudDsKLQotCUFz c2VydChsaXN0ICE9IE5VTEwgJiYgZW50cnktPmNvdW50ID4gMCk7CisJZW50cnkgPSAmYWNj dW0tPnNvcnRlZF9lbnRyaWVzW2FjY3VtLT5jdXJyZW50X3Bvc107CisJYWNjdW0tPmN1cnJl bnRfcG9zKys7CiAKLQlpZiAoZW50cnktPnNob3VsZFNvcnQgJiYgZW50cnktPmNvdW50ID4g MSkKLQkJcXNvcnQobGlzdCwgZW50cnktPmNvdW50LCBzaXplb2YoSXRlbVBvaW50ZXJEYXRh KSwKLQkJCSAgcXNvcnRDb21wYXJlSXRlbVBvaW50ZXJzKTsKKwkqYXR0bnVtID0gZW50cnkt Pmhhc2hrZXkuYXR0bnVtOworCSprZXkgPSBlbnRyeS0+aGFzaGtleS5rZXk7CisJKmNhdGVn b3J5ID0gZW50cnktPmhhc2hrZXkuY2F0ZWdvcnk7CisJKm4gPSBlbnRyeS0+bnVtSXRlbXM7 CiAKLQlyZXR1cm4gbGlzdDsKKwlyZXR1cm4gZW50cnktPml0ZW1zOwogfQpkaWZmIC0tZ2l0 IGEvc3JjL2luY2x1ZGUvYWNjZXNzL2dpbl9wcml2YXRlLmggYi9zcmMvaW5jbHVkZS9hY2Nl c3MvZ2luX3ByaXZhdGUuaAppbmRleCAzYzVmZDZiYTgxNy4uZGY2YjQ0Nzk2YzYgMTAwNjQ0 Ci0tLSBhL3NyYy9pbmNsdWRlL2FjY2Vzcy9naW5fcHJpdmF0ZS5oCisrKyBiL3NyYy9pbmNs dWRlL2FjY2Vzcy9naW5fcHJpdmF0ZS5oCkBAIC0xOCw3ICsxOCw2IEBACiAjaW5jbHVkZSAi Y29tbW9uL2ludC5oIgogI2luY2x1ZGUgImNhdGFsb2cvcGdfYW1fZC5oIgogI2luY2x1ZGUg ImZtZ3IuaCIKLSNpbmNsdWRlICJsaWIvcmJ0cmVlLmgiCiAjaW5jbHVkZSAibm9kZXMvdGlk Yml0bWFwLmgiCiAjaW5jbHVkZSAic3RvcmFnZS9idWZtZ3IuaCIKIApAQCAtNDIwLDI2ICs0 MTksMTUgQEAgZXh0ZXJuIHZvaWQgZ2luYWRqdXN0bWVtYmVycyhPaWQgb3BmYW1pbHlvaWQs CiAJCQkJCQkJIExpc3QgKmZ1bmN0aW9ucyk7CiAKIC8qIGdpbmJ1bGsuYyAqLwotdHlwZWRl ZiBzdHJ1Y3QgR2luRW50cnlBY2N1bXVsYXRvcgotewotCVJCVE5vZGUJCXJidG5vZGU7Ci0J RGF0dW0JCWtleTsKLQlHaW5OdWxsQ2F0ZWdvcnkgY2F0ZWdvcnk7Ci0JT2Zmc2V0TnVtYmVy IGF0dG51bTsKLQlib29sCQlzaG91bGRTb3J0OwotCUl0ZW1Qb2ludGVyRGF0YSAqbGlzdDsK LQl1aW50MzIJCW1heGNvdW50OwkJLyogYWxsb2NhdGVkIHNpemUgb2YgbGlzdFtdICovCi0J dWludDMyCQljb3VudDsJCQkvKiBjdXJyZW50IG51bWJlciBvZiBsaXN0W10gZW50cmllcyAq LwotfSBHaW5FbnRyeUFjY3VtdWxhdG9yOwogCiB0eXBlZGVmIHN0cnVjdAogewotCUdpblN0 YXRlICAgKmdpbnN0YXRlOwotCVNpemUJCWFsbG9jYXRlZE1lbW9yeTsKLQlHaW5FbnRyeUFj Y3VtdWxhdG9yICplbnRyeWFsbG9jYXRvcjsKLQl1aW50MzIJCWVhc191c2VkOwotCVJCVHJl ZQkgICAqdHJlZTsKLQlSQlRyZWVJdGVyYXRvciB0cmVlX3dhbGs7CisJR2luU3RhdGUgKgkJ CQlnaW5zdGF0ZTsKKwlTaXplCQkJCQlhbGxvY2F0ZWRNZW1vcnk7CisJc3RydWN0IGdpbmJ1 aWxkX2hhc2ggKgloYXNoOworCXN0cnVjdCBHaW5Tb3J0RW50cnkgKglzb3J0ZWRfZW50cmll czsKKwl1aW50MzIJCQkJCW51bV9lbnRyaWVzOworCXVpbnQzMgkJCQkJY3VycmVudF9wb3M7 CiB9IEJ1aWxkQWNjdW11bGF0b3I7CiAKIGV4dGVybiB2b2lkIGdpbkluaXRCQShCdWlsZEFj Y3VtdWxhdG9yICphY2N1bSk7CmRpZmYgLS1naXQgYS9zcmMvdG9vbHMvcGdpbmRlbnQvdHlw ZWRlZnMubGlzdCBiL3NyYy90b29scy9wZ2luZGVudC90eXBlZGVmcy5saXN0CmluZGV4IGRl MjFjZWE2NWY5Li5lMjQzYTIwNWI0NSAxMDA2NDQKLS0tIGEvc3JjL3Rvb2xzL3BnaW5kZW50 L3R5cGVkZWZzLmxpc3QKKysrIGIvc3JjL3Rvb2xzL3BnaW5kZW50L3R5cGVkZWZzLmxpc3QK QEAgLTExMDcsNyArMTEwNyw4IEBAIEdpbkJ1aWxkU2hhcmVkCiBHaW5CdWlsZFN0YXRlCiBH aW5DaGtWYWwKIEdpbkVudHJpZXMKLUdpbkVudHJ5QWNjdW11bGF0b3IKK0dpbkhhc2hFbnRy eQorR2luSGFzaEtleQogR2luSW5kZXhTdGF0CiBHaW5MZWFkZXIKIEdpbk1ldGFQYWdlRGF0 YQpAQCAtMTEyNyw2ICsxMTI4LDcgQEAgR2luU2NhbktleURhdGEKIEdpblNjYW5PcGFxdWUK IEdpblNjYW5PcGFxdWVEYXRhCiBHaW5TZWdtZW50SW5mbworR2luU29ydEVudHJ5CiBHaW5T dGF0ZQogR2luU3RhdHNEYXRhCiBHaW5UZXJuYXJ5VmFsdWUKLS0gCjIuNTMuMAoK --------------i0uBgFL0BR4Os7d0xe0pjhHC Content-Type: text/x-patch; charset=UTF-8; name="v11-0002-Use-radix-sort-to-extract-trigrams.patch" Content-Disposition: attachment; filename="v11-0002-Use-radix-sort-to-extract-trigrams.patch" Content-Transfer-Encoding: base64 RnJvbSA0YTZlMDg3NWFlOWI3MTUzMGJjOGE0M2NlNWMyNWVmOTZkMDhiODU3IE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBEYXZpZCBHZWllciA8Z2VpZGF2LnBnQGdtYWlsLmNv bT4KRGF0ZTogVHVlLCAxMSBOb3YgMjAyNSAxMzoxODo1OSArMDEwMApTdWJqZWN0OiBbUEFU Q0ggdjExIDIvM10gVXNlIHJhZGl4IHNvcnQgdG8gZXh0cmFjdCB0cmlncmFtcwoKUmVwbGFj ZSB0aGUgY29tcGFyaXNvbi1iYXNlZCBzb3J0IHVzZWQgYnkgZ2VuZXJhdGVfdHJnbSgpIGFu ZApnZW5lcmF0ZV93aWxkY2FyZF90cmdtKCkgd2l0aCBhIHRocmVlLXBhc3MgcmFkaXggc29y dC4KClRyaWdyYW1zIGNvbnNpc3Qgb2YgdGhyZWUgYnl0ZXMsIHNvIHRoZWlyIGtleXMgaGF2 ZSBhIGZpeGVkIGFuZCB2ZXJ5CnNtYWxsIHdpZHRoLiBBIHJhZGl4IHNvcnQgY2FuIHRoZXJl Zm9yZSBvcmRlciB0aGVtIGluIGxpbmVhciB0aW1lIHdpdGgKcmVzcGVjdCB0byB0aGUgbnVt YmVyIG9mIHRyaWdyYW1zLCBhdm9pZGluZyB0aGUgcmVwZWF0ZWQgY29tcGFyYXRvciBjYWxs cwphbmQgcmVjdXJzaXZlIHBhcnRpdGlvbmluZyBwZXJmb3JtZWQgYnkgcXNvcnQuClRoZSBp bXBsZW1lbnRhdGlvbiBwcmVzZXJ2ZXMgdGhlIGV4aXN0aW5nIGJlaGF2aW9yIG9uIHBsYXRm b3JtcyB3aGVyZQpjaGFyIGlzIHNpZ25lZCBieSBmbGlwcGluZyB0aGUgbW9zdCBzaWduaWZp Y2FudCBiaXQgYmVmb3JlIHNvcnRpbmcuCgpUaGUgcmFkaXggc29ydCByZXF1aXJlcyBhIHRl bXBvcmFyeSBidWZmZXIsIGluY3JlYXNpbmcgdGhlIG1lbW9yeQpmb290cHJpbnQgd2hpbGUg dHJpZ3JhbXMgYXJlIGJlaW5nIGV4dHJhY3RlZCBmcm9tIGFuIGlucHV0IHN0cmluZy4KSG93 ZXZlciwgdGhlIHNvcnQgaXMgcGVyZm9ybWVkIHNlcGFyYXRlbHkgZm9yIGVhY2ggc3RyaW5n IGFuZCBpcyBuZXZlcgphcHBsaWVkIGFjcm9zcyBtdWx0aXBsZSBzdHJpbmdzIGF0IG9uY2Uu IENvbnNlcXVlbnRseSwgdGhlIGFkZGl0aW9uYWwKbWVtb3J5IGlzIGxpbWl0ZWQgdG8gdGhl IHByb2Nlc3Npbmcgb2YgdGhlIGN1cnJlbnQgc3RyaW5nIGFuZCBzaG91bGQKaGF2ZSBhIG5l Z2xpZ2libGUgZWZmZWN0IG9uIHRoZSBvdmVyYWxsIG1lbW9yeSBmb290cHJpbnQgb2YgYSBH SU4gaW5kZXgKYnVpbGQuCgpUaGUgcmVzdWx0aW5nIG9yZGVyIHJlbWFpbnMgY29tcGF0aWJs ZSB3aXRoIHRyaWdyYW0gZGVkdXBsaWNhdGlvbiBhbmQKZG9lcyBub3QgY2hhbmdlIHRoZSBn ZW5lcmF0ZWQgdHJpZ3JhbSBzZXRzLgotLS0KIGNvbnRyaWIvcGdfdHJnbS90cmdtX29wLmMg fCA5OSArKysrKysrKysrKysrKysrKysrKysrKystLS0tLS0tLS0tLS0tLS0KIDEgZmlsZSBj aGFuZ2VkLCA2MSBpbnNlcnRpb25zKCspLCAzOCBkZWxldGlvbnMoLSkKCmRpZmYgLS1naXQg YS9jb250cmliL3BnX3RyZ20vdHJnbV9vcC5jIGIvY29udHJpYi9wZ190cmdtL3RyZ21fb3Au YwppbmRleCAyMmJjYzNjMzM2MS4uNTdlYWJhNDNmMTQgMTAwNjQ0Ci0tLSBhL2NvbnRyaWIv cGdfdHJnbS90cmdtX29wLmMKKysrIGIvY29udHJpYi9wZ190cmdtL3RyZ21fb3AuYwpAQCAt MjI2LDMzICsyMjYsNiBAQCBDTVBUUkdNX0NIT09TRShjb25zdCB2b2lkICphLCBjb25zdCB2 b2lkICpiKQogCXJldHVybiBDTVBUUkdNKGEsIGIpOwogfQogCi0jZGVmaW5lIFNUX1NPUlQg dHJpZ3JhbV9xc29ydF9zaWduZWQKLSNkZWZpbmUgU1RfRUxFTUVOVF9UWVBFX1ZPSUQKLSNk ZWZpbmUgU1RfQ09NUEFSRShhLCBiKSBDTVBUUkdNX1NJR05FRChhLCBiKQotI2RlZmluZSBT VF9TQ09QRSBzdGF0aWMKLSNkZWZpbmUgU1RfREVGSU5FCi0jZGVmaW5lIFNUX0RFQ0xBUkUK LSNpbmNsdWRlICJsaWIvc29ydF90ZW1wbGF0ZS5oIgotCi0jZGVmaW5lIFNUX1NPUlQgdHJp Z3JhbV9xc29ydF91bnNpZ25lZAotI2RlZmluZSBTVF9FTEVNRU5UX1RZUEVfVk9JRAotI2Rl ZmluZSBTVF9DT01QQVJFKGEsIGIpIENNUFRSR01fVU5TSUdORUQoYSwgYikKLSNkZWZpbmUg U1RfU0NPUEUgc3RhdGljCi0jZGVmaW5lIFNUX0RFRklORQotI2RlZmluZSBTVF9ERUNMQVJF Ci0jaW5jbHVkZSAibGliL3NvcnRfdGVtcGxhdGUuaCIKLQotLyogU29ydCBhbiBhcnJheSBv ZiB0cmlncmFtcywgaGFuZGxpbmcgc2lnbmVkbmVzcyBjb3JyZWN0bHkgKi8KLXN0YXRpYyB2 b2lkCi10cmlncmFtX3Fzb3J0KHRyZ20gKmFycmF5LCBzaXplX3QgbikKLXsKLQlpZiAoR2V0 RGVmYXVsdENoYXJTaWduZWRuZXNzKCkpCi0JCXRyaWdyYW1fcXNvcnRfc2lnbmVkKGFycmF5 LCBuLCBzaXplb2YodHJnbSkpOwotCWVsc2UKLQkJdHJpZ3JhbV9xc29ydF91bnNpZ25lZChh cnJheSwgbiwgc2l6ZW9mKHRyZ20pKTsKLX0KLQotCiAvKgogICogQ29tcGFyZSB0d28gdHJp Z3JhbXMgZm9yIGVxdWFsaXR5LiAgVGhpcyBoYXMgdGhlIHNhbWUgc2lnbmF0dXJlIGFzCiAg KiBjb21wYXJpc29uIGZ1bmN0aW9ucyB1c2VkIGZvciBzb3J0aW5nLCBzbyB0aGF0IHRoaXMg Y2FuIGJlIHVzZWQgd2l0aApAQCAtMjY4LDExICsyNDEsNjcgQEAgQ01QVFJHTV9FUShjb25z dCB2b2lkICphLCBjb25zdCB2b2lkICpiKQogCXJldHVybiBhYVswXSAhPSBiYlswXSB8fCBh YVsxXSAhPSBiYlsxXSB8fCBhYVsyXSAhPSBiYlsyXSA/IDEgOiAwOwogfQogCi0vKiBEZWR1 cGxpY2F0ZSBhbiBhcnJheSBvZiB0cmlncmFtcyAqLworLyoKKyAqIE5lZWRlZCB0byBwcm9w ZXJseSBoYW5kbGUgbmVnYXRpdmUgbnVtYmVycyBpbiBjYXNlIGNoYXIgaXMgc2lnbmVkLgor ICovCitzdGF0aWMgaW5saW5lIHVuc2lnbmVkIGNoYXIKK3JhZGl4X2tleShjaGFyIHgsIGJv b2wgY2hhcl9pc19zaWduZWQpCit7CisJcmV0dXJuIGNoYXJfaXNfc2lnbmVkID8geCBeIDB4 ODAgOiB4OworfQorCitzdGF0aWMgaW5saW5lIHNpemVfdAordHJpZ3JhbV9yYWRpeF9zb3J0 X2FuZF91bmlxdWUodHJnbSAqdHJnLCBzaXplX3QgY291bnQsIGJvb2wgY2hhcl9pc19zaWdu ZWQpCit7CisJdHJnbSAqYnVmZmVyID0gcGFsbG9jX2FycmF5KHRyZ20sIGNvdW50KTsKKwl0 cmdtICpzdGFydHNbMjU2XTsKKwl0cmdtICpmcm9tID0gdHJnOworCXRyZ20gKnRvID0gYnVm ZmVyOworCXNpemVfdCBmcmVxc1syNTZdOworCisJLyoKKwkgKiBEbyB0aGUgc29ydGluZy4g U3RhcnQgd2l0aCBsYXN0IGNoYXJhY3RlciBiZWNhdXNlIHRoYXQncyB0aGUgIkxTQiIKKwkg KiBpbiBhIHRyaWdyYW0uIEF2b2lkIHVubmVjZXNzYXJ5IGNvcGllcyBieSBwaW5nLXBvbmdp bmcgYmV0d2VlbiB0aGUgYnVmZmVycy4KKwkgKi8KKwlmb3IgKGludCBpID0gMjsgaSA+PSAw OyBpLS0pCisJeworCQl0cmdtICpvbGRfZnJvbSA9IGZyb207CisJCXRyZ20gKm5leHQgPSB0 bzsKKworCQkvKgorCQkqIENvbXB1dGUgZnJlcXVlbmNpZXMgdG8gcGFydGl0aW9uIHRoZSBi dWZmZXIuCisJCSovCisJCW1lbXNldChmcmVxcywgMCwgc2l6ZW9mKGZyZXFzKSk7CisKKwkJ Zm9yIChzaXplX3QgaiA9IDA7IGogPCBjb3VudDsgaisrKQorCQkJZnJlcXNbcmFkaXhfa2V5 KHRyZ1tqXVtpXSwgY2hhcl9pc19zaWduZWQpXSsrOworCisJCWZvciAoc2l6ZV90IGogPSAw OyBqIDwgMjU2OyBqKyspCisJCXsKKwkJCXN0YXJ0c1tqXSA9IG5leHQ7CisJCQluZXh0ICs9 IGZyZXFzW2pdOworCQl9CisKKwkJZm9yIChzaXplX3QgaiA9IDA7IGogPCBjb3VudDsgaisr KQorCQkJbWVtY3B5KHN0YXJ0c1tyYWRpeF9rZXkoZnJvbVtqXVtpXSwgY2hhcl9pc19zaWdu ZWQpXSsrLCBmcm9tW2pdLCBzaXplb2YodHJnbSkpOworCisJCWZyb20gPSB0bzsKKwkJdG8g PSBvbGRfZnJvbTsKKwl9CisKKwljb3VudCA9IHF1bmlxdWUoYnVmZmVyLCBjb3VudCwgc2l6 ZW9mKHRyZ20pLCBDTVBUUkdNX0VRKTsKKwltZW1jcHkodHJnLCBidWZmZXIsIHNpemVvZih0 cmdtKSAqIGNvdW50KTsKKwlwZnJlZShidWZmZXIpOworCXJldHVybiBjb3VudDsKK30KKwog c3RhdGljIHNpemVfdAotdHJpZ3JhbV9xdW5pcXVlKHRyZ20gKmFycmF5LCBzaXplX3QgbikK K3RyaWdyYW1fc29ydF9hbmRfdW5pcXVlKHRyZ20gKmFycmF5LCBzaXplX3QgbikKIHsKLQly ZXR1cm4gcXVuaXF1ZShhcnJheSwgbiwgc2l6ZW9mKHRyZ20pLCBDTVBUUkdNX0VRKTsKKwlp ZiAoR2V0RGVmYXVsdENoYXJTaWduZWRuZXNzKCkpCisJCXJldHVybiB0cmlncmFtX3JhZGl4 X3NvcnRfYW5kX3VuaXF1ZShhcnJheSwgbiwgdHJ1ZSk7CisJZWxzZQorCQlyZXR1cm4gdHJp Z3JhbV9yYWRpeF9zb3J0X2FuZF91bmlxdWUoYXJyYXksIG4sIGZhbHNlKTsKIH0KIAogLyoK QEAgLTYxMSwxMCArNjQwLDcgQEAgZ2VuZXJhdGVfdHJnbShjaGFyICpzdHIsIGludCBzbGVu KQogCSAqIE1ha2UgdHJpZ3JhbXMgdW5pcXVlLgogCSAqLwogCWlmIChsZW4gPiAxKQotCXsK LQkJdHJpZ3JhbV9xc29ydChHRVRBUlIodHJnKSwgbGVuKTsKLQkJbGVuID0gdHJpZ3JhbV9x dW5pcXVlKEdFVEFSUih0cmcpLCBsZW4pOwotCX0KKwkJbGVuID0gdHJpZ3JhbV9zb3J0X2Fu ZF91bmlxdWUoR0VUQVJSKHRyZyksIGxlbik7CiAKIAlTRVRfVkFSU0laRSh0cmcsIENBTENH VFNJWkUoQVJSS0VZLCBsZW4pKTsKIApAQCAtMTE0MiwxMCArMTE2OCw3IEBAIGdlbmVyYXRl X3dpbGRjYXJkX3RyZ20oY29uc3QgY2hhciAqc3RyLCBpbnQgc2xlbikKIAl0cmcgPSBhcnIu ZGF0dW07CiAJbGVuID0gYXJyLmxlbmd0aDsKIAlpZiAobGVuID4gMSkKLQl7Ci0JCXRyaWdy YW1fcXNvcnQoR0VUQVJSKHRyZyksIGxlbik7Ci0JCWxlbiA9IHRyaWdyYW1fcXVuaXF1ZShH RVRBUlIodHJnKSwgbGVuKTsKLQl9CisJCWxlbiA9IHRyaWdyYW1fc29ydF9hbmRfdW5pcXVl KEdFVEFSUih0cmcpLCBsZW4pOwogCiAJdHJnLT5mbGFnID0gQVJSS0VZOwogCVNFVF9WQVJT SVpFKHRyZywgQ0FMQ0dUU0laRShBUlJLRVksIGxlbikpOwotLSAKMi41My4wCgo= --------------i0uBgFL0BR4Os7d0xe0pjhHC Content-Type: text/x-patch; charset=UTF-8; name="v11-0001-Use-branchless-comparisons-in-btint4cmp-and-btin.patch" Content-Disposition: attachment; filename*0="v11-0001-Use-branchless-comparisons-in-btint4cmp-and-btin.pa"; filename*1="tch" Content-Transfer-Encoding: base64 RnJvbSA5Zjc3Nzc3MDMxNjY1ZDM5OGQ3Y2VhYWQ3ZDM5MDYzMGQ2MDU0OTExIE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBEYXZpZCBHZWllciA8Z2VpZGF2LnBnQGdtYWlsLmNv bT4KRGF0ZTogTW9uLCAxMCBOb3YgMjAyNSAxNTo0MDoxMSArMDEwMApTdWJqZWN0OiBbUEFU Q0ggdjExIDEvM10gVXNlIGJyYW5jaGxlc3MgY29tcGFyaXNvbnMgaW4gYnRpbnQ0Y21wIGFu ZCBidGludDhjbXAKClVzZSB0aGUgY29tbW9uIHBnX2NtcF9zMzIoKSBhbmQgcGdfY21wX3M2 NCgpIGhlbHBlcnMgdG8gaW1wbGVtZW50IHRoZQpidWlsdC1pbiBCLXRyZWUgY29tcGFyaXNv biBmdW5jdGlvbnMgZm9yIGludDQgYW5kIGludDguCgpUaGUgcHJldmlvdXMgaW1wbGVtZW50 YXRpb25zIHVzZWQgY29uZGl0aW9uYWwgYnJhbmNoZXMgdG8gZGlzdGluZ3Vpc2gKbGVzcy10 aGFuLCBlcXVhbCwgYW5kIGdyZWF0ZXItdGhhbiB2YWx1ZXMuIFRoZSBjb21tb24gY29tcGFy aXNvbiBoZWxwZXJzCnBlcmZvcm0gdGhlIHNhbWUgdGhyZWUtd2F5IGNvbXBhcmlzb24gd2l0 aG91dCBkYXRhLWRlcGVuZGVudCBicmFuY2hlcywKd2hpY2ggY2FuIGltcHJvdmUgcGVyZm9y bWFuY2UgZm9yIHdvcmtsb2FkcyBpbnZvbHZpbmcgZnJlcXVlbnQgaW50ZWdlcgpjb21wYXJp c29ucyB3aGlsZSBwcmVzZXJ2aW5nIHRoZSByZXF1aXJlZCBjb21wYXJhdG9yIHJlc3VsdCBz ZW1hbnRpY3MuCgpidGludDRjbXAoKSBhbmQgYnRpbnQ4Y21wKCkgYXJlIFBvc3RncmVTUUwt Y2FsbGFibGUgZnVuY3Rpb25zIGludm9rZWQKdGhyb3VnaCB0aGUgZnVuY3Rpb24gbWFuYWdl ci4gVGhleSBhcmUgbm90IGlubGluZWQgYXQgdGhlaXIgY2FsbCBzaXRlcywKc28gcmVwbGFj aW5nIHRoZSBvcmlnaW5hbCBjb25kaXRpb25hbCBpbXBsZW1lbnRhdGlvbiBkb2VzIG5vdCBw cmV2ZW50IGEKY29tcGlsZXIgZnJvbSBvcHRpbWl6aW5nIGFuIGlubGluZSBjb21wYXJpc29u IGluIGNvbnRleHRzIHdoZXJlIGl0IGNhbgpzZWUgYW5kIGJldHRlciBvcHRpbWl6ZSB0aGUg c3Vycm91bmRpbmcgY29kZS4gSW4gb3RoZXIgd29yZHMsIHRoaXMKY2hhbmdlIGFmZmVjdHMg dGhlIGZ1bmN0aW9uLW1hbmFnZXIgY2FsbCBwYXRoIHdpdGhvdXQgaW1wb3NpbmcgYQpwZXJm b3JtYW5jZSByZWdyZXNzaW9uIG9uIGNhbGxlcnMgZm9yIHdoaWNoIHRoZSBjb21wYXJpc29u IGNvdWxkCm90aGVyd2lzZSBoYXZlIGJlZW4gaW5saW5lZC4KClRoZSBjb21wYXJpc29uIGhl bHBlcnMgYWxzbyBwcm92aWRlIHRoZSBhcHByb3ByaWF0ZSBoYW5kbGluZyBmb3IgdGhlCmZ1 bGwgcmFuZ2VzIG9mIGludDMyIGFuZCBpbnQ2NCB2YWx1ZXMgd2l0aG91dCByZWx5aW5nIG9u IHN1YnRyYWN0aW9uLAp3aGljaCBjb3VsZCBvdmVyZmxvdyBmb3IgdmFsdWVzIG5lYXIgdGhl IHR5cGUgbGltaXRzLgotLS0KIHNyYy9iYWNrZW5kL2FjY2Vzcy9uYnRyZWUvbmJ0Y29tcGFy ZS5jIHwgMTUgKysrLS0tLS0tLS0tLS0tCiAxIGZpbGUgY2hhbmdlZCwgMyBpbnNlcnRpb25z KCspLCAxMiBkZWxldGlvbnMoLSkKCmRpZmYgLS1naXQgYS9zcmMvYmFja2VuZC9hY2Nlc3Mv bmJ0cmVlL25idGNvbXBhcmUuYyBiL3NyYy9iYWNrZW5kL2FjY2Vzcy9uYnRyZWUvbmJ0Y29t cGFyZS5jCmluZGV4IDRlM2EzYTBmN2NlLi44MGRlYzIwMGEzZCAxMDA2NDQKLS0tIGEvc3Jj L2JhY2tlbmQvYWNjZXNzL25idHJlZS9uYnRjb21wYXJlLmMKKysrIGIvc3JjL2JhY2tlbmQv YWNjZXNzL25idHJlZS9uYnRjb21wYXJlLmMKQEAgLTYxLDYgKzYxLDcgQEAKICNpbmNsdWRl ICJ1dGlscy9mbWdycHJvdG9zLmgiCiAjaW5jbHVkZSAidXRpbHMvc2tpcHN1cHBvcnQuaCIK ICNpbmNsdWRlICJ1dGlscy9zb3J0c3VwcG9ydC5oIgorI2luY2x1ZGUgImNvbW1vbi9pbnQu aCIKIAogI2lmZGVmIFNUUkVTU19TT1JUX0lOVF9NSU4KICNkZWZpbmUgQV9MRVNTX1RIQU5f QgkJSU5UX01JTgpAQCAtMTk0LDEyICsxOTUsNyBAQCBidGludDRjbXAoUEdfRlVOQ1RJT05f QVJHUykKIAlpbnQzMgkJYSA9IFBHX0dFVEFSR19JTlQzMigwKTsKIAlpbnQzMgkJYiA9IFBH X0dFVEFSR19JTlQzMigxKTsKIAotCWlmIChhID4gYikKLQkJUEdfUkVUVVJOX0lOVDMyKEFf R1JFQVRFUl9USEFOX0IpOwotCWVsc2UgaWYgKGEgPT0gYikKLQkJUEdfUkVUVVJOX0lOVDMy KDApOwotCWVsc2UKLQkJUEdfUkVUVVJOX0lOVDMyKEFfTEVTU19USEFOX0IpOworCVBHX1JF VFVSTl9JTlQzMihwZ19jbXBfczMyKGEsIGIpKTsKIH0KIAogRGF0dW0KQEAgLTI2MiwxMiAr MjU4LDcgQEAgYnRpbnQ4Y21wKFBHX0ZVTkNUSU9OX0FSR1MpCiAJaW50NjQJCWEgPSBQR19H RVRBUkdfSU5UNjQoMCk7CiAJaW50NjQJCWIgPSBQR19HRVRBUkdfSU5UNjQoMSk7CiAKLQlp ZiAoYSA+IGIpCi0JCVBHX1JFVFVSTl9JTlQzMihBX0dSRUFURVJfVEhBTl9CKTsKLQllbHNl IGlmIChhID09IGIpCi0JCVBHX1JFVFVSTl9JTlQzMigwKTsKLQllbHNlCi0JCVBHX1JFVFVS Tl9JTlQzMihBX0xFU1NfVEhBTl9CKTsKKwlQR19SRVRVUk5fSU5UMzIocGdfY21wX3M2NChh LCBiKSk7CiB9CiAKIERhdHVtCi0tIAoyLjUzLjAKCg== --------------i0uBgFL0BR4Os7d0xe0pjhHC--