| #include "espresso.h" |
| |
| map_dcset(PLA) |
| pPLA PLA; |
| { |
| int var, i; |
| pcover Tplus, Tminus, Tplusbar, Tminusbar; |
| pcover newf, term1, term2, dcset, dcsetbar; |
| pcube cplus, cminus, last, p; |
| |
| if (PLA->label == NIL(char *) || PLA->label[0] == NIL(char)) |
| return 0; |
| |
| /* try to find a binary variable named "DONT_CARE" */ |
| var = -1; |
| for(i = 0; i < cube.num_binary_vars * 2; i++) { |
| if (strncmp(PLA->label[i], "DONT_CARE", 9) == 0 || |
| strncmp(PLA->label[i], "DONTCARE", 8) == 0 || |
| strncmp(PLA->label[i], "dont_care", 9) == 0 || |
| strncmp(PLA->label[i], "dontcare", 8) == 0) { |
| var = i/2; |
| break; |
| } |
| } |
| if (var == -1) { |
| return 0; |
| } |
| |
| /* form the cofactor cubes for the don't-care variable */ |
| cplus = set_save(cube.fullset); |
| cminus = set_save(cube.fullset); |
| set_remove(cplus, var*2); |
| set_remove(cminus, var*2 + 1); |
| |
| /* form the don't-care set */ |
| EXEC(simp_comp(cofactor(cube1list(PLA->F), cplus), &Tplus, &Tplusbar), |
| "simpcomp+", Tplus); |
| EXEC(simp_comp(cofactor(cube1list(PLA->F), cminus), &Tminus, &Tminusbar), |
| "simpcomp-", Tminus); |
| EXEC(term1 = cv_intersect(Tplus, Tminusbar), "term1 ", term1); |
| EXEC(term2 = cv_intersect(Tminus, Tplusbar), "term2 ", term2); |
| EXEC(dcset = sf_union(term1, term2), "union ", dcset); |
| EXEC(simp_comp(cube1list(dcset), &PLA->D, &dcsetbar), "simplify", PLA->D); |
| EXEC(newf = cv_intersect(PLA->F, dcsetbar), "separate ", PLA->F); |
| free_cover(PLA->F); |
| PLA->F = newf; |
| free_cover(Tplus); |
| free_cover(Tminus); |
| free_cover(Tplusbar); |
| free_cover(Tminusbar); |
| free_cover(dcsetbar); |
| |
| /* remove any cubes dependent on the DONT_CARE variable */ |
| (void) sf_active(PLA->F); |
| foreach_set(PLA->F, last, p) { |
| if (! is_in_set(p, var*2) || ! is_in_set(p, var*2+1)) { |
| RESET(p, ACTIVE); |
| } |
| } |
| PLA->F = sf_inactive(PLA->F); |
| |
| /* resize the cube and delete the don't-care variable */ |
| setdown_cube(); |
| for(i = 2*var+2; i < cube.size; i++) { |
| PLA->label[i-2] = PLA->label[i]; |
| } |
| for(i = var+1; i < cube.num_vars; i++) { |
| cube.part_size[i-1] = cube.part_size[i]; |
| } |
| cube.num_binary_vars--; |
| cube.num_vars--; |
| cube_setup(); |
| PLA->F = sf_delc(PLA->F, 2*var, 2*var+1); |
| PLA->D = sf_delc(PLA->D, 2*var, 2*var+1); |
| } |
| |
| map_output_symbolic(PLA) |
| pPLA PLA; |
| { |
| pset_family newF, newD; |
| pset compress; |
| symbolic_t *p1; |
| symbolic_list_t *p2; |
| int i, bit, tot_size, base, old_size; |
| |
| /* Remove the DC-set from the ON-set (is this necessary ??) */ |
| if (PLA->D->count > 0) { |
| sf_free(PLA->F); |
| PLA->F = complement(cube2list(PLA->D, PLA->R)); |
| } |
| |
| /* tot_size = width added for all symbolic variables */ |
| tot_size = 0; |
| for(p1=PLA->symbolic_output; p1!=NIL(symbolic_t); p1=p1->next) { |
| for(p2=p1->symbolic_list; p2!=NIL(symbolic_list_t); p2=p2->next) { |
| if (p2->pos<0 || p2->pos>=cube.part_size[cube.output]) { |
| fatal("symbolic-output index out of range"); |
| /* } else if (p2->variable != cube.output) { |
| fatal("symbolic-output label must be an output");*/ |
| } |
| } |
| tot_size += 1 << p1->symbolic_list_length; |
| } |
| |
| /* adjust the indices to skip over new outputs */ |
| for(p1=PLA->symbolic_output; p1!=NIL(symbolic_t); p1=p1->next) { |
| for(p2=p1->symbolic_list; p2!=NIL(symbolic_list_t); p2=p2->next) { |
| p2->pos += tot_size; |
| } |
| } |
| |
| /* resize the cube structure -- add enough for the one-hot outputs */ |
| old_size = cube.size; |
| cube.part_size[cube.output] += tot_size; |
| setdown_cube(); |
| cube_setup(); |
| |
| /* insert space in the output part for the one-hot output */ |
| base = cube.first_part[cube.output]; |
| PLA->F = sf_addcol(PLA->F, base, tot_size); |
| PLA->D = sf_addcol(PLA->D, base, tot_size); |
| PLA->R = sf_addcol(PLA->R, base, tot_size); |
| |
| /* do the real work */ |
| for(p1=PLA->symbolic_output; p1!=NIL(symbolic_t); p1=p1->next) { |
| newF = new_cover(100); |
| newD = new_cover(100); |
| find_inputs(NIL(set_family_t), PLA, p1->symbolic_list, base, 0, |
| &newF, &newD); |
| /* |
| * Not sure what this means |
| find_dc_inputs(PLA, p1->symbolic_list, |
| base, 1 << p1->symbolic_list_length, &newF, &newD); |
| */ |
| free_cover(PLA->F); |
| PLA->F = newF; |
| /* |
| * retain OLD DC-set -- but we've lost the don't-care arc information |
| * (it defaults to branch to the zero state) |
| free_cover(PLA->D); |
| PLA->D = newD; |
| */ |
| free_cover(newD); |
| base += 1 << p1->symbolic_list_length; |
| } |
| |
| /* delete the old outputs, and resize the cube */ |
| compress = set_full(newF->sf_size); |
| for(p1=PLA->symbolic_output; p1!=NIL(symbolic_t); p1=p1->next) { |
| for(p2=p1->symbolic_list; p2!=NIL(symbolic_list_t); p2=p2->next) { |
| bit = cube.first_part[cube.output] + p2->pos; |
| set_remove(compress, bit); |
| } |
| } |
| cube.part_size[cube.output] -= newF->sf_size - set_ord(compress); |
| setdown_cube(); |
| cube_setup(); |
| PLA->F = sf_compress(PLA->F, compress); |
| PLA->D = sf_compress(PLA->D, compress); |
| if (cube.size != PLA->F->sf_size) fatal("error"); |
| |
| /* Quick minimization */ |
| PLA->F = sf_contain(PLA->F); |
| PLA->D = sf_contain(PLA->D); |
| for(i = 0; i < cube.num_vars; i++) { |
| PLA->F = d1merge(PLA->F, i); |
| PLA->D = d1merge(PLA->D, i); |
| } |
| PLA->F = sf_contain(PLA->F); |
| PLA->D = sf_contain(PLA->D); |
| |
| free_cover(PLA->R); |
| PLA->R = new_cover(0); |
| |
| symbolic_hack_labels(PLA, PLA->symbolic_output, |
| compress, cube.size, old_size, tot_size); |
| set_free(compress); |
| } |
| |
| |
| find_inputs(A, PLA, list, base, value, newF, newD) |
| pcover A; |
| pPLA PLA; |
| symbolic_list_t *list; |
| int base, value; |
| pcover *newF, *newD; |
| { |
| pcover S, S1; |
| register pset last, p; |
| |
| /* |
| * A represents th 'input' values for which the outputs assume |
| * the integer value 'value |
| */ |
| if (list == NIL(symbolic_list_t)) { |
| /* |
| * Simulate these inputs against the on-set; then, insert into the |
| * new on-set a 1 in the proper position |
| */ |
| S = cv_intersect(A, PLA->F); |
| foreach_set(S, last, p) { |
| set_insert(p, base + value); |
| } |
| *newF = sf_append(*newF, S); |
| |
| /* |
| * 'simulate' these inputs against the don't-care set |
| S = cv_intersect(A, PLA->D); |
| *newD = sf_append(*newD, S); |
| */ |
| |
| } else { |
| /* intersect and recur with the OFF-set */ |
| S = cof_output(PLA->R, cube.first_part[cube.output] + list->pos); |
| if (A != NIL(set_family_t)) { |
| S1 = cv_intersect(A, S); |
| free_cover(S); |
| S = S1; |
| } |
| find_inputs(S, PLA, list->next, base, value*2, newF, newD); |
| free_cover(S); |
| |
| /* intersect and recur with the ON-set */ |
| S = cof_output(PLA->F, cube.first_part[cube.output] + list->pos); |
| if (A != NIL(set_family_t)) { |
| S1 = cv_intersect(A, S); |
| free_cover(S); |
| S = S1; |
| } |
| find_inputs(S, PLA, list->next, base, value*2 + 1, newF, newD); |
| free_cover(S); |
| } |
| } |
| |
| |
| #if 0 |
| find_dc_inputs(PLA, list, base, maxval, newF, newD) |
| pPLA PLA; |
| symbolic_list_t *list; |
| int base, maxval; |
| pcover *newF, *newD; |
| { |
| pcover A, S, S1; |
| symbolic_list_t *p2; |
| register pset p, last; |
| register int i; |
| |
| /* painfully find the points for which the symbolic output is dc */ |
| A = NIL(set_family_t); |
| for(p2=list; p2!=NIL(symbolic_list_t); p2=p2->next) { |
| S = cof_output(PLA->D, cube.first_part[cube.output] + p2->pos); |
| if (A == NIL(set_family_t)) { |
| A = S; |
| } else { |
| S1 = cv_intersect(A, S); |
| free_cover(S); |
| free_cover(A); |
| A = S1; |
| } |
| } |
| |
| S = cv_intersect(A, PLA->F); |
| *newF = sf_append(*newF, S); |
| |
| S = cv_intersect(A, PLA->D); |
| foreach_set(S, last, p) { |
| for(i = base; i < base + maxval; i++) { |
| set_insert(p, i); |
| } |
| } |
| *newD = sf_append(*newD, S); |
| free_cover(A); |
| } |
| #endif |
| |
| map_symbolic(PLA) |
| pPLA PLA; |
| { |
| symbolic_t *p1; |
| symbolic_list_t *p2; |
| int var, base, num_vars, num_binary_vars, *new_part_size; |
| int new_size, size_added, num_deleted_vars, num_added_vars, newvar; |
| pset compress; |
| |
| /* Verify legal values are in the symbolic lists */ |
| for(p1 = PLA->symbolic; p1 != NIL(symbolic_t); p1 = p1->next) { |
| for(p2=p1->symbolic_list; p2!=NIL(symbolic_list_t); p2=p2->next) { |
| if (p2->variable < 0 || p2->variable >= cube.num_binary_vars) { |
| fatal(".symbolic requires binary variables"); |
| } |
| } |
| } |
| |
| /* |
| * size_added = width added for all symbolic variables |
| * num_deleted_vars = # binary variables to be deleted |
| * num_added_vars = # new mv variables |
| * compress = a cube which will be used to compress the set families |
| */ |
| size_added = 0; |
| num_added_vars = 0; |
| for(p1 = PLA->symbolic; p1 != NIL(symbolic_t); p1 = p1->next) { |
| size_added += 1 << p1->symbolic_list_length; |
| num_added_vars++; |
| } |
| compress = set_full(PLA->F->sf_size + size_added); |
| for(p1 = PLA->symbolic; p1 != NIL(symbolic_t); p1 = p1->next) { |
| for(p2=p1->symbolic_list; p2!=NIL(symbolic_list_t); p2=p2->next) { |
| set_remove(compress, p2->variable*2); |
| set_remove(compress, p2->variable*2+1); |
| } |
| } |
| 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 0; |
| 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) { |
| fprintf(stderr, |
| "use .symbolic and .symbolic-output to specify\n"); |
| 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) { |
| fprintf(stderr, |
| "use .symbolic and .symbolic-output to specify\n"); |
| 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) { |
| 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) { |
| 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); |
| 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) { |
| 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"); |
| } |
| } |