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

[Kenneth Graunke]

On 09/12/2012 11:03 AM, Matt Turner wrote:
> 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.

Totally agree...especially for the __builtin_clz version.  I've updated
the patch to do that.  Thanks!

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

Yeah, zero is one of my most important inputs (see patch 2) :)

> It's unfortunate that POSIX doesn't specify an fls() function.

I know, right?  It's pretty surprising there isn't just a library
function to do this.

> 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

Thanks again.