[Midnightbsd-cvs] src [7516] trunk/sys/sys/types.h: add bitcount.

[laffer1 at midnightbsd.org]

Revision: 7516
          http://svnweb.midnightbsd.org/src/?rev=7516
Author:   laffer1
Date:     2016-04-12 18:41:47 -0400 (Tue, 12 Apr 2016)
Log Message:
-----------
add bitcount.

Modified Paths:
--------------
    trunk/sys/sys/types.h

Modified: trunk/sys/sys/types.h
===================================================================
--- trunk/sys/sys/types.h	2016-04-09 21:57:45 UTC (rev 7515)
+++ trunk/sys/sys/types.h	2016-04-12 22:41:47 UTC (rev 7516)
@@ -283,7 +283,69 @@
 
 #include <sys/select.h>
 
+#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
 /*
+ * 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
+static __inline __uint64_t
+__bitcount64(__uint64_t _x)
+{
+
+	return (__bitcount32(_x >> 32) + __bitcount32(_x));
+}
+
+#define	__bitcountl(x)	__bitcount32((unsigned long)(x))
+#endif
+#define	__bitcount(x)	__bitcount32((unsigned int)(x))
+#endif
+
+/*
  * minor() gives a cookie instead of an index since we don't want to
  * change the meanings of bits 0-15 or waste time and space shifting
  * bits 16-31 for devices that don't use them.