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

[Ronald S. Bultje]

Hi,

On Wed, Oct 14, 2015 at 1:26 PM, Ganesh Ajjanagadde <gajjanagadde at gmail.com>
wrote:

> 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.


Pushed :)

Ronald