Map characters as HarfBuzz maps them, not as it lists them

The shaping section's character map came from hb_face_collect_unicodes.
HarfBuzz's own suite showed where that list and its mapping part: it cuts
a format 13 map short (AdobeBlank2's whole Unicode to one glyph), and a
symbol map (3,0) it searches through the private use area, Latin and, in an
old Arabic font, Arabic too. Now every code point is asked with
hb_font_get_nominal_glyph (about 30 ms a font) and the map carried as
groups: codes going to consecutive glyphs, or all to one (12 bytes each,
so a format 13 map stays small).

HarfBuzz's suite: 5011 of 5199 cases the same (1355 before). The installed
fonts (213) and the Noto ones (21) still shape as HarfBuzz does on random
runs.

6 files changed, 91 insertions, 48 deletions

diff --git a/docs/design/004-text.md b/docs/design/004-text.md
index 4e8e7fb..9e6f968 100644
--- a/docs/design/004-text.md
+++ b/docs/design/004-text.md
@@ -87,8 +87,10 @@ Sentence_Break, 동아시아 폭이 F·W·H인 여는·닫는 괄호)와 규칙�
   히브리, 한글 셰이퍼의 목록과 단계), 중복을 합치고, 마스크 비트를 나누고, 글꼴의 문자 체계·언어 체계에서 기능을 찾고,
   단계별로 조회를 모아 정렬해 합친다. 누가 자리를 잡는지도 여기서 정한다. GPOS, 옛 `kern` 표(GPOS에 `kern` 기능이 없을 때),
   부호의 대체 배치(GPOS가 없을 때) 가운데 무엇을 쓸지, 부호의 폭을 0으로 만들며 오프셋을 옮길지를 HarfBuzz의 조건 그대로
