Subversion Repositories Kolibri OS

#include "fitz.h"

#define BBOX_MIN -(1<<20)

#define BBOX_MAX (1<<20)

/* divide and floor towards -inf */

static inline int fz_idiv(int a, int b)

{

	return a < 0 ? (a - b + 1) / b : a / b;

}

/* If AA_BITS is defined, then we assume constant N bits of antialiasing. We

 * will attempt to provide at least that number of bits of accuracy in the

 * antialiasing (to a maximum of 8). If it is defined to be 0 then no

 * antialiasing is done. If it is undefined to we will leave the antialiasing

 * accuracy as a run time choice.

 */

#ifndef AA_BITS

#define AA_SCALE(x) ((x * fz_aa_scale) >> 8)

static int fz_aa_hscale = 17;

static int fz_aa_vscale = 15;

static int fz_aa_scale = 256;

static int fz_aa_level = 8;

#elif AA_BITS > 6

#define AA_SCALE(x) (x)

#define fz_aa_hscale 17

#define fz_aa_vscale 15

#define fz_aa_level 8

#elif AA_BITS > 4

#define AA_SCALE(x) ((x * 255) >> 6)

#define fz_aa_hscale 8

#define fz_aa_vscale 8

#define fz_aa_level 6

#elif AA_BITS > 2

#define AA_SCALE(x) (x * 17)

#define fz_aa_hscale 5

#define fz_aa_vscale 3

#define fz_aa_level 4

#elif AA_BITS > 0

#define AA_SCALE(x) ((x * 255) >> 2)

#define fz_aa_hscale 2

#define fz_aa_vscale 2

#define fz_aa_level 2

#else

#define AA_SCALE(x) (x * 255)

#define fz_aa_hscale 1

#define fz_aa_vscale 1

#define fz_aa_level 0

#endif

int

fz_get_aa_level(void)

{

	return fz_aa_level;

}

void

fz_set_aa_level(int level)

{

#ifdef AA_BITS

	fz_warn("anti-aliasing was compiled with a fixed precision of %d bits", fz_aa_level);

#else

	if (level > 6)

	{

		fz_aa_hscale = 17;

		fz_aa_vscale = 15;

		fz_aa_level = 8;

	}

	else if (level > 4)

	{

		fz_aa_hscale = 8;

		fz_aa_vscale = 8;

		fz_aa_level = 6;

	}

	else if (level > 2)

	{

		fz_aa_hscale = 5;

		fz_aa_vscale = 3;

		fz_aa_level = 4;

	}

	else if (level > 0)

	{

		fz_aa_hscale = 2;

		fz_aa_vscale = 2;

		fz_aa_level = 2;

	}

	else

	{

		fz_aa_hscale = 1;

		fz_aa_vscale = 1;

		fz_aa_level = 0;

	}

	fz_aa_scale = 0xFF00 / (fz_aa_hscale * fz_aa_vscale);

#endif

}

/*

 * Global Edge List -- list of straight path segments for scan conversion

 *

 * Stepping along the edges is with bresenham's line algorithm.

 *

 * See Mike Abrash -- Graphics Programming Black Book (notably chapter 40)

 */

typedef struct fz_edge_s fz_edge;

struct fz_edge_s

{

	int x, e, h, y;

	int adj_up, adj_down;

	int xmove;

	int xdir, ydir; /* -1 or +1 */

};

struct fz_gel_s

{

	fz_bbox clip;

	fz_bbox bbox;

	int cap, len;

	fz_edge *edges;

	int acap, alen;

	fz_edge **active;

};

fz_gel *

fz_new_gel(void)

{

	fz_gel *gel;

	gel = fz_malloc(sizeof(fz_gel));

	gel->cap = 512;

	gel->len = 0;

	gel->edges = fz_calloc(gel->cap, sizeof(fz_edge));

	gel->clip.x0 = gel->clip.y0 = BBOX_MAX;

	gel->clip.x1 = gel->clip.y1 = BBOX_MIN;

	gel->bbox.x0 = gel->bbox.y0 = BBOX_MAX;

	gel->bbox.x1 = gel->bbox.y1 = BBOX_MIN;

	gel->acap = 64;

	gel->alen = 0;

	gel->active = fz_calloc(gel->acap, sizeof(fz_edge*));

	return gel;

}

