harfrust/hb/
set_digest.rs

1use read_fonts::tables::layout::CoverageTable;
2
3type mask_t = u64;
4
5const HB_SET_DIGEST_SHIFTS: [u32; 3] = [4, 0, 6];
6const N: usize = HB_SET_DIGEST_SHIFTS.len();
7const MASK_BITS: u32 = mask_t::BITS;
8const MB1: u32 = MASK_BITS - 1;
9const ONE: mask_t = 1;
10const ALL: mask_t = mask_t::MAX;
11
12#[derive(Clone, Debug)]
13pub struct hb_set_digest_t {
14    masks: [mask_t; N],
15}
16
17impl Default for hb_set_digest_t {
18    fn default() -> Self {
19        Self::new()
20    }
21}
22
23impl hb_set_digest_t {
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 mask_t;
65        let b = b as mask_t;
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 mask_t;
74            if (b >> shift).wrapping_sub(a >> shift) >= MB1 as mask_t {
75                self.masks[i] = ALL;
76            } else {
77                let ma = ONE << ((a >> shift) & MB1 as mask_t);
78                let mb = ONE << ((b >> shift) & MB1 as mask_t);
79                self.masks[i] |= mb + mb.wrapping_sub(ma) - mask_t::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        }
99    }
100
101    pub fn may_have(&self, g: u32) -> bool {
102        for i in 0..N {
103            let shift = HB_SET_DIGEST_SHIFTS[i];
104            let bit = (g >> shift) & MB1;
105            if self.masks[i] & (ONE << bit) == 0 {
106                return false;
107            }
108        }
109        true
110    }
111
112    pub fn may_intersect(&self, other: &Self) -> bool {
113        for i in 0..N {
114            if self.masks[i] & other.masks[i] == 0 {
115                return false;
116            }
117        }
118        true
119    }
120}
121
122#[cfg(test)]
123mod tests {
124    use super::*;
125
126    #[test]
127    fn test_single() {
128        let mut set = hb_set_digest_t::new();
129        set.add(2);
130        assert!(set.may_have(2));
131    }
132
133    #[test]
134    fn test_multiple_1() {
135        let mut set = hb_set_digest_t::new();
136        set.add(2);
137        set.add(10);
138        set.add(300);
139        set.add(255);
140        assert!(set.may_have(2));
141        assert!(set.may_have(10));
142        assert!(set.may_have(255));
143        assert!(set.may_have(300));
144    }
145
146    #[test]
147    fn test_multiple_2() {
148        let mut set = hb_set_digest_t::new();
149        set.add(245);
150        set.add(1060);
151        set.add(300);
152        set.add(599);
153        assert!(set.may_have(245));
154        assert!(set.may_have(1060));
155        assert!(set.may_have(300));
156        assert!(set.may_have(599));
157    }
158
159    #[test]
160    fn test_range_1() {
161        let mut set = hb_set_digest_t::new();
162        set.add_range(10, 12);
163        assert!(set.may_have(10));
164        assert!(set.may_have(11));
165        assert!(set.may_have(12));
166    }
167
168    #[test]
169    fn test_range_2() {
170        let mut set = hb_set_digest_t::new();
171        set.add_range(20, 15);
172        set.add_range(15, 20);
173        for gid in 15..=20 {
174            assert!(set.may_have(gid));
175        }
176    }
177
178    #[test]
179    fn test_range_3() {
180        let mut set = hb_set_digest_t::new();
181        for i in 170..=239 {
182            set.add(i);
183        }
184        assert!(set.may_have(200));
185    }
186
187    #[test]
188    fn test_complex() {
189        let mut set = hb_set_digest_t::new();
190        set.add_range(5670, 5675);
191        set.add(3);
192        set.add(8769);
193        set.add(10000);
194        set.add_range(3456, 3460);
195
196        assert!(set.may_have(3));
197        assert!(set.may_have(5670));
198        assert!(set.may_have(5675));
199        assert!(set.may_have(8769));
200        assert!(set.may_have(10000));
201        assert!(set.may_have(3456));
202        assert!(set.may_have(3460));
203    }
204
205    #[test]
206    fn test_intersect() {
207        let mut a = hb_set_digest_t::new();
208        let mut b = hb_set_digest_t::new();
209
210        a.add(123);
211        b.add(456);
212        assert!(!a.may_intersect(&b));
213
214        b.add(123);
215        assert!(a.may_intersect(&b));
216    }
217}
harfrust/hb/set_digest.rs

harfrust/hb/
set_digest.rs
