Skip to main content

read_fonts/ps/
charmap.rs

1//! Unicode character map generated from glyph names.
2
3#[cfg(feature = "agl")]
4use super::agl;
5use alloc::vec::Vec;
6use types::GlyphId;
7
8/// Used to mark variant glyphs such as A.alt.
9const VARIANT_BIT: u32 = 0x80000000;
10
11/// A Unicode charmap built from glyph names.
12///
13/// Building one depends on the `agl` feature.
14#[derive(Clone, Default, Debug)]
15pub struct UnicodeCharmap {
16    mapping: Vec<(u32, GlyphId)>,
17}
18
19impl UnicodeCharmap {
20    /// Create a new unicode charmap for the given sequence of glyph id
21    /// and name pairs.
22    // See <https://gitlab.freedesktop.org/freetype/freetype/-/blob/80a507a6b8e3d2906ad2c8ba69329bd2fb2a85ef/src/psnames/psmodule.c#L313>
23    #[cfg(feature = "agl")]
24    pub fn from_glyph_names<'a>(pairs: impl Iterator<Item = (GlyphId, &'a str)>) -> Self {
25        #[derive(Copy, Clone, PartialEq)]
26        enum State {
27            Unchecked,
28            Include,
29            Exclude,
30        }
31        let mut extra_glyphs = [(State::Unchecked, GlyphId::NOTDEF); 10];
32        let mut mapping = Vec::new();
33        for (gid, name) in pairs {
34            // Check extra glyphs by name
35            if let Some(n) = EXTRA_GLYPH_LIST
36                .iter()
37                .position(|(_, extra_name)| name == *extra_name)
38            {
39                let extra = &mut extra_glyphs[n];
40                if extra.0 == State::Unchecked {
41                    extra.0 = State::Include;
42                    extra.1 = gid;
43                }
44            }
45            // Map to a char
46            let ch = unicode_value(name);
47            if ch & !VARIANT_BIT == 0 {
48                continue;
49            }
50            // If we have a direct char mapping for an entry in the extra
51            // glyph list then disable it
52            if let Some(n) = EXTRA_GLYPH_LIST
53                .iter()
54                .position(|(extra_ch, _)| ch == *extra_ch)
55            {
56                extra_glyphs[n].0 = State::Exclude;
57            }
58            mapping.push((ch, gid));
59        }
60        for ((extra_ch, _), (state, gid)) in EXTRA_GLYPH_LIST.iter().zip(extra_glyphs) {
61            if state == State::Include {
62                mapping.push((*extra_ch, gid));
63            }
64        }
65        mapping.shrink_to_fit();
66        // Base glyphs sort before their variants. The sort is stable, so
67        // glyphs with the same value stay in glyph order, as the C library
68        // sort FreeType uses keeps them on most systems.
69        // <https://gitlab.freedesktop.org/freetype/freetype/-/blob/80a507a6b8e3d2906ad2c8ba69329bd2fb2a85ef/src/psnames/psmodule.c#L182>
70        mapping.sort_by_key(|(ch, _)| (ch & !VARIANT_BIT, *ch));
71        Self { mapping }
72    }
73
74    /// Returns the glyph id for the given character.
75    ///
76    /// A base glyph is preferred, and a variant is used where the font has
77    /// no base glyph for the character.
78    pub fn map(&self, ch: impl Into<u32>) -> Option<GlyphId> {
79        // <https://gitlab.freedesktop.org/freetype/freetype/-/blob/80a507a6b8e3d2906ad2c8ba69329bd2fb2a85ef/src/psnames/psmodule.c#L412>
80        self.search(ch.into(), false).0
81    }
82
83    /// Returns the first character above `ch` that has a glyph, and the
84    /// glyph.
85    ///
86    /// <https://gitlab.freedesktop.org/freetype/freetype/-/blob/80a507a6b8e3d2906ad2c8ba69329bd2fb2a85ef/src/psnames/psmodule.c#L456>
87    pub(crate) fn next_char(&self, ch: u32) -> Option<(u32, GlyphId)> {
88        let ch = ch.checked_add(1)?;
89        match self.search(ch, true) {
90            (Some(glyph), _) => Some((ch, glyph)),
91            // The first entry above, which is a base glyph where there is
92            // one, since bases sort first.
93            (None, min) => self
94                .mapping
95                .get(min)
96                .map(|(next, glyph)| (next & !VARIANT_BIT, *glyph)),
97        }
98    }
99
100    /// Searches for `ch` as FreeType does, returning the glyph found and the
101    /// index of the first entry at or above `ch`.
102    ///
103    /// The search keeps a variant until it finds the base glyph, and after
104    /// each step predicts the next entry as in a run of consecutive
105    /// characters. Where several glyphs share a character, the predictions
106    /// decide which is found. A step below the current entry is a large
107    /// unsigned step forwards. `char_next` keeps a 32 bit index, so the step
108    /// wraps around to the entry below. `char_index` keeps a pointer, which
109    /// wraps the same way on 32 bit targets and lands past the end on 64 bit
110    /// ones, so its results depend on the target.
111    fn search(&self, ch: u32, wrapping_index: bool) -> (Option<GlyphId>, usize) {
112        let entries = &self.mapping;
113        let (mut min, mut max) = (0, entries.len());
114        let mut mid = min + ((max - min) >> 1);
115        let mut result = None;
116        while min < max {
117            let Some(&(value, glyph)) = entries.get(mid) else {
118                break;
119            };
120            if value == ch {
121                return (Some(glyph), min);
122            }
123            let base = value & !VARIANT_BIT;
124            if base == ch {
125                // Remember the variant but keep looking for a base glyph.
126                result = Some(glyph);
127            }
128            if base < ch {
129                min = mid + 1;
130            } else {
131                max = mid;
132            }
133            // A reasonable prediction in a run of consecutive characters.
134            let step = ch.wrapping_sub(base);
135            mid = if wrapping_index || cfg!(target_pointer_width = "32") {
136                (mid as u32).wrapping_add(step) as usize
137            } else {
138                mid.saturating_add(step as usize)
139            };
140            if mid >= max || mid < min {
141                mid = min + ((max - min) >> 1);
142            }
143        }
144        (result, min)
145    }
146
147    /// Returns each character and its glyph, in character order.
148    ///
149    /// A variant glyph, such as `A.alt`, has the high bit set on its
150    /// character, and follows any base glyph for the character.
151    pub fn iter(&self) -> impl Iterator<Item = (u32, GlyphId)> + Clone + '_ {
152        self.mapping.iter().copied()
153    }
154}
155
156/// Returns the code point FreeType assigns `name`, with [`VARIANT_BIT`] set
157/// for a name with a suffix after a dot, or zero if it has none.
158///
159/// A `uni` name takes exactly four uppercase hex digits and a `u` name four
160/// to six. Neither is checked for a valid code point, so either can map a
161/// surrogate or a value past U+10FFFF. Any other name is looked up whole up
162/// to its first dot, so ligatures such as `f_i` and longer `uni` sequences
163/// map to nothing.
164///
165/// See <https://gitlab.freedesktop.org/freetype/freetype/-/blob/80a507a6b8e3d2906ad2c8ba69329bd2fb2a85ef/src/psnames/psmodule.c#L61>
166#[cfg(feature = "agl")]
167fn unicode_value(name: &str) -> u32 {
168    /// Reads up to `max` uppercase hex digits, returning their value and
169    /// count.
170    fn hex_digits(bytes: &[u8], max: usize) -> (u32, usize) {
171        let mut value = 0;
172        let mut count = 0;
173        for &b in bytes.iter().take(max) {
174            let digit = match b {
175                b'0'..=b'9' => b - b'0',
176                b'A'..=b'F' => b - b'A' + 10,
177                _ => break,
178            };
179            value = (value << 4) | digit as u32;
180            count += 1;
181        }
182        (value, count)
183    }
184    /// Returns `value` if the digits end the name or a dot follows them.
185    fn ended(value: u32, rest: &[u8]) -> Option<u32> {
186        match rest.first() {
187            None => Some(value),
188            Some(b'.') => Some(value | VARIANT_BIT),
189            _ => None,
190        }
191    }
192    let bytes = name.as_bytes();
193    if let Some(digits) = bytes.strip_prefix(b"uni") {
194        let (value, count) = hex_digits(digits, 4);
195        if let Some(value) = (count == 4)
196            .then(|| ended(value, &digits[count..]))
197            .flatten()
198        {
199            return value;
200        }
201    }
202    if let Some(digits) = bytes.strip_prefix(b"u") {
203        let (value, count) = hex_digits(digits, 6);
204        if let Some(value) = (count >= 4)
205            .then(|| ended(value, &digits[count..]))
206            .flatten()
207        {
208            return value;
209        }
210    }
211    let base = name.split('.').next().unwrap_or_default();
212    if base.is_empty() {
213        return 0;
214    }
215    let value = agl::lookup_char(base).map_or(0, |ch| ch as u32);
216    if base.len() < name.len() {
217        value | VARIANT_BIT
218    } else {
219        value
220    }
221}
222
223/// Support for extra glyphs not handled well in AGL
224/// See <https://gitlab.freedesktop.org/freetype/freetype/-/blob/80a507a6b8e3d2906ad2c8ba69329bd2fb2a85ef/src/psnames/psmodule.c#L218>
225#[cfg(feature = "agl")]
226#[rustfmt::skip]
227const EXTRA_GLYPH_LIST: [(u32, &str); 10] = [
228    // WGL 4
229    (0x0394, "Delta"),
230    (0x03A9, "Omega"),
231    (0x2215, "fraction"),
232    (0x00AD, "hyphen"),
233    (0x02C9, "macron"),
234    (0x03BC, "mu"),
235    (0x2219, "periodcentered"),
236    (0x00A0, "space"),
237    // Romanian
238    (0x021A, "Tcommaaccent"),
239    (0x021B, "tcommaaccent"),
240];
241
242#[cfg(test)]
243#[cfg(feature = "agl")]
244mod tests {
245    use super::super::type1::Type1Font;
246    use super::*;
247
248    #[test]
249    fn cmap() {
250        let cmap = UnicodeCharmap::from_glyph_names(
251            [
252                (1, "A"),
253                (2, "uni0042"), // B
254                (333, "C.alt"),
255                (4, "D"),
256                (51, "Lcedilla"),
257                (22, "Cdot"),
258                (8, "aacute"),
259                (7, "union"),
260            ]
261            .map(|(gid, name)| (GlyphId::new(gid), name))
262            .iter()
263            .copied(),
264        );
265        assert_eq!(cmap.map('A'), Some(GlyphId::new(1)));
266        assert_eq!(cmap.map('B'), Some(GlyphId::new(2)));
267        // We're actually missing a glyph for "C" but have "C.alt" which
268        // we select by design (matching FT)
269        assert_eq!(cmap.map('C'), Some(GlyphId::new(333)));
270        assert_eq!(cmap.map('D'), Some(GlyphId::new(4)));
271        assert_eq!(cmap.map('Ļ'), Some(GlyphId::new(51)));
272        assert_eq!(cmap.map('Ċ'), Some(GlyphId::new(22)));
273        assert_eq!(cmap.map('á'), Some(GlyphId::new(8)));
274        assert_eq!(cmap.map('∪'), Some(GlyphId::new(7)));
275    }
276
277    #[test]
278    fn cmap_from_type1() {
279        let font = Type1Font::new(font_test_data::type1::NOTO_SERIF_REGULAR_SUBSET_PFB).unwrap();
280        let cmap = UnicodeCharmap::from_glyph_names(font.glyph_names());
281        // Extracted from FreeType's generated unicode cmap
282        let expected = [
283            ('H' as u32, 1),
284            // H.c2sc which gets encoded as a variant
285            ('H' as u32 | VARIANT_BIT, 8),
286            ('f' as u32, 2),
287            ('i' as u32, 3),
288            ('x' as u32, 4),
289        ];
290        let result = cmap
291            .iter()
292            .map(|(ch, gid)| (ch, gid.to_u32()))
293            .collect::<Vec<_>>();
294        assert_eq!(result, expected);
295        assert_eq!(cmap.map('a'), None);
296        for (ch, gid) in expected {
297            if ch & VARIANT_BIT != 0 {
298                assert_eq!(cmap.map(ch), None);
299            } else {
300                assert_eq!(
301                    cmap.map(ch),
302                    Some(GlyphId::new(gid)),
303                    "cmap failed for {ch} -> {gid}"
304                );
305            }
306        }
307    }
308
309    #[test]
310    fn extra_glyphs_override() {
311        // If we have a "hyphen" glyph but no "softhyphen" then add an
312        // additional entry mapping the soft-hyphen codepoint to the
313        // hyphen glyph
314        let cmap = UnicodeCharmap::from_glyph_names([(GlyphId::new(1), "hyphen")].into_iter());
315        assert_eq!(cmap.mapping.len(), 2);
316        assert_eq!(cmap.map('\u{00AD}'), Some(GlyphId::new(1)));
317        assert_eq!(cmap.map('\u{002D}'), Some(GlyphId::new(1)));
318    }
319
320    #[test]
321    fn extra_glyphs_no_override() {
322        // If we have an explicit "softhyphen" glyph then don't add any
323        // additional mapping
324        let cmap = UnicodeCharmap::from_glyph_names([(GlyphId::new(1), "softhyphen")].into_iter());
325        assert_eq!(cmap.mapping.len(), 1);
326        assert_eq!(cmap.map('\u{00AD}'), Some(GlyphId::new(1)));
327    }
328
329    // The values FreeType's psnames module gives these names.
330    #[test]
331    fn names_convert_as_freetype_converts_them() {
332        const V: u32 = VARIANT_BIT;
333        for (name, value) in [
334            ("uni0041", 0x41),
335            ("uni0041.alt", 0x41 | V),
336            ("u0041.alt.sc", 0x41 | V),
337            ("A.", 0x41 | V),
338            ("A..B", 0x41 | V),
339            ("union", 0x222A),
340            ("a1", 0x2701),
341            ("a191.alt", 0x27BE | V),
342            // Out of range values are kept.
343            ("uniD800", 0xD800),
344            ("u110000", 0x110000),
345            ("uFFFFFF", 0xFFFFFF),
346            ("u1F600", 0x1F600),
347            // These map to nothing.
348            ("uni0000", 0),
349            ("u0000", 0),
350            ("u0000041", 0),
351            ("uni00410042", 0),
352            ("uni0041x", 0),
353            ("f_i", 0),
354            ("dalethatafpatah", 0),
355            ("eigujarati", 0),
356            (".notdef", 0),
357        ] {
358            assert_eq!(unicode_value(name), value, "{name}");
359        }
360    }
361
362    /// Steps through `cmap` as FreeType does, stopping at glyph zero.
363    fn walk(cmap: &UnicodeCharmap) -> Vec<(u32, u32)> {
364        let mut entries = Vec::new();
365        let mut code = 0;
366        while let Some((next, glyph)) = cmap.next_char(code) {
367            if glyph == GlyphId::NOTDEF {
368                break;
369            }
370            entries.push((next, glyph.to_u32()));
371            code = next;
372        }
373        entries
374    }
375
376    // The glyphs FreeType's psnames module finds and steps through for these
377    // glyph names, where several glyphs share a character.
378    #[test]
379    fn search_and_walk_match_freetype() {
380        const V: u32 = VARIANT_BIT;
381        type Case<'a> = (&'a str, &'a [(u32, u32)], &'a [(u32, u32)]);
382        let cases: [Case; 9] = [
383            // The search lands on the second glyph and the walk on the first.
384            (".notdef A A", &[(0x41, 2)], &[(0x41, 1)]),
385            (".notdef D D D D D", &[(0x44, 3)], &[(0x44, 1)]),
386            (".notdef C.alt C.swash C.alt", &[(0x43, 1)], &[(0x43, 1)]),
387            (
388                ".notdef A.alt A.sc A",
389                &[(0x41, 3), (0x41 | V, 1)],
390                &[(0x41, 3)],
391            ),
392            (
393                ".notdef A.alt A.alt A.alt A.alt B",
394                &[(0x41, 1), (0x41 | V, 3), (0x42, 5)],
395                &[(0x41, 1), (0x42, 5)],
396            ),
397            // Glyph zero ends the walk.
398            ("space A B", &[(0x41, 1), (0x42, 2)], &[]),
399            (
400                ".notdef uniD800 u110000 uni0000 A",
401                &[(0x41, 4), (0xD800, 1), (0x110000, 2), (0, 0)],
402                &[(0x41, 4), (0xD800, 1), (0x110000, 2)],
403            ),
404            (
405                ".notdef hyphen x a1 spade",
406                &[(0x2D, 1), (0xAD, 1), (0x2701, 3), (0x2660, 4)],
407                &[(0x2D, 1), (0x78, 2), (0xAD, 1), (0x2660, 4), (0x2701, 3)],
408            ),
409            // Searching for B and G steps below the current entry, which
410            // FreeType's search takes as the entry below on 32 bit targets
411            // and as past the end on 64 bit ones. Its walk wraps on both.
412            (
413                ".notdef A uni0041 B uni0042 C uni0043 G uni0047 H",
414                if cfg!(target_pointer_width = "32") {
415                    &[
416                        (0x41, 2),
417                        (0x42, 4),
418                        (0x43, 5),
419                        (0x44, 0),
420                        (0x47, 8),
421                        (0x48, 9),
422                    ]
423                } else {
424                    &[
425                        (0x41, 2),
426                        (0x42, 3),
427                        (0x43, 5),
428                        (0x44, 0),
429                        (0x47, 7),
430                        (0x48, 9),
431                    ]
432                },
433                &[(0x41, 1), (0x42, 4), (0x43, 5), (0x47, 7), (0x48, 9)],
434            ),
435        ];
436        for (names, mapped, walked) in cases {
437            let cmap = UnicodeCharmap::from_glyph_names(
438                names
439                    .split(' ')
440                    .enumerate()
441                    .map(|(glyph, name)| (GlyphId::new(glyph as u32), name)),
442            );
443            for &(ch, glyph) in mapped {
444                assert_eq!(
445                    cmap.map(ch).map_or(0, |glyph| glyph.to_u32()),
446                    glyph,
447                    "{names}: {ch:x}"
448                );
449            }
450            assert_eq!(walk(&cmap), walked, "{names}");
451        }
452    }
453}