chmap_sel: add multichannel fallback heuristic

Instead of just failing during channel map selection, try to select a close
layout that makes most sense and upmix/downmix to that instead of failing AO
initialization. The heuristic is rather simple, and uses the following steps:

1) If mono is required always prefer stereo to a multichannel upmix.
2) Search for an upmix that is an exact superset of the required channel map.
3) Search for a downmix that is the exact subset of the required channel map.
4) Search for either an upmix or downmix that is the closest (minimum difference
   of channels) to the required channel map.

9 files changed, 381 insertions, 4 deletions

diff --git a/audio/chmap.c b/audio/chmap.c
index 64b56b93b2..497b910cff 100644
--- a/audio/chmap.c
+++ b/audio/chmap.c
@@ -375,6 +375,29 @@ void mp_chmap_get_reorder(int dst[MP_NUM_CHANNELS], const struct mp_chmap *from,
         assert(to->speaker[dst[n]] == from->speaker[n]);
 }
 
+// Performs the difference between a and b, and store it in diff. If b has
+// channels that do not appear in a, those will not appear in the difference.
+// To get to those the argument ordering in the function call has to be
+// inverted. For the same reason, the diff with a superset will return no
+// speakers.
+void mp_chmap_diff(const struct mp_chmap *a, const struct mp_chmap *b,
+                   struct mp_chmap *diff)
+{
+    uint64_t a_mask = mp_chmap_to_lavc_unchecked(a);
+    uint64_t b_mask = mp_chmap_to_lavc_unchecked(b);
+    mp_chmap_from_lavc(diff, (a_mask ^ b_mask) & a_mask);
+}
+
+// Checks whether a contains all the speakers in b
+bool mp_chmap_contains(const struct mp_chmap *a, const struct mp_chmap *b)
+{
+    struct mp_chmap d1;
+    struct mp_chmap d2;
+    mp_chmap_diff(a, b, &d1);
+    mp_chmap_diff(b, a, &d2);
+    return a->num >= b->num && d1.num >= 0 && d2.num == 0;
+}
+
 // Returns something like "fl-fr-fc". If there's a standard layout in lavc
 // order, return that, e.g. "3.0" instead of "fl-fr-fc".
 // Unassigned but valid speakers get names like "sp28".
diff --git a/audio/chmap.h b/audio/chmap.h
index d0b9806ff5..9ec1c12d7b 100644
--- a/audio/chmap.h
+++ b/audio/chmap.h
@@ -120,6 +120,11 @@ void mp_chmap_reorder_to_lavc(struct mp_chmap *map);
 void mp_chmap_get_reorder(int dst[MP_NUM_CHANNELS], const struct mp_chmap *from,
                           const struct mp_chmap *to);
 
+void mp_chmap_diff(const struct mp_chmap *a, const struct mp_chmap *b,
+                   struct mp_chmap *diff);
+
+bool mp_chmap_contains(const struct mp_chmap *a, const struct mp_chmap *b);
+
 char *mp_chmap_to_str_buf(char *buf, size_t buf_size, const struct mp_chmap *src);
 #define mp_chmap_to_str(m) mp_chmap_to_str_buf((char[64]){0}, 64, (m))
 
diff --git a/audio/chmap_sel.c b/audio/chmap_sel.c
index fe0b9598a0..23ebe71710 100644
--- a/audio/chmap_sel.c
+++ b/audio/chmap_sel.c
@@ -17,6 +17,7 @@
 
 #include <stdlib.h>
 #include <assert.h>
+#include <limits.h>
 
 #include "common/common.h"
 #include "chmap_sel.h"
@@ -183,6 +184,10 @@ bool mp_chmap_sel_adjust(const struct mp_chmap_sel *s, struct mp_chmap *map)
             return true;
         }
     }
+
+    if (mp_chmap_sel_fallback(s, map))
+        return true;
+
     // Fallback to mono/stereo as last resort
     *map = (struct mp_chmap) MP_CHMAP_INIT_STEREO;
     if (test_layout(s, map))
@@ -194,6 +199,95 @@ bool mp_chmap_sel_adjust(const struct mp_chmap_sel *s, struct mp_chmap *map)
     return false;
 }
 