void

fz_reset_gel(fz_gel *gel, fz_bbox clip)

{

	if (fz_is_infinite_rect(clip))

	{

		gel->clip.x0 = gel->clip.y0 = BBOX_MAX;

		gel->clip.x1 = gel->clip.y1 = BBOX_MIN;

	}

	else {

		gel->clip.x0 = clip.x0 * fz_aa_hscale;

		gel->clip.x1 = clip.x1 * fz_aa_hscale;

		gel->clip.y0 = clip.y0 * fz_aa_vscale;

		gel->clip.y1 = clip.y1 * fz_aa_vscale;

	}

	gel->bbox.x0 = gel->bbox.y0 = BBOX_MAX;

	gel->bbox.x1 = gel->bbox.y1 = BBOX_MIN;

	gel->len = 0;

}

void

fz_free_gel(fz_gel *gel)

{

	fz_free(gel->active);

	fz_free(gel->edges);

	fz_free(gel);

}

fz_bbox

fz_bound_gel(fz_gel *gel)

{

	fz_bbox bbox;

	if (gel->len == 0)

		return fz_empty_bbox;

	bbox.x0 = fz_idiv(gel->bbox.x0, fz_aa_hscale);

	bbox.y0 = fz_idiv(gel->bbox.y0, fz_aa_vscale);

	bbox.x1 = fz_idiv(gel->bbox.x1, fz_aa_hscale) + 1;

	bbox.y1 = fz_idiv(gel->bbox.y1, fz_aa_vscale) + 1;

	return bbox;

}

enum { INSIDE, OUTSIDE, LEAVE, ENTER };

#define clip_lerp_y(v,m,x0,y0,x1,y1,t) clip_lerp_x(v,m,y0,x0,y1,x1,t)

static int

clip_lerp_x(int val, int m, int x0, int y0, int x1, int y1, int *out)

{

	int v0out = m ? x0 > val : x0 < val;

	int v1out = m ? x1 > val : x1 < val;

	if (v0out + v1out == 0)

		return INSIDE;

	if (v0out + v1out == 2)

		return OUTSIDE;

	if (v1out)

	{

		*out = y0 + (y1 - y0) * (val - x0) / (x1 - x0);

		return LEAVE;

	}

	else

	{

		*out = y1 + (y0 - y1) * (val - x1) / (x0 - x1);

		return ENTER;

	}

}

static void

fz_insert_gel_raw(fz_gel *gel, int x0, int y0, int x1, int y1)

{

	fz_edge *edge;

	int dx, dy;

	int winding;

	int width;

	int tmp;

	if (y0 == y1)

		return;

	if (y0 > y1) {

		winding = -1;

		tmp = x0; x0 = x1; x1 = tmp;

		tmp = y0; y0 = y1; y1 = tmp;

	}

	else

		winding = 1;

	if (x0 < gel->bbox.x0) gel->bbox.x0 = x0;

	if (x0 > gel->bbox.x1) gel->bbox.x1 = x0;

	if (x1 < gel->bbox.x0) gel->bbox.x0 = x1;

	if (x1 > gel->bbox.x1) gel->bbox.x1 = x1;

	if (y0 < gel->bbox.y0) gel->bbox.y0 = y0;

	if (y1 > gel->bbox.y1) gel->bbox.y1 = y1;

	if (gel->len + 1 == gel->cap) {

		gel->cap = gel->cap + 512;

		gel->edges = fz_realloc(gel->edges, gel->cap, sizeof(fz_edge));

	}

	edge = &gel->edges[gel->len++];

	dy = y1 - y0;

	dx = x1 - x0;

	width = ABS(dx);

	edge->xdir = dx > 0 ? 1 : -1;

	edge->ydir = winding;

	edge->x = x0;

	edge->y = y0;

	edge->h = dy;

	edge->adj_down = dy;

	/* initial error term going l->r and r->l */

	if (dx >= 0)

		edge->e = 0;

	else

		edge->e = -dy + 1;

	/* y-major edge */

	if (dy >= width) {

		edge->xmove = 0;

		edge->adj_up = width;

	}

	/* x-major edge */

	else {

		edge->xmove = (width / dy) * edge->xdir;

		edge->adj_up = width % dy;

	}

}

void

fz_insert_gel(fz_gel *gel, float fx0, float fy0, float fx1, float fy1)

