1 /*
2 * Copyright (C) 2006-2007 Novell, Inc (http://www.novell.com)
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software
5 * and associated documentation files (the "Software"), to deal in the Software without restriction,
6 * including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense,
7 * and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so,
8 * subject to the following conditions:
9 *
10 * The above copyright notice and this permission notice shall be included in all copies or substantial
11 * portions of the Software.
12 *
13 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
14 * NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
15 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
16 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
17 * OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
18 *
19 * Authors:
20 * Sebastien Pouliot <sebastien@ximian.com>
21 */
22
23 #include "region-private.h"
24 #include "graphics-path-private.h"
25 #include "graphics-cairo-private.h"
26
27 // #define DEBUG_REGION
28
29 #ifdef DEBUG_REGION
30
31 /*
32 * Debugging helpers
33 */
34
35 static void
display32(BYTE * shape,int width,int height)36 display32 (BYTE *shape, int width, int height)
37 {
38 int i, j;
39
40 for (i = 0; i < height; i++) {
41 for (j = 0; j < width; j++) {
42 printf ("%s", (shape [(i*width + j) * 4] == 0) ? "." : "X");
43 }
44 printf ("\n");
45 }
46 printf ("\n");
47 }
48
49 void
display(char * message,GpRegionBitmap * bitmap)50 display (char* message, GpRegionBitmap *bitmap)
51 {
52 int i = 0, j = 0, k;
53
54 printf ("\n%s\n\tbitmap X: %d, Y: %d, Width: %d, Height %d, Mask %p\n", message,
55 bitmap->X, bitmap->Y, bitmap->Width, bitmap->Height, bitmap->Mask);
56 if (!bitmap->Mask)
57 return;
58
59 while (i < SHAPE_SIZE(bitmap)) {
60 BYTE b = bitmap->Mask [i++];
61 for (k = 0; k < 8; k++) {
62 if (j++ == bitmap->Width) {
63 j = 1;
64 printf ("\n");
65 }
66 printf ("%s", ((b & (1 << k)) == 0) ? "." : "X");
67 }
68 }
69 printf ("\n");
70 }
71
72 #endif
73
74
75 /* Helpers */
76
77
78 /*
79 * rect_union:
80 * @bitmap1: a GpRegionBitmap
81 * @bitmap2: a GpRegionBitmap
82 * @rect: a pointer to a GpRect
83 *
84 * Calculate a rectangle, @rect, that contains both @bitmap1 and @bitmap2
85 * rectangles.
86 */
87 static void
rect_union(GpRegionBitmap * bitmap1,GpRegionBitmap * bitmap2,GpRect * rect)88 rect_union (GpRegionBitmap *bitmap1, GpRegionBitmap *bitmap2, GpRect *rect)
89 {
90 int max_x_1 = bitmap1->X + bitmap1->Width;
91 int max_x_2 = bitmap2->X + bitmap2->Width;
92 int max_y_1 = bitmap1->Y + bitmap1->Height;
93 int max_y_2 = bitmap2->Y + bitmap2->Height;
94
95 rect->X = (bitmap1->X < bitmap2->X) ? bitmap1->X : bitmap2->X;
96 rect->Y = (bitmap1->Y < bitmap2->Y) ? bitmap1->Y : bitmap2->Y;
97 rect->Width = ((max_x_1 > max_x_2) ? max_x_1 : max_x_2) - rect->X;
98 rect->Height = ((max_y_1 > max_y_2) ? max_y_1 : max_y_2) - rect->Y;
99 }
100
101
102 /*
103 * rect_intersect:
104 * @bitmap1: a GpRegionBitmap
105 * @bitmap2: a GpRegionBitmap
106 * @rect: a pointer to a GpRect
107 *
108 * Calculate a rectangle, @rect, that represent the area shared by both
109 * @bitmap1 and @bitmap2 rectangles.
110 */
111 static void
rect_intersect(GpRegionBitmap * bitmap1,GpRegionBitmap * bitmap2,GpRect * rect)112 rect_intersect (GpRegionBitmap *bitmap1, GpRegionBitmap *bitmap2, GpRect *rect)
113 {
114 rect->X = (bitmap1->X > bitmap2->X) ? bitmap1->X : bitmap2->X;
115 rect->Y = (bitmap1->Y > bitmap2->Y) ? bitmap1->Y : bitmap2->Y;
116 rect->Width = (((bitmap1->X + bitmap1->Width) < (bitmap2->X + bitmap2->Width)) ?
117 (bitmap1->X + bitmap1->Width) : (bitmap2->X + bitmap2->Width)) - rect->X;
118 rect->Height = (((bitmap1->Y + bitmap1->Height) < (bitmap2->Y + bitmap2->Height)) ?
119 (bitmap1->Y + bitmap1->Height) : (bitmap2->Y + bitmap2->Height)) - rect->Y;
120 }
121
122
123 /*
124 * rect_adjust_horizontal:
125 * @x: a pointer to an integer
126 * @width: a pointer to an integer
127 *
128 * Adjust the @x and @width values so that they both are multiples of 32
129 * and still encompass, at least, the same data as their original value.
130 * The value 32 is chosen to match CAIRO_STRIDE_ALIGNMENT and allow direct
131 * use of cairo surfaces.
132 */
133 static void
rect_adjust_horizontal(int * x,int * width)134 rect_adjust_horizontal (int *x, int *width)
135 {
136 /* ensure that X is a multiple of 8 */
137 int i = (*x & 31);
138 if (i > 0) {
139 /* reduce X to be a multiple of 8*/
140 *x -= i;
141 /* but keep the "true" Width constant */
142 *width += i;
143 }
144 /* ensure that Width is a multiple of 8 */
145 i = (*width & 31);
146 if (i > 0) {
147 *width += (32 - i);
148 }
149 }
150
151
152 /*
153 * alloc_bitmap_memory:
154 * @size: the size of the required allocation
155 * @clear: a BOOL
156 *
157 * Allocate the alpha (1bpp) memory required for storing a bitmap and return
158 * a pointer to this memory. @clear decides if the memory will be zeroized
159 * after being allocated. NULL can be returned if too much memory is
160 * requested (very large region) or if the memory couldn't be allocated (low
161 * memory).
162 */
163 static BYTE*
alloc_bitmap_memory(int size,BOOL clear)164 alloc_bitmap_memory (int size, BOOL clear)
165 {
166 BYTE *buffer;
167
168 if ((size < 1) || (size > REGION_MAX_BITMAP_SIZE)) {
169 g_warning ("Requested %d bytes. Maximum size for region is %d bytes.",
170 size, REGION_MAX_BITMAP_SIZE);
171 return NULL;
172 }
173
174 buffer = (BYTE*) GdipAlloc (size);
175 if (!buffer)
176 return NULL;
177
178 if (clear)
179 memset (buffer, 0, size);
180
181 return buffer;
182 }
183
184
185 /*
186 * alloc_bitmap_with_buffer:
187 * @x: an integer representing the X coordinate of the bitmap
188 * @y: an integer representing the Y coordinate of the bitmap
189 * @width: an integer representing the Width of the bitmap
190 * @height: an integer representing the Height of the bitmap
191 * @buffer: a byte array of the bitmap data
192 *
193 * Allocate and return a new GpRegionBitmap structure using the supplied
194 * @buffer.
195 *
196 * Notes:
197 * - The allocated structure must be freed using gdip_region_bitmap_free.
198 * - The bitmap @x and @width MUST BE multiple of 8.
199 * - The supplied @buffer MUST match the supplied width and height parameters.
200 */
201 static GpRegionBitmap*
alloc_bitmap_with_buffer(int x,int y,int width,int height,BYTE * buffer)202 alloc_bitmap_with_buffer (int x, int y, int width, int height, BYTE *buffer)
203 {
204 GpRegionBitmap *result = (GpRegionBitmap*) GdipAlloc (sizeof (GpRegionBitmap));
205 if (!result) {
206 return NULL;
207 }
208
209 result->X = x;
210 result->Y = y;
211 result->Width = width;
212 result->Height = height;
213 result->Mask = buffer;
214 result->reduced = FALSE; /* bitmap size isn't optimal wrt contents */
215
216 return result;
217 }
218
219
220 /*
221 * alloc_bitmap:
222 * @x: an integer representing the X coordinate of the bitmap
223 * @y: an integer representing the Y coordinate of the bitmap
224 * @width: an integer representing the Width of the bitmap
225 * @height: an integer representing the Height of the bitmap
226 *
227 * Allocate and return a new GpRegionBitmap structure.
228 *
229 * Notes:
230 * - The allocated structure must be freed using gdip_region_bitmap_free.
231 * - The bitmap @x and @width will be adjusted to a multiple of 8.
232 */
233 static GpRegionBitmap*
alloc_bitmap(int x,int y,int width,int height)234 alloc_bitmap (int x, int y, int width, int height)
235 {
236 BYTE *buffer;
237 int size;
238
239 /* ensure X and Width are multiple of 8 */
240 rect_adjust_horizontal (&x, &width);
241
242 size = (width * height >> 3); /* 1 bit per pixel */
243 buffer = alloc_bitmap_memory (size, TRUE);
244
245 return alloc_bitmap_with_buffer (x, y, width, height, buffer);
246 }
247
248
249 /*
250 * alloc_merged_bitmap:
251 * @bitmap1: a GpRegionBitmap
252 * @bitmap2: a GpRegionBitmap
253 *
254 * Allocate and return a new GpRegionBitmap that covers the total area
255 * (single rectangle) of both @bitmap1 and @bitmap2.
256 *
257 * Notes:
258 * - The allocated structure must be freed using gdip_region_bitmap_free.
259 */
260 static GpRegionBitmap*
alloc_merged_bitmap(GpRegionBitmap * bitmap1,GpRegionBitmap * bitmap2)261 alloc_merged_bitmap (GpRegionBitmap *bitmap1, GpRegionBitmap *bitmap2)
262 {
263 GpRect rect;
264
265 rect_union (bitmap1, bitmap2, &rect);
266 return alloc_bitmap (rect.X, rect.Y, rect.Width, rect.Height);
267 }
268
269
270 /*
271 * alloc_intersected_bitmap:
272 * @bitmap1: a GpRegionBitmap
273 * @bitmap2: a GpRegionBitmap
274 *
275 * Allocate and return a new GpRegionBitmap that covers only the shared
276 * rectangle area of both @bitmap1 and @bitmap2.
277 *
278 * Notes:
279 * - The allocated structure must be freed using gdip_region_bitmap_free.
280 * - The bitmap width will be adjusted to a multiple of 8.
281 */
282 static GpRegionBitmap*
alloc_intersected_bitmap(GpRegionBitmap * bitmap1,GpRegionBitmap * bitmap2)283 alloc_intersected_bitmap (GpRegionBitmap *bitmap1, GpRegionBitmap *bitmap2)
284 {
285 GpRect rect;
286
287 rect_intersect (bitmap1, bitmap2, &rect);
288 return alloc_bitmap (rect.X, rect.Y, rect.Width, rect.Height);
289 }
290
291
292 /*
293 * gdip_region_bitmap_clone:
294 * @bitmap: a GpRegionBitmap
295 *
296 * Allocate and return new GpRegionBitmap containing a copy of @bitmap.
297 *
298 * Note: the allocated structure must be freed using gdip_region_bitmap_free.
299 */
300 GpRegionBitmap*
gdip_region_bitmap_clone(GpRegionBitmap * bitmap)301 gdip_region_bitmap_clone (GpRegionBitmap *bitmap)
302 {
303 BYTE *buffer;
304 int size = (bitmap->Width * bitmap->Height >> 3); /* 1 bit per pixel */
305
306 if (size > 0) {
307 buffer = alloc_bitmap_memory (size, FALSE);
308 if (buffer)
309 memcpy (buffer, bitmap->Mask, size);
310 } else {
311 buffer = NULL;
312 }
313 return alloc_bitmap_with_buffer (bitmap->X, bitmap->Y, bitmap->Width, bitmap->Height, buffer);
314 }
315
316
317 /*
318 * empty_bitmap:
319 * @bitmap: a GpRegionBitmap
320 *
321 * Clear and, if required, free the mask of @bitmap. Note that the allocated
322 * GpRegionBitmap structure MUST still be freed using gdip_region_bitmap_free.
323 */
324 static void
empty_bitmap(GpRegionBitmap * bitmap)325 empty_bitmap (GpRegionBitmap *bitmap)
326 {
327 bitmap->X = 0;
328 bitmap->Y = 0;
329 bitmap->Width = 0;
330 bitmap->Height = 0;
331
332 if (bitmap->Mask) {
333 GdipFree (bitmap->Mask);
334 bitmap->Mask = NULL;
335 }
336 }
337
338
339 /*
340 * gdip_region_bitmap_free:
341 * @bitmap: a GpRegionBitmap
342 *
343 * Free the region bitmap @bitmap.
344 */
345 void
gdip_region_bitmap_free(GpRegionBitmap * bitmap)346 gdip_region_bitmap_free (GpRegionBitmap *bitmap)
347 {
348 empty_bitmap (bitmap);
349 GdipFree (bitmap);
350 }
351
352
353 /*
354 * gdip_region_bitmap_from_tree:
355 * @tree: a GpPathTree
356 *
357 * Return a new GpRegionBitmap containing the bitmap recomposed from the
358 * @tree.
359 *
360 * Note: the allocated structure must be freed using gdip_region_bitmap_free.
361 */
362 static GpRegionBitmap*
gdip_region_bitmap_from_tree(GpPathTree * tree)363 gdip_region_bitmap_from_tree (GpPathTree *tree)
364 {
365 GpRegionBitmap *result;
366
367 if (!tree)
368 return NULL;
369
370 /* each item has... */
371 if (tree->path) {
372 /* (a) only a path (the most common case) */
373 result = gdip_region_bitmap_from_path (tree->path);
374 } else {
375 /* (b) two items with an binary operation */
376 GpRegionBitmap *bitmap1 = gdip_region_bitmap_from_tree (tree->branch1);
377 GpRegionBitmap *bitmap2 = gdip_region_bitmap_from_tree (tree->branch2);
378
379 result = gdip_region_bitmap_combine (bitmap1, bitmap2, tree->mode);
380
381 if (bitmap1)
382 gdip_region_bitmap_free (bitmap1);
383 if (bitmap2)
384 gdip_region_bitmap_free (bitmap2);
385 }
386 return result;
387 }
388
389
390 /*
391 * gdip_region_bitmap_ensure:
392 * @region: a GpRegion
393 *
394 * Ensure the @region bitmap is available (as it isn't created until it is
395 * actually needed).
396 */
397 void
gdip_region_bitmap_ensure(GpRegion * region)398 gdip_region_bitmap_ensure (GpRegion *region)
399 {
400 /* we already have the bitmap */
401 if (region->bitmap)
402 return;
403
404 /* redraw the bitmap from the original path + all other operations/paths */
405 region->bitmap = gdip_region_bitmap_from_tree (region->tree);
406 }
407
408
409 /*
410 * gdip_region_bitmap_invalidate:
411 * @region: a GpRegion
412 *
413 * Invalidate (and free) the bitmap (if any) associated with @region. The
414 * bitmap will need to be re-created before begin used.
415 */
416 void
gdip_region_bitmap_invalidate(GpRegion * region)417 gdip_region_bitmap_invalidate (GpRegion *region)
418 {
419 /* it's possible that the bitmap hasn't yet been created (e.g. if
420 a rectangle region has just been converted to a path region) */
421 if (!region->bitmap)
422 return;
423
424 empty_bitmap (region->bitmap);
425 region->bitmap = NULL;
426 }
427
428 /*
429 * gdip_region_bitmap_to_cairo_surface
430 * @bitmap: a GpRegionBitmap
431 *
432 * Create a cairo mask surface for the given region bitmap. Caller is
433 * responsible for calling cairo_surface_destroy on the returned surface.
434 */
435 cairo_surface_t *
gdip_region_bitmap_to_cairo_surface(GpRegionBitmap * bitmap)436 gdip_region_bitmap_to_cairo_surface (GpRegionBitmap *bitmap)
437 {
438 return cairo_image_surface_create_for_data (bitmap->Mask, CAIRO_FORMAT_A1, bitmap->Width, bitmap->Height, bitmap->Width >> 3);
439 }
440
441 /*
442 * gdip_region_bitmap_from_path:
443 * @path: a GpPath
444 *
445 * Return a new GpRegionBitmap containing the bitmap representing the @path.
446 * NULL will be returned if the bitmap cannot be created (e.g. too big).
447 *
448 * Note: the allocated structure must be freed using gdip_region_bitmap_free.
449 */
450 GpRegionBitmap*
gdip_region_bitmap_from_path(GpPath * path)451 gdip_region_bitmap_from_path (GpPath *path)
452 {
453 GpRect bounds;
454 GpRegionBitmap *bitmap;
455 int i, idx;
456 int length = path->count;
457 unsigned long long int size;
458 cairo_surface_t *surface = NULL;
459 cairo_t *cr = NULL;
460
461 /* empty path == empty bitmap */
462 if (length == 0)
463 return alloc_bitmap_with_buffer (0, 0, 0, 0, NULL);
464
465 /* get the limits of the bitmap we need to allocate */
466 if (GdipGetPathWorldBoundsI (path, &bounds, NULL, NULL) != Ok)
467 return NULL;
468
469 /* ensure X and Width are multiple of 8 */
470 rect_adjust_horizontal (&bounds.X, &bounds.Width);
471
472 /* an empty width or height is valid, even if no bitmap can be produced */
473 if ((bounds.Width == 0) || (bounds.Height == 0))
474 return alloc_bitmap_with_buffer (bounds.X, bounds.Y, bounds.Width, bounds.Height, NULL);
475
476 /* replay the path list and the operations to reconstruct the bitmap */
477 size = (unsigned long long int)(bounds.Width >> 3) * bounds.Height;
478 if ((size < 1) || (size > REGION_MAX_BITMAP_SIZE)) {
479 g_warning ("Path conversion requested %llu bytes (%d x %d). Maximum size is %d bytes.",
480 size, bounds.Width, bounds.Height, REGION_MAX_BITMAP_SIZE);
481 return NULL;
482 }
483
484 bitmap = alloc_bitmap (bounds.X, bounds.Y, bounds.Width, bounds.Height);
485 if (bitmap == NULL)
486 return NULL;
487
488 surface = gdip_region_bitmap_to_cairo_surface (bitmap);
489 cr = cairo_create (surface);
490
491 idx = 0;
492 for (i = 0; i < length; ++i) {
493 GpPointF pt = path->points[i];
494 BYTE type = path->types[i];
495 GpPointF pts [3];
496 /* mask the bits so that we get only the type value not the other flags */
497 switch (type & PathPointTypePathTypeMask) {
498 case PathPointTypeStart:
499 cairo_move_to (cr, pt.X - bounds.X, pt.Y - bounds.Y);
500 break;
501 case PathPointTypeLine:
502 cairo_line_to (cr, pt.X - bounds.X, pt.Y - bounds.Y);
503 break;
504 case PathPointTypeBezier:
505 /* make sure we only add at most 3 points to pts */
506 if (idx < 3) {
507 pts [idx] = pt;
508 idx ++;
509 }
510 /* once we've added 3 pts, we can draw the curve */
511 if (idx == 3) {
512 cairo_curve_to (cr, pts [0].X - bounds.X, pts [0].Y - bounds.Y,
513 pts [1].X - bounds.X, pts [1].Y - bounds.Y,
514 pts [2].X - bounds.X, pts [2].Y - bounds.Y);
515 idx = 0;
516 }
517 break;
518 }
519
520 /* close the subpath */
521 if (type & PathPointTypeCloseSubpath)
522 cairo_close_path (cr);
523 }
524
525 cairo_clip (cr);
526 cairo_set_source_rgba (cr, 1, 1, 1, 1);
527 cairo_paint (cr);
528 cairo_destroy (cr);
529
530 cairo_surface_destroy (surface);
531
532 return bitmap;
533 }
534
535
536 /*
537 * gdip_region_bitmap_get_smallest_rect:
538 * @bitmap: a GpRegionBitmap
539 * @rect: a pointer to a GpRect
540 *
541 * Return the minimal used space in the bitmap inside @rect.
542 */
543 void
gdip_region_bitmap_get_smallest_rect(GpRegionBitmap * bitmap,GpRect * rect)544 gdip_region_bitmap_get_smallest_rect (GpRegionBitmap *bitmap, GpRect *rect)
545 {
546 int first_y = bitmap->Height + 1; /* empty (top) lines */
547 int last_y = -1; /* empty (bottom) lines */
548 int first_x = bitmap->Width + 1; /* empty (left) columns */
549 int last_x = -1; /* empty (right) columns */
550 int i = 0;
551 int original_size = SHAPE_SIZE(bitmap);
552 int x = 0, y = 0;
553 int k;
554
555 while (i < original_size) {
556 if (bitmap->Mask [i] != 0) {
557 for (k = 0; k < 8; k++) {
558 if ((bitmap->Mask [i] & (1 << k)) != 0) {
559 if (x < first_x)
560 first_x = x;
561 if (x > last_x)
562 last_x = x;
563 if (y < first_y)
564 first_y = y;
565 if (y > last_y)
566 last_y = y;
567 }
568 x++;
569 }
570 } else {
571 x += 8;
572 }
573 i++;
574 if (x == bitmap->Width) {
575 x = 0;
576 y++;
577 }
578 }
579
580 /* did we found some bits ? */
581 if ((last_x == -1) && (last_y == -1) && (first_x == bitmap->Width + 1) && (first_y == bitmap->Height + 1)) {
582 rect->X = rect->Y = rect->Width = rect->Height = 0;
583 } else {
584 // convert to pixel values
585 rect->X = bitmap->X + first_x;
586 rect->Y = bitmap->Y + first_y;
587 rect->Width = last_x - first_x + 1;
588 rect->Height = last_y - first_y + 1;
589 }
590 }
591
592
593 /*
594 * is_worth_shrinking:
595 * @original_size: the original size of a bitmap
596 * @new_size: the _potential_ new size of the bitmap (if shrinked)
597 *
598 * Decide if the current bitmap, based on it's current size, is worth
599 * shrinking to a lesser size.
600 *
601 * Note: Many binary operations (e.g. intersection) can greatly reduce the
602 * size of the final bitmap.
603 */
604 static BOOL
is_worth_shrinking(int original_size,int new_size)605 is_worth_shrinking (int original_size, int new_size)
606 {
607 /* FIXME - we can do better than checking if we "save" 4kb */
608 return ((original_size - new_size) > 4096);
609 }
610
611
612 /*
613 * gdip_region_bitmap_shrink:
614 * @bitmap: a GpRegionBitmap
615 * @always_shrink: a BOOL
616 *
617 * Shrink the @bitmap if either @always_shrink is TRUE, or if it is decided
618 * to be worth the CPU time (see is_worth_shrinking).
619 *
620 * Reducing the bitmap size permit (a) to reduce the memory footprint and
621 * (b) makes it more likely to apply certain optimizations using rectangle
622 * intersections.
623 *
624 * Notes:
625 * 1. we don't call this after an union (because the result will never be
626 * smaller) but other operations can result in a smaller bitmap.
627 * 2. we keep the bitmap width in multiple of 8 - it's simpler and faster
628 */
629 void
gdip_region_bitmap_shrink(GpRegionBitmap * bitmap,BOOL always_shrink)630 gdip_region_bitmap_shrink (GpRegionBitmap *bitmap, BOOL always_shrink)
631 {
632 int original_size, new_size;
633 BOOL can_be_reduced;
634 GpRect rect;
635
636 /* bitmap (a) was already shrinked, or (b) is empty */
637 if (bitmap->reduced || !bitmap->Mask)
638 return;
639
640 gdip_region_bitmap_get_smallest_rect (bitmap, &rect);
641
642 if ((rect.Width == 0) || (rect.Height == 0)) {
643 /* no, the the bitmap is empty */
644 empty_bitmap (bitmap);
645 return;
646 }
647
648 /* ensure X and Width are multiple of 8 */
649 rect_adjust_horizontal (&rect.X, &rect.Width);
650
651 original_size = SHAPE_SIZE(bitmap);
652 new_size = (rect.Height * rect.Width) >> 3; /* bits->bytes */
653 can_be_reduced = (new_size < original_size);
654
655 /* shrink if:
656 * a. the caller asked for it (and there is a size change)
657 * b. the caller didn't ask for it but "we" decided it's worth it
658 */
659 if ((always_shrink && can_be_reduced) || is_worth_shrinking (original_size, new_size)) {
660 /* reallocate a new bitmap buffer */
661 BYTE *new_mask = alloc_bitmap_memory (new_size, FALSE);
662 int new_width, new_height;
663 int y;
664
665 int old_width_byte, new_width_byte;
666
667 BYTE* newline = NULL;
668 BYTE* oldline = NULL;
669
670 if (!new_mask)
671 return;
672
673 new_width = rect.Width;
674 new_height = rect.Height;
675
676 old_width_byte = bitmap->Width >> 3;
677 new_width_byte = new_width >> 3;
678
679 newline = new_mask;
680 oldline = bitmap->Mask + ((rect.Y - bitmap->Y) * old_width_byte) + ((rect.X - bitmap->X) >> 3);
681 /* copy the interesting portion in the new bitmap */
682 for (y = 0; y < new_height; y++) {
683 memcpy (newline, oldline, new_width_byte);
684 newline += new_width_byte;
685 oldline += old_width_byte;
686 }
687
688 /* replace current data */
689 bitmap->X = rect.X;
690 bitmap->Y = rect.Y;
691 bitmap->Width = rect.Width;
692 bitmap->Height = rect.Height;
693 GdipFree (bitmap->Mask);
694 bitmap->Mask = new_mask;
695 bitmap->reduced = TRUE;
696 }
697 }
698
699
700 /*
701 * is_point_visible:
702 * @bitmap: a GpRegionBitmap
703 * @x: the horizontal position
704 * @y: the vertical position
705 *
706 * Return TRUE if the @x,@y point is set on the bitmap.
707 *
708 * Note: No bounds check are done this internal shared function.
709 */
710 static BOOL
is_point_visible(GpRegionBitmap * bitmap,int x,int y)711 is_point_visible (GpRegionBitmap *bitmap, int x, int y)
712 {
713 int pixel, pos, mask;
714
715 /* is the pixel set ? */
716 x -= bitmap->X;
717 y -= bitmap->Y;
718
719 pixel = (y * bitmap->Width + x);
720 pos = (pixel >> 3);
721 mask = (pixel & 7);
722
723 return ((bitmap->Mask [pos] & (1 << mask)) != 0);
724 }
725
726
727 /*
728 * gdip_region_bitmap_is_point_visible:
729 * @bitmap: a GpRegionBitmap
730 * @x: the horizontal position
731 * @y: the vertical position
732 *
733 * Return TRUE if the @x,@y point is set on the bitmap.
734 *
735 * Note: Using a bitmap reduce the precision to integers.
736 */
737 BOOL
gdip_region_bitmap_is_point_visible(GpRegionBitmap * bitmap,int x,int y)738 gdip_region_bitmap_is_point_visible (GpRegionBitmap *bitmap, int x, int y)
739 {
740 /* is this an empty bitmap ? */
741 if ((bitmap->Width == 0) || (bitmap->Height == 0))
742 return FALSE;
743
744 /* is the point inside the bitmap ? */
745 if ((x < bitmap->X) || (x >= bitmap->X + bitmap->Width))
746 return FALSE;
747 if ((y < bitmap->Y) || (y >= bitmap->Y + bitmap->Height))
748 return FALSE;
749
750 return is_point_visible (bitmap, x, y);
751 }
752
753
754 /*
755 * gdip_region_bitmap_is_point_visible:
756 * @bitmap: a GpRegionBitmap
757 * @rect: a pointer to a GpRect
758 *
759 * Return TRUE is _any_ part of @rect is inside the region.
760 */
761 BOOL
gdip_region_bitmap_is_rect_visible(GpRegionBitmap * bitmap,GpRect * rect)762 gdip_region_bitmap_is_rect_visible (GpRegionBitmap *bitmap, GpRect *rect)
763 {
764 int x, y;
765
766 /* is this an empty bitmap ? */
767 if ((bitmap->Width == 0) || (bitmap->Height == 0))
768 return FALSE;
769
770 /* quick intersection checks */
771 if (bitmap->X >= rect->X + rect->Width)
772 return FALSE;
773 if (bitmap->X + bitmap->Width <= rect->X)
774 return FALSE;
775 if (bitmap->Y >= rect->Y + rect->Height)
776 return FALSE;
777 if (bitmap->Y + bitmap->Height <= rect->Y)
778 return FALSE;
779
780 /* TODO - optimize */
781 for (y = rect->Y; y < rect->Y + rect->Height; y++) {
782 for (x = rect->X; x < rect->X + rect->Width; x++) {
783 if (gdip_region_bitmap_is_point_visible (bitmap, x, y))
784 return TRUE;
785 }
786 }
787
788 return FALSE;
789 }
790
791
792 /*
793 * get_buffer_pos:
794 * @shape: a GpRegionBitmap
795 * @x: the horizontal position
796 * @y: the vertical position
797 *
798 * Return the index, inside the @shape buffer, corresponding to the @x,@y
799 * point.
800 */
801 static int
get_buffer_pos(GpRegionBitmap * shape,int x,int y)802 get_buffer_pos (GpRegionBitmap *shape, int x, int y)
803 {
804 /* check for out of bounds */
805 if ((x < shape->X) || (x >= shape->X + shape->Width))
806 return -1;
807 if ((y < shape->Y) || (y >= shape->Y + shape->Height))
808 return -1;
809
810 x -= shape->X;
811 y -= shape->Y;
812 return ((y * shape->Width + x) >> 3);
813 }
814
815
816 /*
817 * get_byte:
818 * @shape: a GpRegionBitmap
819 * @x: the horizontal position
820 * @y: the vertical position
821 *
822 * Return the byte, from the @shape buffer, corresponding to the @x,@y point.
823 * Note that this byte contains 8 pixels.
824 */
825 static int
get_byte(GpRegionBitmap * shape,int x,int y)826 get_byte (GpRegionBitmap *shape, int x, int y)
827 {
828 /* out of bounds == empty (no pixel) */
829 int pos = get_buffer_pos (shape, x, y);
830 return (pos == -1) ? 0 : shape->Mask [pos];
831 }
832
833
834 /*
835 * Process a single line for gdip_region_bitmap_get_scans.
836 */
837 static BOOL
process_line(GpRegionBitmap * bitmap,int y,int * x,int * w)838 process_line (GpRegionBitmap *bitmap, int y, int *x, int *w)
839 {
840 int pos = *x;
841 *x = -1;
842 *w = -1;
843
844 while (pos < bitmap->X + bitmap->Width) {
845 BOOL visible = gdip_region_bitmap_is_point_visible (bitmap, pos, y);
846 if (*x == -1) {
847 if (visible) {
848 *x += pos + 1;
849 }
850 } else {
851 if (!visible) {
852 *w = pos - *x;
853 return TRUE;
854 }
855 }
856 pos++;
857 }
858
859 /* end of line - have we started a rect ? */
860 if (*x != -1) {
861 *w = pos - *x;
862 return TRUE;
863 }
864
865 return FALSE;
866 }
867
868
869 /*
870 * gdip_region_bitmap_get_scans:
871 * @bitmap: a GpRegionBitmap
872 * @rect: a pointer to an array of GpRectF
873 *
874 * Convert the scan lines of the bitmap into an array of GpRectF. The return
875 * value represents the actual number of GpRectF entries that were generated.
876 */
877 int
gdip_region_bitmap_get_scans(GpRegionBitmap * bitmap,GpRectF * rect)878 gdip_region_bitmap_get_scans (GpRegionBitmap *bitmap, GpRectF *rect)
879 {
880 if (!bitmap || !bitmap->Mask)
881 return 0;
882
883 GpRect actual;
884 int x, y, w;
885 int n = 0;
886
887 actual.X = REGION_INFINITE_POSITION;
888 actual.Width = REGION_INFINITE_LENGTH;
889 /* for each line in the bitmap */
890 for (y = bitmap->Y; y < bitmap->Y + bitmap->Height; y++) {
891 /* until we processed the whole line */
892 x = bitmap->X;
893 while (process_line (bitmap, y, &x, &w)) {
894 /* FIXME - we only look at the last rectangle but we could check all
895 rectangles in the previous line (and retain perfect rendering
896 with, possibly, less rectangle. We could also allow non exact
897 match for X and Width (e.g. +/- 1 pixel). MS doesn't seems to
898 return perfect rectangles for all shapes. */
899
900 /* if position (X) and Width are identical to previous rectangle */
901 if ((x == actual.X) && (w == actual.Width)) {
902 /* then augment it's Height by one */
903 if (rect && (n > 0)) {
904 rect [n - 1].Height++;
905 }
906 } else {
907 actual.X = x;
908 actual.Y = y;
909 actual.Width = w;
910 actual.Height = 1;
911
912 if (rect) {
913 rect [n].X = actual.X;
914 rect [n].Y = actual.Y;
915 rect [n].Width = actual.Width;
916 rect [n].Height = actual.Height;
917 }
918 n++;
919 }
920 /* continue on the same line */
921 x += w + 1;
922 }
923 }
924 return n;
925 }
926
927
928 /*
929 * Binary operators helper functions
930 */
931
932
933 /*
934 * bitmap_intersect:
935 * @shape1: a GpRegionBitmap
936 * @shape2: a GpRegionBitmap
937 *
938 * This function checks if the rectangle containing @shape1 intersect with
939 * the rectangle containing @shape2. It is used to optimize certain code
940 * path in the binary operations.
941 */
942 static BOOL
bitmap_intersect(GpRegionBitmap * shape1,GpRegionBitmap * shape2)943 bitmap_intersect (GpRegionBitmap *shape1, GpRegionBitmap *shape2)
944 {
945 return ((shape1->X < shape2->X + shape2->Width) &&
946 (shape1->X + shape1->Width > shape2->X) &&
947 (shape1->Y < shape2->Y + shape2->Height) &&
948 (shape1->Y + shape1->Height > shape2->Y));
949 }
950
951
952 /*
953 * gdip_region_bitmap_compare:
954 * @shape1: a GpRegionBitmap
955 * @shape2: a GpRegionBitmap
956 *
957 * This function checks if the data inside @shape1 is identical to the data
958 * inside @shape2 - even if their respective rectangles are different.
959 */
960 BOOL
gdip_region_bitmap_compare(GpRegionBitmap * shape1,GpRegionBitmap * shape2)961 gdip_region_bitmap_compare (GpRegionBitmap *shape1, GpRegionBitmap *shape2)
962 {
963 GpRect rect;
964 int x, y;
965
966 /* if the rectangles containing shape1 and shape2 DO NOT
967 intersect, then there is no possible intersection */
968 if (!bitmap_intersect (shape1, shape2))
969 return FALSE;
970
971 rect_union (shape1, shape2, &rect);
972 for (y = rect.Y; y < rect.Y + rect.Height; y++) {
973 for (x = rect.X; x < rect.X + rect.Width; x += 8) {
974 if (get_byte (shape1, x, y) != get_byte (shape2, x, y))
975 return FALSE;
976 }
977 }
978
979 return TRUE;
980 }
981
982
983 /*
984 * Binary operators on bitmap regions
985 *
986 * Notes
987 * - All operations requires the bitmap x origin and it's width to be multiple
988 * of 8.
989 */
990
991
992 /*
993 * gdip_region_bitmap_union:
994 * @shape1: a GpRegionBitmap
995 * @shape2: a GpRegionBitmap
996 *
997 * Return a new bitmap containing the union of the two specified region
998 * bitmaps.
999 */
1000 static GpRegionBitmap*
gdip_region_bitmap_union(GpRegionBitmap * shape1,GpRegionBitmap * shape2)1001 gdip_region_bitmap_union (GpRegionBitmap *shape1, GpRegionBitmap *shape2)
1002 {
1003 GpRegionBitmap *op = alloc_merged_bitmap (shape1, shape2);
1004 int x, y;
1005
1006 for (y = op->Y; y < op->Y + op->Height; y++) {
1007 int p = get_buffer_pos (op, op->X, y);
1008 for (x = op->X; x < op->X + op->Width; x += 8) {
1009 op->Mask [p++] = get_byte (shape1, x, y) | get_byte (shape2, x, y);
1010 }
1011 }
1012
1013 /* no need to call reduce_bitmap (it will never shrink,
1014 unless the original bitmap were oversized) */
1015 return op;
1016 }
1017
1018
1019 /*
1020 * gdip_region_bitmap_intersection:
1021 * @shape1: a GpRegionBitmap
1022 * @shape2: a GpRegionBitmap
1023 *
1024 * Return a new bitmap containing the intersection of the two specified region
1025 * bitmaps.
1026 */
1027 static GpRegionBitmap*
gdip_region_bitmap_intersection(GpRegionBitmap * shape1,GpRegionBitmap * shape2)1028 gdip_region_bitmap_intersection (GpRegionBitmap *shape1, GpRegionBitmap *shape2)
1029 {
1030 GpRegionBitmap *op;
1031 int x, y;
1032
1033 /* if the rectangles containing shape1 and shape2 DO NOT
1034 intersect, then there is no possible intersection */
1035 if (!bitmap_intersect (shape1, shape2))
1036 return alloc_bitmap_with_buffer (0, 0, 0, 0, NULL);
1037
1038 /* the bitmap size cannot be bigger than a rectangle intersection of
1039 both bitmaps */
1040 op = alloc_intersected_bitmap (shape1, shape2);
1041
1042 for (y = op->Y; y < op->Y + op->Height; y++) {
1043 int p = get_buffer_pos (op, op->X, y);
1044 for (x = op->X; x < op->X + op->Width; x += 8) {
1045 op->Mask [p++] = get_byte (shape1, x, y) & get_byte (shape2, x, y);
1046 }
1047 }
1048
1049 /* reduce bitmap size - if it make sense */
1050 gdip_region_bitmap_shrink (op, FALSE);
1051 return op;
1052 }
1053
1054
1055 /*
1056 * gdip_region_bitmap_exclude:
1057 * @shape1: a GpRegionBitmap
1058 * @shape2: a GpRegionBitmap
1059 *
1060 * Return a new bitmap containing the first shape minus the second shape.
1061 */
1062 static GpRegionBitmap*
gdip_region_bitmap_exclude(GpRegionBitmap * shape1,GpRegionBitmap * shape2)1063 gdip_region_bitmap_exclude (GpRegionBitmap *shape1, GpRegionBitmap *shape2)
1064 {
1065 GpRegionBitmap *op;
1066 int x, y;
1067
1068 /* if the rectangles containing shape1 and shape2 DO NOT
1069 intersect, then the result is identical shape1 */
1070 if (!bitmap_intersect (shape1, shape2))
1071 return gdip_region_bitmap_clone (shape1);
1072
1073 /* the new bitmap size cannot be bigger than shape1 */
1074 op = alloc_bitmap (shape1->X, shape1->Y, shape1->Width, shape1->Height);
1075
1076 for (y = op->Y; y < op->Y + op->Height; y++) {
1077 int p = get_buffer_pos (op, op->X, y);
1078 for (x = op->X; x < op->X + op->Width; x += 8) {
1079 BYTE b1 = get_byte (shape1, x, y);
1080 op->Mask [p++] = b1 - (b1 & get_byte (shape2, x, y));
1081 }
1082 }
1083
1084 /* reduce bitmap size - if it make sense */
1085 gdip_region_bitmap_shrink (op, FALSE);
1086 return op;
1087 }
1088
1089
1090 /*
1091 * gdip_region_bitmap_complement:
1092 * @shape1: a GpRegionBitmap
1093 * @shape2: a GpRegionBitmap
1094 *
1095 * Return a new bitmap containing the second shape minus the first shape.
1096 */
1097 static GpRegionBitmap*
gdip_region_bitmap_complement(GpRegionBitmap * shape1,GpRegionBitmap * shape2)1098 gdip_region_bitmap_complement (GpRegionBitmap *shape1, GpRegionBitmap *shape2)
1099 {
1100 GpRegionBitmap *op;
1101 int x, y;
1102
1103 /* if the rectangles containing shape1 and shape2 DO NOT
1104 intersect, then the result is identical shape2 */
1105 if (!bitmap_intersect (shape1, shape2))
1106 return gdip_region_bitmap_clone (shape2);
1107
1108 /* the new bitmap size cannot be bigger than shape2 */
1109 op = alloc_bitmap (shape2->X, shape2->Y, shape2->Width, shape2->Height);
1110
1111 for (y = op->Y; y < op->Y + op->Height; y++) {
1112 int p = get_buffer_pos (op, op->X, y);
1113 for (x = op->X; x < op->X + op->Width; x += 8) {
1114 BYTE b2 = get_byte (shape2, x, y);
1115 op->Mask [p++] = b2 - (b2 & get_byte (shape1, x, y));
1116 }
1117 }
1118
1119 /* reduce bitmap size - if it make sense */
1120 gdip_region_bitmap_shrink (op, FALSE);
1121 return op;
1122 }
1123
1124
1125 /*
1126 * gdip_region_bitmap_xor:
1127 * @shape1: a GpRegionBitmap
1128 * @shape2: a GpRegionBitmap
1129 *
1130 * Return a new bitmap containing the exclusive-or of the two specified region
1131 * bitmaps.
1132 */
1133 static GpRegionBitmap*
gdip_region_bitmap_xor(GpRegionBitmap * shape1,GpRegionBitmap * shape2)1134 gdip_region_bitmap_xor (GpRegionBitmap *shape1, GpRegionBitmap *shape2)
1135 {
1136 GpRegionBitmap *op;
1137 int x, y;
1138
1139 /* if the rectangles containing shape1 and shape2 DO NOT intersect,
1140 then the result is identical an union of shape1 and shape2. Code is
1141 almost similar but no reduction is required for an union. */
1142 if (!bitmap_intersect (shape1, shape2))
1143 return gdip_region_bitmap_union (shape1, shape2);
1144
1145 /* the new bitmap is potentially as big as the two merged bitmaps */
1146 op = alloc_merged_bitmap (shape1, shape2);
1147
1148 for (y = op->Y; y < op->Y + op->Height; y++) {
1149 int p = get_buffer_pos (op, op->X, y);
1150 for (x = op->X; x < op->X + op->Width; x += 8) {
1151 op->Mask [p++] = get_byte (shape1, x, y) ^ get_byte (shape2, x, y);
1152 }
1153 }
1154
1155 /* reduce bitmap size - if it make sense */
1156 gdip_region_bitmap_shrink (op, FALSE);
1157 return op;
1158 }
1159
1160
1161 /*
1162 * gdip_region_bitmap_combine:
1163 * @shape1: a GpRegionBitmap
1164 * @shape2: a GpRegionBitmap
1165 * @combineMode: the binary operator to apply between the two shapes
1166 *
1167 * Return a new GpRegionBitmap containing a new bitmap resulting from applying
1168 * the @combineMode to @shape1 and @shape2 bitmaps.
1169 */
1170 GpRegionBitmap*
gdip_region_bitmap_combine(GpRegionBitmap * bitmap1,GpRegionBitmap * bitmap2,CombineMode combineMode)1171 gdip_region_bitmap_combine (GpRegionBitmap *bitmap1, GpRegionBitmap* bitmap2, CombineMode combineMode)
1172 {
1173 if (!bitmap1 || !bitmap2)
1174 return NULL;
1175
1176 switch (combineMode) {
1177 case CombineModeComplement:
1178 return gdip_region_bitmap_complement (bitmap1, bitmap2);
1179 case CombineModeExclude:
1180 return gdip_region_bitmap_exclude (bitmap1, bitmap2);
1181 case CombineModeIntersect:
1182 return gdip_region_bitmap_intersection (bitmap1, bitmap2);
1183 case CombineModeUnion:
1184 return gdip_region_bitmap_union (bitmap1, bitmap2);
1185 case CombineModeXor:
1186 return gdip_region_bitmap_xor (bitmap1, bitmap2);
1187 default:
1188 g_warning ("Unkown combine mode specified (%d)", combineMode);
1189 return NULL;
1190 }
1191 }
1192