From 86a478032ba93f30adbc0ce96eecd3420fdf7ed1 Mon Sep 17 00:00:00 2001 From: Alan Coopersmith Date: Sat, 2 Mar 2024 12:01:54 -0800 Subject: xcb_popcount: Use __builtin_popcount if compiler supports it If the compiler knows of a better implementation for counting the number of bits set in a word for the target CPU, let it use that, instead of the classic algorithm optimized for PDP-6. Signed-off-by: Alan Coopersmith --- src/xcb_util.c | 13 +++++++++++++ 1 file changed, 13 insertions(+) diff --git a/src/xcb_util.c b/src/xcb_util.c index eb21653..5124d14 100644 --- a/src/xcb_util.c +++ b/src/xcb_util.c @@ -62,12 +62,25 @@ #include +#ifndef __has_builtin +# define __has_builtin(x) 0 +#endif + int xcb_popcount(uint32_t mask) { +#if __has_builtin(__builtin_popcount) + return __builtin_popcount(mask); +#else + /* + * Count the number of bits set to 1 in a 32-bit word. + * Algorithm from MIT AI Lab Memo 239: "HAKMEM", ITEM 169. + * https://dspace.mit.edu/handle/1721.1/6086 + */ uint32_t y; y = (mask >> 1) & 033333333333; y = mask - y - ((y >> 1) & 033333333333); return ((y + (y >> 3)) & 030707070707) % 077; +#endif } int xcb_sumof(uint8_t *list, int len) -- cgit v1.2.3