struct pol
       {
          unsigned long x,y;
          unsigned long cs;
          unsigned char *image;
          struct pol *np;
       };
struct poln
       {
          unsigned long cs;
          unsigned char image[8];
          struct poln *np;
       };

struct meml
       {
          struct poln sp[100];
          struct meml *nm;
       };

struct pol *pold1,*pold2,*pold3,*pold4;
struct poln *palt,*pneu,*lpoff,*poldn,*p1,*poff;
unsigned long poll,polnl,poli,polineu,polin,
         polipix,polix,poliy,offx,offy,tiefe,
         h,b,dis=80L,anz=0,anzx,anzd,ox,oy,adr,
         pich,picb,pico,picn,picz=500,ent=8192,
         blks=100,memp,interv;
void *malloc();
struct meml *malloc_own(); 
unsigned char *imagex,imageh[16],*bild;
struct poln **Entry;
struct meml *memp1,*memp2,*memakt;

main(argc,argv)
int argc;
unsigned char *argv[];
{
 struct poln *p1;

 if(argc < 2)					/* Wenn kein Parameter angegeben	*/
    polin=5;					/* wurde, standardmäßig 5 Steine	*/
 else						/* sonst Anzahl nach >polin<		*/
    sscanf(argv[1],"%ld",&polin);

 if(argc > 2)					/* Zeichen je Zeile für Ausgabe		*/
    sscanf(argv[2],"%ld",&dis);			/* Standard 80, bei 0 keine A.		*/
  
 Entry=(struct poln **) malloc((int)(ent*4));	/* Speicher für Hashtabelle		*/
 if(!Entry)					/* reservieren				*/
    printf("\nFehler bei malloc\n");

 bild=malloc((int)(picz*16));			/* Speicher für Ausgabebereich		*/
 if(!bild)					/* reservieren (500 x 16 Zeichen)	*/
    printf("\nFehler bei malloc\n");

 Init();					/* Diverse Initialisierungen		*/

 memp1=(struct meml *)-1L;			/* Pointer für eigene Speicher-		*/
 memp2=(struct meml *)-1L;			/* verwaltung initialisieren		*/

 pold1=(struct pol *) malloc((int)poll);        /* Initialisieren von vier 		*/
 pold1->x=polineu;				/* Zwischenspeichern für die		*/
 pold1->y=polineu;				/* interne Darstellung der 		*/
 pold1->image=malloc((int)256);			/* Polyominos mit 16 x 16		*/
 pold1->np=(struct pol *)-1L;			/* Punkten. Die Größe wurde		*/
						/* aus dem Grunde statisch 		*/
 pold2=(struct pol *)malloc((int)256);		/* gewählt, da so bei der Adress-	*/
 pold2->x=polineu;				/* berechnung statt einer Mul-		*/
 pold2->y=polineu;				/* tiplikation ein Linksshift		*/
 pold2->image=malloc((int)256);			/* um vier Bits möglich ist.		*/
 pold2->np=(struct pol *)-1L;			/* In diesen Zwischenspeichern		*/
						/* wird jeder gesetzte Stein in		*/
 pold3=(struct pol *)malloc((int)poll);		/* einem Byte abgelegt, was bei		*/
 pold3->x=polineu;				/* späteren Manipulationen		*/
 pold3->y=polineu;				/* (Drehung, Spiegelung, etc.)		*/
 pold3->image=malloc((int)256);			/* schneller ist als bei bit-		*/
 pold3->np=(struct pol *)-1L;			/* orientierter Speicherung.		*/

 pold4=(struct pol *)malloc((int)poll);		/* Struktur pol  -> byteweise		*/
 pold4->x=polineu;				/* Struktur poln -> bitweise		*/
 pold4->y=polineu;	
 pold4->image=malloc((int)256);
 pold4->np=(struct pol *)-1L;

 poldn=(struct poln *)malloc((int)polnl);	/* Initialisieren einer poln-		*/
 poldn->np=(struct poln *)-1L;			/* Struktur				*/

 Poliomino();					/* Aufruf des Hauptprogramms		*/

 anzd=picn=pico=pich=picb=0;

 ClearImage();					/* Löschen des Ausgabebereichs		*/

 while(pneu != (struct poln *)-1L)		/* Abarbeiten der Liste der		*/
 {						/* erzeugten Polyominos und		*/
    if(dis > 0L)				/* Ausgabe + Zählen			*/
       PicOut(pneu,polineu);

    anzd++;

    p1=pneu;
    pneu=pneu->np;
 }

 memp1=memp2;

 free_own();					/* Freigeben des Speichers		*/

 if(dis > 0L)					/* Ausgeben des letzten Ausgabe-	*/
    Out_Line();					/* bereichs				*/

 free(poldn,polnl);				/* Freigabe des Speicher der		*/
 free(pold4->image,256);			/* Zwischenstrukturen			*/
 free(pold4,poll);
 free(pold3->image,256);
 free(pold3,poll);
 free(pold2->image,256);
 free(pold2,poll);
 free(pold1->image,256);
 free(pold1,poll);

 free(bild,picz*16L);				/* Freigabe des Ausgabebereichs		*/
 free(Entry,ent*4L);				/* Freigabe der Hashtabelle		*/

 printf("\n%10ld Poliominos ermittelt\n",anzd);
}

