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

C/C++ Source or Header | 1992-03-12 | 4.8 KB | 154 lines

/****************************************************************************
*
*       Program Name : SSM.C
 *
 *    Written By : Eng-Huat Ong and Kian-Mong Low.
*
*       This program generates the Subsumming Sum of Minterms (SSM) of the
*       given CPT.
*
*    Returns pointer to an array consisting of :
*        1.  no. of X's in the given CPT
*        2.  all minterms covered by the CPT (SSM's)
 *
 * --------------------------------------------------------------------------
 *    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  <stdlib.h>
#include  <string.h>

unsigned char *ssm(d)
unsigned char *d;

{
   unsigned long  m, j, m_cnt, test, terms;
   unsigned char  *e, *temp, *hold, *px;
   unsigned char  nspm, i, k, x_count, cnt, n;

   n = strlen(d);                             /* no. of variables */
   nspm = (n+7)/8;                            /* no. of bytes/minterm */

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

   px = (unsigned char *) malloc(n+1);          /* position of X's in CPT */
   if (px == 0)
      {
     printf("Out of memory -- SSM, *px\n");
     printf("Program terminated - 2\n");
     exit(0);
      }

   /***
    ***  GENERATE 1ST SSM TERM
    ***/

   j = 0;
   x_count = 0;                                     /* no. of X's in CPT */
   m = 0;                                           /* no. of SSM terms */

   for (i=0; i<n; i++)                              /* obtain 1st SSM term */
      {
     if ((i%8) == 0 )
        *(temp+(i/8)) = 0;                      /* reset temp to zero */
     if (*(d+i) == 'X' | *(d+i) == 'x')         /* char in CPT is 'X' */
        {
           x_count++;                           /* no. of X's in CPT */
           *(px + j++) = i;                     /* position of X's */
           *(temp+(i/8)) = *(temp+(i/8)) | (0<<(i%8));
        }
     else if (*(d+i) == '0')                     /* char in CPT is '0' */
        *(temp+(i/8)) = *(temp+(i/8)) | (0<<(i%8));
     else                                        /* char in CPT is '1' */
        *(temp+(i/8)) = *(temp+(i/8)) | (1<<(i%8));
      }

   e = (unsigned char *) malloc(4+nspm*topow(x_count));  /* space for all SSM's */
   if (e == 0)
      {
     printf("Out of memory -- SSM, *e\n");
     printf("Program terminated - 3\n");
     exit(0);
      }

   *e = n;                                   /* no. of variables */
   *(e+3) = nspm;                            /* no. of bytes/minterm */

   memcpy((e+4),temp,nspm);                  /* 1st SSM term */
   m++;                                      /* no. of SSM terms */

   /***
    ***  EXPAND ON 1ST SSM TERM TO GENERATE OTHER SSM TERMS
    ***/

   hold = (unsigned char *) malloc(nspm+1);   /* working array */
   if (hold==0)
      {
     printf("Out of memory -- SSM, *hold");
     printf("Program terminated - 4\n");
     exit(0);
      }

   m_cnt = 0;                            /* counter */

   for (i=0; i<x_count; i++)             /* generate other SSM terms */
      {
     terms = topow(i);               /* no. of terms to generate */

     for (j=1; j<=terms; j++)
        {
           m_cnt++;                  /* determines whether addition is required */
           memcpy(hold, temp, nspm);           /* put in working array */

           for (k=0; k<=i; k++)                /* no. of bits to check */
          {
             test = m_cnt & (1<<k);        /* addition required ? */
             if (test != 0)                /* YES, add to working array */
            *(hold + *(px+k)/8) = *(hold + *(px+k)/8) + topow(*(px+k)%8);
          }

           memcpy((e+4+nspm*m), hold, nspm);      /* add SSM to e-array */
           m++;                                   /* no. of SSM terms */
        }
      }

   free(temp);                  /* free pointers */
   free(px);
   free(hold);

   *(e+1) = x_count;            /* no. of X's in CPT */

   return(e);                   /* return SSM terms */
}