Line data Source code
1 : /* cairo - a vector graphics library with display and print output
2 : *
3 : * Copyright © 2004 Keith Packard
4 : *
5 : * This library is free software; you can redistribute it and/or
6 : * modify it either under the terms of the GNU Lesser General Public
7 : * License version 2.1 as published by the Free Software Foundation
8 : * (the "LGPL") or, at your option, under the terms of the Mozilla
9 : * Public License Version 1.1 (the "MPL"). If you do not alter this
10 : * notice, a recipient may use your version of this file under either
11 : * the MPL or the LGPL.
12 : *
13 : * You should have received a copy of the LGPL along with this library
14 : * in the file COPYING-LGPL-2.1; if not, write to the Free Software
15 : * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
16 : * You should have received a copy of the MPL along with this library
17 : * in the file COPYING-MPL-1.1
18 : *
19 : * The contents of this file are subject to the Mozilla Public License
20 : * Version 1.1 (the "License"); you may not use this file except in
21 : * compliance with the License. You may obtain a copy of the License at
22 : * http://www.mozilla.org/MPL/
23 : *
24 : * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
25 : * OF ANY KIND, either express or implied. See the LGPL or the MPL for
26 : * the specific language governing rights and limitations.
27 : *
28 : * The Original Code is the cairo graphics library.
29 : *
30 : * The Initial Developer of the Original Code is Keith Packard
31 : *
32 : * Contributor(s):
33 : * Keith R. Packard <keithp@keithp.com>
34 : */
35 :
36 : #include "cairoint.h"
37 :
38 : #if HAVE_UINT64_T
39 :
40 : #define uint64_lo32(i) ((i) & 0xffffffff)
41 : #define uint64_hi32(i) ((i) >> 32)
42 : #define uint64_lo(i) ((i) & 0xffffffff)
43 : #define uint64_hi(i) ((i) >> 32)
44 : #define uint64_shift32(i) ((i) << 32)
45 : #define uint64_carry32 (((uint64_t) 1) << 32)
46 :
47 : #define _cairo_uint32s_to_uint64(h,l) ((uint64_t) (h) << 32 | (l))
48 :
49 : #else
50 :
51 : #define uint64_lo32(i) ((i).lo)
52 : #define uint64_hi32(i) ((i).hi)
53 :
54 : static cairo_uint64_t
55 : uint64_lo (cairo_uint64_t i)
56 : {
57 : cairo_uint64_t s;
58 :
59 : s.lo = i.lo;
60 : s.hi = 0;
61 : return s;
62 : }
63 :
64 : static cairo_uint64_t
65 : uint64_hi (cairo_uint64_t i)
66 : {
67 : cairo_uint64_t s;
68 :
69 : s.lo = i.hi;
70 : s.hi = 0;
71 : return s;
72 : }
73 :
74 : static cairo_uint64_t
75 : uint64_shift32 (cairo_uint64_t i)
76 : {
77 : cairo_uint64_t s;
78 :
79 : s.lo = 0;
80 : s.hi = i.lo;
81 : return s;
82 : }
83 :
84 : static const cairo_uint64_t uint64_carry32 = { 0, 1 };
85 :
86 : cairo_uint64_t
87 : _cairo_uint32_to_uint64 (uint32_t i)
88 : {
89 : cairo_uint64_t q;
90 :
91 : q.lo = i;
92 : q.hi = 0;
93 : return q;
94 : }
95 :
96 : cairo_int64_t
97 : _cairo_int32_to_int64 (int32_t i)
98 : {
99 : cairo_uint64_t q;
100 :
101 : q.lo = i;
102 : q.hi = i < 0 ? -1 : 0;
103 : return q;
104 : }
105 :
106 : static cairo_uint64_t
107 : _cairo_uint32s_to_uint64 (uint32_t h, uint32_t l)
108 : {
109 : cairo_uint64_t q;
110 :
111 : q.lo = l;
112 : q.hi = h;
113 : return q;
114 : }
115 :
116 : cairo_uint64_t
117 : _cairo_uint64_add (cairo_uint64_t a, cairo_uint64_t b)
118 : {
119 : cairo_uint64_t s;
120 :
121 : s.hi = a.hi + b.hi;
122 : s.lo = a.lo + b.lo;
123 : if (s.lo < a.lo)
124 : s.hi++;
125 : return s;
126 : }
127 :
128 : cairo_uint64_t
129 : _cairo_uint64_sub (cairo_uint64_t a, cairo_uint64_t b)
130 : {
131 : cairo_uint64_t s;
132 :
133 : s.hi = a.hi - b.hi;
134 : s.lo = a.lo - b.lo;
135 : if (s.lo > a.lo)
136 : s.hi--;
137 : return s;
138 : }
139 :
140 : #define uint32_lo(i) ((i) & 0xffff)
141 : #define uint32_hi(i) ((i) >> 16)
142 : #define uint32_carry16 ((1) << 16)
143 :
144 : cairo_uint64_t
145 : _cairo_uint32x32_64_mul (uint32_t a, uint32_t b)
146 : {
147 : cairo_uint64_t s;
148 :
149 : uint16_t ah, al, bh, bl;
150 : uint32_t r0, r1, r2, r3;
151 :
152 : al = uint32_lo (a);
153 : ah = uint32_hi (a);
154 : bl = uint32_lo (b);
155 : bh = uint32_hi (b);
156 :
157 : r0 = (uint32_t) al * bl;
158 : r1 = (uint32_t) al * bh;
159 : r2 = (uint32_t) ah * bl;
160 : r3 = (uint32_t) ah * bh;
161 :
162 : r1 += uint32_hi(r0); /* no carry possible */
163 : r1 += r2; /* but this can carry */
164 : if (r1 < r2) /* check */
165 : r3 += uint32_carry16;
166 :
167 : s.hi = r3 + uint32_hi(r1);
168 : s.lo = (uint32_lo (r1) << 16) + uint32_lo (r0);
169 : return s;
170 : }
171 :
172 : cairo_int64_t
173 : _cairo_int32x32_64_mul (int32_t a, int32_t b)
174 : {
175 : cairo_int64_t s;
176 : s = _cairo_uint32x32_64_mul ((uint32_t) a, (uint32_t) b);
177 : if (a < 0)
178 : s.hi -= b;
179 : if (b < 0)
180 : s.hi -= a;
181 : return s;
182 : }
183 :
184 : cairo_uint64_t
185 : _cairo_uint64_mul (cairo_uint64_t a, cairo_uint64_t b)
186 : {
187 : cairo_uint64_t s;
188 :
189 : s = _cairo_uint32x32_64_mul (a.lo, b.lo);
190 : s.hi += a.lo * b.hi + a.hi * b.lo;
191 : return s;
192 : }
193 :
194 : cairo_uint64_t
195 : _cairo_uint64_lsl (cairo_uint64_t a, int shift)
196 : {
197 : if (shift >= 32)
198 : {
199 : a.hi = a.lo;
200 : a.lo = 0;
201 : shift -= 32;
202 : }
203 : if (shift)
204 : {
205 : a.hi = a.hi << shift | a.lo >> (32 - shift);
206 : a.lo = a.lo << shift;
207 : }
208 : return a;
209 : }
210 :
211 : cairo_uint64_t
212 : _cairo_uint64_rsl (cairo_uint64_t a, int shift)
213 : {
214 : if (shift >= 32)
215 : {
216 : a.lo = a.hi;
217 : a.hi = 0;
218 : shift -= 32;
219 : }
220 : if (shift)
221 : {
222 : a.lo = a.lo >> shift | a.hi << (32 - shift);
223 : a.hi = a.hi >> shift;
224 : }
225 : return a;
226 : }
227 :
228 : #define _cairo_uint32_rsa(a,n) ((uint32_t) (((int32_t) (a)) >> (n)))
229 :
230 : cairo_int64_t
231 : _cairo_uint64_rsa (cairo_int64_t a, int shift)
232 : {
233 : if (shift >= 32)
234 : {
235 : a.lo = a.hi;
236 : a.hi = _cairo_uint32_rsa (a.hi, 31);
237 : shift -= 32;
238 : }
239 : if (shift)
240 : {
241 : a.lo = a.lo >> shift | a.hi << (32 - shift);
242 : a.hi = _cairo_uint32_rsa (a.hi, shift);
243 : }
244 : return a;
245 : }
246 :
247 : int
248 : _cairo_uint64_lt (cairo_uint64_t a, cairo_uint64_t b)
249 : {
250 : return (a.hi < b.hi ||
251 : (a.hi == b.hi && a.lo < b.lo));
252 : }
253 :
254 : int
255 : _cairo_uint64_eq (cairo_uint64_t a, cairo_uint64_t b)
256 : {
257 : return a.hi == b.hi && a.lo == b.lo;
258 : }
259 :
260 : int
261 : _cairo_int64_lt (cairo_int64_t a, cairo_int64_t b)
262 : {
263 : if (_cairo_int64_negative (a) && !_cairo_int64_negative (b))
264 : return 1;
265 : if (!_cairo_int64_negative (a) && _cairo_int64_negative (b))
266 : return 0;
267 : return _cairo_uint64_lt (a, b);
268 : }
269 :
270 : int
271 : _cairo_uint64_cmp (cairo_uint64_t a, cairo_uint64_t b)
272 : {
273 : if (a.hi < b.hi)
274 : return -1;
275 : else if (a.hi > b.hi)
276 : return 1;
277 : else if (a.lo < b.lo)
278 : return -1;
279 : else if (a.lo > b.lo)
280 : return 1;
281 : else
282 : return 0;
283 : }
284 :
285 : int
286 : _cairo_int64_cmp (cairo_int64_t a, cairo_int64_t b)
287 : {
288 : if (_cairo_int64_negative (a) && !_cairo_int64_negative (b))
289 : return -1;
290 : if (!_cairo_int64_negative (a) && _cairo_int64_negative (b))
291 : return 1;
292 :
293 : return _cairo_uint64_cmp (a, b);
294 : }
295 :
296 : cairo_uint64_t
297 : _cairo_uint64_not (cairo_uint64_t a)
298 : {
299 : a.lo = ~a.lo;
300 : a.hi = ~a.hi;
301 : return a;
302 : }
303 :
304 : cairo_uint64_t
305 : _cairo_uint64_negate (cairo_uint64_t a)
306 : {
307 : a.lo = ~a.lo;
308 : a.hi = ~a.hi;
309 : if (++a.lo == 0)
310 : ++a.hi;
311 : return a;
312 : }
313 :
314 : /*
315 : * Simple bit-at-a-time divide.
316 : */
317 : cairo_uquorem64_t
318 : _cairo_uint64_divrem (cairo_uint64_t num, cairo_uint64_t den)
319 : {
320 : cairo_uquorem64_t qr;
321 : cairo_uint64_t bit;
322 : cairo_uint64_t quo;
323 :
324 : bit = _cairo_uint32_to_uint64 (1);
325 :
326 : /* normalize to make den >= num, but not overflow */
327 : while (_cairo_uint64_lt (den, num) && (den.hi & 0x80000000) == 0)
328 : {
329 : bit = _cairo_uint64_lsl (bit, 1);
330 : den = _cairo_uint64_lsl (den, 1);
331 : }
332 : quo = _cairo_uint32_to_uint64 (0);
333 :
334 : /* generate quotient, one bit at a time */
335 : while (bit.hi | bit.lo)
336 : {
337 : if (_cairo_uint64_le (den, num))
338 : {
339 : num = _cairo_uint64_sub (num, den);
340 : quo = _cairo_uint64_add (quo, bit);
341 : }
342 : bit = _cairo_uint64_rsl (bit, 1);
343 : den = _cairo_uint64_rsl (den, 1);
344 : }
345 : qr.quo = quo;
346 : qr.rem = num;
347 : return qr;
348 : }
349 :
350 : #endif /* !HAVE_UINT64_T */
351 :
352 : #if HAVE_UINT128_T
353 : cairo_uquorem128_t
354 : _cairo_uint128_divrem (cairo_uint128_t num, cairo_uint128_t den)
355 : {
356 : cairo_uquorem128_t qr;
357 :
358 : qr.quo = num / den;
359 : qr.rem = num % den;
360 : return qr;
361 : }
362 :
363 : #else
364 :
365 : cairo_uint128_t
366 0 : _cairo_uint32_to_uint128 (uint32_t i)
367 : {
368 : cairo_uint128_t q;
369 :
370 0 : q.lo = _cairo_uint32_to_uint64 (i);
371 0 : q.hi = _cairo_uint32_to_uint64 (0);
372 0 : return q;
373 : }
374 :
375 : cairo_int128_t
376 0 : _cairo_int32_to_int128 (int32_t i)
377 : {
378 : cairo_int128_t q;
379 :
380 0 : q.lo = _cairo_int32_to_int64 (i);
381 0 : q.hi = _cairo_int32_to_int64 (i < 0 ? -1 : 0);
382 0 : return q;
383 : }
384 :
385 : cairo_uint128_t
386 0 : _cairo_uint64_to_uint128 (cairo_uint64_t i)
387 : {
388 : cairo_uint128_t q;
389 :
390 0 : q.lo = i;
391 0 : q.hi = _cairo_uint32_to_uint64 (0);
392 0 : return q;
393 : }
394 :
395 : cairo_int128_t
396 0 : _cairo_int64_to_int128 (cairo_int64_t i)
397 : {
398 : cairo_int128_t q;
399 :
400 0 : q.lo = i;
401 0 : q.hi = _cairo_int32_to_int64 (_cairo_int64_negative(i) ? -1 : 0);
402 0 : return q;
403 : }
404 :
405 : cairo_uint128_t
406 0 : _cairo_uint128_add (cairo_uint128_t a, cairo_uint128_t b)
407 : {
408 : cairo_uint128_t s;
409 :
410 0 : s.hi = _cairo_uint64_add (a.hi, b.hi);
411 0 : s.lo = _cairo_uint64_add (a.lo, b.lo);
412 0 : if (_cairo_uint64_lt (s.lo, a.lo))
413 0 : s.hi = _cairo_uint64_add (s.hi, _cairo_uint32_to_uint64 (1));
414 0 : return s;
415 : }
416 :
417 : cairo_uint128_t
418 0 : _cairo_uint128_sub (cairo_uint128_t a, cairo_uint128_t b)
419 : {
420 : cairo_uint128_t s;
421 :
422 0 : s.hi = _cairo_uint64_sub (a.hi, b.hi);
423 0 : s.lo = _cairo_uint64_sub (a.lo, b.lo);
424 0 : if (_cairo_uint64_gt (s.lo, a.lo))
425 0 : s.hi = _cairo_uint64_sub (s.hi, _cairo_uint32_to_uint64(1));
426 0 : return s;
427 : }
428 :
429 : cairo_uint128_t
430 0 : _cairo_uint64x64_128_mul (cairo_uint64_t a, cairo_uint64_t b)
431 : {
432 : cairo_uint128_t s;
433 : uint32_t ah, al, bh, bl;
434 : cairo_uint64_t r0, r1, r2, r3;
435 :
436 0 : al = uint64_lo32 (a);
437 0 : ah = uint64_hi32 (a);
438 0 : bl = uint64_lo32 (b);
439 0 : bh = uint64_hi32 (b);
440 :
441 0 : r0 = _cairo_uint32x32_64_mul (al, bl);
442 0 : r1 = _cairo_uint32x32_64_mul (al, bh);
443 0 : r2 = _cairo_uint32x32_64_mul (ah, bl);
444 0 : r3 = _cairo_uint32x32_64_mul (ah, bh);
445 :
446 0 : r1 = _cairo_uint64_add (r1, uint64_hi (r0)); /* no carry possible */
447 0 : r1 = _cairo_uint64_add (r1, r2); /* but this can carry */
448 0 : if (_cairo_uint64_lt (r1, r2)) /* check */
449 0 : r3 = _cairo_uint64_add (r3, uint64_carry32);
450 :
451 0 : s.hi = _cairo_uint64_add (r3, uint64_hi(r1));
452 0 : s.lo = _cairo_uint64_add (uint64_shift32 (r1),
453 : uint64_lo (r0));
454 0 : return s;
455 : }
456 :
457 : cairo_int128_t
458 0 : _cairo_int64x64_128_mul (cairo_int64_t a, cairo_int64_t b)
459 : {
460 : cairo_int128_t s;
461 0 : s = _cairo_uint64x64_128_mul (_cairo_int64_to_uint64(a),
462 : _cairo_int64_to_uint64(b));
463 0 : if (_cairo_int64_negative (a))
464 0 : s.hi = _cairo_uint64_sub (s.hi,
465 : _cairo_int64_to_uint64 (b));
466 0 : if (_cairo_int64_negative (b))
467 0 : s.hi = _cairo_uint64_sub (s.hi,
468 : _cairo_int64_to_uint64 (a));
469 0 : return s;
470 : }
471 :
472 : cairo_uint128_t
473 0 : _cairo_uint128_mul (cairo_uint128_t a, cairo_uint128_t b)
474 : {
475 : cairo_uint128_t s;
476 :
477 0 : s = _cairo_uint64x64_128_mul (a.lo, b.lo);
478 0 : s.hi = _cairo_uint64_add (s.hi,
479 : _cairo_uint64_mul (a.lo, b.hi));
480 0 : s.hi = _cairo_uint64_add (s.hi,
481 : _cairo_uint64_mul (a.hi, b.lo));
482 0 : return s;
483 : }
484 :
485 : cairo_uint128_t
486 0 : _cairo_uint128_lsl (cairo_uint128_t a, int shift)
487 : {
488 0 : if (shift >= 64)
489 : {
490 0 : a.hi = a.lo;
491 0 : a.lo = _cairo_uint32_to_uint64 (0);
492 0 : shift -= 64;
493 : }
494 0 : if (shift)
495 : {
496 0 : a.hi = _cairo_uint64_add (_cairo_uint64_lsl (a.hi, shift),
497 : _cairo_uint64_rsl (a.lo, (64 - shift)));
498 0 : a.lo = _cairo_uint64_lsl (a.lo, shift);
499 : }
500 0 : return a;
501 : }
502 :
503 : cairo_uint128_t
504 0 : _cairo_uint128_rsl (cairo_uint128_t a, int shift)
505 : {
506 0 : if (shift >= 64)
507 : {
508 0 : a.lo = a.hi;
509 0 : a.hi = _cairo_uint32_to_uint64 (0);
510 0 : shift -= 64;
511 : }
512 0 : if (shift)
513 : {
514 0 : a.lo = _cairo_uint64_add (_cairo_uint64_rsl (a.lo, shift),
515 : _cairo_uint64_lsl (a.hi, (64 - shift)));
516 0 : a.hi = _cairo_uint64_rsl (a.hi, shift);
517 : }
518 0 : return a;
519 : }
520 :
521 : cairo_uint128_t
522 0 : _cairo_uint128_rsa (cairo_int128_t a, int shift)
523 : {
524 0 : if (shift >= 64)
525 : {
526 0 : a.lo = a.hi;
527 0 : a.hi = _cairo_uint64_rsa (a.hi, 64-1);
528 0 : shift -= 64;
529 : }
530 0 : if (shift)
531 : {
532 0 : a.lo = _cairo_uint64_add (_cairo_uint64_rsl (a.lo, shift),
533 : _cairo_uint64_lsl (a.hi, (64 - shift)));
534 0 : a.hi = _cairo_uint64_rsa (a.hi, shift);
535 : }
536 0 : return a;
537 : }
538 :
539 : int
540 0 : _cairo_uint128_lt (cairo_uint128_t a, cairo_uint128_t b)
541 : {
542 0 : return (_cairo_uint64_lt (a.hi, b.hi) ||
543 0 : (_cairo_uint64_eq (a.hi, b.hi) &&
544 0 : _cairo_uint64_lt (a.lo, b.lo)));
545 : }
546 :
547 : int
548 0 : _cairo_int128_lt (cairo_int128_t a, cairo_int128_t b)
549 : {
550 0 : if (_cairo_int128_negative (a) && !_cairo_int128_negative (b))
551 0 : return 1;
552 0 : if (!_cairo_int128_negative (a) && _cairo_int128_negative (b))
553 0 : return 0;
554 0 : return _cairo_uint128_lt (a, b);
555 : }
556 :
557 : int
558 0 : _cairo_uint128_cmp (cairo_uint128_t a, cairo_uint128_t b)
559 : {
560 : int cmp;
561 :
562 0 : cmp = _cairo_uint64_cmp (a.hi, b.hi);
563 0 : if (cmp)
564 0 : return cmp;
565 0 : return _cairo_uint64_cmp (a.lo, b.lo);
566 : }
567 :
568 : int
569 0 : _cairo_int128_cmp (cairo_int128_t a, cairo_int128_t b)
570 : {
571 0 : if (_cairo_int128_negative (a) && !_cairo_int128_negative (b))
572 0 : return -1;
573 0 : if (!_cairo_int128_negative (a) && _cairo_int128_negative (b))
574 0 : return 1;
575 :
576 0 : return _cairo_uint128_cmp (a, b);
577 : }
578 :
579 : int
580 0 : _cairo_uint128_eq (cairo_uint128_t a, cairo_uint128_t b)
581 : {
582 0 : return (_cairo_uint64_eq (a.hi, b.hi) &&
583 0 : _cairo_uint64_eq (a.lo, b.lo));
584 : }
585 :
586 : #if HAVE_UINT64_T
587 : #define _cairo_msbset64(q) (q & ((uint64_t) 1 << 63))
588 : #else
589 : #define _cairo_msbset64(q) (q.hi & ((uint32_t) 1 << 31))
590 : #endif
591 :
592 : cairo_uquorem128_t
593 0 : _cairo_uint128_divrem (cairo_uint128_t num, cairo_uint128_t den)
594 : {
595 : cairo_uquorem128_t qr;
596 : cairo_uint128_t bit;
597 : cairo_uint128_t quo;
598 :
599 0 : bit = _cairo_uint32_to_uint128 (1);
600 :
601 : /* normalize to make den >= num, but not overflow */
602 0 : while (_cairo_uint128_lt (den, num) && !_cairo_msbset64(den.hi))
603 : {
604 0 : bit = _cairo_uint128_lsl (bit, 1);
605 0 : den = _cairo_uint128_lsl (den, 1);
606 : }
607 0 : quo = _cairo_uint32_to_uint128 (0);
608 :
609 : /* generate quotient, one bit at a time */
610 0 : while (_cairo_uint128_ne (bit, _cairo_uint32_to_uint128(0)))
611 : {
612 0 : if (_cairo_uint128_le (den, num))
613 : {
614 0 : num = _cairo_uint128_sub (num, den);
615 0 : quo = _cairo_uint128_add (quo, bit);
616 : }
617 0 : bit = _cairo_uint128_rsl (bit, 1);
618 0 : den = _cairo_uint128_rsl (den, 1);
619 : }
620 0 : qr.quo = quo;
621 0 : qr.rem = num;
622 0 : return qr;
623 : }
624 :
625 : cairo_int128_t
626 0 : _cairo_int128_negate (cairo_int128_t a)
627 : {
628 0 : a.lo = _cairo_uint64_not (a.lo);
629 0 : a.hi = _cairo_uint64_not (a.hi);
630 0 : return _cairo_uint128_add (a, _cairo_uint32_to_uint128 (1));
631 : }
632 :
633 : cairo_int128_t
634 0 : _cairo_int128_not (cairo_int128_t a)
635 : {
636 0 : a.lo = _cairo_uint64_not (a.lo);
637 0 : a.hi = _cairo_uint64_not (a.hi);
638 0 : return a;
639 : }
640 :
641 : #endif /* !HAVE_UINT128_T */
642 :
643 : cairo_quorem128_t
644 0 : _cairo_int128_divrem (cairo_int128_t num, cairo_int128_t den)
645 : {
646 0 : int num_neg = _cairo_int128_negative (num);
647 0 : int den_neg = _cairo_int128_negative (den);
648 : cairo_uquorem128_t uqr;
649 : cairo_quorem128_t qr;
650 :
651 0 : if (num_neg)
652 0 : num = _cairo_int128_negate (num);
653 0 : if (den_neg)
654 0 : den = _cairo_int128_negate (den);
655 0 : uqr = _cairo_uint128_divrem (num, den);
656 0 : if (num_neg)
657 0 : qr.rem = _cairo_int128_negate (uqr.rem);
658 : else
659 0 : qr.rem = uqr.rem;
660 0 : if (num_neg != den_neg)
661 0 : qr.quo = _cairo_int128_negate (uqr.quo);
662 : else
663 0 : qr.quo = uqr.quo;
664 0 : return qr;
665 : }
666 :
667 : /**
668 : * _cairo_uint_96by64_32x64_divrem:
669 : *
670 : * Compute a 32 bit quotient and 64 bit remainder of a 96 bit unsigned
671 : * dividend and 64 bit divisor. If the quotient doesn't fit into 32
672 : * bits then the returned remainder is equal to the divisor, and the
673 : * quotient is the largest representable 64 bit integer. It is an
674 : * error to call this function with the high 32 bits of @num being
675 : * non-zero. */
676 : cairo_uquorem64_t
677 0 : _cairo_uint_96by64_32x64_divrem (cairo_uint128_t num,
678 : cairo_uint64_t den)
679 : {
680 : cairo_uquorem64_t result;
681 0 : cairo_uint64_t B = _cairo_uint32s_to_uint64 (1, 0);
682 :
683 : /* These are the high 64 bits of the *96* bit numerator. We're
684 : * going to represent the numerator as xB + y, where x is a 64,
685 : * and y is a 32 bit number. */
686 0 : cairo_uint64_t x = _cairo_uint128_to_uint64 (_cairo_uint128_rsl(num, 32));
687 :
688 : /* Initialise the result to indicate overflow. */
689 0 : result.quo = _cairo_uint32s_to_uint64 (-1U, -1U);
690 0 : result.rem = den;
691 :
692 : /* Don't bother if the quotient is going to overflow. */
693 0 : if (_cairo_uint64_ge (x, den)) {
694 0 : return /* overflow */ result;
695 : }
696 :
697 0 : if (_cairo_uint64_lt (x, B)) {
698 : /* When the final quotient is known to fit in 32 bits, then
699 : * num < 2^64 if and only if den < 2^32. */
700 0 : return _cairo_uint64_divrem (_cairo_uint128_to_uint64 (num), den);
701 : }
702 : else {
703 : /* Denominator is >= 2^32. the numerator is >= 2^64, and the
704 : * division won't overflow: need two divrems. Write the
705 : * numerator and denominator as
706 : *
707 : * num = xB + y x : 64 bits, y : 32 bits
708 : * den = uB + v u, v : 32 bits
709 : */
710 0 : uint32_t y = _cairo_uint128_to_uint32 (num);
711 0 : uint32_t u = uint64_hi32 (den);
712 0 : uint32_t v = _cairo_uint64_to_uint32 (den);
713 :
714 : /* Compute a lower bound approximate quotient of num/den
715 : * from x/(u+1). Then we have
716 : *
717 : * x = q(u+1) + r ; q : 32 bits, r <= u : 32 bits.
718 : *
719 : * xB + y = q(u+1)B + (rB+y)
720 : * = q(uB + B + v - v) + (rB+y)
721 : * = q(uB + v) + qB - qv + (rB+y)
722 : * = q(uB + v) + q(B-v) + (rB+y)
723 : *
724 : * The true quotient of num/den then is q plus the
725 : * contribution of q(B-v) + (rB+y). The main contribution
726 : * comes from the term q(B-v), with the term (rB+y) only
727 : * contributing at most one part.
728 : *
729 : * The term q(B-v) must fit into 64 bits, since q fits into 32
730 : * bits on account of being a lower bound to the true
731 : * quotient, and as B-v <= 2^32, we may safely use a single
732 : * 64/64 bit division to find its contribution. */
733 :
734 : cairo_uquorem64_t quorem;
735 : cairo_uint64_t remainder; /* will contain final remainder */
736 : uint32_t quotient; /* will contain final quotient. */
737 : uint32_t q;
738 : uint32_t r;
739 :
740 : /* Approximate quotient by dividing the high 64 bits of num by
741 : * u+1. Watch out for overflow of u+1. */
742 0 : if (u+1) {
743 0 : quorem = _cairo_uint64_divrem (x, _cairo_uint32_to_uint64 (u+1));
744 0 : q = _cairo_uint64_to_uint32 (quorem.quo);
745 0 : r = _cairo_uint64_to_uint32 (quorem.rem);
746 : }
747 : else {
748 0 : q = uint64_hi32 (x);
749 0 : r = _cairo_uint64_to_uint32 (x);
750 : }
751 0 : quotient = q;
752 :
753 : /* Add the main term's contribution to quotient. Note B-v =
754 : * -v as an uint32 (unless v = 0) */
755 0 : if (v)
756 0 : quorem = _cairo_uint64_divrem (_cairo_uint32x32_64_mul (q, -v), den);
757 : else
758 0 : quorem = _cairo_uint64_divrem (_cairo_uint32s_to_uint64 (q, 0), den);
759 0 : quotient += _cairo_uint64_to_uint32 (quorem.quo);
760 :
761 : /* Add the contribution of the subterm and start computing the
762 : * true remainder. */
763 0 : remainder = _cairo_uint32s_to_uint64 (r, y);
764 0 : if (_cairo_uint64_ge (remainder, den)) {
765 0 : remainder = _cairo_uint64_sub (remainder, den);
766 0 : quotient++;
767 : }
768 :
769 : /* Add the contribution of the main term's remainder. The
770 : * funky test here checks that remainder + main_rem >= den,
771 : * taking into account overflow of the addition. */
772 0 : remainder = _cairo_uint64_add (remainder, quorem.rem);
773 0 : if (_cairo_uint64_ge (remainder, den) ||
774 0 : _cairo_uint64_lt (remainder, quorem.rem))
775 : {
776 0 : remainder = _cairo_uint64_sub (remainder, den);
777 0 : quotient++;
778 : }
779 :
780 0 : result.quo = _cairo_uint32_to_uint64 (quotient);
781 0 : result.rem = remainder;
782 : }
783 0 : return result;
784 : }
785 :
786 : cairo_quorem64_t
787 0 : _cairo_int_96by64_32x64_divrem (cairo_int128_t num, cairo_int64_t den)
788 : {
789 0 : int num_neg = _cairo_int128_negative (num);
790 0 : int den_neg = _cairo_int64_negative (den);
791 : cairo_uint64_t nonneg_den;
792 : cairo_uquorem64_t uqr;
793 : cairo_quorem64_t qr;
794 :
795 0 : if (num_neg)
796 0 : num = _cairo_int128_negate (num);
797 0 : if (den_neg)
798 0 : nonneg_den = _cairo_int64_negate (den);
799 : else
800 0 : nonneg_den = den;
801 :
802 0 : uqr = _cairo_uint_96by64_32x64_divrem (num, nonneg_den);
803 0 : if (_cairo_uint64_eq (uqr.rem, nonneg_den)) {
804 : /* bail on overflow. */
805 0 : qr.quo = _cairo_uint32s_to_uint64 (0x7FFFFFFF, -1U);
806 0 : qr.rem = den;
807 0 : return qr;
808 : }
809 :
810 0 : if (num_neg)
811 0 : qr.rem = _cairo_int64_negate (uqr.rem);
812 : else
813 0 : qr.rem = uqr.rem;
814 0 : if (num_neg != den_neg)
815 0 : qr.quo = _cairo_int64_negate (uqr.quo);
816 : else
817 0 : qr.quo = uqr.quo;
818 0 : return qr;
819 : }
|
