Add clz functions (Count number of Leading Zero bits), 32-and 64-bit variants

webrtc/common_audio/signal_processing/include/spl_inl.h

Index: webrtc/common_audio/signal_processing/include/spl_inl.h
diff --git a/webrtc/common_audio/signal_processing/include/spl_inl.h b/webrtc/common_audio/signal_processing/include/spl_inl.h
index 3c0a81cf34a7e5fba062801936d5d2a31adfd922..884886de7a7426d376033cb165b75c8034341f2a 100644
--- a/webrtc/common_audio/signal_processing/include/spl_inl.h
+++ b/webrtc/common_audio/signal_processing/include/spl_inl.h
@@ -15,6 +15,54 @@
 #ifndef WEBRTC_SPL_SPL_INL_H_
 #define WEBRTC_SPL_SPL_INL_H_
 
+#include "webrtc/system_wrappers/include/compile_assert_c.h"
+
+extern const int8_t kWebRtcSpl_CountLeadingZeros32_Table[64];
+
+// Don't call this directly except in tests!
+static __inline int WebRtcSpl_CountLeadingZeros32_NotBuiltin(uint32_t n) {
+  // Normalize n by rounding up to the nearest number that is a sequence of 0
+  // bits followed by a sequence of 1 bits. This number has the same number of
+  // leading zeros as the original n. There are exactly 33 such values.
+  n |= n >> 1;
+  n |= n >> 2;
+  n |= n >> 4;
+  n |= n >> 8;
+  n |= n >> 16;
+
+  // Multiply the modified n with a constant selected (by exhaustive search)
+  // such that each of the 33 possible values of n give a product whose 6 most
+  // significant bits are unique. Then look up the answer in the table.
+  return kWebRtcSpl_CountLeadingZeros32_Table[(n * 0x8c0b2891) >> 26];
+}
+
+// Don't call this directly except in tests!
+static __inline int WebRtcSpl_CountLeadingZeros64_NotBuiltin(uint64_t n) {
+  const int leading_zeros = n >> 32 == 0 ? 32 : 0;
+  return leading_zeros + WebRtcSpl_CountLeadingZeros32_NotBuiltin(
+                             (uint32_t)(n >> (32 - leading_zeros)));
+}
+
+// Returns the number of leading zero bits in the argument.
+static __inline int WebRtcSpl_CountLeadingZeros32(uint32_t n) {
+#ifdef __GNUC__
+  COMPILE_ASSERT(sizeof(unsigned int) == sizeof(uint32_t));
+  return n == 0 ? 32 : __builtin_clz(n);
+#else
+  return WebRtcSpl_CountLeadingZeros32_NotBuiltin(n);
+#endif
+}
+
+// Returns the number of leading zero bits in the argument.
+static __inline int WebRtcSpl_CountLeadingZeros64(uint64_t n) {
+#ifdef __GNUC__
+  COMPILE_ASSERT(sizeof(unsigned long long) == sizeof(uint64_t));
+  return n == 0 ? 64 : __builtin_clzll(n);
+#else
+  return WebRtcSpl_CountLeadingZeros64_NotBuiltin(n);
+#endif
+}
+
 #ifdef WEBRTC_ARCH_ARM_V7
 #include "webrtc/common_audio/signal_processing/include/spl_inl_armv7.h"
 #else
@@ -74,20 +122,7 @@ static __inline int16_t WebRtcSpl_SubSatW16(int16_t var1, int16_t var2) {
 
 #if !defined(MIPS32_LE)
 static __inline int16_t WebRtcSpl_GetSizeInBits(uint32_t n) {
-  int16_t bits;
-
-  if (0xFFFF0000 & n) {
-    bits = 16;
-  } else {
-    bits = 0;
-  }
-  if (0x0000FF00 & (n >> bits)) bits += 8;
-  if (0x000000F0 & (n >> bits)) bits += 4;
-  if (0x0000000C & (n >> bits)) bits += 2;
-  if (0x00000002 & (n >> bits)) bits += 1;
-  if (0x00000001 & (n >> bits)) bits += 1;
-
-  return bits;
+  return 32 - WebRtcSpl_CountLeadingZeros32(n);
 }
 
 static __inline int16_t WebRtcSpl_NormW32(int32_t a) {