diff options
| -rw-r--r-- | text/shape-build.c | 70 |
1 files changed, 64 insertions, 6 deletions
diff --git a/text/shape-build.c b/text/shape-build.c index 3910c5d..aa653d8 100644 --- a/text/shape-build.c +++ b/text/shape-build.c @@ -120,6 +120,69 @@ static bool add_lookups(Map *m, int table, unsigned feature_index, uint32_t mask return true; } +/* hb_qsort as HarfBuzz builds it (hb-algs.hh's sort_r_simple, Isaac + * Turner's quicksort), by lookup index: which of two entries of one lookup + * comes first decides whose per-syllable and random flags the merge keeps, + * so the order must be its own, unstable as it is. */ +static void swap_lookups(LookupMap *a, LookupMap *b) { + LookupMap t = *a; + *a = *b; + *b = t; +} +static int cmp_lookups(const LookupMap *a, const LookupMap *b) { return (a->index > b->index) - (a->index < b->index); } +static void swap_blocks(LookupMap *p, size_t na, size_t nb) { + if (!na || !nb) return; + if (na > nb) + for (size_t i = 0; i < nb; ++i) swap_lookups(&p[i], &p[na + i]); + else + for (size_t i = 0; i < na; ++i) swap_lookups(&p[i], &p[nb + i]); +} +static void sort_lookups(LookupMap *b, size_t nel) { + if (nel < 10) { + for (size_t i = 1; i < nel; ++i) + for (size_t j = i; j > 0 && cmp_lookups(&b[j - 1], &b[j]) > 0; --j) swap_lookups(&b[j - 1], &b[j]); + return; + } + LookupMap *end = b + nel, *last = b + nel - 1, *t; + /* the median of the second, middle and second-last is the pivot, moved last */ + LookupMap *l[3] = {b + 1, b + nel / 2, last - 1}; + if (cmp_lookups(l[0], l[1]) > 0) t = l[0], l[0] = l[1], l[1] = t; + if (cmp_lookups(l[1], l[2]) > 0) { + t = l[1], l[1] = l[2], l[2] = t; + if (cmp_lookups(l[0], l[1]) > 0) t = l[0], l[0] = l[1], l[1] = t; + } + if (l[1] != last) swap_lookups(l[1], last); + LookupMap *pivot = last, *pl = b, *ple = b, *pr = last, *pre = last; + while (pl < pr) { + for (; pl < pr; pl++) { + int c = cmp_lookups(pl, pivot); + if (c > 0) break; + if (c == 0) { + if (ple < pl) swap_lookups(ple, pl); + ple++; + } + } + if (pl >= pr) break; + while (pl < pr) { + pr--; + int c = cmp_lookups(pr, pivot); + if (c == 0) { + pre--; + if (pr < pre) swap_lookups(pr, pre); + } else if (c < 0) { + if (pl < pr) swap_lookups(pl, pr); + pl++; + break; + } + } + } + pl = pr; + swap_blocks(b, (size_t)(ple - b), (size_t)(pl - ple)); + swap_blocks(pr, (size_t)(pre - pr), (size_t)(end - pre)); + sort_lookups(b, (size_t)(pl - ple)); + sort_lookups(end - (pre - pr), (size_t)(pre - pr)); +} + static bool compile_map(Map *m) { unsigned required_index[2], required_stage[2] = {0, 0}; hb_tag_t required_tag[2]; @@ -210,12 +273,7 @@ static bool compile_map(Map *m) { 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; - } + sort_lookups(l + last, n - last); unsigned j = last; for (unsigned i = j + 1; i < n; ++i) if (l[i].index != l[j].index) l[++j] = l[i]; |