home *** CD-ROM | disk | FTP | other *** search
/ HAM Radio 1 / HamRadio.cdr / tech / pcbsrcs2 / route3.c < prev    next >
C/C++ Source or Header  |  1991-02-07  |  13KB  |  301 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. /*
  57. ** if you run out of memory while routing large boards, there are two things
  58. ** you can do: (1) go into your config.sys file and disable everything you
  59. ** don't need. getting rid of things like ansi.sys, ramdisks, disk caches, and
  60. ** other terminate and stay resident (tsr) programs can free a lot of memory.
  61. ** (2) link the router, inspect the .map file, relink with the /CPARMAXALLOC:n
  62. ** switch, where n is calculated to allow for a near heap of about 5k. read
  63. ** the linker documentation before you do this. for me, the route.map file
  64. ** says the program needs 81EFh bytes. to this i add 1400h (5k) for a near
  65. ** heap to get 95EFh bytes or 95Fh paragraphs, which is 2399 decimal.
  66. */
  67.  
  68. int JustBoard = 0; /* need all data structures, not just the board */
  69. int SortConnects = 1; /* default is to sort non-PRIORITY CONNECTs */
  70. int DoubleSided = 1; /* default is to use both sides of the board.  Option
  71.                         added by stephen smith */
  72. int NoDiag = 0;      /* Diaganol traces allowed.  Option
  73.                         added by stephen smith */
  74. int  RatsNest = 0;   /* Rats Nest Only is Desired */          
  75. int  Manual = 0;     /* Print the manual? */
  76. int  TopSide = 0;    /* default is to route the solder side */
  77. long Percent = 98;   /* quit trying at 98 percent of the board tested */
  78. int  Ntotal;         /* total number of CONNECTs to make */
  79.  
  80. char man[] = 
  81. "the following types of input lines are legal (spaces and tabs can separate\n"
  82. "tokens, and case is not significant):\n"
  83. "  1) a blank line (ignored)\n"
  84. " 2) ';' followed by anything (ignored)\n"
  85. "    use semicolon to insert comments.\n"
  86. " 3) DIMENSION (row,column)\n"
  87. "    this defines the number of rows and columns on the board, and must be\n"
  88. "    given before any of the lines below. note that the user sees the board\n"
  89. "    coordinate space as being 1-based, but internally it is 0-based.\n"
  90. " 4) HOLE (row,column)\n"
  91. "    this defines a hole location.\n"
  92. " 5) CONNECT thing AND thing\n"
  93. "    this declares that two holes are to be electrically connected. a thing\n"
  94. "    can be (row,column), or name1.name2, where name1 is the name of a\n"
  95. "    CHIPAT-defined chip, and name2 is the name of one of its pins, or a\n"
  96. "    number, giving the pin number of the named chip. you can use \"TO\" or\n"
  97. "    \"=\" instead of \"AND\" if you want.\n"
  98. " 6) PRIORITY CONNECT thing AND thing\n"
  99. "    same as above, except the order of connections will be preserved. the\n"
  100. "    autorouter is free to reorder the non-PRIORITY CONNECTs, and in fact\n"
  101. "    reorders them shortest first. if there are PRIORITY CONNECTs, they will\n"
  102. "    all be routed before non-PRIORITY CONNECTs.\n"
  103. " 7) INCLUDE filename\n"
  104. "    this causes the input to be temporarily taken from the given filename.\n"
  105. "    when the given filename is completely processed (EOF encountered),\n"
  106. "    control returns to the current file. INCLUDE statements may be nested\n"
  107. "    (they may occur inside the given filename). complete and partial\n"
  108. "    pathnames can be used (C:\TTL.INC, ..\TTL.INC, \TTL.INC, FOO\TTL.INC).\n"
  109. " 8) CHIP TYPE=type PINS=number HORIZONTAL=number VERTICAL=number\n"
  110. "    this declares a chip type, which can be used to place chips on the\n"
  111. "    board (see CHIPAT, below), but does not itself place anything on the\n"
  112. "    board. TYPE gives the name that will be used in later CHIPAT\n"
  113. "    statements. PINS declares the number of pins. HORIZONTAL gives the\n"
  114. "    number of 50-mil units separating adjacent pins (along the long side of\n"
  115. "    the chip). and VERTICAL gives the number of 50-mil units separating\n"
  116. "    pins across from each other (across the skinny width of the chip).\n"
  117. "    standard values for HORIZONTAL and VERTICAL are 2 and 6, respectively.\n"
  118. "    all CHIP type names must be unique.\n"
  119. " 9) number=name\n"
  120. "    this declares a pin name for the chip that is currently being defined.\n"
  121. "    this statement must follow a CHIP statement. pins not defined will have\n"
  122. "    no name, but you can still refer to them by number. each pin on a chip\n"
  123. "    can be named at most once.\n"
  124. "10) name=number\n"
  125. "    same as above.\n"
  126. "11) CHIPAT (row,column) NAME=name TYPE=type ORIENTATION=orientation\n"
  127. "    this defines an instance of a chip, and places the appropriate holes on\n"
  128. "    the board. (row,column) is the location of pin 1. NAME defines the name\n"
  129. "    to be used in following CONNECT statements. TYPE declares the\n"
  130. "    CHIPAT-defined type of the chip. ORIENTATION can have the values\n"
  131. "    NORMAL, UP, DOWN, and UPSIDEDOWN. all CHIPAT names must be unique.\n"
  132. "12) INLINE TYPE=type PINS=number HORIZONTAL=number\n"
  133. "    this declares an inline type, which can be used to place chips on the\n"
  134. "    board (see CHIPAT, below), but does not itself place anything on the\n"
  135. "    board. TYPE gives the name that will be used in later INLINAT\n"
  136. "    statements. PINS declares the number of pins. HORIZONTAL gives the\n"
  137. "    number of 50-mil units separating adjacent pins.  Standard value\n"
  138. "    for HORIZONTAL is 2.  All INLINE type names must be unique.\n"
  139. "13) INLINEAT (row,column) NAME=name TYPE=type ORIENTATION=orientation\n"
  140. "    this defines an instance of an inline, and places the appropriate\n"
  141. "    holes on the board. (row,column) is the location of pin 1. NAME defines\n"
  142. "    the name to be used in following CONNECT statements. TYPE declares the\n"
  143. "    INLINEAT-defined type of the chip. ORIENTATION can have the values\n"
  144. "    NORMAL, UP, DOWN, and UPSIDEDOWN. all CHIPAT names must be unique.\n\n"
  145. "      NORMAL           UP           DOWN        UPSIDEDOWN\n"
  146. "      6 5 4          +---+         +---+          3 2 1\n"
  147. "    +-*-*-*-+      4 *   * 3     1 * | * 6      +-*-*-*-+\n"
  148. "    |  ->   |      5 * ^ * 2     2 * v * 5      |   <-  |\n"
  149. "    +-*-*-*-+      6 * | * 1     3 *   * 4      +-*-*-*-+\n"
  150. "      1 2 3          +---+         +---+          4 5 6\n\n"
  151. "    Usually the highest-numbered pin (pin N) is Vcc (power) and the pin\n"
  152. "    farthest from it (pin N/2) is GND (ground).\n\n";
  153.  
  154. extern int Initialize( char *, int );
  155. extern void Solve( FILE * );
  156. extern void Report( FILE * );
  157.  
  158. void main( int, char *[] );
  159.  
  160. void main ( argc, argv ) /* input board, route traces, output routed board */
  161.     int argc;
  162.     char **argv;
  163.     {
  164.     char *self, *p;
  165.     FILE *fp, *fp2;
  166.     long start, stop, min, hours;
  167.  
  168.     printf( "Copyright (C) Randy Nevin, 1989, 1990. Version 1.10\n" );
  169.     printf( "See source code for rights granted.\n\n" );
  170.     start = time( NULL );
  171.  
  172.     self = (argv++)[0];
  173.     /* get rid of initial part of path */
  174.     if ((p = strrchr( self, '\\' )) || (p = strrchr( self, ':' )))
  175.         self = ++p;
  176.     /* get rid of extension */
  177.     if ((p = strrchr( self, '.' )) && !stricmp( p, ".EXE" ))
  178.         *p = 0;
  179.  
  180.    while( argc-- > 1 && ( **argv == '-' || **argv == '/') )
  181.       {
  182.          ++*argv;
  183.          while( **argv != '\0' )
  184.          {
  185.             switch( **argv )
  186.             {
  187.                 case 'n' :
  188.                 case 'N' :
  189.                          ++*argv;
  190.                          SortConnects = 0;
  191.                          break;
  192.                 case 's' :
  193.                 case 'S' :
  194.                          ++*argv;
  195.                          DoubleSided = 0;
  196.                          break;
  197.                 case 't' :
  198.                 case 'T' :
  199.                          ++*argv;
  200.                          TopSide = 1;
  201.                          break;
  202.                 case 'd' :
  203.                 case 'D' :
  204.                          ++*argv;
  205.                          NoDiag = 1;
  206.                          break;
  207.                 case 'b' :
  208.                 case 'B' :
  209.                          ++*argv;
  210.                          TopSide = 0;
  211.                          break;
  212.                 case 'm' :
  213.                 case 'M' :
  214.                          ++*argv;
  215.                          Manual = 1;
  216.                          break;
  217.                 case '0' :
  218.                          ++*argv;
  219.                          RatsNest = 1;
  220.                          break;
  221.                 case 'p' :
  222.                 case 'P' :
  223.                          if ( sscanf(++(*argv),"%d",&Percent ) == 0 )
  224.                             {
  225.                                printf("\nOption \"P\" needs a number!");
  226.                                exit(1);
  227.                             }
  228.                          ++*argv;
  229.                          break;
  230.                 default :
  231.                         fprintf(stderr," Unrecongized command-line switch\n"
  232.                                 " The valid switches are:  /N, /S, /T, /B /0"
  233.                                 "\n Program aborted\n" );
  234.                         exit( 1 );
  235.             }
  236.          }
  237.      argv++;
  238.       }
  239.  
  240.     if (Manual){
  241.         printf( "%s", man );
  242.         }
  243.  
  244.     if ((argc < 2) || Manual) { /* need infile and outfile */
  245.         fprintf( ( (Manual) ? stdout: stderr), "usage: %s [options] infile "
  246.                      "outfile\n", self );
  247.         fprintf( ( (Manual) ? stdout: stderr),
  248.                " /N    = no sorting of non-PRIORITY CONNECTs\n"
  249.                " /M    = Print to stdout the manual of valid input statements\n"
  250.                " /0    = Output a ratsnest ony. \n"
  251.                " /Pxxx = Percentage at which to quit trying to route \n"
  252.                "         the trace. \n"                        
  253.                " /S    = single sided printed circuit boards \n"
  254.                " /D    = Diagnal Traces not allowed\n"
  255.                " /T    = Route the top side of the board. Only valid if\n "
  256.                "         S is used. \n"
  257.                " /B    = Route the bottom side of the board. Only valid if\n "
  258.                "         S is used.  Default Option. \n"
  259.                );
  260.         exit( -1 );
  261.         }
  262.  
  263.     fp2 = NULL;
  264.     if (!(fp = fopen( argv[1], "wb" ))) {
  265.         fprintf( stderr, "can't open %s\n", argv[1] );
  266.         exit( -1 );
  267.         }
  268.     if ( argc > 2 ){
  269.         if (!(fp2 = fopen( argv[2], "wt" ))) {
  270.             fprintf( stderr, "can't open %s\n", argv[2] );
  271.             exit( -1 );
  272.             }
  273.         }
  274.     Ntotal = Initialize( argv[0], 1 ); /* echo memory used */
  275.     Solve( fp2 );
  276.     Report( fp );
  277.     stop = time( NULL ) - start;
  278.     min = stop / 60; stop -= min * 60;
  279.     printf( "time = %ld min%s, %ld second%s\n", min, (min == 1) ? "" : "s",
  280.              stop, (stop == 1) ? "" : "s" );
  281.     if (argc > 2 ) fclose( fp2 );
  282.     exit( 0 );
  283.     }
  284.  
  285.  
  286.  
  287.  
  288.  
  289.  
  290.  
  291.  
  292.  
  293.  
  294.  
  295.  
  296.  
  297.  
  298.  
  299.  
  300.  
  301.