Be smarter when quantising sub pixel positions for glyphs.

For large glyphs, sub pixel positioning is supremely unimportant.
Even for smaller glyphs, we don't need 5*5 possible sub pixel
positions. Base the degree of sub pixel quantisation on the size
of the glyphs.

This should result in better cache use.

We push all the glyph sub positioning logic into fz_render_glyph
(and fz_render_stroked_glyph). This simplifies the calling code.

We also tweak fz_render_glyph so that it updates the transform it
is called with to reflect the sub pixel positioning. This solves
various problems: Firstly, we can round positions both up and down
to achieve a smaller net displacement (e.g. (0.99, 0.99) can go
to (1,1) rather than (0.75, 0.75) if we have a subpixel position
resolution of 1/4 pixels).

Secondly, glyphs that are drawn from outlines will have exactly the
same subpixel changes applied. This is unlikely to be noticable, but
it does mean that baselines should avoid having any shifts in them.

Finally, it enables us to avoid lots of unnecessary copying of
matrices, hopefully reducing overhead.

3 files changed, 97 insertions, 82 deletions

diff --git a/source/fitz/draw-device.c b/source/fitz/draw-device.c
index 1cb76ae8..79886405 100644
--- a/source/fitz/draw-device.c
+++ b/source/fitz/draw-device.c
@@ -1,10 +1,6 @@
 #include "mupdf/fitz.h"
 #include "draw-imp.h"
 
