master 7af94bacd7a: Optimize format 12 cmap table lookup

[Po Lu]

branch: master
commit 7af94bacd7a1be6417390ce9523f0e2524deb8e0
Author: Po Lu <luangruo@yahoo.com>
Commit: Po Lu <luangruo@yahoo.com>

    Optimize format 12 cmap table lookup
    
    * src/sfnt.c (sfnt_compare_char): New function.
    (sfnt_lookup_glyph_12): Detect ``large'' cmap tables of format
    12 and perform a binary search.  Such tables are frequently
    provided by CJK fonts.
---
 src/sfnt.c | 38 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 38 insertions(+)

diff --git a/src/sfnt.c b/src/sfnt.c
index 14e353013cd..e71ff9ae101 100644
--- a/src/sfnt.c
+++ b/src/sfnt.c
@@ -1286,6 +1286,19 @@ sfnt_lookup_glyph_8 (sfnt_char character,
   return 0;
 }
 
+/* Compare the sfnt_char A with B's end code.  Employed to bisect
+   through a format 12 table.  */
+
+static int
+sfnt_compare_char (const void *a, const void *b)
+{
+  struct sfnt_cmap_format_8_or_12_group *group;
+
+  group = (struct sfnt_cmap_format_8_or_12_group *) b;
+
+  return ((int) *((sfnt_char *) a)) - group->end_char_code;
+}
+
 /* Look up the glyph corresponding to CHARACTER in the format 12 cmap
    FORMAT12.  Return 0 if no glyph was found.  */
 
@@ -1294,10 +1307,35 @@ sfnt_lookup_glyph_12 (sfnt_char character,
                      struct sfnt_cmap_format_12 *format12)
 {
   uint32_t i;
+  struct sfnt_cmap_format_8_or_12_group *group;
 
   if (character > 0xffffffff)
     return 0;
 
+  if (format12->num_groups > 64)
+    {
+      /* This table is large, likely supplied by a CJK or similar
+        font.  Perform a binary search.  */
+
+      /* Find the group whose END_CHAR_CODE is greater than or equal
+        to CHARACTER.  */
+
+      group = sfnt_bsearch_above (&character, format12->groups,
+                                 format12->num_groups,
+                                 sizeof format12->groups[0],
+                                 sfnt_compare_char);
+
+      if (group->start_char_code > character)
+       /* No glyph matches this group.  */
+       return 0;
+
+      /* Otherwise, use this group to map the character to a
+        glyph.  */
+      return (group->start_glyph_code
+             + character
+             - group->start_char_code);
+    }
+
   for (i = 0; i < format12->num_groups; ++i)
     {
       if (format12->groups[i].start_char_code <= character