firmware/font_cache.c

   1 /***************************************************************************
   2  *             __________               __   ___.
   3  *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
   4  *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
   5  *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
   6  *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
   7  *                     \/            \/     \/    \/            \/
   8  *
   9  * Copyright (C) 2003 Tat Tang
  10  *
  11  * All files in this archive are subject to the GNU General Public License.
  12  * See the file COPYING in the source tree root for full license agreement.
  13  *
  14  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  15  * KIND, either express or implied.
  16  *
  17  ****************************************************************************/
  18
  19 #include <string.h>
  20 #include "font_cache.h"
  21 #include "debug.h"
  22
  23 /*******************************************************************************
  24  * font_cache_lru_init
  25  ******************************************************************************/
  26 static void font_cache_lru_init(void* data)
  27 {
  28     struct font_cache_entry* p = data;
  29     p->_char_code = 0xffff;   /* assume invalid char */
  30 }
  31
  32 /*******************************************************************************
  33  * font_cache_create
  34  ******************************************************************************/
  35 void font_cache_create(
  36     struct font_cache* fcache,
  37     void *buf,
  38     int buf_size,
  39     int bitmap_bytes_size)
  40 {
  41     int font_cache_entry_size =
  42         sizeof(struct font_cache_entry) + bitmap_bytes_size;
  43
  44     /* make sure font cache entries are a multiple of 16 bits */
  45     if (font_cache_entry_size % 2 != 0)
  46         font_cache_entry_size++;
  47
  48     int cache_size = buf_size /
  49         (font_cache_entry_size + LRU_SLOT_OVERHEAD + sizeof(short));
  50
  51     fcache->_size = 1;
  52     fcache->_capacity = cache_size;
  53
  54     /* set up index */
  55     fcache->_index = buf;
  56
  57     /* set up lru list */
  58     unsigned char* lru_buf = buf;
  59     lru_buf += sizeof(short) * cache_size;
  60     lru_create(&fcache->_lru, lru_buf, cache_size, font_cache_entry_size);
  61
  62     /* initialise cache */
  63     lru_traverse(&fcache->_lru, font_cache_lru_init);
  64     short i;
  65     for (i = 0; i < cache_size; i++)
  66         fcache->_index[i] = i; /* small cheat here */
  67 }
  68
  69 /*******************************************************************************
  70  * font_cache_index_of
  71  ******************************************************************************/
  72 static int font_cache_index_of(
  73            struct font_cache* fcache,
  74            unsigned short char_code)
  75 {
  76     struct font_cache_entry* p;
  77     int left, right, mid, c;
  78     left = 0;
  79     right = fcache->_size - 1;
  80
  81     do
  82     {
  83         mid = (left + right) / 2;
  84
  85         p = lru_data(&fcache->_lru, fcache->_index[mid]);
  86         c = p->_char_code - char_code;
  87
  88         if (c == 0)
  89             return mid;
  90
  91         if (c < 0)
  92             left = mid + 1;
  93         else
  94             right = mid - 1;
  95     }
  96     while (left <= right);
  97
  98     return -1;
  99 }
 100
 101 /*******************************************************************************
 102  * font_cache_insertion_point
 103  ******************************************************************************/
 104 static int font_cache_insertion_point(
 105        struct font_cache* fcache,
 106        unsigned short char_code)
 107 {
 108     struct font_cache_entry* p;
 109     short *index = fcache->_index;
 110
 111     p = lru_data(&fcache->_lru, index[0]);
 112     if (char_code < p->_char_code)
 113         return -1;
 114
 115     p = lru_data(&fcache->_lru, index[fcache->_capacity - 1]);
 116     if (char_code > p->_char_code)
 117         return fcache->_capacity - 1;
 118
 119     int left, right, mid, c;
 120
 121     left = 0;
 122     right = fcache->_capacity - 1;
 123
 124     do
 125     {
 126         mid = (left + right) / 2;
 127
 128         p = lru_data(&fcache->_lru, index[mid]);
 129         c = char_code - p->_char_code;
 130
 131         if (c >= 0)
 132         {
 133             p = lru_data(&fcache->_lru, index[mid+1]);
 134             int z = char_code - p->_char_code;
 135
 136             if (z < 0)
 137                 return mid;
 138
 139             if (z == 0)
 140                 return mid + 1;
 141         }
 142
 143
 144         if (c > 0)
 145             left = mid + 1;
 146         else
 147             right = mid - 1;
 148     }
 149     while (left <= right);
 150
 151     /* not found */
 152     return -2;
 153 }
 154
 155 /*******************************************************************************
 156  * font_cache_get
 157  ******************************************************************************/
 158 struct font_cache_entry* font_cache_get(
 159     struct font_cache* fcache,
 160     unsigned short char_code,
 161     void (*callback) (struct font_cache_entry* p, void *callback_data),
 162     void *callback_data)
 163 {
 164     int insertion_point = font_cache_insertion_point(fcache, char_code);
 165     if (insertion_point >= 0)
 166     {
 167         short lru_handle = fcache->_index[insertion_point];
 168         struct font_cache_entry* p = lru_data(&fcache->_lru, lru_handle);
 169         if (p->_char_code == char_code)
 170         {
 171             lru_touch(&fcache->_lru, lru_handle);
 172             return lru_data(&fcache->_lru, lru_handle);
 173         }
 174     }
 175
 176     /* not found */
 177     short lru_handle_to_replace = fcache->_lru._head;
 178     struct font_cache_entry* p =
 179         lru_data(&fcache->_lru, lru_handle_to_replace);
 180     int index_to_replace = font_cache_index_of(fcache, p->_char_code);
 181
 182     if (insertion_point < index_to_replace)
 183     {
 184         /* shift memory up */
 185         memmove(fcache->_index + insertion_point + 2,
 186                 fcache->_index + insertion_point + 1,
 187                 (index_to_replace - insertion_point - 1) * sizeof(short));
 188
 189         /* add to index */
 190         fcache->_index[insertion_point + 1] = lru_handle_to_replace;
 191     }
 192     else if (insertion_point > index_to_replace)
 193     {
 194         /* shift memory down */
 195         memmove(fcache->_index + index_to_replace,
 196                 fcache->_index + index_to_replace + 1,
 197                 (insertion_point - index_to_replace) * sizeof(short));
 198
 199         /* add to index */
 200         fcache->_index[insertion_point] = lru_handle_to_replace;
 201     }
 202
 203     /* load new entry into cache */
 204     lru_touch(&fcache->_lru, lru_handle_to_replace);
 205
 206     if (fcache->_size < fcache->_capacity)
 207         fcache->_size++;
 208
 209     p->_char_code = char_code;
 210     callback(p, callback_data);
 211
 212     return p;
 213 }