path: root/nx-X11/extras/ttf2pt1/bitmap.c

/*
 * Handling of the bitmapped glyphs
 *
 * Copyright (c) 2001 by the TTF2PT1 project
 * Copyright (c) 2001 by Sergey Babkin
 *
 * see COPYRIGHT for the full copyright notice
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "pt1.h"
#include "global.h"

/* possible values of limits */
#define L_NONE	0 /* nothing here */
#define L_ON	1 /* black is on up/right */
#define L_OFF	2 /* black is on down/left */

static int warnedhints = 0;


#ifdef USE_AUTOTRACE
#include <autotrace/autotrace.h>

/*
 * Produce an autotraced outline from a bitmap.
 * scale - factor to scale the sizes
 * bmap - array of dots by lines, xsz * ysz
 * xoff, yoff - offset of the bitmap's lower left corner
 *              from the logical position (0,0)
 */

static void
autotraced_bmp_outline(
	GLYPH *g,
	int scale,
	char *bmap,
	int xsz,
	int ysz,
	int xoff,
	int yoff
)
{
	at_bitmap_type atb;
	at_splines_type *atsp;
	at_fitting_opts_type *atoptsp;
	at_spline_list_type *slp;
	at_spline_type *sp;
	int i, j, k;
	double lastx, lasty;
	double fscale;
	char *xbmap;

	fscale = (double)scale;

	/* provide a white margin around the bitmap */
	xbmap = malloc((ysz+2)*(xsz+2));
	if(xbmap == 0)  {
		fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
		exit(255);
	}
	memset(xbmap, 0, xsz+2);  /* top margin */
	for(i=0, j=xsz+2; i<ysz; i++, j+=xsz+2) {
		xbmap[j] = 0; /* left margin */
		memcpy(&xbmap[j+1], &bmap[xsz*(ysz-1-i)], xsz); /* a line of bitmap */
		xbmap[j+xsz+1] = 0; /* right margin */
	}
	memset(xbmap+j, 0, xsz+2);  /* bottom margin */
	xoff--; yoff-=2; /* compensate for the margins */

	atoptsp = at_fitting_opts_new();

	atb.width = xsz+2;
	atb.height = ysz+2;
	atb.np = 1;
	atb.bitmap = xbmap;

	atsp = at_splines_new(&atb, atoptsp);

	lastx = lasty = -1.;
	for(i=0; i<atsp->length; i++) {
		slp = &atsp->data[i];
#if 0
		fprintf(stderr, "%s: contour %d: %d entries clockwise=%d color=%02X%02X%02X\n",
			g->name, i, slp->length, slp->clockwise, slp->color.r, slp->color.g, slp->color.b);
#endif
		if(slp->length == 0)
			continue;
#if 0
		if(slp->color.r + slp->color.g + slp->color.b == 0)
			continue;
#endif
		fg_rmoveto(g, fscale*(slp->data[0].v[0].x+xoff), fscale*(slp->data[0].v[0].y+yoff));
		for(j=0; j<slp->length; j++) {
#if 0
			fprintf(stderr, "  ");
			for(k=0; k<4; k++)
				fprintf(stderr, "(%g %g) ", 
					fscale*(slp->data[j].v[k].x+xoff), 
					fscale*(ysz-slp->data[j].v[k].y+yoff)
					);
			fprintf(stderr, "\n");
#endif
			fg_rrcurveto(g,
				fscale*(slp->data[j].v[1].x+xoff), fscale*(slp->data[j].v[1].y+yoff),
				fscale*(slp->data[j].v[2].x+xoff), fscale*(slp->data[j].v[2].y+yoff),
				fscale*(slp->data[j].v[3].x+xoff), fscale*(slp->data[j].v[3].y+yoff) );
		}
		g_closepath(g);
	}

	at_splines_free(atsp);
	at_fitting_opts_free(atoptsp);
	free(xbmap);
}

#endif /*USE_AUTOTRACE*/

/* an extension of gentry for description of the fragments */
typedef struct gex_frag GEX_FRAG;
struct gex_frag {
	/* indexes to len, the exact values and order are important */
#define GEXFI_NONE	-1
#define GEXFI_CONVEX	0
#define GEXFI_CONCAVE	1
#define GEXFI_LINE	2 /* a line with steps varying by +-1 pixel */
#define GEXFI_EXACTLINE	3 /* a line with exactly the same steps */
#define GEXFI_SERIF	4 /* small serifs at the ends of stemsi - must be last */
#define GEXFI_COUNT	5 /* maximal index + 1 */
	unsigned short len[GEXFI_COUNT]; /* length of various fragment types starting here */
	unsigned short lenback[GEXFI_COUNT]; /* length back to the start of curve */

	signed char ixstart; /* index of the frag type that starts here */
	signed char ixcont; /* index of the frag type that continues here */

	short flags;
#define GEXFF_HLINE	0x0001 /* the exact line is longer in "horizontal" dimension */
#define GEXFF_EXTR	0x0002 /* this gentry is an extremum in some direction */
#define GEXFF_CIRC	0x0004 /* the joint at this gentry is for a circular curve */
#define GEXFF_DRAWCURVE	0x0008 /* vect[] describes a curve to draw */
#define GEXFF_DRAWLINE	0x0010 /* vect[] describes a line to draw */
#define GEXFF_SPLIT	0x0020 /* is a result of splitting a line */
#define GEXFF_SYMNEXT	0x0040 /* this subfrag is symmetric with next one */
#define GEXFF_DONE	0x0080 /* this subfrag has been vectorized */
#define GEXFF_LONG	0x0100 /* this gentry is longer than 1 pixel */

	unsigned short aidx; /* index of gentry in the array representing the contour */
	
	unsigned short vectlen; /* number of gentries represented by vect[] */

	/* coordinates for vectored replacement of this fragment */
	/* (already scaled because it's needed for curve approximation) */
	double vect[4 /*ref.points*/][2 /*X,Y*/];

	double bbox[2 /*X,Y*/]; /* absolute sizes of bounding box of a subfragment */

	/* used when splitting the curved frags into subfrags */
	GENTRY *prevsub;  /* to gentries describing neighboring subfrags */
	GENTRY *nextsub;
	GENTRY *ordersub; /* single-linked list describing the order of calculation */

	int sublen; /* length of this subfrag */
	/* the symmetry across the subfrags */
	int symaxis; /* the symmetry axis, with next subfrag */
	int symxlen; /* min length of adjacent symmetric frags */
	/* the symmetry within this subfrag (the axis is always diagonal) */
	GENTRY *symge; /* symge->i{x,y}3 is the symmetry point of symge==0 if none */

};
#define	X_FRAG(ge)	((GEX_FRAG *)((ge)->ext))

/* various interesting tables related to GEX_FRAG */
static char *gxf_name[GEXFI_COUNT] = {"Convex", "Concave", "Line", "ExLine", "Serif"};
static int gxf_cvk[2] = {-1, 1}; /* coefficients of concaveness */

/*
 * Dump the contents of X_EXT()->len and ->lenback for a contour
 */
static void
gex_dump_contour(
	GENTRY *ge,
	int clen
)
{
	int i, j;

	for(j = 0; j < GEXFI_COUNT; j++) {
		fprintf(stderr, "%-8s", gxf_name[j]);
		for(i = 0; i < clen; i++, ge = ge->frwd)
			fprintf(stderr, " %2d", X_FRAG(ge)->len[j]);
		fprintf(stderr, " %p\n (back) ", ge);
		for(i = 0; i < clen; i++, ge = ge->frwd)
			fprintf(stderr, " %2d", X_FRAG(ge)->lenback[j]);
		fprintf(stderr, "\n");
	}
}

/*
 * Calculate values of X_EXT()->lenback[] for all entries in
 * a contour. The contour is identified by:
 *  ge - any gentry of the contour
 *  clen - contour length
 */

static void
gex_calc_lenback(
	GENTRY *ge,
	int clen
)
{
	int i, j;
	int end;
	GEX_FRAG *f;
	int len[GEXFI_COUNT]; /* length of the most recent fragment */
	int count[GEXFI_COUNT]; /* steps since beginning of the fragment */

	for(j = 0; j < GEXFI_COUNT; j++)
		len[j] = count[j] = 0;

	end = clen;
	for(i = 0; i < end; i++, ge = ge->frwd) {
		f = X_FRAG(ge);
		for(j = 0; j < GEXFI_COUNT; j++) {
			if(len[j] != count[j]) {
				f->lenback[j] = count[j]++;
			} else
				f->lenback[j] = 0;
			if(f->len[j] != 0) {
				len[j] = f->len[j];
				count[j] = 1; /* start with the next gentry */
				/* if the fragment will wrap over the start, process to its end */
				if(i < clen && i + len[j] > end) 
					end = i + len[j];
			}
		}
	}
	gex_dump_contour(ge, clen);
}

/* Limit a curve to not exceed the given coordinates
 * at its given side
 */

static void
limcurve(
	double curve[4][2 /*X,Y*/],
	double lim[2 /*X,Y*/],
	int where /* 0 - start, 3 - end */
)
{
	int other = 3-where; /* the other end */
	int sgn[2 /*X,Y*/]; /* sign for comparison */
	double t, from, to, nt, t2, nt2, tt[4];
	double val[2 /*X,Y*/];
	int i;

	for(i=0; i<2; i++)
		sgn[i] = fsign(curve[other][i] - curve[where][i]);

#if 0
	fprintf(stderr, "     limit (%g,%g)-(%g,%g) at %d by (%g,%g), sgn(%d,%d)\n",
		curve[0][0], curve[0][1], curve[3][0], curve[3][1],
		where, lim[0], lim[1], sgn[0], sgn[1]);
#endif
	/* a common special case */
	if( sgn[0]*(curve[where][0] - lim[0]) >= 0.
	&& sgn[1]*(curve[where][1] - lim[1]) >= 0. )
		return; /* nothing to do */

	if(other==0) {
		from = 0.;
		to = 1.;
	} else {
		from = 1.;
		to = 0.;
	}
#if 0
	fprintf(stderr, "t=");
#endif
	while( fabs(from-to) > 0.00001 ) {
		t = 0.5 * (from+to);
		t2 = t*t;
		nt = 1.-t;
		nt2 = nt*nt;
		tt[0] = nt2*nt;
		tt[1] = 3*nt2*t;
		tt[2] = 3*nt*t2;
		tt[3] = t*t2;
		for(i=0; i<2; i++)
			val[i] = curve[0][i]*tt[0] + curve[1][i]*tt[1]
				+ curve[2][i]*tt[2] + curve[3][i]*tt[3];
#if 0
		fprintf(stderr, "%g(%g,%g) ", t, val[0], val[1]);
#endif
		if(fabs(val[0] - lim[0]) < 0.1
		|| fabs(val[1] - lim[1]) < 0.1)
			break;

		if(sgn[0] * (val[0] - lim[0]) < 0.
		|| sgn[1] * (val[1] - lim[1]) < 0.)
			to = t;
		else
			from = t;
	}
	/* now t is the point of splitting */
#define SPLIT(pt1, pt2)	( (pt1) + t*((pt2)-(pt1)) ) /* order is important! */
	for(i=0; i<2; i++) {
		double v11, v12, v13, v21, v22, v31; /* intermediate points */

		v11 = SPLIT(curve[0][i], curve[1][i]);
		v12 = SPLIT(curve[1][i], curve[2][i]);
		v13 = SPLIT(curve[2][i], curve[3][i]);
		v21 = SPLIT(v11, v12);
		v22 = SPLIT(v12, v13);
		v31 = SPLIT(v21, v22);
		if(other==0) {
			curve[1][i] = v11;
			curve[2][i] = v21;
			curve[3][i] = fabs(v31 - lim[i]) < 0.1 ? lim[i] : v31;
		} else {
			curve[0][i] = fabs(v31 - lim[i]) < 0.1 ? lim[i] : v31;
			curve[1][i] = v22;
			curve[2][i] = v13;
		}
	}
#undef SPLIT
#if 0
	fprintf(stderr, "\n");
#endif
}

