[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[2268] 2009-06-05 Colin D Bennett <address@hidden>
From: |
Vladimir Serbinenko |
Subject: |
[2268] 2009-06-05 Colin D Bennett <address@hidden> |
Date: |
Fri, 05 Jun 2009 21:22:14 +0000 |
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;
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [2268] 2009-06-05 Colin D Bennett <address@hidden>,
Vladimir Serbinenko <=