-  고른다. 결과는 조회 번호, 마스크, ZWJ/ZWNJ 규칙, 이 깃발들의 목록이다. 글꼴의 문자 지도와 advance, GDEF·GSUB·GPOS와 `kern`
-  표는 그대로 싣고, 대체 배치를 하는 계획이 있으면 글리프마다 외곽 상자(HarfBuzz의 glyph extents, 16비트 넷)를 싣는다
+  고른다. 결과는 조회 번호, 마스크, ZWJ/ZWNJ 규칙, 이 깃발들의 목록이다. 문자 지도는 HarfBuzz가 매기는 대로 싣는다. 모든
+  코드 포인트를 `hb_font_get_nominal_glyph`로 물어, 이어지는 글리프로 가거나 한 글리프로 가는 묶음으로 적는다. 목록
+  (`hb_face_collect_unicodes`)으로 만들면 틀린다. 형식 13 지도는 목록이 잘리고, 기호 지도(3,0)의 라틴과 아랍 문자는 HarfBuzz가
+  사용자 영역으로 옮겨 찾는다. advance, GDEF·GSUB·GPOS와 `kern` 표는 그대로 싣고, 대체 배치를 하는 계획이 있으면 글리프마다 외곽 상자(HarfBuzz의 glyph extents, 16비트 넷)를 싣는다
   ([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, 히브리
@@ -232,6 +234,21 @@ U+180B–180E만 넣고 네 번째 자유 이체 선택자(U+180F)를 빠뜨렸�
 - 미얀마 Zawgyi(표준이 아닌 인코딩, 문자 체계 태그 Qaag로만 오는 것).
 - 이체 선택자(cmap 형식 14)는 싣지 않는다. 선택자는 숨기고 앞 글자는 기본 글리프로 둔다.
 
+### HarfBuzz의 시험 모음
+
+무작위 실행은 흔한 경우를 덮지만, 글꼴 하나가 드러낸 버릇은 그 글꼴과 그 입력이 있어야 보인다. HarfBuzz의 시험 모음
+(`test/shape/data`: in-house, text-rendering-tests, aots)이 그 목록이다. 버릇이 드러날 때마다 글꼴과 입력을 더해 온 것이다.
+[text/harfbuzz-suite.py](../../text/harfbuzz-suite.py)는 그 모든 경우를 `vega-symbols shape-cases`로 양쪽에서 셰이핑한다.
+경우들이 쓰는 문자 체계로 글꼴의 구역을 컴파일하고(문자 체계와 방향은 HarfBuzz가 추측하는 대로), 실행마다 HarfBuzz와 글리프·
+위치를 댄다. 기대 출력 대신 HarfBuzz를 그 자리에서 돌린다. 기록된 출력은 Vega에 없는 선택(글꼴 함수, 크기, 출력 형식)에
+딸려 있기 때문이다. Vega가 하지 않는 것을 묻는 경우(사용자 기능, 가변 글꼴, 언어, 앞뒤 문맥, 클러스터 수준, 버퍼 깃발, 세로쓰기)와
+다른 시스템의 글꼴은 이유별로 세고 뺀다. [text/harfbuzz-suite.known](../../text/harfbuzz-suite.known)에 적힌 것 밖의 차이는
+실패다. 적힌 것이 맞게 되면 알린다(`make check-harfbuzz HARFBUZZ_SRC=...`).
+
+처음 돌렸을 때 비교한 5,199건 가운데 1,355건만 같았다. 차이 대부분은 문자 지도였다(위의 형식 13과 기호 지도). 그것을 고치자
+5,011건이 같다. 남은 것은 AAT 글꼴(거부), 이체 선택자, 글리프를 나눠 쓰는 아랍 대체 셰이핑, `kern` 형식 2, Zawgyi, 계획이 없는
+실행 하나다. 설치된 글꼴 213개와 Noto 21개의 무작위 실행도 다시 돌려 차이가 없다.
+
 ## 비례폭 글줄
 
 [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 a0436bb..f6d9b6d 100644
--- a/text/harfbuzz-suite.known
+++ b/text/harfbuzz-suite.known
@@ -6,18 +6,6 @@
 text-rendering-tests/MORX-*        # AAT
 in-house/aat-*                     # AAT
 
-# The character map made from what HarfBuzz lists (hb_face_collect_unicodes),
-# not from how it maps: a format 13 map it lists cut short, a symbol map
-# whose Latin and Arabic it maps to the private use area.
-in-house/emoji-clusters.tests:*    # cmap format 13
-text-rendering-tests/CMAP-3.tests:1    # cmap
-text-rendering-tests/CMAP-3.tests:11   # cmap
-in-house/arabic-fallback-shaping.tests:7   # symbol cmap, Arabic PUA
-in-house/arabic-fallback-shaping.tests:8   # symbol cmap, Arabic PUA
-in-house/arabic-fallback-shaping.tests:9   # symbol cmap, Arabic PUA
-in-house/arabic-fallback-shaping.tests:10  # symbol cmap, Arabic PUA
-in-house/arabic-fallback-shaping.tests:11  # symbol cmap, Arabic PUA
-
 # Variation selectors (cmap format 14).
 text-rendering-tests/CMAP-1.tests:2    # cmap format 14
 text-rendering-tests/CMAP-1.tests:3    # cmap format 14
diff --git a/text/harfbuzz-suite.py b/text/harfbuzz-suite.py
index aa25195..d132070 100644
--- a/text/harfbuzz-suite.py
+++ b/text/harfbuzz-suite.py
@@ -133,8 +133,10 @@ def main():
     counts = Counter(verdict.split(' ', 1)[0] for verdict in outcome.values())
     is_known = lambda case: any(fnmatch.fnmatchcase(case, pattern) for pattern in known)
     unexpected = sorted(case for case, verdict in outcome.items() if verdict != 'same' and not is_known(case))
-    now_same = sorted(case for case, verdict in outcome.items() if verdict == 'same' and is_known(case) and
-                      case in known)
+    # a listed case, or pattern, all of whose cases now agree
+    now_same = sorted(pattern for pattern in known
+                      if any(fnmatch.fnmatchcase(case, pattern) for case in outcome) and
+                      all(verdict == 'same' for case, verdict in outcome.items() if fnmatch.fnmatchcase(case, pattern)))
     for case in unexpected[:args.show]:
         print(f'{case}: {outcome[case]}', file=sys.stderr)
         print(details.get(case, ''), end='', file=sys.stderr)
diff --git a/text/shape-build.c b/text/shape-build.c
index 7cb251d..fac333b 100644
--- a/text/shape-build.c
+++ b/text/shape-build.c
@@ -914,11 +914,40 @@ bool vega_shaping_compile(hb_face_t *face, const uint32_t *scripts, size_t scrip
         }
     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);) {
+    /* The character map as HarfBuzz maps, not as it lists (a format 13 map
+     * it lists cut short, a symbol map it maps into the private use area):
+     * every code point asked, in groups of codes going to consecutive
+     * glyphs, or all to one. */
+    uint32_t *groups = NULL, group_count = 0, allocated = 0;
+    for (hb_codepoint_t u = 0; u <= 0x10FFFF; ++u) {
         hb_codepoint_t g;
-        if (hb_font_get_nominal_glyph(font, u, &g) && g) cmap_count++;
+        if (!hb_font_get_nominal_glyph(font, u, &g) || !g) continue;
+        hb_set_add(unicodes, u);
+        if (group_count) {
+            uint32_t *last = groups + 3 * (group_count - 1), glyph = last[2] & 0x7FFFFFFF;
+            bool single = last[0] == last[1], same = last[2] >> 31;
+            if (last[1] + 1 == u && ((single || !same) && g == glyph + (u - last[0]))) {
+                last[1] = u;
+                continue;
+            }
+            if (last[1] + 1 == u && (single || same) && g == glyph) {
+                last[1] = u;
+                last[2] = glyph | 0x80000000u;
+                continue;
+            }
+        }
+        if (group_count == allocated) {
+            allocated = allocated ? 2 * allocated : 256;
+            uint32_t *grown = realloc(groups, 3 * (size_t)allocated * sizeof(*groups));
+            if (!grown) {
+                free(groups);
+                FAIL("out of memory");
+            }
+            groups = grown;
+        }
+        uint32_t *next = groups + 3 * group_count++;
+        next[0] = next[1] = u;
+        next[2] = g;
     }
     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)};
