linux-kernel - Re: [PATCH 02/17] bitops: Add generic parity calculation for u64

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: <20250224133431.2c38213f@pumpkin>
Date: Mon, 24 Feb 2025 13:34:31 +0000
From: David Laight <david.laight.linux@...il.com>
To: Jiri Slaby <jirislaby@...nel.org>
Cc: Kuan-Wei Chiu <visitorckw@...il.com>, tglx@...utronix.de,
 mingo@...hat.com, bp@...en8.de, dave.hansen@...ux.intel.com,
 x86@...nel.org, jk@...abs.org, joel@....id.au, eajames@...ux.ibm.com,
 andrzej.hajda@...el.com, neil.armstrong@...aro.org, rfoss@...nel.org,
 maarten.lankhorst@...ux.intel.com, mripard@...nel.org, tzimmermann@...e.de,
 airlied@...il.com, simona@...ll.ch, dmitry.torokhov@...il.com,
 mchehab@...nel.org, awalls@...metrocast.net, hverkuil@...all.nl,
 miquel.raynal@...tlin.com, richard@....at, vigneshr@...com,
 louis.peens@...igine.com, andrew+netdev@...n.ch, davem@...emloft.net,
 edumazet@...gle.com, pabeni@...hat.com,
 parthiban.veerasooran@...rochip.com, arend.vanspriel@...adcom.com,
 johannes@...solutions.net, gregkh@...uxfoundation.org,
 yury.norov@...il.com, akpm@...ux-foundation.org, hpa@...or.com,
 alistair@...ple.id.au, linux@...musvillemoes.dk,
 Laurent.pinchart@...asonboard.com, jonas@...boo.se,
 jernej.skrabec@...il.com, kuba@...nel.org, linux-kernel@...r.kernel.org,
 linux-fsi@...ts.ozlabs.org, dri-devel@...ts.freedesktop.org,
 linux-input@...r.kernel.org, linux-media@...r.kernel.org,
 linux-mtd@...ts.infradead.org, oss-drivers@...igine.com,
 netdev@...r.kernel.org, linux-wireless@...r.kernel.org,
 brcm80211@...ts.linux.dev, brcm80211-dev-list.pdl@...adcom.com,
 linux-serial@...r.kernel.org, bpf@...r.kernel.org, jserv@...s.ncku.edu.tw,
 Yu-Chun Lin <eleanor15x@...il.com>
Subject: Re: [PATCH 02/17] bitops: Add generic parity calculation for u64

On Mon, 24 Feb 2025 08:09:43 +0100
Jiri Slaby <jirislaby@...nel.org> wrote:

> On 23. 02. 25, 17:42, Kuan-Wei Chiu wrote:
> > Several parts of the kernel open-code parity calculations using
> > different methods. Add a generic parity64() helper implemented with the
> > same efficient approach as parity8().
> > 
> > Co-developed-by: Yu-Chun Lin <eleanor15x@...il.com>
> > Signed-off-by: Yu-Chun Lin <eleanor15x@...il.com>
> > Signed-off-by: Kuan-Wei Chiu <visitorckw@...il.com>
> > ---
> >   include/linux/bitops.h | 22 ++++++++++++++++++++++
> >   1 file changed, 22 insertions(+)
> > 
> > diff --git a/include/linux/bitops.h b/include/linux/bitops.h
> > index fb13dedad7aa..67677057f5e2 100644
> > --- a/include/linux/bitops.h
> > +++ b/include/linux/bitops.h
> > @@ -281,6 +281,28 @@ static inline int parity32(u32 val)
> >   	return (0x6996 >> (val & 0xf)) & 1;
> >   }
> >   
> > +/**
> > + * parity64 - get the parity of an u64 value
> > + * @value: the value to be examined
> > + *
> > + * Determine the parity of the u64 argument.
> > + *
> > + * Returns:
> > + * 0 for even parity, 1 for odd parity
> > + */
> > +static inline int parity64(u64 val)
> > +{
> > +	/*
> > +	 * One explanation of this algorithm:
> > +	 * https://funloop.org/codex/problem/parity/README.html
> > +	 */
> > +	val ^= val >> 32;  
> 
> Do we need all these implementations? Can't we simply use parity64() for 
> any 8, 16 and 32-bit values too? I.e. have one parity().

I'm not sure you can guarantee that the compiler will optimise away
the unnecessary operations.

But:
static inline int parity64(u64 val)
{
	return parity32(val ^ (val >> 32))
}

should be ok.
It will also work on x86-32 where parity32() can just check the parity flag.
Although you are unlikely to manage to use the the PF the xor sets.

	David

> 
> > +	val ^= val >> 16;
> > +	val ^= val >> 8;
> > +	val ^= val >> 4;
> > +	return (0x6996 >> (val & 0xf)) & 1;
> > +}
> > +
> >   /**
> >    * __ffs64 - find first set bit in a 64 bit word
> >    * @word: The 64 bit word  
> 
>