[Commit] cairo_u128 Makefile, 1.1.1.1, 1.2 cairo_test.c, 1.1.1.1,
1.2 cairo_uint128.c, 1.1.1.1, 1.2 cairo_uint128.h, 1.1.1.1,
1.2 checkdata.5c, 1.1.1.1, 1.2
Keith Packard
commit at keithp.com
Mon May 24 22:04:52 PDT 2004
- Previous message: [Commit] nickle ChangeLog, 1.48, 1.49 Makefile.am, 1.52,
1.53 make-version.sh, 1.1, 1.2 version.m4, 1.13, NONE
- Next message: [Commit] cairo_u128 .cvsignore, NONE, 1.1 Makefile, 1.2,
1.3 cairo_test.c, 1.2, 1.3 cairo_uint128.c, 1.2,
1.3 cairo_uint128.h, 1.2, 1.3 checkdata.5c, 1.2, 1.3
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
Committed by: keithp
Update of /local/src/CVS/cairo_u128
In directory home.keithp.com:/tmp/cvs-serv29916
Modified Files:
Makefile cairo_test.c cairo_uint128.c cairo_uint128.h
checkdata.5c
Log Message:
Add 64-bit arithmetic for environments without uint64_t
Index: Makefile
===================================================================
RCS file: /local/src/CVS/cairo_u128/Makefile,v
retrieving revision 1.1.1.1
retrieving revision 1.2
diff -u -d -r1.1.1.1 -r1.2
--- a/Makefile 21 May 2004 08:59:32 -0000 1.1.1.1
+++ b/Makefile 25 May 2004 05:04:49 -0000 1.2
@@ -1,5 +1,5 @@
WIDTH=4
-SETS=10000
+SETS=1000
CFLAGS=-g -DWIDTH=$(WIDTH)
OBJS = cairo_uint128.o cairo_test.o
Index: cairo_test.c
===================================================================
RCS file: /local/src/CVS/cairo_u128/cairo_test.c,v
retrieving revision 1.1.1.1
retrieving revision 1.2
diff -u -d -r1.1.1.1 -r1.2
--- a/cairo_test.c 21 May 2004 08:59:32 -0000 1.1.1.1
+++ b/cairo_test.c 25 May 2004 05:04:49 -0000 1.2
@@ -25,29 +25,65 @@
#include "cairo_uint128.h"
#include <stdio.h>
+#if HAVE_UINT64_T
+#define NUM_IN_UINT128 4
+#define WIDE_FORMAT "%08x"
+#else
+#define NUM_IN_UINT64 4
+#define NUM_IN_UINT128 8
+#define WIDE_FORMAT "%04x"
+#endif
+
void
dump_uint128 (cairo_uint128_t q)
{
- char *format="%x";
+ char *format = "%x";
int i;
+ int start = 0;
- for (i = 3; i >= 0; i--)
+ for (i = NUM_IN_UINT128 - 1; i >= 0; i--)
{
- if (q.b[i] || i == 0)
+ if (q.b[i])
+ start=1;
+ if (start)
{
printf (format, q.b[i]);
- format = "%08x";
+ format = WIDE_FORMAT;
}
}
- printf("\n");
+ printf ("\n");
+}
+
+void
+dump_uint64 (cairo_uint64_t q)
+{
+#if HAVE_UINT64_T
+ printf ("%llx\n", q);
+#else
+ char *format = "%x";
+ int i;
+ int start = 0;
+
+ for (i = NUM_IN_UINT64 - 1; i >= 0; i--)
+ {
+ if (q.b[i])
+ start=1;
+ if (start)
+ {
+ printf (format, q.b[i]);
+ format = WIDE_FORMAT;
+ }
+ }
+ printf ("\n");
+#endif
}
int
main (int argc, char **argv)
{
unsigned int i;
- cairo_uint128_t q[WIDTH];
- cairo_uint128_t v;
+ cairo_uint128_t q[WIDTH], qv;
+ cairo_uint64_t d[WIDTH], dv;
int c;
for (;;)
@@ -57,19 +93,34 @@
if (scanf ("%u", &i) != 1)
exit (0);
q[c] = _cairo_uint32_to_uint128 (i);
+ d[c] = _cairo_uint32_to_uint64 (i);
}
- v = _cairo_uint32_to_uint128 (1);
+ qv = _cairo_uint32_to_uint128 (1);
+ dv = _cairo_uint32_to_uint64 (1);
for (c = 0; c < WIDTH; c++)
- v = _cairo_uint128_mul (v, q[c]);
- dump_uint128 (v);
+ {
+ qv = _cairo_uint128_mul (qv, q[c]);
+ dv = _cairo_uint64_mul (dv, d[c]);
+ }
+ dump_uint128 (qv);
+ dump_uint64 (dv);
for (c = 0; c < WIDTH; c++)
- v = _cairo_uint128_sub (v, q[c]);
- dump_uint128 (v);
+ {
+ qv = _cairo_uint128_sub (qv, q[c]);
+ dv = _cairo_uint64_sub (dv, d[c]);
+ }
+ dump_uint128 (qv);
+ dump_uint64 (dv);
- v = _cairo_uint32_to_uint128 (0);
+ qv = _cairo_uint32_to_uint128 (0);
+ dv = _cairo_uint32_to_uint64 (0);
for (c = 0; c < WIDTH; c++)
- v = _cairo_uint128_add (v, q[c]);
- dump_uint128 (v);
+ {
+ qv = _cairo_uint128_add (qv, q[c]);
+ dv = _cairo_uint64_add (dv, d[c]);
+ }
+ dump_uint128 (qv);
+ dump_uint64 (dv);
}
}
Index: cairo_uint128.c
===================================================================
RCS file: /local/src/CVS/cairo_u128/cairo_uint128.c,v
retrieving revision 1.1.1.1
retrieving revision 1.2
diff -u -d -r1.1.1.1 -r1.2
--- a/cairo_uint128.c 21 May 2004 08:59:32 -0000 1.1.1.1
+++ b/cairo_uint128.c 25 May 2004 05:04:49 -0000 1.2
@@ -25,19 +25,144 @@
#include "cairo_uint128.h"
#if HAVE_UINT64_T
+
typedef uint32_t cairo_uint_t;
typedef uint64_t cairo_2uint_t;
#define NUM_IN_UINT128 4
#define BITS_IN_UINT 32
#define MAX_UINT 0xffffffff
+
#else
+
typedef uint16_t cairo_uint_t;
typedef uint32_t cairo_2uint_t;
#define NUM_IN_UINT128 8
+#define NUM_IN_UINT64 4
#define BITS_IN_UINT 16
#define MAX_UINT 0xffff
+
#endif
+#if !HAVE_UINT64_T
+
+cairo_uint64_t
+_cairo_uint32_to_uint64 (uint32_t i)
+{
+ cairo_uint64_t q;
+
+ q.b[0] = (uint16_t) i;
+ q.b[1] = (uint16_t) (i >> 16);
+ q.b[2] = 0;
+ q.b[3] = 0;
+ return q;
+}
+
+cairo_uint64_t
+_cairo_uint64_add (cairo_uint64_t a, cairo_uint64_t b)
+{
+ cairo_uint64_t s;
+ int i;
+ cairo_2uint_t t;
+ cairo_uint_t carry = 0;
+
+ for (i = 0; i < NUM_IN_UINT64; i++)
+ {
+ t = (cairo_2uint_t) a.b[i] + (cairo_2uint_t) b.b[i] + carry;
+ carry = (cairo_uint_t) (t >> BITS_IN_UINT);
+ s.b[i] = (cairo_uint_t) t;
+ }
+ return s;
+}
+
+cairo_uint64_t
+_cairo_uint64_sub (cairo_uint64_t a, cairo_uint64_t b)
+{
+ cairo_uint64_t s;
+ int i;
+ cairo_2uint_t t;
+ cairo_uint_t carry = 0;
+
+ for (i = 0; i < NUM_IN_UINT64; i++)
+ {
+ t = (cairo_2uint_t) a.b[i] - (cairo_2uint_t) b.b[i] - carry;
+ carry = ((cairo_uint_t) (t >> BITS_IN_UINT)) & 1;
+ s.b[i] = (cairo_uint_t) t;
+ }
+ return s;
+}
+
+cairo_uint64_t
+_cairo_uint64_mul (cairo_uint64_t a, cairo_uint64_t b)
+{
+ cairo_uint64_t s;
+ int sibase, siloop, si;
+ int ai, bi;
+ cairo_uint_t ad;
+ cairo_uint_t carry;
+ cairo_2uint_t t;
+
+ memset (&s, '\0', sizeof (s));
+ sibase = 0;
+ for (ai = 0; ai < NUM_IN_UINT64; ai++)
+ {
+ carry = 0;
+ siloop = sibase++;
+ ad = a.b[ai];
+ for (bi = 0; bi < NUM_IN_UINT64; bi++)
+ {
+ t = (cairo_2uint_t) ad * (cairo_2uint_t) b.b[bi] + carry;
+ carry = (cairo_uint_t) (t >> BITS_IN_UINT);
+ t = (cairo_2uint_t) (cairo_uint_t) t;
+ for (si = siloop++; t && si < NUM_IN_UINT64; si++)
+ {
+ t += (cairo_2uint_t) s.b[si];
+ s.b[si] = (cairo_uint_t) t;
+ t = t >> BITS_IN_UINT;
+ }
+ }
+ }
+ return s;
+}
+
+/*
+ * If this appears in profiles as being a performance problem,
+ * it can be easily recoded with half as many multiplies
+ */
+cairo_uint64_t
+_cairo_uint32x32_64_mul (uint32_t a, uint32_t b)
+{
+ return _cairo_uint64_mul (_cairo_uint32_to_uint64 (a),
+ _cairo_uint32_to_uint64 (b));
+}
+
+int
+_cairo_uint64_lt (cairo_uint64_t a, cairo_uint64_t b)
+{
+ int i;
+
+ for (i = NUM_IN_UINT64 - 1; i >= 0; i--)
+ {
+ if (a.b[i] < b.b[i])
+ return 1;
+ if (a.b[i] > b.b[i])
+ return 0;
+ }
+ return 0;
+}
+
+int
+_cairo_uint64_eq (cairo_uint64_t a, cairo_uint64_t b)
+{
+ int i;
+
+ for (i = 0; i < NUM_IN_UINT64; i++)
+ if (a.b[i] != b.b[i])
+ return 0;
+ return 1;
+}
+
+#endif /* !HAVE_UINT64_T */
+
cairo_uint128_t
_cairo_uint32_to_uint128 (uint32_t i)
{
@@ -62,6 +187,29 @@
}
cairo_uint128_t
+_cairo_uint64_to_uint128 (cairo_uint64_t i)
+{
+ cairo_uint128_t q;
+
+#if HAVE_UINT64_T
+ q.b[0] = i;
+ q.b[1] = i >> 32;
+ q.b[2] = 0;
+ q.b[3] = 0;
+#else
+ q.b[0] = i.b[0];
+ q.b[1] = i.b[1];
+ q.b[2] = i.b[2];
+ q.b[3] = i.b[3];
+ q.b[4] = 0;
+ q.b[5] = 0;
+ q.b[6] = 0;
+ q.b[7] = 0;
+#endif
+ return q;
+}
+
+cairo_uint128_t
_cairo_uint128_add (cairo_uint128_t a, cairo_uint128_t b)
{
cairo_uint128_t s;
@@ -117,12 +265,10 @@
t = (cairo_2uint_t) ad * (cairo_2uint_t) b.b[bi] + carry;
carry = (cairo_uint_t) (t >> BITS_IN_UINT);
t = (cairo_2uint_t) (cairo_uint_t) t;
- si = siloop++;
- while (t)
+ for (si = siloop++; t && si < NUM_IN_UINT128; si++)
{
t += (cairo_2uint_t) s.b[si];
s.b[si] = (cairo_uint_t) t;
- si++;
t = t >> BITS_IN_UINT;
}
}
@@ -130,6 +276,17 @@
return s;
}
+/*
+ * If this appears in profiles as being a performance problem,
+ * it can be easily recoded with half as many multiplies
+ */
+cairo_uint128_t
+_cairo_uint64x64_128_mul (cairo_uint64_t a, cairo_uint64_t b)
+{
+ return _cairo_uint128_mul (_cairo_uint64_to_uint128 (a),
+ _cairo_uint64_to_uint128 (b));
+}
+
int
_cairo_uint128_lt (cairo_uint128_t a, cairo_uint128_t b)
{
Index: cairo_uint128.h
===================================================================
RCS file: /local/src/CVS/cairo_u128/cairo_uint128.h,v
retrieving revision 1.1.1.1
retrieving revision 1.2
diff -u -d -r1.1.1.1 -r1.2
--- a/cairo_uint128.h 21 May 2004 08:59:32 -0000 1.1.1.1
+++ b/cairo_uint128.h 25 May 2004 05:04:49 -0000 1.2
@@ -22,10 +22,59 @@
* PERFORMANCE OF THIS SOFTWARE.
*/
+#ifndef CAIRO_UINT128_H
+#define CAIRO_UINT128_H
+
#include <stdint.h>
#define HAVE_UINT64_T 1
+#if !HAVE_UINT64_T
+
+typedef struct _cairo_uint64 {
+ uint16_t b[4];
+} cairo_uint64_t;
+
+extern cairo_uint64_t
+_cairo_uint32_to_uint64 (uint32_t i);
+
+extern cairo_uint64_t
+_cairo_uint64_add (cairo_uint64_t a, cairo_uint64_t b);
+
+extern cairo_uint64_t
+_cairo_uint64_sub (cairo_uint64_t a, cairo_uint64_t b);
+
+extern cairo_uint64_t
+_cairo_uint64_mul (cairo_uint64_t a, cairo_uint64_t b);
+
+extern cairo_uint64_t
+_cairo_uint32x32_64_mul (uint32_t a, uint32_t b);
+
+extern int
+_cairo_uint64_less (cairo_uint64_t a, cairo_uint64_t b);
+
+extern int
+_cairo_uint64_equal (cairo_uint64_t a, cairo_uint64_t b);
+
+#else
+
+typedef uint64_t cairo_uint64_t;
+
+#define _cairo_uint32_to_uint64(i) ((uint64_t) (i))
+#define _cairo_uint64_add(a,b) ((a) + (b))
+#define _cairo_uint64_sub(a,b) ((a) - (b))
+#define _cairo_uint64_mul(a,b) ((a) * (b))
+#define _cairo_uint32x32_64_mul(a,b) ((uint64_t) (a) * (uint64_t) (b))
+#define _cairo_uint64_less(a,b) ((a) < (b))
+#define _cairo_uint64_equal(a,b) ((a) == (b))
+
+#endif
+
+#define _cairo_uint64_gt(a,b) _cairo_uint64_less(b,a)
+#define _cairo_uint64_le(a,b) (!_cairo_uint64_gt(a,b))
+#define _cairo_uint64_ge(a,b) (!_cairo_uint64_lt(a,b))
+#define _cairo_uint64_ne(a,b) (!_cairo_uint64_eq(a,b))
+
typedef struct cairo_uint128 {
#if HAVE_UINT64_T
uint32_t b[4];
@@ -56,3 +105,5 @@
#define _cairo_uint128_le(a,b) (!_cairo_uint128_gt(a,b))
#define _cairo_uint128_ge(a,b) (!_cairo_uint128_lt(a,b))
#define _cairo_uint128_ne(a,b) (!_cairo_uint128_eq(a,b))
+
+#endif /* CAIRO_UINT128_H */
Index: checkdata.5c
===================================================================
RCS file: /local/src/CVS/cairo_u128/checkdata.5c,v
retrieving revision 1.1.1.1
retrieving revision 1.2
diff -u -d -r1.1.1.1 -r1.2
--- a/checkdata.5c 21 May 2004 08:59:32 -0000 1.1.1.1
+++ b/checkdata.5c 25 May 2004 05:04:49 -0000 1.2
@@ -31,8 +31,12 @@
{
int[*] n = readnums();
int p = prod(n);
+ int dp = p & 0xffffffffffffffff;
int s = sum(n);
printf ("%x\n", p);
+ printf ("%x\n", dp);
printf ("%x\n", p - s);
+ printf ("%x\n", dp - s);
+ printf ("%x\n", s);
printf ("%x\n", s);
}
- Previous message: [Commit] nickle ChangeLog, 1.48, 1.49 Makefile.am, 1.52,
1.53 make-version.sh, 1.1, 1.2 version.m4, 1.13, NONE
- Next message: [Commit] cairo_u128 .cvsignore, NONE, 1.1 Makefile, 1.2,
1.3 cairo_test.c, 1.2, 1.3 cairo_uint128.c, 1.2,
1.3 cairo_uint128.h, 1.2, 1.3 checkdata.5c, 1.2, 1.3
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
More information about the Commit
mailing list