[net.sources] PCB part 6 of 10

agn@cmu-cs-unh.ARPA (Andreas Nowatzyk) (08/11/85)

#
# type    sh /usru0/agn/pcb/distr/../usenet/part6   to unpack this archive.
#
echo extracting pleer.c...
cat >pleer.c <<'!E!O!F!'
/***************************************************************\
*								*
*	PCB program						*
*								*
*	Lee Router section  (main part: common code)		*
*								*
*	(c) 1985		A. Nowatzyk			*
*								*
\***************************************************************/

#include "pparm.h"
#include "pcdst.h"
#define mainleer		/* this is the main section	 */
#include "pleer.h"


get_rtprm ()			/* get route parameter		 */
{
    RT_sel = getint ("Select router (0=full, 1=confined)", 0, 1, RT_sel);

    if (RT_sel) {
        rt_str = getint("Preference start (0=alt, 1=Componet-, 2=Soder side)",
			0, 2, rt_str);
	K1 = getint ("Max wrong distance for singe side runs", 0, 100, K1);
	K2 = getint ("Border size for single side traces", 1, 100, K2);
	K3 = getint ("Border size for multiple side trcaes", 1, K3max, K3);
	K4 = getint ("Min length for multiple via hole traces", 20, 1000, K4);
	K5 = getint ("Min length for each segment", K3 + 1, 1000, K5);
	K6 = getint ("Max number of via holes for one connection", 2, 10, K6);
	K7 = getint ("Max level for L-routes retries", 0, 10, K7);
	K8 = -getint ("Bonus for rectangular vias", -20, 20, -K8);}
    else {
	C1 = getint ("Boarder size for routing area", 1, 100, C1);
	C2 = getint ("Max path in wrong direction", 1, 100, C2);
	C3 = getint ("Max number of via holes in one segment", 0, 10, C3);
	C4 = getint ("Penalty for HV via holes", 0, 50, C4);
	C5 = getint ("Penalty for D via hols", C4, 50, C5);
	C7 = getint ("Penalty progression for via hols", 0, 50, C7);
	C6 = 2 * getint ("Via hole alignment", 1, 8, C6 / 2);
    }
}

set_rtps (n)			/* set routing parameters	 */
    int n;
/**********************************************************************\
* 								       *
*  n denotes a standart set of routing parameter. These parameters     *
*  increase the search space with increasing n. A larger search space  *
*  needs more CPU time and produces more obscure result.	       *
* 								       *
\**********************************************************************/
{
#define nmax 4			/* tere are thre sets defined	 */
    static struct rtp {
	int c1, c2, c3, c4, c5, c6, c7;
    } rtps[nmax] = {
	{4, 8, 0, 10, 15, 8, 9},
	{10, 8, 1, 30, 45, 8, 9},
	{15, 12, 2, 20, 30, 4, 6},
	{25, 16, 4, 10, 20, 2, 3}
    };

    if (n < 0 || n >= nmax) {
	printf ("set_rtps: Unkown parameter set - ignored\n");
	return;
    }

    RT_sel = 0;			/* use full router		 */

    C1 = rtps[n].c1;
    C2 = rtps[n].c2;
    C3 = rtps[n].c3;
    C4 = rtps[n].c4;
    C5 = rtps[n].c5;
    C6 = rtps[n].c6;
    C7 = rtps[n].c7;
}

cr_gmaze (x1, y1, x2, y2, b)	/* create a good maze		 */
    int x1, y1, x2, y2, b;
{   register int i;

    if (x1 > x2) {		/* sort x			 */
	i = x1;
	x1 = x2;
	x2 = i;
    }
    if (y1 > y2) {		/* sort y			 */
	i = y1;
	y1 = y2;
	y2 = i;
    }
    x1 -= b;			/* add border			 */
    y1 -= b;
    x2 += b;
    y2 += b;
    x1 = (x1 < 0) ? 0 : x1;	/* bitmap clipping		 */
    y1 = (y1 < 0) ? 0 : y1;
    x2 = (x2 > V.BSX) ? V.BSX : x2;
    y2 = (y2 > V.BSY) ? V.BSY : y2;
    cr_maze (x1, y1, x2 - x1 + 1, y2 - y1 + 1);
}

cr_maze (px, py, qx, qy)	/* create maze (aux. bit map)	 */
    int px, py, qx, qy;
{
    static int tab1[256] = {
/*************************************************************************\
* 									  *
*  Pixel conversion table: indexed by an element of pcb[][], it returns:  *
*  MSB ===---===---=== LSB						  *
*      00.00.00.00.00.       These bits are allways 0			  *
*      ..............1       (1)   : selected hole	slahb		  *
*      ...........1...       (8)   : invalid side 1	ivs1b		  *
*      ........1......       (64)  : invalid side 2	ivs2b		  *
*      .....1.........       (512) : selected side 1	sls1b		  *
*      ..1............       (4096): selected side 2	sls2b		  *
* 									  *
\*************************************************************************/
		   0,    8,   64,   72,   72,   72,   72,   72,
		  72,   72,   72,   72,   72,   72,   72,   72,
		  72,   72,   72,   72,   72,   72,   72,   72,
		  72,   72,   72,   72,   72,   72,   72,   72,
		   0,    8,   64,   72,   72,   72,   72,   72,
		  72,   72,   72,   72,   72,   72,   72,   72,
		  72,   72,   72,   72,   72,   72,   72,   72,
		  72,   72,   72,   72,   72,   72,   72,   72,
		   0,    8,   64,   72,   72,   72,   72,   72,
		  72,   72,   72,   72,   72,   72,   72,   72,
		  72,   72,   72,   72,   72,   72,   72,   72,
		  72,   72,   72,   72,   72,   72,   72,   72,
		   0,    8,   64,   72,   72,   72,   72,   72,
		  72,   72,   72,   72,   72,   72,   72,   72,
		  72,   72,   72,   72,   72,   72,   72,   72,
		  72,   72,   72,   72,   72,   72,   72,   72,
		   0,  512, 4096,  576,    1,    1,    1,    1,
		   1,    1,    1,    1,    1,    1,    1,    1,
		  72,   72,   72,   72,   72,   72,   72,   72,
		  72,   72,   72,   72,   72,   72,   72,   72,
		   0,  512, 4096, 4104,    1,    1,    1,    1,
		   1,    1,    1,    1,    1,    1,    1,    1,
		  72,   72,   72,   72,   72,   72,   72,   72,
		  72,   72,   72,   72,   72,   72,   72,   72,
		   0,  512, 4096,  576,    1,    1,    1,    1,
		   1,    1,    1,    1,    1,    1,    1,    1,
		  72,   72,   72,   72,   72,   72,   72,   72,
		  72,   72,   72,   72,   72,   72,   72,   72,
		   0,  512, 4096, 4104,    1,    1,    1,    1,
		   1,    1,    1,    1,    1,    1,    1,    1,
		  72,   72,   72,   72,   72,   72,   72,   72,
		  72,   72,   72,   72,   72,   72,   72,   72  };

    static int tab2[512] = {
/****************************************************************************\
* 									     *
*  DDE-table: if indexed by an 9 bit integer LSB<876543210>LSB, it returns:  *
*  MSB ===---=== LSB							     *
*      00.00.00.      These bits are allways 0				     *
*      ........1      (1) : if  bit0 & bit1 & bit2			     *
*      .....1...      (8) : if  bit3 | bit4 | bit5			     *
*      ..1......      (64): if  bit6 | bit7 | bit8			     *
* 									     *
\****************************************************************************/
		 0, 0, 0, 0, 0, 0, 0, 1, 8, 8, 8, 8, 8, 8, 8, 9,
		 8, 8, 8, 8, 8, 8, 8, 9, 8, 8, 8, 8, 8, 8, 8, 9,
		 8, 8, 8, 8, 8, 8, 8, 9, 8, 8, 8, 8, 8, 8, 8, 9,
		 8, 8, 8, 8, 8, 8, 8, 9, 8, 8, 8, 8, 8, 8, 8, 9,
		64,64,64,64,64,64,64,65,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		64,64,64,64,64,64,64,65,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		64,64,64,64,64,64,64,65,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		64,64,64,64,64,64,64,65,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		64,64,64,64,64,64,64,65,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		64,64,64,64,64,64,64,65,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		64,64,64,64,64,64,64,65,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73,
		72,72,72,72,72,72,72,73,72,72,72,72,72,72,72,73  };

    static int tab3[128] = {
/***********************************************************\
* 							    *
*  decision table:					    *
*  Input:                 MSB ======= LSB		    *
*                             .x..x..      Don't care bits  *
* 			      1......      invalid side 2   *
*                             ..1....      selected side 2  *
*                             ...1...      invalid side 1   *
*                             .....1.      selected side 1  *
*                             ......1      selected hole    *
* 							    *
*  Output:               MSB ----==== LSB		    *
* 			     ....tttt      side 1 token	    *
* 			     tttt....      side 2 token	    *
* 							    *
\***********************************************************/
		 0,34,50,34, 0,34,50,34, 1,34,50,34, 1,34,50,34,
		35,34,34,34,35,34,34,34,33,34,34,34,33,34,34,34,
		 0,34,50,34, 0,34,50,34, 1,34,50,34, 1,34,50,34,
		35,34,34,34,35,34,34,34,33,34,34,34,33,34,34,34,
		16,34,18,34,16,34,18,34,17,34,18,34,17,34,18,34,
		35,34,34,34,35,34,34,34,33,34,34,34,33,34,34,34,
		16,34,18,34,16,34,18,34,17,34,18,34,17,34,18,34,
		35,34,34,34,35,34,34,34,33,34,34,34,33,34,34,34  };

    char          *p1a;
    register char *p1, *p3;
    int           i, *xbuf;
    register int  r1, r2, j, *p2;

    ox = px;			/* copy parameters		 */
    oy = py;
    sx = qx;
    sy = qy;
    abm = (char *) malloc (sx * sy * sizeof (*abm));
				/* allocate space		 */
    xbuf = (int *) malloc ((sx - 2) * sizeof (*xbuf));
				/* x-buffer			 */

    p3 = abm;			/* get result pointer		 */

    p1 = &pcb[oy][ox];		/*** pre-scan 		       ***/
    p1a = &pcb[oy + 1][ox];
    p2 = xbuf;
    r1 = tab1[255 & *p1++] << 1;
    r1 |= tab1[255 & *p1++];
    r2 = tab1[255 & *p1a++] << 1;
    r2 |= tab1[255 & *p1a++];
    *p3++ = NOGOD | NOGOD << 4;
    *p3++ = NOGOD | NOGOD << 4;
    for (i = 2; i < sx; i++) {	/* this scans 2 lines		 */
	*p3++ = NOGOD | NOGOD << 4;
	r1 = (0x6db6 & r1 << 1) | tab1[255 & *p1++];
	r2 = (0x6db6 & r2 << 1) | tab1[255 & *p1a++];
	*p2++ = tab2[r1 & 511] << 1 | tab2[r2 & 511] | r2 & 0x2400;
    }

    for (i = 2; i < sy; i++) {	/*** main - scan	      ***/
	p1 = &pcb[i + oy][ox];
	p2 = xbuf;
	r1 = tab1[255 & *p1++] << 1;
	r1 |= tab1[255 & *p1++];
	*p3++ = NOGOD | NOGOD << 4;
	for (j = 2; j < sx; j++) {
	    r1 = (0x6db6 & r1 << 1) | tab1[255 & *p1++];
	    r2 = (0xd9b6 & (*p2) << 1) | tab2[r1 & 511] | r1 & 0x2400;
	    *p2++ = r2;
	    *p3++ = tab3[(0x12 & r2 >> 10) | tab2[r2 & 511]];
	}
	*p3++ = NOGOD | NOGOD << 4;
    }

    for (i = 0; i < sx; i++)	/*** post - scan	       ***/
	*p3++ = NOGOD | NOGOD << 4;

    free (xbuf);		/* release x - buffer		 */
}

set_dir ()			/* set up directions		 */
{
    dir [8] = dir[0] = 1;
    dir [9] = dir[1] = 1 + sx;
    dir [10] = dir[2] = sx;
    dir [11] = dir[3] = sx - 1;
    dir [12] = dir[4] = -1;
    dir [13] = dir[5] = -sx - 1;
    dir [14] = dir[6] = -sx;
    dir [15] = dir[7] = 1 - sx;
}

