14de7f66b244bd346333e005c8ec66cbcbfc5116
[swftools.git] / lib / png.c
1 /*  png.c
2    
3    Copyright (c) 2003/2004/2005 Matthias Kramm <kramm@quiss.org>
4
5    This program is free software; you can redistribute it and/or modify
6    it under the terms of the GNU General Public License as published by
7    the Free Software Foundation; either version 2 of the License, or
8    (at your option) any later version.
9
10    This program is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13    GNU General Public License for more details.
14
15    You should have received a copy of the GNU General Public License
16    along with this program; if not, write to the Free Software
17    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
18
19 #include <stdio.h>
20 #include <stdlib.h>
21 #include <string.h>
22 #include <assert.h>
23 #include <math.h>
24 #include <fcntl.h>
25 #include <zlib.h>
26 #include <limits.h>
27
28 #ifdef EXPORT
29 #undef EXPORT
30 #endif
31
32 #ifdef PNG_INLINE_EXPORTS
33 #define EXPORT static
34 #else
35 #define EXPORT
36 #include "png.h"
37 #endif
38
39 typedef unsigned u32;
40
41 typedef struct _COL {
42     unsigned char a,r,g,b;
43 } COL;
44
45 static int png_read_chunk(char (*head)[4], int*destlen, unsigned char**destdata, FILE*fi)
46 {
47     unsigned int len;
48     unsigned char blen[4];
49     if(destlen) *destlen=0;
50     if(destdata) *destdata=0;
51     if(!fread(&blen, 4, 1, fi)) {
52         return 0;
53     }
54     if(!fread(head, 4, 1, fi)) {
55         return 0;
56     }
57     len = blen[0]<<24|blen[1]<<16|blen[2]<<8|blen[3];
58     if(destlen) *destlen = len;
59     if(destdata) {
60         if(!len) {
61             *destdata = 0;
62         } else {
63             *destdata = (unsigned char*)malloc(len);
64             if(!fread(*destdata, len, 1, fi)) {
65                 *destdata = 0;
66                 if(destlen) *destlen=0;
67                 return 0;
68             }
69         }
70         fseek(fi, 4, SEEK_CUR);
71
72     } else {
73         fseek(fi, len+4, SEEK_CUR);
74     }
75     return 1;
76 }
77
78 static unsigned int png_get_dword(FILE*fi)
79 {
80     unsigned int a;
81     unsigned char b[4];
82     fread(&b,4,1,fi);
83     return b[0]<<24|b[1]<<16|b[2]<<8|b[3];
84 }
85
86 struct png_header
87 {
88     int width;
89     int height;
90     int bpp;
91     int mode;
92 };
93
94 static int png_read_header(FILE*fi, struct png_header*header)
95 {
96     char id[4];
97     int len;
98     int ok=0;
99     unsigned char head[8] = {137,80,78,71,13,10,26,10};
100     unsigned char head2[8];
101     unsigned char*data;
102     fread(head2,8,1,fi);
103     if(strncmp((const char*)head,(const char*)head2,4))
104         return 0; // not a png file
105     
106     while(png_read_chunk(&id, &len, &data, fi))
107     {
108         //printf("Chunk: %c%c%c%c (len:%d)\n", id[0],id[1],id[2],id[3], len);
109         if(!strncmp(id, "IHDR", 4)) {
110             char a,b,c,f,i;
111             if(len < 8) exit(1);
112             header->width = data[0]<<24|data[1]<<16|data[2]<<8|data[3];
113             header->height = data[4]<<24|data[5]<<16|data[6]<<8|data[7];
114             a = data[8];      // should be 8
115             b = data[9];      // should be 3(indexed) or 2(rgb)
116
117             c = data[10];     // compression mode (0)
118             f = data[11];     // filter mode (0)
119             i = data[12];     // interlace mode (0)
120
121             if(b!=0 && b!=4 && b!=2 && b!=3 && b!=6) {
122                 fprintf(stderr, "Image mode %d not supported!\n", b);
123                 return 0;
124             }
125             if(a!=8 && (b==2 || b==6)) {
126                 printf("Bpp %d in mode %d not supported!\n", b, a);
127                 return 0;
128             }
129             if(c!=0) {
130                 printf("Compression mode %d not supported!\n", c);
131                 return 0;
132             }
133             if(f!=0) {
134                 printf("Filter mode %d not supported!\n", f);
135                 return 0;
136             }
137             if(i!=0) {
138                 printf("Interlace mode %d not supported!\n", i);
139                 return 0;
140             }
141             //printf("%dx%d bpp:%d mode:%d comp:%d filter:%d interlace:%d\n",header->width, header->height, a,b,c,f,i);
142             header->bpp = a;
143             header->mode = b;
144             ok = 1;
145         } 
146         
147         free(data);
148     }
149     return ok;
150 }
151
152 typedef unsigned char byte;
153 #define ABS(a) ((a)>0?(a):(-(a)))
154 static inline byte PaethPredictor (byte a,byte b,byte c)
155 {
156         // a = left, b = above, c = upper left
157         int p = a + b - c;        // initial estimate
158         int pa = ABS(p - a);      // distances to a, b, c
159         int pb = ABS(p - b);
160         int pc = ABS(p - c);
161         // return nearest of a,b,c,
162         // breaking ties in order a,b,c.
163         if (pa <= pb && pa <= pc) 
164                 return a;
165         else if (pb <= pc) 
166                 return b;
167         else return c;
168 }
169
170 static void applyfilter1(int mode, unsigned char*src, unsigned char*old, unsigned char*dest, int width)
171 {
172     int x;
173     unsigned char last=0;
174     unsigned char upperlast=0;
175
176     if(mode==0) {
177         for(x=0;x<width;x++) {
178             *dest = *src;
179             dest++;
180             src++;
181         }
182     }
183     else if(mode==1) {
184         for(x=0;x<width;x++) {
185             *dest = *src+last;
186             last = *dest;
187             dest++;
188             src++;
189         }
190     }
191     else if(mode==2) {
192         for(x=0;x<width;x++) {
193             *dest = *src+*old;
194             dest++;
195             old++;
196             src++;
197         }
198     }
199     else if(mode==3) {
200         for(x=0;x<width;x++) {
201             *dest = *src+(*old+last)/2;
202             last = *dest;
203             dest++;
204             old++;
205             src++;
206         }
207     }
208     else if(mode==4) {
209         for(x=0;x<width;x++) {
210             *dest = *src+PaethPredictor(last,*old,upperlast);
211             last = *dest;
212             upperlast = *old;
213             dest++;
214             old++;
215             src++;
216         }
217     }    
218
219 }
220
221 static void applyfilter2(int mode, unsigned char*src, unsigned char*old, unsigned char*dest, int width)
222 {
223     int x;
224     unsigned char lasta=0;
225     unsigned char lastb=0;
226     unsigned char upperlasta=0;
227     unsigned char upperlastb=0;
228
229     if(mode==0) {
230         for(x=0;x<width;x++) {
231             dest[0] = src[0];
232             dest[1] = src[1];
233             dest+=2;
234             src+=2;
235         }
236     }
237     else if(mode==1) {
238         for(x=0;x<width;x++) {
239             dest[0] = src[0]+lasta;
240             dest[1] = src[1]+lastb;
241             lasta = dest[0];
242             lastb = dest[1];
243             dest+=2;
244             src+=2;
245         }
246     }
247     else if(mode==2) {
248         for(x=0;x<width;x++) {
249             dest[0] = src[0]+old[0];
250             dest[1] = src[1]+old[1];
251             dest+=2;
252             old+=2;
253             src+=2;
254         }
255     }
256     else if(mode==3) {
257         for(x=0;x<width;x++) {
258             dest[0] = src[0]+(old[0]+lasta)/2;
259             dest[1] = src[1]+(old[1]+lastb)/2;
260             lasta = dest[0];
261             lastb = dest[1];
262             dest+=2;
263             old+=2;
264             src+=2;
265         }
266     }
267     else if(mode==4) {
268         for(x=0;x<width;x++) {
269             dest[0] = src[0]+PaethPredictor(lasta,old[0],upperlasta);
270             dest[1] = src[1]+PaethPredictor(lastb,old[1],upperlastb);
271             lasta = dest[0];
272             lastb = dest[1];
273             upperlasta = old[0];
274             upperlastb = old[1];
275             dest+=2;
276             old+=2;
277             src+=2;
278         }
279     }    
280 }
281
282
283 /* also performs 24 bit conversion! */
284 static void applyfilter3(int mode, unsigned char*src, unsigned char*old, unsigned char*dest, int width)
285 {
286     int x;
287     unsigned char lastr=0;
288     unsigned char lastg=0;
289     unsigned char lastb=0;
290     unsigned char upperlastr=0;
291     unsigned char upperlastg=0;
292     unsigned char upperlastb=0;
293
294     if(mode==0) {
295         for(x=0;x<width;x++) {
296             dest[0] = 255;
297             dest[1] = src[0];
298             dest[2] = src[1];
299             dest[3] = src[2];
300             dest+=4;
301             src+=3;
302         }
303     }
304     else if(mode==1) {
305         for(x=0;x<width;x++) {
306             dest[0] = 255;
307             dest[1] = src[0]+lastr;
308             dest[2] = src[1]+lastg;
309             dest[3] = src[2]+lastb;
310             lastr = dest[1];
311             lastg = dest[2];
312             lastb = dest[3];
313             dest+=4;
314             src+=3;
315         }
316     }
317     else if(mode==2) {
318         for(x=0;x<width;x++) {
319             dest[0] = 255;
320             dest[1] = src[0]+old[1];
321             dest[2] = src[1]+old[2];
322             dest[3] = src[2]+old[3];
323             dest+=4;
324             old+=4;
325             src+=3;
326         }
327     }
328     else if(mode==3) {
329         for(x=0;x<width;x++) {
330             dest[0] = 255;
331             dest[1] = src[0]+(old[1]+lastr)/2;
332             dest[2] = src[1]+(old[2]+lastg)/2;
333             dest[3] = src[2]+(old[3]+lastb)/2;
334             lastr = dest[1];
335             lastg = dest[2];
336             lastb = dest[3];
337             dest+=4;
338             old+=4;
339             src+=3;
340         }
341     }
342     else if(mode==4) {
343         for(x=0;x<width;x++) {
344             dest[0] = 255;
345             dest[1] = src[0]+PaethPredictor(lastr,old[1],upperlastr);
346             dest[2] = src[1]+PaethPredictor(lastg,old[2],upperlastg);
347             dest[3] = src[2]+PaethPredictor(lastb,old[3],upperlastb);
348             lastr = dest[1];
349             lastg = dest[2];
350             lastb = dest[3];
351             upperlastr = old[1];
352             upperlastg = old[2];
353             upperlastb = old[3];
354             dest+=4;
355             old+=4;
356             src+=3;
357         }
358     }    
359 }
360
361 void png_inverse_filter_32(int mode, unsigned char*src, unsigned char*old, unsigned char*dest, int width)
362 {
363     int x;
364     unsigned char lastr=0;
365     unsigned char lastg=0;
366     unsigned char lastb=0;
367     unsigned char lasta=0;
368     unsigned char upperlastr=0;
369     unsigned char upperlastg=0;
370     unsigned char upperlastb=0;
371     unsigned char upperlasta=0;
372
373     if(mode==0) {
374         for(x=0;x<width;x++) {
375             dest[0] = src[3];
376             dest[1] = src[0];
377             dest[2] = src[1];
378             dest[3] = src[2];
379             dest+=4;
380             src+=4;
381         }
382     }
383     else if(mode==1) {
384         for(x=0;x<width;x++) {
385             dest[0] = src[3]+lasta;
386             dest[1] = src[0]+lastr;
387             dest[2] = src[1]+lastg;
388             dest[3] = src[2]+lastb;
389             lasta = dest[0];
390             lastr = dest[1];
391             lastg = dest[2];
392             lastb = dest[3];
393             dest+=4;
394             src+=4;
395         }
396     }
397     else if(mode==2) {
398         for(x=0;x<width;x++) {
399             dest[0] = src[3]+old[0];
400             dest[1] = src[0]+old[1];
401             dest[2] = src[1]+old[2];
402             dest[3] = src[2]+old[3];
403             dest+=4;
404             old+=4;
405             src+=4;
406         }
407     }
408     else if(mode==3) {
409         for(x=0;x<width;x++) {
410             dest[0] = src[3]+(old[0]+lasta)/2;
411             dest[1] = src[0]+(old[1]+lastr)/2;
412             dest[2] = src[1]+(old[2]+lastg)/2;
413             dest[3] = src[2]+(old[3]+lastb)/2;
414             lasta = dest[0];
415             lastr = dest[1];
416             lastg = dest[2];
417             lastb = dest[3];
418             dest+=4;
419             old+=4;
420             src+=4;
421         }
422     }
423     else if(mode==4) {
424         for(x=0;x<width;x++) {
425             dest[0] = src[3]+PaethPredictor(lasta,old[0],upperlasta);
426             dest[1] = src[0]+PaethPredictor(lastr,old[1],upperlastr);
427             dest[2] = src[1]+PaethPredictor(lastg,old[2],upperlastg);
428             dest[3] = src[2]+PaethPredictor(lastb,old[3],upperlastb);
429             lasta = dest[0];
430             lastr = dest[1];
431             lastg = dest[2];
432             lastb = dest[3];
433             upperlasta = old[0];
434             upperlastr = old[1];
435             upperlastg = old[2];
436             upperlastb = old[3];
437             dest+=4;
438             old+=4;
439             src+=4;
440         }
441     }    
442 }
443
444 EXPORT int getPNGdimensions(const char*sname, int*destwidth, int*destheight)
445 {
446     FILE*fi;
447     struct png_header header;
448     if ((fi = fopen(sname, "rb")) == NULL) {
449         fprintf(stderr, "Couldn't open %s\n", sname);
450         return 0;
451     }
452     if(!png_read_header(fi, &header)) {
453         return 0;
454     }
455
456     *destwidth = header.width;
457     *destheight = header.height;
458     fclose(fi);
459     return 1;
460 }
461
462 EXPORT int getPNG(const char*sname, int*destwidth, int*destheight, unsigned char**destdata)
463 {
464     char tagid[4];
465     int len;
466     unsigned char*data;
467     unsigned char*imagedata;
468     unsigned char*zimagedata=0;
469     unsigned long int imagedatalen;
470     unsigned long int zimagedatalen=0;
471     unsigned char*palette = 0;
472     int palettelen = 0;
473     unsigned char*alphapalette = 0;
474     int alphapalettelen = 0;
475     struct png_header header;
476     int bypp;
477     unsigned char*data2 = 0;
478     unsigned char alphacolor[3];
479     int hasalphacolor=0;
480
481     FILE *fi;
482     unsigned char *scanline;
483
484     if ((fi = fopen(sname, "rb")) == NULL) {
485         printf("Couldn't open %s\n", sname);
486         return 0;
487     }
488
489     if(!png_read_header(fi, &header)) {
490         fclose(fi);
491         return 0;
492     }
493
494     if(header.mode == 3 || header.mode == 0) bypp = 1;
495     else if(header.mode == 4) bypp = 2;
496     else if(header.mode == 2) bypp = 3;
497     else if(header.mode == 6) bypp = 4;
498     else {
499         printf("ERROR: mode:%d\n", header.mode);
500         return 0;
501     }
502
503     imagedatalen = bypp * header.width * header.height + 65536;
504     imagedata = (unsigned char*)malloc(imagedatalen);
505
506     fseek(fi,8,SEEK_SET);
507     while(!feof(fi))
508     {
509         if(!png_read_chunk(&tagid, &len, &data, fi))
510             break;
511         if(!strncmp(tagid, "IEND", 4)) {
512             break;
513         }
514         if(!strncmp(tagid, "PLTE", 4)) {
515             palette = data;
516             palettelen = len/3;
517             data = 0; //don't free data
518             //printf("%d colors in palette\n", palettelen);
519         }
520         if(!strncmp(tagid, "tRNS", 4)) {
521             if(header.mode == 3) {
522                 alphapalette = data;
523                 alphapalettelen = len;
524                 data = 0; //don't free data
525                 //printf("found %d alpha colors\n", alphapalettelen);
526             } else if(header.mode == 0 || header.mode == 2) {
527                 int t;
528                 if(header.mode == 2) {
529                     alphacolor[0] = data[1];
530                     alphacolor[1] = data[3];
531                     alphacolor[2] = data[5];
532                 } else {
533                     alphacolor[0] = alphacolor[1] = alphacolor[2] = data[1];
534                 }
535                 hasalphacolor = 1;
536             }
537         }
538         if(!strncmp(tagid, "IDAT", 4)) {
539             if(!zimagedata) {
540                 zimagedatalen = len;
541                 zimagedata = (unsigned char*)malloc(len);
542                 memcpy(zimagedata,data,len);
543             } else {
544                 zimagedata = (unsigned char*)realloc(zimagedata, zimagedatalen+len);
545                 memcpy(&zimagedata[zimagedatalen], data, len);
546                 zimagedatalen += len;
547             }
548         }
549         if(!strncmp(tagid, "tEXt", 4)) {
550             /*int t;
551             printf("Image Text: ");
552             for(t=0;t<len;t++) {
553                 if(data[t]>=32 && data[t]<128)
554                     printf("%c", data[t]);
555                 else
556                     printf("?");
557             }
558             printf("\n");*/
559         }
560         if(data) {
561             free(data); data=0;
562         }
563     }
564     
565     fclose(fi);
566     if(!zimagedata || uncompress(imagedata, &imagedatalen, zimagedata, zimagedatalen) != Z_OK) {
567         printf("Couldn't uncompress %s!\n", sname);
568         if(zimagedata)
569             free(zimagedata);
570         return 0;
571     }
572     free(zimagedata);
573
574     *destwidth = header.width;
575     *destheight = header.height;
576         
577     data2 = (unsigned char*)malloc(header.width*header.height*4);
578
579     if(header.mode == 4)
580     {
581         int i,s=0;
582         int x,y;
583         int pos=0;
584         unsigned char* old= (unsigned char*)malloc(header.width*2);
585         memset(old, 0, header.width*2);
586         *destdata = data2;
587         for(y=0;y<header.height;y++) {
588             int mode = imagedata[pos++]; //filter mode
589             unsigned char*src;
590             unsigned char*dest;
591             int x;
592             dest = &data2[(y*header.width)*4];
593
594             if(header.bpp == 8) {
595                 /* one byte per pixel */
596                 src = &imagedata[pos];
597                 pos+=header.width*2;
598             } else {
599                 /* not implemented yet */
600                 fprintf(stderr, "ERROR: mode=4 bpp:%d\n", header.bpp);
601                 free(data2);
602                 return 0;
603             }
604
605             applyfilter2(mode, src, old, dest, header.width);
606             memcpy(old, dest, header.width*2);
607
608             for(x=header.width-1;x>=0;x--) {
609                 unsigned char gray = dest[x*2+0];
610                 unsigned char alpha = dest[x*2+1];
611                 dest[x*4+0] = alpha;
612                 dest[x*4+1] = gray;
613                 dest[x*4+2] = gray;
614                 dest[x*4+3] = gray;
615             }
616         }
617         free(old);
618         free(imagedata);
619     } else if(header.mode == 6 || header.mode == 2) {
620         int i,s=0;
621         int x,y;
622         int pos=0;
623         *destdata = data2;
624         
625         unsigned char* firstline = malloc(header.width*4);
626         memset(firstline,0,header.width*4);
627         for(y=0;y<header.height;y++) {
628             int mode = imagedata[pos++]; //filter mode
629             unsigned char*src;
630             unsigned char*dest;
631             unsigned char*old;
632             dest = &data2[(y*header.width)*4];
633
634             if(header.bpp == 8)
635             {
636                 /* one byte per pixel */
637                 src = &imagedata[pos];
638                 pos+=header.width*(header.mode==6?4:3);
639             } else {
640                 /* not implemented yet */
641                 fprintf(stderr, "ERROR: bpp:%d\n", header.bpp);
642                 free(data2);
643                 return 0;
644             }
645
646             if(!y) {
647                 old = firstline;
648             } else {
649                 old = &data2[(y-1)*header.width*4];
650             }
651             if(header.mode == 6) { 
652                 png_inverse_filter_32(mode, src, old, dest, header.width);
653             } else { // header.mode = 2
654                 applyfilter3(mode, src, old, dest, header.width);
655                 /* replace alpha color */
656                 if(hasalphacolor) {
657                     int x;
658                     for(x=0;x<header.width;x++) {
659                         if(dest[x*4+1] == alphacolor[0] &&
660                            dest[x*4+2] == alphacolor[1] &&
661                            dest[x*4+3] == alphacolor[2]) {
662                             *(u32*)&dest[x*4] = 0;
663                         }
664                     }
665                 }
666             }
667         }
668         free(firstline);
669         free(imagedata);
670     } else if(header.mode == 0 || header.mode == 3) {
671         COL*rgba = 0;
672         unsigned char*tmpline = (unsigned char*)malloc(header.width+1);
673         unsigned char*destline = (unsigned char*)malloc(header.width+1);
674         int i,x,y;
675         int pos=0;
676         
677         *destdata = data2;
678         
679         if(header.mode == 0) { // grayscale palette
680             int mult = (0x1ff>>header.bpp);
681             palettelen = 1<<header.bpp;
682             rgba = (COL*)malloc(palettelen*sizeof(COL));
683             for(i=0;i<palettelen;i++) {
684                 rgba[i].a = 255;
685                 rgba[i].r = i*mult;
686                 rgba[i].g = i*mult;
687                 rgba[i].b = i*mult;
688                 if(hasalphacolor) {
689                     if(rgba[i].r == alphacolor[0])
690                         rgba[i].a = 0;
691                 }
692             }
693         } else {
694             if(!palette) {
695                 fprintf(stderr, "Error: No palette found!\n");
696                 exit(1);
697             }
698             rgba = (COL*)malloc(palettelen*4);
699             /* 24->32 bit conversion */
700             for(i=0;i<palettelen;i++) {
701                 rgba[i].r = palette[i*3+0];
702                 rgba[i].g = palette[i*3+1];
703                 rgba[i].b = palette[i*3+2];
704                 if(alphapalette && i<alphapalettelen) {
705                     rgba[i].a = alphapalette[i];
706                     /*rgba[i].r = ((int)rgba[i].r*rgba[i].a)/255;
707                     rgba[i].g = ((int)rgba[i].g*rgba[i].a)/255;
708                     rgba[i].b = ((int)rgba[i].b*rgba[i].a)/255;*/
709                 } else {
710                     rgba[i].a = 255;
711                 }
712                 if(hasalphacolor) {
713                     if(rgba[i].r == alphacolor[0] &&
714                        rgba[i].g == alphacolor[1] &&
715                        rgba[i].b == alphacolor[2])
716                         rgba[i].a = 0;
717                 }
718             }
719         }
720
721         for(y=0;y<header.height;y++) {
722             int mode = imagedata[pos++]; //filter mode
723             int x;
724             unsigned char*old;
725             unsigned char*src;
726             src = &imagedata[pos];
727             if(header.bpp == 8) {
728                 pos+=header.width;
729             } else {
730                 int x,s=0;
731                 int bitpos = 0;
732                 u32 v = (1<<header.bpp)-1;
733                 for(x=0;x<header.width;x++) {
734                     u32 r = src[s/8]<<8 | 
735                             src[s/8+1];
736                     int t;
737                     tmpline[x] = (r>>(16-header.bpp-(s&7)))&v;
738                     s+=header.bpp;
739                 }
740                 src = tmpline;
741                 pos+=(header.width*header.bpp+7)/8;
742             }
743
744             if(!y) {
745                 memset(destline,0,header.width);
746                 old = &destline[y*header.width];
747             } else {
748                 old = tmpline;
749             }
750             applyfilter1(mode, src, old, destline, header.width);
751             memcpy(tmpline,destline,header.width);
752             for(x=0;x<header.width;x++) {
753                 *(COL*)&data2[y*header.width*4+x*4+0] = rgba[destline[x]];
754             }
755         }
756         free(tmpline);
757         free(destline);
758         free(rgba);
759         free(imagedata);
760     } else {
761         printf("expected PNG mode to be 2, 3 or 6 (is:%d)\n", header.mode);
762         return 0;
763     }
764
765     return 1;
766 }
767
768 static char hasAlpha(unsigned char*_image, int size)
769 {
770     COL*image = (COL*)_image;
771     int t;
772     for(t=0;t<size;t++) {
773         if(image[t].a!=255)
774             return 1;
775     }
776     return 0;
777 }
778
779 typedef struct {
780     u32 num;
781     u32 color;
782 } colornum_t;
783
784 static int compare_colors(const void*_c1, const void*_c2) {
785     colornum_t*c1 = (colornum_t*)_c1;
786     colornum_t*c2 = (colornum_t*)_c2;
787     return c2->num - c1->num;
788 }
789
790 static colornum_t* getColors(COL*image, int size, int*num)
791 {
792     unsigned char*colexists = malloc((256*256*256)/8);
793     memset(colexists, 0, (256*256*256)/8);
794     int t;
795     int count=0;
796
797     /* find all different colors in the image */
798     for(t=0;t<size;t++) {
799         int index = (image[t].r)|(image[t].g)<<8|(image[t].b)<<16;
800         if(!(colexists[index/8]&(1<<(index&7)))) {
801             count++;
802             colexists[index/8]|=(1<<(index&7));
803         }
804     }
805     
806     /* now store them in an array */
807     colornum_t*colors=(colornum_t*)malloc(sizeof(colornum_t)*count);
808     int pos=0;
809     for(t=0;t<256*256*256;t++) {
810         if(colexists[t/8]&(1<<(t&7))) {
811             colors[pos].color = t;
812             colors[pos].num = 0;
813             pos++;
814         }
815     }
816
817     /* next, count how often each color occurs */
818     for(t=0;t<size;t++) {
819         int col = (image[t].r)|(image[t].g)<<8|(image[t].b)<<16;
820         int min,max,i,l;
821         for(min=0, max=count, i=count/2, l=count; i != l; l=i,i=(min+max)/2) {
822             // binary search
823             if(colors[i].color >= col) max=i;
824             else min=i+1;
825         }
826         assert(colors[i].color==col);
827         colors[i].num++;
828     }
829     free(colexists);
830     *num = count;
831     return colors;
832 }
833
834 static void getOptimalPalette(COL*image, int size, int palettesize, COL*palette)
835 {
836     int num;
837     memset(palette, 0, sizeof(COL)*256);
838     colornum_t*colors = getColors(image, size, &num);
839
840     assert(palettesize<=256);
841
842     qsort(colors, num, sizeof(colornum_t), compare_colors);
843
844     if(num<=palettesize) {
845         /* if there are not more than palettesize different colors in 
846            the image anyway, we are done */
847         int t;
848         for(t=0;t<num;t++) {
849             palette[t].r = colors[t].color;
850             palette[t].g = colors[t].color>>8;
851             palette[t].b = colors[t].color>>16;
852             palette[t].a = 255;
853         }
854         return;
855     }
856
857     if(num>2048) {
858         /* if there are too many different colors, pick the ones that
859            occur most often */
860         num = 2048;
861     }
862
863     colornum_t*centers = malloc(sizeof(colornum_t)*palettesize);
864     int t;
865     for(t=0;t<palettesize;t++) {
866         centers[t].color = colors[t].color;
867     }
868     unsigned char*belongsto = (unsigned char*)malloc(num);
869     memset(belongsto, 0, num);
870     /* do a k-means clustering on the colors */
871     char change = 1;
872     int tries = 0;
873     while(change) {
874         if(tries++ >= (palettesize+num)*2) {
875             fprintf(stderr, "Warning: didn't find optimal palette\n");
876             break;
877         }
878         change = 0;
879         int s,t;
880         for(s=0;s<palettesize;s++) {
881             centers[s].num = 0;
882         }
883         for(t=0;t<num;t++) {
884             int best=0x7fffffff;
885             int bestpos=0;
886             for(s=0;s<palettesize;s++) {
887                 int distance = 0;
888                 distance += abs((centers[s].color>>0&0xff) - (colors[t].color>>0&0xff));
889                 distance += abs((centers[s].color>>8&0xff) - (colors[t].color>>8&0xff));
890                 distance += abs((centers[s].color>>16&0xff) - (colors[t].color>>16&0xff));
891                 distance *= colors[t].num;
892                 if(distance<best) {
893                     best = distance;
894                     bestpos = s;
895                 }
896             }
897             if(bestpos!=belongsto[t])
898                 change = 1;
899             belongsto[t] = bestpos;
900         }
901         for(s=0;s<palettesize;s++) {
902             int r=0;
903             int g=0;
904             int b=0;
905             int count=0;
906             for(t=0;t<num;t++) {
907                 if(belongsto[t]==s) {
908                     r += ((colors[t].color>>0)&0xff)*colors[t].num;
909                     g += ((colors[t].color>>8)&0xff)*colors[t].num;
910                     b += ((colors[t].color>>16)&0xff)*colors[t].num;
911                     count+=colors[t].num;
912                 }
913             }
914             if(!count) {
915                 int random = rand()%num;
916                 centers[s].color = colors[random].color;
917                 centers[s].num = 0;
918                 change = 1;
919             } else {
920                 r /= count;
921                 g /= count;
922                 b /= count;
923                 centers[s].color = r|g<<8|b<<16;
924                 centers[s].num = count;
925             }
926         }
927     }
928     free(belongsto);
929     free(colors);
930     for(t=0;t<palettesize;t++) {
931         palette[t].r = centers[t].color;
932         palette[t].g = centers[t].color>>8;
933         palette[t].b = centers[t].color>>16;
934         palette[t].a = 255;
935     }
936     free(centers);
937 }
938
939 static int sqr(const int x) {return x*x;}
940
941 static void png_quantize_image(unsigned char*_image, int size, int numcolors, unsigned char**newimage, COL*palette) 
942 {
943     COL*image = (COL*)_image;
944     getOptimalPalette(image, size, numcolors, palette);
945     *newimage = (unsigned char*)malloc(size);
946     int t;
947     for(t=0;t<size;t++) {
948         int best=0x7fffffff;
949         int bestcol = 0;
950         int s;
951         for(s=0;s<numcolors;s++) {
952             int distance = 0;
953             distance += sqr((palette[s].r) - (image[t].r))*5;
954             distance += sqr((palette[s].g) - (image[t].g))*6;
955             distance += sqr((palette[s].b) - (image[t].b))*4;
956             if(distance<best) {
957                 best = distance;
958                 bestcol = s;
959             }
960         }
961         (*newimage)[t] = bestcol;
962     }
963 }
964
965 static u32 mycrc32;
966
967 static u32*crc32_table = 0;
968 static void make_crc32_table(void)
969 {
970   int t;
971   if(crc32_table) 
972       return;
973   crc32_table = (u32*)malloc(1024);
974
975   for (t = 0; t < 256; t++) {
976     u32 c = t;
977     int s;
978     for (s = 0; s < 8; s++) {
979       c = (0xedb88320L*(c&1)) ^ (c >> 1);
980     }
981     crc32_table[t] = c;
982   }
983 }
984 static inline void png_write_byte(FILE*fi, unsigned char byte)
985 {
986     fwrite(&byte,1,1,fi);
987     mycrc32 = crc32_table[(mycrc32 ^ byte) & 0xff] ^ (mycrc32 >> 8);
988 }
989 static long png_start_chunk(FILE*fi, char*type, int len)
990 {
991     unsigned char mytype[4]={0,0,0,0};
992     unsigned char mylen[4];
993     long filepos;
994     mylen[0] = len>>24;
995     mylen[1] = len>>16;
996     mylen[2] = len>>8;
997     mylen[3] = len;
998     memcpy(mytype,type,strlen(type));
999     filepos = ftell(fi);
1000     fwrite(&mylen, 4, 1, fi);
1001     mycrc32=0xffffffff;
1002     png_write_byte(fi,mytype[0]);
1003     png_write_byte(fi,mytype[1]);
1004     png_write_byte(fi,mytype[2]);
1005     png_write_byte(fi,mytype[3]);
1006     return filepos;
1007 }
1008 static void png_patch_len(FILE*fi, int pos, int len)
1009 {
1010     unsigned char mylen[4];
1011     long filepos;
1012     mylen[0] = len>>24;
1013     mylen[1] = len>>16;
1014     mylen[2] = len>>8;
1015     mylen[3] = len;
1016     fseek(fi, pos, SEEK_SET);
1017     fwrite(&mylen, 4, 1, fi);
1018     fseek(fi, 0, SEEK_END);
1019 }
1020 static void png_write_bytes(FILE*fi, unsigned char*bytes, int len)
1021 {
1022     int t;
1023     for(t=0;t<len;t++)
1024         png_write_byte(fi,bytes[t]);
1025 }
1026 static void png_write_dword(FILE*fi, u32 dword)
1027 {
1028     png_write_byte(fi,dword>>24);
1029     png_write_byte(fi,dword>>16);
1030     png_write_byte(fi,dword>>8);
1031     png_write_byte(fi,dword);
1032 }
1033 static void png_end_chunk(FILE*fi)
1034 {
1035     u32 tmp = mycrc32^0xffffffff;
1036     unsigned char tmp2[4];
1037     tmp2[0] = tmp>>24;
1038     tmp2[1] = tmp>>16;
1039     tmp2[2] = tmp>>8;
1040     tmp2[3] = tmp;
1041     fwrite(&tmp2,4,1,fi);
1042 }
1043
1044 #define ZLIB_BUFFER_SIZE 16384
1045
1046 static long compress_line(z_stream*zs, Bytef*line, int len, FILE*fi)
1047 {
1048     long size = 0;
1049     zs->next_in = line;
1050     zs->avail_in = len;
1051
1052     while(1) {
1053         int ret = deflate(zs, Z_NO_FLUSH);
1054         if (ret != Z_OK) {
1055             fprintf(stderr, "error in deflate(): %s", zs->msg?zs->msg:"unknown");
1056             return 0;
1057         }
1058         if(zs->avail_out != ZLIB_BUFFER_SIZE) {
1059             int consumed = ZLIB_BUFFER_SIZE - zs->avail_out;
1060             size += consumed;
1061             png_write_bytes(fi, zs->next_out - consumed , consumed);
1062             zs->next_out = zs->next_out - consumed;
1063             zs->avail_out = ZLIB_BUFFER_SIZE;
1064         }
1065         if(!zs->avail_in) {
1066             break;
1067         }
1068     }
1069     return size;
1070 }
1071
1072 static int test_line(z_stream*zs_orig, Bytef*line, int linelen)
1073 {
1074     z_stream zs;
1075     int ret = deflateCopy(&zs, zs_orig);
1076     if(ret != Z_OK) {
1077         fprintf(stderr, "Couldn't copy stream\n");
1078         return 0;
1079     }
1080
1081     zs.next_in = line;
1082     zs.avail_in = linelen;
1083
1084     long size = 0;
1085
1086     int mode = Z_SYNC_FLUSH;
1087     while(1) {
1088         int ret = deflate(&zs, mode);
1089         if (ret != Z_OK && ret != Z_STREAM_END) {
1090             fprintf(stderr, "error in deflate(): %s (mode %s, %d bytes remaining)\n", zs.msg?zs.msg:"unknown", 
1091                     mode==Z_SYNC_FLUSH?"Z_SYNC_FLUSH":"Z_FINISH", zs.avail_in);
1092             return 0;
1093         }
1094         if(zs.avail_out != ZLIB_BUFFER_SIZE) {
1095             int consumed = ZLIB_BUFFER_SIZE - zs.avail_out;
1096             size += consumed;
1097             zs.next_out = zs.next_out - consumed;
1098             zs.avail_out = ZLIB_BUFFER_SIZE;
1099         }
1100         if (ret == Z_STREAM_END) {
1101             break;
1102         }
1103         if(!zs.avail_in) {
1104             mode = Z_FINISH;
1105         }
1106     }
1107     ret = deflateEnd(&zs);
1108     if (ret != Z_OK) {
1109         fprintf(stderr, "error in deflateEnd(): %s\n", zs.msg?zs.msg:"unknown");
1110         return 0;
1111     }
1112     return size;
1113 }
1114
1115 static int finishzlib(z_stream*zs, FILE*fi)
1116 {
1117     int size = 0;
1118     int ret;
1119     while(1) {
1120         ret = deflate(zs, Z_FINISH);
1121         if (ret != Z_OK &&
1122             ret != Z_STREAM_END) {
1123             fprintf(stderr, "error in deflate(finish): %s\n", zs->msg?zs->msg:"unknown");
1124             return 0;
1125         }
1126
1127         if(zs->avail_out != ZLIB_BUFFER_SIZE) {
1128             int consumed = ZLIB_BUFFER_SIZE - zs->avail_out;
1129             size += consumed;
1130             png_write_bytes(fi, zs->next_out - consumed , consumed);
1131             zs->next_out = zs->next_out - consumed;
1132             zs->avail_out = ZLIB_BUFFER_SIZE;
1133         }
1134         if (ret == Z_STREAM_END) {
1135             break;
1136         }
1137     }
1138     ret = deflateEnd(zs);
1139     if (ret != Z_OK) {
1140         fprintf(stderr, "error in deflateEnd(): %s\n", zs->msg?zs->msg:"unknown");
1141         return 0;
1142     }
1143     return size;
1144 }
1145
1146 static inline u32 color_hash(COL*col)
1147 {
1148     u32 col32 = *(u32*)col;
1149     u32 hash = (col32 >> 17) ^ col32;
1150     hash ^= ((hash>>8) + 1) ^ hash;
1151     return hash;
1152 }
1153
1154 static int png_get_number_of_palette_entries(COL*img, int width, int height, COL*palette, char*has_alpha)
1155 {
1156     int len = width*height;
1157     int t;
1158     int palsize = 0;
1159     int size[256];
1160     int palette_overflow = 0;
1161     u32 lastcol32 = 0;
1162     
1163     memset(size, 0, sizeof(size));
1164
1165     u32*pal = (u32*)malloc(65536*sizeof(u32));
1166     int*count = (int*)malloc(65536*sizeof(int));
1167
1168     assert(sizeof(COL)==sizeof(u32));
1169     assert(width && height);
1170
1171     lastcol32 = (*(u32*)&img[0])^0xffffffff; // don't match
1172
1173     for(t=0;t<len;t++) {
1174         u32 col32 = *(u32*)&img[t];
1175         if(col32 == lastcol32)
1176             continue;
1177         
1178         if(img[t].a!=255)
1179             *has_alpha=1;
1180         int i;
1181         
1182         u32 hash = color_hash(&img[t])&255;
1183
1184         int csize = size[hash];
1185         u32*cpal = &pal[hash*256];
1186         int*ccount = &count[hash*256];
1187         for(i=0;i<csize;i++) {
1188             if(col32 == cpal[i]) {
1189                 ccount[i]++;
1190                 break;
1191             }
1192         }
1193         if(i==csize) {
1194             if(palsize==256) {
1195                 palette_overflow = 1;
1196                 break;
1197             }
1198             count[size[hash]] = 1;
1199             cpal[size[hash]++] = col32;
1200             palsize++;
1201         }
1202         lastcol32 = col32;
1203     }
1204     if(palette_overflow) {
1205         free(pal);
1206         *has_alpha=1;
1207         return width*height;
1208     }
1209     if(palette) {
1210         int i = 0;
1211         int occurences[256];
1212         for(t=0;t<256;t++) {
1213             int s;
1214             int csize = size[t];
1215             u32* cpal = &pal[t*256];
1216             int* ccount = &count[t*256];
1217             for(s=0;s<csize;s++) {
1218                 occurences[i] = ccount[s];
1219                 palette[i++] = *(COL*)(&cpal[s]);
1220             }
1221         }
1222         assert(i==palsize);
1223         int j;
1224         for(i=0;i<palsize-1;i++) {
1225             for(j=i+1;j<palsize;j++) {
1226                 if(occurences[j] < occurences[i]) {
1227                     int o = occurences[i];
1228                     COL c = palette[i];
1229                     occurences[i] = occurences[j];
1230                     palette[i] = palette[j];
1231                     occurences[j] = o;
1232                     palette[j] = c;
1233                 }
1234             }
1235         }
1236     }
1237     free(pal);
1238     free(count);
1239     return palsize;
1240 }
1241
1242 static void png_map_to_palette(COL*src, unsigned char*dest, int size, COL*palette, int palette_size)
1243 {
1244     int t;
1245     int palette_hash[1024];
1246     memset(palette_hash, 0, sizeof(int)*1024);
1247     
1248     for(t=0;t<palette_size;t++) {
1249         u32 hash = color_hash(&palette[t])&1023;
1250         while(palette_hash[hash])
1251             hash = (hash+1)&1023;
1252         palette_hash[hash] = t;
1253     }
1254
1255     for(t=0;t<size;t++) {
1256         u32 hash = color_hash(&src[t]);
1257         int index = 0;
1258         while(1) {
1259             hash&=1023;
1260             index = palette_hash[hash];
1261             if(!memcmp(&palette[index], &src[t], sizeof(COL)))
1262                 break;
1263             hash++;
1264         }
1265         dest[t] = palette_hash[hash];
1266     }
1267 }
1268
1269 static int png_apply_specific_filter_8(int filtermode, unsigned char*dest, unsigned char*src, int width)
1270 {
1271     int pos2 = 0;
1272     int pos = 0;
1273     int srcwidth = width;
1274     int x;
1275     if(filtermode == 0) {
1276         for(x=0;x<width;x++) {
1277             dest[pos2++]=src[pos++]; //alpha
1278         }
1279     } else if(filtermode == 1) {
1280         /* x difference filter */
1281         dest[pos2++]=src[pos++];
1282         for(x=1;x<width;x++) {
1283             dest[pos2++]=src[pos] - src[pos-1];
1284             pos++;
1285         }
1286     } else if(filtermode == 2) {
1287         /* y difference filter */
1288         for(x=0;x<width;x++) {
1289             dest[pos2++]=src[pos+0] - src[pos-srcwidth+0]; //alpha
1290             pos++;
1291         }
1292     } else if(filtermode == 3) {
1293         dest[pos2++]=src[pos+0] - src[pos-srcwidth+0]/2;
1294         pos++;
1295         /* x+y difference filter */
1296         for(x=1;x<width;x++) {
1297             dest[pos2++]=src[pos+0] - (src[pos-1+0] + src[pos-srcwidth+0])/2; //alpha
1298             pos++;
1299         }
1300     } else if(filtermode == 4) {
1301         dest[pos2++]=src[pos+0] - PaethPredictor(0, src[pos-srcwidth+0], 0);
1302         pos++;
1303         /* paeth difference filter */
1304         for(x=1;x<width;x++) {
1305             dest[pos2++]=src[pos+0] - PaethPredictor(src[pos-1+0], src[pos-srcwidth+0], src[pos-1-srcwidth+0]);
1306             pos++;
1307         }
1308     }
1309     return filtermode;
1310 }
1311
1312 static int png_apply_specific_filter_32(int filtermode, unsigned char*dest, unsigned char*src, int width)
1313 {
1314     int pos2 = 0;
1315     int pos = 0;
1316     int srcwidth = width*4;
1317     int x;
1318     if(filtermode == 0) {
1319         for(x=0;x<width;x++) {
1320             dest[pos2++]=src[pos+1];
1321             dest[pos2++]=src[pos+2];
1322             dest[pos2++]=src[pos+3];
1323             dest[pos2++]=src[pos+0]; //alpha
1324             pos+=4;
1325         }
1326     } else if(filtermode == 1) {
1327         /* x difference filter */
1328         dest[pos2++]=src[pos+1];
1329         dest[pos2++]=src[pos+2];
1330         dest[pos2++]=src[pos+3];
1331         dest[pos2++]=src[pos+0];
1332         pos+=4;
1333         for(x=1;x<width;x++) {
1334             dest[pos2++]=src[pos+1] - src[pos-4+1];
1335             dest[pos2++]=src[pos+2] - src[pos-4+2];
1336             dest[pos2++]=src[pos+3] - src[pos-4+3];
1337             dest[pos2++]=src[pos+0] - src[pos-4+0]; //alpha
1338             pos+=4;
1339         }
1340     } else if(filtermode == 2) {
1341         /* y difference filter */
1342         for(x=0;x<width;x++) {
1343             dest[pos2++]=src[pos+1] - src[pos-srcwidth+1];
1344             dest[pos2++]=src[pos+2] - src[pos-srcwidth+2];
1345             dest[pos2++]=src[pos+3] - src[pos-srcwidth+3];
1346             dest[pos2++]=src[pos+0] - src[pos-srcwidth+0]; //alpha
1347             pos+=4;
1348         }
1349     } else if(filtermode == 3) {
1350         dest[pos2++]=src[pos+1] - src[pos-srcwidth+1]/2;
1351         dest[pos2++]=src[pos+2] - src[pos-srcwidth+2]/2;
1352         dest[pos2++]=src[pos+3] - src[pos-srcwidth+3]/2;
1353         dest[pos2++]=src[pos+0] - src[pos-srcwidth+0]/2;
1354         pos+=4;
1355         /* x+y difference filter */
1356         for(x=1;x<width;x++) {
1357             dest[pos2++]=src[pos+1] - (src[pos-4+1] + src[pos-srcwidth+1])/2;
1358             dest[pos2++]=src[pos+2] - (src[pos-4+2] + src[pos-srcwidth+2])/2;
1359             dest[pos2++]=src[pos+3] - (src[pos-4+3] + src[pos-srcwidth+3])/2;
1360             dest[pos2++]=src[pos+0] - (src[pos-4+0] + src[pos-srcwidth+0])/2; //alpha
1361             pos+=4;
1362         }
1363     } else if(filtermode == 4) {
1364         dest[pos2++]=src[pos+1] - PaethPredictor(0, src[pos-srcwidth+1], 0);
1365         dest[pos2++]=src[pos+2] - PaethPredictor(0, src[pos-srcwidth+2], 0);
1366         dest[pos2++]=src[pos+3] - PaethPredictor(0, src[pos-srcwidth+3], 0);
1367         dest[pos2++]=src[pos+0] - PaethPredictor(0, src[pos-srcwidth+0], 0);
1368         pos+=4;
1369         /* paeth difference filter */
1370         for(x=1;x<width;x++) {
1371             dest[pos2++]=src[pos+1] - PaethPredictor(src[pos-4+1], src[pos-srcwidth+1], src[pos-4-srcwidth+1]);
1372             dest[pos2++]=src[pos+2] - PaethPredictor(src[pos-4+2], src[pos-srcwidth+2], src[pos-4-srcwidth+2]);
1373             dest[pos2++]=src[pos+3] - PaethPredictor(src[pos-4+3], src[pos-srcwidth+3], src[pos-4-srcwidth+3]);
1374             dest[pos2++]=src[pos+0] - PaethPredictor(src[pos-4+0], src[pos-srcwidth+0], src[pos-4-srcwidth+0]);
1375             pos+=4;
1376         }
1377     }
1378     return filtermode;
1379 }
1380
1381 static int*num_bits_table = 0;
1382
1383 static void make_num_bits_table()
1384 {
1385     if(num_bits_table) return;
1386     num_bits_table = malloc(sizeof(num_bits_table[0])*256);
1387     int t;
1388     for(t=0;t<256;t++) {
1389         int bits=0;
1390         int v = t;
1391         while(v) {
1392             bits++;
1393             v&=v-1;
1394         }
1395         num_bits_table[t]=bits;
1396     }
1397 }
1398
1399 static int png_find_best_filter(unsigned char*src, int width, int bpp, int y)
1400 {
1401     make_num_bits_table();
1402     
1403     int num_filters = y>0?5:2; //don't apply y-direction filter in first line
1404
1405     int bytes_per_pixel = bpp>>3;
1406     int w = width*bytes_per_pixel;
1407     int back_x = bytes_per_pixel;
1408     int back_y = y?width*bytes_per_pixel:0;
1409
1410     unsigned char*pairs[5];
1411     pairs[0] = calloc(1, 8192);
1412     pairs[1] = calloc(1, 8192);
1413     pairs[2] = calloc(1, 8192);
1414     pairs[3] = calloc(1, 8192);
1415     pairs[4] = calloc(1, 8192);
1416     
1417     unsigned char old[5];
1418     int l = bytes_per_pixel - 1;
1419     old[0] = src[l];
1420     old[1] = src[l];
1421     old[2] = src[l] - src[l-back_y];
1422     old[3] = src[l] - src[l-back_y];
1423     old[4] = src[l] - PaethPredictor(0, src[l-back_y], 0);
1424
1425     int different_pairs[5] = {0,0,0,0,0};
1426
1427     int x;
1428     for(x=bytes_per_pixel;x<w;x++) {
1429         unsigned char dest[5];
1430         dest[0] = src[x];
1431         dest[1] = src[x] - src[x-back_x];
1432         dest[2] = src[x] - src[x-back_y];
1433         dest[3] = src[x] - (src[x-back_x] + src[x-back_y])/2;
1434         dest[4] = src[x] - PaethPredictor(src[x-back_x], src[x-back_y], src[x-back_x-back_y]);
1435
1436         int i;
1437         for(i=0;i<5;i++) {
1438             int v = dest[i]<<8|old[i];
1439             int p = v>>3;
1440             int b = 1<<(v&7);
1441             if(!pairs[i][p]&b) {
1442                 pairs[i][p]|=b;
1443                 different_pairs[i]++;
1444             }
1445         }
1446         memcpy(old, dest, sizeof(old));
1447     }
1448     int f;
1449     int best_nr = 0;
1450     int best_energy = INT_MAX;
1451     for(f=0;f<num_filters;f++) {
1452         int energy = different_pairs[f];
1453         if(energy<best_energy) {
1454             best_nr = f;
1455             best_energy = energy;
1456         }
1457     }
1458     free(pairs[0]);
1459     free(pairs[1]);
1460     free(pairs[2]);
1461     free(pairs[3]);
1462     free(pairs[4]);
1463     return best_nr;
1464 }
1465     
1466     
1467 static int png_apply_filter(unsigned char*dest, unsigned char*src, int width, int y, int bpp)
1468 {
1469     int best_nr = 0;
1470 #if 0
1471     make_num_bits_table();
1472     int num_filters = y>0?5:2; //don't apply y-direction filter in first line
1473     int f;
1474     int best_energy = INT_MAX;
1475     int w = width*(bpp/8);
1476     unsigned char* pairs = malloc(8192);
1477     assert(bpp==8 || bpp==32);
1478     for(f=0;f<num_filters;f++) {
1479         if(bpp==8)
1480             png_apply_specific_filter_8(f, dest, src, width);
1481         else
1482             png_apply_specific_filter_32(f, dest, src, width);
1483         int x;
1484
1485         /* approximation for zlib compressability: test how many different
1486            (byte1,byte2) occur */
1487         memset(pairs, 0, 8192);
1488         int different_pairs = 0;
1489         for(x=0;x<w-1;x++) {
1490             int v = dest[x+1]<<8|dest[x];
1491             int p = v>>3;
1492             int b = 1<<(v&7);
1493             if(!pairs[p]&b) {
1494                 pairs[p]|=b;
1495                 different_pairs ++;
1496             }
1497         }
1498         int energy = different_pairs;
1499         if(energy<best_energy) {
1500             best_nr = f;
1501             best_energy = energy;
1502         }
1503     }
1504     free(pairs);
1505 #else
1506     best_nr = png_find_best_filter(src, width, bpp, y);
1507 #endif
1508     if(bpp==8)
1509         png_apply_specific_filter_8(best_nr, dest, src, width);
1510     else
1511         png_apply_specific_filter_32(best_nr, dest, src, width);
1512     return best_nr;
1513 }
1514
1515 int png_apply_filter_8(unsigned char*dest, unsigned char*src, int width, int y)
1516 {
1517     return png_apply_filter(dest, src, width, y, 8);
1518 }
1519 int png_apply_filter_32(unsigned char*dest, unsigned char*src, int width, int y)
1520 {
1521     return png_apply_filter(dest, src, width, y, 32);
1522 }
1523
1524 EXPORT void savePNG(const char*filename, unsigned char*data, int width, int height, int numcolors)
1525 {
1526     FILE*fi;
1527     int crc;
1528     int t;
1529     unsigned char format;
1530     unsigned char tmp;
1531     unsigned char* data2=0;
1532     unsigned char head[] = {137,80,78,71,13,10,26,10}; // PNG header
1533     int cols;
1534     char alpha = 1;
1535     int pos = 0;
1536     int error;
1537     u32 tmp32;
1538     int bpp;
1539     int ret;
1540     char has_alpha=0;
1541     z_stream zs;
1542     COL palette[256];
1543
1544     make_crc32_table();
1545
1546     if(!numcolors) {
1547         int num = png_get_number_of_palette_entries((COL*)data, width, height, palette, &has_alpha);
1548         if(num<=255) {
1549             //printf("image has %d different colors (alpha=%d)\n", num, has_alpha);
1550             data2 = malloc(width*height);
1551             png_map_to_palette((COL*)data, data2, width*height, palette, num);
1552             data = data2;
1553             bpp = 8;
1554             cols = num;
1555             format = 3;
1556         } else {
1557             bpp = 32;
1558             cols = 0;
1559             format = 5;
1560         }
1561     } else {
1562         bpp = 8;
1563         cols = numcolors;
1564         format = 3;
1565         png_quantize_image(data, width*height, numcolors, &data, palette);
1566     }
1567
1568     fi = fopen(filename, "wb");
1569     if(!fi) {
1570         perror("open");
1571         return;
1572     }
1573     fwrite(head,sizeof(head),1,fi);     
1574
1575     png_start_chunk(fi, "IHDR", 13);
1576      png_write_dword(fi,width);
1577      png_write_dword(fi,height);
1578      png_write_byte(fi,8);
1579      if(format == 3)
1580      png_write_byte(fi,3); //indexed
1581      else if(format == 5 && alpha==0)
1582      png_write_byte(fi,2); //rgb
1583      else if(format == 5 && alpha==1)
1584      png_write_byte(fi,6); //rgba
1585      else return;
1586
1587      png_write_byte(fi,0); //compression mode
1588      png_write_byte(fi,0); //filter mode
1589      png_write_byte(fi,0); //interlace mode
1590     png_end_chunk(fi);
1591
1592     if(format == 3) {
1593         png_start_chunk(fi, "PLTE", cols*3);
1594         for(t=0;t<cols;t++) {
1595             png_write_byte(fi,palette[t].r);
1596             png_write_byte(fi,palette[t].g);
1597             png_write_byte(fi,palette[t].b);
1598         }
1599         png_end_chunk(fi);
1600
1601         if(has_alpha) {
1602             png_start_chunk(fi, "tRNS", cols);
1603             for(t=0;t<cols;t++) {
1604                 png_write_byte(fi,palette[t].a);
1605             }
1606             png_end_chunk(fi);
1607         }
1608     }
1609
1610     long idatpos = png_start_chunk(fi, "IDAT", 0);
1611     
1612     memset(&zs,0,sizeof(z_stream));
1613     Bytef*writebuf = (Bytef*)malloc(ZLIB_BUFFER_SIZE);
1614     zs.zalloc = Z_NULL;
1615     zs.zfree  = Z_NULL;
1616     zs.opaque = Z_NULL;
1617     zs.next_out = writebuf;
1618     zs.avail_out = ZLIB_BUFFER_SIZE;
1619     ret = deflateInit(&zs, Z_BEST_COMPRESSION);
1620     if (ret != Z_OK) {
1621         fprintf(stderr, "error in deflateInit(): %s", zs.msg?zs.msg:"unknown");
1622         return;
1623     }
1624
1625     long idatsize = 0;
1626     {
1627         int x,y;
1628         int bypp = bpp/8;
1629         int srcwidth = width * bypp;
1630         int linelen = 1 + srcwidth;
1631         if(bypp==2) 
1632             linelen = 1 + ((srcwidth+1)&~1);
1633         else if(bypp==3) 
1634             linelen = 1 + ((srcwidth+2)/3)*3;
1635         else if(bypp==4) 
1636             linelen = 1 + ((srcwidth+3)&~3);
1637         unsigned char* line = (unsigned char*)malloc(linelen);
1638         memset(line, 0, linelen);
1639 #if 0
1640         unsigned char* bestline = (unsigned char*)malloc(linelen);
1641         memset(bestline, 0, linelen);
1642         for(y=0;y<height;y++)
1643         {
1644             int filtermode;
1645             int bestsize = 0x7fffffff;
1646             for(filtermode=0;filtermode<=4;filtermode++) {
1647                 if(!y && filtermode>=2)
1648                     continue; // don't do y direction filters in the first row
1649                 
1650                 line[0]=filtermode; //filter type
1651                 if(bpp==8)
1652                     png_apply_specific_filter_8(filtermode, line+1, &data[y*srcwidth], width);
1653                 else
1654                     png_apply_specific_filter_32(filtermode, line+1, &data[y*srcwidth], width);
1655
1656                 int size = test_line(&zs, line, linelen);
1657                 if(size < bestsize) {
1658                     memcpy(bestline, line, linelen);
1659                     bestsize = size;
1660                 }
1661             }
1662             idatsize += compress_line(&zs, bestline, linelen, fi);
1663         }
1664         free(bestline);
1665 #else
1666         for(y=0;y<height;y++) {
1667             if(bpp==8)
1668                 line[0] = png_apply_filter_8(line+1, &data[y*srcwidth], width, y);
1669             else
1670                 line[0] = png_apply_filter_32(line+1, &data[y*srcwidth], width, y);
1671
1672             idatsize += compress_line(&zs, line, linelen, fi);
1673         }
1674 #endif
1675         free(line);
1676     }
1677     idatsize += finishzlib(&zs, fi);
1678     png_patch_len(fi, idatpos, idatsize);
1679     png_end_chunk(fi);
1680
1681     png_start_chunk(fi, "IEND", 0);
1682     png_end_chunk(fi);
1683
1684     free(writebuf);
1685     if(data2)
1686         free(data2);
1687     fclose(fi);
1688 }
1689
1690 EXPORT void writePNG(const char*filename, unsigned char*data, int width, int height)
1691 {
1692     savePNG(filename, data, width, height, 0);
1693 }
1694 EXPORT void writePalettePNG(const char*filename, unsigned char*data, int width, int height)
1695 {
1696     savePNG(filename, data, width, height, 256);
1697 }