+----------------------------------------+
|Edit: Wed Dec 22 21:32:28 PST 2004: 	 |
|Author's current address:		 |
|  jesse@ctc.volant.org			 |
|    Ramona, California U.S.A.		 |
|    http://www.ctc.volant.org/		 |
|    http://www.ctc.volant.org/consult/	 |
+----------------------------------------+

From: jesse@gumby.Altos.COM (Jesse Chisholm AAC-RjesseD)
Newsgroups: alt.sources
Subject: Quine McClusky Minimization
Date: 4 Nov 92 18:31:15 GMT
Organization: Altos Computer Systems, San Jose, CA


	My apologies to the many people who pointed out to me that I
responded on alt.sources to a letter that didn't belong on alt.sources.
This was an oversight on my part.  Sadly, my newsreader does not allow
me to cancel that posting.

	Since there were several requests for this code, I am posting it.

	It is written in MICROSOFT C 7.0, but should compile on MSC6.0
as well.  I have not tried to compile it on a UNIX system.  I have not
compiled it with the TURBO-C compiler for several years.  It is rather
non-modular.  Partly because of it's evolution and my evolution.

--- CUT HERE to ROMM.C ---
#define PROG_ID "ROM Minimizer  3.1  (c) Nov  2, 1992, rJc"

/*********************************************************************
*                                                                    *
*             Quine McClusky Boolean Equation Minimizer              *
*                                                                    *
*     Copyright (c) 1988 by Jesse Chisholm, all rights reserved.     *
*                                                                    *
*     This program, and all portions of its source code, were        *
*     produced by and for Jesse Chisholm Associates.                 *
*                                                                    *
*     It has been placed in the PUBLIC DOMAIN as of 90.05.17         *
*                                                                    *
*     For further information, contact:                              *
*                                                                    *
*           Jesse Chisholm                                           *
*           137 East Fremont Avenue #49                              *
*           Sunnyvale, California                                    *
*           U.S.A.     94087-2501                                    *
*                                                                    *
**********************************************************************
*                                                                    *
*     This program is an implimentation of the Quine McClusky        *
*     method for minimizing boolean equations.  This version does N  *
*     parallel equations.  The input lines may be scrambled, as can  *
*     the output lines, if the board layout requires it.             *
*                                                                    *
**********************************************************************

**********************************************************************
*                                                                    *
*   Revision History.                                                *
*                                                                    *
*   Original Version: QM.FOR written in FORTRAN IV on an IBM 360/44  *
*           sometime during college (1975-1982) as a class project.  *
*           It then sat on the shelf until 1988.  Some of the cards  *
*           were damaged, so when it was finally read back in, there *
*           were some errors.  The current FORTRAN source will most  *
*           likely not compile.  (It is available if interested ?)   *
*                                                                    *
*   #define PROG_ID "TCI PLD Minimizer  0.0  (c) May 21, 1988, rJc"  *
*           Initial creation from QM.FOR, written by Jesse Chisholm  *
*           at New Mexico Institute of Mining and Technology, during *
*           the late 1970's.  Various changes were made to accomidate*
*           the language C, and the TCI project.  The sort method    *
*           suggested by Larry Chapman in the original version was   *
*           simplified for use in this version.                      *
*           Implemented in TURBO-C version 1.0                       *
*                                                                    *
*   #define PROG_ID "TCI PLD Minimizer  0.1  (c) May 22, 1988, rJc"  *
*           It reads the display values in from the console, now.    *
*           And it echos them at all stages across the circuit board.*
*           No scrambling is done yet.                               *
*                                                                    *
*   #define PROG_ID "TCI PLD Minimizer  0.2  (c) May 23, 1988, rJc"  *
*           K-MAPs are being generated.  Hooks for scrambling are    *
*           put in.                                                  *
*                                                                    *
*   #define PROG_ID "TCI PLD Minimizer  0.3  (c) May 24, 1988, rJc"  *
*           Some difficulty with cover table.  Array sizes too big   *
*           had to switch to pointers to dynamic memory.             *
*           Added code to print out gate arrangments.                *
*                                                                    *
*   #define PROG_ID "TCI PLD Minimizer  0.4  (c) May 25, 1988, rJc"  *
*           Largest dynamic array was found to be unneeded at all.   *
*           Code changed and memory freed up.   Work better now.     *
*           Added code to invert equations; can now minimize for -Q0 *
*           if that is easier to do than for Q0 itself.  This version*
*           still generates a SUM-OF-PRODUCTS equation for -Qn.  The *
*           original version (QM.FOR) generated a PRODUCT-OF-SUMS for*
*           the inverted Qn.  PLDs are strictly (?) SUM-OF-PRODUCT   *
*           devices though, that can put out Qn or -Qn with equal    *
*           ease.                                                    *
*                                                                    *
*   #define PROG_ID "TCI PLD Minimizer  0.5  (c) May 26, 1988, rJc"  *
*           ADC output bits used to be tied to PLD input bits.       *
*           No longer so.                                            *
*                                                                    *
*   #define PROG_ID "TCI PLD Minimizer  0.6  (c) May 27, 1988, rJc"  *
*           7-Segment mapping from display value only worked for even*
*           number of PLD output bits, due to oversite in code.  It  *
*           is now fixed.                                            *
*                                                                    *
*   #define PROG_ID "TCI PLD Minimizer  1.0  (c) May 31, 1988, rJc"  *
*           A few cosmetic changes.  Released for use by HI-LAB.     *
*                                                                    *
*   #define PROG_ID "ROM Minimizer  2.0  (c) June 1, 1988, rJc"      *
*           Removed all the 7-segment stuff, ADC stuff, and the bit  *
*           scrambling stuff.  This makes it generic to any `ROM'    *
*           style device.                                            *
*                                                                    *
*   #define PROG_ID "ROM Minimizer  2.1  (c) June 3, 1988, rJc"      *
*           Made various corrections to keep it up to date with the  *
*           TCI PLD Minimizer version 1.2.                           *
*                                                                    *
*   #define PROG_ID "ROM Minimizer  3.0  (c) May 17, 1990, rJc"      *
*           Released to the PUBLIC DOMAIN                            *
*                                                                    *
*   #define PROG_ID "ROM Minimizer  3.1  (c) Nov  2, 1992, rJc"      *
*           Re-Released to the PUBLIC DOMAIN                         *
*           Miniscule changes to make contact information up to date.*
*           Minor changes to make in compile under Microsoft C 7.0   *
*           COMPILE: cl -AL romm.c                                   *
*                                                                    *
*                                                                    *
**********************************************************************
*                                                                    *
*   Known Bugs                                                       *
*                                                                    *
*   1    Microsoft C 6.0 Compiler says "code has no effect"          *
*        even though it works.                                       *
*        The lines are marked with "/ * ? * /" at left margin        *
*                                                                    *
*********************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include <time.h>
#include <ctype.h>
#include <assert.h>

typedef unsigned char        byte;
typedef unsigned short        word;
typedef unsigned long        dword;

typedef unsigned char        uchar;
typedef unsigned int        uint;
typedef unsigned long        ulong;

#ifdef TBC
#include <alloc.h>
#define _KEYBRD_READ        0
#define _KEYBRD_READY        1
#else        // must be MSC
#include <malloc.h>
#include <conio.h>
#define coreleft        _memavl
#endif

int ibits  =    8;       /* number of input lines */
int top    =  256;       /* number of input values */
int top8   = 1024;       /* number of temporary work positions */
int nbits  =    8;       /* number of output lines */

