Re: [PATCH] count-leading-zeros: new module

[Eric Blake]

On 08/11/2012 01:45 AM, Jim Meyering wrote:
> Eric Blake wrote:
>> I needed gcc's clz to determine the most significant bit of a
>> number (useful for things like truncating to a power of 2),
>> and was surprised it is not a standardized function

> Did you consider using a variant of the following?
> It looks like it would be more efficient.
> 
> [From http://graphics.stanford.edu/~seander/bithacks.html]
> 
>       Find the log base 2 of an N-bit integer in O(lg(N)) operations
>       with multiply and lookup

Pushed as follows:

From d22f151db0e5217913ec1667a3b4e354dd88a973 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Sat, 11 Aug 2012 07:34:00 -0600
Subject: [PATCH] count-leading-zeros: use a lookup table on non-gcc
compilers

While this only affects non-gcc compilers, we can assume that
lookups are faster than conditionals, even if it results in
a slightly larger executable size.

* lib/count-leading-zeros.h (count_leading_zeros_32): Use an
alternate implementation, suggested by Jim Meyering.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog                 |  6 ++++++
 lib/count-leading-zeros.h | 41 ++++++++++++++++-------------------------
 2 files changed, 22 insertions(+), 25 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 80d1b61..2b7090b 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+2012-08-11  Eric Blake  <address@hidden>
+
+       count-leading-zeros: use a lookup table on non-gcc compilers
+       * lib/count-leading-zeros.h (count_leading_zeros_32): Use an
+       alternate implementation, suggested by Jim Meyering.
+
 2012-08-10  Eric Blake  <address@hidden>

        count-leading-zeros: new module
diff --git a/lib/count-leading-zeros.h b/lib/count-leading-zeros.h
index 4d7c291..cbb3264 100644
--- a/lib/count-leading-zeros.h
+++ b/lib/count-leading-zeros.h
@@ -26,7 +26,7 @@
 /* Expand the code which computes the number of leading zeros of the local
    variable 'x' of type TYPE (an unsigned integer type) and returns it
    from the current function.  */
-#if 0 && __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 # define COUNT_LEADING_ZEROS(BUILTIN, TYPE)     \
   return x ? BUILTIN (x) : CHAR_BIT * sizeof x;
 #else
@@ -47,30 +47,21 @@
 static inline int
 count_leading_zeros_32 (unsigned int x)
 {
-  int count = 0;
-  if (x & 0xffff0000U)
-    x >>= 16;
-  else
-    count += 16;
-  if (x & 0xff00)
-    x >>= 8;
-  else
-    count += 8;
-  if (x & 0xf0)
-    x >>= 4;
-  else
-    count += 4;
-  if (x & 0xc)
-    x >>= 2;
-  else
-    count += 2;
-  if (x & 2)
-    x >>= 1;
-  else
-    count++;
-  if (!(x & 1))
-    count++;
-  return count;
+  /* http://graphics.stanford.edu/~seander/bithacks.html */
+  static const char deBruijnLookup[32] = {
+    0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
+    8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
+  };
+
+  x &= 0xffffffffU;
+  if (!x)
+    return 32;
+  x |= x >> 1;
+  x |= x >> 2;
+  x |= x >> 4;
+  x |= x >> 8;
+  x |= x >> 16;
+  return 31 - deBruijnLookup[(x * 0x07c4acddU) >> 27];
 }
 #endif

-- 
1.7.11.2


-- 
Eric Blake   address@hidden    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

signature.asc
Description: OpenPGP digital signature