[PATCH] Faster text rendering by optimizing font glyph lookup

[Colin D Bennett <colin@gibibit.com>]

[-- Attachment #1.1: Type: text/plain, Size: 860 bytes --]

This patch greatly—*tremendously*, even, if higher-numbered Unicode
characters are used—speeds up retrieving a glyph for a particular
Unicode character.  This makes text rendering in general much faster.

My text benchmark shows the new text rendering speed is somewhere from
2.6x to 31x of the previous speed.  Basically, PFF2 font files are now
required to have the character index ordered in ascending order of code
point.

Fonts created by 'grub-mkfont' already satisfy this requirement.  Fonts
created by my old Java 'fonttool' do not, and cannot be used any longer.

The font loader verifies that fonts fulfill the character ordering
requirement, refusing to load invalid fonts, but the primary change is
in the 'find_glyph()' function, which now uses a binary search rather
than a linear search to find the glyph.

Regards,
Colin

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1.2: font-optimization.patch --]
[-- Type: text/x-patch, Size: 2668 bytes --]

=== modified file 'ChangeLog'
--- ChangeLog	2009-02-04 10:52:25 +0000
+++ ChangeLog	2009-02-08 21:46:42 +0000
@@ -1,3 +1,14 @@
+2009-02-08  Colin D Bennett  <colin@gibibit.com>
+
+	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-02-04  Felix Zielcke  <fzielcke@z-51.de>
 
 	util/getroot.c (grub_util_get_grub_dev): Add support for /dev/mdNpN and

=== modified file 'font/font.c'
--- font/font.c	2009-01-19 17:09:53 +0000
+++ font/font.c	2009-02-08 19:50:58 +0000
@@ -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;
-
-  /* Do a linear search.  */
-  for (i = 0; i < len; i++)
+  struct char_index_entry *table;
+  grub_size_t lo;
+  grub_size_t hi;
+  grub_size_t mid;
+
+  /* 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;


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 197 bytes --]