+#define UPMIX_IDX 0
+#define DOWNMIX_IDX 1
+#define FALLBACK_IDX 2
+
+static bool test_fallbacks(struct mp_chmap *a, struct mp_chmap *b,
+                           int best_diffs[2], struct mp_chmap best[2])
+{
+    struct mp_chmap diff1, diff2;
+
+    mp_chmap_diff(a, b, &diff1);
+    if (mp_chmap_contains(a, b) && best_diffs[UPMIX_IDX] > diff1.num) {
+        best[UPMIX_IDX] = *a;
+        best_diffs[UPMIX_IDX] = diff1.num;
+        return true;
+    }
+
+    mp_chmap_diff(b, a, &diff2);
+    if (mp_chmap_contains(b, a) && best_diffs[DOWNMIX_IDX] > diff2.num) {
+        best[DOWNMIX_IDX] = *a;
+        best_diffs[DOWNMIX_IDX] = diff2.num;
+        return true;
+    }
+
+    if (diff1.num > 0 && best_diffs[FALLBACK_IDX] > diff1.num) {
+        best[FALLBACK_IDX] = *a;
+        best_diffs[FALLBACK_IDX] = diff1.num;
+        return true;
+    }
+
+    if (diff2.num > 0 && best_diffs[FALLBACK_IDX] > diff2.num) {
+        best[FALLBACK_IDX] = *a;
+        best_diffs[FALLBACK_IDX] = diff2.num;
+        return true;
+    }
+
+    return false;
+}
+
+// Determine which channel map to fallback to given a source channel map. It
+// uses the following heuristic:
+// 1) If mono is required always prefer stereo to a multichannel upmix.
+// 2) Search for an upmix that is an exact superset of the required chmap.
+// 3) Search for a downmix that is the exact subset of the required chmap.
+// 4) Search for either an upmix or downmix that is the closest (minimum
+//    difference of speakers) to the required chmap.
+bool mp_chmap_sel_fallback(const struct mp_chmap_sel *s, struct mp_chmap *map)
+{
+    // special case: if possible always fallback mono to stereo (instead of
+    // looking for a multichannel upmix)
+    struct mp_chmap mono   = MP_CHMAP_INIT_MONO;
+    struct mp_chmap stereo = MP_CHMAP_INIT_STEREO;
+    if (mp_chmap_equals(&mono, map) && test_layout(s, &stereo)) {
+        *map = stereo;
+        return true;
+    }
+
+    int best_diffs[] = { INT_MAX, INT_MAX, INT_MAX };
+    struct mp_chmap best[] = { {0}, {0}, {0} };
+
+    for (int n = 0; n < s->num_chmaps; n++) {
+        struct mp_chmap e = s->chmaps[n];
+
+        if (mp_chmap_is_unknown(&e))
+            continue;
+
+        if (test_fallbacks(&e, map, best_diffs, best))
+            continue;
+
+        // in case we didn't match any fallback retry after replacing speakers
+        for (int i = 0; i < MP_ARRAY_SIZE(speaker_replacements); i++) {
+            struct mp_chmap  t = e;
+            struct mp_chmap *r = (struct mp_chmap *)speaker_replacements[i];
+            if (replace_speakers(&t, r)) {
+                if (test_fallbacks(&t, map, best_diffs, best))
+                    continue;
+            }
+        }
+    }
+
+    for (int i = UPMIX_IDX; i < MP_ARRAY_SIZE(best); i++) {
+        if (best_diffs[i] < INT_MAX) {
+            *map = best[i];
+            return true;
+        }
+    }
+
+    return false;
+}
+
 // Set map to a default layout with num channels. Used for audio APIs that
 // return a channel count as part of format negotiation, but give no
 // information about the channel layout.
diff --git a/audio/chmap_sel.h b/audio/chmap_sel.h
index 7758ca5d74..ae80fa5bc3 100644
--- a/audio/chmap_sel.h
+++ b/audio/chmap_sel.h
@@ -41,6 +41,7 @@ void mp_chmap_sel_add_alsa_def(struct mp_chmap_sel *s);
 void mp_chmap_sel_add_map(struct mp_chmap_sel *s, const struct mp_chmap *map);
 void mp_chmap_sel_add_speaker(struct mp_chmap_sel *s, int id);
 bool mp_chmap_sel_adjust(const struct mp_chmap_sel *s, struct mp_chmap *map);
+bool mp_chmap_sel_fallback(const struct mp_chmap_sel *s, struct mp_chmap *map);
 bool mp_chmap_sel_get_def(const struct mp_chmap_sel *s, struct mp_chmap *map,
                           int num);
 