abm_tst (x, y)
    int x, y;
{
    int     i, j;
    char   *t;

    if (!abm || x < ox || y < oy || x >= ox + sx || y >= oy + sy)
	return;

    printf ("ABM - Test at x=%d y=%d\n", x, y);

    for (i = y + 3; i >= y - 3; --i) {
	printf ("\t%d:  ", i);
	for (j = x - 4; j <= x + 4; ++j) {
	    if (i >= oy && i < oy + sy && j >= ox && j < ox + sx) {
		t = abm + (i - oy) * sx + j - ox;
		printf (" %2x", *t & 255);
	    }
	    else
		printf (" ..");
	}
	printf ("\n");
    }
}
!E!O!F!
#
# type    sh /usru0/agn/pcb/distr/../usenet/part6   to unpack this archive.
#
echo extracting pleer1.c...
cat >pleer1.c <<'!E!O!F!'
/*******************************************************\
* 						        *
* 	PCB program				        *
* 						        *
* 	Lee Router section   (part 1: full maze run)    *
* 						        *
* 	(c) 1985		A. Nowatzyk	        *
* 						        *
\*******************************************************/

#include "pparm.h"
#include "pcdst.h"
#include "pleer.h"

maze_run (xs, ys)		/* run through the maze		 */
    int xs, ys;
{
/*****************************************************************\
* 								  *
*  Note: positions and directions refere to the auxilary bitmap.  *
*        They operate on pointer (eficiency hack).		  *
* 								  *
\*****************************************************************/
    static int  htt1[8] = {	/* home token table (side 1)	 */
	HDT + 4, HDT + 5, HDT + 6, HDT + 7, HDT + 0, HDT + 1, HDT + 2, HDT + 3
    };
    static int  htt2[8] = {	/* home token table (side 2)	 */
	(HDT + 4) << 4, (HDT + 5) << 4, (HDT + 6) << 4, (HDT + 7) << 4,
	(HDT + 0) << 4, (HDT + 1) << 4, (HDT + 2) << 4, (HDT + 3) << 4
    };
    static int dtab[16] = {
	1, 0, 1, 1,   1, 1, 1, 1,   0, 0, 0, 0,   0, 0, 0, 0 };
    int cd;
    register int   i, j, k;
    register char  *t, *t1;
    register unsigned *rtp;
    unsigned ort;

#ifdef debug
    int x, y;
#endif

    do {			/* *** main loop - let us run  *** */

	for ((rtp = hvrt, i = 0); i < hvrtc;(rtp++, i++)) {
				/* let us go h/v		 */
	    if (!(*rtp))
		continue;	/* dead entry, will be removed later */
	    if (drtc >= drtmax) /* need more space		 */
		add_space (&drt, drtc, &drtmax);

	    t = abm + (*rtp >> 8);
	    j = *rtp & rtdr;

	    if (!(*rtp & rtsb)) {
		k = (*t & MSK1) ^ HDT;
		if (dtab[MSK1 & *(t + dir[j + 1])] && k != ((j + 5) & 7))
				/* spawn ray in +1 direction	 */
		    drt[drtc++] = *rtp & ~rtdr | (j + 1) & rtdr;
		if (dtab[MSK1 & *(t + dir[j + 7])] && k != ((j + 3) & 7))
				/* spawn ray in -1 direction	 */
		    drt[drtc++] = *rtp & ~rtdr | (j + 7) & rtdr;

		t += dir[j];
		*rtp += dir[j] << 8;
		if (k = MSK1 & *t) {/* ray hit something	 */
		    if (!(k & HDT) && (k != NOGOD) &&
			    trm_chk (xs, ys, t,
				     (j + 4) & 7, s1b, (*rtp & rtvc) >> 4))
			return (1);
		    if (k != HOLE) {
		        hvrtcd++;/* increase deleted count	 */
		        *rtp = 0;}/* terminate this ray		 */
		    else {
		       	*t = (*t & MSK2) | htt1[j];
#ifdef debug
			if (ttt) {
			    color (resb, resb);
			    y = (int)(t-abm);
			    x = ox + y % sx;
			    y = oy + y / sx;
			    point (x, y);
			}
#endif
		    }}
		else {
		    *t |= htt1[j];/* mark square		 */
#ifdef debug
		    if (ttt) {
			color (resb, resb);
			y = (int)(t-abm);
			x = ox + y % sx;
			y = oy + y / sx;
			 point (x, y);
		    }
#endif
		}}
	    else {
		k = HDT ^ (*t & MSK2) >> 4;
		if (dtab[MSK1 & *(t + dir[j + 1]) >> 4] && k != ((j + 5) & 7))
				/* spawn ray in +1 direction	 */
		    drt[drtc++] = *rtp & ~rtdr | (j + 1) & rtdr;
		if (dtab[MSK1 & *(t + dir[j + 7]) >> 4] && k != ((j + 3) & 7))
				/* spawn ray in -1 direction	 */
		    drt[drtc++] = *rtp & ~rtdr | (j + 7) & rtdr;

		t += dir[j];
		*rtp += dir[j] << 8;
		if (k = MSK2 & *t) {/* ray hit something	 */
		    if (!(k & HDT << 4) && (k != NOGOD << 4) &&
			    trm_chk (xs, ys, t,
				     (j + 4) & 7, s2b, (*rtp & rtvc) >> 4))
			return (1);
		    if (k != HOLE << 4) {
		        hvrtcd++;/* increase deleted count	 */
		        *rtp = 0;}/* terminate this ray		 */
		    else {
		       *t = (*t & MSK1) | htt2[j];
#ifdef debug
			if (ttt) {
			    color (resb, resb);
			    y = (int)(t-abm);
			    x = ox + y % sx;
			    y = oy + y / sx;
			    point (x, y);
			}
#endif
		    }}
		else {
		    *t |= htt2[j];/* mark square		 */
#ifdef debug
		    if (ttt) {
			color (resb, resb);
			y = (int)(t-abm);
			x = ox + y % sx;
			y = oy + y / sx;
			 point (x, y);
		    }
#endif
		}
	    }
	}


	cd = hvrtc;		/* save count for balance expand */

	for ((rtp = drt, i = 0); i < drtc;(rtp++, i++)) {
				/* * let us go diagonally	* */
	    if (!(*rtp))	/* dead entry, will be removed later */
		continue;
	    if (hvrtc >= hvrtmax)
		add_space (&hvrt, hvrtc, &hvrtmax);

	    j = *rtp & rtdr;
	    t = abm + (*rtp >> 8);

	    if (!(*rtp & rtsb)) {
		k = (*t & MSK1) ^ HDT;
		if (dtab[MSK1 & *(t + dir[j + 1])] && k != ((j + 5) & 7))
				/* spawn ray in +1 direction	 */
		    hvrt[hvrtc++] = *rtp & ~rtdr | (j + 1) & rtdr;
		if (dtab[MSK1 & *(t + dir[j + 7])] && k != ((j + 3) & 7))
				/* spawn ray in -1 direction	 */
		    hvrt[hvrtc++] = *rtp & ~rtdr | (j + 7) & rtdr;

		t += dir[j];
		*rtp += dir[j] << 8;
		if (k = MSK1 & *t) {/* ray hit something	 */
		    if (!(k & HDT) && (k != NOGOD) &&
			    trm_chk (xs, ys, t,
				     (j + 4) & 7, s1b, (*rtp & rtvc) >> 4))
			return (1);
		    if (k != HOLE) {
		        drtcd++;/* increase deleted count	 */
		        *rtp = 0;}/* terminate this ray		 */
		    else {
		        *t = (*t & MSK2) | htt1[j];
#ifdef debug
			if (ttt) {
			    color (resb, resb);
			    y = (int)(t-abm);
			    x = ox + y % sx;
			    y = oy + y / sx;
			    point (x, y);
			}
#endif
		    }}
		else {
		    *t |= htt1[j];/* mark square		 */
#ifdef debug
		    if (ttt) {
			color (resb, resb);
			y = (int)(t-abm);
			x = ox + y % sx;
			y = oy + y / sx;
			 point (x, y);
		    }
#endif
		}}
	    else {
		k = HDT ^ (*t & MSK2) >> 4;
		if (dtab[MSK1 & *(t + dir[j + 1]) >> 4] && k != ((j + 5) & 7))
				/* spawn ray in +1 direction	 */
		    hvrt[hvrtc++] = *rtp & ~rtdr | (j + 1) & rtdr;
		if (dtab[MSK1 & *(t + dir[j + 7]) >> 4] && k != ((j + 3) & 7))
				/* spawn ray in -1 direction	 */
		    hvrt[hvrtc++] = *rtp & ~rtdr | (j + 7) & rtdr;

		t += dir[j];
	        *rtp += dir[j] << 8;
		if (k = MSK2 & *t) {/* ray hit something	 */
		    if (!(k & HDT << 4) && (k != NOGOD << 4) &&
			    trm_chk (xs, ys, t,
				     (j + 4) & 7, s2b, (*rtp & rtvc) >> 4))
			return (1);
		    if (k != HOLE << 4) {
		        drtcd++;/* increase deleted count	 */
		        *rtp = 0;}/* terminate this ray		 */
		    else {
		 	*t = (*t & MSK1) | htt2[j];
#ifdef debug
			if (ttt) {
			    color (resb, resb);
			    y = (int)(t-abm);
			    x = ox + y % sx;
			    y = oy + y / sx;
			    point (x, y);
			}
#endif
		    }}
		else {
		    *t |= htt2[j];/* mark square		 */
#ifdef debug
		    if (ttt) {
			color (resb, resb);
			y = (int)(t-abm);
			x = ox + y % sx;
			y = oy + y / sx;
			 point (x, y);
		    }
#endif
		}
	    }
	}

	for (rtp = hvrt + (i = cd); i < hvrtc; (rtp++, i++)) {
				/* let us go h/v		 */
	    if (!(*rtp))
		continue;	/* dead entry, will be removed later */
	    if (drtc >= drtmax)
		add_space (&drt, drtc, &drtmax);

	    t1 = t = abm + (*rtp >> 8);
	    ort = *rtp;
	    j = *rtp & rtdr;

	    if (!(*rtp & rtsb)) {
		t += dir[j];
		*rtp += dir[j] << 8;
		if (k = MSK1 & *t) {/* ray hit something	 */
		    if (!(k & HDT) && (k != NOGOD) &&
			    trm_chk (xs, ys, t,
				     (j + 4) & 7, s1b, (*rtp & rtvc) >> 4))
			return (1);
		    if (k != HOLE) {
		        hvrtcd++;/* increase deleted count	 */
		        *rtp = 0;}/* terminate this ray		 */
		    else {
		       *t = (*t & MSK2) | htt1[j];
#ifdef debug
			if (ttt) {
			    color (resb, resb);
			    y = (int)(t-abm);
			    x = ox + y % sx;
			    y = oy + y / sx;
			    point (x, y);
			}
#endif
		    }}
		else {
		    k = (*t1 & MSK1) ^ HDT;
		    if (dtab[MSK1 & *(t1 + dir[j + 1])] && k != ((j + 5) & 7))
				/* spawn ray in +1 direction	 */
			drt[drtc++] = ort & ~rtdr | (j + 1) & rtdr;
		    if (dtab[MSK1 & *(t1 + dir[j + 7])] && k != ((j + 3) & 7))
				/* spawn ray in -1 direction	 */
			drt[drtc++] = ort & ~rtdr | (j + 7) & rtdr;

		    *t |= htt1[j];/* mark square		 */
#ifdef debug
		    if (ttt) {
			color (resb, resb);
			y = (int)(t-abm);
			x = ox + y % sx;
			y = oy + y / sx;
			 point (x, y);
		    }
#endif
		}}
	    else {
		t += dir[j];
		*rtp += dir[j] << 8;
		if (k = MSK2 & *t) {/* ray hit something	 */
		    if (!(k & HDT << 4) && (k != NOGOD << 4) &&
			    trm_chk (xs, ys, t,
				     (j + 4) & 7, s2b, (*rtp & rtvc) >> 4))
			return (1);
		    if (k != HOLE << 4) {
		       hvrtcd++;/* increase deleted count	 */
		       *rtp = 0;}/* terminate this ray		 */
		    else {
			*t = (*t & MSK1) | htt2[j];
#ifdef debug
			if (ttt) {
			    color (resb, resb);
			    y = (int)(t-abm);
			    x = ox + y % sx;
			    y = oy + y / sx;
			    point (x, y);
			}
#endif
		    }}
		else {
		    k = HDT ^ (*t1 & MSK2) >> 4;
		    if (dtab[MSK1 & *(t1 + dir[j + 1]) >> 4] && k != ((j + 5) & 7))
				/* spawn ray in +1 direction	 */
			drt[drtc++] = ort & ~rtdr | (j + 1) & rtdr;
		    if (dtab[MSK1 & *(t1 + dir[j + 7]) >> 4] && k != ((j + 3) & 7))
				/* spawn ray in -1 direction	 */
		        drt[drtc++] = ort & ~rtdr | (j + 7) & rtdr;

		    *t |= htt2[j];/* mark square		 */
#ifdef debug
		    if (ttt) {
			color (resb, resb);
			y = (int)(t-abm);
			x = ox + y % sx;
			y = oy + y / sx;
			 point (x, y);
		    }
#endif
		}
	    }
	}

	for (i = 0; i < vhtc; i++)
	    if (--vht[i].c <= 0) { /* via hole gets trough	 */
		j = (vht[i].s == s1b) ? HDT << 4 : HDT;
		for (k = 0; k < 8; k++)
		    if (j & *(vht[i].t + dir[k]))
			break;
		if (k >= 8) {	/* this is an interesting hole	 */
#ifdef debug
  if (ttt) {
		x = (int) (vht[i].t - abm);
		y = oy + x / sx;
		x = ox + x % sx;
		if (x >= tx1 && x <= tx2 && y >= ty1 && y <= ty2)
		    printf("Hole at %3d,%3d to side %d retrieved\n",
			x, y, vht[i].s ^ vec);
  }
#endif
		    for (j = 0; j < 4; j++) {/* set up ray table */
#ifdef dfirst
		    drt[drtc++] =  ((int)(vht[i].t - abm)) << 8 |
				   (vht[i].n - 1) << 4 |
				   ((vht[i].s == s1b) ? rtsb : 0) |
				   (j + j + 1);
#else
		    hvrt[hvrtc++]= ((int)(vht[i].t - abm)) << 8 |
				   (vht[i].n - 1) << 4 |
				   ((vht[i].s == s1b) ? rtsb : 0) |
				   (j + j);
#endif
		    }
		}
		for (j = i + 1; j < vhtc; j++) {
		    vht[j - 1].t = vht[j].t;
		    vht[j - 1].s = vht[j].s;
		    vht[j - 1].n = vht[j].n;
		    vht[j - 1].c = vht[j].c;
	    	}
	        vhtc--;
	    }
    
	if (drtc < drtcd * 4) {	/* recover space if more than 25% lost */
	    for (j = i = 0; i < drtc; i++)
		if (drt[i]) 
		    drt[j++] = drt[i];
	    drtc = j;
	    drtcd = 0;		/* reset deleted count		 */
	}

	if (hvrtc < hvrtcd * 4) {/* recover space if more than 25% lost */
	    for (j = i = 0; i < hvrtc; i++)
		if (hvrt[i])
		    hvrt[j++] = hvrt[i];
	    hvrtc = j;
	    hvrtcd = 0;		/* reset deleted count		 */
	}
/*getcur(&x,&y);*/
/*tststr("after cleanup");*/
    } while ((drtc - drtcd + hvrtc - hvrtcd) || vhtc);
				/* until all rays died		 */

    return (0);			/* no connection found		 */
}

