Repository: nfrechette/acl (cpp)

Issue:
Enable popcount support for Windows ARM
`_mm_popcnt_u*` and `__builtin_popcount*` aren't supported by MSVC.
Find the correct header and intrinsic to use for that platform.


Discussion:
See this commit and comments for details: https://github.com/nfrechette/acl/commit/610c424dcf99005dc880726e0388af010ae4e9c9


Patch:
diff --git a/includes/acl/core/bit_manip_utils.h b/includes/acl/core/bit_manip_utils.h
--- a/includes/acl/core/bit_manip_utils.h
+++ b/includes/acl/core/bit_manip_utils.h
@@ -26,25 +26,20 @@
 
 #include "acl/core/compiler_utils.h"
 #include "acl/core/error.h"
+#include "acl/math/math.h"
 
 #include <cstdint>
 
 #if !defined(ACL_USE_POPCOUNT)
-	#if defined(ACL_NEON_INTRINSICS) && !defined(_MSC_VER)
-		// Enable pop-count type instructions on ARM NEON
-		#define ACL_USE_POPCOUNT
-	#elif defined(_DURANGO) || defined(_XBOX_ONE)
+	// TODO: Enable this for PlayStation 4 as well, what is the define and can we use it in public code?
+	#if defined(_DURANGO) || defined(_XBOX_ONE)
 		// Enable pop-count type instructions on Xbox One
 		#define ACL_USE_POPCOUNT
-	// TODO: Enable this for PlayStation 4 as well, what is the define and can we use it in public code?
-	// TODO: Enable this for Windows ARM as well, what is the include and intrinsic to use?
 	#endif
 #endif
 
 #if defined(ACL_USE_POPCOUNT)
-	#if defined(_MSC_VER)
-		#include <nmmintrin.h>
-	#endif
+	#include <nmmintrin.h>
 #endif
 
 #if defined(ACL_AVX_INTRINSICS)
