From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-5.2 required=3.0 tests=BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS, URIBL_BLOCKED,USER_AGENT_SANE_1 autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 02F03C4741F for ; Thu, 5 Nov 2020 16:53:15 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id A8BA52073A for ; Thu, 5 Nov 2020 16:53:14 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726557AbgKEQxN (ORCPT ); Thu, 5 Nov 2020 11:53:13 -0500 Received: from foss.arm.com ([217.140.110.172]:37266 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726214AbgKEQxN (ORCPT ); Thu, 5 Nov 2020 11:53:13 -0500 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id A5DFC142F; Thu, 5 Nov 2020 08:53:12 -0800 (PST) Received: from arm.com (usa-sjc-imap-foss1.foss.arm.com [10.121.207.14]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 7024C3F719; Thu, 5 Nov 2020 08:53:11 -0800 (PST) Date: Thu, 5 Nov 2020 16:53:07 +0000 From: Dave Martin To: l00374334 Cc: herbert@gondor.apana.org.au, davem@davemloft.net, catalin.marinas@arm.com, will@kernel.org, mcoquelin.stm32@gmail.com, alexandre.torgue@st.com, linux-crypto@vger.kernel.org, linux-arm-kernel@lists.infradead.org Subject: Re: [PATCH 0/1] arm64: Accelerate Adler32 using arm64 SVE instructions. Message-ID: <20201105165301.GH6882@arm.com> References: <20201103121506.1533-1-liqiang64@huawei.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <20201103121506.1533-1-liqiang64@huawei.com> User-Agent: Mutt/1.5.23 (2014-03-12) Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org On Tue, Nov 03, 2020 at 08:15:05PM +0800, l00374334 wrote: > From: liqiang > > Dear all, > > Thank you for taking the precious time to read this email! > > Let me introduce the implementation ideas of my code here. > > In the process of using the compression library libz, I found that the adler32 > checksum always occupies a higher hot spot, so I paid attention to this algorithm. > After getting in touch with the SVE instruction set of armv8, I realized that > SVE can effectively accelerate adler32, so I made some attempts and got correct > and better performance results. I very much hope that this modification can be > applied to the kernel. > > Below is my analysis process: > > Adler32 algorithm > ================= > > Reference: https://en.wikipedia.org/wiki/Adler-32 > > Assume that the buf of the Adler32 checksum to be calculated is D and the length is n: > > A = 1 + D1 + D2 + ... + Dn (mod 65521) > > B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521) > = n×D1 + (n−1)×D2 + (n−2)×D3 + ... + Dn + n (mod 65521) > > Adler-32(D) = B × 65536 + A > > In C, an inefficient but straightforward implementation is: > > const uint32_t MOD_ADLER = 65521; > > uint32_t adler32(unsigned char *data, size_t len) > { > uint32_t a = 1, b = 0; > size_t index; > > // Process each byte of the data in order > for (index = 0; index < len; ++index) > { > a = (a + data[index]) % MOD_ADLER; > b = (b + a) % MOD_ADLER; > } > > return (b << 16) | a; > } > > SVE vector method > ================= > > Step 1. Determine the block size: > Use addvl instruction to get SVE bit width. > Assuming the SVE bit width is x here. > > Step 2. Start to calculate the first block: > The calculation formula is: > A1 = 1 + D1 + D2 + ... + Dx (mod 65521) > B1 = x*D1 + (x-1)*D2 + ... + Dx + x (mod 65521) > > Step 3. Calculate the follow block: > The calculation formula of A2 is very simple, just add up: > A2 = A1 + Dx+1 + Dx+2 + ... + D2x (mod 65521) > > The calculation formula of B2 is more complicated, because > the result is related to the length of buf. When calculating > the B1 block, it is actually assumed that the length is the > block length x. Now when calculating B2, the length is expanded > to 2x, so B2 becomes: > B2 = 2x*D1 + (2x-1)*D2 + ... + (x+1)*Dx + x*D(x+1) + ... + D2x + 2x > = x*D1 + x*D1 + x*D2 + (x-1)*D2 + ... + x*Dx + Dx + x*1 + x + [x*D(x+1) + (x-1)*D(x+2) + ... + D2x] > ^^^^ ~~~~ ^^^^ ~~~~~~~~ ^^^^ ~~ ^^^ ~ +++++++++++++++++++++++++++++++++++++ > Through the above polynomial transformation: > Symbol "^" represents the ; > Symbol "~" represents the ; > Symbol "+" represents the next block. > > So we can get the method of calculating the next block from > the previous block(Assume that the first byte number of the > new block starts from 1): > An+1 = An + D1 + D2 + ... + Dx (mod 65521) > Bn+1 = Bn + x*An + x*D1 + (x-1)*D2 + ... + Dx (mod 65521) Putting aside people's concerns for the moment, I think this may be formulated in a slightly more convenient way: If X0, X1, ... are the data bytes An is 1 + Sum [i=0 .. n-1] Xi Bn is n + Sum [i=0 .. n-1] (n-i)Xi = Sum [i=1 .. n] Ai (i.e., An, Bn are the accumulations for the first n bytes here, not the first n blocks) then A[n+v] - An = Sum[i=n .. n+v-1] Xi B[n+v] - Bn = v + (Sum [i=0 .. n+v-1] (n+v-i) Xi) - Sum [i=0 .. n-1] (n-i)Xi = v + (Sum [i=n .. n+v-1] (n+v-i) Xi) + (Sum [i=0 .. n-1] (n+v-i) Xi) - Sum [i=0 .. n-1] (n-i)Xi = v + (Sum [i=n .. n+v-1] (n+v-i) Xi) + Sum [i=0 .. n-1] ((n+v-i) - (n-i)) Xi = v + (Sum [i=n .. n+v-1] (n+v-i) Xi) + vSum [i=0 .. n-1] Xi = v + v(An - 1) + Sum [i=n .. n+v-1] (n+v-i) Xi = vAn + Sum [i=n .. n+v-1] (n+v-i) Xi = vAn + vSum [i=n .. n+v-1] Xi + Sum [i=n .. n+v-1] (n-i) Xi = vAn + vSum [i=n .. n+v-1] Xi + Sum [i=n .. n+v-1] (n-i) Xi = vA[n+v] + Sum [i=n .. n+v-1] (n-i) Xi Let j = i - n; then: B[n+v] - Bn = vA[n+v] - Sum [j=0 .. v-1] j X[j+n] Which gives us a multiplier j that increases with the X[] index. I think this gives a core loop along the following lines. I don't know whether this is correct, or whether it works -- but feel free to take ideas from it if it helps. Accumulators are 32 bits. This provides for a fair number of iterations without overflow, but large input data will still require splitting into chunks, with modulo reduction steps in between. There are rather a lot of serial dependencies in the core loop, but since the operations involved are relatively cheap, this is probably not a significant issue in practice: the load-to-use dependency is probably the bigger concern. Pipelined loop unrolling could address these if necessary. The horizontal reductions (UADDV) still probably don't need to be done until after the last chunk. Beware: I wasn't careful with the initial values for Bn / An, so some additional adjustments might be needed... --8<-- ptrue pP.s ptrue pA.s mov zA.s, #0 // accumulator for An mov zB.s, #0 // accumulator for Bn index zJ.s, #0, #1 // zJ.s = [0, 1, .. V-1] mov zV.s, #0 incw zV.s // zV.s = [V, V, .. V] // where V is number of elements per block // = the number of 32-bit elements that fit in a Z-register add xLimit, xX, xLen b start loop: ld1b zX.s, pP/z, [xX] incw xX add zA.s, pP/m, zA.s, zX.s // zA.s += zX.s msb zX.s, pP/m, zJ.s, zB.s // zX.s := zB.s - zX.s * zJ.s movprfx zB, zA mad zB.s, pP/m, zV.s, zX.s // zB.s := zX.s + zA.s * V start: whilelo pP.s, xX, xLimit b.first loop // Collect the partial sums together: uaddv d0, pA, z0.s uaddv d1, pA, z1.s // Finally, add 1 to d0, and xLen to d1, and do modulo reduction. -->8-- [...] Cheers ---Dave From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-5.2 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED,USER_AGENT_SANE_1 autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 835CAC4741F for ; Thu, 5 Nov 2020 16:54:05 +0000 (UTC) Received: from merlin.infradead.org (merlin.infradead.org [205.233.59.134]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 009A220759 for ; Thu, 5 Nov 2020 16:54:04 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=lists.infradead.org header.i=@lists.infradead.org header.b="IMDyyfBo" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 009A220759 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=arm.com Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=merlin.20170209; h=Sender:Content-Transfer-Encoding: Content-Type:Cc:List-Subscribe:List-Help:List-Post:List-Archive: List-Unsubscribe:List-Id:In-Reply-To:MIME-Version:References:Message-ID: Subject:To:From:Date:Reply-To:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Owner; bh=RTEGM+J/9NxKXn0sGEt0le9QoQIekdYk5+8ZH9QOsqs=; b=IMDyyfBoVnEyux3J90ml8Ptag kHBTXpJ7zgARO91RM6uJm45bWbX88KJOmwMgpYY2V1D4wuNXeMbaCODbGSlGPYx96Zd4i1CozCen+ cwSLqGJfiKko97U1nlQkc/DSF2GigerFQXEsv+5c0evHQHmVg2RxFnZb2AiCOAHOYYneYHWTo5pj/ YC4sWuzeR8SMF3wLnAtBr8nzc1Rjpia/1w4qAhSCh7MZBsAmkKiIxo86d6dU5J6GOeSo77eHNbQhC O0JoFvf5Rl3c94VmcQt2s0qWfjCDOBkCfZIT79jnGTnSqxtX8K6RhCiQjvcc3ZtRAX6DquYdxrSil 0Pc/5xaSg==; Received: from localhost ([::1] helo=merlin.infradead.org) by merlin.infradead.org with esmtp (Exim 4.92.3 #3 (Red Hat Linux)) id 1kaiVk-0007iS-1m; Thu, 05 Nov 2020 16:53:20 +0000 Received: from foss.arm.com ([217.140.110.172]) by merlin.infradead.org with esmtp (Exim 4.92.3 #3 (Red Hat Linux)) id 1kaiVg-0007hk-9i for linux-arm-kernel@lists.infradead.org; Thu, 05 Nov 2020 16:53:18 +0000 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id A5DFC142F; Thu, 5 Nov 2020 08:53:12 -0800 (PST) Received: from arm.com (usa-sjc-imap-foss1.foss.arm.com [10.121.207.14]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 7024C3F719; Thu, 5 Nov 2020 08:53:11 -0800 (PST) Date: Thu, 5 Nov 2020 16:53:07 +0000 From: Dave Martin To: l00374334 Subject: Re: [PATCH 0/1] arm64: Accelerate Adler32 using arm64 SVE instructions. Message-ID: <20201105165301.GH6882@arm.com> References: <20201103121506.1533-1-liqiang64@huawei.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20201103121506.1533-1-liqiang64@huawei.com> User-Agent: Mutt/1.5.23 (2014-03-12) X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20201105_115316_574396_E4B08596 X-CRM114-Status: GOOD ( 31.40 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: alexandre.torgue@st.com, catalin.marinas@arm.com, linux-crypto@vger.kernel.org, mcoquelin.stm32@gmail.com, will@kernel.org, davem@davemloft.net, linux-arm-kernel@lists.infradead.org, herbert@gondor.apana.org.au Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: base64 Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org T24gVHVlLCBOb3YgMDMsIDIwMjAgYXQgMDg6MTU6MDVQTSArMDgwMCwgbDAwMzc0MzM0IHdyb3Rl Ogo+IEZyb206IGxpcWlhbmcgPGxpcWlhbmc2NEBodWF3ZWkuY29tPgo+IAo+IERlYXIgYWxsLAo+ IAo+IFRoYW5rIHlvdSBmb3IgdGFraW5nIHRoZSBwcmVjaW91cyB0aW1lIHRvIHJlYWQgdGhpcyBl bWFpbCEKPiAKPiBMZXQgbWUgaW50cm9kdWNlIHRoZSBpbXBsZW1lbnRhdGlvbiBpZGVhcyBvZiBt eSBjb2RlIGhlcmUuCj4gCj4gSW4gdGhlIHByb2Nlc3Mgb2YgdXNpbmcgdGhlIGNvbXByZXNzaW9u IGxpYnJhcnkgbGlieiwgSSBmb3VuZCB0aGF0IHRoZSBhZGxlcjMyCj4gY2hlY2tzdW0gYWx3YXlz IG9jY3VwaWVzIGEgaGlnaGVyIGhvdCBzcG90LCBzbyBJIHBhaWQgYXR0ZW50aW9uIHRvIHRoaXMg YWxnb3JpdGhtLgo+IEFmdGVyIGdldHRpbmcgaW4gdG91Y2ggd2l0aCB0aGUgU1ZFIGluc3RydWN0 aW9uIHNldCBvZiBhcm12OCwgSSByZWFsaXplZCB0aGF0Cj4gU1ZFIGNhbiBlZmZlY3RpdmVseSBh Y2NlbGVyYXRlIGFkbGVyMzIsIHNvIEkgbWFkZSBzb21lIGF0dGVtcHRzIGFuZCBnb3QgY29ycmVj dAo+IGFuZCBiZXR0ZXIgcGVyZm9ybWFuY2UgcmVzdWx0cy4gSSB2ZXJ5IG11Y2ggaG9wZSB0aGF0 IHRoaXMgbW9kaWZpY2F0aW9uIGNhbiBiZQo+IGFwcGxpZWQgdG8gdGhlIGtlcm5lbC4KPiAKPiBC ZWxvdyBpcyBteSBhbmFseXNpcyBwcm9jZXNzOgo+IAo+IEFkbGVyMzIgYWxnb3JpdGhtCj4gPT09 PT09PT09PT09PT09PT0KPiAKPiBSZWZlcmVuY2U6IGh0dHBzOi8vZW4ud2lraXBlZGlhLm9yZy93 aWtpL0FkbGVyLTMyCj4gCj4gQXNzdW1lIHRoYXQgdGhlIGJ1ZiBvZiB0aGUgQWRsZXIzMiBjaGVj a3N1bSB0byBiZSBjYWxjdWxhdGVkIGlzIEQgYW5kIHRoZSBsZW5ndGggaXMgbjoKPiAKPiAgICAg ICAgIEEgPSAxICsgRDEgKyBEMiArIC4uLiArIERuIChtb2QgNjU1MjEpCj4gCj4gICAgICAgICBC ID0gKDEgKyBEMSkgKyAoMSArIEQxICsgRDIpICsgLi4uICsgKDEgKyBEMSArIEQyICsgLi4uICsg RG4pIChtb2QgNjU1MjEpCj4gICAgICAgICAgID0gbsOXRDEgKyAobuKIkjEpw5dEMiArIChu4oiS MinDl0QzICsgLi4uICsgRG4gKyBuIChtb2QgNjU1MjEpCj4gCj4gICAgICAgICBBZGxlci0zMihE KSA9IEIgw5cgNjU1MzYgKyBBCj4gCj4gSW4gQywgYW4gaW5lZmZpY2llbnQgYnV0IHN0cmFpZ2h0 Zm9yd2FyZCBpbXBsZW1lbnRhdGlvbiBpczoKPiAKPiAgICAgICAgIGNvbnN0IHVpbnQzMl90IE1P RF9BRExFUiA9IDY1NTIxOwo+IAo+ICAgICAgICAgdWludDMyX3QgYWRsZXIzMih1bnNpZ25lZCBj aGFyICpkYXRhLCBzaXplX3QgbGVuKQo+ICAgICAgICAgewo+ICAgICAgICAgICAgICAgICB1aW50 MzJfdCBhID0gMSwgYiA9IDA7Cj4gICAgICAgICAgICAgICAgIHNpemVfdCBpbmRleDsKPiAKPiAg ICAgICAgICAgICAgICAgLy8gUHJvY2VzcyBlYWNoIGJ5dGUgb2YgdGhlIGRhdGEgaW4gb3JkZXIK PiAgICAgICAgICAgICAgICAgZm9yIChpbmRleCA9IDA7IGluZGV4IDwgbGVuOyArK2luZGV4KQo+ ICAgICAgICAgICAgICAgICB7Cj4gICAgICAgICAgICAgICAgICAgICAgICAgYSA9IChhICsgZGF0 YVtpbmRleF0pICUgTU9EX0FETEVSOwo+ICAgICAgICAgICAgICAgICAgICAgICAgIGIgPSAoYiAr IGEpICUgTU9EX0FETEVSOwo+ICAgICAgICAgICAgICAgICB9Cj4gCj4gICAgICAgICAgICAgICAg IHJldHVybiAoYiA8PCAxNikgfCBhOwo+ICAgICAgICAgfQo+IAo+IFNWRSB2ZWN0b3IgbWV0aG9k Cj4gPT09PT09PT09PT09PT09PT0KPiAKPiBTdGVwIDEuIERldGVybWluZSB0aGUgYmxvY2sgc2l6 ZToKPiAgICAgICAgIFVzZSBhZGR2bCBpbnN0cnVjdGlvbiB0byBnZXQgU1ZFIGJpdCB3aWR0aC4K PiAgICAgICAgIEFzc3VtaW5nIHRoZSBTVkUgYml0IHdpZHRoIGlzIHggaGVyZS4KPiAKPiBTdGVw IDIuIFN0YXJ0IHRvIGNhbGN1bGF0ZSB0aGUgZmlyc3QgYmxvY2s6Cj4gICAgICAgICBUaGUgY2Fs Y3VsYXRpb24gZm9ybXVsYSBpczoKPiAgICAgICAgICAgICAgICAgQTEgPSAxICsgRDEgKyBEMiAr IC4uLiArIER4IChtb2QgNjU1MjEpCj4gICAgICAgICAgICAgICAgIEIxID0geCpEMSArICh4LTEp KkQyICsgLi4uICsgRHggKyB4IChtb2QgNjU1MjEpCj4gCj4gU3RlcCAzLiBDYWxjdWxhdGUgdGhl IGZvbGxvdyBibG9jazoKPiAgICAgICAgIFRoZSBjYWxjdWxhdGlvbiBmb3JtdWxhIG9mIEEyIGlz IHZlcnkgc2ltcGxlLCBqdXN0IGFkZCB1cDoKPiAgICAgICAgICAgICAgICAgQTIgPSBBMSArIER4 KzEgKyBEeCsyICsgLi4uICsgRDJ4IChtb2QgNjU1MjEpCj4gCj4gICAgICAgICBUaGUgY2FsY3Vs YXRpb24gZm9ybXVsYSBvZiBCMiBpcyBtb3JlIGNvbXBsaWNhdGVkLCBiZWNhdXNlCj4gICAgICAg ICB0aGUgcmVzdWx0IGlzIHJlbGF0ZWQgdG8gdGhlIGxlbmd0aCBvZiBidWYuIFdoZW4gY2FsY3Vs YXRpbmcKPiAgICAgICAgIHRoZSBCMSBibG9jaywgaXQgaXMgYWN0dWFsbHkgYXNzdW1lZCB0aGF0 IHRoZSBsZW5ndGggaXMgdGhlCj4gICAgICAgICBibG9jayBsZW5ndGggeC4gTm93IHdoZW4gY2Fs Y3VsYXRpbmcgQjIsIHRoZSBsZW5ndGggaXMgZXhwYW5kZWQKPiAgICAgICAgIHRvIDJ4LCBzbyBC MiBiZWNvbWVzOgo+ICAgICAgICAgICAgICAgICBCMiA9IDJ4KkQxICsgKDJ4LTEpKkQyICAgICAg ICAgICAgICsgLi4uICsgKHgrMSkqRHggKyB4KkQoeCsxKSArIC4uLiArIEQyeCArIDJ4Cj4gICAg ICAgICAgICAgICAgICAgID0geCpEMSArIHgqRDEgKyB4KkQyICsgKHgtMSkqRDIgKyAuLi4gKyB4 KkR4ICsgRHggKyB4KjEgKyB4ICsgW3gqRCh4KzEpICsgKHgtMSkqRCh4KzIpICsgLi4uICsgRDJ4 XQo+ICAgICAgICAgICAgICAgICAgICAgIF5eXl4gICB+fn5+ICAgXl5eXiAgIH5+fn5+fn5+ICAg ICAgICAgXl5eXiAgIH5+ICAgXl5eICAgfiAgICsrKysrKysrKysrKysrKysrKysrKysrKysrKysr KysrKysrKysKPiAgICAgICAgIFRocm91Z2ggdGhlIGFib3ZlIHBvbHlub21pYWwgdHJhbnNmb3Jt YXRpb246Cj4gICAgICAgICAgICAgICAgIFN5bWJvbCAiXiIgcmVwcmVzZW50cyB0aGUgPHggKiBB MT47Cj4gICAgICAgICAgICAgICAgIFN5bWJvbCAifiIgcmVwcmVzZW50cyB0aGUgPEIxPjsKPiAg ICAgICAgICAgICAgICAgU3ltYm9sICIrIiByZXByZXNlbnRzIHRoZSBuZXh0IGJsb2NrLgo+IAo+ ICAgICAgICAgU28gd2UgY2FuIGdldCB0aGUgbWV0aG9kIG9mIGNhbGN1bGF0aW5nIHRoZSBuZXh0 IGJsb2NrIGZyb20KPiAgICAgICAgIHRoZSBwcmV2aW91cyBibG9jayhBc3N1bWUgdGhhdCB0aGUg Zmlyc3QgYnl0ZSBudW1iZXIgb2YgdGhlCj4gICAgICAgICBuZXcgYmxvY2sgc3RhcnRzIGZyb20g MSk6Cj4gICAgICAgICAgICAgICAgIEFuKzEgPSBBbiArIEQxICsgRDIgKyAuLi4gKyBEeCAobW9k IDY1NTIxKQo+ICAgICAgICAgICAgICAgICBCbisxID0gQm4gKyB4KkFuICsgeCpEMSArICh4LTEp KkQyICsgLi4uICsgRHggKG1vZCA2NTUyMSkKClB1dHRpbmcgYXNpZGUgcGVvcGxlJ3MgY29uY2Vy bnMgZm9yIHRoZSBtb21lbnQsIEkgdGhpbmsgdGhpcyBtYXkgYmUKZm9ybXVsYXRlZCBpbiBhIHNs aWdodGx5IG1vcmUgY29udmVuaWVudCB3YXk6CgpJZgoJWDAsIFgxLCAuLi4gYXJlIHRoZSBkYXRh IGJ5dGVzCglBbiBpcyAxICsgU3VtIFtpPTAgLi4gbi0xXSBYaQoJQm4gaXMgbiArIFN1bSBbaT0w IC4uIG4tMV0gKG4taSlYaQoJCT0gU3VtIFtpPTEgLi4gbl0gQWkKCihpLmUuLCBBbiwgQm4gYXJl IHRoZSBhY2N1bXVsYXRpb25zIGZvciB0aGUgZmlyc3QgbiBieXRlcyBoZXJlLCBub3QgdGhlCmZp cnN0IG4gYmxvY2tzKQoKdGhlbgoKCUFbbit2XSAtIEFuID0gU3VtW2k9biAuLiBuK3YtMV0gWGkK CglCW24rdl0gLSBCbiA9IHYgKyAoU3VtIFtpPTAgLi4gbit2LTFdIChuK3YtaSkgWGkpCgkJCS0g U3VtIFtpPTAgLi4gbi0xXSAobi1pKVhpCgoJCT0gdiArIChTdW0gW2k9biAuLiBuK3YtMV0gKG4r di1pKSBYaSkKCQkJKyAoU3VtIFtpPTAgLi4gbi0xXSAobit2LWkpIFhpKQoJCQktIFN1bSBbaT0w IC4uIG4tMV0gKG4taSlYaQoKCQk9IHYgKyAoU3VtIFtpPW4gLi4gbit2LTFdIChuK3YtaSkgWGkp CgkJCSsgU3VtIFtpPTAgLi4gbi0xXSAoKG4rdi1pKSAtIChuLWkpKSBYaQoKCQk9IHYgKyAoU3Vt IFtpPW4gLi4gbit2LTFdIChuK3YtaSkgWGkpCgkJCSsgdlN1bSBbaT0wIC4uIG4tMV0gWGkKCgkJ PSB2ICsgdihBbiAtIDEpICsgU3VtIFtpPW4gLi4gbit2LTFdIChuK3YtaSkgWGkKCgkJPSB2QW4g KyBTdW0gW2k9biAuLiBuK3YtMV0gKG4rdi1pKSBYaQoKCQk9IHZBbiArIHZTdW0gW2k9biAuLiBu K3YtMV0gWGkKCQkJKyBTdW0gW2k9biAuLiBuK3YtMV0gKG4taSkgWGkKCgkJPSB2QW4gKyB2U3Vt IFtpPW4gLi4gbit2LTFdIFhpCgkJCSsgU3VtIFtpPW4gLi4gbit2LTFdIChuLWkpIFhpCgoJCT0g dkFbbit2XSArIFN1bSBbaT1uIC4uIG4rdi0xXSAobi1pKSBYaQoKTGV0IGogPSBpIC0gbjsgdGhl bjoKCglCW24rdl0gLSBCbiA9IHZBW24rdl0gLSBTdW0gW2o9MCAuLiB2LTFdIGogWFtqK25dCgpX aGljaCBnaXZlcyB1cyBhIG11bHRpcGxpZXIgaiB0aGF0IGluY3JlYXNlcyB3aXRoIHRoZSBYW10g aW5kZXguCgoKSSB0aGluayB0aGlzIGdpdmVzIGEgY29yZSBsb29wIGFsb25nIHRoZSBmb2xsb3dp bmcgbGluZXMuICBJIGRvbid0IGtub3cKd2hldGhlciB0aGlzIGlzIGNvcnJlY3QsIG9yIHdoZXRo ZXIgaXQgd29ya3MgLS0gYnV0IGZlZWwgZnJlZSB0byB0YWtlCmlkZWFzIGZyb20gaXQgaWYgaXQg aGVscHMuCgpBY2N1bXVsYXRvcnMgYXJlIDMyIGJpdHMuICBUaGlzIHByb3ZpZGVzIGZvciBhIGZh aXIgbnVtYmVyIG9mIGl0ZXJhdGlvbnMKd2l0aG91dCBvdmVyZmxvdywgYnV0IGxhcmdlIGlucHV0 IGRhdGEgd2lsbCBzdGlsbCByZXF1aXJlIHNwbGl0dGluZyBpbnRvCmNodW5rcywgd2l0aCBtb2R1 bG8gcmVkdWN0aW9uIHN0ZXBzIGluIGJldHdlZW4uICBUaGVyZSBhcmUgcmF0aGVyIGEgbG90Cm9m IHNlcmlhbCBkZXBlbmRlbmNpZXMgaW4gdGhlIGNvcmUgbG9vcCwgYnV0IHNpbmNlIHRoZSBvcGVy YXRpb25zCmludm9sdmVkIGFyZSByZWxhdGl2ZWx5IGNoZWFwLCB0aGlzIGlzIHByb2JhYmx5IG5v dCBhIHNpZ25pZmljYW50IGlzc3VlCmluIHByYWN0aWNlOiB0aGUgbG9hZC10by11c2UgZGVwZW5k ZW5jeSBpcyBwcm9iYWJseSB0aGUgYmlnZ2VyIGNvbmNlcm4uClBpcGVsaW5lZCBsb29wIHVucm9s bGluZyBjb3VsZCBhZGRyZXNzIHRoZXNlIGlmIG5lY2Vzc2FyeS4KClRoZSBob3Jpem9udGFsIHJl ZHVjdGlvbnMgKFVBRERWKSBzdGlsbCBwcm9iYWJseSBkb24ndCBuZWVkIHRvIGJlIGRvbmUKdW50 aWwgYWZ0ZXIgdGhlIGxhc3QgY2h1bmsuCgoKQmV3YXJlOiBJIHdhc24ndCBjYXJlZnVsIHdpdGgg dGhlIGluaXRpYWwgdmFsdWVzIGZvciBCbiAvIEFuLCBzbyBzb21lCmFkZGl0aW9uYWwgYWRqdXN0 bWVudHMgbWlnaHQgYmUgbmVlZGVkLi4uCgotLTg8LS0KCglwdHJ1ZSAgIHBQLnMKCXB0cnVlICAg cEEucwoKCW1vdiAgICAgekEucywgIzAgICAgICAgICAgICAgICAgLy8gYWNjdW11bGF0b3IgZm9y IEFuCgltb3YgICAgIHpCLnMsICMwICAgICAgICAgICAgICAgIC8vIGFjY3VtdWxhdG9yIGZvciBC bgoJaW5kZXggICB6Si5zLCAjMCwgIzEgICAgICAgICAgICAvLyB6Si5zID0gWzAsIDEsIC4uIFYt MV0KCgltb3YgICAgIHpWLnMsICMwCglpbmN3ICAgIHpWLnMgICAgICAgICAgICAgICAgICAgIC8v IHpWLnMgPSBbViwgViwgLi4gVl0KCi8vIHdoZXJlIFYgaXMgbnVtYmVyIG9mIGVsZW1lbnRzIHBl ciBibG9jawovLyAgICAgID0gdGhlIG51bWJlciBvZiAzMi1iaXQgZWxlbWVudHMgdGhhdCBmaXQg aW4gYSBaLXJlZ2lzdGVyCgoJYWRkICAgICB4TGltaXQsIHhYLCB4TGVuCgliICAgICAgIHN0YXJ0 Cgpsb29wOiAgIAoJbGQxYiAgICB6WC5zLCBwUC96LCBbeFhdCglpbmN3ICAgIHhYCgoJYWRkICAg ICB6QS5zLCBwUC9tLCB6QS5zLCB6WC5zICAgICAgICAvLyB6QS5zICs9IHpYLnMKCgltc2IgICAg IHpYLnMsIHBQL20sIHpKLnMsIHpCLnMgICAgICAgIC8vIHpYLnMgOj0gekIucyAtIHpYLnMgKiB6 Si5zCgoJbW92cHJmeCB6QiwgekEKCW1hZCAgICAgekIucywgcFAvbSwgelYucywgelgucyAgICAg ICAgLy8gekIucyA6PSB6WC5zICsgekEucyAqIFYKc3RhcnQ6ICAKCXdoaWxlbG8gcFAucywgeFgs IHhMaW1pdAoJYi5maXJzdCBsb29wCgovLyBDb2xsZWN0IHRoZSBwYXJ0aWFsIHN1bXMgdG9nZXRo ZXI6CgoJdWFkZHYgICBkMCwgcEEsIHowLnMKCXVhZGR2ICAgZDEsIHBBLCB6MS5zCgovLyBGaW5h bGx5LCBhZGQgMSB0byBkMCwgYW5kIHhMZW4gdG8gZDEsIGFuZCBkbyBtb2R1bG8gcmVkdWN0aW9u LgoKLS0+OC0tCgpbLi4uXQoKQ2hlZXJzCi0tLURhdmUKCl9fX19fX19fX19fX19fX19fX19fX19f X19fX19fX19fX19fX19fX19fX19fX19fCmxpbnV4LWFybS1rZXJuZWwgbWFpbGluZyBsaXN0Cmxp bnV4LWFybS1rZXJuZWxAbGlzdHMuaW5mcmFkZWFkLm9yZwpodHRwOi8vbGlzdHMuaW5mcmFkZWFk Lm9yZy9tYWlsbWFuL2xpc3RpbmZvL2xpbnV4LWFybS1rZXJuZWwK