Skip to main content

max / quasi-type

19.5 KB · 565 lines History Blame Raw
1 //! A proof sheet: the built face rasterised, so a shape can be looked at.
2 //!
3 //! Every assertion in this repo measures a bounding box or an ink area, and
4 //! three real defects have already walked past all of them — arcs curling the
5 //! wrong way, a dashed glyph drawn as two arms with a seam, and an up-down
6 //! arrow whose heads met in the middle and read as a bowtie. Each had a correct
7 //! bbox. So the last check is a person looking at the glyph, and this is what
8 //! gives them something to look at without installing the face first.
9 //!
10 //! Deliberately no image dependency. A grayscale PNG is a signature, three
11 //! chunks and a zlib stream, and the stream may be stored blocks, so the whole
12 //! encoder is under a hundred lines and adds nothing to the dependency tree of
13 //! a pipeline whose whole point is being reproducible from a checkout.
14
15 use std::collections::BTreeMap;
16
17 use read_fonts::types::GlyphId;
18 use read_fonts::{FontRef, TableProvider};
19 use skrifa::MetadataProvider;
20 use skrifa::instance::Size;
21
22 use crate::Error;
23 use crate::compose;
24
25 /// Cell rules are the lightest thing on the page, so the ink reads over them.
26 const PAPER: u8 = 0xff;
27 const RULE: u8 = 0xdc;
28 const BASELINE: u8 = 0xc0;
29
30 /// One rasterised page.
31 pub struct Sheet {
32 pub width: usize,
33 pub height: usize,
34 pixels: Vec<u8>,
35 }
36
37 impl Sheet {
38 fn new(width: usize, height: usize) -> Self {
39 Self {
40 width,
41 height,
42 pixels: vec![PAPER; width * height],
43 }
44 }
45
46 /// How many pixels carry ink darker than the cell rules, which is the
47 /// question "did this glyph draw anything" in the form a sheet can answer.
48 pub fn ink(&self) -> usize {
49 self.pixels.iter().filter(|&&p| p < BASELINE).count()
50 }
51
52 fn darken(&mut self, x: usize, y: usize, value: u8) {
53 if x < self.width && y < self.height {
54 let at = y * self.width + x;
55 self.pixels[at] = self.pixels[at].min(value);
56 }
57 }
58
59 fn rule_v(&mut self, x: usize, y0: usize, y1: usize, value: u8) {
60 for y in y0..y1 {
61 self.darken(x, y, value);
62 }
63 }
64
65 fn rule_h(&mut self, y: usize, x0: usize, x1: usize, value: u8) {
66 for x in x0..x1 {
67 self.darken(x, y, value);
68 }
69 }
70 }
71
72 /// What to draw, in the order it is drawn.
73 ///
74 /// A row is a run of codepoints set adjacently on the cell grid, which is the
75 /// arrangement that shows a seam: box drawing that does not tile leaves a gap
76 /// between two cells, and no single-glyph rendering can show that.
77 pub struct Page {
78 pub rows: Vec<Vec<u32>>,
79 pub px: f32,
80 pub wght: Option<f32>,
81 }
82
83 /// The rows a proof of the house set wants: the authored marks one per cell,
84 /// then the cell furniture set adjacently so its seams show.
85 pub fn house_rows(covered: &BTreeMap<u32, GlyphId>) -> Vec<Vec<u32>> {
86 let present = |row: Vec<u32>| -> Vec<u32> {
87 row.into_iter()
88 .filter(|c| covered.contains_key(c))
89 .collect()
90 };
91 let mut rows = vec![
92 // The authored marks, beside the base's own glyphs they were fitted
93 // against: the X against `x`, the triangles against `+`, the whitespace
94 // renders among lowercase, which is where helix draws them.
95 present(vec![
96 0x25B2, 0x25BC, 0x25B8, 0x25C2, 0x2718, 0x2423, 0x23CE, 0x2191, 0x2193, 0x2192, 0x2195,
97 ]),
98 // The runs, each set beside its own siblings: four arrows that have to
99 // read as one set, and six triangles that have to read as two sizes of
100 // one drawing rather than as six drawings.
101 present(vec![
102 0x2190, 0x2192, 0x2191, 0x2193, 0x2195, 0x0020, 0x25B2, 0x25BC, 0x25B6, 0x25C4, 0x25BA,
103 0x25BE, 0x25B8, 0x25C2,
104 ]),
105 present(vec![
106 0x0078, 0x00D7, 0x2718, 0x002B, 0x25B2, 0x003D, 0x2423, 0x0061, 0x0062, 0x0063, 0x23CE,
107 ]),
108 ];
109
110 // Box drawing, tiled. Three boxes side by side in light, heavy and double,
111 // which is where a wrong arm or a seam shows up at once.
112 for weights in [
113 [0x250C, 0x2500, 0x252C, 0x2510, 0x2502, 0x2524],
114 [0x250F, 0x2501, 0x2533, 0x2513, 0x2503, 0x252B],
115 [0x2554, 0x2550, 0x2566, 0x2557, 0x2551, 0x2563],
116 ] {
117 let [tl, h, t, tr, v, r] = weights;
118 rows.push(present(vec![tl, h, t, h, tr, 0x0020, v, 0x0020, v, r]));
119 }
120 rows.push(present(vec![
121 0x2514, 0x2500, 0x2534, 0x2500, 0x2518, 0x0020, 0x2517, 0x2501, 0x251B,
122 ]));
123 // Arcs and dashes, the two that were drawn wrong and passed their tests.
124 rows.push(present(vec![
125 0x256D, 0x2500, 0x256E, 0x0020, 0x2570, 0x2500, 0x256F, 0x0020, 0x2504, 0x2505, 0x2508,
126 ]));
127 // Block elements: a full cell run, the eighths in order, and the shades.
128 rows.push(present(vec![
129 0x2588, 0x2588, 0x2588, 0x0020, 0x2580, 0x2584, 0x2580, 0x2584, 0x0020, 0x2591, 0x2592,
130 0x2593,
131 ]));
132 rows.push(present(vec![
133 0x258F, 0x258E, 0x258D, 0x258C, 0x258B, 0x258A, 0x2589, 0x2588, 0x0020, 0x2596, 0x2597,
134 0x2598, 0x259D,
135 ]));
136 // A row that lost every glyph but its spaces is a row the face does not
137 // carry — a body slot takes no cell furniture, so its box-drawing rows come
138 // back blank rather than absent.
139 rows.retain(|row| row.iter().any(|&c| c != 0x0020));
140 rows
141 }
142
143 /// Rasterise one page of a face.
144 ///
145 /// `wght` is a location on the axis for a variable face and is ignored by a
146 /// static one.
147 ///
148 /// Glyphs are set on a grid of the face's widest advance rounded to whole
149 /// pixels, which for a monospace face is the cell a terminal lays out with — so
150 /// furniture that only tiles at its exact design size shows its seam here the
151 /// same way it would on a screen. For a proportional face the grid is a
152 /// specimen layout and nothing more: its glyphs carry their own widths and the
153 /// sheet is not a text setting.
154 pub fn render(bytes: &[u8], page: &Page) -> Result<Sheet, Error> {
155 let font = FontRef::new(bytes).map_err(|e| Error::Font(e.to_string()))?;
156 let coverage = compose::coverage(bytes)?;
157 let upem = f32::from(
158 font.head()
159 .map_err(|e| Error::Font(e.to_string()))?
160 .units_per_em(),
161 );
162 let hhea = font.hhea().map_err(|e| Error::Font(e.to_string()))?;
163 let ascent = f32::from(i16::from(hhea.ascender()));
164 let descent = f32::from(i16::from(hhea.descender()));
165
166 let scale = page.px / upem;
167 let advance = {
168 let hmtx = font.hmtx().map_err(|e| Error::Font(e.to_string()))?;
169 let widest = hmtx
170 .h_metrics()
171 .last()
172 .map_or(upem / 2.0, |m| f32::from(m.advance()));
173 (widest * scale).round().max(1.0)
174 };
175 let cell_h = ((ascent - descent) * scale).round().max(1.0);
176 let baseline = (ascent * scale).round();
177
178 let cols = page.rows.iter().map(Vec::len).max().unwrap_or(1);
179 let pad = (page.px * 0.5).round().max(4.0);
180 let width = (advance * cols as f32 + pad * 2.0) as usize;
181 let height = (cell_h * page.rows.len() as f32 + pad * 2.0) as usize;
182 let mut sheet = Sheet::new(width, height);
183
184 // A static face has no axes, so an empty location is its only location and
185 // asking for `wght` on one is answered rather than refused.
186 let location = font
187 .axes()
188 .location(page.wght.map(|w| ("wght", w)).as_slice());
189
190 for (r, row) in page.rows.iter().enumerate() {
191 let top = pad + cell_h * r as f32;
192 // The cell rules, under the ink: a glyph that overruns its cell or sits
193 // off the baseline says so against them.
194 sheet.rule_h(top as usize, pad as usize, width - pad as usize, RULE);
195 sheet.rule_h(
196 (top + baseline) as usize,
197 pad as usize,
198 width - pad as usize,
199 BASELINE,
200 );
201 for c in 0..=row.len() {
202 sheet.rule_v(
203 (pad + advance * c as f32) as usize,
204 top as usize,
205 (top + cell_h) as usize,
206 RULE,
207 );
208 }
209 for (c, codepoint) in row.iter().enumerate() {
210 let Some(gid) = coverage.get(codepoint) else {
211 continue;
212 };
213 let origin = (pad + advance * c as f32, top + baseline);
214 draw_glyph(&mut sheet, &font, *gid, &location, scale, origin)?;
215 }
216 }
217 Ok(sheet)
218 }
219
220 /// Fill one glyph, 3x3 supersampled.
221 fn draw_glyph(
222 sheet: &mut Sheet,
223 font: &FontRef,
224 gid: GlyphId,
225 location: &skrifa::instance::Location,
226 scale: f32,
227 origin: (f32, f32),
228 ) -> Result<(), Error> {
229 let mut pen = Flatten {
230 scale,
231 origin,
232 ..Flatten::default()
233 };
234 font.outline_glyphs()
235 .get(gid)
236 .ok_or_else(|| Error::Font(format!("glyph {gid} has no outline")))?
237 .draw(
238 skrifa::outline::DrawSettings::unhinted(Size::unscaled(), location),
239 &mut pen,
240 )
241 .map_err(|e| Error::Font(e.to_string()))?;
242 pen.close_open();
243 fill(sheet, &pen.edges);
244 Ok(())
245 }
246
247 /// Nonzero-winding scanline fill over straight edges, three samples per pixel
248 /// in each axis. Coverage is the share of the nine samples inside the outline,
249 /// which is enough to judge a shape and far short of a hinted rasteriser.
250 fn fill(sheet: &mut Sheet, edges: &[(f32, f32, f32, f32)]) {
251 if edges.is_empty() {
252 return;
253 }
254 const SUB: usize = 3;
255 let step = 1.0 / SUB as f32;
256 let (mut y0, mut y1) = (f32::MAX, f32::MIN);
257 let (mut x0, mut x1) = (f32::MAX, f32::MIN);
258 for &(ax, ay, bx, by) in edges {
259 y0 = y0.min(ay).min(by);
260 y1 = y1.max(ay).max(by);
261 x0 = x0.min(ax).min(bx);
262 x1 = x1.max(ax).max(bx);
263 }
264 let row0 = y0.floor().max(0.0) as usize;
265 let row1 = (y1.ceil() as usize).min(sheet.height);
266 let col0 = x0.floor().max(0.0) as usize;
267 let col1 = (x1.ceil() as usize).min(sheet.width);
268 if row0 >= row1 || col0 >= col1 {
269 return;
270 }
271
272 let mut coverage = vec![0u8; (col1 - col0) * (row1 - row0)];
273 let mut crossings: Vec<(f32, i32)> = Vec::new();
274 for row in row0..row1 {
275 for sy in 0..SUB {
276 let y = row as f32 + (sy as f32 + 0.5) * step;
277 crossings.clear();
278 for &(ax, ay, bx, by) in edges {
279 if (ay <= y) == (by <= y) {
280 continue;
281 }
282 let t = (y - ay) / (by - ay);
283 crossings.push((ax + t * (bx - ax), if by > ay { 1 } else { -1 }));
284 }
285 if crossings.len() < 2 {
286 continue;
287 }
288 crossings.sort_by(|a, b| a.0.total_cmp(&b.0));
289 let mut winding = 0;
290 for pair in crossings.windows(2) {
291 winding += pair[0].1;
292 if winding == 0 {
293 continue;
294 }
295 let (span0, span1) = (pair[0].0, pair[1].0);
296 for col in col0..col1 {
297 for sx in 0..SUB {
298 let x = col as f32 + (sx as f32 + 0.5) * step;
299 if x >= span0 && x < span1 {
300 coverage[(row - row0) * (col1 - col0) + (col - col0)] += 1;
301 }
302 }
303 }
304 }
305 }
306 }
307 for row in row0..row1 {
308 for col in col0..col1 {
309 let hits = coverage[(row - row0) * (col1 - col0) + (col - col0)];
310 if hits > 0 {
311 let value = PAPER as f32 * (1.0 - f32::from(hits) / (SUB * SUB) as f32);
312 sheet.darken(col, row, value.round() as u8);
313 }
314 }
315 }
316 }
317
318 /// Flattens an outline into straight edges in device space, y down.
319 #[derive(Default)]
320 struct Flatten {
321 scale: f32,
322 origin: (f32, f32),
323 edges: Vec<(f32, f32, f32, f32)>,
324 start: (f32, f32),
325 at: (f32, f32),
326 }
327
328 impl Flatten {
329 fn map(&self, x: f32, y: f32) -> (f32, f32) {
330 (
331 self.origin.0 + x * self.scale,
332 self.origin.1 - y * self.scale,
333 )
334 }
335
336 fn edge(&mut self, to: (f32, f32)) {
337 self.edges.push((self.at.0, self.at.1, to.0, to.1));
338 self.at = to;
339 }
340
341 /// Curves are flattened by subdivision. The house marks are all
342 /// straight-edged, but a base's own glyphs are not and the sheet sets them
343 /// beside the marks on purpose.
344 fn curve(&mut self, points: &[(f32, f32)]) {
345 const STEPS: usize = 16;
346 let from = self.at;
347 for step in 1..=STEPS {
348 let t = step as f32 / STEPS as f32;
349 let mut work: Vec<(f32, f32)> = std::iter::once(from)
350 .chain(points.iter().copied())
351 .collect();
352 while work.len() > 1 {
353 for i in 0..work.len() - 1 {
354 work[i] = (
355 work[i].0 + (work[i + 1].0 - work[i].0) * t,
356 work[i].1 + (work[i + 1].1 - work[i].1) * t,
357 );
358 }
359 work.pop();
360 }
361 self.edge(work[0]);
362 }
363 }
364
365 fn close_open(&mut self) {
366 if self.at != self.start {
367 let start = self.start;
368 self.edge(start);
369 }
370 }
371 }
372
373 impl skrifa::outline::OutlinePen for Flatten {
374 fn move_to(&mut self, x: f32, y: f32) {
375 self.close_open();
376 let to = self.map(x, y);
377 self.start = to;
378 self.at = to;
379 }
380
381 fn line_to(&mut self, x: f32, y: f32) {
382 let to = self.map(x, y);
383 self.edge(to);
384 }
385
386 fn quad_to(&mut self, cx: f32, cy: f32, x: f32, y: f32) {
387 let c = self.map(cx, cy);
388 let to = self.map(x, y);
389 self.curve(&[c, to]);
390 }
391
392 fn curve_to(&mut self, cx0: f32, cy0: f32, cx1: f32, cy1: f32, x: f32, y: f32) {
393 let c0 = self.map(cx0, cy0);
394 let c1 = self.map(cx1, cy1);
395 let to = self.map(x, y);
396 self.curve(&[c0, c1, to]);
397 }
398
399 fn close(&mut self) {
400 self.close_open();
401 }
402 }
403
404 /// Encode a grayscale sheet as a PNG.
405 ///
406 /// Stored deflate blocks rather than a compressor: the file is a build artifact
407 /// somebody looks at once, and a stored stream is a correct zlib stream that
408 /// costs no dependency.
409 pub fn png(sheet: &Sheet) -> Vec<u8> {
410 let mut raw = Vec::with_capacity((sheet.width + 1) * sheet.height);
411 for row in sheet.pixels.chunks(sheet.width) {
412 raw.push(0); // filter: none
413 raw.extend_from_slice(row);
414 }
415
416 let mut out = Vec::new();
417 out.extend_from_slice(&[0x89, b'P', b'N', b'G', 0x0d, 0x0a, 0x1a, 0x0a]);
418
419 let mut ihdr = Vec::new();
420 ihdr.extend_from_slice(&(sheet.width as u32).to_be_bytes());
421 ihdr.extend_from_slice(&(sheet.height as u32).to_be_bytes());
422 ihdr.extend_from_slice(&[8, 0, 0, 0, 0]); // 8-bit grayscale, no interlace
423 chunk(&mut out, *b"IHDR", &ihdr);
424
425 let mut zlib = vec![0x78, 0x01];
426 for (i, block) in raw.chunks(0xffff).enumerate() {
427 let last = u8::from((i + 1) * 0xffff >= raw.len());
428 zlib.push(last);
429 zlib.extend_from_slice(&(block.len() as u16).to_le_bytes());
430 zlib.extend_from_slice(&(!(block.len() as u16)).to_le_bytes());
431 zlib.extend_from_slice(block);
432 }
433 zlib.extend_from_slice(&adler32(&raw).to_be_bytes());
434 chunk(&mut out, *b"IDAT", &zlib);
435 chunk(&mut out, *b"IEND", &[]);
436 out
437 }
438
439 fn chunk(out: &mut Vec<u8>, kind: [u8; 4], data: &[u8]) {
440 out.extend_from_slice(&(data.len() as u32).to_be_bytes());
441 out.extend_from_slice(&kind);
442 out.extend_from_slice(data);
443 let mut crc = crc32(kind.as_slice());
444 crc = crc32_continue(crc, data);
445 out.extend_from_slice(&crc.to_be_bytes());
446 }
447
448 fn adler32(data: &[u8]) -> u32 {
449 let (mut a, mut b) = (1u32, 0u32);
450 for &byte in data {
451 a = (a + u32::from(byte)) % 65521;
452 b = (b + a) % 65521;
453 }
454 (b << 16) | a
455 }
456
457 /// The CRC of one run, which is the running form started from zero.
458 fn crc32(data: &[u8]) -> u32 {
459 crc32_continue(0, data)
460 }
461
462 fn crc32_continue(previous: u32, data: &[u8]) -> u32 {
463 let mut crc = previous ^ 0xffff_ffff;
464 for &byte in data {
465 crc ^= u32::from(byte);
466 for _ in 0..8 {
467 crc = if crc & 1 == 1 {
468 (crc >> 1) ^ 0xedb8_8320
469 } else {
470 crc >> 1
471 };
472 }
473 }
474 crc ^ 0xffff_ffff
475 }
476
477 #[cfg(test)]
478 mod tests {
479 use super::*;
480
481 /// A hand-decoded PNG, because an encoder nobody reads back is an encoder
482 /// that ships a file no viewer opens. Stored deflate blocks make the check
483 /// as short as the encoder: header, then length-prefixed literal runs.
484 fn decode(png: &[u8]) -> (usize, usize, Vec<u8>) {
485 assert_eq!(
486 &png[0..8],
487 &[0x89, b'P', b'N', b'G', 0x0d, 0x0a, 0x1a, 0x0a]
488 );
489 let mut at = 8;
490 let (mut width, mut height, mut raw) = (0usize, 0usize, Vec::new());
491 while at < png.len() {
492 let length = u32::from_be_bytes(png[at..at + 4].try_into().unwrap()) as usize;
493 let kind = &png[at + 4..at + 8];
494 let data = &png[at + 8..at + 8 + length];
495 let stated =
496 u32::from_be_bytes(png[at + 8 + length..at + 12 + length].try_into().unwrap());
497 let mut crc = crc32(kind);
498 crc = crc32_continue(crc, data);
499 assert_eq!(
500 crc,
501 stated,
502 "chunk {} has a bad crc",
503 String::from_utf8_lossy(kind)
504 );
505 match kind {
506 b"IHDR" => {
507 width = u32::from_be_bytes(data[0..4].try_into().unwrap()) as usize;
508 height = u32::from_be_bytes(data[4..8].try_into().unwrap()) as usize;
509 assert_eq!(&data[8..], &[8, 0, 0, 0, 0]);
510 }
511 b"IDAT" => {
512 assert_eq!(&data[0..2], &[0x78, 0x01]);
513 let mut cursor = 2;
514 loop {
515 let last = data[cursor];
516 let len =
517 u16::from_le_bytes(data[cursor + 1..cursor + 3].try_into().unwrap())
518 as usize;
519 let nlen =
520 u16::from_le_bytes(data[cursor + 3..cursor + 5].try_into().unwrap());
521 assert_eq!(
522 nlen,
523 !(len as u16),
524 "a stored block's length is not negated"
525 );
526 raw.extend_from_slice(&data[cursor + 5..cursor + 5 + len]);
527 cursor += 5 + len;
528 if last == 1 {
529 break;
530 }
531 }
532 assert_eq!(
533 u32::from_be_bytes(data[cursor..cursor + 4].try_into().unwrap()),
534 adler32(&raw)
535 );
536 }
537 _ => {}
538 }
539 at += 12 + length;
540 }
541 (width, height, raw)
542 }
543
544 #[test]
545 fn the_png_is_one_a_decoder_can_read_back() {
546 let mut sheet = Sheet::new(3, 2);
547 sheet.darken(1, 0, 0);
548 let file = png(&sheet);
549 let (width, height, raw) = decode(&file);
550 assert_eq!((width, height), (3, 2));
551 // One filter byte per row, then the row.
552 assert_eq!(raw, vec![0, PAPER, 0, PAPER, 0, PAPER, PAPER, PAPER]);
553 }
554
555 /// Over 64KB of pixels the stream needs more than one stored block, and a
556 /// wrong last-block flag there is a truncated image rather than an error.
557 #[test]
558 fn a_sheet_past_one_stored_block_still_decodes() {
559 let sheet = Sheet::new(400, 400);
560 let (width, height, raw) = decode(&png(&sheet));
561 assert_eq!((width, height), (400, 400));
562 assert_eq!(raw.len(), 400 * 401);
563 }
564 }
565