#ifdef debug
tststr(s)	/* test structure */
 char *s;
{
    int     i, j, k, x, y, y_key ();
    unsigned t;
k=0;
    qsort (drt, drtc, sizeof (*drt), y_key);
    qsort (hvrt, hvrtc, sizeof (*hvrt), y_key);

    for (i = 0; i < drtc; i++) {
	t = drt[i];
	for (j = i + 1; j < drtc; j++)
	    if (t != drt[j])
		break;
	j--;

	if (j > i) {
	    if (t) {
		if(!k) {    printf ("structure test - (%8x) %s\n",V.cnet, s);
k=1;}
		printf ("D: x/y= %3d,%3d s=%d d=%d  --  %3d times\n",
			ox + (t >> 8) % sx, oy + (t >> 8) / sx,
			(t & rtsb) ? s2b : s1b, t & rtdr, j - i +1);
	    }
if(t && j - i > 5) {
 printf("have fun\n");
 x=0;
}
	    i = j + 1;
	}
    }

    for (i = 0; i < hvrtc; i++) {
	t = hvrt[i];
	for (j = i + 1; j < hvrtc; j++)
	    if (t != hvrt[j])
		break;
	j--;

	if (j > i) {
	    if (t) {
		if(!k) {    printf ("structure test - (%8x) %s\n",V.cnet, s);
k=1;}
		printf ("HV:x/y= %3d,%3d s=%d d=%d  --  %3d times\n",
			ox + (t >> 8) % sx, oy + (t >> 8) / sx,
			(t & rtsb) ? s2b : s1b, t & rtdr, j - i+1);
	    }
	    i = j + 1;
	}
    }
}

y_key (a, b)
    unsigned *a, *b;
{
    return ((*a > *b) - (*a < *b));
}

#endif

add_space (p, n, max)		/* increase table space		 */
    int n, *max;
    unsigned **p;
{
    int     i;
    unsigned *t, *t1, *t2;

    i = *max + *max / 2;	/* add 50%			 */
    t1 = t = (unsigned *) malloc ((i + sftmrg) * sizeof (*t));
    *max = i;
    for ((t2 = *p, i = 0); i < n; i++)	/* copy stuff		 */
	*(t1++) = *(t2++);
    free (*p);			/* release old space		 */
    *p = t;
}

trm_chk (xs, ys, t, d, sd, vc)	/* termination check		 */
    int xs, ys, d, sd, vc;
    char *t;
/****************************************************************************\
* 									     *
*  Termination check: the maze-runner encountered an unusual object.	     *
*  such objects are:							     *
*    1. TERMs : a path was found (but there might be an s1b/s2b exception).  *
*    2. VTERMs: like 1, but a via-hole is necessary.			     *
*    3. HOLE  : the maze spawns to the other side.			     *
* 									     *
\****************************************************************************/
{
    int i, j, x, y, vt;
    int sx1, sy1, ox1, oy1, s1, d1;
    char *t1, *abm1;

    vt = 0;			/* no via hole default		 */

    j = (sd == s1b) ? *t & MSK1 : (*t & MSK2) >> 4;
    switch (j) {
	case VTERM: 
	case VTERM | HOLE: 

	    if (!C3)
		return 0;	/* allways fails if no via-holes */

	    i = (int) (t - abm);/* get real koordinates		 */
	    y = oy + i / sx;
	    x = ox + i % sx;

	    if ((i = (x | y) & 1)) {/* need alignment		 */
		if (x & 1) {	/* x is of grid			 */
		    if (((d + 1) & 7) < 4)
			x++;
		    else
			x--;
		}
		if (y & 1) {	/* y is of grid			 */
		    if (((d + 7) & 7) < 4)
			y++;
		    else
			y--;
		}
	    }

	    color (ishb | selb, ishb | selb);
	    if (pin (x, y))
		return (0);	/* pin allocation failed	 */

	    if (i) {		/* of wire pin, due to alignment */
		color (vec, vec);
		pxl (x, y);
	    }
	    vt = 1;		/* don't forget to remove grabage*/


	case TERM: 
	case TERM | HOLE: 
	    mz_done (t, d, sd);/* start at <xd,yd>		 */

	    get_vias (t, d, sd);
	    for (i = 0; i < vhptc; i++) {
		t1 = vhpt[i];
		j = (int) (t1 - abm);
		x = ox + j % sx;
		y = oy + j / sx;
		s1 = ((*t1 & MSK1) == HOLE) ? s2b : s1b;
		d1 = 7 & ((s1 == s1b) ? *t1 : *t1 >> 4);
		color (ishb | selb, ishb | selb);
		if (pin (x, y)) {
		    t1 = vhpt[i - 1];
		    d1 = 7 & ((s1 == s2b) ? *t1 : *t1 >>4);
		    if (i && fnc_tnnl (t1, d1, s1))
			mz_done (t1, d1, s1);	/* not a problem	*/
		    else {
			mz_undone (t, d, sd);
			return (0);	/* via-hole interaction problem */
		    }}
		else {
		    if ((*t1 & MSK1) == MSTART ||
			(*t1 & MSK2) == MSTART << 4)
			break;	/* hole on start wire exception	 */
		    if (mz_chk (t1, d1, s1)) {
				/* trouble			 */
			abm1 = abm;/* save aux bit map		 */
			sx1 = sx;
			sy1 = sy;
			ox1 = ox;
			oy1 = oy;
			j = s_route (xs, ys, x, y);
			abm = abm1;/* restore bitmap		 */
			sx = sx1;
			sy = sy1;
			ox = ox1;
			oy = oy1;
			set_dir ();
			if (!j)	/* recovery failed		 */
			    mz_undone (t, d, sd);
			return (j);
		    }
		    mz_done (t1, d1, s1);
		}
	    }

	    if (vt) 		/* (TERM-) via hole needs care	 */
		ckgp (x, y, sd);
	    return (1);		/* that's it			 */


	case HOLE: 		/* prepare for via - hole	 */
	    if (vhtc >= maxvht)
		err ("trm_chk: Via hole table too small - increase 'maxvht'",
		     vhtc, maxvht, 0, 0);
	    if (vc > 0 && *t == (HOLE | HOLE << 4)) {
		vht[vhtc].t = t;
		vht[vhtc].s = sd;
		vht[vhtc].c = ((d & 1) ? C5 : C4) + (C3 - vc) * C7;
		vht[vhtc++].n = vc;
#ifdef debug
   if (ttt) {
		x = (int) (t - abm);
		y = oy + x / sx;
		x = ox + x % sx;
		if (x >= tx1 && x <= tx2 && y >= ty1 && y <= ty2)
		    printf("Hole at %3d,%3d to side %d with delay=%d vc=%d entered\n",
			x, y, sd ^ vec, vht[vhtc - 1].c, vc);
   }
#endif
	    }
	    return (0);

	case MSTART:
	    return (0);		/* ignore start token		 */

	default:
	    err ("trm_chk: Unknown token", j, *t, sd, 0);
    }

    return 0;			/* to please lint		 */
}

fnc_tnnl (t, d, s)		/* fence tunnel			 */
    int d, s;
    char *t;
/************************************************************************\
* 									 *
*  This routine is an exception handler to recover from problems	 *
*  caused by fences: 2 via-holes (which are redundant) are placed	 *
*  too close to eachother. The hole that was already inserted will	 *
*  be removed and the 'wrong' side will be used for the wire.		 *
* 									 *
*  A 1 is returned if the hole was caused by the fence and is therefore	 *
*  redundant. A 0 indicates that a real hole was needed.		 *
* 									 *
\************************************************************************/
{
    int     i, j, x, y, x1, y1, d1;
    char    *t1;

    i = (int) (t - abm);	/* get real koordinates		 */
    y1 = y = oy + i / sx;
    x1 = x = ox + i % sx;
    t1 = t;
    d1 = d;
    j = (s == s2b) ? 0 : 4;

    do {			/* feasability test		 */
	x1 += dr[d1][0];
	y1 += dr[d1][1];
	t1 += dir[d1];

	if (HOLE == (i = (*t1) >> j & MSK1)) 
	    break;		/* exit on offending hole	 */

	if (pcb[y1][x1] & s) 	/* via is not redundant !	 */
	    return (0);

	d1 = i & 7;
    } while (i & HDT);

    color (0, ishb | selb);	/* ready to go !		 */
    dpin (x, y);
    color (0 , (s ^ vec) | selb);
    pxl (x, y);			/* inefficient, but seldom	 */

    do {			/* Loop back			 */

	*t = (s == s2b) ? (*t & MSK1) | (HDT | d) << 4  :
			  (*t & MSK2) | (HDT | d);

	x += dr[d][0];
	y += dr[d][1];
	t += dir[d];

	pxl (x, y);

	if (HOLE == (i = (*t) >> j & MSK1)) 
	    return (1);		/* exit on offending hole	 */

	d = i & 7;
    } while (i & HDT);
    err ("fnc_tnnl: illegal token", x, y, i, (int) (t - abm));

    return 0;			/* to please lint		 */
}

