cvrm.c File Reference

#include "espresso.h"

Include dependency graph for cvrm.c:

Go to the source code of this file.

Functions
pcover	unravel_range (IN pcover B, IN int start, IN int end)
pcover	unravel (IN pcover B, IN int start)
pcover	lex_sort (pcover T)
pcover	size_sort (pcover T)
pcover	mini_sort (pcover F, int *compare)
pcover	sort_reduce (IN pcover T)
pcover	random_order (pcover F)
int	cubelist_partition (pcube *T, pcube **A, pcube **B, unsigned int comp_debug)
pcover	cof_output (pcover T, int i)
pcover	uncof_output (pcover T, int i)
void	foreach_output_function (pPLA PLA, int *func, int *func1)
void	so_espresso (pPLA PLA, int strategy)
void	so_both_espresso (pPLA PLA, int strategy)
int	so_do_espresso (pPLA PLA, int i)
int	so_do_exact (pPLA PLA, int i)
int	so_save (pPLA PLA, int i)
int	so_both_do_espresso (pPLA PLA, int i)
int	so_both_do_exact (pPLA PLA, int i)
int	so_both_save (pPLA PLA, int i)

Function Documentation

cof_output()

pcover cof_output	(	pcover	T,
		int	i )

Definition at line 312 of file cvrm.c.

{
    pcover T1;
    register pcube p, last, pdest, mask;
 
    mask = cube.var_mask[cube.output];
    T1 = new_cover(T->count);
    foreach_set(T, last, p) {
    if (is_in_set(p, i)) {
        pdest = GETSET(T1, T1->count++);
        INLINEset_or(pdest, p, mask);
        RESET(pdest, PRIME);
    }
    }
    return T1;
}

cubelist_partition()

int cubelist_partition	(	pcube *	T,
		pcube **	A,
		pcube **	B,
		unsigned int	comp_debug )

Definition at line 234 of file cvrm.c.

{
    register pcube *T1, p, seed, cof;
    pcube *A1, *B1;
    bool change;
    int count, numcube;
 
    numcube = CUBELISTSIZE(T);
 
    /* Mark all cubes -- covered cubes belong to the partition */
    for(T1 = T+2; (p = *T1++) != NULL; ) {
    RESET(p, COVERED);
    }
 
    /*
     *  Extract a partition from the cubelist T; start with the first cube as a
     *  seed, and then pull in all cubes which share a variable with the seed;
     *  iterate until no new cubes are brought into the partition.
     */
    seed = set_save(T[2]);
    cof = T[0];
    SET(T[2], COVERED);
    count = 1;
 
    do {
    change = FALSE;
    for(T1 = T+2; (p = *T1++) != NULL; ) {
        if (! TESTP(p, COVERED) && ccommon(p, seed, cof)) {
        INLINEset_and(seed, seed, p);
        SET(p, COVERED);
        change = TRUE;
        count++;
        }
    
    }
    } while (change);
 
    set_free(seed);
 
    if (comp_debug) {
    (void) printf("COMPONENT_REDUCTION: split into %d %d\n",
        count, numcube - count);
    }
 
    if (count != numcube) {
    /* Allocate and setup the cubelist's for the two partitions */
    *A = A1 = ALLOC(pcube, numcube+3);
    *B = B1 = ALLOC(pcube, numcube+3);
    (*A)[0] = set_save(T[0]);
    (*B)[0] = set_save(T[0]);
    A1 = *A + 2;
    B1 = *B + 2;
 
    /* Loop over the cubes in T and distribute to A and B */
    for(T1 = T+2; (p = *T1++) != NULL; ) {
        if (TESTP(p, COVERED)) {
        *A1++ = p;
        } else {
        *B1++ = p;
        }
    }
 
    /* Stuff needed at the end of the cubelist's */
    *A1++ = NULL;
    (*A)[1] = (pcube) A1;
    *B1++ = NULL;
    (*B)[1] = (pcube) B1;
    }
 
    return numcube - count;
}

Here is the call graph for this function:

foreach_output_function()

void foreach_output_function	(	pPLA	PLA,
		int *	func,
		int *	func1 )

Definition at line 363 of file cvrm.c.

{
    pPLA PLA1;
    int i;
 
    /* Loop for each output function */
    for(i = 0; i < cube.part_size[cube.output]; i++) {
 
    /* cofactor on the output part */
    PLA1 = new_PLA();
    PLA1->F = cof_output(PLA->F, i + cube.first_part[cube.output]);
    PLA1->R = cof_output(PLA->R, i + cube.first_part[cube.output]);
    PLA1->D = cof_output(PLA->D, i + cube.first_part[cube.output]);
 
    /* Call a routine to do something with the cover */
    if ((*func)(PLA1, i) == 0) {
        free_PLA(PLA1);
        return;
    }
 
    /* intersect with the particular output part again */
    PLA1->F = uncof_output(PLA1->F, i + cube.first_part[cube.output]);
    PLA1->R = uncof_output(PLA1->R, i + cube.first_part[cube.output]);
    PLA1->D = uncof_output(PLA1->D, i + cube.first_part[cube.output]);
 
    /* Call a routine to do something with the final result */
    if ((*func1)(PLA1, i) == 0) {
        free_PLA(PLA1);
        return;
    }
 
    /* Cleanup for next go-around */
    free_PLA(PLA1);
    
 
    }
}

