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 394A5C77B7C for ; Sun, 28 May 2023 17:26:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229528AbjE1R0W (ORCPT ); Sun, 28 May 2023 13:26:22 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:41768 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229448AbjE1R0V (ORCPT ); Sun, 28 May 2023 13:26:21 -0400 X-Greylist: delayed 100683 seconds by postgrey-1.37 at lindbergh.monkeyblade.net; Sun, 28 May 2023 10:26:19 PDT Received: from mout-p-201.mailbox.org (mout-p-201.mailbox.org [80.241.56.171]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B7AC1B1; Sun, 28 May 2023 10:26:19 -0700 (PDT) Received: from smtp1.mailbox.org (smtp1.mailbox.org [IPv6:2001:67c:2050:b231:465::1]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-384) server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by mout-p-201.mailbox.org (Postfix) with ESMTPS id 4QTltq5jctz9sZJ; Sun, 28 May 2023 19:26:11 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oltmanns.dev; s=MBO0001; t=1685294771; 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=ANj+Sn4qSAMQRyLYAP3nENDTtacjr1EZwvPAnMBhYsY=; b=Ybw4hf/mHfr+Jm/7JyfCMeoI0OVOU1gMo9Gtj8jSay5HVfWNrOYCEk1w19KP2AzZTFE2k+ PXsWQTD5xr+BvfKtT7L9Mx3y5Jl2gQVdwjjBjFLq8iNUfjlSAc7Wiqaj/eWh2trG+tHAFG hARVYBIpjhbyBfzOJnB3UhLCxO+Zghwz7LSizikgdOo1/bvVuTl1kQuNTxXNWAOh6tNjvB PhWExZy/fnLsxVjiddhef7GHCGsOMJBMTLTxUWuqZXY2b3q8+lEYl12QBVbzLbXRCcA/g9 SL0rLWU0GOJCqAsAfT6s6jvHKQjwJtVFlQ3KWGAO7XeX861V+4lf6ZARaT1yZw== References: <20230527132747.83196-1-frank@oltmanns.dev> <20230527132747.83196-3-frank@oltmanns.dev> <87sfbgwyvp.fsf@oltmanns.dev> From: Frank Oltmanns To: Julian Calaby Cc: linux-arm-kernel@lists.infradead.org, linux-clk@vger.kernel.org, linux-kernel@vger.kernel.org, linux-sunxi@lists.linux.dev, Andre Przywara , Chen-Yu Tsai , Icenowy Zheng , Jernej Skrabec , Maxime Ripard , Michael Turquette , Rob Herring , Samuel Holland , Stephen Boyd Subject: Re: [RFC PATCH 2/3] clk: sunxi-ng: Implement precalculated NKM rate selection Date: Sun, 28 May 2023 19:12:05 +0200 In-reply-to: Message-ID: <87h6rwcqqk.fsf@oltmanns.dev> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Rspamd-Queue-Id: 4QTltq5jctz9sZJ Precedence: bulk List-ID: X-Mailing-List: linux-clk@vger.kernel.org Hi Julian, On 2023-05-29 at 01:32:02 +1000, Julian Calaby wr= ote: > Hi Frank, > > On Sun, May 28, 2023 at 8:10=E2=80=AFPM Frank Oltmanns wrote: >> >> Hi Julian, >> >> On 2023-05-28 at 09:19:36 +1000, Julian Calaby = wrote: >> > Hi Frank, >> > >> > On Sat, May 27, 2023 at 11:37=E2=80=AFPM Frank Oltmanns wrote: >> >> >> >> Add a new precalculation method for NKM clock rate selection in the >> >> sunxi-ng clock driver. Introduce ccu_nkm_find_best_precalc which uses= a >> >> precalculated table of valid NKM combinations (struct clk_nkm_table a= nd >> >> struct clk_nkm_combo) to find the best rate. This approach provides >> >> faster rate selection by searching a table of valid combinations rath= er >> >> than calculating for all possible combinations. >> >> >> >> The table of NKM combinations needs to be initialized with meaningful >> >> combinations only, i.e. removing redundant combinations that result in >> >> the same rate. >> >> >> >> Keep the existing ccu_nkm_find_best function in place and use it as a >> >> fallback if no precalculated table is provided. >> >> >> >> Signed-off-by: Frank Oltmanns >> >> --- >> >> drivers/clk/sunxi-ng/ccu_nkm.c | 84 +++++++++++++++++++++++++++-----= -- >> >> drivers/clk/sunxi-ng/ccu_nkm.h | 26 +++++++++++ >> >> 2 files changed, 94 insertions(+), 16 deletions(-) >> >> >> >> diff --git a/drivers/clk/sunxi-ng/ccu_nkm.c b/drivers/clk/sunxi-ng/cc= u_nkm.c >> >> index 94d2a83992b2..9652f6df17bd 100644 >> >> --- a/drivers/clk/sunxi-ng/ccu_nkm.c >> >> +++ b/drivers/clk/sunxi-ng/ccu_nkm.c >> >> @@ -54,6 +54,49 @@ static unsigned long ccu_nkm_find_best(unsigned lo= ng parent, unsigned long rate, >> >> return best_rate; >> >> } >> >> >> >> +static unsigned long ccu_nkm_find_best_precalc(unsigned long parent, >> >> + unsigned long rate, >> >> + struct _ccu_nkm *nkm, >> >> + struct clk_nkm_table *= table) >> >> +{ >> >> + unsigned long best_rate =3D 0, best_diff =3D ULONG_MAX; >> >> + unsigned long best_n =3D 0, best_k =3D 0, best_m =3D 0; >> >> + int start =3D 0, end =3D table->num - 1, mid; >> >> + >> >> + while (start <=3D end) { >> >> + unsigned long tmp_rate; >> >> + unsigned long tmp_diff; >> >> + >> >> + mid =3D (start + end) / 2; >> >> + >> >> + tmp_rate =3D parent * table->combos[mid].n * table->c= ombos[mid].k / >> >> + table->combos[mid].m; >> >> + >> >> + tmp_diff =3D abs(rate - tmp_rate); >> >> + >> >> + if (tmp_diff < best_diff) { >> >> + best_rate =3D tmp_rate; >> >> + best_diff =3D tmp_diff; >> >> + best_n =3D table->combos[mid].n; >> >> + best_k =3D table->combos[mid].k; >> >> + best_m =3D table->combos[mid].m; >> >> + if (best_diff =3D=3D 0) >> >> + goto out; >> >> + } >> > >> >> Thank you for your feedback! >> >> In my proposal, the code performs a binary search by >> 1. taking the element in the middle (mid) >> 2. calculating the rate of the element (tmp_rate) >> 3. calculating the difference to the requested rate (tmp_diff) >> 4. if the diff is better than the best_diff making it the new best >> n-k-m-combo (the if block) > > I'm so sorry, I thought that this was still doing a linear search as > it's so close to the original code. > >> >> > If the table was sorted by n * k / m, this could just be a process of >> >> Please note, the table already has to be sorted for the function to >> work, as is the nature of a binary search. I should definitely add >> comments. I'm sorry, the code was intended more as a basis to discuss >> the general idea that I described in the cover letter. I should have >> made that clearer. >> >> > searching through until we either: >> > - find that the first rate in the table is too high >> >> I could see that I could add two steps in the beginning, before the loop: >> - Take the first element and see if its rate is greater than the >> requested rate, if so immediatly return it >> - Take the last element and see if its rate is less than the requested >> rate, if so immediatly return it >> >> Is that what you mean? I'd have to run some simulations to see, if this >> is a real improvement, because we would need two additional rate >> calculations. Worst case would therefore be 2+log(n) calculations >> instead of log(n) and the code would be slightly more complicated in my >> opinion. But if we run this function with all possible parents rate (as >> suggested in the end of my cover letter) these two special cases could >> very well be often applicable. Thanks! >> >> > - find an exact rate >> >> What do you mean by "exact rate"? Do you mean a rate that matches the >> requested rate exactly. This is what the code is already trying to do. >> But, as this is not always possible, in cases where it does not find an >> exact match, it takes the closest match instead. >> >> > - go above the requested rate, then there's only two to compare: our >> > current rate and the previous one >> >> Sorry, you've lost me here. How would I go above the requested rate? You >> would have to do the binary search to find that rate, but then why not >> search the closest rate directly (as the code does) instead of searching >> the closest rate above the requested (as you proposed). I feel like >> either one of us is missing something. :) > > What we're missing is that I'm not explaining this well. > > Let's take a very simple table: (value =3D parent * n * k / m) > > 0. 100 > 1. 200 > 2. 300 > 3. 400 > > If we search for 50, our closest is the first rate, so index 0: this > is the "find that the first rate in the table is too high" case. > > If we search for 300, we'll converge on index 2: this is the "exact > rate" situation. > > If we search for 275, then we'll converge on either 200 or 300: this > is the "two to compare" situation: if we converge until we get to the > lowest rate above our target, we only need to check the rate > immediately before it in the table and the one we converged on to find > the closest. > > So in pseudo-code, we'd end up with something like this: > > -------- > > start =3D 0; > > cur_rate =3D parent * table[start].n * table[start].k / table[start].m; > > if (cur_rate >=3D target) > return table[start]; > > while (start <=3D end) { > mid =3D (start + end) / 2; Thanks for the thorough explanation! This needs to be (start + end + 1) / 2 Otherwise, if we extend your hypothetical list above with another item, let's say 500 and look for 199, this would result in the loop finishing with mid =3D 0, if I'm not mistaken, and hence an access to table[-1] when calculating prev_rate below. Not good. But I *think*, with (start + end + 1) / 2 it works in all cases. > > cur_rate =3D parent * table[mid].n * table[mid].k / table[mid].m; > > if (cur_rate =3D=3D target) > return table[mid]; > > if (target < cur_rate) > end =3D mid - 1; > else > start =3D mid + 1; > } > > prev_rate =3D parent * table[mid - 1].n * table[mid - 1].k / table[mid - = 1].m; > > if (abs(target - prev_rate) < abs(target - cur_rate)) > return table[mid - 1]; > > return table[mid]; > > -------- > > Which seems simpler to my eye and moves all the difference > calculations out of the loop so they only have to be done once, > effectively trading a difference calculation on each checked rate for > a rate calculation, and dropping some variables in the process. At least it's shorter. I'm not sure it's simpler (after all it contained a mistake, I think ;-)). Still, it looks neat, so I might still use your (revised) algorithm. Thanks, Frank > > Thanks, 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 bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 99B6BC7EE29 for ; Sun, 28 May 2023 17:27:04 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:Message-ID:In-reply-to: Date:Subject:Cc:To:From:References:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=aKnWPSyWt9duzv+6y97KXTkQEJfQp/IwHl3EO66SKTs=; b=Cs2u/JHsxqP+jG bXEUjTWgEyzB7xXLe+mmCHO9AidZVBhOhQp9NvFAep3Fs2CdaQO7d+4D0qxpSLDzum5WreNEx2LyV De7P/bj8gq4HQKxSjhKBUIT9aiOA1VMwPhJqACfhdrvdznN45VqAYEmYqodW53XTylq1FgYNXmMuz 0bWnd2xGLpTogW/4t5mEb+FnqrNJAe6Hx5v/3kpDU6rVpF3bMVgv0JcM/RuBSh9AlPJl3TqIVWr3C v0l84+sMOp+2CEFyX91knQf0QbDdQKHAlgpDXn+O3BCKvDrTXhjm/MNITPdz61kCDB7M6x3TEas3p +c6/3EnYFGlAC+XrcNUg==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.96 #2 (Red Hat Linux)) id 1q3KA4-0089CT-0h; Sun, 28 May 2023 17:26:32 +0000 Received: from mout-p-201.mailbox.org ([80.241.56.171]) by bombadil.infradead.org with esmtps (Exim 4.96 #2 (Red Hat Linux)) id 1q3K9z-0089As-15 for linux-arm-kernel@lists.infradead.org; Sun, 28 May 2023 17:26:30 +0000 Received: from smtp1.mailbox.org (smtp1.mailbox.org [IPv6:2001:67c:2050:b231:465::1]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-384) server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by mout-p-201.mailbox.org (Postfix) with ESMTPS id 4QTltq5jctz9sZJ; Sun, 28 May 2023 19:26:11 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oltmanns.dev; s=MBO0001; t=1685294771; 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=ANj+Sn4qSAMQRyLYAP3nENDTtacjr1EZwvPAnMBhYsY=; b=Ybw4hf/mHfr+Jm/7JyfCMeoI0OVOU1gMo9Gtj8jSay5HVfWNrOYCEk1w19KP2AzZTFE2k+ PXsWQTD5xr+BvfKtT7L9Mx3y5Jl2gQVdwjjBjFLq8iNUfjlSAc7Wiqaj/eWh2trG+tHAFG hARVYBIpjhbyBfzOJnB3UhLCxO+Zghwz7LSizikgdOo1/bvVuTl1kQuNTxXNWAOh6tNjvB PhWExZy/fnLsxVjiddhef7GHCGsOMJBMTLTxUWuqZXY2b3q8+lEYl12QBVbzLbXRCcA/g9 SL0rLWU0GOJCqAsAfT6s6jvHKQjwJtVFlQ3KWGAO7XeX861V+4lf6ZARaT1yZw== References: <20230527132747.83196-1-frank@oltmanns.dev> <20230527132747.83196-3-frank@oltmanns.dev> <87sfbgwyvp.fsf@oltmanns.dev> From: Frank Oltmanns To: Julian Calaby Cc: linux-arm-kernel@lists.infradead.org, linux-clk@vger.kernel.org, linux-kernel@vger.kernel.org, linux-sunxi@lists.linux.dev, Andre Przywara , Chen-Yu Tsai , Icenowy Zheng , Jernej Skrabec , Maxime Ripard , Michael Turquette , Rob Herring , Samuel Holland , Stephen Boyd Subject: Re: [RFC PATCH 2/3] clk: sunxi-ng: Implement precalculated NKM rate selection Date: Sun, 28 May 2023 19:12:05 +0200 In-reply-to: Message-ID: <87h6rwcqqk.fsf@oltmanns.dev> MIME-Version: 1.0 X-Rspamd-Queue-Id: 4QTltq5jctz9sZJ X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20230528_102627_525298_7411FDED X-CRM114-Status: GOOD ( 47.04 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list 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-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org SGkgSnVsaWFuLAoKT24gMjAyMy0wNS0yOSBhdCAwMTozMjowMiArMTAwMCwgSnVsaWFuIENhbGFi eSA8anVsaWFuLmNhbGFieUBnbWFpbC5jb20+IHdyb3RlOgo+IEhpIEZyYW5rLAo+Cj4gT24gU3Vu LCBNYXkgMjgsIDIwMjMgYXQgODoxMOKAr1BNIEZyYW5rIE9sdG1hbm5zIDxmcmFua0BvbHRtYW5u cy5kZXY+IHdyb3RlOgo+Pgo+PiBIaSBKdWxpYW4sCj4+Cj4+IE9uIDIwMjMtMDUtMjggYXQgMDk6 MTk6MzYgKzEwMDAsIEp1bGlhbiBDYWxhYnkgPGp1bGlhbi5jYWxhYnlAZ21haWwuY29tPiB3cm90 ZToKPj4gPiBIaSBGcmFuaywKPj4gPgo+PiA+IE9uIFNhdCwgTWF5IDI3LCAyMDIzIGF0IDExOjM3 4oCvUE0gRnJhbmsgT2x0bWFubnMgPGZyYW5rQG9sdG1hbm5zLmRldj4gd3JvdGU6Cj4+ID4+Cj4+ ID4+IEFkZCBhIG5ldyBwcmVjYWxjdWxhdGlvbiBtZXRob2QgZm9yIE5LTSBjbG9jayByYXRlIHNl bGVjdGlvbiBpbiB0aGUKPj4gPj4gc3VueGktbmcgY2xvY2sgZHJpdmVyLiBJbnRyb2R1Y2UgY2N1 X25rbV9maW5kX2Jlc3RfcHJlY2FsYyB3aGljaCB1c2VzIGEKPj4gPj4gcHJlY2FsY3VsYXRlZCB0 YWJsZSBvZiB2YWxpZCBOS00gY29tYmluYXRpb25zIChzdHJ1Y3QgY2xrX25rbV90YWJsZSBhbmQK Pj4gPj4gc3RydWN0IGNsa19ua21fY29tYm8pIHRvIGZpbmQgdGhlIGJlc3QgcmF0ZS4gVGhpcyBh cHByb2FjaCBwcm92aWRlcwo+PiA+PiBmYXN0ZXIgcmF0ZSBzZWxlY3Rpb24gYnkgc2VhcmNoaW5n IGEgdGFibGUgb2YgdmFsaWQgY29tYmluYXRpb25zIHJhdGhlcgo+PiA+PiB0aGFuIGNhbGN1bGF0 aW5nIGZvciBhbGwgcG9zc2libGUgY29tYmluYXRpb25zLgo+PiA+Pgo+PiA+PiBUaGUgdGFibGUg b2YgTktNIGNvbWJpbmF0aW9ucyBuZWVkcyB0byBiZSBpbml0aWFsaXplZCB3aXRoIG1lYW5pbmdm dWwKPj4gPj4gY29tYmluYXRpb25zIG9ubHksIGkuZS4gcmVtb3ZpbmcgcmVkdW5kYW50IGNvbWJp bmF0aW9ucyB0aGF0IHJlc3VsdCBpbgo+PiA+PiB0aGUgc2FtZSByYXRlLgo+PiA+Pgo+PiA+PiBL ZWVwIHRoZSBleGlzdGluZyBjY3VfbmttX2ZpbmRfYmVzdCBmdW5jdGlvbiBpbiBwbGFjZSBhbmQg dXNlIGl0IGFzIGEKPj4gPj4gZmFsbGJhY2sgaWYgbm8gcHJlY2FsY3VsYXRlZCB0YWJsZSBpcyBw cm92aWRlZC4KPj4gPj4KPj4gPj4gU2lnbmVkLW9mZi1ieTogRnJhbmsgT2x0bWFubnMgPGZyYW5r QG9sdG1hbm5zLmRldj4KPj4gPj4gLS0tCj4+ID4+ICBkcml2ZXJzL2Nsay9zdW54aS1uZy9jY3Vf bmttLmMgfCA4NCArKysrKysrKysrKysrKysrKysrKysrKysrKystLS0tLS0tCj4+ID4+ICBkcml2 ZXJzL2Nsay9zdW54aS1uZy9jY3VfbmttLmggfCAyNiArKysrKysrKysrKwo+PiA+PiAgMiBmaWxl cyBjaGFuZ2VkLCA5NCBpbnNlcnRpb25zKCspLCAxNiBkZWxldGlvbnMoLSkKPj4gPj4KPj4gPj4g ZGlmZiAtLWdpdCBhL2RyaXZlcnMvY2xrL3N1bnhpLW5nL2NjdV9ua20uYyBiL2RyaXZlcnMvY2xr L3N1bnhpLW5nL2NjdV9ua20uYwo+PiA+PiBpbmRleCA5NGQyYTgzOTkyYjIuLjk2NTJmNmRmMTdi ZCAxMDA2NDQKPj4gPj4gLS0tIGEvZHJpdmVycy9jbGsvc3VueGktbmcvY2N1X25rbS5jCj4+ID4+ ICsrKyBiL2RyaXZlcnMvY2xrL3N1bnhpLW5nL2NjdV9ua20uYwo+PiA+PiBAQCAtNTQsNiArNTQs NDkgQEAgc3RhdGljIHVuc2lnbmVkIGxvbmcgY2N1X25rbV9maW5kX2Jlc3QodW5zaWduZWQgbG9u ZyBwYXJlbnQsIHVuc2lnbmVkIGxvbmcgcmF0ZSwKPj4gPj4gICAgICAgICByZXR1cm4gYmVzdF9y YXRlOwo+PiA+PiAgfQo+PiA+Pgo+PiA+PiArc3RhdGljIHVuc2lnbmVkIGxvbmcgY2N1X25rbV9m aW5kX2Jlc3RfcHJlY2FsYyh1bnNpZ25lZCBsb25nIHBhcmVudCwKPj4gPj4gKyAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB1bnNpZ25lZCBsb25nIHJhdGUsCj4+ ID4+ICsgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc3RydWN0 IF9jY3VfbmttICpua20sCj4+ID4+ICsgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgc3RydWN0IGNsa19ua21fdGFibGUgKnRhYmxlKQo+PiA+PiArewo+PiA+PiAr ICAgICAgIHVuc2lnbmVkIGxvbmcgYmVzdF9yYXRlID0gMCwgYmVzdF9kaWZmID0gVUxPTkdfTUFY Owo+PiA+PiArICAgICAgIHVuc2lnbmVkIGxvbmcgYmVzdF9uID0gMCwgYmVzdF9rID0gMCwgYmVz dF9tID0gMDsKPj4gPj4gKyAgICAgICBpbnQgc3RhcnQgPSAwLCBlbmQgPSB0YWJsZS0+bnVtIC0g MSwgbWlkOwo+PiA+PiArCj4+ID4+ICsgICAgICAgd2hpbGUgKHN0YXJ0IDw9IGVuZCkgewo+PiA+ PiArICAgICAgICAgICAgICAgdW5zaWduZWQgbG9uZyB0bXBfcmF0ZTsKPj4gPj4gKyAgICAgICAg ICAgICAgIHVuc2lnbmVkIGxvbmcgdG1wX2RpZmY7Cj4+ID4+ICsKPj4gPj4gKyAgICAgICAgICAg ICAgIG1pZCA9IChzdGFydCArIGVuZCkgLyAyOwo+PiA+PiArCj4+ID4+ICsgICAgICAgICAgICAg ICB0bXBfcmF0ZSA9IHBhcmVudCAqIHRhYmxlLT5jb21ib3NbbWlkXS5uICogdGFibGUtPmNvbWJv c1ttaWRdLmsgLwo+PiA+PiArICAgICAgICAgICAgICAgICAgICAgICAgICB0YWJsZS0+Y29tYm9z W21pZF0ubTsKPj4gPj4gKwo+PiA+PiArICAgICAgICAgICAgICAgdG1wX2RpZmYgPSBhYnMocmF0 ZSAtIHRtcF9yYXRlKTsKPj4gPj4gKwo+PiA+PiArICAgICAgICAgICAgICAgaWYgKHRtcF9kaWZm IDwgYmVzdF9kaWZmKSB7Cj4+ID4+ICsgICAgICAgICAgICAgICAgICAgICAgIGJlc3RfcmF0ZSA9 IHRtcF9yYXRlOwo+PiA+PiArICAgICAgICAgICAgICAgICAgICAgICBiZXN0X2RpZmYgPSB0bXBf ZGlmZjsKPj4gPj4gKyAgICAgICAgICAgICAgICAgICAgICAgYmVzdF9uID0gdGFibGUtPmNvbWJv c1ttaWRdLm47Cj4+ID4+ICsgICAgICAgICAgICAgICAgICAgICAgIGJlc3RfayA9IHRhYmxlLT5j b21ib3NbbWlkXS5rOwo+PiA+PiArICAgICAgICAgICAgICAgICAgICAgICBiZXN0X20gPSB0YWJs ZS0+Y29tYm9zW21pZF0ubTsKPj4gPj4gKyAgICAgICAgICAgICAgICAgICAgICAgaWYgKGJlc3Rf ZGlmZiA9PSAwKQo+PiA+PiArICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGdvdG8gb3V0 Owo+PiA+PiArICAgICAgICAgICAgICAgfQo+PiA+Cj4+Cj4+IFRoYW5rIHlvdSBmb3IgeW91ciBm ZWVkYmFjayEKPj4KPj4gSW4gbXkgcHJvcG9zYWwsIHRoZSBjb2RlIHBlcmZvcm1zIGEgYmluYXJ5 IHNlYXJjaCBieQo+PiAgMS4gdGFraW5nIHRoZSBlbGVtZW50IGluIHRoZSBtaWRkbGUgKG1pZCkK Pj4gIDIuIGNhbGN1bGF0aW5nIHRoZSByYXRlIG9mIHRoZSBlbGVtZW50ICh0bXBfcmF0ZSkKPj4g IDMuIGNhbGN1bGF0aW5nIHRoZSBkaWZmZXJlbmNlIHRvIHRoZSByZXF1ZXN0ZWQgcmF0ZSAodG1w X2RpZmYpCj4+ICA0LiBpZiB0aGUgZGlmZiBpcyBiZXR0ZXIgdGhhbiB0aGUgYmVzdF9kaWZmIG1h a2luZyBpdCB0aGUgbmV3IGJlc3QKPj4gICAgIG4tay1tLWNvbWJvICh0aGUgaWYgYmxvY2spCj4K PiBJJ20gc28gc29ycnksIEkgdGhvdWdodCB0aGF0IHRoaXMgd2FzIHN0aWxsIGRvaW5nIGEgbGlu ZWFyIHNlYXJjaCBhcwo+IGl0J3Mgc28gY2xvc2UgdG8gdGhlIG9yaWdpbmFsIGNvZGUuCj4KPj4K Pj4gPiBJZiB0aGUgdGFibGUgd2FzIHNvcnRlZCBieSBuICogayAvIG0sIHRoaXMgY291bGQganVz dCBiZSBhIHByb2Nlc3Mgb2YKPj4KPj4gUGxlYXNlIG5vdGUsIHRoZSB0YWJsZSBhbHJlYWR5IGhh cyB0byBiZSBzb3J0ZWQgZm9yIHRoZSBmdW5jdGlvbiB0bwo+PiB3b3JrLCBhcyBpcyB0aGUgbmF0 dXJlIG9mIGEgYmluYXJ5IHNlYXJjaC4gSSBzaG91bGQgZGVmaW5pdGVseSBhZGQKPj4gY29tbWVu dHMuIEknbSBzb3JyeSwgdGhlIGNvZGUgd2FzIGludGVuZGVkIG1vcmUgYXMgYSBiYXNpcyB0byBk aXNjdXNzCj4+IHRoZSBnZW5lcmFsIGlkZWEgdGhhdCBJIGRlc2NyaWJlZCBpbiB0aGUgY292ZXIg bGV0dGVyLiBJIHNob3VsZCBoYXZlCj4+IG1hZGUgdGhhdCBjbGVhcmVyLgo+Pgo+PiA+IHNlYXJj aGluZyB0aHJvdWdoIHVudGlsIHdlIGVpdGhlcjoKPj4gPiAtIGZpbmQgdGhhdCB0aGUgZmlyc3Qg cmF0ZSBpbiB0aGUgdGFibGUgaXMgdG9vIGhpZ2gKPj4KPj4gSSBjb3VsZCBzZWUgdGhhdCBJIGNv dWxkIGFkZCB0d28gc3RlcHMgaW4gdGhlIGJlZ2lubmluZywgYmVmb3JlIHRoZSBsb29wOgo+PiAg LSBUYWtlIHRoZSBmaXJzdCBlbGVtZW50IGFuZCBzZWUgaWYgaXRzIHJhdGUgaXMgZ3JlYXRlciB0 aGFuIHRoZQo+PiAgICByZXF1ZXN0ZWQgcmF0ZSwgaWYgc28gaW1tZWRpYXRseSByZXR1cm4gaXQK Pj4gIC0gVGFrZSB0aGUgbGFzdCBlbGVtZW50IGFuZCBzZWUgaWYgaXRzIHJhdGUgaXMgbGVzcyB0 aGFuIHRoZSByZXF1ZXN0ZWQKPj4gICAgcmF0ZSwgaWYgc28gaW1tZWRpYXRseSByZXR1cm4gaXQK Pj4KPj4gSXMgdGhhdCB3aGF0IHlvdSBtZWFuPyBJJ2QgaGF2ZSB0byBydW4gc29tZSBzaW11bGF0 aW9ucyB0byBzZWUsIGlmIHRoaXMKPj4gaXMgYSByZWFsIGltcHJvdmVtZW50LCBiZWNhdXNlIHdl IHdvdWxkIG5lZWQgdHdvIGFkZGl0aW9uYWwgcmF0ZQo+PiBjYWxjdWxhdGlvbnMuIFdvcnN0IGNh c2Ugd291bGQgdGhlcmVmb3JlIGJlIDIrbG9nKG4pIGNhbGN1bGF0aW9ucwo+PiBpbnN0ZWFkIG9m IGxvZyhuKSBhbmQgdGhlIGNvZGUgd291bGQgYmUgc2xpZ2h0bHkgbW9yZSBjb21wbGljYXRlZCBp biBteQo+PiBvcGluaW9uLiBCdXQgaWYgd2UgcnVuIHRoaXMgZnVuY3Rpb24gd2l0aCBhbGwgcG9z c2libGUgcGFyZW50cyByYXRlIChhcwo+PiBzdWdnZXN0ZWQgaW4gdGhlIGVuZCBvZiBteSBjb3Zl ciBsZXR0ZXIpIHRoZXNlIHR3byBzcGVjaWFsIGNhc2VzIGNvdWxkCj4+IHZlcnkgd2VsbCBiZSBv ZnRlbiBhcHBsaWNhYmxlLiBUaGFua3MhCj4+Cj4+ID4gLSBmaW5kIGFuIGV4YWN0IHJhdGUKPj4K Pj4gV2hhdCBkbyB5b3UgbWVhbiBieSAiZXhhY3QgcmF0ZSI/IERvIHlvdSBtZWFuIGEgcmF0ZSB0 aGF0IG1hdGNoZXMgdGhlCj4+IHJlcXVlc3RlZCByYXRlIGV4YWN0bHkuIFRoaXMgaXMgd2hhdCB0 aGUgY29kZSBpcyBhbHJlYWR5IHRyeWluZyB0byBkby4KPj4gQnV0LCBhcyB0aGlzIGlzIG5vdCBh bHdheXMgcG9zc2libGUsIGluIGNhc2VzIHdoZXJlIGl0IGRvZXMgbm90IGZpbmQgYW4KPj4gZXhh Y3QgbWF0Y2gsIGl0IHRha2VzIHRoZSBjbG9zZXN0IG1hdGNoIGluc3RlYWQuCj4+Cj4+ID4gLSBn byBhYm92ZSB0aGUgcmVxdWVzdGVkIHJhdGUsIHRoZW4gdGhlcmUncyBvbmx5IHR3byB0byBjb21w YXJlOiBvdXIKPj4gPiBjdXJyZW50IHJhdGUgYW5kIHRoZSBwcmV2aW91cyBvbmUKPj4KPj4gU29y cnksIHlvdSd2ZSBsb3N0IG1lIGhlcmUuIEhvdyB3b3VsZCBJIGdvIGFib3ZlIHRoZSByZXF1ZXN0 ZWQgcmF0ZT8gWW91Cj4+IHdvdWxkIGhhdmUgdG8gZG8gdGhlIGJpbmFyeSBzZWFyY2ggdG8gZmlu ZCB0aGF0IHJhdGUsIGJ1dCB0aGVuIHdoeSBub3QKPj4gc2VhcmNoIHRoZSBjbG9zZXN0IHJhdGUg ZGlyZWN0bHkgKGFzIHRoZSBjb2RlIGRvZXMpIGluc3RlYWQgb2Ygc2VhcmNoaW5nCj4+IHRoZSBj bG9zZXN0IHJhdGUgYWJvdmUgdGhlIHJlcXVlc3RlZCAoYXMgeW91IHByb3Bvc2VkKS4gSSBmZWVs IGxpa2UKPj4gZWl0aGVyIG9uZSBvZiB1cyBpcyBtaXNzaW5nIHNvbWV0aGluZy4gOikKPgo+IFdo YXQgd2UncmUgbWlzc2luZyBpcyB0aGF0IEknbSBub3QgZXhwbGFpbmluZyB0aGlzIHdlbGwuCj4K PiBMZXQncyB0YWtlIGEgdmVyeSBzaW1wbGUgdGFibGU6ICh2YWx1ZSA9IHBhcmVudCAqIG4gKiBr IC8gbSkKPgo+IDAuIDEwMAo+IDEuIDIwMAo+IDIuIDMwMAo+IDMuIDQwMAo+Cj4gSWYgd2Ugc2Vh cmNoIGZvciA1MCwgb3VyIGNsb3Nlc3QgaXMgdGhlIGZpcnN0IHJhdGUsIHNvIGluZGV4IDA6IHRo aXMKPiBpcyB0aGUgImZpbmQgdGhhdCB0aGUgZmlyc3QgcmF0ZSBpbiB0aGUgdGFibGUgaXMgdG9v IGhpZ2giIGNhc2UuCj4KPiBJZiB3ZSBzZWFyY2ggZm9yIDMwMCwgd2UnbGwgY29udmVyZ2Ugb24g aW5kZXggMjogdGhpcyBpcyB0aGUgImV4YWN0Cj4gcmF0ZSIgc2l0dWF0aW9uLgo+Cj4gSWYgd2Ug c2VhcmNoIGZvciAyNzUsIHRoZW4gd2UnbGwgY29udmVyZ2Ugb24gZWl0aGVyIDIwMCBvciAzMDA6 IHRoaXMKPiBpcyB0aGUgInR3byB0byBjb21wYXJlIiBzaXR1YXRpb246IGlmIHdlIGNvbnZlcmdl IHVudGlsIHdlIGdldCB0byB0aGUKPiBsb3dlc3QgcmF0ZSBhYm92ZSBvdXIgdGFyZ2V0LCB3ZSBv bmx5IG5lZWQgdG8gY2hlY2sgdGhlIHJhdGUKPiBpbW1lZGlhdGVseSBiZWZvcmUgaXQgaW4gdGhl IHRhYmxlIGFuZCB0aGUgb25lIHdlIGNvbnZlcmdlZCBvbiB0byBmaW5kCj4gdGhlIGNsb3Nlc3Qu Cj4KPiBTbyBpbiBwc2V1ZG8tY29kZSwgd2UnZCBlbmQgdXAgd2l0aCBzb21ldGhpbmcgbGlrZSB0 aGlzOgo+Cj4gLS0tLS0tLS0KPgo+IHN0YXJ0ID0gMDsKPgo+IGN1cl9yYXRlID0gcGFyZW50ICog dGFibGVbc3RhcnRdLm4gKiB0YWJsZVtzdGFydF0uayAvIHRhYmxlW3N0YXJ0XS5tOwo+Cj4gaWYg KGN1cl9yYXRlID49IHRhcmdldCkKPiAgICAgcmV0dXJuIHRhYmxlW3N0YXJ0XTsKPgo+IHdoaWxl IChzdGFydCA8PSBlbmQpIHsKPiAgICAgbWlkID0gKHN0YXJ0ICsgZW5kKSAvIDI7CgpUaGFua3Mg Zm9yIHRoZSB0aG9yb3VnaCBleHBsYW5hdGlvbiEKClRoaXMgbmVlZHMgdG8gYmUgKHN0YXJ0ICsg ZW5kICsgMSkgLyAyCgpPdGhlcndpc2UsIGlmIHdlIGV4dGVuZCB5b3VyIGh5cG90aGV0aWNhbCBs aXN0IGFib3ZlIHdpdGggYW5vdGhlciBpdGVtLApsZXQncyBzYXkgNTAwIGFuZCBsb29rIGZvciAx OTksIHRoaXMgd291bGQgcmVzdWx0IGluIHRoZSBsb29wIGZpbmlzaGluZwp3aXRoIG1pZCA9IDAs IGlmIEknbSBub3QgbWlzdGFrZW4sIGFuZCBoZW5jZSBhbiBhY2Nlc3MgdG8gdGFibGVbLTFdIHdo ZW4KY2FsY3VsYXRpbmcgcHJldl9yYXRlIGJlbG93LiBOb3QgZ29vZC4KCkJ1dCBJICp0aGluayos IHdpdGggKHN0YXJ0ICsgZW5kICsgMSkgLyAyIGl0IHdvcmtzIGluIGFsbCBjYXNlcy4KCj4KPiAg ICAgY3VyX3JhdGUgPSBwYXJlbnQgKiB0YWJsZVttaWRdLm4gKiB0YWJsZVttaWRdLmsgLyB0YWJs ZVttaWRdLm07Cj4KPiAgICAgaWYgKGN1cl9yYXRlID09IHRhcmdldCkKPiAgICAgICAgIHJldHVy biB0YWJsZVttaWRdOwo+Cj4gICAgaWYgKHRhcmdldCA8IGN1cl9yYXRlKQo+ICAgICAgICBlbmQg PSBtaWQgLSAxOwo+ICAgIGVsc2UKPiAgICAgICAgc3RhcnQgPSBtaWQgKyAxOwo+IH0KPgo+IHBy ZXZfcmF0ZSA9IHBhcmVudCAqIHRhYmxlW21pZCAtIDFdLm4gKiB0YWJsZVttaWQgLSAxXS5rIC8g dGFibGVbbWlkIC0gMV0ubTsKPgo+IGlmIChhYnModGFyZ2V0IC0gcHJldl9yYXRlKSA8IGFicyh0 YXJnZXQgLSBjdXJfcmF0ZSkpCj4gICAgIHJldHVybiB0YWJsZVttaWQgLSAxXTsKPgo+IHJldHVy biB0YWJsZVttaWRdOwo+Cj4gLS0tLS0tLS0KPgo+IFdoaWNoIHNlZW1zIHNpbXBsZXIgdG8gbXkg ZXllIGFuZCBtb3ZlcyBhbGwgdGhlIGRpZmZlcmVuY2UKPiBjYWxjdWxhdGlvbnMgb3V0IG9mIHRo ZSBsb29wIHNvIHRoZXkgb25seSBoYXZlIHRvIGJlIGRvbmUgb25jZSwKPiBlZmZlY3RpdmVseSB0 cmFkaW5nIGEgZGlmZmVyZW5jZSBjYWxjdWxhdGlvbiBvbiBlYWNoIGNoZWNrZWQgcmF0ZSBmb3IK PiBhIHJhdGUgY2FsY3VsYXRpb24sIGFuZCBkcm9wcGluZyBzb21lIHZhcmlhYmxlcyBpbiB0aGUg cHJvY2Vzcy4KCkF0IGxlYXN0IGl0J3Mgc2hvcnRlci4gSSdtIG5vdCBzdXJlIGl0J3Mgc2ltcGxl ciAoYWZ0ZXIgYWxsIGl0IGNvbnRhaW5lZAphIG1pc3Rha2UsIEkgdGhpbmsgOy0pKS4gU3RpbGws IGl0IGxvb2tzIG5lYXQsIHNvIEkgbWlnaHQgc3RpbGwgdXNlIHlvdXIKKHJldmlzZWQpIGFsZ29y aXRobS4KClRoYW5rcywKICBGcmFuawo+Cj4gVGhhbmtzLAoKX19fX19fX19fX19fX19fX19fX19f X19fX19fX19fX19fX19fX19fX19fX19fX18KbGludXgtYXJtLWtlcm5lbCBtYWlsaW5nIGxpc3QK bGludXgtYXJtLWtlcm5lbEBsaXN0cy5pbmZyYWRlYWQub3JnCmh0dHA6Ly9saXN0cy5pbmZyYWRl YWQub3JnL21haWxtYW4vbGlzdGluZm8vbGludXgtYXJtLWtlcm5lbAo=