#include <stdio.h>
/*#define register*/
#define int long
#define maxtext 2200000
#define maxwords 200000
#define bitmask unsigned int
#define MAXMASKS 3
#define maskwidth (8*sizeof(bitmask))
#define STACKMAX 32

typedef bitmask bitsig[MAXMASKS+1];
int     freqs[26];
bitsig  uflosig;
int     letmask[26];
int     letbit[26];
int     letwidth[26];
int     lastmask;
int     numwords;
char    *textnext;
bitmask *wordsigs;
char    *anawords[STACKMAX];
char    **anaptr;
int    anacount=0;
int targetwords=2;

void printanagram(char *target, int expected);
void die (char *ermsg);

int fieldwidth(int num)
{
  int tot = 0;
  while (num != 0) {
    tot += 1;
    num = num >> 1;
  }
  return(tot+1);
}

void choosefields(int *freqs)
{
  int letter;
  int curmask = 0, curbit = 0;
  int width;

  for (letter = 0; letter < 26; letter++)
    if (freqs[letter] != 0) {
      width = fieldwidth(freqs[letter]);
      if (curbit+width > maskwidth) {
        if (++curmask >= MAXMASKS) die("Sorry: Phrase too long to handle.\n");
        curbit = 0;
      }
      letmask[letter] = curmask;
      letbit[letter] = curbit;
      letwidth[letter] = width;
      curbit += width;
/*fprintf(stderr,"Field %c: w=%d\n", letter+'a',width);*/
    }
  if (curmask > lastmask) lastmask = curmask;
/*  fprintf(stderr,"1:lastmask=%d\n",lastmask);*/
}

void makefreqs(char *str, int *freq)
{
  char c;
  int i;
  for (i = 0; i < 26; i++) freq[i] = 0;
/*  printf("makefreqs: %s\n", str); */
  while ((c = *str++) != '\0') {
    if (('A' <= c) && (c <= 'Z')) c += 32;
    c -= 'a';
    if ((c >= 0) && (c < 26)) freq[c] += 1;
  }
}

void printone(bitmask b) {
  int i;
  for (i = 31; i >= 0; --i) {
    fprintf(stderr, "%c", ((b>>i)&1) + '0');
  }
}

void printmask(char c, bitmask *sig) {
return;
   fprintf(stderr,"%c", c);
   printone(sig[0]);
   if (lastmask > 0) printone(sig[1]);
   if (lastmask == 2) printone(sig[2]);
   fprintf(stderr," (%d)\n", lastmask);
}

void makeonesig(register char *str, bitmask sig[])
{
  register int l;
  int sfreqs[26];
  register bitmask fr;

  makefreqs(str, sfreqs);

/*  printf("Makeonesig: %s - lastmask = %d, &sig[0] = %08X\n",
          str, lastmask, &sig[0]); */
  for (l = 0; l <= lastmask; l++) sig[l] = 0;
/*  printf("Makeonesig #2: %s\n", str); */

  for (l = 0; l < 26; l++) {
/*    printf("Makeonesig #3: %s\n", str); */
      if (sfreqs[l]) {
        fr = ((bitmask) sfreqs[l]) << letbit[l];
/*        printf("Makeonesig #4: %s\n", str); */
        sig[letmask[l]] += fr;
/*        printf("Makeonesig #5: %s\n", str); */
      }
   }
/*  fprintf(stderr,"%s:\n", str);*/
  printmask('?',sig);
}

void makeuf(int freqs[], int letmask[], int letbit[], int letwidth[])
{
  int l;
  int bnum, bwidth;

  for (l = 0; l <= MAXMASKS; l++) uflosig[l] = 0;

  for (l = 0; l < 26; l++)
    if (freqs[l] != 0) {
      bnum = letbit[l];
      bwidth = letwidth[l];
      uflosig[letmask[l]] += (1L << (bnum+bwidth-1));
    }
}

#define DOMASK(MASK) { \
  /*fprintf(stderr,"node%d: %08X, sig: %08X\n", MASK, curnode[MASK], cursig[MASK]);*/ \
  newmask = curnode[MASK] - cursig[MASK]; \
  if ((newmask & uflosig[MASK])) break; \
  newsig[MASK] = newmask; \
  bitsleft = bitsleft | newmask; \
  /*fprintf(stderr,"bitsleft: %08X, newsig%d: %08X\n", bitsleft, MASK, newmask);*/ \
}


