⟦52067bedc⟧

TextFile

/* Copyright (C) 1989 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.  */

/* gxim2out.c */
/* Image to outline conversion for GhostScript library */
#include <setjmp.h>
#include "gx.h"
#include "malloc_.h"
#include "gserrors.h"

/*
 * Convert a bitmap image to an outline (path) representation.
 * The outline representation is a byte string made up of subpaths.
 * Each subpath, in turn, is composed of short line segments.
 *
 * Each line segment is normally represented by a single byte,
 * (dx + 8) * 16 + (dy + 8), where -7 <= dx <= 7, -7 <= dy <= 7.
 * If dx or dy is -8 (i.e. coded as a zero), then the actual
 * delta value follows the packed byte: the value is encoded as
 * a single byte biased by 128.  If dx and dy are both zero
 * (i.e., coded as 8), this marks the end of a subpath.
 * The first "line segment" of a subpath is a moveto rather than
 * a lineto, and each subpath ends with an implicit closepath.
 */

/* Outlines are scaled by a constant factor */
extern int gs_addcharpath_log2_scale;	/* must be 2! */
private int outline_scale;

/* Forward declarations */
private void fill_cells(P4(byte *, byte *, int, int));
private int trace_cells(P5(byte *, uint, byte *, int, int));

/*
 * gs_imagecharpath 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_imagecharpath(byte *data, int width, int height,
  byte *str, uint maxlen)
{	byte *cells = (byte *)malloc((width + 2) * (height + 2));
	int len;
	outline_scale = 1 << gs_addcharpath_log2_scale;
	if ( cells == 0 ) return_error(gs_error_VMerror);
	fill_cells(cells, data, width, height);
	len = trace_cells(str, maxlen, cells, width, height);
	free(cells);
	return len;
}

/* 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 x, 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;
		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. */
typedef struct {
	byte *next;			/* next byte goes here */
	byte *limit;			/* stop output here */
	int dx;				/* X increment of current run */
	int dy;				/* Y increment of current run */
	int count;			/* # of steps in current run */
	jmp_buf exit;			/* error exit */
} status;
private void trace_from(P3(status *, byte *, int));
private void add_deltas(P4(status *, int, int, int));
private void put_deltas(P3(status *, int, int));
private int
trace_cells(byte *str, uint maxlen, byte *cells, int width, int height)
{	status out;
	byte *cptr;
	if ( setjmp(out.exit) )
	   {	/* Overflow, return error code */
		return gs_error_limitcheck;
	   }
	out.next = str;
	out.limit = str + maxlen;
	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,
				   y * outline_scale);
			out.count = 0;
			trace_from(&out, cptr, width);
			add_deltas(&out, 0, 0, 1);	/* force end of line */
			put_deltas(&out, 0, 0);	/* encode end of subpath */
		   }
	   }
	return out.next - str;
}

/* Trace a path */
private void
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 */
	/* 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;
			*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);
	   }
#undef move
}

/* Add a (dx, dy) pair to the path being formed. */
/* Accumulate successive segments in the same direction. */
private void
add_deltas(register status *out, int dx, int dy, int count)
{	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);
			out->dx = dx, out->dy = dy;
			out->count = count;
		   }
	   }
}

/* Encode a (dx, dy) pair onto the path. */
/* If there isn't enough space, do a longjmp. */
private void
put_deltas(register status *out, int dx, int dy)
{	byte *ptr = out->next;
	byte encoding;
	if ( ptr + 3 > out->limit )	/* conservative test is faster */
		longjmp(out->exit, 1);
	encoding = ((dx >= -7 && dx <= 7 ? dx + 8 : 0) << 4) +
		   (dy >= -7 && dy <= 7 ? dy + 8 : 0);
	*ptr++ = encoding;
	if ( encoding < 0x10 ) *ptr++ = dx + 0x80;
	if ( !(encoding & 0xf) ) *ptr++ = dy + 0x80;
	out->next = ptr;
}
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦52067bedc⟧ TextFile

Derivation

TextFile
