opo.c

主要进行大规模的电路综合

pset select;
int f, fbar;		/* indices of f and fbar in the output part */
{
    register int i;
    register pcube p;
    pset_family f_table, fbar_table;

    /* setup required for fcube_is_covered */
    Rp_size = F->count;
    Rp_start = set_new(Rp_size);
    foreachi_set(F, i, p) {
	PUTSIZE(p, i);
    }
    foreachi_set(D, i, p) {
	RESET(p, REDUND);
    }

    f_table = find_covers(F, D, select, f);
    fbar_table = find_covers(F, D, select, fbar);
    f_table = sf_append(f_table, fbar_table);

    set_free(Rp_start);
    return f_table;
}


pset_family find_covers(F, D, select, n)
pcover F, D;
register pset select;
int n;
{
    register pset p, last, new;
    pcover F1;
    pcube *Flist;
    pset_family f_table, table;
    int i;

    n += cube.first_part[cube.output];

    /* save cubes in this output, and remove the output variable */
    F1 = new_cover(F->count);
    foreach_set(F, last, p)
	if (is_in_set(p, n)) {
	    new = GETSET(F1, F1->count++);
	    (void) set_or(new, p, cube.var_mask[cube.output]);
	    PUTSIZE(new, SIZE(p));
	    SET(new, REDUND);
	}

    /* Find ways (sop form) to fail to cover output indexed by n */
    Flist = cube2list(F1, D);
    table = sf_new(10, Rp_size);
    foreach_set(F1, last, p) {
	(void) set_fill(Rp_start, Rp_size);
	set_remove(Rp_start, SIZE(p));
	table = sf_append(table, fcube_is_covered(Flist, p));
	RESET(p, REDUND);
    }
    (void) set_fill(Rp_start, Rp_size);
    foreach_set(table, last, p) {
	(void) set_diff(p, Rp_start, p);
    }

    /* complement this to get possible ways to cover the function */
    for(i = 0; i < Rp_size; i++) {
	if (! is_in_set(select, i)) {
	    p = set_new(Rp_size);
	    set_insert(p, i);
	    table = sf_addset(table, p);
	    set_free(p);
	}
    }
    f_table = unate_compl(table);

    /* what a pain, but we need bitwise complement of this */
    (void) set_fill(Rp_start, Rp_size);
    foreach_set(f_table, last, p) {
	(void) set_diff(p, Rp_start, p);
    }

    free_cubelist(Flist);
    sf_free(F1);
    return f_table;
}
#endif

/*
 *  Take a PLA (ON-set, OFF-set and DC-set) and create the
 *  "double-phase characteristic function" which is merely a new
 *  function which has twice as many outputs and realizes both the
 *  function and the complement.
 *
 *  The cube structure is assumed to represent the PLA upon entering.
 *  It will be modified to represent the double-phase function upon
 *  exit.
 *
 *  Only the outputs numbered starting with "first_output" are
 *  duplicated in the output part
 */

output_phase_setup(PLA, first_output)
INOUT pPLA PLA;
int first_output;
{
    pcover F, R, D;
    pcube mask, mask1, last;
    int first_part, offset;
    bool save;
    register pcube p, pr, pf;
    register int i, last_part;

    if (cube.output == -1)
	fatal("output_phase_setup: must have an output");

    F = PLA->F;
    D = PLA->D;
    R = PLA->R;
    first_part = cube.first_part[cube.output] + first_output;
    last_part = cube.last_part[cube.output];
    offset = cube.part_size[cube.output] - first_output;

    /* Change the output size, setup the cube structure */
    setdown_cube();
    cube.part_size[cube.output] += offset;
    cube_setup();

    /* Create a mask to select that part of the cube which isn't changing */
    mask = set_save(cube.fullset);
    for(i = first_part; i < cube.size; i++)
	set_remove(mask, i);
    mask1 = set_save(mask);
    for(i = cube.first_part[cube.output]; i < first_part; i++) {
	set_remove(mask1, i);
    }

    PLA->F = new_cover(F->count + R->count);
    PLA->R = new_cover(F->count + R->count);
    PLA->D = new_cover(D->count);

    foreach_set(F, last, p) {
	pf = GETSET(PLA->F, (PLA->F)->count++);
	pr = GETSET(PLA->R, (PLA->R)->count++);
	INLINEset_and(pf, mask, p);
	INLINEset_and(pr, mask1, p);
	for(i = first_part; i <= last_part; i++)
	    if (is_in_set(p, i))
		set_insert(pf, i);
	save = FALSE;
	for(i = first_part; i <= last_part; i++)
	    if (is_in_set(p, i))
		save = TRUE, set_insert(pr, i+offset);
	if (! save) PLA->R->count--;
    }

    foreach_set(R, last, p) {
	pf = GETSET(PLA->F, (PLA->F)->count++);
	pr = GETSET(PLA->R, (PLA->R)->count++);
	INLINEset_and(pf, mask1, p);
	INLINEset_and(pr, mask, p);
	save = FALSE;
	for(i = first_part; i <= last_part; i++)
	    if (is_in_set(p, i))
		save = TRUE, set_insert(pf, i+offset);
	if (! save) PLA->F->count--;
	for(i = first_part; i <= last_part; i++)
	    if (is_in_set(p, i))
		set_insert(pr, i);
    }

    foreach_set(D, last, p) {
	pf = GETSET(PLA->D, (PLA->D)->count++);
	INLINEset_and(pf, mask, p);
	for(i = first_part; i <= last_part; i++)
	    if (is_in_set(p, i)) {
		set_insert(pf, i);
		set_insert(pf, i+offset);
	    }
    }

    free_cover(F);
    free_cover(D);
    free_cover(R);
    set_free(mask);
    set_free(mask1);
}

