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

webrtc/common_audio/signal_processing/include/spl_inl.h

 /*
  *  Copyright (c) 2011 The WebRTC project authors. All Rights Reserved.
  *
  *  Use of this source code is governed by a BSD-style license
  *  that can be found in the LICENSE file in the root of the source
  *  tree. An additional intellectual property rights grant can be found
  *  in the file PATENTS.  All contributing project authors may
  *  be found in the AUTHORS file in the root of the source tree.
  */
 
 
 // This header file includes the inline functions in
 // the fix point signal processing library.
 
 #ifndef WEBRTC_SPL_SPL_INL_H_
 #define WEBRTC_SPL_SPL_INL_H_
 
+#include "webrtc/system_wrappers/include/compile_assert_c.h"
+
+// Don't call this directly except in tests!
+static __inline int WebRtcSpl_CountLeadingZeros32_NotBuiltin(uint32_t n) {
+  int leading_zeros = n >> 16 == 0 ? 16 : 0;
+  leading_zeros += (n << leading_zeros) >> 24 == 0 ? 8 : 0;
+  leading_zeros += (n << leading_zeros) >> 28 == 0 ? 4 : 0;
+  leading_zeros += (n << leading_zeros) >> 30 == 0 ? 2 : 0;
+  leading_zeros += (n << leading_zeros) >> 31 == 0 ? 1 : 0;
+  leading_zeros += (n << leading_zeros) >> 31 == 0 ? 1 : 0;
+  return leading_zeros;
+}
+
+// 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
 
 #if defined(MIPS32_LE)
 #include "webrtc/common_audio/signal_processing/include/spl_inl_mips.h"
 #endif
 
 #if !defined(MIPS_DSP_R1_LE)
 static __inline int16_t WebRtcSpl_SatW32ToW16(int32_t value32) {
@@ skipping 39 matching lines @@
   return WebRtcSpl_SatW32ToW16((int32_t) a + (int32_t) b);
 }
 
 static __inline int16_t WebRtcSpl_SubSatW16(int16_t var1, int16_t var2) {
   return WebRtcSpl_SatW32ToW16((int32_t) var1 - (int32_t) var2);
 }
 #endif  // #if !defined(MIPS_DSP_R1_LE)
 
 #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) {

[tlegrand-webrtc, 2016/05/26 12:01:46]

Maybe use your new function here as well?

   int16_t zeros;
 
   if (a == 0) {
     return 0;
   }
   else if (a < 0) {
     a = ~a;
   }
 
   if (!(0xFFFF8000 & a)) {
     zeros = 16;
   } else {
     zeros = 0;
   }
   if (!(0xFF800000 & (a << zeros))) zeros += 8;
   if (!(0xF8000000 & (a << zeros))) zeros += 4;
   if (!(0xE0000000 & (a << zeros))) zeros += 2;
   if (!(0xC0000000 & (a << zeros))) zeros += 1;
 
   return zeros;
 }
 
 static __inline int16_t WebRtcSpl_NormU32(uint32_t a) {

[tlegrand-webrtc, 2016/05/26 12:01:46]

And here.

   int16_t zeros;
 
   if (a == 0) return 0;
 
   if (!(0xFFFF0000 & a)) {
     zeros = 16;
   } else {
     zeros = 0;
   }
   if (!(0xFF000000 & (a << zeros))) zeros += 8;
@@ skipping 27 matching lines @@
 }
 
 static __inline int32_t WebRtc_MulAccumW16(int16_t a, int16_t b, int32_t c) {
   return (a * b + c);
 }
 #endif  // #if !defined(MIPS32_LE)
 
 #endif  // WEBRTC_ARCH_ARM_V7
 
 #endif  // WEBRTC_SPL_SPL_INL_H_