diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | docs/design/004-text.md | 15 | ||||
| -rw-r--r-- | text/harfbuzz-suite.known | 3 | ||||
| -rw-r--r-- | text/shape-build.c | 28 | ||||
| -rw-r--r-- | text/shape.c | 112 | ||||
| -rw-r--r-- | text/shape.h | 2 | ||||
| -rw-r--r-- | text/test-kern.py | 99 |
7 files changed, 235 insertions, 26 deletions
@@ -90,6 +90,8 @@ check: $(BUILD)/vega $(BUILD)/vega-symbols $(BUILD)/vega-surface.so $(BUILD)/tes 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 && \ $(BUILD)/test-layout $(BUILD)/shaped.vsym; else echo "no $(SHAPED_FONT): shaping tests skipped"; fi + if [ -f $(SHAPED_FONT) ] && python3 -c 'import fontTools' 2>/dev/null; then \ + python3 text/test-kern.py $(BUILD)/vega-symbols $(SHAPED_FONT); else echo "no fontTools: kern class 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 dd631af..58a53ad 100644 --- a/docs/design/004-text.md +++ b/docs/design/004-text.md @@ -99,9 +99,10 @@ Sentence_Break, 동아시아 폭이 F·W·H인 여는·닫는 괄호)와 규칙� 순서로 정렬한다), 거울 글자, 아랍 연결 상태 기계, GSUB(유형 1–8과 확장, 문맥과 연쇄 문맥의 형식 1–3, 역연쇄), 합자의 성분 추적, GPOS(유형 1–8, 짝 형식 1·2, 필기체, 기저·합자·부호에 붙는 부호), 부착 오프셋의 전파, 보이지 않는 문자 숨기기를 한다. 한글은 글꼴에 통째로 있는 음절은 자모를 합치고, 없는 음절은 자모로 풀어 `ljmo`·`vjmo`·`tjmo`를 걸고, 성조 - 기호는 음절 앞으로 옮긴다(앞에 음절이 없으면 점선 원을 넣는다). `kern` 표는 OpenType(판 0)과 Apple(1.0)의 짝 하위 표를 - 부호를 건너뛰며 적용하고 커닝을 두 글리프에 나눠 준다(HarfBuzz의 이진 탐색을 그대로 해서, 정렬이 어긋난 표도 같은 답을 - 낸다). GPOS가 없는 글꼴은 부호를 결합 등급(태국·라오·히브리·아랍·티베트는 HarfBuzz처럼 다시 분류한 등급)과 외곽 상자로 + 기호는 음절 앞으로 옮긴다(앞에 음절이 없으면 점선 원을 넣는다). `kern` 표는 OpenType(판 0)과 Apple(1.0)의 짝 하위 표 + (형식 0)와 등급 하위 표(형식 2, 3)를 부호를 건너뛰며 적용하고 커닝을 두 글리프에 나눠 준다(HarfBuzz의 이진 탐색을 그대로 + 해서, 정렬이 어긋난 표도 같은 답을 낸다). 형식 2는 HarfBuzz처럼 등급 표의 글리프를 다이제스트로 걸러, 다이제스트가 잘못 + 통과시킨 글리프는 등급 0으로 읽는다. 읽는 곳은 하위 표 안이어야 하고, 마지막 하위 표만 표 끝까지 읽는다. GPOS가 없는 글꼴은 부호를 결합 등급(태국·라오·히브리·아랍·티베트는 HarfBuzz처럼 다시 분류한 등급)과 외곽 상자로 기저의 위·아래·양옆에 쌓는다. 합자 위의 부호는 제 성분의 몫에 놓는다. 표는 제자리에서 읽고, 읽을 때마다 표의 끝을 넘는지 확인한다. 망가진 표는 틀리게 셰이핑할 뿐 밖을 읽지 않는다. @@ -231,7 +232,7 @@ U+180B–180E만 넣고 네 번째 자유 이체 선택자(U+180F)를 빠뜨렸� 받지 않는 것(빌드 도구가 이유를 말하고 거부한다): -- `kern` 표의 상태 기계(Apple 형식 1), 등급 형식(2, 3), 교차 방향 커닝. 설치된 글꼴의 `kern` 표는 모두 짝 형식(0)이다. +- `kern` 표의 상태 기계(Apple 형식 1), 교차 방향 커닝. - AAT 표(morx, kerx, trak). - 미얀마 Zawgyi(표준이 아닌 인코딩, 문자 체계 태그 Qaag로만 오는 것). @@ -251,6 +252,12 @@ U+180B–180E만 넣고 네 번째 자유 이체 선택자(U+180F)를 빠뜨렸� 아랍 대체 셰이핑, `kern` 형식 2, Zawgyi)과 계획이 없는 실행 하나다. 무작위 실행에도 글꼴이 가진 순서와 아무 선택자를 섞는다. Noto Sans CJK의 한자 이체 순서(14,787개)를 섞은 3만 실행이 HarfBuzz와 같다. +`kern` 형식 2를 받자 5,017건이 같다. 형식 3은 시험 모음에도 설치된 글꼴에도 없다. 그래서 +[text/test-kern.py](../../text/test-kern.py)가 글꼴을 만든다. DejaVu Sans에서 GPOS를 빼고, 형식 3과 형식 2 하위 표를 +여러 순서로 넣는다. 등급 값 1, 표 밖 글리프, 배열보다 앞이거나 홀수인 오프셋, 하위 표와 표 끝을 넘는 값, 개수를 넘는 등급과 +색인을 담는다. 글꼴 24개, 계획 96개의 무작위 실행이 HarfBuzz와 같다. 처음에는 형식 2가 달랐다. HarfBuzz가 등급 표 밖의 +글리프를 다이제스트로 거르므로, 거짓 양성이 된 공백이 등급 0으로 커닝되었다. + ## 비례폭 글줄 [text/layout.c](../../text/layout.c)는 검증한 부품을 UAX #9 3.4절과 UAX #14가 말하는 순서로 잇는다. diff --git a/text/harfbuzz-suite.known b/text/harfbuzz-suite.known index 4b93ab4..76a5be4 100644 --- a/text/harfbuzz-suite.known +++ b/text/harfbuzz-suite.known @@ -13,9 +13,6 @@ in-house/arabic-fallback-shaping.tests:4 in-house/arabic-fallback-shaping.tests:5 in-house/arabic-fallback-shaping.tests:6 -# A kern table of class pairs (format 2; refused). -in-house/kern-format2.tests:* - # Myanmar as Zawgyi encodes it (Qaag; refused). in-house/myanmar-zawgyi.tests:* diff --git a/text/shape-build.c b/text/shape-build.c index 98a12b0..1fe1c67 100644 --- a/text/shape-build.c +++ b/text/shape-build.c @@ -375,7 +375,10 @@ static Stage stage_of(const Map *m, const char *tag) { /* What HarfBuzz makes of the font's kern table (hb-ot-kern-table.hh): one * with subtables that pass its checks (data), Apple's state machines among * them (machine), cross-stream kerning (cross); and whether it has what - * Vega does not apply (other: a format but pairs, a version but 0 and 1). */ + * Vega does not apply (other: a state machine, a version but 0 and 1). + * Its checks: each subtable within the table, and what a format reads + * within the subtable (the last one: within the table, as HarfBuzz lets a + * last subtable run past a length whose 16 bits overflowed). */ typedef struct { bool data, machine, cross, other; } Kerning; static Kerning kerning_of(hb_face_t *face) { @@ -402,8 +405,27 @@ static Kerning kerning_of(hb_face_t *face) { valid = size >= header && at + size <= length; uint64_t end = i + 1 < count ? at + size : length; if (valid && format == 0) valid = at + header + 8 + 6 * (uint64_t)U16(at + header) <= end; + if (valid && format == 2) { + /* the row width, the offsets of the left and right class + * tables and of the kerning array; each class table a first + * glyph, a count and that many values */ + valid = at + header + 8 <= end; + for (int side = 0; valid && side < 2; ++side) { + uint64_t table = at + U16(at + header + 2 + 2 * side); + valid = table + 4 <= end && table + 4 + 2 * (uint64_t)U16(table + 2) <= end; + } + valid = valid && at + U16(at + header + 6) <= end; + } + if (valid && format == 3) { + /* glyph count, value count, left and right class counts, flags; + * the values, the classes, the index */ + valid = at + header + 6 <= end; + if (valid) + valid = at + header + 6 + 2 * (uint64_t)p[at + header + 2] + 2 * (uint64_t)U16(at + header) + + (uint64_t)p[at + header + 3] * p[at + header + 4] <= end; + } k.machine |= format == 1; - k.other |= format != 0; + k.other |= format == 1; k.cross |= apple ? coverage & 0x40 : coverage & 4; at += size; } @@ -610,7 +632,7 @@ static bool plan_for(hb_face_t *face, uint32_t script_tag, int direction, Plan * bool apply_gpos = !disable_gpos && hb_ot_layout_has_positioning(face); bool apply_kern = (!has_gpos_kern || !apply_gpos) && kern_table.data; if (apply_kern && (kern_table.other || kern_table.cross)) - FAIL("%s: the font's kern table has more than pairs (state machines, classes, cross-stream kerning)", name); + FAIL("%s: the font's kern table has a state machine or cross-stream kerning", name); /* Hangul's, Indic's and Khmer's shapers zero no marks (Myanmar's does, * before GPOS); none of these places marks without GPOS. */ bool zeroes = shaper != VEGA_SHAPER_HANGUL && shaper != VEGA_SHAPER_INDIC && shaper != VEGA_SHAPER_KHMER; diff --git a/text/shape.c b/text/shape.c index 2c8d2a6..8db4a7a 100644 --- a/text/shape.c +++ b/text/shape.c @@ -172,6 +172,8 @@ static bool resolve_lookups(VegaShaping *s, VegaTable t, int table, VegaLookup * return true; } +static bool kern_sets(VegaShaping *s); + 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) @@ -215,6 +217,7 @@ bool vega_shaping_open(VegaShaping *s, const unsigned char *bytes, size_t size, uint32_t kern = le32(bytes + 64), kern_size = le32(bytes + 68), extents = le32(bytes + 72); if (!within(size, kern, kern_size)) REFUSE("kern table"); s->kern = (VegaTable){kern_size ? bytes + kern : NULL, kern_size}; + if (kern_size && !kern_sets(s)) REFUSE("out of memory"); if (extents && !within(size, extents, 8 * (uint64_t)s->glyph_count)) REFUSE("extents"); s->extents = extents ? bytes + extents : NULL; s->plan_count = le32(bytes + 48); @@ -278,6 +281,8 @@ bool vega_shaping_open(VegaShaping *s, const unsigned char *bytes, size_t size, void vega_shaping_close(VegaShaping *s) { for (int i = 0; i < 256; ++i) free(s->bmp[i]), s->bmp[i] = NULL; + free(s->kern_sets); + s->kern_sets = NULL; free(s->lookups[0]); free(s->lookups[1]); free(s->fallback_lookups); @@ -2259,11 +2264,12 @@ static void apply_table(const VegaShaping *s, const Plan *plan, VegaShaper *b, i } } -/* ---- The kern table (hb-ot-kern-table.hh, hb-kern.hh): OpenType's (version - * 0) and Apple's (1.0), their pair subtables (format 0), each a pass over - * the glyphs with marks skipped, the kerning split between the pair. (The - * build tool refuses the other formats, and cross-stream kerning, which no - * font installed here has.) */ +/* ---- The kern table (hb-ot-kern-table.hh, hb-aat-layout-kerx-table.hh, + * hb-kern.hh): OpenType's (version 0) and Apple's (1.0), their subtables of + * pairs (format 0) and of classes (2 and 3), each a pass over the glyphs + * with marks skipped, the kerning split between the pair. (The build tool + * refuses state machines, format 1, and cross-stream kerning; HarfBuzz + * passes over other formats, and so does this.) */ static uint32_t get8(VegaTable t, uint32_t at) { return at < t.size ? t.p[at] : 0; } @@ -2281,19 +2287,93 @@ static int32_t kern_pair(VegaTable t, uint32_t pairs, uint32_t left, uint32_t ri return 0; } +/* A glyph's value in a format 2 class table (a first glyph, a count, the + * values: offsets into the kerning array); 0 outside it. */ +static uint32_t kern_class(VegaTable t, uint32_t table, uint32_t glyph) { + uint32_t i = glyph - get16(t, table); + return i < get16(t, table + 2) ? get16(t, table + 4 + 2 * i) : 0; +} + +/* What subtable st (of format 0, 2 or 3; its header header bytes) gives + * left then right; what it reads must lie before end (the subtable's end, + * or the table's for the last one). */ +static int32_t kerning(VegaTable t, unsigned format, uint32_t st, uint32_t header, uint32_t end, const VegaDigest *sets, + uint32_t left, uint32_t right) { + if (format == 0) return kern_pair(t, st + header, left, right); + if (format == 2) { + /* only glyphs the tables' digests may have (a digest's false + * positive takes class 0, as in HarfBuzz) */ + if (!digest_may_have(&sets[0], left) || !digest_may_have(&sets[1], right)) return 0; + uint32_t array = get16(t, st + header + 6), l = kern_class(t, st + get16(t, st + header + 2), left), + r = kern_class(t, st + get16(t, st + header + 4), right); + if (l + r < array) return 0; + uint64_t v = st + (uint64_t)array + ((l + r - array) & ~1u); + return v + 2 <= end ? gets16(t, (uint32_t)v) : 0; + } + /* format 3: glyph count, value count, left and right class counts, + * flags; the values; the left and right classes; the index */ + uint32_t glyphs = get16(t, st + header), values = get8(t, st + header + 2), lefts = get8(t, st + header + 3), + rights = get8(t, st + header + 4), value_at = st + header + 6, class_at = value_at + 2 * values; + uint32_t l = left < glyphs ? get8(t, class_at + left) : 0, r = right < glyphs ? get8(t, class_at + glyphs + right) : 0; + if (l >= lefts || r >= rights) return 0; + uint32_t index = get8(t, class_at + 2 * glyphs + l * rights + r); + return index < values ? gets16(t, value_at + 2 * index) : 0; +} + +/* Walk the kern table's subtables: each one's start, header size, where + * its reading ends, format and coverage; false when it has no more. */ +typedef struct { uint32_t at, count, k; bool apple; } KernWalk; +static bool kern_walk(VegaTable t, KernWalk *w, uint32_t *st, uint32_t *header, uint32_t *end, unsigned *format, + unsigned *coverage) { + if (w->k >= w->count || w->at >= t.size) return false; + uint32_t length = w->apple ? get32(t, w->at) : get16(t, w->at + 2); + *format = get8(t, w->at + (w->apple ? 5 : 4)); + *coverage = get8(t, w->at + (w->apple ? 4 : 5)); + *st = w->at; + *header = w->apple ? 8 : 6; + *end = w->k + 1 < w->count && length < t.size - w->at ? w->at + length : t.size; + w->at += length ? length : t.size; + w->k++; + return true; +} +static KernWalk kern_start(VegaTable t) { + bool apple = get16(t, 0) == 1; + return (KernWalk){apple ? 8 : 4, apple ? get32(t, 4) : get16(t, 2), 0, apple}; +} + +/* The digests of each format 2 subtable's class tables' glyphs (those not + * valued 1), as HarfBuzz's kern accelerator makes them. */ +static bool kern_sets(VegaShaping *s) { + VegaTable t = s->kern; + if (get16(t, 0) > 1) return true; + KernWalk w = kern_start(t); + s->kern_subtables = 0; + if (!(s->kern_sets = calloc(2 * (size_t)(w.count ? w.count : 1), sizeof(VegaDigest)))) return false; + uint32_t st, header, end; + unsigned format, coverage; + while (kern_walk(t, &w, &st, &header, &end, &format, &coverage)) { + VegaDigest *sets = &s->kern_sets[2 * s->kern_subtables++]; + if (format != 2) continue; + for (int side = 0; side < 2; ++side) { + uint32_t table = st + get16(t, st + header + 2 + 2 * (uint32_t)side), first = get16(t, table); + for (uint32_t i = 0, n = get16(t, table + 2); i < n; ++i) + if (get16(t, table + 4 + 2 * i) != 1) digest_add_range(&sets[side], first + i, first + i); + } + } + return true; +} + static void kern_table(const VegaShaping *s, VegaShaper *b, const Plan *plan) { VegaTable t = s->kern; - uint32_t major = get16(t, 0); - if (major > 1 || !plan->kern_mask) return; - bool apple = major == 1; - uint32_t count = apple ? get32(t, 4) : get16(t, 2), at = apple ? 8 : 4; - for (uint32_t k = 0; k < count && at < t.size; ++k) { - uint32_t length = apple ? get32(t, at) : get16(t, at + 2); - unsigned format = get8(t, at + (apple ? 5 : 4)), coverage = get8(t, at + (apple ? 4 : 5)); + if (get16(t, 0) > 1 || !plan->kern_mask) return; + KernWalk w = kern_start(t); + bool apple = w.apple; + uint32_t st, header, end; + unsigned format, coverage; + while (kern_walk(t, &w, &st, &header, &end, &format, &coverage)) { + const VegaDigest *sets = &s->kern_sets[2 * (w.k - 1)]; bool horizontal = apple ? !(coverage & 0x80) : coverage & 1; - uint32_t pairs = at + (apple ? 8 : 6); - at += length ? length : t.size; - if ((apple && (coverage & 0x20)) || !horizontal || format != 0) continue; + if ((apple && (coverage & 0x20)) || !horizontal || (format != 0 && format != 2 && format != 3)) continue; bool reverse = b->direction == VEGA_SHAPE_RTL; if (reverse) reverse_range(b, 0, b->len, true); Apply c = {.s = s, .b = b, .table = 1, .t = s->gpos, .lookup_mask = plan->kern_mask, .lookup_props = 0x08, @@ -2311,7 +2391,7 @@ static void kern_table(const VegaShaping *s, VegaShaper *b, const Plan *plan) { continue; } size_t i = idx, j = it.idx; - int32_t kern = kern_pair(t, pairs, b->info[i].codepoint, b->info[j].codepoint); + int32_t kern = kerning(t, format, st, header, end, sets, b->info[i].codepoint, b->info[j].codepoint); if (kern) { int32_t first = kern >> 1, second = kern - first; b->pos[i].x_advance += first; diff --git a/text/shape.h b/text/shape.h index 690430c..e02f0e4 100644 --- a/text/shape.h +++ b/text/shape.h @@ -121,6 +121,8 @@ typedef struct { const unsigned char *sequences; /* variation sequences */ uint32_t sequence_count; VegaTable gdef, gsub, gpos, kern; + VegaDigest *kern_sets; /* each kern subtable's left and right glyphs (format 2's), as HarfBuzz digests them */ + uint32_t kern_subtables; VegaTable fallback; /* Arabic fallback shaping's lookups, a GSUB table */ uint32_t fallback_count; uint8_t fallback_features[7]; /* what each is for: init, medi, fina, isol, rlig x3 (0..6) */ diff --git a/text/test-kern.py b/text/test-kern.py new file mode 100644 index 0000000..2d423f2 --- /dev/null +++ b/text/test-kern.py @@ -0,0 +1,99 @@ +#!/usr/bin/env python3 +"""The kern table's class subtables against HarfBuzz, where no font here has +them: + + python3 text/test-kern.py VEGA_SYMBOLS [FONT.ttf] + +Fonts made from DejaVu Sans without its GPOS, their kern table a format 3 +subtable and a format 2 one in every order (and two of either), with what +HarfBuzz's reading of them turns on: class value 1 (out of bounds), +glyphs outside a class table (a digest's false positive takes class 0), +offsets below the kerning array, odd ones, values past the subtable's end +(the last subtable may read on to the table's) and past the table's, class +and index values past their counts. Each is built with vega-symbols, which +refuses a font whose shaping differs from HarfBuzz's on random runs. +Needs fontTools; prints one JSON line, exits 1 on a difference. +""" +import json +import random +import struct +import subprocess +import sys +import tempfile +from pathlib import Path + +from fontTools.ttLib import TTFont, newTable + + +def subtable(format, body): + return struct.pack('>HHBB', 0, 6 + len(body), format, 1) + body # horizontal + + +def format3(rng, glyphs): + lefts, rights, values = 7, 9, 40 + body = struct.pack('>HBBBB', glyphs, values, lefts, rights, 0) + body += b''.join(struct.pack('>h', rng.randrange(-150, 150)) for _ in range(values)) + body += bytes(rng.randrange(lefts + 1) for _ in range(glyphs)) # some past the count + body += bytes(rng.randrange(rights + 1) for _ in range(glyphs)) + body += bytes(rng.randrange(values + 3) for _ in range(lefts * rights)) + return subtable(3, body) + + +def format2(rng, latin): + rows, columns = 6, 8 + width = 2 * columns + first_left, first_right, left_count, right_count = latin[5], latin[3], 60, 70 + left_at = 6 + 8 + right_at = left_at + 4 + 2 * left_count + array = right_at + 4 + 2 * right_count + + def left(): + k = rng.randrange(20) + return (1 if k == 0 else rng.randrange(array) if k == 1 else array + rows * width + 64 if k == 2 else + array + rng.randrange(rows) * width + (k == 3)) + + def right(): + k = rng.randrange(20) + return 1 if k == 0 else 60000 if k == 1 else 2 * rng.randrange(columns) + + body = struct.pack('>HHHH', width, left_at, right_at, array) + body += struct.pack('>HH', first_left, left_count) + b''.join(struct.pack('>H', left()) for _ in range(left_count)) + body += struct.pack('>HH', first_right, right_count) + b''.join(struct.pack('>H', right()) for _ in range(right_count)) + body += b''.join(struct.pack('>h', rng.randrange(-120, 120)) for _ in range(rows * columns)) + return subtable(2, body) + + +def main(): + tool = sys.argv[1] + source = sys.argv[2] if len(sys.argv) > 2 else '/usr/share/fonts/truetype/dejavu/DejaVuSans.ttf' + fonts = plans = differing = 0 + with tempfile.TemporaryDirectory(prefix='vega-kern-') as directory: + work = Path(directory) + for seed in range(1, 5): + for order in ('32', '23', '3', '2', '22', '33'): + rng = random.Random(seed * 100 + len(order)) + font = TTFont(source) + del font['GPOS'] + glyphs = len(font.getGlyphOrder()) + cmap = font.getBestCmap() + latin = sorted({font.getGlyphID(cmap[c]) for c in range(0x20, 0x7F) if c in cmap}) + tables = [format3(rng, glyphs) if c == '3' else format2(rng, latin) for c in order] + font['kern'] = newTable('kern') + font['kern'].decompile(struct.pack('>HH', 0, len(tables)) + b''.join(tables), font) + path = work / f'kern-{seed}-{order}.ttf' + font.save(path) + built = subprocess.run([tool, 'build', '--font', str(path), '--codes', '0x20-0x7e', '--shape', + 'Latn,Zyyy', '--runs', '3000', '-o', str(work / 'kern.vsym')], + capture_output=True, text=True) + results = [json.loads(line) for line in built.stdout.splitlines() if line.startswith('{"script"')] + fonts += 1 + plans += len(results) + if built.returncode or not results or any(r['differences'] for r in results): + differing += 1 + print(f'seed {seed}, subtables {order}:\n{built.stderr[-2000:]}', file=sys.stderr) + print(json.dumps({'fonts': fonts, 'plans': plans, 'differing_fonts': differing})) + return 1 if differing else 0 + + +if __name__ == '__main__': + sys.exit(main()) |