{

	int x0, y0, x1, y1;

	int d, v;

	fx0 = floorf(fx0 * fz_aa_hscale);

	fx1 = floorf(fx1 * fz_aa_hscale);

	fy0 = floorf(fy0 * fz_aa_vscale);

	fy1 = floorf(fy1 * fz_aa_vscale);

	x0 = CLAMP(fx0, BBOX_MIN, BBOX_MAX);

	y0 = CLAMP(fy0, BBOX_MIN, BBOX_MAX);

	x1 = CLAMP(fx1, BBOX_MIN, BBOX_MAX);

	y1 = CLAMP(fy1, BBOX_MIN, BBOX_MAX);

	d = clip_lerp_y(gel->clip.y0, 0, x0, y0, x1, y1, &v);

	if (d == OUTSIDE) return;

	if (d == LEAVE) { y1 = gel->clip.y0; x1 = v; }

	if (d == ENTER) { y0 = gel->clip.y0; x0 = v; }

	d = clip_lerp_y(gel->clip.y1, 1, x0, y0, x1, y1, &v);

	if (d == OUTSIDE) return;

	if (d == LEAVE) { y1 = gel->clip.y1; x1 = v; }

	if (d == ENTER) { y0 = gel->clip.y1; x0 = v; }

	d = clip_lerp_x(gel->clip.x0, 0, x0, y0, x1, y1, &v);

	if (d == OUTSIDE) {

		x0 = x1 = gel->clip.x0;

	}

	if (d == LEAVE) {

		fz_insert_gel_raw(gel, gel->clip.x0, v, gel->clip.x0, y1);

		x1 = gel->clip.x0;

		y1 = v;

	}

	if (d == ENTER) {

		fz_insert_gel_raw(gel, gel->clip.x0, y0, gel->clip.x0, v);

		x0 = gel->clip.x0;

		y0 = v;

	}

	d = clip_lerp_x(gel->clip.x1, 1, x0, y0, x1, y1, &v);

	if (d == OUTSIDE) {

		x0 = x1 = gel->clip.x1;

	}

	if (d == LEAVE) {

		fz_insert_gel_raw(gel, gel->clip.x1, v, gel->clip.x1, y1);

		x1 = gel->clip.x1;

		y1 = v;

	}

	if (d == ENTER) {

		fz_insert_gel_raw(gel, gel->clip.x1, y0, gel->clip.x1, v);

		x0 = gel->clip.x1;

		y0 = v;

	}

	fz_insert_gel_raw(gel, x0, y0, x1, y1);

}

void

fz_sort_gel(fz_gel *gel)

{

	fz_edge *a = gel->edges;

	int n = gel->len;

	int h, i, k;

	fz_edge t;

	h = 1;

	if (n < 14) {

		h = 1;

	}

	else {

		while (h < n)

			h = 3 * h + 1;

		h /= 3;

		h /= 3;

	}

	while (h > 0)

	{

		for (i = 0; i < n; i++) {

			t = a[i];

			k = i - h;

			/* TODO: sort on y major, x minor */

			while (k >= 0 && a[k].y > t.y) {

				a[k + h] = a[k];

				k -= h;

			}

			a[k + h] = t;

		}

		h /= 3;

	}

}

int

fz_is_rect_gel(fz_gel *gel)

{

	/* a rectangular path is converted into two vertical edges of identical height */

	if (gel->len == 2)

	{

		fz_edge *a = gel->edges + 0;

		fz_edge *b = gel->edges + 1;

		return a->y == b->y && a->h == b->h &&

			a->xmove == 0 && a->adj_up == 0 &&

			b->xmove == 0 && b->adj_up == 0;

	}

	return 0;

}

/*

 * Active Edge List -- keep track of active edges while sweeping

 */

static void

sort_active(fz_edge **a, int n)

{

	int h, i, k;

	fz_edge *t;

	h = 1;

	if (n < 14) {

		h = 1;

	}

	else {

		while (h < n)

			h = 3 * h + 1;

		h /= 3;

		h /= 3;

	}

	while (h > 0)

	{

		for (i = 0; i < n; i++) {

			t = a[i];

			k = i - h;

			while (k >= 0 && a[k]->x > t->x) {

				a[k + h] = a[k];

				k -= h;

			}

			a[k + h] = t;

		}

		h /= 3;

	}

}

