+ /* We never spell simple intervals as inversions. */
+ if (num_degrees == 2 && inversion > 0)
+ return 0;
+
+ for (i = 0; i < num_degrees; i++) {
+ /* The num_degrees is in the addition just to ensure all
+ * inputs to the modulus operator remain positive. */
+ int index = (i + num_degrees - inversion) % num_degrees;
+
+ /* Again, adding a 12 to keep things positive. */
+ relative_pitches[index] =
+ (12 +
+ _modified_degree_to_half_steps (°rees[i]) -
+ _modified_degree_to_half_steps (°rees[inversion])) % 12;
+
+ }
+
+ for (i = 0; i < num_pitches; i++)
+ if (pitches[i].relative_pitch != relative_pitches[i])
+ return 0;
+
+ root_index = (num_pitches - inversion) % num_pitches;
+ *root = pitches[root_index].pitch;
+
+ return 1;
+}
+
+typedef struct chord_signature
+{
+ int num_degrees;
+ modified_degree_t degrees[MAX_DEGREES];
+ const char *name;
+} chord_signature_t;
+
+/* XXX: The superscript rise value should be relative to the current
+ * font size. Best would be for pango to support this. See:
+ *
+ * https://bugzilla.gnome.org/show_bug.cgi?id=708780
+ *
+ * For now, these are emipirically-derived values that look reasonable
+ * at the default size that score.c is using to draw the staff. If the
+ * user scales the staff up or down then these will look wrong.
+ */
+
+#define SUP "<span font='33' rise='30000'>"
+#define PUS "</span>"
+
+chord_signature_t signatures[] = {
+ /* Octave */
+ { 1, {{1, 0}}, "P8" },
+
+ /* Intervals */
+ { 2, {{1, 0}, {2, -1}}, "m2" },
+ { 2, {{1, 0}, {2, 0}}, "M2" },
+ { 2, {{1, 0}, {3, -1}}, "m3" },
+ { 2, {{1, 0}, {3, 0}}, "M3" },
+ { 2, {{1, 0}, {4, 0}}, "P4" },
+ { 2, {{1, 0}, {5, -1}}, "Tri-tone" },
+ { 2, {{1, 0}, {5, 0}}, "P5" },
+ { 2, {{1, 0}, {6, -1}}, "m6" },
+ { 2, {{1, 0}, {6, 0}}, "M6" },
+ { 2, {{1, 0}, {7, -1}}, "m7" },
+ { 2, {{1, 0}, {7, 0}}, "M7" },
+
+ /* Triads */
+ { 3, {{1, 0}, {4, 0}, {5, 0}}, "sus" },
+ { 3, {{1, 0}, {3, 0}, {5, +1}}, SUP "+" PUS },
+ { 3, {{1, 0}, {3, 0}, {5, 0}}, "" },
+ { 3, {{1, 0}, {3, -1}, {5, 0}}, "m" },
+ { 3, {{1, 0}, {3, -1}, {5, -1}}, "°" },
+ { 3, {{1, 0}, {2, 0}, {5, 0}}, "msus2" },
+
+ /* Seventh chords with no 3rd */
+ { 3, {{1, 0}, {5, +1}, {7, 0}}, SUP "+M7" PUS },
+ { 3, {{1, 0}, {5, +1}, {7, -1}}, SUP "+7" PUS },
+ { 3, {{1, 0}, {5, 0}, {7, 0}}, "M7" },
+ { 3, {{1, 0}, {5, 0}, {7, -1}}, "7" },
+ { 3, {{1, 0}, {5, -1}, {7, -1}}, "7♭5" },
+
+ /* Seventh chords with no 5th */
+ { 3, {{1, 0}, {4, 0}, {7, 0}}, "M7sus" },
+ { 3, {{1, 0}, {4, 0}, {7, -1}}, "7sus" },
+ { 3, {{1, 0}, {3, 0}, {7, 0}}, "M7" },
+ { 3, {{1, 0}, {3, 0}, {7, -1}}, "7" },
+ { 3, {{1, 0}, {3, -1}, {7, 0}}, "m" SUP "M7" PUS },
+ { 3, {{1, 0}, {3, -1}, {7, -1}}, "m7" },
+ { 3, {{1, 0}, {2, 0}, {7, 0}}, "m" SUP "M7" PUS "sus2" },
+ { 3, {{1, 0}, {2, 0}, {7, -1}}, "m7sus2" },
+
+ /* Sixth chords */
+ { 4, {{1, 0}, {4, 0}, {5, 0}, {6, 0}}, "6sus" },
+ { 4, {{1, 0}, {3, 0}, {5, 0}, {6, 0}}, "6" }, /* Ambiguous with m7 */
+ { 4, {{1, 0}, {3, -1}, {5, 0}, {6, 0}}, "m6" },
+ { 4, {{1, 0}, {2, 0}, {5, 0}, {6, 0}}, "m6sus2" },
+
+ /* Seventh chords */
+ { 4, {{1, 0}, {4, 0}, {5, +1}, {7, 0}}, SUP "+M7" PUS "sus" },
+ { 4, {{1, 0}, {4, 0}, {5, +1}, {7, -1}}, SUP "+7" PUS "sus" },
+ { 4, {{1, 0}, {4, 0}, {5, 0}, {7, 0}}, "M7sus" },
+ { 4, {{1, 0}, {4, 0}, {5, 0}, {7, -1}}, "7sus" },
+ { 4, {{1, 0}, {4, 0}, {5, -1}, {7, -1}}, "7♭5sus" },
+ { 4, {{1, 0}, {3, 0}, {5, +1}, {7, 0}}, SUP "+M7" PUS },
+ { 4, {{1, 0}, {3, 0}, {5, +1}, {7, -1}}, SUP "+7" PUS },
+ { 4, {{1, 0}, {3, 0}, {5, 0}, {7, 0}}, "M7" },
+ { 4, {{1, 0}, {3, 0}, {5, 0}, {7, -1}}, "7" },
+ { 4, {{1, 0}, {3, 0}, {5, -1}, {7, -1}}, "7♭5" },
+ { 4, {{1, 0}, {3, -1}, {5, 0}, {7, 0}}, "m" SUP "M7" PUS },
+ { 4, {{1, 0}, {3, -1}, {5, 0}, {7, -1}}, "m7" },
+ { 4, {{1, 0}, {3, -1}, {5, -1}, {7, 0}}, "°" SUP "M7" PUS },
+ { 4, {{1, 0}, {3, -1}, {5, -1}, {7, -1}}, "𝆩" SUP "7" PUS },
+ { 4, {{1, 0}, {3, -1}, {5, -1}, {7, -2}}, "°" SUP "7" PUS },
+ { 4, {{1, 0}, {2, 0}, {5, 0}, {7, 0}}, "m" SUP "M7" PUS "sus2" },
+ { 4, {{1, 0}, {2, 0}, {5, 0}, {7, -1}}, "m7sus2" },
+ { 4, {{1, 0}, {2, 0}, {5, -1}, {7, 0}}, "°" SUP "M7" PUS "sus2" },
+ { 4, {{1, 0}, {2, 0}, {5, -1}, {7, -1}}, "𝆩" SUP "7" PUS "sus2" },
+ { 4, {{1, 0}, {2, 0}, {5, -1}, {7, -2}}, "°" SUP "7" PUS "sus2" }, /* Ambiguous with 7 */
+
+ /* The sorting for chords with degree higher than 9 is funny
+ * to keep the array in degree order after reducing each
+ * degree to an actual scale degree, (9 -> 2, 11 -> 4, 13 ->
+ * 6) */
+
+ /* Ninth chords voiced with no 5th */
+ { 4, {{1, 0}, {9, 0}, {4, 0}, {7, 0}}, "M9sus" },
+ { 4, {{1, 0}, {9, 0}, {4, 0}, {7, -1}}, "9sus" },
+ { 4, {{1, 0}, {9, 0}, {3, 0}, {7, 0}}, "M9" },
+ { 4, {{1, 0}, {9, 0}, {3, 0}, {7, -1}}, "9" },
+ { 4, {{1, 0}, {9, 0}, {3, -1}, {7, 0}}, "m" SUP "M9" PUS },
+ { 4, {{1, 0}, {9, 0}, {3, -1}, {7, -1}}, "m9" },
+ { 4, {{1, 0}, {9, -1}, {3, -1}, {7, -1}}, "m♭9" },
+ { 4, {{1, 0}, {9, 0}, {3, -1}, {6, 0}}, "m6/9" },
+ { 4, {{1, 0}, {9, -1}, {3, -1}, {6, 0}}, "m6/♭9" },
+
+ /* Sixth plus 9 */
+ { 5, {{1, 0}, {9, 0}, {3, 0}, {5, 0}, {6, 0}}, "6/9" },
+ { 5, {{1, 0}, {9, 0}, {3, -1}, {5, 0}, {6, 0}}, "m6/9" },
+ { 5, {{1, 0}, {9, -1}, {3, -1}, {5, 0}, {6, 0}}, "m6/♭9" },
+
+ /* Seventh plus altered 9 */
+ { 5, {{1, 0}, {9, +1}, {3, 0}, {5, 0}, {7, -1}}, "7♯9" },
+ { 5, {{1, 0}, {9, -1}, {3, 0}, {5, 0}, {7, -1}}, "7♭9" },
+ { 5, {{1, 0}, {9, +1}, {3, 0}, {5, -1}, {7, -1}}, "7♭5♯9" },
+ { 5, {{1, 0}, {9, -1}, {3, 0}, {5, -1}, {7, -1}}, "7♭5♭9" },
+
+ /* Ninth chords */
+ { 5, {{1, 0}, {9, 0}, {4, 0}, {5, +1}, {7, 0}}, SUP "+M9" PUS "sus" },
+ { 5, {{1, 0}, {9, 0}, {4, 0}, {5, +1}, {7, -1}}, SUP "+9" PUS "sus" },
+ { 5, {{1, 0}, {9, 0}, {4, 0}, {5, 0}, {7, 0}}, "M9sus" },
+ { 5, {{1, 0}, {9, 0}, {4, 0}, {5, 0}, {7, -1}}, "9sus" },
+ { 5, {{1, 0}, {9, 0}, {3, 0}, {5, +1}, {7, 0}}, SUP "+M9" PUS },
+ { 5, {{1, 0}, {9, 0}, {3, 0}, {5, +1}, {7, -1}}, SUP "+9" PUS },
+ { 5, {{1, 0}, {9, 0}, {3, 0}, {5, 0}, {7, 0}}, "M9" },
+ { 5, {{1, 0}, {9, 0}, {3, 0}, {5, 0}, {7, -1}}, "9" },
+ { 5, {{1, 0}, {9, 0}, {3, -1}, {5, 0}, {7, 0}}, "m" SUP "M9" PUS },
+ { 5, {{1, 0}, {9, 0}, {3, -1}, {5, 0}, {7, -1}}, "m9" },
+ { 5, {{1, 0}, {9, -1}, {3, -1}, {5, 0}, {7, -1}}, "m♭9" },
+ { 5, {{1, 0}, {9, 0}, {3, 0}, {5, -1}, {7, 0}}, "M9" SUP "♭5" PUS },
+ { 5, {{1, 0}, {9, 0}, {3, 0}, {5, -1}, {7, -1}}, "9" SUP "♭5" PUS },
+ { 5, {{1, 0}, {9, 0}, {3, -1}, {5, -1}, {7, 0}}, "m" SUP "M9♭5" PUS },
+ { 5, {{1, 0}, {9, 0}, {3, -1}, {5, -1}, {7, -1}}, "𝆩" SUP "9" PUS },
+ { 5, {{1, 0}, {9, -1}, {3, -1}, {5, -1}, {7, -1}}, "𝆩" SUP "♭9" PUS },
+ { 5, {{1, 0}, {9, 0}, {3, -1}, {5, -1}, {7, -2}}, "°" SUP "9" PUS },
+ { 5, {{1, 0}, {9, -1}, {3, -1}, {5, -1}, {7, -2}}, "°" SUP "♭9" PUS },
+
+ /* Eleventh chords */
+ { 6, {{1, 0}, {9, 0}, {3, 0}, {11, 0}, {5, +1}, {7, 0}}, SUP "+M11" PUS },
+ { 6, {{1, 0}, {9, 0}, {3, 0}, {11, 0}, {5, +1}, {7, -1}}, SUP "+11" PUS },
+ { 6, {{1, 0}, {9, 0}, {3, 0}, {11, 0}, {5, 0}, {7, 0}}, "M11" },
+ { 6, {{1, 0}, {9, 0}, {3, 0}, {11, 0}, {5, 0}, {7, -1}}, "11" },
+ { 6, {{1, 0}, {9, 0}, {3, -1}, {11, 0}, {5, 0}, {7, 0}}, "m" SUP "M11" PUS },
+ { 6, {{1, 0}, {9, 0}, {3, -1}, {11, 0}, {5, 0}, {7, -1}}, "m11" },
+ { 6, {{1, 0}, {9, -1}, {3, -1}, {11, 0}, {5, -1}, {7, -1}}, "𝆩" SUP "11" PUS },
+ { 6, {{1, 0}, {9, -1}, {3, -1}, {11, -1}, {5, -1}, {7, -2}}, "°" SUP "11" PUS }
+};
+
+static void
+_spell_chord_by_signature (pitch_group_t *chord,
+ chord_signature_t *signature,
+ pitch_t root)
+{
+ int i, degree, note_half_steps, degree_half_steps;
+
+ for (i = 0; i < chord->num_pitches; i++) {
+ note_half_steps = pitch_from_root_in_half_steps (chord->pitches[i],
+ root);
+ for (degree = 0; degree < signature->num_degrees; degree++) {
+ degree_half_steps = _modified_degree_to_half_steps (&signature->degrees[degree]);
+ if (note_half_steps == degree_half_steps) {
+ chord->pitches[i] = pitch_spell_as_degree (chord->pitches[i],
+ root,
+ signature->degrees[degree].degree);
+ break;
+ }
+ }
+ if (note_half_steps != degree_half_steps) {
+ fprintf (stderr, "Internal error: Chord and degree mis-match\n");
+ exit (1);
+ }
+ }
+}
+
+static void
+_analyze_chord (pitch_group_t *chord,
+ chord_signature_t **signature_ret,
+ pitch_t **root_ret)
+{
+ void *local = talloc_new (NULL);
+ analyzed_pitch_t *pitches;
+ int i, j, num_pitches;
+ int bass_pitch, inversion;
+ pitch_t root;
+ chord_signature_t *match = NULL;
+
+ /* Default to no-match for any early return */
+ *signature_ret = NULL;
+ *root_ret = NULL;
+
+ num_pitches = chord->num_pitches;
+
+ if (chord->num_pitches <= 1)
+ goto DONE;
+
+ pitches = talloc_array (local, analyzed_pitch_t, num_pitches);
+ if (pitches == NULL)
+ goto DONE;
+
+ for (i = 0; i < num_pitches; i++) {
+ pitch_t pitch = chord->pitches[i];
+ pitches[i].pitch = pitch;
+ pitches[i].midi_pitch = pitch_to_midi (pitch);
+ /* Relative pitch will be filled in after sorting. */
+ pitches[i].relative_pitch = 0;
+ }
+
+ /* First, sort by midi pitch to find the bass note. */
+ qsort (pitches, num_pitches, sizeof (analyzed_pitch_t),
+ _compare_analyzed_pitch_by_midi_pitch);
+
+ bass_pitch = pitches[0].midi_pitch;
+
+ /* With the bass note identified, we can find all relative pitches. */
+ for (i = 0; i < num_pitches; i++) {
+ pitches[i].relative_pitch = pitches[i].midi_pitch - bass_pitch;
+ while (pitches[i].relative_pitch >= 12)
+ pitches[i].relative_pitch -= 12;
+ }
+
+ /* Now, sort again by relative pitch. */
+ qsort (pitches, num_pitches, sizeof (analyzed_pitch_t),
+ _compare_analyzed_pitch_by_relative_pitch);
+
+ /* Finally, eliminate all duplicate notes. */
+ for (i = 0; i < num_pitches - 1; i++) {
+ if (pitches[i+1].relative_pitch == pitches[i].relative_pitch) {
+ j = i+1;
+ while (j < num_pitches &&
+ pitches[j].relative_pitch == pitches[i].relative_pitch)
+ {
+ j++;
+ }
+ /* The loop incremented j one past the last
+ * duplicate. Decrement so that it points to the
+ * last duplicate (and is guaranteed to not exceed
+ * the array bounds).*/
+ j--;
+
+ if (j < num_pitches - 1) {
+ memmove (&pitches[i+1], &pitches[j+1],
+ (num_pitches - j) * sizeof (analyzed_pitch_t));
+ }
+
+ num_pitches -= (j - i);
+ }
+ }
+
+ for (inversion = 0; inversion < 4; inversion++) {
+ for (i = 0; i < ARRAY_SIZE (signatures); i++) {
+ if (_chord_signature_matches (pitches, num_pitches,
+ signatures[i].degrees,
+ signatures[i].num_degrees,
+ inversion, &root))
+ {
+ match = &signatures[i];
+ goto HAVE_MATCH;
+ }
+ }
+ }
+HAVE_MATCH:
+
+ if (match) {
+ *signature_ret = match;
+ for (i = 0; i < chord->num_pitches; i++) {
+ if (chord->pitches[i] == root) {
+ *root_ret = &chord->pitches[i];
+ break;
+ }
+ }
+ }
+
+DONE:
+ talloc_free (local);
+}
+
+static void
+pitch_group_init (void *ctx, pitch_group_t *group)
+{
+ group->ctx = ctx;
+ group->pitches = NULL;
+ group->size = 0;
+ group->num_pitches = 0;
+}
+
+static void
+pitch_group_add_pitch (pitch_group_t *group, pitch_t pitch)
+{
+ int i;
+
+ /* Do nothing if pitch is already in group. */
+ for (i = 0; i < group->num_pitches; i++)
+ if (group->pitches[i] == pitch)
+ return;
+
+ group->num_pitches++;
+
+ if (group->num_pitches > group->size) {
+ group->size++;
+ group->pitches = talloc_realloc (group->ctx, group->pitches,
+ pitch_t, group->size);
+
+ if (group->pitches == NULL) {
+ fprintf (stderr, "Out of memory.\n");
+ exit (1);
+ }
+ }
+
+ group->pitches[group->num_pitches - 1] = pitch;
+}
+
+static void
+pitch_group_remove_pitch_at (pitch_group_t *group, int i)
+{
+ if (i > group->num_pitches) {
+ fprintf (stderr, "Internal error: Cannot remove pitch %d from group with only %d %s\n",
+ i, group->num_pitches,
+ group->num_pitches == 1 ? "pitch" : "pitches");