#define VERSIONNUMBER "1.0"

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define PUTDEFENITION \
	"\\newcommand{\\PP}[3]"\
	"{\\put(#1){\\rule{#2\\unitlength}{#3\\unitlength}}}\n"

#define RESTBIT(x) (RestImage[(x)/8] & (UnsCharEins<<(7-(x)%8)))
#define OLDBIT(x) (OldImage[(x)/8] & (UnsCharEins << (7-(x)%8)))

#define SETRESTBIT(x) RestImage[(x)/8] |= (UnsCharEins << (7-(x)%8))
#define DELETERESTBIT(x) RestImage[(x)/8] &= ~(UnsCharEins << (7-(x)%8))
#define SETOLDBIT(x)  OldImage[(x)/8] |= (UnsCharEins << (7-(x)%8))

/************************************************************************/
/*									*/
/*			NO WARRANTY!!					*/
/*									*/
/*	There is absolutely no warranty on this program! Feel free to	*/
/*	use, modify and redistribute this program in any way, but	*/
/*	anything you do with it, you do on your very own risk!		*/
/*									*/
/*	If you find bugs in this program please let me know. If you	*/
/*	modify it in some useful way I would be glad to receive a copy	*/
/*	of the modified source. (My e-mail address see below.)		*/
/*									*/
/************************************************************************/
/* 									*/
/*	program:	pbm2TeX						*/
/* 									*/
/*	author:		Andreas Barth					*/
/*			Universitaet Ulm	(Germany)		*/
/*			Abteilung Mathematische Physik			*/
/*			bar@physik.uni-ulm.de				*/
/* 									*/
/*	date:		some sunday in 1990 version 0.1			*/
/*	date:		november 1993 (version 0.2)			*/
/*	date:		january 1994 (version 1.0)			*/
/* 									*/
/************************************************************************/
/*									*/
/*	This is pbm2TeX, an image converter from the pbm (portable	*/
/*	bitmap) format to a LaTeX picture environment.			*/
/*									*/
/************************************************************************/
/*									*/
/* 	There are no special system requirements. Just compile this	*/
/*	program	with your favourite C-copiler. 				*/
/*									*/
/************************************************************************/
/*									*/
/*	This program is intended to make the import of graphic easy	*/
/*	and as portable as possible. There are many DVI drivers who	*/
/*	allow to import different graphic formats but you at least	*/
/*	have to pay the price of restricted portability. 		*/
/*									*/
/*	To get fully portable graphics inclusion into my LaTeX docu-	*/
/*	ments I some years ago wrote a program that converted pixel	*/
/*	images to LaTeX picture environments. This program worked fine,	*/
/*	but the time TeX needed to compile the documents grow rapidly	*/
/*	(I had a document with 19 x-y-plots in about 30 pages that	*/
/*	needed about one hour to compile!) and so I gave it up. But	*/
/*	the computer power increased considerably and the TeX imple-	*/
/*	mentations I use are perhaps a hundred times faster than those	*/
/*	I used at the first try. So I decided to rewrite the program	*/
/*	and try again to use it. I hope in future I can reduce the	*/
/*	number of rules used to build the pcture. This version (0.1)	*/
/*	works not very optimized. (I am thinking about a smarter algo-	*/
/*	rithm!)								*/
/*									*/
/*	(The transform algorithm was modified in version 1.0.)		*/
/*									*/
/************************************************************************/
/*									*/
/*	useage:	pbm2TeX works as a pipeline. Just pipe the pbm image	*/
/*		into the program and redirect the LaTeX output into a	*/
/*		file you may include into your document:		*/
/*									*/
/*			pbm2TeX <myimage.pbm >myimage.tex		*/
/*									*/
/*		There is a single command line option at this  time.	*/
/*		This is the -L option. It is needed because in some	*/
/*		environments a newline may be two bytes long and so	*/
/*		in case of a binary image (magic number 4) there may	*/
/*		be two bytes between the end of the image width number	*/
/*		and the start of the image. This aditional byte is	*/
/*		skipped when using the -L option.			*/
/*									*/
/*	limitation: At this time (version 1.0) comments in the image	*/
/*		file are not supported (I never saw a pbm image that	*/
/*		contained any).						*/
/*									*/
/************************************************************************/

unsigned char UnsCharEins=1, DummyC;
int ImageWidth=0, ImageHeight=0;
int LinefeedFlag=0;
unsigned char * OldImage;
unsigned char * RestImage;

