set.c

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

/* sf_print -- print a set_family as a set (list the element numbers) */
void sf_print(A)
pset_family A;
{
    char *ps1();
    register pset p;
    register int i;
    foreachi_set(A, i, p)
	(void) printf("A[%d] = %s\n", i, ps1(p));
}

/* sf_bm_print -- print a set_family as a bit-matrix */
void sf_bm_print(A)
pset_family A;
{
    char *pbv1();
    register pset p;
    register int i;
    foreachi_set(A, i, p)
	(void) printf("[%4d] %s\n", i, pbv1(p, A->sf_size));
}


/* sf_write -- output a set family in an unintelligable manner */
void sf_write(fp, A)
FILE *fp;
pset_family A;
{
    register pset p, last;
    (void) fprintf(fp, "%d %d\n", A->count, A->sf_size);
    foreach_set(A, last, p)
	set_write(fp, p);
    (void) fflush(fp);
}


/* sf_read -- read a set family written by sf_write */
pset_family sf_read(fp)
FILE *fp;
{
    int i, j;
    register pset p, last;
    pset_family A;

    (void) fscanf(fp, "%d %d\n", &i, &j);
    A = sf_new(i, j);
    A->count = i;
    foreach_set(A, last, p) {
	(void) fscanf(fp, "%x", p);
	for(j = 1; j <= LOOP(p); j++)
	    (void) fscanf(fp, "%x", p+j);
    }
    return A;
}


/* set_write -- output a set in an unintelligable manner */
void set_write(fp, a)
register FILE *fp;
register pset a;
{
    register int n = LOOP(a), j;

    for(j = 0; j <= n; j++) {
	(void) fprintf(fp, "%x ", a[j]);
	if ((j+1) % 8 == 0 && j != n)
	    (void) fprintf(fp, "\n\t");
    }
     (void) fprintf(fp, "\n");
}


/* sf_bm_read -- read a set family written by sf_bm_print (almost) */
pset_family sf_bm_read(fp)
FILE *fp;
{
    int i, j, rows, cols;
    register pset pdest;
    pset_family A;

    (void) fscanf(fp, "%d %d\n", &rows, &cols);
    A = sf_new(rows, cols);
    for(i = 0; i < rows; i++) {
	pdest = GETSET(A, A->count++);
	(void) set_clear(pdest, A->sf_size);
	for(j = 0; j < cols; j++) {
	    switch(getc(fp)) {
		case '0':
		    break;
		case '1':
		    set_insert(pdest, j);
		    break;
		default:
		    fatal("Error reading set family");
	    }
	}
	if (getc(fp) != '\n') {
	    fatal("Error reading set family (at end of line)");
	}
    }
    return A;
}



/* ps1 -- convert a set into a printable string */
#define largest_string 120
static char s1[largest_string];
char *ps1(a)
register pset a;
{
    register int i, num, l, len = 0, n = NELEM(a);
    char temp[20];
    bool first = TRUE;

    s1[len++] = '[';
    for(i = 0; i < n; i++)
	if (is_in_set(a,i)) {
	    if (! first)
		s1[len++] = ',';
	    first = FALSE; num = i;
	    /* Generate digits (reverse order) */
	    l = 0; do temp[l++] = num % 10 + '0'; while ((num /= 10) > 0);
	    /* Copy them back in correct order */
	    do s1[len++] = temp[--l]; while (l > 0);
	    if (len > largest_string-15) {
		s1[len++] = '.'; s1[len++] = '.'; s1[len++] = '.';
		break;
	    }
	}

    s1[len++] = ']';
    s1[len++] = '\0';
    return s1;
}

/* pbv1 -- print bit-vector */
char *pbv1(s, n)
pset s;
int n;
{
    register int i;
    for(i = 0; i < n; i++)
	s1[i] = is_in_set(s,i) ? '1' : '0';
    s1[n] = '\0';
    return s1;
}


/* set_adjcnt -- adjust the counts for a set by "weight" */
void
set_adjcnt(a, count, weight)
register pset a;
register int *count, weight;
{
    register int i, base;
    register unsigned int val;

    for(i = LOOP(a); i > 0; ) {
	for(val = a[i], base = --i << LOGBPI; val != 0; base++, val >>= 1) {
	    if (val & 1) {
		count[base] += weight;
	    }
	}
    }
}



/* sf_count -- perform a column sum over a set family */
int *sf_count(A)
pset_family A;
{
    register pset p, last;
    register int i, base, *count;
    register unsigned int val;

    count = ALLOC(int, A->sf_size);
    for(i = A->sf_size - 1; i >= 0; i--) {
	count[i] = 0;
    }

    foreach_set(A, last, p) {
	for(i = LOOP(p); i > 0; ) {
	    for(val = p[i], base = --i << LOGBPI; val != 0; base++, val >>= 1) {
		if (val & 1) {
		    count[base]++;
		}
	    }
	}
    }
    return count;
}


/* sf_count_restricted -- perform a column sum over a set family, restricting
 * to only the columns which are in r; also, the columns are weighted by the
 * number of elements which are in each row
 */
