/* $XConsortium: lines.c,v 1.2 91/10/10 11:18:21 rws Exp $ */
/* Copyright International Business Machines, Corp. 1991
 * All Rights Reserved
 * Copyright Lexmark International, Inc. 1991
 * All Rights Reserved
 *
 * License to use, copy, modify, and distribute this software and its
 * documentation for any purpose and without fee is hereby granted,
 * provided that the above copyright notice appear in all copies and that
 * both that copyright notice and this permission notice appear in
 * supporting documentation, and that the name of IBM or Lexmark not be
 * used in advertising or publicity pertaining to distribution of the
 * software without specific, written prior permission.
 *
 * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF
 * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY
 * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
 * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS.  THE ENTIRE RISK AS TO THE
 * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT
 * OR MAINTAIN, BELONGS TO THE LICENSEE.  SHOULD ANY PORTION OF THE
 * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE
 * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION.  IN NO EVENT SHALL
 * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
 * THIS SOFTWARE.
 */

/*
 * LINES Module - Rasterizing Lines
 *
 * &author. Duaine W. Pryor, Jr. and Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com)
 */

#ifndef T1GST
#include "global.h"
#endif

static void Bresenham(pel *edgeP, fractpel x1, fractpel y1, fractpel x2, fractpel y2);

/*
StepLine() - Produces Run Ends for a Line After Checks

The main work is done by Bresenham(); here we just perform checks and
get the line so that its Y direction is always increasing:
*/

void t1_StepLine(
		struct T1GlyphEngine *engine,
		struct region *R,		/* region being built */
		fractpel x1,
		fractpel y1,			/* starting point */
		fractpel x2,
		fractpel y2)			/* ending point */
{
	fractpel dy;

//	IfTrace4((engine->LineDebug > 0), ".....StepLine: (%p,%p) to (%p,%p)\n",
	IfTrace4((engine->LineDebug > 0), ".....StepLine: (%ld,%ld) to (%ld,%ld)\n",
		 x1, y1, x2, y2);

	dy = y2 - y1;

/*
We execute the "GOING_TO" macro to call back the REGIONS module, if
necessary (like if the Y direction of the edge has changed):
*/
	GOING_TO(engine, R, x1, y1, x2, y2, dy);

	if (dy == 0)
		return;

	if (dy < 0)
		Bresenham(R->edge, x2, y2, x1, y1);
	else
		Bresenham(R->edge, x1, y1, x2, y2);
	return;
}


/*
Bresenham() - Actually Produces Run Ends

This routine runs a Bresenham line-stepping
algorithm.  See, for example, Newman and Sproul, :hp1/Principles
of Interactive Computer Graphics/, pp. 25-27.
When we enter this, we
are guaranteed that dy is positive.
We'd like to work in 8 bit precision, so we'll define some macros and
constants to let us do that:
*/

#define PREC 8			/* we'll keep fraction pels in 8 bit precision  */
/*
RoundFP() rounds down by 'b' bits:
*/
#define  RoundFP(xy,b)   (((xy)+(1<<((b)-1)))>>(b))

/*
TruncFP() truncates down by 'b' bits:
*/
#define  TruncFP(xy,b)   ((xy)>>(b))


static void Bresenham(
		pel *edgeP,				/* pointer to top of list (y==0) */
		fractpel x1,
		fractpel y1,			/* starting point on line */
		fractpel x2,
		fractpel y2)			/* ending point on the line (down) */
{
	long dx, dy;	/* change in x and y, in my own precision       */
	long x, y;	/* integer pel starting point                   */
	int count;	/* integer pel delta y                          */
	long d;	/* the Bresenham algorithm error term           */

	x1 = TruncFP(x1, FRACTBITS - PREC);
	y1 = TruncFP(y1, FRACTBITS - PREC);
	x2 = TruncFP(x2, FRACTBITS - PREC);
	y2 = TruncFP(y2, FRACTBITS - PREC);

	dx = x2 - x1;
	dy = y2 - y1;
/*
Find the starting x and y integer pel coordinates:
*/

	x = RoundFP(x1, PREC);
	y = RoundFP(y1, PREC);
	edgeP += y;
	count = RoundFP(y2, PREC) - y;
/*------------------------------------------------------------------*/
/* Force dx to be positive so that dfy will be negative             */
/*       this means that vertical moves will decrease d             */
/*------------------------------------------------------------------*/

// TetiSoft: Don't forget very small horizontal lines
//#define DRAWEVENSMALLPOINTS
#ifdef DRAWEVENSMALLPOINTS
		if(count == 0)
		{
			count++;
			kprintf("-------- Bresenham count was 0\n");
		}
#endif

	if (dx < 0)
	{
		dx = -dx;
#define P PREC
		d = (dy * (x1 - (x << P) + (1 << (P - 1))) - dx * ((y << P) - y1 + (1 << (P - 1)))) >> P;
#undef P
		while (--count >= 0)
		{
			while (d < 0)
			{
				--x;
				d += dy;
			}
			*(edgeP++) = x;
			d -= dx;
		}
	}
	else
		/* positive dx */
	{
#define P PREC
		d = (dy * ((x << P) - x1 + (1 << (P - 1))) - dx * ((y << P) - y1 + (1 << (P - 1)))) >> P;
#undef P
		while (--count >= 0)
		{
			while (d < 0)
			{
				++x;
				d += dy;
			}
			*(edgeP++) = x;
			d -= dx;
		}
	}
}