Poliomino()
{
 for(poli=1;poli<polin;poli++)                  /* Hauptschleife			*/
     Poli_1();
}

Init()
{
 memp=blks+1;					/* Initialisierung der verkette-	*/
 memp2=(struct meml *)-1L;			/* ten Listen für die Polyominos	*/
 memakt=(struct meml *)-1L;			/* und die Speicherverwaltung		*/

 poll=sizeof(struct pol);			/* Dabei wird das Ausgangs-		*/
 polnl=sizeof(struct poln);			/* polyomino (ein einziger Stein)	*/
 poli=1;					/* "per Hand" erzeugt			*/
 palt=(struct poln *)-1L;
 pneu=(struct poln *) malloc_own();
 pneu->cs=0x00000011;				
 pneu->image[0]=0x10;
 pneu->np=(struct poln *)-1L;

 tiefe=1;
}
 
Poli_1()
{
 register unsigned long i;			/* In dieser Routine wird die		*/
 struct poln *p1;				/* jeweils zuletzt erzeugte		*/
						/* Liste mit Polyominos abge-		*/
 polineu=poli+2;				/* arbeitet und die neue Liste		*/
						/* aufgebaut				*/
 palt=pneu;
 anzx=0;
 pneu=(struct poln *)-1L;
 poff=(struct poln *)-1L;

 memp1=memp2;

 memakt=(struct meml *)-1L;
 memp=blks+1;

 for(i=0;i<ent;i++)				/* Löschen der Hashtabelle		*/
    Entry[i]=0L;

 anzd=0;
 interv=0;

 while(palt != (struct poln *)-1L)		/* Abarbeiten der alten Liste		*/
 {						/* und Aufruf eines Unterpro-		*/
    Poli_2();					/* gramms, das aus jedem alten		*/
						/* Bild versucht mehrere neue		*/
    p1=palt;					/* zu erstellen				*/
    palt=palt->np;
 }

 free_own();					/* komplette Freigabe des 		*/
						/* Speichers der alten Struktur		*/
 printf("%10ld%10ld\n",poli+1,anzd);		/* Ausgabe eines Zwischenstandes	*/
}

Poli_2()
{
 register unsigned long i,j;
 register unsigned char *p1,*p2;

 j=256;

 p1=pold1->image;
 p2=pold2->image;

 for(i=0;i<j;i++)				/* Löschen der Bildspeicher		*/
 {						/* von pold1 und pold2			*/
    *p1++=0;
    *p2++=0;
 }

 Unpack(palt);					/* Entpacken des nächsten		*/
						/* Eintrags in der Liste		*/
 p1=pold1->image;
 p2=pold2->image;

 for(i=1;i<=pold1->y;i++)			/* Das entpackte Bild wird		*/
    for(j=1;j<=pold1->x;j++)			/* Zeile für Zeile, Zeichen für		*/
       if(*(p1+(i<<4)+j) != 0)			/* Zeichen abgearbeitet.		*/
       {					/* Bei einem nicht leeren Feld		*/
          Poli_5(p1,p2,i,j-1);			/* wird versucht, oben, unten,		*/
          Poli_5(p1,p2,i-1,j);			/* rechts und links ein Stein		*/
          Poli_5(p1,p2,i,j+1);			/* anzufügen				*/
          Poli_5(p1,p2,i+1,j);
       }
}