#define IBITS   ibits    /* input + calced */
#define TOP     top      /* calced */
#define TOP8    top8     /* calced */
#define NBITS   nbits    /* input + calced */

/* this define is used to calculate the index of wrk */
#define W(i0,w1,i1,w2,i2) (((long)(i0)*(long)(w1)+(long)(i1))*(long)(w2)+(long)(i2))

byte *out;  /*[TOP];                  /* holds hex of display output */
int *eqns;  /*[NBITS][TOP];           /* terms of each equation */
int *lneq;  /*[NBITS];                /* how long is each equation */
byte *wrk;  /*[2*TOP8*IBITS/4];/*nip*//* work area for minimization */
byte *weqn[32]; /*[?*IBITS/4]; /*nip*//* storage for minimized equations */
int *lnweq; /*[NBITS];                /* how long is minimized version */
byte *cof;  /*[TOP];                  /* count times term is covered */
byte *esn;  /*[TOP];                  /* is implicant essential? */
byte *hnd;  /*[TOP/8];         /*bit*//* is term handled? */
byte *clms; /*[TOP];                  /* flags for printing gates */
char *line; /*[TOP];                  /* work area for printing gates */
int show;                             /* flag show intermediate tables? */
int pict;                             /* flag show gate picture? */
int alow;                             /* flag allow inverting function? */
int nvrt[32];                         /* flag function is inverted */
int smry;                             /* flag write summary to file? */
char ofname[100];                     /* where to write it */
FILE *ofp;                            /* Summary File Pointer */
int nterms, mterms;                   /* used in minimization */
int num_esn;                          /* number of essential implicants */
int num_use;                          /* number of implicants in use */
char TCIname[32];                     /* name of TCI version */

void a_mem(char *nme, byte  **bp, long nel, int sz);
void mk_mem(void);
void fr_mem(void);
void rd_file(void);
int yesno(char *s);
void pause(char *s);
void setbits(byte *a, int nb, long ofs, int val);
int getbits(byte *a, int nb, long ofs);
void p_term(FILE *ofp, byte *t, int wt, long ot, int n, char f);
void pr_eqn(FILE *ofp, int *e, int ln, int b, int mnmx);
void pr_esn(FILE *ofp, int b, int nm,
       byte *w, int ww, int wi1, int wf2, int wf3,
       int nb, byte *e, int mnmx);
void merge(byte *a, int wa, long oa,
      byte *b, int wb, long ob,
      byte *c, int wc, long oc,
      int n);
int dist(byte *a, int wa, long oa,
         byte *b, int wb, long ob,
         int n);
int covers(byte *w, int ww, long wo, int t, int n);
void gate1(FILE *ofp, byte *f, int wf, int if1, int wf2, int if2, int wf3,
      int n, int r, int nme, byte *clms, int ln);
void gate2(FILE *ofp, int mnmx, int nme, int bt);
void invert(int *eq, int *ln, int bt);

