Skip to contentSkip to conversation

Faster glyph lookup by BMP index

PATCH In review Vladimir 'φ-coder/phcoder' Serbinenko 3 participants 4 messages Nov 29, 2009 – Dec 4, 2009

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Faster glyph lookup by BMP index

Hello. Basic Multilingual Plane is range of Unicode characters in 0-65535 and it contains most of the characters needed by most of the languages of the world. By keeping an array with pointers to such characters at the cost of 128KiB per font we can almost instantenously lookup characters which are likely to be used in grub. Available in experimental

Signature · 2 lines
Regards
Vladimir 'φ-coder/phcoder' Serbinenko

=== added file 'ChangeLog.bmpidx'

ChangeLog.bmpidx +9 -0
@@ -0,0 +1,9 @@
+2009-11-29  Vladimir Serbinenko  <[email protected]>
+
+	Optimise glyph lookup by Basic Multilingual Plane lookup array.
+
+	* font/font.c (struct grub_font): New member 'bmp_idx'.
+	(font_init): Initialise 'bmp_idx'.
+	(load_font_index): Fill 'bmp_idx'.
+	(find_glyph): Make inline. Use bmp_idx for BMP characters.
+

=== modified file 'font/font.c'

font.c +24 -2
@@ -58,6 +58,7 @@ struct grub_font
   short leading;
   grub_uint32_t num_chars;
   struct char_index_entry *char_index;
+  grub_uint16_t *bmp_idx;
 };
 
 /* Definition of font registry.  */
@@ -180,6 +181,7 @@ font_init (grub_font_t font)
   font->descent = 0;
   font->num_chars = 0;
   font->char_index = 0;
+  font->bmp_idx = 0;
 }
 
 /* Open the next section in the file.
@@ -273,6 +275,14 @@ load_font_index (grub_file_t file, grub_
                                   * sizeof (struct char_index_entry));
   if (! font->char_index)
     return 1;
+  font->bmp_idx = grub_malloc (0x10000 * sizeof (grub_uint16_t));
+  if (! font->bmp_idx)
+    {
+      grub_free (font->char_index);
+      return 1;
+    }
+  grub_memset (font->bmp_idx, 0xff, 0x10000 * sizeof (grub_uint16_t));
+
 
 #if FONT_DEBUG >= 2
   grub_printf("num_chars=%d)\n", font->num_chars);
@@ -299,6 +309,9 @@ load_font_index (grub_file_t file, grub_
           return 1;
         }
 
+      if (entry->code < 0x10000)
+	font->bmp_idx[entry->code] = i;
+
       last_code = entry->code;
 
       /* Read storage flags byte.  */
@@ -594,7 +607,7 @@ read_be_int16 (grub_file_t file, grub_in
 
 /* Return a pointer to the character index entry for the glyph corresponding to
    the codepoint CODE in the font FONT.  If not found, return zero.  */
-static struct char_index_entry *
+static inline struct char_index_entry *
 find_glyph (const grub_font_t font, grub_uint32_t code)
 {
   struct char_index_entry *table;
@@ -602,8 +615,17 @@ find_glyph (const grub_font_t font, grub
   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;
+
+  /* Use BMP index if possible.  */
+  if (code < 0x10000)
+    {
+      if (font->bmp_idx[code] == 0xffff)
+	return 0;
+      return &table[font->bmp_idx[code]];
+    }
+
+  /* Do a binary search in `char_index', which is ordered by code point.  */
   lo = 0;
   hi = font->num_chars - 1;
 
#1 lore raw

Is this table stored in the file or built during font load? 128KiB in memory is no issue at all on modern systems, 128KiB in a file is somewhat more troublesome since it won't fit in a boot sector, is a big chunk of a rescue diskette, and the I/O cost is noticeable. These glyphs are stored in sorted order in the file, correct? May I suggest that only every Nth index be stored in the file header (where N = 16 for example) and the intermediate ones discovered at runtime, in those subranges containing a character actually used (and the indexes and character data for those glyphs are then cached in memory)? This also means block reads from the file (block length is easily calculated as the difference of two adjacent indices) instead of extraction of individual characters, most languages tend to have good locality so this should also be a win. Or is the entire font file cached in memory anyway?

2009/11/29 Vladimir 'φ-coder/phcoder' Serbinenko <[email protected]>:

Quoted 18 lines

Hello. Basic Multilingual Plane is range of Unicode characters in 0-65535 and it contains most of the characters needed by most of the languages of the world. By keeping an array with pointers to such characters at the cost of 128KiB per font we can almost instantenously lookup characters which are likely to be used in grub. Available in experimental

--
Regards
Vladimir 'φ-coder/phcoder' Serbinenko

_______________________________________________
Grub-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/grub-devel

#2 lore raw
Quoted 1 line · [email protected] wrote:

Is this table stored in the file or built during font load?

This table is generated on file load

Quoted 29 lines

2009/11/29 Vladimir 'φ-coder/phcoder' Serbinenko <[email protected]>:

Quoted 12 lines

Hello. Basic Multilingual Plane is range of Unicode characters in 0-65535 and it contains most of the characters needed by most of the languages of the world. By keeping an array with pointers to such characters at the cost of 128KiB per font we can almost instantenously lookup characters which are likely to be used in grub. Available in experimental

--
Regards
Vladimir 'φ-coder/phcoder' Serbinenko

Quoted 7 lines

_______________________________________________
Grub-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/grub-devel

_______________________________________________
Grub-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/grub-devel

Signature · 2 lines
Regards
Vladimir 'φ-coder/phcoder' Serbinenko
#3 lore raw
In reply to Vladimir 'φ-coder/phcoder' Serbinenko
Quoted 6 lines · Vladimir 'φ-coder/phcoder' Serbinenko

Hello. Basic Multilingual Plane is range of Unicode characters in 0-65535 and it contains most of the characters needed by most of the languages of the world. By keeping an array with pointers to such characters at the cost of 128KiB per font we can almost instantenously lookup characters which are likely to be used in grub. Available in experimental

Seems fine (for trunk as well), just one thing:

font.c find_glyph (const grub_font_t font, grub · line 623

Quoted 8 lines
font.c +6 -0
+  grub_memset (font->bmp_idx, 0xff, 0x10000 * sizeof (grub_uint16_t));
[...]
+      if (entry->code < 0x10000)
[...]
+  /* Use BMP index if possible.  */
+  if (code < 0x10000)
+    {
+      if (font->bmp_idx[code] == 0xffff)

Could these be macroified? Makes it harder to do mistakes in the future.

Signature · 5 lines
Robert Millan

  The DRM opt-in fallacy: "Your data belongs to us. We will decide when (and
  how) you may access your data; but nobody's threatening your freedom: we
  still allow you to remove your data and not access it at all."