/*
 *  set_phase -- given a "cube" which describes which phases of the output
 *  are to be implemented, compute the appropriate on-set and off-set
 */
pPLA set_phase(PLA)
INOUT pPLA PLA;
{
    pcover F1, R1;
    register pcube last, p, outmask;
    register pcube temp=cube.temp[0], phase=PLA->phase, phase1=cube.temp[1];

    outmask = cube.var_mask[cube.num_vars - 1];
    (void) set_diff(phase1, outmask, phase);
    (void) set_or(phase1, set_diff(temp, cube.fullset, outmask), phase1);
    F1 = new_cover((PLA->F)->count + (PLA->R)->count);
    R1 = new_cover((PLA->F)->count + (PLA->R)->count);

    foreach_set(PLA->F, last, p) {
	if (! setp_disjoint(set_and(temp, p, phase), outmask))
	    (void) set_copy(GETSET(F1, F1->count++), temp);
	if (! setp_disjoint(set_and(temp, p, phase1), outmask))
	    (void) set_copy(GETSET(R1, R1->count++), temp);
    }
    foreach_set(PLA->R, last, p) {
	if (! setp_disjoint(set_and(temp, p, phase), outmask))
	    (void) set_copy(GETSET(R1, R1->count++), temp);
	if (! setp_disjoint(set_and(temp, p, phase1), outmask))
	    (void) set_copy(GETSET(F1, F1->count++), temp);
    }
    free_cover(PLA->F);
    free_cover(PLA->R);
    PLA->F = F1;
    PLA->R = R1;
    return PLA;
}

#define POW2(x)		(1 << (x))

void opoall(PLA, first_output, last_output, opo_strategy)
pPLA PLA;
int first_output, last_output;
int opo_strategy;
{
    pcover F, D, R, best_F, best_D, best_R;
    int i, j, ind, num;
    pcube bestphase;

    opo_exact = opo_strategy;

    if (PLA->phase != NULL) {
	set_free(PLA->phase);
    }

    bestphase = set_save(cube.fullset);
    best_F = sf_save(PLA->F);
    best_D = sf_save(PLA->D);
    best_R = sf_save(PLA->R);

    for(i = 0; i < POW2(last_output - first_output + 1); i++) {

	/* save the initial PLA covers */
	F = sf_save(PLA->F);
	D = sf_save(PLA->D);
	R = sf_save(PLA->R);

	/* compute the phase cube for this iteration */
	PLA->phase = set_save(cube.fullset);
	num = i;
	for(j = last_output; j >= first_output; j--) {
	    if (num % 2 == 0) {
		ind = cube.first_part[cube.output] + j;
		set_remove(PLA->phase, ind);
	    }
	    num /= 2;
	}

	/* set the phase and minimize */
	(void) set_phase(PLA);
	(void) printf("# phase is %s\n", pc1(PLA->phase));
	summary = TRUE;
	esp_minimize(PLA);

	/* see if this is the best so far */
	if (PLA->F->count < best_F->count) {
	    /* save new best solution */
	    (void) set_copy(bestphase, PLA->phase);
	    sf_free(best_F);
	    sf_free(best_D);
	    sf_free(best_R);
	    best_F = PLA->F;
	    best_D = PLA->D;
	    best_R = PLA->R;
	} else {
	    /* throw away the solution */
	    free_cover(PLA->F);
	    free_cover(PLA->D);
	    free_cover(PLA->R);
	}
	set_free(PLA->phase);

	/* restore the initial PLA covers */
	PLA->F = F;
	PLA->D = D;
	PLA->R = R;
    }

    /* one more minimization to restore the best answer */
    PLA->phase = bestphase;
    sf_free(PLA->F);
    sf_free(PLA->D);
    sf_free(PLA->R);
    PLA->F = best_F;
    PLA->D = best_D;
    PLA->R = best_R;
}

static void
esp_minimize(PLA)
pPLA PLA;
{
    if (opo_exact) {
	EXEC_S(PLA->F = minimize_exact(PLA->F,PLA->D,PLA->R,1), "EXACT", PLA->F);
    } else {
	EXEC_S(PLA->F = espresso(PLA->F, PLA->D, PLA->R), "ESPRESSO  ",PLA->F);
    }
}