home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Snippets / Quine-McClusky 1.2 / main.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-29  |  13.9 KB  |  612 lines  |  [TEXT/MPCC]
  1. /****************************************************************************
  2.  *
  3.  *     main.c
  4.  *
  5.  *     By         John A. Schlack
  6.  *     Dates:     October 1994 - November 1994
  7.  *
  8.  *     Description:
  9.  *
  10.  *        This module has the main module and support routines for generating
  11.  *        the irredundant prime implicants.  It gathers data from the user,
  12.  *        handles error conditions and some memory allocation.  The functions
  13.  *        that perform the real work are located in "decimal.c" and "ir.c".
  14.  *
  15.  *
  16.  *    Release Notes:
  17.  *
  18.  *        1.10    11/02/94    Created to manage generation of irredundant prime
  19.  *                            implicants.
  20.  *        1.20    11/28/94    Modified input routines to accept a range for
  21.  *                            decimal function specification.  One places a dash
  22.  *                            between the numbers, no white spaces.
  23.  *
  24.  ****************************************************************************/
  25.  
  26.  
  27. #define MAIN_C
  28.  
  29.  
  30. /* --------------------------------------------------------------------------------------------- */
  31.  
  32.  
  33. #include <ctype.h>
  34. #include <stdlib.h>
  35. #include <stdio.h>
  36. #include <string.h>
  37.  
  38. #include "qmPrime.h"
  39.  
  40.  
  41. /* --------------------------------------------------------------------------------------------- */
  42.  
  43.  
  44. #if DEBUG
  45.     FILE *    fp;
  46. #endif
  47.  
  48. static char    userData[120];
  49.  
  50.  
  51. /* --------------------------------------------------------------------------------------------- */
  52.  
  53.  
  54. /* PROTOTYPES */
  55.  
  56. void             main( void );
  57. static short    getFunction( decimalArray * output, decimalArray * dontCare, short * vars );
  58. static short *     getPartialFunction( char * prompt, short * len, short vars,
  59.                     short * ignore, short ignoreLen );
  60. static int         ascendingOrder( const void * a1, const void * a2 );
  61. static short     parseFunction( char * cp, short * dec, short * dnum, long max,
  62.                     short * ignore, short ignoreLen );
  63. static void     makeDecimal( char * field1, char * field2, short * decList, short * decNum,
  64.                     long maxValue, short * ignore, short ignoreLen );
  65. static void     freeIrredundant( irredundant * ir );
  66.  
  67.  
  68. /* --------------------------------------------------------------------------------------------- */
  69.  
  70.  
  71. void main( void )
  72. {
  73.     decimalArray    output, dontCare;
  74.     short             actualVars;
  75.  
  76. #if DEBUG
  77.     fp = fopen( "debug.out", "wt" );
  78.     if (fp == NULL)
  79.     {
  80.         printf( "Cannot open debug file...aborting\n" );
  81.         exit( 4 );
  82.     }
  83. #endif
  84.  
  85.     printf( "\n\n------------------------------------------------\n\n" );
  86.     printf( "Quine-McClusky Method (version 1.2)\n\nby John A. Schlack\nNovember 29, 1994\n\n" );
  87.  
  88. #if defined(powerc) || defined (__powerc)
  89.     printf( "Power Macintosh version\nCompiled using Metrowerks CodeWarrior 4.5\n" );
  90. #elif defined(__MWERKS__)
  91.     printf( "68K Macintosh version\nCompiled using Metrowerks CodeWarrior 4.5\n" );
  92. #else
  93.     printf( "PC version\nCompiled using Borland C++ 2.0\n" );
  94. #endif
  95.  
  96.     printf( "(Originally developed on a Power Macintosh 6100/80 using CodeWarrior 4.5)\n\n" );
  97.     printf( "------------------------------------------------\n\n" );
  98.  
  99.     // initialize
  100.     memset( &output, 0, sizeof( output ) );
  101.     memset( &dontCare, 0, sizeof( dontCare ) );
  102.  
  103.     // retrieve desired function from user
  104.     if (getFunction( &output, &dontCare, &actualVars ))
  105.     {
  106.         QuineMcClusky( &output, &dontCare, actualVars );
  107.         free( output.array );
  108.         if (dontCare.array != NULL)
  109.             free( dontCare.array );
  110.     }
  111.  
  112. #if DEBUG
  113.     fclose( fp );
  114. #endif
  115. }
  116.  
  117.  
  118. /* --------------------------------------------------------------------------------------------- */
  119.  
  120.  
  121. void QuineMcClusky( decimalArray * output, decimalArray * dontCare, short actualVars )
  122. {
  123.     irredundant *    primes;
  124.     short *            function, funcLen;
  125.  
  126.     // build combined list of decimals
  127.     funcLen = output->len + dontCare->len;
  128.     function = (short *) malloc( funcLen * sizeof( short ) );
  129.     if (function == NULL)
  130.         lowMemory();
  131.  
  132.     memcpy( function, output->array, output->len * sizeof( short ) );
  133.     if (dontCare->len)
  134.         memcpy( function + output->len, dontCare->array, dontCare->len * sizeof( short ) );
  135.     qsort( function, funcLen, sizeof( short ), ascendingOrder );
  136.  
  137.     // get prime implicants
  138.     primes = doDecimal( function, funcLen, actualVars );
  139.     free( function );
  140.  
  141.     // reduce to irredundant form
  142.     if (primes != NULL)
  143.     {
  144.         irredundantForm( primes, output->array, output->len, actualVars );
  145.         freeIrredundant( primes );
  146.     }
  147. }
  148.  
  149.  
  150. /* --------------------------------------------------------------------------------------------- */
  151.  
  152.  
  153. void lowMemory( void )
  154. {
  155.     printf( "Insufficient memory to execute this program.  Exiting...\n" );
  156.     exit( 1 );
  157. }
  158.  
  159.  
  160. /* --------------------------------------------------------------------------------------------- */
  161.  
  162.  
  163. void paramError( char * funcName, short param )
  164. {
  165.     printf( "Parameter error in function %.32s argument %d\n", funcName, param );
  166.     exit( 2 );
  167. }
  168.  
  169.  
  170. /* --------------------------------------------------------------------------------------------- */
  171.  
  172.  
  173. /*
  174.     static short getFunction( decimalArray * output, decimalArray * dontCare, short * vars )
  175.  
  176.     Description:
  177.         This routine controls the retrieval of function information from the user.
  178.         The user is prompted for the number of variables in the function and the
  179.         function expressed in decimal notation (sum of products entries).
  180.  
  181.     Input:
  182.         none
  183.  
  184.     Output:
  185.         "output" contains the actual decimal output array and its length.
  186.         "dontCare" contains an array of decimal don't care conditions and its length.
  187.         "vars" is the number of variables in the user's function.
  188.  
  189.     Globals Modified:
  190.         none
  191.  
  192.     Returns:
  193.         Boolean flag (1 or 0) indicating whether valid data has been entered.
  194. */
  195.  
  196.  
  197. static short getFunction( decimalArray * output, decimalArray * dontCare, short * vars )
  198. {
  199.     long    decNum;
  200.  
  201.     // get number of variables
  202.     do
  203.     {
  204.         printf( "\nEnter the number of variables (2 to %d)...", MAX_VARS );
  205.         gets( userData );
  206.         sscanf( userData, "%ld", &decNum );
  207.         *vars = (short) decNum;
  208.         if (*vars <= 0)
  209.         {
  210.             printf( "Exiting...\n" );
  211.             exit( 0 );
  212.         }
  213.     } while ((*vars < 2) || (*vars > MAX_VARS));
  214.  
  215.     output->array = getPartialFunction( "decimal function", &output->len, *vars,
  216.         NULL, 0 );
  217.     if (output->len <= 0)
  218.     {
  219.         printf( "Function undefined.  Exiting...\n" );
  220.         exit( 3 );
  221.     }
  222.  
  223.     dontCare->array = getPartialFunction( "don't cares", &dontCare->len, *vars,
  224.         output->array, output->len );
  225.  
  226.     return 1;
  227. }
  228.  
  229.  
  230. /* --------------------------------------------------------------------------------------------- */
  231.  
  232.  
  233. static short * getPartialFunction( char * prompt, short * len, short vars,
  234.     short * ignore, short ignoreLen )
  235. {
  236.     long    decNum;
  237.     size_t    size;
  238.     short    * decimal, count, more;
  239.  
  240.     // allocate memory to store decimal representation of function
  241.     decNum = 1L << vars;
  242.     size = (size_t) (decNum * sizeof( short ));
  243.     decimal = malloc( size );
  244.     if (decimal == NULL)
  245.         lowMemory();
  246.     memset( decimal, 0xFF, size );
  247.     count = 0;
  248.  
  249.     printf( "\n-------------\n" );
  250.  
  251.     // get function
  252.     do
  253.     {
  254.         printf( "\n\nEnter the %.40s.  Each entry must be separated by\n", prompt );
  255.         printf( "a space or comma.  If you need more than one line to enter\n" );
  256.         printf( "the data, end the line with a comma or plus sign.\n\n" );
  257.         userData[0] = 0;
  258.         gets( userData );
  259.         userData[sizeof( userData ) - 1] = 0;    // make sure we are null terminated
  260.         more = parseFunction( userData, decimal, &count, decNum, ignore, ignoreLen );
  261.     } while (more);
  262.  
  263.     if (count > 0)
  264.     {
  265.         qsort( decimal, decNum, sizeof( short ), ascendingOrder );
  266.         size = count * sizeof( short );
  267.         decimal = realloc( decimal, size );
  268.     }
  269.     else
  270.     {
  271.         free( decimal );
  272.         decimal = NULL;
  273.     }
  274.  
  275.     *len = count;
  276.     return decimal;
  277. }
  278.  
  279.  
  280. /* --------------------------------------------------------------------------------------------- */
  281.  
  282.  
  283. /*
  284.     static int ascendingOrder( const void * a1, const void * a2 )
  285.  
  286.     Description:
  287.         This function is used by qsort() to place the decimal function data
  288.         into ascending order.
  289.  
  290.     Input:
  291.         none
  292.  
  293.     Output:
  294.         "a1" and "a2" are pointers to the elements being compared.
  295.  
  296.     Globals Modified:
  297.         none
  298.  
  299.     Returns:
  300.         -1 if a1<a2, 1 if a1>a2, 0 if a1=a2
  301. */
  302.  
  303.  
  304. static int ascendingOrder( const void * a1, const void * a2 )
  305. {
  306.     unsigned short    v1, v2;
  307.  
  308.     v1 = *((unsigned short *) a1);
  309.     v2 = *((unsigned short *) a2);
  310.     if (v1 < v2)
  311.         return -1;
  312.     if (v1 > v2)
  313.         return 1;
  314.     return 0;
  315. }
  316.  
  317.  
  318. /* --------------------------------------------------------------------------------------------- */
  319.  
  320.  
  321. static short parseFunction( char * cp, short * dec, short * dnum, long max,
  322.     short * ignore, short ignoreLen )
  323. {
  324.     #define    MAX_STR_SIZE    15
  325.     
  326.     char    str[MAX_STR_SIZE+1], str2[MAX_STR_SIZE+1], lastNonWhite;
  327.     short    i, i2, badFlag, doSecond;
  328.     
  329.     // scan line
  330.     lastNonWhite = 0;
  331.     badFlag = 0;
  332.     doSecond = 0;
  333.     for (i=i2=0; *cp; cp++)
  334.     {
  335.         if (!isspace( *cp ))
  336.             lastNonWhite = *cp;
  337.         if (isalnum( *cp ) || (*cp == '-'))
  338.         {
  339.             // flag error if field too long
  340.             if ( (!doSecond && (i >= MAX_STR_SIZE)) || (doSecond && (i2 >= MAX_STR_SIZE)) )
  341.                 badFlag = 1;
  342.             
  343.             // start recording second digit
  344.             else if (*cp == '-')
  345.             {
  346.                 if (doSecond)
  347.                     badFlag = 1;
  348.                 else
  349.                     doSecond = 1;
  350.             }
  351.                 
  352.             // save character for conversion
  353.             else if (isdigit( *cp ))
  354.             {
  355.                 if (!doSecond && (i < MAX_STR_SIZE))
  356.                     str[i++] = *cp;
  357.                 else if (doSecond && (i2 < MAX_STR_SIZE))
  358.                     str2[i2++] = *cp;
  359.             }
  360.             
  361.             // flag error for non-digit
  362.             else
  363.                 badFlag = 1;
  364.         }
  365.         else
  366.         {
  367.             str[i] = 0;
  368.             str2[i2] = 0;
  369.             if (badFlag)
  370.             {
  371.                 printf( "Invalid input" );
  372.                 if (i > 0)
  373.                 {
  374.                     printf( ": %.16s", str );
  375.                     if (i2 > 0)
  376.                         printf( ", %.16s", str2 );
  377.                 }
  378.                 putc( '\n', stdout );
  379.             }
  380.             else
  381.                 makeDecimal( str, str2, dec, dnum, max, ignore, ignoreLen );
  382.  
  383.             i = 0;
  384.             i2 = 0;
  385.             badFlag = 0;
  386.             doSecond = 0;
  387.         }
  388.     }
  389.  
  390.     // in case have unprocessed decimal value
  391.     if ((i > 0) && (!badFlag))
  392.     {
  393.         str[i] = 0;
  394.         str2[i2] = 0;
  395.         makeDecimal( str, str2, dec, dnum, max, ignore, ignoreLen );
  396.     }
  397.  
  398.     // return whether more input lines are expected
  399.     return (((lastNonWhite == ',') || (lastNonWhite == '+')) ? 1 : 0);
  400. }
  401.  
  402.  
  403. /* --------------------------------------------------------------------------------------------- */
  404.  
  405.  
  406. static void makeDecimal( char * field1, char * field2, short * decList, short * decNum,
  407.     long maxValue, short * ignore, short ignoreLen )
  408. {
  409.     long    value, value2, j;
  410.     short    i;
  411.  
  412.     // convert field and verify range
  413.     value = atol( field1 );
  414.     if (field2[0])
  415.         value2 = atol( field2 );
  416.     else
  417.         value2 = value;
  418.  
  419.     if ((value < 0) || (value >= maxValue) || (value2 < 0) || (value2 >= maxValue))
  420.     {
  421.         printf( "Invalid input range: %.16s %.16s\n", field1, field2 );
  422.         return;
  423.     }
  424.  
  425.     // do not permit don't cares with same decimal as output
  426.     if (ignore != NULL)
  427.     {
  428.         for (j=value; j<=value2; j++)
  429.         {
  430.             i = (short) j;
  431.             if (bsearch( &i, ignore, sizeof( short ), ignoreLen, ascendingOrder ) != NULL)
  432.             {
  433.                 printf( "Duplicated input: %ld\n", value );
  434.                 return;
  435.             }
  436.         }
  437.     }
  438.  
  439.     for (j=value; j<=value2; j++)
  440.     {
  441.         // determine if value is already in list
  442.         for (i=0; i<*decNum; i++)
  443.             if (decList[i] == (short) j)
  444.                 return;
  445.     
  446.         // insert entry in list
  447.         decList[*decNum] = (short) j;
  448.         (*decNum)++;
  449.     }
  450. }
  451.  
  452.  
  453. /* --------------------------------------------------------------------------------------------- */
  454.  
  455.  
  456. /*
  457.     Properly copies two blocks of data, even if they overlap.
  458. */
  459. void blockMove( char * dst, char * src, size_t len )
  460. {
  461.     size_t    i;
  462.  
  463.     if (len <= 0)
  464.         return;
  465.     if (dst > src)
  466.     {
  467.         len--;
  468.         dst += len;
  469.         src += len;
  470.         for (i=len; i>=0; i--)
  471.             *dst++ = *src++;
  472.     }
  473.     else if (dst < src)
  474.     {
  475.         for (i=0; i<len; i++)
  476.             *dst++ = *src++;
  477.     }
  478. }
  479.  
  480.  
  481. /* --------------------------------------------------------------------------------------------- */
  482.  
  483.  
  484. void printNumbers( FILE * fout, unsigned char * numStr, short len )
  485. {
  486.     short    i;
  487.  
  488.     for (i=0; i<len; i++)
  489.         fprintf( fout, "%2d ", (int) (numStr[i]) );
  490. }
  491.  
  492.  
  493. /* --------------------------------------------------------------------------------------------- */
  494.  
  495.  
  496. static void freeIrredundant( irredundant * ir )
  497. {
  498.     irElement *    elem;
  499.     short        i;
  500.  
  501.     if (ir == NULL)
  502.         return;
  503.  
  504.     if (ir->irArray != NULL)
  505.     {
  506.         elem = ir->irArray;
  507.         for (i=0; i<ir->len; i++, elem++)
  508.         {
  509.             if (elem->decimal != NULL)
  510.                 free( elem->decimal );
  511.             if (elem->difference != NULL)
  512.                 free( elem->difference );
  513.         }
  514.  
  515.         free( ir->irArray );
  516.     }
  517.     free( ir );
  518. }
  519.  
  520.  
  521. /* --------------------------------------------------------------------------------------------- */
  522.  
  523.  
  524. /*
  525.     void printEntry( unsigned char * decimal, unsigned char * difference,
  526.         short level, short vars, short * minLevel )
  527.  
  528.     Description:
  529.         This function prints a prime implicant to the screen.
  530.  
  531.     Input:
  532.         "decimal" is the list of decimal functions that were used in creating
  533.             this prime implicant.
  534.         "difference" is an array of exclusing values that are used to display
  535.             the prime implicant.
  536.         "level" is the list number in which this prime implicant resides
  537.             (used for determining the number of entries in "difference"
  538.             and "decimal").
  539.         "vars" is the number of variables for this function.
  540.         "minLevel" is used for determining the number of spaces to print
  541.             between prime implicant and decimal list.  This is only used
  542.             with the non-reduced list of primes.
  543.  
  544.     Output:
  545.         none
  546.  
  547.     Globals Modified:
  548.         none
  549.  
  550.     Returns:
  551.         none
  552. */
  553.  
  554.  
  555. void printEntry( unsigned char * decimal, unsigned char * difference,
  556.     short level, short vars, short * minLevel )
  557. {
  558.     short            count, i, spaces, numDec;
  559.     unsigned char    * diff, ignore, number, mask;
  560.  
  561.     if (decimal == NULL)
  562.         return;
  563.  
  564.     // build a number with all "differences" ORed together
  565.     ignore = 0;
  566.     if (difference != NULL)
  567.     {
  568.         diff = difference;
  569.         for (i=1; i<level; i++, diff++)
  570.         {
  571.             if (*diff)
  572.                 ignore |= *diff;
  573.             else
  574.             {
  575.                 printf( "\n*** ERROR!  Invalid number of 'ignore' arguments (level=%d). ***\n", level );
  576.                 break;
  577.             }
  578.         }
  579.     }
  580.  
  581.     // print individual elements of prime implicant
  582.     number = *(decimal);
  583.     mask = 1 << (vars - 1);
  584.     for (i=1, count=0; i<=vars; i++, mask>>=1)
  585.     {
  586.         // if this var's ignore bit is set, skip it
  587.         if (ignore & mask)
  588.             continue;
  589.  
  590.         // print variable
  591.         printf( "x%d%c ", vars - i, (number & mask) ? (' ') : ('\'') );
  592.         count++;
  593.     }
  594.  
  595.     // print decimal components
  596.     if (minLevel != NULL)
  597.     {
  598.         if (*minLevel <= 0)
  599.             *minLevel = level;
  600.         spaces = (level - *minLevel) * 4 + 8;
  601.         for (i=0; i<spaces; i++)
  602.             putc( ' ', stdout );
  603.         putc( '(', stdout );
  604.         numDec = 1 << (level - 1);
  605.         printNumbers( stdout, decimal, numDec );
  606.         putc( ')', stdout );
  607.     }
  608.  
  609.     if (count)
  610.         putc( '\n', stdout );
  611. }
  612.