[PATCH] For RTEMS-LIBBSD support, add bitcount routines

[PATCH] For RTEMS-LIBBSD support, add bitcount routines

[Kevin Kirspel]

---
 newlib/libc/include/sys/types.h | 66 ++++++++++++++++++++++++++++++++++++++---
 1 file changed, 62 insertions(+), 4 deletions(-)

diff --git a/newlib/libc/include/sys/types.h b/newlib/libc/include/sys/types.h
index 65ff520..83f891e 100644
--- a/newlib/libc/include/sys/types.h
+++ b/newlib/libc/include/sys/types.h
@@ -53,6 +53,64 @@ typedef	__int64_t	quad_t;
 typedef	quad_t *	qaddr_t;
 #endif

+#ifdef __POPCNT__
+#define __bitcount64(x) __builtin_popcountll((__uint64_t)(x))
+#define __bitcount32(x) __builtin_popcount((__uint32_t)(x))
+#define __bitcount16(x) __builtin_popcount((__uint16_t)(x))
+#define __bitcountl(x)  __builtin_popcountl((unsigned long)(x))
+#define __bitcount(x)   __builtin_popcount((unsigned int)(x))
+#else /* __POPCNT__ */
+/*
+ * Population count algorithm using SWAR approach
+ * - "SIMD Within A Register".
+ */
+static __inline __uint16_t
+__bitcount16(__uint16_t _x)
+{
+	_x = (_x & 0x5555) + ((_x & 0xaaaa) >> 1);
+	_x = (_x & 0x3333) + ((_x & 0xcccc) >> 2);
+	_x = (_x + (_x >> 4)) & 0x0f0f;
+	_x = (_x + (_x >> 8)) & 0x00ff;
+	return (_x);
+}
+
+static __inline __uint32_t
+__bitcount32(__uint32_t _x)
+{
+	_x = (_x & 0x55555555) + ((_x & 0xaaaaaaaa) >> 1);
+	_x = (_x & 0x33333333) + ((_x & 0xcccccccc) >> 2);
+	_x = (_x + (_x >> 4)) & 0x0f0f0f0f;
+	_x = (_x + (_x >> 8));
+	_x = (_x + (_x >> 16)) & 0x000000ff;
+	return (_x);
+}
+
+#ifdef __LP64__
+static __inline __uint64_t
+__bitcount64(__uint64_t _x)
+{
+	_x = (_x & 0x5555555555555555) + ((_x & 0xaaaaaaaaaaaaaaaa) >> 1);
+	_x = (_x & 0x3333333333333333) + ((_x & 0xcccccccccccccccc) >> 2);
+	_x = (_x + (_x >> 4)) & 0x0f0f0f0f0f0f0f0f;
+	_x = (_x + (_x >> 8));
+	_x = (_x + (_x >> 16));
+	_x = (_x + (_x >> 32)) & 0x000000ff;
+	return (_x);
+}
+
+#define __bitcountl(x)  __bitcount64((unsigned long)(x))
+#else /* __LP64__ */
+static __inline __uint64_t
+__bitcount64(__uint64_t _x)
+{
+	return (__bitcount32(_x >> 32) + __bitcount32(_x));
+}
+
+#define __bitcountl(x)  __bitcount32((unsigned long)(x))
+#endif /* __LP64__ */
+#define __bitcount(x)   __bitcount32((unsigned int)(x))
+#endif /* __POPCNT__ */
+
 #endif /* __rtems__ || __XMK__ */

 #ifndef __need_inttypes
--
1.9.1

Re: [PATCH] For RTEMS-LIBBSD support, add bitcount routines

[Craig Howland]