Here is the call graph for this function:

lex_sort()

pcover lex_sort

(

pcover

T

)

Definition at line 121 of file cvrm.c.

{
    pcover T1 = sf_unlist(sf_sort(T, lex_order), T->count, T->sf_size);
    free_cover(T);
    return T1;
}

Here is the call graph for this function:

mini_sort()

pcover mini_sort	(	pcover	F,
		int *	compare )

Definition at line 141 of file cvrm.c.

{
    register int *count, cnt, n = cube.size, i;
    register pcube p, last;
    pcover F_sorted;
    pcube *F1;
 
    /* Perform a column sum over the set family */
    count = sf_count(F);
 
    /* weight is "inner product of the cube and the column sums" */
    foreach_set(F, last, p) {
    cnt = 0;
    for(i = 0; i < n; i++)
        if (is_in_set(p, i))
        cnt += count[i];
    PUTSIZE(p, cnt);
    }
    FREE(count);
 
    /* use qsort to sort the array */
    qsort((char *) (F1 = sf_list(F)), (size_t)F->count, sizeof(pcube), compare);
    F_sorted = sf_unlist(F1, F->count, F->sf_size);
    free_cover(F);
 
    return F_sorted;
}

Here is the call graph for this function:

random_order()

pcover random_order

(

pcover

F

)

Definition at line 199 of file cvrm.c.

{
    pset temp;
    register int i, k;
#ifdef RANDOM
    long random();
#endif
 
    temp = set_new(F->sf_size);
    for(i = F->count - 1; i > 0; i--) {
    /* Choose a random number between 0 and i */
#ifdef RANDOM
    k = random() % i;
#else
    /* this is not meant to be really used; just provides an easy
       "out" if random() and srandom() aren't around
    */
    k = (i*23 + 997) % i;
#endif
    /* swap sets i and k */
    (void) set_copy(temp, GETSET(F, k));
    (void) set_copy(GETSET(F, k), GETSET(F, i));
    (void) set_copy(GETSET(F, i), temp);
    }
    set_free(temp);
    return F;
}

Here is the call graph for this function:

size_sort()

pcover size_sort

(

pcover

T

)

Definition at line 131 of file cvrm.c.

{
    pcover T1 = sf_unlist(sf_sort(T, descend), T->count, T->sf_size);
    free_cover(T);
    return T1;
}

Here is the call graph for this function:

so_both_do_espresso()

int so_both_do_espresso	(	pPLA	PLA,
		int	i )

Definition at line 485 of file cvrm.c.

