firmware/font_cache.c

   1 /***************************************************************************
   2  *             __________               __   ___.
   3  *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
   4  *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
   5  *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
   6  *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
   7  *                     \/            \/     \/    \/            \/
   8  *
   9  * Copyright (C) 2003 Tat Tang
  10  *
  11  * This program is free software; you can redistribute it and/or
  12  * modify it under the terms of the GNU General Public License
  13  * as published by the Free Software Foundation; either version 2
  14  * of the License, or (at your option) any later version.
  15  *
  16  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  17  * KIND, either express or implied.
  18  *
  19  ****************************************************************************/
  20
  21 #include <string.h>
  22 #include "font_cache.h"
  23 #include "debug.h"
  24
  25 /*******************************************************************************
  26  * font_cache_lru_init
  27  ******************************************************************************/
  28 static void font_cache_lru_init(void* data)
  29 {
  30     struct font_cache_entry* p = data;
  31     p->_char_code = 0xffff;   /* assume invalid char */
  32 }
  33
  34 /*******************************************************************************
  35  * font_cache_create
  36  ******************************************************************************/
  37 void font_cache_create(
  38     struct font_cache* fcache,
  39     void *buf,
  40     int buf_size,
  41     int bitmap_bytes_size)
  42 {
  43     int font_cache_entry_size =
  44         sizeof(struct font_cache_entry) + bitmap_bytes_size;
  45
  46     /* make sure font cache entries are a multiple of 16 bits */
  47     if (font_cache_entry_size % 2 != 0)
  48         font_cache_entry_size++;
  49
  50     int cache_size = buf_size /
  51         (font_cache_entry_size + LRU_SLOT_OVERHEAD + sizeof(short));
  52
  53     fcache->_size = 1;
  54     fcache->_capacity = cache_size;
  55     fcache->_prev_result = 0;
  56     fcache->_prev_char_code = 0;
  57
  58     /* set up index */
  59     fcache->_index = buf;
  60
  61     /* set up lru list */
  62     unsigned char* lru_buf = buf;
  63     lru_buf += sizeof(short) * cache_size;
  64     lru_create(&fcache->_lru, lru_buf, cache_size, font_cache_entry_size);
  65
  66     /* initialise cache */
  67     lru_traverse(&fcache->_lru, font_cache_lru_init);
  68     short i;
  69     for (i = 0; i < cache_size; i++)
  70         fcache->_index[i] = i; /* small cheat here */
  71 }
  72
  73 /*************************************************************************
  74  * Binary search that attempts a primary lucky guess that succeeds
  75  * when there are consecutive codes in the cache between previous
  76  * search and new search. Returns a negative of insertion point if
  77  * not found.
  78  ************************************************************************/
  79 static int search(struct font_cache* fcache,
  80                   unsigned short char_code,
  81                   int *p_insertion_point )
  82 {
  83     struct font_cache_entry *p;
  84     int left, right, mid=-1, c;
  85     left = 0;
  86     right = fcache->_size - 1;
  87
  88     /* go for a lucky guess */
  89     mid = char_code +
  90         fcache->_prev_result - fcache->_prev_char_code;
  91
  92     /* check bounds */
  93     if ( mid < 0 || mid > right )
  94             mid = ( left + right ) / 2;
  95
  96     do
  97     {
  98         p = lru_data(&fcache->_lru, fcache->_index[mid]);
  99         c = p->_char_code - char_code;
 100
 101         if (c == 0)
 102         {
 103             fcache->_prev_result = mid;
 104             fcache->_prev_char_code = char_code;
 105             *p_insertion_point = mid;
 106             return 1;
 107         }
 108         if (c < 0)
 109             left = mid + 1;
 110         else
 111             right = mid - 1;
 112
 113         mid = (left + right) / 2;
 114     }
 115     while (left <= right);
 116
 117     /* not found */
 118     *p_insertion_point = mid;
 119     return 0;
 120 }
 121 /*******************************************************************************
 122  * font_cache_get
 123  ******************************************************************************/
 124 struct font_cache_entry* font_cache_get(
 125     struct font_cache* fcache,
 126     unsigned short char_code,
 127     void (*callback) (struct font_cache_entry* p, void *callback_data),
 128     void *callback_data)
 129 {
 130     struct font_cache_entry* p;
 131     int insertion_point;
 132     int index_to_replace;
 133
 134     if( search(fcache, char_code, &insertion_point))
 135     {
 136         short lru_handle = fcache->_index[insertion_point];
 137         p = lru_data(&fcache->_lru, lru_handle);
 138         if (p->_char_code == char_code)
 139         {
 140             lru_touch(&fcache->_lru, lru_handle);
 141             return lru_data(&fcache->_lru, lru_handle);
 142         }
 143     }
 144     else  /* not found */
 145     {
 146         p = lru_data(&fcache->_lru,
 147                      fcache->_index[insertion_point+1]);
 148         if ( char_code > p->_char_code )
 149             insertion_point++;
 150     }
 151
 152     /* find index to replace */
 153     short lru_handle_to_replace = fcache->_lru._head;
 154     p = lru_data(&fcache->_lru, lru_handle_to_replace);
 155     search(fcache, p->_char_code, &index_to_replace);
 156
 157     if (insertion_point < index_to_replace)
 158     {
 159         /* shift memory up */
 160         memmove(fcache->_index + insertion_point + 2,
 161                 fcache->_index + insertion_point + 1,
 162                 (index_to_replace - insertion_point - 1) * sizeof(short));
 163
 164         /* add to index */
 165         fcache->_index[insertion_point + 1] = lru_handle_to_replace;
 166     }
 167     else if (insertion_point > index_to_replace)
 168     {
 169         /* shift memory down */
 170         memmove(fcache->_index + index_to_replace,
 171                 fcache->_index + index_to_replace + 1,
 172                 (insertion_point - index_to_replace) * sizeof(short));
 173
 174         /* add to index */
 175         fcache->_index[insertion_point] = lru_handle_to_replace;
 176     }
 177
 178     /* load new entry into cache */
 179     lru_touch(&fcache->_lru, lru_handle_to_replace);
 180
 181     if (fcache->_size < fcache->_capacity)
 182         fcache->_size++;
 183
 184     p->_char_code = char_code;
 185     /* fill bitmap */
 186     callback(p, callback_data);
 187     return p;
 188 }