aboutsummaryrefslogtreecommitdiffstats
path: root/symbols
diff options
context:
space:
mode:
Diffstat (limited to 'symbols')
-rw-r--r--symbols/symbols-gl.c260
-rw-r--r--symbols/symbols-gl.h24
-rw-r--r--symbols/symbols-tool.c881
-rw-r--r--symbols/symbols.c185
-rw-r--r--symbols/symbols.h54
5 files changed, 1404 insertions, 0 deletions
diff --git a/symbols/symbols-gl.c b/symbols/symbols-gl.c
new file mode 100644
index 0000000..0e78efe
--- /dev/null
+++ b/symbols/symbols-gl.c
@@ -0,0 +1,260 @@
+#include "symbols-gl.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+enum { BANDS = 16 };
+
+/* Coordinates travel doubled, so implied points stay whole: 2x of a point
+ * is its raw i16 without the flag, and an implied point's is the sum of its
+ * two neighbours' coordinates. */
+#define SHARED \
+ "#version 310 es\n" \
+ "precision highp float;\n" \
+ "precision highp int;\n"
+
+static const char vertex_source[] = SHARED
+ "layout(location = 0) in vec4 place; /* origin x, y in pixels; pixels per unit; unused */\n"
+ "layout(location = 1) in vec4 bounds; /* left, bottom, right, top in units */\n"
+ "layout(location = 2) in uint bands; /* its first band */\n"
+ "uniform vec2 target;\n"
+ "out vec2 units;\n"
+ "flat out float scale;\n"
+ "flat out ivec2 rows; /* bottom and top in units */\n"
+ "flat out uint base;\n"
+ "void main() {\n"
+ " vec2 corner = vec2(float(gl_VertexID & 1), float(gl_VertexID >> 1));\n"
+ " vec2 pad = vec2(1.0 / place.z);\n"
+ " units = mix(bounds.xy - pad, bounds.zw + pad, corner);\n"
+ " vec2 pixel = place.xy + vec2(units.x, -units.y) * place.z;\n"
+ " gl_Position = vec4(pixel.x / target.x * 2.0 - 1.0, 1.0 - pixel.y / target.y * 2.0, 0.0, 1.0);\n"
+ " scale = place.z;\n"
+ " rows = ivec2(bounds.yw);\n"
+ " base = bands;\n"
+ "}\n";
+
+static const char fragment_source[] = SHARED
+ "layout(std430, binding = 0) readonly buffer Points { uint points[]; };\n"
+ "layout(std430, binding = 1) readonly buffer Bands { uint bands[]; };\n"
+ "uniform uint listed; /* where the lists of curves start in bands */\n"
+ "in vec2 units;\n"
+ "flat in float scale;\n"
+ "flat in ivec2 rows;\n"
+ "flat in uint base;\n"
+ "out vec4 color;\n"
+ "\n"
+ "ivec3 point(uint i) { /* doubled x, doubled y, off */\n"
+ " uint w = points[i];\n"
+ " int x = int(w << 16u) >> 16, y = int(w) >> 16;\n"
+ " return ivec3(x & ~1, y & ~1, x & 1);\n"
+ "}\n"
+ "int band(int doubled) { /* which of 16 bands a doubled y lies in */\n"
+ " return clamp((doubled - 2 * rows.x) * 16 / (2 * (rows.y - rows.x) + 2), 0, 15);\n"
+ "}\n"
+ "int roots(float a, float b, float c, inout float ts[10], int n) {\n"
+ " float r0 = -1.0, r1 = -1.0;\n"
+ " if (a == 0.0) { if (b != 0.0) r0 = -c / b; }\n"
+ " else {\n"
+ " float d = b * b - 4.0 * a * c;\n"
+ " if (d >= 0.0) {\n"
+ " float q = -0.5 * (b + (b >= 0.0 ? sqrt(d) : -sqrt(d)));\n"
+ " r0 = q / a;\n"
+ " if (q != 0.0) r1 = c / q;\n"
+ " }\n"
+ " }\n"
+ " if (r0 > 0.0 && r0 < 1.0) ts[n++] = r0;\n"
+ " if (r1 > 0.0 && r1 < 1.0) ts[n++] = r1;\n"
+ " return n;\n"
+ "}\n"
+ "/* As curve_area in symbols.c: the curve's share of the pixel [0, 1]^2. */\n"
+ "float area(vec2 p0, vec2 p1, vec2 p2) {\n"
+ " if (max(max(p0.y, p1.y), p2.y) <= 0.0 || min(min(p0.y, p1.y), p2.y) >= 1.0 || min(min(p0.x, p1.x), p2.x) >= 1.0)\n"
+ " return 0.0;\n"
+ " if (max(max(p0.x, p1.x), p2.x) <= 0.0) return clamp(p2.y, 0.0, 1.0) - clamp(p0.y, 0.0, 1.0);\n"
+ " vec2 a = p0 - 2.0 * p1 + p2, b = p0 - p1;\n"
+ " float ts[10];\n"
+ " ts[0] = 0.0;\n"
+ " int n = 1;\n"
+ " n = roots(a.y, -2.0 * b.y, p0.y, ts, n);\n"
+ " n = roots(a.y, -2.0 * b.y, p0.y - 1.0, ts, n);\n"
+ " n = roots(a.x, -2.0 * b.x, p0.x, ts, n);\n"
+ " n = roots(a.x, -2.0 * b.x, p0.x - 1.0, ts, n);\n"
+ " ts[n++] = 1.0;\n"
+ " for (int i = 1; i < n; ++i)\n"
+ " for (int j = i; j > 0 && ts[j] < ts[j - 1]; --j) { float t = ts[j]; ts[j] = ts[j - 1]; ts[j - 1] = t; }\n"
+ " float u0 = 1.0 - p0.x, u1 = 2.0 * b.x, u2 = -a.x, v0 = -2.0 * b.y, v1 = 2.0 * a.y;\n"
+ " float k1 = u0 * v0, k2 = (u0 * v1 + u1 * v0) / 2.0, k3 = (u1 * v1 + u2 * v0) / 3.0, k4 = u2 * v1 / 4.0, sum = 0.0;\n"
+ " for (int i = 0; i + 1 < n; ++i) {\n"
+ " float ta = ts[i], tb = ts[i + 1], t = (ta + tb) / 2.0;\n"
+ " if (tb <= ta) continue;\n"
+ " float y = (a.y * t - 2.0 * b.y) * t + p0.y, x = (a.x * t - 2.0 * b.x) * t + p0.x;\n"
+ " if (y <= 0.0 || y >= 1.0 || x >= 1.0) continue;\n"
+ " if (x <= 0.0) sum += (a.y * tb - 2.0 * b.y) * tb - (a.y * ta - 2.0 * b.y) * ta;\n"
+ " else sum += (((k4 * tb + k3) * tb + k2) * tb + k1) * tb - (((k4 * ta + k3) * ta + k2) * ta + k1) * ta;\n"
+ " }\n"
+ " return sum;\n"
+ "}\n"
+ "void main() {\n"
+ " vec2 corner = units - vec2(0.5 / scale); /* the pixel's lower left, in units */\n"
+ " int b0 = band(2 * int(floor(corner.y))), b1 = band(2 * int(ceil(corner.y + 1.0 / scale)));\n"
+ " float sum = 0.0;\n"
+ " for (int b = b0; b <= b1; ++b) {\n"
+ " uint at = bands[base + 2u * uint(b)], end = at + bands[base + 2u * uint(b) + 1u];\n"
+ " for (; at < end; ++at) {\n"
+ " uint k = bands[listed + at];\n"
+ " ivec3 p = point(k), n = point(k + 1u);\n"
+ " ivec2 s, c, e;\n"
+ " if (p.z == 1) {\n"
+ " ivec3 q = point(k - 1u);\n"
+ " s = q.z == 1 ? (q.xy + p.xy) / 2 : q.xy;\n"
+ " c = p.xy;\n"
+ " e = n.z == 1 ? (p.xy + n.xy) / 2 : n.xy;\n"
+ " } else {\n"
+ " s = p.xy;\n"
+ " c = (p.xy + n.xy) / 2;\n"
+ " e = n.xy;\n"
+ " }\n"
+ " /* a curve over several of this pixel's bands counts in the first */\n"
+ " if (max(band(min(min(s.y, c.y), e.y)), b0) != b) continue;\n"
+ " sum += area((vec2(s) * 0.5 - corner) * scale, (vec2(c) * 0.5 - corner) * scale, (vec2(e) * 0.5 - corner) * scale);\n"
+ " }\n"
+ " }\n"
+ " color = vec4(min(abs(sum), 1.0), 0.0, 0.0, 1.0);\n"
+ "}\n";
+
+static GLuint compile(GLenum type, const char *source, char *error, size_t error_size) {
+ GLuint shader = glCreateShader(type);
+ glShaderSource(shader, 1, &source, NULL);
+ glCompileShader(shader);
+ GLint ok;
+ glGetShaderiv(shader, GL_COMPILE_STATUS, &ok);
+ if (!ok) {
+ glGetShaderInfoLog(shader, (GLsizei)error_size, NULL, error);
+ glDeleteShader(shader);
+ return 0;
+ }
+ return shader;
+}
+
+/* Doubled coordinates make implied points whole; bands as the shader cuts them. */
+static int band(int doubled, int bottom, int top) {
+ int b = (doubled - 2 * bottom) * BANDS / (2 * (top - bottom) + 2);
+ return b < 0 ? 0 : b >= BANDS ? BANDS - 1 : b;
+}
+
+bool vega_gl_open(VegaGl *gl, const VegaSymbols *s, char *error, size_t error_size) {
+ *gl = (VegaGl){0};
+ GLuint vertex = compile(GL_VERTEX_SHADER, vertex_source, error, error_size);
+ GLuint fragment = vertex ? compile(GL_FRAGMENT_SHADER, fragment_source, error, error_size) : 0;
+ if (!fragment) return false;
+ gl->program = glCreateProgram();
+ glAttachShader(gl->program, vertex);
+ glAttachShader(gl->program, fragment);
+ glLinkProgram(gl->program);
+ glDeleteShader(vertex);
+ glDeleteShader(fragment);
+ GLint ok;
+ glGetProgramiv(gl->program, GL_LINK_STATUS, &ok);
+ if (!ok) {
+ glGetProgramInfoLog(gl->program, (GLsizei)error_size, NULL, error);
+ return false;
+ }
+ /* The point table, as the file has it. */
+ glGenBuffers(1, &gl->points);
+ glBindBuffer(GL_SHADER_STORAGE_BUFFER, gl->points);
+ glBufferData(GL_SHADER_STORAGE_BUFFER, (GLsizeiptr)(s->points ? s->points : 1) * VEGA_POINT_BYTES,
+ s->bytes + VEGA_SYMBOLS_HEADER + (size_t)s->symbols * VEGA_SYMBOL_BYTES, GL_STATIC_DRAW);
+ /* Bands: per symbol, 16 (start, count) pairs into one list of curves,
+ * each curve (by the point that begins it) in every band it reaches. */
+ size_t table = (size_t)s->symbols * BANDS * 2, listed = 0;
+ uint32_t *counts = calloc(table + 1, sizeof(*counts));
+ for (int pass = 0; pass < 2; ++pass) {
+ uint32_t *bands = pass ? malloc((table + listed + 1) * sizeof(*bands)) : NULL;
+ size_t next = 0;
+ for (uint32_t i = 0; i < s->symbols; ++i) {
+ VegaSymbol symbol = vega_symbol_at(s, i);
+ uint32_t *mine = pass ? bands + (size_t)i * BANDS * 2 : counts + (size_t)i * BANDS * 2;
+ if (pass)
+ for (int b = 0; b < BANDS; ++b) {
+ mine[2 * b] = (uint32_t)next;
+ next += counts[(size_t)i * BANDS * 2 + 2 * b + 1];
+ mine[2 * b + 1] = 0;
+ }
+ VegaCurve c;
+ for (uint32_t k = symbol.first; k < symbol.first + symbol.count; ++k) {
+ if (!vega_symbol_curve(s, &symbol, k, &c)) continue;
+ float low = c.y0 < c.y1 ? c.y0 : c.y1, high = c.y0 > c.y1 ? c.y0 : c.y1;
+ low = c.y2 < low ? c.y2 : low;
+ high = c.y2 > high ? c.y2 : high;
+ int from = band((int)(2 * low), symbol.bottom, symbol.top), to = band((int)(2 * high), symbol.bottom, symbol.top);
+ for (int b = from; b <= to; ++b) {
+ if (pass) bands[table + mine[2 * b] + mine[2 * b + 1]] = k;
+ ++mine[2 * b + 1];
+ listed += !pass;
+ }
+ }
+ }
+ if (pass) {
+ glGenBuffers(1, &gl->bands);
+ glBindBuffer(GL_SHADER_STORAGE_BUFFER, gl->bands);
+ glBufferData(GL_SHADER_STORAGE_BUFFER, (GLsizeiptr)((table + listed + 1) * sizeof(*bands)), bands, GL_STATIC_DRAW);
+ free(bands);
+ }
+ }
+ free(counts);
+ glGenVertexArrays(1, &gl->array);
+ glGenBuffers(1, &gl->instances);
+ glBindVertexArray(gl->array);
+ glBindBuffer(GL_ARRAY_BUFFER, gl->instances);
+ glEnableVertexAttribArray(0);
+ glEnableVertexAttribArray(1);
+ glEnableVertexAttribArray(2);
+ glVertexAttribPointer(0, 4, GL_FLOAT, GL_FALSE, 36, (void *)0);
+ glVertexAttribPointer(1, 4, GL_FLOAT, GL_FALSE, 36, (void *)16);
+ glVertexAttribIPointer(2, 1, GL_UNSIGNED_INT, 36, (void *)32);
+ glVertexAttribDivisor(0, 1);
+ glVertexAttribDivisor(1, 1);
+ glVertexAttribDivisor(2, 1);
+ glBindVertexArray(0);
+ glUseProgram(gl->program);
+ glUniform1ui(glGetUniformLocation(gl->program, "listed"), (GLuint)table);
+ gl->viewport = glGetUniformLocation(gl->program, "target");
+ if (glGetError() != GL_NO_ERROR) {
+ snprintf(error, error_size, "GL error while uploading");
+ return false;
+ }
+ return true;
+}
+
+void vega_gl_draw(VegaGl *gl, const VegaSymbols *s, const VegaGlyph *glyphs, uint32_t count, int width, int height) {
+ float *instances = malloc((size_t)(count ? count : 1) * 36);
+ for (uint32_t i = 0; i < count; ++i) {
+ VegaSymbol symbol = vega_symbol_at(s, glyphs[i].symbol);
+ float *f = instances + (size_t)i * 9;
+ f[0] = glyphs[i].x, f[1] = glyphs[i].y, f[2] = glyphs[i].scale, f[3] = 0;
+ f[4] = symbol.left, f[5] = symbol.bottom, f[6] = symbol.right, f[7] = symbol.top;
+ uint32_t base = glyphs[i].symbol * BANDS * 2;
+ memcpy(f + 8, &base, 4);
+ }
+ glUseProgram(gl->program);
+ glUniform2f(gl->viewport, (float)width, (float)height);
+ glBindBufferBase(GL_SHADER_STORAGE_BUFFER, 0, gl->points);
+ glBindBufferBase(GL_SHADER_STORAGE_BUFFER, 1, gl->bands);
+ glBindVertexArray(gl->array);
+ glBindBuffer(GL_ARRAY_BUFFER, gl->instances);
+ glBufferData(GL_ARRAY_BUFFER, (GLsizeiptr)count * 36, instances, GL_STREAM_DRAW);
+ glEnable(GL_BLEND);
+ glBlendFunc(GL_ONE, GL_ONE);
+ glDrawArraysInstanced(GL_TRIANGLE_STRIP, 0, 4, (GLsizei)count);
+ glBindVertexArray(0);
+ free(instances);
+}
+
+void vega_gl_close(VegaGl *gl) {
+ glDeleteBuffers(1, &gl->points);
+ glDeleteBuffers(1, &gl->bands);
+ glDeleteBuffers(1, &gl->instances);
+ glDeleteVertexArrays(1, &gl->array);
+ glDeleteProgram(gl->program);
+ *gl = (VegaGl){0};
+}
diff --git a/symbols/symbols-gl.h b/symbols/symbols-gl.h
new file mode 100644
index 0000000..4c6db67
--- /dev/null
+++ b/symbols/symbols-gl.h
@@ -0,0 +1,24 @@
+#ifndef VEGA_SYMBOLS_GL_H
+#define VEGA_SYMBOLS_GL_H
+#include "symbols.h"
+#include <GLES3/gl31.h>
+
+/* Symbols drawn by the GPU (OpenGL ES 3.1): the file's point table goes up
+ * as it is, one storage buffer, and each pixel of a symbol's box sums the
+ * exact area of the curves crossing its row, as vega_coverage does. Rows
+ * are cut into bands at upload, each listing its curves, so a pixel reads
+ * only those. Needs a current context. */
+typedef struct {
+ GLuint program, points, bands, instances, array;
+ GLint viewport;
+} VegaGl;
+
+/* A symbol placed: its origin in pixels from the target's top left, and
+ * pixels per unit. */
+typedef struct { float x, y, scale; uint32_t symbol; } VegaGlyph;
+
+bool vega_gl_open(VegaGl *, const VegaSymbols *, char *error, size_t error_size);
+/* Coverage added into the red channel of the bound framebuffer. */
+void vega_gl_draw(VegaGl *, const VegaSymbols *, const VegaGlyph *, uint32_t count, int width, int height);
+void vega_gl_close(VegaGl *);
+#endif
diff --git a/symbols/symbols-tool.c b/symbols/symbols-tool.c
new file mode 100644
index 0000000..a94feb3
--- /dev/null
+++ b/symbols/symbols-tool.c
@@ -0,0 +1,881 @@
+#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 --codes 0x20-0x7e,...] [--svg CODE=ICON.svg ...] [--units N] -o OUT.vsym
+ * 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 "symbols-gl.h"
+#include "symbols.h"
+#include <EGL/egl.h>
+#include <EGL/eglext.h>
+#include <ft2build.h>
+#include FT_FREETYPE_H
+#include FT_OUTLINE_H
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+
+#define PI 3.14159265358979323846
+
+typedef struct { double x, y; } Point;
+/* 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(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++] = segment;
+ path->at = segment.end;
+}
+
+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 (!same(to, path->at)) add(path, (Segment){LINE, false, to, 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);
+}
+
+/* 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) {
+ 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));
+ }
+ 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);
+ /* 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);
+ add(path, (Segment){MOVE, false, to, to});
+ path->start = to;
+ path->open = true;
+}
+
+/* ---- Fonts, through FreeType's outline walk (in its units, times font_scale). */
+
+static Point point_of(const Path *path, const FT_Vector *v) {
+ return (Point){(double)v->x * path->font_scale, (double)v->y * path->font_scale};
+}
+static int ft_move(const FT_Vector *to, void *user) { move_to(user, point_of(user, to)); return 0; }
+static int ft_line(const FT_Vector *to, void *user) { line_to(user, point_of(user, to)); return 0; }
+static int ft_conic(const FT_Vector *c, const FT_Vector *to, void *user) {
+ quad_to(user, point_of(user, c), point_of(user, to));
+ return 0;
+}
+static int ft_cubic(const FT_Vector *c1, const FT_Vector *c2, const FT_Vector *to, void *user) {
+ cubic_to(user, point_of(user, c1), point_of(user, c2), point_of(user, to));
+ return 0;
+}
+
+/* ---- SVG icons: the d of each path, the viewBox's height as the em. */
+
+static const char *number(const char *p, double *out) {
+ while (*p == ' ' || *p == ',' || *p == '\n' || *p == '\t' || *p == '\r') ++p;
+ char *end;
+ *out = strtod(p, &end);
+ return end == p ? NULL : end;
+}
+
+/* An arc's flags are single digits, perhaps with no space between them. */
+static const char *flag(const char *p, double *out) {
+ while (*p == ' ' || *p == ',' || *p == '\n' || *p == '\t' || *p == '\r') ++p;
+ if (*p != '0' && *p != '1') return NULL;
+ *out = *p - '0';
+ return p + 1;
+}
+
+typedef struct { double x, y, width, height, scale; } Box;
+
+static Point svg_point(const Box *box, double x, double y) {
+ return (Point){(x - box->x) * box->scale, (box->y + box->height - y) * box->scale};
+}
+
+/* An elliptical arc from (x1, y1) to (x2, y2) as cubics of at most a quarter
+ * turn each (SVG 1.1, F.6.5: from its endpoints to its center). */
+static void arc_to(Path *path, const Box *box, double x1, double y1, double rx, double ry, double degrees, bool large,
+ bool sweep, double x2, double y2) {
+ rx = fabs(rx);
+ ry = fabs(ry);
+ if ((x1 == x2 && y1 == y2)) return;
+ if (!rx || !ry) {
+ line_to(path, svg_point(box, x2, y2));
+ return;
+ }
+ double phi = degrees * PI / 180, cp = cos(phi), sp = sin(phi);
+ double hx = (x1 - x2) / 2, hy = (y1 - y2) / 2, px = cp * hx + sp * hy, py = -sp * hx + cp * hy;
+ double lambda = px * px / (rx * rx) + py * py / (ry * ry);
+ if (lambda > 1) { rx *= sqrt(lambda); ry *= sqrt(lambda); }
+ double num = rx * rx * ry * ry - rx * rx * py * py - ry * ry * px * px, den = rx * rx * py * py + ry * ry * px * px;
+ double k = (large == sweep ? -1 : 1) * sqrt(fmax(num / den, 0));
+ double ccx = k * rx * py / ry, ccy = -k * ry * px / rx;
+ double cx = cp * ccx - sp * ccy + (x1 + x2) / 2, cy = sp * ccx + cp * ccy + (y1 + y2) / 2;
+ double start = atan2((py - ccy) / ry, (px - ccx) / rx), turn = atan2((-py - ccy) / ry, (-px - ccx) / rx) - start;
+ if (sweep && turn < 0) turn += 2 * PI;
+ if (!sweep && turn > 0) turn -= 2 * PI;
+ int n = (int)ceil(fabs(turn) / (PI / 2) - 1e-9);
+ double step = turn / n, kappa = 4.0 / 3 * tan(step / 4);
+ for (int i = 0; i < n; ++i) {
+ double a = start + i * step, b = a + step;
+ double u[4][2] = {{cos(a), sin(a)}, {cos(a) - kappa * sin(a), sin(a) + kappa * cos(a)},
+ {cos(b) + kappa * sin(b), sin(b) - kappa * cos(b)}, {cos(b), sin(b)}};
+ Point q[4];
+ for (int j = 0; j < 4; ++j)
+ q[j] = svg_point(box, cx + rx * cp * u[j][0] - ry * sp * u[j][1], cy + rx * sp * u[j][0] + ry * cp * u[j][1]);
+ if (i == n - 1) q[3] = svg_point(box, x2, y2);
+ cubic_to(path, q[1], q[2], q[3]);
+ }
+}
+
+static void svg_path(Path *path, const Box *box, const char *d) {
+ double cx = 0, cy = 0, sx = 0, sy = 0, lx = 0, ly = 0; /* current, subpath start, last control */
+ char command = 0, last = 0;
+ for (const char *p = d; *p;) {
+ while (*p == ' ' || *p == ',' || *p == '\n' || *p == '\t' || *p == '\r') ++p;
+ if (!*p) break;
+ if (strchr("MmLlHhVvQqTtCcSsZzAa", *p)) command = *p++;
+ else if (!command) fail("SVG path data without a command");
+ bool relative = command >= 'a';
+ double ox = relative ? cx : 0, oy = relative ? cy : 0, v[7];
+ char upper = (char)(command & ~32);
+ int want = upper == 'M' || upper == 'L' || upper == 'T' ? 2 : upper == 'H' || upper == 'V' ? 1 :
+ upper == 'Q' || upper == 'S' ? 4 : upper == 'C' ? 6 : upper == 'A' ? 7 : 0;
+ for (int i = 0; i < want; ++i)
+ if (!(p = (upper == 'A' && (i == 3 || i == 4) ? flag : number)(p, &v[i]))) fail("SVG path data");
+ switch (upper) {
+ case 'Z':
+ close_path(path);
+ cx = sx; cy = sy;
+ path->at = svg_point(box, cx, cy);
+ command = 0; /* a number after closepath is an error */
+ break;
+ case 'A': {
+ double x = ox + v[5], y = oy + v[6];
+ arc_to(path, box, cx, cy, v[0], v[1], v[2], v[3] != 0, v[4] != 0, x, y);
+ cx = x; cy = y;
+ break;
+ }
+ case 'M':
+ cx = ox + v[0]; cy = oy + v[1]; sx = cx; sy = cy;
+ move_to(path, svg_point(box, cx, cy));
+ command = relative ? 'l' : 'L'; /* pairs after a moveto are linetos */
+ break;
+ case 'L': cx = ox + v[0]; cy = oy + v[1]; line_to(path, svg_point(box, cx, cy)); break;
+ case 'H': cx = ox + v[0]; line_to(path, svg_point(box, cx, cy)); break;
+ case 'V': cy = (relative ? cy : 0) + v[0]; line_to(path, svg_point(box, cx, cy)); break;
+ case 'Q':
+ lx = ox + v[0]; ly = oy + v[1]; cx = ox + v[2]; cy = oy + v[3];
+ quad_to(path, svg_point(box, lx, ly), svg_point(box, cx, cy));
+ break;
+ case 'T':
+ lx = last == 'Q' || last == 'T' ? 2 * cx - lx : cx; ly = last == 'Q' || last == 'T' ? 2 * cy - ly : cy;
+ cx = ox + v[0]; cy = oy + v[1];
+ quad_to(path, svg_point(box, lx, ly), svg_point(box, cx, cy));
+ break;
+ case 'C': case 'S': {
+ double x1, y1;
+ if (upper == 'C') { x1 = ox + v[0]; y1 = oy + v[1]; }
+ else { x1 = last == 'C' || last == 'S' ? 2 * cx - lx : cx; y1 = last == 'C' || last == 'S' ? 2 * cy - ly : cy; }
+ int at = upper == 'C' ? 2 : 0;
+ lx = ox + v[at]; ly = oy + v[at + 1];
+ double x = ox + v[at + 2], y = oy + v[at + 3];
+ cubic_to(path, svg_point(box, x1, y1), svg_point(box, lx, ly), svg_point(box, x, y));
+ cx = x; cy = y;
+ break;
+ }
+ }
+ last = upper;
+ }
+ close_path(path);
+}
+
+static char *read_file(const char *name, size_t *size) {
+ FILE *f = fopen(name, "rb");
+ if (!f) return NULL;
+ fseek(f, 0, SEEK_END);
+ long length = ftell(f);
+ fseek(f, 0, SEEK_SET);
+ char *bytes = length >= 0 ? malloc((size_t)length + 1) : NULL;
+ if (bytes && fread(bytes, 1, (size_t)length, f) != (size_t)length) { free(bytes); bytes = NULL; }
+ fclose(f);
+ if (bytes) { bytes[length] = 0; *size = (size_t)length; }
+ return bytes;
+}
+
+static const char *attribute(const char *from, const char *end, const char *name) {
+ size_t length = strlen(name);
+ for (const char *p = from; p && p < end; ++p) {
+ p = strstr(p, name);
+ if (!p || p >= end) return NULL;
+ if ((p == from || p[-1] == ' ' || p[-1] == '\n' || p[-1] == '\t') && p[length] == '=' &&
+ (p[length + 1] == '"' || p[length + 1] == '\'')) return p + length + 2;
+ }
+ return NULL;
+}
+
+/* Only solid, nonzero-filled paths: anything else an icon asks for would be
+ * drawn wrong, so it is refused rather than dropped. */
+static const char *const unsupported[] = {"transform", "opacity", "evenodd", "stroke", "fill=\"none\"", "<use",
+ "<rect", "<circle", "<ellipse", "<poly", "<line", "<radial", "<clip",
+ "<mask", "<image", "<text", "<filter", "<pattern"};
+
+static void svg_icon(Path *path, const char *file, uint16_t units, int16_t *advance) {
+ size_t size;
+ char *svg = read_file(file, &size), why[512];
+ if (!svg) fail("cannot read an SVG file");
+ for (size_t i = 0; i < sizeof(unsupported) / sizeof(*unsupported); ++i)
+ if (strstr(svg, unsupported[i])) {
+ snprintf(why, sizeof(why), "%s: icons hold only solid paths, not %s", file, unsupported[i]);
+ fail(why);
+ }
+ const char *tag = strstr(svg, "<svg"), *tag_end = tag ? strchr(tag, '>') : NULL, *view = tag ? attribute(tag, tag_end, "viewBox") : NULL;
+ /* Without a viewBox, the width and height (in px) are the user space. */
+ Box box = {0};
+ const char *width = tag ? attribute(tag, tag_end, "width") : NULL, *height = tag ? attribute(tag, tag_end, "height") : NULL;
+ if (view ? !(view = number(view, &box.x)) || !(view = number(view, &box.y)) || !(view = number(view, &box.width)) ||
+ !number(view, &box.height)
+ : !width || !height || !number(width, &box.width) || !number(height, &box.height) || box.height <= 0) {
+ snprintf(why, sizeof(why), "%s: an icon needs a viewBox, or a width and height", file);
+ fail(why);
+ }
+ box.scale = units / box.height;
+ *advance = (int16_t)lround(box.width * box.scale);
+ for (const char *p = svg; (p = strstr(p, "<path"));) {
+ const char *end = strchr(p, '>'), *d = attribute(p, end, "d");
+ if (d) {
+ char quote = d[-1];
+ const char *close = strchr(d, quote);
+ char *data = strndup(d, (size_t)(close - d));
+ svg_path(path, &box, data);
+ free(data);
+ }
+ p = end ? end : p + 5;
+ }
+ free(svg);
+}
+
+/* ---- 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 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) {
+ uint32_t x = ((const Built *)a)->code, y = ((const Built *)b)->code;
+ return (x > y) - (x < y);
+}
+
+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");
+ 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, "VEGASYM2", 8);
+ put16(bytes + 8, units);
+ put32(bytes + 12, (uint32_t)count);
+ put32(bytes + 16, (uint32_t)points.count);
+ put32(bytes + 20, (uint32_t)size);
+ 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) {
+ 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 *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");
+ char error[128];
+ VegaSymbols check;
+ 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. */
+static size_t codes_of(const char *text, uint32_t **out) {
+ size_t count = 0, capacity = 0;
+ *out = NULL;
+ for (const char *p = text; *p;) {
+ char *end;
+ unsigned long first = strtoul(p, &end, 0), last = first;
+ if (end == p) fail("--codes takes FIRST[-LAST],...");
+ p = end;
+ if (*p == '-') { last = strtoul(p + 1, &end, 0); p = end; }
+ for (unsigned long c = first; c <= last; ++c) {
+ if (count == capacity && !(*out = realloc(*out, (capacity = capacity ? 2 * capacity : 256) * sizeof(**out))))
+ fail("out of memory");
+ (*out)[count++] = (uint32_t)c;
+ }
+ if (*p == ',') ++p;
+ }
+ return count;
+}
+
+static double seconds(void) {
+ struct timespec t;
+ clock_gettime(CLOCK_MONOTONIC, &t);
+ return (double)t.tv_sec + (double)t.tv_nsec / 1e9;
+}
+
+#define BUILD_USAGE "usage: vega-symbols build [--font FONT.ttf --codes 0x20-0x7e,...] [--svg CODE=ICON.svg ...] [--units N] -o OUT.vsym"
+
+static int build(int argc, char **argv) {
+ const char *font = NULL, *out = NULL, *codes = NULL, **icons = calloc((size_t)argc, sizeof(*icons));
+ size_t icon_count = 0;
+ 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")) font = argv[i + 1];
+ else if (!strcmp(argv[i], "--codes")) codes = argv[i + 1];
+ else if (!strcmp(argv[i], "--units")) units = strtol(argv[i + 1], NULL, 10);
+ else if (!strcmp(argv[i], "--svg")) icons[icon_count++] = argv[i + 1];
+ else fail(BUILD_USAGE);
+ }
+ if (!out || !font != !codes) fail(BUILD_USAGE);
+ FT_Library library = NULL;
+ FT_Face face = NULL;
+ if (font && (FT_Init_FreeType(&library) || FT_New_Face(library, font, 0, &face))) fail("cannot open the font");
+ /* Twice a font's units by default: TrueType's implied points, halfway
+ * between two control points, then land on whole units. (FreeType finds
+ * them by integer halving, so outlines are doubled before it walks them.) */
+ if (!units) units = face ? 2 * face->units_per_EM : 4096;
+ if (units < 16 || units > 16384) fail("--units: 16 to 16384");
+ uint32_t *list = NULL;
+ size_t count = codes ? codes_of(codes, &list) : 0;
+ Built *built = calloc(count + icon_count + 1, sizeof(*built));
+ Path path = {.font_scale = face ? (double)units / (2.0 * face->units_per_EM) : 1};
+ size_t made = 0;
+ FT_Outline_Funcs walk = {ft_move, ft_line, ft_conic, ft_cubic, 0, 0};
+ for (size_t i = 0; i < count; ++i) {
+ FT_UInt glyph = FT_Get_Char_Index(face, list[i]);
+ if (!glyph || FT_Load_Glyph(face, glyph, FT_LOAD_NO_SCALE)) continue; /* the font lacks it */
+ 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){list[i], first, path.count - first, (int16_t)(advance > INT16_MAX ? INT16_MAX : advance)};
+ }
+ for (size_t i = 0; i < icon_count; ++i) {
+ char *equals = strchr(icons[i], '=');
+ if (!equals) fail("--svg takes CODE=FILE");
+ size_t first = path.count;
+ 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};
+ }
+ write_symbols(out, (uint16_t)units, built, made, &path);
+ if (face) FT_Done_Face(face);
+ if (library) FT_Done_FreeType(library);
+ free(icons);
+ free(list);
+ free(built);
+ free(path.items);
+ return 0;
+}
+
+static VegaSymbols open_symbols(const char *name, char **bytes) {
+ size_t size;
+ char error[128];
+ VegaSymbols s;
+ if (!(*bytes = read_file(name, &size))) fail("cannot read the symbol file");
+ if (!vega_symbols_open(&s, (unsigned char *)*bytes, size, error, sizeof(error))) fail(error);
+ return s;
+}
+
+static volatile long sink; /* keeps the timed loops' reads */
+static int ignore_point(const FT_Vector *to, void *user) { ++*(long *)user; (void)to; return 0; }
+static int ignore_conic(const FT_Vector *c, const FT_Vector *to, void *user) { (void)c; return ignore_point(to, user); }
+static int ignore_cubic(const FT_Vector *c1, const FT_Vector *c2, const FT_Vector *to, void *user) {
+ (void)c1;
+ (void)c2;
+ return ignore_point(to, user);
+}
+
+/* What reading costs, both ways: opening (verifying the symbol file; parsing
+ * the font's tables) and reaching every symbol's outline. */
+static void measure_open(FT_Library library, const char *font, const VegaSymbols *s) {
+ size_t font_size;
+ char *font_bytes = read_file(font, &font_size), error[128];
+ if (!font_bytes) fail("cannot read the font");
+ int rounds = 200;
+ double started = seconds();
+ for (int i = 0; i < rounds; ++i) {
+ VegaSymbols again;
+ if (!vega_symbols_open(&again, s->bytes, s->size, error, sizeof(error))) fail(error);
+ }
+ double open_us = (seconds() - started) / rounds * 1e6;
+ started = seconds();
+ for (int i = 0; i < rounds; ++i) {
+ FT_Face face;
+ if (FT_New_Memory_Face(library, (const FT_Byte *)font_bytes, (FT_Long)font_size, 0, &face)) fail("cannot open the font");
+ FT_Done_Face(face);
+ }
+ double freetype_open_us = (seconds() - started) / rounds * 1e6;
+ FT_Face face;
+ 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");
+ 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();
+ for (int r = 0; r < rounds; ++r)
+ for (uint32_t i = 0; i < s->symbols; ++i) {
+ FT_UInt glyph = FT_Get_Char_Index(face, vega_symbol_at(s, i).code);
+ if (glyph && !FT_Load_Glyph(face, glyph, FT_LOAD_NO_SCALE)) FT_Outline_Decompose(&face->glyph->outline, &walk, &walked);
+ }
+ double freetype_outline_ns = (seconds() - started) / rounds / s->symbols * 1e9;
+ printf("{\"symbol_bytes\":%zu,\"font_bytes\":%zu,\"open_us\":%.1f,\"freetype_open_us\":%.1f,\"outline_ns\":%.0f,"
+ "\"freetype_outline_ns\":%.0f}\n", s->size, font_size, open_us, freetype_open_us, outline_ns, freetype_outline_ns);
+ 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
+ * FreeType's (no hinting, 8-bit gray) over FreeType's bitmap. */
+static int compare(int argc, char **argv) {
+ if (argc < 6 || strcmp(argv[4], "--sizes")) fail("usage: vega-symbols compare FONT.ttf SYMBOLS.vsym --sizes 12,16,32,64");
+ char *bytes;
+ VegaSymbols s = open_symbols(argv[3], &bytes);
+ FT_Library library;
+ FT_Face face;
+ if (FT_Init_FreeType(&library) || FT_New_Face(library, argv[2], 0, &face)) fail("cannot open the font");
+ measure_open(library, argv[2], &s);
+ for (const char *p = argv[5]; *p;) {
+ char *end;
+ long size = strtol(p, &end, 10);
+ p = *end == ',' ? end + 1 : end;
+ if (size <= 0 || FT_Set_Pixel_Sizes(face, 0, (FT_UInt)size)) fail("--sizes");
+ double scale = (double)size / s.units, total = 0, ours_seconds = 0;
+ uint64_t pixels = 0, close = 0;
+ int worst = 0, glyphs = 0;
+ unsigned char *raster = NULL;
+ size_t raster_size = 0;
+ for (uint32_t i = 0; i < s.symbols; ++i) {
+ VegaSymbol symbol = vega_symbol_at(&s, i);
+ FT_UInt glyph = FT_Get_Char_Index(face, symbol.code);
+ if (!glyph || FT_Load_Glyph(face, glyph, FT_LOAD_NO_HINTING | FT_LOAD_RENDER)) continue;
+ FT_Bitmap *b = &face->glyph->bitmap;
+ size_t need = (size_t)b->width * b->rows;
+ if (!need) continue;
+ if (need > raster_size && !(raster = realloc(raster, raster_size = need))) fail("out of memory");
+ double started = seconds();
+ vega_symbol_raster(&s, &symbol, scale, face->glyph->bitmap_left / scale, face->glyph->bitmap_top / scale,
+ (int)b->width, (int)b->rows, raster);
+ ours_seconds += seconds() - started;
+ for (unsigned j = 0; j < b->rows; ++j)
+ for (unsigned i2 = 0; i2 < b->width; ++i2) {
+ int theirs = b->buffer[j * (unsigned)b->pitch + i2], ours = raster[j * b->width + i2];
+ int difference = abs(theirs - ours);
+ total += difference;
+ close += difference <= 16;
+ if (difference > worst) worst = difference;
+ ++pixels;
+ }
+ ++glyphs;
+ }
+ printf("{\"pixels_per_em\":%ld,\"glyphs\":%d,\"mean_difference\":%.2f,\"worst\":%d,\"within_16\":%.4f,"
+ "\"reference_us_per_glyph\":%.1f}\n", size, glyphs, pixels ? total / (double)pixels : 0, worst,
+ pixels ? (double)close / (double)pixels : 1, glyphs ? ours_seconds / glyphs * 1e6 : 0);
+ free(raster);
+ }
+ FT_Done_Face(face);
+ FT_Done_FreeType(library);
+ free(bytes);
+ return 0;
+}
+
+/* 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) {
+ if (argc < 3) fail("usage: vega-symbols info SYMBOLS.vsym");
+ char *bytes;
+ VegaSymbols s = open_symbols(argv[2], &bytes);
+ printf("{\"units\":%u,\"symbols\":[", s.units);
+ 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) {
+ 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,\"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);
+ return 0;
+}
+
+static int render(int argc, char **argv) {
+ if (argc < 6) fail("usage: vega-symbols render SYMBOLS.vsym CODE PIXELS OUT.pgm");
+ char *bytes;
+ VegaSymbols s = open_symbols(argv[2], &bytes);
+ VegaSymbol symbol;
+ if (!vega_symbol(&s, (uint32_t)strtoul(argv[3], NULL, 0), &symbol)) fail("no such symbol");
+ double pixels = atof(argv[4]), scale = pixels / s.units;
+ int width = (int)ceil((symbol.advance > symbol.right ? symbol.advance : symbol.right) * scale) + 2;
+ int height = (int)ceil(pixels * 1.25) + 2;
+ unsigned char *raster = malloc((size_t)width * (size_t)height);
+ vega_symbol_raster(&s, &symbol, scale, -1 / scale, (pixels + 1) / scale, width, height, raster);
+ FILE *f = fopen(argv[5], "wb");
+ if (!f) fail("cannot write");
+ fprintf(f, "P5\n%d %d\n255\n", width, height);
+ fwrite(raster, 1, (size_t)width * (size_t)height, f);
+ fclose(f);
+ free(raster);
+ free(bytes);
+ return 0;
+}
+
+/* ---- The GPU: a context of its own, no window (EGL, Mesa's surfaceless platform). */
+
+static void gl_context(void) {
+ PFNEGLGETPLATFORMDISPLAYEXTPROC platform = (PFNEGLGETPLATFORMDISPLAYEXTPROC)eglGetProcAddress("eglGetPlatformDisplayEXT");
+ EGLDisplay display = platform ? platform(EGL_PLATFORM_SURFACELESS_MESA, EGL_DEFAULT_DISPLAY, NULL) : EGL_NO_DISPLAY;
+ EGLint major, minor, found;
+ EGLConfig config;
+ EGLint wanted[] = {EGL_RENDERABLE_TYPE, EGL_OPENGL_ES3_BIT, EGL_NONE};
+ EGLint version[] = {EGL_CONTEXT_MAJOR_VERSION, 3, EGL_CONTEXT_MINOR_VERSION, 1, EGL_NONE};
+ if (display == EGL_NO_DISPLAY || !eglInitialize(display, &major, &minor) || !eglBindAPI(EGL_OPENGL_ES_API) ||
+ !eglChooseConfig(display, wanted, &config, 1, &found))
+ fail("no EGL display for OpenGL ES 3.1");
+ /* With no surface, a context needs no config (EGL_KHR_no_config_context). */
+ EGLContext context = eglCreateContext(display, found ? config : EGL_NO_CONFIG_KHR, EGL_NO_CONTEXT, version);
+ if (context == EGL_NO_CONTEXT || !eglMakeCurrent(display, EGL_NO_SURFACE, EGL_NO_SURFACE, context))
+ fail("no OpenGL ES 3.1 context");
+}
+
+/* A width x height target of 8-bit red, bound. */
+static GLuint gl_target(int width, int height) {
+ GLuint texture, framebuffer;
+ glGenTextures(1, &texture);
+ glBindTexture(GL_TEXTURE_2D, texture);
+ glTexStorage2D(GL_TEXTURE_2D, 1, GL_R8, width, height);
+ glGenFramebuffers(1, &framebuffer);
+ glBindFramebuffer(GL_FRAMEBUFFER, framebuffer);
+ glFramebufferTexture2D(GL_FRAMEBUFFER, GL_COLOR_ATTACHMENT0, GL_TEXTURE_2D, texture, 0);
+ if (glCheckFramebufferStatus(GL_FRAMEBUFFER) != GL_FRAMEBUFFER_COMPLETE) fail("no framebuffer");
+ glViewport(0, 0, width, height);
+ glClearColor(0, 0, 0, 0);
+ glClear(GL_COLOR_BUFFER_BIT);
+ return texture;
+}
+
+/* Every symbol in a grid of cells, drawn by the GPU and by vega_coverage:
+ * how far apart; then pages of text (glyphs cycling through the file)
+ * drawn again and again: how long a page takes. */
+static int gpu(int argc, char **argv) {
+ if (argc < 5 || strcmp(argv[3], "--sizes")) fail("usage: vega-symbols gpu SYMBOLS.vsym --sizes 12,16,32,64 [--frames N]");
+ int frames = argc > 6 && !strcmp(argv[5], "--frames") ? atoi(argv[6]) : 20;
+ if (frames < 1) fail("--frames");
+ char *bytes, error[4096];
+ VegaSymbols s = open_symbols(argv[2], &bytes);
+ gl_context();
+ printf("{\"renderer\":\"%s\"}\n", (const char *)glGetString(GL_RENDERER));
+ VegaGl gl;
+ double started = seconds();
+ if (!vega_gl_open(&gl, &s, error, sizeof(error))) fail(error);
+ glFinish();
+ double open_ms = (seconds() - started) * 1e3;
+ for (const char *p = argv[4]; *p;) {
+ char *end;
+ long size = strtol(p, &end, 10);
+ p = *end == ',' ? end + 1 : end;
+ if (size <= 0 || size > 512) fail("--sizes");
+ double scale = (double)size / s.units;
+ /* Cells that hold any symbol, so none reaches into another's. */
+ int left = 0, bottom = 0, right = 0, top = 0;
+ for (uint32_t i = 0; i < s.symbols; ++i) {
+ VegaSymbol symbol = vega_symbol_at(&s, i);
+ left = symbol.left < left ? symbol.left : left;
+ bottom = symbol.bottom < bottom ? symbol.bottom : bottom;
+ right = symbol.right > right ? symbol.right : right;
+ top = symbol.top > top ? symbol.top : top;
+ }
+ int cell = (int)ceil((right - left > top - bottom ? right - left : top - bottom) * scale) + 4;
+ int across = 4096 / cell, rows = (int)((s.symbols + (uint32_t)across - 1) / (uint32_t)across);
+ if (rows * cell > 4096) rows = 4096 / cell;
+ int width = across * cell, height = rows * cell;
+ uint32_t shown = s.symbols < (uint32_t)(across * rows) ? s.symbols : (uint32_t)(across * rows);
+ VegaGlyph *glyphs = malloc(shown * sizeof(*glyphs));
+ for (uint32_t i = 0; i < shown; ++i)
+ glyphs[i] = (VegaGlyph){(float)(i % (uint32_t)across * (uint32_t)cell) + 2 - (float)(left * scale),
+ (float)(i / (uint32_t)across * (uint32_t)cell) + 2 + (float)(top * scale), (float)scale, i};
+ GLuint texture = gl_target(width, height);
+ vega_gl_draw(&gl, &s, glyphs, shown, width, height);
+ unsigned char *drawn = malloc((size_t)width * (size_t)height), *reference = malloc((size_t)cell * (size_t)cell);
+ glPixelStorei(GL_PACK_ALIGNMENT, 1);
+ glReadPixels(0, 0, width, height, GL_RED, GL_UNSIGNED_BYTE, drawn);
+ double total = 0;
+ uint64_t pixels = 0;
+ int worst = 0;
+ for (uint32_t i = 0; i < shown; ++i) {
+ VegaSymbol symbol = vega_symbol_at(&s, i);
+ int x0 = (int)(i % (uint32_t)across) * cell, y0 = (int)(i / (uint32_t)across) * cell;
+ vega_symbol_raster(&s, &symbol, scale, (x0 - glyphs[i].x) / scale, (glyphs[i].y - y0) / scale, cell, cell, reference);
+ for (int j = 0; j < cell; ++j)
+ for (int k = 0; k < cell; ++k) {
+ /* GL's rows run bottom up */
+ int gpu_value = drawn[(size_t)(height - 1 - (y0 + j)) * (size_t)width + (size_t)(x0 + k)];
+ int difference = abs(gpu_value - reference[j * cell + k]);
+ total += difference;
+ worst = difference > worst ? difference : worst;
+ ++pixels;
+ }
+ }
+ /* Pages: glyphs at their advances in lines, a full target's worth. */
+ int page_width = 1920, page_height = 1080;
+ uint32_t page = 0, capacity = 1 << 16;
+ VegaGlyph *text = malloc(capacity * sizeof(*text));
+ float x = 0, line = (float)size * 1.2f;
+ for (float y = line; y + (float)size * 0.3f < (float)page_height && page < capacity; ) {
+ VegaSymbol symbol = vega_symbol_at(&s, page % s.symbols);
+ float advance = (float)(symbol.advance * scale);
+ if (x + advance > (float)page_width) { x = 0; y += line; continue; }
+ text[page++] = (VegaGlyph){x, y, (float)scale, page % s.symbols};
+ x += advance;
+ }
+ glDeleteTextures(1, &texture);
+ texture = gl_target(page_width, page_height);
+ vega_gl_draw(&gl, &s, text, page, page_width, page_height);
+ glFinish();
+ started = seconds();
+ for (int f = 0; f < frames; ++f) vega_gl_draw(&gl, &s, text, page, page_width, page_height);
+ glFinish();
+ double page_ms = (seconds() - started) / frames * 1e3;
+ printf("{\"pixels_per_em\":%ld,\"symbols\":%u,\"mean_difference\":%.3f,\"worst\":%d,\"page_glyphs\":%u,"
+ "\"page_ms\":%.2f,\"upload_ms\":%.1f}\n", size, shown, pixels ? total / (double)pixels : 0, worst, page, page_ms, open_ms);
+ glDeleteTextures(1, &texture);
+ free(text);
+ free(glyphs);
+ free(drawn);
+ free(reference);
+ }
+ vega_gl_close(&gl);
+ free(bytes);
+ return 0;
+}
+
+int main(int argc, char **argv) {
+ if (argc > 1 && !strcmp(argv[1], "build")) return build(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 ...");
+ return 2;
+}
diff --git a/symbols/symbols.c b/symbols/symbols.c
new file mode 100644
index 0000000..cedd68f
--- /dev/null
+++ b/symbols/symbols.c
@@ -0,0 +1,185 @@
+#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', '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); }
+static uint32_t u32(const unsigned char *p) { return p[0] | p[1] << 8 | (uint32_t)p[2] << 16 | (uint32_t)p[3] << 24; }
+
+VegaSymbol vega_symbol_at(const VegaSymbols *s, uint32_t index) {
+ const unsigned char *p = s->bytes + VEGA_SYMBOLS_HEADER + (size_t)index * VEGA_SYMBOL_BYTES;
+ 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)};
+}
+
+/* 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_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)
+
+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->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 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->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;
+}
+
+bool vega_symbol(const VegaSymbols *s, uint32_t code, VegaSymbol *out) {
+ uint32_t low = 0, high = s->symbols;
+ while (low < high) {
+ uint32_t middle = low + (high - low) / 2;
+ VegaSymbol symbol = vega_symbol_at(s, middle);
+ if (symbol.code == code) { *out = symbol; return true; }
+ if (symbol.code < code) low = middle + 1; else high = middle;
+ }
+ 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;
+ if (fabs(a) < 1e-12) {
+ if (fabs(b) > 1e-12) ts[n++] = -c / b;
+ } else {
+ double d = b * b - 4 * a * c;
+ if (d >= 0) {
+ /* The root that does not cancel, and the other by the product. */
+ double q = -0.5 * (b + copysign(sqrt(d), b));
+ ts[n++] = q / a;
+ if (q != 0) ts[n++] = c / q;
+ }
+ }
+ int kept = 0;
+ for (int i = 0; i < n; ++i) if (ts[i] > 0 && ts[i] < 1) ts[kept++] = ts[i];
+ return kept;
+}
+
+static double clamp01(double v) { return v < 0 ? 0 : v > 1 ? 1 : v; }
+
+/* The curve's share of the pixel [0, 1]^2 (points relative to its lower left
+ * corner, in pixels): the integral of clamp(1 - x, 0, 1) dy along the part
+ * with y in [0, 1]. Over a closed outline these add up to the covered area,
+ * negative for a counterclockwise one (Green's theorem), so the covered area
+ * is exact, as FreeType's is. The curve splits where it crosses the pixel's
+ * sides; each piece lies left of it (dy counts whole), right of it (nothing),
+ * or across it (a cubic in t, integrated in closed form). */
+static double curve_area(double x0, double y0, double x1, double y1, double x2, double y2) {
+ if (fmax(fmax(y0, y1), y2) <= 0 || fmin(fmin(y0, y1), y2) >= 1 || fmin(fmin(x0, x1), x2) >= 1) return 0;
+ if (fmax(fmax(x0, x1), x2) <= 0) return clamp01(y2) - clamp01(y0);
+ /* x(t) = x0 - 2 bx t + ax t^2, and y alike. */
+ double ax = x0 - 2 * x1 + x2, bx = x0 - x1, ay = y0 - 2 * y1 + y2, by = y0 - y1;
+ double ts[10] = {0};
+ int n = 1;
+ n += roots(ay, -2 * by, y0, ts + n);
+ n += roots(ay, -2 * by, y0 - 1, ts + n);
+ n += roots(ax, -2 * bx, x0, ts + n);
+ n += roots(ax, -2 * bx, x0 - 1, ts + n);
+ ts[n++] = 1;
+ for (int i = 1; i < n; ++i)
+ for (int j = i; j > 0 && ts[j] < ts[j - 1]; --j) { double t = ts[j]; ts[j] = ts[j - 1]; ts[j - 1] = t; }
+ /* (1 - x(t)) y'(t) = (u0 + u1 t + u2 t^2)(v0 + v1 t) */
+ double u0 = 1 - x0, u1 = 2 * bx, u2 = -ax, v0 = -2 * by, v1 = 2 * ay;
+ double k1 = u0 * v0, k2 = (u0 * v1 + u1 * v0) / 2, k3 = (u1 * v1 + u2 * v0) / 3, k4 = u2 * v1 / 4, area = 0;
+ for (int i = 0; i + 1 < n; ++i) {
+ double ta = ts[i], tb = ts[i + 1], t = (ta + tb) / 2;
+ if (tb <= ta) continue;
+ double y = (ay * t - 2 * by) * t + y0, x = (ax * t - 2 * bx) * t + x0;
+ if (y <= 0 || y >= 1 || x >= 1) continue;
+ if (x <= 0) area += ((ay * tb - 2 * by) * tb) - ((ay * ta - 2 * by) * ta);
+ else area += (((k4 * tb + k3) * tb + k2) * tb + k1) * tb - (((k4 * ta + k3) * ta + k2) * ta + k1) * ta;
+ }
+ return area;
+}
+
+/* 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 = 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;
+}
+
+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_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/symbols/symbols.h b/symbols/symbols.h
new file mode 100644
index 0000000..998ff3f
--- /dev/null
+++ b/symbols/symbols.h
@@ -0,0 +1,54 @@
+#ifndef VEGA_SYMBOLS_H
+#define VEGA_SYMBOLS_H
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+
+/* 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 {
+ 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;
+typedef struct {
+ const unsigned char *bytes;
+ size_t size;
+ uint16_t units; /* per em */
+ 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
+ * 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);
+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: 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,
+ int height, unsigned char *out);
+#endif
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-20 14:05:56 +0000