-#define QUANT(x,a) (((int)((x) * (a))) / (a))
-#define HSUBPIX 5.0
-#define VSUBPIX 5.0
-
 #define STACK_SIZE 96
 
 /* Enable the following to attempt to support knockout and/or isolated
@@ -523,12 +519,11 @@ fz_draw_fill_text(fz_device *devp, fz_text *text, const fz_matrix *ctm,
 	unsigned char colorbv[FZ_MAX_COLORS + 1];
 	unsigned char shapebv;
 	float colorfv[FZ_MAX_COLORS];
-	fz_matrix tm, trm, trunc_trm;
+	fz_matrix tm, trm;
 	fz_glyph *glyph;
-	int i, x, y, gid;
+	int i, gid;
 	fz_draw_state *state = &dev->stack[dev->top];
 	fz_colorspace *model = state->dest->colorspace;
-	fz_irect scissor;
 
 	if (state->blendmode & FZ_BLEND_KNOCKOUT)
 		state = fz_knockout_begin(dev);
@@ -550,22 +545,13 @@ fz_draw_fill_text(fz_device *devp, fz_text *text, const fz_matrix *ctm,
 		tm.e = text->items[i].x;
 		tm.f = text->items[i].y;
 		fz_concat(&trm, &tm, ctm);
-		x = floorf(trm.e);
-		y = floorf(trm.f);
-
-		trunc_trm = trm;
-		trunc_trm.e = QUANT(trm.e - floorf(trm.e), HSUBPIX);
-		trunc_trm.f = QUANT(trm.f - floorf(trm.f), VSUBPIX);
 
-		scissor.x0 = state->scissor.x0 - x;
-		scissor.y0 = state->scissor.y0 - y;
-		scissor.x1 = state->scissor.x1 - x;
-		scissor.y1 = state->scissor.y1 - y;
-
-		glyph = fz_render_glyph(dev->ctx, text->font, gid, &trunc_trm, model, scissor);
+		glyph = fz_render_glyph(dev->ctx, text->font, gid, &trm, model, &state->scissor);
 		if (glyph)
 		{
 			fz_pixmap *pixmap = glyph->pixmap;
+			int x = (int)trm.e;
+			int y = (int)trm.f;
 			if (pixmap == NULL || pixmap->n == 1)
 			{
 				draw_glyph(colorbv, state->dest, glyph, x, y, &state->scissor);
@@ -606,12 +592,11 @@ fz_draw_stroke_text(fz_device *devp, fz_text *text, fz_stroke_state *stroke,
 	fz_draw_device *dev = devp->user;
 	unsigned char colorbv[FZ_MAX_COLORS + 1];
 	float colorfv[FZ_MAX_COLORS];
-	fz_matrix tm, trm, trunc_trm;
+	fz_matrix tm, trm;
 	fz_glyph *glyph;
-	int i, x, y, gid;
+	int i, gid;
 	fz_draw_state *state = &dev->stack[dev->top];
 	fz_colorspace *model = state->dest->colorspace;
-	fz_irect scissor;
 
 	if (state->blendmode & FZ_BLEND_KNOCKOUT)
 		state = fz_knockout_begin(dev);
@@ -632,21 +617,12 @@ fz_draw_stroke_text(fz_device *devp, fz_text *text, fz_stroke_state *stroke,
 		tm.e = text->items[i].x;
 		tm.f = text->items[i].y;
 		fz_concat(&trm, &tm, ctm);
-		x = floorf(trm.e);
-		y = floorf(trm.f);
-
-		trunc_trm = trm;
-		trunc_trm.e = QUANT(trm.e - floorf(trm.e), HSUBPIX);
-		trunc_trm.f = QUANT(trm.f - floorf(trm.f), VSUBPIX);
 
-		scissor.x0 = state->scissor.x0 - x;
-		scissor.y0 = state->scissor.y0 - y;
-		scissor.x1 = state->scissor.x1 - x;
-		scissor.y1 = state->scissor.y1 - y;
-
-		glyph = fz_render_stroked_glyph(dev->ctx, text->font, gid, &trunc_trm, ctm, stroke, scissor);
+		glyph = fz_render_stroked_glyph(dev->ctx, text->font, gid, &trm, ctm, stroke, &state->scissor);
 		if (glyph)
 		{
+			int x = (int)trm.e;
+			int y = (int)trm.f;
 			draw_glyph(colorbv, state->dest, glyph, x, y, &state->scissor);
 			if (state->shape)
 				draw_glyph(colorbv, state->shape, glyph, x, y, &state->scissor);
@@ -678,9 +654,9 @@ fz_draw_clip_text(fz_device *devp, fz_text *text, const fz_matrix *ctm, int accu
 	fz_context *ctx = dev->ctx;
 	fz_irect bbox;
 	fz_pixmap *mask, *dest, *shape;
-	fz_matrix tm, trm, trunc_trm;
+	fz_matrix tm, trm;
 	fz_glyph *glyph;
-	int i, x, y, gid;
+	int i, gid;
 	fz_draw_state *state;
 	fz_colorspace *model;
 
@@ -742,8 +718,6 @@ fz_draw_clip_text(fz_device *devp, fz_text *text, const fz_matrix *ctm, int accu
 
 			for (i = 0; i < text->len; i++)
 			{
-				fz_irect scissor;
-
 				gid = text->items[i].gid;
 				if (gid < 0)
 					continue;
@@ -751,20 +725,12 @@ fz_draw_clip_text(fz_device *devp, fz_text *text, const fz_matrix *ctm, int accu
 				tm.e = text->items[i].x;
 				tm.f = text->items[i].y;
 				fz_concat(&trm, &tm, ctm);
-				x = floorf(trm.e);
-				y = floorf(trm.f);
-
-				trunc_trm = trm;
-				trunc_trm.e = QUANT(trm.e - floorf(trm.e), HSUBPIX);
-				trunc_trm.f = QUANT(trm.f - floorf(trm.f), VSUBPIX);
-				scissor.x0 = bbox.x0 - x;
-				scissor.y0 = bbox.y0 - y;
-				scissor.x1 = bbox.x1 - x;
-				scissor.y1 = bbox.y1 - y;
-
-				glyph = fz_render_glyph(dev->ctx, text->font, gid, &trunc_trm, model, scissor);
+
+				glyph = fz_render_glyph(dev->ctx, text->font, gid, &trm, model, &state->scissor);
 				if (glyph)
 				{
+					int x = (int)trm.e;
+					int y = (int)trm.f;
 					draw_glyph(NULL, mask, glyph, x, y, &bbox);
 					if (state[1].shape)
 						draw_glyph(NULL, state[1].shape, glyph, x, y, &bbox);
@@ -820,9 +786,9 @@ fz_draw_clip_stroke_text(fz_device *devp, fz_text *text, fz_stroke_state *stroke
 	fz_context *ctx = dev->ctx;
 	fz_irect bbox;
 	fz_pixmap *mask, *dest, *shape;
-	fz_matrix tm, trm, trunc_trm;
+	fz_matrix tm, trm;
 	fz_glyph *glyph;
-	int i, x, y, gid;
+	int i, gid;
 	fz_draw_state *state = push_stack(dev);
 	fz_colorspace *model = state->dest->colorspace;
 	fz_rect rect;
@@ -857,7 +823,6 @@ fz_draw_clip_stroke_text(fz_device *devp, fz_text *text, fz_stroke_state *stroke
 
 			for (i = 0; i < text->len; i++)
 			{
-				fz_irect scissor;
 				gid = text->items[i].gid;
 				if (gid < 0)
 					continue;
@@ -865,21 +830,12 @@ fz_draw_clip_stroke_text(fz_device *devp, fz_text *text, fz_stroke_state *stroke
 				tm.e = text->items[i].x;
 				tm.f = text->items[i].y;
 				fz_concat(&trm, &tm, ctm);
-				x = floorf(trm.e);
-				y = floorf(trm.f);
-
-				trunc_trm = trm;
-				trunc_trm.e = QUANT(trm.e - floorf(trm.e), HSUBPIX);
-				trunc_trm.f = QUANT(trm.f - floorf(trm.f), VSUBPIX);
-
-				scissor.x0 = bbox.x0 - x;
-				scissor.y0 = bbox.y0 - y;
-				scissor.x1 = bbox.x1 - x;
-				scissor.y1 = bbox.y1 - y;
 
-				glyph = fz_render_stroked_glyph(dev->ctx, text->font, gid, &trunc_trm, ctm, stroke, scissor);
+				glyph = fz_render_stroked_glyph(dev->ctx, text->font, gid, &trm, ctm, stroke, &state->scissor);
 				if (glyph)
 				{
+					int x = (int)trm.e;
+					int y = (int)trm.f;
 					draw_glyph(NULL, mask, glyph, x, y, &bbox);
 					if (shape)
 						draw_glyph(NULL, shape, glyph, x, y, &bbox);
diff --git a/source/fitz/draw-glyph.c b/source/fitz/draw-glyph.c
index 3486cb99..3609cc8b 100644
--- a/source/fitz/draw-glyph.c
+++ b/source/fitz/draw-glyph.c
@@ -131,13 +131,47 @@ fz_keep_glyph_cache(fz_context *ctx)
 }
 
 fz_glyph *
-fz_render_stroked_glyph(fz_context *ctx, fz_font *font, int gid, const fz_matrix *trm, const fz_matrix *ctm, fz_stroke_state *stroke, fz_irect scissor)
+fz_render_stroked_glyph(fz_context *ctx, fz_font *font, int gid, fz_matrix *trm, const fz_matrix *ctm, fz_stroke_state *stroke, const fz_irect *scissor)
 {
 	if (font->ft_face)
 	{
+		float size = fz_matrix_expansion(trm);
+		fz_matrix subpix_trm = *trm;
+		unsigned char qe, qf;
+		int q;
+		float pix_e, pix_f, r;
+
+		/* Quantise the subpixel positions. */
+		/* We never need more than 4 subpixel positions for glyphs - arguably
+		 * even that is too much. */
+		if (size >= 48)
+			q = 0, r = 0.5f;
+		else if (size >= 24)
+			q = 128, r = 0.25f;
+		else
+			q = 192, r = 0.125f;
+
+		/* Split translation into pixel and subpixel parts */
+		subpix_trm.e += r;
+		pix_e = floorf(subpix_trm.e);
+		subpix_trm.e -= pix_e;
+		subpix_trm.f += r;
+		pix_f = floorf(subpix_trm.f);
+		subpix_trm.f -= pix_f;
+
+		/* Quantise the subpixel part */
+		qe = (int)(subpix_trm.e * 256) & q;
+		qf = (int)(subpix_trm.f * 256) & q;
+		subpix_trm.e = qe / 256.0f;
+		subpix_trm.f = qf / 256.0f;
+
+		/* Reassemble the complete translation */
+		trm->e = subpix_trm.e + pix_e;
+		trm->f = subpix_trm.f + pix_f;
+
 		if (stroke->dash_len > 0)
 			return NULL;