diff --git a/test/chmap.c b/test/chmap.c
new file mode 100644
index 0000000000..f0e8a1802d
--- /dev/null
+++ b/test/chmap.c
@@ -0,0 +1,56 @@
+#include "test_helpers.h"
+#include "audio/chmap.h"
+
+static void test_mp_chmap_diff(void **state) {
+    struct mp_chmap a;
+    struct mp_chmap b;
+    struct mp_chmap diff;
+
+    mp_chmap_from_str(&a, bstr0("3.1"));
+    mp_chmap_from_str(&b, bstr0("2.1"));
+
+    mp_chmap_diff(&a, &b, &diff);
+    assert_int_equal(diff.num, 1);
+    assert_int_equal(diff.speaker[0], MP_SPEAKER_ID_FC);
+
+    mp_chmap_from_str(&b, bstr0("6.1(back)"));
+    mp_chmap_diff(&a, &b, &diff);
+    assert_int_equal(diff.num, 0);
+
+    mp_chmap_diff(&b, &a, &diff);
+    assert_int_equal(diff.num, 3);
+    assert_int_equal(diff.speaker[0], MP_SPEAKER_ID_BL);
+    assert_int_equal(diff.speaker[1], MP_SPEAKER_ID_BR);
+    assert_int_equal(diff.speaker[2], MP_SPEAKER_ID_BC);
+}
+
+static void test_mp_chmap_contains_with_related_chmaps(void **state) {
+    struct mp_chmap a;
+    struct mp_chmap b;
+
+    mp_chmap_from_str(&a, bstr0("3.1"));
+    mp_chmap_from_str(&b, bstr0("2.1"));
+
+    assert_true(mp_chmap_contains(&a, &b));
+    assert_false(mp_chmap_contains(&b, &a));
+}
+
+static void test_mp_chmap_contains_with_unrelated_chmaps(void **state) {
+    struct mp_chmap a;
+    struct mp_chmap b;
+
+    mp_chmap_from_str(&a, bstr0("mono"));
+    mp_chmap_from_str(&b, bstr0("stereo"));
+
+    assert_false(mp_chmap_contains(&a, &b));
+    assert_false(mp_chmap_contains(&b, &a));
+}
+
+int main(void) {
+    const UnitTest tests[] = {
+        unit_test(test_mp_chmap_diff),
+        unit_test(test_mp_chmap_contains_with_related_chmaps),
+        unit_test(test_mp_chmap_contains_with_unrelated_chmaps),
+    };
+    return run_tests(tests);
+}
diff --git a/test/chmap_sel.c b/test/chmap_sel.c
new file mode 100644
index 0000000000..c315d2f9a1
--- /dev/null
+++ b/test/chmap_sel.c
@@ -0,0 +1,162 @@
+#include "test_helpers.h"
+#include "audio/chmap_sel.h"
+
+static void test_mp_chmap_sel_fallback_upmix(void **state) {
+    struct mp_chmap a;
+    struct mp_chmap b;
+    struct mp_chmap_sel s = {0};
+
+    mp_chmap_from_str(&a, bstr0("7.1"));
+    mp_chmap_from_str(&b, bstr0("5.1"));
+
+    mp_chmap_sel_add_map(&s, &a);
+    assert_true(mp_chmap_sel_fallback(&s, &b));
+    assert_string_equal(mp_chmap_to_str(&b), "7.1");
+}
+
+static void test_mp_chmap_sel_fallback_downmix(void **state) {
+    struct mp_chmap a;
+    struct mp_chmap b;
+    struct mp_chmap_sel s = {0};
+
+    mp_chmap_from_str(&a, bstr0("5.1"));
+    mp_chmap_from_str(&b, bstr0("7.1"));
+
+    mp_chmap_sel_add_map(&s, &a);
+    assert_true(mp_chmap_sel_fallback(&s, &b));
+    assert_string_equal(mp_chmap_to_str(&b), "5.1");
+}
+
+static void test_mp_chmap_sel_fallback_incompatible(void **state) {
+    struct mp_chmap a;
+    struct mp_chmap b;
+    struct mp_chmap_sel s = {0};
+
+    mp_chmap_from_str(&a, bstr0("7.1"));
+    mp_chmap_from_str(&b, bstr0("7.1(wide-side)"));
+
+    mp_chmap_sel_add_map(&s, &a);
+    assert_true(mp_chmap_sel_fallback(&s, &b));
+    assert_string_equal(mp_chmap_to_str(&b), "7.1");
+}
+
+static void test_mp_chmap_sel_fallback_prefer_compatible(void **state) {
+    struct mp_chmap a, b, c;
+    struct mp_chmap_sel s = {0};
+
+    mp_chmap_from_str(&a, bstr0("7.1"));
+    mp_chmap_from_str(&b, bstr0("5.1(side)"));
+    mp_chmap_from_str(&c, bstr0("7.1(wide-side)"));
+
+    mp_chmap_sel_add_map(&s, &a);
+    mp_chmap_sel_add_map(&s, &b);
+
+    assert_true(mp_chmap_sel_fallback(&s, &c));
+    assert_string_equal(mp_chmap_to_str(&b), "5.1(side)");
+}
+
+static void test_mp_chmap_sel_fallback_prefer_closest_upmix(void **state) {
+    struct mp_chmap_sel s = {0};
+
+    char *maps[] = { "7.1", "5.1", "2.1", "stereo", "mono", NULL };
+    for (int i = 0; maps[i]; i++) {
+        struct mp_chmap m;
+        mp_chmap_from_str(&m, bstr0(maps[i]));
+        mp_chmap_sel_add_map(&s, &m);
+    }
+
+    struct mp_chmap c;
+    mp_chmap_from_str(&c, bstr0("3.1"));
+    assert_true(mp_chmap_sel_fallback(&s, &c));
+    assert_string_equal(mp_chmap_to_str(&c), "5.1");
+}
+
+static void test_mp_chmap_sel_fallback_use_replacements(void **state) {
+    struct mp_chmap a;
+    struct mp_chmap b;
+    struct mp_chmap_sel s = {0};
+
+    mp_chmap_from_str(&a, bstr0("7.1(rear)"));
+    mp_chmap_from_str(&b, bstr0("5.1"));
+
+    mp_chmap_sel_add_map(&s, &a);
+    assert_true(mp_chmap_sel_fallback(&s, &b));
+    assert_string_equal(mp_chmap_to_str(&b), "7.1(rear)");
+}
+
+static void test_mp_chmap_sel_fallback_reject_unknown(void **state) {
+    struct mp_chmap a;
+    struct mp_chmap b;
+    struct mp_chmap_sel s = {0};
+
+    a.num = 2;
+    a.speaker[0] = MP_SPEAKER_ID_UNKNOWN0;
+    a.speaker[1] = MP_SPEAKER_ID_UNKNOWN0 + 1;
+
+    mp_chmap_from_str(&b, bstr0("5.1"));
+
+    mp_chmap_sel_add_map(&s, &a);
+    assert_false(mp_chmap_sel_fallback(&s, &b));
+    assert_string_equal(mp_chmap_to_str(&b), "5.1");
+}
+
+static void test_mp_chmap_sel_fallback_works_on_alsa_chmaps(void **state) {
+    struct mp_chmap a;
+    struct mp_chmap b;
+    struct mp_chmap_sel s = {0};
+
+    mp_chmap_from_str(&a, bstr0("7.1(alsa)"));
+    mp_chmap_from_str(&b, bstr0("5.1"));
+
+    mp_chmap_sel_add_map(&s, &a);
+    assert_true(mp_chmap_sel_fallback(&s, &b));
+    assert_string_equal(mp_chmap_to_str(&b), "7.1(alsa)");
+}
+
+static void test_mp_chmap_sel_fallback_mono_to_stereo(void **state) {
+    struct mp_chmap a;
+    struct mp_chmap b;
+    struct mp_chmap c;
+    struct mp_chmap_sel s = {0};
+
+    mp_chmap_from_str(&a, bstr0("stereo"));
+    mp_chmap_from_str(&b, bstr0("5.1"));
+    mp_chmap_from_str(&c, bstr0("mono"));
+
+    mp_chmap_sel_add_map(&s, &a);
+    mp_chmap_sel_add_map(&s, &b);
+    assert_true(mp_chmap_sel_fallback(&s, &c));
+    assert_string_equal(mp_chmap_to_str(&c), "stereo");
+}
+
+static void test_mp_chmap_sel_fallback_stereo_to_stereo(void **state) {
+    struct mp_chmap a;
+    struct mp_chmap b;
+    struct mp_chmap c;
+    struct mp_chmap_sel s = {0};
+
+    mp_chmap_from_str(&a, bstr0("stereo"));
+    mp_chmap_from_str(&b, bstr0("5.1"));
+    mp_chmap_from_str(&c, bstr0("stereo"));
+
+    mp_chmap_sel_add_map(&s, &a);
+    mp_chmap_sel_add_map(&s, &b);
+    assert_true(mp_chmap_sel_fallback(&s, &c));
+    assert_string_equal(mp_chmap_to_str(&c), "stereo");
+}
+
+int main(void) {
+    const UnitTest tests[] = {
+        unit_test(test_mp_chmap_sel_fallback_upmix),
+        unit_test(test_mp_chmap_sel_fallback_downmix),
+        unit_test(test_mp_chmap_sel_fallback_incompatible),
+        unit_test(test_mp_chmap_sel_fallback_prefer_compatible),
+        unit_test(test_mp_chmap_sel_fallback_prefer_closest_upmix),
+        unit_test(test_mp_chmap_sel_fallback_use_replacements),
+        unit_test(test_mp_chmap_sel_fallback_reject_unknown),
+        unit_test(test_mp_chmap_sel_fallback_works_on_alsa_chmaps),
+        unit_test(test_mp_chmap_sel_fallback_mono_to_stereo),
+        unit_test(test_mp_chmap_sel_fallback_stereo_to_stereo),
+    };
+    return run_tests(tests);
+}
diff --git a/test/test_helpers.h b/test/test_helpers.h
new file mode 100644
index 0000000000..3dfe08fdbe
--- /dev/null
+++ b/test/test_helpers.h
@@ -0,0 +1,11 @@
+#ifndef MP_TESTS_H
+#define MP_TESTS_H
+
+#include <stdarg.h>
+#include <stddef.h>
+#include <setjmp.h>
+#include <cmocka.h>
+
+#include <stdio.h>
+
+#endif
diff --git a/wscript b/wscript
index 8b752fa607..20d8bbed99 100644
--- a/wscript
+++ b/wscript
@@ -84,6 +84,10 @@ build_options = [
         'desc': 'inline assembly (currently without effect)',
         'default': 'enable',
         'func': check_true,
+    }, {
+        'name': '--test',
+        'desc': 'test suite (using cmocka)',
+        'func': check_pkg_config('cmocka >= 0.4.1'),
     }
 ]
 
