[Mesa-dev] [PATCH 1/2] mesa: Add a _mesa_fls() function to find the last bit set in a word.

[Matt Turner]

On Tue, Sep 11, 2012 at 10:14 PM, Kenneth Graunke <kenneth at whitecape.org> wrote:
> ffs() finds the least significant bit set; _mesa_fls() finds the /most/
> significant bit.
>
> Signed-off-by: Kenneth Graunke <kenneth at whitecape.org>
> ---
>  src/mesa/main/imports.c | 22 ++++++++++++++++++++++
>  src/mesa/main/imports.h |  2 ++
>  2 files changed, 24 insertions(+)
>
> Wow.  NAK my last patch which used ffs().  Totally backwards and just
> happened to work for the one test because it only used limited values.
>
> diff --git a/src/mesa/main/imports.c b/src/mesa/main/imports.c
> index 934a2d0..eac8e21 100644
> --- a/src/mesa/main/imports.c
> +++ b/src/mesa/main/imports.c
> @@ -316,6 +316,28 @@ _mesa_bitcount_64(uint64_t n)
>  }
>  #endif
>
> +/**
> + * Find the last (most significant) bit set in a word.
> + *
> + * Essentially ffs() in the reverse direction.
> + */
> +unsigned int
> +_mesa_fls(unsigned int n)
> +{
> +#if defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304)
> +   return n == 0 ? 0 : 32 - __builtin_clz(n);
> +#else
> +   unsigned int v = 1;
> +
> +   if (n == 0)
> +      return 0;
> +
> +   while (n >>= 1)
> +       v++;
> +
> +   return v;
> +#endif
> +}
>

I agree with Brian that we should avoid a function call and inline
this. We could do this as a follow-on. Don't care much.

Nice remembering that __builtin_clz has undefined behavior when given
zero as input. Wikipedia [1] confirms this.

It's unfortunate that POSIX doesn't specify an fls() function. While
searching in vain for fls() man pages, I came across [2] which makes
me think that our conditions for defining ffs() in imports.* are sort
of wrong.

Reviewed-by: Matt Turner <mattst88 at gmail.com>

[1] http://en.wikipedia.org/wiki/Find_first_set#Tool_and_library_support
[2] http://www.kernel.org/doc/man-pages/online/pages/man3/ffsl.3.html