From e53d77142ac4ecbe38ab3235491fa93cb7ff16ab Mon Sep 17 00:00:00 2001
From: Behdad Esfahbod <behdad@behdad.org>
Date: Fri, 21 May 2010 13:32:38 +0100
Subject: [PATCH] Speed up feature mask setting

Patch from Jonathan Kew.
---
 src/hb-ot-shape.cc | 31 +++++++++++++++++++++++++------
 1 file changed, 25 insertions(+), 6 deletions(-)

diff --git a/src/hb-ot-shape.cc b/src/hb-ot-shape.cc
index 6a8c7ec..84f3432 100644
--- a/src/hb-ot-shape.cc
+++ b/src/hb-ot-shape.cc
@@ -122,6 +122,7 @@ setup_lookups (hb_face_t    *face,
     buffer->info[i].mask = 1;
 
   unsigned int last_bit_used = 1;
+  unsigned int global_values = 0;
   for (i = 0; i < num_features; i++)
   {
     unsigned int bits_needed = _hb_bit_storage (features[i].value);
@@ -136,15 +137,33 @@ setup_lookups (hb_face_t    *face,
 					    &feature_index))
       add_feature (face, table_tag, feature_index, mask, lookups, num_lookups, room_lookups);
 
-    /* Turn mask on in the buffer, the über-slow way! */
-    unsigned int count = buffer->len;
-    for (unsigned int j = 0; j < count; j++) {
-        unsigned int cluster = buffer->info[j].cluster;
-	if (features[i].start <= cluster && cluster < features[i].end)
-	  buffer->info[j].mask |= value;
+    if (features[i].start == 0 && features[i].end == (unsigned int)-1)
+      global_values |= value;
+    else
+    {
+      unsigned int start = features[i].start, end = features[i].end;
+      unsigned int a = 0, b = buffer->len;
+      while (a < b)
+      {
+        unsigned int h = a + ((b - a) / 2);
+        if (buffer->info[h].cluster < start)
+          a = h + 1;
+        else
+          b = h;
+      }
+      unsigned int count = buffer->len;
+      for (unsigned int j = a; j < count && buffer->info[j].cluster < end; j++)
+        buffer->info[j].mask |= value;
     }
   }
 
+  if (global_values)
+  {
+    unsigned int count = buffer->len;
+    for (unsigned int j = 0; j < count; j++)
+      buffer->info[j].mask |= global_values;
+  }
+
   qsort (lookups, *num_lookups, sizeof (lookups[0]), cmp_lookups);
 
   if (*num_lookups)
-- 
2.7.4