src/hb-ot-layout-common.hh | 2 src/hb-ot-layout.cc | 247 ++++++++++++++++++++------------------------- 2 files changed, 113 insertions(+), 136 deletions(-)
New commits: commit e98af6d1eda33346f72de8a45fbd317fc0e15935 Author: Behdad Esfahbod <beh...@behdad.org> Date: Thu Oct 25 22:25:29 2018 -0700 [layout] Try to speed up collect_lookups some more Barely made a dent :(. diff --git a/src/hb-ot-layout-common.hh b/src/hb-ot-layout-common.hh index 98f6a079..7bca2cae 100644 --- a/src/hb-ot-layout-common.hh +++ b/src/hb-ot-layout-common.hh @@ -555,6 +555,8 @@ struct Feature unsigned int *lookup_count /* IN/OUT */, unsigned int *lookup_tags /* OUT */) const { return lookupIndex.get_indexes (start_index, lookup_count, lookup_tags); } + inline void add_lookup_indexes_to (hb_set_t *lookup_indexes) const + { lookupIndex.add_indexes_to (lookup_indexes); } inline const FeatureParams &get_feature_params (void) const { return this+featureParams; } diff --git a/src/hb-ot-layout.cc b/src/hb-ot-layout.cc index c2803f3f..096fda20 100644 --- a/src/hb-ot-layout.cc +++ b/src/hb-ot-layout.cc @@ -828,29 +828,14 @@ hb_ot_layout_collect_lookups (hb_face_t *face, const hb_tag_t *features, hb_set_t *lookup_indexes /* OUT */) { + const OT::GSUBGPOS &g = get_gsubgpos_table (face, table_tag); + hb_auto_t<hb_set_t> feature_indexes; hb_ot_layout_collect_features (face, table_tag, scripts, languages, features, &feature_indexes); + for (hb_codepoint_t feature_index = HB_SET_VALUE_INVALID; hb_set_next (&feature_indexes, &feature_index);) - { - unsigned int lookup_indices[32]; - unsigned int offset, len; - - offset = 0; - do { - len = ARRAY_LENGTH (lookup_indices); - hb_ot_layout_feature_get_lookups (face, - table_tag, - feature_index, - offset, &len, - lookup_indices); - - for (unsigned int i = 0; i < len; i++) - lookup_indexes->add (lookup_indices[i]); - - offset += len; - } while (len == ARRAY_LENGTH (lookup_indices)); - } + g.get_feature (feature_index).add_lookup_indexes_to (lookup_indexes); } /** commit eb44bfc864f91c0c833c3156475d191ac1b79c72 Author: Behdad Esfahbod <beh...@behdad.org> Date: Thu Oct 25 21:42:19 2018 -0700 [layout] Memoize collect_features Fixes https://github.com/harfbuzz/harfbuzz/pull/1317 Fixes https://oss-fuzz.com/v2/testcase-detail/6543700493598720 diff --git a/src/hb-ot-layout.cc b/src/hb-ot-layout.cc index aa1a3570..c2803f3f 100644 --- a/src/hb-ot-layout.cc +++ b/src/hb-ot-layout.cc @@ -664,8 +664,46 @@ struct hb_collect_features_context_t : g (get_gsubgpos_table (face, table_tag)), feature_indexes (feature_indexes_) {} + bool inline visited (const OT::Script &s) + { + /* We might have Null() object here. Don't want to involve + * that in the memoize. So, detect empty objects and return. */ + if (unlikely (!s.has_default_lang_sys () && + !s.get_lang_sys_count ())) + return true; + + return visited (s, visited_script); + } + bool inline visited (const OT::LangSys &l) + { + /* We might have Null() object here. Don't want to involve + * that in the memoize. So, detect empty objects and return. */ + if (unlikely (!l.has_required_feature () && + !l.get_feature_count ())) + return true; + + return visited (l, visited_langsys); + } + + private: + template <typename T> + bool inline visited (const T &p, hb_set_t &visited_set) + { + hb_codepoint_t delta = (hb_codepoint_t) ((uintptr_t) &p - (uintptr_t) &g); + if (visited_set.has (delta)) + return true; + + visited_set.add (delta); + return false; + } + + public: const OT::GSUBGPOS &g; hb_set_t *feature_indexes; + + private: + hb_auto_t<hb_set_t> visited_script; + hb_auto_t<hb_set_t> visited_langsys; }; static void @@ -673,12 +711,13 @@ langsys_collect_features (hb_collect_features_context_t *c, const OT::LangSys &l, const hb_tag_t *features) { + if (c->visited (l)) return; + if (!features) { /* All features. */ - unsigned int index = l.get_required_feature_index (); - if (index != HB_OT_LAYOUT_NO_FEATURE_INDEX) - c->feature_indexes->add (index); + if (l.has_required_feature ()) + c->feature_indexes->add (l.get_required_feature_index ()); l.add_feature_indexes_to (c->feature_indexes); } @@ -688,7 +727,6 @@ langsys_collect_features (hb_collect_features_context_t *c, for (; *features; features++) { hb_tag_t feature_tag = *features; - unsigned int feature_index; unsigned int num_features = l.get_feature_count (); for (unsigned int i = 0; i < num_features; i++) { @@ -710,12 +748,15 @@ script_collect_features (hb_collect_features_context_t *c, const hb_tag_t *languages, const hb_tag_t *features) { + if (c->visited (s)) return; + if (!languages) { /* All languages. */ - langsys_collect_features (c, - s.get_default_lang_sys (), - features); + if (s.has_default_lang_sys ()) + langsys_collect_features (c, + s.get_default_lang_sys (), + features); unsigned int count = s.get_lang_sys_count (); for (unsigned int language_index = 0; language_index < count; language_index++) commit 84098b1639775aea5bf3f5d91fa6e657b612ce3a Author: Behdad Esfahbod <beh...@behdad.org> Date: Thu Oct 25 21:33:12 2018 -0700 [layout] Remove unintentionally added code diff --git a/src/hb-ot-layout-common.hh b/src/hb-ot-layout-common.hh index c9a87ce8..98f6a079 100644 --- a/src/hb-ot-layout-common.hh +++ b/src/hb-ot-layout-common.hh @@ -277,8 +277,6 @@ struct Script { return langSys.find_index (tag, index); } inline bool has_default_lang_sys (void) const { return defaultLangSys != 0; } - inline const LangSys& get_default_lang_sys (unsigned int i) const - { return get_default_lang_sys (); } inline const LangSys& get_default_lang_sys (void) const { return this+defaultLangSys; } inline bool subset (hb_subset_context_t *c) const commit 941600a9e06309f148d51403fa07dc56ce542572 Author: Behdad Esfahbod <beh...@behdad.org> Date: Thu Oct 25 21:26:08 2018 -0700 [layout] Add hb_collect_features_context_t Towards https://github.com/harfbuzz/harfbuzz/pull/1317 diff --git a/src/hb-ot-layout.cc b/src/hb-ot-layout.cc index ece7f89d..aa1a3570 100644 --- a/src/hb-ot-layout.cc +++ b/src/hb-ot-layout.cc @@ -655,20 +655,32 @@ hb_ot_layout_table_get_lookup_count (hb_face_t *face, return get_gsubgpos_table (face, table_tag).get_lookup_count (); } + +struct hb_collect_features_context_t +{ + hb_collect_features_context_t (hb_face_t *face, + hb_tag_t table_tag, + hb_set_t *feature_indexes_) + : g (get_gsubgpos_table (face, table_tag)), + feature_indexes (feature_indexes_) {} + + const OT::GSUBGPOS &g; + hb_set_t *feature_indexes; +}; + static void -langsys_collect_features (const OT::GSUBGPOS &g, +langsys_collect_features (hb_collect_features_context_t *c, const OT::LangSys &l, - const hb_tag_t *features, - hb_set_t *feature_indexes /* OUT */) + const hb_tag_t *features) { if (!features) { /* All features. */ unsigned int index = l.get_required_feature_index (); if (index != HB_OT_LAYOUT_NO_FEATURE_INDEX) - feature_indexes->add (index); + c->feature_indexes->add (index); - l.add_feature_indexes_to (feature_indexes); + l.add_feature_indexes_to (c->feature_indexes); } else { @@ -682,9 +694,9 @@ langsys_collect_features (const OT::GSUBGPOS &g, { unsigned int feature_index = l.get_feature_index (i); - if (feature_tag == g.get_feature_tag (feature_index)) + if (feature_tag == c->g.get_feature_tag (feature_index)) { - feature_indexes->add (feature_index); + c->feature_indexes->add (feature_index); break; } } @@ -693,26 +705,23 @@ langsys_collect_features (const OT::GSUBGPOS &g, } static void -script_collect_features (const OT::GSUBGPOS &g, +script_collect_features (hb_collect_features_context_t *c, const OT::Script &s, const hb_tag_t *languages, - const hb_tag_t *features, - hb_set_t *feature_indexes /* OUT */) + const hb_tag_t *features) { if (!languages) { /* All languages. */ - langsys_collect_features (g, + langsys_collect_features (c, s.get_default_lang_sys (), - features, - feature_indexes); + features); unsigned int count = s.get_lang_sys_count (); for (unsigned int language_index = 0; language_index < count; language_index++) - langsys_collect_features (g, + langsys_collect_features (c, s.get_lang_sys (language_index), - features, - feature_indexes); + features); } else { @@ -720,10 +729,9 @@ script_collect_features (const OT::GSUBGPOS &g, { unsigned int language_index; if (s.find_lang_sys_index (*languages, &language_index)) - langsys_collect_features (g, + langsys_collect_features (c, s.get_lang_sys (language_index), - features, - feature_indexes); + features); } } } @@ -741,29 +749,27 @@ hb_ot_layout_collect_features (hb_face_t *face, const hb_tag_t *features, hb_set_t *feature_indexes /* OUT */) { - const OT::GSUBGPOS &g = get_gsubgpos_table (face, table_tag); + hb_collect_features_context_t c (face, table_tag, feature_indexes); if (!scripts) { /* All scripts. */ - unsigned int count = g.get_script_count (); + unsigned int count = c.g.get_script_count (); for (unsigned int script_index = 0; script_index < count; script_index++) - script_collect_features (g, - g.get_script (script_index), + script_collect_features (&c, + c.g.get_script (script_index), languages, - features, - feature_indexes); + features); } else { for (; *scripts; scripts++) { unsigned int script_index; - if (g.find_script_index (*scripts, &script_index)) - script_collect_features (g, - g.get_script (script_index), + if (c.g.find_script_index (*scripts, &script_index)) + script_collect_features (&c, + c.g.get_script (script_index), languages, - features, - feature_indexes); + features); } } } commit c237cdfcc74d33f77b2399b4d08228c2fcf50df5 Author: Behdad Esfahbod <beh...@behdad.org> Date: Thu Oct 25 21:17:30 2018 -0700 [lookup] Fold another function inline diff --git a/src/hb-ot-layout.cc b/src/hb-ot-layout.cc index 787ef13b..ece7f89d 100644 --- a/src/hb-ot-layout.cc +++ b/src/hb-ot-layout.cc @@ -656,31 +656,6 @@ hb_ot_layout_table_get_lookup_count (hb_face_t *face, } static void -_hb_ot_layout_collect_lookups_lookups (hb_face_t *face, - hb_tag_t table_tag, - unsigned int feature_index, - hb_set_t *lookup_indexes /* OUT */) -{ - unsigned int lookup_indices[32]; - unsigned int offset, len; - - offset = 0; - do { - len = ARRAY_LENGTH (lookup_indices); - hb_ot_layout_feature_get_lookups (face, - table_tag, - feature_index, - offset, &len, - lookup_indices); - - for (unsigned int i = 0; i < len; i++) - lookup_indexes->add (lookup_indices[i]); - - offset += len; - } while (len == ARRAY_LENGTH (lookup_indices)); -} - -static void langsys_collect_features (const OT::GSUBGPOS &g, const OT::LangSys &l, const hb_tag_t *features, @@ -808,8 +783,27 @@ hb_ot_layout_collect_lookups (hb_face_t *face, { hb_auto_t<hb_set_t> feature_indexes; hb_ot_layout_collect_features (face, table_tag, scripts, languages, features, &feature_indexes); - for (hb_codepoint_t feature_index = HB_SET_VALUE_INVALID; hb_set_next (&feature_indexes, &feature_index);) - _hb_ot_layout_collect_lookups_lookups (face, table_tag, feature_index, lookup_indexes); + for (hb_codepoint_t feature_index = HB_SET_VALUE_INVALID; + hb_set_next (&feature_indexes, &feature_index);) + { + unsigned int lookup_indices[32]; + unsigned int offset, len; + + offset = 0; + do { + len = ARRAY_LENGTH (lookup_indices); + hb_ot_layout_feature_get_lookups (face, + table_tag, + feature_index, + offset, &len, + lookup_indices); + + for (unsigned int i = 0; i < len; i++) + lookup_indexes->add (lookup_indices[i]); + + offset += len; + } while (len == ARRAY_LENGTH (lookup_indices)); + } } /** commit fe5520ddea3941f7a72888d908fd2b895e2f388e Author: Behdad Esfahbod <beh...@behdad.org> Date: Thu Oct 25 20:58:34 2018 -0700 [layout] More prep work to memoize collect_features() work diff --git a/src/hb-ot-layout.cc b/src/hb-ot-layout.cc index d4bb280f..787ef13b 100644 --- a/src/hb-ot-layout.cc +++ b/src/hb-ot-layout.cc @@ -718,29 +718,24 @@ langsys_collect_features (const OT::GSUBGPOS &g, } static void -_hb_ot_layout_collect_features_languages (hb_face_t *face, - hb_tag_t table_tag, - unsigned int script_index, - const hb_tag_t *languages, - const hb_tag_t *features, - hb_set_t *feature_indexes /* OUT */) +script_collect_features (const OT::GSUBGPOS &g, + const OT::Script &s, + const hb_tag_t *languages, + const hb_tag_t *features, + hb_set_t *feature_indexes /* OUT */) { - const OT::GSUBGPOS &g = get_gsubgpos_table (face, table_tag); if (!languages) { /* All languages. */ langsys_collect_features (g, - g.get_script (script_index).get_default_lang_sys (), + s.get_default_lang_sys (), features, feature_indexes); - unsigned int count = hb_ot_layout_script_get_language_tags (face, - table_tag, - script_index, - 0, nullptr, nullptr); + unsigned int count = s.get_lang_sys_count (); for (unsigned int language_index = 0; language_index < count; language_index++) langsys_collect_features (g, - g.get_script (script_index).get_lang_sys (language_index), + s.get_lang_sys (language_index), features, feature_indexes); } @@ -749,14 +744,9 @@ _hb_ot_layout_collect_features_languages (hb_face_t *face, for (; *languages; languages++) { unsigned int language_index; - if (hb_ot_layout_script_select_language (face, - table_tag, - script_index, - 1, - languages, - &language_index)) + if (s.find_lang_sys_index (*languages, &language_index)) langsys_collect_features (g, - g.get_script (script_index).get_lang_sys (language_index), + s.get_lang_sys (language_index), features, feature_indexes); } @@ -776,35 +766,29 @@ hb_ot_layout_collect_features (hb_face_t *face, const hb_tag_t *features, hb_set_t *feature_indexes /* OUT */) { + const OT::GSUBGPOS &g = get_gsubgpos_table (face, table_tag); if (!scripts) { /* All scripts. */ - unsigned int count = hb_ot_layout_table_get_script_tags (face, - table_tag, - 0, nullptr, nullptr); + unsigned int count = g.get_script_count (); for (unsigned int script_index = 0; script_index < count; script_index++) - _hb_ot_layout_collect_features_languages (face, - table_tag, - script_index, - languages, - features, - feature_indexes); + script_collect_features (g, + g.get_script (script_index), + languages, + features, + feature_indexes); } else { for (; *scripts; scripts++) { unsigned int script_index; - if (hb_ot_layout_table_find_script (face, - table_tag, - *scripts, - &script_index)) - _hb_ot_layout_collect_features_languages (face, - table_tag, - script_index, - languages, - features, - feature_indexes); + if (g.find_script_index (*scripts, &script_index)) + script_collect_features (g, + g.get_script (script_index), + languages, + features, + feature_indexes); } } } commit e8e67503ff0a50eb10ad410d6a76a282ea494cf4 Author: Behdad Esfahbod <beh...@behdad.org> Date: Thu Oct 25 20:48:20 2018 -0700 [lookup] More prep work for memoizing collect_features https://github.com/harfbuzz/harfbuzz/pull/1317 diff --git a/src/hb-ot-layout-common.hh b/src/hb-ot-layout-common.hh index 98f6a079..c9a87ce8 100644 --- a/src/hb-ot-layout-common.hh +++ b/src/hb-ot-layout-common.hh @@ -277,6 +277,8 @@ struct Script { return langSys.find_index (tag, index); } inline bool has_default_lang_sys (void) const { return defaultLangSys != 0; } + inline const LangSys& get_default_lang_sys (unsigned int i) const + { return get_default_lang_sys (); } inline const LangSys& get_default_lang_sys (void) const { return this+defaultLangSys; } inline bool subset (hb_subset_context_t *c) const diff --git a/src/hb-ot-layout.cc b/src/hb-ot-layout.cc index 338ca649..d4bb280f 100644 --- a/src/hb-ot-layout.cc +++ b/src/hb-ot-layout.cc @@ -681,40 +681,38 @@ _hb_ot_layout_collect_lookups_lookups (hb_face_t *face, } static void -_hb_ot_layout_collect_features_features (hb_face_t *face, - hb_tag_t table_tag, - unsigned int script_index, - unsigned int language_index, - const hb_tag_t *features, - hb_set_t *feature_indexes /* OUT */) +langsys_collect_features (const OT::GSUBGPOS &g, + const OT::LangSys &l, + const hb_tag_t *features, + hb_set_t *feature_indexes /* OUT */) { if (!features) { - unsigned int required_feature_index; - if (hb_ot_layout_language_get_required_feature (face, - table_tag, - script_index, - language_index, - &required_feature_index, - nullptr)) - feature_indexes->add (required_feature_index); - - const OT::GSUBGPOS &g = get_gsubgpos_table (face, table_tag); - const OT::LangSys &l = g.get_script (script_index).get_lang_sys (language_index); + /* All features. */ + unsigned int index = l.get_required_feature_index (); + if (index != HB_OT_LAYOUT_NO_FEATURE_INDEX) + feature_indexes->add (index); + l.add_feature_indexes_to (feature_indexes); } else { + /* Ugh. Any faster way? */ for (; *features; features++) { + hb_tag_t feature_tag = *features; unsigned int feature_index; - if (hb_ot_layout_language_find_feature (face, - table_tag, - script_index, - language_index, - *features, - &feature_index)) - feature_indexes->add (feature_index); + unsigned int num_features = l.get_feature_count (); + for (unsigned int i = 0; i < num_features; i++) + { + unsigned int feature_index = l.get_feature_index (i); + + if (feature_tag == g.get_feature_tag (feature_index)) + { + feature_indexes->add (feature_index); + break; + } + } } } } @@ -727,27 +725,24 @@ _hb_ot_layout_collect_features_languages (hb_face_t *face, const hb_tag_t *features, hb_set_t *feature_indexes /* OUT */) { - _hb_ot_layout_collect_features_features (face, - table_tag, - script_index, - HB_OT_LAYOUT_DEFAULT_LANGUAGE_INDEX, - features, - feature_indexes); - + const OT::GSUBGPOS &g = get_gsubgpos_table (face, table_tag); if (!languages) { - /* All languages */ + /* All languages. */ + langsys_collect_features (g, + g.get_script (script_index).get_default_lang_sys (), + features, + feature_indexes); + unsigned int count = hb_ot_layout_script_get_language_tags (face, table_tag, script_index, 0, nullptr, nullptr); for (unsigned int language_index = 0; language_index < count; language_index++) - _hb_ot_layout_collect_features_features (face, - table_tag, - script_index, - language_index, - features, - feature_indexes); + langsys_collect_features (g, + g.get_script (script_index).get_lang_sys (language_index), + features, + feature_indexes); } else { @@ -760,12 +755,10 @@ _hb_ot_layout_collect_features_languages (hb_face_t *face, 1, languages, &language_index)) - _hb_ot_layout_collect_features_features (face, - table_tag, - script_index, - language_index, - features, - feature_indexes); + langsys_collect_features (g, + g.get_script (script_index).get_lang_sys (language_index), + features, + feature_indexes); } } } @@ -785,7 +778,7 @@ hb_ot_layout_collect_features (hb_face_t *face, { if (!scripts) { - /* All scripts */ + /* All scripts. */ unsigned int count = hb_ot_layout_table_get_script_tags (face, table_tag, 0, nullptr, nullptr); commit 96828b97a8fc2c50721ce040bdde63c462908791 Author: Behdad Esfahbod <beh...@behdad.org> Date: Thu Oct 25 20:34:29 2018 -0700 [layout] Minor We were returning the accelerator's lookup count. Returns table's. They are the same except for OOM cases. Just shorter code. diff --git a/src/hb-ot-layout.cc b/src/hb-ot-layout.cc index 7e08c2a0..338ca649 100644 --- a/src/hb-ot-layout.cc +++ b/src/hb-ot-layout.cc @@ -652,19 +652,7 @@ unsigned int hb_ot_layout_table_get_lookup_count (hb_face_t *face, hb_tag_t table_tag) { - if (unlikely (!hb_ot_shaper_face_data_ensure (face))) return 0; - switch (table_tag) - { - case HB_OT_TAG_GSUB: - { - return hb_ot_face_data (face)->GSUB->lookup_count; - } - case HB_OT_TAG_GPOS: - { - return hb_ot_face_data (face)->GPOS->lookup_count; - } - } - return 0; + return get_gsubgpos_table (face, table_tag).get_lookup_count (); } static void commit 73449cd213c3a12468e99b9c3d840fc60a334902 Author: Behdad Esfahbod <beh...@behdad.org> Date: Thu Oct 25 20:32:05 2018 -0700 [layout] Fold one function inline Preparation for fixing https://github.com/harfbuzz/harfbuzz/pull/1317 diff --git a/src/hb-ot-layout.cc b/src/hb-ot-layout.cc index 128253da..7e08c2a0 100644 --- a/src/hb-ot-layout.cc +++ b/src/hb-ot-layout.cc @@ -555,19 +555,6 @@ hb_ot_layout_language_get_required_feature (hb_face_t *face, return l.has_required_feature (); } -static void -_hb_ot_layout_language_add_feature_indexes_to (hb_face_t *face, - hb_tag_t table_tag, - unsigned int script_index, - unsigned int language_index, - hb_set_t *feature_indexes /* OUT */) -{ - const OT::GSUBGPOS &g = get_gsubgpos_table (face, table_tag); - const OT::LangSys &l = g.get_script (script_index).get_lang_sys (language_index); - l.add_feature_indexes_to (feature_indexes); -} - - unsigned int hb_ot_layout_language_get_feature_indexes (hb_face_t *face, hb_tag_t table_tag, @@ -724,12 +711,9 @@ _hb_ot_layout_collect_features_features (hb_face_t *face, nullptr)) feature_indexes->add (required_feature_index); - /* All features */ - _hb_ot_layout_language_add_feature_indexes_to (face, - table_tag, - script_index, - language_index, - feature_indexes); + const OT::GSUBGPOS &g = get_gsubgpos_table (face, table_tag); + const OT::LangSys &l = g.get_script (script_index).get_lang_sys (language_index); + l.add_feature_indexes_to (feature_indexes); } else { _______________________________________________ HarfBuzz mailing list HarfBuzz@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/harfbuzz