mz_done (t, d, s)		/* maze done - backtrace	 */
    int d, s;
    char *t;
{
    int     i, j, x, y, n, xl, yl, dl;

    i = (int) (t - abm);	/* get real koordinates		 */
    yl = y = oy + i / sx;
    xl = x = ox + i % sx;
    dl = d;

    color (s | selb, s | selb);

    j = (s == s1b) ? 0 : 4;

    do {			/* Loop back			 */
	x += dr[d][0];
	y += dr[d][1];
	t += dir[d];

	n = 0;
	if (d != dl) {
	     plt (xl, yl, x - dr[d][0], y - dr[d][1]);
	     xl = x;
	     yl = y;
	     dl = d;
	     n = 1;
	}

	if (MSTART == (i = (*t) >> j & MSK1) || i == HOLE) {
	    if (n)
		pxl (x, y);
	    else
		plt (xl, yl, x, y);
	    return;		/* exit on start token		 */
	}
	d = i & 7;
    } while (i & HDT);
    err ("mz_done: illegal token", x, y, i, (int) (t - abm));
}

mz_chk (t, d, s)		/* maze done - backtrace	 */
    int d, s;
    char *t;
/*******************************************************************\
* 								    *
*  Maze check: The result path is check for selected s1b and s2b    *
*  pixels on not-hole squares. a '1' is returned if this violation  *
*  is detected, a '0' is returned for a good path. Note: this is    *
*  just an other hack due to the lack of 2 marker/select bits.	    *
* 								    *
\*******************************************************************/
{
    int     i, j, x, y, p, c;

    i = (int) (t - abm);	/* get real koordinates		 */
    y = oy + i / sx;
    x = ox + i % sx;

    j = (s == s1b) ? 0 : 4;
    c = selb | (vec ^ s);

    p = pcb[y][x];
    if (!(p & ahb) && !(~p & c))
	return (1);		/* error			 */

    do {			/* Loop back			 */
	x += dr[d][0];
	y += dr[d][1];
	t += dir[d];

	p = pcb[y][x];
	if (!(p & ahb) && !(~p & c))
	    return (1);		/* error			 */

	if (MSTART == (i = (*t) >> j & MSK1) || i == HOLE)
	    return (0);		/* success			 */

	d = i & 7;
    } while (i & HDT);
    err ("mz_chk: illegal token", x, y, i, (int) (t - abm));

    return 0;			/* to plese lint		 */
}

mz_undone (t, d, s)		/* maze un-done - backtrace	 */
/**********************************************************************\
* 								       *
*  This routine un-does the effect of a mz_done call which may become  *
*  necessary to un-do long traces in L*_routes. The main problem is    *
*  the lack of bit-planes: 2 mark and 2 select bits are necessary to   *
*  avoid these hacks.						       *
* 								       *
\**********************************************************************/
    int d, s;
    char *t;
{
    int     i, j, x, y, n, xl, yl, dl, xs, ys;

    i = (int) (t - abm);	/* get real koordinates		 */
    ys = yl = y = oy + i / sx;
    xs = xl = x = ox + i % sx;
    dl = d;


    color (0, s | selb);

    j = (s == s1b) ? 0 : 4;

    do {			/* Loop back			 */
	x += dr[d][0];
	y += dr[d][1];
	t += dir[d];

	n = 1;
	if (d != dl) {
	     plt (xl, yl, x - dr[d][0], y - dr[d][1]);
	     xl = x;
	     yl = y;
	     dl = d;
	     n = 0;
	}

	i = *t >> j & MSK1;

	if (i == HOLE) {	/* time to switch sides		 */
	    j ^= 4;
	    i = *t >> j & MSK1;
	    plt (xl, yl, x, y);
	    xl = x;
	    yl = y;
	    dl = i & 7;
	    if (i != MSTART) {
		color (0, ishb | selb);
		dpin (x, y);	/* remove via hole		 */
		s ^= vec;	/* change color			 */
		color (0, s | selb);
	    }
	}

	if (MSTART == i) {
	    if (n)
		plt (xl, yl, x - dr[d][0], y - dr[d][1]);
	    i = 8;		/* assume safe to do ck_rdnb	 */
	    if (pcb[y][x] & ahb)
		for (i = 0; i < 8; i++)
		    if (pcb[y + dr[i][1]][x + dr[i][0]] & s)
			break;
	    if (i >= 8)		/* don't remove center of holes	 */
	    	ck_rdnb (x, y, s);
	    if (pcb[y][x] & ahb) {
		color (selb, selb);
		dpin (x, y);
	    }

	    if (pcb[ys][xs] & ahb) {
		color (selb, selb);
		dpin (xs, ys);
	    }
	    return;		/* exit on start token		 */
	}

	d = i & 7;
    } while (i & HDT);
    err ("mz_undone: illegal token", x, y, i, (int) (t - abm));
}

get_vias (t, d, s)		/* get list of via holes	 */
    int d, s;
    char *t;
/***********************************************************************\
* 								        *
*  The list of via holes is necessary to check for s1b-s2b problems,    *
*  which has to be done for each segment after the previous was added.  *
* 								        *
\***********************************************************************/
{
    int     i, j;

    vhptc = 0;			/* reset via hole counter	 */

    j = (s == s1b) ? 0 : 4;

    do {			/* Loop back			 */
	t += dir[d];

	i = *t >> j & MSK1;

	if (i == HOLE) {	/* time to switch sides		 */
	   j ^= 4;
	   i = *t >> j & MSK1;
	   vhpt[vhptc++] = t;
	}

	if (MSTART == i)
	    return;		/* done				 */

	d = i & 7;
    } while (i & HDT);
    err ("get_vias: illegal token", i, (int) (t - abm), 0, 0);
}

S_route (xs, ys, xd, yd)		/* full maze - run		 */
    int xs, ys, xd, yd;
/**************************************************************************\
* 									   *
*  This is a allmost unrestricted version of a maze-router. The routing	   *
*  area is confined to a rectangle that is C1 larger than the one defined  *
*  by <xs,ys> and <xd,yd>. Runing will start at <xs,ys>.		   *
*  This routind runs faster if <xd,yd> points to the larger object.	   *
*  s_route returns successfully if <xs,ys> is connected to an other	   *
*  part of its net. This need not be a connection to <xd,yd>, thus	   *
*  a successfull return does *not* guarantee a connection between	   *
*  <xs,ys> and <xd,yd>.							   *
* 									   *
\**************************************************************************/
{
    int     mz_vf (), mz_hf ();
    char   *t;
    int     i;
#ifdef debug
    int x, y;
#endif

    cr_gmaze (xs, ys, xd, yd, C1);/* create maze		 */

#ifdef debug
  if (ttt) {
    color (resb, resb);
    plts (ox, oy, ox+sx-1, oy);
    plts (ox+sx-1, oy, ox+sx-1, oy+sy-1);
    plts (ox+sx-1, oy+sy-1, ox, oy+sy-1);
    plts (ox, oy+sy-1, ox, oy);
  }
#endif

    fence (xs, ys, xd, yd);	/* insert fences		 */
    mz_hole ();			/* insert via hole candidates	 */

#ifdef debug
  if (ttt) {
    err_msg ("llc of test area");
    getcur(&tx1,&ty1);
    err_msg ("urc of test area");
    getcur(&tx2,&ty2);
    err_msg ("abort?");
    if (getcur (&x, &y) > 3) {	/* abort			 */
	free (abm);
	abm = 0;
	return (0);
    }
  }
#endif

    set_dir ();			/* prepare maze run		 */
    hvrt = (unsigned *) malloc ((maxrtl + sftmrg) * sizeof (*hvrt));
    drt = (unsigned *) malloc ((maxrtl + sftmrg) * sizeof (*drt));
    drtmax = hvrtmax = maxrtl;
    vhtc = drtc = drtcd = hvrtcd = hvrtc = 0;/* reset table counter */

    wtvf = mz_vf;		/* mark start			 */
    wthf = mz_hf;
    i = pcb[ys][xs];
    if (i & ahb)
	wtrace (xs, ys, vec);
    else if (i & selb) {
	if (i & s1b && !(i & resb))
	    wtrace (xs, ys, s1b);
	else if (i & s2b && i & resb)
	    wtrace (xs, ys, s2b);
	else {
	    free (abm);
	    return 0;		/* somthing is wrong		 */
	}
    }	    

    t = abm + (yd - oy) * sx + xd - ox;
    i = (*t & MSK1) == MSTART || (*t & MSK2) == MSTART << 4;

    if (!i)
	i = maze_run (xs, ys);	/* find the path		 */

#ifdef debug
    if (ttt && !i) {
	do {
	    err_msg ("select point");
	    getcur (&x, &y);
	    if (x > ox && y > oy && x < ox + sx - 1 && y < oy + sy - 1) {
		t = abm + (y - oy) * sx + x - ox;
		if (*t & HDT) {
		    get_vias (t, *t & 7, s1b);
		    printf ("S1-path: Path has %d via holes\n", vhptc);}
		if (*t & HDT << 4) {
		    get_vias (t, (*t >> 4) & 7, s2b);
		    printf ("S2-path: Path has %d via holes\n", vhptc);}
		if (!(*t & (HDT | HDT << 4)))
		    printf ("No path\n");}
	    else
		break;
	} while (1);
    }
#endif

    free (drt);			/* release memory		 */
    free (hvrt);
    free (abm);
    abm = 0;

    return (i);
}
RE_route (src, dst, xl, yl, xh, yh, sd)
    int xl, yl, xh, yh, sd;
    char *src, *dst;
/********************************************************************\
* 								     *
*   Re_route is similar to S_route, but is used to straight a wire   *
*   (see 'straight' in pplow.c): an existing trace is erased and     *
*   routed again. For this reason, the maze-size is precisely known  *
*   and no via-holes are necessary or desirable.		     *
* 								     *
\********************************************************************/
{
    int     mz_vf (), mz_hf ();
    char   *t;
    register int i, j, xs, ys, xd, yd;
    int sv_C3 = C3;

    C3 = 0;			/* no via - holes		 */

    xs = ((int) src - (int) pcb) % xmax;      /* long live ptr-s */
    ys = ((int) src - (int) pcb) / xmax;
    xd = ((int) dst - (int) pcb) % xmax;
    yd = ((int) dst - (int) pcb) / xmax;

    cr_maze (xl, yl, xh - xl + 1, yh - yl + 1);	/* create maze	 */

    set_dir ();			/* prepare maze run		 */
    hvrt = (unsigned *) malloc ((maxrtl + sftmrg) * sizeof (*hvrt));
    drt = (unsigned *) malloc ((maxrtl + sftmrg) * sizeof (*drt));
    drtmax = hvrtmax = maxrtl;
    vhtc = drtc = drtcd = hvrtcd = hvrtc = 0;/* reset table counter */

    wtvf = mz_vf;		/* mark start			 */
    wthf = mz_hf;
    wtrace (xs, ys, sd);

    j = (sd == s1b) ? 0 : rtsb;
    for (i = 0; i < hvrtc; i++)
	if ((hvrt[i] & rtsb) != j)
	    hvrt[i] = 0;	/* kill rays for wrong side	 */
    for (i = 0; i < drtc; i++)
	if ((drt[i] & rtsb) != j)
	    drt[i] = 0;		/* kill rays for wrong side	 */

    t = abm + (yd - oy) * sx + xd - ox;
    i = (*t & MSK1) == MSTART || (*t & MSK2) == MSTART << 4;

    if (!i)
	i = maze_run (xs, ys);	/* find the path		 */

    if (!i)
	err ("RE_route: there should be a path ??", xs, ys, xd, yd);

    free (drt);			/* release memory		 */
    free (hvrt);
    free (abm);
    abm = 0;
    C3 = sv_C3;			/* restore C3			 */
}

