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