ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng)/ProfitPress-MegaCDROM2.B6I/MISC/EDUCATIO/NTUMIN10.ZIP/READF.C

C/C++ Source or Header | 1992-03-12 | 12.5 KB | 387 lines

/****************************************************************************
 *
 *      Program name : READF.C
 *
 *    Written By : Eng-Huat Ong and Kian-Mong Low.
 *
 *      This program reads the cubes from the input file, converts them to
 *      minterms and then packs them in bits in the main memory.
 *
 *    Returns solution array if cube of all X's found
 *              else an array of minterms
 *
 * --------------------------------------------------------------------------
 *    Copyright (c) 1992. All Rights Reserved. Nanyang Technological
 *    University.
 *
 *    You are free to use, copy and distribute this software and its
 *    documentation providing that:
 *
 *        NO FEE IS CHARGED FOR USE, COPYING OR DISTRIBUTION.
 *
 *        IT IS NOT MODIFIED IN ANY WAY.
 *
 *        THE COPYRIGHT NOTICE APPEAR IN ALL COPIES.
 *
 *    This program is provided "AS IS" without any warranty, expressed or
 *    implied, including but not limited to fitness for any particular
 *    purpose.
 *
 *    If you find NTUMIN fast, easy, and useful, a note or comment would be
 *    appreciated. Please send to:
 *
 *        Boon-Tiong Tan or Othman Bin Ahmad
 *        School of EEE
 *        Nanyang Technological University
 *        Nanyang Avenue
 *        Singapore 2263
 *        Republic of Singapore
 *
 ***************************************************************************/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define mask8 255

unsigned char   *readf(fp, a, ondc)
FILE            *fp;
unsigned char   ondc, *a;

