linux-kernel - Re: [PATCH v10 1/3] lib: Add strongly typed 64bit int

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] [thread-next>] [day] [month] [year] [list]

Date:   Wed, 20 Dec 2017 18:30:24 +0100
From:   Crt Mori <cmo@...exis.com>
To:     David Laight <David.Laight@...lab.com>
Cc:     Peter Zijlstra <peterz@...radead.org>,
        Jonathan Cameron <jic23@...nel.org>,
        Ingo Molnar <mingo@...nel.org>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Kees Cook <keescook@...omium.org>,
        Rusty Russell <rusty@...tcorp.com.au>,
        Ian Abbott <abbotti@....co.uk>,
        Larry Finger <Larry.Finger@...inger.net>,
        Niklas Soderlund <niklas.soderlund+renesas@...natech.se>,
        Thomas Gleixner <tglx@...utronix.de>,
        Krzysztof Kozlowski <krzk@...nel.org>,
        Masahiro Yamada <yamada.masahiro@...ionext.com>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        "linux-iio@...r.kernel.org" <linux-iio@...r.kernel.org>,
        Joe Perches <joe@...ches.com>
Subject: Re: [PATCH v10 1/3] lib: Add strongly typed 64bit int_sqrt

On 20 December 2017 at 17:46, David Laight <David.Laight@...lab.com> wrote:
> From: Crt Mori
>> Sent: 20 December 2017 16:17
>>
>> On 20 December 2017 at 17:00, Peter Zijlstra <peterz@...radead.org> wrote:
>> > On Wed, Dec 20, 2017 at 02:39:26PM +0000, David Laight wrote:
>> >
>> >> With minor changes it ought to be possible to remove most of the
>> >> 64bit arithmetic and shifts.
>> >>
>> >> If you care about performance then using 32 bit maths will be much faster.
>> >
>> > Some, u64 add/sub/shift isn't exactly expensive, but yes, I also
>> > indicated that improvement is possible. At the very least y can be made
>> > a u32 I suppose.
>>
>> OK, is there any more easy optimizations you see?
>
> I think this version works.
> It doesn't have the optimisation for small values.
>
> unsigned int sqrt64(unsigned long long x)
> {
>         unsigned int x_hi = x >> 32;
>
>         unsigned int b = 0;
>         unsigned int y = 0;
>         unsigned int i;
>
>         for (i = 0; i < 32; i++) {
>                 b <<= 2;
>                 b |= x_hi >> 30;
>                 x_hi <<= 2;
>                 if (i == 15)
>                         x_hi = x;
>                 y <<= 1;
>                 if (b > y)
>                         b -= ++y;
>         }
>         return y;
> }
>
> Put it through cc -O3 -m32 -c -o sqrt64.o sqrt64.c and then objdump sqrt64.o
> and compare to that of your version.
>
>         David
>

Wow, thanks. This seems like a major change.

I did a quick run through unit tests for the sensor and the results
are way off. On the sensor I had to convert double calculations to
integer calculations and target was to get end result within 0.02 degC
(with previous approximate sqrt implementation) in sensor working
range. This now gets into 3 degC delta at least and some are way off.
It might be off because of some scaling on the other hand during the
equation (not exactly comparing sqrt implementations here).

I will need a bit more testing of this to see if it is replaceable.