fence (x1, y1, x2, y2)		/* insert fences		 */
    int x1, y1, x2, y2;
{
    int     i, j, k;
    char *t;
#ifdef debug
    int xx, yy;
#endif

    if (x1 > x2) {		/* insure x1 <= x2		 */
	i = x1;
	x1 = x2;
	x2 = i;
    }
    if (y1 > y2) {		/* insure y2 <= y2		 */
	i = y1;
	y1 = y2;
	y2 = i;
    }

    k = sx / 2;

    x1 = (((x1 - C2 / 2) | 1) % C2) - (ox % C2);
    for (i = (x1 <= 0) ? x1 + C2 : x1; i < k; i += C2) {
	t = abm + i + sx;	/* insert y - fences		 */
#ifdef debug
  if (ttt) {
	yy = (int)(t - abm);
	xx = ox + yy % sx;
	yy = oy + yy / sx;
	color (mrkb, mrkb);
	plts (xx, yy, xx, yy + sy - 2);
  }
#endif
	for (j = 2; j < sy; (t += sx, j++))
	    if ((*t & MSK2) != TERM << 4)
		*t = (*t & MSK1) | NOGOD << 4;
    }

    x2 = (((x2 - 1 - C2 / 2) | 1) % C2) - ((ox + k) % C2);
    for (i = k + ((x2 < 0) ? x2 + C2 : x2); i < sx - 1; i += C2) {
	t = abm + i + sx;	/* insert y - fences		 */
#ifdef debug
  if (ttt) {
	yy = (int)(t - abm);
	xx = ox + yy % sx;
	yy = oy + yy / sx;
	color (mrkb, mrkb);
	plts (xx, yy, xx, yy + sy - 2);
  }
#endif
	for (j = 2; j < sy; (t += sx, j++))
	    if ((*t & MSK2) != TERM << 4)
		*t = (*t & MSK1) | NOGOD << 4;
    }

    k = sy / 2;

    y1 = (((y1 - C2 / 2) | 1) % C2) - (oy % C2);
    for (i = (y1 <= 0) ? y1 + C2 : y1; i < k; i += C2) {
	t = abm + i * sx + 1;	/* insert x - fences		 */
#ifdef debug
  if (ttt) {
	yy = (int)(t - abm);
	xx = ox + yy % sx;
	yy = oy + yy / sx;
	color (mrkb, mrkb);
	plts (xx, yy, xx + sx - 2, yy);
  }
#endif
	for (j = 2; j < sx; (t++, j++))
	    if ((*t & MSK1) != TERM)
		*t = (*t & MSK2) | NOGOD;
    }

    y2 = (((y2 - 1 - C2 / 2) | 1) % C2) - ((oy + k) % C2);
    for (i = k + ((y2 < 0) ? y2 + C2 : y2); i < sy - 1; i += C2) {
	t = abm + i * sx + 1;	/* insert x - fences		 */
#ifdef debug
   if (ttt) {
	yy = (int)(t - abm);
	xx = ox + yy % sx;
	yy = oy + yy / sx;
	color (mrkb, mrkb);
	plts (xx, yy, xx + sx - 2, yy);
   }
#endif
	for (j = 2; j < sx; (t++, j++))
	    if ((*t & MSK1) != TERM)
		*t = (*t & MSK2) | NOGOD;
    }
}

mz_hole()			/* insert via-hole candiates	 */
{
    int     x, y;
    char *t;

    for (y = oy + C6 - oy % C6; y < oy + sy - 1; y += C6)	
	for ((x = ox + C6 - ox % C6, t = abm + x - ox + (y - oy) * sx);
	     x < ox + sx - 1; (t += C6, x += C6))
	    if (((*t & MSK1) != NOGOD) && ((*t & MSK2) != NOGOD << 4) &&
		ck_pin (x, y)) {
#ifdef debug
  if (ttt) {
		color (mrkb, mrkb);
		point (x, y);
  }
#endif
		*t |= HOLE | (HOLE << 4);
	    }
}

mz_hf (x, y)			/* maze-run hole function	 */
    int x, y;
{
    register int i, j;
    register char   *t;

    if (x <= ox || y <= oy || x >= ox + sx - 1 || y >= oy + sy - 1)
	return (0);		/* outside of maze		 */

    t = abm + (x - ox + (y - oy) * sx);/* get start pointer	 */
    *t = MSTART | MSTART << 4;	/* mark start			 */
    for (i = 0; i < 4; i++) {	/* set up ray table		 */
#ifdef dfirst
	drt[drtc++] = j = ((int) (t - abm)) << 8 |
		    C3 << 4 |
		    i + i + 1;
	drt[drtc++] = j | rtsb;
#else
	hvrt[hvrtc++] = j = ((int) (t - abm)) << 8 |
		      C3 << 4 |
		      i + i;
	hvrt[hvrtc++] = j | rtsb;
#endif
    }
    return (0);
}

mz_vf (x1, y1, x2, y2)		/* maze-run set up vector 	 */
    int x1, y1, x2, y2;
{   int i, j, k, d, xl, yl, xh, yh;
    char *t;
    static int ct[9] = {5, 4, 3, 6, 8, 2, 7, 0, 1};

    xl = ox + 1;		/* active area of aux bit map	 */
    yl = oy + 1;
    xh = ox + sx - 2;
    yh = oy + sy - 2;

    if (y1 > y2) {		/* order y for y-band clipping	 */
	i = x1;
	x1 = x2;
	x2 = i;
	i = y1;
	y1 = y2;
	y2 = i;
    }
    i = ((x1 < x2) - (x2 < x1));

    if (y1 < yl) {
	if (y2 < yl)
	    return;
	x1 += (yl - y1) * i;
	y1 = yl;
    };

    if (y2 > yh) {
	if (y1 > yh)
	    return;
	x2 -= (y2 - yh) * i;
	y2 = yh;
    }

    if (x1 > x2) {		/* order x for x-band clipping	 */
	i = x1;
	x1 = x2;
	x2 = i;
	i = y1;
	y1 = y2;
	y2 = i;
    }
    i = (y1 < y2) - (y2 < y1);

    if (x1 < xl) {
	if (x2 < xl)
	    return;
	y1 += (xl - x1) * i;
	x1 = xl;
    }

    if (x2 > xh) {
	if (x1 > xh)
	    return;
	y2 -= (x2 - xh) * i;
	x2 = xh;
    }

    d = ct[((x1 < x2) - (x1 > x2) + 1) * 3 + (y1 < y2) - (y1 > y2) + 1];
    j = abs (x1 - x2) | abs (y1 - y2);/* length of vector	 */
    t = abm + (x1 - ox + (y1 - oy) * sx);/* get start pointer	 */

    if (wtsb == s1b)
	for (i = 0; i <= j; i++) {
	    if (!(pcb[y1][x1] & ahb)) {/* skip hole area	 */
		if (C3 && (*t & MSK2) == (HOLE | VTERM) << 4) {
		    *t = MSTART | HOLE << 4; 
		    for (k = 0; k < 4; k++) {
#ifdef dfirst
			drt[drtc++] = ((int) (t - abm)) << 8 |
				      (C3 - 1) << 4 |
				      rtsb |
				      k + k + 1;
#else
			hvrt[hvrtc++] = ((int) (t - abm)) << 8 |
				        (C3 - 1) << 4 |
				        rtsb |
				        k + k;
#endif
		    }}
		else if ((*t & MSK1) != MSTART)
		    *t = NOGOD << 4 | MSTART;/* mark start	 */
		if (d & 1) {	/* diagonal vector ?		 */
		    drt[drtc++] = ((int) (t - abm)) << 8 |
				  C3 << 4 |
				  (d + 2) & rtdr;
		    drt[drtc++] = ((int) (t - abm)) << 8 |
				  C3 << 4 |
				  (d + 6) & rtdr;
		}
		else {
		    hvrt[hvrtc++] = ((int) (t - abm)) << 8 |
				    C3 << 4 |
				    (d + 2) & rtdr;
		    hvrt[hvrtc++] = ((int) (t - abm)) << 8 |
				    C3 << 4 |
				    (d + 6) & rtdr;
		}
	    }
	    t += dir[d];
	    x1 += dr[d][0];
	    y1 += dr[d][1];
	}
    else
	for (i = 0; i <= j; i++) {
	    if (!(pcb[y1][x1] & ahb)) {/* skip hole area	 */
		if (C3 && (*t & MSK1) == (HOLE | VTERM)) {
		    *t = MSTART << 4 | HOLE;
		    for (k = 0; k < 4; k++) {
#ifdef dfirst
			drt[drtc++] = ((int) (t - abm)) << 8 |
				      (C3 - 1) << 4 |
				      k + k + 1;
#else
			hvrt[hvrtc++] = ((int) (t - abm)) << 8 |
				        (C3 - 1) << 4 |
				        k + k;
#endif
		    }}
		else if ((*t & MSK2) != MSTART << 4)
		    *t = NOGOD | MSTART << 4;/* mark start	 */
		if (d & 1) {	/* diagonal vector ?		 */
		    drt[drtc++] = ((int) (t - abm)) << 8 |
				  C3 << 4 |
				  rtsb |
				  (d + 2) & rtdr;
		    drt[drtc++] = ((int) (t - abm)) << 8 |
				  C3 << 4 |
				  rtsb |
				  (d + 6) & rtdr;
		}
		else {
		    hvrt[hvrtc++] = ((int) (t - abm)) << 8 |
				    C3 << 4 |
				    rtsb |
				    (d + 2) & rtdr;
		    hvrt[hvrtc++] = ((int) (t - abm)) << 8 |
				    C3 << 4 |
				    rtsb |
				    (d + 6) & rtdr;
		}
	    }
	    t += dir[d];
	    x1 += dr[d][0];
	    y1 += dr[d][1];
	}
}
!E!O!F!
#
# type    sh /usru0/agn/pcb/distr/../usenet/part6   to unpack this archive.
#
echo extracting pleer2.c...
cat >pleer2.c <<'!E!O!F!'
/***************************************************************\
*								*
*	PCB program						*
*								*
*	Lee Router section	(part 2: confined maze run)	*
*								*
*	(c) 1985		A. Nowatzyk			*
*								*
\***************************************************************/

#include "pparm.h"
#include "pcdst.h"
#include "pleer.h"

static int viahcnt;		/* via hole count for L*_route	 */
struct vht {			/* via hole table		 */
    char *t;			/* koordinate			 */
    int c;			/* cost				 */
} vhct[maxvhct];

maze_run1 (xs, ys)		/* run through the maze on side 1 */
    int xs, ys;
{
    int    i, mz_vf (), mz_hf ();

    if ((xs <= ox) || (xs >= ox + sx - 1) || (ys <= oy) || (ys >= oy + sy - 1))
	err ("maze_run1: invalid start point", xs, ys, ox, oy);

    set_dir ();
    hvrt = (unsigned *) malloc ((maxrtl + sftmrg) * sizeof (*hvrt));
    drt = (unsigned *) malloc ((maxrtl + sftmrg) * sizeof (*drt));
    drtmax = hvrtmax = maxrtl;
    vhtc = drtc = drtcd = hvrtcd = hvrtc = 0;/* reset table counter */

    wtvf = mz_vf;		/* mark start			 */
    wthf = mz_hf;
    wtrace (xs, ys, vec);

    for (i = 0; i < drtc; i++)	/* remove entries for wrong side */
	if (drt[i] & rtsb) {
	    drt[i] = 0;
	    drtcd++;
	}
    for (i = 0; i < hvrtc; i++)
	if (hvrt[i] & rtsb) {
	    hvrt[i] = 0;
	    hvrtcd++;
	}

    i = maze_run (xs, ys);	/* find the path		 */

    free (drt);
    free (hvrt);

    return (i);
}

maze_run2 (xs, ys)		/* run through the maze on side 1 */
    int xs, ys;
{
    int    i, mz_vf (), mz_hf ();

    if ((xs <= ox) || (xs >= ox + sx - 1) || (ys <= oy) || (ys >= oy + sy - 1))
	err ("maze_run2: invalid start point", xs, ys, ox, oy);

    set_dir ();
    hvrt = (unsigned *) malloc ((maxrtl + sftmrg) * sizeof (*hvrt));
    drt = (unsigned *) malloc ((maxrtl + sftmrg) * sizeof (*drt));
    drtmax = hvrtmax = maxrtl;
    vhtc = drtc = drtcd = hvrtcd = hvrtc = 0;/* reset table counter */

    wtvf = mz_vf;		/* mark start			 */
    wthf = mz_hf;
    wtrace (xs, ys, vec);

    for (i = 0; i < drtc; i++)	/* remove entries for wrong side */
	if (!(drt[i] & rtsb)) {
	    drt[i] = 0;
	    drtcd++;
	}
    for (i = 0; i < hvrtc; i++)
	if (!(hvrt[i] & rtsb)) {
	    hvrt[i] = 0;
	    hvrtcd++;
	}

    i = maze_run (xs, ys);	/* find the path		 */

    free (drt);
    free (hvrt);

    return (i);
}

