1 /**CFile***********************************************************************
7 Synopsis [Sanity check tests for some CUDD functions.]
9 Description [testcudd reads a matrix with real coefficients and
10 transforms it into an ADD. It then performs various operations on
11 the ADD and on the BDD corresponding to the ADD pattern. Finally,
12 testcudd tests functions relate to Walsh matrices and matrix
17 Author [Fabio Somenzi]
19 Copyright [Copyright (c) 1995-2004, Regents of the University of Colorado
23 Redistribution and use in source and binary forms, with or without
24 modification, are permitted provided that the following conditions
27 Redistributions of source code must retain the above copyright
28 notice, this list of conditions and the following disclaimer.
30 Redistributions in binary form must reproduce the above copyright
31 notice, this list of conditions and the following disclaimer in the
32 documentation and/or other materials provided with the distribution.
34 Neither the name of the University of Colorado nor the names of its
35 contributors may be used to endorse or promote products derived from
36 this software without specific prior written permission.
38 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
39 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
40 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
41 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
42 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
43 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
44 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
45 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
46 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
47 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
48 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
49 POSSIBILITY OF SUCH DAMAGE.]
51 ******************************************************************************/
57 /*---------------------------------------------------------------------------*/
58 /* Constant declarations */
59 /*---------------------------------------------------------------------------*/
61 #define TESTCUDD_VERSION "TestCudd Version #1.0, Release date 3/17/01"
63 /*---------------------------------------------------------------------------*/
64 /* Variable declarations */
65 /*---------------------------------------------------------------------------*/
68 static char rcsid
[] DD_UNUSED
= "$Id: testcudd.c,v 1.20 2009/03/08 02:49:02 fabio Exp $";
71 static const char *onames
[] = { "C", "M" }; /* names of functions to be dumped */
73 /**AutomaticStart*************************************************************/
75 /*---------------------------------------------------------------------------*/
76 /* Static function prototypes */
77 /*---------------------------------------------------------------------------*/
79 static void usage (char * prog
);
80 static FILE *open_file (char *filename
, const char *mode
);
81 static int testIterators (DdManager
*dd
, DdNode
*M
, DdNode
*C
, int pr
);
82 static int testXor (DdManager
*dd
, DdNode
*f
, int pr
, int nvars
);
83 static int testHamming (DdManager
*dd
, DdNode
*f
, int pr
);
84 static int testWalsh (DdManager
*dd
, int N
, int cmu
, int approach
, int pr
);
86 /**AutomaticEnd***************************************************************/
89 /**Function********************************************************************
91 Synopsis [Main function for testcudd.]
99 ******************************************************************************/
101 main(int argc
, char **argv
)
103 FILE *fp
; /* pointer to input file */
104 char *file
= (char *) ""; /* input file name */
105 FILE *dfp
= NULL
; /* pointer to dump file */
106 char *dfile
; /* file for DD dump */
107 DdNode
*dfunc
[2]; /* addresses of the functions to be dumped */
108 DdManager
*dd
; /* pointer to DD manager */
109 DdNode
*one
; /* fast access to constant function */
111 DdNode
**x
; /* pointers to variables */
112 DdNode
**y
; /* pointers to variables */
113 DdNode
**xn
; /* complements of row variables */
114 DdNode
**yn_
; /* complements of column variables */
117 DdNode
*C
; /* result of converting from ADD to BDD */
118 DdNode
*ess
; /* cube of essential variables */
119 DdNode
*shortP
; /* BDD cube of shortest path */
120 DdNode
*largest
; /* BDD of largest cube */
121 DdNode
*shortA
; /* ADD cube of shortest path */
122 DdNode
*constN
; /* value returned by evaluation of ADD */
123 DdNode
*ycube
; /* cube of the negated y vars for c-proj */
124 DdNode
*CP
; /* C-Projection of C */
125 DdNode
*CPr
; /* C-Selection of C */
126 int length
; /* length of the shortest path */
127 int nx
; /* number of variables */
134 int cmu
; /* use CMU multiplication */
135 int pr
; /* verbose printout level */
137 int multiple
; /* read multiple matrices */
139 int c
; /* variable to read in options */
140 int approach
; /* reordering approach */
141 int autodyn
; /* automatic reordering */
142 int groupcheck
; /* option for group sifting */
143 int profile
; /* print heap profile if != 0 */
144 int keepperm
; /* keep track of permutation */
145 int clearcache
; /* clear the cache after each matrix */
146 int blifOrDot
; /* dump format: 0 -> dot, 1 -> blif, ... */
147 int retval
; /* return value */
148 int i
; /* loop index */
149 long startTime
; /* initial time */
152 unsigned int cacheSize
, maxMemory
;
153 unsigned int nvars
,nslots
;
155 startTime
= util_cpu_time();
157 approach
= CUDD_REORDER_NONE
;
169 nslots
= CUDD_UNIQUE_SLOTS
;
171 groupcheck
= CUDD_GROUP_CHECK7
;
173 blifOrDot
= 0; /* dot format */
175 /* Parse command line. */
176 while ((c
= util_getopt(argc
, argv
, (char *) "CDHMPS:a:bcd:g:hkmn:p:v:x:X:"))
190 (void) mnem_setrecording(0);
197 nslots
= atoi(util_optarg
);
200 maxMemory
= atoi(util_optarg
);
203 approach
= atoi(util_optarg
);
206 blifOrDot
= 1; /* blif format */
215 groupcheck
= atoi(util_optarg
);
224 N
= atoi(util_optarg
);
227 pr
= atoi(util_optarg
);
230 nvars
= atoi(util_optarg
);
233 cacheSize
= atoi(util_optarg
);
242 if (argc
- util_optind
== 0) {
244 } else if (argc
- util_optind
== 1) {
245 file
= argv
[util_optind
];
249 if ((approach
<0) || (approach
>17)) {
250 (void) fprintf(stderr
,"Invalid approach: %d \n",approach
);
255 (void) printf("# %s\n", TESTCUDD_VERSION
);
256 /* Echo command line and arguments. */
258 for (i
= 0; i
< argc
; i
++) {
259 (void) printf(" %s", argv
[i
]);
262 (void) fflush(stdout
);
265 /* Initialize manager and provide easy reference to terminals. */
266 dd
= Cudd_Init(nvars
,0,nslots
,cacheSize
,maxMemory
);
268 dd
->groupcheck
= (Cudd_AggregationType
) groupcheck
;
269 if (autodyn
) Cudd_AutodynEnable(dd
,CUDD_REORDER_SAME
);
271 /* Open input file. */
272 fp
= open_file(file
, "r");
274 /* Open dump file if requested */
276 dfp
= open_file(dfile
, "w");
279 x
= y
= xn
= yn_
= NULL
;
281 /* We want to start anew for every matrix. */
283 nx
= maxnx
; ny
= maxny
;
284 if (pr
>0) lapTime
= util_cpu_time();
286 if (pr
>= 0) (void) printf(":name: ");
287 ok
= Cudd_addHarwell(fp
, dd
, &M
, &x
, &y
, &xn
, &yn_
, &nx
, &ny
,
288 &m
, &n
, 0, 2, 1, 2, pr
);
290 ok
= Cudd_addRead(fp
, dd
, &M
, &x
, &y
, &xn
, &yn_
, &nx
, &ny
,
293 (void) printf(":name: %s: %d rows %d columns\n", file
, m
, n
);
296 (void) fprintf(stderr
, "Error reading matrix\n");
300 if (nx
> maxnx
) maxnx
= nx
;
301 if (ny
> maxny
) maxny
= ny
;
303 /* Build cube of negated y's. */
306 for (i
= maxny
- 1; i
>= 0; i
--) {
308 tmpp
= Cudd_bddAnd(dd
,Cudd_Not(dd
->vars
[y
[i
]->index
]),ycube
);
309 if (tmpp
== NULL
) exit(2);
311 Cudd_RecursiveDeref(dd
,ycube
);
314 /* Initialize vectors of BDD variables used by priority func. */
315 xvars
= ALLOC(DdNode
*, nx
);
316 if (xvars
== NULL
) exit(2);
317 for (i
= 0; i
< nx
; i
++) {
318 xvars
[i
] = dd
->vars
[x
[i
]->index
];
320 yvars
= ALLOC(DdNode
*, ny
);
321 if (yvars
== NULL
) exit(2);
322 for (i
= 0; i
< ny
; i
++) {
323 yvars
[i
] = dd
->vars
[y
[i
]->index
];
327 for (i
=0; i
< maxnx
; i
++) {
328 Cudd_RecursiveDeref(dd
, x
[i
]);
329 Cudd_RecursiveDeref(dd
, xn
[i
]);
333 for (i
=0; i
< maxny
; i
++) {
334 Cudd_RecursiveDeref(dd
, y
[i
]);
335 Cudd_RecursiveDeref(dd
, yn_
[i
]);
340 if (pr
>0) {(void) printf(":1: M"); Cudd_PrintDebug(dd
,M
,nx
+ny
,pr
);}
342 if (pr
>0) (void) printf(":2: time to read the matrix = %s\n",
343 util_print_time(util_cpu_time() - lapTime
));
345 C
= Cudd_addBddPattern(dd
, M
);
348 if (pr
>0) {(void) printf(":3: C"); Cudd_PrintDebug(dd
,C
,nx
+ny
,pr
);}
350 /* Test iterators. */
351 retval
= testIterators(dd
,M
,C
,pr
);
352 if (retval
== 0) exit(2);
354 cuddCacheProfile(dd
,stdout
);
357 retval
= testXor(dd
,C
,pr
,nx
+ny
);
358 if (retval
== 0) exit(2);
360 /* Test Hamming distance functions. */
361 retval
= testHamming(dd
,C
,pr
);
362 if (retval
== 0) exit(2);
364 /* Test selection functions. */
365 CP
= Cudd_CProjection(dd
,C
,ycube
);
366 if (CP
== NULL
) exit(2);
368 if (pr
>0) {(void) printf("ycube"); Cudd_PrintDebug(dd
,ycube
,nx
+ny
,pr
);}
369 if (pr
>0) {(void) printf("CP"); Cudd_PrintDebug(dd
,CP
,nx
+ny
,pr
);}
372 CPr
= Cudd_PrioritySelect(dd
,C
,xvars
,yvars
,(DdNode
**)NULL
,
373 (DdNode
*)NULL
,ny
,Cudd_Xgty
);
374 if (CPr
== NULL
) exit(2);
376 if (pr
>0) {(void) printf(":4: CPr"); Cudd_PrintDebug(dd
,CPr
,nx
+ny
,pr
);}
378 (void) printf("CP != CPr!\n");
380 Cudd_RecursiveDeref(dd
, CPr
);
383 /* Test inequality generator. */
385 int Nmin
= ddMin(nx
,ny
);
389 DdNode
*f
= Cudd_Inequality(dd
,Nmin
,2,xvars
,yvars
);
390 if (f
== NULL
) exit(2);
393 (void) printf(":4: ineq");
394 Cudd_PrintDebug(dd
,f
,nx
+ny
,pr
);
396 Cudd_ForeachPrime(dd
,Cudd_Not(f
),Cudd_Not(f
),gen
,cube
) {
397 for (q
= 0; q
< dd
->size
; q
++) {
412 (void) printf(" 1\n");
417 Cudd_IterDerefBdd(dd
, f
);
419 FREE(xvars
); FREE(yvars
);
421 Cudd_RecursiveDeref(dd
, CP
);
422 Cudd_RecursiveDeref(dd
, ycube
);
424 /* Test functions for essential variables. */
425 ess
= Cudd_FindEssential(dd
,C
);
426 if (ess
== NULL
) exit(2);
428 if (pr
>0) {(void) printf(":4: ess"); Cudd_PrintDebug(dd
,ess
,nx
+ny
,pr
);}
429 Cudd_RecursiveDeref(dd
, ess
);
431 /* Test functions for shortest paths. */
432 shortP
= Cudd_ShortestPath(dd
, M
, NULL
, NULL
, &length
);
433 if (shortP
== NULL
) exit(2);
436 (void) printf(":5: shortP"); Cudd_PrintDebug(dd
,shortP
,nx
+ny
,pr
);
438 /* Test functions for largest cubes. */
439 largest
= Cudd_LargestCube(dd
, Cudd_Not(C
), &length
);
440 if (largest
== NULL
) exit(2);
443 (void) printf(":5b: largest");
444 Cudd_PrintDebug(dd
,largest
,nx
+ny
,pr
);
446 Cudd_RecursiveDeref(dd
, largest
);
448 /* Test Cudd_addEvalConst and Cudd_addIteConstant. */
449 shortA
= Cudd_BddToAdd(dd
,shortP
);
450 if (shortA
== NULL
) exit(2);
452 Cudd_RecursiveDeref(dd
, shortP
);
453 constN
= Cudd_addEvalConst(dd
,shortA
,M
);
454 if (constN
== DD_NON_CONSTANT
) exit(2);
455 if (Cudd_addIteConstant(dd
,shortA
,M
,constN
) != constN
) exit(2);
456 if (pr
>0) {(void) printf("The value of M along the chosen shortest path is %g\n", cuddV(constN
));}
457 Cudd_RecursiveDeref(dd
, shortA
);
459 shortP
= Cudd_ShortestPath(dd
, C
, NULL
, NULL
, &length
);
460 if (shortP
== NULL
) exit(2);
463 (void) printf(":6: shortP"); Cudd_PrintDebug(dd
,shortP
,nx
+ny
,pr
);
466 /* Test Cudd_bddIteConstant and Cudd_bddLeq. */
467 if (!Cudd_bddLeq(dd
,shortP
,C
)) exit(2);
468 if (Cudd_bddIteConstant(dd
,Cudd_Not(shortP
),one
,C
) != one
) exit(2);
469 Cudd_RecursiveDeref(dd
, shortP
);
472 retval
= cuddHeapProfile(dd
);
478 (void) printf("Average distance: %g\n", Cudd_AverageDistance(dd
));
481 /* Reorder if so requested. */
482 if (approach
!= CUDD_REORDER_NONE
) {
484 retval
= Cudd_EnableReorderingReporting(dd
);
486 (void) fprintf(stderr
,"Error reported by Cudd_EnableReorderingReporting\n");
491 retval
= Cudd_DebugCheck(dd
);
493 (void) fprintf(stderr
,"Error reported by Cudd_DebugCheck\n");
496 retval
= Cudd_CheckKeys(dd
);
498 (void) fprintf(stderr
,"Error reported by Cudd_CheckKeys\n");
502 retval
= Cudd_ReduceHeap(dd
,(Cudd_ReorderingType
)approach
,5);
504 (void) fprintf(stderr
,"Error reported by Cudd_ReduceHeap\n");
508 retval
= Cudd_DisableReorderingReporting(dd
);
510 (void) fprintf(stderr
,"Error reported by Cudd_DisableReorderingReporting\n");
515 retval
= Cudd_DebugCheck(dd
);
517 (void) fprintf(stderr
,"Error reported by Cudd_DebugCheck\n");
520 retval
= Cudd_CheckKeys(dd
);
522 (void) fprintf(stderr
,"Error reported by Cudd_CheckKeys\n");
526 if (approach
== CUDD_REORDER_SYMM_SIFT
||
527 approach
== CUDD_REORDER_SYMM_SIFT_CONV
) {
528 Cudd_SymmProfile(dd
,0,dd
->size
-1);
532 (void) printf("Average distance: %g\n", Cudd_AverageDistance(dd
));
536 /* Print variable permutation. */
537 (void) printf("Variable Permutation:");
538 for (i
=0; i
<size
; i
++) {
539 if (i
%20 == 0) (void) printf("\n");
540 (void) printf("%d ", dd
->invperm
[i
]);
543 (void) printf("Inverse Permutation:");
544 for (i
=0; i
<size
; i
++) {
545 if (i
%20 == 0) (void) printf("\n");
546 (void) printf("%d ", dd
->perm
[i
]);
551 if (pr
>0) {(void) printf("M"); Cudd_PrintDebug(dd
,M
,nx
+ny
,pr
);}
554 retval
= cuddHeapProfile(dd
);
559 /* Dump DDs of C and M if so requested. */
563 if (blifOrDot
== 1) {
564 /* Only dump C because blif cannot handle ADDs */
565 retval
= Cudd_DumpBlif(dd
,1,dfunc
,NULL
,(char **)onames
,
568 retval
= Cudd_DumpDot(dd
,2,dfunc
,NULL
,(char **)onames
,dfp
);
571 (void) fprintf(stderr
,"abnormal termination\n");
576 Cudd_RecursiveDeref(dd
, C
);
577 Cudd_RecursiveDeref(dd
, M
);
580 if (pr
>0) {(void) printf("Clearing the cache... ");}
581 for (i
= dd
->cacheSlots
- 1; i
>=0; i
--) {
582 dd
->cache
[i
].data
= NIL(DdNode
);
584 if (pr
>0) {(void) printf("done\n");}
587 (void) printf("Number of variables = %6d\t",dd
->size
);
588 (void) printf("Number of slots = %6u\n",dd
->slots
);
589 (void) printf("Number of keys = %6u\t",dd
->keys
);
590 (void) printf("Number of min dead = %6u\n",dd
->minDead
);
593 } while (multiple
&& !feof(fp
));
600 /* Second phase: experiment with Walsh matrices. */
601 if (!testWalsh(dd
,N
,cmu
,approach
,pr
)) {
605 /* Check variable destruction. */
606 assert(cuddDestroySubtables(dd
,3));
607 assert(Cudd_DebugCheck(dd
) == 0);
608 assert(Cudd_CheckKeys(dd
) == 0);
610 retval
= Cudd_CheckZeroRef(dd
);
611 ok
= retval
!= 0; /* ok == 0 means O.K. */
613 (void) fprintf(stderr
,
614 "%d non-zero DD reference counts after dereferencing\n", retval
);
618 (void) Cudd_PrintInfo(dd
,stdout
);
627 if (pr
>0) (void) printf("total time = %s\n",
628 util_print_time(util_cpu_time() - startTime
));
630 if (pr
>= 0) util_print_cpu_stats(stdout
);
637 /*---------------------------------------------------------------------------*/
638 /* Definition of static functions */
639 /*---------------------------------------------------------------------------*/
642 /**Function********************************************************************
644 Synopsis [Prints usage info for testcudd.]
652 ******************************************************************************/
656 (void) fprintf(stderr
, "usage: %s [options] [file]\n", prog
);
657 (void) fprintf(stderr
, " -C\t\tuse CMU multiplication algorithm\n");
658 (void) fprintf(stderr
, " -D\t\tenable automatic dynamic reordering\n");
659 (void) fprintf(stderr
, " -H\t\tread matrix in Harwell format\n");
660 (void) fprintf(stderr
, " -M\t\tturns off memory allocation recording\n");
661 (void) fprintf(stderr
, " -P\t\tprint BDD heap profile\n");
662 (void) fprintf(stderr
, " -S n\t\tnumber of slots for each subtable\n");
663 (void) fprintf(stderr
, " -X n\t\ttarget maximum memory in bytes\n");
664 (void) fprintf(stderr
, " -a n\t\tchoose reordering approach (0-13)\n");
665 (void) fprintf(stderr
, " \t\t\t0: same as autoMethod\n");
666 (void) fprintf(stderr
, " \t\t\t1: no reordering (default)\n");
667 (void) fprintf(stderr
, " \t\t\t2: random\n");
668 (void) fprintf(stderr
, " \t\t\t3: pivot\n");
669 (void) fprintf(stderr
, " \t\t\t4: sifting\n");
670 (void) fprintf(stderr
, " \t\t\t5: sifting to convergence\n");
671 (void) fprintf(stderr
, " \t\t\t6: symmetric sifting\n");
672 (void) fprintf(stderr
, " \t\t\t7: symmetric sifting to convergence\n");
673 (void) fprintf(stderr
, " \t\t\t8-10: window of size 2-4\n");
674 (void) fprintf(stderr
, " \t\t\t11-13: window of size 2-4 to conv.\n");
675 (void) fprintf(stderr
, " \t\t\t14: group sifting\n");
676 (void) fprintf(stderr
, " \t\t\t15: group sifting to convergence\n");
677 (void) fprintf(stderr
, " \t\t\t16: simulated annealing\n");
678 (void) fprintf(stderr
, " \t\t\t17: genetic algorithm\n");
679 (void) fprintf(stderr
, " -b\t\tuse blif as format for dumps\n");
680 (void) fprintf(stderr
, " -c\t\tclear the cache after each matrix\n");
681 (void) fprintf(stderr
, " -d file\tdump DDs to file\n");
682 (void) fprintf(stderr
, " -g\t\tselect aggregation criterion (0,5,7)\n");
683 (void) fprintf(stderr
, " -h\t\tprints this message\n");
684 (void) fprintf(stderr
, " -k\t\tprint the variable permutation\n");
685 (void) fprintf(stderr
, " -m\t\tread multiple matrices (only with -H)\n");
686 (void) fprintf(stderr
, " -n n\t\tnumber of variables\n");
687 (void) fprintf(stderr
, " -p n\t\tcontrol verbosity\n");
688 (void) fprintf(stderr
, " -v n\t\tinitial variables in the unique table\n");
689 (void) fprintf(stderr
, " -x n\t\tinitial size of the cache\n");
694 /**Function********************************************************************
696 Synopsis [Opens a file.]
698 Description [Opens a file, or fails with an error message and exits.
699 Allows '-' as a synonym for standard input.]
705 ******************************************************************************/
707 open_file(char *filename
, const char *mode
)
711 if (strcmp(filename
, "-") == 0) {
712 return mode
[0] == 'r' ? stdin
: stdout
;
713 } else if ((fp
= fopen(filename
, mode
)) == NULL
) {
719 } /* end of open_file */
722 /**Function********************************************************************
724 Synopsis [Tests Walsh matrix multiplication.]
726 Description [Tests Walsh matrix multiplication. Return 1 if successful;
729 SideEffects [May create new variables in the manager.]
733 ******************************************************************************/
736 DdManager
*dd
/* manager */,
737 int N
/* number of variables */,
738 int cmu
/* use CMU approach to matrix multiplication */,
739 int approach
/* reordering approach */,
740 int pr
/* verbosity level */)
742 DdNode
*walsh1
, *walsh2
, *wtw
;
743 DdNode
**x
, **v
, **z
;
745 DdNode
*one
= DD_ONE(dd
);
746 DdNode
*zero
= DD_ZERO(dd
);
749 x
= ALLOC(DdNode
*,N
);
750 v
= ALLOC(DdNode
*,N
);
751 z
= ALLOC(DdNode
*,N
);
753 for (i
= N
-1; i
>= 0; i
--) {
754 Cudd_Ref(x
[i
]=cuddUniqueInter(dd
,3*i
,one
,zero
));
755 Cudd_Ref(v
[i
]=cuddUniqueInter(dd
,3*i
+1,one
,zero
));
756 Cudd_Ref(z
[i
]=cuddUniqueInter(dd
,3*i
+2,one
,zero
));
758 Cudd_Ref(walsh1
= Cudd_addWalsh(dd
,v
,z
,N
));
759 if (pr
>0) {(void) printf("walsh1"); Cudd_PrintDebug(dd
,walsh1
,2*N
,pr
);}
760 Cudd_Ref(walsh2
= Cudd_addWalsh(dd
,x
,v
,N
));
762 Cudd_Ref(wtw
= Cudd_addTimesPlus(dd
,walsh2
,walsh1
,v
,N
));
764 Cudd_Ref(wtw
= Cudd_addMatrixMultiply(dd
,walsh2
,walsh1
,v
,N
));
766 if (pr
>0) {(void) printf("wtw"); Cudd_PrintDebug(dd
,wtw
,2*N
,pr
);}
768 if (approach
!= CUDD_REORDER_NONE
) {
770 retval
= Cudd_DebugCheck(dd
);
772 (void) fprintf(stderr
,"Error reported by Cudd_DebugCheck\n");
776 retval
= Cudd_ReduceHeap(dd
,(Cudd_ReorderingType
)approach
,5);
778 (void) fprintf(stderr
,"Error reported by Cudd_ReduceHeap\n");
782 retval
= Cudd_DebugCheck(dd
);
784 (void) fprintf(stderr
,"Error reported by Cudd_DebugCheck\n");
788 if (approach
== CUDD_REORDER_SYMM_SIFT
||
789 approach
== CUDD_REORDER_SYMM_SIFT_CONV
) {
790 Cudd_SymmProfile(dd
,0,dd
->size
-1);
794 Cudd_RecursiveDeref(dd
, wtw
);
795 Cudd_RecursiveDeref(dd
, walsh1
);
796 Cudd_RecursiveDeref(dd
, walsh2
);
797 for (i
=0; i
< N
; i
++) {
798 Cudd_RecursiveDeref(dd
, x
[i
]);
799 Cudd_RecursiveDeref(dd
, v
[i
]);
800 Cudd_RecursiveDeref(dd
, z
[i
]);
808 } /* end of testWalsh */
810 /**Function********************************************************************
812 Synopsis [Tests iterators.]
814 Description [Tests iterators on cubes and nodes.]
820 ******************************************************************************/
829 CUDD_VALUE_TYPE value
;
833 /* Test iterator for cubes. */
835 (void) printf("Testing iterator on cubes:\n");
836 Cudd_ForeachCube(dd
,M
,gen
,cube
,value
) {
837 for (q
= 0; q
< dd
->size
; q
++) {
852 (void) printf(" %g\n",value
);
858 (void) printf("Testing prime expansion of cubes:\n");
859 if (!Cudd_bddPrintCover(dd
,C
,C
)) return(0);
863 (void) printf("Testing iterator on primes (CNF):\n");
864 Cudd_ForeachPrime(dd
,Cudd_Not(C
),Cudd_Not(C
),gen
,cube
) {
865 for (q
= 0; q
< dd
->size
; q
++) {
880 (void) printf(" 1\n");
885 /* Test iterator on nodes. */
888 (void) printf("Testing iterator on nodes:\n");
889 Cudd_ForeachNode(dd
,M
,gen
,node
) {
890 if (Cudd_IsConstant(node
)) {
891 #if SIZEOF_VOID_P == 8
892 (void) printf("ID = 0x%lx\tvalue = %-9g\n",
894 (ptruint
) sizeof(DdNode
),
897 (void) printf("ID = 0x%x\tvalue = %-9g\n",
899 (ptruint
) sizeof(DdNode
),
903 #if SIZEOF_VOID_P == 8
904 (void) printf("ID = 0x%lx\tindex = %u\tr = %u\n",
906 (ptruint
) sizeof(DdNode
),
907 node
->index
, node
->ref
);
909 (void) printf("ID = 0x%x\tindex = %u\tr = %u\n",
911 (ptruint
) sizeof(DdNode
),
912 node
->index
, node
->ref
);
920 } /* end of testIterators */
923 /**Function********************************************************************
925 Synopsis [Tests the functions related to the exclusive OR.]
927 Description [Tests the functions related to the exclusive OR. It
928 builds the boolean difference of the given function in three
929 different ways and checks that the results is the same. Returns 1 if
930 successful; 0 otherwise.]
936 ******************************************************************************/
938 testXor(DdManager
*dd
, DdNode
*f
, int pr
, int nvars
)
940 DdNode
*f1
, *f0
, *res1
, *res2
;
943 /* Extract cofactors w.r.t. mid variable. */
945 f1
= Cudd_Cofactor(dd
,f
,dd
->vars
[x
]);
946 if (f1
== NULL
) return(0);
949 f0
= Cudd_Cofactor(dd
,f
,Cudd_Not(dd
->vars
[x
]));
951 Cudd_RecursiveDeref(dd
,f1
);
956 /* Compute XOR of cofactors with ITE. */
957 res1
= Cudd_bddIte(dd
,f1
,Cudd_Not(f0
),f0
);
958 if (res1
== NULL
) return(0);
961 if (pr
>0) {(void) printf("xor1"); Cudd_PrintDebug(dd
,res1
,nvars
,pr
);}
963 /* Compute XOR of cofactors with XOR. */
964 res2
= Cudd_bddXor(dd
,f1
,f0
);
966 Cudd_RecursiveDeref(dd
,res1
);
972 if (pr
>0) {(void) printf("xor2"); Cudd_PrintDebug(dd
,res2
,nvars
,pr
);}
973 Cudd_RecursiveDeref(dd
,res1
);
974 Cudd_RecursiveDeref(dd
,res2
);
977 Cudd_RecursiveDeref(dd
,res1
);
978 Cudd_RecursiveDeref(dd
,f1
);
979 Cudd_RecursiveDeref(dd
,f0
);
981 /* Compute boolean difference directly. */
982 res1
= Cudd_bddBooleanDiff(dd
,f
,x
);
984 Cudd_RecursiveDeref(dd
,res2
);
990 if (pr
>0) {(void) printf("xor3"); Cudd_PrintDebug(dd
,res1
,nvars
,pr
);}
991 Cudd_RecursiveDeref(dd
,res1
);
992 Cudd_RecursiveDeref(dd
,res2
);
995 Cudd_RecursiveDeref(dd
,res1
);
996 Cudd_RecursiveDeref(dd
,res2
);
999 } /* end of testXor */
1002 /**Function********************************************************************
1004 Synopsis [Tests the Hamming distance functions.]
1006 Description [Tests the Hammming distance functions. Returns
1007 1 if successful; 0 otherwise.]
1013 ******************************************************************************/
1020 DdNode
**vars
, *minBdd
, *zero
, *scan
;
1024 int size
= Cudd_ReadSize(dd
);
1026 vars
= ALLOC(DdNode
*, size
);
1027 if (vars
== NULL
) return(0);
1028 for (i
= 0; i
< size
; i
++) {
1029 vars
[i
] = Cudd_bddIthVar(dd
,i
);
1032 minBdd
= Cudd_bddPickOneMinterm(dd
,Cudd_Not(f
),vars
,size
);
1035 (void) printf("Chosen minterm for Hamming distance test: ");
1036 Cudd_PrintDebug(dd
,minBdd
,size
,pr
);
1039 minterm
= ALLOC(int,size
);
1040 if (minterm
== NULL
) {
1042 Cudd_RecursiveDeref(dd
,minBdd
);
1046 zero
= Cudd_Not(DD_ONE(dd
));
1047 while (!Cudd_IsConstant(scan
)) {
1048 DdNode
*R
= Cudd_Regular(scan
);
1049 DdNode
*T
= Cudd_T(R
);
1050 DdNode
*E
= Cudd_E(R
);
1056 minterm
[R
->index
] = 0;
1059 minterm
[R
->index
] = 1;
1063 Cudd_RecursiveDeref(dd
,minBdd
);
1065 d
= Cudd_MinHammingDist(dd
,f
,minterm
,size
);
1067 (void) printf("Minimum Hamming distance = %d\n", d
);
1073 } /* end of testHamming */