spiceparser/netlist.c

   1 /********************
   2     This file is part of the software library CADLIB written by Conrad Ziesler
   3     Copyright 2003, Conrad Ziesler, all rights reserved.
   4
   5 *************************
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19
  20 ******************/
  21 /* netlist.c, generalized netlist functions
  22 Conrad Ziesler
  23 */
  24 #include <stdio.h>
  25 /* note:
  26
  27    we try to store a netlist in a form which is as compact as possible, while being extensible
  28    by clients, in addition to being general enough to handle all possible netlist input formats
  29
  30    the primary memory saving device is the termptr_t bitfield, where we make a complex
  31    pointer which represents the type of node it points to.
  32
  33    also we statically allocate memory for the devices using list_t blocks.
  34    and allocate extra space per device as defined by the client structure
  35
  36 */
  37
  38 #include <stdarg.h>
  39 #include <stdio.h>
  40
  41 #include "debug.h"
  42
  43 #define __NETLIST_PRIVATE__
  44 #include "netlist.h"
  45 #include "mergedup.h"
  46
  47
  48 /* call these at entry and exit of all netlist functions that potentially modify equations */
  49 void netlist_eqn_begin(netlist_t *nl)
  50 {
  51   assert(nl->eqn_mem!=NULL);
  52   eqn_mem_push(nl->eqn_mem);
  53 }
  54
  55 void netlist_eqn_end(netlist_t *nl)
  56 {
  57   if(eqn_mem_pop()!=nl->eqn_mem)
  58     assert(0);
  59 }
  60
  61
  62 /* some assumptions we make about bitfield encodings */
  63 int netlist_machine(void)
  64 {
  65  assert(sizeof(termptr_t)==sizeof(void*));
  66  assert(sizeof(unsigned int) == sizeof(void*));
  67  assert(sizeof(unsigned int) == 4 );
  68  return 0;
  69 }
  70
  71 termptr_t netlist_termptr_null_t(termptr_t from)
  72 {
  73   from.nonnull=0;
  74   return from;
  75 }
  76
  77 termptr_t netlist_termptr_null(void)
  78 {
  79   termptr_t v;
  80   v.nonnull=0;
  81   v.termi=0;
  82   v.devi=0;
  83   v.devt=0;
  84   return v;
  85 }
  86
  87 termptr_t netlist_termptr_nonnull(termptr_t from)
  88 {
  89   from.nonnull=1;
  90   return from;
  91 }
  92
  93
  94 termptr_t netlist_termptr(int dev, int term, int type)
  95 {
  96   termptr_t t;
  97   t.termi=term;
  98   t.devi=dev;
  99   t.devt=type;
 100   t.nonnull=1;
 101   return t;
 102 }
 103
 104 int netlist_termptr_devi(termptr_t t)
 105 { return t.devi; }
 106
 107 int netlist_termptr_termi(termptr_t t)
 108 { return t.termi; }
 109
 110 int netlist_termptr_devt(termptr_t t)
 111 { return t.devt; }
 112
 113 termptr_t netlist_termptr_deref(netlist_t *nl, termptr_t t)
 114 {
 115   assert(t.devt>=0);
 116   assert(t.devt<nl->qe);
 117   assert(t.termi>=0);
 118   assert(t.termi<nl->e[t.devt].qterms);
 119   assert(t.nonnull==1);
 120   return NETLIST_TERM(nl,t.devt,t.devi,t.termi);
 121 }
 122
 123 int netlist_node_termptr(netlist_t *nl, termptr_t t)
 124 {
 125   while(t.devt!=DEVT_NODE)
 126     t=netlist_termptr_deref(nl,t);
 127   return t.devi;
 128 }
 129
 130
 131 int netlist_add_dev_(netlist_t *nl, int devt, void *p)
 132 {
 133   int i;
 134   assert(devt>=0);
 135   assert(devt<nl->qe);
 136   i=list_add(&(nl->e[devt].l),p);
 137   return i;
 138 }
 139
 140 int netlist_add_dev(netlist_t *nl, int devt)
 141 {
 142   int i;
 143   assert(devt>=0);
 144   assert(devt<nl->qe);
 145   i=list_nextz(&(nl->e[devt].l));
 146   return i;
 147 }
 148
 149 /* merge duplicate entities summing results
 150    the user function tocompare returns a ptr to some static area
 151    which is filled with data that should be sorted and matched to
 152
 153    the user function sum takes the indices of the two entities
 154    and performs the equivilent of [a]=[a]+[b]
 155    if sum returns 1 we remove item b
 156    so sum should frees any private data associated with [b] on 1
 157 */
 158
 159 void netlist_merge(netlistfunc_t *nm)
 160 {
 161   mergedup_t *md;
 162   int i,ib,ia;
 163   void *data;
 164   char *buffer;
 165   list_t *entity=&(nm->entity->l);
 166   list_t newl;
 167
 168   if(nm->tocompare==NULL)return;
 169   if(nm->sum==NULL)return;
 170   if(nm->qcmp<=0)return;
 171   buffer=malloc(nm->qcmp);
 172   assert(buffer!=NULL);
 173   memset(buffer,0,nm->qcmp);
 174
 175   md=mergedup_alloc(list_qty(entity),nm->qcmp);
 176
 177   list_iterate(entity,i,data)
 178     {
 179       nm->tocompare(nm,i,buffer);
 180       mergedup_fill(md,buffer,i);
 181     }
 182   free(buffer);
 183   buffer=NULL;
 184   mergedup_sort(md);
 185   ib=-1;
 186   ia=-1;
 187   while(1)
 188     {
 189       ib=mergedup_visit(md,0); /* get next same */
 190       if(ib==-1)
 191         {
 192           i=ia;
 193           ia=mergedup_visit(md,1); /* get next different */
 194           if(ia==-1)break;
 195         }
 196       else
 197         {
 198           if(nm->sum(nm,ia,ib))
 199             {
 200               /* flag delete item */
 201               mergedup_setbit(md,ib);
 202             }
 203         }
 204
 205     }
 206
 207   ia=0; /* count number of remaining elements */
 208   for(i=0;i<list_qty(entity);i++)
 209     if(!mergedup_testbit(md,i))ia++;
 210
 211   list_copyfrom(&newl,entity); /* setup new list */
 212   list_hint(&newl,ia); /* pre-alloc data */
 213   list_iterate(entity,i,data)  /* fill new list */
 214     {
 215       if(!mergedup_testbit(md,i))
 216         list_add(&newl,data);
 217     }
 218   mergedup_free(md); /* free mergedup */
 219   list_empty(entity); /* free old list data */
 220   *entity=newl; /* copy over new pointers into old list */
 221 }
 222
 223
 224 /* distribute some attribute across entity
 225
 226    network of entities, connected via nodes.
 227    some attribute associated with an entity terminal
 228    first accumulate properties per node
 229    then distribute to all entities connected to that node
 230
 231    ie: extract programs lump diffusion on one fet instead of distributing it as per width
 232    for resizing
 233 */
 234
 235 void netlist_distribute(netlistfunc_t *nm)
 236 {
 237   int i,j;
 238   netlist_t *nl=nm->nl;
 239   list_t *entity=&(nm->entity->l);
 240   entity_t *e=nm->entity;
 241   int qterm=nm->entity->qterms;
 242   float *node_sums;
 243
 244   if(nm->qproperties<=0)return;
 245
 246   node_sums=malloc(sizeof(float)*list_qty(&(nl->e[DEVT_NODE].l))*nm->qproperties);
 247   assert(node_sums!=NULL);
 248
 249   for(i=0;i< (list_qty(&(nl->e[DEVT_NODE].l))*nm->qproperties);i++)
 250     node_sums[i]=0.0;
 251
 252   list_iterate_(entity,i)
 253     {
 254       for(j=0;j<qterm;j++)
 255         {
 256           termptr_t t;
 257           float *node_data;
 258           t=NETLIST_E_TERM(e,i,j);
 259           node_data=node_sums+ (netlist_termptr_devi(t)*nm->qproperties) ;
 260           if(nm->accumulate!=NULL)
 261             nm->accumulate(nm,i,j,node_data);
 262         }
 263     }
 264
 265   list_iterate_(entity,i)
 266     {
 267       for(j=0;j<qterm;j++)
 268         {
 269           termptr_t t;
 270           float *node_data;
 271           t=NETLIST_E_TERM(e,i,j);
 272           node_data=node_sums+ (netlist_termptr_devi(t)*nm->qproperties) ;
 273           if(nm->distribute!=NULL)
 274             nm->distribute(nm,i,j,node_data);
 275         }
 276     }
 277   free(node_sums);
 278 }
 279
 280
 281
 282 /*  fixup netlist node pointers
 283
 284     when we first build a netlist, we have a many to one relationship
 285     for the entity terminals, ie. they all point to the associated node
 286
 287     we also want to be able to enumerate the list of entity terminals on
 288     a given net, without going through all entities and comparing.
 289
 290     thus we have to fixup the netlist, making a linked list out of the terminal ptrs
 291
 292     so we can walk through all the terminals on a net.
 293     also we put the actual node on the head of that list.
 294
 295     we call a user function for each terminal on the net (to store back pointer if necessary)
 296 */
 297
 298 void netlist_fixup(netlistfunc_t *nm)
 299 {
 300   netlist_t *nl=nm->nl;
 301   int i,j,k;
 302   int qterms;
 303   termptr_t t,nt;
 304
 305   void *dp;
 306   void *np;
 307
 308   /* init tail ptrs, to point to the head ptr */
 309   list_iterate(&(nl->e[DEVT_NODE].l),i,np)
 310     {
 311       termptr_t t;
 312       NETLIST_TERM(nl,DEVT_NODE,i,1)=t=netlist_termptr(i,0,DEVT_NODE);
 313       NETLIST_TERM(nl,DEVT_NODE,i,0)=netlist_termptr_null_t(t);
 314     }
 315
 316   for(i=0;i<nl->qe;i++)
 317     {
 318       qterms=nl->e[i].qterms;
 319       list_iterate(&(nl->e[i].l),j,dp)
 320         {
 321           for(k=0;k<qterms;k++)
 322             {
 323               termptr_t npn1;
 324               t=NETLIST_TERM(nl,i,j,k);
 325               assert(t.devt==DEVT_NODE);
 326               nt=NETLIST_TERM(nl,t.devt,t.devi,1); /* tail ptr */
 327               npn1=NETLIST_TERM(nl,t.devt,t.devi,1)=netlist_termptr(j,k,i);
 328               NETLIST_TERM(nl,nt.devt,nt.devi,nt.termi)=npn1; /* also links n[0] */
 329               /* call user routine if not avail */
 330               if(nm->fixup!=NULL)
 331                 nm->fixup(nm,t);
 332             }
 333         }
 334     }
 335 }
 336
 337
 338
 339 int netlist_findnode(netlist_t *nl, char *str)
 340 {
 341   int pindex;
 342   pindex=names_check(nl->names,str);
 343   return pindex;
 344 }
 345
 346
 347 termptr_t netlist_node(netlist_t *nl, char *str, void *parent)
 348 {
 349   int pindex;
 350   termptr_t tp;
 351   if(0)fprintf(stderr,"\nnode %s %p\n",str,parent);
 352   pindex=names_check(nl->names,str);
 353   if(pindex==-1)
 354     {
 355       pindex=netlist_add_dev(nl,DEVT_NODE);
 356       names_add(nl->names,pindex,str);
 357       tp=netlist_termptr(pindex,0,DEVT_NODE);
 358       NETLIST_TERM(nl,DEVT_NODE,pindex,0)=tp;
 359       NETLIST_TERM(nl,DEVT_NODE,pindex,1)=tp;
 360     }
 361   else
 362     {
 363       tp=netlist_termptr(pindex,0,DEVT_NODE);
 364     }
 365   return tp;
 366 }
 367
 368
 369
 370 int netlist_newdev_fromnode(netlist_t *nl, int devt, dev_input_t parent , termptr_t n[])
 371 {
 372   int q,qv,i,index;
 373
 374   qv =NETLIST_QVALS  (nl,devt);
 375   q  =NETLIST_QTERMS (nl,devt);
 376
 377   index=netlist_add_dev(nl,devt);
 378   NETLIST_PARENT(nl,devt,index)=parent;
 379
 380   for(i=0;i<q;i++)
 381     NETLIST_TERM(nl,devt,index,i)=n[i];
 382
 383   for(i=0;i<qv;i++)
 384     NETLIST_VAL(nl,devt,index,i)=eqn_empty();
 385
 386   return index;
 387 }
 388
 389
 390 void netlist_init(netlist_t *nl)
 391 {
 392   int i;
 393   entity_t e=ENTITY_INVALID;
 394   netlist_machine();
 395   for(i=0;i<TERMPTR_MAX_DEVT;i++)
 396     nl->e[i]=e;
 397   nl->qe=0;
 398   nl->names=names_new();
 399   nl->input.p=NULL;
 400   nl->eqn_mem=eqn_mem_new();
 401   nl->iscopy=0;
 402   eqnl_init(&(nl->eqnl));
 403 }
 404
 405
 406 int netlist_register_entity (netlist_t *nl, int id, int qterms, int qvals, int qrest, char *sym, int othersize)
 407 {
 408   entity_t *ep;
 409
 410   if(nl->qe>=TERMPTR_MAX_DEVT)
 411     return -1;
 412
 413   ep=&(nl->e[nl->qe]);
 414   nl->qe++;
 415   ep->id=id;
 416   ep->qterms=qterms;
 417   ep->qvals=qvals;
 418   strncpy(ep->sym,sym,8);
 419   ep->sym[7]=0;
 420   ep->qcount=0;
 421   ep->qother=qrest;
 422   list_init(&(ep->l),NETLIST_OFFSET_OTHER((*ep))+othersize,LIST_DEFMODE);
 423   return nl->qe-1;
 424 }
 425
 426 netlist_input_t netlist_parse_input(scanner_t *scan, char *type, netlist_param_t *params)
 427 {
 428   netlist_input_t p;
 429
 430   netlist_machine();
 431   p.p=NULL;
 432
 433   if(strcmp(type,"spice")==0)
 434     {
 435       p.spice=spice_new(scan);
 436     }
 437   if(strcmp(type,"extract")==0)
 438     {
 439       /* p.ext=extract_new(scan); */
 440     }
 441   if(p.p==NULL)
 442     parse_error(scan, "Netlist: can't parse input of type %s",type);
 443   return p;
 444 }
 445
 446
 447
 448 void netlist_debug_input(void * dbg_fp, netlist_input_t p)
 449 {
 450   FILE *dbg=dbg_fp;
 451   netlist_machine();
 452
 453   if(p.p==NULL)
 454     fprintf(dbg, "can't debug netlist input, null ptr");
 455
 456   if(p.generic->magic==SPICE_MAGIC)
 457     spice_debug(dbg,p.spice);
 458
 459   else if(p.generic->magic==EXTRACT_MAGIC)
 460     /* p.ext=extract_debug(dbg,p.extract) */ ;
 461
 462 }
 463
 464 void netlist_debug(void * dbg_fp, netlist_t *nl)
 465 {
 466   netlist_debug_(dbg_fp,nl,0);
 467 }
 468
 469
 470 void netlist_debug_(void * dbg_fp, netlist_t *nl, int eval)
 471 {
 472   FILE *dbg=dbg_fp;
 473   int i;
 474
 475   if(nl==NULL)
 476     fprintf(dbg,"can't debug netlist, null ptr");
 477
 478   if(eval)
 479     {
 480       if(0)fprintf(stderr,"\n\nbegin evaldep \n\n");
 481       eqnl_evaldep(&(nl->eqnl));
 482       if(0)fprintf(stderr,"\n\ndone evaldep \n\n");
 483     }
 484
 485   fprintf(dbg,"debugging netlist eval=%i,  %p\n",eval,nl);
 486   for(i=0;i<nl->qe;i++)
 487     {
 488       entity_t *e;
 489       int j;
 490       eqn_t *v;
 491
 492       e=nl->e+i;
 493       fprintf(dbg,"   e %i %s, qterm=%i qcount=%i l.q,m=%i,%i\n",
 494                   i,e->sym,e->qterms,e->qcount,e->l.q,e->l.m
 495                   );
 496       list_iterate_(&(e->l),j)
 497         {
 498           int k;
 499           fprintf(dbg,"%i:  ",j);
 500
 501           for(k=0;k<e->qterms;k++)
 502             {
 503               termptr_t t=NETLIST_E_TERM(e,j,k);
 504               fprintf(dbg,"  [%i %s.%i]",t.devi,nl->e[t.devt].sym,t.termi);
 505               if(i==DEVT_NODE)
 506                 fprintf(dbg,"=%s ",names_lookup(nl->names,j));
 507             }
 508           fprintf(dbg,"\n  ");
 509
 510           v=NETLIST_VALS(nl,i,j);
 511           for(k=0;k<e->qvals;k++)
 512             {
 513               if(!eval)
 514                 {
 515                   char buf[32];
 516                   sprintf(buf," %i",k);
 517                   debug_eqn(dbg,buf,v+k);
 518                   fprintf(dbg," ");
 519                 }
 520               else
 521                 {
 522                   float f;
 523                   f=eqnl_eval(&(nl->eqnl),v[k]);
 524                   fprintf(dbg," ev %g ",f);
 525                 }
 526             }
 527           fprintf(dbg,"\n");
 528         }
 529     }
 530 }
 531
 532
 533
 534
 535
 536 /* release input from netlist (free structures if possible)
 537    after this call, all parent ptrs and input ptrs are set to null
 538 */
 539 void netlist_release(netlist_t *nl)
 540 {
 541   int i,j;
 542
 543   /* reset all the parent ptrs to null */
 544   for(i=0;i<nl->qe;i++)
 545     {
 546       list_iterate_(&(nl->e[i].l),j)
 547         NETLIST_PARENT(nl,i,j).p=NULL;
 548     }
 549
 550   /* call low level free function */
 551   switch(nl->input.generic->magic)
 552     {
 553     case SPICE_MAGIC:
 554       spice_release(nl->input.spice);
 555       break;
 556
 557     case EXTRACT_MAGIC:
 558       /* extract_release(nl->input.ext); */
 559       break;
 560     }
 561   nl->input.p=NULL;
 562 }
 563
 564
 565
 566 /* this releases input if not already done
 567    and then frees up the memory associated with the netlist
 568    any additional client memory should already have been freed
 569 */
 570
 571 void netlist_free(netlist_t *nl)
 572 {
 573   int i;
 574   if(nl!=NULL)
 575     {
 576       if(nl->input.p!=NULL)
 577         netlist_release(nl);
 578
 579       for(i=0;i<TERMPTR_MAX_DEVT;i++)
 580         list_empty(&(nl->e[i].l));
 581
 582       eqn_mem_free(nl->eqn_mem);
 583       nl->eqn_mem=NULL;
 584       if(!nl->iscopy)
 585         {
 586           eqnl_free(&(nl->eqnl));
 587           names_free(nl->names);
 588         }
 589       free(nl);
 590       nl=NULL;
 591     }
 592 }
 593
 594
 595
 596 int netlist_print_nodep(netlist_t *n, netprint_t grp, void * file_fp, void *gn, char *str)
 597 {
 598   FILE *file=file_fp;
 599   int index=-1;
 600   const char *err="node_error";
 601   char *name="error";
 602   int i;
 603
 604   fprintf(file,"%s",str);
 605   if(n!=NULL)
 606     index=list_index(&(n->e[DEVT_NODE].l),gn);
 607
 608   switch(grp)
 609     {
 610     case netprint_none:
 611       break;
 612     case netprint_name:
 613       if(index!=-1)
 614         fprintf(file,"%s",names_lookup(n->names,index));
 615       else fprintf(file,err);
 616       break;
 617     case netprint_index:
 618       if(index!=-1)
 619         fprintf(file,"n%i",index);
 620       else fprintf(file,err);
 621     case netprint_ptr:
 622       fprintf(file,"N_%p",gn);
 623     case netprint_nname:
 624       if(index!=-1)
 625         name=names_lookup(n->names,index);
 626       i=strlen(name)-8;
 627       if(i<0)i=0;
 628       fprintf(file,"N%i_%s",index,name+i);
 629       break;
 630
 631     case netprint_debug:
 632       if(index!=-1)
 633         fprintf(file,"[Node %p %i %s]",gn,index,names_lookup(n->names,index));
 634       else
 635         fprintf(file,"[Node %p]",gn);
 636       break;
 637     }
 638   return 0;
 639 }
 640
 641 void netlist_eval(netlist_t *n)
 642 {
 643   eqnl_evaldep(&(n->eqnl));
 644 }
 645
 646
 647
 648 /* this is somewhat inefficient, please don't rely on it  */
 649 netlist_t *netlist_copyisher(netlist_t *in, int extrasize, int extrasizes[])
 650 {
 651   char buffer[4096];
 652   int i,j,sin;
 653   void *p;
 654   netlist_t *nl;
 655   netlist_machine();
 656   nl=malloc(sizeof(netlist_t)+extrasize);
 657   assert(nl!=NULL);
 658   netlist_init(nl);
 659   nl->iscopy=1;
 660   for(i=0;i<in->qe;i++)
 661     {
 662       entity_t *ep;
 663       int index;
 664       ep=in->e+i;
 665       index=netlist_register_entity(nl,ep->id,ep->qterms,ep->qvals,ep->qother,ep->sym,extrasizes[i]);
 666       assert(sizeof(buffer)> (extrasizes[i]+NETLIST_OFFSET_OTHER((*ep))));
 667       assert(index>=0);
 668       memset(buffer,0,sizeof(buffer));
 669       sin=list_sizeof(&(in->e[i].l));
 670       list_hint(&(nl->e[index].l),sin);
 671       list_iterate(&(ep->l),j,p)
 672         {
 673           memcpy(buffer,p,sin); /* yes, we copy twice. this is required, think about it */
 674           list_add(&(nl->e[index].l),buffer);
 675         }
 676     }
 677
 678   /* POTENTIAL MEMORY LEAK HERE */
 679   nl->names=in->names;  /* share name database */
 680   nl->eqnl=in->eqnl;    /* share eqnl database */
 681   nl->input.p=NULL;     /* flag this to null   */
 682
 683   return nl;
 684 }
 685
 686