From c38380464d29c4502c98d996236ccf890392fe86 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 28 Sep 2026 12:48:45 +0100 Subject: Shape text as HarfBuzz does, from a symbol file, checked against HarfBuzz The build tool compiles a font's shaping plans the way HarfBuzz's planner does (features, stages, masks, lookups per script and direction) and carries them with the font's character map, advances and GDEF, GSUB and GPOS tables in a section of the symbol file (VEGASYM4); glyphs shaping reaches become symbols of their own. A small engine ports HarfBuzz 10's default, Arabic and Hebrew shaping step for step and reads the tables in place, every read bounds-checked. The build refuses a file whose shaping differs from HarfBuzz's on random runs: DejaVu Sans agrees on 600,000 runs in six scripts both ways, and every installed font the tool accepts agrees too, at 1.05-1.18 times HarfBuzz's time. --- Makefile | 23 +- docs/design/004-text.md | 61 +- symbols/symbols-tool.c | 271 +++++- symbols/symbols.c | 19 +- symbols/symbols.h | 7 + text/shape-build.c | 723 ++++++++++++++++ text/shape-build.h | 31 + text/shape.c | 2156 +++++++++++++++++++++++++++++++++++++++++++++++ text/shape.h | 101 +++ 9 files changed, 3357 insertions(+), 35 deletions(-) create mode 100644 text/shape-build.c create mode 100644 text/shape-build.h create mode 100644 text/shape.c create mode 100644 text/shape.h diff --git a/Makefile b/Makefile index 29bbc27..119e116 100644 --- a/Makefile +++ b/Makefile @@ -39,24 +39,37 @@ $(BUILD)/vega-surface.so: $(SURFACES) surfaces/vega.h symbols/symbols.c symbols/ -fdata-sections -DVEGA_SURFACE -I$(PURE)/core -I$(PURE)/serve -Isymbols $(SURFACES) symbols/symbols.c \ $(LDFLAGS) -Wl,--gc-sections -lm $(LDLIBS) -o $@ -# Building symbol files reads fonts through FreeType; reading them does not. +# Building symbol files reads fonts through FreeType, and compiles and checks +# their shaping with HarfBuzz; reading them needs neither. FREETYPE_CFLAGS ?= $(shell pkg-config --cflags freetype2) FREETYPE_LIBS ?= $(shell pkg-config --libs freetype2) +HARFBUZZ_CFLAGS ?= $(shell pkg-config --cflags harfbuzz) +HARFBUZZ_LIBS ?= $(shell pkg-config --libs harfbuzz) # Drawing them on the GPU takes OpenGL ES 3.1 through EGL. GL_LIBS ?= $(shell pkg-config --libs egl glesv2) SYMBOLS = symbols/symbols.c symbols/symbols-gl.c -$(BUILD)/vega-symbols: symbols/symbols-tool.c $(SYMBOLS) symbols/symbols.h symbols/symbols-gl.h | $(BUILD) - $(CC) $(CPPFLAGS) $(CFLAGS) $(FREETYPE_CFLAGS) symbols/symbols-tool.c $(SYMBOLS) $(LDFLAGS) \ - $(FREETYPE_LIBS) $(GL_LIBS) -lm $(LDLIBS) -o $@ +SHAPE = text/shape.c text/unicode-data.c +$(BUILD)/vega-symbols: symbols/symbols-tool.c $(SYMBOLS) symbols/symbols.h symbols/symbols-gl.h $(SHAPE) text/shape-build.c \ + text/shape.h text/shape-build.h text/text.h | $(BUILD) + $(CC) $(CPPFLAGS) $(CFLAGS) $(FREETYPE_CFLAGS) $(HARFBUZZ_CFLAGS) -Itext symbols/symbols-tool.c $(SYMBOLS) $(SHAPE) \ + text/shape-build.c $(LDFLAGS) $(FREETYPE_LIBS) $(HARFBUZZ_LIBS) $(GL_LIBS) -lm $(LDLIBS) -o $@ TEXT = text/bidi.c text/normalize.c text/unicode-data.c $(BUILD)/test-text: text/test-text.c $(TEXT) text/text.h | $(BUILD) $(CC) $(CPPFLAGS) $(CFLAGS) -Itext text/test-text.c $(TEXT) $(LDFLAGS) $(LDLIBS) -o $@ -# Unicode's conformance tests, where the UCD is installed (Debian: unicode-data). +# Unicode's conformance tests, where the UCD is installed (Debian: unicode-data); +# and shaping, where DejaVu Sans is: the build refuses a file whose shaping +# differs from HarfBuzz's on random runs of Latin, Greek, Cyrillic, Hebrew, +# Arabic and Common text, both ways. UCD ?= /usr/share/unicode +SHAPED_FONT ?= /usr/share/fonts/truetype/dejavu/DejaVuSans.ttf +SHAPED_CODES = 0x20-0x7e,0xa0-0x24f,0x300-0x36f,0x370-0x3ff,0x400-0x4ff,0x591-0x5f4,0x600-0x6ff,0x2000-0x206f check: $(BUILD)/vega $(BUILD)/vega-symbols $(BUILD)/vega-surface.so $(BUILD)/test-text if [ -f $(UCD)/BidiTest.txt ]; then $(BUILD)/test-text $(UCD); else echo "no UCD at $(UCD): text tests skipped"; fi + if [ -f $(SHAPED_FONT) ]; then $(BUILD)/vega-symbols build --font $(SHAPED_FONT) --codes $(SHAPED_CODES) \ + --shape Latn,Grek,Cyrl,Hebr,Arab,Zyyy --runs 5000 -o $(BUILD)/shaped.vsym; \ + else echo "no $(SHAPED_FONT): shaping tests skipped"; fi $(MAKE) -C $(AUP) build/aup $(MAKE) -C $(PURE) build/pure-serve python3 tests/check.py --vega $(BUILD)/vega --symbols $(BUILD)/vega-symbols --aup $(AUP)/build/aup --serve $(PURE)/build/pure-serve diff --git a/docs/design/004-text.md b/docs/design/004-text.md index f423221..4ee1cf2 100644 --- a/docs/design/004-text.md +++ b/docs/design/004-text.md @@ -7,7 +7,8 @@ 착수 기준: - 바꿀 결정: 셰이핑을 실행 중에 OpenType 표(GSUB, GPOS)를 해석해서 할지(HarfBuzz의 방식), 빌드할 때 글꼴의 행동을 - 단순한 표로 컴파일해 두고 실행 중에는 검증한 표를 제자리에서 읽기만 할지. 심볼과 같은 원칙이면 뒤쪽이다. + 단순한 표로 컴파일해 두고 실행 중에는 검증한 표를 제자리에서 읽기만 할지. 심볼과 같은 원칙이면 뒤쪽이다. (결과: 둘을 + 나눴다. 계획은 빌드할 때 컴파일하고, 조회는 OpenType 그대로 읽는다. 아래 셰이핑 절.) - 남은 질문: 컴파일한 표만으로 HarfBuzz와 같은 글리프와 자리가 나오는가? 어느 문자 체계까지인가? 양방향과 합성은 유니코드의 적합성 시험을 모두 통과하는가? - 최소 확인: 유니코드 15.1의 `BidiTest.txt`(49만 줄)와 `BidiCharacterTest.txt`(9.6만 줄), `NormalizationTest.txt`를 모두 @@ -23,8 +24,8 @@ 2. 양방향(UAX #9): 문단 수준, 명시적 수준과 격리(X1–X10), 약한 형(W1–W7), 괄호 쌍(N0), 중립(N1–N2), 암시적 수준(I1–I2), 줄(L1)과 보이는 순서(L2). 3. 정규화: 한글 음절과 정준 합성(NFC). -4. 셰이핑: 빌드 도구가 글꼴마다 HarfBuzz로 커닝 쌍, 합자, 위치별 형태, 결합 부호의 자리를 뽑아 심볼 파일에 넣는다. 실행 중에는 - 그 표를 찾아 쓴다. +4. 셰이핑: 빌드 도구가 글꼴의 셰이핑 계획을 컴파일해 배치 표와 함께 심볼 파일에 넣는다. 실행 중에는 HarfBuzz의 절차를 + 그대로 옮긴 엔진이 그것을 읽는다. 빌드 도구는 HarfBuzz와 결과가 다른 파일을 만들지 않는다. 5. 비례폭 글줄: 셰이핑한 글리프를 제 advance로 늘어놓아 그린다. 6. 접근성. @@ -49,3 +50,57 @@ U+3008·3009의 정준 동치, 바뀐 괄호 뒤의 결합 부호), 중립(N1– `NormalizationTest.txt`의 19,074줄(줄마다 NFC와 NFD 16가지 대조)과, 그 1부에 없는 코드 포인트 1,095,035개가 제 자신의 NFC이자 NFD라는 것을 모두 지킨다. 적합성 시험 셋을 합쳐 Pi 5에서 0.9초다. + +## 셰이핑 + +처음 계획은 HarfBuzz가 표본 문자열(글자 쌍, 부호 하나 붙은 글자, 위치별 형태)을 셰이핑한 결과를 표로 뽑는 것이었다. 글꼴을 +열어 보고 버렸다. DejaVu Sans 한 벌에만 표본으로 잡히지 않는 규칙이 여럿이다. + +- 라틴의 `ccmp`: i와 j는 위 부호가 뒤에 오면 점 없는 꼴이 된다. 사이에 아래 부호가 둘까지 있어도 그렇고, 셋이면 안 된다. + 대문자 뒤의 위 부호는 대문자용 꼴이 된다. +- 히브리: ayin 뒤에 아래 부호가 오면 ayin이 다른 꼴이 된다. yod와 hiriq는 한 글리프가 된다. +- 아랍: 부호끼리의 합자가 있다(shadda와 fatha). lam-alef는 사이의 부호를 건너뛰어 합쳐지고, 그 부호는 합자의 어느 성분에 + 붙었는지를 따라간다(mark-to-ligature). + +이런 문맥은 규칙 자체를 옮기지 않고는 정확히 재현할 수 없다. 그래서 나눴다. + +- 빌드할 때: 계획을 컴파일한다. 문자 체계와 방향마다 HarfBuzz의 계획기가 하는 일을 그대로 한다. 기능을 모으고(기본, 아랍, + 히브리 셰이퍼의 목록과 단계), 중복을 합치고, 마스크 비트를 나누고, 글꼴의 문자 체계·언어 체계에서 기능을 찾고, 단계별로 + 조회를 모아 정렬해 합친다. 결과는 조회 번호, 마스크, ZWJ/ZWNJ 규칙의 목록이다. 글꼴의 문자 지도와 advance, GDEF·GSUB·GPOS + 표는 그대로 싣는다([text/shape.h](../../text/shape.h), [text/shape-build.c](../../text/shape-build.c)). +- 실행 중에: [text/shape.c](../../text/shape.c)가 HarfBuzz 10의 절차를 함수 단위로 옮긴다. 유니코드 성질과 자소 묶음, + 글꼴을 보는 정규화(없는 글자는 분해하고 있는 합성은 합치며, 부호는 HarfBuzz의 수정 결합 등급과 아랍 UTR #53, 히브리 + 순서로 정렬한다), 거울 글자, 아랍 연결 상태 기계, GSUB(유형 1–8과 확장, 문맥과 연쇄 문맥의 형식 1–3, 역연쇄), 합자의 + 성분 추적, GPOS(유형 1–8, 짝 형식 1·2, 필기체, 기저·합자·부호에 붙는 부호), 부착 오프셋의 전파, 보이지 않는 문자 + 숨기기를 한다. 표는 제자리에서 읽고, 읽을 때마다 표의 끝을 넘는지 확인한다. 망가진 표는 틀리게 셰이핑할 뿐 밖을 읽지 + 않는다. + +심볼 파일은 VEGASYM4가 됐다. 헤더의 깃발이 점들 뒤에 셰이핑 구역이 있다고 알린다. 셰이핑이 닿는 글리프(문자 지도, +분해와 합성, 거울, GSUB의 닫힘)는 `0x110000 + 글리프 번호`로 심볼이 된다. 같은 글리프의 심볼들은 점을 나눠 쓴다. + +HarfBuzz와 다른 파일은 만들어지지 않는다. `vega-symbols build --shape`는 파일을 쓴 뒤 계획마다 무작위 실행을 HarfBuzz +10.2와 함께 셰이핑한다. 실행은 두 종류다. 하나는 낱말들(글꼴의 치환이 시작되는 글자를 자주 섞고, 부호를 하나에서 +셋까지 붙이고, ZWJ·ZWNJ를 끼운다)이고, 다른 하나는 아무 순서의 문자(맨 앞의 부호, 쌓인 부호)다. 글리프, 클러스터, +advance, 오프셋 가운데 하나라도 다른 실행이 있으면 파일을 지운다. + +결과(Pi 5): + +- DejaVu Sans, 라틴·그리스·키릴·히브리·아랍·Common, 양방향 12개 계획에 각 5만 실행(60만 실행, 1,270만 문자): 다른 + 실행 0. +- 설치된 글꼴 전부(Free, Liberation, Lato, Noto Sans Mono, URW, DejaVu 계열 등 60여 벌), 계획마다 1천 실행: 받아들인 + 글꼴은 모두 다른 실행 0. 한 번 달랐다. 짝 위치 형식 2에서 두 번째 글리프의 등급이 0이면 다음 하위 표로 넘어가게 짰는데, + HarfBuzz 10.2는 그 하위 표를 적용하고 멈춘다(FreeSerif의 y와 마침표 커닝이 40 단위 달랐다). 고친 뒤 FreeSerif, FreeMono, + DejaVu Sans Bold, Liberation Mono, Lato에 계획마다 2만 실행으로 다시 확인했다. +- 속도: 조회마다, 하위 표마다 시작 글리프의 요약(HarfBuzz의 set digest: 64비트 무늬 셋)을 열 때 만들어 두면, 버퍼에 없는 + 글리프로 시작하는 조회와 하위 표를 건너뛴다. 문자 지도는 BMP를 쪽마다 바로 찾는다. 이것으로 HarfBuzz의 1.05–1.18배 + 시간이다(문자당 라틴 422 대 404 ns, 아랍 428 대 371 ns, 히브리 313 대 274 ns). 요약 전에는 2.5배였다. + +받지 않는 것(빌드 도구가 이유를 말하고 거부한다): + +- GPOS가 없는 글꼴. HarfBuzz는 결합 등급과 글리프 외곽 상자로 부호를 놓는다(fallback positioning). CJK 글꼴, Nimbus Mono, + Noto Mono 등이 여기에 걸린다. +- 옛 `kern` 표로 커닝하는 글꼴(Liberation Sans·Serif, FreeSans). +- AAT 표(morx, kerx, trak), 늘이기(stch), 아랍 형태가 없어 HarfBuzz가 대체 셰이핑을 하는 글꼴. +- 기본·아랍·히브리 셰이퍼가 아닌 문자 체계: 인도계, 태국·라오, 한글 자모, 크메르, 미얀마, USE 문자 체계들, 시리아. +- 이체 선택자(cmap 형식 14)는 싣지 않는다. 선택자는 숨기고 앞 글자는 기본 글리프로 둔다. + diff --git a/symbols/symbols-tool.c b/symbols/symbols-tool.c index b705d84..765dd5c 100644 --- a/symbols/symbols-tool.c +++ b/symbols/symbols-tool.c @@ -1,13 +1,17 @@ #define _POSIX_C_SOURCE 200809L /* vega-symbols: build symbol files from fonts and SVG icons, and measure them * against FreeType (docs/design/002-symbol-format.md). - * vega-symbols build [--font FONT.ttf [--face N] --codes 0x20-0x7e,...]... [--svg CODE=ICON.svg ...] [--units N] -o OUT.vsym + * vega-symbols build [--font FONT.ttf [--face N] --codes 0x20-0x7e,... [--shape Latn,Arab,...]]... [--svg CODE=ICON.svg ...] + * [--units N] [--runs N] -o OUT.vsym + * vega-symbols shape-check FONT.ttf OUT.vsym [--face N] [--runs N] [--seed N] * vega-symbols compare FONT.ttf OUT.vsym --sizes 12,16,32,64 * vega-symbols info OUT.vsym * vega-symbols render OUT.vsym CODE PIXELS OUT.pgm * vega-symbols gpu OUT.vsym --sizes 12,16,32,64 [--frames N] */ +#include "shape-build.h" #include "symbols-gl.h" #include "symbols.h" +#include "text.h" #include #include #include @@ -18,6 +22,7 @@ #include #include #include +#include #define PI 3.14159265358979323846 @@ -27,7 +32,9 @@ typedef struct { double x, y; } Point; typedef enum { MOVE, LINE, QUAD } Kind; typedef struct { Kind kind; bool smooth; Point control, end; } Segment; typedef struct { Segment *items; size_t count, capacity; Point at, start; bool open; double font_scale; } Path; -typedef struct { uint32_t code; size_t first, count; int16_t advance; } Built; /* segments [first, first + count) */ +/* segments [first, first + count); a font's glyph (-1 for an icon), for + * symbols that share it to share its points */ +typedef struct { uint32_t code; size_t first, count; int16_t advance; int font; long glyph; } Built; static void fail(const char *why) { fprintf(stderr, "vega-symbols: %s\n", why); @@ -407,18 +414,45 @@ static int by_code(const void *a, const void *b) { return (x > y) - (x < y); } -/* line: a font's ascent and descent in the build's units (0 and 0 without a font). */ -static void write_symbols(const char *out, uint16_t units, const long line[2], Built *built, size_t count, const Path *path) { +/* The first symbol built from the same font's glyph, or i itself. */ +static size_t shared_with(const Built *built, size_t i, long *table, size_t capacity) { + if (built[i].glyph < 0) return i; + size_t at = ((size_t)built[i].glyph * 2654435761u + (size_t)built[i].font) & (capacity - 1); + for (;; at = (at + 1) & (capacity - 1)) { + if (table[at] < 0) { + table[at] = (long)i; + return i; + } + const Built *other = &built[table[at]]; + if (other->glyph == built[i].glyph && other->font == built[i].font) return (size_t)table[at]; + } +} + +/* line: a font's ascent and descent in the build's units (0 and 0 without a + * font); shaping: a shaping section to carry (NULL for none). */ +static void write_symbols(const char *out, uint16_t units, const long line[2], Built *built, size_t count, const Path *path, + const VegaSection *shaping) { long ascent = line[0], descent = line[1]; qsort(built, count, sizeof(*built), by_code); for (size_t i = 1; i < count; ++i) if (built[i].code == built[i - 1].code) fail("a code is given twice"); Points points = {0}; - size_t *first = calloc(count + 1, sizeof(*first)); + size_t *first = calloc(count + 1, sizeof(*first)), *length = calloc(count + 1, sizeof(*length)), capacity = 16; + while (capacity < 2 * count) capacity *= 2; + long *table = malloc(capacity * sizeof(*table)); + if (!first || !length || !table) fail("out of memory"); + for (size_t i = 0; i < capacity; ++i) table[i] = -1; for (size_t i = 0; i < count; ++i) { + size_t same = shared_with(built, i, table, capacity); + if (same != i) { + first[i] = first[same]; + length[i] = length[same]; + continue; + } first[i] = points.count; emit_symbol(&points, path->items + built[i].first, built[i].count); + length[i] = points.count - first[i]; } - first[count] = points.count; + free(table); /* Halve units while every coordinate is even: a TrueType font's own. */ for (;;) { bool even = units % 2 == 0 && units > 16; @@ -432,10 +466,14 @@ static void write_symbols(const char *out, uint16_t units, const long line[2], B units /= 2; } if (ascent > INT16_MAX || descent < INT16_MIN) fail("the font's line does not fit 16 bits"); - size_t size = VEGA_SYMBOLS_HEADER + count * VEGA_SYMBOL_BYTES + points.count * VEGA_POINT_BYTES; + size_t size = VEGA_SYMBOLS_HEADER + count * VEGA_SYMBOL_BYTES + points.count * VEGA_POINT_BYTES, + outlines = size; + if (shaping) size += shaping->size; unsigned char *bytes = calloc(1, size); if (!bytes) fail("out of memory"); - memcpy(bytes, "VEGASYM3", 8); + memcpy(bytes, shaping ? "VEGASYM4" : "VEGASYM3", 8); + put16(bytes + 10, shaping ? VEGA_SYMBOLS_SHAPING : 0); + if (shaping) memcpy(bytes + outlines, shaping->bytes, shaping->size); put16(bytes + 8, units); put16(bytes + 24, (int)ascent); put16(bytes + 26, (int)descent); @@ -451,7 +489,7 @@ static void write_symbols(const char *out, uint16_t units, const long line[2], B } for (size_t i = 0; i < count; ++i) { long left = 0, bottom = 0, right = 0, top = 0; - for (size_t k = first[i]; k < first[i + 1]; ++k) { + for (size_t k = first[i]; k < first[i] + length[i]; ++k) { const Emitted *e = &points.items[k]; if (k == first[i]) { left = right = e->x; bottom = top = e->y; } left = e->x < left ? e->x : left; @@ -462,7 +500,7 @@ static void write_symbols(const char *out, uint16_t units, const long line[2], B unsigned char *p = bytes + VEGA_SYMBOLS_HEADER + i * VEGA_SYMBOL_BYTES; put32(p, built[i].code); put32(p + 4, (uint32_t)first[i]); - put32(p + 8, (uint32_t)(first[i + 1] - first[i])); + put32(p + 8, (uint32_t)length[i]); put16(p + 12, (int)left); put16(p + 14, (int)bottom); put16(p + 16, (int)right); @@ -480,10 +518,11 @@ static void write_symbols(const char *out, uint16_t units, const long line[2], B VegaSymbol symbol = vega_symbol_at(&check, i); for (uint32_t k = symbol.first; k < symbol.first + symbol.count; ++k) curves += vega_symbol_curve(&check, &symbol, k, &curve); } - printf("{\"symbols\":%zu,\"points\":%zu,\"curves\":%zu,\"units\":%u,\"bytes\":%zu}\n", count, points.count, curves, - units, size); + printf("{\"symbols\":%zu,\"points\":%zu,\"curves\":%zu,\"units\":%u,\"shaping\":%zu,\"bytes\":%zu}\n", count, + points.count, curves, units, shaping ? shaping->size : 0, size); free(bytes); free(first); + free(length); free(points.items); } @@ -513,23 +552,72 @@ static double seconds(void) { return (double)t.tv_sec + (double)t.tv_nsec / 1e9; } -#define BUILD_USAGE \ - "usage: vega-symbols build [--font FONT.ttf [--face N] --codes 0x20-0x7e,...]... [--svg CODE=ICON.svg ...] [--units N] -o OUT.vsym" +#define BUILD_USAGE \ + "usage: vega-symbols build [--font FONT.ttf [--face N] --codes 0x20-0x7e,... [--shape Latn,Arab,...]]... " \ + "[--svg CODE=ICON.svg ...] [--units N] [--runs N] -o OUT.vsym" + +static VegaSymbols open_symbols(const char *name, char **bytes); /* Fonts in order, each with the codes to take from it: a code an earlier * font gave is not taken again, so later fonts fill what earlier ones lack - * (a monospace Latin font, then a CJK one for Hangul). */ -typedef struct { const char *path, *codes; long face; } Font; + * (a monospace Latin font, then a CJK one for Hangul). One font may be + * shaped: its shaping for the scripts named (ISO 15924 codes) goes into the + * file, with the glyphs shaping reaches as symbols of their own. */ +typedef struct { const char *path, *codes, *shape; long face; } Font; + +static uint32_t le32_at(const unsigned char *p) { return p[0] | p[1] << 8 | (uint32_t)p[2] << 16 | (uint32_t)p[3] << 24; } + +/* Shape runs random runs of codes per plan of the file's shaping with it + * and with HarfBuzz; one JSON line per plan; false when any run differs. */ +static bool check_shaping(const VegaSymbols *symbols, hb_font_t *font, const uint32_t *codes, size_t count, size_t runs, + uint64_t seed) { + char error[128]; + VegaShaping shaping; + if (!symbols->shaping) fail("the symbol file carries no shaping"); + if (!vega_shaping_open(&shaping, symbols->shaping, symbols->shaping_size, error, sizeof(error))) fail(error); + bool same = true; + for (uint32_t i = 0; i < shaping.plan_count; ++i) { + const unsigned char *plan = shaping.plans + (size_t)i * VEGA_PLAN_BYTES; + uint32_t script = le32_at(plan); + VegaShapeCheck check; + vega_shaping_check(font, &shaping, script, plan[4], codes, count, seed, runs, &check, stderr); + printf("{\"script\":\"%c%c%c%c\",\"direction\":\"%s\",\"runs\":%zu,\"characters\":%zu,\"glyphs\":%zu," + "\"differences\":%zu,\"vega_ns_per_character\":%.1f,\"harfbuzz_ns_per_character\":%.1f}\n", + (char)(script >> 24), (char)(script >> 16), (char)(script >> 8), (char)script, + plan[4] == VEGA_SHAPE_RTL ? "rtl" : "ltr", check.runs, check.characters, check.glyphs, check.differences, + check.characters ? 1e9 * check.vega_seconds / (double)check.characters : 0, + check.characters ? 1e9 * check.harfbuzz_seconds / (double)check.characters : 0); + same = same && !check.differences; + } + vega_shaping_close(&shaping); + return same; +} + +/* 0x4C61746E for "Latn,..." and so on. */ +static size_t script_tags(const char *text, uint32_t *out, size_t room) { + size_t count = 0; + for (const char *p = text; *p && count < room;) { + if (strlen(p) < 4) fail("--shape takes ISO 15924 codes: Latn,Arab,..."); + out[count++] = (uint32_t)(unsigned char)p[0] << 24 | (uint32_t)(unsigned char)p[1] << 16 | + (uint32_t)(unsigned char)p[2] << 8 | (unsigned char)p[3]; + p += 4; + if (*p == ',') ++p; + else if (*p) fail("--shape takes ISO 15924 codes: Latn,Arab,..."); + } + return count; +} static int build(int argc, char **argv) { const char *out = NULL, **icons = calloc((size_t)argc, sizeof(*icons)); Font *fonts = calloc((size_t)argc, sizeof(*fonts)); - size_t icon_count = 0, font_count = 0; + size_t icon_count = 0, font_count = 0, runs = 3000; long units = 0; for (int i = 2; i < argc; i += 2) { if (i + 1 == argc) fail(BUILD_USAGE); if (!strcmp(argv[i], "-o")) out = argv[i + 1]; - else if (!strcmp(argv[i], "--font")) fonts[font_count++] = (Font){argv[i + 1], NULL, 0}; + else if (!strcmp(argv[i], "--font")) fonts[font_count++] = (Font){argv[i + 1], NULL, NULL, 0}; + else if (!strcmp(argv[i], "--shape") && font_count) fonts[font_count - 1].shape = argv[i + 1]; + else if (!strcmp(argv[i], "--runs")) runs = strtoul(argv[i + 1], NULL, 10); else if (!strcmp(argv[i], "--face") && font_count) fonts[font_count - 1].face = strtol(argv[i + 1], NULL, 10); /* in a .ttc */ else if (!strcmp(argv[i], "--codes") && font_count) fonts[font_count - 1].codes = argv[i + 1]; else if (!strcmp(argv[i], "--units")) units = strtol(argv[i + 1], NULL, 10); @@ -537,7 +625,12 @@ static int build(int argc, char **argv) { else fail(BUILD_USAGE); } if (!out) fail(BUILD_USAGE); - for (size_t f = 0; f < font_count; ++f) if (!fonts[f].codes) fail(BUILD_USAGE); + long shaped = -1; + for (size_t f = 0; f < font_count; ++f) { + if (!fonts[f].codes) fail(BUILD_USAGE); + if (fonts[f].shape && shaped >= 0) fail("only one font can be shaped"); + if (fonts[f].shape) shaped = (long)f; + } FT_Library library = NULL; FT_Face *faces = calloc(font_count + 1, sizeof(*faces)); if (font_count && FT_Init_FreeType(&library)) fail("cannot start FreeType"); @@ -553,6 +646,23 @@ static int build(int argc, char **argv) { uint32_t **lists = calloc(font_count + 1, sizeof(*lists)); size_t *counts = calloc(font_count + 1, sizeof(*counts)); for (size_t f = 0; f < font_count; ++f) capacity += counts[f] = codes_of(fonts[f].codes, &lists[f]); + /* The shaped font's section, and the glyphs shaping reaches. */ + VegaSection section = {0}; + hb_face_t *hb_face = NULL; + hb_set_t *reached = hb_set_create(); + if (shaped >= 0) { + uint32_t scripts[64]; + size_t script_count = script_tags(fonts[shaped].shape, scripts, 64); + hb_blob_t *blob = hb_blob_create_from_file_or_fail(fonts[shaped].path); + if (!blob) fail("cannot read a font to shape"); + hb_face = hb_face_create(blob, (unsigned)fonts[shaped].face); + hb_blob_destroy(blob); + char error[160]; + if (!vega_shaping_compile(hb_face, scripts, script_count, lists[shaped], counts[shaped], §ion, reached, error, + sizeof(error))) + fail(error); + capacity += hb_set_get_population(reached); + } Built *built = calloc(capacity, sizeof(*built)); Path path = {.font_scale = 1}; size_t made = 0; @@ -573,7 +683,22 @@ static int build(int argc, char **argv) { } close_path(&path); long advance = lround((double)face->glyph->metrics.horiAdvance * units / face->units_per_EM); - built[made++] = (Built){lists[f][i], first, path.count - first, (int16_t)(advance > INT16_MAX ? INT16_MAX : advance)}; + built[made++] = (Built){lists[f][i], first, path.count - first, (int16_t)(advance > INT16_MAX ? INT16_MAX : advance), + (int)f, (long)glyph}; + } + if ((long)f != shaped) continue; + for (hb_codepoint_t glyph = HB_SET_VALUE_INVALID; hb_set_next(reached, &glyph);) { + if (FT_Load_Glyph(face, glyph, FT_LOAD_NO_SCALE)) fail("cannot load a glyph shaping reaches"); + size_t first = path.count; + path.open = false; + if (face->glyph->format == FT_GLYPH_FORMAT_OUTLINE) { + FT_Outline_Transform(&face->glyph->outline, &(FT_Matrix){0x20000, 0, 0, 0x20000}); + if (FT_Outline_Decompose(&face->glyph->outline, &walk, &path)) fail("cannot walk an outline"); + } + close_path(&path); + long advance = lround((double)face->glyph->metrics.horiAdvance * units / face->units_per_EM); + built[made++] = (Built){VEGA_GLYPH_SYMBOLS + glyph, first, path.count - first, + (int16_t)(advance > INT16_MAX ? INT16_MAX : advance), (int)f, (long)glyph}; } } for (size_t i = 0; i < icon_count; ++i) { @@ -583,12 +708,28 @@ static int build(int argc, char **argv) { path.open = false; int16_t advance; svg_icon(&path, equals + 1, (uint16_t)units, &advance); - built[made++] = (Built){(uint32_t)strtoul(icons[i], NULL, 0), first, path.count - first, advance}; + built[made++] = (Built){(uint32_t)strtoul(icons[i], NULL, 0), first, path.count - first, advance, -1, -1}; } /* The first font's line as FreeType reports it (hhea or typo metrics). */ long line[2] = {font_count ? lround((double)faces[0]->ascender * units / faces[0]->units_per_EM) : 0, font_count ? lround((double)faces[0]->descender * units / faces[0]->units_per_EM) : 0}; - write_symbols(out, (uint16_t)units, line, built, made, &path); + write_symbols(out, (uint16_t)units, line, built, made, &path, shaped >= 0 ? §ion : NULL); + if (shaped >= 0) { + /* The file refuses to exist if its shaping differs from HarfBuzz's. */ + char *bytes; + VegaSymbols check = open_symbols(out, &bytes); + hb_font_t *font = hb_font_create(hb_face); + bool same = check_shaping(&check, font, lists[shaped], counts[shaped], runs, 1); + hb_font_destroy(font); + free(bytes); + if (!same) { + unlink(out); + fail("shaping differs from HarfBuzz's: the file is not written"); + } + hb_face_destroy(hb_face); + free(section.bytes); + } + hb_set_destroy(reached); for (size_t f = 0; f < font_count; ++f) { FT_Done_Face(faces[f]); free(lists[f]); @@ -926,12 +1067,96 @@ static int gpu(int argc, char **argv) { return 0; } +/* Check a file's shaping against HarfBuzz with the font it was built from, + * on runs made of the codes it has symbols for. */ +static int shape_check(int argc, char **argv) { + if (argc < 4) fail("usage: vega-symbols shape-check FONT.ttf OUT.vsym [--face N] [--runs N] [--seed N]"); + long face_index = 0; + size_t runs = 20000; + uint64_t seed = 1; + for (int i = 4; i + 1 < argc; i += 2) { + if (!strcmp(argv[i], "--face")) face_index = strtol(argv[i + 1], NULL, 10); + else if (!strcmp(argv[i], "--runs")) runs = strtoul(argv[i + 1], NULL, 10); + else if (!strcmp(argv[i], "--seed")) seed = strtoull(argv[i + 1], NULL, 10); + else fail("shape-check takes --face, --runs and --seed"); + } + char *bytes; + VegaSymbols s = open_symbols(argv[3], &bytes); + uint32_t *codes = malloc((s.symbols + 1) * sizeof(*codes)); + size_t count = 0; + for (uint32_t i = 0; i < s.symbols; ++i) { + uint32_t code = vega_symbol_at(&s, i).code; + if (code < VEGA_GLYPH_SYMBOLS) codes[count++] = code; + } + hb_blob_t *blob = hb_blob_create_from_file_or_fail(argv[2]); + if (!blob) fail("cannot read the font"); + hb_face_t *face = hb_face_create(blob, (unsigned)face_index); + hb_font_t *font = hb_font_create(face); + bool same = check_shaping(&s, font, codes, count, runs, seed); + hb_font_destroy(font); + hb_face_destroy(face); + hb_blob_destroy(blob); + free(codes); + free(bytes); + return same ? 0 : 1; +} + +/* Shape one run with both and print them: vega-symbols shape FONT.ttf + * OUT.vsym SCRIPT ltr|rtl 0066,0069,... */ +static int shape_one(int argc, char **argv) { + if (argc != 7) fail("usage: vega-symbols shape FONT.ttf OUT.vsym SCRIPT ltr|rtl CODE,CODE,..."); + char *bytes, error[128]; + VegaSymbols s = open_symbols(argv[3], &bytes); + VegaShaping shaping; + if (!s.shaping || !vega_shaping_open(&shaping, s.shaping, s.shaping_size, error, sizeof(error))) fail("no shaping"); + uint32_t script, codes[256]; + script_tags(argv[4], &script, 1); + int direction = !strcmp(argv[5], "rtl") ? VEGA_SHAPE_RTL : VEGA_SHAPE_LTR; + size_t count = 0; + for (char *p = argv[6]; *p && count < 256;) { + codes[count++] = (uint32_t)strtoul(p, &p, 16); + if (*p == ',') ++p; + } + VegaShaper *shaper = vega_shaper_new(); + const VegaShaped *ours; + long n = vega_shape(shaper, &shaping, codes, count, script, direction, &ours); + printf("vega "); + for (long i = 0; i < n; ++i) + printf(" %u@%u(%d+%d,%d)", ours[i].glyph, ours[i].cluster, ours[i].x_advance, ours[i].x_offset, ours[i].y_offset); + printf("\n"); + hb_blob_t *blob = hb_blob_create_from_file_or_fail(argv[2]); + hb_face_t *face = hb_face_create(blob, 0); + hb_font_t *font = hb_font_create(face); + hb_buffer_t *buffer = hb_buffer_create(); + hb_buffer_add_codepoints(buffer, codes, (int)count, 0, (int)count); + hb_buffer_set_direction(buffer, direction == VEGA_SHAPE_RTL ? HB_DIRECTION_RTL : HB_DIRECTION_LTR); + hb_buffer_set_script(buffer, hb_script_from_iso15924_tag(script)); + hb_shape(font, buffer, NULL, 0); + unsigned m; + hb_glyph_info_t *info = hb_buffer_get_glyph_infos(buffer, &m); + hb_glyph_position_t *pos = hb_buffer_get_glyph_positions(buffer, &m); + printf("harfbuzz"); + for (unsigned i = 0; i < m; ++i) + printf(" %u@%u(%d+%d,%d)", info[i].codepoint, info[i].cluster, pos[i].x_advance, pos[i].x_offset, pos[i].y_offset); + printf("\n"); + hb_buffer_destroy(buffer); + hb_font_destroy(font); + hb_face_destroy(face); + hb_blob_destroy(blob); + vega_shaper_free(shaper); + vega_shaping_close(&shaping); + free(bytes); + return 0; +} + int main(int argc, char **argv) { + if (argc > 1 && !strcmp(argv[1], "shape")) return shape_one(argc, argv); if (argc > 1 && !strcmp(argv[1], "build")) return build(argc, argv); + if (argc > 1 && !strcmp(argv[1], "shape-check")) return shape_check(argc, argv); if (argc > 1 && !strcmp(argv[1], "compare")) return compare(argc, argv); if (argc > 1 && !strcmp(argv[1], "info")) return info(argc, argv); if (argc > 1 && !strcmp(argv[1], "render")) return render(argc, argv); if (argc > 1 && !strcmp(argv[1], "gpu")) return gpu(argc, argv); - fail("vega-symbols build|compare|info|render|gpu ..."); + fail("vega-symbols build|shape-check|compare|info|render|gpu ..."); return 2; } diff --git a/symbols/symbols.c b/symbols/symbols.c index 2ee5d5e..71e617c 100644 --- a/symbols/symbols.c +++ b/symbols/symbols.c @@ -4,7 +4,9 @@ #include #include -static const unsigned char magic[8] = {'V', 'E', 'G', 'A', 'S', 'Y', 'M', '3'}; +/* VEGASYM3, or VEGASYM4: flags in the header (VEGA_SYMBOLS_SHAPING) and + * what they name after the points. */ +static const unsigned char magic[7] = {'V', 'E', 'G', 'A', 'S', 'Y', 'M'}; static uint16_t u16(const unsigned char *p) { return (uint16_t)(p[0] | p[1] << 8); } static int16_t i16(const unsigned char *p) { return (int16_t)u16(p); } @@ -28,10 +30,19 @@ VegaPoint vega_symbols_point(const VegaSymbols *s, uint32_t index) { #define REFUSE(...) do { snprintf(error, error_size, __VA_ARGS__); return false; } while (0) bool vega_symbols_open(VegaSymbols *s, const unsigned char *bytes, size_t size, char *error, size_t error_size) { - if (size < VEGA_SYMBOLS_HEADER || memcmp(bytes, magic, sizeof(magic))) REFUSE("not a symbol file"); - *s = (VegaSymbols){bytes, size, u16(bytes + 8), i16(bytes + 24), i16(bytes + 26), u32(bytes + 12), u32(bytes + 16)}; + if (size < VEGA_SYMBOLS_HEADER || memcmp(bytes, magic, sizeof(magic)) || (bytes[7] != '3' && bytes[7] != '4')) + REFUSE("not a symbol file"); + *s = (VegaSymbols){bytes, size, u16(bytes + 8), i16(bytes + 24), i16(bytes + 26), u32(bytes + 12), u32(bytes + 16), NULL, 0}; uint64_t expected = VEGA_SYMBOLS_HEADER + (uint64_t)s->symbols * VEGA_SYMBOL_BYTES + (uint64_t)s->points * VEGA_POINT_BYTES; - if (u16(bytes + 10) || !s->units || s->ascent < s->descent) REFUSE("header"); + unsigned flags = u16(bytes + 10); + if ((flags && bytes[7] == '3') || (flags & ~(unsigned)VEGA_SYMBOLS_SHAPING) || !s->units || s->ascent < s->descent) + REFUSE("header"); + if (flags & VEGA_SYMBOLS_SHAPING) { + if (expected > size || size - expected < 8) REFUSE("size: no room for the shaping section"); + s->shaping = bytes + expected; + s->shaping_size = u32(s->shaping + 4); + expected += s->shaping_size; + } if (u32(bytes + 20) != size || expected != size) REFUSE("size: %zu bytes for %u symbols and %u points", size, s->symbols, s->points); for (uint32_t i = 0; i < s->symbols; ++i) { VegaSymbol symbol = vega_symbol_at(s, i); diff --git a/symbols/symbols.h b/symbols/symbols.h index 32f48d0..f6a6175 100644 --- a/symbols/symbols.h +++ b/symbols/symbols.h @@ -26,7 +26,14 @@ typedef struct { uint16_t units; /* per em */ int16_t ascent, descent; /* a font's line, in units from the baseline, y up (0 and 0 for icons) */ uint32_t symbols, points; + /* A font's shaping (text/shape.h), when the file carries it: after the + * points, a flag in the header saying so (VEGASYM4). */ + const unsigned char *shaping; + size_t shaping_size; } VegaSymbols; +/* The glyphs shaping gives are the shaped font's own: glyph g is the symbol + * VEGA_GLYPH_SYMBOLS + g (past every code point). */ +enum { VEGA_GLYPH_SYMBOLS = 0x110000, VEGA_SYMBOLS_SHAPING = 1 }; /* Verify bytes as a symbol file (kept, not copied); false with why. What * reading needs is checked, per symbol: after this no read leaves the file diff --git a/text/shape-build.c b/text/shape-build.c new file mode 100644 index 0000000..c5fd237 --- /dev/null +++ b/text/shape-build.c @@ -0,0 +1,723 @@ +/* Building shaping sections with HarfBuzz (text/shape-build.h): plans as + * HarfBuzz's planner compiles them (hb-ot-shape.cc's features, hb-ot-map.cc's + * masks and stages), what the section carries, and a check of it against + * HarfBuzz on random runs. */ +#include "shape-build.h" +#include "text.h" +#include +#include +#include +#include + +/* ---- The planner (hb_ot_map_builder_t) */ + +enum { F_NONE = 0, F_GLOBAL = 1, F_HAS_FALLBACK = 2, F_MANUAL_ZWNJ = 4, F_MANUAL_ZWJ = 8, F_GLOBAL_SEARCH = 16, + F_RANDOM = 32, F_PER_SYLLABLE = 64 }; +enum { MAX_VALUE = 255, GLOBAL_BIT_SHIFT = 31, MAX_BITS = 8, MAX_FEATURES = 96, MAX_STAGES = 32 }; +#define GLOBAL_BIT_MASK (1u << GLOBAL_BIT_SHIFT) +#define NO_FEATURE HB_OT_LAYOUT_NO_FEATURE_INDEX +#define TAG(s) HB_TAG((s)[0], (s)[1], (s)[2], (s)[3]) + +typedef struct { hb_tag_t tag; unsigned seq, max_value, flags, default_value, stage[2]; } FeatureInfo; +typedef struct { + hb_tag_t tag; + unsigned index[2], stage[2], shift; + uint32_t mask, one_mask; + bool auto_zwnj, auto_zwj, random, per_syllable, needs_fallback; +} FeatureMap; +typedef struct { unsigned index; uint32_t mask; bool auto_zwnj, auto_zwj, random, per_syllable; } LookupMap; + +typedef struct { + hb_face_t *face; + unsigned script_index[2], language_index[2]; + hb_tag_t chosen_script[2]; + FeatureInfo infos[MAX_FEATURES]; + unsigned info_count, current_stage[2]; + bool is_simple; + /* compiled */ + FeatureMap features[MAX_FEATURES]; + unsigned feature_count; + uint32_t global_mask; + LookupMap *lookups[2]; + unsigned lookup_count[2]; +} Map; + +static const hb_tag_t table_tags[2] = {HB_OT_TAG_GSUB, HB_OT_TAG_GPOS}; + +static void add_feature(Map *m, hb_tag_t tag, unsigned flags, unsigned value) { + if (!tag || m->info_count == MAX_FEATURES) return; + m->infos[m->info_count] = (FeatureInfo){tag, m->info_count, value, flags, flags & F_GLOBAL ? value : 0, + {m->current_stage[0], m->current_stage[1]}}; + m->info_count++; +} +static void enable_feature(Map *m, hb_tag_t tag, unsigned flags, unsigned value) { add_feature(m, tag, flags | F_GLOBAL, value); } +static void add_gsub_pause(Map *m) { m->current_stage[0]++; } + +static bool has_feature(const Map *m, hb_tag_t tag) { + for (int t = 0; t < 2; ++t) + if (hb_ot_layout_language_find_feature(m->face, table_tags[t], m->script_index[t], m->language_index[t], tag, NULL)) + return true; + return false; +} + +/* The first feature of the table with tag, whatever its script. */ +static bool table_find_feature(hb_face_t *face, hb_tag_t table, hb_tag_t tag, unsigned *index) { + hb_tag_t tags[64]; + unsigned offset = 0, count; + do { + count = 64; + hb_ot_layout_table_get_feature_tags(face, table, offset, &count, tags); + for (unsigned i = 0; i < count; ++i) + if (tags[i] == tag) { + *index = offset + i; + return true; + } + offset += count; + } while (count == 64); + *index = NO_FEATURE; + return false; +} + +static int by_tag_seq(const void *a, const void *b) { + const FeatureInfo *x = a, *y = b; + return x->tag != y->tag ? (x->tag < y->tag ? -1 : 1) : (x->seq > y->seq) - (x->seq < y->seq); +} +static int by_tag(const void *a, const void *b) { + const FeatureMap *x = a, *y = b; + return (x->tag > y->tag) - (x->tag < y->tag); +} + +static const FeatureMap *find_feature(const Map *m, hb_tag_t tag) { + for (unsigned i = 0; i < m->feature_count; ++i) + if (m->features[i].tag == tag) return &m->features[i]; + return NULL; +} +static uint32_t one_mask(const Map *m, const char *tag) { + const FeatureMap *f = find_feature(m, TAG(tag)); + return f ? f->one_mask : 0; +} + +static bool add_lookups(Map *m, int table, unsigned feature_index, uint32_t mask, bool auto_zwnj, bool auto_zwj, + bool random, bool per_syllable, unsigned *allocated) { + unsigned table_lookup_count = hb_ot_layout_table_get_lookup_count(m->face, table_tags[table]); + unsigned indices[32], offset = 0, len; + do { + len = 32; + hb_ot_layout_feature_get_lookups(m->face, table_tags[table], feature_index, offset, &len, indices); + for (unsigned i = 0; i < len; ++i) { + if (indices[i] >= table_lookup_count) continue; + if (m->lookup_count[table] == *allocated) { + *allocated = *allocated ? 2 * *allocated : 64; + LookupMap *grown = realloc(m->lookups[table], *allocated * sizeof(*grown)); + if (!grown) return false; + m->lookups[table] = grown; + } + m->lookups[table][m->lookup_count[table]++] = + (LookupMap){indices[i], mask, auto_zwnj, auto_zwj, random, per_syllable}; + } + offset += len; + } while (len == 32); + return true; +} + +static bool compile_map(Map *m) { + unsigned required_index[2], required_stage[2] = {0, 0}; + hb_tag_t required_tag[2]; + for (int t = 0; t < 2; ++t) + if (!hb_ot_layout_language_get_required_feature(m->face, table_tags[t], m->script_index[t], m->language_index[t], + &required_index[t], &required_tag[t])) + required_index[t] = NO_FEATURE, required_tag[t] = 0; + /* Sort features and merge duplicates. */ + if (m->info_count) { + if (!m->is_simple) qsort(m->infos, m->info_count, sizeof(*m->infos), by_tag_seq); + FeatureInfo *f = m->infos; + unsigned j = 0; + for (unsigned i = 1; i < m->info_count; ++i) + if (f[i].tag != f[j].tag) f[++j] = f[i]; + else { + if (f[i].flags & F_GLOBAL) { + f[j].flags |= F_GLOBAL; + f[j].max_value = f[i].max_value; + f[j].default_value = f[i].default_value; + } else { + if (f[j].flags & F_GLOBAL) f[j].flags ^= F_GLOBAL; + if (f[i].max_value > f[j].max_value) f[j].max_value = f[i].max_value; + } + f[j].flags |= f[i].flags & F_HAS_FALLBACK; + for (int t = 0; t < 2; ++t) + if (f[i].stage[t] < f[j].stage[t]) f[j].stage[t] = f[i].stage[t]; + } + m->info_count = j + 1; + } + /* Allocate bits. */ + m->global_mask = GLOBAL_BIT_MASK; + unsigned next_bit = 3 + 1; /* after the glyph flags HarfBuzz keeps in the mask */ + for (unsigned i = 0; i < m->info_count; ++i) { + const FeatureInfo *info = &m->infos[i]; + unsigned bits_needed = 0; + if (!((info->flags & F_GLOBAL) && info->max_value == 1)) { + unsigned storage = 0; + for (unsigned v = info->max_value; v; v >>= 1) storage++; + bits_needed = storage < MAX_BITS ? storage : MAX_BITS; + } + if (!info->max_value || next_bit + bits_needed >= GLOBAL_BIT_SHIFT) continue; + bool found = false; + unsigned index[2]; + for (int t = 0; t < 2; ++t) { + if (required_tag[t] == info->tag) required_stage[t] = info->stage[t]; + if (hb_ot_layout_language_find_feature(m->face, table_tags[t], m->script_index[t], m->language_index[t], + info->tag, &index[t])) + found = true; + else + index[t] = NO_FEATURE; + } + if (!found && (info->flags & F_GLOBAL_SEARCH)) + for (int t = 0; t < 2; ++t) + found |= table_find_feature(m->face, table_tags[t], info->tag, &index[t]); + if (!found && !(info->flags & F_HAS_FALLBACK)) continue; + FeatureMap *map = &m->features[m->feature_count++]; + *map = (FeatureMap){info->tag, {index[0], index[1]}, {info->stage[0], info->stage[1]}, 0, 0, 0, + !(info->flags & F_MANUAL_ZWNJ), !(info->flags & F_MANUAL_ZWJ), info->flags & F_RANDOM, + info->flags & F_PER_SYLLABLE, !found}; + if ((info->flags & F_GLOBAL) && info->max_value == 1) { + map->shift = GLOBAL_BIT_SHIFT; + map->mask = GLOBAL_BIT_MASK; + } else { + map->shift = next_bit; + map->mask = (1u << (next_bit + bits_needed)) - (1u << next_bit); + next_bit += bits_needed; + m->global_mask |= (info->default_value << map->shift) & map->mask; + } + map->one_mask = (1u << map->shift) & map->mask; + } + if (m->is_simple) qsort(m->features, m->feature_count, sizeof(*m->features), by_tag); + /* The final pause, then each stage's lookups: sorted, duplicates merged. */ + m->current_stage[0]++; + m->current_stage[1]++; + for (int t = 0; t < 2; ++t) { + unsigned allocated = 0, last = 0; + for (unsigned stage = 0; stage < m->current_stage[t]; ++stage) { + if (required_index[t] != NO_FEATURE && required_stage[t] == stage && + !add_lookups(m, t, required_index[t], GLOBAL_BIT_MASK, true, true, false, false, &allocated)) + return false; + for (unsigned i = 0; i < m->feature_count; ++i) { + const FeatureMap *f = &m->features[i]; + if (f->stage[t] == stage && + !add_lookups(m, t, f->index[t], f->mask, f->auto_zwnj, f->auto_zwj, f->random, f->per_syllable, + &allocated)) + return false; + } + LookupMap *l = m->lookups[t]; + unsigned n = m->lookup_count[t]; + if (last + 1 < n) { + for (unsigned i = last + 1; i < n; ++i) /* stable, by index */ + for (unsigned k = i; k > last && l[k - 1].index > l[k].index; --k) { + LookupMap swap = l[k]; + l[k] = l[k - 1]; + l[k - 1] = swap; + } + unsigned j = last; + for (unsigned i = j + 1; i < n; ++i) + if (l[i].index != l[j].index) l[++j] = l[i]; + else { + l[j].mask |= l[i].mask; + l[j].auto_zwnj &= l[i].auto_zwnj; + l[j].auto_zwj &= l[i].auto_zwj; + } + m->lookup_count[t] = j + 1; + } + last = m->lookup_count[t]; + } + } + return true; +} + +/* The scripts HarfBuzz gives the Universal Shaping Engine, or the default + * shaper when the font has no script of their own. */ +static const char *const use_scripts[] = { + "Tibt", "Mong", "Sinh", "Buhd", "Hano", "Tglg", "Tagb", "Limb", "Tale", "Bugi", "Khar", "Sylo", "Tfng", "Bali", + "Nkoo", "Phag", "Cham", "Kali", "Lepc", "Rjng", "Saur", "Sund", "Egyp", "Java", "Kthi", "Mtei", "Lana", "Tavt", + "Batk", "Brah", "Mand", "Cakm", "Plrd", "Shrd", "Takr", "Dupl", "Gran", "Khoj", "Sind", "Mahj", "Mani", "Modi", + "Hmng", "Phlp", "Sidd", "Tirh", "Ahom", "Mult", "Adlm", "Bhks", "Marc", "Newa", "Gonm", "Soyo", "Zanb", "Dogr", + "Gong", "Rohg", "Maka", "Medf", "Sogo", "Sogd", "Elym", "Nand", "Hmnp", "Wcho", "Chrs", "Diak", "Kits", "Yezi", + "Cpmn", "Ougr", "Tnsa", "Toto", "Vith", "Kawi", "Nagm", "Gara", "Gukh", "Krai", "Onao", "Sunu", "Todr", "Tutg"}; +static const char *const indic_scripts[] = {"Beng", "Deva", "Gujr", "Guru", "Knda", "Mlym", "Orya", "Taml", "Telu"}; + +static bool listed(const char *const *list, size_t count, uint32_t script) { + for (size_t i = 0; i < count; ++i) + if (TAG(list[i]) == script) return true; + return false; +} + +/* hb_ot_shaper_categorize, for the shapers the runtime has; -1 for others. */ +static int categorize(uint32_t script, hb_tag_t gsub_script) { + bool dflt = gsub_script == HB_OT_TAG_DEFAULT_SCRIPT || gsub_script == TAG("latn"); + if (script == TAG("Arab")) return VEGA_SHAPER_ARABIC; + if (script == TAG("Hebr")) return VEGA_SHAPER_HEBREW; + if (script == TAG("Syrc") || script == TAG("Thai") || script == TAG("Laoo") || script == TAG("Hang") || + script == TAG("Khmr") || script == TAG("Qaag")) + return -1; + if (listed(indic_scripts, sizeof(indic_scripts) / sizeof(*indic_scripts), script) || + listed(use_scripts, sizeof(use_scripts) / sizeof(*use_scripts), script)) + return dflt ? VEGA_SHAPER_DEFAULT : -1; + if (script == TAG("Mymr")) return dflt || gsub_script == TAG("mymr") ? VEGA_SHAPER_DEFAULT : -1; + return VEGA_SHAPER_DEFAULT; +} + +static bool has_table(hb_face_t *face, hb_tag_t tag) { + hb_blob_t *blob = hb_face_reference_table(face, tag); + bool has = hb_blob_get_length(blob) > 0; + hb_blob_destroy(blob); + return has; +} + +typedef struct { + uint32_t script; + int direction, native, shaper, flags; + uint32_t global_mask, masks[VEGA_PLAN_MASKS]; + LookupMap *lookups[2]; + unsigned lookup_count[2]; +} Plan; + +#define FAIL(...) \ + do { \ + snprintf(error, error_size, __VA_ARGS__); \ + goto fail; \ + } while (0) + +static bool plan_for(hb_face_t *face, uint32_t script_tag, int direction, Plan *plan, char *error, size_t error_size) { + Map *m = calloc(1, sizeof(*m)); + if (!m) { + snprintf(error, error_size, "out of memory"); + return false; + } + m->face = face; + hb_script_t script = hb_script_from_iso15924_tag(script_tag); + char name[5] = {(char)(script_tag >> 24), (char)(script_tag >> 16), (char)(script_tag >> 8), (char)script_tag, 0}; + unsigned script_count = HB_OT_MAX_TAGS_PER_SCRIPT, language_count = HB_OT_MAX_TAGS_PER_LANGUAGE; + hb_tag_t script_tags[HB_OT_MAX_TAGS_PER_SCRIPT], language_tags[HB_OT_MAX_TAGS_PER_LANGUAGE]; + hb_ot_tags_from_script_and_language(script, HB_LANGUAGE_INVALID, &script_count, script_tags, &language_count, + language_tags); + for (int t = 0; t < 2; ++t) { + hb_ot_layout_table_select_script(face, table_tags[t], script_count, script_tags, &m->script_index[t], + &m->chosen_script[t]); + hb_ot_layout_script_select_language(face, table_tags[t], m->script_index[t], language_count, language_tags, + &m->language_index[t]); + } + int shaper = categorize(script_tag, m->chosen_script[0]); + if (shaper < 0) FAIL("%s: HarfBuzz shapes it with a shaper Vega does not have", name); + if (has_table(face, HB_TAG('m', 'o', 'r', 'x')) || has_table(face, HB_TAG('k', 'e', 'r', 'x')) || + has_table(face, HB_TAG('t', 'r', 'a', 'k'))) + FAIL("%s: the font has AAT tables (morx, kerx, trak)", name); + + /* hb_ot_shape_collect_features */ + m->is_simple = true; + enable_feature(m, TAG("rvrn"), F_NONE, 1); + add_gsub_pause(m); + if (direction == VEGA_SHAPE_LTR) { + enable_feature(m, TAG("ltra"), F_NONE, 1); + enable_feature(m, TAG("ltrm"), F_NONE, 1); + } else { + enable_feature(m, TAG("rtla"), F_NONE, 1); + add_feature(m, TAG("rtlm"), F_NONE, 1); + } + add_feature(m, TAG("frac"), F_NONE, 1); + add_feature(m, TAG("numr"), F_NONE, 1); + add_feature(m, TAG("dnom"), F_NONE, 1); + enable_feature(m, TAG("rand"), F_RANDOM, MAX_VALUE); + enable_feature(m, TAG("trak"), F_HAS_FALLBACK, 1); + enable_feature(m, TAG("Harf"), F_NONE, 1); + enable_feature(m, TAG("HARF"), F_NONE, 1); + static const char *const arabic_features[7] = {"isol", "fina", "fin2", "fin3", "medi", "med2", "init"}; + if (shaper == VEGA_SHAPER_ARABIC) { + m->is_simple = false; + enable_feature(m, TAG("stch"), F_NONE, 1); + add_gsub_pause(m); /* record_stch */ + enable_feature(m, TAG("ccmp"), F_MANUAL_ZWJ, 1); + enable_feature(m, TAG("locl"), F_MANUAL_ZWJ, 1); + add_gsub_pause(m); + for (int i = 0; i < 7; ++i) { + bool syriac = arabic_features[i][3] == '2' || arabic_features[i][3] == '3'; + add_feature(m, TAG(arabic_features[i]), F_MANUAL_ZWJ | (script == HB_SCRIPT_ARABIC && !syriac ? F_HAS_FALLBACK : 0), 1); + add_gsub_pause(m); + } + enable_feature(m, TAG("rlig"), F_MANUAL_ZWJ | F_HAS_FALLBACK, 1); + if (script == HB_SCRIPT_ARABIC) add_gsub_pause(m); /* arabic_fallback_shape */ + enable_feature(m, TAG("calt"), F_MANUAL_ZWJ, 1); + if (!has_feature(m, TAG("rclt"))) add_gsub_pause(m); + enable_feature(m, TAG("liga"), F_MANUAL_ZWJ, 1); + enable_feature(m, TAG("clig"), F_MANUAL_ZWJ, 1); + enable_feature(m, TAG("mset"), F_MANUAL_ZWJ, 1); + } + enable_feature(m, TAG("Buzz"), F_NONE, 1); + enable_feature(m, TAG("BUZZ"), F_NONE, 1); + static const char *const common[] = {"abvm", "blwm", "ccmp", "locl", "mark", "mkmk", "rlig"}; + for (int i = 0; i < 7; ++i) + add_feature(m, TAG(common[i]), F_GLOBAL | (i == 4 || i == 5 ? F_MANUAL_ZWNJ | F_MANUAL_ZWJ : 0), 1); + static const char *const horizontal[] = {"calt", "clig", "curs", "dist", "kern", "liga", "rclt"}; + for (int i = 0; i < 7; ++i) add_feature(m, TAG(horizontal[i]), F_GLOBAL | (i == 4 ? F_HAS_FALLBACK : 0), 1); + if (!compile_map(m)) FAIL("out of memory"); + + /* hb_ot_shape_planner_t::compile */ + const FeatureMap *kern = find_feature(m, TAG("kern")); + bool has_gpos_kern = kern && kern->index[1] != NO_FEATURE; + bool disable_gpos = shaper == VEGA_SHAPER_HEBREW && m->chosen_script[1] != TAG("hebr"); + bool apply_gpos = !disable_gpos && hb_ot_layout_has_positioning(face); + if ((!has_gpos_kern || !apply_gpos) && has_table(face, HB_TAG('k', 'e', 'r', 'n'))) + FAIL("%s: HarfBuzz would kern with the font's kern table", name); + if (!apply_gpos) FAIL("%s: HarfBuzz would position without GPOS (fallback positioning)", name); + if (shaper == VEGA_SHAPER_ARABIC) { + if (one_mask(m, "stch")) FAIL("%s: the font stretches (stch)", name); + bool fallback = script == HB_SCRIPT_ARABIC; + for (int i = 0; i < 7; ++i) { + const FeatureMap *f = find_feature(m, TAG(arabic_features[i])); + bool syriac = arabic_features[i][3] == '2' || arabic_features[i][3] == '3'; + fallback = fallback && (syriac || (f && f->needs_fallback)); + } + if (fallback) FAIL("%s: the font lacks Arabic's forms (HarfBuzz would fall back)", name); + } + hb_direction_t native = hb_script_get_horizontal_direction(script); + uint32_t frac = one_mask(m, "frac"), numr = one_mask(m, "numr"), dnom = one_mask(m, "dnom"); + *plan = (Plan){script_tag, direction, native == HB_DIRECTION_LTR ? VEGA_SHAPE_LTR : native == HB_DIRECTION_RTL ? VEGA_SHAPE_RTL : 0, + shaper, + VEGA_PLAN_GPOS | VEGA_PLAN_ZERO_MARKS | (hb_ot_layout_has_glyph_classes(face) ? 0 : VEGA_PLAN_GUESS_CLASSES) | + (one_mask(m, "mark") ? VEGA_PLAN_GPOS_MARK : 0) | (frac || (numr && dnom) ? VEGA_PLAN_FRACTIONS : 0), + m->global_mask, {0}, {m->lookups[0], m->lookups[1]}, {m->lookup_count[0], m->lookup_count[1]}}; + for (int i = 0; i < 7; ++i) plan->masks[VEGA_MASK_ISOL + i] = one_mask(m, arabic_features[i]); + plan->masks[VEGA_MASK_RTLM] = one_mask(m, "rtlm"); + plan->masks[VEGA_MASK_FRAC] = frac; + plan->masks[VEGA_MASK_NUMR] = numr; + plan->masks[VEGA_MASK_DNOM] = dnom; + free(m); + return true; +fail: + free(m->lookups[0]); + free(m->lookups[1]); + free(m); + return false; +} + +/* ---- The section */ + +typedef struct { unsigned char *bytes; size_t size, allocated; bool failed; } Out; + +static void put(Out *o, const void *bytes, size_t n) { + if (o->failed) return; + if (o->size + n > o->allocated) { + size_t a = o->allocated ? o->allocated : 4096; + while (a < o->size + n) a *= 2; + unsigned char *grown = realloc(o->bytes, a); + if (!grown) { + o->failed = true; + return; + } + o->bytes = grown; + o->allocated = a; + } + memcpy(o->bytes + o->size, bytes, n); + o->size += n; +} +static void put32(Out *o, uint32_t v) { + unsigned char b[4] = {(unsigned char)v, (unsigned char)(v >> 8), (unsigned char)(v >> 16), (unsigned char)(v >> 24)}; + put(o, b, 4); +} +static void put16(Out *o, uint32_t v) { + unsigned char b[2] = {(unsigned char)v, (unsigned char)(v >> 8)}; + put(o, b, 2); +} +static void align4(Out *o) { + static const unsigned char zero[4] = {0}; + put(o, zero, (4 - o->size % 4) % 4); +} +static void set32(Out *o, size_t at, uint32_t v) { + if (o->failed) return; + for (int i = 0; i < 4; ++i) o->bytes[at + i] = (unsigned char)(v >> (8 * i)); +} + +bool vega_shaping_compile(hb_face_t *face, const uint32_t *scripts, size_t script_count, const uint32_t *codes, + size_t code_count, VegaSection *out, hb_set_t *glyphs, char *error, size_t error_size) { + Plan *plans = calloc(2 * script_count + 1, sizeof(*plans)); + size_t plan_count = 0; + Out o = {0}; + hb_font_t *font = hb_font_create(face); + hb_set_t *unicodes = hb_set_create(); + if (!plans) FAIL("out of memory"); + /* Both directions: a run's comes from bidi, and need not be its script's. */ + for (size_t i = 0; i < script_count; ++i) + for (int d = VEGA_SHAPE_LTR; d <= VEGA_SHAPE_RTL; ++d) { + if (!plan_for(face, scripts[i], d, &plans[plan_count], error, error_size)) goto fail; + plan_count++; + } + unsigned glyph_count = hb_face_get_glyph_count(face); + if (glyph_count > 65535) FAIL("more than 65535 glyphs"); + hb_face_collect_unicodes(face, unicodes); + uint32_t cmap_count = 0; + for (hb_codepoint_t u = HB_SET_VALUE_INVALID; hb_set_next(unicodes, &u);) { + hb_codepoint_t g; + if (hb_font_get_nominal_glyph(font, u, &g) && g) cmap_count++; + } + hb_blob_t *tables[3] = {hb_face_reference_table(face, HB_OT_TAG_GDEF), hb_face_reference_table(face, HB_OT_TAG_GSUB), + hb_face_reference_table(face, HB_OT_TAG_GPOS)}; + /* The header, filled in as the parts land. */ + put(&o, "VSHP", 4); + put32(&o, 0); + put16(&o, hb_face_get_upem(face)); + put16(&o, glyph_count); + for (int i = 0; i < 13; ++i) put32(&o, 0); + set32(&o, 12, cmap_count); + set32(&o, 16, (uint32_t)o.size); + for (hb_codepoint_t u = HB_SET_VALUE_INVALID; hb_set_next(unicodes, &u);) { + hb_codepoint_t g; + if (hb_font_get_nominal_glyph(font, u, &g) && g) { + put32(&o, u); + put32(&o, g); + } + } + set32(&o, 20, (uint32_t)o.size); + for (unsigned g = 0; g < glyph_count; ++g) { + hb_position_t advance = hb_font_get_glyph_h_advance(font, g); + if (advance < 0 || advance > 65535) { + for (int k = 0; k < 3; ++k) hb_blob_destroy(tables[k]); + FAIL("glyph %u: an advance outside 0 to 65535", g); + } + put16(&o, (uint32_t)advance); + } + for (int k = 0; k < 3; ++k) { + align4(&o); + unsigned length; + const char *data = hb_blob_get_data(tables[k], &length); + set32(&o, 24 + 8 * k, length ? (uint32_t)o.size : 0); + set32(&o, 28 + 8 * k, length); + put(&o, data, length); + hb_blob_destroy(tables[k]); + } + align4(&o); + set32(&o, 48, (uint32_t)plan_count); + set32(&o, 52, (uint32_t)o.size); + uint32_t step = 0; + for (size_t i = 0; i < plan_count; ++i) { + const Plan *p = &plans[i]; + put32(&o, p->script); + unsigned char small[4] = {(unsigned char)p->direction, (unsigned char)p->native, (unsigned char)p->shaper, + (unsigned char)p->flags}; + put(&o, small, 4); + put32(&o, p->global_mask); + for (int k = 0; k < VEGA_PLAN_MASKS; ++k) put32(&o, p->masks[k]); + for (int t = 0; t < 2; ++t) { + put32(&o, step); + put32(&o, p->lookup_count[t]); + step += p->lookup_count[t]; + } + } + set32(&o, 56, step); + set32(&o, 60, (uint32_t)o.size); + for (size_t i = 0; i < plan_count; ++i) + for (int t = 0; t < 2; ++t) + for (unsigned k = 0; k < plans[i].lookup_count[t]; ++k) { + const LookupMap *l = &plans[i].lookups[t][k]; + put16(&o, l->index); + unsigned char flags[2] = {(unsigned char)((l->auto_zwnj ? VEGA_STEP_AUTO_ZWNJ : 0) | + (l->auto_zwj ? VEGA_STEP_AUTO_ZWJ : 0) | + (l->random ? VEGA_STEP_RANDOM : 0) | + (l->per_syllable ? VEGA_STEP_PER_SYLLABLE : 0)), + 0}; + put(&o, flags, 2); + put32(&o, l->mask); + } + set32(&o, 4, (uint32_t)o.size); + if (o.failed) FAIL("out of memory"); + + if (glyphs) { + /* What normalization can reach from codes: them, what they + * decompose into and compose to, mirrors, the space; then what GSUB + * can make of those. */ + hb_set_t *wanted = hb_set_create(), *lookups = hb_set_create(); + for (size_t i = 0; i < code_count; ++i) { + hb_set_add(wanted, codes[i]); + uint32_t mirror = vega_mirror(codes[i]); + if (mirror) hb_set_add(wanted, mirror); + const uint32_t *parts; + size_t n = vega_decomposition(codes[i], &parts); + for (size_t k = 0; k < n; ++k) hb_set_add(wanted, parts[k]); + } + static const uint32_t always[] = {0x0020, 0x2010, 0x25CC}; + for (size_t i = 0; i < sizeof(always) / sizeof(*always); ++i) hb_set_add(wanted, always[i]); + for (hb_codepoint_t u = HB_SET_VALUE_INVALID; hb_set_next(unicodes, &u);) { + const uint32_t *parts; + size_t n = vega_decomposition(u, &parts); + bool composed = n > 0; + for (size_t k = 0; k < n && composed; ++k) composed = hb_set_has(wanted, parts[k]); + if (composed) hb_set_add(wanted, u); + } + hb_set_add(glyphs, 0); + for (hb_codepoint_t u = HB_SET_VALUE_INVALID; hb_set_next(wanted, &u);) { + hb_codepoint_t g; + if (hb_font_get_nominal_glyph(font, u, &g)) hb_set_add(glyphs, g); + } + for (size_t i = 0; i < plan_count; ++i) + for (unsigned k = 0; k < plans[i].lookup_count[0]; ++k) hb_set_add(lookups, plans[i].lookups[0][k].index); + hb_ot_layout_lookups_substitute_closure(face, lookups, glyphs); + hb_set_destroy(wanted); + hb_set_destroy(lookups); + } + for (size_t i = 0; i < plan_count; ++i) free(plans[i].lookups[0]), free(plans[i].lookups[1]); + free(plans); + hb_set_destroy(unicodes); + hb_font_destroy(font); + *out = (VegaSection){o.bytes, o.size}; + return true; +fail: + if (plans) + for (size_t i = 0; i < plan_count; ++i) free(plans[i].lookups[0]), free(plans[i].lookups[1]); + free(plans); + free(o.bytes); + hb_set_destroy(unicodes); + hb_font_destroy(font); + return false; +} + +/* ---- The check */ + +static double now(void) { + struct timespec t; + clock_gettime(CLOCK_MONOTONIC, &t); + return (double)t.tv_sec + (double)t.tv_nsec / 1e9; +} + +typedef struct { uint64_t s; } Random; +static uint64_t next_random(Random *r) { + r->s ^= r->s >> 12; + r->s ^= r->s << 25; + r->s ^= r->s >> 27; + return r->s * 0x2545F4914F6CDD1DULL; +} +static uint32_t below(Random *r, uint32_t n) { return n ? (uint32_t)(next_random(r) % n) : 0; } + +typedef struct { uint32_t *items; size_t count; } Pool; +static void pool_add(Pool *p, uint32_t code) { + if (!(p->count & (p->count - 1)) || !p->count) { + uint32_t *grown = realloc(p->items, (p->count ? 2 * p->count : 16) * sizeof(*grown)); + if (!grown) return; + p->items = grown; + } + p->items[p->count++] = code; +} +static uint32_t pick(Random *r, const Pool *p) { return p->items[below(r, (uint32_t)p->count)]; } + +static void describe(FILE *report, const char *who, const VegaShaped *g, unsigned count) { + fprintf(report, " %-8s", who); + for (unsigned i = 0; i < count; ++i) + fprintf(report, " %u@%u(%d,%d+%d,%d)", g[i].glyph, g[i].cluster, g[i].x_advance, g[i].y_advance, g[i].x_offset, + g[i].y_offset); + fprintf(report, "\n"); +} + +void vega_shaping_check(hb_font_t *font, const VegaShaping *s, uint32_t script, int direction, const uint32_t *codes, + size_t code_count, uint64_t seed, size_t runs, VegaShapeCheck *out, FILE *report) { + *out = (VegaShapeCheck){0}; + /* Letters of the script, marks it can take (its own and inherited + * ones), the rest of its characters and Common's (spaces, digits, + * punctuation), and those whose glyphs some substitution starts from. */ + Pool letters = {0}, marks = {0}, others = {0}, hot = {0}; + hb_set_t *inputs = hb_set_create(); + uint32_t common = HB_TAG('Z', 'y', 'y', 'y'), inherited = HB_TAG('Z', 'i', 'n', 'h'); + for (unsigned t = 0; t < s->lookup_count[0]; ++t) + hb_ot_layout_lookup_collect_glyphs(hb_font_get_face(font), HB_OT_TAG_GSUB, t, NULL, inputs, NULL, NULL); + for (size_t i = 0; i < code_count; ++i) { + uint32_t code = codes[i], of = vega_script_code(vega_script(code)); + VegaCategory c = vega_category(code); + hb_codepoint_t glyph; + if (!hb_font_get_nominal_glyph(font, code, &glyph) || c == VEGA_CC || c == VEGA_CS || c == VEGA_CO) continue; + bool mark = c == VEGA_MN || c == VEGA_MC || c == VEGA_ME; + if (mark && (of == script || of == inherited)) pool_add(&marks, code); + else if (!mark && of == script && c >= VEGA_LU && c <= VEGA_LO) pool_add(&letters, code); + else if (!mark && (of == script || of == common) && c != VEGA_ZL && c != VEGA_ZP) pool_add(&others, code); + else continue; + if (hb_set_has(inputs, glyph)) pool_add(&hot, code); + } + hb_set_destroy(inputs); + if (!letters.count) letters = others, others = (Pool){0}; + VegaShaper *shaper = vega_shaper_new(); + hb_buffer_t *buffer = hb_buffer_create(); + Random random = {seed * 0x9E3779B97F4A7C15ULL + script + 1}; + uint32_t text[256]; + bool rtl_script = direction == VEGA_SHAPE_RTL; + unsigned mark_rate = rtl_script ? 40 : 12; + for (size_t run = 0; run < runs && letters.count && shaper; ++run) { + size_t n = 0; + if (below(&random, 4)) { + /* Words: letters (often ones substitution starts from), marks after + * some, spaces and punctuation between. */ + unsigned words = 1 + below(&random, 6); + for (unsigned w = 0; w < words && n < 200; ++w) { + if (w) { + if (others.count && !below(&random, 6)) text[n++] = pick(&random, &others); + text[n++] = ' '; + } + unsigned length = 1 + below(&random, 8); + for (unsigned k = 0; k < length && n < 200; ++k) { + text[n++] = hot.count && below(&random, 3) == 0 ? pick(&random, &hot) : pick(&random, &letters); + if (marks.count && below(&random, 100) < mark_rate) { + text[n++] = pick(&random, &marks); + if (!below(&random, 5)) text[n++] = pick(&random, &marks); + if (!below(&random, 20)) text[n++] = pick(&random, &marks); + } + if (!below(&random, 40)) text[n++] = below(&random, 2) ? 0x200C : 0x200D; + } + } + } else { + /* Anything, in any order: marks first, marks in piles, joiners. */ + unsigned length = 1 + below(&random, 24); + for (unsigned k = 0; k < length; ++k) { + unsigned kind = below(&random, 10); + const Pool *p = kind < 4 ? &letters : kind < 7 && marks.count ? &marks : kind < 8 && hot.count ? &hot : &others; + text[n++] = kind == 9 ? (below(&random, 3) ? ' ' : below(&random, 2) ? 0x200C : 0x200D) + : p->count ? pick(&random, p) : pick(&random, &letters); + } + } + const VegaShaped *ours; + double start = now(); + long count = vega_shape(shaper, s, text, n, script, direction, &ours); + double middle = now(); + hb_buffer_clear_contents(buffer); + hb_buffer_add_codepoints(buffer, text, (int)n, 0, (int)n); + hb_buffer_set_direction(buffer, direction == VEGA_SHAPE_RTL ? HB_DIRECTION_RTL : HB_DIRECTION_LTR); + hb_buffer_set_script(buffer, hb_script_from_iso15924_tag(script)); + hb_shape(font, buffer, NULL, 0); + out->vega_seconds += middle - start; + out->harfbuzz_seconds += now() - middle; + unsigned theirs_count; + hb_glyph_info_t *info = hb_buffer_get_glyph_infos(buffer, &theirs_count); + hb_glyph_position_t *pos = hb_buffer_get_glyph_positions(buffer, &theirs_count); + bool same = count == (long)theirs_count; + for (unsigned i = 0; same && i < theirs_count; ++i) + same = ours[i].glyph == info[i].codepoint && ours[i].cluster == info[i].cluster && + ours[i].x_advance == pos[i].x_advance && ours[i].y_advance == pos[i].y_advance && + ours[i].x_offset == pos[i].x_offset && ours[i].y_offset == pos[i].y_offset; + out->runs++; + out->characters += n; + out->glyphs += theirs_count; + if (same) continue; + if (report && out->differences < 5) { + fprintf(report, "%c%c%c%c run %zu:", (char)(script >> 24), (char)(script >> 16), (char)(script >> 8), + (char)script, run); + for (size_t i = 0; i < n; ++i) fprintf(report, " %04X", text[i]); + fprintf(report, "\n"); + if (count >= 0) describe(report, "vega", ours, (unsigned)count); + else fprintf(report, " vega (failed)\n"); + VegaShaped *theirs = malloc((theirs_count + 1) * sizeof(*theirs)); + for (unsigned i = 0; theirs && i < theirs_count; ++i) + theirs[i] = (VegaShaped){info[i].codepoint, info[i].cluster, pos[i].x_advance, pos[i].y_advance, + pos[i].x_offset, pos[i].y_offset}; + if (theirs) describe(report, "harfbuzz", theirs, theirs_count); + free(theirs); + } + out->differences++; + } + hb_buffer_destroy(buffer); + vega_shaper_free(shaper); + free(letters.items); + free(marks.items); + free(others.items); + free(hot.items); +} diff --git a/text/shape-build.h b/text/shape-build.h new file mode 100644 index 0000000..dd93177 --- /dev/null +++ b/text/shape-build.h @@ -0,0 +1,31 @@ +#ifndef VEGA_SHAPE_BUILD_H +#define VEGA_SHAPE_BUILD_H +#include "shape.h" +#include +#include + +/* Building a shaping section (text/shape.h), and checking it, with + * HarfBuzz: only the build tool links this. */ + +typedef struct { unsigned char *bytes; size_t size; } VegaSection; + +/* A section for face: plans for each script (ISO 15924 tags) and both + * directions, compiled as + * HarfBuzz's planner compiles it. Refuses a script HarfBuzz shapes with a + * shaper other than the default, Arabic and Hebrew ones, or a font that + * needs what those do without GPOS (fallback positioning, 'kern' tables, + * AAT). glyphs, when given, gets every glyph shaping can reach from codes + * (for their outlines). */ +bool vega_shaping_compile(hb_face_t *face, const uint32_t *scripts, size_t script_count, const uint32_t *codes, + size_t code_count, VegaSection *out, hb_set_t *glyphs, char *error, size_t error_size); + +typedef struct { + size_t runs, characters, glyphs, differences; + double vega_seconds, harfbuzz_seconds; /* shaping alone, each */ +} VegaShapeCheck; +/* Shape runs random runs of script (in its plan's direction) made of codes + * with both the section and HarfBuzz, and count the runs that differ (the + * first few are written to report). */ +void vega_shaping_check(hb_font_t *font, const VegaShaping *s, uint32_t script, int direction, const uint32_t *codes, + size_t code_count, uint64_t seed, size_t runs, VegaShapeCheck *out, FILE *report); +#endif diff --git a/text/shape.c b/text/shape.c new file mode 100644 index 0000000..4aedba7 --- /dev/null +++ b/text/shape.c @@ -0,0 +1,2156 @@ +/* Shaping as HarfBuzz 10 does it (text/shape.h), with its default, Arabic + * and Hebrew shapers. The code follows HarfBuzz's own step for step + * (hb-ot-shape.cc, hb-ot-shape-normalize.cc, hb-buffer.cc, hb-ot-layout- + * gsubgpos.hh, the GSUB and GPOS lookups, hb-ot-shaper-arabic.cc and + * -hebrew.cc), under HarfBuzz's names, so that the two read side by side; + * the build tool compares the results with HarfBuzz's (symbols-tool.c). */ +#include "shape.h" +#include "text.h" +#include +#include +#include + +/* ---- OpenType tables, read in place: a read past a table's end gives 0 */ + +static uint32_t get16(VegaTable t, uint32_t at) { + return at < t.size && t.size - at >= 2 ? (uint32_t)t.p[at] << 8 | t.p[at + 1] : 0; +} +static int32_t gets16(VegaTable t, uint32_t at) { return (int16_t)get16(t, at); } +static uint32_t get32(VegaTable t, uint32_t at) { + return at < t.size && t.size - at >= 4 + ? (uint32_t)t.p[at] << 24 | (uint32_t)t.p[at + 1] << 16 | (uint32_t)t.p[at + 2] << 8 | t.p[at + 3] + : 0; +} +/* What the Offset16 at `at` points to from base; 0 is none (a table's + * start is never an offset's target). */ +static uint32_t offset16(VegaTable t, uint32_t base, uint32_t at) { + uint32_t o = get16(t, at); + return o ? base + o : 0; +} + +#define NOT_COVERED 0xFFFFFFFFu + +static uint32_t coverage(VegaTable t, uint32_t at, uint32_t glyph) { + if (!at) return NOT_COVERED; + uint32_t format = get16(t, at), count = get16(t, at + 2), low = 0, high = count; + if (format == 1) + while (low < high) { + uint32_t middle = (low + high) / 2, g = get16(t, at + 4 + 2 * middle); + if (g < glyph) low = middle + 1; + else if (g > glyph) high = middle; + else return middle; + } + else if (format == 2) + while (low < high) { + uint32_t middle = (low + high) / 2, r = at + 4 + 6 * middle; + if (get16(t, r + 2) < glyph) low = middle + 1; + else if (get16(t, r) > glyph) high = middle; + else return get16(t, r + 4) + glyph - get16(t, r); + } + return NOT_COVERED; +} + +static uint32_t class_of(VegaTable t, uint32_t at, uint32_t glyph) { + if (!at) return 0; + uint32_t format = get16(t, at); + if (format == 1) { + uint32_t start = get16(t, at + 2), count = get16(t, at + 4); + return glyph >= start && glyph - start < count ? get16(t, at + 6 + 2 * (glyph - start)) : 0; + } + if (format == 2) { + uint32_t low = 0, high = get16(t, at + 2); + while (low < high) { + uint32_t middle = (low + high) / 2, r = at + 4 + 6 * middle; + if (get16(t, r + 2) < glyph) low = middle + 1; + else if (get16(t, r) > glyph) high = middle; + else return get16(t, r + 4); + } + } + return 0; +} + +/* ---- The section */ + +static uint32_t le32(const unsigned char *p) { return p[0] | p[1] << 8 | (uint32_t)p[2] << 16 | (uint32_t)p[3] << 24; } +static uint16_t le16(const unsigned char *p) { return (uint16_t)(p[0] | p[1] << 8); } +static bool within(size_t size, uint64_t offset, uint64_t length) { return offset <= size && length <= size - offset; } + +#define REFUSE(...) \ + do { \ + snprintf(error, error_size, __VA_ARGS__); \ + vega_shaping_close(s); \ + return false; \ + } while (0) + +/* ---- Digests */ + +static const unsigned digest_shifts[3] = {4, 0, 9}; + +static void digest_add_range(VegaDigest *d, uint32_t first, uint32_t last) { + for (int k = 0; k < 3; ++k) { + uint32_t a = first >> digest_shifts[k], b = last >> digest_shifts[k]; + if (b - a >= 63) d->mask[k] = ~0ULL; + else + for (uint32_t v = a; v <= b; ++v) d->mask[k] |= 1ULL << (v & 63); + } +} +static bool digest_may_have(const VegaDigest *d, uint32_t glyph) { + for (int k = 0; k < 3; ++k) + if (!(d->mask[k] >> (glyph >> digest_shifts[k] & 63) & 1)) return false; + return true; +} +static bool digest_may_intersect(const VegaDigest *a, const VegaDigest *b) { + for (int k = 0; k < 3; ++k) + if (!(a->mask[k] & b->mask[k])) return false; + return true; +} + +static void digest_add_coverage(VegaDigest *d, VegaTable t, uint32_t at) { + if (!at) return; + uint32_t format = get16(t, at), count = get16(t, at + 2); + for (uint32_t i = 0; i < count; ++i) + if (format == 1) digest_add_range(d, get16(t, at + 4 + 2 * i), get16(t, at + 4 + 2 * i)); + else if (format == 2) digest_add_range(d, get16(t, at + 4 + 6 * i), get16(t, at + 6 + 6 * i)); +} + +/* The coverage a subtable starts from: the first glyph's. */ +static uint32_t first_coverage(VegaTable t, int table, const VegaSubtable *st) { + uint32_t at = st->at; + if (!at) return 0; + unsigned context = table ? 7 : 5, chain = table ? 8 : 6; + if ((st->type == context || st->type == chain) && get16(t, at) == 3) { + if (st->type == context) return offset16(t, at, at + 6); + return offset16(t, at, at + 4 + 2 * get16(t, at + 2) + 2); + } + return offset16(t, at, at + 2); +} + +/* A table's lookups, their subtables' types resolved through extensions. */ +static bool resolve_lookups(VegaShaping *s, int table, size_t *subtables, size_t *allocated) { + VegaTable t = table ? s->gpos : s->gsub; + uint32_t list = t.size ? offset16(t, 0, 8) : 0, count = list ? get16(t, list) : 0; + s->lookup_count[table] = count; + if (!(s->lookups[table] = calloc(count ? count : 1, sizeof(VegaLookup)))) return false; + uint16_t extension = table ? 9 : 7; + for (uint32_t i = 0; i < count; ++i) { + uint32_t at = offset16(t, list, list + 2 + 2 * i), n = at ? get16(t, at + 4) : 0; + VegaLookup *l = &s->lookups[table][i]; + l->type = (uint16_t)get16(t, at); + l->flags = (uint16_t)get16(t, at + 2); + l->props = l->flags | (l->flags & 0x10 ? get16(t, at + 6 + 2 * n) << 16 : 0); + l->first = (uint32_t)*subtables; + l->count = n; + for (uint32_t k = 0; k < n; ++k) { + if (*subtables == *allocated) { + *allocated = *allocated ? 2 * *allocated : 64; + VegaSubtable *grown = realloc(s->subtables, *allocated * sizeof(*grown)); + if (!grown) return false; + s->subtables = grown; + } + uint32_t st = offset16(t, at, at + 6 + 2 * k); + uint16_t type = l->type; + if (type == extension) { + uint32_t target = get32(t, st + 4); + type = get16(t, st) == 1 && target ? (uint16_t)get16(t, st + 2) : 0; + st = type && type != extension ? st + target : 0; + if (!st) type = 0; + } + s->subtables[(*subtables)++] = (VegaSubtable){type, st, {{0, 0, 0}}}; + } + /* HarfBuzz: reverse by the lookup's type, or its first extension's. */ + l->reverse = !table && (l->type == 8 || (l->type == 7 && n && s->subtables[l->first].type == 8)); + for (uint32_t k = 0; k < n; ++k) { + VegaSubtable *st = &s->subtables[l->first + k]; + digest_add_coverage(&st->digest, t, first_coverage(t, table, st)); + for (int m = 0; m < 3; ++m) l->digest.mask[m] |= st->digest.mask[m]; + } + } + return true; +} + +bool vega_shaping_open(VegaShaping *s, const unsigned char *bytes, size_t size, char *error, size_t error_size) { + *s = (VegaShaping){0}; + if (size < VEGA_SHAPING_HEADER || memcmp(bytes, "VSHP", 4) || le32(bytes + 4) != size) + REFUSE("not a shaping section"); + s->bytes = bytes; + s->size = size; + s->upem = le16(bytes + 8); + s->glyph_count = le16(bytes + 10); + s->cmap_count = le32(bytes + 12); + uint32_t cmap = le32(bytes + 16), advances = le32(bytes + 20); + if (!s->upem) REFUSE("units per em"); + if (!within(size, cmap, (uint64_t)s->cmap_count * 8)) REFUSE("character map"); + s->cmap = bytes + cmap; + for (uint32_t i = 0; i < s->cmap_count; ++i) { + uint32_t code = le32(s->cmap + 8 * i), glyph = le32(s->cmap + 8 * i + 4); + if ((i && code <= le32(s->cmap + 8 * i - 8)) || !glyph || glyph >= s->glyph_count) + REFUSE("character map: entry %u", i); + } + for (uint32_t i = 0; i < s->cmap_count; ++i) { + uint32_t code = le32(s->cmap + 8 * i); + if (code > 0xFFFF) break; + uint16_t **page = &s->bmp[code >> 8]; + if (!*page && !(*page = calloc(256, sizeof(**page)))) REFUSE("out of memory"); + (*page)[code & 255] = (uint16_t)le32(s->cmap + 8 * i + 4); + } + if (!within(size, advances, 2 * (uint64_t)s->glyph_count)) REFUSE("advances"); + s->advances = bytes + advances; + VegaTable *tables[3] = {&s->gdef, &s->gsub, &s->gpos}; + for (int k = 0; k < 3; ++k) { + uint32_t at = le32(bytes + 24 + 8 * k), n = le32(bytes + 28 + 8 * k); + if (!within(size, at, n)) REFUSE("layout table %d", k); + *tables[k] = (VegaTable){n ? bytes + at : NULL, n}; + } + s->plan_count = le32(bytes + 48); + uint32_t plans = le32(bytes + 52), step_count = le32(bytes + 56), steps = le32(bytes + 60); + if (!within(size, plans, (uint64_t)s->plan_count * VEGA_PLAN_BYTES)) REFUSE("plans"); + if (!within(size, steps, (uint64_t)step_count * VEGA_STEP_BYTES)) REFUSE("steps"); + s->plans = bytes + plans; + s->steps = bytes + steps; + if (s->gdef.size) { + uint32_t minor = get16(s->gdef, 2); + s->glyph_classes = offset16(s->gdef, 0, 4); + s->attach_classes = offset16(s->gdef, 0, 10); + s->mark_sets = minor >= 2 ? offset16(s->gdef, 0, 12) : 0; + } + size_t subtables = 0, allocated = 0; + if (!resolve_lookups(s, 0, &subtables, &allocated) || !resolve_lookups(s, 1, &subtables, &allocated)) + REFUSE("out of memory"); + for (uint32_t i = 0; i < s->plan_count; ++i) { + const unsigned char *p = s->plans + (size_t)i * VEGA_PLAN_BYTES; + uint32_t ranges[2][2] = {{le32(p + 56), le32(p + 60)}, {le32(p + 64), le32(p + 68)}}; + if ((p[4] != VEGA_SHAPE_LTR && p[4] != VEGA_SHAPE_RTL) || p[5] > VEGA_SHAPE_RTL || p[6] > VEGA_SHAPER_HEBREW) + REFUSE("plan %u", i); + for (int table = 0; table < 2; ++table) { + if (ranges[table][0] > step_count || ranges[table][1] > step_count - ranges[table][0]) + REFUSE("plan %u: steps", i); + for (uint32_t k = 0; k < ranges[table][1]; ++k) + if (le16(s->steps + (size_t)(ranges[table][0] + k) * VEGA_STEP_BYTES) >= s->lookup_count[table]) + REFUSE("plan %u: a lookup the font lacks", i); + } + } + return true; +} + +void vega_shaping_close(VegaShaping *s) { + for (int i = 0; i < 256; ++i) free(s->bmp[i]), s->bmp[i] = NULL; + free(s->lookups[0]); + free(s->lookups[1]); + free(s->subtables); + s->lookups[0] = s->lookups[1] = NULL; + s->subtables = NULL; +} + +uint32_t vega_shaping_glyph(const VegaShaping *s, uint32_t code) { + if (code <= 0xFFFF) return s->bmp[code >> 8] ? s->bmp[code >> 8][code & 255] : 0; + uint32_t low = 0, high = s->cmap_count; + while (low < high) { + uint32_t middle = (low + high) / 2, c = le32(s->cmap + 8 * (size_t)middle); + if (c < code) low = middle + 1; + else if (c > code) high = middle; + else return le32(s->cmap + 8 * (size_t)middle + 4); + } + return 0; +} + +static int32_t advance_of(const VegaShaping *s, uint32_t glyph) { + return glyph < s->glyph_count ? le16(s->advances + 2 * glyph) : 0; +} + +/* glyph_props: GDEF's class as the lookup flags that skip it, a mark's + * attachment class in the high byte; the flags substitution sets. */ +enum { BASE_GLYPH = 0x02, LIGATURE = 0x04, MARK = 0x08, SUBSTITUTED = 0x10, LIGATED = 0x20, MULTIPLIED = 0x40, + PRESERVE = SUBSTITUTED | LIGATED | MULTIPLIED }; + +static uint16_t glyph_props(const VegaShaping *s, uint32_t glyph) { + switch (class_of(s->gdef, s->glyph_classes, glyph)) { + case 1: return BASE_GLYPH; + case 2: return LIGATURE; + case 3: return (uint16_t)(MARK | class_of(s->gdef, s->attach_classes, glyph) << 8); + default: return 0; + } +} + +static bool mark_set_covers(const VegaShaping *s, uint32_t set, uint32_t glyph) { + if (!s->mark_sets || get16(s->gdef, s->mark_sets) != 1 || set >= get16(s->gdef, s->mark_sets + 2)) return false; + uint32_t at = get32(s->gdef, s->mark_sets + 4 + 4 * set); + return at && coverage(s->gdef, s->mark_sets + at, glyph) != NOT_COVERED; +} + +/* ---- The buffer (hb-buffer.cc): glyphs in, and glyphs out of the lookup + * that is running; positions once substitution is done. */ + +typedef struct { + uint32_t codepoint; /* a character, then (map_glyphs) a glyph */ + uint32_t mask, cluster, glyph_index; + uint16_t uprops, gprops; + uint8_t lig_props, action; +} Info; +typedef struct { + int32_t x_advance, y_advance, x_offset, y_offset; + int32_t chain; + uint8_t attach; +} Position; + +struct VegaShaper { + Info *info, *out; + Position *pos; + size_t len, out_len, idx, allocated, max_len; + bool have_output, successful; + int direction; + uint32_t scratch, serial; + long max_ops; + VegaShaped *glyphs; + size_t glyphs_allocated; +}; + +enum { HAS_NON_ASCII = 1, HAS_DEFAULT_IGNORABLES = 2, HAS_SPACE_FALLBACK = 4, HAS_GPOS_ATTACHMENT = 8, HAS_CGJ = 16, + HAS_VARIATION_SELECTOR_FALLBACK = 32 }; + +VegaShaper *vega_shaper_new(void) { return calloc(1, sizeof(VegaShaper)); } + +void vega_shaper_free(VegaShaper *b) { + if (!b) return; + free(b->info); + free(b->out); + free(b->pos); + free(b->glyphs); + free(b); +} + +static bool ensure(VegaShaper *b, size_t size) { + if (size <= b->allocated) return true; + if (!b->successful) return false; + if (size > b->max_len) { + b->successful = false; + return false; + } + size_t n = b->allocated ? b->allocated : 32; + while (n < size) n *= 2; + Info *info = realloc(b->info, n * sizeof(*info)); + if (info) b->info = info; + Info *out = info ? realloc(b->out, n * sizeof(*out)) : NULL; + if (out) b->out = out; + Position *pos = out ? realloc(b->pos, n * sizeof(*pos)) : NULL; + if (!pos) { + b->successful = false; + return false; + } + b->pos = pos; + b->allocated = n; + return true; +} + +/* The glyphs before idx: out while a lookup writes, else info itself. */ +static Info *out_info(VegaShaper *b) { return b->have_output ? b->out : b->info; } +static size_t backtrack_len(const VegaShaper *b) { return b->have_output ? b->out_len : b->idx; } +static size_t lookahead_len(const VegaShaper *b) { return b->len - b->idx; } + +static void clear_output(VegaShaper *b) { + b->have_output = true; + b->idx = b->out_len = 0; +} + +static void next_glyph(VegaShaper *b) { + if (b->have_output) { + if (!ensure(b, b->out_len + 1)) return; + b->out[b->out_len++] = b->info[b->idx]; + } + b->idx++; +} + +static void next_glyphs(VegaShaper *b, size_t n) { + if (b->have_output) { + if (!ensure(b, b->out_len + n)) return; + memmove(b->out + b->out_len, b->info + b->idx, n * sizeof(Info)); + b->out_len += n; + } + b->idx += n; +} + +static void skip_glyph(VegaShaper *b) { b->idx++; } + +static void replace_glyph(VegaShaper *b, uint32_t glyph) { + if (!ensure(b, b->out_len + 1)) return; + b->out[b->out_len] = b->info[b->idx]; + b->out[b->out_len++].codepoint = glyph; + b->idx++; +} + +static void output_glyph(VegaShaper *b, uint32_t glyph) { + if (!ensure(b, b->out_len + 1)) return; + if (b->idx == b->len && !b->out_len) return; + b->out[b->out_len] = b->idx < b->len ? b->info[b->idx] : b->out[b->out_len - 1]; + b->out[b->out_len++].codepoint = glyph; +} + +static void sync(VegaShaper *b) { + if (!b->successful) { + b->have_output = false; + b->out_len = b->idx = 0; + return; + } + next_glyphs(b, b->len - b->idx); + Info *swap = b->info; + b->info = b->out; + b->out = swap; + b->len = b->out_len; + b->have_output = false; + b->out_len = b->idx = 0; +} + +static bool shift_forward(VegaShaper *b, size_t count) { + if (!ensure(b, b->len + count)) return false; + memmove(b->info + b->idx + count, b->info + b->idx, (b->len - b->idx) * sizeof(Info)); + if (b->idx + count > b->len) memset(b->info + b->len, 0, (b->idx + count - b->len) * sizeof(Info)); + b->len += count; + b->idx += count; + return true; +} + +static bool move_to(VegaShaper *b, size_t i) { + if (!b->have_output) { + b->idx = i; + return true; + } + if (!b->successful) return false; + if (b->out_len < i) { + size_t count = i - b->out_len; + if (!ensure(b, b->out_len + count)) return false; + memmove(b->out + b->out_len, b->info + b->idx, count * sizeof(Info)); + b->idx += count; + b->out_len += count; + } else if (b->out_len > i) { + size_t count = b->out_len - i; + if (b->idx < count && !shift_forward(b, count - b->idx)) return false; + b->idx -= count; + b->out_len -= count; + memmove(b->info + b->idx, b->out + b->out_len, count * sizeof(Info)); + } + return true; +} + +static void merge_clusters(VegaShaper *b, size_t start, size_t end) { + if (end - start < 2) return; + uint32_t cluster = b->info[start].cluster; + for (size_t i = start + 1; i < end; ++i) + if (b->info[i].cluster < cluster) cluster = b->info[i].cluster; + if (cluster != b->info[end - 1].cluster) + while (end < b->len && b->info[end - 1].cluster == b->info[end].cluster) end++; + if (cluster != b->info[start].cluster) + while (b->idx < start && b->info[start - 1].cluster == b->info[start].cluster) start--; + if (b->idx == start && b->info[start].cluster != cluster) + for (size_t i = b->out_len; i && b->out[i - 1].cluster == b->info[start].cluster; i--) + b->out[i - 1].cluster = cluster; + for (size_t i = start; i < end; ++i) b->info[i].cluster = cluster; +} + +static void merge_out_clusters(VegaShaper *b, size_t start, size_t end) { + if (end - start < 2) return; + uint32_t cluster = b->out[start].cluster; + for (size_t i = start + 1; i < end; ++i) + if (b->out[i].cluster < cluster) cluster = b->out[i].cluster; + while (start && b->out[start - 1].cluster == b->out[start].cluster) start--; + while (end < b->out_len && b->out[end - 1].cluster == b->out[end].cluster) end++; + if (end == b->out_len) + for (size_t i = b->idx; i < b->len && b->info[i].cluster == b->out[end - 1].cluster; ++i) + b->info[i].cluster = cluster; + for (size_t i = start; i < end; ++i) b->out[i].cluster = cluster; +} + +/* Delete the current glyph, keeping its cluster on a neighbour. */ +static void delete_glyph(VegaShaper *b) { + uint32_t cluster = b->info[b->idx].cluster; + if ((b->idx + 1 < b->len && cluster == b->info[b->idx + 1].cluster) || + (b->out_len && cluster == b->out[b->out_len - 1].cluster)) { + skip_glyph(b); + return; + } + if (b->out_len) { + if (cluster < b->out[b->out_len - 1].cluster) { + uint32_t old = b->out[b->out_len - 1].cluster; + for (size_t i = b->out_len; i && b->out[i - 1].cluster == old; i--) b->out[i - 1].cluster = cluster; + } + skip_glyph(b); + return; + } + if (b->idx + 1 < b->len) merge_clusters(b, b->idx, b->idx + 2); + skip_glyph(b); +} + +static void reverse_range(VegaShaper *b, size_t start, size_t end, bool positions) { + for (size_t i = start, j = end; i + 1 < j; ++i, --j) { + Info t = b->info[i]; + b->info[i] = b->info[j - 1]; + b->info[j - 1] = t; + if (positions) { + Position p = b->pos[i]; + b->pos[i] = b->pos[j - 1]; + b->pos[j - 1] = p; + } + } +} + +static uint8_t allocate_lig_id(VegaShaper *b) { + for (;;) { + if (!++b->serial) ++b->serial; + uint8_t id = b->serial & 7; + if (id) return id; + } +} + +/* ---- Characters' properties (unicode_props) */ + +enum { UPROPS_IGNORABLE = 0x20, UPROPS_HIDDEN = 0x40, UPROPS_CONTINUATION = 0x80, UPROPS_ZWJ = 0x100, + UPROPS_ZWNJ = 0x200, UPROPS_VS = 0x400 }; + +static unsigned gen_cat(const Info *i) { return i->uprops & 0x1F; } +static bool is_mark_category(unsigned c) { return c == VEGA_MN || c == VEGA_MC || c == VEGA_ME; } +static bool is_unicode_mark(const Info *i) { return is_mark_category(gen_cat(i)); } +static unsigned info_cc(const Info *i) { return is_unicode_mark(i) ? i->uprops >> 8 : 0; } +static void set_info_cc(Info *i, unsigned cc) { + if (is_unicode_mark(i)) i->uprops = (uint16_t)(cc << 8 | (i->uprops & 0xFF)); +} +static bool is_unicode_space(const Info *i) { return gen_cat(i) == VEGA_ZS; } +static bool substituted(const Info *i) { return i->gprops & SUBSTITUTED; } +static bool is_default_ignorable(const Info *i) { return (i->uprops & UPROPS_IGNORABLE) && !substituted(i); } +static bool is_zwnj(const Info *i) { return gen_cat(i) == VEGA_CF && (i->uprops & UPROPS_ZWNJ); } +static bool is_zwj(const Info *i) { return gen_cat(i) == VEGA_CF && (i->uprops & UPROPS_ZWJ); } +static bool is_continuation(const Info *i) { return i->uprops & UPROPS_CONTINUATION; } +static bool is_letter(unsigned c) { return c >= VEGA_LU && c <= VEGA_LO; } +/* The categories set_unicode_props passes over (not Lm). */ +static bool cased_or_other_letter_or_space(unsigned c) { + return c == VEGA_LU || c == VEGA_LL || c == VEGA_LT || c == VEGA_LO || c == VEGA_ZS; +} + +/* HarfBuzz's Default_Ignorable: Unicode's, less the Hangul fillers and a + * few others that fonts draw. */ +static bool default_ignorable(uint32_t ch) { + uint32_t plane = ch >> 16; + if (!plane) { + switch (ch >> 8) { + case 0x00: return ch == 0x00AD; + case 0x03: return ch == 0x034F; + case 0x06: return ch == 0x061C; + case 0x17: return ch >= 0x17B4 && ch <= 0x17B5; + case 0x18: return ch >= 0x180B && ch <= 0x180F; + case 0x20: return (ch >= 0x200B && ch <= 0x200F) || (ch >= 0x202A && ch <= 0x202E) || (ch >= 0x2060 && ch <= 0x206F); + case 0xFE: return (ch >= 0xFE00 && ch <= 0xFE0F) || ch == 0xFEFF; + case 0xFF: return ch >= 0xFFF0 && ch <= 0xFFF8; + default: return false; + } + } + if (plane == 1) return ch >= 0x1D173 && ch <= 0x1D17A; + return plane == 0x0E && ch <= 0xE0FFF; +} + +static bool variation_selector(uint32_t ch) { return (ch >= 0xFE00 && ch <= 0xFE0F) || (ch >= 0xE0100 && ch <= 0xE01EF); } + +/* Canonical_Combining_Class as HarfBuzz reorders by: Hebrew's fixed + * positions in the SBL order, Arabic's shadda before the other marks. */ +static unsigned modified_combining_class(uint32_t u) { + if (u == 0x1A60 || u == 0x0FC6) return 254; + if (u == 0x0F39) return 127; + static const uint8_t hebrew_arabic[27] = {22, 15, 16, 17, 23, 18, 19, 20, 21, 14, 24, 12, 25, 13, + 10, 11, 26, 28, 29, 30, 31, 32, 33, 27, 34, 35, 36}; + unsigned c = vega_combining_class(u); + if (c >= 10 && c <= 36) return hebrew_arabic[c - 10]; + switch (c) { + case 84: case 91: return 0; + case 103: return 3; + case 130: return 132; + case 132: return 131; + default: return c; + } +} + +enum { NOT_SPACE = 0, SPACE_EM = 1, SPACE_EM_2 = 2, SPACE_EM_3 = 3, SPACE_EM_4 = 4, SPACE_EM_5 = 5, SPACE_EM_6 = 6, + SPACE_EM_16 = 16, SPACE_4_EM_18 = 17, SPACE = 18, SPACE_FIGURE = 19, SPACE_PUNCTUATION = 20, SPACE_NARROW = 21 }; + +static unsigned space_fallback(uint32_t u) { + switch (u) { + case 0x0020: case 0x00A0: return SPACE; + case 0x2000: case 0x2002: return SPACE_EM_2; + case 0x2001: case 0x2003: case 0x3000: return SPACE_EM; + case 0x2004: return SPACE_EM_3; + case 0x2005: return SPACE_EM_4; + case 0x2006: return SPACE_EM_6; + case 0x2007: return SPACE_FIGURE; + case 0x2008: return SPACE_PUNCTUATION; + case 0x2009: return SPACE_EM_5; + case 0x200A: return SPACE_EM_16; + case 0x202F: return SPACE_NARROW; + case 0x205F: return SPACE_4_EM_18; + default: return NOT_SPACE; + } +} + +static void init_unicode_props(Info *info, uint32_t *scratch) { + uint32_t u = info->codepoint; + unsigned gen = vega_category(u), props = gen; + if (u >= 0x80) { + *scratch |= HAS_NON_ASCII; + if (default_ignorable(u)) { + *scratch |= HAS_DEFAULT_IGNORABLES; + props |= UPROPS_IGNORABLE; + if (u == 0x200C) props |= UPROPS_ZWNJ; + else if (u == 0x200D) props |= UPROPS_ZWJ; + else if ((u >= 0x180B && u <= 0x180D) || u == 0x180F) props |= UPROPS_HIDDEN; + else if (u >= 0xE0020 && u <= 0xE007F) props |= UPROPS_HIDDEN; + else if (u == 0x034F) { + *scratch |= HAS_CGJ; + props |= UPROPS_HIDDEN; + } + } + if (is_mark_category(gen)) props |= UPROPS_CONTINUATION | modified_combining_class(u) << 8; + } + info->uprops = (uint16_t)props; +} + +static bool regional_indicator(uint32_t u) { return u >= 0x1F1E6 && u <= 0x1F1FF; } + +/* Enough of Unicode's graphemes that shaping backwards keeps them whole: + * marks, ZWJ (and the pictograph after it), emoji modifiers, pairs of + * regional indicators, and a few others continue the character before. */ +static void set_unicode_props(VegaShaper *b) { + for (size_t i = 0; i < b->len; ++i) { + Info *info = &b->info[i]; + init_unicode_props(info, &b->scratch); + unsigned gen = gen_cat(info); + if (cased_or_other_letter_or_space(gen)) continue; + uint32_t u = info->codepoint; + if (gen == VEGA_SK && u >= 0x1F3FB && u <= 0x1F3FF) info->uprops |= UPROPS_CONTINUATION; + else if (i && regional_indicator(u)) { + if (regional_indicator(b->info[i - 1].codepoint) && !is_continuation(&b->info[i - 1])) + info->uprops |= UPROPS_CONTINUATION; + } else if (is_zwj(info)) { + info->uprops |= UPROPS_CONTINUATION; + if (i + 1 < b->len && vega_extended_pictographic(b->info[i + 1].codepoint)) { + ++i; + init_unicode_props(&b->info[i], &b->scratch); + b->info[i].uprops |= UPROPS_CONTINUATION; + } + } else if ((u >= 0xFF9E && u <= 0xFF9F) || (u >= 0xE0020 && u <= 0xE007F)) + info->uprops |= UPROPS_CONTINUATION; + } +} + +static size_t grapheme_end(const VegaShaper *b, size_t start) { + size_t end = start + 1; + while (end < b->len && is_continuation(&b->info[end])) end++; + return end; +} + +static void form_clusters(VegaShaper *b) { + if (!(b->scratch & HAS_NON_ASCII)) return; + for (size_t start = 0, end; start < b->len; start = end) { + end = grapheme_end(b, start); + merge_clusters(b, start, end); + } +} + +/* ---- The plan */ + +typedef struct { + uint32_t script; + int direction, native, shaper, flags; + uint32_t global_mask, masks[VEGA_PLAN_MASKS]; + const unsigned char *gsub, *gpos; + uint32_t gsub_count, gpos_count; +} Plan; + +static bool find_plan(const VegaShaping *s, uint32_t script, int direction, Plan *plan) { + const unsigned char *found = NULL; + for (int pass = 0; pass < 2 && !found; ++pass) + for (uint32_t i = 0; i < s->plan_count && !found; ++i) { + const unsigned char *p = s->plans + (size_t)i * VEGA_PLAN_BYTES; + if (le32(p) == (pass ? 0x5A797979u : script) && p[4] == direction) found = p; + } + if (!found) return false; + *plan = (Plan){le32(found), found[4], found[5], found[6], found[7], le32(found + 8), {0}, + s->steps + (size_t)le32(found + 56) * VEGA_STEP_BYTES, + s->steps + (size_t)le32(found + 64) * VEGA_STEP_BYTES, le32(found + 60), le32(found + 68)}; + for (int k = 0; k < VEGA_PLAN_MASKS; ++k) plan->masks[k] = le32(found + 12 + 4 * k); + return true; +} + +/* Runs of digits in right-to-left scripts are left-to-right; a run whose + * direction is not its script's is shaped in the script's, graphemes + * reversed. */ +static void ensure_native_direction(VegaShaper *b, const Plan *plan) { + int horizontal = plan->native; + if (horizontal == VEGA_SHAPE_RTL && b->direction == VEGA_SHAPE_LTR) { + bool number = false, letter = false, indicator = false; + for (size_t i = 0; i < b->len; ++i) { + unsigned gen = gen_cat(&b->info[i]); + if (gen == VEGA_ND) number = true; + else if (is_letter(gen)) { + letter = true; + break; + } else if (regional_indicator(b->info[i].codepoint)) indicator = true; + } + if ((number || indicator) && !letter) horizontal = VEGA_SHAPE_LTR; + } + if (horizontal && b->direction != horizontal) { + for (size_t start = 0, end; start < b->len; start = end) { + end = grapheme_end(b, start); + reverse_range(b, start, end, false); + } + reverse_range(b, 0, b->len, false); + b->direction = horizontal; + } +} + +/* ---- Normalization (hb-ot-shape-normalize.cc): decompose what the font + * lacks, order marks, compose what the font has. */ + +typedef struct { + const VegaShaping *s; + const Plan *plan; + VegaShaper *b; +} Normalizer; + +enum { SBASE = 0xAC00, LBASE = 0x1100, VBASE = 0x1161, TBASE = 0x11A7, LCOUNT = 19, VCOUNT = 21, TCOUNT = 28, + NCOUNT = VCOUNT * TCOUNT, SCOUNT = LCOUNT * NCOUNT }; + +static bool decompose_unicode(uint32_t ab, uint32_t *a, uint32_t *b) { + uint32_t si = ab - SBASE; + if (si < SCOUNT) { + if (si % TCOUNT) *a = SBASE + si / TCOUNT * TCOUNT, *b = TBASE + si % TCOUNT; + else *a = LBASE + si / NCOUNT, *b = VBASE + si % NCOUNT / TCOUNT; + return true; + } + return vega_decomposition_step(ab, a, b); +} + +static bool compose_unicode(uint32_t a, uint32_t b, uint32_t *ab) { + if (a >= SBASE && a < SBASE + SCOUNT && b > TBASE && b < TBASE + TCOUNT && !((a - SBASE) % TCOUNT)) { + *ab = a + (b - TBASE); + return true; + } + if (a >= LBASE && a < LBASE + LCOUNT && b >= VBASE && b < VBASE + VCOUNT) { + *ab = SBASE + (a - LBASE) * NCOUNT + (b - VBASE) * TCOUNT; + return true; + } + return (*ab = vega_composition(a, b)) != 0; +} + +/* Hebrew's presentation forms, for fonts that position no marks. */ +static bool compose_hebrew(const Normalizer *c, uint32_t a, uint32_t b, uint32_t *ab) { + static const uint16_t dagesh[27] = {0xFB30, 0xFB31, 0xFB32, 0xFB33, 0xFB34, 0xFB35, 0xFB36, 0, 0xFB38, + 0xFB39, 0xFB3A, 0xFB3B, 0xFB3C, 0, 0xFB3E, 0, 0xFB40, 0xFB41, + 0, 0xFB43, 0xFB44, 0, 0xFB46, 0xFB47, 0xFB48, 0xFB49, 0xFB4A}; + if (compose_unicode(a, b, ab)) return true; + if (c->plan->flags & VEGA_PLAN_GPOS_MARK) return false; + *ab = 0; + switch (b) { + case 0x05B4: if (a == 0x05D9) *ab = 0xFB1D; break; + case 0x05B7: if (a == 0x05D9) *ab = 0xFB1F; else if (a == 0x05D0) *ab = 0xFB2E; break; + case 0x05B8: if (a == 0x05D0) *ab = 0xFB2F; break; + case 0x05B9: if (a == 0x05D5) *ab = 0xFB4B; break; + case 0x05BC: + if (a >= 0x05D0 && a <= 0x05EA) *ab = dagesh[a - 0x05D0]; + else if (a == 0xFB2A) *ab = 0xFB2C; + else if (a == 0xFB2B) *ab = 0xFB2D; + break; + case 0x05BF: if (a == 0x05D1) *ab = 0xFB4C; else if (a == 0x05DB) *ab = 0xFB4D; else if (a == 0x05E4) *ab = 0xFB4E; break; + case 0x05C1: if (a == 0x05E9) *ab = 0xFB2A; else if (a == 0xFB49) *ab = 0xFB2C; break; + case 0x05C2: if (a == 0x05E9) *ab = 0xFB2B; else if (a == 0xFB49) *ab = 0xFB2D; break; + } + return *ab != 0; +} + +static bool compose(const Normalizer *c, uint32_t a, uint32_t b, uint32_t *ab) { + return c->plan->shaper == VEGA_SHAPER_HEBREW ? compose_hebrew(c, a, b, ab) : compose_unicode(a, b, ab); +} + +static bool nominal(const VegaShaping *s, uint32_t u, uint32_t *glyph) { return (*glyph = vega_shaping_glyph(s, u)) != 0; } + +static void output_char(VegaShaper *b, uint32_t unichar, uint32_t glyph) { + b->info[b->idx].glyph_index = glyph; + size_t before = b->out_len; + output_glyph(b, unichar); + if (b->out_len > before) init_unicode_props(&b->out[b->out_len - 1], &b->scratch); +} + +static void next_char(VegaShaper *b, uint32_t glyph) { + b->info[b->idx].glyph_index = glyph; + next_glyph(b); +} + +/* Returns how many characters ab became, 0 if it did not decompose. */ +static unsigned decompose(const Normalizer *c, bool shortest, uint32_t ab) { + uint32_t a, bb, a_glyph = 0, b_glyph = 0; + if (!decompose_unicode(ab, &a, &bb) || (bb && !nominal(c->s, bb, &b_glyph))) return 0; + bool has_a = nominal(c->s, a, &a_glyph); + if (shortest && has_a) { + output_char(c->b, a, a_glyph); + if (bb) { + output_char(c->b, bb, b_glyph); + return 2; + } + return 1; + } + unsigned ret = decompose(c, shortest, a); + if (ret) { + if (bb) { + output_char(c->b, bb, b_glyph); + return ret + 1; + } + return ret; + } + if (has_a) { + output_char(c->b, a, a_glyph); + if (bb) { + output_char(c->b, bb, b_glyph); + return 2; + } + return 1; + } + return 0; +} + +static void decompose_current_character(const Normalizer *c, bool shortest) { + VegaShaper *b = c->b; + uint32_t u = b->info[b->idx].codepoint, glyph = 0; + bool has = nominal(c->s, u, &glyph); + if (shortest && has) { + next_char(b, glyph); + return; + } + if (decompose(c, shortest, u)) { + skip_glyph(b); + return; + } + if (!shortest && has) { + next_char(b, glyph); + return; + } + if (is_unicode_space(&b->info[b->idx])) { + uint32_t space_glyph; + unsigned type = space_fallback(u); + if (type != NOT_SPACE && nominal(c->s, 0x0020, &space_glyph)) { + b->info[b->idx].uprops = (uint16_t)(type << 8 | (b->info[b->idx].uprops & 0xFF)); + next_char(b, space_glyph); + b->scratch |= HAS_SPACE_FALLBACK; + return; + } + } + if (u == 0x2011) { + uint32_t other; + if (nominal(c->s, 0x2010, &other)) { + next_char(b, other); + return; + } + } + next_char(b, 0); +} + +/* A variation selector's cluster: normalization gives up on it. (Variation + * sequences the font maps, cmap format 14, are not carried: each character + * passes on alone, the selector hidden.) */ +static void handle_variation_selector_cluster(const Normalizer *c, size_t end) { + VegaShaper *b = c->b; + uint32_t glyph; + while (b->idx + 1 < end && b->successful) { + if (variation_selector(b->info[b->idx + 1].codepoint)) { + b->info[b->idx].glyph_index = nominal(c->s, b->info[b->idx].codepoint, &glyph) ? glyph : 0; + next_glyph(b); + b->scratch |= HAS_VARIATION_SELECTOR_FALLBACK; + Info *vs = &b->info[b->idx]; + vs->uprops = (uint16_t)((vs->uprops & ~0x1Fu & 0xFF) | VEGA_CF | UPROPS_VS); + vs->glyph_index = nominal(c->s, vs->codepoint, &glyph) ? glyph : 0; + next_glyph(b); + while (b->idx < end && b->successful && variation_selector(b->info[b->idx].codepoint)) { + b->info[b->idx].glyph_index = nominal(c->s, b->info[b->idx].codepoint, &glyph) ? glyph : 0; + next_glyph(b); + } + } else { + b->info[b->idx].glyph_index = nominal(c->s, b->info[b->idx].codepoint, &glyph) ? glyph : 0; + next_glyph(b); + } + } + if (b->idx < end) { + b->info[b->idx].glyph_index = nominal(c->s, b->info[b->idx].codepoint, &glyph) ? glyph : 0; + next_glyph(b); + } +} + +static void decompose_multi_char_cluster(const Normalizer *c, size_t end, bool short_circuit) { + VegaShaper *b = c->b; + for (size_t i = b->idx; i < end && b->successful; ++i) + if (variation_selector(b->info[i].codepoint)) { + handle_variation_selector_cluster(c, end); + return; + } + while (b->idx < end && b->successful) decompose_current_character(c, short_circuit); +} + +enum { MAX_COMBINING_MARKS = 32 }; + +/* Stable: a mark moves before the marks of a higher class, and the + * clusters it crosses merge. */ +static void sort_marks(VegaShaper *b, size_t start, size_t end) { + for (size_t i = start + 1; i < end; ++i) { + size_t j = i; + while (j > start && info_cc(&b->info[j - 1]) > info_cc(&b->info[i])) j--; + if (i == j) continue; + merge_clusters(b, j, i + 1); + Info t = b->info[i]; + memmove(&b->info[j + 1], &b->info[j], (i - j) * sizeof(Info)); + b->info[j] = t; + } +} + +/* Arabic marks that modify the letter (UTR #53) go first among their class. */ +static bool modifier_combining_mark(uint32_t u) { + switch (u) { + case 0x0654: case 0x0655: case 0x0658: case 0x06DC: case 0x06E3: case 0x06E7: case 0x06E8: case 0x08CA: + case 0x08CB: case 0x08CD: case 0x08CE: case 0x08CF: case 0x08D3: case 0x08F3: + return true; + default: + return false; + } +} + +static void reorder_marks_arabic(VegaShaper *b, size_t start, size_t end) { + size_t i = start; + for (unsigned cc = 220; cc <= 230; cc += 10) { + while (i < end && info_cc(&b->info[i]) < cc) i++; + if (i == end) break; + if (info_cc(&b->info[i]) > cc) continue; + size_t j = i; + while (j < end && info_cc(&b->info[j]) == cc && modifier_combining_mark(b->info[j].codepoint)) j++; + if (i == j) continue; + Info moved[MAX_COMBINING_MARKS]; + merge_clusters(b, start, j); + memcpy(moved, &b->info[i], (j - i) * sizeof(Info)); + memmove(&b->info[start + j - i], &b->info[start], (i - start) * sizeof(Info)); + memcpy(&b->info[start], moved, (j - i) * sizeof(Info)); + /* Renumbered so the sequence stays sorted: 22 and 26 are below every + * Arabic class. */ + size_t new_start = start + j - i; + unsigned new_cc = cc == 220 ? 25 : 26; + for (; start < new_start; ++start) set_info_cc(&b->info[start], new_cc); + i = j; + } +} + +static void reorder_marks_hebrew(VegaShaper *b, size_t start, size_t end) { + for (size_t i = start + 2; i < end; ++i) { + unsigned c0 = info_cc(&b->info[i - 2]), c1 = info_cc(&b->info[i - 1]), c2 = info_cc(&b->info[i]); + if ((c0 == 20 || c0 == 21) && (c1 == 22 || c1 == 23) && (c2 == 25 || c2 == 220)) { + merge_clusters(b, i - 1, i + 1); + Info t = b->info[i - 1]; + b->info[i - 1] = b->info[i]; + b->info[i] = t; + break; + } + } +} + +static void normalize(const VegaShaping *s, const Plan *plan, VegaShaper *b) { + if (!b->len) return; + Normalizer c = {s, plan, b}; + /* The shapers' preference is "auto": composed diacritics. */ + const bool might_short_circuit = true, always_short_circuit = false; + bool all_simple = true; + clear_output(b); + size_t count = b->len; + do { + size_t end = b->idx + 1; + while (end < count && !is_unicode_mark(&b->info[end])) end++; + if (end < count) end--; /* one base left for the marks */ + if (might_short_circuit) { + size_t done = 0; + uint32_t glyph; + while (b->idx + done < end && nominal(s, b->info[b->idx + done].codepoint, &glyph)) + b->info[b->idx + done++].glyph_index = glyph; + next_glyphs(b, done); + } + while (b->idx < end && b->successful) decompose_current_character(&c, might_short_circuit); + if (b->idx == count || !b->successful) break; + all_simple = false; + for (end = b->idx + 1; end < count; end++) + if (!is_unicode_mark(&b->info[end])) break; + decompose_multi_char_cluster(&c, end, always_short_circuit); + } while (b->idx < count && b->successful); + sync(b); + + if (!all_simple) { + count = b->len; + for (size_t i = 0; i < count; i++) { + if (!info_cc(&b->info[i])) continue; + size_t end = i + 1; + while (end < count && info_cc(&b->info[end])) end++; + if (end - i <= MAX_COMBINING_MARKS) { + sort_marks(b, i, end); + if (plan->shaper == VEGA_SHAPER_ARABIC) reorder_marks_arabic(b, i, end); + else if (plan->shaper == VEGA_SHAPER_HEBREW) reorder_marks_hebrew(b, i, end); + } + i = end; + } + } + if (b->scratch & HAS_CGJ) + for (size_t i = 1; i + 1 < b->len; ++i) + if (b->info[i].codepoint == 0x034F && + (!info_cc(&b->info[i + 1]) || info_cc(&b->info[i - 1]) <= info_cc(&b->info[i + 1]))) + b->info[i].uprops &= (uint16_t)~UPROPS_HIDDEN; + + if (!all_simple && b->successful) { + clear_output(b); + count = b->len; + size_t starter = 0; + next_glyph(b); + while (b->idx < count && b->successful) { + Info *cur = &b->info[b->idx]; + uint32_t composed, glyph; + if (is_unicode_mark(cur) && + (starter == b->out_len - 1 || info_cc(&b->out[b->out_len - 1]) < info_cc(cur)) && + compose(&c, b->out[starter].codepoint, cur->codepoint, &composed) && nominal(s, composed, &glyph)) { + next_glyph(b); + if (!b->successful) return; + merge_out_clusters(b, starter, b->out_len); + b->out_len--; + b->out[starter].codepoint = composed; + b->out[starter].glyph_index = glyph; + init_unicode_props(&b->out[starter], &b->scratch); + continue; + } + next_glyph(b); + if (!info_cc(&b->out[b->out_len - 1])) starter = b->out_len - 1; + } + sync(b); + } +} + +/* ---- Masks: fractions, and Arabic's joining forms (hb-ot-shaper-arabic.cc) */ + +static void setup_masks_fraction(VegaShaper *b, const Plan *plan) { + if (!(b->scratch & HAS_NON_ASCII) || !(plan->flags & VEGA_PLAN_FRACTIONS)) return; + uint32_t frac = plan->masks[VEGA_MASK_FRAC], numr = plan->masks[VEGA_MASK_NUMR], dnom = plan->masks[VEGA_MASK_DNOM]; + bool forward = b->direction == VEGA_SHAPE_LTR; + uint32_t pre = forward ? numr | frac : frac | dnom, post = forward ? frac | dnom : numr | frac; + for (size_t i = 0; i < b->len;) { + if (b->info[i].codepoint != 0x2044) { + i++; + continue; + } + size_t start = i, end = i + 1; + while (start && gen_cat(&b->info[start - 1]) == VEGA_ND) start--; + while (end < b->len && gen_cat(&b->info[end]) == VEGA_ND) end++; + if (start == i || end == i + 1) { + i++; + continue; + } + for (size_t k = start; k < i; ++k) b->info[k].mask |= pre; + b->info[i].mask |= frac; + for (size_t k = i + 1; k < end; ++k) b->info[k].mask |= post; + i = end; + } +} + +enum { ISOL, FINA, FIN2, FIN3, MEDI, MED2, INIT, NONE }; +enum { JT_U, JT_L, JT_R, JT_D, JG_ALAPH, JG_DALATH_RISH, JT_T = 7 }; + +static unsigned joining_type(uint32_t u) { + switch (vega_joining(u)) { + case VEGA_JOINING_L: return JT_L; + case VEGA_JOINING_R: return JT_R; + case VEGA_JOINING_D: case VEGA_JOINING_C: return JT_D; + case VEGA_JOINING_T: return JT_T; + default: return JT_U; + } +} + +static void setup_masks_arabic(VegaShaper *b, const Plan *plan) { + static const uint8_t table[7][6][3] = { + {{NONE, NONE, 0}, {NONE, ISOL, 2}, {NONE, ISOL, 1}, {NONE, ISOL, 2}, {NONE, ISOL, 1}, {NONE, ISOL, 6}}, + {{NONE, NONE, 0}, {NONE, ISOL, 2}, {NONE, ISOL, 1}, {NONE, ISOL, 2}, {NONE, FIN2, 5}, {NONE, ISOL, 6}}, + {{NONE, NONE, 0}, {NONE, ISOL, 2}, {INIT, FINA, 1}, {INIT, FINA, 3}, {INIT, FINA, 4}, {INIT, FINA, 6}}, + {{NONE, NONE, 0}, {NONE, ISOL, 2}, {MEDI, FINA, 1}, {MEDI, FINA, 3}, {MEDI, FINA, 4}, {MEDI, FINA, 6}}, + {{NONE, NONE, 0}, {NONE, ISOL, 2}, {MED2, ISOL, 1}, {MED2, ISOL, 2}, {MED2, FIN2, 5}, {MED2, ISOL, 6}}, + {{NONE, NONE, 0}, {NONE, ISOL, 2}, {ISOL, ISOL, 1}, {ISOL, ISOL, 2}, {ISOL, FIN2, 5}, {ISOL, ISOL, 6}}, + {{NONE, NONE, 0}, {NONE, ISOL, 2}, {NONE, ISOL, 1}, {NONE, ISOL, 2}, {NONE, FIN3, 5}, {NONE, ISOL, 6}}}; + size_t prev = (size_t)-1; + unsigned state = 0; + for (size_t i = 0; i < b->len; ++i) { + unsigned type = joining_type(b->info[i].codepoint); + if (type == JT_T) { + b->info[i].action = NONE; + continue; + } + const uint8_t *entry = table[state][type]; + if (entry[0] != NONE && prev != (size_t)-1) b->info[prev].action = entry[0]; + b->info[i].action = entry[1]; + prev = i; + state = entry[2]; + } + for (size_t i = 0; i < b->len; ++i) + if (b->info[i].action < NONE) b->info[i].mask |= plan->masks[VEGA_MASK_ISOL + b->info[i].action]; +} + +/* ---- Applying lookups (hb-ot-layout-gsubgpos.hh) */ + +typedef struct { + const VegaShaping *s; + VegaShaper *b; + int table; /* 0 GSUB, 1 GPOS */ + VegaTable t; + uint32_t lookup_mask, lookup_props; + bool auto_zwnj, auto_zwj, random, has_glyph_classes; + int nesting_left; + uint32_t random_state; + long last_base; + size_t last_base_until; + VegaDigest digest; /* the buffer's glyphs, and every glyph substitution made since */ +} Apply; + +enum { MAX_NESTING_LEVEL = 64, MAX_CONTEXT_LENGTH = 64 }; + +static bool check_glyph_property(const Apply *c, const Info *info, uint32_t match_props) { + unsigned props = info->gprops, flags = match_props & 0xFFFF; + if (props & flags & (BASE_GLYPH | LIGATURE | MARK)) return false; + if (props & MARK) { + if (flags & 0x10) return mark_set_covers(c->s, match_props >> 16, info->codepoint); + if (flags & 0xFF00) return (flags & 0xFF00) == (props & 0xFF00); + } + return true; +} + +/* What a glyph matches against: a glyph id, a class of a ClassDef, or a + * Coverage (by its offset from the subtable), one value per position. */ +enum { MATCH_ANY, MATCH_GLYPH, MATCH_CLASS, MATCH_COVERAGE }; +typedef struct { + int kind; + uint32_t data; /* the ClassDef, or the subtable the coverages' offsets start from */ + uint32_t values; /* where the values are */ +} Matcher; + +typedef struct { + Apply *c; + uint32_t lookup_props, mask; + bool ignore_zwnj, ignore_zwj, ignore_hidden; + Matcher matcher; + uint32_t glyph_data; + size_t idx, end; +} Skippy; + +enum { SKIP_NO, SKIP_YES, SKIP_MAYBE }; +enum { MATCH_NO, MATCH_YES, MATCH_MAYBE }; +enum { MATCH, NOT_MATCH, SKIP }; + +static void skippy_init(Skippy *it, Apply *c, bool context_match, size_t start) { + *it = (Skippy){c, c->lookup_props, context_match ? 0xFFFFFFFFu : c->lookup_mask, + c->table == 1 || (context_match && c->auto_zwnj), context_match || c->auto_zwj, c->table == 1, + {MATCH_ANY, 0, 0}, 0, start, c->b->len}; +} + +static int may_skip(const Skippy *it, const Info *info) { + if (!check_glyph_property(it->c, info, it->lookup_props)) return SKIP_YES; + if (is_default_ignorable(info) && (it->ignore_zwnj || !is_zwnj(info)) && (it->ignore_zwj || !is_zwj(info)) && + (it->ignore_hidden || !(info->uprops & UPROPS_HIDDEN))) + return SKIP_MAYBE; + return SKIP_NO; +} + +static bool matches(const Apply *c, const Matcher *m, uint32_t index, uint32_t glyph) { + uint32_t value = get16(c->t, m->values + 2 * index); + switch (m->kind) { + case MATCH_GLYPH: return glyph == value; + case MATCH_CLASS: return class_of(c->t, m->data, glyph) == value; + case MATCH_COVERAGE: return coverage(c->t, value ? m->data + value : 0, glyph) != NOT_COVERED; + default: return true; + } +} + +static int may_match(const Skippy *it, const Info *info) { + if (!(info->mask & it->mask)) return MATCH_NO; + if (it->matcher.kind != MATCH_ANY) return matches(it->c, &it->matcher, it->glyph_data, info->codepoint) ? MATCH_YES : MATCH_NO; + return MATCH_MAYBE; +} + +static int skippy_match(const Skippy *it, const Info *info) { + int skip = may_skip(it, info); + if (skip == SKIP_YES) return SKIP; + int match = may_match(it, info); + if (match == MATCH_YES || (match == MATCH_MAYBE && skip == SKIP_NO)) return MATCH; + return skip == SKIP_NO ? NOT_MATCH : SKIP; +} + +static bool skippy_next(Skippy *it, size_t *unsafe_to) { + while (it->idx + 1 < it->end) { + it->idx++; + switch (skippy_match(it, &it->c->b->info[it->idx])) { + case MATCH: it->glyph_data++; return true; + case NOT_MATCH: if (unsafe_to) *unsafe_to = it->idx + 1; return false; + default: continue; + } + } + if (unsafe_to) *unsafe_to = it->end; + return false; +} + +static bool skippy_prev(Skippy *it) { + const Info *outs = out_info(it->c->b); + while (it->idx > 0) { + it->idx--; + switch (skippy_match(it, &outs[it->idx])) { + case MATCH: it->glyph_data++; return true; + case NOT_MATCH: return false; + default: continue; + } + } + return false; +} + +static uint8_t lig_id(const Info *i) { return i->lig_props >> 5; } +static bool ligated_internal(const Info *i) { return i->lig_props & 0x10; } +static uint8_t lig_comp(const Info *i) { return ligated_internal(i) ? 0 : i->lig_props & 0x0F; } +static uint8_t lig_num_comps(const Info *i) { return (i->gprops & LIGATURE) && ligated_internal(i) ? i->lig_props & 0x0F : 1; } +static void set_lig_props_for_ligature(Info *i, uint8_t id, uint8_t comps) { i->lig_props = (uint8_t)(id << 5 | 0x10 | (comps & 0x0F)); } +static void set_lig_props_for_mark(Info *i, uint8_t id, uint8_t comp) { i->lig_props = (uint8_t)(id << 5 | (comp & 0x0F)); } + +/* Match count - 1 more glyphs after the current one against matcher; + * their positions go to positions[1..], the first's to positions[0]. */ +static bool match_input(Apply *c, unsigned count, Matcher matcher, size_t *end_position, size_t *positions, + unsigned *total_component_count) { + if (count > MAX_CONTEXT_LENGTH) return false; + VegaShaper *b = c->b; + Skippy it; + skippy_init(&it, c, false, b->idx); + it.matcher = matcher; + unsigned first_lig_id = lig_id(&b->info[b->idx]), first_lig_comp = lig_comp(&b->info[b->idx]), total = 0; + enum { NOT_CHECKED, MAY_NOT_SKIP, MAY_SKIP } ligbase = NOT_CHECKED; + for (unsigned i = 1; i < count; ++i) { + size_t unsafe_to; + if (!skippy_next(&it, &unsafe_to)) { + *end_position = unsafe_to; + return false; + } + positions[i] = it.idx; + const Info *this = &b->info[it.idx]; + unsigned this_lig_id = lig_id(this), this_lig_comp = lig_comp(this); + if (first_lig_id && first_lig_comp) { + /* Attached to a component of an earlier ligature: all must be + * attached to the same one, unless that ligature is skipped. */ + if (first_lig_id != this_lig_id || first_lig_comp != this_lig_comp) { + if (ligbase == NOT_CHECKED) { + const Info *out = out_info(b); + size_t j = b->have_output ? b->out_len : 0; + bool found = false; + while (j && lig_id(&out[j - 1]) == first_lig_id) { + if (!lig_comp(&out[j - 1])) { + j--; + found = true; + break; + } + j--; + } + ligbase = found && may_skip(&it, &out[j]) == SKIP_YES ? MAY_SKIP : MAY_NOT_SKIP; + } + if (ligbase == MAY_NOT_SKIP) return false; + } + } else if (this_lig_id && this_lig_comp && this_lig_id != first_lig_id) + return false; + total += lig_num_comps(this); + } + *end_position = it.idx + 1; + if (total_component_count) *total_component_count = total + lig_num_comps(&b->info[b->idx]); + positions[0] = b->idx; + return true; +} + +static bool match_backtrack(Apply *c, unsigned count, Matcher matcher) { + Skippy it; + skippy_init(&it, c, true, backtrack_len(c->b)); + it.matcher = matcher; + for (unsigned i = 0; i < count; ++i) + if (!skippy_prev(&it)) return false; + return true; +} + +static bool match_lookahead(Apply *c, unsigned count, Matcher matcher, size_t start) { + Skippy it; + skippy_init(&it, c, true, start - 1); + it.matcher = matcher; + for (unsigned i = 0; i < count; ++i) + if (!skippy_next(&it, NULL)) return false; + return true; +} + +static void set_glyph_class(Apply *c, uint32_t glyph, unsigned class_guess, bool ligature, bool component) { + digest_add_range(&c->digest, glyph, glyph); + Info *cur = &c->b->info[c->b->idx]; + unsigned props = cur->gprops | SUBSTITUTED; + if (ligature) props = (props | LIGATED) & ~(unsigned)MULTIPLIED; + if (component) props |= MULTIPLIED; + if (c->has_glyph_classes) props = (props & PRESERVE) | glyph_props(c->s, glyph); + else if (class_guess) props = (props & PRESERVE) | class_guess; + cur->gprops = (uint16_t)props; +} + +static void apply_replace_glyph(Apply *c, uint32_t glyph) { + set_glyph_class(c, glyph, 0, false, false); + replace_glyph(c->b, glyph); +} + +static void replace_glyph_inplace(Apply *c, uint32_t glyph) { + set_glyph_class(c, glyph, 0, false, false); + c->b->info[c->b->idx].codepoint = glyph; +} + +static bool apply_lookup_index(Apply *c, uint32_t lookup_index); + +static bool recurse(Apply *c, uint32_t lookup_index) { + if (!c->nesting_left || c->b->max_ops-- <= 0) return false; + c->nesting_left--; + uint32_t saved = c->lookup_props; + bool ret = apply_lookup_index(c, lookup_index); + c->lookup_props = saved; + c->nesting_left++; + return ret; +} + +/* Run a (chain) context rule's lookups at the positions matched. */ +static void apply_lookup(Apply *c, unsigned count, size_t *positions, uint32_t records, unsigned record_count, + size_t match_end) { + VegaShaper *b = c->b; + size_t bl = backtrack_len(b); + long end = (long)bl + (long)match_end - (long)b->idx, delta = (long)bl - (long)b->idx; + for (unsigned j = 0; j < count; ++j) positions[j] = (size_t)((long)positions[j] + delta); + for (unsigned i = 0; i < record_count && b->successful; ++i) { + unsigned idx = get16(c->t, records + 4 * i); + uint32_t lookup = get16(c->t, records + 4 * i + 2); + if (idx >= count) continue; + size_t orig_len = backtrack_len(b) + lookahead_len(b); + if (positions[idx] >= orig_len) continue; + if (!move_to(b, positions[idx])) break; + if (b->max_ops <= 0) break; + if (!recurse(c, lookup)) continue; + size_t new_len = backtrack_len(b) + lookahead_len(b); + long d = (long)new_len - (long)orig_len; + if (!d) continue; + end += d; + if (end < (long)positions[idx]) { + d += (long)positions[idx] - end; + end = (long)positions[idx]; + } + long next = idx + 1; + if (d > 0) { + if (d + count > MAX_CONTEXT_LENGTH) break; + } else { + if (d < next - (long)count) d = next - (long)count; + next -= d; + } + memmove(positions + next + d, positions + next, (size_t)((long)count - next) * sizeof(*positions)); + next += d; + count = (unsigned)((long)count + d); + for (long j = idx + 1; j < next; ++j) positions[j] = positions[j - 1] + 1; + for (; next < (long)count; ++next) positions[next] = (size_t)((long)positions[next] + d); + } + move_to(b, (size_t)end); +} + +static void ligate_input(Apply *c, unsigned count, const size_t *positions, size_t match_end, uint32_t lig_glyph, + unsigned total_component_count) { + VegaShaper *b = c->b; + merge_clusters(b, b->idx, match_end); + bool is_base_ligature = b->info[positions[0]].gprops & BASE_GLYPH; + bool is_mark_ligature = b->info[positions[0]].gprops & MARK; + for (unsigned i = 1; i < count; ++i) + if (!(b->info[positions[i]].gprops & MARK)) { + is_base_ligature = is_mark_ligature = false; + break; + } + bool is_ligature = !is_base_ligature && !is_mark_ligature; + uint8_t id = is_ligature ? allocate_lig_id(b) : 0; + Info *cur = &b->info[b->idx]; + unsigned last_lig_id = lig_id(cur), last_num_components = lig_num_comps(cur), components_so_far = last_num_components; + if (is_ligature) { + set_lig_props_for_ligature(cur, id, (uint8_t)total_component_count); + if (gen_cat(cur) == VEGA_MN) cur->uprops = (uint16_t)((cur->uprops & ~0x1Fu) | VEGA_LO); + } + set_glyph_class(c, lig_glyph, is_ligature ? LIGATURE : 0, true, false); + replace_glyph(b, lig_glyph); + for (unsigned i = 1; i < count; ++i) { + while (b->idx < positions[i] && b->successful) { + if (is_ligature) { + Info *mark = &b->info[b->idx]; + unsigned this_comp = lig_comp(mark); + if (!this_comp) this_comp = last_num_components; + unsigned comp = components_so_far - last_num_components + + (this_comp < last_num_components ? this_comp : last_num_components); + set_lig_props_for_mark(mark, id, (uint8_t)comp); + } + next_glyph(b); + } + last_lig_id = lig_id(&b->info[b->idx]); + last_num_components = lig_num_comps(&b->info[b->idx]); + components_so_far += last_num_components; + b->idx++; /* the component itself */ + } + if (!is_mark_ligature && last_lig_id) + for (size_t i = b->idx; i < b->len; ++i) { + Info *mark = &b->info[i]; + if (last_lig_id != lig_id(mark)) break; + unsigned this_comp = lig_comp(mark); + if (!this_comp) break; + unsigned comp = components_so_far - last_num_components + + (this_comp < last_num_components ? this_comp : last_num_components); + set_lig_props_for_mark(mark, id, (uint8_t)comp); + } +} + +/* Context and chain context rules, for GSUB and GPOS alike. A rule's + * sequences are glyphs (format 1) or classes (format 2). */ +static bool context_rule(Apply *c, uint32_t rule, Matcher input) { + unsigned input_count = get16(c->t, rule), record_count = get16(c->t, rule + 2); + input.values = rule + 4; + size_t positions[MAX_CONTEXT_LENGTH], match_end = 0; + if (!input_count || input_count > MAX_CONTEXT_LENGTH) return false; + if (!match_input(c, input_count, input, &match_end, positions, NULL)) return false; + apply_lookup(c, input_count, positions, rule + 4 + 2 * (input_count - 1), record_count, match_end); + return true; +} + +static bool chain_rule(Apply *c, uint32_t rule, Matcher back, Matcher input, Matcher ahead) { + VegaTable t = c->t; + unsigned back_count = get16(t, rule); + uint32_t at = rule + 2 + 2 * back_count; + unsigned input_count = get16(t, at); + if (!input_count || input_count > MAX_CONTEXT_LENGTH) return false; + uint32_t input_values = at + 2, ahead_at = input_values + 2 * (input_count - 1); + unsigned ahead_count = get16(t, ahead_at); + uint32_t records_at = ahead_at + 2 + 2 * ahead_count; + unsigned record_count = get16(t, records_at); + back.values = rule + 2; + input.values = input_values; + ahead.values = ahead_at + 2; + size_t positions[MAX_CONTEXT_LENGTH], match_end = 0; + if (!match_input(c, input_count, input, &match_end, positions, NULL) || !match_lookahead(c, ahead_count, ahead, match_end)) + return false; + if (!match_backtrack(c, back_count, back)) return false; + apply_lookup(c, input_count, positions, records_at + 2, record_count, match_end); + return true; +} + +static bool context_apply(Apply *c, uint32_t at) { + VegaTable t = c->t; + uint32_t glyph = c->b->info[c->b->idx].codepoint, format = get16(t, at); + if (format == 1 || format == 2) { + uint32_t index = coverage(t, offset16(t, at, at + 2), glyph); + if (index == NOT_COVERED) return false; + uint32_t classes = format == 2 ? offset16(t, at, at + 4) : 0; + uint32_t sets_at = format == 2 ? at + 6 : at + 4; + if (format == 2) index = class_of(t, classes, glyph); + if (index >= get16(t, sets_at)) return false; + uint32_t set = offset16(t, at, sets_at + 2 + 2 * index); + if (!set) return false; + Matcher input = {format == 2 ? MATCH_CLASS : MATCH_GLYPH, classes, 0}; + for (uint32_t r = 0, n = get16(t, set); r < n; ++r) + if (context_rule(c, offset16(t, set, set + 2 + 2 * r), input)) return true; + return false; + } + if (format == 3) { + unsigned input_count = get16(t, at + 2), record_count = get16(t, at + 4); + if (!input_count || coverage(t, offset16(t, at, at + 6), glyph) == NOT_COVERED) return false; + if (input_count > MAX_CONTEXT_LENGTH) return false; + Matcher input = {MATCH_COVERAGE, at, at + 8}; + size_t positions[MAX_CONTEXT_LENGTH], match_end = 0; + if (!match_input(c, input_count, input, &match_end, positions, NULL)) return false; + apply_lookup(c, input_count, positions, at + 6 + 2 * input_count, record_count, match_end); + return true; + } + return false; +} + +static bool chain_context_apply(Apply *c, uint32_t at) { + VegaTable t = c->t; + uint32_t glyph = c->b->info[c->b->idx].codepoint, format = get16(t, at); + if (format == 1 || format == 2) { + uint32_t index = coverage(t, offset16(t, at, at + 2), glyph); + if (index == NOT_COVERED) return false; + Matcher back = {MATCH_GLYPH, 0, 0}, input = back, ahead = back; + uint32_t sets_at = at + 4; + if (format == 2) { + back = (Matcher){MATCH_CLASS, offset16(t, at, at + 4), 0}; + input = (Matcher){MATCH_CLASS, offset16(t, at, at + 6), 0}; + ahead = (Matcher){MATCH_CLASS, offset16(t, at, at + 8), 0}; + sets_at = at + 10; + index = class_of(t, input.data, glyph); + } + if (index >= get16(t, sets_at)) return false; + uint32_t set = offset16(t, at, sets_at + 2 + 2 * index); + if (!set) return false; + for (uint32_t r = 0, n = get16(t, set); r < n; ++r) + if (chain_rule(c, offset16(t, set, set + 2 + 2 * r), back, input, ahead)) return true; + return false; + } + if (format == 3) { + unsigned back_count = get16(t, at + 2); + uint32_t input_at = at + 4 + 2 * back_count; + unsigned input_count = get16(t, input_at); + if (!input_count || input_count > MAX_CONTEXT_LENGTH) return false; + if (coverage(t, offset16(t, at, input_at + 2), glyph) == NOT_COVERED) return false; + uint32_t ahead_at = input_at + 2 + 2 * input_count; + unsigned ahead_count = get16(t, ahead_at); + uint32_t records_at = ahead_at + 2 + 2 * ahead_count; + Matcher back = {MATCH_COVERAGE, at, at + 4}, input = {MATCH_COVERAGE, at, input_at + 4}, + ahead = {MATCH_COVERAGE, at, ahead_at + 2}; + size_t positions[MAX_CONTEXT_LENGTH], match_end = 0; + if (!match_input(c, input_count, input, &match_end, positions, NULL) || + !match_lookahead(c, ahead_count, ahead, match_end)) + return false; + if (!match_backtrack(c, back_count, back)) return false; + apply_lookup(c, input_count, positions, records_at + 2, get16(t, records_at), match_end); + return true; + } + return false; +} + +/* ---- GSUB */ + +static bool single_subst(Apply *c, uint32_t at) { + VegaTable t = c->t; + uint32_t glyph = c->b->info[c->b->idx].codepoint, format = get16(t, at); + uint32_t index = coverage(t, offset16(t, at, at + 2), glyph); + if (index == NOT_COVERED) return false; + if (format == 1) apply_replace_glyph(c, (glyph + get16(t, at + 4)) & 0xFFFF); + else if (format == 2 && index < get16(t, at + 4)) apply_replace_glyph(c, get16(t, at + 6 + 2 * index)); + else return false; + return true; +} + +static bool multiple_subst(Apply *c, uint32_t at) { + VegaTable t = c->t; + VegaShaper *b = c->b; + uint32_t index = coverage(t, offset16(t, at, at + 2), b->info[b->idx].codepoint); + if (get16(t, at) != 1 || index == NOT_COVERED || index >= get16(t, at + 4)) return false; + uint32_t sequence = offset16(t, at, at + 6 + 2 * index); + unsigned count = get16(t, sequence); + if (count == 1) { + apply_replace_glyph(c, get16(t, sequence + 2)); + return true; + } + if (!count) { + delete_glyph(b); + return true; + } + unsigned klass = b->info[b->idx].gprops & LIGATURE ? BASE_GLYPH : 0; + unsigned id = lig_id(&b->info[b->idx]); + for (unsigned i = 0; i < count; ++i) { + if (!id) set_lig_props_for_mark(&b->info[b->idx], 0, (uint8_t)i); + uint32_t glyph = get16(t, sequence + 2 + 2 * i); + set_glyph_class(c, glyph, klass, false, true); + output_glyph(b, glyph); + } + skip_glyph(b); + return true; +} + +static bool alternate_subst(Apply *c, uint32_t at) { + VegaTable t = c->t; + VegaShaper *b = c->b; + uint32_t index = coverage(t, offset16(t, at, at + 2), b->info[b->idx].codepoint); + if (get16(t, at) != 1 || index == NOT_COVERED || index >= get16(t, at + 4)) return false; + uint32_t set = offset16(t, at, at + 6 + 2 * index); + unsigned count = get16(t, set); + if (!count) return false; + uint32_t mask = c->lookup_mask, shift = 0; + while (shift < 31 && !(mask >> shift & 1)) shift++; + uint32_t alt = (mask & b->info[b->idx].mask) >> shift; + if (alt == 255 && c->random) { + c->random_state = c->random_state * 48271u % 2147483647u; + alt = c->random_state % count + 1; + } + if (alt > count || !alt) return false; + apply_replace_glyph(c, get16(t, set + 2 + 2 * (alt - 1))); + return true; +} + +static bool ligature_subst(Apply *c, uint32_t at) { + VegaTable t = c->t; + VegaShaper *b = c->b; + uint32_t index = coverage(t, offset16(t, at, at + 2), b->info[b->idx].codepoint); + if (get16(t, at) != 1 || index == NOT_COVERED || index >= get16(t, at + 4)) return false; + uint32_t set = offset16(t, at, at + 6 + 2 * index); + for (uint32_t k = 0, n = get16(t, set); k < n; ++k) { + uint32_t lig = offset16(t, set, set + 2 + 2 * k); + uint32_t glyph = get16(t, lig); + unsigned count = get16(t, lig + 2); + if (!count) continue; + if (count == 1) { + apply_replace_glyph(c, glyph); + return true; + } + if (count > MAX_CONTEXT_LENGTH) continue; + size_t positions[MAX_CONTEXT_LENGTH], match_end = 0; + unsigned total = 0; + if (!match_input(c, count, (Matcher){MATCH_GLYPH, 0, lig + 4}, &match_end, positions, &total)) continue; + ligate_input(c, count, positions, match_end, glyph, total); + return true; + } + return false; +} + +static bool reverse_chain_single_subst(Apply *c, uint32_t at) { + VegaTable t = c->t; + VegaShaper *b = c->b; + uint32_t index = coverage(t, offset16(t, at, at + 2), b->info[b->idx].codepoint); + if (get16(t, at) != 1 || index == NOT_COVERED || c->nesting_left != MAX_NESTING_LEVEL) return false; + unsigned back_count = get16(t, at + 4); + uint32_t ahead_at = at + 6 + 2 * back_count; + unsigned ahead_count = get16(t, ahead_at); + uint32_t subst_at = ahead_at + 2 + 2 * ahead_count; + if (index >= get16(t, subst_at)) return false; + Matcher back = {MATCH_COVERAGE, at, at + 6}, ahead = {MATCH_COVERAGE, at, ahead_at + 2}; + if (match_backtrack(c, back_count, back) && match_lookahead(c, ahead_count, ahead, b->idx + 1)) { + replace_glyph_inplace(c, get16(t, subst_at + 2 + 2 * index)); + return true; + } + return false; +} + +/* ---- GPOS */ + +typedef struct { int32_t x_placement, y_placement, x_advance; } Value; + +static unsigned value_length(unsigned format) { return (unsigned)__builtin_popcount(format); } + +/* Apply a ValueRecord to a position; whether it moved anything. Device + * tables apply only at a size in pixels, and positions here are in the + * font's units: they are passed over. */ +static bool apply_value(Apply *c, unsigned format, uint32_t at, Position *pos) { + bool worked = false; + int32_t v; + if (format & 1) { + pos->x_offset += v = gets16(c->t, at), at += 2; + worked |= v != 0; + } + if (format & 2) { + pos->y_offset += v = gets16(c->t, at), at += 2; + worked |= v != 0; + } + if (format & 4) { + pos->x_advance += v = gets16(c->t, at), at += 2; + worked |= v != 0; + } + return worked; +} + +static bool single_pos(Apply *c, uint32_t at) { + VegaTable t = c->t; + VegaShaper *b = c->b; + uint32_t index = coverage(t, offset16(t, at, at + 2), b->info[b->idx].codepoint); + if (index == NOT_COVERED) return false; + unsigned format = get16(t, at + 4); + if (get16(t, at) == 1) apply_value(c, format, at + 6, &b->pos[b->idx]); + else if (get16(t, at) == 2 && index < get16(t, at + 6)) + apply_value(c, format, at + 8 + 2 * value_length(format) * index, &b->pos[b->idx]); + else return false; + b->idx++; + return true; +} + +static bool pair_pos(Apply *c, uint32_t at) { + VegaTable t = c->t; + VegaShaper *b = c->b; + uint32_t index = coverage(t, offset16(t, at, at + 2), b->info[b->idx].codepoint); + if (index == NOT_COVERED) return false; + Skippy it; + skippy_init(&it, c, false, b->idx); + if (!skippy_next(&it, NULL)) return false; + size_t pos = it.idx; + unsigned format1 = get16(t, at + 4), format2 = get16(t, at + 6), len1 = value_length(format1), + len2 = value_length(format2); + uint32_t values; + if (get16(t, at) == 1) { + if (index >= get16(t, at + 8)) return false; + uint32_t set = offset16(t, at, at + 10 + 2 * index); + unsigned count = get16(t, set), size = 2 * (1 + len1 + len2); + uint32_t second = b->info[pos].codepoint, low = 0, high = count, found = NOT_COVERED; + while (low < high) { + uint32_t middle = (low + high) / 2, g = get16(t, set + 2 + size * middle); + if (g < second) low = middle + 1; + else if (g > second) high = middle; + else { + found = middle; + break; + } + } + if (found == NOT_COVERED) return false; + values = set + 2 + size * found + 2; + } else if (get16(t, at) == 2) { + /* Class 0 of the second glyph applies too (its values often 0): the + * subtables after it are not tried. */ + uint32_t klass2 = class_of(t, offset16(t, at, at + 10), b->info[pos].codepoint); + uint32_t klass1 = class_of(t, offset16(t, at, at + 8), b->info[b->idx].codepoint); + unsigned class1_count = get16(t, at + 12), class2_count = get16(t, at + 14); + if (klass1 >= class1_count || klass2 >= class2_count) return false; + values = at + 16 + 2 * (len1 + len2) * (klass1 * class2_count + klass2); + } else + return false; + if (len1) apply_value(c, format1, values, &b->pos[b->idx]); + if (len2) apply_value(c, format2, values + 2 * len1, &b->pos[pos]); + if (len2) pos++; + b->idx = pos; + return true; +} + +static bool anchor(Apply *c, uint32_t at, int32_t *x, int32_t *y) { + if (!at) return false; + unsigned format = get16(c->t, at); + if (format < 1 || format > 3) { + *x = *y = 0; + return true; + } + *x = gets16(c->t, at + 2); + *y = gets16(c->t, at + 4); + return true; +} + +enum { ATTACH_MARK = 1, ATTACH_CURSIVE = 2 }; + +static void reverse_cursive_minor_offset(Position *pos, size_t i, int direction, size_t new_parent) { + int32_t chain = pos[i].chain; + uint8_t type = pos[i].attach; + if (!chain || !(type & ATTACH_CURSIVE)) return; + pos[i].chain = 0; + size_t j = (size_t)((long)i + chain); + if (j == new_parent) return; + reverse_cursive_minor_offset(pos, j, direction, new_parent); + pos[j].y_offset = -pos[i].y_offset; + pos[j].chain = -chain; + pos[j].attach = type; + (void)direction; +} + +static bool cursive_pos(Apply *c, uint32_t at) { + VegaTable t = c->t; + VegaShaper *b = c->b; + uint32_t cov = offset16(t, at, at + 2), count = get16(t, at + 4); + uint32_t this_index = coverage(t, cov, b->info[b->idx].codepoint); + uint32_t entry_this = this_index < count ? offset16(t, at, at + 6 + 4 * this_index) : 0; + if (!entry_this || get16(t, at) != 1) return false; + Skippy it; + skippy_init(&it, c, false, b->idx); + if (!skippy_prev(&it)) return false; + size_t i = it.idx, j = b->idx; + uint32_t prev_index = coverage(t, cov, b->info[i].codepoint); + uint32_t exit_prev = prev_index < count ? offset16(t, at, at + 6 + 4 * prev_index + 2) : 0; + if (!exit_prev) return false; + int32_t entry_x, entry_y, exit_x, exit_y; + anchor(c, exit_prev, &exit_x, &exit_y); + anchor(c, entry_this, &entry_x, &entry_y); + Position *pos = b->pos; + int32_t d; + if (b->direction == VEGA_SHAPE_LTR) { + pos[i].x_advance = exit_x + pos[i].x_offset; + d = entry_x + pos[j].x_offset; + pos[j].x_advance -= d; + pos[j].x_offset -= d; + } else { + d = exit_x + pos[i].x_offset; + pos[i].x_advance -= d; + pos[i].x_offset -= d; + pos[j].x_advance = entry_x + pos[j].x_offset; + } + size_t child = i, parent = j; + int32_t y_offset = entry_y - exit_y; + if (!(c->lookup_props & 1)) { + child = j, parent = i; + y_offset = -y_offset; + } + reverse_cursive_minor_offset(pos, child, b->direction, parent); + pos[child].attach = ATTACH_CURSIVE; + pos[child].chain = (int32_t)((long)parent - (long)child); + b->scratch |= HAS_GPOS_ATTACHMENT; + pos[child].y_offset = y_offset; + if (pos[parent].chain == -pos[child].chain) { + pos[parent].chain = 0; + pos[parent].y_offset = 0; + } + b->idx++; + return true; +} + +/* A mark's record: its class and anchor; the anchor it attaches to is in + * the matrix at (row, class). */ +static bool mark_array_apply(Apply *c, uint32_t mark_array, uint32_t mark_index, uint32_t matrix, uint32_t row, + unsigned class_count, size_t glyph_pos) { + VegaTable t = c->t; + VegaShaper *b = c->b; + /* Past the array, HarfBuzz reads an empty record: class 0, no anchor. */ + bool inside = mark_index < get16(t, mark_array); + uint32_t record = mark_array + 2 + 4 * mark_index; + unsigned mark_class = inside ? get16(t, record) : 0; + uint32_t mark_anchor = inside ? offset16(t, mark_array, record + 2) : 0; + if (row >= get16(t, matrix) || mark_class >= class_count) return false; + uint32_t glyph_anchor = offset16(t, matrix, matrix + 2 + 2 * (row * class_count + mark_class)); + if (!glyph_anchor) return false; + int32_t mark_x = 0, mark_y = 0, base_x, base_y; + anchor(c, mark_anchor, &mark_x, &mark_y); + anchor(c, glyph_anchor, &base_x, &base_y); + Position *o = &b->pos[b->idx]; + o->x_offset = base_x - mark_x; + o->y_offset = base_y - mark_y; + o->attach = ATTACH_MARK; + o->chain = (int32_t)((long)glyph_pos - (long)b->idx); + b->scratch |= HAS_GPOS_ATTACHMENT; + b->idx++; + return true; +} + +static bool multiplied(const Info *i) { return i->gprops & MULTIPLIED; } + +/* Marks attach to the first glyph of what a multiple substitution made. */ +static bool accept_base(const VegaShaper *b, size_t idx) { + const Info *info = b->info; + return !multiplied(&info[idx]) || !lig_comp(&info[idx]) || idx == 0 || (info[idx - 1].gprops & MARK) || + !multiplied(&info[idx - 1]) || lig_id(&info[idx]) != lig_id(&info[idx - 1]) || + lig_comp(&info[idx]) != lig_comp(&info[idx - 1]) + 1; +} + +/* The nearest glyph before that is not a mark (cached along the lookup). */ +static bool find_base(Apply *c, uint32_t base_coverage, bool mark_base) { + VegaShaper *b = c->b; + Skippy it; + skippy_init(&it, c, false, b->idx); + it.lookup_props = 0x08; /* IgnoreMarks */ + if (c->last_base_until > b->idx) { + c->last_base_until = 0; + c->last_base = -1; + } + for (size_t j = b->idx; j > c->last_base_until; --j) { + int match = skippy_match(&it, &b->info[j - 1]); + if (match == MATCH && mark_base && !accept_base(b, j - 1) && + coverage(c->t, base_coverage, b->info[j - 1].codepoint) == NOT_COVERED) + match = SKIP; + if (match == MATCH) { + c->last_base = (long)j - 1; + break; + } + } + c->last_base_until = b->idx; + return c->last_base != -1; +} + +static bool mark_base_pos(Apply *c, uint32_t at) { + VegaTable t = c->t; + VegaShaper *b = c->b; + uint32_t mark_index = coverage(t, offset16(t, at, at + 2), b->info[b->idx].codepoint); + if (get16(t, at) != 1 || mark_index == NOT_COVERED) return false; + uint32_t base_coverage = offset16(t, at, at + 4); + if (!find_base(c, base_coverage, true)) return false; + size_t idx = (size_t)c->last_base; + uint32_t base_index = coverage(t, base_coverage, b->info[idx].codepoint); + if (base_index == NOT_COVERED) return false; + return mark_array_apply(c, offset16(t, at, at + 8), mark_index, offset16(t, at, at + 10), base_index, + get16(t, at + 6), idx); +} + +static bool mark_lig_pos(Apply *c, uint32_t at) { + VegaTable t = c->t; + VegaShaper *b = c->b; + uint32_t mark_index = coverage(t, offset16(t, at, at + 2), b->info[b->idx].codepoint); + if (get16(t, at) != 1 || mark_index == NOT_COVERED) return false; + if (!find_base(c, 0, false)) return false; + size_t idx = (size_t)c->last_base; + uint32_t lig_index = coverage(t, offset16(t, at, at + 4), b->info[idx].codepoint); + if (lig_index == NOT_COVERED) return false; + uint32_t lig_array = offset16(t, at, at + 10); + if (lig_index >= get16(t, lig_array)) return false; + uint32_t attach = offset16(t, lig_array, lig_array + 2 + 2 * lig_index); + unsigned comp_count = get16(t, attach); + if (!comp_count) return false; + unsigned id = lig_id(&b->info[idx]), mark_id = lig_id(&b->info[b->idx]), mark_comp = lig_comp(&b->info[b->idx]); + unsigned comp_index = id && id == mark_id && mark_comp > 0 ? (mark_comp < comp_count ? mark_comp : comp_count) - 1 + : comp_count - 1; + return mark_array_apply(c, offset16(t, at, at + 8), mark_index, attach, comp_index, get16(t, at + 6), idx); +} + +static bool mark_mark_pos(Apply *c, uint32_t at) { + VegaTable t = c->t; + VegaShaper *b = c->b; + uint32_t mark1_index = coverage(t, offset16(t, at, at + 2), b->info[b->idx].codepoint); + if (get16(t, at) != 1 || mark1_index == NOT_COVERED) return false; + Skippy it; + skippy_init(&it, c, false, b->idx); + it.lookup_props = c->lookup_props & ~0x0Eu; + if (!skippy_prev(&it)) return false; + size_t j = it.idx; + if (!(b->info[j].gprops & MARK)) return false; + unsigned id1 = lig_id(&b->info[b->idx]), id2 = lig_id(&b->info[j]), comp1 = lig_comp(&b->info[b->idx]), + comp2 = lig_comp(&b->info[j]); + bool good = id1 == id2 ? !id1 || comp1 == comp2 : (id1 && !comp1) || (id2 && !comp2); + if (!good) return false; + uint32_t mark2_index = coverage(t, offset16(t, at, at + 4), b->info[j].codepoint); + if (mark2_index == NOT_COVERED) return false; + return mark_array_apply(c, offset16(t, at, at + 8), mark1_index, offset16(t, at, at + 10), mark2_index, + get16(t, at + 6), j); +} + +/* ---- Lookups */ + +static bool apply_subtable(Apply *c, const VegaSubtable *st) { + if (!st->at) return false; + if (!c->table) switch (st->type) { + case 1: return single_subst(c, st->at); + case 2: return multiple_subst(c, st->at); + case 3: return alternate_subst(c, st->at); + case 4: return ligature_subst(c, st->at); + case 5: return context_apply(c, st->at); + case 6: return chain_context_apply(c, st->at); + case 8: return reverse_chain_single_subst(c, st->at); + default: return false; + } + switch (st->type) { + case 1: return single_pos(c, st->at); + case 2: return pair_pos(c, st->at); + case 3: return cursive_pos(c, st->at); + case 4: return mark_base_pos(c, st->at); + case 5: return mark_lig_pos(c, st->at); + case 6: return mark_mark_pos(c, st->at); + case 7: return context_apply(c, st->at); + case 8: return chain_context_apply(c, st->at); + default: return false; + } +} + +static bool apply_subtables(Apply *c, const VegaLookup *l) { + uint32_t glyph = c->b->info[c->b->idx].codepoint; + for (uint32_t k = 0; k < l->count; ++k) { + const VegaSubtable *st = &c->s->subtables[l->first + k]; + if (digest_may_have(&st->digest, glyph) && apply_subtable(c, st)) return true; + } + return false; +} + +static bool apply_lookup_index(Apply *c, uint32_t lookup_index) { + if (lookup_index >= c->s->lookup_count[c->table]) return false; + const VegaLookup *l = &c->s->lookups[c->table][lookup_index]; + c->lookup_props = l->props; + return c->b->idx < c->b->len && digest_may_have(&l->digest, c->b->info[c->b->idx].codepoint) && apply_subtables(c, l); +} + +static void apply_string(Apply *c, const VegaLookup *l) { + VegaShaper *b = c->b; + if (!b->len || !c->lookup_mask) return; + c->lookup_props = l->props; + if (!l->reverse) { + if (!c->table) clear_output(b); + b->idx = 0; + while (b->idx < b->len && b->successful) { + const Info *cur = &b->info[b->idx]; + if (!(digest_may_have(&l->digest, cur->codepoint) && (cur->mask & c->lookup_mask) && + check_glyph_property(c, cur, c->lookup_props) && apply_subtables(c, l))) + next_glyph(b); + } + if (!c->table) sync(b); + } else { + b->idx = b->len - 1; + for (;;) { + const Info *cur = &b->info[b->idx]; + if (digest_may_have(&l->digest, cur->codepoint) && (cur->mask & c->lookup_mask) && + check_glyph_property(c, cur, c->lookup_props)) + apply_subtables(c, l); + if (!b->idx) break; + b->idx--; + } + } +} + +/* The glyphs of the buffer, as a digest. */ +static VegaDigest buffer_digest(const VegaShaper *b) { + VegaDigest d = {{0, 0, 0}}; + for (size_t i = 0; i < b->len; ++i) digest_add_range(&d, b->info[i].codepoint, b->info[i].codepoint); + return d; +} + +static void apply_table(const VegaShaping *s, VegaShaper *b, int table, const unsigned char *steps, uint32_t count) { + /* A lookup can apply only where the buffer has a glyph it starts from. */ + Apply c = {s, b, table, table ? s->gpos : s->gsub, 0, 0, true, true, false, s->glyph_classes != 0, + MAX_NESTING_LEVEL, 1, -1, 0, buffer_digest(b)}; + for (uint32_t i = 0; i < count; ++i) { + const unsigned char *step = steps + (size_t)i * VEGA_STEP_BYTES; + uint32_t index = le16(step); + if (!digest_may_intersect(&s->lookups[table][index].digest, &c.digest)) continue; + c.lookup_mask = le32(step + 4); + c.last_base = -1; + c.last_base_until = 0; + c.auto_zwnj = step[2] & VEGA_STEP_AUTO_ZWNJ; + c.auto_zwj = step[2] & VEGA_STEP_AUTO_ZWJ; + c.random = step[2] & VEGA_STEP_RANDOM; + apply_string(&c, &s->lookups[table][index]); + } +} + +/* ---- Positions */ + +static void fallback_spaces(const VegaShaping *s, VegaShaper *b) { + for (size_t i = 0; i < b->len; ++i) { + const Info *info = &b->info[i]; + if (!is_unicode_space(info) || (info->gprops & LIGATED)) continue; + unsigned type = info->uprops >> 8; + int32_t upem = s->upem; + uint32_t glyph; + switch (type) { + case SPACE_EM: case SPACE_EM_2: case SPACE_EM_3: case SPACE_EM_4: case SPACE_EM_5: case SPACE_EM_6: + case SPACE_EM_16: + b->pos[i].x_advance = (upem + (int32_t)type / 2) / (int32_t)type; + break; + case SPACE_4_EM_18: b->pos[i].x_advance = (int32_t)((int64_t)upem * 4 / 18); break; + case SPACE_FIGURE: + for (uint32_t u = '0'; u <= '9'; ++u) + if (nominal(s, u, &glyph)) { + b->pos[i].x_advance = advance_of(s, glyph); + break; + } + break; + case SPACE_PUNCTUATION: + if (nominal(s, '.', &glyph) || nominal(s, ',', &glyph)) b->pos[i].x_advance = advance_of(s, glyph); + break; + case SPACE_NARROW: b->pos[i].x_advance /= 2; break; + default: break; + } + } +} + +static void propagate_attachment_offsets(Position *pos, size_t len, size_t i, int direction, int nesting) { + int32_t chain = pos[i].chain; + uint8_t type = pos[i].attach; + if (!chain) return; + pos[i].chain = 0; + size_t j = (size_t)((long)i + chain); + if (j >= len || !nesting) return; + propagate_attachment_offsets(pos, len, j, direction, nesting - 1); + if (type & ATTACH_CURSIVE) { + pos[i].y_offset += pos[j].y_offset; + return; + } + pos[i].x_offset += pos[j].x_offset; + pos[i].y_offset += pos[j].y_offset; + if (direction == VEGA_SHAPE_LTR) + for (size_t k = j; k < i; ++k) { + pos[i].x_offset -= pos[k].x_advance; + pos[i].y_offset -= pos[k].y_advance; + } + else + for (size_t k = j + 1; k < i + 1; ++k) { + pos[i].x_offset += pos[k].x_advance; + pos[i].y_offset += pos[k].y_advance; + } +} + +static void position(const VegaShaping *s, const Plan *plan, VegaShaper *b) { + b->have_output = false; + b->out_len = 0; + memset(b->pos, 0, b->len * sizeof(Position)); + for (size_t i = 0; i < b->len; ++i) b->pos[i].x_advance = advance_of(s, b->info[i].codepoint); + if (b->scratch & HAS_SPACE_FALLBACK) fallback_spaces(s, b); + if (plan->flags & VEGA_PLAN_GPOS) apply_table(s, b, 1, plan->gpos, plan->gpos_count); + if (plan->flags & VEGA_PLAN_ZERO_MARKS) + for (size_t i = 0; i < b->len; ++i) + if (b->info[i].gprops & MARK) b->pos[i].x_advance = b->pos[i].y_advance = 0; + if (b->scratch & HAS_DEFAULT_IGNORABLES) + for (size_t i = 0; i < b->len; ++i) + if (is_default_ignorable(&b->info[i])) + b->pos[i].x_advance = b->pos[i].y_advance = b->pos[i].x_offset = b->pos[i].y_offset = 0; + if (b->scratch & HAS_GPOS_ATTACHMENT) + for (size_t i = 0; i < b->len; ++i) propagate_attachment_offsets(b->pos, b->len, i, b->direction, MAX_NESTING_LEVEL); + if (b->direction == VEGA_SHAPE_RTL) reverse_range(b, 0, b->len, true); +} + +/* ---- Shaping (hb-ot-shape.cc) */ + +long vega_shape(VegaShaper *b, const VegaShaping *s, const uint32_t *codes, size_t count, uint32_t script, int direction, + const VegaShaped **out) { + Plan plan; + if (!find_plan(s, script, direction, &plan)) return -1; + b->len = b->out_len = b->idx = 0; + b->have_output = false; + b->successful = true; + b->scratch = b->serial = 0; + b->direction = direction; + b->max_len = count * 64 > 16384 ? count * 64 : 16384; + b->max_ops = (long)(count * 1024 > 16384 ? count * 1024 : 16384); + if (!ensure(b, count + 1)) return -1; + for (size_t i = 0; i < count; ++i) b->info[i] = (Info){codes[i], plan.global_mask, (uint32_t)i, 0, 0, 0, 0, 0}; + b->len = count; + + set_unicode_props(b); + form_clusters(b); + ensure_native_direction(b, &plan); + + /* Mirror what the font mirrors; mark the rest for rtlm. */ + if (direction == VEGA_SHAPE_RTL) + for (size_t i = 0; i < b->len; ++i) { + uint32_t mirror = vega_mirror(b->info[i].codepoint), glyph; + if (mirror && nominal(s, mirror, &glyph)) b->info[i].codepoint = mirror; + else b->info[i].mask |= plan.masks[VEGA_MASK_RTLM]; + } + normalize(s, &plan, b); + setup_masks_fraction(b, &plan); + if (plan.shaper == VEGA_SHAPER_ARABIC) setup_masks_arabic(b, &plan); + for (size_t i = 0; i < b->len; ++i) { + Info *info = &b->info[i]; + info->codepoint = info->glyph_index; + info->gprops = glyph_props(s, info->codepoint); + info->lig_props = 0; + if (plan.flags & VEGA_PLAN_GUESS_CLASSES) + info->gprops = gen_cat(info) != VEGA_MN || is_default_ignorable(info) ? BASE_GLYPH : MARK; + } + apply_table(s, b, 0, plan.gsub, plan.gsub_count); + if (!b->successful || !ensure(b, b->len)) return -1; + position(s, &plan, b); + + /* Hide what shows nothing: the space glyph, with nothing to advance. */ + if (b->scratch & HAS_DEFAULT_IGNORABLES) { + uint32_t invisible; + if (nominal(s, ' ', &invisible)) { + for (size_t i = 0; i < b->len; ++i) + if (is_default_ignorable(&b->info[i])) b->info[i].codepoint = invisible; + } else { + size_t j = 0; + for (size_t i = 0; i < b->len; ++i) { + if (is_default_ignorable(&b->info[i])) { + /* Its cluster goes to a neighbour (hb_buffer_t::delete_glyphs_inplace). */ + uint32_t cluster = b->info[i].cluster; + if (i + 1 < b->len && cluster == b->info[i + 1].cluster) continue; + if (j) { + if (cluster < b->info[j - 1].cluster) { + uint32_t old = b->info[j - 1].cluster; + for (size_t k = j; k && b->info[k - 1].cluster == old; k--) b->info[k - 1].cluster = cluster; + } + continue; + } + if (i + 1 < b->len) { + uint32_t next = b->info[i + 1].cluster; + for (size_t k = i + 1; k < b->len && b->info[k].cluster == next; ++k) + b->info[k].cluster = cluster < next ? cluster : next; + } + continue; + } + if (j != i) { + b->info[j] = b->info[i]; + b->pos[j] = b->pos[i]; + } + j++; + } + b->len = j; + } + } + + if (b->glyphs_allocated < b->len) { + VegaShaped *glyphs = realloc(b->glyphs, b->len * sizeof(*glyphs)); + if (!glyphs) return -1; + b->glyphs = glyphs; + b->glyphs_allocated = b->len; + } + for (size_t i = 0; i < b->len; ++i) + b->glyphs[i] = (VegaShaped){b->info[i].codepoint, b->info[i].cluster, b->pos[i].x_advance, b->pos[i].y_advance, + b->pos[i].x_offset, b->pos[i].y_offset}; + *out = b->glyphs; + return (long)b->len; +} diff --git a/text/shape.h b/text/shape.h new file mode 100644 index 0000000..5fe7c4e --- /dev/null +++ b/text/shape.h @@ -0,0 +1,101 @@ +#ifndef VEGA_SHAPE_H +#define VEGA_SHAPE_H +#include +#include +#include + +/* Shaping (docs/design/004-text.md): a run of characters (one script, one + * direction) to glyphs and their positions, as HarfBuzz 10 shapes it with + * its default, Arabic and Hebrew shapers, glyph for glyph and unit for unit. + * + * What a font's shaping needs travels in a symbol file (its shaping + * section), written by the build tool: + * - plans, compiled from the font: per script and direction, which + * lookups run, in what order, on which glyphs (the feature masks); + * - the font's character map and advances; + * - its OpenType layout tables (GDEF, GSUB, GPOS) as they are: they are + * read in place, every read checked against the table's end, so a + * damaged table shapes wrong but never reads outside it. + * Positions are in the font's units (VegaShaping.upem to an em). + * + * The section, little-endian: + * "VSHP", u32 size, u16 upem, u16 glyph_count, + * u32 cmap_count, u32 cmap_offset (u32 code, u32 glyph; by code), + * u32 advances_offset (glyph_count u16), + * u32 offset, u32 size of GDEF, of GSUB and of GPOS (0 0 when absent), + * u32 plan_count, u32 plans_offset (VEGA_PLAN_BYTES each), + * u32 step_count, u32 steps_offset (8 bytes each) + * Offsets are from the section's start. A plan: + * u32 script (ISO 15924 as a tag: 'Latn'), u8 direction, u8 native + * direction (of its script; 0 when it has none), u8 shaper, u8 flags, + * u32 global mask, u32 masks[VEGA_PLAN_MASKS], u32 first GSUB step, + * u32 GSUB steps, u32 first GPOS step, u32 GPOS steps. + * A step, a lookup to run: u16 lookup index, u8 flags, u8 0, u32 mask. */ +enum { VEGA_SHAPING_HEADER = 64, VEGA_PLAN_BYTES = 72, VEGA_STEP_BYTES = 8, VEGA_PLAN_MASKS = 11 }; +enum { VEGA_SHAPE_LTR = 1, VEGA_SHAPE_RTL = 2 }; +enum { VEGA_SHAPER_DEFAULT, VEGA_SHAPER_ARABIC, VEGA_SHAPER_HEBREW }; +/* Plan flags. */ +enum { VEGA_PLAN_GPOS = 1, VEGA_PLAN_ZERO_MARKS = 2, VEGA_PLAN_GUESS_CLASSES = 4, VEGA_PLAN_GPOS_MARK = 8, + VEGA_PLAN_FRACTIONS = 16 }; +/* The masks a plan names, for the features set glyph by glyph. */ +enum { VEGA_MASK_ISOL, VEGA_MASK_FINA, VEGA_MASK_FIN2, VEGA_MASK_FIN3, VEGA_MASK_MEDI, VEGA_MASK_MED2, + VEGA_MASK_INIT, VEGA_MASK_RTLM, VEGA_MASK_FRAC, VEGA_MASK_NUMR, VEGA_MASK_DNOM }; +/* Step flags. */ +enum { VEGA_STEP_AUTO_ZWNJ = 1, VEGA_STEP_AUTO_ZWJ = 2, VEGA_STEP_RANDOM = 4, VEGA_STEP_PER_SYLLABLE = 8 }; + +typedef struct { const unsigned char *p; uint32_t size; } VegaTable; +/* Which glyphs may be in a set, as three 64-bit patterns of glyph bits + * (HarfBuzz's set digest): a glyph whose bits are not all there is not. */ +typedef struct { uint64_t mask[3]; } VegaDigest; +typedef struct { + uint16_t type; /* with extensions resolved */ + uint32_t at; + VegaDigest digest; /* the glyphs it starts from */ +} VegaSubtable; +typedef struct { + uint16_t type, flags; + uint32_t props; /* flags, and the mark filtering set in the high half */ + uint32_t first, count; /* subtables */ + bool reverse; + VegaDigest digest; /* the glyphs its subtables start from */ +} VegaLookup; +typedef struct { + const unsigned char *bytes; + size_t size; + uint16_t upem, glyph_count; + uint32_t cmap_count, plan_count; + const unsigned char *cmap, *advances, *plans, *steps; + VegaTable gdef, gsub, gpos; + uint32_t glyph_classes, attach_classes, mark_sets; /* in GDEF; 0 when absent */ + VegaLookup *lookups[2]; /* GSUB, GPOS */ + uint32_t lookup_count[2]; + VegaSubtable *subtables; + uint16_t *bmp[256]; /* the character map's glyphs below U+10000, by page */ +} VegaShaping; + +/* Open a shaping section (kept, not copied); false with why. */ +bool vega_shaping_open(VegaShaping *, const unsigned char *bytes, size_t size, char *error, size_t error_size); +void vega_shaping_close(VegaShaping *); +/* The font's glyph for a character, or 0. */ +uint32_t vega_shaping_glyph(const VegaShaping *, uint32_t code); + +/* A shaped glyph, as HarfBuzz gives it: in visual order (left to right), + * cluster the index of the first character it came from; each glyph is + * drawn at the pen plus its offset, then the pen moves by its advance. */ +typedef struct { + uint32_t glyph, cluster; + int32_t x_advance, y_advance, x_offset, y_offset; +} VegaShaped; + +/* The buffers shaping works in, kept from one run to the next. */ +typedef struct VegaShaper VegaShaper; +VegaShaper *vega_shaper_new(void); +void vega_shaper_free(VegaShaper *); +/* Shape a run of count characters of script (an ISO 15924 tag, as + * vega_script_code gives it) in direction (VEGA_SHAPE_LTR or _RTL) by the + * plan compiled for them (or for Common, 'Zyyy', when there is none). The + * glyphs (as many as returned) are the shaper's until its next run; -1 + * when there is no plan or no memory. */ +long vega_shape(VegaShaper *, const VegaShaping *, const uint32_t *codes, size_t count, uint32_t script, int direction, + const VegaShaped **out); +#endif -- cgit v1.2.3