[patch] added glyph caching

[Vesa Jääskeläinen]

Hi,

This patch adds glyph caching to GRUB 2. It functions like a hash table
with paging. If one hash table entry's page is full, new will be
allocated and linked to previous. When font module is unloaded, cache
will be freed. There is also a support to preload set of glyphs in order
to fasten glyph loading times.

It also fixes issue in gfxterm with unknown glyph's character length.
Problem caused incorrect rendering of menu entries.

Thanks,
Vesa Jääskeläinen

Index: ChangeLog
===================================================================
RCS file: /sources/grub/grub2/ChangeLog,v
retrieving revision 1.230
diff -u -r1.230 ChangeLog
--- ChangeLog   1 Apr 2006 19:22:58 -0000       1.230
+++ ChangeLog   6 Apr 2006 19:15:58 -0000
@@ -1,3 +1,25 @@
+2006-04-06  Vesa Jaaskelainen  <address@hidden>
+
+       * font/manager.c (GLYPH_CACHE_HASH_SIZE): New define.
+       (GLYPH_CACHE_MAX_PER_PAGE): Likewise.
+       (GLYPH_CACHE_PRELOAD): Likewise.
+       (GLYPH_CACHE_PRELOAD_START): Likewise.
+       (GLYPH_CACHE_PRELOAD_END): Likewise.
+       (glyph_cache_item): New structure.
+       (glyph_cache): Likewise.
+       (cache): New static variable.
+       (add_font): Added preloading of glyphs.
+       (get_hash): New function.
+       (cache_add_glyph): Likewise.
+       (cache_find_glyph): Likewise.
+       (cache_preload): Likewise.
+       (cache_clear): Likewise.
+       (grub_font_get_glyph): Added caching for glyphs.
+       (font_manager): Added cache clearing to module unloading.
+
+       * term/gfxterm.c (grub_gfxterm_getcharwidth): Fixed character 
+       length for unknown glyph.
+
 2006-04-01  Vesa Jaaskelainen  <address@hidden>
 
        * util/unifont2pff.rb: Removed unnecessary byte ordering.  Now
Index: font/manager.c
===================================================================
RCS file: /sources/grub/grub2/font/manager.c,v
retrieving revision 1.8
diff -u -r1.8 manager.c
--- font/manager.c      31 Mar 2006 13:32:52 -0000      1.8
+++ font/manager.c      6 Apr 2006 19:15:58 -0000
@@ -25,6 +25,17 @@
 #include <grub/mm.h>
 #include <grub/font.h>
 
+#define GLYPH_CACHE_HASH_SIZE          128
+#define GLYPH_CACHE_MAX_PER_PAGE        32
+
+/* Comment out this define if you want to disable preloading of glyphs.  */
+#define GLYPH_CACHE_PRELOAD
+
+#if defined(GLYPH_CACHE_PRELOAD)
+#define GLYPH_CACHE_PRELOAD_START      32
+#define GLYPH_CACHE_PRELOAD_END                127
+#endif
+
 struct entry
 {
   grub_uint32_t code;
@@ -39,7 +50,24 @@
   struct entry table[0];
 };
 
+struct glyph_cache_item
+{
+  grub_uint32_t code;
+  struct grub_font_glyph glyph;
+};
+    
+struct glyph_cache
+{
+  struct glyph_cache *next;
+  unsigned int count;
+  unsigned int max_count;
+  struct glyph_cache_item items[0];
+};
+
 static struct font *font_list;
+static struct glyph_cache *cache[GLYPH_CACHE_HASH_SIZE];
+
+static void cache_preload (struct font *font);
 
 static int
 add_font (const char *filename)
@@ -90,6 +118,10 @@
 
   font->next = font_list;
   font_list = font;
+  
+#if defined(GLYPH_CACHE_PRELOAD)
+  cache_preload (font);
+#endif
 
   return 1;
 
@@ -164,6 +196,146 @@
   glyph->baseline = (16 * 3) / 4;
 }
 
