drawing: tokenise vector drawings like VSFilter

Our old code deviated from VSFilter in many ways, though
the tokenisation differences only affected nonsensical
or technically invalid drawing command sequences.

While it is possible to retrofit the existing tokenisation loop
to emulate VSFilter’s logic, the result is not as readable as just
directly using greedy point aggregation and a search for the next
valid command similar to VSFilter.
Unfortunately, this has the downside of making the individual
compatibility changes/issues less visible in the diff. Instead
they are spelled out below:

 - VSFilter ignores invalid commands together with their coordinates.
   Prior to this, libass ignored invalid commands itself but appended
   their coordinates to the preceding valid command. This was even
   intentionally exploited to (not-)implement p, resulting in different
   behaviour if p was following something other than s.
 - VSFilter will accept n as the first node
   if an _invalid_ m command appeared before
 - VSFilter drops points from b which are not part of a triplet.
 - VSFilter ignores s commands with less than three points.
 - VSFilter ignores p commands if there aren’t at least 3 nodes yet.

(The last one strictly speaking only holds for xy-VSFilter and
 MPC-HC ISR — but guliverkli2 VSFilter just crashes on such input)

Furthermore, until now libass recognised q for conic bezier in the
tokeniser. This does not exist in VSFilters and was also never
implemented in libass’ token-to-outline parser.

Other than the lack of distinction between spline start and extension
nodes (which also requires support in the parser) our tokenisation
result should now exactly match modern VSFilters.

2 files changed, 179 insertions, 75 deletions

diff --git a/libass/ass_drawing.c b/libass/ass_drawing.c
index 9343425..dd26601 100644
--- a/libass/ass_drawing.c
+++ b/libass/ass_drawing.c
@@ -43,93 +43,199 @@ static bool token_check_values(ASS_DrawingToken *token, int i, ASS_TokenType typ
     return true;
 }
 
