source: vis_dev/glu-2.3/src/calBdd/calBddReorderTest.c @ 103

Last change on this file since 103 was 13, checked in by cecile, 13 years ago

library glu 2.3
File size: 8.1 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [calBddReorderTest.c]
4
5  PackageName [cal]
6
7  Synopsis    [A test routine for checking the functionality of
8  dynamic reordering.]
9
10  Description []
11
12  SeeAlso     [optional]
13
14  Author      [Wilsin Gosti    (wilsin@eecs.berkeley.edu)
15               Rajeev Ranjan   (rajeev@eecs.berkeley.edu)
16               Jagesh Sanghavi (sanghavi@eecs.berkeley.edu)
17               ]
18  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
19  All rights reserved.
20
21  Permission is hereby granted, without written agreement and without license
22  or royalty fees, to use, copy, modify, and distribute this software and its
23  documentation for any purpose, provided that the above copyright notice and
24  the following two paragraphs appear in all copies of this software.
25
26  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
27  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
28  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
29  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
32  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
33  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
34  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
35  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
36
37  Revision    [$Id: calBddReorderTest.c,v 1.1.1.4 1998/05/04 00:58:52 hsv Exp $]
38
39******************************************************************************/
40
41#include "calInt.h"
42
43/*---------------------------------------------------------------------------*/
44/* Constant declarations                                                     */
45/*---------------------------------------------------------------------------*/
46
47/*---------------------------------------------------------------------------*/
48/* Type declarations                                                         */
49/*---------------------------------------------------------------------------*/
50
51/*---------------------------------------------------------------------------*/
52/* Stucture declarations                                                     */
53/*---------------------------------------------------------------------------*/
54
55
56/*---------------------------------------------------------------------------*/
57/* Variable declarations                                                     */
58/*---------------------------------------------------------------------------*/
59static CalAddress_t asDoubleSpace[2];
60
61/*---------------------------------------------------------------------------*/
62/* Macro declarations                                                        */
63/*---------------------------------------------------------------------------*/
64
65#define CalBddReorderBddIsForwarded(bdd) \
66  (CAL_BDD_POINTER(CalBddGetElseBddNode(bdd)) == FORWARD_FLAG)
67
68#define CalBddReorderBddNodeIsForwarded(bddNode) \
69  (CAL_BDD_POINTER(CalBddNodeGetElseBddNode(bddNode)) == FORWARD_FLAG)
70
71#define CalBddReorderForward(bdd) \
72{ \
73  CalBddNode_t *_bddNode, *_bddNodeTagged; \
74  _bddNodeTagged = CalBddGetBddNode(bdd); \
75  _bddNode = CAL_BDD_POINTER(_bddNodeTagged); \
76  (bdd).bddId = _bddNode->thenBddId; \
77  (bdd).bddNode = (CalBddNode_t*) \
78                  (((CalAddress_t)(_bddNode->thenBddNode) & ~0xe) \
79                   ^(CAL_TAG0(_bddNodeTagged))); \
80}
81
82/**AutomaticStart*************************************************************/
83
84/*---------------------------------------------------------------------------*/
85/* Static function prototypes                                                */
86/*---------------------------------------------------------------------------*/
87
88static double cpuTime();
89static long elapsedTime();
90
91/**AutomaticEnd***************************************************************/
92
93/*---------------------------------------------------------------------------*/
94/* Definition of exported functions                                          */
95/*---------------------------------------------------------------------------*/
96
97
98/*---------------------------------------------------------------------------*/
99/* Definition of internal functions                                          */
100/*---------------------------------------------------------------------------*/
101
102/**Function********************************************************************
103
104  Synopsis    [required]
105
106  Description [optional]
107
108  SideEffects [required]
109
110  SeeAlso     [optional]
111
112******************************************************************************/
113int
114main(int argc, char **argv)
115{
116  Cal_Bdd expected;
117  Cal_Bdd a[100];
118  Cal_Bdd temp1;
119  Cal_Bdd temp2;
120  Cal_Bdd b, c, d, e, f, g, result;
121  Cal_BddManager_t *bddManager;
122  CalBddNode_t *bddNode;
123  int i;
124  int numVars;
125  int siftFlag = 0;
126 
127  if (argc == 1) {
128    numVars = 5;
129  } else if (argc >= 2) {
130    numVars = atoi(argv[1]);
131  }
132  if (argc == 3) {
133    siftFlag = 1;
134  }
135
136  bddManager = Cal_BddManagerInit();
137
138  for (i = 0; i < 2 * numVars; i++) {
139    a[i] = Cal_BddManagerCreateNewVarLast(bddManager);
140  }
141
142  result = Cal_BddZero(bddManager);
143  for (i = 0; i < numVars; i++) {
144    temp1 = Cal_BddAnd(bddManager, a[i], a[numVars + i]);
145    temp2 = Cal_BddOr(bddManager, result, temp1);
146    Cal_BddFree(bddManager, temp1);
147    Cal_BddFree(bddManager, result);
148    result = temp2;
149  }
150  Cal_BddManagerGC(bddManager);
151  Cal_BddStats(bddManager, stdout);
152  cpuTime();
153  elapsedTime();
154  printf("%%%%%%%%%%%% Reordering %%%%%%%%%%%%%%%%%%%\n");
155  if (siftFlag){
156    printf("Using Sift Technique\n");
157    Cal_BddDynamicReordering(bddManager, CAL_REORDER_SIFT);
158  }
159  else{
160    printf("Using Window Technique\n");
161    Cal_BddDynamicReordering(bddManager, CAL_REORDER_WINDOW);
162  }
163  Cal_BddReorder(bddManager);
164  printf("CPU time: %-8.2f\t Elapsed Time = %-10ld\n", cpuTime(), elapsedTime());
165  printf("%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%\n");
166  Cal_BddManagerGC(bddManager);
167  Cal_BddStats(bddManager, stdout);
168  /*Cal_BddFunctionPrint(bddManager, result, "Result");*/
169  temp1 = Cal_BddZero(bddManager);
170  for (i = 0; i < numVars; i++) {
171    temp2 = Cal_BddAnd(bddManager, a[i], a[numVars + i]);
172    expected = Cal_BddOr(bddManager, temp1, temp2);
173    Cal_BddFree(bddManager, temp1);
174    Cal_BddFree(bddManager, temp2);
175    temp1 = expected;
176  }
177
178  if (!Cal_BddIsEqual(bddManager, result, expected)) {
179    printf("ERROR: BDDs are not equal\n");
180    Cal_BddFunctionPrint(bddManager, result, "Result");
181    Cal_BddFunctionPrint(bddManager, expected, "Expected");
182  }
183  printf("\n%%%%%%BDDs are equal\n");
184  Cal_BddFree(bddManager, result);
185  Cal_BddFree(bddManager, expected);
186  Cal_BddManagerGC(bddManager);
187  Cal_BddStats(bddManager, stdout);
188  Cal_BddManagerQuit(bddManager);
189}
190
191
192/**Function********************************************************************
193
194  Synopsis    [required]
195
196  Description [optional]
197
198  SideEffects [required]
199
200  SeeAlso     [optional]
201
202******************************************************************************/
203static double
204cpuTime()
205{
206  static double timeNew, timeOld;
207  struct rusage rusage;
208  static flag = 0;
209
210  getrusage(RUSAGE_SELF, &rusage);
211  if (flag == 0){
212    timeOld = timeNew = rusage.ru_utime.tv_sec+
213        ((double)rusage.ru_utime.tv_usec)/1000000;
214    flag = 1;
215  }
216  else {
217    timeOld = timeNew;
218    timeNew = rusage.ru_utime.tv_sec+
219        ((float)rusage.ru_utime.tv_usec)/1000000;
220  }
221  return timeNew - timeOld;
222}
223
224/**Function********************************************************************
225
226  Synopsis    [Computes the time.]
227
228  Description [optional]
229
230  SideEffects [required]
231
232  SeeAlso     [optional]
233
234******************************************************************************/
235static long
236elapsedTime()
237{
238  static long time_new, time_old;
239  struct timeval t;
240  struct timezone tz;
241  static flag = 0;
242 
243  gettimeofday(&t, &tz);
244  if (flag == 0){
245    time_old = time_new = t.tv_sec;
246    flag = 1;
247  }
248  else {
249    time_old = time_new;
250    time_new =  t.tv_sec;
251  }
252  return time_new-time_old;
253}
Note: See TracBrowser for help on using the repository browser.