libass/ass_cache.c

   1 /*
   2  * Copyright (C) 2006 Evgeniy Stepanov <eugeni.stepanov@gmail.com>
   3  * Copyright (C) 2011 Grigori Goronzy <greg@chown.ath.cx>
   4  *
   5  * This file is part of libass.
   6  *
   7  * Permission to use, copy, modify, and distribute this software for any
   8  * purpose with or without fee is hereby granted, provided that the above
   9  * copyright notice and this permission notice appear in all copies.
  10  *
  11  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  12  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  13  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  14  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  15  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  16  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  17  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  18  */
  19
  20 #include "config.h"
  21
  22 #include <inttypes.h>
  23 #include <ft2build.h>
  24 #include FT_OUTLINE_H
  25 #include <assert.h>
  26
  27 #include "ass_utils.h"
  28 #include "ass_font.h"
  29 #include "ass_cache.h"
  30
  31 // type-specific functions
  32 // create hash/compare functions for bitmap, outline and composite cache
  33 #define CREATE_HASH_FUNCTIONS
  34 #include "ass_cache_template.h"
  35 #define CREATE_COMPARISON_FUNCTIONS
  36 #include "ass_cache_template.h"
  37
  38 // font cache
  39 static unsigned font_hash(void *buf, size_t len)
  40 {
  41     ASS_FontDesc *desc = buf;
  42     unsigned hval;
  43     hval = fnv_32a_str(desc->family, FNV1_32A_INIT);
  44     hval = fnv_32a_buf(&desc->bold, sizeof(desc->bold), hval);
  45     hval = fnv_32a_buf(&desc->italic, sizeof(desc->italic), hval);
  46     hval = fnv_32a_buf(&desc->treat_family_as_pattern,
  47             sizeof(desc->treat_family_as_pattern), hval);
  48     hval = fnv_32a_buf(&desc->vertical, sizeof(desc->vertical), hval);
  49     return hval;
  50 }
  51
  52 static unsigned font_compare(void *key1, void *key2, size_t key_size)
  53 {
  54     ASS_FontDesc *a = key1;
  55     ASS_FontDesc *b = key2;
  56     if (strcmp(a->family, b->family) != 0)
  57         return 0;
  58     if (a->bold != b->bold)
  59         return 0;
  60     if (a->italic != b->italic)
  61         return 0;
  62     if (a->treat_family_as_pattern != b->treat_family_as_pattern)
  63         return 0;
  64     if (a->vertical != b->vertical)
  65         return 0;
  66     return 1;
  67 }
  68
  69 static void font_destruct(void *key, void *value)
  70 {
  71     ass_font_free(value);
  72     free(key);
  73 }
  74
  75 // bitmap cache
  76 static void bitmap_destruct(void *key, void *value)
  77 {
  78     BitmapHashValue *v = value;
  79     BitmapHashKey *k = key;
  80     if (v->bm)
  81         ass_free_bitmap(v->bm);
  82     if (v->bm_o)
  83         ass_free_bitmap(v->bm_o);
  84     if (v->bm_s)
  85         ass_free_bitmap(v->bm_s);
  86     if (k->type == BITMAP_CLIP)
  87         free(k->u.clip.text);
  88     free(key);
  89     free(value);
  90 }
  91
  92 static size_t bitmap_size(void *value, size_t value_size)
  93 {
  94     BitmapHashValue *val = value;
  95     if (val->bm_o)
  96         return val->bm_o->w * val->bm_o->h * 3;
  97     else if (val->bm)
  98         return val->bm->w * val->bm->h * 3;
  99     return 0;
 100 }
 101
 102 static unsigned bitmap_hash(void *key, size_t key_size)
 103 {
 104     BitmapHashKey *k = key;
 105     switch (k->type) {
 106         case BITMAP_OUTLINE: return outline_bitmap_hash(&k->u, key_size);
 107         case BITMAP_CLIP: return clip_bitmap_hash(&k->u, key_size);
 108         default: return 0;
 109     }
 110 }
 111
 112 static unsigned bitmap_compare (void *a, void *b, size_t key_size)
 113 {
 114     BitmapHashKey *ak = a;
 115     BitmapHashKey *bk = b;
 116     if (ak->type != bk->type) return 0;
 117     switch (ak->type) {
 118         case BITMAP_OUTLINE: return outline_bitmap_compare(&ak->u, &bk->u, key_size);
 119         case BITMAP_CLIP: return clip_bitmap_compare(&ak->u, &bk->u, key_size);
 120         default: return 0;
 121     }
 122 }
 123
 124 // composite cache
 125 static void composite_destruct(void *key, void *value)
 126 {
 127     CompositeHashValue *v = value;
 128     free(v->a);
 129     free(v->b);
 130     free(key);
 131     free(value);
 132 }
 133
 134 // outline cache
 135
 136 static unsigned outline_hash(void *key, size_t key_size)
 137 {
 138     OutlineHashKey *k = key;
 139     switch (k->type) {
 140         case OUTLINE_GLYPH: return glyph_hash(&k->u, key_size);
 141         case OUTLINE_DRAWING: return drawing_hash(&k->u, key_size);
 142         default: return 0;
 143     }
 144 }
 145
 146 static unsigned outline_compare(void *a, void *b, size_t key_size)
 147 {
 148     OutlineHashKey *ak = a;
 149     OutlineHashKey *bk = b;
 150     if (ak->type != bk->type) return 0;
 151     switch (ak->type) {
 152         case OUTLINE_GLYPH: return glyph_compare(&ak->u, &bk->u, key_size);
 153         case OUTLINE_DRAWING: return drawing_compare(&ak->u, &bk->u, key_size);
 154         default: return 0;
 155     }
 156 }
 157
 158 static void outline_destruct(void *key, void *value)
 159 {
 160     OutlineHashValue *v = value;
 161     OutlineHashKey *k = key;
 162     if (v->outline)
 163         outline_free(v->lib, v->outline);
 164     if (v->border)
 165         outline_free(v->lib, v->border);
 166     if (k->type == OUTLINE_DRAWING)
 167         free(k->u.drawing.text);
 168     free(key);
 169     free(value);
 170 }
 171
 172
 173
 174 // Cache data
 175 typedef struct cache_item {
 176     void *key;
 177     void *value;
 178     struct cache_item *next;
 179 } CacheItem;
 180
 181 struct cache {
 182     unsigned buckets;
 183     CacheItem **map;
 184
 185     HashFunction hash_func;
 186     ItemSize size_func;
 187     HashCompare compare_func;
 188     CacheItemDestructor destruct_func;
 189     size_t key_size;
 190     size_t value_size;
 191
 192     size_t cache_size;
 193     unsigned hits;
 194     unsigned misses;
 195     unsigned items;
 196 };
 197
 198 // Hash for a simple (single value or array) type
 199 static unsigned hash_simple(void *key, size_t key_size)
 200 {
 201     return fnv_32a_buf(key, key_size, FNV1_32A_INIT);
 202 }
 203
 204 // Comparison of a simple type
 205 static unsigned compare_simple(void *a, void *b, size_t key_size)
 206 {
 207     return memcmp(a, b, key_size) == 0;
 208 }
 209
 210 // Default destructor
 211 static void destruct_simple(void *key, void *value)
 212 {
 213     free(key);
 214     free(value);
 215 }
 216
 217
 218 // Create a cache with type-specific hash/compare/destruct/size functions
 219 Cache *ass_cache_create(HashFunction hash_func, HashCompare compare_func,
 220                         CacheItemDestructor destruct_func, ItemSize size_func,
 221                         size_t key_size, size_t value_size)
 222 {
 223     Cache *cache = calloc(1, sizeof(*cache));
 224     cache->buckets = 0xFFFF;
 225     cache->hash_func = hash_simple;
 226     cache->compare_func = compare_simple;
 227     cache->destruct_func = destruct_simple;
 228     cache->size_func = size_func;
 229     if (hash_func)
 230         cache->hash_func = hash_func;
 231     if (compare_func)
 232         cache->compare_func = compare_func;
 233     if (destruct_func)
 234         cache->destruct_func = destruct_func;
 235     cache->key_size = key_size;
 236     cache->value_size = value_size;
 237     cache->map = calloc(cache->buckets, sizeof(CacheItem *));
 238
 239     return cache;
 240 }
 241
 242 void *ass_cache_put(Cache *cache, void *key, void *value)
 243 {
 244     unsigned bucket = cache->hash_func(key, cache->key_size) % cache->buckets;
 245     CacheItem **item = &cache->map[bucket];
 246     while (*item)
 247         item = &(*item)->next;
 248     (*item) = calloc(1, sizeof(CacheItem));
 249     (*item)->key = malloc(cache->key_size);
 250     (*item)->value = malloc(cache->value_size);
 251     memcpy((*item)->key, key, cache->key_size);
 252     memcpy((*item)->value, value, cache->value_size);
 253
 254     cache->items++;
 255     if (cache->size_func)
 256         cache->cache_size += cache->size_func(value, cache->value_size);
 257     else
 258         cache->cache_size++;
 259
 260     return (*item)->value;
 261 }
 262
 263 void *ass_cache_get(Cache *cache, void *key)
 264 {
 265     unsigned bucket = cache->hash_func(key, cache->key_size) % cache->buckets;
 266     CacheItem *item = cache->map[bucket];
 267     while (item) {
 268         if (cache->compare_func(key, item->key, cache->key_size)) {
 269             cache->hits++;
 270             return item->value;
 271         }
 272         item = item->next;
 273     }
 274     cache->misses++;
 275     return NULL;
 276 }
 277
 278 int ass_cache_empty(Cache *cache, size_t max_size)
 279 {
 280     int i;
 281
 282     if (cache->cache_size < max_size)
 283         return 0;
 284
 285     for (i = 0; i < cache->buckets; i++) {
 286         CacheItem *item = cache->map[i];
 287         while (item) {
 288             CacheItem *next = item->next;
 289             cache->destruct_func(item->key, item->value);
 290             free(item);
 291             item = next;
 292         }
 293         cache->map[i] = NULL;
 294     }
 295
 296     cache->items = cache->hits = cache->misses = cache->cache_size = 0;
 297
 298     return 1;
 299 }
 300
 301 void ass_cache_stats(Cache *cache, size_t *size, unsigned *hits,
 302                      unsigned *misses, unsigned *count)
 303 {
 304     if (size)
 305         *size = cache->cache_size;
 306     if (hits)
 307         *hits = cache->hits;
 308     if (misses)
 309         *misses = cache->misses;
 310     if (count)
 311         *count = cache->items;
 312 }
 313
 314 void ass_cache_done(Cache *cache)
 315 {
 316     ass_cache_empty(cache, 0);
 317     free(cache->map);
 318     free(cache);
 319 }
 320
 321 // Type-specific creation function
 322 Cache *ass_font_cache_create(void)
 323 {
 324     return ass_cache_create(font_hash, font_compare, font_destruct,
 325             (ItemSize)NULL, sizeof(ASS_FontDesc), sizeof(ASS_Font));
 326 }
 327
 328 Cache *ass_outline_cache_create(void)
 329 {
 330     return ass_cache_create(outline_hash, outline_compare, outline_destruct,
 331             NULL, sizeof(OutlineHashKey), sizeof(OutlineHashValue));
 332 }
 333
 334 Cache *ass_glyph_metrics_cache_create(void)
 335 {
 336     return ass_cache_create(glyph_metrics_hash, glyph_metrics_compare, NULL,
 337             (ItemSize) NULL, sizeof(GlyphMetricsHashKey),
 338             sizeof(GlyphMetricsHashValue));
 339 }
 340
 341 Cache *ass_bitmap_cache_create(void)
 342 {
 343     return ass_cache_create(bitmap_hash, bitmap_compare, bitmap_destruct,
 344             bitmap_size, sizeof(BitmapHashKey), sizeof(BitmapHashValue));
 345 }
 346
 347 Cache *ass_composite_cache_create(void)
 348 {
 349     return ass_cache_create(composite_hash, composite_compare,
 350             composite_destruct, (ItemSize)NULL, sizeof(CompositeHashKey),
 351             sizeof(CompositeHashValue));
 352 }