linux-kernel - Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-Id: <201012021712.49377.br1@einfach.org>
Date:	Thu, 2 Dec 2010 17:12:49 +0900
From:	Bruno Randolf <br1@...fach.org>
To:	Peter Zijlstra <peterz@...radead.org>
Cc:	Bob Copeland <me@...copeland.com>,
	Johannes Berg <johannes@...solutions.net>,
	Jouni Malinen <j@...fi>, linville@...driver.com,
	randy.dunlap@...cle.com, blp@...stanford.edu,
	linux-wireless@...r.kernel.org, linux-kernel@...r.kernel.org,
	Lars_Ericsson@...ia.com, stefanr@...6.in-berlin.de,
	kosaki.motohiro@...fujitsu.com, akpm@...ux-foundation.org,
	kevin.granade@...il.com
Subject: Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

On Sat November 20 2010 08:01:55 Peter Zijlstra wrote:
> On Fri, 2010-11-19 at 17:28 -0500, Bob Copeland wrote:
> > On Fri, Nov 19, 2010 at 06:07:05PM +0900, Bruno Randolf wrote:
> > > Hmm, maybe I suck in mathemathics, but I don't see a way to do that
> > > given the formula:
> > > 
> > > (((internal * (weight - 1)) + (val * factor)) / weight
> > 
> > I was thinking something along the lines of:
> > 
> > round = (1 << n) - 1;
> > (((internal * (weight - 1) + round) >> n) + val) * ((1 << n) / weight)
> > 
> > where (1 << n) is the factor and ((1 << n) / weight) can be precomputed.
> > If you think about it, this is just reciprocal multiplication in fixed-
> > point math with n bits of decimal resolution.
> > 
> > The problem is the shift of the older terms introduces roundoff error,
> > but there are some tricks you can do to maintain bounded error, e.g.
> > shifting by some smaller factor of n and scaling other terms -- in the
> > limit you reinvent floating point and then it's slower than division :)
> 
> Sure, x/y := x/z * z/y, and by picking z := 2^n, we can pre-compute z/y
> and write x/z using a shift. The problem however is always range vs
> granularity, you chose to first /z and then *z/y, this avoids some
> overflow issues but truncates the lower n bits of x.
> 
> If you first *z/y and then /z you keep your low bits but risk loosing
> the top bits to an overflow.
> 
> I guess the question is do we really need weights outside of 2^n? If
> not, you can use the weight := 2^n version. If you do, you get to pick
> either of the previously mentioned options.
> 
> Sadly gcc doesn't sanely support a u128 type, which would be very useful
> to avoid some of these overflow issues (like we used to use u64 mults
> for u32 fixed points mults).

Thank you all for your help and sorry for following up so late!

I think we don't really need weights outside of 2^n and i'm going to post a 
patch based on Peter Zijlstra's formula. Thanks again! Would it make sense to 
have the factor 2^n too, so we can bitshift there too?

bruno
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/