s_route (xs, ys, xd, yd)
    int xs, ys, xd, yd;
/******************************************************************\
* 								   *
*  Segment route: <xs,ys> and <xd,yd> of a *selected* net will be  *
*  connected by a wire. No action is taken if they are already	   *
*  connected. Routing starts from <xd,yd>, therefore it is more	   *
*  efficient if <xs,ys> is part of the larger object.		   *
* 								   *
\******************************************************************/
{   int     r, lx, ly, dpin (), plt ();

    if (!(pcb[ys][xs] & pcb[yd][xd] & selb))
	err ("S-route: unselected net", xs, ys, xd, yd);

    lx = abs (xs - xd);
    ly = abs (ys - yd);

    if (!RT_sel || (lx + ly) < 10)
	return (S_route (xs, ys, xd, yd));

    r = 0;
    if (pcb[ys][xs] & ahb && pcb[yd][xd] & ahb)
	r = filter (xs, ys, xd, yd);/* crude attempt		 */
    if (!r) {
	if (lx > ly && ly < K1)	/* simple horizontal run	 */
	    r = a_route (xs, ys, xd, yd, s1b);
	else if (lx < ly && lx < K1)/* simple vertical run	 */
	    r = a_route (xs, ys, xd, yd, s2b);
	else
	    r = b_route (xs, ys, xd, yd);/* non-trivial run	 */
    }
    return (r);
}

a_route (xs, ys, xd, yd, sd)
    int xs, ys, xd, yd, sd;
/***************************************************************************\
* 									    *
*  a-route: connect <xd,yd> to <xs,ys> with a single side run (side=<sd>).  *
*  prerequisites: <xd,yd> was de-selected to avoid shortcuts.		    *
*                 <x?,y?> must be centered if on a hole.		    *
* 									    *
\***************************************************************************/
{
    int     i;

    if (!(pcb[yd][xd] & ahb) && ((pcb[yd][xd] & vec) != sd)) {
				/* start on wrong side		 */
	return (0);		/* not yet implemented		 */
    }

    cr_gmaze (xs, ys, xd, yd, K2);/* create maze		 */

    i = (sd == s1b) ? maze_run1 (xd, yd) : maze_run2 (xd, yd);

    if (!i) {			/* failed?			 */
	i = *(abm + (xs - ox + (ys - oy) * sx));
	i = ((sd == s1b) ? i : i >> 4) & MSK1;
	i = i == START || ((i == NOGOD) && !(pcb[ys][xs] & (sd ^ vec)));
				/* =1 if already connected	 */
    }

    free (abm);			/* release memory		 */

    return (i);
}

b_route (xs, ys, xd, yd)	/* 2 side L-route		 */
    int xs, ys, xd, yd;
{
    int     i;
    static int  lst = s1b;	/* last side			 */

    switch (rt_str) {		/* select side to start		 */
	default: 		/* alternating preferences	 */
	    lst = (pcb[yd][xd] & ahb) ? vec ^ lst : pcb[yd][xd] & vec;
	    break;
	case 1: 		/* prefere side 1		 */
	    lst = (pcb[yd][xd] & ahb) ? s1b : pcb[yd][xd] & vec;
	    break;
	case 2: 		/* prefere side 2		 */
	    lst = (pcb[yd][xd] & ahb) ? s2b : pcb[yd][xd] & vec;
	    break;
    }

    if (!(i = l_route (xs, ys, xd, yd, lst)) && (pcb[yd][xd] & ahb)) {
	if((i = l_route (xs, ys, xd, yd, lst ^ vec)))
	    lst ^= vec;
    }

    if (!i && (abs (xs - xd) + abs (ys - yd) > K4)) {
        viahcnt = 0;
	i = (lst == s1b) ? L1_route (xs, ys, xd, yd) :
			   L2_route (xs, ys, xd, yd);
	if (!i && (pcb[yd][xd] & ahb)) {
	    viahcnt = 0;
	    i = (lst == s2b) ? L1_route (xs, ys, xd, yd) :
			       L2_route (xs, ys, xd, yd);
	    lst ^= (i) ? vec : 0;
	}
    }

    return (i);
}

l_route (xs, ys, xd, yd, sd)	/* 2 side L-route		 */
    int xs, ys, xd, yd, sd;
{
    int i, j, x, y, x1, y1, x2, y2, vh_key();
    int ox1, oy1, sx1, sy1, ox2, oy2, sx2, sy2;
    char *t, *t1, *abm1, *abm2;

    if (sd == s1b) {		/* start on side 1		 */
	cr_gmaze (xd, yd, xs, yd, K3);
	if (maze_run1 (xd, yd)) {/* surprise: done		 */
	    free (abm);
	    return (1);
	}
	x = (xs > xd) ? xs - K3 : xs + K3;
	if (x <= ox || x >= ox + sx - 1)
	    x = (xd + xs) / 2;
	t = abm + (x - ox);
	for (i = 0; i <= 2 * K3; i++) {
	    if (*t & HDT)
		break;
	    t += sx;
	}
	if (i > 2 * K3) {
	    free (abm);		/* failed to reach via-area	 */
	    return (0);
	}}
    else {			/* start on side 2		 */
	cr_gmaze (xd, yd, xd, ys, K3);
	if (maze_run2 (xd, yd)) {/* surprise: done		 */
	    free (abm);
	    return (1);
	}
	y = (ys > yd) ? ys - K3 : ys + K3;
	if (y <= oy || y >= oy + sy - 1)
	    y = (yd + ys) / 2;
	t = abm + (y - oy) * sx;
	for (i = 0; i <= 2 * K3; i++) {
	    if (*t & HDT << 4)
		break;
	    t++;
	}
	if (i > 2 * K3) {
	    free (abm);		/* failed to reach via-area	 */
	    return (0);
	}
    }

    abm1 = abm;			/* save aux bit map 1		 */
    ox1 = ox;
    oy1 = oy;
    sx1 = sx;
    sy1 = sy;

    if (sd == s1b) {		/* start on side 1		 */
	cr_gmaze (xs, ys, xs, yd, K3);
	if (maze_run2 (xs, ys)) {/* surprise: done		 */
	    free (abm1);
	    free (abm);
	    return (1);
	}}
    else {			/* start on side 2		 */
	cr_gmaze (xs, ys, xd, ys, K3);
	if (maze_run1 (xs, ys)) {/* surprise: done		 */
	    free (abm1);
	    free (abm);
	    return (1);
	}
    }

    abm2 = abm;			/* save aux bit map 2		 */
    ox2 = ox;
    oy2 = oy;
    sx2 = sx;
    sy2 = sy;

    x1 = ((ox > ox1) ? ox : ox1) + 1;/* get via-hole area	 */
    y1 = ((oy > oy1) ? oy : oy1) + 1;
    x2 = ((ox + sx > ox1 + sx1) ? ox1 + sx1 : ox + sx) - 2;
    y2 = ((oy + sy > oy1 + sy1) ? oy1 + sy1 : oy + sy) - 2;

    if (x1 > x2 || y1 > y2)
	err ("b_route: 0-area", x1, y1, x2, y2);

    color (ishb | selb, ishb | selb);
    i = 0;
    for (y = (y1 + 1) & 0xfffffffe; y <= y2; y += 2)
	for (x = (x1 + 1) & 0xfffffffe; x <= x2; x += 2) {
	    t = abm + (x - ox + (y - oy) * sx);
	    t1 = abm1 + (x - ox1 + (y - oy1) * sx1);
	    if ((((sd == s1b) && (*t1 & HDT) && (*t & HDT << 4)) ||
		 ((sd == s2b) && (*t & HDT) && (*t1 & HDT << 4)))) {
		vhct[i].t = t;
		vhct[i].c = (sd == s1b) ? vh_cost (t1, sx1, t, sx) :
					  vh_cost (t, sx, t1, sx1);
		if (sd == s1b)
		    vhct[i].c += ((*t1 & 1) ? 0 : K8) +
				 ((*t & 0x10) ? 0 : K8);
		else
		    vhct[i].c += ((*t1 & 0x10) ? 0 : K8) +
				 ((*t & 1) ? 0 : K8);
		i++;
	    }
	}

    qsort (vhct, i, sizeof (vhct[0]), vh_key);

    for (j = 0; j < i; j++) {
	t = vhct[j].t;
	y = (int) (t - abm);
	x = ox + y % sx;
	y = oy + y / sx;
	if (!pin (x, y)) {	/* got via hole			 */
	    t1 = abm1 + (x - ox1 + (y - oy1) * sx1);

	    mz_done (t, (sd == s1b) ? 7 & ((*t) >> 4) : 7 & *t, vec ^ sd);

	    abm = abm1;		/* restore aux bit map 1	 */
	    ox = ox1;
	    oy = oy1;
	    sx = sx1;
	    sy = sy1;
	    set_dir ();

	    if (mz_chk (t1, (sd == s2b) ? 7 & ((*t1) >> 4) : 7 & *t1, sd)){
				/* got a problem		 */
		free (abm);
		cr_maze (ox, oy, sx, sy);/* redo first maze	 */
		if (((sd == s1b) && maze_run1 (x, y)) ||
		    ((sd == s2b) && maze_run2 (x, y))) { /* recovered	*/
		    free (abm);
		    free (abm2);
		    return (1);
		}
		free (abm);	/* recovery failed		 */

		abm = abm2;	/* restore aux bit map 2	 */
		ox = ox2;
		oy = oy2;
		sx = sx2;
		sy = sy2;
		set_dir ();
	        mz_undone (t, (sd == s1b) ? 7 & ((*t) >> 4) : 7 & *t, vec ^ sd);
		free (abm);
		color (0, selb | ishb);
		dpin (x, y);	/* remove hole			 */
		return (0);
	    }
	    mz_done (t1, (sd == s2b) ? 7 & ((*t1) >> 4) : 7 & *t1, sd);
	    free (abm);

	    return (1);
	}
    }

    free (abm);
    free (abm1);
    return (0);			/* unsuccessful return		 */
}

vh_key (a, b)			/* sort key for via-holes	 */
    struct vht *a, *b;
{
    return ((a -> c > b -> c) - (a -> c < b -> c));
}

vh_cost (t1, sx1, t2, sx2)	/* compute via-hole cost	 */
    char *t1, *t2;
    int sx1, sx2;
{
    int     c, dirt[8];

    c = 0;			/* initial cost			 */

    dirt[0] = 1;
    dirt[1] = 1 + sx1;
    dirt[2] = sx1;
    dirt[3] = sx1 - 1;
    dirt[4] = -1;
    dirt[5] = -sx1 - 1;
    dirt[6] = -sx1;
    dirt[7] = 1 - sx1;

    do {			/* count length on side 1	 */
	c++;
	t1 += dirt[7 & *t1];
    } while (*t1 & HDT);

    dirt[1] = 1 + sx2;
    dirt[2] = sx2;
    dirt[3] = sx2 - 1;
    dirt[5] = -sx2 - 1;
    dirt[6] = -sx2;
    dirt[7] = 1 - sx2;

    do {			/* count length on side 2	 */
	c++;
	t2 += dirt[7 & ((*t2) >> 4)];
    } while (*t2 & HDT << 4);

    return (c);
}

L1_route (xs, ys, xd, yd)
    int xs, ys, xd, yd;
