netdev - 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: <Z7ykvf1g03XDLXKc@eleanor-wkdl>
Date: Tue, 25 Feb 2025 00:56:29 +0800
From: Yu-Chun Lin <eleanor15x@...il.com>
To: David Laight <david.laight.linux@...il.com>
Cc: Jiri Slaby <jirislaby@...nel.org>, 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
Subject: Re: [PATCH 02/17] bitops: Add generic parity calculation for u64

On Mon, Feb 24, 2025 at 01:34:31PM +0000, David Laight wrote:
> 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.

Hi Jiri and David,

Unless we can be certain about the compiler's optimization behavior, we
prefer to follow an approach similar to hweight, distinguishing
implementations based on different bit sizes.

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

We will adopt this approach, as it is indeed more concise.

Thank you all for your feedback.

Best regards,

Yu-Chun Lin

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