1 /*
2  * Copyright (c) 1998 by The XFree86 Project, Inc.
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a
5  * copy of this software and associated documentation files (the "Software"),
6  * to deal in the Software without restriction, including without limitation
7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8  * and/or sell copies of the Software, and to permit persons to whom the
9  * Software is furnished to do so, subject to the following conditions:
10  *
11  * The above copyright notice and this permission notice shall be included in
12  * all copies or substantial portions of the Software.
13  *
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
17  * THE XFREE86 PROJECT BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
18  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
19  * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20  * SOFTWARE.
21  *
22  * Except as contained in this notice, the name of the XFree86 Project shall
23  * not be used in advertising or otherwise to promote the sale, use or other
24  * dealings in this Software without prior written authorization from the
25  * XFree86 Project.
26  */
27 
28 #ifdef HAVE_CONFIG_H
29 #include <config.h>
30 #endif
31 #include <stdlib.h>
32 
33 #include <X11/IntrinsicP.h>
34 #include <X11/Xmu/Xmu.h>
35 
36 #define XmuMax(a, b)	((a) > (b) ? (a) : (b))
37 #define XmuMin(a, b)	((a) < (b) ? (a) : (b))
38 
39 /*
40  * Function:
41  *	XmuNewArea
42  *
43  * Parameters:
44  *	x1 - Coordinates of the rectangle
45  *	y1 - ""
46  *	x2 - ""
47  *	y2 - ""
48  *
49  * Description:
50  *	Creates a new rectangular clipping area
51  */
52 XmuArea *
XmuNewArea(int x1,int y1,int x2,int y2)53 XmuNewArea(int x1, int y1, int x2, int y2)
54 {
55   XmuArea *area;
56 
57   area = (XmuArea *)XtMalloc(sizeof(XmuArea));
58   if (x2 > x1 && y2 > y1)
59     {
60       area->scanline = XmuNewScanline(y1, x1, x2);
61       area->scanline->next = XmuNewScanline(y2, 0, 0);
62     }
63   else
64     area->scanline = (XmuScanline *)NULL;
65 
66   return (area);
67 }
68 
69 /*
70  * Function:
71  *	XmuAreaDup
72  *
73  * Parameters:
74  *	area - Area to copy
75  *
76  * Description:
77  *	Returns a copy of its argument
78  */
79 XmuArea *
XmuAreaDup(XmuArea * area)80 XmuAreaDup(XmuArea *area)
81 {
82   XmuArea *dst;
83 
84   if (!area)
85     return ((XmuArea *)NULL);
86 
87   dst = XmuCreateArea();
88   XmuAreaCopy(dst, area);
89   return (dst);
90 }
91 
92 /*
93  * Function:
94  *	XmuAreaCopy
95  *
96  * Parameters:
97  *	dst - destination area
98  *	src - source area
99  *
100  * Description:
101  *	Minimizes memory alocation, trying to use already alocated memory
102  *	in dst, freeing what is not required anymore.
103  */
104 XmuArea *
XmuAreaCopy(XmuArea * dst,XmuArea * src)105 XmuAreaCopy(XmuArea *dst, XmuArea *src)
106 {
107   XmuScanline *z, *p, *Z;
108 
109   if (!dst || !src || dst == src)
110     return (dst);
111 
112   z = p = dst->scanline;
113   Z = src->scanline;
114 
115   /*CONSTCOND*/
116   while (1)
117     {
118       if (!Z)
119 	{
120 	  if (z == dst->scanline)
121 	    {
122 	      XmuDestroyScanlineList(dst->scanline);
123 	      dst->scanline = (XmuScanline *)NULL;
124 	    }
125 	  else
126 	    {
127 	      XmuDestroyScanlineList(p->next);
128 	      p->next = (XmuScanline *)NULL;
129 	    }
130 	  return (dst);
131 	}
132       if (z)
133 	{
134 	  XmuScanlineCopy(z, Z);
135 	  z->y = Z->y;
136 	}
137       else
138 	{
139 	  z = XmuNewScanline(Z->y, 0, 0);
140 	  XmuScanlineCopy(z, Z);
141 	  if (p == dst->scanline && !dst->scanline)
142 	    p = dst->scanline = z;
143 	  else
144 	    p->next = z;
145 	}
146       p = z;
147       z = z->next;
148       Z = Z->next;
149     }
150 
151   return (dst);
152 }
153 
154 /*
155  * Function:
156  *   XmuAreaNot
157  *
158  * Parameters:
159  *	area - area to operate
160  *	x1   - retangle to clip the result against
161  *	y1   - ""
162  *	x2   - ""
163  *	y2   - ""
164  *
165  * Description:
166  * (Input)
167  * (x1, y1)                                                (x2, y1)
168  *                   +-------------+
169  *      +------------+             +----+
170  *      |                +--------------+
171  *      +----------------+
172  * (x1, y2)                                                (x2, y2)
173  *
174  * (Output)
175  * (x1, y1)                                                (x2, y1)
176  *    +--------------+             +--------------------------+
177  *    | +------------+             +----+                     |
178  *    | |                +--------------+                     |
179  *    +-+                +------------------------------------+
180  * (x1, y2)                                                (x2, y2)
181  */
182 XmuArea *
XmuAreaNot(XmuArea * area,int x1,int y1,int x2,int y2)183 XmuAreaNot(XmuArea *area, int x1, int y1, int x2, int y2)
184 {
185   XmuScanline *z;
186   XmuArea *and;
187 
188   if (!area)
189     return (area);
190 
191   if (x1 > x2)
192     {
193       x1 ^= x2; x2 ^= x1; x1 ^= x2;
194     }
195     if (y1 > y2)
196       {
197 	y1 ^= y2; y2 ^= y1; y1 ^= y2;
198       }
199     if (!area->scanline)
200       {
201 	if ((area->scanline = XmuNewScanline(y1, x1, x2)) != NULL)
202 	  area->scanline->next = XmuNewScanline(y2, 0, 0);
203 	return (area);
204       }
205     and = XmuNewArea(x1, y1, x2, y2);
206     XmuAreaAnd(area, and);
207     XmuDestroyArea(and);
208     z = area->scanline;
209     if (z->y != y1)
210       {
211 	XmuScanline *q = XmuNewScanline(y1, x1, x2);
212 	q->next = z;
213 	area->scanline = q;
214       }
215     else
216       {
217 	area->scanline = area->scanline->next;
218 	XmuDestroyScanline(z);
219 	XmuOptimizeArea(area);
220 	if((z = area->scanline) == (XmuScanline *)NULL)
221 	  return (area);
222       }
223 
224     /* CONSTCOND */
225     while (1)
226       {
227 	XmuScanlineNot(z, x1, x2);
228 	if (!z->next)
229 	  {
230 	    z->next = XmuNewScanline(y2, 0, 0);
231 	    break;
232 	  }
233 	if (z->next->y == y2)
234 	  {
235 	    XmuDestroyScanlineList(z->next);
236 	    z->next = XmuNewScanline(y2, 0, 0);
237 	    break;
238 	  }
239 	z = z->next;
240       }
241 
242     return (area);
243 }
244 
245 /*
246  * Function:
247  *	XmuAreaOrXor
248  *
249  * Parameters:
250  *	dst - destination area
251  *	src - source area
252  *	or  - or operation if true, else xor operation
253  *
254  * Description:
255  *	Executes Or (Union) or Xor (Reverse intesection) of the areas
256  */
257 XmuArea *
XmuAreaOrXor(XmuArea * dst,XmuArea * src,Bool or)258 XmuAreaOrXor(XmuArea *dst, XmuArea *src, Bool or)
259 {
260   XmuScanline *z, *p, *Z, *P, *ins, *top;
261 
262   if (!dst || !src)
263     return (dst);
264 
265   if (dst == src)
266     {
267       if (or)
268 	return (dst);
269       XmuDestroyScanlineList(dst->scanline);
270       dst->scanline = (XmuScanline *)NULL;
271       return (dst);
272     }
273   if (!XmuValidArea(src))
274     return (dst);
275   if (!XmuValidArea(dst))
276     {
277       XmuAreaCopy(dst, src);
278       return (dst);
279     }
280 
281   p = z = dst->scanline;
282   P = Z = src->scanline;
283   ins = XmuNewScanline(dst->scanline->y, 0, 0);
284   top = XmuNewScanline(dst->scanline->y, 0, 0);
285   XmuScanlineCopy(ins, dst->scanline);
286   XmuScanlineCopy(top, dst->scanline);
287 
288   /*CONSTCOND*/
289   while (1)
290     {
291       if (!Z)
292 	break;
293       else if (Z->y < z->y)
294 	{
295 	  XmuScanline  *q = XmuNewScanline(Z->y, 0, 0);
296 	  XmuScanlineCopy(q, Z);
297 
298 	  if (z == dst->scanline)
299 	    {
300 	      dst->scanline = p = q;
301 	      q->next = z;
302             }
303 	  else
304 	    {
305 	      p->next = q;
306 	      q->next = z;
307 	      if (Z->y >= p->y)
308 		{
309 		  if (ins->y >= top->y
310 		      && (p->y != P->y || !XmuScanlineEqu(p, P)
311 			  || (ins->y <= P->y && !XmuScanlineEqu(ins, P))))
312 		    {
313 		      if (or)
314 			XmuScanlineOr(q, ins);
315 		      else
316 			XmuScanlineXor(q, ins);
317                     }
318 		  else if (Z->y >= top->y
319 			   && (top->y == p->y || top->y > ins->y
320 			       || !XmuValidScanline(Z)
321 			       || (p->y == P->y && XmuValidScanline(p)
322 				   && XmuValidScanline(P))
323 			       || XmuScanlineEqu(ins, top)))
324 		    {
325 		      if (or)
326 			XmuScanlineOr(q, top);
327 		      else
328 			XmuScanlineXor(q, top);
329 		    }
330 		  if (ins->y != p->y && p->y != P->y)
331 		    {
332 		      XmuScanlineCopy(ins, p);
333 		      ins->y = p->y;
334 		    }
335 		}
336 	      if (!XmuValidScanline(p) || Z->y <= p->y)
337 		{
338 		  XmuScanlineCopy(top, p);
339 		  top->y = p->y;
340                 }
341 	      p = q;
342 	    }
343 	  P = Z;
344 	  Z = Z->next;
345 	  continue;
346         }
347       else if (Z->y == z->y)
348 	{
349 	  if (top->y != z->y)
350 	    {
351 	      XmuScanlineCopy(top, z);
352 	      top->y = z->y;
353 	    }
354 	  if (or)
355 	    XmuScanlineOr(z, Z);
356 	  else
357 	    XmuScanlineXor(z, Z);
358 	  P = Z;
359 	  Z = Z->next;
360 	}
361       else if (P != Z)		/* && Z->y > z->y */
362 	{
363 	  if (top->y == ins->y && top->y != z->y)
364 	    {
365 	      XmuScanlineCopy(top, z);
366 	      top->y = z->y;
367 	    }
368 	  if (ins->y != z->y)
369 	    {
370 	      XmuScanlineCopy(ins, z);
371 	      ins->y = z->y;
372 	    }
373 	  if (or)
374 	    XmuScanlineOr(z, P);
375 	  else
376 	    XmuScanlineXor(z, P);
377 	}
378       else if (ins->y != z->y)
379 	{
380 	  XmuScanlineCopy(ins, z);
381 	  ins->y = z->y;
382 	}
383       p = z;
384       z = z->next;
385       if (!z)
386 	{
387 	  while (Z)
388 	    {
389 	      p->next = XmuNewScanline(Z->y, 0, 0);
390 	      XmuScanlineCopy(p->next, Z);
391 	      p = p->next;
392 	      Z = Z->next;
393 	    }
394 	  break;
395 	}
396       else if (ins->y > top->y && !XmuValidScanline(z)
397 	       && XmuValidScanline(ins))
398 	{
399 	  XmuScanlineCopy(top, ins);
400 	  top->y = ins->y;
401 	}
402     }
403   XmuOptimizeArea(dst);
404   XmuDestroyScanline(ins);
405   XmuDestroyScanline(top);
406 
407   return (dst);
408 }
409 
410 /*
411  * Function:
412  *	XmuAreaAnd(dst, src)
413  *
414  * Parameters:
415  *	dst - destination area
416  *	src - source area
417  *
418  * Description:
419  *	Executes And (intersection) of the areas
420  */
421 XmuArea *
XmuAreaAnd(XmuArea * dst,XmuArea * src)422 XmuAreaAnd(XmuArea *dst, XmuArea *src)
423 {
424   XmuScanline *z, *p, *Z, *P, *top;
425 
426   if (!dst || !src || dst == src)
427     return (dst);
428   if (!XmuValidArea(dst) || !XmuValidArea(src))
429     {
430       XmuDestroyScanlineList(dst->scanline);
431       dst->scanline = (XmuScanline *)NULL;
432       return (dst);
433     }
434   z = p = dst->scanline;
435   Z = P = src->scanline;
436   top = XmuNewScanline(dst->scanline->y, 0, 0);
437   XmuScanlineCopy(top, dst->scanline);
438 
439   while (z)
440     {
441       while (Z->next && Z->next->y < z->y)
442 	{
443 	  P = Z;
444 	  Z = Z->next;
445 	  if (Z->y >= p->y)
446 	    {
447 	      XmuScanline *q = XmuNewScanline(Z->y, 0, 0);
448 	      XmuScanlineCopy(q, Z);
449 
450 	      XmuScanlineAnd(q, top);
451 	      if (p->y != P->y)
452 		{
453 		  XmuScanlineAnd(p, P);
454 		  p->y = XmuMax(p->y, P->y);
455 		}
456 	      p->next = q;
457 	      q->next = z;
458 	      p = q;
459 	    }
460 	}
461       if (!z->next)
462 	{
463 	  z->y = XmuMax(z->y, Z->y);
464 	  break;
465         }
466       while (Z->y >= z->next->y)
467 	{
468 	  if (z == dst->scanline)
469 	    {
470 	      p = dst->scanline = dst->scanline->next;
471 	      XmuDestroyScanline(z);
472 	      z = dst->scanline;
473 	    }
474 	  else
475 	    {
476 	      p->next = z->next;
477 	      XmuDestroyScanline(z);
478 	      z = p;
479 	    }
480 	  if (!z || !z->next)
481 	    {
482 	      XmuOptimizeArea(dst);
483 	      XmuDestroyScanline(top);
484 
485 	      return (dst);
486 	    }
487 	}
488       if (Z->y > p->y)
489 	z->y = XmuMax(z->y, Z->y);
490       if (top->y != z->y)
491 	{
492 	  XmuScanlineCopy(top, z);
493 	  top->y = z->y;
494 	}
495       XmuScanlineAnd(z, Z);
496       p = z;
497       z = z->next;
498     }
499   XmuOptimizeArea(dst);
500   XmuDestroyScanline(top);
501 
502   return (dst);
503 }
504 
505 /*
506  * Function:
507  *   XmuValidArea(area)
508  *
509  * Parameters:
510  *	area - area to verify
511  *
512  * Description:
513  *	Verifies if the area is valid and/or useful
514  */
515 Bool
XmuValidArea(XmuArea * area)516 XmuValidArea(XmuArea *area)
517 {
518   XmuScanline *at;
519 
520   if (!area || !area->scanline)
521     return (False);
522 
523   at = area->scanline;
524   while (at)
525     {
526       if (XmuValidScanline(at))
527 	return (True);
528       at = at->next;
529     }
530 
531   return (False);
532 }
533 
534 /*
535  * Function:
536  *	XmuValidScanline
537  *
538  * Parameters:
539  *	scanline - scanline to verify
540  *
541  * Description:
542  *	Verifies if a scanline is useful
543  */
544 Bool
XmuValidScanline(XmuScanline * scanline)545 XmuValidScanline(XmuScanline *scanline)
546 {
547   XmuSegment *z;
548 
549   if (!scanline)
550     return (False);
551 
552   z = scanline->segment;
553   while (z)
554     {
555       if (XmuValidSegment(z))
556 	return (True);
557       z = z->next;
558     }
559 
560   return (False);
561 }
562 
563 /*
564  * Function:
565  *   XmuScanlineEqu
566  *
567  * Parameters:
568  *	s1 - scanline 1
569  *	s2 - scanline 2
570  *
571  * Description:
572  *	Checks if s1 and s2 are equal
573  */
574 Bool
XmuScanlineEqu(XmuScanline * s1,XmuScanline * s2)575 XmuScanlineEqu(XmuScanline *s1, XmuScanline *s2)
576 {
577   XmuSegment *z, *Z;
578 
579   if ((!s1 && !s2) || s1 == s2)
580     return (True);
581   if (!s1 || !s2)
582     return (False);
583 
584   z = s1->segment;
585   Z = s2->segment;
586 
587   /*CONSTCOND*/
588   while (1)
589     {
590       if (!z && !Z)
591 	return (True);
592       if (!z || !Z)
593 	return (False);
594       if (!XmuSegmentEqu(z, Z))
595 	return (False);
596       z = z->next;
597       Z = Z->next;
598     }
599   /*NOTREACHED*/
600 }
601 
602 /*
603  * Function:
604  *	XmuNewSegment
605  *
606  * Parameters:
607  *	x1 - coordinates of the segment
608  *	x2 - ""
609  *
610  * Description:
611  *	Creates a new segments with the coordinates x1 and x2
612  *
613  * Returns:
614  *	New Segment of NULL
615  */
616 XmuSegment *
XmuNewSegment(int x1,int x2)617 XmuNewSegment(int x1, int x2)
618 {
619   XmuSegment *segment;
620 
621   if ((segment = (XmuSegment *)XtMalloc(sizeof(XmuSegment))) == NULL)
622     return (segment);
623 
624   segment->x1 = x1;
625   segment->x2 = x2;
626   segment->next = (XmuSegment *)NULL;
627 
628   return (segment);
629 }
630 
631 /*
632  * Function:
633  *	XmuDestroySegmentList
634  *
635  * Parameters:
636  *	segment - Segment to destroy
637  *
638  * Description:
639  *	Frees the memory used by the list headed by segment
640  */
641 void
XmuDestroySegmentList(XmuSegment * segment)642 XmuDestroySegmentList(XmuSegment *segment)
643 {
644   XmuSegment *z;
645 
646   if (!segment)
647     return;
648 
649   while (segment)
650     {
651       z = segment;
652       segment = segment->next;
653       XmuDestroySegment(z);
654     }
655 }
656 
657 /*
658  * Function:
659  *	XmuScanlineCopy
660  *
661  * Parameters:
662  *	dst - destination scanline
663  *	src - source scanline
664  *
665  * Description:
666  *	Makes dst contain the same data as src
667  */
668 XmuScanline *
XmuScanlineCopy(XmuScanline * dst,XmuScanline * src)669 XmuScanlineCopy(XmuScanline *dst, XmuScanline *src)
670 {
671   XmuSegment *z, *p, *Z;
672 
673   if (!dst || !src || dst == src)
674     return (dst);
675 
676   z = p = dst->segment;
677   Z = src->segment;
678 
679   /*CONSTCOND*/
680   while (1)
681     {
682       if (!Z)
683 	{
684 	  if (z == dst->segment)
685 	    dst->segment = (XmuSegment *)NULL;
686 	  else
687 	    p->next = (XmuSegment *)NULL;
688 	  XmuDestroySegmentList(z);
689 	  return (dst);
690 	}
691       if (z)
692 	{
693 	  z->x1 = Z->x1;
694 	  z->x2 = Z->x2;
695 	}
696       else
697 	{
698 	  z = XmuNewSegment(Z->x1, Z->x2);
699 	  if (p == dst->segment && !dst->segment)
700 	    p = dst->segment = z;
701 	  else
702 	    p->next = z;
703 	}
704       p = z;
705       z = z->next;
706       Z = Z->next;
707     }
708   /*NOTREACHED*/
709 }
710 
711 /*
712  * Function:
713  *	XmuAppendSegment
714  *
715  * Parameters:
716  *	segment - destination segment
717  *	append  - segment to add
718  *
719  * Description:
720  *	Adds a copy of the append list at the end of the segment list
721  */
722 Bool
XmuAppendSegment(XmuSegment * segment,XmuSegment * append)723 XmuAppendSegment(XmuSegment *segment, XmuSegment *append)
724 {
725   if (!segment || !append)
726     return (False);
727 
728   if (segment->next)
729     /* Should not happen! */
730     XmuDestroySegmentList(segment->next);
731 
732   while (append)
733     {
734       if (XmuValidSegment(append))
735 	{
736 	  if ((segment->next = XmuNewSegment(append->x1, append->x2)) == NULL)
737 	    return (False);
738 	  segment = segment->next;
739 	}
740       append = append->next;
741     }
742 
743   return (True);
744 }
745 
746 /*
747  * Function:
748  *	XmuOptimizeScanline
749  *
750  * Parameters:
751  *	scanline - scanline to optimize
752  *
753  * Description:
754  *	  Some functions, when transforming Segments of Scanlines, left these
755  *	with unnecessary data (that may cause error in these same functions).
756  *	  This function corrects these incorrect segments.
757  */
758 XmuScanline *
XmuOptimizeScanline(XmuScanline * scanline)759 XmuOptimizeScanline(XmuScanline *scanline)
760 {
761   XmuSegment *z, *p;
762 
763   while (scanline->segment && !XmuValidSegment(scanline->segment))
764     {
765       XmuSegment *s = scanline->segment;
766 
767       scanline->segment = scanline->segment->next;
768       XmuDestroySegment(s);
769     }
770   for (z = p = scanline->segment; z; p = z, z = z->next)
771     {
772       if (!XmuValidSegment(z))
773 	{
774 	  p->next = z->next;
775 	  XmuDestroySegment(z);
776 	  z = p;
777 	}
778     }
779   return (scanline);
780 }
781 
782 /*
783  * Name:
784  *	XmuScanlineNot(scanline, minx, maxx)
785  *
786  * Parameters:
787  *	scanline - scanlines operate
788  *	minx	 - minimum x coordinate
789  *	maxx	 - maximum x coordinate
790  *
791  * Description:
792  *         (minx)                                                        (maxx)
793  *           +                                                             +
794  * (input)         +---------+     +--------+        +--------+
795  * (output)  +-----+         +-----+        +--------+        +------------+
796  */
797 XmuScanline *
XmuScanlineNot(XmuScanline * scanline,int minx,int maxx)798 XmuScanlineNot(XmuScanline *scanline, int minx, int maxx)
799 {
800   XmuSegment *z;
801   static XmuSegment x = { 0, 0, NULL };
802   static XmuScanline and = { 0, &x, NULL };
803 
804   if (!scanline)
805     return (scanline);
806 
807   XmuOptimizeScanline(scanline);
808   if (minx > maxx)
809     {
810       minx ^= maxx; maxx ^= minx; minx ^= maxx;
811     }
812   and.segment->x1 = minx;
813   and.segment->x2 = maxx;
814   XmuScanlineAnd(scanline, &and);
815   if (!scanline->segment)
816     {
817       scanline->segment = XmuNewSegment(minx, maxx);
818       return (scanline);
819     }
820   z = scanline->segment;
821   if (z->x1 != minx)
822     {
823       XmuSegment *q = XmuNewSegment(minx, z->x1);
824 
825       q->next = z;
826       scanline->segment = q;
827     }
828 
829   /*CONSTCOND*/
830   while (1)
831     {
832       z->x1 = z->x2;
833       if (!z->next)
834 	{
835 	  z->x2 = maxx;
836 	  break;
837 	}
838       z->x2 = z->next->x1;
839       if (z->next->x2 == maxx)
840 	{
841 	  XmuDestroySegment(z->next);
842 	  z->next = (XmuSegment *)NULL;
843 	  break;
844 	}
845       z = z->next;
846     }
847 
848   return (scanline);
849 }
850 
851 
852 #ifndef notdef
853 /*
854  * Function:
855  *	XmuScanlineOrSegment
856  *
857  * Parameters:
858  *	dst - destionation scanline
859  *	src - source segment
860  *
861  * Description:
862  * (input)      +-----------+  +--------+    +---------+
863  * (src)              +-------------------+
864  * (output)     +-------------------------+  +---------+
865  */
866 XmuScanline *
XmuScanlineOrSegment(XmuScanline * dst,XmuSegment * src)867 XmuScanlineOrSegment(XmuScanline *dst, XmuSegment *src)
868 {
869   XmuSegment *z, *p, ins;
870 
871   if (!src || !dst || !XmuValidSegment(src))
872     return (dst);
873 
874   if (!dst->segment)
875     {
876       dst->segment = XmuNewSegment(src->x1, src->x2);
877       return (dst);
878     }
879 
880   z = p = dst->segment;
881   ins.x1 = src->x1;
882   ins.x2 = src->x2;
883 
884   /*CONSTCOND*/
885   while (1)
886     {
887       if (!z)
888 	{
889             XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
890 
891 	    if (p == dst->segment && z == p)
892 	      dst->segment = q;
893 	    else
894 	      p->next = q;
895 	    break;
896 	}
897       else if (ins.x2 < z->x1)
898 	{
899 	  XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
900 
901 	  if (p == dst->segment && z == p)
902 	    {
903 	      q->next = dst->segment;
904 	      dst->segment = q;
905 	    }
906 	  else
907 	    {
908 	      p->next = q;
909 	      q->next = z;
910 	    }
911 	  break;
912         }
913       else if (ins.x2 <= z->x2)
914 	{
915 	  z->x1 = XmuMin(z->x1, ins.x1);
916 	  break;
917 	}
918       else if (ins.x1 <= z->x2)
919 	{
920 	  ins.x1 = XmuMin(z->x1, ins.x1);
921 	  if (!z->next)
922 	    {
923 	      z->x1 = ins.x1;
924 	      z->x2 = ins.x2;
925 	      break;
926 	    }
927 	  else
928 	    {
929 	      if (z == dst->segment)
930 		{
931 		  p = dst->segment = dst->segment->next;
932 		  XmuDestroySegment(z);
933 		  z = dst->segment;
934 		  continue;
935 		}
936 	      else
937 		{
938 		  p->next = z->next;
939 		  XmuDestroySegment(z);
940 		  z = p;
941 		}
942 	    }
943 	}
944       p = z;
945       z = z->next;
946     }
947 
948   return (dst);
949 }
950 
951 /*
952  * Function:
953  *	XmuScanlineAndSegment
954  *
955  * Parameters:
956  *	dst - destination scanline
957  *	src - source segment
958  *
959  * Description:
960  * (input)      +------------+   +------+     +----------+
961  * (src)             +---------------------+
962  * (output)          +-------+   +------+
963  */
964 XmuScanline *
XmuScanlineAndSegment(XmuScanline * dst,XmuSegment * src)965 XmuScanlineAndSegment(XmuScanline *dst, XmuSegment *src)
966 {
967   XmuSegment *z, *p;
968 
969   if (!dst || !src)
970     return (dst);
971 
972   if (!XmuValidSegment(src))
973     {
974       XmuDestroySegmentList(dst->segment);
975       dst->segment = (XmuSegment *)NULL;
976       return (dst);
977     }
978   if (!dst->segment)
979     return (dst);
980 
981   z = p = dst->segment;
982   while (z)
983     {
984       if (src->x2 <= z->x1 || src->x1 >= z->x2)
985 	{
986 	  if (z == dst->segment)
987 	    {
988 	      p = dst->segment = dst->segment->next;
989 	      XmuDestroySegment(z);
990 	      z = dst->segment;
991 	      continue;
992 	    }
993 	  else
994 	    {
995 	      p->next = z->next;
996 	      XmuDestroySegment(z);
997 	      z = p;
998 	    }
999 	}
1000       else
1001 	{
1002 	  z->x1 = XmuMax(z->x1, src->x1);
1003 	  z->x2 = XmuMin(z->x2, src->x2);
1004 	}
1005       p = z;
1006       z = z->next;
1007     }
1008 
1009   return (dst);
1010 }
1011 
1012 /*
1013  * Function:
1014  *	XmuScanlineXorSegment
1015  *
1016  * Parameters:
1017  *	dst - destionation scanline
1018  *	src - source segment
1019  *
1020  * Descriptipn:
1021  * (input)     +------------+  +----------+    +-----------+
1022  * (src)           +------------------------+
1023  * (output)    +---+        +--+          +-+  +-----------+
1024  */
1025 XmuScanline *
XmuScanlineXorSegment(XmuScanline * dst,XmuSegment * src)1026 XmuScanlineXorSegment(XmuScanline *dst, XmuSegment *src)
1027 {
1028   XmuSegment *p, *z, ins;
1029   int tmp1, tmp2;
1030 
1031   if (!dst || !src || !XmuValidSegment(src))
1032     return (dst);
1033   if (!dst->segment)
1034     {
1035       dst->segment = XmuNewSegment(src->x1, src->x2);
1036       return (dst);
1037     }
1038 
1039   p = z = dst->segment;
1040   ins.x1 = src->x1;
1041   ins.x2 = src->x2;
1042 
1043   /*CONSTCOND*/
1044   while (1)
1045     {
1046       if (!XmuValidSegment((&ins)))
1047 	break;
1048       if (!z || ins.x2 < z->x1)
1049 	{
1050 	  XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
1051 
1052 	  q->next = z;
1053 	  if (z == dst->segment)
1054 	    dst->segment = q;
1055 	  else
1056 	    p->next = q;
1057 	  break;
1058 	}
1059       else if (ins.x2 == z->x1)
1060 	{
1061 	  z->x1 = ins.x1;
1062 	  break;
1063 	}
1064       else if (ins.x1 < z->x2)
1065 	{
1066 	  if (ins.x1 < z->x1)
1067 	    {
1068 	      tmp1 = ins.x2;
1069 	      tmp2 = z->x2;
1070 	      ins.x2 = XmuMax(ins.x2, z->x2);
1071 	      z->x2 = z->x1;
1072 	      z->x1 = ins.x1;
1073 	      ins.x1 = XmuMin(tmp1, tmp2);
1074 	    }
1075 	  else if (ins.x1 > z->x1)
1076 	    {
1077 	      tmp1 = ins.x1;
1078 	      ins.x1 = XmuMin(ins.x2, z->x2);
1079 	      ins.x2 = XmuMax(z->x2, ins.x2);
1080 	      z->x2 = tmp1;
1081 	    }
1082 	  else	/* ins.x1 == z->x1 */
1083 	    {
1084 	      if (ins.x2 < z->x2)
1085 		{
1086 		  z->x1 = ins.x2;
1087 		  break;
1088 		}
1089 	      else
1090 		{
1091 		  ins.x1 = z->x2;
1092 		  if (z == dst->segment)
1093 		    p = dst->segment = dst->segment->next;
1094 		  else
1095 		    p->next = z->next;
1096 		  XmuDestroySegment(z);
1097 		  z = p;
1098 		  continue;
1099 		}
1100 	    }
1101 	}
1102       else if (ins.x1 == z->x2)
1103 	{
1104 	  ins.x1 = z->x1;
1105 	  if (z == dst->segment)
1106 	    p = dst->segment = dst->segment->next;
1107 	  else
1108 	    p->next = z->next;
1109 	  XmuDestroySegment(z);
1110 	  z = p;
1111 	  continue;
1112 	}
1113       p = z;
1114       z = z->next;
1115     }
1116 
1117   return (dst);
1118 }
1119 #endif /* notdef */
1120 
1121 /*
1122  * Function:
1123  *	ScanlineOr
1124  *
1125  * Parameters:
1126  *	dst - destionation scanline
1127  *	src - source scanline
1128  *
1129  * Description:
1130  * (input)    +--------------+  +-----+    +----------+
1131  * (src)          +---------------------+       +-----------+
1132  * (output)   +-------------------------+  +----------------+
1133  */
1134 XmuScanline *
XmuScanlineOr(XmuScanline * dst,XmuScanline * src)1135 XmuScanlineOr(XmuScanline *dst, XmuScanline *src)
1136 {
1137   XmuSegment *z, *p, *Z, ins;
1138 
1139   if (!src || !src->segment || !dst || dst == src)
1140     return (dst);
1141   if (!dst->segment)
1142     {
1143       XmuScanlineCopy(dst, src);
1144       return (dst);
1145     }
1146 
1147   z = p = dst->segment;
1148   Z = src->segment;
1149   ins.x1 = Z->x1;
1150   ins.x2 = Z->x2;
1151 
1152   /*CONSTCOND*/
1153   while (1)
1154     {
1155       while (!XmuValidSegment((&ins)))
1156 	{
1157 	  if ((Z = Z->next) == (XmuSegment *)NULL)
1158 	    return (dst);
1159 	  ins.x1 = Z->x1;
1160 	  ins.x2 = Z->x2;
1161 	}
1162         if (!z)
1163 	  {
1164             XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
1165 
1166             if (p == dst->segment && z == p)
1167 	      dst->segment = p = q;
1168             else
1169 	      {
1170 		p->next = q;
1171 		p = q;
1172 	      }
1173 	    Z = Z->next;
1174 	    XmuAppendSegment(p, Z);
1175 	    break;
1176 	  }
1177         else if (ins.x2 < z->x1)
1178 	  {
1179 	    XmuSegment *r = XmuNewSegment(ins.x1, ins.x2);
1180 
1181 	    if (p == dst->segment && z == p)
1182 	      {
1183 		r->next = dst->segment;
1184 		dst->segment = p = r;
1185 	      }
1186 	    else
1187 	      {
1188 		p->next = r;
1189 		r->next = z;
1190 		p = r;
1191 	      }
1192 	    Z = Z->next;
1193             if (!Z)
1194 	      break;
1195             else
1196 	      {
1197 		ins.x1 = Z->x1;
1198 		ins.x2 = Z->x2;
1199 		continue;
1200 	      }
1201 	  }
1202 	else if (ins.x2 <= z->x2)
1203 	  {
1204 	    z->x1 = XmuMin(z->x1, ins.x1);
1205 	    Z = Z->next;
1206 	    if (!Z)
1207 	      break;
1208             else
1209 	      {
1210 		ins.x1 = Z->x1;
1211 		ins.x2 = Z->x2;
1212 		continue;
1213 	      }
1214 	  }
1215 	else if (ins.x1 <= z->x2)
1216 	  {
1217 	    ins.x1 = XmuMin(z->x1, ins.x1);
1218 	    if (!z->next)
1219 	      {
1220 		z->x1 = ins.x1;
1221 		z->x2 = ins.x2;
1222 		p = z;
1223 		Z = Z->next;
1224 		XmuAppendSegment(p, Z);
1225 		break;
1226 	      }
1227             else
1228 	      {
1229 		if (z == dst->segment)
1230 		  {
1231 		    p = dst->segment = dst->segment->next;
1232 		    XmuDestroySegment(z);
1233 		    z = p;
1234 		    continue;
1235 		  }
1236                 else
1237 		  {
1238 		    p->next = z->next;
1239 		    XmuDestroySegment(z);
1240 		    z = p;
1241 		  }
1242 	      }
1243 	  }
1244 	p = z;
1245 	z = z->next;
1246     }
1247 
1248   return (dst);
1249 }
1250 
1251 /*
1252  * Function:
1253  *	XmuScanlineAnd
1254  *
1255  * Parameters:
1256  *	dst - destination scanline
1257  *	src - source scanline
1258  *
1259  * Description:
1260  * (input)    +--------------+  +-----+    +----------+
1261  * (src)          +---------------------+       +-----------+
1262  * (output)       +----------+  +-----+         +-----+
1263  */
1264 XmuScanline *
XmuScanlineAnd(XmuScanline * dst,XmuScanline * src)1265 XmuScanlineAnd(XmuScanline *dst, XmuScanline *src)
1266 {
1267   XmuSegment  *z, *p, *Z;
1268 
1269   if (!dst || !src || dst == src || !dst->segment) {
1270         return (dst);
1271   }
1272   if (!src->segment)
1273     {
1274       XmuDestroySegmentList(dst->segment);
1275       dst->segment = (XmuSegment *)NULL;
1276       return (dst);
1277     }
1278   z = p = dst->segment;
1279   Z = src->segment;
1280 
1281   while (z)
1282     {
1283       while (!XmuValidSegment(Z) || Z->x2 <= z->x1)
1284 	{
1285 	  Z = Z->next;
1286 	  if (!Z)
1287 	    {
1288 	      if (z == dst->segment)
1289 		dst->segment = (XmuSegment *)NULL;
1290 	      else
1291 		p->next = (XmuSegment *)0;
1292 	      XmuDestroySegmentList(z);
1293 	      return (dst);
1294 	    }
1295 	}
1296       if (Z->x1 >= z->x2)
1297 	{
1298 	  if (z == dst->segment)
1299 	    {
1300 	      p = dst->segment = dst->segment->next;
1301 	      XmuDestroySegment(z);
1302 	      z = dst->segment;
1303 	    }
1304 	  else
1305 	    {
1306 	      p->next = z->next;
1307 	      XmuDestroySegment(z);
1308 	      z = p->next;
1309 	    }
1310 	  if (!z)
1311 	    return (dst);
1312 	  else
1313 	    continue;
1314 	}
1315         z->x1 = XmuMax(z->x1, Z->x1);
1316 	if (z->x2 > Z->x2)
1317 	  {
1318             if (Z->next)
1319 	      {
1320                 XmuSegment *q = XmuNewSegment(Z->x2, z->x2);
1321 
1322 		q->next = z->next;
1323 		z->next = q;
1324 	      }
1325 	    z->x2 = Z->x2;
1326 	  }
1327 	p = z;
1328 	z = z->next;
1329     }
1330 
1331   return (dst);
1332 }
1333 
1334 /*
1335  * Function:
1336  *	ScanlineXor
1337  *
1338  * Parameters:
1339  *	dst - destination scanline
1340  *	src - source scanline
1341  *
1342  * Description:
1343  * (input)    +--------------+  +-----+    +----------+
1344  * (src)          +---------------------+       +-----------+
1345  * (output)   +---+          +--+     +-+  +----+     +-----+
1346  */
1347 XmuScanline *
XmuScanlineXor(XmuScanline * dst,XmuScanline * src)1348 XmuScanlineXor(XmuScanline *dst, XmuScanline *src)
1349 {
1350   XmuSegment *z, *p, *Z, ins;
1351   int tmp1, tmp2;
1352 
1353   if (!src || !dst || !src->segment)
1354     return (dst);
1355   if (src == dst)
1356     {
1357       XmuDestroySegmentList(dst->segment);
1358       dst->segment = (XmuSegment *)NULL;
1359       return (dst);
1360     }
1361   if (!dst->segment)
1362     {
1363       XmuScanlineCopy(dst, src);
1364       return (dst);
1365     }
1366 
1367   z = p = dst->segment;
1368   Z = src->segment;
1369   ins.x1 = Z->x1;
1370   ins.x2 = Z->x2;
1371 
1372   /*CONSTCOND*/
1373   while (1)
1374     {
1375       while (!XmuValidSegment((&ins)))
1376 	{
1377 	  if ((Z = Z->next) == (XmuSegment *)NULL)
1378 	    return (dst);
1379 	  ins.x1 = Z->x1;
1380 	  ins.x2 = Z->x2;
1381 	}
1382       if (!z)
1383 	{
1384 	  XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
1385 
1386             if (!dst->segment)
1387 	      dst->segment = q;
1388             else
1389 	      p->next = q;
1390 	    p = q;
1391 	    Z = Z->next;
1392 	    XmuAppendSegment(p, Z);
1393 	    break;
1394 	}
1395       else if (ins.x2 < z->x1)
1396 	{
1397 	  XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
1398 
1399 	  q->next = z;
1400 	  if (z == dst->segment)
1401 	    dst->segment = q;
1402 	  else
1403 	    p->next = q;
1404 	  if ((Z = Z->next) == (XmuSegment *)NULL)
1405 	    return (dst);
1406 
1407 	  p = q;
1408 	  ins.x1 = Z->x1;
1409 	  ins.x2 = Z->x2;
1410 	  continue;
1411 	}
1412       else if (ins.x2 == z->x1)
1413 	{
1414 	  z->x1 = ins.x1;
1415 	  if ((Z = Z->next) == (XmuSegment *)NULL)
1416 	    break;
1417 	  ins.x1 = Z->x1;
1418 	  ins.x2 = Z->x2;
1419 	  continue;
1420 	}
1421       else if (ins.x1 < z->x2)
1422 	{
1423 	  if (ins.x1 == z->x1)
1424 	    {
1425 	      if (ins.x2 < z->x2)
1426 		{
1427 		  z->x1 = ins.x2;
1428 		  if ((Z = Z->next) == (XmuSegment *)NULL)
1429 		    break;
1430 		  ins.x1 = Z->x1;
1431 		  ins.x2 = Z->x2;
1432 		  continue;
1433 		}
1434 	      else
1435 		{
1436 		  ins.x1 = z->x2;
1437 		  if (z == dst->segment)
1438 		    p = dst->segment = dst->segment->next;
1439 		  else
1440 		    p->next = z->next;
1441 		  XmuDestroySegment(z);
1442 		  z = p;
1443 		  continue;
1444 		}
1445 	    }
1446 	  else
1447 	    {
1448 	      if (Z->x2 < z->x2)
1449 		{
1450 		  XmuSegment  *q = XmuNewSegment(XmuMin(ins.x1, z->x1),
1451 						 XmuMax(z->x1, ins.x1));
1452 
1453 		  q->next = z;
1454 		  if (z == dst->segment)
1455 		    dst->segment = q;
1456 		  else
1457 		    p->next = q;
1458 		  ins.x1 = z->x2;
1459 		  z->x1 = ins.x2;
1460 		  p = q;
1461 		  continue;
1462 		}
1463 	      else
1464 		{
1465 		  tmp1 = ins.x2;
1466 		  tmp2 = z->x2;
1467 		  ins.x2 = XmuMax(ins.x2, z->x2);
1468 		  z->x2 = XmuMax(z->x1, ins.x1);
1469 		  z->x1 = XmuMin(ins.x1, z->x1);
1470 		  ins.x1 = XmuMin(tmp1, tmp2);
1471 		}
1472 	    }
1473 	}
1474       else if (ins.x1 == z->x2)
1475 	{
1476 	  ins.x1 = z->x1;
1477 	  if (z == dst->segment)
1478 	    p = dst->segment = dst->segment->next;
1479 	  else
1480 	    p->next = z->next;
1481 	  XmuDestroySegment(z);
1482 	  z = p;
1483 	  continue;
1484 	}
1485       p = z;
1486       z = z->next;
1487     }
1488 
1489   return (dst);
1490 }
1491 
1492 /*
1493  * Function:
1494  *	XmuNewScanline
1495  *
1496  * Parameters:
1497  *	y  - y coordinate
1498  *	x1 - left coordinate
1499  *	x2 - right coordinate
1500  *
1501  * Description:
1502  *	Creates a new Scanline
1503  */
1504 XmuScanline *
XmuNewScanline(int y,int x1,int x2)1505 XmuNewScanline(int y, int x1, int x2)
1506 {
1507   XmuScanline *scanline;
1508 
1509   scanline = (XmuScanline *)XtMalloc(sizeof(XmuScanline));
1510   scanline->y = y;
1511   if (x1 < x2)
1512     scanline->segment = XmuNewSegment(x1, x2);
1513   else
1514     scanline->segment = (XmuSegment *)NULL;
1515 
1516   scanline->next = (XmuScanline *)NULL;
1517 
1518   return (scanline);
1519 }
1520 
1521 /*
1522  * Function:
1523  *	XmuDestroyScanlineList
1524  *
1525  * Parameters:
1526  *	scanline - scanline list to destroy
1527  *
1528  * Description:
1529  *	Destroy a scanline list
1530  *
1531  * Observation:
1532  *	Use as follow:
1533  *	XmuDestroyScanlineList(area->scanline);
1534  *	area->scanline = (XmuScanline *)NULL;
1535  */
1536 void
XmuDestroyScanlineList(XmuScanline * scanline)1537 XmuDestroyScanlineList(XmuScanline *scanline)
1538 {
1539   XmuScanline *z;
1540 
1541   if (!scanline)
1542     return;
1543 
1544   while (scanline)
1545     {
1546       z = scanline;
1547       scanline = scanline->next;
1548       XmuDestroyScanline(z);
1549     }
1550 }
1551 
1552 /*
1553  * Function:
1554  *	XmuOptimizeArea
1555  *
1556  * Parameters:
1557  *	area - area to optimize
1558  *
1559  * Description:
1560  *	  Optimizes an area. This function is called when finishing a
1561  *	operation between areas, since they can end with redundant data,
1562  *	and the algorithms for area combination waits a area with
1563  *	correct data (but can left unnecessary data in the area, to avoid
1564  *	to much paranoia tests).
1565  */
XmuOptimizeArea(XmuArea * area)1566 XmuArea *XmuOptimizeArea(XmuArea *area)
1567 {
1568   XmuScanline *pr, *at;
1569 
1570   if (!area || !area->scanline)
1571     return (area);
1572 
1573   if (!area->scanline->next)
1574     {
1575       XmuDestroyScanlineList(area->scanline);
1576       area->scanline = (XmuScanline *)0;
1577       return (area);
1578     }
1579 
1580   pr = area->scanline;
1581   at = area->scanline->next;
1582   while (area->scanline && (!XmuValidScanline(area->scanline)
1583 			    || (area->scanline->next && area->scanline->y
1584 				>= area->scanline->next->y)))
1585     {
1586       area->scanline = area->scanline->next;
1587       XmuDestroyScanline(pr);
1588       pr = area->scanline;
1589       if (pr)
1590 	at = pr->next;
1591     }
1592 
1593   for (; at; pr = at, at = at->next)
1594     {
1595       if (XmuScanlineEqu(at, pr)
1596 	  || (!XmuValidScanline(at) && !XmuValidScanline(pr))
1597 	  || (at->next && at->y >= at->next->y))
1598 	{
1599 	  pr->next = at->next;
1600 	  XmuDestroyScanline(at);
1601 	  at = pr;
1602 	}
1603     }
1604   if (pr && XmuValidScanline(pr))
1605     {
1606       XmuDestroySegmentList(pr->segment);
1607       pr->segment = (XmuSegment *)NULL;
1608     }
1609   if (area->scanline && !area->scanline->next)
1610     {
1611       XmuDestroyScanlineList(area->scanline);
1612       area->scanline = (XmuScanline *)NULL;
1613     }
1614 
1615   return (area);
1616 }
1617