rustybuzz/hb/
set_digest.rs

1use ttf_parser::GlyphId;
2
3// To make things easier, we don't have the generic parameter mask_t,
4// and assume we always use u64, since this is what is also used in
5// harfbuzz.
6type mask_t = u64;
7
8pub trait hb_set_digest_ext: Clone {
9    type A;
10    // Instead of `init()`
11    fn new() -> Self;
12    fn full() -> Self;
13    fn add(&mut self, g: GlyphId);
14    fn add_array(&mut self, array: impl IntoIterator<Item = GlyphId> + Clone);
15    fn add_range(&mut self, a: GlyphId, b: GlyphId) -> bool;
16    fn may_have(&self, o: &Self::A) -> bool;
17    fn may_have_glyph(&self, g: GlyphId) -> bool;
18}
19
20#[derive(Clone)]
21pub struct hb_set_digest_bits_pattern_t<const shift: u8> {
22    mask: mask_t,
23}
24
25impl<const shift: u8> hb_set_digest_bits_pattern_t<shift> {
26    const fn mask_bytes() -> mask_t {
27        core::mem::size_of::<mask_t>() as mask_t
28    }
29
30    const fn mask_bits() -> mask_t {
31        (core::mem::size_of::<mask_t>() * 8) as mask_t
32    }
33
34    fn mask_for(g: GlyphId) -> mask_t {
35        1 << ((g.0 as mask_t >> shift) & (hb_set_digest_bits_pattern_t::<shift>::mask_bits() - 1))
36    }
37
38    const fn num_bits() -> usize {
39        let mut num = 0;
40
41        if hb_set_digest_bits_pattern_t::<shift>::mask_bytes() >= 1 {
42            num += 3;
43        }
44
45        if hb_set_digest_bits_pattern_t::<shift>::mask_bytes() >= 2 {
46            num += 1;
47        }
48
49        if hb_set_digest_bits_pattern_t::<shift>::mask_bytes() >= 4 {
50            num += 1;
51        }
52
53        if hb_set_digest_bits_pattern_t::<shift>::mask_bytes() >= 8 {
54            num += 1;
55        }
56
57        if hb_set_digest_bits_pattern_t::<shift>::mask_bytes() >= 16 {
58            num += 1;
59        }
60
61        num
62    }
63}
64
65impl<const shift: u8> hb_set_digest_ext for hb_set_digest_bits_pattern_t<shift> {
66    type A = hb_set_digest_bits_pattern_t<shift>;
67
68    fn new() -> Self {
69        debug_assert!((shift as usize) < core::mem::size_of::<GlyphId>() * 8);
70        debug_assert!((shift as usize + Self::num_bits()) < core::mem::size_of::<GlyphId>() * 8);
71        Self { mask: 0 }
72    }
73
74    fn full() -> Self {
75        Self { mask: mask_t::MAX }
76    }
77
78    fn add(&mut self, g: GlyphId) {
79        self.mask |= hb_set_digest_bits_pattern_t::<shift>::mask_for(g);
80    }
81
82    fn add_array(&mut self, array: impl IntoIterator<Item = GlyphId> + Clone) {
83        for el in array {
84            self.add(el);
85        }
86    }
87
88    fn add_range(&mut self, a: GlyphId, b: GlyphId) -> bool {
89        if self.mask == mask_t::MAX {
90            return false;
91        }
92
93        if (b.0 as mask_t >> shift) - (a.0 as mask_t >> shift)
94            >= hb_set_digest_bits_pattern_t::<shift>::mask_bits() - 1
95        {
96            self.mask = mask_t::MAX;
97            false
98        } else {
99            let ma = hb_set_digest_bits_pattern_t::<shift>::mask_for(a);
100            let mb = hb_set_digest_bits_pattern_t::<shift>::mask_for(b);
101            self.mask |= mb + mb.wrapping_sub(ma) - mask_t::from(mb < ma);
102            true
103        }
104    }
105
106    fn may_have(&self, o: &hb_set_digest_bits_pattern_t<shift>) -> bool {
107        self.mask & o.mask != 0
108    }
109
110    fn may_have_glyph(&self, g: GlyphId) -> bool {
111        self.mask & hb_set_digest_bits_pattern_t::<shift>::mask_for(g) != 0
112    }
113}
114
115#[derive(Clone)]
116pub struct hb_set_digest_combiner_t<head_t, tail_t>
117where
118    head_t: hb_set_digest_ext,
119    tail_t: hb_set_digest_ext,
120{
121    head: head_t,
122    tail: tail_t,
123}
124
125impl<head_t, tail_t> hb_set_digest_ext for hb_set_digest_combiner_t<head_t, tail_t>
126where
127    head_t: hb_set_digest_ext<A = head_t>,
128    tail_t: hb_set_digest_ext<A = tail_t>,
129{
130    type A = hb_set_digest_combiner_t<head_t, tail_t>;
131
132    fn new() -> Self {
133        Self {
134            head: head_t::new(),
135            tail: tail_t::new(),
136        }
137    }
138
139    fn full() -> Self {
140        Self {
141            head: head_t::full(),
142            tail: tail_t::full(),
143        }
144    }
145
146    fn add(&mut self, g: GlyphId) {
147        self.head.add(g);
148        self.tail.add(g);
149    }
150
151    fn add_array(&mut self, array: impl IntoIterator<Item = GlyphId> + Clone) {
152        // TODO: Is this expensive if someone passes e.g. a vector?
153        self.head.add_array(array.clone());
154        self.tail.add_array(array);
155    }
156
157    fn add_range(&mut self, a: GlyphId, b: GlyphId) -> bool {
158        let first = self.head.add_range(a, b);
159        let second = self.tail.add_range(a, b);
160        first || second
161    }
162
163    fn may_have(&self, o: &Self::A) -> bool {
164        self.head.may_have(&o.head) && self.tail.may_have(&o.tail)
165    }
166
167    fn may_have_glyph(&self, g: GlyphId) -> bool {
168        self.head.may_have_glyph(g) && self.tail.may_have_glyph(g)
169    }
170}
171
172#[rustfmt::skip]
173pub type hb_set_digest_t = hb_set_digest_combiner_t<
174    hb_set_digest_bits_pattern_t<4>,
175    hb_set_digest_combiner_t<
176        hb_set_digest_bits_pattern_t<0>,
177        hb_set_digest_bits_pattern_t<9>
178    >,
179>;
180
181#[rustfmt::skip]
182#[cfg(test)]
183mod tests {
184    use super::*;
185
186    #[test]
187    fn test_single() {
188        let mut set = hb_set_digest_t::new();
189
190        set.add(GlyphId(2));
191        assert!(set.may_have_glyph(GlyphId(2)))
192    }
193
194    #[test]
195    fn test_multiple_1() {
196        let mut set = hb_set_digest_t::new();
197
198        set.add(GlyphId(2));
199        set.add(GlyphId(10));
200        set.add(GlyphId(300));
201        set.add(GlyphId(255));
202        assert!(set.may_have_glyph(GlyphId(2)));
203        assert!(set.may_have_glyph(GlyphId(300)));
204        assert!(set.may_have_glyph(GlyphId(10)));
205        assert!(set.may_have_glyph(GlyphId(255)));
206    }
207
208    #[test]
209    fn test_multiple_2() {
210        let mut set = hb_set_digest_t::new();
211
212        set.add(GlyphId(245));
213        set.add(GlyphId(1060));
214        set.add(GlyphId(300));
215        set.add(GlyphId(599));
216        assert!(set.may_have_glyph(GlyphId(245)));
217        assert!(set.may_have_glyph(GlyphId(1060)));
218        assert!(set.may_have_glyph(GlyphId(300)));
219        assert!(set.may_have_glyph(GlyphId(599)));
220    }
221
222    #[test]
223    fn test_range_1() {
224        let mut set = hb_set_digest_t::new();
225
226        set.add_range(GlyphId(10), GlyphId(12));
227        assert!(set.may_have_glyph(GlyphId(10)));
228        assert!(set.may_have_glyph(GlyphId(11)));
229        assert!(set.may_have_glyph(GlyphId(12)));
230    }
231
232    #[test]
233    fn test_range_2() {
234        let mut set = hb_set_digest_t::new();
235
236        set.add_range(GlyphId(15), GlyphId(20));
237        assert!(set.may_have_glyph(GlyphId(15)));
238        assert!(set.may_have_glyph(GlyphId(16)));
239        assert!(set.may_have_glyph(GlyphId(17)));
240        assert!(set.may_have_glyph(GlyphId(18)));
241        assert!(set.may_have_glyph(GlyphId(19)));
242        assert!(set.may_have_glyph(GlyphId(20)));
243    }
244
245    #[test]
246    fn test_range_3() {
247        let mut set = hb_set_digest_t::new();
248
249        for i in 170..=239 {
250            set.add(GlyphId(i));
251        }
252        assert!(set.may_have_glyph(GlyphId(200)));
253    }
254
255    #[test]
256    fn test_complex() {
257        let mut set = hb_set_digest_t::new();
258
259        set.add_range(GlyphId(5670), GlyphId(5675));
260        set.add(GlyphId(3));
261        set.add(GlyphId(8769));
262        set.add(GlyphId(10000));
263        set.add_range(GlyphId(3456), GlyphId(3460));
264        assert!(set.may_have_glyph(GlyphId(5670)));
265        assert!(set.may_have_glyph(GlyphId(5675)));
266        assert!(set.may_have_glyph(GlyphId(3)));
267        assert!(set.may_have_glyph(GlyphId(8769)));
268        assert!(set.may_have_glyph(GlyphId(10000)));
269        assert!(set.may_have_glyph(GlyphId(3456)));
270        assert!(set.may_have_glyph(GlyphId(3460)));
271    }
272}
rustybuzz/hb/set_digest.rs

rustybuzz/hb/
set_digest.rs
