diff options
Diffstat (limited to 'thirdparty/harfbuzz/src/hb-set-digest.hh')
| -rw-r--r-- | thirdparty/harfbuzz/src/hb-set-digest.hh | 30 |
1 files changed, 21 insertions, 9 deletions
diff --git a/thirdparty/harfbuzz/src/hb-set-digest.hh b/thirdparty/harfbuzz/src/hb-set-digest.hh index 7d4979b73b..fab36216e4 100644 --- a/thirdparty/harfbuzz/src/hb-set-digest.hh +++ b/thirdparty/harfbuzz/src/hb-set-digest.hh @@ -30,7 +30,7 @@ #include "hb.hh" /* - * The set digests here implement various "filters" that support + * The set-digests here implement various "filters" that support * "approximate member query". Conceptually these are like Bloom * Filter and Quotient Filter, however, much smaller, faster, and * designed to fit the requirements of our uses for glyph coverage @@ -40,13 +40,25 @@ * set of glyphs, but fully flooded and ineffective if coverage is * all over the place. * - * The frozen-set can be used instead of a digest, to trade more - * memory for 100% accuracy, but in practice, that doesn't look like - * an attractive trade-off. + * The way these are used is that the filter is first populated by + * a lookup's or subtable's Coverage table(s), and then when we + * want to apply the lookup or subtable to a glyph, before trying + * to apply, we ask the filter if the glyph may be covered. If it's + * not, we return early. + * + * We use these filters both at the lookup-level, and then again, + * at the subtable-level. Both have performance win. + * + * The main filter we use is a combination of three bits-pattern + * filters. A bits-pattern filter checks a number of bits (5 or 6) + * of the input number (glyph-id in this case) and checks whether + * its pattern is amongst the patterns of any of the accepted values. + * The accepted patterns are represented as a "long" integer. The + * check is done using four bitwise operations only. */ template <typename mask_t, unsigned int shift> -struct hb_set_digest_lowest_bits_t +struct hb_set_digest_bits_pattern_t { static constexpr unsigned mask_bytes = sizeof (mask_t); static constexpr unsigned mask_bits = sizeof (mask_t) * 8; @@ -102,7 +114,7 @@ struct hb_set_digest_lowest_bits_t bool add_sorted_array (const hb_sorted_array_t<const T>& arr) { return add_sorted_array (&arr, arr.len ()); } bool may_have (hb_codepoint_t g) const - { return !!(mask & mask_for (g)); } + { return mask & mask_for (g); } private: @@ -171,11 +183,11 @@ struct hb_set_digest_combiner_t using hb_set_digest_t = hb_set_digest_combiner_t < - hb_set_digest_lowest_bits_t<unsigned long, 4>, + hb_set_digest_bits_pattern_t<unsigned long, 4>, hb_set_digest_combiner_t < - hb_set_digest_lowest_bits_t<unsigned long, 0>, - hb_set_digest_lowest_bits_t<unsigned long, 9> + hb_set_digest_bits_pattern_t<unsigned long, 0>, + hb_set_digest_bits_pattern_t<unsigned long, 9> > > ; |