From 67dfa8c7c2f2e9040a9c60c680f739ada4a35fb5 Mon Sep 17 00:00:00 2001 From: Behdad Esfahbod Date: Mon, 19 Jan 2015 17:00:31 -0800 Subject: [PATCH] When matching second glyph of kerning pairs, use bsearch Roboto has glyphs (like 'F') that have 200 kerning pairs. Add a handcoded bsearch instead of previous linear search. This doesn't show much speedup though, apparently we spend the bulk of the time somewhere before here. --- src/hb-ot-layout-gpos-table.hh | 21 ++++++++++++++++----- 1 file changed, 16 insertions(+), 5 deletions(-) diff --git a/src/hb-ot-layout-gpos-table.hh b/src/hb-ot-layout-gpos-table.hh index 4255f5a..f7fef52 100644 --- a/src/hb-ot-layout-gpos-table.hh +++ b/src/hb-ot-layout-gpos-table.hh @@ -602,12 +602,24 @@ struct PairSet unsigned int len2 = valueFormats[1].get_len (); unsigned int record_size = USHORT::static_size * (1 + len1 + len2); - const PairValueRecord *record = CastP (arrayZ); + const PairValueRecord *record_array = CastP (arrayZ); unsigned int count = len; - for (unsigned int i = 0; i < count; i++) + + /* Hand-coded bsearch. */ + if (unlikely (!count)) + return TRACE_RETURN (false); + hb_codepoint_t x = buffer->info[pos].codepoint; + int min = 0, max = (int) count - 1; + while (min <= max) { - /* TODO bsearch */ - if (buffer->info[pos].codepoint == record->secondGlyph) + int mid = (min + max) / 2; + const PairValueRecord *record = &StructAtOffset (record_array, record_size * mid); + hb_codepoint_t mid_x = record->secondGlyph; + if (x < mid_x) + max = mid - 1; + else if (x > mid_x) + min = mid + 1; + else { valueFormats[0].apply_value (c->font, c->direction, this, &record->values[0], buffer->cur_pos()); @@ -618,7 +630,6 @@ struct PairSet buffer->idx = pos; return TRACE_RETURN (true); } - record = &StructAtOffset (record, record_size); } return TRACE_RETURN (false); -- 2.7.4