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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <949B0809-3BB9-4E18-8FA1-A12BD47F2843@zytor.com>
Date: Tue, 25 Feb 2025 07:21:38 -0800
From: "H. Peter Anvin" <hpa@...or.com>
To: David Laight <david.laight.linux@...il.com>,
        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, 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 February 24, 2025 5:34:31 AM PST, David Laight <david.laight.linux@...il.com> 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.
>
>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  
>> 
>> 
>

Sure you can; you do need an 8- and a 16-bit arch implementation though (the 16 bit one being xor %rh,%rl)