Subversion Repositories Scribus

Rev

Rev 14952 | Details | Compare with Previous | Last modification | View Log | RSS feed

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