int findanagrams(
  register int curword,
  register bitmask *curnode,
  char *wordlist[],
  char *target
)
{
  bitsig newsig;
  register bitmask newmask;
  register bitmask *cursig;
  register int bitsleft;

  cursig = &wordsigs[curword * (lastmask+1)];

  while (curword < numwords) {
/*    fprintf(stderr,"Looking at wordlist[%d] '%s'\n", curword, wordlist[curword]);*/
    bitsleft = 0;
    if (lastmask > 2) {fprintf(stderr,"BUG 1\n");exit(0);}
    if (lastmask < 0) {fprintf(stderr,"BUG 2\n");exit(0);}
/*printmask(' ',curnode);*/
/*printmask('-',cursig); */
    switch (lastmask) {

    case 2: DOMASK(2)
    case 1: DOMASK(1)
    case 0: DOMASK(0)
/*printmask('=',newsig);*/

      *anaptr++ = wordlist[curword];
      if (!bitsleft) {
        printanagram(target,targetwords);
      } else {
/*        fprintf(stderr,"Extracted %s - Recursing! (%08X%08X%08X -> %08X%08X%08X)\n", wordlist[curword], cursig[0],cursig[1],cursig[2],
                                                                                newsig[0],newsig[1],newsig[2]);*/
        findanagrams(curword, newsig, wordlist, target);
/*        fprintf(stderr,"Extracted %s - RETURNED ! (%08X%08X%08X -> %08X%08X%08X)\n", wordlist[curword], cursig[0],cursig[1],cursig[2],
                                                                                newsig[0],newsig[1],newsig[2]);*/
      }
      --anaptr;
    }
    curword++;
    cursig += (lastmask+1);
  }
}

void printanagram(char *target, int expected)
{
  int wc;
  char **word;

  wc = 0;
  for (word = &anawords[0]; word != anaptr; word++) {
    wc ++;
  }
  if (wc == expected) {
    wc = 0;
    fprintf(stderr, "%s is an anagram of ", target);
    for (word = &anawords[0]; word != anaptr; word++) {
      printf("%s", *word); wc++;
      if ((expected > 1) && (wc != expected)) fprintf(stderr, "+");
    }
    printf("\n");
  }
}

void die (char *ermsg)
{
  printf(ermsg);
  exit(0);
}

int getline(char *s, int lim)
{
  int c, i;

  i = 0;
  while (--lim > 0 && (c=getc(stdin)) != EOF && c != '\n')
    s[i++] = c;
  if (c == '\n')
    s[i++] = '\0';
  s[i] = '\0';
  return(i);
}

int main(int argc, char **argv)
{
  int c;
  int i, len, compatible;
  char inittarget[64];
  char *target;
  char *textbuffer;
  char **wordlist;
  int wfreqs[26];
  FILE *dictf = fopen(argv[1], "r");

  textbuffer = (char *)malloc(maxtext);
  wordlist = (char **)malloc(maxwords*sizeof(char *));
  if ((textbuffer == NULL) || (wordlist == NULL)) {
    fprintf(stderr, "Not enough store\n");exit(0);
  }

  target = &inittarget[0];
  numwords = 0;
  anaptr = &anawords[0];
  textnext = &textbuffer[0];


  len = getline(target, 64);
  target = strcpy(textnext, target); 
  textnext += len+1;
  textnext = (char *) ((((int) textnext)+3) & (~3));
  makefreqs(target, freqs);

  fprintf(stderr,"Reading dictionary...\n");
  while ((c = fgetc(dictf)) != EOF) {
    compatible = 0;
    if ((c < 0) || (c > 128)) compatible = 1;
    wordlist[numwords] = textnext;
    *textnext++ = c;
    while ((c = fgetc(dictf)) != EOF && c != '\n') {
      if ((c < 0) || (c > 128)) compatible = 1;
      *textnext++ = c;
    }
    *textnext++ = '\0';
    /* If strlen(wordlist[numwords]) > strlen[target]) skip this... */
      makefreqs(wordlist[numwords], wfreqs);
      for (i= 0; i < 26; i++) {
        if (wfreqs[i] > freqs[i]) {
          compatible = 1; break;
        }
      }
      if (compatible==0) {
        fprintf(stderr,"Added %s\n", wordlist[numwords++]);
      }
  }
/*  fprintf(stderr, "Choosefields\n");*/
  choosefields(freqs);

  textnext = (char *)((((int)textnext)+3) & (~3));
  wordsigs = (bitmask *) &textnext[0];
label:                               

/*  fprintf(stderr,"Start of buffer: %08X, word ptr buff: %08X (%08X)\n",
         &textbuffer[0], &textnext[0], wordsigs);*/

  makeonesig(target, &wordsigs[numwords*(lastmask+1)]);
/*  fprintf(stderr, "makeuf\n");*/
  makeuf(freqs, letmask, letbit, letwidth);

  fprintf(stderr,"Calculating signatures...\n");

  for (i = 0; i < numwords; i++) {
/*fprintf(stderr,"makesig %s\n", wordlist[i]);*/
    makeonesig(wordlist[i], &wordsigs[i*(lastmask+1)]);
  }

  fprintf(stderr,"signatures done...\n");

  fprintf(stderr,"Search begins!!!\n");
  findanagrams(0, &wordsigs[numwords*(lastmask+1)], wordlist, target);

  fprintf(stderr,"PROGRAM FINISHED!\n");
  exit(0);
  return(0);
}