/*
 * Vectorize a subfragment of a curve fragment. All the data has been already
 * collected by this time
 */

static void
dosubfrag(
	GLYPH *g,
	int fti, /* fragment type index */
	GENTRY *firstge, /* first gentry of fragment */
	GENTRY *ge, /* first gentry of subfragment */
	double fscale
) 
{
	GENTRY *gel, *gei; /* last gentry of this subfrag */
	GEX_FRAG *f, *ff, *lf, *pf, *xf;
	/* maximal amount of space that can be used at the beginning and the end */
	double fixfront[2], fixend[2]; /* fixed points - used to show direction */
	double mvfront[2], mvend[2]; /* movable points */
	double limfront[2], limend[2]; /* limit of movement for movabel points */
	double sympt;
	int outfront, outend; /* the beginning/end is going outwards */
	int symfront, symend; /* a ready symmetric fragment is present at front/end */
	int drnd[2 /*X,Y*/]; /* size of the round part */
	int i, j, a1, a2, ndots;
	double avg2, max2; /* squared distances */
	struct dot_dist *dots, *usedots;

	ff = X_FRAG(firstge);
	f = X_FRAG(ge);
	gel = f->nextsub;
	lf = X_FRAG(gel);
	if(f->prevsub != 0)
		pf = X_FRAG(f->prevsub);
	else
		pf = 0;

	for(i=0; i<2; i++)
		drnd[i] = gel->bkwd->ipoints[i][2] - ge->ipoints[i][2];

	if(f->prevsub==0 && f->ixcont == GEXFI_NONE) {
		/* nothing to join with : may use the whole length */
		for(i = 0; i < 2; i++)
			limfront[i] = ge->bkwd->ipoints[i][2];
	} else {
		/* limit to a half */
		for(i = 0; i < 2; i++)
			limfront[i] = 0.5 * (ge->ipoints[i][2] + ge->bkwd->ipoints[i][2]);
	}
	if( (ge->ix3 == ge->bkwd->ix3) /* vert */
	^ (isign(ge->bkwd->ix3 - ge->frwd->ix3)==isign(ge->bkwd->iy3 - ge->frwd->iy3))
	^ (fti == GEXFI_CONCAVE) /* counter-clockwise */ ) {
		/* the beginning is not a flat 90-degree end */
		outfront = 1;
		for(i = 0; i < 2; i++)
			fixfront[i] = ge->frwd->ipoints[i][2];
	} else {
		outfront = 0;
		for(i = 0; i < 2; i++)
			fixfront[i] = ge->ipoints[i][2];
	}

	if(lf->nextsub==0 && lf->ixstart == GEXFI_NONE) {
		/* nothing to join with : may use the whole length */
		for(i = 0; i < 2; i++)
			limend[i] = gel->ipoints[i][2];
	} else {
		/* limit to a half */
		for(i = 0; i < 2; i++)
			limend[i] = 0.5 * (gel->ipoints[i][2] + gel->bkwd->ipoints[i][2]);
	}
	gei = gel->bkwd->bkwd;
	if( (gel->ix3 == gel->bkwd->ix3) /* vert */
	^ (isign(gel->ix3 - gei->ix3)==isign(gel->iy3 - gei->iy3))
	^ (fti == GEXFI_CONVEX) /* clockwise */ ) {
		/* the end is not a flat 90-degree end */
		outend = 1;
		for(i = 0; i < 2; i++)
			fixend[i] = gel->bkwd->bkwd->ipoints[i][2];
	} else {
		outend = 0;
		for(i = 0; i < 2; i++)
			fixend[i] = gel->bkwd->ipoints[i][2];
	}

	for(i = 0; i < 2; i++) {
		fixfront[i] *= fscale;
		limfront[i] *= fscale;
		fixend[i] *= fscale;
		limend[i] *= fscale;
	}

	fprintf(stderr, "    %d out(%d[%d %d %d],%d[%d %d %d]) drnd(%d, %d)\n", 
		fti,
		outfront, 
			(ge->ix3 == ge->bkwd->ix3),
			(isign(ge->bkwd->ix3 - ge->frwd->ix3)==isign(ge->bkwd->iy3 - ge->frwd->iy3)),
			(fti == GEXFI_CONCAVE),
		outend,
			(gel->ix3 == gel->bkwd->ix3),
			(isign(gel->ix3 - gei->ix3)==isign(gel->iy3 - gei->iy3)),
			(fti == GEXFI_CONVEX),
		drnd[0], drnd[1]);

	/* prepare to calculate the distances */
	ndots = f->sublen - 1;
	dots = malloc(sizeof(*dots) * ndots);
	if(dots == 0) {
		fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
		exit(255);
	}
	for(i = 0, gei = ge; i < ndots; i++, gei = gei->frwd) {
		for(a1 = 0; a1 < 2; a1++)
			dots[i].p[a1] = fscale * gei->ipoints[a1][2];
	}

	/* see if we can mirror a ready symmetric curve */

	/* check symmetry with the fragment before this */
	symfront = (pf != 0 && (pf->flags & GEXFF_SYMNEXT) && (pf->flags & GEXFF_DONE)
		&& ( outend && f->sublen <= pf->sublen
			|| ( pf->sublen == f->sublen 
				&& (lf->sublen == 0
					|| ( abs(limfront[0]-limend[0]) >= abs(pf->vect[0][0]-pf->vect[3][0])
						&& abs(limfront[1]-limend[1]) >= abs(pf->vect[0][1]-pf->vect[3][1]) ))
			)
		)
	);
	/* check symmetry with the fragment after this */
	symend = ( (f->flags & GEXFF_SYMNEXT) && (lf->flags & GEXFF_DONE)
		&& ( outfront && f->sublen <= lf->sublen
			|| ( lf->sublen == f->sublen 
				&& (pf == 0 
					|| ( abs(limfront[0]-limend[0]) >= abs(lf->vect[0][0]-lf->vect[3][0])
						&& abs(limfront[1]-limend[1]) >= abs(lf->vect[0][1]-lf->vect[3][1]) )) 
			)
		)
	);
	if(symfront || symend) {
		/* mirror the symmetric neighbour subfrag */
		if(symfront) {
			a1 = (ge->ix3 != ge->bkwd->ix3); /* the symmetry axis */
			a2 = !a1; /* the other axis (goes along the extremum gentry) */

			/* the symmetry point on a2 */
			sympt = fscale * 0.5 * (ge->ipoints[a2][2] + ge->bkwd->ipoints[a2][2]);
			xf = pf; /* the symmetric fragment */
		} else {
			a1 = (gel->ix3 != gel->bkwd->ix3); /* the symmetry axis */
			a2 = !a1; /* the other axis (goes along the extremum gentry) */

			/* the symmetry point on a2 */
			sympt = fscale * 0.5 * (gel->ipoints[a2][2] + gel->bkwd->ipoints[a2][2]);
			xf = lf; /* the symmetric fragment */
		}
		fprintf(stderr, "     sym with %p f=%d(%p) e=%d(%p) a1=%c a2=%c sympt=%g\n",
			xf, symfront, pf, symend, lf,
			a1 ? 'Y': 'X', a2 ? 'Y': 'X', sympt
		);
		for(i=0; i<4; i++) {
			f->vect[3-i][a1] = xf->vect[i][a1];
			f->vect[3-i][a2] = sympt - (xf->vect[i][a2]-sympt);
		}
		if(symfront) {
			if(outend || lf->sublen==0)
				limcurve(f->vect, limend, 3);
		} else {
			if(outfront || pf == 0)
				limcurve(f->vect, limfront, 0);
		}
		avg2 = fdotcurvdist2(f->vect, dots, ndots, &max2);
		fprintf(stderr, "     avg=%g max=%g fscale=%g\n", sqrt(avg2), sqrt(max2), fscale);
		if(max2 <= fscale*fscale) {
			f->flags |= (GEXFF_DONE | GEXFF_DRAWCURVE);
			f->vectlen = f->sublen;
			free(dots);
			return;
		}
	}

	if( !outfront && !outend && f->symge != 0) {
		/* a special case: try a circle segment as an approximation */
		double lenfront, lenend, len, maxlen;

		/* coefficient for a Bezier approximation of a circle */
#define CIRCLE_FRAC	0.55

		a1 = (ge->ix3 == ge->bkwd->ix3); /* get the axis along the front */
		a2 = !a1; /* axis along the end */

		lenfront = fixfront[a1] - limfront[a1];
		lenend = fixend[a2] - limend[a2];
		if(fabs(lenfront) < fabs(lenend))
			len = fabs(lenfront);
		else
			len = fabs(lenend);

		/* make it go close to the round shape */
		switch(f->sublen) {
		case 2:
			maxlen = fscale;
			break;
		case 4:
		case 6:
			maxlen = fscale * 2.;
			break;
		default:
			maxlen = fscale * abs(ge->frwd->frwd->ipoints[a1][2] 
				- ge->ipoints[a1][2]);
			break;
		}
		if(len > maxlen)
			len = maxlen;

		mvfront[a1] = fixfront[a1] - fsign(lenfront) * len;
		mvfront[a2] = limfront[a2];
		mvend[a2] = fixend[a2] - fsign(lenend) * len;
		mvend[a1] = limend[a1];

		for(i=0; i<2; i++) {
			f->vect[0][i] = mvfront[i];
			f->vect[3][i] = mvend[i];
		}
		f->vect[1][a1] = mvfront[a1] + CIRCLE_FRAC*(mvend[a1]-mvfront[a1]);
		f->vect[1][a2] = mvfront[a2];
		f->vect[2][a1] = mvend[a1];
		f->vect[2][a2] = mvend[a2] + CIRCLE_FRAC*(mvfront[a2]-mvend[a2]);

		avg2 = fdotcurvdist2(f->vect, dots, ndots, &max2);
		fprintf(stderr, "     avg=%g max=%g fscale=%g\n", sqrt(avg2), sqrt(max2), fscale);
		if(max2 <= fscale*fscale) {
			f->flags |= (GEXFF_DONE | GEXFF_DRAWCURVE);
			f->vectlen = f->sublen;
			free(dots);
			return;
		}
#undef CIRCLE_FRAC
	}
	for(i=0; i<2; i++) {
		f->vect[0][i] = limfront[i];
		f->vect[1][i] = fixfront[i];
		f->vect[2][i] = fixend[i];
		f->vect[3][i] = limend[i];
	}
	usedots = dots;
	if(outfront) {
		usedots++; ndots--;
	}
	if(outend)
		ndots--;
	if( fcrossrayscv(f->vect, NULL, NULL) == 0) {
		fprintf(stderr, "**** Internal error: rays must cross but don't at %p-%p\n",
			ge, gel);
		fprintf(stderr, "  (%g, %g) (%g, %g) (%g, %g) (%g, %g)\n", 
			limfront[0], limfront[1],
			fixfront[0], fixfront[1],
			fixend[0], fixend[1],
			limend[0], limend[1]
		);
		dumppaths(g, NULL, NULL);
		exit(1);
	} else {
		if(ndots != 0)
			fapproxcurve(f->vect, usedots, ndots);
		f->flags |= (GEXFF_DONE | GEXFF_DRAWCURVE);
		f->vectlen = f->sublen;
	}
	free(dots);
}

/*
 * Subtract a list of gentries (covered by a fragment of higher
 * priority) from the set of fragments of a given
 * type.
 *
 * An example is subtraction of the long exact line fragments
 * from the curve fragments which get overridden.
 */

