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