void main(void)
{
int i,j,k;                    /* generic loop counters */
int bit;                      /* loop counter */
int term;                     /* loop counter */
int ngates, mgates;           /* how many gates needed */
int nlines, mlines;           /* how many lines needed */
int tgates, fgates;           /* totals before and after */
int tlines, flines;           /* totals before and after */
int kmap;                     /* counter for minimization loop */
int q;                        /* which half of wrk is in use */
int num_merges;               /* count of merges this time through */
int uni;                      /* flag checks uniqueness of new item */
char line[100];               /* generic string for input and such */
int max_a, max_b, max_c;      /* used to select non-essential implicant. */
int tmp_a, tmp_b, tmp_c;      /* used in that selection also. */

long t_start, t_end, t_loop, t_tmp; /* used in timing */
long n_iter, iter;                  /* used to keep user from being bored. */


   printf("\033[2J%s\n", PROG_ID);
   printf("\n");
   printf("Quine McClusky Boolean Equation Minimizer\n");
   printf("\n");
   printf("This program was written by Jesse Chisholm.\n");
   printf("It has been placed in the PUBLIC DOMAIN as of 90.05.17\n");
   printf("\n");
   printf("\nFor information concerning this program\n");
   printf("please contact:\n");
   printf("\n");
   printf("               Jesse Chisholm\n");
   printf("               4306 Alum Rock Avenue\n");
   printf("               San Jose, California 95127-2904\n");
   printf("\n");
   printf("                          .......\n");
   printf("                          .     .\n");
   printf("                          . .....\n");
   printf("                      ... . .    \n");
   printf("                      . ... .....\n");
   printf("                      .         .\n");
   printf("                      ...........\n");
   printf("\n");
   pause("to use this program.");
   printf("\033[2J");

   printf("This program will read in the ROM data output for each of\n");
   printf("the ROM address input values.\n");
   printf("\n");
   printf("Then the boolean equations will be generated from that data,\n");
   printf("and those equations will be minimized.\n");
   printf("\n");
   printf("\n");
   printf("\n");
   printf("\n");
   printf("\n");
   printf("Then the equations and the minimized versions will be\n");
   printf("displayed and compared (#gates and #lines).  Finally,\n");
   printf("a picture of the gate arrangement may be drawn.\n");
   printf("\n");
   printf("\n");
   printf("                          .......\n");
   printf("                          .     .\n");
   printf("                          . .....\n");
   printf("                      ... . .    \n");
   printf("                      . ... .....\n");
   printf("                      .         .\n");
   printf("                      ...........\n");
   printf("\n");
   pause("to proceed");
   printf("\n\n");


   memset(nvrt, 0, sizeof(nvrt));

/* read in parameters */

   printf(      "Enter the name of this product ");
   gets(TCIname);
   show = yesno("Do you want to see intermediate tables         : ");
   pict = yesno("Do you want to see gate pictures               : ");
   alow = yesno("Do you allow inverting the equations           : ");
   smry = yesno("Do you want a summary to be put in a file      : ");
   if (!smry)
      ofp = stdout;
   else
   {
      printf( "\nWhat file should the summary be put in         :  ");
      gets(ofname);
      if ((ofp = fopen(ofname, "w")) == NULL)
      {
         printf("can't open `%s', sending to screen.\n", ofname);
         ofp = stdout;
      }
   }
   if (smry)
      fprintf(ofp, "%s\n\n%s\n\n", PROG_ID, TCIname);

   if (yesno(  "Should display information come from a file    : "))
   {  /* read in ibits, nbits, and out[] values from a file */

      rd_file();
   }
   else   /* get display info from the console */
   {
      printf("Enter the number of address bits: ");
      gets(line);
      sscanf(line, "%d", &ibits);
      ibits = (ibits<1) ? 1 : (ibits>32) ? 32 : ibits;

      printf("\nEnter number of data out bits : ");
      gets(line);
      sscanf(line, "%d", &nbits);
      nbits = (nbits<1) ? 1 : (nbits>32) ? 32 : nbits;

      pause("to echo parameters");

/* echo parameters */

      fprintf(ofp, "\n");
      top  = 1 << ibits;
      top8 = top * (ibits - 1);
      fprintf(ofp, "The ROM gets in  %4d bits\n", ibits);
      fprintf(ofp, "The ROM puts out %4d bits\n", nbits);
      fflush(ofp);

/* clear all work areas to 0's */

      mk_mem();

/* read in minterms */

      printf("\n\n%s %d ROM address values.\n\n",
             "Enter the hex output value for each of the", TOP);
      for (i=0; i<TOP; i++)
      {
         printf("ROM address of %02X produces output of :", i);
         gets(line);
         sscanf(line, "%X", &term);
         out[i] = term;
      }
   } /* end of interactive vs file input */

   printf("\n");

   pause("to echo address and output values");

/* echo care terms */

   fprintf(ofp, "\n\n");
   for (i=0; i<4; i++)
   {
      fprintf(ofp, "|  ROM  -> ROM  |");
   }
   fprintf(ofp, "\n");
   for (i=0; i<4; i++)
   {
      fprintf(ofp, "|address  output|");
   }
   fprintf(ofp,  "\n\n");
   for (i=0; i<TOP; i += 4)
   {
      fprintf(ofp, "|  %02X      %02X   |", i+0, out[i+0]);
      fprintf(ofp, "|  %02X      %02X   |", i+1, out[i+1]);
      fprintf(ofp, "|  %02X      %02X   |", i+2, out[i+2]);
      fprintf(ofp, "|  %02X      %02X   |\n", i+3, out[i+3]);
   }
   fflush(ofp);

/* figure out the equations from the input and desired output */

   for (bit=0, pause("to generate the equations");
        bit<NBITS;
        bit++)
   {
      lneq[bit] = 0;

      /* scan through all output values to find when this bit is on */
      /*    when it is, add that input value to the growing equation */

      for (term=0; term<TOP; term++)
      {
         if (out[term] & (1 << bit))
         {
         /* add this term to the equation */

            eqns[bit*TOP+(lneq[bit]++)] = term;
         }
      }
   }

/* echo the equations */

   if (smry)
   {
      for (bit = 0; bit < NBITS; bit++)
      {
         pr_eqn(ofp, eqns, lneq[bit], bit, 0);
      }
      fprintf(ofp, "\n");
   }
   fflush(ofp);

/* calculate #gates and #lines */

   fgates = tgates = 0;
   flines = tlines = 0;
   for (i=0; i<NBITS; i++)
   {
      tgates += lneq[i];          /* stage 1 gates */
      if (lneq[i] > 0)
         tgates++;                /* stage 2 gates */

      tlines += lneq[i] * IBITS;  /* stage 1 lines */
      if (lneq[i] > 0)
         tlines += lneq[i];       /* stage 2 lines */
   }

/* echo gates and lines */

   printf("\nThis will be %d gates, %d input lines to gates, %s\n",
          tgates, tlines, "if unminimized.");
   if (smry)
      fprintf(ofp, "\nThis will be %d gates, %d input lines to gates, %s\n\014",
             tgates, tlines, "if unminimized.");


/* Now minimization starts in earnest */

   time(&t_start);

/* if permitted to invert
      and desirable to invert
         then invert
            echo new terms */

   if (alow)
   {
      for (bit = 0; bit < NBITS; bit++)
      {
         if (lneq[bit] > (TOP / 2))
         {
            invert(eqns, lneq, bit);

            nvrt[bit] = 1;

            printf("\nInverting equation Q%d to -Q%d.\n", bit, bit);

            if (smry)
            {
               fprintf(ofp, "\nInverted equation -Q%d.\n\n", bit);

               pr_eqn(ofp, eqns, lneq[bit], bit, nvrt[bit]);
            }
         }
      }
   }
   fflush(ofp);


/* minimize each equation separately */

   for (bit=0, pause("to minimize the first equation");
        bit<NBITS;
        bit++, pause("to minimize the next equation"))
   {
      fprintf(ofp, "\014\nNow working on %cQ%d\n\n",
         nvrt[bit] ? '/' : ' ', bit);

      if (smry)
         printf("\nNow working on %cQ%d\n\n", nvrt[bit] ? '/' : ' ', bit);

/* echo the equation */

      pr_eqn(ofp, eqns, lneq[bit], bit, nvrt[bit]);
      fprintf(ofp, "\n");
      fflush(ofp);

/* break terms into working copy in binary (nibbles) */

      memset(wrk, 0, (int)(W(1,TOP8,TOP8-1,IBITS,IBITS-1)/
                           (long)4 *
                           (long)sizeof(byte)));

      for (term=0; term<lneq[bit]; term++)
      {
         for (i=0; i<IBITS; i++)
         {
            setbits(wrk, 2, W(0,TOP8,term,IBITS,i),
/*?*/               (0 != (eqns[bit*TOP+term] & (1 << i))) ? 1 : 0 );
         }
      }
      nterms = lneq[bit];

/* check for tautology (and for half-tautology) */
/* or minimize it all */

      if (nterms >= TOP)
      {
         nterms = 1;
         q = 0;
         for (i=0; i<IBITS; i++)
         {
/*?*/       setbits(wrk, 2, W(0, TOP8, 0, IBITS, i), 2);
         }
      }
      else if (nterms == (TOP / 2))
      {
      /* if one bit is constant, all the rest become don't cares */

         for (i=0; i<IBITS; i++)
         {
         int prev, this;
         int cnt;

/*?*/       prev = getbits(wrk, 2, W(0, TOP8, 0, IBITS, i));

            for (cnt=0, term=0; term<nterms; term++)
            {
/*?*/          if ((this=getbits(wrk, 2, W(0,TOP8,term,IBITS,i))) != prev)
               {
                  cnt++;
                  prev = this;
               }
            }
            if (cnt == 0)
            {
            /* found constant bit, other bits run through ALL possible */
            /*       values, hence this minimization step */

               nterms = 1;
               q = 0;
               for (j=0; j<IBITS; j++)
               {
/*?*/             setbits(wrk, 2, W(0, TOP8, 0, IBITS, j), 2);
               }
/*?*/          setbits(wrk, 2, W(0, TOP8, 0, IBITS, i), prev);
               break;
            }
         }
      }

/* just to be sure, drop into the work horse of the minimization code */

/* loop for each K-map */

      for (kmap=0, q = kmap & 1;   /* q says which half of wrk is in use */
           kmap<IBITS;
           kmap++, q = kmap & 1, nterms = mterms)
      {
/*    if should show it, then write out this K-MAP as a cover table */

         if ( show && smry && (nterms > 0) && (lneq[bit] > 0))
         {
            fprintf(ofp, "\n\nQ%d K-MAP %d\n", bit, kmap);
            for (i=IBITS-1; i>=0; i--)
            {
               for (j=0; j<IBITS; j++)
                  fprintf(ofp, " ");
               fprintf(ofp, " ");
               for (j=0; j<lneq[bit]; j++)
                  fprintf(ofp, "%d", 0!=(eqns[bit*TOP+j]&(1<<i)));
               fprintf(ofp, "\n");
            }
            for (i=0; i<nterms; i++)
            {
               p_term(ofp, wrk, 2, W(q,TOP8,i,IBITS,0), IBITS, '\n');
               fprintf(ofp, " ");
               for (term=0; term<lneq[bit]; term++)
                  fprintf(ofp, "%c", covers(wrk,2,W(q,TOP8,i,IBITS,0),
                                            eqns[bit*TOP+term],
                                            IBITS) ? 'x' : ' ');
            }
            fprintf(ofp, "\n");
         }

/* calculate approximately how long this will take */
/* this keeps the user from getting too impatient */

         n_iter = (long)((long)nterms)
                * ((long)nterms-(long)1)
                / (long)2;

         printf("%ld iterations may take %ld seconds ...", n_iter,
                n_iter / ((long)9 * (long)(kmap+1)) );

         time(&t_loop);


/*    clear the COveredFunction array */

         memset(cof, 0, TOP*sizeof(byte));

/*    for each term
         for each other term
            if distance == 1 then */

         fflush(ofp);

         mterms = 0;
         num_merges = 0;
         iter = (long)0;

         for (term=0; term<(nterms-1); term++)
         {
         /* print out current iteration, this not only keeps user occupied */
         /* it also allows the system to check for ^C during this I/O */

            printf(" iter %6ld\b\b\b\b\b\b\b\b\b\b\b\b", iter);
            iter += (long)(nterms-1-term);

            for (i=(term+1); i<nterms; i++)
            {
               if (dist(wrk,2,W(q,TOP8,term,IBITS,0),
                        wrk,2,W(q,TOP8,i,IBITS,0),
                        IBITS) == 1)
               {

/*             merge the two terms into a new implicant */

                  merge(wrk,2,W(q,TOP8,term,IBITS,0),
                        wrk,2,W(q,TOP8,i,IBITS,0),
                        wrk,2,W((1-q),TOP8,mterms,IBITS,0),
                        IBITS);
                  num_merges++;

/*             if this new implicant is not already in the table
                  then add it to the list for next time around */

                  uni = 1;
                  for (j=0; j<mterms && uni; j++)
                  {
                     if (dist(wrk,2,W((1-q),TOP8,j,IBITS,0),
                              wrk,2,W((1-q),TOP8,mterms,IBITS,0),
                              IBITS) == 0)
                     {
                        uni = 0;
                        break;
                     }
                  }
                  if (uni)
                  {
                     mterms++;
                  }

/*             mark both terms as covered at least once */

                  cof[term]++;
                  cof[i]++;

               }
            }
         }

/*    copy any unmerged terms into new list also. */

         for(term=0; term<nterms; term++)
         {
            if (cof[term] == 0)
            {
               merge(wrk,2,W(q,TOP8,term,IBITS,0),
                     wrk,2,W(q,TOP8,term,IBITS,0),
                     wrk,2,W((1-q),TOP8,mterms,IBITS,0),
                     IBITS);
               mterms++;
            }
         }

         time(&t_tmp);
         printf(" actual time: %ld seconds.\n", t_tmp - t_loop);

/*    if no terms merged
         then end of loop early */

         if (num_merges == 0)
         {
            break;
         }
      } /* end of for kmap ... */

      fflush(ofp);

/* echo a cover table of these PRIME IMPLICANTS
      care terms as labels across the top
      implicant number down the left
      mark the care terms that each implicant covers */

      if (show && smry)
      {
         fprintf(ofp, "\014\nPrime Implicants Cover Table for %cQ%d\n\n",
                 nvrt[bit] ? '/' : ' ', bit);
         for (i=IBITS-1; i>=0; i--)
         {
            for (j=0; j<IBITS; j++)
               fprintf(ofp, " ");
            fprintf(ofp, " ");

            for (term=0; term<lneq[bit]; term++)
            {
               fprintf(ofp, "%d", 0!=(eqns[bit*TOP+term] & (1 << i)));
            }
            fprintf(ofp, "\n");
         }

         memset(cof, 0, TOP*sizeof(byte));

         for (i=0; i<nterms; i++)
         {
            p_term(ofp, wrk, 2, W(q,TOP8,i,IBITS,0), IBITS, '\n');
            fprintf(ofp, " ");
            for (term=0; term<lneq[bit]; term++)
            {
            int x;

               x = covers(wrk,2,W(q,TOP8,i,IBITS,0),
                          eqns[bit*TOP+term],
                          IBITS);
               cof[term] += x;
               fprintf(ofp, "%c", x ? 'x' : ' ');
            }
         }
         fprintf(ofp, "\n");
         fflush(ofp);

         pause("to continue");
      }


/* now it is necessary to scan this list of prime implicants to see if */
/* any of them are essential.  That is, if an original term is covered */
/* by only ONE implicant, then that implicant is essential to the function. */

/* if any care term is covered by a single implicant
      mark that implicant as ESSENTIAL
      mark as handled all care terms that this implicant covers */

      memset(esn, 0, TOP*sizeof(int));
      memset(hnd, 0, TOP/8*sizeof(byte));
      num_esn = 0;
      for (term=0; term<lneq[bit]; term++)
      {
         printf("Checking for essentials, %d found so far, testing # %d\r",
                num_esn, term);

         if (cof[term] == 1)
         {
         /* this term is covered only once, we must find which implicant */

            for (i=0; i<nterms; i++)
            {
               if (covers(wrk,2,W(q,TOP8,i,IBITS,0),
                          eqns[bit*TOP+term],
                          IBITS))
               {
               /* we found the implicant, it is essential only if unique */

                  esn[num_esn] = i;
                  for (j=0; j<num_esn; j++)
                  {
                     if (esn[j] == (byte)i)
                        break;
                  }
                  if (j == num_esn)
                  {
                     num_esn++;
                  }
                  for (j=0; j<lneq[bit]; j++)
                  {
                  /* mark all of this implicants covered terms as handled */

                     if (covers(wrk,2,W(q,TOP8,i,IBITS,0),
                                eqns[bit*TOP+j],
                                IBITS))
                        setbits(hnd, 1, (long)j, 1);
                  }
               }
            }
         }
      }
      num_use = num_esn;
      printf("\n");

/* echo essential implicants */

      if (num_esn == 0)
      {
         if (show)
         {
            fprintf(ofp, "\nThere are no ESSENTIAL implicants.\n");
            fprintf(ofp, "Following is ONE way to implement the function.\n");
         }
      }
      else
      {
         if (show)
         {
            fprintf(ofp, "\nThere are %d ESSENTIAL implicants of the function.\n",
                    num_esn);
         }
      }
      fflush(ofp);

/*    if any care terms remained uncovered */
/*       then start picking best non-essential implicants */
/*       to finish covering the care terms */

      for (i=0, term=0; term<lneq[bit]; term++)
         if (getbits(hnd, 1, (long)term) == 0)
            i++;
      if ((i > 0) && show && (num_esn > 0))
      {
         fprintf(ofp, "\n\nThese do not completely cover the function, so it\n");
         fprintf(ofp, "may be finished in various ways,  here is one...\n\n");
      }

      for (; i>0; ) /* until all terms handled */
      {
         for (i=0, term=0; term<lneq[bit]; term++)
            if (getbits(hnd, 1, (long)term) == 0)
               i++;
         printf("There are %d remaining terms %s, making %d final terms.\r",
                i, "uncovered", num_use);

         if (i > 0)
         {
         /* there is an uncovered term left to handle */

            max_a = max_b = max_c = 0;

         /* for each implicant k */

            for (k=0; k<nterms; k++)
            {
               tmp_a = tmp_b = tmp_c = 0;

         /*    for each essential implicant j */

               for (j=0; j<num_use; j++)
               {
         /*       if esn[j] == k */
         /*          continue k loop */

                  if (esn[j] == (byte)k)
                     break;                   /* already in use */
               }
               if (j < num_use)
                  continue; /* the k loop */

         /*    &wrk[(q*TOP8+k)*IBITS+0] is non essential */
         /*    count its stars and also its terms */
         /*       that are uncovered by the essentials */

               tmp_a = k;

               tmp_b = 0;
               for (j=0; j<lneq[bit]; j++)
               {
                  if ((covers(wrk,2,W(q,TOP8,tmp_a,IBITS,0),
                              eqns[bit*TOP+j],
                              IBITS) == 1) &&
                      (getbits(hnd,  1, (long)j) == 0))
                     tmp_b++;
               }

               tmp_c = 0;
               for (j=IBITS-1; j>=0; j--)
                  if (getbits(wrk, 2, W(q,TOP8,k,IBITS,j)) == 2)
                     tmp_c++;

         /* check if this is best so far */
         /*    test is major key: most new terms covered */
         /*            minor key: most stars */

               if (max_b < tmp_b)
               {
                  max_a = tmp_a;
                  max_b = tmp_b;
                  max_c = tmp_c;
               }
               else if (max_b == tmp_b)
               {
                  if (max_c < tmp_c)
                  {
                     max_a = tmp_a;
                     max_c = tmp_c;
                  }
               }
            }

         /* mark this implicant as "inuse" */

            esn[num_use++] = max_a;

         /* mark all its terms as handled */

            for (k=0; k<lneq[bit]; k++)
            {
               if (covers(wrk, 2, W(q,TOP8,max_a,IBITS,0),
                          eqns[bit*TOP+k],
                          IBITS))
               {
                  setbits(hnd, 1, (long)k, 1);
               }
            }
         } /* end if unhandled terms found */
      } /* end until no unhandled terms */
/* until all terms covered */
      fflush(ofp);

/* echo list of implicants that cover the care terms */

      if (show && smry)
      {
         fprintf(ofp, "\014\nFinal Cover Table for Q%d\n\n", bit);
         for (i=IBITS-1; i>=0; i--)
         {
            for (j=0; j<IBITS; j++)
               fprintf(ofp, " ");
            fprintf(ofp, " ");
            for (term=0; term<lneq[bit]; term++)
               fprintf(ofp, "%d", 0!=(eqns[bit*TOP+term] & (1 << i)));
            fprintf(ofp, "\n");
         }
         for (i=0; i<num_use; i++)
         {
            p_term(ofp, wrk, 2, W(q,TOP8,esn[i],IBITS,0),IBITS, '\n');
            fprintf(ofp, " ");
            for (term=0; term<lneq[bit]; term++)
               fprintf(ofp, "%c", covers(wrk,2,W(q,TOP8,esn[i],IBITS,0),
                                         eqns[bit*TOP+term], IBITS)
                                  ? 'x' : ' ');
         }
         fprintf(ofp, "\n");
         fflush(ofp);
      }

/* calculate number of gates and number of lines */

      ngates = lneq[bit] + 1;
      nlines = ngates * IBITS;
      mgates = 0;
      mlines = 0;

      for (i=0; i<num_use; i++)
      {int c;

         for (c=0, j=0; j<IBITS; j++)
            if (getbits(wrk, 2, W(q,TOP8,esn[i],IBITS,j)) != 2)
               c++;

         if (c == 0)         /* This means output may be tied high or low */
         {
            mlines = 1;
            mgates = 0;
         }
         else if (c == 1)    /* this implicant needs no gate, just a line */
            mlines++;
         else /* (c > 1) */  /* this implicant needs a gate and some lines */
         {
            mlines += c;
            mgates++;
         }
      }
      if (num_use > 1)       /* this means a final gate is needed */
      {
         mlines += num_use;
         mgates++;
      }
      fgates += mgates;
      flines += mlines;

/* echo number of gates and number of lines */

      printf("\nUnminimized %sQ%d\n",
             nvrt[bit] ? "(but simplified) " : "", bit);
      pr_eqn(stdout, eqns, lneq[bit], bit, nvrt[bit]);
      printf("\n");
      printf("Unminimized: gates = %4d, lines = %4d\n", ngates, nlines);

      printf("\n  Minimized Q%d\n", bit);
      pr_esn(stdout, bit, num_use, wrk,2,q,TOP8,IBITS, IBITS, esn, nvrt[bit]);
      printf("\n");
      printf("  Minimized: gates = %4d, lines = %4d\n", mgates, mlines);

      if (smry)
      {
         fprintf(ofp, "\014\nUnminimized %sQ%d\n",
                 nvrt[bit] ? "(but simplified) " : "", bit);
         pr_eqn(ofp, eqns, lneq[bit], bit, nvrt[bit]);
         fprintf(ofp, "\n");
         fprintf(ofp, "Unminimized: gates = %4d, lines = %4d\n", ngates, nlines);

         fprintf(ofp, "\n  Minimized Q%d\n", bit);
         pr_esn(ofp, bit, num_use, wrk,2,q,TOP8,IBITS, IBITS, esn, nvrt[bit]);
         fprintf(ofp, "\n");
         fprintf(ofp, "  Minimized: gates = %4d, lines = %4d\n", mgates, mlines);
      }

/* save this minimized equation for later */

      lnweq[bit] = num_use;
      sprintf(line, "weqn[%d]", bit);
      a_mem(line, &weqn[bit], (long)num_use*(long)IBITS, sizeof(byte));
      for (term=0; term<num_use; term++)
         for (i=0; i<IBITS; i++)
            setbits(weqn[bit], 2, W(0,lnweq[bit],term,IBITS,i),
/*?*/               getbits(wrk, 2, W(q,TOP8,esn[term],IBITS,i)));

/* if they want a picture
      then show them a picture */

      fflush(ofp);

      if (pict)
      {
      int ln;

         fprintf(ofp, "\014");
         memset(clms, 0, TOP*sizeof(byte));
         for (term=0; term<num_use; term++)
         {
            for (ln=0, i=0; i<IBITS; i++)
            {
               if (getbits(wrk, 2, W(q,TOP8,esn[term],IBITS,i)) != 2)
                  ln++;
            }
            gate1(ofp, wrk,2,q,TOP8,esn[term],IBITS,
                  IBITS, term, num_use, clms, ln);
         }
         gate2(ofp, nvrt[bit], num_use, bit);
      }
      fflush(ofp);
   } /* end of loop on each equation */

   time(&t_end);

   if (smry)
   {
      printf("\n\n\nTotal minimization from:\n");
      printf("\n      %4d gates, %4d lines\n", tgates, tlines);
      printf("\n   to %4d gates, %4d lines.\n\n", fgates, flines);
      printf("\n\nTotal time spent minimizing is %ld seconds.\n",
              t_end - t_start);
   }

   fflush(ofp);

   if (smry)
   {
      fprintf(ofp, "\014\n%s\n\n%s Original Unminimized\n\n", 
         PROG_ID, TCIname);
      printf("\nPrinting original unminimized equations to disk ...");

      /* print out original equations */

      for (bit=0; bit<NBITS; bit++)
      {
         if (nvrt[bit])
         {
            invert(eqns, lneq, bit);
            pr_eqn(ofp, eqns, lneq[bit], bit, 0);
            invert(eqns, lneq, bit);
         }
         else
         {
            invert(eqns, lneq, bit);             /* this ends up sorting */
            invert(eqns, lneq, bit);             /* the terms */
            pr_eqn(ofp, eqns, lneq[bit], bit, 0);
         }
      }

      fprintf(ofp, "\014\n%s\n\n%s Unminimized (but simplified?)\n\n", 
         PROG_ID, TCIname);
      printf("\nPrinting unminimized (but simplified?) equations to disk ...");

      /* print out original equations */

      for (bit=0; bit<NBITS; bit++)
      {
         pr_eqn(ofp, eqns, lneq[bit], bit, nvrt[bit]);
      }

      /* print out minimized equations */

      fprintf(ofp, "\n\014%s\n\n%s Minimized\n", PROG_ID, TCIname);
      printf("\nPrinting   minimized equations to disk ...");

      for (bit=0; bit<NBITS; bit++)
      {int x,y;

         fprintf(ofp, "\n%cQ%d = ", nvrt[bit] ? '/' : ' ', bit);

         for (term=0; term<lnweq[bit]; term++)
         {
            y = 0;

            fprintf(ofp, "(");
            for (i=0; i<IBITS; i++)
            {
/*?*/          x=getbits(weqn[bit], 2, W(0,lnweq[bit],term,IBITS,i));
               if (x != 2)
               {
                  if (y != 0)
                  {
                     fprintf(ofp, " & ");
                  }
                  fprintf(ofp, "%cX%d", x==1 ? ' ' : '/', i);
                  y++;
               }
            }
            fprintf(ofp, ")\n");
            if (term < (lnweq[bit]-1))
               fprintf(ofp, "    | ");
         } /* end for each term in minimized list */

         if (lnweq[bit] == 0)
            fprintf(ofp, "V-\n");

      } /* end for each equation */

      fprintf(ofp, "\n\n\nTotal minimization from:\n");
      fprintf(ofp, "\n      %4d gates, %4d lines\n", tgates, tlines);
      fprintf(ofp, "\n   to %4d gates, %4d lines.\n\n", fgates, flines);
      fprintf(ofp, "\n\nTotal time spent minimizing is %ld seconds.\n",
               t_end - t_start);

      if (pict)
      {
      int ln;

         fprintf(ofp, "\014\n%s\n\n%s Minimized Gate Pictures\n\n",
                 PROG_ID, TCIname);
         printf("\nPrinting gate pictures to disk ...");

         for (bit=0; bit<NBITS; bit++)
         {
            if (bit > 0)
               fprintf(ofp, "\014");
            fprintf(ofp, "SUM-OF-PRODUCTS gate picture for %cQ%d\n\n",
                    nvrt[bit] ? '/' : ' ', bit);

            memset(clms, 0, TOP*sizeof(byte));
            for (term=0; term<lnweq[bit]; term++)
            {
               for (ln=0, i=0; i<IBITS; i++)
               {
/*?*/             if (getbits(weqn[bit], 2, W(0,lnweq[bit],term,IBITS,i)) != 2)
                     ln++;
               }
               gate1(ofp, weqn[bit],2,0,lnweq[bit],term,IBITS,
                     IBITS, term, lnweq[bit], clms, ln);
            }
            gate2(ofp, nvrt[bit], lnweq[bit], bit);
            fprintf(ofp, "\n");
         }
      }
   }
   fflush(ofp);

   printf("\nPrinting simulation of results to disk ...");

   fprintf(ofp, "\014\n%s\n\n%s Simulation results.\n\n", PROG_ID, TCIname);

   for (i=0; i<4; i++)
   {
      fprintf(ofp, "|  ROM  -> ROM  |");
   }
   fprintf(ofp, "\n");
   for (i=0; i<4; i++)
   {
      fprintf(ofp, "|address  output|");
   }
   fprintf(ofp,  "\n\n");

   for (i=0; i<TOP; i++)
   {
   int rom;

      rom = 0;
      for (bit=0; bit<NBITS; bit++)
      {
      int x;

         x = 0;
         for (term=0; term<lnweq[bit]; term++)
         {
/*?*/       x |= covers(weqn[bit],2,W(0,lnweq[bit],term,IBITS,0),i,IBITS);
         }

         if (nvrt[bit])
         {
            if (!x)
               rom |= (1 << bit);
         }
         else
         {
            if (x)
               rom |= (1 << bit);
         }
      }

      fprintf(ofp,    "|  %02X      %02X", i, rom);
      if ((byte)rom == out[i])
         fprintf(ofp, "   |");
      else
         fprintf(ofp, " * |");

      if ((i % 4) == 3)
         fprintf(ofp, "\n");

   }
   fprintf(ofp, "\n");
   printf("\n");

   fflush(ofp);

   if (smry)
      fclose(ofp);

   fr_mem();

   exit(0);
}