static void
frag_subtract(
	GLYPH *g,
	GENTRY **age, /* array of gentries for this contour */
	int clen, /* length of the contour */
	GENTRY *ge, /* first gentry to be subtracted */
	int slen, /* number of gentries in the list to be subtracted */
	int d /* type of fragments from which to subtract, as in GEXFI_... */
)
{
	GENTRY *pge;
	GEX_FRAG *f, *pf;
	int len, i, j;

	f = X_FRAG(ge);
	len = slen; 

	/* check if we overlap the end of some fragment */
	if(f->lenback[d]) {
		/* chop off the end of conflicting fragment */
		len = f->lenback[d];
		pge = age[(f->aidx + clen - len)%clen];
		pf = X_FRAG(pge);
		if(pf->len[d] == clen+1 && pf->flags & GEXFF_CIRC) {
			/* the conflicting fragment is self-connected */

			pf->len[d] = 0;
			/* calculate the new value for lenback */
			len = clen+1 - slen;
			for(pge = ge; len > 0; pge = pge->bkwd, len--)
				X_FRAG(pge)->lenback[d] = len;
			/* now pge points to the last entry of the line,
			 * which is also the new first entry of the curve
			 */
			X_FRAG(pge)->len[d] = clen+2 - slen;
			/* clean lenback of gentries covered by the line */
			for(pge = ge->frwd, j = slen-1; j > 0; pge = pge->frwd, j--)
				X_FRAG(pge)->lenback[d] = 0;
			fprintf(stderr, "    cut %s circular frag to %p-%p\n", 
				gxf_name[d], pge, ge);
			gex_dump_contour(ge, clen);
		} else {
			/* when we chop off a piece of fragment, we leave the remaining
			 * piece(s) overlapping with the beginning and possibly the end 
			 * of the line fragment under consideration
			 */
			fprintf(stderr, "    cut %s frag at %p from len=%d to len=%d (end %p)\n", 
				gxf_name[d], pge, pf->len[d], len+1, ge);
			j = pf->len[d] - len - 1; /* how many gentries are chopped off */
			pf->len[d] = len + 1;
			i = slen - 1;
			for(pge = ge->frwd; j > 0 && i > 0; j--, i--, pge = pge->frwd)
				X_FRAG(pge)->lenback[d] = 0;
			gex_dump_contour(ge, clen);

			if(j != 0) {
				/* the conflicting fragment is split in two by this line
				 * fragment, fix up its tail
				 */

				fprintf(stderr, "    end of %s frag len=%d %p-", 
					gxf_name[d], j+1, pge->bkwd);
				X_FRAG(pge->bkwd)->len[d] = j+1; /* the overlapping */
				for(i = 1; j > 0; j--, i++, pge = pge->frwd)
					X_FRAG(pge)->lenback[d] = i;
				fprintf(stderr, "%p\n", pge->bkwd);
				gex_dump_contour(ge, clen);
			}
		}
	}
	/* check if we overlap the beginning of some fragments */
	i = slen-1; /* getntries remaining to consider */
	j = 0; /* gentries remaining in the overlapping fragment */
	for(pge = ge; i > 0; i--, pge = pge->frwd) {
		if(j > 0) {
			X_FRAG(pge)->lenback[d] = 0;
			j--;
		} 
		/* the beginning of one fragment may be the end of another
		 * fragment, in this case if j-- above results in 0, that will 
		 * cause it to check the same gentry for the beginning
		 */
		if(j == 0) {
			pf = X_FRAG(pge);
			j = pf->len[d]; 
			if(j != 0) {
				fprintf(stderr, "    removed %s frag at %p len=%d\n", 
					gxf_name[d], pge, j);
				gex_dump_contour(ge, clen);
				pf->len[d] = 0;
				j--;
			}
		}
	}
	/* pge points at the last gentry of the line fragment */
	if(j > 1) { /* we have the tail of a fragment left */
		fprintf(stderr, "    end of %s frag len=%d %p-", 
			gxf_name[d], j, pge);
		X_FRAG(pge)->len[d] = j; /* the overlapping */
		for(i = 0; j > 0; j--, i++, pge = pge->frwd)
			X_FRAG(pge)->lenback[d] = i;
		fprintf(stderr, "%p\n", pge->bkwd);
		gex_dump_contour(ge, clen);
	} else if(j == 1) {
		X_FRAG(pge)->lenback[d] = 0;
	}
}

/*
 * Produce an outline from a bitmap.
 * scale - factor to scale the sizes
 * bmap - array of dots by lines, xsz * ysz
 * xoff, yoff - offset of the bitmap's lower left corner
 *              from the logical position (0,0)
 */

