Line data Source code
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
28 : #include <config.h>
29 : #endif
30 :
31 : #include <math.h>
32 : #include <string.h>
33 : #include "pixman-private.h"
34 :
35 : #define F(x) pixman_int_to_fixed (x)
36 :
37 : static force_inline int
38 : count_leading_zeros (uint32_t x)
39 : {
40 : #ifdef __GNUC__
41 0 : 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 0 : assert(div < ((uint64_t)1 << 48));
74 :
75 0 : remainder = hi % div;
76 0 : *result_hi = hi / div;
77 :
78 0 : tmp = (remainder << 16) + (lo >> 48);
79 0 : result_lo = tmp / div;
80 0 : remainder = tmp % div;
81 :
82 0 : tmp = (remainder << 16) + ((lo >> 32) & 0xFFFF);
83 0 : result_lo = (result_lo << 16) + (tmp / div);
84 0 : remainder = tmp % div;
85 :
86 0 : tmp = (remainder << 16) + ((lo >> 16) & 0xFFFF);
87 0 : result_lo = (result_lo << 16) + (tmp / div);
88 0 : remainder = tmp % div;
89 :
90 0 : tmp = (remainder << 16) + (lo & 0xFFFF);
91 0 : result_lo = (result_lo << 16) + (tmp / div);
92 0 : remainder = tmp % div;
93 :
94 : /* round to nearest */
95 0 : if (remainder * 2 >= div && ++result_lo == 0)
96 0 : *result_hi += 1;
97 :
98 0 : return result_lo;
99 : }
100 :
101 : /* signed division (128-bit by 49-bit) with rounding to nearest */
102 : static inline int64_t
103 0 : 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 0 : int sign = 0;
110 0 : if (div < 0)
111 : {
112 0 : div = -div;
113 0 : sign ^= 1;
114 : }
115 0 : if (hi < 0)
116 : {
117 0 : if (lo != 0)
118 0 : hi++;
119 0 : hi = -hi;
120 0 : lo = -lo;
121 0 : sign ^= 1;
122 : }
123 0 : result_lo = rounded_udiv_128_by_48 (hi, lo, div, &result_hi);
124 0 : if (sign)
125 : {
126 0 : if (result_lo != 0)
127 0 : result_hi++;
128 0 : result_hi = -result_hi;
129 0 : result_lo = -result_lo;
130 : }
131 0 : if (signed_result_hi)
132 : {
133 0 : *signed_result_hi = result_hi;
134 : }
135 0 : 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 0 : hi += lo >> 16;
151 0 : lo &= 0xFFFF;
152 :
153 0 : if (scalebits <= 0)
154 : {
155 0 : *rlo = hi >> (-scalebits);
156 0 : *rhi = *rlo >> 63;
157 : }
158 : else
159 : {
160 0 : *rhi = hi >> (64 - scalebits);
161 0 : *rlo = (uint64_t)hi << scalebits;
162 0 : if (scalebits < 16)
163 0 : *rlo += lo >> (16 - scalebits);
164 : else
165 0 : *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 0 : if ((lo >> 63) != hi)
177 : {
178 0 : *clampflag = TRUE;
179 0 : return hi >= 0 ? INT64_MAX : INT64_MIN;
180 : }
181 : else
182 : {
183 0 : 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 0 : 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 0 : 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 0 : assert (v->v[0] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
210 0 : assert (v->v[0] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
211 0 : assert (v->v[1] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
212 0 : assert (v->v[1] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
213 0 : assert (v->v[2] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
214 0 : assert (v->v[2] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
215 :
216 0 : for (i = 0; i < 3; i++)
217 : {
218 0 : tmp[i][0] = (int64_t)t->matrix[i][0] * (v->v[0] >> 16);
219 0 : tmp[i][1] = (int64_t)t->matrix[i][0] * (v->v[0] & 0xFFFF);
220 0 : tmp[i][0] += (int64_t)t->matrix[i][1] * (v->v[1] >> 16);
221 0 : tmp[i][1] += (int64_t)t->matrix[i][1] * (v->v[1] & 0xFFFF);
222 0 : tmp[i][0] += (int64_t)t->matrix[i][2] * (v->v[2] >> 16);
223 0 : 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 0 : divint = tmp[2][0] + (tmp[2][1] >> 16);
231 0 : divfrac = tmp[2][1] & 0xFFFF;
232 :
233 0 : if (divint == pixman_fixed_1 && divfrac == 0)
234 : {
235 : /*
236 : * this is a simple affine transformation
237 : */
238 0 : result->v[0] = tmp[0][0] + ((tmp[0][1] + 0x8000) >> 16);
239 0 : result->v[1] = tmp[1][0] + ((tmp[1][1] + 0x8000) >> 16);
240 0 : result->v[2] = pixman_fixed_1;
241 : }
242 0 : 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 0 : clampflag = TRUE;
249 :
250 0 : result->v[0] = tmp[0][0] + ((tmp[0][1] + 0x8000) >> 16);
251 0 : result->v[1] = tmp[1][0] + ((tmp[1][1] + 0x8000) >> 16);
252 :
253 0 : if (result->v[0] > 0)
254 0 : result->v[0] = INT64_MAX;
255 0 : else if (result->v[0] < 0)
256 0 : result->v[0] = INT64_MIN;
257 :
258 0 : if (result->v[1] > 0)
259 0 : result->v[1] = INT64_MAX;
260 0 : else if (result->v[1] < 0)
261 0 : result->v[1] = INT64_MIN;
262 : }
263 : else
264 : {
265 : /*
266 : * projective transformation, analyze the top 32 bits of the divisor
267 : */
268 0 : int32_t hi32divbits = divint >> 32;
269 0 : if (hi32divbits < 0)
270 0 : hi32divbits = ~hi32divbits;
271 :
272 0 : if (hi32divbits == 0)
273 : {
274 : /* the divisor is small, we can actually keep all the bits */
275 : int64_t hi, rhi, lo, rlo;
276 0 : int64_t div = (divint << 16) + divfrac;
277 :
278 0 : fixed_64_16_to_int128 (tmp[0][0], tmp[0][1], &hi, &lo, 32);
279 0 : rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi);
280 0 : result->v[0] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag);
281 :
282 0 : fixed_64_16_to_int128 (tmp[1][0], tmp[1][1], &hi, &lo, 32);
283 0 : rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi);
284 0 : 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 0 : int shift = 32 - count_leading_zeros (hi32divbits);
291 0 : fixed_64_16_to_int128 (divint, divfrac, &hi, &div, 16 - shift);
292 :
293 0 : fixed_64_16_to_int128 (tmp[0][0], tmp[0][1], &hi, &lo, 32 - shift);
294 0 : rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi);
295 0 : result->v[0] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag);
296 :
297 0 : fixed_64_16_to_int128 (tmp[1][0], tmp[1][1], &hi, &lo, 32 - shift);
298 0 : rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi);
299 0 : result->v[1] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag);
300 : }
301 : }
302 0 : result->v[2] = pixman_fixed_1;
303 0 : return !clampflag;
304 : }
305 :
306 : PIXMAN_EXPORT void
307 0 : 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 0 : assert (v->v[0] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
316 0 : assert (v->v[0] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
317 0 : assert (v->v[1] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
318 0 : assert (v->v[1] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
319 :
320 0 : hi0 = (int64_t)t->matrix[0][0] * (v->v[0] >> 16);
321 0 : lo0 = (int64_t)t->matrix[0][0] * (v->v[0] & 0xFFFF);
322 0 : hi0 += (int64_t)t->matrix[0][1] * (v->v[1] >> 16);
323 0 : lo0 += (int64_t)t->matrix[0][1] * (v->v[1] & 0xFFFF);
324 0 : hi0 += (int64_t)t->matrix[0][2];
325 :
326 0 : hi1 = (int64_t)t->matrix[1][0] * (v->v[0] >> 16);
327 0 : lo1 = (int64_t)t->matrix[1][0] * (v->v[0] & 0xFFFF);
328 0 : hi1 += (int64_t)t->matrix[1][1] * (v->v[1] >> 16);
329 0 : lo1 += (int64_t)t->matrix[1][1] * (v->v[1] & 0xFFFF);
330 0 : hi1 += (int64_t)t->matrix[1][2];
331 :
332 0 : result->v[0] = hi0 + ((lo0 + 0x8000) >> 16);
333 0 : result->v[1] = hi1 + ((lo1 + 0x8000) >> 16);
334 0 : result->v[2] = pixman_fixed_1;
335 0 : }
336 :
337 : PIXMAN_EXPORT void
338 0 : 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 0 : assert (v->v[0] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
348 0 : assert (v->v[0] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
349 0 : assert (v->v[1] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
350 0 : assert (v->v[1] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
351 0 : assert (v->v[2] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
352 0 : assert (v->v[2] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
353 :
354 0 : for (i = 0; i < 3; i++)
355 : {
356 0 : tmp[i][0] = (int64_t)t->matrix[i][0] * (v->v[0] >> 16);
357 0 : tmp[i][1] = (int64_t)t->matrix[i][0] * (v->v[0] & 0xFFFF);
358 0 : tmp[i][0] += (int64_t)t->matrix[i][1] * (v->v[1] >> 16);
359 0 : tmp[i][1] += (int64_t)t->matrix[i][1] * (v->v[1] & 0xFFFF);
360 0 : tmp[i][0] += (int64_t)t->matrix[i][2] * (v->v[2] >> 16);
361 0 : tmp[i][1] += (int64_t)t->matrix[i][2] * (v->v[2] & 0xFFFF);
362 : }
363 :
364 0 : result->v[0] = tmp[0][0] + ((tmp[0][1] + 0x8000) >> 16);
365 0 : result->v[1] = tmp[1][0] + ((tmp[1][1] + 0x8000) >> 16);
366 0 : result->v[2] = tmp[2][0] + ((tmp[2][1] + 0x8000) >> 16);
367 0 : }
368 :
369 : PIXMAN_EXPORT void
370 0 : pixman_transform_init_identity (struct pixman_transform *matrix)
371 : {
372 : int i;
373 :
374 0 : memset (matrix, '\0', sizeof (struct pixman_transform));
375 0 : for (i = 0; i < 3; i++)
376 0 : matrix->matrix[i][i] = F (1);
377 0 : }
378 :
379 : typedef pixman_fixed_32_32_t pixman_fixed_34_30_t;
380 :
381 : PIXMAN_EXPORT pixman_bool_t
382 0 : pixman_transform_point_3d (const struct pixman_transform *transform,
383 : struct pixman_vector * vector)
384 : {
385 : pixman_vector_48_16_t tmp;
386 0 : tmp.v[0] = vector->vector[0];
387 0 : tmp.v[1] = vector->vector[1];
388 0 : tmp.v[2] = vector->vector[2];
389 :
390 0 : pixman_transform_point_31_16_3d (transform, &tmp, &tmp);
391 :
392 0 : vector->vector[0] = tmp.v[0];
393 0 : vector->vector[1] = tmp.v[1];
394 0 : vector->vector[2] = tmp.v[2];
395 :
396 0 : return vector->vector[0] == tmp.v[0] &&
397 0 : vector->vector[1] == tmp.v[1] &&
398 0 : vector->vector[2] == tmp.v[2];
399 : }
400 :
401 : PIXMAN_EXPORT pixman_bool_t
402 0 : pixman_transform_point (const struct pixman_transform *transform,
403 : struct pixman_vector * vector)
404 : {
405 : pixman_vector_48_16_t tmp;
406 0 : tmp.v[0] = vector->vector[0];
407 0 : tmp.v[1] = vector->vector[1];
408 0 : tmp.v[2] = vector->vector[2];
409 :
410 0 : if (!pixman_transform_point_31_16 (transform, &tmp, &tmp))
411 0 : return FALSE;
412 :
413 0 : vector->vector[0] = tmp.v[0];
414 0 : vector->vector[1] = tmp.v[1];
415 0 : vector->vector[2] = tmp.v[2];
416 :
417 0 : return vector->vector[0] == tmp.v[0] &&
418 0 : vector->vector[1] == tmp.v[1] &&
419 0 : vector->vector[2] == tmp.v[2];
420 : }
421 :
422 : PIXMAN_EXPORT pixman_bool_t
423 0 : 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 0 : for (dy = 0; dy < 3; dy++)
432 : {
433 0 : for (dx = 0; dx < 3; dx++)
434 : {
435 : pixman_fixed_48_16_t v;
436 : pixman_fixed_32_32_t partial;
437 :
438 0 : v = 0;
439 0 : for (o = 0; o < 3; o++)
440 : {
441 0 : partial =
442 0 : (pixman_fixed_32_32_t) l->matrix[dy][o] *
443 0 : (pixman_fixed_32_32_t) r->matrix[o][dx];
444 :
445 0 : v += (partial + 0x8000) >> 16;
446 : }
447 :
448 0 : if (v > pixman_max_fixed_48_16 || v < pixman_min_fixed_48_16)
449 0 : return FALSE;
450 :
451 0 : d.matrix[dy][dx] = (pixman_fixed_t) v;
452 : }
453 : }
454 :
455 0 : *dst = d;
456 0 : return TRUE;
457 : }
458 :
459 : PIXMAN_EXPORT void
460 0 : pixman_transform_init_scale (struct pixman_transform *t,
461 : pixman_fixed_t sx,
462 : pixman_fixed_t sy)
463 : {
464 0 : memset (t, '\0', sizeof (struct pixman_transform));
465 :
466 0 : t->matrix[0][0] = sx;
467 0 : t->matrix[1][1] = sy;
468 0 : t->matrix[2][2] = F (1);
469 0 : }
470 :
471 : static pixman_fixed_t
472 0 : fixed_inverse (pixman_fixed_t x)
473 : {
474 0 : return (pixman_fixed_t) ((((pixman_fixed_48_16_t) F (1)) * F (1)) / x);
475 : }
476 :
477 : PIXMAN_EXPORT pixman_bool_t
478 0 : 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 0 : if (sx == 0 || sy == 0)
486 0 : return FALSE;
487 :
488 0 : if (forward)
489 : {
490 0 : pixman_transform_init_scale (&t, sx, sy);
491 0 : if (!pixman_transform_multiply (forward, &t, forward))
492 0 : return FALSE;
493 : }
494 :
495 0 : if (reverse)
496 : {
497 0 : pixman_transform_init_scale (&t, fixed_inverse (sx),
498 : fixed_inverse (sy));
499 0 : if (!pixman_transform_multiply (reverse, reverse, &t))
500 0 : return FALSE;
501 : }
502 :
503 0 : return TRUE;
504 : }
505 :
506 : PIXMAN_EXPORT void
507 0 : pixman_transform_init_rotate (struct pixman_transform *t,
508 : pixman_fixed_t c,
509 : pixman_fixed_t s)
510 : {
511 0 : memset (t, '\0', sizeof (struct pixman_transform));
512 :
513 0 : t->matrix[0][0] = c;
514 0 : t->matrix[0][1] = -s;
515 0 : t->matrix[1][0] = s;
516 0 : t->matrix[1][1] = c;
517 0 : t->matrix[2][2] = F (1);
518 0 : }
519 :
520 : PIXMAN_EXPORT pixman_bool_t
521 0 : 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 0 : if (forward)
529 : {
530 0 : pixman_transform_init_rotate (&t, c, s);
531 0 : if (!pixman_transform_multiply (forward, &t, forward))
532 0 : return FALSE;
533 : }
534 :
535 0 : if (reverse)
536 : {
537 0 : pixman_transform_init_rotate (&t, c, -s);
538 0 : if (!pixman_transform_multiply (reverse, reverse, &t))
539 0 : return FALSE;
540 : }
541 :
542 0 : return TRUE;
543 : }
544 :
545 : PIXMAN_EXPORT void
546 0 : pixman_transform_init_translate (struct pixman_transform *t,
547 : pixman_fixed_t tx,
548 : pixman_fixed_t ty)
549 : {
550 0 : memset (t, '\0', sizeof (struct pixman_transform));
551 :
552 0 : t->matrix[0][0] = F (1);
553 0 : t->matrix[0][2] = tx;
554 0 : t->matrix[1][1] = F (1);
555 0 : t->matrix[1][2] = ty;
556 0 : t->matrix[2][2] = F (1);
557 0 : }
558 :
559 : PIXMAN_EXPORT pixman_bool_t
560 0 : 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 0 : if (forward)
568 : {
569 0 : pixman_transform_init_translate (&t, tx, ty);
570 :
571 0 : if (!pixman_transform_multiply (forward, &t, forward))
572 0 : return FALSE;
573 : }
574 :
575 0 : if (reverse)
576 : {
577 0 : pixman_transform_init_translate (&t, -tx, -ty);
578 :
579 0 : if (!pixman_transform_multiply (reverse, reverse, &t))
580 0 : return FALSE;
581 : }
582 0 : return TRUE;
583 : }
584 :
585 : PIXMAN_EXPORT pixman_bool_t
586 0 : 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 0 : v[0].vector[0] = F (b->x1);
595 0 : v[0].vector[1] = F (b->y1);
596 0 : v[0].vector[2] = F (1);
597 :
598 0 : v[1].vector[0] = F (b->x2);
599 0 : v[1].vector[1] = F (b->y1);
600 0 : v[1].vector[2] = F (1);
601 :
602 0 : v[2].vector[0] = F (b->x2);
603 0 : v[2].vector[1] = F (b->y2);
604 0 : v[2].vector[2] = F (1);
605 :
606 0 : v[3].vector[0] = F (b->x1);
607 0 : v[3].vector[1] = F (b->y2);
608 0 : v[3].vector[2] = F (1);
609 :
610 0 : for (i = 0; i < 4; i++)
611 : {
612 0 : if (!pixman_transform_point (matrix, &v[i]))
613 0 : return FALSE;
614 :
615 0 : x1 = pixman_fixed_to_int (v[i].vector[0]);
616 0 : y1 = pixman_fixed_to_int (v[i].vector[1]);
617 0 : x2 = pixman_fixed_to_int (pixman_fixed_ceil (v[i].vector[0]));
618 0 : y2 = pixman_fixed_to_int (pixman_fixed_ceil (v[i].vector[1]));
619 :
620 0 : if (i == 0)
621 : {
622 0 : b->x1 = x1;
623 0 : b->y1 = y1;
624 0 : b->x2 = x2;
625 0 : b->y2 = y2;
626 : }
627 : else
628 : {
629 0 : if (x1 < b->x1) b->x1 = x1;
630 0 : if (y1 < b->y1) b->y1 = y1;
631 0 : if (x2 > b->x2) b->x2 = x2;
632 0 : if (y2 > b->y2) b->y2 = y2;
633 : }
634 : }
635 :
636 0 : return TRUE;
637 : }
638 :
639 : PIXMAN_EXPORT pixman_bool_t
640 0 : pixman_transform_invert (struct pixman_transform * dst,
641 : const struct pixman_transform *src)
642 : {
643 : struct pixman_f_transform m;
644 :
645 0 : pixman_f_transform_from_pixman_transform (&m, src);
646 :
647 0 : if (!pixman_f_transform_invert (&m, &m))
648 0 : return FALSE;
649 :
650 0 : if (!pixman_transform_from_pixman_f_transform (dst, &m))
651 0 : return FALSE;
652 :
653 0 : return TRUE;
654 : }
655 :
656 : static pixman_bool_t
657 0 : within_epsilon (pixman_fixed_t a,
658 : pixman_fixed_t b,
659 : pixman_fixed_t epsilon)
660 : {
661 0 : pixman_fixed_t t = a - b;
662 :
663 0 : if (t < 0)
664 0 : t = -t;
665 :
666 0 : 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 0 : pixman_transform_is_identity (const struct pixman_transform *t)
682 : {
683 0 : return (IS_SAME (t->matrix[0][0], t->matrix[1][1]) &&
684 0 : IS_SAME (t->matrix[0][0], t->matrix[2][2]) &&
685 0 : !IS_ZERO (t->matrix[0][0]) &&
686 0 : IS_ZERO (t->matrix[0][1]) &&
687 0 : IS_ZERO (t->matrix[0][2]) &&
688 0 : IS_ZERO (t->matrix[1][0]) &&
689 0 : IS_ZERO (t->matrix[1][2]) &&
690 0 : IS_ZERO (t->matrix[2][0]) &&
691 0 : IS_ZERO (t->matrix[2][1]));
692 : }
693 :
694 : PIXMAN_EXPORT pixman_bool_t
695 0 : pixman_transform_is_scale (const struct pixman_transform *t)
696 : {
697 0 : return (!IS_ZERO (t->matrix[0][0]) &&
698 0 : IS_ZERO (t->matrix[0][1]) &&
699 0 : IS_ZERO (t->matrix[0][2]) &&
700 :
701 0 : IS_ZERO (t->matrix[1][0]) &&
702 0 : !IS_ZERO (t->matrix[1][1]) &&
703 0 : IS_ZERO (t->matrix[1][2]) &&
704 :
705 0 : IS_ZERO (t->matrix[2][0]) &&
706 0 : IS_ZERO (t->matrix[2][1]) &&
707 0 : !IS_ZERO (t->matrix[2][2]));
708 : }
709 :
710 : PIXMAN_EXPORT pixman_bool_t
711 0 : pixman_transform_is_int_translate (const struct pixman_transform *t)
712 : {
713 0 : return (IS_ONE (t->matrix[0][0]) &&
714 0 : IS_ZERO (t->matrix[0][1]) &&
715 0 : IS_INT (t->matrix[0][2]) &&
716 :
717 0 : IS_ZERO (t->matrix[1][0]) &&
718 0 : IS_ONE (t->matrix[1][1]) &&
719 0 : IS_INT (t->matrix[1][2]) &&
720 :
721 0 : IS_ZERO (t->matrix[2][0]) &&
722 0 : IS_ZERO (t->matrix[2][1]) &&
723 0 : IS_ONE (t->matrix[2][2]));
724 : }
725 :
726 : PIXMAN_EXPORT pixman_bool_t
727 0 : pixman_transform_is_inverse (const struct pixman_transform *a,
728 : const struct pixman_transform *b)
729 : {
730 : struct pixman_transform t;
731 :
732 0 : if (!pixman_transform_multiply (&t, a, b))
733 0 : return FALSE;
734 :
735 0 : return pixman_transform_is_identity (&t);
736 : }
737 :
738 : PIXMAN_EXPORT void
739 0 : pixman_f_transform_from_pixman_transform (struct pixman_f_transform * ft,
740 : const struct pixman_transform *t)
741 : {
742 : int i, j;
743 :
744 0 : for (j = 0; j < 3; j++)
745 : {
746 0 : for (i = 0; i < 3; i++)
747 0 : ft->m[j][i] = pixman_fixed_to_double (t->matrix[j][i]);
748 : }
749 0 : }
750 :
751 : PIXMAN_EXPORT pixman_bool_t
752 0 : pixman_transform_from_pixman_f_transform (struct pixman_transform * t,
753 : const struct pixman_f_transform *ft)
754 : {
755 : int i, j;
756 :
757 0 : for (j = 0; j < 3; j++)
758 : {
759 0 : for (i = 0; i < 3; i++)
760 : {
761 0 : double d = ft->m[j][i];
762 0 : if (d < -32767.0 || d > 32767.0)
763 0 : return FALSE;
764 0 : d = d * 65536.0 + 0.5;
765 0 : t->matrix[j][i] = (pixman_fixed_t) floor (d);
766 : }
767 : }
768 :
769 0 : return TRUE;
770 : }
771 :
772 : PIXMAN_EXPORT pixman_bool_t
773 0 : pixman_f_transform_invert (struct pixman_f_transform * dst,
774 : const struct pixman_f_transform *src)
775 : {
776 : static const int a[3] = { 2, 2, 1 };
777 : static const int b[3] = { 1, 0, 0 };
778 : pixman_f_transform_t d;
779 : double det;
780 : int i, j;
781 :
782 0 : det = 0;
783 0 : for (i = 0; i < 3; i++)
784 : {
785 : double p;
786 0 : int ai = a[i];
787 0 : int bi = b[i];
788 0 : p = src->m[i][0] * (src->m[ai][2] * src->m[bi][1] -
789 0 : src->m[ai][1] * src->m[bi][2]);
790 0 : if (i == 1)
791 0 : p = -p;
792 0 : det += p;
793 : }
794 :
795 0 : if (det == 0)
796 0 : return FALSE;
797 :
798 0 : det = 1 / det;
799 0 : for (j = 0; j < 3; j++)
800 : {
801 0 : for (i = 0; i < 3; i++)
802 : {
803 : double p;
804 0 : int ai = a[i];
805 0 : int aj = a[j];
806 0 : int bi = b[i];
807 0 : int bj = b[j];
808 :
809 0 : p = (src->m[ai][aj] * src->m[bi][bj] -
810 0 : src->m[ai][bj] * src->m[bi][aj]);
811 :
812 0 : if (((i + j) & 1) != 0)
813 0 : p = -p;
814 :
815 0 : d.m[j][i] = det * p;
816 : }
817 : }
818 :
819 0 : *dst = d;
820 :
821 0 : return TRUE;
822 : }
823 :
824 : PIXMAN_EXPORT pixman_bool_t
825 0 : 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 0 : for (j = 0; j < 3; j++)
833 : {
834 0 : a = 0;
835 0 : for (i = 0; i < 3; i++)
836 0 : a += t->m[j][i] * v->v[i];
837 0 : result.v[j] = a;
838 : }
839 :
840 0 : if (!result.v[2])
841 0 : return FALSE;
842 :
843 0 : for (j = 0; j < 2; j++)
844 0 : v->v[j] = result.v[j] / result.v[2];
845 :
846 0 : v->v[2] = 1;
847 :
848 0 : return TRUE;
849 : }
850 :
851 : PIXMAN_EXPORT void
852 0 : 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 0 : for (j = 0; j < 3; j++)
860 : {
861 0 : a = 0;
862 0 : for (i = 0; i < 3; i++)
863 0 : a += t->m[j][i] * v->v[i];
864 0 : result.v[j] = a;
865 : }
866 :
867 0 : *v = result;
868 0 : }
869 :
870 : PIXMAN_EXPORT void
871 0 : 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 0 : for (dy = 0; dy < 3; dy++)
880 : {
881 0 : for (dx = 0; dx < 3; dx++)
882 : {
883 0 : double v = 0;
884 0 : for (o = 0; o < 3; o++)
885 0 : v += l->m[dy][o] * r->m[o][dx];
886 0 : d.m[dy][dx] = v;
887 : }
888 : }
889 :
890 0 : *dst = d;
891 0 : }
892 :
893 : PIXMAN_EXPORT void
894 0 : pixman_f_transform_init_scale (struct pixman_f_transform *t,
895 : double sx,
896 : double sy)
897 : {
898 0 : t->m[0][0] = sx;
899 0 : t->m[0][1] = 0;
900 0 : t->m[0][2] = 0;
901 0 : t->m[1][0] = 0;
902 0 : t->m[1][1] = sy;
903 0 : t->m[1][2] = 0;
904 0 : t->m[2][0] = 0;
905 0 : t->m[2][1] = 0;
906 0 : t->m[2][2] = 1;
907 0 : }
908 :
909 : PIXMAN_EXPORT pixman_bool_t
910 0 : 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 0 : if (sx == 0 || sy == 0)
918 0 : return FALSE;
919 :
920 0 : if (forward)
921 : {
922 0 : pixman_f_transform_init_scale (&t, sx, sy);
923 0 : pixman_f_transform_multiply (forward, &t, forward);
924 : }
925 :
926 0 : if (reverse)
927 : {
928 0 : pixman_f_transform_init_scale (&t, 1 / sx, 1 / sy);
929 0 : pixman_f_transform_multiply (reverse, reverse, &t);
930 : }
931 :
932 0 : return TRUE;
933 : }
934 :
935 : PIXMAN_EXPORT void
936 0 : pixman_f_transform_init_rotate (struct pixman_f_transform *t,
937 : double c,
938 : double s)
939 : {
940 0 : t->m[0][0] = c;
941 0 : t->m[0][1] = -s;
942 0 : t->m[0][2] = 0;
943 0 : t->m[1][0] = s;
944 0 : t->m[1][1] = c;
945 0 : t->m[1][2] = 0;
946 0 : t->m[2][0] = 0;
947 0 : t->m[2][1] = 0;
948 0 : t->m[2][2] = 1;
949 0 : }
950 :
951 : PIXMAN_EXPORT pixman_bool_t
952 0 : 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 0 : if (forward)
960 : {
961 0 : pixman_f_transform_init_rotate (&t, c, s);
962 0 : pixman_f_transform_multiply (forward, &t, forward);
963 : }
964 :
965 0 : if (reverse)
966 : {
967 0 : pixman_f_transform_init_rotate (&t, c, -s);
968 0 : pixman_f_transform_multiply (reverse, reverse, &t);
969 : }
970 :
971 0 : return TRUE;
972 : }
973 :
974 : PIXMAN_EXPORT void
975 0 : pixman_f_transform_init_translate (struct pixman_f_transform *t,
976 : double tx,
977 : double ty)
978 : {
979 0 : t->m[0][0] = 1;
980 0 : t->m[0][1] = 0;
981 0 : t->m[0][2] = tx;
982 0 : t->m[1][0] = 0;
983 0 : t->m[1][1] = 1;
984 0 : t->m[1][2] = ty;
985 0 : t->m[2][0] = 0;
986 0 : t->m[2][1] = 0;
987 0 : t->m[2][2] = 1;
988 0 : }
989 :
990 : PIXMAN_EXPORT pixman_bool_t
991 0 : 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 0 : if (forward)
999 : {
1000 0 : pixman_f_transform_init_translate (&t, tx, ty);
1001 0 : pixman_f_transform_multiply (forward, &t, forward);
1002 : }
1003 :
1004 0 : if (reverse)
1005 : {
1006 0 : pixman_f_transform_init_translate (&t, -tx, -ty);
1007 0 : pixman_f_transform_multiply (reverse, reverse, &t);
1008 : }
1009 :
1010 0 : return TRUE;
1011 : }
1012 :
1013 : PIXMAN_EXPORT pixman_bool_t
1014 0 : 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 0 : v[0].v[0] = b->x1;
1022 0 : v[0].v[1] = b->y1;
1023 0 : v[0].v[2] = 1;
1024 0 : v[1].v[0] = b->x2;
1025 0 : v[1].v[1] = b->y1;
1026 0 : v[1].v[2] = 1;
1027 0 : v[2].v[0] = b->x2;
1028 0 : v[2].v[1] = b->y2;
1029 0 : v[2].v[2] = 1;
1030 0 : v[3].v[0] = b->x1;
1031 0 : v[3].v[1] = b->y2;
1032 0 : v[3].v[2] = 1;
1033 :
1034 0 : for (i = 0; i < 4; i++)
1035 : {
1036 0 : if (!pixman_f_transform_point (t, &v[i]))
1037 0 : return FALSE;
1038 :
1039 0 : x1 = floor (v[i].v[0]);
1040 0 : y1 = floor (v[i].v[1]);
1041 0 : x2 = ceil (v[i].v[0]);
1042 0 : y2 = ceil (v[i].v[1]);
1043 :
1044 0 : if (i == 0)
1045 : {
1046 0 : b->x1 = x1;
1047 0 : b->y1 = y1;
1048 0 : b->x2 = x2;
1049 0 : b->y2 = y2;
1050 : }
1051 : else
1052 : {
1053 0 : if (x1 < b->x1) b->x1 = x1;
1054 0 : if (y1 < b->y1) b->y1 = y1;
1055 0 : if (x2 > b->x2) b->x2 = x2;
1056 0 : if (y2 > b->y2) b->y2 = y2;
1057 : }
1058 : }
1059 :
1060 0 : return TRUE;
1061 : }
1062 :
1063 : PIXMAN_EXPORT void
1064 0 : pixman_f_transform_init_identity (struct pixman_f_transform *t)
1065 : {
1066 : int i, j;
1067 :
1068 0 : for (j = 0; j < 3; j++)
1069 : {
1070 0 : for (i = 0; i < 3; i++)
1071 0 : t->m[j][i] = i == j ? 1 : 0;
1072 : }
1073 0 : }
|
