/* Copyright (C) 2008, Chaoji Li<lichaoji@gmail.com> */

#include <stdio.h>

/* Compare result flags. Don't change value assignment */
#define C_EQ       0
#define C_LT       1
#define C_GT       2
#define C_OVERLAP  3
#define C_EMPTY    4

#define REMOVE     1
#define DUP        2

#define MAXLINE    100
#define MAXINPUT   23
#define MAXVECTOR  100
#define MAXBUF     1000

int ninput, noutput;

struct vector {
    char v[MAXINPUT+1];
};

/* U vector: on + off + don't care  */
struct vector u = {"xxxxxxxxxxxxxxxxxxxxxxx"};

struct vector on[MAXVECTOR];
struct vector off[MAXVECTOR];

int table[MAXVECTOR][MAXVECTOR];
int xcost[MAXVECTOR];

int debug = 0;
int non;
int noff;

int nx;
struct vector x[MAXBUF];  /* x = on + don't care = u - off */
int flag[MAXBUF];

void error(const char *s)
{
    fprintf(stderr, "comlog error: %s\n", s);
    exit(1);
}

void mem_usage()
{
    int n;
    n = sizeof(u) + sizeof(on) + sizeof(off) + sizeof(x) + sizeof(table) 
      + sizeof(xcost) + sizeof(flag);
    fprintf(stderr, "Memory usage: %d,%03d Bytes\n", n/1000,n%1000);
}

int compare(struct vector *p, struct vector *q)
{
    int i, r = C_EQ;
    for (i = 0; i < ninput; i++)
        switch (p->v[i] - q->v[i])
        {
            case '0' - '1':
            case '1' - '0':
                return C_EMPTY;

            case 'x' - '0':
            case 'x' - '1':
                r |= C_GT;
                break;
                    
            case '1' - 'x':
            case '0' - 'x':
                r |= C_LT;
                break;
        }

    return r;
}

void init_vector(struct vector *dest, const char *s)
{
    int i;
    for (i = 0; i < ninput; i++)
        dest->v[i] = s[i];
    dest->v[ninput] = 0;
}

int cost(struct vector *p)
{
    int i, cnt;
    for (i = 0, cnt = 0; i < ninput; i++)
    {
        if (p->v[i]!='x') cnt++;
    }
    return cnt;
}

int and(struct vector *p, struct vector *q, struct vector *res)
{
    int i;
    for (i = 0; i < ninput; i++)
    {
        switch (p->v[i] - q->v[i])
        {
            case 0:
            case '1'-'x':
            case '0'-'x':
            {
                res->v[i] = p->v[i];
                break;
            }

            case 'x'-'0':
            case 'x'-'1':
            {
                res->v[i] = q->v[i];
                break;
            }
            
            default:
                return 0;
        }
    }
    return 1;
}

/* p - q => res ... */
int exclude(struct vector *p, struct vector *q, struct vector *res, int n)
{
    int i, k;

    switch (compare(p,q))
    {
        case C_EMPTY:
            if (n < 1) 
                error("exclude: no space");
            *res = *p;
            return 1;
            
        case C_LT:
        case C_EQ:
            return 0;
    }

    k = n;
    for (i = 0; i < ninput; i++)
        switch (p->v[i] - q->v[i])
        {
            case 'x' - '0':
            case 'x' - '1':
                if (k-- < 1) 
                    error("exclude: no space");
                *res = *p;
                res->v[i] = (q->v[i] == '0' ? '1' : '0');
                res++;
                break;
        }

    return n - k;
}

void print(struct vector *pv, int n)
{
    while (n-- > 0) {
        printf("%s\n", pv->v);
        pv++;
    }
}

/*
 * Remove dead vectors, duplicated, and be-contained vectors,
 */
void merge()
{
    int i, j, m;

    m = 0;

    for (i = 0; i < nx; i++)
    {
        if (flag[i] & DUP)
            continue;

        for (j = i + 1; j < nx; j++)
        {
            switch (compare(&x[i], &x[j]))
            {
                case C_EQ:
                {
                    flag[j] |= DUP;
                    break;
                }

                case C_GT:
                {
                    flag[j] |= REMOVE;
                    break;
                }

                case C_LT:
                {
                    flag[i] |= REMOVE;
                    break;
                }
            }
        }

        if (!(flag[i] & REMOVE))
        {
            if (m != i)
                x[m] = x[i];
            m++;
        }
    }

    nx = m;
}