void
bmp_outline(
	GLYPH *g,
	int scale,
	char *bmap,
	int xsz,
	int ysz,
	int xoff,
	int yoff
)
{
	char *hlm, *vlm; /* arrays of the limits of outlines */
	char *amp; /* map of ambiguous points */
	int x, y;
	char *ip, *op;
	double fscale;

	if(xsz==0 || ysz==0)
		return;

#ifdef USE_AUTOTRACE
	if(use_autotrace) {
		autotraced_bmp_outline(g, scale, bmap, xsz, ysz, xoff, yoff);
		return;
	}
#endif /*USE_AUTOTRACE*/

	fscale = (double)scale;
	g->flags &= ~GF_FLOAT; /* build it as int first */

	if(!warnedhints) {
		warnedhints = 1;
		if(hints && subhints) {
			WARNING_2 fprintf(stderr, 
				"Use of hint substitution on bitmap fonts is not recommended\n");
		}
	}

#if 0
	printbmap(bmap, xsz, ysz, xoff, yoff);
#endif

	/* now find the outlines */
	hlm=calloc( xsz, ysz+1 ); /* horizontal limits */
	vlm=calloc( xsz+1, ysz ); /* vertical limits */
	amp=calloc( xsz, ysz ); /* ambiguous points */

	if(hlm==0 || vlm==0 || amp==0)  {
		fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
		exit(255);
	}

	/*
	 * hlm and vlm represent a grid of horisontal and
	 * vertical lines. Each pixel is surrounded by the grid
	 * from all the sides. The values of [hv]lm mark the
	 * parts of grid where the pixel value switches from white
	 * to black and back.
	 */

	/* find the horizontal limits */
	ip=bmap; op=hlm;
	/* 1st row */
	for(x=0; x<xsz; x++) {
		if(ip[x])
			op[x]=L_ON;
	}
	ip+=xsz; op+=xsz;
	/* internal rows */
	for(y=1; y<ysz; y++) {
		for(x=0; x<xsz; x++) {
			if(ip[x]) {
				if(!ip[x-xsz])
					op[x]=L_ON;
			} else {
				if(ip[x-xsz])
					op[x]=L_OFF;
			}
		}
		ip+=xsz; op+=xsz;
	}

	/* last row */
	ip-=xsz;
	for(x=0; x<xsz; x++) {
		if(ip[x])
			op[x]=L_OFF;
	}

	/* find the vertical limits */
	ip=bmap; op=vlm;
	for(y=0; y<ysz; y++) {
		if(ip[0])
			op[0]=L_ON;
		for(x=1; x<xsz; x++) {
			if(ip[x]) {
				if(!ip[x-1])
					op[x]=L_ON;
			} else {
				if(ip[x-1])
					op[x]=L_OFF;
			}
		}
		if(ip[xsz-1])
			op[xsz]=L_OFF;
		ip+=xsz; op+=xsz+1; 
	}

	/*
	 * Ambiguous points are the nodes of the grids
	 * that are between two white and two black pixels
	 * located in a checkerboard style. Actually
	 * there are only two patterns that may be
	 * around an ambiguous point:
	 *
	 *    X|.    .|X
	 *    -*-    -*-
	 *    .|X    X|.
	 *
	 * where "|" and "-" represent the grid (respectively members
	 * of vlm and hlm), "*" represents an ambiguous point
	 * and "X" and "." represent black and white pixels.
	 *
	 * If these sample pattern occur in the lower left corner
	 * of the bitmap then this ambiguous point will be
	 * located at amp[1][1] or in other words amp[1*xsz+1].
	 *
	 * These points are named "ambiguous" because it's
	 * not easy to guess what did the font creator mean
	 * at these points. So we are going to treat them 
	 * specially, doing no aggressive smoothing.
	 */

	/* find the ambiguous points */
	for(y=ysz-1; y>0; y--)
		for(x=xsz-1; x>0; x--) {
			if(bmap[y*xsz+x]) {
				if( !bmap[y*xsz+x-1] && !bmap[y*xsz-xsz+x] && bmap[y*xsz-xsz+x-1] )
					amp[y*xsz+x]=1;
			} else {
				if( bmap[y*xsz+x-1] && bmap[y*xsz-xsz+x] && !bmap[y*xsz-xsz+x-1] )
					amp[y*xsz+x]=1;
			}
		}

#if 0
	printlimits(hlm, vlm, amp, xsz, ysz);
#endif

	/* generate the vectored (stepping) outline */

	while(1) {
		int found = 0;
		int outer; /* flag: this is an outer contour */
		int hor, newhor; /* flag: the current contour direction is horizontal */
		int dir; /* previous direction of the coordinate, 1 - L_ON, 0 - L_OFF */
		int startx, starty; /* start of a contour */
		int firstx, firsty; /* start of the current line */
		int newx, newy; /* new coordinates to try */
		char *lm, val;
		int maxx, maxy, xor;

		for(y=ysz; !found &&  y>0; y--) 
			for(x=0; x<xsz; x++) 
				if(hlm[y*xsz+x] > L_NONE) 
					goto foundcontour;
		break; /* have no contours left */

	foundcontour:
		ig_rmoveto(g, x+xoff, y+yoff); /* intermediate as int */

		startx = firstx = x;
		starty = firsty = y;

		if(hlm[y*xsz+x] == L_OFF) {
			outer = 1; dir = 0;
			hlm[y*xsz+x] = -hlm[y*xsz+x]; /* mark as seen */
			hor = 1; x++;
		} else {
			outer = 0; dir = 0;
			hor = 0; y--;
			vlm[y*(xsz+1)+x] = -vlm[y*(xsz+1)+x]; /* mark as seen */
		}

		while(x!=startx || y!=starty) {
#if 0
			printf("trace (%d, %d) outer=%d hor=%d dir=%d\n", x, y, outer, hor, dir);
#endif

			/* initialization common for try1 and try2 */
			if(hor) {
				lm = vlm; maxx = xsz+1; maxy = ysz; newhor = 0;
			} else {
				lm = hlm; maxx = xsz; maxy = ysz+1; newhor = 1;
			}
			xor = (outer ^ hor ^ dir);

		try1:
			/* first we try to change axis, to keep the
			 * contour as long as possible
			 */

			newx = x; newy = y;
			if(!hor && (!outer ^ dir))
				newx--;
			if(hor && (!outer ^ dir))
				newy--;

			if(newx < 0 || newx >= maxx || newy < 0 || newy >= maxy)
				goto try2;

			if(!xor)
				val = L_ON;
			else
				val = L_OFF;
#if 0
			printf("try 1, want %d have %d at %c(%d, %d)\n", val, lm[newy*maxx + newx],
				(newhor ? 'h':'v'), newx, newy);
#endif
			if( lm[newy*maxx + newx] == val )
				goto gotit;

		try2:
			/* try to change the axis anyway */

			newx = x; newy = y;
			if(!hor && (outer ^ dir))
				newx--;
			if(hor && (outer ^ dir))
				newy--;

			if(newx < 0 || newx >= maxx || newy < 0 || newy >= maxy)
				goto try3;

			if(xor)
				val = L_ON;
			else
				val = L_OFF;
#if 0
			printf("try 2, want %d have %d at %c(%d, %d)\n", val, lm[newy*maxx + newx],
				(newhor ? 'h':'v'), newx, newy);
#endif
			if( lm[newy*maxx + newx] == val )
				goto gotit;

		try3:
			/* try to continue in the old direction */

			if(hor) {
				lm = hlm; maxx = xsz; maxy = ysz+1;
			} else {
				lm = vlm; maxx = xsz+1; maxy = ysz;
			}
			newhor = hor;
			newx = x; newy = y;
			if(hor && dir)
				newx--;
			if(!hor && !dir)
				newy--;

			if(newx < 0 || newx >= maxx || newy < 0 || newy >= maxy)
				goto badtry;

			if(dir)
				val = L_ON;
			else
				val = L_OFF;
#if 0
			printf("try 3, want %d have %d at %c(%d, %d)\n", val, lm[newy*maxx + newx],
				(newhor ? 'h':'v'), newx, newy);
#endif
			if( lm[newy*maxx + newx] == val )
				goto gotit;

		badtry:
			fprintf(stderr, "**** Internal error in the contour detection code at (%d, %d)\n", x, y);
			fprintf(stderr, "glyph='%s' outer=%d hor=%d dir=%d\n", g->name, outer, hor, dir);
			fflush(stdout);
			exit(1);

		gotit:
			if(hor != newhor) { /* changed direction, end the previous line */
				ig_rlineto(g, x+xoff, y+yoff); /* intermediate as int */
				firstx = x; firsty = y;
			}
			lm[newy*maxx + newx] = -lm[newy*maxx + newx];
			hor = newhor;
			dir = (val == L_ON);
			if(newhor)
				x -= (dir<<1)-1;
			else
				y += (dir<<1)-1;
		}
#if 0
		printf("trace (%d, %d) outer=%d hor=%d dir=%d\n", x, y, outer, hor, dir);
#endif
		ig_rlineto(g, x+xoff, y+yoff); /* intermediate as int */
		g_closepath(g);
	}


	/* try to vectorize the curves and sloped lines in the bitmap */
	if(vectorize) { 
		GENTRY *ge, *pge, *cge, *loopge;
		int i;
		int skip;

		dumppaths(g, NULL, NULL);

		/* allocate the extensions */
		for(cge=g->entries; cge!=0; cge=cge->next) {
			cge->ext = calloc(1, sizeof(GEX_FRAG) );
			if(cge->ext == 0)  {
				fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
				exit(255);
			}
		}

		for(cge=g->entries; cge!=0; cge=cge->next) {
			if(cge->type != GE_MOVE)
				continue;

			/* we've found the beginning of a contour */
			{
				int d, vert, count, stepmore, delaystop;
				int vdir, hdir, fullvdir, fullhdir, len;
				int dx, dy, lastdx, lastdy; 
				int k1, k2, reversal, smooth, good;
				int line[2 /*H,V*/], maxlen[2 /*H,V*/], minlen[2 /*H,V*/];
				GENTRY **age; /* array of gentries in a contour */
				int clen; /* contour length, size of ths array */
				int i, j;
				GEX_FRAG *f;

				/* we know that all the contours start at the top-left corner,
				 * so at most it might be before/after the last element of
				 * the last/first fragment
				 */

				ge = cge->next;
				pge = ge->bkwd;
				if(ge->ix3 == pge->ix3) { /* a vertical line */
					/* we want to start always from a horizontal line because
					 * then we always start from top and that is quaranteed to be a 
					 * fragment boundary, so move the start point of the contour
					 */
					pge->prev->next = pge->next;
					pge->next->prev = pge->prev;
					cge->next = pge;
					pge->prev = cge;
					pge->next = ge;
					ge->prev = pge;
					ge = pge; pge = ge->bkwd;
					cge->ix3 = pge->ix3; cge->iy3 = pge->iy3;
				}

				/* fill the array of gentries */
				clen = 1;
				for(ge = cge->next->frwd; ge != cge->next; ge = ge->frwd)
					clen++;
				age = (GENTRY **)malloc(sizeof(*age) * clen);
				ge = cge->next;
				count = 0;
				do {
					age[count] = ge;
					X_FRAG(ge)->aidx = count++;

					/* and by the way find the extremums */
					for(i=0; i<2; i++) {
						if( isign(ge->frwd->ipoints[i][2] - ge->ipoints[i][2])
						* isign(ge->bkwd->bkwd->ipoints[i][2] - ge->bkwd->ipoints[i][2]) == 1) {
							X_FRAG(ge)->flags |= GEXFF_EXTR;
							fprintf(stderr, "  %s extremum at %p\n", (i?"vert":"hor"), ge);
						}
						if(abs(ge->ipoints[i][2] - ge->bkwd->ipoints[i][2]) > 1)
							X_FRAG(ge)->flags |= GEXFF_LONG;
					}

					ge = ge->frwd;
				} while(ge != cge->next);

				/* Find the serif fragments, looking as either of:
				 *           -+              |
				 *            |              |        
				 *          +-+            +-+        
				 *          |              |          
				 *          +--...         +--...
				 * with the thickness of serifs being 1 pixel. We make no
				 * difference between serifs on vertical and horizontal stems.
				 */

				ge = cge->next;
				do {
					GENTRY *nge;
					int pdx, pdy, ndx, ndy;

					/* two gentries of length 1 mean a potential serif */
					pge = ge->bkwd;
					nge = ge->frwd;

					dx = nge->ix3 - pge->ix3;
					dy = nge->iy3 - pge->iy3;

					if(abs(dx) != 1 || abs(dy) != 1) /* 2 small ones */
						continue;

					if( 
						(!(X_FRAG(ge)->flags & GEXFF_EXTR) 
							|| !(X_FRAG(ge->bkwd)->flags & GEXFF_EXTR))
						&& (!(X_FRAG(ge->frwd)->flags & GEXFF_EXTR) 
							|| !(X_FRAG(ge->frwd->frwd)->flags & GEXFF_EXTR))
					)
						continue; /* either side must be a couple of extremums */

					pdx = pge->ix3 - pge->bkwd->ix3;
					pdy = pge->iy3 - pge->bkwd->iy3;
					ndx = nge->frwd->ix3 - nge->ix3;
					ndy = nge->frwd->iy3 - nge->iy3;

					if(pdx*dx + pdy*dy > 0 && ndx*dx + ndy*dy > 0) 
						continue; /* definitely not a serif but a round corner */

					if(abs(pdx) + abs(pdy) == 1 || abs(ndx) + abs(ndy) == 1)
						continue;

					/* we've found a serif including this and next gentry */
					X_FRAG(ge)->len[GEXFI_SERIF] = 2;

				} while( (ge = ge->frwd) != cge->next );


				/* Find the convex and concave fragments, defined as:
				 * convex (clockwise): dy/dx <= dy0/dx0, 
				 *  or a reversal: dy/dx == - dy0/dx0 && abs(dxthis) == 1 && dy/dx > 0
				 * concave (counter-clockwise): dy/dx >= dy0/dx0, 
				 *  or a reversal: dy/dx == - dy0/dx0 && abs(dxthis) == 1 && dy/dx < 0
				 *
				 * Where dx and dy are measured between the end of this gentry
				 * and the start of the previous one (dx0 and dy0 are the same
				 * thing calculated for the previous gentry and its previous one),
				 * dxthis is between the end and begginning of this gentry.
				 *
				 * A reversal is a situation when the curve changes its direction
				 * along the x axis, so it passes through a momentary vertical
				 * direction.
				 */
				for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) {
					ge = cge->next;
					pge = ge->bkwd; /* the beginning of the fragment */
					count = 1;
					lastdx = pge->ix3 - pge->bkwd->bkwd->ix3;
					lastdy = pge->iy3 - pge->bkwd->bkwd->iy3;

#define CHKCURVCONN(ge, msg)	do { \
		dx = (ge)->ix3 - (ge)->bkwd->bkwd->ix3; \
		dy = (ge)->iy3 - (ge)->bkwd->bkwd->iy3; \
		if(0 && msg) { \
			fprintf(stderr, "  %p: dx=%d dy=%d dx0=%d dy0=%d ", \
				(ge), dx, dy, lastdx, lastdy); \
		} \
		k1 = X_FRAG(ge)->flags; \
		k2 = X_FRAG((ge)->bkwd)->flags; \
		if(0 && msg) { \
			fprintf(stderr, "fl=%c%c%c%c ", \
				(k1 & GEXFF_EXTR) ? 'X' : '-', \
				(k1 & GEXFF_LONG) ? 'L' : '-', \
				(k2 & GEXFF_EXTR) ? 'X' : '-', \
				(k2 & GEXFF_LONG) ? 'L' : '-' \
			); \
		} \
		if( (k1 & GEXFF_EXTR) && (k2 & GEXFF_LONG) \
		|| (k2 & GEXFF_EXTR) && (k1 & GEXFF_LONG) ) { \
			smooth = 0; \
			good = reversal = -1; /* for debugging */ \
		} else { \
			k1 = dy * lastdx; \
			k2 = lastdy * dx; \
			smooth = (abs(dx)==1 || abs(dy)==1); \
			good = (k1 - k2)*gxf_cvk[d] >= 0; \
			if(smooth && !good) { \
				reversal = (k1 == -k2 && abs((ge)->ix3 - (ge)->bkwd->ix3)==1  \
					&& dy*dx*gxf_cvk[d] < 0); \
			} else \
				reversal = 0; \
		} \
		if(0 && msg) { \
			fprintf(stderr, "k1=%d k2=%d pge=%p count=%d %s good=%d rev=%d\n", \
				k1, k2, pge, count, gxf_name[d], good, reversal); \
		} \
	} while(0)

					do {
						CHKCURVCONN(ge, 1);

						if(smooth && (good || reversal) )
							count++;
						else {
							/* can't continue */
#if 0
							if(count >= 4) { /* worth remembering */
								fprintf(stderr, " %s frag %p-%p count=%d\n", gxf_name[d], pge, ge->bkwd, count);
							}
#endif
							X_FRAG(pge)->len[d] = count;
							if(smooth) {
								pge = ge->bkwd;
								count = 2;
							} else {
								pge = ge;
								count = 1;
							}
						}
						lastdx = dx; lastdy = dy;
						ge = ge->frwd;
					} while(ge != cge->next);

					/* see if we can connect the last fragment to the first */
					CHKCURVCONN(ge, 1);

					if(smooth && (good || reversal) ) {
						/* -1 to avoid ge->bkwd being counted twice */
						if( X_FRAG(ge->bkwd)->len[d] >= 2 )
							count += X_FRAG(ge->bkwd)->len[d] - 1;
						else if(count == clen+1) {
							/* we are joining a circular (closed) curve, check whether it
							 * can be joined at any point or whether it has a discontinuity
							 * at the point where we join it now
							 */
							lastdx = dx; lastdy = dy;
							CHKCURVCONN(ge->frwd, 0);

							if(smooth && (good || reversal) ) {
								/* yes, the curve is truly a circular one and can be 
								 * joined at any point
								 */

#if 0
								fprintf(stderr, " found a circular joint point at %p\n", pge);
#endif
								/* make sure that in a circular fragment we start from an extremum */
								while( ! (X_FRAG(pge)->flags & GEXFF_EXTR) )
									pge = pge->frwd;
								X_FRAG(pge)->flags |= GEXFF_CIRC;
							}
						}
#if 0
						fprintf(stderr, " %s joined %p to %p count=%d bk_count=%d\n", gxf_name[d], pge, ge->bkwd, 
							count, X_FRAG(ge->bkwd)->len[d] );
#endif
						X_FRAG(ge->bkwd)->len[d] = 0;
					} 
					X_FRAG(pge)->len[d] = count;
#if 0
					if(count >= 4) { /* worth remembering */
						fprintf(stderr, " %s last frag %p-%p count=%d\n", gxf_name[d], pge, ge->bkwd, count);
					}
#endif
#undef CHKCURVCONN

					/* do postprocessing */
					ge = cge->next;
					do {
						f = X_FRAG(ge);
						len = f->len[d];
#if 0
						fprintf(stderr, "   %p %s len=%d clen=%d\n", ge, gxf_name[d], len, clen);
#endif
						if(len < 3) /* get rid of the fragments that are too short */
							f->len[d] = 0;
						else if(len == 3) {
							/*                                                    _
							 * drop the |_| - shaped fragments, leave alone the _|  - shaped
							 * (and even those only if not too short in pixels),
							 * those left alone are further filtered later
							 */
							k1 = (ge->ix3 == ge->bkwd->ix3); /* axis of the start */
							if(isign(ge->ipoints[k1][2] - ge->bkwd->ipoints[k1][2])
								!= isign(ge->frwd->ipoints[k1][2] - ge->frwd->frwd->ipoints[k1][2])
							&& abs(ge->frwd->frwd->ipoints[k1][2] - ge->bkwd->ipoints[k1][2]) > 2) {
#if 0
								fprintf(stderr, " %s frag %p count=%d good shape\n", 
									gxf_name[d], ge, count);
#endif
							} else
								f->len[d] = 0;
						} else if(len == clen+1)
							break;  /* a closed fragment, nothing else interesting */
						else { /* only for open fragments */
							GENTRY *gem, *gex, *gei, *ges;

							ges = ge; /* the start entry */
							gem = age[(f->aidx + f->len[d])%clen]; /* entry past the end of the fragment */

							gei = ge->frwd;
							if( (ge->ix3 == ge->bkwd->ix3) /* vert */
							^ (isign(ge->bkwd->ix3 - gei->ix3)==isign(ge->bkwd->iy3 - gei->iy3))
							^ !(d == GEXFI_CONVEX) /* counter-clockwise */ ) {

#if 0
								fprintf(stderr, " %p: %s potential spurious start\n", ge, gxf_name[d]);
#endif
								/* the beginning may be a spurious entry */

								gex = 0; /* the extremum closest to the beginning - to be found */
								for(gei = ge->frwd; gei != gem; gei = gei->frwd) {
									if(X_FRAG(gei)->flags & GEXFF_EXTR) {
										gex = gei;
										break;
									}
								}
								if(gex == 0)
									gex = gem->bkwd; 

								/* A special case: ignore the spurious ends on small curves that
								 * either enclose an 1-pixel-wide extremum or are 1-pixel deep.
								 * Any 5-or-less-pixel-long curve with extremum 2 steps away
								 * qualifies for that.
								 */

								if(len <= 5 && gex == ge->frwd->frwd) {
									good = 0;
#if 0
									fprintf(stderr, " E");
#endif
								} else {
									good = 1; /* assume that ge is not spurious */

									/* gei goes backwards, gex goes forwards from the extremum */
									gei = gex;
									/* i is the symmetry axis, j is the other axis (X=0 Y=1) */
									i = (gex->ix3 != gex->bkwd->ix3);
									j = !i;
									for( ; gei!=ge && gex!=gem; gei=gei->bkwd, gex=gex->frwd) {
										if( gei->bkwd->ipoints[i][2] != gex->ipoints[i][2]
										|| gei->bkwd->ipoints[j][2] - gei->ipoints[j][2]
											!= gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] 
										) {
											good = 0; /* no symmetry - must be spurious */
#if 0
											fprintf(stderr, " M(%p,%p)(%d %d,%d)(%d %d,%d)",
												gei, gex,
												i, gei->bkwd->ipoints[i][2], gex->ipoints[i][2],
												j, gei->bkwd->ipoints[j][2] - gei->ipoints[j][2],
												gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] );
#endif
											break;
										}
									}
									if(gex == gem) { /* oops, the other side is too short */
										good = 0;
#if 0
										fprintf(stderr, " X");
#endif
									}
									if(good && gei == ge) {
										if( isign(gei->bkwd->ipoints[j][2] - gei->ipoints[j][2])
										!= isign(gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]) ) {
											good = 0; /* oops, goes into another direction */
#if 0
											fprintf(stderr, " D");
#endif
										}
									}
								}
								if(!good) { /* it is spurious, drop it */
#if 0
									fprintf(stderr, " %p: %s spurious start\n", ge, gxf_name[d]);
#endif
									f->len[d] = 0;
									ges = ge->frwd;
									len--;
									X_FRAG(ges)->len[d] = len;
								}
							}

							gei = gem->bkwd->bkwd->bkwd;
							if( (gem->ix3 != gem->bkwd->ix3) /* gem->bkwd is vert */
							^ (isign(gem->bkwd->ix3 - gei->ix3)==isign(gem->bkwd->iy3 - gei->iy3))
							^ (d == GEXFI_CONVEX) /* clockwise */ ) {
								
#if 0
								fprintf(stderr, " %p: %s potential spurious end\n", gem->bkwd, gxf_name[d]);
#endif
								/* the end may be a spurious entry */

								gex = 0; /* the extremum closest to the end - to be found */
								for(gei = gem->bkwd->bkwd; gei != ges->bkwd; gei = gei->bkwd) {
									if(X_FRAG(gei)->flags & GEXFF_EXTR) {
										gex = gei;
										break;
									}
								}
								if(gex == 0)
									gex = ges; 

								good = 1; /* assume that gem->bkwd is not spurious */
								/* gei goes backwards, gex goes forwards from the extremum */
								gei = gex;
								/* i is the symmetry axis, j is the other axis (X=0 Y=1) */
								i = (gex->ix3 != gex->bkwd->ix3);
								j = !i;
								for( ; gei!=ges->bkwd && gex!=gem->bkwd; gei=gei->bkwd, gex=gex->frwd) {
									if( gei->bkwd->ipoints[i][2] != gex->ipoints[i][2]
									|| gei->bkwd->ipoints[j][2] - gei->ipoints[j][2]
										!= gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] 
									) {
										good = 0; /* no symmetry - must be spurious */
#if 0
										fprintf(stderr, " M(%p,%p)(%d %d,%d)(%d %d,%d)",
											gei, gex,
											i, gei->bkwd->ipoints[i][2], gex->ipoints[i][2],
											j, gei->bkwd->ipoints[j][2] - gei->ipoints[j][2],
											gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] );
#endif
										break;
									}
								}
								if(gei == ges->bkwd) { /* oops, the other side is too short */
									good = 0;
#if 0
									fprintf(stderr, " X");
#endif
								}
								if(good && gex == gem->bkwd) {
									if( isign(gei->bkwd->ipoints[j][2] - gei->ipoints[j][2])
									!= isign(gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]) ) {
										good = 0; /* oops, goes into another direction */
#if 0
										fprintf(stderr, " D");
#endif
									}
								}
								if(!good) { /* it is spurious, drop it */
#if 0
									fprintf(stderr, " %p: %s spurious end\n", gem->bkwd, gxf_name[d]);
#endif
									X_FRAG(ges)->len[d] = --len;
								}
							}
							if(len < 4) {
								X_FRAG(ges)->len[d] = 0;
#if 0
								fprintf(stderr, " %p: %s frag discarded, too small now\n", ge, gxf_name[d]);
#endif
							}
							if(ges != ge) {
								if(ges == cge->next)
									break; /* went around the loop */
								else {
									ge = ges->frwd; /* don't look at this fragment twice */
									continue;
								}
							}
						}

						ge = ge->frwd;
					} while(ge != cge->next);
				}

				/* Find the straight line fragments.
				 * Even though the lines are sloped, they are called
				 * "vertical" or "horizontal" according to their longer
				 * dimension. All the steps in the shother dimension must 
				 * be 1 pixel long, all the steps in the longer dimension
				 * must be within the difference of 1 pixel.
				 */
				for(d = GEXFI_LINE; d<= GEXFI_EXACTLINE; d++) {
					ge = cge->next;
					pge = ge->bkwd; /* the beginning of the fragment */
					count = 1;
					delaystop = 0;
					do {
						int h;

						stepmore = 0;
						hdir = isign(ge->ix3 - ge->bkwd->ix3);
						vdir = isign(ge->iy3 - ge->bkwd->iy3);
						vert = (hdir == 0);
						if(count==1) {
							/* at this point pge==ge->bkwd */
							/* account for the previous gentry, which was !vert */
							if(!vert) { /* prev was vertical */
								maxlen[0] = minlen[0] = 0;
								maxlen[1] = minlen[1] = abs(pge->iy3 - pge->bkwd->iy3);
								line[0] = (maxlen[1] == 1);
								line[1] = 1;
								fullhdir = hdir;
								fullvdir = isign(pge->iy3 - pge->bkwd->iy3);
							} else {
								maxlen[0] = minlen[0] = abs(pge->ix3 - pge->bkwd->ix3);
								maxlen[1] = minlen[1] = 0;
								line[0] = 1;
								line[1] = (maxlen[0] == 1);
								fullhdir = isign(pge->ix3 - pge->bkwd->ix3);
								fullvdir = vdir;
							}
						}
						h = line[0]; /* remember the prevalent direction */
#if 0
						fprintf(stderr, "  %p: v=%d(%d) h=%d(%d) vl(%d,%d,%d) hl=(%d,%d,%d) %s count=%d ",
							ge, vdir, fullvdir, hdir, fullhdir, 
							line[1], minlen[1], maxlen[1],
							line[0], minlen[0], maxlen[0],
							gxf_name[d], count);
#endif
						if(vert) {
							if(vdir != fullvdir)
								line[0] = line[1] = 0;
							len = abs(ge->iy3 - ge->bkwd->iy3);
						} else {
							if(hdir != fullhdir)
								line[0] = line[1] = 0;
							len = abs(ge->ix3 - ge->bkwd->ix3);
						}
#if 0
						fprintf(stderr, "len=%d\n", len);
#endif
						if(len != 1) /* this is not a continuation in the short dimension */
							line[!vert] = 0;

						/* can it be a continuation in the long dimension ? */
						if( line[vert] ) {
							if(maxlen[vert]==0)
								maxlen[vert] = minlen[vert] = len;
							else if(maxlen[vert]==minlen[vert]) {
								if(d == GEXFI_EXACTLINE) {
									if(len != maxlen[vert])
										line[vert] = 0; /* it can't */
								} else if(len < maxlen[vert]) {
									if(len < minlen[vert]-1)
										line[vert] = 0; /* it can't */
									else
										minlen[vert] = len;
								} else {
									if(len > maxlen[vert]+1)
										line[vert] = 0; /* it can't */
									else
										maxlen[vert] = len;
								}
							} else if(len < minlen[vert] || len > maxlen[vert])
								line[vert] = 0; /* it can't */
						}

						if(line[0] == 0 && line[1] == 0) {
#if 0
							if(count >= 3)
								fprintf(stderr, " %s frag %p-%p count=%d\n", gxf_name[d], pge, ge->bkwd, count);
#endif
							X_FRAG(pge)->len[d] = count;
							if(d == GEXFI_EXACTLINE && h) {
								X_FRAG(pge)->flags |= GEXFF_HLINE;
							}
							if(count == 1)
								pge = ge;
							else {
								stepmore = 1; /* may reconsider the 1st gentry */
								pge = ge = ge->bkwd;
								count = 1;
							}
						} else
							count++;

						ge = ge->frwd;
						if(ge == cge->next && !stepmore)
							delaystop = 1; /* consider the first gentry again */
					} while(stepmore || ge != cge->next ^ delaystop);
					/* see if there is an unfinished line left */
					if(count != 1) {
#if 0
						if(count >= 3)
							fprintf(stderr, " %s frag %p-%p count=%d\n", gxf_name[d], pge, ge->bkwd, count);
#endif
						X_FRAG(ge->bkwd->bkwd)->len[d] = 0;
						X_FRAG(pge)->len[d] = count;
					}
				}

				/* do postprocessing of the lines */