Poli_5(p1,p2,x,y)
register unsigned char *p1,*p2;
register unsigned long x,y;
{
 register unsigned long x1;

 x1=(x<<4)+y;

 if(*(p2+x1) == 1)				/* Wenn dort schon ein Stein war	*/
    return(0);					/* ->Rücksprung				*/

 *(p1+x1)=1;					/* Eintragen des Steins			*/
 *(p2+x1)=1;					/* Position als besetzt kenn-		*/
						/* zeichnen				*/
 ox=1;						/* Feststellen, ob sich die Höhe	*/
 oy=1;						/* oder die Breite geändert hat 	*/
 b=pold1->x;					/* oder ob in den oberen oder		*/
 h=pold1->y;					/* linken Rahmen geschrieben		*/
						/* wurde.				*/
 if(x == 0L)
 {
    ox--;
    h++;
 }

 if(x > h)
    h++;

 if(y == 0L)
 {
    oy--;
    b++;
 }

 if(y > b)
    b++;

 Poli_7(x,y);

 *(p1+x1)=0;					/* Herstellen der Originalbildes	*/
}

Poli_7(x,y)
unsigned long x,y;
{
 register unsigned char *p1,*p2;		/* Das neu entstandene Bild wird	*/
 register unsigned long i,j,l;			/* bündig nach oben links ausge-	*/
						/* richtet.				*/
 p1=pold1->image+(ox<<4)+oy;
 p2=pold3->image;

 pold3->x=b;
 pold3->y=h;

 for(i=0;i<h;i++)
 {
    for(j=0;j<b;j++)
       *p2++=*p1++;

    p1+=(16-b);
    p2+=(16-b);
 }

 if(h > b)					/* Wenn die Höhe des Bildes		*/
    Rot_90();					/* größer ist als die Breite		*/
						/* wird es um 90 Grad gedreht		*/
 Poli_9();
}

Rot_90()
{
 register unsigned char *p1,*p2,zeichen;	/* In diesem Unterprogramm		*/
 register unsigned long i,j,i1,i2,x;		/* findet die Drehung durch		*/
						/* Spiegelung an der Diagonalen		*/
 p1=pold3->image;				/* statt.				*/

 x=pold3->x;
 pold3->x=pold3->y;
 pold3->y=x;

 p1=pold3->image;
 p2=pold3->image;

 for(i=0;i<pold3->x;i++)
 {
    i1=i<<4;
    i2=i;

    for(j=0;j<i;j++)
    {
       zeichen=*(p1+i1);
       *(p1+i1)=*(p2+i2);
       *(p2+i2)=zeichen;
       i1++;
       i2+=16;
    }
 }
}

Poli_9()
{
 register struct poln *p1,*p2;
 register unsigned long i,k,offset;

 p1=pneu;
 p2=(struct poln *)-1L;

 Normalize();					/* Beschreibung siehe Routine		*/

 Copy_Pol(pold3,pold4);				/* Es wird das höchstwertige Bild	*/
						/* übernommen				*/
 Checksum();					/* Ermitteln des Hashindexes		*/
 
 Pack(pold3);					/* Packen zum Vergleich			*/

 adr=poldn->cs>>8;				/* Hashadresse ermitteln		*/

 for(i=adr;i>0;i--)
 {
    if(Entry[i] != 0L)				/* Ersten Eintrag <= dem gesuchten	*/
    {						/* ermitteln				*/
       p1=Entry[i];
       break;
    }
 }

 k=0;

 while((p1 != (struct poln *)-1L) && (k == 0))	/* Durchsuchen der schon vorhan-	*/
 {						/* denen Bilder				*/
    if((p1->cs>>8) > adr)
       break;

    if(p1->cs == poldn->cs)
       if(strncmp(p1->image,poldn->image,8) == 0)
          k=1;
       else
          k=0;

    p2=p1;

    p1=p1->np;
 }

 if(k == 1)					/* schon vorhanden -> Rücksprung	*/
    return(0);

 Poli_10(p1,p2);				/* Aufnehmen des Bildes			*/
}

Poli_10(lp,lp2)
struct poln *lp,*lp2;
{
 register struct poln *p1;			/* Einstellen in die Kette		*/
 register unsigned char *p2,*p3;
 register unsigned long i,j;

 p1=poff;

 poff=(struct poln *)malloc_own();
 poff->cs=poldn->cs;
 strncpy(poff->image,poldn->image,8);
 poff->np=lp;

 if((lp == (struct poln *)-1L) && (lp2 == (struct poln *)-1L))
    pneu=poff;
 else
    if(lp2 == (struct poln *)-1L)
    {
       pneu=poff;
       poff->np=lp;
    }
    else
       lp2->np=poff;

