• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /* -=- sraRegion.c
2  * Copyright (c) 2001 James "Wez" Weatherall, Johannes E. Schindelin
3  *
4  * A general purpose region clipping library
5  * Only deals with rectangular regions, though.
6  */
7 
8 #include <rfb/rfb.h>
9 #include <rfb/rfbregion.h>
10 
11 /* -=- Internal Span structure */
12 
13 struct sraRegion;
14 
15 typedef struct sraSpan {
16   struct sraSpan *_next;
17   struct sraSpan *_prev;
18   int start;
19   int end;
20   struct sraRegion *subspan;
21 } sraSpan;
22 
23 typedef struct sraRegion {
24   sraSpan front;
25   sraSpan back;
26 } sraSpanList;
27 
28 /* -=- Span routines */
29 
30 sraSpanList *sraSpanListDup(const sraSpanList *src);
31 void sraSpanListDestroy(sraSpanList *list);
32 
33 static sraSpan *
sraSpanCreate(int start,int end,const sraSpanList * subspan)34 sraSpanCreate(int start, int end, const sraSpanList *subspan) {
35   sraSpan *item = (sraSpan*)malloc(sizeof(sraSpan));
36   item->_next = item->_prev = NULL;
37   item->start = start;
38   item->end = end;
39   item->subspan = sraSpanListDup(subspan);
40   return item;
41 }
42 
43 static sraSpan *
sraSpanDup(const sraSpan * src)44 sraSpanDup(const sraSpan *src) {
45   sraSpan *span;
46   if (!src) return NULL;
47   span = sraSpanCreate(src->start, src->end, src->subspan);
48   return span;
49 }
50 
51 static void
sraSpanInsertAfter(sraSpan * newspan,sraSpan * after)52 sraSpanInsertAfter(sraSpan *newspan, sraSpan *after) {
53   newspan->_next = after->_next;
54   newspan->_prev = after;
55   after->_next->_prev = newspan;
56   after->_next = newspan;
57 }
58 
59 static void
sraSpanInsertBefore(sraSpan * newspan,sraSpan * before)60 sraSpanInsertBefore(sraSpan *newspan, sraSpan *before) {
61   newspan->_next = before;
62   newspan->_prev = before->_prev;
63   before->_prev->_next = newspan;
64   before->_prev = newspan;
65 }
66 
67 static void
sraSpanRemove(sraSpan * span)68 sraSpanRemove(sraSpan *span) {
69   span->_prev->_next = span->_next;
70   span->_next->_prev = span->_prev;
71 }
72 
73 static void
sraSpanDestroy(sraSpan * span)74 sraSpanDestroy(sraSpan *span) {
75   if (span->subspan) sraSpanListDestroy(span->subspan);
76   free(span);
77 }
78 
79 #ifdef DEBUG
80 static void
sraSpanCheck(const sraSpan * span,const char * text)81 sraSpanCheck(const sraSpan *span, const char *text) {
82   /* Check the span is valid! */
83   if (span->start == span->end) {
84     printf(text);
85     printf(":%d-%d\n", span->start, span->end);
86   }
87 }
88 #endif
89 
90 /* -=- SpanList routines */
91 
92 static void sraSpanPrint(const sraSpan *s);
93 
94 static void
sraSpanListPrint(const sraSpanList * l)95 sraSpanListPrint(const sraSpanList *l) {
96   sraSpan *curr;
97   if (!l) {
98 	  printf("NULL");
99 	  return;
100   }
101   curr = l->front._next;
102   printf("[");
103   while (curr != &(l->back)) {
104     sraSpanPrint(curr);
105     curr = curr->_next;
106   }
107   printf("]");
108 }
109 
110 void
sraSpanPrint(const sraSpan * s)111 sraSpanPrint(const sraSpan *s) {
112   printf("(%d-%d)", (s->start), (s->end));
113   if (s->subspan)
114     sraSpanListPrint(s->subspan);
115 }
116 
117 static sraSpanList *
sraSpanListCreate(void)118 sraSpanListCreate(void) {
119   sraSpanList *item = (sraSpanList*)malloc(sizeof(sraSpanList));
120   item->front._next = &(item->back);
121   item->front._prev = NULL;
122   item->back._prev = &(item->front);
123   item->back._next = NULL;
124   return item;
125 }
126 
127 sraSpanList *
sraSpanListDup(const sraSpanList * src)128 sraSpanListDup(const sraSpanList *src) {
129   sraSpanList *newlist;
130   sraSpan *newspan, *curr;
131 
132   if (!src) return NULL;
133   newlist = sraSpanListCreate();
134   curr = src->front._next;
135   while (curr != &(src->back)) {
136     newspan = sraSpanDup(curr);
137     sraSpanInsertBefore(newspan, &(newlist->back));
138     curr = curr->_next;
139   }
140 
141   return newlist;
142 }
143 
144 void
sraSpanListDestroy(sraSpanList * list)145 sraSpanListDestroy(sraSpanList *list) {
146   sraSpan *curr, *next;
147   while (list->front._next != &(list->back)) {
148     curr = list->front._next;
149     next = curr->_next;
150     sraSpanRemove(curr);
151     sraSpanDestroy(curr);
152     curr = next;
153   }
154   free(list);
155 }
156 
157 static void
sraSpanListMakeEmpty(sraSpanList * list)158 sraSpanListMakeEmpty(sraSpanList *list) {
159   sraSpan *curr, *next;
160   while (list->front._next != &(list->back)) {
161     curr = list->front._next;
162     next = curr->_next;
163     sraSpanRemove(curr);
164     sraSpanDestroy(curr);
165     curr = next;
166   }
167   list->front._next = &(list->back);
168   list->front._prev = NULL;
169   list->back._prev = &(list->front);
170   list->back._next = NULL;
171 }
172 
173 static rfbBool
sraSpanListEqual(const sraSpanList * s1,const sraSpanList * s2)174 sraSpanListEqual(const sraSpanList *s1, const sraSpanList *s2) {
175   sraSpan *sp1, *sp2;
176 
177   if (!s1) {
178     if (!s2) {
179       return 1;
180     } else {
181       rfbErr("sraSpanListEqual:incompatible spans (only one NULL!)\n");
182       return FALSE;
183     }
184   }
185 
186   sp1 = s1->front._next;
187   sp2 = s2->front._next;
188   while ((sp1 != &(s1->back)) &&
189 	 (sp2 != &(s2->back))) {
190     if ((sp1->start != sp2->start) ||
191 	(sp1->end != sp2->end) ||
192 	(!sraSpanListEqual(sp1->subspan, sp2->subspan))) {
193       return 0;
194     }
195     sp1 = sp1->_next;
196     sp2 = sp2->_next;
197   }
198 
199   if ((sp1 == &(s1->back)) && (sp2 == &(s2->back))) {
200     return 1;
201   } else {
202     return 0;
203   }
204 }
205 
206 static rfbBool
sraSpanListEmpty(const sraSpanList * list)207 sraSpanListEmpty(const sraSpanList *list) {
208   return (list->front._next == &(list->back));
209 }
210 
211 static unsigned long
sraSpanListCount(const sraSpanList * list)212 sraSpanListCount(const sraSpanList *list) {
213   sraSpan *curr = list->front._next;
214   unsigned long count = 0;
215   while (curr != &(list->back)) {
216     if (curr->subspan) {
217       count += sraSpanListCount(curr->subspan);
218     } else {
219       count += 1;
220     }
221     curr = curr->_next;
222   }
223   return count;
224 }
225 
226 static void
sraSpanMergePrevious(sraSpan * dest)227 sraSpanMergePrevious(sraSpan *dest) {
228   sraSpan *prev = dest->_prev;
229 
230   while ((prev->_prev) &&
231 	 (prev->end == dest->start) &&
232 	 (sraSpanListEqual(prev->subspan, dest->subspan))) {
233     /*
234     printf("merge_prev:");
235     sraSpanPrint(prev);
236     printf(" & ");
237     sraSpanPrint(dest);
238     printf("\n");
239     */
240     dest->start = prev->start;
241     sraSpanRemove(prev);
242     sraSpanDestroy(prev);
243     prev = dest->_prev;
244   }
245 }
246 
247 static void
sraSpanMergeNext(sraSpan * dest)248 sraSpanMergeNext(sraSpan *dest) {
249   sraSpan *next = dest->_next;
250   while ((next->_next) &&
251 	 (next->start == dest->end) &&
252 	 (sraSpanListEqual(next->subspan, dest->subspan))) {
253 /*
254 	  printf("merge_next:");
255     sraSpanPrint(dest);
256     printf(" & ");
257     sraSpanPrint(next);
258     printf("\n");
259 	*/
260     dest->end = next->end;
261     sraSpanRemove(next);
262     sraSpanDestroy(next);
263     next = dest->_next;
264   }
265 }
266 
267 static void
sraSpanListOr(sraSpanList * dest,const sraSpanList * src)268 sraSpanListOr(sraSpanList *dest, const sraSpanList *src) {
269   sraSpan *d_curr, *s_curr;
270   int s_start, s_end;
271 
272   if (!dest) {
273     if (!src) {
274       return;
275     } else {
276       rfbErr("sraSpanListOr:incompatible spans (only one NULL!)\n");
277       return;
278     }
279   }
280 
281   d_curr = dest->front._next;
282   s_curr = src->front._next;
283   s_start = s_curr->start;
284   s_end = s_curr->end;
285   while (s_curr != &(src->back)) {
286 
287     /* - If we are at end of destination list OR
288        If the new span comes before the next destination one */
289     if ((d_curr == &(dest->back)) ||
290 		(d_curr->start >= s_end)) {
291       /* - Add the span */
292       sraSpanInsertBefore(sraSpanCreate(s_start, s_end,
293 					s_curr->subspan),
294 			  d_curr);
295       if (d_curr != &(dest->back))
296 	sraSpanMergePrevious(d_curr);
297       s_curr = s_curr->_next;
298       s_start = s_curr->start;
299       s_end = s_curr->end;
300     } else {
301 
302       /* - If the new span overlaps the existing one */
303       if ((s_start < d_curr->end) &&
304 	  (s_end > d_curr->start)) {
305 
306 	/* - Insert new span before the existing destination one? */
307 	if (s_start < d_curr->start) {
308 	  sraSpanInsertBefore(sraSpanCreate(s_start,
309 					    d_curr->start,
310 					    s_curr->subspan),
311 			      d_curr);
312 	  sraSpanMergePrevious(d_curr);
313 	}
314 
315 	/* Split the existing span if necessary */
316 	if (s_end < d_curr->end) {
317 	  sraSpanInsertAfter(sraSpanCreate(s_end,
318 					   d_curr->end,
319 					   d_curr->subspan),
320 			     d_curr);
321 	  d_curr->end = s_end;
322 	}
323 	if (s_start > d_curr->start) {
324 	  sraSpanInsertBefore(sraSpanCreate(d_curr->start,
325 					    s_start,
326 					    d_curr->subspan),
327 			      d_curr);
328 	  d_curr->start = s_start;
329 	}
330 
331 	/* Recursively OR subspans */
332 	sraSpanListOr(d_curr->subspan, s_curr->subspan);
333 
334 	/* Merge this span with previous or next? */
335 	if (d_curr->_prev != &(dest->front))
336 	  sraSpanMergePrevious(d_curr);
337 	if (d_curr->_next != &(dest->back))
338 	  sraSpanMergeNext(d_curr);
339 
340 	/* Move onto the next pair to compare */
341 	if (s_end > d_curr->end) {
342 	  s_start = d_curr->end;
343 	  d_curr = d_curr->_next;
344 	} else {
345 	  s_curr = s_curr->_next;
346 	  s_start = s_curr->start;
347 	  s_end = s_curr->end;
348 	}
349       } else {
350 	/* - No overlap.  Move to the next destination span */
351 	d_curr = d_curr->_next;
352       }
353     }
354   }
355 }
356 
357 static rfbBool
sraSpanListAnd(sraSpanList * dest,const sraSpanList * src)358 sraSpanListAnd(sraSpanList *dest, const sraSpanList *src) {
359   sraSpan *d_curr, *s_curr, *d_next;
360 
361   if (!dest) {
362     if (!src) {
363       return 1;
364     } else {
365       rfbErr("sraSpanListAnd:incompatible spans (only one NULL!)\n");
366       return FALSE;
367     }
368   }
369 
370   d_curr = dest->front._next;
371   s_curr = src->front._next;
372   while ((s_curr != &(src->back)) && (d_curr != &(dest->back))) {
373 
374     /* - If we haven't reached a destination span yet then move on */
375     if (d_curr->start >= s_curr->end) {
376       s_curr = s_curr->_next;
377       continue;
378     }
379 
380     /* - If we are beyond the current destination span then remove it */
381     if (d_curr->end <= s_curr->start) {
382       sraSpan *next = d_curr->_next;
383       sraSpanRemove(d_curr);
384       sraSpanDestroy(d_curr);
385       d_curr = next;
386       continue;
387     }
388 
389     /* - If we partially overlap a span then split it up or remove bits */
390     if (s_curr->start > d_curr->start) {
391       /* - The top bit of the span does not match */
392       d_curr->start = s_curr->start;
393     }
394     if (s_curr->end < d_curr->end) {
395       /* - The end of the span does not match */
396       sraSpanInsertAfter(sraSpanCreate(s_curr->end,
397 				       d_curr->end,
398 				       d_curr->subspan),
399 			 d_curr);
400       d_curr->end = s_curr->end;
401     }
402 
403     /* - Now recursively process the affected span */
404     if (!sraSpanListAnd(d_curr->subspan, s_curr->subspan)) {
405       /* - The destination subspan is now empty, so we should remove it */
406 		sraSpan *next = d_curr->_next;
407       sraSpanRemove(d_curr);
408       sraSpanDestroy(d_curr);
409       d_curr = next;
410     } else {
411       /* Merge this span with previous or next? */
412       if (d_curr->_prev != &(dest->front))
413 	sraSpanMergePrevious(d_curr);
414 
415       /* - Move on to the next span */
416       d_next = d_curr;
417       if (s_curr->end >= d_curr->end) {
418 	d_next = d_curr->_next;
419       }
420       if (s_curr->end <= d_curr->end) {
421 	s_curr = s_curr->_next;
422       }
423       d_curr = d_next;
424     }
425   }
426 
427   while (d_curr != &(dest->back)) {
428     sraSpan *next = d_curr->_next;
429     sraSpanRemove(d_curr);
430     sraSpanDestroy(d_curr);
431     d_curr=next;
432   }
433 
434   return !sraSpanListEmpty(dest);
435 }
436 
437 static rfbBool
sraSpanListSubtract(sraSpanList * dest,const sraSpanList * src)438 sraSpanListSubtract(sraSpanList *dest, const sraSpanList *src) {
439   sraSpan *d_curr, *s_curr;
440 
441   if (!dest) {
442     if (!src) {
443       return 1;
444     } else {
445       rfbErr("sraSpanListSubtract:incompatible spans (only one NULL!)\n");
446       return FALSE;
447     }
448   }
449 
450   d_curr = dest->front._next;
451   s_curr = src->front._next;
452   while ((s_curr != &(src->back)) && (d_curr != &(dest->back))) {
453 
454     /* - If we haven't reached a destination span yet then move on */
455     if (d_curr->start >= s_curr->end) {
456       s_curr = s_curr->_next;
457       continue;
458     }
459 
460     /* - If we are beyond the current destination span then skip it */
461     if (d_curr->end <= s_curr->start) {
462       d_curr = d_curr->_next;
463       continue;
464     }
465 
466     /* - If we partially overlap the current span then split it up */
467     if (s_curr->start > d_curr->start) {
468       sraSpanInsertBefore(sraSpanCreate(d_curr->start,
469 					s_curr->start,
470 					d_curr->subspan),
471 			  d_curr);
472       d_curr->start = s_curr->start;
473     }
474     if (s_curr->end < d_curr->end) {
475       sraSpanInsertAfter(sraSpanCreate(s_curr->end,
476 				       d_curr->end,
477 				       d_curr->subspan),
478 			 d_curr);
479       d_curr->end = s_curr->end;
480     }
481 
482     /* - Now recursively process the affected span */
483     if ((!d_curr->subspan) || !sraSpanListSubtract(d_curr->subspan, s_curr->subspan)) {
484       /* - The destination subspan is now empty, so we should remove it */
485       sraSpan *next = d_curr->_next;
486       sraSpanRemove(d_curr);
487       sraSpanDestroy(d_curr);
488       d_curr = next;
489     } else {
490       /* Merge this span with previous or next? */
491       if (d_curr->_prev != &(dest->front))
492 	sraSpanMergePrevious(d_curr);
493       if (d_curr->_next != &(dest->back))
494 	sraSpanMergeNext(d_curr);
495 
496       /* - Move on to the next span */
497       if (s_curr->end > d_curr->end) {
498 	d_curr = d_curr->_next;
499       } else {
500 	s_curr = s_curr->_next;
501       }
502     }
503   }
504 
505   return !sraSpanListEmpty(dest);
506 }
507 
508 /* -=- Region routines */
509 
510 sraRegion *
sraRgnCreate(void)511 sraRgnCreate(void) {
512   return (sraRegion*)sraSpanListCreate();
513 }
514 
515 sraRegion *
sraRgnCreateRect(int x1,int y1,int x2,int y2)516 sraRgnCreateRect(int x1, int y1, int x2, int y2) {
517   sraSpanList *vlist, *hlist;
518   sraSpan *vspan, *hspan;
519 
520   /* - Build the horizontal portion of the span */
521   hlist = sraSpanListCreate();
522   hspan = sraSpanCreate(x1, x2, NULL);
523   sraSpanInsertAfter(hspan, &(hlist->front));
524 
525   /* - Build the vertical portion of the span */
526   vlist = sraSpanListCreate();
527   vspan = sraSpanCreate(y1, y2, hlist);
528   sraSpanInsertAfter(vspan, &(vlist->front));
529 
530   sraSpanListDestroy(hlist);
531 
532   return (sraRegion*)vlist;
533 }
534 
535 sraRegion *
sraRgnCreateRgn(const sraRegion * src)536 sraRgnCreateRgn(const sraRegion *src) {
537   return (sraRegion*)sraSpanListDup((sraSpanList*)src);
538 }
539 
540 void
sraRgnDestroy(sraRegion * rgn)541 sraRgnDestroy(sraRegion *rgn) {
542   sraSpanListDestroy((sraSpanList*)rgn);
543 }
544 
545 void
sraRgnMakeEmpty(sraRegion * rgn)546 sraRgnMakeEmpty(sraRegion *rgn) {
547   sraSpanListMakeEmpty((sraSpanList*)rgn);
548 }
549 
550 /* -=- Boolean Region ops */
551 
552 rfbBool
sraRgnAnd(sraRegion * dst,const sraRegion * src)553 sraRgnAnd(sraRegion *dst, const sraRegion *src) {
554   return sraSpanListAnd((sraSpanList*)dst, (sraSpanList*)src);
555 }
556 
557 void
sraRgnOr(sraRegion * dst,const sraRegion * src)558 sraRgnOr(sraRegion *dst, const sraRegion *src) {
559   sraSpanListOr((sraSpanList*)dst, (sraSpanList*)src);
560 }
561 
562 rfbBool
sraRgnSubtract(sraRegion * dst,const sraRegion * src)563 sraRgnSubtract(sraRegion *dst, const sraRegion *src) {
564   return sraSpanListSubtract((sraSpanList*)dst, (sraSpanList*)src);
565 }
566 
567 void
sraRgnOffset(sraRegion * dst,int dx,int dy)568 sraRgnOffset(sraRegion *dst, int dx, int dy) {
569   sraSpan *vcurr, *hcurr;
570 
571   vcurr = ((sraSpanList*)dst)->front._next;
572   while (vcurr != &(((sraSpanList*)dst)->back)) {
573     vcurr->start += dy;
574     vcurr->end += dy;
575 
576     hcurr = vcurr->subspan->front._next;
577     while (hcurr != &(vcurr->subspan->back)) {
578       hcurr->start += dx;
579       hcurr->end += dx;
580       hcurr = hcurr->_next;
581     }
582 
583     vcurr = vcurr->_next;
584   }
585 }
586 
sraRgnBBox(const sraRegion * src)587 sraRegion *sraRgnBBox(const sraRegion *src) {
588   int xmin=((unsigned int)(int)-1)>>1,ymin=xmin,xmax=1-xmin,ymax=xmax;
589   sraSpan *vcurr, *hcurr;
590 
591   if(!src)
592     return sraRgnCreate();
593 
594   vcurr = ((sraSpanList*)src)->front._next;
595   while (vcurr != &(((sraSpanList*)src)->back)) {
596     if(vcurr->start<ymin)
597       ymin=vcurr->start;
598     if(vcurr->end>ymax)
599       ymax=vcurr->end;
600 
601     hcurr = vcurr->subspan->front._next;
602     while (hcurr != &(vcurr->subspan->back)) {
603       if(hcurr->start<xmin)
604 	xmin=hcurr->start;
605       if(hcurr->end>xmax)
606 	xmax=hcurr->end;
607       hcurr = hcurr->_next;
608     }
609 
610     vcurr = vcurr->_next;
611   }
612 
613   if(xmax<xmin || ymax<ymin)
614     return sraRgnCreate();
615 
616   return sraRgnCreateRect(xmin,ymin,xmax,ymax);
617 }
618 
619 rfbBool
sraRgnPopRect(sraRegion * rgn,sraRect * rect,unsigned long flags)620 sraRgnPopRect(sraRegion *rgn, sraRect *rect, unsigned long flags) {
621   sraSpan *vcurr, *hcurr;
622   sraSpan *vend, *hend;
623   rfbBool right2left = (flags & 2) == 2;
624   rfbBool bottom2top = (flags & 1) == 1;
625 
626   /* - Pick correct order */
627   if (bottom2top) {
628     vcurr = ((sraSpanList*)rgn)->back._prev;
629     vend = &(((sraSpanList*)rgn)->front);
630   } else {
631     vcurr = ((sraSpanList*)rgn)->front._next;
632     vend = &(((sraSpanList*)rgn)->back);
633   }
634 
635   if (vcurr != vend) {
636     rect->y1 = vcurr->start;
637     rect->y2 = vcurr->end;
638 
639     /* - Pick correct order */
640     if (right2left) {
641       hcurr = vcurr->subspan->back._prev;
642       hend = &(vcurr->subspan->front);
643     } else {
644       hcurr = vcurr->subspan->front._next;
645       hend = &(vcurr->subspan->back);
646     }
647 
648     if (hcurr != hend) {
649       rect->x1 = hcurr->start;
650       rect->x2 = hcurr->end;
651 
652       sraSpanRemove(hcurr);
653       sraSpanDestroy(hcurr);
654 
655       if (sraSpanListEmpty(vcurr->subspan)) {
656 	sraSpanRemove(vcurr);
657 	sraSpanDestroy(vcurr);
658       }
659 
660 #if 0
661       printf("poprect:(%dx%d)-(%dx%d)\n",
662 	     rect->x1, rect->y1, rect->x2, rect->y2);
663 #endif
664       return 1;
665     }
666   }
667 
668   return 0;
669 }
670 
671 unsigned long
sraRgnCountRects(const sraRegion * rgn)672 sraRgnCountRects(const sraRegion *rgn) {
673   unsigned long count = sraSpanListCount((sraSpanList*)rgn);
674   return count;
675 }
676 
677 rfbBool
sraRgnEmpty(const sraRegion * rgn)678 sraRgnEmpty(const sraRegion *rgn) {
679   return sraSpanListEmpty((sraSpanList*)rgn);
680 }
681 
682 /* iterator stuff */
sraRgnGetIterator(sraRegion * s)683 sraRectangleIterator *sraRgnGetIterator(sraRegion *s)
684 {
685   /* these values have to be multiples of 4 */
686 #define DEFSIZE 4
687 #define DEFSTEP 8
688   sraRectangleIterator *i =
689     (sraRectangleIterator*)malloc(sizeof(sraRectangleIterator));
690   if(!i)
691     return NULL;
692 
693   /* we have to recurse eventually. So, the first sPtr is the pointer to
694      the sraSpan in the first level. the second sPtr is the pointer to
695      the sraRegion.back. The third and fourth sPtr are for the second
696      recursion level and so on. */
697   i->sPtrs = (sraSpan**)malloc(sizeof(sraSpan*)*DEFSIZE);
698   if(!i->sPtrs) {
699     free(i);
700     return NULL;
701   }
702   i->ptrSize = DEFSIZE;
703   i->sPtrs[0] = &(s->front);
704   i->sPtrs[1] = &(s->back);
705   i->ptrPos = 0;
706   i->reverseX = 0;
707   i->reverseY = 0;
708   return i;
709 }
710 
sraRgnGetReverseIterator(sraRegion * s,rfbBool reverseX,rfbBool reverseY)711 sraRectangleIterator *sraRgnGetReverseIterator(sraRegion *s,rfbBool reverseX,rfbBool reverseY)
712 {
713   sraRectangleIterator *i = sraRgnGetIterator(s);
714   if(reverseY) {
715     i->sPtrs[1] = &(s->front);
716     i->sPtrs[0] = &(s->back);
717   }
718   i->reverseX = reverseX;
719   i->reverseY = reverseY;
720   return(i);
721 }
722 
sraReverse(sraRectangleIterator * i)723 static rfbBool sraReverse(sraRectangleIterator *i)
724 {
725   return( ((i->ptrPos&2) && i->reverseX) ||
726      (!(i->ptrPos&2) && i->reverseY));
727 }
728 
sraNextSpan(sraRectangleIterator * i)729 static sraSpan* sraNextSpan(sraRectangleIterator *i)
730 {
731   if(sraReverse(i))
732     return(i->sPtrs[i->ptrPos]->_prev);
733   else
734     return(i->sPtrs[i->ptrPos]->_next);
735 }
736 
sraRgnIteratorNext(sraRectangleIterator * i,sraRect * r)737 rfbBool sraRgnIteratorNext(sraRectangleIterator* i,sraRect* r)
738 {
739   /* is the subspan finished? */
740   while(sraNextSpan(i) == i->sPtrs[i->ptrPos+1]) {
741     i->ptrPos -= 2;
742     if(i->ptrPos < 0) /* the end */
743       return(0);
744   }
745 
746   i->sPtrs[i->ptrPos] = sraNextSpan(i);
747 
748   /* is this a new subspan? */
749   while(i->sPtrs[i->ptrPos]->subspan) {
750     if(i->ptrPos+2 > i->ptrSize) { /* array is too small */
751       i->ptrSize += DEFSTEP;
752       i->sPtrs = (sraSpan**)realloc(i->sPtrs, sizeof(sraSpan*)*i->ptrSize);
753     }
754     i->ptrPos += 2;
755     if(sraReverse(i)) {
756       i->sPtrs[i->ptrPos]   =   i->sPtrs[i->ptrPos-2]->subspan->back._prev;
757       i->sPtrs[i->ptrPos+1] = &(i->sPtrs[i->ptrPos-2]->subspan->front);
758     } else {
759       i->sPtrs[i->ptrPos]   =   i->sPtrs[i->ptrPos-2]->subspan->front._next;
760       i->sPtrs[i->ptrPos+1] = &(i->sPtrs[i->ptrPos-2]->subspan->back);
761     }
762   }
763 
764   if((i->ptrPos%4)!=2) {
765     rfbErr("sraRgnIteratorNext: offset is wrong (%d%%4!=2)\n",i->ptrPos);
766     return FALSE;
767   }
768 
769   r->y1 = i->sPtrs[i->ptrPos-2]->start;
770   r->y2 = i->sPtrs[i->ptrPos-2]->end;
771   r->x1 = i->sPtrs[i->ptrPos]->start;
772   r->x2 = i->sPtrs[i->ptrPos]->end;
773 
774   return(-1);
775 }
776 
sraRgnReleaseIterator(sraRectangleIterator * i)777 void sraRgnReleaseIterator(sraRectangleIterator* i)
778 {
779   free(i->sPtrs);
780   free(i);
781 }
782 
783 void
sraRgnPrint(const sraRegion * rgn)784 sraRgnPrint(const sraRegion *rgn) {
785 	sraSpanListPrint((sraSpanList*)rgn);
786 }
787 
788 rfbBool
sraClipRect(int * x,int * y,int * w,int * h,int cx,int cy,int cw,int ch)789 sraClipRect(int *x, int *y, int *w, int *h,
790 	    int cx, int cy, int cw, int ch) {
791   if (*x < cx) {
792     *w -= (cx-*x);
793     *x = cx;
794   }
795   if (*y < cy) {
796     *h -= (cy-*y);
797     *y = cy;
798   }
799   if (*x+*w > cx+cw) {
800     *w = (cx+cw)-*x;
801   }
802   if (*y+*h > cy+ch) {
803     *h = (cy+ch)-*y;
804   }
805   return (*w>0) && (*h>0);
806 }
807 
808 rfbBool
sraClipRect2(int * x,int * y,int * x2,int * y2,int cx,int cy,int cx2,int cy2)809 sraClipRect2(int *x, int *y, int *x2, int *y2,
810 	    int cx, int cy, int cx2, int cy2) {
811   if (*x < cx)
812     *x = cx;
813   if (*y < cy)
814     *y = cy;
815   if (*x >= cx2)
816     *x = cx2-1;
817   if (*y >= cy2)
818     *y = cy2-1;
819   if (*x2 <= cx)
820     *x2 = cx+1;
821   if (*y2 <= cy)
822     *y2 = cy+1;
823   if (*x2 > cx2)
824     *x2 = cx2;
825   if (*y2 > cy2)
826     *y2 = cy2;
827   return (*x2>*x) && (*y2>*y);
828 }
829 
830 /* test */
831 
832 #ifdef SRA_TEST
833 /* pipe the output to sort|uniq -u and you'll get the errors. */
main(int argc,char ** argv)834 int main(int argc, char** argv)
835 {
836   sraRegionPtr region, region1, region2;
837   sraRectangleIterator* i;
838   sraRect rect;
839   rfbBool b;
840 
841   region = sraRgnCreateRect(10, 10, 600, 300);
842   region1 = sraRgnCreateRect(40, 50, 350, 200);
843   region2 = sraRgnCreateRect(0, 0, 20, 40);
844 
845   sraRgnPrint(region);
846   printf("\n[(10-300)[(10-600)]]\n\n");
847 
848   b = sraRgnSubtract(region, region1);
849   printf("%s ",b?"true":"false");
850   sraRgnPrint(region);
851   printf("\ntrue [(10-50)[(10-600)](50-200)[(10-40)(350-600)](200-300)[(10-600)]]\n\n");
852 
853   sraRgnOr(region, region2);
854   printf("%ld\n6\n\n", sraRgnCountRects(region));
855 
856   i = sraRgnGetIterator(region);
857   while(sraRgnIteratorNext(i, &rect))
858     printf("%dx%d+%d+%d ",
859 	   rect.x2-rect.x1,rect.y2-rect.y1,
860 	   rect.x1,rect.y1);
861   sraRgnReleaseIterator(i);
862   printf("\n20x10+0+0 600x30+0+10 590x10+10+40 30x150+10+50 250x150+350+50 590x100+10+200 \n\n");
863 
864   i = sraRgnGetReverseIterator(region,1,0);
865   while(sraRgnIteratorNext(i, &rect))
866     printf("%dx%d+%d+%d ",
867 	   rect.x2-rect.x1,rect.y2-rect.y1,
868 	   rect.x1,rect.y1);
869   sraRgnReleaseIterator(i);
870   printf("\n20x10+0+0 600x30+0+10 590x10+10+40 250x150+350+50 30x150+10+50 590x100+10+200 \n\n");
871 
872   i = sraRgnGetReverseIterator(region,1,1);
873   while(sraRgnIteratorNext(i, &rect))
874     printf("%dx%d+%d+%d ",
875 	   rect.x2-rect.x1,rect.y2-rect.y1,
876 	   rect.x1,rect.y1);
877   sraRgnReleaseIterator(i);
878   printf("\n590x100+10+200 250x150+350+50 30x150+10+50 590x10+10+40 600x30+0+10 20x10+0+0 \n\n");
879 
880   sraRgnDestroy(region);
881   sraRgnDestroy(region1);
882   sraRgnDestroy(region2);
883 
884   return(0);
885 }
886 #endif
887