From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-il1-x135.google.com (mail-il1-x135.google.com [IPv6:2607:f8b0:4864:20::135]) by sourceware.org (Postfix) with ESMTPS id 2E8BC3858D28 for ; Mon, 17 Oct 2022 10:32:39 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 2E8BC3858D28 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=linaro.org Received: by mail-il1-x135.google.com with SMTP id i9so5573732ilv.9 for ; Mon, 17 Oct 2022 03:32:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=yK93vpwzdz9FyTRMEyj0md/FIsXtz1/TmWhnQ6JvrbI=; b=S/pohl4qnr4lJQrREGr5hR52T/eNTegkhskUPKVIhjCQb64RunjCEWOkFqg8EqdqBs Ky+3NL8YbUGTnxC+ZBEfrDvUFPyZqqmznVI4SnvCStWTIJLNPrckVRbX+xS/34Jzw5ci Tx8LTa962l4OYi0vSC470nMlgWgT0LI3lsDCtQ2XAI+Hf04wKvb01OGZZNa7COnKJQbO 5M+rVXHH/KMvIpN3+t9qSJ8wazh7JVSVrc9eKCyhw6QneRRY5yrayAa+kiucE/lTnrCs rUMxxeXfXkv5Gq7UYlyjCjDNVkMq+PM2It0Qx3aGhBi1OCi7T9hH1a4ttl40iBX7ZvR2 ecHQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=yK93vpwzdz9FyTRMEyj0md/FIsXtz1/TmWhnQ6JvrbI=; b=63/pwiCl9KAtqDWZDZ2AwRm+nw92QK6Qkf7lmCgW7g+9FFLBx3iItveJM6xzLnaL6e UYo9O3NWk5fnopZSt9sIWTX4mdfqcPQEZlc9A14bEir4h2lh1Qfu8nwhYzO/CyQEuYIf GjLUPMYiQYcaDw8AosdH6rFmNLjyUEsn8gwumJPfeyU6/2J9xGHxqM1nsbQotlQDEGrT mgrQKtFQWfl1HJz1R34VTc3rAUS1FXshnahfIOOSxrqvAn3cOiOveSAzThYlciTPx3KZ 5tVMc7Xlz9h4l4OjG6VMse6CzGZOIovTAMLCvP7IXxDKz8Zdk/Gn8OCN7umhfgJRhswO JJZg== X-Gm-Message-State: ACrzQf2z9/zI2s7mdwgRYYCTkVz2erLhExwbVIZbecQvw0tZC3NEg6oR 6N4Jk5gMC7RbWHvBwefxAtIwLPKm8GGHCvin3dB9ig== X-Google-Smtp-Source: AMsMyM5tluBBvklrZGKSgNxA+tUtg4Ev3eHQ5rh8s1Vugn9myfhDkJIvpjq7A0N0DpGCQS854KKRArzStnG9CVxr944= X-Received: by 2002:a05:6e02:1a05:b0:2fb:7a23:1703 with SMTP id s5-20020a056e021a0500b002fb7a231703mr4301164ild.284.1666002758386; Mon, 17 Oct 2022 03:32:38 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Prathamesh Kulkarni Date: Mon, 17 Oct 2022 16:02:02 +0530 Message-ID: Subject: Re: Extend fold_vec_perm to fold VEC_PERM_EXPR in VLA manner To: Prathamesh Kulkarni , gcc Patches , Richard Biener , richard.sandiford@arm.com Content-Type: multipart/mixed; boundary="0000000000009bf4bd05eb387e54" X-Spam-Status: No, score=-9.2 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: --0000000000009bf4bd05eb387e54 Content-Type: text/plain; charset="UTF-8" On Mon, 10 Oct 2022 at 16:18, Prathamesh Kulkarni wrote: > > On Fri, 30 Sept 2022 at 21:38, Richard Sandiford > wrote: > > > > Richard Sandiford via Gcc-patches writes: > > > Prathamesh Kulkarni writes: > > >> Sorry to ask a silly question but in which case shall we select 2nd vector ? > > >> For num_poly_int_coeffs == 2, > > >> a1 /trunc n1 == (a1 + 0x) / (n1.coeffs[0] + n1.coeffs[1]*x) > > >> If a1/trunc n1 succeeds, > > >> 0 / n1.coeffs[1] == a1/n1.coeffs[0] == 0. > > >> So, a1 has to be < n1.coeffs[0] ? > > > > > > Remember that a1 is itself a poly_int. It's not necessarily a constant. > > > > > > E.g. the TRN1 .D instruction maps to a VEC_PERM_EXPR with the selector: > > > > > > { 0, 2 + 2x, 1, 4 + 2x, 2, 6 + 2x, ... } > > > > Sorry, should have been: > > > > { 0, 2 + 2x, 2, 4 + 2x, 4, 6 + 2x, ... } > Hi Richard, > Thanks for the clarifications, and sorry for late reply. > I have attached POC patch that tries to implement the above approach. > Passes bootstrap+test on x86_64-linux-gnu and aarch64-linux-gnu for VLS vectors. > > For VLA vectors, I have only done limited testing so far. > It seems to pass couple of tests written in the patch for > nelts_per_pattern == 3, > and folds the following svld1rq test: > int32x4_t v = {1, 2, 3, 4}; > return svld1rq_s32 (svptrue_b8 (), &v[0]) > into: > return {1, 2, 3, 4, ...}; > I will try to bootstrap+test it on SVE machine to test further for VLA folding. With the attached patch it seems to pass bootstrap+test with SVE enabled. The only difference w.r.t previous patch is it adds check in get_vector_for_pattern if S is constant otherwise returns NULL_TREE. I added this check because 930325-1.c ICE'd with previous patch because it had following vec_perm_expr, where S was non-constant: vect__16.13_70 = VEC_PERM_EXPR ; I am not sure how to proceed in this case, so chose to bail out. Thanks, Prathamesh > > I have a couple of questions: > 1] When mask selects elements from same vector but from different patterns: > For eg: > arg0 = {1, 11, 2, 12, 3, 13, ...}, > arg1 = {21, 31, 22, 32, 23, 33, ...}, > mask = {0, 0, 0, 1, 0, 2, ... }, > All have npatterns = 2, nelts_per_pattern = 3. > > With above mask, > Pattern {0, ...} selects arg0[0], ie {1, ...} > Pattern {0, 1, 2, ...} selects arg0[0], arg0[1], arg0[2], ie {1, 11, 2, ...} > While arg0[0] and arg0[2] belong to same pattern, arg0[1] belongs to different > pattern in arg0. > The result is: > res = {1, 1, 1, 11, 1, 2, ...} > In this case, res's 2nd pattern {1, 11, 2, ...} is encoded with: > with a0 = 1, a1 = 11, S = -9. > Is that expected tho ? It seems to create a new encoding which > wasn't present in the input vector. For instance, the next elem in > sequence would be -7, > which is not present originally in arg0. > I suppose it's fine since if the user defines mask to have pattern {0, > 1, 2, ...} > they intended result to have pattern with above encoding. > Just wanted to confirm if this is correct ? > > 2] Could you please suggest a test-case for S < 0 ? > I am not able to come up with one :/ > > Thanks, > Prathamesh > > > > > which is an interleaving of the two patterns: > > > > > > { 0, 2, 4, ... } a0 = 0, a1 = 2, S = 2 > > > { 2 + 2x, 4 + 2x, 6 + 2x } a0 = 2 + 2x, a1 = 4 + 2x, S = 2 --0000000000009bf4bd05eb387e54 Content-Type: text/plain; charset="US-ASCII"; name="fold-vec-perm-3.txt" Content-Disposition: attachment; filename="fold-vec-perm-3.txt" Content-Transfer-Encoding: base64 Content-ID: X-Attachment-Id: f_l9clfd5x0 ZGlmZiAtLWdpdCBhL2djYy9mb2xkLWNvbnN0LmNjIGIvZ2NjL2ZvbGQtY29uc3QuY2MKaW5kZXgg OWY3YmVhZTE0ZTUuLmU5M2YyYzdiNTkyIDEwMDY0NAotLS0gYS9nY2MvZm9sZC1jb25zdC5jYwor KysgYi9nY2MvZm9sZC1jb25zdC5jYwpAQCAtODUsNiArODUsOSBAQCBhbG9uZyB3aXRoIEdDQzsg c2VlIHRoZSBmaWxlIENPUFlJTkczLiAgSWYgbm90IHNlZQogI2luY2x1ZGUgInZlYy1wZXJtLWlu ZGljZXMuaCIKICNpbmNsdWRlICJhc2FuLmgiCiAjaW5jbHVkZSAiZ2ltcGxlLXJhbmdlLmgiCisj aW5jbHVkZSA8YWxnb3JpdGhtPgorI2luY2x1ZGUgInRyZWUtcHJldHR5LXByaW50LmgiCisjaW5j bHVkZSAicHJpbnQtdHJlZS5oIgogCiAvKiBOb256ZXJvIGlmIHdlIGFyZSBmb2xkaW5nIGNvbnN0 YW50cyBpbnNpZGUgYW4gaW5pdGlhbGl6ZXIgb3IgYSBDKysKICAgIG1hbmlmZXN0bHktY29uc3Rh bnQtZXZhbHVhdGVkIGNvbnRleHQ7IHplcm8gb3RoZXJ3aXNlLgpAQCAtMTA0OTQsMzggKzEwNDk3 LDU2IEBAIGZvbGRfbXVsdF96Y29uanogKGxvY2F0aW9uX3QgbG9jLCB0cmVlIHR5cGUsIHRyZWUg ZXhwcikKIAkJCSAgYnVpbGRfemVyb19jc3QgKGl0eXBlKSk7CiB9CiAKKy8qIENoZWNrIGlmIFBB VFRFUk4gaW4gU0VMIHNlbGVjdHMgZWl0aGVyIEFSRzAgb3IgQVJHMSwKKyAgIGFuZCByZXR1cm4g dGhlIHNlbGVjdGVkIGFyZywgb3RoZXJ3aXNlIHJldHVybiBOVUxMX1RSRUUuICAqLwogCi0vKiBI ZWxwZXIgZnVuY3Rpb24gZm9yIGZvbGRfdmVjX3Blcm0uICBTdG9yZSBlbGVtZW50cyBvZiBWRUNU T1JfQ1NUIG9yCi0gICBDT05TVFJVQ1RPUiBBUkcgaW50byBhcnJheSBFTFRTLCB3aGljaCBoYXMg TkVMVFMgZWxlbWVudHMsIGFuZCByZXR1cm4KLSAgIHRydWUgaWYgc3VjY2Vzc2Z1bC4gICovCi0K LXN0YXRpYyBib29sCi12ZWNfY3N0X2N0b3JfdG9fYXJyYXkgKHRyZWUgYXJnLCB1bnNpZ25lZCBp bnQgbmVsdHMsIHRyZWUgKmVsdHMpCitzdGF0aWMgdHJlZQorZ2V0X3ZlY3Rvcl9mb3JfcGF0dGVy biAodHJlZSBhcmcwLCB0cmVlIGFyZzEsCisJCQljb25zdCB2ZWNfcGVybV9pbmRpY2VzICZzZWws IHVuc2lnbmVkIHBhdHRlcm4pCiB7Ci0gIHVuc2lnbmVkIEhPU1RfV0lERV9JTlQgaSwgbnVuaXRz OworICB1bnNpZ25lZCBzZWxfbnBhdHRlcm5zID0gc2VsLmVuY29kaW5nICgpLm5wYXR0ZXJucyAo KTsKKyAgdW5zaWduZWQgc2VsX25lbHRzX3Blcl9wYXR0ZXJuID0gc2VsLmVuY29kaW5nICgpLm5l bHRzX3Blcl9wYXR0ZXJuICgpOwogCi0gIGlmIChUUkVFX0NPREUgKGFyZykgPT0gVkVDVE9SX0NT VAotICAgICAgJiYgVkVDVE9SX0NTVF9ORUxUUyAoYXJnKS5pc19jb25zdGFudCAoJm51bml0cykp CisgIHBvbHlfdWludDY0IG4xID0gVFlQRV9WRUNUT1JfU1VCUEFSVFMgKFRSRUVfVFlQRSAoYXJn MCkpOworICBwb2x5X3VpbnQ2NCBuc2VsID0gc2VsLmxlbmd0aCAoKTsKKyAgcG9seV91aW50NjQg ZXNlbDsKKworICBpZiAoIW11bHRpcGxlX3AgKG5zZWwsIHNlbF9ucGF0dGVybnMsICZlc2VsKSkK KyAgICByZXR1cm4gTlVMTF9UUkVFOworCisgIHBvbHlfdWludDY0IGExID0gc2VsW3BhdHRlcm4g KyBzZWxfbnBhdHRlcm5zXTsKKyAgaW50NjRfdCBTID0gMDsKKyAgaWYgKHNlbF9uZWx0c19wZXJf cGF0dGVybiA9PSAzKQogICAgIHsKLSAgICAgIGZvciAoaSA9IDA7IGkgPCBudW5pdHM7ICsraSkK LQllbHRzW2ldID0gVkVDVE9SX0NTVF9FTFQgKGFyZywgaSk7CisgICAgICBwb2x5X3VpbnQ2NCBh MiA9IHNlbFtwYXR0ZXJuICsgMiAqIHNlbF9ucGF0dGVybnNdOworICAgICAgcG9seV91aW50NjQg ZGlmZiA9IGEyIC0gYTE7CisgICAgICBpZiAoIWRpZmYuaXNfY29uc3RhbnQgKCkpCisJcmV0dXJu IE5VTExfVFJFRTsKKyAgICAgIFMgPSBkaWZmLnRvX2NvbnN0YW50ICgpOwogICAgIH0KLSAgZWxz ZSBpZiAoVFJFRV9DT0RFIChhcmcpID09IENPTlNUUlVDVE9SKQorICAKKyAgcG9seV91aW50NjQg YWUgPSBhMSArIChlc2VsIC0gMikgKiBTOworICB1aW50NjRfdCBxMSwgcWU7CisgIHBvbHlfdWlu dDY0IHIxLCByZTsKKworICBpZiAoIWNhbl9kaXZfdHJ1bmNfcCAoYTEsIG4xLCAmcTEsICZyMSkK KyAgICAgIHx8ICFjYW5fZGl2X3RydW5jX3AgKGFlLCBuMSwgJnFlLCAmcmUpCisgICAgICB8fCAo cTEgIT0gcWUpKQorICAgIHJldHVybiBOVUxMX1RSRUU7CisKKyAgdHJlZSBhcmcgPSAoKHExICYg MSkgPT0gMCkgPyBhcmcwIDogYXJnMTsKKworICBpZiAoUyA8IDApCiAgICAgewotICAgICAgY29u c3RydWN0b3JfZWx0ICplbHQ7CisgICAgICBwb2x5X3VpbnQ2NCBhMCA9IHNlbFtwYXR0ZXJuXTsK KyAgICAgIGlmICgha25vd25fZXEgKFMsIGExIC0gYTApKQorICAgICAgICByZXR1cm4gTlVMTF9U UkVFOwogCi0gICAgICBGT1JfRUFDSF9WRUNfU0FGRV9FTFQgKENPTlNUUlVDVE9SX0VMVFMgKGFy ZyksIGksIGVsdCkKLQlpZiAoaSA+PSBuZWx0cyB8fCBUUkVFX0NPREUgKFRSRUVfVFlQRSAoZWx0 LT52YWx1ZSkpID09IFZFQ1RPUl9UWVBFKQotCSAgcmV0dXJuIGZhbHNlOwotCWVsc2UKLQkgIGVs dHNbaV0gPSBlbHQtPnZhbHVlOworICAgICAgaWYgKCFrbm93bl9ndCAocmUsIFZFQ1RPUl9DU1Rf TlBBVFRFUk5TIChhcmcpKSkKKyAgICAgICAgcmV0dXJuIE5VTExfVFJFRTsKICAgICB9Ci0gIGVs c2UKLSAgICByZXR1cm4gZmFsc2U7Ci0gIGZvciAoOyBpIDwgbmVsdHM7IGkrKykKLSAgICBlbHRz W2ldCi0gICAgICA9IGZvbGRfY29udmVydCAoVFJFRV9UWVBFIChUUkVFX1RZUEUgKGFyZykpLCBp bnRlZ2VyX3plcm9fbm9kZSk7Ci0gIHJldHVybiB0cnVlOworICAKKyAgcmV0dXJuIGFyZzsKIH0K IAogLyogQXR0ZW1wdCB0byBmb2xkIHZlY3RvciBwZXJtdXRhdGlvbiBvZiBBUkcwIGFuZCBBUkcx IHZlY3RvcnMgdXNpbmcgU0VMCkBAIC0xMDUzOSw0MSArMTA1NjAsMTEyIEBAIGZvbGRfdmVjX3Bl cm0gKHRyZWUgdHlwZSwgdHJlZSBhcmcwLCB0cmVlIGFyZzEsIGNvbnN0IHZlY19wZXJtX2luZGlj ZXMgJnNlbCkKICAgdW5zaWduZWQgSE9TVF9XSURFX0lOVCBuZWx0czsKICAgYm9vbCBuZWVkX2N0 b3IgPSBmYWxzZTsKIAotICBpZiAoIXNlbC5sZW5ndGggKCkuaXNfY29uc3RhbnQgKCZuZWx0cykp Ci0gICAgcmV0dXJuIE5VTExfVFJFRTsKLSAgZ2NjX2Fzc2VydCAoa25vd25fZXEgKFRZUEVfVkVD VE9SX1NVQlBBUlRTICh0eXBlKSwgbmVsdHMpCi0JICAgICAgJiYga25vd25fZXEgKFRZUEVfVkVD VE9SX1NVQlBBUlRTIChUUkVFX1RZUEUgKGFyZzApKSwgbmVsdHMpCi0JICAgICAgJiYga25vd25f ZXEgKFRZUEVfVkVDVE9SX1NVQlBBUlRTIChUUkVFX1RZUEUgKGFyZzEpKSwgbmVsdHMpKTsKKyAg Z2NjX2Fzc2VydCAoa25vd25fZXEgKFRZUEVfVkVDVE9SX1NVQlBBUlRTICh0eXBlKSwgc2VsLmxl bmd0aCAoKSkKKwkgICAgICAmJiBrbm93bl9lcSAoVFlQRV9WRUNUT1JfU1VCUEFSVFMgKFRSRUVf VFlQRSAoYXJnMCkpLAorCQkJICAgVFlQRV9WRUNUT1JfU1VCUEFSVFMgKFRSRUVfVFlQRSAoYXJn MSkpKSk7CiAgIGlmIChUUkVFX1RZUEUgKFRSRUVfVFlQRSAoYXJnMCkpICE9IFRSRUVfVFlQRSAo dHlwZSkKICAgICAgIHx8IFRSRUVfVFlQRSAoVFJFRV9UWVBFIChhcmcxKSkgIT0gVFJFRV9UWVBF ICh0eXBlKSkKICAgICByZXR1cm4gTlVMTF9UUkVFOwogCi0gIHRyZWUgKmluX2VsdHMgPSBYQUxM T0NBVkVDICh0cmVlLCBuZWx0cyAqIDIpOwotICBpZiAoIXZlY19jc3RfY3Rvcl90b19hcnJheSAo YXJnMCwgbmVsdHMsIGluX2VsdHMpCi0gICAgICB8fCAhdmVjX2NzdF9jdG9yX3RvX2FycmF5IChh cmcxLCBuZWx0cywgaW5fZWx0cyArIG5lbHRzKSkKKyAgdW5zaWduZWQgcmVzX25wYXR0ZXJucyA9 IDA7CisgIHVuc2lnbmVkIHJlc19uZWx0c19wZXJfcGF0dGVybiA9IDA7CisgIHVuc2lnbmVkIHNl bF9ucGF0dGVybnMgPSAwOworICB0cmVlICp2ZWN0b3JfZm9yX3BhdHRlcm4gPSBOVUxMOworCisg IGlmIChUUkVFX0NPREUgKGFyZzApID09IFZFQ1RPUl9DU1QKKyAgICAgICYmIFRSRUVfQ09ERSAo YXJnMSkgPT0gVkVDVE9SX0NTVAorICAgICAgJiYgIXNlbC5sZW5ndGggKCkuaXNfY29uc3RhbnQg KCkpCisgICAgeworICAgICAgc2VsX25wYXR0ZXJucyA9IHNlbC5lbmNvZGluZyAoKS5ucGF0dGVy bnMgKCk7CisgICAgICB2ZWN0b3JfZm9yX3BhdHRlcm4gPSBYQUxMT0NBVkVDICh0cmVlLCBzZWxf bnBhdHRlcm5zKTsKKyAgICAgIGZvciAodW5zaWduZWQgaSA9IDA7IGkgPCBzZWxfbnBhdHRlcm5z OyBpKyspCisJeworCSAgdHJlZSBvcCA9IGdldF92ZWN0b3JfZm9yX3BhdHRlcm4gKGFyZzAsIGFy ZzEsIHNlbCwgaSk7CisJICBpZiAoIW9wKQorCSAgICByZXR1cm4gTlVMTF9UUkVFOworCSAgdmVj dG9yX2Zvcl9wYXR0ZXJuW2ldID0gb3A7CisJfQorCisgICAgICB1bnNpZ25lZCBhcmcwX25wYXR0 ZXJucyA9IFZFQ1RPUl9DU1RfTlBBVFRFUk5TIChhcmcwKTsKKyAgICAgIHVuc2lnbmVkIGFyZzFf bnBhdHRlcm5zID0gVkVDVE9SX0NTVF9OUEFUVEVSTlMgKGFyZzEpOworCisgICAgICByZXNfbnBh dHRlcm5zCisgICAgICAgID0gbGVhc3RfY29tbW9uX211bHRpcGxlIChzZWxfbnBhdHRlcm5zLAor CQkJCSBsZWFzdF9jb21tb25fbXVsdGlwbGUgKGFyZzBfbnBhdHRlcm5zLAorCQkJCSAJCQlhcmcx X25wYXR0ZXJucykpOworICAgICAgcmVzX25lbHRzX3Blcl9wYXR0ZXJuCisJPSBzdGQ6Om1heChz ZWwuZW5jb2RpbmcgKCkubmVsdHNfcGVyX3BhdHRlcm4gKCksCisJCSAgIHN0ZDo6bWF4IChWRUNU T1JfQ1NUX05FTFRTX1BFUl9QQVRURVJOIChhcmcwKSwKKwkJCSAgICAgVkVDVE9SX0NTVF9ORUxU U19QRVJfUEFUVEVSTiAoYXJnMSkpKTsKKyAgICB9CisgIGVsc2UgaWYgKHNlbC5sZW5ndGggKCku aXNfY29uc3RhbnQgKCZuZWx0cykKKwkgICAmJiBUWVBFX1ZFQ1RPUl9TVUJQQVJUUyAoVFJFRV9U WVBFIChhcmcwKSkuaXNfY29uc3RhbnQgKCkKKwkgICAmJiBUWVBFX1ZFQ1RPUl9TVUJQQVJUUyAo VFJFRV9UWVBFIChhcmcwKSkudG9fY29uc3RhbnQgKCkgPT0gbmVsdHMpCisgICAgeworICAgICAg LyogRm9yIFZMUyB2ZWN0b3JzLCB0cmVhdCBhbGwgdmVjdG9ycyB3aXRoCisJIG5wYXR0ZXJucyA9 IG5lbHRzLCBuZWx0c19wZXJfcGF0dGVybiA9IDEuICovCisgICAgICByZXNfbnBhdHRlcm5zID0g c2VsX25wYXR0ZXJucyA9IG5lbHRzOworICAgICAgcmVzX25lbHRzX3Blcl9wYXR0ZXJuID0gMTsK KyAgICAgIHZlY3Rvcl9mb3JfcGF0dGVybiA9IFhBTExPQ0FWRUMgKHRyZWUsIG5lbHRzKTsKKyAg ICAgIGZvciAodW5zaWduZWQgaSA9IDA7IGkgPCBuZWx0czsgaSsrKQorICAgICAgICB7CisJICBI T1NUX1dJREVfSU5UIGluZGV4OworCSAgaWYgKCFzZWxbaV0uaXNfY29uc3RhbnQgKCZpbmRleCkp CisJICAgIHJldHVybiBOVUxMX1RSRUU7CisJICB2ZWN0b3JfZm9yX3BhdHRlcm5baV0gPSAoaW5k ZXggPCBuZWx0cykgPyBhcmcwIDogYXJnMTsJCisJfQorICAgIH0KKyAgZWxzZQogICAgIHJldHVy biBOVUxMX1RSRUU7CiAKLSAgdHJlZV92ZWN0b3JfYnVpbGRlciBvdXRfZWx0cyAodHlwZSwgbmVs dHMsIDEpOwotICBmb3IgKGkgPSAwOyBpIDwgbmVsdHM7IGkrKykKKyAgdHJlZV92ZWN0b3JfYnVp bGRlciBvdXRfZWx0cyAodHlwZSwgcmVzX25wYXR0ZXJucywKKwkJCQlyZXNfbmVsdHNfcGVyX3Bh dHRlcm4pOworICB1bnNpZ25lZCByZXNfbmVsdHMgPSByZXNfbnBhdHRlcm5zICogcmVzX25lbHRz X3Blcl9wYXR0ZXJuOworICBmb3IgKHVuc2lnbmVkIGkgPSAwOyBpIDwgcmVzX25lbHRzOyBpKysp CiAgICAgewotICAgICAgSE9TVF9XSURFX0lOVCBpbmRleDsKLSAgICAgIGlmICghc2VsW2ldLmlz X2NvbnN0YW50ICgmaW5kZXgpKQorICAgICAgcG9seV91aW50NjQgbjEgPSBUWVBFX1ZFQ1RPUl9T VUJQQVJUUyAoVFJFRV9UWVBFIChhcmcwKSk7CisgICAgICB1aW50NjRfdCBxOworICAgICAgcG9s eV91aW50NjQgcjsKKworICAgICAgLyogRGl2aWRlIHNlbFtpXSBieSBpbnB1dCB2ZWN0b3IgbGVu Z3RoLCB0byBvYnRhaW4gcmVtYWluZGVyLAorCSB3aGljaCB3b3VsZCBiZSB0aGUgaW5kZXggZm9y IGVpdGhlciBpbnB1dCB2ZWN0b3IuICAqLworICAgICAgaWYgKCFjYW5fZGl2X3RydW5jX3AgKHNl bFtpXSwgbjEsICZxLCAmcikpCiAJcmV0dXJuIE5VTExfVFJFRTsKLSAgICAgIGlmICghQ09OU1RB TlRfQ0xBU1NfUCAoaW5fZWx0c1tpbmRleF0pKQotCW5lZWRfY3RvciA9IHRydWU7Ci0gICAgICBv dXRfZWx0cy5xdWlja19wdXNoICh1bnNoYXJlX2V4cHIgKGluX2VsdHNbaW5kZXhdKSk7CisKKyAg ICAgIHVuc2lnbmVkIEhPU1RfV0lERV9JTlQgaW5kZXg7CisgICAgICBpZiAoIXIuaXNfY29uc3Rh bnQgKCZpbmRleCkpCisJcmV0dXJuIE5VTExfVFJFRTsKKworICAgICAgLyogRm9yIFZMQSB2ZWN0 b3JzLCBpICUgc2VsX25wYXR0ZXJucyB3b3VsZCBnaXZlIHRoZSBwYXR0ZXJuCisgICAgICAgICBp biBzZWwgdGhhdCBpdGggZWxlbSBiZWxvbmdzIHRvLgorCSBGb3IgVkxTIHZlY3RvcnMsIHNlbF9u cGF0dGVybnMgPT0gcmVzX25lbHRzID09IG5lbHRzLAorCSBzbyBpICUgc2VsX25wYXR0ZXJucyA9 PSBpIHNpbmNlIGkgPCBuZWx0cyAqLworICAgICAgdHJlZSBhcmcgPSB2ZWN0b3JfZm9yX3BhdHRl cm5baSAlIHNlbF9ucGF0dGVybnNdOworICAgICAgdHJlZSBlbGVtOworICAgICAgaWYgKFRSRUVf Q09ERSAoYXJnKSA9PSBDT05TVFJVQ1RPUikKKyAgICAgICAgeworCSAgZ2NjX2Fzc2VydCAoaW5k ZXggPCBuZWx0cyk7CisJICBpZiAoaW5kZXggPj0gdmVjX3NhZmVfbGVuZ3RoIChDT05TVFJVQ1RP Ul9FTFRTIChhcmcpKSkKKwkgICAgcmV0dXJuIE5VTExfVFJFRTsKKwkgIGVsZW0gPSBDT05TVFJV Q1RPUl9FTFQgKGFyZywgaW5kZXgpLT52YWx1ZTsKKwkgIGlmIChWRUNUT1JfVFlQRV9QIChUUkVF X1RZUEUgKGVsZW0pKSkKKwkgICAgcmV0dXJuIE5VTExfVFJFRTsKKwkgIG5lZWRfY3RvciA9IHRy dWU7CisJfQorICAgICAgZWxzZQorICAgICAgICBlbGVtID0gdmVjdG9yX2NzdF9lbHQgKGFyZywg aW5kZXgpOworICAgICAgb3V0X2VsdHMucXVpY2tfcHVzaCAoZWxlbSk7CiAgICAgfQogCiAgIGlm IChuZWVkX2N0b3IpCiAgICAgewogICAgICAgdmVjPGNvbnN0cnVjdG9yX2VsdCwgdmFfZ2M+ICp2 OwotICAgICAgdmVjX2FsbG9jICh2LCBuZWx0cyk7Ci0gICAgICBmb3IgKGkgPSAwOyBpIDwgbmVs dHM7IGkrKykKKyAgICAgIHZlY19hbGxvYyAodiwgcmVzX25lbHRzKTsKKyAgICAgIGZvciAoaSA9 IDA7IGkgPCByZXNfbmVsdHM7IGkrKykKIAlDT05TVFJVQ1RPUl9BUFBFTkRfRUxUICh2LCBOVUxM X1RSRUUsIG91dF9lbHRzW2ldKTsKICAgICAgIHJldHVybiBidWlsZF9jb25zdHJ1Y3RvciAodHlw ZSwgdik7CiAgICAgfQotICBlbHNlCi0gICAgcmV0dXJuIG91dF9lbHRzLmJ1aWxkICgpOworICBy ZXR1cm4gb3V0X2VsdHMuYnVpbGQgKCk7CiB9CiAKIC8qIFRyeSB0byBmb2xkIGEgcG9pbnRlciBk aWZmZXJlbmNlIG9mIHR5cGUgVFlQRSB0d28gYWRkcmVzcyBleHByZXNzaW9ucyBvZgpAQCAtMTY5 MTAsNiArMTcwMDIsOTcgQEAgdGVzdF92ZWNfZHVwbGljYXRlX2ZvbGRpbmcgKCkKICAgQVNTRVJU X1RSVUUgKG9wZXJhbmRfZXF1YWxfcCAoZHVwNV9leHByLCBkdXA1X2NzdCwgMCkpOwogfQogCitz dGF0aWMgdHJlZQorYnVpbGRfdmVjX2ludF9jc3QgKHVuc2lnbmVkIG5wYXR0ZXJucywgdW5zaWdu ZWQgbmVsdHNfcGVyX3BhdHRlcm4sCisJCSAgIGludCAqZW5jb2RlZF9lbGVtcykKK3sKKyAgc2Nh bGFyX2ludF9tb2RlIGludF9tb2RlID0gU0NBTEFSX0lOVF9UWVBFX01PREUgKGludGVnZXJfdHlw ZV9ub2RlKTsKKyAgbWFjaGluZV9tb2RlIHZtb2RlID0gdGFyZ2V0bS52ZWN0b3JpemUucHJlZmVy cmVkX3NpbWRfbW9kZSAoaW50X21vZGUpOworICAvL21hY2hpbmVfbW9kZSB2bW9kZSA9IFZOeDRT SW1vZGU7CisgIHBvbHlfdWludDY0IG51bml0cyA9IEdFVF9NT0RFX05VTklUUyAodm1vZGUpOwor ICB0cmVlIHZlY3R5cGUgPSBidWlsZF92ZWN0b3JfdHlwZSAoaW50ZWdlcl90eXBlX25vZGUsIG51 bml0cyk7CisKKyAgdHJlZV92ZWN0b3JfYnVpbGRlciBidWlsZGVyICh2ZWN0eXBlLCBucGF0dGVy bnMsIG5lbHRzX3Blcl9wYXR0ZXJuKTsKKyAgZm9yICh1bnNpZ25lZCBpID0gMDsgaSA8IG5wYXR0 ZXJucyAqIG5lbHRzX3Blcl9wYXR0ZXJuOyBpKyspCisgICAgYnVpbGRlci5xdWlja19wdXNoIChi dWlsZF9pbnRfY3N0IChpbnRlZ2VyX3R5cGVfbm9kZSwgZW5jb2RlZF9lbGVtc1tpXSkpOworICBy ZXR1cm4gYnVpbGRlci5idWlsZCAoKTsKK30KKworc3RhdGljIHZvaWQKK3Rlc3RfdmVjX3Blcm1f dmxhX2ZvbGRpbmcgKCkKK3sKKyAgaW50IGFyZzBfZWxlbXNbXSA9IHsgMSwgMTEsIDIsIDEyLCAz LCAxMyB9OworICB0cmVlIGFyZzAgPSBidWlsZF92ZWNfaW50X2NzdCAoMiwgMywgYXJnMF9lbGVt cyk7CisKKyAgaW50IGFyZzFfZWxlbXNbXSA9IHsgMjEsIDMxLCAyMiwgMzIsIDIzLCAzMyB9Owor ICB0cmVlIGFyZzEgPSBidWlsZF92ZWNfaW50X2NzdCAoMiwgMywgYXJnMV9lbGVtcyk7CisKKyAg aWYgKFRZUEVfVkVDVE9SX1NVQlBBUlRTIChUUkVFX1RZUEUgKGFyZzApKS5pc19jb25zdGFudCAo KQorICAgICAgfHwgVFlQRV9WRUNUT1JfU1VCUEFSVFMgKFRSRUVfVFlQRSAoYXJnMSkpLmlzX2Nv bnN0YW50ICgpKQorICAgIHJldHVybjsKKworICAvKiBDYXNlIDE6IEZvciBtYXNrOiB7MCwgMSwg MiwgLi4ufSwgbnBhdHRlcm5zID09IDEsIG5lbHRzX3Blcl9wYXR0ZXJuID09IDMsCisgICAgIHNo b3VsZCBzZWxlY3QgYXJnMC4gICovCisgIHsKKyAgICBpbnQgbWFza19lbGVtc1tdID0gezAsIDEs IDJ9OworICAgIHRyZWUgbWFzayA9IGJ1aWxkX3ZlY19pbnRfY3N0ICgxLCAzLCBtYXNrX2VsZW1z KTsKKyAgICB0cmVlIHJlcyA9IGZvbGRfdGVybmFyeSAoVkVDX1BFUk1fRVhQUiwgVFJFRV9UWVBF IChhcmcwKSwgYXJnMCwgYXJnMSwgbWFzayk7CisgICAgQVNTRVJUX1RSVUUgKFZFQ1RPUl9DU1Rf TlBBVFRFUk5TIChyZXMpID09IDIpOworICAgIEFTU0VSVF9UUlVFIChWRUNUT1JfQ1NUX05FTFRT X1BFUl9QQVRURVJOIChyZXMpID09IDMpOworCisgICAgdW5zaWduZWQgcmVzX25lbHRzID0gdmVj dG9yX2NzdF9lbmNvZGVkX25lbHRzIChyZXMpOworICAgIGZvciAodW5zaWduZWQgaSA9IDA7IGkg PCByZXNfbmVsdHM7IGkrKykKKyAgICAgIEFTU0VSVF9UUlVFIChvcGVyYW5kX2VxdWFsX3AgKFZF Q1RPUl9DU1RfRUxUIChyZXMsIGkpLAorCQkJCSAgICBWRUNUT1JfQ1NUX0VMVCAoYXJnMCwgaSks IDApKTsKKyAgfQorCisgIC8qIENhc2UgMjogRm9yIG1hc2s6IHs0LCA1LCA2LCAuLi59LCBucGF0 dGVybnMgPT0gMSwgbmVsdHNfcGVyX3BhdHRlcm4gPT0gMywKKyAgICAgc2hvdWxkIHJldHVybiBO VUxMIGJlY2F1c2UgZm9yIGxlbiA9IDQgKyA0eCwKKyAgICAgaWYgeCA9PSAwLCB3ZSBzZWxlY3Qg ZnJvbSBhcmcxCisgICAgIGlmIHggPiAwLCB3ZSBzZWxlY3QgZnJvbSBhcmcwCisgICAgIGFuZCB0 aHVzIGNhbm5vdCBkZXRlcm1pbmUgcmVzdWx0IGF0IGNvbXBpbGUgdGltZS4gICovCisgIHsKKyAg ICBpbnQgbWFza19lbGVtc1tdID0gezQsIDUsIDZ9OworICAgIHRyZWUgbWFzayA9IGJ1aWxkX3Zl Y19pbnRfY3N0ICgxLCAzLCBtYXNrX2VsZW1zKTsKKyAgICB0cmVlIHJlcyA9IGZvbGRfdGVybmFy eSAoVkVDX1BFUk1fRVhQUiwgVFJFRV9UWVBFIChhcmcwKSwgYXJnMCwgYXJnMSwgbWFzayk7Cisg ICAgZ2NjX2Fzc2VydCAocmVzID09IE5VTExfVFJFRSk7CisgIH0KKworICAvKiBDYXNlIDM6Cisg ICAgIG1hc2s6IHswLCAwLCAwLCAxLCAwLCAyLCAuLi59IAorICAgICBucGF0dGVybnMgPT0gMiwg bmVsdHNfcGVyX3BhdHRlcm4gPT0gMworICAgICBQYXR0ZXJuIHswLCAuLi59IHNob3VsZCBzZWxl Y3QgYXJnMFswXSwgaWUsIDEuCisgICAgIFBhdHRlcm4gezAsIDEsIDIsIC4uLn0gc2hvdWxkIHNl bGVjdCBhcmcwOiB7MSwgMTEsIDIsIC4uLn0sCisgICAgIHNvIHJlcyA9IHsxLCAxLCAxLCAxMSwg MSwgMiwgLi4ufS4gICovCisgIHsKKyAgICBpbnQgbWFza19lbGVtc1tdID0gezAsIDAsIDAsIDEs IDAsIDJ9OworICAgIHRyZWUgbWFzayA9IGJ1aWxkX3ZlY19pbnRfY3N0ICgyLCAzLCBtYXNrX2Vs ZW1zKTsKKyAgICB0cmVlIHJlcyA9IGZvbGRfdGVybmFyeSAoVkVDX1BFUk1fRVhQUiwgVFJFRV9U WVBFIChhcmcwKSwgYXJnMCwgYXJnMSwgbWFzayk7CisKKyAgICBBU1NFUlRfVFJVRSAoVkVDVE9S X0NTVF9OUEFUVEVSTlMgKHJlcykgPT0gMik7CisgICAgQVNTRVJUX1RSVUUgKFZFQ1RPUl9DU1Rf TkVMVFNfUEVSX1BBVFRFUk4gKHJlcykgPT0gMyk7CisKKyAgICAvKiBDaGVjayBlbmNvZGluZzog ezEsIDExLCAyLCAuLi59ICovCisgICAgaW50IHJlc19lbmNvZGVkX2VsZW1zW10gPSB7MSwgMSwg MSwgMTEsIDEsIDJ9OworICAgIGZvciAodW5zaWduZWQgaSA9IDA7IGkgPCB2ZWN0b3JfY3N0X2Vu Y29kZWRfbmVsdHMgKHJlcyk7IGkrKykKKyAgICAgIEFTU0VSVF9UUlVFICh3aTo6dG9fd2lkZShW RUNUT1JfQ1NUX0VMVCAocmVzLCBpKSkgPT0gcmVzX2VuY29kZWRfZWxlbXNbaV0pOworICB9CisK KyAgLyogQ2FzZSA0OgorICAgICBtYXNrOiB7MCwgNCArIDR4LCAwLCA1ICsgNHgsIDAsIDYgKyA0 eCwgLi4ufQorICAgICBucGF0dGVybnMgPT0gMiwgbmVsdHNfcGVyX3BhdHRlcm4gPT0gMworICAg ICBQYXR0ZXJuIHswLCAuLi59IHNob3VsZCBzZWxlY3QgYXJnMFsxXQorICAgICBQYXR0ZXJuIHs0 ICsgNHgsIDUgKyA0eCwgNiArIDR4LCAuLi59IHNob3VsZCBzZWxlY3QgZnJvbSBhcmcxLCBzaW5j ZToKKyAgICAgYTEgPSA1ICsgNHgKKyAgICAgYWUgPSAoNSArIDR4KSArICgoNCArIDR4KSAvIDIg LSAyKSAqIDEKKyAgICAgICAgPSA1ICsgNngKKyAgICAgU2luY2UgYTEvNCs0eCA9PSBhZS80KzR4 ID09IDEsIHdlIHNlbGVjdCBhcmcxWzBdLCBhcmcxWzFdLCBhcmcxWzJdLCAuLi4KKyAgICAgcmVz OiB7MSwgMjEsIDEsIDMxLCAxLCAyMiwgLi4uIH0KKyAgICAgRklYTUU6IEhvdyB0byBidWlsZCB2 ZWN0b3Igd2l0aCBwb2x5X2ludCBlbGVtcyA/ICAqLworCisgIC8qIENhc2UgNTogUyA8IDAuICAq LworfQorCiAvKiBSdW4gYWxsIG9mIHRoZSBzZWxmdGVzdHMgd2l0aGluIHRoaXMgZmlsZS4gICov CiAKIHZvaWQKQEAgLTE2OTE4LDYgKzE3MTAxLDcgQEAgZm9sZF9jb25zdF9jY190ZXN0cyAoKQog ICB0ZXN0X2FyaXRobWV0aWNfZm9sZGluZyAoKTsKICAgdGVzdF92ZWN0b3JfZm9sZGluZyAoKTsK ICAgdGVzdF92ZWNfZHVwbGljYXRlX2ZvbGRpbmcgKCk7CisgIHRlc3RfdmVjX3Blcm1fdmxhX2Zv bGRpbmcgKCk7CiB9CiAKIH0gLy8gbmFtZXNwYWNlIHNlbGZ0ZXN0Cg== --0000000000009bf4bd05eb387e54--