<NME> bit_manip_utils.h
<BEF> #pragma once

////////////////////////////////////////////////////////////////////////////////
// The MIT License (MIT)
//
// Copyright (c) 2018 Nicholas Frechette & Animation Compression Library contributors
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
////////////////////////////////////////////////////////////////////////////////

#include "acl/version.h"
#include "acl/core/impl/compiler_utils.h"

#include <cstdint>

#if defined(ACL_USE_POPCOUNT)
	#if defined(_MSC_VER)
		#include <nmmintrin.h>

#if !defined(ACL_BMI_INTRINSICS) && !defined(RTM_NO_INTRINSICS)
	// 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 BMI type instructions on Xbox One
		#define ACL_BMI_INTRINSICS
	#elif defined(RTM_AVX_INTRINSICS) && !(defined(_MSC_VER) && defined(__clang__))
		// Enable BMI when AVX is enabled except with clang under Windows
		// Note: It seems that the Clang toolchain with MSVC enables BMI only with AVX2 unlike
		// MSVC which enables it with AVX
		#define ACL_BMI_INTRINSICS
	#endif
#endif

#if defined(ACL_BMI_INTRINSICS)
	#include <ammintrin.h>		// MSVC uses this header for _andn_u32 BMI intrinsic
	#include <immintrin.h>		// Intel documentation says _andn_u32 and others are here
#endif

ACL_IMPL_FILE_PRAGMA_PUSH

#if defined(RTM_COMPILER_MSVC)
	#pragma warning(push)
	// warning C4146: unary minus operator applied to unsigned type, result still unsigned
	// This is fine because we use bitwise arithmetic and rely on the fact that unsigned
	// integers use twos complement.
	#pragma warning(disable : 4146)
#endif

namespace acl
{
	ACL_IMPL_VERSION_NAMESPACE_BEGIN

	//////////////////////////////////////////////////////////////////////////
	// Counts the number of '1' bits (aka: pop-count)
	inline uint8_t count_set_bits(uint8_t value)
	{
#if defined(ACL_USE_POPCOUNT)
		return (uint8_t)_mm_popcnt_u32(value);
#elif defined(RTM_NEON_INTRINSICS)
		return (uint8_t)vget_lane_u8(vcnt_u8(vcreate_u8(value)), 0);
#else
		value = value - ((value >> 1) & 0x55);
		value = (value & 0x33) + ((value >> 2) & 0x33);
		return ((value + (value >> 4)) & 0x0F);
#endif
	}

	//////////////////////////////////////////////////////////////////////////
	// Counts the number of '1' bits (aka: pop-count)
	inline uint16_t count_set_bits(uint16_t value)
	{
#if defined(ACL_USE_POPCOUNT)
		return (uint16_t)_mm_popcnt_u32(value);
#elif defined(RTM_NEON_INTRINSICS)
		return (uint16_t)vget_lane_u16(vpaddl_u8(vcnt_u8(vcreate_u8(value))), 0);
#else
		value = value - ((value >> 1) & 0x5555);
		value = (value & 0x3333) + ((value >> 2) & 0x3333);
		return uint16_t(((value + (value >> 4)) & 0x0F0F) * 0x0101) >> 8;
#endif
	}

