1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
|
/*
* Revision Control Information
*
* $Source$
* $Author$
* $Revision$
* $Date$
*
*/
/*
module: essen.c
purpose: Find essential primes in a multiple-valued function
*/
#include "espresso.h"
ABC_NAMESPACE_IMPL_START
/*
essential -- return a cover consisting of the cubes of F which are
essential prime implicants (with respect to F u D); Further, remove
these cubes from the ON-set F, and add them to the OFF-set D.
Sometimes EXPAND can determine that a cube is not an essential prime.
If so, it will set the "NONESSEN" flag in the cube.
We count on IRREDUNDANT to have set the flag RELESSEN to indicate
that a prime was relatively essential (i.e., covers some minterm
not contained in any other prime in the current cover), or to have
reset the flag to indicate that a prime was relatively redundant
(i.e., all minterms covered by other primes in the current cover).
Of course, after executing irredundant, all of the primes in the
cover are relatively essential, but we can mark the primes which
were redundant at the start of irredundant and avoid an extra check
on these primes for essentiality.
*/
pcover essential(Fp, Dp)
IN pcover *Fp, *Dp;
{
register pcube last, p;
pcover E, F = *Fp, D = *Dp;
/* set all cubes in F active */
(void) sf_active(F);
/* Might as well start out with some cubes in E */
E = new_cover(10);
foreach_set(F, last, p) {
/* don't test a prime which EXPAND says is nonessential */
if (! TESTP(p, NONESSEN)) {
/* only test a prime which was relatively essential */
if (TESTP(p, RELESSEN)) {
/* Check essentiality */
if (essen_cube(F, D, p)) {
if (debug & ESSEN)
printf("ESSENTIAL: %s\n", pc1(p));
E = sf_addset(E, p);
RESET(p, ACTIVE);
F->active_count--;
}
}
}
}
*Fp = sf_inactive(F); /* delete the inactive cubes from F */
*Dp = sf_join(D, E); /* add the essentials to D */
sf_free(D);
return E;
}
/*
essen_cube -- check if a single cube is essential or not
The prime c is essential iff
consensus((F u D) # c, c) u D
does not contain c.
*/
bool essen_cube(F, D, c)
IN pcover F, D;
IN pcube c;
{
pcover H, FD;
pcube *H1;
bool essen;
/* Append F and D together, and take the sharp-consensus with c */
FD = sf_join(F, D);
H = cb_consensus(FD, c);
free_cover(FD);
/* Add the don't care set, and see if this covers c */
H1 = cube2list(H, D);
essen = ! cube_is_covered(H1, c);
free_cubelist(H1);
free_cover(H);
return essen;
}
/*
* cb_consensus -- compute consensus(T # c, c)
*/
pcover cb_consensus(T, c)
register pcover T;
register pcube c;
{
register pcube temp, last, p;
register pcover R;
R = new_cover(T->count*2);
temp = new_cube();
foreach_set(T, last, p) {
if (p != c) {
switch (cdist01(p, c)) {
case 0:
/* distance-0 needs special care */
R = cb_consensus_dist0(R, p, c);
break;
case 1:
/* distance-1 is easy because no sharping required */
consensus(temp, p, c);
R = sf_addset(R, temp);
break;
}
}
}
set_free(temp);
return R;
}
/*
* form the sharp-consensus for p and c when they intersect
* What we are forming is consensus(p # c, c).
*/
pcover cb_consensus_dist0(R, p, c)
pcover R;
register pcube p, c;
{
int var;
bool got_one;
register pcube temp, mask;
register pcube p_diff_c=cube.temp[0], p_and_c=cube.temp[1];
/* If c contains p, then this gives us no information for essential test */
if (setp_implies(p, c)) {
return R;
}
/* For the multiple-valued variables */
temp = new_cube();
got_one = FALSE;
INLINEset_diff(p_diff_c, p, c);
INLINEset_and(p_and_c, p, c);
for(var = cube.num_binary_vars; var < cube.num_vars; var++) {
/* Check if c(var) is contained in p(var) -- if so, no news */
mask = cube.var_mask[var];
if (! setp_disjoint(p_diff_c, mask)) {
INLINEset_merge(temp, c, p_and_c, mask);
R = sf_addset(R, temp);
got_one = TRUE;
}
}
/* if no cube so far, add one for the intersection */
if (! got_one && cube.num_binary_vars > 0) {
/* Add a single cube for the intersection of p and c */
INLINEset_and(temp, p, c);
R = sf_addset(R, temp);
}
set_free(temp);
return R;
}
ABC_NAMESPACE_IMPL_END
|