/**************************************************************/
/* Routine mk_mem allocates dynamic memory for the various    */
/* arraies.  If there are any problems, a message is printed  */
/* and the program terminates.                                */
/**************************************************************/
void a_mem(char *nme, byte  **bp, long nel, int sz)
{
   if ((nel * sz) > (long)coreleft())
   {
      fprintf(stderr, "Not enough memory for `%s'.\n", nme);
      exit(1);
   }
   *bp = calloc((uint)nel, sz);
   if (*bp == NULL)
   {
      fprintf(stderr, "Could not allocate memory for `%s'.\n", nme);
      perror("romm");
      exit(1);
   }
}

void mk_mem(void)
{
   a_mem("out",   (byte **)&out,   (long)TOP,                    sizeof(byte));
   a_mem("eqns",  (byte **)&eqns,  (long)TOP*(long)NBITS,        sizeof(int));
   a_mem("lneq",  (byte **)&lneq,  (long)NBITS,                  sizeof(int));
   a_mem("wrk",   (byte **)&wrk,   2L*(long)TOP8*(long)IBITS/4L, sizeof(byte));
   a_mem("lnweq", (byte **)&lnweq, (long)NBITS,                  sizeof(int));
   a_mem("cof",   (byte **)&cof,   (long)TOP,                    sizeof(byte));
   a_mem("esn",   (byte **)&esn,   (long)TOP,                    sizeof(int));
   a_mem("hnd",   (byte **)&hnd,   (long)TOP/8L,                 sizeof(byte));
   a_mem("clms",  (byte **)&clms,  (long)TOP,                    sizeof(byte));
   a_mem("line",  (byte **)&line,  (long)TOP,                    sizeof(char));
}


