[cairo-commit] cairo/src cairo-wideint.c, 1.5, 1.6 cairo-wideint.h,
1.10, 1.11
Keith Packard
commit at pdx.freedesktop.org
Sat Jul 30 12:57:57 PDT 2005
Committed by: keithp
Update of /cvs/cairo/cairo/src
In directory gabe:/tmp/cvs-serv4004/src
Modified Files:
cairo-wideint.c cairo-wideint.h
Log Message:
2005-07-30 Keith Packard <keithp at keithp.com>
* src/cairo-wideint.c: (_cairo_int32x32_64_mul),
(_cairo_uint64_divrem), (_cairo_uint128_divrem):
* src/cairo-wideint.h:
Replace wide integer divide algorithms with
trivial bit-at-a-time code. Original code was
of unclear provenance, this new code is
completely different.
Index: cairo-wideint.c
===================================================================
RCS file: /cvs/cairo/cairo/src/cairo-wideint.c,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- cairo-wideint.c 3 Jun 2005 21:51:57 -0000 1.5
+++ cairo-wideint.c 30 Jul 2005 19:57:54 -0000 1.6
@@ -36,22 +36,6 @@
#include "cairoint.h"
-#if !HAVE_UINT64_T || !HAVE_UINT128_T
-
-static const unsigned char top_bit[256] =
-{
- 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
- 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
- 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
- 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
- 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
- 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
- 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
- 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
-};
-
-#endif
-
#if HAVE_UINT64_T
#define _cairo_uint32s_to_uint64(h,l) ((uint64_t) (h) << 32 | (l))
@@ -157,7 +141,8 @@
cairo_int64_t
_cairo_int32x32_64_mul (int32_t a, int32_t b)
{
- s = _cairo_uint32x32_64_mul ((uint32_t) a, (uint32_t b));
+ cairo_int64_t s;
+ s = _cairo_uint32x32_64_mul ((uint32_t) a, (uint32_t) b);
if (a < 0)
s.hi -= b;
if (b < 0)
@@ -270,200 +255,38 @@
}
/*
- * The design of this algorithm comes from GCC,
- * but the actual implementation is new
- */
-
-static const int
-_cairo_leading_zeros32 (uint32_t i)
-{
- int top;
-
- if (i < 0x100)
- top = 0;
- else if (i < 0x10000)
- top = 8;
- else if (i < 0x1000000)
- top = 16;
- else
- top = 24;
- top = top + top_bit [i >> top];
- return 32 - top;
-}
-
-typedef struct _cairo_uquorem32_t {
- uint32_t quo;
- uint32_t rem;
-} cairo_uquorem32_t;
-
-/*
- * den >= num.hi
+ * Simple bit-at-a-time divide.
*/
-static const cairo_uquorem32_t
-_cairo_uint64x32_normalized_divrem (cairo_uint64_t num, uint32_t den)
-{
- cairo_uquorem32_t qr;
- uint32_t q0, q1, r0, r1;
- uint16_t d0, d1;
- uint32_t t;
-
- d0 = den & 0xffff;
- d1 = den >> 16;
-
- q1 = num.hi / d1;
- r1 = num.hi % d1;
-
- t = q1 * d0;
- r1 = (r1 << 16) | (num.lo >> 16);
- if (r1 < t)
- {
- q1--;
- r1 += den;
- if (r1 >= den && r1 < t)
- {
- q1--;
- r1 += den;
- }
- }
-
- r1 -= t;
-
- q0 = r1 / d1;
- r0 = r1 % d1;
- t = q0 * d0;
- r0 = (r0 << 16) | (num.lo & 0xffff);
- if (r0 < t)
- {
- q0--;
- r0 += den;
- if (r0 >= den && r0 < t)
- {
- q0--;
- r0 += den;
- }
- }
- r0 -= t;
- qr.quo = (q1 << 16) | q0;
- qr.rem = r0;
- return qr;
-}
-
cairo_uquorem64_t
_cairo_uint64_divrem (cairo_uint64_t num, cairo_uint64_t den)
{
- cairo_uquorem32_t qr32;
cairo_uquorem64_t qr;
- int norm;
- uint32_t q1, q0, r1, r0;
-
- if (den.hi == 0)
+ cairo_uint64_t bit;
+ cairo_uint64_t quo;
+
+ bit = _cairo_uint32_to_uint64 (1);
+
+ /* normalize to make den >= num, but not overflow */
+ while (_cairo_uint64_lt (den, num) && (den.hi & 0x80000000) == 0)
{
- if (den.lo > num.hi)
- {
- /* 0q = nn / 0d */
-
- norm = _cairo_leading_zeros32 (den.lo);
- if (norm)
- {
- den.lo <<= norm;
- num = _cairo_uint64_lsl (num, norm);
- }
- q1 = 0;
- }
- else
- {
- /* qq = NN / 0d */
-
- if (den.lo == 0)
- den.lo = 1 / den.lo;
-
- norm = _cairo_leading_zeros32 (den.lo);
- if (norm)
- {
- cairo_uint64_t num1;
- den.lo <<= norm;
- num1 = _cairo_uint64_rsl (num, 32 - norm);
- qr32 = _cairo_uint64x32_normalized_divrem (num1, den.lo);
- q1 = qr32.quo;
- num.hi = qr32.rem;
- num.lo <<= norm;
- }
- else
- {
- num.hi -= den.lo;
- q1 = 1;
- }
- }
- qr32 = _cairo_uint64x32_normalized_divrem (num, den.lo);
- q0 = qr32.quo;
- r1 = 0;
- r0 = qr32.rem >> norm;
+ bit = _cairo_uint64_lsl (bit, 1);
+ den = _cairo_uint64_lsl (den, 1);
}
- else
+ quo = _cairo_uint32_to_uint64 (0);
+
+ /* generate quotient, one bit at a time */
+ while (bit.hi | bit.lo)
{
- if (den.hi > num.hi)
- {
- /* 00 = nn / DD */
- q0 = q1 = 0;
- r0 = num.lo;
- r1 = num.hi;
- }
- else
+ if (_cairo_uint64_le (den, num))
{
- /* 0q = NN / dd */
-
- norm = _cairo_leading_zeros32 (den.hi);
- if (norm == 0)
- {
- if (num.hi > den.hi || num.lo >= den.lo)
- {
- q0 = 1;
- num = _cairo_uint64_sub (num, den);
- }
- else
- {
- q0 = 0;
- }
-
- q1 = 0;
- r0 = num.lo;
- r1 = num.hi;
- }
- else
- {
- cairo_uint64_t num1;
- cairo_uint64_t part;
-
- num1 = _cairo_uint64_rsl (num, 32 - norm);
- den = _cairo_uint64_lsl (den, norm);
-
- qr32 = _cairo_uint64x32_normalized_divrem (num1, den.hi);
- part = _cairo_uint32x32_64_mul (qr32.quo, den.lo);
-
- q0 = qr32.quo;
-
- num.lo <<= norm;
- num.hi = qr32.rem;
-
- if (_cairo_uint64_gt (part, num))
- {
- q0--;
- part = _cairo_uint64_sub (part, den);
- }
-
- q1 = 0;
-
- num = _cairo_uint64_sub (num, part);
- num = _cairo_uint64_rsl (num, norm);
- r0 = num.lo;
- r1 = num.hi;
- }
+ num = _cairo_uint64_sub (num, den);
+ quo = _cairo_uint64_add (quo, bit);
}
+ bit = _cairo_uint64_rsl (bit, 1);
+ den = _cairo_uint64_rsl (den, 1);
}
- qr.quo.lo = q0;
- qr.quo.hi = q1;
- qr.rem.lo = r0;
- qr.rem.hi = r1;
+ qr.quo = quo;
+ qr.rem = num;
return qr;
}
@@ -754,234 +577,42 @@
_cairo_uint64_eq (a.lo, b.lo));
}
-/*
- * The design of this algorithm comes from GCC,
- * but the actual implementation is new
- */
-
-/*
- * den >= num.hi
- */
-static cairo_uquorem64_t
-_cairo_uint128x64_normalized_divrem (cairo_uint128_t num, cairo_uint64_t den)
-{
- cairo_uquorem64_t qr64;
- cairo_uquorem64_t qr;
- uint32_t q0, q1;
- cairo_uint64_t r0, r1;
- uint32_t d0, d1;
- cairo_uint64_t t;
-
- d0 = uint64_lo32 (den);
- d1 = uint64_hi32 (den);
-
- qr64 = _cairo_uint64_divrem (num.hi, _cairo_uint32_to_uint64 (d1));
- q1 = _cairo_uint64_to_uint32 (qr64.quo);
- r1 = qr64.rem;
-
- t = _cairo_uint32x32_64_mul (q1, d0);
-
- r1 = _cairo_uint64_add (_cairo_uint64_lsl (r1, 32),
- _cairo_uint64_rsl (num.lo, 32));
-
- if (_cairo_uint64_lt (r1, t))
- {
- q1--;
- r1 = _cairo_uint64_add (r1, den);
- if (_cairo_uint64_ge (r1, den) && _cairo_uint64_lt (r1, t))
- {
- q1--;
- r1 = _cairo_uint64_add (r1, den);
- }
- }
-
- r1 = _cairo_uint64_sub (r1, t);
-
- qr64 = _cairo_uint64_divrem (r1, _cairo_uint32_to_uint64 (d1));
-
- q0 = _cairo_uint64_to_uint32 (qr64.quo);
- r0 = qr64.rem;
-
- t = _cairo_uint32x32_64_mul (q0, d0);
-
- r0 = _cairo_uint64_add (_cairo_uint64_lsl (r0, 32),
- _cairo_uint32_to_uint64 (_cairo_uint64_to_uint32 (num.lo)));
- if (_cairo_uint64_lt (r0, t))
- {
- q0--;
- r0 = _cairo_uint64_add (r0, den);
- if (_cairo_uint64_ge (r0, den) && _cairo_uint64_lt (r0, t))
- {
- q0--;
- r0 = _cairo_uint64_add (r0, den);
- }
- }
-
- r0 = _cairo_uint64_sub (r0, t);
-
- qr.quo = _cairo_uint32s_to_uint64 (q1, q0);
- qr.rem = r0;
- return qr;
-}
-
#if HAVE_UINT64_T
-
-static int
-_cairo_leading_zeros64 (cairo_uint64_t q)
-{
- int top = 0;
-
- if (q >= (uint64_t) 0x10000 << 16)
- {
- top += 32;
- q >>= 32;
- }
- if (q >= (uint64_t) 0x10000)
- {
- top += 16;
- q >>= 16;
- }
- if (q >= (uint64_t) 0x100)
- {
- top += 8;
- q >>= 8;
- }
- top += top_bit [q];
- return 64 - top;
-}
-
+#define _cairo_msbset64(q) (q & ((uint64_t) 1 << 63))
#else
-
-static const int
-_cairo_leading_zeros64 (cairo_uint64_t d)
-{
- if (d.hi)
- return _cairo_leading_zeros32 (d.hi);
- else
- return 32 + _cairo_leading_zeros32 (d.lo);
-}
-
+#define _cairo_msbset64(q) (q.hi & ((uint32_t) 1 << 31))
#endif
cairo_uquorem128_t
_cairo_uint128_divrem (cairo_uint128_t num, cairo_uint128_t den)
{
- cairo_uquorem64_t qr64;
cairo_uquorem128_t qr;
- int norm;
- cairo_uint64_t q1, q0, r1, r0;
-
- if (_cairo_uint64_eq (den.hi, _cairo_uint32_to_uint64 (0)))
+ cairo_uint128_t bit;
+ cairo_uint128_t quo;
+
+ bit = _cairo_uint32_to_uint128 (1);
+
+ /* normalize to make den >= num, but not overflow */
+ while (_cairo_uint128_lt (den, num) && !_cairo_msbset64(den.hi))
{
- if (_cairo_uint64_gt (den.lo, num.hi))
- {
- /* 0q = nn / 0d */
-
- norm = _cairo_leading_zeros64 (den.lo);
- if (norm)
- {
- den.lo = _cairo_uint64_lsl (den.lo, norm);
- num = _cairo_uint128_lsl (num, norm);
- }
- q1 = _cairo_uint32_to_uint64 (0);
- }
- else
- {
- /* qq = NN / 0d */
-
- if (_cairo_uint64_eq (den.lo, _cairo_uint32_to_uint64 (0)))
- den.lo = _cairo_uint64_divrem (_cairo_uint32_to_uint64 (1),
- den.lo).quo;
-
- norm = _cairo_leading_zeros64 (den.lo);
- if (norm)
- {
- cairo_uint128_t num1;
-
- den.lo = _cairo_uint64_lsl (den.lo, norm);
- num1 = _cairo_uint128_rsl (num, 64 - norm);
- qr64 = _cairo_uint128x64_normalized_divrem (num1, den.lo);
- q1 = qr64.quo;
- num.hi = qr64.rem;
- num.lo = _cairo_uint64_lsl (num.lo, norm);
- }
- else
- {
- num.hi = _cairo_uint64_sub (num.hi, den.lo);
- q1 = _cairo_uint32_to_uint64 (1);
- }
- }
- qr64 = _cairo_uint128x64_normalized_divrem (num, den.lo);
- q0 = qr64.quo;
- r1 = _cairo_uint32_to_uint64 (0);
- r0 = _cairo_uint64_rsl (qr64.rem, norm);
+ bit = _cairo_uint128_lsl (bit, 1);
+ den = _cairo_uint128_lsl (den, 1);
}
- else
+ quo = _cairo_uint32_to_uint128 (0);
+
+ /* generate quotient, one bit at a time */
+ while (_cairo_uint128_ne (bit, _cairo_uint32_to_uint128(0)))
{
- if (_cairo_uint64_gt (den.hi, num.hi))
- {
- /* 00 = nn / DD */
- q0 = q1 = _cairo_uint32_to_uint64 (0);
- r0 = num.lo;
- r1 = num.hi;
- }
- else
+ if (_cairo_uint128_le (den, num))
{
- /* 0q = NN / dd */
-
- norm = _cairo_leading_zeros64 (den.hi);
- if (norm == 0)
- {
- if (_cairo_uint64_gt (num.hi, den.hi) ||
- _cairo_uint64_ge (num.lo, den.lo))
- {
- q0 = _cairo_uint32_to_uint64 (1);
- num = _cairo_uint128_sub (num, den);
- }
- else
- {
- q0 = _cairo_uint32_to_uint64 (0);
- }
-
- q1 = _cairo_uint32_to_uint64 (0);
- r0 = num.lo;
- r1 = num.hi;
- }
- else
- {
- cairo_uint128_t num1;
- cairo_uint128_t part;
-
- num1 = _cairo_uint128_rsl (num, 64 - norm);
- den = _cairo_uint128_lsl (den, norm);
-
- qr64 = _cairo_uint128x64_normalized_divrem (num1, den.hi);
- part = _cairo_uint64x64_128_mul (qr64.quo, den.lo);
-
- q0 = qr64.quo;
-
- num.lo = _cairo_uint64_lsl (num.lo, norm);
- num.hi = qr64.rem;
-
- if (_cairo_uint128_gt (part, num))
- {
- q0 = _cairo_uint64_sub (q0, _cairo_uint32_to_uint64 (1));
- part = _cairo_uint128_sub (part, den);
- }
-
- q1 = _cairo_uint32_to_uint64 (0);
-
- num = _cairo_uint128_sub (num, part);
- num = _cairo_uint128_rsl (num, norm);
- r0 = num.lo;
- r1 = num.hi;
- }
+ num = _cairo_uint128_sub (num, den);
+ quo = _cairo_uint128_add (quo, bit);
}
+ bit = _cairo_uint128_rsl (bit, 1);
+ den = _cairo_uint128_rsl (den, 1);
}
- qr.quo.lo = q0;
- qr.quo.hi = q1;
- qr.rem.lo = r0;
- qr.rem.hi = r1;
+ qr.quo = quo;
+ qr.rem = num;
return qr;
}
Index: cairo-wideint.h
===================================================================
RCS file: /cvs/cairo/cairo/src/cairo-wideint.h,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -d -r1.10 -r1.11
--- cairo-wideint.h 10 May 2005 19:42:32 -0000 1.10
+++ cairo-wideint.h 30 Jul 2005 19:57:54 -0000 1.11
@@ -85,7 +85,7 @@
#define _cairo_int64_add(a,b) _cairo_uint64_add (a,b)
#define _cairo_int64_sub(a,b) _cairo_uint64_sub (a,b)
#define _cairo_int64_mul(a,b) _cairo_uint64_mul (a,b)
-int I _cairo_int32x32_64_mul (int32_t a, int32_t b);
+cairo_int64_t I _cairo_int32x32_64_mul (int32_t a, int32_t b);
int I _cairo_int64_lt (cairo_uint64_t a, cairo_uint64_t b);
#define _cairo_int64_eq(a,b) _cairo_uint64_eq (a,b)
#define _cairo_int64_lsl(a,b) _cairo_uint64_lsl (a,b)
@@ -208,7 +208,7 @@
#define _cairo_int128_add(a,b) _cairo_uint128_add(a,b)
#define _cairo_int128_sub(a,b) _cairo_uint128_sub(a,b)
#define _cairo_int128_mul(a,b) _cairo_uint128_mul(a,b)
-cairo_uint128_t I _cairo_int64x64_128_mul (cairo_int64_t a, cairo_int64_t b);
+cairo_int128_t I _cairo_int64x64_128_mul (cairo_int64_t a, cairo_int64_t b);
#define _cairo_int128_lsl(a,b) _cairo_uint128_lsl(a,b)
#define _cairo_int128_rsl(a,b) _cairo_uint128_rsl(a,b)
#define _cairo_int128_rsa(a,b) _cairo_uint128_rsa(a,b)
More information about the cairo-commit
mailing list