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}
273