hack.c

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

    num_deleted_vars = ((PLA->F->sf_size + size_added) - set_ord(compress))/2;

    /* compute the new cube constants */
    num_vars = cube.num_vars - num_deleted_vars + num_added_vars;
    num_binary_vars = cube.num_binary_vars - num_deleted_vars;
    new_size = cube.size - num_deleted_vars*2 + size_added;
    new_part_size = ALLOC(int, num_vars);
    new_part_size[num_vars-1] = cube.part_size[cube.num_vars-1];
    for(var = cube.num_binary_vars; var < cube.num_vars-1; var++) {
	new_part_size[var-num_deleted_vars] = cube.part_size[var];
    }

    /* re-size the covers, opening room for the new mv variables */
    base = cube.first_part[cube.output];
    PLA->F = sf_addcol(PLA->F, base, size_added);
    PLA->D = sf_addcol(PLA->D, base, size_added);
    PLA->R = sf_addcol(PLA->R, base, size_added);

    /* compute the values for the new mv variables */
    newvar = (cube.num_vars - 1) - num_deleted_vars;
    for(p1 = PLA->symbolic; p1 != NIL(symbolic_t); p1 = p1->next) {
	PLA->F = map_symbolic_cover(PLA->F, p1->symbolic_list, base);
	PLA->D = map_symbolic_cover(PLA->D, p1->symbolic_list, base);
	PLA->R = map_symbolic_cover(PLA->R, p1->symbolic_list, base);
	base += 1 << p1->symbolic_list_length;
	new_part_size[newvar++] = 1 << p1->symbolic_list_length;
    }

    /* delete the binary variables which disappear */
    PLA->F = sf_compress(PLA->F, compress);
    PLA->D = sf_compress(PLA->D, compress);
    PLA->R = sf_compress(PLA->R, compress);

    symbolic_hack_labels(PLA, PLA->symbolic, compress,
		new_size, cube.size, size_added);
    setdown_cube();
    FREE(cube.part_size);
    cube.num_vars = num_vars;
    cube.num_binary_vars = num_binary_vars;
    cube.part_size = new_part_size;
    cube_setup();
    set_free(compress);
}


pcover map_symbolic_cover(T, list, base)
pcover T;
symbolic_list_t *list;
int base;
{
    pset last, p;
    foreach_set(T, last, p) {
	form_bitvector(p, base, 0, list);
    }
    return T;
}


form_bitvector(p, base, value, list)
pset p;			/* old cube, looking at binary variables */
int base;		/* where in mv cube the new variable starts */
int value;		/* current value for this recursion */
symbolic_list_t *list;	/* current place in the symbolic list */
{
    if (list == NIL(symbolic_list_t)) {
	set_insert(p, base + value);
    } else {
	switch(GETINPUT(p, list->variable)) {
	    case ZERO:
		form_bitvector(p, base, value*2, list->next);
		break;
	    case ONE:
		form_bitvector(p, base, value*2+1, list->next);
		break;
	    case TWO:
		form_bitvector(p, base, value*2, list->next);
		form_bitvector(p, base, value*2+1, list->next);
		break;
	    default:
		fatal("bad cube in form_bitvector");
	}
    }
}


symbolic_hack_labels(PLA, list, compress, new_size, old_size, size_added)
pPLA PLA;
symbolic_t *list;
pset compress;
int new_size, old_size, size_added;
{
    int i, base;
    char **oldlabel;
    symbolic_t *p1;
    symbolic_label_t *p3;

    /* hack with the labels */
    if ((oldlabel = PLA->label) == NIL(char *))
	return;
    PLA->label = ALLOC(char *, new_size);
    for(i = 0; i < new_size; i++) {
	PLA->label[i] = NIL(char);
    }

    /* copy the binary variable labels and unchanged mv variable labels */
    base = 0;
    for(i = 0; i < cube.first_part[cube.output]; i++) {
	if (is_in_set(compress, i)) {
	    PLA->label[base++] = oldlabel[i];
	} else {
	    if (oldlabel[i] != NIL(char)) {
		FREE(oldlabel[i]);
	    }
	}
    }

    /* add the user-defined labels for the symbolic outputs */
    for(p1 = list; p1 != NIL(symbolic_t); p1 = p1->next) {
	p3 = p1->symbolic_label;
	for(i = 0; i < (1 << p1->symbolic_list_length); i++) {
	    if (p3 == NIL(symbolic_label_t)) {
		PLA->label[base+i] = ALLOC(char, 10);
		(void) sprintf(PLA->label[base+i], "X%d", i);
	    } else {
		PLA->label[base+i] = p3->label;
		p3 = p3->next;
	    }
	}
	base += 1 << p1->symbolic_list_length;
    }

    /* copy the labels for the binary outputs which remain */
    for(i = cube.first_part[cube.output]; i < old_size; i++) {
	if (is_in_set(compress, i + size_added)) {
	    PLA->label[base++] = oldlabel[i];
	} else {
	    if (oldlabel[i] != NIL(char)) {
		FREE(oldlabel[i]);
	    }
	}
    }
    FREE(oldlabel);
}

static pcover fsm_simplify(F)
pcover F;
{
    pcover D, R;
    D = new_cover(0);
    R = complement(cube1list(F));
    F = espresso(F, D, R);
    free_cover(D);
    free_cover(R);
    return F;
}


