hall.c 3.4 KB

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