#if 0
				fprintf(stderr, "Line postprocessing\n");
				gex_dump_contour(cge->next, clen);
#endif

				/* the non-exact line frags are related to exact line frags sort 
				 * of like to individual gentries: two kinds of exact frags
				 * must be interleaved, with one kind having the size of 3
				 * and the other kind having the size varying within +-2.
				 */

				ge = cge->next;
				do {
					GEX_FRAG *pf, *lastf1, *lastf2;
					int len1, len2, fraglen;

					f = X_FRAG(ge);

					fraglen = f->len[GEXFI_LINE];
					if(fraglen >= 4) {

						vert = 0; /* vert is a pseudo-directon */
						line[0] = line[1] = 1;
						maxlen[0] = minlen[0] = maxlen[1] = minlen[1] = 0;
						lastf2 = lastf1 = f;
						len2 = len1 = 0;
						for(pge = ge, i = 1; i < fraglen; i++, pge=pge->frwd) {
							pf = X_FRAG(pge);
							len = pf->len[GEXFI_EXACTLINE];
#if 0
							fprintf(stderr, "      pge=%p i=%d of %d ge=%p exLen=%d\n", pge, i, 
								f->len[GEXFI_LINE], ge, len);
#endif
							len1++; len2++;
							if(len==0) {
								continue;
							}
							vert = !vert; /* alternate the pseudo-direction */
							if(len > 3)
								line[!vert] = 0;
							if(maxlen[vert] == 0)
								maxlen[vert] = minlen[vert] = len;
							else if(maxlen[vert]-2 >= len && minlen[vert]+2 <= len) {
								if(len > maxlen[vert])
									maxlen[vert] = len;
								else if(len < minlen[vert])
									minlen[vert] = len;
							} else
								line[vert] = 0;
							if(line[0] == 0 && line[1] == 0) {
#if 0
								fprintf(stderr, "  Line breaks at %p %c(%d, %d) %c(%d, %d) len=%d fl=%d l2=%d l1=%d\n",
									pge, (!vert)?'*':' ', minlen[0], maxlen[0], 
									vert?'*':' ', minlen[1], maxlen[1], len, fraglen, len2, len1);
#endif
								if(lastf2 != lastf1) {
									lastf2->len[GEXFI_LINE] = len2-len1;
								}
								lastf1->len[GEXFI_LINE] = len1+1;
								pf->len[GEXFI_LINE] = fraglen+1 - i;
#if 0
								gex_dump_contour(pge, clen);
#endif

								/* continue with the line */
								vert = 0; /* vert is a pseudo-directon */
								line[0] = line[1] = 1;
								maxlen[0] = minlen[0] = maxlen[1] = minlen[1] = 0;
								lastf2 = lastf1 = f;
								len2 = len1 = 0;
							} else {
								lastf1 = pf;
								len1 = 0;
							}
						}
					}

					ge = ge->frwd;
				} while(ge != cge->next);
