libass/ass_cache.c

   1 // -*- c-basic-offset: 8; indent-tabs-mode: t -*-
   2 // vim:ts=8:sw=8:noet:ai:
   3 /*
   4   Copyright (C) 2006 Evgeniy Stepanov <eugeni.stepanov@gmail.com>
   5
   6   This program is free software; you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation; either version 2 of the License, or
   9   (at your option) any later version.
  10
  11   This program is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with this program; if not, write to the Free Software
  18   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  19 */
  20
  21 #include "config.h"
  22
  23 #include <inttypes.h>
  24 #include <ft2build.h>
  25 #include FT_FREETYPE_H
  26 #include FT_GLYPH_H
  27
  28 #include <assert.h>
  29
  30 #include "mputils.h"
  31 #include "ass.h"
  32 #include "ass_fontconfig.h"
  33 #include "ass_font.h"
  34 #include "ass_bitmap.h"
  35 #include "ass_cache.h"
  36
  37
  38 typedef struct hashmap_item_s {
  39         void* key;
  40         void* value;
  41         struct hashmap_item_s* next;
  42 } hashmap_item_t;
  43 typedef hashmap_item_t* hashmap_item_p;
  44
  45 struct hashmap_s {
  46         int nbuckets;
  47         size_t key_size, value_size;
  48         hashmap_item_p* root;
  49         hashmap_item_dtor_t item_dtor; // a destructor for hashmap key/value pairs
  50         hashmap_key_compare_t key_compare;
  51         hashmap_hash_t hash;
  52         // stats
  53         int hit_count;
  54         int miss_count;
  55         int count;
  56 };
  57
  58 #define FNV1_32A_INIT (unsigned)0x811c9dc5
  59
  60 static inline unsigned fnv_32a_buf(void* buf, size_t len, unsigned hval)
  61 {
  62         unsigned char *bp = buf;
  63         unsigned char *be = bp + len;
  64         while (bp < be) {
  65                 hval ^= (unsigned)*bp++;
  66                 hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);
  67         }
  68         return hval;
  69 }
  70 static inline unsigned fnv_32a_str(char* str, unsigned hval)
  71 {
  72         unsigned char* s = (unsigned char*)str;
  73         while (*s) {
  74                 hval ^= (unsigned)*s++;
  75                 hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);
  76         }
  77         return hval;
  78 }
  79
  80 static unsigned hashmap_hash(void* buf, size_t len)
  81 {
  82         return fnv_32a_buf(buf, len, FNV1_32A_INIT);
  83 }
  84
  85 static int hashmap_key_compare(void* a, void* b, size_t size)
  86 {
  87         return (memcmp(a, b, size) == 0);
  88 }
  89
  90 static void hashmap_item_dtor(void* key, size_t key_size, void* value, size_t value_size)
  91 {
  92         free(key);
  93         free(value);
  94 }
  95
  96 hashmap_t* hashmap_init(size_t key_size, size_t value_size, int nbuckets,
  97                         hashmap_item_dtor_t item_dtor, hashmap_key_compare_t key_compare,
  98                         hashmap_hash_t hash)
  99 {
 100         hashmap_t* map = calloc(1, sizeof(hashmap_t));
 101         map->nbuckets = nbuckets;
 102         map->key_size = key_size;
 103         map->value_size = value_size;
 104         map->root = calloc(nbuckets, sizeof(hashmap_item_p));
 105         map->item_dtor = item_dtor ? item_dtor : hashmap_item_dtor;
 106         map->key_compare = key_compare ? key_compare : hashmap_key_compare;
 107         map->hash = hash ? hash : hashmap_hash;
 108         return map;
 109 }
 110
 111 void hashmap_done(hashmap_t* map)
 112 {
 113         int i;
 114         // print stats
 115         if (map->count > 0 || map->hit_count + map->miss_count > 0)
 116                 mp_msg(MSGT_ASS, MSGL_V, "cache statistics: \n  total accesses: %d\n  hits: %d\n  misses: %d\n  object count: %d\n",
 117                        map->hit_count + map->miss_count, map->hit_count, map->miss_count, map->count);
 118
 119         for (i = 0; i < map->nbuckets; ++i) {
 120                 hashmap_item_t* item = map->root[i];
 121                 while (item) {
 122                         hashmap_item_t* next = item->next;
 123                         map->item_dtor(item->key, map->key_size, item->value, map->value_size);
 124                         free(item);
 125                         item = next;
 126                 }
 127         }
 128         free(map->root);
 129         free(map);
 130 }
 131
 132 // does nothing if key already exists
 133 void* hashmap_insert(hashmap_t* map, void* key, void* value)
 134 {
 135         unsigned hash = map->hash(key, map->key_size);
 136         hashmap_item_t** next = map->root + (hash % map->nbuckets);
 137         while (*next) {
 138                 if (map->key_compare(key, (*next)->key, map->key_size))
 139                         return (*next)->value;
 140                 next = &((*next)->next);
 141                 assert(next);
 142         }
 143         (*next) = malloc(sizeof(hashmap_item_t));
 144         (*next)->key = malloc(map->key_size);
 145         (*next)->value = malloc(map->value_size);
 146         memcpy((*next)->key, key, map->key_size);
 147         memcpy((*next)->value, value, map->value_size);
 148         (*next)->next = 0;
 149
 150         map->count ++;
 151         return (*next)->value;
 152 }
 153
 154 void* hashmap_find(hashmap_t* map, void* key)
 155 {
 156         unsigned hash = map->hash(key, map->key_size);
 157         hashmap_item_t* item = map->root[hash % map->nbuckets];
 158         while (item) {
 159                 if (map->key_compare(key, item->key, map->key_size)) {
 160                         map->hit_count++;
 161                         return item->value;
 162                 }
 163                 item = item->next;
 164         }
 165         map->miss_count++;
 166         return 0;
 167 }
 168
 169 //---------------------------------
 170 // font cache
 171
 172 hashmap_t* font_cache;
 173
 174 static unsigned font_desc_hash(void* buf, size_t len)
 175 {
 176         ass_font_desc_t* desc = buf;
 177         unsigned hval;
 178         hval = fnv_32a_str(desc->family, FNV1_32A_INIT);
 179         hval = fnv_32a_buf(&desc->bold, sizeof(desc->bold), hval);
 180         hval = fnv_32a_buf(&desc->italic, sizeof(desc->italic), hval);
 181         return hval;
 182 }
 183
 184 static int font_compare(void* key1, void* key2, size_t key_size) {
 185         ass_font_desc_t* a = key1;
 186         ass_font_desc_t* b = key2;
 187         if (strcmp(a->family, b->family) != 0)
 188                 return 0;
 189         if (a->bold != b->bold)
 190                 return 0;
 191         if (a->italic != b->italic)
 192                 return 0;
 193         return 1;
 194 }
 195
 196 static void font_hash_dtor(void* key, size_t key_size, void* value, size_t value_size)
 197 {
 198         ass_font_free(value);
 199         free(key);
 200 }
 201
 202 ass_font_t* ass_font_cache_find(ass_font_desc_t* desc)
 203 {
 204         return hashmap_find(font_cache, desc);
 205 }
 206
 207 /**
 208  * \brief Add a face struct to cache.
 209  * \param font font struct
 210 */
 211 void* ass_font_cache_add(ass_font_t* font)
 212 {
 213         return hashmap_insert(font_cache, &(font->desc), font);
 214 }
 215
 216 void ass_font_cache_init(void)
 217 {
 218         font_cache = hashmap_init(sizeof(ass_font_desc_t),
 219                                   sizeof(ass_font_t),
 220                                   1000,
 221                                   font_hash_dtor, font_compare, font_desc_hash);
 222 }
 223
 224 void ass_font_cache_done(void)
 225 {
 226         hashmap_done(font_cache);
 227 }
 228
 229 //---------------------------------
 230 // bitmap cache
 231
 232 hashmap_t* bitmap_cache;
 233
 234 static void bitmap_hash_dtor(void* key, size_t key_size, void* value, size_t value_size)
 235 {
 236         bitmap_hash_val_t* v = value;
 237         if (v->bm) ass_free_bitmap(v->bm);
 238         if (v->bm_o) ass_free_bitmap(v->bm_o);
 239         if (v->bm_s) ass_free_bitmap(v->bm_s);
 240         free(key);
 241         free(value);
 242 }
 243
 244 void* cache_add_bitmap(bitmap_hash_key_t* key, bitmap_hash_val_t* val)
 245 {
 246         return hashmap_insert(bitmap_cache, key, val);
 247 }
 248
 249 /**
 250  * \brief Get a bitmap from bitmap cache.
 251  * \param key hash key
 252  * \return requested hash val or 0 if not found
 253 */
 254 bitmap_hash_val_t* cache_find_bitmap(bitmap_hash_key_t* key)
 255 {
 256         return hashmap_find(bitmap_cache, key);
 257 }
 258
 259 void ass_bitmap_cache_init(void)
 260 {
 261         bitmap_cache = hashmap_init(sizeof(bitmap_hash_key_t),
 262                                    sizeof(bitmap_hash_val_t),
 263                                    0xFFFF + 13,
 264                                    bitmap_hash_dtor, NULL, NULL);
 265 }
 266
 267 void ass_bitmap_cache_done(void)
 268 {
 269         hashmap_done(bitmap_cache);
 270 }
 271
 272 void ass_bitmap_cache_reset(void)
 273 {
 274         ass_bitmap_cache_done();
 275         ass_bitmap_cache_init();
 276 }
 277
 278 //---------------------------------
 279 // glyph cache
 280
 281 hashmap_t* glyph_cache;
 282
 283 static void glyph_hash_dtor(void* key, size_t key_size, void* value, size_t value_size)
 284 {
 285         glyph_hash_val_t* v = value;
 286         if (v->glyph) FT_Done_Glyph(v->glyph);
 287         if (v->outline_glyph) FT_Done_Glyph(v->outline_glyph);
 288         free(key);
 289         free(value);
 290 }
 291
 292 void* cache_add_glyph(glyph_hash_key_t* key, glyph_hash_val_t* val)
 293 {
 294         return hashmap_insert(glyph_cache, key, val);
 295 }
 296
 297 /**
 298  * \brief Get a glyph from glyph cache.
 299  * \param key hash key
 300  * \return requested hash val or 0 if not found
 301 */
 302 glyph_hash_val_t* cache_find_glyph(glyph_hash_key_t* key)
 303 {
 304         return hashmap_find(glyph_cache, key);
 305 }
 306
 307 void ass_glyph_cache_init(void)
 308 {
 309         glyph_cache = hashmap_init(sizeof(glyph_hash_key_t),
 310                                    sizeof(glyph_hash_val_t),
 311                                    0xFFFF + 13,
 312                                    glyph_hash_dtor, NULL, NULL);
 313 }
 314
 315 void ass_glyph_cache_done(void)
 316 {
 317         hashmap_done(glyph_cache);
 318 }
 319
 320 void ass_glyph_cache_reset(void)
 321 {
 322         ass_glyph_cache_done();
 323         ass_glyph_cache_init();
 324 }