-
Exporting KiCad DSN to Text
12/03/2019 at 08:37 • 0 commentsExporting KiCad DSN to Text
I finally got round to exporting the DSN file to some intermediate files that are easier to work with:
- pcb.txt
- nets.txt
- parts.txt
The code is rather bloated so later I will try and remove the S-Expr linked list.
The "pcb" file looks like this (units are um):
pcb: 130810 -95250 130810 -120650 175260 -120650 175260 -95250 130810 -95250 130810 -95250
I can write some code to consider an arbitrary shape but a rectangle is good enough for now.
The "nets":
nets: C1-1 D2-1 Q1-2 R2-1 C1-2 D1-2 D3-2 D4-2 D5-2 R3-1 D1-1 D2-2 D3-1 J1-3 D4-1 J1-4 D5-1 J1-5 J1-1 R1-2 R3-2 J1-2 Q1-3 R1-1 J1-6 Q1-1 R2-2
The nets will need to be converted into number for the router.
And finally the "pins" or parts:
Component Surface/Pin X Y Rot C1 front 154940 -105410 180 1 0 0 0 2 5000 0 0 D1 front 165100 -110490 180 1 0 0 0 2 7620 0 0 D2 front 157480 -107950 0 1 0 0 0 2 7620 0 0 D3 front 139700 -107950 0 1 0 0 0 2 7620 0 0 D4 front 139700 -110490 0 1 0 0 0 2 7620 0 0 D5 front 139700 -113030 0 1 0 0 0 2 7620 0 0 J1 front 135890 -102870 0 1 0 0 0 2 0 -2540 0 3 0 -5080 0 4 0 -7620 0 5 0 -10160 0 6 0 -12700 0 Q1 front 163830 -101600 90 2 1270 1270 90 3 2540 0 90 1 0 0 90 R1 front 147320 -102870 180 1 0 0 0 2 7620 0 0 R2 front 157480 -105410 0 1 0 0 0 2 7620 0 0 R3 front 147320 -105410 180 1 0 0 0 2 7620 0 0
All the pin locations need to be processed (translated and rotated).
The next step is to build the "links" list:
SRC DST 1 7 7 8 2 13 13 22 3 9 4 10 5 11 6 24 24 25 12 14 14 19 14 15 15 16 16 21 17 18 18 23 18 20 26 27
The then build a "map":
25 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 12 0 17 0 0 0 0 0 25 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 13 0 18 0 0 0 0 22 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 23 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 14 0 19 0 0 0 0 24 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 15 0 20 0 0 0 0 0 26 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 16 0 21 0 0 0 0 0 27 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
AlanX
-
Importing a KiCAD SPECCTRA File
07/24/2019 at 10:25 • 0 commentsThe KiCAD SPECCTRA File
KiCAD can export PCBs as "dsn" or SPECCTRA files. These file are ASCII and use Symbolic Expression format (often called S-Expr format). The SPECCTA specification is quite complex but for this application I only need the Board Area and the Pin locations.
I have modified code by https://github.com/benthepoet/c-sexpr-parser to read "dsn" format and then write it out again. As the rewritten "dsn" file was readable I assume that the code is correct.
Here is the modified "sexpr.h" and "sexpr.c" files:And finally my code to read/write the "dsn" file:
enum SNodeType { LIST, STRING, SYMBOL, INTEGER, FLOAT }; struct SNode { struct SNode *next; enum SNodeType type; union { struct SNode *list; char *value; }; }; struct SNode *snode_parse(FILE *fp); void snode_free(struct SNode *node);
#include <ctype.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include "sexpr.h" #define BUFFER_MAX 511 static char quoteChar='"'; int is_float(char *str) { char *ptr=NULL; strtod(str,&ptr); return !(*ptr); } int is_integer(char *str) { char *ptr=NULL; strtol(str,&ptr,10); return !(*ptr); } int is_lst_term(int c) { return ((c==EOF)||(isspace(c))||(c=='(')||(c ==')')); } int is_str_term(int c) { return ((c==EOF)||(c=='"')); } char *read_value(FILE *fp,int *c,int (*is_term)(int)) { int len=0; char buffer[BUFFER_MAX+1]; while ((!is_term(*c=fgetc(fp)))&&(len<BUFFER_MAX)) { buffer[len]=(char)*c; len++; } buffer[len]='\0'; char *str=malloc((unsigned int)(len+1)*sizeof(char)); return strcpy(str,buffer); } // Recursively parse an s-expression from a file stream struct SNode *snode_parse(FILE *fp) { // Using a linked list, nodes are appended to the list tail until we // reach a list terminator at which point we return the list head. struct SNode *tail=NULL,*head=NULL; int c; char lastSymbol[BUFFER_MAX+1]=""; while ((c=fgetc(fp))!=EOF) { struct SNode *node=NULL; if (c==')') { // Terminate list recursion break; } else if (c=='(') { // Begin list recursion node=malloc(sizeof(struct SNode)); node->type=LIST; node->list=snode_parse(fp); } else if ((strcmp(lastSymbol,"string_quote")==0)&&(!isspace(c))) { // Read symbol ungetc(c,fp); node=malloc(sizeof(struct SNode)); node->value=read_value(fp,&c,&is_lst_term); // Put the terminator back ungetc(c,fp); node->type=SYMBOL; strcpy(lastSymbol,node->value); quoteChar=lastSymbol[0]; } else if (c=='"') { node=malloc(sizeof(struct SNode)); node->type=STRING; node->value=read_value(fp,&c,&is_str_term); } else if (!isspace(c)) { // Read a float, integer, or symbol ungetc(c,fp); node=malloc(sizeof(struct SNode)); node->value=read_value(fp,&c,&is_lst_term); // Put the terminator back ungetc(c,fp); if (is_integer(node->value)) { node->type=INTEGER; } else if (is_float(node->value)) { node->type=FLOAT; } else { node->type=SYMBOL; strcpy(lastSymbol,node->value); } } if (node!=NULL) { // Terminate the node node->next=NULL; if (head==NULL) { // Initialize the list head head=tail=node; } else { // Append the node to the list tail tail=tail->next=node; } } } return head; } // Recursively free memory allocated by a node void snode_free(struct SNode *node) { while (node!=NULL) { struct SNode *tmp=node; if (node->type==LIST) { snode_free(node->list); } else { // Free current value free(node->value); node->value=NULL; } node=node->next; // Free current node free(tmp); tmp=NULL; } }
And my code to read the "dsn" file and then rewrite (export) it:
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> #include "sexpr.h" void run_tests(struct SNode *node); int main(int argc, char *argv[]) { // Unused parameters (void)argc; (void)argv; FILE *fp=fopen("DTL.dsn","r"); struct SNode *node=snode_parse(fp); fclose(fp); run_tests(node); snode_free(node); return 0; } void run_tests(struct SNode *node) { int depth=1; int stackSize=1; struct SNode* current=NULL; struct SNode** stack=malloc((unsigned long)stackSize*sizeof(struct SNode)); FILE *F1=fopen("test.dat","w"); stack[0]=NULL; current=node->list; fprintf(F1,"( "); while (depth>0) { if (current==NULL) { depth--; fprintf(F1,") "); current=stack[depth]; } else if (current->type==LIST) { stack[depth]=current->next; if (depth>=stackSize) { stackSize=depth+1; stack=(struct SNode**)realloc(stack,(unsigned int)stackSize*sizeof(struct SNode)); } fprintf(F1,"\n"); for (int i=0;i<depth;i++) fprintf(F1," "); fprintf(F1,"( "); depth++; for (int i=0;i<depth;i++) printf(" "); current=current->list; } else if (current->type==SYMBOL) { fprintf(F1,"%s ",current->value); current=current->next; } else if (current->type==STRING) { fprintf(F1,"\"%s\" ",current->value); current=current->next; } else if (current->type==INTEGER) { fprintf(F1,"%d ",atoi(current->value)); current=current->next; } else if (current->type==FLOAT) { fprintf(F1,"%f ",atof(current->value)); current=current->next; } } fclose(F1); }
Here is the first few lines of the exported "dsn" file:
( pcb /home/alanx/KiCAD/DTL/DTL.dsn ( parser ( string_quote " ) ( space_in_quoted_tokens on ) ( host_cad "KiCad's Pcbnew" ) ( host_version "4.0.7-e2-6376~61~ubuntu18.04.1" ) ) ( resolution um 10 ) ( unit um ) ( structure ( layer F.Cu ( type signal ) ( property ( index 0 ) ) ) ( layer B.Cu ( type signal ) ( property ( index 1 ) ) ) ( boundary ( path pcb 0 130810 -95250 130810 -120650 175260 -120650 175260 -95250 130810 -95250 130810 -95250 ) ) ( plane Earth ( polygon F.Cu 0 129540 -93980 176530 -93980 176530 -121920 129540 -121920 ) ) ( via "Via[0-1]_600:400_um" ) ( rule ( width 250 ) ( clearance 200.100000 ) ( clearance 200.100000 ( type default_smd ) ) ( clearance 50 ( type smd_smd ) ) ) )
Now all I have to do is to export what I need.
Here is the scan of the "dsn" file for what I need:
PCB DTL component Capacitors_THT:C_Rect_L7.0mm_W2.0mm_P5.00mm place C1 154940 -105410 front 180 component Diodes_THT:D_DO-35_SOD27_P7.62mm_Horizontal place D1 165100 -110490 front 180 place D2 157480 -107950 front 0 place D3 139700 -107950 front 0 place D4 139700 -110490 front 0 place D5 139700 -113030 front 0 component Socket_Strips:Socket_Strip_Straight_1x06_Pitch2.54mm place J1 135890 -102870 front 0 component TO_SOT_Packages_THT:TO-92_Molded_Narrow place Q1 163830 -101600 front 90 component Resistors_THT:R_Axial_DIN0207_L6.3mm_D2.5mm_P7.62mm_Horizontal place R1 147320 -102870 front 180 place R2 157480 -105410 front 0 place R3 147320 -105410 front 180 image Capacitors_THT:C_Rect_L7.0mm_W2.0mm_P5.00mm pin Round[A]Pad_1600_um 1 0 0 pin Round[A]Pad_1600_um 2 5000 0 image Diodes_THT:D_DO-35_SOD27_P7.62mm_Horizontal pin Rect[A]Pad_1600x1600_um 1 0 0 pin Oval[A]Pad_1600x1600_um 2 7620 0 image Socket_Strips:Socket_Strip_Straight_1x06_Pitch2.54mm pin Rect[A]Pad_1700x1700_um 1 0 0 pin Oval[A]Pad_1700x1700_um 2 0 -2540 pin Oval[A]Pad_1700x1700_um 3 0 -5080 pin Oval[A]Pad_1700x1700_um 4 0 -7620 pin Oval[A]Pad_1700x1700_um 5 0 -10160 pin Oval[A]Pad_1700x1700_um 6 0 -12700 image TO_SOT_Packages_THT:TO-92_Molded_Narrow pin Round[A]Pad_1000_um 2 1270 1270 pin Round[A]Pad_1000_um 3 2540 0 pin Rect[A]Pad_1000x1000_um 1 0 0 image Resistors_THT:R_Axial_DIN0207_L6.3mm_D2.5mm_P7.62mm_Horizontal pin Round[A]Pad_1600_um 1 0 0 pin Oval[A]Pad_1600x1600_um 2 7620 0 net Net-(C1-Pad1) pins C1-1 D2-1 Q1-2 R2-1 net Net-(C1-Pad2) pins C1-2 D1-2 D3-2 D4-2 D5-2 R3-1 net Net-(D1-Pad1) pins D1-1 D2-2 net Net-(D3-Pad1) pins D3-1 J1-3 net Net-(D4-Pad1) pins D4-1 J1-4 net Net-(D5-Pad1) pins D5-1 J1-5 net Net-(J1-Pad1) pins J1-1 R1-2 R3-2 net Net-(J1-Pad2) pins J1-2 Q1-3 R1-1 net Earth pins J1-6 Q1-1 R2-2
Now I need to write code to link the "component/place" to the "image/pin" for positional information and then decode "net/pins".
Update
I have bee a little bit distracted but back to it and have managed (though the use of associative arrays) to join the data:
C1 154940 -105410 front 180 pin 1 0 0 pin 2 5000 0 D1 165100 -110490 front 180 pin 1 0 0 pin 2 7620 0 D2 157480 -107950 front 0 pin 1 0 0 pin 2 7620 0 D3 139700 -107950 front 0 pin 1 0 0 pin 2 7620 0 D4 139700 -110490 front 0 pin 1 0 0 pin 2 7620 0 D5 139700 -113030 front 0 pin 1 0 0 pin 2 7620 0 J1 135890 -102870 front 0 pin 1 0 0 pin 2 0 -2540 pin 3 0 -5080 pin 4 0 -7620 pin 5 0 -10160 pin 6 0 -12700 Q1 163830 -101600 front 90 pin 2 1270 1270 pin 3 2540 0 pin 1 0 0 R1 147320 -102870 front 180 pin 1 0 0 pin 2 7620 0 R2 157480 -105410 front 0 pin 1 0 0 pin 2 7620 0 R3 147320 -105410 front 180 pin 1 0 0 pin 2 7620 0
Still more work to do.
AlanX
-
First Steps
07/20/2019 at 02:23 • 0 commentsFirst Steps
There is a lot of work setting up the interface between the schematic capture and PCB layout applications and the auto-routing applications. So I will just read in a simple text files to begin.
The Schematic
One of my first PCB schematics was a DTL (Diode Transistor Logic) three input NAND gate. Here is a KiCAD version.
First the KiCAD schematic:
And the KiCAD PCB:
Now I have tried to get a single sided PCB version of this design (in Eagle and EasyEDA) but it is surprisingly difficult to do. KiCAD does not even offer the option. In the end I had to hand route a design (okay it has nine copies):
With a bit of imagination you should see the KiCAD PCB here (map.txt):
And the links list:
SRC DST 1 7 7 8 2 13 13 22 3 9 4 10 5 11 6 24 24 25 12 14 14 19 14 15 15 16 16 21 17 18 18 23 18 20 26 27
After a Day of Coding
Here is a series of images as I debugged and got the penalty function working.
Well its just about getting something on screen to look at!
I want to penalise paths that get too close to the pins (thus the small red dots):
Note: The red tracks failed to find a legal path. A diagonal path between tracks was consider illegal.
Here is a working case:
Note: The links are exactly honoured and thus the ugly links.
Finally with a pseudo-Steiner Tree modification gives a pretty reasonable result:
So for a single side PCB I have a result that works (for the small example).
So how is that, all of the above in less than 600 lines of code!
A lot more to do, add multi-able layers and back-tracking when the algorithm fails.
Update
Added some code to randomly swap around the links to see if I can improve the result.
I gave the router 1 second, it looked as 2083 options and reduced the penalty from 682 to 582:
I have been looking at the passes that failed to determine if there is an easy heuristic I could apply. Even in the above image the I can see faults that could be fixed that would improve the success rate.A couple of papers suggested:
- Sorting the nest by complexity (i.e. number of bounding square interactions) or at least net length.
- And if that fails, then route the conflicted net on the next layer.
Currently I completely randomise the links for a run and run a many as I can in one second.
Here is an example where I use the above approach (i.e. a single run) but include a congestion penalty:
You can see that the congestion penalty has moved the tracks away from the pins (and other tracks) leaving space for later tracks. This in my mind is a pretty good result (for a single run). Without the congestion penalty you get:
Code
I have posted the code for the above.
Paper by Eric Rosenberg on Iterative Routers
I found a paper by Eric Rosenberg that describes an iterative method for improving the router performance. Here is a simplified version of his algorithm:
- There is no prioritisation of the nets (or links).
- Initially with the supply/demand router, all nets are routed without regard to conflicts and can share the grid node (or cell). After each iteration, the conflicted cells are given a penalty with the "hope" that it will resolve the conflict.
- With each iteration the penalties of the remaining conflicted cell are increased.
- Eric Rosenberg proposes that if a solution cannot be found after a number of iterations, then the conflicting nets are ripped up and rerouted.
It should be noted the algorithm can be unstable and much of Eric Rosenberg's paper is about approaches to resolve this issue.
AlanX