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
  56     /* set up index */
  57     fcache->_index = buf;
  58
  59     /* set up lru list */
  60     unsigned char* lru_buf = buf;
  61     lru_buf += sizeof(short) * cache_size;
  62     lru_create(&fcache->_lru, lru_buf, cache_size, font_cache_entry_size);
  63
  64     /* initialise cache */
  65     lru_traverse(&fcache->_lru, font_cache_lru_init);
  66     short i;
  67     for (i = 0; i < cache_size; i++)
  68         fcache->_index[i] = i; /* small cheat here */
  69 }
  70
  71 /*******************************************************************************
  72  * font_cache_index_of
  73  ******************************************************************************/
  74 static int font_cache_index_of(
  75            struct font_cache* fcache,
  76            unsigned short char_code)
  77 {
  78     struct font_cache_entry* p;
  79     int left, right, mid, c;
  80     left = 0;
  81     right = fcache->_size - 1;
  82
  83     do
  84     {
  85         mid = (left + right) / 2;
  86
  87         p = lru_data(&fcache->_lru, fcache->_index[mid]);
  88         c = p->_char_code - char_code;
  89
  90         if (c == 0)
  91             return mid;
  92
  93         if (c < 0)
  94             left = mid + 1;
  95         else
  96             right = mid - 1;
  97     }
  98     while (left <= right);
  99
 100     return -1;
 101 }
 102
 103 /*******************************************************************************
 104  * font_cache_insertion_point
 105  ******************************************************************************/
 106 static int font_cache_insertion_point(
 107        struct font_cache* fcache,
 108        unsigned short char_code)
 109 {
 110     struct font_cache_entry* p;
 111     short *index = fcache->_index;
 112
 113     p = lru_data(&fcache->_lru, index[0]);
 114     if (char_code < p->_char_code)
 115         return -1;
 116
 117     p = lru_data(&fcache->_lru, index[fcache->_capacity - 1]);
 118     if (char_code > p->_char_code)
 119         return fcache->_capacity - 1;
 120
 121     int left, right, mid, c;
 122
 123     left = 0;
 124     right = fcache->_capacity - 1;
 125
 126     do
 127     {
 128         mid = (left + right) / 2;
 129
 130         p = lru_data(&fcache->_lru, index[mid]);
 131         c = char_code - p->_char_code;
 132
 133         if (c >= 0)
 134         {
 135             p = lru_data(&fcache->_lru, index[mid+1]);
 136             int z = char_code - p->_char_code;
 137
 138             if (z < 0)
 139                 return mid;
 140
 141             if (z == 0)
 142                 return mid + 1;
 143         }
 144
 145
 146         if (c > 0)
 147             left = mid + 1;
 148         else
 149             right = mid - 1;
 150     }
 151     while (left <= right);
 152
 153     /* not found */
 154     return -2;
 155 }
 156
 157 /*******************************************************************************
 158  * font_cache_get
 159  ******************************************************************************/
 160 struct font_cache_entry* font_cache_get(
 161     struct font_cache* fcache,
 162     unsigned short char_code,
 163     void (*callback) (struct font_cache_entry* p, void *callback_data),
 164     void *callback_data)
 165 {
 166     int insertion_point = font_cache_insertion_point(fcache, char_code);
 167     if (insertion_point >= 0)
 168     {
 169         short lru_handle = fcache->_index[insertion_point];
 170         struct font_cache_entry* p = lru_data(&fcache->_lru, lru_handle);
 171         if (p->_char_code == char_code)
 172         {
 173             lru_touch(&fcache->_lru, lru_handle);
 174             return lru_data(&fcache->_lru, lru_handle);
 175         }
 176     }
 177
 178     /* not found */
 179     short lru_handle_to_replace = fcache->_lru._head;
 180     struct font_cache_entry* p =
 181         lru_data(&fcache->_lru, lru_handle_to_replace);
 182     int index_to_replace = font_cache_index_of(fcache, p->_char_code);
 183
 184     if (insertion_point < index_to_replace)
 185     {
 186         /* shift memory up */
 187         memmove(fcache->_index + insertion_point + 2,
 188                 fcache->_index + insertion_point + 1,
 189                 (index_to_replace - insertion_point - 1) * sizeof(short));
 190
 191         /* add to index */
 192         fcache->_index[insertion_point + 1] = lru_handle_to_replace;
 193     }
 194     else if (insertion_point > index_to_replace)
 195     {
 196         /* shift memory down */
 197         memmove(fcache->_index + index_to_replace,
 198                 fcache->_index + index_to_replace + 1,
 199                 (insertion_point - index_to_replace) * sizeof(short));
 200
 201         /* add to index */
 202         fcache->_index[insertion_point] = lru_handle_to_replace;
 203     }
 204
 205     /* load new entry into cache */
 206     lru_touch(&fcache->_lru, lru_handle_to_replace);
 207
 208     if (fcache->_size < fcache->_capacity)
 209         fcache->_size++;
 210
 211     p->_char_code = char_code;
 212     callback(p, callback_data);
 213
 214     return p;
 215 }