int main(int argc, char *argv[])
{
    FILE * fp;
    char buf[MAXLINE];
    int i, j, outpin, ny, mincost, minx;
    struct vector *y;

    mem_usage();

    if (argc != 2) 
        error("I only takes one argument.");

    fp = fopen(argv[1], "r");

    if (fp == NULL) 
        error("cannot open input file");

    /* We are going to generate output logic for each output pin.
       Start from the first. */
    outpin = 0;

NEXTOUT:

    /* Initialize the number of ON and OFF vectors to ZERO */
    non = 0;
    noff = 0;

    /* The first line of input file is composed by two numbers: 
          ninput  -- Number of input pins;
          noutput -- Number of output pins. */ 

    fgets(buf, MAXLINE, fp);
    sscanf(buf, "%d%d", &ninput, &noutput);

    /* initialize ON and OFF vectors for OUTPIN */
    while (fgets(buf, MAXLINE, fp))
    {
        /* A valid data line should start with '0', '1' or 'x'.
           Here we skip invalid lines. */
        if (buf[0] != '0' && buf[0] != '1' && buf[0] != 'x')
            continue;

        /* The layout of a data line looks like:

           101010010110
           \--v--/\---/
              |     |
            INPUT  OUTPUT
           VECTOR  VECTOR

           In this case, the number of input pins <ninput> is 7, 
           and <noutput> is 5.
           The data line means that with the input "1010100" each output pin 
           should output the value as specified by the output vector "10110",
           i.e. output[0] = 1, output[1] = 0, ... , output[4] = 0.  

           An output value '0' implies that the input vector is an OFF vector 
           for the corresponding output pin.
           The output pin should be OFF under this input vector.

           An output value '1' implies that the input vector is an ON vector 
           for the corresponding output pin.
           The output pin should be ON under this input vector.

           An output value 'x' is ignored.
         */
        switch (buf[ninput+outpin])
        {
            case '0':
                init_vector(&off[noff++], buf);
                break;

            case '1':
                init_vector(&on[non++], buf);
                break;
        }
    }

    /* Now we have read all the data lines, 
       and ON vectors and OFF vectors for output[outpin] is ready.
       Start the logic output phase. */
    printf("output[%d] begin\n", outpin);

    /* X = U - OFF */

    x[0] = u;
    x[0].v[ninput] = 0;

    nx = 1;
    for (i = 0; i < noff; i++)
    {
        int nres;

        nres = nx;

        for (j = 0; j < nx; j++)
        {
            nres += exclude(&x[j], &off[i], &x[nres], MAXBUF-nres);
            flag[j] = DUP;
        }

        for (j = nx; j < nres; j++)
            flag[j] = 0;

        nx = nres;
        merge(); 
    }

    if (nx >= MAXVECTOR)
        error("nx too big");

    y = &x[nx];
    for (i = 0; i < non; i++)
        y[i] = on[i];
    ny = non;

    /* Break down the ON vectors so that each ON vector either belongs to 
     * one X vector or out of it. Mark the relation in table to speed up 
     * further calculation */

    for (i = 0; i < ny; i++)
        for (j = 0; j < nx; j++)
        {
            int comp;

            comp = compare(&y[i], &x[j]);
            if (comp == C_OVERLAP || comp == C_GT)
            {
                struct vector common;

                and(&y[i], &x[j], &common);
                
                ny += exclude(&y[i], &common, &y[ny], MAXBUF-nx-ny);

                if (ny >= MAXVECTOR) 
                    error("ny too big");

                y[i] = common;
            }

            table[i][j] = (comp == C_EMPTY ? 0 : 1);
        }

    for (i = 0; i < nx; i++) 
    {
        flag[i] = 0;
        xcost[i] = cost(&x[i]);
    }

NEXTX:

    /* For each loop, we pick up a x vector as one of our final result,
     * which is an approximately good pick, but not guarranteed as best. */

    minx = -1;
    mincost = 9999;
    for (i = 0; i < nx; i++)
    {
        int n;
        if (flag[i] & REMOVE) 
            continue;
        n = 0;
        for (j = 0; j < ny; j++)
            n += table[j][i];

        if (n == 0)
        {
            flag[i] |= REMOVE;
            continue;
        }

        /* If we are going to adopt this vector, we can eliminate n vectors,
         * with the cost of xcost[i] */
        n = xcost[i]*100/n;
        if (n < mincost)
        {
            mincost = n;
            minx = i;
        }
    }

    /* If minx is not updated, we are done */
    if (minx < 0) 
        goto ENDOUT;
    
    /* Print the picked up vector */
    print(&x[minx], 1);

    flag[minx] |= REMOVE;
    for (i = 0; i < ny; i++)
        if (table[i][minx])
        {
            for (j = 0; j < nx; j++)
                table[i][j] = 0;
        }

    goto NEXTX;

ENDOUT:
    /* Finishing the logic of output[outpin]. */
    printf("output[%d] end\n", outpin);

    /* Goto next output pin */
    if (++outpin < noutput)
    {
        /* We have to start over from the beginning of file */
        fseek(fp, 0, SEEK_SET);
        goto NEXTOUT;
    }

    /* All output logic have been generated. Power off and say good night.*/
    fclose(fp);
}