/* ** printed circuit board autorouter, Copyright (C) Randy Nevin 1989, 1990. ** ** you may give this software to anyone, make as many copies as you like, and ** post it on public computer bulletin boards and file servers. you may not ** sell it or charge any fee for distribution (except for media and postage), ** remove this comment or the copyright notice from the code, or claim that ** you wrote this code or anything derived from it. you may modify the code as ** much as you want (please document clearly with comments, and maintain the ** coding style), but programs which are derived from this one are subject to ** the conditions stated here. i am providing this code so that people can ** learn from it, so if you distribute it, please include source code, not ** just executables. contact me to report bugs or suggest enhancements; i do ** not guarantee support, but i will make an effort to help you, and i want to ** act as a central clearing house for future versions. you should contact me ** before undertaking a significant development effort, to avoid reinventing ** the wheel. if you come up with an enhancement you consider particularly ** useful, i would appreciate being informed so that it can be incorporated in ** future versions. my address is: Randy Nevin, 1731 211th PL NE, Redmond, ** WA 98053, USA. this code is available directly from the author; just send a ** 360k floppy and a self-addressed floppy mailer with sufficient postage. ** ** HISTORY ** (name date description) ** ---------------------------------------------------- ** randy nevin 2/1/89 initial version ** randy nevin 2/4/89 made retrace table driven, instead of ** doubly-nested switch statements. ** randy nevin 2/4/89 changed dir from int to char (cut ** storage for it in half). ** randy nevin 2/8/89 changed SetQueue and ReSetQueue to ** give priority to goal nodes. ** randy nevin 2/11/89 don't output incremental search ** results if stdout is redirected. ** randy nevin 2/11/89 released version 1.00 ** randy nevin 5/7/89 added /N switch (don't sort ** non-PRIORITY CONNECTs) ** randy nevin 12/27/89 removed code for compensating from ** edge of hole to center of hole; just ** approximate distance between centers ** of two holes (simplify) ** randy nevin 12/29/89 added code to keep traces from ** touching corner of a hole/via cell, ** and to keep from drilling a via where ** a corner of its cell touches a trace ** randy nevin 12/29/89 released version 1.10 */ #include #include #include #include #include #include "cell.h" #define VERSION 3.0 /* ** if you run out of memory while routing large boards, there are two things ** you can do: (1) go into your config.sys file and disable everything you ** don't need. getting rid of things like ansi.sys, ramdisks, disk caches, and ** other terminate and stay resident (tsr) programs can free a lot of memory. ** (2) link the router, inspect the .map file, relink with the /CPARMAXALLOC:n ** switch, where n is calculated to allow for a near heap of about 5k. read ** the linker documentation before you do this. for me, the route.map file ** says the program needs 81EFh bytes. to this i add 1400h (5k) for a near ** heap to get 95EFh bytes or 95Fh paragraphs, which is 2399 decimal. */ int JustBoard = 0; /* need all data structures, not just the board */ int SortConnects = 1; /* default is to sort non-PRIORITY CONNECTs */ int DoubleSided = 1; /* default is to use both sides of the board. Option added by stephen smith */ int NoDiag = 0; /* Diaganol traces allowed. Option added by stephen smith */ int RatsNest = 0; /* Rats Nest Only is Desired */ int Manual = 0; /* Print the manual? */ int TopSide = 0; /* default is to route the solder side */ long Percent = 98; /* quit trying at 98 percent of the board tested */ int Ntotal; /* total number of CONNECTs to make */ int PartsList = 0; /* Print a parts list to a file */ FILE *partsfile; char man[] = "\n\n" "the following types of input lines are legal (spaces and tabs can separate \n" "tokens, and case is not significant): \n" " \n" " 1) a blank line (ignored) \n" " 2) ';' followed by anything (ignored) \n" " use semicolon to insert comments. \n" " 3) DIMENSION (row,column) \n" " this defines the number of rows and columns on the board, and must be \n" " given before any of the lines below. note that the user sees the board \n" " coordinate space as being 1-based, but internally it is 0-based. \n" " 4) HOLE (row,column) \n" " this defines a hole location. \n" " 5) CONNECT thing AND thing \n" " this declares that two holes are to be electrically connected. a thing \n" " can be (row,column), or name1.name2, where name1 is the name of a \n" " CHIPAT-defined chip, and name2 is the name of one of its pins, or a \n" " number, giving the pin number of the named chip. you can use \"TO\" or \n" " \"=\" instead of \"AND\" if you want. \n" " 6) PRIORITY CONNECT thing AND thing \n" " same as above, except the order of connections will be preserved. the \n" " autorouter is free to reorder the non-PRIORITY CONNECTs, and in fact \n" " reorders them shortest first. if there are PRIORITY CONNECTs, they will \n" " all be routed before non-PRIORITY CONNECTs. \n" " 7) INCLUDE filename \n" " this causes the input to be temporarily taken from the given filename. \n" " when the given filename is completely processed (EOF encountered), \n" " control returns to the current file. INCLUDE statements may be nested \n" " (they may occur inside the given filename). complete and partial \n" " pathnames can be used (C:\TTL.INC, ..\TTL.INC, \TTL.INC, FOO\TTL.INC). \n" " 8) CHIP TYPE=type PINS=number HORIZONTAL=number VERTICAL=number \n" " [PACKAGE=package] \n" " this declares a chip type, which can be used to place chips on the \n" " board (see CHIPAT, below), but does not itself place anything on the \n" " board. TYPE gives the name that will be used in later CHIPAT \n" " statements. PINS declares the number of pins. HORIZONTAL gives the \n" " number of 50-mil units separating adjacent pins (along the long side of \n" " the chip). and VERTICAL gives the number of 50-mil units separating \n" " pins across from each other (across the skinny width of the chip). \n" " standard values for HORIZONTAL and VERTICAL are 2 and 6, respectively. \n" " all CHIP type names must be unique. The package string must be included \n" " if the parts listing switch is used. \n" " 9) number=name \n" " this declares a pin name for the chip that is currently being defined. \n" " this statement must follow a CHIP statement. pins not defined will have \n" " no name, but you can still refer to them by number. each pin on a chip \n" " can be named at most once. \n" "10) name=number \n" " same as above. \n" "11) CHIPAT (row,column) NAME=name TYPE=type ORIENTATION=orientation \n" " this defines an instance of a chip, and places the appropriate holes on \n" " the board. (row,column) is the location of pin 1. NAME defines the name \n" " to be used in following CONNECT statements. TYPE declares the \n" " CHIPAT-defined type of the chip. ORIENTATION can have the values \n" " NORMAL, UP, DOWN, and UPSIDEDOWN.All CUSTOM, INLINE and CHIP names \n" " must be unique. \n" " \n" " NORMAL UP DOWN UPSIDEDOWN \n" " \n" " 6 5 4 +---+ +---+ 3 2 1 \n" " +-*-*-*-+ 4 * * 3 1 * | * 6 +-*-*-*-+ \n" " | -> | 5 * ^ * 2 2 * v * 5 | <- | \n" " +-*-*-*-+ 6 * | * 1 3 * * 4 +-*-*-*-+ \n" " 1 2 3 +---+ +---+ 4 5 6 \n" " \n" " usually the highest-numbered pin (pin N) is Vcc (power) and the pin \n" " farthest from it (pin N/2) is GND (ground). \n" " \n" "The following statements were added by Stephen Smith. \n" " \n" "12) INLINE TYPE=type PINS=number HORIZONTAL=number [PACKAGE=package] \n" " this declares an inline type, which can be used to place chips on the \n" " board (see CHIPAT, above), but does not itself place anything on the \n" " board. TYPE gives the name that will be used in later INLINAT \n" " statements. PINS declares the number of pins. HORIZONTAL gives the \n" " number of 50-mil units separating adjacent pins. Standard value \n" " for HORIZONTAL is 2. All INLINE type names must be unique. The package\n" " string must be included if the parts listing switch is used. \n" "13) INLINEAT (row,column) NAME=name TYPE=type ORIENTATION=orientation \n" " this defines an instance of an inline, and places the appropriate \n" " holes on the board. (row,column) is the location of pin 1. NAME defines \n" " the name to be used in following CONNECT statements. TYPE declares the \n" " INLINEAT-defined type of the chip. ORIENTATION can have the values \n" " NORMAL, UP, DOWN, and UPSIDEDOWN. All CUSTOM, INLINE and CHIP \n" " names must be unique. \n" " \n" " NORMAL UP DOWN UPSIDEDOWN \n" " \n" " 1 2 3 + + 3 2 1 \n" " +-*-*-*-+ * 3 1 * +-*-*-*-+ \n" " * 2 2 * \n" " * 1 3 * \n" " + + \n" " \n" "14) CUSTOM TYPE=type PACKAGE=package \n" " In this case package is predefined in the EXE file and can be \n" " one of the following strings: \n" " PLCC20, PLCC28, PLCC32, PLCC44, PLCC52, PLCC68, PLCC84, \n" " TO5, TO18, TRIMMER_W, TRIMMERP, and TRIMMERY. \n" " These strings and the associated arrays that go with them are defined \n" " in the file plcc.c. The numbers in the arrays are offsets from pin \n" " number 1 on a fifty mil grid. \n" " \n" "15) CUSTOMAT (row,column) NAME=name TYPE=type ORIENTATION=orientation \n" " this defines an instance of an inline, and places the appropriate \n" " holes on the board. (row,column) is the location of pin 1. NAME defines \n" " the name to be used in following CONNECT statements. TYPE declares the \n" " CUSTOMAT-defined type of the chip. ORIENTATION can have the values \n" " NORMAL, UP, DOWN, and UPSIDEDOWN. All CUSTOM, INLINE and CHIP \n" " names must be unique. The directions shown below are for the \n" " PLCC chip carriers. \n" " \n" " NORMAL UP DOWN UPSIDEDOWN \n" " \n" " ***** ***** **1** ***** \n" " ******* ******* ******* ******* \n" " ** ** ** ** ** ** ** ** \n" " 1* ** ** ** ** ** ** *1 \n" " ** ** ** ** ** ** ** ** \n" " ******* ******* ******* ******* \n" " ***** **1** ***** ***** \n" " \n" " \n" " TOxx packages: \n" " \n" " E C \n" " B B B E C \n" " C E C E B \n" " \n" " \n" " TRIMMERx packages: \n" " \n" " 3 1 \n" " 2 2 \n" " 1 3 2 3 1 \n" " 2 1 3 \n" " \n" " Note: The coordinate system is left handed. ( Positive X values \n" " are vertical and positive Y values are to the right. Cell (1,1) \n" " denotes the lower left hand corner of the board. ) \n" " \n" " \n" " X \n" " ^ \n" " | \n" " | \n" " +----> Y \n\n" ; extern int Initialize( char *, int ); extern void Solve( FILE * ); extern void Report( FILE * ); void main( int, char *[] ); void main ( argc, argv ) /* input board, route traces, output routed board */ int argc; char **argv; { char *self, *p; FILE *fp, *fp2; long start, stop, min, hours; start = time( NULL ); self = (argv++)[0]; /* get rid of initial part of path */ if ((p = strrchr( self, '\\' )) || (p = strrchr( self, ':' ))) self = ++p; /* get rid of extension */ if ((p = strrchr( self, '.' )) && !stricmp( p, ".EXE" )) *p = 0; printf( "%s.EXE, Copyright (C) Randy Nevin, 1989, 1990. Version 1.10\n" "Modifications by Stephen Smith - Version %.2f\n\n", self, VERSION ); printf( "See source code for rights granted.\n\n" ); while( argc-- > 1 && ( **argv == '-' || **argv == '/') ) { ++*argv; while( **argv != '\0' ) { switch( **argv ) { case 'n' : case 'N' : ++*argv; SortConnects = 0; break; case 's' : case 'S' : ++*argv; DoubleSided = 0; break; case 't' : case 'T' : ++*argv; TopSide = 1; break; case 'd' : case 'D' : ++*argv; NoDiag = 1; break; case 'b' : case 'B' : ++*argv; TopSide = 0; break; case 'm' : case 'M' : ++*argv; Manual = 1; break; case '0' : ++*argv; RatsNest = 1; break; case 'p' : case 'P' : if ( sscanf(++(*argv),"%d",&Percent ) == 0 ) { printf("\nOption \"P\" needs a number!"); exit(1); } while ( **argv != NULL ) ++*argv; break; case 'l' : case 'L' : ++*argv; if ( (partsfile = fopen(*argv,"wt")) == NULL ) { fprintf(stderr, "Couldn\'t open parts list " "file: %s\n Program aborted\n", *argv ); exit(1); } while ( **argv != NULL ) ++*argv; PartsList = 1; break; default : fprintf(stderr," Unrecongized command-line switch\n" " The valid switches are: /N, /S, /T, /B /0" " /D /M /P /L" "\n Program aborted\n" ); exit( 1 ); } } argv++; } if (Manual){ printf( "%s", man ); } if ((argc < 2) || Manual) { /* need infile and outfile */ fprintf( ( (Manual) ? stdout: stderr), "usage: %s [options] infile " "outfile [no_connect_file]\n", self ); fprintf( ( (Manual) ? stdout: stderr), " /N = no sorting of non-PRIORITY CONNECTs\n" " /M = Print to stdout the manual of valid input statements\n" " /0 = Output a ratsnest ony. \n" " /Pxxx = Percentage at which to quit trying to route \n" " the trace. \n" " /S = single sided printed circuit boards \n" " /D = Diagnal Traces not allowed\n" " /Lfile = Print out a parts listing to \"file\"\n" " /T = Route the top side of the board. Only valid if\n " " S is used. \n" " /B = Route the bottom side of the board. Only valid if\n " " S is used. Default Option. \n" ); exit( -1 ); } fp2 = NULL; if (!(fp = fopen( argv[1], "wb" ))) { fprintf( stderr, "can't open %s\n", argv[1] ); exit( -1 ); } if ( argc > 2 ){ if (!(fp2 = fopen( argv[2], "wt" ))) { fprintf( stderr, "can't open %s\n", argv[2] ); exit( -1 ); } } Ntotal = Initialize( argv[0], 1 ); /* echo memory used */ Solve( fp2 ); Report( fp ); stop = time( NULL ) - start; min = stop / 60; stop -= min * 60; printf( "time = %ld min%s, %ld second%s\n", min, (min == 1) ? "" : "s", stop, (stop == 1) ? "" : "s" ); if (argc > 2 ) fclose( fp2 ); if ( PartsList ) fclose( partsfile ); exit( 0 ); }