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 size,
  82                   int *p_insertion_point )
  83 {
  84     struct font_cache_entry *p;
  85     int left, right, mid=-1, c;
  86     left = 0;
  87     right = size;
  88
  89     /* go for a lucky guess */
  90     mid = char_code +
  91         fcache->_prev_result - fcache->_prev_char_code;
  92
  93     /* check bounds */
  94     if ( mid < 0 || mid > right )
  95             mid = ( left + right ) / 2;
  96
  97     do
  98     {
  99         p = lru_data(&fcache->_lru, fcache->_index[mid]);
 100         c = p->_char_code - char_code;
 101
 102         if (c == 0)
 103         {
 104             fcache->_prev_result = mid;
 105             fcache->_prev_char_code = char_code;
 106             *p_insertion_point = mid;
 107             return 1;
 108         }
 109         if (c < 0)
 110             left = mid + 1;
 111         else
 112             right = mid - 1;
 113
 114         mid = (left + right) / 2;
 115     }
 116     while (left <= right);
 117
 118     /* not found */
 119     *p_insertion_point = mid;
 120     return 0;
 121 }
 122 /*******************************************************************************
 123  * font_cache_get
 124  ******************************************************************************/
 125 struct font_cache_entry* font_cache_get(
 126     struct font_cache* fcache,
 127     unsigned short char_code,
 128     void (*callback) (struct font_cache_entry* p, void *callback_data),
 129     void *callback_data)
 130 {
 131     struct font_cache_entry* p;
 132     int insertion_point;
 133     int index_to_replace;
 134
 135     /* check bounds */
 136     p = lru_data(&fcache->_lru, fcache->_index[0]);
 137     if( char_code < p->_char_code )
 138         insertion_point = -1;
 139     else
 140     {
 141         p = lru_data(&fcache->_lru, fcache->_index[fcache->_capacity - 1]);
 142         if( char_code > p->_char_code )
 143         {
 144             insertion_point = fcache->_capacity - 1;
 145         }
 146         else
 147         {
 148             if( search(fcache, char_code, fcache->_size - 1, &insertion_point))
 149             {
 150                 short lru_handle = fcache->_index[insertion_point];
 151                 p = lru_data(&fcache->_lru, lru_handle);
 152                 if (p->_char_code == char_code)
 153                 {
 154                     lru_touch(&fcache->_lru, lru_handle);
 155                     return lru_data(&fcache->_lru, lru_handle);
 156                 }
 157             }
 158             else
 159             {
 160                 p = lru_data(&fcache->_lru,
 161                 fcache->_index[insertion_point+1]);
 162                 if ( char_code > p->_char_code )
 163                      insertion_point++;
 164             }
 165         }
 166     }
 167
 168     /* not found */
 169
 170     /* find index to replace */
 171     short lru_handle_to_replace = fcache->_lru._head;
 172     p = lru_data(&fcache->_lru, lru_handle_to_replace);
 173     search(fcache, p->_char_code, fcache->_size - 1, &index_to_replace);
 174     if (insertion_point < index_to_replace)
 175     {
 176         /* shift memory up */
 177         memmove(fcache->_index + insertion_point + 2,
 178                 fcache->_index + insertion_point + 1,
 179                 (index_to_replace - insertion_point - 1) * sizeof(short));
 180
 181         /* add to index */
 182         fcache->_index[insertion_point + 1] = lru_handle_to_replace;
 183     }
 184     else if (insertion_point > index_to_replace)
 185     {
 186         /* shift memory down */
 187         memmove(fcache->_index + index_to_replace,
 188                 fcache->_index + index_to_replace + 1,
 189                 (insertion_point - index_to_replace) * sizeof(short));
 190
 191         /* add to index */
 192         fcache->_index[insertion_point] = lru_handle_to_replace;
 193     }
 194
 195     /* load new entry into cache */
 196     lru_touch(&fcache->_lru, lru_handle_to_replace);
 197
 198     if (fcache->_size < fcache->_capacity)
 199         fcache->_size++;
 200
 201     p->_char_code = char_code;
 202     /* fill bitmap */
 203     callback(p, callback_data);
 204     return p;
 205 }