Skip to main content

harfrust/
set_digest.rs

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}