MHEG5  18.9.0
MHEG5 Documentation
mg_dla.inl
Go to the documentation of this file.
1 /*******************************************************************************
2  * Copyright © 2014 The DTVKit Open Software Foundation Ltd (www.dtvkit.org)
3  * Copyright © 2008 Ocean Blue Software Ltd
4  *
5  * This file is part of a DTVKit Software Component
6  * You are permitted to copy, modify or distribute this file subject to the terms
7  * of the DTVKit 1.0 Licence which can be found in licence.txt or at www.dtvkit.org
8  *
9  * THIS CODE AND INFORMATION ARE PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND,
10  * EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE IMPLIED WARRANTIES
11  * OF MERCHANTABILITY AND/OR FITNESS FOR A PARTICULAR PURPOSE.
12  *
13  * If you or your organisation is not a member of DTVKit then you have access
14  * to this source code outside of the terms of the licence agreement
15  * and you are expected to delete this and any associated files immediately.
16  * Further information on DTVKit, membership and terms can be found at www.dtvkit.org
17  *******************************************************************************/
25 #undef DEBUG_FUNCTION
26 
27 /*---includes for this file--------------------------------------------------*/
28 
29 /* compiler library header files */
30 #include <stdlib.h>
31 #include <stdio.h>
32 #include <string.h>
33 
34 /* third party header files */
35 
36 /* OBS header files */
37 #include "dla_inl.h"
38 #include "glue_memory.h"
39 #include "glue_debug.h"
40 #include "mg_osd.h"
41 #include "mg_api.h"
42 #include "mh5assert.h"
43 
44 /*---constant definitions for this file--------------------------------------*/
45 
46 #define ABS(x) ((x) < 0 ? -(x) : (x))
47 #define SGN(x) ((x) < 0 ? -1 : 1)
48 #define MIN(a,b) ((a) < (b) ? (a) : (b))
49 #define MAX(a,b) ((a) > (b) ? (a) : (b))
50 
51 /* Advances the index by one vertex forward through the vertex list, wrapping
52  * at the end of the list
53  */
54 #define INDEX_FORWARD(index) \
55  index = (index + 1) % vertex_list->length;
56 
57 /* Advances the index by one vertex backward through the vertex list, wrapping
58  * at the start of the list
59  */
60 #define INDEX_BACKWARD(index) \
61  index = (index - 1 + vertex_list->length) % vertex_list->length;
62 
63 /* Advances the index by one vertex either forward or backward through the
64  * vertex list, wrapping at either end of the list
65  */
66 #define INDEX_MOVE(index,direction) \
67  if (direction > 0) \
68  index = (index + 1) % vertex_list->length; \
69  else \
70  index = (index - 1 + vertex_list->length) % vertex_list->length;
71 
72 #define DEBUG_DLA 0
73 #undef DEBUG_DRAW_SECTOR
74 
75 /*---local typedef structs for this file-------------------------------------*/
76 
77 typedef struct point_list_header {
78  U16BIT length;
79  S_POINT *point_list;
80 } S_POINT_LIST_HEADER;
81 
82 typedef struct hline {
83  U16BIT x_start;
84  U16BIT x_end;
85 } S_HLINE;
86 
87 typedef struct hline_list {
88  U16BIT length;
89  S32BIT y_start;
90  S_HLINE *hline;
91 } S_HLINE_LIST;
92 
93 typedef struct
94 {
95  U32BIT msw;
96  U32BIT lsw;
97 } S_64_BIT;
98 
99 /*---local (static) variable declarations for this file----------------------*/
100 /* (internal variables declared static to make them local) */
101 
102 static DLA_Surface* dla_canvas;
103 
104 static const U32BIT sd_tan_table_32[45] = {
105  0x00000000, 0x0477ef65, 0x08f0914a, 0x0d6a98a2, 0x11e6b93a, 0x1665a834,
106  0x1ae81c75, 0x1f6ecf19, 0x23fa7bf0, 0x288be1f7, 0x2d23c3d7, 0x31c2e86e,
107  0x366a1b58, 0x3b1a2d82, 0x3fd3f5c2, 0x4498517a, 0x49682546, 0x4e445dae,
108  0x532defed, 0x5825dabe, 0x5d2d273c, 0x6244e9d4, 0x676e4342, 0x6caa61ad,
109  0x71fa81d2, 0x775ff04d, 0x7cdc0afd, 0x82704286, 0x881e1bfb, 0x8de732af,
110  0x93cd3a2c, 0x99d20064, 0x9ff77016, 0xa63f9376, 0xacac9714, 0xb340cd1d,
111  0xb9feb0ec, 0xc0e8eb10, 0xc80255b6, 0xcf4e01a3, 0xd6cf3bc1, 0xde89935d,
112  0xe680e123, 0xeeb94f05, 0xf7376129
113 };
114 
115 /* Note - 55 values, not 45, becuase tan(t_HD) = 1 when t_HD = 54.89 deg */
116 static const U32BIT hd_tan_table_32[55] = {
117  0x00000000, 0x03245453, 0x06492628, 0x096ef351, 0x0c963a3d, 0x0fbf7a44,
118  0x12eb3402, 0x1619e99d, 0x194c1f25, 0x1c825ae1, 0x1fbd25b3, 0x22fd0b6d,
119  0x26429b3a, 0x298e67ff, 0x2ce108cc, 0x303b194a, 0x339d3a35, 0x370811de,
120  0x3a7c4cb2, 0x3dfa9dcd, 0x4183bf96, 0x45187469, 0x48b9874a, 0x4c67ccae,
121  0x50242348, 0x53ef74f6, 0x57cab7b9, 0x5bb6eec6, 0x5fb52bad, 0x63c68fa3,
122  0x67ec4ce7, 0x6c27a846, 0x7079facf, 0x74e4b3af, 0x79695a3a, 0x7e099038,
123  0x82c71466, 0x87a3c547, 0x8ca1a444, 0x91c2d926, 0x9709b604, 0x9c78bb9d,
124  0xa2129e4c, 0xa7da4b90, 0xadd2f051, 0xb3ffffff, 0xba653ca2, 0xc106c00a,
125  0xc7e90651, 0xcf10f9e8, 0xd684016b, 0xde480f9b, 0xe663b5dd, 0xeede39b2,
126  0xf7bfadcc
127 };
128 
129 /* 36 values for reversed table */
130 static const U32BIT hd_tan_table_rev_32[36] = {
131  0x00000000, 0x065aee12, 0x0cb6da04, 0x1314c252, 0x1975a6b9, 0x1fda88d3,
132  0x26446cbd, 0x2cb459bd, 0x332b5af0, 0x39aa7ff3, 0x4032dda4, 0x46c58ed6,
133  0x4d63b51d, 0x540e799d, 0x5ac70de0, 0x618eacc4, 0x68669b69, 0x6f502a36,
134  0x764cb5f0, 0x7d5da8e0, 0x84847c12, 0x8bc2b8a5, 0x9319f942, 0x9a8beba1,
135  0xa21a523c, 0xa9c7061e, 0xb193f8df, 0xb98336ca, 0xc196e938, 0xc9d15927,
136  0xd234f206, 0xdac444d2, 0xe3820b81, 0xec712cbf, 0xf594c01d, 0xfef012a6
137 };
138 
139 /*---local function prototypes for this file---------------------------------*/
140 /* (internal functions declared static to make them local) */
141 
142 static void Swap(S16BIT *a, S16BIT *b);
143 static BOOLEAN ClipLine(S16BIT *x1, S16BIT *y1, S16BIT *x2, S16BIT *y2);
144 static BOOLEAN ClipPolygon(S_POLYGON *polygon);
145 static BOOLEAN ClipPolygonLeft(S_POLYGON *polygon);
146 static BOOLEAN ClipPolygonRight(S_POLYGON *polygon);
147 static BOOLEAN ClipPolygonTop(S_POLYGON *polygon);
148 static BOOLEAN ClipPolygonBottom(S_POLYGON *polygon);
149 static BOOLEAN AppendPoint(S_POINT_LIST ***ppl, S16BIT x, S16BIT y);
150 static BOOLEAN FillPolygon( S_POLYGON *polygon, DLAColor colour );
151 static void FillConvexPolygon(S_POINT_LIST_HEADER *vertex_list, DLAColor colour);
152 static void FreePolygon(S_POLYGON *polygon);
153 static void FreePointList(S_POINT_LIST *pl);
154 static void FillSimpleRectangle(S16BIT x1, S16BIT y1, S16BIT x2, S16BIT y2, DLAColor colour);
155 static void DrawLine(S16BIT x1, S16BIT y1, S16BIT x2, S16BIT y2, U16BIT width, DLAColor colour);
156 static void DrawThinLine(S16BIT x1, S16BIT y1, S16BIT x2, S16BIT y2, DLAColor colour);
157 static void DrawFatLine(S16BIT x1, S16BIT y1, S16BIT x2, S16BIT y2, U16BIT width, DLAColor colour);
158 static void DrawHorizontalLineList(S_HLINE_LIST *hline_list, DLAColor colour);
159 static void FillEllipse(S16BIT x, S16BIT y, U16BIT w, U16BIT h, DLAColor colour);
160 static void DrawEllipse(S16BIT x, S16BIT y, U16BIT w, U16BIT h, U16BIT width, DLAColor colour);
161 static void DrawArc(S16BIT x, S16BIT y, U16BIT w, U16BIT h, U16BIT start, U16BIT arc, U16BIT width, DLAColor colour);
162 static void DrawSector(S16BIT x, S16BIT y, U16BIT w, U16BIT h, U16BIT start, U16BIT arc, U16BIT width, DLAColor fill_colour, DLAColor line_colour);
163 static void FillLine(DLAColor *buffer, S16BIT offset, U16BIT length, DLAColor colour);
164 static void FillTriangle(S16BIT x1, S16BIT y1, S16BIT x2, S16BIT y2,
165  S16BIT x3, S16BIT y3, DLAColor colour);
166 static void FillCircle(S16BIT cx, S16BIT cy, U16BIT width, DLAColor colour);
167 static void PutPixel(S16BIT x, S16BIT y, DLAColor c);
168 static void GetHitPoints(U32BIT rx, U32BIT ry, U16BIT angle, S32BIT *hx, S32BIT *hy);
169 static void ScanEdge(S32BIT x1, S32BIT y1, S32BIT x2, S32BIT y2,
170  S32BIT set_x_start, S32BIT skip_first,
171  S_HLINE **edge_point);
172 static void S64AssignS32(S_64_BIT *s64, S32BIT s32);
173 static void S64AddS32(S_64_BIT *s64, S32BIT s32);
174 static void S64AddS64(S_64_BIT *s64_var, S_64_BIT *s64_value);
175 static void S64SubtractS32(S_64_BIT *s64, S32BIT s32);
176 static void S64MultiplyS32(S_64_BIT *s64, S32BIT s32);
177 static S32BIT S64CompareS64(S_64_BIT *s64_a, S_64_BIT *s64_b);
178 
179 
180 /*---local function definitions----------------------------------------------*/
181 
188 static void Swap(S16BIT *a, S16BIT *b)
189 {
190  S16BIT t = *a;
191  *a = *b;
192  *b = t;
193 }
194 
203 static BOOLEAN ClipLine(S16BIT *x1, S16BIT *y1, S16BIT *x2, S16BIT *y2)
204 {
205  S32BIT mx1 = *x1, my1 = *y1, mx2 = *x2, my2 = *y2;
206  S32BIT dx = mx2 - mx1, adx = ABS(dx), hadx = adx/2, sdx = SGN(dx);
207  S32BIT dy = my2 - my1, ady = ABS(dy), hady = ady/2, sdy = SGN(dy);
208  S32BIT factor = adx * ady;
209  S32BIT t0 = 0, t1 = factor, r;
210  BOOLEAN draw;
211 
212  FUNCTION_START(ClipLine);
213 
214  /* clip left */
215  r = -mx1 * ady * sdx;
216  if (r >= 0 && r <= factor)
217  {
218  if (mx2 > mx1)
219  {
220  t0 = MAX(t0, r);
221  }
222  else
223  {
224  t1 = MIN(t1, r);
225  }
226  }
227 
228  /* clip right */
229  r = (dla_canvas->width-1 - mx1) * ady * sdx;
230  if (t0 <= t1 && r >= 0 && r <= factor)
231  {
232  if (mx2 < mx1)
233  {
234  t0 = MAX(t0, r);
235  }
236  else
237  {
238  t1 = MIN(t1, r);
239  }
240  }
241 
242  /* clip top */
243  r = -my1 * adx * sdy;
244  if (t0 <= t1 && r >= 0 && r <= factor)
245  {
246  if (my2 > my1)
247  {
248  t0 = MAX(t0, r);
249  }
250  else
251  {
252  t1 = MIN(t1, r);
253  }
254  }
255 
256  /* clip bottom */
257  r = (dla_canvas->height-1 - my1) * adx * sdy;
258  if (t0 <= t1 && r >= 0 && r <= factor)
259  {
260  if (my2 < my1)
261  {
262  t0 = MAX(t0, r);
263  }
264  else
265  {
266  t1 = MIN(t1, r);
267  }
268  }
269 
270  if (t0 <= t1)
271  {
272  *x2 = *x1 + (t1 + hady) / ady * sdx;
273  *x1 += (t0 + hady) / ady * sdx;
274  *y2 = *y1 + (t1 + hadx) / adx * sdy;
275  *y1 += (t0 + hadx) / adx * sdy;
276  draw = TRUE;
277  }
278  else
279  {
280  draw = FALSE;
281  }
282 
283  FUNCTION_FINISH(ClipLine);
284 
285  return draw;
286 }
287 
295 static BOOLEAN ClipPolygon(S_POLYGON *polygon)
296 {
297  BOOLEAN success;
298 
299  FUNCTION_START(ClipPolygon);
300 
301  success = ClipPolygonLeft(polygon);
302  success = success && ClipPolygonRight(polygon);
303  success = success && ClipPolygonTop(polygon);
304  success = success && ClipPolygonBottom(polygon);
305 
306  FUNCTION_FINISH(ClipPolygon);
307 
308  return success;
309 }
310 
316 static BOOLEAN ClipPolygonLeft(S_POLYGON *polygon)
317 {
318  S_POINT_LIST *cp, *np;
319  S_POINT_LIST *new_list = NULL;
320  S_POINT_LIST **ppl;
321  U16BIT count;
322  S16BIT cx, cy, nx, ny;
323  BOOLEAN clipped;
324  BOOLEAN success;
325 
326  FUNCTION_START(ClipPolygonLeft);
327 
328  /* Check whether we need to do anything */
329  cp = polygon->point_list;
330  clipped = FALSE;
331  while (!clipped && cp != NULL)
332  {
333  if (cp->point.x < 0)
334  {
335  clipped = TRUE;
336  }
337  else
338  {
339  cp = cp->next;
340  }
341  }
342 
343  if (clipped)
344  {
345  cp = polygon->point_list;
346  ppl = &new_list;
347  count = 0;
348  success = TRUE;
349  while (success && cp != NULL)
350  {
351  np = cp->next;
352  if (np == NULL)
353  {
354  /* Cycle around */
355  np = polygon->point_list;
356  }
357 
358  cx = cp->point.x;
359  cy = cp->point.y;
360  nx = np->point.x;
361  ny = np->point.y;
362 
363 #if DEBUG_DLA
364  printf("current point: (%d, %d)\n", cx, cy);
365  printf("next point: (%d, %d)\n", nx, ny);
366 #endif
367 
368  if (cx >= 0 && nx < 0)
369  {
370  /* current point inside, next point outside */
371 #if DEBUG_DLA
372  printf("(0, %d)\n", cy - cx * (cy - ny) / (cx - nx));
373 #endif
374  success = AppendPoint(&ppl, 0, cy - cx * (cy - ny) / (cx - nx));
375  ++count;
376  }
377  else if (cx < 0 && nx >= 0)
378  {
379  /* current point outside, next point inside */
380 #if DEBUG_DLA
381  printf("(0, %d)\n", ny - nx * (cy - ny) / (cx - nx));
382 #endif
383  success = AppendPoint(&ppl, 0, ny - nx * (cy - ny) / (cx - nx));
384  ++count;
385 #if DEBUG_DLA
386  printf("(%d, %d)\n", nx, ny);
387 #endif
388  success = success && AppendPoint(&ppl, nx, ny);
389  ++count;
390  }
391  else if (cx >= 0 && nx >= 0)
392  {
393 #if DEBUG_DLA
394  printf("(%d, %d)\n", nx, ny);
395 #endif
396  success = AppendPoint(&ppl, nx, ny);
397  ++count;
398  }
399  cp = cp->next;
400  }
401  *ppl = NULL;
402 
403  if (success)
404  {
405  /* Replace old list with new list */
406  FreePointList(polygon->point_list);
407  polygon->point_list = new_list;
408  polygon->num_points = count;
409  }
410  else
411  {
412  /* Free new list */
413  FreePointList(new_list);
414  }
415  }
416  else
417  {
418  /* No need to clip */
419  success = TRUE;
420  }
421 
422  FUNCTION_FINISH(ClipPolygonLeft);
423 
424  return success;
425 }
426 
432 static BOOLEAN ClipPolygonRight(S_POLYGON *polygon)
433 {
434  S_POINT_LIST *cp, *np;
435  S_POINT_LIST *new_list = NULL;
436  S_POINT_LIST **ppl;
437  U16BIT count;
438  U16BIT width;
439  S16BIT cx, cy, nx, ny;
440  BOOLEAN clipped;
441  BOOLEAN success;
442 
443  FUNCTION_START(ClipPolygonRight);
444 
445  width = dla_canvas->width;
446 
447  /* Check whether we need to do anything */
448  cp = polygon->point_list;
449  clipped = FALSE;
450  while (!clipped && cp != NULL)
451  {
452  if (cp->point.x >= width)
453  {
454  clipped = TRUE;
455  }
456  else
457  {
458  cp = cp->next;
459  }
460  }
461 
462  if (clipped)
463  {
464  cp = polygon->point_list;
465  ppl = &new_list;
466  count = 0;
467  success = TRUE;
468  while (success && cp != NULL)
469  {
470  np = cp->next;
471  if (np == NULL)
472  {
473  /* Cycle around */
474  np = polygon->point_list;
475  }
476 
477  cx = cp->point.x;
478  cy = cp->point.y;
479  nx = np->point.x;
480  ny = np->point.y;
481 
482 #if DEBUG_DLA
483  printf("current point: (%d, %d)\n", cx, cy);
484  printf("next point: (%d, %d)\n", nx, ny);
485 #endif
486 
487  if (cx < width && nx >= width)
488  {
489  /* current point inside, next point outside */
490 #if DEBUG_DLA
491  printf("(%d, %d)\n", width,
492  cy + (width - cx) * (cy - ny) / (cx - nx));
493 #endif
494  success = AppendPoint(&ppl, width, cy + (width - cx) * (cy - ny) / (cx - nx));
495  ++count;
496  }
497  else if (cx >= width && nx < width)
498  {
499  /* current point outside, next point inside */
500 #if DEBUG_DLA
501  printf("(%d, %d)\n", width, ny + (width - 1 - nx) * (cy - ny) / (cx - nx));
502 #endif
503  success = AppendPoint(&ppl, width, ny + (width - nx) * (cy - ny) / (cx - nx));
504  ++count;
505 #if DEBUG_DLA
506  printf("(%d, %d)\n", nx, ny);
507 #endif
508  success = success && AppendPoint(&ppl, nx, ny);
509  ++count;
510  }
511  else if (cx < width && nx < width)
512  {
513 #if DEBUG_DLA
514  printf("(%d, %d)\n", nx, ny);
515 #endif
516  success = AppendPoint(&ppl, nx, ny);
517  ++count;
518  }
519  cp = cp->next;
520  }
521  *ppl = NULL;
522 
523  if (success)
524  {
525  /* Replace old list with new list */
526  FreePointList(polygon->point_list);
527  polygon->point_list = new_list;
528  polygon->num_points = count;
529  }
530  else
531  {
532  /* Free new list */
533  FreePointList(new_list);
534  }
535  }
536  else
537  {
538  /* No need to clip */
539  success = TRUE;
540  }
541 
542  FUNCTION_FINISH(ClipPolygonRight);
543 
544  return success;
545 }
546 
552 static BOOLEAN ClipPolygonTop(S_POLYGON *polygon)
553 {
554  S_POINT_LIST *cp, *np;
555  S_POINT_LIST *new_list = NULL;
556  S_POINT_LIST **ppl;
557  U16BIT count;
558  S16BIT cx, cy, nx, ny;
559  BOOLEAN clipped;
560  BOOLEAN success;
561 
562  FUNCTION_START(ClipPolygonTop);
563 
564  /* Check whether we need to do anything */
565  cp = polygon->point_list;
566  clipped = FALSE;
567  while (!clipped && cp != NULL)
568  {
569  if (cp->point.y < 0)
570  {
571  clipped = TRUE;
572  }
573  else
574  {
575  cp = cp->next;
576  }
577  }
578 
579  if (clipped)
580  {
581  cp = polygon->point_list;
582  ppl = &new_list;
583  count = 0;
584  success = TRUE;
585  while (success && cp != NULL)
586  {
587  np = cp->next;
588  if (np == NULL)
589  {
590  /* Cycle around */
591  np = polygon->point_list;
592  }
593 
594  cx = cp->point.x;
595  cy = cp->point.y;
596  nx = np->point.x;
597  ny = np->point.y;
598 
599 #if DEBUG_DLA
600  printf("current point: (%d, %d)\n", cx, cy);
601  printf("next point: (%d, %d)\n", nx, ny);
602 #endif
603 
604  if (cy >= 0 && ny < 0)
605  {
606  /* current point inside, next point outside */
607 #if DEBUG_DLA
608  printf("(%d, 0)\n", cx - cy * (cx - nx) / (cy - ny));
609 #endif
610  success = AppendPoint(&ppl, cx - cy * (cx - nx) / (cy - ny), 0);
611  ++count;
612  }
613  else if (cy < 0 && ny >= 0)
614  {
615  /* current point outside, next point inside */
616 #if DEBUG_DLA
617  printf("(%d, 0)\n", nx - ny * (cx - nx) / (cy - ny));
618 #endif
619  success = AppendPoint(&ppl, nx - ny * (cx - nx) / (cy - ny), 0);
620  ++count;
621 #if DEBUG_DLA
622  printf("(%d, %d)\n", nx, ny);
623 #endif
624  success = success && AppendPoint(&ppl, nx, ny);
625  ++count;
626  }
627  else if (cy >= 0 && ny >= 0)
628  {
629 #if DEBUG_DLA
630  printf("(%d, %d)\n", nx, ny);
631 #endif
632  success = AppendPoint(&ppl, nx, ny);
633  ++count;
634  }
635  cp = cp->next;
636  }
637  *ppl = NULL;
638 
639  if (success)
640  {
641  /* Replace old list with new list */
642  FreePointList(polygon->point_list);
643  polygon->point_list = new_list;
644  polygon->num_points = count;
645  }
646  else
647  {
648  /* Free new list */
649  FreePointList(new_list);
650  }
651  }
652  else
653  {
654  /* No need to clip */
655  success = TRUE;
656  }
657 
658  FUNCTION_FINISH(ClipPolygonTop);
659 
660  return success;
661 }
662 
668 static BOOLEAN ClipPolygonBottom(S_POLYGON *polygon)
669 {
670  S_POINT_LIST *cp, *np;
671  S_POINT_LIST *new_list = NULL;
672  S_POINT_LIST **ppl;
673  U16BIT count;
674  U16BIT height;
675  S16BIT cx, cy, nx, ny;
676  BOOLEAN clipped;
677  BOOLEAN success;
678 
679  FUNCTION_START(ClipPolygonBottom);
680 
681  height = dla_canvas->height;
682 
683  /* Check whether we need to do anything */
684  cp = polygon->point_list;
685  clipped = FALSE;
686  while (!clipped && cp != NULL)
687  {
688  if (cp->point.y >= height)
689  {
690  clipped = TRUE;
691  }
692  else
693  {
694  cp = cp->next;
695  }
696  }
697 
698  if (clipped)
699  {
700  cp = polygon->point_list;
701  ppl = &new_list;
702  count = 0;
703  success = TRUE;
704  while (success && cp != NULL)
705  {
706  np = cp->next;
707  if (np == NULL)
708  {
709  /* Cycle around */
710  np = polygon->point_list;
711  }
712 
713  cx = cp->point.x;
714  cy = cp->point.y;
715  nx = np->point.x;
716  ny = np->point.y;
717 
718 #if DEBUG_DLA
719  printf("current point: (%d, %d)\n", cx, cy);
720  printf("next point: (%d, %d)\n", nx, ny);
721 #endif
722 
723  if (cy < height && ny >= height)
724  {
725  /* current point inside, next point outside */
726 #if DEBUG_DLA
727  printf("(%d, %d)\n",
728  cx + (height - cy) * (cx - nx) / (cy - ny), height);
729 #endif
730  success = AppendPoint(&ppl, cx + (height - cy) * (cx - nx) / (cy - ny), height);
731  ++count;
732  }
733  else if (cy >= height && ny < height)
734  {
735  /* current point outside, next point inside */
736 #if DEBUG_DLA
737  printf("(%d, %d)\n", nx + (height - ny) * (cx - nx) / (cy - ny), height);
738 #endif
739  success = AppendPoint(&ppl, nx + (height - ny) * (cx - nx) / (cy - ny), height);
740  ++count;
741 #if DEBUG_DLA
742  printf("(%d, %d)\n", nx, ny);
743 #endif
744  success = success && AppendPoint(&ppl, nx, ny);
745  ++count;
746  }
747  else if (cy < height && ny < height)
748  {
749 #if DEBUG_DLA
750  printf("(%d, %d)\n", nx, ny);
751 #endif
752  success = AppendPoint(&ppl, nx, ny);
753  ++count;
754  }
755  cp = cp->next;
756  }
757  *ppl = NULL;
758 
759  if (success)
760  {
761  /* Replace old list with new list */
762  FreePointList(polygon->point_list);
763  polygon->point_list = new_list;
764  polygon->num_points = count;
765  }
766  else
767  {
768  /* Free new list */
769  FreePointList(new_list);
770  }
771  }
772  else
773  {
774  /* No need to clip */
775  success = TRUE;
776  }
777 
778  FUNCTION_FINISH(ClipPolygonBottom);
779 
780  return success;
781 }
782 
790 static BOOLEAN ConvertPolygon(S_POINT *points, U16BIT num_points, S_POLYGON *polygon)
791 {
792  U16BIT i;
793  S_POINT_LIST **ppl;
794  BOOLEAN success;
795 
796  FUNCTION_START(ConvertPolygon);
797 
798  success = TRUE;
799  ppl = &polygon->point_list;
800  for (i = 0; success && i < num_points; ++i)
801  {
802  success = AppendPoint(&ppl, points[i].x, points[i].y);
803 #if DEBUG_DLA
804  printf("AppendPoint(%d, %d).rc = %d\n",
805  points[i].x, points[i].y, success);
806 #endif
807  }
808  *ppl = NULL;
809  polygon->num_points = num_points;
810 
811  if (!success)
812  {
813  FreePolygon(polygon);
814  }
815 
816  FUNCTION_FINISH(ConvertPolygon);
817 
818  return success;
819 }
820 
826 static void FreePolygon(S_POLYGON *polygon)
827 {
828  FUNCTION_START(FreePolygon);
829 
830  FreePointList(polygon->point_list);
831  polygon->point_list = NULL;
832  polygon->num_points = 0;
833 
834  FUNCTION_FINISH(FreePolygon);
835 }
836 
842 static void FreePointList(S_POINT_LIST *pl)
843 {
844  S_POINT_LIST *np;
845 
846  FUNCTION_START(FreePointList);
847 
848  while (pl != NULL)
849  {
850  np = pl->next;
851  OSD_MemFree(pl);
852  pl = np;
853  }
854 
855  FUNCTION_FINISH(FreePointList);
856 }
857 
865 static BOOLEAN FillPolygon( S_POLYGON *polygon, DLAColor colour )
866 {
867  BOOLEAN success;
868  U16BIT i;
869  S_POINT_LIST *cp;
870  S_POINT_LIST_HEADER point_list_header;
871 
872  FUNCTION_START(FillPolygon);
873 
874  if ( ClipPolygon(polygon) && polygon->num_points > 0 )
875  {
876  point_list_header.length = polygon->num_points;
877  point_list_header.point_list = OSD_MemAlloc(polygon->num_points *
878  sizeof(S_POINT));
879  if (point_list_header.point_list != NULL)
880  {
881  cp = polygon->point_list;
882  i = 0;
883  while (cp != NULL)
884  {
885 #if DEBUG_DLA
886  printf("(%d,%d)\n", cp->point.x, cp->point.y);
887 #endif
888  point_list_header.point_list[i].x = cp->point.x;
889  point_list_header.point_list[i].y = cp->point.y;
890  cp = cp->next;
891  ++i;
892  }
893 
894  FillConvexPolygon(&point_list_header, colour);
895  OSD_MemFree(point_list_header.point_list);
896  }
897 
898  success = TRUE;
899  }
900  else
901  {
902  success = FALSE;
903 #if DEBUG_DLA
904  printf("ClipPolygon failed\n");
905 #endif
906  }
907 
908  FUNCTION_FINISH(FillPolygon);
909 
910  return success;
911 }
912 
922 static void FillSimpleRectangle(S16BIT x1, S16BIT y1, S16BIT x2, S16BIT y2, DLAColor colour)
923 {
924  S16BIT i, stride;
925  DLAColor *sp;
926 
927  FUNCTION_START(FillSimpleRectangle);
928 
929  if ( x1 < 0 ) x1 = 0;
930  if ( x2 > dla_canvas->width ) x2 = dla_canvas->width;
931  if ( y1 < 0 ) y1 = 0;
932  if ( y2 > dla_canvas->height ) y2 = dla_canvas->height;
933 
934  if (x2 > x1 && y2 > y1)
935  {
936  stride = dla_canvas->bf_stride / sizeof(DLAColor);
937  sp = dla_canvas->cols + (y1 * stride) + x1;
938  x2 -= x1; /* x2 becomes width */
939  for (i = y1; i != y2; ++i)
940  {
941  DLA_MEMSET( sp, colour, x2 );
942  sp += stride;
943  }
944  }
945 
946  FUNCTION_FINISH(FillSimpleRectangle);
947 }
948 
959 static void DrawLine(S16BIT x1, S16BIT y1, S16BIT x2, S16BIT y2, U16BIT width, DLAColor colour)
960 {
961  FUNCTION_START(DrawLine);
962 
963 #if DEBUG_DLA
964  printf("DrawLine(%d, %d, %d, %d, %d)\n", x1, y1, x2, y2, width);
965 #endif
966 
967  if (width == 1)
968  {
969  if ((x1 < 0 && x2 < 0) ||
970  (y1 < 0 && y2 < 0) ||
971  (x1 >= dla_canvas->width && x2 >= dla_canvas->width) ||
972  (y1 >= dla_canvas->height && y2 >= dla_canvas->height))
973  {
974  /* Trivially clipped out */
975  }
976  else if (x1 == x2)
977  {
978  /* Quick clipping */
979  y1 = y1 < 0 ? 0 : y1;
980  y2 = y2 < 0 ? 0 : y2;
981  y1 = y1 >= dla_canvas->height ? dla_canvas->height-1 : y1;
982  y2 = y2 >= dla_canvas->height ? dla_canvas->height-1 : y2;
983  DrawThinLine(x1, y1, x2, y2, colour);
984  }
985  else if (y1 == y2)
986  {
987  /* Quick clipping */
988  x1 = x1 < 0 ? 0 : x1;
989  x2 = x2 < 0 ? 0 : x2;
990  x1 = x1 >= dla_canvas->width ? dla_canvas->width-1 : x1;
991  x2 = x2 >= dla_canvas->width ? dla_canvas->width-1 : x2;
992  DrawThinLine(x1, y1, x2, y2, colour);
993  }
994  else if (ClipLine(&x1, &y1, &x2, &y2))
995  {
996  DrawThinLine(x1, y1, x2, y2, colour);
997  }
998  }
999  else if (width > 1)
1000  {
1001  U16BIT wl = width / 2, ws = (width + 1) / 2;
1002  /* Width > 1 */
1003  if ((x1 + ws <= 0 && x2 + ws <= 0) ||
1004  (y1 + ws <= 0 && y2 + ws <= 0) ||
1005  (x1 - wl >= dla_canvas->width && x2 - wl >= dla_canvas->width) ||
1006  (y1 - wl >= dla_canvas->height && y2 - wl >= dla_canvas->height))
1007  {
1008  /* Trivially clipped out */
1009  }
1010  #ifdef SIMPLE_LINES_AS_RECTANGLES
1011  else if (x1 == x2)
1012  {
1013  /* Draw rectangle */
1014  if (y1 < y2)
1015  {
1016  FillSimpleRectangle(x1 - wl, y1, x1 + ws, y2, colour);
1017  }
1018  else
1019  {
1020  FillSimpleRectangle(x1 - wl, y2, x1 + ws, y1, colour);
1021  }
1022 
1023  /* Draw line ends */
1024  FillCircle(x1, y1, ws+wl, colour);
1025  FillCircle(x2, y2, ws+wl, colour);
1026  }
1027  else if (y1 == y2)
1028  {
1029  /* Draw rectangle */
1030  if (x1 < x2)
1031  {
1032  FillSimpleRectangle(x1, y1 - wl, x2, y1 + ws, colour);
1033  }
1034  else
1035  {
1036  FillSimpleRectangle(x2, y1 - wl, x1, y1 + ws, colour);
1037  }
1038 
1039  /* Draw line ends */
1040  FillCircle(x1, y1, ws+wl, colour);
1041  FillCircle(x2, y2, ws+wl, colour);
1042  }
1043  #endif /* SIMPLE_LINES_AS_RECTANGLES */
1044  else
1045  {
1046  DrawFatLine(x1, y1, x2, y2, ws+wl, colour);
1047  }
1048  }
1049 
1050  FUNCTION_FINISH(DrawLine);
1051 }
1052 
1062 static void DrawThinLine(S16BIT x1, S16BIT y1, S16BIT x2, S16BIT y2, DLAColor colour)
1063 {
1064  S32BIT delta_x;
1065  S32BIT delta_y;
1066  S32BIT error;
1067  S32BIT y_step;
1068  S32BIT x, y;
1069  BOOLEAN steep;
1070 
1071  FUNCTION_START(DrawLine);
1072 
1073  /* Check if line is "steep" (closer to Y-axis in slope) */
1074  if (ABS(y2-y1) > ABS(x2-x1))
1075  {
1076  /* Swap (x1,y1) with (y1,x1) and (x2,y2) with (y2,x2) */
1077  Swap(&x1, &y1);
1078  Swap(&x2, &y2);
1079  steep = TRUE;
1080  }
1081  else
1082  {
1083  steep = FALSE;
1084  }
1085 
1086  if (x1 > x2)
1087  {
1088  /* Swap (x1,y1) with (x2,y2) and (x2,y2) with (x1,y1) */
1089  Swap(&x1, &x2);
1090  Swap(&y1, &y2);
1091  }
1092 
1093  delta_x = x2 - x1;
1094  delta_y = ABS(y2 - y1);
1095  error = 0;
1096  y = y1;
1097  if (y1 < y2)
1098  {
1099  y_step = 1;
1100  }
1101  else
1102  {
1103  y_step = -1;
1104  }
1105 
1106 
1107  if (steep)
1108  {
1109  for (x = x1; x <= x2; ++x)
1110  {
1111  /* plot(y,x) */
1112  assert(x>=0 && x<dla_canvas->height);
1113  assert(y>=0 && y<dla_canvas->width);
1114  PutPixel(y, x, colour);
1115 
1116  error = error + delta_y;
1117  if (error * 2 >= delta_x)
1118  {
1119  y += y_step;
1120  error -= delta_x;
1121  }
1122  }
1123  }
1124  else
1125  {
1126  for (x = x1; x <= x2; ++x)
1127  {
1128  /* plot(x,y) */
1129  assert(x>=0 && x<dla_canvas->width);
1130  assert(y>=0 && y<dla_canvas->height);
1131  PutPixel(x, y, colour);
1132  error = error + delta_y;
1133  if (error * 2 >= delta_x)
1134  {
1135  y += y_step;
1136  error -= delta_x;
1137  }
1138  }
1139  }
1140 
1141  FUNCTION_FINISH(DrawLine);
1142 }
1143 
1154 static void DrawFatLine(S16BIT x1, S16BIT y1, S16BIT x2, S16BIT y2, U16BIT width, DLAColor colour)
1155 {
1156 #if 0
1157  S_POLYGON polygon;
1158  S_POINT corner[4];
1159  S32BIT dx, dy;
1160  U32BIT adx, ady;
1161  U32BIT d;
1162  U16BIT a, b;
1163 
1164  FUNCTION_START(DrawFatLine);
1165 
1166  dx = x2 - x1;
1167  dy = y2 - y1;
1168  adx = ABS(dx);
1169  ady = ABS(dy);
1170 
1171  /* Approximate distance between points */
1172  if (adx < ady)
1173  {
1174  d = 41*adx + 94*ady;
1175  }
1176  else
1177  {
1178  d = 41*ady + 94*adx;
1179  }
1180 
1181  /* a is the x-component of width */
1182  a = (width * ady * 100 + d) / (2*d);
1183  /* b is the y-component of width */
1184  b = (width * adx * 100 + d) / (2*d);
1185 
1186  /* Find 4 corners of "fat line" */
1187  if (dx * dy > 0)
1188  {
1189  corner[0].x = x1 + a;
1190  corner[0].y = y1 - b;
1191  corner[1].x = x1 - a;
1192  corner[1].y = y1 + b;
1193  corner[2].x = x2 - a;
1194  corner[2].y = y2 + b;
1195  corner[3].x = x2 + a;
1196  corner[3].y = y2 - b;
1197  }
1198  else
1199  {
1200  corner[0].x = x1 - a;
1201  corner[0].y = y1 - b;
1202  corner[1].x = x1 + a;
1203  corner[1].y = y1 + b;
1204  corner[2].x = x2 + a;
1205  corner[2].y = y2 + b;
1206  corner[3].x = x2 - a;
1207  corner[3].y = y2 - b;
1208  }
1209 
1210  /* Draw fat line as a filled polygon */
1211  if ( ConvertPolygon(corner, 4, &polygon)
1212  && FillPolygon(&polygon, colour) )
1213  {
1214  FreePolygon(&polygon);
1215  }
1216 
1217  /* Draw line ends (note that the polygon algorithm is slightly skewed) */
1218  FillCircle(x1 + 1, y1 + 1, width, colour);
1219  FillCircle(x2 + 1, y2 + 1, width, colour);
1220 
1221  FUNCTION_FINISH(DrawFatLine);
1222 #else
1223  S32BIT delta_x;
1224  S32BIT delta_y;
1225  S32BIT error;
1226  S32BIT y_step;
1227  S32BIT x, y;
1228  BOOLEAN steep;
1229 
1230  FUNCTION_START(DrawLine);
1231 
1232  /* Check if line is "steep" (closer to Y-axis in slope) */
1233  if (ABS(y2-y1) > ABS(x2-x1))
1234  {
1235  /* Swap (x1,y1) with (y1,x1) and (x2,y2) with (y2,x2) */
1236  Swap(&x1, &y1);
1237  Swap(&x2, &y2);
1238  steep = TRUE;
1239  }
1240  else
1241  {
1242  steep = FALSE;
1243  }
1244 
1245  if (x1 > x2)
1246  {
1247  /* Swap (x1,y1) with (x2,y2) and (x2,y2) with (x1,y1) */
1248  Swap(&x1, &x2);
1249  Swap(&y1, &y2);
1250  }
1251 
1252  delta_x = x2 - x1;
1253  delta_y = ABS(y2 - y1);
1254  error = 0;
1255  y = y1;
1256  if (y1 < y2)
1257  {
1258  y_step = 1;
1259  }
1260  else
1261  {
1262  y_step = -1;
1263  }
1264 
1265 
1266  if (steep)
1267  {
1268  for (x = x1; x <= x2; ++x)
1269  {
1270  /* plot(y,x) */
1271  FillCircle(y, x, width, colour);
1272  error = error + delta_y;
1273  if (error * 2 >= delta_x)
1274  {
1275  y += y_step;
1276  error -= delta_x;
1277  }
1278  }
1279  }
1280  else
1281  {
1282  for (x = x1; x <= x2; ++x)
1283  {
1284  /* plot(x,y) */
1285  FillCircle(x, y, width, colour);
1286  error = error + delta_y;
1287  if (error * 2 >= delta_x)
1288  {
1289  y += y_step;
1290  error -= delta_x;
1291  }
1292  }
1293  }
1294 
1295  FUNCTION_FINISH(DrawLine);
1296 #endif
1297 }
1298 
1305 static void DrawHorizontalLineList(S_HLINE_LIST *hline_list, DLAColor colour)
1306 {
1307  S_HLINE *hline;
1308  U16BIT length, stride;
1309  S32BIT width;
1310  DLAColor *ScreenPtr;
1311 
1312  stride = dla_canvas->bf_stride / sizeof(DLAColor);
1313 
1314  /* Point to the start of the first scan line on which to draw */
1315  ScreenPtr = dla_canvas->cols + hline_list->y_start * stride;
1316 
1317  /* Point to the x_start/x_end descriptor for the first (top)
1318  horizontal line */
1319  hline = hline_list->hline;
1320  /* Draw each horizontal line in turn, starting with the top one and
1321  advancing one line each time */
1322  length = hline_list->length;
1323  while (length-- > 0) {
1324  /* Draw the whole horizontal line if it has a positive width */
1325  width = hline->x_end - hline->x_start + 1; /*<-AMS: THIS IS HOW IT WAS - I THINK IT SHOULD OMIT THE '+1'*/
1326  if (width > 0)
1327  {
1328 #if DEBUG_DLA
1329  printf("line from %d of %d\n", hline->x_start, Width);
1330 #endif
1331  assert (hline->x_end < dla_canvas->width);
1332  DLA_MEMSET( ScreenPtr + hline->x_start, colour, width );
1333  }
1334  ScreenPtr += stride; /* point to next scan line start */
1335  hline++; /* point to next scan line X info */
1336  }
1337 }
1338 
1348 static void FillEllipse(S16BIT x, S16BIT y, U16BIT w, U16BIT h, DLAColor colour)
1349 {
1350  S32BIT cx, cy, rx, ry, px, py;
1351  S32BIT x_change, y_change;
1352  S32BIT error;
1353  S32BIT two_a2, two_b2;
1354  S32BIT stop_x, stop_y;
1355  S32BIT f, t, stride;
1356  S32BIT xadj, yadj;
1357  DLAColor *spb, *spt;
1358 
1359  FUNCTION_START(FillEllipse);
1360 
1361  stride = dla_canvas->bf_stride / sizeof(DLAColor);
1362 
1363  /* Calculate radii and centre */
1364  rx = (w+1)/2-1;
1365  ry = (h+1)/2-1;
1366  cx = x + rx;
1367  cy = y + ry;
1368 
1369  /* Calculate adjustment for even width / height */
1370  xadj = 1 - (w % 2);
1371  yadj = 1 - (h % 2);
1372 
1373  /* Calculate 2a^2 and 2b^2 */
1374  two_a2 = 2 * rx * rx;
1375  two_b2 = 2 * ry * ry;
1376 
1377  /* Start first stage: in this stage the y value is changing faster than
1378  * the x value, so y changes at every iteration and x is only corrected
1379  * when required.
1380  */
1381  px = rx;
1382  py = 0;
1383  x_change = ry * ry * (1 - 2 * rx);
1384  y_change = rx * rx;
1385  error = 0;
1386  stop_x = two_b2 * rx;
1387  stop_y = 0;
1388 
1389  spt = dla_canvas->cols + cy * stride;
1390  spb = spt + yadj * stride;
1391 
1392  while (stop_x >= stop_y)
1393  {
1394  /* Fill the ellipse */
1395  f = cx - px;
1396  f = f < 0 ? 0 : f;
1397  t = cx + px + 1 + xadj;
1398  t = t >= dla_canvas->width ? dla_canvas->width : t;
1399  if (t > f)
1400  {
1401  t -= f;
1402  if (cy - py >= 0 && cy - py < dla_canvas->height)
1403  {
1404  DLA_MEMSET( spt + f, colour, t );
1405  }
1406  if (cy + py + yadj >= 0 && cy + py + yadj < dla_canvas->height)
1407  {
1408  DLA_MEMSET( spb + f, colour, t );
1409  }
1410  }
1411 
1412  ++py;
1413  spt -= stride;
1414  spb += stride;
1415  stop_y += two_a2;
1416  error += y_change;
1417  y_change += two_a2;
1418  if (2*error + x_change > 0)
1419  {
1420  --px;
1421  stop_x -= two_b2;
1422  error += x_change;
1423  x_change += two_b2;
1424  }
1425  }
1426 
1427  /* Start second stage: in this stage the x value is changing faster than
1428  * the y value, so x changes at every iteration and y is only corrected
1429  * when required.
1430  */
1431  px = 0;
1432  py = ry;
1433  x_change = ry * ry;
1434  y_change = rx * rx * (1 - 2 * ry);
1435  error = 0;
1436  stop_x = 0;
1437  stop_y = two_a2 * ry;;
1438 
1439  spt = dla_canvas->cols + (cy-py) * stride;
1440  spb = dla_canvas->cols + (cy+py+yadj) * stride;
1441 
1442  while (stop_x <= stop_y)
1443  {
1444  ++px;
1445  stop_x += two_b2;
1446  error += x_change;
1447  x_change += two_b2;
1448  if (2 * error + y_change > 0)
1449  {
1450  /* Fill the ellipse */
1451  f = cx - px + 1;
1452  f = f < 0 ? 0 : f;
1453  t = cx + px + xadj;
1454  t = t >= dla_canvas->width ? dla_canvas->width : t;
1455  if (t > f)
1456  {
1457  t -= f;
1458  if (cy - py >= 0 && cy - py < dla_canvas->height)
1459  {
1460  DLA_MEMSET( spt + f, colour, t );
1461  }
1462  if (cy + py + yadj >= 0 && cy + py + yadj < dla_canvas->height)
1463  {
1464  DLA_MEMSET( spb + f, colour, t );
1465  }
1466  }
1467 
1468  --py;
1469  spt += stride;
1470  spb -= stride;
1471  stop_y -= two_a2;
1472  error += y_change;
1473  y_change += two_a2;
1474  }
1475  }
1476 
1477  FUNCTION_FINISH(FillEllipse);
1478 }
1479 
1490 static void DrawEllipse(S16BIT x, S16BIT y, U16BIT w, U16BIT h, U16BIT width, DLAColor colour)
1491 {
1492  S32BIT cx, cy, rx, ry, px, py;
1493  S32BIT x_change, y_change;
1494  S32BIT error;
1495  S32BIT two_a2, two_b2;
1496  S32BIT stop_x, stop_y;
1497  S32BIT xadj, yadj;
1498 
1499  FUNCTION_START(DrawEllipse);
1500 
1501  /* Calculate radii and centre */
1502  rx = (w+1)/2-1;
1503  ry = (h+1)/2-1;
1504  cx = x + rx;
1505  cy = y + ry;
1506 
1507  /* Calculate adjustment for even width / height */
1508  xadj = 1 - (w % 2);
1509  yadj = 1 - (h % 2);
1510 
1511  /* Calculate 2a^2 and 2b^2 */
1512  two_a2 = 2 * rx * rx;
1513  two_b2 = 2 * ry * ry;
1514 
1515  /* Start first stage: in this stage the y value is changing faster than
1516  * the x value, so y changes at every iteration and x is only corrected
1517  * when required.
1518  */
1519  px = rx;
1520  py = 0;
1521  x_change = ry * ry * (1 - 2 * rx);
1522  y_change = rx * rx;
1523  error = 0;
1524  stop_x = two_b2 * rx;
1525  stop_y = 0;
1526 
1527  while (stop_x >= stop_y)
1528  {
1529  if (width == 1)
1530  {
1531  PutPixel(cx+px+xadj, cy+py+yadj, colour);
1532  PutPixel(cx-px, cy+py+yadj, colour);
1533  PutPixel(cx-px, cy-py, colour);
1534  PutPixel(cx+px+xadj, cy-py, colour);
1535  }
1536  else
1537  {
1538  FillCircle(cx+px+xadj, cy+py+yadj, width, colour);
1539  FillCircle(cx-px, cy+py+yadj, width, colour);
1540  FillCircle(cx-px, cy-py, width, colour);
1541  FillCircle(cx+px+xadj, cy-py, width, colour);
1542  }
1543 
1544  ++py;
1545  stop_y += two_a2;
1546  error += y_change;
1547  y_change += two_a2;
1548  if (2*error + x_change > 0)
1549  {
1550  --px;
1551  stop_x -= two_b2;
1552  error += x_change;
1553  x_change += two_b2;
1554  }
1555  }
1556 
1557  /* Start second stage: in this stage the x value is changing faster than
1558  * the y value, so x changes at every iteration and y is only corrected
1559  * when required.
1560  */
1561  px = 0;
1562  py = ry;
1563  x_change = ry * ry;
1564  y_change = rx * rx * (1 - 2 * ry);
1565  error = 0;
1566  stop_x = 0;
1567  stop_y = two_a2 * ry;;
1568 
1569  while (stop_x <= stop_y)
1570  {
1571  if (width == 1)
1572  {
1573  PutPixel(cx+px+xadj, cy+py+yadj, colour);
1574  PutPixel(cx-px, cy+py+yadj, colour);
1575  PutPixel(cx-px, cy-py, colour);
1576  PutPixel(cx+px+xadj, cy-py, colour);
1577  }
1578  else
1579  {
1580  FillCircle(cx+px+xadj, cy+py+yadj, width, colour);
1581  FillCircle(cx-px, cy+py+yadj, width, colour);
1582  FillCircle(cx-px, cy-py, width, colour);
1583  FillCircle(cx+px+xadj, cy-py, width, colour);
1584  }
1585 
1586  ++px;
1587  stop_x += two_b2;
1588  error += x_change;
1589  x_change += two_b2;
1590  if (2 * error + y_change > 0)
1591  {
1592  --py;
1593  stop_y -= two_a2;
1594  error += y_change;
1595  y_change += two_a2;
1596  }
1597  }
1598 
1599  FUNCTION_FINISH(DrawEllipse);
1600 }
1601 
1614 static void DrawArc(S16BIT x, S16BIT y, U16BIT w, U16BIT h, U16BIT start, U16BIT arc, U16BIT width, DLAColor colour)
1615 {
1616  S32BIT cx, cy, rx, ry;
1617  S32BIT px1, px2;
1618  S32BIT py1, py2;
1619  S32BIT hsx, hsy, hex, hey;
1620  S_64_BIT x_change, y_change;
1621  S_64_BIT error;
1622  S32BIT two_a2, two_b2;
1623  S_64_BIT stop_x, stop_y;
1624  S32BIT xadj, yadj;
1625  U16BIT end;
1626  U16BIT qs, qe, i;
1627  S_64_BIT temp_check, zero;
1628 
1629  /* Quadrant type */
1630  enum
1631  {
1632  QUADRANT_FULL,
1633  QUADRANT_EMPTY,
1634  QUADRANT_START,
1635  QUADRANT_END,
1636  QUADRANT_START_BEFORE_END,
1637  QUADRANT_END_BEFORE_START
1638  } quadrant_type[4];
1639 
1640  FUNCTION_START(DrawArc);
1641 
1642  /* Calculate radii and centre */
1643  rx = (w+1)/2-1;
1644  ry = (h+1)/2-1;
1645  cx = x + rx;
1646  cy = y + ry;
1647 
1648  /* Calculate adjustment for even width / height */
1649  xadj = 1 - (w % 2);
1650  yadj = 1 - (h % 2);
1651 
1652  /* Calculate 'hit points' for start and end angle */
1653  end = start + arc - 1;
1654  if (end > 23040)
1655  {
1656  end -= 23040;
1657  }
1658 
1659  GetHitPoints(rx, ry, start, &hsx, &hsy);
1660  GetHitPoints(rx, ry, end, &hex, &hey);
1661 
1662  hsx += cx + xadj * (hsx > 0);
1663  hex += cx + xadj * (hex > 0);
1664  hsy += cy + yadj * (hsy > 0);
1665  hey += cy + yadj * (hey > 0);
1666 
1667  /* Find quadrant types */
1668  qs = start / 5760;
1669  qe = end / 5760;
1670 
1671  for (i = 0; i < 4; ++i)
1672  {
1673  quadrant_type[i] = QUADRANT_EMPTY;
1674  }
1675  if (qs < qe)
1676  {
1677  for (i = qs + 1; i < qe; ++i)
1678  {
1679  quadrant_type[i] = QUADRANT_FULL;
1680  }
1681  quadrant_type[qs] = QUADRANT_START;
1682  quadrant_type[qe] = QUADRANT_END;
1683  }
1684  else if (qs > qe)
1685  {
1686  for (i = qs + 1; i < qe + 4; ++i)
1687  {
1688  quadrant_type[i%4] = QUADRANT_FULL;
1689  }
1690  quadrant_type[qs] = QUADRANT_START;
1691  quadrant_type[qe] = QUADRANT_END;
1692  }
1693  else
1694  {
1695  if (start < end)
1696  {
1697  quadrant_type[qs] = QUADRANT_START_BEFORE_END;
1698  }
1699  else
1700  {
1701  for (i = qs + 1; i < qe + 4; ++i)
1702  {
1703  quadrant_type[i%4] = QUADRANT_FULL;
1704  }
1705  quadrant_type[qs] = QUADRANT_END_BEFORE_START;
1706  }
1707  }
1708 
1709 #if DEBUG_DLA
1710  printf("quadrants: %s %s %s %s\n",
1711  quadrant_type[0] == QUADRANT_FULL ? "QUADRANT_FULL" :
1712  quadrant_type[0] == QUADRANT_EMPTY ? "QUADRANT_EMPTY" :
1713  quadrant_type[0] == QUADRANT_START ? "QUADRANT_START" :
1714  quadrant_type[0] == QUADRANT_END ? "QUADRANT_END" :
1715  quadrant_type[0] == QUADRANT_START_BEFORE_END ? "QUADRANT_START_BEFORE_END" :
1716  quadrant_type[0] == QUADRANT_END_BEFORE_START ? "QUADRANT_END_BEFORE_START" : "UNKNOWN",
1717  quadrant_type[1] == QUADRANT_FULL ? "QUADRANT_FULL" :
1718  quadrant_type[1] == QUADRANT_EMPTY ? "QUADRANT_EMPTY" :
1719  quadrant_type[1] == QUADRANT_START ? "QUADRANT_START" :
1720  quadrant_type[1] == QUADRANT_END ? "QUADRANT_END" :
1721  quadrant_type[1] == QUADRANT_START_BEFORE_END ? "QUADRANT_START_BEFORE_END" :
1722  quadrant_type[1] == QUADRANT_END_BEFORE_START ? "QUADRANT_END_BEFORE_START" : "UNKNOWN",
1723  quadrant_type[2] == QUADRANT_FULL ? "QUADRANT_FULL" :
1724  quadrant_type[2] == QUADRANT_EMPTY ? "QUADRANT_EMPTY" :
1725  quadrant_type[2] == QUADRANT_START ? "QUADRANT_START" :
1726  quadrant_type[2] == QUADRANT_END ? "QUADRANT_END" :
1727  quadrant_type[2] == QUADRANT_START_BEFORE_END ? "QUADRANT_START_BEFORE_END" :
1728  quadrant_type[2] == QUADRANT_END_BEFORE_START ? "QUADRANT_END_BEFORE_START" : "UNKNOWN",
1729  quadrant_type[3] == QUADRANT_FULL ? "QUADRANT_FULL" :
1730  quadrant_type[3] == QUADRANT_EMPTY ? "QUADRANT_EMPTY" :
1731  quadrant_type[3] == QUADRANT_START ? "QUADRANT_START" :
1732  quadrant_type[3] == QUADRANT_END ? "QUADRANT_END" :
1733  quadrant_type[3] == QUADRANT_START_BEFORE_END ? "QUADRANT_START_BEFORE_END" :
1734  quadrant_type[3] == QUADRANT_END_BEFORE_START ? "QUADRANT_END_BEFORE_START" : "UNKNOWN");
1735 #endif
1736 
1737  /* Calculate 2a^2 and 2b^2 */
1738  two_a2 = 2 * rx * rx;
1739  two_b2 = 2 * ry * ry;
1740 
1741  /* Start first stage: in this stage the y value is changing faster than
1742  * the x value, so y changes at every iteration and x is only corrected
1743  * when required.
1744  */
1745  px1 = cx+rx+xadj;
1746  px2 = cx-rx;
1747  py1 = cy+yadj;
1748  py2 = cy;
1749  /* x_change = ry * ry * (1 - 2 * rx); */
1750  S64AssignS32(&x_change, ry);
1751  S64MultiplyS32(&x_change, ry);
1752  S64MultiplyS32(&x_change, 1 - 2 * rx);
1753 
1754  /* y_change = rx * rx; */
1755  S64AssignS32(&y_change, rx);
1756  S64MultiplyS32(&y_change, rx);
1757 
1758  /* stop_x = two_b2 * rx; */
1759  S64AssignS32(&stop_x, two_b2);
1760  S64MultiplyS32(&stop_x, rx);
1761 
1762  /* stop_y = 0; */
1763  S64AssignS32(&stop_y, 0);
1764 
1765  /* error = 0; */
1766  S64AssignS32(&error, 0);
1767 
1768  /* while (stop_x >= stop_y) */
1769  while (S64CompareS64(&stop_x, &stop_y) >= 0)
1770  {
1771  if ((quadrant_type[0] == QUADRANT_FULL) ||
1772  (quadrant_type[0] == QUADRANT_START && py2 <= hsy) ||
1773  (quadrant_type[0] == QUADRANT_END && py2 >= hey) ||
1774  (quadrant_type[0] == QUADRANT_START_BEFORE_END && (py2 <= hsy && py2 >= hey)) ||
1775  (quadrant_type[0] == QUADRANT_END_BEFORE_START && (py2 <= hsy || py2 >= hey)))
1776  {
1777  if (width == 1)
1778  {
1779  PutPixel(px1, py2, colour);
1780  }
1781  else if (width > 1)
1782  {
1783  FillCircle(px1, py2, width, colour);
1784  }
1785  }
1786  if ((quadrant_type[1] == QUADRANT_FULL) ||
1787  (quadrant_type[1] == QUADRANT_START && py2 >= hsy) ||
1788  (quadrant_type[1] == QUADRANT_END && py2 <= hey) ||
1789  (quadrant_type[1] == QUADRANT_START_BEFORE_END && (py2 >= hsy && py2 <= hey)) ||
1790  (quadrant_type[1] == QUADRANT_END_BEFORE_START && (py2 >= hsy || py2 <= hey)))
1791  {
1792  if (width == 1)
1793  {
1794  PutPixel(px2, py2, colour);
1795  }
1796  else if (width > 1)
1797  {
1798  FillCircle(px2, py2, width, colour);
1799  }
1800  }
1801  if ((quadrant_type[2] == QUADRANT_FULL) ||
1802  (quadrant_type[2] == QUADRANT_START && py1 >= hsy) ||
1803  (quadrant_type[2] == QUADRANT_END && py1 <= hey) ||
1804  (quadrant_type[2] == QUADRANT_START_BEFORE_END && (py1 >= hsy && py1 <= hey)) ||
1805  (quadrant_type[2] == QUADRANT_END_BEFORE_START && (py1 >= hsy || py1 <= hey)))
1806  {
1807  if (width == 1)
1808  {
1809  PutPixel(px2, py1, colour);
1810  }
1811  else if (width > 1)
1812  {
1813  FillCircle(px2, py1, width, colour);
1814  }
1815  }
1816  if ((quadrant_type[3] == QUADRANT_FULL) ||
1817  (quadrant_type[3] == QUADRANT_START && py1 <= hsy) ||
1818  (quadrant_type[3] == QUADRANT_END && py1 >= hey) ||
1819  (quadrant_type[3] == QUADRANT_START_BEFORE_END && (py1 <= hsy && py1 >= hey)) ||
1820  (quadrant_type[3] == QUADRANT_END_BEFORE_START && (py1 <= hsy || py1 >= hey)))
1821  {
1822  if (width == 1)
1823  {
1824  PutPixel(px1, py1, colour);
1825  }
1826  else if (width > 1)
1827  {
1828  FillCircle(px1, py1, width, colour);
1829  }
1830  }
1831 
1832  ++py1;
1833  --py2;
1834 
1835  /* stop_y += two_a2; */
1836  S64AddS32(&stop_y, two_a2);
1837 
1838  /* error += y_change; */
1839  S64AddS64(&error, &y_change);
1840 
1841  /* y_change += two_a2; */
1842  S64AddS32(&y_change, two_a2);
1843 
1844  /* if (2*error + x_change > 0) */
1845  S64AssignS32(&zero, 0);
1846  S64AssignS32(&temp_check, 0);
1847  S64AddS64(&temp_check, &error);
1848  S64AddS64(&temp_check, &error);
1849  S64AddS64(&temp_check, &x_change);
1850 
1851  if (S64CompareS64(&temp_check, &zero) > 0)
1852  {
1853  ++px2;
1854  --px1;
1855 
1856  /* stop_x -= two_b2; */
1857  S64SubtractS32(&stop_x, two_b2);
1858 
1859  /* error += x_change; */
1860  S64AddS64(&error, &x_change);
1861 
1862  /* x_change += two_b2; */
1863  S64AddS32(&x_change, two_b2);
1864  }
1865  }
1866 
1867  /* Start second stage: in this stage the x value is changing faster than
1868  * the y value, so x changes at every iteration and y is only corrected
1869  * when required.
1870  */
1871  px1 = cx+xadj;
1872  px2 = cx;
1873  py1 = cy+ry+yadj;
1874  py2 = cy-ry;
1875 
1876  /* x_change = ry * ry; */
1877  S64AssignS32(&x_change, ry);
1878  S64MultiplyS32(&x_change, ry);
1879 
1880  /* y_change = rx * rx * (1 - 2 * ry); */
1881  S64AssignS32(&y_change, rx);
1882  S64MultiplyS32(&y_change, rx);
1883  S64MultiplyS32(&y_change, 1 - 2 * ry);
1884 
1885  /* stop_x = 0; */
1886  S64AssignS32(&stop_x, 0);
1887 
1888  /* stop_y = two_a2 * ry; */
1889  S64AssignS32(&stop_y, two_a2);
1890  S64MultiplyS32(&stop_y, ry);
1891 
1892  /* error = 0; */
1893  S64AssignS32(&error, 0);
1894 
1895  /* while (stop_x <= stop_y) */
1896  while (S64CompareS64(&stop_x, &stop_y) <= 0)
1897  {
1898  if ((quadrant_type[0] == QUADRANT_FULL) ||
1899  (quadrant_type[0] == QUADRANT_START && px1 <= hsx) ||
1900  (quadrant_type[0] == QUADRANT_END && px1 >= hex) ||
1901  (quadrant_type[0] == QUADRANT_START_BEFORE_END && (px1 <= hsx && px1 >= hex)) ||
1902  (quadrant_type[0] == QUADRANT_END_BEFORE_START && (px1 <= hsx || px1 >= hex)))
1903  {
1904  if (width == 1)
1905  {
1906  PutPixel(px1, py2, colour);
1907  }
1908  else if (width > 1)
1909  {
1910  FillCircle(px1, py2, width, colour);
1911  }
1912  }
1913  if ((quadrant_type[1] == QUADRANT_FULL) ||
1914  (quadrant_type[1] == QUADRANT_START && px2 <= hsx) ||
1915  (quadrant_type[1] == QUADRANT_END && px2 >= hex) ||
1916  (quadrant_type[1] == QUADRANT_START_BEFORE_END && (px2 <= hsx && px2 >= hex)) ||
1917  (quadrant_type[1] == QUADRANT_END_BEFORE_START && (px2 <= hsx || px2 >= hex)))
1918  {
1919  if (width == 1)
1920  {
1921  PutPixel(px2, py2, colour);
1922  }
1923  else if (width > 1)
1924  {
1925  FillCircle(px2, py2, width, colour);
1926  }
1927  }
1928  if ((quadrant_type[2] == QUADRANT_FULL) ||
1929  (quadrant_type[2] == QUADRANT_START && px2 >= hsx) ||
1930  (quadrant_type[2] == QUADRANT_END && px2 <= hex) ||
1931  (quadrant_type[2] == QUADRANT_START_BEFORE_END && (px2 >= hsx && px2 <= hex)) ||
1932  (quadrant_type[2] == QUADRANT_END_BEFORE_START && (px2 >= hsx || px2 <= hex)))
1933  {
1934  if (width == 1)
1935  {
1936  PutPixel(px2, py1, colour);
1937  }
1938  else if (width > 1)
1939  {
1940  FillCircle(px2, py1, width, colour);
1941  }
1942  }
1943  if ((quadrant_type[3] == QUADRANT_FULL) ||
1944  (quadrant_type[3] == QUADRANT_START && px1 >= hsx) ||
1945  (quadrant_type[3] == QUADRANT_END && px1 <= hex) ||
1946  (quadrant_type[3] == QUADRANT_START_BEFORE_END && (px1 >= hsx && px1 <= hex)) ||
1947  (quadrant_type[3] == QUADRANT_END_BEFORE_START && (px1 >= hsx || px1 <= hex)))
1948  {
1949  if (width == 1)
1950  {
1951  PutPixel(px1, py1, colour);
1952  }
1953  else if (width > 1)
1954  {
1955  FillCircle(px1, py1, width, colour);
1956  }
1957  }
1958 
1959  ++px1;
1960  --px2;
1961 
1962  /* stop_x += two_b2; */
1963  S64AddS32(&stop_x, two_b2);
1964 
1965  /* error += x_change; */
1966  S64AddS64(&error, &x_change);
1967 
1968  /* x_change += two_b2; */
1969  S64AddS32(&x_change, two_b2);
1970 
1971  /* if (2 * error + y_change > 0) */
1972  S64AssignS32(&zero, 0);
1973  S64AssignS32(&temp_check, 0);
1974  S64AddS64(&temp_check, &error);
1975  S64AddS64(&temp_check, &error);
1976  S64AddS64(&temp_check, &y_change);
1977 
1978  if (S64CompareS64(&temp_check, &zero) > 0)
1979  {
1980  --py1;
1981  ++py2;
1982 
1983  /* stop_y -= two_a2; */
1984  S64SubtractS32(&stop_y, two_a2);
1985 
1986  /* error += y_change; */
1987  S64AddS64(&error, &y_change);
1988 
1989  /* y_change += two_a2; */
1990  S64AddS32(&y_change, two_a2);
1991  }
1992  }
1993 
1994  FUNCTION_FINISH(DrawArc);
1995 }
1996 
2011 static void DrawSector(S16BIT x, S16BIT y, U16BIT w, U16BIT h, U16BIT start, U16BIT arc, U16BIT width, DLAColor fill_colour, DLAColor line_colour)
2012 {
2013  S32BIT cx, cy, rx, ry;
2014  S32BIT px1, px2;
2015  S32BIT py1, py2;
2016  S32BIT hsx, hsy, hex, hey;
2017  S_64_BIT x_change, y_change;
2018  S_64_BIT error;
2019  S32BIT two_a2, two_b2, stride;
2020  S_64_BIT stop_x, stop_y;
2021  S32BIT xadj, yadj;
2022  U16BIT end;
2023  U16BIT qs, qe, i;
2024  DLAColor *sp1, *sp2;
2025  S_64_BIT temp_check, zero;
2026  S32BIT sd_adj=0;
2027 #ifdef DEBUG_DRAW_SECTOR
2028  printf("DrawSector: x %d y %d w %d h %d start %d arc %d lw %d fill %d line %d\n",
2029  x,y,w,h,start,arc,width,(int)fill_colour,(int)line_colour);
2030 #endif
2031 
2032  /* Quadrant type */
2033  enum
2034  {
2035  QUADRANT_FULL,
2036  QUADRANT_EMPTY,
2037  QUADRANT_START,
2038  QUADRANT_END,
2039  QUADRANT_START_BEFORE_END,
2040  QUADRANT_END_BEFORE_START
2041  } quadrant_type[4];
2042 
2043  FUNCTION_START(DrawSector);
2044 
2045  stride = dla_canvas->bf_stride / sizeof(DLAColor);
2046 
2047  /* Make sure the width is at least 3 pixels */
2048  w = MAX(3, w);
2049 
2050  /* Calculate radii and centre */
2051  rx = (w+1)/2-1;
2052  ry = (h+1)/2-1;
2053  cx = x + rx;
2054  cy = y + ry;
2055 
2056  /* Calculate adjustment for even width / height */
2057  xadj = !(w & 1);
2058  yadj = !(h & 1);
2059 
2060  /* Calculate 'hit points' for start and end angle */
2061  end = start + arc;
2062  if (end >= 23040)
2063  {
2064  end -= 23040;
2065  }
2066 
2067  /* Find quadrant types */
2068  qs = start / 5760;
2069  qe = end / 5760;
2070 
2071  for (i = 0; i < 4; ++i)
2072  {
2073  quadrant_type[i] = QUADRANT_EMPTY;
2074  }
2075  if (qs < qe)
2076  {
2077  for (i = qs + 1; i < qe; ++i)
2078  {
2079  quadrant_type[i] = QUADRANT_FULL;
2080  }
2081  quadrant_type[qs] = QUADRANT_START;
2082  quadrant_type[qe] = QUADRANT_END;
2083  }
2084  else if (qs > qe)
2085  {
2086  for (i = qs + 1; i < qe + 4; ++i)
2087  {
2088  quadrant_type[i%4] = QUADRANT_FULL;
2089  }
2090  quadrant_type[qs] = QUADRANT_START;
2091  quadrant_type[qe] = QUADRANT_END;
2092  }
2093  else
2094  {
2095  if (start < end)
2096  {
2097  quadrant_type[qs] = QUADRANT_START_BEFORE_END;
2098  }
2099  else
2100  {
2101  for (i = qs + 1; i < qe + 4; ++i)
2102  {
2103  quadrant_type[i%4] = QUADRANT_FULL;
2104  }
2105  quadrant_type[qs] = QUADRANT_END_BEFORE_START;
2106  }
2107  }
2108 
2109 #ifdef DEBUG_DRAW_SECTOR
2110  printf("qs = %d, qe = %d\n", qs, qe);
2111  for (i = 0; i < 4; i++)
2112  {
2113  printf("quadrant_type[%d] = %s\n", i,
2114  quadrant_type[i] == QUADRANT_FULL ? "QUADRANT_FULL" :
2115  quadrant_type[i] == QUADRANT_EMPTY ? "QUADRANT_EMPTY" :
2116  quadrant_type[i] == QUADRANT_START ? "QUADRANT_START" :
2117  quadrant_type[i] == QUADRANT_END ? "QUADRANT_END" :
2118  quadrant_type[i] == QUADRANT_START_BEFORE_END ? "QUADRANT_START_BEFORE_END" :
2119  quadrant_type[i] == QUADRANT_END_BEFORE_START ? "QUADRANT_END_BEFORE_START" :
2120  "UNKNOWN");
2121  }
2122 #endif
2123 
2124 
2125  GetHitPoints(rx, ry, start, &hsx, &hsy);
2126  GetHitPoints(rx, ry, end, &hex, &hey);
2127 
2128  hsx += cx + xadj * (hsx >= 0);
2129  hex += cx + xadj * (hex >= 0);
2130  hsy += cy + yadj * (hsy >= 0);
2131  hey += cy + yadj * (hey >= 0);
2132 
2133 #ifdef DEBUG_DRAW_SECTOR
2134  printf("hsx %d hex %d\nhsy %d hey %d\n", hsx, hex, hsy, hey);
2135  printf("cx = %d, cy = %d, xadj = %d, yadj = %d\n", cx, cy, xadj, yadj);
2136 #endif
2137 
2138 #ifdef DEBUG_DLA_QUAD
2139  printf("quadrants: %s %s %s %s\n",
2140  quadrant_type[0] == QUADRANT_FULL ? "QUADRANT_FULL" :
2141  quadrant_type[0] == QUADRANT_EMPTY ? "QUADRANT_EMPTY" :
2142  quadrant_type[0] == QUADRANT_START ? "QUADRANT_START" :
2143  quadrant_type[0] == QUADRANT_END ? "QUADRANT_END" :
2144  quadrant_type[0] == QUADRANT_START_BEFORE_END ? "QUADRANT_START_BEFORE_END" :
2145  quadrant_type[0] == QUADRANT_END_BEFORE_START ? "QUADRANT_END_BEFORE_START" : "UNKNOWN",
2146  quadrant_type[1] == QUADRANT_FULL ? "QUADRANT_FULL" :
2147  quadrant_type[1] == QUADRANT_EMPTY ? "QUADRANT_EMPTY" :
2148  quadrant_type[1] == QUADRANT_START ? "QUADRANT_START" :
2149  quadrant_type[1] == QUADRANT_END ? "QUADRANT_END" :
2150  quadrant_type[1] == QUADRANT_START_BEFORE_END ? "QUADRANT_START_BEFORE_END" :
2151  quadrant_type[1] == QUADRANT_END_BEFORE_START ? "QUADRANT_END_BEFORE_START" : "UNKNOWN",
2152  quadrant_type[2] == QUADRANT_FULL ? "QUADRANT_FULL" :
2153  quadrant_type[2] == QUADRANT_EMPTY ? "QUADRANT_EMPTY" :
2154  quadrant_type[2] == QUADRANT_START ? "QUADRANT_START" :
2155  quadrant_type[2] == QUADRANT_END ? "QUADRANT_END" :
2156  quadrant_type[2] == QUADRANT_START_BEFORE_END ? "QUADRANT_START_BEFORE_END" :
2157  quadrant_type[2] == QUADRANT_END_BEFORE_START ? "QUADRANT_END_BEFORE_START" : "UNKNOWN",
2158  quadrant_type[3] == QUADRANT_FULL ? "QUADRANT_FULL" :
2159  quadrant_type[3] == QUADRANT_EMPTY ? "QUADRANT_EMPTY" :
2160  quadrant_type[3] == QUADRANT_START ? "QUADRANT_START" :
2161  quadrant_type[3] == QUADRANT_END ? "QUADRANT_END" :
2162  quadrant_type[3] == QUADRANT_START_BEFORE_END ? "QUADRANT_START_BEFORE_END" :
2163  quadrant_type[3] == QUADRANT_END_BEFORE_START ? "QUADRANT_END_BEFORE_START" : "UNKNOWN");
2164  fflush(stdout);
2165 #endif
2166 
2167  /* Calculate 2a^2 and 2b^2 */
2168  two_a2 = 2 * rx * rx;
2169  two_b2 = 2 * ry * ry;
2170 
2171  /* Start first stage: in this stage the y value is changing faster than
2172  * the x value, so y changes at every iteration and x is only corrected
2173  * when required.
2174  */
2175  px1 = cx+rx+xadj;
2176  px2 = cx-rx;
2177  py1 = cy+yadj;
2178  py2 = cy;
2179 
2180  /* x_change = ry * ry * (1 - 2 * rx); */
2181  S64AssignS32(&x_change, ry);
2182  S64MultiplyS32(&x_change, ry);
2183  S64MultiplyS32(&x_change, 1 - 2 * rx);
2184 
2185  /* y_change = rx * rx; */
2186  S64AssignS32(&y_change, rx);
2187  S64MultiplyS32(&y_change, rx);
2188 
2189  /* stop_x = two_b2 * rx; */
2190  S64AssignS32(&stop_x, two_b2);
2191  S64MultiplyS32(&stop_x, rx);
2192 
2193  /* stop_y = 0; */
2194  S64AssignS32(&stop_y, 0);
2195 
2196  /* error = 0; */
2197  S64AssignS32(&error, 0);
2198 
2199  sp1 = dla_canvas->cols + py1 * stride;
2200  sp2 = dla_canvas->cols + py2 * stride;
2201 
2202 #if DEBUG_DLA
2203  printf("first phase\n"); fflush(stdout);
2204 #endif
2205  /* while (stop_x >= stop_y) */
2206  while (S64CompareS64(&stop_x, &stop_y) >= 0)
2207  {
2208  if (py2 >= 0 && py2 < dla_canvas->height)
2209  {
2210  /* First quadrant */
2211  switch (quadrant_type[0])
2212  {
2213  case QUADRANT_FULL:
2214  FillLine(sp2, cx + xadj, px1 - cx + 1, fill_colour);
2215  break;
2216  case QUADRANT_START:
2217  if (py2 <= hsy)
2218  {
2219  FillLine(sp2, cx + xadj, px1 - cx + 1, fill_colour);
2220  }
2221  break;
2222  case QUADRANT_END:
2223  if (py2 >= hey)
2224  {
2225  FillLine(sp2, hex, px1 - hex + 1 + xadj, fill_colour);
2226  }
2227  break;
2228  case QUADRANT_START_BEFORE_END:
2229  if (py2 <= hsy && py2 >= hey)
2230  {
2231  FillLine(sp2, hex, px1 - hex + 1 + xadj, fill_colour);
2232  }
2233  break;
2234  case QUADRANT_END_BEFORE_START:
2235  if (py2 <= hsy)
2236  {
2237  FillLine(sp2, cx + xadj, px1 - cx + 1, fill_colour);
2238  }
2239  if (py2 >= hey)
2240  {
2241  FillLine(sp2, hex, px1 - hex + 1 + xadj, fill_colour);
2242  }
2243  break;
2244  case QUADRANT_EMPTY:
2245  break;
2246  }
2247 
2248  /* Second quadrant */
2249  switch (quadrant_type[1])
2250  {
2251  case QUADRANT_FULL:
2252  FillLine(sp2, px2, cx - px2 + 1 + xadj, fill_colour);
2253  break;
2254  case QUADRANT_START:
2255  if (py2 >= hsy)
2256  {
2257  FillLine(sp2, px2, hsx - px2 + 1, fill_colour);
2258  }
2259  break;
2260  case QUADRANT_END:
2261  if (py2 <= hey)
2262  {
2263  FillLine(sp2, px2, cx - px2 + 1 + xadj, fill_colour);
2264  }
2265  break;
2266  case QUADRANT_START_BEFORE_END:
2267  if (py2 >= hsy && py2 <= hey)
2268  {
2269  FillLine(sp2, px2, hsx - px2 + 1, fill_colour);
2270  }
2271  break;
2272  case QUADRANT_END_BEFORE_START:
2273  if (py2 >= hsy)
2274  {
2275  FillLine(sp2, px2, hsx - px2 + 1, fill_colour);
2276  }
2277  if (py2 <= hey)
2278  {
2279  FillLine(sp2, px2, cx - px2 + 1 + xadj, fill_colour);
2280  }
2281  break;
2282  case QUADRANT_EMPTY:
2283  break;
2284  }
2285  }
2286 
2287  if (py1 >= 0 && py1 < dla_canvas->height)
2288  {
2289  /* Third quadrant */
2290  switch (quadrant_type[2])
2291  {
2292  case QUADRANT_FULL:
2293  FillLine(sp1, px2, cx - px2 + 1 + xadj, fill_colour);
2294  break;
2295  case QUADRANT_START:
2296  if (py1 >= hsy)
2297  {
2298  FillLine(sp1, px2, cx - px2 + 1 + xadj, fill_colour);
2299  }
2300  break;
2301  case QUADRANT_END:
2302  if (py1 <= hey)
2303  {
2304  FillLine(sp1, px2, hex - px2 + 1, fill_colour);
2305  }
2306  break;
2307  case QUADRANT_START_BEFORE_END:
2308  if (py1 >= hsy && py1 <= hey)
2309  {
2310  FillLine(sp1, px2, hex - px2 + 1, fill_colour);
2311  }
2312  break;
2313  case QUADRANT_END_BEFORE_START:
2314  if (py1 >= hsy)
2315  {
2316  FillLine(sp1, px2, cx - px2 + 1 + xadj, fill_colour);
2317  }
2318  if (py1 <= hey)
2319  {
2320  FillLine(sp1, px2, hex - px2 + 1, fill_colour);
2321  }
2322  break;
2323  case QUADRANT_EMPTY:
2324  break;
2325  }
2326 
2327  /* Fourth quadrant */
2328  switch (quadrant_type[3])
2329  {
2330  case QUADRANT_FULL:
2331  FillLine(sp1, cx + xadj, px1 - cx + 1, fill_colour);
2332  break;
2333  case QUADRANT_START:
2334  if (py1 <= hsy)
2335  {
2336  FillLine(sp1, hsx, px1 - hsx + 1 + xadj, fill_colour);
2337  }
2338  break;
2339  case QUADRANT_END:
2340  if (py1 >= hey)
2341  {
2342  FillLine(sp1, cx + xadj, px1 - cx + 1, fill_colour);
2343  }
2344  break;
2345  case QUADRANT_START_BEFORE_END:
2346  if (py1 <= hsy && py1 >= hey)
2347  {
2348  FillLine(sp1, hsx, px1 - hsx + 1 + xadj, fill_colour);
2349  }
2350  break;
2351  case QUADRANT_END_BEFORE_START:
2352  if (py1 <= hsy)
2353  {
2354  FillLine(sp1, hsx, px1 - hsx + 1 + xadj, fill_colour);
2355  }
2356  if (py1 >= hey)
2357  {
2358  FillLine(sp1, cx + xadj, px1 - cx + 1, fill_colour);
2359  }
2360  break;
2361  case QUADRANT_EMPTY:
2362  break;
2363  }
2364  }
2365 
2366  ++py1;
2367  sp1 += stride;
2368  --py2;
2369  sp2 -= stride;
2370 
2371  /* stop_y += two_a2; */
2372  S64AddS32(&stop_y, two_a2);
2373 
2374  /* error += y_change; */
2375  S64AddS64(&error, &y_change);
2376 
2377  /* y_change += two_a2; */
2378  S64AddS32(&y_change, two_a2);
2379 
2380  /* if (2*error + x_change > 0) */
2381  S64AssignS32(&zero, 0);
2382  S64AssignS32(&temp_check, 0);
2383  S64AddS64(&temp_check, &error);
2384  S64AddS64(&temp_check, &error);
2385  S64AddS64(&temp_check, &x_change);
2386 
2387  if (S64CompareS64(&temp_check, &zero) > 0)
2388  {
2389  ++px2;
2390  --px1;
2391 
2392  /* stop_x -= two_b2; */
2393  S64SubtractS32(&stop_x, two_b2);
2394 
2395  /* error += x_change; */
2396  S64AddS64(&error, &x_change);
2397 
2398  /* x_change += two_b2; */
2399  S64AddS32(&x_change, two_b2);
2400  }
2401  }
2402 
2403  /* Start second stage: in this stage the x value is changing faster than
2404  * the y value, so x changes at every iteration and y is only corrected
2405  * when required.
2406  */
2407  px1 = cx+xadj;
2408  px2 = cx;
2409  py1 = cy+ry+yadj;
2410  py2 = cy-ry;
2411 
2412  /* x_change = ry * ry; */
2413  S64AssignS32(&x_change, ry);
2414  S64MultiplyS32(&x_change, ry);
2415 
2416  /* y_change = rx * rx * (1 - 2 * ry); */
2417  S64AssignS32(&y_change, rx);
2418  S64MultiplyS32(&y_change, rx);
2419  S64MultiplyS32(&y_change, 1 - 2 * ry);
2420 
2421  /* stop_x = 0; */
2422  S64AssignS32(&stop_x, 0);
2423 
2424  /* stop_y = two_a2 * ry; */
2425  S64AssignS32(&stop_y, two_a2);
2426  S64MultiplyS32(&stop_y, ry);
2427 
2428  /* error = 0; */
2429  S64AssignS32(&error, 0);
2430 
2431  sp1 = dla_canvas->cols + py1 * stride;
2432  sp2 = dla_canvas->cols + py2 * stride;
2433 
2434  /* while (stop_x <= stop_y) */
2435  while (S64CompareS64(&stop_x, &stop_y) <= 0)
2436  {
2437  if (py2 >= 0 && py2 < dla_canvas->height)
2438  {
2439  /* First quadrant */
2440  switch (quadrant_type[0])
2441  {
2442  case QUADRANT_FULL:
2443  FillLine(sp2, cx + xadj, px1 - cx + 1, fill_colour);
2444  break;
2445  case QUADRANT_START:
2446  if (px1 <= hsx)
2447  {
2448  FillLine(sp2, cx + xadj, px1 - cx + 1, fill_colour);
2449  }
2450  break;
2451  case QUADRANT_END:
2452  if (px1 >= hex)
2453  {
2454  FillLine(sp2, hex, px1 - hex + 1 + xadj, fill_colour);
2455  }
2456  break;
2457  case QUADRANT_START_BEFORE_END:
2458  if (px1 <= hsx && px1 >= hex)
2459  {
2460  FillLine(sp2, hex, px1 - hex + 1 + xadj, fill_colour);
2461  }
2462  break;
2463  case QUADRANT_END_BEFORE_START:
2464  if (px1 <= hsx)
2465  {
2466  FillLine(sp2, cx + xadj, px1 - cx + 1, fill_colour);
2467  }
2468  if (px1 >= hex)
2469  {
2470  FillLine(sp2, hex, px1 - hex + 1 + xadj, fill_colour);
2471  }
2472  break;
2473  case QUADRANT_EMPTY:
2474  break;
2475  }
2476 
2477  /* Second quadrant */
2478  switch (quadrant_type[1])
2479  {
2480  case QUADRANT_FULL:
2481  FillLine(sp2, px2, cx - px2 + 1 + xadj, fill_colour);
2482  break;
2483  case QUADRANT_START:
2484  if (px2 <= hsx)
2485  {
2486  FillLine(sp2, px2, hsx - px2 + 1, fill_colour);
2487  }
2488  break;
2489  case QUADRANT_END:
2490  if (px2 >= hex)
2491  {
2492  FillLine(sp2, px2, cx - px2 + 1 + xadj, fill_colour);
2493  }
2494  break;
2495  case QUADRANT_START_BEFORE_END:
2496  if (px2 <= hsx && px2 >= hex)
2497  {
2498  FillLine(sp2, px2, hsx - px2 + 1, fill_colour);
2499  }
2500  break;
2501  case QUADRANT_END_BEFORE_START:
2502  if (px2 <= hsx)
2503  {
2504  FillLine(sp2, px2, hsx - px2 + 1, fill_colour);
2505  }
2506  if (px2 >= hex)
2507  {
2508  FillLine(sp2, px2, cx - px2 + 1 + xadj, fill_colour);
2509  }
2510  break;
2511  case QUADRANT_EMPTY:
2512  break;
2513  }
2514  }
2515 
2516  if (py1 >= 0 && py1 < dla_canvas->height)
2517  {
2518  /* Third quadrant */
2519  switch (quadrant_type[2])
2520  {
2521  case QUADRANT_FULL:
2522  FillLine(sp1, px2, cx - px2 + 1 + xadj, fill_colour);
2523  break;
2524  case QUADRANT_START:
2525  if (px2 >= hsx)
2526  {
2527  FillLine(sp1, px2, cx - px2 + 1 + xadj, fill_colour);
2528  }
2529  break;
2530  case QUADRANT_END:
2531  if (px2 <= hex)
2532  {
2533  FillLine(sp1, px2, hex - px2 + 1, fill_colour);
2534  }
2535  break;
2536  case QUADRANT_START_BEFORE_END:
2537  if (px2 >= hsx && px2 <= hex)
2538  {
2539  FillLine(sp1, px2, hex - px2 + 1, fill_colour);
2540  }
2541  break;
2542  case QUADRANT_END_BEFORE_START:
2543  if (px2 >= hsx)
2544  {
2545  FillLine(sp1, px2, cx - px2 + 1 + xadj, fill_colour);
2546  }
2547  if (px2 <= hex)
2548  {
2549  FillLine(sp1, px2, hex - px2 + 1, fill_colour);
2550  }
2551  break;
2552  case QUADRANT_EMPTY:
2553  break;
2554  }
2555 
2556  /* Fourth quadrant */
2557  switch (quadrant_type[3])
2558  {
2559  case QUADRANT_FULL:
2560  FillLine(sp1, cx + xadj, px1 - cx + 1, fill_colour);
2561  break;
2562  case QUADRANT_START:
2563  if (px1 >= hsx)
2564  {
2565  FillLine(sp1, hsx, px1 - hsx + 1 + xadj, fill_colour);
2566  }
2567  break;
2568  case QUADRANT_END:
2569  if (px1 <= hex)
2570  {
2571  FillLine(sp1, cx + xadj, px1 - cx + 1, fill_colour);
2572  }
2573  break;
2574  case QUADRANT_START_BEFORE_END:
2575  if (px1 >= hsx && px1 <= hex)
2576  {
2577  FillLine(sp1, hsx, px1 - hsx + 1 + xadj, fill_colour);
2578  }
2579  break;
2580  case QUADRANT_END_BEFORE_START:
2581  if (px1 >= hsx)
2582  {
2583  FillLine(sp1, hsx, px1 - hsx + 1 + xadj, fill_colour);
2584  }
2585  if (px1 <= hex)
2586  {
2587  FillLine(sp1, cx + xadj, px1 - cx + 1, fill_colour);
2588  }
2589  break;
2590  case QUADRANT_EMPTY:
2591  break;
2592  }
2593  }
2594 
2595  ++px1;
2596  --px2;
2597 
2598  /* stop_x += two_b2; */
2599  S64AddS32(&stop_x, two_b2);
2600 
2601  /* error += x_change; */
2602  S64AddS64(&error, &x_change);
2603 
2604  /* x_change += two_b2; */
2605  S64AddS32(&x_change, two_b2);
2606 
2607  /* if (2 * error + y_change > 0) */
2608  S64AssignS32(&zero, 0);
2609  S64AssignS32(&temp_check, 0);
2610  S64AddS64(&temp_check, &error);
2611  S64AddS64(&temp_check, &error);
2612  S64AddS64(&temp_check, &y_change);
2613 
2614  if (S64CompareS64(&temp_check, &zero) > 0)
2615  {
2616  --py1;
2617  sp1 -= stride;
2618  ++py2;
2619  sp2 += stride;
2620 
2621  /* stop_y -= two_a2; */
2622  S64SubtractS32(&stop_y, two_a2);
2623 
2624  /* error += y_change; */
2625  S64AddS64(&error, &y_change);
2626 
2627  /* y_change += two_a2; */
2628  S64AddS32(&y_change, two_a2);
2629  }
2630  }
2631 
2632  if (mg_ctxt.out_osd_width == 720)
2633  {
2634  /*small adjustment for "pacman" sectors at SD resolution*/
2635  sd_adj = 1;
2636  }
2637  /* Fill missing triangles */
2638  switch (quadrant_type[0])
2639  {
2640  case QUADRANT_START:
2641  FillTriangle(cx+xadj-1, hsy-xadj, hsx-xadj, hsy-xadj, cx+xadj-1, cy, fill_colour);
2642  DrawLine(cx+xadj, cy, hsx-xadj, hsy-yadj, width, line_colour);
2643  break;
2644  case QUADRANT_END:
2645  FillTriangle(hex, hey-yadj-sd_adj, hex, cy+1, cx+xadj-1, cy+1, fill_colour);
2646  DrawLine(cx+xadj, cy, hex, hey-yadj, width, line_colour);
2647  break;
2648  case QUADRANT_START_BEFORE_END:
2649  FillTriangle(hex, hsy, hsx, hsy, cx+xadj-1, cy+1, fill_colour);
2650  DrawLine(cx+xadj-1, cy+1, hsx, hsy, width, line_colour);
2651  FillTriangle(hex, hey-sd_adj, hex, hsy, cx+xadj-1, cy+1, fill_colour);
2652  DrawLine(cx+xadj-1, cy, hex, hey, width, line_colour);
2653  break;
2654  case QUADRANT_END_BEFORE_START:
2655  FillTriangle(cx+xadj-1, hsy, hsx, hsy, cx+xadj-1, cy+1, fill_colour);
2656  DrawLine(cx+xadj-1, cy+1, hsx, hsy, width, line_colour);
2657  FillTriangle(hex, hey-sd_adj, hex, cy+1, cx+xadj-1, cy+1, fill_colour);
2658  DrawLine(cx+xadj-1, cy, hex, hey-sd_adj, width, line_colour);
2659  break;
2660  default:
2661  ;
2662  }
2663 
2664  switch (quadrant_type[1])
2665  {
2666  case QUADRANT_START:
2667  FillTriangle(hsx, hsy, hsx, cy+1, cx+1, cy+1, fill_colour);
2668  DrawLine(cx+1, cy, hsx, hsy, width, line_colour);
2669  break;
2670  case QUADRANT_END:
2671  FillTriangle(hex, hey, cx+1, hey, cx+1, cy+1, fill_colour);
2672  DrawLine(cx, cy+1, hex, hey, width, line_colour);
2673  break;
2674  case QUADRANT_START_BEFORE_END:
2675  FillTriangle(hex, hey, hsx, hey, cx+1, cy+1, fill_colour);
2676  DrawLine(cx, cy, hex, hey, width, line_colour);
2677  FillTriangle(hsx, hsy, hsx, hey, cx+1, cy+1, fill_colour);
2678  DrawLine(cx, cy, hsx, hsy, width, line_colour);
2679  break;
2680  case QUADRANT_END_BEFORE_START:
2681  FillTriangle(hsx, hsy, hsx, cy+1, cx+1, cy+1, fill_colour);
2682  DrawLine(cx, cy+1, hsx, hsy, width, line_colour);
2683  FillTriangle(hex, hey, cx+1, hey, cx+1, cy+1, fill_colour);
2684  DrawLine(cx, cy+1, hex, hey, width, line_colour);
2685  break;
2686  default:
2687  ;
2688  }
2689 
2690  switch (quadrant_type[2])
2691  {
2692  case QUADRANT_START:
2693  FillTriangle(hsx, hsy+1, cx+1, hsy+1, cx+1, cy+yadj, fill_colour);
2694  DrawLine(cx, cy+yadj, hsx, hsy, width, line_colour);
2695  break;
2696  case QUADRANT_END:
2697  FillTriangle(hex, cy+yadj, hex, hey, cx+1, cy+yadj, fill_colour);
2698  DrawLine(cx, cy+yadj, hex-xadj, hey, width, line_colour);
2699  break;
2700  case QUADRANT_START_BEFORE_END:
2701  FillTriangle(cx+1, cy+yadj, hsx, hsy, hex, hsy, fill_colour);
2702  DrawLine(cx, cy+yadj, hsx, hsy, width, line_colour);
2703  FillTriangle(cx+1, cy+yadj, hex, hsy, hex, hey, fill_colour);
2704  DrawLine(cx, cy+yadj, hex, hey, width, line_colour);
2705  break;
2706  case QUADRANT_END_BEFORE_START:
2707  FillTriangle(hsx, hsy+1, cx+1, hsy+1, cx+1, cy+yadj, fill_colour);
2708  DrawLine(cx, cy+yadj, hsx, hsy, width, line_colour);
2709  FillTriangle(hex, cy+yadj, hex, hey, cx+1, cy+yadj, fill_colour);
2710  DrawLine(cx, cy+yadj, hex, hey, width, line_colour);
2711  break;
2712  default:
2713  ;
2714  }
2715 
2716  switch (quadrant_type[3])
2717  {
2718  case QUADRANT_START:
2719  FillTriangle(cx+xadj-1, cy+yadj, hsx, cy+yadj, hsx, hsy, fill_colour);
2720  DrawLine(cx+xadj-1, cy+yadj, hsx, hsy, width, line_colour);
2721  break;
2722  case QUADRANT_END:
2723  FillTriangle(cx+xadj-1, cy+yadj, cx+xadj, hey+1, hex+sd_adj, hey+1, fill_colour);
2724  DrawLine(cx+xadj, cy+yadj, hex, hey, width, line_colour);
2725  break;
2726  case QUADRANT_START_BEFORE_END:
2727  FillTriangle(cx+xadj-1, cy+yadj, hsx, hsy, hsx, hey, fill_colour);
2728  DrawLine(cx+xadj-1, cy+yadj, hsx, hsy, width, line_colour);
2729  FillTriangle(cx+xadj-1, cy+yadj, hsx, hey, hex, hey, fill_colour);
2730  DrawLine(cx+xadj-1, cy+yadj, hex, hey, width, line_colour);
2731  break;
2732  case QUADRANT_END_BEFORE_START:
2733  FillTriangle(cx+xadj-1, cy+yadj, hsx, cy+yadj, hsx, hsy, fill_colour);
2734  DrawLine(cx+xadj-1, cy+yadj, hsx, hsy, width, line_colour);
2735  FillTriangle(cx+xadj-1, cy+yadj, cx+xadj-1, hey+1, hex, hey+1, fill_colour);
2736  DrawLine(cx+xadj-1, cy+yadj, hex, hey, width, line_colour);
2737  break;
2738  default:
2739  ;
2740  }
2741 
2742  /* Draw outline */
2743  DrawArc(x, y, w, h, start, arc, width, line_colour);
2744 
2745  FUNCTION_FINISH(DrawSector);
2746 }
2747 
2756 static void FillLine(DLAColor *buffer, S16BIT offset, U16BIT length, DLAColor colour)
2757 {
2758  S32BIT f, t;
2759 
2760  FUNCTION_START(FillLine);
2761 
2762  f = offset;
2763  t = offset + length - 1;
2764  f = f < 0 ? 0 : f;
2765  t = t >= dla_canvas->width ? dla_canvas->width : t;
2766 
2767  if (t > f)
2768  {
2769  DLA_MEMSET( buffer + f, colour, t - f );
2770  }
2771 
2772  FUNCTION_FINISH(FillLine);
2773 }
2774 
2786 static void FillTriangle(S16BIT x1, S16BIT y1, S16BIT x2, S16BIT y2,
2787  S16BIT x3, S16BIT y3, DLAColor colour)
2788 {
2789  S_POLYGON polygon;
2790  S_POINT points[3];
2791 
2792  FUNCTION_START(FillTriangle);
2793 
2794 #if DEBUG_DLA
2795  printf("FillTriangle(%d, %d, %d, %d, %d, %d)\n", x1, y1, x2, y2, x3, y3);
2796 #endif
2797 
2798  points[0].x = x1;
2799  points[0].y = y1;
2800  points[1].x = x2;
2801  points[1].y = y2;
2802  points[2].x = x3;
2803  points[2].y = y3;
2804 
2805  if ( ConvertPolygon(points, 3, &polygon)
2806  && FillPolygon(&polygon, colour) )
2807  {
2808  FreePolygon(&polygon);
2809  }
2810 
2811  FUNCTION_FINISH(FillTriangle);
2812 }
2813 
2822 static void FillCircle(S16BIT cx, S16BIT cy, U16BIT width, DLAColor colour)
2823 {
2824  U16BIT radius = width / 2;
2825  U16BIT even = (width % 2 == 0);
2826 
2827  S32BIT f = 1 - radius;
2828  S32BIT ddF_x = 0;
2829  S32BIT ddF_y = -2 * radius;
2830  S32BIT x = 0;
2831  S32BIT y = radius;
2832  S32BIT line_from_ext, line_to_ext, line_from_int, line_to_int, lf, lt, stride;
2833 
2834  DLAColor *sp1, *sp2, *sp3, *sp4;
2835 
2836  FUNCTION_START(FillCircle);
2837 
2838  /* Special case, only for HD resolutions */
2839  if (width <= 4 && mg_ctxt.out_osd_width > 720)
2840  {
2841  FillSimpleRectangle(cx-radius, cy-radius,
2842  cx+radius+even+1, cy+radius+even+1, colour);
2843  return;
2844  }
2845 
2846  stride = dla_canvas->bf_stride / sizeof(DLAColor);
2847 
2848  /* Check if the circle needs to be drawn */
2849  if (cx + radius >= 0 && cx - radius < dla_canvas->width &&
2850  cy >= 0 && cy - radius < dla_canvas->height)
2851  {
2852  sp1 = dla_canvas->cols + (cy + y - even) * stride;
2853  sp2 = dla_canvas->cols + (cy - y) * stride;
2854  sp3 = dla_canvas->cols + (cy + x - even) * stride;
2855  sp4 = dla_canvas->cols + (cy - x) * stride;
2856 
2857  /* Bresenham circle-drawing algorithm */
2858  if ( (even == 0) && (cy < dla_canvas->height) )
2859  {
2860  lf = cx - radius;
2861  if (lf < 0)
2862  {
2863  lf = 0;
2864  }
2865  lt = cx + radius;
2866  if (lt >= dla_canvas->width)
2867  {
2868  lt = dla_canvas->width - 1;
2869  }
2870  lt -= lf;
2871  lt++;
2872  DLA_MEMSET( sp4 + lf, colour, lt );
2873  }
2874 
2875  line_from_ext = cx - x;
2876  line_to_ext = cx + x - even;
2877  line_from_int = cx - y;
2878  line_to_int = cx + y - even;
2879 
2880  while(x < y)
2881  {
2882  if(f >= 0)
2883  {
2884  y--;
2885  sp1 -= stride;
2886  sp2 += stride;
2887  line_from_int++;
2888  line_to_int--;
2889  ddF_y += 2;
2890  f += ddF_y;
2891  }
2892  x++;
2893  sp3 += stride;
2894  sp4 -= stride;
2895  line_from_ext--;
2896  line_to_ext++;
2897  ddF_x += 2;
2898  f += ddF_x + 1;
2899 
2900  lf = line_from_ext;
2901  lt = line_to_ext;
2902  if (lf < 0)
2903  {
2904  lf = 0;
2905  }
2906  if (lt >= dla_canvas->width)
2907  {
2908  lt = dla_canvas->width - 1;
2909  }
2910  if (lt > lf)
2911  {
2912  lt -= lf;
2913  lt++;
2914  if (cy + y - even >= 0 && cy + y - even < dla_canvas->height)
2915  {
2916  DLA_MEMSET( sp1 + lf, colour, lt );
2917  }
2918  if (cy - y >= 0 && cy - y < dla_canvas->height)
2919  {
2920  DLA_MEMSET( sp2 + lf, colour, lt );
2921  }
2922  }
2923 
2924  lf = line_from_int;
2925  lt = line_to_int;
2926  if (lf < 0)
2927  {
2928  lf = 0;
2929  }
2930  if (lt >= dla_canvas->width)
2931  {
2932  lt = dla_canvas->width - 1;
2933  }
2934  if (lt > lf)
2935  {
2936  lt -= lf;
2937  lt++;
2938  if (cy + x - even >= 0 && cy + x - even < dla_canvas->height)
2939  {
2940  DLA_MEMSET( sp3 + lf, colour, lt );
2941  }
2942  if (cy - x >= 0 && cy - x < dla_canvas->height)
2943  {
2944  DLA_MEMSET( sp4 + lf, colour, lt );
2945  }
2946  }
2947  }
2948  }
2949 
2950  FUNCTION_FINISH(FillCircle);
2951 }
2952 
2960 static void PutPixel(S16BIT x, S16BIT y, DLAColor c)
2961 {
2962  FUNCTION_START(PutPixel);
2963 
2964  if (x >= 0 && x < dla_canvas->width && y >= 0 && y < dla_canvas->height)
2965  {
2966  U32BIT stride = dla_canvas->bf_stride / sizeof(DLAColor);
2967  dla_canvas->cols[x+y*stride] = c;
2968  }
2969 
2970  FUNCTION_FINISH(PutPixel);
2971 }
2972 
2982 static BOOLEAN AppendPoint(S_POINT_LIST ***ppl, S16BIT x, S16BIT y)
2983 {
2984  BOOLEAN success;
2985 
2986  FUNCTION_START(AppendPoint);
2987 
2988  **ppl = OSD_MemAlloc(sizeof ***ppl);
2989  if (**ppl != NULL)
2990  {
2991  (**ppl)->point.x = x;
2992  (**ppl)->point.y = y;
2993  *ppl = &((**ppl)->next);
2994 
2995  success = TRUE;
2996  }
2997  else
2998  {
2999  success = FALSE;
3000  }
3001 
3002  FUNCTION_FINISH(AppendPoint);
3003 
3004  return success;
3005 }
3006 
3012 static U32BIT GetLog2(U32BIT v)
3013 {
3014  const U32BIT b[] = {0xAAAAAAAAUL, 0xCCCCCCCCUL, 0xF0F0F0F0UL,
3015  0xFF00FF00UL, 0xFFFF0000UL};
3016  register U32BIT r;
3017 
3018  FUNCTION_START(GetLog2);
3019 
3020  /* Make sure v is a power of 2 */
3021  v--;
3022  v |= v >> 1;
3023  v |= v >> 2;
3024  v |= v >> 4;
3025  v |= v >> 8;
3026  v |= v >> 16;
3027  v++;
3028 
3029  /* Find log2(v) */
3030  r = (v & b[0]) != 0;
3031  r |= ((v & b[4]) != 0) << 4;
3032  r |= ((v & b[3]) != 0) << 3;
3033  r |= ((v & b[2]) != 0) << 2;
3034  r |= ((v & b[1]) != 0) << 1;
3035 
3036  FUNCTION_FINISH(GetLog2);
3037 
3038  return r;
3039 }
3040 
3046 static U16BIT GetSqrt(U32BIT v)
3047 {
3048  U32BIT temp, g = 0, b = 0x8000, bshft = 15;
3049 
3050  FUNCTION_START(GetSqrt);
3051 
3052  do {
3053  temp = ((g << 1) + b) << bshft;
3054  --bshft;
3055  if (v >= temp) {
3056  g += b;
3057  v -= temp;
3058  }
3059  } while (b >>= 1);
3060 
3061  FUNCTION_FINISH(GetSqrt);
3062 
3063  return g;
3064 }
3065 
3075 static void GetHitPoints(U32BIT rx, U32BIT ry, U16BIT angle, S32BIT *hx, S32BIT *hy)
3076 {
3077  U16BIT degrees;
3078  U16BIT quadrant; /* 0 to 3 */
3079  U16BIT tan_1_deg; /* where tan(x) = 1 */
3080  BOOLEAN swap;
3081  U32BIT numer, numer_factor;
3082  U32BIT denom, denom_factor;
3083  U32BIT tan_factor;
3084  U32BIT tangens;
3085  U32BIT xh, yh, temp;
3086  S32BIT tmp;
3087  BOOLEAN hdres;
3088  const U32BIT *tan_table_32;
3089 
3090  FUNCTION_START(GetHitPoints);
3091 
3092  /* Some explanations are required here, otherwise nothing makes much
3093  * sense.
3094  *
3095  * To find the hit points, we use the parametric equations:
3096  * x = a * cos(q) and y = b * sin(q), where 0 <= q < 2*pi
3097  *
3098  * We are trying to find q so that y = tan(t) * x (where t is the
3099  * given angle we want to find hit points for).
3100  *
3101  * This means (given the parametric equations above):
3102  * y = tan(t) * x
3103  * b * sin(q) = tan(t) * a * cos(q)
3104  *
3105  * So, tan(q) = a * tan(t) / b.
3106  *
3107  * In the first quadrant, q = arctan(a*tan(t)/b).
3108  *
3109  * Now we substitute in the parametric equations and get:
3110  * x = a * cos(arctan(a*tan(t)/b))
3111  * y = b * sin(arctan(a*tan(t)/b))
3112  *
3113  * Some trigonometry:
3114  * cos(p) = 1 / sec(p)
3115  * sec(p) = sqrt(1 + tan^2(p))
3116  * So:
3117  * cos(p) = 1 / sqrt(1 + tan^2(p))
3118  * So:
3119  * cos(arctan(p)) = 1 / sqrt(1 + tan^2(arctan(p)))
3120  * But:
3121  * tan(arctan(p)) = p (first quadrant)
3122  * So:
3123  * tan^2(arctan(p)) = p^2
3124  * And we have:
3125  * cos(arctan(p)) = 1 / sqrt(1 + p^2)
3126  *
3127  * In a similar fashion (left as an exercise to the reader):
3128  * sin(arctan(p)) = p / sqrt(1 + p^2)
3129  *
3130  * Now we substitute our enourmous expression for p and get (try it!):
3131  *
3132  * x = a / sqrt(1 + (a*tan(t)/b)^2)
3133  * y = a * tan(t) / sqrt(1 + (a*tan(t)/b)^2)
3134  *
3135  * And this explains what we're trying to calculate below. So we're down
3136  * to just using tan(t) and square root.
3137  *
3138  * Now, for HD, we have an additional complication:
3139  *
3140  * t_HD = arctan( (xres_SD * yres_HD) / (xres_HD * yres_SD) * tan(t_SD) )
3141  *
3142  * So:
3143  *
3144  * tan(t_HD) = tan(arctan(...)) =
3145  * (xres_SD * yres_HD) / (xres_HD * yres_SD) * tan(t_SD)
3146  *
3147  * In other words, tan(t_HD) = C * tan(t_SD), we don't need to change
3148  * anything in the calculation apart from multiplying the tan(x) by
3149  * a constant.
3150  *
3151  * Also, note that for HD the constant is always 45 / 64, because
3152  * x/y is always 16/9. So in the case of HD we use a different table
3153  * for tangens and get what we need.
3154  *
3155  * For 45 degress, we have different stories for SD and HD. For SD,
3156  * everything is simple. tan(t) = 1, so:
3157  *
3158  * x = a / sqrt(1 + (a*tan(t)/b)^2) = a / sqrt(1 + (a/b)^2)
3159  * = a / sqrt((b^2 + a^2) / b^2) = a * b / sqrt(a^2 + b^2)
3160  *
3161  * y = a * tan(t) / sqrt(1 + (a*tan(t)/b)^2) = x
3162  *
3163  * But for HD it's not so simple. 45 degrees is not a magic number
3164  * anymore, things have to change a bit. Reflection doesn't quite
3165  * work out of the box, because the C factor 45/64 becomes 64/45 when
3166  * we use reflection (this means a different tangens table), and the
3167  * magic degree for reflection is now 54.89... So we use a 55-value
3168  * table for degree < 55 and a 36-value table for degree >= 55.
3169  *
3170  * All in all, it seems to work.
3171  */
3172 
3173  if (mg_ctxt.out_osd_width == SD_WIDTH)
3174  {
3175  tan_table_32 = sd_tan_table_32;
3176  tan_1_deg = 45;
3177  hdres = FALSE;
3178  }
3179  else
3180  {
3181  tan_table_32 = hd_tan_table_32;
3182  tan_1_deg = 55;
3183  hdres = TRUE;
3184  }
3185 
3186  /* 0 <= angle < 23040 */
3187  degrees = (angle + 32) >> 6;
3188  quadrant = (degrees / 90) & 0x3;
3189  degrees %= 90;
3190 
3191  if (degrees == 45 && !hdres)
3192  {
3193  xh = rx * ry / GetSqrt(rx*rx + ry*ry);
3194  yh = xh; /* 45 degrees */
3195  }
3196  else
3197  {
3198  if (quadrant == 1 || quadrant == 3)
3199  {
3200  degrees = 90 - degrees;
3201  }
3202 
3203  if (degrees < tan_1_deg)
3204  {
3205  swap = FALSE;
3206  }
3207  else
3208  {
3209  /* For degrees > 45 we can reflect everything with respect to
3210  * the line y=x, so that degrees -> 90 - degrees and rx <-> ry.
3211  * Of course, we also have to swap the final result.
3212  */
3213  degrees = 90 - degrees;
3214  temp = rx;
3215  rx = ry;
3216  ry = temp;
3217  if (hdres)
3218  {
3219  /* Need to use a different table with the reciprocal of the
3220  * magic constant 45/64.
3221  */
3222  tan_table_32 = hd_tan_table_rev_32;
3223  }
3224  swap = TRUE;
3225  }
3226 
3227  /* denominator = sqrt((rx*tan(angle))^2 + ry^2) */
3228 
3229  /* Calculate denominator factor */
3230  denom_factor = GetLog2(rx * rx + ry * ry);
3231 
3232  /* For the square root, we must make sure that denom_factor is
3233  * even, otherwise we can't use GetSqrt()
3234  */
3235  denom_factor += (denom_factor & 1);
3236 
3237  /* tan factor is (32 - denom_factor) / 2, so that when we
3238  * multiply by tan(angle) we end up with 32 bits
3239  */
3240  tan_factor = (32 - denom_factor) >> 1;
3241 
3242  /* Calculate tan(angle) */
3243  tangens = (tan_table_32[degrees]) >> (32 - tan_factor);
3244 
3245  /* rx * rx is multiplied by tan * tan, and ry * ry must be
3246  * shifted accordingly so that the results can be added */
3247  denom = (((rx * rx) * (tangens * tangens)) +
3248  ((ry * ry) << (tan_factor << 1)));
3249 
3250  /* Square root halves the factor, and the tan factor */
3251  denom = GetSqrt(denom);
3252  denom_factor >>= 1;
3253 
3254  /* Calculate numerator for x-hit */
3255  numer = rx * ry;
3256  numer_factor = GetLog2(numer);
3257 
3258  /* Dividie numerator by denominator to get x-hit: to do that
3259  * we first make the numerator as large as possible, then
3260  * we adjust the denominator so that the result is a 16 bit integer
3261  */
3262  numer <<= (32 - numer_factor);
3263  if (denom_factor + tan_factor > 16)
3264  {
3265  denom >>= (denom_factor + tan_factor - 16);
3266  tan_factor = 16 - denom_factor;
3267  }
3268 
3269  xh = numer / denom;
3270  xh >>= (32 - numer_factor - tan_factor);
3271 
3272  /* Calculate tan(angle) for numerator */
3273  tangens = (tan_table_32[degrees]) >> numer_factor;
3274 
3275  /* Calculate numerator for y-hit (now it's 32 bits) */
3276  numer = rx * ry * tangens;
3277 
3278  /* Dividie numerator by denominator to get y-hit: the numerator
3279  * is already 32 bits, and the denominator has already been normalised
3280  */
3281  yh = numer / denom;
3282  yh >>= (32 - numer_factor - tan_factor);
3283 
3284  if (swap)
3285  {
3286  /* Everything is reflected, so we have to swap the result xh <-> yh */
3287  temp = xh;
3288  xh = yh;
3289  yh = temp;
3290  }
3291  }
3292 
3293  /* We must now consider the quadrant */
3294  switch (quadrant)
3295  {
3296  case 0:
3297  /* first quadrant: xh and yh are correct */
3298  *hx = xh;
3299  *hy = yh;
3300  break;
3301  case 1:
3302  /* second quadrant: xh should be negative */
3303  tmp = xh;
3304  *hx = -tmp;
3305  *hy = yh;
3306  break;
3307  case 2:
3308  /* third quadrant: both xh and yh should be negative */
3309  tmp = xh;
3310  *hx = -tmp;
3311  tmp = yh;
3312  *hy = -tmp;
3313  break;
3314  case 3:
3315  /* fourth quadrant: yh should be negative */
3316  *hx = xh;
3317  tmp = yh;
3318  *hy = -tmp;
3319  break;
3320  }
3321 
3322  /* Convert "logical" coordinate to "screen" coordinate */
3323  *hy = -*hy;
3324 
3325  FUNCTION_FINISH(GetHitPoints);
3326 }
3327 
3334 static void FillConvexPolygon(S_POINT_LIST_HEADER *vertex_list, DLAColor colour)
3335 {
3336  S32BIT i, min_index_l, max_index, min_index_r, skip_first, temp;
3337  S32BIT min_point_y, max_point_y, top_is_flat, left_edge_dir;
3338  S32BIT next_index, current_index, previous_index;
3339  S32BIT delta_x_n, delta_y_n, delta_x_p, delta_y_p;
3340  S_HLINE_LIST working_hline_list;
3341  S_HLINE *edge_point;
3342  S_POINT *vertex;
3343 
3344 #if DEBUG_DLA
3345  printf("FillConvexPolygon\n");
3346 #endif
3347 
3348  /* Point to the vertex list */
3349  vertex = vertex_list->point_list;
3350 
3351  /* Scan the list to find the top and bottom of the polygon */
3352  if (vertex_list->length == 0)
3353  return; /* reject null polygons */
3354  max_point_y = min_point_y = vertex[min_index_l = max_index = 0].y;
3355  for (i = 1; i < vertex_list->length; i++) {
3356  if (vertex[i].y < min_point_y)
3357  min_point_y = vertex[min_index_l = i].y; /* new top */
3358  else if (vertex[i].y > max_point_y)
3359  max_point_y = vertex[max_index = i].y; /* new bottom */
3360  }
3361  if (min_point_y == max_point_y)
3362  return; /* polygon is 0-height; avoid infinite loop below */
3363 
3364  /* Scan in ascending order to find the last top-edge point */
3365  min_index_r = min_index_l;
3366  while (vertex[min_index_r].y == min_point_y)
3367  INDEX_FORWARD(min_index_r);
3368  INDEX_BACKWARD(min_index_r); /* back up to last top-edge point */
3369 
3370  /* Now scan in descending order to find the first top-edge point */
3371  while (vertex[min_index_l].y == min_point_y)
3372  INDEX_BACKWARD(min_index_l);
3373  INDEX_FORWARD(min_index_l); /* back up to first top-edge point */
3374 
3375  /* Figure out which direction through the vertex list from the top
3376  vertex is the left edge and which is the right */
3377  left_edge_dir = -1; /* assume left edge runs down thru vertex list */
3378  if ((top_is_flat = (vertex[min_index_l].x !=
3379  vertex[min_index_r].x) ? 1 : 0) == 1) {
3380  /* If the top is flat, just see which of the ends is leftmost */
3381  if (vertex[min_index_l].x > vertex[min_index_r].x) {
3382  left_edge_dir = 1; /* left edge runs up through vertex list */
3383  temp = min_index_l; /* swap the indices so min_index_l */
3384  min_index_l = min_index_r; /* points to the start of the left */
3385  min_index_r = temp; /* edge, similarly for min_index_r */
3386  }
3387  } else {
3388  /* Point to the downward end of the first line of each of the
3389  two edges down from the top */
3390  next_index = min_index_r;
3391  INDEX_FORWARD(next_index);
3392  previous_index = min_index_l;
3393  INDEX_BACKWARD(previous_index);
3394  /* Calculate X and Y lengths from the top vertex to the end of
3395  the first line down each edge; use those to compare slopes
3396  and see which line is leftmost */
3397  delta_x_n = vertex[next_index].x - vertex[min_index_l].x;
3398  delta_y_n = vertex[next_index].y - vertex[min_index_l].y;
3399  delta_x_p = vertex[previous_index].x - vertex[min_index_l].x;
3400  delta_y_p = vertex[previous_index].y - vertex[min_index_l].y;
3401  if (((long)delta_x_n * delta_y_p - (long)delta_y_n * delta_x_p) < 0L) {
3402  left_edge_dir = 1; /* left edge runs up through vertex list */
3403  temp = min_index_l; /* swap the indices so min_index_l */
3404  min_index_l = min_index_r; /* points to the start of the left */
3405  min_index_r = temp; /* edge, similarly for min_index_r */
3406  }
3407  }
3408 
3409  /* Set the # of scan lines in the polygon, skipping the bottom edge
3410  and also skipping the top vertex if the top isn't flat because
3411  in that case the top vertex has a right edge component, and set
3412  the top scan line to draw, which is likewise the second line of
3413  the polygon unless the top is flat */
3414  if ((working_hline_list.length =
3415  max_point_y - min_point_y - 1 + top_is_flat) <= 0)
3416  return; /* there's nothing to draw, so we're done */
3417  working_hline_list.y_start = min_point_y + 1 - top_is_flat;
3418 
3419  /* Get memory in which to store the line list we generate */
3420  if ((working_hline_list.hline = OSD_MemAlloc(sizeof(S_HLINE) * working_hline_list.length)) == NULL)
3421  return; /* couldn't get memory for the line list */
3422 
3423  /* Scan the left edge and store the boundary points in the list */
3424  /* Initial pointer for storing scan converted left-edge coords */
3425  edge_point = working_hline_list.hline;
3426  /* Start from the top of the left edge */
3427  previous_index = current_index = min_index_l;
3428  /* Skip the first point of the first line unless the top is flat;
3429  if the top isn't flat, the top vertex is exactly on a right
3430  edge and isn't drawn */
3431  skip_first = top_is_flat ? 0 : 1;
3432  /* Scan convert each line in the left edge from top to bottom */
3433  do {
3434  INDEX_MOVE(current_index,left_edge_dir);
3435  ScanEdge(vertex[previous_index].x,
3436  vertex[previous_index].y,
3437  vertex[current_index].x,
3438  vertex[current_index].y, 1, skip_first, &edge_point);
3439  previous_index = current_index;
3440  skip_first = 0; /* scan convert the first point from now on */
3441  } while (current_index != max_index);
3442 
3443  /* Scan the right edge and store the boundary points in the list */
3444  edge_point = working_hline_list.hline;
3445  previous_index = current_index = min_index_r;
3446  skip_first = top_is_flat ? 0 : 1;
3447 
3448  /* Scan convert the right edge, top to bottom. X coordinates are
3449  adjusted 1 to the left, effectively causing scan conversion of
3450  the nearest points to the left of but not exactly on the edge */
3451  do {
3452  INDEX_MOVE(current_index,-left_edge_dir);
3453  ScanEdge(vertex[previous_index].x - 1,
3454  vertex[previous_index].y,
3455  vertex[current_index].x - 1,
3456  vertex[current_index].y, 0, skip_first, &edge_point);
3457  previous_index = current_index;
3458  skip_first = 0; /* scan convert the first point from now on */
3459  } while (current_index != max_index);
3460 
3461  /* Draw the line list representing the scan converted polygon */
3462  DrawHorizontalLineList(&working_hline_list, colour);
3463 
3464  /* Release the line list's memory and we're successfully done */
3465  OSD_MemFree(working_hline_list.hline);
3466  return;
3467 }
3468 
3480 static void ScanEdge(S32BIT x1, S32BIT y1, S32BIT x2, S32BIT y2,
3481  S32BIT set_x_start, S32BIT skip_first,
3482  S_HLINE **edge_point)
3483 {
3484  S32BIT y, delta_x, delta_y;
3485  S_HLINE *working_edge_point;
3486 
3487  FUNCTION_START(ScanEdge);
3488 
3489  /* Scan converts an edge from (X1,Y1) to (X2,Y2), not including the point at
3490  * (X2,Y2). This avoids overlapping the end of one line with the start of
3491  * the next, and causes the bottom scan line of the polygon not to be
3492  * drawn. If SkipFirst != 0, the point at (X1,Y1) isn't drawn. For each scan
3493  * line, the pixel closest to the scanned line without being to the left of
3494  * the scanned line is chosen.
3495  */
3496 
3497  /* Calculate X and Y lengths of the line and the inverse slope */
3498  delta_x = x2 - x1;
3499  delta_y = y2 - y1;
3500  if (delta_y > 0)
3501  {
3502  /* Store the X coordinate of the pixel closest to but not to the left of
3503  * the line for each Y coordinate between Y1 and Y2, not including Y2 and
3504  * also not including Y1 if SkipFirst != 0
3505  */
3506  working_edge_point = *edge_point;
3507  for (y = y1 + skip_first; y < y2; y++, working_edge_point++)
3508  {
3509  /* Store the X coordinate in the appropriate edge list */
3510  if (set_x_start == 1)
3511  {
3512  working_edge_point->x_start =
3513  x1 + ((y - y1) * delta_x + (delta_y >> 1)) / delta_y;
3514  }
3515  else
3516  {
3517  working_edge_point->x_end =
3518  x1 + ((y - y1) * delta_x + (delta_y >> 1)) / delta_y;
3519  }
3520  }
3521  *edge_point = working_edge_point; /* advance caller's ptr */
3522  }
3523 
3524  FUNCTION_FINISH(ScanEdge);
3525 }
3526 
3533 static void S64AssignS32(S_64_BIT *s64, S32BIT s32)
3534 {
3535  if (s32 < 0)
3536  {
3537  /* sign extend */
3538  s64->msw = 0xffffffff;
3539  }
3540  else
3541  {
3542  s64->msw = 0;
3543  }
3544  s64->lsw = (U32BIT)s32;
3545 }
3546 
3553 static void S64AddS32(S_64_BIT *s64, S32BIT s32)
3554 {
3555  /* a b c d
3556  * + e f
3557  */
3558  U32BIT t = (U32BIT)s32;
3559 
3560  s64->lsw += t;
3561 
3562  /* Add carry */
3563  s64->msw += (s64->lsw < t);
3564 
3565  if (s32 < 0)
3566  {
3567  /* Sign extend */
3568  --s64->msw;
3569  }
3570 }
3571 
3578 static void S64AddS64(S_64_BIT *s64_var, S_64_BIT *s64_value)
3579 {
3580  /* a b c d
3581  * + e f g h
3582  */
3583 
3584  s64_var->lsw += s64_value->lsw;
3585 
3586  /* add carry */
3587  s64_var->msw += (s64_var->lsw < s64_value->lsw);
3588 
3589  s64_var->msw += s64_value->msw;
3590 }
3591 
3598 static void S64SubtractS32(S_64_BIT *s64, S32BIT s32)
3599 {
3600  /* a b c d
3601  * - e f
3602  */
3603  U32BIT t = ~((U32BIT)s32) + 1; /* t = -s32 */
3604 
3605  s64->lsw += t;
3606 
3607  /* Add carry */
3608  s64->msw += (s64->lsw < t);
3609 
3610  if (s32 >= 0)
3611  {
3612  /* Sign extend */
3613  s64->msw += 0xffffffff;
3614  }
3615 }
3616 
3623 static void S64MultiplyS32(S_64_BIT *s64, S32BIT s32)
3624 {
3625  /* a b c d
3626  * x s s e f
3627  * -------
3628  * d f
3629  * c f
3630  * d e
3631  * b f
3632  * c e
3633  * d s
3634  * a f
3635  * b e
3636  * c s
3637  * d s
3638  */
3639  U32BIT a, b, c, d;
3640  U32BIT e, f, s;
3641  U32BIT x, xn, y, c1, c2;
3642  U32BIT lo, hi;
3643 
3644  if (s32 < 0)
3645  {
3646  /* sign extension */
3647  s = 0xffff;
3648  }
3649  else
3650  {
3651  s = 0x0000;
3652  }
3653 
3654  e = (s32 >> 16) & 0xffff;
3655  f = s32 & 0xffff;
3656 
3657  a = (s64->msw >> 16) & 0xffff;
3658  b = s64->msw & 0xffff;
3659  c = (s64->lsw >> 16) & 0xffff;
3660  d = s64->lsw & 0xffff;
3661 
3662  lo = d * f;
3663  x = c * f;
3664  xn = d * e;
3665  x += xn;
3666 
3667  /* first carry */
3668  c1 = (x < xn);
3669 
3670  y = ((lo >> 16) & 0xffff) + x;
3671 
3672  /* second carry */
3673  c2 = (y < x);
3674 
3675  lo = (lo & 0xffff) | ((y & 0xffff) << 16);
3676  hi = (y >> 16) & 0xffff;
3677 
3678  hi += b * f;
3679  hi += c * e;
3680  hi += ((a * f) & 0xffff) << 16;
3681  hi += ((b * e) & 0xffff) << 16;
3682 
3683  hi += c1 << 16; /* add first carry */
3684  hi += c2 << 16; /* add second carry */
3685 
3686  /* add sign-extention multiplication */
3687  hi += d * s;
3688  hi += ((c * s) & 0xffff) << 16;
3689  hi += ((d * s) & 0xffff) << 16;
3690 
3691  s64->lsw = lo;
3692  s64->msw = hi;
3693 }
3694 
3703 static S32BIT S64CompareS64(S_64_BIT *s64_a, S_64_BIT *s64_b)
3704 {
3705  S32BIT a, b, diff;
3706  U32BIT sign;
3707  U32BIT overflow;
3708  S32BIT result;
3709 
3710  a = (S32BIT)s64_a->msw;
3711  b = (S32BIT)s64_b->msw;
3712 
3713  diff = a - b;
3714  overflow = (((b > 0) && (diff > a)) || ((b < 0) && (diff < a)));
3715  sign = (diff < 0);
3716 
3717  if (a == b)
3718  {
3719  /* unsigned comparison for least significant word */
3720  if (s64_a->lsw < s64_b->lsw)
3721  {
3722  result = -1;
3723  }
3724  else if (s64_a->lsw == s64_b->lsw)
3725  {
3726  result = 0;
3727  }
3728  else
3729  {
3730  result = 1;
3731  }
3732  }
3733  else
3734  {
3735  if (sign ^ overflow)
3736  {
3737  /* a < b */
3738  result = -1;
3739  }
3740  else if (a == b)
3741  {
3742  /* a == b */
3743  result = 0;
3744  }
3745  else
3746  {
3747  /* a > b */
3748  result = 1;
3749  }
3750  }
3751 
3752  return result;
3753 }
3754 
3755 /*---global function definitions---------------------------------------------*/
3756 
3757 #ifndef VOYAGER_PORT_DEMO
3758 
3768 void DLA_FUNCTION(Line)( DLA_Surface* canvas, S16BIT x1, S16BIT y1,
3769  S16BIT x2, S16BIT y2, U16BIT width, DLAColor colour)
3770 {
3771  FUNCTION_START(DLA_PCX_Line);
3772 
3773  dla_canvas = canvas;
3774  DrawLine(x1, y1, x2, y2, width, colour);
3775 
3776  FUNCTION_FINISH(DLA_PCX_Line);
3777 }
3778 #endif /*VOYAGER_PORT_DEMO*/
3779 
3789 void DLA_FUNCTION(Polygon)( DLA_Surface* canvas, S_POLYGON poly,
3790  U16BIT width, DLAColor fill_colour, DLAColor line_colour )
3791 {
3792  S_POINT_LIST *cp;
3793 
3794  FUNCTION_START(DLA_PCX_Polygon);
3795 
3796  if (poly.point_list)
3797  {
3798  if (poly.num_points > 2)
3799  {
3800  dla_canvas = canvas;
3801  if ( FillPolygon(&poly, fill_colour) )
3802  {
3803  cp = poly.point_list;
3804  while (cp->next != NULL)
3805  {
3806  DrawLine(cp->point.x, cp->point.y, cp->next->point.x, cp->next->point.y,
3807  width, line_colour);
3808  cp = cp->next;
3809  if ( width > 1 )
3810  {
3811  FillCircle(cp->point.x, cp->point.y, width, line_colour);
3812  }
3813  }
3814  DrawLine( cp->point.x, cp->point.y,
3815  poly.point_list->point.x, poly.point_list->point.y, width, line_colour );
3816  if (width > 1)
3817  {
3818  FillCircle(poly.point_list->point.x, poly.point_list->point.y, width, line_colour);
3819  }
3820  FreePolygon(&poly);
3821  }
3822  }
3823  else
3824  {
3825  FreePolygon(&poly);
3826  }
3827  }
3828 
3829  FUNCTION_FINISH(DLA_PCX_Polygon);
3830 }
3831 
3840 void DLA_FUNCTION(Polyline)( DLA_Surface* canvas, S_POLYGON poly, U16BIT width, DLAColor colour )
3841 {
3842  S_POINT_LIST *cp;
3843 
3844  FUNCTION_START(DLA_PCX_Polyline);
3845 
3846  if (poly.point_list)
3847  {
3848  if (poly.num_points > 2)
3849  {
3850  dla_canvas = canvas;
3851  cp = poly.point_list;
3852  while (cp->next != NULL)
3853  {
3854  DrawLine( cp->point.x, cp->point.y, cp->next->point.x, cp->next->point.y,
3855  width, colour);
3856  cp = cp->next;
3857  if ( (width > 1) && (cp->next != NULL) )
3858  {
3859  FillCircle(cp->point.x, cp->point.y, width, colour);
3860  }
3861  }
3862  }
3863  FreePolygon(&poly);
3864  }
3865 
3866  FUNCTION_FINISH(DLA_PCX_Polyline);
3867 }
3868 
3869 #ifndef VOYAGER_PORT_DEMO
3870 
3883 void DLA_FUNCTION(Rectangle)( DLA_Surface* canvas, S16BIT x1, S16BIT y1,
3884  S16BIT x2, S16BIT y2, U16BIT x_lw, U16BIT y_lw,
3885  DLAColor fill_colour, DLAColor line_colour )
3886 {
3887  FUNCTION_START(DLA_PCX_Rectangle);
3888 
3889  if (x1 < x2 && y1 < y2)
3890  {
3891  dla_canvas = canvas;
3892  FillSimpleRectangle( x1, y1, x2, y2, fill_colour);
3893 
3894  DrawLine( x1, y1, x2, y1, y_lw, line_colour );
3895  DrawLine( x2, y1, x2, y2, x_lw, line_colour );
3896  DrawLine( x2, y2, x1, y2, y_lw, line_colour );
3897  DrawLine( x1, y2, x1, y1, x_lw, line_colour );
3898  if (y_lw > 1 && x_lw > 1)
3899  {
3900  if ( y_lw == x_lw )
3901  {
3902  FillCircle( x1, y1, x_lw, line_colour);
3903  FillCircle( x2, y1, x_lw, line_colour);
3904  FillCircle( x2, y2, x_lw, line_colour);
3905  FillCircle( x1, y2, x_lw, line_colour);
3906  }
3907  else
3908  {
3909  /* Find the top-left corners for ellipses */
3910  x1 -= x_lw >> 1;
3911  x2 -= x_lw >> 1;
3912  y1 -= y_lw >> 1;
3913  y2 -= y_lw >> 1;
3914  /* and then draw them */
3915  FillEllipse( x1, y1, x_lw, y_lw, line_colour);
3916  FillEllipse( x2, y1, x_lw, y_lw, line_colour);
3917  FillEllipse( x2, y2, x_lw, y_lw, line_colour);
3918  FillEllipse( x1, y2, x_lw, y_lw, line_colour);
3919  }
3920  }
3921  }
3922 
3923  FUNCTION_FINISH(DLA_PCX_Rectangle);
3924 }
3925 
3937 void DLA_FUNCTION(Ellipse)( DLA_Surface* canvas, S16BIT x, S16BIT y,
3938  U16BIT w, U16BIT h, U16BIT width, DLAColor fill_colour, DLAColor line_colour)
3939 {
3940  FUNCTION_START(DLA_PCX_Ellipse);
3941 
3942  if (w > 1 && h > 1 && h+w > 4)
3943  {
3944  dla_canvas = canvas;
3945  FillEllipse(x, y, w, h, fill_colour);
3946  DrawEllipse(x, y, w, h, width, line_colour);
3947  }
3948 
3949  FUNCTION_FINISH(DLA_PCX_Ellipse);
3950 }
3951 
3964 void DLA_FUNCTION(Arc)( DLA_Surface* canvas, S16BIT x, S16BIT y,
3965  U16BIT w, U16BIT h, U16BIT start, U16BIT arc, U16BIT width, DLAColor colour)
3966 {
3967  FUNCTION_START(DLA_PCX_Arc);
3968 
3969  if (start < 23040 && arc != 0 && arc < 23040 && w > 0 && h > 0)
3970  {
3971  dla_canvas = canvas;
3972  DrawArc(x, y, w, h, start, arc, width, colour);
3973  }
3974 
3975  FUNCTION_FINISH(DLA_PCX_Arc);
3976 }
3977 
3992 void DLA_FUNCTION(Sector)( DLA_Surface* canvas, S16BIT x, S16BIT y, U16BIT w, U16BIT h,
3993  U16BIT start, U16BIT arc, U16BIT width, DLAColor fill_colour, DLAColor line_colour)
3994 {
3995  FUNCTION_START(DLA_PCX_Sector);
3996 
3997  if (start < 23040 && arc != 0 && arc < 23040 && w > 0 && h > 0)
3998  {
3999  if (w < 5)
4000  {
4001  /* Approximate as a rectangle (line+border) */
4002  /* TODO: find real hit-points */
4003  DLA_FUNCTION(Rectangle)(canvas, x, y, x+w, y+h, width, width, fill_colour, line_colour);
4004  }
4005  else if (h < 4)
4006  {
4007  /* Approximate as a line (line+border) */
4008  /* TODO: find real hit-points */
4009  DLA_FUNCTION(Rectangle)(canvas, x, y, x+w, y+h, width, width, fill_colour, line_colour);
4010  }
4011  else
4012  {
4013  dla_canvas = canvas;
4014  DrawSector(x, y, w, h, start, arc, width,
4015  fill_colour, line_colour);
4016  }
4017  }
4018 
4019  FUNCTION_FINISH(DLA_PCX_Sector);
4020 }
4021 #endif /*VOYAGER_PORT_DEMO*/
4022 
4032 void DLA_FUNCTION(Border)( DLA_Surface* canvas, U16BIT x1_bw, U16BIT y1_bw,
4033  U16BIT x2_bw, U16BIT y2_bw, DLAColor line_colour)
4034 {
4035  FUNCTION_START(DLA_PCX_Border);
4036 
4037  dla_canvas = canvas;
4038  if (x1_bw == 1)
4039  {
4040  DrawThinLine(0, 0, 0, dla_canvas->height-1, line_colour);
4041  }
4042  else if (x1_bw > 1)
4043  {
4044  FillSimpleRectangle(0, 0, x1_bw, dla_canvas->height, line_colour);
4045  }
4046  if (x2_bw == 1)
4047  {
4048  DrawThinLine(dla_canvas->width-1, 0, dla_canvas->width-1, dla_canvas->height-1, line_colour);
4049  }
4050  else if (x2_bw > 1)
4051  {
4052  FillSimpleRectangle(dla_canvas->width-x2_bw, 0, dla_canvas->width, dla_canvas->height, line_colour);
4053  }
4054  if (y1_bw == 1)
4055  {
4056  DrawThinLine(0, 0, dla_canvas->width-1, 0, line_colour);
4057  }
4058  else if (y1_bw > 1)
4059  {
4060  FillSimpleRectangle(0, 0, dla_canvas->width, y1_bw, line_colour);
4061  }
4062  if (y2_bw == 1)
4063  {
4064  DrawThinLine(0, dla_canvas->height-1, dla_canvas->width-1, dla_canvas->height-1, line_colour);
4065  }
4066  else if (y2_bw > 1)
4067  {
4068  FillSimpleRectangle(0, dla_canvas->height-y2_bw, dla_canvas->width, dla_canvas->height, line_colour);
4069  }
4070 
4071  FUNCTION_FINISH(DLA_PCX_Border);
4072 }
4073 
SGN
#define SGN(x)
Definition: mg_dla.inl:47
_MGContext::out_osd_width
U16BIT out_osd_width
Definition: mg_ctxt.h:81
S_POINT_LIST_HEADER
struct point_list_header S_POINT_LIST_HEADER
S_64_BIT::lsw
U32BIT lsw
Definition: mg_dla.inl:96
point_list::point
S_POINT point
Definition: dla_inl.h:42
FUNCTION_FINISH
#define FUNCTION_FINISH(name)
Definition: glue_debug.h:143
DLA_struct
Definition: dla_inl.h:58
INDEX_MOVE
#define INDEX_MOVE(index, direction)
Definition: mg_dla.inl:66
DLA_struct::height
U16BIT height
Definition: dla_inl.h:61
OSD_MemAlloc
#define OSD_MemAlloc
Definition: glue_memory.h:96
mg_api.h
Polyline
void DLA_FUNCTION() Polyline(DLA_Surface *canvas, S_POLYGON poly, U16BIT width, DLAColor colour)
Draw a polyline (sequence of connected lines) on the canvas.
Definition: mg_dla.inl:3840
MIN
#define MIN(a, b)
Definition: mg_dla.inl:48
_point::x
S16BIT x
Definition: dla_inl.h:35
glue_debug.h
Debug tracing.
ABS
#define ABS(x)
Definition: mg_dla.inl:46
hline::x_start
U16BIT x_start
Definition: mg_dla.inl:83
S_HLINE
struct hline S_HLINE
_point
Definition: dla_inl.h:33
point_list_header
Definition: mg_dla.inl:77
point_list::next
struct point_list * next
Definition: dla_inl.h:41
_point::y
S16BIT y
Definition: dla_inl.h:36
dla_inl.h
MHEG-5 Graphics: Dynamic Line-Art utility functions.
S_64_BIT
Definition: mg_dla.inl:93
Ellipse
void DLA_FUNCTION() Ellipse(DLA_Surface *canvas, S16BIT x, S16BIT y, U16BIT w, U16BIT h, U16BIT width, DLAColor fill_colour, DLAColor line_colour)
Draw an ellipse ("oval") on the canvas.
Definition: mg_dla.inl:3937
S16BIT
int16_t S16BIT
Definition: techtype.h:85
UL
#define UL
Definition: vpa1_tgs.h:335
mh5assert.h
redirection include
point_list
Definition: dla_inl.h:39
Arc
void DLA_FUNCTION() Arc(DLA_Surface *canvas, S16BIT x, S16BIT y, U16BIT w, U16BIT h, U16BIT start, U16BIT arc, U16BIT width, DLAColor colour)
Draw an arc on the canvas.
Definition: mg_dla.inl:3964
polygon::point_list
S_POINT_LIST * point_list
Definition: dla_inl.h:47
glue_memory.h
Memory functions.
Polygon
void DLA_FUNCTION() Polygon(DLA_Surface *canvas, S_POLYGON poly, U16BIT width, DLAColor fill_colour, DLAColor line_colour)
Draw a polygon on the canvas.
Definition: mg_dla.inl:3789
Rectangle
void DLA_FUNCTION() Rectangle(DLA_Surface *canvas, S16BIT x1, S16BIT y1, S16BIT x2, S16BIT y2, U16BIT x_lw, U16BIT y_lw, DLAColor fill_colour, DLAColor line_colour)
Draw a rectangle on the canvas.
Definition: mg_dla.inl:3883
hline_list::length
U16BIT length
Definition: mg_dla.inl:88
INDEX_BACKWARD
#define INDEX_BACKWARD(index)
Definition: mg_dla.inl:60
mg_ctxt
S_MGContext mg_ctxt
Definition: mg_osd.c:144
mg_osd.h
Interface to OSD.
polygon::num_points
U16BIT num_points
Definition: dla_inl.h:48
S_HLINE_LIST
struct hline_list S_HLINE_LIST
hline
Definition: mg_dla.inl:82
DLA_struct::bf_stride
U32BIT bf_stride
Definition: dla_inl.h:64
Line
void DLA_FUNCTION() Line(DLA_Surface *canvas, S16BIT x1, S16BIT y1, S16BIT x2, S16BIT y2, U16BIT width, DLAColor colour)
Draw a line on the canvas.
Definition: mg_dla.inl:3768
point_list_header::point_list
S_POINT * point_list
Definition: mg_dla.inl:79
MAX
#define MAX(a, b)
Definition: mg_dla.inl:49
S32BIT
int32_t S32BIT
Definition: techtype.h:87
hline_list::hline
S_HLINE * hline
Definition: mg_dla.inl:90
S_64_BIT::msw
U32BIT msw
Definition: mg_dla.inl:95
U16BIT
uint16_t U16BIT
Definition: techtype.h:84
Border
void DLA_FUNCTION() Border(DLA_Surface *canvas, U16BIT x1_bw, U16BIT y1_bw, U16BIT x2_bw, U16BIT y2_bw, DLAColor line_colour)
Draw a border around the canvas.
Definition: mg_dla.inl:4032
point_list_header::length
U16BIT length
Definition: mg_dla.inl:78
buffer
Definition: mg_png.c:52
INDEX_FORWARD
#define INDEX_FORWARD(index)
Definition: mg_dla.inl:54
FALSE
#define FALSE
Definition: techtype.h:68
SD_WIDTH
#define SD_WIDTH
Definition: osdtype.h:31
hline_list::y_start
S32BIT y_start
Definition: mg_dla.inl:89
DLA_struct::width
U16BIT width
Definition: dla_inl.h:60
DLA_struct::cols
DLAColor * cols
Definition: dla_inl.h:62
BOOLEAN
U8BIT BOOLEAN
Definition: techtype.h:99
TRUE
#define TRUE
Definition: techtype.h:69
Sector
void DLA_FUNCTION() Sector(DLA_Surface *canvas, S16BIT x, S16BIT y, U16BIT w, U16BIT h, U16BIT start, U16BIT arc, U16BIT width, DLAColor fill_colour, DLAColor line_colour)
Draw a sector ("pie slice") on the canvas.
Definition: mg_dla.inl:3992
hline::x_end
U16BIT x_end
Definition: mg_dla.inl:84
FUNCTION_START
#define FUNCTION_START(name)
Definition: glue_debug.h:142
OSD_MemFree
#define OSD_MemFree
Definition: glue_memory.h:97
hline_list
Definition: mg_dla.inl:87
U32BIT
uint32_t U32BIT
Definition: techtype.h:86
Generated by   doxygen 1.8.11