Skip to contentSkip to conversation

lib/bch.c: Use __builtin_parity() when available

PATCH New Uros Bizjak 1 participant 1 message Jan 29, 2025 Library code

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 lib/bch.c: Use __builtin_parity() when available

Compilers (GCC and clang) provide optimized __builtin_parity() function that returns the parity of X, i.e. the number of 1-bits in X modulo 2.

Use __builtin_parity() built-in function to optimize parity(). This improves generated code on x86_64 from:

	movl    %edi, %edx
	shrl    %edx
	xorl    %edi, %edx
	movl    %edx, %eax
	shrl    $2, %eax
	xorl    %edx, %eax
	andl    $286331153, %eax
	imull   $286331153, %eax, %eax
	shrl    $28, %eax
	andl    $1, %eax

to an optimized:

	movl    %edi, %ecx
	shrl    $16, %ecx
	xorl    %edi, %ecx
	xorl    %eax, %eax
	xorb    %ch, %cl
	setnp   %al

Please note SETNP instruction that exercises hardware parity calculation of x86 processors. When POPCNT instruction is available, the generated code gets optimized even further:

popcntl %edi, %eax
andl $1, %eax

Compile-tested only.

---
 lib/bch.c | 4 ++++
 1 file changed, 4 insertions(+)
lib/bch.c +4 -0
index 1c0cb07cdfeb..7a266c160839 100644
@@ -313,6 +313,9 @@ static inline int deg(unsigned int poly)
 
 static inline int parity(unsigned int x)
 {
+#if __has_builtin(__builtin_parity)
+	return __builtin_parity(x);
+#else
 	/*
 	 * public domain code snippet, lifted from
 	 * http://www-graphics.stanford.edu/~seander/bithacks.html
@@ -321,6 +324,7 @@ static inline int parity(unsigned int x)
 	x ^= x >> 2;
 	x = (x & 0x11111111U) * 0x11111111U;
 	return (x >> 28) & 1;
+#endif
 }
 
 /* Galois field basic operations: multiply, divide, inverse, etc. */
Signature · 1 line
2.42.0