lib/filigree/src/layout/coverage.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 const binary = @import("binary.zig");
4 const LayoutError = binary.LayoutError;
5 const hasBytes = binary.hasBytes;
6 const readU16 = binary.readU16;
7
8 pub const Coverage = union(enum) {
9 format_1: CoverageFormat1,
10 format_2: CoverageFormat2,
11
12 pub fn init(data: []const u8, offset: usize) LayoutError!Coverage {
13 if (!hasBytes(data, offset, 2)) return error.InvalidLayout;
14 return switch (try readU16(data, offset)) {
15 1 => .{ .format_1 = try CoverageFormat1.init(data, offset) },
16 2 => .{ .format_2 = try CoverageFormat2.init(data, offset) },
17 else => error.UnsupportedCoverage,
18 };
19 }
20
21 pub fn index(self: Coverage, data: []const u8, glyph_id: u32) LayoutError!?u16 {
22 return switch (self) {
23 .format_1 => |format| format.index(data, glyph_id),
24 .format_2 => |format| format.index(data, glyph_id),
25 };
26 }
27 };
28
29 pub const CoverageFormat1 = struct {
30 glyph_array_offset: usize,
31 glyph_count: u16,
32
33 fn init(data: []const u8, offset: usize) LayoutError!CoverageFormat1 {
34 if (!hasBytes(data, offset, 4)) return error.InvalidLayout;
35 const glyph_count = try readU16(data, offset + 2);
36 const array_offset = offset + 4;
37 const array_len = @as(usize, glyph_count) * 2;
38 if (!hasBytes(data, array_offset, array_len)) return error.InvalidLayout;
39 var previous: ?u16 = null;
40 for (0..glyph_count) |i| {
41 const glyph = try readU16(data, array_offset + i * 2);
42 if (previous) |seen| {
43 if (glyph <= seen) return error.InvalidLayout;
44 }
45 previous = glyph;
46 }
47 return .{
48 .glyph_array_offset = array_offset,
49 .glyph_count = glyph_count,
50 };
51 }
52
53 fn index(self: CoverageFormat1, data: []const u8, glyph_id: u32) LayoutError!?u16 {
54 if (glyph_id > std.math.maxInt(u16)) return null;
55 const glyph: u16 = @intCast(glyph_id);
56 var left: usize = 0;
57 var right: usize = self.glyph_count;
58 while (left < right) {
59 const mid = left + (right - left) / 2;
60 const candidate = try readU16(data, self.glyph_array_offset + mid * 2);
61 if (glyph < candidate) {
62 right = mid;
63 } else if (glyph > candidate) {
64 left = mid + 1;
65 } else {
66 return @intCast(mid);
67 }
68 }
69 return null;
70 }
71 };
72
73 pub const CoverageFormat2 = struct {
74 range_array_offset: usize,
75 range_count: u16,
76
77 fn init(data: []const u8, offset: usize) LayoutError!CoverageFormat2 {
78 if (!hasBytes(data, offset, 4)) return error.InvalidLayout;
79 const range_count = try readU16(data, offset + 2);
80 const array_offset = offset + 4;
81 const array_len = @as(usize, range_count) * 6;
82 if (!hasBytes(data, array_offset, array_len)) return error.InvalidLayout;
83 var previous_end: ?u16 = null;
84 for (0..range_count) |i| {
85 const record = array_offset + i * 6;
86 const start = try readU16(data, record);
87 const end = try readU16(data, record + 2);
88 if (start > end) return error.InvalidLayout;
89 if (previous_end) |seen| {
90 if (start <= seen) return error.InvalidLayout;
91 }
92 previous_end = end;
93 }
94 return .{
95 .range_array_offset = array_offset,
96 .range_count = range_count,
97 };
98 }
99
100 fn index(self: CoverageFormat2, data: []const u8, glyph_id: u32) LayoutError!?u16 {
101 if (glyph_id > std.math.maxInt(u16)) return null;
102 const glyph: u16 = @intCast(glyph_id);
103 var left: usize = 0;
104 var right: usize = self.range_count;
105 while (left < right) {
106 const mid = left + (right - left) / 2;
107 const record = self.range_array_offset + mid * 6;
108 const start = try readU16(data, record);
109 const end = try readU16(data, record + 2);
110 if (glyph < start) {
111 right = mid;
112 } else if (glyph > end) {
113 left = mid + 1;
114 } else {
115 const start_index = try readU16(data, record + 4);
116 const delta = glyph - start;
117 if (start_index > std.math.maxInt(u16) - delta) return error.InvalidLayout;
118 return start_index + delta;
119 }
120 }
121 return null;
122 }
123 };
124
125 test "Coverage format 1 maps sorted glyph array to indexes" {
126 const data = [_]u8{
127 0, 1,
128 0, 3,
129 0, 5,
130 0, 9,
131 0, 20,
132 };
133 const coverage = try Coverage.init(&data, 0);
134 try std.testing.expectEqual(@as(?u16, 0), try coverage.index(&data, 5));
135 try std.testing.expectEqual(@as(?u16, 1), try coverage.index(&data, 9));
136 try std.testing.expectEqual(@as(?u16, 2), try coverage.index(&data, 20));
137 try std.testing.expectEqual(@as(?u16, null), try coverage.index(&data, 6));
138 try std.testing.expectEqual(@as(?u16, null), try coverage.index(&data, 0x1_0000));
139 }
140
141 test "Coverage format 1 rejects unsorted glyph array" {
142 const data = [_]u8{
143 0, 1,
144 0, 2,
145 0, 7,
146 0, 7,
147 };
148 try std.testing.expectError(error.InvalidLayout, Coverage.init(&data, 0));
149 }
150
151 test "Coverage format 2 maps glyph ranges to indexes" {
152 const data = [_]u8{
153 0, 2,
154 0, 2,
155 0, 10,
156 0, 12,
157 0, 0,
158 0, 20,
159 0, 21,
160 0, 3,
161 };
162 const coverage = try Coverage.init(&data, 0);
163 try std.testing.expectEqual(@as(?u16, 0), try coverage.index(&data, 10));
164 try std.testing.expectEqual(@as(?u16, 2), try coverage.index(&data, 12));
165 try std.testing.expectEqual(@as(?u16, 3), try coverage.index(&data, 20));
166 try std.testing.expectEqual(@as(?u16, 4), try coverage.index(&data, 21));
167 try std.testing.expectEqual(@as(?u16, null), try coverage.index(&data, 13));
168 }
169
170 test "Coverage format 2 rejects overlapping ranges" {
171 const data = [_]u8{
172 0, 2,
173 0, 2,
174 0, 10,
175 0, 12,
176 0, 0,
177 0, 12,
178 0, 14,
179 0, 3,
180 };
181 try std.testing.expectError(error.InvalidLayout, Coverage.init(&data, 0));
182 }
183
184 test "Coverage honors nonzero table offsets" {
185 const data = [_]u8{
186 0xaa, 0xbb,
187 0, 1,
188 0, 1,
189 0, 42,
190 };
191 const coverage = try Coverage.init(&data, 2);
192 try std.testing.expectEqual(@as(?u16, 0), try coverage.index(&data, 42));
193 }