home *** CD-ROM | disk | FTP | other *** search
/ ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng) / ProfitPress-MegaCDROM2.B6I / MISC / EDUCATIO / NTUMIN10.ZIP / LOGMIN_A.C < prev    next >
Encoding:
C/C++ Source or Header  |  1992-03-12  |  16.7 KB  |  512 lines
  1. /****************************************************************************
  2.  *
  3.  *      Program name : LOGMIN_A.C
  4.  *
  5.  *    Written By : Eng-Huat Ong and Kian-Mong Low.
  6.  *
  7.  *      This is where the original LOGMIN algorithmn is implemented.
  8.  *
  9.  * --------------------------------------------------------------------------
  10.  *    Copyright (c) 1992. All Rights Reserved. Nanyang Technological
  11.  *    University.
  12.  *
  13.  *    You are free to use, copy and distribute this software and its
  14.  *    documentation providing that:
  15.  *
  16.  *        NO FEE IS CHARGED FOR USE, COPYING OR DISTRIBUTION.
  17.  *
  18.  *        IT IS NOT MODIFIED IN ANY WAY.
  19.  *
  20.  *        THE COPYRIGHT NOTICE APPEAR IN ALL COPIES.
  21.  *
  22.  *    This program is provided "AS IS" without any warranty, expressed or
  23.  *    implied, including but not limited to fitness for any particular
  24.  *    purpose.
  25.  *
  26.  *    If you find NTUMIN fast, easy, and useful, a note or comment would be
  27.  *    appreciated. Please send to:
  28.  *
  29.  *        Boon-Tiong Tan or Othman Bin Ahmad
  30.  *        School of EEE
  31.  *        Nanyang Technological University
  32.  *        Nanyang Avenue
  33.  *        Singapore 2263
  34.  *        Republic of Singapore
  35.  *
  36.  ***************************************************************************/
  37.  
  38. #include <stdio.h>
  39. #include <stdlib.h>
  40. #include <string.h>
  41. #define mask8 255
  42.  
  43. unsigned char   *logmin_a(a, b)              /* pointer to a & b array passed */
  44. unsigned char   *a, *b;
  45.  
  46. {
  47.    unsigned short   pterm, ma, mb, pos;
  48.    unsigned short   *ca, *mp, m_cnt;
  49.    unsigned long    m, j, size, addr, count, count1, topow();
  50.    register long    i, wo, wi;
  51.          char   test;
  52.    unsigned  char   *c, *d, *e, *s, *temp, *cp, *mt, *at, *ad;
  53.    unsigned  char   n, adj, adj0, adji, adjacency(), nspm, cover;
  54.    unsigned  char   *adjacent(), *reduce(), *cpt(), *ssm(), adj_of_mi();
  55.  
  56.  
  57.    mb = *(b+2)<<8 | *(b+1);            /* no. of minterms in b-array */
  58.  
  59.    n    = *a;                          /* no. of variables */
  60.    nspm = *(a+3);                      /* no. of bytes/minterm */
  61.    ma = *(a+2)<<8 | *(a+1);           /* no. of minterms in a-array */
  62.  
  63.    temp = (unsigned char *) malloc(nspm+1);        /* temporary storage */
  64.    if (temp == 0)
  65.       {
  66.      printf("Out of memory -- LOGMIN_A, *temp\n");
  67.      printf("Program terminated - 1\n");
  68.      exit(0);
  69.       }
  70.  
  71.    s = (unsigned char *) malloc(4);                /* header of s-array */
  72.    if (s == 0)
  73.       {
  74.      printf("Out of memory -- LOGMIN_A, *s\n");
  75.      printf("Program terminated - 2\n");
  76.      exit(0);
  77.       }
  78.  
  79.  
  80.    /***********\
  81.     * PHASE I *
  82.    \***********/
  83.  
  84.    pterm = 0;                                /* no. of product term */
  85.    count = 0;                                /* no. of terms stored for phase II */
  86.  
  87.    /***
  88.     ***  DETERMINE ADJACENCY OF ALL MINTERMS AND GENERATE THEIR CPT
  89.     ***/
  90.  
  91.    for (i=0; i<mb; i++)                      /* for all minterms in b-array */
  92.       {
  93.      *b = n;                             /* assign back to n */
  94.  
  95.      memcpy(temp, (b+4+nspm*i), nspm);   /* pick a minterm from b-array */
  96.      c = adjacent(temp, a, 255);         /* obtain the adjacent terms */
  97.      adj = *(c+1);                       /* adjacency of minterm */
  98.      d = cpt(c);                         /* generate CPT */
  99.  
  100.      /***
  101.       ***  MINIMIZE ALL MINTERMS WITH ADJACENCY OF 0 & 1 FIRST
  102.       ***/
  103.  
  104.      if (adj <= 1)                       /* adjacency 0 or 1 */
  105.         {
  106.            s = (unsigned char *) realloc(s,4+n*(pterm+1));   /* more space */
  107.            if (s == 0)
  108.           {
  109.              printf("Out of memory -- LOGMIN_A, *s\n");
  110.              printf("Program terminated - 3\n");
  111.              exit(0);
  112.           }
  113.            memcpy ((s+4+n*pterm),d,n);   /* add CPT to soln array */
  114.            pterm++;                      /* product term count */
  115.  
  116.            b = reduce(c,b,i);            /* remove minterms covered from b-array */
  117.            i = (char) *b;                /* index pointer of b-array */
  118.            mb = *(b+2)<<8 | *(b+1);      /* value of mb altered in b-array */
  119.         }
  120.      else                                /* adj > 1 */
  121.         {
  122.  
  123.            /***
  124.         ***  MINTERMS WITH ADJACENCY GREATER THAN 1, GENERATE SSM AND TEST FOR COVERAGE
  125.         ***/
  126.  
  127.            e = ssm(d);                          /* generate SSM */
  128.            m = topow(*(e+1));                   /* no. of SSM terms */
  129.  
  130.            for (j=0; j<m; j++)                  /* check for SSM coverage */
  131.           {
  132.              memcpy (temp, (e+4+nspm*j), nspm);   /* pick SSM term */
  133.              test = exist (temp, a, ma);
  134.              if (test == -1)                /* minterm not in a-array */
  135.             break;
  136.           }
  137.  
  138.            /***
  139.         ***  ALL SSM COVERED BY THE FUNCTION, SELECT CPT AS PRODUCT TERM
  140.         ***/
  141.  
  142.            if (test == 0)                        /* all SSM's covered by fn */
  143.           {
  144.              if (m > 65536)                  /* too many SSM terms */
  145.             {
  146.                printf("Product Term Too Huge \n");
  147.                printf("Program terminated \n");
  148.                exit(0);
  149.             }
  150.              *e = n;                         /* no. of variables */
  151.              *(e+1) = (m-1) & mask8;         /* no. of SSM terms minus 1 */
  152.              *(e+2) = (m-1)>>8 & mask8;
  153.              b = reduce(e,b,i);              /* remove minterms covered from b-array */
  154.              i = (char) *b;                  /* index pointer of b-array */
  155.              mb = *(b+2)<<8 | *(b+1);        /* no. of minterms in b-array */
  156.  
  157.              s = (unsigned char *) realloc(s, 4+n*(pterm+1)); /* more space */
  158.              if (s == 0)
  159.             {
  160.                printf("Out of memory -- LOGMIN_A, *s\n");
  161.                printf("Program terminated - 4\n");
  162.                exit(0);
  163.             }
  164.              memcpy((s+4+n*pterm),d,n);     /* add CPT to soln array */
  165.              pterm++;                       /* no. of product terms */
  166.           }
  167.            else
  168.           {
  169.              /***
  170.               ***  NOT COVERED, STORE UNCOVERED MINTERMS, ITS CORRESPONDING
  171.               ***  ADJACENCY, ADJACENT TERMS AND CPT FOR PHASE II
  172.               ***/
  173.  
  174.              count++;                       /* no. of terms for phase II */
  175.              if (count==1)                  /* 1st uncovered term */
  176.             {
  177.                ad = (unsigned char *) malloc(1);    /* array of adjacency */
  178.                if (ad==0)
  179.                   {
  180.                  printf("Out of memory -- LOGMIN_A, *ad\n");
  181.                  printf("Program terminated - 5\n");
  182.                  exit(0);
  183.                   }
  184.                cp = (unsigned char *) malloc(n);     /* array of CPT's */
  185.                if (cp==0)
  186.                   {
  187.                  printf("Out of memory -- LOGMIN_A, *cp\n");
  188.                  printf("Program terminated - 6\n");
  189.                  exit(0);
  190.                   }
  191.                mt = (unsigned char *) malloc(4+nspm*count);  /* array of minterms */
  192.                if (mt==0)
  193.                   {
  194.                  printf("Out of memory -- LOGMIN_A, *mt\n");
  195.                  printf("Program terminated - 7\n");
  196.                  exit(0);
  197.                   }
  198.                size = 4 + nspm*(1+adj);                         /* addr counter of at-array */
  199.                at = (unsigned char *) malloc (4+nspm*(1+adj));  /* all adj terms from c-arrays */
  200.                if (at==0)
  201.                   {
  202.                  printf("Out of memory -- LOGMIN_A, *at\n");
  203.                  printf("Program terminated - 8\n");
  204.                  exit(0);
  205.                   }
  206.                ca = (unsigned short *) malloc(2);          /* array of addr of at-array */
  207.                if (ca==0)
  208.                   {
  209.                  printf("Out of memory -- LOGMIN_A, *ca\n");
  210.                  printf("Program terminated - 9\n");
  211.                  exit(0);
  212.                   }
  213.                addr = 0;         /* starting address of at-array */
  214.             }
  215.              else                    /* subsequent uncovered terms */
  216.             {
  217.                ad = (unsigned char *) realloc(ad, count);    /* adjacency */
  218.                if (ad==0)
  219.                   {
  220.                  printf("Out of memory -- LOGMIN_A, *ad\n");
  221.                  printf("Program terminated - 10\n");
  222.                  exit(0);
  223.                   }
  224.                cp = (unsigned char *) realloc(cp,n*count);    /* CPT's */
  225.                if (cp==0)
  226.                   {
  227.                  printf("Out of memory -- LOGMIN_A, *cp\n");
  228.                  printf("Program terminated - 11\n");
  229.                  printf("n = %d, count = %d\n", n, count);
  230.                  exit(0);
  231.                   }
  232.                mt = (unsigned char *) realloc(mt,4+nspm*count); /* minterms */
  233.                if (mt==0)
  234.                   {
  235.                  printf("Out of memory -- LOGMIN_A, *mt\n");
  236.                  printf("Program terminated - 12\n");
  237.                  exit(0);
  238.                   }
  239.                size+=4+nspm*(1+adj);                     /* addr counter of at-array */
  240.                at = (unsigned char *) realloc (at,size); /* all adj terms from c-arrays */
  241.                if (mt==0)
  242.                   {
  243.                  printf("Out of memory -- LOGMIN_A, *mt\n");
  244.                  printf("Program terminated - 13\n");
  245.                  exit(0);
  246.                   }
  247.                ca = (unsigned short *) realloc(ca,2*count);       /* addr of at-array */
  248.                if (ca==0)
  249.                   {
  250.                  printf("Out of memory -- LOGMIN_A, *ca\n");
  251.                  printf("Program terminated - 14\n");
  252.                  exit(0);
  253.                   }
  254.             }
  255.  
  256.              /***
  257.               ***  STORE IN ARRAYS FOR PHASE II
  258.               ***/
  259.  
  260.              *(ad+(count-1)) = adj;                           /* adjacency */
  261.              memcpy((cp+n*(count-1)),d,n);                    /* CPT's */
  262.              memcpy((mt+4+nspm*(count-1)),(b+4+nspm*i),nspm); /* minterms */
  263.              memcpy((at+addr),c,4+nspm*(1+adj));              /* adj terms */
  264.              *(ca+(count-1)) = addr;                   /* addr of at-array */
  265.              addr = size;                              /* update addr */
  266.           }
  267.            free(e);                       /* free pointer */
  268.         }
  269.      free(c);                     /* free pointers */
  270.      free(d);
  271.       }
  272.    count1 = count;                   /* no. of terms for phase II */
  273.  
  274.  
  275.    /************\
  276.     * PHASE II *
  277.    \************/
  278.  
  279.    while (count > 0)               /* some terms stored for phase II */
  280.       {
  281.      /***
  282.       ***  SELECT NEXT MINTERM WITH THE LOWEST ADJACENCY AND AT LEAST ONE OF
  283.       ***  ITS ADJACENT TERMS PREVIOUSLY COVERED
  284.       ***/
  285.  
  286.      adj0 = 255;               /* set to max of 8-bit */
  287.  
  288.      for (i=0; i<count1; i++)               /* do for all adj terms in phase II */
  289.         {
  290.            if (*(ad+i)<adj0 && *(ad+i)!=0)  /* choose minterms with lowest adj */
  291.           {
  292.              if (adj0 != 255)           /* not the first lowest */
  293.             free(mp);
  294.              adj0 = *(ad+i);            /* new lowest value */
  295.              m_cnt = 1;                 /* reset count to 1 */
  296.  
  297.              mp = (unsigned short *) malloc(2);     /* space for pos of lowest adj */
  298.              if (mp==0)
  299.             {
  300.                printf("Out of memory -- LOGMIN_A, *mp\n");
  301.                printf("Program terminated - 15\n");
  302.                exit(0);
  303.             }
  304.              *mp = i;                               /* first element */
  305.           }
  306.            else if (*(ad+i) == adj0)                    /* adj as large */
  307.           {
  308.              m_cnt++;                               /* no. of element in mp-array */
  309.              mp = (unsigned short *) realloc(mp, 2*m_cnt); /* more space */
  310.              if (mp==0)
  311.             {
  312.                printf("Out of memory -- LOGMIN_A, *mp\n");
  313.                printf("Program terminated - 16\n");
  314.                exit(0);
  315.             }
  316.              *(mp+m_cnt-1) = i;            /* elements in mp-array */
  317.           }
  318.         }
  319.  
  320.      /***
  321.       ***  SELECT FROM MP-ARRAY, A MINTERM WITH AT LEAST ONE ADJACENT TERM PREVIOSLY
  322.       ***  COVERED
  323.       ***/
  324.  
  325.      for (i=0; i<m_cnt; i++)                 /* do for all in mp-array */
  326.         {
  327.            adj = *(ad+ *(mp+i));             /* adjacency from ad-array */
  328.  
  329.            c = (unsigned char *) malloc(4+nspm*(1+adj));  /* space for adj terms */
  330.            if (c == 0)
  331.           {
  332.              printf("Out of memory -- LOGMIN_A, *c\n");
  333.              printf("Program terminated - 17\n");
  334.              exit(0);
  335.           }
  336.            memcpy(c, (at+ *(ca+ *(mp+i))), 4+nspm*(1+adj));  /* adj terms from at-array */
  337.  
  338.            for (j=0; j<adj; j++)          /* check for at least 1 adj term covered */
  339.           {
  340.              memcpy(temp, (c+4+nspm*(1+j)),nspm);
  341.              test = exist(temp,b,mb);
  342.              if (test == -1)          /* adj term covered */
  343.             break;
  344.           }
  345.  
  346.            if (test == -1)                /* adj term covered */
  347.           break;
  348.            else
  349.           free(c);                    /* free pointer */
  350.         }
  351.  
  352.      if (test == -1)                      /* adj term covered */
  353.         pos = *(mp+i);                    /* position of minterm required */
  354.      else                                 /* none of adj terms covered */
  355.         {
  356.            adj = *(ad+ *mp);              /* choose adj of 1st minterm */
  357.            pos = *mp;                     /* position of 1st minterm */
  358.  
  359.            c = (unsigned char *) malloc(4+nspm*(1+adj));   /* space for adj terms */
  360.            if (c == 0)
  361.           {
  362.              printf("Out of memory -- LOGMIN_A, *c\n");
  363.              printf("Program terminated - 18\n");
  364.              exit(0);
  365.           }
  366.            memcpy(c, (at+ *(ca+pos)), 4+nspm*(1+adj));     /* adj terms from at-array */
  367.         }
  368.  
  369.      d = (unsigned char *) malloc(n+1);       /* space for corresponding CPT */
  370.      if (d == 0)
  371.         {
  372.            printf("Out of memory -- LOGMIN_A, *d\n");
  373.            printf("Program terminated - 19\n");
  374.            exit(0);
  375.         }
  376.      memcpy(d, (cp+n*pos), n);       /* corresponding CPT from cp-array */
  377.      *(d+n) = '\0';                  /* terminate with NULL string */
  378.  
  379.      e = ssm(d);                     /* generate SSM */
  380.  
  381.      free(d);                        /* free pointers */
  382.      free(mp);
  383.  
  384.      /***
  385.       ***  KEEP SHRINKING THE CPT UNTIL THE SELECTED MINTERM IS COVERED BY THE FUNCTION
  386.       ***/
  387.  
  388.      cover = 0;                      /* coverage status */
  389.      while (!cover)                  /* do until shrinked CPT is covered */
  390.         {
  391.            /***
  392.         ***  SELECT THE 1ST ADJACENT TERM WITH THE LOWEST WI TO SHRINK AWAY
  393.         ***  WI IS THE NO. OF TERMS ADJACENT TO THE ADJACENT TERMS THAT ARE
  394.         ***  SSM, E-ARRAY BUT NOT IN THE FUNCTION, A-ARRAY
  395.         ***/
  396.  
  397.            wo = -1;                  /* initial value */
  398.            for (i=0; i<adj; i++)     /* do for all adjacent terms */
  399.           {
  400.              memcpy(temp, (c+4+nspm*(i+1)), nspm);  /* pick adjacent term */
  401.  
  402.              wi = adj_of_mi(temp,e,a);              /* obtain wi */
  403.              if (wi>wo)
  404.             {
  405.                wo = wi;               /* new largest value */
  406.                pos = i;               /* position of adj terms */
  407.             }
  408.           }
  409.            free(e);                           /* free pointer */
  410.  
  411.            adj--;                             /* decrement adjacency */
  412.            *(c+1) = adj;                      /* update in c-array */
  413.  
  414.            memcpy((c+4+nspm*(1+pos)), (c+4+nspm*(2+pos)), nspm*(adj-pos)); /* shrink c-array */
  415.  
  416.            c = (unsigned char*) realloc(c, 4+nspm*(1+adj));   /* decrease space */
  417.            if (c == 0)
  418.           {
  419.              printf("Out of memory -- LOGMIN_A, *c\n");
  420.              printf("Program terminated - 20\n");
  421.              exit(0);
  422.           }
  423.  
  424.            d = cpt(c);                  /* generate CPT */
  425.            e = ssm(d);                  /* generate SSM */
  426.            m = topow(*(e+1));           /* no. of SSM terms */
  427.  
  428.            for (i=0; i<m; i++)          /* check SSM coverage by function */
  429.           {
  430.              memcpy(temp, (e+4+nspm*i), nspm);   /* pick SSM term */
  431.              test = exist(temp,a,ma);
  432.              if (test == -1)                     /* SSM not covered */
  433.             break;
  434.           }
  435.  
  436.            /***
  437.         ***  SHRINKED SSM COVERED BY FUNCTION, REDUCE B-ARRAY AND
  438.         ***  SELECT SHRINKED CPT AS PRODUCT TERM
  439.         ***/
  440.  
  441.            if (test==0)                      /* SSM covered */
  442.           {
  443.              if (m > 65536)                 /* too many SSM terms */
  444.             {
  445.                printf("Product Term Too Huge \n");
  446.                printf("Program terminated \n");
  447.                exit(0);
  448.             }
  449.              *e = n;                         /* no. of variables */
  450.              *(e+1) = (m-1) & mask8;         /* no. of SSM terms minus 1 */
  451.              *(e+2) = (m-1)>>8 & mask8;
  452.              b = reduce(e, b, m);        /* remove minterms covered from b-array */
  453.              mb = *(b+2)<<8 | *(b+1);    /* no. of minterms in b-array */
  454.  
  455.              count = mb;                 /* count of no. of minterms not covered */
  456.  
  457.              s = (unsigned char *) realloc(s, 4+n*(pterm+1));   /* more space */
  458.              if (s == 0)
  459.             {
  460.                printf("Out of memory -- LOGMIN_A, *s\n");
  461.                printf("Program terminated - 21\n");
  462.                exit(0);
  463.             }
  464.              memcpy ((s+4+n*pterm), d, n);     /* add shrinked CPT to soln array */
  465.              pterm++;                          /* no. of product terms */
  466.  
  467.              cover = 1;                        /* coverage status */
  468.  
  469.              /***
  470.               ***  FLAG TERMS COVERED IN THE AD-ARRAY
  471.               ***/
  472.  
  473.              for (i=0; i<m; i++)               /* flag terms just covered */
  474.             {
  475.                for (j=0; j<count1; j++)    /* do for all terms in mt-array */
  476.                   {
  477.                  test = memcmp((e+4+nspm*i), (mt+4+nspm*j), nspm);
  478.                  if (test==0)
  479.                     {
  480.                        *(ad+j) = 0;    /* flag the adjacency to indicate coverage */
  481.                        break;
  482.                     }
  483.                   }
  484.             }
  485.              free(e);            /* free pointer */
  486.           }
  487.            free (d);                 /* free pointer */
  488.         }
  489.      free(c);                        /* free pointer */
  490.       }
  491.  
  492.    if (count1>0)                  /* some terms stored for phase II */
  493.       {
  494.      free(ad);                /* free pointers */
  495.      free(cp);
  496.      free(mt);
  497.      free(at);
  498.      free(ca);
  499.       }
  500.  
  501.    *s = n;                        /* no. of variables */
  502.    *(s+1) = pterm & mask8;        /* no. of product terms in 2 bytes */
  503.    *(s+2) = pterm>>8 & mask8;
  504.  
  505.    free(temp);                    /* free pointer */
  506.    free(a);
  507.    free(b);
  508.  
  509.    return(s);                     /* return solution array */
  510. }
  511.  
  512.