text: /*  png.c
     
     Copyright (c) 2003/2004/2005 Matthias Kramm <kramm@quiss.org>
  
     This program is free software; you can redistribute it and/or modify
     it under the terms of the GNU General Public License as published by
     the Free Software Foundation; either version 2 of the License, or
     (at your option) any later version.
  
     This program is distributed in the hope that it will be useful,
     but WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     GNU General Public License for more details.
  
     You should have received a copy of the GNU General Public License
     along with this program; if not, write to the Free Software
     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  
  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  #include <assert.h>
  #include <math.h>
  #include <fcntl.h>
  #include <zlib.h>
  #include <limits.h>
  
  #ifdef EXPORT
  #undef EXPORT
  #endif
  
  #ifdef PNG_INLINE_EXPORTS
  #define EXPORT static
  #else
  #define EXPORT
  #include "png.h"
  #endif
  
  typedef unsigned u32;
  
  typedef struct _COL {
      unsigned char a,r,g,b;
  } COL;
  
  static int png_read_chunk(char (*head)[4], int*destlen, unsigned char**destdata, FILE*fi)
  {
      unsigned int len;
      unsigned char blen[4];
      if(destlen) *destlen=0;
      if(destdata) *destdata=0;
      if(!fread(&blen, 4, 1, fi)) {
  	return 0;
      }
      if(!fread(head, 4, 1, fi)) {
  	return 0;
      }
      len = blen[0]<<24|blen[1]<<16|blen[2]<<8|blen[3];
      if(destlen) *destlen = len;
      if(destdata) {
  	if(!len) {
  	    *destdata = 0;
  	} else {
  	    *destdata = (unsigned char*)malloc(len);
  	    if(!fread(*destdata, len, 1, fi)) {
  		*destdata = 0;
  		if(destlen) *destlen=0;
  		return 0;
  	    }
  	}
  	fseek(fi, 4, SEEK_CUR);
  
      } else {
  	fseek(fi, len+4, SEEK_CUR);
      }
      return 1;
  }
  
  static unsigned int png_get_dword(FILE*fi)
  {
      unsigned int a;
      unsigned char b[4];
      fread(&b,4,1,fi);
      return b[0]<<24|b[1]<<16|b[2]<<8|b[3];
  }
  
  struct png_header
  {
      unsigned width;
      unsigned height;
      int bpp;
      int mode;
  };
  
  static int png_read_header(FILE*fi, struct png_header*header)
  {
      char id[4];
      int len;
      int ok=0;
      unsigned char head[8] = {137,80,78,71,13,10,26,10};
      unsigned char head2[8];
      unsigned char*data;
      fread(head2,8,1,fi);
      if(strncmp((const char*)head,(const char*)head2,4))
  	return 0; // not a png file
      
      while(png_read_chunk(&id, &len, &data, fi))
      {
  	//printf("Chunk: %c%c%c%c (len:%d)\n", id[0],id[1],id[2],id[3], len);
  	if(!strncmp(id, "IHDR", 4)) {
  	    char a,b,c,f,i;
  	    if(len < 8) exit(1);
  	    header->width = data[0]<<24|data[1]<<16|data[2]<<8|data[3];
  	    header->height = data[4]<<24|data[5]<<16|data[6]<<8|data[7];
  	    a = data[8];      // should be 8
  	    b = data[9];      // should be 3(indexed) or 2(rgb)
  
  	    c = data[10];     // compression mode (0)
  	    f = data[11];     // filter mode (0)
  	    i = data[12];     // interlace mode (0)
  
  	    if(b!=0 && b!=4 && b!=2 && b!=3 && b!=6) {
  		fprintf(stderr, "Image mode %d not supported!\n", b);
  		return 0;
  	    }
  	    if(a!=8 && (b==2 || b==6)) {
  		printf("Bpp %d in mode %d not supported!\n", b, a);
  		return 0;
  	    }
  	    if(c!=0) {
  		printf("Compression mode %d not supported!\n", c);
  		return 0;
  	    }
  	    if(f!=0) {
  		printf("Filter mode %d not supported!\n", f);
  		return 0;
  	    }
  	    if(i!=0) {
  		printf("Interlace mode %d not supported!\n", i);
  		return 0;
  	    }
  	    //printf("%dx%d bpp:%d mode:%d comp:%d filter:%d interlace:%d\n",header->width, header->height, a,b,c,f,i);
  	    header->bpp = a;
  	    header->mode = b;
  	    ok = 1;
  	} 
  	
  	free(data);
      }
      return ok;
  }
  
  typedef unsigned char byte;
  #define ABS(a) ((a)>0?(a):(-(a)))
  static inline byte PaethPredictor (byte a,byte b,byte c)
  {
          // a = left, b = above, c = upper left
          int p = a + b - c;        // initial estimate
          int pa = ABS(p - a);      // distances to a, b, c
          int pb = ABS(p - b);
          int pc = ABS(p - c);
          // return nearest of a,b,c,
          // breaking ties in order a,b,c.
          if (pa <= pb && pa <= pc) 
  		return a;
          else if (pb <= pc) 
  		return b;
          else return c;
  }
  
  static void applyfilter1(int mode, unsigned char*src, unsigned char*old, unsigned char*dest, unsigned width)
  {
      int x;
      unsigned char last=0;
      unsigned char upperlast=0;
  
      if(mode==0) {
  	for(x=0;x<width;x++) {
  	    *dest = *src;
  	    dest++;
  	    src++;
  	}
      }
      else if(mode==1) {
  	for(x=0;x<width;x++) {
  	    *dest = *src+last;
  	    last = *dest;
  	    dest++;
  	    src++;
  	}
      }
      else if(mode==2) {
  	for(x=0;x<width;x++) {
  	    *dest = *src+*old;
  	    dest++;
  	    old++;
  	    src++;
  	}
      }
      else if(mode==3) {
  	for(x=0;x<width;x++) {
  	    *dest = *src+(*old+last)/2;
  	    last = *dest;
  	    dest++;
  	    old++;
  	    src++;
  	}
      }
      else if(mode==4) {
  	for(x=0;x<width;x++) {
  	    *dest = *src+PaethPredictor(last,*old,upperlast);
  	    last = *dest;
  	    upperlast = *old;
  	    dest++;
  	    old++;
  	    src++;
  	}
      }    
  
  }
  
  static void applyfilter2(int mode, unsigned char*src, unsigned char*old, unsigned char*dest, unsigned width)
  {
      int x;
      unsigned char lasta=0;
      unsigned char lastb=0;
      unsigned char upperlasta=0;
      unsigned char upperlastb=0;
  
      if(mode==0) {
  	for(x=0;x<width;x++) {
  	    dest[0] = src[0];
  	    dest[1] = src[1];
  	    dest+=2;
  	    src+=2;
  	}
      }
      else if(mode==1) {
  	for(x=0;x<width;x++) {
  	    dest[0] = src[0]+lasta;
  	    dest[1] = src[1]+lastb;
  	    lasta = dest[0];
  	    lastb = dest[1];
  	    dest+=2;
  	    src+=2;
  	}
      }
      else if(mode==2) {
  	for(x=0;x<width;x++) {
  	    dest[0] = src[0]+old[0];
  	    dest[1] = src[1]+old[1];
  	    dest+=2;
  	    old+=2;
  	    src+=2;
  	}
      }
      else if(mode==3) {
  	for(x=0;x<width;x++) {
  	    dest[0] = src[0]+(old[0]+lasta)/2;
  	    dest[1] = src[1]+(old[1]+lastb)/2;
  	    lasta = dest[0];
  	    lastb = dest[1];
  	    dest+=2;
  	    old+=2;
  	    src+=2;
  	}
      }
      else if(mode==4) {
  	for(x=0;x<width;x++) {
  	    dest[0] = src[0]+PaethPredictor(lasta,old[0],upperlasta);
  	    dest[1] = src[1]+PaethPredictor(lastb,old[1],upperlastb);
  	    lasta = dest[0];
  	    lastb = dest[1];
  	    upperlasta = old[0];
  	    upperlastb = old[1];
  	    dest+=2;
  	    old+=2;
  	    src+=2;
  	}
      }    
  }
  
  
  /* also performs 24 bit conversion! */
  static void applyfilter3(int mode, unsigned char*src, unsigned char*old, unsigned char*dest, unsigned width)
  {
      int x;
      unsigned char lastr=0;
      unsigned char lastg=0;
      unsigned char lastb=0;
      unsigned char upperlastr=0;
      unsigned char upperlastg=0;
      unsigned char upperlastb=0;
  
      if(mode==0) {
  	for(x=0;x<width;x++) {
  	    dest[0] = 255;
  	    dest[1] = src[0];
  	    dest[2] = src[1];
  	    dest[3] = src[2];
  	    dest+=4;
  	    src+=3;
  	}
      }
      else if(mode==1) {
  	for(x=0;x<width;x++) {
  	    dest[0] = 255;
  	    dest[1] = src[0]+lastr;
  	    dest[2] = src[1]+lastg;
  	    dest[3] = src[2]+lastb;
  	    lastr = dest[1];
  	    lastg = dest[2];
  	    lastb = dest[3];
  	    dest+=4;
  	    src+=3;
  	}
      }
      else if(mode==2) {
  	for(x=0;x<width;x++) {
  	    dest[0] = 255;
  	    dest[1] = src[0]+old[1];
  	    dest[2] = src[1]+old[2];
  	    dest[3] = src[2]+old[3];
  	    dest+=4;
  	    old+=4;
  	    src+=3;
  	}
      }
      else if(mode==3) {
  	for(x=0;x<width;x++) {
  	    dest[0] = 255;
  	    dest[1] = src[0]+(old[1]+lastr)/2;
  	    dest[2] = src[1]+(old[2]+lastg)/2;
  	    dest[3] = src[2]+(old[3]+lastb)/2;
  	    lastr = dest[1];
  	    lastg = dest[2];
  	    lastb = dest[3];
  	    dest+=4;
  	    old+=4;
  	    src+=3;
  	}
      }
      else if(mode==4) {
  	for(x=0;x<width;x++) {
  	    dest[0] = 255;
  	    dest[1] = src[0]+PaethPredictor(lastr,old[1],upperlastr);
  	    dest[2] = src[1]+PaethPredictor(lastg,old[2],upperlastg);
  	    dest[3] = src[2]+PaethPredictor(lastb,old[3],upperlastb);
  	    lastr = dest[1];
  	    lastg = dest[2];
  	    lastb = dest[3];
  	    upperlastr = old[1];
  	    upperlastg = old[2];
  	    upperlastb = old[3];
  	    dest+=4;
  	    old+=4;
  	    src+=3;
  	}
      }    
  }
  
  void png_inverse_filter_32(int mode, unsigned char*src, unsigned char*old, unsigned char*dest, unsigned width)
  {
      int x;
      unsigned char lastr=0;
      unsigned char lastg=0;
      unsigned char lastb=0;
      unsigned char lasta=0;
      unsigned char upperlastr=0;
      unsigned char upperlastg=0;
      unsigned char upperlastb=0;
      unsigned char upperlasta=0;
  
      if(mode==0) {
  	for(x=0;x<width;x++) {
  	    dest[0] = src[3];
  	    dest[1] = src[0];
  	    dest[2] = src[1];
  	    dest[3] = src[2];
  	    dest+=4;
  	    src+=4;
  	}
      }
      else if(mode==1) {
  	for(x=0;x<width;x++) {
  	    dest[0] = src[3]+lasta;
  	    dest[1] = src[0]+lastr;
  	    dest[2] = src[1]+lastg;
  	    dest[3] = src[2]+lastb;
  	    lasta = dest[0];
  	    lastr = dest[1];
  	    lastg = dest[2];
  	    lastb = dest[3];
  	    dest+=4;
  	    src+=4;
  	}
      }
      else if(mode==2) {
  	for(x=0;x<width;x++) {
  	    dest[0] = src[3]+old[0];
  	    dest[1] = src[0]+old[1];
  	    dest[2] = src[1]+old[2];
  	    dest[3] = src[2]+old[3];
  	    dest+=4;
  	    old+=4;
  	    src+=4;
  	}
      }
      else if(mode==3) {
  	for(x=0;x<width;x++) {
  	    dest[0] = src[3]+(old[0]+lasta)/2;
  	    dest[1] = src[0]+(old[1]+lastr)/2;
  	    dest[2] = src[1]+(old[2]+lastg)/2;
  	    dest[3] = src[2]+(old[3]+lastb)/2;
  	    lasta = dest[0];
  	    lastr = dest[1];
  	    lastg = dest[2];
  	    lastb = dest[3];
  	    dest+=4;
  	    old+=4;
  	    src+=4;
  	}
      }
      else if(mode==4) {
  	for(x=0;x<width;x++) {
  	    dest[0] = src[3]+PaethPredictor(lasta,old[0],upperlasta);
  	    dest[1] = src[0]+PaethPredictor(lastr,old[1],upperlastr);
  	    dest[2] = src[1]+PaethPredictor(lastg,old[2],upperlastg);
  	    dest[3] = src[2]+PaethPredictor(lastb,old[3],upperlastb);
  	    lasta = dest[0];
  	    lastr = dest[1];
  	    lastg = dest[2];
  	    lastb = dest[3];
  	    upperlasta = old[0];
  	    upperlastr = old[1];
  	    upperlastg = old[2];
  	    upperlastb = old[3];
  	    dest+=4;
  	    old+=4;
  	    src+=4;
  	}
      }    
  }
  
  EXPORT int png_getdimensions(const char*sname, unsigned*destwidth, unsigned*destheight)
  {
      FILE*fi;
      struct png_header header;
      if ((fi = fopen(sname, "rb")) == NULL) {
  	fprintf(stderr, "Couldn't open %s\n", sname);
  	return 0;
      }
      if(!png_read_header(fi, &header)) {
  	return 0;
      }
  
      *destwidth = header.width;
      *destheight = header.height;
      fclose(fi);
      return 1;
  }
  
  EXPORT int png_load(const char*sname, unsigned*destwidth, unsigned*destheight, unsigned char**destdata)
  {
      char tagid[4];
      int len;
      unsigned char*data;
      unsigned char*imagedata;
      unsigned char*zimagedata=0;
      unsigned long int zimagedatalen=0;
      unsigned char*palette = 0;
      int palettelen = 0;
      unsigned char*alphapalette = 0;
      int alphapalettelen = 0;
      struct png_header header;
      int bypp;
      unsigned char*data2 = 0;
      unsigned char alphacolor[3];
      int hasalphacolor=0;
  
      FILE *fi;
      unsigned char *scanline;
  
      if ((fi = fopen(sname, "rb")) == NULL) {
  	printf("Couldn't open %s\n", sname);
  	return 0;
      }
  
      if(!png_read_header(fi, &header)) {
  	fclose(fi);
  	return 0;
      }
  
      if(header.mode == 3 || header.mode == 0) bypp = 1;
      else if(header.mode == 4) bypp = 2;
      else if(header.mode == 2) bypp = 3;
      else if(header.mode == 6) bypp = 4;
      else {
  	printf("ERROR: mode:%d\n", header.mode);
  	return 0;
      }
  
      unsigned long long imagedatalen_64 = ((unsigned long long)header.width + 1) * header.height * bypp;
      if(imagedatalen_64 > 0xffffffff)
  	return 0;
      unsigned long imagedatalen = (unsigned long)imagedatalen_64;
      imagedata = (unsigned char*)malloc(imagedatalen);
  
      fseek(fi,8,SEEK_SET);
      while(!feof(fi))
      {
  	if(!png_read_chunk(&tagid, &len, &data, fi))
  	    break;
  	if(!strncmp(tagid, "IEND", 4)) {
  	    break;
  	}
  	if(!strncmp(tagid, "PLTE", 4)) {
  	    palette = data;
  	    palettelen = len/3;
  	    data = 0; //don't free data
  	    //printf("%d colors in palette\n", palettelen);
  	}
  	if(!strncmp(tagid, "tRNS", 4)) {
  	    if(header.mode == 3) {
  		alphapalette = data;
  		alphapalettelen = len;
  		data = 0; //don't free data
  		//printf("found %d alpha colors\n", alphapalettelen);
  	    } else if(header.mode == 0 || header.mode == 2) {
  		int t;
  		if(header.mode == 2) {
  		    alphacolor[0] = data[1];
  		    alphacolor[1] = data[3];
  		    alphacolor[2] = data[5];
  		} else {
  		    alphacolor[0] = alphacolor[1] = alphacolor[2] = data[1];
  		}
  		hasalphacolor = 1;
  	    }
  	}
  	if(!strncmp(tagid, "IDAT", 4)) {
  	    if(!zimagedata) {
  		zimagedatalen = len;
  		zimagedata = (unsigned char*)malloc(len);
  		memcpy(zimagedata,data,len);
  	    } else {
  		zimagedata = (unsigned char*)realloc(zimagedata, zimagedatalen+len);
  		memcpy(&zimagedata[zimagedatalen], data, len);
  		zimagedatalen += len;
  	    }
  	}
  	if(!strncmp(tagid, "tEXt", 4)) {
  	    /*int t;
  	    printf("Image Text: ");
  	    for(t=0;t<len;t++) {
  		if(data[t]>=32 && data[t]<128)
  		    printf("%c", data[t]);
  		else
  		    printf("?");
  	    }
  	    printf("\n");*/
  	}
  	if(data) {
  	    free(data); data=0;
          }
      }
      
      fclose(fi);
      if(!zimagedata || uncompress(imagedata, &imagedatalen, zimagedata, zimagedatalen) != Z_OK) {
  	printf("Couldn't uncompress %s!\n", sname);
  	if(zimagedata)
  	    free(zimagedata);
  	return 0;
      }
      free(zimagedata);
  
      *destwidth = header.width;
      *destheight = header.height;
  	
      data2 = (unsigned char*)malloc(header.width*header.height*4);
  
      if(header.mode == 4)
      {
  	int i,s=0;
  	int x,y;
  	int pos=0;
  	unsigned char* old= (unsigned char*)malloc(header.width*2);
  	memset(old, 0, header.width*2);
  	*destdata = data2;
  	for(y=0;y<header.height;y++) {
  	    int mode = imagedata[pos++]; //filter mode
  	    unsigned char*src;
  	    unsigned char*dest;
  	    int x;
  	    dest = &data2[(y*header.width)*4];
  
  	    if(header.bpp == 8) {
  		/* one byte per pixel */
  		src = &imagedata[pos];
  		pos+=header.width*2;
  	    } else {
  		/* not implemented yet */
  		fprintf(stderr, "ERROR: mode=4 bpp:%d\n", header.bpp);
  		free(data2);
  		return 0;
  	    }
  
  	    applyfilter2(mode, src, old, dest, header.width);
  	    memcpy(old, dest, header.width*2);
  
  	    for(x=header.width-1;x>=0;x--) {
  		unsigned char gray = dest[x*2+0];
  		unsigned char alpha = dest[x*2+1];
  		dest[x*4+0] = alpha;
  		dest[x*4+1] = gray;
  		dest[x*4+2] = gray;
  		dest[x*4+3] = gray;
  	    }
  	}
  	free(old);
          free(imagedata);
      } else if(header.mode == 6 || header.mode == 2) {
  	int i,s=0;
  	int x,y;
  	int pos=0;
  	*destdata = data2;
  	
  	unsigned char* firstline = malloc(header.width*4);
  	memset(firstline,0,header.width*4);
  	for(y=0;y<header.height;y++) {
  	    int mode = imagedata[pos++]; //filter mode
  	    unsigned char*src;
  	    unsigned char*dest;
  	    unsigned char*old;
  	    dest = &data2[(y*header.width)*4];
  
  	    if(header.bpp == 8)
  	    {
  		/* one byte per pixel */
  		src = &imagedata[pos];
  		pos+=header.width*(header.mode==6?4:3);
  	    } else {
  		/* not implemented yet */
  		fprintf(stderr, "ERROR: bpp:%d\n", header.bpp);
  		free(data2);
  		return 0;
  	    }
  
  	    if(!y) {
  		old = firstline;
  	    } else {
  		old = &data2[(y-1)*header.width*4];
  	    }
  	    if(header.mode == 6) { 
  		png_inverse_filter_32(mode, src, old, dest, header.width);
  	    } else { // header.mode = 2
  		applyfilter3(mode, src, old, dest, header.width);
  		/* replace alpha color */
  		if(hasalphacolor) {
  		    int x;
  		    for(x=0;x<header.width;x++) {
  			if(dest[x*4+1] == alphacolor[0] &&
  			   dest[x*4+2] == alphacolor[1] &&
  			   dest[x*4+3] == alphacolor[2]) {
  			    *(u32*)&dest[x*4] = 0;
  			}
  		    }
  		}
  	    }
  	}
  	free(firstline);
          free(imagedata);
      } else if(header.mode == 0 || header.mode == 3) {
  	COL*rgba = 0;
  	unsigned char*tmpline = (unsigned char*)malloc(header.width+1);
  	unsigned char*destline = (unsigned char*)malloc(header.width+1);
  	int i,x,y;
  	int pos=0;
  	
  	*destdata = data2;
  	
  	if(header.mode == 0) { // grayscale palette
              int mult = (0x1ff>>header.bpp);
  	    palettelen = 1<<header.bpp;
  	    rgba = (COL*)malloc(palettelen*sizeof(COL));
  	    for(i=0;i<palettelen;i++) {
  		rgba[i].a = 255;
  		rgba[i].r = i*mult;
  		rgba[i].g = i*mult;
  		rgba[i].b = i*mult;
  		if(hasalphacolor) {
  		    if(rgba[i].r == alphacolor[0])
  			rgba[i].a = 0;
  		}
  	    }
  	} else {
  	    if(!palette) {
  		fprintf(stderr, "Error: No palette found!\n");
  		exit(1);
  	    }
  	    rgba = (COL*)malloc(palettelen*4);
  	    /* 24->32 bit conversion */
  	    for(i=0;i<palettelen;i++) {
  		rgba[i].r = palette[i*3+0];
  		rgba[i].g = palette[i*3+1];
  		rgba[i].b = palette[i*3+2];
  		if(alphapalette && i<alphapalettelen) {
  		    rgba[i].a = alphapalette[i];
  		    /*rgba[i].r = ((int)rgba[i].r*rgba[i].a)/255;
  		    rgba[i].g = ((int)rgba[i].g*rgba[i].a)/255;
  		    rgba[i].b = ((int)rgba[i].b*rgba[i].a)/255;*/
  		} else {
  		    rgba[i].a = 255;
  		}
  		if(hasalphacolor) {
  		    if(rgba[i].r == alphacolor[0] &&
  		       rgba[i].g == alphacolor[1] &&
  		       rgba[i].b == alphacolor[2])
  			rgba[i].a = 0;
  		}
  	    }
  	}
  
  	for(y=0;y<header.height;y++) {
  	    int mode = imagedata[pos++]; //filter mode
  	    int x;
  	    unsigned char*old;
  	    unsigned char*src;
  	    src = &imagedata[pos];
  	    if(header.bpp == 8) {
  		pos+=header.width;
  	    } else {
  		int x,s=0;
  		int bitpos = 0;
  		u32 v = (1<<header.bpp)-1;
  		for(x=0;x<header.width;x++) {
  		    u32 r = src[s/8]<<8 | 
  			    src[s/8+1];
  		    int t;
  		    tmpline[x] = (r>>(16-header.bpp-(s&7)))&v;
  		    s+=header.bpp;
  		}
  		src = tmpline;
  		pos+=(header.width*header.bpp+7)/8;
  	    }
  
  	    if(!y) {
  		memset(destline,0,header.width);
  		old = &destline[y*header.width];
  	    } else {
  		old = tmpline;
  	    }
  	    applyfilter1(mode, src, old, destline, header.width);
  	    memcpy(tmpline,destline,header.width);
  	    for(x=0;x<header.width;x++) {
  		*(COL*)&data2[y*header.width*4+x*4+0] = rgba[destline[x]];
  	    }
  	}
  	free(tmpline);
  	free(destline);
  	free(rgba);
          free(imagedata);
      } else {
  	printf("expected PNG mode to be 2, 3 or 6 (is:%d)\n", header.mode);
  	return 0;
      }
  
      return 1;
  }
  
  static char hasAlpha(unsigned char*_image, int size)
  {
      COL*image = (COL*)_image;
      int t;
      for(t=0;t<size;t++) {
          if(image[t].a!=255)
              return 1;
      }
      return 0;
  }
  
  typedef struct {
      u32 num;
      u32 color;
  } colornum_t;
  
  static int compare_colors(const void*_c1, const void*_c2) {
      colornum_t*c1 = (colornum_t*)_c1;
      colornum_t*c2 = (colornum_t*)_c2;
      return c2->num - c1->num;
  }
  
  static colornum_t* getColors(COL*image, int size, int*num)
  {
      unsigned char*colexists = malloc((256*256*256)/8);
      memset(colexists, 0, (256*256*256)/8);
      int t;
      int count=0;
  
      /* find all different colors in the image */
      for(t=0;t<size;t++) {
          int index = (image[t].r)|(image[t].g)<<8|(image[t].b)<<16;
          if(!(colexists[index/8]&(1<<(index&7)))) {
              count++;
              colexists[index/8]|=(1<<(index&7));
          }
      }
      
      /* now store them in an array */
      colornum_t*colors=(colornum_t*)malloc(sizeof(colornum_t)*count);
      int pos=0;
      for(t=0;t<256*256*256;t++) {
          if(colexists[t/8]&(1<<(t&7))) {
              colors[pos].color = t;
              colors[pos].num = 0;
              pos++;
          }
      }
  
      /* next, count how often each color occurs */
      for(t=0;t<size;t++) {
          int col = (image[t].r)|(image[t].g)<<8|(image[t].b)<<16;
          int min,max,i,l;
          for(min=0, max=count, i=count/2, l=count; i != l; l=i,i=(min+max)/2) {
  	    // binary search
              if(colors[i].color >= col) max=i;
              else min=i+1;
          }
          assert(colors[i].color==col);
          colors[i].num++;
      }
      free(colexists);
      *num = count;
      return colors;
  }
  
  static void getOptimalPalette(COL*image, int size, int palettesize, COL*palette)
  {
      int num;
      memset(palette, 0, sizeof(COL)*256);
      colornum_t*colors = getColors(image, size, &num);
  
      assert(palettesize<=256);
  
      qsort(colors, num, sizeof(colornum_t), compare_colors);
  
      if(num<=palettesize) {
          /* if there are not more than palettesize different colors in 
             the image anyway, we are done */
          int t;
          for(t=0;t<num;t++) {
              palette[t].r = colors[t].color;
              palette[t].g = colors[t].color>>8;
              palette[t].b = colors[t].color>>16;
              palette[t].a = 255;
          }
          return;
      }
  
      if(num>2048) {
  	/* if there are too many different colors, pick the ones that
  	   occur most often */
  	num = 2048;
      }
  
      colornum_t*centers = malloc(sizeof(colornum_t)*palettesize);
      int t;
      for(t=0;t<palettesize;t++) {
          centers[t].color = colors[t].color;
      }
      unsigned char*belongsto = (unsigned char*)malloc(num);
      memset(belongsto, 0, num);
      /* do a k-means clustering on the colors */
      char change = 1;
      int tries = 0;
      while(change) {
          if(tries++ >= (palettesize+num)*2) {
              fprintf(stderr, "Warning: didn't find optimal palette\n");
              break;
          }
          change = 0;
          int s,t;
          for(s=0;s<palettesize;s++) {
              centers[s].num = 0;
          }
          for(t=0;t<num;t++) {
              int best=0x7fffffff;
              int bestpos=0;
              for(s=0;s<palettesize;s++) {
                  int distance = 0;
                  distance += abs((centers[s].color>>0&0xff) - (colors[t].color>>0&0xff));
                  distance += abs((centers[s].color>>8&0xff) - (colors[t].color>>8&0xff));
                  distance += abs((centers[s].color>>16&0xff) - (colors[t].color>>16&0xff));
                  distance *= colors[t].num;
                  if(distance<best) {
                      best = distance;
                      bestpos = s;
                  }
              }
              if(bestpos!=belongsto[t])
                  change = 1;
              belongsto[t] = bestpos;
          }
          for(s=0;s<palettesize;s++) {
              int r=0;
              int g=0;
              int b=0;
              int count=0;
              for(t=0;t<num;t++) {
                  if(belongsto[t]==s) {
                      r += ((colors[t].color>>0)&0xff)*colors[t].num;
                      g += ((colors[t].color>>8)&0xff)*colors[t].num;
                      b += ((colors[t].color>>16)&0xff)*colors[t].num;
                      count+=colors[t].num;
                  }
              }
              if(!count) {
                  int random = rand()%num;
                  centers[s].color = colors[random].color;
                  centers[s].num = 0;
                  change = 1;
              } else {
                  r /= count;
                  g /= count;
                  b /= count;
                  centers[s].color = r|g<<8|b<<16;
                  centers[s].num = count;
              }
          }
      }
      free(belongsto);
      free(colors);
      for(t=0;t<palettesize;t++) {
          palette[t].r = centers[t].color;
          palette[t].g = centers[t].color>>8;
          palette[t].b = centers[t].color>>16;
          palette[t].a = 255;
      }
      free(centers);
  }
  
  static int sqr(const int x) {return x*x;}
  
  static void png_quantize_image(unsigned char*_image, int size, int numcolors, unsigned char**newimage, COL*palette) 
  {
      COL*image = (COL*)_image;
      getOptimalPalette(image, size, numcolors, palette);
      *newimage = (unsigned char*)malloc(size);
      int t;
      for(t=0;t<size;t++) {
          int best=0x7fffffff;
          int bestcol = 0;
          int s;
          for(s=0;s<numcolors;s++) {
              int distance = 0;
              distance += sqr((palette[s].r) - (image[t].r))*5;
              distance += sqr((palette[s].g) - (image[t].g))*6;
              distance += sqr((palette[s].b) - (image[t].b))*4;
              if(distance<best) {
                  best = distance;
                  bestcol = s;
              }
          }
          (*newimage)[t] = bestcol;
      }
  }
  
  static u32 mycrc32;
  
  static u32*crc32_table = 0;
  static void make_crc32_table(void)
  {
    int t;
    if(crc32_table) 
        return;
    crc32_table = (u32*)malloc(1024);
  
    for (t = 0; t < 256; t++) {
      u32 c = t;
      int s;
      for (s = 0; s < 8; s++) {
        c = (0xedb88320L*(c&1)) ^ (c >> 1);
      }
      crc32_table[t] = c;
    }
  }
  static inline void png_write_byte(FILE*fi, unsigned char byte)
  {
      fwrite(&byte,1,1,fi);
      mycrc32 = crc32_table[(mycrc32 ^ byte) & 0xff] ^ (mycrc32 >> 8);
  }
  static long png_start_chunk(FILE*fi, char*type, int len)
  {
      unsigned char mytype[4]={0,0,0,0};
      unsigned char mylen[4];
      long filepos;
      mylen[0] = len>>24;
      mylen[1] = len>>16;
      mylen[2] = len>>8;
      mylen[3] = len;
      memcpy(mytype,type,strlen(type));
      filepos = ftell(fi);
      fwrite(&mylen, 4, 1, fi);
      mycrc32=0xffffffff;
      png_write_byte(fi,mytype[0]);
      png_write_byte(fi,mytype[1]);
      png_write_byte(fi,mytype[2]);
      png_write_byte(fi,mytype[3]);
      return filepos;
  }
  static void png_patch_len(FILE*fi, int pos, int len)
  {
      unsigned char mylen[4];
      long filepos;
      mylen[0] = len>>24;
      mylen[1] = len>>16;
      mylen[2] = len>>8;
      mylen[3] = len;
      fseek(fi, pos, SEEK_SET);
      fwrite(&mylen, 4, 1, fi);
      fseek(fi, 0, SEEK_END);
  }
  static void png_write_bytes(FILE*fi, unsigned char*bytes, int len)
  {
      int t;
      for(t=0;t<len;t++)
  	png_write_byte(fi,bytes[t]);
  }
  static void png_write_dword(FILE*fi, u32 dword)
  {
      png_write_byte(fi,dword>>24);
      png_write_byte(fi,dword>>16);
      png_write_byte(fi,dword>>8);
      png_write_byte(fi,dword);
  }
  static void png_end_chunk(FILE*fi)
  {
      u32 tmp = mycrc32^0xffffffff;
      unsigned char tmp2[4];
      tmp2[0] = tmp>>24;
      tmp2[1] = tmp>>16;
      tmp2[2] = tmp>>8;
      tmp2[3] = tmp;
      fwrite(&tmp2,4,1,fi);
  }
  
  #define ZLIB_BUFFER_SIZE 16384
  
  static long compress_line(z_stream*zs, Bytef*line, int len, FILE*fi)
  {
      long size = 0;
      zs->next_in = line;
      zs->avail_in = len;
  
      while(1) {
  	int ret = deflate(zs, Z_NO_FLUSH);
  	if (ret != Z_OK) {
  	    fprintf(stderr, "error in deflate(): %s", zs->msg?zs->msg:"unknown");
  	    return 0;
  	}
  	if(zs->avail_out != ZLIB_BUFFER_SIZE) {
  	    int consumed = ZLIB_BUFFER_SIZE - zs->avail_out;
  	    size += consumed;
  	    png_write_bytes(fi, zs->next_out - consumed , consumed);
  	    zs->next_out = zs->next_out - consumed;
  	    zs->avail_out = ZLIB_BUFFER_SIZE;
  	}
  	if(!zs->avail_in) {
  	    break;
  	}
      }
      return size;
  }
  
  static int test_line(z_stream*zs_orig, Bytef*line, int linelen)
  {
      z_stream zs;
      int ret = deflateCopy(&zs, zs_orig);
      if(ret != Z_OK) {
  	fprintf(stderr, "Couldn't copy stream\n");
  	return 0;
      }
  
      zs.next_in = line;
      zs.avail_in = linelen;
  
      long size = 0;
  
      int mode = Z_SYNC_FLUSH;
      while(1) {
  	int ret = deflate(&zs, mode);
  	if (ret != Z_OK && ret != Z_STREAM_END) {
  	    fprintf(stderr, "error in deflate(): %s (mode %s, %d bytes remaining)\n", zs.msg?zs.msg:"unknown", 
  		    mode==Z_SYNC_FLUSH?"Z_SYNC_FLUSH":"Z_FINISH", zs.avail_in);
  	    return 0;
  	}
  	if(zs.avail_out != ZLIB_BUFFER_SIZE) {
  	    int consumed = ZLIB_BUFFER_SIZE - zs.avail_out;
  	    size += consumed;
  	    zs.next_out = zs.next_out - consumed;
  	    zs.avail_out = ZLIB_BUFFER_SIZE;
  	}
          if (ret == Z_STREAM_END) {
              break;
          }
  	if(!zs.avail_in) {
  	    mode = Z_FINISH;
  	}
      }
      ret = deflateEnd(&zs);
      if (ret != Z_OK) {
  	fprintf(stderr, "error in deflateEnd(): %s\n", zs.msg?zs.msg:"unknown");
  	return 0;
      }
      return size;
  }
  
  static int finishzlib(z_stream*zs, FILE*fi)
  {
      int size = 0;
      int ret;
      while(1) {
          ret = deflate(zs, Z_FINISH);
          if (ret != Z_OK &&
              ret != Z_STREAM_END) {
  	    fprintf(stderr, "error in deflate(finish): %s\n", zs->msg?zs->msg:"unknown");
  	    return 0;
  	}
  
  	if(zs->avail_out != ZLIB_BUFFER_SIZE) {
  	    int consumed = ZLIB_BUFFER_SIZE - zs->avail_out;
  	    size += consumed;
  	    png_write_bytes(fi, zs->next_out - consumed , consumed);
  	    zs->next_out = zs->next_out - consumed;
  	    zs->avail_out = ZLIB_BUFFER_SIZE;
  	}
          if (ret == Z_STREAM_END) {
              break;
          }
      }
      ret = deflateEnd(zs);
      if (ret != Z_OK) {
  	fprintf(stderr, "error in deflateEnd(): %s\n", zs->msg?zs->msg:"unknown");
  	return 0;
      }
      return size;
  }
  
  static inline u32 color_hash(COL*col)
  {
      u32 col32 = *(u32*)col;
      u32 hash = (col32 >> 17) ^ col32;
      hash ^= ((hash>>8) + 1) ^ hash;
      return hash;
  }
  
  static int png_get_number_of_palette_entries(COL*img, unsigned width, unsigned height, COL*palette, char*has_alpha)
  {
      int len = width*height;
      int t;
      int palsize = 0;
      int size[256];
      int palette_overflow = 0;
      u32 lastcol32 = 0;
      
      memset(size, 0, sizeof(size));
  
      u32*pal = (u32*)malloc(65536*sizeof(u32));
      int*count = (int*)malloc(65536*sizeof(int));
  
      assert(sizeof(COL)==sizeof(u32));
      assert(width && height);
  
      lastcol32 = (*(u32*)&img[0])^0xffffffff; // don't match
  
      for(t=0;t<len;t++) {
  	u32 col32 = *(u32*)&img[t];
  	if(col32 == lastcol32)
  	    continue;
  	
  	if(img[t].a!=255)
  	    *has_alpha=1;
  	int i;
  	
  	u32 hash = color_hash(&img[t])&255;
  
  	int csize = size[hash];
  	u32*cpal = &pal[hash*256];
  	int*ccount = &count[hash*256];
  	for(i=0;i<csize;i++) {
  	    if(col32 == cpal[i]) {
  		ccount[i]++;
  		break;
  	    }
  	}
  	if(i==csize) {
  	    if(palsize==256) {
  		palette_overflow = 1;
  		break;
  	    }
  	    count[size[hash]] = 1;
  	    cpal[size[hash]++] = col32;
  	    palsize++;
  	}
  	lastcol32 = col32;
      }
      if(palette_overflow) {
  	free(pal);
  	*has_alpha=1;
  	return width*height;
      }
      if(palette) {
  	int i = 0;
  	int occurences[256];
  	for(t=0;t<256;t++) {
  	    int s;
  	    int csize = size[t];
  	    u32* cpal = &pal[t*256];
  	    int* ccount = &count[t*256];
  	    for(s=0;s<csize;s++) {
  		occurences[i] = ccount[s];
  		palette[i++] = *(COL*)(&cpal[s]);
  	    }
  	}
  	assert(i==palsize);
  	int j;
  	for(i=0;i<palsize-1;i++) {
  	    for(j=i+1;j<palsize;j++) {
  		if(occurences[j] < occurences[i]) {
  		    int o = occurences[i];
  		    COL c = palette[i];
  		    occurences[i] = occurences[j];
  		    palette[i] = palette[j];
  		    occurences[j] = o;
  		    palette[j] = c;
  		}
  	    }
  	}
      }
      free(pal);
      free(count);
      return palsize;
  }
  
  static void png_map_to_palette(COL*src, unsigned char*dest, int size, COL*palette, int palette_size)
  {
      int t;
      int palette_hash[1024];
      memset(palette_hash, 0, sizeof(int)*1024);
      
      for(t=0;t<palette_size;t++) {
  	u32 hash = color_hash(&palette[t])&1023;
  	while(palette_hash[hash])
  	    hash = (hash+1)&1023;
  	palette_hash[hash] = t;
      }
  
      for(t=0;t<size;t++) {
  	u32 hash = color_hash(&src[t]);
  	int index = 0;
  	while(1) {
  	    hash&=1023;
  	    index = palette_hash[hash];
  	    if(!memcmp(&palette[index], &src[t], sizeof(COL)))
  		break;
  	    hash++;
  	}
  	dest[t] = palette_hash[hash];
      }
  }
  
  static int png_apply_specific_filter_8(int filtermode, unsigned char*dest, unsigned char*src, unsigned width)
  {
      int pos2 = 0;
      int pos = 0;
      int srcwidth = width;
      int x;
      if(filtermode == 0) {
  	for(x=0;x<width;x++) {
  	    dest[pos2++]=src[pos++]; //alpha
  	}
      } else if(filtermode == 1) {
  	/* x difference filter */
  	dest[pos2++]=src[pos++];
  	for(x=1;x<width;x++) {
  	    dest[pos2++]=src[pos] - src[pos-1];
  	    pos++;
  	}
      } else if(filtermode == 2) {
  	/* y difference filter */
  	for(x=0;x<width;x++) {
  	    dest[pos2++]=src[pos+0] - src[pos-srcwidth+0]; //alpha
  	    pos++;
  	}
      } else if(filtermode == 3) {
  	dest[pos2++]=src[pos+0] - src[pos-srcwidth+0]/2;
  	pos++;
  	/* x+y difference filter */
  	for(x=1;x<width;x++) {
  	    dest[pos2++]=src[pos+0] - (src[pos-1+0] + src[pos-srcwidth+0])/2; //alpha
  	    pos++;
  	}
      } else if(filtermode == 4) {
  	dest[pos2++]=src[pos+0] - PaethPredictor(0, src[pos-srcwidth+0], 0);
  	pos++;
  	/* paeth difference filter */
  	for(x=1;x<width;x++) {
  	    dest[pos2++]=src[pos+0] - PaethPredictor(src[pos-1+0], src[pos-srcwidth+0], src[pos-1-srcwidth+0]);
  	    pos++;
  	}
      }
      return filtermode;
  }
  
  static int png_apply_specific_filter_32(int filtermode, unsigned char*dest, unsigned char*src, unsigned width)
  {
      int pos2 = 0;
      int pos = 0;
      int srcwidth = width*4;
      int x;
      if(filtermode == 0) {
  	for(x=0;x<width;x++) {
  	    dest[pos2++]=src[pos+1];
  	    dest[pos2++]=src[pos+2];
  	    dest[pos2++]=src[pos+3];
  	    dest[pos2++]=src[pos+0]; //alpha
  	    pos+=4;
  	}
      } else if(filtermode == 1) {
  	/* x difference filter */
  	dest[pos2++]=src[pos+1];
  	dest[pos2++]=src[pos+2];
  	dest[pos2++]=src[pos+3];
  	dest[pos2++]=src[pos+0];
  	pos+=4;
  	for(x=1;x<width;x++) {
  	    dest[pos2++]=src[pos+1] - src[pos-4+1];
  	    dest[pos2++]=src[pos+2] - src[pos-4+2];
  	    dest[pos2++]=src[pos+3] - src[pos-4+3];
  	    dest[pos2++]=src[pos+0] - src[pos-4+0]; //alpha
  	    pos+=4;
  	}
      } else if(filtermode == 2) {
  	/* y difference filter */
  	for(x=0;x<width;x++) {
  	    dest[pos2++]=src[pos+1] - src[pos-srcwidth+1];
  	    dest[pos2++]=src[pos+2] - src[pos-srcwidth+2];
  	    dest[pos2++]=src[pos+3] - src[pos-srcwidth+3];
  	    dest[pos2++]=src[pos+0] - src[pos-srcwidth+0]; //alpha
  	    pos+=4;
  	}
      } else if(filtermode == 3) {
  	dest[pos2++]=src[pos+1] - src[pos-srcwidth+1]/2;
  	dest[pos2++]=src[pos+2] - src[pos-srcwidth+2]/2;
  	dest[pos2++]=src[pos+3] - src[pos-srcwidth+3]/2;
  	dest[pos2++]=src[pos+0] - src[pos-srcwidth+0]/2;
  	pos+=4;
  	/* x+y difference filter */
  	for(x=1;x<width;x++) {
  	    dest[pos2++]=src[pos+1] - (src[pos-4+1] + src[pos-srcwidth+1])/2;
  	    dest[pos2++]=src[pos+2] - (src[pos-4+2] + src[pos-srcwidth+2])/2;
  	    dest[pos2++]=src[pos+3] - (src[pos-4+3] + src[pos-srcwidth+3])/2;
  	    dest[pos2++]=src[pos+0] - (src[pos-4+0] + src[pos-srcwidth+0])/2; //alpha
  	    pos+=4;
  	}
      } else if(filtermode == 4) {
  	dest[pos2++]=src[pos+1] - PaethPredictor(0, src[pos-srcwidth+1], 0);
  	dest[pos2++]=src[pos+2] - PaethPredictor(0, src[pos-srcwidth+2], 0);
  	dest[pos2++]=src[pos+3] - PaethPredictor(0, src[pos-srcwidth+3], 0);
  	dest[pos2++]=src[pos+0] - PaethPredictor(0, src[pos-srcwidth+0], 0);
  	pos+=4;
  	/* paeth difference filter */
  	for(x=1;x<width;x++) {
  	    dest[pos2++]=src[pos+1] - PaethPredictor(src[pos-4+1], src[pos-srcwidth+1], src[pos-4-srcwidth+1]);
  	    dest[pos2++]=src[pos+2] - PaethPredictor(src[pos-4+2], src[pos-srcwidth+2], src[pos-4-srcwidth+2]);
  	    dest[pos2++]=src[pos+3] - PaethPredictor(src[pos-4+3], src[pos-srcwidth+3], src[pos-4-srcwidth+3]);
  	    dest[pos2++]=src[pos+0] - PaethPredictor(src[pos-4+0], src[pos-srcwidth+0], src[pos-4-srcwidth+0]);
  	    pos+=4;
  	}
      }
      return filtermode;
  }
  
  static int*num_bits_table = 0;
  
  static void make_num_bits_table()
  {
      if(num_bits_table) return;
      num_bits_table = malloc(sizeof(num_bits_table[0])*256);
      int t;
      for(t=0;t<256;t++) {
  	int bits=0;
  	int v = t;
  	while(v) {
  	    bits++;
  	    v&=v-1;
  	}
  	num_bits_table[t]=bits;
      }
  }
  
  static int png_find_best_filter(unsigned char*src, unsigned width, int bpp, int y)
  {
      make_num_bits_table();
      
      int num_filters = y>0?5:2; //don't apply y-direction filter in first line
      
      int bytes_per_pixel = bpp>>3;
      int w = width*bytes_per_pixel;
      int back_x = bytes_per_pixel;
      int back_y = y?width*bytes_per_pixel:0;
  
      unsigned char*pairs[5];
      pairs[0] = calloc(1, 8192);
      pairs[1] = calloc(1, 8192);
      pairs[2] = calloc(1, 8192);
      pairs[3] = calloc(1, 8192);
      pairs[4] = calloc(1, 8192);
      
      unsigned char old[5];
      int l = bytes_per_pixel - 1;
      old[0] = src[l];
      old[1] = src[l];
      old[2] = src[l] - src[l-back_y];
      old[3] = src[l] - src[l-back_y];
      old[4] = src[l] - PaethPredictor(0, src[l-back_y], 0);
  
      int different_pairs[5] = {0,0,0,0,0};
  
      int x;
      for(x=bytes_per_pixel;x<w;x++) {
  	unsigned char dest[5];
  	dest[0] = src[x];
  	dest[1] = src[x] - src[x-back_x];
  	dest[2] = src[x] - src[x-back_y];
  	dest[3] = src[x] - (src[x-back_x] + src[x-back_y])/2;
  	dest[4] = src[x] - PaethPredictor(src[x-back_x], src[x-back_y], src[x-back_x-back_y]);
  
  	int i;
  	for(i=0;i<5;i++) {
  	    int v = dest[i]<<8|old[i];
  	    int p = v>>3;
  	    int b = 1<<(v&7);
  	    if(!pairs[i][p]&b) {
  		pairs[i][p]|=b;
  		different_pairs[i]++;
  	    }
  	}
  	memcpy(old, dest, sizeof(old));
      }
      int f;
      int best_nr = 0;
      int best_energy = INT_MAX;
      for(f=0;f<num_filters;f++) {
  	int energy = different_pairs[f];
  	if(energy<best_energy) {
  	    best_nr = f;
  	    best_energy = energy;
  	}
      }
      free(pairs[0]);
      free(pairs[1]);
      free(pairs[2]);
      free(pairs[3]);
      free(pairs[4]);
      return best_nr;
  }
      
      
  static int png_apply_filter(unsigned char*dest, unsigned char*src, unsigned width, int y, int bpp)
  {
      int best_nr = 0;
  #if 0
      make_num_bits_table();
      int num_filters = y>0?5:2; //don't apply y-direction filter in first line
      int f;
      int best_energy = INT_MAX;
      int w = width*(bpp/8);
      unsigned char* pairs = malloc(8192);
      assert(bpp==8 || bpp==32);
      for(f=0;f<num_filters;f++) {
  	if(bpp==8)
  	    png_apply_specific_filter_8(f, dest, src, width);
  	else
  	    png_apply_specific_filter_32(f, dest, src, width);
  	int x;
  
  	/* approximation for zlib compressability: test how many different
  	   (byte1,byte2) occur */
  	memset(pairs, 0, 8192);
  	int different_pairs = 0;
  	for(x=0;x<w-1;x++) {
  	    int v = dest[x+1]<<8|dest[x];
  	    int p = v>>3;
  	    int b = 1<<(v&7);
  	    if(!pairs[p]&b) {
  		pairs[p]|=b;
  		different_pairs ++;
  	    }
  	}
  	int energy = different_pairs;
  	if(energy<best_energy) {
  	    best_nr = f;
  	    best_energy = energy;
  	}
      }
      free(pairs);
  #else
      best_nr = png_find_best_filter(src, width, bpp, y);
  #endif
      if(bpp==8)
  	png_apply_specific_filter_8(best_nr, dest, src, width);
      else
  	png_apply_specific_filter_32(best_nr, dest, src, width);
      return best_nr;
  }
  
  int png_apply_filter_8(unsigned char*dest, unsigned char*src, unsigned width, int y)
  {
      return png_apply_filter(dest, src, width, y, 8);
  }
  int png_apply_filter_32(unsigned char*dest, unsigned char*src, unsigned width, int y)
  {
      return png_apply_filter(dest, src, width, y, 32);
  }
  
  static void png_write_palette_based2(const char*filename, unsigned char*data, unsigned width, unsigned height, int numcolors, int compression)
  {
      FILE*fi;
      int crc;
      int t;
      unsigned char format;
      unsigned char tmp;
      unsigned char* data2=0;
      unsigned char head[] = {137,80,78,71,13,10,26,10}; // PNG header
      int cols;
      char alpha = 1;
      int pos = 0;
      int error;
      u32 tmp32;
      int bpp;
      int ret;
      char has_alpha=0;
      z_stream zs;
      COL palette[256];
  
      make_crc32_table();
  
      if(numcolors>256) {
  	bpp = 32;
  	cols = 0;
  	format = 5;
      } else if(!numcolors) {
  	int num = png_get_number_of_palette_entries((COL*)data, width, height, palette, &has_alpha);
  	if(num<=255) {
  	    //printf("image has %d different colors (alpha=%d)\n", num, has_alpha);
  	    data2 = malloc(width*height);
  	    png_map_to_palette((COL*)data, data2, width*height, palette, num);
  	    data = data2;
  	    bpp = 8;
  	    cols = num;
  	    format = 3;
  	} else {
  	    bpp = 32;
  	    cols = 0;
  	    format = 5;
  	}
      } else {
          bpp = 8;
          cols = numcolors;
          format = 3;
          png_quantize_image(data, width*height, numcolors, &data, palette);
      }
  
      fi = fopen(filename, "wb");
      if(!fi) {
  	perror("open");
  	return;
      }
      fwrite(head,sizeof(head),1,fi);     
  
      png_start_chunk(fi, "IHDR", 13);
       png_write_dword(fi,width);
       png_write_dword(fi,height);
       png_write_byte(fi,8);
       if(format == 3)
       png_write_byte(fi,3); //indexed
       else if(format == 5 && alpha==0)
       png_write_byte(fi,2); //rgb
       else if(format == 5 && alpha==1)
       png_write_byte(fi,6); //rgba
       else return;
  
       png_write_byte(fi,0); //compression mode
       png_write_byte(fi,0); //filter mode
       png_write_byte(fi,0); //interlace mode
      png_end_chunk(fi);
  
      if(format == 3) {
  	png_start_chunk(fi, "PLTE", cols*3);
  	for(t=0;t<cols;t++) {
  	    png_write_byte(fi,palette[t].r);
  	    png_write_byte(fi,palette[t].g);
  	    png_write_byte(fi,palette[t].b);
  	}
  	png_end_chunk(fi);
  
  	if(has_alpha) {
  	    png_start_chunk(fi, "tRNS", cols);
  	    for(t=0;t<cols;t++) {
  		png_write_byte(fi,palette[t].a);
  	    }
  	    png_end_chunk(fi);
  	}
      }
  
      long idatpos = png_start_chunk(fi, "IDAT", 0);
      
      memset(&zs,0,sizeof(z_stream));
      Bytef*writebuf = (Bytef*)malloc(ZLIB_BUFFER_SIZE);
      zs.zalloc = Z_NULL;
      zs.zfree  = Z_NULL;
      zs.opaque = Z_NULL;
      zs.next_out = writebuf;
      zs.avail_out = ZLIB_BUFFER_SIZE;
      ret = deflateInit(&zs, compression);
      if (ret != Z_OK) {
  	fprintf(stderr, "error in deflateInit(): %s", zs.msg?zs.msg:"unknown");
  	return;
      }
  
      long idatsize = 0;
      {
  	int x,y;
          int bypp = bpp/8;
  	unsigned srcwidth = width * bypp;
  	unsigned linelen = 1 + srcwidth;
          if(bypp==2) 
              linelen = 1 + ((srcwidth+1)&~1);
          else if(bypp==3) 
              linelen = 1 + ((srcwidth+2)/3)*3;
          else if(bypp==4) 
              linelen = 1 + ((srcwidth+3)&~3);
  	unsigned char* line = (unsigned char*)malloc(linelen);
  	memset(line, 0, linelen);
  #if 0
  	unsigned char* bestline = (unsigned char*)malloc(linelen);
  	memset(bestline, 0, linelen);
  	for(y=0;y<height;y++)
  	{
  	    int filtermode;
  	    int bestsize = 0x7fffffff;
  	    for(filtermode=0;filtermode<=4;filtermode++) {
  		if(!y && filtermode>=2)
  		    continue; // don't do y direction filters in the first row
  		
  		line[0]=filtermode; //filter type
                  if(bpp==8)
  		    png_apply_specific_filter_8(filtermode, line+1, &data[y*srcwidth], width);
                  else
  		    png_apply_specific_filter_32(filtermode, line+1, &data[y*srcwidth], width);
  
  		int size = test_line(&zs, line, linelen);
  		if(size < bestsize) {
  		    memcpy(bestline, line, linelen);
  		    bestsize = size;
  		}
  	    }
  	    idatsize += compress_line(&zs, bestline, linelen, fi);
  	}
  	free(bestline);
  #else
  	for(y=0;y<height;y++) {
              if(bpp==8)
  		line[0] = png_apply_filter_8(line+1, &data[y*srcwidth], width, y);
              else
  		line[0] = png_apply_filter_32(line+1, &data[y*srcwidth], width, y);
  
  	    idatsize += compress_line(&zs, line, linelen, fi);
  	}
  #endif
  	free(line);
      }
      idatsize += finishzlib(&zs, fi);
      png_patch_len(fi, idatpos, idatsize);
      png_end_chunk(fi);
  
      png_start_chunk(fi, "IEND", 0);
      png_end_chunk(fi);
  
      free(writebuf);
      if(data2)
  	free(data2);
      fclose(fi);
  }
  
  EXPORT void png_write_palette_based(const char*filename, unsigned char*data, unsigned width, unsigned height, int numcolors)
  {
      png_write_palette_based2(filename, data, width, height, numcolors, Z_BEST_COMPRESSION);
  }
  EXPORT void png_write(const char*filename, unsigned char*data, unsigned width, unsigned height)
  {
      png_write_palette_based2(filename, data, width, height, 0, Z_BEST_COMPRESSION);
  }
  EXPORT void png_write_quick(const char*filename, unsigned char*data, unsigned width, unsigned height)
  {
      png_write_palette_based2(filename, data, width, height, 257, Z_NO_COMPRESSION);
  }
  EXPORT void png_write_palette_based_2(const char*filename, unsigned char*data, unsigned width, unsigned height)
  {
      png_write_palette_based2(filename, data, width, height, 256, Z_BEST_COMPRESSION);
  }
  