static void

insert_active(fz_gel *gel, int y, int *e)

{

	/* insert edges that start here */

	while (*e < gel->len && gel->edges[*e].y == y) {

		if (gel->alen + 1 == gel->acap) {

			int newcap = gel->acap + 64;

			fz_edge **newactive = fz_realloc(gel->active, newcap, sizeof(fz_edge*));

			gel->active = newactive;

			gel->acap = newcap;

		}

		gel->active[gel->alen++] = &gel->edges[(*e)++];

	}

	/* shell-sort the edges by increasing x */

	sort_active(gel->active, gel->alen);

}

static void

advance_active(fz_gel *gel)

{

	fz_edge *edge;

	int i = 0;

	while (i < gel->alen)

	{

		edge = gel->active[i];

		edge->h --;

		/* terminator! */

		if (edge->h == 0) {

			gel->active[i] = gel->active[--gel->alen];

		}

		else {

			edge->x += edge->xmove;

			edge->e += edge->adj_up;

			if (edge->e > 0) {

				edge->x += edge->xdir;

				edge->e -= edge->adj_down;

			}

			i ++;

		}

	}

}

/*

 * Anti-aliased scan conversion.

 */

static inline void add_span_aa(int *list, int x0, int x1, int xofs)

{

	int x0pix, x0sub;

	int x1pix, x1sub;

	if (x0 == x1)

		return;

	/* x between 0 and width of bbox */

	x0 -= xofs;

	x1 -= xofs;

	x0pix = x0 / fz_aa_hscale;

	x0sub = x0 % fz_aa_hscale;

	x1pix = x1 / fz_aa_hscale;

	x1sub = x1 % fz_aa_hscale;

	if (x0pix == x1pix)

	{

		list[x0pix] += x1sub - x0sub;

		list[x0pix+1] += x0sub - x1sub;

	}

	else

	{

		list[x0pix] += fz_aa_hscale - x0sub;

		list[x0pix+1] += x0sub;

		list[x1pix] += x1sub - fz_aa_hscale;

		list[x1pix+1] += -x1sub;

	}

}

static inline void non_zero_winding_aa(fz_gel *gel, int *list, int xofs)

{

	int winding = 0;

	int x = 0;

	int i;

	for (i = 0; i < gel->alen; i++)

	{

		if (!winding && (winding + gel->active[i]->ydir))

			x = gel->active[i]->x;

		if (winding && !(winding + gel->active[i]->ydir))

			add_span_aa(list, x, gel->active[i]->x, xofs);

		winding += gel->active[i]->ydir;

	}

}

static inline void even_odd_aa(fz_gel *gel, int *list, int xofs)

{

	int even = 0;

	int x = 0;

	int i;

	for (i = 0; i < gel->alen; i++)

	{

		if (!even)

			x = gel->active[i]->x;

		else

			add_span_aa(list, x, gel->active[i]->x, xofs);

		even = !even;

	}

}

static inline void undelta_aa(unsigned char * restrict out, int * restrict in, int n)

{

	int d = 0;

	while (n--)

	{

		d += *in++;

		*out++ = AA_SCALE(d);

	}

}

static inline void blit_aa(fz_pixmap *dst, int x, int y,

	unsigned char *mp, int w, unsigned char *color)

{

	unsigned char *dp;

	dp = dst->samples + ( (y - dst->y) * dst->w + (x - dst->x) ) * dst->n;

	if (color)

		fz_paint_span_with_color(dp, mp, dst->n, w, color);

	else

		fz_paint_span(dp, mp, 1, w, 255);

}

static void

fz_scan_convert_aa(fz_gel *gel, int eofill, fz_bbox clip,

	fz_pixmap *dst, unsigned char *color)

