/* ************************************* */
/*   mfg.c                               */
/*   Copyright 2001 Martin L"auter       */
/*   laeuter@mathematik.uni-leipzig.de   */
/*   improved by Jean-Charles Meyrignac  */
/*   euler@free.fr                       */
/* ************************************* */

#include <stdio.h>
#define a (n1-1)
#define b (n2-1)
#define FREQ 4
#define CNTMETHOD 2
#define DIAGNOSIS 0
#define MAX_ANF 32

typedef struct {
  int nr,wlen,slen,inwlen,inslen;
} TInfo;

TInfo *info;
int anf[MAX_ANF];
unsigned char lenneeded[16];

int ctr,mctr,n1,n2;

char *RealName;

int IsSymmetric()
{
	int x, y;
	if (n1 != n2) return 0;
	for (x = 1;x < n1-1;++x)
	{
		for (y = 1;y < n1-1;++y)
		{
			if (info[y*n1+x].nr >= 128 && info[x*n1+y].nr >= 128) continue;
			if (info[y*n1+x].nr < 128 && info[x*n1+y].nr < 128) continue;
			return 0;
		}
	}
	return 1;
}

void gibtext(int i, int j)
{ int p;
  p=j*n1+i;
  if(info[p].wlen) {
    if(info[p-n1].nr>=0) {
      printf("  feld[%d].mask=feld[%d].smask&(*((NODE *)(feld[%d].wnode)));\n",info[p].nr,info[p].nr,info[p].nr);
    } else {
      if(info[p].slen) {
        if(info[p].wlen!=info[p].slen) {
          printf("  feld[%d].mask=feld[%d].smask&(*((NODE *)(feld[%d].wnode)));\n",info[p].nr,info[p].nr,info[p].nr);
        } else {
          printf("  feld[%d].mask=feld[%d].smask;\n",info[p].nr,info[p].nr);
        }
      } else {
        printf("  feld[%d].mask=(*((NODE *)(feld[%d].wnode)));\n",info[p].nr,info[p].nr);
      }
    }
  } else {
    if(info[p-1].nr<0) {
      printf("  feld[%d].mask=feld[%d].smask;\n",info[p].nr,info[p].nr);
    }
  }
  printf("m%d:\n",mctr);
//  printf("fprintf(stderr,\" @%d\");\n",mctr);
	printf(" mask=feld[%d].mask;\n", info[p].nr);
  if(mctr) {
    if(DIAGNOSIS) {
      printf("  if(mask==0) { acc[%d]++; goto m%d; }\n",info[p].nr,mctr-1);
    } else {
      printf("  if(mask==0) { goto m%d; }\n",mctr-1);
    }
  } else { printf("  if(mask==0) return;\n"); }
  printf("  maske=mask&(-mask); feld[%d].mask=mask^maske;\n",info[p].nr);
  if((info[p+1].nr>=0)||(info[p+n1].nr>=0)) {

	  if (info[p].nr == 1 && IsSymmetric())
	  {
		  printf(" savesym=maske;\n");
	  }
	  else if (info[p].nr == n1-2 && IsSymmetric())
	  {
		  printf("\tif (maske < savesym) goto m%d;\n", mctr);
	  }

    switch(CNTMETHOD) {
      case 1: printf("  log=(31-__cntlzw(maske))<<2;\n"); break;
      case 2: printf("  log=0; if(maske&0xffff0000) { maske>>=16; log=16; }\n");
              printf("  if(maske&0xff00) { maske>>=8; log+=8; }\n");
              printf("  log+=logtab[maske];"); break;
      case 3: printf("  log=logtab[(maske*0x4653adf)>>27];\n"); break;
      default: break;
    }
    if(info[p+n1].nr>=0) {
      if(0!=0) { /* evtl. noch Beginn eines Wortes testen */
        printf("  mask=*(uint32 *)(feld[%d].snode=dawg%d+PTR(*(NODE *)(feld[%d].snode+log)));\n",info[p+n1].nr,info[p].inslen,info[p].nr);
        printf("  if((feld[%d].smask=(*(uint32 *)(feld[%d].wnode))&mask)==0) { mask=feld[%d].mask; goto m%d; }\n",info[p+n1].nr,info[p+n1].nr,info[p].nr,mctr);
      } else {
		  //printf("  feld[%d].smask=*(uint32 *)(feld[%d].snode=dawg%d+PTR(*(NODE *)(feld[%d].snode+log)));\n",info[p+n1].nr,info[p+n1].nr,info[p].inslen,info[p].nr);
		  printf("  feld[%d].smask=*(uint32 *)(feld[%d].snode=(NODE *)feld[%d].snode[log]);\n",info[p+n1].nr,info[p+n1].nr,info[p].nr);
      }
    }
    if(info[p+1].nr>=0) {
      if((info[p+1-n1].nr>=0)||(info[p+1].slen>0)) {
		  //printf("  mask=feld[%d].mask=feld[%d].smask&(*(uint32 *)(feld[%d].wnode=dawg%d+PTR(*(NODE *)(feld[%d].wnode+log))));\n",info[p+1].nr,info[p+1].nr,info[p+1].nr,info[p].inwlen,info[p].nr);
		  printf("  mask=feld[%d].mask=feld[%d].smask&(*(uint32 *)(feld[%d].wnode=(NODE *)feld[%d].wnode[log]));\n",info[p+1].nr,info[p+1].nr,info[p+1].nr,info[p].nr);
      } else {
		  //printf("  mask=feld[%d].mask=*(uint32 *)(feld[%d].wnode=dawg%d+PTR(*(NODE *)(feld[%d].wnode+log)));\n",info[p+1].nr,info[p+1].nr,info[p].inwlen,info[p].nr);
		  printf("  mask=feld[%d].mask=*(uint32 *)(feld[%d].wnode=(NODE *)feld[%d].wnode[log])));\n",info[p+1].nr,info[p+1].nr,info[p].nr);
      }
    }
    if(--ctr==0)
	{
      printf("  if (saveausgabe()<0) { goto m%d;}\n", mctr);
	}
    
  }
  mctr++;
}  

