3 Copyright (c) 2003/2004/2005 Matthias Kramm <kramm@quiss.org>
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.
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.
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 */
32 #ifdef PNG_INLINE_EXPORTS
42 unsigned char a,r,g,b;
45 static int png_read_chunk(char (*head)[4], int*destlen, unsigned char**destdata, FILE*fi)
48 unsigned char blen[4];
49 if(destlen) *destlen=0;
50 if(destdata) *destdata=0;
51 if(!fread(&blen, 4, 1, fi)) {
54 if(!fread(head, 4, 1, fi)) {
57 len = blen[0]<<24|blen[1]<<16|blen[2]<<8|blen[3];
58 if(destlen) *destlen = len;
63 *destdata = (unsigned char*)malloc(len);
64 if(!fread(*destdata, len, 1, fi)) {
66 if(destlen) *destlen=0;
70 fseek(fi, 4, SEEK_CUR);
73 fseek(fi, len+4, SEEK_CUR);
78 static unsigned int png_get_dword(FILE*fi)
83 return b[0]<<24|b[1]<<16|b[2]<<8|b[3];
94 static int png_read_header(FILE*fi, struct png_header*header)
99 unsigned char head[8] = {137,80,78,71,13,10,26,10};
100 unsigned char head2[8];
103 if(strncmp((const char*)head,(const char*)head2,4))
104 return 0; // not a png file
106 while(png_read_chunk(&id, &len, &data, fi))
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)) {
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)
117 c = data[10]; // compression mode (0)
118 f = data[11]; // filter mode (0)
119 i = data[12]; // interlace mode (0)
121 if(b!=0 && b!=4 && b!=2 && b!=3 && b!=6) {
122 fprintf(stderr, "Image mode %d not supported!\n", b);
125 if(a!=8 && (b==2 || b==6)) {
126 printf("Bpp %d in mode %d not supported!\n", b, a);
130 printf("Compression mode %d not supported!\n", c);
134 printf("Filter mode %d not supported!\n", f);
138 printf("Interlace mode %d not supported!\n", i);
141 //printf("%dx%d bpp:%d mode:%d comp:%d filter:%d interlace:%d\n",header->width, header->height, a,b,c,f,i);
152 typedef unsigned char byte;
153 #define ABS(a) ((a)>0?(a):(-(a)))
154 static inline byte PaethPredictor (byte a,byte b,byte c)
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
161 // return nearest of a,b,c,
162 // breaking ties in order a,b,c.
163 if (pa <= pb && pa <= pc)
170 static void applyfilter1(int mode, unsigned char*src, unsigned char*old, unsigned char*dest, unsigned width)
173 unsigned char last=0;
174 unsigned char upperlast=0;
177 for(x=0;x<width;x++) {
184 for(x=0;x<width;x++) {
192 for(x=0;x<width;x++) {
200 for(x=0;x<width;x++) {
201 *dest = *src+(*old+last)/2;
209 for(x=0;x<width;x++) {
210 *dest = *src+PaethPredictor(last,*old,upperlast);
221 static void applyfilter2(int mode, unsigned char*src, unsigned char*old, unsigned char*dest, unsigned width)
224 unsigned char lasta=0;
225 unsigned char lastb=0;
226 unsigned char upperlasta=0;
227 unsigned char upperlastb=0;
230 for(x=0;x<width;x++) {
238 for(x=0;x<width;x++) {
239 dest[0] = src[0]+lasta;
240 dest[1] = src[1]+lastb;
248 for(x=0;x<width;x++) {
249 dest[0] = src[0]+old[0];
250 dest[1] = src[1]+old[1];
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;
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);
283 /* also performs 24 bit conversion! */
284 static void applyfilter3(int mode, unsigned char*src, unsigned char*old, unsigned char*dest, unsigned width)
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;
295 for(x=0;x<width;x++) {
305 for(x=0;x<width;x++) {
307 dest[1] = src[0]+lastr;
308 dest[2] = src[1]+lastg;
309 dest[3] = src[2]+lastb;
318 for(x=0;x<width;x++) {
320 dest[1] = src[0]+old[1];
321 dest[2] = src[1]+old[2];
322 dest[3] = src[2]+old[3];
329 for(x=0;x<width;x++) {
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;
343 for(x=0;x<width;x++) {
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);
361 void png_inverse_filter_32(int mode, unsigned char*src, unsigned char*old, unsigned char*dest, unsigned width)
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;
374 for(x=0;x<width;x++) {
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;
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];
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;
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);
444 EXPORT int png_getdimensions(const char*sname, unsigned*destwidth, unsigned*destheight)
447 struct png_header header;
448 if ((fi = fopen(sname, "rb")) == NULL) {
449 fprintf(stderr, "Couldn't open %s\n", sname);
452 if(!png_read_header(fi, &header)) {
456 *destwidth = header.width;
457 *destheight = header.height;
462 EXPORT int png_load(const char*sname, unsigned*destwidth, unsigned*destheight, unsigned char**destdata)
467 unsigned char*imagedata;
468 unsigned char*zimagedata=0;
469 unsigned long int zimagedatalen=0;
470 unsigned char*palette = 0;
472 unsigned char*alphapalette = 0;
473 int alphapalettelen = 0;
474 struct png_header header;
476 unsigned char*data2 = 0;
477 unsigned char alphacolor[3];
481 unsigned char *scanline;
483 if ((fi = fopen(sname, "rb")) == NULL) {
484 printf("Couldn't open %s\n", sname);
488 if(!png_read_header(fi, &header)) {
493 if(header.mode == 3 || header.mode == 0) bypp = 1;
494 else if(header.mode == 4) bypp = 2;
495 else if(header.mode == 2) bypp = 3;
496 else if(header.mode == 6) bypp = 4;
498 printf("ERROR: mode:%d\n", header.mode);
502 unsigned long long imagedatalen_64 = ((unsigned long long)header.width + 1) * header.height * bypp;
503 if(imagedatalen_64 > 0xffffffff)
505 unsigned long imagedatalen = (unsigned long)imagedatalen_64;
506 imagedata = (unsigned char*)malloc(imagedatalen);
508 fseek(fi,8,SEEK_SET);
511 if(!png_read_chunk(&tagid, &len, &data, fi))
513 if(!strncmp(tagid, "IEND", 4)) {
516 if(!strncmp(tagid, "PLTE", 4)) {
519 data = 0; //don't free data
520 //printf("%d colors in palette\n", palettelen);
522 if(!strncmp(tagid, "tRNS", 4)) {
523 if(header.mode == 3) {
525 alphapalettelen = len;
526 data = 0; //don't free data
527 //printf("found %d alpha colors\n", alphapalettelen);
528 } else if(header.mode == 0 || header.mode == 2) {
530 if(header.mode == 2) {
531 alphacolor[0] = data[1];
532 alphacolor[1] = data[3];
533 alphacolor[2] = data[5];
535 alphacolor[0] = alphacolor[1] = alphacolor[2] = data[1];
540 if(!strncmp(tagid, "IDAT", 4)) {
543 zimagedata = (unsigned char*)malloc(len);
544 memcpy(zimagedata,data,len);
546 zimagedata = (unsigned char*)realloc(zimagedata, zimagedatalen+len);
547 memcpy(&zimagedata[zimagedatalen], data, len);
548 zimagedatalen += len;
551 if(!strncmp(tagid, "tEXt", 4)) {
553 printf("Image Text: ");
555 if(data[t]>=32 && data[t]<128)
556 printf("%c", data[t]);
568 if(!zimagedata || uncompress(imagedata, &imagedatalen, zimagedata, zimagedatalen) != Z_OK) {
569 printf("Couldn't uncompress %s!\n", sname);
576 *destwidth = header.width;
577 *destheight = header.height;
579 data2 = (unsigned char*)malloc(header.width*header.height*4);
586 unsigned char* old= (unsigned char*)malloc(header.width*2);
587 memset(old, 0, header.width*2);
589 for(y=0;y<header.height;y++) {
590 int mode = imagedata[pos++]; //filter mode
594 dest = &data2[(y*header.width)*4];
596 if(header.bpp == 8) {
597 /* one byte per pixel */
598 src = &imagedata[pos];
601 /* not implemented yet */
602 fprintf(stderr, "ERROR: mode=4 bpp:%d\n", header.bpp);
607 applyfilter2(mode, src, old, dest, header.width);
608 memcpy(old, dest, header.width*2);
610 for(x=header.width-1;x>=0;x--) {
611 unsigned char gray = dest[x*2+0];
612 unsigned char alpha = dest[x*2+1];
621 } else if(header.mode == 6 || header.mode == 2) {
627 unsigned char* firstline = malloc(header.width*4);
628 memset(firstline,0,header.width*4);
629 for(y=0;y<header.height;y++) {
630 int mode = imagedata[pos++]; //filter mode
634 dest = &data2[(y*header.width)*4];
638 /* one byte per pixel */
639 src = &imagedata[pos];
640 pos+=header.width*(header.mode==6?4:3);
642 /* not implemented yet */
643 fprintf(stderr, "ERROR: bpp:%d\n", header.bpp);
651 old = &data2[(y-1)*header.width*4];
653 if(header.mode == 6) {
654 png_inverse_filter_32(mode, src, old, dest, header.width);
655 } else { // header.mode = 2
656 applyfilter3(mode, src, old, dest, header.width);
657 /* replace alpha color */
660 for(x=0;x<header.width;x++) {
661 if(dest[x*4+1] == alphacolor[0] &&
662 dest[x*4+2] == alphacolor[1] &&
663 dest[x*4+3] == alphacolor[2]) {
664 *(u32*)&dest[x*4] = 0;
672 } else if(header.mode == 0 || header.mode == 3) {
674 unsigned char*tmpline = (unsigned char*)malloc(header.width+1);
675 unsigned char*destline = (unsigned char*)malloc(header.width+1);
681 if(header.mode == 0) { // grayscale palette
682 int mult = (0x1ff>>header.bpp);
683 palettelen = 1<<header.bpp;
684 rgba = (COL*)malloc(palettelen*sizeof(COL));
685 for(i=0;i<palettelen;i++) {
691 if(rgba[i].r == alphacolor[0])
697 fprintf(stderr, "Error: No palette found!\n");
700 rgba = (COL*)malloc(palettelen*4);
701 /* 24->32 bit conversion */
702 for(i=0;i<palettelen;i++) {
703 rgba[i].r = palette[i*3+0];
704 rgba[i].g = palette[i*3+1];
705 rgba[i].b = palette[i*3+2];
706 if(alphapalette && i<alphapalettelen) {
707 rgba[i].a = alphapalette[i];
708 /*rgba[i].r = ((int)rgba[i].r*rgba[i].a)/255;
709 rgba[i].g = ((int)rgba[i].g*rgba[i].a)/255;
710 rgba[i].b = ((int)rgba[i].b*rgba[i].a)/255;*/
715 if(rgba[i].r == alphacolor[0] &&
716 rgba[i].g == alphacolor[1] &&
717 rgba[i].b == alphacolor[2])
723 for(y=0;y<header.height;y++) {
724 int mode = imagedata[pos++]; //filter mode
728 src = &imagedata[pos];
729 if(header.bpp == 8) {
734 u32 v = (1<<header.bpp)-1;
735 for(x=0;x<header.width;x++) {
736 u32 r = src[s/8]<<8 |
739 tmpline[x] = (r>>(16-header.bpp-(s&7)))&v;
743 pos+=(header.width*header.bpp+7)/8;
747 memset(destline,0,header.width);
748 old = &destline[y*header.width];
752 applyfilter1(mode, src, old, destline, header.width);
753 memcpy(tmpline,destline,header.width);
754 for(x=0;x<header.width;x++) {
755 *(COL*)&data2[y*header.width*4+x*4+0] = rgba[destline[x]];
763 printf("expected PNG mode to be 2, 3 or 6 (is:%d)\n", header.mode);
770 static char hasAlpha(unsigned char*_image, int size)
772 COL*image = (COL*)_image;
774 for(t=0;t<size;t++) {
786 static int compare_colors(const void*_c1, const void*_c2) {
787 colornum_t*c1 = (colornum_t*)_c1;
788 colornum_t*c2 = (colornum_t*)_c2;
789 return c2->num - c1->num;
792 static colornum_t* getColors(COL*image, int size, int*num)
794 unsigned char*colexists = malloc((256*256*256)/8);
795 memset(colexists, 0, (256*256*256)/8);
799 /* find all different colors in the image */
800 for(t=0;t<size;t++) {
801 int index = (image[t].r)|(image[t].g)<<8|(image[t].b)<<16;
802 if(!(colexists[index/8]&(1<<(index&7)))) {
804 colexists[index/8]|=(1<<(index&7));
808 /* now store them in an array */
809 colornum_t*colors=(colornum_t*)malloc(sizeof(colornum_t)*count);
811 for(t=0;t<256*256*256;t++) {
812 if(colexists[t/8]&(1<<(t&7))) {
813 colors[pos].color = t;
819 /* next, count how often each color occurs */
820 for(t=0;t<size;t++) {
821 int col = (image[t].r)|(image[t].g)<<8|(image[t].b)<<16;
823 for(min=0, max=count, i=count/2, l=count; i != l; l=i,i=(min+max)/2) {
825 if(colors[i].color >= col) max=i;
828 assert(colors[i].color==col);
836 static void getOptimalPalette(COL*image, int size, int palettesize, COL*palette)
839 memset(palette, 0, sizeof(COL)*256);
840 colornum_t*colors = getColors(image, size, &num);
842 assert(palettesize<=256);
844 qsort(colors, num, sizeof(colornum_t), compare_colors);
846 if(num<=palettesize) {
847 /* if there are not more than palettesize different colors in
848 the image anyway, we are done */
851 palette[t].r = colors[t].color;
852 palette[t].g = colors[t].color>>8;
853 palette[t].b = colors[t].color>>16;
860 /* if there are too many different colors, pick the ones that
865 colornum_t*centers = malloc(sizeof(colornum_t)*palettesize);
867 for(t=0;t<palettesize;t++) {
868 centers[t].color = colors[t].color;
870 unsigned char*belongsto = (unsigned char*)malloc(num);
871 memset(belongsto, 0, num);
872 /* do a k-means clustering on the colors */
876 if(tries++ >= (palettesize+num)*2) {
877 fprintf(stderr, "Warning: didn't find optimal palette\n");
882 for(s=0;s<palettesize;s++) {
888 for(s=0;s<palettesize;s++) {
890 distance += abs((centers[s].color>>0&0xff) - (colors[t].color>>0&0xff));
891 distance += abs((centers[s].color>>8&0xff) - (colors[t].color>>8&0xff));
892 distance += abs((centers[s].color>>16&0xff) - (colors[t].color>>16&0xff));
893 distance *= colors[t].num;
899 if(bestpos!=belongsto[t])
901 belongsto[t] = bestpos;
903 for(s=0;s<palettesize;s++) {
909 if(belongsto[t]==s) {
910 r += ((colors[t].color>>0)&0xff)*colors[t].num;
911 g += ((colors[t].color>>8)&0xff)*colors[t].num;
912 b += ((colors[t].color>>16)&0xff)*colors[t].num;
913 count+=colors[t].num;
917 int random = rand()%num;
918 centers[s].color = colors[random].color;
925 centers[s].color = r|g<<8|b<<16;
926 centers[s].num = count;
932 for(t=0;t<palettesize;t++) {
933 palette[t].r = centers[t].color;
934 palette[t].g = centers[t].color>>8;
935 palette[t].b = centers[t].color>>16;
941 static int sqr(const int x) {return x*x;}
943 static void png_quantize_image(unsigned char*_image, int size, int numcolors, unsigned char**newimage, COL*palette)
945 COL*image = (COL*)_image;
946 getOptimalPalette(image, size, numcolors, palette);
947 *newimage = (unsigned char*)malloc(size);
949 for(t=0;t<size;t++) {
953 for(s=0;s<numcolors;s++) {
955 distance += sqr((palette[s].r) - (image[t].r))*5;
956 distance += sqr((palette[s].g) - (image[t].g))*6;
957 distance += sqr((palette[s].b) - (image[t].b))*4;
963 (*newimage)[t] = bestcol;
969 static u32*crc32_table = 0;
970 static void make_crc32_table(void)
975 crc32_table = (u32*)malloc(1024);
977 for (t = 0; t < 256; t++) {
980 for (s = 0; s < 8; s++) {
981 c = (0xedb88320L*(c&1)) ^ (c >> 1);
986 static inline void png_write_byte(FILE*fi, unsigned char byte)
988 fwrite(&byte,1,1,fi);
989 mycrc32 = crc32_table[(mycrc32 ^ byte) & 0xff] ^ (mycrc32 >> 8);
991 static long png_start_chunk(FILE*fi, char*type, int len)
993 unsigned char mytype[4]={0,0,0,0};
994 unsigned char mylen[4];
1000 memcpy(mytype,type,strlen(type));
1001 filepos = ftell(fi);
1002 fwrite(&mylen, 4, 1, fi);
1004 png_write_byte(fi,mytype[0]);
1005 png_write_byte(fi,mytype[1]);
1006 png_write_byte(fi,mytype[2]);
1007 png_write_byte(fi,mytype[3]);
1010 static void png_patch_len(FILE*fi, int pos, int len)
1012 unsigned char mylen[4];
1018 fseek(fi, pos, SEEK_SET);
1019 fwrite(&mylen, 4, 1, fi);
1020 fseek(fi, 0, SEEK_END);
1022 static void png_write_bytes(FILE*fi, unsigned char*bytes, int len)
1026 png_write_byte(fi,bytes[t]);
1028 static void png_write_dword(FILE*fi, u32 dword)
1030 png_write_byte(fi,dword>>24);
1031 png_write_byte(fi,dword>>16);
1032 png_write_byte(fi,dword>>8);
1033 png_write_byte(fi,dword);
1035 static void png_end_chunk(FILE*fi)
1037 u32 tmp = mycrc32^0xffffffff;
1038 unsigned char tmp2[4];
1043 fwrite(&tmp2,4,1,fi);
1046 #define ZLIB_BUFFER_SIZE 16384
1048 static long compress_line(z_stream*zs, Bytef*line, int len, FILE*fi)
1055 int ret = deflate(zs, Z_NO_FLUSH);
1057 fprintf(stderr, "error in deflate(): %s", zs->msg?zs->msg:"unknown");
1060 if(zs->avail_out != ZLIB_BUFFER_SIZE) {
1061 int consumed = ZLIB_BUFFER_SIZE - zs->avail_out;
1063 png_write_bytes(fi, zs->next_out - consumed , consumed);
1064 zs->next_out = zs->next_out - consumed;
1065 zs->avail_out = ZLIB_BUFFER_SIZE;
1074 static int test_line(z_stream*zs_orig, Bytef*line, int linelen)
1077 int ret = deflateCopy(&zs, zs_orig);
1079 fprintf(stderr, "Couldn't copy stream\n");
1084 zs.avail_in = linelen;
1088 int mode = Z_SYNC_FLUSH;
1090 int ret = deflate(&zs, mode);
1091 if (ret != Z_OK && ret != Z_STREAM_END) {
1092 fprintf(stderr, "error in deflate(): %s (mode %s, %d bytes remaining)\n", zs.msg?zs.msg:"unknown",
1093 mode==Z_SYNC_FLUSH?"Z_SYNC_FLUSH":"Z_FINISH", zs.avail_in);
1096 if(zs.avail_out != ZLIB_BUFFER_SIZE) {
1097 int consumed = ZLIB_BUFFER_SIZE - zs.avail_out;
1099 zs.next_out = zs.next_out - consumed;
1100 zs.avail_out = ZLIB_BUFFER_SIZE;
1102 if (ret == Z_STREAM_END) {
1109 ret = deflateEnd(&zs);
1111 fprintf(stderr, "error in deflateEnd(): %s\n", zs.msg?zs.msg:"unknown");
1117 static int finishzlib(z_stream*zs, FILE*fi)
1122 ret = deflate(zs, Z_FINISH);
1124 ret != Z_STREAM_END) {
1125 fprintf(stderr, "error in deflate(finish): %s\n", zs->msg?zs->msg:"unknown");
1129 if(zs->avail_out != ZLIB_BUFFER_SIZE) {
1130 int consumed = ZLIB_BUFFER_SIZE - zs->avail_out;
1132 png_write_bytes(fi, zs->next_out - consumed , consumed);
1133 zs->next_out = zs->next_out - consumed;
1134 zs->avail_out = ZLIB_BUFFER_SIZE;
1136 if (ret == Z_STREAM_END) {
1140 ret = deflateEnd(zs);
1142 fprintf(stderr, "error in deflateEnd(): %s\n", zs->msg?zs->msg:"unknown");
1148 static inline u32 color_hash(COL*col)
1150 u32 col32 = *(u32*)col;
1151 u32 hash = (col32 >> 17) ^ col32;
1152 hash ^= ((hash>>8) + 1) ^ hash;
1156 static int png_get_number_of_palette_entries(COL*img, unsigned width, unsigned height, COL*palette, char*has_alpha)
1158 int len = width*height;
1162 int palette_overflow = 0;
1165 memset(size, 0, sizeof(size));
1167 u32*pal = (u32*)malloc(65536*sizeof(u32));
1168 int*count = (int*)malloc(65536*sizeof(int));
1170 assert(sizeof(COL)==sizeof(u32));
1171 assert(width && height);
1173 lastcol32 = (*(u32*)&img[0])^0xffffffff; // don't match
1175 for(t=0;t<len;t++) {
1176 u32 col32 = *(u32*)&img[t];
1177 if(col32 == lastcol32)
1184 u32 hash = color_hash(&img[t])&255;
1186 int csize = size[hash];
1187 u32*cpal = &pal[hash*256];
1188 int*ccount = &count[hash*256];
1189 for(i=0;i<csize;i++) {
1190 if(col32 == cpal[i]) {
1197 palette_overflow = 1;
1200 count[size[hash]] = 1;
1201 cpal[size[hash]++] = col32;
1206 if(palette_overflow) {
1209 return width*height;
1213 int occurences[256];
1214 for(t=0;t<256;t++) {
1216 int csize = size[t];
1217 u32* cpal = &pal[t*256];
1218 int* ccount = &count[t*256];
1219 for(s=0;s<csize;s++) {
1220 occurences[i] = ccount[s];
1221 palette[i++] = *(COL*)(&cpal[s]);
1226 for(i=0;i<palsize-1;i++) {
1227 for(j=i+1;j<palsize;j++) {
1228 if(occurences[j] < occurences[i]) {
1229 int o = occurences[i];
1231 occurences[i] = occurences[j];
1232 palette[i] = palette[j];
1244 static void png_map_to_palette(COL*src, unsigned char*dest, int size, COL*palette, int palette_size)
1247 int palette_hash[1024];
1248 memset(palette_hash, 0, sizeof(int)*1024);
1250 for(t=0;t<palette_size;t++) {
1251 u32 hash = color_hash(&palette[t])&1023;
1252 while(palette_hash[hash])
1253 hash = (hash+1)&1023;
1254 palette_hash[hash] = t;
1257 for(t=0;t<size;t++) {
1258 u32 hash = color_hash(&src[t]);
1262 index = palette_hash[hash];
1263 if(!memcmp(&palette[index], &src[t], sizeof(COL)))
1267 dest[t] = palette_hash[hash];
1271 static int png_apply_specific_filter_8(int filtermode, unsigned char*dest, unsigned char*src, unsigned width)
1275 unsigned srcwidth = width;
1277 if(filtermode == 0) {
1278 for(x=0;x<width;x++) {
1279 dest[pos2++]=src[pos++]; //alpha
1281 } else if(filtermode == 1) {
1282 /* x difference filter */
1283 dest[pos2++]=src[pos++];
1284 for(x=1;x<width;x++) {
1285 dest[pos2++]=src[pos] - src[pos-1];
1288 } else if(filtermode == 2) {
1289 /* y difference filter */
1290 for(x=0;x<width;x++) {
1291 dest[pos2++]=src[pos+0] - src[pos-srcwidth+0]; //alpha
1294 } else if(filtermode == 3) {
1295 dest[pos2++]=src[pos+0] - src[pos-srcwidth+0]/2;
1297 /* x+y difference filter */
1298 for(x=1;x<width;x++) {
1299 dest[pos2++]=src[pos+0] - (src[pos-1+0] + src[pos-srcwidth+0])/2; //alpha
1302 } else if(filtermode == 4) {
1303 dest[pos2++]=src[pos+0] - PaethPredictor(0, src[pos-srcwidth+0], 0);
1305 /* paeth difference filter */
1306 for(x=1;x<width;x++) {
1307 dest[pos2++]=src[pos+0] - PaethPredictor(src[pos-1+0], src[pos-srcwidth+0], src[pos-1-srcwidth+0]);
1314 static int png_apply_specific_filter_32(int filtermode, unsigned char*dest, unsigned char*src, unsigned width)
1318 unsigned srcwidth = width*4;
1320 if(filtermode == 0) {
1321 for(x=0;x<width;x++) {
1322 dest[pos2++]=src[pos+1];
1323 dest[pos2++]=src[pos+2];
1324 dest[pos2++]=src[pos+3];
1325 dest[pos2++]=src[pos+0]; //alpha
1328 } else if(filtermode == 1) {
1329 /* x difference filter */
1330 dest[pos2++]=src[pos+1];
1331 dest[pos2++]=src[pos+2];
1332 dest[pos2++]=src[pos+3];
1333 dest[pos2++]=src[pos+0];
1335 for(x=1;x<width;x++) {
1336 dest[pos2++]=src[pos+1] - src[pos-4+1];
1337 dest[pos2++]=src[pos+2] - src[pos-4+2];
1338 dest[pos2++]=src[pos+3] - src[pos-4+3];
1339 dest[pos2++]=src[pos+0] - src[pos-4+0]; //alpha
1342 } else if(filtermode == 2) {
1343 /* y difference filter */
1344 for(x=0;x<width;x++) {
1345 dest[pos2++]=src[pos+1] - src[pos-srcwidth+1];
1346 dest[pos2++]=src[pos+2] - src[pos-srcwidth+2];
1347 dest[pos2++]=src[pos+3] - src[pos-srcwidth+3];
1348 dest[pos2++]=src[pos+0] - src[pos-srcwidth+0]; //alpha
1351 } else if(filtermode == 3) {
1352 dest[pos2++]=src[pos+1] - src[pos-srcwidth+1]/2;
1353 dest[pos2++]=src[pos+2] - src[pos-srcwidth+2]/2;
1354 dest[pos2++]=src[pos+3] - src[pos-srcwidth+3]/2;
1355 dest[pos2++]=src[pos+0] - src[pos-srcwidth+0]/2;
1357 /* x+y difference filter */
1358 for(x=1;x<width;x++) {
1359 dest[pos2++]=src[pos+1] - (src[pos-4+1] + src[pos-srcwidth+1])/2;
1360 dest[pos2++]=src[pos+2] - (src[pos-4+2] + src[pos-srcwidth+2])/2;
1361 dest[pos2++]=src[pos+3] - (src[pos-4+3] + src[pos-srcwidth+3])/2;
1362 dest[pos2++]=src[pos+0] - (src[pos-4+0] + src[pos-srcwidth+0])/2; //alpha
1365 } else if(filtermode == 4) {
1366 dest[pos2++]=src[pos+1] - PaethPredictor(0, src[pos-srcwidth+1], 0);
1367 dest[pos2++]=src[pos+2] - PaethPredictor(0, src[pos-srcwidth+2], 0);
1368 dest[pos2++]=src[pos+3] - PaethPredictor(0, src[pos-srcwidth+3], 0);
1369 dest[pos2++]=src[pos+0] - PaethPredictor(0, src[pos-srcwidth+0], 0);
1371 /* paeth difference filter */
1372 for(x=1;x<width;x++) {
1373 dest[pos2++]=src[pos+1] - PaethPredictor(src[pos-4+1], src[pos-srcwidth+1], src[pos-4-srcwidth+1]);
1374 dest[pos2++]=src[pos+2] - PaethPredictor(src[pos-4+2], src[pos-srcwidth+2], src[pos-4-srcwidth+2]);
1375 dest[pos2++]=src[pos+3] - PaethPredictor(src[pos-4+3], src[pos-srcwidth+3], src[pos-4-srcwidth+3]);
1376 dest[pos2++]=src[pos+0] - PaethPredictor(src[pos-4+0], src[pos-srcwidth+0], src[pos-4-srcwidth+0]);
1383 static int*num_bits_table = 0;
1385 static void make_num_bits_table()
1387 if(num_bits_table) return;
1388 num_bits_table = malloc(sizeof(num_bits_table[0])*256);
1390 for(t=0;t<256;t++) {
1397 num_bits_table[t]=bits;
1401 static int png_find_best_filter(unsigned char*src, unsigned width, int bpp, int y)
1403 make_num_bits_table();
1405 int num_filters = y>0?5:2; //don't apply y-direction filter in first line
1407 int bytes_per_pixel = bpp>>3;
1408 int w = width*bytes_per_pixel;
1409 int back_x = bytes_per_pixel;
1410 int back_y = y?width*bytes_per_pixel:0;
1412 unsigned char*pairs[5];
1413 pairs[0] = calloc(1, 8192);
1414 pairs[1] = calloc(1, 8192);
1415 pairs[2] = calloc(1, 8192);
1416 pairs[3] = calloc(1, 8192);
1417 pairs[4] = calloc(1, 8192);
1419 unsigned char old[5];
1420 int l = bytes_per_pixel - 1;
1423 old[2] = src[l] - src[l-back_y];
1424 old[3] = src[l] - src[l-back_y];
1425 old[4] = src[l] - PaethPredictor(0, src[l-back_y], 0);
1427 int different_pairs[5] = {0,0,0,0,0};
1430 for(x=bytes_per_pixel;x<w;x++) {
1431 unsigned char dest[5];
1433 dest[1] = src[x] - src[x-back_x];
1434 dest[2] = src[x] - src[x-back_y];
1435 dest[3] = src[x] - (src[x-back_x] + src[x-back_y])/2;
1436 dest[4] = src[x] - PaethPredictor(src[x-back_x], src[x-back_y], src[x-back_x-back_y]);
1440 int v = dest[i]<<8|old[i];
1443 if(!pairs[i][p]&b) {
1445 different_pairs[i]++;
1448 memcpy(old, dest, sizeof(old));
1452 int best_energy = INT_MAX;
1453 for(f=0;f<num_filters;f++) {
1454 int energy = different_pairs[f];
1455 if(energy<best_energy) {
1457 best_energy = energy;
1469 static int png_apply_filter(unsigned char*dest, unsigned char*src, unsigned width, int y, int bpp)
1473 make_num_bits_table();
1474 int num_filters = y>0?5:2; //don't apply y-direction filter in first line
1476 int best_energy = INT_MAX;
1477 int w = width*(bpp/8);
1478 unsigned char* pairs = malloc(8192);
1479 assert(bpp==8 || bpp==32);
1480 for(f=0;f<num_filters;f++) {
1482 png_apply_specific_filter_8(f, dest, src, width);
1484 png_apply_specific_filter_32(f, dest, src, width);
1487 /* approximation for zlib compressability: test how many different
1488 (byte1,byte2) occur */
1489 memset(pairs, 0, 8192);
1490 int different_pairs = 0;
1491 for(x=0;x<w-1;x++) {
1492 int v = dest[x+1]<<8|dest[x];
1500 int energy = different_pairs;
1501 if(energy<best_energy) {
1503 best_energy = energy;
1508 best_nr = png_find_best_filter(src, width, bpp, y);
1511 png_apply_specific_filter_8(best_nr, dest, src, width);
1513 png_apply_specific_filter_32(best_nr, dest, src, width);
1517 int png_apply_filter_8(unsigned char*dest, unsigned char*src, unsigned width, int y)
1519 return png_apply_filter(dest, src, width, y, 8);
1521 int png_apply_filter_32(unsigned char*dest, unsigned char*src, unsigned width, int y)
1523 return png_apply_filter(dest, src, width, y, 32);
1526 EXPORT void png_write_palette_based(const char*filename, unsigned char*data, unsigned width, unsigned height, int numcolors)
1531 unsigned char format;
1533 unsigned char* data2=0;
1534 unsigned char head[] = {137,80,78,71,13,10,26,10}; // PNG header
1549 int num = png_get_number_of_palette_entries((COL*)data, width, height, palette, &has_alpha);
1551 //printf("image has %d different colors (alpha=%d)\n", num, has_alpha);
1552 data2 = malloc(width*height);
1553 png_map_to_palette((COL*)data, data2, width*height, palette, num);
1567 png_quantize_image(data, width*height, numcolors, &data, palette);
1570 fi = fopen(filename, "wb");
1575 fwrite(head,sizeof(head),1,fi);
1577 png_start_chunk(fi, "IHDR", 13);
1578 png_write_dword(fi,width);
1579 png_write_dword(fi,height);
1580 png_write_byte(fi,8);
1582 png_write_byte(fi,3); //indexed
1583 else if(format == 5 && alpha==0)
1584 png_write_byte(fi,2); //rgb
1585 else if(format == 5 && alpha==1)
1586 png_write_byte(fi,6); //rgba
1589 png_write_byte(fi,0); //compression mode
1590 png_write_byte(fi,0); //filter mode
1591 png_write_byte(fi,0); //interlace mode
1595 png_start_chunk(fi, "PLTE", cols*3);
1596 for(t=0;t<cols;t++) {
1597 png_write_byte(fi,palette[t].r);
1598 png_write_byte(fi,palette[t].g);
1599 png_write_byte(fi,palette[t].b);
1604 png_start_chunk(fi, "tRNS", cols);
1605 for(t=0;t<cols;t++) {
1606 png_write_byte(fi,palette[t].a);
1612 long idatpos = png_start_chunk(fi, "IDAT", 0);
1614 memset(&zs,0,sizeof(z_stream));
1615 Bytef*writebuf = (Bytef*)malloc(ZLIB_BUFFER_SIZE);
1619 zs.next_out = writebuf;
1620 zs.avail_out = ZLIB_BUFFER_SIZE;
1621 ret = deflateInit(&zs, Z_BEST_COMPRESSION);
1623 fprintf(stderr, "error in deflateInit(): %s", zs.msg?zs.msg:"unknown");
1631 unsigned srcwidth = width * bypp;
1632 unsigned linelen = 1 + srcwidth;
1634 linelen = 1 + ((srcwidth+1)&~1);
1636 linelen = 1 + ((srcwidth+2)/3)*3;
1638 linelen = 1 + ((srcwidth+3)&~3);
1639 unsigned char* line = (unsigned char*)malloc(linelen);
1640 memset(line, 0, linelen);
1642 unsigned char* bestline = (unsigned char*)malloc(linelen);
1643 memset(bestline, 0, linelen);
1644 for(y=0;y<height;y++)
1647 int bestsize = 0x7fffffff;
1648 for(filtermode=0;filtermode<=4;filtermode++) {
1649 if(!y && filtermode>=2)
1650 continue; // don't do y direction filters in the first row
1652 line[0]=filtermode; //filter type
1654 png_apply_specific_filter_8(filtermode, line+1, &data[y*srcwidth], width);
1656 png_apply_specific_filter_32(filtermode, line+1, &data[y*srcwidth], width);
1658 int size = test_line(&zs, line, linelen);
1659 if(size < bestsize) {
1660 memcpy(bestline, line, linelen);
1664 idatsize += compress_line(&zs, bestline, linelen, fi);
1668 for(y=0;y<height;y++) {
1670 line[0] = png_apply_filter_8(line+1, &data[y*srcwidth], width, y);
1672 line[0] = png_apply_filter_32(line+1, &data[y*srcwidth], width, y);
1674 idatsize += compress_line(&zs, line, linelen, fi);
1679 idatsize += finishzlib(&zs, fi);
1680 png_patch_len(fi, idatpos, idatsize);
1683 png_start_chunk(fi, "IEND", 0);
1692 EXPORT void png_write(const char*filename, unsigned char*data, unsigned width, unsigned height)
1694 png_write_palette_based(filename, data, width, height, 0);
1696 EXPORT void png_write_palette_based_2(const char*filename, unsigned char*data, unsigned width, unsigned height)
1698 png_write_palette_based(filename, data, width, height, 256);