/* "NETCMP", an simple netlist comparator, Copyright (C) 1985, 1990 California Institute of Technology. Original author: Massimo Sivilotti Unix Port Maintainer: John Lazzaro Maintainers's address: lazzaro@csvax.caltech.edu; CB 425 CU Boulder/Boulder CO 91125. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation (any version). This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; see the file COPYING. If not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ /* Output from P2C, the Pascal-to-C translator */ /* From input file "compare.text" */ #include #include #include #include #include "compare.h" static char no_legal_moves_done; static tequivtype *find_equiv(nd, list) trantype *nd; tequivtype *list; { char found; /* somewhere in here, need to discount effect of bad node classes */ found = 0; while (list != NULL && !found) { if (nd->gate->my_equiv_class == list->egate && ((nd->s1->my_equiv_class == list->es1 && nd->s2->my_equiv_class == list->es2) || (nd->s1->my_equiv_class == list->es2 && nd->s2->my_equiv_class == list->es1))) /* p2c: compare.text, line 83: Note: Line breaker spent 1.0+0.30 seconds, 1884 tries on line 27 */ found = 1; else list = list->next; } if (found) return list; else return NULL; } /************************************************************************/ /************************************************************************/ /************************************************************************/ /************************************************************************/ /*************** ************/ /*************** TRANSISTOR STUFF BELOW..... ************/ /*************** ************/ /************************************************************************/ /************************************************************************/ /************************************************************************/ /************************************************************************/ static tequivtype *check_tran_class(scan) trantype *scan; { /* return a list of equivalence classes that the nodes pointed to by scan belong to */ tequivtype *tmp_head; trantype *scannext; tequivtype *class_, *new_class; tmp_head = NULL; while (scan != NULL) { scannext = scan->next; /* scan^.equiv_list := nil; */ /* generate_class (scan, scan^.equiv_list); do not need this for transistors*/ class_ = find_equiv(scan, tmp_head); if (class_ == NULL) { /* create new class */ /* writeln ('creating new tran class'); */ new_class = getTEquiv(); new_class->transistors = scan; new_class->egate = scan->gate->my_equiv_class; new_class->es1 = scan->s1->my_equiv_class; new_class->es2 = scan->s2->my_equiv_class; scan->next = NULL; scan->my_equiv_class = new_class; /* class^.equiv_list := scan^.equiv_list; nodes only */ add_tclass_to_list(new_class, &tmp_head); } else add_tran_to_class(scan, &class_); scan = scannext; } return tmp_head; } static void update_tran_classes(head) tequivtype **head; { /* for each equivalence class of transistors, all elements in the class are examined, and are broken into subclasses, depending on the equivalence classes of the nodes they touch. Each class is broken into a set of classes pointed to by tmp_class. These classes are examined at the end. Valid classes are broken off; invalid classes are re-aggregated, and flagged as bad. The resulting class(es) are placed in the tequiv list in the position originally occupied by the single class being considered. CALLS: check_tran_class add_tclass_to_list add_tran_to_class */ tequivtype *tmp_class, *good_classes; /* my list of new classes, contains only valid classes */ tequivtype *bad_classes; /* my list of new classes, contains only bad classes */ tequivtype *single_bad_class; /* bad_classes amalgamated into one */ tequivtype *scan, *scannext; /* scans down the list passed by head */ tequivtype *scan2, *scan2next; /* scans down the temporary list returned by check_tran_class */ trantype *scan3, *scan3next; /* scans down the tran list in each temporary bad class */ scan = *head; while (scan != NULL) { /* consider each equivalence class; split into equivalence sub-classes */ scannext = scan->next; if (!(fast_mode && scan->good && scan->count == 2)) { remove_tran_class_from_list(scan, head); tmp_class = check_tran_class(scan->transistors); /* split it up */ /* now try to reclaim the original scan node */ reclaim_tran_class(&scan); /* MAS */ /* for each sub-class, check for validity; reamalgamate if invalid */ bad_classes = NULL; scan2 = tmp_class; while (scan2 != NULL) { scan2next = scan2->next; if (valid_tran_class(scan2)) /* add to main list*/ add_tclass_to_list(scan2, &tequiv); else { if (allow_illegal_moves) add_tclass_to_list(scan2, &tequiv); else add_tclass_to_list(scan2, &bad_classes); } scan2 = scan2next; } /* now aggregate transistors in bad_classes into a single class */ single_bad_class = NULL; scan2 = bad_classes; /* will be nil if allow_illegal_moves */ while (scan2 != NULL) { /* writeln ('found 1 bad class of transistors'); */ scan2next = scan2->next; scan3 = scan2->transistors; while (scan3 != NULL) { scan3next = scan3->next; add_tran_to_class(scan3, &single_bad_class); scan3 = scan3next; } reclaim_tran_class(&scan2); /* reclaim the nodes used */ scan2 = scan2next; } /* add this single bad class back to the main list, if it exists */ if (single_bad_class != NULL) { single_bad_class->good = 0; add_tclass_to_list(single_bad_class, &tequiv); } } /* process next equivalence class */ scan = scannext; } } static tequivtype *find_class(t_type, head) transistor_types t_type; tequivtype *head; { /* returns the equivalence class with the correct transistor type */ tequivtype *scan; char done; scan = head; done = 0; while (scan != NULL && !done) { if (scan->transistors->t_type == t_type) done = 1; else scan = scan->next; } return scan; } static void initialize_transistors(head) tequivtype **head; { /* partition the transistors up into equivalence classes, according to their types */ trantype *scan, *scannext; tequivtype *class_, *new_class; scan = (*head)->transistors; *head = NULL; /* really want to reclaim the head node.....*/ while (scan != NULL) { scannext = scan->next; class_ = find_class(scan->t_type, *head); if (class_ == NULL) /* make a new class */ { /* create new class */ new_class = getTEquiv(); new_class->transistors = scan; scan->my_equiv_class = new_class; scan->next = NULL; add_tclass_to_list(new_class, head); } else add_tran_to_class(scan, &class_); scan = scannext; } /* now check all the classes for validity */ class_ = *head; while (class_ != NULL) { class_->good = !(number_of_trans_in_class(class_) & 1); class_ = class_->next; } } /*$if false$ PROCEDURE add_to_list (nd : tran_list_ptr; var head : equiv_list_ptr); { adds an element to the list, in sorted order } var tmp : equiv_list_ptr; begin if head = nil then begin head := getEquivList; { FIX THIS ***** MAS ******} with head^ do begin tran_class := nd^.tran^.my_equiv_class; next := nil; end; end else if ord(nd^.tran^.my_equiv_class) <= ord(head^.tran_class) then begin tmp := getEquivList; { FIX THIS ***** MAS ******} with tmp^ do begin tran_class := nd^.tran^.my_equiv_class; next := head; end; head := tmp; end else begin { insert in rest of list } add_to_list (nd, head^.next); { FIX THIS ***** MAS ******} { this wants to be made iterative, but not now } end; end; $end$*/ static void add_to_list(nd, head) tran_list_type *nd; equiv_list_type **head; { /* adds an element to the list, in sorted order */ equiv_list_type *tmp; char done; equiv_list_type *tmp_head; if (*head == NULL || (long)nd->tran->my_equiv_class <= (long)(*head)->tran_class) { tmp_head = getEquivList(); /* FIXed THIS ***** MAS *******/ tmp_head->tran_class = nd->tran->my_equiv_class; tmp_head->next = *head; *head = tmp_head; return; } done = 0; tmp_head = *head; while (!done) { if (tmp_head->next == NULL) { /* insert at tail of list */ tmp = getEquivList(); tmp->tran_class = nd->tran->my_equiv_class; tmp->next = NULL; tmp_head->next = tmp; done = 1; continue; } if ((long)nd->tran->my_equiv_class > (long)tmp_head->next->tran_class) { tmp_head = tmp_head->next; continue; } tmp = getEquivList(); /* FIXed THIS ***** MAS *******/ tmp->tran_class = nd->tran->my_equiv_class; tmp->next = tmp_head->next; tmp_head->next = tmp; done = 1; } /* check intermediate node */ /* insert in rest of list */ } static void generate_class(n, equiv_list) nodetype *n; equiv_list_type **equiv_list; { /* traverses all transistors attached to n, and puts all their pointers into a sorted list pointed to be equiv_list */ tran_list_type *scan; scan = n->trans; *equiv_list = NULL; while (scan != NULL) { /* could check to see if transistor is in valid class here */ add_to_list(scan, equiv_list); scan = scan->next; } } static nequivtype *find_equiv_(n, list) nodetype *n; nequivtype *list; { /* compare the equiv_list's of both 'n', and 'list', and return the class which has the same transistor equivalences */ char done, found; equiv_list_type *scan1, *scan2; found = 0; while (list != NULL && !found) { scan1 = n->equiv_list; scan2 = list->equiv_list; done = 0; while (scan1 != NULL && scan2 != NULL && !done) { if (scan1->tran_class != scan2->tran_class) { done = 1; found = 0; } else { scan1 = scan1->next; scan2 = scan2->next; } } if (scan1 == NULL && scan2 == NULL) found = 1; else list = list->next; } if (found) return list; else return NULL; } /************************************************************************/ /************************************************************************/ /************************************************************************/ /************************************************************************/ /*************** ************/ /*************** NODE STUFF BELOW..... ************/ /*************** ************/ /************************************************************************/ /************************************************************************/ /************************************************************************/ /************************************************************************/ static nequivtype *check_node_class(scan) nodetype *scan; { /* return a list of equivalence classes that the nodes pointed to by scan belong to */ nequivtype *tmp_head; nodetype *scannext; nequivtype *class_, *new_class; tmp_head = NULL; while (scan != NULL) { scannext = scan->next; reclaimEquivList(&scan->equiv_list); /* used to be scan^.equiv_list := nil */ generate_class(scan, &scan->equiv_list); class_ = find_equiv_(scan, tmp_head); if (class_ == NULL) { /* create new class */ new_class = getNEquiv(); new_class->nodes = scan; scan->next = NULL; scan->my_equiv_class = new_class; new_class->equiv_list = scan->equiv_list; add_nclass_to_list(new_class, &tmp_head); } else { /* reclaim scan^.equiv_list .... */ add_node_to_class(scan, &class_); } scan = scannext; } return tmp_head; } static void update_node_classes(head) nequivtype **head; { /* for each equivalence class of nodes, all nodes in the class are examined, and are broken into subclasses, depending on the equivalence classes of the transistors they touch. Each class is broken into a set of classes pointed to by tmp_class. These classes are examined at the end. Valid classes are broken off; invalid classes are re-aggregated, and flagged as bad. The resulting class(es) are placed in the nequiv list in the position originally occupied by the single class being considered. CALLS: check_node_class add_nclass_to_list add_node_to_class */ nequivtype *tmp_class, *bad_classes; /* my list of new classes, contains only bad classes */ nequivtype *single_bad_class; /* bad_classes aggregated into one class */ nequivtype *scan, *scannext; /* scans down the list passed by head */ nequivtype *scan2, *scan2next; /* scans down the temporary list returned by check_node_class */ nodetype *scan3, *scan4; /* scans down the node list in each temporary bad class */ scan = *head; while (scan != NULL) { /* consider each equivalence class; split into equivalence sub-classes */ scannext = scan->next; if (!(fast_mode && scan->good && scan->count == 2)) { remove_from_list(scan, head); tmp_class = check_node_class(scan->nodes); /* try to reclaim nequiv record */ scan->nodes = NULL; reclaim_node_class(&scan); /* MAS */ /* for each sub-class, check for validity; reamalgamate if invalid */ bad_classes = NULL; scan2 = tmp_class; while (scan2 != NULL) { scan2next = scan2->next; if (valid_node_class(scan2)) /* add to main list*/ add_nclass_to_list(scan2, &nequiv); else { if (allow_illegal_moves) add_nclass_to_list(scan2, &nequiv); else add_nclass_to_list(scan2, &bad_classes); } scan2 = scan2next; } /* now aggregate nodes in bad_classes into a single class */ single_bad_class = NULL; scan2 = bad_classes; /* will be nil if allow_illegal_moves */ while (scan2 != NULL) { scan2next = scan2->next; scan3 = scan2->nodes; while (scan3 != NULL) { scan4 = scan3->next; add_node_to_class(scan3, &single_bad_class); scan3 = scan4; } reclaim_node_class(&scan2); /* reclaim the nodes used */ scan2 = scan2next; } /* add this single bad class back to the main list, if it exists */ if (single_bad_class != NULL) { single_bad_class->good = 0; add_nclass_to_list(single_bad_class, &nequiv); } } /* process next equivalence class */ scan = scannext; } } static nequivtype *find_class_(pg, ng, ps, ns, head) long pg, ng, ps, ns; nequivtype *head; { /* returns the equivalence class with the correct pg,ng,ps,ns */ nequivtype *scan; char done; scan = head; done = 0; while (scan != NULL && !done) { if (scan->nodes->pg == pg && scan->nodes->ng == ng && scan->nodes->ps == ps && scan->nodes->ns == ns) done = 1; else scan = scan->next; } return scan; } static void initialize_nodes(head) nequivtype **head; { /* takes all the nodes, and partitions them into equivalence classes according to their fanout */ nodetype *scan, *scannext; nequivtype *class_, *new_class, *tmp_head, *scan_nclass, *scan_nclassnext; nodetype *node_scan, *node_scannext; nequivtype *single_bad_class; scan = (*head)->nodes; tmp_head = NULL; /* really want to reclaim the head node.....*/ while (scan != NULL) { scannext = scan->next; class_ = find_class_(scan->pg, scan->ng, scan->ps, scan->ns, tmp_head); if (class_ == NULL) /* make a new class */ { /* create new class */ new_class = getNEquiv(); new_class->nodes = scan; scan->next = NULL; scan->my_equiv_class = new_class; new_class->equiv_list = scan->equiv_list; add_nclass_to_list(new_class, &tmp_head); } else add_node_to_class(scan, &class_); scan = scannext; } /* above used to reference head instead of tmp_head */ /* now consider the elements in tmp_head, reassemble into head */ *head = NULL; scan_nclass = tmp_head; single_bad_class = NULL; while (scan_nclass != NULL) { scan_nclassnext = scan_nclass->next; remove_from_list(scan_nclass, &tmp_head); if (valid_node_class(scan_nclass)) add_nclass_to_list(scan_nclass, head); else { /* append to single_bad_list */ node_scan = scan_nclass->nodes; while (node_scan != NULL) { node_scannext = node_scan->next; add_node_to_class(node_scan, &single_bad_class); node_scan = node_scannext; } } scan_nclass = scan_nclassnext; } if (single_bad_class != NULL) { single_bad_class->good = 0; add_nclass_to_list(single_bad_class, head); } } #define iteration_limit 500 void compare_networks(automorphisms) char automorphisms; { /* accepts two equivalence-class lists ( a node list pointed to by nequiv, and a transistor list pointed to by tequiv), and iterates until no further legal moves are possible. CALLS: update_node_classes -- to update the node equivalence classes update_tran_classes -- to update the transistor eq. classes */ long iteration, old_tran_classes, new_tran_classes, old_node_classes, new_node_classes; if (dbug) { fprintf(outfyle, "************** AFTER PARSING *******************\n"); dump_data_structure(); } initialize_nodes(&nequiv); if (dbug) { fprintf(outfyle, "\n*************** AFTER initialize_nodes *************\n"); dump_data_structure(); } initialize_transistors(&tequiv); if (dbug) { fprintf(outfyle, "\n*************** AFTER initialize_trans *************\n"); dump_data_structure(); } iteration = 1; new_tran_classes = number_of_tran_classes(tequiv); new_node_classes = number_of_node_classes(nequiv); allow_illegal_moves = 0; do { old_tran_classes = new_tran_classes; old_node_classes = new_node_classes; no_legal_moves_done = 1; update_node_classes(&nequiv); if (dbug) { fprintf(outfyle, "\n*********** ITERATION: %ld result of: update_node **********\n", iteration); dump_data_structure(); fprintf(outfyle, "\n*********** ITERATION: %ld result of: update_tran **********\n", iteration); } update_tran_classes(&tequiv); if (dbug) dump_data_structure(); new_tran_classes = number_of_tran_classes(tequiv); new_node_classes = number_of_node_classes(nequiv); printf( "Iteration: %ld; Transistor classes = %ld (+%ld); Node classes = %ld (+%ld)\n", iteration, new_tran_classes, new_tran_classes - old_tran_classes, new_node_classes, new_node_classes - old_node_classes); print_memory(); fprintf(outfyle, "Iteration: %ld; Transistor classes = %ld (+%ld); Node classes = %ld (+%ld)\n", iteration, new_tran_classes, new_tran_classes - old_tran_classes, new_node_classes, new_node_classes - old_node_classes); iteration++; /* illegal_state (nequiv) or illegal_state (tequiv) or */ } while ((new_tran_classes != old_tran_classes || new_node_classes != old_node_classes) && iteration <= iteration_limit); /* we now have exhausted all legal moves */ /* perform one more iteration, and dump results */ if (iteration > iteration_limit) fprintf(outfyle, "ITERATION LIMIT EXCEEDED: %ld\n", (long)iteration_limit); allow_illegal_moves = 1; fprintf(outfyle, "************ results of fixed-point iteration **************\n"); printf("************ results of fixed-point iteration **************\n"); print_results(nequiv, tequiv, automorphisms); if (fast_mode) /* try to break things up */ return; update_node_classes(&nequiv); update_tran_classes(&tequiv); fprintf(outfyle, "************ results of allowing illegal moves **************\n"); printf("************ results of allowing illegal moves **************\n"); print_results(nequiv, tequiv, automorphisms); } #undef iteration_limit /* of module COMPARE */ /* End. */