X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=blobdiff_plain;f=lib%2Fpng.c;h=5895269fd8cfcf0385bb4a94e62252bbe3a138f2;hp=141218e6d4e0f138479e253e2d849c3274d0ab62;hb=27215f1c64457c50a5e1a5b2790bf2b9e73d3c4e;hpb=d66545795a2323237dec29186b714d67149dc24d

diff --git a/lib/png.c b/lib/png.c
index 141218e..5895269 100644
--- a/lib/png.c
+++ b/lib/png.c
@@ -19,9 +19,11 @@
 #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
@@ -99,12 +101,12 @@ static int png_read_header(FILE*fi, struct png_header*header)
     unsigned char*data;
     fread(head2,8,1,fi);
     if(strncmp((const char*)head,(const char*)head2,4))
-	return 0;
+	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(!strncasecmp(id, "IHDR", 4)) {
+	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];
@@ -121,7 +123,7 @@ static int png_read_header(FILE*fi, struct png_header*header)
 		return 0;
 	    }
 	    if(a!=8 && (b==2 || b==6)) {
-		printf("Bpp %d in mode %d not supported!\n", a);
+		printf("Bpp %d in mode %d not supported!\n", b, a);
 		return 0;
 	    }
 	    if(c!=0) {
@@ -197,6 +199,7 @@ static void applyfilter1(int mode, unsigned char*src, unsigned char*old, unsigne
     else if(mode==3) {
 	for(x=0;x<width;x++) {
 	    *dest = *src+(*old+last)/2;
+	    last = *dest;
 	    dest++;
 	    old++;
 	    src++;
@@ -439,7 +442,7 @@ static void inline applyfilter4(int mode, unsigned char*src, unsigned char*old,
 }
 
 
-EXPORT int getPNGdimensions(char*sname, int*destwidth, int*destheight)
+EXPORT int getPNGdimensions(const char*sname, int*destwidth, int*destheight)
 {
     FILE*fi;
     struct png_header header;
@@ -448,7 +451,6 @@ EXPORT int getPNGdimensions(char*sname, int*destwidth, int*destheight)
 	return 0;
     }
     if(!png_read_header(fi, &header)) {
-	fprintf(stderr, "Error reading header from file %s\n", sname);
 	return 0;
     }
 
@@ -457,7 +459,7 @@ EXPORT int getPNGdimensions(char*sname, int*destwidth, int*destheight)
     return 1;
 }
 
-EXPORT int getPNG(char*sname, int*destwidth, int*destheight, unsigned char**destdata)
+EXPORT int getPNG(const char*sname, int*destwidth, int*destheight, unsigned char**destdata)
 {
     char tagid[4];
     int len;
@@ -485,7 +487,7 @@ EXPORT int getPNG(char*sname, int*destwidth, int*destheight, unsigned char**dest
     }
 
     if(!png_read_header(fi, &header)) {
-	printf("Error reading header from file %s\n", sname);
+	fclose(fi);
 	return 0;
     }
 
@@ -619,6 +621,9 @@ EXPORT int getPNG(char*sname, int*destwidth, int*destheight, unsigned char**dest
 	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;
@@ -639,12 +644,11 @@ EXPORT int getPNG(char*sname, int*destwidth, int*destheight, unsigned char**dest
 	    }
 
 	    if(!y) {
-		memset(data2,0,header.width*4);
-		old = &data2[y*header.width*4];
+		old = firstline;
 	    } else {
 		old = &data2[(y-1)*header.width*4];
 	    }
-	    if(header.mode == 6) {
+	    if(header.mode == 6) { 
 		applyfilter4(mode, src, old, dest, header.width);
 	    } else { // header.mode = 2
 		applyfilter3(mode, src, old, dest, header.width);
@@ -661,6 +665,7 @@ EXPORT int getPNG(char*sname, int*destwidth, int*destheight, unsigned char**dest
 		}
 	    }
 	}
+	free(firstline);
         free(imagedata);
     } else if(header.mode == 0 || header.mode == 3) {
 	COL*rgba = 0;
@@ -760,6 +765,203 @@ EXPORT int getPNG(char*sname, int*destwidth, int*destheight, unsigned char**dest
     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;
@@ -784,21 +986,36 @@ 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 void png_start_chunk(FILE*fi, char*type, int len)
+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)
 {
@@ -824,7 +1041,416 @@ static void png_end_chunk(FILE*fi)
     fwrite(&tmp2,4,1,fi);
 }
 
-EXPORT void writePNG(char*filename, unsigned char*data, int width, int height)
+#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, int width, int 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, int 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, int 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_apply_filter(unsigned char*dest, unsigned char*src, int width, int y, int bpp)
+{
+    make_num_bits_table();
+
+    int num_filters = y>0?5:2; //don't apply y-direction filter in first line
+    int f;
+    int best_nr = 0;
+    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;
+	}
+    }
+    if(bpp==8)
+	png_apply_specific_filter_8(best_nr, dest, src, width);
+    else
+	png_apply_specific_filter_32(best_nr, dest, src, width);
+    free(pairs);
+    return best_nr;
+}
+
+int png_apply_filter_8(unsigned char*dest, unsigned char*src, int width, int y)
+{
+    return png_apply_filter(dest, src, width, y, 8);
+}
+int png_apply_filter_32(unsigned char*dest, unsigned char*src, int width, int y)
+{
+    return png_apply_filter(dest, src, width, y, 32);
+}
+
+EXPORT void savePNG(const char*filename, unsigned char*data, int width, int height, int numcolors)
 {
     FILE*fi;
     int crc;
@@ -832,10 +1458,6 @@ EXPORT void writePNG(char*filename, unsigned char*data, int width, int height)
     unsigned char format;
     unsigned char tmp;
     unsigned char* data2=0;
-    unsigned char* data3=0;
-    u32 datalen;
-    u32 datalen2;
-    u32 datalen3;
     unsigned char head[] = {137,80,78,71,13,10,26,10}; // PNG header
     int cols;
     char alpha = 1;
@@ -844,15 +1466,34 @@ EXPORT void writePNG(char*filename, unsigned char*data, int width, int height)
     u32 tmp32;
     int bpp;
     int ret;
+    char has_alpha=0;
+    z_stream zs;
+    COL palette[256];
 
     make_crc32_table();
 
-    bpp = 32;
-    cols = 0;
-    format = 5;
+    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);
+    }
 
-    datalen = (width*height*bpp/8+cols*8);
-    
     fi = fopen(filename, "wb");
     if(!fi) {
 	perror("open");
@@ -876,51 +1517,110 @@ EXPORT void writePNG(char*filename, unsigned char*data, int width, int height)
      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", 768);
-	 
-	 for(t=0;t<256;t++) {
-	     png_write_byte(fi,palette[t].r);
-	     png_write_byte(fi,palette[t].g);
-	     png_write_byte(fi,palette[t].b);
-	 }
+
+    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, Z_BEST_COMPRESSION);
+    if (ret != Z_OK) {
+	fprintf(stderr, "error in deflateInit(): %s", zs.msg?zs.msg:"unknown");
+	return;
+    }
+
+    long idatsize = 0;
     {
-	int pos2 = 0;
 	int x,y;
-	int srcwidth = width * (bpp/8);
-	datalen3 = (width*4+5)*height;
-	data3 = (unsigned char*)malloc(datalen3);
+        int bypp = bpp/8;
+	int srcwidth = width * bypp;
+	int 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++)
 	{
-	   data3[pos2++]=0; //filter type
-	   for(x=0;x<width;x++) {
-	       data3[pos2++]=data[pos+1];
-	       data3[pos2++]=data[pos+2];
-	       data3[pos2++]=data[pos+3];
-	       data3[pos2++]=data[pos+0]; //alpha
-	       pos+=4;
-	   }
-	   pos+=((srcwidth+3)&~3)-srcwidth; //align
-	}
-	datalen3=pos2;
-    }
+	    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);
 
-    datalen2 = datalen3;
-    data2 = (unsigned char*)malloc(datalen2);
+		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);
 
-    if((ret = compress (data2, &datalen2, data3, datalen3)) != Z_OK) {
-	fprintf(stderr, "zlib error in pic %d\n", ret);
-	return;
+	    idatsize += compress_line(&zs, line, linelen, fi);
+	}
+#endif
+	free(line);
     }
-    png_start_chunk(fi, "IDAT", datalen2);
-    png_write_bytes(fi,data2,datalen2);
+    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(data2);
-    free(data3);
+    free(writebuf);
+    if(data2)
+	free(data2);
+    fclose(fi);
+}
+
+EXPORT void writePNG(const char*filename, unsigned char*data, int width, int height)
+{
+    savePNG(filename, data, width, height, 0);
+}
+EXPORT void writePalettePNG(const char*filename, unsigned char*data, int width, int height)
+{
+    savePNG(filename, data, width, height, 256);
 }