[FFmpeg-devel] [PATCH] intmath.h: add an ff_log2_nz

[Rostislav Pehlivanov]

This commit adds a raw integer log2 function (which directly maps to a
builtin). This was needed as the Daala entropy coding system requires a
raw log2 and the existing ff_log2 OR'd the argument with 1.

The C implementation was taken from Daala's source code, which
got it from someplace else as a search reveals more similar
implementations. It was described as the fastest
implementation tested on a Pentium MMX, but considering its simplicity
this statement is still probably valid to this day.

While the native Daala decoder is still in development, this required
piece might prove useful to other parts of the code, such as access to
the __builtin_clz.

Signed-off-by: Rostislav Pehlivanov <atomnuker at gmail.com>
---
 libavutil/intmath.h | 53 ++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 52 insertions(+), 1 deletion(-)

diff --git a/libavutil/intmath.h b/libavutil/intmath.h
index 2016723..b61341a 100644
--- a/libavutil/intmath.h
+++ b/libavutil/intmath.h
@@ -35,8 +35,14 @@
 
 #if HAVE_FAST_CLZ
 #if AV_GCC_VERSION_AT_LEAST(3,4)
+#ifndef ff_log2_nz
+#   define ff_log2_nz(x) (CHAR_BIT*sizeof(unsigned) - __builtin_clz(x))
+#endif /* ff_log2_nz */
+#ifndef ff_log2l_nz
+#   define ff_log2l_nz(x) (CHAR_BIT*sizeof(long unsigned) - __builtin_clzl(x))
+#endif /* ff_log2l_nz */
 #ifndef ff_log2
-#   define ff_log2(x) (31 - __builtin_clz((x)|1))
+#   define ff_log2(x) (8*sizeof(unsigned int) - 1 - __builtin_clz((x)|1))
 #   ifndef ff_log2_16bit
 #      define ff_log2_16bit av_log2
 #   endif
@@ -44,6 +50,51 @@
 #endif /* AV_GCC_VERSION_AT_LEAST(3,4) */
 #endif
 
+#ifndef ff_log2_nz
+#define ff_log2_nz ff_log2_c_nz
+/* From Daala, src/internal.c, od_ilog() */
+static av_always_inline av_const int ff_log2_c_nz(unsigned int x)
+{
+    int ret = !!x;
+    int m = !!(x&0xFFFF0000)<<4;
+    x >>= m;
+    ret |= m;
+    m = !!(x&0xFF00)<<3;
+    x >>= m;
+    ret |= m;
+    m = !!(x&0xF0)<<2;
+    x >>= m;
+    ret |= m;
+    m = !!(x&0xC)<<1;
+    x >>= m;
+    ret |= m;
+    ret += !!(x&0x2);
+    return ret;
+}
+#endif
+
+#ifndef ff_log2l_nz
+#define ff_log2l_nz ff_log2l_c_nz
+static av_always_inline av_const int ff_log2l_c_nz(long unsigned int x)
+{
+    long int ret = !!x;
+    long int m = !!(x&0xFFFF0000)<<4;
+    x >>= m;
+    ret |= m;
+    m = !!(x&0xFF00)<<3;
+    x >>= m;
+    ret |= m;
+    m = !!(x&0xF0)<<2;
+    x >>= m;
+    ret |= m;
+    m = !!(x&0xC)<<1;
+    x >>= m;
+    ret |= m;
+    ret += !!(x&0x2);
+    return ret;
+}
+#endif
+
 extern const uint8_t ff_log2_tab[256];
 
 #ifndef ff_log2
-- 
2.6.4