1/*
2 * Copyright © 1998 Keith Packard
3 * Copyright © 2012 Intel Corporation
4 *
5 * Permission to use, copy, modify, distribute, and sell this software and its
6 * documentation for any purpose is hereby granted without fee, provided that
7 * the above copyright notice appear in all copies and that both that
8 * copyright notice and this permission notice appear in supporting
9 * documentation, and that the name of Keith Packard not be used in
10 * advertising or publicity pertaining to distribution of the software without
11 * specific, written prior permission.  Keith Packard makes no
12 * representations about the suitability of this software for any purpose.  It
13 * is provided "as is" without express or implied warranty.
14 *
15 * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
16 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
17 * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
18 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
19 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
20 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
21 * PERFORMANCE OF THIS SOFTWARE.
22 */
23
24#include <stdlib.h>
25
26#include "fb.h"
27
28static Bool region_grow(RegionPtr region)
29{
30	RegDataPtr data;
31	int n;
32
33	n = 16;
34	if (!region->data) {
35		region->data = malloc(RegionSizeof(n));
36		if (!region->data)
37			return RegionBreak(region);
38		region->data->numRects = 1;
39		*RegionBoxptr(region) = region->extents;
40	} else if (!region->data->size) {
41		region->data = malloc(RegionSizeof(n));
42		if (!region->data)
43			return RegionBreak(region);
44		region->data->numRects = 0;
45	} else {
46		n = 2 * region->data->numRects;
47		data = (RegDataPtr) realloc(region->data, RegionSizeof(n));
48		if (!data)
49			return RegionBreak(region);
50		region->data = data;
51	}
52	region->data->size = n;
53	return TRUE;
54}
55
56static inline void add(RegionPtr region,
57		       int16_t x1, int16_t y1, int16_t x2, int16_t y2)
58{
59	BoxPtr r;
60
61	if (region->data->numRects == region->data->size &&
62	    !region_grow(region))
63		return;
64
65	r = RegionBoxptr(region) + region->data->numRects++;
66	r->x1 = x1; r->y1 = y1;
67	r->x2 = x2; r->y2 = y2;
68
69	DBG(("%s[%ld/%ld]: (%d, %d), (%d, %d)\n",
70	     __FUNCTION__,
71	     (long)region->data->numRects, (long)region->data->size,
72	     x1, y1, x2, y2));
73
74	if (x1 < region->extents.x1)
75		region->extents.x1 = x1;
76	if (x2 > region->extents.x2)
77		region->extents.x2 = x2;
78}
79
80#define MASK_0 (FB_ALLONES & ~FbScrRight(FB_ALLONES, 1))
81
82/* Convert bitmap clip mask into clipping region.
83 * First, goes through each line and makes boxes by noting the transitions
84 * from 0 to 1 and 1 to 0.
85 * Then it coalesces the current line with the previous if they have boxes
86 * at the same X coordinates.
87 */
88RegionPtr
89fbBitmapToRegion(PixmapPtr pixmap)
90{
91	FbBits maskw;
92	register RegionPtr region;
93	const FbBits *bits, *line, *end;
94	int width, y1, y2, base, x1;
95	int stride, i;
96
97	DBG(("%s bitmap=%dx%d\n", __FUNCTION__,
98	     pixmap->drawable.width, pixmap->drawable.height));
99
100	region = RegionCreate(NULL, 1);
101	if (!region)
102		return NullRegion;
103
104	line = (FbBits *) pixmap->devPrivate.ptr;
105	stride = pixmap->devKind >> (FB_SHIFT - 3);
106
107	width = pixmap->drawable.width;
108	maskw = 0;
109	if (width & 7)
110		maskw = FB_ALLONES & ~FbScrRight(FB_ALLONES, width & FB_MASK);
111	region->extents.x1 = width;
112	region->extents.x2 = 0;
113	y2 = 0;
114	while (y2 < pixmap->drawable.height) {
115		y1 = y2++;
116		bits = line;
117		line += stride;
118		while (y2 < pixmap->drawable.height &&
119		       memcmp(bits, line, width >> 3) == 0 &&
120		       (maskw == 0 || (bits[width >> FB_SHIFT] & maskw) == (line[width >> FB_SHIFT] & maskw)))
121			line += stride, y2++;
122
123		if (READ(bits) & MASK_0)
124			x1 = 0;
125		else
126			x1 = -1;
127
128		/* Process all words which are fully in the pixmap */
129		end = bits + (width >> FB_SHIFT);
130		for (base = 0; bits < end; base += FB_UNIT) {
131			FbBits w = READ(bits++);
132			if (x1 < 0) {
133				if (!w)
134					continue;
135			} else {
136				if (!~w)
137					continue;
138			}
139			for (i = 0; i < FB_UNIT; i++) {
140				if (w & MASK_0) {
141					if (x1 < 0)
142						x1 = base + i;
143				} else {
144					if (x1 >= 0) {
145						add(region, x1, y1, base + i, y2);
146						x1 = -1;
147					}
148				}
149				w = FbScrLeft(w, 1);
150			}
151		}
152		if (width & FB_MASK) {
153			FbBits w = READ(bits++);
154			for (i = 0; i < (width & FB_MASK); i++) {
155				if (w & MASK_0) {
156					if (x1 < 0)
157						x1 = base + i;
158				} else {
159					if (x1 >= 0) {
160						add(region, x1, y1, base + i, y2);
161						x1 = -1;
162					}
163				}
164				w = FbScrLeft(w, 1);
165			}
166		}
167		if (x1 >= 0)
168			add(region, x1, y1, width, y2);
169	}
170
171	if (region->data->numRects) {
172		region->extents.y1 = RegionBoxptr(region)->y1;
173		region->extents.y2 = RegionEnd(region)->y2;
174		if (region->data->numRects == 1) {
175			free(region->data);
176			region->data = NULL;
177		}
178	} else
179		region->extents.x1 = region->extents.x2 = 0;
180
181	DBG(("%s: region extents=(%d, %d), (%d, %d) x %d\n",
182	     __FUNCTION__,
183	     region->extents.x1, region->extents.y1,
184	     region->extents.x2, region->extents.y2,
185	     region_num_rects(region)));
186
187	return region;
188}
189