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

diff --git a/lib/png.c b/lib/png.c
index 739b895..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,7 +101,7 @@ 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))
     {
@@ -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++;
@@ -448,7 +451,6 @@ EXPORT int getPNGdimensions(const 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;
     }
 
@@ -485,7 +487,7 @@ EXPORT int getPNG(const char*sname, int*destwidth, int*destheight, unsigned char
     }
 
     if(!png_read_header(fi, &header)) {
-	printf("Error reading header from file %s\n", sname);
+	fclose(fi);
 	return 0;
     }
 
@@ -763,6 +765,203 @@ EXPORT int getPNG(const char*sname, int*destwidth, int*destheight, unsigned char
     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;
@@ -944,7 +1143,173 @@ static int finishzlib(z_stream*zs, FILE*fi)
     return size;
 }
 
-static void filter_line(int filtermode, unsigned char*dest, unsigned char*src, int width)
+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;
@@ -1010,9 +1375,82 @@ static void filter_line(int filtermode, unsigned char*dest, unsigned char*src, i
 	    pos+=4;
 	}
     }
+    return filtermode;
 }
+    
+static int*num_bits_table = 0;
 
-EXPORT void writePNG(const char*filename, unsigned char*data, int width, int height)
+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;
@@ -1020,8 +1458,6 @@ EXPORT void writePNG(const char*filename, unsigned char*data, int width, int hei
     unsigned char format;
     unsigned char tmp;
     unsigned char* data2=0;
-    u32 datalen;
-    u32 datalen2;
     unsigned char head[] = {137,80,78,71,13,10,26,10}; // PNG header
     int cols;
     char alpha = 1;
@@ -1030,16 +1466,34 @@ EXPORT void writePNG(const char*filename, unsigned char*data, int width, int hei
     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");
@@ -1064,16 +1518,24 @@ EXPORT void writePNG(const char*filename, unsigned char*data, int width, int hei
      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));
@@ -1083,7 +1545,7 @@ EXPORT void writePNG(const char*filename, unsigned char*data, int width, int hei
     zs.opaque = Z_NULL;
     zs.next_out = writebuf;
     zs.avail_out = ZLIB_BUFFER_SIZE;
-    ret = deflateInit(&zs, 9);
+    ret = deflateInit(&zs, Z_BEST_COMPRESSION);
     if (ret != Z_OK) {
 	fprintf(stderr, "error in deflateInit(): %s", zs.msg?zs.msg:"unknown");
 	return;
@@ -1092,22 +1554,33 @@ EXPORT void writePNG(const char*filename, unsigned char*data, int width, int hei
     long idatsize = 0;
     {
 	int x,y;
-	int srcwidth = width * (bpp/8);
-	int linelen = 1 + ((srcwidth+3)&~3);
+        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);
-	unsigned char* bestline = (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<5;filtermode++) {
-
+	    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
-		filter_line(filtermode, line+1, &data[y*srcwidth], width);
+                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) {
@@ -1117,7 +1590,18 @@ EXPORT void writePNG(const char*filename, unsigned char*data, int width, int hei
 	    }
 	    idatsize += compress_line(&zs, bestline, linelen, fi);
 	}
-	free(line);free(bestline);
+	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);
@@ -1127,7 +1611,16 @@ EXPORT void writePNG(const char*filename, unsigned char*data, int width, int hei
     png_end_chunk(fi);
 
     free(writebuf);
-    free(data2);
+    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);
+}