[2268] 2009-06-05 Colin D Bennett <address@hidden>

[Vladimir Serbinenko]

Revision: 2268
          http://svn.sv.gnu.org/viewvc/?view=rev&root=grub&revision=2268
Author:   phcoder
Date:     2009-06-05 21:22:14 +0000 (Fri, 05 Jun 2009)
Log Message:
-----------
2009-06-05  Colin D Bennett  <address@hidden>

        Optimized font character lookup using binary search instead of linear
        search.  Fonts now are required to have the character index ordered by
        code point.

        * font/font.c (load_font_index): Verify that fonts have ordered
        character indices.
        (find_glyph): Use binary search instead of linear search to find a
        character in a font.

Modified Paths:
--------------
    trunk/grub2/ChangeLog
    trunk/grub2/font/font.c

Modified: trunk/grub2/ChangeLog
===================================================================
--- trunk/grub2/ChangeLog       2009-06-05 21:00:43 UTC (rev 2267)
+++ trunk/grub2/ChangeLog       2009-06-05 21:22:14 UTC (rev 2268)
@@ -1,3 +1,14 @@
+2009-06-05  Colin D Bennett  <address@hidden>
+
+       Optimized font character lookup using binary search instead of linear
+       search.  Fonts now are required to have the character index ordered by
+       code point.
+
+       * font/font.c (load_font_index): Verify that fonts have ordered
+       character indices.
+       (find_glyph): Use binary search instead of linear search to find a
+       character in a font.
+
 2009-06-05  Michael Scherer  <address@hidden>
 
        * fs/hfsplus.c (grub_hfsplus_mount): Determine if the filesystem

Modified: trunk/grub2/font/font.c
===================================================================
--- trunk/grub2/font/font.c     2009-06-05 21:00:43 UTC (rev 2267)
+++ trunk/grub2/font/font.c     2009-06-05 21:22:14 UTC (rev 2268)
@@ -249,6 +249,7 @@
                  grub_font *font)
 {
   unsigned i;
+  grub_uint32_t last_code;
 
 #if FONT_DEBUG >= 2
   grub_printf("load_font_index(sect_length=%d)\n", sect_length);
@@ -277,6 +278,8 @@
   grub_printf("num_chars=%d)\n", font->num_chars);
 #endif
 
+  last_code = 0;
+
   /* Load the character index data from the file.  */
   for (i = 0; i < font->num_chars; i++)
     {
@@ -287,6 +290,17 @@
         return 1;
       entry->code = grub_be_to_cpu32 (entry->code);
 
+      /* Verify that characters are in ascending order.  */
+      if (i != 0 && entry->code <= last_code)
+        {
+          grub_error (GRUB_ERR_BAD_FONT,
+                      "Font characters not in ascending order: %u <= %u",
+                      entry->code, last_code);
+          return 1;
+        }
+
+      last_code = entry->code;
+
       /* Read storage flags byte.  */
       if (grub_file_read (file, (char *) &entry->storage_flags, 1) != 1)
         return 1;
@@ -583,15 +597,25 @@
 static struct char_index_entry *
 find_glyph (const grub_font_t font, grub_uint32_t code)
 {
-  grub_uint32_t i;
-  grub_uint32_t len = font->num_chars;
-  struct char_index_entry *table = font->char_index;
+  struct char_index_entry *table;
+  grub_size_t lo;
+  grub_size_t hi;
+  grub_size_t mid;
 
-  /* Do a linear search.  */
-  for (i = 0; i < len; i++)
+  /* Do a binary search in `char_index', which is ordered by code point.  */
+  table = font->char_index;
+  lo = 0;
+  hi = font->num_chars - 1;
+
+  while (lo <= hi)
     {
-      if (table[i].code == code)
-        return &table[i];
+      mid = lo + (hi - lo) / 2;
+      if (code < table[mid].code)
+        hi = mid - 1;
+      else if (code > table[mid].code)
+        lo = mid + 1;
+      else
+        return &table[mid];
     }
 
   return 0;