/***********************************************************************\
* 								        *
*  Start on side 1 for an connection between <xs,ys> and <xd,yd>.       *
*  The wire may change sides several times. L1_route calls L2_route     *
*  and vice versa. Routing is aborted if no significant progress        *
*  is made in one step. Routing starts at <xd,yd> and works backwards.  *
*  If the distance between <xs,ys> and <xd,yd> is less than K4,	        *
*  l_route is used.						        *
* 								        *
\***********************************************************************/
{
    int i, j, x, y, x1, y1, x2, y2, sx1, sy1, ox1, oy1, c, vh_key(), xl;
    char *t, *abm1;

    if (abs (ys - yd) < K1)	/* single side run only		 */
	return (a_route (xs, ys, xd, yd, s1b));

    if (abs (xd - xs) + abs (yd - ys) <= K4)
				/* short net: use l_route	 */
	return (l_route (xs, ys, xd, yd, s1b));

    if (viahcnt > K6)		/* limit the number of via holes */
	return (0);

    cr_gmaze (xd, yd, xs, yd, K3);/* create maze		 */

    if (maze_run1 (xd, yd)) {
	free (abm);
	return (1);		/* successful termination	 */
    }

    if (xs > xd) {		/* check direction		 */
	x1 = K3;
	x2 = sx - 2;}
    else {
	x1 = sx - K3 - 1;
	x2 = 1;
    }

    while (abs (x1 - x2) > 1) {	/* check max. extension of maze  */
	x = (x1 + x2) >> 1;
	t = abm + (sx + x);
	for (i = 0; i < 2 * K3 - 1; (t += sx, i++))
	    if (*t & HDT)
		break;
	if (i >= 2 * K3 - 1)	/* no trace			 */
	    x2 = x;
	else
	    x1 = x;
    }

    xl = x + ox;

    while (abs (xl - xd) > K5) {/* try next leg 	 	 */

	if (xs > xd) {		/* locate via-hole area		 */
	    x2 = xl;
	    x1 = xl - 2 * K3;
	}
	else {
	    x1 = xl;
	    x2 = xl + 2 * K3;
	}
	y1 = oy + 1;
	y2 = oy + sy - 2;

	i = 0;			/* collect potential via points	 */
	for (y = (y1 + 1) & 0xfffffffe; y <= y2; y += 2)
	    for (x = (x1 + 1) & 0xfffffffe; x <= x2; x += 2) {
		t = abm + (x - ox + (y - oy) * sx);
		if (*t & HDT) {
		    vhct[i].t = t;
		    c = abs (x - xs) + abs (y - ys);
		    c += (*t & 1) ? 0 : K8;
		    do {	/* count length (for cost)	 */
			c++;
			t += dir[7 & *t];
		    } while (*t & HDT);
		    vhct[i++].c = c;
		}
	    }

	qsort (vhct, i, sizeof (vhct[0]), vh_key);/* check best first */

	color (ishb | selb, ishb | selb);/* try to create a via hole */
	for (j = 0; j < i; j++) {
	    t = vhct[j].t;
	    y = (int) (t - abm);
	    x = ox + y % sx;
	    y = oy + y / sx;
	    if (!pin (x, y)) {	/* got a via hole		 */
		viahcnt++;
		mz_done (t, 7 & *t, s1b);
		abm1 = abm;	/* save bit-map			 */
		sx1 = sx;
		sy1 = sy;
		ox1 = ox;
		oy1 = oy;
		if (L2_route (xs, ys, x, y)) {/* done		 */
		    free (abm1);
		    return (1);
		}		/* success			 */
		else {
		    color (0, ishb | selb);
		    dpin (x, y);/* remove pin			 */
		    viahcnt--;
		    abm = abm1;	/* restore bitmap		 */
		    sx = sx1;
		    sy = sy1;
		    ox = ox1;
		    oy = oy1;
		    set_dir ();
		    mz_undone (t, 7 & *t, s1b);
		    break;	/* failure			 */
		}
	    }
	}

	if (viahcnt > K7)
	    break;		/* no retries at this level	 */
	xl = (xl + xd) / 2;
    }
    free (abm);
    return (0);			/* via allocation failure	 */
}

L2_route (xs, ys, xd, yd)
    int xs, ys, xd, yd;
/***********************************************************************\
* 								        *
*  Start on side 2 for an connection between <xs,ys> and <xd,yd>.       *
*  The wire may change sides several times. L2_route calls L1_route     *
*  and vice versa. Routing is aborted if no significant progress        *
*  is made in one step. Routing starts at <xd,yd> and works backwards.  *
*  If the distance between <xs,ys> and <xd,yd> is less than K4,	        *
*  l_route is used.						        *
* 								        *
\***********************************************************************/
{
    int i, j, x, y, x1, y1, x2, y2, sx1, sy1, ox1, oy1, c, vh_key(), yl;
    char *t, *abm1;

    if (abs (xs - xd) < K1)	/* single side run only		 */
	return (a_route (xs, ys, xd, yd, s2b));

    if (abs (xd - xs) + abs (yd - ys) <= K4)
				/* short net: use l_route	 */
	return (l_route (xs, ys, xd, yd, s2b));

    if (viahcnt > K6)
	return (0);		/* too many via holes		 */

    cr_gmaze (xd, yd, xd, ys, K3);/* create maze		 */

    if (maze_run2 (xd, yd)) {
	free (abm);
	return (1);		/* successful termination	 */
    }

    if (ys > yd) {		/* check direction		 */
	y1 = K3;
	y2 = sy - 2;}
    else {
	y1 = sy - K3 - 1;
	y2 = 1;
    }

    while (abs (y1 - y2) > 1) {	/* check max. extension of maze  */
	y = (y1 + y2) >> 1;
	t = abm + (sx * y + 1);
	for (i = 0; i < 2 * K3 - 1; (t++, i++))
	    if (*t & HDT << 4)
		break;
	if (i >= 2 * K3 - 1)	/* no trace			 */
	    y2 = y;
	else
	    y1 = y;
    }

    yl = y + oy;

    while (abs (yl - yd) > K5) {/* try next leg			 */

	if (ys > yd) {		/* locate via-hole area		 */
	    y2 = yl;
	    y1 = yl - 2 * K3;}
	else {
	    y1 = yl;
	    y2 = yl + 2 * K3;
	}
	x1 = ox + 1;
	x2 = ox + sx - 2;

	i = 0;			/* collect potential via points	 */
	for (y = (y1 + 1) & 0xfffffffe; y <= y2; y += 2)
	    for (x = (x1 + 1) & 0xfffffffe; x <= x2; x += 2) {
		t = abm + (x - ox + (y - oy) * sx);
		if (*t & HDT << 4) {
		    vhct[i].t = t;
		    c = abs (x - xs) + abs (y - ys);
		    c += (*t & 0x10) ? 0 : K8;
		    do {	/* count length (for cost)	 */
			c++;
			t += dir[7 & ((*t) >> 4)];
		    } while (*t & HDT << 4);
		    vhct[i++].c = c;
		}
	    }

	qsort (vhct, i, sizeof (vhct[0]), vh_key);/* check best first */

	color (ishb | selb, ishb | selb);/* try to create a via hole */
	for (j = 0; j < i; j++) {
	    t = vhct[j].t;
	    y = (int) (t - abm);
	    x = ox + y % sx;
	    y = oy + y / sx;
	    if (!pin (x, y)) {	/* got a via hole		 */
		viahcnt++;
		mz_done (t, 7 & ((*t) >> 4), s2b);
		abm1 = abm;	/* save bit-map			 */
		sx1 = sx;
		sy1 = sy;
		ox1 = ox;
		oy1 = oy;
		if (L1_route (xs, ys, x, y)) {/* done		 */
		    free (abm1);
		    return (1);
		}		/* success			 */
		else {
		    color (0, ishb | selb);
		    dpin (x, y);/* remove pin			 */
		    viahcnt--;
		    abm = abm1;	/* restore bitmap		 */
		    sx = sx1;
		    sy = sy1;
		    ox = ox1;
		    oy = oy1;
		    set_dir ();
		    mz_undone (t, 7 & ((*t) >> 4), s2b);
		    break;	/* failure			 */
		}
	    }
	}

	if (viahcnt > K7)
	    break;		/* no retries at this level	 */
	yl = (yl + yd) / 2;
    }

    free (abm);
    return (0);			/* via allocation failure	 */
}
!E!O!F!
#
# type    sh /usru0/agn/pcb/distr/../usenet/part6   to unpack this archive.
#
echo extracting pmain.c...
cat >pmain.c <<'!E!O!F!'
/***************************************************************\
*								*
*	PCB program						*
*								*
*	Main section						*
*								*
*	(c) 1985		A. Nowatzyk			*
*								*
\***************************************************************/

#include <stdio.h>
#include "pparm.h"
#define mainpgm 1		/* This is the main pgm    */
#include "pcdst.h"

main (argc, argv)
    int argc;
    char *argv[];
{

    if (argc == 2 && !strcmp (argv[1], "-b")) {
	printf ("PCB is running in batch-autoroute mode\n");
	batch = 1;
    }

    if (argc == 2 && !strcmp (argv[1], "-s")) {
	printf ("PCB is running in batch-straight mode\n");
	batch = 2;
    }

    init ();			/* initialize environement */

    rdnl ();			/* read net list	   */


    if (batch && !ck_placed ())
	err ("-Please place components first", 0, 0, 0, 0);
	    
    if      (batch == 1)
	autor ();		/* start autorouting	   */
    else if (batch == 2)
	straight_all ();	/* straight wires	   */
    else
	cmd_loop ();		/* edit loop		   */

    printf ("Have a nice day\n");
    finish ();
}
!E!O!F!
#
# type    sh /usru0/agn/pcb/distr/../usenet/part6   to unpack this archive.
#
echo extracting pmap.c...
cat >pmap.c <<'!E!O!F!'
/***************************************************************\
*								*
*	PCB program						*
*								*
*	Bitmap I/O section					*
*								*
*	(c) 1985		A. Nowatzyk			*
*								*
\***************************************************************/

#include <stdio.h>
#include <pwd.h>
#include "pparm.h"
#include "pcdst.h"

#define bmapw 264		/* bitmap width (in bytes)	 */
#define BMF "/usr/vlsi/tmp/PCB"	/* bitmap file prefix		 */
#define SPF1 "/usr/spool/vpd/tmp"	/* spool file prefix 	 */
#define SPF2 "/usr/spool/vpd/dfa"	/* spool file prefix	 */
#define DAE "/usr/lib/vpd"	/* spool daemon			 */


pntbm ()			/* print bit map on versatek	 */
{
    char    bname[40], sname[40];
    int     pid, bch;
    static int  cnt = 0;
    FILE *sf, *fopen ();
    extern struct passwd  *getpwuid ();

    if (V.BSY > bmapw * 4) {
	printf ("Sorry, int Bitmap too wide for single page at this scale\n");
	return;
    }

    pid = getpid ();		/* get process id		 */
    sprintf (bname, "%s%d.%d", BMF, pid, ++cnt);
    bch = creat (bname, 0x1e4);
    if (bch < 0) {
	printf ("Could not open bitmap output file\n");
	return;
    };
    wbmap (bch);		/* write the bitmap		 */
    close (bch);		/* close bit map file		 */

    sprintf (sname, "%s%d.%d", SPF1, pid, cnt);
    sf = fopen (sname, "w");
    if (sf == nil) {
	printf ("Could not open spool entry file\n");
	return;
    };
    fprintf (sf, "L%s : PC-Board preview (%5.2f by %5.2f cm)       \n",
	     getpwuid (getuid ()) -> pw_gecos,
	     (V.BSX / rsun) * 0.254, (V.BSY / rsun) * 0.254);
    fprintf (sf, "B%d components with %d holes connected by %d nets\n",
	     V.ncp, V.nch, V.nnh);
    fprintf (sf, "BCreated by PCB V%d.%d\n", V.pver / 100, V.pver % 100);
    fprintf (sf, "C%s\nU%s\n", bname, bname);
    fclose (sf);

    sprintf (bname, "%s%d.%d", SPF2, pid, cnt);
    link (sname, bname);
    unlink (sname);
    if (vfork () == 0)
	execl (DAE, "vpd", 0);
}

