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     unsigned width;
  89     unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned*destwidth, unsigned*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, unsigned*destwidth, unsigned*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 zimagedatalen=0;
 470     unsigned char*palette = 0;
 471     int palettelen = 0;
 472     unsigned char*alphapalette = 0;
 473     int alphapalettelen = 0;
 474     struct png_header header;
 475     int bypp;
 476     unsigned char*data2 = 0;
 477     unsigned char alphacolor[3];
 478     int hasalphacolor=0;
 479
 480     FILE *fi;
 481     unsigned char *scanline;
 482
 483     if ((fi = fopen(sname, "rb")) == NULL) {
 484         printf("Couldn't open %s\n", sname);
 485         return 0;
 486     }
 487
 488     if(!png_read_header(fi, &header)) {
 489         fclose(fi);
 490         return 0;
 491     }
 492
 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;
 497     else {
 498         printf("ERROR: mode:%d\n", header.mode);
 499         return 0;
 500     }
 501
 502     unsigned long long imagedatalen_64 = ((unsigned long long)header.width + 1) * header.height * bypp;
 503     if(imagedatalen_64 > 0xffffffff)
 504         return 0;
 505     unsigned long imagedatalen = (unsigned long)imagedatalen_64;
 506     imagedata = (unsigned char*)malloc(imagedatalen);
 507
 508     fseek(fi,8,SEEK_SET);
 509     while(!feof(fi))
 510     {
 511         if(!png_read_chunk(&tagid, &len, &data, fi))
 512             break;
 513         if(!strncmp(tagid, "IEND", 4)) {
 514             break;
 515         }
 516         if(!strncmp(tagid, "PLTE", 4)) {
 517             palette = data;
 518             palettelen = len/3;
 519             data = 0; //don't free data
 520             //printf("%d colors in palette\n", palettelen);
 521         }
 522         if(!strncmp(tagid, "tRNS", 4)) {
 523             if(header.mode == 3) {
 524                 alphapalette = data;
 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) {
 529                 int t;
 530                 if(header.mode == 2) {
 531                     alphacolor[0] = data[1];
 532                     alphacolor[1] = data[3];
 533                     alphacolor[2] = data[5];
 534                 } else {
 535                     alphacolor[0] = alphacolor[1] = alphacolor[2] = data[1];
 536                 }
 537                 hasalphacolor = 1;
 538             }
 539         }
 540         if(!strncmp(tagid, "IDAT", 4)) {
 541             if(!zimagedata) {
 542                 zimagedatalen = len;
 543                 zimagedata = (unsigned char*)malloc(len);
 544                 memcpy(zimagedata,data,len);
 545             } else {
 546                 zimagedata = (unsigned char*)realloc(zimagedata, zimagedatalen+len);
 547                 memcpy(&zimagedata[zimagedatalen], data, len);
 548                 zimagedatalen += len;
 549             }
 550         }
 551         if(!strncmp(tagid, "tEXt", 4)) {
 552             /*int t;
 553             printf("Image Text: ");
 554             for(t=0;t<len;t++) {
 555                 if(data[t]>=32 && data[t]<128)
 556                     printf("%c", data[t]);
 557                 else
 558                     printf("?");
 559             }
 560             printf("\n");*/
 561         }
 562         if(data) {
 563             free(data); data=0;
 564         }
 565     }
 566
 567     fclose(fi);
 568     if(!zimagedata || uncompress(imagedata, &imagedatalen, zimagedata, zimagedatalen) != Z_OK) {
 569         printf("Couldn't uncompress %s!\n", sname);
 570         if(zimagedata)
 571             free(zimagedata);
 572         return 0;
 573     }
 574     free(zimagedata);
 575
 576     *destwidth = header.width;
 577     *destheight = header.height;
 578
 579     data2 = (unsigned char*)malloc(header.width*header.height*4);
 580
 581     if(header.mode == 4)
 582     {
 583         int i,s=0;
 584         int x,y;
 585         int pos=0;
 586         unsigned char* old= (unsigned char*)malloc(header.width*2);
 587         memset(old, 0, header.width*2);
 588         *destdata = data2;
 589         for(y=0;y<header.height;y++) {
 590             int mode = imagedata[pos++]; //filter mode
 591             unsigned char*src;
 592             unsigned char*dest;
 593             int x;
 594             dest = &data2[(y*header.width)*4];
 595
 596             if(header.bpp == 8) {
 597                 /* one byte per pixel */
 598                 src = &imagedata[pos];
 599                 pos+=header.width*2;
 600             } else {
 601                 /* not implemented yet */
 602                 fprintf(stderr, "ERROR: mode=4 bpp:%d\n", header.bpp);
 603                 free(data2);
 604                 return 0;
 605             }
 606
 607             applyfilter2(mode, src, old, dest, header.width);
 608             memcpy(old, dest, header.width*2);
 609
 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];
 613                 dest[x*4+0] = alpha;
 614                 dest[x*4+1] = gray;
 615                 dest[x*4+2] = gray;
 616                 dest[x*4+3] = gray;
 617             }
 618         }
 619         free(old);
 620         free(imagedata);
 621     } else if(header.mode == 6 || header.mode == 2) {
 622         int i,s=0;
 623         int x,y;
 624         int pos=0;
 625         *destdata = data2;
 626
 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
 631             unsigned char*src;
 632             unsigned char*dest;
 633             unsigned char*old;
 634             dest = &data2[(y*header.width)*4];
 635
 636             if(header.bpp == 8)
 637             {
 638                 /* one byte per pixel */
 639                 src = &imagedata[pos];
 640                 pos+=header.width*(header.mode==6?4:3);
 641             } else {
 642                 /* not implemented yet */
 643                 fprintf(stderr, "ERROR: bpp:%d\n", header.bpp);
 644                 free(data2);
 645                 return 0;
 646             }
 647
 648             if(!y) {
 649                 old = firstline;
 650             } else {
 651                 old = &data2[(y-1)*header.width*4];
 652             }
 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 */
 658                 if(hasalphacolor) {
 659                     int x;
 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;
 665                         }
 666                     }
 667                 }
 668             }
 669         }
 670         free(firstline);
 671         free(imagedata);
 672     } else if(header.mode == 0 || header.mode == 3) {
 673         COL*rgba = 0;
 674         unsigned char*tmpline = (unsigned char*)malloc(header.width+1);
 675         unsigned char*destline = (unsigned char*)malloc(header.width+1);
 676         int i,x,y;
 677         int pos=0;
 678
 679         *destdata = data2;
 680
 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++) {
 686                 rgba[i].a = 255;
 687                 rgba[i].r = i*mult;
 688                 rgba[i].g = i*mult;
 689                 rgba[i].b = i*mult;
 690                 if(hasalphacolor) {
 691                     if(rgba[i].r == alphacolor[0])
 692                         rgba[i].a = 0;
 693                 }
 694             }
 695         } else {
 696             if(!palette) {
 697                 fprintf(stderr, "Error: No palette found!\n");
 698                 exit(1);
 699             }
 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;*/
 711                 } else {
 712                     rgba[i].a = 255;
 713                 }
 714                 if(hasalphacolor) {
 715                     if(rgba[i].r == alphacolor[0] &&
 716                        rgba[i].g == alphacolor[1] &&
 717                        rgba[i].b == alphacolor[2])
 718                         rgba[i].a = 0;
 719                 }
 720             }
 721         }
 722
 723         for(y=0;y<header.height;y++) {
 724             int mode = imagedata[pos++]; //filter mode
 725             int x;
 726             unsigned char*old;
 727             unsigned char*src;
 728             src = &imagedata[pos];
 729             if(header.bpp == 8) {
 730                 pos+=header.width;
 731             } else {
 732                 int x,s=0;
 733                 int bitpos = 0;
 734                 u32 v = (1<<header.bpp)-1;
 735                 for(x=0;x<header.width;x++) {
 736                     u32 r = src[s/8]<<8 |
 737                             src[s/8+1];
 738                     int t;
 739                     tmpline[x] = (r>>(16-header.bpp-(s&7)))&v;
 740                     s+=header.bpp;
 741                 }
 742                 src = tmpline;
 743                 pos+=(header.width*header.bpp+7)/8;
 744             }
 745
 746             if(!y) {
 747                 memset(destline,0,header.width);
 748                 old = &destline[y*header.width];
 749             } else {
 750                 old = tmpline;
 751             }
 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]];
 756             }
 757         }
 758         free(tmpline);
 759         free(destline);
 760         free(rgba);
 761         free(imagedata);
 762     } else {
 763         printf("expected PNG mode to be 2, 3 or 6 (is:%d)\n", header.mode);
 764         return 0;
 765     }
 766
 767     return 1;
 768 }
 769
 770 static char hasAlpha(unsigned char*_image, int size)
 771 {
 772     COL*image = (COL*)_image;
 773     int t;
 774     for(t=0;t<size;t++) {
 775         if(image[t].a!=255)
 776             return 1;
 777     }
 778     return 0;
 779 }
 780
 781 typedef struct {
 782     u32 num;
 783     u32 color;
 784 } colornum_t;
 785
 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;
 790 }
 791
 792 static colornum_t* getColors(COL*image, int size, int*num)
 793 {
 794     unsigned char*colexists = malloc((256*256*256)/8);
 795     memset(colexists, 0, (256*256*256)/8);
 796     int t;
 797     int count=0;
 798
 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)))) {
 803             count++;
 804             colexists[index/8]|=(1<<(index&7));
 805         }
 806     }
 807
 808     /* now store them in an array */
 809     colornum_t*colors=(colornum_t*)malloc(sizeof(colornum_t)*count);
 810     int pos=0;
 811     for(t=0;t<256*256*256;t++) {
 812         if(colexists[t/8]&(1<<(t&7))) {
 813             colors[pos].color = t;
 814             colors[pos].num = 0;
 815             pos++;
 816         }
 817     }
 818
 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;
 822         int min,max,i,l;
 823         for(min=0, max=count, i=count/2, l=count; i != l; l=i,i=(min+max)/2) {
 824             // binary search
 825             if(colors[i].color >= col) max=i;
 826             else min=i+1;
 827         }
 828         assert(colors[i].color==col);
 829         colors[i].num++;
 830     }
 831     free(colexists);
 832     *num = count;
 833     return colors;
 834 }
 835
 836 static void getOptimalPalette(COL*image, int size, int palettesize, COL*palette)
 837 {
 838     int num;
 839     memset(palette, 0, sizeof(COL)*256);
 840     colornum_t*colors = getColors(image, size, &num);
 841
 842     assert(palettesize<=256);
 843
 844     qsort(colors, num, sizeof(colornum_t), compare_colors);
 845
 846     if(num<=palettesize) {
 847         /* if there are not more than palettesize different colors in
 848            the image anyway, we are done */
 849         int t;
 850         for(t=0;t<num;t++) {
 851             palette[t].r = colors[t].color;
 852             palette[t].g = colors[t].color>>8;
 853             palette[t].b = colors[t].color>>16;
 854             palette[t].a = 255;
 855         }
 856         return;
 857     }
 858
 859     if(num>2048) {
 860         /* if there are too many different colors, pick the ones that
 861            occur most often */
 862         num = 2048;
 863     }
 864
 865     colornum_t*centers = malloc(sizeof(colornum_t)*palettesize);
 866     int t;
 867     for(t=0;t<palettesize;t++) {
 868         centers[t].color = colors[t].color;
 869     }
 870     unsigned char*belongsto = (unsigned char*)malloc(num);
 871     memset(belongsto, 0, num);
 872     /* do a k-means clustering on the colors */
 873     char change = 1;
 874     int tries = 0;
 875     while(change) {
 876         if(tries++ >= (palettesize+num)*2) {
 877             fprintf(stderr, "Warning: didn't find optimal palette\n");
 878             break;
 879         }
 880         change = 0;
 881         int s,t;
 882         for(s=0;s<palettesize;s++) {
 883             centers[s].num = 0;
 884         }
 885         for(t=0;t<num;t++) {
 886             int best=0x7fffffff;
 887             int bestpos=0;
 888             for(s=0;s<palettesize;s++) {
 889                 int distance = 0;
 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;
 894                 if(distance<best) {
 895                     best = distance;
 896                     bestpos = s;
 897                 }
 898             }
 899             if(bestpos!=belongsto[t])
 900                 change = 1;
 901             belongsto[t] = bestpos;
 902         }
 903         for(s=0;s<palettesize;s++) {
 904             int r=0;
 905             int g=0;
 906             int b=0;
 907             int count=0;
 908             for(t=0;t<num;t++) {
 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;
 914                 }
 915             }
 916             if(!count) {
 917                 int random = rand()%num;
 918                 centers[s].color = colors[random].color;
 919                 centers[s].num = 0;
 920                 change = 1;
 921             } else {
 922                 r /= count;
 923                 g /= count;
 924                 b /= count;
 925                 centers[s].color = r|g<<8|b<<16;
 926                 centers[s].num = count;
 927             }
 928         }
 929     }
 930     free(belongsto);
 931     free(colors);
 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;
 936         palette[t].a = 255;
 937     }
 938     free(centers);
 939 }
 940
 941 static int sqr(const int x) {return x*x;}
 942
 943 static void png_quantize_image(unsigned char*_image, int size, int numcolors, unsigned char**newimage, COL*palette)
 944 {
 945     COL*image = (COL*)_image;
 946     getOptimalPalette(image, size, numcolors, palette);
 947     *newimage = (unsigned char*)malloc(size);
 948     int t;
 949     for(t=0;t<size;t++) {
 950         int best=0x7fffffff;
 951         int bestcol = 0;
 952         int s;
 953         for(s=0;s<numcolors;s++) {
 954             int distance = 0;
 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;
 958             if(distance<best) {
 959                 best = distance;
 960                 bestcol = s;
 961             }
 962         }
 963         (*newimage)[t] = bestcol;
 964     }
 965 }
 966
 967 static u32 mycrc32;
 968
 969 static u32*crc32_table = 0;
 970 static void make_crc32_table(void)
 971 {
 972   int t;
 973   if(crc32_table)
 974       return;
 975   crc32_table = (u32*)malloc(1024);
 976
 977   for (t = 0; t < 256; t++) {
 978     u32 c = t;
 979     int s;
 980     for (s = 0; s < 8; s++) {
 981       c = (0xedb88320L*(c&1)) ^ (c >> 1);
 982     }
 983     crc32_table[t] = c;
 984   }
 985 }
 986 static inline void png_write_byte(FILE*fi, unsigned char byte)
 987 {
 988     fwrite(&byte,1,1,fi);
 989     mycrc32 = crc32_table[(mycrc32 ^ byte) & 0xff] ^ (mycrc32 >> 8);
 990 }
 991 static long png_start_chunk(FILE*fi, char*type, int len)
 992 {
 993     unsigned char mytype[4]={0,0,0,0};
 994     unsigned char mylen[4];
 995     long filepos;
 996     mylen[0] = len>>24;
 997     mylen[1] = len>>16;
 998     mylen[2] = len>>8;
 999     mylen[3] = len;
1000     memcpy(mytype,type,strlen(type));
1001     filepos = ftell(fi);
1002     fwrite(&mylen, 4, 1, fi);
1003     mycrc32=0xffffffff;
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]);
1008     return filepos;
1009 }
1010 static void png_patch_len(FILE*fi, int pos, int len)
1011 {
1012     unsigned char mylen[4];
1013     long filepos;
1014     mylen[0] = len>>24;
1015     mylen[1] = len>>16;
1016     mylen[2] = len>>8;
1017     mylen[3] = len;
1018     fseek(fi, pos, SEEK_SET);
1019     fwrite(&mylen, 4, 1, fi);
1020     fseek(fi, 0, SEEK_END);
1021 }
1022 static void png_write_bytes(FILE*fi, unsigned char*bytes, int len)
1023 {
1024     int t;
1025     for(t=0;t<len;t++)
1026         png_write_byte(fi,bytes[t]);
1027 }
1028 static void png_write_dword(FILE*fi, u32 dword)
1029 {
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);
1034 }
1035 static void png_end_chunk(FILE*fi)
1036 {
1037     u32 tmp = mycrc32^0xffffffff;
1038     unsigned char tmp2[4];
1039     tmp2[0] = tmp>>24;
1040     tmp2[1] = tmp>>16;
1041     tmp2[2] = tmp>>8;
1042     tmp2[3] = tmp;
1043     fwrite(&tmp2,4,1,fi);
1044 }
1045
1046 #define ZLIB_BUFFER_SIZE 16384
1047
1048 static long compress_line(z_stream*zs, Bytef*line, int len, FILE*fi)
1049 {
1050     long size = 0;
1051     zs->next_in = line;
1052     zs->avail_in = len;
1053
1054     while(1) {
1055         int ret = deflate(zs, Z_NO_FLUSH);
1056         if (ret != Z_OK) {
1057             fprintf(stderr, "error in deflate(): %s", zs->msg?zs->msg:"unknown");
1058             return 0;
1059         }
1060         if(zs->avail_out != ZLIB_BUFFER_SIZE) {
1061             int consumed = ZLIB_BUFFER_SIZE - zs->avail_out;
1062             size += consumed;
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;
1066         }
1067         if(!zs->avail_in) {
1068             break;
1069         }
1070     }
1071     return size;
1072 }
1073
1074 static int test_line(z_stream*zs_orig, Bytef*line, int linelen)
1075 {
1076     z_stream zs;
1077     int ret = deflateCopy(&zs, zs_orig);
1078     if(ret != Z_OK) {
1079         fprintf(stderr, "Couldn't copy stream\n");
1080         return 0;
1081     }
1082
1083     zs.next_in = line;
1084     zs.avail_in = linelen;
1085
1086     long size = 0;
1087
1088     int mode = Z_SYNC_FLUSH;
1089     while(1) {
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);
1094             return 0;
1095         }
1096         if(zs.avail_out != ZLIB_BUFFER_SIZE) {
1097             int consumed = ZLIB_BUFFER_SIZE - zs.avail_out;
1098             size += consumed;
1099             zs.next_out = zs.next_out - consumed;
1100             zs.avail_out = ZLIB_BUFFER_SIZE;
1101         }
1102         if (ret == Z_STREAM_END) {
1103             break;
1104         }
1105         if(!zs.avail_in) {
1106             mode = Z_FINISH;
1107         }
1108     }
1109     ret = deflateEnd(&zs);
1110     if (ret != Z_OK) {
1111         fprintf(stderr, "error in deflateEnd(): %s\n", zs.msg?zs.msg:"unknown");
1112         return 0;
1113     }
1114     return size;
1115 }
1116
1117 static int finishzlib(z_stream*zs, FILE*fi)
1118 {
1119     int size = 0;
1120     int ret;
1121     while(1) {
1122         ret = deflate(zs, Z_FINISH);
1123         if (ret != Z_OK &&
1124             ret != Z_STREAM_END) {
1125             fprintf(stderr, "error in deflate(finish): %s\n", zs->msg?zs->msg:"unknown");
1126             return 0;
1127         }
1128
1129         if(zs->avail_out != ZLIB_BUFFER_SIZE) {
1130             int consumed = ZLIB_BUFFER_SIZE - zs->avail_out;
1131             size += consumed;
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;
1135         }
1136         if (ret == Z_STREAM_END) {
1137             break;
1138         }
1139     }
1140     ret = deflateEnd(zs);
1141     if (ret != Z_OK) {
1142         fprintf(stderr, "error in deflateEnd(): %s\n", zs->msg?zs->msg:"unknown");
1143         return 0;
1144     }
1145     return size;
1146 }
1147
1148 static inline u32 color_hash(COL*col)
1149 {
1150     u32 col32 = *(u32*)col;
1151     u32 hash = (col32 >> 17) ^ col32;
1152     hash ^= ((hash>>8) + 1) ^ hash;
1153     return hash;
1154 }
1155
1156 static int png_get_number_of_palette_entries(COL*img, unsigned width, unsigned height, COL*palette, char*has_alpha)
1157 {
1158     int len = width*height;
1159     int t;
1160     int palsize = 0;
1161     int size[256];
1162     int palette_overflow = 0;
1163     u32 lastcol32 = 0;
1164
1165     memset(size, 0, sizeof(size));
1166
1167     u32*pal = (u32*)malloc(65536*sizeof(u32));
1168     int*count = (int*)malloc(65536*sizeof(int));
1169
1170     assert(sizeof(COL)==sizeof(u32));
1171     assert(width && height);
1172
1173     lastcol32 = (*(u32*)&img[0])^0xffffffff; // don't match
1174
1175     for(t=0;t<len;t++) {
1176         u32 col32 = *(u32*)&img[t];
1177         if(col32 == lastcol32)
1178             continue;
1179
1180         if(img[t].a!=255)
1181             *has_alpha=1;
1182         int i;
1183
1184         u32 hash = color_hash(&img[t])&255;
1185
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]) {
1191                 ccount[i]++;
1192                 break;
1193             }
1194         }
1195         if(i==csize) {
1196             if(palsize==256) {
1197                 palette_overflow = 1;
1198                 break;
1199             }
1200             count[size[hash]] = 1;
1201             cpal[size[hash]++] = col32;
1202             palsize++;
1203         }
1204         lastcol32 = col32;
1205     }
1206     if(palette_overflow) {
1207         free(pal);
1208         *has_alpha=1;
1209         return width*height;
1210     }
1211     if(palette) {
1212         int i = 0;
1213         int occurences[256];
1214         for(t=0;t<256;t++) {
1215             int s;
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]);
1222             }
1223         }
1224         assert(i==palsize);
1225         int j;
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];
1230                     COL c = palette[i];
1231                     occurences[i] = occurences[j];
1232                     palette[i] = palette[j];
1233                     occurences[j] = o;
1234                     palette[j] = c;
1235                 }
1236             }
1237         }
1238     }
1239     free(pal);
1240     free(count);
1241     return palsize;
1242 }
1243
1244 static void png_map_to_palette(COL*src, unsigned char*dest, int size, COL*palette, int palette_size)
1245 {
1246     int t;
1247     int palette_hash[1024];
1248     memset(palette_hash, 0, sizeof(int)*1024);
1249
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;
1255     }
1256
1257     for(t=0;t<size;t++) {
1258         u32 hash = color_hash(&src[t]);
1259         int index = 0;
1260         while(1) {
1261             hash&=1023;
1262             index = palette_hash[hash];
1263             if(!memcmp(&palette[index], &src[t], sizeof(COL)))
1264                 break;
1265             hash++;
1266         }
1267         dest[t] = palette_hash[hash];
1268     }
1269 }
1270
1271 static int png_apply_specific_filter_8(int filtermode, unsigned char*dest, unsigned char*src, unsigned width)
1272 {
1273     int pos2 = 0;
1274     int pos = 0;
1275     unsigned srcwidth = width;
1276     int x;
1277     if(filtermode == 0) {
1278         for(x=0;x<width;x++) {
1279             dest[pos2++]=src[pos++]; //alpha
1280         }
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];
1286             pos++;
1287         }
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
1292             pos++;
1293         }
1294     } else if(filtermode == 3) {
1295         dest[pos2++]=src[pos+0] - src[pos-srcwidth+0]/2;
1296         pos++;
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
1300             pos++;
1301         }
1302     } else if(filtermode == 4) {
1303         dest[pos2++]=src[pos+0] - PaethPredictor(0, src[pos-srcwidth+0], 0);
1304         pos++;
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]);
1308             pos++;
1309         }
1310     }
1311     return filtermode;
1312 }
1313
1314 static int png_apply_specific_filter_32(int filtermode, unsigned char*dest, unsigned char*src, unsigned width)
1315 {
1316     int pos2 = 0;
1317     int pos = 0;
1318     unsigned srcwidth = width*4;
1319     int x;
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
1326             pos+=4;
1327         }
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];
1334         pos+=4;
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
1340             pos+=4;
1341         }
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
1349             pos+=4;
1350         }
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;
1356         pos+=4;
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
1363             pos+=4;
1364         }
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);
1370         pos+=4;
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]);
1377             pos+=4;
1378         }
1379     }
1380     return filtermode;
1381 }
1382
1383 static int*num_bits_table = 0;
1384
1385 static void make_num_bits_table()
1386 {
1387     if(num_bits_table) return;
1388     num_bits_table = malloc(sizeof(num_bits_table[0])*256);
1389     int t;
1390     for(t=0;t<256;t++) {
1391         int bits=0;
1392         int v = t;
1393         while(v) {
1394             bits++;
1395             v&=v-1;
1396         }
1397         num_bits_table[t]=bits;
1398     }
1399 }
1400
1401 static int png_find_best_filter(unsigned char*src, unsigned width, int bpp, int y)
1402 {
1403     make_num_bits_table();
1404
1405     int num_filters = y>0?5:2; //don't apply y-direction filter in first line
1406
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;
1411
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);
1418
1419     unsigned char old[5];
1420     int l = bytes_per_pixel - 1;
1421     old[0] = src[l];
1422     old[1] = src[l];
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);
1426
1427     int different_pairs[5] = {0,0,0,0,0};
1428
1429     int x;
1430     for(x=bytes_per_pixel;x<w;x++) {
1431         unsigned char dest[5];
1432         dest[0] = src[x];
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]);
1437
1438         int i;
1439         for(i=0;i<5;i++) {
1440             int v = dest[i]<<8|old[i];
1441             int p = v>>3;
1442             int b = 1<<(v&7);
1443             if(!pairs[i][p]&b) {
1444                 pairs[i][p]|=b;
1445                 different_pairs[i]++;
1446             }
1447         }
1448         memcpy(old, dest, sizeof(old));
1449     }
1450     int f;
1451     int best_nr = 0;
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) {
1456             best_nr = f;
1457             best_energy = energy;
1458         }
1459     }
1460     free(pairs[0]);
1461     free(pairs[1]);
1462     free(pairs[2]);
1463     free(pairs[3]);
1464     free(pairs[4]);
1465     return best_nr;
1466 }
1467
1468
1469 static int png_apply_filter(unsigned char*dest, unsigned char*src, unsigned width, int y, int bpp)
1470 {
1471     int best_nr = 0;
1472 #if 0
1473     make_num_bits_table();
1474     int num_filters = y>0?5:2; //don't apply y-direction filter in first line
1475     int f;
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++) {
1481         if(bpp==8)
1482             png_apply_specific_filter_8(f, dest, src, width);
1483         else
1484             png_apply_specific_filter_32(f, dest, src, width);
1485         int x;
1486
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];
1493             int p = v>>3;
1494             int b = 1<<(v&7);
1495             if(!pairs[p]&b) {
1496                 pairs[p]|=b;
1497                 different_pairs ++;
1498             }
1499         }
1500         int energy = different_pairs;
1501         if(energy<best_energy) {
1502             best_nr = f;
1503             best_energy = energy;
1504         }
1505     }
1506     free(pairs);
1507 #else
1508     best_nr = png_find_best_filter(src, width, bpp, y);
1509 #endif
1510     if(bpp==8)
1511         png_apply_specific_filter_8(best_nr, dest, src, width);
1512     else
1513         png_apply_specific_filter_32(best_nr, dest, src, width);
1514     return best_nr;
1515 }
1516
1517 int png_apply_filter_8(unsigned char*dest, unsigned char*src, unsigned width, int y)
1518 {
1519     return png_apply_filter(dest, src, width, y, 8);
1520 }
1521 int png_apply_filter_32(unsigned char*dest, unsigned char*src, unsigned width, int y)
1522 {
1523     return png_apply_filter(dest, src, width, y, 32);
1524 }
1525
1526 EXPORT void savePNG(const char*filename, unsigned char*data, unsigned width, unsigned height, int numcolors)
1527 {
1528     FILE*fi;
1529     int crc;
1530     int t;
1531     unsigned char format;
1532     unsigned char tmp;
1533     unsigned char* data2=0;
1534     unsigned char head[] = {137,80,78,71,13,10,26,10}; // PNG header
1535     int cols;
1536     char alpha = 1;
1537     int pos = 0;
1538     int error;
1539     u32 tmp32;
1540     int bpp;
1541     int ret;
1542     char has_alpha=0;
1543     z_stream zs;
1544     COL palette[256];
1545
1546     make_crc32_table();
1547
1548     if(!numcolors) {
1549         int num = png_get_number_of_palette_entries((COL*)data, width, height, palette, &has_alpha);
1550         if(num<=255) {
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);
1554             data = data2;
1555             bpp = 8;
1556             cols = num;
1557             format = 3;
1558         } else {
1559             bpp = 32;
1560             cols = 0;
1561             format = 5;
1562         }
1563     } else {
1564         bpp = 8;
1565         cols = numcolors;
1566         format = 3;
1567         png_quantize_image(data, width*height, numcolors, &data, palette);
1568     }
1569
1570     fi = fopen(filename, "wb");
1571     if(!fi) {
1572         perror("open");
1573         return;
1574     }
1575     fwrite(head,sizeof(head),1,fi);
1576
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);
1581      if(format == 3)
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
1587      else return;
1588
1589      png_write_byte(fi,0); //compression mode
1590      png_write_byte(fi,0); //filter mode
1591      png_write_byte(fi,0); //interlace mode
1592     png_end_chunk(fi);
1593
1594     if(format == 3) {
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);
1600         }
1601         png_end_chunk(fi);
1602
1603         if(has_alpha) {
1604             png_start_chunk(fi, "tRNS", cols);
1605             for(t=0;t<cols;t++) {
1606                 png_write_byte(fi,palette[t].a);
1607             }
1608             png_end_chunk(fi);
1609         }
1610     }
1611
1612     long idatpos = png_start_chunk(fi, "IDAT", 0);
1613
1614     memset(&zs,0,sizeof(z_stream));
1615     Bytef*writebuf = (Bytef*)malloc(ZLIB_BUFFER_SIZE);
1616     zs.zalloc = Z_NULL;
1617     zs.zfree  = Z_NULL;
1618     zs.opaque = Z_NULL;
1619     zs.next_out = writebuf;
1620     zs.avail_out = ZLIB_BUFFER_SIZE;
1621     ret = deflateInit(&zs, Z_BEST_COMPRESSION);
1622     if (ret != Z_OK) {
1623         fprintf(stderr, "error in deflateInit(): %s", zs.msg?zs.msg:"unknown");
1624         return;
1625     }
1626
1627     long idatsize = 0;
1628     {
1629         int x,y;
1630         int bypp = bpp/8;
1631         unsigned srcwidth = width * bypp;
1632         unsigned linelen = 1 + srcwidth;
1633         if(bypp==2)
1634             linelen = 1 + ((srcwidth+1)&~1);
1635         else if(bypp==3)
1636             linelen = 1 + ((srcwidth+2)/3)*3;
1637         else if(bypp==4)
1638             linelen = 1 + ((srcwidth+3)&~3);
1639         unsigned char* line = (unsigned char*)malloc(linelen);
1640         memset(line, 0, linelen);
1641 #if 0
1642         unsigned char* bestline = (unsigned char*)malloc(linelen);
1643         memset(bestline, 0, linelen);
1644         for(y=0;y<height;y++)
1645         {
1646             int filtermode;
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
1651
1652                 line[0]=filtermode; //filter type
1653                 if(bpp==8)
1654                     png_apply_specific_filter_8(filtermode, line+1, &data[y*srcwidth], width);
1655                 else
1656                     png_apply_specific_filter_32(filtermode, line+1, &data[y*srcwidth], width);
1657
1658                 int size = test_line(&zs, line, linelen);
1659                 if(size < bestsize) {
1660                     memcpy(bestline, line, linelen);
1661                     bestsize = size;
1662                 }
1663             }
1664             idatsize += compress_line(&zs, bestline, linelen, fi);
1665         }
1666         free(bestline);
1667 #else
1668         for(y=0;y<height;y++) {
1669             if(bpp==8)
1670                 line[0] = png_apply_filter_8(line+1, &data[y*srcwidth], width, y);
1671             else
1672                 line[0] = png_apply_filter_32(line+1, &data[y*srcwidth], width, y);
1673
1674             idatsize += compress_line(&zs, line, linelen, fi);
1675         }
1676 #endif
1677         free(line);
1678     }
1679     idatsize += finishzlib(&zs, fi);
1680     png_patch_len(fi, idatpos, idatsize);
1681     png_end_chunk(fi);
1682
1683     png_start_chunk(fi, "IEND", 0);
1684     png_end_chunk(fi);
1685
1686     free(writebuf);
1687     if(data2)
1688         free(data2);
1689     fclose(fi);
1690 }
1691
1692 EXPORT void writePNG(const char*filename, unsigned char*data, unsigned width, unsigned height)
1693 {
1694     savePNG(filename, data, width, height, 0);
1695 }
1696 EXPORT void writePalettePNG(const char*filename, unsigned char*data, unsigned width, unsigned height)
1697 {
1698     savePNG(filename, data, width, height, 256);
1699 }