klisp

commit 460194f646aa294ff209b1a6cd4d5797bd283390
parent ff482c2c28350522b46e491ecaa11ead69112da5
Author: Andres Navarro <canavarro82@gmail.com>
Date:   Wed,  6 Apr 2011 00:42:05 -0300

Added some helpers for working with fixints. Refactored gcd code. All of these in preparation for map.

Diffstat:
M
src/kghelpers.c
 | 
50
++++++++++++++++++++++++++++++++++++++++++++++++++
M
src/kghelpers.h
 | 
19
+++++++++++++++++++
M
src/kgnumbers.c
 | 
46
++--------------------------------------------

3 files changed, 71 insertions(+), 44 deletions(-)
diff --git a/src/kghelpers.c b/src/kghelpers.c
@@ -250,3 +250,53 @@ void do_return_value(klisp_State *K, TValue *xparams, TValue obj)
     TValue ret_obj = xparams[0];
     kapply_cc(K, ret_obj);
 }
+
+/* Some helpers for working with fixints (signed 32 bits) */
+int64_t kgcd32_64(int32_t a_, int32_t b_)
+{
+    /* this is a vanilla binary gcd algorithm */ 
+
+    /* work with positive numbers, use unsigned numbers to 
+       allow INT32_MIN to have an absolute value */
+    uint32_t a = (uint32_t) kabs64(a_);
+    uint32_t b = (uint32_t) kabs64(b_);
+
+    int powerof2;
+
+    /* the easy cases first, unlike the general kernel gcd the
+     gcd2 of a number and zero is zero */
+    if (a == 0)
+	return b;
+    else if (b == 0)
+	return a;
+ 
+    for (powerof2 = 0; ((a & 1) == 0) && 
+	     ((b & 1) == 0); ++powerof2, a >>= 1, b >>= 1)
+	;
+ 
+    while(a != 0 && b!= 0) {
+	/* either a or b are odd, make them both odd */
+	for (; (a & 1) == 0; a >>= 1)
+	    ;
+	for (; (b & 1) == 0; b >>= 1)
+	    ;
+
+	/* now the difference is sure to be even */
+	if (a < b) {
+	    b = (b - a) >> 1;
+	} else {
+	    a = (a - b) >> 1;
+	}
+    }
+ 
+    return (a == 0? b : a) << powerof2;
+}
+
+int64_t klcm32_64(int32_t a_, int32_t b_)
+{
+    int64_t gcd = kgcd32_64(a_, b_);
+    int64_t a = kabs64(a_) / gcd;
+    int64_t b = kabs64(b_) / gcd;
+
+    return a * b;
+}
diff --git a/src/kghelpers.h b/src/kghelpers.h
@@ -404,4 +404,23 @@ inline TValue make_return_value_cont(klisp_State *K, TValue parent, TValue obj)
     return kmake_continuation(K, parent, KNIL, KNIL, do_return_value, 1, obj);
 }
 
+/* Some helpers for working with fixints (signed 32 bits) */
+inline int32_t kabs32(int32_t a) { return a < 0? -a : a; }
+inline int64_t kabs64(int64_t a) { return a < 0? -a : a; }
+inline int32_t kmin32(int32_t a, int32_t b) { return a < b? a : b; }
+inline int32_t kmax32(int32_t a, int32_t b) { return a > b? a : b; }
+inline int32_t kcheck32(klisp_State *K, char *msg, int64_t i) 
+{
+    if (i > (int64_t) INT32_MAX || i < (int64_t) INT32_MIN) {
+	klispE_throw(K, msg);
+	return 0;
+    } else {
+	return (int32_t) i;
+    }
+}
+
+/* gcd for two numbers, used for gcd, lcm & map */
+int64_t kgcd32_64(int32_t a, int32_t b);
+int64_t klcm32_64(int32_t a, int32_t b);
+
 #endif
diff --git a/src/kgnumbers.c b/src/kgnumbers.c
@@ -699,48 +699,6 @@ void kmin_max(klisp_State *K, TValue *xparams, TValue ptree, TValue denv)
 }
 
 /* 12.5.14 gcm, lcm */
-
-/* gcd for two numbers */
-int32_t gcd2(int32_t a, int32_t b)
-{
-    /* work with positive numbers */
-    if (a < 0)
-	a = -a;
-    if (b < 0)
-	b = -b;
-
-    /* this is a vanilla binary gcd algorithm */ 
-    int32_t powerof2;
-
-    /* the easy cases first, unlike the general kernel gcd the
-     gcd2 of a number and zero is zero */
-    if (a == 0)
-	return b;
-    else if (b == 0)
-	return a;
- 
-    for (powerof2 = 0; ((a & 1) == 0) && 
-	     ((b & 1) == 0); ++powerof2, a >>= 1, b >>= 1)
-	;
- 
-    while(a != 0 && b!= 0) {
-	/* either a or b are odd, make them both odd */
-	for (; (a & 1) == 0; a >>= 1)
-	    ;
-	for (; (b & 1) == 0; b >>= 1)
-	    ;
-
-	/* now the difference is sure to be even */
-	if (a < b) {
-	    b = (b - a) >> 1;
-	} else {
-	    a = (a - b) >> 1;
-	}
-    }
- 
-    return (a == 0? b : a) << powerof2;
-}
-
 void kgcd(klisp_State *K, TValue *xparams, TValue ptree, TValue denv)
 {
     UNUSED(xparams);
@@ -765,7 +723,7 @@ void kgcd(klisp_State *K, TValue *xparams, TValue ptree, TValue denv)
 		seen_zero = true;
 	    } else if (ttisfixint(first)) {
 		seen_finite_non_zero = true;
-		finite_gcd = gcd2(finite_gcd, ivalue(first));
+		finite_gcd = (int32_t) kgcd32_64(finite_gcd, ivalue(first));
 	    }
 	}
 	if (seen_finite_non_zero) {
@@ -811,7 +769,7 @@ void klcm(klisp_State *K, TValue *xparams, TValue ptree, TValue denv)
 	    klispE_throw(K, "lcm: result has no primary");
 	    return;
 	} else if (!seen_infinite) {
-	    finite_gcd = gcd2(finite_gcd, ivalue(first));
+	    finite_gcd = (int32_t) kgcd32_64(finite_gcd, ivalue(first));
 	}
     }