libraries/gd1.3/gd.c

   1 #include <stdio.h>
   2 #include <math.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 #include "gd.h"
   6 #include "mtables.c"
   7
   8 static void gdImageBrushApply(gdImagePtr im, int x, int y);
   9 static void gdImageTileApply(gdImagePtr im, int x, int y);
  10
  11 gdImagePtr gdImageCreate(int sx, int sy)
  12 {
  13         int i;
  14         gdImagePtr im;
  15         im = (gdImage *) calloc(1,sizeof(gdImage));
  16         /* NOW ROW-MAJOR IN GD 1.3 */
  17         im->pixels = (unsigned char **) malloc(sizeof(unsigned char *) * sy);
  18         im->polyInts = 0;
  19         im->polyAllocated = 0;
  20         im->brush = 0;
  21         im->tile = 0;
  22         im->style = 0;
  23         for (i=0; (i<sy); i++) {
  24                 /* NOW ROW-MAJOR IN GD 1.3 */
  25                 im->pixels[i] = (unsigned char *) calloc(
  26                         sx, sizeof(unsigned char));
  27         }
  28         im->sx = sx;
  29         im->sy = sy;
  30         im->colorsTotal = 0;
  31         im->transparent = (-1);
  32         im->interlace = 0;
  33         return im;
  34 }
  35
  36 void gdImageDestroy(gdImagePtr im)
  37 {
  38         int i;
  39         for (i=0; (i<im->sy); i++) {
  40                 free(im->pixels[i]);
  41         }
  42         free(im->pixels);
  43         if (im->polyInts) {
  44                         free(im->polyInts);
  45         }
  46         if (im->style) {
  47                 free(im->style);
  48         }
  49         free(im);
  50 }
  51
  52 int gdImageColorClosest(gdImagePtr im, int r, int g, int b)
  53 {
  54         int i;
  55         long rd, gd, bd;
  56         int ct = (-1);
  57         long mindist = 0;
  58         for (i=0; (i<(im->colorsTotal)); i++) {
  59                 long dist;
  60                 if (im->open[i]) {
  61                         continue;
  62                 }
  63                 rd = (im->red[i] - r);
  64                 gd = (im->green[i] - g);
  65                 bd = (im->blue[i] - b);
  66                 dist = rd * rd + gd * gd + bd * bd;
  67                 if ((i == 0) || (dist < mindist)) {
  68                         mindist = dist;
  69                         ct = i;
  70                 }
  71         }
  72         return ct;
  73 }
  74
  75 int gdImageColorExact(gdImagePtr im, int r, int g, int b)
  76 {
  77         int i;
  78         for (i=0; (i<(im->colorsTotal)); i++) {
  79                 if (im->open[i]) {
  80                         continue;
  81                 }
  82                 if ((im->red[i] == r) &&
  83                         (im->green[i] == g) &&
  84                         (im->blue[i] == b)) {
  85                         return i;
  86                 }
  87         }
  88         return -1;
  89 }
  90
  91 int gdImageColorAllocate(gdImagePtr im, int r, int g, int b)
  92 {
  93         int i;
  94         int ct = (-1);
  95         for (i=0; (i<(im->colorsTotal)); i++) {
  96                 if (im->open[i]) {
  97                         ct = i;
  98                         break;
  99                 }
 100         }
 101         if (ct == (-1)) {
 102                 ct = im->colorsTotal;
 103                 if (ct == gdMaxColors) {
 104                         return -1;
 105                 }
 106                 im->colorsTotal++;
 107         }
 108         im->red[ct] = r;
 109         im->green[ct] = g;
 110         im->blue[ct] = b;
 111         im->open[ct] = 0;
 112         return ct;
 113 }
 114
 115 void gdImageColorDeallocate(gdImagePtr im, int color)
 116 {
 117         /* Mark it open. */
 118         im->open[color] = 1;
 119 }
 120
 121 void gdImageColorTransparent(gdImagePtr im, int color)
 122 {
 123         im->transparent = color;
 124 }
 125
 126 void gdImageSetPixel(gdImagePtr im, int x, int y, int color)
 127 {
 128         int p;
 129         switch(color) {
 130                 case gdStyled:
 131                 if (!im->style) {
 132                         /* Refuse to draw if no style is set. */
 133                         return;
 134                 } else {
 135                         p = im->style[im->stylePos++];
 136                 }
 137                 if (p != (gdTransparent)) {
 138                         gdImageSetPixel(im, x, y, p);
 139                 }
 140                 im->stylePos = im->stylePos %  im->styleLength;
 141                 break;
 142                 case gdStyledBrushed:
 143                 if (!im->style) {
 144                         /* Refuse to draw if no style is set. */
 145                         return;
 146                 }
 147                 p = im->style[im->stylePos++];
 148                 if ((p != gdTransparent) && (p != 0)) {
 149                         gdImageSetPixel(im, x, y, gdBrushed);
 150                 }
 151                 im->stylePos = im->stylePos %  im->styleLength;
 152                 break;
 153                 case gdBrushed:
 154                 gdImageBrushApply(im, x, y);
 155                 break;
 156                 case gdTiled:
 157                 gdImageTileApply(im, x, y);
 158                 break;
 159                 default:
 160                 if (gdImageBoundsSafe(im, x, y)) {
 161                         /* NOW ROW-MAJOR IN GD 1.3 */
 162                         im->pixels[y][x] = color;
 163                 }
 164                 break;
 165         }
 166 }
 167
 168 static void gdImageBrushApply(gdImagePtr im, int x, int y)
 169 {
 170         int lx, ly;
 171         int hy;
 172         int hx;
 173         int x1, y1, x2, y2;
 174         int srcx, srcy;
 175         if (!im->brush) {
 176                 return;
 177         }
 178         hy = gdImageSY(im->brush)/2;
 179         y1 = y - hy;
 180         y2 = y1 + gdImageSY(im->brush);
 181         hx = gdImageSX(im->brush)/2;
 182         x1 = x - hx;
 183         x2 = x1 + gdImageSX(im->brush);
 184         srcy = 0;
 185         for (ly = y1; (ly < y2); ly++) {
 186                 srcx = 0;
 187                 for (lx = x1; (lx < x2); lx++) {
 188                         int p;
 189                         p = gdImageGetPixel(im->brush, srcx, srcy);
 190                         /* Allow for non-square brushes! */
 191                         if (p != gdImageGetTransparent(im->brush)) {
 192                                 gdImageSetPixel(im, lx, ly,
 193                                         im->brushColorMap[p]);
 194                         }
 195                         srcx++;
 196                 }
 197                 srcy++;
 198         }
 199 }
 200
 201 static void gdImageTileApply(gdImagePtr im, int x, int y)
 202 {
 203         int srcx, srcy;
 204         int p;
 205         if (!im->tile) {
 206                 return;
 207         }
 208         srcx = x % gdImageSX(im->tile);
 209         srcy = y % gdImageSY(im->tile);
 210         p = gdImageGetPixel(im->tile, srcx, srcy);
 211         /* Allow for transparency */
 212         if (p != gdImageGetTransparent(im->tile)) {
 213                 gdImageSetPixel(im, x, y,
 214                         im->tileColorMap[p]);
 215         }
 216 }
 217
 218 int gdImageGetPixel(gdImagePtr im, int x, int y)
 219 {
 220         if (gdImageBoundsSafe(im, x, y)) {
 221                 /* NOW ROW-MAJOR IN GD 1.3 */
 222                 return im->pixels[y][x];
 223         } else {
 224                 return 0;
 225         }
 226 }
 227
 228 /* Bresenham as presented in Foley & Van Dam */
 229
 230 void gdImageLine(gdImagePtr im, int x1, int y1, int x2, int y2, int color)
 231 {
 232         int dx, dy, incr1, incr2, d, x, y, xend, yend, xdirflag, ydirflag;
 233         dx = abs(x2-x1);
 234         dy = abs(y2-y1);
 235         if (dy <= dx) {
 236                 d = 2*dy - dx;
 237                 incr1 = 2*dy;
 238                 incr2 = 2 * (dy - dx);
 239                 if (x1 > x2) {
 240                         x = x2;
 241                         y = y2;
 242                         ydirflag = (-1);
 243                         xend = x1;
 244                 } else {
 245                         x = x1;
 246                         y = y1;
 247                         ydirflag = 1;
 248                         xend = x2;
 249                 }
 250                 gdImageSetPixel(im, x, y, color);
 251                 if (((y2 - y1) * ydirflag) > 0) {
 252                         while (x < xend) {
 253                                 x++;
 254                                 if (d <0) {
 255                                         d+=incr1;
 256                                 } else {
 257                                         y++;
 258                                         d+=incr2;
 259                                 }
 260                                 gdImageSetPixel(im, x, y, color);
 261                         }
 262                 } else {
 263                         while (x < xend) {
 264                                 x++;
 265                                 if (d <0) {
 266                                         d+=incr1;
 267                                 } else {
 268                                         y--;
 269                                         d+=incr2;
 270                                 }
 271                                 gdImageSetPixel(im, x, y, color);
 272                         }
 273                 }
 274         } else {
 275                 d = 2*dx - dy;
 276                 incr1 = 2*dx;
 277                 incr2 = 2 * (dx - dy);
 278                 if (y1 > y2) {
 279                         y = y2;
 280                         x = x2;
 281                         yend = y1;
 282                         xdirflag = (-1);
 283                 } else {
 284                         y = y1;
 285                         x = x1;
 286                         yend = y2;
 287                         xdirflag = 1;
 288                 }
 289                 gdImageSetPixel(im, x, y, color);
 290                 if (((x2 - x1) * xdirflag) > 0) {
 291                         while (y < yend) {
 292                                 y++;
 293                                 if (d <0) {
 294                                         d+=incr1;
 295                                 } else {
 296                                         x++;
 297                                         d+=incr2;
 298                                 }
 299                                 gdImageSetPixel(im, x, y, color);
 300                         }
 301                 } else {
 302                         while (y < yend) {
 303                                 y++;
 304                                 if (d <0) {
 305                                         d+=incr1;
 306                                 } else {
 307                                         x--;
 308                                         d+=incr2;
 309                                 }
 310                                 gdImageSetPixel(im, x, y, color);
 311                         }
 312                 }
 313         }
 314 }
 315
 316 static void dashedSet(gdImagePtr im, int x, int y, int color,
 317         int *onP, int *dashStepP);
 318
 319 void gdImageDashedLine(gdImagePtr im, int x1, int y1, int x2, int y2, int color)
 320 {
 321         int dx, dy, incr1, incr2, d, x, y, xend, yend, xdirflag, ydirflag;
 322         int dashStep = 0;
 323         int on = 1;
 324         dx = abs(x2-x1);
 325         dy = abs(y2-y1);
 326         if (dy <= dx) {
 327                 d = 2*dy - dx;
 328                 incr1 = 2*dy;
 329                 incr2 = 2 * (dy - dx);
 330                 if (x1 > x2) {
 331                         x = x2;
 332                         y = y2;
 333                         ydirflag = (-1);
 334                         xend = x1;
 335                 } else {
 336                         x = x1;
 337                         y = y1;
 338                         ydirflag = 1;
 339                         xend = x2;
 340                 }
 341                 dashedSet(im, x, y, color, &on, &dashStep);
 342                 if (((y2 - y1) * ydirflag) > 0) {
 343                         while (x < xend) {
 344                                 x++;
 345                                 if (d <0) {
 346                                         d+=incr1;
 347                                 } else {
 348                                         y++;
 349                                         d+=incr2;
 350                                 }
 351                                 dashedSet(im, x, y, color, &on, &dashStep);
 352                         }
 353                 } else {
 354                         while (x < xend) {
 355                                 x++;
 356                                 if (d <0) {
 357                                         d+=incr1;
 358                                 } else {
 359                                         y--;
 360                                         d+=incr2;
 361                                 }
 362                                 dashedSet(im, x, y, color, &on, &dashStep);
 363                         }
 364                 }
 365         } else {
 366                 d = 2*dx - dy;
 367                 incr1 = 2*dx;
 368                 incr2 = 2 * (dx - dy);
 369                 if (y1 > y2) {
 370                         y = y2;
 371                         x = x2;
 372                         yend = y1;
 373                         xdirflag = (-1);
 374                 } else {
 375                         y = y1;
 376                         x = x1;
 377                         yend = y2;
 378                         xdirflag = 1;
 379                 }
 380                 dashedSet(im, x, y, color, &on, &dashStep);
 381                 if (((x2 - x1) * xdirflag) > 0) {
 382                         while (y < yend) {
 383                                 y++;
 384                                 if (d <0) {
 385                                         d+=incr1;
 386                                 } else {
 387                                         x++;
 388                                         d+=incr2;
 389                                 }
 390                                 dashedSet(im, x, y, color, &on, &dashStep);
 391                         }
 392                 } else {
 393                         while (y < yend) {
 394                                 y++;
 395                                 if (d <0) {
 396                                         d+=incr1;
 397                                 } else {
 398                                         x--;
 399                                         d+=incr2;
 400                                 }
 401                                 dashedSet(im, x, y, color, &on, &dashStep);
 402                         }
 403                 }
 404         }
 405 }
 406
 407 static void dashedSet(gdImagePtr im, int x, int y, int color,
 408         int *onP, int *dashStepP)
 409 {
 410         int dashStep = *dashStepP;
 411         int on = *onP;
 412         dashStep++;
 413         if (dashStep == gdDashSize) {
 414                 dashStep = 0;
 415                 on = !on;
 416         }
 417         if (on) {
 418                 gdImageSetPixel(im, x, y, color);
 419         }
 420         *dashStepP = dashStep;
 421         *onP = on;
 422 }
 423
 424
 425 int gdImageBoundsSafe(gdImagePtr im, int x, int y)
 426 {
 427         return (!(((y < 0) || (y >= im->sy)) ||
 428                 ((x < 0) || (x >= im->sx))));
 429 }
 430
 431 void gdImageChar(gdImagePtr im, gdFontPtr f, int x, int y,
 432         int c, int color)
 433 {
 434         int cx, cy;
 435         int px, py;
 436         int fline;
 437         cx = 0;
 438         cy = 0;
 439         if ((c < f->offset) || (c >= (f->offset + f->nchars))) {
 440                 return;
 441         }
 442         fline = (c - f->offset) * f->h * f->w;
 443         for (py = y; (py < (y + f->h)); py++) {
 444                 for (px = x; (px < (x + f->w)); px++) {
 445                         if (f->data[fline + cy * f->w + cx]) {
 446                                 gdImageSetPixel(im, px, py, color);
 447                         }
 448                         cx++;
 449                 }
 450                 cx = 0;
 451                 cy++;
 452         }
 453 }
 454
 455 void gdImageCharUp(gdImagePtr im, gdFontPtr f,
 456         int x, int y, int c, int color)
 457 {
 458         int cx, cy;
 459         int px, py;
 460         int fline;
 461         cx = 0;
 462         cy = 0;
 463         if ((c < f->offset) || (c >= (f->offset + f->nchars))) {
 464                 return;
 465         }
 466         fline = (c - f->offset) * f->h * f->w;
 467         for (py = y; (py > (y - f->w)); py--) {
 468                 for (px = x; (px < (x + f->h)); px++) {
 469                         if (f->data[fline + cy * f->w + cx]) {
 470                                 gdImageSetPixel(im, px, py, color);
 471                         }
 472                         cy++;
 473                 }
 474                 cy = 0;
 475                 cx++;
 476         }
 477 }
 478
 479 void gdImageString(gdImagePtr im, gdFontPtr f,
 480         int x, int y, unsigned char *s, int color)
 481 {
 482         int i;
 483         int l;
 484         l = strlen(s);
 485         for (i=0; (i<l); i++) {
 486                 gdImageChar(im, f, x, y, s[i], color);
 487                 x += f->w;
 488         }
 489 }
 490
 491 void gdImageStringUp(gdImagePtr im, gdFontPtr f,
 492         int x, int y, unsigned char *s, int color)
 493 {
 494         int i;
 495         int l;
 496         l = strlen(s);
 497         for (i=0; (i<l); i++) {
 498                 gdImageCharUp(im, f, x, y, s[i], color);
 499                 y -= f->w;
 500         }
 501 }
 502
 503 static int strlen16(unsigned short *s);
 504
 505 void gdImageString16(gdImagePtr im, gdFontPtr f,
 506         int x, int y, unsigned short *s, int color)
 507 {
 508         int i;
 509         int l;
 510         l = strlen16(s);
 511         for (i=0; (i<l); i++) {
 512                 gdImageChar(im, f, x, y, s[i], color);
 513                 x += f->w;
 514         }
 515 }
 516
 517 void gdImageStringUp16(gdImagePtr im, gdFontPtr f,
 518         int x, int y, unsigned short *s, int color)
 519 {
 520         int i;
 521         int l;
 522         l = strlen16(s);
 523         for (i=0; (i<l); i++) {
 524                 gdImageCharUp(im, f, x, y, s[i], color);
 525                 y -= f->w;
 526         }
 527 }
 528
 529 static int strlen16(unsigned short *s)
 530 {
 531         int len = 0;
 532         while (*s) {
 533                 s++;
 534                 len++;
 535         }
 536         return len;
 537 }
 538
 539 /* s and e are integers modulo 360 (degrees), with 0 degrees
 540   being the rightmost extreme and degrees changing clockwise.
 541   cx and cy are the center in pixels; w and h are the horizontal
 542   and vertical diameter in pixels. Nice interface, but slow, since
 543   I don't yet use Bresenham (I'm using an inefficient but
 544   simple solution with too much work going on in it; generalizing
 545   Bresenham to ellipses and partial arcs of ellipses is non-trivial,
 546   at least for me) and there are other inefficiencies (small circles
 547   do far too much work). */
 548
 549 void gdImageArc(gdImagePtr im, int cx, int cy, int w, int h, int s, int e, int color)
 550 {
 551         int i;
 552         int lx = 0, ly = 0;
 553         int w2, h2;
 554         w2 = w/2;
 555         h2 = h/2;
 556         while (e < s) {
 557                 e += 360;
 558         }
 559         for (i=s; (i <= e); i++) {
 560                 int x, y;
 561                 x = ((long)cost[i % 360] * (long)w2 / costScale) + cx;
 562                 y = ((long)sint[i % 360] * (long)h2 / sintScale) + cy;
 563                 if (i != s) {
 564                         gdImageLine(im, lx, ly, x, y, color);
 565                 }
 566                 lx = x;
 567                 ly = y;
 568         }
 569 }
 570
 571
 572 #if 0
 573         /* Bresenham octant code, which I should use eventually */
 574         int x, y, d;
 575         x = 0;
 576         y = w;
 577         d = 3-2*w;
 578         while (x < y) {
 579                 gdImageSetPixel(im, cx+x, cy+y, color);
 580                 if (d < 0) {
 581                         d += 4 * x + 6;
 582                 } else {
 583                         d += 4 * (x - y) + 10;
 584                         y--;
 585                 }
 586                 x++;
 587         }
 588         if (x == y) {
 589                 gdImageSetPixel(im, cx+x, cy+y, color);
 590         }
 591 #endif
 592
 593 void gdImageFillToBorder(gdImagePtr im, int x, int y, int border, int color)
 594 {
 595         int lastBorder;
 596         /* Seek left */
 597         int leftLimit, rightLimit;
 598         int i;
 599         leftLimit = (-1);
 600         if (border < 0) {
 601                 /* Refuse to fill to a non-solid border */
 602                 return;
 603         }
 604         for (i = x; (i >= 0); i--) {
 605                 if (gdImageGetPixel(im, i, y) == border) {
 606                         break;
 607                 }
 608                 gdImageSetPixel(im, i, y, color);
 609                 leftLimit = i;
 610         }
 611         if (leftLimit == (-1)) {
 612                 return;
 613         }
 614         /* Seek right */
 615         rightLimit = x;
 616         for (i = (x+1); (i < im->sx); i++) {
 617                 if (gdImageGetPixel(im, i, y) == border) {
 618                         break;
 619                 }
 620                 gdImageSetPixel(im, i, y, color);
 621                 rightLimit = i;
 622         }
 623         /* Look at lines above and below and start paints */
 624         /* Above */
 625         if (y > 0) {
 626                 lastBorder = 1;
 627                 for (i = leftLimit; (i <= rightLimit); i++) {
 628                         int c;
 629                         c = gdImageGetPixel(im, i, y-1);
 630                         if (lastBorder) {
 631                                 if ((c != border) && (c != color)) {
 632                                         gdImageFillToBorder(im, i, y-1,
 633                                                 border, color);
 634                                         lastBorder = 0;
 635                                 }
 636                         } else if ((c == border) || (c == color)) {
 637                                 lastBorder = 1;
 638                         }
 639                 }
 640         }
 641         /* Below */
 642         if (y < ((im->sy) - 1)) {
 643                 lastBorder = 1;
 644                 for (i = leftLimit; (i <= rightLimit); i++) {
 645                         int c;
 646                         c = gdImageGetPixel(im, i, y+1);
 647                         if (lastBorder) {
 648                                 if ((c != border) && (c != color)) {
 649                                         gdImageFillToBorder(im, i, y+1,
 650                                                 border, color);
 651                                         lastBorder = 0;
 652                                 }
 653                         } else if ((c == border) || (c == color)) {
 654                                 lastBorder = 1;
 655                         }
 656                 }
 657         }
 658 }
 659
 660 void gdImageFill(gdImagePtr im, int x, int y, int color)
 661 {
 662         int lastBorder;
 663         int old;
 664         int leftLimit, rightLimit;
 665         int i;
 666         old = gdImageGetPixel(im, x, y);
 667         if (color == gdTiled) {
 668                 /* Tile fill -- got to watch out! */
 669                 int p, tileColor;
 670                 int srcx, srcy;
 671                 if (!im->tile) {
 672                         return;
 673                 }
 674                 /* Refuse to flood-fill with a transparent pattern --
 675                         I can't do it without allocating another image */
 676                 if (gdImageGetTransparent(im->tile) != (-1)) {
 677                         return;
 678                 }
 679                 srcx = x % gdImageSX(im->tile);
 680                 srcy = y % gdImageSY(im->tile);
 681                 p = gdImageGetPixel(im->tile, srcx, srcy);
 682                 tileColor = im->tileColorMap[p];
 683                 if (old == tileColor) {
 684                         /* Nothing to be done */
 685                         return;
 686                 }
 687         } else {
 688                 if (old == color) {
 689                         /* Nothing to be done */
 690                         return;
 691                 }
 692         }
 693         /* Seek left */
 694         leftLimit = (-1);
 695         for (i = x; (i >= 0); i--) {
 696                 if (gdImageGetPixel(im, i, y) != old) {
 697                         break;
 698                 }
 699                 gdImageSetPixel(im, i, y, color);
 700                 leftLimit = i;
 701         }
 702         if (leftLimit == (-1)) {
 703                 return;
 704         }
 705         /* Seek right */
 706         rightLimit = x;
 707         for (i = (x+1); (i < im->sx); i++) {
 708                 if (gdImageGetPixel(im, i, y) != old) {
 709                         break;
 710                 }
 711                 gdImageSetPixel(im, i, y, color);
 712                 rightLimit = i;
 713         }
 714         /* Look at lines above and below and start paints */
 715         /* Above */
 716         if (y > 0) {
 717                 lastBorder = 1;
 718                 for (i = leftLimit; (i <= rightLimit); i++) {
 719                         int c;
 720                         c = gdImageGetPixel(im, i, y-1);
 721                         if (lastBorder) {
 722                                 if (c == old) {
 723                                         gdImageFill(im, i, y-1, color);
 724                                         lastBorder = 0;
 725                                 }
 726                         } else if (c != old) {
 727                                 lastBorder = 1;
 728                         }
 729                 }
 730         }
 731         /* Below */
 732         if (y < ((im->sy) - 1)) {
 733                 lastBorder = 1;
 734                 for (i = leftLimit; (i <= rightLimit); i++) {
 735                         int c;
 736                         c = gdImageGetPixel(im, i, y+1);
 737                         if (lastBorder) {
 738                                 if (c == old) {
 739                                         gdImageFill(im, i, y+1, color);
 740                                         lastBorder = 0;
 741                                 }
 742                         } else if (c != old) {
 743                                 lastBorder = 1;
 744                         }
 745                 }
 746         }
 747 }
 748
 749 /* Code drawn from ppmtogif.c, from the pbmplus package
 750 **
 751 ** Based on GIFENCOD by David Rowley <mgardi@watdscu.waterloo.edu>. A
 752 ** Lempel-Zim compression based on "compress".
 753 **
 754 ** Modified by Marcel Wijkstra <wijkstra@fwi.uva.nl>
 755 **
 756 ** Copyright (C) 1989 by Jef Poskanzer.
 757 **
 758 ** Permission to use, copy, modify, and distribute this software and its
 759 ** documentation for any purpose and without fee is hereby granted, provided
 760 ** that the above copyright notice appear in all copies and that both that
 761 ** copyright notice and this permission notice appear in supporting
 762 ** documentation.  This software is provided "as is" without express or
 763 ** implied warranty.
 764 **
 765 ** The Graphics Interchange Format(c) is the Copyright property of
 766 ** CompuServe Incorporated.  GIF(sm) is a Service Mark property of
 767 ** CompuServe Incorporated.
 768 *
 769 *  Heavily modified by Mouse, 1998-02-12.
 770 *  Remove LZW compression.
 771 *  Added miGIF run length compression.
 772 *
 773 */
 774
 775 /*
 776  * a code_int must be able to hold 2**GIFBITS values of type int, and also -1
 777  */
 778 typedef int code_int;
 779
 780 static int colorstobpp(int colors);
 781 static void BumpPixel (void);
 782 static int GIFNextPixel (gdImagePtr im);
 783 static void GIFEncode (FILE *fp, int GWidth, int GHeight, int GInterlace, int Background, int Transparent, int BitsPerPixel, int *Red, int *Green, int *Blue, gdImagePtr im);
 784 static void Putword (int w, FILE *fp);
 785 static void compress (int, FILE *, gdImagePtr, int);
 786 static void output (code_int code);
 787 /* Allows for reuse */
 788 static void init_statics(void);
 789
 790 void gdImageGif(gdImagePtr im, FILE *out)
 791 {
 792         int interlace, transparent, BitsPerPixel;
 793         interlace = im->interlace;
 794         transparent = im->transparent;
 795
 796         BitsPerPixel = colorstobpp(im->colorsTotal);
 797         /* Clear any old values in statics strewn through the GIF code */
 798         init_statics();
 799         /* All set, let's do it. */
 800         GIFEncode(
 801                 out, im->sx, im->sy, interlace, 0, transparent, BitsPerPixel,
 802                 im->red, im->green, im->blue, im);
 803 }
 804
 805 static int
 806 colorstobpp(int colors)
 807 {
 808     int bpp = 0;
 809
 810     if ( colors <= 2 )
 811         bpp = 1;
 812     else if ( colors <= 4 )
 813         bpp = 2;
 814     else if ( colors <= 8 )
 815         bpp = 3;
 816     else if ( colors <= 16 )
 817         bpp = 4;
 818     else if ( colors <= 32 )
 819         bpp = 5;
 820     else if ( colors <= 64 )
 821         bpp = 6;
 822     else if ( colors <= 128 )
 823         bpp = 7;
 824     else if ( colors <= 256 )
 825         bpp = 8;
 826     return bpp;
 827     }
 828
 829 /*****************************************************************************
 830  *
 831  * GIFENCODE.C    - GIF Image compression interface
 832  *
 833  * GIFEncode( FName, GHeight, GWidth, GInterlace, Background, Transparent,
 834  *            BitsPerPixel, Red, Green, Blue, gdImagePtr )
 835  *
 836  *****************************************************************************/
 837
 838 #define TRUE 1
 839 #define FALSE 0
 840
 841 static int Width, Height;
 842 static int curx, cury;
 843 static long CountDown;
 844 static int Pass = 0;
 845 static int Interlace;
 846
 847 /*
 848  * Bump the 'curx' and 'cury' to point to the next pixel
 849  */
 850 static void
 851 BumpPixel(void)
 852 {
 853         /*
 854          * Bump the current X position
 855          */
 856         ++curx;
 857
 858         /*
 859          * If we are at the end of a scan line, set curx back to the beginning
 860          * If we are interlaced, bump the cury to the appropriate spot,
 861          * otherwise, just increment it.
 862          */
 863         if( curx == Width ) {
 864                 curx = 0;
 865
 866                 if( !Interlace )
 867                         ++cury;
 868                 else {
 869                      switch( Pass ) {
 870
 871                        case 0:
 872                           cury += 8;
 873                           if( cury >= Height ) {
 874                                 ++Pass;
 875                                 cury = 4;
 876                           }
 877                           break;
 878
 879                        case 1:
 880                           cury += 8;
 881                           if( cury >= Height ) {
 882                                 ++Pass;
 883                                 cury = 2;
 884                           }
 885                           break;
 886
 887                        case 2:
 888                           cury += 4;
 889                           if( cury >= Height ) {
 890                              ++Pass;
 891                              cury = 1;
 892                           }
 893                           break;
 894
 895                        case 3:
 896                           cury += 2;
 897                           break;
 898                         }
 899                 }
 900         }
 901 }
 902
 903 /*
 904  * Return the next pixel from the image
 905  */
 906 static int
 907 GIFNextPixel(gdImagePtr im)
 908 {
 909         int r;
 910
 911         if( CountDown == 0 )
 912                 return EOF;
 913
 914         --CountDown;
 915
 916         r = gdImageGetPixel(im, curx, cury);
 917
 918         BumpPixel();
 919
 920         return r;
 921 }
 922
 923 /* public */
 924
 925 static void
 926 GIFEncode(FILE *fp, int GWidth, int GHeight, int GInterlace, int Background, int Transparent, int BitsPerPixel, int *Red, int *Green, int *Blue, gdImagePtr im)
 927 {
 928         int B;
 929         int RWidth, RHeight;
 930         int LeftOfs, TopOfs;
 931         int Resolution;
 932         int ColorMapSize;
 933         int InitCodeSize;
 934         int i;
 935
 936         Interlace = GInterlace;
 937
 938         ColorMapSize = 1 << BitsPerPixel;
 939
 940         RWidth = Width = GWidth;
 941         RHeight = Height = GHeight;
 942         LeftOfs = TopOfs = 0;
 943
 944         Resolution = BitsPerPixel;
 945
 946         /*
 947          * Calculate number of bits we are expecting
 948          */
 949         CountDown = (long)Width * (long)Height;
 950
 951         /*
 952          * Indicate which pass we are on (if interlace)
 953          */
 954         Pass = 0;
 955
 956         /*
 957          * The initial code size
 958          */
 959         if( BitsPerPixel <= 1 )
 960                 InitCodeSize = 2;
 961         else
 962                 InitCodeSize = BitsPerPixel;
 963
 964         /*
 965          * Set up the current x and y position
 966          */
 967         curx = cury = 0;
 968
 969         /*
 970          * Write the Magic header
 971          */
 972         fwrite( Transparent < 0 ? "GIF87a" : "GIF89a", 1, 6, fp );
 973
 974         /*
 975          * Write out the screen width and height
 976          */
 977         Putword( RWidth, fp );
 978         Putword( RHeight, fp );
 979
 980         /*
 981          * Indicate that there is a global colour map
 982          */
 983         B = 0x80;       /* Yes, there is a color map */
 984
 985         /*
 986          * OR in the resolution
 987          */
 988         B |= (Resolution - 1) << 4;
 989
 990         /*
 991          * OR in the Bits per Pixel
 992          */
 993         B |= (BitsPerPixel - 1);
 994
 995         /*
 996          * Write it out
 997          */
 998         fputc( B, fp );
 999
1000         /*
1001          * Write out the Background colour
1002          */
1003         fputc( Background, fp );
1004
1005         /*
1006          * Byte of 0's (future expansion)
1007          */
1008         fputc( 0, fp );
1009
1010         /*
1011          * Write out the Global Colour Map
1012          */
1013         for( i=0; i<ColorMapSize; ++i ) {
1014                 fputc( Red[i], fp );
1015                 fputc( Green[i], fp );
1016                 fputc( Blue[i], fp );
1017         }
1018
1019         /*
1020          * Write out extension for transparent colour index, if necessary.
1021          */
1022         if ( Transparent >= 0 ) {
1023             fputc( '!', fp );
1024             fputc( 0xf9, fp );
1025             fputc( 4, fp );
1026             fputc( 1, fp );
1027             fputc( 0, fp );
1028             fputc( 0, fp );
1029             fputc( (unsigned char) Transparent, fp );
1030             fputc( 0, fp );
1031         }
1032
1033         /*
1034          * Write an Image separator
1035          */
1036         fputc( ',', fp );
1037
1038         /*
1039          * Write the Image header
1040          */
1041
1042         Putword( LeftOfs, fp );
1043         Putword( TopOfs, fp );
1044         Putword( Width, fp );
1045         Putword( Height, fp );
1046
1047         /*
1048          * Write out whether or not the image is interlaced
1049          */
1050         if( Interlace )
1051                 fputc( 0x40, fp );
1052         else
1053                 fputc( 0x00, fp );
1054
1055         /*
1056          * Write out the initial code size
1057          */
1058         fputc( InitCodeSize, fp );
1059
1060         /*
1061          * Go and actually compress the data
1062          */
1063         compress( InitCodeSize+1, fp, im, Background );
1064
1065         /*
1066          * Write out a Zero-length packet (to end the series)
1067          */
1068         fputc( 0, fp );
1069
1070         /*
1071          * Write the GIF file terminator
1072          */
1073         fputc( ';', fp );
1074 }
1075
1076 /*
1077  * Write out a word to the GIF file
1078  */
1079 static void
1080 Putword(int w, FILE *fp)
1081 {
1082         fputc( w & 0xff, fp );
1083         fputc( (w / 256) & 0xff, fp );
1084 }
1085
1086 #define GIFBITS 12
1087
1088 /*-----------------------------------------------------------------------
1089  *
1090  * miGIF Compression - mouse and ivo's GIF-compatible compression
1091  *
1092  *          -run length encoding compression routines-
1093  *
1094  * Copyright (C) 1998 Hutchison Avenue Software Corporation
1095  *               http://www.hasc.com
1096  *               info@hasc.com
1097  *
1098  * Permission to use, copy, modify, and distribute this software and its
1099  * documentation for any purpose and without fee is hereby granted, provided
1100  * that the above copyright notice appear in all copies and that both that
1101  * copyright notice and this permission notice appear in supporting
1102  * documentation.  This software is provided "AS IS." The Hutchison Avenue
1103  * Software Corporation disclaims all warranties, either express or implied,
1104  * including but not limited to implied warranties of merchantability and
1105  * fitness for a particular purpose, with respect to this code and accompanying
1106  * documentation.
1107  *
1108  * The miGIF compression routines do not, strictly speaking, generate files
1109  * conforming to the GIF spec, since the image data is not LZW-compressed
1110  * (this is the point: in order to avoid transgression of the Unisys patent
1111  * on the LZW algorithm.)  However, miGIF generates data streams that any
1112  * reasonably sane LZW decompresser will decompress to what we want.
1113  *
1114  * miGIF compression uses run length encoding. It compresses horizontal runs
1115  * of pixels of the same color. This type of compression gives good results
1116  * on images with many runs, for example images with lines, text and solid
1117  * shapes on a solid-colored background. It gives little or no compression
1118  * on images with few runs, for example digital or scanned photos.
1119  *
1120  *                               der Mouse
1121  *                      mouse@rodents.montreal.qc.ca
1122  *            7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B
1123  *
1124  *                             ivo@hasc.com
1125  *
1126  * The Graphics Interchange Format(c) is the Copyright property of
1127  * CompuServe Incorporated.  GIF(sm) is a Service Mark property of
1128  * CompuServe Incorporated.
1129  *
1130  */
1131
1132 static int rl_pixel;
1133 static int rl_basecode;
1134 static int rl_count;
1135 static int rl_table_pixel;
1136 static int rl_table_max;
1137 static int just_cleared;
1138 static int out_bits;
1139 static int out_bits_init;
1140 static int out_count;
1141 static int out_bump;
1142 static int out_bump_init;
1143 static int out_clear;
1144 static int out_clear_init;
1145 static int max_ocodes;
1146 static int code_clear;
1147 static int code_eof;
1148 static unsigned int obuf;
1149 static int obits;
1150 static FILE *ofile;
1151 static unsigned char oblock[256];
1152 static int oblen;
1153
1154 /* Used only when debugging GIF compression code */
1155 /* #define DEBUGGING_ENVARS */
1156
1157 #ifdef DEBUGGING_ENVARS
1158
1159 static int verbose_set = 0;
1160 static int verbose;
1161 #define VERBOSE (verbose_set?verbose:set_verbose())
1162
1163 static int set_verbose(void)
1164 {
1165  verbose = !!getenv("GIF_VERBOSE");
1166  verbose_set = 1;
1167  return(verbose);
1168 }
1169
1170 #else
1171
1172 #define VERBOSE 0
1173
1174 #endif
1175
1176
1177 static const char *binformat(unsigned int v, int nbits)
1178 {
1179  static char bufs[8][64];
1180  static int bhand = 0;
1181  unsigned int bit;
1182  int bno;
1183  char *bp;
1184
1185  bhand --;
1186  if (bhand < 0) bhand = (sizeof(bufs)/sizeof(bufs[0]))-1;
1187  bp = &bufs[bhand][0];
1188  for (bno=nbits-1,bit=1U<<bno;bno>=0;bno--,bit>>=1)
1189   { *bp++ = (v & bit) ? '1' : '0';
1190     if (((bno&3) == 0) && (bno != 0)) *bp++ = '.';
1191   }
1192  *bp = '\0';
1193  return(&bufs[bhand][0]);
1194 }
1195
1196 static void write_block(void)
1197 {
1198  int i;
1199
1200  if (VERBOSE)
1201   { printf("write_block %d:",oblen);
1202     for (i=0;i<oblen;i++) printf(" %02x",oblock[i]);
1203     printf("\n");
1204   }
1205  fputc(oblen,ofile);
1206  fwrite(&oblock[0],1,oblen,ofile);
1207  oblen = 0;
1208 }
1209
1210 static void block_out(unsigned char c)
1211 {
1212  if (VERBOSE) printf("block_out %s\n",binformat(c,8));
1213  oblock[oblen++] = c;
1214  if (oblen >= 255) write_block();
1215 }
1216
1217 static void block_flush(void)
1218 {
1219  if (VERBOSE) printf("block_flush\n");
1220  if (oblen > 0) write_block();
1221 }
1222
1223 static void output(int val)
1224 {
1225  if (VERBOSE) printf("output %s [%s %d %d]\n",binformat(val,out_bits),binformat(obuf,obits),obits,out_bits);
1226  obuf |= val << obits;
1227  obits += out_bits;
1228  while (obits >= 8)
1229   { block_out(obuf&0xff);
1230     obuf >>= 8;
1231     obits -= 8;
1232   }
1233  if (VERBOSE) printf("output leaving [%s %d]\n",binformat(obuf,obits),obits);
1234 }
1235
1236 static void output_flush(void)
1237 {
1238  if (VERBOSE) printf("output_flush\n");
1239  if (obits > 0) block_out(obuf);
1240  block_flush();
1241 }
1242
1243 static void did_clear(void)
1244 {
1245  if (VERBOSE) printf("did_clear\n");
1246  out_bits = out_bits_init;
1247  out_bump = out_bump_init;
1248  out_clear = out_clear_init;
1249  out_count = 0;
1250  rl_table_max = 0;
1251  just_cleared = 1;
1252 }
1253
1254 static void output_plain(int c)
1255 {
1256  if (VERBOSE) printf("output_plain %s\n",binformat(c,out_bits));
1257  just_cleared = 0;
1258  output(c);
1259  out_count ++;
1260  if (out_count >= out_bump)
1261   { out_bits ++;
1262     out_bump += 1 << (out_bits - 1);
1263   }
1264  if (out_count >= out_clear)
1265   { output(code_clear);
1266     did_clear();
1267   }
1268 }
1269
1270 static unsigned int isqrt(unsigned int x)
1271 {
1272  unsigned int r;
1273  unsigned int v;
1274
1275  if (x < 2) return(x);
1276  for (v=x,r=1;v;v>>=2,r<<=1) ;
1277  while (1)
1278   { v = ((x / r) + r) / 2;
1279     if ((v == r) || (v == r+1)) return(r);
1280     r = v;
1281   }
1282 }
1283
1284 static unsigned int compute_triangle_count(unsigned int count, unsigned int nrepcodes)
1285 {
1286  unsigned int perrep;
1287  unsigned int ncost;
1288
1289  ncost = 0;
1290  perrep = (nrepcodes * (nrepcodes+1)) / 2;
1291  while (count >= perrep)
1292   { ncost += nrepcodes;
1293     count -= perrep;
1294   }
1295  if (count > 0)
1296   { unsigned int n;
1297     n = isqrt(count);
1298     while ((n*(n+1)) >= 2*count) n --;
1299     while ((n*(n+1)) < 2*count) n ++;
1300     ncost += n;
1301   }
1302  return(ncost);
1303 }
1304
1305 static void max_out_clear(void)
1306 {
1307  out_clear = max_ocodes;
1308 }
1309
1310 static void reset_out_clear(void)
1311 {
1312  out_clear = out_clear_init;
1313  if (out_count >= out_clear)
1314   { output(code_clear);
1315     did_clear();
1316   }
1317 }
1318
1319 static void rl_flush_fromclear(int count)
1320 {
1321  int n;
1322
1323  if (VERBOSE) printf("rl_flush_fromclear %d\n",count);
1324  max_out_clear();
1325  rl_table_pixel = rl_pixel;
1326  n = 1;
1327  while (count > 0)
1328   { if (n == 1)
1329      { rl_table_max = 1;
1330        output_plain(rl_pixel);
1331        count --;
1332      }
1333     else if (count >= n)
1334      { rl_table_max = n;
1335        output_plain(rl_basecode+n-2);
1336        count -= n;
1337      }
1338     else if (count == 1)
1339      { rl_table_max ++;
1340        output_plain(rl_pixel);
1341        count = 0;
1342      }
1343     else
1344      { rl_table_max ++;
1345        output_plain(rl_basecode+count-2);
1346        count = 0;
1347      }
1348     if (out_count == 0) n = 1; else n ++;
1349   }
1350  reset_out_clear();
1351  if (VERBOSE) printf("rl_flush_fromclear leaving table_max=%d\n",rl_table_max);
1352 }
1353
1354 static void rl_flush_clearorrep(int count)
1355 {
1356  int withclr;
1357
1358  if (VERBOSE) printf("rl_flush_clearorrep %d\n",count);
1359  withclr = 1 + compute_triangle_count(count,max_ocodes);
1360  if (withclr < count)
1361   { output(code_clear);
1362     did_clear();
1363     rl_flush_fromclear(count);
1364   }
1365  else
1366   { for (;count>0;count--) output_plain(rl_pixel);
1367   }
1368 }
1369
1370 static void rl_flush_withtable(int count)
1371 {
1372  int repmax;
1373  int repleft;
1374  int leftover;
1375
1376  if (VERBOSE) printf("rl_flush_withtable %d\n",count);
1377  repmax = count / rl_table_max;
1378  leftover = count % rl_table_max;
1379  repleft = (leftover ? 1 : 0);
1380  if (out_count+repmax+repleft > max_ocodes)
1381   { repmax = max_ocodes - out_count;
1382     leftover = count - (repmax * rl_table_max);
1383     repleft = 1 + compute_triangle_count(leftover,max_ocodes);
1384   }
1385  if (VERBOSE) printf("rl_flush_withtable repmax=%d leftover=%d repleft=%d\n",repmax,leftover,repleft);
1386  if (1+compute_triangle_count(count,max_ocodes) < repmax+repleft)
1387   { output(code_clear);
1388     did_clear();
1389     rl_flush_fromclear(count);
1390     return;
1391   }
1392  max_out_clear();
1393  for (;repmax>0;repmax--) output_plain(rl_basecode+rl_table_max-2);
1394  if (leftover)
1395   { if (just_cleared)
1396      { rl_flush_fromclear(leftover);
1397      }
1398     else if (leftover == 1)
1399      { output_plain(rl_pixel);
1400      }
1401     else
1402      { output_plain(rl_basecode+leftover-2);
1403      }
1404   }
1405  reset_out_clear();
1406 }
1407
1408 static void rl_flush(void)
1409 {
1410
1411  if (VERBOSE) printf("rl_flush [ %d %d\n",rl_count,rl_pixel);
1412  if (rl_count == 1)
1413   { output_plain(rl_pixel);
1414     rl_count = 0;
1415     if (VERBOSE) printf("rl_flush ]\n");
1416     return;
1417   }
1418  if (just_cleared)
1419   { rl_flush_fromclear(rl_count);
1420   }
1421  else if ((rl_table_max < 2) || (rl_table_pixel != rl_pixel))
1422   { rl_flush_clearorrep(rl_count);
1423   }
1424  else
1425   { rl_flush_withtable(rl_count);
1426   }
1427  if (VERBOSE) printf("rl_flush ]\n");
1428  rl_count = 0;
1429 }
1430
1431 static void compress(int init_bits, FILE *outfile, gdImagePtr im, int background)
1432 {
1433  int c;
1434
1435  ofile = outfile;
1436  obuf = 0;
1437  obits = 0;
1438  oblen = 0;
1439  code_clear = 1 << (init_bits - 1);
1440  code_eof = code_clear + 1;
1441  rl_basecode = code_eof + 1;
1442  out_bump_init = (1 << (init_bits - 1)) - 1;
1443  /* for images with a lot of runs, making out_clear_init larger will
1444     give better compression. */
1445  out_clear_init = (init_bits <= 3) ? 9 : (out_bump_init-1);
1446 #ifdef DEBUGGING_ENVARS
1447   { const char *ocienv;
1448     ocienv = getenv("GIF_OUT_CLEAR_INIT");
1449     if (ocienv)
1450      { out_clear_init = atoi(ocienv);
1451        if (VERBOSE) printf("[overriding out_clear_init to %d]\n",out_clear_init);
1452      }
1453   }
1454 #endif
1455  out_bits_init = init_bits;
1456  max_ocodes = (1 << GIFBITS) - ((1 << (out_bits_init - 1)) + 3);
1457  did_clear();
1458  output(code_clear);
1459  rl_count = 0;
1460  while (1)
1461   { c = GIFNextPixel(im);
1462     if ((rl_count > 0) && (c != rl_pixel)) rl_flush();
1463     if (c == EOF) break;
1464     if (rl_pixel == c)
1465      { rl_count ++;
1466      }
1467     else
1468      { rl_pixel = c;
1469        rl_count = 1;
1470      }
1471   }
1472  output(code_eof);
1473  output_flush();
1474 }
1475
1476 /*-----------------------------------------------------------------------
1477  *
1478  * End of miGIF section  - See copyright notice at start of section.
1479  *
1480  *-----------------------------------------------------------------------
1481
1482
1483  ******************************************************************************
1484  *
1485  * GIF Specific routines
1486  *
1487  ******************************************************************************/
1488
1489 /*
1490  * Number of characters so far in this 'packet'
1491  */
1492 static int a_count;
1493
1494 /*
1495  * Define the storage for the packet accumulator
1496  */
1497
1498 static void init_statics(void) {
1499         /* Some of these are properly initialized later. What I'm doing
1500                 here is making sure code that depends on C's initialization
1501                 of statics doesn't break when the code gets called more
1502                 than once. */
1503         Width = 0;
1504         Height = 0;
1505         curx = 0;
1506         cury = 0;
1507         CountDown = 0;
1508         Pass = 0;
1509         Interlace = 0;
1510         a_count = 0;
1511 }
1512
1513
1514 /* +-------------------------------------------------------------------+ */
1515 /* | Copyright 1990, 1991, 1993, David Koblas.  (koblas@netcom.com)    | */
1516 /* |   Permission to use, copy, modify, and distribute this software   | */
1517 /* |   and its documentation for any purpose and without fee is hereby | */
1518 /* |   granted, provided that the above copyright notice appear in all | */
1519 /* |   copies and that both that copyright notice and this permission  | */
1520 /* |   notice appear in supporting documentation.  This software is    | */
1521 /* |   provided "as is" without express or implied warranty.           | */
1522 /* +-------------------------------------------------------------------+ */
1523
1524
1525 #define        MAXCOLORMAPSIZE         256
1526
1527 #define        TRUE    1
1528 #define        FALSE   0
1529
1530 #define CM_RED         0
1531 #define CM_GREEN       1
1532 #define CM_BLUE                2
1533
1534 #define        MAX_LWZ_BITS            12
1535
1536 #define INTERLACE              0x40
1537 #define LOCALCOLORMAP  0x80
1538 #define BitSet(byte, bit)      (((byte) & (bit)) == (bit))
1539
1540 #define        ReadOK(file,buffer,len) (fread(buffer, len, 1, file) != 0)
1541
1542 #define LM_to_uint(a,b)                        (((b)<<8)|(a))
1543
1544 /* We may eventually want to use this information, but def it out for now */
1545 #if 0
1546 static struct {
1547        unsigned int    Width;
1548        unsigned int    Height;
1549        unsigned char   ColorMap[3][MAXCOLORMAPSIZE];
1550        unsigned int    BitPixel;
1551        unsigned int    ColorResolution;
1552        unsigned int    Background;
1553        unsigned int    AspectRatio;
1554 } GifScreen;
1555 #endif
1556
1557 int ZeroDataBlock;
1558
1559
1560 void gdImageRectangle(gdImagePtr im, int x1, int y1, int x2, int y2, int color)
1561 {
1562         gdImageLine(im, x1, y1, x2, y1, color);
1563         gdImageLine(im, x1, y2, x2, y2, color);
1564         gdImageLine(im, x1, y1, x1, y2, color);
1565         gdImageLine(im, x2, y1, x2, y2, color);
1566 }
1567
1568 void gdImageFilledRectangle(gdImagePtr im, int x1, int y1, int x2, int y2, int color)
1569 {
1570         int x, y;
1571         for (y=y1; (y<=y2); y++) {
1572                 for (x=x1; (x<=x2); x++) {
1573                         gdImageSetPixel(im, x, y, color);
1574                 }
1575         }
1576 }
1577
1578 void gdImageCopy(gdImagePtr dst, gdImagePtr src, int dstX, int dstY, int srcX, int srcY, int w, int h)
1579 {
1580         int c;
1581         int x, y;
1582         int tox, toy;
1583         int i;
1584         int colorMap[gdMaxColors];
1585         for (i=0; (i<gdMaxColors); i++) {
1586                 colorMap[i] = (-1);
1587         }
1588         toy = dstY;
1589         for (y=srcY; (y < (srcY + h)); y++) {
1590                 tox = dstX;
1591                 for (x=srcX; (x < (srcX + w)); x++) {
1592                         int nc;
1593                         c = gdImageGetPixel(src, x, y);
1594                         /* Added 7/24/95: support transparent copies */
1595                         if (gdImageGetTransparent(src) == c) {
1596                                 tox++;
1597                                 continue;
1598                         }
1599                         /* Have we established a mapping for this color? */
1600                         if (colorMap[c] == (-1)) {
1601                                 /* If it's the same image, mapping is trivial */
1602                                 if (dst == src) {
1603                                         nc = c;
1604                                 } else {
1605                                         /* First look for an exact match */
1606                                         nc = gdImageColorExact(dst,
1607                                                 src->red[c], src->green[c],
1608                                                 src->blue[c]);
1609                                 }
1610                                 if (nc == (-1)) {
1611                                         /* No, so try to allocate it */
1612                                         nc = gdImageColorAllocate(dst,
1613                                                 src->red[c], src->green[c],
1614                                                 src->blue[c]);
1615                                         /* If we're out of colors, go for the
1616                                                 closest color */
1617                                         if (nc == (-1)) {
1618                                                 nc = gdImageColorClosest(dst,
1619                                                         src->red[c], src->green[c],
1620                                                         src->blue[c]);
1621                                         }
1622                                 }
1623                                 colorMap[c] = nc;
1624                         }
1625                         gdImageSetPixel(dst, tox, toy, colorMap[c]);
1626                         tox++;
1627                 }
1628                 toy++;
1629         }
1630 }
1631
1632 void gdImageCopyResized(gdImagePtr dst, gdImagePtr src, int dstX, int dstY, int srcX, int srcY, int dstW, int dstH, int srcW, int srcH)
1633 {
1634         int c;
1635         int x, y;
1636         int tox, toy;
1637         int ydest;
1638         int i;
1639         int colorMap[gdMaxColors];
1640         /* Stretch vectors */
1641         int *stx;
1642         int *sty;
1643         /* We only need to use floating point to determine the correct
1644                 stretch vector for one line's worth. */
1645         double accum;
1646         stx = (int *) malloc(sizeof(int) * srcW);
1647         sty = (int *) malloc(sizeof(int) * srcH);
1648         accum = 0;
1649         for (i=0; (i < srcW); i++) {
1650                 int got;
1651                 accum += (double)dstW/(double)srcW;
1652                 got = floor(accum);
1653                 stx[i] = got;
1654                 accum -= got;
1655         }
1656         accum = 0;
1657         for (i=0; (i < srcH); i++) {
1658                 int got;
1659                 accum += (double)dstH/(double)srcH;
1660                 got = floor(accum);
1661                 sty[i] = got;
1662                 accum -= got;
1663         }
1664         for (i=0; (i<gdMaxColors); i++) {
1665                 colorMap[i] = (-1);
1666         }
1667         toy = dstY;
1668         for (y=srcY; (y < (srcY + srcH)); y++) {
1669                 for (ydest=0; (ydest < sty[y-srcY]); ydest++) {
1670                         tox = dstX;
1671                         for (x=srcX; (x < (srcX + srcW)); x++) {
1672                                 int nc;
1673                                 if (!stx[x - srcX]) {
1674                                         continue;
1675                                 }
1676                                 c = gdImageGetPixel(src, x, y);
1677                                 /* Added 7/24/95: support transparent copies */
1678                                 if (gdImageGetTransparent(src) == c) {
1679                                         tox += stx[x-srcX];
1680                                         continue;
1681                                 }
1682                                 /* Have we established a mapping for this color? */
1683                                 if (colorMap[c] == (-1)) {
1684                                         /* If it's the same image, mapping is trivial */
1685                                         if (dst == src) {
1686                                                 nc = c;
1687                                         } else {
1688                                                 /* First look for an exact match */
1689                                                 nc = gdImageColorExact(dst,
1690                                                         src->red[c], src->green[c],
1691                                                         src->blue[c]);
1692                                         }
1693                                         if (nc == (-1)) {
1694                                                 /* No, so try to allocate it */
1695                                                 nc = gdImageColorAllocate(dst,
1696                                                         src->red[c], src->green[c],
1697                                                         src->blue[c]);
1698                                                 /* If we're out of colors, go for the
1699                                                         closest color */
1700                                                 if (nc == (-1)) {
1701                                                         nc = gdImageColorClosest(dst,
1702                                                                 src->red[c], src->green[c],
1703                                                                 src->blue[c]);
1704                                                 }
1705                                         }
1706                                         colorMap[c] = nc;
1707                                 }
1708                                 for (i=0; (i < stx[x - srcX]); i++) {
1709                                         gdImageSetPixel(dst, tox, toy, colorMap[c]);
1710                                         tox++;
1711                                 }
1712                         }
1713                         toy++;
1714                 }
1715         }
1716         free(stx);
1717         free(sty);
1718 }
1719
1720 int gdGetWord(int *result, FILE *in)
1721 {
1722         int r;
1723         r = getc(in);
1724         if (r == EOF) {
1725                 return 0;
1726         }
1727         *result = r << 8;
1728         r = getc(in);
1729         if (r == EOF) {
1730                 return 0;
1731         }
1732         *result += r;
1733         return 1;
1734 }
1735
1736 void gdPutWord(int w, FILE *out)
1737 {
1738         putc((unsigned char)(w >> 8), out);
1739         putc((unsigned char)(w & 0xFF), out);
1740 }
1741
1742 int gdGetByte(int *result, FILE *in)
1743 {
1744         int r;
1745         r = getc(in);
1746         if (r == EOF) {
1747                 return 0;
1748         }
1749         *result = r;
1750         return 1;
1751 }
1752
1753 gdImagePtr gdImageCreateFromGd(FILE *in)
1754 {
1755         int sx, sy;
1756         int x, y;
1757         int i;
1758         gdImagePtr im;
1759         if (!gdGetWord(&sx, in)) {
1760                 goto fail1;
1761         }
1762         if (!gdGetWord(&sy, in)) {
1763                 goto fail1;
1764         }
1765         im = gdImageCreate(sx, sy);
1766         if (!gdGetByte(&im->colorsTotal, in)) {
1767                 goto fail2;
1768         }
1769         if (!gdGetWord(&im->transparent, in)) {
1770                 goto fail2;
1771         }
1772         if (im->transparent == 257) {
1773                 im->transparent = (-1);
1774         }
1775         for (i=0; (i<gdMaxColors); i++) {
1776                 if (!gdGetByte(&im->red[i], in)) {
1777                         goto fail2;
1778                 }
1779                 if (!gdGetByte(&im->green[i], in)) {
1780                         goto fail2;
1781                 }
1782                 if (!gdGetByte(&im->blue[i], in)) {
1783                         goto fail2;
1784                 }
1785         }
1786         for (y=0; (y<sy); y++) {
1787                 for (x=0; (x<sx); x++) {
1788                         int ch;
1789                         ch = getc(in);
1790                         if (ch == EOF) {
1791                                 gdImageDestroy(im);
1792                                 return 0;
1793                         }
1794                         /* ROW-MAJOR IN GD 1.3 */
1795                         im->pixels[y][x] = ch;
1796                 }
1797         }
1798         return im;
1799 fail2:
1800         gdImageDestroy(im);
1801 fail1:
1802         return 0;
1803 }
1804
1805 void gdImageGd(gdImagePtr im, FILE *out)
1806 {
1807         int x, y;
1808         int i;
1809         int trans;
1810         gdPutWord(im->sx, out);
1811         gdPutWord(im->sy, out);
1812         putc((unsigned char)im->colorsTotal, out);
1813         trans = im->transparent;
1814         if (trans == (-1)) {
1815                 trans = 257;
1816         }
1817         gdPutWord(trans, out);
1818         for (i=0; (i<gdMaxColors); i++) {
1819                 putc((unsigned char)im->red[i], out);
1820                 putc((unsigned char)im->green[i], out);
1821                 putc((unsigned char)im->blue[i], out);
1822         }
1823         for (y=0; (y < im->sy); y++) {
1824                 for (x=0; (x < im->sx); x++) {
1825                         /* ROW-MAJOR IN GD 1.3 */
1826                         putc((unsigned char)im->pixels[y][x], out);
1827                 }
1828         }
1829 }
1830
1831 gdImagePtr
1832 gdImageCreateFromXbm(FILE *fd)
1833 {
1834         gdImagePtr im;
1835         int bit;
1836         int w, h;
1837         int bytes;
1838         int ch;
1839         int i, x, y;
1840         char *sp;
1841         char s[161];
1842         if (!fgets(s, 160, fd)) {
1843                 return 0;
1844         }
1845         sp = &s[0];
1846         /* Skip #define */
1847         sp = strchr(sp, ' ');
1848         if (!sp) {
1849                 return 0;
1850         }
1851         /* Skip width label */
1852         sp++;
1853         sp = strchr(sp, ' ');
1854         if (!sp) {
1855                 return 0;
1856         }
1857         /* Get width */
1858         w = atoi(sp + 1);
1859         if (!w) {
1860                 return 0;
1861         }
1862         if (!fgets(s, 160, fd)) {
1863                 return 0;
1864         }
1865         sp = s;
1866         /* Skip #define */
1867         sp = strchr(sp, ' ');
1868         if (!sp) {
1869                 return 0;
1870         }
1871         /* Skip height label */
1872         sp++;
1873         sp = strchr(sp, ' ');
1874         if (!sp) {
1875                 return 0;
1876         }
1877         /* Get height */
1878         h = atoi(sp + 1);
1879         if (!h) {
1880                 return 0;
1881         }
1882         /* Skip declaration line */
1883         if (!fgets(s, 160, fd)) {
1884                 return 0;
1885         }
1886         bytes = (w * h / 8) + 1;
1887         im = gdImageCreate(w, h);
1888         gdImageColorAllocate(im, 255, 255, 255);
1889         gdImageColorAllocate(im, 0, 0, 0);
1890         x = 0;
1891         y = 0;
1892         for (i=0; (i < bytes); i++) {
1893                 char h[3];
1894                 int b;
1895                 /* Skip spaces, commas, CRs, 0x */
1896                 while(1) {
1897                         ch = getc(fd);
1898                         if (ch == EOF) {
1899                                 goto fail;
1900                         }
1901                         if (ch == 'x') {
1902                                 break;
1903                         }
1904                 }
1905                 /* Get hex value */
1906                 ch = getc(fd);
1907                 if (ch == EOF) {
1908                         goto fail;
1909                 }
1910                 h[0] = ch;
1911                 ch = getc(fd);
1912                 if (ch == EOF) {
1913                         goto fail;
1914                 }
1915                 h[1] = ch;
1916                 h[2] = '\0';
1917                 sscanf(h, "%x", &b);
1918                 for (bit = 1; (bit <= 128); (bit = bit << 1)) {
1919                         gdImageSetPixel(im, x++, y, (b & bit) ? 1 : 0);
1920                         if (x == im->sx) {
1921                                 x = 0;
1922                                 y++;
1923                                 if (y == im->sy) {
1924                                         return im;
1925                                 }
1926                                 /* Fix 8/8/95 */
1927                                 break;
1928                         }
1929                 }
1930         }
1931         /* Shouldn't happen */
1932         fprintf(stderr, "Error: bug in gdImageCreateFromXbm!\n");
1933         return 0;
1934 fail:
1935         gdImageDestroy(im);
1936         return 0;
1937 }
1938
1939 void gdImagePolygon(gdImagePtr im, gdPointPtr p, int n, int c)
1940 {
1941         int i;
1942         int lx, ly;
1943         if (!n) {
1944                 return;
1945         }
1946         lx = p->x;
1947         ly = p->y;
1948         gdImageLine(im, lx, ly, p[n-1].x, p[n-1].y, c);
1949         for (i=1; (i < n); i++) {
1950                 p++;
1951                 gdImageLine(im, lx, ly, p->x, p->y, c);
1952                 lx = p->x;
1953                 ly = p->y;
1954         }
1955 }
1956
1957 int gdCompareInt(const void *a, const void *b);
1958
1959 void gdImageFilledPolygon(gdImagePtr im, gdPointPtr p, int n, int c)
1960 {
1961         int i;
1962         int y;
1963         int y1, y2;
1964         int ints;
1965         if (!n) {
1966                 return;
1967         }
1968         if (!im->polyAllocated) {
1969                 im->polyInts = (int *) malloc(sizeof(int) * n);
1970                 im->polyAllocated = n;
1971         }
1972         if (im->polyAllocated < n) {
1973                 while (im->polyAllocated < n) {
1974                         im->polyAllocated *= 2;
1975                 }
1976                 im->polyInts = (int *) realloc(im->polyInts,
1977                         sizeof(int) * im->polyAllocated);
1978         }
1979         y1 = p[0].y;
1980         y2 = p[0].y;
1981         for (i=1; (i < n); i++) {
1982                 if (p[i].y < y1) {
1983                         y1 = p[i].y;
1984                 }
1985                 if (p[i].y > y2) {
1986                         y2 = p[i].y;
1987                 }
1988         }
1989         /* Fix in 1.3: count a vertex only once */
1990         for (y=y1; (y < y2); y++) {
1991                 int interLast = 0;
1992                 int dirLast = 0;
1993                 int interFirst = 1;
1994                 ints = 0;
1995                 for (i=0; (i <= n); i++) {
1996                         int x1, x2;
1997                         int y1, y2;
1998                         int dir;
1999                         int ind1, ind2;
2000                         int lastInd1 = 0;
2001                         if ((i == n) || (!i)) {
2002                                 ind1 = n-1;
2003                                 ind2 = 0;
2004                         } else {
2005                                 ind1 = i-1;
2006                                 ind2 = i;
2007                         }
2008                         y1 = p[ind1].y;
2009                         y2 = p[ind2].y;
2010                         if (y1 < y2) {
2011                                 y1 = p[ind1].y;
2012                                 y2 = p[ind2].y;
2013                                 x1 = p[ind1].x;
2014                                 x2 = p[ind2].x;
2015                                 dir = -1;
2016                         } else if (y1 > y2) {
2017                                 y2 = p[ind1].y;
2018                                 y1 = p[ind2].y;
2019                                 x2 = p[ind1].x;
2020                                 x1 = p[ind2].x;
2021                                 dir = 1;
2022                         } else {
2023                                 /* Horizontal; just draw it */
2024                                 gdImageLine(im,
2025                                         p[ind1].x, y1,
2026                                         p[ind2].x, y1,
2027                                         c);
2028                                 continue;
2029                         }
2030                         if ((y >= y1) && (y <= y2)) {
2031                                 int inter =
2032                                         (y-y1) * (x2-x1) / (y2-y1) + x1;
2033                                 /* Only count intersections once
2034                                         except at maxima and minima. Also,
2035                                         if two consecutive intersections are
2036                                         endpoints of the same horizontal line
2037                                         that is not at a maxima or minima,
2038                                         discard the leftmost of the two. */
2039                                 if (!interFirst) {
2040                                         if ((p[ind1].y == p[lastInd1].y) &&
2041                                                 (p[ind1].x != p[lastInd1].x)) {
2042                                                 if (dir == dirLast) {
2043                                                         if (inter > interLast) {
2044                                                                 /* Replace the old one */
2045                                                                 im->polyInts[ints] = inter;
2046                                                         } else {
2047                                                                 /* Discard this one */
2048                                                         }
2049                                                         continue;
2050                                                 }
2051                                         }
2052                                         if (inter == interLast) {
2053                                                 if (dir == dirLast) {
2054                                                         continue;
2055                                                 }
2056                                         }
2057                                 }
2058                                 if (i > 0) {
2059                                         im->polyInts[ints++] = inter;
2060                                 }
2061                                 lastInd1 = i;
2062                                 dirLast = dir;
2063                                 interLast = inter;
2064                                 interFirst = 0;
2065                         }
2066                 }
2067                 qsort(im->polyInts, ints, sizeof(int), gdCompareInt);
2068                 for (i=0; (i < (ints-1)); i+=2) {
2069                         gdImageLine(im, im->polyInts[i], y,
2070                                 im->polyInts[i+1], y, c);
2071                 }
2072         }
2073 }
2074
2075 int gdCompareInt(const void *a, const void *b)
2076 {
2077         return (*(const int *)a) - (*(const int *)b);
2078 }
2079
2080 void gdImageSetStyle(gdImagePtr im, int *style, int noOfPixels)
2081 {
2082         if (im->style) {
2083                 free(im->style);
2084         }
2085         im->style = (int *)
2086                 malloc(sizeof(int) * noOfPixels);
2087         memcpy(im->style, style, sizeof(int) * noOfPixels);
2088         im->styleLength = noOfPixels;
2089         im->stylePos = 0;
2090 }
2091
2092 void gdImageSetBrush(gdImagePtr im, gdImagePtr brush)
2093 {
2094         int i;
2095         im->brush = brush;
2096         for (i=0; (i < gdImageColorsTotal(brush)); i++) {
2097                 int index;
2098                 index = gdImageColorExact(im,
2099                         gdImageRed(brush, i),
2100                         gdImageGreen(brush, i),
2101                         gdImageBlue(brush, i));
2102                 if (index == (-1)) {
2103                         index = gdImageColorAllocate(im,
2104                                 gdImageRed(brush, i),
2105                                 gdImageGreen(brush, i),
2106                                 gdImageBlue(brush, i));
2107                         if (index == (-1)) {
2108                                 index = gdImageColorClosest(im,
2109                                         gdImageRed(brush, i),
2110                                         gdImageGreen(brush, i),
2111                                         gdImageBlue(brush, i));
2112                         }
2113                 }
2114                 im->brushColorMap[i] = index;
2115         }
2116 }
2117
2118 void gdImageSetTile(gdImagePtr im, gdImagePtr tile)
2119 {
2120         int i;
2121         im->tile = tile;
2122         for (i=0; (i < gdImageColorsTotal(tile)); i++) {
2123                 int index;
2124                 index = gdImageColorExact(im,
2125                         gdImageRed(tile, i),
2126                         gdImageGreen(tile, i),
2127                         gdImageBlue(tile, i));
2128                 if (index == (-1)) {
2129                         index = gdImageColorAllocate(im,
2130                                 gdImageRed(tile, i),
2131                                 gdImageGreen(tile, i),
2132                                 gdImageBlue(tile, i));
2133                         if (index == (-1)) {
2134                                 index = gdImageColorClosest(im,
2135                                         gdImageRed(tile, i),
2136                                         gdImageGreen(tile, i),
2137                                         gdImageBlue(tile, i));
2138                         }
2139                 }
2140                 im->tileColorMap[i] = index;
2141         }
2142 }
2143
2144 void gdImageInterlace(gdImagePtr im, int interlaceArg)
2145 {
2146         im->interlace = interlaceArg;
2147 }