/**************************************************************/
/* Routine fr_mem returns the dynamic memory to the system    */
/**************************************************************/
void fr_mem(void)
{
int i;

   free(out);
   free(eqns);
   free(lneq);
   free(wrk);
   for (i=0; i<NBITS; i++)
      free(weqn[i]);
   free(lnweq);
   free(cof);
   free(esn);
   free(hnd);
   free(clms);
   free(line);
}

/**************************************************************/
/* Routine rd_file gets the important input information from  */
/* the file that the global variable `ofp' points to.         */
/*                                                            */
/* format is:                                                 */
/*       line 1   :  d     decimal number of address bits     */
/*            2   :  d     decimal number of data out bits    */
/*            3-? :  HH    hex display values for each of the */
/*                         possible ADC output values.        */
/*                                                            */
/**************************************************************/
void rd_file(void)
{
FILE *fp;
char line[100];
int i, ans;

   printf("\nFile format is: line  1  : dd ; decimal number of address bits\n");
   printf(  "                line  2  : dd ; decimal number of output bits\n");
   printf(  "                lines 3-?: HH ; hex output for each address.\n\n");
   printf("\nWhat file to read data from                    :  ");
   gets(line);

   if((fp = fopen(line, "r")) == NULL)
   {
      printf("cannot open `%s'\n", line);
      exit(1);
   }
   fgets(line, 99, fp); sscanf(line, "%d", &ibits);
   ibits = (ibits<1) ? 1 : (ibits>8) ? 8 : ibits;
   fgets(line, 99, fp); sscanf(line, "%d", &nbits);
   nbits = (nbits<1) ? 1 : (nbits>8) ? 8 : nbits;

   fprintf(ofp, "\n");
   top  = 1 << ibits;
   top8 = top * (ibits-1);
   fprintf(ofp, "The ROM gets in  %4d bits\n", ibits);
   fprintf(ofp, "The ROM puts out %4d bits\n", nbits);
   if (smry)
   {
      printf("The ROM gets in  %4d bits\n", ibits);
      printf("The ROM puts out %4d bits\n", nbits);
   }

   mk_mem();

   printf("Reading values in ...");
   for (i=0; i<TOP; i++)
   {
      fgets(line, 99, fp);
      sscanf(line, "%02X", &ans);
      out[i] = ans;
      printf("Value %02X => %02X\r", i, ans);
   }
   printf("\n");

   fclose(fp);
}

