util/ncgg/hall.c

   1 /*
   2  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
   3  * See the copyright notice in the ACK home directory, in the file "Copyright".
   4  */
   5 #ifndef NORCSID
   6 static char rcsid[]= "$Id: hall.c,v 0.4 1994/06/24 10:37:23 ceriel Exp $";
   7 #endif
   8
   9 #include "assert.h"
  10 #include "param.h"
  11 #include "set.h"
  12 #include <stdio.h>
  13
  14 /*
  15  * This file implements the marriage thesis from Hall.
  16  * The thesis says that given a number, say N, of subsets from
  17  * a finite set, it is possible to create a set with cardinality N,
  18  * that contains one member for each of the subsets,
  19  * iff for each number, say M, of subsets from 2 to N the union of
  20  * each M-tuple sets has cardinality >= M.
  21  *
  22  * So what, you might say. As indeed I did.
  23  * But this is actually used here to check the possibility of each
  24  * code rule. If a code rule has a number of token_sets in the with
  25  * clause and a number of properties in the uses rule it must be
  26  * possible to do this from an empty fakestack. Hall helps.
  27  */
  28
  29 #define MAXHALL (TOKPATMAX+MAXALLREG)
  30 short hallsets[MAXHALL][SETSIZE];
  31 int nhallsets= -1;
  32 int hallfreq[MAXHALL][2];
  33
  34 hallverbose() {
  35         register i;
  36         register max;
  37
  38         fprintf(stderr,"Table of hall frequencies\n   #   pre   post\n");
  39         for (max=MAXHALL-1;hallfreq[max][0]==0 && hallfreq[max][1]==0;max--)
  40                 ;
  41         for (i=0;i<=max;i++)
  42                 fprintf(stderr,"%3d%6d%6d\n",i,hallfreq[i][0],hallfreq[i][1]);
  43 }
  44
  45 inithall() {
  46
  47         assert(nhallsets == -1);
  48         nhallsets=0;
  49 }
  50
  51 nexthall(sp) register short *sp; {
  52         register i;
  53
  54         assert(nhallsets>=0);
  55         for(i=0;i<SETSIZE;i++)
  56                 hallsets[nhallsets][i] = sp[i];
  57         nhallsets++;
  58 }
  59
  60 card(sp) register short *sp; {
  61         register sum,i;
  62
  63         sum=0;
  64         for(i=0;i<8*sizeof(short)*SETSIZE;i++)
  65                 if (BIT(sp,i))
  66                         sum++;
  67         return(sum);
  68 }
  69
  70 checkhall() {
  71
  72         assert(nhallsets>=0);
  73         if (!hall())
  74                 error("Hall says: \"You can't have those registers\"");
  75 }
  76
  77 hall() {
  78         register i,j,k;
  79         int ok;
  80
  81         hallfreq[nhallsets][0]++;
  82         /*
  83          * If a set has cardinality >= nhallsets it can never be the cause
  84          * of the hall algorithm failing. So it can be thrown away.
  85          * But then nhallsets is less, so this step can be re-applied.
  86          */
  87
  88         do {
  89                 ok = 0;
  90                 for(i=0;i<nhallsets;i++)
  91                         if (card(hallsets[i])>=nhallsets) {
  92                                 for (j=i+1;j<nhallsets;j++)
  93                                         for(k=0;k<SETSIZE;k++)
  94                                                 hallsets[j-1][k] =
  95                                                         hallsets[j][k];
  96                                 nhallsets--;
  97                                 ok = 1;
  98                                 break;
  99                         }
 100         } while (ok);
 101
 102         /*
 103          * Now all sets have cardinality < nhallsets
 104          */
 105
 106         hallfreq[nhallsets][1]++;
 107         ok=recurhall(nhallsets,hallsets);
 108         nhallsets = -1;
 109         return(ok);
 110 }
 111
 112 recurhall(nhallsets,hallsets) short hallsets[][SETSIZE]; {
 113         short copysets[MAXHALL][SETSIZE];
 114         short setsum[SETSIZE];
 115         register i,j,k,ncopys;
 116
 117         /*
 118          * First check cardinality of union of all
 119          */
 120         for(k=0;k<SETSIZE;k++)
 121                 setsum[k]=0;
 122         for(i=0;i<nhallsets;i++)
 123                 unite(hallsets[i],setsum);
 124         if (card(setsum)<nhallsets)
 125                 return(0);
 126         /*
 127          * Now check the hall property of everything but one set,
 128          * for all sets
 129          */
 130         for(i=0;i<nhallsets;i++) {
 131                 ncopys=0;
 132                 for(j=0;j<nhallsets;j++) if (j!=i) {
 133                         for(k=0;k<SETSIZE;k++)
 134                                 copysets[ncopys][k] = hallsets[j][k];
 135                         ncopys++;
 136                 }
 137                 assert(ncopys == nhallsets-1);
 138                 if (!recurhall(ncopys,copysets))
 139                         return(0);
 140         }
 141         return(1);
 142 }
 143
 144 unite(sp,into) register short *sp,*into; {
 145         register i;
 146
 147         for(i=0;i<SETSIZE;i++)
 148                 into[i] |= sp[i];
 149 }
 150
 151 /*
 152  * Limerick (rot13)
 153  *
 154  * N zngurzngvpvna anzrq Unyy
 155  * Unf n urknurqebavpny onyy,
 156  *      Naq gur phor bs vgf jrvtug
 157  *      Gvzrf uvf crpxre'f, cyhf rvtug
 158  * Vf uvf cubar ahzore -- tvir uvz n pnyy..
 159  */