1use read_fonts::tables::layout::CoverageTable;
2
3type DigestMask = u64;
4
5const HB_SET_DIGEST_SHIFTS: [u32; 3] = [4, 0, 6];
6const N: usize = HB_SET_DIGEST_SHIFTS.len();
7const MASK_BITS: u32 = DigestMask::BITS;
8const MB1: u32 = MASK_BITS - 1;
9const ONE: DigestMask = 1;
10const ALL: DigestMask = DigestMask::MAX;
11
12#[derive(Clone, Debug)]
13pub struct SetDigest {
14 masks: [DigestMask; N],
15}
16
17impl Default for SetDigest {
18 fn default() -> Self {
19 Self::new()
20 }
21}
22
23impl SetDigest {
24 pub fn new() -> Self {
25 Self { masks: [0; N] }
26 }
27
28 pub fn from_coverage(coverage: &CoverageTable) -> Self {
29 let mut digest = Self::new();
30 digest.add_coverage(coverage);
31 digest
32 }
33
34 #[allow(dead_code)]
35 pub fn clear(&mut self) {
36 self.masks = [0; N];
37 }
38
39 pub fn full() -> Self {
40 Self { masks: [ALL; N] }
41 }
42
43 pub fn union(&mut self, other: &Self) {
44 for i in 0..N {
45 self.masks[i] |= other.masks[i];
46 }
47 }
48
49 pub fn add(&mut self, g: u32) {
50 for i in 0..N {
51 let shift = HB_SET_DIGEST_SHIFTS[i];
52 let bit = (g >> shift) & MB1;
53 self.masks[i] |= ONE << bit;
54 }
55 }
56
57 pub fn add_array(&mut self, array: impl IntoIterator<Item = u32>) {
58 for g in array {
59 self.add(g);
60 }
61 }
62
63 pub fn add_range(&mut self, a: u32, b: u32) -> bool {
64 let a = a as DigestMask;
65 let b = b as DigestMask;
66
67 if self.masks.iter().all(|&m| m == ALL) {
68 return false;
69 }
70
71 let mut changed = false;
72 for i in 0..N {
73 let shift = HB_SET_DIGEST_SHIFTS[i] as DigestMask;
74 if (b >> shift).wrapping_sub(a >> shift) >= MB1 as DigestMask {
75 self.masks[i] = ALL;
76 } else {
77 let ma = ONE << ((a >> shift) & MB1 as DigestMask);
78 let mb = ONE << ((b >> shift) & MB1 as DigestMask);
79 self.masks[i] |= mb + mb.wrapping_sub(ma) - DigestMask::from(mb < ma);
80 changed = true;
81 }
82 }
83 changed
84 }
85
86 pub fn add_coverage(&mut self, coverage: &CoverageTable) {
87 match coverage {
88 CoverageTable::Format1(table) => {
89 for glyph in table.glyph_array() {
90 self.add(glyph.get().into());
91 }
92 }
93 CoverageTable::Format2(table) => {
94 for range in table.range_records() {
95 self.add_range(range.start_glyph_id().into(), range.end_glyph_id().into());
96 }
97 }
98 CoverageTable::Format3(table) => {
99 for glyph in table.glyph_array() {
100 self.add(glyph.get().to_u32());
101 }
102 }
103 CoverageTable::Format4(table) => {
104 for range in table.range_records() {
105 self.add_range(
106 range.start_glyph_id().to_u32(),
107 range.end_glyph_id().to_u32(),
108 );
109 }
110 }
111 }
112 }
113
114 pub fn may_have(&self, g: u32) -> bool {
115 for i in 0..N {
116 let shift = HB_SET_DIGEST_SHIFTS[i];
117 let bit = (g >> shift) & MB1;
118 if self.masks[i] & (ONE << bit) == 0 {
119 return false;
120 }
121 }
122 true
123 }
124
125 pub fn may_intersect(&self, other: &Self) -> bool {
126 for i in 0..N {
127 if self.masks[i] & other.masks[i] == 0 {
128 return false;
129 }
130 }
131 true
132 }
133}
134
135#[cfg(test)]
136mod tests {
137 use super::*;
138
139 #[test]
140 fn test_single() {
141 let mut set = SetDigest::new();
142 set.add(2);
143 assert!(set.may_have(2));
144 }
145
146 #[test]
147 fn test_multiple_1() {
148 let mut set = SetDigest::new();
149 set.add(2);
150 set.add(10);
151 set.add(300);
152 set.add(255);
153 assert!(set.may_have(2));
154 assert!(set.may_have(10));
155 assert!(set.may_have(255));
156 assert!(set.may_have(300));
157 }
158
159 #[test]
160 fn test_multiple_2() {
161 let mut set = SetDigest::new();
162 set.add(245);
163 set.add(1060);
164 set.add(300);
165 set.add(599);
166 assert!(set.may_have(245));
167 assert!(set.may_have(1060));
168 assert!(set.may_have(300));
169 assert!(set.may_have(599));
170 }
171
172 #[test]
173 fn test_range_1() {
174 let mut set = SetDigest::new();
175 set.add_range(10, 12);
176 assert!(set.may_have(10));
177 assert!(set.may_have(11));
178 assert!(set.may_have(12));
179 }
180
181 #[test]
182 fn test_range_2() {
183 let mut set = SetDigest::new();
184 set.add_range(20, 15);
185 set.add_range(15, 20);
186 for gid in 15..=20 {
187 assert!(set.may_have(gid));
188 }
189 }
190
191 #[test]
192 fn test_range_3() {
193 let mut set = SetDigest::new();
194 for i in 170..=239 {
195 set.add(i);
196 }
197 assert!(set.may_have(200));
198 }
199
200 #[test]
201 fn test_complex() {
202 let mut set = SetDigest::new();
203 set.add_range(5670, 5675);
204 set.add(3);
205 set.add(8769);
206 set.add(10000);
207 set.add_range(3456, 3460);
208
209 assert!(set.may_have(3));
210 assert!(set.may_have(5670));
211 assert!(set.may_have(5675));
212 assert!(set.may_have(8769));
213 assert!(set.may_have(10000));
214 assert!(set.may_have(3456));
215 assert!(set.may_have(3460));
216 }
217
218 #[test]
219 fn test_intersect() {
220 let mut a = SetDigest::new();
221 let mut b = SetDigest::new();
222
223 a.add(123);
224 b.add(456);
225 assert!(!a.may_intersect(&b));
226
227 b.add(123);
228 assert!(a.may_intersect(&b));
229 }
230}