@@ -928,15 +957,10 @@ bool vega_shaping_compile(hb_face_t *face, const uint32_t *scripts, size_t scrip
     put16(&o, hb_face_get_upem(face));
     put16(&o, glyph_count);
     for (int i = 0; i < 17; ++i) put32(&o, 0);
-    set32(&o, 12, cmap_count);
+    set32(&o, 12, group_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);
-        }
-    }
+    for (uint32_t i = 0; i < 3 * group_count; ++i) put32(&o, groups[i]);
+    free(groups);
     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);
diff --git a/text/shape.c b/text/shape.c
index 0ea2968..926632d 100644
--- a/text/shape.c
+++ b/text/shape.c
@@ -180,22 +180,29 @@ bool vega_shaping_open(VegaShaping *s, const unsigned char *bytes, size_t size,
     s->size = size;
     s->upem = le16(bytes + 8);
     s->glyph_count = le16(bytes + 10);
-    s->cmap_count = le32(bytes + 12);
+    s->cmap_groups = 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");
+    if (!within(size, cmap, (uint64_t)s->cmap_groups * 12)) 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);
+    for (uint32_t i = 0; i < s->cmap_groups; ++i) {
+        const unsigned char *g = s->cmap + 12 * (size_t)i;
+        uint32_t first = le32(g), last = le32(g + 4), glyph = le32(g + 8) & 0x7FFFFFFF;
+        bool same = le32(g + 8) >> 31;
+        if ((i && first <= le32(g - 8)) || last < first || last > 0x10FFFF || !glyph ||
+            (uint64_t)glyph + (same ? 0 : last - first) >= s->glyph_count)
+            REFUSE("character map: group %u", i);
+    }
+    for (uint32_t i = 0; i < s->cmap_groups; ++i) {
+        const unsigned char *g = s->cmap + 12 * (size_t)i;
+        uint32_t first = le32(g), last = le32(g + 4), glyph = le32(g + 8) & 0x7FFFFFFF;
+        bool same = le32(g + 8) >> 31;
+        if (first > 0xFFFF) break;
+        for (uint32_t code = first; code <= last && code <= 0xFFFF; ++code) {
+            uint16_t **page = &s->bmp[code >> 8];
+            if (!*page && !(*page = calloc(256, sizeof(**page)))) REFUSE("out of memory");
+            (*page)[code & 255] = (uint16_t)(same ? glyph : glyph + (code - first));
+        }
     }
     if (!within(size, advances, 2 * (uint64_t)s->glyph_count)) REFUSE("advances");
     s->advances = bytes + advances;
@@ -272,12 +279,13 @@ void vega_shaping_close(VegaShaping *s) {
 
 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;
+    uint32_t low = 0, high = s->cmap_groups;
     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);
+        uint32_t middle = (low + high) / 2;
+        const unsigned char *g = s->cmap + 12 * (size_t)middle;
+        if (le32(g + 4) < code) low = middle + 1;
+        else if (le32(g) > code) high = middle;
+        else return le32(g + 8) >> 31 ? le32(g + 8) & 0x7FFFFFFF : le32(g + 8) + (code - le32(g));
     }
     return 0;
 }
diff --git a/text/shape.h b/text/shape.h
index cafa9b4..3fe3ff8 100644
--- a/text/shape.h
+++ b/text/shape.h
@@ -21,7 +21,11 @@
  *
  * 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 cmap_groups, u32 cmap_offset      (u32 first, u32 last code, u32
+ *                                          glyph: first's, the next codes'
+ *                                          following it, or with the top bit
+ *                                          set, the glyph of them all; by
+ *                                          code, apart),
  *   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),
@@ -109,7 +113,7 @@ typedef struct {
     const unsigned char *bytes;
     size_t size;
     uint16_t upem, glyph_count;
-    uint32_t cmap_count, plan_count;
+    uint32_t cmap_groups, plan_count;
     const unsigned char *cmap, *advances, *plans, *steps, *extents;
     VegaTable gdef, gsub, gpos, kern;
     VegaTable fallback;             /* Arabic fallback shaping's lookups, a GSUB table */