int main(int argc,char **argv)
{ int s,i,j,sanf0,c,nsp,anzf; FILE *fin;
  n1=n2=0; info=NULL;
  RealName = argv[1];
  if(fin=fopen(argv[1],"rb")) {
    s=0;
    while((c=getc(fin))!=EOF) {
		if (c == 13) continue;
      if(c=='\n') {
		  if (s)
		  {
			if(n1<s) n1=s;
			n2++; s=0;
		  }
      } else {
        s++;
      }
    }
    fclose(fin);
    n1+=2; n2+=2;
    info=(TInfo *)malloc(sizeof(TInfo)*n1*n2);
  }
  if(info&&(fin=fopen(argv[1],"rb"))) {
    for(i=n2*n1-1;i>=0;i--) {
      info[i].nr=-1;
      info[i].wlen=info[i].slen=info[i].inwlen=info[i].inslen=0;
    }
    j=n1; s=1; i=0;
    while((c=getc(fin))!=EOF) {
		if (c==13) continue;
      if(c=='\n') {
        j+=n1;
        s=1;
      } else {
        if(c!=' ') {
          info[j+s].nr=i++;
        }
        s++;
      }
    }
    fclose(fin);
  }
  anzf=i;
  s=0;
  for(j=1;j<n2-1;j++) {
    for(i=1;i<n1-1;i++) {
      if((info[j*n1+i-1].nr<0)&&(info[j*n1+i+1].nr>=0)&&(info[j*n1+i].nr>=0)) {
        if(s==MAX_ANF) {
          fprintf(stderr,"Too many word beginnings (%d)\n",s);
          exit(1);
        }
        anf[s++]=j*n1+i;
      }
    }
  }
  sanf0=s;
  for(j=1;j<n2-1;j++) {
    for(i=1;i<n1-1;i++) {
      if((info[(j-1)*n1+i].nr<0)&&(info[(j+1)*n1+i].nr>=0)&&(info[j*n1+i].nr>=0)) {
        if(s==MAX_ANF) {
          fprintf(stderr,"Too many word beginnings (%d)\n",s);
          exit(1);
        }
        anf[s++]=j*n1+i;
      }
    }
  }
  if(s==0) return(0);
  for(i=0;i<16;i++) lenneeded[i]=0;
  for(i=0;i<sanf0;i++) {
    for(j=anf[i];info[j].nr>=0;j++);
    info[anf[i]].wlen=j-=anf[i];
    if(j>15) {
      fprintf(stderr,"Too long a word\n");
      exit(1);
    }
    lenneeded[j]++;
    for(j=anf[i];info[j].nr>=0;info[j++].inwlen=info[anf[i]].wlen);
  }
  for(;i<s;i++) {
    for(j=anf[i];info[j].nr>=0;j+=n1);
    info[anf[i]].slen=j=(j-anf[i])/n1;
    if(j>15) {
      fprintf(stderr,"Too long a word\n");
      exit(1);
    }
    lenneeded[j]++;
    for(j=anf[i];info[j].nr>=0;j+=n1) info[j].inslen=info[anf[i]].slen;
  }
  printf("#include <stdio.h>\n");
  printf("#include <stdlib.h>\n");
  printf("#include <string.h>\n");
  printf("#include <windows.h>\n");
  //printf("#include \"MDawg.h\"\n");
  //printf("#include \"MDawg.cpp\"\n\n");

  printf("typedef unsigned int uint32;\n\n");
  printf("typedef unsigned int NODE;\n");
  printf("typedef struct\n");
  printf("{\n");
  printf("\tNODE *snode,*wnode;\n");
  printf("\tuint32 smask,mask;\n");
  printf("} TFeld;\n\n");
  

  printf("typedef struct\n");
  printf("{\n");
  printf("\tNODE *dawg,*firstnode;\n");
  printf("} DAWG;\n");
  
  j=0;
  for(i=2;i<16;i++)
  {
	  if(lenneeded[i])
	  {
		  printf(j?",*dawg%d":"DAWG dawg%d",i);
		  j++;
	  }
  }
  printf(";\n\n");
  
  switch(CNTMETHOD) {
    case 2: printf("unsigned int logtab[256];\n\n"); break;
    case 3: printf("unsigned int logtab[32]={ 0,4,8,24,12,44,28,64,16,56,48,84,32,92,68,104,124,20,40,60,52,80,88,100,120,36,76,96,116,72,112,108};\n\n");
    default: break;
  }
  printf("TFeld feld[%d];\n\n",anzf);

  printf("FILE *fout;\n\n");
  if(DIAGNOSIS) printf("unsigned int acc[%d];\n\n",anzf);
  
  printf("unsigned char partstr[] = {");
  for(j=n1+1;j<=n1+FREQ;j++)
  {
	  if(info[j].nr>=0)
	  {
		  printf("%d,",128+info[j].nr);
	  } 
	  else
	  {
		  printf("' ',"); nsp--; 
	  }
  }
  printf("0};\n\n");
  
  
  printf("unsigned char fullstr[] = {\n  ");
  for(j=1;j<n2-1;j++) {
    nsp=0;
    for(i=1;i<n1-1;i++) {
      if(info[j*n1+i].nr>=0) {
        while(nsp) { printf("' ',"); nsp--; }
        printf("%d,",128+info[j*n1+i].nr);
      } else nsp++;
    }
    if(j<n2-2) {
      printf("'\\n',\n  ");
    } else {
      printf("0 };\n\n");
    }
  }
  printf("unsigned char letters[]=\"?ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ\";\n\n");
  printf("static unsigned char logs[16]={0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3};\n");
  printf("char savestat[%d];\n", FREQ);
  if (IsSymmetric())
  {
	  printf("unsigned int savesym;\n");
  }
  

  printf("void relocate(NODE *node, NODE *reloc, int Pass)\n");
  printf("{\n");
  printf("\tNODE next;\n");
  printf("\tunsigned int log, mask, maske;\n");
  printf("\tmask = *node;\n");
  printf("\twhile(mask)\n");
  printf("\t{\n");
  printf("\t\tmaske=mask&(-mask);\n");
  printf("\t\tmask ^= maske;\n");
  printf("\t\tlog=0;\n");
  printf("\t\tif(maske&0xffff0000) { maske>>=16; log+=16; }\n");
  printf("\t\tif(maske&0xff00) { maske>>=8; log+=8; }\n");
  printf("\t\tif(maske&0xf0) { maske>>=4; log+=4; }\n");
  printf("\t\tlog+=logs[maske];\n");
  printf("\t\tnext = (node[log]&0xFFFFFCL)>>2;\n");
  printf("\t\tif (next)\n");
  printf("\t\t{\n");
  printf("\t\t\tif (Pass&&!(node[log] & 1)) continue;\n");
  printf("\t\t\trelocate(reloc+next,reloc,Pass);\n");
  printf("\t\t\tif (!Pass)\n");
  printf("\t\t\t\tnode[log] |= 1;\n");
  printf("\t\t\telse\n");
  printf("\t\t\t\tnode[log] = (NODE)(reloc+next);\n");
  printf("\t\t}\n");
  printf("\t\telse\n");
  printf("\t\t{\n");
  printf("\t\t\tnode[log] = 0;\n");
  printf("\t\t}\n");
  printf("\t}\n");
  printf("}\n");
  
  printf("void LoadDawg(char *name, DAWG *Dawg)\n");
  printf("{\n");
  printf("\tFILE *fin;\n");
  printf("\tlong info[4];\n");
  printf("\tDawg->dawg=NULL;\n");
  printf("\tDawg->firstnode=NULL;\n");
  printf("\tif ((fin=fopen(name,\"rb\"))==NULL)\n");
  printf("\t{\n");
  printf("\t\tfprintf(stderr,\"Cannot open DAWG-File (%%s) !\\n\",name);\n");
  printf("\t\texit(1);\n");
  printf("\t}\n");
  printf("\tfread(info,sizeof(long),4,fin);\n");
  printf("\tif(((info[0]&0xff000000)!=0xff000000)&&(info[0]!=0x01234567))\n");
  printf("\t{\n");
  printf("\t\tfprintf(stderr,\"Bad DAWG format\\n\");\n");
  printf("\t\texit(1);\n");
  printf("\t}\n");
  
  printf("\tif((Dawg->dawg=(NODE *)malloc(info[1]))==NULL)\n");
  printf("\t{\n");
  printf("\t\tfprintf(stderr,\"Not enough memory for DAWG\\n\");\n");
  printf("\t\texit(1);\n");
  printf("\t}\n");
  printf("\tfread(Dawg->dawg,1,info[1],fin);\n");
  printf("\tDawg->firstnode=(NODE *)(((unsigned char *)Dawg->dawg)+info[2]);\n");
  printf("\trelocate(Dawg->firstnode,Dawg->dawg,0);\n", i, i);
  printf("\trelocate(Dawg->firstnode,Dawg->dawg,1);\n", i, i);
  
  printf("\tfclose(fin);\n");
  printf("}\n");
  
  printf("void FreeDawg(DAWG *Dawg)\n");
  printf("{\n");
  printf("\tif (Dawg->dawg != NULL)\n");
  printf("\t{\n");
  printf("\t\tfree(Dawg->dawg);\n");
  printf("\t\tDawg->dawg = NULL;\n");
  printf("\t}\n");
  printf("}\n");
  


  printf("int saveausgabe()\n");
  printf("{\n");
  printf("\tint zp;\n");
  printf("\tFILE *fout;\n");
  printf("\tunsigned char zeile[%d];\n",(n1+3)*(n2-2)+1);
  printf("\tunsigned int mask,log;\n");
  printf("\tunsigned char *ctrl=partstr;\n");
  printf("\tTFeld *fp;\n");
  printf("\tzp=0;\n");
  printf("\twhile(*ctrl)\n");
  printf("\t{\n");
  printf("\t\tif(*ctrl>=128)\n");
  printf("\t\t{\n");
  printf("\t\t\tfp=&(feld[(*ctrl)-128]);\n");
  printf("\t\t\tmask=fp->mask^(*fp->wnode&*fp->snode);\n");
  printf("\t\t\tlog=0;\n");
  printf("\t\t\tif(mask&0xffff0000) { log=16; mask>>=16; }\n");
  printf("\t\t\tif(mask&0xff00) { log+=8; mask>>=8; }\n");
  printf("\t\t\tif(mask&0xf0) { log+=4; mask>>=4; }\n");
  printf("\t\t\tlog+=logs[mask];\n");
  printf("\t\t\tzeile[zp++]=letters[log];\n");
  printf("\t\t}\n");
  printf("\t\telse\n");
  printf("\t\t{\n");
  printf("\t\t\tzeile[zp++]=*ctrl;\n");
  printf("\t\t}\n");
  printf("\t\tctrl++;\n");
  printf("\t}\n");
  printf("\tzeile[zp++]='\\n';\n");
  printf("\tzeile[zp]=0;\n");
  printf("\tif (memcmp(zeile, savestat, %d)<0) return -1;\n", FREQ);
  printf("\tprintf(\"%%s\",zeile);\n");
  printf("\tfout=fopen(\"%s.sav\", \"wb\");\n", RealName);
  printf("\tfwrite(zeile, %d,1,fout);\n", FREQ);
  printf("\tfclose(fout);\n");
  
  printf("\treturn 0;\n");
  printf("}\n\n");
  
  printf("void fullausgabe()\n");
  printf("{\n");
  printf("\tFILE *fout;\n");
  printf("\tunsigned char *ctrl=fullstr;\n");
  printf("\tint zp;\n");
  printf("\tunsigned char zeile[%d];\n",(n1+3)*(n2-2)+1);
  printf("\tunsigned int mask,log;\n");
  printf("\tTFeld *fp;\n");
  printf("\tzp=0;\n");
  printf("\twhile(*ctrl)\n");
  printf("\t{\n");
  printf("\t\tif(*ctrl>=128)\n");
  printf("\t\t{\n");
  printf("\t\t\tfp=&(feld[(*ctrl)-128]);\n");
  printf("\t\t\tmask=fp->mask^(*fp->wnode&*fp->snode);\n");
  printf("\t\t\tlog=0;\n");
  printf("\t\t\tif(mask&0xffff0000) { log=16; mask>>=16; }\n");
  printf("\t\t\tif(mask&0xff00) { log+=8; mask>>=8; }\n");
  printf("\t\t\tif(mask&0xf0) { log+=4; mask>>=4; }\n");
  printf("\t\t\tlog+=logs[mask];\n");
  printf("\t\t\tzeile[zp++]=letters[log];\n");
  printf("\t\t}\n");
  printf("\t\telse\n");
  printf("\t\t{\n");
  printf("\t\t\tzeile[zp++]=*ctrl;\n");
  printf("\t\t}\n");
  printf("\t\tctrl++;\n");
  printf("\t}\n");
  printf("\tzeile[zp++]='\\n';\n");
  printf("\tzeile[zp]=0;\n");
  printf("\tfout=fopen(\"%s.res\",\"at\");\n",argv[1]);
  printf("\tfprintf(fout,\"%%s\\n\",zeile);\n");
  printf("\tfclose(fout);\n");
  printf("\tprintf(\"%%s\\n\",zeile);\n");
  printf("}\n\n");
  
  
  printf("void doform()\n{ uint32 mask,maske; int log;");
  
  ctr=FREQ;
  mctr=0;
  for(j=1;j<n2-1;j++) {
    for(i=1;i<n1-1;i++) {
      if(info[j*n1+i].nr>=0) gibtext(i,j);
    }
  }
  printf("  fullausgabe();\n goto m%d;\n}\n\n",mctr-1);
  
  printf("int main()\n{\n");
  printf("\tint i;\n");
  printf("\tFILE *fout;\n");
  printf("\tint start, end;\n");

  for(i=2;i<16;i++)
  {
	  if(lenneeded[i])
	  {
		  printf("\tLoadDawg(\"rdawg%d.pck2\",&dawg%d);\n",i,i);
	  }
  }
  printf("\tfout=fopen(\"%s.sav\", \"rb\");\n", RealName);
  printf("\tif (fout)\n");
  printf("\t{\n");
  printf("\t\tfread(savestat, %d,1,fout);\n", FREQ);
  printf("\t\tfclose(fout);\n");
  printf("\t}\n");
  
  for(i=0;i<sanf0;i++)
  {
	  printf("\tfeld[%d].wnode=dawg%d.firstnode;\n",info[anf[i]].nr,info[anf[i]].wlen);
  }
  for(;i<s;i++)
  {
	  printf("\tfeld[%d].smask=*(feld[%d].snode=dawg%d.firstnode);\n",info[anf[i]].nr,info[anf[i]].nr,info[anf[i]].slen);
  }
  if(CNTMETHOD==2) {
    printf("  for(i=0;i<8;i++) logtab[1<<i]=i;\n");
  }
  if(DIAGNOSIS) {
    printf("  for(i=0;i<%d;i++) acc[i]=0;\n",anzf);
  }
  for(j=1;j<n2-1;j++)
  {
	  for(i=1;i<n1-1;i++)
	  {
		  if((info[j*n1+i].nr>=0)&&(info[(j-1)*n1+i].nr<0)&&(info[j*n1+i].slen==0))
		  {
			  printf("\tfeld[%d].snode=dawg%d.firstnode;\n",info[j*n1+i].nr,info[j*n1+i].inwlen);
		  }
	  }
  }
  for(j=1;j<n2-1;j++)
  {
	  for(i=1;i<n1-1;i++)
	  {
		  if((info[j*n1+i].nr>=0)&&(info[j*n1+i-1].nr<0)&&(info[j*n1+i].wlen==0))
		  {
			  printf("\tfeld[%d].wnode=dawg%d.firstnode;\n",info[j*n1+i].nr,info[j*n1+i].inslen);
		  }
	  }
  }
  printf("\tstart = GetTickCount();\n");
  printf("\tdoform();\n");
  printf("\tend = GetTickCount();\n");
  printf("\tfout=fopen(\"%s.res\",\"at\");\n", RealName);
  printf("\tfprintf(fout,\"Finished in %%d milliseconds\\n\",end-start);\n");
  if(DIAGNOSIS)
  {
	  printf("\tfor(i=0;i<%d;i++) fprintf(fout, \"%%I64d \", Nodes[i]);\n", anzf);
	  printf("\tfprintf(fout, \"\\n\");\n");
  }
  printf("\tfclose(fout);\n");
  for(i=2;i<16;i++)
  {
	  if(lenneeded[i])
	  {
		  printf("\tFreeDawg(&dawg%d);\n",i);
	  }
  }
  printf("  return(0);\n}\n");
  return(0);
}