/*
   This converts a P4-type PBM data-stream to GIF.
   
   rd@redleaf.bbs.no  (c) 2.3.96
*/


#include <stdio.h>

/* lzw compression constants */

#define bits 2                 /* 2  bits for each pixel. black/white=2 */
#define firstsize bits+1       /* 3  size of first code */
#define clearcode 1<<bits      /* 4  value of code for clearing tables */
#define endcode (clearcode)+1  /* 5  value of code for ending bitstream */
#define mincode (endcode)+1    /* 6  min code value to use for compress */
#define maxcode (clearcode)<<1 /* 8  I'm not using this, whatever it's for */

/* compression vars */

int child[4096], sib[4096], shade[4096];
unsigned char buff[255];
int nextcode, codesize=firstsize, color, parent, son, bro, buffpos;

/* gif format vars */

int xres, yres;

main(int argc, char *argv[]) 
{
  readpbmhead();   /* get resolution and filetype. abort if wrong filetype */
  writegifhead();  /* write gif head */
  lzwcompstream(); /* read, lzw-compress, then write bitstream */
  writegiftail();  /* write gif trailer */
  return 0;
}


readpbmhead() /* get resolution and filetype. abort if wrong filetype */
{
  int i;
  char sig[2];
  scanf("%2s %d %d ", sig, &xres, &yres);
  if (!(sig[0]=='P' && sig[1]=='4'))
    {
      fprintf(stderr,"Sorry, can only handle P4-type PBM data.\n"); 
      exit(-1);
    }
}


int writegifhead() /* write gif head */
{
  /* header */

  printf("GIF87a");

  /* logical screen descriptor */

  putchar(xres);putchar(xres>>8); /* xres */
  putchar(yres);putchar(yres>>8); /* yres */
  putchar(0xf0);                  /* misc */
  putchar(0x01);                  /* background color index */
  putchar(0x00);                  /* pixel aspect ratio not given */

  /* global color-table */

  putchar(0xff);putchar(0xff);putchar(0xff); /* white */
  putchar(0x00);putchar(0x00);putchar(0x00); /* black */

  /* image descriptor */

  putchar(0x2c);                  /* signature */
  putchar(0x00);putchar(0x00);    /* left position */
  putchar(0x00);putchar(0x00);    /* top position */
  putchar(xres);putchar(xres>>8); /* xres */
  putchar(yres);putchar(yres>>8); /* yres */
  putchar(0x00);                  /* misc */
}


int writegiftail() /* write gif trailer */
{
  putchar (0x3b); /* end stream code */
}


int lzwcompstream() /* read, lzw-compress, then write bitstream */

{
  putchar(bits);
  clearall();

  color=getcolor();
  parent=color;
  while((color=getcolor())!=EOF)
    {
      son=child[parent];
      if (son>0)
	{
	  if (shade[son]==color) parent=son;
	  else 
	    {
	      bro=son;
	      do
		{
		  if (sib[bro]>0)
		    {
		      bro=sib[bro];
		      if (shade[bro]==color)
			{
			  parent=bro;
			  break;
			}}
		  else
		    {
		      sib[bro]=nextcode;
		      shade[nextcode]=color;
		      buffercode(parent);
		      parent=color;
		      nextcode++;
		      codesize=calccs(nextcode);
		      break;
		    }
		}
	      while (1);
	    }}
      else 
	{
	  child[parent]=nextcode;
	  shade[nextcode]=color;
	  buffercode(parent);
	  parent=color;
	  nextcode++;
	  codesize=calccs(nextcode);
	}
      if (nextcode==4096) clearall();
    }    
  buffercode(endcode);
  codesize=7; buffercode(0); /* flush last bits, if any, from wrkint to buff*/
  if (buffpos) writebuff();  /* write final part of buffer */
  putchar(0);                /* write block terminator */
} 


int clearall() /* write clearcode and clear all vars/compression tables */
{
  int i;
  buffercode(clearcode);
  for (i=0; i<4096; i++) child[i]=sib[i]=shade[i]=0;
  nextcode=mincode; codesize=firstsize;
  color=parent=son=bro=0;
}


int calccs(int code) /* return size of code */
{
  int len=1;
  code--;
  while (code>>=1) len++;
  return len;
}


int getcolor() /* get value of next color (0 or 1) */
{
  static int wrkint;
  static unsigned char wrkpos;
  int tmp;
  if (!wrkpos) 
    {
      if ((wrkint=getchar())==EOF) return EOF;
      else wrkpos=128;
    }
  if ((wrkint & wrkpos)>=1) tmp=1; else tmp=0;
  wrkpos>>=1;
  return tmp;
}      


int buffercode(int code) /* buffer bit-pattern of codesize length */
{
  static int wrkint, wrkpos;
  wrkint|=(code<<wrkpos);
  wrkpos+=codesize;
  while (wrkpos>7)
    {
      buff[buffpos]=wrkint;
      buffpos++;
      wrkpos-=8;
      wrkint>>=8;
      if (buffpos==255) writebuff();
    }
}


int writebuff() /* write buffer with counter to compressed stream */
{
  int i;
  putchar(buffpos);
  for (i=0; i<buffpos; i++) putchar(buff[i]);
  buffpos=0;
}