Extend av_log2 in codeclib into a generic for scanning for set bits, which can provide either log2 or leading-zero-count output, and can force mapping 0 input to 0 output if needed (otherwise 0 input produces undefined result). Replace av_log2 in lib/codeclib.h, floor_log2 and wl_min_lzc in libfaad/common.c and common.h, and count_leading_zeros in libalac/alac.c with macros using bs_generic.

git-svn-id: svn://svn.rockbox.org/rockbox/trunk@23903 a1c6a512-1295-4272-9138-f99709370657

2 files changed, 89 insertions, 34 deletions

diff --git a/apps/codecs/lib/codeclib.c b/apps/codecs/lib/codeclib.c
index 1c624e0f8c..3a137068ba 100644
--- a/apps/codecs/lib/codeclib.c
+++ b/apps/codecs/lib/codeclib.c
@@ -33,6 +33,15 @@ unsigned char* mp3buf;     // The actual MP3 buffer from Rockbox
 unsigned char* mallocbuf;  // 512K from the start of MP3 buffer
 unsigned char* filebuf;    // The rest of the MP3 buffer
 
+unsigned bs_log2(unsigned x)
+{ return bs_generic(x, BS_LOG2); }
+unsigned bs_log2_0(unsigned x)
+{ return bs_generic(x, BS_LOG2|BS_0_0); }
+unsigned bs_clz(unsigned x)
+{ return bs_generic(x, BS_CLZ); }
+unsigned bs_clz_0(unsigned x)
+{ return bs_generic(x, BS_CLZ|BS_0_0); }
+
 int codec_init(void)
 {
     mem_ptr = 0;
@@ -139,7 +148,7 @@ void qsort(void *base, size_t nmemb, size_t size,
 }
 
 /* From ffmpeg - libavutil/common.h */
-const uint8_t ff_log2_tab[256] ICONST_ATTR = {
+const uint8_t bs_log2_tab[256] ICONST_ATTR = {
     0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
     5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
     6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
@@ -150,6 +159,17 @@ const uint8_t ff_log2_tab[256] ICONST_ATTR = {
     7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
 };
 
+const uint8_t bs_clz_tab[256] ICONST_ATTR = {
+    8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
+    2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
+    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
+    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
+    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
+};
+
 #ifdef RB_PROFILE
 void __cyg_profile_func_enter(void *this_fn, void *call_site) {
 #ifdef CPU_COLDFIRE
diff --git a/apps/codecs/lib/codeclib.h b/apps/codecs/lib/codeclib.h
index 9c3624b422..aeae5d6369 100644
--- a/apps/codecs/lib/codeclib.h
+++ b/apps/codecs/lib/codeclib.h
@@ -74,45 +74,80 @@ unsigned udiv32_arm(unsigned a, unsigned b);
 #define UDIV32(a, b) (a / b)
 #endif
 
-/* TODO figure out if we really need to care about calculating
-   av_log2(0) */
-#if defined(CPU_ARM) && ARM_ARCH >= 6
-static inline unsigned int av_log2(uint32_t v)
-{
-    unsigned int r;
-    asm volatile("clz %[r], %[v]\n\t" /* count leading zeroes */
-                 "rsb %[r], %[r], #31\n\t" /* r = 31 - leading zeroes */
-                 "usat %[r], #5, %[r]\n\t" /* unsigned saturate r so -1 -> 0 */
-                 :[r] "=r" (r) : [v] "r" (v));
-    return(r);
-}
-#elif defined(CPU_ARM) && ARM_ARCH >= 5
-static inline unsigned int av_log2(uint32_t v)
-{
-    return v ? 31 - __builtin_clz(v) : 0;
-}
-#else /* CPU_ARM */
+#if !defined(CPU_ARM) || ARM_ARCH < 5
 /* From libavutil/common.h */
-extern const uint8_t ff_log2_tab[256] ICONST_ATTR;
+extern const uint8_t bs_log2_tab[256] ICONST_ATTR;
+extern const uint8_t bs_clz_tab[256] ICONST_ATTR;
+#endif
 
-static inline unsigned int av_log2(unsigned int v)
-{
-    int n;
+#define BS_LOG2  0 /* default personality, equivalent floor(log2(x)) */
+#define BS_CLZ   1 /* alternate personality, Count Leading Zeros */
+#define BS_SHORT 2 /* input guaranteed not to exceed 16 bits */
+#define BS_0_0   4 /* guarantee mapping of 0 input to 0 output */
 
-    n = 0;
-    if (v & 0xffff0000) {
-        v >>= 16;
-        n += 16;
+/* Generic bit-scanning function, used to wrap platform CLZ instruction or
+   scan-and-lookup code, and to provide control over output for 0 inputs. */
+static inline unsigned int bs_generic(unsigned int v, int mode)
+{
+#if defined(CPU_ARM) && ARM_ARCH >= 5
+    unsigned int r = __builtin_clz(v);
+    if (mode & BS_CLZ)
+    {
+        if (mode & BS_0_0)
+            r &= 31;
+    } else {
+        r = 31 - r;
+        /* If mode is constant, this is a single conditional instruction */
+        if (mode & BS_0_0 && (signed)r < 0) 
+            r += 1;
+    }
+#else
+    const uint8_t *bs_tab;
+    unsigned int r;
+    unsigned int n = v;
+    int inc;
+    /* Set up table, increment, and initial result value based on
+       personality. */
+    if (mode & BS_CLZ)
+    {
+        bs_tab = bs_clz_tab;
+        r = 24;
+        inc = -16;
+    } else {
+        bs_tab = bs_log2_tab;
+        r = 0;
+        inc = 16;
     }
-    if (v & 0xff00) {
-        v >>= 8;
-        n += 8;
+    if (!(mode & BS_SHORT) && n >= 0x10000) {
+        n >>= 16;
+        r += inc;
     }
-    n += ff_log2_tab[v];
-
-    return n;
-}
+    if (n > 0xff) {
+        n >>= 8;
+        r += inc / 2;
+    }
+#ifdef CPU_COLDFIRE
+    /* The high 24 bits of n are guaranteed empty after the above, so a
+       superfluous ext.b instruction can be saved by loading the LUT value over
+       n with asm */
+    asm volatile (
+        "move.b (%1,%0.l),%0"
+        : "+d" (n)
+        : "a" (bs_tab)
+    );
+#else
+    n = bs_tab[n];
 #endif
+    r += n;
+    if (mode & BS_CLZ && mode & BS_0_0 && v == 0)
+        r = 0;
+#endif
+    return r;
+}
+
+/* TODO figure out if we really need to care about calculating
+   av_log2(0) */
+#define av_log2(v) bs_generic(v, BS_0_0)
 
 /* Various codec helper functions */