+static inline void add_node(ASS_DrawingToken **tail, ASS_TokenType type, ASS_Vector point)
+{
+    assert(tail && *tail);
+
+    ASS_DrawingToken *new_tail = malloc(sizeof(**tail));
+    if (!new_tail)
+        return;
+    (*tail)->next = new_tail;
+    new_tail->prev = *tail;
+    new_tail->next = NULL;
+    new_tail->type = type;
+    new_tail->point = point;
+    *tail = new_tail;
+}
+
+static inline bool get_point(const char **str, ASS_Vector *point)
+{
+    double x, y;
+    if (!mystrtod((char **) str, &x) || !mystrtod((char **) str, &y))
+        return false;
+    *point = (ASS_Vector) {double_to_d6(x), double_to_d6(y)};
+    return true;
+}
+
+
+/**
+ * Parses and advances the string for exactly 3 points.
+ * If the string contains fewer than 3 points,
+ * any initial matching coordinates are still consumed.
+ * \return whether three valid points were added
+ */
+static bool add_3_points(const char **str, ASS_DrawingToken **tail, ASS_TokenType type)
+{
+    ASS_Vector buf[3];
+
+    if (!*str)
+        return false;
+
+    bool valid = get_point(str, buf + 0);
+    valid = valid && get_point(str, buf + 1);
+    valid = valid && get_point(str, buf + 2);
+
+    if (!valid)
+        return false;
+
+    add_node(tail, type, buf[0]);
+    add_node(tail, type, buf[1]);
+    add_node(tail, type, buf[2]);
+
+    return true;
+}
+
+/*
+ * Parses and advances the string while it matches points.
+ * Each set of batch_size points will be turned into tokens and appended to tail.
+ * Partial matches (i.e. an insufficient amount of coordinates) are still consumed.
+ * \return count of added points
+ */
+static size_t add_many_points(const char **str, ASS_DrawingToken **tail,
+                              ASS_TokenType type, size_t batch_size)
+{
+    ASS_Vector buf[3];
+    size_t max_buf = sizeof(buf) / sizeof(*buf);
+    assert(batch_size <= max_buf);
+
+    if (!*str)
+        return 0;
+
+    size_t count_total = 0;
+    size_t count_batch = 0;
+    while (**str) {
+        ASS_Vector point;
+        if (!get_point(str, &point))
+            break;
+        buf[count_batch] = point;
+        count_total++;
+        count_batch++;
+
+        if (count_batch != batch_size)
+            continue;
+
+        for (size_t i = 0; i < count_batch; i++)
+            add_node(tail, type, buf[i]);
+        count_batch = 0;
+    }
+
+    return count_total - count_batch;
+}
+
+static inline bool add_root_node(ASS_DrawingToken **root, ASS_DrawingToken **tail,
+                                 size_t *points, ASS_Vector point, ASS_TokenType type)
+{
+    *root = *tail = calloc(1, sizeof(ASS_DrawingToken));
+    if (!*root)
+        return false;
+    (*root)->point = point;
+    (*root)->type = type;
+    *points = 1;
+    return true;
+}
+
 /*
  * \brief Tokenize a drawing string into a list of ASS_DrawingToken
  * This also expands points for closing b-splines
  */
 static ASS_DrawingToken *drawing_tokenize(const char *str)
 {
-    char *p = (char *) str;
-    ASS_TokenType type = TOKEN_INVALID;
-    int is_set = 0;
-    double val;
-    ASS_Vector point = {0, 0};
-
+    const char *p = str;
     ASS_DrawingToken *root = NULL, *tail = NULL, *spline_start = NULL;
+    size_t points = 0;
+    bool m_seen = false;
 
     while (p && *p) {
-        int got_coord = 0;
-        if (*p == 'c' && spline_start) {
-            // Close b-splines: add the first three points of the b-spline
-            // back to the end
-            if (token_check_values(spline_start->next, 2, TOKEN_B_SPLINE)) {
-                for (int i = 0; i < 3; i++) {
-                    tail->next = calloc(1, sizeof(ASS_DrawingToken));
-                    tail->next->prev = tail;
-                    tail = tail->next;
-                    tail->type = TOKEN_B_SPLINE;
-                    tail->point = spline_start->point;
-                    spline_start = spline_start->next;
-                }
-                spline_start = NULL;
+        char cmd = *p;
+        p++;
+        /* VSFilter compat:
+         * In guliverkli(2) VSFilter all drawings
+         * whose first known (but potentially invalid) command isn't m are rejected.
+         * xy-VSF and MPC-HC ISR later relaxed this (possibly inadvertenly),
+         * such that all known commands but n are ignored if there was no prior node yet.
+         * If an invalid m preceded n, the latter becomes the root node, otherwise
+         * if n comes before any other not-ignored command the entire drawing is rejected.
+         * 'p' is further restricted and ignored unless there are already >= 3 nodes.
+         * This relaxation was a byproduct of a fix for crashing on drawings
+         * containing commands with fewer preceding nodes than expected.
+         */
+        switch (cmd) {
+        case 'm':
+            m_seen = true;
+            if (!root) {
+                ASS_Vector point;
+                if (!get_point(&p, &point))
+                    continue;
+                if (!add_root_node(&root, &tail, &points, point, TOKEN_MOVE))
+                    continue;
             }
-        } else if (!is_set && mystrtod(&p, &val)) {
-            point.x = double_to_d6(val);
-            is_set = 1;
-            got_coord = 1;
-            p--;
-        } else if (is_set == 1 && mystrtod(&p, &val)) {
-            point.y = double_to_d6(val);
-            is_set = 2;
-            got_coord = 1;
-            p--;
-        } else if (*p == 'm')
-            type = TOKEN_MOVE;
-        else if (*p == 'n')
-            type = TOKEN_MOVE_NC;
-        else if (*p == 'l')
-            type = TOKEN_LINE;
-        else if (*p == 'b')
-            type = TOKEN_CUBIC_BEZIER;
-        else if (*p == 'q')
-            type = TOKEN_CONIC_BEZIER;
-        else if (*p == 's')
-            type = TOKEN_B_SPLINE;
-        // We're simply ignoring TOKEN_EXTEND_B_SPLINE here.
-        // This is not harmful at all, since it can be ommitted with
-        // similar result (the spline is extended anyway).
-
-        // Ignore the odd extra value, it makes no sense.
-        if (!got_coord)
-            is_set = 0;
-
-        if (type != TOKEN_INVALID && is_set == 2) {
-            if (root) {
-                tail->next = calloc(1, sizeof(ASS_DrawingToken));
-                tail->next->prev = tail;
-                tail = tail->next;
-            } else {
-                /* VSFilter compat:
-                 * In guliverkli(2) VSFilter all drawings
-                 * whose first valid command isn't m are rejected.
-                 * xy-VSF and MPC-HC ISR this was (possibly inadvertenly) later relaxed,
-                 * such that all valid commands but n are ignored if there was no m yet.
-                 */
-                if (type == TOKEN_MOVE_NC) {
+            points += add_many_points(&p, &tail, TOKEN_MOVE, 1);
+            break;
+        case 'n':
+            if (!root) {
+                ASS_Vector point;
+                if (!get_point(&p, &point))
+                    continue;
+                if (!m_seen)
                     return NULL;
-                } else if (type != TOKEN_MOVE) {
-                    p++;
+                if (!add_root_node(&root, &tail, &points, point, TOKEN_MOVE_NC))
                     continue;
-                }
-                root = tail = calloc(1, sizeof(ASS_DrawingToken));
             }
-            tail->type = type;
-            tail->point = point;
-            is_set = 0;
-            if (type == TOKEN_B_SPLINE && !spline_start)
-                spline_start = tail->prev;
+            points += add_many_points(&p, &tail, TOKEN_MOVE_NC, 1);
+            break;
+        case 'l':
+            if (!root)
+                continue;
+            points += add_many_points(&p, &tail, TOKEN_LINE, 1);
+            break;
+        case 'b':
+            if (!root)
+                continue;
+            points += add_many_points(&p, &tail, TOKEN_CUBIC_BEZIER, 3);
+            break;
+        case 's':
+            if (!root)
+                continue;
+            // Only the initial 3 points are TOKEN_B_SPLINE,
+            // all following ones are TOKEN_EXTEND_SPLINE
+            spline_start = tail;
+            if (!add_3_points(&p, &tail, TOKEN_B_SPLINE)) {
+                spline_start = NULL;
+                continue;
+            }
+            points += 3;
+            //-fallthrough
+        case 'p':
+            if (points < 3)
+                continue;
+            // XXX: use TOKEN_EXTEND_SPLINE
+            points += add_many_points(&p, &tail, TOKEN_B_SPLINE, 1);
+            break;
+        case 'c':
+            if (!spline_start)
+                continue;
+            // Close b-splines: add the first three points of the b-spline back to the end
+            for (int i = 0; i < 3; i++) {
+                // XXX: use TOKEN_EXTEND_SPLINE
+                add_node(&tail, TOKEN_B_SPLINE, spline_start->point);
+                spline_start = spline_start->next;
+            }
+            spline_start = NULL;
+            break;
+        default:
+            // Ignore, just search for next valid command
+            break;
         }
-        p++;
     }
 
     return root;
diff --git a/libass/ass_drawing.h b/libass/ass_drawing.h
index 2c5e921..a99470a 100644
--- a/libass/ass_drawing.h
+++ b/libass/ass_drawing.h
@@ -24,12 +24,10 @@
 #include "ass_bitmap.h"
 
 typedef enum {
-    TOKEN_INVALID,
     TOKEN_MOVE,
     TOKEN_MOVE_NC,
     TOKEN_LINE,
     TOKEN_CUBIC_BEZIER,
-    TOKEN_CONIC_BEZIER,
     TOKEN_B_SPLINE,
     TOKEN_EXTEND_SPLINE,
     TOKEN_CLOSE