Add WRAP_UNICODE feature

Setting this feature allows breaking lines according to the Unicode
Line Breaking Algorithm and is incompatible with VSFilter.
This is useful for non-ASS renderers utilising libass, especially for
languages typically not using ASCII-spaces to separate words, but
also to correctly break on punctuation even in languages that do. It
does not allow breaking words apart, so line overflow might still occur.
For this to work a new optional dependency on libunibrak is added.
We assume FriBidi's and libunibreak's utf32/glyph type match.

This is based on an earlier patch by GitHub user siikamiika.

6 files changed, 100 insertions, 16 deletions

diff --git a/configure.ac b/configure.ac
index 42b5a81..543a44e 100644
--- a/configure.ac
+++ b/configure.ac
@@ -30,6 +30,8 @@ AC_ARG_ENABLE([directwrite], AS_HELP_STRING([--disable-directwrite],
     [disable DirectWrite support (Windows only) @<:@default=check@:>@]))
 AC_ARG_ENABLE([coretext], AS_HELP_STRING([--disable-coretext],
     [disable CoreText support (OSX only) @<:@default=check@:>@]))
+AC_ARG_ENABLE([libunibreak], AS_HELP_STRING([--disable-libunibreak],
+    [disable libunibreak support @<:@default=check@:>@]))
 AC_ARG_ENABLE([require-system-font-provider], AS_HELP_STRING([--disable-require-system-font-provider],
     [allow compilation even if no system font provider was found @<:@default=enabled:>@]))
 AC_ARG_ENABLE([asm], AS_HELP_STRING([--disable-asm],
@@ -104,6 +106,19 @@ AS_IF([test "x$enable_test" = xyes || test "x$enable_compare" = xyes], [
     ])
 ])
 