On 05/16/2017 02:23 PM, Kevin Kirspel wrote:
> ---
>   newlib/libc/include/sys/types.h | 66 ++++++++++++++++++++++++++++++++++++++---
>   1 file changed, 62 insertions(+), 4 deletions(-)
>
> diff --git a/newlib/libc/include/sys/types.h b/newlib/libc/include/sys/types.h
> index 65ff520..83f891e 100644
> ...
> +#ifdef __LP64__
> +static __inline __uint64_t
> +__bitcount64(__uint64_t _x)
> +{
> ...
> +}
> +
> +#define __bitcountl(x)  __bitcount64((unsigned long)(x))
> +#else /* __LP64__ */
> +static __inline __uint64_t
> +__bitcount64(__uint64_t _x)
> +{
> +	return (__bitcount32(_x >> 32) + __bitcount32(_x));
> +}
> +
> +#define __bitcountl(x)  __bitcount32((unsigned long)(x))
> +#endif /* __LP64__ */
> +#define __bitcount(x)   __bitcount32((unsigned int)(x))
> +#endif /* __POPCNT__ */
> +
Depending only upon LP64 is not sufficient in general to get all the sizes 
right.  (ARM Cortex A53, for example, has 64-bit int, too--ILP64.  So A53 would 
probably end up with two problems, bitcountl and bitcount.)

One possible solution would be something similar to this size-agnostic endian 
function I use:

#define __bswap(x) \
     __builtin_choose_expr( \
         sizeof(x) == sizeof(char), \
         (x), \
         __builtin_choose_expr( \
             sizeof(x) == sizeof(short), \
             __bswap16(x), \
             __builtin_choose_expr( \
                 sizeof(x) == sizeof(int), \
                 __bswap32(x), \
                 __builtin_choose_expr( \
                     sizeof(x) == sizeof(long long), \
                     __bswap64(x), \
                     /* The void expression results in a compile-time error \
                     when assigning the result to something. */ \
                     (void) 0 \
                     ) \
                 ) \
             ) \
         )


One problem with it is that it is GCC-specific with the use of 
__builtin_choose_expr(), but that can be avoided, too, by using a contruct 
similar to that for fpclassify in math.h (use sizeof(int)==4 and sizeof(int)==8 
for the tests, etc.)--the version in the else when the GNUC_PREREQ(4,4) check fails.
Craig

Re: [PATCH] For RTEMS-LIBBSD support, add bitcount routines

[Sebastian Huber]

If we want to make this RTEMS-specific, then it should be in:

newlib/libc/sys/rtems/include/machine/types.h

-- 
Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone   : +49 89 189 47 41-16
Fax     : +49 89 189 47 41-09
E-Mail  : sebastian.huber@embedded-brains.de
PGP     : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.

Re: [PATCH] For RTEMS-LIBBSD support, add bitcount routines

[Sebastian Huber]

On 16/05/17 21:04, Craig Howland wrote:
> On 05/16/2017 02:23 PM, Kevin Kirspel wrote:
>> ---
>>   newlib/libc/include/sys/types.h | 66 
>> ++++++++++++++++++++++++++++++++++++++---
>>   1 file changed, 62 insertions(+), 4 deletions(-)
>>
>> diff --git a/newlib/libc/include/sys/types.h 
>> b/newlib/libc/include/sys/types.h
>> index 65ff520..83f891e 100644
>> ...
>> +#ifdef __LP64__
>> +static __inline __uint64_t
>> +__bitcount64(__uint64_t _x)
>> +{
>> ...
>> +}
>> +
>> +#define __bitcountl(x)  __bitcount64((unsigned long)(x))
>> +#else /* __LP64__ */
>> +static __inline __uint64_t
>> +__bitcount64(__uint64_t _x)
>> +{
>> +    return (__bitcount32(_x >> 32) + __bitcount32(_x));
>> +}
>> +
>> +#define __bitcountl(x)  __bitcount32((unsigned long)(x))
>> +#endif /* __LP64__ */
>> +#define __bitcount(x)   __bitcount32((unsigned int)(x))
>> +#endif /* __POPCNT__ */
>> +
> Depending only upon LP64 is not sufficient in general to get all the 
> sizes right.  (ARM Cortex A53, for example, has 64-bit int, 
> too--ILP64.  So A53 would probably end up with two problems, bitcountl 
> and bitcount.) 

RTEMS doesn't support an __ILP64__ ABI at the moment, so it should be 
sufficient. However, maybe we should use the __SIZEOF_INT__ and 
__SIZEOF_LONG__ builtin defines instead of __LP64.

-- 
Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone   : +49 89 189 47 41-16
Fax     : +49 89 189 47 41-09
E-Mail  : sebastian.huber@embedded-brains.de
PGP     : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.