pastry

Makefile modified +3 -3

diff --git a/Makefile b/Makefile
index d503914095ce3db763196687123da1c14ffb893e..cbba3a3711c3c78e06f9f5226365d937b4ed530b 100644
--- a/Makefile
+++ b/Makefile
@@ -1,6 +1,6 @@
 CC = gcc
-DEMO_CFLAGS     = $(shell pkg-config --cflags x11 xrender harfbuzz)
-DEMO_LIBS       = $(shell pkg-config --libs x11 xrender harfbuzz)
+DEMO_CFLAGS     = $(shell pkg-config --cflags x11 xrender harfbuzz fribidi)
+DEMO_LIBS       = $(shell pkg-config --libs x11 xrender harfbuzz fribidi)
 CFLAGS = -std=c99 -pedantic-errors -Wall -Wextra -Werror -Wstrict-prototypes -Wmissing-prototypes -Wmissing-declarations -Wredundant-decls  \
              -Wnested-externs -Winline -Wundef -Wshadow -Wpointer-arith -Wcast-qual -Wcast-align -Wwrite-strings -Wconversion -Wsign-conversion \
              -Wfloat-conversion -Wformat=2 -Wformat-security -Wformat-nonliteral -Wstrict-aliasing=3 -Wstrict-overflow=5 -Wjump-misses-init     \
@@ -28,7 +28,7 @@ 	@mkdir -p $(INCLUDE_DIR)
 	cp $(HDR) $(INCLUDE_DIR)/
 	$(CC) $(CFLAGS) -c $< -o $@
 
-# the demo shapes with harfbuzz at runtime and draws with pastry
+# the demo resolves the bidi order with fribidi, shapes with harfbuzz, and draws with pastry
 demo: demo.c $(SRC) $(HDR)
 	$(CC) -std=c99 -O2 -Wall -Wextra $(DEMO_CFLAGS) demo.c $(SRC) -o $@ $(DEMO_LIBS)
 

demo.c modified +106 -16

diff --git a/demo.c b/demo.c
index ddbdc7e0b5d8611a47939ef1fcc80854f44fad16..41a31d5136aa39441f86d20f501914024fd2f6cf 100644
--- a/demo.c
+++ b/demo.c
@@ -9,7 +9,11 @@
 #include <hb.h>
 #include <hb-ot.h>
 
-static int add_glyph(Display *dpy, GlyphSet glyphset, PASTRY *pastry, PASTRY_Glyph glyph)
+#include <fribidi.h>
+
+#define MAX_CHARS 256
+
+static int add_glyph(Display *dpy, GlyphSet glyphset, PASTRY *pastry, PASTRY_Glyph glyph, int *advance)
 {
 #define ABORT(glyph, m) do { fprintf(stderr, "glyph %lu %s\n", (unsigned long)(glyph), m); return -1; } while (0)
 
@@ -38,6 +42,104 @@     Glyph g = (Glyph) glyph;
     XRenderAddGlyphs(dpy, glyphset, &g, &info, 1,
                      img.pixels, (int) (img.width * img.height));
 
+    *advance += info.xOff;
+    return 0;
+}
+
+typedef struct {
+    FriBidiLevel  level;          // embedding level; odd means right-to-left
+    int           advance;        // total advance, used to place the next run
+    unsigned int  count;          // number of shaped glyphs
+    uint32_t      glyphs[MAX_CHARS];
+} LineRun;
+
+static int draw_line(Display *dpy, GlyphSet glyphset, Picture fgpic, Picture pic,
+                     PASTRY *pastry, hb_font_t *font, hb_buffer_t *buffer,
+                     const char *text, int y)
+{
+    FriBidiChar  u[MAX_CHARS];
+    FriBidiLevel levels[MAX_CHARS];
+
+    FriBidiStrIndex len = fribidi_charset_to_unicode(FRIBIDI_CHAR_SET_UTF8, text,
+                                                     (FriBidiStrIndex) strlen(text), u);
+    if (len <= 0)
+        return 0;
+    if (len > MAX_CHARS)
+        len = MAX_CHARS;
+
+    for (FriBidiStrIndex i = 0; i < len; i++)
+        levels[i] = 0;
+
+    FriBidiParType baseDir = FRIBIDI_PAR_ON; // let fribidi pick the direction
+    fribidi_log2vis(u, len, &baseDir, NULL, NULL, NULL, levels);
+
+    // split the line into runs of equal embedding level, in logical order
+    LineRun runs[MAX_CHARS];
+    unsigned int nruns = 0;
+
+    for (FriBidiStrIndex i = 0; i < len; ) {
+        FriBidiStrIndex end = i + 1;
+        while (end < len && levels[end] == levels[i])
+            end++;
+
+        LineRun *run = &runs[nruns++];
+        run->level   = levels[i];
+        run->advance = 0;
+
+        hb_buffer_clear_contents(buffer);
+        hb_buffer_add_utf32(buffer, (const uint32_t *) &u[i], (int) (end - i), 0, (int) (end - i));
+        hb_buffer_guess_segment_properties(buffer);
+        hb_buffer_set_direction(buffer, (levels[i] & 1) ? HB_DIRECTION_RTL : HB_DIRECTION_LTR);
+        hb_shape(font, buffer, NULL, 0);
+
+        unsigned int count = 0;
+        hb_glyph_info_t *info = hb_buffer_get_glyph_infos(buffer, &count);
+        if (count > MAX_CHARS)
+            count = MAX_CHARS;
+        run->count = count;
+        for (unsigned int k = 0; k < count; k++) {
+            run->glyphs[k] = info[k].codepoint;
+            if (add_glyph(dpy, glyphset, pastry, (PASTRY_Glyph) info[k].codepoint, &run->advance) < 0)
+                return -1;
+        }
+
+        i = end;
+    }
+
+    // reorder the runs into visual order (rule L2 of the bidi algorithm)
+    FriBidiLevel maxLevel = 0, lowestOdd = 0;
+    for (unsigned int i = 0; i < nruns; i++) {
+        if (runs[i].level > maxLevel)
+            maxLevel = runs[i].level;
+        if ((runs[i].level & 1) && (lowestOdd == 0 || runs[i].level < lowestOdd))
+            lowestOdd = runs[i].level;
+    }
+    for (FriBidiLevel level = maxLevel; lowestOdd && level >= lowestOdd; level--) {
+        for (unsigned int i = 0; i < nruns; ) {
+            if (runs[i].level < level) {
+                i++;
+                continue;
+            }
+            unsigned int j = i;
+            while (j < nruns && runs[j].level >= level)
+                j++;
+            for (unsigned int a = i, b = j - 1; a < b; a++, b--) {
+                LineRun tmp = runs[a];
+                runs[a] = runs[b];
+                runs[b] = tmp;
+            }
+            i = j;
+        }
+    }
+
+    int x = 20;
+    for (unsigned int i = 0; i < nruns; i++) {
+        if (runs[i].count == 0)
+            continue;
+        XRenderCompositeString32(dpy, PictOpOver, fgpic, pic, NULL, glyphset,
+                                 0, 0, x, y, runs[i].glyphs, (int) runs[i].count);
+        x += runs[i].advance;
+    }
     return 0;
 }
 
