src/hb-ot-layout-gsubgpos-private.hh | 37 ++++++++++++++++++++++-------------
1 file changed, 24 insertions(+), 13 deletions(-)
New commits:
commit 621c49cb8657a79ee6897c4d313d0e825b2b228f
Author: Behdad Esfahbod <beh...@behdad.org>
Date: Wed Oct 4 15:06:48 2017 +0200
Improve performance of ligature component matching
This O(N^2) was introduced in 8b2c94c43fd335b944d5e5487265706b8e0f9041.
Make it O(N).
diff --git a/src/hb-ot-layout-gsubgpos-private.hh
b/src/hb-ot-layout-gsubgpos-private.hh
index aa0862ad..cedf96e3 100644
--- a/src/hb-ot-layout-gsubgpos-private.hh
+++ b/src/hb-ot-layout-gsubgpos-private.hh
@@ -764,6 +764,12 @@ static inline bool match_input (hb_apply_context_t *c,
unsigned int first_lig_id = _hb_glyph_info_get_lig_id (&buffer->cur());
unsigned int first_lig_comp = _hb_glyph_info_get_lig_comp (&buffer->cur());
+ enum {
+ LIGBASE_NOT_CHECKED,
+ LIGBASE_MAY_NOT_SKIP,
+ LIGBASE_MAY_SKIP
+ } ligbase = LIGBASE_NOT_CHECKED;
+
match_positions[0] = buffer->idx;
for (unsigned int i = 1; i < count; i++)
{
@@ -783,29 +789,34 @@ static inline bool match_input (hb_apply_context_t *c,
{
/* ...unless, we are attached to a base ligature and that base
* ligature is ignorable. */
- bool found = false;
- const hb_glyph_info_t *out = buffer->out_info;
- unsigned int j = buffer->out_len;
- while (j && _hb_glyph_info_get_lig_id (&out[j - 1]) == first_lig_id)
+ if (ligbase == LIGBASE_NOT_CHECKED)
{
- if (_hb_glyph_info_get_lig_comp (&out[j - 1]) == 0)
+ bool found = false;
+ const hb_glyph_info_t *out = buffer->out_info;
+ unsigned int j = buffer->out_len;
+ while (j && _hb_glyph_info_get_lig_id (&out[j - 1]) == first_lig_id)
{
+ if (_hb_glyph_info_get_lig_comp (&out[j - 1]) == 0)
+ {
+ j--;
+ found = true;
+ break;
+ }
j--;
- found = true;
- break;
}
- j--;
- }
- if (!found)
- return_trace (false);
+ if (found && skippy_iter.may_skip (c, out[j]) ==
hb_apply_context_t::matcher_t::SKIP_YES)
+ ligbase = LIGBASE_MAY_SKIP;
+ else
+ ligbase = LIGBASE_MAY_NOT_SKIP;
+ }
- if (skippy_iter.may_skip (c, out[j]) !=
hb_apply_context_t::matcher_t::SKIP_YES)
+ if (ligbase == LIGBASE_MAY_NOT_SKIP)
return_trace (false);
}
}
else
- {
+ {
/* If first component was NOT attached to a previous ligature component,
* all subsequent components should also NOT be attached to any ligature
* component, unless they are attached to the first component itself! */
_______________________________________________
HarfBuzz mailing list
HarfBuzz@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/harfbuzz