disassemble_fsm(PLA, verbose_mode)
pPLA PLA;
int verbose_mode;
{
    int nin, nstates, nout;
    int before, after, present_state, next_state, i, j;
    pcube next_state_mask, present_state_mask, state_mask, p, p1, last;
    pcover go_nowhere, F, tF;

    /* We make the DISGUSTING assumption that the first 'n' outputs have
     *  been created by .symbolic-output, and represent a one-hot encoding
     * of the next state.  'n' is the size of the second-to-last multiple-
     * valued variable (i.e., before the outputs
     */

    if (cube.num_vars - cube.num_binary_vars != 2) {
	(void) fprintf(stderr,
	"use .symbolic and .symbolic-output to specify\n");
	(void) fprintf(stderr,
	"the present state and next state field information\n");
	fatal("disassemble_pla: need two multiple-valued variables\n");
    }

    nin = cube.num_binary_vars;
    nstates = cube.part_size[cube.num_binary_vars];
    nout = cube.part_size[cube.num_vars - 1];
    if (nout < nstates) {
	(void) fprintf(stderr,
	    "use .symbolic and .symbolic-output to specify\n");
	(void) fprintf(stderr,
	    "the present state and next state field information\n");
	fatal("disassemble_pla: # outputs < # states\n");
    }


    present_state = cube.first_part[cube.num_binary_vars];
    present_state_mask = new_cube();
    for(i = 0; i < nstates; i++) {
	set_insert(present_state_mask, i + present_state);
    }

    next_state = cube.first_part[cube.num_binary_vars+1];
    next_state_mask = new_cube();
    for(i = 0; i < nstates; i++) {
	set_insert(next_state_mask, i + next_state);
    }

    state_mask = set_or(new_cube(), next_state_mask, present_state_mask);

    F = new_cover(10);


    /*
     *  check for arcs which go from ANY state to state #i
     */
    for(i = 0; i < nstates; i++) {
	tF = new_cover(10);
	foreach_set(PLA->F, last, p) {
	    if (setp_implies(present_state_mask, p)) { /* from any state ! */
		if (is_in_set(p, next_state + i)) {
		    tF = sf_addset(tF, p);
		}
	    }
	}
	before = tF->count;
	if (before > 0) {
	    tF = fsm_simplify(tF);
	    /* don't allow the next state to disappear ... */
	    foreach_set(tF, last, p) {
		set_insert(p, next_state + i);
	    }
	    after = tF->count;
	    F = sf_append(F, tF);
	    if (verbose_mode) {
		(void) printf("# state EVERY to %d, before=%d after=%d\n",
			i, before, after);
	    }
	}
    }


    /*
     *  some 'arcs' may NOT have a next state -- handle these
     *  we must unravel the present state part
     */
    go_nowhere = new_cover(10);
    foreach_set(PLA->F, last, p) {
	if (setp_disjoint(p, next_state_mask)) { /* no next state !! */
	    go_nowhere = sf_addset(go_nowhere, p);
	}
    }
    before = go_nowhere->count;
    go_nowhere = unravel_range(go_nowhere,
				cube.num_binary_vars, cube.num_binary_vars);
    after = go_nowhere->count;
    F = sf_append(F, go_nowhere);
    if (verbose_mode) {
	(void) printf("# state ANY to NOWHERE, before=%d after=%d\n", before, after);
    }


    /*
     *  minimize cover for all arcs from state #i to state #j
     */
    for(i = 0; i < nstates; i++) {
	for(j = 0; j < nstates; j++) {
	    tF = new_cover(10);
	    foreach_set(PLA->F, last, p) {
		/* not EVERY state */
		if (! setp_implies(present_state_mask, p)) {
		    if (is_in_set(p, present_state + i)) {
			if (is_in_set(p, next_state + j)) {
			    p1 = set_save(p);
			    (void) set_diff(p1, p1, state_mask);
			    set_insert(p1, present_state + i);
			    set_insert(p1, next_state + j);
			    tF = sf_addset(tF, p1);
			    set_free(p1);
			}
		    }
		}
	    }
	    before = tF->count;
	    if (before > 0) {
		tF = fsm_simplify(tF);
		/* don't allow the next state to disappear ... */
		foreach_set(tF, last, p) {
		    set_insert(p, next_state + j);
		}
		after = tF->count;
		F = sf_append(F, tF);
		if (verbose_mode) {
		    (void) printf("# state %d to %d, before=%d after=%d\n",
			    i, j, before, after);
		}
	    }
	}
    }


    free_cube(state_mask);
    free_cube(present_state_mask);
    free_cube(next_state_mask);

    free_cover(PLA->F);
    PLA->F = F;
    free_cover(PLA->D);
    PLA->D = new_cover(0);

    setdown_cube();
    FREE(cube.part_size);
    cube.num_binary_vars = nin;
    cube.num_vars = nin + 3;
    cube.part_size = ALLOC(int, cube.num_vars);
    cube.part_size[cube.num_binary_vars] = nstates;
    cube.part_size[cube.num_binary_vars+1] = nstates;
    cube.part_size[cube.num_binary_vars+2] = nout - nstates;
    cube_setup();

    foreach_set(PLA->F, last, p) {
	kiss_print_cube(stdout, PLA, p, "~1");
    }
}