#if 0
				fprintf(stderr, "Line postprocessing part 2\n");
				gex_dump_contour(cge->next, clen);
#endif

				ge = cge->next;
				do {
					f = X_FRAG(ge);

					if(f->len[GEXFI_LINE] >= 4) {
						len = f->len[GEXFI_EXACTLINE];
						/* if a non-exact line covers precisely two exact lines,
						 * split it
						 */
						if(len > 0 && f->len[GEXFI_LINE] >= len+1) {
							GEX_FRAG *pf;
							pge = age[(f->aidx + len - 1)%clen]; /* last gentry of exact line */
							pf = X_FRAG(pge);
							if(f->len[GEXFI_LINE] + 1 == len + pf->len[GEXFI_EXACTLINE]) {
								f->len[GEXFI_LINE] = len;
								f->flags |= GEXFF_SPLIT;
								pf->len[GEXFI_LINE] = pf->len[GEXFI_EXACTLINE];
								pf->flags |= GEXFF_SPLIT;
							}
						}
					}

					ge = ge->frwd;
				} while(ge != cge->next);
#if 0
				fprintf(stderr, "Line postprocessing part 2a\n");
				gex_dump_contour(cge->next, clen);
#endif
				ge = cge->next;
				do {
					f = X_FRAG(ge);

					/* too small lines are of no interest */
					if( (f->flags & GEXFF_SPLIT)==0 && f->len[GEXFI_LINE] < 4)
						f->len[GEXFI_LINE] = 0;

					len = f->len[GEXFI_EXACTLINE];
					/* too small exact lines are of no interest */
					if(len < 3) /* exact lines may be shorter */
						f->len[GEXFI_EXACTLINE] = 0;
					/* get rid of inexact additions to the end of the exact lines */
					else if(f->len[GEXFI_LINE] == len+1)
						f->len[GEXFI_LINE] = len;
					/* same at the beginning */
					else {
						int diff = X_FRAG(ge->bkwd)->len[GEXFI_LINE] - len;

						if(diff == 1 || diff == 2) {
							X_FRAG(ge->bkwd)->len[GEXFI_LINE] = 0;
							f->len[GEXFI_LINE] = len;
						}
					}

					ge = ge->frwd;
				} while(ge != cge->next);
#if 0
				fprintf(stderr, "Line postprocessing is completed\n");
				gex_dump_contour(cge->next, clen);