/**************************************************************/
/* function yesno prompts with the given string and waits for */
/* Y or N response.                                           */
/*                 Return value == 1 iff Y, 0 iff N           */
/**************************************************************/
int yesno(char *s)
{
char c;

   for (c='x'; c!='Y' && c!='N';)
   {
      printf("%s?",s);
#ifdef TBC
      while (!bioskey(_KEYBRD_READY))
         ;
      c = toupper(bioskey(_KEYBRD_READ));
#else
      c = toupper(getch());
#endif
      printf("%s\n", c=='Y'?"Yes":c=='N'?"No":"Please type `Y' or `N'");
   }
   return(c=='Y');
}

/**************************************************************/
/* Routine pause prompts with the string given and then waits */
/* for any key to be typed.                                   */
/*                                                            */
/* NOTE: no action is taken if the global flag `smry' if true */
/**************************************************************/
void pause(char *s)
{
char c;

   if (smry)
      return;

   printf("\nType any key %s ", s);
#ifdef TBC
   while (!bioskey(_KEYBRD_READY))
      ;
   c = bioskey(_KEYBRD_READ);
#else
   c = getch();
#endif
   printf("\n");
}

/**************************************************************/
/* routine setbits treats the byte array as a bit array       */
/* it sets the element specified to the given value           */
/**************************************************************/
void setbits(byte *a, int nb, long ofs, int val)
/* a    is address of beginning of bit array */
/* nb   is number of bits per element */
/* ofs  is which element (0 based) */
/* val  is the value to be placed */
{
int *p;
int mask;

   p = (int*)(a + (ofs*nb / 8));   /* points to byte where field begins */
   mask = ((1 << nb) - 1) << (ofs*nb % 8);   /* ones in field position */
   *p &= ~mask;                              /* turn off those bits */
   *p |= ((val << (ofs*nb % 8)) & mask);     /* put in value */
}

