[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


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);
 }




More information about the Commit mailing list