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.

4 files changed, 123 insertions, 0 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);