From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 120343 invoked by alias); 8 Sep 2019 13:45:00 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 119950 invoked by uid 89); 8 Sep 2019 13:45:00 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-15.9 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,KAM_LOTSOFHASH,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.1 spammy=death, H*RU:209.85.160.193, HX-Spam-Relays-External:209.85.160.193, compressed X-HELO: mail-qt1-f193.google.com Received: from mail-qt1-f193.google.com (HELO mail-qt1-f193.google.com) (209.85.160.193) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 08 Sep 2019 13:44:58 +0000 Received: by mail-qt1-f193.google.com with SMTP id n7so12841155qtb.6; Sun, 08 Sep 2019 06:44:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=GygaYAqQfw7bUk/BCwsMBzjIgucKOgpAXXNDm7ahOXk=; b=XEYlAILj5XhLdKa8S/eX/Qwao5Xwm+77jdyrvue+pbYbiGhT/jwet15hNfcoaPslYw wSsVfUGhBvpNHB3EeoX2tLi8drgtH3YEZoH4cBC/toZgRqT2A2pUxj5maqrnuM8GcD9c YB4gnp26mHltvULVjcqOqKjpcA6l9nxDDaaaS5qQPTkeaiK8eND0s8gOdcrkIEfP9mcr ZUtrcP+DAhYSfSlCfrDHf3ea5KSIs1raCqj9nGtGEGbLGOuNq+/H5vDaSATifWv/1zOk 5KeGimMIw/iLYQ7Rs1tb1+5M2Kl92EfskUl0R/c6MUMhePBNGUUslZiSSXvgVxf4q/ym Bwaw== MIME-Version: 1.0 References: <20190830160126.GO9487@redhat.com> <20190830160857.GP9487@redhat.com> <20190902113226.GW9487@redhat.com> In-Reply-To: <20190902113226.GW9487@redhat.com> From: Antony Polukhin Date: Sun, 08 Sep 2019 13:45:00 -0000 Message-ID: Subject: Re: [PATCH] Optimize to_chars To: Jonathan Wakely Cc: "libstdc++" , gcc-patches List Content-Type: multipart/mixed; boundary="00000000000072fee605920ae063" X-SW-Source: 2019-09/txt/msg00449.txt.bz2 --00000000000072fee605920ae063 Content-Type: text/plain; charset="UTF-8" Content-length: 1672 We've already beaten this topic to death, so let's put a final nail in the coffin: __to_chars_10_impl is quite fast. According to the IACA the main loop takes only 6.0 cycles, the whole function with one iteration takes 10.0 cycles. Replacing the __first[pos] and __first[pos - 1] with __first[0] and __first[1] drops the function time to 7.53 cycles. Changelog: 2019-09-08 Antony Polukhin * include/bits/charconv.h (__detail::__to_chars_10_impl): Replace final offsets with constants. And that's the only optimization that improves all the usecases and reduces code size on 3 instructions. Different approaches for optimizing the loop were showing different results depending on the workload. The most interesting result gives the compressed table of binary coded decimals: static constexpr unsigned char __binary_coded_decimals[50] = { 0x00, 0x02, 0x04, 0x06, 0x08, 0x10... 0x98 }; unsigned __pos = __len - 1; while (__val >= 100) { auto const addition = __val & 1; auto const __num = (__val % 100) >> 1; __val /= 100; auto const __bcd = __binary_coded_decimals[__num]; __first[__pos] = '0' + (__bcd & 0xf) + addition; __first[__pos - 1] = '0' + (__bcd >> 4); __pos -= 2; } That approach shows the same results or even outperforms the existing approach with __digits[201] = "0001020304..." in case of cold cache. It also produces slightly smaller binaries. Unfortunately on a warmed up cache it's slower than the existing approach. I don't think that it's a worth change. Attaching some of the benchmarks as a separate file (not for merge, just something to experiment with). -- Best regards, Antony Polukhin --00000000000072fee605920ae063 Content-Type: text/plain; charset="US-ASCII"; name="to_chars_10_impl_patch.txt" Content-Disposition: attachment; filename="to_chars_10_impl_patch.txt" Content-Transfer-Encoding: base64 Content-ID: X-Attachment-Id: f_k0b0qc071 Content-length: 777 ZGlmZiAtLWdpdCBhL2xpYnN0ZGMrKy12My9pbmNsdWRlL2JpdHMvY2hhcmNv bnYuaCBiL2xpYnN0ZGMrKy12My9pbmNsdWRlL2JpdHMvY2hhcmNvbnYuaApp bmRleCAwOTExNjYwLi5hNWI2YmU1IDEwMDY0NAotLS0gYS9saWJzdGRjKyst djMvaW5jbHVkZS9iaXRzL2NoYXJjb252LmgKKysrIGIvbGlic3RkYysrLXYz L2luY2x1ZGUvYml0cy9jaGFyY29udi5oCkBAIC05MiwxMSArOTIsMTEgQEAg bmFtZXNwYWNlIF9fZGV0YWlsCiAgICAgICBpZiAoX192YWwgPj0gMTApCiAJ ewogCSAgYXV0byBjb25zdCBfX251bSA9IF9fdmFsICogMjsKLQkgIF9fZmly c3RbX19wb3NdID0gX19kaWdpdHNbX19udW0gKyAxXTsKLQkgIF9fZmlyc3Rb X19wb3MgLSAxXSA9IF9fZGlnaXRzW19fbnVtXTsKKwkgIF9fZmlyc3RbMV0g PSBfX2RpZ2l0c1tfX251bSArIDFdOworCSAgX19maXJzdFswXSA9IF9fZGln aXRzW19fbnVtXTsKIAl9CiAgICAgICBlbHNlCi0JX19maXJzdFtfX3Bvc10g PSAnMCcgKyBfX3ZhbDsKKwlfX2ZpcnN0WzBdID0gJzAnICsgX192YWw7CiAg ICAgfQogCiB9IC8vIG5hbWVzcGFjZSBfX2RldGFpbAo= --00000000000072fee605920ae063 Content-Type: text/x-c++hdr; charset="US-ASCII"; name="algorithm_x.hpp" Content-Disposition: attachment; filename="algorithm_x.hpp" Content-Transfer-Encoding: base64 Content-ID: X-Attachment-Id: f_k0b0q0pm0 Content-length: 12505 I2luY2x1ZGUgPHR5cGVfdHJhaXRzPgojaW5jbHVkZSA8dmVjdG9yPgojaW5j bHVkZSA8YmVuY2htYXJrL2JlbmNobWFyay5oPgoKCi8vIEFkanVzdCB0aG9z ZSB2YXJpYWJsZXMgdG8gdGVzdCBvbiBkaWZmZXJlbnQgd29ya2xvYWRzCmNv bnN0ZXhwciB1bnNpZ25lZCBGcm9tID0gMTMwMDAwOwpjb25zdGV4cHIgdW5z aWduZWQgVG8gICA9IDEzMDAwNDsKY29uc3RleHByIHVuc2lnbmVkIExlbiAg PSA2OwovLyBCeXRlcyBvZiBDUFUgY2FjaGUgdG8gcmVzZXQKI2RlZmluZSBS QU5HRVMgLT5BcmdzKHsxNiAqIDEwMjQgKiAxMDI0fSkKCgoKbmFtZXNwYWNl IHN0ZCB7IG5hbWVzcGFjZSBfX2RldGFpbCB7CiAgdGVtcGxhdGU8dHlwZW5h bWUgX1RwPgogICAgaW50CiAgICBfX3RvX2NoYXJzXzEwX3RhYmxlXzJfaW1w bChjaGFyKiBfX2ZpcnN0LCB1bnNpZ25lZCBfX2xlbiwgX1RwIF9fdmFsKSBu b2V4Y2VwdAogICAgewogICAgICBzdGF0aWNfYXNzZXJ0KGlzX2ludGVncmFs PF9UcD46OnZhbHVlLCAiaW1wbGVtZW50YXRpb24gYnVnIik7CiAgICAgIHN0 YXRpY19hc3NlcnQoaXNfdW5zaWduZWQ8X1RwPjo6dmFsdWUsICJpbXBsZW1l bnRhdGlvbiBidWciKTsKCiAgICAgIHN0YXRpYyBjb25zdGV4cHIgY2hhciBf X2RpZ2l0c1syMDFdID0KICAgICIwMDAxMDIwMzA0MDUwNjA3MDgwOTEwMTEx MjEzMTQxNTE2MTcxODE5IgogICAgIjIwMjEyMjIzMjQyNTI2MjcyODI5MzAz MTMyMzMzNDM1MzYzNzM4MzkiCiAgICAiNDA0MTQyNDM0NDQ1NDY0NzQ4NDk1 MDUxNTI1MzU0NTU1NjU3NTg1OSIKICAgICI2MDYxNjI2MzY0NjU2NjY3Njg2 OTcwNzE3MjczNzQ3NTc2Nzc3ODc5IgogICAgIjgwODE4MjgzODQ4NTg2ODc4 ODg5OTA5MTkyOTM5NDk1OTY5Nzk4OTkiOwogICAgICB1bnNpZ25lZCBfX3Bv cyA9IF9fbGVuIC0gMTsKICAgICAgd2hpbGUgKF9fdmFsID49IDEwMCkKICAg IHsKICAgICAgYXV0byBjb25zdCBfX251bSA9IChfX3ZhbCAlIDEwMCkgKiAy OwogICAgICBfX3ZhbCAvPSAxMDA7CiAgICAgIF9fZmlyc3RbX19wb3NdID0g X19kaWdpdHNbX19udW0gKyAxXTsKICAgICAgX19maXJzdFtfX3BvcyAtIDFd ID0gX19kaWdpdHNbX19udW1dOwogICAgICBfX3BvcyAtPSAyOwogICAgfQog ICAgICBpZiAoX192YWwgPj0gMTApCiAgICB7CiAgICAgIGF1dG8gY29uc3Qg X19udW0gPSBfX3ZhbCAqIDI7CiAgICAgIF9fZmlyc3RbMV0gPSBfX2RpZ2l0 c1tfX251bSArIDFdOwogICAgICBfX2ZpcnN0WzBdID0gX19kaWdpdHNbX19u dW1dOwogICAgfQogICAgICBlbHNlCiAgICBfX2ZpcnN0WzBdID0gJzAnICsg X192YWw7CiAgICByZXR1cm4gMDsKICAgIH0KCiAgICAgIHRlbXBsYXRlPHR5 cGVuYW1lIF9UcD4KICAgIGludAogICAgX190b19jaGFyc18xMF9iY2RfaW1w bChjaGFyKiBfX2ZpcnN0LCB1bnNpZ25lZCBfX2xlbiwgX1RwIF9fdmFsKSBu b2V4Y2VwdAogICAgewogICAgICBzdGF0aWNfYXNzZXJ0KGlzX2ludGVncmFs PF9UcD46OnZhbHVlLCAiaW1wbGVtZW50YXRpb24gYnVnIik7CiAgICAgIHN0 YXRpY19hc3NlcnQoaXNfdW5zaWduZWQ8X1RwPjo6dmFsdWUsICJpbXBsZW1l bnRhdGlvbiBidWciKTsKCiAgICAgIHN0YXRpYyBjb25zdGV4cHIgdW5zaWdu ZWQgY2hhciBfX2JpbmFyeV9jb2RlZF9kZWNpbWFsc1sxMDBdID0KICAgIHsg MHgwMCwgMHgwMSwgMHgwMiwgMHgwMywgMHgwNCwgMHgwNSwgMHgwNiwgMHgw NywgMHgwOCwgMHgwOSwgMHgxMAogICwgMHgxMSwgMHgxMiwgMHgxMywgMHgx NCwgMHgxNSwgMHgxNiwgMHgxNywgMHgxOCwgMHgxOSwgMHgyMAogICwgMHgy MSwgMHgyMiwgMHgyMywgMHgyNCwgMHgyNSwgMHgyNiwgMHgyNywgMHgyOCwg MHgyOSwgMHgzMAogICwgMHgzMSwgMHgzMiwgMHgzMywgMHgzNCwgMHgzNSwg MHgzNiwgMHgzNywgMHgzOCwgMHgzOSwgMHg0MAogICwgMHg0MSwgMHg0Miwg MHg0MywgMHg0NCwgMHg0NSwgMHg0NiwgMHg0NywgMHg0OCwgMHg0OSwgMHg1 MAogICwgMHg1MSwgMHg1MiwgMHg1MywgMHg1NCwgMHg1NSwgMHg1NiwgMHg1 NywgMHg1OCwgMHg1OSwgMHg2MAogICwgMHg2MSwgMHg2MiwgMHg2MywgMHg2 NCwgMHg2NSwgMHg2NiwgMHg2NywgMHg2OCwgMHg2OSwgMHg3MAogICwgMHg3 MSwgMHg3MiwgMHg3MywgMHg3NCwgMHg3NSwgMHg3NiwgMHg3NywgMHg3OCwg MHg3OSwgMHg4MAogICwgMHg4MSwgMHg4MiwgMHg4MywgMHg4NCwgMHg4NSwg MHg4NiwgMHg4NywgMHg4OCwgMHg4OSwgMHg5MAogICwgMHg5MSwgMHg5Miwg MHg5MywgMHg5NCwgMHg5NSwgMHg5NiwgMHg5NywgMHg5OCwgMHg5OX07CiAg ICAgIHVuc2lnbmVkIF9fcG9zID0gX19sZW4gLSAxOwogICAgICB3aGlsZSAo X192YWwgPj0gMTAwKQogICAgewogICAgICBhdXRvIGNvbnN0IF9fbnVtID0g X192YWwgJSAxMDA7CiAgICAgIF9fdmFsIC89IDEwMDsKICAgIGF1dG8gY29u c3QgX19iY2QgPSBfX2JpbmFyeV9jb2RlZF9kZWNpbWFsc1tfX251bV07CiAg ICAgIF9fZmlyc3RbX19wb3NdID0gJzAnICsgKF9fYmNkICYgMHhmKTsKICAg ICAgX19maXJzdFtfX3BvcyAtIDFdID0gJzAnICsgKF9fYmNkID4+IDQpOwog ICAgICBfX3BvcyAtPSAyOwogICAgfQogICAgICBpZiAoX192YWwgPj0gMTAp CiAgICB7CiAgICBhdXRvIGNvbnN0IF9fYmNkID0gX19iaW5hcnlfY29kZWRf ZGVjaW1hbHNbX192YWxdOwogICAgICBfX2ZpcnN0WzFdID0gJzAnICsgKF9f YmNkICYgMHhmKTsKICAgICAgX19maXJzdFswXSA9ICcwJyArIChfX2JjZCA+ PiA0KTsKICAgIH0KICAgICAgZWxzZQogICAgX19maXJzdFswXSA9ICcwJyAr IF9fdmFsOwogICAgcmV0dXJuIDA7CiAgICB9CgogICAgICB0ZW1wbGF0ZTx0 eXBlbmFtZSBfVHA+CiAgICBpbnQKICAgIF9fdG9fY2hhcnNfMTBfYmNkX2Nv bXByZXNzZWRfaW1wbChjaGFyKiBfX2ZpcnN0LCB1bnNpZ25lZCBfX2xlbiwg X1RwIF9fdmFsKSBub2V4Y2VwdAogICAgewogICAgICBzdGF0aWNfYXNzZXJ0 KGlzX2ludGVncmFsPF9UcD46OnZhbHVlLCAiaW1wbGVtZW50YXRpb24gYnVn Iik7CiAgICAgIHN0YXRpY19hc3NlcnQoaXNfdW5zaWduZWQ8X1RwPjo6dmFs dWUsICJpbXBsZW1lbnRhdGlvbiBidWciKTsKCiAgICAgIHN0YXRpYyBjb25z dGV4cHIgdW5zaWduZWQgY2hhciBfX2JpbmFyeV9jb2RlZF9kZWNpbWFsc1s1 MF0gPQogICAgeyAweDAwLCAweDAyLCAweDA0LCAweDA2LCAweDA4LCAgMHgx MAogICAgICAgICwgMHgxMiwgMHgxNCwgMHgxNiwgMHgxOCwgIDB4MjAKICAg ICAgICAsIDB4MjIsIDB4MjQsIDB4MjYsIDB4MjgsICAweDMwCiAgICAgICAg LCAweDMyLCAweDM0LCAweDM2LCAweDM4LCAgMHg0MAogICAgICAgICwgMHg0 MiwgMHg0NCwgMHg0NiwgMHg0OCwgIDB4NTAKICAgICAgICAsIDB4NTIsIDB4 NTQsIDB4NTYsIDB4NTgsICAweDYwCiAgICAgICAgLCAweDYyLCAweDY0LCAw eDY2LCAweDY4LCAgMHg3MAogICAgICAgICwgMHg3MiwgMHg3NCwgMHg3Niwg MHg3OCwgIDB4ODAKICAgICAgICAsIDB4ODIsIDB4ODQsIDB4ODYsIDB4ODgs ICAweDkwCiAgICAgICAgLCAweDkyLCAweDk0LCAweDk2LCAweDk4IH07CiAg ICAgIHVuc2lnbmVkIF9fcG9zID0gX19sZW4gLSAxOwogICAgICB3aGlsZSAo X192YWwgPj0gMTAwKQogICAgewogICAgYXV0byBjb25zdCBhZGRpdGlvbiA9 IF9fdmFsICYgMTsKICAgICAgYXV0byBjb25zdCBfX251bSA9IChfX3ZhbCAl IDEwMCkgPj4gMTsKICAgICAgX192YWwgLz0gMTAwOwogICAgYXV0byBjb25z dCBfX2JjZCA9IF9fYmluYXJ5X2NvZGVkX2RlY2ltYWxzW19fbnVtXTsKICAg ICAgX19maXJzdFtfX3Bvc10gPSAnMCcgKyAoX19iY2QgJiAweGYpICsgYWRk aXRpb247CiAgICAgIF9fZmlyc3RbX19wb3MgLSAxXSA9ICcwJyArIChfX2Jj ZCA+PiA0KTsKICAgICAgX19wb3MgLT0gMjsKICAgIH0KICAgICAgaWYgKF9f dmFsID49IDEwKQogICAgewogICAgYXV0byBjb25zdCBfX2JjZCA9IF9fYmlu YXJ5X2NvZGVkX2RlY2ltYWxzW19fdmFsID4+IDFdOwogICAgICBfX2ZpcnN0 WzFdID0gJzAnICsgKF9fYmNkICYgMHhmKSArIChfX3ZhbCAmIDEpOwogICAg ICBfX2ZpcnN0WzBdID0gJzAnICsgKF9fYmNkID4+IDQpOwogICAgfQogICAg ICBlbHNlCiAgICBfX2ZpcnN0WzBdID0gJzAnICsgX192YWw7CiAgICByZXR1 cm4gMDsKICAgIH0KCiAgICAgIHRlbXBsYXRlPHR5cGVuYW1lIF9UcD4KICAg IF9HTElCQ1hYMTRfQ09OU1RFWFBSIGludAogICAgX190b19jaGFyc18xMF9u YWl2ZV9pbXBsKGNoYXIqIF9fZmlyc3QsIHVuc2lnbmVkIF9fbGVuLCBfVHAg X192YWwpIG5vZXhjZXB0CiAgICB7CiAgICAgIHN0YXRpY19hc3NlcnQoaXNf aW50ZWdyYWw8X1RwPjo6dmFsdWUsICJpbXBsZW1lbnRhdGlvbiBidWciKTsK ICAgICAgc3RhdGljX2Fzc2VydChpc191bnNpZ25lZDxfVHA+Ojp2YWx1ZSwg ImltcGxlbWVudGF0aW9uIGJ1ZyIpOwoKICAgICAgdW5zaWduZWQgX19wb3Mg PSBfX2xlbiAtIDE7CiAgICAgIHdoaWxlIChfX3ZhbCA+PSAxMDApCiAgICB7 CiAgICAgIGF1dG8gX19udW0gPSBfX3ZhbCAlIDEwOwogICAgICBfX3ZhbCAv PSAxMDsKICAgICAgX19maXJzdFtfX3Bvc10gPSAnMCcgKyBfX251bTsKICAg ICAgX19udW0gPSBfX3ZhbCAlIDEwOwogICAgICBfX3ZhbCAvPSAxMDsKICAg ICAgX19maXJzdFtfX3BvcyAtIDFdID0gJzAnICsgX19udW07CiAgICAgIF9f cG9zIC09IDI7CiAgICB9CiAgICAgIGlmIChfX3ZhbCA+PSAxMCkKICAgIHsK ICAgICAgYXV0byBjb25zdCBfX251bSA9IF9fdmFsICUgMTA7CiAgICAgIF9f dmFsIC89IDEwOwogICAgICBfX2ZpcnN0WzFdID0gJzAnICsgX19udW07CiAg ICAgIF9fZmlyc3RbMF0gPSAnMCcgKyBfX3ZhbDsKICAgIH0KICAgICAgZWxz ZQogICAgX19maXJzdFswXSA9ICcwJyArIF9fdmFsOwogICAgcmV0dXJuIDA7 CiAgICB9CgogICAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBfVHA+CiAgICBfR0xJ QkNYWDE0X0NPTlNURVhQUiBpbnQKICAgIF9fdG9fY2hhcnNfMTBfbmFpdmVf dW5yX2ltcGwoY2hhciogX19maXJzdCwgdW5zaWduZWQgX19sZW4sIF9UcCBf X3ZhbCkgbm9leGNlcHQKICAgIHsKICAgICAgc3RhdGljX2Fzc2VydChpc19p bnRlZ3JhbDxfVHA+Ojp2YWx1ZSwgImltcGxlbWVudGF0aW9uIGJ1ZyIpOwog ICAgICBzdGF0aWNfYXNzZXJ0KGlzX3Vuc2lnbmVkPF9UcD46OnZhbHVlLCAi aW1wbGVtZW50YXRpb24gYnVnIik7CgogICAgICB3aGlsZSAoX19sZW4gPj0g NikKICAgIHsKICAgICAgdW5zaWduZWQgX19wb3MgPSBfX2xlbiAtIDE7CiAg ICAgIGF1dG8gX19udW0gPSBfX3ZhbCAlIDEwOwogICAgICBfX3ZhbCAvPSAx MDsKICAgICAgX19maXJzdFtfX3Bvc10gPSAnMCcgKyBfX251bTsKCiAgICAg IF9fbnVtID0gX192YWwgJSAxMDsKICAgICAgX192YWwgLz0gMTA7CiAgICAg IF9fZmlyc3RbX19wb3MgLSAxXSA9ICcwJyArIF9fbnVtOwoKICAgIF9fbnVt ID0gX192YWwgJSAxMDsKICAgICAgX192YWwgLz0gMTA7CiAgICAgIF9fZmly c3RbX19wb3MgLSAyXSA9ICcwJyArIF9fbnVtOwoKICAgICAgX19udW0gPSBf X3ZhbCAlIDEwOwogICAgICBfX3ZhbCAvPSAxMDsKICAgICAgX19maXJzdFtf X3BvcyAtIDNdID0gJzAnICsgX19udW07CgogICAgX19udW0gPSBfX3ZhbCAl IDEwOwogICAgICBfX3ZhbCAvPSAxMDsKICAgICAgX19maXJzdFtfX3BvcyAt IDRdID0gJzAnICsgX19udW07CgogICAgICBfX251bSA9IF9fdmFsICUgMTA7 CiAgICAgIF9fdmFsIC89IDEwOwogICAgICBfX2ZpcnN0W19fcG9zIC0gNV0g PSAnMCcgKyBfX251bTsKICAgIF9fbGVuIC09IDY7CiAgICB9CgogIHN3aXRj aCAoX19sZW4pIHsKICAgIGNhc2UgNToKICAgICAgX19maXJzdFs0XSA9ICcw JyArIF9fdmFsICUgMTA7CiAgICAgIF9fdmFsIC89IDEwOwogICAgY2FzZSA0 OgogICAgICBfX2ZpcnN0WzNdID0gJzAnICsgX192YWwgJSAxMDsKICAgICAg X192YWwgLz0gMTA7CiAgICBjYXNlIDM6CiAgICAgIF9fZmlyc3RbMl0gPSAn MCcgKyBfX3ZhbCAlIDEwOwogICAgICBfX3ZhbCAvPSAxMDsKICAgIGNhc2Ug MjoKICAgICAgX19maXJzdFsxXSA9ICcwJyArIF9fdmFsICUgMTA7CiAgICAg IF9fdmFsIC89IDEwOwogICAgY2FzZSAxOgogICAgICBfX2ZpcnN0WzBdID0g JzAnICsgX192YWw7CiAgfQogICAgcmV0dXJuIDA7CiAgICB9Cgp9fQoKCgpz dGF0aWMgdm9pZCBGbHVzaENhY2hlTm9ucGF1c2luZyh1bnNpZ25lZCBGbHVz aENhY2hlQmF5dGVzKSB7CiAgICBzdGQ6OnZlY3Rvcjx1bnNpZ25lZD4gcmVz ZXR0ZXI7CiAgICByZXNldHRlci5yZXNpemUoRmx1c2hDYWNoZUJheXRlcyAv IHNpemVvZih1bnNpZ25lZCksIEZsdXNoQ2FjaGVCYXl0ZXMpOwoKICAgIHVu c2lnbmVkIHRyYXNoID0gc3RhdGljX2Nhc3Q8dW5zaWduZWQ+KEZsdXNoQ2Fj aGVCYXl0ZXMgKiBGbHVzaENhY2hlQmF5dGVzKTsKICAgIGZvciAodW5zaWdu ZWQmIHYgOiByZXNldHRlcikgewogICAgICAgIHRyYXNoICs9IHY7CiAgICAg ICAgdiArPSB0cmFzaDsKICAgIH0KCiAgICBiZW5jaG1hcms6OkRvTm90T3B0 aW1pemUodHJhc2gpOwogICAgYmVuY2htYXJrOjpEb05vdE9wdGltaXplKHJl c2V0dGVyKTsKfQoKc3RhdGljIHZvaWQgbmFpdmUoYmVuY2htYXJrOjpTdGF0 ZSYgc3RhdGUpIHsKICAgIGNvbnN0IHVuc2lnbmVkIEZsdXNoQ2FjaGVCYXl0 ZXMgPSBzdGF0ZS5yYW5nZSgpOwogIGZvciAoYXV0byBfIDogc3RhdGUpIHsK ICAgICAgIGlmIChGbHVzaENhY2hlQmF5dGVzKSB7CiAgICAgICAgc3RhdGUu UGF1c2VUaW1pbmcoKTsKICAgICAgICBGbHVzaENhY2hlTm9ucGF1c2luZyhG bHVzaENhY2hlQmF5dGVzKTsKICAgICAgICBzdGF0ZS5SZXN1bWVUaW1pbmco KTsKICAgICAgIH0KICAgICBmb3IodW5zaWduZWQgaSA9IEZyb207IGkgIT0g VG87ICsraSkKICAgICB7CiAgICAgICAgY2hhciBidWZmZXJbTGVuXTsKICAg ICAgICBiZW5jaG1hcms6OkRvTm90T3B0aW1pemUoc3RkOjpfX2RldGFpbDo6 X190b19jaGFyc18xMF9uYWl2ZV9pbXBsKGJ1ZmZlciwgTGVuLCBpKSk7CiAg ICAgICAgYmVuY2htYXJrOjpEb05vdE9wdGltaXplKGJ1ZmZlcik7CiAgICAg fQoKICB9Cn0KQkVOQ0hNQVJLKG5haXZlKSBSQU5HRVM7CgpzdGF0aWMgdm9p ZCB1bnJvbGxlZChiZW5jaG1hcms6OlN0YXRlJiBzdGF0ZSkgewogICAgY29u c3QgdW5zaWduZWQgRmx1c2hDYWNoZUJheXRlcyA9IHN0YXRlLnJhbmdlKCk7 CiAgZm9yIChhdXRvIF8gOiBzdGF0ZSkgewogICAgICAgaWYgKEZsdXNoQ2Fj aGVCYXl0ZXMpIHsKICAgICAgICBzdGF0ZS5QYXVzZVRpbWluZygpOwogICAg ICAgIEZsdXNoQ2FjaGVOb25wYXVzaW5nKEZsdXNoQ2FjaGVCYXl0ZXMpOwog ICAgICAgIHN0YXRlLlJlc3VtZVRpbWluZygpOwogICAgICAgfQogICAgIGZv cih1bnNpZ25lZCBpID0gRnJvbTsgaSAhPSBUbzsgKytpKQogICAgIHsKICAg ICAgICBjaGFyIGJ1ZmZlcltMZW5dOwogICAgICAgIGJlbmNobWFyazo6RG9O b3RPcHRpbWl6ZShzdGQ6Ol9fZGV0YWlsOjpfX3RvX2NoYXJzXzEwX25haXZl X3Vucl9pbXBsKGJ1ZmZlciwgTGVuLCBpKSk7CiAgICAgICAgYmVuY2htYXJr OjpEb05vdE9wdGltaXplKGJ1ZmZlcik7CiAgICAgfQoKICB9Cn0KQkVOQ0hN QVJLKHVucm9sbGVkKSBSQU5HRVM7CgoKc3RhdGljIHZvaWQgdGFibGVfMihi ZW5jaG1hcms6OlN0YXRlJiBzdGF0ZSkgewogICAgY29uc3QgdW5zaWduZWQg Rmx1c2hDYWNoZUJheXRlcyA9IHN0YXRlLnJhbmdlKCk7CiAgZm9yIChhdXRv IF8gOiBzdGF0ZSkgewogICAgICAgaWYgKEZsdXNoQ2FjaGVCYXl0ZXMpIHsK ICAgICAgICBzdGF0ZS5QYXVzZVRpbWluZygpOwogICAgICAgIEZsdXNoQ2Fj aGVOb25wYXVzaW5nKEZsdXNoQ2FjaGVCYXl0ZXMpOwogICAgICAgIHN0YXRl LlJlc3VtZVRpbWluZygpOwogICAgICAgfQogICAgIGZvcih1bnNpZ25lZCBp ID0gRnJvbTsgaSAhPSBUbzsgKytpKQogICAgIHsKICAgICAgICBjaGFyIGJ1 ZmZlcltMZW5dOwogICAgICAgIGJlbmNobWFyazo6RG9Ob3RPcHRpbWl6ZShz dGQ6Ol9fZGV0YWlsOjpfX3RvX2NoYXJzXzEwX3RhYmxlXzJfaW1wbChidWZm ZXIsIExlbiwgaSkpOwogICAgICAgIGJlbmNobWFyazo6RG9Ob3RPcHRpbWl6 ZShidWZmZXIpOwogICAgIH0KCiAgfQp9CkJFTkNITUFSSyh0YWJsZV8yKSBS QU5HRVM7CgoKc3RhdGljIHZvaWQgYmNkKGJlbmNobWFyazo6U3RhdGUmIHN0 YXRlKSB7CiAgICBjb25zdCB1bnNpZ25lZCBGbHVzaENhY2hlQmF5dGVzID0g c3RhdGUucmFuZ2UoKTsKICBmb3IgKGF1dG8gXyA6IHN0YXRlKSB7CiAgICAg ICBpZiAoRmx1c2hDYWNoZUJheXRlcykgewogICAgICAgIHN0YXRlLlBhdXNl VGltaW5nKCk7CiAgICAgICAgRmx1c2hDYWNoZU5vbnBhdXNpbmcoRmx1c2hD YWNoZUJheXRlcyk7CiAgICAgICAgc3RhdGUuUmVzdW1lVGltaW5nKCk7CiAg ICAgICB9CiAgICAgZm9yKHVuc2lnbmVkIGkgPSBGcm9tOyBpICE9IFRvOyAr K2kpCiAgICAgewogICAgICAgIGNoYXIgYnVmZmVyW0xlbl07CiAgICAgICAg YmVuY2htYXJrOjpEb05vdE9wdGltaXplKHN0ZDo6X19kZXRhaWw6Ol9fdG9f Y2hhcnNfMTBfYmNkX2ltcGwoYnVmZmVyLCBMZW4sIGkpKTsKICAgICAgICBi ZW5jaG1hcms6OkRvTm90T3B0aW1pemUoYnVmZmVyKTsKICAgICB9CgogIH0K fQpCRU5DSE1BUksoYmNkKSBSQU5HRVM7CgoKc3RhdGljIHZvaWQgY29tcHJl c3NlZF9iaW5fY29kZWQoYmVuY2htYXJrOjpTdGF0ZSYgc3RhdGUpIHsKICAg IGNvbnN0IHVuc2lnbmVkIEZsdXNoQ2FjaGVCYXl0ZXMgPSBzdGF0ZS5yYW5n ZSgpOwogIGZvciAoYXV0byBfIDogc3RhdGUpIHsKICAgICAgIGlmIChGbHVz aENhY2hlQmF5dGVzKSB7CiAgICAgICAgc3RhdGUuUGF1c2VUaW1pbmcoKTsK ICAgICAgICBGbHVzaENhY2hlTm9ucGF1c2luZyhGbHVzaENhY2hlQmF5dGVz KTsKICAgICAgICBzdGF0ZS5SZXN1bWVUaW1pbmcoKTsKICAgICAgIH0KICAg ICBmb3IodW5zaWduZWQgaSA9IEZyb207IGkgIT0gVG87ICsraSkKICAgICB7 CiAgICAgICAgY2hhciBidWZmZXJbTGVuXTsKICAgICAgICBiZW5jaG1hcms6 OkRvTm90T3B0aW1pemUoc3RkOjpfX2RldGFpbDo6X190b19jaGFyc18xMF9i Y2RfY29tcHJlc3NlZF9pbXBsKGJ1ZmZlciwgTGVuLCBpKSk7CiAgICAgICAg YmVuY2htYXJrOjpEb05vdE9wdGltaXplKGJ1ZmZlcik7CiAgICAgfQoKICB9 Cn0KQkVOQ0hNQVJLKGNvbXByZXNzZWRfYmluX2NvZGVkKSBSQU5HRVM7Cg== --00000000000072fee605920ae063--