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
, int 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
, int 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
, int 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
, int 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 getPNGdimensions(const char*sname
, int*destwidth
, int*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 getPNG(const char*sname
, int*destwidth
, int*destheight
, unsigned char**destdata
)
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;
473 unsigned char*alphapalette
= 0;
474 int alphapalettelen
= 0;
475 struct png_header header
;
477 unsigned char*data2
= 0;
478 unsigned char alphacolor
[3];
482 unsigned char *scanline
;
484 if ((fi
= fopen(sname
, "rb")) == NULL
) {
485 printf("Couldn't open %s\n", sname
);
489 if(!png_read_header(fi
, &header
)) {
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;
499 printf("ERROR: mode:%d\n", header
.mode
);
503 imagedatalen
= bypp
* header
.width
* header
.height
+ 65536;
504 imagedata
= (unsigned char*)malloc(imagedatalen
);
506 fseek(fi
,8,SEEK_SET
);
509 if(!png_read_chunk(&tagid
, &len
, &data
, fi
))
511 if(!strncmp(tagid
, "IEND", 4)) {
514 if(!strncmp(tagid
, "PLTE", 4)) {
517 data
= 0; //don't free data
518 //printf("%d colors in palette\n", palettelen);
520 if(!strncmp(tagid
, "tRNS", 4)) {
521 if(header
.mode
== 3) {
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) {
528 if(header
.mode
== 2) {
529 alphacolor
[0] = data
[1];
530 alphacolor
[1] = data
[3];
531 alphacolor
[2] = data
[5];
533 alphacolor
[0] = alphacolor
[1] = alphacolor
[2] = data
[1];
538 if(!strncmp(tagid
, "IDAT", 4)) {
541 zimagedata
= (unsigned char*)malloc(len
);
542 memcpy(zimagedata
,data
,len
);
544 zimagedata
= (unsigned char*)realloc(zimagedata
, zimagedatalen
+len
);
545 memcpy(&zimagedata
[zimagedatalen
], data
, len
);
546 zimagedatalen
+= len
;
549 if(!strncmp(tagid
, "tEXt", 4)) {
551 printf("Image Text: ");
553 if(data[t]>=32 && data[t]<128)
554 printf("%c", data[t]);
566 if(!zimagedata
|| uncompress(imagedata
, &imagedatalen
, zimagedata
, zimagedatalen
) != Z_OK
) {
567 printf("Couldn't uncompress %s!\n", sname
);
574 *destwidth
= header
.width
;
575 *destheight
= header
.height
;
577 data2
= (unsigned char*)malloc(header
.width
*header
.height
*4);
584 unsigned char* old
= (unsigned char*)malloc(header
.width
*2);
585 memset(old
, 0, header
.width
*2);
587 for(y
=0;y
<header
.height
;y
++) {
588 int mode
= imagedata
[pos
++]; //filter mode
592 dest
= &data2
[(y
*header
.width
)*4];
594 if(header
.bpp
== 8) {
595 /* one byte per pixel */
596 src
= &imagedata
[pos
];
599 /* not implemented yet */
600 fprintf(stderr
, "ERROR: mode=4 bpp:%d\n", header
.bpp
);
605 applyfilter2(mode
, src
, old
, dest
, header
.width
);
606 memcpy(old
, dest
, header
.width
*2);
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];
619 } else if(header
.mode
== 6 || header
.mode
== 2) {
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
632 dest
= &data2
[(y
*header
.width
)*4];
636 /* one byte per pixel */
637 src
= &imagedata
[pos
];
638 pos
+=header
.width
*(header
.mode
==6?4:3);
640 /* not implemented yet */
641 fprintf(stderr
, "ERROR: bpp:%d\n", header
.bpp
);
649 old
= &data2
[(y
-1)*header
.width
*4];
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 */
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;
670 } else if(header
.mode
== 0 || header
.mode
== 3) {
672 unsigned char*tmpline
= (unsigned char*)malloc(header
.width
+1);
673 unsigned char*destline
= (unsigned char*)malloc(header
.width
+1);
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
++) {
689 if(rgba
[i
].r
== alphacolor
[0])
695 fprintf(stderr
, "Error: No palette found!\n");
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;*/
713 if(rgba
[i
].r
== alphacolor
[0] &&
714 rgba
[i
].g
== alphacolor
[1] &&
715 rgba
[i
].b
== alphacolor
[2])
721 for(y
=0;y
<header
.height
;y
++) {
722 int mode
= imagedata
[pos
++]; //filter mode
726 src
= &imagedata
[pos
];
727 if(header
.bpp
== 8) {
732 u32 v
= (1<<header
.bpp
)-1;
733 for(x
=0;x
<header
.width
;x
++) {
734 u32 r
= src
[s
/8]<<8 |
737 tmpline
[x
] = (r
>>(16-header
.bpp
-(s
&7)))&v
;
741 pos
+=(header
.width
*header
.bpp
+7)/8;
745 memset(destline
,0,header
.width
);
746 old
= &destline
[y
*header
.width
];
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
]];
761 printf("expected PNG mode to be 2, 3 or 6 (is:%d)\n", header
.mode
);
768 static char hasAlpha(unsigned char*_image
, int size
)
770 COL
*image
= (COL
*)_image
;
772 for(t
=0;t
<size
;t
++) {
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
;
790 static colornum_t
* getColors(COL
*image
, int size
, int*num
)
792 unsigned char*colexists
= malloc((256*256*256)/8);
793 memset(colexists
, 0, (256*256*256)/8);
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)))) {
802 colexists
[index
/8]|=(1<<(index
&7));
806 /* now store them in an array */
807 colornum_t
*colors
=(colornum_t
*)malloc(sizeof(colornum_t
)*count
);
809 for(t
=0;t
<256*256*256;t
++) {
810 if(colexists
[t
/8]&(1<<(t
&7))) {
811 colors
[pos
].color
= t
;
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;
821 for(min
=0, max
=count
, i
=count
/2, l
=count
; i
!= l
; l
=i
,i
=(min
+max
)/2) {
823 if(colors
[i
].color
>= col
) max
=i
;
826 assert(colors
[i
].color
==col
);
834 static void getOptimalPalette(COL
*image
, int size
, int palettesize
, COL
*palette
)
837 memset(palette
, 0, sizeof(COL
)*256);
838 colornum_t
*colors
= getColors(image
, size
, &num
);
840 assert(palettesize
<=256);
842 qsort(colors
, num
, sizeof(colornum_t
), compare_colors
);
844 if(num
<=palettesize
) {
845 /* if there are not more than palettesize different colors in
846 the image anyway, we are done */
849 palette
[t
].r
= colors
[t
].color
;
850 palette
[t
].g
= colors
[t
].color
>>8;
851 palette
[t
].b
= colors
[t
].color
>>16;
858 /* if there are too many different colors, pick the ones that
863 colornum_t
*centers
= malloc(sizeof(colornum_t
)*palettesize
);
865 for(t
=0;t
<palettesize
;t
++) {
866 centers
[t
].color
= colors
[t
].color
;
868 unsigned char*belongsto
= (unsigned char*)malloc(num
);
869 memset(belongsto
, 0, num
);
870 /* do a k-means clustering on the colors */
874 if(tries
++ >= (palettesize
+num
)*2) {
875 fprintf(stderr
, "Warning: didn't find optimal palette\n");
880 for(s
=0;s
<palettesize
;s
++) {
886 for(s
=0;s
<palettesize
;s
++) {
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
;
897 if(bestpos
!=belongsto
[t
])
899 belongsto
[t
] = bestpos
;
901 for(s
=0;s
<palettesize
;s
++) {
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
;
915 int random
= rand()%num
;
916 centers
[s
].color
= colors
[random
].color
;
923 centers
[s
].color
= r
|g
<<8|b
<<16;
924 centers
[s
].num
= count
;
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;
939 static int sqr(const int x
) {return x
*x
;}
941 static void png_quantize_image(unsigned char*_image
, int size
, int numcolors
, unsigned char**newimage
, COL
*palette
)
943 COL
*image
= (COL
*)_image
;
944 getOptimalPalette(image
, size
, numcolors
, palette
);
945 *newimage
= (unsigned char*)malloc(size
);
947 for(t
=0;t
<size
;t
++) {
951 for(s
=0;s
<numcolors
;s
++) {
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;
961 (*newimage
)[t
] = bestcol
;
967 static u32
*crc32_table
= 0;
968 static void make_crc32_table(void)
973 crc32_table
= (u32
*)malloc(1024);
975 for (t
= 0; t
< 256; t
++) {
978 for (s
= 0; s
< 8; s
++) {
979 c
= (0xedb88320L
*(c
&1)) ^ (c
>> 1);
984 static inline void png_write_byte(FILE*fi
, unsigned char byte
)
986 fwrite(&byte
,1,1,fi
);
987 mycrc32
= crc32_table
[(mycrc32
^ byte
) & 0xff] ^ (mycrc32
>> 8);
989 static long png_start_chunk(FILE*fi
, char*type
, int len
)
991 unsigned char mytype
[4]={0,0,0,0};
992 unsigned char mylen
[4];
998 memcpy(mytype
,type
,strlen(type
));
1000 fwrite(&mylen
, 4, 1, fi
);
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]);
1008 static void png_patch_len(FILE*fi
, int pos
, int len
)
1010 unsigned char mylen
[4];
1016 fseek(fi
, pos
, SEEK_SET
);
1017 fwrite(&mylen
, 4, 1, fi
);
1018 fseek(fi
, 0, SEEK_END
);
1020 static void png_write_bytes(FILE*fi
, unsigned char*bytes
, int len
)
1024 png_write_byte(fi
,bytes
[t
]);
1026 static void png_write_dword(FILE*fi
, u32 dword
)
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
);
1033 static void png_end_chunk(FILE*fi
)
1035 u32 tmp
= mycrc32
^0xffffffff;
1036 unsigned char tmp2
[4];
1041 fwrite(&tmp2
,4,1,fi
);
1044 #define ZLIB_BUFFER_SIZE 16384
1046 static long compress_line(z_stream
*zs
, Bytef
*line
, int len
, FILE*fi
)
1053 int ret
= deflate(zs
, Z_NO_FLUSH
);
1055 fprintf(stderr
, "error in deflate(): %s", zs
->msg
?zs
->msg
:"unknown");
1058 if(zs
->avail_out
!= ZLIB_BUFFER_SIZE
) {
1059 int consumed
= ZLIB_BUFFER_SIZE
- zs
->avail_out
;
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
;
1072 static int test_line(z_stream
*zs_orig
, Bytef
*line
, int linelen
)
1075 int ret
= deflateCopy(&zs
, zs_orig
);
1077 fprintf(stderr
, "Couldn't copy stream\n");
1082 zs
.avail_in
= linelen
;
1086 int mode
= Z_SYNC_FLUSH
;
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
);
1094 if(zs
.avail_out
!= ZLIB_BUFFER_SIZE
) {
1095 int consumed
= ZLIB_BUFFER_SIZE
- zs
.avail_out
;
1097 zs
.next_out
= zs
.next_out
- consumed
;
1098 zs
.avail_out
= ZLIB_BUFFER_SIZE
;
1100 if (ret
== Z_STREAM_END
) {
1107 ret
= deflateEnd(&zs
);
1109 fprintf(stderr
, "error in deflateEnd(): %s\n", zs
.msg
?zs
.msg
:"unknown");
1115 static int finishzlib(z_stream
*zs
, FILE*fi
)
1120 ret
= deflate(zs
, Z_FINISH
);
1122 ret
!= Z_STREAM_END
) {
1123 fprintf(stderr
, "error in deflate(finish): %s\n", zs
->msg
?zs
->msg
:"unknown");
1127 if(zs
->avail_out
!= ZLIB_BUFFER_SIZE
) {
1128 int consumed
= ZLIB_BUFFER_SIZE
- zs
->avail_out
;
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
;
1134 if (ret
== Z_STREAM_END
) {
1138 ret
= deflateEnd(zs
);
1140 fprintf(stderr
, "error in deflateEnd(): %s\n", zs
->msg
?zs
->msg
:"unknown");
1146 static inline u32
color_hash(COL
*col
)
1148 u32 col32
= *(u32
*)col
;
1149 u32 hash
= (col32
>> 17) ^ col32
;
1150 hash
^= ((hash
>>8) + 1) ^ hash
;
1154 static int png_get_number_of_palette_entries(COL
*img
, int width
, int height
, COL
*palette
, char*has_alpha
)
1156 int len
= width
*height
;
1160 int palette_overflow
= 0;
1163 memset(size
, 0, sizeof(size
));
1165 u32
*pal
= (u32
*)malloc(65536*sizeof(u32
));
1166 int*count
= (int*)malloc(65536*sizeof(int));
1168 assert(sizeof(COL
)==sizeof(u32
));
1169 assert(width
&& height
);
1171 lastcol32
= (*(u32
*)&img
[0])^0xffffffff; // don't match
1173 for(t
=0;t
<len
;t
++) {
1174 u32 col32
= *(u32
*)&img
[t
];
1175 if(col32
== lastcol32
)
1182 u32 hash
= color_hash(&img
[t
])&255;
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
]) {
1195 palette_overflow
= 1;
1198 count
[size
[hash
]] = 1;
1199 cpal
[size
[hash
]++] = col32
;
1204 if(palette_overflow
) {
1207 return width
*height
;
1211 int occurences
[256];
1212 for(t
=0;t
<256;t
++) {
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
]);
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
];
1229 occurences
[i
] = occurences
[j
];
1230 palette
[i
] = palette
[j
];
1242 static void png_map_to_palette(COL
*src
, unsigned char*dest
, int size
, COL
*palette
, int palette_size
)
1245 int palette_hash
[1024];
1246 memset(palette_hash
, 0, sizeof(int)*1024);
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
;
1255 for(t
=0;t
<size
;t
++) {
1256 u32 hash
= color_hash(&src
[t
]);
1260 index
= palette_hash
[hash
];
1261 if(!memcmp(&palette
[index
], &src
[t
], sizeof(COL
)))
1265 dest
[t
] = palette_hash
[hash
];
1269 static int png_apply_specific_filter_8(int filtermode
, unsigned char*dest
, unsigned char*src
, int width
)
1273 int srcwidth
= width
;
1275 if(filtermode
== 0) {
1276 for(x
=0;x
<width
;x
++) {
1277 dest
[pos2
++]=src
[pos
++]; //alpha
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];
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
1292 } else if(filtermode
== 3) {
1293 dest
[pos2
++]=src
[pos
+0] - src
[pos
-srcwidth
+0]/2;
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
1300 } else if(filtermode
== 4) {
1301 dest
[pos2
++]=src
[pos
+0] - PaethPredictor(0, src
[pos
-srcwidth
+0], 0);
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]);
1312 static int png_apply_specific_filter_32(int filtermode
, unsigned char*dest
, unsigned char*src
, int width
)
1316 int srcwidth
= width
*4;
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
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];
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
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
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;
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
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);
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]);
1381 static int*num_bits_table
= 0;
1383 static void make_num_bits_table()
1385 if(num_bits_table
) return;
1386 num_bits_table
= malloc(sizeof(num_bits_table
[0])*256);
1388 for(t
=0;t
<256;t
++) {
1395 num_bits_table
[t
]=bits
;
1399 static int png_find_best_filter(unsigned char*src
, int width
, int bpp
, int y
)
1401 make_num_bits_table();
1403 int num_filters
= y
>0?5:2; //don't apply y-direction filter in first line
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;
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);
1417 unsigned char old
[5];
1418 int l
= bytes_per_pixel
- 1;
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);
1425 int different_pairs
[5] = {0,0,0,0,0};
1428 for(x
=bytes_per_pixel
;x
<w
;x
++) {
1429 unsigned char dest
[5];
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
]);
1438 int v
= dest
[i
]<<8|old
[i
];
1441 if(!pairs
[i
][p
]&b
) {
1443 different_pairs
[i
]++;
1446 memcpy(old
, dest
, sizeof(old
));
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
) {
1455 best_energy
= energy
;
1467 static int png_apply_filter(unsigned char*dest
, unsigned char*src
, int width
, int y
, int bpp
)
1471 make_num_bits_table();
1472 int num_filters
= y
>0?5:2; //don't apply y-direction filter in first line
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
++) {
1480 png_apply_specific_filter_8(f
, dest
, src
, width
);
1482 png_apply_specific_filter_32(f
, dest
, src
, width
);
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
];
1498 int energy
= different_pairs
;
1499 if(energy
<best_energy
) {
1501 best_energy
= energy
;
1506 best_nr
= png_find_best_filter(src
, width
, bpp
, y
);
1509 png_apply_specific_filter_8(best_nr
, dest
, src
, width
);
1511 png_apply_specific_filter_32(best_nr
, dest
, src
, width
);
1515 int png_apply_filter_8(unsigned char*dest
, unsigned char*src
, int width
, int y
)
1517 return png_apply_filter(dest
, src
, width
, y
, 8);
1519 int png_apply_filter_32(unsigned char*dest
, unsigned char*src
, int width
, int y
)
1521 return png_apply_filter(dest
, src
, width
, y
, 32);
1524 EXPORT
void savePNG(const char*filename
, unsigned char*data
, int width
, int height
, int numcolors
)
1529 unsigned char format
;
1531 unsigned char* data2
=0;
1532 unsigned char head
[] = {137,80,78,71,13,10,26,10}; // PNG header
1547 int num
= png_get_number_of_palette_entries((COL
*)data
, width
, height
, palette
, &has_alpha
);
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
);
1565 png_quantize_image(data
, width
*height
, numcolors
, &data
, palette
);
1568 fi
= fopen(filename
, "wb");
1573 fwrite(head
,sizeof(head
),1,fi
);
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);
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
1587 png_write_byte(fi
,0); //compression mode
1588 png_write_byte(fi
,0); //filter mode
1589 png_write_byte(fi
,0); //interlace mode
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
);
1602 png_start_chunk(fi
, "tRNS", cols
);
1603 for(t
=0;t
<cols
;t
++) {
1604 png_write_byte(fi
,palette
[t
].a
);
1610 long idatpos
= png_start_chunk(fi
, "IDAT", 0);
1612 memset(&zs
,0,sizeof(z_stream
));
1613 Bytef
*writebuf
= (Bytef
*)malloc(ZLIB_BUFFER_SIZE
);
1617 zs
.next_out
= writebuf
;
1618 zs
.avail_out
= ZLIB_BUFFER_SIZE
;
1619 ret
= deflateInit(&zs
, Z_BEST_COMPRESSION
);
1621 fprintf(stderr
, "error in deflateInit(): %s", zs
.msg
?zs
.msg
:"unknown");
1629 int srcwidth
= width
* bypp
;
1630 int linelen
= 1 + srcwidth
;
1632 linelen
= 1 + ((srcwidth
+1)&~1);
1634 linelen
= 1 + ((srcwidth
+2)/3)*3;
1636 linelen
= 1 + ((srcwidth
+3)&~3);
1637 unsigned char* line
= (unsigned char*)malloc(linelen
);
1638 memset(line
, 0, linelen
);
1640 unsigned char* bestline
= (unsigned char*)malloc(linelen
);
1641 memset(bestline
, 0, linelen
);
1642 for(y
=0;y
<height
;y
++)
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
1650 line
[0]=filtermode
; //filter type
1652 png_apply_specific_filter_8(filtermode
, line
+1, &data
[y
*srcwidth
], width
);
1654 png_apply_specific_filter_32(filtermode
, line
+1, &data
[y
*srcwidth
], width
);
1656 int size
= test_line(&zs
, line
, linelen
);
1657 if(size
< bestsize
) {
1658 memcpy(bestline
, line
, linelen
);
1662 idatsize
+= compress_line(&zs
, bestline
, linelen
, fi
);
1666 for(y
=0;y
<height
;y
++) {
1668 line
[0] = png_apply_filter_8(line
+1, &data
[y
*srcwidth
], width
, y
);
1670 line
[0] = png_apply_filter_32(line
+1, &data
[y
*srcwidth
], width
, y
);
1672 idatsize
+= compress_line(&zs
, line
, linelen
, fi
);
1677 idatsize
+= finishzlib(&zs
, fi
);
1678 png_patch_len(fi
, idatpos
, idatsize
);
1681 png_start_chunk(fi
, "IEND", 0);
1690 EXPORT
void writePNG(const char*filename
, unsigned char*data
, int width
, int height
)
1692 savePNG(filename
, data
, width
, height
, 0);
1694 EXPORT
void writePalettePNG(const char*filename
, unsigned char*data
, int width
, int height
)
1696 savePNG(filename
, data
, width
, height
, 256);