+AS_IF([test "x$enable_libunibreak" != xno], [
+    PKG_CHECK_MODULES([LIBUNIBREAK], [libunibreak >= 1.1], [
+        pkg_requires="libunibreak >= 1.1, ${pkg_requires}"
+        CFLAGS="$CFLAGS $LIBUNIBREAK_CFLAGS"
+        LIBS="$LIBS $LIBUNIBREAK_LIBS"
+        AC_DEFINE(CONFIG_UNIBREAK, 1, [found libunibreak via pkg-config])
+    ], [
+        AS_IF([test "x$enable_libunibreak" = xyes], [
+            AC_MSG_ERROR([libunibreak support was requested, but it was not found.])
+        ])
+    ])
+])
+
 ## Check for system font providers
 ### Fontconfig
 AS_IF([test "x$enable_fontconfig" != xno], [
diff --git a/libass/ass.c b/libass/ass.c
index 991d31b..41f72d6 100644
--- a/libass/ass.c
+++ b/libass/ass.c
@@ -1546,6 +1546,9 @@ int ass_track_set_feature(ASS_Track *track, ASS_Feature feature, int enable)
 #ifdef USE_FRIBIDI_EX_API
         FEATURE_MASK(ASS_FEATURE_BIDI_BRACKETS) |
 #endif
+#ifdef CONFIG_UNIBREAK
+        FEATURE_MASK(ASS_FEATURE_WRAP_UNICODE) |
+#endif
         FEATURE_MASK(ASS_FEATURE_WHOLE_TEXT_LAYOUT) |
         0;
     uint32_t requested = 0;
diff --git a/libass/ass.h b/libass/ass.h
index 85dc1fe..f0e54bc 100644
--- a/libass/ass.h
+++ b/libass/ass.h
@@ -24,7 +24,7 @@
 #include <stdarg.h>
 #include "ass_types.h"
 
-#define LIBASS_VERSION 0x01600000
+#define LIBASS_VERSION 0x01600010
 
 #ifdef __cplusplus
 extern "C" {
@@ -266,6 +266,19 @@ typedef enum {
      */
     ASS_FEATURE_WHOLE_TEXT_LAYOUT,
 
+    /**
+     * Break lines according to the Unicode Line Breaking Algorithm.
+     * If the track language is set, some additional language-specific tweaks
+     * may be applied. Setting this enables more breaking opportunities
+     * compared to classic ASS. However, it is still possible for long words
+     * without breaking opportunities to cause overfull lines.
+     * This is incompatible with VSFilter and disabled by default.
+     *
+     * This feature may be unavailable at runtime if
+     * libass was compiled without libunibreak support.
+     */
+    ASS_FEATURE_WRAP_UNICODE,
+
     // New enum values can be added here in new ABI-compatible library releases.
 } ASS_Feature;
 
diff --git a/libass/ass_library.c b/libass/ass_library.c
index 745798e..42cabbd 100644
--- a/libass/ass_library.c
+++ b/libass/ass_library.c
@@ -24,6 +24,9 @@
 #include <stdlib.h>
 #include <string.h>
 #include <stdarg.h>
+#ifdef CONFIG_UNIBREAK
+#include <linebreak.h>
+#endif
 
 #include "ass.h"
 #include "ass_library.h"
@@ -44,6 +47,10 @@ ASS_Library *ass_library_init(void)
     ASS_Library* lib = calloc(1, sizeof(*lib));
     if (lib)
         lib->msg_callback = ass_msg_handler;
+    #ifdef CONFIG_UNIBREAK
+    // libunibreak works without, but its docs suggest this improves performance
+    init_linebreak();
+    #endif
     return lib;
 }
 
diff --git a/libass/ass_render.c b/libass/ass_render.c
index 5fac76b..7f31f2b 100644
--- a/libass/ass_render.c
+++ b/libass/ass_render.c
@@ -24,6 +24,10 @@
 #include <string.h>
 #include <stdbool.h>
 
+#ifdef CONFIG_UNIBREAK
+#include <linebreak.h>
+#endif
+
 #include "ass.h"
 #include "ass_outline.h"
 #include "ass_render.h"
@@ -108,8 +112,10 @@ ASS_Renderer *ass_renderer_init(ASS_Library *library)
     priv->text_info.combined_bitmaps = calloc(MAX_BITMAPS_INITIAL, sizeof(CombinedBitmapInfo));
     priv->text_info.glyphs = calloc(MAX_GLYPHS_INITIAL, sizeof(GlyphInfo));
     priv->text_info.event_text = calloc(MAX_GLYPHS_INITIAL, sizeof(FriBidiChar));
+    priv->text_info.breaks = malloc(MAX_GLYPHS_INITIAL);
     priv->text_info.lines = calloc(MAX_LINES_INITIAL, sizeof(LineInfo));
-    if (!priv->text_info.combined_bitmaps || !priv->text_info.glyphs || !priv->text_info.lines)
+    if (!priv->text_info.combined_bitmaps || !priv->text_info.glyphs ||
+            !priv->text_info.lines || !priv->text_info.breaks)
         goto fail;
 
     priv->settings.font_size_coeff = 1.;
@@ -155,6 +161,7 @@ void ass_renderer_done(ASS_Renderer *render_priv)
     free(render_priv->eimg);
     free(render_priv->text_info.glyphs);
     free(render_priv->text_info.event_text);
+    free(render_priv->text_info.breaks);
     free(render_priv->text_info.lines);
 
     free(render_priv->text_info.combined_bitmaps);
@@ -1629,11 +1636,19 @@ static void trim_whitespace(ASS_Renderer *render_priv)
 }
 #undef IS_WHITESPACE
 
+#ifdef CONFIG_UNIBREAK
+    #define ALLOWBREAK(glyph, index) (unibrks ? unibrks[index] == LINEBREAK_ALLOWBREAK : glyph == ' ')
+    #define FORCEBREAK(glyph, index) (unibrks ? unibrks[index] == LINEBREAK_MUSTBREAK  : glyph == '\n')
+#else
+    #define ALLOWBREAK(glyph, index) (glyph == ' ')
+    #define FORCEBREAK(glyph, index) (glyph == '\n')
+#endif
+
 /*
  * Starts a new line on the first breakable character after overflow
  */
 static void
-wrap_lines_naive(ASS_Renderer *render_priv, double max_text_width)
+wrap_lines_naive(ASS_Renderer *render_priv, double max_text_width, char *unibrks)
 {
     TextInfo *text_info = &render_priv->text_info;
     GlyphInfo *s1  = text_info->glyphs; // current line start
@@ -1647,21 +1662,23 @@ wrap_lines_naive(ASS_Renderer *render_priv, double max_text_width)
         double s_offset = d6_to_double(s1->bbox.x_min + s1->pos.x);
         double len = d6_to_double(cur->bbox.x_max + cur->pos.x) - s_offset;
 
-        if (cur->symbol == '\n') {
+        if (FORCEBREAK(cur->symbol, i)) {
             break_type = 2;
             break_at = i;
             ass_msg(render_priv->library, MSGL_DBG2,
                     "forced line break at %d", break_at);
-        } else if (cur->symbol == ' ') {
-            last_breakable = i;
-        } else if (len >= max_text_width
-                   && (render_priv->state.wrap_style != 2)) {
+        } else if (len >= max_text_width &&
+                   cur->symbol != ' ' /* get trimmed */ &&
+                   (render_priv->state.wrap_style != 2)) {
             break_type = 1;
             break_at = last_breakable;
             if (break_at >= 0)
                 ass_msg(render_priv->library, MSGL_DBG2, "line break at %d",
                         break_at);
         }
+        if (ALLOWBREAK(cur->symbol, i)) {
+            last_breakable = i;
+        }
 
         if (break_at != -1) {
             // need to use one more line
@@ -1690,7 +1707,7 @@ wrap_lines_naive(ASS_Renderer *render_priv, double max_text_width)
  * FIXME: implement style 0 and 3 correctly
  */
 static void
-wrap_lines_rebalance(ASS_Renderer *render_priv, double max_text_width)
+wrap_lines_rebalance(ASS_Renderer *render_priv, double max_text_width, char *unibrks)
 {
     TextInfo *text_info = &render_priv->text_info;
     int exit = 0;
@@ -1711,10 +1728,12 @@ wrap_lines_rebalance(ASS_Renderer *render_priv, double max_text_width)
                     double l1, l2, l1_new, l2_new;
                     GlyphInfo *w = s2;
 
+                    // Find last word of line and trim surrounding whitespace before measuring
+                    // (whitespace ' ' will also get trimmed in rendering)
                     do {
                         --w;
                     } while ((w > s1) && (w->symbol == ' '));
-                    while ((w > s1) && (w->symbol != ' ')) {
+                    while ((w > s1) && (!ALLOWBREAK(w->symbol, w - text_info->glyphs))) {
                         --w;
                     }
                     GlyphInfo *e1 = w;
@@ -1755,7 +1774,7 @@ wrap_lines_rebalance(ASS_Renderer *render_priv, double max_text_width)
 }
 
 static void
-wrap_lines_measure(ASS_Renderer *render_priv)
+wrap_lines_measure(ASS_Renderer *render_priv, char *unibrks)
 {
     TextInfo *text_info = &render_priv->text_info;
     int cur_line = 1;
@@ -1769,7 +1788,7 @@ wrap_lines_measure(ASS_Renderer *render_priv)
     for (i = 0; i < text_info->length; ++i) {
         GlyphInfo *cur = text_info->glyphs + i;
         if (cur->linebreak) {
-            while (i < text_info->length && cur->skip && cur->symbol != '\n')
+            while (i < text_info->length && cur->skip && !FORCEBREAK(cur->symbol, i))
                 cur = text_info->glyphs + ++i;
             double height =
                 text_info->lines[cur_line - 1].desc +
@@ -1788,6 +1807,9 @@ wrap_lines_measure(ASS_Renderer *render_priv)
         text_info->length - text_info->lines[cur_line - 1].offset;
 }
 
+#undef ALLOWBREAK
+#undef FORCEBREAK
+
 /**
  * \brief rearrange text between lines
  * \param max_text_width maximal text line width in pixels
@@ -1802,12 +1824,34 @@ wrap_lines_measure(ASS_Renderer *render_priv)
 static void
 wrap_lines_smart(ASS_Renderer *render_priv, double max_text_width)
 {
-    wrap_lines_naive(render_priv, max_text_width);
-    wrap_lines_rebalance(render_priv, max_text_width);
+    char *unibrks = NULL;
+
+#ifdef CONFIG_UNIBREAK
+    if (render_priv->track->parser_priv->feature_flags & FEATURE_MASK(ASS_FEATURE_WRAP_UNICODE)) {
+        unibrks = render_priv->text_info.breaks;
+        set_linebreaks_utf32(
+            render_priv->text_info.event_text, render_priv->text_info.length,
+            render_priv->track->Language, unibrks);
+#if UNIBREAK_VERSION < 0x0500UL
+        // Prior to 5.0 libunibreaks always ended text with LINE_BREAKMUSTBREAK, matching
+        // Unicode spec, but messing with our text-overflow detection.
+        // Thus reevaluate the last char in a different context.
+        // (Later versions set either MUSTBREAK or the newly added INDETERMINATE)
+        unibrks[render_priv->text_info.length - 1] = is_line_breakable(
+            render_priv->text_info.event_text[render_priv->text_info.length - 1],
+            ' ',
+            render_priv->track->Language
+        );
+#endif
+    }
+#endif
+
+    wrap_lines_naive(render_priv, max_text_width, unibrks);
+    wrap_lines_rebalance(render_priv, max_text_width, unibrks);
 
     trim_whitespace(render_priv);
     measure_text(render_priv);
-    wrap_lines_measure(render_priv);
+    wrap_lines_measure(render_priv, unibrks);
 }
 
 /**
@@ -1974,7 +2018,8 @@ static bool parse_events(ASS_Renderer *render_priv, ASS_Event *event)
             if (text_info->length >= new_max)
                 goto fail;
             if (!ASS_REALLOC_ARRAY(text_info->glyphs, new_max) ||
-                    !ASS_REALLOC_ARRAY(text_info->event_text, new_max))
+                    !ASS_REALLOC_ARRAY(text_info->event_text, new_max) ||
+                    !ASS_REALLOC_ARRAY(text_info->breaks, new_max))
                 goto fail;
             text_info->max_glyphs = new_max;
         }
diff --git a/libass/ass_render.h b/libass/ass_render.h
index 58b6aa2..19d03f3 100644
--- a/libass/ass_render.h
+++ b/libass/ass_render.h
@@ -188,6 +188,7 @@ typedef struct {
 typedef struct {
     GlyphInfo *glyphs;
     FriBidiChar *event_text;
+    char *breaks;
     int length;
     LineInfo *lines;
     int n_lines;