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