#endif

				gex_calc_lenback(cge->next, clen); /* prepare data */

				/* resolve conflicts between lines and curves */

				/*
				 * the short (3-gentry) curve frags must have one of the ends
				 * coinciding with another curve frag of the same type
				 */

				for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) {
					ge = cge->next;
					do {
						f = X_FRAG(ge);

						if(f->len[d] == 3) {
							pge = age[(f->aidx + 2)%clen]; /* last gentry of this frag */
							if(f->lenback[d] == 0 && X_FRAG(pge)->len[d] == 0) {
								fprintf(stderr, "    discarded small %s at %p-%p\n", gxf_name[d], ge, pge);
								f->len[d] = 0;
								X_FRAG(ge->frwd)->lenback[d] = 0;
								X_FRAG(ge->frwd->frwd)->lenback[d] = 0;
							}
						}
						ge = ge->frwd;
					} while(ge != cge->next);
				}

				/* the serifs take priority over everything else */
				ge = cge->next;
				do {
					f = X_FRAG(ge);

					len = f->len[GEXFI_SERIF];
					if(len == 0)
						continue;

					if(len != 2) { /* this is used in the code below */
						fprintf(stderr, "Internal error at %s line %d: serif frags len is %d\n",
							__FILE__, __LINE__, len);
						exit(1);
					}

					for(d = 0; d < GEXFI_SERIF; d++) {
						/* serifs may not have common ends with the other fragments,
						 * this is expressed as extending them by 1 gentry on each side
						 */
						frag_subtract(g, age, clen, ge->bkwd, len+2, d);
					}
				} while( (ge = ge->frwd) != cge->next);

				/*
				 * longer exact lines take priority over curves; shorter lines
				 * and inexact lines are resolved with convex/concave conflicts
				 */
				ge = cge->next;
				do {
					f = X_FRAG(ge);

					len = f->len[GEXFI_EXACTLINE]; 

					if(len < 6) { /* line is short */
						ge = ge->frwd;
						continue;
					}

					fprintf(stderr, "   line at %p len=%d\n", ge, f->len[GEXFI_EXACTLINE]);
					for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) {
						frag_subtract(g, age, clen, ge, len, d);
					}

					ge = ge->frwd;
				} while(ge != cge->next);

				/*
				 * The exact lines take priority over curves that coincide
				 * with them or extend by only one gentry on either side
				 * (but not both sides). By this time it applies only to the
				 * small exact lines.
				 *
				 * An interesting general case is when a curve matches more
				 * than one exact line going diamond-like.
				 */

				ge = cge->next;
				do {
					int done, len2;
					int sharpness;
					GEX_FRAG *pf;

					f = X_FRAG(ge);

					/* "sharpness" shows how a group of exact line frags is connected: if the gentries 
					 * of some of them overlap, the curve matching requirement is loosened: it may
					 * extend up to 1 gentry beyond each end of the group of exact line frags
					 * (sharpness=2); otherwise it may extend to only one end (sharpness=1)
					 */
					sharpness = 1;

					len = f->len[GEXFI_EXACTLINE];
					if(len >= 4) {
						while(len < clen) {
							done = 0;
							pf = X_FRAG(ge->bkwd);
							for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) {
								if(f->len[d] == len || f->len[d] == len+1) {

									fprintf(stderr, "    removed %s frag at %p len=%d linelen=%d\n", 
										gxf_name[d], ge, f->len[d], len);
									pge = ge->frwd;
									for(i = f->len[d]; i > 1; i--, pge = pge->frwd)
										X_FRAG(pge)->lenback[d] = 0;
									f->len[d] = 0;
									gex_dump_contour(ge, clen);
									done = 1;
								} else if(pf->len[d] == len+1 || pf->len[d] == len+sharpness) {
									fprintf(stderr, "    removed %s frag at %p len=%d next linelen=%d\n", 
										gxf_name[d], ge->bkwd, pf->len[d], len);
									pge = ge;
									for(i = pf->len[d]; i > 1; i--, pge = pge->frwd)
										X_FRAG(pge)->lenback[d] = 0;
									pf->len[d] = 0;
									gex_dump_contour(ge, clen);
									done = 1;
								}
							}
							if(done)
								break;

							/* is there any chance to match a sequence of exect lines ? */
							if(f->len[GEXFI_CONVEX] < len && f->len[GEXFI_CONCAVE] < len
							&& pf->len[GEXFI_CONVEX] < len && pf->len[GEXFI_CONCAVE] < len)
								break;

							done = 1;
							/* check whether the line is connected to another exact line at an extremum */
							pge = age[(f->aidx + len - 1)%clen]; /* last gentry of exact line */
							len2 = X_FRAG(pge)->len[GEXFI_EXACTLINE];
							if(len2 > 0) {
								if( len2 >= 4 && (X_FRAG(pge)->flags & GEXFF_EXTR) ) {
									len += len2 - 1;
									sharpness = 2;
									done = 0;
								}
							} else {
								/* see if the extremum is between two exact lines */
								pge = pge->frwd;
								if(X_FRAG(pge)->flags & GEXFF_EXTR) {
									pge = pge->frwd;
									len2 = X_FRAG(pge)->len[GEXFI_EXACTLINE];
									if(len2 >= 4) {
										len += len2 + 1;
										done = 0;
									}
								}
							}
							if(done)
								break;
						}
					}

					ge = ge->frwd;
				} while(ge != cge->next);

				/* 
				 * The lines may cover only whole curves (or otherwise empty space),
				 * so cut them where they overlap parts of the curves. If 2 or less
				 * gentries are left in the line, remove the line.
				 * If a line and a curve fully coincide, remove the line.  Otherwise 
				 * remove the curves that are completely covered by the lines.
				 */

				ge = cge->next;
				do {
					f = X_FRAG(ge);

				reconsider_line:
					len = f->len[GEXFI_LINE];

					if(len == 0) {
						ge = ge->frwd;
						continue;
					}

					if(f->len[GEXFI_CONVEX] >= len 
					|| f->len[GEXFI_CONCAVE] >= len) {
				line_completely_covered:
						fprintf(stderr, "    removed covered Line frag at %p len=%d\n", 
							ge, len);
						f->len[GEXFI_LINE] = 0;
						for(pge = ge->frwd; len > 1; len--, pge = pge->frwd)
							X_FRAG(pge)->lenback[GEXFI_LINE] = 0;
						gex_dump_contour(ge, clen);
						ge = ge->frwd;
						continue;
					}
					
					k1 = 0; /* how much to cut at the front */
					for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) {
						if(f->lenback[d]) {
							pge = age[(f->aidx + clen - f->lenback[d])%clen];
							i = X_FRAG(pge)->len[d] - f->lenback[d] - 1;
							if(i > k1)
								k1 = i;
						}
					}

					k2 = 0; /* how much to cut at the end */
					pge = age[(f->aidx + len)%clen]; /* gentry after the end */
					for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) {
						i = X_FRAG(pge)->lenback[d] - 1;
						if(i > k2)
							k2 = i;
					}

					if(k1+k2 > 0 && k1+k2 >= len-3) {
						fprintf(stderr, "    k1=%d k2=%d\n", k1, k2);
						goto line_completely_covered;
					}


					if(k2 != 0) { /* cut the end */
						len -= k2;
						f->len[GEXFI_LINE] = len;
						/* pge still points after the end */
						for(i = k2, pge = pge->bkwd; i > 0; i--, pge = pge->bkwd)
							X_FRAG(pge)->lenback[GEXFI_LINE] = 0;
					}
					if(k1 != 0) { /* cut the beginning */
						len -= k1;
						f->len[GEXFI_LINE] = 0;
						for(i = 1, pge = ge->frwd; i < k1; i++, pge = pge->frwd)
							X_FRAG(pge)->lenback[GEXFI_LINE] = 0;
						X_FRAG(pge)->len[GEXFI_LINE] = len;
						for(i = 0; i < len; i++, pge = pge->frwd)
							X_FRAG(pge)->lenback[GEXFI_LINE] = i;
					}
					if(k1 != 0 || k2 != 0) {
						fprintf(stderr, "    cut Line frag at %p by (%d,%d) to len=%d\n", 
							ge, k1, k2, len);
						gex_dump_contour(ge, clen);

						goto reconsider_line; /* the line may have to be cut again */
					}
					pge = age[(f->aidx + k1)%clen]; /* new beginning */
					good = 1; /* flag: no need do do a debugging dump */
					for(i=1; i<len; i++, pge = pge->frwd)
						for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) {
							if(X_FRAG(pge)->len[d]) {
								fprintf(stderr, "    removed %s frag at %p len=%d covered by line\n", 
									gxf_name[d], pge, X_FRAG(pge)->len[d], len);
								good = 0;
							}
							X_FRAG(pge)->len[d] = 0;
						}
					pge = age[(f->aidx + k1 + 1)%clen]; /* next after new beginning */
					for(i=1; i<len; i++, pge = pge->frwd)
						for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++)
							X_FRAG(pge)->lenback[d] = 0;
					if(!good)
						gex_dump_contour(ge, clen);

					ge = ge->frwd;
				} while(ge != cge->next);

				/* Resolve conflicts between curves */
				for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) {
					dx = (GEXFI_CONVEX + GEXFI_CONCAVE) - d; /* the other type */
					ge = cge->next;
					do {
						GENTRY *sge;

						f = X_FRAG(ge);
						len = f->len[d];
						if(len < 2) {
							ge = ge->frwd;
							continue;
						}
						sge = ge; /* the start of fragment */

						i = f->len[dx];
						if(i != 0) { /* two curved frags starting here */
							/* should be i!=len because otherwise they would be
							 * covered by an exact line
							 */
							if(i > len) {
							curve_completely_covered:
								/* remove the convex frag */
								fprintf(stderr, "    removed %s frag at %p len=%d covered by %s\n", 
									gxf_name[d], ge, len, gxf_name[dx]);
								f->len[d] = 0;
								for(pge = ge->frwd, j = 1; j < len; j++, pge = pge->frwd)
									X_FRAG(pge)->lenback[d] = 0;
								gex_dump_contour(ge, clen);

								ge = ge->frwd; /* the frag is gone, nothing more to do */
								continue;
							} else {
								/* remove the concave frag */
								fprintf(stderr, "    removed %s frag at %p len=%d covered by %s\n", 
									gxf_name[dx], ge, i, gxf_name[d]);
								f->len[dx] = 0;
								for(pge = ge->frwd, j = 1; j < i; j++, pge = pge->frwd)
									X_FRAG(pge)->lenback[dx] = 0;
								gex_dump_contour(ge, clen);
							}
						}


						k1 = X_FRAG(ge->frwd)->lenback[dx];
						if(k1 != 0) { /* conflict at the front */
							GENTRY *gels, *gele, *gei;

							pge = age[(f->aidx + clen - (k1-1))%clen]; /* first gentry of concave frag */
							k2 = X_FRAG(pge)->len[dx]; /* its length */
							
							i = k2 - (k1-1); /* amount of overlap */
							if(i > len)
								i = len;
							/* i >= 2 by definition */
							if(i >= k2-1) { /* covers the other frag - maybe with 1 gentry showing */
								fprintf(stderr, "    removed %s frag at %p len=%d covered by %s\n", 
									gxf_name[dx], pge, k2, gxf_name[d]);
								X_FRAG(pge)->len[dx] = 0;
								for(pge = pge->frwd, j = 1; j < k2; j++, pge = pge->frwd)
									X_FRAG(pge)->lenback[dx] = 0;
								if(i >= len-1) { /* covers our frag too - maybe with 1 gentry showing */
									/* our frag will be removed as well, prepare a line to replace it */
									gels = ge;
									gele = age[(f->aidx + i - 1)%clen];
									fprintf(stderr, "    new Line frag at %p-%p len=%d\n", gels, gele, i);
									X_FRAG(gels)->len[GEXFI_LINE] = i;
									for(gei = gels->frwd, j = 1; j < i; gei = gei->frwd, j++)
										X_FRAG(gei)->lenback[GEXFI_LINE] = j;
								} else {
									gex_dump_contour(ge, clen);
									ge = ge->frwd;
									continue;
								}
							}
							if(i >= len-1) /* covers our frag - maybe with 1 gentry showing */
								goto curve_completely_covered;

							/* XXX need to do something better for the case when a curve frag
							 * is actually nothing but an artifact of two other curves of
							 * the opposite type touching each other, like on the back of "3"
							 */

							/* change the overlapping part to a line */
							gels = ge;
							gele = age[(f->aidx + i - 1)%clen];
							/* give preference to local extremums */
							if(X_FRAG(gels)->flags & GEXFF_EXTR) {
								gels = gels->frwd;
								i--;
							}
							if(X_FRAG(gele)->flags & GEXFF_EXTR) {
								gele = gele->bkwd;
								i--;
							}
							if(gels->bkwd == gele) { 
								/* Oops the line became negative.  Probably should 
								 * never happen but I can't think of any formal reasoning
								 * leading to that, so check just in case. Restore
								 * the previous state.
								 */
								gels = gele; gele = gels->frwd; i = 2;
							}

							j = X_FRAG(gels)->lenback[dx] + 1; /* new length */
							if(j != k2) {
								X_FRAG(pge)->len[dx] = j;
								fprintf(stderr, "    cut %s frag at %p len=%d to %p len=%d end overlap with %s\n", 
									gxf_name[dx], pge, k2, gels, j, gxf_name[d]);
								for(gei = gels->frwd; j < k2; gei = gei->frwd, j++)
									X_FRAG(gei)->lenback[dx] = 0;
							}

							if(gele != ge) {
								sge = gele;
								f->len[d] = 0;
								fprintf(stderr, "    cut %s frag at %p len=%d ", gxf_name[d], ge, len);
								len--;
								for(gei = ge->frwd; gei != gele; gei = gei->frwd, len--)
									X_FRAG(gei)->lenback[d] = 0;
								X_FRAG(gele)->len[d] = len;
								X_FRAG(gele)->lenback[d] = 0;
								fprintf(stderr, "to %p len=%d start overlap with %s\n", 
									sge, len, gxf_name[dx]);
								for(gei = gei->frwd, j = 1; j < len; gei = gei->frwd, j++)
									X_FRAG(gei)->lenback[d] = j;

							}
							if(i > 1) {
								fprintf(stderr, "    new Line frag at %p-%p len=%d\n", gels, gele, i);
								X_FRAG(gels)->len[GEXFI_LINE] = i;
								for(gei = gels->frwd, j = 1; j < i; gei = gei->frwd, j++)
									X_FRAG(gei)->lenback[GEXFI_LINE] = j;
							}
							gex_dump_contour(ge, clen);
						}

						ge = ge->frwd;
					} while(ge != cge->next);
				}

				/* 
				 * Assert that there are no conflicts any more and
				 * for each gentry find the fragment types that start
				 * and continue here.
				 */
				ge = cge->next;
				do {
					f = X_FRAG(ge);
					dx = GEXFI_NONE; /* type that starts here */
					dy = GEXFI_NONE; /* type that goes through here */
					/* GEXFI_EXACTLINE and GEXFI_SERIF are auxiliary and don't
					 * generate any actual lines/curves in the result
					 */
					for(d = GEXFI_CONVEX; d<= GEXFI_LINE; d++) {
						if(f->len[d]) {
							if(dx >= 0) {
								fprintf(stderr, "**** Internal error in vectorization\n");
								fprintf(stderr, "CONFLICT in %s at %p between %s and %s\n",
									g->name, ge, gxf_name[dx], gxf_name[d]);
								dumppaths(g, cge->next, cge->next->bkwd);
								gex_dump_contour(ge, clen);
								exit(1);
							}
							dx = d;
						}
						if(f->lenback[d]) {
							if(dy >= 0) {
								fprintf(stderr, "**** Internal error in vectorization\n");
								fprintf(stderr, "CONFLICT in %s at %p between %s and %s\n",
									g->name, ge, gxf_name[dy], gxf_name[d]);
								dumppaths(g, cge->next, cge->next->bkwd);
								gex_dump_contour(ge, clen);
								exit(1);
							}
							dy = d;
						}
					}
					f->ixstart = dx;
					f->ixcont = dy;
					ge = ge->frwd;
				} while(ge != cge->next);

				/*
				 * make sure that the contour does not start in the
				 * middle of a fragment
				 */
				ge = cge->next; /* old start of the contour */
				f = X_FRAG(ge);
				if(f->ixstart == GEXFI_NONE && f->ixcont != GEXFI_NONE) {
					/* oops, it's mid-fragment, move the start */
					GENTRY *xge;

					xge = ge->bkwd->next; /* entry following the contour */

					/* find the first gentry of this frag */
					pge = age[(f->aidx + clen - f->lenback[f->ixcont])%clen]; 

					ge->prev = ge->bkwd; 
					ge->bkwd->next = ge;

					cge->next = pge;
					pge->prev = cge;

					pge->bkwd->next = xge;
					if(xge) 
						xge->prev = pge->bkwd;

					cge->ix3 = pge->bkwd->ix3; cge->iy3 = pge->bkwd->iy3;
				}

				/* vectorize each fragment separately 
				 * make 2 passes: first handle the straight lines, then
				 * the curves to allow the curver to be connected smoothly
				 * to the straights
				 */
				ge = cge->next;
				do { /* pass 1 */
					f = X_FRAG(ge);
					switch(f->ixstart) {
					case GEXFI_LINE:
						len = f->len[GEXFI_LINE];
						pge = age[(f->aidx + len - 1)%clen]; /* last gentry */

						if(ge->iy3 == ge->bkwd->iy3) { /* frag starts and ends horizontally */
							k1 = 1/*Y*/ ; /* across the direction of start */
							k2 = 0/*X*/ ; /* along the direction of start */
						} else { /* frag starts and ends vertically */
							k1 = 0/*X*/ ; /* across the direction of start */
							k2 = 1/*Y*/ ; /* along the direction of start */
						}

						if(len % 2) {
							/* odd number of entries in the frag */
							double halfstep, halfend;

							f->vect[0][k1] = fscale * ge->ipoints[k1][2];
							f->vect[3][k1] = fscale * pge->ipoints[k1][2];

							halfstep = (pge->ipoints[k2][2] - ge->bkwd->ipoints[k2][2]) 
								* 0.5 / ((len+1)/2);
							if(f->ixcont != GEXFI_NONE) {
								halfend = (ge->ipoints[k2][2] - ge->bkwd->ipoints[k2][2]) * 0.5;
								if(fabs(halfstep) < fabs(halfend)) /* must be at least half gentry away */
									halfstep = halfend;
							}
							if(X_FRAG(pge)->ixstart != GEXFI_NONE) {
								halfend = (pge->ipoints[k2][2] - pge->bkwd->ipoints[k2][2]) * 0.5;
								if(fabs(halfstep) < fabs(halfend)) /* must be at least half gentry away */
									halfstep = halfend;
							}
							f->vect[0][k2] = fscale * (ge->bkwd->ipoints[k2][2] + halfstep);
							f->vect[3][k2] = fscale * (pge->ipoints[k2][2] - halfstep);
						} else {
							/* even number of entries */
							double halfstep, halfend;

							f->vect[0][k1] = fscale * ge->ipoints[k1][2];
							halfstep = (pge->ipoints[k2][2] - ge->bkwd->ipoints[k2][2]) 
								* 0.5 / (len/2);
							if(f->ixcont != GEXFI_NONE) {
								halfend = (ge->ipoints[k2][2] - ge->bkwd->ipoints[k2][2]) * 0.5;
								if(fabs(halfstep) < fabs(halfend)) /* must be at least half gentry away */
									halfstep = halfend;
							}
							f->vect[0][k2] = fscale * (ge->bkwd->ipoints[k2][2] + halfstep);

							halfstep = (pge->ipoints[k1][2] - ge->bkwd->ipoints[k1][2]) 
								* 0.5 / (len/2);
							if(X_FRAG(pge)->ixstart != GEXFI_NONE) {
								halfend = (pge->ipoints[k1][2] - pge->bkwd->ipoints[k1][2]) * 0.5;
								if(fabs(halfstep) < fabs(halfend)) /* must be at least half gentry away */
									halfstep = halfend;
							}
							f->vect[3][k1] = fscale * (pge->ipoints[k1][2] - halfstep);
							f->vect[3][k2] = fscale * pge->ipoints[k2][2];
						}
						f->vectlen = len;
						f->flags |= GEXFF_DRAWLINE;
						break;
					}
				} while((ge = ge->frwd) != cge->next);

				ge = cge->next;
				do { /* pass 2 */
					/* data for curves */
					GENTRY *firstge, *lastge, *gef, *gel, *gei, *gex;
					GENTRY *ordhd; /* head of the order list */
					GENTRY **ordlast;
					int nsub; /* number of subfrags */
					GEX_FRAG *ff, *lf, *xf;

					f = X_FRAG(ge);
					switch(f->ixstart) {
					case GEXFI_CONVEX:
					case GEXFI_CONCAVE:
						len = f->len[f->ixstart];
						firstge = ge;
						lastge = age[(f->aidx + len - 1)%clen]; /* last gentry */

						nsub = 0;
						gex = firstge;
						xf = X_FRAG(gex);
						xf->prevsub = 0;
						xf->sublen = 1;
						xf->flags &= ~GEXFF_DONE;
						for(gei = firstge->frwd; gei != lastge; gei = gei->frwd) {
							xf->sublen++;
							if(X_FRAG(gei)->flags & GEXFF_EXTR) {
									xf->nextsub = gei;
									for(i=0; i<2; i++)
										xf->bbox[i] = abs(gei->ipoints[i][2] - gex->bkwd->ipoints[i][2]);
									nsub++;
									xf = X_FRAG(gei);
									xf->prevsub = gex;
									xf->sublen = 1;
									xf->flags &= ~GEXFF_DONE;
									gex = gei;
								}
						}
						xf->sublen++;
						xf->nextsub = gei;
						for(i=0; i<2; i++)
							xf->bbox[i] = abs(gei->ipoints[i][2] - gex->bkwd->ipoints[i][2]);
						nsub++;
						ff = xf; /* remember the beginning of the last subfrag */
						xf = X_FRAG(gei);
						xf->prevsub = gex;
						if(firstge != lastge) {
							xf->nextsub = 0;
							xf->sublen = 0;

							/* correct the bounding box of the last and first subfrags for
							 * intersections with other fragments 
							 */
							if(xf->ixstart != GEXFI_NONE) {
								/* ff points to the beginning of the last subfrag */
								for(i=0; i<2; i++)
									ff->bbox[i] -= 0.5 * abs(lastge->ipoints[i][2] - lastge->bkwd->ipoints[i][2]);
							}
							ff = X_FRAG(firstge);
							if(ff->ixcont != GEXFI_NONE) {
								for(i=0; i<2; i++)
									ff->bbox[i] -= 0.5 * abs(firstge->ipoints[i][2] - firstge->bkwd->ipoints[i][2]);
							}
						}

						fprintf(stderr, " %s frag %p%s nsub=%d\n", gxf_name[f->ixstart],
							ge, (f->flags&GEXFF_CIRC)?" circular":"", nsub);

						/* find the symmetry between the subfragments */
						for(gef = firstge, count=0; count < nsub; gef = ff->nextsub, count++) {
							ff = X_FRAG(gef);
							gex = ff->nextsub;
							xf = X_FRAG(gex);
							gel = xf->nextsub;
							if(gel == 0) {
								ff->flags &= ~GEXFF_SYMNEXT;
								break; /* not a circular frag */
							}
							good = 1; /* assume that we have symmetry */
							/* gei goes backwards, gex goes forwards from the extremum */
							gei = gex;
							/* i is the symmetry axis, j is the other axis (X=0 Y=1) */
							ff->symaxis = i = (gex->ix3 != gex->bkwd->ix3);
							j = !i;
							for( ; gei!=gef && gex!=gel; gei=gei->bkwd, gex=gex->frwd) {
								if( gei->bkwd->ipoints[i][2] != gex->ipoints[i][2]
								|| gei->bkwd->ipoints[j][2] - gei->ipoints[j][2]
									!= gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] 
								) {
									good = 0; /* no symmetry */
									break;
								}
							}
							if(good) {
								if( isign(gei->bkwd->ipoints[j][2] - gei->ipoints[j][2])
								!= isign(gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]) ) {
									good = 0; /* oops, goes into another direction */
								}
							}
							if(good)
								ff->flags |= GEXFF_SYMNEXT;
							else
								ff->flags &= ~GEXFF_SYMNEXT;
						}

						for(gef = firstge, count=0; count < nsub; gef = ff->nextsub, count++) {
							ff = X_FRAG(gef);
							if((ff->flags & GEXFF_SYMNEXT)==0) {
								ff->symxlen = 0;
								continue;
							}
							gex = ff->prevsub;
							if(gex == 0 || (X_FRAG(gex)->flags & GEXFF_SYMNEXT)==0) {
								ff->symxlen = 0;
								continue;
							}
							ff->symxlen = X_FRAG(gex)->sublen;
							xf = X_FRAG(ff->nextsub);
							if(xf->sublen < ff->symxlen)
								ff->symxlen = xf->sublen;
						}

						/* find the symmetry inside the subfragments */
						for(gef = firstge, count=0; count < nsub; gef = ff->nextsub, count++) {
							ff = X_FRAG(gef);

							if(ff->sublen % 2) {
								/* we must have an even number of gentries for diagonal symmetry */
								ff->symge = 0;
								continue;
							}

							/* gei goes forwards from the front */
							gei = gef->frwd;
							/* gex goes backwards from the back */
							gex = ff->nextsub->bkwd;

							/* i is the direction of gei, j is the direction of gex */
							i = (gei->iy3 != gei->bkwd->iy3);
							j = !i;
							for( ; gei->bkwd != gex; gei=gei->frwd, gex=gex->bkwd) {
								if( abs(gei->bkwd->ipoints[i][2] - gei->ipoints[i][2])
								!= abs(gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]) )
									break; /* no symmetry */
								i = j;
								j = !j;
							}
							if(gei->bkwd == gex)
								ff->symge = gex;
							else
								ff->symge = 0; /* no symmetry */
						}

						/* find the order of calculation:
						 * prefer to start from long fragments that have the longest
						 * neighbours symmetric with them, with all being equal prefer
						 * the fragments that have smaller physical size
						 */
						ordhd = 0;
						for(gef = firstge, count=0; count < nsub; gef = ff->nextsub, count++) {
							ff = X_FRAG(gef);

							for(ordlast = &ordhd; *ordlast != 0; ordlast = &xf->ordersub) {
								xf = X_FRAG(*ordlast);
								if(ff->sublen > xf->sublen)
									break;
								if(ff->sublen < xf->sublen)
									continue;
								if(ff->symxlen > xf->symxlen)
									break;
								if(ff->symxlen < xf->symxlen)
									continue;
								if(ff->bbox[0] < xf->bbox[0] || ff->bbox[1] < xf->bbox[1])
									break;
							}

							ff->ordersub = *ordlast;
							*ordlast = gef;
						}

						/* vectorize the subfragments */
						for(gef = ordhd; gef != 0; gef = ff->ordersub) {

							/* debugging stuff */
							ff = X_FRAG(gef);
							fprintf(stderr, "   %p-%p bbox[%g,%g] sym=%p %s len=%d xlen=%d\n",
								gef, ff->nextsub, ff->bbox[0], ff->bbox[1], ff->symge, 
								(ff->flags & GEXFF_SYMNEXT) ? "symnext" : "",
								ff->sublen, ff->symxlen);

							dosubfrag(g, f->ixstart, firstge, gef, fscale);
						}

						break;
					}
				} while((ge = ge->frwd) != cge->next);

				free(age);

			}

		}

		/* all the fragments are found, extract the vectorization */
		pge = g->entries;
		g->entries = g->lastentry = 0;
		g->flags |= GF_FLOAT;
		loopge = 0;
		skip = 0;

		for(ge = pge; ge != 0; ge = ge->next) {
			GEX_FRAG *f, *pf;

			switch(ge->type) {
			case GE_LINE:
				f = X_FRAG(ge);
				if(skip == 0) {
					if(f->flags & (GEXFF_DRAWLINE|GEXFF_DRAWCURVE)) {
						/* draw a line to the start point */
						fg_rlineto(g, f->vect[0][0], f->vect[0][1]);
						/* draw the fragment */
						if(f->flags & GEXFF_DRAWCURVE)
							fg_rrcurveto(g, 
								f->vect[1][0], f->vect[1][1],
								f->vect[2][0], f->vect[2][1],
								f->vect[3][0], f->vect[3][1]);
						else
							fg_rlineto(g, f->vect[3][0], f->vect[3][1]);
						skip = f->vectlen - 2;
					} else {
						fg_rlineto(g, fscale * ge->ix3, fscale * ge->iy3);
					}
				} else
					skip--;
				break;
			case GE_MOVE:
				fg_rmoveto(g, -1e6, -1e6); /* will be fixed by GE_PATH */
				skip = 0;
				/* remember the reference to update it later */
				loopge = g->lastentry;
				break;
			case GE_PATH:
				/* update the first MOVE of this contour */
				if(loopge) {
					loopge->fx3 = g->lastentry->fx3;
					loopge->fy3 = g->lastentry->fy3;
					loopge = 0;
				}
				g_closepath(g);
				break;
			}
		}
		for(ge = pge; ge != 0; ge = cge) {
			cge = ge->next;
			free(ge->ext);
			free(ge);
		}
		dumppaths(g, NULL, NULL);
		
		/* end of vectorization logic */
	} else {
		/* convert the data to float */
		GENTRY *ge;
		double x, y;

		for(ge = g->entries; ge != 0; ge = ge->next) {
			ge->flags |= GEF_FLOAT;
			if(ge->type != GE_MOVE && ge->type != GE_LINE) 
				continue;

			x = fscale * ge->ix3;
			y = fscale * ge->iy3;

			ge->fx3 = x;
			ge->fy3 = y;
		}
		g->flags |= GF_FLOAT;
	}

	free(hlm); free(vlm); free(amp);
}

