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!