diff options
| author | Ganesh Ajjanagadde <gajjanagadde@gmail.com> | 2015-10-14 17:26:59 +0300 |
|---|---|---|
| committer | Ronald S. Bultje <rsbultje@gmail.com> | 2015-10-14 20:39:42 +0300 |
| commit | 55d3e97970888baa173061704a085144c5a014b4 (patch) | |
| tree | 9091228d79c3757490ccdf7ec47d92e8b87b98e9 /libavutil | |
| parent | 2d0a10e369f133540bc8770ba702a3ad97821f59 (diff) | |
avutil/intmath: use de Bruijn based ff_ctz
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@gmail.com>
Signed-off-by: Ronald S. Bultje <rsbultje@gmail.com>
Diffstat (limited to 'libavutil')
| -rw-r--r-- | libavutil/intmath.h | 32 |
1 files changed, 7 insertions, 25 deletions
diff --git a/libavutil/intmath.h b/libavutil/intmath.h index 802abe32b0..5a55123737 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 ) |