lkml.org 
[lkml]   [2017]   [Oct]   [19]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    Date
    SubjectRe: [PATCH] lib/int_sqrt.c: optimize for small argument values
    On Thu, Oct 19, 2017 at 1:31 PM, Michael Davidson <md@google.com> wrote:
    > int_sqrt() currently takes approximately constant time
    > regardless of the value of the argument. By using the
    > magnitude of the operand to set the initial conditions
    > for the calculation the cost becomes proportional to
    > log2 of the argument with the worst case behavior not
    > being measurably slower than it currently is.

    Maybe a stupid question, but is this function ultimately used by any
    crypto that expects it to be constant-time for safety?

    Also, is there a specific workload that is meaningfully sped up by this change?

    -Kees

    >
    > Signed-off-by: Michael Davidson <md@google.com>
    > ---
    > lib/int_sqrt.c | 2 +-
    > 1 file changed, 1 insertion(+), 1 deletion(-)
    >
    > diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c
    > index 1ef4cc344977..8394b0dcecd4 100644
    > --- a/lib/int_sqrt.c
    > +++ b/lib/int_sqrt.c
    > @@ -21,7 +21,7 @@ unsigned long int_sqrt(unsigned long x)
    > if (x <= 1)
    > return x;
    >
    > - m = 1UL << (BITS_PER_LONG - 2);
    > + m = 1UL << (__fls(x) & ~1UL);
    > while (m != 0) {
    > b = y + m;
    > y >>= 1;
    > --
    > 2.15.0.rc1.287.g2b38de12cc-goog
    >



    --
    Kees Cook
    Pixel Security

    \
     
     \ /
      Last update: 2017-10-22 17:29    [W:3.809 / U:0.084 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site