diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/symbols-tool.c | 305 | ||||
| -rw-r--r-- | src/symbols.c | 83 | ||||
| -rw-r--r-- | src/symbols.h | 38 |
3 files changed, 309 insertions, 117 deletions
diff --git a/src/symbols-tool.c b/src/symbols-tool.c index bec8656..e957c9e 100644 --- a/src/symbols-tool.c +++ b/src/symbols-tool.c @@ -18,81 +18,129 @@ #define PI 3.14159265358979323846 typedef struct { double x, y; } Point; -typedef struct { Point p[3]; } Quad; -typedef struct { Quad *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; +/* An outline as the pen drew it. smooth: the end lies halfway between this + * control and the next, by construction, so it may go unwritten. */ +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) */ static void fail(const char *why) { fprintf(stderr, "vega-symbols: %s\n", why); exit(1); } -static void add_quad(Path *path, Point a, Point b, Point c) { +static void add(Path *path, Segment segment) { if (path->count == path->capacity) { path->capacity = path->capacity ? 2 * path->capacity : 64; if (!(path->items = realloc(path->items, path->capacity * sizeof(*path->items)))) fail("out of memory"); } - path->items[path->count++] = (Quad){{a, b, c}}; + path->items[path->count++] = segment; + path->at = segment.end; } -/* A line is a quadratic whose control point is its middle. */ +static bool same(Point a, Point b) { return a.x == b.x && a.y == b.y; } + static void line_to(Path *path, Point to) { - if (to.x != path->at.x || to.y != path->at.y) - add_quad(path, path->at, (Point){(path->at.x + to.x) / 2, (path->at.y + to.y) / 2}, to); - path->at = to; + if (!same(to, path->at)) add(path, (Segment){LINE, false, to, to}); } -static void quad_to(Path *path, Point control, Point to) { - add_quad(path, path->at, control, to); - path->at = to; +static void quad_to(Path *path, Point control, Point to) { add(path, (Segment){QUAD, false, control, to}); } + +static Point lerp(Point a, Point b, double t) { return (Point){a.x + (b.x - a.x) * t, a.y + (b.y - a.y) * t}; } +static double length(double x, double y) { return sqrt(x * x + y * y); } + +/* Whether the cubic of these differences stays within tolerance of zero + * (split in halves until its control points do). */ +static bool fits(Point p0, Point p1, Point p2, Point p3, double tolerance) { + if (length(p1.x, p1.y) <= tolerance && length(p2.x, p2.y) <= tolerance) return true; + Point mid = {(p0.x + 3 * (p1.x + p2.x) + p3.x) / 8, (p0.y + 3 * (p1.y + p2.y) + p3.y) / 8}; + if (length(mid.x, mid.y) > tolerance) return false; + Point d = {(p3.x + p2.x - p1.x - p0.x) / 8, (p3.y + p2.y - p1.y - p0.y) / 8}; + return fits(p0, lerp(p0, p1, 0.5), (Point){mid.x - d.x, mid.y - d.y}, mid, tolerance) && + fits(mid, (Point){mid.x + d.x, mid.y + d.y}, lerp(p2, p3, 0.5), p3, tolerance); } -/* A cubic as quadratics, within half a unit: split in n equal pieces, each - * approximated by the quadratic through its ends with the control point - * (3(c1 + c2) - (p0 + p3)) / 4. The error shrinks with the cube of n. */ -static void cubic_to(Path *path, Point c1, Point c2, Point to) { - Point p0 = path->at; - double dx = to.x - 3 * c2.x + 3 * c1.x - p0.x, dy = to.y - 3 * c2.y + 3 * c1.y - p0.y; - double error = sqrt(3) / 36 * sqrt(dx * dx + dy * dy); - int n = (int)ceil(cbrt(error / 0.5)); - if (n < 1) n = 1; - if (n > 64) n = 64; +/* The piece of cubic c over [a, b], as a cubic. */ +static void piece(const Point c[4], double a, double b, Point out[4]) { + Point q[4]; + for (int k = 0; k < 2; ++k) { + double t = k ? b : a, u = 1 - t; + Point e = {u * u * u * c[0].x + 3 * u * u * t * c[1].x + 3 * u * t * t * c[2].x + t * t * t * c[3].x, + u * u * u * c[0].y + 3 * u * u * t * c[1].y + 3 * u * t * t * c[2].y + t * t * t * c[3].y}; + Point d = {3 * (u * u * (c[1].x - c[0].x) + 2 * u * t * (c[2].x - c[1].x) + t * t * (c[3].x - c[2].x)), + 3 * (u * u * (c[1].y - c[0].y) + 2 * u * t * (c[2].y - c[1].y) + t * t * (c[3].y - c[2].y))}; + double h = (b - a) / 3 * (k ? -1 : 1); + q[3 * k] = e; + q[1 + k] = (Point){e.x + d.x * h, e.y + d.y * h}; + } + memcpy(out, q, sizeof(q)); +} + +/* A cubic as a quadratic spline whose joins lie halfway between neighbouring + * controls (so they go unwritten), within tolerance: the approach of cu2qu + * (fontTools). With n pieces, piece i takes its control on the line between + * the points where the cubic's end tangents reach 1.5 times their control + * arms, at i / (n - 1); the fewest pieces that fit win. */ +static bool spline(const Point c[4], int n, double tolerance, Point *controls) { + if (n == 1) { + /* One quadratic: its control where the end tangents meet. */ + Point a = {c[1].x - c[0].x, c[1].y - c[0].y}, b = {c[2].x - c[3].x, c[2].y - c[3].y}; + double cross = a.x * b.y - a.y * b.x; + if (fabs(cross) < 1e-12) return false; + double t = ((c[3].x - c[0].x) * b.y - (c[3].y - c[0].y) * b.x) / cross; + controls[0] = (Point){c[0].x + a.x * t, c[0].y + a.y * t}; + Point q1 = lerp(c[0], controls[0], 2.0 / 3), q2 = lerp(c[3], controls[0], 2.0 / 3); + return fits((Point){0, 0}, (Point){q1.x - c[1].x, q1.y - c[1].y}, (Point){q2.x - c[2].x, q2.y - c[2].y}, + (Point){0, 0}, tolerance); + } + Point from = c[0], before = {0, 0}; for (int i = 0; i < n; ++i) { - double t0 = (double)i / n, t1 = (double)(i + 1) / n; - Point q[4]; - double ts[2] = {t0, t1}; - /* The piece's points by de Casteljau at t0 and t1, and its control points. */ - Point e[2]; - for (int k = 0; k < 2; ++k) { - double t = ts[k], u = 1 - t; - e[k] = (Point){u * u * u * p0.x + 3 * u * u * t * c1.x + 3 * u * t * t * c2.x + t * t * t * to.x, - u * u * u * p0.y + 3 * u * u * t * c1.y + 3 * u * t * t * c2.y + t * t * t * to.y}; - } - /* Derivatives give the piece's cubic control points. */ - double h = t1 - t0; - for (int k = 0; k < 2; ++k) { - double t = ts[k], u = 1 - t; - Point d = {3 * (u * u * (c1.x - p0.x) + 2 * u * t * (c2.x - c1.x) + t * t * (to.x - c2.x)), - 3 * (u * u * (c1.y - p0.y) + 2 * u * t * (c2.y - c1.y) + t * t * (to.y - c2.y))}; - q[k ? 2 : 1] = k ? (Point){e[1].x - d.x * h / 3, e[1].y - d.y * h / 3} : (Point){e[0].x + d.x * h / 3, e[0].y + d.y * h / 3}; - } - q[0] = e[0]; - q[3] = e[1]; - Point control = {(3 * (q[1].x + q[2].x) - (q[0].x + q[3].x)) / 4, (3 * (q[1].y + q[2].y) - (q[0].y + q[3].y)) / 4}; - path->at = q[0]; - quad_to(path, control, q[3]); + Point p[4]; + piece(c, (double)i / n, (double)(i + 1) / n, p); + Point near = lerp(p[0], p[1], 1.5), far = lerp(p[3], p[2], 1.5); + controls[i] = lerp(near, far, (double)i / (n - 1)); } - path->at = to; + for (int i = 0; i < n; ++i) { + Point p[4]; + piece(c, (double)i / n, (double)(i + 1) / n, p); + Point to = i + 1 < n ? lerp(controls[i], controls[i + 1], 0.5) : c[3]; + Point after = {to.x - p[3].x, to.y - p[3].y}; + Point q1 = lerp(from, controls[i], 2.0 / 3), q2 = lerp(to, controls[i], 2.0 / 3); + if (length(after.x, after.y) > tolerance || + !fits(before, (Point){q1.x - p[1].x, q1.y - p[1].y}, (Point){q2.x - p[2].x, q2.y - p[2].y}, after, tolerance)) + return false; + from = to; + before = after; + } + return true; +} + +static void cubic_to(Path *path, Point c1, Point c2, Point to) { + Point c[4] = {path->at, c1, c2, to}, controls[64]; + if (same(c[0], c1) && same(c1, c2) && same(c2, to)) return; + for (int n = 1; n <= 64; ++n) + if (spline(c, n, 1, controls)) { + for (int i = 0; i < n; ++i) + add(path, (Segment){QUAD, i + 1 < n, controls[i], i + 1 < n ? lerp(controls[i], controls[i + 1], 0.5) : to}); + return; + } + fail("a cubic that 64 quadratics do not fit"); } static void close_path(Path *path) { - if (path->open) line_to(path, path->start); + if (path->open) { + line_to(path, path->start); + /* A contour of a move alone draws nothing: drop it. */ + if (path->count && path->items[path->count - 1].kind == MOVE) --path->count; + } path->open = false; } static void move_to(Path *path, Point to) { close_path(path); - path->at = path->start = to; + add(path, (Segment){MOVE, false, to, to}); + path->start = to; path->open = true; } @@ -300,13 +348,54 @@ static void svg_icon(Path *path, const char *file, uint16_t units, int16_t *adva /* ---- Writing. */ +typedef struct { long x, y; bool off, move; } Emitted; +typedef struct { Emitted *items; size_t count, capacity; } Points; + static void put16(unsigned char *p, int v) { p[0] = (unsigned char)v; p[1] = (unsigned char)((unsigned)v >> 8); } static void put32(unsigned char *p, uint32_t v) { for (int i = 0; i < 4; ++i) p[i] = (unsigned char)(v >> (8 * i)); } -static int16_t unit(double v) { - long r = lround(v); - if (r < INT16_MIN || r > INT16_MAX) fail("a coordinate does not fit 16 bits"); - return (int16_t)r; +static void emit(Points *points, Point at, bool off, bool move) { + if (points->count == points->capacity) { + points->capacity = points->capacity ? 2 * points->capacity : 256; + if (!(points->items = realloc(points->items, points->capacity * sizeof(*points->items)))) fail("out of memory"); + } + points->items[points->count++] = (Emitted){lround(at.x), lround(at.y), off, move}; +} + +/* Whether s ends where its control and the next curve's would imply. */ +static bool implied(const Segment *s, const Segment *next) { + if (s->kind != QUAD || !next || next->kind != QUAD) return false; + return s->smooth || (2 * lround(s->end.x) == lround(s->control.x) + lround(next->control.x) && + 2 * lround(s->end.y) == lround(s->control.y) + lround(next->control.y)); +} + +/* One symbol's segments as points: each contour an on point that starts it, + * then per segment its control (if a curve) and its end, unless the next + * curve's control implies it; the last end, back at the start, is written. + * A contour that starts at an implied point (as FreeType starts TrueType's + * when its first point is off) starts instead at its first written one. */ +static void emit_symbol(Points *points, const Segment *segments, size_t count) { + for (size_t i = 0; i < count;) { + size_t end = i + 1; + while (end < count && segments[end].kind != MOVE) ++end; + const Segment *body = segments + i + 1; + size_t n = end - i - 1, from = 0; + if (n > 1 && implied(&body[n - 1], &body[0])) + for (size_t k = 0; k + 1 < n; ++k) + if (!implied(&body[k], &body[k + 1])) { from = k + 1; break; } + emit(points, from ? body[from - 1].end : segments[i].end, false, true); + for (size_t m = 0; m < n; ++m) { + const Segment *s = &body[(from + m) % n], *next = m + 1 < n ? &body[(from + m + 1) % n] : NULL; + const Emitted *last = &points->items[points->count - 1]; + if (s->kind == LINE) { + if (last->off || last->x != lround(s->end.x) || last->y != lround(s->end.y)) emit(points, s->end, false, false); + continue; + } + emit(points, s->control, true, false); + if (!implied(s, next)) emit(points, s->end, false, false); + } + i = end; + } } static int by_code(const void *a, const void *b) { @@ -317,53 +406,74 @@ static int by_code(const void *a, const void *b) { static void write_symbols(const char *out, uint16_t units, Built *built, size_t count, const Path *path) { 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"); - size_t size = VEGA_SYMBOLS_HEADER + count * VEGA_SYMBOL_BYTES + path->count * VEGA_CURVE_BYTES; + Points points = {0}; + size_t *first = calloc(count + 1, sizeof(*first)); + for (size_t i = 0; i < count; ++i) { + first[i] = points.count; + emit_symbol(&points, path->items + built[i].first, built[i].count); + } + first[count] = points.count; + /* Halve units while every coordinate is even: a TrueType font's own. */ + for (;;) { + bool even = units % 2 == 0 && units > 16; + for (size_t i = 0; even && i < points.count; ++i) even = points.items[i].x % 2 == 0 && points.items[i].y % 2 == 0; + for (size_t i = 0; even && i < count; ++i) even = built[i].advance % 2 == 0; + if (!even) break; + for (size_t i = 0; i < points.count; ++i) { points.items[i].x /= 2; points.items[i].y /= 2; } + for (size_t i = 0; i < count; ++i) built[i].advance = (int16_t)(built[i].advance / 2); + units /= 2; + } + size_t size = VEGA_SYMBOLS_HEADER + count * VEGA_SYMBOL_BYTES + points.count * VEGA_POINT_BYTES; unsigned char *bytes = calloc(1, size); if (!bytes) fail("out of memory"); - memcpy(bytes, "VEGASYM1", 8); + memcpy(bytes, "VEGASYM2", 8); put16(bytes + 8, units); put32(bytes + 12, (uint32_t)count); - put32(bytes + 16, (uint32_t)path->count); + put32(bytes + 16, (uint32_t)points.count); put32(bytes + 20, (uint32_t)size); - unsigned char *curves = bytes + VEGA_SYMBOLS_HEADER + count * VEGA_SYMBOL_BYTES; - uint32_t next = 0; + unsigned char *at = bytes + VEGA_SYMBOLS_HEADER + count * VEGA_SYMBOL_BYTES; + for (size_t i = 0; i < points.count; ++i) { + const Emitted *e = &points.items[i]; + if (e->x < -16384 || e->x > 16383 || e->y < -16384 || e->y > 16383) fail("a coordinate does not fit 15 bits"); + put16(at + 4 * i, (int)(2 * e->x + e->off)); + put16(at + 4 * i + 2, (int)(2 * e->y + e->move)); + } for (size_t i = 0; i < count; ++i) { - int16_t left = 0, bottom = 0, right = 0, top = 0; - for (size_t k = 0; k < built[i].count; ++k) { - const Quad *q = &path->items[built[i].first + k]; - unsigned char *c = curves + (size_t)(next + k) * VEGA_CURVE_BYTES; - for (int j = 0; j < 3; ++j) { - int16_t x = unit(q->p[j].x), y = unit(q->p[j].y); - put16(c + 4 * j, x); - put16(c + 4 * j + 2, y); - if (!k && !j) { left = right = x; bottom = top = y; } - if (x < left) left = x; - if (x > right) right = x; - if (y < bottom) bottom = y; - if (y > top) top = y; - } + long left = 0, bottom = 0, right = 0, top = 0; + for (size_t k = first[i]; k < first[i + 1]; ++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; + right = e->x > right ? e->x : right; + bottom = e->y < bottom ? e->y : bottom; + top = e->y > top ? e->y : top; } - unsigned char *s = bytes + VEGA_SYMBOLS_HEADER + i * VEGA_SYMBOL_BYTES; - put32(s, built[i].code); - put32(s + 4, next); - put32(s + 8, (uint32_t)built[i].count); - put16(s + 12, left); - put16(s + 14, bottom); - put16(s + 16, right); - put16(s + 18, top); - put16(s + 20, built[i].advance); - next += (uint32_t)built[i].count; + 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])); + put16(p + 12, (int)left); + put16(p + 14, (int)bottom); + put16(p + 16, (int)right); + put16(p + 18, (int)top); + put16(p + 20, built[i].advance); } FILE *f = fopen(out, "wb"); if (!f || fwrite(bytes, 1, size, f) != size || fclose(f)) fail("cannot write the symbol file"); - free(bytes); char error[128]; VegaSymbols check; - size_t read_size; - char *again = read_file(out, &read_size); - if (!again || !vega_symbols_open(&check, (unsigned char *)again, read_size, error, sizeof(error))) fail(error); - free(again); - printf("{\"symbols\":%zu,\"curves\":%zu,\"bytes\":%zu}\n", count, path->count, size); + if (!vega_symbols_open(&check, bytes, size, error, sizeof(error))) fail(error); + size_t curves = 0; + VegaCurve curve; + for (uint32_t i = 0; i < check.symbols; ++i) { + 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); + free(bytes); + free(first); + free(points.items); } /* 0x20-0x7e,0xac00 as a list of codes. */ @@ -432,7 +542,7 @@ static int build(int argc, char **argv) { if (FT_Outline_Decompose(&face->glyph->outline, &walk, &path)) fail("cannot walk an outline"); } close_path(&path); - long advance = lround(face->glyph->metrics.horiAdvance * path.font_scale); + long advance = lround((double)face->glyph->metrics.horiAdvance * units / face->units_per_EM); built[made++] = (Built){list[i], first, path.count - first, (int16_t)(advance > INT16_MAX ? INT16_MAX : advance)}; } for (size_t i = 0; i < icon_count; ++i) { @@ -496,12 +606,16 @@ static void measure_open(FT_Library library, const char *font, const VegaSymbols if (FT_New_Memory_Face(library, (const FT_Byte *)font_bytes, (FT_Long)font_size, 0, &face)) fail("cannot open the font"); FT_Outline_Funcs walk = {ignore_point, ignore_point, ignore_conic, ignore_cubic, 0, 0}; long touched = 0, walked = 0; + uint32_t most = 0; + for (uint32_t i = 0; i < s->symbols; ++i) most = vega_symbol_at(s, i).count > most ? vega_symbol_at(s, i).count : most; + VegaCurve *curves = malloc((most + 1) * sizeof(*curves)); started = seconds(); for (int r = 0; r < rounds; ++r) for (uint32_t i = 0; i < s->symbols; ++i) { VegaSymbol symbol; if (!vega_symbol(s, vega_symbol_at(s, i).code, &symbol)) fail("lookup"); - for (uint32_t k = symbol.first; k < symbol.first + symbol.count; ++k) touched += vega_curve(s, k).x2; + uint32_t count = vega_symbol_curves(s, &symbol, curves); + touched += count ? (long)curves[count - 1].x2 : 0; } double outline_ns = (seconds() - started) / rounds / s->symbols * 1e9; started = seconds(); @@ -516,6 +630,7 @@ static void measure_open(FT_Library library, const char *font, const VegaSymbols sink = touched + walked; FT_Done_Face(face); free(font_bytes); + free(curves); } /* Every symbol with a glyph in the font, at each size: our coverage against @@ -572,7 +687,7 @@ static int compare(int argc, char **argv) { return 0; } -/* Each symbol's code, curves, bounds, advance and filled area (in square +/* Each symbol's code, points, curves, bounds, advance and filled area (in square * units: the integral of x dy around its outline, as a check against other * readers of the same fonts and icons). */ static int info(int argc, char **argv) { @@ -583,14 +698,18 @@ static int info(int argc, char **argv) { for (uint32_t i = 0; i < s.symbols; ++i) { VegaSymbol symbol = vega_symbol_at(&s, i); double area = 0; + uint32_t curves = 0; + VegaCurve c; for (uint32_t k = symbol.first; k < symbol.first + symbol.count; ++k) { - VegaCurve c = vega_curve(&s, k); + if (!vega_symbol_curve(&s, &symbol, k, &c)) continue; + ++curves; /* x(t) = x0 - 2 bx t + ax t^2, y'(t) = -2 by + 2 ay t, over [0, 1]. */ double ax = c.x0 - 2 * c.x1 + c.x2, bx = c.x0 - c.x1, ay = c.y0 - 2 * c.y1 + c.y2, by = c.y0 - c.y1; area += c.x0 * -2 * by + (c.x0 * 2 * ay + 4 * bx * by) / 2 + (-4 * bx * ay - 2 * ax * by) / 3 + ax * ay / 2; } - printf("%s{\"code\":%u,\"curves\":%u,\"bounds\":[%d,%d,%d,%d],\"advance\":%d,\"area\":%.1f}", i ? "," : "", - symbol.code, symbol.count, symbol.left, symbol.bottom, symbol.right, symbol.top, symbol.advance, area); + printf("%s{\"code\":%u,\"points\":%u,\"curves\":%u,\"bounds\":[%d,%d,%d,%d],\"advance\":%d,\"area\":%.1f}", + i ? "," : "", symbol.code, symbol.count, curves, symbol.left, symbol.bottom, symbol.right, symbol.top, + symbol.advance, area); } printf("]}\n"); free(bytes); diff --git a/src/symbols.c b/src/symbols.c index daa35e5..cedd68f 100644 --- a/src/symbols.c +++ b/src/symbols.c @@ -1,9 +1,10 @@ #include "symbols.h" #include <math.h> #include <stdio.h> +#include <stdlib.h> #include <string.h> -static const unsigned char magic[8] = {'V', 'E', 'G', 'A', 'S', 'Y', 'M', '1'}; +static const unsigned char magic[8] = {'V', 'E', 'G', 'A', 'S', 'Y', 'M', '2'}; 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); } @@ -14,10 +15,14 @@ VegaSymbol vega_symbol_at(const VegaSymbols *s, uint32_t index) { return (VegaSymbol){u32(p), u32(p + 4), u32(p + 8), i16(p + 12), i16(p + 14), i16(p + 16), i16(p + 18), i16(p + 20)}; } -VegaCurve vega_curve(const VegaSymbols *s, uint32_t index) { +/* A point is two i16s, each its coordinate times two plus a flag: off the + * curve in x, starting a contour in y. */ +VegaPoint vega_point(const VegaSymbols *s, uint32_t index) { const unsigned char *p = s->bytes + VEGA_SYMBOLS_HEADER + (size_t)s->symbols * VEGA_SYMBOL_BYTES + - (size_t)index * VEGA_CURVE_BYTES; - return (VegaCurve){i16(p), i16(p + 2), i16(p + 4), i16(p + 6), i16(p + 8), i16(p + 10)}; + (size_t)index * VEGA_POINT_BYTES; + int x = i16(p), y = i16(p + 2); + /* x >> 1 without relying on how a negative number shifts */ + return (VegaPoint){(int16_t)((x - (x & 1)) / 2), (int16_t)((y - (y & 1)) / 2), x & 1, y & 1}; } #define REFUSE(...) do { snprintf(error, error_size, __VA_ARGS__); return false; } while (0) @@ -25,16 +30,22 @@ VegaCurve vega_curve(const VegaSymbols *s, uint32_t index) { 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), u32(bytes + 12), u32(bytes + 16)}; - uint64_t expected = VEGA_SYMBOLS_HEADER + (uint64_t)s->symbols * VEGA_SYMBOL_BYTES + (uint64_t)s->curves * VEGA_CURVE_BYTES; + uint64_t expected = VEGA_SYMBOLS_HEADER + (uint64_t)s->symbols * VEGA_SYMBOL_BYTES + (uint64_t)s->points * VEGA_POINT_BYTES; if (u16(bytes + 10) || u32(bytes + 24) || !s->units) REFUSE("header"); - if (u32(bytes + 20) != size || expected != size) REFUSE("size: %zu bytes for %u symbols and %u curves", size, s->symbols, s->curves); + 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); const unsigned char *p = bytes + VEGA_SYMBOLS_HEADER + (size_t)i * VEGA_SYMBOL_BYTES; if (u16(p + 22)) REFUSE("symbol %u: flags", i); if (i && symbol.code <= vega_symbol_at(s, i - 1).code) REFUSE("symbol %u: codes out of order", i); - if (symbol.first > s->curves || symbol.count > s->curves - symbol.first) REFUSE("symbol %u: curves", i); + if (symbol.first > s->points || symbol.count > s->points - symbol.first) REFUSE("symbol %u: points", i); if (symbol.left > symbol.right || symbol.bottom > symbol.top) REFUSE("symbol %u: bounds", i); + /* An off point then always has both neighbours within the symbol. */ + if (symbol.count) { + VegaPoint first = vega_point(s, symbol.first), last = vega_point(s, symbol.first + symbol.count - 1); + if (first.off || !first.move) REFUSE("symbol %u: its first point does not start a contour on the curve", i); + if (last.off) REFUSE("symbol %u: its last point is off the curve", i); + } } return true; } @@ -50,6 +61,21 @@ bool vega_symbol(const VegaSymbols *s, uint32_t code, VegaSymbol *out) { return false; } +bool vega_symbol_curve(const VegaSymbols *s, const VegaSymbol *symbol, uint32_t index, VegaCurve *out) { + VegaPoint p = vega_point(s, index); + if (p.off) { + VegaPoint a = vega_point(s, index - 1), b = vega_point(s, index + 1); + *out = (VegaCurve){a.off ? (a.x + p.x) * 0.5f : a.x, a.off ? (a.y + p.y) * 0.5f : a.y, p.x, p.y, + b.off ? (p.x + b.x) * 0.5f : b.x, b.off ? (p.y + b.y) * 0.5f : b.y}; + return true; + } + if (index + 1 >= symbol->first + symbol->count) return false; + VegaPoint b = vega_point(s, index + 1); + if (b.off || b.move) return false; + *out = (VegaCurve){p.x, p.y, (p.x + b.x) * 0.5f, (p.y + b.y) * 0.5f, b.x, b.y}; + return true; +} + /* Where a t^2 + b t + c = 0 inside (0, 1), appended to ts. */ static int roots(double a, double b, double c, double *ts) { int n = 0; @@ -106,13 +132,41 @@ static double curve_area(double x0, double y0, double x1, double y1, double x2, return area; } -double vega_symbol_coverage(const VegaSymbols *s, const VegaSymbol *symbol, double scale, double x, double y) { +/* Without branches on the flags, which no predictor guesses: implied points + * and whether a point begins a curve come out of arithmetic on them. */ +uint32_t vega_symbol_curves(const VegaSymbols *s, const VegaSymbol *symbol, VegaCurve *out) { + if (!symbol->count) return 0; + const unsigned char *p = s->bytes + VEGA_SYMBOLS_HEADER + (size_t)s->symbols * VEGA_SYMBOL_BYTES + + (size_t)symbol->first * VEGA_POINT_BYTES; + uint32_t count = 0; + int x = i16(p), y = i16(p + 2), off = x & 1; + float bx = 0, by = 0, bo = 0, hx = (float)(x - off) * 0.5f, hy = (float)(y - (y & 1)) * 0.5f, ho = (float)off; + for (uint32_t k = 1; k < symbol->count; ++k) { + p += VEGA_POINT_BYTES; + x = i16(p); + y = i16(p + 2); + float nx = (float)(x - (x & 1)) * 0.5f, ny = (float)(y - (y & 1)) * 0.5f, no = (float)(x & 1); + /* before, or halfway to here if before is off; here if here is on */ + float sx = bx + (hx - bx) * 0.5f * bo, sy = by + (hy - by) * 0.5f * bo; + out[count] = (VegaCurve){hx + (sx - hx) * ho, hy + (sy - hy) * ho, hx + (nx - hx) * 0.5f * (1 - ho), + hy + (ny - hy) * 0.5f * (1 - ho), nx + (hx - nx) * 0.5f * no, ny + (hy - ny) * 0.5f * no}; + /* an off point begins a curve, and so does an on point before an on + * point of the same contour (a line) */ + count += (uint32_t)(off | (((x & 1) ^ 1) & ((y & 1) ^ 1))); + off = x & 1; + bx = hx, by = hy, bo = ho; + hx = nx, hy = ny, ho = no; + } + return count; +} + +double vega_coverage(const VegaCurve *curves, uint32_t count, double scale, double x, double y) { /* The pixel's lower left corner, in units. */ double left = x - 0.5 / scale, bottom = y - 0.5 / scale, area = 0; - for (uint32_t k = symbol->first; k < symbol->first + symbol->count; ++k) { - VegaCurve c = vega_curve(s, k); - area += curve_area((c.x0 - left) * scale, (c.y0 - bottom) * scale, (c.x1 - left) * scale, (c.y1 - bottom) * scale, - (c.x2 - left) * scale, (c.y2 - bottom) * scale); + for (uint32_t k = 0; k < count; ++k) { + const VegaCurve *c = &curves[k]; + area += curve_area((c->x0 - left) * scale, (c->y0 - bottom) * scale, (c->x1 - left) * scale, (c->y1 - bottom) * scale, + (c->x2 - left) * scale, (c->y2 - bottom) * scale); } area = fabs(area); return area > 1 ? 1 : area; @@ -120,9 +174,12 @@ double vega_symbol_coverage(const VegaSymbols *s, const VegaSymbol *symbol, doub void vega_symbol_raster(const VegaSymbols *s, const VegaSymbol *symbol, double scale, double left, double top, int width, int height, unsigned char *out) { + VegaCurve *curves = malloc((symbol->count ? symbol->count : 1) * sizeof(*curves)); + uint32_t count = curves ? vega_symbol_curves(s, symbol, curves) : 0; for (int j = 0; j < height; ++j) for (int i = 0; i < width; ++i) { - double coverage = vega_symbol_coverage(s, symbol, scale, left + (i + 0.5) / scale, top - (j + 0.5) / scale); + double coverage = vega_coverage(curves, count, scale, left + (i + 0.5) / scale, top - (j + 0.5) / scale); out[(size_t)j * (size_t)width + (size_t)i] = (unsigned char)lround(coverage * 255); } + free(curves); } diff --git a/src/symbols.h b/src/symbols.h index da33e34..998ff3f 100644 --- a/src/symbols.h +++ b/src/symbols.h @@ -4,12 +4,19 @@ #include <stddef.h> #include <stdint.h> -/* Symbols: glyphs and icons as quadratic curves in one file, verified once - * and then read where it lies (docs/design/002-symbol-format.md). */ -enum { VEGA_SYMBOLS_HEADER = 28, VEGA_SYMBOL_BYTES = 24, VEGA_CURVE_BYTES = 12 }; -typedef struct { int16_t x0, y0, x1, y1, x2, y2; } VegaCurve; +/* Symbols: glyphs and icons as outlines of quadratic curves in one file, + * verified once and then read where it lies (docs/design/002-symbol-format.md). + * An outline is a chain of points, on or off the curve, as in TrueType: two + * off points in a row imply the on point halfway between them. */ +enum { VEGA_SYMBOLS_HEADER = 28, VEGA_SYMBOL_BYTES = 24, VEGA_POINT_BYTES = 4 }; typedef struct { - uint32_t code, first, count; /* its curves: [first, first + count) */ + int16_t x, y; + bool off; /* a control point */ + bool move; /* starts a contour */ +} VegaPoint; +typedef struct { float x0, y0, x1, y1, x2, y2; } VegaCurve; /* a line has its middle as control */ +typedef struct { + uint32_t code, first, count; /* its points: [first, first + count) */ int16_t left, bottom, right, top; /* bounds, in units, y up */ int16_t advance; } VegaSymbol; @@ -17,20 +24,29 @@ typedef struct { const unsigned char *bytes; size_t size; uint16_t units; /* per em */ - uint32_t symbols, curves; + uint32_t symbols, points; } VegaSymbols; /* 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. - * The curves themselves are not: one outside its symbol's bounds draws wrong. */ + * reading needs is checked, per symbol: after this no read leaves the file + * or its symbol. The points themselves are not: one outside its symbol's + * bounds draws wrong. */ bool vega_symbols_open(VegaSymbols *, const unsigned char *bytes, size_t size, char *error, size_t error_size); /* The symbol of code (a binary search), or false. */ bool vega_symbol(const VegaSymbols *, uint32_t code, VegaSymbol *out); VegaSymbol vega_symbol_at(const VegaSymbols *, uint32_t index); -VegaCurve vega_curve(const VegaSymbols *, uint32_t index); +VegaPoint vega_point(const VegaSymbols *, uint32_t index); +/* The curve that point index of symbol begins, if any: an off point is the + * control of one, and an on point followed by another on point in the same + * contour starts a line. Every curve of a symbol is had once this way, from + * the point and its two neighbours alone (as a GPU would fetch it). */ +bool vega_symbol_curve(const VegaSymbols *, const VegaSymbol *, uint32_t index, VegaCurve *out); +/* All of a symbol's curves, in one pass over its points; out has room for + * symbol->count (a symbol has no more curves than points). */ +uint32_t vega_symbol_curves(const VegaSymbols *, const VegaSymbol *, VegaCurve *out); /* The coverage (0 to 1) of the pixel whose center is (x, y) in units, at - * scale pixels per unit: as a GPU would compute it per pixel. */ -double vega_symbol_coverage(const VegaSymbols *, const VegaSymbol *, double scale, double x, double y); + * scale pixels per unit: the exact area the curves' outline covers. */ +double vega_coverage(const VegaCurve *, uint32_t count, double scale, double x, double y); /* width x height 8-bit coverage, rows top first; pixel (i, j) has its center * at (left + (i + 0.5) / scale, top - (j + 0.5) / scale) in units. */ void vega_symbol_raster(const VegaSymbols *, const VegaSymbol *, double scale, double left, double top, int width, |