hall.c 3.4 KB

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