 if(Entry[adr] == 0L)				/* Eintrag in die Hashtabelle		*/
    Entry[adr] = poff;

 anzd++;
 interv++;

 if(interv == 100)				/* Alle 100 neuen Bilder Anzeige	*/
 {						/* auf dem Bildschrim			*/
    printf("%10ld%10ld\r",poli+1,anzd);
    interv=0;
 }
}

Mirror_H()					/* Die Routine spiegelt ein		*/
{						/* Bild horizontal			*/
 struct pol *p1;
 register unsigned char *p3,*p4,zeichen,*p2;
 register unsigned long i,j,k,l;

 l=pold3->x/2;

 p1=pold3;
 p2=p1->image;

 for(i=0;i<pold3->y;i++)
 {
    k=pold3->x-1;
    p3=p2+pold3->x;
    p4=p2;

    for(j=0;j<l;j++)
    {
       zeichen=*p4;
       *(p4++)=*(--p3);
       *p3=zeichen;
    }
    p2+=16;
 }
}

Mirror_V()					/* Die Routine spiegelt ein		*/
{						/* Bild vertikal			*/
 struct pol *p1;
 register unsigned char *p3,*p4,zeichen,*p2;
 register unsigned long i,j,k,l;

 p1=pold3;
 p2=p1->image;

 k=0;
 l=(pold3->y-1)<<4;

 for(i=0;i<pold3->y/2;i++)
 {
    p3=p2+k;
    p4=p2+l;

    for(j=0;j<pold3->x;j++)
    {
       zeichen=*p3;
       *(p3++)=*p4;
       *(p4++)=zeichen;
    }
    k+=16;
    l-=16;
 }
}

Copy_Pol(p1,p2)					/* Die Routine kopiert eine 		*/
struct pol *p1,*p2;				/* komplette Struktur			*/
{
 register unsigned char *p3,*p4;
 register unsigned long i,j,k;

 p3=p1->image;
 p4=p2->image;
 k=pold3->x;

 for(i=0;i<pold3->y;i++)
 {
    for(j=0;j<k;j++)
       *p3++=*p4++;

    p3+=16-k;
    p4+=16-k;
 }
}

Cmp_Pol(p1,p2)					/* Die Routine vergleicht		*/
struct pol *p1,*p2;				/* zwei Bilder				*/
{
 register unsigned char *p3,*p4;
 register unsigned long i,j,k;

 p3=p1->image;
 p4=p2->image;

 for(i=0;i<pold3->y;i++)
    for(j=0;j<pold3->x;j++)
    {
       k=*(p3+(i<<4)+j);
       k=k-*(p4+(i<<4)+j);

       if(k != 0)
         return(k);
    }
 return(0);
}

Normalize()					/* In dieser Routine wird das		*/
{						/* Bild auf alle möglichen		*/
 Copy_Pol(pold4,pold3);				/* Darstellungen gedreht und 		*/
						/* gespiegelt.				*/
 Mirror_H();					/* Dabei wird das Bild mit der		*/
						/* höchsten Wertigkeit, d. h. 		*/
 if(Cmp_Pol(pold3,pold4) > 0)			/* mit dem frühesten Auftreten		*/
    Copy_Pol(pold4,pold3);			/* ausgefüllter Felder (von		*/
						/* rechts nach links und von 		*/
 Mirror_V();					/* oben nach unten) in pold4		*/
 if(Cmp_Pol(pold3,pold4) > 0)			/* abgelegt.				*/
    Copy_Pol(pold4,pold3);

 Mirror_H();

 if(Cmp_Pol(pold3,pold4) > 0)
    Copy_Pol(pold4,pold3);

 if(pold3->x != pold3->y)
    return(0);

 Rot_90();

 if(Cmp_Pol(pold3,pold4) > 0)
    Copy_Pol(pold4,pold3);

 Mirror_H();

 if(Cmp_Pol(pold3,pold4) > 0)
    Copy_Pol(pold4,pold3);

 Mirror_V();

 if(Cmp_Pol(pold3,pold4) > 0)
    Copy_Pol(pold4,pold3);

 Mirror_H();

 if(Cmp_Pol(pold3,pold4) > 0)
    Copy_Pol(pold4,pold3);

 return(0);
}

Checksum()					/* Ermitteln der Checksumme		*/
{
 register unsigned char *p1;
 register unsigned long i,j,k,l;

 k=0;
 l=0;

 p1=pold3->image;

 for(i=0;i<pold3->y;i++)
    for(j=0;j<pold3->x;j++)
       k+=(*(p1+(i<<4)+j)*i<<10+j);

}

