Rev 1891 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
1891 | serge | 1 | /* |
2 | * Copyright © 2008 Keith Packard |
||
3 | * |
||
4 | * Permission to use, copy, modify, distribute, and sell this software and its |
||
5 | * documentation for any purpose is hereby granted without fee, provided that |
||
6 | * the above copyright notice appear in all copies and that both that copyright |
||
7 | * notice and this permission notice appear in supporting documentation, and |
||
8 | * that the name of the copyright holders not be used in advertising or |
||
9 | * publicity pertaining to distribution of the software without specific, |
||
10 | * written prior permission. The copyright holders make no representations |
||
11 | * about the suitability of this software for any purpose. It is provided "as |
||
12 | * is" without express or implied warranty. |
||
13 | * |
||
14 | * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, |
||
15 | * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO |
||
16 | * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR |
||
17 | * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, |
||
18 | * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER |
||
19 | * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE |
||
20 | * OF THIS SOFTWARE. |
||
21 | */ |
||
22 | |||
23 | /* |
||
24 | * Matrix interfaces |
||
25 | */ |
||
26 | |||
27 | #ifdef HAVE_CONFIG_H |
||
3931 | Serge | 28 | #include |
1891 | serge | 29 | #endif |
30 | |||
31 | #include |
||
32 | #include |
||
33 | #include "pixman-private.h" |
||
34 | |||
35 | #define F(x) pixman_int_to_fixed (x) |
||
36 | |||
3931 | Serge | 37 | static force_inline int |
38 | count_leading_zeros (uint32_t x) |
||
39 | { |
||
40 | #ifdef __GNUC__ |
||
41 | return __builtin_clz (x); |
||
42 | #else |
||
43 | int n = 0; |
||
44 | while (x) |
||
45 | { |
||
46 | n++; |
||
47 | x >>= 1; |
||
48 | } |
||
49 | return 32 - n; |
||
50 | #endif |
||
51 | } |
||
52 | |||
53 | /* |
||
54 | * Large signed/unsigned integer division with rounding for the platforms with |
||
55 | * only 64-bit integer data type supported (no 128-bit data type). |
||
56 | * |
||
57 | * Arguments: |
||
58 | * hi, lo - high and low 64-bit parts of the dividend |
||
59 | * div - 48-bit divisor |
||
60 | * |
||
61 | * Returns: lowest 64 bits of the result as a return value and highest 64 |
||
62 | * bits of the result to "result_hi" pointer |
||
63 | */ |
||
64 | |||
65 | /* grade-school unsigned division (128-bit by 48-bit) with rounding to nearest */ |
||
66 | static force_inline uint64_t |
||
67 | rounded_udiv_128_by_48 (uint64_t hi, |
||
68 | uint64_t lo, |
||
69 | uint64_t div, |
||
70 | uint64_t *result_hi) |
||
71 | { |
||
72 | uint64_t tmp, remainder, result_lo; |
||
73 | assert(div < ((uint64_t)1 << 48)); |
||
74 | |||
75 | remainder = hi % div; |
||
76 | *result_hi = hi / div; |
||
77 | |||
78 | tmp = (remainder << 16) + (lo >> 48); |
||
79 | result_lo = tmp / div; |
||
80 | remainder = tmp % div; |
||
81 | |||
82 | tmp = (remainder << 16) + ((lo >> 32) & 0xFFFF); |
||
83 | result_lo = (result_lo << 16) + (tmp / div); |
||
84 | remainder = tmp % div; |
||
85 | |||
86 | tmp = (remainder << 16) + ((lo >> 16) & 0xFFFF); |
||
87 | result_lo = (result_lo << 16) + (tmp / div); |
||
88 | remainder = tmp % div; |
||
89 | |||
90 | tmp = (remainder << 16) + (lo & 0xFFFF); |
||
91 | result_lo = (result_lo << 16) + (tmp / div); |
||
92 | remainder = tmp % div; |
||
93 | |||
94 | /* round to nearest */ |
||
95 | if (remainder * 2 >= div && ++result_lo == 0) |
||
96 | *result_hi += 1; |
||
97 | |||
98 | return result_lo; |
||
99 | } |
||
100 | |||
101 | /* signed division (128-bit by 49-bit) with rounding to nearest */ |
||
102 | static inline int64_t |
||
103 | rounded_sdiv_128_by_49 (int64_t hi, |
||
104 | uint64_t lo, |
||
105 | int64_t div, |
||
106 | int64_t *signed_result_hi) |
||
107 | { |
||
108 | uint64_t result_lo, result_hi; |
||
109 | int sign = 0; |
||
110 | if (div < 0) |
||
111 | { |
||
112 | div = -div; |
||
113 | sign ^= 1; |
||
114 | } |
||
115 | if (hi < 0) |
||
116 | { |
||
117 | if (lo != 0) |
||
118 | hi++; |
||
119 | hi = -hi; |
||
120 | lo = -lo; |
||
121 | sign ^= 1; |
||
122 | } |
||
123 | result_lo = rounded_udiv_128_by_48 (hi, lo, div, &result_hi); |
||
124 | if (sign) |
||
125 | { |
||
126 | if (result_lo != 0) |
||
127 | result_hi++; |
||
128 | result_hi = -result_hi; |
||
129 | result_lo = -result_lo; |
||
130 | } |
||
131 | if (signed_result_hi) |
||
132 | { |
||
133 | *signed_result_hi = result_hi; |
||
134 | } |
||
135 | return result_lo; |
||
136 | } |
||
137 | |||
138 | /* |
||
139 | * Multiply 64.16 fixed point value by (2^scalebits) and convert |
||
140 | * to 128-bit integer. |
||
141 | */ |
||
142 | static force_inline void |
||
143 | fixed_64_16_to_int128 (int64_t hi, |
||
144 | int64_t lo, |
||
145 | int64_t *rhi, |
||
146 | int64_t *rlo, |
||
147 | int scalebits) |
||
148 | { |
||
149 | /* separate integer and fractional parts */ |
||
150 | hi += lo >> 16; |
||
151 | lo &= 0xFFFF; |
||
152 | |||
153 | if (scalebits <= 0) |
||
154 | { |
||
155 | *rlo = hi >> (-scalebits); |
||
156 | *rhi = *rlo >> 63; |
||
157 | } |
||
158 | else |
||
159 | { |
||
160 | *rhi = hi >> (64 - scalebits); |
||
161 | *rlo = (uint64_t)hi << scalebits; |
||
162 | if (scalebits < 16) |
||
163 | *rlo += lo >> (16 - scalebits); |
||
164 | else |
||
165 | *rlo += lo << (scalebits - 16); |
||
166 | } |
||
167 | } |
||
168 | |||
169 | /* |
||
170 | * Convert 112.16 fixed point value to 48.16 with clamping for the out |
||
171 | * of range values. |
||
172 | */ |
||
173 | static force_inline pixman_fixed_48_16_t |
||
174 | fixed_112_16_to_fixed_48_16 (int64_t hi, int64_t lo, pixman_bool_t *clampflag) |
||
175 | { |
||
176 | if ((lo >> 63) != hi) |
||
177 | { |
||
178 | *clampflag = TRUE; |
||
179 | return hi >= 0 ? INT64_MAX : INT64_MIN; |
||
180 | } |
||
181 | else |
||
182 | { |
||
183 | return lo; |
||
184 | } |
||
185 | } |
||
186 | |||
187 | /* |
||
188 | * Transform a point with 31.16 fixed point coordinates from the destination |
||
189 | * space to a point with 48.16 fixed point coordinates in the source space. |
||
190 | * No overflows are possible for affine transformations and the results are |
||
191 | * accurate including the least significant bit. Projective transformations |
||
192 | * may overflow, in this case the results are just clamped to return maximum |
||
193 | * or minimum 48.16 values (so that the caller can at least handle the NONE |
||
194 | * and PAD repeats correctly) and the return value is FALSE to indicate that |
||
195 | * such clamping has happened. |
||
196 | */ |
||
197 | PIXMAN_EXPORT pixman_bool_t |
||
198 | pixman_transform_point_31_16 (const pixman_transform_t *t, |
||
199 | const pixman_vector_48_16_t *v, |
||
200 | pixman_vector_48_16_t *result) |
||
201 | { |
||
202 | pixman_bool_t clampflag = FALSE; |
||
203 | int i; |
||
204 | int64_t tmp[3][2], divint; |
||
205 | uint16_t divfrac; |
||
206 | |||
207 | /* input vector values must have no more than 31 bits (including sign) |
||
208 | * in the integer part */ |
||
209 | assert (v->v[0] < ((pixman_fixed_48_16_t)1 << (30 + 16))); |
||
210 | assert (v->v[0] >= -((pixman_fixed_48_16_t)1 << (30 + 16))); |
||
211 | assert (v->v[1] < ((pixman_fixed_48_16_t)1 << (30 + 16))); |
||
212 | assert (v->v[1] >= -((pixman_fixed_48_16_t)1 << (30 + 16))); |
||
213 | assert (v->v[2] < ((pixman_fixed_48_16_t)1 << (30 + 16))); |
||
214 | assert (v->v[2] >= -((pixman_fixed_48_16_t)1 << (30 + 16))); |
||
215 | |||
216 | for (i = 0; i < 3; i++) |
||
217 | { |
||
218 | tmp[i][0] = (int64_t)t->matrix[i][0] * (v->v[0] >> 16); |
||
219 | tmp[i][1] = (int64_t)t->matrix[i][0] * (v->v[0] & 0xFFFF); |
||
220 | tmp[i][0] += (int64_t)t->matrix[i][1] * (v->v[1] >> 16); |
||
221 | tmp[i][1] += (int64_t)t->matrix[i][1] * (v->v[1] & 0xFFFF); |
||
222 | tmp[i][0] += (int64_t)t->matrix[i][2] * (v->v[2] >> 16); |
||
223 | tmp[i][1] += (int64_t)t->matrix[i][2] * (v->v[2] & 0xFFFF); |
||
224 | } |
||
225 | |||
226 | /* |
||
227 | * separate 64-bit integer and 16-bit fractional parts for the divisor, |
||
228 | * which is also scaled by 65536 after fixed point multiplication. |
||
229 | */ |
||
230 | divint = tmp[2][0] + (tmp[2][1] >> 16); |
||
231 | divfrac = tmp[2][1] & 0xFFFF; |
||
232 | |||
233 | if (divint == pixman_fixed_1 && divfrac == 0) |
||
234 | { |
||
235 | /* |
||
236 | * this is a simple affine transformation |
||
237 | */ |
||
238 | result->v[0] = tmp[0][0] + ((tmp[0][1] + 0x8000) >> 16); |
||
239 | result->v[1] = tmp[1][0] + ((tmp[1][1] + 0x8000) >> 16); |
||
240 | result->v[2] = pixman_fixed_1; |
||
241 | } |
||
242 | else if (divint == 0 && divfrac == 0) |
||
243 | { |
||
244 | /* |
||
245 | * handle zero divisor (if the values are non-zero, set the |
||
246 | * results to maximum positive or minimum negative) |
||
247 | */ |
||
248 | clampflag = TRUE; |
||
249 | |||
250 | result->v[0] = tmp[0][0] + ((tmp[0][1] + 0x8000) >> 16); |
||
251 | result->v[1] = tmp[1][0] + ((tmp[1][1] + 0x8000) >> 16); |
||
252 | |||
253 | if (result->v[0] > 0) |
||
254 | result->v[0] = INT64_MAX; |
||
255 | else if (result->v[0] < 0) |
||
256 | result->v[0] = INT64_MIN; |
||
257 | |||
258 | if (result->v[1] > 0) |
||
259 | result->v[1] = INT64_MAX; |
||
260 | else if (result->v[1] < 0) |
||
261 | result->v[1] = INT64_MIN; |
||
262 | } |
||
263 | else |
||
264 | { |
||
265 | /* |
||
266 | * projective transformation, analyze the top 32 bits of the divisor |
||
267 | */ |
||
268 | int32_t hi32divbits = divint >> 32; |
||
269 | if (hi32divbits < 0) |
||
270 | hi32divbits = ~hi32divbits; |
||
271 | |||
272 | if (hi32divbits == 0) |
||
273 | { |
||
274 | /* the divisor is small, we can actually keep all the bits */ |
||
275 | int64_t hi, rhi, lo, rlo; |
||
276 | int64_t div = (divint << 16) + divfrac; |
||
277 | |||
278 | fixed_64_16_to_int128 (tmp[0][0], tmp[0][1], &hi, &lo, 32); |
||
279 | rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi); |
||
280 | result->v[0] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag); |
||
281 | |||
282 | fixed_64_16_to_int128 (tmp[1][0], tmp[1][1], &hi, &lo, 32); |
||
283 | rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi); |
||
284 | result->v[1] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag); |
||
285 | } |
||
286 | else |
||
287 | { |
||
288 | /* the divisor needs to be reduced to 48 bits */ |
||
289 | int64_t hi, rhi, lo, rlo, div; |
||
290 | int shift = 32 - count_leading_zeros (hi32divbits); |
||
291 | fixed_64_16_to_int128 (divint, divfrac, &hi, &div, 16 - shift); |
||
292 | |||
293 | fixed_64_16_to_int128 (tmp[0][0], tmp[0][1], &hi, &lo, 32 - shift); |
||
294 | rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi); |
||
295 | result->v[0] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag); |
||
296 | |||
297 | fixed_64_16_to_int128 (tmp[1][0], tmp[1][1], &hi, &lo, 32 - shift); |
||
298 | rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi); |
||
299 | result->v[1] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag); |
||
300 | } |
||
301 | } |
||
302 | result->v[2] = pixman_fixed_1; |
||
303 | return !clampflag; |
||
304 | } |
||
305 | |||
1891 | serge | 306 | PIXMAN_EXPORT void |
3931 | Serge | 307 | pixman_transform_point_31_16_affine (const pixman_transform_t *t, |
308 | const pixman_vector_48_16_t *v, |
||
309 | pixman_vector_48_16_t *result) |
||
310 | { |
||
311 | int64_t hi0, lo0, hi1, lo1; |
||
312 | |||
313 | /* input vector values must have no more than 31 bits (including sign) |
||
314 | * in the integer part */ |
||
315 | assert (v->v[0] < ((pixman_fixed_48_16_t)1 << (30 + 16))); |
||
316 | assert (v->v[0] >= -((pixman_fixed_48_16_t)1 << (30 + 16))); |
||
317 | assert (v->v[1] < ((pixman_fixed_48_16_t)1 << (30 + 16))); |
||
318 | assert (v->v[1] >= -((pixman_fixed_48_16_t)1 << (30 + 16))); |
||
319 | |||
320 | hi0 = (int64_t)t->matrix[0][0] * (v->v[0] >> 16); |
||
321 | lo0 = (int64_t)t->matrix[0][0] * (v->v[0] & 0xFFFF); |
||
322 | hi0 += (int64_t)t->matrix[0][1] * (v->v[1] >> 16); |
||
323 | lo0 += (int64_t)t->matrix[0][1] * (v->v[1] & 0xFFFF); |
||
324 | hi0 += (int64_t)t->matrix[0][2]; |
||
325 | |||
326 | hi1 = (int64_t)t->matrix[1][0] * (v->v[0] >> 16); |
||
327 | lo1 = (int64_t)t->matrix[1][0] * (v->v[0] & 0xFFFF); |
||
328 | hi1 += (int64_t)t->matrix[1][1] * (v->v[1] >> 16); |
||
329 | lo1 += (int64_t)t->matrix[1][1] * (v->v[1] & 0xFFFF); |
||
330 | hi1 += (int64_t)t->matrix[1][2]; |
||
331 | |||
332 | result->v[0] = hi0 + ((lo0 + 0x8000) >> 16); |
||
333 | result->v[1] = hi1 + ((lo1 + 0x8000) >> 16); |
||
334 | result->v[2] = pixman_fixed_1; |
||
335 | } |
||
336 | |||
337 | PIXMAN_EXPORT void |
||
338 | pixman_transform_point_31_16_3d (const pixman_transform_t *t, |
||
339 | const pixman_vector_48_16_t *v, |
||
340 | pixman_vector_48_16_t *result) |
||
341 | { |
||
342 | int i; |
||
343 | int64_t tmp[3][2]; |
||
344 | |||
345 | /* input vector values must have no more than 31 bits (including sign) |
||
346 | * in the integer part */ |
||
347 | assert (v->v[0] < ((pixman_fixed_48_16_t)1 << (30 + 16))); |
||
348 | assert (v->v[0] >= -((pixman_fixed_48_16_t)1 << (30 + 16))); |
||
349 | assert (v->v[1] < ((pixman_fixed_48_16_t)1 << (30 + 16))); |
||
350 | assert (v->v[1] >= -((pixman_fixed_48_16_t)1 << (30 + 16))); |
||
351 | assert (v->v[2] < ((pixman_fixed_48_16_t)1 << (30 + 16))); |
||
352 | assert (v->v[2] >= -((pixman_fixed_48_16_t)1 << (30 + 16))); |
||
353 | |||
354 | for (i = 0; i < 3; i++) |
||
355 | { |
||
356 | tmp[i][0] = (int64_t)t->matrix[i][0] * (v->v[0] >> 16); |
||
357 | tmp[i][1] = (int64_t)t->matrix[i][0] * (v->v[0] & 0xFFFF); |
||
358 | tmp[i][0] += (int64_t)t->matrix[i][1] * (v->v[1] >> 16); |
||
359 | tmp[i][1] += (int64_t)t->matrix[i][1] * (v->v[1] & 0xFFFF); |
||
360 | tmp[i][0] += (int64_t)t->matrix[i][2] * (v->v[2] >> 16); |
||
361 | tmp[i][1] += (int64_t)t->matrix[i][2] * (v->v[2] & 0xFFFF); |
||
362 | } |
||
363 | |||
364 | result->v[0] = tmp[0][0] + ((tmp[0][1] + 0x8000) >> 16); |
||
365 | result->v[1] = tmp[1][0] + ((tmp[1][1] + 0x8000) >> 16); |
||
366 | result->v[2] = tmp[2][0] + ((tmp[2][1] + 0x8000) >> 16); |
||
367 | } |
||
368 | |||
369 | PIXMAN_EXPORT void |
||
1891 | serge | 370 | pixman_transform_init_identity (struct pixman_transform *matrix) |
371 | { |
||
372 | int i; |
||
373 | |||
374 | memset (matrix, '\0', sizeof (struct pixman_transform)); |
||
375 | for (i = 0; i < 3; i++) |
||
376 | matrix->matrix[i][i] = F (1); |
||
377 | } |
||
378 | |||
379 | typedef pixman_fixed_32_32_t pixman_fixed_34_30_t; |
||
380 | |||
381 | PIXMAN_EXPORT pixman_bool_t |
||
382 | pixman_transform_point_3d (const struct pixman_transform *transform, |
||
383 | struct pixman_vector * vector) |
||
384 | { |
||
3931 | Serge | 385 | pixman_vector_48_16_t tmp; |
386 | tmp.v[0] = vector->vector[0]; |
||
387 | tmp.v[1] = vector->vector[1]; |
||
388 | tmp.v[2] = vector->vector[2]; |
||
1891 | serge | 389 | |
3931 | Serge | 390 | pixman_transform_point_31_16_3d (transform, &tmp, &tmp); |
1891 | serge | 391 | |
3931 | Serge | 392 | vector->vector[0] = tmp.v[0]; |
393 | vector->vector[1] = tmp.v[1]; |
||
394 | vector->vector[2] = tmp.v[2]; |
||
1891 | serge | 395 | |
3931 | Serge | 396 | return vector->vector[0] == tmp.v[0] && |
397 | vector->vector[1] == tmp.v[1] && |
||
398 | vector->vector[2] == tmp.v[2]; |
||
1891 | serge | 399 | } |
400 | |||
401 | PIXMAN_EXPORT pixman_bool_t |
||
402 | pixman_transform_point (const struct pixman_transform *transform, |
||
403 | struct pixman_vector * vector) |
||
404 | { |
||
3931 | Serge | 405 | pixman_vector_48_16_t tmp; |
406 | tmp.v[0] = vector->vector[0]; |
||
407 | tmp.v[1] = vector->vector[1]; |
||
408 | tmp.v[2] = vector->vector[2]; |
||
1891 | serge | 409 | |
3931 | Serge | 410 | if (!pixman_transform_point_31_16 (transform, &tmp, &tmp)) |
411 | return FALSE; |
||
1891 | serge | 412 | |
3931 | Serge | 413 | vector->vector[0] = tmp.v[0]; |
414 | vector->vector[1] = tmp.v[1]; |
||
415 | vector->vector[2] = tmp.v[2]; |
||
416 | |||
417 | return vector->vector[0] == tmp.v[0] && |
||
418 | vector->vector[1] == tmp.v[1] && |
||
419 | vector->vector[2] == tmp.v[2]; |
||
1891 | serge | 420 | } |
421 | |||
422 | PIXMAN_EXPORT pixman_bool_t |
||
423 | pixman_transform_multiply (struct pixman_transform * dst, |
||
424 | const struct pixman_transform *l, |
||
425 | const struct pixman_transform *r) |
||
426 | { |
||
427 | struct pixman_transform d; |
||
428 | int dx, dy; |
||
429 | int o; |
||
430 | |||
431 | for (dy = 0; dy < 3; dy++) |
||
432 | { |
||
433 | for (dx = 0; dx < 3; dx++) |
||
434 | { |
||
435 | pixman_fixed_48_16_t v; |
||
436 | pixman_fixed_32_32_t partial; |
||
437 | |||
438 | v = 0; |
||
439 | for (o = 0; o < 3; o++) |
||
440 | { |
||
441 | partial = |
||
442 | (pixman_fixed_32_32_t) l->matrix[dy][o] * |
||
443 | (pixman_fixed_32_32_t) r->matrix[o][dx]; |
||
444 | |||
3931 | Serge | 445 | v += (partial + 0x8000) >> 16; |
1891 | serge | 446 | } |
447 | |||
448 | if (v > pixman_max_fixed_48_16 || v < pixman_min_fixed_48_16) |
||
449 | return FALSE; |
||
450 | |||
451 | d.matrix[dy][dx] = (pixman_fixed_t) v; |
||
452 | } |
||
453 | } |
||
454 | |||
455 | *dst = d; |
||
456 | return TRUE; |
||
457 | } |
||
458 | |||
459 | PIXMAN_EXPORT void |
||
460 | pixman_transform_init_scale (struct pixman_transform *t, |
||
461 | pixman_fixed_t sx, |
||
462 | pixman_fixed_t sy) |
||
463 | { |
||
464 | memset (t, '\0', sizeof (struct pixman_transform)); |
||
465 | |||
466 | t->matrix[0][0] = sx; |
||
467 | t->matrix[1][1] = sy; |
||
468 | t->matrix[2][2] = F (1); |
||
469 | } |
||
470 | |||
471 | static pixman_fixed_t |
||
472 | fixed_inverse (pixman_fixed_t x) |
||
473 | { |
||
474 | return (pixman_fixed_t) ((((pixman_fixed_48_16_t) F (1)) * F (1)) / x); |
||
475 | } |
||
476 | |||
477 | PIXMAN_EXPORT pixman_bool_t |
||
478 | pixman_transform_scale (struct pixman_transform *forward, |
||
479 | struct pixman_transform *reverse, |
||
480 | pixman_fixed_t sx, |
||
481 | pixman_fixed_t sy) |
||
482 | { |
||
483 | struct pixman_transform t; |
||
484 | |||
485 | if (sx == 0 || sy == 0) |
||
486 | return FALSE; |
||
487 | |||
488 | if (forward) |
||
489 | { |
||
490 | pixman_transform_init_scale (&t, sx, sy); |
||
491 | if (!pixman_transform_multiply (forward, &t, forward)) |
||
492 | return FALSE; |
||
493 | } |
||
494 | |||
495 | if (reverse) |
||
496 | { |
||
497 | pixman_transform_init_scale (&t, fixed_inverse (sx), |
||
498 | fixed_inverse (sy)); |
||
499 | if (!pixman_transform_multiply (reverse, reverse, &t)) |
||
500 | return FALSE; |
||
501 | } |
||
502 | |||
503 | return TRUE; |
||
504 | } |
||
505 | |||
506 | PIXMAN_EXPORT void |
||
507 | pixman_transform_init_rotate (struct pixman_transform *t, |
||
508 | pixman_fixed_t c, |
||
509 | pixman_fixed_t s) |
||
510 | { |
||
511 | memset (t, '\0', sizeof (struct pixman_transform)); |
||
512 | |||
513 | t->matrix[0][0] = c; |
||
514 | t->matrix[0][1] = -s; |
||
515 | t->matrix[1][0] = s; |
||
516 | t->matrix[1][1] = c; |
||
517 | t->matrix[2][2] = F (1); |
||
518 | } |
||
519 | |||
520 | PIXMAN_EXPORT pixman_bool_t |
||
521 | pixman_transform_rotate (struct pixman_transform *forward, |
||
522 | struct pixman_transform *reverse, |
||
523 | pixman_fixed_t c, |
||
524 | pixman_fixed_t s) |
||
525 | { |
||
526 | struct pixman_transform t; |
||
527 | |||
528 | if (forward) |
||
529 | { |
||
530 | pixman_transform_init_rotate (&t, c, s); |
||
531 | if (!pixman_transform_multiply (forward, &t, forward)) |
||
532 | return FALSE; |
||
533 | } |
||
534 | |||
535 | if (reverse) |
||
536 | { |
||
537 | pixman_transform_init_rotate (&t, c, -s); |
||
538 | if (!pixman_transform_multiply (reverse, reverse, &t)) |
||
539 | return FALSE; |
||
540 | } |
||
541 | |||
542 | return TRUE; |
||
543 | } |
||
544 | |||
545 | PIXMAN_EXPORT void |
||
546 | pixman_transform_init_translate (struct pixman_transform *t, |
||
547 | pixman_fixed_t tx, |
||
548 | pixman_fixed_t ty) |
||
549 | { |
||
550 | memset (t, '\0', sizeof (struct pixman_transform)); |
||
551 | |||
552 | t->matrix[0][0] = F (1); |
||
553 | t->matrix[0][2] = tx; |
||
554 | t->matrix[1][1] = F (1); |
||
555 | t->matrix[1][2] = ty; |
||
556 | t->matrix[2][2] = F (1); |
||
557 | } |
||
558 | |||
559 | PIXMAN_EXPORT pixman_bool_t |
||
560 | pixman_transform_translate (struct pixman_transform *forward, |
||
561 | struct pixman_transform *reverse, |
||
562 | pixman_fixed_t tx, |
||
563 | pixman_fixed_t ty) |
||
564 | { |
||
565 | struct pixman_transform t; |
||
566 | |||
567 | if (forward) |
||
568 | { |
||
569 | pixman_transform_init_translate (&t, tx, ty); |
||
570 | |||
571 | if (!pixman_transform_multiply (forward, &t, forward)) |
||
572 | return FALSE; |
||
573 | } |
||
574 | |||
575 | if (reverse) |
||
576 | { |
||
577 | pixman_transform_init_translate (&t, -tx, -ty); |
||
578 | |||
579 | if (!pixman_transform_multiply (reverse, reverse, &t)) |
||
580 | return FALSE; |
||
581 | } |
||
582 | return TRUE; |
||
583 | } |
||
584 | |||
585 | PIXMAN_EXPORT pixman_bool_t |
||
586 | pixman_transform_bounds (const struct pixman_transform *matrix, |
||
587 | struct pixman_box16 * b) |
||
588 | |||
589 | { |
||
590 | struct pixman_vector v[4]; |
||
591 | int i; |
||
592 | int x1, y1, x2, y2; |
||
593 | |||
594 | v[0].vector[0] = F (b->x1); |
||
595 | v[0].vector[1] = F (b->y1); |
||
596 | v[0].vector[2] = F (1); |
||
597 | |||
598 | v[1].vector[0] = F (b->x2); |
||
599 | v[1].vector[1] = F (b->y1); |
||
600 | v[1].vector[2] = F (1); |
||
601 | |||
602 | v[2].vector[0] = F (b->x2); |
||
603 | v[2].vector[1] = F (b->y2); |
||
604 | v[2].vector[2] = F (1); |
||
605 | |||
606 | v[3].vector[0] = F (b->x1); |
||
607 | v[3].vector[1] = F (b->y2); |
||
608 | v[3].vector[2] = F (1); |
||
609 | |||
610 | for (i = 0; i < 4; i++) |
||
611 | { |
||
612 | if (!pixman_transform_point (matrix, &v[i])) |
||
613 | return FALSE; |
||
614 | |||
615 | x1 = pixman_fixed_to_int (v[i].vector[0]); |
||
616 | y1 = pixman_fixed_to_int (v[i].vector[1]); |
||
617 | x2 = pixman_fixed_to_int (pixman_fixed_ceil (v[i].vector[0])); |
||
618 | y2 = pixman_fixed_to_int (pixman_fixed_ceil (v[i].vector[1])); |
||
619 | |||
620 | if (i == 0) |
||
621 | { |
||
622 | b->x1 = x1; |
||
623 | b->y1 = y1; |
||
624 | b->x2 = x2; |
||
625 | b->y2 = y2; |
||
626 | } |
||
627 | else |
||
628 | { |
||
629 | if (x1 < b->x1) b->x1 = x1; |
||
630 | if (y1 < b->y1) b->y1 = y1; |
||
631 | if (x2 > b->x2) b->x2 = x2; |
||
632 | if (y2 > b->y2) b->y2 = y2; |
||
633 | } |
||
634 | } |
||
635 | |||
636 | return TRUE; |
||
637 | } |
||
638 | |||
639 | PIXMAN_EXPORT pixman_bool_t |
||
640 | pixman_transform_invert (struct pixman_transform * dst, |
||
641 | const struct pixman_transform *src) |
||
642 | { |
||
3931 | Serge | 643 | struct pixman_f_transform m; |
1891 | serge | 644 | |
645 | pixman_f_transform_from_pixman_transform (&m, src); |
||
646 | |||
3931 | Serge | 647 | if (!pixman_f_transform_invert (&m, &m)) |
1891 | serge | 648 | return FALSE; |
649 | |||
3931 | Serge | 650 | if (!pixman_transform_from_pixman_f_transform (dst, &m)) |
1891 | serge | 651 | return FALSE; |
652 | |||
653 | return TRUE; |
||
654 | } |
||
655 | |||
656 | static pixman_bool_t |
||
657 | within_epsilon (pixman_fixed_t a, |
||
658 | pixman_fixed_t b, |
||
659 | pixman_fixed_t epsilon) |
||
660 | { |
||
661 | pixman_fixed_t t = a - b; |
||
662 | |||
663 | if (t < 0) |
||
664 | t = -t; |
||
665 | |||
666 | return t <= epsilon; |
||
667 | } |
||
668 | |||
669 | #define EPSILON (pixman_fixed_t) (2) |
||
670 | |||
671 | #define IS_SAME(a, b) (within_epsilon (a, b, EPSILON)) |
||
672 | #define IS_ZERO(a) (within_epsilon (a, 0, EPSILON)) |
||
673 | #define IS_ONE(a) (within_epsilon (a, F (1), EPSILON)) |
||
674 | #define IS_UNIT(a) \ |
||
675 | (within_epsilon (a, F (1), EPSILON) || \ |
||
676 | within_epsilon (a, F (-1), EPSILON) || \ |
||
677 | IS_ZERO (a)) |
||
678 | #define IS_INT(a) (IS_ZERO (pixman_fixed_frac (a))) |
||
679 | |||
680 | PIXMAN_EXPORT pixman_bool_t |
||
681 | pixman_transform_is_identity (const struct pixman_transform *t) |
||
682 | { |
||
683 | return (IS_SAME (t->matrix[0][0], t->matrix[1][1]) && |
||
684 | IS_SAME (t->matrix[0][0], t->matrix[2][2]) && |
||
685 | !IS_ZERO (t->matrix[0][0]) && |
||
686 | IS_ZERO (t->matrix[0][1]) && |
||
687 | IS_ZERO (t->matrix[0][2]) && |
||
688 | IS_ZERO (t->matrix[1][0]) && |
||
689 | IS_ZERO (t->matrix[1][2]) && |
||
690 | IS_ZERO (t->matrix[2][0]) && |
||
691 | IS_ZERO (t->matrix[2][1])); |
||
692 | } |
||
693 | |||
694 | PIXMAN_EXPORT pixman_bool_t |
||
695 | pixman_transform_is_scale (const struct pixman_transform *t) |
||
696 | { |
||
697 | return (!IS_ZERO (t->matrix[0][0]) && |
||
698 | IS_ZERO (t->matrix[0][1]) && |
||
699 | IS_ZERO (t->matrix[0][2]) && |
||
700 | |||
701 | IS_ZERO (t->matrix[1][0]) && |
||
702 | !IS_ZERO (t->matrix[1][1]) && |
||
703 | IS_ZERO (t->matrix[1][2]) && |
||
704 | |||
705 | IS_ZERO (t->matrix[2][0]) && |
||
706 | IS_ZERO (t->matrix[2][1]) && |
||
707 | !IS_ZERO (t->matrix[2][2])); |
||
708 | } |
||
709 | |||
710 | PIXMAN_EXPORT pixman_bool_t |
||
711 | pixman_transform_is_int_translate (const struct pixman_transform *t) |
||
712 | { |
||
713 | return (IS_ONE (t->matrix[0][0]) && |
||
714 | IS_ZERO (t->matrix[0][1]) && |
||
715 | IS_INT (t->matrix[0][2]) && |
||
716 | |||
717 | IS_ZERO (t->matrix[1][0]) && |
||
718 | IS_ONE (t->matrix[1][1]) && |
||
719 | IS_INT (t->matrix[1][2]) && |
||
720 | |||
721 | IS_ZERO (t->matrix[2][0]) && |
||
722 | IS_ZERO (t->matrix[2][1]) && |
||
723 | IS_ONE (t->matrix[2][2])); |
||
724 | } |
||
725 | |||
726 | PIXMAN_EXPORT pixman_bool_t |
||
727 | pixman_transform_is_inverse (const struct pixman_transform *a, |
||
728 | const struct pixman_transform *b) |
||
729 | { |
||
730 | struct pixman_transform t; |
||
731 | |||
3931 | Serge | 732 | if (!pixman_transform_multiply (&t, a, b)) |
733 | return FALSE; |
||
1891 | serge | 734 | |
735 | return pixman_transform_is_identity (&t); |
||
736 | } |
||
737 | |||
738 | PIXMAN_EXPORT void |
||
739 | pixman_f_transform_from_pixman_transform (struct pixman_f_transform * ft, |
||
740 | const struct pixman_transform *t) |
||
741 | { |
||
742 | int i, j; |
||
743 | |||
744 | for (j = 0; j < 3; j++) |
||
745 | { |
||
746 | for (i = 0; i < 3; i++) |
||
747 | ft->m[j][i] = pixman_fixed_to_double (t->matrix[j][i]); |
||
748 | } |
||
749 | } |
||
750 | |||
751 | PIXMAN_EXPORT pixman_bool_t |
||
752 | pixman_transform_from_pixman_f_transform (struct pixman_transform * t, |
||
753 | const struct pixman_f_transform *ft) |
||
754 | { |
||
755 | int i, j; |
||
756 | |||
757 | for (j = 0; j < 3; j++) |
||
758 | { |
||
759 | for (i = 0; i < 3; i++) |
||
760 | { |
||
761 | double d = ft->m[j][i]; |
||
762 | if (d < -32767.0 || d > 32767.0) |
||
763 | return FALSE; |
||
764 | d = d * 65536.0 + 0.5; |
||
765 | t->matrix[j][i] = (pixman_fixed_t) floor (d); |
||
766 | } |
||
767 | } |
||
768 | |||
769 | return TRUE; |
||
770 | } |
||
771 | |||
772 | PIXMAN_EXPORT pixman_bool_t |
||
773 | pixman_f_transform_invert (struct pixman_f_transform * dst, |
||
774 | const struct pixman_f_transform *src) |
||
775 | { |
||
3931 | Serge | 776 | static const int a[3] = { 2, 2, 1 }; |
777 | static const int b[3] = { 1, 0, 0 }; |
||
778 | pixman_f_transform_t d; |
||
1891 | serge | 779 | double det; |
780 | int i, j; |
||
781 | |||
782 | det = 0; |
||
783 | for (i = 0; i < 3; i++) |
||
784 | { |
||
785 | double p; |
||
786 | int ai = a[i]; |
||
787 | int bi = b[i]; |
||
788 | p = src->m[i][0] * (src->m[ai][2] * src->m[bi][1] - |
||
789 | src->m[ai][1] * src->m[bi][2]); |
||
790 | if (i == 1) |
||
791 | p = -p; |
||
792 | det += p; |
||
793 | } |
||
794 | |||
795 | if (det == 0) |
||
796 | return FALSE; |
||
797 | |||
798 | det = 1 / det; |
||
799 | for (j = 0; j < 3; j++) |
||
800 | { |
||
801 | for (i = 0; i < 3; i++) |
||
802 | { |
||
803 | double p; |
||
804 | int ai = a[i]; |
||
805 | int aj = a[j]; |
||
806 | int bi = b[i]; |
||
807 | int bj = b[j]; |
||
808 | |||
809 | p = (src->m[ai][aj] * src->m[bi][bj] - |
||
810 | src->m[ai][bj] * src->m[bi][aj]); |
||
811 | |||
812 | if (((i + j) & 1) != 0) |
||
813 | p = -p; |
||
814 | |||
3931 | Serge | 815 | d.m[j][i] = det * p; |
1891 | serge | 816 | } |
817 | } |
||
818 | |||
3931 | Serge | 819 | *dst = d; |
820 | |||
1891 | serge | 821 | return TRUE; |
822 | } |
||
823 | |||
824 | PIXMAN_EXPORT pixman_bool_t |
||
825 | pixman_f_transform_point (const struct pixman_f_transform *t, |
||
826 | struct pixman_f_vector * v) |
||
827 | { |
||
828 | struct pixman_f_vector result; |
||
829 | int i, j; |
||
830 | double a; |
||
831 | |||
832 | for (j = 0; j < 3; j++) |
||
833 | { |
||
834 | a = 0; |
||
835 | for (i = 0; i < 3; i++) |
||
836 | a += t->m[j][i] * v->v[i]; |
||
837 | result.v[j] = a; |
||
838 | } |
||
839 | |||
840 | if (!result.v[2]) |
||
841 | return FALSE; |
||
842 | |||
843 | for (j = 0; j < 2; j++) |
||
844 | v->v[j] = result.v[j] / result.v[2]; |
||
845 | |||
846 | v->v[2] = 1; |
||
847 | |||
848 | return TRUE; |
||
849 | } |
||
850 | |||
851 | PIXMAN_EXPORT void |
||
852 | pixman_f_transform_point_3d (const struct pixman_f_transform *t, |
||
853 | struct pixman_f_vector * v) |
||
854 | { |
||
855 | struct pixman_f_vector result; |
||
856 | int i, j; |
||
857 | double a; |
||
858 | |||
859 | for (j = 0; j < 3; j++) |
||
860 | { |
||
861 | a = 0; |
||
862 | for (i = 0; i < 3; i++) |
||
863 | a += t->m[j][i] * v->v[i]; |
||
864 | result.v[j] = a; |
||
865 | } |
||
866 | |||
867 | *v = result; |
||
868 | } |
||
869 | |||
870 | PIXMAN_EXPORT void |
||
871 | pixman_f_transform_multiply (struct pixman_f_transform * dst, |
||
872 | const struct pixman_f_transform *l, |
||
873 | const struct pixman_f_transform *r) |
||
874 | { |
||
875 | struct pixman_f_transform d; |
||
876 | int dx, dy; |
||
877 | int o; |
||
878 | |||
879 | for (dy = 0; dy < 3; dy++) |
||
880 | { |
||
881 | for (dx = 0; dx < 3; dx++) |
||
882 | { |
||
883 | double v = 0; |
||
884 | for (o = 0; o < 3; o++) |
||
885 | v += l->m[dy][o] * r->m[o][dx]; |
||
886 | d.m[dy][dx] = v; |
||
887 | } |
||
888 | } |
||
889 | |||
890 | *dst = d; |
||
891 | } |
||
892 | |||
893 | PIXMAN_EXPORT void |
||
894 | pixman_f_transform_init_scale (struct pixman_f_transform *t, |
||
895 | double sx, |
||
896 | double sy) |
||
897 | { |
||
898 | t->m[0][0] = sx; |
||
899 | t->m[0][1] = 0; |
||
900 | t->m[0][2] = 0; |
||
901 | t->m[1][0] = 0; |
||
902 | t->m[1][1] = sy; |
||
903 | t->m[1][2] = 0; |
||
904 | t->m[2][0] = 0; |
||
905 | t->m[2][1] = 0; |
||
906 | t->m[2][2] = 1; |
||
907 | } |
||
908 | |||
909 | PIXMAN_EXPORT pixman_bool_t |
||
910 | pixman_f_transform_scale (struct pixman_f_transform *forward, |
||
911 | struct pixman_f_transform *reverse, |
||
912 | double sx, |
||
913 | double sy) |
||
914 | { |
||
915 | struct pixman_f_transform t; |
||
916 | |||
917 | if (sx == 0 || sy == 0) |
||
918 | return FALSE; |
||
919 | |||
920 | if (forward) |
||
921 | { |
||
922 | pixman_f_transform_init_scale (&t, sx, sy); |
||
923 | pixman_f_transform_multiply (forward, &t, forward); |
||
924 | } |
||
925 | |||
926 | if (reverse) |
||
927 | { |
||
928 | pixman_f_transform_init_scale (&t, 1 / sx, 1 / sy); |
||
929 | pixman_f_transform_multiply (reverse, reverse, &t); |
||
930 | } |
||
931 | |||
932 | return TRUE; |
||
933 | } |
||
934 | |||
935 | PIXMAN_EXPORT void |
||
936 | pixman_f_transform_init_rotate (struct pixman_f_transform *t, |
||
937 | double c, |
||
938 | double s) |
||
939 | { |
||
940 | t->m[0][0] = c; |
||
941 | t->m[0][1] = -s; |
||
942 | t->m[0][2] = 0; |
||
943 | t->m[1][0] = s; |
||
944 | t->m[1][1] = c; |
||
945 | t->m[1][2] = 0; |
||
946 | t->m[2][0] = 0; |
||
947 | t->m[2][1] = 0; |
||
948 | t->m[2][2] = 1; |
||
949 | } |
||
950 | |||
951 | PIXMAN_EXPORT pixman_bool_t |
||
952 | pixman_f_transform_rotate (struct pixman_f_transform *forward, |
||
953 | struct pixman_f_transform *reverse, |
||
954 | double c, |
||
955 | double s) |
||
956 | { |
||
957 | struct pixman_f_transform t; |
||
958 | |||
959 | if (forward) |
||
960 | { |
||
961 | pixman_f_transform_init_rotate (&t, c, s); |
||
962 | pixman_f_transform_multiply (forward, &t, forward); |
||
963 | } |
||
964 | |||
965 | if (reverse) |
||
966 | { |
||
967 | pixman_f_transform_init_rotate (&t, c, -s); |
||
968 | pixman_f_transform_multiply (reverse, reverse, &t); |
||
969 | } |
||
970 | |||
971 | return TRUE; |
||
972 | } |
||
973 | |||
974 | PIXMAN_EXPORT void |
||
975 | pixman_f_transform_init_translate (struct pixman_f_transform *t, |
||
976 | double tx, |
||
977 | double ty) |
||
978 | { |
||
979 | t->m[0][0] = 1; |
||
980 | t->m[0][1] = 0; |
||
981 | t->m[0][2] = tx; |
||
982 | t->m[1][0] = 0; |
||
983 | t->m[1][1] = 1; |
||
984 | t->m[1][2] = ty; |
||
985 | t->m[2][0] = 0; |
||
986 | t->m[2][1] = 0; |
||
987 | t->m[2][2] = 1; |
||
988 | } |
||
989 | |||
990 | PIXMAN_EXPORT pixman_bool_t |
||
991 | pixman_f_transform_translate (struct pixman_f_transform *forward, |
||
992 | struct pixman_f_transform *reverse, |
||
993 | double tx, |
||
994 | double ty) |
||
995 | { |
||
996 | struct pixman_f_transform t; |
||
997 | |||
998 | if (forward) |
||
999 | { |
||
1000 | pixman_f_transform_init_translate (&t, tx, ty); |
||
1001 | pixman_f_transform_multiply (forward, &t, forward); |
||
1002 | } |
||
1003 | |||
1004 | if (reverse) |
||
1005 | { |
||
1006 | pixman_f_transform_init_translate (&t, -tx, -ty); |
||
1007 | pixman_f_transform_multiply (reverse, reverse, &t); |
||
1008 | } |
||
1009 | |||
1010 | return TRUE; |
||
1011 | } |
||
1012 | |||
1013 | PIXMAN_EXPORT pixman_bool_t |
||
1014 | pixman_f_transform_bounds (const struct pixman_f_transform *t, |
||
1015 | struct pixman_box16 * b) |
||
1016 | { |
||
1017 | struct pixman_f_vector v[4]; |
||
1018 | int i; |
||
1019 | int x1, y1, x2, y2; |
||
1020 | |||
1021 | v[0].v[0] = b->x1; |
||
1022 | v[0].v[1] = b->y1; |
||
1023 | v[0].v[2] = 1; |
||
1024 | v[1].v[0] = b->x2; |
||
1025 | v[1].v[1] = b->y1; |
||
1026 | v[1].v[2] = 1; |
||
1027 | v[2].v[0] = b->x2; |
||
1028 | v[2].v[1] = b->y2; |
||
1029 | v[2].v[2] = 1; |
||
1030 | v[3].v[0] = b->x1; |
||
1031 | v[3].v[1] = b->y2; |
||
1032 | v[3].v[2] = 1; |
||
1033 | |||
1034 | for (i = 0; i < 4; i++) |
||
1035 | { |
||
1036 | if (!pixman_f_transform_point (t, &v[i])) |
||
1037 | return FALSE; |
||
1038 | |||
1039 | x1 = floor (v[i].v[0]); |
||
1040 | y1 = floor (v[i].v[1]); |
||
1041 | x2 = ceil (v[i].v[0]); |
||
1042 | y2 = ceil (v[i].v[1]); |
||
1043 | |||
1044 | if (i == 0) |
||
1045 | { |
||
1046 | b->x1 = x1; |
||
1047 | b->y1 = y1; |
||
1048 | b->x2 = x2; |
||
1049 | b->y2 = y2; |
||
1050 | } |
||
1051 | else |
||
1052 | { |
||
1053 | if (x1 < b->x1) b->x1 = x1; |
||
1054 | if (y1 < b->y1) b->y1 = y1; |
||
1055 | if (x2 > b->x2) b->x2 = x2; |
||
1056 | if (y2 > b->y2) b->y2 = y2; |
||
1057 | } |
||
1058 | } |
||
1059 | |||
1060 | return TRUE; |
||
1061 | } |
||
1062 | |||
1063 | PIXMAN_EXPORT void |
||
1064 | pixman_f_transform_init_identity (struct pixman_f_transform *t) |
||
1065 | { |
||
1066 | int i, j; |
||
1067 | |||
1068 | for (j = 0; j < 3; j++) |
||
1069 | { |
||
1070 | for (i = 0; i < 3; i++) |
||
1071 | t->m[j][i] = i == j ? 1 : 0; |
||
1072 | } |
||
1073 | }>>>>>>>>>>>>>>>>>>>>>=>>>>>>>>>>>><>><>>><>><>>><>><>>><>><>>><>><>>><>>>>>><>><>>><>><>>><>><>>><>>><>=>>>><>><>><>><>><>><>><>><>> |