MultiSource/Benchmarks/MallocBench/gs/gsim2out.c - third_party/llvm-test-suite - Git at Google

 /* Copyright (C) 1989, 1990 Aladdin Enterprises.  All rights reserved.
    Distributed by Free Software Foundation, Inc.

 This file is part of Ghostscript.

 Ghostscript is distributed in the hope that it will be useful, but
 WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
 to anyone for the consequences of using it or for whether it serves any
 particular purpose or works at all, unless he says so in writing.  Refer
 to the Ghostscript General Public License for full details.

 Everyone is granted permission to copy, modify and redistribute
 Ghostscript, but only under the conditions described in the Ghostscript
 General Public License.  A copy of this license is supposed to have been
 given to you along with Ghostscript so you can know your rights and
 responsibilities.  It should be in a file named COPYING.  Among other
 things, the copyright notice and this notice must be preserved on all
 copies.  */

 /* gsim2out.c */
 /* Image to outline conversion for GhostScript library */
 #include "gx.h"
 #include "memory_.h"
 #include "gserrors.h"
 #include "gsmatrix.h"
 #include "gsstate.h"
 #include "gscoord.h"
 #include "gxfixed.h"
 #include "gxtype1.h"

 /*
  * Convert a bitmap image to an outline (path) representation.
  * The outline representation is in Adobe Type 1 CharString format.
  * See ghost.doc for more details.
  */

 /* Define the state of the conversion process. */
 typedef struct {
 	/* The following are set at the beginning of the conversion. */
 	gs_matrix ifm;			/* inverse of (CTM */
 					/* scaled by width/height * 4). */
 	byte *limit;			/* stop output here */
 	int ox, oy;			/* X/Y pixel offset of char origin */
 	/* The following are updated dynamically. */
 	byte *next;			/* next byte goes here */
 	int px, py;			/* X/Y position at start of run */
 	int cpx, cpy;			/* px/py in character coordinates */
 	int dx, dy;			/* X/Y increment of current run */
 	int count;			/* # of steps in current run */
 } status;

 /* Define the scaling for the path tracer. */
 #define outline_scale 4

 /* Forward declarations */
 private int round_coord(P1(floatp));
 private int put_int(P2(status *, int));
 private void fill_cells(P4(byte *, byte *, int, int));
 private int trace_cells(P4(byte *, int, int, status *));

 /*
  * gs_type1imagepath encodes an image into a byte string supplied
  * by the caller.  If the string is not big enough, the procedure
  * returns gs_error_limitcheck.  Otherwise, the procedure returns
  * the actual number of bytes of data stored.
  */
 int
 gs_type1imagepath(gs_state *pgs, byte *data, int width, int height,
   floatp wx, floatp wy, floatp origin_x, floatp origin_y,
   byte *str, uint maxlen)
 {	uint csize;
 	byte *cells;
 	status stat;
 	status *out = &stat;
 	int lsbx;
 	int iwx, iwy, ilsbx, ilsby;
 	int code;
 	/* Construct the coordinate transformation. */
 	   {	float hsc = height * outline_scale;
 		gs_matrix mat;
 		gs_currentmatrix(pgs, &stat.ifm);
 #ifdef DEBUG
 if ( gs_debug['0'] )
 		printf("[0]ctm=[%g %g %g %g %g %g]\n",
 			stat.ifm.xx, stat.ifm.xy, stat.ifm.yx, stat.ifm.yy,
 			stat.ifm.tx, stat.ifm.ty);
 #endif
 		if (	(code = gs_make_scaling(hsc, hsc, &mat)) < 0 ||
 			(code = gs_matrix_multiply(&mat, &stat.ifm, &stat.ifm)) < 0 ||
 			(code = gs_matrix_invert(&stat.ifm, &stat.ifm)) < 0
 		   )
 			return code;
 	   }
 	/* Allocate and fill in the cell matrix. */
 	csize = (width + 2) * (height + 2);
 	cells = (byte *)gs_malloc(csize, 1, "gsim2out cells");
 	if ( cells == 0 ) return_error(gs_error_VMerror);
 	fill_cells(cells, data, width, height);
 	/* Initialize the rest of the state. */
 	stat.next = str;
 	stat.limit = str + maxlen;
 	/* Determine the left side bearing by looking for */
 	/* the leftmost column with any 1-bits. */
 	for ( lsbx = 0; lsbx < width; lsbx++ )
 	   {	int y;
 		for ( y = 1; y <= height; y++ )
 		  if ( cells[y * (width + 2) + lsbx + 1] ) goto xit;
 	   }
 xit:	/* Encode the origin, width, and side bearing. */
 	   {	gs_point opt, wpt, lsbpt;
 		if (	(code = gs_distance_transform(origin_x * outline_scale,
 						      origin_y * outline_scale,
 						      &stat.ifm, &opt)) < 0 ||
 			(code = gs_distance_transform(wx * outline_scale,
 						      wy * outline_scale,
 						      &stat.ifm, &wpt)) < 0 ||
 			(code = gs_distance_transform((lsbx - origin_x) *
 						       outline_scale, (floatp)0,
 						      &stat.ifm, &lsbpt)) < 0
 		   )
 			return code;
 		stat.ox = round_coord(opt.x);
 		stat.oy = round_coord(opt.y);
 		iwx = round_coord(wpt.x);
 		iwy = round_coord(wpt.y);
 		ilsbx = round_coord(lsbpt.x);
 		ilsby = round_coord(lsbpt.y);
 #ifdef DEBUG
 if ( gs_debug['0'] )
 	   {	int cy, cx;
 		byte *cp = data;
 		printf("[0]w=%d h=%d oxy=(%g,%g) wxy=(%g,%g)\n",
 			width, height, origin_x, origin_y, wx, wy);
 		printf("   io=(%d,%d) iw=(%d,%d) ilsb=(%d,%d)\n",
 			stat.ox, stat.oy, iwx, iwy, ilsbx, ilsby);
 		for ( cy = 0; cy < height; cy++ )
 		   {	printf("[0]%3d ", cy);
 			for ( cx = 0; cx < width; cx += 8 )
 				printf("%02x", (int)*cp++);
 			putchar('\n');
 		   }
 	   }
 #endif
 		if ( (code = put_int(out, ilsbx)) < 0 ) return code;
 		if ( iwy != 0 || ilsby != 0 )
 		   {	if (	(code = put_int(out, ilsby)) < 0 ||
 				(code = put_int(out, iwx)) < 0 ||
 				(code = put_int(out, iwy)) < 0
 			   )
 				return code;
 			if ( stat.next + 2 > stat.limit )
 				return_error(gs_error_limitcheck);
 			*stat.next++ = (byte)c_escape;
 			*stat.next++ = (byte)ce_sbw;
 		   }
 		else
 		   {	if ( (code = put_int(out, iwx)) < 0 ) return code;
 			if ( stat.next + 1 > stat.limit )
 				return_error(gs_error_limitcheck);
 			*stat.next++ = (byte)c_hsbw;
 		   }
 	   }
 	/* Since all further movements are relative, we can account */
 	/* for the origin by simply setting px/py to the lsb, */
 	/* and cpx/cpy to the lsb plus the origin. */
 	stat.px = (lsbx * outline_scale);
 	stat.py = (int)(origin_y * outline_scale);
 	stat.cpx = ilsbx + stat.ox;
 	stat.cpy = ilsby + stat.oy;
 	/* Trace the outline of the cells. */
 	code = trace_cells(cells, width, height, out);
 	gs_free((char *)cells, csize, 1, "gsim2out cells");
 	if ( code < 0 ) return code;
 	if ( stat.next >= stat.limit ) return_error(gs_error_limitcheck);
 	*stat.next++ = (byte)c_endchar;
 	return stat.next - str;
 }

 /* Fill the cell matrix with the image being traced. */
 /* The cell matrix has a row and column of zero padding on each side, */
 /* so we don't have to check for boundary conditions all the time. */
 /* Note that the image data are in PostScript / Ghostscript standard */
 /* order (left to right, top row first), but the cells are stored */
 /* bottom row first. */
 private void
 fill_cells(byte *cells, byte *data, int width, int height)
 {	int y;
 	byte *dptr = data - 1;
 	byte *cptr = cells + (width + 2) * height + 1;
 	memset(cells, 0, (width + 2) * (height + 2));
 	for ( y = 0; y < height; y++ )
 	   {	register int mask = 0;
 		register int b;
 		register int x;
 		for ( x = 0; x < width; x++, mask >>= 1, cptr++ )
 		   {	if ( mask == 0 ) mask = 0x80, b = *++dptr;
 			if ( b & mask ) *cptr = 1;
 		   }
 		cptr -= width * 2 + 2;	/* back up 1 row */
 	   }
 }

 /* Trace the cells to form an outline.  The trace goes in clockwise */
 /* order, always starting by going west along a bottom edge. */
 /* All the subsidiary routines return 0 on success, */
 /* -1 if the output buffer overflowed. */
 private int trace_from(P3(status *, byte *, int));
 private int add_dxdy(P4(status *, int, int, int));
 #define add_deltas(s, dx, dy, n)\
   if ( (code = add_dxdy(s, dx, dy, n)) < 0 ) return code
 private int put_dxdy(P4(status *, int, int, int));
 #define put_deltas(s, dx, dy, moving)\
   if ( (code = put_dxdy(s, dx, dy, moving)) < 0 ) return code
 private int
 trace_cells(byte *cells, int width, int height, register status *out)
 {	byte *cptr;
 	int code;
 	for ( cptr = cells + (width + 2) * (height + 1) - 2;
 	      cptr >= cells;  cptr--
 	    )
 	   {	if ( *cptr == 1 && cptr[-(width+2)] == 0 )
 		   {	/* Found a starting point */
 			int x = (cptr-cells) % (width+2) - 1;
 			int y = (cptr-cells) / (width+2) - 1;
 			put_deltas(out,
 				   x * outline_scale + 1 - out->px,
 				   y * outline_scale - out->py,
 				   1);
 			out->count = 0;
 			if ( (code = trace_from(out, cptr, width)) < 0 )
 				return code;
 			if ( out->next >= out->limit )
 				return_error(gs_error_limitcheck);
 			*out->next++ = (byte)c_closepath;
 		   }
 	   }
 	return 0;
 }

 /* Trace a path */
 private int
 trace_from(register status *out, byte *cptr, int width)
 {	typedef enum {			/* must be in this order */
 		north = 0, east = 1, south = 2, west = 3
 	} direction;
 	direction dir;
 	int w2 = width + 2;		/* actual width of cell rows */
 	int part;			/* how far along edge we are */
 	int code;
 	/* Movement tables */
 	typedef struct {
 		short tx, ty;		/* relative index of first cell */
 					/* to test (counter-clockwise move) */
 		short dx, dy;		/* continue in same direction */
 	   } dir_descr;
 	static dir_descr nesw[4+1] =
 	   {	/* Going north (along a western edge) */
 		   { -1, 1,   0, 1 },
 		/* Going east (along a northern edge) */
 			{ 1, 1,   1, 0 },
 		/* Going south (along an eastern edge) */
 		   { 1, -1,   0, -1 },
 		/* Going west (along a southern edge) */
 		   { -1, -1,   -1, 0 },
 		/* An extra copy of north */
 		   { -1, 1,   0, 1 }
 	   };
 	for ( dir = west, part = 1; ; )
 	   {	register dir_descr *pd = &nesw[(int)dir];
 		int dx = pd->dx, dy = pd->dy;
 		int delta;
 		if ( dir == west )
 		   {	/* This is the only case that has to check */
 			/* for the end of a subpath. */
 			if ( *cptr == 2 ) return 0;
 			*cptr = 2;
 		   }
 		delta = pd->ty * w2 + pd->tx;
 		if ( cptr[delta] )	/* go counter-clockwise */
 		   {	cptr += delta;
 			add_deltas(out, dx, dy, 1 - part);
 			add_deltas(out, pd->tx, pd->ty, outline_scale - 1);
 			dir = (direction)(((int)dir - 1) & 3);
 			part = outline_scale - 1;
 			continue;
 		   }
 		delta = dy * w2 + dx;
 		if ( !cptr[delta] )	/* go clockwise */
 		   {	add_deltas(out, dx, dy, outline_scale - 1 - part);
 			add_deltas(out, dx + pd[1].dx, dy + pd[1].dy, 1);
 			dir = (direction)(((int)dir + 1) & 3);
 			part = 1;
 			continue;
 		   }
 		cptr += delta;		/* go in same direction */
 		add_deltas(out, dx, dy, outline_scale);
 	   }
 }

 /* Add a (dx, dy) pair to the path being formed. */
 /* Accumulate successive segments in the same direction. */
 private int
 add_dxdy(register status *out, int dx, int dy, int count)
 {	int code;
 	if ( count != 0 )
 	   {	if ( dx == out->dx && dy == out->dy )
 			out->count += count;
 		else
 		   {	if ( out->count != 0 )
 				put_deltas(out, out->dx * out->count,
 					   out->dy * out->count, 0);
 			out->dx = dx, out->dy = dy;
 			out->count = count;
 		   }
 	   }
 	return 0;
 }

 /* Encode a (dx, dy) pair onto the path. */
 /* If there isn't enough space, return -1. */
 private int
 put_dxdy(register status *out, int dx, int dy, int moving)
 {	int code;
 	/* We do the arithmetic in the 1/4-pixel coordinate system, */
 	/* and then transform the result, to avoid accumulating */
 	/* rounding errors. */
 	int npx = out->px + dx, npy = out->py + dy;
 	gs_point npt;
 	int ncpx, ncpy;
 	int cdx, cdy;
 	gs_distance_transform((floatp)npx, (floatp)npy, &out->ifm, &npt);
 	ncpx = round_coord(npt.x);
 	ncpy = round_coord(npt.y);
 	cdx = ncpx - out->cpx;
 	cdy = ncpy - out->cpy;
 #ifdef DEBUG
 if ( gs_debug['0'] )
 	printf("[0]  pxy=(%d,%d)+(%d,%d)  cpxy=(%d,%d)+(%d,%d)\n",
 		out->px, out->py, dx, dy, out->cpx, out->cpy, cdx, cdy);
 #endif
 	if ( cdx != 0 || cdy == 0 )	/* encode dx if needed */
 	  if ( (code = put_int(out, cdx)) < 0 ) return code;
 	if ( cdy != 0 )			/* encode dy if needed */
 	  if ( (code = put_int(out, cdy)) < 0 ) return code;
 	if ( out->next == out->limit ) return_error(gs_error_limitcheck);
 	*out->next++ = (byte)
 		(cdy == 0 ?		/* use hmove/lineto */
 			(moving ? c_hmoveto : c_hlineto) :
 		cdx == 0 ?		/* use vmove/lineto */
 			(moving ? c_vmoveto : c_vlineto) :
 		(moving ? c_rmoveto : c_rlineto));
 	out->px = npx, out->py = npy;
 	out->cpx = ncpx, out->cpy = ncpy;
 	return 0;
 }

 /* Round a floating point coordinate.  If it is out of range, */
 /* return a limiting value. */
 private int
 round_coord(floatp v)
 {	long c = (long)(v + 0.5);
 	return( c > 0x7fff ? 0x7fff :
 		c < -0x7fff ? -0x7fff :
 		(int)c );
 }
 /* Encode a single number in Type 1 representation. */
 private int
 put_int(status *out, register int v)
 {
 #define min_enc_num1 ((c_min_num - c_max_num1) / 2)
 #define max_enc_num1 ((c_max_num1 - c_min_num) / 2)
 #define min_enc_num2 (max_enc_num1 + 1)
 #define max_enc_num2 (min_enc_num2 + (c_max_num2 - c_max_num1) * 256 - 1)
 #define min_enc_num3 (-max_enc_num2)
 #define max_enc_num3 (-min_enc_num2)
 	register byte *ptr = out->next;
 	if ( ptr + 5 > out->limit )	/* conservative test is faster */
 		return_error(gs_error_limitcheck);
 	if ( v >= min_enc_num1 && v <= max_enc_num1 )
 		*ptr++ = v - min_enc_num1 + c_min_num;
 	else if ( v >= min_enc_num2 && v <= max_enc_num2 )
 	   {	v -= min_enc_num2;
 		*ptr++ = (v >> 8) + c_max_num1+1;
 		*ptr++ = v & 0xff;
 	   }
 	else if ( v >= min_enc_num3 && v <= max_enc_num3 )
 	   {	v = -(v - max_enc_num3);
 		*ptr++ = (v >> 8) + c_max_num2+1;
 		*ptr++ = v & 0xff;
 	   }
 	else
 	   {	*ptr++ = c_max_num3+1;
 		*ptr++ = ((long)v >> 24) & 0xff;
 		*ptr++ = ((long)v >> 16) & 0xff;
 		*ptr++ = (v >> 8) & 0xff;
 		*ptr++ = v & 0xff;
 	   }
 	out->next = ptr;
 	return 0;
 }
	/* Copyright (C) 1989, 1990 Aladdin Enterprises. All rights reserved.
	Distributed by Free Software Foundation, Inc.

	This file is part of Ghostscript.

	Ghostscript is distributed in the hope that it will be useful, but
	WITHOUT ANY WARRANTY. No author or distributor accepts responsibility
	to anyone for the consequences of using it or for whether it serves any
	particular purpose or works at all, unless he says so in writing. Refer
	to the Ghostscript General Public License for full details.

	Everyone is granted permission to copy, modify and redistribute
	Ghostscript, but only under the conditions described in the Ghostscript
	General Public License. A copy of this license is supposed to have been
	given to you along with Ghostscript so you can know your rights and
	responsibilities. It should be in a file named COPYING. Among other
	things, the copyright notice and this notice must be preserved on all
	copies. */

	/* gsim2out.c */
	/* Image to outline conversion for GhostScript library */
	#include "gx.h"
	#include "memory_.h"
	#include "gserrors.h"
	#include "gsmatrix.h"
	#include "gsstate.h"
	#include "gscoord.h"
	#include "gxfixed.h"
	#include "gxtype1.h"

	/*
	* Convert a bitmap image to an outline (path) representation.
	* The outline representation is in Adobe Type 1 CharString format.
	* See ghost.doc for more details.
	*/

	/* Define the state of the conversion process. */
	typedef struct {
	/* The following are set at the beginning of the conversion. */
	gs_matrix ifm; /* inverse of (CTM */
	/* scaled by width/height * 4). */
	byte limit; / stop output here */
	int ox, oy; /* X/Y pixel offset of char origin */
	/* The following are updated dynamically. */
	byte next; / next byte goes here */
	int px, py; /* X/Y position at start of run */
	int cpx, cpy; /* px/py in character coordinates */
	int dx, dy; /* X/Y increment of current run */
	int count; /* # of steps in current run */
	} status;

	/* Define the scaling for the path tracer. */
	#define outline_scale 4

	/* Forward declarations */
	private int round_coord(P1(floatp));
	private int put_int(P2(status *, int));
	private void fill_cells(P4(byte , byte , int, int));
	private int trace_cells(P4(byte , int, int, status ));

	/*
	* gs_type1imagepath encodes an image into a byte string supplied
	* by the caller. If the string is not big enough, the procedure
	* returns gs_error_limitcheck. Otherwise, the procedure returns
	* the actual number of bytes of data stored.
	*/
	int
	gs_type1imagepath(gs_state pgs, byte data, int width, int height,
	floatp wx, floatp wy, floatp origin_x, floatp origin_y,
	byte *str, uint maxlen)
	{ uint csize;
	byte *cells;
	status stat;
	status *out = &stat;
	int lsbx;
	int iwx, iwy, ilsbx, ilsby;
	int code;
	/* Construct the coordinate transformation. */
	{ float hsc = height * outline_scale;
	gs_matrix mat;
	gs_currentmatrix(pgs, &stat.ifm);
	#ifdef DEBUG
	if ( gs_debug['0'] )
	printf("[0]ctm=[%g %g %g %g %g %g]\n",
	stat.ifm.xx, stat.ifm.xy, stat.ifm.yx, stat.ifm.yy,
	stat.ifm.tx, stat.ifm.ty);
	#endif
	if ( (code = gs_make_scaling(hsc, hsc, &mat)) < 0 \|\|
	(code = gs_matrix_multiply(&mat, &stat.ifm, &stat.ifm)) < 0 \|\|
	(code = gs_matrix_invert(&stat.ifm, &stat.ifm)) < 0
	)
	return code;
	}
	/* Allocate and fill in the cell matrix. */
	csize = (width + 2) * (height + 2);
	cells = (byte *)gs_malloc(csize, 1, "gsim2out cells");
	if ( cells == 0 ) return_error(gs_error_VMerror);
	fill_cells(cells, data, width, height);
	/* Initialize the rest of the state. */
	stat.next = str;
	stat.limit = str + maxlen;
	/* Determine the left side bearing by looking for */
	/* the leftmost column with any 1-bits. */
	for ( lsbx = 0; lsbx < width; lsbx++ )
	{ int y;
	for ( y = 1; y <= height; y++ )
	if ( cells[y * (width + 2) + lsbx + 1] ) goto xit;
	}
	xit: /* Encode the origin, width, and side bearing. */
	{ gs_point opt, wpt, lsbpt;
	if ( (code = gs_distance_transform(origin_x * outline_scale,
	origin_y * outline_scale,
	&stat.ifm, &opt)) < 0 \|\|
	(code = gs_distance_transform(wx * outline_scale,
	wy * outline_scale,
	&stat.ifm, &wpt)) < 0 \|\|
	(code = gs_distance_transform((lsbx - origin_x) *
	outline_scale, (floatp)0,
	&stat.ifm, &lsbpt)) < 0
	)
	return code;
	stat.ox = round_coord(opt.x);
	stat.oy = round_coord(opt.y);
	iwx = round_coord(wpt.x);
	iwy = round_coord(wpt.y);
	ilsbx = round_coord(lsbpt.x);
	ilsby = round_coord(lsbpt.y);
	#ifdef DEBUG
	if ( gs_debug['0'] )
	{ int cy, cx;
	byte *cp = data;
	printf("[0]w=%d h=%d oxy=(%g,%g) wxy=(%g,%g)\n",
	width, height, origin_x, origin_y, wx, wy);
	printf(" io=(%d,%d) iw=(%d,%d) ilsb=(%d,%d)\n",
	stat.ox, stat.oy, iwx, iwy, ilsbx, ilsby);
	for ( cy = 0; cy < height; cy++ )
	{ printf("[0]%3d ", cy);
	for ( cx = 0; cx < width; cx += 8 )
	printf("%02x", (int)*cp++);
	putchar('\n');
	}
	}
	#endif
	if ( (code = put_int(out, ilsbx)) < 0 ) return code;
	if ( iwy != 0 \|\| ilsby != 0 )
	{ if ( (code = put_int(out, ilsby)) < 0 \|\|
	(code = put_int(out, iwx)) < 0 \|\|
	(code = put_int(out, iwy)) < 0
	)
	return code;
	if ( stat.next + 2 > stat.limit )
	return_error(gs_error_limitcheck);
	*stat.next++ = (byte)c_escape;
	*stat.next++ = (byte)ce_sbw;
	}
	else
	{ if ( (code = put_int(out, iwx)) < 0 ) return code;
	if ( stat.next + 1 > stat.limit )
	return_error(gs_error_limitcheck);
	*stat.next++ = (byte)c_hsbw;
	}
	}
	/* Since all further movements are relative, we can account */
	/* for the origin by simply setting px/py to the lsb, */
	/* and cpx/cpy to the lsb plus the origin. */
	stat.px = (lsbx * outline_scale);
	stat.py = (int)(origin_y * outline_scale);
	stat.cpx = ilsbx + stat.ox;
	stat.cpy = ilsby + stat.oy;
	/* Trace the outline of the cells. */
	code = trace_cells(cells, width, height, out);
	gs_free((char *)cells, csize, 1, "gsim2out cells");
	if ( code < 0 ) return code;
	if ( stat.next >= stat.limit ) return_error(gs_error_limitcheck);
	*stat.next++ = (byte)c_endchar;
	return stat.next - str;
	}

	/* Fill the cell matrix with the image being traced. */
	/* The cell matrix has a row and column of zero padding on each side, */
	/* so we don't have to check for boundary conditions all the time. */
	/* Note that the image data are in PostScript / Ghostscript standard */
	/* order (left to right, top row first), but the cells are stored */
	/* bottom row first. */
	private void
	fill_cells(byte cells, byte data, int width, int height)
	{ int y;
	byte *dptr = data - 1;
	byte cptr = cells + (width + 2) height + 1;
	memset(cells, 0, (width + 2) * (height + 2));
	for ( y = 0; y < height; y++ )
	{ register int mask = 0;
	register int b;
	register int x;
	for ( x = 0; x < width; x++, mask >>= 1, cptr++ )
	{ if ( mask == 0 ) mask = 0x80, b = *++dptr;
	if ( b & mask ) *cptr = 1;
	}
	cptr -= width * 2 + 2; /* back up 1 row */
	}
	}

	/* Trace the cells to form an outline. The trace goes in clockwise */
	/* order, always starting by going west along a bottom edge. */
	/* All the subsidiary routines return 0 on success, */
	/* -1 if the output buffer overflowed. */
	private int trace_from(P3(status , byte , int));
	private int add_dxdy(P4(status *, int, int, int));
	#define add_deltas(s, dx, dy, n)\
	if ( (code = add_dxdy(s, dx, dy, n)) < 0 ) return code
	private int put_dxdy(P4(status *, int, int, int));
	#define put_deltas(s, dx, dy, moving)\
	if ( (code = put_dxdy(s, dx, dy, moving)) < 0 ) return code
	private int
	trace_cells(byte cells, int width, int height, register status out)
	{ byte *cptr;
	int code;
	for ( cptr = cells + (width + 2) * (height + 1) - 2;
	cptr >= cells; cptr--
	)
	{ if ( *cptr == 1 && cptr[-(width+2)] == 0 )
	{ /* Found a starting point */
	int x = (cptr-cells) % (width+2) - 1;
	int y = (cptr-cells) / (width+2) - 1;
	put_deltas(out,
	x * outline_scale + 1 - out->px,
	y * outline_scale - out->py,
	1);
	out->count = 0;
	if ( (code = trace_from(out, cptr, width)) < 0 )
	return code;
	if ( out->next >= out->limit )
	return_error(gs_error_limitcheck);
	*out->next++ = (byte)c_closepath;
	}
	}
	return 0;
	}

	/* Trace a path */
	private int
	trace_from(register status out, byte cptr, int width)
	{ typedef enum { /* must be in this order */
	north = 0, east = 1, south = 2, west = 3
	} direction;
	direction dir;
	int w2 = width + 2; /* actual width of cell rows */
	int part; /* how far along edge we are */
	int code;
	/* Movement tables */
	typedef struct {
	short tx, ty; /* relative index of first cell */
	/* to test (counter-clockwise move) */
	short dx, dy; /* continue in same direction */
	} dir_descr;
	static dir_descr nesw[4+1] =
	{ /* Going north (along a western edge) */
	{ -1, 1, 0, 1 },
	/* Going east (along a northern edge) */
	{ 1, 1, 1, 0 },
	/* Going south (along an eastern edge) */
	{ 1, -1, 0, -1 },
	/* Going west (along a southern edge) */
	{ -1, -1, -1, 0 },
	/* An extra copy of north */
	{ -1, 1, 0, 1 }
	};
	for ( dir = west, part = 1; ; )
	{ register dir_descr *pd = &nesw[(int)dir];
	int dx = pd->dx, dy = pd->dy;
	int delta;
	if ( dir == west )
	{ /* This is the only case that has to check */
	/* for the end of a subpath. */
	if ( *cptr == 2 ) return 0;
	*cptr = 2;
	}
	delta = pd->ty * w2 + pd->tx;
	if ( cptr[delta] ) /* go counter-clockwise */
	{ cptr += delta;
	add_deltas(out, dx, dy, 1 - part);
	add_deltas(out, pd->tx, pd->ty, outline_scale - 1);
	dir = (direction)(((int)dir - 1) & 3);
	part = outline_scale - 1;
	continue;
	}
	delta = dy * w2 + dx;
	if ( !cptr[delta] ) /* go clockwise */
	{ add_deltas(out, dx, dy, outline_scale - 1 - part);
	add_deltas(out, dx + pd[1].dx, dy + pd[1].dy, 1);
	dir = (direction)(((int)dir + 1) & 3);
	part = 1;
	continue;
	}
	cptr += delta; /* go in same direction */
	add_deltas(out, dx, dy, outline_scale);
	}
	}

	/* Add a (dx, dy) pair to the path being formed. */
	/* Accumulate successive segments in the same direction. */
	private int
	add_dxdy(register status *out, int dx, int dy, int count)
	{ int code;
	if ( count != 0 )
	{ if ( dx == out->dx && dy == out->dy )
	out->count += count;
	else
	{ if ( out->count != 0 )
	put_deltas(out, out->dx * out->count,
	out->dy * out->count, 0);
	out->dx = dx, out->dy = dy;
	out->count = count;
	}
	}
	return 0;
	}

	/* Encode a (dx, dy) pair onto the path. */
	/* If there isn't enough space, return -1. */
	private int
	put_dxdy(register status *out, int dx, int dy, int moving)
	{ int code;
	/* We do the arithmetic in the 1/4-pixel coordinate system, */
	/* and then transform the result, to avoid accumulating */
	/* rounding errors. */
	int npx = out->px + dx, npy = out->py + dy;
	gs_point npt;
	int ncpx, ncpy;
	int cdx, cdy;
	gs_distance_transform((floatp)npx, (floatp)npy, &out->ifm, &npt);
	ncpx = round_coord(npt.x);
	ncpy = round_coord(npt.y);
	cdx = ncpx - out->cpx;
	cdy = ncpy - out->cpy;
	#ifdef DEBUG
	if ( gs_debug['0'] )
	printf("[0] pxy=(%d,%d)+(%d,%d) cpxy=(%d,%d)+(%d,%d)\n",
	out->px, out->py, dx, dy, out->cpx, out->cpy, cdx, cdy);
	#endif
	if ( cdx != 0 \|\| cdy == 0 ) /* encode dx if needed */
	if ( (code = put_int(out, cdx)) < 0 ) return code;
	if ( cdy != 0 ) /* encode dy if needed */
	if ( (code = put_int(out, cdy)) < 0 ) return code;
	if ( out->next == out->limit ) return_error(gs_error_limitcheck);
	*out->next++ = (byte)
	(cdy == 0 ? /* use hmove/lineto */
	(moving ? c_hmoveto : c_hlineto) :
	cdx == 0 ? /* use vmove/lineto */
	(moving ? c_vmoveto : c_vlineto) :
	(moving ? c_rmoveto : c_rlineto));
	out->px = npx, out->py = npy;
	out->cpx = ncpx, out->cpy = ncpy;
	return 0;
	}

	/* Round a floating point coordinate. If it is out of range, */
	/* return a limiting value. */
	private int
	round_coord(floatp v)
	{ long c = (long)(v + 0.5);
	return( c > 0x7fff ? 0x7fff :
	c < -0x7fff ? -0x7fff :
	(int)c );
	}
	/* Encode a single number in Type 1 representation. */
	private int
	put_int(status *out, register int v)
	{
	#define min_enc_num1 ((c_min_num - c_max_num1) / 2)
	#define max_enc_num1 ((c_max_num1 - c_min_num) / 2)
	#define min_enc_num2 (max_enc_num1 + 1)
	#define max_enc_num2 (min_enc_num2 + (c_max_num2 - c_max_num1) * 256 - 1)
	#define min_enc_num3 (-max_enc_num2)
	#define max_enc_num3 (-min_enc_num2)
	register byte *ptr = out->next;
	if ( ptr + 5 > out->limit ) /* conservative test is faster */
	return_error(gs_error_limitcheck);
	if ( v >= min_enc_num1 && v <= max_enc_num1 )
	*ptr++ = v - min_enc_num1 + c_min_num;
	else if ( v >= min_enc_num2 && v <= max_enc_num2 )
	{ v -= min_enc_num2;
	*ptr++ = (v >> 8) + c_max_num1+1;
	*ptr++ = v & 0xff;
	}
	else if ( v >= min_enc_num3 && v <= max_enc_num3 )
	{ v = -(v - max_enc_num3);
	*ptr++ = (v >> 8) + c_max_num2+1;
	*ptr++ = v & 0xff;
	}
	else
	{ *ptr++ = c_max_num3+1;
	*ptr++ = ((long)v >> 24) & 0xff;
	*ptr++ = ((long)v >> 16) & 0xff;
	*ptr++ = (v >> 8) & 0xff;
	*ptr++ = v & 0xff;
	}
	out->next = ptr;
	return 0;
	}