/* -*- tab-width: 4 -*- * * Electric(tm) VLSI Design System * * File: dbmath.c * Database transformation and mathematics support module * Written by: Steven M. Rubin, Static Free Software * * Copyright (c) 2000 Static Free Software. * * Electric(tm) is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * Electric(tm) is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with Electric(tm); see the file COPYING. If not, write to * the Free Software Foundation, Inc., 59 Temple Place, Suite 330, * Boston, Mass 02111-1307, USA. * * Static Free Software * 4119 Alpine Road * Portola Valley, California 94028 * info@staticfreesoft.com */ #include "global.h" #include "database.h" #include "egraphics.h" #include "efunction.h" #include "tecart.h" #include "tecgen.h" #include "tecschem.h" #include "usr.h" #include "drc.h" #include #include /* clipping directions */ #define LEFT 1 #define RIGHT 2 #define BOTTOM 4 #define TOP 8 static WINDOWPART *db_windowpartfree = NOWINDOWPART; /* top of free list of windows */ static INTBIG db_rectx[4] = {0, 0, 1, 1}; static INTBIG db_recty[4] = {0, 1, 1, 0}; static POLYGON *db_staticpolygons = NOPOLYGON; static INTBIG *db_primearray; /* array of small prime numbers */ static INTBIG db_primearraytotal = 0; /* size of small prime number array */ static INTBIG db_maxcheckableprime; /* max value that can be checked with array */ static POLYGON *db_freepolygons = NOPOLYGON; static void *db_polygonmutex = 0; /* mutex for polygon modules */ static void *db_primenumbermutex = 0; /* mutex for prime numbers */ /* prototypes for local routines */ static BOOLEAN db_addpointtopoly(INTBIG x, INTBIG y, POLYGON *poly); static void db_findconnectionpoint(INTBIG, INTBIG, INTBIG, INTBIG, float, float, float, INTBIG*, INTBIG*); static INTBIG db_quadrant(INTBIG, INTBIG); static void db_closestpointtoline(INTBIG, INTBIG, INTBIG, INTBIG, INTBIG, INTBIG, INTBIG*, INTBIG*); static VIEW *db_makepermanentview(CHAR*, CHAR*, INTBIG); static void db_clipedge(POLYGON*, POLYGON*, INTBIG, INTBIG); static BOOLEAN db_clip(INTBIG*, INTBIG*, INTBIG*, INTBIG*, INTBIG, INTBIG); static BOOLEAN db_lineintersect(INTBIG, INTBIG, INTBIG, INTBIG, POLYGON*); static BOOLEAN db_isprime(INTBIG); static BOOLEAN db_isachildof(NODEPROTO *parent, NODEPROTO *child); static int db_anglelistdescending(const void *e1, const void *e2); static BOOLEAN db_primeinit(void); static BOOLEAN db_extendprimetable(INTBIG length); static void db_deallocatepolygon(POLYGON *poly); /* * Routine to free all memory associated with this module. */ void db_freemathmemory(void) { REGISTER WINDOWPART *w; REGISTER POLYGON *poly; /* free all statically allocated polygons */ while (db_staticpolygons != NOPOLYGON) { poly = db_staticpolygons; db_staticpolygons = db_staticpolygons->nextpolygon; freepolygon(poly); } /* cleanup cached polygons */ while (db_freepolygons != NOPOLYGON) { poly = db_freepolygons; db_freepolygons = db_freepolygons->nextpolygon; db_deallocatepolygon(poly); } /* free all window partitions */ while (el_topwindowpart != NOWINDOWPART) { w = el_topwindowpart; el_topwindowpart = el_topwindowpart->nextwindowpart; freewindowpart(w); } /* free unused pool of window partitions */ while (db_windowpartfree != NOWINDOWPART) { w = db_windowpartfree; db_windowpartfree = db_windowpartfree->nextwindowpart; efree((CHAR *)w); } /* free miscellaneous allocations */ efree((CHAR *)el_libdir); if (db_primearraytotal != 0) efree((CHAR *)db_primearray); } /************************* TRANSFORMATION *************************/ #define ZE 0 /* fractional representation of 0 */ #define P1 (1<<30) /* fractional representation of 1 */ #define N1 (-1<<30) /* fractional representation of -1 */ /* * there are eight different standard transformation matrices that cover * all of the Manhattan transformations: * * +------+ +------+ * |^ | +-----------+ | | +-----------+ * | | | | | | | >| * | R0 | | R90 | | R180 | | R270 | * | | |< | | | | | * | | +-----------+ | v| +-----------+ * +------+ +------+ * * +------+ +------+ * +-----------+ | ^| +-----------+ | | * |< | | | | | | | * | R0T | | R90T | | R180T | |R270T | * | | | | | >| | | * +-----------+ | | +-----------+ |v | * +------+ +------+ * * Form 0 (R0): 0 rotation, no transposition: 1 0 * 0 1 * Form 1 (R90): 90 rotation, no transposition: 0 1 * -1 0 * Form 2 (R180): 180 rotation, no transposition: -1 0 * 0 -1 * Form 3 (R270): 270 rotation, no transposition: 0 -1 * 1 0 * Form 4 (R0T): 0 rotation, transposition: 0 -1 * -1 0 * Form 5 (R90T): 90 rotation, transposition: -1 0 * 0 1 * Form 6 (R180T): 180 rotation, transposition: 0 1 * 1 0 * Form 7 (R270T): 270 rotation, transposition: 1 0 * 0 -1 * * When element [2][2] of a transformation matrix is not equal to P1, then * that matrix is in standard form and the value of element [2][2] selects * from the eight forms above. */ /* the rotational contents of the eight standard forms */ static INTBIG db_matstyle[8][2][2] = { {{P1, ZE}, {ZE, P1}}, {{ZE, P1}, {N1, ZE}}, {{N1, ZE}, {ZE, N1}}, {{ZE, N1}, {P1, ZE}}, {{ZE, N1}, {N1, ZE}}, {{N1, ZE}, {ZE, P1}}, {{ZE, P1}, {P1, ZE}}, {{P1, ZE}, {ZE, N1}} }; /* the transpose of the eight standard forms */ static INTBIG db_mattrans[8] = {0, 3, 2, 1, 4, 5, 6, 7}; /* the determinants of the eight standard forms */ static INTBIG db_determinant[8] = {1, 1, 1, 1, -1, -1, -1, -1}; /* the product of the eight standard forms (filled in by "db_initdatabase") */ static INTBIG db_matmult[8][8]; /* * routine to transform the point (x, y) through the transformation matrix in * the array "trans" and produce a transformed co-ordinate in (newx, newy) */ void xform(INTBIG x, INTBIG y, INTBIG *newx, INTBIG *newy, XARRAY trans) { REGISTER INTBIG px, py, t22; px = trans[2][0]; py = trans[2][1]; t22 = trans[2][2]; if (t22 != P1) { switch (t22) { case 0: *newx = x + px; *newy = y + py; return; case 1: *newx = -y + px; *newy = x + py; return; case 2: *newx = -x + px; *newy = -y + py; return; case 3: *newx = y + px; *newy = -x + py; return; case 4: *newx = -y + px; *newy = -x + py; return; case 5: *newx = -x + px; *newy = y + py; return; case 6: *newx = y + px; *newy = x + py; return; case 7: *newx = x + px; *newy = -y + py; return; } (void)db_error(DBBADTMAT|DBXFORM); return; } *newx = mult(trans[0][0],x) + mult(trans[1][0],y) + px; *newy = mult(trans[0][1],x) + mult(trans[1][1],y) + py; } /* * Takes a box specified by lx, hx, ly, hy, transforms it by trans, and * returns the box in lx, hx, ly, hy. The relationship between lx, hx, * ly, hy is preserved - i.e hx > lx, hy > ly */ void xformbox(INTBIG *lx, INTBIG *hx, INTBIG *ly, INTBIG *hy, XARRAY trans) { INTBIG tx, ty; REGISTER INTBIG lowx, highx, lowy, highy; lowx = *lx; highx = *hx; lowy = *ly; highy = *hy; xform(lowx, lowy, lx,ly, trans); *hx = *lx; *hy = *ly; xform(lowx, highy, &tx,&ty, trans); if (tx < *lx) *lx = tx; if (tx > *hx) *hx = tx; if (ty < *ly) *ly = ty; if (ty > *hy) *hy = ty; xform(highx, highy, &tx,&ty, trans); if (tx < *lx) *lx = tx; if (tx > *hx) *hx = tx; if (ty < *ly) *ly = ty; if (ty > *hy) *hy = ty; xform(highx, lowy, &tx,&ty, trans); if (tx < *lx) *lx = tx; if (tx > *hx) *hx = tx; if (ty < *ly) *ly = ty; if (ty > *hy) *hy = ty; } /* * routine to make a transformation matrix in the array "trans" which * rotates the nodeinst "ni" in its offset position. * The nodeinst is first translated to (0,0), then rotated to its proper * orientation, then translated back to its original position. */ void makerot(NODEINST *ni, XARRAY trans) { makeangle(ni->rotation, ni->transpose, trans); /* * the code used to be: (but caused roundoff errors) * trans[2][0] = (ni->lowx+ni->highx) / 2; * trans[2][1] = (ni->lowy+ni->highy) / 2; * xform(-trans[2][0], -trans[2][1], &trans[2][0], &trans[2][1], trans); */ trans[2][0] = ni->lowx + ni->highx; trans[2][1] = ni->lowy + ni->highy; xform(-trans[2][0], -trans[2][1], &trans[2][0], &trans[2][1], trans); trans[2][0] /= 2; trans[2][1] /= 2; } void makerotI(NODEINST *ni, XARRAY trans) { if (ni->transpose != 0) { makeangle(ni->rotation, ni->transpose, trans); } else { makeangle((3600 - ni->rotation)%3600, 0, trans); } /* * the code used to be: (but caused roundoff errors) * trans[2][0] = (ni->lowx+ni->highx) / 2; * trans[2][1] = (ni->lowy+ni->highy) / 2; * xform(-trans[2][0], -trans[2][1], &trans[2][0], &trans[2][1], trans); */ trans[2][0] = ni->lowx + ni->highx; trans[2][1] = ni->lowy + ni->highy; xform(-trans[2][0], -trans[2][1], &trans[2][0], &trans[2][1], trans); trans[2][0] /= 2; trans[2][1] /= 2; } void makeangle(INTBIG rot, INTBIG tra, XARRAY trans) { REGISTER INTBIG i; switch (rot) { case 0: if (tra) trans[2][2] = 4; else trans[2][2] = 0; break; case 900: if (tra) trans[2][2] = 5; else trans[2][2] = 1; break; case 1800: if (tra) trans[2][2] = 6; else trans[2][2] = 2; break; case 2700: if (tra) trans[2][2] = 7; else trans[2][2] = 3; break; default: /* get rotation matrix from sine and cosine */ trans[0][0] = trans[1][1] = cosine(rot); trans[0][1] = sine(rot); trans[1][0] = -trans[0][1]; /* re-organize if the matrix is transposed */ if (tra) { i = trans[0][0]; trans[0][0] = -trans[0][1]; trans[0][1] = -i; i = trans[1][1]; trans[1][1] = -trans[1][0]; trans[1][0] = -i; } trans[2][2] = P1; break; } /* fill in edge values */ trans[2][0] = trans[2][1] = ZE; trans[0][2] = trans[1][2] = ZE; } /* * routine to make transformation matrix in "trans" for translating points * in nodeinst "ni" to the outside environment. */ void maketrans(NODEINST *ni, XARRAY trans) { REGISTER NODEPROTO *np; np = ni->proto; transid(trans); /* * the code used to be: (but caused roundoff errors) * trans[2][0] = (ni->lowx + ni->highx)/2 - (np->lowx + np->highx)/2; * trans[2][1] = (ni->lowy + ni->highy)/2 - (np->lowy + np->highy)/2; */ trans[2][0] = (ni->lowx + ni->highx - np->lowx - np->highx)/2; trans[2][1] = (ni->lowy + ni->highy - np->lowy - np->highy)/2; } /* * routine to make transformation matrix in "trans" for translating points * from the outside environment to the nodeinst "ni". */ void maketransI(NODEINST *ni, XARRAY trans) { REGISTER NODEPROTO *np; np = ni->proto; transid(trans); /* * the code used to be: (but caused roundoff errors) * trans[2][0] = (np->lowx + np->highx)/2 - (ni->lowx + ni->highx)/2; * trans[2][1] = (np->lowy + np->highy)/2 - (ni->lowy + ni->highy)/2; */ trans[2][0] = (np->lowx + np->highx - ni->lowx - ni->highx)/2; trans[2][1] = (np->lowy + np->highy - ni->lowy - ni->highy)/2; } /* routine to create an identity transformation matrix in the array "matr" */ void transid(XARRAY matr) { /* make standard matrix with edge values zero */ matr[2][0] = matr[2][1] = matr[0][2] = matr[1][2] = ZE; matr[2][2] = 0; } /* * routine to copy from the transformation matrix in the array "mats" * to the transformation matrix in the array "matd" */ void transcpy(XARRAY mats, XARRAY matd) { REGISTER INTBIG i, j; if (mats[2][2] != P1) { /* standard matrix: copy edge values and matrix type */ matd[0][2] = mats[0][2]; matd[1][2] = mats[1][2]; matd[2][0] = mats[2][0]; matd[2][1] = mats[2][1]; matd[2][2] = mats[2][2]; return; } /* normal matrix: copy everything */ for(i=0; i<3; i++) for(j=0; j<3; j++) matd[i][j] = mats[i][j]; } /* * routine to multiply the transformation matrix in the array "mata" with * the transformation matrix in the array "matb" to produce the transformation * matrix in the array "matc" */ void transmult(XARRAY mata, XARRAY matb, XARRAY matc) { REGISTER INTBIG sum, ma, mb, i, j, k; ma = mata[2][2]; mb = matb[2][2]; if (ma != P1 && mb != P1) { /* standard matrix: compute edges, use tables for matrix type */ if (ma < 0 || ma > 7 || mb < 0 || mb > 7) { (void)db_error(DBBADTMAT|DBTRANSMULT); return; } matc[2][2] = db_matmult[ma][mb]; i = mata[2][0]; mata[2][0] = mata[0][2]; j = mata[2][1]; mata[2][1] = mata[1][2]; mata[2][2] = db_mattrans[ma]; xform(matb[0][2], matb[1][2], &matc[0][2], &matc[1][2], mata); mata[2][0] = i; mata[2][1] = j; mata[2][2] = ma; xform(mata[2][0], mata[2][1], &matc[2][0], &matc[2][1], matb); return; } /* normal matrices: make sure both are in full form */ if (ma != P1) { for(i=0; i<2; i++) for(j=0; j<2; j++) mata[i][j] = db_matstyle[ma][i][j]; mata[2][2] = P1; } if (mb != P1) { for(i=0; i<2; i++) for(j=0; j<2; j++) matb[i][j] = db_matstyle[mb][i][j]; matb[2][2] = P1; } /* multiply the matrices */ for(i=0; i<3; i++) for(j=0; j<3; j++) { sum = 0; for(k=0; k<3; k++) sum += mult(mata[i][k], matb[k][j]); matc[i][j] = sum; } mata[2][2] = ma; matb[2][2] = mb; } /* * routine to tell whether the array "trans" is a manhattan orientation. * returns true if so. */ BOOLEAN ismanhattan(XARRAY trans) { if (trans[2][2] != P1) return(TRUE); return(FALSE); } /* * routine to rotate label style "oldstyle" according to the rotation factor * in "trans", returning the new rotation factor */ static INTBIG db_textstyle[8] = {TEXTLEFT, TEXTBOTLEFT, TEXTBOT, TEXTBOTRIGHT, TEXTRIGHT, TEXTTOPRIGHT, TEXTTOP, TEXTTOPLEFT}; static INTBIG db_texttranspose[8] = {TEXTTOP, TEXTTOPRIGHT, TEXTRIGHT, TEXTBOTRIGHT, TEXTBOT, TEXTBOTLEFT, TEXTLEFT, TEXTTOPLEFT}; INTBIG rotatelabel(INTBIG oldstyle, INTBIG rotation, XARRAY trans) { REGISTER INTBIG i; /* if text style is not offset, rotation not done */ if (oldstyle == TEXTCENT || oldstyle == TEXTBOX) return(oldstyle); /* cannot handle nonmanhattan rotations */ if (trans[2][2] == P1) return(oldstyle); /* find the label style */ for(i=0; i<8; i++) if (db_textstyle[i] == oldstyle) break; if (i >= 8) return(oldstyle); /* handle nontransposed transformation */ if (trans[2][2] <= 3) return(db_textstyle[(i + 2*trans[2][2] + rotation*2) % 8]); /* handle transposed transformation */ return(db_texttranspose[(i + 2*(trans[2][2]-4) + rotation*2) % 8]); } /************************* TRANSCENDENTAL MATH *************************/ static INTBIG db_sinetable[] = { 0x00000000,0x001C9870,0x003930DA,0x0055C939,0x00726187,0x008EF9BE, 0x00AB91D9,0x00C829D1,0x00E4C1A1,0x01015944,0x011DF0B3,0x013A87E9, 0x01571EE0,0x0173B593,0x01904BFC,0x01ACE214,0x01C977D7,0x01E60D3F, 0x0202A246,0x021F36E6,0x023BCB19,0x02585EDB,0x0274F224,0x029184F0, 0x02AE1739,0x02CAA8F9,0x02E73A2A,0x0303CAC6,0x03205AC9,0x033CEA2C, 0x035978E9,0x037606FB,0x0392945D,0x03AF2107,0x03CBACF6,0x03E83822, 0x0404C287,0x04214C1E,0x043DD4E3,0x045A5CCE,0x0476E3DB,0x04936A04, 0x04AFEF43,0x04CC7393,0x04E8F6ED,0x0505794D,0x0521FAAB,0x053E7B04, 0x055AFA50,0x0577788B,0x0593F5AE,0x05B071B4,0x05CCEC98,0x05E96653, 0x0605DEE0,0x06225639,0x063ECC59,0x065B4139,0x0677B4D5,0x06942726, 0x06B09827,0x06CD07D2,0x06E97621,0x0705E30F,0x07224E97,0x073EB8B1, 0x075B215A,0x0777888A,0x0793EE3D,0x07B0526C,0x07CCB513,0x07E9162B, 0x080575AF,0x0821D399,0x083E2FE3,0x085A8A88,0x0876E382,0x08933ACB, 0x08AF905E,0x08CBE436,0x08E8364B,0x0904869A,0x0920D51B,0x093D21CB, 0x09596CA2,0x0975B59B,0x0991FCB0,0x09AE41DD,0x09CA851B,0x09E6C664, 0x0A0305B4,0x0A1F4304,0x0A3B7E4E,0x0A57B78E,0x0A73EEBD,0x0A9023D5, 0x0AAC56D2,0x0AC887AE,0x0AE4B662,0x0B00E2EA,0x0B1D0D3F,0x0B39355C, 0x0B555B3C,0x0B717ED9,0x0B8DA02C,0x0BA9BF32,0x0BC5DBE3,0x0BE1F63A, 0x0BFE0E33,0x0C1A23C6,0x0C3636EF,0x0C5247A7,0x0C6E55EB,0x0C8A61B2, 0x0CA66AF9,0x0CC271BA,0x0CDE75EE,0x0CFA7790,0x0D16769C,0x0D32730A, 0x0D4E6CD6,0x0D6A63FA,0x0D865870,0x0DA24A34,0x0DBE393E,0x0DDA258A, 0x0DF60F12,0x0E11F5D0,0x0E2DD9C0,0x0E49BADB,0x0E65991B,0x0E81747C, 0x0E9D4CF8,0x0EB92288,0x0ED4F529,0x0EF0C4D3,0x0F0C9181,0x0F285B2F, 0x0F4421D6,0x0F5FE570,0x0F7BA5F9,0x0F97636B,0x0FB31DC0,0x0FCED4F2, 0x0FEA88FD,0x100639DA,0x1021E784,0x103D91F6,0x1059392A,0x1074DD1A, 0x10907DC2,0x10AC1B1A,0x10C7B51F,0x10E34BCA,0x10FEDF16,0x111A6EFD, 0x1135FB7B,0x11518488,0x116D0A21,0x11888C3F,0x11A40ADD,0x11BF85F6, 0x11DAFD83,0x11F67180,0x1211E1E7,0x122D4EB2,0x1248B7DD,0x12641D61, 0x127F7F39,0x129ADD60,0x12B637D0,0x12D18E83,0x12ECE175,0x130830A0, 0x13237BFE,0x133EC38A,0x135A073E,0x13754715,0x1390830A,0x13ABBB17, 0x13C6EF37,0x13E21F64,0x13FD4B99,0x141873D0,0x14339805,0x144EB831, 0x1469D44F,0x1484EC59,0x14A0004B,0x14BB101F,0x14D61BD0,0x14F12358, 0x150C26B1,0x152725D7,0x154220C4,0x155D1772,0x157809DC,0x1592F7FE, 0x15ADE1D0,0x15C8C74F,0x15E3A875,0x15FE853B,0x16195D9E,0x16343197, 0x164F0122,0x1669CC38,0x168492D5,0x169F54F3,0x16BA128E,0x16D4CB9E, 0x16EF8020,0x170A300D,0x1724DB61,0x173F8217,0x175A2428,0x1774C190, 0x178F5A49,0x17A9EE4E,0x17C47D99,0x17DF0826,0x17F98DEF,0x18140EEF, 0x182E8B20,0x1849027D,0x18637501,0x187DE2A7,0x18984B69,0x18B2AF42, 0x18CD0E2D,0x18E76824,0x1901BD23,0x191C0D23,0x19365821,0x19509E15, 0x196ADEFC,0x19851AD1,0x199F518C,0x19B9832B,0x19D3AFA7,0x19EDD6FA, 0x1A07F921,0x1A221615,0x1A3C2DD2,0x1A564052,0x1A704D90,0x1A8A5587, 0x1AA45831,0x1ABE558A,0x1AD84D8C,0x1AF24032,0x1B0C2D77,0x1B261556, 0x1B3FF7C9,0x1B59D4CC,0x1B73AC59,0x1B8D7E6A,0x1BA74AFC,0x1BC11208, 0x1BDAD38A,0x1BF48F7D,0x1C0E45DB,0x1C27F69F,0x1C41A1C4,0x1C5B4745, 0x1C74E71C,0x1C8E8146,0x1CA815BC,0x1CC1A479,0x1CDB2D79,0x1CF4B0B6, 0x1D0E2E2B,0x1D27A5D4,0x1D4117AA,0x1D5A83A9,0x1D73E9CC,0x1D8D4A0E, 0x1DA6A46A,0x1DBFF8DA,0x1DD9475A,0x1DF28FE4,0x1E0BD274,0x1E250F04, 0x1E3E4590,0x1E577612,0x1E70A086,0x1E89C4E6,0x1EA2E32D,0x1EBBFB56, 0x1ED50D5D,0x1EEE193C,0x1F071EEE,0x1F201E6E,0x1F3917B8,0x1F520AC6, 0x1F6AF794,0x1F83DE1C,0x1F9CBE59,0x1FB59846,0x1FCE6BDF,0x1FE7391F, 0x20000000,0x2018C07E,0x20317A93,0x204A2E3B,0x2062DB71,0x207B8230, 0x20942272,0x20ACBC34,0x20C54F70,0x20DDDC21,0x20F66242,0x210EE1CF, 0x21275AC2,0x213FCD17,0x215838C8,0x21709DD2,0x2188FC2E,0x21A153D9, 0x21B9A4CD,0x21D1EF05,0x21EA327D,0x22026F30,0x221AA519,0x2232D432, 0x224AFC78,0x22631DE5,0x227B3875,0x22934C23,0x22AB58EA,0x22C35EC5, 0x22DB5DAF,0x22F355A4,0x230B469E,0x2323309A,0x233B1392,0x2352EF81, 0x236AC463,0x23829234,0x239A58ED,0x23B2188B,0x23C9D108,0x23E18261, 0x23F92C8F,0x2410CF90,0x24286B5D,0x243FFFF2,0x24578D4B,0x246F1362, 0x24869233,0x249E09BA,0x24B579F1,0x24CCE2D4,0x24E4445F,0x24FB9E8C, 0x2512F157,0x252A3CBB,0x254180B4,0x2558BD3D,0x256FF251,0x25871FEC, 0x259E4609,0x25B564A3,0x25CC7BB7,0x25E38B3E,0x25FA9336,0x26119398, 0x26288C61,0x263F7D8B,0x26566713,0x266D48F4,0x26842329,0x269AF5AD, 0x26B1C07C,0x26C88392,0x26DF3EEA,0x26F5F27F,0x270C9E4D,0x27234250, 0x2739DE82,0x275072DF,0x2766FF63,0x277D840A,0x279400CE,0x27AA75AC, 0x27C0E29F,0x27D747A1,0x27EDA4B0,0x2803F9C6,0x281A46DF,0x28308BF7, 0x2846C909,0x285CFE10,0x28732B08,0x28894FED,0x289F6CBB,0x28B5816C, 0x28CB8DFD,0x28E19269,0x28F78EAC,0x290D82C1,0x29236EA4,0x29395251, 0x294F2DC3,0x296500F6,0x297ACBE5,0x29908E8C,0x29A648E7,0x29BBFAF2, 0x29D1A4A7,0x29E74604,0x29FCDF02,0x2A126F9F,0x2A27F7D6,0x2A3D77A3, 0x2A52EF00,0x2A685DEB,0x2A7DC45F,0x2A932256,0x2AA877CE,0x2ABDC4C2, 0x2AD3092E,0x2AE8450D,0x2AFD785B,0x2B12A314,0x2B27C534,0x2B3CDEB6, 0x2B51EF96,0x2B66F7D1,0x2B7BF761,0x2B90EE43,0x2BA5DC73,0x2BBAC1EC, 0x2BCF9EAA,0x2BE472A9,0x2BF93DE5,0x2C0E005A,0x2C22BA03,0x2C376ADC, 0x2C4C12E2,0x2C60B210,0x2C754862,0x2C89D5D4,0x2C9E5A61,0x2CB2D606, 0x2CC748BF,0x2CDBB288,0x2CF0135C,0x2D046B37,0x2D18BA16,0x2D2CFFF4, 0x2D413CCD,0x2D55709D,0x2D699B61,0x2D7DBD14,0x2D91D5B1,0x2DA5E536, 0x2DB9EB9E,0x2DCDE8E5,0x2DE1DD07,0x2DF5C801,0x2E09A9CD,0x2E1D8269, 0x2E3151D0,0x2E4517FE,0x2E58D4EF,0x2E6C88A0,0x2E80330C,0x2E93D430, 0x2EA76C08,0x2EBAFA8F,0x2ECE7FC2,0x2EE1FB9C,0x2EF56E1B,0x2F08D73A, 0x2F1C36F5,0x2F2F8D48,0x2F42DA30,0x2F561DA9,0x2F6957AE,0x2F7C883D, 0x2F8FAF50,0x2FA2CCE5,0x2FB5E0F8,0x2FC8EB84,0x2FDBEC86,0x2FEEE3FA, 0x3001D1DC,0x3014B629,0x302790DD,0x303A61F3,0x304D2969,0x305FE73B, 0x30729B64,0x308545E1,0x3097E6AE,0x30AA7DC8,0x30BD0B2B,0x30CF8ED3, 0x30E208BD,0x30F478E4,0x3106DF46,0x31193BDD,0x312B8EA8,0x313DD7A2, 0x315016C7,0x31624C14,0x31747785,0x31869916,0x3198B0C5,0x31AABE8D, 0x31BCC26A,0x31CEBC5A,0x31E0AC58,0x31F29261,0x32046E72,0x32164086, 0x3228089A,0x3239C6AC,0x324B7AB6,0x325D24B6,0x326EC4A8,0x32805A89, 0x3291E654,0x32A36807,0x32B4DF9F,0x32C64D17,0x32D7B06C,0x32E9099A, 0x32FA589F,0x330B9D77,0x331CD81D,0x332E0890,0x333F2ECB,0x33504ACB, 0x33615C8C,0x3372640C,0x33836146,0x33945438,0x33A53CDD,0x33B61B34, 0x33C6EF37,0x33D7B8E5,0x33E87838,0x33F92D2F,0x3409D7C6,0x341A77FA, 0x342B0DC6,0x343B9929,0x344C1A1E,0x345C90A2,0x346CFCB2,0x347D5E4B, 0x348DB56A,0x349E020A,0x34AE442A,0x34BE7BC5,0x34CEA8D9,0x34DECB62, 0x34EEE35C,0x34FEF0C6,0x350EF39B,0x351EEBD9,0x352ED97C,0x353EBC81, 0x354E94E4,0x355E62A4,0x356E25BB,0x357DDE29,0x358D8BE8,0x359D2EF7, 0x35ACC751,0x35BC54F5,0x35CBD7DE,0x35DB500A,0x35EABD75,0x35FA201D, 0x360977FF,0x3618C517,0x36280762,0x36373EDD,0x36466B86,0x36558D58, 0x3664A452,0x3673B070,0x3682B1B0,0x3691A80D,0x36A09386,0x36AF7417, 0x36BE49BD,0x36CD1475,0x36DBD43D,0x36EA8911,0x36F932EE,0x3707D1D2, 0x371665BA,0x3724EEA2,0x37336C88,0x3741DF69,0x37504742,0x375EA410, 0x376CF5D1,0x377B3C80,0x3789781D,0x3797A8A3,0x37A5CE10,0x37B3E860, 0x37C1F793,0x37CFFBA3,0x37DDF48F,0x37EBE255,0x37F9C4F0,0x38079C5E, 0x3815689D,0x382329AA,0x3830DF81,0x383E8A21,0x384C2987,0x3859BDB0, 0x38674698,0x3874C43E,0x3882369F,0x388F9DB8,0x389CF986,0x38AA4A07, 0x38B78F38,0x38C4C916,0x38D1F79F,0x38DF1AD0,0x38EC32A7,0x38F93F21, 0x3906403A,0x391335F2,0x39202045,0x392CFF30,0x3939D2B1,0x39469AC6, 0x3953576B,0x3960089F,0x396CAE5E,0x397948A7,0x3985D777,0x39925ACA, 0x399ED2A0,0x39AB3EF4,0x39B79FC6,0x39C3F512,0x39D03ED5,0x39DC7D0E, 0x39E8AFBA,0x39F4D6D6,0x3A00F260,0x3A0D0256,0x3A1906B6,0x3A24FF7C, 0x3A30ECA6,0x3A3CCE33,0x3A48A41F,0x3A546E69,0x3A602D0D,0x3A6BE00A, 0x3A77875E,0x3A832305,0x3A8EB2FF,0x3A9A3747,0x3AA5AFDD,0x3AB11CBD, 0x3ABC7DE6,0x3AC7D355,0x3AD31D08,0x3ADE5AFC,0x3AE98D30,0x3AF4B3A2, 0x3AFFCE4E,0x3B0ADD33,0x3B15E04E,0x3B20D79E,0x3B2BC320,0x3B36A2D3, 0x3B4176B3,0x3B4C3EBE,0x3B56FAF3,0x3B61AB50,0x3B6C4FD1,0x3B76E876, 0x3B81753C,0x3B8BF621,0x3B966B22,0x3BA0D43E,0x3BAB3173,0x3BB582BE, 0x3BBFC81E,0x3BCA0190,0x3BD42F13,0x3BDE50A4,0x3BE86641,0x3BF26FE9, 0x3BFC6D99,0x3C065F4F,0x3C10450A,0x3C1A1EC7,0x3C23EC85,0x3C2DAE41, 0x3C3763F9,0x3C410DAC,0x3C4AAB58,0x3C543CFA,0x3C5DC291,0x3C673C1B, 0x3C70A996,0x3C7A0B01,0x3C836058,0x3C8CA99B,0x3C95E6C7,0x3C9F17DB, 0x3CA83CD5,0x3CB155B3,0x3CBA6273,0x3CC36314,0x3CCC5793,0x3CD53FEF, 0x3CDE1C27,0x3CE6EC37,0x3CEFB01F,0x3CF867DD,0x3D01136E,0x3D09B2D2, 0x3D124607,0x3D1ACD0A,0x3D2347DB,0x3D2BB677,0x3D3418DD,0x3D3C6F0B, 0x3D44B8FF,0x3D4CF6B9,0x3D552835,0x3D5D4D73,0x3D656671,0x3D6D732D, 0x3D7573A6,0x3D7D67D9,0x3D854FC7,0x3D8D2B6C,0x3D94FAC7,0x3D9CBDD8, 0x3DA4749B,0x3DAC1F10,0x3DB3BD36,0x3DBB4F0A,0x3DC2D48B,0x3DCA4DB8, 0x3DD1BA8F,0x3DD91B0E,0x3DE06F35,0x3DE7B701,0x3DEEF272,0x3DF62185, 0x3DFD443A,0x3E045A8F,0x3E0B6482,0x3E126213,0x3E19533F,0x3E203806, 0x3E271065,0x3E2DDC5C,0x3E349BEA,0x3E3B4F0C,0x3E41F5C2,0x3E48900A, 0x3E4F1DE3,0x3E559F4C,0x3E5C1443,0x3E627CC7,0x3E68D8D6,0x3E6F2871, 0x3E756B94,0x3E7BA23F,0x3E81CC72,0x3E87EA29,0x3E8DFB65,0x3E940024, 0x3E99F865,0x3E9FE426,0x3EA5C367,0x3EAB9627,0x3EB15C63,0x3EB7161C, 0x3EBCC34F,0x3EC263FC,0x3EC7F822,0x3ECD7FBF,0x3ED2FAD2,0x3ED8695B, 0x3EDDCB58,0x3EE320C8,0x3EE869AB,0x3EEDA5FE,0x3EF2D5C1,0x3EF7F8F3, 0x3EFD0F93,0x3F0219A0,0x3F071719,0x3F0C07FD,0x3F10EC4A,0x3F15C401, 0x3F1A8F1F,0x3F1F4DA5,0x3F23FF90,0x3F28A4E1,0x3F2D3D96,0x3F31C9AE, 0x3F364928,0x3F3ABC04,0x3F3F2241,0x3F437BDD,0x3F47C8D8,0x3F4C0931, 0x3F503CE7,0x3F5463FA,0x3F587E68,0x3F5C8C30,0x3F608D52,0x3F6481CE, 0x3F6869A1,0x3F6C44CC,0x3F70134E,0x3F73D526,0x3F778A53,0x3F7B32D4, 0x3F7ECEA9,0x3F825DD1,0x3F85E04B,0x3F895617,0x3F8CBF34,0x3F901BA1, 0x3F936B5D,0x3F96AE69,0x3F99E4C2,0x3F9D0E69,0x3FA02B5D,0x3FA33B9E, 0x3FA63F2A,0x3FA93601,0x3FAC2023,0x3FAEFD8F,0x3FB1CE44,0x3FB49242, 0x3FB74988,0x3FB9F416,0x3FBC91EB,0x3FBF2306,0x3FC1A768,0x3FC41F10, 0x3FC689FC,0x3FC8E82E,0x3FCB39A3,0x3FCD7E5C,0x3FCFB659,0x3FD1E198, 0x3FD4001A,0x3FD611DE,0x3FD816E3,0x3FDA0F29,0x3FDBFAB1,0x3FDDD978, 0x3FDFAB80,0x3FE170C7,0x3FE3294E,0x3FE4D513,0x3FE67417,0x3FE8065A, 0x3FE98BDA,0x3FEB0498,0x3FEC7094,0x3FEDCFCC,0x3FEF2242,0x3FF067F4, 0x3FF1A0E2,0x3FF2CD0C,0x3FF3EC73,0x3FF4FF14,0x3FF604F1,0x3FF6FE0A, 0x3FF7EA5D,0x3FF8C9EB,0x3FF99CB4,0x3FFA62B7,0x3FFB1BF5,0x3FFBC86D, 0x3FFC681F,0x3FFCFB0A,0x3FFD8130,0x3FFDFA8F,0x3FFE6728,0x3FFEC6FA, 0x3FFF1A06,0x3FFF604B,0x3FFF99CA,0x3FFFC681,0x3FFFE672,0x3FFFF99D, 0x40000000}; /* * routine to return a fixed-point sine value for "n" (in tenth-degrees from 0 to * 3599) */ INTBIG sine(INTBIG n) { if (n <= 900) return(db_sinetable[n]); if (n <= 1800) return(db_sinetable[1800-n]); if (n <= 2700) return(-db_sinetable[n-1800]); return(-db_sinetable[3600-n]); } /* * routine to return a fixed-point cosine value for "n" (in tenth-degrees from 0 to * 3599) */ INTBIG cosine(INTBIG n) { if (n <= 900) return(db_sinetable[900-n]); if (n <= 1800) return(-db_sinetable[n-900]); if (n <= 2700) return(-db_sinetable[2700-n]); return(db_sinetable[n-2700]); } /* * routine to return the angle from point (x1,y1) to point (x2,y2) in tenth-degrees * where right-pointing is 0 and positive angles are counter-clockwise. */ INTBIG figureangle(INTBIG x1, INTBIG y1, INTBIG x2, INTBIG y2) { double dx, dy, ang; INTBIG iang; dx = x2 - x1; dy = y2 - y1; if (dx == 0.0 && dy == 0.0) { ttyputerr(_("Warning: domain violation while figuring angle")); return(0); } ang = atan2(dy, dx); if (ang < 0.0) ang += EPI*2.0; iang = rounddouble(ang * 1800.0 / EPI); return(iang); } /* * routine to return the angle from point (x1,y1) to point (x2,y2) in tenth-degrees * where right-pointing is 0 and positive angles are counter-clockwise. */ double ffigureangle(INTBIG x1, INTBIG y1, INTBIG x2, INTBIG y2) { double dx, dy, ang; dx = x2 - x1; dy = y2 - y1; if (dx == 0.0 && dy == 0.0) { ttyputerr(_("Warning: domain violation while figuring angle")); return(0); } ang = atan2(dy, dx); if (ang < 0.0) ang += EPI*2.0; return(ang); } /************************* PRIME NUMBERS *************************/ /* This table contains the first few hundred prime numbers */ static INTBIG db_small_primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463 }; #define NUMSMALLPRIMES (sizeof(db_small_primes) / SIZEOFINTBIG) /* * Routine to initialize the prime number tables. Returns true on error. */ BOOLEAN db_primeinit(void) { REGISTER INTBIG i; if (db_primearraytotal != 0) return(FALSE); if (db_multiprocessing) emutexlock(db_primenumbermutex); if (db_primearraytotal == 0) { db_primearray = (INTBIG *)emalloc(NUMSMALLPRIMES * SIZEOFINTBIG, db_cluster); if (db_primearray == 0) { if (db_multiprocessing) emutexunlock(db_primenumbermutex); return(TRUE); } for(i=0; i= db_primearraytotal) { if (db_multiprocessing) emutexlock(db_primenumbermutex); newtotal = db_primearraytotal * 2; if (length >= newtotal) newtotal = length + 100; newprimearray = (INTBIG *)emalloc(newtotal * SIZEOFINTBIG, db_cluster); if (newprimearray == 0) { if (db_multiprocessing) emutexunlock(db_primenumbermutex); return(TRUE); } for(i=0; i= db_maxcheckableprime) return(FALSE); for(i = 0; i < db_primearraytotal; i++) { m = db_primearray[i]; if (m * m >= n) break; if (n % m == 0) return(FALSE); } return(TRUE); } /* * Routine to return the "n"th prime number. * Prime #0 is 2, #1 is 3, #2 is 5... */ INTBIG getprime(INTBIG n) { if (n >= db_primearraytotal) { if (db_extendprimetable(n)) return(0); } return(db_primearray[n]); } /* * Returns the first prime over N, by checking all odd numbers * over N till it finds one. */ INTBIG pickprime(INTBIG n) { if (db_primeinit()) return(0); if (n >= db_maxcheckableprime) return(0); if (n % 2 == 0) n++; while (!db_isprime(n)) { n += 2; } return(n); } /************************* MISCELLANEOUS MATHEMATICS *************************/ /* * integer square-root. */ INTBIG intsqrt(INTBIG val) { REGISTER INTBIG guess, i; /* can only take square root of a positive number */ if (val <= 0) return(val); /* compute initial guess of square root */ guess = 0; i = val; while (i != 0) { guess = (guess << 1) | 1; i = i >> 2; } /* six iterations of Newton's approximation to square root */ for(i=0; i<6; i++) guess = (guess + val / guess) >> 1; return(guess); } /* * routine to compute the euclidean distance between point (x1,y1) and * point (x2,y2). This may require determining the hypotenuse of a triangle * by finding square roots, in which case an integer square-root subroutine * that uses Newton's method is called. */ INTBIG computedistance(INTBIG x1,INTBIG y1, INTBIG x2,INTBIG y2) { REGISTER INTBIG dx, dy, res; double fdx, fdy; dx = abs(x1 - x2); dy = abs(y1 - y2); if (dx == 0 || dy == 0) return(dx + dy); /* nonmanhattan distance: need to do square root */ if (dx <= 32767 && dy <= 32767) return(intsqrt(dx*dx + dy*dy)); /* do it in floating point */ fdx = dx; fdy = dy; res = rounddouble(sqrt(fdx*fdx + fdy*fdy)); return(res); } /* * routine to return true if the point (x,y) is on the line segment from * (x1,y1) to (x2,y2) */ BOOLEAN isonline(INTBIG x1, INTBIG y1, INTBIG x2, INTBIG y2, INTBIG x, INTBIG y) { /* trivial rejection if point not in the bounding box of the line */ if (x < mini(x1,x2)) return(FALSE); if (x > maxi(x1,x2)) return(FALSE); if (y < mini(y1,y2)) return(FALSE); if (y > maxi(y1,y2)) return(FALSE); /* handle manhattan cases specially */ if (x1 == x2) { if (x == x1) return(TRUE); return(FALSE); } if (y1 == y2) { if (y == y1) return(TRUE); return(FALSE); } /* handle nonmanhattan */ if (muldiv(x-x1, y2-y1, x2-x1) == y-y1) return(TRUE); return(FALSE); } /* * routine to determine the intersection of two lines and return that point * in (x,y). The first line is at "ang1" tenth-degrees and runs through (x1,y1) * and the second line is at "ang2" tenth-degrees and runs through (x2,y2). The * routine returns a negative value if the lines do not intersect. */ INTBIG intersect(INTBIG x1, INTBIG y1, INTBIG ang1, INTBIG x2, INTBIG y2, INTBIG ang2, INTBIG *x, INTBIG *y) { double fa1, fb1, fc1, fa2, fb2, fc2, fang1, fang2, fswap, fy; /* cannot handle lines if they are at the same angle */ if (ang1 == ang2) return(-1); /* also at the same angle if off by 180 degrees */ if (mini(ang1, ang2) + 1800 == maxi(ang1, ang2)) return(-1); fang1 = ang1 / 1800.0 * EPI; fang2 = ang2 / 1800.0 * EPI; fa1 = sin(fang1); fb1 = -cos(fang1); fc1 = -fa1 * ((double)x1) - fb1 * ((double)y1); fa2 = sin(fang2); fb2 = -cos(fang2); fc2 = -fa2 * ((double)x2) - fb2 * ((double)y2); if (fabs(fa1) < fabs(fa2)) { fswap = fa1; fa1 = fa2; fa2 = fswap; fswap = fb1; fb1 = fb2; fb2 = fswap; fswap = fc1; fc1 = fc2; fc2 = fswap; } fy = (fa2 * fc1 / fa1 - fc2) / (fb2 - fa2*fb1/fa1); *y = rounddouble(fy); *x = rounddouble((-fb1 * fy - fc1) / fa1); return(0); } /* * routine to determine the intersection of two lines and return that point * in (x,y). The first line is at "ang1" radians and runs through (x1,y1) * and the second line is at "ang2" radians and runs through (x2,y2). The * routine returns a negative value if the lines do not intersect. */ INTBIG fintersect(INTBIG x1, INTBIG y1, double fang1, INTBIG x2, INTBIG y2, double fang2, INTBIG *x, INTBIG *y) { double fa1, fb1, fc1, fa2, fb2, fc2, fswap, fy, fmin, fmax; /* cannot handle lines if they are at the same angle */ if (doublesequal(fang1, fang2)) return(-1); /* also at the same angle if off by 180 degrees */ if (fang1 < fang2) { fmin = fang1; fmax = fang2; } else { fmin = fang2; fmax = fang1; } if (doublesequal(fmin + EPI, fmax)) return(-1); fa1 = sin(fang1); fb1 = -cos(fang1); fc1 = -fa1 * ((double)x1) - fb1 * ((double)y1); fa2 = sin(fang2); fb2 = -cos(fang2); fc2 = -fa2 * ((double)x2) - fb2 * ((double)y2); if (fabs(fa1) < fabs(fa2)) { fswap = fa1; fa1 = fa2; fa2 = fswap; fswap = fb1; fb1 = fb2; fb2 = fswap; fswap = fc1; fc1 = fc2; fc2 = fswap; } fy = (fa2 * fc1 / fa1 - fc2) / (fb2 - fa2*fb1/fa1); *y = rounddouble(fy); *x = rounddouble((-fb1 * fy - fc1) / fa1); return(0); } /* * Routine to determine whether the line segment from (fx1,fy1) to (tx1,ty1) * intersects the line segment from (fx2,fy2) to (tx2,ty2). Returns true if * they do and sets the intersection point to (ix,iy). */ BOOLEAN segintersect(INTBIG fx1, INTBIG fy1, INTBIG tx1, INTBIG ty1, INTBIG fx2, INTBIG fy2, INTBIG tx2, INTBIG ty2, INTBIG *ix, INTBIG *iy) { REGISTER INTBIG ang1, ang2; ang1 = figureangle(fx1, fy1, tx1, ty1); ang2 = figureangle(fx2, fy2, tx2, ty2); if (intersect(fx1, fy1, ang1, fx2, fy2, ang2, ix, iy) >= 0) { if (*ix < mini(fx1, tx1) || *ix > maxi(fx1, tx1) || *iy < mini(fy1, ty1) || *iy > maxi(fy1, ty1)) return(FALSE); if (*ix < mini(fx2, tx2) || *ix > maxi(fx2, tx2) || *iy < mini(fy2, ty2) || *iy > maxi(fy2, ty2)) return(FALSE); return(TRUE); } return(FALSE); } /* * routine to find the intersection points between the circle at (icx,icy) with point (isx,isy) * and the line from (lx1,ly1) to (lx2,ly2). Returns the two points in (ix1,iy1) and (ix2,iy2). * Allows intersection tolerance of "tolerance". * Returns the number of intersection points (0 if none, 1 if tangent, 2 if intersecting). */ INTBIG circlelineintersection(INTBIG icx, INTBIG icy, INTBIG isx, INTBIG isy, INTBIG lx1, INTBIG ly1, INTBIG lx2, INTBIG ly2, INTBIG *ix1, INTBIG *iy1, INTBIG *ix2, INTBIG *iy2, INTBIG tolerance) { double fx, fy, radius, adjacent, angle, intangle, a1, a2, segx, segy, m, b, mi, bi; /* * construct a line that is perpendicular to the intersection line and passes * through the circle center. It meets the intersection line at (segx, segy) */ if (ly1 == ly2) { segx = icx; segy = ly1; } else if (lx1 == lx2) { segx = lx1; segy = icy; } else { /* compute equation of the line */ fx = lx1 - lx2; fy = ly1 - ly2; m = fy / fx; b = -lx1; b *= m; b += ly1; /* compute perpendicular to line through the point */ mi = -1.0/m; bi = -icx; bi *= mi; bi += icy; /* compute intersection of the lines */ segx = (bi-b) / (m-mi); segy = m * segx + b; } /* special case when line passes through the circle center */ if (segx == icx && segy == icy) { fx = isx - icx; fy = isy - icy; radius = sqrt(fx*fx + fy*fy); fx = lx2 - lx1; fy = ly2 - ly1; if (fx == 0.0 && fy == 0.0) { ttyputerr(_("Domain error doing circle/line intersection")); return(0); } angle = atan2(fy, fx); *ix1 = icx + rounddouble(cos(angle) * radius); *iy1 = icy + rounddouble(sin(angle) * radius); *ix2 = icx + rounddouble(cos(-angle) * radius); *iy2 = icy + rounddouble(sin(-angle) * radius); } else { /* * construct a right triangle with the three points: (icx, icy), (segx, segy), and (ix1,iy1) * the right angle is at the point (segx, segy) and the hypotenuse is the circle radius * The unknown point is (ix1, iy1), the intersection of the line and the circle. * To find it, determine the angle at the point (icx, icy) */ fx = isx - icx; fy = isy - icy; radius = sqrt(fx*fx + fy*fy); fx = segx - icx; fy = segy - icy; adjacent = sqrt(fx*fx + fy*fy); /* if they are within tolerance, accept */ if (fabs(adjacent - radius) < tolerance) { *ix1 = rounddouble(segx); *iy1 = rounddouble(segy); return(1); } /* if the point is outside of the circle, quit */ if (adjacent > radius) return(0); /* for zero radius, use circle center */ if (radius == 0.0) { *ix1 = *ix2 = icx; *iy1 = *iy2 = icy; } else { /* * now determine the angle from the center to the point (segx, segy) and offset that angle * by "angle". Then project it by "radius" to get the two intersection points */ angle = acos(adjacent / radius); fx = segx - icx; fy = segy - icy; if (fx == 0.0 && fy == 0.0) { ttyputerr(_("Domain error doing line/circle intersection")); return(0); } intangle = atan2(fy, fx); a1 = intangle - angle; a2 = intangle + angle; *ix1 = icx + rounddouble(cos(a1) * radius); *iy1 = icy + rounddouble(sin(a1) * radius); *ix2 = icx + rounddouble(cos(a2) * radius); *iy2 = icy + rounddouble(sin(a2) * radius); } } if (*ix1 == *ix2 && *iy1 == *iy2) return(1); return(2); } /* * routine to find the two tangent points on a circle that connect to the point * (x,y). The circle is at (cx,cy) with a point at (sx,sy). The points are returned in * (ix1,iy1) and (ix2, iy2). Returns true if tangent points cannot be found * (if the point (x,y) is inside of the circle). */ BOOLEAN circletangents(INTBIG x, INTBIG y, INTBIG cx, INTBIG cy, INTBIG sx, INTBIG sy, INTBIG *ix1, INTBIG *iy1, INTBIG *ix2, INTBIG *iy2) { double in, offset, dang, ang1, ang2, dx, dy, hypotenuse, radius; /* determine circle radius, make sure tangents can be determined */ dx = sx - cx; dy = sy - cy; radius = sqrt(dx*dx + dy*dy); dx = x - cx; dy = y - cy; hypotenuse = sqrt(dx*dx + dy*dy); if (hypotenuse + 1.0 <= radius) return(TRUE); if (hypotenuse < radius) radius = hypotenuse; /* * construct a right triangle, where: * the line from the circle center to the point (x,y) is the hypotenuse * the line from the circle center to an intersection point is side of length "r" * then the angle between these two lines is arccosine(r/hypotenuse) */ in = radius / hypotenuse; offset = acos(in); dx = (double)x-cx; dy = (double)y-cy; if (dx == 0.0 && dy == 0.0) { ttyputerr(_("Domain error doing circle tangents")); return(TRUE); } dang = atan2(dy, dx); ang1 = dang - offset; if (ang1 < 0.0) ang1 += EPI*2.0; ang2 = dang + offset; if (ang2 < 0.0) ang2 += EPI*2.0; if (ang2 >= EPI*2.0) ang2 -= EPI*2.0; *ix1 = cx + rounddouble(cos(ang1)*radius); *iy1 = cy + rounddouble(sin(ang1)*radius); *ix2 = cx + rounddouble(cos(ang2)*radius); *iy2 = cy + rounddouble(sin(ang2)*radius); return(FALSE); } /* * routine to convert an arc to line segments. The arc goes counterclockwise from * (sx,sy) to (ex,ey), centered about the point (cx,cy). The polygon "poly" is loaded * with the line-approximation. There is an arc segment every "arcres" tenth-degrees and * no segment sags from its true curvature by more than "arcsag". */ void arctopoly(INTBIG cx, INTBIG cy, INTBIG sx, INTBIG sy, INTBIG ex, INTBIG ey, POLYGON *poly, INTBIG arcres, INTBIG arcsag) { REGISTER INTBIG as, ae, ang, degreespersegment, segmentcount, pointcount, curangle, pointnum, angleincrement; REGISTER INTBIG radius; double fradius, sag; radius = computedistance(cx, cy, sx, sy); as = figureangle(cx, cy, sx, sy); ae = figureangle(cx, cy, ex, ey); if (ae > as) ang = ae - as; else if (as > ae) ang = ae + 3600 - as; else ang = 0; /* determine number of degrees per segment */ fradius = radius; sag = arcsag; if (fradius - sag <= 0.0) degreespersegment = ang; else degreespersegment = rounddouble(2.0 * acos((fradius - sag) / fradius) * 1800.0 / EPI); if (degreespersegment > arcres) degreespersegment = arcres; if (degreespersegment <= 0) degreespersegment = 1; segmentcount = ang / degreespersegment; if (segmentcount < 1) segmentcount = 1; angleincrement = ang / segmentcount; pointcount = segmentcount + 1; curangle = as; if (poly->limit < pointcount) (void)extendpolygon(poly, pointcount); poly->count = pointcount; poly->style = OPENED; for(pointnum = 0; pointnum < pointcount; pointnum++) { if (pointnum == 0) { poly->xv[pointnum] = sx; poly->yv[pointnum] = sy; } else if (pointnum == pointcount-1) { poly->xv[pointnum] = ex; poly->yv[pointnum] = ey; } else { poly->xv[pointnum] = cx + mult(cosine(curangle), radius); poly->yv[pointnum] = cy + mult(sine(curangle), radius); } curangle += angleincrement; if (curangle >= 3600) curangle -= 3600; } } /* * routine to convert a circle to line segments. The circle is at (cx,cy) and has radius * "radius". The polygon "poly" is loaded with the line-approximation. There is an arc * segment every "arcres" tenth-degrees and no segment sags from its true curvature by * more than "arcsag". */ void circletopoly(INTBIG cx, INTBIG cy, INTBIG radius, POLYGON *poly, INTBIG arcres, INTBIG arcsag) { REGISTER INTBIG degreespersegment, segmentcount, pointcount, curangle, pointnum, angleincrement; REGISTER INTBIG sx, sy; double fradius, sag; sx = cx + radius; sy = cy; /* determine number of degrees per segment */ fradius = radius; sag = arcsag; degreespersegment = rounddouble(2.0 * acos((fradius - sag) / fradius) * 1800.0 / EPI); if (degreespersegment > arcres) degreespersegment = arcres; if (degreespersegment <= 0) degreespersegment = 1; segmentcount = 3600 / degreespersegment; if (segmentcount < 1) segmentcount = 1; angleincrement = 3600 / segmentcount; pointcount = segmentcount + 1; if (poly->limit < pointcount) (void)extendpolygon(poly, pointcount); poly->count = pointcount; poly->style = OPENED; curangle = 0; for(pointnum = 0; pointnum < pointcount; pointnum++) { if (pointnum == 0) { poly->xv[pointnum] = sx; poly->yv[pointnum] = sy; } else if (pointnum == pointcount-1) { poly->xv[pointnum] = sx; poly->yv[pointnum] = sy; } else { poly->xv[pointnum] = cx + mult(cosine(curangle), radius); poly->yv[pointnum] = cy + mult(sine(curangle), radius); } curangle += angleincrement; if (curangle >= 3600) curangle -= 3600; } } /* * Routine to determine whether an arc at angle "ang" can connect the two ports * whose bounding boxes are "lx1<=X<=hx1" and "ly1<=Y<=hy1" for port 1 and * "lx2<=X<=hx2" and "ly2<=Y<=hy2" for port 2. Returns true if a line can * be drawn at that angle between the two ports and returns connection points * in (x1,y1) and (x2,y2) */ BOOLEAN arcconnects(INTBIG ang, INTBIG lx1, INTBIG hx1, INTBIG ly1, INTBIG hy1, INTBIG lx2, INTBIG hx2, INTBIG ly2, INTBIG hy2, INTBIG *x1, INTBIG *y1, INTBIG *x2, INTBIG *y2) { float a, b, d, lx, hx, ly, hy, low1, high1, low2, high2; /* first try simple solutions */ if ((ang%1800) == 0) { /* horizontal angle: simply test Y coordinates */ if (ly1 > hy2 || ly2 > hy1) return(FALSE); *y1 = *y2 = (maxi(ly1, ly2) + mini(hy1, hy2)) / 2; *x1 = (lx1+hx1) / 2; *x2 = (lx2+hx2) / 2; return(TRUE); } if ((ang%1800) == 900) { /* vertical angle: simply test X coordinates */ if (lx1 > hx2 || lx2 > hx1) return(FALSE); *x1 = *x2 = (maxi(lx1, lx2) + mini(hx1, hx2)) / 2; *y1 = (ly1+hy1) / 2; *y2 = (ly2+hy2) / 2; return(TRUE); } /* construct an imaginary line at the proper angle that runs through (0,0) */ a = (float)sine(ang); a /= 1073741824.0; b = (float)-cosine(ang); b /= 1073741824.0; /* get the range of distances from the line to port 1 */ lx = (float)lx1; hx = (float)hx1; ly = (float)ly1; hy = (float)hy1; d = lx*a + ly*b; low1 = high1 = d; d = hx*a + ly*b; if (d < low1) low1 = d; if (d > high1) high1 = d; d = hx*a + hy*b; if (d < low1) low1 = d; if (d > high1) high1 = d; d = lx*a + hy*b; if (d < low1) low1 = d; if (d > high1) high1 = d; /* get the range of distances from the line to port 2 */ lx = (float)lx2; hx = (float)hx2; ly = (float)ly2; hy = (float)hy2; d = lx*a + ly*b; low2 = high2 = d; d = hx*a + ly*b; if (d < low2) low2 = d; if (d > high2) high2 = d; d = hx*a + hy*b; if (d < low2) low2 = d; if (d > high2) high2 = d; d = lx*a + hy*b; if (d < low2) low2 = d; if (d > high2) high2 = d; /* if the ranges do not overlap, a line cannot be drawn */ if (low1 > high2 || low2 > high1) return(FALSE); /* the line can be drawn: determine equation (aX + bY = d) */ d = ((low1 > low2 ? low1 : low2) + (high1 < high2 ? high1 : high2)) / 2.0f; /* determine intersection with polygon 1 */ db_findconnectionpoint(lx1, hx1, ly1, hy1, a, b, d, x1, y1); db_findconnectionpoint(lx2, hx2, ly2, hy2, a, b, d, x2, y2); return(TRUE); } /* * Routine to find a point inside the rectangle bounded by (lx<=X<=hx, ly<=Y<=hy) * that satisfies the equation aX + bY = d. Returns the point in (x,y). */ void db_findconnectionpoint(INTBIG lx, INTBIG hx, INTBIG ly, INTBIG hy, float a, float b, float d, INTBIG *x, INTBIG *y) { float in, out; if (a != 0.0) { in = (float)ly; *y = ly; out = (d - b * in) / a; *x = (INTBIG)out; if (*x >= lx && *x <= hx) return; in = (float)hy; *y = hy; out = (d - b * in) / a; *x = (INTBIG)out; if (*x >= lx && *x <= hx) return; } if (b != 0.0) { in = (float)lx; *x = lx; out = (d - a * in) / b; *y = (INTBIG)out; if (*y >= ly && *y <= hy) return; in = (float)hx; *x = hx; out = (d - a * in) / b; *y = (INTBIG)out; if (*y >= ly && *y <= hy) return; } /* not the right solution, but nothing else works */ *x = (lx+hx) / 2; *y = (ly+hy) / 2; } /* * compute the quadrant of the point x,y 2 | 1 * Standard quadrants are used: ----- * 3 | 4 */ INTBIG db_quadrant(INTBIG x, INTBIG y) { if (x > 0) { if (y >= 0) return(1); return(4); } if (y > 0) return(2); return(3); } /* * routine to compute the bounding box of the arc that runs clockwise from * (xs,ys) to (xe,ye) and is centered at (xc,yc). The bounding box is * placed in the reference parameters "lx", "hx", "ly", and "hy". */ void arcbbox(INTBIG xs, INTBIG ys, INTBIG xe, INTBIG ye, INTBIG xc, INTBIG yc, INTBIG *lx, INTBIG *hx, INTBIG *ly, INTBIG *hy) { REGISTER INTBIG x1, y1, x2, y2, radius; REGISTER INTBIG q1, q2; /* determine radius and compute bounds of full circle */ radius = computedistance(xc, yc, xs, ys); *lx = xc - radius; *ly = yc - radius; *hx = xc + radius; *hy = yc + radius; /* compute quadrant of two endpoints */ x1 = xs - xc; x2 = xe - xc; y1 = ys - yc; y2 = ye - yc; q1 = db_quadrant(x1, y1); q2 = db_quadrant(x2, y2); /* see if the two endpoints are in the same quadrant */ if (q1 == q2) { /* if the arc runs a full circle, use the MBR of the circle */ if (q1 == 1 || q1 == 2) { if (x1 > x2) return; } else { if (x1 < x2) return; } /* use the MBR of the two arc points */ *lx = mini(xs, xe); *hx = maxi(xs, xe); *ly = mini(ys, ye); *hy = maxi(ys, ye); return; } switch (q1) { case 1: switch (q2) { case 2: /* 3 quadrants clockwise from Q1 to Q2 */ *hy = maxi(y1,y2) + yc; break; case 3: /* 2 quadrants clockwise from Q1 to Q3 */ *lx = x2 + xc; *hy = y1 + yc; break; case 4: /* 1 quadrant clockwise from Q1 to Q4 */ *lx = mini(x1,x2) + xc; *ly = y2 + yc; *hy = y1 + yc; break; } break; case 2: switch (q2) { case 1: /* 1 quadrant clockwise from Q2 to Q1 */ *lx = x1 + xc; *ly = mini(y1,y2) + yc; *hx = x2 + xc; break; case 3: /* 3 quadrants clockwise from Q2 to Q3 */ *lx = mini(x1,x2) + xc; break; case 4: /* 2 quadrants clockwise from Q2 to Q4 */ *lx = x1 + xc; *ly = y2 + yc; break; } break; case 3: switch (q2) { case 1: /* 2 quadrants clockwise from Q3 to Q1 */ *ly = y1 + yc; *hx = x2 + xc; break; case 2: /* 1 quadrant clockwise from Q3 to Q2 */ *ly = y1 + yc; *hx = maxi(x1,x2) + xc; *hy = y2 + yc; break; case 4: /* 3 quadrants clockwise from Q3 to Q4 */ *ly = mini(y1,y2) + yc; break; } break; case 4: switch (q2) { case 1: /* 3 quadrants clockwise from Q4 to Q1 */ *hx = maxi(x1,x2) + xc; break; case 2: /* 2 quadrants clockwise from Q4 to Q2 */ *hx = x1 + xc; *hy = y2 + yc; break; case 3: /* 1 quadrant clockwise from Q4 to Q3 */ *lx = x2 + xc; *hx = x1 + xc; *hy = maxi(y1,y2) + yc; break; } break; } } /* * Routine to find the two possible centers for a circle whose radius is * "r" and has two points (x01,y01) and (x02,y02) on the edge. The two * center points are returned in (x1,y1) and (x2,y2). The distance between * the points (x01,y01) and (x02,y02) is in "d". The routine returns * false if successful, true if there is no intersection. This code * was written by John Mohammed of Schlumberger. */ BOOLEAN findcenters(INTBIG r, INTBIG x01, INTBIG y01, INTBIG x02, INTBIG y02, INTBIG d, INTBIG *x1, INTBIG *y1, INTBIG *x2, INTBIG *y2) { float r2, delta_1, delta_12, delta_2; /* quit now if the circles concentric */ if (x01 == x02 && y01 == y02) return(TRUE); /* find the intersections, if any */ r2 = (float)r; r2 *= r; delta_1 = -d / 2.0f; delta_12 = delta_1 * delta_1; /* quit if there are no intersections */ if (r2 < delta_12) return(TRUE); /* compute the intersection points */ delta_2 = (float)sqrt(r2 - delta_12); *x1 = x02 + (INTBIG)(((delta_1 * (x02 - x01)) + (delta_2 * (y02 - y01))) / d); *y1 = y02 + (INTBIG)(((delta_1 * (y02 - y01)) + (delta_2 * (x01 - x02))) / d); *x2 = x02 + (INTBIG)(((delta_1 * (x02 - x01)) + (delta_2 * (y01 - y02))) / d); *y2 = y02 + (INTBIG)(((delta_1 * (y02 - y01)) + (delta_2 * (x02 - x01))) / d); return(FALSE); } /* * routine to determine the point on the line segment that runs from * (x1,y1) to (x2,y2) that is closest to the point (*x,*y). The value in * (*x,*y) is adjusted to be that close point and the distance is returned. */ INTBIG closestpointtosegment(INTBIG x1, INTBIG y1, INTBIG x2, INTBIG y2, INTBIG *x, INTBIG *y) { REGISTER INTBIG dist1, dist2; INTBIG xi, yi; /* find closest point on line */ db_closestpointtoline(x1,y1, x2,y2, *x,*y, &xi, &yi); /* see if that intersection point is actually on the segment */ if (xi >= mini(x1, x2) && xi <= maxi(x1, x2) && yi >= mini(y1, y2) && yi <= maxi(y1, y2)) { /* it is: get the distance and return this point */ dist1 = computedistance(*x, *y, xi, yi); *x = xi; *y = yi; return(dist1); } /* intersection not on segment: choose one endpoint as the closest */ dist1 = computedistance(*x, *y, x1, y1); dist2 = computedistance(*x, *y, x2, y2); if (dist2 < dist1) { *x = x2; *y = y2; return(dist2); } *x = x1; *y = y1; return(dist1); } /* * routine to determine the point on the line that runs from (x1,y1) to * (x2,y2) that is closest to the point (xp,yp). This point is returned * in (*xi,*yi). */ void db_closestpointtoline(INTBIG x1, INTBIG y1, INTBIG x2, INTBIG y2, INTBIG xp, INTBIG yp, INTBIG *xi, INTBIG *yi) { float m, b, mi, bi, t; INTBIG newx, newy; /* special case for horizontal line */ if (y1 == y2) { *xi = xp; *yi = y1; return; } /* special case for vertical line */ if (x1 == x2) { *xi = x1; *yi = yp; return; } /* compute equation of the line */ m = (float)(y1-y2); m /= x1-x2; b = (float)-x1; b *= m; b += y1; /* compute perpendicular to line through the point */ mi = -1.0f / m; bi = (float)-xp; bi *= mi; bi += yp; /* compute intersection of the lines */ t = (bi-b) / (m-mi); newx = (INTBIG)t; newy = (INTBIG)(m * t + b); *xi = newx; *yi = newy; } /* * routine to compute the distance between point (x,y) and the line that runs * from (x1,y1) to (x2,y2). */ INTBIG disttoline(INTBIG x1, INTBIG y1, INTBIG x2, INTBIG y2, INTBIG x, INTBIG y) { REGISTER INTBIG ang; REGISTER INTBIG dist, ix, iy; INTBIG oix, oiy; /* get point on line from (x1,y1) to (x2,y2) close to (x,y) */ if (x1 == x2 && y1 == y2) { return(computedistance(x, y, x1, y1)); } ang = figureangle(x1,y1, x2,y2); (void)intersect(x1, y1, ang, x, y, (ang+900)%3600, &oix, &oiy); ix = oix; iy = oiy; if (x1 == x2) ix = x1; if (y1 == y2) iy = y1; /* make sure (ix,iy) is on the segment from (x1,y1) to (x2,y2) */ if (ix < mini(x1,x2) || ix > maxi(x1,x2) || iy < mini(y1,y2) || iy > maxi(y1,y2)) { if (abs(ix-x1) + abs(iy-y1) < abs(ix-x2) + abs(iy-y2)) { ix = x1; iy = y1; } else { ix = x2; iy = y2; } } dist = computedistance(ix, iy, x, y); return(dist); } /* * Routine to scale "value" from database units to the requested display unit "dispunit". */ float scaletodispunit(INTBIG value, INTBIG dispunit) { REGISTER float scalefactor; scalefactor = db_getcurrentscale(el_units&INTERNALUNITS, dispunit, el_curlib->lambda[el_curtech->techindex]); return((float)value / scalefactor); } /* * Routine to scale "value" from square database units to the requested square display unit "dispunit". */ float scaletodispunitsq(INTBIG value, INTBIG dispunit) { REGISTER float scalefactor; scalefactor = db_getcurrentscale(el_units&INTERNALUNITS, dispunit, el_curlib->lambda[el_curtech->techindex]); return((float)value / scalefactor / scalefactor); } /* * Routine to scale "value" from the requested display unit "dispunit" to database units. */ INTBIG scalefromdispunit(float value, INTBIG dispunit) { REGISTER float scalefactor; scalefactor = db_getcurrentscale(el_units&INTERNALUNITS, dispunit, el_curlib->lambda[el_curtech->techindex]); return(roundfloat(value * scalefactor)); } /* * Routine to return the scaling factor between database units and display units. * The current value of lambda is provided for use when that is the unit. */ float db_getcurrentscale(INTBIG intunit, INTBIG dispunit, INTBIG lambda) { switch (intunit&INTERNALUNITS) { case INTUNITHNM: switch (dispunit&DISPLAYUNITS) { case DISPUNITINCH: return(50800000.0f); case DISPUNITCM: return(20000000.0f); case DISPUNITMM: return(2000000.0f); case DISPUNITMIL: return(50800.0f); case DISPUNITMIC: return(2000.0f); case DISPUNITCMIC: return(20.0f); case DISPUNITNM: return(2.0f); } break; case INTUNITHDMIC: switch (dispunit&DISPLAYUNITS) { case DISPUNITINCH: return(508000.0f); case DISPUNITCM: return(200000.0f); case DISPUNITMM: return(20000.0f); case DISPUNITMIL: return(508.0f); case DISPUNITMIC: return(20.0f); case DISPUNITCMIC: return(0.2f); case DISPUNITNM: return(0.02f); } break; } return((float)lambda); } void db_getinternalunitscale(INTBIG *numerator, INTBIG *denominator, INTBIG oldunits, INTBIG newunits) { if ((newunits&INTERNALUNITS) == INTUNITHNM) { /* scaling from half-decimicrons to half-nanometers (multiply by 100) */ *numerator = 100; *denominator = 1; } else { /* scaling from half-nanometers to half-decimicrons (divide by 100) */ *numerator = 1; *denominator = 100; } } /* * routine to crop the box in the reference parameters (lx-hx, ly-hy) * against the box in (bx-ux, by-uy). If the box is cropped into oblivion, * the routine returns 1. If the boxes overlap but cannot be cleanly cropped, * the routine returns -1. Otherwise the box is cropped and zero is returned */ INTBIG cropbox(INTBIG *lx, INTBIG *hx, INTBIG *ly, INTBIG *hy, INTBIG bx, INTBIG ux, INTBIG by, INTBIG uy) { REGISTER INTBIG crops; /* if the two boxes don't touch, just return */ if (bx >= *hx || by >= *hy || ux <= *lx || uy <= *ly) return(0); /* if the box to be cropped is within the other, say so */ if (bx <= *lx && ux >= *hx && by <= *ly && uy >= *hy) return(1); /* reduce (lx-hx,ly-hy) by (bx-ux,by-uy) */ crops = 0; if (bx <= *lx && ux >= *hx) { /* it covers in X...crop in Y */ if (uy >= *hy) *hy = by; if (by <= *ly) *ly = uy; crops++; } if (by <= *ly && uy >= *hy) { /* it covers in Y...crop in X */ if (ux >= *hx) *hx = bx; if (bx <= *lx) *lx = ux; crops++; } if (crops == 0) return(-1); return(0); } /************************* SIMPLE MATHEMATICS *************************/ INTBIG mini(INTBIG a, INTBIG b) { return(ab ? a : b); } INTBIG roundfloat(float a) { if (a < 0.0) return((INTBIG)(a-0.5)); return((INTBIG)(a+0.5)); } INTBIG rounddouble(double a) { if (a < 0.0) return((INTBIG)(a-0.5)); return((INTBIG)(a+0.5)); } /* * Routine to return true if "a" is equal to "b" within the epsilon of floating * point arithmetic. */ BOOLEAN floatsequal(float a, float b) { if (fabs(a-b) <= FLT_EPSILON) return(TRUE); return(FALSE); } /* * Routine to return true if "a" is equal to "b" within the epsilon of double floating * point arithmetic. */ BOOLEAN doublesequal(double a, double b) { if (fabs(a-b) <= DBL_EPSILON) return(TRUE); return(FALSE); } /* * Routine to return true if "a" is less than "b" within the epsilon of floating * point arithmetic. */ BOOLEAN floatslessthan(float a, float b) { if (a+FLT_EPSILON < b) return(TRUE); return(FALSE); } /* * Routine to return true if "a" is less than "b" within the epsilon of double floating * point arithmetic. */ BOOLEAN doubleslessthan(double a, double b) { if (a+DBL_EPSILON < b) return(TRUE); return(FALSE); } /* * Routine to truncate "a" to the lowest integral value. */ float floatfloor(float a) { INTBIG i; i = (INTBIG)(a + FLT_EPSILON); return((float)i); } /* * Routine to truncate "a" to the lowest integral value. */ double doublefloor(double a) { INTBIG i; i = (INTBIG)(a + DBL_EPSILON); return((float)i); } /* routine to convert a floating value to integer by casting! */ INTBIG castint(float a) { union { INTBIG i; float x; } cast; cast.x = a; return(cast.i); } /* routine to convert an integer value to floating point by casting! */ float castfloat(INTBIG j) { union { INTBIG i; float x; } cast; cast.i = j; return(cast.x); } /************************* 3D MATHEMATICS *************************/ void vectoradd3d(float *a, float *b, float *sum) { sum[0] = a[0] + b[0]; sum[1] = a[1] + b[1]; sum[2] = a[2] + b[2]; } void vectorsubtract3d(float *a, float *b, float *diff) { diff[0] = a[0] - b[0]; diff[1] = a[1] - b[1]; diff[2] = a[2] - b[2]; } void vectormultiply3d(float *a, float b, float *res) { res[0] = a[0] * b; res[1] = a[1] * b; res[2] = a[2] * b; } void vectordivide3d(float *a, float b, float *res) { res[0] = a[0] / b; res[1] = a[1] / b; res[2] = a[2] / b; } float vectormagnitude3d(float *a) { return((float)sqrt(a[0]*a[0] + a[1]*a[1] + a[2]*a[2])); } float vectordot3d(float *a, float *b) { return(a[0] * b[0] + a[1] * b[1] + a[2] * b[2]); } void vectornormalize3d(float *a) { float mag; mag = (float)sqrt(a[0] * a[0] + a[1] * a[1] + a[2] * a[2]); if (mag > 1.0e-11f) { a[0] /= mag; a[1] /= mag; a[2] /= mag; } } void vectorcross3d(float *a, float *b, float *res) { res[0] = a[1] * b[2] - b[1] * a[2]; res[1] = a[2] * b[0] - b[2] * a[0]; res[2] = a[0] * b[1] - b[0] * a[1]; } void matrixid3d(float xform[4][4]) { REGISTER INTBIG i, j; for(i=0; i<4; i++) { for(j=0; j<4; j++) { if (i == j) xform[i][j] = 1.0; else xform[i][j] = 0.0; } } } void matrixmult3d(float a[4][4], float b[4][4], float res[4][4]) { REGISTER INTBIG row, col, i; for (row = 0; row < 4; row++) { for (col = 0; col < 4; col++) { res[row][col] = 0.0f; for (i = 0; i < 4; i++) { res[row][col] += a[i][col] * b[row][i]; } } } } /* * Routine to build the invert of the transformation. Returns nonzero if a * singularity is detected. */ void matrixinvert3d(float in[4][4], float out[4][4]) { float a[4][8], temp; short i, j, k, l; /* copy into the matrix */ for(i=0; i<4; i++) { for(j=0; j<8; j++) { if (j < 4) a[i][j] = in[i][j]; else if (j == i+4) a[i][j] = 1.0; else a[i][j] = 0.0; } } /* do the inversion */ for(i=0; i<4; i++) { for(l=i; l<4; l++) if (a[l][i] != 0.0) break; if (l >= 4) return; if (l != i) for(k=0; k<8; k++) { temp = a[l][k]; a[l][k] = a[i][k]; a[i][k] = temp; } for(k=7; k>=i; k--) a[i][k] = a[i][k] / a[i][i]; for(l=0; l<4; l++) if (l != i) for(k=7; k>=i; k--) a[l][k] = a[l][k] - a[i][k] * a[l][i]; } /* copy back from the matrix */ l = 0; for(i=0; i<4; i++) for(j=0; j<4; j++) out[i][j] = a[i][j+4]; } void matrixxform3d(float *vec, float mat[4][4], float *res) { res[0] = mat[0][0] * vec[0] + mat[0][1] * vec[1] + mat[0][2] * vec[2] + mat[0][3] * vec[3]; res[1] = mat[1][0] * vec[0] + mat[1][1] * vec[1] + mat[1][2] * vec[2] + mat[1][3] * vec[3]; res[2] = mat[2][0] * vec[0] + mat[2][1] * vec[1] + mat[2][2] * vec[2] + mat[2][3] * vec[3]; res[3] = mat[3][0] * vec[0] + mat[3][1] * vec[1] + mat[3][2] * vec[2] + mat[2][3] * vec[3]; } /************************* POLYGON MANIPULATION *************************/ /* * routine to allocate a polygon with "points" points from cluster "clus" * and return the address. Returns NOPOLYGON if an error occurs. */ #ifdef DEBUGMEMORY POLYGON *_allocpolygon(INTBIG points, CLUSTER *cluster, CHAR *filename, INTBIG lineno) #else POLYGON *allocpolygon(INTBIG points, CLUSTER *cluster) #endif { REGISTER POLYGON *poly; if (db_multiprocessing) emutexlock(db_polygonmutex); poly = NOPOLYGON; if (db_freepolygons != NOPOLYGON) { poly = db_freepolygons; db_freepolygons = poly->nextpolygon; if (poly->count < points) (void)extendpolygon(poly, points); } if (db_multiprocessing) emutexunlock(db_polygonmutex); if (poly == NOPOLYGON) { #ifdef DEBUGMEMORY poly = (POLYGON *)_emalloc((sizeof (POLYGON)), cluster, filename, lineno); if (poly == 0) return((POLYGON *)db_error(DBNOMEM|DBALLOCPOLYGON)); poly->xv = _emalloc((SIZEOFINTBIG*points), cluster, filename, lineno); if (poly->xv == 0) return((POLYGON *)db_error(DBNOMEM|DBALLOCPOLYGON)); poly->yv = _emalloc((SIZEOFINTBIG*points), cluster, filename, lineno); if (poly->yv == 0) return((POLYGON *)db_error(DBNOMEM|DBALLOCPOLYGON)); #else poly = (POLYGON *)emalloc((sizeof (POLYGON)), cluster); if (poly == 0) return((POLYGON *)db_error(DBNOMEM|DBALLOCPOLYGON)); poly->xv = emalloc((SIZEOFINTBIG*points), cluster); if (poly->xv == 0) return((POLYGON *)db_error(DBNOMEM|DBALLOCPOLYGON)); poly->yv = emalloc((SIZEOFINTBIG*points), cluster); if (poly->yv == 0) return((POLYGON *)db_error(DBNOMEM|DBALLOCPOLYGON)); #endif poly->cluster = cluster; poly->limit = points; } poly->string = NOSTRING; poly->desc = NOGRAPHICS; poly->portproto = NOPORTPROTO; poly->count = 0; poly->style = FILLED; TDCLEAR(poly->textdescript); TDSETSIZE(poly->textdescript, TXTSETPOINTS(8)); poly->tech = el_curtech; poly->layer = 0; poly->nextpolygon = NOPOLYGON; poly->numvar = 0; return(poly); } /* * routine to ensure that polygon "poly" is valid and has "points" points. * If not allocated, it is created from cluster "clus" and remembered as a * static polygon to be freed later. Returns TRUE on error. */ BOOLEAN needstaticpolygon(POLYGON **poly, INTBIG points, CLUSTER *clus) { /* if the polygon is already allocated, stop */ if (*poly != NOPOLYGON) { if ((*poly)->count < points) (void)extendpolygon(*poly, points); return(FALSE); } /* lock the allocation and saving of the pointers */ if (db_multiprocessing) emutexlock(db_polygonmutex); if (*poly == NOPOLYGON) { *poly = allocpolygon(points, clus); if (*poly != NOPOLYGON) { (*poly)->nextpolygon = db_staticpolygons; db_staticpolygons = *poly; } } if (db_multiprocessing) emutexunlock(db_polygonmutex); if (*poly == NOPOLYGON) return(TRUE); if ((*poly)->count < points) (void)extendpolygon(*poly, points); return(FALSE); } /* * routine to extend polygon "poly" to be "newcount" points. Returns * true if there is an allocation error */ BOOLEAN extendpolygon(POLYGON *poly, INTBIG newcount) { REGISTER INTBIG *oldxp, *oldyp, i; /* if polygon can already handle this many points, quit */ if (newcount <= poly->limit) return(FALSE); /* save the old coordinates */ oldxp = poly->xv; oldyp = poly->yv; /* get space for the new ones */ poly->xv = emalloc((SIZEOFINTBIG*newcount), poly->cluster); if (poly->xv == 0) return(db_error(DBNOMEM|DBEXTENDPOLYGON)!=0); poly->yv = emalloc((SIZEOFINTBIG*newcount), poly->cluster); if (poly->yv == 0) return(db_error(DBNOMEM|DBEXTENDPOLYGON)!=0); for(i=0; ilimit; i++) { poly->xv[i] = oldxp[i]; poly->yv[i] = oldyp[i]; } poly->limit = newcount; efree((CHAR *)oldxp); efree((CHAR *)oldyp); return(FALSE); } /* * routine to free the memory associated with polygon "poly" */ void freepolygon(POLYGON *poly) { if (db_multiprocessing) emutexlock(db_polygonmutex); poly->nextpolygon = db_freepolygons; db_freepolygons = poly; if (db_multiprocessing) emutexunlock(db_polygonmutex); } #ifdef DEBUGMEMORY POLYLIST *_allocpolylist(CLUSTER *cluster, CHAR *filename, INTBIG lineno) #else POLYLIST *allocpolylist(CLUSTER *cluster) #endif { REGISTER POLYLIST *plist; #ifdef DEBUGMEMORY plist = (POLYLIST *)_emalloc(sizeof(POLYLIST), cluster, filename, lineno); #else plist = (POLYLIST *)emalloc(sizeof(POLYLIST), cluster); #endif if (plist == 0) return(0); plist->polylisttotal = 0; return(plist); } /* * routine to accumulate a list of polygons at least "tot" long in the * polygon structure "list". The routine returns true if there is no * more memory. */ #ifdef DEBUGMEMORY BOOLEAN _ensurepolylist(POLYLIST *list, INTBIG tot, CLUSTER *cluster, CHAR *filename, INTBIG lineno) #else BOOLEAN ensurepolylist(POLYLIST *list, INTBIG tot, CLUSTER *cluster) #endif { REGISTER POLYGON **newpolylist; REGISTER INTBIG j, *newlx, *newhx, *newly, *newhy; /* make sure the list is the right size */ if (tot > list->polylisttotal) { #ifdef DEBUGMEMORY newpolylist = (POLYGON **)_emalloc(tot * (sizeof (POLYGON *)), dr_tool->cluster, filename, lineno); newlx = (INTBIG *)_emalloc(tot * SIZEOFINTBIG, dr_tool->cluster, filename, lineno); newhx = (INTBIG *)_emalloc(tot * SIZEOFINTBIG, dr_tool->cluster, filename, lineno); newly = (INTBIG *)_emalloc(tot * SIZEOFINTBIG, dr_tool->cluster, filename, lineno); newhy = (INTBIG *)_emalloc(tot * SIZEOFINTBIG, dr_tool->cluster, filename, lineno); #else newpolylist = (POLYGON **)emalloc(tot * (sizeof (POLYGON *)), dr_tool->cluster); newlx = (INTBIG *)emalloc(tot * SIZEOFINTBIG, dr_tool->cluster); newhx = (INTBIG *)emalloc(tot * SIZEOFINTBIG, dr_tool->cluster); newly = (INTBIG *)emalloc(tot * SIZEOFINTBIG, dr_tool->cluster); newhy = (INTBIG *)emalloc(tot * SIZEOFINTBIG, dr_tool->cluster); #endif if (newpolylist == 0 || newlx == 0 || newhx == 0 || newly == 0 || newhy == 0) { ttyputerr(_("DRC error allocating memory for polygons")); return(TRUE); } for(j=0; jpolylisttotal != 0) { for(j=0; jpolylisttotal; j++) newpolylist[j] = list->polygons[j]; efree((CHAR *)list->polygons); efree((CHAR *)list->lx); efree((CHAR *)list->hx); efree((CHAR *)list->ly); efree((CHAR *)list->hy); } list->polygons = newpolylist; list->lx = newlx; list->hx = newhx; list->ly = newly; list->hy = newhy; list->polylisttotal = tot; } /* make sure there is a polygon for each entry in the list */ for(j=0; jpolygons[j] == NOPOLYGON) { #ifdef DEBUGMEMORY list->polygons[j] = _allocpolygon(4, cluster, filename, lineno); #else list->polygons[j] = allocpolygon(4, cluster); #endif } return(FALSE); } void freepolylist(POLYLIST *list) { REGISTER INTBIG i; for(i=0; ipolylisttotal; i++) if (list->polygons[i] != NOPOLYGON) freepolygon(list->polygons[i]); if (list->polylisttotal > 0) { efree((CHAR *)list->polygons); efree((CHAR *)list->lx); efree((CHAR *)list->hx); efree((CHAR *)list->ly); efree((CHAR *)list->hy); } efree((CHAR *)list); } void db_deallocatepolygon(POLYGON *poly) { efree((CHAR *)poly->xv); efree((CHAR *)poly->yv); efree((CHAR *)poly); } /* routine to transform polygon "poly" through the transformation "trans" */ void xformpoly(POLYGON *poly, XARRAY trans) { REGISTER INTBIG i, x, y, det, t22, px, py; t22 = trans[2][2]; if (poly->style == FILLEDRECT || poly->style == CLOSEDRECT) { /* rectangles must be fleshed-out if nonmanhattan */ if (t22 == P1) maketruerect(poly); } else if (poly->style == CIRCLEARC || poly->style == THICKCIRCLEARC) { /* special hack to reverse points in arcs if node is transposed */ if (t22 != P1) det = db_determinant[t22]; else det = mult(trans[0][0], trans[1][1]) - mult(trans[0][1], trans[1][0]); if (det < 0) for(i=0; icount; i += 3) { x = poly->xv[i+1]; y = poly->yv[i+1]; poly->xv[i+1] = poly->xv[i+2]; poly->yv[i+1] = poly->yv[i+2]; poly->xv[i+2] = x; poly->yv[i+2] = y; } } /* transform the polygon */ px = trans[2][0]; py = trans[2][1]; if (t22 != P1) { for(i=0; icount; i++) { x = poly->xv[i]; y = poly->yv[i]; switch (t22) { case 0: poly->xv[i] = x + px; poly->yv[i] = y + py; break; case 1: poly->xv[i] = -y + px; poly->yv[i] = x + py; break; case 2: poly->xv[i] = -x + px; poly->yv[i] = -y + py; break; case 3: poly->xv[i] = y + px; poly->yv[i] = -x + py; break; case 4: poly->xv[i] = -y + px; poly->yv[i] = -x + py; break; case 5: poly->xv[i] = -x + px; poly->yv[i] = y + py; break; case 6: poly->xv[i] = y + px; poly->yv[i] = x + py; break; case 7: poly->xv[i] = x + px; poly->yv[i] = -y + py; break; } } } else { for(i=0; icount; i++) { x = poly->xv[i]; y = poly->yv[i]; poly->xv[i] = mult(trans[0][0],x) + mult(trans[1][0],y) + px; poly->yv[i] = mult(trans[0][1],x) + mult(trans[1][1],y) + py; } } } /* * routine to ensure that polygon "poly" has true vertices, and is not described * as a "rectangle" with only two diagonal points. */ void maketruerect(POLYGON *poly) { REGISTER INTBIG lx, ux, ly, uy; if (poly->style != FILLEDRECT && poly->style != CLOSEDRECT) return; if (poly->limit < 4) (void)extendpolygon(poly, 4); lx = poly->xv[0]; ux = poly->xv[1]; ly = poly->yv[0]; uy = poly->yv[1]; poly->xv[0] = poly->xv[1] = lx; poly->xv[2] = poly->xv[3] = ux; poly->yv[0] = poly->yv[3] = ly; poly->yv[1] = poly->yv[2] = uy; poly->count = 4; if (poly->style == FILLEDRECT) poly->style = FILLED; else poly->style = CLOSED; } /* * routine to return true if the polygon in "poly" is an orthogonal box. * If the polygon is an orthogonal box, the bounds of that box are placed * in the reference integers "xl", "xh", "yl", and "yh". */ BOOLEAN isbox(POLYGON *poly, INTBIG *xl, INTBIG *xh, INTBIG *yl, INTBIG *yh) { /* rectangular styles are always boxes */ if (poly->style == FILLEDRECT || poly->style == CLOSEDRECT) { if (poly->xv[0] > poly->xv[1]) { *xl = poly->xv[1]; *xh = poly->xv[0]; } else { *xl = poly->xv[0]; *xh = poly->xv[1]; } if (poly->yv[0] > poly->yv[1]) { *yl = poly->yv[1]; *yh = poly->yv[0]; } else { *yl = poly->yv[0]; *yh = poly->yv[1]; } return(TRUE); } /* closed boxes must have exactly four points */ if (poly->count == 4) { /* only closed polygons and text can be boxes */ if ((poly->style < TEXTCENT || poly->style > TEXTBOX) && poly->style != CROSSED && poly->style != FILLED && poly->style != CLOSED) return(FALSE); } else if (poly->count == 5) { if (poly->style < OPENED || poly->style > OPENEDO1) return(FALSE); if (poly->xv[0] != poly->xv[4] || poly->yv[0] != poly->yv[4]) return(FALSE); } else return(FALSE); /* make sure the polygon is rectangular and orthogonal */ if (poly->xv[0] == poly->xv[1] && poly->xv[2] == poly->xv[3] && poly->yv[0] == poly->yv[3] && poly->yv[1] == poly->yv[2]) { if (poly->xv[0] < poly->xv[2]) { *xl = poly->xv[0]; *xh = poly->xv[2]; } else { *xl = poly->xv[2]; *xh = poly->xv[0]; } if (poly->yv[0] < poly->yv[1]) { *yl = poly->yv[0]; *yh = poly->yv[1]; } else { *yl = poly->yv[1]; *yh = poly->yv[0]; } return(TRUE); } if (poly->xv[0] == poly->xv[3] && poly->xv[1] == poly->xv[2] && poly->yv[0] == poly->yv[1] && poly->yv[2] == poly->yv[3]) { if (poly->xv[0] < poly->xv[1]) { *xl = poly->xv[0]; *xh = poly->xv[1]; } else { *xl = poly->xv[1]; *xh = poly->xv[0]; } if (poly->yv[0] < poly->yv[2]) { *yl = poly->yv[0]; *yh = poly->yv[2]; } else { *yl = poly->yv[2]; *yh = poly->yv[0]; } return(TRUE); } return(FALSE); } /* * routine to return true if (X,Y) is inside of polygon "poly" */ BOOLEAN isinside(INTBIG x, INTBIG y, POLYGON *poly) { INTBIG xl, xh, yl, yh; REGISTER INTBIG ang, lastp, tang, thisp, startangle, endangle; REGISTER INTBIG i, odist, dist, angrange, startdist, enddist, wantdist; switch (poly->style) { case FILLED: case CLOSED: case FILLEDRECT: case CLOSEDRECT: case CROSSED: case TEXTCENT: case TEXTTOP: case TEXTBOT: case TEXTLEFT: case TEXTRIGHT: case TEXTTOPLEFT: case TEXTBOTLEFT: case TEXTTOPRIGHT: case TEXTBOTRIGHT: case TEXTBOX: /* check rectangular case for containment */ if (isbox(poly, &xl, &xh, &yl, &yh)) { if (x < xl || x > xh || y < yl || y > yh) return(FALSE); return(TRUE); } /* general polygon containment by summing angles to vertices */ ang = 0; if (x == poly->xv[poly->count-1] && y == poly->yv[poly->count-1]) return(TRUE); lastp = figureangle(x, y, poly->xv[poly->count-1], poly->yv[poly->count-1]); for(i=0; icount; i++) { if (x == poly->xv[i] && y == poly->yv[i]) return(TRUE); thisp = figureangle(x, y, poly->xv[i], poly->yv[i]); tang = lastp - thisp; if (tang < -1800) tang += 3600; if (tang > 1800) tang -= 3600; ang += tang; lastp = thisp; } if (abs(ang) <= poly->count) return(FALSE); return(TRUE); case CROSS: case BIGCROSS: /* polygon is only a single point */ getcenter(poly, &xl, &yl); if (xl == x && yl == y) return(TRUE); return(FALSE); case OPENED: case OPENEDT1: case OPENEDT2: case OPENEDT3: case VECTORS: /* first look for trivial inclusion by being a vertex */ for(i=0; icount; i++) if (poly->xv[i] == x && poly->yv[i] == y) return(TRUE); /* see if the point is on one of the edges */ if (poly->style == VECTORS) { for(i=0; icount; i += 2) if (isonline(poly->xv[i],poly->yv[i], poly->xv[i+1], poly->yv[i+1], x, y)) return(TRUE); } else { for(i=1; icount; i++) if (isonline(poly->xv[i-1],poly->yv[i-1], poly->xv[i], poly->yv[i], x, y)) return(TRUE); } return(FALSE); case CIRCLE: case THICKCIRCLE: case DISC: dist = computedistance(poly->xv[0], poly->yv[0], poly->xv[1], poly->yv[1]); odist = computedistance(poly->xv[0], poly->yv[0], x, y); if (odist < dist) return(TRUE); return(FALSE); case CIRCLEARC: case THICKCIRCLEARC: /* first see if the point is at the proper angle from the center of the arc */ ang = figureangle(poly->xv[0], poly->yv[0], x, y); endangle = figureangle(poly->xv[0], poly->yv[0], poly->xv[1], poly->yv[1]); startangle = figureangle(poly->xv[0], poly->yv[0], poly->xv[2], poly->yv[2]); if (endangle > startangle) { if (ang < startangle || ang > endangle) return(FALSE); angrange = endangle - startangle; } else { if (ang < startangle && ang > endangle) return(FALSE); angrange = 3600 - startangle + endangle; } /* now see if the point is the proper distance from the center of the arc */ dist = computedistance(poly->xv[0], poly->yv[0], x, y); if (ang == startangle || angrange == 0) { wantdist = computedistance(poly->xv[0], poly->yv[0], poly->xv[1], poly->yv[1]); } else if (ang == endangle) { wantdist = computedistance(poly->xv[0], poly->yv[0], poly->xv[2], poly->yv[2]); } else { startdist = computedistance(poly->xv[0], poly->yv[0], poly->xv[1], poly->yv[1]); enddist = computedistance(poly->xv[0], poly->yv[0], poly->xv[2], poly->yv[2]); if (enddist == startdist) wantdist = startdist; else { wantdist = startdist + (ang - startangle) / angrange * (enddist - startdist); } } if (dist == wantdist) return(TRUE); return(FALSE); } /* I give up */ return(FALSE); } /* * Routine to compute the minimum size of polygon "poly". * Only works with manhattan geometry. */ INTBIG polyminsize(POLYGON *poly) { INTBIG xl, xh, yl, yh; if (isbox(poly, &xl, &xh, &yl, &yh)) { if (xh-xl < yh-yl) return(xh-xl); return(yh-yl); } return(0); } /* * Routine to determine whether polygon "poly" intersects the rectangle defined by * lx <= X <= hx and ly <= Y <= hy. Returns true if so. */ BOOLEAN polyinrect(POLYGON *poly, INTBIG lx, INTBIG hx, INTBIG ly, INTBIG hy) { REGISTER INTBIG i, count; INTBIG sx, sy, ex, ey, plx, phx, ply, phy; REGISTER POLYGON *mypoly; switch (poly->style) { case FILLED: if (isinside(lx, ly, poly)) return(TRUE); if (isinside(lx, hy, poly)) return(TRUE); if (isinside(hx, hy, poly)) return(TRUE); if (isinside(hx, ly, poly)) return(TRUE); /* FALLTHROUGH */ case CLOSED: case OPENED: case OPENEDT1: case OPENEDT2: case OPENEDT3: case OPENEDO1: for(i=0; icount; i++) { if (i == 0) { if (poly->style != CLOSED) continue; sx = poly->xv[poly->count-1]; sy = poly->yv[poly->count-1]; } else { sx = poly->xv[i-1]; sy = poly->yv[i-1]; } ex = poly->xv[i]; ey = poly->yv[i]; if (!clipline(&sx, &sy, &ex, &ey, lx, hx, ly, hy)) return(TRUE); } return(FALSE); case VECTORS: for(i=0; icount; i += 2) { sx = poly->xv[i]; sy = poly->yv[i]; ex = poly->xv[i+1]; ey = poly->yv[i+1]; if (!clipline(&sx, &sy, &ex, &ey, lx, hx, ly, hy)) return(TRUE); } return(FALSE); case CIRCLE: case THICKCIRCLE: case DISC: case CIRCLEARC: case THICKCIRCLEARC: mypoly = allocpolygon(poly->count, db_cluster); mypoly->count = poly->count; mypoly->style = poly->style; for(i=0; icount; i++) { mypoly->xv[i] = poly->xv[i]; mypoly->yv[i] = poly->yv[i]; } cliparc(mypoly, lx, hx, ly, hy); count = mypoly->count; freepolygon(mypoly); if (count != 0) return(TRUE); return(FALSE); } getbbox(poly, &plx, &phx, &ply, &phy); if (phx < lx || plx > hx || phy < ly || ply > hy) return(FALSE); return(TRUE); } /* * compute and return the area of the polygon in "poly". The calculation * may return a negative value if the polygon points are counter-clockwise */ float areapoly(POLYGON *poly) { REGISTER INTBIG sign; float area; INTBIG xl, xh, yl, yh; switch (poly->style) { case FILLED: case CLOSED: case FILLEDRECT: case CLOSEDRECT: case CROSSED: case TEXTCENT: case TEXTTOP: case TEXTBOT: case TEXTLEFT: case TEXTRIGHT: case TEXTTOPLEFT: case TEXTBOTLEFT: case TEXTTOPRIGHT: case TEXTBOTRIGHT: case TEXTBOX: if (isbox(poly, &xl, &xh, &yl, &yh)) { area = (float)(xh-xl); area *= (float)(yh-yl); /* now determine the sign of the area */ if (poly->xv[0] == poly->xv[1]) { /* first line is vertical */ sign = (poly->xv[2] - poly->xv[1]) * (poly->yv[1] - poly->yv[0]); } else { /* first line is horizontal */ sign = (poly->xv[1] - poly->xv[0]) * (poly->yv[1] - poly->yv[2]); } if (sign < 0) area = -area; return(area); } return(areapoints(poly->count, poly->xv, poly->yv)); } return(0.0); } /* * reverse the edge order of a polygon */ void reversepoly(POLYGON *poly) { REGISTER INTBIG i, invi; REGISTER INTBIG mx, my; for (i = 0, invi = poly->count-1; ixv[invi]; my = poly->yv[invi]; poly->xv[invi] = poly->xv[i]; poly->yv[invi] = poly->yv[i]; poly->xv[i] = mx; poly->yv[i] = my; } } /* * Compute and return the area of the polygon in the "count" points (x,y). * The calculation may return a negative value if the polygon points are * counter-clockwise. */ float areapoints(INTBIG count, INTBIG *x, INTBIG *y) { REGISTER INTBIG i, x0, y0, x1, y1; float p1, p2, partial, area; area = 0.0; x0 = x[0]; y0 = y[0]; for (i=1; istyle) { case FILLED: case FILLEDRECT: case CROSSED: case CROSS: case BIGCROSS: case TEXTCENT: case TEXTTOP: case TEXTBOT: case TEXTLEFT: case TEXTRIGHT: case TEXTTOPLEFT: case TEXTBOTLEFT: case TEXTTOPRIGHT: case TEXTBOTRIGHT: case TEXTBOX: if (isbox(poly, &xl, &xh, &yl, &yh)) { *x = (xl + xh) / 2; *y = (yl + yh) / 2; return; } *x = *y = 0; for(i=0; icount; i++) { *x += poly->xv[i]; *y += poly->yv[i]; } *x /= poly->count; *y /= poly->count; return; case CLOSED: /* merely use the center point */ *x = poly->xv[poly->count/2]; *y = poly->yv[poly->count/2]; return; case CLOSEDRECT: /* merely use the first point */ *x = poly->xv[0]; *y = poly->yv[0]; return; case OPENED: case OPENEDT1: case OPENEDT2: case OPENEDT3: /* if there are a odd number of lines, use center of middle one */ if ((poly->count & 1) == 0) { *x = (poly->xv[poly->count/2] + poly->xv[poly->count/2-1]) / 2; *y = (poly->yv[poly->count/2] + poly->yv[poly->count/2-1]) / 2; return; } /* FALLTHROUGH */ case VECTORS: /* if there are a odd number of lines, use center of middle one */ if ((poly->count & 3) == 0) { *x = (poly->xv[poly->count/2] + poly->xv[poly->count/2-1]) / 2; *y = (poly->yv[poly->count/2] + poly->yv[poly->count/2-1]) / 2; return; } *x = poly->xv[poly->count/2]; *y = poly->yv[poly->count/2]; return; case DISC: *x = poly->xv[0]; *y = poly->yv[0]; return; case CIRCLE: case THICKCIRCLE: case CIRCLEARC: case THICKCIRCLEARC: *x = poly->xv[1]; *y = poly->yv[1]; return; } } /* * routine to report the distance of point (x,y) to polygon "poly". The * routine returns a negative amount if the point is a direct hit on or in * the polygon (the more negative, the closer to the center) */ INTBIG polydistance(POLYGON *poly, INTBIG x, INTBIG y) { INTBIG lx, hx, ly, hy; REGISTER INTBIG sty, pang, sang, eang; REGISTER INTBIG i, dist, cx, cy, bestdist, odist, sdist, edist; /* handle single point polygons */ sty = poly->style; if (sty == CROSS || sty == BIGCROSS || poly->count == 1) { getcenter(poly, &lx, &ly); if (lx == x && ly == y) return(-MAXINTBIG); return(computedistance(lx, ly, x, y)); } /* handle polygons that are filled in */ if (sty == FILLED || sty == FILLEDRECT || sty == CROSSED || (sty >= TEXTCENT && sty <= TEXTBOX)) { /* give special returned value if point is a direct hit */ if (isinside(x, y, poly)) { getcenter(poly, &lx, &ly); return(computedistance(lx, ly, x, y) - MAXINTBIG); } /* if polygon is a box, use M.B.R. information */ if (isbox(poly, &lx, &hx, &ly, &hy)) { if (x > hx) cx = x - hx; else if (x < lx) cx = lx - x; else cx = 0; if (y > hy) cy = y - hy; else if (y < ly) cy = ly - y; else cy = 0; if (cx == 0 || cy == 0) return(cx + cy); return(computedistance(0, 0, cx, cy)); } /* point is outside of irregular polygon: fall into to next case */ if (sty == FILLEDRECT) sty = CLOSEDRECT; else sty = CLOSED; } /* handle closed outline figures */ if (sty == CLOSED) { bestdist = MAXINTBIG; for(i=0; icount; i++) { if (i == 0) { lx = poly->xv[poly->count-1]; ly = poly->yv[poly->count-1]; } else { lx = poly->xv[i-1]; ly = poly->yv[i-1]; } hx = poly->xv[i]; hy = poly->yv[i]; /* compute distance of close point to (x,y) */ dist = disttoline(lx,ly, hx,hy, x,y); if (dist < bestdist) bestdist = dist; } return(bestdist); } /* handle closed rectangle figures */ if (sty == CLOSEDRECT) { bestdist = MAXINTBIG; for(i=0; i<4; i++) { lx = poly->xv[db_rectx[i]]; ly = poly->yv[db_recty[i]]; hx = poly->xv[db_rectx[(i+1)&3]]; hy = poly->yv[db_recty[(i+1)&3]]; /* compute distance of close point to (x,y) */ dist = disttoline(lx,ly, hx,hy, x,y); if (dist < bestdist) bestdist = dist; } return(bestdist); } /* handle opened outline figures */ if (sty >= OPENED && sty <= OPENEDO1) { bestdist = MAXINTBIG; for(i=1; icount; i++) { lx = poly->xv[i-1]; ly = poly->yv[i-1]; hx = poly->xv[i]; hy = poly->yv[i]; /* compute distance of close point to (x,y) */ dist = disttoline(lx,ly, hx,hy, x,y); if (dist < bestdist) bestdist = dist; } return(bestdist); } /* handle outline vector lists */ if (sty == VECTORS) { bestdist = MAXINTBIG; for(i=0; icount; i += 2) { lx = poly->xv[i]; ly = poly->yv[i]; hx = poly->xv[i+1]; hy = poly->yv[i+1]; /* compute distance of close point to (x,y) */ dist = disttoline(lx,ly, hx,hy, x,y); if (dist < bestdist) bestdist = dist; } return(bestdist); } /* handle circular objects */ if (sty == CIRCLE || sty == THICKCIRCLE || sty == DISC) { odist = computedistance(poly->xv[0], poly->yv[0], poly->xv[1], poly->yv[1]); dist = computedistance(poly->xv[0], poly->yv[0], x, y); if (sty == DISC && dist < odist) return(dist-MAXINTBIG); return(abs(dist-odist)); } if (sty == CIRCLEARC || sty == THICKCIRCLEARC) { /* determine closest point to ends of arc */ sdist = computedistance(x, y, poly->xv[1], poly->yv[1]); edist = computedistance(x, y, poly->xv[2], poly->yv[2]); dist = mini(sdist,edist); /* see if the point is in the segment of the arc */ pang = figureangle(poly->xv[0], poly->yv[0], x, y); sang = figureangle(poly->xv[0], poly->yv[0], poly->xv[1], poly->yv[1]); eang = figureangle(poly->xv[0], poly->yv[0], poly->xv[2], poly->yv[2]); if (eang > sang) { if (pang < eang && pang > sang) return(dist); } else { if (pang < eang || pang > sang) return(dist); } /* point in arc: determine distance */ odist = computedistance(poly->xv[0], poly->yv[0], poly->xv[1], poly->yv[1]); dist = computedistance(poly->xv[0], poly->yv[0], x, y); return(abs(dist-odist)); } /* grid polygons cover everything */ if (sty == GRIDDOTS) return(-1); /* can't figure out others: use distance to polygon center */ getcenter(poly, &lx, &ly); return(computedistance(lx, ly, x, y)); } /* * Routine to return the distance between polygons "poly1" and "poly2". * Returns zero if they touch or overlap. */ INTBIG polyseparation(POLYGON *poly1, POLYGON *poly2) { INTBIG cx, cy; REGISTER INTBIG i, pd, minpd; /* stop now if they touch */ if (polyintersect(poly1, poly2)) return(0); /* look at all points on polygon 1 */ for(i=0; icount; i++) { cx = poly1->xv[i]; cy = poly1->yv[i]; closestpoint(poly2, &cx, &cy); pd = computedistance(poly1->xv[i], poly1->yv[i], cx, cy); if (pd <= 0) return(0); if (i == 0) minpd = pd; else { if (pd < minpd) minpd = pd; } } /* look at all points on polygon 2 */ for(i=0; icount; i++) { cx = poly2->xv[i]; cy = poly2->yv[i]; closestpoint(poly1, &cx, &cy); pd = computedistance(poly2->xv[i], poly2->yv[i], cx, cy); if (pd <= 0) return(0); if (pd < minpd) minpd = pd; } return(minpd); } /* * routine to return true if polygons "poly1" and "poly2" intersect (that is, * if any of their lines intersect). */ BOOLEAN polyintersect(POLYGON *poly1, POLYGON *poly2) { INTBIG lx1, hx1, ly1, hy1, lx2, hx2, ly2, hy2; REGISTER INTBIG i, px, py, tx, ty; /* quit now if bounding boxes don't overlap */ getbbox(poly1, &lx1, &hx1, &ly1, &hy1); getbbox(poly2, &lx2, &hx2, &ly2, &hy2); if (hx1 < lx2 || hx2 < lx1 || hy1 < ly2 || hy2 < ly1) return(FALSE); /* make sure these polygons are not the "RECT" type */ maketruerect(poly1); maketruerect(poly2); /* check each line in polygon 1 */ for(i=0; icount; i++) { if (i == 0) { if (poly1->style == OPENED || poly1->style == OPENEDT1 || poly1->style == OPENEDT2 || poly1->style == OPENEDT3 || poly1->style == VECTORS) continue; px = poly1->xv[poly1->count-1]; py = poly1->yv[poly1->count-1]; } else { px = poly1->xv[i-1]; py = poly1->yv[i-1]; } tx = poly1->xv[i]; ty = poly1->yv[i]; if (poly1->style == VECTORS && (i&1) != 0) i++; if (px == tx && py == ty) continue; /* compare this line with polygon 2 */ if (mini(px,tx) > hx2 || maxi(px,tx) < lx2 || mini(py,ty) > hy2 || maxi(py,ty) < ly2) continue; if (db_lineintersect(px,py, tx,ty, poly2)) return(TRUE); } return(FALSE); } /* * routine to return true if the line segment from (px1,py1) to (tx1,ty1) * intersects any line in polygon "poly" */ BOOLEAN db_lineintersect(INTBIG px1, INTBIG py1, INTBIG tx1, INTBIG ty1, POLYGON *poly) { REGISTER INTBIG i, px2, py2, tx2, ty2, ang, ang1, ang2; INTBIG ix, iy; for(i=0; icount; i++) { if (i == 0) { if (poly->style == OPENED || poly->style == OPENEDT1 || poly->style == OPENEDT2 || poly->style == OPENEDT3 || poly->style == VECTORS) continue; px2 = poly->xv[poly->count-1]; py2 = poly->yv[poly->count-1]; } else { px2 = poly->xv[i-1]; py2 = poly->yv[i-1]; } tx2 = poly->xv[i]; ty2 = poly->yv[i]; if (poly->style == VECTORS && (i&1) != 0) i++; if (px2 == tx2 && py2 == ty2) continue; /* special case: this line is vertical */ if (px2 == tx2) { /* simple bounds check */ if (mini(px1,tx1) > px2 || maxi(px1,tx1) < px2) continue; if (px1 == tx1) { if (mini(py1,ty1) > maxi(py2,ty2) || maxi(py1,ty1) < mini(py2,ty2)) continue; return(TRUE); } if (py1 == ty1) { if (mini(py2,ty2) > py1 || maxi(py2,ty2) < py1) continue; return(TRUE); } ang = figureangle(px1,py1, tx1,ty1); (void)intersect(px2,py2, 900, px1,py1, ang, &ix, &iy); if (ix != px2 || iy < mini(py2,ty2) || iy > maxi(py2,ty2)) continue; return(TRUE); } /* special case: this line is horizontal */ if (py2 == ty2) { /* simple bounds check */ if (mini(py1,ty1) > py2 || maxi(py1,ty1) < py2) continue; if (py1 == ty1) { if (mini(px1,tx1) > maxi(px2,tx2) || maxi(px1,tx1) < mini(px2,tx2)) continue; return(TRUE); } if (px1 == tx1) { if (mini(px2,tx2) > px1 || maxi(px2,tx2) < px1) continue; return(TRUE); } ang = figureangle(px1,py1, tx1,ty1); (void)intersect(px2,py2, 0, px1,py1, ang, &ix, &iy); if (iy != py2 || ix < mini(px2,tx2) || ix > maxi(px2,tx2)) continue; return(TRUE); } /* simple bounds check */ if (mini(px1,tx1) > maxi(px2,tx2) || maxi(px1,tx1) < mini(px2,tx2) || mini(py1,ty1) > maxi(py2,ty2) || maxi(py1,ty1) < mini(py2,ty2)) continue; /* general case of line intersection */ ang1 = figureangle(px1,py1, tx1,ty1); ang2 = figureangle(px2,py2, tx2,ty2); (void)intersect(px2, py2, ang2, px1, py1, ang1, &ix, &iy); if (ix < mini(px2,tx2) || ix > maxi(px2,tx2) || iy < mini(py2,ty2) || iy > maxi(py2,ty2) || ix < mini(px1,tx1) || ix > maxi(px1,tx1) || iy < mini(py1,ty1) || iy > maxi(py1,ty1)) continue; return(TRUE); } return(FALSE); } /* * routine to determine the closest point on polygon "poly" to the point * (*x, *y) and return that point in (*x, *y). Thus, the coordinate value * is adjusted to the closest point in or on the polygon */ void closestpoint(POLYGON *poly, INTBIG *x, INTBIG *y) { INTBIG lx, hx, ly, hy, nx, ny; REGISTER INTBIG i, dist, gx, gy, bestdist; switch (poly->style) { case CROSS: case BIGCROSS: /* single point polygons simply use the center */ getcenter(poly, x, y); return; case FILLED: case FILLEDRECT: case CROSSED: case TEXTCENT: case TEXTTOP: case TEXTBOT: case TEXTLEFT: case TEXTRIGHT: case TEXTTOPLEFT: case TEXTBOTLEFT: case TEXTTOPRIGHT: case TEXTBOTRIGHT: case TEXTBOX: /* filled polygon: check for regularity first */ if (isbox(poly, &lx, &hx, &ly, &hy)) { if (*x < lx) *x = lx; if (*x > hx) *x = hx; if (*y < ly) *y = ly; if (*y > hy) *y = hy; return; } if (poly->style == FILLED || poly->style == FILLEDRECT) { if (isinside(*x, *y, poly)) return; } /* FALLTHROUGH */ case CLOSED: /* check outline of description */ bestdist = MAXINTBIG; for(i=0; icount; i++) { nx = *x; ny = *y; if (i == 0) { lx = poly->xv[poly->count-1]; ly = poly->yv[poly->count-1]; } else { lx = poly->xv[i-1]; ly = poly->yv[i-1]; } dist = closestpointtosegment(lx,ly, poly->xv[i], poly->yv[i], &nx, &ny); if (dist > bestdist) continue; bestdist = dist; gx = nx; gy = ny; } *x = gx; *y = gy; return; case CLOSEDRECT: /* check outline of description */ bestdist = MAXINTBIG; for(i=0; i<4; i++) { nx = *x; ny = *y; lx = poly->xv[db_rectx[i]]; ly = poly->yv[db_recty[i]]; hx = poly->xv[db_rectx[(i+1)&3]]; hy = poly->yv[db_recty[(i+1)&3]]; dist = closestpointtosegment(lx,ly, hx, hy, &nx, &ny); if (dist > bestdist) continue; bestdist = dist; gx = nx; gy = ny; } *x = gx; *y = gy; return; case OPENED: case OPENEDT1: case OPENEDT2: case OPENEDT3: /* check outline of description */ bestdist = MAXINTBIG; for(i=1; icount; i++) { nx = *x; ny = *y; dist = closestpointtosegment(poly->xv[i-1], poly->yv[i-1], poly->xv[i], poly->yv[i], &nx, &ny); if (dist > bestdist) continue; bestdist = dist; gx = nx; gy = ny; } *x = gx; *y = gy; return; case VECTORS: /* check outline of description */ bestdist = MAXINTBIG; for(i=0; icount; i = i + 2) { nx = *x; ny = *y; dist = closestpointtosegment(poly->xv[i], poly->yv[i], poly->xv[i+1], poly->yv[i+1], &nx, &ny); if (dist > bestdist) continue; bestdist = dist; gx = nx; gy = ny; } *x = gx; *y = gy; return; } } /* * routine to determine the minimum bounding rectangle of the polygon in * "poly" and return it in the reference parameters "lx", "hx", "ly", and "hy" */ void getbbox(POLYGON *poly, INTBIG *lx, INTBIG *hx, INTBIG *ly, INTBIG *hy) { REGISTER INTBIG i, dist; /* rectangular styles store information differently */ if (poly->style == FILLEDRECT || poly->style == CLOSEDRECT) { *lx = mini(poly->xv[0], poly->xv[1]); *hx = maxi(poly->xv[0], poly->xv[1]); *ly = mini(poly->yv[0], poly->yv[1]); *hy = maxi(poly->yv[0], poly->yv[1]); return; } /* special code for circles */ if (poly->style == CIRCLE || poly->style == THICKCIRCLE || poly->style == DISC) { dist = computedistance(poly->xv[0], poly->yv[0], poly->xv[1], poly->yv[1]); *lx = poly->xv[0] - dist; *hx = poly->xv[0] + dist; *ly = poly->yv[0] - dist; *hy = poly->yv[0] + dist; return; } /* special code for arcs */ if (poly->style == CIRCLEARC || poly->style == THICKCIRCLEARC) { arcbbox(poly->xv[1], poly->yv[1], poly->xv[2], poly->yv[2], poly->xv[0], poly->yv[0], lx, hx, ly, hy); return; } /* just compute the bounds of the points */ *lx = *hx = poly->xv[0]; *ly = *hy = poly->yv[0]; for(i=1; icount; i++) { if (poly->xv[i] < *lx) *lx = poly->xv[i]; if (poly->xv[i] > *hx) *hx = poly->xv[i]; if (poly->yv[i] < *ly) *ly = poly->yv[i]; if (poly->yv[i] > *hy) *hy = poly->yv[i]; } } /* * routine to compare two polygons and return true if they are the same */ BOOLEAN polysame(POLYGON *poly1, POLYGON *poly2) { INTBIG xl1, xh1, yl1, yh1, xl2, xh2, yl2, yh2; REGISTER INTBIG i; /* polygons must have the same number of points */ if (poly1->count != poly2->count) return(FALSE); /* if both are boxes, compare their extents */ if (isbox(poly1, &xl1, &xh1, &yl1, &yh1)) { if (isbox(poly2, &xl2, &xh2, &yl2, &yh2)) { /* compare box extents */ if (xl1 == xl2 && xh1 == xh2 && yl1 == yl2 && yh1 == yh2) return(TRUE); } return(FALSE); } else if (isbox(poly2, &xl2, &xh2, &yl2, &yh2)) return(FALSE); /* compare these boxes the hard way */ for(i=0; icount; i++) if (poly1->xv[i] != poly2->xv[i] || poly1->yv[i] != poly2->yv[i]) return(FALSE); return(TRUE); } /* * routine to copy polygon "spoly" to polygon "dpoly" */ void polycopy(POLYGON *dpoly, POLYGON *spoly) { REGISTER INTBIG i; if (dpoly->limit < spoly->count) (void)extendpolygon(dpoly, spoly->count); for(i=0; icount; i++) { dpoly->xv[i] = spoly->xv[i]; dpoly->yv[i] = spoly->yv[i]; } dpoly->count = spoly->count; dpoly->style = spoly->style; dpoly->string = spoly->string; TDCOPY(dpoly->textdescript, spoly->textdescript); dpoly->tech = spoly->tech; dpoly->desc = spoly->desc; dpoly->layer = spoly->layer; dpoly->portproto = spoly->portproto; } /* * routine to make a polygon that describes the rectangle running from * (lx,ly) to (hx,hy). */ void makerectpoly(INTBIG lx, INTBIG ux, INTBIG ly, INTBIG uy, POLYGON *poly) { if (poly->limit < 4) (void)extendpolygon(poly, 4); poly->xv[0] = poly->xv[1] = lx; poly->xv[2] = poly->xv[3] = ux; poly->yv[0] = poly->yv[3] = ly; poly->yv[1] = poly->yv[2] = uy; poly->count = 4; } /* * routine to make a rectangle polygon that describes the rectangle running from * (lx,ly) to (hx,hy). */ void maketruerectpoly(INTBIG lx, INTBIG ux, INTBIG ly, INTBIG uy, POLYGON *poly) { if (poly->limit < 2) (void)extendpolygon(poly, 2); poly->xv[0] = lx; poly->xv[1] = ux; poly->yv[0] = ly; poly->yv[1] = uy; poly->count = 2; } /* * routine to reduce polygon "poly" by the proper amount given that it is the * description of port "pp" on nodeinst "ni" and will be connected to an arc * with width "wid" (this arc width should be the offset width, not the actual * width). The angle of the arc is "angle" (negative if angle should not be * considered). The polygon is modified. */ void reduceportpoly(POLYGON *poly, NODEINST *ni, PORTPROTO *pp, INTBIG wid, INTBIG angle) { INTBIG lx, ly, hx, hy, cx, cy, bx, by, ux, uy, plx, phx, ply, phy; REGISTER INTBIG j, realwid, dist, swapi; XARRAY trans, localtran, t1; /* find bottommost node */ makerot(ni, trans); while (ni->proto->primindex == 0) { maketrans(ni, localtran); transmult(localtran, trans, t1); ni = pp->subnodeinst; pp = pp->subportproto; makerot(ni, localtran); transmult(localtran, t1, trans); } /* do not reduce port if not filled */ if (poly->style != FILLED && poly->style != FILLEDRECT && poly->style != CROSSED && poly->style != DISC) return; /* do not reduce port areas on polygonally defined nodes */ if (gettrace(ni) != NOVARIABLE) return; /* determine amount to reduce port */ realwid = wid / 2; /* get bounding box of port polygon */ if (!isbox(poly, &bx, &ux, &by, &uy)) { /* special case: nonrectangular port */ if (poly->style == DISC) { /* shrink discs */ dist = computedistance(poly->xv[0], poly->yv[0], poly->xv[1], poly->yv[1]); dist = maxi(0, dist-realwid); poly->xv[1] = poly->xv[0] + dist; poly->yv[1] = poly->yv[0]; return; } /* cannot handle polygons yet */ return; } /* determine the center of the port polygon */ getcenter(poly, &cx, &cy); /* compute the area of the nodeinst */ nodesizeoffset(ni, &plx, &ply, &phx, &phy); xform(ni->lowx+plx, ni->lowy+ply, &lx, &ly, trans); xform(ni->highx-phx, ni->highy-phy, &hx, &hy, trans); if (lx > hx) { swapi = lx; lx = hx; hx = swapi; } if (ly > hy) { swapi = ly; ly = hy; hy = swapi; } /* do not reduce in X if arc is horizontal */ if (angle != 0 && angle != 1800) { /* determine reduced port area */ lx = maxi(bx, lx + realwid); hx = mini(ux, hx - realwid); if (hx < lx) hx = lx = (hx + lx) / 2; /* only clip in X if the port area is within of the reduced node X area */ if (ux >= lx && bx <= hx) for(j=0; jcount; j++) { if (poly->xv[j] < lx) poly->xv[j] = lx; if (poly->xv[j] > hx) poly->xv[j] = hx; } } /* do not reduce in Y if arc is vertical */ if (angle != 900 && angle != 2700) { /* determine reduced port area */ ly = maxi(by, ly + realwid); hy = mini(uy, hy - realwid); if (hy < ly) hy = ly = (hy + ly) / 2; /* only clip in Y if the port area is inside of the reduced node Y area */ if (uy >= ly && by <= hy) for(j=0; jcount; j++) { if (poly->yv[j] < ly) poly->yv[j] = ly; if (poly->yv[j] > hy) poly->yv[j] = hy; } } } /* * Routine that splits the polygon "which" horizontally at "yl". * The part above is placed in "abovep" and the part below in "belowp" * Returns true on error. */ BOOLEAN polysplithoriz(INTBIG yl, POLYGON *which, POLYGON **abovep, POLYGON **belowp) { INTBIG xt, yt, xn, yn, i, pind, x, y; POLYGON *above, *below; /* create two new polygons and delete the original */ above = allocpolygon(4, which->cluster); if (above == 0) return(TRUE); below = allocpolygon(4, which->cluster); if (below == 0) return(TRUE); above->count = below->count = 0; /* run through points in polygon to be split */ for(i=0; icount; i++) { if (i == 0) pind = which->count-1; else pind = i-1; xt = which->xv[pind]; yt = which->yv[pind]; xn = which->xv[i]; yn = which->yv[i]; /* if point is on line, put in both polygons */ if (yn == yl) { if (db_addpointtopoly(xn, yn, above)) return(TRUE); if (db_addpointtopoly(xn, yn, below)) return(TRUE); continue; } /* if both points are on same side, put in appropriate polygon */ if (yn >= yl && yt >= yl) { if (db_addpointtopoly(xn, yn, above)) return(TRUE); continue; } if (yn <= yl && yt <= yl) { if (db_addpointtopoly(xn, yn, below)) return(TRUE); continue; } /* lines cross, intersect them */ y = yl; if (yn == yl) x = xn; else if (yt == yl) x = xt; else { x = xt + muldiv(y-yt, xn-xt, yn-yt); } /* insert new point in polygons */ if (yt <= yl && yn >= yl) { if (db_addpointtopoly(x, y, above)) return(TRUE); if (db_addpointtopoly(x, y, below)) return(TRUE); if (db_addpointtopoly(xn, yn, above)) return(TRUE); continue; } if (yt >= yl && yn <= yl) { if (db_addpointtopoly(x, y, above)) return(TRUE); if (db_addpointtopoly(x, y, below)) return(TRUE); if (db_addpointtopoly(xn, yn, below)) return(TRUE); continue; } } *abovep = above; *belowp = below; return(FALSE); } /* * Routine that splits the polygon "which" vertically at "xl". * The part to the left is placed in "leftp" and the part to the right in "rightp". * Returns true on error. */ BOOLEAN polysplitvert(INTBIG xl, POLYGON *which, POLYGON **leftp, POLYGON **rightp) { INTBIG xt, yt, xn, yn, i, pind, x, y; POLYGON *left, *right; /* create two new polygons and delete the original */ left = allocpolygon(4, which->cluster); if (left == 0) return(TRUE); right = allocpolygon(4, which->cluster); if (right == 0) return(TRUE); left->count = right->count = 0; /* run through points in polygon to be split */ for(i=0; icount; i++) { if (i == 0) pind = which->count-1; else pind = i-1; xt = which->xv[pind]; yt = which->yv[pind]; xn = which->xv[i]; yn = which->yv[i]; /* if point is on line, put in both polygons */ if (xn == xl) { if (db_addpointtopoly(xn, yn, left)) return(TRUE); if (db_addpointtopoly(xn, yn, right)) return(TRUE); continue; } /* if both points are on same side, put in appropriate polygon */ if (xn <= xl && xt <= xl) { if (db_addpointtopoly(xn, yn, left)) return(TRUE); continue; } if (xn >= xl && xt >= xl) { if (db_addpointtopoly(xn, yn, right)) return(TRUE); continue; } /* lines cross, intersect them */ x = xl; if (xn == xl) y = yn; else if (xt == xl) y = yt; else { y = yt + muldiv(x-xt, yn-yt, xn-xt); } /* insert new point in polygons */ if (xt >= xl && xn <= xl) { if (db_addpointtopoly(x, y, left)) return(TRUE); if (db_addpointtopoly(x, y, right)) return(TRUE); if (db_addpointtopoly(xn, yn, left)) return(TRUE); continue; } if (xt <= xl && xn >= xl) { if (db_addpointtopoly(x, y, left)) return(TRUE); if (db_addpointtopoly(x, y, right)) return(TRUE); if (db_addpointtopoly(xn, yn, right)) return(TRUE); continue; } } *leftp = left; *rightp = right; return(FALSE); } BOOLEAN db_addpointtopoly(INTBIG x, INTBIG y, POLYGON *poly) { if (poly->count >= poly->limit) { if (extendpolygon(poly, poly->limit*2)) return(TRUE); } poly->xv[poly->count] = x; poly->yv[poly->count] = y; poly->count++; return(FALSE); } /************************* CLIPPING *************************/ /* * Routine to clip a line from (fx,fy) to (tx,ty) in the rectangle lx <= X <= hx and ly <= Y <= hy. * Returns true if the line is not visible. */ BOOLEAN clipline(INTBIG *fx, INTBIG *fy, INTBIG *tx, INTBIG *ty, INTBIG lx, INTBIG hx, INTBIG ly, INTBIG hy) { REGISTER INTBIG t, fc, tc; for(;;) { /* compute code bits for "from" point */ fc = 0; if (*fx < lx) fc |= LEFT; else if (*fx > hx) fc |= RIGHT; if (*fy < ly) fc |= BOTTOM; else if (*fy > hy) fc |= TOP; /* compute code bits for "to" point */ tc = 0; if (*tx < lx) tc |= LEFT; else if (*tx > hx) tc |= RIGHT; if (*ty < ly) tc |= BOTTOM; else if (*ty > hy) tc |= TOP; /* look for trivial acceptance or rejection */ if (fc == 0 && tc == 0) return(FALSE); if (fc == tc || (fc & tc) != 0) return(TRUE); /* make sure the "from" side needs clipping */ if (fc == 0) { t = *fx; *fx = *tx; *tx = t; t = *fy; *fy = *ty; *ty = t; t = fc; fc = tc; tc = t; } if ((fc&LEFT) != 0) { if (*tx == *fx) return(TRUE); t = muldiv(*ty - *fy, lx - *fx, *tx - *fx); *fy += t; *fx = lx; } if ((fc&RIGHT) != 0) { if (*tx == *fx) return(TRUE); t = muldiv(*ty - *fy, hx - *fx, *tx - *fx); *fy += t; *fx = hx; } if ((fc&BOTTOM) != 0) { if (*ty == *fy) return(TRUE); t = muldiv(*tx - *fx, ly - *fy, *ty - *fy); *fx += t; *fy = ly; } if ((fc&TOP) != 0) { if (*ty == *fy) return(TRUE); t = muldiv(*tx - *fx, hy - *fy, *ty - *fy); *fx += t; *fy = hy; } } } typedef struct { double angle; INTBIG x, y; } ANGLELIST; /* * Helper routine for "esort" that makes angles go in descending order (used by "cliparc()"). */ int db_anglelistdescending(const void *e1, const void *e2) { REGISTER ANGLELIST *c1, *c2; REGISTER double diff; c1 = (ANGLELIST *)e1; c2 = (ANGLELIST *)e2; diff = c2->angle - c1->angle; if (diff < 0.0) return(-1); if (diff > 0.0) return(1); return(0); } /* * Routine to clips curved polygon (CIRCLE, THICKCIRCLE, DISC, CIRCLEARC, or THICKCIRCLEARC) * against the rectangle lx <= X <= hx and ly <= Y <= hy. * Adjusts the polygon to contain the visible portions. */ void cliparc(POLYGON *in, INTBIG lx, INTBIG hx, INTBIG ly, INTBIG hy) { INTBIG plx, ply, phx, phy, ix1, iy1, ix2, iy2; REGISTER INTBIG xc, yc, xp, yp, midx, midy; double radius, midangle, dx, dy; REGISTER INTBIG i, j, intcount, ints, initialcount, prev; ANGLELIST anglelist[10]; getbbox(in, &plx, &phx, &ply, &phy); /* if not clipped, stop now */ if (plx >= lx && phx <= hx && ply >= ly && phy <= hy) return; /* if totally invisible, blank the polygon */ if (plx > hx || phx < lx || ply > hy || phy < ly) { in->count = 0; return; } /* initialize list of relevant points */ xc = in->xv[0]; yc = in->yv[0]; xp = in->xv[1]; yp = in->yv[1]; intcount = 0; if (in->style == CIRCLEARC || in->style == THICKCIRCLEARC) { /* include arc endpoints */ anglelist[intcount].x = xp; anglelist[intcount].y = yp; dx = (double)(xp-xc); dy = (double)(yp-yc); if (dx == 0.0 && dy == 0.0) { ttyputerr(_("Domain error doing circle/circle tangents")); in->count = 0; return; } anglelist[intcount].angle = atan2(dy, dx); intcount++; anglelist[intcount].x = in->xv[2]; anglelist[intcount].y = in->yv[2]; dx = (double)(anglelist[intcount].x-xc); dy = (double)(anglelist[intcount].y-yc); if (dx == 0.0 && dy == 0.0) { ttyputerr(_("Domain error doing circle/circle tangents")); in->count = 0; return; } anglelist[intcount].angle = atan2(dy, dx); intcount++; } initialcount = intcount; /* find intersection points along left edge */ ints = circlelineintersection(xc, yc, xp, yp, lx, ly, lx, hy, &ix1, &iy1, &ix2, &iy2, 0); if (ints > 0) { anglelist[intcount].x = ix1; anglelist[intcount++].y = iy1; } if (ints > 1) { anglelist[intcount].x = ix2; anglelist[intcount++].y = iy2; } /* find intersection points along top edge */ ints = circlelineintersection(xc, yc, xp, yp, lx, hy, hx, hy, &ix1, &iy1, &ix2, &iy2, 0); if (ints > 0) { anglelist[intcount].x = ix1; anglelist[intcount++].y = iy1; } if (ints > 1) { anglelist[intcount].x = ix2; anglelist[intcount++].y = iy2; } /* find intersection points along right edge */ ints = circlelineintersection(xc, yc, xp, yp, hx, hy, hx, ly, &ix1, &iy1, &ix2, &iy2, 0); if (ints > 0) { anglelist[intcount].x = ix1; anglelist[intcount++].y = iy1; } if (ints > 1) { anglelist[intcount].x = ix2; anglelist[intcount++].y = iy2; } /* find intersection points along bottom edge */ ints = circlelineintersection(xc, yc, xp, yp, hx, ly, lx, ly, &ix1, &iy1, &ix2, &iy2, 0); if (ints > 0) { anglelist[intcount].x = ix1; anglelist[intcount++].y = iy1; } if (ints > 1) { anglelist[intcount].x = ix2; anglelist[intcount++].y = iy2; } /* if there are no intersections, arc is invisible */ if (intcount == initialcount) { in->count = 0; return; } /* determine angle of intersection points */ for(i=initialcount; icount = 0; return; } dx = (double)(anglelist[i].x-xc); dy = (double)(anglelist[i].y-yc); if (dx == 0.0 && dy == 0.0) { ttyputerr(_("Domain error doing circle/circle tangents")); in->count = 0; return; } anglelist[i].angle = atan2(dy, dx); } /* reject points not on the arc */ if (in->style == CIRCLEARC || in->style == THICKCIRCLEARC) { j = 2; for(i=2; i anglelist[1].angle) { if (anglelist[i].angle > anglelist[0].angle || anglelist[i].angle < anglelist[1].angle) continue; } else { if (anglelist[i].angle > anglelist[0].angle && anglelist[i].angle < anglelist[1].angle) continue; } anglelist[j].x = anglelist[i].x; anglelist[j].y = anglelist[i].y; anglelist[j].angle = anglelist[i].angle; j++; } intcount = j; /* make sure the start of the arc is the first point */ for(i=0; i anglelist[0].angle) anglelist[i].angle -= EPI*2.0; } else { /* make sure all angles are negative */ for(i=0; i 0.0) anglelist[i].angle -= EPI*2.0; } /* sort by angle */ esort(anglelist, intcount, sizeof (ANGLELIST), db_anglelistdescending); /* for full circles, add in starting point to complete circle */ if (in->style != CIRCLEARC && in->style != THICKCIRCLEARC) { anglelist[intcount].x = anglelist[0].x; anglelist[intcount].y = anglelist[0].y; anglelist[intcount].angle = anglelist[0].angle - EPI*2.0; intcount++; } /* now examine each segment and add it, if it is in the window */ radius = (double)computedistance(xc, yc, xp, yp); in->count = 0; for(i=1; i hx || midy < ly || midy > hy) continue; /* add this segment */ if (in->limit < in->count+3) (void)extendpolygon(in, in->count+3); in->xv[in->count] = xc; in->yv[in->count++] = yc; in->xv[in->count] = anglelist[prev].x; in->yv[in->count++] = anglelist[prev].y; in->xv[in->count] = anglelist[i].x; in->yv[in->count++] = anglelist[i].y; } if (in->style == THICKCIRCLE) in->style = THICKCIRCLEARC; else if (in->style == CIRCLE) in->style = CIRCLEARC; } void clippoly(POLYGON *in, INTBIG lx, INTBIG hx, INTBIG ly, INTBIG hy) { REGISTER INTBIG i; REGISTER INTBIG pre; REGISTER POLYGON *a, *b, *swap; REGISTER POLYGON *out; /* see if any points are outside */ pre = 0; for(i=0; icount; i++) { if (in->xv[i] < lx) pre |= LEFT; else if (in->xv[i] > hx) pre |= RIGHT; if (in->yv[i] < ly) pre |= BOTTOM; else if (in->yv[i] > hy) pre |= TOP; } if (pre == 0) return; /* get polygon */ out = allocpolygon(4, db_cluster); /* clip on all four sides */ a = in; b = out; out->style = in->style; if ((pre & LEFT) != 0) { db_clipedge(a, b, LEFT, lx); swap = a; a = b; b = swap; } if ((pre & RIGHT) != 0) { db_clipedge(a, b, RIGHT, hx); swap = a; a = b; b = swap; } if ((pre & TOP) != 0) { db_clipedge(a, b, TOP, hy); swap = a; a = b; b = swap; } if ((pre & BOTTOM) != 0) { db_clipedge(a, b, BOTTOM, ly); swap = a; a = b; b = swap; } /* remove redundant points from polygon */ for(pre=0, i=0; icount; i++) { if (i > 0 && a->xv[i-1] == a->xv[i] && a->yv[i-1] == a->yv[i]) continue; if (pre >= b->limit) (void)extendpolygon(b, pre+1); b->xv[pre] = a->xv[i]; b->yv[pre++] = a->yv[i]; } /* if polygon is not opened, remove redundancy on wrap-around */ if (in->style != OPENED) while (pre != 0 && b->xv[0] == b->xv[pre-1] && b->yv[0] == b->yv[pre-1]) pre--; b->count = pre; /* copy the polygon back if it in the wrong place */ if (b != in) { if (in->limit < b->count) (void)extendpolygon(in, b->count); for(i=0; icount; i++) { in->xv[i] = b->xv[i]; in->yv[i] = b->yv[i]; } in->count = b->count; } freepolygon(out); } /* * routine to clip polygon "in" against line "edge" (1:left, 2:right, * 4:bottom, 8:top) and place clipped result in "out". */ void db_clipedge(POLYGON *in, POLYGON *out, INTBIG edge, INTBIG value) { REGISTER INTBIG outcount; REGISTER INTBIG i, pre, firstx, firsty; INTBIG x1, y1, x2, y2; /* look at all the lines */ outcount = 0; if (in->style != OPENED) { for(i=0; icount; i++) { if (i == 0) pre = in->count-1; else pre = i-1; x1 = in->xv[pre]; y1 = in->yv[pre]; x2 = in->xv[i]; y2 = in->yv[i]; if (db_clip(&x1, &y1, &x2, &y2, edge, value)) continue; if (outcount+1 >= out->limit) (void)extendpolygon(out, outcount+2); if (outcount != 0) { if (x1 != out->xv[outcount-1] || y1 != out->yv[outcount-1]) { out->xv[outcount] = x1; out->yv[outcount++] = y1; } } else { firstx = x1; firsty = y1; } out->xv[outcount] = x2; out->yv[outcount++] = y2; } if (outcount != 0 && (out->xv[outcount-1] != firstx || out->yv[outcount-1] != firsty)) { out->xv[outcount] = firstx; out->yv[outcount++] = firsty; } } else { for(i=0; icount-1; i++) { x1 = in->xv[i]; y1 = in->yv[i]; x2 = in->xv[i+1];y2 = in->yv[i+1]; if (db_clip(&x1, &y1, &x2, &y2, edge, value)) continue; if (out->limit < outcount+2) (void)extendpolygon(out, outcount+2); out->xv[outcount] = x1; out->yv[outcount++] = y1; out->xv[outcount] = x2; out->yv[outcount++] = y2; } } out->count = outcount; } /* * Routine to do clipping on the vector from (x1,y1) to (x2,y2). * If the vector is completely invisible, true is returned. */ BOOLEAN db_clip(INTBIG *xp1, INTBIG *yp1, INTBIG *xp2, INTBIG *yp2, INTBIG codebit, INTBIG value) { REGISTER INTBIG t, x1, y1, x2, y2, c1, c2; REGISTER BOOLEAN flip; x1 = *xp1; y1 = *yp1; x2 = *xp2; y2 = *yp2; c1 = c2 = 0; if (codebit == LEFT) { if (x1 < value) c1 = codebit; if (x2 < value) c2 = codebit; } else if (codebit == BOTTOM) { if (y1 < value) c1 = codebit; if (y2 < value) c2 = codebit; } else if (codebit == RIGHT) { if (x1 > value) c1 = codebit; if (x2 > value) c2 = codebit; } else if (codebit == TOP) { if (y1 > value) c1 = codebit; if (y2 > value) c2 = codebit; } if (c1 == c2) return(c1 != 0); if (c1 == 0) { t = x1; x1 = x2; x2 = t; t = y1; y1 = y2; y2 = t; flip = TRUE; } else flip = FALSE; if (codebit == LEFT || codebit == RIGHT) { t = muldiv(y2-y1, value-x1, x2-x1); y1 += t; x1 = value; } else if (codebit == BOTTOM || codebit == TOP) { t = muldiv(x2-x1, value-y1, y2-y1); x1 += t; y1 = value; } if (flip) { *xp1 = x2; *yp1 = y2; *xp2 = x1; *yp2 = y1; } else { *xp1 = x1; *yp1 = y1; *xp2 = x2; *yp2 = y2; } return(0); } /************************* WINDOWPART CONTROL *************************/ /* * routine to make a new window at location "l". If "protow" is not NOWINDOWPART, * use it for other information. Returns NOWINDOWPART upon error */ WINDOWPART *newwindowpart(CHAR *l, WINDOWPART *protow) { REGISTER WINDOWPART *w; REGISTER VARIABLE *var; REGISTER INTBIG lambda; if (db_windowpartfree == NOWINDOWPART) { w = (WINDOWPART *)emalloc((sizeof (WINDOWPART)), db_cluster); if (w == 0) { db_donextchangequietly = FALSE; return(NOWINDOWPART); } } else { /* take window from free list */ w = db_windowpartfree; db_windowpartfree = w->nextwindowpart; } if (protow != NOWINDOWPART) { copywindowpart(w, protow); } else { lambda = el_curlib->lambda[el_curtech->techindex]; w->uselx = -lambda * 10; w->usehx = lambda * 10; w->usely = -lambda * 10; w->usehy = lambda * 10; w->screenlx = -lambda * 10; w->screenhx = lambda * 10; w->screenly = -lambda * 10; w->screenhy = lambda * 10; w->hratio = w->vratio = 50; computewindowscale(w); w->curnodeproto = NONODEPROTO; w->topnodeproto = NONODEPROTO; w->inplacedepth = 0; transid(w->intocell); transid(w->outofcell); var = getval((INTBIG)us_tool, VTOOL, VFRACT|VISARRAY, x_("USER_default_grid")); if (var == NOVARIABLE) { w->gridx = w->gridy = WHOLE; } else { w->gridx = ((INTBIG *)var->addr)[0]; w->gridy = ((INTBIG *)var->addr)[1]; } w->state = DISPWINDOW; w->frame = getwindowframe(FALSE); w->charhandler = 0; w->buttonhandler = 0; w->changehandler = 0; w->termhandler = 0; w->redisphandler = 0; } if (allocstring(&w->location, l, db_cluster)) { db_donextchangequietly = FALSE; return(NOWINDOWPART); } w->editor = NOEDITOR; w->expwindow = (void *)-1; w->numvar = 0; if (db_enterwindowpart(w)) return(NOWINDOWPART); /* handle change control and broadcast */ if (!db_donextchangequietly && !db_dochangesquietly) { (void)db_change((INTBIG)w, OBJECTNEW, VWINDOWPART, 0, 0, 0, 0, 0); } db_donextchangequietly = FALSE; return(w); } /* * Routine to enter window "w" into the database. Returns true on error. */ BOOLEAN db_enterwindowpart(WINDOWPART *w) { WINDOWFRAME *wf; /* make a new frame if requested */ if ((w->state & HASOWNFRAME) != 0) { /* create a new frame */ wf = newwindowframe(FALSE, 0); if (wf == NOWINDOWFRAME) wf = getwindowframe(FALSE); w->frame = wf; if (wf != NOWINDOWFRAME) { /* recreating old frame: set size */ sizewindowframe(wf, w->framehx, w->framehy); } w->state &= ~HASOWNFRAME; } /* insert window in linked list */ w->nextwindowpart = el_topwindowpart; w->prevwindowpart = NOWINDOWPART; if (el_topwindowpart != NOWINDOWPART) el_topwindowpart->prevwindowpart = w; el_topwindowpart = w; return(FALSE); } void computewindowscale(WINDOWPART *w) { float denominator; w->scalex = (float)(w->usehx - w->uselx); denominator = (float)w->screenhx; denominator -= (float)w->screenlx; if (denominator != 0.0) w->scalex /= denominator; w->scaley = (float)(w->usehy - w->usely); denominator = (float)w->screenhy; denominator -= (float)w->screenly; if (denominator != 0.0) w->scaley /= denominator; } INTBIG applyxscale(WINDOWPART *w, INTBIG val) { return(roundfloat((float)val * w->scalex)); } INTBIG applyyscale(WINDOWPART *w, INTBIG val) { return(roundfloat((float)val * w->scaley)); } /* * routine to kill window "w" */ void killwindowpart(WINDOWPART *w) { db_retractwindowpart(w); /* handle change control and broadcast */ if (!db_donextchangequietly && !db_dochangesquietly) { (void)db_change((INTBIG)w, OBJECTKILL, VWINDOWPART, 0, 0, 0, 0, 0); } db_donextchangequietly = FALSE; } void db_retractwindowpart(WINDOWPART *w) { REGISTER WINDOWPART *ow; if (w->termhandler != 0) (*w->termhandler)(w); /* remove the window from the linked list */ if (w->prevwindowpart != NOWINDOWPART) w->prevwindowpart->nextwindowpart = w->nextwindowpart; if (w->nextwindowpart != NOWINDOWPART) w->nextwindowpart->prevwindowpart = w->prevwindowpart; if (w == el_topwindowpart) el_topwindowpart = w->nextwindowpart; /* see if this window lived by itself in a frame */ for(ow = el_topwindowpart; ow != NOWINDOWPART; ow = ow->nextwindowpart) if (ow->frame == w->frame) break; if (ow == NOWINDOWPART) { /* delete the frame too */ w->framelx = 0; w->framely = 0; getwindowframesize(w->frame, &w->framehx, &w->framehy); w->state |= HASOWNFRAME; killwindowframe(w->frame); } } /* * routine to return window "w" to the pool of free windows */ void freewindowpart(WINDOWPART *w) { if ((w->state&WINDOWTYPE) == TEXTWINDOW || (w->state&WINDOWTYPE) == POPTEXTWINDOW) { us_editorterm(w); } else if ((w->state&WINDOWTYPE) == EXPLORERWINDOW) { us_deleteexplorerstruct(w); } efree(w->location); w->nextwindowpart = db_windowpartfree; db_windowpartfree = w; } /* * routine to copy the contents of window "from" to window "to" */ void copywindowpart(WINDOWPART *to, WINDOWPART *from) { REGISTER INTBIG i; to->uselx = from->uselx; to->usehx = from->usehx; to->usely = from->usely; to->usehy = from->usehy; to->screenlx = from->screenlx; to->screenhx = from->screenhx; to->screenly = from->screenly; to->screenhy = from->screenhy; to->hratio = from->hratio; to->vratio = from->vratio; to->scalex = from->scalex; to->scaley = from->scaley; to->curnodeproto = from->curnodeproto; to->topnodeproto = from->topnodeproto; to->inplacedepth = from->inplacedepth; for(i=0; iinplacedepth; i++) to->inplacestack[i] = from->inplacestack[i]; transcpy(from->intocell, to->intocell); transcpy(from->outofcell, to->outofcell); to->gridx = from->gridx; to->gridy = from->gridy; to->state = from->state; to->frame = from->frame; to->editor = from->editor; to->expwindow = from->expwindow; to->buttonhandler = from->buttonhandler; to->charhandler = from->charhandler; to->changehandler = from->changehandler; to->termhandler = from->termhandler; to->redisphandler = from->redisphandler; } /*************************************** INTBIG OBJECTS ***************************************/ LISTINTBIG *newintlistobj(CLUSTER *clus) { REGISTER LISTINTBIG *li; li = (LISTINTBIG *)emalloc(sizeof (LISTINTBIG), clus); if (li == 0) return(0); li->count = li->total = 0; li->cluster = clus; return(li); } void killintlistobj(LISTINTBIG *li) { if (li->total > 0) efree((CHAR *)li->list); efree((CHAR *)li); } void clearintlistobj(LISTINTBIG *li) { li->count = 0; } INTBIG *getintlistobj(LISTINTBIG *li, INTBIG *count) { *count = li->count; return(li->list); } /* * Routine to ensure that the integer list "li" has "needed" entries in it. Returns TRUE on error. */ BOOLEAN ensureintlistobj(LISTINTBIG *li, INTBIG needed) { if (needed > li->total) { if (li->total > 0) efree((CHAR *)li->list); li->total = 0; li->list = (INTBIG *)emalloc(needed * SIZEOFINTBIG, li->cluster); if (li->list == 0) return(TRUE); li->total = needed; } return(FALSE); } /* * Routine to add value "i" to the end of the global list "li". If "unique" is TRUE, * does not add duplicate values. Returns true on error. */ BOOLEAN addtointlistobj(LISTINTBIG *li, INTBIG value, BOOLEAN unique) { REGISTER INTBIG newtotal, m, *newqueue; /* if a unique list is needed, check for duplications */ if (unique) { for(m=0; mcount; m++) if (li->list[m] == value) return(FALSE); } if (li->count >= li->total) { newtotal = li->total * 2; if (li->count >= newtotal) newtotal = li->count + 50; newqueue = (INTBIG *)emalloc(newtotal * SIZEOFINTBIG, li->cluster); if (newqueue == 0) return(TRUE); for(m=0; m < li->count; m++) newqueue[m] = li->list[m]; if (li->total > 0) efree((CHAR *)li->list); li->total = newtotal; li->list = newqueue; } li->list[li->count++] = value; return(FALSE); } /*************************************** STRING OBJECTS ***************************************/ /* * Routine to create a new string object from memory cluster "clus". Returns zero on error. */ STRINGOBJ *newstringobj(CLUSTER *clus) { REGISTER STRINGOBJ *so; so = (STRINGOBJ *)emalloc(sizeof (STRINGOBJ), clus); if (so == 0) return(0); so->total = 0; so->cluster = clus; return(so); } /* * Routine to delete new string object "so". */ void killstringobj(STRINGOBJ *so) { if (so->total > 0) efree((CHAR *)so->string); efree((CHAR *)so); } /* * Routine to clear the string in string object "so". */ void clearstringobj(STRINGOBJ *so) { so->count = 0; } /* * Routine to return the string in string object "so". */ CHAR *getstringobj(STRINGOBJ *so) { if (so->count == 0) return(x_("")); return(so->string); } /* * Routine to add "string" to the string in string object "so". */ void addstringtostringobj(CHAR *string, STRINGOBJ *so) { REGISTER INTBIG len, newtotal; REGISTER CHAR *newstring; len = estrlen(string); if (so->count + len >= so->total) { newtotal = so->total * 2; if (so->count + len > newtotal) newtotal = so->count + len + 10; newstring = (CHAR *)emalloc(newtotal * SIZEOFCHAR, so->cluster); if (newstring == 0) return; if (so->count > 0) strncpy(newstring, so->string, so->count); if (so->total > 0) efree((CHAR *)so->string); so->string = newstring; so->total = newtotal; } estrcpy(&so->string[so->count], string); so->count += len; } /************************* MISCELLANEOUS *************************/ /* * routine to return the value of lambda to use for object "geom" */ INTBIG figurelambda(GEOM *geom) { if (!geom->entryisnode) return(lambdaofarc(geom->entryaddr.ai)); return(lambdaofnode(geom->entryaddr.ni)); } /* * Routine to determine the proper value of lambda to use, given that * the work involves NODEPROTO "np". */ INTBIG lambdaofcell(NODEPROTO *np) { REGISTER TECHNOLOGY *tech; REGISTER LIBRARY *lib; tech = np->tech; if (np->primindex != 0) return(el_curlib->lambda[tech->techindex]); /* cell: figure out the proper technology and library */ lib = np->lib; return(lib->lambda[tech->techindex]); } /* * Routine to determine the proper value of lambda to use, given that * the work involves ARCINST "ai". */ INTBIG lambdaofarc(ARCINST *ai) { REGISTER TECHNOLOGY *tech; REGISTER LIBRARY *lib; REGISTER NODEPROTO *np; np = ai->parent; if (np == NONODEPROTO) tech = ai->proto->tech; else { tech = np->tech; if (tech == NOTECHNOLOGY) tech = whattech(np); } if (ai->parent == NONODEPROTO) lib = el_curlib; else lib = ai->parent->lib; return(lib->lambda[tech->techindex]); } /* * Routine to determine the proper value of lambda to use, given that * the work involves NODEINST "ni". */ INTBIG lambdaofnode(NODEINST *ni) { REGISTER TECHNOLOGY *tech; REGISTER LIBRARY *lib; REGISTER NODEPROTO *np; REGISTER INTBIG lambda; np = ni->parent; if (np == NONODEPROTO) np = ni->proto; tech = np->tech; if (tech == NOTECHNOLOGY) tech = whattech(np); if (ni->parent == NONODEPROTO) lib = el_curlib; else lib = ni->parent->lib; lambda = lib->lambda[tech->techindex]; return(lambda); } /* * routine to determine the technology of a cell. Gives preference to * the layout technologies (i.e. ignores "schematic" and "artwork" unless they * are the only elements in the cell). Someday this code should be * generalized to read special codes on the technologies that indicate * "layout" versus "symbolic". */ #define MAXTECHNOLOGIES 100 /* assumed maximum number of technologies (not hard limit) */ TECHNOLOGY *whattech(NODEPROTO *cell) { REGISTER INTBIG best, bestlayout, usecountneed, i, *usecount, *allocatedusecount; REGISTER BOOLEAN foundicons; INTBIG staticusecount[MAXTECHNOLOGIES]; REGISTER NODEPROTO *np, *onp, *cv, *cnp; REGISTER NODEINST *ni; REGISTER ARCINST *ai; REGISTER ARCPROTO *ap; REGISTER TECHNOLOGY *tech, *besttech, *bestlayouttech, *rettech; /* primitives know their technology */ if (cell->primindex != 0) return(cell->tech); /* ensure proper memory for usage counts */ usecountneed = 0; for(tech = el_technologies; tech != NOTECHNOLOGY; tech = tech->nexttechnology) if (tech->techindex > usecountneed) usecountneed = tech->techindex; usecountneed++; if (usecountneed > MAXTECHNOLOGIES) { allocatedusecount = (INTBIG *)emalloc(usecountneed * SIZEOFINTBIG, db_cluster); if (allocatedusecount == 0) return(gen_tech); usecount = allocatedusecount; } else { usecount = staticusecount; allocatedusecount = 0; } /* zero counters for every technology */ for(i=0; ifirstnodeinst; ni != NONODEINST; ni = ni->nextnodeinst) { np = ni->proto; if (np == NONODEPROTO) continue; if (np->primindex == 0) { cnp = contentsview(np); if (cnp != NONODEPROTO) np = cnp; } if (np->tech != NOTECHNOLOGY) usecount[np->tech->techindex]++; } /* count technologies of all arcs in the cell */ for(ai = cell->firstarcinst; ai != NOARCINST; ai = ai->nextarcinst) { ap = ai->proto; if (ap == NOARCPROTO) continue; usecount[ap->tech->techindex]++; } /* find a concensus */ best = 0; besttech = NOTECHNOLOGY; bestlayout = 0; bestlayouttech = NOTECHNOLOGY; for(tech = el_technologies; tech != NOTECHNOLOGY; tech = tech->nexttechnology) { /* always ignore the generic technology */ if (tech == gen_tech) continue; /* find the most popular of ALL technologies */ if (usecount[tech->techindex] > best) { best = usecount[tech->techindex]; besttech = tech; } /* find the most popular of the layout technologies */ if (tech == sch_tech || tech == art_tech) continue; if (usecount[tech->techindex] > bestlayout) { bestlayout = usecount[tech->techindex]; bestlayouttech = tech; } } /* presume generic */ if (cell->cellview == el_iconview) { /* in icons, if there is any artwork, use it */ if (usecount[art_tech->techindex] > 0) return(art_tech); /* in icons, if there is nothing, presume artwork */ if (besttech == NOTECHNOLOGY) return(art_tech); /* use artwork as a default */ rettech = art_tech; } else if (cell->cellview == el_schematicview) { /* in schematic, if there are any schematic components, use it */ if (usecount[sch_tech->techindex] > 0) return(sch_tech); /* in schematic, if there is nothing, presume schematic */ if (besttech == NOTECHNOLOGY) return(sch_tech); /* use schematic as a default */ rettech = sch_tech; } else { /* use the current layout technology as the default */ rettech = el_curlayouttech; } /* if a layout technology was voted the most, return it */ if (bestlayouttech != NOTECHNOLOGY) rettech = bestlayouttech; else { /* if any technology was voted the most, return it */ if (besttech != NOTECHNOLOGY) rettech = besttech; else { /* if this is an icon, presume the technology of its contents */ cv = contentsview(cell); if (cv != NONODEPROTO) { if (cv->tech == NOTECHNOLOGY) cv->tech = whattech(cv); rettech = cv->tech; } else { /* look at the contents of the sub-cells */ foundicons = FALSE; for(ni = cell->firstnodeinst; ni != NONODEINST; ni = ni->nextnodeinst) { np = ni->proto; if (np == NONODEPROTO) continue; if (np->primindex != 0) continue; /* ignore recursive references (showing icon in contents) */ if (isiconof(np, cell)) continue; /* see if the cell has an icon */ if (np->cellview == el_iconview) foundicons = TRUE; /* do not follow into another library */ if (np->lib != cell->lib) continue; onp = contentsview(np); if (onp != NONODEPROTO) np = onp; tech = whattech(np); if (tech == gen_tech) continue; rettech = tech; break; } if (ni == NONODEINST) { /* could not find instances that give information: were there icons? */ if (foundicons) rettech = sch_tech; } } } } if (allocatedusecount != 0) efree((CHAR *)allocatedusecount); /* give up and report the generic technology */ return(rettech); } /* * routine to return the parent node prototype of geometry object "g" */ NODEPROTO *geomparent(GEOM *g) { if (g == NOGEOM) return(NONODEPROTO); if (g->entryisnode) return(g->entryaddr.ni->parent); return(g->entryaddr.ai->parent); } /* * routine to recursively determine whether the nodeproto "parent" is * a descendant of nodeproto "child" (which would make the relationship * "child insideof parent" recursive). If the routine returns zero, * the parent is not a descendent of the child and all is well. If * true returned, recursion exists. */ BOOLEAN isachildof(NODEPROTO *parent, NODEPROTO *child) { REGISTER NODEPROTO *np; /* if the child is primitive there is no recursion */ if (child->primindex != 0) return(FALSE); /* special case: allow an icon to be inside of the contents for illustration */ if (isiconof(child, parent)) { if (child->cellview == el_iconview && parent->cellview != el_iconview) return(FALSE); } /* make sure the child is not an icon */ np = contentsview(child); if (np != NONODEPROTO) child = np; return(db_isachildof(parent, child)); } BOOLEAN db_isachildof(NODEPROTO *parent, NODEPROTO *child) { REGISTER NODEINST *ni; REGISTER NODEPROTO *np; /* if the child is primitive there is no recursion */ if (child->primindex != 0) return(FALSE); /* if they are the same, that is recursion */ if (child == parent) return(TRUE); /* look through every instance of the parent cell */ for(ni = parent->firstinst; ni != NONODEINST; ni = ni->nextinst) { /* if two instances in a row have same parent, skip this one */ if (ni->nextinst != NONODEINST && ni->nextinst->parent == ni->parent) continue; /* recurse to see if the grandparent belongs to the child */ if (db_isachildof(ni->parent, child)) return(TRUE); } /* if this has an icon, look at it's instances */ np = iconview(parent); if (np != NONODEPROTO) { for(ni = np->firstinst; ni != NONODEINST; ni = ni->nextinst) { /* if two instances in a row have same parent, skip this one */ if (ni->nextinst != NONODEINST && ni->nextinst->parent == ni->parent) continue; /* special case: allow an icon to be inside of the contents for illustration */ if (isiconof(ni->proto, parent)) { if (parent->cellview != el_iconview) continue; } /* recurse to see if the grandparent belongs to the child */ if (db_isachildof(ni->parent, child)) return(TRUE); } } return(FALSE); } /* * routine to tell the nodeproto that connects arcs of type "ap" */ NODEPROTO *getpinproto(ARCPROTO *ap) { REGISTER NODEPROTO *np; REGISTER PORTPROTO *pp; REGISTER INTBIG i; static INTBIG defaultpinkey = 0; REGISTER VARIABLE *var; if (ap == NOARCPROTO) return(NONODEPROTO); /* see if there is a default on this arc proto */ if (defaultpinkey == 0) defaultpinkey = makekey(x_("ARC_Default_Pin")); var = getvalkey((INTBIG)ap, VARCPROTO, VNODEPROTO, defaultpinkey); if (var != NOVARIABLE) { /* default found: test it for validity */ np = (NODEPROTO *)var->addr; pp = np->firstportproto; for(i=0; pp->connects[i] != NOARCPROTO; i++) if (pp->connects[i] == ap) return(np); } /* first look for nodeprotos that are actually declared as pins */ for(np = ap->tech->firstnodeproto; np != NONODEPROTO; np = np->nextnodeproto) { if (((np->userbits & NFUNCTION) >> NFUNCTIONSH) != NPPIN) continue; pp = np->firstportproto; for(i=0; pp->connects[i] != NOARCPROTO; i++) if (pp->connects[i] == ap) return(np); } /* now look for a nodeproto that can connect to this type of arc */ for(np = ap->tech->firstnodeproto; np != NONODEPROTO; np = np->nextnodeproto) { pp = np->firstportproto; if (pp == NOPORTPROTO) continue; if (pp->nextportproto != NOPORTPROTO) continue; for(i=0; pp->connects[i] != NOARCPROTO; i++) if (pp->connects[i] == ap) return(np); } ttyputerr(_("No node to connect %s arcs"), describearcproto(ap)); return(NONODEPROTO); } /* * Routine to return TRUE if node "ni" is a pin that is between * two arcs such that it can be deleted without affecting the geometry of the two arcs. */ BOOLEAN isinlinepin(NODEINST *ni, ARCINST ***thearcs) { static ARCINST *reconar[2]; INTBIG dx[2], dy[2]; REGISTER INTBIG i, j; REGISTER ARCINST *ai; REGISTER PORTARCINST *pi; REGISTER VARIABLE *var0, *var1; if ((ni->proto->userbits&NFUNCTION) >> NFUNCTIONSH != NPPIN) return(FALSE); /* see if the pin is connected to two arcs along the same slope */ j = 0; for(pi = ni->firstportarcinst; pi != NOPORTARCINST; pi = pi->nextportarcinst) { if (j >= 2) { j = 0; break; } reconar[j] = ai = pi->conarcinst; for(i=0; i<2; i++) if (ai->end[i].nodeinst != ni) { dx[j] = ai->end[i].xpos - ai->end[1-i].xpos; dy[j] = ai->end[i].ypos - ai->end[1-i].ypos; } j++; } if (j != 2) return(FALSE); /* must connect to two arcs of the same type and width */ if (reconar[0]->proto != reconar[1]->proto) return(FALSE); if (reconar[0]->width != reconar[1]->width) return(FALSE); /* arcs must be along the same angle, and not be curved */ if (dx[0] != 0 || dy[0] != 0 || dx[1] != 0 || dy[1] != 0) { if ((dx[0] != 0 || dy[0] != 0) && (dx[1] != 0 || dy[1] != 0) && figureangle(0, 0, dx[0], dy[0]) != figureangle(dx[1], dy[1], 0, 0)) return(FALSE); } if (getvalkey((INTBIG)reconar[0], VARCINST, VINTEGER, el_arc_radius_key) != NOVARIABLE) return(FALSE); if (getvalkey((INTBIG)reconar[1], VARCINST, VINTEGER, el_arc_radius_key) != NOVARIABLE) return(FALSE); /* the arcs must not have network names on them */ var0 = getvalkey((INTBIG)reconar[0], VARCINST, VSTRING, el_arc_name_key); var1 = getvalkey((INTBIG)reconar[1], VARCINST, VSTRING, el_arc_name_key); if (var0 != NOVARIABLE && var1 != NOVARIABLE) { if ((var0->type&VDISPLAY) != 0 && (var1->type&VDISPLAY) != 0) return(FALSE); } thearcs = (ARCINST ***)reconar; return(TRUE); } /* * Routine to return TRUE if node "ni" is an invisible pin that has text in a different * location. If so, (x,y) is set to the location of that text. */ BOOLEAN invisiblepinwithoffsettext(NODEINST *ni, INTBIG *x, INTBIG *y, BOOLEAN repair) { REGISTER INTBIG i, j, lambda; REGISTER PORTEXPINST *pe; REGISTER PORTPROTO *pp; REGISTER VARIABLE *var; static POLYGON *poly = NOPOLYGON; /* get polygon */ (void)needstaticpolygon(&poly, 4, us_tool->cluster); /* look for pins that are invisible and have text in different location */ if ((ni->proto->userbits&NFUNCTION) >> NFUNCTIONSH != NPPIN) return(FALSE); if (ni->firstportarcinst != NOPORTARCINST) return(FALSE); /* stop now if this isn't invisible */ if (ni->proto != gen_invispinprim) { j = nodepolys(ni, 0, NOWINDOWPART); if (j > 0) { shapenodepoly(ni, 0, poly); if (poly->style != TEXTCENT && poly->style != TEXTTOP && poly->style != TEXTBOT && poly->style != TEXTLEFT && poly->style != TEXTRIGHT && poly->style != TEXTTOPLEFT && poly->style != TEXTBOTLEFT && poly->style != TEXTTOPRIGHT && poly->style != TEXTBOTRIGHT && poly->style != TEXTBOX) return(FALSE); } } /* invisible: look for offset text */ for(pe = ni->firstportexpinst; pe != NOPORTEXPINST; pe = pe->nextportexpinst) { pp = pe->exportproto; if (TDGETXOFF(pp->textdescript) != 0 || TDGETYOFF(pp->textdescript) != 0) { lambda = lambdaofnode(ni); *x = (ni->lowx + ni->highx) / 2 + muldiv(TDGETXOFF(pp->textdescript), lambda, 4); *y = (ni->lowy + ni->highy) / 2 + muldiv(TDGETYOFF(pp->textdescript), lambda, 4); if (repair) { (void)startobjectchange((INTBIG)ni, VNODEINST); TDSETOFF(pp->textdescript, 0, 0); (void)setind((INTBIG)pp, VPORTPROTO, x_("textdescript"), 0, pp->textdescript[0]); (void)setind((INTBIG)pp, VPORTPROTO, x_("textdescript"), 1, pp->textdescript[1]); (void)endobjectchange((INTBIG)ni, VNODEINST); } return(TRUE); } } for(i=0; inumvar; i++) { var = &ni->firstvar[i]; if ((var->type&VDISPLAY) != 0 && (TDGETXOFF(var->textdescript) != 0 || TDGETYOFF(var->textdescript) != 0)) { lambda = lambdaofnode(ni); *x = (ni->lowx + ni->highx) / 2 + muldiv(TDGETXOFF(var->textdescript), lambda, 4); *y = (ni->lowy + ni->highy) / 2 + muldiv(TDGETYOFF(var->textdescript), lambda, 4); if (repair) { (void)startobjectchange((INTBIG)ni, VNODEINST); TDSETOFF(var->textdescript, 0, 0); modifydescript((INTBIG)ni, VNODEINST, var, var->textdescript); (void)endobjectchange((INTBIG)ni, VNODEINST); } return(TRUE); } } return(FALSE); } /* * routine to return the variable with "trace" information on nodeinst "ni". * Returns NOVARIABLE if there is no trace information */ VARIABLE *gettrace(NODEINST *ni) { REGISTER VARIABLE *var; /* now look for the variable */ var = getvalkey((INTBIG)ni, VNODEINST, VINTEGER|VISARRAY, el_trace_key); if (var == NOVARIABLE) return(NOVARIABLE); /* return the trace variable */ return(var); } /* * routine to return the "grab point" of cell "np" and place it in the * reference integers (grabx, graby). The default is the lower-left corner */ void grabpoint(NODEPROTO *np, INTBIG *grabx, INTBIG *graby) { REGISTER VARIABLE *var; *grabx = np->lowx; *graby = np->lowy; var = getvalkey((INTBIG)np, VNODEPROTO, VINTEGER|VISARRAY, el_prototype_center_key); if (var != NOVARIABLE) { *grabx = ((INTBIG *)var->addr)[0]; *graby = ((INTBIG *)var->addr)[1]; } } /* * routine to determine the offset of the lower-left corner of nodeinst "ni" * (which may be NONODEINST), nodeproto "np" given that it is rotated "rot" * and transposed "trn". The offset from the actual corner to the effective * corner is placed in "x" and "y". */ void corneroffset(NODEINST *ni, NODEPROTO *np, INTBIG rot, INTBIG trn, INTBIG *x, INTBIG *y, BOOLEAN centerbased) { INTBIG lx, ly, hx, hy, tx, ty, bx, by, pxs, pys; XARRAY mat; REGISTER INTBIG px, py, cx, cy; REGISTER VARIABLE *var; /* build transformation matrix */ makeangle(rot, trn, mat); /* see if there is a real grab-point */ var = getvalkey((INTBIG)np, VNODEPROTO, VINTEGER|VISARRAY, el_prototype_center_key); if (var != NOVARIABLE) { /* use grab point if specified */ cx = (np->lowx + np->highx) / 2; cy = (np->lowy + np->highy) / 2; px = np->lowx - cx; py = np->lowy - cy; xform(((INTBIG *)var->addr)[0]-cx, ((INTBIG *)var->addr)[1]-cy, &bx, &by, mat); } else { /* no grab point: find corner that is lowest and most to the left */ if (ni == NONODEINST) { nodeprotosizeoffset(np, &lx, &ly, &hx, &hy, NONODEPROTO); if (np->primindex != 0) { defaultnodesize(np, &pxs, &pys); cx = cy = 0; px = -pxs/2; py = -pys/2; lx = lx - pxs/2; hx = pxs/2 - hx; ly = ly - pys/2; hy = pys/2 - hy; } else { cx = (np->lowx + np->highx) / 2; cy = (np->lowy + np->highy) / 2; px = np->lowx - cx; py = np->lowy - cy; lx = lx + np->lowx - cx; hx = np->highx - hx - cx; ly = ly + np->lowy - cy; hy = np->highy - hy - cy; } } else { nodesizeoffset(ni, &lx, &ly, &hx, &hy); cx = (ni->lowx + ni->highx) / 2; cy = (ni->lowy + ni->highy) / 2; px = ni->lowx - cx; py = ni->lowy - cy; lx = lx + ni->lowx - cx; hx = ni->highx - hx - cx; ly = ly + ni->lowy - cy; hy = ni->highy - hy - cy; } xform(lx, ly, &tx, &ty, mat); bx = tx; by = ty; xform(lx, hy, &tx, &ty, mat); if ((tx-bx) + (ty-by) < 0) { bx = tx; by = ty; } xform(hx, hy, &tx, &ty, mat); if ((tx-bx) + (ty-by) < 0) { bx = tx; by = ty; } xform(hx, ly, &tx, &ty, mat); if ((tx-bx) + (ty-by) < 0) { bx = tx; by = ty; } if (centerbased && np->primindex != 0) bx = by = 0; } /* now compute offset between lower-left corner and this point */ *x = bx - px; *y = by - py; } #ifdef HAVE_QSORT /* * Routine to sort "entries" objects in "data" that are "structsize" bytes large. * The routine "numericorder" is called with two elements and returns their ordering. */ void esort(void *data, INTBIG entries, INTBIG structsize, int (*numericorder)(const void *e1, const void *e2)) { /* sort the data */ qsort(data, entries, structsize, numericorder); } #else /* for systems that don't have "qsort" */ void db_sortquick(int start, int endv, int len, int structsize, void *data, int (*numericorder)(const void *e1, const void *e2)); void esort(void *data, INTBIG entries, INTBIG structsize, int (*numericorder)(const void *e1, const void *e2)) { db_sortquick(0, entries-1, entries-1, structsize, data, numericorder); } /* Helper routine for "qsort" to order the list */ void db_sortquick(int start, int endv, int len, int structsize, void *data, int (*numericorder)(const void *e1, const void *e2)) { REGISTER int endv1, i, j, inorder, mright, mleft; REGISTER UCHAR1 *d1, *d2, *dr, swap, *chrdata; chrdata = (UCHAR1 *)data; if (endv-start > 9) { /* do a quicksort */ mright = endv+1; mleft = start; dr = &chrdata[start*structsize]; while (mleft < mright) { mleft = mleft+1; for(;;) { if (mleft >= len) break; d2 = &chrdata[mleft*structsize]; if (numericorder(d2, dr) >= 0) break; mleft++; } mright--; for(;;) { if (mright <= 0) break; d2 = &chrdata[mright*structsize]; if (numericorder(d2, dr) <= 0) break; mright--; } if (mleft < mright) { d1 = &chrdata[mleft*structsize]; d2 = &chrdata[mright*structsize]; for(j=0; jprotoname, c2->protoname)); } /* * Helper routine for "esort" that makes exports go in descending name order. */ int sort_exportnamedescending(const void *e1, const void *e2) { REGISTER PORTPROTO *c1, *c2; c1 = *((PORTPROTO **)e1); c2 = *((PORTPROTO **)e2); return(namesamenumeric(c2->protoname, c1->protoname)); } /* * routine to initialize the database */ void db_initdatabase(void) { REGISTER INTBIG x, y, i, j, k; INTBIG matc[2][2]; /* create interlocks */ if (ensurevalidmutex(&db_polygonmutex, TRUE)) return; if (ensurevalidmutex(&db_primenumbermutex, TRUE)) return; /* initialize change control */ db_initializechanges(); /* miscellaneous initialization */ db_windowpartfree = NOWINDOWPART; db_lasterror = DBNOERROR; el_curwindowpart = NOWINDOWPART; el_units = DISPUNITLAMBDA | INTUNITHNM; db_printerrors = TRUE; db_mrgdatainit(); /* setup disk file descriptors */ el_filetypetext = setupfiletype(x_(""), x_("*.*"), MACFSTAG('TEXT'), FALSE, x_("text"), _("Text")); /* prepare language translation */ db_inittranslation(); /* transformation initialization */ for(x=0; x<8; x++) for(y=0; y<8; y++) { for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0, matc[i][j]=0; k<2; k++) matc[i][j] += mult(db_matstyle[x][i][k], db_matstyle[y][k][j]); for(k=0; k<8; k++) { if (matc[0][0] != db_matstyle[k][0][0] || matc[0][1] != db_matstyle[k][0][1] || matc[1][0] != db_matstyle[k][1][0] || matc[1][1] != db_matstyle[k][1][1]) continue; db_matmult[x][y] = k; break; } } /* initialize variables */ el_numnames = 0; /* initialize globals that key to variables */ el_node_name_key = makekey(x_("NODE_name")); el_arc_name_key = makekey(x_("ARC_name")); el_arc_radius_key = makekey(x_("ARC_radius")); el_trace_key = makekey(x_("trace")); el_cell_message_key = makekey(x_("FACET_message")); el_schematic_page_size_key = makekey(x_("FACET_schematic_page_size")); el_transistor_width_key = makekey(x_("transistor_width")); el_prototype_center_key = makekey(x_("prototype_center")); el_essential_bounds_key = makekey(x_("FACET_essentialbounds")); el_node_size_default_key = makekey(x_("NODE_size_default")); el_arc_width_default_key = makekey(x_("ARC_width_default")); el_attrkey_area = makekey(x_("ATTR_area")); el_attrkey_length = makekey(x_("ATTR_length")); el_attrkey_width = makekey(x_("ATTR_width")); el_attrkey_M = makekey(x_("ATTR_M")); el_techstate_key = makekey(x_("TECH_state")); db_tech_node_width_offset_key = makekey(x_("TECH_node_width_offset")); db_tech_layer_function_key = makekey(x_("TECH_layer_function")); db_tech_layer_names_key = makekey(x_("TECH_layer_names")); db_tech_arc_width_offset_key = makekey(x_("TECH_arc_width_offset")); /* DRC keys need to be created early since they're used in "dbtech.c" */ dr_max_distanceskey = makekey(x_("DRC_max_distances")); dr_wide_limitkey = makekey(x_("DRC_wide_limit")); dr_min_widthkey = makekey(x_("DRC_min_width")); dr_min_width_rulekey = makekey(x_("DRC_min_width_rule")); dr_min_node_sizekey = makekey(x_("DRC_min_node_size")); dr_min_node_size_rulekey = makekey(x_("DRC_min_node_size_rule")); dr_connected_distanceskey = makekey(x_("DRC_min_connected_distances")); dr_connected_distances_rulekey = makekey(x_("DRC_min_connected_distances_rule")); dr_unconnected_distanceskey = makekey(x_("DRC_min_unconnected_distances")); dr_unconnected_distances_rulekey = makekey(x_("DRC_min_unconnected_distances_rule")); dr_connected_distancesWkey = makekey(x_("DRC_min_connected_distances_wide")); dr_connected_distancesW_rulekey = makekey(x_("DRC_min_connected_distances_wide_rule")); dr_unconnected_distancesWkey = makekey(x_("DRC_min_unconnected_distances_wide")); dr_unconnected_distancesW_rulekey = makekey(x_("DRC_min_unconnected_distances_wide_rule")); dr_connected_distancesMkey = makekey(x_("DRC_min_connected_distances_multi")); dr_connected_distancesM_rulekey = makekey(x_("DRC_min_connected_distances_multi_rule")); dr_unconnected_distancesMkey = makekey(x_("DRC_min_unconnected_distances_multi")); dr_unconnected_distancesM_rulekey = makekey(x_("DRC_min_unconnected_distances_multi_rule")); dr_edge_distanceskey = makekey(x_("DRC_min_edge_distances")); dr_edge_distances_rulekey = makekey(x_("DRC_min_edge_distances_rule")); #ifdef SURROUNDRULES dr_surround_layer_pairskey = makekey(x_("DRC_surround_layer_pairs")); dr_surround_distanceskey = makekey(x_("DRC_surround_distances")); dr_surround_rulekey = makekey(x_("DRC_surround_rule")); #endif /* create identity matrix */ transid(el_matid); /* initialize the views */ el_views = NOVIEW; el_unknownview = db_makepermanentview(x_("unknown"), x_(""), 0); el_simsnapview = db_makepermanentview(x_("simulation-snapshot"), x_("sim"), 0); el_netlistnetlispview = db_makepermanentview(x_("netlist-netlisp-format"), x_("net-netlisp"), TEXTVIEW); el_netlistrsimview = db_makepermanentview(x_("netlist-rsim-format"), x_("net-rsim"), TEXTVIEW); el_netlistsilosview = db_makepermanentview(x_("netlist-silos-format"), x_("net-silos"), TEXTVIEW); el_netlistquiscview = db_makepermanentview(x_("netlist-quisc-format"), x_("net-quisc"), TEXTVIEW); el_netlistalsview = db_makepermanentview(x_("netlist-als-format"), x_("net-als"), TEXTVIEW); el_netlistview = db_makepermanentview(x_("netlist"), x_("net"), TEXTVIEW); el_vhdlview = db_makepermanentview(x_("VHDL"), x_("vhdl"), TEXTVIEW); el_verilogview = db_makepermanentview(x_("Verilog"), x_("ver"), TEXTVIEW); el_skeletonview = db_makepermanentview(x_("skeleton"), x_("sk"), 0); el_compview = db_makepermanentview(x_("compensated"), x_("comp"), 0); el_docview = db_makepermanentview(x_("documentation"), x_("doc"), TEXTVIEW); el_iconview = db_makepermanentview(x_("icon"), x_("ic"), 0); el_schematicview = db_makepermanentview(x_("schematic"), x_("sch"), 0); el_layoutview = db_makepermanentview(x_("layout"), x_("lay"), 0); } /* * routine to build one of the permanent views by allocating it, giving it the full * name "fname" and abbreviation "sname", and including "state" in its "viewstate". */ VIEW *db_makepermanentview(CHAR *fname, CHAR *sname, INTBIG state) { REGISTER VIEW *v; /* create the view */ v = allocview(); /* name it and assign state */ (void)allocstring(&v->viewname, fname, db_cluster); (void)allocstring(&v->sviewname, sname, db_cluster); v->viewstate = state | PERMANENTVIEW; /* link into the global list */ v->nextview = el_views; el_views = v; /* return the view */ return(v); }