summaryrefslogtreecommitdiffstats
path: root/src/misc/espresso/reduce.c
blob: 00e4507f23e3a6c1ff6b2279e7b687edfe08d9fe (plain)
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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
/*
 * Revision Control Information
 *
 * $Source$
 * $Author$
 * $Revision$
 * $Date$
 *
 */
/*
    module: reduce.c
    purpose: Perform the Espresso-II reduction step

    Reduction is a technique used to explore larger regions of the
    optimization space.  We replace each cube of F with a smaller
    cube while still maintaining a cover of the same logic function.
*/

#include "espresso.h"

static bool toggle = TRUE;


/*
    reduce -- replace each cube in F with its reduction

    The reduction of a cube is the smallest cube contained in the cube
    which can replace the cube in the original cover without changing
    the cover.  This is equivalent to the super cube of all of the
    essential points in the cube.  This can be computed directly.

    The problem is that the order in which the cubes are reduced can
    greatly affect the final result.  We alternate between two ordering
    strategies:

    (1) Order the cubes in ascending order of distance from the
    largest cube breaking ties by ordering cubes of equal distance
    in descending order of size (sort_reduce)

    (2) Order the cubes in descending order of the inner-product of
    the cube and the column sums (mini_sort)

    The real workhorse of this section is the routine SCCC which is
    used to find the Smallest Cube Containing the Complement of a cover.
    Reduction as proposed by Espresso-II takes a cube and computes its
    maximal reduction as the intersection between the cube and the
    smallest cube containing the complement of (F u D - {c}) cofactored
    against c.

    As usual, the unate-recursive paradigm is used to compute SCCC.
    The SCCC of a unate cover is trivial to compute, and thus we perform
    Shannon Cofactor expansion attempting to drive the cover to be unate
    as fast as possible.
*/

pcover reduce(F, D)
INOUT pcover F;
IN pcover D;
{
    register pcube last, p, cunder, *FD;

    /* Order the cubes */
    if (use_random_order)
    F = random_order(F);
    else {
    F = toggle ? sort_reduce(F) : mini_sort(F, descend);
    toggle = ! toggle;
    }

    /* Try to reduce each cube */
    FD = cube2list(F, D);
    foreach_set(F, last, p) {
    cunder = reduce_cube(FD, p);        /* reduce the cube */
    if (setp_equal(cunder, p)) {            /* see if it actually did */
        SET(p, ACTIVE);    /* cube remains active */
        SET(p, PRIME);    /* cube remains prime ? */
    } else {
        if (debug & REDUCE) {
        printf("REDUCE: %s to %s %s\n",
            pc1(p), pc2(cunder), print_time(ptime()));
        }
        set_copy(p, cunder);                /* save reduced version */
        RESET(p, PRIME);                    /* cube is no longer prime */
        if (setp_empty(cunder))
        RESET(p, ACTIVE);               /* if null, kill the cube */
        else
        SET(p, ACTIVE);                 /* cube is active */
    }
    free_cube(cunder);
    }
    free_cubelist(FD);

    /* Delete any cubes of F which reduced to the empty cube */
    return sf_inactive(F);
}

/* reduce_cube -- find the maximal reduction of a cube */
pcube reduce_cube(FD, p)
IN pcube *FD, p;
{
    pcube cunder;

    cunder = sccc(cofactor(FD, p));
    return set_and(cunder, cunder, p);
}


/* sccc -- find Smallest Cube Containing the Complement of a cover */
pcube sccc(T)
INOUT pcube *T;         /* T will be disposed of */
{
    pcube r;
    register pcube cl, cr;
    register int best;
    static int sccc_level = 0;

    if (debug & REDUCE1) {
    debug_print(T, "SCCC", sccc_level++);
    }

    if (sccc_special_cases(T, &r) == MAYBE) {
    cl = new_cube();
    cr = new_cube();
    best = binate_split_select(T, cl, cr, REDUCE1);
    r = sccc_merge(sccc(scofactor(T, cl, best)),
               sccc(scofactor(T, cr, best)), cl, cr);
    free_cubelist(T);
    }

    if (debug & REDUCE1)
    printf("SCCC[%d]: result is %s\n", --sccc_level, pc1(r));
    return r;
}