int *sf_count_restricted(A, r)
pset_family A;
register pset r;
{
    register pset p;
    register int i, base, *count;
    register unsigned int val;
    int weight;
    pset last;

    count = ALLOC(int, A->sf_size);
    for(i = A->sf_size - 1; i >= 0; i--) {
	count[i] = 0;
    }

    /* Loop for each set */
    foreach_set(A, last, p) {
	weight = 1024 / (set_ord(p) - 1);
	for(i = LOOP(p); i > 0; ) {
	    for(val=p[i]&r[i], base= --i<<LOGBPI; val!=0; base++, val >>= 1) {
		if (val & 1) {
		    count[base] += weight;
		}
	    }
	}
    }
    return count;
}


/*
 *  sf_delc -- delete columns first ... last of A
 */
pset_family sf_delc(A, first, last)
pset_family A;
int first, last;
{
    return sf_delcol(A, first, last-first + 1);
}


/*
 *  sf_addcol -- add columns to a set family; includes a quick check to see
 *  if there is already enough room (and hence, can avoid copying)
 */
pset_family sf_addcol(A, firstcol, n)
pset_family A;
int firstcol, n;
{
    int maxsize;

    /* Check if adding columns at the end ... */
    if (firstcol == A->sf_size) {
	/* If so, check if there is already enough room */
	maxsize = BPI * LOOPINIT(A->sf_size);
	if ((A->sf_size + n) <= maxsize) {
	    A->sf_size += n;
	    return A;
	}
    }
    return sf_delcol(A, firstcol, -n);
}

/*
 * sf_delcol -- add/delete columns to/from a set family
 *
 *  if n > 0 then n columns starting from firstcol are deleted if n < 0
 *  then n blank columns are inserted starting at firstcol
 *      (i.e., the first new column number is firstcol)
 *
 *  This is done by copying columns in the array which is a relatively
 *  slow operation.
 */
pset_family sf_delcol(A, firstcol, n)
pset_family A;
register int firstcol, n;
{
    register pset p, last, pdest;
    register int i;
    pset_family B;

    B = sf_new(A->count, A->sf_size - n);
    foreach_set(A, last, p) {
	pdest = GETSET(B, B->count++);
	INLINEset_clear(pdest, B->sf_size);
	for(i = 0; i < firstcol; i++)
	    if (is_in_set(p, i))
		set_insert(pdest, i);
	for(i = n > 0 ? firstcol + n : firstcol; i < A->sf_size; i++)
	    if (is_in_set(p, i))
		set_insert(pdest, i - n);
    }
    sf_free(A);
    return B;
}


/*
 *  sf_copy_col -- copy column "srccol" from "src" to column "dstcol" of "dst"
 */
pset_family sf_copy_col(dst, dstcol, src, srccol)
pset_family dst, src;
int dstcol, srccol;
{
    register pset last, p, pdest;
    register int word_test, word_set;
    unsigned int bit_set, bit_test;

    /* CHEAT! form these constants outside the loop */
    word_test = WHICH_WORD(srccol);
    bit_test = 1 << WHICH_BIT(srccol);
    word_set = WHICH_WORD(dstcol);
    bit_set = 1 << WHICH_BIT(dstcol);

    pdest = dst->data;
    foreach_set(src, last, p) {
	if ((p[word_test] & bit_test) != 0)
	    pdest[word_set] |= bit_set;
/*
 *  equivalent code for this is ...
 *	if (is_in_set(p, srccol)) set_insert(pdest, destcol);
 */
	pdest += dst->wsize;
    }
    return dst;
}



/*
 *  sf_compress -- delete columns from a matrix
 */
pset_family sf_compress(A, c)
pset_family A;			/* will be freed */
register pset c;
{
    register pset p;
    register int i, bcol;
    pset_family B;

    /* create a clean set family for the result */
    B = sf_new(A->count, set_ord(c));
    for(i = 0; i < A->count; i++) {
	p = GETSET(B, B->count++);
	INLINEset_clear(p, B->sf_size);
    }

    /* copy each column of A which has a 1 in c */
    bcol = 0;
    for(i = 0; i < A->sf_size; i++) {
	if (is_in_set(c, i)) {
	    (void) sf_copy_col(B, bcol++, A, i);
	}
    }
    sf_free(A);
    return B;
}



/*
 *  sf_transpose -- transpose a bit matrix
 *
 *  There are trickier ways of doing this, but this works.
 */
pset_family sf_transpose(A)
pset_family A;
{
    pset_family B;
    register pset p;
    register int i, j;

    B = sf_new(A->sf_size, A->count);
    B->count = A->sf_size;
    foreachi_set(B, i, p) {
	INLINEset_clear(p, B->sf_size);
    }
    foreachi_set(A, i, p) {
	for(j = 0; j < A->sf_size; j++) {
	    if (is_in_set(p, j)) {
		set_insert(GETSET(B, j), i);
	    }
	}
    }
    sf_free(A);
    return B;
}


/*
 *   sf_permute -- permute the columns of a set_family
 *
 *   permute is an array of integers containing column numbers of A which
 *   are to be retained.
 */
pset_family sf_permute(A, permute, npermute)
pset_family A;
register int *permute, npermute;
{
    pset_family B;
    register pset p, last, pdest;
    register int j;

    B = sf_new(A->count, npermute);
    B->count = A->count;
    foreach_set(B, last, p)
	INLINEset_clear(p, npermute);

    pdest = B->data;
    foreach_set(A, last, p) {
	for(j = 0; j < npermute; j++)
	    if (is_in_set(p, permute[j]))
		set_insert(pdest, j);
	pdest += B->wsize;
    }
    sf_free(A);
    return B;
}