#if 0
/* print out the bitmap */
printbmap(bmap, xsz, ysz, xoff, yoff)
	char *bmap;
	int xsz, ysz, xoff, yoff;
{
	int x, y;

	for(y=ysz-1; y>=0; y--) {
		putchar( (y%10==0) ? y/10+'0' : ' ' );
		putchar( y%10+'0' );
		for(x=0; x<xsz; x++)
			putchar( bmap[y*xsz+x] ? 'X' : '.' );
		if(-yoff==y)
			putchar('_'); /* mark the baseline */
		putchar('\n');
	}
	putchar(' '); putchar(' ');
	for(x=0; x<xsz; x++)
		putchar( x%10+'0' );
	putchar('\n'); putchar(' '); putchar(' ');
	for(x=0; x<xsz; x++)
		putchar( (x%10==0) ? x/10+'0' : ' ' );
	putchar('\n');
}

/* print out the limits of outlines */
printlimits(hlm, vlm, amp, xsz, ysz)
	char *hlm, *vlm, *amp;
	int xsz, ysz;
{
	int x, y;
	static char h_char[]={ ' ', '~', '^' };
	static char v_char[]={ ' ', '(', ')' };

	for(y=ysz-1; y>=0; y--) {
		for(x=0; x<xsz; x++) {
			if(amp[y*xsz+x])
				putchar('!'); /* ambigouos point is always on a limit */
			else
				putchar(v_char[ vlm[y*(xsz+1)+x] & (L_ON|L_OFF) ]);
			putchar(h_char[ hlm[(y+1)*xsz+x] & (L_ON|L_OFF) ]);
		}
		putchar(v_char[ vlm[y*(xsz+1)+x] & (L_ON|L_OFF) ]);
		putchar('\n');
	}
	/* last line */
	for(x=0; x<xsz; x++) {
		putchar(' ');
		putchar(h_char[ hlm[x] & (L_ON|L_OFF) ]);
	}
	putchar(' ');
	putchar('\n');
}
#endif /* 0 */