	//////////////////////////////////////////////////////////////////////////
	// Counts the number of '1' bits (aka: pop-count)
	inline uint32_t count_set_bits(uint32_t value)
	{
#if defined(ACL_USE_POPCOUNT)
		return _mm_popcnt_u32(value);
#elif defined(RTM_NEON_INTRINSICS)
		return (uint32_t)vget_lane_u32(vpaddl_u16(vpaddl_u8(vcnt_u8(vcreate_u8(value)))), 0);
#else
		value = value - ((value >> 1) & 0x55555555);
		value = (value & 0x33333333) + ((value >> 2) & 0x33333333);
		return (((value + (value >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
#endif
	}

	//////////////////////////////////////////////////////////////////////////
	// Counts the number of '1' bits (aka: pop-count)
	inline uint64_t count_set_bits(uint64_t value)
	{
#if defined(ACL_USE_POPCOUNT)
		return _mm_popcnt_u64(value);
#elif defined(RTM_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);
		return (((value + (value >> 4)) & 0x0F0F0F0F0F0F0F0FULL) * 0x0101010101010101ULL) >> 56;
#endif
	}

	//////////////////////////////////////////////////////////////////////////
	// Starting at the MSB, counts the number of leading zeros
	inline uint32_t count_leading_zeros(uint32_t value)
	{
#if defined(ACL_USE_POPCOUNT)
		return _lzcnt_u32(value);
#elif defined(RTM_COMPILER_MSVC)
		unsigned long first_set_bit_index;
		return _BitScanReverse(&first_set_bit_index, value) ? (31 - first_set_bit_index) : 32;
#elif defined(RTM_COMPILER_GCC) || defined(RTM_COMPILER_CLANG)
		return value != 0 ? __builtin_clz(value) : 32;
#else
		value = value | (value >> 1);
		value = value | (value >> 2);
		value = value | (value >> 4);
		value = value | (value >> 8);
		value = value | (value >> 16);
		return count_set_bits(~value);
#endif
	}

	//////////////////////////////////////////////////////////////////////////
	// Starting at the LSB, counts the number of trailing zeros
	inline uint32_t count_trailing_zeros(uint32_t value)
	{
#if defined(ACL_BMI_INTRINSICS)
		return _tzcnt_u32(value);
#elif defined(RTM_COMPILER_MSVC)
		unsigned long first_set_bit_index;
		return _BitScanForward(&first_set_bit_index, value) ? first_set_bit_index : 32;
#elif defined(RTM_COMPILER_GCC) || defined(RTM_COMPILER_CLANG)
		return value != 0 ? __builtin_ctz(value) : 32;
#else
		return value != 0 ? (31 - count_leading_zeros(value & -value)) : 32;
#endif
	}

	//////////////////////////////////////////////////////////////////////////
	// Rotate the bits left by some amount
	inline uint32_t rotate_bits_left(uint32_t value, int32_t num_bits)
	{
		ACL_ASSERT(num_bits >= 0, "Attempting to rotate by negative bits");
		ACL_ASSERT(num_bits < 32, "Attempting to rotate by too many bits");
		const uint32_t mask = 32 - 1;
		num_bits &= mask;
		return (value << num_bits) | (value >> ((-num_bits) & mask));
	}

	//////////////////////////////////////////////////////////////////////////
	// Perform: ~not_value & and_value
	inline uint32_t and_not(uint32_t not_value, uint32_t and_value)
	{
#if defined(ACL_BMI_INTRINSICS)
		// Use BMI
#if defined(RTM_COMPILER_GCC) && !defined(_andn_u32)
		return __andn_u32(not_value, and_value);	// GCC doesn't define the right intrinsic symbol
#else
		return _andn_u32(not_value, and_value);
#endif
#else
		return ~not_value & and_value;
#endif
	}

	ACL_IMPL_VERSION_NAMESPACE_END
}

#if defined(RTM_COMPILER_MSVC)
	#pragma warning(pop)
#endif

ACL_IMPL_FILE_PRAGMA_POP

<MSG> perf(core): enable pop-count type instructions on ARM and Xbox One

<DFF> @@ -29,6 +29,17 @@
 
 #include <cstdint>
 
+#if !defined(ACL_USE_POPCOUNT)
+	#if defined(ACL_NEON_INTRINSICS)
+		// Enable pop-count type instructions on ARM NEON
+		#define ACL_USE_POPCOUNT
+	#elif 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?
+	#endif
+#endif
+
 #if defined(ACL_USE_POPCOUNT)
 	#if defined(_MSC_VER)
 		#include <nmmintrin.h>

{'commit': 'diff --git a/includes/acl/core/bit_manip_utils.h b/includes/acl/core/bit_manip_utils.h\nindex 304940e7..45747c01 100644\n--- a/includes/acl/core/bit_manip_utils.h\n+++ b/includes/acl/core/bit_manip_utils.h\n@@ -29,6 +29,17 @@\n \n #include <cstdint>\n \n+#if !defined(ACL_USE_POPCOUNT)\n+\t#if defined(ACL_NEON_INTRINSICS)\n+\t\t// Enable pop-count type instructions on ARM NEON\n+\t\t#define ACL_USE_POPCOUNT\n+\t#elif defined(_DURANGO) || defined(_XBOX_ONE)\n+\t\t// Enable pop-count type instructions on Xbox One\n+\t\t#define ACL_USE_POPCOUNT\n+\t// TODO: Enable this for PlayStation 4 as well, what is the define and can we use it in public code?\n+\t#endif\n+#endif\n+\n #if defined(ACL_USE_POPCOUNT)\n \t#if defined(_MSC_VER)\n \t\t#include <nmmintrin.h>\n', 'commit_subject': 'perf(core): enable pop-count type instructions on ARM and Xbox One', 'repo_name': 'nfrechette/acl', 'committer': {'name': 'Nicholas Frechette', 'email': '4afa1ee64a5cb1edca81e75e933c58ad9445b064@gmail.com', 'time_sec': '1557870575', 'tz_offset': '-240', 'date': {'seconds': '1557870575'}}, 'commit_tree': 'c1458d084a8d3ca5a48dc42a5c946ac23d36608a', 'commit_message': 'perf(core): enable pop-count type instructions on ARM and Xbox One\n', 'language_name': 'Python', 'license': 'mit', 'hunks': '@@ -29,6 +29,17 @@\n \n #include <cstdint>\n \n+#if !defined(ACL_USE_POPCOUNT)\n+\t#if defined(ACL_NEON_INTRINSICS)\n+\t\t// Enable pop-count type instructions on ARM NEON\n+\t\t#define ACL_USE_POPCOUNT\n+\t#elif defined(_DURANGO) || defined(_XBOX_ONE)\n+\t\t// Enable pop-count type instructions on Xbox One\n+\t\t#define ACL_USE_POPCOUNT\n+\t// TODO: Enable this for PlayStation 4 as well, what is the define and can we use it in public code?\n+\t#endif\n+#endif\n+\n #if defined(ACL_USE_POPCOUNT)\n \t#if defined(_MSC_VER)\n \t\t#include <nmmintrin.h>\n', 'addition_count': 11, 'deletion_count': 0, 'src_file': 'a/includes/acl/core/bit_manip_utils.h', 'tgt_file': 'b/includes/acl/core/bit_manip_utils.h', 'file_extension': '.h', 'before_file': '#pragma once\n\n////////////////////////////////////////////////////////////////////////////////\n// The MIT License (MIT)\n//\n// Copyright (c) 2018 Nicholas Frechette & Animation Compression Library contributors\n//\n// Permission is hereby granted, free of charge, to any person obtaining a copy\n// of this software and associated documentation files (the "Software"), to deal\n// in the Software without restriction, including without limitation the rights\n// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\n// copies of the Software, and to permit persons to whom the Software is\n// furnished to do so, subject to the following conditions:\n//\n// The above copyright notice and this permission notice shall be included in all\n// copies or substantial portions of the Software.\n//\n// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\n// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\n// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\n// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\n// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\n// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\n// SOFTWARE.\n////////////////////////////////////////////////////////////////////////////////\n\n#include "acl/version.h"\n#include "acl/core/impl/compiler_utils.h"\n\n#include <cstdint>\n\n#if defined(ACL_USE_POPCOUNT)\n\t#if defined(_MSC_VER)\n\t\t#include <nmmintrin.h>\n\n#if !defined(ACL_BMI_INTRINSICS) && !defined(RTM_NO_INTRINSICS)\n\t// TODO: Enable this for PlayStation 4 as well, what is the define and can we use it in public code?\n\t#if defined(_DURANGO) || defined(_XBOX_ONE)\n\t\t// Enable BMI type instructions on Xbox One\n\t\t#define ACL_BMI_INTRINSICS\n\t#elif defined(RTM_AVX_INTRINSICS) && !(defined(_MSC_VER) && defined(__clang__))\n\t\t// Enable BMI when AVX is enabled except with clang under Windows\n\t\t// Note: It seems that the Clang toolchain with MSVC enables BMI only with AVX2 unlike\n\t\t// MSVC which enables it with AVX\n\t\t#define ACL_BMI_INTRINSICS\n\t#endif\n#endif\n\n#if defined(ACL_BMI_INTRINSICS)\n\t#include <ammintrin.h>\t\t// MSVC uses this header for _andn_u32 BMI intrinsic\n\t#include <immintrin.h>\t\t// Intel documentation says _andn_u32 and others are here\n#endif\n\nACL_IMPL_FILE_PRAGMA_PUSH\n\n#if defined(RTM_COMPILER_MSVC)\n\t#pragma warning(push)\n\t// warning C4146: unary minus operator applied to unsigned type, result still unsigned\n\t// This is fine because we use bitwise arithmetic and rely on the fact that unsigned\n\t// integers use twos complement.\n\t#pragma warning(disable : 4146)\n#endif\n\nnamespace acl\n{\n\tACL_IMPL_VERSION_NAMESPACE_BEGIN\n\n\t//////////////////////////////////////////////////////////////////////////\n\t// Counts the number of \'1\' bits (aka: pop-count)\n\tinline uint8_t count_set_bits(uint8_t value)\n\t{\n#if defined(ACL_USE_POPCOUNT)\n\t\treturn (uint8_t)_mm_popcnt_u32(value);\n#elif defined(RTM_NEON_INTRINSICS)\n\t\treturn (uint8_t)vget_lane_u8(vcnt_u8(vcreate_u8(value)), 0);\n#else\n\t\tvalue = value - ((value >> 1) & 0x55);\n\t\tvalue = (value & 0x33) + ((value >> 2) & 0x33);\n\t\treturn ((value + (value >> 4)) & 0x0F);\n#endif\n\t}\n\n\t//////////////////////////////////////////////////////////////////////////\n\t// Counts the number of \'1\' bits (aka: pop-count)\n\tinline uint16_t count_set_bits(uint16_t value)\n\t{\n#if defined(ACL_USE_POPCOUNT)\n\t\treturn (uint16_t)_mm_popcnt_u32(value);\n#elif defined(RTM_NEON_INTRINSICS)\n\t\treturn (uint16_t)vget_lane_u16(vpaddl_u8(vcnt_u8(vcreate_u8(value))), 0);\n#else\n\t\tvalue = value - ((value >> 1) & 0x5555);\n\t\tvalue = (value & 0x3333) + ((value >> 2) & 0x3333);\n\t\treturn uint16_t(((value + (value >> 4)) & 0x0F0F) * 0x0101) >> 8;\n#endif\n\t}\n\n\t//////////////////////////////////////////////////////////////////////////\n\t// Counts the number of \'1\' bits (aka: pop-count)\n\tinline uint32_t count_set_bits(uint32_t value)\n\t{\n#if defined(ACL_USE_POPCOUNT)\n\t\treturn _mm_popcnt_u32(value);\n#elif defined(RTM_NEON_INTRINSICS)\n\t\treturn (uint32_t)vget_lane_u32(vpaddl_u16(vpaddl_u8(vcnt_u8(vcreate_u8(value)))), 0);\n#else\n\t\tvalue = value - ((value >> 1) & 0x55555555);\n\t\tvalue = (value & 0x33333333) + ((value >> 2) & 0x33333333);\n\t\treturn (((value + (value >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;\n#endif\n\t}\n\n\t//////////////////////////////////////////////////////////////////////////\n\t// Counts the number of \'1\' bits (aka: pop-count)\n\tinline uint64_t count_set_bits(uint64_t value)\n\t{\n#if defined(ACL_USE_POPCOUNT)\n\t\treturn _mm_popcnt_u64(value);\n#elif defined(RTM_NEON_INTRINSICS)\n\t\treturn vget_lane_u64(vpaddl_u32(vpaddl_u16(vpaddl_u8(vcnt_u8(vcreate_u8(value))))), 0);\n#else\n\t\tvalue = value - ((value >> 1) & 0x5555555555555555ULL);\n\t\tvalue = (value & 0x3333333333333333ULL) + ((value >> 2) & 0x3333333333333333ULL);\n\t\treturn (((value + (value >> 4)) & 0x0F0F0F0F0F0F0F0FULL) * 0x0101010101010101ULL) >> 56;\n#endif\n\t}\n\n\t//////////////////////////////////////////////////////////////////////////\n\t// Starting at the MSB, counts the number of leading zeros\n\tinline uint32_t count_leading_zeros(uint32_t value)\n\t{\n#if defined(ACL_USE_POPCOUNT)\n\t\treturn _lzcnt_u32(value);\n#elif defined(RTM_COMPILER_MSVC)\n\t\tunsigned long first_set_bit_index;\n\t\treturn _BitScanReverse(&first_set_bit_index, value) ? (31 - first_set_bit_index) : 32;\n#elif defined(RTM_COMPILER_GCC) || defined(RTM_COMPILER_CLANG)\n\t\treturn value != 0 ? __builtin_clz(value) : 32;\n#else\n\t\tvalue = value | (value >> 1);\n\t\tvalue = value | (value >> 2);\n\t\tvalue = value | (value >> 4);\n\t\tvalue = value | (value >> 8);\n\t\tvalue = value | (value >> 16);\n\t\treturn count_set_bits(~value);\n#endif\n\t}\n\n\t//////////////////////////////////////////////////////////////////////////\n\t// Starting at the LSB, counts the number of trailing zeros\n\tinline uint32_t count_trailing_zeros(uint32_t value)\n\t{\n#if defined(ACL_BMI_INTRINSICS)\n\t\treturn _tzcnt_u32(value);\n#elif defined(RTM_COMPILER_MSVC)\n\t\tunsigned long first_set_bit_index;\n\t\treturn _BitScanForward(&first_set_bit_index, value) ? first_set_bit_index : 32;\n#elif defined(RTM_COMPILER_GCC) || defined(RTM_COMPILER_CLANG)\n\t\treturn value != 0 ? __builtin_ctz(value) : 32;\n#else\n\t\treturn value != 0 ? (31 - count_leading_zeros(value & -value)) : 32;\n#endif\n\t}\n\n\t//////////////////////////////////////////////////////////////////////////\n\t// Rotate the bits left by some amount\n\tinline uint32_t rotate_bits_left(uint32_t value, int32_t num_bits)\n\t{\n\t\tACL_ASSERT(num_bits >= 0, "Attempting to rotate by negative bits");\n\t\tACL_ASSERT(num_bits < 32, "Attempting to rotate by too many bits");\n\t\tconst uint32_t mask = 32 - 1;\n\t\tnum_bits &= mask;\n\t\treturn (value << num_bits) | (value >> ((-num_bits) & mask));\n\t}\n\n\t//////////////////////////////////////////////////////////////////////////\n\t// Perform: ~not_value & and_value\n\tinline uint32_t and_not(uint32_t not_value, uint32_t and_value)\n\t{\n#if defined(ACL_BMI_INTRINSICS)\n\t\t// Use BMI\n#if defined(RTM_COMPILER_GCC) && !defined(_andn_u32)\n\t\treturn __andn_u32(not_value, and_value);\t// GCC doesn\'t define the right intrinsic symbol\n#else\n\t\treturn _andn_u32(not_value, and_value);\n#endif\n#else\n\t\treturn ~not_value & and_value;\n#endif\n\t}\n\n\tACL_IMPL_VERSION_NAMESPACE_END\n}\n\n#if defined(RTM_COMPILER_MSVC)\n\t#pragma warning(pop)\n#endif\n\nACL_IMPL_FILE_PRAGMA_POP\n', 'message': 'perf(core): enable pop-count type instructions on ARM and Xbox One\n', 'author_name': 'Nicholas Frechette', 'lang': 'h'}