1 /*   gifgen.c
2 * ===========================================================================
3 *
4 *                            PUBLIC DOMAIN NOTICE
5 *            National Center for Biotechnology Information (NCBI)
6 *
7 *  This software/database is a "United States Government Work" under the
8 *  terms of the United States Copyright Act.  It was written as part of
9 *  the author's official duties as a United States Government employee and
10 *  thus cannot be copyrighted.  This software/database is freely available
11 *  to the public for use. The National Library of Medicine and the U.S.
12 *  Government do not place any restriction on its use or reproduction.
13 *  We would, however, appreciate having the NCBI and the author cited in
14 *  any work or product based on this material
15 *
16 *  Although all reasonable efforts have been taken to ensure the accuracy
17 *  and reliability of the software and data, the NLM and the U.S.
18 *  Government do not and cannot warrant the performance or results that
19 *  may be obtained by using this software or data. The NLM and the U.S.
20 *  Government disclaim all warranties, express or implied, including
21 *  warranties of performance, merchantability or fitness for any particular
22 *  purpose.
23 *
24 * ===========================================================================
25 */
26 
27 /* +-------------------------------------------------------------------+ */
28 /* | Copyright 1990, 1991, 1993, David Koblas.  (koblas@netcom.com)    | */
29 /* |   Permission to use, copy, modify, and distribute this software   | */
30 /* |   and its documentation for any purpose and without fee is hereby | */
31 /* |   granted, provided that the above copyright notice appear in all | */
32 /* |   copies and that both that copyright notice and this permission  | */
33 /* |   notice appear in supporting documentation.  This software is    | */
34 /* |   provided "as is" without express or implied warranty.           | */
35 /* +-------------------------------------------------------------------+ */
36 
37 /*
38  *
39  * File Name:  gifgen.c
40  *
41  * Author:  Alex Smirnov, Denis Vakatov
42  *
43  * Version Creation Date:   10/20/95
44  *
45  * File Description:
46  *       GIF drawing functions
47  *
48  * $Log: gifgen.c,v $
49  * Revision 6.16  2008/04/29 13:40:53  kans
50  * fixes for warnings caught by mingw cross-compiler
51  *
52  * Revision 6.15  2001/03/21 18:54:57  juran
53  * Fix "for (...);" warnings by adding a space before the semicolon.
54  *
55  * Revision 6.14  2001/01/05 20:10:29  vakatov
56  * s_ComposeEffClip() -- fixed a typo (".lt" -> ".rb")
57  *
58  * Revision 6.13  2000/04/06 17:12:54  chetvern
59  * gdImageFilledPolygon
60  * zero section width case fixed
61  *
62  * Revision 6.12  1999/10/20 19:48:39  vakatov
63  * + gdImageGetDimensions()
64  *
65  * Revision 6.11  1999/08/13 21:23:08  vakatov
66  * Renamed "gd[Set|Get]ImageColor()" to "gdImage[Set|Get]Color()"
67  *
68  * Revision 6.10  1999/08/13 20:57:40  vakatov
69  * + gdSetImageColor()
70  * + gdImageGetAutoCropRectangle(), gdImageCrop(), gdImageAutoCrop()  <in
71  * a close collab. with S.Resenchuk & R.Tatusov>
72  * + static s_*Rect() to handle "gdRect"
73  *
74  * Revision 6.9  1999/05/20 21:32:45  vakatov
75  * s_DrawEllipse():  "ad hoc" patches for the case of zero radius.
76  * [_DEBUG] s_DrawConic():  just do nothing(and dont crash) if obtained
77  * a wrong octant
78  *
79  * Revision 6.8  1998/06/26 19:57:15  vakatov
80  * gdImageRoundRectangle():  check and adjust the passed args
81  *
82  * Revision 6.7  1998/06/15 22:02:53  vakatov
83  * Added gdImageSetClip() to allow clipping(rectangular area only)
84  *
85  * Revision 6.6  1998/05/08 21:25:29  vakatov
86  * Fixed a typo in the IMAGE_BOUNDS_SAFE macro(Roman Tatusov)
87  *
88  * Revision 6.5  1998/04/27 15:52:53  vakatov
89  * Added gdImageRoundRectangle() and gdImageQuadrant() to draw a rounded
90  * rectangle and a quarter of an ellipse respectively
91  *
92  * Revision 6.4  1998/04/08 19:53:48  brandon
93  * Added gdImageCopy() and gdImageCopyResized() from gd1.2
94  *
95  * Revision 6.3  1998/03/30 16:55:38  vakatov
96  * Added s_DrawConic() -- the generic conic section drawing algorithm;
97  * implemented gdImageArcEx() and gdImageEllipse()
98  * NOTE:  "fill" argument of gdImageArcEx() intended to draw filled
99  *        sector of an ellipse is not implemented yet
100  *
101  * Revision 6.2  1997/11/26 21:26:08  vakatov
102  * Fixed errors and warnings issued by C and C++ (GNU and Sun) compilers
103  *
104  * Revision 6.1  1997/09/10 00:00:53  vakatov
105  * Ignore current drawing pattern when drawing line-based primitives
106  * (line, polygon and arc) -- use current line style only
107  *
108  * Revision 5.5  1997/08/19 19:26:43  vakatov
109  * Added gdImageSelectPattern() to provide Nlm_SelectPattern()
110  * functionality for GIFs
111  *
112  * Revision 5.4  1997/05/28 21:10:09  vakatov
113  * gdGetImageColor() now accepts NULL as r,g,b w/out a crash
114  *
115  * Revision 5.3  1996/12/03 21:48:33  vakatov
116  * Adopted for 32-bit MS-Windows DLLs
117  *
118  * Revision 5.2  1996/11/22  19:44:54  vakatov
119  * Added auxiliary function gdGetImageColor()
120  *
121  * Revision 5.1  1996/11/12  15:38:17  vakatov
122  * Added two routines for the vertical text printing:  gdImageCharV() and
123  * gdImageStringV() -- [by R.Tatusov]
124  *
125  * Revision 1.4  1996/05/21  14:35:04  vakatov
126  * "qsort()" function call has been replaced with the call of toolkit function
127  * "HeapSort()" for the portability(VMS compiler) reason
128  *
129  * Revision 1.3  1996/04/23  21:33:07  kans
130  * includes ncbi.h, uses Nlm_Malloc instead of malloc, etc.
131  */
132 
133 
134 /**************************************************************************/
135 /* INCLUDE */
136 /**************************************************************************/
137 #include <ncbi.h>
138 #include <gifgen.h>
139 
140 
141 /**************************************************************************/
142 /* DEFINES */
143 /**************************************************************************/
144 #define costScale 1024
145 #define sintScale 1024
146 
147 #define IMAGE_BOUNDS_SAFE(im, X, Y) \
148 ((X) >= im->eff_clip.lt.x  &&  (Y) >= im->eff_clip.lt.y  && \
149  (X) <  im->eff_clip.rb.x  &&  (Y) <  im->eff_clip.rb.y)
150 
151 
152 #define directSet(im, x, y, color) \
153 { \
154   if ( IMAGE_BOUNDS_SAFE(im, x, y) ) \
155     im->pixels[x+y*im->sx] = (Uint1)color; \
156 }
157 
158 #define dashedSet \
159 { \
160   dashStep++; \
161   if (dashStep == gdDashSize) { \
162     dashStep = 0; \
163     on = !on; \
164   } \
165   if (on) { \
166     directSet(im, x, y, color); \
167   } \
168 }
169 
170 
171 /**************************************************************************/
172 /* TYPEDEFS */
173 /**************************************************************************/
174 
175 /**************************************************************************/
176 /* STATIC VARIABLE */
177 /**************************************************************************/
178 static const int cost[] = {
179   1024, 1023, 1023, 1022, 1021, 1020, 1018,
180   1016, 1014, 1011, 1008, 1005, 1001, 997,
181   993, 989, 984, 979, 973, 968, 962,
182   955, 949, 942, 935, 928, 920, 912,
183   904, 895, 886, 877, 868, 858, 848,
184   838, 828, 817, 806, 795, 784, 772,
185   760, 748, 736, 724, 711, 698, 685,
186   671, 658, 644, 630, 616, 601, 587,
187   572, 557, 542, 527, 512, 496, 480,
188   464, 448, 432, 416, 400, 383, 366,
189   350, 333, 316, 299, 282, 265, 247,
190   230, 212, 195, 177, 160, 142, 124,
191   107, 89, 71, 53, 35, 17, 0,
192   -17, -35, -53, -71, -89, -107, -124,
193   -142, -160, -177, -195, -212, -230, -247,
194   -265, -282, -299, -316, -333, -350, -366,
195   -383, -400, -416, -432, -448, -464, -480,
196   -496, -512, -527, -542, -557, -572, -587,
197   -601, -616, -630, -644, -658, -671, -685,
198   -698, -711, -724, -736, -748, -760, -772,
199   -784, -795, -806, -817, -828, -838, -848,
200   -858, -868, -877, -886, -895, -904, -912,
201   -920, -928, -935, -942, -949, -955, -962,
202   -968, -973, -979, -984, -989, -993, -997,
203   -1001, -1005, -1008, -1011, -1014, -1016, -1018,
204   -1020, -1021, -1022, -1023, -1023, -1024, -1023,
205   -1023, -1022, -1021, -1020, -1018, -1016, -1014,
206   -1011, -1008, -1005, -1001, -997, -993, -989,
207   -984, -979, -973, -968, -962, -955, -949,
208   -942, -935, -928, -920, -912, -904, -895,
209   -886, -877, -868, -858, -848, -838, -828,
210   -817, -806, -795, -784, -772, -760, -748,
211   -736, -724, -711, -698, -685, -671, -658,
212   -644, -630, -616, -601, -587, -572, -557,
213   -542, -527, -512, -496, -480, -464, -448,
214   -432, -416, -400, -383, -366, -350, -333,
215   -316, -299, -282, -265, -247, -230, -212,
216   -195, -177, -160, -142, -124, -107, -89,
217   -71, -53, -35, -17, 0, 17, 35,
218   53, 71, 89, 107, 124, 142, 160,
219   177, 195, 212, 230, 247, 265, 282,
220   299, 316, 333, 350, 366, 383, 400,
221   416, 432, 448, 464, 480, 496, 512,
222   527, 542, 557, 572, 587, 601, 616,
223   630, 644, 658, 671, 685, 698, 711,
224   724, 736, 748, 760, 772, 784, 795,
225   806, 817, 828, 838, 848, 858, 868,
226   877, 886, 895, 904, 912, 920, 928,
227   935, 942, 949, 955, 962, 968, 973,
228   979, 984, 989, 993, 997, 1001, 1005,
229   1008, 1011, 1014, 1016, 1018, 1020, 1021,
230   1022, 1023, 1023
231 };
232 
233 static const int sint[] = {
234   0, 17, 35, 53, 71, 89, 107,
235   124, 142, 160, 177, 195, 212, 230,
236   247, 265, 282, 299, 316, 333, 350,
237   366, 383, 400, 416, 432, 448, 464,
238   480, 496, 512, 527, 542, 557, 572,
239   587, 601, 616, 630, 644, 658, 671,
240   685, 698, 711, 724, 736, 748, 760,
241   772, 784, 795, 806, 817, 828, 838,
242   848, 858, 868, 877, 886, 895, 904,
243   912, 920, 928, 935, 942, 949, 955,
244   962, 968, 973, 979, 984, 989, 993,
245   997, 1001, 1005, 1008, 1011, 1014, 1016,
246   1018, 1020, 1021, 1022, 1023, 1023, 1024,
247   1023, 1023, 1022, 1021, 1020, 1018, 1016,
248   1014, 1011, 1008, 1005, 1001, 997, 993,
249   989, 984, 979, 973, 968, 962, 955,
250   949, 942, 935, 928, 920, 912, 904,
251   895, 886, 877, 868, 858, 848, 838,
252   828, 817, 806, 795, 784, 772, 760,
253   748, 736, 724, 711, 698, 685, 671,
254   658, 644, 630, 616, 601, 587, 572,
255   557, 542, 527, 512, 496, 480, 464,
256   448, 432, 416, 400, 383, 366, 350,
257   333, 316, 299, 282, 265, 247, 230,
258   212, 195, 177, 160, 142, 124, 107,
259   89, 71, 53, 35, 17, 0, -17,
260   -35, -53, -71, -89, -107, -124, -142,
261   -160, -177, -195, -212, -230, -247, -265,
262   -282, -299, -316, -333, -350, -366, -383,
263   -400, -416, -432, -448, -464, -480, -496,
264   -512, -527, -542, -557, -572, -587, -601,
265   -616, -630, -644, -658, -671, -685, -698,
266   -711, -724, -736, -748, -760, -772, -784,
267   -795, -806, -817, -828, -838, -848, -858,
268   -868, -877, -886, -895, -904, -912, -920,
269   -928, -935, -942, -949, -955, -962, -968,
270   -973, -979, -984, -989, -993, -997, -1001,
271   -1005, -1008, -1011, -1014, -1016, -1018, -1020,
272   -1021, -1022, -1023, -1023, -1024, -1023, -1023,
273   -1022, -1021, -1020, -1018, -1016, -1014, -1011,
274   -1008, -1005, -1001, -997, -993, -989, -984,
275   -979, -973, -968, -962, -955, -949, -942,
276   -935, -928, -920, -912, -904, -895, -886,
277   -877, -868, -858, -848, -838, -828, -817,
278   -806, -795, -784, -772, -760, -748, -736,
279   -724, -711, -698, -685, -671, -658, -644,
280   -630, -616, -601, -587, -572, -557, -542,
281   -527, -512, -496, -480, -464, -448, -432,
282   -416, -400, -383, -366, -350, -333, -316,
283   -299, -282, -265, -247, -230, -212, -195,
284   -177, -160, -142, -124, -107, -89, -71,
285   -53,  -35,  -17
286 };
287 
288 /**************************************************************************/
289 /* STATIC FUNCTION */
290 /**************************************************************************/
291 
292 
s_NormalizeRect(gdRect * rect)293 static void s_NormalizeRect(gdRect* rect)
294 {
295   if (rect->lt.x > rect->rb.x) {
296     int x = rect->lt.x;
297     rect->lt.x = rect->rb.x;
298     rect->rb.x = x;
299   }
300 
301   if (rect->lt.y > rect->rb.y) {
302     int y = rect->lt.y;
303     rect->lt.y = rect->rb.y;
304     rect->rb.y = y;
305   }
306 }
307 
308 
s_ExpandRect(gdRect * rect,int dX,int dY)309 static void s_ExpandRect(gdRect* rect, int dX, int dY)
310 {
311   s_NormalizeRect(rect);
312   rect->lt.x -= dX;
313   rect->rb.x += dX;
314   rect->lt.y -= dY;
315   rect->rb.y += dY;
316 
317   if (rect->lt.x > rect->rb.x)
318     rect->lt.x = rect->rb.x = (rect->lt.x + rect->rb.x) / 2;
319   if (rect->lt.y > rect->rb.y)
320     rect->lt.y = rect->rb.y = (rect->lt.y + rect->rb.y) / 2;
321 }
322 
323 
s_CropRect(gdRect * rect,const gdRect * crop)324 static void s_CropRect(gdRect* rect, const gdRect* crop)
325 {
326   s_NormalizeRect(rect);
327 
328   if (rect->lt.x < crop->lt.x)
329     rect->lt.x = crop->lt.x;
330   if (rect->rb.x > crop->rb.x)
331     rect->rb.x = crop->rb.x;
332 
333   if (rect->lt.y < crop->lt.y)
334     rect->lt.y = crop->lt.y;
335   if (rect->rb.y > crop->rb.y)
336     rect->rb.y = crop->rb.y;
337 
338 }
339 
340 
s_GetRectImage(gdRect * rect,const gdImage * im)341 static void s_GetRectImage(gdRect* rect, const gdImage* im)
342 {
343   rect->lt.x = 0;
344   rect->lt.y = 0;
345   rect->rb.x = (im ? im->sx : INT2_MAX) - 1;
346   rect->rb.y = (im ? im->sy : INT2_MAX) - 1;
347 }
348 
349 
s_CropRectImage(gdRect * rect,const gdImage * im)350 static void s_CropRectImage(gdRect* rect, const gdImage* im)
351 {
352   gdRect crop;
353   s_GetRectImage(&crop, im);
354   s_CropRect(rect, &crop);
355 }
356 
357 
358 
359 static void
gdImageBrushApply(gdImagePtr im,int x,int y)360 /*FCN*/gdImageBrushApply(gdImagePtr im, int x, int y)
361 {
362    int lx, ly;
363    int hy;
364    int hx;
365    int x1, y1, x2, y2;
366    int srcx, srcy;
367 
368    if (!im->brush) {
369       return;
370    }
371    hy = gdImageSY(im->brush)/2;
372    y1 = y - hy;
373    y2 = y1 + gdImageSY(im->brush);
374    hx = gdImageSX(im->brush)/2;
375    x1 = x - hx;
376    x2 = x1 + gdImageSX(im->brush);
377    srcy = 0;
378    for (ly = y1; (ly < y2); ly++) {
379       srcx = 0;
380       for (lx = x1; (lx < x2); lx++) {
381          int p;
382          p = gdImageGetPixel(im->brush, srcx, srcy);
383          /* Allow for non-square brushes! */
384          if (p != gdImageGetTransparent(im->brush)) {
385             gdImageSetPixel(im, lx, ly,
386                im->brushColorMap[p]);
387          }
388          srcx++;
389       }
390       srcy++;
391    }
392 }
393 
394 static void
gdImageTileApply(gdImagePtr im,int x,int y)395 /*FCN*/gdImageTileApply(gdImagePtr im, int x, int y)
396 {
397    int srcx, srcy;
398    int p;
399 
400    if (!im->tile) {
401       return;
402    }
403    srcx = x % gdImageSX(im->tile);
404    srcy = y % gdImageSY(im->tile);
405    p = gdImageGetPixel(im->tile, srcx, srcy);
406    /* Allow for transparency */
407    if (p != gdImageGetTransparent(im->tile)) {
408       gdImageSetPixel(im, x, y,
409          im->tileColorMap[p]);
410    }
411 }
412 
413 #ifdef __cplusplus
414 extern "C" {
415   static int LIBCALLBACK gdCompareInt(Nlm_VoidPtr a, Nlm_VoidPtr b);
416 }
417 #endif
418 
419 static
gdCompareInt(Nlm_VoidPtr a,Nlm_VoidPtr b)420 /*FCN*/int LIBCALLBACK gdCompareInt(Nlm_VoidPtr a, Nlm_VoidPtr b)
421 {
422    return (*(const int *)a) - (*(const int *)b);
423 }
424 
425 /* s_DrawConic():
426  *
427  * CONIC  2D Bresenham-like conic drawer.
428  *       CONIC(Sx,Sy, Ex,Ey, A,B,C,D,E,F) draws the conic specified
429  *       by A x^2 + B x y + C y^2 + D x + E y + F = 0, between the
430  *       start point (Sx, Sy) and endpoint (Ex,Ey).
431  *
432  * Author: Andrew W. Fitzgibbon (andrewfg@ed.ac.uk),
433  *         Machine Vision Unit,
434  *         Dept. of Artificial Intelligence,
435  *         Edinburgh University,
436  *
437  * Date: 31-Mar-94
438  * Version 2: 6-Oct-95
439  *      Bugfixes from Arne Steinarson <arst@ludd.luth.se>
440  *      (ftp://ftp.dai.ed.ac.uk/pub/vision/src/conic-patch1.[ch])
441  * Adopted and "beautified" for the NCBI toolkit by D.Vakatov, Feb-98;
442  * and, s_GetOctant() rewritten to fix at the octant boundary points
443  */
444 
s_GetOctant(int gx,int gy)445 static int s_GetOctant(int gx, int gy)
446 {
447   static const int OCTANT[3 /*gX?0*/][3 /*gY?0*/][3 /*|gX|?|gY|*/] = {
448     /***********  gY < 0 *** gY = 0 *** gY > 0 */
449     /* gX < 0 */ {{8, 8, 7},   {0, 0, 7},   {5, 6, 6}},
450     /* gX = 0 */ {{1, 0, 0},   {0, 0, 0},   {5, 0, 0}},
451     /* gX > 0 */ {{1, 2, 2},   {0, 0, 3},   {4, 4, 3}}
452   };
453 
454 #define A_VS_B(a,b) (a < b) ? 0 : (a == b) ? 1 : 2
455   int Xvs0 = A_VS_B(gx, 0);
456   int Yvs0 = A_VS_B(gy, 0);
457   if (gx < 0)
458     gx = -gx;
459   if (gy < 0)
460     gy = -gy;
461 
462   /* ASSERT ( 1 <= OCTANT[Xvs0][Yvs0][A_VS_B(gx, gy)] ); */
463   /* ASSERT ( 8 >= OCTANT[Xvs0][Yvs0][A_VS_B(gx, gy)] ); */
464   return OCTANT[Xvs0][Yvs0][A_VS_B(gx, gy)];
465 }
466 
467 
468 typedef void (*Nlm_DrawPoint)(int x, int y, void *data);
469 
s_DrawConic(int A,int B,int C,int D,int E,int F,int xs,int ys,int xe,int ye,Nlm_DrawPoint draw_func,void * draw_data)470 static void s_DrawConic
471 (/* Axx + Bxy + Cyy + Dx + Ey + F = 0 */
472  int A, int B, int C, int D, int E, int F,
473  int xs, int ys, /* starting point */
474  int xe, int ye, /* ending point   */
475  /* call "draw_func" to draw a point */
476  Nlm_DrawPoint draw_func, void *draw_data)
477 {
478   static const int DIAGx[] = {999, 1,  1, -1, -1, -1, -1,  1,  1};
479   static const int DIAGy[] = {999, 1,  1,  1,  1, -1, -1, -1, -1};
480   static const int SIDEx[] = {999, 1,  0,  0, -1, -1,  0,  0,  1};
481   static const int SIDEy[] = {999, 0,  1,  1,  0,  0, -1, -1,  0};
482 
483   int octant;
484   int dxS, dyS, dxD, dyD;
485   int d,u,v;
486   int k1sign, k1, Bsign, k2, k3;
487   int gxe, gye, gx, gy;
488   int octantcount;
489   int x, y;
490 
491   if (xs == xe  &&  ys == ye)
492     return;
493 
494   A *= 4;  B *= 4;  C *= 4;  D *= 4;  E *= 4;  F *= 4;
495 
496   /* Translate start point to origin... */
497   F = A*xs*xs + B*xs*ys + C*ys*ys + D*xs + E*ys + F;
498   D = D + 2*A*xs + B*ys;
499   E = E + B*xs + 2*C*ys;
500 
501   /* Work out starting octant */
502   octant = s_GetOctant(D, E);
503 
504   dxS = SIDEx[octant];
505   dyS = SIDEy[octant];
506   dxD = DIAGx[octant];
507   dyD = DIAGy[octant];
508 
509   switch ( octant ) {
510   case 1:
511     d = A + B/2 + C/4 + D + E/2 + F;
512     u = A + B/2 + D;
513     v = u + E;
514     break;
515   case 2:
516     d = A/4 + B/2 + C + D/2 + E + F;
517     u = B/2 + C + E;
518     v = u + D;
519     break;
520   case 3:
521     d = A/4 - B/2 + C - D/2 + E + F;
522     u = -B/2 + C + E;
523     v = u - D;
524     break;
525   case 4:
526     d = A - B/2 + C/4 - D + E/2 + F;
527     u = A - B/2 - D;
528     v = u + E;
529     break;
530   case 5:
531     d = A + B/2 + C/4 - D - E/2 + F;
532     u = A + B/2 - D;
533     v = u - E;
534     break;
535   case 6:
536     d = A/4 + B/2 + C - D/2 - E + F;
537     u = B/2 + C - E;
538     v = u - D;
539     break;
540   case 7:
541     d = A/4 - B/2 + C + D/2 - E + F;
542     u =  -B/2 + C - E;
543     v = u + D;
544     break;
545   case 8:
546     d = A - B/2 + C/4 + D - E/2 + F;
547     u = A - B/2 + D;
548     v = u - E;
549     break;
550   default:
551     /* ASSERT ( FALSE );  cannot be drawn by this algorithm */
552     return;
553   }
554 
555   k1sign = dyS * dyD;
556   k1 = 2 * (A + k1sign * (C - A));
557   Bsign = dxD * dyD;
558   k2 = k1 + Bsign * B;
559   k3 = 2 * (A + C + Bsign * B);
560 
561   /* Work out gradient at endpoint */
562   gxe = xe - xs;
563   gye = ye - ys;
564   gx = 2*A*gxe +   B*gye + D;
565   gy =   B*gxe + 2*C*gye + E;
566 
567   octantcount = s_GetOctant(gx, gy) - octant;
568   if (octantcount < 0  ||
569       ((octantcount == 0)  &&
570        ((xs > xe  &&  dxD > 0)  ||  (ys > ye  &&  dyD > 0)  ||
571         (xs < xe  &&  dxD < 0)  ||  (ys < ye  &&  dyD < 0))))
572     octantcount += 8;
573 
574   x = xs;
575   y = ys;
576 
577   while (octantcount > 0) {
578     if (octant & 1) { /* Octant is odd */
579       while (2*v <= k2) {
580         draw_func(x, y, draw_data);
581 
582         if (d < 0) { /* inside */
583           x += dxS;
584           y += dyS;
585           u += k1;
586           v += k2;
587           d += u;
588         }
589         else { /* outside */
590           x += dxD;
591           y += dyD;
592           u += k2;
593           v += k3;
594           d += v;
595         }
596       }
597 
598       d = d - u + v/2 - k2/2 + 3*k3/8;
599       u = -u + v - k2/2 + k3/2;
600       v = v - k2 + k3/2;
601       k1 = k1 - 2*k2 + k3;
602       k2 = k3 - k2;
603       {{ int tmp = dxS;  dxS = -dyS;  dyS = tmp; }}
604     }
605     else { /* Octant is even */
606       while (2*u < k2) {
607         draw_func(x, y, draw_data);
608 
609         if (d > 0) { /* outside */
610           x += dxS;
611           y += dyS;
612           u += k1;
613           v += k2;
614           d += u;
615         }
616         else { /* inside */
617           x += dxD;
618           y += dyD;
619           u += k2;
620           v += k3;
621           d += v;
622         }
623       }
624 
625       {{
626         int tmpdk = k1 - k2;
627         d = d + u - v + tmpdk;
628         v = 2*u - v + tmpdk;
629         u = u + tmpdk;
630         k3 = k3 + 4*tmpdk;
631         k2 = k1 + tmpdk;
632         {{ int tmp = dxD;  dxD = -dyD;  dyD = tmp; }}
633       }}
634     }
635 
636     octant = (octant & 7) + 1;
637     octantcount--;
638   }
639 
640   /* Draw final octant until we reach the endpoint */
641   if (octant & 1) {  /* Octant is odd */
642     while (2*v <= k2) {
643       draw_func(x, y, draw_data);
644       if (x == xe  &&  y == ye)
645         break;
646 
647       if (d < 0) { /* inside */
648         x += dxS;
649         y += dyS;
650         u += k1;
651         v += k2;
652         d += u;
653       }
654       else { /* outside */
655         x += dxD;
656         y += dyD;
657         u += k2;
658         v += k3;
659         d += v;
660       }
661     }
662   }
663   else { /* Octant is even */
664     while ((2*u < k2)) {
665       draw_func(x, y, draw_data);
666       if (x == xe  &&  y == ye)
667         break;
668 
669       if (d > 0) { /* outside */
670         x += dxS;
671         y += dyS;
672         u += k1;
673         v += k2;
674         d += u;
675       }
676       else { /* inside */
677         x += dxD;
678         y += dyD;
679         u += k2;
680         v += k3;
681         d += v;
682       }
683     }
684   }
685 }
686 
687 typedef struct {
688   gdImage *im;
689   int color;
690 } SDrawPointArc;
691 
s_DrawPointArc(int x,int y,void * data)692 static void s_DrawPointArc(int x, int y, void *data)
693 {
694   SDrawPointArc *dpa = (SDrawPointArc *)data;
695   directSet(dpa->im, x, y, dpa->color);
696 }
697 
698 
699 typedef struct {
700   int x;
701   int y;
702 } SPoint;
703 
704 typedef struct {
705   int xdim;
706   int ydim;
707   int n;
708   SPoint *points;
709 } SStorePoint;
710 
s_StorePoint(int x,int y,void * data)711 static void s_StorePoint(int x, int y, void *data)
712 {
713   SStorePoint *sp = (SStorePoint *)data;
714   if (x < 0  ||  y < 0  ||  sp->xdim <= x  ||  sp->ydim <= y)
715     return;
716 
717   sp->points[sp->n].x = x;
718   sp->points[sp->n].y = y;
719   sp->n++;
720 }
721 
722 
723 typedef struct {
724   gdImage *im;
725   int color;
726   int cx;
727   int cy;
728   int prev_y;    /* for fill only */
729   int quadrant; /* 0 -- all quadrants;  1 -- right top;  2,3,4 -- clockwise */
730 } SDrawPointEllipse;
731 
732 
s_DrawPointEllipse(int x,int y,void * data)733 static void s_DrawPointEllipse(int x, int y, void *data)
734 {
735   SDrawPointEllipse *dpe = (SDrawPointEllipse *)data;
736   int xl = dpe->cx - x;
737   int xr = dpe->cx + x;
738   int yt = dpe->cy - y;
739   int yb = dpe->cy + y;
740 
741   switch ( dpe->quadrant ) {
742   case 0:
743     if ( x ) {
744       directSet(dpe->im, xl, yb, dpe->color);
745       directSet(dpe->im, xr, yt, dpe->color);
746     }
747     if ( y ) {
748       directSet(dpe->im, xl, yt, dpe->color);
749       directSet(dpe->im, xr, yb, dpe->color);
750     }
751     break;
752   case 1:
753     directSet(dpe->im, xr, yt, dpe->color);
754     break;
755   case 2:
756     directSet(dpe->im, xl, yt, dpe->color);
757     break;
758   case 3:
759     directSet(dpe->im, xl, yb, dpe->color);
760     break;
761   case 4:
762     directSet(dpe->im, xr, yb, dpe->color);
763     break;
764   default:
765     ASSERT(0);
766   }
767 }
768 
769 
s_ImageHLine(gdImagePtr im,int y,int x1,int x2,int color)770 static void s_ImageHLine(gdImagePtr im, int y, int x1, int x2, int color)
771 {
772   int x;
773   if (y < 0  ||  im->sy <= y)
774     return;
775   if (x1 > x2) {
776     x = x1;  x1 = x2;  x2 = x;
777   }
778   if (x2 < 0  ||  im->sx <= x1)
779     return;
780 
781   x1 = MAX(x1, 0);
782   x2++;
783   x2 = MIN(x2, im->sx);
784 
785   for (x = x1;  x < x2;  x++)
786     gdImageSetPixel(im, x, y, color);
787 }
788 
789 
s_DrawPointFilledEllipse(int x,int y,void * data)790 static void s_DrawPointFilledEllipse(int x, int y, void *data)
791 {
792   SDrawPointEllipse *dpe = (SDrawPointEllipse *)data;
793   if (y == dpe->prev_y)
794     return;
795 
796   switch ( dpe->quadrant ) {
797   case 0:
798     s_ImageHLine(dpe->im, dpe->cy + y, dpe->cx - x, dpe->cx + x, dpe->color);
799     if ( y )
800       s_ImageHLine(dpe->im, dpe->cy - y, dpe->cx - x, dpe->cx + x, dpe->color);
801     break;
802   case 1:
803     s_ImageHLine(dpe->im, dpe->cy - y, dpe->cx, dpe->cx + x, dpe->color);
804     break;
805   case 2:
806     s_ImageHLine(dpe->im, dpe->cy - y, dpe->cx - x, dpe->cx, dpe->color);
807     break;
808   case 3:
809     s_ImageHLine(dpe->im, dpe->cy + y, dpe->cx - x, dpe->cx, dpe->color);
810     break;
811   case 4:
812     s_ImageHLine(dpe->im, dpe->cy + y, dpe->cx, dpe->cx + x, dpe->color);
813     break;
814   default:
815     ASSERT(0);
816   }
817 
818   dpe->prev_y = y;
819 }
820 
821 
s_ComposeEffClip(gdImagePtr im)822 static void s_ComposeEffClip(gdImagePtr im)
823 {
824   if ( !im->use_clip ) {
825     im->eff_clip.lt.x = im->eff_clip.lt.y = 0;
826     im->eff_clip.rb.x = im->sx;
827     im->eff_clip.rb.y = im->sy;
828     return;
829   }
830 
831   im->eff_clip.lt.x = MAX(im->clip.lt.x, 0);
832   im->eff_clip.lt.y = MAX(im->clip.lt.y, 0);
833   im->eff_clip.rb.x = MIN(im->clip.rb.x + 1, im->sx);
834   im->eff_clip.rb.y = MIN(im->clip.rb.y + 1, im->sy);
835 }
836 
837 
838 /**************************************************************************/
839 /* GLOBAL FUNCTIONS */
840 /**************************************************************************/
841 
842 NLM_EXTERN gdImagePtr
gdImageCreate(int sx,int sy)843 /*FCN*/gdImageCreate(int sx, int sy)
844 {
845    gdImagePtr im;
846 
847    im = (gdImage *) Nlm_Malloc(sizeof(gdImage));
848    im->pixels = (unsigned char *) Nlm_Calloc( sx * sy, 1 );
849    im->polyInts = 0;
850    im->polyAllocated = 0;
851    im->brush = 0;
852    im->tile = 0;
853    im->style = 0;
854    im->sx = sx;
855    im->sy = sy;
856    im->colorsTotal = 0;
857    im->transparent = (-1);
858    im->interlace = 0;
859    im->use_pattern = 0;
860    im->use_clip = 0;
861    s_ComposeEffClip(im);
862    return im;
863 }
864 
865 NLM_EXTERN void
gdImageDestroy(gdImagePtr im)866 /*FCN*/gdImageDestroy(gdImagePtr im)
867 {
868    Nlm_Free(im->pixels);
869    if (im->polyInts) {
870          Nlm_Free(im->polyInts);
871    }
872    if (im->style) {
873       Nlm_Free(im->style);
874    }
875    Nlm_Free(im);
876 }
877 
878 NLM_EXTERN int
gdImageColorClosest(gdImagePtr im,int r,int g,int b)879 /*FCN*/gdImageColorClosest(gdImagePtr im, int r, int g, int b)
880 {
881    int i;
882    long rd, gd, bd;
883    int ct = (-1);
884    long mindist = 0;
885 
886    for (i=0; (i<(im->colorsTotal)); i++) {
887       long dist;
888       if (im->open[i]) {
889          continue;
890       }
891       rd = (im->red[i] - r);
892       gd = (im->green[i] - g);
893       bd = (im->blue[i] - b);
894       dist = rd * rd + gd * gd + bd * bd;
895       if ((i == 0) || (dist < mindist)) {
896          mindist = dist;
897          ct = i;
898       }
899    }
900    return ct;
901 }
902 
903 NLM_EXTERN int
gdImageColorExact(gdImagePtr im,int r,int g,int b)904 /*FCN*/gdImageColorExact(gdImagePtr im, int r, int g, int b)
905 {
906    int i;
907 
908    for (i=0; (i<(im->colorsTotal)); i++) {
909       if (im->open[i]) {
910          continue;
911       }
912       if ((im->red[i] == r) &&
913          (im->green[i] == g) &&
914          (im->blue[i] == b)) {
915          return i;
916       }
917    }
918    return -1;
919 }
920 
921 NLM_EXTERN int
gdImageColorAllocate(gdImagePtr im,int r,int g,int b)922 /*FCN*/gdImageColorAllocate(gdImagePtr im, int r, int g, int b)
923 {
924    int i;
925    int ct = (-1);
926 
927    for (i=0; (i<(im->colorsTotal)); i++) {
928       if (im->open[i]) {
929          ct = i;
930          break;
931       }
932    }
933    if (ct == (-1)) {
934       ct = im->colorsTotal;
935       if (ct == gdMaxColors) {
936          return -1;
937       }
938       im->colorsTotal++;
939    }
940    im->red[ct] = r;
941    im->green[ct] = g;
942    im->blue[ct] = b;
943    im->open[ct] = 0;
944    return ct;
945 }
946 
947 NLM_EXTERN void
gdImageColorDeallocate(gdImagePtr im,int color)948 /*FCN*/gdImageColorDeallocate(gdImagePtr im, int color)
949 {
950    im->open[color] = 1;
951 }
952 
953 NLM_EXTERN int
gdImageGetColor(gdImagePtr im,int color,int * r,int * g,int * b)954 /*FCN*/gdImageGetColor(gdImagePtr im, int color, int *r, int *g, int *b)
955 {
956   ASSERT ( color >= 0 );
957   if (color < 0  ||  color >= im->colorsTotal  ||  im->open[color])
958     return FALSE;
959 
960   if ( r )
961     *r = im->red  [color];
962   if ( g )
963     *g = im->green[color];
964   if ( b )
965     *b = im->blue [color];
966   return TRUE;
967 }
968 
969 
970 NLM_EXTERN int
gdImageSetColor(gdImagePtr im,int color,int r,int g,int b)971 /*FCN*/gdImageSetColor(gdImagePtr im, int color, int r, int g, int b)
972 {
973   ASSERT ( color >= 0 );
974   if (color < 0  ||  color >= im->colorsTotal  ||  im->open[color])
975     return FALSE;
976 
977   im->red  [color] = r;
978   im->green[color] = g;
979   im->blue [color] = b;
980   return TRUE;
981 }
982 
983 
984 NLM_EXTERN void
gdImageColorTransparent(gdImagePtr im,int color)985 /*FCN*/gdImageColorTransparent(gdImagePtr im, int color)
986 {
987    im->transparent = color;
988 }
989 
990 NLM_EXTERN void
gdImageSetPixel(gdImagePtr im,int x,int y,int color)991 /*FCN*/gdImageSetPixel(gdImagePtr im, int x, int y, int color)
992 {
993    int p;
994 
995    switch(color) {
996      case gdStyled:
997       if (!im->style) {
998          /* Refuse to draw if no style is set. */
999          return;
1000       } else {
1001          p = im->style[im->stylePos++];
1002       }
1003       if (p != (gdTransparent)) {
1004          gdImageSetPixel(im, x, y, p);
1005       }
1006       im->stylePos = im->stylePos %  im->styleLength;
1007       break;
1008     case gdStyledBrushed:
1009       if (!im->style) {
1010          /* Refuse to draw if no style is set. */
1011          return;
1012       }
1013       p = im->style[im->stylePos++];
1014       if ((p != gdTransparent) && (p != 0)) {
1015          gdImageSetPixel(im, x, y, gdBrushed);
1016       }
1017       im->stylePos = im->stylePos %  im->styleLength;
1018       break;
1019     case gdBrushed:
1020       gdImageBrushApply(im, x, y);
1021       break;
1022     case gdTiled:
1023       gdImageTileApply(im, x, y);
1024       break;
1025     default:
1026       if (IMAGE_BOUNDS_SAFE(im, x, y)  &&
1027           (!im->use_pattern  ||  (char)(im->pattern[7-y%8] >> x%8 << 7)))
1028         im->pixels[x+y*im->sx] = (Uint1)color;
1029       break;
1030    }
1031 }
1032 
1033 NLM_EXTERN int
gdImageGetPixel(gdImagePtr im,int x,int y)1034 /*FCN*/gdImageGetPixel(gdImagePtr im, int x, int y)
1035 {
1036    if (IMAGE_BOUNDS_SAFE(im, x, y)) {
1037       return im->pixels[x+y*im->sx];
1038    } else {
1039       return 0;
1040    }
1041 }
1042 
1043 NLM_EXTERN void
gdImageLine(gdImagePtr im,int x1,int y1,int x2,int y2,int color)1044 /*FCN*/gdImageLine(gdImagePtr im, int x1, int y1, int x2, int y2, int color)
1045 {
1046    int dx, dy, incr1, incr2, d, x, y, xend, yend, xdirflag, ydirflag;
1047 
1048    dx = abs(x2-x1);
1049    dy = abs(y2-y1);
1050    if (dy <= dx) {
1051       d = 2*dy - dx;
1052       incr1 = 2*dy;
1053       incr2 = 2 * (dy - dx);
1054       if (x1 > x2) {
1055          x = x2;
1056          y = y2;
1057          ydirflag = (-1);
1058          xend = x1;
1059       } else {
1060          x = x1;
1061          y = y1;
1062          ydirflag = 1;
1063          xend = x2;
1064       }
1065       directSet(im, x, y, color);
1066       if (((y2 - y1) * ydirflag) > 0) {
1067          while (x < xend) {
1068             x++;
1069             if (d < 0) {
1070                d+=incr1;
1071             } else {
1072                y++;
1073                d+=incr2;
1074             }
1075             directSet(im, x, y, color);
1076          }
1077       } else {
1078          while (x < xend) {
1079             x++;
1080             if (d < 0) {
1081                d+=incr1;
1082             } else {
1083                y--;
1084                d+=incr2;
1085             }
1086             directSet(im, x, y, color);
1087          }
1088       }
1089    } else {
1090       d = 2*dx - dy;
1091       incr1 = 2*dx;
1092       incr2 = 2 * (dx - dy);
1093       if (y1 > y2) {
1094          y = y2;
1095          x = x2;
1096          yend = y1;
1097          xdirflag = (-1);
1098       } else {
1099          y = y1;
1100          x = x1;
1101          yend = y2;
1102          xdirflag = 1;
1103       }
1104       directSet(im, x, y, color);
1105       if (((x2 - x1) * xdirflag) > 0) {
1106          while (y < yend) {
1107             y++;
1108             if (d < 0) {
1109                d+=incr1;
1110             } else {
1111                x++;
1112                d+=incr2;
1113             }
1114             directSet(im, x, y, color);
1115          }
1116       } else {
1117          while (y < yend) {
1118             y++;
1119             if (d < 0) {
1120                d+=incr1;
1121             } else {
1122                x--;
1123                d+=incr2;
1124             }
1125             directSet(im, x, y, color);
1126          }
1127       }
1128    }
1129 }
1130 
1131 NLM_EXTERN void
gdImageDashedLine(gdImagePtr im,int x1,int y1,int x2,int y2,int color)1132 /*FCN*/gdImageDashedLine(gdImagePtr im, int x1, int y1, int x2, int y2, int color)
1133 {
1134    int dx, dy, incr1, incr2, d, x, y, xend, yend, xdirflag, ydirflag;
1135    int dashStep = 0;
1136    int on = 1;
1137 
1138    dx = abs(x2-x1);
1139    dy = abs(y2-y1);
1140    if (dy <= dx) {
1141       d = 2*dy - dx;
1142       incr1 = 2*dy;
1143       incr2 = 2 * (dy - dx);
1144       if (x1 > x2) {
1145          x = x2;
1146          y = y2;
1147          ydirflag = (-1);
1148          xend = x1;
1149       } else {
1150          x = x1;
1151          y = y1;
1152          ydirflag = 1;
1153          xend = x2;
1154       }
1155       dashedSet;
1156       if (((y2 - y1) * ydirflag) > 0) {
1157          while (x < xend) {
1158             x++;
1159             if (d <0) {
1160                d+=incr1;
1161             } else {
1162                y++;
1163                d+=incr2;
1164             }
1165             dashedSet;
1166          }
1167       } else {
1168          while (x < xend) {
1169             x++;
1170             if (d <0) {
1171                d+=incr1;
1172             } else {
1173                y--;
1174                d+=incr2;
1175             }
1176             dashedSet;
1177          }
1178       }
1179    } else {
1180       d = 2*dx - dy;
1181       incr1 = 2*dx;
1182       incr2 = 2 * (dx - dy);
1183       if (y1 > y2) {
1184          y = y2;
1185          x = x2;
1186          yend = y1;
1187          xdirflag = (-1);
1188       } else {
1189          y = y1;
1190          x = x1;
1191          yend = y2;
1192          xdirflag = 1;
1193       }
1194       dashedSet;
1195       if (((x2 - x1) * xdirflag) > 0) {
1196          while (y < yend) {
1197             y++;
1198             if (d <0) {
1199                d+=incr1;
1200             } else {
1201                x++;
1202                d+=incr2;
1203             }
1204             dashedSet;
1205          }
1206       } else {
1207          while (y < yend) {
1208             y++;
1209             if (d <0) {
1210                d+=incr1;
1211             } else {
1212                x--;
1213                d+=incr2;
1214             }
1215             dashedSet;
1216          }
1217       }
1218    }
1219 }
1220 
1221 NLM_EXTERN int
gdImageBoundsSafe(gdImagePtr im,int x,int y)1222 /*FCN*/gdImageBoundsSafe(gdImagePtr im, int x, int y)
1223 {
1224    return IMAGE_BOUNDS_SAFE(im, x, y);
1225 }
1226 
1227 NLM_EXTERN void
gdImageChar(gdImagePtr im,gdFontPtr f,int x,int y,int c,int color)1228 /*FCN*/gdImageChar(gdImagePtr im, gdFontPtr f, int x, int y, int c, int color)
1229 {
1230    int cx, cy;
1231    int px, py;
1232    int fline;
1233 
1234    cx = 0;
1235    cy = 0;
1236    if ((c < f->offset) || (c >= (f->offset + f->nchars))) {
1237       return;
1238    }
1239    fline = (c - f->offset) * f->h * f->w;
1240    for (py = y; (py < (y + f->h)); py++) {
1241       for (px = x; (px < (x + f->w)); px++) {
1242          if (f->data[fline + cy * f->w + cx]) {
1243             gdImageSetPixel(im, px, py, color);
1244          }
1245          cx++;
1246       }
1247       cx = 0;
1248       cy++;
1249    }
1250 }
1251 
1252 NLM_EXTERN void
gdImageCharV(gdImagePtr im,gdFontPtr f,int x,int y,int c,int color)1253 /*FCN*/gdImageCharV(gdImagePtr im, gdFontPtr f, int x, int y, int c, int color)
1254 {
1255    int h, w;
1256    int px, py;
1257    int fline;
1258    char *da;
1259 
1260    h = f->h;
1261    w = f->w;
1262    fline = (c - f->offset) * h * w;
1263    da = f->data + fline;
1264    for (py = 0; py < h; py++) {
1265       for (px = 0; px < w; px++, da++) {
1266          if (*da) {
1267             gdImageSetPixel(im, x+py, y-px, color);
1268          }
1269       }
1270    }
1271 }
1272 
1273 NLM_EXTERN void
gdImageString(gdImagePtr im,gdFontPtr f,int x,int y,char * s,int color)1274 /*FCN*/gdImageString(gdImagePtr im, gdFontPtr f, int x, int y, char *s, int color)
1275 {
1276    int i;
1277    int l;
1278 
1279    l = strlen(s);
1280    for (i=0; (i<l); i++) {
1281       gdImageChar(im, f, x, y, s[i], color);
1282       x += f->w;
1283    }
1284 }
1285 
1286 NLM_EXTERN void
gdImageStringV(gdImagePtr im,gdFontPtr f,int x,int y,char * s,int color)1287 /*FCN*/gdImageStringV(gdImagePtr im, gdFontPtr f, int x, int y, char *s, int color)
1288 {
1289    int i;
1290    int l;
1291 
1292    l = strlen(s);
1293    for (i=0; (i<l); i++) {
1294       gdImageCharV(im, f, x, y, s[i], color);
1295       y -= f->w;
1296    }
1297 }
1298 
1299 
1300 NLM_EXTERN void
gdImageArc(gdImagePtr im,int cx,int cy,int w,int h,int s,int e,int color)1301 /*FCN*/gdImageArc(gdImagePtr im, int cx, int cy, int w, int h, int s, int e, int color)
1302 {
1303    int i;
1304    int lx = 0, ly = 0;
1305    int w2, h2;
1306 
1307    w2 = w/2;
1308    h2 = h/2;
1309    while (e < s) {
1310       e += 360;
1311    }
1312    for (i=s; (i <= e); i++) {
1313       int x, y;
1314       x = ((long)cost[i % 360] * (long)w2 / costScale) + cx;
1315       y = ((long)sint[i % 360] * (long)h2 / sintScale) + cy;
1316       if (i != s) {
1317          gdImageLine(im, lx, ly, x, y, color);
1318       }
1319       lx = x;
1320       ly = y;
1321    }
1322 }
1323 
1324 
1325 NLM_EXTERN void
gdImageArcEx(gdImagePtr im,int cx,int cy,int rx,int ry,double s_angle,double e_angle,int color,Nlm_Boolean fill)1326 /*FCN*/gdImageArcEx(gdImagePtr im, int cx, int cy, int rx, int ry,
1327                     double s_angle, double e_angle, int color,
1328                     Nlm_Boolean fill)
1329 {
1330   int A, B, C, D, E, F;
1331   int xs, ys, xe, ye;
1332 
1333   double s_cos = cos(s_angle);
1334   double s_sin = sin(s_angle);
1335   double e_cos = cos(e_angle);
1336   double e_sin = sin(e_angle);
1337 
1338   A = ry * ry;
1339   B = 0;
1340   C = rx * rx;
1341   D = -2 * A * cx;
1342   E = -2 * C * cy;
1343   F = A * cx * cx + C * cy * cy - A * C;
1344 
1345 #define ROUNDER(x)  (x ? 0.5 : 0)
1346   xs = cx + (int)(rx * s_cos + ROUNDER(s_cos));
1347   ys = cy + (int)(ry * s_sin + ROUNDER(s_sin));
1348   xe = cx + (int)(rx * e_cos + ROUNDER(e_cos));
1349   ye = cy + (int)(ry * e_sin + ROUNDER(e_sin));
1350 
1351   if ( !fill )
1352     {
1353       /* plain arc */
1354       SDrawPointArc dpa;
1355       dpa.im = im;
1356       dpa.color = color;
1357       s_DrawConic(A, B, C, D, E, F, xs, ys, xe, ye, s_DrawPointArc, &dpa);
1358     }
1359   else
1360     {
1361       /* filled arc */
1362       SStorePoint sp_arc;
1363       sp_arc.xdim   = im->sx;
1364       sp_arc.ydim   = im->sy;
1365       sp_arc.n      = 0;
1366       sp_arc.points = (SPoint *)Nlm_Malloc(2 * (sp_arc.xdim + sp_arc.ydim));
1367       s_DrawConic(A, B, C, D, E, F, xs, ys, xe, ye, s_StorePoint, &sp_arc);
1368       if (!sp_arc.n  &&  (A + B + C + D + E + F > 0))
1369         return; /* point (1,1) to check if it belongs to the internal area */
1370     }
1371 }
1372 
1373 
s_DrawEllipse(gdImagePtr im,int cx,int cy,int rx,int ry,int color,Nlm_Boolean fill,int quadrant)1374 static void s_DrawEllipse(gdImagePtr im,
1375                           int cx, int cy, int rx, int ry, int color,
1376                           Nlm_Boolean fill, int quadrant)
1377 {
1378   SDrawPointEllipse dpe;
1379   int A, B, C, D, E, F;
1380   int xs, ys, xe, ye;
1381 
1382   if (!rx  &&  !ry) {
1383     gdImageSetPixel(im, cx, cy, color);
1384     return;
1385   }
1386 
1387   if ( !rx ) {
1388     ys = (quadrant == 0  ||  quadrant == 3  ||  quadrant == 4) ?
1389       cy + ry : cy;
1390     ye = (quadrant == 0  ||  quadrant == 1  ||  quadrant == 2) ?
1391       cy - ry : cy;
1392     gdImageLine(im, cx, ys, cx, ye, color);
1393     return;
1394   }
1395 
1396   if ( !ry ) {
1397     xs = (quadrant == 0  ||  quadrant == 1  ||  quadrant == 4) ?
1398       cx + rx : cx;
1399     xe = (quadrant == 0  ||  quadrant == 2  ||  quadrant == 3) ?
1400       cx - rx : cx;
1401     gdImageLine(im, xs, cy, xe, cy, color);
1402     return;
1403   }
1404 
1405   ASSERT( rx > 0  &&  ry > 0 );
1406 
1407   A = ry * ry;
1408   B = 0;
1409   C = rx * rx;
1410   D = 0;
1411   E = 0;
1412   F = - A * C;
1413 
1414   xs = rx;
1415   ys = 0;
1416   xe = 0;
1417   ye = ry;
1418 
1419   dpe.im = im;
1420   dpe.color = color;
1421   dpe.cx = cx;
1422   dpe.cy = cy;
1423   dpe.prev_y = 999;
1424   dpe.quadrant = quadrant;
1425   s_DrawConic(A, B, C, D, E, F, xs, ys, xe, ye,
1426               fill ? s_DrawPointFilledEllipse : s_DrawPointEllipse, &dpe);
1427 }
1428 
1429 
1430 NLM_EXTERN void
gdImageEllipse(gdImagePtr im,int cx,int cy,int rx,int ry,int color,Nlm_Boolean fill)1431 /*FCN*/gdImageEllipse(gdImagePtr im, int cx, int cy, int rx, int ry, int color,
1432                       Nlm_Boolean fill)
1433 {
1434   s_DrawEllipse(im, cx, cy, rx, ry, color, fill, 0);
1435 }
1436 
1437 NLM_EXTERN void
gdImageQuadrant(gdImagePtr im,int cx,int cy,int rx,int ry,int color,Nlm_Boolean fill,int quadrant)1438 /*FCN*/gdImageQuadrant(gdImagePtr im,
1439                        int cx, int cy, int rx, int ry, int color,
1440                        Nlm_Boolean fill, int quadrant)
1441 {
1442   s_DrawEllipse(im, cx, cy, rx, ry, color, fill, quadrant);
1443 }
1444 
1445 
1446 NLM_EXTERN void
gdImageRectangle(gdImagePtr im,int x1,int y1,int x2,int y2,int color)1447 /*FCN*/gdImageRectangle(gdImagePtr im,
1448                         int x1, int y1, int x2, int y2, int color)
1449 {
1450    gdImageLine(im, x1, y1, x2, y1, color);
1451    gdImageLine(im, x1, y2, x2, y2, color);
1452    gdImageLine(im, x1, y1, x1, y2, color);
1453    gdImageLine(im, x2, y1, x2, y2, color);
1454 }
1455 
1456 NLM_EXTERN void
gdImageFilledRectangle(gdImagePtr im,int x1,int y1,int x2,int y2,int color)1457 /*FCN*/gdImageFilledRectangle(gdImagePtr im,
1458                               int x1, int y1, int x2, int y2, int color)
1459 {
1460    int x, y;
1461 
1462    for (y=y1; (y<=y2); y++) {
1463       for (x=x1; (x<=x2); x++) {
1464          gdImageSetPixel(im, x, y, color);
1465       }
1466    }
1467 }
1468 
1469 NLM_EXTERN void
gdImageRoundRectangle(gdImagePtr im,int x1,int y1,int x2,int y2,int oval_w,int oval_h,int color,Nlm_Boolean fill)1470 /*FCN*/gdImageRoundRectangle(gdImagePtr im,
1471                              int x1, int y1, int x2, int y2,
1472                              int oval_w, int oval_h,
1473                              int color, Nlm_Boolean fill)
1474 {
1475   int X1 = MIN(x1, x2);
1476   int Y1 = MIN(y1, y2);
1477   int X2 = MAX(x1, x2);
1478   int Y2 = MAX(y1, y2);
1479 
1480   int w = x2 - x1 + 1;
1481   int h = y2 - y1 + 1;
1482 
1483   if (oval_w > w/2)
1484     oval_w = w/2;
1485   if (oval_h > h/2)
1486     oval_h = h/2;
1487 
1488   x1 = X1;  y1 = Y1;  x2 = X2;  y2 = Y2;
1489 
1490   X1 = X1 + oval_w;  Y1 = Y1 + oval_h;
1491   X2 = X2 - oval_w;  Y2 = Y2 - oval_h;
1492 
1493   if ( fill ) {
1494     gdImageFilledRectangle(im, x1, Y1, x2, Y2, color);
1495     gdImageFilledRectangle(im, X1, y1, X2, Y1, color);
1496     gdImageFilledRectangle(im, X1, Y2, X2, y2, color);
1497   }
1498   else {
1499     gdImageLine(im, x1, Y1, x1, Y2, color);
1500     gdImageLine(im, x2, Y1, x2, Y2, color);
1501     gdImageLine(im, X1, y1, X2, y1, color);
1502     gdImageLine(im, X1, y2, X2, y2, color);
1503   }
1504 
1505   gdImageQuadrant(im, X2, Y1, oval_w, oval_h, color, fill, 1);
1506   gdImageQuadrant(im, X1, Y1, oval_w, oval_h, color, fill, 2);
1507   gdImageQuadrant(im, X1, Y2, oval_w, oval_h, color, fill, 3);
1508   gdImageQuadrant(im, X2, Y2, oval_w, oval_h, color, fill, 4);
1509 }
1510 
1511 
1512 NLM_EXTERN void
gdImagePolygon(gdImagePtr im,gdPointPtr p,int n,int c)1513 /*FCN*/gdImagePolygon(gdImagePtr im, gdPointPtr p, int n, int c)
1514 {
1515    int i;
1516    int lx, ly;
1517 
1518    if (!n) {
1519       return;
1520    }
1521    lx = p->x;
1522    ly = p->y;
1523    gdImageLine(im, lx, ly, p[n-1].x, p[n-1].y, c);
1524    for (i=1; (i < n); i++) {
1525       p++;
1526       gdImageLine(im, lx, ly, p->x, p->y, c);
1527       lx = p->x;
1528       ly = p->y;
1529    }
1530 }
1531 
1532 NLM_EXTERN void
gdImageFilledPolygon(gdImagePtr im,gdPointPtr p,int n,int c)1533 /*FCN*/gdImageFilledPolygon(gdImagePtr im, gdPointPtr p, int n, int c)
1534 {
1535    int i;
1536    int y;
1537    int y1, y2;
1538    size_t ints;
1539 
1540    if (!n) {
1541       return;
1542    }
1543    if (!im->polyAllocated) {
1544       im->polyInts = (int *) Nlm_Malloc(sizeof(int) * n);
1545       im->polyAllocated = n;
1546    }
1547    if (im->polyAllocated < n) {
1548       while (im->polyAllocated < n) {
1549          im->polyAllocated *= 2;
1550       }
1551       im->polyInts = (int *) realloc(im->polyInts,
1552          sizeof(int) * im->polyAllocated);
1553    }
1554    y1 = p[0].y;
1555    y2 = p[0].y;
1556    for (i=1; (i < n); i++) {
1557       if (p[i].y < y1) {
1558          y1 = p[i].y;
1559       }
1560       if (p[i].y > y2) {
1561          y2 = p[i].y;
1562       }
1563    }
1564    for (y=y1; (y <= y2); y++) {
1565       int interLast = 0;
1566       int dirLast = 0;
1567       int interFirst = 1;
1568       ints = 0;
1569       for (i=0; (i <= n); i++) {
1570          int x1, x2;
1571          int y1, y2;
1572          int dir;
1573          int ind1, ind2;
1574          int lastInd1 = 0;
1575          if ((i == n) || (!i)) {
1576             ind1 = n-1;
1577             ind2 = 0;
1578          } else {
1579             ind1 = i-1;
1580             ind2 = i;
1581          }
1582          y1 = p[ind1].y;
1583          y2 = p[ind2].y;
1584          if (y1 < y2) {
1585             y1 = p[ind1].y;
1586             y2 = p[ind2].y;
1587             x1 = p[ind1].x;
1588             x2 = p[ind2].x;
1589             dir = -1;
1590          } else if (y1 > y2) {
1591             y2 = p[ind1].y;
1592             y1 = p[ind2].y;
1593             x2 = p[ind1].x;
1594             x1 = p[ind2].x;
1595             dir = 1;
1596          } else {
1597             gdImageLine(im,
1598                p[ind1].x, y1,
1599                p[ind2].x, y1,
1600                c);
1601             continue;
1602          }
1603          if ((y >= y1) && (y <= y2)) {
1604             int inter;
1605             int tmp = y2 - y1;
1606             if ( x2 > x1 ){
1607               inter = ((y-y1) * (x2-x1) + tmp/2)/tmp + x1;
1608             } else{
1609               inter = ((y-y1) * (x2-x1) - tmp/2)/tmp + x1;
1610             }
1611             if (!interFirst) {
1612                if ((p[ind1].y == p[lastInd1].y) &&
1613                   (p[ind1].x != p[lastInd1].x)) {
1614                   if (dir == dirLast) {
1615                      if (inter > interLast) {
1616                         im->polyInts[ints] = inter;
1617                      }
1618                      continue;
1619                   }
1620                }
1621                if (inter == interLast) {
1622                   if (dir == dirLast) {
1623                      continue;
1624                   }
1625                }
1626             }
1627             if (i > 0) {
1628                im->polyInts[ints++] = inter;
1629             }
1630             lastInd1 = i;
1631             dirLast = dir;
1632             interLast = inter;
1633             interFirst = 0;
1634          }
1635       }
1636 
1637       if (ints > 1) {
1638         size_t j;
1639         HeapSort((Nlm_VoidPtr)im->polyInts, ints, sizeof(int), &gdCompareInt);
1640         for (j = 0;  j < (ints-1);  j += 2) {
1641           gdImageLine(im, im->polyInts[j], y, im->polyInts[j+1], y, c);
1642         }
1643       }
1644    }
1645 }
1646 
1647 NLM_EXTERN void
gdImageInterlace(gdImagePtr im,int interlaceArg)1648 /*FCN*/gdImageInterlace(gdImagePtr im, int interlaceArg)
1649 {
1650    im->interlace = interlaceArg;
1651 }
1652 
1653 NLM_EXTERN void
gdImageCopyBits(gdImagePtr im,int x,int y,int w,int h,char * ptr,int color)1654 /*FCN*/gdImageCopyBits ( gdImagePtr im, int x, int y, int w, int h,
1655                          char * ptr, int color )
1656 {
1657   int i,j;
1658   unsigned char * uptr;
1659   int index;
1660 
1661   for ( i=0; i<w; i++ ){
1662     for ( j=0; j<h; j++ ){
1663       index = i+j*w;
1664       uptr = (unsigned char *)(ptr+index/8);
1665       index = 7 - index%8;
1666       index = (int)(*uptr >> index);
1667       if ( index & 0x1 ){
1668         gdImageSetPixel ( im, i+x, j+y, color );
1669       } else {
1670         gdImageSetPixel ( im, i+x, j+y, 0 );
1671       }
1672     }
1673   }
1674 }
1675 
1676 NLM_EXTERN void
gdImageSelectPattern(gdImagePtr im,const unsigned char pattern[])1677 /*FCN*/gdImageSelectPattern(gdImagePtr im, const unsigned char pattern[])
1678 {
1679   size_t i;
1680   if ( !im )
1681     return;
1682   ASSERT ( sizeof(im->pattern) == 8 );
1683 
1684   im->use_pattern = 0;
1685   for (i = 0;  i < sizeof(im->pattern);  i++)
1686     {
1687       if ((im->pattern[i] = pattern[i]) != 0xFF)
1688         im->use_pattern = 1;
1689     }
1690 }
1691 
1692 NLM_EXTERN void
gdImageCopy(gdImagePtr dst,gdImagePtr src,int dstX,int dstY,int srcX,int srcY,int w,int h)1693 /*FCN*/gdImageCopy(gdImagePtr dst, gdImagePtr src, int dstX, int dstY, int srcX, int srcY, int w, int h)
1694 {
1695 	int c;
1696 	int x, y;
1697 	int tox, toy;
1698 	int i;
1699 	int colorMap[gdMaxColors];
1700 	for (i=0; (i<gdMaxColors); i++) {
1701 		colorMap[i] = (-1);
1702 	}
1703 	toy = dstY;
1704 	for (y=srcY; (y < (srcY + h)); y++) {
1705 		tox = dstX;
1706 		for (x=srcX; (x < (srcX + w)); x++) {
1707 			int nc;
1708 			c = gdImageGetPixel(src, x, y);
1709 			/* Added 7/24/95: support transparent copies */
1710 			if (gdImageGetTransparent(src) == c) {
1711 				tox++;
1712 				continue;
1713 			}
1714 			/* Have we established a mapping for this color? */
1715 			if (colorMap[c] == (-1)) {
1716 				/* If it's the same image, mapping is trivial */
1717 				if (dst == src) {
1718 					nc = c;
1719 				} else {
1720 					/* First look for an exact match */
1721 					nc = gdImageColorExact(dst,
1722 						src->red[c], src->green[c],
1723 						src->blue[c]);
1724 				}
1725 				if (nc == (-1)) {
1726 					/* No, so try to allocate it */
1727 					nc = gdImageColorAllocate(dst,
1728 						src->red[c], src->green[c],
1729 						src->blue[c]);
1730 					/* If we're out of colors, go for the
1731 						closest color */
1732 					if (nc == (-1)) {
1733 						nc = gdImageColorClosest(dst,
1734 							src->red[c], src->green[c],
1735 							src->blue[c]);
1736 					}
1737 				}
1738 				colorMap[c] = nc;
1739 			}
1740 			gdImageSetPixel(dst, tox, toy, colorMap[c]);
1741 			tox++;
1742 		}
1743 		toy++;
1744 	}
1745 }
1746 
1747 NLM_EXTERN void
gdImageCopyResized(gdImagePtr dst,gdImagePtr src,int dstX,int dstY,int srcX,int srcY,int dstW,int dstH,int srcW,int srcH)1748 /*FCN*/gdImageCopyResized(gdImagePtr dst, gdImagePtr src, int dstX, int dstY, int srcX, int srcY, int dstW, int dstH, int srcW, int srcH)
1749 {
1750 	int c;
1751 	int x, y;
1752 	int tox, toy;
1753 	int ydest;
1754 	int i;
1755 	int colorMap[gdMaxColors];
1756 	/* Stretch vectors */
1757 	int *stx;
1758 	int *sty;
1759 	/* We only need to use floating point to determine the correct
1760 		stretch vector for one line's worth. */
1761 	double accum;
1762 	stx = (int *) MemNew(sizeof(int) * srcW);
1763 	sty = (int *) MemNew(sizeof(int) * srcH);
1764 	accum = 0;
1765 	for (i=0; (i < srcW); i++) {
1766 		int got;
1767 		accum += (double)dstW/(double)srcW;
1768 		got = (int)floor(accum);
1769 		stx[i] = got;
1770 		accum -= got;
1771 	}
1772 	accum = 0;
1773 	for (i=0; (i < srcH); i++) {
1774 		int got;
1775 		accum += (double)dstH/(double)srcH;
1776 		got = (int)floor(accum);
1777 		sty[i] = got;
1778 		accum -= got;
1779 	}
1780 	for (i=0; (i<gdMaxColors); i++) {
1781 		colorMap[i] = (-1);
1782 	}
1783 	toy = dstY;
1784 	for (y=srcY; (y < (srcY + srcH)); y++) {
1785 		for (ydest=0; (ydest < sty[y-srcY]); ydest++) {
1786 			tox = dstX;
1787 			for (x=srcX; (x < (srcX + srcW)); x++) {
1788 				int nc;
1789 				if (!stx[x - srcX]) {
1790 					continue;
1791 				}
1792 				c = gdImageGetPixel(src, x, y);
1793 				/* Added 7/24/95: support transparent copies */
1794 				if (gdImageGetTransparent(src) == c) {
1795 					tox += stx[x-srcX];
1796 					continue;
1797 				}
1798 				/* Have we established a mapping for this color? */
1799 				if (colorMap[c] == (-1)) {
1800 					/* If it's the same image, mapping is trivial */
1801 					if (dst == src) {
1802 						nc = c;
1803 					} else {
1804 						/* First look for an exact match */
1805 						nc = gdImageColorExact(dst,
1806 							src->red[c], src->green[c],
1807 							src->blue[c]);
1808 					}
1809 					if (nc == (-1)) {
1810 						/* No, so try to allocate it */
1811 						nc = gdImageColorAllocate(dst,
1812 							src->red[c], src->green[c],
1813 							src->blue[c]);
1814 						/* If we're out of colors, go for the
1815 							closest color */
1816 						if (nc == (-1)) {
1817 							nc = gdImageColorClosest(dst,
1818 								src->red[c], src->green[c],
1819 								src->blue[c]);
1820 						}
1821 					}
1822 					colorMap[c] = nc;
1823 				}
1824 				for (i=0; (i < stx[x - srcX]); i++) {
1825 					gdImageSetPixel(dst, tox, toy, colorMap[c]);
1826 					tox++;
1827 				}
1828 			}
1829 			toy++;
1830 		}
1831 	}
1832 	free(stx);
1833 	free(sty);
1834 }
1835 
1836 
gdImageSetClip(gdImagePtr im,const gdRect * clip,gdRect * old_clip)1837 NLM_EXTERN int gdImageSetClip(gdImagePtr im,
1838                               const gdRect *clip, gdRect *old_clip)
1839 {
1840   static const gdRect empty_clip = { {0, 0}, {0, 0} };
1841 
1842   int was_clip = im->use_clip;
1843   if ( old_clip ) {
1844     if ( im->use_clip )
1845       MemCpy(old_clip, &im->clip, sizeof(gdRect));
1846     else
1847       MemSet(old_clip, '\0', sizeof(gdRect));
1848   }
1849 
1850   if (clip  &&  MemCmp(&clip, &empty_clip, sizeof(gdRect))) {
1851     im->clip.lt.x = MIN(clip->lt.x, clip->rb.x);
1852     im->clip.lt.y = MIN(clip->lt.y, clip->rb.y);
1853     im->clip.rb.x = MAX(clip->lt.x, clip->rb.x);
1854     im->clip.rb.y = MAX(clip->lt.y, clip->rb.y);
1855     im->use_clip = 1;
1856   } else {
1857     im->use_clip = 0;
1858   }
1859 
1860   s_ComposeEffClip(im);
1861 
1862   return was_clip;
1863 }
1864 
1865 
gdImageGetDimensions(gdImagePtr im,int * width,int * height)1866 NLM_EXTERN void gdImageGetDimensions(gdImagePtr im, int* width, int* height)
1867 {
1868   if ( width )
1869     *width = im->sx;
1870   if ( height )
1871     *height = im->sy;
1872 }
1873 
1874 
gdImageGetAutoCropRectangle(gdImagePtr im,gdRect * rect)1875 NLM_EXTERN void gdImageGetAutoCropRectangle(gdImagePtr im, gdRect* rect)
1876 {
1877   int width  = im->sx;
1878   int height = im->sy;
1879   int x, y, xb, yb, ye;
1880   Uint1 *base_ptr, *ptr;
1881 
1882   /* find upper colored pixel (CP);  background is zero */
1883   for (y = 0, base_ptr = im->pixels;  y < height;  y++, base_ptr += width) {
1884     for (x = 0, ptr = base_ptr;  x < width  &&  !*ptr;  x++, ptr++) ;
1885     if (x < width)
1886       break;
1887   }
1888   rect->lt.y = yb = y;
1889 
1890   /* Found no CPs at all? */
1891   if (y == height) {
1892     rect->lt.x = rect->lt.y = 0;
1893     rect->rb.x = MAX(im->sx-1, 0);
1894     rect->rb.y = MAX(im->sy-1, 0);
1895     return;
1896   }
1897 
1898   /* find lower CP */
1899   base_ptr = im->pixels + width * (height - 1);
1900   for (y = height-1;  y > yb;  y--, base_ptr -= width) {
1901     for (x = 0, ptr = base_ptr;  x < width  &&  !*ptr;  x++, ptr++) ;
1902     if (x < width)
1903       break;
1904   }
1905   rect->rb.y = ye = y;
1906 
1907   /* find left CP */
1908   base_ptr = im->pixels + width * yb;
1909   for (x = 0;  x < width;  x++, base_ptr++) {
1910     for (y = yb, ptr = base_ptr;  y <= ye  &&  !*ptr;  y++, ptr += width) ;
1911     if (y <= ye)
1912       break;
1913   }
1914   rect->lt.x = xb = x;
1915 
1916   /* find right CP */
1917   base_ptr = im->pixels + width * (ye + 1) - 1;
1918   for (x = width-1;  x > xb;  x--, base_ptr--) {
1919     for (y = ye, ptr = base_ptr;  y >= yb  &&  !*ptr;  y--, ptr -= width) ;
1920     if (y >= yb)
1921       break;
1922   }
1923   rect->rb.x = x;
1924 }
1925 
1926 
1927 
gdImageCrop(gdImagePtr im,const gdRect * rect)1928 NLM_EXTERN void gdImageCrop(gdImagePtr im, const gdRect* rect)
1929 {
1930   Uint1* base_ptr = im->pixels;
1931   gdRect crop     = *rect;
1932   int    width    = im->sx;
1933 
1934   int    new_width;
1935   int    y;
1936   Uint1* ptr;
1937 
1938   /* adjust crop rectangle to fit image boundaries */
1939   s_CropRectImage(&crop, im);
1940 
1941   /* nothing to crop;  or crop without memcpy? */
1942   if (crop.lt.x == 0  &&  crop.lt.y == 0  &&  crop.rb.x == im->sx - 1) {
1943     im->sy = crop.rb.y + 1;
1944     return;
1945   }
1946 
1947   /* "crop" -- move the content of crop rectangle to (0, 0) */
1948   new_width = crop.rb.x - crop.lt.x + 1;
1949   ptr = base_ptr + crop.lt.y * width + crop.lt.x;
1950   for (y = crop.lt.y;  y <= crop.rb.y;  y++) {
1951     memcpy(base_ptr, ptr, new_width);
1952     base_ptr += new_width;
1953     ptr  += width;
1954   }
1955 
1956   /* alternate image width/height */
1957   im->sx = new_width;
1958   im->sy = crop.rb.y - crop.lt.y + 1;
1959 }
1960 
1961 
gdImageAutoCrop(gdImagePtr im,int border)1962 NLM_EXTERN void gdImageAutoCrop(gdImagePtr im, int border)
1963 {
1964   gdRect crop;
1965   if (border < 0)
1966     border = -border;
1967 
1968   gdImageGetAutoCropRectangle(im, &crop);
1969   s_ExpandRect(&crop, border, border);
1970   gdImageCrop(im, &crop);
1971 }
1972 
1973 
1974 /*EOF*/
1975