+/* Get hash for unicode character.  */
+static unsigned int
+get_hash (grub_uint32_t code)
+{
+  return code % GLYPH_CACHE_HASH_SIZE;
+}
+
+/* Add glyph to glyph cache.  */
+static int
+cache_add_glyph (grub_uint32_t code, grub_font_glyph_t glyph)
+{
+  unsigned int hash;
+  unsigned int i;
+  struct glyph_cache *ptr;
+  struct glyph_cache *last = NULL;
+  
+  /* Get hash index for code.  */
+  hash = get_hash (code);
+  
+  ptr = cache[hash];
+
+  /* Search for duplicates and for next free slot.  */
+  while (ptr != NULL)
+    {
+      /* Check for duplicates.  */
+      for (i = 0; i < ptr->count; i++)
+        if (ptr->items[i].code == code)
+          return 1;
+
+      /* Check if there is free slots.  */
+      if (ptr->count != ptr->max_count)
+        break;
+
+      /* Advance to next page.  */
+      last = ptr;
+      ptr = ptr->next;
+    }
+
+  /* No root cache or no free pages, add new page.  */
+  if (ptr == NULL)
+    {
+      ptr = grub_malloc (sizeof (struct glyph_cache)
+                         + (sizeof (struct glyph_cache_item)
+                            * GLYPH_CACHE_MAX_PER_PAGE));
+
+      if (grub_errno != GRUB_ERR_NONE)
+        return 0;
+
+      ptr->next = NULL;
+      ptr->count = 0;
+      ptr->max_count = GLYPH_CACHE_MAX_PER_PAGE;
+    }
+
+  /* Cache glyph.  */
+  ptr->items[ptr->count].code = code;
+  ptr->items[ptr->count].glyph = *glyph;
+  ptr->count++;
+
+  /* If there wasn't yet a root cache, set it.  */
+  if (cache[hash] == NULL)
+    cache[hash] = ptr;
+
+  return 1;
+}
+
+/* Search glyph matching character code from glyph cache.  */
+static int
+cache_find_glyph (grub_uint32_t code, grub_font_glyph_t glyph)
+{
+  unsigned int i;
+  unsigned int hash;
+  struct glyph_cache *ptr;
+  
+  /* Search glyph from cache.  */
+  hash = get_hash (code);
+  ptr = cache[hash];
+
+  while (ptr != NULL)
+    {
+      /* Search from this page.  */
+      for (i = 0; i < ptr->count; i++)
+        if (ptr->items[i].code == code)
+          {
+            *glyph = ptr->items[i].glyph;
+            return 1;
+          }
+
+      /* Advance to next page.  */
+      ptr = ptr->next;
+    }
+
+  /* No glyph found in cache.  */
+  return 0;
+}
+
+#if defined(GLYPH_CACHE_PRELOAD)
+/* Preload predefined range of glyhs to cache.  */
+static void
+cache_preload (struct font *font)
+{
+  struct entry *table = font->table;
+  struct grub_font_glyph tmp;  
+  unsigned int i;
+  
+  /* Scan for chars to preload.  */
+  for (i = 0; i < font->num; i++)
+    {
+      if (table[i].code < GLYPH_CACHE_PRELOAD_START)
+        continue;
+      
+      if (table[i].code > GLYPH_CACHE_PRELOAD_END)
+        break;
+      
+      grub_font_get_glyph (table[i].code, &tmp);      
+    }
+}
+#endif
+
+/* Clears cache by freeing up all entries.  */
+static void
+cache_clear (void)
+{
+  unsigned int i;
+  struct glyph_cache *ptr;
+  struct glyph_cache *tmp;
+  
+  for (i = 0; i < GLYPH_CACHE_HASH_SIZE; i++)
+    {
+      ptr = cache[i];
+      
+      while ((tmp = ptr) != NULL)
+        {
+          ptr = ptr->next;
+          grub_free (tmp);
+        }
+      
+      cache[i] = NULL;
+    }
+}
+
 /* Get a glyph corresponding to the codepoint CODE.  Always fill glyph
    information with something, even if no glyph is found.  */
 int
@@ -173,7 +345,9 @@
   struct font *font;
   grub_uint8_t bitmap[32];
 
-  /* FIXME: It is necessary to cache glyphs!  */
+  /* First, try to find glyph from cache.  */
+  if (cache_find_glyph (code, glyph))
+    return 1;
   
  restart:
   for (font = font_list; font; font = font->next)
@@ -221,6 +395,9 @@
          glyph->width = glyph->char_width * 8;
          glyph->height = 16;
          glyph->baseline = (16 * 3) / 4;
+
+          /* Try to add glyph to cache.  */
+          cache_add_glyph (code, glyph);
          
          /* Restore old error message.  */
           grub_error_pop ();
@@ -258,5 +435,6 @@
 
 GRUB_MOD_FINI(font_manager)
 {
-  grub_unregister_command ("font");
+  grub_unregister_command ("font");  
+  cache_clear ();
 }
Index: term/gfxterm.c
===================================================================
RCS file: /sources/grub/grub2/term/gfxterm.c,v
retrieving revision 1.1
diff -u -r1.1 gfxterm.c
--- term/gfxterm.c      14 Mar 2006 19:08:34 -0000      1.1
+++ term/gfxterm.c      6 Apr 2006 19:15:59 -0000
@@ -641,8 +641,7 @@
 {
   struct grub_font_glyph glyph;
   
-  if (! grub_font_get_glyph (c, &glyph))
-    return 0;
+  grub_font_get_glyph (c, &glyph);
 
   return glyph.char_width;
 }