home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Snippets / Quine-McClusky 1.2 / decimal.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-29  |  20.1 KB  |  833 lines  |  [TEXT/MPCC]
  1. /****************************************************************************
  2.  *
  3.  *  decimal.c
  4.  *
  5.  *    Quine - McClusky Method
  6.  *
  7.  *    By:        John A. Schlack
  8.  *    Dates:    October 1994 - November 1994
  9.  *
  10.  *
  11.  *    This program implements to Quine-McClusky method for reducing a function to its
  12.  *    prime implicants.  The user must specify the number of variables (2 to 8) and the
  13.  *    decimal components that define the function.  The program will calculate the prime
  14.  *    implicants.  The output is in the form: x1x2...xn (where n has a maximum value of
  15.  *    the number of variables chosen by the user).  x1 is the most significant term (bit)
  16.  *    while xn is the least significant.
  17.  *
  18.  *
  19.  *    Limitations:
  20.  *        1)    No more than 8 variables can be used (even if "MAX_VARS" is changed below)
  21.  *            without major changes to the data structures.  The data structures use
  22.  *            "unsigned char", which limits the total variables to 8.  This can be changed,
  23.  *            but be wary that certain constants (which are hard coded) may also need to
  24.  *            be altered.
  25.  *
  26.  *        2)    This code has not been extensively tested.  It seems to work properly, but
  27.  *            cases not yet tested may cause errors.
  28.  *
  29.  *        3)    This code was developed on a Power Macintosh computer running in 32 bit mode
  30.  *            (and using a flat memory model).  Segmented architectures may cause this
  31.  *            program problems, and may also limit the maximum number of variables that
  32.  *            can be used.
  33.  *
  34.  *        4)    The user interface code may be a major limiting factor.  It requires the user
  35.  *            to hand enter the decimal components of the function.  This can be tedious
  36.  *            and error prone.  Also, continuing the decimal function on more than one
  37.  *            line has not been tested.
  38.  *
  39.  *        5)    This code is written entirely in ANSI C.  This means that it is compatible
  40.  *            across all major computer systems.  It also means that platform specific
  41.  *            code to take advantage of proprietary user interfaces does not exist, making
  42.  *            data entry more difficult.
  43.  *
  44.  *
  45.  *    You may not use any portion of this code (whether in source code or compiled form)
  46.  *    without written permission from its author.  You may contact the author by writing to:
  47.  *
  48.  *        John A. Schlack
  49.  *        406 Newgate Court, Apt. A1
  50.  *        Andalusia, Pa. 19020
  51.  *        USA
  52.  *
  53.  *
  54.  *    Release Notes:
  55.  *
  56.  *        1.00    10/19/94    Created Quine-McClusky method of generating
  57.  *                            prime implicants (they are NOT irredundant form).
  58.  *        1.10    11/02/94    Isolate Quine-McClusky method from user input.
  59.  *                            Return pointer to resulting prime implicants
  60.  *                            for reduction or manipulation by other routines.
  61.  *        1.20    11/28/94    Fixed bug in bit table which caused it to be only
  62.  *                            128 elements instead of 256 (crashed on 8 variables).
  63.  *
  64.  ****************************************************************************/
  65.  
  66.  
  67. /* --------------------------------------------------------------------------------------------- */
  68.  
  69.  
  70. #include <stdio.h>
  71. #include <stdlib.h>
  72. #include <string.h>
  73.  
  74. #include "qmPrime.h"
  75.  
  76.  
  77. /* --------------------------------------------------------------------------------------------- */
  78.  
  79.  
  80. typedef struct entryStruct
  81. {
  82.     unsigned char *    decimal;
  83.     unsigned char *    difference;
  84.     char            used;
  85. } entryStruct;
  86.  
  87. typedef struct segmentStruct
  88. {
  89.     short            count;
  90.     entryStruct *    entries;
  91. } segmentStruct;
  92.  
  93. typedef struct listStruct
  94. {
  95.     short            listNum;
  96.     short            count;
  97.     segmentStruct *    segments;
  98. } listStruct;
  99.  
  100.  
  101. /* --------------------------------------------------------------------------------------------- */
  102.  
  103.  
  104. /* PROTOTYPES */
  105.  
  106. static char *        buildBitsSetArray( short vars );
  107. static void         freeList( listStruct * list, short num );
  108. static void         freeSegment( segmentStruct * baseSeg, short numSegs );
  109. static void         purgeSegment( segmentStruct * segment );
  110. static void         freeEntries( entryStruct * baseEntry, short entryCount );
  111. static listStruct *    buildBaseList( short vars );
  112. static void         doQuineMcClusky( char * bitTable, listStruct * list, short * func, short fNum,
  113.                         short vars );
  114. static short        compareSegments( char * bitTable, segmentStruct * seg1, segmentStruct * seg2,
  115.                     segmentStruct * nextSeg, short curLevel );
  116. static void            buildList1( char * bitTable, listStruct * list1, short * func, short fNum );
  117. static entryStruct *    appendEntry( segmentStruct * seg, short decCount, short difCount );
  118. static long         printResults( listStruct * list, short actualVars );
  119. static void         simplifyList( listStruct * list );
  120. static int             ucharSortFunc( const void * a1, const void * a2 );
  121. static void         dumpList( listStruct * list );
  122. static irredundant *    primes2Irredundant( listStruct * list, long count, short actualVars );
  123.  
  124.  
  125. /* --------------------------------------------------------------------------------------------- */
  126.  
  127.  
  128. irredundant * doDecimal( short * decFunction, short decCount, short actualVars )
  129. {
  130.     irredundant *    ir;
  131.     listStruct *    list;
  132.     char *            binaryBitsSet;
  133.     long            primes;
  134.     short            maxDecs;
  135.  
  136.     maxDecs = 1 << actualVars;
  137.     if (decCount >= maxDecs)
  138.     {
  139.         printf( "\n*** Trivial solution: 1 ***\n" );
  140.         exit( 1 );
  141.     }
  142.     if (decCount <= 0)
  143.     {
  144.         printf( "\n*** Trivial solution: 0 ***\n" );
  145.         exit( 1 );
  146.     }
  147.  
  148.     binaryBitsSet = buildBitsSetArray( MAX_VARS );
  149.     list = buildBaseList( MAX_VARS );
  150.     doQuineMcClusky( binaryBitsSet, list, decFunction, decCount, actualVars );
  151.     primes = printResults( list, actualVars );
  152.     ir = (primes > 0L) ? (primes2Irredundant( list, primes, actualVars )) : NULL;
  153.     free( binaryBitsSet );
  154.     freeList( list, MAX_VARS );
  155.  
  156.     return ir;
  157. }
  158.  
  159.  
  160. /* --------------------------------------------------------------------------------------------- */
  161.  
  162.  
  163. /*
  164.     static char * buildBitsSetArray( short vars )
  165.  
  166.     Description:
  167.         This function builds a table of the number of bits set for the table's
  168.         index.  That is, for index entry 4, the value is 1 since 4 has 1 bit set.
  169.         The number of entries in this table is 2 to the "vars" power.
  170.         
  171.         This function will abort the program on an invalid parameter or low memory.
  172.  
  173.     Input:
  174.         "vars" is the number of variables that this program can handle.  This
  175.             value control the number of entries in the table.
  176.  
  177.     Output:
  178.         none
  179.  
  180.     Globals Modified:
  181.         none
  182.  
  183.     Returns:
  184.         Pointer to the table.
  185. */
  186.  
  187.  
  188. static char * buildBitsSetArray( short vars )
  189. {
  190.     char *    array;
  191.     long    i, j, entries;
  192.     short    count;
  193.     
  194.     if ((vars < 2) || (vars > 32))
  195.         paramError( "buildBitsSetArray", 1 );
  196.     entries = 1L << vars;
  197.     
  198.     array = malloc( entries * sizeof( char ) );
  199.     if (array == NULL)
  200.         lowMemory();
  201.  
  202.     for (i=0L; i<entries; i++)
  203.     {
  204.         for (j=1L, count=0; j<entries; j<<=1)
  205.         {
  206.             if (i & j)
  207.                 count++;
  208.         }
  209.         array[i] = (char) count;
  210.     }
  211.     
  212.     return array;
  213. }
  214.  
  215.  
  216. /* --------------------------------------------------------------------------------------------- */
  217.  
  218.  
  219. static void freeList( listStruct * list, short num )
  220. {
  221.     short    i;
  222.  
  223.     if (list == NULL)
  224.         return;
  225.  
  226.     for (i=0; i<num; i++)
  227.         freeSegment( list[i].segments, list[i].count );
  228.     free( list );
  229. }
  230.  
  231.  
  232. /* --------------------------------------------------------------------------------------------- */
  233.  
  234.  
  235. static void freeSegment( segmentStruct * baseSeg, short numSegs )
  236. {
  237.     short    i;
  238.  
  239.     if (baseSeg == NULL)
  240.         return;
  241.  
  242.     for (i=0; i<numSegs; i++)
  243.         freeEntries( baseSeg[i].entries, baseSeg[i].count );
  244.     free( baseSeg );
  245. }
  246.  
  247.  
  248. /* --------------------------------------------------------------------------------------------- */
  249.  
  250.  
  251. /*
  252.     This function is used to free up system memory after a segment's entries
  253.     have been processed.  All used entries are deleted since their data will
  254.     no longer be used in this program.
  255. */
  256. static void purgeSegment( segmentStruct * segment )
  257. {
  258.     entryStruct *    entry;
  259.     short            i;
  260.     
  261.     if (segment == NULL)
  262.         return;
  263.     
  264.     entry = segment->entries;
  265.     if (entry == NULL)
  266.         return;
  267.  
  268.     for (i=0; i<segment->count; i++, entry++)
  269.     {
  270.         if (entry->used)
  271.         {
  272.             if (entry->decimal != NULL)
  273.             {
  274.                 free( entry->decimal );
  275.                 entry->decimal = NULL;
  276.             }
  277.             if (entry->difference != NULL)
  278.             {
  279.                 free( entry->difference );
  280.                 entry->difference = NULL;
  281.             }
  282.         }
  283.     }
  284. }
  285.  
  286.  
  287. /* --------------------------------------------------------------------------------------------- */
  288.  
  289.  
  290. /*
  291.     "baseEntry" is a pointer to the first element of an entries array.  We must free all
  292.         of the "decimal" and "difference" arrays before freeing the actual base.
  293. */
  294. static void freeEntries( entryStruct * baseEntry, short entryCount )
  295. {
  296.     entryStruct *    entry;
  297.     short            i;
  298.     
  299.     if (baseEntry == NULL)
  300.         return;
  301.  
  302.     entry = baseEntry;
  303.     for (i=0; i<entryCount; i++, entry++)
  304.     {
  305.         if (entry->decimal != NULL)
  306.             free( entry->decimal );
  307.         if (entry->difference != NULL)
  308.             free( entry->difference );
  309.     }
  310.     free( baseEntry );
  311. }
  312.  
  313.  
  314. /* --------------------------------------------------------------------------------------------- */
  315.  
  316.  
  317. /*
  318.     listStruct * buildBaseList( short vars )
  319.  
  320.     Description:
  321.         This function allocates the base memory for all possible lists and
  322.         segment arrays within those lists.  One list is created for each
  323.         variable, with the number of segments per list set at ("vars" -
  324.         list number - 1).  All segments are zeroed.
  325.  
  326.     Input:
  327.         "vars" is the number of variables that this program can handle.  This
  328.             value control the number of lists.
  329.  
  330.     Output:
  331.         none
  332.  
  333.     Globals Modified:
  334.         none
  335.  
  336.     Returns:
  337.         Pointer to the list array.
  338. */
  339.  
  340.  
  341. static listStruct * buildBaseList( short vars )
  342. {
  343.     listStruct *    list;
  344.     size_t            size;
  345.     short            i;
  346.     
  347.     if ((vars < 2) || (vars > 32))
  348.         paramError( "buildBaseList", 1 );
  349.  
  350.     // create array of list pointers
  351.     size = vars * sizeof( listStruct );
  352.     list = malloc( size );
  353.     if (list == NULL)
  354.         lowMemory();
  355.     
  356.     // initialize list pointers
  357.     for (i=0; i<vars; i++)
  358.     {
  359.         list[i].listNum = i + 1;
  360.         list[i].count = vars + 1 - i;
  361.         list[i].segments = calloc( list[i].count, sizeof( segmentStruct ) );
  362.         if (list[i].segments == NULL)
  363.             lowMemory();
  364.     }
  365.  
  366.     return list;
  367. }
  368.  
  369.  
  370. /* --------------------------------------------------------------------------------------------- */
  371.  
  372.  
  373. static void doQuineMcClusky( char * bitTable, listStruct * list, short * func, short fNum, short vars )
  374. {
  375.     segmentStruct *    nextSeg;
  376.     short            doNextList, i, j;
  377.     
  378.     buildList1( bitTable, &(list[0]), func, fNum );
  379.     
  380.     for (i=1; i<vars; i++, list++)
  381.     {
  382.         doNextList = 0;
  383.         nextSeg = (list+1)->segments;    // point to first segment in next list
  384.         
  385.         for (j=1; j<list->count; j++)
  386.         {
  387.             if (compareSegments( bitTable, &list->segments[j-1], &list->segments[j],
  388.                 nextSeg, i ))
  389.             {
  390.                 nextSeg++;        // created some segment entries, go to next segment
  391.                 doNextList = 1;    // at least 1 new entry in next list, will continue
  392.             }
  393.             purgeSegment( &list->segments[j-1] );    // purge each segment as it is compared
  394.         }
  395.         purgeSegment( &list->segments[j-1] );        // purge last segment
  396.         
  397.         if (!doNextList)
  398.             break;
  399.  
  400. #if DEBUG
  401.         dumpList( list + 1 );
  402. #endif
  403.  
  404.         simplifyList( list + 1 );    // remove duplicate entries from new list
  405.         
  406. #if DEBUG
  407.         dumpList( list + 1 );
  408. #endif
  409.     }
  410.     
  411. #if DEBUG
  412.     dumpList( list );
  413. #endif
  414. }
  415.  
  416.  
  417. /* --------------------------------------------------------------------------------------------- */
  418.  
  419.  
  420. static short compareSegments( char * bitTable, segmentStruct * seg1, segmentStruct * seg2,
  421.     segmentStruct * nextSeg, short curLevel )
  422. {
  423.     entryStruct    *     elo, * ehi, * enew;
  424.     long            count;
  425.     short            i, j, seg1count, seg2count, diff;
  426.     short            nextDec, nextDif, curDec, curDif;
  427.     
  428.     // verify parameters
  429.     if ((seg1->count == 0) || (seg2->count == 0))
  430.         return 0;
  431.  
  432.     // initialize search variables
  433.     seg1count = seg1->count;
  434.     seg2count = seg2->count;
  435.     elo = seg1->entries;
  436.     count = 0L;
  437.     nextDec = 1 << curLevel;
  438.     nextDif = curLevel;
  439.     curDec = nextDec >> 1;
  440.     curDif = nextDif - 1;
  441.     
  442.     // compare all entries in lower segment with those in upper segment
  443.     for (i=0; i<seg1count; i++, elo++)
  444.     {
  445.         ehi = seg2->entries;
  446.         for (j=0; j<seg2count; j++, ehi++)
  447.         {
  448.             // verify difference values
  449.             if (curDif)
  450.                 if (memcmp( elo->difference, ehi->difference, (size_t) curDif ))
  451.                     continue;
  452.             
  453.             // check differences in first entry
  454.             diff = (short) *ehi->decimal - (short) *elo->decimal;
  455.             if (diff <= 0)
  456.                 continue;
  457.             
  458.             // insert entry in next list (difference is multiple of 2)
  459.             if (bitTable[diff] == 1)
  460.             {
  461.                 // update entries as used and create a new entry in the next list
  462.                 elo->used = ehi->used = 1;
  463.                 count++;
  464.                 enew = appendEntry( nextSeg, nextDec, nextDif );
  465.                 enew->used = 0;
  466.  
  467.                 // copy decimal data
  468.                 memcpy( enew->decimal, elo->decimal, (size_t) curDec );
  469.                 memcpy( enew->decimal + curDec, ehi->decimal, (size_t) curDec );
  470.                 
  471.                 // copy difference data
  472.                 if (curDif > 0)
  473.                     memcpy( enew->difference, elo->difference, (size_t) curDif );
  474.                 *(enew->difference + curDif) = (unsigned char) diff;
  475.             }
  476.         }
  477.     }
  478.     
  479.     return ((count) ? 1 : 0);
  480. }
  481.  
  482.  
  483. /* --------------------------------------------------------------------------------------------- */
  484.  
  485.  
  486. /*
  487.     static void buildList1( char * bitTable, listStruct * list1, short * func, short fNum )
  488.  
  489.     Description:
  490.         This function builds the initial list (list 1) from the user specified
  491.         decimal function.
  492.  
  493.     Input:
  494.         "bitTable" is a table with entries that correspond to the number of set bits
  495.             in a decimal number.
  496.         "func" is a list of user specified decimals that specify the function.
  497.         "fNum" are the number of entries in the array "func".
  498.  
  499.     Output:
  500.         "list1" points to the first entry of the list master pointer.  It's segments
  501.             will be altered to contain the user specified data.
  502.  
  503.     Globals Modified:
  504.         none
  505.  
  506.     Returns:
  507.         none
  508. */
  509.  
  510.  
  511. static void buildList1( char * bitTable, listStruct * list1, short * func, short fNum )
  512. {
  513.     segmentStruct *    seg;
  514.     entryStruct *    entry;
  515.     short            i, indx, dec;
  516.     
  517.     for (i=0; i<fNum; i++)
  518.     {
  519.         // get segment number by looking up decimal in bit table
  520.         dec = func[i];
  521.         indx = (short) bitTable[dec];
  522.         seg = &(list1->segments[indx]);
  523.         
  524.         // add decimal data to list
  525.         entry = appendEntry( seg, 1, 0 );
  526.         entry->decimal[0] = (unsigned char) dec;
  527.     }
  528. }
  529.  
  530.  
  531. /* --------------------------------------------------------------------------------------------- */
  532.  
  533.  
  534. /*
  535.     static entryStruct * appendEntry( segmentStruct * seg, short decCount, short difCount )
  536.  
  537.     Description:
  538.         This routine expands segment to include a new entry.  The memory for the
  539.         entry sub-data is also allocated.  The calling function must fill this
  540.         space.
  541.  
  542.     Input:
  543.         "decCount" is the number of decimal entries to allocate in the new
  544.             "entry" struct.
  545.         "difCount" is the number of difference entries to allocate in the
  546.             new "entry" struct.
  547.  
  548.     Output:
  549.         "seg" is the segment data that is being expanded.
  550.  
  551.     Globals Modified:
  552.         none
  553.  
  554.     Returns:
  555.         Pointer to the new "entry" struct (the new element appended to "seg").
  556. */
  557.  
  558.  
  559. static entryStruct * appendEntry( segmentStruct * seg, short decCount, short difCount )
  560. {
  561.     entryStruct *    entry;
  562.     size_t            size;
  563.         
  564.     // insert a new entry in the array
  565.     (seg->count)++;
  566.     size = seg->count * sizeof( entryStruct );
  567.     seg->entries = realloc( seg->entries, size );
  568.     if (seg->entries == NULL)
  569.         lowMemory();
  570.     
  571.     // allocate decimal list for new entry
  572.     entry = &(seg->entries[seg->count - 1]);
  573.     entry->used = 0;
  574.     entry->decimal = calloc( decCount, sizeof( unsigned char ) );
  575.     if (entry->decimal == NULL)
  576.         lowMemory();
  577.     
  578.     // allocate difference list for new entry
  579.     if (difCount <= 0)
  580.         entry->difference = NULL;
  581.     else
  582.     {
  583.         entry->difference = calloc( difCount, sizeof( unsigned char ) );
  584.         if (entry->difference == NULL)
  585.             lowMemory();
  586.     }
  587.     
  588.     return entry;
  589. }
  590.  
  591.  
  592. /* --------------------------------------------------------------------------------------------- */
  593.  
  594.  
  595. static long printResults( listStruct * list, short actualVars )
  596. {
  597.     segmentStruct *    seg;
  598.     entryStruct *    entry;
  599.     long            count;
  600.     short            i, j, k, minLevel;
  601.  
  602.     printf( "\n--------------------------------------------\n" );
  603.     printf( "Prime Implicants (x%d is MSB, x0 is LSB):\n\n", actualVars - 1 );
  604.  
  605.     count = 0L;
  606.     minLevel = 0;
  607.     for (i=0; i<actualVars; i++, list++)
  608.     {
  609.         if (list->count <= 0)
  610.             continue;
  611.  
  612.         seg = list->segments;
  613.         for (j=0; j<list->count; j++, seg++)
  614.         {
  615.             if (seg->count <= 0)
  616.                 continue;
  617.  
  618.             entry = seg->entries;
  619.             for (k=0; k<seg->count; k++, entry++)
  620.             {
  621.                 if (!(entry->used))
  622.                 {
  623.                     printEntry( entry->decimal, entry->difference, list->listNum,
  624.                         actualVars, &minLevel );
  625.                     count++;
  626.                 }
  627.             }
  628.         }
  629.     }
  630.  
  631.     if (!count)
  632.         printf( "\n*** ERROR!  No prime implicants found. ***\n" );
  633.  
  634.     return count;
  635. }
  636.  
  637.  
  638. /* --------------------------------------------------------------------------------------------- */
  639.  
  640.  
  641. static void simplifyList( listStruct * list )
  642. {
  643.     segmentStruct *    seg;
  644.     entryStruct *    entry, * ecomp;
  645.     short            i, j, k, numDec, numDif, countm1;
  646.     
  647.     numDif = list->listNum - 1;
  648.     numDec = 1 << numDif;
  649.     seg = list->segments;
  650.     
  651.     for (i=0; i<list->count; i++, seg++)
  652.     {
  653.         if (seg->count <= 0)
  654.             continue;
  655.  
  656.         // sort all entries in all segments
  657.         entry = seg->entries;
  658.         for (j=0; j<seg->count; j++, entry++)
  659.         {
  660.             if (numDec > 1)
  661.             {
  662.                 qsort( entry->decimal, (size_t) numDec, sizeof( unsigned char ),
  663.                     ucharSortFunc );
  664.             }
  665.             if (numDif > 1)
  666.             {
  667.                 qsort( entry->difference, (size_t) numDif, sizeof( unsigned char ),
  668.                     ucharSortFunc );
  669.             }
  670.         }
  671.  
  672.         // remove duplicate entries in segments
  673.         countm1 = seg->count - 1;
  674.         entry = seg->entries;
  675.         for (j=0; j<countm1; j++, entry++)
  676.         {
  677.             ecomp = &(seg->entries[j+1]);
  678.             for (k=j+1; k<seg->count; k++, ecomp++)
  679.             {
  680.                 if (memcmp( entry->decimal, ecomp->decimal, (size_t) numDec ))
  681.                     continue;
  682.                 if (memcmp( entry->difference, ecomp->difference, (size_t) numDif ))
  683.                     continue;
  684.                     
  685.                 // duplicate entry, remove it
  686.                 free( ecomp->decimal );
  687.                 free( ecomp->difference );
  688.                 memcpy( &(seg->entries[k]), &(seg->entries[k+1]),
  689.                     (seg->count - k - 1) * sizeof( entryStruct ) );
  690.  
  691.                 // update our counters
  692.                 (seg->count)--;
  693.                 countm1--;
  694.                 ecomp--;    // decrement "ecomp" since it will be incremented (end of loop)
  695.                 k--;        // decrement "k" for reason above
  696.             }
  697.         }
  698.     }
  699. }
  700.  
  701.  
  702. /* --------------------------------------------------------------------------------------------- */
  703.  
  704.  
  705. static int ucharSortFunc( const void * a1, const void * a2 )
  706. {
  707.     unsigned char    v1, v2;
  708.  
  709.     v1 = *((unsigned char *) a1);
  710.     v2 = *((unsigned char *) a2);
  711.     if (v1 < v2)
  712.         return -1;
  713.     if (v1 > v2)
  714.         return 1;
  715.     return 0;
  716. }
  717.  
  718.  
  719. /* --------------------------------------------------------------------------------------------- */
  720.  
  721.  
  722. #if DEBUG
  723. static void dumpList( listStruct * list )
  724. {
  725.     segmentStruct *    seg;
  726.     entryStruct *    entry;
  727.     short            i, j, numDec, numDif;
  728.     
  729.     numDif = list->listNum - 1;
  730.     numDec = 1 << numDif;
  731.     fprintf( fp, "\n ---------------------- Dump List = %d  ----------------------\n", list->listNum );
  732.     
  733.     if ((seg = list->segments) == NULL)
  734.         return;
  735.     for (i=0; i<list->count; i++, seg++)
  736.     {
  737.         if (seg->count <= 0)
  738.             continue;
  739.         fprintf( fp, "\nsegment = %d\n", i );
  740.         
  741.         if ((entry = seg->entries) == NULL)
  742.             continue;
  743.         for (j=0; j<seg->count; j++, entry++)
  744.         {
  745.             if (entry->decimal == NULL)
  746.                 continue;
  747.             
  748.             fprintf( fp, "    " );
  749.             printNumbers( fp, entry->decimal, numDec );
  750.             if (entry->difference != NULL)
  751.             {
  752.                 fprintf( fp, "    " );
  753.                 printNumbers( fp, entry->difference, numDif );
  754.             }
  755.             fprintf( fp, "    %c\n", (entry->used) ? 'Y' : 'N' );
  756.         }
  757.     }
  758.     fputc( '\n', fp );
  759. }
  760. #endif
  761.  
  762.  
  763. /* --------------------------------------------------------------------------------------------- */
  764.  
  765.  
  766. static irredundant * primes2Irredundant( listStruct * list, long count, short actualVars )
  767. {
  768.     irredundant *    ir;
  769.     irElement *        elem;
  770.     segmentStruct *    seg;
  771.     entryStruct *    entry;
  772.     size_t            size;
  773.     short            i, j, k;
  774.  
  775.     // allocate main buffer to store irredundant info
  776.     ir = (irredundant *) malloc( sizeof( irredundant ) );
  777.     if (ir == NULL)
  778.         lowMemory();
  779.  
  780.     // allocate expected array size
  781.     ir->irArray = calloc( (size_t) count, sizeof( irElement ) );
  782.     if (ir->irArray == NULL)
  783.         lowMemory();
  784.  
  785.     // initialize
  786.     ir->len = 0;
  787.     elem = ir->irArray;
  788.  
  789.     // loop through all segments
  790.     for (i=0; i<actualVars; i++, list++)
  791.     {
  792.         if (list->count <= 0)
  793.             continue;
  794.  
  795.         seg = list->segments;
  796.         for (j=0; j<list->count; j++, seg++)
  797.         {
  798.             if (seg->count <= 0)
  799.                 continue;
  800.  
  801.             entry = seg->entries;
  802.             for (k=0; k<seg->count; k++, entry++)
  803.             {
  804.                 if (entry->used)
  805.                     continue;
  806.  
  807.                 // check to see if we need a larger array (should not happen)
  808.                 if (count-- < 0)
  809.                 {
  810.                     size = ((size_t) ir->len + 1) * sizeof( irElement );
  811.                     ir->irArray = realloc( ir->irArray, size );
  812.                     if (ir->irArray == NULL)
  813.                         lowMemory();
  814.                     elem = &(ir->irArray[ir->len]);
  815.                     memset( &elem, 0, sizeof( irElement ) );
  816.                 }
  817.  
  818.                 elem->decimal = entry->decimal;
  819.                 elem->difference = entry->difference;
  820.                 elem->level = i + 1;
  821.                 (ir->len)++;
  822.                 elem++;
  823.  
  824.                 // make sure we don't free the prime implicants
  825.                 entry->decimal = NULL;
  826.                 entry->difference = NULL;
  827.             }
  828.         }
  829.     }
  830.  
  831.     return ir;
  832. }
  833.