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

[Ronald S. Bultje]

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?

Ronald