1#include "mupdf/fitz.h"
2#include "draw-imp.h"
3#include "fitz-imp.h"
4
5#include <string.h>
6#include <math.h>
7
8#define MAX_GLYPH_SIZE 256
9#define MAX_CACHE_SIZE (1024*1024)
10
11#define GLYPH_HASH_LEN 509
12
13typedef struct fz_glyph_cache_entry_s fz_glyph_cache_entry;
14typedef struct fz_glyph_key_s fz_glyph_key;
15
16struct fz_glyph_key_s
17{
18 fz_font *font;
19 int a, b;
20 int c, d;
21 unsigned short gid;
22 unsigned char e, f;
23 int aa;
24};
25
26struct fz_glyph_cache_entry_s
27{
28 fz_glyph_key key;
29 unsigned hash;
30 fz_glyph_cache_entry *lru_prev;
31 fz_glyph_cache_entry *lru_next;
32 fz_glyph_cache_entry *bucket_next;
33 fz_glyph_cache_entry *bucket_prev;
34 fz_glyph *val;
35};
36
37struct fz_glyph_cache_s
38{
39 int refs;
40 size_t total;
41#ifndef NDEBUG
42 int num_evictions;
43 ptrdiff_t evicted;
44#endif
45 fz_glyph_cache_entry *entry[GLYPH_HASH_LEN];
46 fz_glyph_cache_entry *lru_head;
47 fz_glyph_cache_entry *lru_tail;
48};
49
50void
51fz_new_glyph_cache_context(fz_context *ctx)
52{
53 fz_glyph_cache *cache;
54
55 cache = fz_malloc_struct(ctx, fz_glyph_cache);
56 cache->total = 0;
57 cache->refs = 1;
58
59 ctx->glyph_cache = cache;
60}
61
62static void
63drop_glyph_cache_entry(fz_context *ctx, fz_glyph_cache_entry *entry)
64{
65 fz_glyph_cache *cache = ctx->glyph_cache;
66
67 if (entry->lru_next)
68 entry->lru_next->lru_prev = entry->lru_prev;
69 else
70 cache->lru_tail = entry->lru_prev;
71 if (entry->lru_prev)
72 entry->lru_prev->lru_next = entry->lru_next;
73 else
74 cache->lru_head = entry->lru_next;
75 cache->total -= fz_glyph_size(ctx, entry->val);
76 if (entry->bucket_next)
77 entry->bucket_next->bucket_prev = entry->bucket_prev;
78 if (entry->bucket_prev)
79 entry->bucket_prev->bucket_next = entry->bucket_next;
80 else
81 cache->entry[entry->hash] = entry->bucket_next;
82 fz_drop_font(ctx, entry->key.font);
83 fz_drop_glyph(ctx, entry->val);
84 fz_free(ctx, entry);
85}
86
87/* The glyph cache lock is always held when this function is called. */
88static void
89do_purge(fz_context *ctx)
90{
91 fz_glyph_cache *cache = ctx->glyph_cache;
92 int i;
93
94 for (i = 0; i < GLYPH_HASH_LEN; i++)
95 {
96 while (cache->entry[i])
97 drop_glyph_cache_entry(ctx, cache->entry[i]);
98 }
99
100 cache->total = 0;
101}
102
103void
104fz_purge_glyph_cache(fz_context *ctx)
105{
106 fz_lock(ctx, FZ_LOCK_GLYPHCACHE);
107 do_purge(ctx);
108 fz_unlock(ctx, FZ_LOCK_GLYPHCACHE);
109}
110
111void
112fz_drop_glyph_cache_context(fz_context *ctx)
113{
114 if (!ctx || !ctx->glyph_cache)
115 return;
116
117 fz_lock(ctx, FZ_LOCK_GLYPHCACHE);
118 ctx->glyph_cache->refs--;
119 if (ctx->glyph_cache->refs == 0)
120 {
121 do_purge(ctx);
122 fz_free(ctx, ctx->glyph_cache);
123 ctx->glyph_cache = NULL;
124 }
125 fz_unlock(ctx, FZ_LOCK_GLYPHCACHE);
126}
127
128fz_glyph_cache *
129fz_keep_glyph_cache(fz_context *ctx)
130{
131 fz_lock(ctx, FZ_LOCK_GLYPHCACHE);
132 ctx->glyph_cache->refs++;
133 fz_unlock(ctx, FZ_LOCK_GLYPHCACHE);
134 return ctx->glyph_cache;
135}
136
137float
138fz_subpixel_adjust(fz_context *ctx, fz_matrix *ctm, fz_matrix *subpix_ctm, unsigned char *qe, unsigned char *qf)
139{
140 float size = fz_matrix_expansion(*ctm);
141 int q;
142 float pix_e, pix_f, r;
143
144 /* Quantise the subpixel positions. */
145 /* We never need more than 4 subpixel positions for glyphs - arguably
146 * even that is too much. */
147 if (size >= 48)
148 q = 0, r = 0.5f;
149 else if (size >= 24)
150 q = 128, r = 0.25f;
151 else
152 q = 192, r = 0.125f;
153
154 /* Split translation into pixel and subpixel parts */
155 subpix_ctm->a = ctm->a;
156 subpix_ctm->b = ctm->b;
157 subpix_ctm->c = ctm->c;
158 subpix_ctm->d = ctm->d;
159 subpix_ctm->e = ctm->e + r;
160 pix_e = floorf(subpix_ctm->e);
161 subpix_ctm->e -= pix_e;
162 subpix_ctm->f = ctm->f + r;
163 pix_f = floorf(subpix_ctm->f);
164 subpix_ctm->f -= pix_f;
165
166 /* Quantise the subpixel part */
167 *qe = (int)(subpix_ctm->e * 256) & q;
168 subpix_ctm->e = *qe / 256.0f;
169 *qf = (int)(subpix_ctm->f * 256) & q;
170 subpix_ctm->f = *qf / 256.0f;
171
172 /* Reassemble the complete translation */
173 ctm->e = subpix_ctm->e + pix_e;
174 ctm->f = subpix_ctm->f + pix_f;
175
176 return size;
177}
178
179fz_glyph *
180fz_render_stroked_glyph(fz_context *ctx, fz_font *font, int gid, fz_matrix *trm, fz_matrix ctm, const fz_stroke_state *stroke, const fz_irect *scissor, int aa)
181{
182 if (fz_font_ft_face(ctx, font))
183 {
184 fz_matrix subpix_trm;
185 unsigned char qe, qf;
186
187 if (stroke->dash_len > 0)
188 return NULL;
189 (void)fz_subpixel_adjust(ctx, trm, &subpix_trm, &qe, &qf);
190 return fz_render_ft_stroked_glyph(ctx, font, gid, subpix_trm, ctm, stroke, aa);
191 }
192 return fz_render_glyph(ctx, font, gid, trm, NULL, scissor, 1, aa);
193}
194
195fz_pixmap *
196fz_render_stroked_glyph_pixmap(fz_context *ctx, fz_font *font, int gid, fz_matrix *trm, fz_matrix ctm, const fz_stroke_state *stroke, const fz_irect *scissor, int aa)
197{
198 if (fz_font_ft_face(ctx, font))
199 {
200 fz_matrix subpix_trm;
201 unsigned char qe, qf;
202
203 if (stroke->dash_len > 0)
204 return NULL;
205 (void)fz_subpixel_adjust(ctx, trm, &subpix_trm, &qe, &qf);
206 return fz_render_ft_stroked_glyph_pixmap(ctx, font, gid, subpix_trm, ctm, stroke, aa);
207 }
208 return fz_render_glyph_pixmap(ctx, font, gid, trm, scissor, aa);
209}
210
211static unsigned do_hash(unsigned char *s, int len)
212{
213 unsigned val = 0;
214 int i;
215 for (i = 0; i < len; i++)
216 {
217 val += s[i];
218 val += (val << 10);
219 val ^= (val >> 6);
220 }
221 val += (val << 3);
222 val ^= (val >> 11);
223 val += (val << 15);
224 return val;
225}
226
227static inline void
228move_to_front(fz_glyph_cache *cache, fz_glyph_cache_entry *entry)
229{
230 if (entry->lru_prev == NULL)
231 return; /* At front already */
232
233 /* Unlink */
234 entry->lru_prev->lru_next = entry->lru_next;
235 if (entry->lru_next)
236 entry->lru_next->lru_prev = entry->lru_prev;
237 else
238 cache->lru_tail = entry->lru_prev;
239 /* Relink */
240 entry->lru_next = cache->lru_head;
241 if (entry->lru_next)
242 entry->lru_next->lru_prev = entry;
243 cache->lru_head = entry;
244 entry->lru_prev = NULL;
245}
246
247fz_glyph *
248fz_render_glyph(fz_context *ctx, fz_font *font, int gid, fz_matrix *ctm, fz_colorspace *model, const fz_irect *scissor, int alpha, int aa)
249{
250 fz_glyph_cache *cache;
251 fz_glyph_key key;
252 fz_matrix subpix_ctm;
253 fz_irect subpix_scissor;
254 float size;
255 fz_glyph *val;
256 int do_cache, locked, caching;
257 fz_glyph_cache_entry *entry;
258 unsigned hash;
259 int is_ft_font = !!fz_font_ft_face(ctx, font);
260
261 fz_var(locked);
262 fz_var(caching);
263 fz_var(val);
264
265 memset(&key, 0, sizeof key);
266 size = fz_subpixel_adjust(ctx, ctm, &subpix_ctm, &key.e, &key.f);
267 if (size <= MAX_GLYPH_SIZE)
268 {
269 scissor = &fz_infinite_irect;
270 do_cache = 1;
271 }
272 else
273 {
274 if (is_ft_font)
275 return NULL;
276 subpix_scissor.x0 = scissor->x0 - floorf(ctm->e);
277 subpix_scissor.y0 = scissor->y0 - floorf(ctm->f);
278 subpix_scissor.x1 = scissor->x1 - floorf(ctm->e);
279 subpix_scissor.y1 = scissor->y1 - floorf(ctm->f);
280 scissor = &subpix_scissor;
281 do_cache = 0;
282 }
283
284 cache = ctx->glyph_cache;
285
286 key.font = font;
287 key.gid = gid;
288 key.a = subpix_ctm.a * 65536;
289 key.b = subpix_ctm.b * 65536;
290 key.c = subpix_ctm.c * 65536;
291 key.d = subpix_ctm.d * 65536;
292 key.aa = aa;
293
294 hash = do_hash((unsigned char *)&key, sizeof(key)) % GLYPH_HASH_LEN;
295 fz_lock(ctx, FZ_LOCK_GLYPHCACHE);
296 entry = cache->entry[hash];
297 while (entry)
298 {
299 if (memcmp(&entry->key, &key, sizeof(key)) == 0)
300 {
301 move_to_front(cache, entry);
302 val = fz_keep_glyph(ctx, entry->val);
303 fz_unlock(ctx, FZ_LOCK_GLYPHCACHE);
304 return val;
305 }
306 entry = entry->bucket_next;
307 }
308
309 locked = 1;
310 caching = 0;
311 val = NULL;
312
313 fz_try(ctx)
314 {
315 if (is_ft_font)
316 {
317 val = fz_render_ft_glyph(ctx, font, gid, subpix_ctm, aa);
318 }
319 else if (fz_font_t3_procs(ctx, font))
320 {
321 /* We drop the glyphcache here, and execute the t3
322 * glyph code. The danger here is that some other
323 * thread will come along, and want the same glyph
324 * too. If it does, we may both end up rendering
325 * pixmaps. We cope with this later on, by ensuring
326 * that only one gets inserted into the cache. If
327 * we insert ours to find one already there, we
328 * abandon ours, and use the one there already.
329 */
330 fz_unlock(ctx, FZ_LOCK_GLYPHCACHE);
331 locked = 0;
332 val = fz_render_t3_glyph(ctx, font, gid, subpix_ctm, model, scissor, aa);
333 fz_lock(ctx, FZ_LOCK_GLYPHCACHE);
334 locked = 1;
335 }
336 else
337 {
338 fz_warn(ctx, "assert: uninitialized font structure");
339 }
340 if (val && do_cache)
341 {
342 if (val->w < MAX_GLYPH_SIZE && val->h < MAX_GLYPH_SIZE)
343 {
344 /* If we throw an exception whilst caching,
345 * just ignore the exception and carry on. */
346 caching = 1;
347 if (!is_ft_font)
348 {
349 /* We had to unlock. Someone else might
350 * have rendered in the meantime */
351 entry = cache->entry[hash];
352 while (entry)
353 {
354 if (memcmp(&entry->key, &key, sizeof(key)) == 0)
355 {
356 fz_drop_glyph(ctx, val);
357 move_to_front(cache, entry);
358 val = fz_keep_glyph(ctx, entry->val);
359 goto unlock_and_return_val;
360 }
361 entry = entry->bucket_next;
362 }
363 }
364
365 entry = fz_malloc_struct(ctx, fz_glyph_cache_entry);
366 entry->key = key;
367 entry->hash = hash;
368 entry->bucket_next = cache->entry[hash];
369 if (entry->bucket_next)
370 entry->bucket_next->bucket_prev = entry;
371 cache->entry[hash] = entry;
372 entry->val = fz_keep_glyph(ctx, val);
373 fz_keep_font(ctx, key.font);
374
375 entry->lru_next = cache->lru_head;
376 if (entry->lru_next)
377 entry->lru_next->lru_prev = entry;
378 else
379 cache->lru_tail = entry;
380 cache->lru_head = entry;
381
382 cache->total += fz_glyph_size(ctx, val);
383 while (cache->total > MAX_CACHE_SIZE)
384 {
385#ifndef NDEBUG
386 cache->num_evictions++;
387 cache->evicted += fz_glyph_size(ctx, cache->lru_tail->val);
388#endif
389 drop_glyph_cache_entry(ctx, cache->lru_tail);
390 }
391 }
392 }
393unlock_and_return_val:
394 {
395 }
396 }
397 fz_always(ctx)
398 {
399 if (locked)
400 fz_unlock(ctx, FZ_LOCK_GLYPHCACHE);
401 }
402 fz_catch(ctx)
403 {
404 if (caching)
405 fz_warn(ctx, "cannot encache glyph; continuing");
406 else
407 fz_rethrow(ctx);
408 }
409
410 return val;
411}
412
413fz_pixmap *
414fz_render_glyph_pixmap(fz_context *ctx, fz_font *font, int gid, fz_matrix *ctm, const fz_irect *scissor, int aa)
415{
416 fz_pixmap *val = NULL;
417 unsigned char qe, qf;
418 fz_matrix subpix_ctm;
419 float size = fz_subpixel_adjust(ctx, ctm, &subpix_ctm, &qe, &qf);
420 int is_ft_font = !!fz_font_ft_face(ctx, font);
421
422 if (size <= MAX_GLYPH_SIZE)
423 {
424 scissor = &fz_infinite_irect;
425 }
426 else
427 {
428 if (is_ft_font)
429 return NULL;
430 }
431
432 if (is_ft_font)
433 {
434 val = fz_render_ft_glyph_pixmap(ctx, font, gid, subpix_ctm, aa);
435 }
436 else if (fz_font_t3_procs(ctx, font))
437 {
438 val = fz_render_t3_glyph_pixmap(ctx, font, gid, subpix_ctm, NULL, scissor, aa);
439 }
440 else
441 {
442 fz_warn(ctx, "assert: uninitialized font structure");
443 val = NULL;
444 }
445
446 return val;
447}
448
449void
450fz_dump_glyph_cache_stats(fz_context *ctx)
451{
452 fz_glyph_cache *cache = ctx->glyph_cache;
453 fprintf(stderr, "Glyph Cache Size: %zu\n", cache->total);
454#ifndef NDEBUG
455 fprintf(stderr, "Glyph Cache Evictions: %d (%zu bytes)\n", cache->num_evictions, cache->evicted);
456#endif
457}
458