Unpack(p)					/* Entpacken eines Bildes		*/
struct poln *p;
{
 register unsigned char *p1,*p2,*p3;
 register unsigned long i,j,k,ln,la,x,y;

 i=p->cs&0xff;
 x=i/16;
 y=i&0xf;
 j=0;

 pold1->x=x;
 pold1->y=y;

 p1=pold1->image;
 p2=pold2->image;

 imagex=(unsigned char *) &p->image[0];
 p3=&imageh[0];

 for(i=0;i<8;i++)
 {
    j=imagex[i];

    *p3++=(j>>4)&0xf;
    *p3++=j&0xf;
 }

 x=0;
 y=0;
 la=99;

 for(k=0;k<poli;k++)
 {
    ln=imageh[k];

    if(ln <=la)
       y++;

    x=ln;
    la=ln;

    *(p1+(y<<4)+x)=1;
    *(p2+(y<<4)+x)=1;
 }
}

Pack(p)						/* Packen eines Bildes			*/
struct pol *p;
{
 register unsigned long i,j,k,l,m;
 register unsigned char *p1,*p2;

 p1=p->image;
 p2=&imageh[0];


 for(i=0;i<16;i++)
    *p2++=0;

 p2=&imageh[0];

 k=0;

 for(i=0;i<p->y;i++)
 {
    l=0;

    for(j=0;j<p->x;j++)
    {
       m=*(p1+(i<<4)+j);

       if(m != 0)
       {
          *p2++=j+1;
          l+=(1<<j);
       }
    }

    k=k^l;
    k*=9;
 }

 p2=&imageh[0];
 imagex=(unsigned char *) &poldn->image[0];

 for(i=0;i<8;i++)
 {
    j=*p2++<<4;
    j+=*p2++;
    imagex[i]=j;
 }

 poldn->cs=pold3->x*16+pold3->y;
 poldn->cs+=((k&0x1fff)<<8);

}

PicOut(p,n)					/* Ausgabe der Polyominos		*/
register struct poln *p;
register unsigned long n;
{
 unsigned char *p1,*p2,*p3;
 unsigned long i,j,k,ln,la,x,y,h,b;

 anz++;

 i=p->cs&0xff;
 x=i/16;
 y=i&0xf;
 j=0;

 b=x;
 h=y;

 if(pico + b > dis)
    Out_Line();

 if(h > pich)
    pich=h;

 x=0;
 y=0;
 la=0;

 imagex=(unsigned char *) &p->image[0];
 p3=&imageh[0];

 for(i=0;i<8;i++)
 {
    j=imagex[i];

    *p3++=(j>>4)&0xf;
    *p3++=j&0xf;
 }

 x=0;
 y=0;
 la=0;
 k=0;

 while(ln=imageh[k])
 {
    k++;

    if(ln <=la)
       y++;

    x=ln;
    la=ln;

    x--;

    *(bild+pico+y*picz+x)='#';
 }

 pico+=b+1;
}

Out_Line()
{
 register unsigned long i,j;

 for(i=0;i<pich;i++)
 {
    *(bild+i*picz+pico)=0;
    printf("%s\n",bild+i*picz);
 }

 printf("-----\n");

 pich=0;
 picb=0;
 pico=0;

 ClearImage();
}

ClearImage()
{
 register unsigned char *p1;
 register unsigned long i,j;

 p1=bild;

 for(i=0;i<picz*16;i++)
    *p1++=' ';
}

struct meml *malloc_own()			/* eigene Speicherverwaltung		*/
{						/* dadurch muß nur alle 100		*/
 register struct meml *p1;			/* Bilder ein malloc durchge-		*/
						/* führt werden.			*/
 memp++;

 if(memp >= blks)
 {
    memp=0;
    p1=memakt;
    
    memakt=(struct meml *)malloc(sizeof (struct meml));
    

    if(p1 == (struct meml *)-1L)
       memp2=memakt;
    else
       p1->nm=memakt;

    memakt->nm=(struct mel *)-1L;
 }

 return((struct meml *)&memakt->sp[memp]);
}   

free_own()					/* Freigabe der Speicherliste		*/
{
 register struct meml *p1,*p2;

 p1=memp1;

 while(p1 != (struct meml *)-1L)
 {
    p2=p1;
    p1=p1->nm;

    free(p2,sizeof(struct meml));
 }
}