@@ -101,26 +203,14 @@             PASTRY_LMetrics lmtx;
             pastry_lmetrics(&pastry, &lmtx);
             int y = 20 + (int)lmtx.ascender + (int)lmtx.lineGap;
 
-            char text[256];
+            char text[MAX_CHARS];
             while (fgets(text, sizeof(text), file)) {
                 size_t len = strlen(text);
                 if (len > 0 && text[len - 1] == '\n')
                     text[--len] = 0;
 
-                hb_buffer_clear_contents(buffer);
-                hb_buffer_add_utf8(buffer, text, (int)len, 0, (int)len);
-                hb_buffer_guess_segment_properties(buffer);
-                hb_shape(font, buffer, NULL, 0);
-
-                unsigned int count = 0;
-                hb_glyph_info_t *info = hb_buffer_get_glyph_infos(buffer, &count);
-                for (unsigned int i = 0; i < count; i++)
-                    add_glyph(dpy, glyphset, &pastry, (PASTRY_Glyph) info[i].codepoint);
-
-                unsigned int glyphs[256];
-                for (unsigned int i = 0; i < count && i < 256; i++)
-                    glyphs[i] = info[i].codepoint;
-                XRenderCompositeString32(dpy, PictOpOver, fgpic, pic, NULL, glyphset, 0, 0, 20, y, glyphs, (int)count);
+                if (draw_line(dpy, glyphset, fgpic, pic, &pastry, font, buffer, text, y) < 0)
+                    END("failed to draw line");
 
                 y += 2 * ((int)lmtx.ascender + (int)lmtx.descender + (int)lmtx.lineGap);
             }

text.utf8 modified +3 -3

diff --git a/text.utf8 b/text.utf8
index 9787d099b5214d564cf67b02daba5205ceaf53ac..99d1aa1dbc03dc50dbc6e6013e7659ce89b608ab 100644
--- a/text.utf8
+++ b/text.utf8
@@ -6,9 +6,9 @@  5. Romanian: Pot să mănânc sticlă și ea nu mă rănește
  6. Ukrainian: Я можу їсти шкло, й воно мені не пошкодить
  7. Georgian: მინას ვჭამ და არა მტკივა
  8. Hindi: मैं काँच खा सकता हूँ, मुझे उस से कोई पीडा नहीं होती
- 9. Hebrew: אני יכול לאכול זכוכית וזה לא מזיק לי
-10. Yiddish: איך קען עסן גלאָז און עס טוט מיר נישט װײ
-11. Arabic: أنا قادر على أكل الزجاج و هذا لا يؤلمني.
+ 9. Hebrew: אני יכול לאכול זכוכית וזה לא מזיק לי‏
+10. Yiddish: איך קען עסן גלאָז און עס טוט מיר נישט װײ‏
+11. Arabic: أنا قادر على أكل الزجاج و هذا لا يؤلمني.‏
 12. Thai: ฉันกินกระจกได้ แต่มันไม่ทำให้ฉันเจ็บ
 13. Random Egyptian hieroglyphs: 𓀌 𓀹 𓁚 𓁭