/* Last edited on 2006-05-25 21:19:19 by stolfi */ /* ---------------------------------------------------------------------- */ /* ---------------------------------------------------------------------- */ bifun_t bifun_from_tcgate(int m, int n, tcgate_t g) { bool_t debug = FALSE; assert(m <= m_max); assert(n <= n_max); uint32_t mw = (1 << m); uint32_t nw = (1 << n); uint32_t nmask = nw - 1; word_t y[mw]; uint32_t kx; for (kx = 0; kx < mw; kx++) { word_t x = mw - 1 - kx; y[x] = tcgate_apply(g, x) & nmask; } if (debug) { word_table_print_h(stderr, "\n ( ", m, n, mw, y, " )\n"); } return pack_bifun(m, n, y); } /* ---------------------------------------------------------------------- */ /* The non-ident TC gates and their bifuns: */ uint32_t ng = 0; /* Number of non-ident TC gates. */ bifun_t gg[ng_max]; /* {gg[0..ng-1]} are the non-trivial TC gates. */ bifun_t fg[ng_max]; /* {fg[i]} is the bifun of TC gate {gg[i]}. */ { uint32_t kg; for (kg = 0; kg < ng_max; kg++) { tcgate_t gk = kg; fprintf(stderr, "TC gate %02d", gk); tcgate_print(stderr, " = ", n, gk, "", TRUE); bifun_t fk = !! bifun_from_tcgate(m, n, gk); if (fk == bifun_ident(m, n)) { fprintf(stderr, " (no-op)\n"); } else { bifun_print_h(stderr, " = ", fk, "\n"); gg[ng] = gk; fg[ng] = fk; ng++; } } } /* ---------------------------------------------------------------------- */ /* TC GATES A TC gate is encoded as the integer {K + m*(T + 3^K*Q)} where {K} is the position of the first inverter in {0..m-1}, {T} is a ternary encoding of the first {K} elements, and {Q} is a quaternary encoding of the remaining {m-1-K} elements; where pass is 0, 0-test is 1, 1-test is 2, and invert is 3. All TC gates have {n_max} wires. The encoding is such that gates which use only the lowest {m} wires have lower numbers than those with */ void get_tcgate_masks(tcgate_t g, word_t *a, word_t *b); /* Expands a TC gate {g} into two binary masks {a,b}. The element on wire {i} is encoded as the pair {(a[i],b[i])}, with the conventions 00 = pass, 01 = invert, 10 = 0-test, 11 = 1-test. */ typedef uint8_t bit_t; char elem_symbol(bit_t a, bit_t b); /* The symbolic code for element {e} with mask bits {a,b}: which is one of 'X' (invert), '-' (pass), '0' (0-test), and '1' (1-test). */ void get_tcgate_masks(tcgate_t g, word_t *a, word_t *b) { assert((g >= 0) && (g < NG)); uint32_t gg = g; int ip = gg % n; /* Wire number of first inverter. */ gg = gg/n; uint32_t H = ipow(3, ip); uint32_t gg1 = gg % H; /* Elements before first inverter. */ uint32_t gg2 = gg / H; /* Elements after first inverter. */ /* Masks being built: */ word_t aa = 0, bb = 0; int k = 0; /* Current wire. */ word_t z = 1; /* {z = 2^i}. */ /* Expand elements before first inverter: */ while (k < ip) { uint32_t r = gg1 % 3; gg1 /= 3; switch(r) { case 0: /* Pass: */ break; case 1: /* 0-test: */ aa |= z; break; case 2: /* 1-test: */ aa |= z; bb |= z; break; default: assert(FALSE); } k++; z <<= 1; } /* Add first inverter: */ bb |= z; k++; z <<= 1; /* Expand elements after first inverter: */ while (k < n) { uint32_t r = gg2 % 4; gg2 /= 4; switch(r) { case 0: /* Pass: */ break; case 1: /* 0-test: */ aa |= z; break; case 2: /* 1-test: */ aa |= z; bb |= z; break; case 3: /* invert: */ bb |= z; break; default: assert(FALSE); } k++; z <<= 1; } /* Return masks: */ (*a) = aa; (*b) = bb; } /* ---------------------------------------------------------------------- */ typedef int32_t bifun_t; /* A one-to-one map {f} of {B^N} to {B^N}, encoded as an integer in {0..NF-1}. */ #define BIFUN_NULL ((int32_t)-1) /* A NULL value for a {bifun_t}. */ bifun_t bifun_ident(void); /* The identity bifun. */ word_t bifun_apply(bifun_t f, word_t x); /* Applies the bifun {f} to the word {x}. */ bifun_t bifun_from_tcgate(tcgate_t g); /* Returns the function computed by the TC gate {g}. */ bifun_t bifun_compose(bifun_t f1, bifun_t f2); /* Returns the function {f1·f2} equivalent to applying first {f1} then {f2}. */ void bifun_print_h(FILE *wr, char *pre, bifun_t f, char *suf); /* Writes bifun {f} to {wr}, human-readable, in single-line format, namely "fNNNNN =" followed by the word table in horizontal format. The whole is sanwiched between {pre} and {suf}. */ void bifun_print_v(FILE *wr, char *head, int ind, bifun_t f, char *foot); /* Writes bifun {f} to {wr}, human-readable, one entry per line. Namely, writes "fNNNNN =" in the first line, then the argument-value table in vertical format. Each line is indented by {ind} spaces. The whole table is sandwiched between lines containing {head} and {foot} (if not NULL). */ /* ---------------------------------------------------------------------- */ /* BIFUNS (PERMUTATIONS OF {B^N}). */ void unpack_bifun(bifun_t f, word_t t[]); /* Stores in {t[x]} the value of {f(x)}, for all words {x} in {0..NW-1}. */ bifun_t pack_bifun(word_t t[]); /* Returns the bifun {f} such that {f(x) = t[x]} for all {x} in {0..NW-1}. */ void unpack_bifun(bifun_t f, word_t t[]) { auto void aux(bifun_t h, uint32_t L); /* Assumes that {h} is a bifun that maps any word {y >= L} to itself. Stores in {t[y]} the value of {h(y)} for all {y < L}. */ void aux(bifun_t h, uint32_t L) { if (L == 0) { assert(h == 0); return; } else { word_t xx = L - 1; word_t yy = xx - (h % L); t[xx] = yy; aux(h/L, xx); /* Remap {t[0..xx-1]} so as to skip the value {yy}: */ word_t y; for (y = 0; y < xx; y++) { if (t[y] >= yy) { t[y]++; }; assert(t[y] < L); } } } aux(f, NW); } bifun_t pack_bifun(word_t t[]) { auto bifun_t aux(int L); /* Returns the code of the bifun {h} such that {h(y) = t[y]} if {y < L}, and {h(y) = y} if {y >= L}. */ bifun_t aux(int L) { if (L == 0) { return 0; } else { word_t xx = L - 1; word_t yy = t[xx]; assert(yy < L); /* Remap {t[0..xx-1]} so as to close the hole {yy}: */ word_t y; for (y = 0; y < xx; y++) { assert(t[y] != t[xx]); if (t[y] > t[xx]) { t[y]--; } } /* Get code of reduced perm: */ uint32_t hh = aux(xx); return L*hh + (xx - yy); } } return aux(NW); } bifun_t bifun_ident(void) { return 0; } word_t bifun_apply(bifun_t f, word_t x) { word_t t[NW]; unpack_bifun(f, t); return t[x]; } bifun_t bifun_from_tcgate(tcgate_t g) { bool_t debug = FALSE; word_t t[NW]; uint32_t x; for (x = 0; x < NW; x++) { t[x] = tcgate_apply(g, x); } if (debug) { word_table_print_h(stderr, "\n ( ", t, " ", " )\n"); } return pack_bifun(t); } bifun_t bifun_compose(bifun_t f1, bifun_t f2) { word_t t1[NW]; unpack_bifun(f1, t1); word_t t2[NW]; unpack_bifun(f2, t2); word_t t[NW]; uint32_t x; for (x = 0; x < NW; x++) { t[x] = t2[t1[x]]; } return pack_bifun(t); } void bifun_print_h(FILE *wr, char *pre, bifun_t f, char *suf) { fprintf(wr, "%sf%05d", pre, f); word_t t[NW]; unpack_bifun(f, t); word_table_print_h(wr, " = ", t, " ", suf); } void bifun_print_v(FILE *wr, char *head, int ind, bifun_t f, char *foot) { if (head != NULL) { fprintf(wr, "%s\n", head); } fprintf(wr, "f%05d = ", f); word_t t[NW]; unpack_bifun(f, t); word_table_print_v(wr, ind + 2, t); if (foot != NULL) { fprintf(wr, "%s\n", foot); } } /* ---------------------------------------------------------------------- */ /* ---------------------------------------------------------------------- */