/**************************************************************/
/* routine getbits treats the pointer as the address of a bit */
/* array, it then returns the value of the element specified  */
/**************************************************************/
int getbits(byte *a, int nb, long ofs)
/* a    is address of beginning of bit array */
/* nb   is number of bits per element */
/* ofs  is which element (0 based) */
{
int *p;
int mask;

   p = (int*)(a + (ofs*nb / 8));   /* points to byte where field begins */
   mask = ((1 << nb) - 1) << (ofs*nb % 8);   /* ones in field position */
   return((*p & mask) >> (ofs*nb % 8));
}

/**************************************************************/
/* routine p_term prints out an implicant in extended binary  */
/**************************************************************/
void p_term(FILE *ofp, byte *t, int wt, long ot,
       int n, char f)
{
int i;
int x;

   if (f)
      fprintf(ofp, "%c", f);
   for (i=n-1; i>=0; i--)
   {
      fprintf(ofp, "%c", (x=getbits(t, wt, ot+i))==0?'0':x==1?'1':'*');
   }
}

/**************************************************************/
/* routine pr_eqn prints out an equation in condensed hex form*/
/**************************************************************/
void pr_eqn(FILE *ofp, int *e, int ln, int b, int mnmx)
{
int ll, i;
char line[100];

   sprintf(line, "\n%cQ%d", mnmx ? '/' : ' ', b);
   ll = strlen(line);
   fprintf(ofp, "%s", line);
   if (ln == 0)
   {
      fprintf(ofp, " = V-");
   }
   else
      for (i=0; i<ln; i++)
      {
         sprintf(line, " %c %02X", (i==0 ? '=' : '+'), e[b*TOP+i]);
         fprintf(ofp, "%s", line);
         ll += strlen(line);
         if (ll > 64)
         {
            sprintf(line, "\n%cQ%d", mnmx ? '/' : ' ', b);
            ll = strlen(line);
            fprintf(ofp, "\n%*s", ll-1, " ");
         }
      }
   fprintf(ofp, "\n");
}

/**************************************************************/
/* routine pr_esn prints out a minimized equation in extended */
/* binary form.                                               */
/**************************************************************/
void pr_esn(FILE *ofp, int b, int nm,
       byte *w, int ww, int wi1, int wf2, int wf3,
       int nb, byte *e, int mnmx)
{
int ll, i;
char line[100];

   sprintf(line, "\n%cQ%d", mnmx ? '/' : ' ', b);
   ll = strlen(line);
   fprintf(ofp, "%s", line);
   if (nm == 0)
   {
      fprintf(ofp, " = V-");
   }
   else
      for (i=0; i<nm; i++)
      {
         fprintf(ofp, " %c", (i==0) ? '=' : '+');
         ll += 2;

         p_term(ofp, w, ww, W(wi1,wf2,e[i],wf3,0), nb, ' ');
         ll += nb+1;

         if (ll > 64)
         {
            sprintf(line, "\n%cQ%d", mnmx ? '/' : ' ', b);
            ll = strlen(line);
            fprintf(ofp, "\n%*s", ll-1, " ");
         }
      }

   fprintf(ofp, "\n");
}

/**************************************************************/
/* routine merge does just that, merges two implicants into a */
/* third position.                                            */
/**************************************************************/
void merge(byte *a, int wa, long oa,
      byte *b, int wb, long ob,
      byte *c, int wc, long oc,
      int n)
{
int i, x;

   for (i=0; i<n; i++)
   {
      setbits(c, wc, oc+i, (x=getbits(a, wa, oa+i)));
      if (x != getbits(b, wb, ob+i))
         setbits(c, wc, oc+i, 2);
   }
}

/**************************************************************/
/* function dist calculates the distance between implicants   */
/* the resulting value is returned                            */
/**************************************************************/
int dist(byte *a, int wa, long oa,
         byte *b, int wb, long ob,
         int n)
{
int i,d;

   for (d=0, i=0; i<n; i++)
   {
      if (getbits(a, wa, oa+i) != getbits(b, wb, ob+i))
         d++;
   }

   return (d);
}