{
    char word[32];
 
    /* minimize the single-output function (on-set) */
    (void) sprintf(word, "ESPRESSO-POS(%d)", i);
    skip_make_sparse = 1;
    EXEC_S(PLA->F = espresso(PLA->F, PLA->D, PLA->R), word, PLA->F);
 
    /* minimize the single-output function (off-set) */
    (void) sprintf(word, "ESPRESSO-NEG(%d)", i);
    skip_make_sparse = 1;
    EXEC_S(PLA->R = espresso(PLA->R, PLA->D, PLA->F), word, PLA->R);
 
    return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

so_both_do_exact()

int so_both_do_exact	(	pPLA	PLA,
		int	i )

Definition at line 505 of file cvrm.c.

{
    char word[32];
 
    /* minimize the single-output function (on-set) */
    (void) sprintf(word, "EXACT-POS(%d)", i);
    skip_make_sparse = 1;
    EXEC_S(PLA->F = minimize_exact(PLA->F, PLA->D, PLA->R, 1), word, PLA->F);
 
    /* minimize the single-output function (off-set) */
    (void) sprintf(word, "EXACT-NEG(%d)", i);
    skip_make_sparse = 1;
    EXEC_S(PLA->R = minimize_exact(PLA->R, PLA->D, PLA->F, 1), word, PLA->R);
 
    return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

so_both_espresso()

void so_both_espresso	(	pPLA	PLA,
		int	strategy )

Definition at line 429 of file cvrm.c.

{
    phase = set_save(cube.fullset);
    Fmin = new_cover(PLA->F->count);
    if (strategy == 0) {
    foreach_output_function(PLA, so_both_do_espresso, so_both_save);
    } else {
    foreach_output_function(PLA, so_both_do_exact, so_both_save);
    }
    sf_free(PLA->F);
    PLA->F = Fmin;
    PLA->phase = phase;
}

Here is the call graph for this function:

so_both_save()

int so_both_save	(	pPLA	PLA,
		int	i )

Definition at line 525 of file cvrm.c.

{
    if (PLA->F->count > PLA->R->count) {
    sf_free(PLA->F);
    PLA->F = PLA->R;
    PLA->R = NULL;
    i += cube.first_part[cube.output];
    set_remove(phase, i);
    } else {
    sf_free(PLA->R);
    PLA->R = NULL;
    }
    Fmin = sf_append(Fmin, PLA->F);
    PLA->F = NULL;
    return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

so_do_espresso()

int so_do_espresso	(	pPLA	PLA,
		int	i )

Definition at line 446 of file cvrm.c.

{
    char word[32];
 
    /* minimize the single-output function (on-set) */
    skip_make_sparse = 1;
    (void) sprintf(word, "ESPRESSO-POS(%d)", i);
    EXEC_S(PLA->F = espresso(PLA->F, PLA->D, PLA->R), word, PLA->F);
    return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

so_do_exact()

int so_do_exact	(	pPLA	PLA,
		int	i )

Definition at line 460 of file cvrm.c.

{
    char word[32];
 
    /* minimize the single-output function (on-set) */
    skip_make_sparse = 1;
    (void) sprintf(word, "EXACT-POS(%d)", i);
    EXEC_S(PLA->F = minimize_exact(PLA->F, PLA->D, PLA->R, 1), word, PLA->F);
    return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

so_espresso()

void so_espresso	(	pPLA	PLA,
		int	strategy )

Definition at line 410 of file cvrm.c.

{
    Fmin = new_cover(PLA->F->count);
    if (strategy == 0) {
    foreach_output_function(PLA, so_do_espresso, so_save);
    } else {
    foreach_output_function(PLA, so_do_exact, so_save);
    }
    sf_free(PLA->F);
    PLA->F = Fmin;
}

Here is the call graph for this function:

so_save()

int so_save	(	pPLA	PLA,
		int	i )

Definition at line 475 of file cvrm.c.

{
    Fmin = sf_append(Fmin, PLA->F);    /* disposes of PLA->F */
    PLA->F = NULL;
    return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

sort_reduce()

pcover sort_reduce

(

IN pcover

T

)

Definition at line 173 of file cvrm.c.

{
    register pcube p, last, largest = NULL;
    register int bestsize = -1, size, n = cube.num_vars;
    pcover T_sorted;
    pcube *T1;
 
    if (T->count == 0)
    return T;
 
    /* find largest cube */
    foreach_set(T, last, p)
    if ((size = set_ord(p)) > bestsize)
        largest = p, bestsize = size;
 
    foreach_set(T, last, p)
    PUTSIZE(p, ((n - cdist(largest,p)) << 7) + MIN(set_ord(p),127));
 
    qsort((char *) (T1 = sf_list(T)), (size_t)T->count, sizeof(pcube), (int (*)()) descend);
    T_sorted = sf_unlist(T1, T->count, T->sf_size);
    free_cover(T);
 
    return T_sorted;
}

Here is the call graph for this function:

uncof_output()

pcover uncof_output	(	pcover	T,
		int	i )

Definition at line 335 of file cvrm.c.

{
    register pcube p, last, mask;
 
    if (T == NULL) {
    return T;
    }
 
    mask = cube.var_mask[cube.output];
    foreach_set(T, last, p) {
    INLINEset_diff(p, p, mask);
    set_insert(p, i);
    }
    return T;
}

unravel()

pcover unravel	(	IN pcover	B,
		IN int	start )

Definition at line 113 of file cvrm.c.

{
    return unravel_range(B, start, cube.num_vars-1);
}

Here is the call graph for this function:

unravel_range()

pcover unravel_range	(	IN pcover	B,
		IN int	start,
		IN int	end )

Definition at line 77 of file cvrm.c.

{
    pcover B1;
    int var, total_size, expansion, size;
    register pcube p, last, startbase = cube.temp[1];
 
    /* Create the starting base for those variables not being unravelled */
    (void) set_copy(startbase, cube.emptyset);
    for(var = 0; var < start; var++)
    (void) set_or(startbase, startbase, cube.var_mask[var]);
    for(var = end+1; var < cube.num_vars; var++)
    (void) set_or(startbase, startbase, cube.var_mask[var]);
 
    /* Determine how many cubes it will blow up into */
    total_size = 0;
    foreach_set(B, last, p) {
    expansion = 1;
    for(var = start; var <= end; var++)
        if ((size = set_dist(p, cube.var_mask[var])) >= 2)
        if ((expansion *= size) > 1000000)
            fatal("unreasonable expansion in unravel");
    total_size += expansion;
    }
 
    /* We can now allocate a cover of exactly the correct size */
    B1 = new_cover(total_size);
    foreach_set(B, last, p) {
    cb_unravel(p, start, end, startbase, B1);
    }
    free_cover(B);
    return B1;
}

Here is the call graph for this function: