grub-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[PATCH] Faster glyph lookup by BMP index


From: Vladimir 'φ-coder/phcoder' Serbinenko
Subject: [PATCH] Faster glyph lookup by BMP index
Date: Sun, 29 Nov 2009 15:29:18 +0100
User-agent: Mozilla-Thunderbird 2.0.0.22 (X11/20091109)

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

=== added file 'ChangeLog.bmpidx'
--- ChangeLog.bmpidx    1970-01-01 00:00:00 +0000
+++ ChangeLog.bmpidx    2009-11-29 14:17:03 +0000
@@ -0,0 +1,9 @@
+2009-11-29  Vladimir Serbinenko  <address@hidden>
+
+       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/font.c 2009-07-20 17:37:37 +0000
+++ font/font.c 2009-11-29 13:24:58 +0000
@@ -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;
 

Attachment: signature.asc
Description: OpenPGP digital signature


reply via email to

[Prev in Thread] Current Thread [Next in Thread]