{
   unsigned char   nspm, l, mterm, x, x_count, c, bptr=0, bit_num;
   unsigned char   *temp, *hold, *nn, *cnn, *px, *cube, *p, *b;
   unsigned long   m, k, mlast;
   unsigned short  n, cu, i;
   unsigned long   mem, terms, topow(), m_cnt, test, ccube;
        char   e, j, exist();


   /***
    ***  READ NO. OF VARIABLES AND NO. OF CUBES FROM INPUT FILE
    ***/

   if (ondc == 0)                             /* ON array */
      {
     nn = (unsigned char *) malloc(4);    /* space for no. of var */
     if (nn==0)
        {
           printf("Out of Memory -- READF, *nn\n");
           printf("Program terminated - 1\n");
           exit(0);
        }

     n = 0;
     while (n == 0)                        /* take care of leading blank lines */
        {
           fgets(nn, 4, fp);              /* read no. of variable */
           n = atoi(nn);                  /* ascii to integer */
        }

     if (n > 255)                         /* exceed max limit */
        {
           printf("No. of variables exceeded maximum limit of 255 in input file.\n");
           printf("Program terminated.\n");
           exit(0);
        }

     mlast = 0;                           /* reset no. of minterms */

     nspm = (n+7)/8;                      /* no. bytes/minterm */
     mem  = 4 + nspm;                     /* amount to allocate */

     a = (unsigned char *) malloc(mem);   /* space for a -array */
     if (a==0)
        {
           printf("Out of memory -- READF, *a\n");
           printf("Progam terminated - 2\n");
           exit(0);
        }

     *a     = n;                          /* no. of variable */
     *(a+3) = nspm;                       /* no. of storage per minterm */
      }
   else                                       /* DC array, ondc = 1 */
      {
     n  = *a;                             /* no. of variables */
     nspm = *(a+3);                       /* no. of bytes/minterm */
     mlast = *(a+1) | *(a+2)<<8;          /* no. of minterms from ON array */
     mem = 4 + nspm*(1+mlast);            /* allocate in advance for next term */
      }

   cnn = (unsigned char *) malloc(8);         /* space for no. of cubes */
   if (cnn==0)
      {
     printf("Out of Memory -- READF, *cnn\n");
     printf("Program terminated - 3\n");
     exit(0);
      }

   fgets(cnn, 8, fp);                         /* read no. of cubes */
   cu = atoi(cnn);                            /* ascii to integer */

   /***
    ***  BREAK THE CUBES INTO MINTERMS IF ANY
    ***/

   if (cu != 0)                                   /* cube count not zero */
      {
     cube = (unsigned char *)malloc(n+12);    /* space for cube */
     if (cube==0)
        {
           printf("Out of Memory -- READF, *cube\n");
           printf("Program terminated - 4\n");
           exit(0);
        }
     px = (unsigned char *)malloc(n+1);       /* space for position of X */
     if (px==0)
        {
           printf("Out of Memory -- READF, *px\n");
           printf("Program terminated - 5\n");
           exit(0);
        }
     p = (unsigned char *)malloc(n+1);        /* space for p-array */
     if (p==0)
        {
           printf("Out of Memory -- READF, *p\n");
           printf("Program terminated - 6\n");
           exit(0);
        }
     b = (unsigned char *)malloc(n+1);        /* space for b-array */
     if (b==0)
        {
           printf("Out of Memory -- READF, *b\n");
           printf("Program terminated - 7\n");
           exit(0);
        }
     temp = (unsigned char *) malloc(nspm+1);   /* temporary store */
     if (temp==0)
        {
           printf("Out of Memory -- READF, *temp\n");
           printf("Program terminated - 8\n");
           exit(0);
        }
      }

   m = mlast;                   /* no. of minterms */
   i = 0;

   while (++i<=cu)              /* do for all cubes read */
      {
     x_count = 0;                      /* no. of X's in a cube */
     fgets(cube, n+12, fp);            /* get cube from infile */
     *(cube+n) = '\0';                 /* terminate with NULL string */

     x = 0;
     for (j=n-1; j>=0; j--)            /* reverse the order */
        {
           if (*(cube+j) == 'x' || *(cube+j) == 'X')  /* X encountered */
          {
             *(px+x++) = n-j-1;        /* position of X's in cube */
             *(p+n-j-1) = 1;           /* 1 in p-array indicates a X */
             *(b+n-j-1) = 0;           /* position reset to zero */
             x_count++;                /* no. of X's in a cube */
          }
           else                            /* a 0 or 1 encountered */
          {
             *(p+n-j-1) = 0;           /* 0 in p-array indicates a 0 or 1 */
             *(b+n-j-1) = *(cube+j);   /* position assume input value */
          }
        }

     /***
      ***   CUBE IS A MINTERM, JUST CONVERT IT INTO BINARY FORM, CHECK THAT IT HAS NOT
      ***   EXISTED IN A-ARRAY BEFORE STORING IT IN A-ARRAY
      ***/

     if (x_count == 0)                     /* it is a minterm */
        {
           c=0;                            /* a counter */

           if (n%8 == 0)                   /* multiple of bytes */
          bit_num = 8;
           else                            /* not multiple of bytes */
          bit_num = (n%8);             /* remainder */

           for (j=0; j<nspm; j++)          /* if nspm>1 */
          {
             bptr = 0;                 /* reset bit pointer */
             *(temp+j) = 0;                                     /* reset temporary storage */
             while (bptr++<bit_num || (j!=(nspm-1) && bptr<=8)) /* bit storage operation */
            {
               ccube = *(cube+n-1-c++)-48;                  /* ascii to integer */
               *(temp+j) = ccube<<(bptr-1) | *(temp+j);     /* temporary storage */
            }
          }

           e = exist(temp, a, m);          /* temp exist in A ? */
           if (e == -1)                    /* don't exist */
          {
             memcpy((a+4+nspm*m), temp, nspm);       /* store in a-array */
             m++;                                    /* no. of minterms */
             mem = mem+nspm;                         /* space required */
             a = (unsigned char *) realloc(a, mem);  /* space for a-array */
             if (a==0)
            {
               printf("Out of Memory -- READF, *a\n");
               printf("Program terminated - 9\n");
               exit(0);
            }
          }
        }

     /***
      ***  IF CUBE CONSISTS OF X ONLY, RETURN THE SOLUTION OF ALL X OR ALL -
      ***/

     else if (x_count == n)                  /* cube with all X's */
           {
          *a = n;                            /* no. of variables */
          *(a+1) = 1;                        /* no. of product terms */
          *(a+2) = 0;
          *(a+3) = 0;                        /* indicate soln obtained */

          if (ondc==0 || (ondc==1 && mlast>0))    /* cube with all X's in ON array */
         {
            for (j=0; j<n; j++)
               *(a+4+j) = 'X';                /* solution cube with all X's */
            return (a);                       /* return solution array */
         }
          else                                    /* cube with all X's in DC array */
         {
            for (j=0; j<n; j++)
               *(a+4+j) = '-';                /* solution cube with all - */
            return (a);                       /* return solution array */
         }
           }
    else
       {
           /***
        ***  CUBE WITH SOME X, SO GENERATE THE 1ST MINTERM AND EXPAND TO
        ***  GENERATE ALL OTHER MINTERMS COVER BY THE CUBE. CHECK THAT THEY
        ***  ARE NOT ALREADY PRESENT IN A-ARRAY AND STORE THEM IN A-ARRAY
        ***/

           l=0;                                   /* counters */
           k=0;
           mterm=0;                               /* temporary storage */

           /***
        ***   GENERATE 1ST MINTERM
        ***/

           for (j=0; j<n; j++)                    /* do for no. of var */
          {
             if (*(b+j) == '1')               /* a 1 in bit position */
            mterm += topow(k);            /* convert to binary */
             k++;
             if (k==8 && ++l<=nspm)           /* new byte required */
                {
               *(temp+l-1)=mterm;         /* store the completed byte */
               k=0;                       /* reset counter */
               mterm=0;                   /* reset for new byte */
            }
             if (k==n-8*l)                    /* less than 8-bit remains */
            *(temp+l) = mterm;            /* transfer to temp */
          }

           /***
        ***  STORE 1ST MINTERM IN A-ARRAY IF NOT ALREADY EXISTED
        ***/

           e = exist(temp, a, m);                          /* minterm exist ? */
           if (e == -1)                                    /* don't exist */
          {
             memcpy((a+4+nspm*m), temp, nspm);         /* store in a-array */
             m++;                                      /* no. of minterms */
             mem = mem+nspm;                           /* space required */
             a = (unsigned char *) realloc(a, mem);    /* more space */
             if (a==0)
            {
               printf("Out of Memory -- READF, *a\n");
               printf("Program terminated - 10\n");
               exit(0);
            }
          }

        /***
         ***  EXPAND USING THE 1ST MINTERM BASE ON THE NO. OF X AND THEIR POSITION
         ***/

        hold = (unsigned char *) malloc(nspm+1);       /* temporary storage */
        if (hold==0)
            {
               printf("Out of Memory -- READF, *hold\n");
               printf("Program terminated - 11\n");
               exit(0);
            }

           m_cnt = 0;                  /* counter to simulate binary expansion */

           for (j=0; j<x_count; j++)   /* expand for the no. of X */
          {
             terms = topow(j);     /* no. of terms required in expansion */

             for (k=1; k<=terms; k++)           /* for all required terms */
            {
               m_cnt++;                     /* simulate binary expansion */
               memcpy(hold, temp, nspm);    /* transfer 1st minterm */

               for (l=0; l<=j; l++)         /* no. of times = pos of X */
                   {
                 test = m_cnt & (1<<l);     /* addition required ? */
                 if (test != 0)
                    *(hold + *(px+l)/8) = *(hold + *(px+l)/8)  /* add */
                              + topow(*(px+l)%8);
                  }

               /***
                ***  STORE THE GENERATED MINTERM IF NOT ALREADY EXISTED IN A-ARRAY
                ***/

               e = exist(hold, a, m);      /* minterm exist in a-array ? */

               if (e == -1)                /* don't exist */
                  {
                 memcpy((a+4+nspm*m), hold, nspm);       /* store in a-array */
                 m++;                                    /* no. of minterms */
                 mem = mem+nspm;                         /* space required */
                 a = (unsigned char *) realloc(a, mem);  /* more space */
                 if (a==0)
                    {
                       printf("Out of Memory -- READF, *a\n");
                       printf("Program terminated - 12\n");
                       exit(0);
                    }
                  }
            }
          }
           free(hold);          /* free pointer */
        }
      }

   if (ondc == 0)                   /* ON-array processed */
      free(nn);
   free(cnn);
   if (cu != 0)                     /* cube(s) processed */
      {
     free(cube);                /* free pointers used */
     free(px);
     free(b);
     free(p);
     free(temp);
      }

   if (m > 65535)                   /* max no. of minterms exceeded */
      {
     printf("Maximum number of minterms exceeded !\n");
     printf("Program terminated.\n");
     exit(0);
      }

   *(a+1) = m & mask8;              /* no. of minterms in 2 bytes */
   *(a+2) = m >> 8;

   return(a);                       /* return array of minterms */
}