pcube sccc_merge(left, right, cl, cr)
INOUT register pcube left, right;       /* will be disposed of ... */
INOUT register pcube cl, cr;            /* will be disposed of ... */
{
    INLINEset_and(left, left, cl);
    INLINEset_and(right, right, cr);
    INLINEset_or(left, left, right);
    free_cube(right);
    free_cube(cl);
    free_cube(cr);
    return left;
}


/*
    sccc_cube -- find the smallest cube containing the complement of a cube

    By DeMorgan's law and the fact that the smallest cube containing a
    cover is the "or" of the positional cubes, it is simple to see that
    the SCCC is the universe if the cube has more than two active
    variables.  If there is only a single active variable, then the
    SCCC is merely the bitwise complement of the cube in that
    variable.  A last special case is no active variables, in which
    case the SCCC is empty.

    This is "anded" with the incoming cube result.
*/
pcube sccc_cube(result, p)
register pcube result, p;
{
    register pcube temp=cube.temp[0], mask;
    int var;

    if ((var = cactive(p)) >= 0) {
    mask = cube.var_mask[var];
    INLINEset_xor(temp, p, mask);
    INLINEset_and(result, result, temp);
    }
    return result;
}

/*
 *   sccc_special_cases -- check the special cases for sccc
 */

bool sccc_special_cases(T, result)
INOUT pcube *T;                 /* will be disposed if answer is determined */
OUT pcube *result;              /* returned only if answer determined */
{
    register pcube *T1, p, temp = cube.temp[1], ceil, cof = T[0];
    pcube *A, *B;

    /* empty cover => complement is universe => SCCC is universe */
    if (T[2] == NULL) {
    *result = set_save(cube.fullset);
    free_cubelist(T);
    return TRUE;
    }

    /* row of 1's => complement is empty => SCCC is empty */
    for(T1 = T+2; (p = *T1++) != NULL; ) {
    if (full_row(p, cof)) {
        *result = new_cube();
        free_cubelist(T);
        return TRUE;
    }
    }

    /* Collect column counts, determine unate variables, etc. */
    massive_count(T);

    /* If cover is unate (or single cube), apply simple rules to find SCCCU */
    if (cdata.vars_unate == cdata.vars_active || T[3] == NULL) {
    *result = set_save(cube.fullset);
    for(T1 = T+2; (p = *T1++) != NULL; ) {
        (void) sccc_cube(*result, set_or(temp, p, cof));
    }
    free_cubelist(T);
    return TRUE;
    }

    /* Check for column of 0's (which can be easily factored( */
    ceil = set_save(cof);
    for(T1 = T+2; (p = *T1++) != NULL; ) {
    INLINEset_or(ceil, ceil, p);
    }
    if (! setp_equal(ceil, cube.fullset)) {
    *result = sccc_cube(set_save(cube.fullset), ceil);
    if (setp_equal(*result, cube.fullset)) {
        free_cube(ceil);
    } else {
        *result = sccc_merge(sccc(cofactor(T,ceil)),
             set_save(cube.fullset), ceil, *result);
    }
    free_cubelist(T);
    return TRUE;
    }
    free_cube(ceil);

    /* Single active column at this point => tautology => SCCC is empty */
    if (cdata.vars_active == 1) {
    *result = new_cube();
    free_cubelist(T);
    return TRUE;
    }

    /* Check for components */
    if (cdata.var_zeros[cdata.best] < CUBELISTSIZE(T)/2) {
    if (cubelist_partition(T, &A, &B, debug & REDUCE1) == 0) {
        return MAYBE;
    } else {
        free_cubelist(T);
        *result = sccc(A);
        ceil = sccc(B);
        (void) set_and(*result, *result, ceil);
        set_free(ceil);
        return TRUE;
    }
    }

    /* Not much we can do about it */
    return MAYBE;
}