wbmap(bch)				/* write Bit map		 */
    int bch;
{
    char   line0[bmapw], line1[bmapw], buf0[ymax], buf1[ymax],
           *z1, *p, t0, t1;
    register char *q0, *q1, *z0;
    register int k0, k1;
    int     i, j;

    static int btab[16] = { 0x46, 0x00, 0xce, 0x88,
			    0x56, 0x10, 0xfe, 0xf8,
			    0xf6, 0x20, 0xee, 0xa8,
			    0xf6, 0x30, 0xfe, 0xf8  };

#define getbits0  k0 = btab[*q0 | (k0 & 2) | !(*p & t0)]; *(q0++) = k0 & 0xc
#define getbits1  k1 = btab[*q1 | (k1 & 2) | !(*p & t1)]; *(q1++) = k1 & 0xc

    t0 = ahb | fb | s1b;	/* layers to be plotted (solid)	 */
    t1 = s2b;			/* layers to be plotted (shaded) */

    for (i = ymax / 4; i < bmapw; ++i)
	line0[i] = line1[i] = 0;	/* pad with 0's		 */
    for (i = 0; i < ymax; ++i)
	buf0[i] = buf1[i] = 0;

    for (i = 0; i < xmax; i++) {
	p = &pcb[0][i];
	q0 = &buf0[0];
	q1 = &buf1[0];
	z0 = &line0[0];
	z1 = &line1[0];
	k0 = k1 = 0;
	for (j = 0; j < ymax; j += 4) {
	    getbits0; getbits1; p += xmax;
	    *z0 = (0xc0 & (k0 << 2)) | (0x80 & (k1 << 2));
	    *z1 = (0xc0 & k0) | (0x40 & k1);
	    getbits0; getbits1; p += xmax;
	    *z0 |= (0x30 & k0) | (0x20 & k1);
	    *z1 |= (0x30 & (k0 >> 2)) | (0x10 & (k1 >> 2));
	    getbits0; getbits1; p += xmax;
	    *z0 |= (0x0c & (k0 >> 2)) | (0x08 & (k1 >> 2));
	    *z1 |= (0x0c & (k0 >> 4)) | (0x04 & (k1 >> 4));
	    getbits0; getbits1; p += xmax;
	    *(z0++) |= (0x03 & (k0 >> 4)) | (0x02 & (k1 >> 4));
	    *(z1++) |= (0x03 & (k0 >> 6)) | (0x01 & (k1 >> 6));
	};
	write (bch, line0, bmapw);
	write (bch, line1, bmapw);
    };

#undef getbits0
#undef getbits1

}

  
!E!O!F!
#
# type    sh /usru0/agn/pcb/distr/../usenet/part6   to unpack this archive.
#
echo extracting pstat.c...
cat >pstat.c <<'!E!O!F!'
/***************************************************************\
*								*
*	PCB program						*
*								*
*	Statistics routines					*
*								*
*	(c) 1985		A. Nowatzyk			*
*								*
\***************************************************************/

#include <stdio.h>
#include "pparm.h"
#include "pcdst.h"

#define c_grid 32			/* cc - grid width	 */
#define pscale 20			/* size of project plot  */

static int s1_wlen, s2_wlen;		/* side 1/2 wire length	 */
static int vh_cnt;			/* via hole count	 */
static int seg_done;			/* segments done	 */
static int seg_tot;			/* segments total	 */
static int s_valid = 0;			/* =1 if cc statistic ok */

static int *cc_array = 0;		/* congestion cntr array */
static int nccx, nccy;			/* cca organization	 */
static int xpro[xmax], ypro[ymax];	/* net projections	 */
static int cca_tot, xp_tot, yp_tot;	/* totals		 */
static int n_vect;			/* number of vectors	 */

wire_sta ()			/* update wire statistic	 */
{
    struct nlhd *net;		/* preserve selection		 */
    register int i, j, x, y;
    register struct nlst *p;
    int wstat_hf (),  wstat_vf ();

    if (net = V.cnet)
	deseln (net);		/* deselect net (to prevent side effects) */

    s1_wlen = 0;		/* reset counter		 */
    s2_wlen = 0;
    vh_cnt = 0;
    seg_done = 0;
    seg_tot = 0;
    n_vect = 0;

    wthf = wstat_hf;
    wtvf = wstat_vf;

    for (i = 0; i < V.nnh; i++) {	/* scan nets		 */

	for (p = NH[i].lp; p; p = p -> n)
	    p -> mk = -1;		/* remove marks		 */

	for (j = 0, p = NH[i].lp; p; p = p -> n)
	    if (p -> mk == -1) {
		j++;
		x = p -> c -> x;
		y = p -> c -> y;
		wtrace (x, y, vec);
	    }

	seg_done += NH[i].l - j;
	seg_tot += (NH[i].l - 1);
    }

    if (net)				/* reselect net		 */
	selnet (net);
}

wstat_hf (x, y)				/* hole function for wire_sta */
    int x, y;
{
    register struct hole *hp;
    struct hole *fndh();

    if (pcb[y][x] & ishb)
	vh_cnt++;
    else {
	hp = fndh (x, y);
	if (!hp)
	    err ("wstat_hf: could not find hole", x, y, 0, 0);
	else
	    hp -> n -> mk = 0;
    }

    return 0;
}

wstat_vf (x1, y1, x2, y2)		/* vector function for wire_sta */
    int x1, y1, x2, y2;
{
    register int i, j;
    double sqrt ();

    n_vect++;

    i = x1 - x2;
    j = y1 - y2;

    i = sqrt ((double) (i * i) + (double) (j * j)) + 0.5;

    if (wtsb == s1b)
	s1_wlen += i;
    else
        s2_wlen += i;
}

cc_stat ()				/* congestion analysis		 */
{
    register int i, j, k, l, m, n;

    if (s_valid)
	return;				/* still valid		 */
    s_valid = 1;

    for (i = 0; i < V.BSX; i++)		/* clear counter arrays	 */
	xpro[i] = 0;	
    for (i = 0; i < V.BSY; i++)
	ypro[i] = 0;	

    if (!cc_array) {			/* allocate cca		 */
	nccx = (V.BSX - c_grid / 2) / c_grid + 1;
	nccy = (V.BSY - c_grid / 2) / c_grid + 1;
	cc_array = (int *) malloc (sizeof (int) * nccx * nccy);
    }
    j = nccx * nccy;

    for (i = 0; i < j; i++)
	cc_array[i] = 0;

    for (i = 0; i <V.nnh; i++) {

	for (j = NH[i].x1; j < NH[i].x2; j++)	/* update x-projection */
	    xpro[j]++;
	for (j = NH[i].y1; j < NH[i].y2; j++)	/* update y-projection */
	    ypro[j]++;

	for (j = NH[i].y1 / c_grid, k = NH[i].y2 / c_grid; j <= k; j++) {
	    l = j * nccx;
	    for (m = NH[i].x1 / c_grid, n = NH[i].x2 / c_grid; m <= n; m++)
		cc_array[l + m]++;
	}
    }

    for (i = 0, j = 0; i < V.BSX; i++)		/* get totals		*/
	j += xpro[i];
    xp_tot =j;

    for (i = 0, j = 0; i < V.BSY; i++)
	j += ypro[i];
    yp_tot =j;

    for (i = 0, j = 0, k = nccx * nccy; i < k; i++)
	j += cc_array[i];
    cca_tot = j;
}

flush_stat ()			/* invalidate statistics		 */
{
   s_valid = 0;
}

pgen_stat ()			/* print general statistics		 */
{
    register int i, j;
    double f, f1;

    Ferr_msg ("Collecting data");

    wire_sta ();		/* get statistics			*/
    cc_stat ();
    
    printf ("PCB Version: %d.%2d\n", V.pver / 100, V.pver % 100);

    f1 = 3.937007874;
    f1 *= rsun;

    for (i = j = V.ncp; i; j -= !strcmp (CP[--i].name, DELETED));
				/* count undeleted components		 */

    printf ("\nGeneral statistics:\n");
    printf ("\tBoard size: . . . . . . . . . . . . . . %5.2lf by %5.2lf cm\n",
	(double) V.BSX / f1, (double) V.BSY / f1);
    printf ("\tNumber of components: . . . . . . . . . %d\n", j);
    printf ("\tNumber of component holes:  . . . . . . %d\n", V.nch);
    printf ("\tCurrent number of via holes:  . . . . . %d\n", vh_cnt);

    for (i = 0, j = 0; i < V.nnh; i++)
	if (NH[i].l) j++;	/* count nets				 */

    printf ("\tNumber of nets: . . . . . . . . . . . . %d\n", j);
    printf ("\tNumber of point-to-point connections: . %d\n", seg_tot);

    printf ("\nRouting information:\n");

    for (i = 0, j = 0; i < V.nnh; i++)
	if (NH[i].f) j++;
    printf ("\tNumber of nets routed:  . . . . . . . . %-4d (%5.1lf%%)\n",
	j, (double) (100 * j) / (double) V.nnh);
    printf ("\tNumber of routed p-p connections: . . . %-4d (%5.1lf%%)\n",
	seg_done, (double) (100 * seg_done) / (double) seg_tot);
    printf ("\tWire length on side 1 (component):  . . %5.1lf cm\n",
	(double) s1_wlen / f1);
    printf ("\t            on side 2 (solder): . . . . %5.1lf cm\n",
	(double) s2_wlen / f1);
    printf ("\t            total:  . . . . . . . . . . %5.1lf cm\n",
	(double) (s1_wlen + s2_wlen) / f1);

    for (i = 0, j = 0; i < V.nnh; i++)
	j += abs (NH[i].x1 - NH[i].x2) + abs (NH[i].y1 - NH[i].y2);
    printf ("\t            estimated:  . . . . . . . . %5.1lf cm\n",
	(double) j / f1);

    printf ("\tNumber of staight wire segments:  . . . %d\n", n_vect);

    f1 = V.BSX * V.BSY;
    f1 /= 100 * rsun * rsun;		/* f1: area in sq inches */
    printf ("\tEquivalent density (14DIP / sqi): . . . %-5.2lf\n",
	(double) V.nch / (14.0 * f1));

    for (i = 0, f = 0.0, j = nccx * nccy; i < j; i++)
	f += cc_array[i] * cc_array[i];
    f1 = cca_tot;
    f1 /= j;
    printf ("\tCongestion index (1=evenly distributed) %5.3lf\n",
	f / ((double) j * f1 * f1));

    err_msg ("Done");
}

dis_pro ()		/* display wire desity projections	*/
{
    register int i, j, k, l;
    int x, y;

    cc_stat ();		/* update statistic			*/
    msg_off ();

    color (resb, resb);

    for (i = wx, j = wx + (512 /cz) - pscale, k = 1; i < j; i++)
	if (k < xpro[i])
	    k = xpro[i];		/* find  x max		*/

    l = wy + (482 / cz) - pscale;	/* plot x-scale		*/
    for (i = wx, j = wx + (512 /cz) - pscale; i < j; i++)
	plts (i, l, i, l + (pscale * xpro[i]) / k);

    for (i = wy, j = wy + (482 /cz) - pscale, k = 1; i < j; i++)
	if (k < ypro[i])
	    k = ypro[i];		/* find  y max		*/

    l = wx + (512 / cz) - pscale;	/* plot y-scale		*/
    for (i = wy, j = wy + (482 /cz) - pscale; i < j; i++)
	plts (l, i, l + (pscale * ypro[i]) / k, i);

    getcur (&x, &y);			/* wait for response	 */

    color (0, resb);

    rect (wx, wy + 482/cz - pscale - 1, wx + 512/cz + 1, wy + 482/cz + 2);
    rect (wx + 512/cz - pscale - 1, wy, wx + 512/cz + 2, wy + 482/cz + 1);

    msg_on ();
}

dis_cc ()			/* display congestion		*/
{
    register int i, j, k, l, m, n;
    int x, y, x1, x2, y1, y2;

    x1 = wx / c_grid;
    x2 = (wx + 512/cz -1) / c_grid;
    y1 = wy / c_grid;
    y2 = (wy + 482/cz -1) / c_grid;

    cc_stat ();

    for (i = y1, k = 1; i < y2; i++) {	/* find max desity */
	l = i * nccx;
	for (m = x1, n = x2; m < n; m++) {
	    j = cc_array[m + l];
	    if (k < j * j)
		k = j * j;
	}
    }

    msg_off ();
    color (resb, resb);

    k += k;
    for (i = y1; i < y2; i++) {		/* plot result		 */
	l = i * nccx;
        y = c_grid / 2 + c_grid * i;
	for (m = x1; m < x2; m++) {
	    x = c_grid / 2 + c_grid * m;
	    j = cc_array[m + l];
	    j *= j * c_grid;
	    j /= k;			/* get size of square */
	    rect (x - j, y - j, x + j, y + j);
	}
    }

    getcur (&x, &y);

    color (0, resb);
    rect ((wx - c_grid/2 < 0) ? 0 : wx - c_grid/2,
	  (wy - c_grid/2 < 0) ? 0 : wy - c_grid/2,
	   wx + 512/cz + c_grid/2, wy + 482/cz + c_grid/2);
    msg_on ();
}
!E!O!F!