From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-oi1-x234.google.com (mail-oi1-x234.google.com [IPv6:2607:f8b0:4864:20::234]) by sourceware.org (Postfix) with ESMTPS id 6489B386F033 for ; Mon, 8 Feb 2021 19:35:35 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 6489B386F033 Received: by mail-oi1-x234.google.com with SMTP id r75so3230711oie.11 for ; Mon, 08 Feb 2021 11:35:35 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=AsWfPou5+Eiv8OZ7HpELjUvZSPvGovxAyH+gzBSRdWs=; b=F3H1TaKhpmXGtO/QKO+yJYwrBdKy8IkfJDRGo4KzlO3yU9hxeh1GJy/ICu55+riwyH bmlP5TUk4ZPNW887sqjIObv6zZaBxowfZMSV+6XYcnZlwnIjYBpm989W4qzUreniGZnx aWfEiC8ZV5DVAGfvGXozScBJo7K16UseTK1bwCXOm02Xngn1ZcvKhxi5IGU0SEPCYuZm dKzFOh32NdC0Z4n1pufC/GRh4TZ/s2qunKClhnklN+WzPlZtnXdbnU5lbSw/1gvhWmj6 fvPcRQNtcUsQpJGPFv5tx8BZ0O45hDbZvndEYYqVUmiCI6kvdN0+QmS/m6u+qEhBN293 +goA== X-Gm-Message-State: AOAM531BEnJSXIKDxO8rv7bb8ASJuYc226H6b98i9SO6/vuAPPQk5YbO E07528YbWxzIb+wt66Thu43z1kQXQYFnkJADESc= X-Google-Smtp-Source: ABdhPJyMzZJNbccZ4eaFsqmfjBMoN808byY8Z2XLjfpPa5zdIRyRjxSUszil8aZvGNU3xdVcKiLLysQg2yiFj9MtQOg= X-Received: by 2002:a05:6808:187:: with SMTP id w7mr208270oic.79.1612812934744; Mon, 08 Feb 2021 11:35:34 -0800 (PST) MIME-Version: 1.0 References: <20210203053900.4125403-1-goldstein.w.n@gmail.com> <20210203053900.4125403-2-goldstein.w.n@gmail.com> In-Reply-To: From: "H.J. Lu" Date: Mon, 8 Feb 2021 11:34:58 -0800 Message-ID: Subject: Re: [PATCH v4 2/2] x86: Add additional benchmarks and tests for strchr To: noah Cc: GNU C Library , "Carlos O'Donell" Content-Type: multipart/mixed; boundary="00000000000010a9f405bad846e3" X-Spam-Status: No, score=-3036.1 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 08 Feb 2021 19:35:43 -0000 --00000000000010a9f405bad846e3 Content-Type: text/plain; charset="UTF-8" On Mon, Feb 8, 2021 at 6:08 AM H.J. Lu wrote: > > On Tue, Feb 2, 2021 at 9:39 PM wrote: > > > > From: noah > > > > This patch adds additional benchmarks and tests for string size of > > 4096 and several benchmarks for string size 256 with different > > alignments. > > > > Signed-off-by: noah > > --- > > Added 2 additional benchmark and test sizes: > > > > 4096: Just feels like a natural "large" size to test > > > > 256 with multiple alignments: This essentially is to test how > > expensive the initial work prior to the 4x loop is depending on > > different alignments. > > > > results from bench-strchr: All times are in seconds and the medium of > > 100 runs. Old is current strchr-avx2.S implementation. New is this > > patch. > > > > Summary: New is definetly faster for medium -> large sizes. Once the > > 4x loop is hit there is a 10%+ speedup and New always wins out. For > > smaller sizes there is more variance as to which is faster and the > > differences are small. Generally it seems the New version wins > > out. This is likely because 0 - 31 sized strings are the fast path for > > new (no jmp). Also something that is neat is the significant > > performance improved for alignment 96 and 112. This is because the 5x > > vectors before 4x loop really favor that alignment. > > > > Benchmarking CPU: > > Icelake: Intel(R) Core(TM) i7-1065G7 CPU @ 1.30GHz > > > > size, algn, Old T , New T -------- Win Dif > > 0 , 0 , 2.54 , 2.52 -------- New -0.02 > > 1 , 0 , 2.57 , 2.52 -------- New -0.05 > > 2 , 0 , 2.56 , 2.52 -------- New -0.04 > > 3 , 0 , 2.58 , 2.54 -------- New -0.04 > > 4 , 0 , 2.61 , 2.55 -------- New -0.06 > > 5 , 0 , 2.65 , 2.62 -------- New -0.03 > > 6 , 0 , 2.73 , 2.74 -------- Old -0.01 > > 7 , 0 , 2.75 , 2.74 -------- New -0.01 > > 8 , 0 , 2.62 , 2.6 -------- New -0.02 > > 9 , 0 , 2.73 , 2.75 -------- Old -0.02 > > 10 , 0 , 2.74 , 2.74 -------- Eq N/A > > 11 , 0 , 2.76 , 2.72 -------- New -0.04 > > 12 , 0 , 2.74 , 2.72 -------- New -0.02 > > 13 , 0 , 2.75 , 2.72 -------- New -0.03 > > 14 , 0 , 2.74 , 2.73 -------- New -0.01 > > 15 , 0 , 2.74 , 2.73 -------- New -0.01 > > 16 , 0 , 2.74 , 2.73 -------- New -0.01 > > 17 , 0 , 2.74 , 2.74 -------- Eq N/A > > 18 , 0 , 2.73 , 2.73 -------- Eq N/A > > 19 , 0 , 2.73 , 2.73 -------- Eq N/A > > 20 , 0 , 2.73 , 2.73 -------- Eq N/A > > 21 , 0 , 2.73 , 2.72 -------- New -0.01 > > 22 , 0 , 2.71 , 2.74 -------- Old -0.03 > > 23 , 0 , 2.71 , 2.69 -------- New -0.02 > > 24 , 0 , 2.68 , 2.67 -------- New -0.01 > > 25 , 0 , 2.66 , 2.62 -------- New -0.04 > > 26 , 0 , 2.64 , 2.62 -------- New -0.02 > > 27 , 0 , 2.71 , 2.64 -------- New -0.07 > > 28 , 0 , 2.67 , 2.69 -------- Old -0.02 > > 29 , 0 , 2.72 , 2.72 -------- Eq N/A > > 30 , 0 , 2.68 , 2.69 -------- Old -0.01 > > 31 , 0 , 2.68 , 2.68 -------- Eq N/A > > 32 , 0 , 3.51 , 3.52 -------- Old -0.01 > > 32 , 1 , 3.52 , 3.51 -------- New -0.01 > > 64 , 0 , 3.97 , 3.93 -------- New -0.04 > > 64 , 2 , 3.95 , 3.9 -------- New -0.05 > > 64 , 1 , 4.0 , 3.93 -------- New -0.07 > > 64 , 3 , 3.97 , 3.88 -------- New -0.09 > > 64 , 4 , 3.95 , 3.89 -------- New -0.06 > > 64 , 5 , 3.94 , 3.9 -------- New -0.04 > > 64 , 6 , 3.97 , 3.9 -------- New -0.07 > > 64 , 7 , 3.97 , 3.91 -------- New -0.06 > > 96 , 0 , 4.74 , 4.52 -------- New -0.22 > > 128 , 0 , 5.29 , 5.19 -------- New -0.1 > > 128 , 2 , 5.29 , 5.15 -------- New -0.14 > > 128 , 3 , 5.31 , 5.22 -------- New -0.09 > > 256 , 0 , 11.19 , 9.81 -------- New -1.38 > > 256 , 3 , 11.19 , 9.84 -------- New -1.35 > > 256 , 4 , 11.2 , 9.88 -------- New -1.32 > > 256 , 16 , 11.21 , 9.79 -------- New -1.42 > > 256 , 32 , 11.39 , 10.34 -------- New -1.05 > > 256 , 48 , 11.88 , 10.56 -------- New -1.32 > > 256 , 64 , 11.82 , 10.83 -------- New -0.99 > > 256 , 80 , 11.85 , 10.86 -------- New -0.99 > > 256 , 96 , 9.56 , 8.76 -------- New -0.8 > > 256 , 112 , 9.55 , 8.9 -------- New -0.65 > > 512 , 0 , 15.76 , 13.72 -------- New -2.04 > > 512 , 4 , 15.72 , 13.74 -------- New -1.98 > > 512 , 5 , 15.73 , 13.74 -------- New -1.99 > > 1024, 0 , 24.85 , 21.33 -------- New -3.52 > > 1024, 5 , 24.86 , 21.27 -------- New -3.59 > > 1024, 6 , 24.87 , 21.32 -------- New -3.55 > > 2048, 0 , 45.75 , 36.7 -------- New -9.05 > > 2048, 6 , 43.91 , 35.42 -------- New -8.49 > > 2048, 7 , 44.43 , 36.37 -------- New -8.06 > > 4096, 0 , 96.94 , 81.34 -------- New -15.6 > > 4096, 7 , 97.01 , 81.32 -------- New -15.69 > > > > benchtests/bench-strchr.c | 26 +++++++++++++++++++++++++- > > string/test-strchr.c | 26 +++++++++++++++++++++++++- > > 2 files changed, 50 insertions(+), 2 deletions(-) > > > > diff --git a/benchtests/bench-strchr.c b/benchtests/bench-strchr.c > > index bf493fe458..4ce2369d9b 100644 > > --- a/benchtests/bench-strchr.c > > +++ b/benchtests/bench-strchr.c > > @@ -100,7 +100,7 @@ do_test (size_t align, size_t pos, size_t len, int seek_char, int max_char) > > size_t i; > > CHAR *result; > > CHAR *buf = (CHAR *) buf1; > > - align &= 15; > > + align &= 127; > > if ((align + len) * sizeof (CHAR) >= page_size) > > return; > > > > @@ -151,12 +151,24 @@ test_main (void) > > do_test (i, 16 << i, 2048, SMALL_CHAR, MIDDLE_CHAR); > > } > > > > + for (i = 1; i < 8; ++i) > > + { > > + do_test (0, 16 << i, 4096, SMALL_CHAR, MIDDLE_CHAR); > > + do_test (i, 16 << i, 4096, SMALL_CHAR, MIDDLE_CHAR); > > + } > > + > > for (i = 1; i < 8; ++i) > > { > > do_test (i, 64, 256, SMALL_CHAR, MIDDLE_CHAR); > > do_test (i, 64, 256, SMALL_CHAR, BIG_CHAR); > > } > > > > + for (i = 0; i < 8; ++i) > > + { > > + do_test (16 * i, 256, 512, SMALL_CHAR, MIDDLE_CHAR); > > + do_test (16 * i, 256, 512, SMALL_CHAR, BIG_CHAR); > > + } > > + > > for (i = 0; i < 32; ++i) > > { > > do_test (0, i, i + 1, SMALL_CHAR, MIDDLE_CHAR); > > @@ -169,12 +181,24 @@ test_main (void) > > do_test (i, 16 << i, 2048, 0, MIDDLE_CHAR); > > } > > > > + for (i = 1; i < 8; ++i) > > + { > > + do_test (0, 16 << i, 4096, 0, MIDDLE_CHAR); > > + do_test (i, 16 << i, 4096, 0, MIDDLE_CHAR); > > + } > > + > > for (i = 1; i < 8; ++i) > > { > > do_test (i, 64, 256, 0, MIDDLE_CHAR); > > do_test (i, 64, 256, 0, BIG_CHAR); > > } > > > > + for (i = 0; i < 8; ++i) > > + { > > + do_test (16 * i, 256, 512, 0, MIDDLE_CHAR); > > + do_test (16 * i, 256, 512, 0, BIG_CHAR); > > + } > > + > > for (i = 0; i < 32; ++i) > > { > > do_test (0, i, i + 1, 0, MIDDLE_CHAR); > > diff --git a/string/test-strchr.c b/string/test-strchr.c > > index 5b6022746c..2cf4ea2add 100644 > > --- a/string/test-strchr.c > > +++ b/string/test-strchr.c > > @@ -130,7 +130,7 @@ do_test (size_t align, size_t pos, size_t len, int seek_char, int max_char) > > size_t i; > > CHAR *result; > > CHAR *buf = (CHAR *) buf1; > > - align &= 15; > > + align &= 127; > > if ((align + len) * sizeof (CHAR) >= page_size) > > return; > > > > @@ -259,12 +259,24 @@ test_main (void) > > do_test (i, 16 << i, 2048, SMALL_CHAR, MIDDLE_CHAR); > > } > > > > + for (i = 1; i < 8; ++i) > > + { > > + do_test (0, 16 << i, 4096, SMALL_CHAR, MIDDLE_CHAR); > > + do_test (i, 16 << i, 4096, SMALL_CHAR, MIDDLE_CHAR); > > + } > > + > > for (i = 1; i < 8; ++i) > > { > > do_test (i, 64, 256, SMALL_CHAR, MIDDLE_CHAR); > > do_test (i, 64, 256, SMALL_CHAR, BIG_CHAR); > > } > > > > + for (i = 0; i < 8; ++i) > > + { > > + do_test (16 * i, 256, 512, SMALL_CHAR, MIDDLE_CHAR); > > + do_test (16 * i, 256, 512, SMALL_CHAR, BIG_CHAR); > > + } > > + > > for (i = 0; i < 32; ++i) > > { > > do_test (0, i, i + 1, SMALL_CHAR, MIDDLE_CHAR); > > @@ -277,12 +289,24 @@ test_main (void) > > do_test (i, 16 << i, 2048, 0, MIDDLE_CHAR); > > } > > > > + for (i = 1; i < 8; ++i) > > + { > > + do_test (0, 16 << i, 4096, 0, MIDDLE_CHAR); > > + do_test (i, 16 << i, 4096, 0, MIDDLE_CHAR); > > + } > > + > > for (i = 1; i < 8; ++i) > > { > > do_test (i, 64, 256, 0, MIDDLE_CHAR); > > do_test (i, 64, 256, 0, BIG_CHAR); > > } > > > > + for (i = 0; i < 8; ++i) > > + { > > + do_test (16 * i, 256, 512, 0, MIDDLE_CHAR); > > + do_test (16 * i, 256, 512, 0, BIG_CHAR); > > + } > > + > > for (i = 0; i < 32; ++i) > > { > > do_test (0, i, i + 1, 0, MIDDLE_CHAR); > > -- > > 2.29.2 > > > > LGTM. > > Thanks. > > -- > H.J. This is the updated patch with extra white spaces fixed I am checking in. -- H.J. --00000000000010a9f405bad846e3 Content-Type: text/x-patch; charset="US-ASCII"; name="0002-strchr-Add-additional-benchmarks-and-tests.patch" Content-Disposition: attachment; filename="0002-strchr-Add-additional-benchmarks-and-tests.patch" Content-Transfer-Encoding: base64 Content-ID: X-Attachment-Id: f_kkwz5cd20 RnJvbSBhMDBlMmZlM2RmZDNhNGUyMThiYTZjMWMzNDQ1ZWU2ODMyMmRkZGE5IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBub2FoIDxnb2xkc3RlaW4udy5uQGdtYWlsLmNvbT4KRGF0ZTog V2VkLCAzIEZlYiAyMDIxIDAwOjM5OjAwIC0wNTAwClN1YmplY3Q6IFtQQVRDSCAyLzJdIHN0cmNo cjogQWRkIGFkZGl0aW9uYWwgYmVuY2htYXJrcyBhbmQgdGVzdHMKClRoaXMgcGF0Y2ggYWRkcyBh ZGRpdGlvbmFsIGJlbmNobWFya3MgYW5kIHRlc3RzIGZvciBzdHJpbmcgc2l6ZSBvZgo0MDk2IGFu ZCBzZXZlcmFsIGJlbmNobWFya3MgZm9yIHN0cmluZyBzaXplIDI1NiB3aXRoIGRpZmZlcmVudAph bGlnbm1lbnRzLgotLS0KIGJlbmNodGVzdHMvYmVuY2gtc3RyY2hyLmMgfCAyNiArKysrKysrKysr KysrKysrKysrKysrKysrLQogc3RyaW5nL3Rlc3Qtc3RyY2hyLmMgICAgICB8IDI2ICsrKysrKysr KysrKysrKysrKysrKysrKystCiAyIGZpbGVzIGNoYW5nZWQsIDUwIGluc2VydGlvbnMoKyksIDIg ZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEvYmVuY2h0ZXN0cy9iZW5jaC1zdHJjaHIuYyBiL2Jl bmNodGVzdHMvYmVuY2gtc3RyY2hyLmMKaW5kZXggYmY0OTNmZTQ1OC4uNGNlMjM2OWQ5YiAxMDA2 NDQKLS0tIGEvYmVuY2h0ZXN0cy9iZW5jaC1zdHJjaHIuYworKysgYi9iZW5jaHRlc3RzL2JlbmNo LXN0cmNoci5jCkBAIC0xMDAsNyArMTAwLDcgQEAgZG9fdGVzdCAoc2l6ZV90IGFsaWduLCBzaXpl X3QgcG9zLCBzaXplX3QgbGVuLCBpbnQgc2Vla19jaGFyLCBpbnQgbWF4X2NoYXIpCiAgIHNpemVf dCBpOwogICBDSEFSICpyZXN1bHQ7CiAgIENIQVIgKmJ1ZiA9IChDSEFSICopIGJ1ZjE7Ci0gIGFs aWduICY9IDE1OworICBhbGlnbiAmPSAxMjc7CiAgIGlmICgoYWxpZ24gKyBsZW4pICogc2l6ZW9m IChDSEFSKSA+PSBwYWdlX3NpemUpCiAgICAgcmV0dXJuOwogCkBAIC0xNTEsMTIgKzE1MSwyNCBA QCB0ZXN0X21haW4gKHZvaWQpCiAgICAgICBkb190ZXN0IChpLCAxNiA8PCBpLCAyMDQ4LCBTTUFM TF9DSEFSLCBNSURETEVfQ0hBUik7CiAgICAgfQogCisgIGZvciAoaSA9IDE7IGkgPCA4OyArK2kp CisgICAgeworICAgICAgZG9fdGVzdCAoMCwgMTYgPDwgaSwgNDA5NiwgU01BTExfQ0hBUiwgTUlE RExFX0NIQVIpOworICAgICAgZG9fdGVzdCAoaSwgMTYgPDwgaSwgNDA5NiwgU01BTExfQ0hBUiwg TUlERExFX0NIQVIpOworICAgIH0KKwogICBmb3IgKGkgPSAxOyBpIDwgODsgKytpKQogICAgIHsK ICAgICAgIGRvX3Rlc3QgKGksIDY0LCAyNTYsIFNNQUxMX0NIQVIsIE1JRERMRV9DSEFSKTsKICAg ICAgIGRvX3Rlc3QgKGksIDY0LCAyNTYsIFNNQUxMX0NIQVIsIEJJR19DSEFSKTsKICAgICB9CiAK KyAgZm9yIChpID0gMDsgaSA8IDg7ICsraSkKKyAgICB7CisgICAgICBkb190ZXN0ICgxNiAqIGks IDI1NiwgNTEyLCBTTUFMTF9DSEFSLCBNSURETEVfQ0hBUik7CisgICAgICBkb190ZXN0ICgxNiAq IGksIDI1NiwgNTEyLCBTTUFMTF9DSEFSLCBCSUdfQ0hBUik7CisgICAgfQorCiAgIGZvciAoaSA9 IDA7IGkgPCAzMjsgKytpKQogICAgIHsKICAgICAgIGRvX3Rlc3QgKDAsIGksIGkgKyAxLCBTTUFM TF9DSEFSLCBNSURETEVfQ0hBUik7CkBAIC0xNjksMTIgKzE4MSwyNCBAQCB0ZXN0X21haW4gKHZv aWQpCiAgICAgICBkb190ZXN0IChpLCAxNiA8PCBpLCAyMDQ4LCAwLCBNSURETEVfQ0hBUik7CiAg ICAgfQogCisgIGZvciAoaSA9IDE7IGkgPCA4OyArK2kpCisgICAgeworICAgICAgZG9fdGVzdCAo MCwgMTYgPDwgaSwgNDA5NiwgMCwgTUlERExFX0NIQVIpOworICAgICAgZG9fdGVzdCAoaSwgMTYg PDwgaSwgNDA5NiwgMCwgTUlERExFX0NIQVIpOworICAgIH0KKwogICBmb3IgKGkgPSAxOyBpIDwg ODsgKytpKQogICAgIHsKICAgICAgIGRvX3Rlc3QgKGksIDY0LCAyNTYsIDAsIE1JRERMRV9DSEFS KTsKICAgICAgIGRvX3Rlc3QgKGksIDY0LCAyNTYsIDAsIEJJR19DSEFSKTsKICAgICB9CiAKKyAg Zm9yIChpID0gMDsgaSA8IDg7ICsraSkKKyAgICB7CisgICAgICBkb190ZXN0ICgxNiAqIGksIDI1 NiwgNTEyLCAwLCBNSURETEVfQ0hBUik7CisgICAgICBkb190ZXN0ICgxNiAqIGksIDI1NiwgNTEy LCAwLCBCSUdfQ0hBUik7CisgICAgfQorCiAgIGZvciAoaSA9IDA7IGkgPCAzMjsgKytpKQogICAg IHsKICAgICAgIGRvX3Rlc3QgKDAsIGksIGkgKyAxLCAwLCBNSURETEVfQ0hBUik7CmRpZmYgLS1n aXQgYS9zdHJpbmcvdGVzdC1zdHJjaHIuYyBiL3N0cmluZy90ZXN0LXN0cmNoci5jCmluZGV4IDVi NjAyMjc0NmMuLjZjOGNhNTRhN2QgMTAwNjQ0Ci0tLSBhL3N0cmluZy90ZXN0LXN0cmNoci5jCisr KyBiL3N0cmluZy90ZXN0LXN0cmNoci5jCkBAIC0xMzAsNyArMTMwLDcgQEAgZG9fdGVzdCAoc2l6 ZV90IGFsaWduLCBzaXplX3QgcG9zLCBzaXplX3QgbGVuLCBpbnQgc2Vla19jaGFyLCBpbnQgbWF4 X2NoYXIpCiAgIHNpemVfdCBpOwogICBDSEFSICpyZXN1bHQ7CiAgIENIQVIgKmJ1ZiA9IChDSEFS ICopIGJ1ZjE7Ci0gIGFsaWduICY9IDE1OworICBhbGlnbiAmPSAxMjc7CiAgIGlmICgoYWxpZ24g KyBsZW4pICogc2l6ZW9mIChDSEFSKSA+PSBwYWdlX3NpemUpCiAgICAgcmV0dXJuOwogCkBAIC0y NTksMTIgKzI1OSwyNCBAQCB0ZXN0X21haW4gKHZvaWQpCiAgICAgICBkb190ZXN0IChpLCAxNiA8 PCBpLCAyMDQ4LCBTTUFMTF9DSEFSLCBNSURETEVfQ0hBUik7CiAgICAgfQogCisgIGZvciAoaSA9 IDE7IGkgPCA4OyArK2kpCisgICAgeworICAgICAgZG9fdGVzdCAoMCwgMTYgPDwgaSwgNDA5Niwg U01BTExfQ0hBUiwgTUlERExFX0NIQVIpOworICAgICAgZG9fdGVzdCAoaSwgMTYgPDwgaSwgNDA5 NiwgU01BTExfQ0hBUiwgTUlERExFX0NIQVIpOworICAgIH0KKwogICBmb3IgKGkgPSAxOyBpIDwg ODsgKytpKQogICAgIHsKICAgICAgIGRvX3Rlc3QgKGksIDY0LCAyNTYsIFNNQUxMX0NIQVIsIE1J RERMRV9DSEFSKTsKICAgICAgIGRvX3Rlc3QgKGksIDY0LCAyNTYsIFNNQUxMX0NIQVIsIEJJR19D SEFSKTsKICAgICB9CiAKKyAgZm9yIChpID0gMDsgaSA8IDg7ICsraSkKKyAgICB7CisgICAgICBk b190ZXN0ICgxNiAqIGksIDI1NiwgNTEyLCBTTUFMTF9DSEFSLCBNSURETEVfQ0hBUik7CisgICAg ICBkb190ZXN0ICgxNiAqIGksIDI1NiwgNTEyLCBTTUFMTF9DSEFSLCBCSUdfQ0hBUik7CisgICAg fQorCiAgIGZvciAoaSA9IDA7IGkgPCAzMjsgKytpKQogICAgIHsKICAgICAgIGRvX3Rlc3QgKDAs IGksIGkgKyAxLCBTTUFMTF9DSEFSLCBNSURETEVfQ0hBUik7CkBAIC0yNzcsMTIgKzI4OSwyNCBA QCB0ZXN0X21haW4gKHZvaWQpCiAgICAgICBkb190ZXN0IChpLCAxNiA8PCBpLCAyMDQ4LCAwLCBN SURETEVfQ0hBUik7CiAgICAgfQogCisgIGZvciAoaSA9IDE7IGkgPCA4OyArK2kpCisgICAgewor ICAgICAgZG9fdGVzdCAoMCwgMTYgPDwgaSwgNDA5NiwgMCwgTUlERExFX0NIQVIpOworICAgICAg ZG9fdGVzdCAoaSwgMTYgPDwgaSwgNDA5NiwgMCwgTUlERExFX0NIQVIpOworICAgIH0KKwogICBm b3IgKGkgPSAxOyBpIDwgODsgKytpKQogICAgIHsKICAgICAgIGRvX3Rlc3QgKGksIDY0LCAyNTYs IDAsIE1JRERMRV9DSEFSKTsKICAgICAgIGRvX3Rlc3QgKGksIDY0LCAyNTYsIDAsIEJJR19DSEFS KTsKICAgICB9CiAKKyAgZm9yIChpID0gMDsgaSA8IDg7ICsraSkKKyAgICB7CisgICAgICBkb190 ZXN0ICgxNiAqIGksIDI1NiwgNTEyLCAwLCBNSURETEVfQ0hBUik7CisgICAgICBkb190ZXN0ICgx NiAqIGksIDI1NiwgNTEyLCAwLCBCSUdfQ0hBUik7CisgICAgfQorCiAgIGZvciAoaSA9IDA7IGkg PCAzMjsgKytpKQogICAgIHsKICAgICAgIGRvX3Rlc3QgKDAsIGksIGkgKyAxLCAwLCBNSURETEVf Q0hBUik7Ci0tIAoyLjI5LjIKCg== --00000000000010a9f405bad846e3--