lib/filigree/src/font/outline.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const cff = @import("cff.zig");
3 const face_table = @import("face.zig");
4
5 pub const Error = error{
6 InvalidFont,
7 MissingTable,
8 UnsupportedOutline,
9 OutOfMemory,
10 };
11
12 pub const Bounds = struct {
13 x_min: i32 = 0,
14 y_min: i32 = 0,
15 x_max: i32 = 0,
16 y_max: i32 = 0,
17 };
18
19 pub const Point = struct {
20 x: i32,
21 y: i32,
22 on_curve: bool,
23 };
24
25 pub const Contour = struct {
26 start: usize,
27 end: usize,
28 };
29
30 pub const Glyph = struct {
31 bounds: Bounds = .{},
32 contours: []Contour = &.{},
33 points: []Point = &.{},
34
35 pub fn deinit(self: Glyph, allocator: std.mem.Allocator) void {
36 if (self.contours.len > 0) allocator.free(self.contours);
37 if (self.points.len > 0) allocator.free(self.points);
38 }
39 };
40
41 pub fn glyphAlloc(
42 allocator: std.mem.Allocator,
43 face: face_table.Face,
44 glyph_id: u32,
45 ) Error!Glyph {
46 if (glyph_id >= face.num_glyphs) return error.InvalidFont;
47 if (face.tableSlice("glyf") == null or face.tableSlice("loca") == null) {
48 if (face.tableSlice("CFF ") != null) return cffGlyphAlloc(allocator, face, glyph_id);
49 }
50 const head = face.tableSlice("head") orelse return error.MissingTable;
51 const loca = face.tableSlice("loca") orelse return error.MissingTable;
52 const glyf = face.tableSlice("glyf") orelse return error.MissingTable;
53 if (head.len < 52) return error.InvalidFont;
54
55 const loc_format = readI16(head, 50) catch return error.InvalidFont;
56 return glyphAllocFromTables(allocator, loca, glyf, loc_format, glyph_id, 0);
57 }
58
59 fn cffGlyphAlloc(
60 allocator: std.mem.Allocator,
61 face: face_table.Face,
62 glyph_id: u32,
63 ) Error!Glyph {
64 var builder = CffGlyphBuilder.init(allocator);
65 errdefer builder.deinit();
66 try cff.buildGlyph(face, glyph_id, &builder);
67 return try builder.toGlyph();
68 }
69
70 const CffGlyphBuilder = struct {
71 allocator: std.mem.Allocator,
72 contours: std.ArrayListUnmanaged(Contour) = .empty,
73 points: std.ArrayListUnmanaged(Point) = .empty,
74 contour_start: ?usize = null,
75 current_x: i32 = 0,
76 current_y: i32 = 0,
77
78 fn init(allocator: std.mem.Allocator) CffGlyphBuilder {
79 return .{ .allocator = allocator };
80 }
81
82 fn deinit(self: *CffGlyphBuilder) void {
83 self.contours.deinit(self.allocator);
84 self.points.deinit(self.allocator);
85 }
86
87 pub fn moveTo(self: *CffGlyphBuilder, x: i32, y: i32) Error!void {
88 try self.close();
89 self.contour_start = self.points.items.len;
90 try self.points.append(self.allocator, .{ .x = x, .y = y, .on_curve = true });
91 self.current_x = x;
92 self.current_y = y;
93 }
94
95 pub fn lineTo(self: *CffGlyphBuilder, x: i32, y: i32) Error!void {
96 try self.ensureContour();
97 try self.points.append(self.allocator, .{ .x = x, .y = y, .on_curve = true });
98 self.current_x = x;
99 self.current_y = y;
100 }
101
102 pub fn curveTo(self: *CffGlyphBuilder, x1: i32, y1: i32, x2: i32, y2: i32, x3: i32, y3: i32) Error!void {
103 try self.ensureContour();
104 const p0x: f32 = @floatFromInt(self.current_x);
105 const p0y: f32 = @floatFromInt(self.current_y);
106 const p1x: f32 = @floatFromInt(x1);
107 const p1y: f32 = @floatFromInt(y1);
108 const p2x: f32 = @floatFromInt(x2);
109 const p2y: f32 = @floatFromInt(y2);
110 const p3x: f32 = @floatFromInt(x3);
111 const p3y: f32 = @floatFromInt(y3);
112 const steps: usize = 12;
113 for (1..(steps + 1)) |step| {
114 const t = @as(f32, @floatFromInt(step)) / @as(f32, @floatFromInt(steps));
115 const mt = 1.0 - t;
116 const x = mt * mt * mt * p0x + 3.0 * mt * mt * t * p1x + 3.0 * mt * t * t * p2x + t * t * t * p3x;
117 const y = mt * mt * mt * p0y + 3.0 * mt * mt * t * p1y + 3.0 * mt * t * t * p2y + t * t * t * p3y;
118 try self.points.append(self.allocator, .{ .x = roundPoint(x), .y = roundPoint(y), .on_curve = true });
119 }
120 self.current_x = x3;
121 self.current_y = y3;
122 }
123
124 pub fn close(self: *CffGlyphBuilder) Error!void {
125 const start = self.contour_start orelse return;
126 if (self.points.items.len - start >= 3) {
127 try self.contours.append(self.allocator, .{ .start = start, .end = self.points.items.len });
128 } else {
129 self.points.shrinkRetainingCapacity(start);
130 }
131 self.contour_start = null;
132 }
133
134 fn toGlyph(self: *CffGlyphBuilder) Error!Glyph {
135 try self.close();
136 const contours = try self.contours.toOwnedSlice(self.allocator);
137 errdefer self.allocator.free(contours);
138 const points = try self.points.toOwnedSlice(self.allocator);
139 errdefer self.allocator.free(points);
140 return .{
141 .bounds = boundsFor(points),
142 .contours = contours,
143 .points = points,
144 };
145 }
146
147 fn ensureContour(self: *CffGlyphBuilder) Error!void {
148 if (self.contour_start != null) return;
149 try self.moveTo(self.current_x, self.current_y);
150 }
151 };
152
153 fn boundsFor(points: []const Point) Bounds {
154 if (points.len == 0) return .{};
155 var bounds = Bounds{
156 .x_min = points[0].x,
157 .y_min = points[0].y,
158 .x_max = points[0].x,
159 .y_max = points[0].y,
160 };
161 for (points[1..]) |point| {
162 bounds.x_min = @min(bounds.x_min, point.x);
163 bounds.y_min = @min(bounds.y_min, point.y);
164 bounds.x_max = @max(bounds.x_max, point.x);
165 bounds.y_max = @max(bounds.y_max, point.y);
166 }
167 return bounds;
168 }
169
170 fn roundPoint(value: f32) i32 {
171 return @intFromFloat(@round(value));
172 }
173
174 const max_component_depth = 16;
175
176 fn glyphAllocFromTables(
177 allocator: std.mem.Allocator,
178 loca: []const u8,
179 glyf: []const u8,
180 loc_format: i16,
181 glyph_id: u32,
182 depth: usize,
183 ) Error!Glyph {
184 if (depth > max_component_depth) return error.InvalidFont;
185 const range = try glyphRange(loca, glyph_id, loc_format);
186 if (range.start == range.end) return .{};
187 if (range.start > range.end or range.end > glyf.len) return error.InvalidFont;
188 return parseGlyphAlloc(allocator, loca, glyf, loc_format, glyf[range.start..range.end], depth);
189 }
190
191 const GlyphRange = struct {
192 start: usize,
193 end: usize,
194 };
195
196 fn glyphRange(loca: []const u8, glyph_id: u32, loc_format: i16) Error!GlyphRange {
197 const index: usize = @intCast(glyph_id);
198 if (loc_format == 0) {
199 const offset = index * 2;
200 if (offset + 4 > loca.len) return error.InvalidFont;
201 return .{
202 .start = @as(usize, try readU16(loca, offset)) * 2,
203 .end = @as(usize, try readU16(loca, offset + 2)) * 2,
204 };
205 }
206 if (loc_format == 1) {
207 const offset = index * 4;
208 if (offset + 8 > loca.len) return error.InvalidFont;
209 return .{
210 .start = @intCast(try readU32(loca, offset)),
211 .end = @intCast(try readU32(loca, offset + 4)),
212 };
213 }
214 return error.InvalidFont;
215 }
216
217 fn parseGlyphAlloc(
218 allocator: std.mem.Allocator,
219 loca: []const u8,
220 glyf: []const u8,
221 loc_format: i16,
222 data: []const u8,
223 depth: usize,
224 ) Error!Glyph {
225 if (data.len < 10) return error.InvalidFont;
226 const contour_count = try readI16(data, 0);
227 const bounds = Bounds{
228 .x_min = try readI16(data, 2),
229 .y_min = try readI16(data, 4),
230 .x_max = try readI16(data, 6),
231 .y_max = try readI16(data, 8),
232 };
233 if (contour_count < 0) return parseCompositeGlyphAlloc(allocator, loca, glyf, loc_format, data, bounds, depth);
234 if (contour_count == 0) return .{};
235
236 const contour_count_usize: usize = @intCast(contour_count);
237
238 var offset: usize = 10;
239 const contours = try allocator.alloc(Contour, contour_count_usize);
240 errdefer allocator.free(contours);
241
242 var point_count: usize = 0;
243 for (0..contour_count_usize) |contour_index| {
244 const end_point = try readU16(data, offset);
245 offset += 2;
246 const start = point_count;
247 point_count = @as(usize, end_point) + 1;
248 if (point_count < start) return error.InvalidFont;
249 contours[contour_index] = .{ .start = start, .end = point_count };
250 }
251
252 const instruction_len = try readU16(data, offset);
253 offset += 2;
254 if (offset + instruction_len > data.len) return error.InvalidFont;
255 offset += instruction_len;
256
257 const flags = try allocator.alloc(u8, point_count);
258 defer allocator.free(flags);
259 var flag_count: usize = 0;
260 while (flag_count < point_count) {
261 if (offset >= data.len) return error.InvalidFont;
262 const flag = data[offset];
263 offset += 1;
264 var repeat_count: usize = 1;
265 if ((flag & 0x08) != 0) {
266 if (offset >= data.len) return error.InvalidFont;
267 repeat_count += data[offset];
268 offset += 1;
269 }
270 if (flag_count + repeat_count > point_count) return error.InvalidFont;
271 @memset(flags[flag_count..][0..repeat_count], flag);
272 flag_count += repeat_count;
273 }
274
275 const points = try allocator.alloc(Point, point_count);
276 errdefer allocator.free(points);
277 for (flags, points) |flag, *point| {
278 point.* = .{ .x = 0, .y = 0, .on_curve = (flag & 0x01) != 0 };
279 }
280
281 var x: i32 = 0;
282 for (flags, points) |flag, *point| {
283 const delta: i32 = if ((flag & 0x02) != 0) delta: {
284 if (offset >= data.len) return error.InvalidFont;
285 const value: i32 = data[offset];
286 offset += 1;
287 break :delta if ((flag & 0x10) != 0) value else -value;
288 } else if ((flag & 0x10) != 0)
289 0
290 else delta: {
291 const value = try readI16(data, offset);
292 offset += 2;
293 break :delta value;
294 };
295 x += delta;
296 point.x = x;
297 }
298
299 var y: i32 = 0;
300 for (flags, points) |flag, *point| {
301 const delta: i32 = if ((flag & 0x04) != 0) delta: {
302 if (offset >= data.len) return error.InvalidFont;
303 const value: i32 = data[offset];
304 offset += 1;
305 break :delta if ((flag & 0x20) != 0) value else -value;
306 } else if ((flag & 0x20) != 0)
307 0
308 else delta: {
309 const value = try readI16(data, offset);
310 offset += 2;
311 break :delta value;
312 };
313 y += delta;
314 point.y = y;
315 }
316
317 return .{
318 .bounds = bounds,
319 .contours = contours,
320 .points = points,
321 };
322 }
323
324 const component_arg_words = 0x0001;
325 const component_args_xy = 0x0002;
326 const component_has_scale = 0x0008;
327 const component_more = 0x0020;
328 const component_has_xy_scale = 0x0040;
329 const component_has_2x2 = 0x0080;
330 const component_has_instructions = 0x0100;
331
332 const ComponentTransform = struct {
333 xx: f32 = 1,
334 yx: f32 = 0,
335 xy: f32 = 0,
336 yy: f32 = 1,
337 dx: i32 = 0,
338 dy: i32 = 0,
339
340 fn apply(self: ComponentTransform, point: Point) Point {
341 const x: f32 = @floatFromInt(point.x);
342 const y: f32 = @floatFromInt(point.y);
343 return .{
344 .x = roundTransformed(self.xx * x + self.xy * y + @as(f32, @floatFromInt(self.dx))),
345 .y = roundTransformed(self.yx * x + self.yy * y + @as(f32, @floatFromInt(self.dy))),
346 .on_curve = point.on_curve,
347 };
348 }
349 };
350
351 fn parseCompositeGlyphAlloc(
352 allocator: std.mem.Allocator,
353 loca: []const u8,
354 glyf: []const u8,
355 loc_format: i16,
356 data: []const u8,
357 bounds: Bounds,
358 depth: usize,
359 ) Error!Glyph {
360 var contours = std.ArrayListUnmanaged(Contour).empty;
361 errdefer contours.deinit(allocator);
362 var points = std.ArrayListUnmanaged(Point).empty;
363 errdefer points.deinit(allocator);
364
365 var offset: usize = 10;
366 var flags: u16 = component_more;
367 while ((flags & component_more) != 0) {
368 if (offset + 4 > data.len) return error.InvalidFont;
369 flags = try readU16(data, offset);
370 const component_glyph_id = try readU16(data, offset + 2);
371 offset += 4;
372
373 var transform = ComponentTransform{};
374 if ((flags & component_arg_words) != 0) {
375 if (offset + 4 > data.len) return error.InvalidFont;
376 transform.dx = try readI16(data, offset);
377 transform.dy = try readI16(data, offset + 2);
378 offset += 4;
379 } else {
380 if (offset + 2 > data.len) return error.InvalidFont;
381 transform.dx = try readI8(data, offset);
382 transform.dy = try readI8(data, offset + 1);
383 offset += 2;
384 }
385 if ((flags & component_args_xy) == 0) return error.UnsupportedOutline;
386
387 if ((flags & component_has_scale) != 0) {
388 if (offset + 2 > data.len) return error.InvalidFont;
389 const scale = try readF2Dot14(data, offset);
390 transform.xx = scale;
391 transform.yy = scale;
392 offset += 2;
393 } else if ((flags & component_has_xy_scale) != 0) {
394 if (offset + 4 > data.len) return error.InvalidFont;
395 transform.xx = try readF2Dot14(data, offset);
396 transform.yy = try readF2Dot14(data, offset + 2);
397 offset += 4;
398 } else if ((flags & component_has_2x2) != 0) {
399 if (offset + 8 > data.len) return error.InvalidFont;
400 transform.xx = try readF2Dot14(data, offset);
401 transform.yx = try readF2Dot14(data, offset + 2);
402 transform.xy = try readF2Dot14(data, offset + 4);
403 transform.yy = try readF2Dot14(data, offset + 6);
404 offset += 8;
405 }
406
407 var component = try glyphAllocFromTables(allocator, loca, glyf, loc_format, component_glyph_id, depth + 1);
408 defer component.deinit(allocator);
409 try appendComponent(allocator, &contours, &points, component, transform);
410 }
411
412 if ((flags & component_has_instructions) != 0) {
413 const instruction_len = try readU16(data, offset);
414 offset += 2;
415 if (offset + instruction_len > data.len) return error.InvalidFont;
416 }
417
418 const owned_contours = try contours.toOwnedSlice(allocator);
419 errdefer allocator.free(owned_contours);
420 const owned_points = try points.toOwnedSlice(allocator);
421 return .{
422 .bounds = bounds,
423 .contours = owned_contours,
424 .points = owned_points,
425 };
426 }
427
428 fn appendComponent(
429 allocator: std.mem.Allocator,
430 contours: *std.ArrayListUnmanaged(Contour),
431 points: *std.ArrayListUnmanaged(Point),
432 component: Glyph,
433 transform: ComponentTransform,
434 ) Error!void {
435 const point_offset = points.items.len;
436 try points.ensureUnusedCapacity(allocator, component.points.len);
437 for (component.points) |point| {
438 points.appendAssumeCapacity(transform.apply(point));
439 }
440 try contours.ensureUnusedCapacity(allocator, component.contours.len);
441 for (component.contours) |contour| {
442 contours.appendAssumeCapacity(.{
443 .start = point_offset + contour.start,
444 .end = point_offset + contour.end,
445 });
446 }
447 }
448
449 fn readI8(data: []const u8, offset: usize) Error!i8 {
450 if (offset >= data.len) return error.InvalidFont;
451 return @bitCast(data[offset]);
452 }
453
454 fn readF2Dot14(data: []const u8, offset: usize) Error!f32 {
455 const raw = try readI16(data, offset);
456 return @as(f32, @floatFromInt(raw)) / 16384.0;
457 }
458
459 fn roundTransformed(value: f32) i32 {
460 return @intFromFloat(@round(value));
461 }
462
463 fn readU16(data: []const u8, offset: usize) Error!u16 {
464 if (offset + 2 > data.len) return error.InvalidFont;
465 return std.mem.readInt(u16, data[offset..][0..2], .big);
466 }
467
468 fn readI16(data: []const u8, offset: usize) Error!i16 {
469 return @bitCast(try readU16(data, offset));
470 }
471
472 fn readU32(data: []const u8, offset: usize) Error!u32 {
473 if (offset + 4 > data.len) return error.InvalidFont;
474 return std.mem.readInt(u32, data[offset..][0..4], .big);
475 }
476
477 test "outline loads simple fixture glyph" {
478 const fixtures = @import("../fixture/root.zig");
479 const allocator = std.testing.allocator;
480 const bytes = try fixtures.createWithOutlines(allocator);
481 defer allocator.free(bytes);
482
483 const face = try face_table.Face.init(bytes);
484 const glyph = try glyphAlloc(allocator, face, face.glyphId('A'));
485 defer glyph.deinit(allocator);
486
487 try std.testing.expectEqual(Bounds{ .x_min = 50, .y_min = 0, .x_max = 450, .y_max = 700 }, glyph.bounds);
488 try std.testing.expectEqual(@as(usize, 1), glyph.contours.len);
489 try std.testing.expectEqual(Contour{ .start = 0, .end = 4 }, glyph.contours[0]);
490 try std.testing.expectEqual(@as(usize, 4), glyph.points.len);
491 try std.testing.expectEqual(Point{ .x = 50, .y = 0, .on_curve = true }, glyph.points[0]);
492 try std.testing.expectEqual(Point{ .x = 450, .y = 700, .on_curve = true }, glyph.points[2]);
493 }
494
495 test "outline reports empty fixture glyphs" {
496 const fixtures = @import("../fixture/root.zig");
497 const allocator = std.testing.allocator;
498 const bytes = try fixtures.createWithOutlines(allocator);
499 defer allocator.free(bytes);
500
501 const face = try face_table.Face.init(bytes);
502 const glyph = try glyphAlloc(allocator, face, face.glyphId('C'));
503 defer glyph.deinit(allocator);
504
505 try std.testing.expectEqual(@as(usize, 0), glyph.contours.len);
506 try std.testing.expectEqual(@as(usize, 0), glyph.points.len);
507 }
508
509 test "outline loads composite fixture glyph" {
510 const fixtures = @import("../fixture/root.zig");
511 const allocator = std.testing.allocator;
512 const bytes = try fixtures.createWithOutlines(allocator);
513 defer allocator.free(bytes);
514
515 const face = try face_table.Face.init(bytes);
516 const glyph = try glyphAlloc(allocator, face, face.glyphId('i'));
517 defer glyph.deinit(allocator);
518
519 try std.testing.expectEqual(Bounds{ .x_min = 50, .y_min = 0, .x_max = 950, .y_max = 700 }, glyph.bounds);
520 try std.testing.expectEqual(@as(usize, 2), glyph.contours.len);
521 try std.testing.expectEqual(Contour{ .start = 0, .end = 4 }, glyph.contours[0]);
522 try std.testing.expectEqual(Contour{ .start = 4, .end = 8 }, glyph.contours[1]);
523 try std.testing.expectEqual(@as(usize, 8), glyph.points.len);
524 try std.testing.expectEqual(Point{ .x = 550, .y = 0, .on_curve = true }, glyph.points[4]);
525 try std.testing.expectEqual(Point{ .x = 950, .y = 700, .on_curve = true }, glyph.points[6]);
526 }
527
528 test "outline loads CFF fixture glyph" {
529 const fixtures = @import("../fixture/root.zig");
530 const allocator = std.testing.allocator;
531 const bytes = try fixtures.createWithCffOutlines(allocator);
532 defer allocator.free(bytes);
533
534 const face = try face_table.Face.init(bytes);
535 const glyph = try glyphAlloc(allocator, face, face.glyphId('A'));
536 defer glyph.deinit(allocator);
537
538 try std.testing.expectEqual(Bounds{ .x_min = 50, .y_min = 0, .x_max = 450, .y_max = 700 }, glyph.bounds);
539 try std.testing.expectEqual(@as(usize, 1), glyph.contours.len);
540 try std.testing.expectEqual(@as(usize, 4), glyph.points.len);
541 try std.testing.expectEqual(Point{ .x = 50, .y = 0, .on_curve = true }, glyph.points[0]);
542 try std.testing.expectEqual(Point{ .x = 450, .y = 700, .on_curve = true }, glyph.points[2]);
543 }