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
=== 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 <co...@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 <fziel...@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;
signature.asc
Description: PGP signature
_______________________________________________ Grub-devel mailing list Grub-devel@gnu.org http://lists.gnu.org/mailman/listinfo/grub-devel
