[HarfBuzz] harfbuzz: Branch 'master'

[Behdad Esfahbod]

 src/hb-ot-layout-gpos-table.hh |   21 ++++++++++++++++-----
 1 file changed, 16 insertions(+), 5 deletions(-)

New commits:
commit 67dfa8c7c2f2e9040a9c60c680f739ada4a35fb5
Author: Behdad Esfahbod <behdad at behdad.org>
Date:   Mon Jan 19 17:00:31 2015 -0800

    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.

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<PairValueRecord> (arrayZ);
+    const PairValueRecord *record_array = CastP<PairValueRecord> (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<PairValueRecord> (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<PairValueRecord> (record, record_size);
     }
 
     return TRACE_RETURN (false);