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 1rwTxb-0025JD-JU for pgsql-hackers@arkaria.postgresql.org; Mon, 15 Apr 2024 21:33:56 +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 1rwTxa-00G3gl-Am for pgsql-hackers@arkaria.postgresql.org; Mon, 15 Apr 2024 21:33:54 +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 1rwTxY-00G3gd-Bi for pgsql-hackers@lists.postgresql.org; Mon, 15 Apr 2024 21:33:54 +0000 Received: from fhigh5-smtp.messagingengine.com ([103.168.172.156]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1rwTxU-0031wq-NT for pgsql-hackers@postgresql.org; Mon, 15 Apr 2024 21:33:51 +0000 Received: from compute6.internal (compute6.nyi.internal [10.202.2.47]) by mailfhigh.nyi.internal (Postfix) with ESMTP id EC4E81140181 for ; Mon, 15 Apr 2024 17:33:46 -0400 (EDT) Received: from imap48 ([10.202.2.98]) by compute6.internal (MEProxy); Mon, 15 Apr 2024 17:33:46 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=compiler.org; h= cc:content-type:content-type:date:date:from:from:in-reply-to :message-id:mime-version:reply-to:subject:subject:to:to; s=fm2; t=1713216826; x=1713303226; bh=RCQrGK1ul2znmPuRICamqh169LbYHtM4 ddsM8Hufnew=; b=j9TgSCwHCe9O+PaZz7M1rkoJ1yE5XLk0QsR43RoojrfkadWV naFoj4uJfWOoqzh687kmcCuBt1ZyP6t+NAcWGR/EnooxCpdXlhDEAPFOSqzZwIjy wF+6+G8Vg0kMtw1Y9XJebTPF+zvXi8+VOsEIPik9QLY20rI06HO47Qoejq/K8e1N UwfLEWM+lU2FjtP4Sy70doKAo32wlhhpPPW/pGDWVkIKQnotiuqpFjdq4a8MHe0b /u20EfxQ5PMFA6lAm+qTuK1uMamAWfKGn9IHmSPQpanCggw4x93LzE6VxBFg37eH hdBqi6mibGHgOzoL9E+y4Bt5t6nLJ1uutWRsHg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:message-id :mime-version:reply-to:subject:subject:to:to:x-me-proxy :x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=fm2; t= 1713216826; x=1713303226; bh=RCQrGK1ul2znmPuRICamqh169LbYHtM4dds M8Hufnew=; b=Q2p2bONrVJnjis9vVQjXM+piO+DpNNjzIwKs3RKtz+3f6I1dudv KwxqCkm7RlTG+45YEIZfWekUr7c+8a9P5uU57LzNOmB+MgLNIwTJRGkoyPV02jog 7Bfh6u82wchZ8/qvBJZPxN5dN/gii0LM6l60v7+4xBAmPFsLc9uuNoH2adVgmJlb Z9FVECKC1i4x5hvPuawzXeMpLxez/T3O9Chip5z5y+hroxlJ1Q57A+V4PwW6Iz6H uzbRw/AUem7OESzyzqSDq8SPh71hkhcAZ6J+k9PFyRyfCo4JcfAFhk6yJVxPTKuY l+QEGh8PH/rrRdrrqRqUYMoVeVpYRdY9L3g== X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrudejvddgudeifecutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecunecujfgurhepofgfggfkfffhvffutgesmhdtre erreerjeenucfhrhhomhepfdflohgvlhculfgrtghosghsohhnfdcuoehjohgvlhestgho mhhpihhlvghrrdhorhhgqeenucggtffrrghtthgvrhhnpeevteefleejgfetjeekieevff eljeelteeuveeufedvueetveefiedtgeeuvdefteenucffohhmrghinhepghhithhhuhgs uhhsvghrtghonhhtvghnthdrtghomhenucevlhhushhtvghrufhiiigvpedtnecurfgrrh grmhepmhgrihhlfhhrohhmpehjohgvlhestghomhhpihhlvghrrdhorhhg X-ME-Proxy: Feedback-ID: ic6394509:Fastmail Received: by mailuser.nyi.internal (Postfix, from userid 501) id 7185E31A0065; Mon, 15 Apr 2024 17:33:46 -0400 (EDT) X-Mailer: MessagingEngine.com Webmail Interface User-Agent: Cyrus-JMAP/3.11.0-alpha0-379-gabd37849b7-fm-20240408.001-gabd37849 MIME-Version: 1.0 Message-Id: <7f95163f-2019-4416-a042-6e2141619e5d@app.fastmail.com> Date: Mon, 15 Apr 2024 23:33:01 +0200 From: "Joel Jacobson" To: pgsql-hackers Subject: Optimize numeric.c mul_var() using the Karatsuba algorithm Content-Type: multipart/mixed; boundary=1fe2dc603a1541548bd694b5363b4c7c List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --1fe2dc603a1541548bd694b5363b4c7c Content-Type: text/plain;charset=utf-8 Content-Transfer-Encoding: quoted-printable Hi, This patch introduces the Karatsuba algorithm to speed up multiplication operations in numeric.c, where the operands have many digits. It is implemented via a new conditional in mul_var() that determines whe= ther the sizes of the factors are sufficiently large to justify its use. This= decision is non-trivial due to its recursive nature, depending on the size and ra= tio of the factors. Moreover, the optimal threshold varies across different architectures. This benefits all users of mul_var() in numeric.c, such as: numeric_mul() numeric_lcm() numeric_fac() int64_div_fast_to_numeric() mod_var() div_mod_var() sqrt_var() exp_var() ln_var() power_var() The macro KARATSUBA_CONDITION(var1ndigits, var2ndigits) is responsible o= f this decision. It is deliberately conservative to prevent performance regress= ions on the tested architectures while maximizing potential gains and maintaining simplicity. Patches: 1. mul_var-karatsuba.patch Modifies mul_var() to use the Karatsuba-functions for multiplying larger numerical factors. 2. mul_var-karatsuba-benchmark.patch Introduces numeric_mul_karatsuba() and mul_var_karatsuba() alongside the existing numeric_mul() and mul_var() functions. This enables benchmark comparisons between the original multiplication m= ethod and the Karatsuba-optimized version. Some benchmark numbers, tested on Intel Core i9-14900K: Helper-function to generate numeric of given ndigits, using the new random(min numeric, max numeric): CREATE OR REPLACE FUNCTION random_ndigits(ndigits INT) RETURNS NUMERIC A= S $$ SELECT random( ('1000'||repeat('0000',ndigits-1))::numeric, (repeat('9999',ndigits))::numeric ) $$ LANGUAGE sql; Benchmark equal factor sizes, 16384 x 16384 ndigits: SELECT random_ndigits(16384) * random_ndigits(16384) > 0; Time: 33.990 ms Time: 33.961 ms Time: 34.183 ms SELECT numeric_mul_karatsuba(random_ndigits(16384), random_ndigits(16384= )) > 0; Time: 17.621 ms Time: 17.209 ms Time: 16.444 ms Benchmark equal factor sizes, 8192 x 8192 ndigits: SELECT random_ndigits(8192) * random_ndigits(8192) > 0; Time: 12.568 ms Time: 12.563 ms Time: 12.701 ms SELECT numeric_mul_karatsuba(random_ndigits(8192), random_ndigits(8192))= > 0; Time: 9.919 ms Time: 9.929 ms Time: 9.659 ms To measure smaller factor sizes, \timing doesn't provide enough precisio= n. Below measurements are made using my pg-timeit extension: Benchmark equal factor sizes, 1024 x 1024 ndigits: SELECT timeit.h('numeric_mul',ARRAY[random_ndigits(1024)::TEXT,random_nd= igits(1024)::TEXT],significant_figures:=3D2); 100 =C2=B5s SELECT timeit.h('numeric_mul_karatsuba',ARRAY[random_ndigits(1024)::TEXT= ,random_ndigits(1024)::TEXT],significant_figures:=3D2); 73 =C2=B5s Benchmark equal factor sizes, 512 x 512 ndigits: SELECT timeit.h('numeric_mul',ARRAY[random_ndigits(512)::TEXT,random_ndi= gits(512)::TEXT],significant_figures:=3D2); 27 =C2=B5s SELECT timeit.h('numeric_mul_karatsuba',ARRAY[random_ndigits(512)::TEXT,= random_ndigits(512)::TEXT],significant_figures:=3D2); 23 =C2=B5s Benchmark unequal factor sizes, 2048 x 16384 ndigits: SELECT timeit.h('numeric_mul',ARRAY[random_ndigits(2048)::TEXT,random_nd= igits(16384)::TEXT],significant_figures:=3D2); 3.6 ms SELECT timeit.h('numeric_mul_karatsuba',ARRAY[random_ndigits(2048)::TEXT= ,random_ndigits(16384)::TEXT],significant_figures:=3D2); 2.7 ms The KARATSUBA_CONDITION was determined through benchmarking on the follo= wing architectures: - Intel Core i9-14900K (desktop) - AMD Ryzen 9 7950X3D (desktop) - Apple M1Max (laptop) - AWS EC2 m7g.4xlarge (cloud server, AWS Graviton3 CPU) - AWS EC2 m7i.4xlarge (cloud server, Intel Xeon 4th Gen, Sapphire Rapids) The images depicting the benchmark plots are rather large, so I've refra= ined from including them as attachments. Instead, I've provided URLs to the benchmarks for direct access: https://gist.githubusercontent.com/joelonsql/e9d06cdbcdf56cd8ffa673f4998= 80b0d/raw/69df06e95bc254090f8397765079e1a8145eb5ac/derive_threshold_func= tion_using_dynamic_programming.png This image shows the best possible performance ratio per architecture, derived using Dynamic Programming. The black line segment shows the manu= ally crafted threshold function, which aims to avoid performance regressions, while c= apturing the beneficial regions, as a relatively simple threshold function, which has been implemented in both patches as the KARATSUBA_CONDITION ma= cro. https://gist.githubusercontent.com/joelonsql/e9d06cdbcdf56cd8ffa673f4998= 80b0d/raw/69df06e95bc254090f8397765079e1a8145eb5ac/benchmark.png This plot displays the actual performance ratio per architecture, measured after applying the mul_var-karatsuba-benchmark.patch. The performance_ratio scale in both plots uses a rainbow scale, where blue is at 1.0 and means no change. The maximum at 4.0 means that the Karatsuba version was four times faster than the traditional mul_var() at that architecture. To make it easier to distinguish performance regressions from, a magenta color scale that goes from pure magenta just below 1.0, to dark at 0.0. I picked magenta for this purpose since it's not part of the rainbow colors. /Joel --1fe2dc603a1541548bd694b5363b4c7c Content-Disposition: attachment; filename="mul_var-karatsuba.patch" Content-Type: application/octet-stream; name="mul_var-karatsuba.patch" Content-Transfer-Encoding: BASE64 ZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL3V0aWxzL2FkdC9udW1lcmljLmMgYi9zcmMvYmFj a2VuZC91dGlscy9hZHQvbnVtZXJpYy5jCmluZGV4IDU1MTBhMjAzYjAuLjA4YWQxMDI5MDEg MTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL3V0aWxzL2FkdC9udW1lcmljLmMKKysrIGIvc3Jj L2JhY2tlbmQvdXRpbHMvYWR0L251bWVyaWMuYwpAQCAtNDU5LDYgKzQ1OSwzMCBAQCBzdGF0 aWMgY29uc3QgTnVtZXJpY1ZhciBjb25zdF9uaW5mID0KIHN0YXRpYyBjb25zdCBpbnQgcm91 bmRfcG93ZXJzWzRdID0gezAsIDEwMDAsIDEwMCwgMTB9OwogI2VuZGlmCiAKKyNkZWZpbmUg S0FSQVRTVUJBX0JBU0VfTElNSVQgMzg0CisjZGVmaW5lIEtBUkFUU1VCQV9WQVIxX01JTjEg MTI4CisjZGVmaW5lIEtBUkFUU1VCQV9WQVIxX01JTjIgMjAwMAorI2RlZmluZSBLQVJBVFNV QkFfVkFSMl9NSU4xIDI1MDAKKyNkZWZpbmUgS0FSQVRTVUJBX1ZBUjJfTUlOMiA5MDAwCisj ZGVmaW5lIEtBUkFUU1VCQV9TTE9QRSAwLjc2NAorI2RlZmluZSBLQVJBVFNVQkFfSU5URVJD RVBUIDkwLjczNworCisjZGVmaW5lIEtBUkFUU1VCQV9MT1dfUkFOR0VfQ09ORElUSU9OKHZh cjFuZGlnaXRzLCB2YXIybmRpZ2l0cykgXAorCSgodmFyMW5kaWdpdHMpID4gKEtBUkFUU1VC QV9TTE9QRSkgKiAodmFyMm5kaWdpdHMpICsgS0FSQVRTVUJBX0lOVEVSQ0VQVCkKKworI2Rl ZmluZSBLQVJBVFNVQkFfTUlERExFX1JBTkdFX0NPTkRJVElPTih2YXIxbmRpZ2l0cywgdmFy Mm5kaWdpdHMpIFwKKwkoKHZhcjJuZGlnaXRzKSA+IEtBUkFUU1VCQV9WQVIyX01JTjEgJiYg XAorCSAodmFyMW5kaWdpdHMpID4gS0FSQVRTVUJBX1ZBUjFfTUlOMikKKworI2RlZmluZSBL QVJBVFNVQkFfSElHSF9SQU5HRV9DT05ESVRJT04odmFyMW5kaWdpdHMsIHZhcjJuZGlnaXRz KSBcCisJKCh2YXIybmRpZ2l0cykgPiBLQVJBVFNVQkFfVkFSMl9NSU4yICYmIFwKKwkgKHZh cjFuZGlnaXRzKSA+IEtBUkFUU1VCQV9WQVIxX01JTjEpCisKKyNkZWZpbmUgS0FSQVRTVUJB X0NPTkRJVElPTih2YXIxbmRpZ2l0cywgdmFyMm5kaWdpdHMpIFwKKwkoKHZhcjJuZGlnaXRz KSA+PSBLQVJBVFNVQkFfQkFTRV9MSU1JVCAmJiBcCisJIChLQVJBVFNVQkFfTE9XX1JBTkdF X0NPTkRJVElPTih2YXIxbmRpZ2l0cywgdmFyMm5kaWdpdHMpIHx8IFwKKwkgIEtBUkFUU1VC QV9NSURETEVfUkFOR0VfQ09ORElUSU9OKHZhcjFuZGlnaXRzLCB2YXIybmRpZ2l0cykgfHwg XAorCSAgS0FSQVRTVUJBX0hJR0hfUkFOR0VfQ09ORElUSU9OKHZhcjFuZGlnaXRzLCB2YXIy bmRpZ2l0cykpKQogCiAvKiAtLS0tLS0tLS0tCiAgKiBMb2NhbCBmdW5jdGlvbnMKQEAgLTU0 OCw2ICs1NzIsMTQgQEAgc3RhdGljIHZvaWQgYWRkX3Zhcihjb25zdCBOdW1lcmljVmFyICp2 YXIxLCBjb25zdCBOdW1lcmljVmFyICp2YXIyLAogCQkJCQlOdW1lcmljVmFyICpyZXN1bHQp Owogc3RhdGljIHZvaWQgc3ViX3Zhcihjb25zdCBOdW1lcmljVmFyICp2YXIxLCBjb25zdCBO dW1lcmljVmFyICp2YXIyLAogCQkJCQlOdW1lcmljVmFyICpyZXN1bHQpOworaW5saW5lIHN0 YXRpYyB2b2lkIHNwbGl0X3Zhcl9hdChjb25zdCBOdW1lcmljVmFyICp2YXIsIGludCBzcGxp dF9wb2ludCwKKwkJCQkJCQkJTnVtZXJpY1ZhciAqbG93LCBOdW1lcmljVmFyICpoaWdoKTsK K3N0YXRpYyB2b2lkIG11bF92YXJfa2FyYXRzdWJhX2Z1bGwoY29uc3QgTnVtZXJpY1ZhciAq dmFyMSwgY29uc3QgTnVtZXJpY1ZhciAqdmFyMiwKKwkJCQkJTnVtZXJpY1ZhciAqcmVzdWx0 LAorCQkJCQlpbnQgcnNjYWxlKTsKK3N0YXRpYyB2b2lkIG11bF92YXJfa2FyYXRzdWJhX2hh bGYoY29uc3QgTnVtZXJpY1ZhciAqdmFyMSwgY29uc3QgTnVtZXJpY1ZhciAqdmFyMiwKKwkJ CQkJTnVtZXJpY1ZhciAqcmVzdWx0LAorCQkJCQlpbnQgcnNjYWxlKTsKIHN0YXRpYyB2b2lk IG11bF92YXIoY29uc3QgTnVtZXJpY1ZhciAqdmFyMSwgY29uc3QgTnVtZXJpY1ZhciAqdmFy MiwKIAkJCQkJTnVtZXJpY1ZhciAqcmVzdWx0LAogCQkJCQlpbnQgcnNjYWxlKTsKQEAgLTg2 NTksNiArODY5MSwyMTkgQEAgc3ViX3Zhcihjb25zdCBOdW1lcmljVmFyICp2YXIxLCBjb25z dCBOdW1lcmljVmFyICp2YXIyLCBOdW1lcmljVmFyICpyZXN1bHQpCiB9CiAKIAorLyoKKyAq IHNwbGl0X3Zhcl9hdCgpIC0KKyAqCisgKiBTcGxpdCBhIE51bWVyaWNWYXIgaW50byB0d28g cGFydHMgYXQgYSBzcGVjaWZpZWQgcG9zaXRpb24uCisgKi8KK2lubGluZSBzdGF0aWMgdm9p ZAorc3BsaXRfdmFyX2F0KGNvbnN0IE51bWVyaWNWYXIgKnZhciwgaW50IHNwbGl0X3BvaW50 LAorCQkJIE51bWVyaWNWYXIgKmxvdywgTnVtZXJpY1ZhciAqaGlnaCkKK3sKKwlpbnQgaGln aF9uZGlnaXRzID0gdmFyLT5uZGlnaXRzIC0gc3BsaXRfcG9pbnQ7CisJaW50IGxvd19uZGln aXRzID0gc3BsaXRfcG9pbnQ7CisKKwlpbml0X3ZhcihoaWdoKTsKKwlpbml0X3Zhcihsb3cp OworCisJaGlnaC0+bmRpZ2l0cyA9IGhpZ2hfbmRpZ2l0czsKKwloaWdoLT5kaWdpdHMgPSB2 YXItPmRpZ2l0czsKKwloaWdoLT5idWYgPSBOVUxMOworCWhpZ2gtPndlaWdodCA9IHZhci0+ d2VpZ2h0IC0gbG93X25kaWdpdHM7CisJaGlnaC0+c2lnbiA9IHZhci0+c2lnbjsKKwloaWdo LT5kc2NhbGUgPSAodmFyLT5uZGlnaXRzIC0gdmFyLT53ZWlnaHQgLSAxKSAqIERFQ19ESUdJ VFM7CisKKwlsb3ctPm5kaWdpdHMgPSBsb3dfbmRpZ2l0czsKKwlsb3ctPmRpZ2l0cyA9IHZh ci0+ZGlnaXRzICsgaGlnaF9uZGlnaXRzOworCWxvdy0+YnVmID0gTlVMTDsKKwlsb3ctPndl aWdodCA9IHZhci0+d2VpZ2h0IC0gaGlnaF9uZGlnaXRzOworCWxvdy0+c2lnbiA9IHZhci0+ c2lnbjsKKwlsb3ctPmRzY2FsZSA9IHZhci0+ZHNjYWxlOworfQorCisKKy8qCisgKiBtdWxf dmFyX2thcmF0c3ViYV9mdWxsKCkgLQorICoKKyAqCU11bHRpcGxpY2F0aW9uIHVzaW5nIHRo ZSBLYXJhdHN1YmEgYWxnb3JpdGhtLgorICoKKyAqCVRoZSBhbGdvcml0aG0gbm9ybWFsbHkg c3RhcnRzIGJ5IGNoZWNraW5nIGlmIGFueSBvZiB0aGUgaW5wdXRzCisgKglhcmUgc21hbGxl ciB0aGFuIHRoZSBOQkFTRSwgdGhlIGJhc2UgY2FzZSBmb3IgdGhlIHJlY3Vyc2lvbiwKKyAq CWFuZCBpZiBzbywgZmFsbCBiYWNrIHRvIHRyYWRpdGlvbmFsIG11bHRpcGxpY2F0aW9uLgor ICoKKyAqCVRoYXQgcGFydCBpcyBoYW5kbGVkIGJ5IHRoZSBjYWxsZXIgaW4gb3VyIGNvZGUs IHNvIHdoZW4gdGhpcyBmdW5jdGlvbgorICoJaXMgY2FsbGVkLCB3ZSBrbm93IHRoYXQgdmFy MSBhbmQgdmFyMiBhcmUgbGFyZ2UgZW5vdWdoIGZvciBLYXJhdHN1YmEKKyAqCXRvIGJlIHVz ZWQuIFdlIGFsc28ga25vdyB0aGF0IHZhcjEgaXMgc2hvcnRlciBvciBvZiBlcXVhbCBsZW5n dGggYXMgdmFyMiwKKyAqCXdoaWNoIGhhcyBiZWVuIGFycmFuZ2VkIGJ5IHRoZSBjYWxsZXIg Ynkgc3dhcHBpbmcgdGhlbSBpZiBuZWNlc3NhcnkuCisgKgorICoJVGhlIGFsZ29yaXRobSB0 aGVuIHByb2NlZWRzIGJ5IHNwbGl0dGluZyB2YXIxIGFuZCB2YXIyIGludG8KKyAqCXR3byBo aWdoIGFuZCBsb3cgcGFydHMsIGF0IGhhbGYgdGhlIGxlbmd0aCBvZiB0aGUgbG9uZ2VyIGlu cHV0OgorICoKKyAqCQltID0gbWF4KHNpemVfTkJBU0UodmFyMSksIHNpemVfTkJBU0UodmFy MikpCisgKgkJbTIgPSBmbG9vcihtIC8gMikKKyAqCisgKgkJaGlnaDEsIGxvdzEgPSBzcGxp dF92YXJfYXQodmFyMSwgbTIpCisgKgkJaGlnaDIsIGxvdzIgPSBzcGxpdF92YXJfYXQodmFy MiwgbTIpCisgKgorICoJCXowID0gKGxvdzEgKiBsb3cyKQorICoJCXoxID0gKChsb3cxICsg aGlnaDEpICogKGxvdzIgKyBoaWdoMikpCisgKgkJejIgPSAoaGlnaDEgKiBoaWdoMikKKyAq CisgKgkJcmV0dXJuICh6MiAqIE5CQVNFIF4gKG0yIMOXIDIpKSArICgoejEgLSB6MiAtIHow KSAqIE5CQVNFIF4gbTIpICsgejAKKyAqLworc3RhdGljIHZvaWQKK211bF92YXJfa2FyYXRz dWJhX2Z1bGwoY29uc3QgTnVtZXJpY1ZhciAqdmFyMSwgY29uc3QgTnVtZXJpY1ZhciAqdmFy MiwKKwkJTnVtZXJpY1ZhciAqcmVzdWx0LCBpbnQgcnNjYWxlKQoreworCQlOdW1lcmljVmFy CWhpZ2gxLCBsb3cxOworCQlOdW1lcmljVmFyCWhpZ2gyLCBsb3cyOworCQlOdW1lcmljVmFy CXowLCB6MSwgejI7CisJCU51bWVyaWNWYXIJdGVtcDEsIHRlbXAyOworCQlpbnQJCQltMiA9 IHZhcjItPm5kaWdpdHMgLyAyOworCisJCWluaXRfdmFyKCZsb3cxKTsKKwkJaW5pdF92YXIo JmxvdzIpOworCQlpbml0X3ZhcigmaGlnaDEpOworCQlpbml0X3ZhcigmaGlnaDIpOworCQlp bml0X3ZhcigmejApOworCQlpbml0X3ZhcigmejEpOworCQlpbml0X3ZhcigmejIpOworCQlp bml0X3ZhcigmdGVtcDEpOworCQlpbml0X3ZhcigmdGVtcDIpOworCisJCXNwbGl0X3Zhcl9h dCh2YXIxLCBtMiwgJmxvdzEsICZoaWdoMSk7CisJCXNwbGl0X3Zhcl9hdCh2YXIyLCBtMiwg JmxvdzIsICZoaWdoMik7CisKKwkJbXVsX3ZhcigmbG93MSwgJmxvdzIsICZ6MCwgbG93MS5k c2NhbGUgKyBsb3cyLmRzY2FsZSk7CisKKwkJYWRkX3ZhcigmbG93MSwgJmhpZ2gxLCAmdGVt cDEpOworCQlhZGRfdmFyKCZsb3cyLCAmaGlnaDIsICZ0ZW1wMik7CisJCW11bF92YXIoJnRl bXAxLCAmdGVtcDIsICZ6MSwgdGVtcDEuZHNjYWxlICsgdGVtcDIuZHNjYWxlKTsKKworCQlt dWxfdmFyKCZoaWdoMSwgJmhpZ2gyLCAmejIsIGhpZ2gxLmRzY2FsZSArIGhpZ2gyLmRzY2Fs ZSk7CisKKwkJc2V0X3Zhcl9mcm9tX3ZhcigmejIsICZ0ZW1wMSk7CisJCXRlbXAxLndlaWdo dCArPSBtMiAqIDI7CisKKwkJc3ViX3ZhcigmejEsICZ6MiwgJnoxKTsKKwkJc3ViX3Zhcigm ejEsICZ6MCwgJnRlbXAyKTsKKwkJdGVtcDIud2VpZ2h0ICs9IG0yOworCisJCWFkZF92YXIo JnRlbXAxLCAmdGVtcDIsICZ0ZW1wMik7CisJCWFkZF92YXIoJnRlbXAyLCAmejAsIHJlc3Vs dCk7CisKKwkJZnJlZV92YXIoJmxvdzEpOworCQlmcmVlX3ZhcigmbG93Mik7CisJCWZyZWVf dmFyKCZoaWdoMSk7CisJCWZyZWVfdmFyKCZoaWdoMik7CisJCWZyZWVfdmFyKCZ6MCk7CisJ CWZyZWVfdmFyKCZ6MSk7CisJCWZyZWVfdmFyKCZ6Mik7CisJCWZyZWVfdmFyKCZ0ZW1wMSk7 CisJCWZyZWVfdmFyKCZ0ZW1wMik7CisKKwkJLyogUm91bmQgdG8gdGFyZ2V0IHJzY2FsZSAo YW5kIHNldCByZXN1bHQtPmRzY2FsZSkgKi8KKwkJcm91bmRfdmFyKHJlc3VsdCwgcnNjYWxl KTsKKworCQkvKiBTdHJpcCBsZWFkaW5nIGFuZCB0cmFpbGluZyB6ZXJvZXMgKi8KKwkJc3Ry aXBfdmFyKHJlc3VsdCk7CisKKwkJcmV0dXJuOworfQorCisKKy8qCisgKiBtdWxfdmFyX2th cmF0c3ViYV9oYWxmKCkgLQorICoKKyAqCUthcmF0c3ViYSBNdWx0aXBsaWNhdGlvbiBmb3Ig ZmFjdG9ycyB3aXRoIHNpZ25pZmljYW50IGxlbmd0aCBkaXNwYXJpdHkuCisgKgorICoJVGhl IEhhbGYtS2FyYXRzdWJhIE11bHRpcGxpY2F0aW9uIEFsZ29yaXRobSBpcyBhIHNwZWNpYWxp emVkIGNhc2Ugb2YKKyAqCXRoZSBub3JtYWwgS2FyYXRzdWJhIG11bHRpcGxpY2F0aW9uIGFs Z29yaXRobSwgZGVzaWduZWQgZm9yIHRoZSBzY2VuYXJpbworICoJd2hlcmUgdmFyMiBoYXMg YXQgbGVhc3QgdHdpY2UgYXMgbWFueSBiYXNlIGRpZ2l0cyBhcyB2YXIxLgorICoKKyAqCUlu IHRoaXMgY2FzZSB2YXIyICh0aGUgbG9uZ2VyIGlucHV0KSBpcyBzcGxpdCBpbnRvIGhpZ2gy IGFuZCBsb3cxLAorICoJYXQgbTIgKGhhbGYgdGhlIGxlbmd0aCBvZiB2YXIyKSBhbmQgdmFy MSAodGhlIHNob3J0ZXIgaW5wdXQpLAorICoJaXMgdXNlZCBkaXJlY3RseSB3aXRob3V0IHNw bGl0dGluZy4KKyAqCisgKglUaGUgYWxnb3JpdGhtIHRoZW4gcHJvY2VlZHMgYXMgZm9sbG93 czoKKyAqCisgKgkxLiBDb21wdXRlIHRoZSBwcm9kdWN0IHowID0gdmFyMSAqIGxvdzIuCisg KgkyLiBDb21wdXRlIHRoZSBwcm9kdWN0IHRlbXAyID0gdmFyMSAqIGhpZ2gyLgorICoJMy4g QWRqdXN0IHRoZSB3ZWlnaHQgb2YgdGVtcDIgYnkgYWRkaW5nIG0yICgqIE5CQVNFIF4gbTIp CisgKgk0LiBBZGQgdGVtcDIgYW5kIHowIHRvIG9idGFpbiB0aGUgZmluYWwgcmVzdWx0Lgor ICoKKyAqCVByb29mOgorICoKKyAqCVRoZSBhbGdvcml0aG0gY2FuIGJlIGRlcml2ZWQgZnJv bSB0aGUgb3JpZ2luYWwgS2FyYXRzdWJhIGFsZ29yaXRobSBieQorICoJc2ltcGxpZnlpbmcg dGhlIGZvcm11bGEgd2hlbiB0aGUgc2hvcnRlciBmYWN0b3IgdmFyMSBpcyBub3Qgc3BsaXQg aW50bworICoJaGlnaCBhbmQgbG93IHBhcnRzLCBhcyBzaG93biBiZWxvdy4KKyAqCisgKglP cmlnaW5hbCBLYXJhdHN1YmEgZm9ybXVsYToKKyAqCisgKgkJcmVzdWx0ID0gKHoyICogTkJB U0UgXiAobTIgw5cgMikpICsgKCh6MSAtIHoyIC0gejApICogTkJBU0UgXiBtMikgKyB6MAor ICoKKyAqCVN1YnN0aXR1dGlvbnM6CisgKgorICoJCWxvdzEgPSB2YXIxCisgKgkJaGlnaDEg PSAwCisgKgorICoJQXBwbHlpbmcgc3Vic3RpdHV0aW9uczoKKyAqCisgKgkJejAgPSAobG93 MSAqIGxvdzIpCisgKgkJICAgPSAodmFyMSAqIGxvdzIpCisgKgorICoJCXoxID0gKChsb3cx ICsgaGlnaDEpICogKGxvdzIgKyBoaWdoMikpCisgKgkJICAgPSAoKHZhcjEgKyAwKSAqIChs b3cyICsgaGlnaDIpKQorICoJCSAgID0gKHZhcjEgKiBsb3cyKSArICh2YXIxICogaGlnaDIp CisgKgorICoJCXoyID0gKGhpZ2gxICogaGlnaDIpCisgKgkJICAgPSAoMCAqIGhpZ2gyKQor ICoJCSAgID0gMAorICoKKyAqCVNpbXBsaWZpZWQgdXNpbmcgdGhlIGFib3ZlIHN1YnN0aXR1 dGlvbnM6CisgKgorICoJCXJlc3VsdCA9ICh6MiAqIE5CQVNFIF4gKG0yIMOXIDIpKSArICgo ejEgLSB6MiAtIHowKSAqIE5CQVNFIF4gbTIpICsgejAKKyAqCQkJICAgPSAoMCAqIE5CQVNF IF4gKG0yIMOXIDIpKSArICgoejEgLSAwIC0gejApICogTkJBU0UgXiBtMikgKyB6MAorICoJ CQkgICA9ICgoejEgLSB6MCkgKiBOQkFTRSBeIG0yKSArIHowCisgKgkJCSAgID0gKCh6MSAt IHowKSAqIE5CQVNFIF4gbTIpICsgejAKKyAqCQkJICAgPSAodmFyMSAqIGhpZ2gyKSAqIE5C QVNFIF4gbTIgKyB6MAorICovCitzdGF0aWMgdm9pZAorbXVsX3Zhcl9rYXJhdHN1YmFfaGFs Zihjb25zdCBOdW1lcmljVmFyICp2YXIxLCBjb25zdCBOdW1lcmljVmFyICp2YXIyLAorCQlO dW1lcmljVmFyICpyZXN1bHQsIGludCByc2NhbGUpCit7CisJTnVtZXJpY1ZhcgloaWdoMiwg bG93MjsKKwlOdW1lcmljVmFyCXowOworCU51bWVyaWNWYXIJdGVtcDI7CisJaW50CQkJbTIg PSB2YXIyLT5uZGlnaXRzIC8gMjsKKworCWluaXRfdmFyKCZoaWdoMik7CisJaW5pdF92YXIo JmxvdzIpOworCWluaXRfdmFyKCZ6MCk7CisJaW5pdF92YXIoJnRlbXAyKTsKKworCXNwbGl0 X3Zhcl9hdCh2YXIyLCBtMiwgJmxvdzIsICZoaWdoMik7CisKKwltdWxfdmFyKHZhcjEsICZs b3cyLCAmejAsIHZhcjEtPmRzY2FsZSArIGxvdzIuZHNjYWxlKTsKKwltdWxfdmFyKHZhcjEs ICZoaWdoMiwgJnRlbXAyLCB2YXIxLT5kc2NhbGUgKyBoaWdoMi5kc2NhbGUpOworCXRlbXAy LndlaWdodCArPSBtMjsKKwlhZGRfdmFyKCZ0ZW1wMiwgJnowLCByZXN1bHQpOworCisJZnJl ZV92YXIoJmhpZ2gyKTsKKwlmcmVlX3ZhcigmbG93Mik7CisJZnJlZV92YXIoJnowKTsKKwlm cmVlX3ZhcigmdGVtcDIpOworCisJLyogUm91bmQgdG8gdGFyZ2V0IHJzY2FsZSAoYW5kIHNl dCByZXN1bHQtPmRzY2FsZSkgKi8KKwlyb3VuZF92YXIocmVzdWx0LCByc2NhbGUpOworCisJ LyogU3RyaXAgbGVhZGluZyBhbmQgdHJhaWxpbmcgemVyb2VzICovCisJc3RyaXBfdmFyKHJl c3VsdCk7CisKKwlyZXR1cm47Cit9CisKKwogLyoKICAqIG11bF92YXIoKSAtCiAgKgpAQCAt ODc0Nyw2ICs4OTkyLDE4IEBAIG11bF92YXIoY29uc3QgTnVtZXJpY1ZhciAqdmFyMSwgY29u c3QgTnVtZXJpY1ZhciAqdmFyMiwgTnVtZXJpY1ZhciAqcmVzdWx0LAogCQlyZXR1cm47CiAJ fQogCisJLyoKKwkgKiBVc2UgdGhlIEthcmF0c3ViYSBhbGdvcml0aG0gZm9yIHN1ZmZpY2ll bnRseSBsYXJnZSBmYWN0b3JzLgorCSAqLworCWlmIChLQVJBVFNVQkFfQ09ORElUSU9OKHZh cjFuZGlnaXRzLCB2YXIybmRpZ2l0cykpCisJeworCQlpZiAodmFyMW5kaWdpdHMgKiAyID4g dmFyMm5kaWdpdHMpCisJCQltdWxfdmFyX2thcmF0c3ViYV9mdWxsKHZhcjEsIHZhcjIsIHJl c3VsdCwgcnNjYWxlKTsKKwkJZWxzZQorCQkJbXVsX3Zhcl9rYXJhdHN1YmFfaGFsZih2YXIx LCB2YXIyLCByZXN1bHQsIHJzY2FsZSk7CisJCXJldHVybjsKKwl9CisKIAkvKgogCSAqIFdl IGRvIHRoZSBhcml0aG1ldGljIGluIGFuIGFycmF5ICJkaWdbXSIgb2Ygc2lnbmVkIGludCdz LiAgU2luY2UKIAkgKiBJTlRfTUFYIGlzIG5vdGljZWFibHkgbGFyZ2VyIHRoYW4gTkJBU0Uq TkJBU0UsIHRoaXMgZ2l2ZXMgdXMgaGVhZHJvb20K --1fe2dc603a1541548bd694b5363b4c7c Content-Disposition: attachment; filename="mul_var-karatsuba-benchmark.patch" Content-Type: application/octet-stream; name="mul_var-karatsuba-benchmark.patch" Content-Transfer-Encoding: BASE64 ZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL3V0aWxzL2FkdC9udW1lcmljLmMgYi9zcmMvYmFj a2VuZC91dGlscy9hZHQvbnVtZXJpYy5jCmluZGV4IDU1MTBhMjAzYjAuLmM0MGIwNjJjOWEg MTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL3V0aWxzL2FkdC9udW1lcmljLmMKKysrIGIvc3Jj L2JhY2tlbmQvdXRpbHMvYWR0L251bWVyaWMuYwpAQCAtNDU5LDYgKzQ1OSwzMCBAQCBzdGF0 aWMgY29uc3QgTnVtZXJpY1ZhciBjb25zdF9uaW5mID0KIHN0YXRpYyBjb25zdCBpbnQgcm91 bmRfcG93ZXJzWzRdID0gezAsIDEwMDAsIDEwMCwgMTB9OwogI2VuZGlmCiAKKyNkZWZpbmUg S0FSQVRTVUJBX0JBU0VfTElNSVQgMzg0CisjZGVmaW5lIEtBUkFUU1VCQV9WQVIxX01JTjEg MTI4CisjZGVmaW5lIEtBUkFUU1VCQV9WQVIxX01JTjIgMjAwMAorI2RlZmluZSBLQVJBVFNV QkFfVkFSMl9NSU4xIDI1MDAKKyNkZWZpbmUgS0FSQVRTVUJBX1ZBUjJfTUlOMiA5MDAwCisj ZGVmaW5lIEtBUkFUU1VCQV9TTE9QRSAwLjc2NAorI2RlZmluZSBLQVJBVFNVQkFfSU5URVJD RVBUIDkwLjczNworCisjZGVmaW5lIEtBUkFUU1VCQV9MT1dfUkFOR0VfQ09ORElUSU9OKHZh cjFuZGlnaXRzLCB2YXIybmRpZ2l0cykgXAorCSgodmFyMW5kaWdpdHMpID4gKEtBUkFUU1VC QV9TTE9QRSkgKiAodmFyMm5kaWdpdHMpICsgS0FSQVRTVUJBX0lOVEVSQ0VQVCkKKworI2Rl ZmluZSBLQVJBVFNVQkFfTUlERExFX1JBTkdFX0NPTkRJVElPTih2YXIxbmRpZ2l0cywgdmFy Mm5kaWdpdHMpIFwKKwkoKHZhcjJuZGlnaXRzKSA+IEtBUkFUU1VCQV9WQVIyX01JTjEgJiYg XAorCSAodmFyMW5kaWdpdHMpID4gS0FSQVRTVUJBX1ZBUjFfTUlOMikKKworI2RlZmluZSBL QVJBVFNVQkFfSElHSF9SQU5HRV9DT05ESVRJT04odmFyMW5kaWdpdHMsIHZhcjJuZGlnaXRz KSBcCisJKCh2YXIybmRpZ2l0cykgPiBLQVJBVFNVQkFfVkFSMl9NSU4yICYmIFwKKwkgKHZh cjFuZGlnaXRzKSA+IEtBUkFUU1VCQV9WQVIxX01JTjEpCisKKyNkZWZpbmUgS0FSQVRTVUJB X0NPTkRJVElPTih2YXIxbmRpZ2l0cywgdmFyMm5kaWdpdHMpIFwKKwkoKHZhcjJuZGlnaXRz KSA+PSBLQVJBVFNVQkFfQkFTRV9MSU1JVCAmJiBcCisJIChLQVJBVFNVQkFfTE9XX1JBTkdF X0NPTkRJVElPTih2YXIxbmRpZ2l0cywgdmFyMm5kaWdpdHMpIHx8IFwKKwkgIEtBUkFUU1VC QV9NSURETEVfUkFOR0VfQ09ORElUSU9OKHZhcjFuZGlnaXRzLCB2YXIybmRpZ2l0cykgfHwg XAorCSAgS0FSQVRTVUJBX0hJR0hfUkFOR0VfQ09ORElUSU9OKHZhcjFuZGlnaXRzLCB2YXIy bmRpZ2l0cykpKQogCiAvKiAtLS0tLS0tLS0tCiAgKiBMb2NhbCBmdW5jdGlvbnMKQEAgLTU1 MSw2ICs1NzUsMTcgQEAgc3RhdGljIHZvaWQgc3ViX3Zhcihjb25zdCBOdW1lcmljVmFyICp2 YXIxLCBjb25zdCBOdW1lcmljVmFyICp2YXIyLAogc3RhdGljIHZvaWQgbXVsX3Zhcihjb25z dCBOdW1lcmljVmFyICp2YXIxLCBjb25zdCBOdW1lcmljVmFyICp2YXIyLAogCQkJCQlOdW1l cmljVmFyICpyZXN1bHQsCiAJCQkJCWludCByc2NhbGUpOworc3RhdGljIHZvaWQgbXVsX3Zh cl9rYXJhdHN1YmEoY29uc3QgTnVtZXJpY1ZhciAqdmFyMSwgY29uc3QgTnVtZXJpY1ZhciAq dmFyMiwKKwkJCQkJTnVtZXJpY1ZhciAqcmVzdWx0LAorCQkJCQlpbnQgcnNjYWxlKTsKK2lu bGluZSBzdGF0aWMgdm9pZCBzcGxpdF92YXJfYXQoY29uc3QgTnVtZXJpY1ZhciAqdmFyLCBp bnQgc3BsaXRfcG9pbnQsCisJCQkJCQkJCU51bWVyaWNWYXIgKmxvdywgTnVtZXJpY1ZhciAq aGlnaCk7CitzdGF0aWMgdm9pZCBtdWxfdmFyX2thcmF0c3ViYV9mdWxsKGNvbnN0IE51bWVy aWNWYXIgKnZhcjEsIGNvbnN0IE51bWVyaWNWYXIgKnZhcjIsCisJCQkJCU51bWVyaWNWYXIg KnJlc3VsdCwKKwkJCQkJaW50IHJzY2FsZSk7CitzdGF0aWMgdm9pZCBtdWxfdmFyX2thcmF0 c3ViYV9oYWxmKGNvbnN0IE51bWVyaWNWYXIgKnZhcjEsIGNvbnN0IE51bWVyaWNWYXIgKnZh cjIsCisJCQkJCU51bWVyaWNWYXIgKnJlc3VsdCwKKwkJCQkJaW50IHJzY2FsZSk7CiBzdGF0 aWMgdm9pZCBkaXZfdmFyKGNvbnN0IE51bWVyaWNWYXIgKnZhcjEsIGNvbnN0IE51bWVyaWNW YXIgKnZhcjIsCiAJCQkJCU51bWVyaWNWYXIgKnJlc3VsdCwKIAkJCQkJaW50IHJzY2FsZSwg Ym9vbCByb3VuZCk7CkBAIC0zMTE1LDYgKzMxNTAsMTMwIEBAIG51bWVyaWNfbXVsX29wdF9l cnJvcihOdW1lcmljIG51bTEsIE51bWVyaWMgbnVtMiwgYm9vbCAqaGF2ZV9lcnJvcikKIH0K IAogCisvKgorICogbnVtZXJpY19tdWxfa2FyYXRzdWJhKCkgLQorICoKKyAqIFRoaXMgZnVu Y3Rpb24gbXVsdGlwbGllcyB0d28gbnVtZXJpYyB2YWx1ZXMgdXNpbmcgdGhlIEthcmF0c3Vi YSBhbGdvcml0aG0sCisgKiBkZXNpZ25lZCBmb3IgZWZmaWNpZW50IGhhbmRsaW5nIG9mIGxh cmdlIG51bWJlcnMuIEl0J3MgaW50cm9kdWNlZCB0byBhbGxvdworICogZGlyZWN0IGJlbmNo bWFyayBjb21wYXJpc29ucyB3aXRoIHRoZSBzdGFuZGFyZCBudW1lcmljX211bCgpIGZ1bmN0 aW9uLgorICovCitEYXR1bQorbnVtZXJpY19tdWxfa2FyYXRzdWJhKFBHX0ZVTkNUSU9OX0FS R1MpCit7CisJTnVtZXJpYwkJbnVtMSA9IFBHX0dFVEFSR19OVU1FUklDKDApOworCU51bWVy aWMJCW51bTIgPSBQR19HRVRBUkdfTlVNRVJJQygxKTsKKwlOdW1lcmljCQlyZXM7CisKKwly ZXMgPSBudW1lcmljX211bF9rYXJhdHN1YmFfb3B0X2Vycm9yKG51bTEsIG51bTIsIE5VTEwp OworCisJUEdfUkVUVVJOX05VTUVSSUMocmVzKTsKK30KKworCisvKgorICogbnVtZXJpY19t dWxfa2FyYXRzdWJhX29wdF9lcnJvcigpIC0KKyAqCisgKglJbnRlcm5hbCB2ZXJzaW9uIG9m IG51bWVyaWNfbXVsX2thcmF0c3ViYSgpLgorICoJSWYgIipoYXZlX2Vycm9yIiBmbGFnIGlz IHByb3ZpZGVkLCBvbiBlcnJvciBpdCdzIHNldCB0byB0cnVlLCBOVUxMIHJldHVybmVkLgor ICoJVGhpcyBpcyBoZWxwZnVsIHdoZW4gY2FsbGVyIG5lZWQgdG8gaGFuZGxlIGVycm9ycyBi eSBpdHNlbGYuCisgKi8KK051bWVyaWMKK251bWVyaWNfbXVsX2thcmF0c3ViYV9vcHRfZXJy b3IoTnVtZXJpYyBudW0xLCBOdW1lcmljIG51bTIsIGJvb2wgKmhhdmVfZXJyb3IpCit7CisJ TnVtZXJpY1ZhcglhcmcxOworCU51bWVyaWNWYXIJYXJnMjsKKwlOdW1lcmljVmFyCXJlc3Vs dDsKKwlOdW1lcmljCQlyZXM7CisKKwkvKgorCSAqIEhhbmRsZSBOYU4gYW5kIGluZmluaXRp ZXMKKwkgKi8KKwlpZiAoTlVNRVJJQ19JU19TUEVDSUFMKG51bTEpIHx8IE5VTUVSSUNfSVNf U1BFQ0lBTChudW0yKSkKKwl7CisJCWlmIChOVU1FUklDX0lTX05BTihudW0xKSB8fCBOVU1F UklDX0lTX05BTihudW0yKSkKKwkJCXJldHVybiBtYWtlX3Jlc3VsdCgmY29uc3RfbmFuKTsK KwkJaWYgKE5VTUVSSUNfSVNfUElORihudW0xKSkKKwkJeworCQkJc3dpdGNoIChudW1lcmlj X3NpZ25faW50ZXJuYWwobnVtMikpCisJCQl7CisJCQkJY2FzZSAwOgorCQkJCQlyZXR1cm4g bWFrZV9yZXN1bHQoJmNvbnN0X25hbik7IC8qIEluZiAqIDAgKi8KKwkJCQljYXNlIDE6CisJ CQkJCXJldHVybiBtYWtlX3Jlc3VsdCgmY29uc3RfcGluZik7CisJCQkJY2FzZSAtMToKKwkJ CQkJcmV0dXJuIG1ha2VfcmVzdWx0KCZjb25zdF9uaW5mKTsKKwkJCX0KKwkJCUFzc2VydChm YWxzZSk7CisJCX0KKwkJaWYgKE5VTUVSSUNfSVNfTklORihudW0xKSkKKwkJeworCQkJc3dp dGNoIChudW1lcmljX3NpZ25faW50ZXJuYWwobnVtMikpCisJCQl7CisJCQkJY2FzZSAwOgor CQkJCQlyZXR1cm4gbWFrZV9yZXN1bHQoJmNvbnN0X25hbik7IC8qIC1JbmYgKiAwICovCisJ CQkJY2FzZSAxOgorCQkJCQlyZXR1cm4gbWFrZV9yZXN1bHQoJmNvbnN0X25pbmYpOworCQkJ CWNhc2UgLTE6CisJCQkJCXJldHVybiBtYWtlX3Jlc3VsdCgmY29uc3RfcGluZik7CisJCQl9 CisJCQlBc3NlcnQoZmFsc2UpOworCQl9CisJCS8qIGJ5IGhlcmUsIG51bTEgbXVzdCBiZSBm aW5pdGUsIHNvIG51bTIgaXMgbm90ICovCisJCWlmIChOVU1FUklDX0lTX1BJTkYobnVtMikp CisJCXsKKwkJCXN3aXRjaCAobnVtZXJpY19zaWduX2ludGVybmFsKG51bTEpKQorCQkJewor CQkJCWNhc2UgMDoKKwkJCQkJcmV0dXJuIG1ha2VfcmVzdWx0KCZjb25zdF9uYW4pOyAvKiAw ICogSW5mICovCisJCQkJY2FzZSAxOgorCQkJCQlyZXR1cm4gbWFrZV9yZXN1bHQoJmNvbnN0 X3BpbmYpOworCQkJCWNhc2UgLTE6CisJCQkJCXJldHVybiBtYWtlX3Jlc3VsdCgmY29uc3Rf bmluZik7CisJCQl9CisJCQlBc3NlcnQoZmFsc2UpOworCQl9CisJCUFzc2VydChOVU1FUklD X0lTX05JTkYobnVtMikpOworCQlzd2l0Y2ggKG51bWVyaWNfc2lnbl9pbnRlcm5hbChudW0x KSkKKwkJeworCQkJY2FzZSAwOgorCQkJCXJldHVybiBtYWtlX3Jlc3VsdCgmY29uc3RfbmFu KTsgLyogMCAqIC1JbmYgKi8KKwkJCWNhc2UgMToKKwkJCQlyZXR1cm4gbWFrZV9yZXN1bHQo JmNvbnN0X25pbmYpOworCQkJY2FzZSAtMToKKwkJCQlyZXR1cm4gbWFrZV9yZXN1bHQoJmNv bnN0X3BpbmYpOworCQl9CisJCUFzc2VydChmYWxzZSk7CisJfQorCisJLyoKKwkgKiBVbnBh Y2sgdGhlIHZhbHVlcywgbGV0IG11bF92YXIoKSBjb21wdXRlIHRoZSByZXN1bHQgYW5kIHJl dHVybiBpdC4KKwkgKiBVbmxpa2UgYWRkX3ZhcigpIGFuZCBzdWJfdmFyKCksIG11bF92YXIo KSB3aWxsIHJvdW5kIGl0cyByZXN1bHQuIEluIHRoZQorCSAqIGNhc2Ugb2YgbnVtZXJpY19t dWwoKSwgd2hpY2ggaXMgaW52b2tlZCBmb3IgdGhlICogb3BlcmF0b3Igb24gbnVtZXJpY3Ms CisJICogd2UgcmVxdWVzdCBleGFjdCByZXByZXNlbnRhdGlvbiBmb3IgdGhlIHByb2R1Y3Qg KHJzY2FsZSA9IHN1bShkc2NhbGUgb2YKKwkgKiBhcmcxLCBkc2NhbGUgb2YgYXJnMikpLiAg SWYgdGhlIGV4YWN0IHJlc3VsdCBoYXMgbW9yZSBkaWdpdHMgYWZ0ZXIgdGhlCisJICogZGVj aW1hbCBwb2ludCB0aGFuIGNhbiBiZSBzdG9yZWQgaW4gYSBudW1lcmljLCB3ZSByb3VuZCBp dC4gIFJvdW5kaW5nCisJICogYWZ0ZXIgY29tcHV0aW5nIHRoZSBleGFjdCByZXN1bHQgZW5z dXJlcyB0aGF0IHRoZSBmaW5hbCByZXN1bHQgaXMKKwkgKiBjb3JyZWN0bHkgcm91bmRlZCAo cm91bmRpbmcgaW4gbXVsX3ZhcigpIHVzaW5nIGEgdHJ1bmNhdGVkIHByb2R1Y3QKKwkgKiB3 b3VsZCBub3QgZ3VhcmFudGVlIHRoaXMpLgorCSAqLworCWluaXRfdmFyX2Zyb21fbnVtKG51 bTEsICZhcmcxKTsKKwlpbml0X3Zhcl9mcm9tX251bShudW0yLCAmYXJnMik7CisKKwlpbml0 X3ZhcigmcmVzdWx0KTsKKworCW11bF92YXJfa2FyYXRzdWJhKCZhcmcxLCAmYXJnMiwgJnJl c3VsdCwgYXJnMS5kc2NhbGUgKyBhcmcyLmRzY2FsZSk7CisKKwlpZiAocmVzdWx0LmRzY2Fs ZSA+IE5VTUVSSUNfRFNDQUxFX01BWCkKKwkJcm91bmRfdmFyKCZyZXN1bHQsIE5VTUVSSUNf RFNDQUxFX01BWCk7CisKKwlyZXMgPSBtYWtlX3Jlc3VsdF9vcHRfZXJyb3IoJnJlc3VsdCwg aGF2ZV9lcnJvcik7CisKKwlmcmVlX3ZhcigmcmVzdWx0KTsKKworCXJldHVybiByZXM7Cit9 CisKKwogLyoKICAqIG51bWVyaWNfZGl2KCkgLQogICoKQEAgLTg2NTksNiArODgxOCwzNyBA QCBzdWJfdmFyKGNvbnN0IE51bWVyaWNWYXIgKnZhcjEsIGNvbnN0IE51bWVyaWNWYXIgKnZh cjIsIE51bWVyaWNWYXIgKnJlc3VsdCkKIH0KIAogCisvKgorICogc3BsaXRfdmFyX2F0KCkg LQorICoKKyAqIFNwbGl0IGEgTnVtZXJpY1ZhciBpbnRvIHR3byBwYXJ0cyBhdCBhIHNwZWNp ZmllZCBwb3NpdGlvbi4KKyAqLworaW5saW5lIHN0YXRpYyB2b2lkCitzcGxpdF92YXJfYXQo Y29uc3QgTnVtZXJpY1ZhciAqdmFyLCBpbnQgc3BsaXRfcG9pbnQsCisJCQkgTnVtZXJpY1Zh ciAqbG93LCBOdW1lcmljVmFyICpoaWdoKQoreworCWludCBoaWdoX25kaWdpdHMgPSB2YXIt Pm5kaWdpdHMgLSBzcGxpdF9wb2ludDsKKwlpbnQgbG93X25kaWdpdHMgPSBzcGxpdF9wb2lu dDsKKworCWluaXRfdmFyKGhpZ2gpOworCWluaXRfdmFyKGxvdyk7CisKKwloaWdoLT5uZGln aXRzID0gaGlnaF9uZGlnaXRzOworCWhpZ2gtPmRpZ2l0cyA9IHZhci0+ZGlnaXRzOworCWhp Z2gtPmJ1ZiA9IE5VTEw7CisJaGlnaC0+d2VpZ2h0ID0gdmFyLT53ZWlnaHQgLSBsb3dfbmRp Z2l0czsKKwloaWdoLT5zaWduID0gdmFyLT5zaWduOworCWhpZ2gtPmRzY2FsZSA9ICh2YXIt Pm5kaWdpdHMgLSB2YXItPndlaWdodCAtIDEpICogREVDX0RJR0lUUzsKKworCWxvdy0+bmRp Z2l0cyA9IGxvd19uZGlnaXRzOworCWxvdy0+ZGlnaXRzID0gdmFyLT5kaWdpdHMgKyBoaWdo X25kaWdpdHM7CisJbG93LT5idWYgPSBOVUxMOworCWxvdy0+d2VpZ2h0ID0gdmFyLT53ZWln aHQgLSBoaWdoX25kaWdpdHM7CisJbG93LT5zaWduID0gdmFyLT5zaWduOworCWxvdy0+ZHNj YWxlID0gdmFyLT5kc2NhbGU7Cit9CisKKwogLyoKICAqIG11bF92YXIoKSAtCiAgKgpAQCAt ODg2NSw2ICs5MDU1LDQxMSBAQCBtdWxfdmFyKGNvbnN0IE51bWVyaWNWYXIgKnZhcjEsIGNv bnN0IE51bWVyaWNWYXIgKnZhcjIsIE51bWVyaWNWYXIgKnJlc3VsdCwKIH0KIAogCisvKgor ICogbXVsX3Zhcl9rYXJhdHN1YmFfZnVsbCgpIC0KKyAqCisgKglNdWx0aXBsaWNhdGlvbiB1 c2luZyB0aGUgS2FyYXRzdWJhIGFsZ29yaXRobS4KKyAqCisgKglUaGUgYWxnb3JpdGhtIG5v cm1hbGx5IHN0YXJ0cyBieSBjaGVja2luZyBpZiBhbnkgb2YgdGhlIGlucHV0cworICoJYXJl IHNtYWxsZXIgdGhhbiB0aGUgTkJBU0UsIHRoZSBiYXNlIGNhc2UgZm9yIHRoZSByZWN1cnNp b24sCisgKglhbmQgaWYgc28sIGZhbGwgYmFjayB0byB0cmFkaXRpb25hbCBtdWx0aXBsaWNh dGlvbi4KKyAqCisgKglUaGF0IHBhcnQgaXMgaGFuZGxlZCBieSB0aGUgY2FsbGVyIGluIG91 ciBjb2RlLCBzbyB3aGVuIHRoaXMgZnVuY3Rpb24KKyAqCWlzIGNhbGxlZCwgd2Uga25vdyB0 aGF0IHZhcjEgYW5kIHZhcjIgYXJlIGxhcmdlIGVub3VnaCBmb3IgS2FyYXRzdWJhCisgKgl0 byBiZSB1c2VkLiBXZSBhbHNvIGtub3cgdGhhdCB2YXIxIGlzIHNob3J0ZXIgb3Igb2YgZXF1 YWwgbGVuZ3RoIGFzIHZhcjIsCisgKgl3aGljaCBoYXMgYmVlbiBhcnJhbmdlZCBieSB0aGUg Y2FsbGVyIGJ5IHN3YXBwaW5nIHRoZW0gaWYgbmVjZXNzYXJ5LgorICoKKyAqCVRoZSBhbGdv cml0aG0gdGhlbiBwcm9jZWVkcyBieSBzcGxpdHRpbmcgdmFyMSBhbmQgdmFyMiBpbnRvCisg Kgl0d28gaGlnaCBhbmQgbG93IHBhcnRzLCBhdCBoYWxmIHRoZSBsZW5ndGggb2YgdGhlIGxv bmdlciBpbnB1dDoKKyAqCisgKgkJbSA9IG1heChzaXplX05CQVNFKHZhcjEpLCBzaXplX05C QVNFKHZhcjIpKQorICoJCW0yID0gZmxvb3IobSAvIDIpCisgKgorICoJCWhpZ2gxLCBsb3cx ID0gc3BsaXRfdmFyX2F0KHZhcjEsIG0yKQorICoJCWhpZ2gyLCBsb3cyID0gc3BsaXRfdmFy X2F0KHZhcjIsIG0yKQorICoKKyAqCQl6MCA9IChsb3cxICogbG93MikKKyAqCQl6MSA9ICgo bG93MSArIGhpZ2gxKSAqIChsb3cyICsgaGlnaDIpKQorICoJCXoyID0gKGhpZ2gxICogaGln aDIpCisgKgorICoJCXJldHVybiAoejIgKiBOQkFTRSBeIChtMiDDlyAyKSkgKyAoKHoxIC0g ejIgLSB6MCkgKiBOQkFTRSBeIG0yKSArIHowCisgKi8KK3N0YXRpYyB2b2lkCittdWxfdmFy X2thcmF0c3ViYV9mdWxsKGNvbnN0IE51bWVyaWNWYXIgKnZhcjEsIGNvbnN0IE51bWVyaWNW YXIgKnZhcjIsCisJCU51bWVyaWNWYXIgKnJlc3VsdCwgaW50IHJzY2FsZSkKK3sKKwkJTnVt ZXJpY1ZhcgloaWdoMSwgbG93MTsKKwkJTnVtZXJpY1ZhcgloaWdoMiwgbG93MjsKKwkJTnVt ZXJpY1Zhcgl6MCwgejEsIHoyOworCQlOdW1lcmljVmFyCXRlbXAxLCB0ZW1wMjsKKwkJaW50 CQkJbTIgPSB2YXIyLT5uZGlnaXRzIC8gMjsKKworCQlpbml0X3ZhcigmbG93MSk7CisJCWlu aXRfdmFyKCZsb3cyKTsKKwkJaW5pdF92YXIoJmhpZ2gxKTsKKwkJaW5pdF92YXIoJmhpZ2gy KTsKKwkJaW5pdF92YXIoJnowKTsKKwkJaW5pdF92YXIoJnoxKTsKKwkJaW5pdF92YXIoJnoy KTsKKwkJaW5pdF92YXIoJnRlbXAxKTsKKwkJaW5pdF92YXIoJnRlbXAyKTsKKworCQlzcGxp dF92YXJfYXQodmFyMSwgbTIsICZsb3cxLCAmaGlnaDEpOworCQlzcGxpdF92YXJfYXQodmFy MiwgbTIsICZsb3cyLCAmaGlnaDIpOworCisJCW11bF92YXJfa2FyYXRzdWJhKCZsb3cxLCAm bG93MiwgJnowLCBsb3cxLmRzY2FsZSArIGxvdzIuZHNjYWxlKTsKKworCQlhZGRfdmFyKCZs b3cxLCAmaGlnaDEsICZ0ZW1wMSk7CisJCWFkZF92YXIoJmxvdzIsICZoaWdoMiwgJnRlbXAy KTsKKwkJbXVsX3Zhcl9rYXJhdHN1YmEoJnRlbXAxLCAmdGVtcDIsICZ6MSwgdGVtcDEuZHNj YWxlICsgdGVtcDIuZHNjYWxlKTsKKworCQltdWxfdmFyX2thcmF0c3ViYSgmaGlnaDEsICZo aWdoMiwgJnoyLCBoaWdoMS5kc2NhbGUgKyBoaWdoMi5kc2NhbGUpOworCisJCXNldF92YXJf ZnJvbV92YXIoJnoyLCAmdGVtcDEpOworCQl0ZW1wMS53ZWlnaHQgKz0gbTIgKiAyOworCisJ CXN1Yl92YXIoJnoxLCAmejIsICZ6MSk7CisJCXN1Yl92YXIoJnoxLCAmejAsICZ0ZW1wMik7 CisJCXRlbXAyLndlaWdodCArPSBtMjsKKworCQlhZGRfdmFyKCZ0ZW1wMSwgJnRlbXAyLCAm dGVtcDIpOworCQlhZGRfdmFyKCZ0ZW1wMiwgJnowLCByZXN1bHQpOworCisJCWZyZWVfdmFy KCZsb3cxKTsKKwkJZnJlZV92YXIoJmxvdzIpOworCQlmcmVlX3ZhcigmaGlnaDEpOworCQlm cmVlX3ZhcigmaGlnaDIpOworCQlmcmVlX3ZhcigmejApOworCQlmcmVlX3ZhcigmejEpOwor CQlmcmVlX3ZhcigmejIpOworCQlmcmVlX3ZhcigmdGVtcDEpOworCQlmcmVlX3ZhcigmdGVt cDIpOworCisJCS8qIFJvdW5kIHRvIHRhcmdldCByc2NhbGUgKGFuZCBzZXQgcmVzdWx0LT5k c2NhbGUpICovCisJCXJvdW5kX3ZhcihyZXN1bHQsIHJzY2FsZSk7CisKKwkJLyogU3RyaXAg bGVhZGluZyBhbmQgdHJhaWxpbmcgemVyb2VzICovCisJCXN0cmlwX3ZhcihyZXN1bHQpOwor CisJCXJldHVybjsKK30KKworCisvKgorICogbXVsX3Zhcl9rYXJhdHN1YmFfaGFsZigpIC0K KyAqCisgKglLYXJhdHN1YmEgTXVsdGlwbGljYXRpb24gZm9yIGZhY3RvcnMgd2l0aCBzaWdu aWZpY2FudCBsZW5ndGggZGlzcGFyaXR5LgorICoKKyAqCVRoZSBIYWxmLUthcmF0c3ViYSBN dWx0aXBsaWNhdGlvbiBBbGdvcml0aG0gaXMgYSBzcGVjaWFsaXplZCBjYXNlIG9mCisgKgl0 aGUgbm9ybWFsIEthcmF0c3ViYSBtdWx0aXBsaWNhdGlvbiBhbGdvcml0aG0sIGRlc2lnbmVk IGZvciB0aGUgc2NlbmFyaW8KKyAqCXdoZXJlIHZhcjIgaGFzIGF0IGxlYXN0IHR3aWNlIGFz IG1hbnkgYmFzZSBkaWdpdHMgYXMgdmFyMS4KKyAqCisgKglJbiB0aGlzIGNhc2UgdmFyMiAo dGhlIGxvbmdlciBpbnB1dCkgaXMgc3BsaXQgaW50byBoaWdoMiBhbmQgbG93MSwKKyAqCWF0 IG0yIChoYWxmIHRoZSBsZW5ndGggb2YgdmFyMikgYW5kIHZhcjEgKHRoZSBzaG9ydGVyIGlu cHV0KSwKKyAqCWlzIHVzZWQgZGlyZWN0bHkgd2l0aG91dCBzcGxpdHRpbmcuCisgKgorICoJ VGhlIGFsZ29yaXRobSB0aGVuIHByb2NlZWRzIGFzIGZvbGxvd3M6CisgKgorICoJMS4gQ29t cHV0ZSB0aGUgcHJvZHVjdCB6MCA9IHZhcjEgKiBsb3cyLgorICoJMi4gQ29tcHV0ZSB0aGUg cHJvZHVjdCB0ZW1wMiA9IHZhcjEgKiBoaWdoMi4KKyAqCTMuIEFkanVzdCB0aGUgd2VpZ2h0 IG9mIHRlbXAyIGJ5IGFkZGluZyBtMiAoKiBOQkFTRSBeIG0yKQorICoJNC4gQWRkIHRlbXAy IGFuZCB6MCB0byBvYnRhaW4gdGhlIGZpbmFsIHJlc3VsdC4KKyAqCisgKglQcm9vZjoKKyAq CisgKglUaGUgYWxnb3JpdGhtIGNhbiBiZSBkZXJpdmVkIGZyb20gdGhlIG9yaWdpbmFsIEth cmF0c3ViYSBhbGdvcml0aG0gYnkKKyAqCXNpbXBsaWZ5aW5nIHRoZSBmb3JtdWxhIHdoZW4g dGhlIHNob3J0ZXIgZmFjdG9yIHZhcjEgaXMgbm90IHNwbGl0IGludG8KKyAqCWhpZ2ggYW5k IGxvdyBwYXJ0cywgYXMgc2hvd24gYmVsb3cuCisgKgorICoJT3JpZ2luYWwgS2FyYXRzdWJh IGZvcm11bGE6CisgKgorICoJCXJlc3VsdCA9ICh6MiAqIE5CQVNFIF4gKG0yIMOXIDIpKSAr ICgoejEgLSB6MiAtIHowKSAqIE5CQVNFIF4gbTIpICsgejAKKyAqCisgKglTdWJzdGl0dXRp b25zOgorICoKKyAqCQlsb3cxID0gdmFyMQorICoJCWhpZ2gxID0gMAorICoKKyAqCUFwcGx5 aW5nIHN1YnN0aXR1dGlvbnM6CisgKgorICoJCXowID0gKGxvdzEgKiBsb3cyKQorICoJCSAg ID0gKHZhcjEgKiBsb3cyKQorICoKKyAqCQl6MSA9ICgobG93MSArIGhpZ2gxKSAqIChsb3cy ICsgaGlnaDIpKQorICoJCSAgID0gKCh2YXIxICsgMCkgKiAobG93MiArIGhpZ2gyKSkKKyAq CQkgICA9ICh2YXIxICogbG93MikgKyAodmFyMSAqIGhpZ2gyKQorICoKKyAqCQl6MiA9ICho aWdoMSAqIGhpZ2gyKQorICoJCSAgID0gKDAgKiBoaWdoMikKKyAqCQkgICA9IDAKKyAqCisg KglTaW1wbGlmaWVkIHVzaW5nIHRoZSBhYm92ZSBzdWJzdGl0dXRpb25zOgorICoKKyAqCQly ZXN1bHQgPSAoejIgKiBOQkFTRSBeIChtMiDDlyAyKSkgKyAoKHoxIC0gejIgLSB6MCkgKiBO QkFTRSBeIG0yKSArIHowCisgKgkJCSAgID0gKDAgKiBOQkFTRSBeIChtMiDDlyAyKSkgKyAo KHoxIC0gMCAtIHowKSAqIE5CQVNFIF4gbTIpICsgejAKKyAqCQkJICAgPSAoKHoxIC0gejAp ICogTkJBU0UgXiBtMikgKyB6MAorICoJCQkgICA9ICgoejEgLSB6MCkgKiBOQkFTRSBeIG0y KSArIHowCisgKgkJCSAgID0gKHZhcjEgKiBoaWdoMikgKiBOQkFTRSBeIG0yICsgejAKKyAq Lworc3RhdGljIHZvaWQKK211bF92YXJfa2FyYXRzdWJhX2hhbGYoY29uc3QgTnVtZXJpY1Zh ciAqdmFyMSwgY29uc3QgTnVtZXJpY1ZhciAqdmFyMiwKKwkJTnVtZXJpY1ZhciAqcmVzdWx0 LCBpbnQgcnNjYWxlKQoreworCU51bWVyaWNWYXIJaGlnaDIsIGxvdzI7CisJTnVtZXJpY1Zh cgl6MDsKKwlOdW1lcmljVmFyCXRlbXAyOworCWludAkJCW0yID0gdmFyMi0+bmRpZ2l0cyAv IDI7CisKKwlpbml0X3ZhcigmaGlnaDIpOworCWluaXRfdmFyKCZsb3cyKTsKKwlpbml0X3Zh cigmejApOworCWluaXRfdmFyKCZ0ZW1wMik7CisKKwlzcGxpdF92YXJfYXQodmFyMiwgbTIs ICZsb3cyLCAmaGlnaDIpOworCisJbXVsX3Zhcl9rYXJhdHN1YmEodmFyMSwgJmxvdzIsICZ6 MCwgdmFyMS0+ZHNjYWxlICsgbG93Mi5kc2NhbGUpOworCW11bF92YXJfa2FyYXRzdWJhKHZh cjEsICZoaWdoMiwgJnRlbXAyLCB2YXIxLT5kc2NhbGUgKyBoaWdoMi5kc2NhbGUpOworCXRl bXAyLndlaWdodCArPSBtMjsKKwlhZGRfdmFyKCZ0ZW1wMiwgJnowLCByZXN1bHQpOworCisJ ZnJlZV92YXIoJmhpZ2gyKTsKKwlmcmVlX3ZhcigmbG93Mik7CisJZnJlZV92YXIoJnowKTsK KwlmcmVlX3ZhcigmdGVtcDIpOworCisJLyogUm91bmQgdG8gdGFyZ2V0IHJzY2FsZSAoYW5k IHNldCByZXN1bHQtPmRzY2FsZSkgKi8KKwlyb3VuZF92YXIocmVzdWx0LCByc2NhbGUpOwor CisJLyogU3RyaXAgbGVhZGluZyBhbmQgdHJhaWxpbmcgemVyb2VzICovCisJc3RyaXBfdmFy KHJlc3VsdCk7CisKKwlyZXR1cm47Cit9CisKKworLyoKKyAqIG11bF92YXJfa2FyYXRzdWJh KCkgLQorICoKKyAqIEltcGxlbWVudHMgS2FyYXRzdWJhIG11bHRpcGxpY2F0aW9uIGZvciBs YXJnZSBudW1iZXJzLCBpbnRyb2R1Y2VkCisgKiBhbG9uZ3NpZGUgdGhlIHVuY2hhbmdlZCBv cmlnaW5hbCBtdWxfdmFyKCkuIFRoaXMgZnVuY3Rpb24gaXMgcGFydCBvZgorICogYW4gb3B0 aW1pemF0aW9uIGVmZm9ydCwgYWxsb3dpbmcgZGlyZWN0IGJlbmNobWFyayBjb21wYXJpc29u cyB3aXRoCisgKiBtdWxfdmFyKCkuIEl0IHNlbGVjdHMgZnVsbCBvciBoYWxmIEthcmF0c3Vi YSBiYXNlZCBvbiBpbnB1dCBzaXplLgorICogVGhpcyBpcyBhIHRlbXBvcmFyeSBtZWFzdXJl IGJlZm9yZSBjb25zaWRlcmluZyBpdHMgcmVwbGFjZW1lbnQgb2YKKyAqIG11bF92YXIoKSBi YXNlZCBvbiBiZW5jaG1hcmsgb3V0Y29tZXMuCisgKi8KK3N0YXRpYyB2b2lkCittdWxfdmFy X2thcmF0c3ViYShjb25zdCBOdW1lcmljVmFyICp2YXIxLCBjb25zdCBOdW1lcmljVmFyICp2 YXIyLAorCQlOdW1lcmljVmFyICpyZXN1bHQsIGludCByc2NhbGUpCit7CisJaW50CQkJcmVz X25kaWdpdHM7CisJaW50CQkJcmVzX3NpZ247CisJaW50CQkJcmVzX3dlaWdodDsKKwlpbnQJ CQltYXhkaWdpdHM7CisJaW50CQkgICAqZGlnOworCWludAkJCWNhcnJ5OworCWludAkJCW1h eGRpZzsKKwlpbnQJCQluZXdkaWc7CisJaW50CQkJdmFyMW5kaWdpdHM7CisJaW50CQkJdmFy Mm5kaWdpdHM7CisJTnVtZXJpY0RpZ2l0ICp2YXIxZGlnaXRzOworCU51bWVyaWNEaWdpdCAq dmFyMmRpZ2l0czsKKwlOdW1lcmljRGlnaXQgKnJlc19kaWdpdHM7CisJaW50CQkJaSwKKwkJ CQlpMSwKKwkJCQlpMjsKKworCS8qCisJICogQXJyYW5nZSBmb3IgdmFyMSB0byBiZSB0aGUg c2hvcnRlciBvZiB0aGUgdHdvIG51bWJlcnMuICBUaGlzIGltcHJvdmVzCisJICogcGVyZm9y bWFuY2UgYmVjYXVzZSB0aGUgaW5uZXIgbXVsdGlwbGljYXRpb24gbG9vcCBpcyBtdWNoIHNp bXBsZXIgdGhhbgorCSAqIHRoZSBvdXRlciBsb29wLCBzbyBpdCdzIGJldHRlciB0byBoYXZl IGEgc21hbGxlciBudW1iZXIgb2YgaXRlcmF0aW9ucworCSAqIG9mIHRoZSBvdXRlciBsb29w LiAgVGhpcyBhbHNvIHJlZHVjZXMgdGhlIG51bWJlciBvZiB0aW1lcyB0aGF0IHRoZQorCSAq IGFjY3VtdWxhdG9yIGFycmF5IG5lZWRzIHRvIGJlIG5vcm1hbGl6ZWQuCisJICovCisJaWYg KHZhcjEtPm5kaWdpdHMgPiB2YXIyLT5uZGlnaXRzKQorCXsKKwkJY29uc3QgTnVtZXJpY1Zh ciAqdG1wID0gdmFyMTsKKworCQl2YXIxID0gdmFyMjsKKwkJdmFyMiA9IHRtcDsKKwl9CisK KwkvKiBjb3B5IHRoZXNlIHZhbHVlcyBpbnRvIGxvY2FsIHZhcnMgZm9yIHNwZWVkIGluIGlu bmVyIGxvb3AgKi8KKwl2YXIxbmRpZ2l0cyA9IHZhcjEtPm5kaWdpdHM7CisJdmFyMm5kaWdp dHMgPSB2YXIyLT5uZGlnaXRzOworCXZhcjFkaWdpdHMgPSB2YXIxLT5kaWdpdHM7CisJdmFy MmRpZ2l0cyA9IHZhcjItPmRpZ2l0czsKKworCWlmICh2YXIxbmRpZ2l0cyA9PSAwIHx8IHZh cjJuZGlnaXRzID09IDApCisJeworCQkvKiBvbmUgb3IgYm90aCBpbnB1dHMgaXMgemVybzsg c28gaXMgcmVzdWx0ICovCisJCXplcm9fdmFyKHJlc3VsdCk7CisJCXJlc3VsdC0+ZHNjYWxl ID0gcnNjYWxlOworCQlyZXR1cm47CisJfQorCisJLyogRGV0ZXJtaW5lIHJlc3VsdCBzaWdu IGFuZCAobWF4aW11bSBwb3NzaWJsZSkgd2VpZ2h0ICovCisJaWYgKHZhcjEtPnNpZ24gPT0g dmFyMi0+c2lnbikKKwkJcmVzX3NpZ24gPSBOVU1FUklDX1BPUzsKKwllbHNlCisJCXJlc19z aWduID0gTlVNRVJJQ19ORUc7CisJcmVzX3dlaWdodCA9IHZhcjEtPndlaWdodCArIHZhcjIt PndlaWdodCArIDI7CisKKwkvKgorCSAqIERldGVybWluZSB0aGUgbnVtYmVyIG9mIHJlc3Vs dCBkaWdpdHMgdG8gY29tcHV0ZS4gIElmIHRoZSBleGFjdCByZXN1bHQKKwkgKiB3b3VsZCBo YXZlIG1vcmUgdGhhbiByc2NhbGUgZnJhY3Rpb25hbCBkaWdpdHMsIHRydW5jYXRlIHRoZSBj b21wdXRhdGlvbgorCSAqIHdpdGggTVVMX0dVQVJEX0RJR0lUUyBndWFyZCBkaWdpdHMsIGku ZS4sIGlnbm9yZSBpbnB1dCBkaWdpdHMgdGhhdAorCSAqIHdvdWxkIG9ubHkgY29udHJpYnV0 ZSB0byB0aGUgcmlnaHQgb2YgdGhhdC4gIChUaGlzIHdpbGwgZ2l2ZSB0aGUgZXhhY3QKKwkg KiByb3VuZGVkLXRvLXJzY2FsZSBhbnN3ZXIgdW5sZXNzIGNhcnJpZXMgb3V0IG9mIHRoZSBp Z25vcmVkIHBvc2l0aW9ucworCSAqIHdvdWxkIGhhdmUgcHJvcGFnYXRlZCB0aHJvdWdoIG1v cmUgdGhhbiBNVUxfR1VBUkRfRElHSVRTIGRpZ2l0cy4pCisJICoKKwkgKiBOb3RlOiBhbiBl eGFjdCBjb21wdXRhdGlvbiBjb3VsZCBub3QgcHJvZHVjZSBtb3JlIHRoYW4gdmFyMW5kaWdp dHMgKworCSAqIHZhcjJuZGlnaXRzIGRpZ2l0cywgYnV0IHdlIGFsbG9jYXRlIG9uZSBleHRy YSBvdXRwdXQgZGlnaXQgaW4gY2FzZQorCSAqIHJzY2FsZS1kcml2ZW4gcm91bmRpbmcgcHJv ZHVjZXMgYSBjYXJyeSBvdXQgb2YgdGhlIGhpZ2hlc3QgZXhhY3QgZGlnaXQuCisJICovCisJ cmVzX25kaWdpdHMgPSB2YXIxbmRpZ2l0cyArIHZhcjJuZGlnaXRzICsgMTsKKwltYXhkaWdp dHMgPSByZXNfd2VpZ2h0ICsgMSArIChyc2NhbGUgKyBERUNfRElHSVRTIC0gMSkgLyBERUNf RElHSVRTICsKKwkJTVVMX0dVQVJEX0RJR0lUUzsKKwlyZXNfbmRpZ2l0cyA9IE1pbihyZXNf bmRpZ2l0cywgbWF4ZGlnaXRzKTsKKworCWlmIChyZXNfbmRpZ2l0cyA8IDMpCisJeworCQkv KiBBbGwgaW5wdXQgZGlnaXRzIHdpbGwgYmUgaWdub3JlZDsgc28gcmVzdWx0IGlzIHplcm8g Ki8KKwkJemVyb192YXIocmVzdWx0KTsKKwkJcmVzdWx0LT5kc2NhbGUgPSByc2NhbGU7CisJ CXJldHVybjsKKwl9CisKKwkvKgorCSAqIFVzZSB0aGUgS2FyYXRzdWJhIGFsZ29yaXRobSBm b3Igc3VmZmljaWVudGx5IGxhcmdlIGZhY3RvcnMuCisJICovCisJaWYgKEtBUkFUU1VCQV9D T05ESVRJT04odmFyMW5kaWdpdHMsIHZhcjJuZGlnaXRzKSkKKwl7CisJCWlmICh2YXIxbmRp Z2l0cyAqIDIgPiB2YXIybmRpZ2l0cykKKwkJCW11bF92YXJfa2FyYXRzdWJhX2Z1bGwodmFy MSwgdmFyMiwgcmVzdWx0LCByc2NhbGUpOworCQllbHNlCisJCQltdWxfdmFyX2thcmF0c3Vi YV9oYWxmKHZhcjEsIHZhcjIsIHJlc3VsdCwgcnNjYWxlKTsKKwkJcmV0dXJuOworCX0KKwor CS8qCisJICogV2UgZG8gdGhlIGFyaXRobWV0aWMgaW4gYW4gYXJyYXkgImRpZ1tdIiBvZiBz aWduZWQgaW50J3MuICBTaW5jZQorCSAqIElOVF9NQVggaXMgbm90aWNlYWJseSBsYXJnZXIg dGhhbiBOQkFTRSpOQkFTRSwgdGhpcyBnaXZlcyB1cyBoZWFkcm9vbQorCSAqIHRvIGF2b2lk IG5vcm1hbGl6aW5nIGNhcnJpZXMgaW1tZWRpYXRlbHkuCisJICoKKwkgKiBtYXhkaWcgdHJh Y2tzIHRoZSBtYXhpbXVtIHBvc3NpYmxlIHZhbHVlIG9mIGFueSBkaWdbXSBlbnRyeTsgd2hl biB0aGlzCisJICogdGhyZWF0ZW5zIHRvIGV4Y2VlZCBJTlRfTUFYLCB3ZSB0YWtlIHRoZSB0 aW1lIHRvIHByb3BhZ2F0ZSBjYXJyaWVzLgorCSAqIEZ1cnRoZXJtb3JlLCB3ZSBuZWVkIHRv IGVuc3VyZSB0aGF0IG92ZXJmbG93IGRvZXNuJ3Qgb2NjdXIgZHVyaW5nIHRoZQorCSAqIGNh cnJ5IHByb3BhZ2F0aW9uIHBhc3NlcyBlaXRoZXIuICBUaGUgY2FycnkgdmFsdWVzIGNvdWxk IGJlIGFzIG11Y2ggYXMKKwkgKiBJTlRfTUFYL05CQVNFLCBzbyByZWFsbHkgd2UgbXVzdCBu b3JtYWxpemUgd2hlbiBkaWdpdHMgdGhyZWF0ZW4gdG8KKwkgKiBleGNlZWQgSU5UX01BWCAt IElOVF9NQVgvTkJBU0UuCisJICoKKwkgKiBUbyBhdm9pZCBvdmVyZmxvdyBpbiBtYXhkaWcg aXRzZWxmLCBpdCBhY3R1YWxseSByZXByZXNlbnRzIHRoZSBtYXgKKwkgKiBwb3NzaWJsZSB2 YWx1ZSBkaXZpZGVkIGJ5IE5CQVNFLTEsIGllLCBhdCB0aGUgdG9wIG9mIHRoZSBsb29wIGl0 IGlzCisJICoga25vd24gdGhhdCBubyBkaWdbXSBlbnRyeSBleGNlZWRzIG1heGRpZyAqIChO QkFTRS0xKS4KKwkgKi8KKwlkaWcgPSAoaW50ICopIHBhbGxvYzAocmVzX25kaWdpdHMgKiBz aXplb2YoaW50KSk7CisJbWF4ZGlnID0gMDsKKworCS8qCisJICogVGhlIGxlYXN0IHNpZ25p ZmljYW50IGRpZ2l0cyBvZiB2YXIxIHNob3VsZCBiZSBpZ25vcmVkIGlmIHRoZXkgZG9uJ3QK KwkgKiBjb250cmlidXRlIGRpcmVjdGx5IHRvIHRoZSBmaXJzdCByZXNfbmRpZ2l0cyBkaWdp dHMgb2YgdGhlIHJlc3VsdCB0aGF0CisJICogd2UgYXJlIGNvbXB1dGluZy4KKwkgKgorCSAq IERpZ2l0IGkxIG9mIHZhcjEgYW5kIGRpZ2l0IGkyIG9mIHZhcjIgYXJlIG11bHRpcGxpZWQg YW5kIGFkZGVkIHRvIGRpZ2l0CisJICogaTEraTIrMiBvZiB0aGUgYWNjdW11bGF0b3IgYXJy YXksIHNvIHdlIG5lZWQgb25seSBjb25zaWRlciBkaWdpdHMgb2YKKwkgKiB2YXIxIGZvciB3 aGljaCBpMSA8PSByZXNfbmRpZ2l0cyAtIDMuCisJICovCisJZm9yIChpMSA9IE1pbih2YXIx bmRpZ2l0cyAtIDEsIHJlc19uZGlnaXRzIC0gMyk7IGkxID49IDA7IGkxLS0pCisJeworCQlO dW1lcmljRGlnaXQgdmFyMWRpZ2l0ID0gdmFyMWRpZ2l0c1tpMV07CisKKwkJaWYgKHZhcjFk aWdpdCA9PSAwKQorCQkJY29udGludWU7CisKKwkJLyogVGltZSB0byBub3JtYWxpemU/ICov CisJCW1heGRpZyArPSB2YXIxZGlnaXQ7CisJCWlmIChtYXhkaWcgPiAoSU5UX01BWCAtIElO VF9NQVggLyBOQkFTRSkgLyAoTkJBU0UgLSAxKSkKKwkJeworCQkJLyogWWVzLCBkbyBpdCAq LworCQkJY2FycnkgPSAwOworCQkJZm9yIChpID0gcmVzX25kaWdpdHMgLSAxOyBpID49IDA7 IGktLSkKKwkJCXsKKwkJCQluZXdkaWcgPSBkaWdbaV0gKyBjYXJyeTsKKwkJCQlpZiAobmV3 ZGlnID49IE5CQVNFKQorCQkJCXsKKwkJCQkJY2FycnkgPSBuZXdkaWcgLyBOQkFTRTsKKwkJ CQkJbmV3ZGlnIC09IGNhcnJ5ICogTkJBU0U7CisJCQkJfQorCQkJCWVsc2UKKwkJCQkJY2Fy cnkgPSAwOworCQkJCWRpZ1tpXSA9IG5ld2RpZzsKKwkJCX0KKwkJCUFzc2VydChjYXJyeSA9 PSAwKTsKKwkJCS8qIFJlc2V0IG1heGRpZyB0byBpbmRpY2F0ZSBuZXcgd29yc3QtY2FzZSAq LworCQkJbWF4ZGlnID0gMSArIHZhcjFkaWdpdDsKKwkJfQorCisJCS8qCisJCSAqIEFkZCB0 aGUgYXBwcm9wcmlhdGUgbXVsdGlwbGUgb2YgdmFyMiBpbnRvIHRoZSBhY2N1bXVsYXRvci4K KwkJICoKKwkJICogQXMgYWJvdmUsIGRpZ2l0cyBvZiB2YXIyIGNhbiBiZSBpZ25vcmVkIGlm IHRoZXkgZG9uJ3QgY29udHJpYnV0ZSwKKwkJICogc28gd2Ugb25seSBpbmNsdWRlIGRpZ2l0 cyBmb3Igd2hpY2ggaTEraTIrMiA8IHJlc19uZGlnaXRzLgorCQkgKgorCQkgKiBUaGlzIGlu bmVyIGxvb3AgaXMgdGhlIHBlcmZvcm1hbmNlIGJvdHRsZW5lY2sgZm9yIG11bHRpcGxpY2F0 aW9uLAorCQkgKiBzbyB3ZSB3YW50IHRvIGtlZXAgaXQgc2ltcGxlIGVub3VnaCBzbyB0aGF0 IGl0IGNhbiBiZQorCQkgKiBhdXRvLXZlY3Rvcml6ZWQuICBBY2NvcmRpbmdseSwgcHJvY2Vz cyB0aGUgZGlnaXRzIGxlZnQtdG8tcmlnaHQKKwkJICogZXZlbiB0aG91Z2ggc2Nob29sYm9v ayBtdWx0aXBsaWNhdGlvbiB3b3VsZCBzdWdnZXN0IHJpZ2h0LXRvLWxlZnQuCisJCSAqIFNp bmNlIHdlIGFyZW4ndCBwcm9wYWdhdGluZyBjYXJyaWVzIGluIHRoaXMgbG9vcCwgdGhlIG9y ZGVyIGRvZXMKKwkJICogbm90IG1hdHRlci4KKwkJICovCisJCXsKKwkJCWludAkJCWkybGlt aXQgPSBNaW4odmFyMm5kaWdpdHMsIHJlc19uZGlnaXRzIC0gaTEgLSAyKTsKKwkJCWludAkJ ICAgKmRpZ19pMV8yID0gJmRpZ1tpMSArIDJdOworCisJCQlmb3IgKGkyID0gMDsgaTIgPCBp MmxpbWl0OyBpMisrKQorCQkJCWRpZ19pMV8yW2kyXSArPSB2YXIxZGlnaXQgKiB2YXIyZGln aXRzW2kyXTsKKwkJfQorCX0KKworCS8qCisJICogTm93IHdlIGRvIGEgZmluYWwgY2Fycnkg cHJvcGFnYXRpb24gcGFzcyB0byBub3JtYWxpemUgdGhlIHJlc3VsdCwgd2hpY2gKKwkgKiB3 ZSBjb21iaW5lIHdpdGggc3RvcmluZyB0aGUgcmVzdWx0IGRpZ2l0cyBpbnRvIHRoZSBvdXRw dXQuIE5vdGUgdGhhdAorCSAqIHRoaXMgaXMgc3RpbGwgZG9uZSBhdCBmdWxsIHByZWNpc2lv biB3L2d1YXJkIGRpZ2l0cy4KKwkgKi8KKwlhbGxvY192YXIocmVzdWx0LCByZXNfbmRpZ2l0 cyk7CisJcmVzX2RpZ2l0cyA9IHJlc3VsdC0+ZGlnaXRzOworCWNhcnJ5ID0gMDsKKwlmb3Ig KGkgPSByZXNfbmRpZ2l0cyAtIDE7IGkgPj0gMDsgaS0tKQorCXsKKwkJbmV3ZGlnID0gZGln W2ldICsgY2Fycnk7CisJCWlmIChuZXdkaWcgPj0gTkJBU0UpCisJCXsKKwkJCWNhcnJ5ID0g bmV3ZGlnIC8gTkJBU0U7CisJCQluZXdkaWcgLT0gY2FycnkgKiBOQkFTRTsKKwkJfQorCQll bHNlCisJCQljYXJyeSA9IDA7CisJCXJlc19kaWdpdHNbaV0gPSBuZXdkaWc7CisJfQorCUFz c2VydChjYXJyeSA9PSAwKTsKKworCXBmcmVlKGRpZyk7CisKKwkvKgorCSAqIEZpbmFsbHks IHJvdW5kIHRoZSByZXN1bHQgdG8gdGhlIHJlcXVlc3RlZCBwcmVjaXNpb24uCisJICovCisJ cmVzdWx0LT53ZWlnaHQgPSByZXNfd2VpZ2h0OworCXJlc3VsdC0+c2lnbiA9IHJlc19zaWdu OworCisJLyogUm91bmQgdG8gdGFyZ2V0IHJzY2FsZSAoYW5kIHNldCByZXN1bHQtPmRzY2Fs ZSkgKi8KKwlyb3VuZF92YXIocmVzdWx0LCByc2NhbGUpOworCisJLyogU3RyaXAgbGVhZGlu ZyBhbmQgdHJhaWxpbmcgemVyb2VzICovCisJc3RyaXBfdmFyKHJlc3VsdCk7CisKK30KKwor CiAvKgogICogZGl2X3ZhcigpIC0KICAqCmRpZmYgLS1naXQgYS9zcmMvaW5jbHVkZS9jYXRh bG9nL3BnX3Byb2MuZGF0IGIvc3JjL2luY2x1ZGUvY2F0YWxvZy9wZ19wcm9jLmRhdAppbmRl eCAxNTNkODE2YTA1Li5jYWI2ZmI4MjM4IDEwMDY0NAotLS0gYS9zcmMvaW5jbHVkZS9jYXRh bG9nL3BnX3Byb2MuZGF0CisrKyBiL3NyYy9pbmNsdWRlL2NhdGFsb2cvcGdfcHJvYy5kYXQK QEAgLTQ0NjUsNiArNDQ2NSw5IEBACiB7IG9pZCA9PiAnMTcyNicsCiAgIHByb25hbWUgPT4g J251bWVyaWNfbXVsJywgcHJvcmV0dHlwZSA9PiAnbnVtZXJpYycsCiAgIHByb2FyZ3R5cGVz ID0+ICdudW1lcmljIG51bWVyaWMnLCBwcm9zcmMgPT4gJ251bWVyaWNfbXVsJyB9LAoreyBv aWQgPT4gJzYzMTInLAorICBwcm9uYW1lID0+ICdudW1lcmljX211bF9rYXJhdHN1YmEnLCBw cm9yZXR0eXBlID0+ICdudW1lcmljJywKKyAgcHJvYXJndHlwZXMgPT4gJ251bWVyaWMgbnVt ZXJpYycsIHByb3NyYyA9PiAnbnVtZXJpY19tdWxfa2FyYXRzdWJhJyB9LAogeyBvaWQgPT4g JzE3MjcnLAogICBwcm9uYW1lID0+ICdudW1lcmljX2RpdicsIHByb3JldHR5cGUgPT4gJ251 bWVyaWMnLAogICBwcm9hcmd0eXBlcyA9PiAnbnVtZXJpYyBudW1lcmljJywgcHJvc3JjID0+ ICdudW1lcmljX2RpdicgfSwKZGlmZiAtLWdpdCBhL3NyYy9pbmNsdWRlL3V0aWxzL251bWVy aWMuaCBiL3NyYy9pbmNsdWRlL3V0aWxzL251bWVyaWMuaAppbmRleCA0M2M3NWM0MzZmLi4y YjIxNGE3NzAwIDEwMDY0NAotLS0gYS9zcmMvaW5jbHVkZS91dGlscy9udW1lcmljLmgKKysr IGIvc3JjL2luY2x1ZGUvdXRpbHMvbnVtZXJpYy5oCkBAIC05Nyw2ICs5Nyw4IEBAIGV4dGVy biBOdW1lcmljIG51bWVyaWNfc3ViX29wdF9lcnJvcihOdW1lcmljIG51bTEsIE51bWVyaWMg bnVtMiwKIAkJCQkJCQkJCSBib29sICpoYXZlX2Vycm9yKTsKIGV4dGVybiBOdW1lcmljIG51 bWVyaWNfbXVsX29wdF9lcnJvcihOdW1lcmljIG51bTEsIE51bWVyaWMgbnVtMiwKIAkJCQkJ CQkJCSBib29sICpoYXZlX2Vycm9yKTsKK2V4dGVybiBOdW1lcmljIG51bWVyaWNfbXVsX2th cmF0c3ViYV9vcHRfZXJyb3IoTnVtZXJpYyBudW0xLCBOdW1lcmljIG51bTIsCisJCQkJCQkJ CQkgYm9vbCAqaGF2ZV9lcnJvcik7CiBleHRlcm4gTnVtZXJpYyBudW1lcmljX2Rpdl9vcHRf ZXJyb3IoTnVtZXJpYyBudW0xLCBOdW1lcmljIG51bTIsCiAJCQkJCQkJCQkgYm9vbCAqaGF2 ZV9lcnJvcik7CiBleHRlcm4gTnVtZXJpYyBudW1lcmljX21vZF9vcHRfZXJyb3IoTnVtZXJp YyBudW0xLCBOdW1lcmljIG51bTIsCg== --1fe2dc603a1541548bd694b5363b4c7c--