hall.c 3.2 KB

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