Re: [PATCH v4 00/13] Introduce parity_odd() and refactor redundant parity code

H. Peter Anvin
2025-05-15T09:20:35Z

On 4/9/25 11:33, Yury Norov wrote:
>>>
>> I don't have a strong preference for the name, but if I had to guess
>> the return value from the function prototype, I would intuitively
>> expect an int to return "0 for even and 1 for odd," and a bool to
>> return "true for even, false for odd." I recall Jiri and Jacob shared
>> similar thoughts, which is why I felt adding _odd could provide better
>> clarity.
>
> I think they said they are convinced that parity should return 1 for
> odd because of folding and __builtin_parity() arguments.
>

And for bool, 0 == false, and 1 == true. In fact, the *definitions* for
false and true in C (but not C++) is:

<stdbool.h>:
typedef _Bool bool;
#define false 0
#define true 1

If someone wants to make more clear, it would be better to put "typedef
bool bit_t" in a common header, but that personally seems ridiculous to me.
>>>> type from u8 to u64 for broader applicability, and updates its
return
>>>> type from int to bool to make its usage and return semantics more
>>>> intuitive-returning true for odd parity and false for even parity. It
>>>> also adds __attribute_const__ to enable compiler optimizations.
>>>
>>> That's correct and nice, but can you support it with a bloat-o-meter's
>>> before/after and/or asm snippets? I also think it worth to be a separate
>>> patch, preferably the last patch in the series.
>>>
>> I quickly tested it with the x86 defconfig, and it appears that the
>> generated code doesn't change. I forgot who requested the addition
>> during the review process, but I initially thought it would either
>> improve the generated code or leave it unchanged without significantly
>> increasing the source code size.
>
> That's what I actually expected, but was shy to guess openly. :). It's
> hard to imagine how compiler may improve code generation in this case...
>
> This attribute is used when there's an asm block, or some non-trivial
> function call. In this case, the function is self-consistent and makes
> no calls. And you see, const annotation raises more questions than
> solves problems. Let's drop it.

Ah yes; one of the quirks about gcc asm is that an asm is implicitly
assumed "const" (with no memory operands) or "pure" (with memory
operands) unless declared volatile or given an explicit "memory" clobber.

So yes, the compiler can most definitely derive the constness from the
form of the function even in the variable case.

I would still like to see __builtin_parity() being used as an
architecture opt-in; it can, of course, also be unconditionally used in
the constant case.

So in the end one of these two become my preferred implementation, and I
really don't think it is very complicated:

#ifndef use_builtin_parity
#define use_builtin_parity(x) __builtin_constant_p(x)
#endif

static inline bool parity8(u8 val)
{
if (use_builtin_parity(val))
return __builtin_parity(val);
val ^= val >> 4;
return (0x6996 >> (val & 0xf)) & 1;
}

static inline bool parity16(u16 val)
{
if (use_builtin_parity(val))
return __builtin_parity(val);
return parity8(val ^ (val >> 8));
}

static inline bool parity32(u32 val)
{
if (use_builtin_parity(val))
return __builtin_parity(val);
return parity16(val ^ (val >> 16));
}

static inline bool parity64(u64 val)
{
if (use_builtin_parity(val))
return __builtin_parityll(val);
return parity32(val ^ (val >> 32));
}

This means that an architecture -- in particular, x86 -- can still ask
to use __builtin_parity*() directly. It means that architectures on
which __builtin_parity*() produces bad code should either complain to
the gcc/clang team and have it fixed, or we can add additional mechanism
for them to override the implementation at that time.

The alternative is to stop worrying about overengineering, and just do
it once and for all:

#ifndef parity8
static inline bool parity8(u8 val)
{
val ^= val >> 4;
return (0x6996 >> (val & 0xf)) & 1;
}
#endif

#ifndef parity16
static inline bool parity16(u16 val)
{
return parity8(val ^ (val >> 8));
}
#endif

#ifndef parity32
static inline bool parity32(u32 val)
{
return parity16(val ^ (val >> 16));
}
#endif

#ifndef parity64
static inline bool parity64(u64 val)
{
return parity32(val ^ (val >> 32));
}
#endif

In either case, instead of packing the cascade into one function, make
good use of it.

In the latter case, __builtin_constant_p() isn't necessary as it puts
the onus on the architecture to separate out const and non-const cases,
if it matters -- which it doesn't if the architecture simply wants to
use __builtin_parity:

#define parity8(x) ((bool) __builtin_parity((u8)(x)))
#define parity16(x) ((bool) __builtin_parity((u16)(x)))
#define parity32(x) ((bool) __builtin_parity((u32)(x)))
#define parity64(x) ((bool) __builtin_parityll((u64)(x)))

As stated before, I don't really see that the parity function itself
would be very suitable for a generic helper, but if it were to, then
using the "standard" macro construct for it would seem to be the better
option.

(And I would be very much in favor of not open-coding the helper
everywhere but to macroize it; effectively creating a C++ template
equivalent. It is out of scope for this project, though.)

-hpa