{

	unsigned char *alphas;

	int *deltas;

	int y, e;

	int yd, yc;

	int xmin = fz_idiv(gel->bbox.x0, fz_aa_hscale);

	int xmax = fz_idiv(gel->bbox.x1, fz_aa_hscale) + 1;

	int xofs = xmin * fz_aa_hscale;

	int skipx = clip.x0 - xmin;

	int clipn = clip.x1 - clip.x0;

	if (gel->len == 0)

		return;

	assert(clip.x0 >= xmin);

	assert(clip.x1 <= xmax);

	alphas = fz_malloc(xmax - xmin + 1);

	deltas = fz_malloc((xmax - xmin + 1) * sizeof(int));

	memset(deltas, 0, (xmax - xmin + 1) * sizeof(int));

	e = 0;

	y = gel->edges[0].y;

	yc = fz_idiv(y, fz_aa_vscale);

	yd = yc;

	while (gel->alen > 0 || e < gel->len)

	{

		yc = fz_idiv(y, fz_aa_vscale);

		if (yc != yd)

		{

			if (yd >= clip.y0 && yd < clip.y1)

			{

				undelta_aa(alphas, deltas, skipx + clipn);

				blit_aa(dst, xmin + skipx, yd, alphas + skipx, clipn, color);

				memset(deltas, 0, (skipx + clipn) * sizeof(int));

			}

		}

		yd = yc;

		insert_active(gel, y, &e);

		if (yd >= clip.y0 && yd < clip.y1)

		{

			if (eofill)

				even_odd_aa(gel, deltas, xofs);

			else

				non_zero_winding_aa(gel, deltas, xofs);

		}

		advance_active(gel);

		if (gel->alen > 0)

			y ++;

		else if (e < gel->len)

			y = gel->edges[e].y;

	}

	if (yd >= clip.y0 && yd < clip.y1)

	{

		undelta_aa(alphas, deltas, skipx + clipn);

		blit_aa(dst, xmin + skipx, yd, alphas + skipx, clipn, color);

	}

	fz_free(deltas);

	fz_free(alphas);

}

/*

 * Sharp (not anti-aliased) scan conversion

 */

static inline void blit_sharp(int x0, int x1, int y,

	fz_bbox clip, fz_pixmap *dst, unsigned char *color)

{

	unsigned char *dp;

	x0 = CLAMP(x0, dst->x, dst->x + dst->w);

	x1 = CLAMP(x1, dst->x, dst->x + dst->w);

	if (x0 < x1)

	{

		dp = dst->samples + ( (y - dst->y) * dst->w + (x0 - dst->x) ) * dst->n;

		if (color)

			fz_paint_solid_color(dp, dst->n, x1 - x0, color);

		else

			fz_paint_solid_alpha(dp, x1 - x0, 255);

	}

}

static inline void non_zero_winding_sharp(fz_gel *gel, int y,

	fz_bbox clip, fz_pixmap *dst, unsigned char *color)

{

	int winding = 0;

	int x = 0;

	int i;

	for (i = 0; i < gel->alen; i++)

	{

		if (!winding && (winding + gel->active[i]->ydir))

			x = gel->active[i]->x;

		if (winding && !(winding + gel->active[i]->ydir))

			blit_sharp(x, gel->active[i]->x, y, clip, dst, color);

		winding += gel->active[i]->ydir;

	}

}

static inline void even_odd_sharp(fz_gel *gel, int y,

	fz_bbox clip, fz_pixmap *dst, unsigned char *color)

{

	int even = 0;

	int x = 0;

	int i;

	for (i = 0; i < gel->alen; i++)

	{

		if (!even)

			x = gel->active[i]->x;

		else

			blit_sharp(x, gel->active[i]->x, y, clip, dst, color);

		even = !even;

	}

}

static void

fz_scan_convert_sharp(fz_gel *gel, int eofill, fz_bbox clip,

	fz_pixmap *dst, unsigned char *color)

{

	int e = 0;

	int y = gel->edges[0].y;

	while (gel->alen > 0 || e < gel->len)

	{

		insert_active(gel, y, &e);

		if (y >= clip.y0 && y < clip.y1)

		{

			if (eofill)

				even_odd_sharp(gel, y, clip, dst, color);

			else

				non_zero_winding_sharp(gel, y, clip, dst, color);

		}

		advance_active(gel);

		if (gel->alen > 0)

			y ++;

		else if (e < gel->len)

			y = gel->edges[e].y;

	}

}

void

fz_scan_convert(fz_gel *gel, int eofill, fz_bbox clip,

	fz_pixmap *dst, unsigned char *color)

{

	if (fz_aa_level > 0)

		fz_scan_convert_aa(gel, eofill, clip, dst, color);

	else

		fz_scan_convert_sharp(gel, eofill, clip, dst, color);

}