@@ -61,10 +56,10 @@ namespace acl
 {
 	inline uint8_t count_set_bits(uint8_t value)
 	{
-#if defined(ACL_USE_POPCOUNT) && defined(_MSC_VER)
+#if defined(ACL_USE_POPCOUNT)
 		return (uint8_t)_mm_popcnt_u32(value);
-#elif defined(ACL_USE_POPCOUNT) && (defined(__GNUC__) || defined(__clang__))
-		return (uint8_t)__builtin_popcount(value);
+#elif defined(ACL_NEON_INTRINSICS)
+		return (uint8_t)vget_lane_u64(vcnt_u8(vcreate_u8(value)), 0);
 #else
 		value = value - ((value >> 1) & 0x55);
 		value = (value & 0x33) + ((value >> 2) & 0x33);
@@ -74,10 +69,10 @@ namespace acl
 
 	inline uint16_t count_set_bits(uint16_t value)
 	{
-#if defined(ACL_USE_POPCOUNT) && defined(_MSC_VER)
+#if defined(ACL_USE_POPCOUNT)
 		return (uint16_t)_mm_popcnt_u32(value);
-#elif defined(ACL_USE_POPCOUNT) && (defined(__GNUC__) || defined(__clang__))
-		return (uint16_t)__builtin_popcount(value);
+#elif defined(ACL_NEON_INTRINSICS)
+		return (uint16_t)vget_lane_u64(vpaddl_u8(vcnt_u8(vcreate_u8(value))), 0);
 #else
 		value = value - ((value >> 1) & 0x5555);
 		value = (value & 0x3333) + ((value >> 2) & 0x3333);
@@ -87,10 +82,10 @@ namespace acl
 
 	inline uint32_t count_set_bits(uint32_t value)
 	{
-#if defined(ACL_USE_POPCOUNT) && defined(_MSC_VER)
+#if defined(ACL_USE_POPCOUNT)
 		return _mm_popcnt_u32(value);
-#elif defined(ACL_USE_POPCOUNT) && (defined(__GNUC__) || defined(__clang__))
-		return __builtin_popcount(value);
+#elif defined(ACL_NEON_INTRINSICS)
+		return (uint32_t)vget_lane_u64(vpaddl_u16(vpaddl_u8(vcnt_u8(vcreate_u8(value)))), 0);
 #else
 		value = value - ((value >> 1) & 0x55555555);
 		value = (value & 0x33333333) + ((value >> 2) & 0x33333333);
@@ -100,10 +95,10 @@ namespace acl
 
 	inline uint64_t count_set_bits(uint64_t value)
 	{
-#if defined(ACL_USE_POPCOUNT) && defined(_MSC_VER)
+#if defined(ACL_USE_POPCOUNT)
 		return _mm_popcnt_u64(value);
-#elif defined(ACL_USE_POPCOUNT) && (defined(__GNUC__) || defined(__clang__))
-		return __builtin_popcountll(value);
+#elif defined(ACL_NEON_INTRINSICS)
+		return vget_lane_u64(vpaddl_u32(vpaddl_u16(vpaddl_u8(vcnt_u8(vcreate_u8(value))))), 0);
 #else
 		value = value - ((value >> 1) & 0x5555555555555555ull);
 		value = (value & 0x3333333333333333ull) + ((value >> 2) & 0x3333333333333333ull);
diff --git a/includes/acl/core/bitset.h b/includes/acl/core/bitset.h
--- a/includes/acl/core/bitset.h
+++ b/includes/acl/core/bitset.h
@@ -190,6 +190,8 @@ namespace acl
 	{
 		const uint32_t size = desc.get_size();
 
+		// TODO: Optimize for NEON by using the intrinsic directly and unrolling the loop to
+		// reduce the number of pairwise add instructions.
 		uint32_t num_set_bits = 0;
 		for (uint32_t offset = 0; offset < size; ++offset)
 			num_set_bits += count_set_bits(bitset[offset]);


Test patch:
diff --git a/tests/sources/core/test_bit_manip_utils.cpp b/tests/sources/core/test_bit_manip_utils.cpp
--- a/tests/sources/core/test_bit_manip_utils.cpp
+++ b/tests/sources/core/test_bit_manip_utils.cpp
@@ -26,8 +26,6 @@
 
 #include <acl/core/bit_manip_utils.h>
 
-//#include <cstring>
-
 using namespace acl;
 
 TEST_CASE("bit_manip_utils", "[core][utils]")
@@ -40,16 +38,19 @@ TEST_CASE("bit_manip_utils", "[core][utils]")
 	REQUIRE(count_set_bits(uint16_t(0x0000)) == 0);
 	REQUIRE(count_set_bits(uint16_t(0x0001)) == 1);
 	REQUIRE(count_set_bits(uint16_t(0x1000)) == 1);
+	REQUIRE(count_set_bits(uint16_t(0x1001)) == 2);
 	REQUIRE(count_set_bits(uint16_t(0xFFFF)) == 16);
 
 	REQUIRE(count_set_bits(uint32_t(0x00000000)) == 0);
 	REQUIRE(count_set_bits(uint32_t(0x00000001)) == 1);
 	REQUIRE(count_set_bits(uint32_t(0x10000000)) == 1);
+	REQUIRE(count_set_bits(uint32_t(0x10101001)) == 4);
 	REQUIRE(count_set_bits(uint32_t(0xFFFFFFFF)) == 32);
 
 	REQUIRE(count_set_bits(uint64_t(0x0000000000000000ull)) == 0);
 	REQUIRE(count_set_bits(uint64_t(0x0000000000000001ull)) == 1);
 	REQUIRE(count_set_bits(uint64_t(0x1000000000000000ull)) == 1);
+	REQUIRE(count_set_bits(uint64_t(0x1000100001010101ull)) == 6);
 	REQUIRE(count_set_bits(uint64_t(0xFFFFFFFFFFFFFFFFull)) == 64);
 
 	REQUIRE(rotate_bits_left(0x00000010, 0) == 0x00000010);