/**************************************************************/
/* function covers checks to see if an implicant does indeed  */
/* imply a given term.                                        */
/**************************************************************/
int covers(byte *w, int ww, long wo,
           int t, int n)
{
int i;
byte tt[32];

/* first break the term into a bit array */

   for (i=31; i>=0; i--)
   {
      tt[i] = (0 != (t & (1 << i)));
   }

/* then check each non-star for a match with the term */

   for (i=n-1; i>=0; i--)
   {
   int x;

      if ((x = getbits(w, ww, wo+i)) < 2)
         if ((byte)x != tt[i])
            return(0);
   }
   return(1);
}

/**************************************************************/
/* routine gate1 prints out an AND gate with appropriate      */
/* input lines labeled.  The outputs of previous gates are    */
/* carried down the page with this new one.                   */
/**************************************************************/
void gate1(FILE *ofp, byte *f, int wf, int if1, int wf2, int if2, int wf3,
      int n, int r, int nme, byte *clms, int ln)
{
int i, x;
char trms[32][5];

   memset(trms, ' ', sizeof(trms));
   memset(line, 0, TOP*sizeof(char));

   /* carry all previous terms down */

   for (i=0; i<=nme; i++)
   {
      line[i] = ' ';
      if (clms[i] == 1)
         line[i] = '|';
   }

   /* and add the current term for later */

   clms[nme - r] = 1;

   /* if this gate has only one (or no) input line, handle it here */

   if (ln <= 1)
   {
      fprintf(ofp, "%14c%s\n", ' ', line);
      fprintf(ofp, "%14c%s\n", ' ', line);

      for (i=0; i<(nme-r); i++)
         line[i] = '-';
      line[nme-r] = '.';

      for (i=0; i<n; i++)
         if ((x=getbits(f, wf, W(if1,wf2,if2,wf3,i))) != 2)
            break;
      sprintf(trms[i], "%cX%d", x==0 ? '/' : ' ', i);

      if (ln == 0)
         fprintf(ofp, " %3s----------%s\n", "V+ ", line);
      else
         fprintf(ofp, " %3s----------%s\n", trms[i], line);

      for (i=0; i<(nme-r); i++)
         line[i] = ' ';
      line[nme-r] = '|';

      fprintf(ofp, "%14c%s\n", ' ', line);
      fprintf(ofp, "%14c%s\n", ' ', line);
      fprintf(ofp, "%14c%s\n", ' ', line);
      fprintf(ofp, "%14c%s\n", ' ', line);
      fprintf(ofp, "%14c%s\n", ' ', line);
   }
   else /* there are 2 or more input lines to this gate */
   {
      /* load names of factors in this term */
      for (i=0; i<n; i++)
      {
         x = getbits(f, wf, W(if1,wf2,if2,wf3,i));
         if (x == 2)
            trms[i][3] = '\0';
         else
            sprintf(trms[i], "%cX%d", ((x == 0) ? '/' : ' '), i);
      }

      /* write out the gate */

      fprintf(ofp, "     ---      %s\n", line);
      fprintf(ofp, " %3s|%3s|     %s\n", trms[0], " A ", line);
      fprintf(ofp, " %3s|%3s|     %s\n", trms[1], " N ", line);
      fprintf(ofp, " %3s|%3s|     %s\n", trms[2], " D ", line);
      for (i=3; i<n; i++)
      {
      fprintf(ofp, " %3s|   |     %s\n", trms[i], line);
      }

      for (i=0; i<(nme-r); i++)
         line[i] = '-';
      line[nme-r] = '.';
      fprintf(ofp, "     ---------%s\n", line);

      for (i=0; i<(nme-r); i++)
         line[i] = ' ';
      line[nme-r] = '|';
      fprintf(ofp, "%14c%s\n", ' ', line);
      fprintf(ofp, "%14c%s\n", ' ', line);
      fprintf(ofp, "%14c%s\n", ' ', line);
   }
}

/**************************************************************/
/* routine gate2 prints out an OR gate wide enough to grab all*/
/* the AND gates that descend to it.                          */
/**************************************************************/
void gate2(FILE *ofp, int mnmx, int nme, int bt)
{
int i;

/* if there were no previous gates, or only one gate, then no OR gate needed */
   if (nme <= 1)
   {
      if (nme < 1)
      {
         fprintf(ofp, " V- ----------.\n");
      }
   /* only one essential, it is `f' */
      fprintf(ofp, "%15c|\n", ' ');
      fprintf(ofp, "%15c|\n", ' ');
      fprintf(ofp, "%15c|\n", ' ');
      fprintf(ofp, "%14c%cQ%d\n", ' ', mnmx ? '/' : ' ', bt);
   }
   else /* more than one previous gate, so OR gate is needed */
   {
   /* several gates have lines feeding down to here */

      fprintf(ofp, "%13c", ' ');
      for (i=0; i<(nme+4); i++)
         fprintf(ofp, "-");
      fprintf(ofp, "\n");

      fprintf(ofp, "%13c|%*c|\n", ' ', nme+2, ' ');
      fprintf(ofp, "%13c|%*c%s%*c|\n",
                   ' ', nme/2, ' ', "OR", nme/2 + nme%2, ' ');
      fprintf(ofp, "%13c|%*c|\n", ' ', nme+2, ' ');
      fprintf(ofp, "%13c", ' ');
      for (i=0; i<(nme+4); i++)
         fprintf(ofp, "-");
      fprintf(ofp, "\n");
      fprintf(ofp, "%15c|\n%15c|\n%15c|\n%14c%cQ%d\n",
                   ' ', ' ', ' ', ' ', mnmx ? '/' : ' ', bt);
   }
   fprintf(ofp, "\n\n\n");
}

/**************************************************************/
/* routine invert replaces the terms in the equation array    */
/* with the inverse of the array; i.e., every term that is NOT*/
/* in the list already will be there when finished, and every */
/* term that is in the list now is removed.                   */
/**************************************************************/
void invert(int *eq, int *ln, int bt)
{
/* eq[NBITS][TOP] */
/* ln[NBITS]
/* bt is bit number */
int i;
int *buf;

/* first make room for the temporary list */

   a_mem("buf", (byte **)&buf, (long)TOP, sizeof(int));

/* and fill it with all possible terms */

   for (i=0; i<TOP; i++)
      buf[i] = i;

/* remove the terms that are already in the list */

   for (i=0; i<ln[bt]; i++)
      buf[eq[bt*TOP+i]] = -1;

/* finally, count up and store away the remaining (inverted) list */

   ln[bt] = 0;
   for (i=0; i<TOP; i++)
      if (buf[i] >= 0)
         eq[bt*TOP+(ln[bt]++)] = buf[i];

/* return temporary space to system */

   free(buf);
}
--- END OF CUT TO ROMM.C ---
Jesse Chisholm          | Disclaimer: My opinions are rarely understood, let
                        | tel: 1-408-432-6200 | alone held, by this company.
jesse@gumby.altos.com   | fax: 1-408-434-0273 |-----------------------------
======== This company has officially disavowed all knowledge of my opinions.
-- 
"Question Authority!"  -- Wallace Stegner
"And that's an order!"