-		return fz_render_ft_stroked_glyph(ctx, font, gid, trm, ctm, stroke);
+		return fz_render_ft_stroked_glyph(ctx, font, gid, &subpix_trm, ctm, stroke);
 	}
 	return fz_render_glyph(ctx, font, gid, trm, NULL, scissor);
 }
@@ -188,23 +222,25 @@ move_to_front(fz_glyph_cache *cache, fz_glyph_cache_entry *entry)
 		This must not be inserted into the cache.
  */
 fz_glyph *
-fz_render_glyph(fz_context *ctx, fz_font *font, int gid, const fz_matrix *ctm, fz_colorspace *model, fz_irect scissor)
+fz_render_glyph(fz_context *ctx, fz_font *font, int gid, fz_matrix *ctm, fz_colorspace *model, const fz_irect *scissor)
 {
 	fz_glyph_cache *cache;
 	fz_glyph_key key;
 	fz_glyph *val;
 	float size = fz_matrix_expansion(ctm);
 	int do_cache, locked, caching;
-	fz_matrix local_ctm = *ctm;
+	fz_matrix subpix_ctm = *ctm;
 	fz_glyph_cache_entry *entry;
 	unsigned hash;
+	int q;
+	float pix_e, pix_f, r;
 
 	fz_var(locked);
 	fz_var(caching);
 
 	if (size <= MAX_GLYPH_SIZE)
 	{
-		scissor = fz_infinite_irect;
+		scissor = &fz_infinite_irect;
 		do_cache = 1;
 	}
 	else
@@ -216,19 +252,42 @@ fz_render_glyph(fz_context *ctx, fz_font *font, int gid, const fz_matrix *ctm, f
 
 	cache = ctx->glyph_cache;
 
+	/* Quantise the subpixel positions. */
+	/* We never need more than 4 subpixel positions for glyphs - arguably
+	 * even that is too much. */
+	if (size >= 48)
+		q = 0, r = 0.5f;
+	else if (size >= 24)
+		q = 128, r = 0.25f;
+	else
+		q = 192, r = 0.125f;
+
+	/* Split translation into pixel and subpixel parts */
+	subpix_ctm.e += r;
+	pix_e = floorf(subpix_ctm.e);
+	subpix_ctm.e -= pix_e;
+	subpix_ctm.f += r;
+	pix_f = floorf(subpix_ctm.f);
+	subpix_ctm.f -= pix_f;
+
 	memset(&key, 0, sizeof key);
 	key.font = font;
 	key.gid = gid;
-	key.a = local_ctm.a * 65536;
-	key.b = local_ctm.b * 65536;
-	key.c = local_ctm.c * 65536;
-	key.d = local_ctm.d * 65536;
-	key.e = (local_ctm.e - floorf(local_ctm.e)) * 256;
-	key.f = (local_ctm.f - floorf(local_ctm.f)) * 256;
+	key.a = subpix_ctm.a * 65536;
+	key.b = subpix_ctm.b * 65536;
+	key.c = subpix_ctm.c * 65536;
+	key.d = subpix_ctm.d * 65536;
 	key.aa = fz_aa_level(ctx);
 
-	local_ctm.e = floorf(local_ctm.e) + key.e / 256.0f;
-	local_ctm.f = floorf(local_ctm.f) + key.f / 256.0f;
+	/* Quantise the subpixel part */
+	key.e = (int)(subpix_ctm.e * 256) & q;
+	key.f = (int)(subpix_ctm.f * 256) & q;
+	subpix_ctm.e = key.e / 256.0f;
+	subpix_ctm.f = key.f / 256.0f;
+
+	/* Reassemble the complete translation */
+	ctm->e = subpix_ctm.e + pix_e;
+	ctm->f = subpix_ctm.f + pix_f;
 
 	fz_lock(ctx, FZ_LOCK_GLYPHCACHE);
 	hash = do_hash((unsigned char *)&key, sizeof(key)) % GLYPH_HASH_LEN;
@@ -252,7 +311,7 @@ fz_render_glyph(fz_context *ctx, fz_font *font, int gid, const fz_matrix *ctm, f
 	{
 		if (font->ft_face)
 		{
-			val = fz_render_ft_glyph(ctx, font, gid, &local_ctm, key.aa);
+			val = fz_render_ft_glyph(ctx, font, gid, &subpix_ctm, key.aa);
 		}
 		else if (font->t3procs)
 		{
@@ -267,7 +326,7 @@ fz_render_glyph(fz_context *ctx, fz_font *font, int gid, const fz_matrix *ctm, f
 			 */
 			fz_unlock(ctx, FZ_LOCK_GLYPHCACHE);
 			locked = 0;
-			val = fz_render_t3_glyph(ctx, font, gid, &local_ctm, model, scissor);
+			val = fz_render_t3_glyph(ctx, font, gid, &subpix_ctm, model, scissor);
 			fz_lock(ctx, FZ_LOCK_GLYPHCACHE);
 			locked = 1;
 		}
diff --git a/source/fitz/font.c b/source/fitz/font.c
index 1f44d096..1aeab3a6 100644
--- a/source/fitz/font.c
+++ b/source/fitz/font.c
@@ -934,7 +934,7 @@ fz_bound_t3_glyph(fz_context *ctx, fz_font *font, int gid, const fz_matrix *trm,
 }
 
 fz_glyph *
-fz_render_t3_glyph(fz_context *ctx, fz_font *font, int gid, const fz_matrix *trm, fz_colorspace *model, fz_irect scissor)
+fz_render_t3_glyph(fz_context *ctx, fz_font *font, int gid, const fz_matrix *trm, fz_colorspace *model, const fz_irect *scissor)
 {
 	fz_display_list *list;
 	fz_matrix ctm;
@@ -970,7 +970,7 @@ fz_render_t3_glyph(fz_context *ctx, fz_font *font, int gid, const fz_matrix *trm
 
 	fz_expand_rect(fz_bound_glyph(ctx, font, gid, trm, &bounds), 1);
 	fz_irect_from_rect(&bbox, &bounds);
-	fz_intersect_irect(&bbox, &scissor);
+	fz_intersect_irect(&bbox, scissor);
 
 	glyph = fz_new_pixmap_with_bbox(ctx, model ? model : fz_device_gray(ctx), &bbox);
 	fz_clear_pixmap(ctx, glyph);