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 1wFf68-005PZu-2z for pgsql-hackers@arkaria.postgresql.org; Wed, 22 Apr 2026 21:27:05 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.96) (envelope-from ) id 1wFf67-00FQTB-2Q for pgsql-hackers@arkaria.postgresql.org; Wed, 22 Apr 2026 21:27:03 +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 1wFf67-00FQT2-1E for pgsql-hackers@lists.postgresql.org; Wed, 22 Apr 2026 21:27:03 +0000 Received: from mail-wr1-x42d.google.com ([2a00:1450:4864:20::42d]) by magus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.98.2) (envelope-from ) id 1wFf65-00000002XMw-00nG for pgsql-hackers@postgresql.org; Wed, 22 Apr 2026 21:27:03 +0000 Received: by mail-wr1-x42d.google.com with SMTP id ffacd0b85a97d-43d7650202fso4611991f8f.2 for ; Wed, 22 Apr 2026 14:27:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1776893219; x=1777498019; darn=postgresql.org; h=in-reply-to:content-language:references:cc:to:subject:from :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=cQR1t4RNYepxvSkg+mXUKIJdPFQto5DLCViiJJpjt84=; b=PmthQFM1iSeo32Sd79jprzc+3sbcs22rdd1KzcURLjEmPP06MkRZnLS0Gv27VlI8rH R+AFunZd0mjOUXilevoHoFPdm3uRsI1dqDpaVr/BCto00zNLQe/1CPmnw8s4s/lguCIp 9AuiUw6courkgzt5QfBvOKKl20ZpSDb/dKit1l6j4gzuCUXytAIcZ8IQEgFBo4be/YqT iPOkrZV9x0fCLkszGUGQsM8RcksKLnO6xm5oCrjKX13VqNsM29NS6EBpE4M6GS8h+Ooz Bg6JF2IhVi3uWw4MjxauMJ/9TwrovPXMPgZHSkb1DuECFCLjqDVSJ62gh83egjKG6p5a Dgig== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1776893219; x=1777498019; h=in-reply-to:content-language:references:cc:to:subject:from :user-agent:mime-version:date:message-id:x-gm-gg:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=cQR1t4RNYepxvSkg+mXUKIJdPFQto5DLCViiJJpjt84=; b=ijRC9jY96w7RQrNSnffpTqTim+ot3vGBMFL4JR2exJg3S9JnJnZJiYgU071U7XU3/u V3nJK1m2R94U7xaNv/21/S20I7iy2P0NR7t3tJqt3SfRwrSnusGfzNTp8qbeVdKlYl0k leU/nK/NzSSje3xucvILzezVwQRItnerym2Q6D5tXaoW+3pgsjogx5RaS5xam06zmXGJ wbcuLeEoluolJr9V0vbICxB0jpeFqAg9HfVmmlMD7GA6UT387wKOM4FUrAvEBVF2Hf08 QyBaeGlPxkGSkBIOEaGshMuL+/TD2r3Z8Q+/4E0s0OA58LpQWmW2S11E4XERabBp+qQR pgRw== X-Gm-Message-State: AOJu0YxG/L2AxOWumczcTfiQhVZmJWS14D1bGGuk4iJaqEXr3pLiLjQr CnkWEJBiTaqlRzlvRXoeQlgpjVAeSITwe4ElI2Hz5u/MwLFJzcdtW3OM X-Gm-Gg: AeBDievjmF5SQSgwH/ZLzsSUR/fnTYjVOB5Ggpknmmo3qlYotvP9eLjvbvDFnCRgDTC 2FRMqlXAy1HTPms3m3R/H7yyLzXN2KKBI+mRD4gABrqppli6UZuEWGOj8O36c7UaJQSIM8QXeYk IOAZGtCWDa8Idm4bdKDCVKiBYczc532hpSs169m4kfg7CczFteT9XTuPKKIg63+v5NnHyYMPjVh NypvG264cCyljqVZyTWKyYccfYQn1y/AEw+SfLRTIlKxGalXGZ3u2wIoGQC/aa2BIFVsH2R/xWP d/IN5flI2HudqB8oq1vE4FVb8S17gjvQBZT+Yv3Xc3Lbo2Z1VDydTzpmWG8x0CXf5AZ9wbbHGt4 qrVM1TpXB+NquviIPu62uNJTlQS7EDvWHDPHkx2IHXIb5FIAwZlHgwJdD6ldDiu/ahV9dcyRV56 x9K7/Y01N+kKI0cVKzxxJI8QQQcx8KIYU0C+w= X-Received: by 2002:a05:6000:26cf:b0:441:1fa5:457e with SMTP id ffacd0b85a97d-4411fa548d5mr14054497f8f.13.1776893218860; Wed, 22 Apr 2026 14:26:58 -0700 (PDT) Received: from [172.31.5.233] ([165.225.27.16]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-43fe4e4d525sm46048094f8f.31.2026.04.22.14.26.57 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 22 Apr 2026 14:26:57 -0700 (PDT) Content-Type: multipart/mixed; boundary="------------0Z0AtKWMsTOAeFv0hcZKxpd4" Message-ID: <10395cb6-a804-49ac-b2f1-3f98d7204359@gmail.com> Date: Wed, 22 Apr 2026 23:26:56 +0200 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird From: David Geier Subject: Re: Reduce build times of pg_trgm GIN indexes To: Heikki Linnakangas , Matthias van de Meent Cc: pgsql-hackers References: <5d366878-2007-4d31-861e-19294b7a583b@gmail.com> <9ac3931a-180e-4283-a7a8-05eb66099206@iki.fi> <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> Content-Language: en-US In-Reply-To: <5650bf75-dcb8-446d-8cba-e626eb44594b@gmail.com> 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. --------------0Z0AtKWMsTOAeFv0hcZKxpd4 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit On 14.04.2026 16:24, David Geier wrote: > Attached are the remaining patches (previously 0003 and 0005) rebased on > latest master. Currently, there's no radix sort variant for the unsigned > char case. Do we care about this case or is it fine if that case runs > slower? > > The following perf profiles show that trigram_qsort() goes from ~34% > down to ~7% with the radix sort optimization. The optimized run also > includes the btint4cmp() optimization. Without that the result would be > even better. > > With that change we could move on and tackle optimizing > > 1. 41.52% generate_trgm_only() by e.g. using an ASCII fast-patch > 2. 32.72% ginInsertBAEntries() by no longer using the RB-tree but > e.g. also the radix sort Attached is the rebased patch set as well as a new patch that optimizes ginInsertBAEntries(). Performance improvements are as follows, measured with the same benchmark I used in the first mail of this thread. Runtimes and deltas are in milliseconds. Code | movies | delta | lineitem | delta -----------------------------------|--------|--------|------------------ master | 11,160 | - | 248,146 | - v7-0001-Make-btint4cmp-branchless | 9,509 | 1,651 | 236,760 | 11,386 v7-0002-Use-radix-sort | 6,123 | 3,386 | 214,632 | 22,128 v7-0003-Replace-RB-tree | 4,755 | 1,368 | 144,252 | 70,380 I optimized ginInsertBAEntries() by replacing the red-black tree by a hash map (simplehash.h) on the keys (e.g. trigrams), where each hash map entry contains an item pointer list with the row TIDs the key occurs in. This is in the spirit of the original red-black tree implementation but this way the deduplication of each key is handled in O(1), instead of O(log(num_unique_keys)). This reduces the overall runtime complexity from O(num_total_keys * log(num_unique_keys)) -> O(num_total_keys + num_unique_keys * log(num_unique_keys)) As there are normally a lot less keys than rows, this is complexity-wise preferable. And even if all keys are unique, the rebalancing operations are pretty expensive and in reality outweigh the slightly better complexity in the worst-case. - The sorting of the item pointer lists for each key stays as is, except for that I switched to sort_template.h. - The red-black tree code in rbtree.c/.h is now completely unused and could be removed. Thoughts? - The size on disk changed very slightly. I think this is because the memory accounting is slightly different and with that slightly more or less keys / item pointers can be processed in one go. - FWICS, we can use datumIsEqual() and datum_image_hash() in the hash map because as of today, the GIN index code doesn't work properly with non-deterministic collations / non-image-equal types, e.g. see [1]. - I also simplified ginInsertBAEntries(). Previously, it used an insertion order that minimizes the number of RB-tree rebalancing operations for sorted inputs. With the hash map approach, it's better to insert in sort order as this increases the likelihood of hitting the same hash map entry again for equal keys. - This patch set also improves parallel GIN index builds as the parallel code builds on top of ginInsertBAEntries(). - Regression tests pass and gin_index_check() from amcheck couldn't find an error in the data structures. To be fair: 0001 is less interesting after removing the RB-tree because a lot less key comparisons are being performed. I still think it makes sense to merge it as it should also accelerate e.g. B-tree traversals. With these changes the number one bottleneck becomes the trigram generation in generate_trgm_only(). The following perf profile nicely shows that: - 99.89% 0.00% postgres postgres [.] ginbuild ginbuild table_index_build_scan (inlined) - heapam_index_build_range_scan - 94.05% ginBuildCallback - 86.48% ginHeapTupleBulkInsert - 68.57% ginExtractEntries - 64.69% FunctionCall3Coll - gin_extract_value_trgm - 62.75% generate_trgm - 39.57% generate_trgm_only + 18.53% str_tolower + 16.91% find_word (inlined) + 1.36% make_trigrams (inlined) 0.66% __strlen_avx2 + 18.49% trigram_qsort (inlined) + 4.17% trigram_qunique (inlined) 0.79% trgm2int + 3.33% qsort_arg_entries - 17.28% ginInsertBAEntries - ginInsertBAEntry (inlined) - 8.04% ginbuild_insert (inlined) - 4.89% ginbuild_insert_hash_internal (inlined) 1.25% gin_equal_key (inlined) 0.68% ginbuild_initial_bucket (inlined) + 3.14% gin_hash_key (inlined) + 2.45% AllocSetRealloc + 0.85% asm_exc_page_fault 0.52% getDatumCopy (inlined) + 6.00% ginEntryInsert + 1.19% ginBeginBAScan + 2.99% heap_getnext [1] https://www.postgresql.org/message-id/flat/8ef4899c4acfebca45cc6c042a6dc611d25ffab1.camel%40cybertec.at -- David Geier --------------0Z0AtKWMsTOAeFv0hcZKxpd4 Content-Type: text/x-patch; charset=UTF-8; name="v7-0003-Replace-RB-tree-with-hash-map-and-sort-in-GIN-ind.patch" Content-Disposition: attachment; filename*0="v7-0003-Replace-RB-tree-with-hash-map-and-sort-in-GIN-ind.pa"; filename*1="tch" Content-Transfer-Encoding: base64 RnJvbSBjM2ZiNjI2Y2FlNTZiY2I2MjBhZjAyYmU1NWRkMThjY2FiOTdkYTcyIE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBEYXZpZCBHZWllciA8Z2VpZGF2LnBnQGdtYWlsLmNv bT4KRGF0ZTogV2VkLCAyMiBBcHIgMjAyNiAxNDowMDo0MCArMDIwMApTdWJqZWN0OiBbUEFU Q0ggdjcgMy8zXSBSZXBsYWNlIFJCLXRyZWUgd2l0aCBoYXNoIG1hcCBhbmQgc29ydCBpbiBH SU4gaW5kZXgKCi0tLQogc3JjL2JhY2tlbmQvYWNjZXNzL2dpbi9naW5idWxrLmMgfCAzNDMg KysrKysrKysrKysrKysrLS0tLS0tLS0tLS0tLS0tLQogc3JjL2luY2x1ZGUvYWNjZXNzL2dp bl9wcml2YXRlLmggfCAgMjQgKy0tCiAyIGZpbGVzIGNoYW5nZWQsIDE3MiBpbnNlcnRpb25z KCspLCAxOTUgZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2JhY2tlbmQvYWNjZXNz L2dpbi9naW5idWxrLmMgYi9zcmMvYmFja2VuZC9hY2Nlc3MvZ2luL2dpbmJ1bGsuYwppbmRl eCA4NTg2NWIzOTEwNS4uZTJkMjM3ODYyMjUgMTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL2Fj Y2Vzcy9naW4vZ2luYnVsay5jCisrKyBiL3NyYy9iYWNrZW5kL2FjY2Vzcy9naW4vZ2luYnVs ay5jCkBAIC0xNywxMDcgKzE3LDExOCBAQAogI2luY2x1ZGUgPGxpbWl0cy5oPgogCiAjaW5j bHVkZSAiYWNjZXNzL2dpbl9wcml2YXRlLmgiCisjaW5jbHVkZSAiY29tbW9uL2hhc2hmbi5o IgogI2luY2x1ZGUgInV0aWxzL2RhdHVtLmgiCiAjaW5jbHVkZSAidXRpbHMvbWVtdXRpbHMu aCIKIAorI2RlZmluZSBERUZfTkVOVFJZCQkJMjA0OAkvKiBJbml0aWFsIGhhc2ggdGFibGUg c2l6ZSAqLworI2RlZmluZSBERUZfSVRFTVNfUEVSX0tFWQk4CQkvKiBJbml0aWFsIEl0ZW1Q b2ludGVyIGFycmF5IHNpemUgcGVyIGtleSAqLwogCi0jZGVmaW5lIERFRl9ORU5UUlkJMjA0 OAkJLyogR2luRW50cnlBY2N1bXVsYXRvciBhbGxvY2F0aW9uIHF1YW50dW0gKi8KLSNkZWZp bmUgREVGX05QVFIJNQkJCS8qIEl0ZW1Qb2ludGVyIGluaXRpYWwgYWxsb2NhdGlvbiBxdWFu dHVtICovCi0KLQotLyogQ29tYmluZXIgZnVuY3Rpb24gZm9yIHJidHJlZS5jICovCi1zdGF0 aWMgdm9pZAotZ2luQ29tYmluZURhdGEoUkJUTm9kZSAqZXhpc3RpbmcsIGNvbnN0IFJCVE5v ZGUgKm5ld2RhdGEsIHZvaWQgKmFyZykKK3R5cGVkZWYgc3RydWN0IEdpbkhhc2hLZXkKIHsK LQlHaW5FbnRyeUFjY3VtdWxhdG9yICplbyA9IChHaW5FbnRyeUFjY3VtdWxhdG9yICopIGV4 aXN0aW5nOwotCWNvbnN0IEdpbkVudHJ5QWNjdW11bGF0b3IgKmVuID0gKGNvbnN0IEdpbkVu dHJ5QWNjdW11bGF0b3IgKikgbmV3ZGF0YTsKLQlCdWlsZEFjY3VtdWxhdG9yICphY2N1bSA9 IChCdWlsZEFjY3VtdWxhdG9yICopIGFyZzsKKwlPZmZzZXROdW1iZXIJYXR0bnVtOworCUdp bk51bGxDYXRlZ29yeQljYXRlZ29yeTsKKwlEYXR1bQkJCWtleTsKK30gR2luSGFzaEtleTsK IAotCS8qCi0JICogTm90ZSB0aGlzIGNvZGUgYXNzdW1lcyB0aGF0IG5ld2RhdGEgY29udGFp bnMgb25seSBvbmUgaXRlbXBvaW50ZXIuCi0JICovCi0JaWYgKGVvLT5jb3VudCA+PSBlby0+ bWF4Y291bnQpCi0JewotCQlpZiAoZW8tPm1heGNvdW50ID4gSU5UX01BWCkKLQkJCWVyZXBv cnQoRVJST1IsCi0JCQkJCShlcnJjb2RlKEVSUkNPREVfUFJPR1JBTV9MSU1JVF9FWENFRURF RCksCi0JCQkJCSBlcnJtc2coInBvc3RpbmcgbGlzdCBpcyB0b28gbG9uZyIpLAotCQkJCQkg ZXJyaGludCgiUmVkdWNlIFwibWFpbnRlbmFuY2Vfd29ya19tZW1cIi4iKSkpOwordHlwZWRl ZiBzdHJ1Y3QgR2luSGFzaEVudHJ5Cit7CisJR2luSGFzaEtleQkJCWhhc2hrZXk7CisJdWlu dDMyCQkJCWhhc2g7CisJY2hhcgkJCQlzdGF0dXM7CisJSXRlbVBvaW50ZXJEYXRhICoJaXRl bXM7CisJdWludDMyCQkJCW51bUl0ZW1zOworCXVpbnQzMgkJCQlhbGxvY2F0ZWRJdGVtczsK K30gR2luSGFzaEVudHJ5OworCit0eXBlZGVmIHN0cnVjdCBHaW5Tb3J0RW50cnkKK3sKKwlH aW5IYXNoS2V5CQkJaGFzaGtleTsKKwlJdGVtUG9pbnRlckRhdGEgKglpdGVtczsKKwl1aW50 MzIgCQkJCW51bUl0ZW1zOworfSBHaW5Tb3J0RW50cnk7CisKK3N0YXRpYyB1aW50MzIgZ2lu X2hhc2hfa2V5KHN0cnVjdCBnaW5idWlsZF9oYXNoICp0YiwgR2luSGFzaEtleSAqa2V5KTsK K3N0YXRpYyBib29sIGdpbl9lcXVhbF9rZXkoc3RydWN0IGdpbmJ1aWxkX2hhc2ggKnRiLCBH aW5IYXNoS2V5ICphLCBHaW5IYXNoS2V5ICpiKTsKKworI2RlZmluZSBTSF9QUkVGSVggZ2lu YnVpbGQKKyNkZWZpbmUgU0hfRUxFTUVOVF9UWVBFIEdpbkhhc2hFbnRyeQorI2RlZmluZSBT SF9LRVlfVFlQRSBHaW5IYXNoS2V5CisjZGVmaW5lIFNIX0tFWSBoYXNoa2V5CisjZGVmaW5l IFNIX0hBU0hfS0VZKHRiLCBrZXkpIGdpbl9oYXNoX2tleSh0YiwgJmtleSkKKyNkZWZpbmUg U0hfRVFVQUwodGIsIGEsIGIpIGdpbl9lcXVhbF9rZXkodGIsICZhLCAmYikKKyNkZWZpbmUg U0hfU0NPUEUgc3RhdGljIGlubGluZQorI2RlZmluZSBTSF9TVE9SRV9IQVNICisjZGVmaW5l IFNIX0dFVF9IQVNIKHRiLCBhKSAoYSktPmhhc2gKKyNkZWZpbmUgU0hfREVGSU5FCisjZGVm aW5lIFNIX0RFQ0xBUkUKKyNpbmNsdWRlICJsaWIvc2ltcGxlaGFzaC5oIgorCitzdGF0aWMg dWludDMyCitnaW5faGFzaF9rZXkoc3RydWN0IGdpbmJ1aWxkX2hhc2ggKnRiLCBHaW5IYXNo S2V5ICprZXkpCit7CisJQnVpbGRBY2N1bXVsYXRvciAqYWNjdW0gPSAoQnVpbGRBY2N1bXVs YXRvciAqKSB0Yi0+cHJpdmF0ZV9kYXRhOworCXVpbnQzMgkJaGFzaDsKIAotCQlhY2N1bS0+ YWxsb2NhdGVkTWVtb3J5IC09IEdldE1lbW9yeUNodW5rU3BhY2UoZW8tPmxpc3QpOwotCQll by0+bWF4Y291bnQgKj0gMjsKLQkJZW8tPmxpc3QgPSAoSXRlbVBvaW50ZXJEYXRhICopCi0J CQlyZXBhbGxvY19odWdlKGVvLT5saXN0LCBzaXplb2YoSXRlbVBvaW50ZXJEYXRhKSAqIGVv LT5tYXhjb3VudCk7Ci0JCWFjY3VtLT5hbGxvY2F0ZWRNZW1vcnkgKz0gR2V0TWVtb3J5Q2h1 bmtTcGFjZShlby0+bGlzdCk7Ci0JfQorCWhhc2ggPSBoYXNoX2NvbWJpbmUoMCwgbXVybXVy aGFzaDMyKCh1aW50MzIpIGtleS0+YXR0bnVtKSk7CisJaGFzaCA9IGhhc2hfY29tYmluZSho YXNoLCBtdXJtdXJoYXNoMzIoKHVpbnQzMikga2V5LT5jYXRlZ29yeSkpOwogCi0JLyogSWYg aXRlbSBwb2ludGVycyBhcmUgbm90IG9yZGVyZWQsIHRoZXkgd2lsbCBuZWVkIHRvIGJlIHNv cnRlZCBsYXRlciAqLwotCWlmIChlby0+c2hvdWxkU29ydCA9PSBmYWxzZSkKKwlpZiAoa2V5 LT5jYXRlZ29yeSA9PSBHSU5fQ0FUX05PUk1fS0VZKQogCXsKLQkJaW50CQkJcmVzOwotCi0J CXJlcyA9IGdpbkNvbXBhcmVJdGVtUG9pbnRlcnMoZW8tPmxpc3QgKyBlby0+Y291bnQgLSAx LCBlbi0+bGlzdCk7Ci0JCUFzc2VydChyZXMgIT0gMCk7CisJCUNvbXBhY3RBdHRyaWJ1dGUg KmF0dDsKIAotCQlpZiAocmVzID4gMCkKLQkJCWVvLT5zaG91bGRTb3J0ID0gdHJ1ZTsKKwkJ YXR0ID0gVHVwbGVEZXNjQ29tcGFjdEF0dHIoYWNjdW0tPmdpbnN0YXRlLT5vcmlnVHVwZGVz Yywga2V5LT5hdHRudW0gLSAxKTsKKwkJaGFzaCA9IGhhc2hfY29tYmluZShoYXNoLCBkYXR1 bV9pbWFnZV9oYXNoKGtleS0+a2V5LCBhdHQtPmF0dGJ5dmFsLCBhdHQtPmF0dGxlbikpOwog CX0KIAotCWVvLT5saXN0W2VvLT5jb3VudF0gPSBlbi0+bGlzdFswXTsKLQllby0+Y291bnQr KzsKKwlyZXR1cm4gaGFzaDsKIH0KIAotLyogQ29tcGFyYXRvciBmdW5jdGlvbiBmb3IgcmJ0 cmVlLmMgKi8KLXN0YXRpYyBpbnQKLWNtcEVudHJ5QWNjdW11bGF0b3IoY29uc3QgUkJUTm9k ZSAqYSwgY29uc3QgUkJUTm9kZSAqYiwgdm9pZCAqYXJnKQorc3RhdGljIGJvb2wKK2dpbl9l cXVhbF9rZXkoc3RydWN0IGdpbmJ1aWxkX2hhc2ggKnRiLCBHaW5IYXNoS2V5ICphLCBHaW5I YXNoS2V5ICpiKQogewotCWNvbnN0IEdpbkVudHJ5QWNjdW11bGF0b3IgKmVhID0gKGNvbnN0 IEdpbkVudHJ5QWNjdW11bGF0b3IgKikgYTsKLQljb25zdCBHaW5FbnRyeUFjY3VtdWxhdG9y ICplYiA9IChjb25zdCBHaW5FbnRyeUFjY3VtdWxhdG9yICopIGI7Ci0JQnVpbGRBY2N1bXVs YXRvciAqYWNjdW0gPSAoQnVpbGRBY2N1bXVsYXRvciAqKSBhcmc7Ci0KLQlyZXR1cm4gZ2lu Q29tcGFyZUF0dEVudHJpZXMoYWNjdW0tPmdpbnN0YXRlLAotCQkJCQkJCQllYS0+YXR0bnVt LCBlYS0+a2V5LCBlYS0+Y2F0ZWdvcnksCi0JCQkJCQkJCWViLT5hdHRudW0sIGViLT5rZXks IGViLT5jYXRlZ29yeSk7Ci19CisJQnVpbGRBY2N1bXVsYXRvciAqYWNjdW0gPSAoQnVpbGRB Y2N1bXVsYXRvciAqKSB0Yi0+cHJpdmF0ZV9kYXRhOworCUNvbXBhY3RBdHRyaWJ1dGUgKmF0 dDsKIAotLyogQWxsb2NhdG9yIGZ1bmN0aW9uIGZvciByYnRyZWUuYyAqLwotc3RhdGljIFJC VE5vZGUgKgotZ2luQWxsb2NFbnRyeUFjY3VtdWxhdG9yKHZvaWQgKmFyZykKLXsKLQlCdWls ZEFjY3VtdWxhdG9yICphY2N1bSA9IChCdWlsZEFjY3VtdWxhdG9yICopIGFyZzsKLQlHaW5F bnRyeUFjY3VtdWxhdG9yICplYTsKKwlpZiAoYS0+YXR0bnVtICE9IGItPmF0dG51bSkKKwkJ cmV0dXJuIGZhbHNlOworCWlmIChhLT5jYXRlZ29yeSAhPSBiLT5jYXRlZ29yeSkKKwkJcmV0 dXJuIGZhbHNlOworCWlmIChhLT5jYXRlZ29yeSAhPSBHSU5fQ0FUX05PUk1fS0VZKQorCQly ZXR1cm4gdHJ1ZTsKIAogCS8qCi0JICogQWxsb2NhdGUgbWVtb3J5IGJ5IHJhdGhlciBiaWcg Y2h1bmtzIHRvIGRlY3JlYXNlIG92ZXJoZWFkLiAgV2UgaGF2ZSBubwotCSAqIG5lZWQgdG8g cmVjbGFpbSBSQlROb2RlcyBpbmRpdmlkdWFsbHksIHNvIHRoaXMgY29zdHMgbm90aGluZy4K KwkgKiBDb21wYXJlIHRoZSBhY3R1YWwga2V5IHZhbHVlcyB1c2luZyBpbWFnZSBlcXVhbGl0 eS4KKwkgKiBUaGlzIGlzIGNvcnJlY3QgYmVjYXVzZSB3ZSBkb24ndCB3YW50IHRvIGRlZHVw bGljYXRlIGF0IHRoaXMgcG9pbnQuCiAJICovCi0JaWYgKGFjY3VtLT5lbnRyeWFsbG9jYXRv ciA9PSBOVUxMIHx8IGFjY3VtLT5lYXNfdXNlZCA+PSBERUZfTkVOVFJZKQotCXsKLQkJYWNj dW0tPmVudHJ5YWxsb2NhdG9yID0gcGFsbG9jX2FycmF5KEdpbkVudHJ5QWNjdW11bGF0b3Is IERFRl9ORU5UUlkpOwotCQlhY2N1bS0+YWxsb2NhdGVkTWVtb3J5ICs9IEdldE1lbW9yeUNo dW5rU3BhY2UoYWNjdW0tPmVudHJ5YWxsb2NhdG9yKTsKLQkJYWNjdW0tPmVhc191c2VkID0g MDsKLQl9Ci0KLQkvKiBBbGxvY2F0ZSBuZXcgUkJUTm9kZSBmcm9tIGN1cnJlbnQgY2h1bmsg Ki8KLQllYSA9IGFjY3VtLT5lbnRyeWFsbG9jYXRvciArIGFjY3VtLT5lYXNfdXNlZDsKLQlh Y2N1bS0+ZWFzX3VzZWQrKzsKLQotCXJldHVybiAoUkJUTm9kZSAqKSBlYTsKKwlhdHQgPSBU dXBsZURlc2NDb21wYWN0QXR0cihhY2N1bS0+Z2luc3RhdGUtPm9yaWdUdXBkZXNjLCBhLT5h dHRudW0gLSAxKTsKKwlyZXR1cm4gZGF0dW1Jc0VxdWFsKGEtPmtleSwgYi0+a2V5LCBhdHQt PmF0dGJ5dmFsLCBhdHQtPmF0dGxlbik7CiB9CiAKKyNkZWZpbmUgU1RfU09SVCBzb3J0X2l0 ZW1wb2ludGVycworI2RlZmluZSBTVF9FTEVNRU5UX1RZUEUgSXRlbVBvaW50ZXJEYXRhCisj ZGVmaW5lIFNUX0NPTVBBUkUoYSwgYikgZ2luQ29tcGFyZUl0ZW1Qb2ludGVycyhhLCBiKQor I2RlZmluZSBTVF9TQ09QRSBzdGF0aWMKKyNkZWZpbmUgU1RfREVGSU5FCisjaW5jbHVkZSAi bGliL3NvcnRfdGVtcGxhdGUuaCIKKworI2RlZmluZSBTVF9TT1JUIHNvcnRfa2V5cworI2Rl ZmluZSBTVF9FTEVNRU5UX1RZUEUgR2luU29ydEVudHJ5CisjZGVmaW5lIFNUX0NPTVBBUkVf QVJHX1RZUEUgR2luU3RhdGUKKyNkZWZpbmUgU1RfQ09NUEFSRShhLCBiLCBzdGF0ZSkgZ2lu Q29tcGFyZUF0dEVudHJpZXMoc3RhdGUsIGEtPmhhc2hrZXkuYXR0bnVtLCBhLT5oYXNoa2V5 LmtleSwgYS0+aGFzaGtleS5jYXRlZ29yeSwgYi0+aGFzaGtleS5hdHRudW0sIGItPmhhc2hr ZXkua2V5LCBiLT5oYXNoa2V5LmNhdGVnb3J5KQorI2RlZmluZSBTVF9TQ09QRSBzdGF0aWMK KyNkZWZpbmUgU1RfREVGSU5FCisjaW5jbHVkZSAibGliL3NvcnRfdGVtcGxhdGUuaCIKKwog dm9pZAogZ2luSW5pdEJBKEJ1aWxkQWNjdW11bGF0b3IgKmFjY3VtKQogewogCS8qIGFjY3Vt LT5naW5zdGF0ZSBpcyBpbnRlbnRpb25hbGx5IG5vdCBzZXQgaGVyZSAqLwotCWFjY3VtLT5h bGxvY2F0ZWRNZW1vcnkgPSAwOwotCWFjY3VtLT5lbnRyeWFsbG9jYXRvciA9IE5VTEw7Ci0J YWNjdW0tPmVhc191c2VkID0gMDsKLQlhY2N1bS0+dHJlZSA9IHJidF9jcmVhdGUoc2l6ZW9m KEdpbkVudHJ5QWNjdW11bGF0b3IpLAotCQkJCQkJCSBjbXBFbnRyeUFjY3VtdWxhdG9yLAot CQkJCQkJCSBnaW5Db21iaW5lRGF0YSwKLQkJCQkJCQkgZ2luQWxsb2NFbnRyeUFjY3VtdWxh dG9yLAotCQkJCQkJCSBOVUxMLAkvKiBubyBmcmVlZnVuYyBuZWVkZWQgKi8KLQkJCQkJCQkg YWNjdW0pOworCWFjY3VtLT5oYXNoID0gZ2luYnVpbGRfY3JlYXRlKEN1cnJlbnRNZW1vcnlD b250ZXh0LCBERUZfTkVOVFJZLCBhY2N1bSk7CisJYWNjdW0tPmFsbG9jYXRlZE1lbW9yeSA9 IGFjY3VtLT5oYXNoLT5zaXplICogc2l6ZW9mKEdpbkhhc2hFbnRyeSk7CisJYWNjdW0tPnNv cnRlZF9lbnRyaWVzID0gTlVMTDsKKwlhY2N1bS0+bnVtX2VudHJpZXMgPSAwOworCWFjY3Vt LT5jdXJyZW50X3BvcyA9IDA7CiB9CiAKIC8qCkBAIC0xNDIsMTI0ICsxNTMsMTA5IEBAIGdl dERhdHVtQ29weShCdWlsZEFjY3VtdWxhdG9yICphY2N1bSwgT2Zmc2V0TnVtYmVyIGF0dG51 bSwgRGF0dW0gdmFsdWUpCiB9CiAKIC8qCi0gKiBGaW5kL3N0b3JlIG9uZSBlbnRyeSBmcm9t IGluZGV4ZWQgdmFsdWUuCisgKiBJbnNlcnQgb25lIGVudHJ5IGludG8gdGhlIGhhc2ggbWFw LgorICogSWYgdGhlIGtleSBhbHJlYWR5IGV4aXN0cywgYXBwZW5kIHRvIGl0cyBJdGVtUG9p bnRlciBhcnJheS4KKyAqIE90aGVyd2lzZSwgY3JlYXRlIGEgbmV3IGhhc2ggZW50cnkgd2l0 aCBhIG5ldyBJdGVtUG9pbnRlciBhcnJheS4KICAqLwogc3RhdGljIHZvaWQKIGdpbkluc2Vy dEJBRW50cnkoQnVpbGRBY2N1bXVsYXRvciAqYWNjdW0sCiAJCQkJIEl0ZW1Qb2ludGVyIGhl YXBwdHIsIE9mZnNldE51bWJlciBhdHRudW0sCiAJCQkJIERhdHVtIGtleSwgR2luTnVsbENh dGVnb3J5IGNhdGVnb3J5KQogewotCUdpbkVudHJ5QWNjdW11bGF0b3IgZWF0bXA7Ci0JR2lu RW50cnlBY2N1bXVsYXRvciAqZWE7Ci0JYm9vbAkJaXNOZXc7Ci0KLQkvKgotCSAqIEZvciB0 aGUgbW9tZW50LCBmaWxsIG9ubHkgdGhlIGZpZWxkcyBvZiBlYXRtcCB0aGF0IHdpbGwgYmUg bG9va2VkIGF0IGJ5Ci0JICogY21wRW50cnlBY2N1bXVsYXRvciBvciBnaW5Db21iaW5lRGF0 YS4KLQkgKi8KLQllYXRtcC5hdHRudW0gPSBhdHRudW07Ci0JZWF0bXAua2V5ID0ga2V5Owot CWVhdG1wLmNhdGVnb3J5ID0gY2F0ZWdvcnk7Ci0JLyogdGVtcG9yYXJpbHkgc2V0IHVwIHNp bmdsZS1lbnRyeSBpdGVtcG9pbnRlciBsaXN0ICovCi0JZWF0bXAubGlzdCA9IGhlYXBwdHI7 CisJR2luSGFzaEtleQloYXNoa2V5OworCUdpbkhhc2hFbnRyeSAqZW50cnk7CisJYm9vbAkJ Zm91bmQ7CisJdWludDY0CQlvbGRzaXplOworCisJaGFzaGtleS5hdHRudW0gPSBhdHRudW07 CisJaGFzaGtleS5jYXRlZ29yeSA9IGNhdGVnb3J5OworCWlmIChjYXRlZ29yeSA9PSBHSU5f Q0FUX05PUk1fS0VZKQorCQloYXNoa2V5LmtleSA9IGdldERhdHVtQ29weShhY2N1bSwgYXR0 bnVtLCBrZXkpOworCWVsc2UKKwkJaGFzaGtleS5rZXkgPSBrZXk7CiAKLQllYSA9IChHaW5F bnRyeUFjY3VtdWxhdG9yICopIHJidF9pbnNlcnQoYWNjdW0tPnRyZWUsIChSQlROb2RlICop ICZlYXRtcCwKLQkJCQkJCQkJCQkJJmlzTmV3KTsKKwlvbGRzaXplID0gYWNjdW0tPmhhc2gt PnNpemU7CisJZW50cnkgPSBnaW5idWlsZF9pbnNlcnQoYWNjdW0tPmhhc2gsIGhhc2hrZXks ICZmb3VuZCk7CiAKLQlpZiAoaXNOZXcpCisJaWYgKCFmb3VuZCkKIAl7Ci0JCS8qCi0JCSAq IEZpbmlzaCBpbml0aWFsaXppbmcgbmV3IHRyZWUgZW50cnksIGluY2x1ZGluZyBtYWtpbmcg cGVybWFuZW50Ci0JCSAqIGNvcGllcyBvZiB0aGUgZGF0dW0gKGlmIGl0J3Mgbm90IG51bGwp IGFuZCBpdGVtcG9pbnRlci4KLQkJICovCi0JCWlmIChjYXRlZ29yeSA9PSBHSU5fQ0FUX05P Uk1fS0VZKQotCQkJZWEtPmtleSA9IGdldERhdHVtQ29weShhY2N1bSwgYXR0bnVtLCBrZXkp OwotCQllYS0+bWF4Y291bnQgPSBERUZfTlBUUjsKLQkJZWEtPmNvdW50ID0gMTsKLQkJZWEt PnNob3VsZFNvcnQgPSBmYWxzZTsKLQkJZWEtPmxpc3QgPSBwYWxsb2NfYXJyYXkoSXRlbVBv aW50ZXJEYXRhLCBERUZfTlBUUik7Ci0JCWVhLT5saXN0WzBdID0gKmhlYXBwdHI7Ci0JCWFj Y3VtLT5hbGxvY2F0ZWRNZW1vcnkgKz0gR2V0TWVtb3J5Q2h1bmtTcGFjZShlYS0+bGlzdCk7 CisJCWVudHJ5LT5pdGVtcyA9IHBhbGxvY19hcnJheShJdGVtUG9pbnRlckRhdGEsIERFRl9J VEVNU19QRVJfS0VZKTsKKwkJZW50cnktPm51bUl0ZW1zID0gMDsKKwkJZW50cnktPmFsbG9j YXRlZEl0ZW1zID0gREVGX0lURU1TX1BFUl9LRVk7CisJCWFjY3VtLT5hbGxvY2F0ZWRNZW1v cnkgKz0gKGFjY3VtLT5oYXNoLT5zaXplIC0gb2xkc2l6ZSkgKiBzaXplb2YoR2luSGFzaEVu dHJ5KTsKKwkJYWNjdW0tPmFsbG9jYXRlZE1lbW9yeSArPSBHZXRNZW1vcnlDaHVua1NwYWNl KGVudHJ5LT5pdGVtcyk7CiAJfQotCWVsc2UKKworCWlmIChlbnRyeS0+bnVtSXRlbXMgPj0g ZW50cnktPmFsbG9jYXRlZEl0ZW1zKQogCXsKLQkJLyoKLQkJICogZ2luQ29tYmluZURhdGEg ZGlkIGV2ZXJ5dGhpbmcgbmVlZGVkLgotCQkgKi8KKwkJdWludDMyCQluZXdfYWxsb2NhdGVk OworCisJCWlmIChlbnRyeS0+YWxsb2NhdGVkSXRlbXMgPiBVSU5UMzJfTUFYIC8gMikKKwkJ CWVyZXBvcnQoRVJST1IsCisJCQkJCShlcnJjb2RlKEVSUkNPREVfUFJPR1JBTV9MSU1JVF9F WENFRURFRCksCisJCQkJCSBlcnJtc2coInRvbyBtYW55IEdJTiBpdGVtIHBvaW50ZXJzIGZv ciBhIHNpbmdsZSBrZXkiKSwKKwkJCQkJIGVycmhpbnQoIlJlZHVjZSBcIm1haW50ZW5hbmNl X3dvcmtfbWVtXCIuIikpKTsKKworCQlhY2N1bS0+YWxsb2NhdGVkTWVtb3J5IC09IEdldE1l bW9yeUNodW5rU3BhY2UoZW50cnktPml0ZW1zKTsKKwkJbmV3X2FsbG9jYXRlZCA9IGVudHJ5 LT5hbGxvY2F0ZWRJdGVtcyAqIDI7CisJCWVudHJ5LT5pdGVtcyA9IHJlcGFsbG9jX2h1Z2Uo ZW50cnktPml0ZW1zLCBzaXplb2YoSXRlbVBvaW50ZXJEYXRhKSAqIG5ld19hbGxvY2F0ZWQp OworCQllbnRyeS0+YWxsb2NhdGVkSXRlbXMgPSBuZXdfYWxsb2NhdGVkOworCQlhY2N1bS0+ YWxsb2NhdGVkTWVtb3J5ICs9IEdldE1lbW9yeUNodW5rU3BhY2UoZW50cnktPml0ZW1zKTsK IAl9CisKKwllbnRyeS0+aXRlbXNbZW50cnktPm51bUl0ZW1zKytdID0gKmhlYXBwdHI7CiB9 CiAKLS8qCi0gKiBJbnNlcnQgdGhlIGVudHJpZXMgZm9yIG9uZSBoZWFwIHBvaW50ZXIuCi0g KgotICogU2luY2UgdGhlIGVudHJpZXMgYXJlIGJlaW5nIGluc2VydGVkIGludG8gYSBiYWxh bmNlZCBiaW5hcnkgdHJlZSwgeW91Ci0gKiBtaWdodCB0aGluayB0aGF0IHRoZSBvcmRlciBv ZiBpbnNlcnRpb24gd291bGRuJ3QgYmUgY3JpdGljYWwsIGJ1dCBpdCB0dXJucwotICogb3V0 IHRoYXQgaW5zZXJ0aW5nIHRoZSBlbnRyaWVzIGluIHNvcnRlZCBvcmRlciByZXN1bHRzIGlu IGEgbG90IG9mCi0gKiByZWJhbGFuY2luZyBvcGVyYXRpb25zIGFuZCBpcyBzbG93LiAgVG8g cHJldmVudCB0aGlzLCB3ZSBhdHRlbXB0IHRvIGluc2VydAotICogdGhlIG5vZGVzIGluIGFu IG9yZGVyIHRoYXQgd2lsbCBwcm9kdWNlIGEgbmVhcmx5LWJhbGFuY2VkIHRyZWUgaWYgdGhl IGlucHV0Ci0gKiBpcyBpbiBmYWN0IHNvcnRlZC4KLSAqCi0gKiBXZSBkbyB0aGlzIGFzIGZv bGxvd3MuICBGaXJzdCwgd2UgaW1hZ2luZSB0aGF0IHdlIGhhdmUgYW4gYXJyYXkgd2hvc2Ug c2l6ZQotICogaXMgdGhlIHNtYWxsZXN0IHBvd2VyIG9mIHR3byBncmVhdGVyIHRoYW4gb3Ig ZXF1YWwgdG8gdGhlIGFjdHVhbCBhcnJheQotICogc2l6ZS4gIFNlY29uZCwgd2UgaW5zZXJ0 IHRoZSBtaWRkbGUgZW50cnkgb2Ygb3VyIHZpcnR1YWwgYXJyYXkgaW50byB0aGUKLSAqIHRy ZWU7IHRoZW4sIHdlIGluc2VydCB0aGUgbWlkZGxlcyBvZiBlYWNoIGhhbGYgb2Ygb3VyIHZp cnR1YWwgYXJyYXksIHRoZW4KLSAqIG1pZGRsZXMgb2YgcXVhcnRlcnMsIGV0Yy4KLSAqLwog dm9pZAogZ2luSW5zZXJ0QkFFbnRyaWVzKEJ1aWxkQWNjdW11bGF0b3IgKmFjY3VtLAogCQkJ CSAgIEl0ZW1Qb2ludGVyIGhlYXBwdHIsIE9mZnNldE51bWJlciBhdHRudW0sCiAJCQkJICAg RGF0dW0gKmVudHJpZXMsIEdpbk51bGxDYXRlZ29yeSAqY2F0ZWdvcmllcywKIAkJCQkgICBp bnQzMiBuZW50cmllcykKIHsKLQl1aW50MzIJCXN0ZXAgPSBuZW50cmllczsKLQogCWlmIChu ZW50cmllcyA8PSAwKQogCQlyZXR1cm47CiAKIAlBc3NlcnQoSXRlbVBvaW50ZXJJc1ZhbGlk KGhlYXBwdHIpICYmIGF0dG51bSA+PSBGaXJzdE9mZnNldE51bWJlcik7CiAKLQkvKgotCSAq IHN0ZXAgd2lsbCBjb250YWluIGxhcmdlc3QgcG93ZXIgb2YgMiBhbmQgPD0gbmVudHJpZXMK LQkgKi8KLQlzdGVwIHw9IChzdGVwID4+IDEpOwotCXN0ZXAgfD0gKHN0ZXAgPj4gMik7Ci0J c3RlcCB8PSAoc3RlcCA+PiA0KTsKLQlzdGVwIHw9IChzdGVwID4+IDgpOwotCXN0ZXAgfD0g KHN0ZXAgPj4gMTYpOwotCXN0ZXAgPj49IDE7Ci0Jc3RlcCsrOwotCi0Jd2hpbGUgKHN0ZXAg PiAwKQotCXsKLQkJaW50CQkJaTsKLQotCQlmb3IgKGkgPSBzdGVwIC0gMTsgaSA8IG5lbnRy aWVzICYmIGkgPj0gMDsgaSArPSBzdGVwIDw8IDEgLyogKjIgKi8gKQotCQkJZ2luSW5zZXJ0 QkFFbnRyeShhY2N1bSwgaGVhcHB0ciwgYXR0bnVtLAotCQkJCQkJCSBlbnRyaWVzW2ldLCBj YXRlZ29yaWVzW2ldKTsKLQotCQlzdGVwID4+PSAxOwkJCQkvKiAvMiAqLwotCX0KKwlmb3Ig KGludCBpID0gMDsgaSA8IG5lbnRyaWVzOyBpKyspCisJCWdpbkluc2VydEJBRW50cnkoYWNj dW0sIGhlYXBwdHIsIGF0dG51bSwgZW50cmllc1tpXSwgY2F0ZWdvcmllc1tpXSk7CiB9CiAK LXN0YXRpYyBpbnQKLXFzb3J0Q29tcGFyZUl0ZW1Qb2ludGVycyhjb25zdCB2b2lkICphLCBj b25zdCB2b2lkICpiKQotewotCWludAkJCXJlcyA9IGdpbkNvbXBhcmVJdGVtUG9pbnRlcnMo KGNvbnN0IEl0ZW1Qb2ludGVyRGF0YSAqKSBhLCAoY29uc3QgSXRlbVBvaW50ZXJEYXRhICop IGIpOwotCi0JLyogQXNzZXJ0IHRoYXQgdGhlcmUgYXJlIG5vIGVxdWFsIGl0ZW0gcG9pbnRl cnMgYmVpbmcgc29ydGVkICovCi0JQXNzZXJ0KHJlcyAhPSAwKTsKLQlyZXR1cm4gcmVzOwot fQotCi0vKiBQcmVwYXJlIHRvIHJlYWQgb3V0IHRoZSByYnRyZWUgY29udGVudHMgdXNpbmcg Z2luR2V0QkFFbnRyeSAqLworLyogUHJlcGFyZSB0byByZWFkIG91dCB0aGUgaGFzaCB0YWJs ZSBjb250ZW50cyB1c2luZyBnaW5HZXRCQUVudHJ5ICovCiB2b2lkCiBnaW5CZWdpbkJBU2Nh bihCdWlsZEFjY3VtdWxhdG9yICphY2N1bSkKIHsKLQlyYnRfYmVnaW5faXRlcmF0ZShhY2N1 bS0+dHJlZSwgTGVmdFJpZ2h0V2FsaywgJmFjY3VtLT50cmVlX3dhbGspOworCWdpbmJ1aWxk X2l0ZXJhdG9yIGl0ZXI7CisJR2luSGFzaEVudHJ5ICplbnRyeTsKKwl1aW50MzIJCWkgPSAw OworCisJYWNjdW0tPm51bV9lbnRyaWVzID0gYWNjdW0tPmhhc2gtPm1lbWJlcnM7CisJYWNj dW0tPmN1cnJlbnRfcG9zID0gMDsKKworCWlmIChhY2N1bS0+bnVtX2VudHJpZXMgPT0gMCkK KwkJcmV0dXJuOworCisJYWNjdW0tPnNvcnRlZF9lbnRyaWVzID0gcGFsbG9jX2FycmF5KEdp blNvcnRFbnRyeSwgYWNjdW0tPm51bV9lbnRyaWVzKTsKKwlnaW5idWlsZF9zdGFydF9pdGVy YXRlKGFjY3VtLT5oYXNoLCAmaXRlcik7CisKKwl3aGlsZSAoKGVudHJ5ID0gZ2luYnVpbGRf aXRlcmF0ZShhY2N1bS0+aGFzaCwgJml0ZXIpKSAhPSBOVUxMKQorCXsKKwkJR2luU29ydEVu dHJ5ICpzZSA9ICZhY2N1bS0+c29ydGVkX2VudHJpZXNbaV07CisJCXNvcnRfaXRlbXBvaW50 ZXJzKGVudHJ5LT5pdGVtcywgZW50cnktPm51bUl0ZW1zKTsKKworCQlzZS0+aGFzaGtleSA9 IGVudHJ5LT5oYXNoa2V5OworCQlzZS0+aXRlbXMgPSBlbnRyeS0+aXRlbXM7CisJCXNlLT5u dW1JdGVtcyA9IGVudHJ5LT5udW1JdGVtczsKKwkJaSsrOworCX0KKworCUFzc2VydChpID09 IGFjY3VtLT5udW1fZW50cmllcyk7CisJc29ydF9rZXlzKGFjY3VtLT5zb3J0ZWRfZW50cmll cywgYWNjdW0tPm51bV9lbnRyaWVzLCBhY2N1bS0+Z2luc3RhdGUpOworCWFjY3VtLT5jdXJy ZW50X3BvcyA9IDA7CiB9CiAKIC8qCi0gKiBHZXQgdGhlIG5leHQgZW50cnkgaW4gc2VxdWVu Y2UgZnJvbSB0aGUgQnVpbGRBY2N1bXVsYXRvcidzIHJidHJlZS4KKyAqIEdldCB0aGUgbmV4 dCBlbnRyeSBpbiBzZXF1ZW5jZSBmcm9tIHRoZSBCdWlsZEFjY3VtdWxhdG9yJ3Mgc29ydGVk IGhhc2ggZW50cmllcy4KICAqIFRoaXMgY29uc2lzdHMgb2YgYSBzaW5nbGUga2V5IGRhdHVt IGFuZCBhIGxpc3QgKGFycmF5KSBvZiBvbmUgb3IgbW9yZQogICogaGVhcCBUSURzIGluIHdo aWNoIHRoYXQga2V5IGlzIGZvdW5kLiAgVGhlIGxpc3QgaXMgZ3VhcmFudGVlZCBzb3J0ZWQu CiAgKi8KQEAgLTI2OCwyNSArMjY0LDE4IEBAIGdpbkdldEJBRW50cnkoQnVpbGRBY2N1bXVs YXRvciAqYWNjdW0sCiAJCQkgIE9mZnNldE51bWJlciAqYXR0bnVtLCBEYXR1bSAqa2V5LCBH aW5OdWxsQ2F0ZWdvcnkgKmNhdGVnb3J5LAogCQkJICB1aW50MzIgKm4pCiB7Ci0JR2luRW50 cnlBY2N1bXVsYXRvciAqZW50cnk7Ci0JSXRlbVBvaW50ZXJEYXRhICpsaXN0OwotCi0JZW50 cnkgPSAoR2luRW50cnlBY2N1bXVsYXRvciAqKSByYnRfaXRlcmF0ZSgmYWNjdW0tPnRyZWVf d2Fsayk7CisJR2luU29ydEVudHJ5ICplbnRyeTsKIAotCWlmIChlbnRyeSA9PSBOVUxMKQor CWlmIChhY2N1bS0+Y3VycmVudF9wb3MgPj0gYWNjdW0tPm51bV9lbnRyaWVzKQogCQlyZXR1 cm4gTlVMTDsJCQkvKiBubyBtb3JlIGVudHJpZXMgKi8KIAotCSphdHRudW0gPSBlbnRyeS0+ YXR0bnVtOwotCSprZXkgPSBlbnRyeS0+a2V5OwotCSpjYXRlZ29yeSA9IGVudHJ5LT5jYXRl Z29yeTsKLQlsaXN0ID0gZW50cnktPmxpc3Q7Ci0JKm4gPSBlbnRyeS0+Y291bnQ7Ci0KLQlB c3NlcnQobGlzdCAhPSBOVUxMICYmIGVudHJ5LT5jb3VudCA+IDApOworCWVudHJ5ID0gJmFj Y3VtLT5zb3J0ZWRfZW50cmllc1thY2N1bS0+Y3VycmVudF9wb3NdOworCWFjY3VtLT5jdXJy ZW50X3BvcysrOwogCi0JaWYgKGVudHJ5LT5zaG91bGRTb3J0ICYmIGVudHJ5LT5jb3VudCA+ IDEpCi0JCXFzb3J0KGxpc3QsIGVudHJ5LT5jb3VudCwgc2l6ZW9mKEl0ZW1Qb2ludGVyRGF0 YSksCi0JCQkgIHFzb3J0Q29tcGFyZUl0ZW1Qb2ludGVycyk7CisJKmF0dG51bSA9IGVudHJ5 LT5oYXNoa2V5LmF0dG51bTsKKwkqa2V5ID0gZW50cnktPmhhc2hrZXkua2V5OworCSpjYXRl Z29yeSA9IGVudHJ5LT5oYXNoa2V5LmNhdGVnb3J5OworCSpuID0gZW50cnktPm51bUl0ZW1z OwogCi0JcmV0dXJuIGxpc3Q7CisJcmV0dXJuIGVudHJ5LT5pdGVtczsKIH0KZGlmZiAtLWdp dCBhL3NyYy9pbmNsdWRlL2FjY2Vzcy9naW5fcHJpdmF0ZS5oIGIvc3JjL2luY2x1ZGUvYWNj ZXNzL2dpbl9wcml2YXRlLmgKaW5kZXggNjcyNWVlMjgzOWYuLjM5YzAxNWIxMzU1IDEwMDY0 NAotLS0gYS9zcmMvaW5jbHVkZS9hY2Nlc3MvZ2luX3ByaXZhdGUuaAorKysgYi9zcmMvaW5j bHVkZS9hY2Nlc3MvZ2luX3ByaXZhdGUuaApAQCAtMTgsNyArMTgsNiBAQAogI2luY2x1ZGUg ImNvbW1vbi9pbnQuaCIKICNpbmNsdWRlICJjYXRhbG9nL3BnX2FtX2QuaCIKICNpbmNsdWRl ICJmbWdyLmgiCi0jaW5jbHVkZSAibGliL3JidHJlZS5oIgogI2luY2x1ZGUgIm5vZGVzL3Rp ZGJpdG1hcC5oIgogI2luY2x1ZGUgInN0b3JhZ2UvYnVmbWdyLmgiCiAKQEAgLTQyMCwyNiAr NDE5LDE1IEBAIGV4dGVybiB2b2lkIGdpbmFkanVzdG1lbWJlcnMoT2lkIG9wZmFtaWx5b2lk LAogCQkJCQkJCSBMaXN0ICpmdW5jdGlvbnMpOwogCiAvKiBnaW5idWxrLmMgKi8KLXR5cGVk ZWYgc3RydWN0IEdpbkVudHJ5QWNjdW11bGF0b3IKLXsKLQlSQlROb2RlCQlyYnRub2RlOwot CURhdHVtCQlrZXk7Ci0JR2luTnVsbENhdGVnb3J5IGNhdGVnb3J5OwotCU9mZnNldE51bWJl ciBhdHRudW07Ci0JYm9vbAkJc2hvdWxkU29ydDsKLQlJdGVtUG9pbnRlckRhdGEgKmxpc3Q7 Ci0JdWludDMyCQltYXhjb3VudDsJCS8qIGFsbG9jYXRlZCBzaXplIG9mIGxpc3RbXSAqLwot CXVpbnQzMgkJY291bnQ7CQkJLyogY3VycmVudCBudW1iZXIgb2YgbGlzdFtdIGVudHJpZXMg Ki8KLX0gR2luRW50cnlBY2N1bXVsYXRvcjsKIAogdHlwZWRlZiBzdHJ1Y3QKIHsKLQlHaW5T dGF0ZSAgICpnaW5zdGF0ZTsKLQlTaXplCQlhbGxvY2F0ZWRNZW1vcnk7Ci0JR2luRW50cnlB Y2N1bXVsYXRvciAqZW50cnlhbGxvY2F0b3I7Ci0JdWludDMyCQllYXNfdXNlZDsKLQlSQlRy ZWUJICAgKnRyZWU7Ci0JUkJUcmVlSXRlcmF0b3IgdHJlZV93YWxrOworCUdpblN0YXRlICoJ CQkJZ2luc3RhdGU7CisJU2l6ZQkJCQkJYWxsb2NhdGVkTWVtb3J5OworCXN0cnVjdCBnaW5i dWlsZF9oYXNoICoJaGFzaDsKKwlzdHJ1Y3QgR2luU29ydEVudHJ5ICoJc29ydGVkX2VudHJp ZXM7CisJdWludDMyCQkJCQludW1fZW50cmllczsKKwl1aW50MzIJCQkJCWN1cnJlbnRfcG9z OwogfSBCdWlsZEFjY3VtdWxhdG9yOwogCiBleHRlcm4gdm9pZCBnaW5Jbml0QkEoQnVpbGRB Y2N1bXVsYXRvciAqYWNjdW0pOwotLSAKMi41MS4wCgo= --------------0Z0AtKWMsTOAeFv0hcZKxpd4 Content-Type: text/x-patch; charset=UTF-8; name="v7-0002-Optimize-generate_trgm-with-radix-sort.patch" Content-Disposition: attachment; filename="v7-0002-Optimize-generate_trgm-with-radix-sort.patch" Content-Transfer-Encoding: base64 RnJvbSBlYjhmNmM5MDE1MmNlOTc2MTYxYjA0YzlkNTQwZjMzOGEwNjQwYjJhIE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBEYXZpZCBHZWllciA8Z2VpZGF2LnBnQGdtYWlsLmNv bT4KRGF0ZTogVHVlLCAxMSBOb3YgMjAyNSAxMzoxODo1OSArMDEwMApTdWJqZWN0OiBbUEFU Q0ggdjcgMi8zXSBPcHRpbWl6ZSBnZW5lcmF0ZV90cmdtKCkgd2l0aCByYWRpeCBzb3J0Cgot LS0KIGNvbnRyaWIvcGdfdHJnbS90cmdtX29wLmMgfCA1OSArKysrKysrKysrKysrKysrKysr KysrKysrKysrKysrKystLS0tLS0KIDEgZmlsZSBjaGFuZ2VkLCA1MSBpbnNlcnRpb25zKCsp LCA4IGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL2NvbnRyaWIvcGdfdHJnbS90cmdtX29w LmMgYi9jb250cmliL3BnX3RyZ20vdHJnbV9vcC5jCmluZGV4IDNmZDA4Nzg1MmU3Li5mNWRj NTI0MmM3ZCAxMDA2NDQKLS0tIGEvY29udHJpYi9wZ190cmdtL3RyZ21fb3AuYworKysgYi9j b250cmliL3BnX3RyZ20vdHJnbV9vcC5jCkBAIC0yMjYsMTMgKzIyNiw1NiBAQCBDTVBUUkdN X0NIT09TRShjb25zdCB2b2lkICphLCBjb25zdCB2b2lkICpiKQogCXJldHVybiBDTVBUUkdN KGEsIGIpOwogfQogCi0jZGVmaW5lIFNUX1NPUlQgdHJpZ3JhbV9xc29ydF9zaWduZWQKLSNk ZWZpbmUgU1RfRUxFTUVOVF9UWVBFX1ZPSUQKLSNkZWZpbmUgU1RfQ09NUEFSRShhLCBiKSBD TVBUUkdNX1NJR05FRChhLCBiKQotI2RlZmluZSBTVF9TQ09QRSBzdGF0aWMKLSNkZWZpbmUg U1RfREVGSU5FCi0jZGVmaW5lIFNUX0RFQ0xBUkUKLSNpbmNsdWRlICJsaWIvc29ydF90ZW1w bGF0ZS5oIgorLyoKKyAqIE5lZWRlZCB0byBwcm9wZXJseSBoYW5kbGUgbmVnYXRpdmUgbnVt YmVycyBpbiBjYXNlIGNoYXIgaXMgc2lnbmVkLgorICovCitzdGF0aWMgaW5saW5lIHVuc2ln bmVkIGNoYXIgRmxpcFNpZ24oY2hhciB4KQoreworCXJldHVybiB4XjB4ODA7Cit9CisKK3N0 YXRpYyB2b2lkIHJhZGl4X3NvcnRfdHJpZ3JhbXNfc2lnbmVkKHRyZ20gKnRyZywgaW50IGNv dW50KQoreworCXRyZ20gKmJ1ZmZlciA9IHBhbGxvY19hcnJheSh0cmdtLCBjb3VudCk7CisJ dHJnbSAqc3RhcnRzWzI1Nl07CisJdHJnbSAqZnJvbSA9IHRyZzsKKwl0cmdtICp0byA9IGJ1 ZmZlcjsKKwlpbnQgZnJlcXNbM11bMjU2XTsKKworCS8qCisJICogQ29tcHV0ZSBmcmVxdWVu Y2llcyB0byBwYXJ0aXRpb24gdGhlIGJ1ZmZlci4KKwkgKi8KKwltZW1zZXQoZnJlcXMsIDAs IHNpemVvZihmcmVxcykpOworCisJZm9yIChpbnQgaT0wOyBpPGNvdW50OyBpKyspCisJCWZv ciAoaW50IGo9MDsgajwzOyBqKyspCisJCQlmcmVxc1tqXVtGbGlwU2lnbih0cmdbaV1bal0p XSsrOworCisJLyoKKwkgKiBEbyB0aGUgc29ydGluZy4gU3RhcnQgd2l0aCBsYXN0IGNoYXJh Y3RlciBiZWNhdXNlIHRoYXQncyB0aGUgaXMgIkxTQiIKKwkgKiBpbiBhIHRyaWdyYW0uIEF2 b2lkIHVubmVjZXNzYXJ5IGNvcGllcyBieSBwaW5nLXBvbmdpbmcgYmV0d2VlbiB0aGUgYnVm ZmVycy4KKwkgKi8KKwlmb3IgKGludCBpPTI7IGk+PTA7IGktLSkKKwl7CisJCXRyZ20gKm9s ZF9mcm9tID0gZnJvbTsKKwkJdHJnbSAqbmV4dCA9IHRvOworCisJCWZvciAoaW50IGo9MDsg ajwyNTY7IGorKykKKwkJeworCQkJc3RhcnRzW2pdID0gbmV4dDsKKwkJCW5leHQgKz0gZnJl cXNbaV1bal07CisJCX0KKworCQlmb3IgKGludCBqPTA7IGo8Y291bnQ7IGorKykKKwkJCW1l bWNweShzdGFydHNbRmxpcFNpZ24oZnJvbVtqXVtpXSldKyssIGZyb21bal0sIHNpemVvZih0 cmdtKSk7CisKKwkJZnJvbSA9IHRvOworCQl0byA9IG9sZF9mcm9tOworCX0KKworCW1lbWNw eSh0cmcsIGJ1ZmZlciwgc2l6ZW9mKHRyZ20pICogY291bnQpOworCXBmcmVlKGJ1ZmZlcik7 Cit9CiAKICNkZWZpbmUgU1RfU09SVCB0cmlncmFtX3Fzb3J0X3Vuc2lnbmVkCiAjZGVmaW5l IFNUX0VMRU1FTlRfVFlQRV9WT0lECkBAIC0yNDcsNyArMjkwLDcgQEAgc3RhdGljIHZvaWQK IHRyaWdyYW1fcXNvcnQodHJnbSAqYXJyYXksIHNpemVfdCBuKQogewogCWlmIChHZXREZWZh dWx0Q2hhclNpZ25lZG5lc3MoKSkKLQkJdHJpZ3JhbV9xc29ydF9zaWduZWQoYXJyYXksIG4s IHNpemVvZih0cmdtKSk7CisJCXJhZGl4X3NvcnRfdHJpZ3JhbXNfc2lnbmVkKGFycmF5LCBu KTsKIAllbHNlCiAJCXRyaWdyYW1fcXNvcnRfdW5zaWduZWQoYXJyYXksIG4sIHNpemVvZih0 cmdtKSk7CiB9Ci0tIAoyLjUxLjAKCg== --------------0Z0AtKWMsTOAeFv0hcZKxpd4 Content-Type: text/x-patch; charset=UTF-8; name="v7-0001-Make-btint4cmp-branchless.patch" Content-Disposition: attachment; filename="v7-0001-Make-btint4cmp-branchless.patch" Content-Transfer-Encoding: base64 RnJvbSBhYmVlYTE1OGIwZjU4MzQ0YWJiMDg1ZjkxNGQ1Y2M1ZjgwNDM5NWM4IE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBEYXZpZCBHZWllciA8Z2VpZGF2LnBnQGdtYWlsLmNv bT4KRGF0ZTogTW9uLCAxMCBOb3YgMjAyNSAxNTo0MDoxMSArMDEwMApTdWJqZWN0OiBbUEFU Q0ggdjcgMS8zXSBNYWtlIGJ0aW50NGNtcCgpIGJyYW5jaGxlc3MKCi0tLQogc3JjL2JhY2tl bmQvYWNjZXNzL25idHJlZS9uYnRjb21wYXJlLmMgfCA4ICsrLS0tLS0tCiAxIGZpbGUgY2hh bmdlZCwgMiBpbnNlcnRpb25zKCspLCA2IGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL3Ny Yy9iYWNrZW5kL2FjY2Vzcy9uYnRyZWUvbmJ0Y29tcGFyZS5jIGIvc3JjL2JhY2tlbmQvYWNj ZXNzL25idHJlZS9uYnRjb21wYXJlLmMKaW5kZXggMWQzNDMzNzdlOTguLmFjMTZlM2Q5OTNk IDEwMDY0NAotLS0gYS9zcmMvYmFja2VuZC9hY2Nlc3MvbmJ0cmVlL25idGNvbXBhcmUuYwor KysgYi9zcmMvYmFja2VuZC9hY2Nlc3MvbmJ0cmVlL25idGNvbXBhcmUuYwpAQCAtNjEsNiAr NjEsNyBAQAogI2luY2x1ZGUgInV0aWxzL2ZtZ3Jwcm90b3MuaCIKICNpbmNsdWRlICJ1dGls cy9za2lwc3VwcG9ydC5oIgogI2luY2x1ZGUgInV0aWxzL3NvcnRzdXBwb3J0LmgiCisjaW5j bHVkZSAiY29tbW9uL2ludC5oIgogCiAjaWZkZWYgU1RSRVNTX1NPUlRfSU5UX01JTgogI2Rl ZmluZSBBX0xFU1NfVEhBTl9CCQlJTlRfTUlOCkBAIC0yMDMsMTIgKzIwNCw3IEBAIGJ0aW50 NGNtcChQR19GVU5DVElPTl9BUkdTKQogCWludDMyCQlhID0gUEdfR0VUQVJHX0lOVDMyKDAp OwogCWludDMyCQliID0gUEdfR0VUQVJHX0lOVDMyKDEpOwogCi0JaWYgKGEgPiBiKQotCQlQ R19SRVRVUk5fSU5UMzIoQV9HUkVBVEVSX1RIQU5fQik7Ci0JZWxzZSBpZiAoYSA9PSBiKQot CQlQR19SRVRVUk5fSU5UMzIoMCk7Ci0JZWxzZQotCQlQR19SRVRVUk5fSU5UMzIoQV9MRVNT X1RIQU5fQik7CisJUEdfUkVUVVJOX0lOVDMyKHBnX2NtcF9zMzIoYSwgYikpOwogfQogCiBE YXR1bQotLSAKMi41MS4wCgo= --------------0Z0AtKWMsTOAeFv0hcZKxpd4--