linux-kernel - Re: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}

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]

Message-ID: <CA+55aFyvBTDh_DkXs6Z6zFmjyYxvWaAEm9-rJDXhvPx8CpDiKA@mail.gmail.com>
Date:	Tue, 24 Apr 2012 12:37:53 -0700
From:	Linus Torvalds <torvalds@...ux-foundation.org>
To:	Peter Zijlstra <a.p.zijlstra@...llo.nl>
Cc:	linux-kernel@...r.kernel.org, linux-arch@...r.kernel.org,
	Andrew Morton <akpm@...ux-foundation.org>,
	Juri Lelli <juri.lelli@...il.com>,
	Ingo Molnar <mingo@...nel.org>,
	Thomas Gleixner <tglx@...utronix.de>
Subject: Re: [RFC][PATCH 2/3] math128: Introduce {mult,add,cmp}_u128

On Tue, Apr 24, 2012 at 9:10 AM, Peter Zijlstra <a.p.zijlstra@...llo.nl> wrote:
> Grow rudimentary u128 support without relying on gcc/libgcc.
>
> +#ifndef add_u128
> +static inline u128 add_u128(u128 a, u128 b)
> +{
> +       u128 res;
> +
> +       res.hi = a.hi + b.hi;
> +       res.lo = a.lo + b.lo;
> +
> +       if (res.lo < a.lo || res.lo < b.lo)
> +               res.hi++;

This is wrong. Or at least stupid.

Just do one of the comparisons, not both. If overflow occurs, the
result will be smaller than *either* of the added numbers, so
comparing both is just silly and confused.

So just pick one.

Also, it might be worth looking at code generation, to see if it's
better to just do

   a.hi += b.hi;
   a.low += b.low;
   if (a.low < b.low)
      a.hi++;
   return a;

because that might make it clear that there are fewer actual values
live at any particular time. But gcc may not care. Try it.

Also, for the multiply, please make sure gcc knows to do a "32x32->64"
multiplication, rather than thinking it needs to do full 64x64
multiplies..

I'm not sure gcc understands that as you wrote it. You are probably
better off actually using 32-bit values, and then an explicit cast, ie

  u32 a32_0 = .. low 32 bits of a ..
  u32 b32_0 = .. low 32 bits of b ..
  u64 res64_0 = (u64) a32_0 * (u64) b32_0;

but if gcc understands it from the shifts and masks, I guess it doesn't matter.

        Linus
--
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/