void readimage(void)
{
int MagicNumber;
register int i;

scanf("P%d%d%d",&MagicNumber, &ImageWidth, &ImageHeight);

OldImage = (unsigned char *) malloc( (ImageWidth*ImageHeight+7)/8);
RestImage = (unsigned char *) malloc( (ImageWidth*ImageHeight+7)/8);

if( NULL == OldImage || NULL == RestImage)
	{
	fprintf(stderr,"\ncan't allocate enough memory! => exit");
	exit(1);
	}

for(i=0; i<(ImageWidth*ImageHeight+7)/8; i++) 
	{
	OldImage[i]=0;
	}

if(1 == MagicNumber)
	{
	for(i=0; i<(ImageWidth*ImageHeight); i++)
		{
		int v;
		scanf("%d", &v);
		if(v != 0) SETOLDBIT(i);
		}
	memcpy(RestImage,OldImage,(ImageWidth*ImageHeight+7)/8);
	}
else if(4 == MagicNumber)
	{
	if(LinefeedFlag)
		{
		char c;
		fread(&c,1,1,stdin);
		}
	fread(OldImage,(ImageWidth*ImageHeight+7)/8,1,stdin);
	memcpy(RestImage,OldImage,(ImageWidth*ImageHeight+7)/8);
	}
else
	{
	fprintf(stderr,"\nbad magic number: %d (1 or 4 expected) => exit");
	exit(1);
	}
}


int LowerBorder(int x1, int x2, int y)
{
int lower=y+1;
int x;
unsigned char there=255;

while(there && lower < ImageHeight)
	{
	for(x=x1; x<x2; x++)
		{
		there = there && OLDBIT(lower*ImageWidth+x);
		}
	if(there) lower++;
	}
return(lower);
}


void NoteSquare(int Xmin, int Xmax, int Ymin, int Ymax)
{
register int x,y;
for(y=Ymin; y<Ymax; y++)
	{
	for(x=Xmin; x<Xmax; x++)
		{
		DELETERESTBIT(x+ImageWidth*y);
		}
	}
printf("\\PP{%d,%d}{%d}{%d}\n",
	Xmin,
	ImageHeight-Ymin-(Ymax-Ymin),
	Xmax-Xmin,
	Ymax-Ymin);
}


int InsideSquare(int Xmin, int Xmax, int Ymin, int Ymax)
{
register int M=0;
register int x,y;
for(y=Ymin; y<Ymax; y++)
	{
	for(x=Xmin; x<Xmax; x++)
		{
		if(RESTBIT(y*ImageWidth+x)) M++;
		}
	}
return(M);
}


int main(int argc, char * args[])
{
register int l,i;

for(i=1; i<argc; i++)
	{
	if('-' == args[i][0] && 'L' == args[i][1])
		LinefeedFlag=1;
	}

fprintf(stderr,"\nthis is pbm2TeX %s",VERSIONNUMBER);
readimage();
fprintf(stderr,"\nimage of size %d X %d read",
	ImageWidth,ImageHeight);

printf("%%%%This is an output from pbm2TeX ver. %s!\n",VERSIONNUMBER);
printf("%%%%To resize the image change the definition\n");
printf("%%%%of \\unitlength\n");
printf("{\n");
printf(PUTDEFENITION);
printf("\\setlength{\\unitlength}{0.0846666mm}\n");
printf("\\begin{picture}(%d,%d)\n",ImageWidth,ImageHeight);

for(l=0; l<ImageHeight; l++)
	{
	int s;
	fprintf(stderr,".");
	for(s=0; s<ImageWidth; s++)
		{
		if(RESTBIT(l*ImageWidth+s))
			{
			int XA,XE,Xa,Xe,Xmin,Xmax,Y,YN,NT,N=0;

			Xmin= s;
			while( Xmin>0 &&
				OLDBIT(l*ImageWidth+Xmin-1) )
				Xmin--;
			Xmax = s+1;
			while(Xmax<ImageWidth &&
				OLDBIT(l*ImageWidth+Xmax)) Xmax++;

			for(Xa=Xmin; Xa<=s; Xa++)
				{
				for(Xe=s+1; Xe<=Xmax; Xe++)
					{
					Y=LowerBorder(Xa,Xe,l);
					NT=InsideSquare(Xa,Xe,l,Y);
					if(NT >= N)
						{
						YN=Y;
						XA=Xa;
						XE=Xe;
						N=NT;
						}
					}
				}

			NoteSquare(XA,XE,l,YN);
			}
		}
	}
printf("\\end{picture}\n");
printf("}\n");
printf("%%%%end output from pbm2TeX ver. %s\n",VERSIONNUMBER);
exit(0);
}