#include <stdio.h>

#define MAX_VARS 4   /* Max # of variables in a product term */
typedef unsigned short WORD;   /* Use 16-bit words */
struct cube {
  WORD t;  /* Bits 1 for uncomplemented variables. */
  WORD f;  /* Bits 1 for complemented variables.   */
};
typedef struct cube CUBE;

int EqualCubes(CUBE C1, CUBE C2) /* Returns true if C1 and C2 are identical.  */
{
  return ( (C1.t == C2.t) && (C1.f == C2.f) );
}

int Oneone(WORD w)     /* Returns true if w has exactly one 1 bit.            */
{				      	  /* Optimizing the speed of this routine is critical    */
  int ones, b;         /*   and is left as an exercise for the hacker.        */
  ones = 0;
  for (b=0; b<MAX_VARS; b++) {
	 if (w & 1) ones++;
	 w = w>>1;
  }
  return((ones==1));
}

int Combinable(CUBE C1, CUBE C2) /* Returns true if C1 and C2 differ in only one variable, */
{                                /* which appears true in one and false in the other.      */
CUBE tcube;

  tcube.t = C1.t ^ C2.t;
  tcube.f = C1.f ^ C2.f;
  return( (tcube.t==tcube.f) && Oneone(tcube.f) );
}


void Combine(CUBE C1, CUBE C2, CUBE *C3)
						/* Combines C1 and C2 using theorem T10, and stores the    */
{  					/*   result in C3.  Assumes Combinable(C1,C2) is true.     */
C3->t = C1.t & C2.t;
C3->f = C1.f & C2.f;
}

void PrintCube(CUBE C)
{
  printf("t:%04x f:%01x\n", C.t, C.f);
}

#define TRUE   1
#define FALSE  0
#define MAX_CUBES 50

void main()
{
  CUBE cubes[MAX_VARS+1][MAX_CUBES];
  int covered[MAX_VARS+1][MAX_CUBES];
  int numCubes[MAX_VARS+1];
  int m;          /* Value of m in an m-cube, i.e., ‘‘level m.’’ */
  int j, k, p;    /* Indices into the cubes or covered array.    */
  CUBE tempCube;
  int found;

  /* Initialize number of m-cubes at each level m. */
  for (m=0; m<MAX_VARS+1; m++)
  numCubes[m] = 0;

  /* Read a list of minterms (0-cubes) supplied by the user, storing them    */
  /* in the cubes[0,j] subarray, setting covered[0,j] to false for each      */
  /* minterm, and setting numCubes[0] to the total number of minterms read.  */
  /* ReadMinterms; */
  cubes[0][0].t = 0x3;
  cubes[0][0].f = 0x0;
  cubes[0][1].t = 0x2;
  cubes[0][1].f = 0x1;
  cubes[0][2].t = 0x6;
  cubes[0][2].f = 0x1;
  cubes[0][3].t = 0x4;
  cubes[0][3].f = 0x3;

  numCubes[0] = 4;

  for (m=0; m<MAX_VARS; m++)            /* Do for all levels except the last */
	 for (j=0; j<numCubes[m]; j++)       /* Do for all cubes at this level    */
		for (k=j+1; k<numCubes[m]; k++)   /* Do for other cubes at this level  */
		  if (Combinable(cubes[m][j], cubes[m][k])) {
				/* Mark the cubes as covered. */
				covered[m][j] = TRUE;  covered[m][k] = TRUE;
				/* Combine into an (m+1)-cube, store in tempCube. */
				Combine(cubes[m][j], cubes[m][k], &tempCube);
				found = FALSE;  /* See if we’ve generated this one before. */
				for (p=0; p<numCubes[m+1]; p++)
				  if (EqualCubes(cubes[m+1][p],tempCube)) found = TRUE;
				if (!found) {  /* Add the new cube to the next level. */
					 numCubes[m+1] = numCubes[m+1] + 1;
					 cubes[m+1][numCubes[m+1]-1] = tempCube;
					 covered[m+1][numCubes[m+1]-1] = FALSE;
				}
  }
  for (m=0; m<MAX_VARS; m++)       /* Do for all levels              */
	 for (j=0; j<numCubes[m]; j++)  /* Do for all cubes at this level */
	 /* Print uncovered cubes – these are the prime implicants. */
		if (!covered[m][j])
		PrintCube(cubes[m][j]);
}