diff --git a/wscript_build.py b/wscript_build.py
index 58925444cf..6c6b6bd3ae 100644
--- a/wscript_build.py
+++ b/wscript_build.py
@@ -33,6 +33,10 @@ def _build_pdf(ctx):
 
     _add_rst_manual_dependencies(ctx)
 
+def _all_includes(ctx):
+    return [ctx.bldnode.abspath(), ctx.srcnode.abspath()] + \
+            ctx.dependencies_includes()
+
 def build(ctx):
     ctx.load('waf_customizations')
     ctx.load('generators.sources')
@@ -415,13 +419,21 @@ def build(ctx):
                 ctx.path.find_node('osdep/mpv.rc'),
                 ctx.path.find_node(node))
 
+    if ctx.dependency_satisfied('cplayer') or ctx.dependency_satisfied('test'):
+        ctx(
+            target       = "objects",
+            source       = ctx.filtered_sources(sources),
+            use          = ctx.dependencies_use(),
+            includes     = _all_includes(ctx),
+            features     = "c",
+        )
+
     if ctx.dependency_satisfied('cplayer'):
         ctx(
             target       = "mpv",
-            source       = ctx.filtered_sources(sources) + ["player/main_fn.c"],
-            use          = ctx.dependencies_use(),
-            includes     = [ctx.bldnode.abspath(), ctx.srcnode.abspath()] + \
-                           ctx.dependencies_includes(),
+            source       = "player/main_fn.c",
+            use          = 'objects',
+            includes     = _all_includes(ctx),
             features     = "c cprogram",
             install_path = ctx.env.BINDIR
         )
@@ -443,6 +455,15 @@ def build(ctx):
             wrapctx.env.CFLAGS = wrapflags
             wrapctx.env.LAST_LINKFLAGS = wrapflags
 
+    if ctx.dependency_satisfied('test'):
+        for test in ctx.path.ant_glob("test/*.c"):
+            ctx(
+                target   = os.path.splitext(test.srcpath())[0],
+                source   = test.srcpath(),
+                use      = "objects",
+                includes = _all_includes(ctx),
+                features = "c cprogram",
+            )
 
     build_shared = ctx.dependency_satisfied('libmpv-shared')
     build_static = ctx.dependency_satisfied('libmpv-static')