home *** CD-ROM | disk | FTP | other *** search
/ HAM Radio 1 / HamRadio.cdr / tech / pcbsrcs2 / route4.c < prev    next >
C/C++ Source or Header  |  1991-02-10  |  22KB  |  400 lines
  1. /*
  2. ** printed circuit board autorouter, Copyright (C) Randy Nevin 1989, 1990.
  3. **
  4. ** you may give this software to anyone, make as many copies as you like, and
  5. ** post it on public computer bulletin boards and file servers. you may not
  6. ** sell it or charge any fee for distribution (except for media and postage),
  7. ** remove this comment or the copyright notice from the code, or claim that
  8. ** you wrote this code or anything derived from it. you may modify the code as
  9. ** much as you want (please document clearly with comments, and maintain the
  10. ** coding style), but programs which are derived from this one are subject to
  11. ** the conditions stated here. i am providing this code so that people can
  12. ** learn from it, so if you distribute it, please include source code, not
  13. ** just executables. contact me to report bugs or suggest enhancements; i do
  14. ** not guarantee support, but i will make an effort to help you, and i want to
  15. ** act as a central clearing house for future versions. you should contact me
  16. ** before undertaking a significant development effort, to avoid reinventing
  17. ** the wheel. if you come up with an enhancement you consider particularly
  18. ** useful, i would appreciate being informed so that it can be incorporated in
  19. ** future versions. my address is: Randy Nevin, 1731 211th PL NE, Redmond,
  20. ** WA 98053, USA. this code is available directly from the author; just send a
  21. ** 360k floppy and a self-addressed floppy mailer with sufficient postage.
  22. **
  23. ** HISTORY
  24. ** (name        date        description)
  25. ** ----------------------------------------------------
  26. ** randy nevin        2/1/89        initial version
  27. ** randy nevin        2/4/89        made retrace table driven, instead of
  28. **                    doubly-nested switch statements.
  29. ** randy nevin        2/4/89        changed dir from int to char (cut
  30. **                    storage for it in half).
  31. ** randy nevin        2/8/89        changed SetQueue and ReSetQueue to
  32. **                    give priority to goal nodes.
  33. ** randy nevin        2/11/89        don't output incremental search
  34. **                    results if stdout is redirected.
  35. ** randy nevin        2/11/89        released version 1.00
  36. ** randy nevin        5/7/89        added /N switch (don't sort
  37. **                    non-PRIORITY CONNECTs)
  38. ** randy nevin        12/27/89    removed code for compensating from
  39. **                    edge of hole to center of hole; just
  40. **                    approximate distance between centers
  41. **                    of two holes (simplify)
  42. ** randy nevin        12/29/89    added code to keep traces from
  43. **                    touching corner of a hole/via cell,
  44. **                    and to keep from drilling a via where
  45. **                    a corner of its cell touches a trace
  46. ** randy nevin        12/29/89    released version 1.10
  47. */
  48.  
  49. #include <stdio.h>
  50. #include <stdlib.h>
  51. #include <io.h>
  52. #include <time.h>
  53. #include <string.h>
  54. #include "cell.h"
  55.  
  56. #define VERSION 3.0
  57.  
  58. /*
  59. ** if you run out of memory while routing large boards, there are two things
  60. ** you can do: (1) go into your config.sys file and disable everything you
  61. ** don't need. getting rid of things like ansi.sys, ramdisks, disk caches, and
  62. ** other terminate and stay resident (tsr) programs can free a lot of memory.
  63. ** (2) link the router, inspect the .map file, relink with the /CPARMAXALLOC:n
  64. ** switch, where n is calculated to allow for a near heap of about 5k. read
  65. ** the linker documentation before you do this. for me, the route.map file
  66. ** says the program needs 81EFh bytes. to this i add 1400h (5k) for a near
  67. ** heap to get 95EFh bytes or 95Fh paragraphs, which is 2399 decimal.
  68. */
  69.  
  70. int JustBoard = 0; /* need all data structures, not just the board */
  71. int SortConnects = 1; /* default is to sort non-PRIORITY CONNECTs */
  72. int DoubleSided = 1; /* default is to use both sides of the board.  Option
  73.                         added by stephen smith */
  74. int NoDiag = 0;      /* Diaganol traces allowed.  Option
  75.                         added by stephen smith */
  76. int  RatsNest = 0;   /* Rats Nest Only is Desired */          
  77. int  Manual = 0;     /* Print the manual? */
  78. int  TopSide = 0;    /* default is to route the solder side */
  79. long Percent = 98;   /* quit trying at 98 percent of the board tested */
  80. int  Ntotal;         /* total number of CONNECTs to make */
  81. int  PartsList = 0;  /* Print a parts list to a file */
  82. FILE *partsfile;
  83.  
  84. char man[] =
  85. "\n\n"
  86. "the following types of input lines are legal (spaces and tabs can separate  \n"
  87. "tokens, and case is not significant):                                       \n"
  88. "                                                                            \n"
  89. " 1) a blank line (ignored)                                                  \n"
  90. " 2) ';' followed by anything (ignored)                                      \n"
  91. "    use semicolon to insert comments.                                       \n"
  92. " 3) DIMENSION (row,column)                                                  \n"
  93. "    this defines the number of rows and columns on the board, and must be   \n"
  94. "    given before any of the lines below. note that the user sees the board  \n"
  95. "    coordinate space as being 1-based, but internally it is 0-based.        \n"
  96. " 4) HOLE (row,column)                                                       \n"
  97. "    this defines a hole location.                                           \n"
  98. " 5) CONNECT thing AND thing                                                 \n"
  99. "    this declares that two holes are to be electrically connected. a thing  \n"
  100. "    can be (row,column), or name1.name2, where name1 is the name of a       \n"
  101. "    CHIPAT-defined chip, and name2 is the name of one of its pins, or a     \n"
  102. "    number, giving the pin number of the named chip. you can use \"TO\" or  \n"
  103. "    \"=\" instead of \"AND\" if you want.                                   \n"
  104. " 6) PRIORITY CONNECT thing AND thing                                        \n"
  105. "    same as above, except the order of connections will be preserved. the   \n"
  106. "    autorouter is free to reorder the non-PRIORITY CONNECTs, and in fact    \n"
  107. "    reorders them shortest first. if there are PRIORITY CONNECTs, they will \n"
  108. "    all be routed before non-PRIORITY CONNECTs.                             \n"
  109. " 7) INCLUDE filename                                                        \n"
  110. "    this causes the input to be temporarily taken from the given filename.  \n"
  111. "    when the given filename is completely processed (EOF encountered),      \n"
  112. "    control returns to the current file. INCLUDE statements may be nested   \n"
  113. "    (they may occur inside the given filename). complete and partial        \n"
  114. "    pathnames can be used (C:\TTL.INC, ..\TTL.INC, \TTL.INC, FOO\TTL.INC).  \n"
  115. " 8) CHIP TYPE=type PINS=number HORIZONTAL=number VERTICAL=number            \n"
  116. "      [PACKAGE=package]                                                     \n"
  117. "    this declares a chip type, which can be used to place chips on the      \n"
  118. "    board (see CHIPAT, below), but does not itself place anything on the    \n"
  119. "    board. TYPE gives the name that will be used in later CHIPAT            \n"
  120. "    statements. PINS declares the number of pins. HORIZONTAL gives the      \n"
  121. "    number of 50-mil units separating adjacent pins (along the long side of \n"
  122. "    the chip). and VERTICAL gives the number of 50-mil units separating     \n"
  123. "    pins across from each other (across the skinny width of the chip).      \n"
  124. "    standard values for HORIZONTAL and VERTICAL are 2 and 6, respectively.  \n"
  125. "    all CHIP type names must be unique. The package string must be included \n"
  126. "    if the parts listing switch is used.                                    \n"
  127. " 9) number=name                                                             \n"
  128. "    this declares a pin name for the chip that is currently being defined.  \n"
  129. "    this statement must follow a CHIP statement. pins not defined will have \n"
  130. "    no name, but you can still refer to them by number. each pin on a chip  \n"
  131. "    can be named at most once.                                              \n"
  132. "10) name=number                                                             \n"
  133. "    same as above.                                                          \n"
  134. "11) CHIPAT (row,column) NAME=name TYPE=type ORIENTATION=orientation         \n"
  135. "    this defines an instance of a chip, and places the appropriate holes on \n"
  136. "    the board. (row,column) is the location of pin 1. NAME defines the name \n"
  137. "    to be used in following CONNECT statements. TYPE declares the           \n"
  138. "    CHIPAT-defined type of the chip. ORIENTATION can have the values        \n"
  139. "    NORMAL, UP, DOWN, and UPSIDEDOWN.All CUSTOM, INLINE and CHIP names      \n"
  140. "    must be unique.                                                         \n"
  141. "                                                                            \n"
  142. "     NORMAL           UP           DOWN        UPSIDEDOWN                   \n"
  143. "                                                                            \n"
  144. "      6 5 4          +---+         +---+          3 2 1                     \n"
  145. "    +-*-*-*-+      4 *   * 3     1 * | * 6      +-*-*-*-+                   \n"
  146. "    |  ->   |      5 * ^ * 2     2 * v * 5      |   <-  |                   \n"
  147. "    +-*-*-*-+      6 * | * 1     3 *   * 4      +-*-*-*-+                   \n"
  148. "      1 2 3          +---+         +---+          4 5 6                     \n"
  149. "                                                                            \n"
  150. "    usually the highest-numbered pin (pin N) is Vcc (power) and the pin     \n"
  151. "    farthest from it (pin N/2) is GND (ground).                             \n"
  152. "                                                                            \n"
  153. "The following statements were added by Stephen Smith.                       \n"
  154. "                                                                            \n"
  155. "12) INLINE TYPE=type PINS=number HORIZONTAL=number [PACKAGE=package]        \n"
  156. "    this declares an inline type, which can be used to place chips on the   \n"
  157. "    board (see CHIPAT, above), but does not itself place anything on the    \n"
  158. "    board. TYPE gives the name that will be used in later INLINAT           \n"
  159. "    statements. PINS declares the number of pins. HORIZONTAL gives the      \n"
  160. "    number of 50-mil units separating adjacent pins.  Standard value        \n"
  161. "    for HORIZONTAL is 2.  All INLINE type names must be unique.  The package\n"
  162. "    string must be included if the parts listing switch is used.            \n"
  163. "13) INLINEAT (row,column) NAME=name TYPE=type ORIENTATION=orientation       \n"
  164. "    this defines an instance of an inline, and places the appropriate       \n"
  165. "    holes on the board. (row,column) is the location of pin 1. NAME defines \n"
  166. "    the name to be used in following CONNECT statements. TYPE declares the  \n"
  167. "    INLINEAT-defined type of the chip. ORIENTATION can have the values      \n"
  168. "    NORMAL, UP, DOWN, and UPSIDEDOWN.  All CUSTOM, INLINE and CHIP          \n"
  169. "    names must be unique.                                                   \n"
  170. "                                                                            \n"
  171. "     NORMAL           UP           DOWN        UPSIDEDOWN                   \n"
  172. "                                                                            \n"
  173. "     1 2 3            +              +          3 2 1                       \n"
  174. "   +-*-*-*-+          * 3          1 *        +-*-*-*-+                     \n"
  175. "                      * 2          2 *                                      \n"
  176. "                      * 1          3 *                                      \n"
  177. "                      +              +                                      \n"
  178. "                                                                            \n"
  179. "14) CUSTOM TYPE=type  PACKAGE=package                                       \n"
  180. "    In this case package is predefined in the EXE file and can be           \n"
  181. "    one of the following strings:                                           \n"
  182. "        PLCC20, PLCC28, PLCC32, PLCC44, PLCC52, PLCC68, PLCC84,             \n"
  183. "        TO5, TO18, TRIMMER_W, TRIMMERP, and TRIMMERY.                       \n"
  184. "    These strings and the associated arrays that go with them are defined   \n"
  185. "    in the file plcc.c.  The numbers in the arrays are offsets from pin     \n"
  186. "    number 1 on a fifty mil grid.                                           \n"
  187. "                                                                            \n"
  188. "15) CUSTOMAT (row,column) NAME=name TYPE=type ORIENTATION=orientation       \n"
  189. "    this defines an instance of an inline, and places the appropriate       \n"
  190. "    holes on the board. (row,column) is the location of pin 1. NAME defines \n"
  191. "    the name to be used in following CONNECT statements. TYPE declares the  \n"
  192. "    CUSTOMAT-defined type of the chip. ORIENTATION can have the values      \n"
  193. "    NORMAL, UP, DOWN, and UPSIDEDOWN.  All CUSTOM, INLINE and CHIP          \n"
  194. "    names must be unique.  The directions shown below are for the           \n"
  195. "    PLCC chip carriers.                                                     \n"
  196. "                                                                            \n"
  197. "     NORMAL           UP           DOWN        UPSIDEDOWN                   \n"
  198. "                                                                            \n"
  199. "      *****          *****         **1**          *****                     \n"
  200. "     *******        *******       *******        *******                    \n"
  201. "     **   **        **   **       **   **        **   **                    \n"
  202. "     1*   **        **   **       **   **        **   *1                    \n"
  203. "     **   **        **   **       **   **        **   **                    \n"
  204. "     *******        *******       *******        *******                    \n"
  205. "      *****          **1**         *****          *****                     \n"
  206. "                                                                            \n"
  207. "                                                                            \n"
  208. "     TOxx packages:                                                         \n"
  209. "                                                                            \n"
  210. "                      E              C                                      \n"
  211. "       B            B                  B          E   C                     \n"
  212. "     C   E            C              E              B                       \n"
  213. "                                                                            \n"
  214. "                                                                            \n"
  215. "     TRIMMERx packages:                                                     \n"
  216. "                                                                            \n"
  217. "                      3              1                                      \n"
  218. "                       2                           2                        \n"
  219. "     1    3                         2             3    1                    \n"
  220. "         2            1              3                                      \n"
  221. "                                                                            \n"
  222. "     Note:  The coordinate system is left handed.  ( Positive X values      \n"
  223. "     are vertical and positive Y values are to the right.  Cell (1,1)       \n"
  224. "     denotes the lower left hand corner of the board. )                     \n"
  225. "                                                                            \n"
  226. "                                                                            \n"
  227. "     X                                                                      \n"
  228. "     ^                                                                      \n"
  229. "     |                                                                      \n"
  230. "     |                                                                      \n"
  231. "     +----> Y                                                             \n\n"
  232. ;
  233.  
  234.  
  235. extern int Initialize( char *, int );
  236. extern void Solve( FILE * );
  237. extern void Report( FILE * );
  238.  
  239. void main( int, char *[] );
  240.  
  241. void main ( argc, argv ) /* input board, route traces, output routed board */
  242.     int argc;
  243.     char **argv;
  244.     {
  245.     char *self, *p;
  246.     FILE *fp, *fp2;
  247.     long start, stop, min, hours;
  248.  
  249.     start = time( NULL );
  250.  
  251.     self = (argv++)[0];
  252.     /* get rid of initial part of path */
  253.     if ((p = strrchr( self, '\\' )) || (p = strrchr( self, ':' )))
  254.         self = ++p;
  255.     /* get rid of extension */
  256.     if ((p = strrchr( self, '.' )) && !stricmp( p, ".EXE" ))
  257.         *p = 0;
  258.  
  259.     printf( "%s.EXE,  Copyright (C) Randy Nevin, 1989, 1990. Version 1.10\n"
  260.             "Modifications by Stephen Smith - Version %.2f\n\n",
  261.             self, VERSION );
  262.     printf( "See source code for rights granted.\n\n" );
  263.  
  264.    while( argc-- > 1 && ( **argv == '-' || **argv == '/') )
  265.       {
  266.          ++*argv;
  267.          while( **argv != '\0' )
  268.          {
  269.             switch( **argv )
  270.             {
  271.                 case 'n' :
  272.                 case 'N' :
  273.                          ++*argv;
  274.                          SortConnects = 0;
  275.                          break;
  276.                 case 's' :
  277.                 case 'S' :
  278.                          ++*argv;
  279.                          DoubleSided = 0;
  280.                          break;
  281.                 case 't' :
  282.                 case 'T' :
  283.                          ++*argv;
  284.                          TopSide = 1;
  285.                          break;
  286.                 case 'd' :
  287.                 case 'D' :
  288.                          ++*argv;
  289.                          NoDiag = 1;
  290.                          break;
  291.                 case 'b' :
  292.                 case 'B' :
  293.                          ++*argv;
  294.                          TopSide = 0;
  295.                          break;
  296.                 case 'm' :
  297.                 case 'M' :
  298.                          ++*argv;
  299.                          Manual = 1;
  300.                          break;
  301.                 case '0' :
  302.                          ++*argv;
  303.                          RatsNest = 1;
  304.                          break;
  305.                 case 'p' :
  306.                 case 'P' :
  307.                          if ( sscanf(++(*argv),"%d",&Percent ) == 0 )
  308.                             {
  309.                                printf("\nOption \"P\" needs a number!");
  310.                                exit(1);
  311.                             }
  312.                          while ( **argv != NULL ) ++*argv;
  313.                          break;
  314.                 case 'l' :
  315.                 case 'L' :
  316.                          ++*argv;
  317.                          if ( (partsfile = fopen(*argv,"wt")) == NULL )
  318.                             {
  319.                                fprintf(stderr, "Couldn\'t open parts list "
  320.                                       "file:  %s\n Program aborted\n", *argv );
  321.                                exit(1);
  322.                             }
  323.                          while ( **argv != NULL ) ++*argv;
  324.                          PartsList = 1;
  325.                          break;
  326.                 default :
  327.                         fprintf(stderr," Unrecongized command-line switch\n"
  328.                                 " The valid switches are:  /N, /S, /T, /B /0"
  329.                                 " /D /M /P /L"
  330.                                 "\n Program aborted\n" );
  331.                         exit( 1 );
  332.             }
  333.          }
  334.      argv++;
  335.       }
  336.  
  337.     if (Manual){
  338.         printf( "%s", man );
  339.         }
  340.  
  341.     if ((argc < 2) || Manual) { /* need infile and outfile */
  342.         fprintf( ( (Manual) ? stdout: stderr), "usage: %s [options] infile "
  343.                      "outfile [no_connect_file]\n", self );
  344.         fprintf( ( (Manual) ? stdout: stderr),
  345.            " /N      = no sorting of non-PRIORITY CONNECTs\n"
  346.            " /M      = Print to stdout the manual of valid input statements\n"
  347.            " /0      = Output a ratsnest ony. \n"
  348.            " /Pxxx   = Percentage at which to quit trying to route \n"
  349.            "           the trace. \n"
  350.            " /S      = single sided printed circuit boards \n"
  351.            " /D      = Diagnal Traces not allowed\n"
  352.            " /Lfile  = Print out a parts listing to \"file\"\n"
  353.            " /T      = Route the top side of the board. Only valid if\n "
  354.            "           S is used. \n"
  355.            " /B      = Route the bottom side of the board. Only valid if\n "
  356.            "           S is used.  Default Option. \n"
  357.            );
  358.         exit( -1 );
  359.         }
  360.  
  361.     fp2 = NULL;
  362.     if (!(fp = fopen( argv[1], "wb" ))) {
  363.         fprintf( stderr, "can't open %s\n", argv[1] );
  364.         exit( -1 );
  365.         }
  366.     if ( argc > 2 ){
  367.         if (!(fp2 = fopen( argv[2], "wt" ))) {
  368.             fprintf( stderr, "can't open %s\n", argv[2] );
  369.             exit( -1 );
  370.             }
  371.         }
  372.     Ntotal = Initialize( argv[0], 1 ); /* echo memory used */
  373.     Solve( fp2 );
  374.     Report( fp );
  375.     stop = time( NULL ) - start;
  376.     min = stop / 60; stop -= min * 60;
  377.     printf( "time = %ld min%s, %ld second%s\n", min, (min == 1) ? "" : "s",
  378.              stop, (stop == 1) ? "" : "s" );
  379.     if (argc > 2 ) fclose( fp2 );
  380.     if ( PartsList ) fclose( partsfile );
  381.     exit( 0 );
  382.     }
  383.  
  384.  
  385.  
  386.  
  387.  
  388.  
  389.  
  390.  
  391.  
  392.  
  393.  
  394.  
  395.  
  396.  
  397.  
  398.  
  399.  
  400.