Back to index

lightning-sunbird  0.9+nobinonly
cairo-wideint.c
Go to the documentation of this file.
00001 /*
00002  * $Id: cairo-wideint.c,v 1.1.4.1 2005/09/27 23:09:01 vladimir%pobox.com Exp $
00003  *
00004  * Copyright © 2004 Keith Packard
00005  *
00006  * This library is free software; you can redistribute it and/or
00007  * modify it either under the terms of the GNU Lesser General Public
00008  * License version 2.1 as published by the Free Software Foundation
00009  * (the "LGPL") or, at your option, under the terms of the Mozilla
00010  * Public License Version 1.1 (the "MPL"). If you do not alter this
00011  * notice, a recipient may use your version of this file under either
00012  * the MPL or the LGPL.
00013  *
00014  * You should have received a copy of the LGPL along with this library
00015  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
00016  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
00017  * You should have received a copy of the MPL along with this library
00018  * in the file COPYING-MPL-1.1
00019  *
00020  * The contents of this file are subject to the Mozilla Public License
00021  * Version 1.1 (the "License"); you may not use this file except in
00022  * compliance with the License. You may obtain a copy of the License at
00023  * http://www.mozilla.org/MPL/
00024  *
00025  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
00026  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
00027  * the specific language governing rights and limitations.
00028  *
00029  * The Original Code is the cairo graphics library.
00030  *
00031  * The Initial Developer of the Original Code is Keith Packard
00032  *
00033  * Contributor(s):
00034  *     Keith R. Packard <keithp@keithp.com>
00035  */
00036 
00037 #include "cairoint.h"
00038 
00039 #if HAVE_UINT64_T
00040 
00041 #define _cairo_uint32s_to_uint64(h,l) ((uint64_t) (h) << 32 | (l))
00042 
00043 cairo_uquorem64_t
00044 _cairo_uint64_divrem (cairo_uint64_t num, cairo_uint64_t den)
00045 {
00046     cairo_uquorem64_t       qr;
00047 
00048     qr.quo = num / den;
00049     qr.rem = num % den;
00050     return qr;
00051 }
00052 
00053 #else
00054 
00055 cairo_uint64_t
00056 _cairo_uint32_to_uint64 (uint32_t i)
00057 {
00058     cairo_uint64_t   q;
00059 
00060     q.lo = i;
00061     q.hi = 0;
00062     return q;
00063 }
00064 
00065 cairo_int64_t
00066 _cairo_int32_to_int64 (int32_t i)
00067 {
00068     cairo_uint64_t   q;
00069 
00070     q.lo = i;
00071     q.hi = i < 0 ? -1 : 0;
00072     return q;
00073 }
00074 
00075 static const cairo_uint64_t
00076 _cairo_uint32s_to_uint64 (uint32_t h, uint32_t l)
00077 {
00078     cairo_uint64_t   q;
00079 
00080     q.lo = l;
00081     q.hi = h;
00082     return q;
00083 }
00084 
00085 cairo_uint64_t
00086 _cairo_uint64_add (cairo_uint64_t a, cairo_uint64_t b)
00087 {
00088     cairo_uint64_t   s;
00089 
00090     s.hi = a.hi + b.hi;
00091     s.lo = a.lo + b.lo;
00092     if (s.lo < a.lo)
00093        s.hi++;
00094     return s;
00095 }
00096 
00097 cairo_uint64_t
00098 _cairo_uint64_sub (cairo_uint64_t a, cairo_uint64_t b)
00099 {
00100     cairo_uint64_t   s;
00101 
00102     s.hi = a.hi - b.hi;
00103     s.lo = a.lo - b.lo;
00104     if (s.lo > a.lo)
00105        s.hi--;
00106     return s;
00107 }
00108 
00109 #define uint32_lo(i) ((i) & 0xffff)
00110 #define uint32_hi(i) ((i) >> 16)
00111 #define uint32_carry16      ((1) << 16)
00112 
00113 cairo_uint64_t
00114 _cairo_uint32x32_64_mul (uint32_t a, uint32_t b)
00115 {
00116     cairo_uint64_t  s;
00117     
00118     uint16_t  ah, al, bh, bl;
00119     uint32_t  r0, r1, r2, r3;
00120 
00121     al = uint32_lo (a);
00122     ah = uint32_hi (a);
00123     bl = uint32_lo (b);
00124     bh = uint32_hi (b);
00125 
00126     r0 = (uint32_t) al * bl;
00127     r1 = (uint32_t) al * bh;
00128     r2 = (uint32_t) ah * bl;
00129     r3 = (uint32_t) ah * bh;
00130 
00131     r1 += uint32_hi(r0);    /* no carry possible */
00132     r1 += r2;            /* but this can carry */
00133     if (r1 < r2)         /* check */
00134        r3 += uint32_carry16;
00135 
00136     s.hi = r3 + uint32_hi(r1);
00137     s.lo = (uint32_lo (r1) << 16) + uint32_lo (r0);
00138     return s;
00139 }
00140 
00141 cairo_int64_t
00142 _cairo_int32x32_64_mul (int32_t a, int32_t b)
00143 {
00144     cairo_int64_t s;
00145     s = _cairo_uint32x32_64_mul ((uint32_t) a, (uint32_t) b);
00146     if (a < 0)
00147        s.hi -= b;
00148     if (b < 0)
00149        s.hi -= a;
00150     return s;
00151 }
00152 
00153 cairo_uint64_t
00154 _cairo_uint64_mul (cairo_uint64_t a, cairo_uint64_t b)
00155 {
00156     cairo_uint64_t   s;
00157     
00158     s = _cairo_uint32x32_64_mul (a.lo, b.lo);
00159     s.hi += a.lo * b.hi + a.hi * b.lo;
00160     return s;
00161 }
00162 
00163 cairo_uint64_t
00164 _cairo_uint64_lsl (cairo_uint64_t a, int shift)
00165 {
00166     if (shift >= 32)
00167     {
00168        a.hi = a.lo;
00169        a.lo = 0;
00170        shift -= 32;
00171     }
00172     if (shift)
00173     {
00174        a.hi = a.hi << shift | a.lo >> (32 - shift);
00175        a.lo = a.lo << shift;
00176     }
00177     return a;
00178 }
00179 
00180 cairo_uint64_t
00181 _cairo_uint64_rsl (cairo_uint64_t a, int shift)
00182 {
00183     if (shift >= 32)
00184     {
00185        a.lo = a.hi;
00186        a.hi = 0;
00187        shift -= 32;
00188     }
00189     if (shift)
00190     {
00191        a.lo = a.lo >> shift | a.hi << (32 - shift);
00192        a.hi = a.hi >> shift;
00193     }
00194     return a;
00195 }
00196 
00197 #define _cairo_uint32_rsa(a,n)     ((uint32_t) (((int32_t) (a)) >> (n)))
00198 
00199 cairo_int64_t
00200 _cairo_uint64_rsa (cairo_int64_t a, int shift)
00201 {
00202     if (shift >= 32)
00203     {
00204        a.lo = a.hi;
00205        a.hi = _cairo_uint32_rsa (a.hi, 31);
00206        shift -= 32;
00207     }
00208     if (shift)
00209     {
00210        a.lo = a.lo >> shift | a.hi << (32 - shift);
00211        a.hi = _cairo_uint32_rsa (a.hi, shift);
00212     }
00213     return a;
00214 }
00215 
00216 int
00217 _cairo_uint64_lt (cairo_uint64_t a, cairo_uint64_t b)
00218 {
00219     return (a.hi < b.hi ||
00220            (a.hi == b.hi && a.lo < b.lo));
00221 }
00222 
00223 int
00224 _cairo_uint64_eq (cairo_uint64_t a, cairo_uint64_t b)
00225 {
00226     return a.hi == b.hi && a.lo == b.lo;
00227 }
00228 
00229 int
00230 _cairo_int64_lt (cairo_int64_t a, cairo_int64_t b)
00231 {
00232     if (_cairo_int64_negative (a) && !_cairo_int64_negative (b))
00233        return 1;
00234     if (!_cairo_int64_negative (a) && _cairo_int64_negative (b))
00235        return 0;
00236     return _cairo_uint64_lt (a, b);
00237 }
00238 
00239 cairo_uint64_t
00240 _cairo_uint64_not (cairo_uint64_t a)
00241 {
00242     a.lo = ~a.lo;
00243     a.hi = ~a.hi;
00244     return a;
00245 }
00246 
00247 cairo_uint64_t
00248 _cairo_uint64_negate (cairo_uint64_t a)
00249 {
00250     a.lo = ~a.lo;
00251     a.hi = ~a.hi;
00252     if (++a.lo == 0)
00253        ++a.hi;
00254     return a;
00255 }
00256 
00257 /*
00258  * Simple bit-at-a-time divide.
00259  */
00260 cairo_uquorem64_t
00261 _cairo_uint64_divrem (cairo_uint64_t num, cairo_uint64_t den)
00262 {
00263     cairo_uquorem64_t       qr;
00264     cairo_uint64_t   bit;
00265     cairo_uint64_t   quo;
00266     
00267     bit = _cairo_uint32_to_uint64 (1);
00268     
00269     /* normalize to make den >= num, but not overflow */
00270     while (_cairo_uint64_lt (den, num) && (den.hi & 0x80000000) == 0)
00271     {
00272        bit = _cairo_uint64_lsl (bit, 1);
00273        den = _cairo_uint64_lsl (den, 1);
00274     }
00275     quo = _cairo_uint32_to_uint64 (0);
00276     
00277     /* generate quotient, one bit at a time */
00278     while (bit.hi | bit.lo)
00279     {
00280        if (_cairo_uint64_le (den, num))
00281        {
00282            num = _cairo_uint64_sub (num, den);
00283            quo = _cairo_uint64_add (quo, bit);
00284        }
00285        bit = _cairo_uint64_rsl (bit, 1);
00286        den = _cairo_uint64_rsl (den, 1);
00287     }
00288     qr.quo = quo;
00289     qr.rem = num;
00290     return qr;
00291 }
00292 
00293 #endif /* !HAVE_UINT64_T */
00294 
00295 cairo_quorem64_t
00296 _cairo_int64_divrem (cairo_int64_t num, cairo_int64_t den)
00297 {
00298     int                     num_neg = _cairo_int64_negative (num);
00299     int                     den_neg = _cairo_int64_negative (den);
00300     cairo_uquorem64_t       uqr;
00301     cairo_quorem64_t qr;
00302 
00303     if (num_neg)
00304        num = _cairo_int64_negate (num);
00305     if (den_neg)
00306        den = _cairo_int64_negate (den);
00307     uqr = _cairo_uint64_divrem (num, den);
00308     if (num_neg)
00309        qr.rem = _cairo_int64_negate (uqr.rem);
00310     else
00311        qr.rem = uqr.rem;
00312     if (num_neg != den_neg)
00313        qr.quo = (cairo_int64_t) _cairo_int64_negate (uqr.quo);
00314     else
00315        qr.quo = (cairo_int64_t) uqr.quo;
00316     return qr;
00317 }
00318 
00319 #if HAVE_UINT128_T
00320 
00321 cairo_uquorem128_t
00322 _cairo_uint128_divrem (cairo_uint128_t num, cairo_uint128_t den)
00323 {
00324     cairo_uquorem128_t      qr;
00325 
00326     qr.quo = num / den;
00327     qr.rem = num % den;
00328     return qr;
00329 }
00330 
00331 #else
00332 
00333 cairo_uint128_t
00334 _cairo_uint32_to_uint128 (uint32_t i)
00335 {
00336     cairo_uint128_t  q;
00337 
00338     q.lo = _cairo_uint32_to_uint64 (i);
00339     q.hi = _cairo_uint32_to_uint64 (0);
00340     return q;
00341 }
00342 
00343 cairo_int128_t
00344 _cairo_int32_to_int128 (int32_t i)
00345 {
00346     cairo_int128_t   q;
00347 
00348     q.lo = _cairo_int32_to_int64 (i);
00349     q.hi = _cairo_int32_to_int64 (i < 0 ? -1 : 0);
00350     return q;
00351 }
00352 
00353 cairo_uint128_t
00354 _cairo_uint64_to_uint128 (cairo_uint64_t i)
00355 {
00356     cairo_uint128_t  q;
00357 
00358     q.lo = i;
00359     q.hi = _cairo_uint32_to_uint64 (0);
00360     return q;
00361 }
00362 
00363 cairo_int128_t
00364 _cairo_int64_to_int128 (cairo_int64_t i)
00365 {
00366     cairo_int128_t   q;
00367 
00368     q.lo = i;
00369     q.hi = _cairo_int32_to_int64 (_cairo_int64_negative(i) ? -1 : 0);
00370     return q;
00371 }
00372 
00373 cairo_uint128_t
00374 _cairo_uint128_add (cairo_uint128_t a, cairo_uint128_t b)
00375 {
00376     cairo_uint128_t  s;
00377 
00378     s.hi = _cairo_uint64_add (a.hi, b.hi);
00379     s.lo = _cairo_uint64_add (a.lo, b.lo);
00380     if (_cairo_uint64_lt (s.lo, a.lo))
00381        s.hi = _cairo_uint64_add (s.hi, _cairo_uint32_to_uint64 (1));
00382     return s;
00383 }
00384 
00385 cairo_uint128_t
00386 _cairo_uint128_sub (cairo_uint128_t a, cairo_uint128_t b)
00387 {
00388     cairo_uint128_t  s;
00389 
00390     s.hi = _cairo_uint64_sub (a.hi, b.hi);
00391     s.lo = _cairo_uint64_sub (a.lo, b.lo);
00392     if (_cairo_uint64_gt (s.lo, a.lo))
00393        s.hi = _cairo_uint64_sub (s.hi, _cairo_uint32_to_uint64(1));
00394     return s;
00395 }
00396 
00397 #if HAVE_UINT64_T
00398 
00399 #define uint64_lo32(i)      ((i) & 0xffffffff)
00400 #define uint64_hi32(i)      ((i) >> 32)
00401 #define uint64_lo(i) ((i) & 0xffffffff)
00402 #define uint64_hi(i) ((i) >> 32)
00403 #define uint64_shift32(i)   ((i) << 32)
00404 #define uint64_carry32      (((uint64_t) 1) << 32)
00405 
00406 #else
00407 
00408 #define uint64_lo32(i)      ((i).lo)
00409 #define uint64_hi32(i)      ((i).hi)
00410 
00411 static const cairo_uint64_t
00412 uint64_lo (cairo_uint64_t i)
00413 {
00414     cairo_uint64_t  s;
00415 
00416     s.lo = i.lo;
00417     s.hi = 0;
00418     return s;
00419 }
00420 
00421 static const cairo_uint64_t
00422 uint64_hi (cairo_uint64_t i)
00423 {
00424     cairo_uint64_t  s;
00425 
00426     s.lo = i.hi;
00427     s.hi = 0;
00428     return s;
00429 }
00430 
00431 static const cairo_uint64_t
00432 uint64_shift32 (cairo_uint64_t i)
00433 {
00434     cairo_uint64_t  s;
00435 
00436     s.lo = 0;
00437     s.hi = i.lo;
00438     return s;
00439 }
00440 
00441 static const cairo_uint64_t uint64_carry32 = { 0, 1 };
00442 
00443 #endif
00444 
00445 cairo_uint128_t
00446 _cairo_uint64x64_128_mul (cairo_uint64_t a, cairo_uint64_t b)
00447 {
00448     cairo_uint128_t  s;
00449     uint32_t         ah, al, bh, bl;
00450     cairo_uint64_t   r0, r1, r2, r3;
00451 
00452     al = uint64_lo32 (a);
00453     ah = uint64_hi32 (a);
00454     bl = uint64_lo32 (b);
00455     bh = uint64_hi32 (b);
00456 
00457     r0 = _cairo_uint32x32_64_mul (al, bl);
00458     r1 = _cairo_uint32x32_64_mul (al, bh);
00459     r2 = _cairo_uint32x32_64_mul (ah, bl);
00460     r3 = _cairo_uint32x32_64_mul (ah, bh);
00461 
00462     r1 = _cairo_uint64_add (r1, uint64_hi (r0));    /* no carry possible */
00463     r1 = _cairo_uint64_add (r1, r2);                 /* but this can carry */
00464     if (_cairo_uint64_lt (r1, r2))            /* check */
00465        r3 = _cairo_uint64_add (r3, uint64_carry32);
00466 
00467     s.hi = _cairo_uint64_add (r3, uint64_hi(r1));
00468     s.lo = _cairo_uint64_add (uint64_shift32 (r1),
00469                             uint64_lo (r0));
00470     return s;
00471 }
00472 
00473 cairo_int128_t
00474 _cairo_int64x64_128_mul (cairo_int64_t a, cairo_int64_t b)
00475 {
00476     cairo_int128_t  s;
00477     s = _cairo_uint64x64_128_mul (_cairo_int64_to_uint64(a),
00478                               _cairo_int64_to_uint64(b));
00479     if (_cairo_int64_negative (a))
00480        s.hi = _cairo_uint64_sub (s.hi, 
00481                               _cairo_int64_to_uint64 (b));
00482     if (_cairo_int64_negative (b))
00483        s.hi = _cairo_uint64_sub (s.hi,
00484                               _cairo_int64_to_uint64 (a));
00485     return s;
00486 }
00487 
00488 cairo_uint128_t
00489 _cairo_uint128_mul (cairo_uint128_t a, cairo_uint128_t b)
00490 {
00491     cairo_uint128_t  s;
00492 
00493     s = _cairo_uint64x64_128_mul (a.lo, b.lo);
00494     s.hi = _cairo_uint64_add (s.hi,
00495                             _cairo_uint64_mul (a.lo, b.hi));
00496     s.hi = _cairo_uint64_add (s.hi,
00497                             _cairo_uint64_mul (a.hi, b.lo));
00498     return s;
00499 }
00500 
00501 cairo_uint128_t
00502 _cairo_uint128_lsl (cairo_uint128_t a, int shift)
00503 {
00504     if (shift >= 64)
00505     {
00506        a.hi = a.lo;
00507        a.lo = _cairo_uint32_to_uint64 (0);
00508        shift -= 64;
00509     }
00510     if (shift)
00511     {
00512        a.hi = _cairo_uint64_add (_cairo_uint64_lsl (a.hi, shift),
00513                                 _cairo_uint64_rsl (a.lo, (64 - shift)));
00514        a.lo = _cairo_uint64_lsl (a.lo, shift);
00515     }
00516     return a;
00517 }
00518 
00519 cairo_uint128_t
00520 _cairo_uint128_rsl (cairo_uint128_t a, int shift)
00521 {
00522     if (shift >= 64)
00523     {
00524        a.lo = a.hi;
00525        a.hi = _cairo_uint32_to_uint64 (0);
00526        shift -= 64;
00527     }
00528     if (shift)
00529     {
00530        a.lo = _cairo_uint64_add (_cairo_uint64_rsl (a.lo, shift),
00531                                 _cairo_uint64_lsl (a.hi, (64 - shift)));
00532        a.hi = _cairo_uint64_rsl (a.hi, shift);
00533     }
00534     return a;
00535 }
00536 
00537 cairo_uint128_t
00538 _cairo_uint128_rsa (cairo_int128_t a, int shift)
00539 {
00540     if (shift >= 64)
00541     {
00542        a.lo = a.hi;
00543        a.hi = _cairo_uint64_rsa (a.hi, 64-1);
00544        shift -= 64;
00545     }
00546     if (shift)
00547     {
00548        a.lo = _cairo_uint64_add (_cairo_uint64_rsl (a.lo, shift),
00549                                 _cairo_uint64_lsl (a.hi, (64 - shift)));
00550        a.hi = _cairo_uint64_rsa (a.hi, shift);
00551     }
00552     return a;
00553 }
00554 
00555 int
00556 _cairo_uint128_lt (cairo_uint128_t a, cairo_uint128_t b)
00557 {
00558     return (_cairo_uint64_lt (a.hi, b.hi) ||
00559            (_cairo_uint64_eq (a.hi, b.hi) &&
00560             _cairo_uint64_lt (a.lo, b.lo)));
00561 }
00562 
00563 int
00564 _cairo_int128_lt (cairo_int128_t a, cairo_int128_t b)
00565 {
00566     if (_cairo_int128_negative (a) && !_cairo_int128_negative (b))
00567        return 1;
00568     if (!_cairo_int128_negative (a) && _cairo_int128_negative (b))
00569        return 0;
00570     return _cairo_uint128_lt (a, b);
00571 }
00572 
00573 int
00574 _cairo_uint128_eq (cairo_uint128_t a, cairo_uint128_t b)
00575 {
00576     return (_cairo_uint64_eq (a.hi, b.hi) &&
00577            _cairo_uint64_eq (a.lo, b.lo));
00578 }
00579 
00580 #if HAVE_UINT64_T
00581 #define _cairo_msbset64(q)  (q & ((uint64_t) 1 << 63))
00582 #else
00583 #define _cairo_msbset64(q)  (q.hi & ((uint32_t) 1 << 31))
00584 #endif
00585 
00586 cairo_uquorem128_t
00587 _cairo_uint128_divrem (cairo_uint128_t num, cairo_uint128_t den)
00588 {
00589     cairo_uquorem128_t      qr;
00590     cairo_uint128_t  bit;
00591     cairo_uint128_t  quo;
00592     
00593     bit = _cairo_uint32_to_uint128 (1);
00594     
00595     /* normalize to make den >= num, but not overflow */
00596     while (_cairo_uint128_lt (den, num) && !_cairo_msbset64(den.hi))
00597     {
00598        bit = _cairo_uint128_lsl (bit, 1);
00599        den = _cairo_uint128_lsl (den, 1);
00600     }
00601     quo = _cairo_uint32_to_uint128 (0);
00602     
00603     /* generate quotient, one bit at a time */
00604     while (_cairo_uint128_ne (bit, _cairo_uint32_to_uint128(0)))
00605     {
00606        if (_cairo_uint128_le (den, num))
00607        {
00608            num = _cairo_uint128_sub (num, den);
00609            quo = _cairo_uint128_add (quo, bit);
00610        }
00611        bit = _cairo_uint128_rsl (bit, 1);
00612        den = _cairo_uint128_rsl (den, 1);
00613     }
00614     qr.quo = quo;
00615     qr.rem = num;
00616     return qr;
00617 }
00618 
00619 cairo_int128_t
00620 _cairo_int128_negate (cairo_int128_t a)
00621 {
00622     a.lo = _cairo_uint64_not (a.lo);
00623     a.hi = _cairo_uint64_not (a.hi);
00624     return _cairo_uint128_add (a, _cairo_uint32_to_uint128 (1));
00625 }
00626 
00627 cairo_int128_t
00628 _cairo_int128_not (cairo_int128_t a)
00629 {
00630     a.lo = _cairo_uint64_not (a.lo);
00631     a.hi = _cairo_uint64_not (a.hi);
00632     return a;
00633 }
00634 
00635 #endif /* !HAVE_UINT128_T */
00636 
00637 cairo_quorem128_t
00638 _cairo_int128_divrem (cairo_int128_t num, cairo_int128_t den)
00639 {
00640     int                     num_neg = _cairo_int128_negative (num);
00641     int                     den_neg = _cairo_int128_negative (den);
00642     cairo_uquorem128_t      uqr;
00643     cairo_quorem128_t       qr;
00644 
00645     if (num_neg)
00646        num = _cairo_int128_negate (num);
00647     if (den_neg)
00648        den = _cairo_int128_negate (den);
00649     uqr = _cairo_uint128_divrem (num, den);
00650     if (num_neg)
00651        qr.rem = _cairo_int128_negate (uqr.rem);
00652     else
00653        qr.rem = uqr.rem;
00654     if (num_neg != den_neg)
00655        qr.quo = _cairo_int128_negate (uqr.quo);
00656     else
00657        qr.quo = uqr.quo;
00658     return qr;
00659 }