[FFmpeg-devel] [PATCHv2] avutil/intmath: use de Bruijn based ff_ctz

[Ganesh Ajjanagadde]

On Wed, Oct 14, 2015 at 1:13 PM, Ronald S. Bultje <rsbultje at gmail.com> wrote:
> Hi,
>
> On Wed, Oct 14, 2015 at 10:26 AM, Ganesh Ajjanagadde
> <gajjanagadde at gmail.com> wrote:
>>
>> It has already been demonstrated that the de Bruijn method has benefits
>> over the current implementation: commit
>> 971d12b7f9d7be3ca8eb98e6c04ed521f83cbd3c.
>> That commit implemented it for long long, this extends it to the int
>> version.
>>
>> Tested with FATE.
>>
>> Signed-off-by: Ganesh Ajjanagadde <gajjanagadde at gmail.com>
>> ---
>>  libavutil/intmath.h | 32 +++++++-------------------------
>>  1 file changed, 7 insertions(+), 25 deletions(-)
>>
>> diff --git a/libavutil/intmath.h b/libavutil/intmath.h
>> index 802abe3..5a55123 100644
>> --- a/libavutil/intmath.h
>> +++ b/libavutil/intmath.h
>> @@ -129,33 +129,15 @@ static av_always_inline av_const int
>> ff_log2_16bit_c(unsigned int v)
>>   * @return   the number of trailing 0-bits
>>   */
>>  #if !defined( _MSC_VER )
>> +/* We use the De-Bruijn method outlined in:
>> + * http://supertech.csail.mit.edu/papers/debruijn.pdf. */
>>  static av_always_inline av_const int ff_ctz_c(int v)
>>  {
>> -    int c;
>> -
>> -    if (v & 0x1)
>> -        return 0;
>> -
>> -    c = 1;
>> -    if (!(v & 0xffff)) {
>> -        v >>= 16;
>> -        c += 16;
>> -    }
>> -    if (!(v & 0xff)) {
>> -        v >>= 8;
>> -        c += 8;
>> -    }
>> -    if (!(v & 0xf)) {
>> -        v >>= 4;
>> -        c += 4;
>> -    }
>> -    if (!(v & 0x3)) {
>> -        v >>= 2;
>> -        c += 2;
>> -    }
>> -    c -= v & 0x1;
>> -
>> -    return c;
>> +    static const uint8_t debruijn_ctz32[32] = {
>> +        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
>> +        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
>> +    };
>> +    return debruijn_ctz32[(uint32_t)((v & -v) * 0x077CB531U) >> 27];
>>  }
>>  #else
>>  static av_always_inline av_const int ff_ctz_c( int v )
>> --
>> 2.6.1
>
>
> lgtm. Would you like to push yourself or have me do it for you?

Either way is fine: if it is not done by tonight, I will do it.
Thanks.

>
> Ronald