Math utils: Add bit scan operations

2 files changed, 42 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_math_bits.h b/source/blender/blenlib/BLI_math_bits.h
index 40a1d84b0e1..248b615e3f8 100644
--- a/source/blender/blenlib/BLI_math_bits.h
+++ b/source/blender/blenlib/BLI_math_bits.h
@@ -31,6 +31,14 @@ extern "C" {
 
 #include "BLI_math_inline.h"
 
+/* Search the value from LSB to MSB for a set bit. Returns index of this bit. */
+MINLINE int bitscan_forward_i(int a);
+MINLINE unsigned int bitscan_forward_uint(unsigned int a);
+
+/* Search the value from MSB to LSB for a set bit. Returns index of this bit. */
+MINLINE int bitscan_reverse_i(int a);
+MINLINE unsigned int bitscan_reverse_uint(unsigned int a);
+
 /* NOTE: Those functions returns 2 to the power of index of highest order bit. */
 MINLINE unsigned int highest_order_bit_uint(unsigned int n);
 MINLINE unsigned short highest_order_bit_s(unsigned short n);
diff --git a/source/blender/blenlib/intern/math_bits_inline.c b/source/blender/blenlib/intern/math_bits_inline.c
index 9f502d367cb..fdef0f9c9c6 100644
--- a/source/blender/blenlib/intern/math_bits_inline.c
+++ b/source/blender/blenlib/intern/math_bits_inline.c
@@ -27,6 +27,40 @@
 
 #include "BLI_math_bits.h"
 
+MINLINE int bitscan_forward_i(int a)
+{
+	BLI_assert(a != 0);
+#  ifdef _MSC_VER
+	unsigned long ctz;
+	_BitScanForward(&ctz, a);
+	return ctz;
+#else
+	return __builtin_ctz((unsigned int)a);
+#endif
+}
+
+MINLINE unsigned int bitscan_forward_uint(unsigned int a)
+{
+	return (unsigned int)bitscan_forward_i((int)a);
+}
+
+MINLINE int bitscan_reverse_i(int a)
+{
+	BLI_assert(a != 0);
+#  ifdef _MSC_VER
+	unsigned long clz;
+	_BitScanReverse(&clz, a);
+	return clz;
+#else
+	return __builtin_clz((unsigned int)a);
+#endif
+}
+
+MINLINE unsigned int bitscan_reverse_uint(unsigned int a)
+{
+	return (unsigned int)bitscan_reverse_i((int)a);
+}
+
 MINLINE unsigned int highest_order_bit_uint(unsigned int n)
 {
 	n |= (n >>  1);