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 Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 9A5DEC433EF for ; Sat, 28 May 2022 16:40:25 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S238390AbiE1QkY (ORCPT ); Sat, 28 May 2022 12:40:24 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51894 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S238307AbiE1QkX (ORCPT ); Sat, 28 May 2022 12:40:23 -0400 Received: from out2.migadu.com (out2.migadu.com [IPv6:2001:41d0:2:aacc::]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id F1A9713EA1; Sat, 28 May 2022 09:40:21 -0700 (PDT) Date: Sun, 29 May 2022 00:41:07 +0800 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.dev; s=key1; t=1653756019; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=+FSRGYJ5CWwQNcNXNsvsX6b7FMt9Ji3rjbqmnbhCCV8=; b=fxJ8CQ3ukTwvSLk3yAXJhEmIxlVVq1bixVA9RaazQ0TbAszmWjZY/g+tQ5SZs4/xgRUTGj Zgbx5n1/BYoXqvXLVrGWi2pHo9f/0c5eoDKV6gOunaJjhmYeoU4uB8SsJhYtBqWOcuzHL9 Ipa5rP6uzroFO6rXWxJv8xQZfqdKPtE= X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. From: Tao Zhou To: Yu-Jen Chang , tao.zhou@linux.dev Cc: ak@linux.intel.com, jdike@linux.intel.com, tglx@linutronix.de, mingo@redhat.com, bp@alien8.de, dave.hansen@linux.intel.com, x86@kernel.org, hpa@zytor.com, keescook@chromium.org, linux-kernel@vger.kernel.org, linux-hardening@vger.kernel.org, richard@nod.at, anton.ivanov@cambridgegreys.com, johannes@sipsolutions.net, linux-um@lists.infradead.org, jserv@ccns.ncku.edu.tw Subject: Re: [PATCH 1/2] x86/lib: Optimize memchr() Message-ID: References: <20220528081236.3020-1-arthurchang09@gmail.com> <20220528081236.3020-2-arthurchang09@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <20220528081236.3020-2-arthurchang09@gmail.com> X-Migadu-Flow: FLOW_OUT X-Migadu-Auth-User: linux.dev Precedence: bulk List-ID: X-Mailing-List: linux-hardening@vger.kernel.org On Sat, May 28, 2022 at 04:12:35PM +0800, Yu-Jen Chang wrote: > The original assembly version of memchr() is implemented with > the byte-wise comparing technique, which does not fully > use 64-bits registers in x86_64 CPU. We use word-wide > comparing so that 8 characters can be compared at the same time > on x86_64 CPU. First we align the input and then use word-wise > comparing to find the first 64-bit word that contain the target. > Secondly, we compare every byte in the word and get the output. > > We create two files to measure the performance. The first file > contains on average 10 characters ahead the target character. > The second file contains at least 1000 characters ahead the > target character. Our implementation of “memchr()” is slightly > better in the first test and nearly 4x faster than the orginal > implementation in the second test. > > Signed-off-by: Yu-Jen Chang > Signed-off-by: Ching-Chun (Jim) Huang > --- > arch/x86/include/asm/string_64.h | 3 ++ > arch/x86/lib/Makefile | 1 + > arch/x86/lib/string_64.c | 78 ++++++++++++++++++++++++++++++++ > 3 files changed, 82 insertions(+) > create mode 100644 arch/x86/lib/string_64.c > > diff --git a/arch/x86/include/asm/string_64.h b/arch/x86/include/asm/string_64.h > index 6e450827f..edce657e0 100644 > --- a/arch/x86/include/asm/string_64.h > +++ b/arch/x86/include/asm/string_64.h > @@ -14,6 +14,9 @@ > extern void *memcpy(void *to, const void *from, size_t len); > extern void *__memcpy(void *to, const void *from, size_t len); > > +#define __HAVE_ARCH_MEMCHR > +extern void *memchr(const void *cs, int c, size_t length); > + > #define __HAVE_ARCH_MEMSET > void *memset(void *s, int c, size_t n); > void *__memset(void *s, int c, size_t n); > diff --git a/arch/x86/lib/Makefile b/arch/x86/lib/Makefile > index f76747862..4d530e559 100644 > --- a/arch/x86/lib/Makefile > +++ b/arch/x86/lib/Makefile > @@ -69,5 +69,6 @@ else > lib-y += clear_page_64.o copy_page_64.o > lib-y += memmove_64.o memset_64.o > lib-y += copy_user_64.o > + lib-y += string_64.o > lib-y += cmpxchg16b_emu.o > endif > diff --git a/arch/x86/lib/string_64.c b/arch/x86/lib/string_64.c > new file mode 100644 > index 000000000..4e067d5be > --- /dev/null > +++ b/arch/x86/lib/string_64.c > @@ -0,0 +1,78 @@ > +// SPDX-License-Identifier: GPL-2.0 > +#include > +#include > +#include > + > +/* How many bytes are loaded each iteration of the word copy loop */ > +#define LBLOCKSIZE (sizeof(long)) > + > +#ifdef __HAVE_ARCH_MEMCHR > + > +void *memchr(const void *cs, int c, size_t length) > +{ > + const unsigned char *src = (const unsigned char *)cs, d = c; I don't know why this 'd = c' is not error. d is a char pointer and c is int. At least this is not safe me do not know. > + while (!IS_ALIGNED((long)src, sizeof(long))) { > + if (!length--) > + return NULL; > + if (*src == d) Compare a character value to a pointer value and this value is c. May be right do not know. Or: char d = c; ... > + return (void *)src; > + src++; > + } > + if (length >= LBLOCKSIZE) { > + unsigned long mask = d << 8 | d; > + unsigned int i = 32; > + long xor, data; > + const long consta = 0xFEFEFEFEFEFEFEFF, > + constb = 0x8080808080808080; Two magic number.. > + /* > + * Create a 8-bytes mask for word-wise comparing. > + * For example, a mask for 'a' is 0x6161616161616161. > + */ > + > + mask |= mask << 16; > + for (i = 32; i < LBLOCKSIZE * 8; i <<= 1) > + mask |= mask << i; > + /* > + * We perform word-wise comparing with following operation: > + * 1. Perform xor on the long word @src and @mask > + * and put into @xor. > + * 2. Add @xor with @consta. > + * 3. ~@xor & @constb. > + * 4. Perform & with the result of step 2 and 3. > + * > + * Step 1 creates a byte which is 0 in the long word if > + * there is at least one target byte in it. > + * > + * Step 2 to Step 4 find if there is a byte with 0 in > + * the long word. > + */ > + asm volatile("1:\n\t" > + "movq (%0),%1\n\t" > + "xorq %6,%1\n\t" > + "lea (%1,%4), %2\n\t" > + "notq %1\n\t" > + "andq %5,%1\n\t" > + "testq %1,%2\n\t" > + "jne 2f\n\t" s/jne/jnz/ Lack much here from me. But I give example that should check the CF flag is zero. 1) contain matching byte. 1111111011111111(consta) +add 0000000001101100(xor) ------------------------ 1111111101101011 (%1) 1111111110010100(~xor) &and 1000000010000000(constb) ------------------------ 1000000010000000 (%2) the logical and of %1 and %2 is 1000000000000000 that is not zero. 2) not contain matching byte 1111111011111111 + 0110111011011100 ---------------- 0110110111011011(%1) 1001000100100011 & 1000000010000000 ---------------- 1000000000000000(%2) %1 and %2 is 0000000000000000 that is zero. I guess that here should use jump instruction jnz instead. Even though, I do not know why that two magic number is so magical.. Thanks, Tao > + "add $8,%0\n\t" > + "sub $8,%3\n\t" > + "cmp $7,%3\n\t" > + "ja 1b\n\t" > + "2:\n\t" > + : "=D"(src), "=r"(xor), "=r"(data), "=r"(length) > + : "r"(consta), "r"(constb), "r"(mask), "0"(src), > + "1"(xor), "2"(data), "3"(length) > + : "memory", "cc"); > + } > + > + while (length--) { > + if (*src == d) > + return (void *)src; > + src++; > + } > + return NULL; > +} > +EXPORT_SYMBOL(memchr); > +#endif > -- > 2.25.1 > From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from out2.migadu.com ([2001:41d0:2:aacc::]) by bombadil.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1nuzUJ-002Qz7-Mt for linux-um@lists.infradead.org; Sat, 28 May 2022 16:40:30 +0000 Date: Sun, 29 May 2022 00:41:07 +0800 From: Tao Zhou Subject: Re: [PATCH 1/2] x86/lib: Optimize memchr() Message-ID: References: <20220528081236.3020-1-arthurchang09@gmail.com> <20220528081236.3020-2-arthurchang09@gmail.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20220528081236.3020-2-arthurchang09@gmail.com> List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: base64 Sender: "linux-um" Errors-To: linux-um-bounces+geert=linux-m68k.org@lists.infradead.org To: Yu-Jen Chang , tao.zhou@linux.dev Cc: ak@linux.intel.com, jdike@linux.intel.com, tglx@linutronix.de, mingo@redhat.com, bp@alien8.de, dave.hansen@linux.intel.com, x86@kernel.org, hpa@zytor.com, keescook@chromium.org, linux-kernel@vger.kernel.org, linux-hardening@vger.kernel.org, richard@nod.at, anton.ivanov@cambridgegreys.com, johannes@sipsolutions.net, linux-um@lists.infradead.org, jserv@ccns.ncku.edu.tw T24gU2F0LCBNYXkgMjgsIDIwMjIgYXQgMDQ6MTI6MzVQTSArMDgwMCwgWXUtSmVuIENoYW5nIHdy b3RlOgoKPiBUaGUgb3JpZ2luYWwgYXNzZW1ibHkgdmVyc2lvbiBvZiBtZW1jaHIoKSBpcyBpbXBs ZW1lbnRlZCB3aXRoCj4gdGhlIGJ5dGUtd2lzZSBjb21wYXJpbmcgdGVjaG5pcXVlLCB3aGljaCBk b2VzIG5vdCBmdWxseQo+IHVzZSA2NC1iaXRzIHJlZ2lzdGVycyBpbiB4ODZfNjQgQ1BVLiBXZSB1 c2Ugd29yZC13aWRlCj4gY29tcGFyaW5nIHNvIHRoYXQgOCBjaGFyYWN0ZXJzIGNhbiBiZSBjb21w YXJlZCBhdCB0aGUgc2FtZSB0aW1lCj4gb24geDg2XzY0IENQVS4gRmlyc3Qgd2UgYWxpZ24gdGhl IGlucHV0IGFuZCB0aGVuIHVzZSB3b3JkLXdpc2UKPiBjb21wYXJpbmcgdG8gZmluZCB0aGUgZmly c3QgNjQtYml0IHdvcmQgdGhhdCBjb250YWluIHRoZSB0YXJnZXQuCj4gU2Vjb25kbHksIHdlIGNv bXBhcmUgZXZlcnkgYnl0ZSBpbiB0aGUgd29yZCBhbmQgZ2V0IHRoZSBvdXRwdXQuCj4gCj4gV2Ug Y3JlYXRlIHR3byBmaWxlcyB0byBtZWFzdXJlIHRoZSBwZXJmb3JtYW5jZS4gVGhlIGZpcnN0IGZp bGUKPiBjb250YWlucyBvbiBhdmVyYWdlIDEwIGNoYXJhY3RlcnMgYWhlYWQgdGhlIHRhcmdldCBj aGFyYWN0ZXIuCj4gVGhlIHNlY29uZCBmaWxlIGNvbnRhaW5zIGF0IGxlYXN0IDEwMDAgY2hhcmFj dGVycyBhaGVhZCB0aGUKPiB0YXJnZXQgY2hhcmFjdGVyLiBPdXIgaW1wbGVtZW50YXRpb24gb2Yg 4oCcbWVtY2hyKCnigJ0gaXMgc2xpZ2h0bHkKPiBiZXR0ZXIgaW4gdGhlIGZpcnN0IHRlc3QgYW5k IG5lYXJseSA0eCBmYXN0ZXIgdGhhbiB0aGUgb3JnaW5hbAo+IGltcGxlbWVudGF0aW9uIGluIHRo ZSBzZWNvbmQgdGVzdC4KPiAKPiBTaWduZWQtb2ZmLWJ5OiBZdS1KZW4gQ2hhbmcgPGFydGh1cmNo YW5nMDlAZ21haWwuY29tPgo+IFNpZ25lZC1vZmYtYnk6IENoaW5nLUNodW4gKEppbSkgSHVhbmcg PGpzZXJ2QGNjbnMubmNrdS5lZHUudHc+Cj4gLS0tCj4gIGFyY2gveDg2L2luY2x1ZGUvYXNtL3N0 cmluZ182NC5oIHwgIDMgKysKPiAgYXJjaC94ODYvbGliL01ha2VmaWxlICAgICAgICAgICAgfCAg MSArCj4gIGFyY2gveDg2L2xpYi9zdHJpbmdfNjQuYyAgICAgICAgIHwgNzggKysrKysrKysrKysr KysrKysrKysrKysrKysrKysrKysKPiAgMyBmaWxlcyBjaGFuZ2VkLCA4MiBpbnNlcnRpb25zKCsp Cj4gIGNyZWF0ZSBtb2RlIDEwMDY0NCBhcmNoL3g4Ni9saWIvc3RyaW5nXzY0LmMKPiAKPiBkaWZm IC0tZ2l0IGEvYXJjaC94ODYvaW5jbHVkZS9hc20vc3RyaW5nXzY0LmggYi9hcmNoL3g4Ni9pbmNs dWRlL2FzbS9zdHJpbmdfNjQuaAo+IGluZGV4IDZlNDUwODI3Zi4uZWRjZTY1N2UwIDEwMDY0NAo+ IC0tLSBhL2FyY2gveDg2L2luY2x1ZGUvYXNtL3N0cmluZ182NC5oCj4gKysrIGIvYXJjaC94ODYv aW5jbHVkZS9hc20vc3RyaW5nXzY0LmgKPiBAQCAtMTQsNiArMTQsOSBAQAo+ICBleHRlcm4gdm9p ZCAqbWVtY3B5KHZvaWQgKnRvLCBjb25zdCB2b2lkICpmcm9tLCBzaXplX3QgbGVuKTsKPiAgZXh0 ZXJuIHZvaWQgKl9fbWVtY3B5KHZvaWQgKnRvLCBjb25zdCB2b2lkICpmcm9tLCBzaXplX3QgbGVu KTsKPiAgCj4gKyNkZWZpbmUgX19IQVZFX0FSQ0hfTUVNQ0hSCj4gK2V4dGVybiB2b2lkICptZW1j aHIoY29uc3Qgdm9pZCAqY3MsIGludCBjLCBzaXplX3QgbGVuZ3RoKTsKPiArCj4gICNkZWZpbmUg X19IQVZFX0FSQ0hfTUVNU0VUCj4gIHZvaWQgKm1lbXNldCh2b2lkICpzLCBpbnQgYywgc2l6ZV90 IG4pOwo+ICB2b2lkICpfX21lbXNldCh2b2lkICpzLCBpbnQgYywgc2l6ZV90IG4pOwo+IGRpZmYg LS1naXQgYS9hcmNoL3g4Ni9saWIvTWFrZWZpbGUgYi9hcmNoL3g4Ni9saWIvTWFrZWZpbGUKPiBp bmRleCBmNzY3NDc4NjIuLjRkNTMwZTU1OSAxMDA2NDQKPiAtLS0gYS9hcmNoL3g4Ni9saWIvTWFr ZWZpbGUKPiArKysgYi9hcmNoL3g4Ni9saWIvTWFrZWZpbGUKPiBAQCAtNjksNSArNjksNiBAQCBl bHNlCj4gICAgICAgICAgbGliLXkgKz0gY2xlYXJfcGFnZV82NC5vIGNvcHlfcGFnZV82NC5vCj4g ICAgICAgICAgbGliLXkgKz0gbWVtbW92ZV82NC5vIG1lbXNldF82NC5vCj4gICAgICAgICAgbGli LXkgKz0gY29weV91c2VyXzY0Lm8KPiArICAgICAgICBsaWIteSArPSBzdHJpbmdfNjQubwo+ICAJ bGliLXkgKz0gY21weGNoZzE2Yl9lbXUubwo+ICBlbmRpZgo+IGRpZmYgLS1naXQgYS9hcmNoL3g4 Ni9saWIvc3RyaW5nXzY0LmMgYi9hcmNoL3g4Ni9saWIvc3RyaW5nXzY0LmMKPiBuZXcgZmlsZSBt b2RlIDEwMDY0NAo+IGluZGV4IDAwMDAwMDAwMC4uNGUwNjdkNWJlCj4gLS0tIC9kZXYvbnVsbAo+ ICsrKyBiL2FyY2gveDg2L2xpYi9zdHJpbmdfNjQuYwo+IEBAIC0wLDAgKzEsNzggQEAKPiArLy8g U1BEWC1MaWNlbnNlLUlkZW50aWZpZXI6IEdQTC0yLjAKPiArI2luY2x1ZGUgPGxpbnV4L3N0cmlu Zy5oPgo+ICsjaW5jbHVkZSA8bGludXgvZXhwb3J0Lmg+Cj4gKyNpbmNsdWRlIDxsaW51eC9hbGln bi5oPgo+ICsKPiArLyogSG93IG1hbnkgYnl0ZXMgYXJlIGxvYWRlZCBlYWNoIGl0ZXJhdGlvbiBv ZiB0aGUgd29yZCBjb3B5IGxvb3AgKi8KPiArI2RlZmluZSBMQkxPQ0tTSVpFIChzaXplb2YobG9u ZykpCj4gKwo+ICsjaWZkZWYgX19IQVZFX0FSQ0hfTUVNQ0hSCj4gKwo+ICt2b2lkICptZW1jaHIo Y29uc3Qgdm9pZCAqY3MsIGludCBjLCBzaXplX3QgbGVuZ3RoKQo+ICt7Cj4gKwljb25zdCB1bnNp Z25lZCBjaGFyICpzcmMgPSAoY29uc3QgdW5zaWduZWQgY2hhciAqKWNzLCBkID0gYzsKCkkgZG9u J3Qga25vdyB3aHkgdGhpcyAnZCA9IGMnIGlzIG5vdCBlcnJvci4KZCBpcyBhIGNoYXIgcG9pbnRl ciBhbmQgYyBpcyBpbnQuIEF0IGxlYXN0IHRoaXMgaXMgbm90IHNhZmUgbWUgZG8gbm90IGtub3cu Cgo+ICsJd2hpbGUgKCFJU19BTElHTkVEKChsb25nKXNyYywgc2l6ZW9mKGxvbmcpKSkgewo+ICsJ CWlmICghbGVuZ3RoLS0pCj4gKwkJCXJldHVybiBOVUxMOwo+ICsJCWlmICgqc3JjID09IGQpCgpD b21wYXJlIGEgY2hhcmFjdGVyIHZhbHVlIHRvIGEgcG9pbnRlciB2YWx1ZSBhbmQgdGhpcyB2YWx1 ZSBpcyBjLgpNYXkgYmUgcmlnaHQgZG8gbm90IGtub3cuCgpPcjoKCmNoYXIgZCA9IGM7Ci4uLgoK PiArCQkJcmV0dXJuICh2b2lkICopc3JjOwo+ICsJCXNyYysrOwo+ICsJfQo+ICsJaWYgKGxlbmd0 aCA+PSBMQkxPQ0tTSVpFKSB7Cj4gKwkJdW5zaWduZWQgbG9uZyBtYXNrID0gZCA8PCA4IHwgZDsK PiArCQl1bnNpZ25lZCBpbnQgaSA9IDMyOwo+ICsJCWxvbmcgeG9yLCBkYXRhOwo+ICsJCWNvbnN0 IGxvbmcgY29uc3RhID0gMHhGRUZFRkVGRUZFRkVGRUZGLAo+ICsJCQkgICBjb25zdGIgPSAweDgw ODA4MDgwODA4MDgwODA7CgpUd28gbWFnaWMgbnVtYmVyLi4KCj4gKwkJLyoKPiArCQkgKiBDcmVh dGUgYSA4LWJ5dGVzIG1hc2sgZm9yIHdvcmQtd2lzZSBjb21wYXJpbmcuCj4gKwkJICogRm9yIGV4 YW1wbGUsIGEgbWFzayBmb3IgJ2EnIGlzIDB4NjE2MTYxNjE2MTYxNjE2MS4KPiArCQkgKi8KPiAr Cj4gKwkJbWFzayB8PSBtYXNrIDw8IDE2Owo+ICsJCWZvciAoaSA9IDMyOyBpIDwgTEJMT0NLU0la RSAqIDg7IGkgPDw9IDEpCj4gKwkJCW1hc2sgfD0gbWFzayA8PCBpOwo+ICsJCS8qCj4gKwkJICog V2UgcGVyZm9ybSB3b3JkLXdpc2UgY29tcGFyaW5nIHdpdGggZm9sbG93aW5nIG9wZXJhdGlvbjoK PiArCQkgKgkxLiBQZXJmb3JtIHhvciBvbiB0aGUgbG9uZyB3b3JkIEBzcmMgYW5kIEBtYXNrCj4g KwkJICoJICAgYW5kIHB1dCBpbnRvIEB4b3IuCj4gKwkJICoJMi4gQWRkIEB4b3Igd2l0aCBAY29u c3RhLgo+ICsJCSAqCTMuIH5AeG9yICYgQGNvbnN0Yi4KPiArCQkgKgk0LiBQZXJmb3JtICYgd2l0 aCB0aGUgcmVzdWx0IG9mIHN0ZXAgMiBhbmQgMy4KPiArCQkgKgo+ICsJCSAqIFN0ZXAgMSBjcmVh dGVzIGEgYnl0ZSB3aGljaCBpcyAwIGluIHRoZSBsb25nIHdvcmQgaWYKPiArCQkgKiB0aGVyZSBp cyBhdCBsZWFzdCBvbmUgdGFyZ2V0IGJ5dGUgaW4gaXQuCj4gKwkJICoKPiArCQkgKiBTdGVwIDIg dG8gU3RlcCA0IGZpbmQgaWYgdGhlcmUgaXMgYSBieXRlIHdpdGggMCBpbgo+ICsJCSAqIHRoZSBs b25nIHdvcmQuCj4gKwkJICovCj4gKwkJYXNtIHZvbGF0aWxlKCIxOlxuXHQiCj4gKwkJCSAgICAg Im1vdnEgKCUwKSwlMVxuXHQiCj4gKwkJCSAgICAgInhvcnEgJTYsJTFcblx0Igo+ICsJCQkgICAg ICJsZWEgKCUxLCU0KSwgJTJcblx0Igo+ICsJCQkgICAgICJub3RxICUxXG5cdCIKPiArCQkJICAg ICAiYW5kcSAlNSwlMVxuXHQiCj4gKwkJCSAgICAgInRlc3RxICUxLCUyXG5cdCIKPiArCQkJICAg ICAiam5lIDJmXG5cdCIKCnMvam5lL2puei8KCkxhY2sgbXVjaCBoZXJlIGZyb20gbWUuIEJ1dCBJ IGdpdmUgZXhhbXBsZSB0aGF0IHNob3VsZCBjaGVjayB0aGUgCkNGIGZsYWcgaXMgemVyby4KCjEp IGNvbnRhaW4gbWF0Y2hpbmcgYnl0ZS4KCjExMTExMTEwMTExMTExMTEoY29uc3RhKQogICAgICAg ICAgICAgICAgICAgICAgICArYWRkCjAwMDAwMDAwMDExMDExMDAoeG9yKQotLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0KMTExMTExMTEwMTEwMTAxMSAoJTEpCgoKMTExMTExMTExMDAxMDEwMCh+eG9y KQogICAgICAgICAgICAgICAgICAgICAgICAmYW5kCjEwMDAwMDAwMTAwMDAwMDAoY29uc3RiKQot LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KMTAwMDAwMDAxMDAwMDAwMCAoJTIpCgoKdGhlIGxvZ2lj YWwgYW5kIG9mICUxIGFuZCAlMiBpcwoxMDAwMDAwMDAwMDAwMDAwIHRoYXQgaXMgbm90IHplcm8u CgoyKSBub3QgY29udGFpbiBtYXRjaGluZyBieXRlCgoxMTExMTExMDExMTExMTExCiAgICAgICAg ICAgICAgICAgKwowMTEwMTExMDExMDExMTAwCi0tLS0tLS0tLS0tLS0tLS0KMDExMDExMDExMTAx MTAxMSglMSkKCjEwMDEwMDAxMDAxMDAwMTEKICAgICAgICAgICAgICAgICAmCjEwMDAwMDAwMTAw MDAwMDAKLS0tLS0tLS0tLS0tLS0tLQoxMDAwMDAwMDAwMDAwMDAwKCUyKQoKJTEgYW5kICUyIGlz CjAwMDAwMDAwMDAwMDAwMDAgdGhhdCBpcyB6ZXJvLgoKSSBndWVzcyB0aGF0IGhlcmUgc2hvdWxk IHVzZSBqdW1wIGluc3RydWN0aW9uIGpueiBpbnN0ZWFkLgpFdmVuIHRob3VnaCwgSSBkbyBub3Qg a25vdyB3aHkgdGhhdCB0d28gbWFnaWMgbnVtYmVyIGlzIHNvIG1hZ2ljYWwuLgoKVGhhbmtzLApU YW8KPiArCQkJICAgICAiYWRkICQ4LCUwXG5cdCIKPiArCQkJICAgICAic3ViICQ4LCUzXG5cdCIK PiArCQkJICAgICAiY21wICQ3LCUzXG5cdCIKPiArCQkJICAgICAiamEgMWJcblx0Igo+ICsJCQkg ICAgICIyOlxuXHQiCj4gKwkJCSAgICAgOiAiPUQiKHNyYyksICI9ciIoeG9yKSwgIj1yIihkYXRh KSwgIj1yIihsZW5ndGgpCj4gKwkJCSAgICAgOiAiciIoY29uc3RhKSwgInIiKGNvbnN0YiksICJy IihtYXNrKSwgIjAiKHNyYyksCj4gKwkJCSAgICAgICAiMSIoeG9yKSwgIjIiKGRhdGEpLCAiMyIo bGVuZ3RoKQo+ICsJCQkgICAgIDogIm1lbW9yeSIsICJjYyIpOwo+ICsJfQo+ICsKPiArCXdoaWxl IChsZW5ndGgtLSkgewo+ICsJCWlmICgqc3JjID09IGQpCj4gKwkJCXJldHVybiAodm9pZCAqKXNy YzsKPiArCQlzcmMrKzsKPiArCX0KPiArCXJldHVybiBOVUxMOwo+ICt9Cj4gK0VYUE9SVF9TWU1C T0wobWVtY2hyKTsKPiArI2VuZGlmCj4gLS0gCj4gMi4yNS4xCj4gCgpfX19fX19fX19fX19fX19f X19fX19fX19fX19fX19fX19fX19fX19fX19fX19fXwpsaW51eC11bSBtYWlsaW5nIGxpc3QKbGlu dXgtdW1AbGlzdHMuaW5mcmFkZWFkLm9yZwpodHRwOi8vbGlzdHMuaW5mcmFkZWFkLm9yZy9tYWls bWFuL2xpc3RpbmZvL2xpbnV4LXVtCg==