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"
+
+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
 
 #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);
 }
 
+// Return the number of steps a can be left-shifted without overflow, or 0 if a

[tlegrand-webrtc, 2016/06/02 09:49:11]

Nit: move 'a' to next line.

[kwiberg-webrtc, 2016/06/02 09:55:34]

Done.

+// == 0.
 static __inline int16_t WebRtcSpl_NormW32(int32_t a) {
-  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;
+  return a == 0 ? 0 : WebRtcSpl_CountLeadingZeros32(a < 0 ? ~a : a) - 1;
 }
 
+// Return the number of steps a can be left-shifted without overflow, or 0 if a
+// == 0.

[tlegrand-webrtc, 2016/06/02 09:49:11]

Same nit.

[kwiberg-webrtc, 2016/06/02 09:55:34]

Done.

 static __inline int16_t WebRtcSpl_NormU32(uint32_t a) {
-  int16_t zeros;
-
-  if (a == 0) return 0;
-
-  if (!(0xFFFF0000 & a)) {
-    zeros = 16;
-  } else {
-    zeros = 0;
-  }
-  if (!(0xFF000000 & (a << zeros))) zeros += 8;
-  if (!(0xF0000000 & (a << zeros))) zeros += 4;
-  if (!(0xC0000000 & (a << zeros))) zeros += 2;
-  if (!(0x80000000 & (a << zeros))) zeros += 1;
-
-  return zeros;
+  return a == 0 ? 0 : WebRtcSpl_CountLeadingZeros32(a);
 }
 
+// Return the number of steps a can be left-shifted without overflow, or 0 if a

[tlegrand-webrtc, 2016/06/02 09:49:11]

...and here. :)

[kwiberg-webrtc, 2016/06/02 09:55:34]

Done.

+// == 0.
 static __inline int16_t WebRtcSpl_NormW16(int16_t a) {
-  int16_t zeros;
-
-  if (a == 0) {
-    return 0;
-  }
-  else if (a < 0) {
-    a = ~a;
-  }
-
-  if (!(0xFF80 & a)) {
-    zeros = 8;
-  } else {
-    zeros = 0;
-  }
-  if (!(0xF800 & (a << zeros))) zeros += 4;
-  if (!(0xE000 & (a << zeros))) zeros += 2;
-  if (!(0xC000 & (a << zeros))) zeros += 1;
-
-  return zeros;
+  const int32_t a32 = a;
+  return a == 0 ? 0 : WebRtcSpl_CountLeadingZeros32(a < 0 ? ~a32 : a32) - 17;
 }
 
 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_