Home | History | Annotate | Download | only in libvncserver 
      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 *
     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 *
     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
     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
     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
     68 sraSpanRemove(sraSpan *span) {
     69   span->_prev->_next = span->_next;
     70   span->_next->_prev = span->_prev;
     71 }
     72 
     73 static void
     74 sraSpanDestroy(sraSpan *span) {
     75   if (span->subspan) sraSpanListDestroy(span->subspan);
     76   free(span);
     77 }
     78 
     79 #ifdef DEBUG
     80 static void
     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
     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
    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 *
    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 *
    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
    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
    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
    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
    207 sraSpanListEmpty(const sraSpanList *list) {
    208   return (list->front._next == &(list->back));
    209 }
    210 
    211 static unsigned long
    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
    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
    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
    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
    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
    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 *
    511 sraRgnCreate(void) {
    512   return (sraRegion*)sraSpanListCreate();
    513 }
    514 
    515 sraRegion *
    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 *
    536 sraRgnCreateRgn(const sraRegion *src) {
    537   return (sraRegion*)sraSpanListDup((sraSpanList*)src);
    538 }
    539 
    540 void
    541 sraRgnDestroy(sraRegion *rgn) {
    542   sraSpanListDestroy((sraSpanList*)rgn);
    543 }
    544 
    545 void
    546 sraRgnMakeEmpty(sraRegion *rgn) {
    547   sraSpanListMakeEmpty((sraSpanList*)rgn);
    548 }
    549 
    550 /* -=- Boolean Region ops */
    551 
    552 rfbBool
    553 sraRgnAnd(sraRegion *dst, const sraRegion *src) {
    554   return sraSpanListAnd((sraSpanList*)dst, (sraSpanList*)src);
    555 }
    556 
    557 void
    558 sraRgnOr(sraRegion *dst, const sraRegion *src) {
    559   sraSpanListOr((sraSpanList*)dst, (sraSpanList*)src);
    560 }
    561 
    562 rfbBool
    563 sraRgnSubtract(sraRegion *dst, const sraRegion *src) {
    564   return sraSpanListSubtract((sraSpanList*)dst, (sraSpanList*)src);
    565 }
    566 
    567 void
    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 
    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
    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
    672 sraRgnCountRects(const sraRegion *rgn) {
    673   unsigned long count = sraSpanListCount((sraSpanList*)rgn);
    674   return count;
    675 }
    676 
    677 rfbBool
    678 sraRgnEmpty(const sraRegion *rgn) {
    679   return sraSpanListEmpty((sraSpanList*)rgn);
    680 }
    681 
    682 /* iterator stuff */
    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 
    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 
    723 static rfbBool sraReverse(sraRectangleIterator *i)
    724 {
    725   return( ((i->ptrPos&2) && i->reverseX) ||
    726      (!(i->ptrPos&2) && i->reverseY));
    727 }
    728 
    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 
    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 
    777 void sraRgnReleaseIterator(sraRectangleIterator* i)
    778 {
    779   free(i->sPtrs);
    780   free(i);
    781 }
    782 
    783 void
    784 sraRgnPrint(const sraRegion *rgn) {
    785 	sraSpanListPrint((sraSpanList*)rgn);
    786 }
    787 
    788 rfbBool
    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
    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. */
    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